23290386671

Committed 19 Mar 2026 10:23AM UTC coverage: 63.42% (-0.4%) from 63.839%

Build # 23290386671

Build Type

Pull #600

github

Committed by

web-flow

Commit Message

Merge a96768fad into 5fb101d73

Pull Request Pull Request #600: moves transformations from sdfg to opt

Coverage Stats

17 of 53 new or added lines in 1 file covered. (32.08%)

4 existing lines in 3 files now uncovered.

26084 of 41129 relevant lines covered (63.42%)

399.2 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

71.33

/sdfg/src/passes/structured_control_flow/dead_cfg_elimination.cpp

#include "sdfg/passes/structured_control_flow/dead_cfg_elimination.h"

#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/symbolic/assumptions.h"
#include "sdfg/symbolic/conjunctive_normal_form.h"
#include "sdfg/symbolic/series.h"

namespace sdfg {
namespace passes {

bool DeadCFGElimination::is_dead(const structured_control_flow::ControlFlowNode& node) {
    if (auto block_stmt = dynamic_cast<const structured_control_flow::Block*>(&node)) {
        return (block_stmt->dataflow().nodes().size() == 0);
    } else if (auto sequence_stmt = dynamic_cast<const structured_control_flow::Sequence*>(&node)) {
        return (sequence_stmt->size() == 0);
    } else if (auto if_else_stmt = dynamic_cast<const structured_control_flow::IfElse*>(&node)) {
        return (if_else_stmt->size() == 0);
    } else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(&node)) {
        return is_dead(while_stmt->root());
    } else if (auto sloop = dynamic_cast<const structured_control_flow::StructuredLoop*>(&node)) {
        if (sloop->root().size() != 0) {
            return false;
        }
        // TODO: Check use of indvar later
        return permissive_;
    }

    return false;
};

bool DeadCFGElimination::is_trivial(structured_control_flow::Map* loop) {
    // Check if stride is 1
    if (!analysis::LoopAnalysis::is_contiguous(loop, symbolic::Assumptions())) {
        return false;
    }

    auto bound = analysis::LoopAnalysis::canonical_bound(loop, symbolic::Assumptions());
    if (bound.is_null()) {
        return false;
    }
    auto init = loop->init();

    // Check if bound - init == 1
    auto trip_count = symbolic::sub(bound, init);
    return symbolic::eq(trip_count, symbolic::one());
}

DeadCFGElimination::DeadCFGElimination()
    : Pass(), permissive_(false) {

      };

DeadCFGElimination::DeadCFGElimination(bool permissive)
    : Pass(), permissive_(permissive) {

      };

std::string DeadCFGElimination::name() { return "DeadCFGElimination"; };

bool DeadCFGElimination::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    bool applied = false;

    auto& sdfg = builder.subject();

    auto& root = sdfg.root();
    if (root.size() == 0) {
        return false;
    }

    std::list<structured_control_flow::ControlFlowNode*> queue = {&sdfg.root()};
    while (!queue.empty()) {
        auto curr = queue.front();
        queue.pop_front();

        if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(curr)) {
            // Simplify
            size_t i = 0;
            while (i < sequence_stmt->size()) {
                auto child = sequence_stmt->at(i);
                symbolic::SymbolSet dead_lhs;
                for (auto& entry : child.second.assignments()) {
                    if (symbolic::eq(entry.first, entry.second)) {
                        dead_lhs.insert(entry.first);
                    }
                }
                for (auto& lhs : dead_lhs) {
                    child.second.assignments().erase(lhs);
                    applied = true;
                }

                // Return node found, everything after is dead
                if (auto return_node = dynamic_cast<structured_control_flow::Return*>(&child.first)) {
                    if (child.second.assignments().size() > 0) {
                        // Clear assignments
                        child.second.assignments().clear();
                        applied = true;
                    }
                    for (size_t j = i + 1; j < sequence_stmt->size();) {
                        builder.remove_child(*sequence_stmt, i + 1);
                        applied = true;
                    }
                    break;
                }

                // Non-empty transitions are not safe to remove
                if (!child.second.empty()) {
                    i++;
                    continue;
                }

                // Dead
                if (is_dead(child.first)) {
                    builder.remove_child(*sequence_stmt, i);
                    applied = true;
                    continue;
                }

                // Trivial branch
                if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {
                    auto branch = if_else_stmt->at(0);
                    if (symbolic::is_true(branch.second)) {
                        builder.move_children(branch.first, *sequence_stmt, i + 1);
                        builder.remove_child(*sequence_stmt, i);
                        applied = true;
                        continue;
                    }
                }

                // Trivial structured loop (bound - init == 1 and stride == 1)
                if (auto sloop = dynamic_cast<structured_control_flow::Map*>(&child.first)) {
                    if (is_trivial(sloop)) {
                        auto indvar = sloop->indvar();
                        auto init = sloop->init();
                        sloop->root().replace(indvar, init);

                        // Move children from loop body to parent sequence
                        builder.move_children(sloop->root(), *sequence_stmt, i + 1);

                        // Remove the loop
                        builder.remove_child(*sequence_stmt, i);
                        applied = true;
                        continue;
                    }
                }

                i++;
            }

            // Add to queue
            for (size_t j = 0; j < sequence_stmt->size(); j++) {
                queue.push_back(&sequence_stmt->at(j).first);
            }
        } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(curr)) {
            // False branches are safe to remove
            size_t i = 0;
            while (i < if_else_stmt->size()) {
                auto child = if_else_stmt->at(i);
                if (symbolic::is_false(child.second)) {
                    builder.remove_case(*if_else_stmt, i);
                    applied = true;
                    continue;
                }

                i++;
            }

            // Trailing dead branches are safe to remove
            if (if_else_stmt->size() > 0) {
                if (is_dead(if_else_stmt->at(if_else_stmt->size() - 1).first)) {
                    builder.remove_case(*if_else_stmt, if_else_stmt->size() - 1);
                    applied = true;
                }
            }

            // If-else to simple if conversion
            if (if_else_stmt->size() == 2) {
                auto if_condition = if_else_stmt->at(0).second;
                auto else_condition = if_else_stmt->at(1).second;
                if (symbolic::eq(if_condition->logical_not(), else_condition)) {
                    if (is_dead(if_else_stmt->at(1).first)) {
                        builder.remove_case(*if_else_stmt, 1);
                        applied = true;
                    } else if (is_dead(if_else_stmt->at(0).first)) {
                        builder.remove_case(*if_else_stmt, 0);
                        applied = true;
                    }
                }
            }

            // Add to queue
            for (size_t j = 0; j < if_else_stmt->size(); j++) {
                queue.push_back(&if_else_stmt->at(j).first);
            }
        } else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(curr)) {
            auto& root = loop_stmt->root();
            queue.push_back(&root);
        } else if (auto sloop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(curr)) {
            auto& root = sloop_stmt->root();
            queue.push_back(&root);
        } else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(curr)) {
            auto& root = map_stmt->root();
            queue.push_back(&root);
        }
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/dead_cfg_elimination.h"
2
3	#include "sdfg/analysis/loop_analysis.h"
4	#include "sdfg/structured_control_flow/structured_loop.h"
5	#include "sdfg/symbolic/assumptions.h"
6	#include "sdfg/symbolic/conjunctive_normal_form.h"
7	#include "sdfg/symbolic/series.h"
8
9	namespace sdfg {
10	namespace passes {
11
12	bool DeadCFGElimination::is_dead(const structured_control_flow::ControlFlowNode& node) {	189✔
13	if (auto block_stmt = dynamic_cast<const structured_control_flow::Block*>(&node)) {	189✔
14	return (block_stmt->dataflow().nodes().size() == 0);	92✔
15	} else if (auto sequence_stmt = dynamic_cast<const structured_control_flow::Sequence*>(&node)) {	97✔
16	return (sequence_stmt->size() == 0);	20✔
17	} else if (auto if_else_stmt = dynamic_cast<const structured_control_flow::IfElse*>(&node)) {	77✔
18	return (if_else_stmt->size() == 0);	16✔
19	} else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(&node)) {	61✔
20	return is_dead(while_stmt->root());	×
21	} else if (auto sloop = dynamic_cast<const structured_control_flow::StructuredLoop*>(&node)) {	61✔
22	if (sloop->root().size() != 0) {	61✔
23	return false;	60✔
24	}	60✔
25	// TODO: Check use of indvar later
26	return permissive_;	1✔
27	}	61✔
28
29	return false;	×
30	};	189✔
31
32	bool DeadCFGElimination::is_trivial(structured_control_flow::Map* loop) {	37✔
33	// Check if stride is 1
34	if (!analysis::LoopAnalysis::is_contiguous(loop, symbolic::Assumptions())) {	37✔
35	return false;	2✔
36	}	2✔
37
38	auto bound = analysis::LoopAnalysis::canonical_bound(loop, symbolic::Assumptions());	35✔
39	if (bound.is_null()) {	35✔
40	return false;	×
41	}	×
42	auto init = loop->init();	35✔
43
44	// Check if bound - init == 1
45	auto trip_count = symbolic::sub(bound, init);	35✔
46	return symbolic::eq(trip_count, symbolic::one());	35✔
47	}	35✔
48
49	DeadCFGElimination::DeadCFGElimination()
50	: Pass(), permissive_(false) {	27✔
51
52	};	27✔
53
54	DeadCFGElimination::DeadCFGElimination(bool permissive)
UNCOV 55	: Pass(), permissive_(permissive) {	×
56
UNCOV 57	};	×
58
59	std::string DeadCFGElimination::name() { return "DeadCFGElimination"; };	×
60
61	bool DeadCFGElimination::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	31✔
62	bool applied = false;	31✔
63
64	auto& sdfg = builder.subject();	31✔
65
66	auto& root = sdfg.root();	31✔
67	if (root.size() == 0) {	31✔
68	return false;	×
69	}	×
70
71	std::list<structured_control_flow::ControlFlowNode*> queue = {&sdfg.root()};	31✔
72	while (!queue.empty()) {	307✔
73	auto curr = queue.front();	276✔
74	queue.pop_front();	276✔
75
76	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(curr)) {	276✔
77	// Simplify
78	size_t i = 0;	110✔
79	while (i < sequence_stmt->size()) {	285✔
80	auto child = sequence_stmt->at(i);	182✔
81	symbolic::SymbolSet dead_lhs;	182✔
82	for (auto& entry : child.second.assignments()) {	182✔
83	if (symbolic::eq(entry.first, entry.second)) {	4✔
84	dead_lhs.insert(entry.first);	×
85	}	×
86	}	4✔
87	for (auto& lhs : dead_lhs) {	182✔
88	child.second.assignments().erase(lhs);	×
89	applied = true;	×
90	}	×
91
92	// Return node found, everything after is dead
93	if (auto return_node = dynamic_cast<structured_control_flow::Return*>(&child.first)) {	182✔
94	if (child.second.assignments().size() > 0) {	7✔
95	// Clear assignments
96	child.second.assignments().clear();	2✔
97	applied = true;	2✔
98	}	2✔
99	for (size_t j = i + 1; j < sequence_stmt->size();) {	8✔
100	builder.remove_child(*sequence_stmt, i + 1);	1✔
101	applied = true;	1✔
102	}	1✔
103	break;	7✔
104	}	7✔
105
106	// Non-empty transitions are not safe to remove
107	if (!child.second.empty()) {	175✔
108	i++;	2✔
109	continue;	2✔
110	}	2✔
111
112	// Dead
113	if (is_dead(child.first)) {	173✔
114	builder.remove_child(*sequence_stmt, i);	8✔
115	applied = true;	8✔
116	continue;	8✔
117	}	8✔
118
119	// Trivial branch
120	if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {	165✔
121	auto branch = if_else_stmt->at(0);	16✔
122	if (symbolic::is_true(branch.second)) {	16✔
123	builder.move_children(branch.first, *sequence_stmt, i + 1);	×
124	builder.remove_child(*sequence_stmt, i);	×
125	applied = true;	×
126	continue;	×
127	}	×
128	}	16✔
129
130	// Trivial structured loop (bound - init == 1 and stride == 1)
131	if (auto sloop = dynamic_cast<structured_control_flow::Map*>(&child.first)) {	165✔
132	if (is_trivial(sloop)) {	37✔
133	auto indvar = sloop->indvar();	4✔
134	auto init = sloop->init();	4✔
135	sloop->root().replace(indvar, init);	4✔
136
137	// Move children from loop body to parent sequence
138	builder.move_children(sloop->root(), *sequence_stmt, i + 1);	4✔
139
140	// Remove the loop
141	builder.remove_child(*sequence_stmt, i);	4✔
142	applied = true;	4✔
143	continue;	4✔
144	}	4✔
145	}	37✔
146
147	i++;	161✔
148	}	161✔
149
150	// Add to queue
151	for (size_t j = 0; j < sequence_stmt->size(); j++) {	280✔
152	queue.push_back(&sequence_stmt->at(j).first);	170✔
153	}	170✔
154	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(curr)) {	166✔
155	// False branches are safe to remove
156	size_t i = 0;	16✔
157	while (i < if_else_stmt->size()) {	32✔
158	auto child = if_else_stmt->at(i);	16✔
159	if (symbolic::is_false(child.second)) {	16✔
160	builder.remove_case(*if_else_stmt, i);	×
161	applied = true;	×
162	continue;	×
163	}	×
164
165	i++;	16✔
166	}	16✔
167
168	// Trailing dead branches are safe to remove
169	if (if_else_stmt->size() > 0) {	16✔
170	if (is_dead(if_else_stmt->at(if_else_stmt->size() - 1).first)) {	16✔
171	builder.remove_case(*if_else_stmt, if_else_stmt->size() - 1);	×
172	applied = true;	×
173	}	×
174	}	16✔
175
176	// If-else to simple if conversion
177	if (if_else_stmt->size() == 2) {	16✔
178	auto if_condition = if_else_stmt->at(0).second;	×
179	auto else_condition = if_else_stmt->at(1).second;	×
180	if (symbolic::eq(if_condition->logical_not(), else_condition)) {	×
181	if (is_dead(if_else_stmt->at(1).first)) {	×
182	builder.remove_case(*if_else_stmt, 1);	×
183	applied = true;	×
184	} else if (is_dead(if_else_stmt->at(0).first)) {	×
185	builder.remove_case(*if_else_stmt, 0);	×
186	applied = true;	×
187	}	×
188	}	×
189	}	×
190
191	// Add to queue
192	for (size_t j = 0; j < if_else_stmt->size(); j++) {	32✔
193	queue.push_back(&if_else_stmt->at(j).first);	16✔
194	}	16✔
195	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(curr)) {	150✔
196	auto& root = loop_stmt->root();	×
197	queue.push_back(&root);	×
198	} else if (auto sloop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(curr)) {	150✔
199	auto& root = sloop_stmt->root();	59✔
200	queue.push_back(&root);	59✔
201	} else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(curr)) {	91✔
202	auto& root = map_stmt->root();	×
203	queue.push_back(&root);	×
204	}	×
205	}	276✔
206
207	return applied;	31✔
208	};	31✔
209
210	} // namespace passes
211	} // namespace sdfg

daisytuner / docc / 23290386671

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous