20388902294

Committed 18 Dec 2025 07:41PM UTC coverage: 39.328% (-0.1%) from 39.454%

Build # 20388902294

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #400 from daisytuner/backward-symbol-propagation

adds backward symbol propagation

Run Details

13427 of 44322 branches covered (30.29%)

Branch coverage included in aggregate %.

113 of 250 new or added lines in 4 files covered. (45.2%)

13 existing lines in 3 files now uncovered.

11565 of 19225 relevant lines covered (60.16%)

83.99 hits per line

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

35.99

/src/passes/structured_control_flow/dead_cfg_elimination.cpp

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

#include "sdfg/structured_control_flow/structured_loop.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 (dynamic_cast<const structured_control_flow::For*>(&node)) {
        return false;
    }

    return false;
};

DeadCFGElimination::DeadCFGElimination()
    : Pass() {

      };

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;
                    }
                }

                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/structured_control_flow/structured_loop.h"
4
5	namespace sdfg {
6	namespace passes {
7
8	bool DeadCFGElimination::is_dead(const structured_control_flow::ControlFlowNode& node) {	15✔
9	if (auto block_stmt = dynamic_cast<const structured_control_flow::Block*>(&node)) {	15!
10	return (block_stmt->dataflow().nodes().size() == 0);	8✔
11	} else if (auto sequence_stmt = dynamic_cast<const structured_control_flow::Sequence*>(&node)) {	7!
12	return (sequence_stmt->size() == 0);	×
13	} else if (auto if_else_stmt = dynamic_cast<const structured_control_flow::IfElse*>(&node)) {	7!
14	return (if_else_stmt->size() == 0);	×
15	} else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(&node)) {	7!
16	return is_dead(while_stmt->root());	×
17	} else if (dynamic_cast<const structured_control_flow::For*>(&node)) {	7!
18	return false;	7✔
19	}
20
21	return false;	×
22	};	15✔
23
24	DeadCFGElimination::DeadCFGElimination()	6✔
25	: Pass() {	6✔
26
27	};	6✔
28
29	std::string DeadCFGElimination::name() { return "DeadCFGElimination"; };	×
30
31	bool DeadCFGElimination::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	6✔
32	bool applied = false;	6✔
33
34	auto& sdfg = builder.subject();	6✔
35
36	auto& root = sdfg.root();	6✔
37	if (root.size() == 0) {	6!
38	return false;	×
39	}
40
41	std::list<structured_control_flow::ControlFlowNode*> queue = {&sdfg.root()};	6!
42	while (!queue.empty()) {	38✔
43	auto curr = queue.front();	32✔
44	queue.pop_front();	32✔
45
46	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(curr)) {	32!
47	// Simplify
48	size_t i = 0;	14✔
49	while (i < sequence_stmt->size()) {	30!
50	auto child = sequence_stmt->at(i);	18!
51	symbolic::SymbolSet dead_lhs;	18✔
52	for (auto& entry : child.second.assignments()) {	21!
53	if (symbolic::eq(entry.first, entry.second)) {	3!
NEW 54	dead_lhs.insert(entry.first);	×
NEW 55	}	×
56	}
57	for (auto& lhs : dead_lhs) {	18!
NEW 58	child.second.assignments().erase(lhs);	×
NEW 59	applied = true;	×
60	}
61
62	// Return node found, everything after is dead
63	if (auto return_node = dynamic_cast<structured_control_flow::Return*>(&child.first)) {	18!
64	if (child.second.assignments().size() > 0) {	2!
65	// Clear assignments
66	child.second.assignments().clear();	2!
67	applied = true;	2✔
68	}	2✔
69	for (size_t j = i + 1; j < sequence_stmt->size();) {	3!
70	builder.remove_child(*sequence_stmt, i + 1);	1!
71	applied = true;	1✔
72	}
73	break;	2✔
74	}
75
76	// Non-empty transitions are not safe to remove
77	if (!child.second.empty()) {	16!
78	i++;	1✔
79	continue;	1✔
80	}
81
82	// Dead
83	if (is_dead(child.first)) {	15!
84	builder.remove_child(*sequence_stmt, i);	×
85	applied = true;	×
86	continue;	×
87	}
88
89	// Trivial branch
90	if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {	15!
91	auto branch = if_else_stmt->at(0);	×
92	if (symbolic::is_true(branch.second)) {	×
93	builder.move_children(branch.first, *sequence_stmt, i + 1);	×
94	builder.remove_child(*sequence_stmt, i);	×
95	applied = true;	×
96	continue;	×
97	}
98	}	×
99
100	i++;	15✔
101	}	18✔
102
103	// Add to queue
104	for (size_t j = 0; j < sequence_stmt->size(); j++) {	32!
105	queue.push_back(&sequence_stmt->at(j).first);	18!
106	}	18✔
107	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(curr)) {	32!
108	// False branches are safe to remove
109	size_t i = 0;	×
110	while (i < if_else_stmt->size()) {	×
111	auto child = if_else_stmt->at(i);	×
112	if (symbolic::is_false(child.second)) {	×
113	builder.remove_case(*if_else_stmt, i);	×
114	applied = true;	×
115	continue;	×
116	}
117
118	i++;	×
119	}	×
120
121	// Trailing dead branches are safe to remove
122	if (if_else_stmt->size() > 0) {	×
123	if (is_dead(if_else_stmt->at(if_else_stmt->size() - 1).first)) {	×
124	builder.remove_case(*if_else_stmt, if_else_stmt->size() - 1);	×
125	applied = true;	×
126	}	×
127	}	×
128
129	// If-else to simple if conversion
130	if (if_else_stmt->size() == 2) {	×
131	auto if_condition = if_else_stmt->at(0).second;	×
132	auto else_condition = if_else_stmt->at(1).second;	×
133	if (symbolic::eq(if_condition->logical_not(), else_condition)) {	×
134	if (is_dead(if_else_stmt->at(1).first)) {	×
135	builder.remove_case(*if_else_stmt, 1);	×
136	applied = true;	×
137	} else if (is_dead(if_else_stmt->at(0).first)) {	×
138	builder.remove_case(*if_else_stmt, 0);	×
139	applied = true;	×
140	}	×
141	}	×
142	}	×
143
144	// Add to queue
145	for (size_t j = 0; j < if_else_stmt->size(); j++) {	×
146	queue.push_back(&if_else_stmt->at(j).first);	×
147	}	×
148	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(curr)) {	18!
149	auto& root = loop_stmt->root();	×
150	queue.push_back(&root);	×
151	} else if (auto sloop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(curr)) {	18!
152	auto& root = sloop_stmt->root();	8!
153	queue.push_back(&root);	8!
154	} else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(curr)) {	18!
155	auto& root = map_stmt->root();	×
156	queue.push_back(&root);	×
157	}	×
158	}
159
160	return applied;	6✔
161	};	6✔
162
163	} // namespace passes
164	} // namespace sdfg

daisytuner / sdfglib / 20388902294

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