15973046991

Committed 30 Jun 2025 12:34PM UTC coverage: 64.64% (-0.2%) from 64.86%

Build # 15973046991

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #123 from daisytuner/simplify-tiling-transformation

Avoid deep copy in loop tiling

Run Details

31 of 32 new or added lines in 2 files covered. (96.88%)

27 existing lines in 6 files now uncovered.

8643 of 13371 relevant lines covered (64.64%)

171.55 hits per line

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

43.43

/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;
    }
    auto last = root.at(root.size() - 1);
    if (last.second.empty() && dynamic_cast<structured_control_flow::Return*>(&last.first)) {
        builder.remove_child(root, root.size() - 1);
        applied = true;
    }

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

daisytuner / sdfglib / 15973046991

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