17698271146

Committed 13 Sep 2025 03:06PM UTC coverage: 60.505% (+1.2%) from 59.335%

Build # 17698271146

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #219 from daisytuner/stdlib-nodes

stdlib Library Nodes and ConstantNodes

Run Details

640 of 1885 new or added lines in 107 files covered. (33.95%)

107 existing lines in 40 files now uncovered.

9443 of 15607 relevant lines covered (60.5%)

106.96 hits per line

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

0.0

/src/passes/structured_control_flow/while_to_for_conversion.cpp

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

#include "sdfg/analysis/data_dependency_analysis.h"
#include "sdfg/structured_control_flow/structured_loop.h"

namespace sdfg {
namespace passes {

bool WhileToForConversion::can_be_applied(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::While& loop
) {
    auto& sdfg = builder.subject();
    auto& body = loop.root();
    if (loop.root().size() < 2) {
        return false;
    }

    // Identify break and continue conditions
    auto end_of_body = body.at(body.size() - 1);
    if (end_of_body.second.size() > 0) {
        return false;
    }
    auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(&end_of_body.first);
    if (!if_else_stmt || if_else_stmt->size() != 2) {
        return false;
    }

    bool first_is_continue = false;
    bool first_is_break = false;
    auto& first_branch = if_else_stmt->at(0).first;
    if (first_branch.size() != 1) {
        return false;
    }
    auto first_condition = if_else_stmt->at(0).second;
    if (dynamic_cast<structured_control_flow::Break*>(&first_branch.at(0).first)) {
        first_is_break = true;
    } else if (dynamic_cast<structured_control_flow::Continue*>(&first_branch.at(0).first)) {
        first_is_continue = true;
    }
    if (!first_is_break && !first_is_continue) {
        return false;
    }

    bool second_is_continue = false;
    bool second_is_break = false;
    auto& second_branch = if_else_stmt->at(1).first;
    if (second_branch.size() != 1) {
        return false;
    }
    auto second_condition = if_else_stmt->at(1).second;
    if (dynamic_cast<structured_control_flow::Break*>(&second_branch.at(0).first)) {
        second_is_break = true;
    } else if (dynamic_cast<structured_control_flow::Continue*>(&second_branch.at(0).first)) {
        second_is_continue = true;
    }
    if (!second_is_break && !second_is_continue) {
        return false;
    }
    if (first_is_break == second_is_break) {
        return false;
    }

    // Check symbolic expressions
    if (!symbolic::is_true(symbolic::Eq(symbolic::Not(first_condition), second_condition))) {
        return false;
    }

    // Criterion: Exactly one moving iterator, which is written once
    auto& all_users = analysis_manager.get<analysis::Users>();
    analysis::UsersView body_users(all_users, body);
    analysis::User* update_write = nullptr;
    for (auto& atom : symbolic::atoms(first_condition)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
        if (symbolic::is_pointer(sym)) {
            return false;
        }
        auto& type = sdfg.type(sym->get_name());
        if (!dynamic_cast<const types::Scalar*>(&type)) {
            return false;
        }

        auto writes = body_users.writes(sym->get_name());
        if (writes.size() > 1) {
            return false;
        } else if (writes.size() == 1) {
            if (update_write != nullptr) {
                return false;
            }
            if (!dynamic_cast<structured_control_flow::Transition*>(writes.at(0)->element())) {
                return false;
            }
            update_write = writes.at(0);
        } else {
            continue;
        }
    }
    if (update_write == nullptr) {
        return false;
    }
    auto indvar = symbolic::symbol(update_write->container());
    auto update_element = dynamic_cast<structured_control_flow::Transition*>(update_write->element());
    ;
    auto update = update_element->assignments().at(indvar);

    std::unordered_set<std::string> update_symbols;
    for (auto atom : symbolic::atoms(update)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
        update_symbols.insert(sym->get_name());
    }

    // Check that we can replace all post-usages of iterator (after increment)
    auto users_after = body_users.all_uses_after(*update_write);
    for (auto use : users_after) {
        if (use->use() == analysis::Use::WRITE && update_symbols.find(use->container()) != update_symbols.end()) {
            return false;
        }
    }

    // No other continue, break or return inside loop body
    std::list<const structured_control_flow::ControlFlowNode*> queue = {&loop.root()};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();
        if (dynamic_cast<const structured_control_flow::Break*>(current)) {
            return false;
        } else if (dynamic_cast<const structured_control_flow::Continue*>(current)) {
            return false;
        } else if (dynamic_cast<const structured_control_flow::Return*>(current)) {
            return false;
        }

        if (auto sequence_stmt = dynamic_cast<const structured_control_flow::Sequence*>(current)) {
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
                queue.push_back(&sequence_stmt->at(i).first);
            }
        } else if (auto if_else = dynamic_cast<const structured_control_flow::IfElse*>(current)) {
            // Ignore the if_else_stmt
            if (if_else == if_else_stmt) {
                continue;
            }
            for (size_t i = 0; i < if_else->size(); i++) {
                queue.push_back(&if_else->at(i).first);
            }
        }
    }

    return true;
}

void WhileToForConversion::apply(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::Sequence& parent,
    structured_control_flow::While& loop
) {
    auto& sdfg = builder.subject();
    auto& body = loop.root();

    // Identify break and continue conditions
    auto last_element = body.at(body.size() - 1);
    auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(&last_element.first);

    auto first_condition = if_else_stmt->at(0).second;

    bool second_is_break = false;
    auto& second_branch = if_else_stmt->at(1).first;
    auto second_condition = if_else_stmt->at(1).second;
    if (dynamic_cast<structured_control_flow::Break*>(&second_branch.at(0).first)) {
        second_is_break = true;
    }
    auto& all_users = analysis_manager.get<analysis::Users>();
    analysis::UsersView body_users(all_users, body);
    analysis::User* write_to_indvar = nullptr;
    for (auto& atom : symbolic::atoms(first_condition)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
        auto writes = body_users.writes(sym->get_name());
        if (writes.size() == 1) {
            write_to_indvar = writes.at(0);
        } else {
            continue;
        }
    }
    auto update_element = dynamic_cast<structured_control_flow::Transition*>(write_to_indvar->element());

    auto indvar = symbolic::symbol(write_to_indvar->container());
    auto update = update_element->assignments().at(indvar);

    // Add temporary symbol for uses after increment
    auto pseudo_indvar = symbolic::symbol(builder.find_new_name(indvar->get_name()));
    builder.add_container(pseudo_indvar->get_name(), sdfg.type(indvar->get_name()));

    // All usages after increment of indvar must be replaced with pseudo_indvar
    auto users_after = body_users.all_uses_after(*write_to_indvar);
    for (auto use : users_after) {
        if (use->container() != indvar->get_name()) {
            continue;
        }

        use->element()->replace(indvar, pseudo_indvar);
    }

    // Remove update from transition
    update_element->assignments().erase(indvar);
    update_element->assignments()[pseudo_indvar] = update;

    if (second_is_break) {
        auto& for_loop = builder.convert_while(parent, loop, indvar, first_condition, indvar, update);
        builder.remove_child(for_loop.root(), for_loop.root().size() - 1);
    } else {
        auto& for_loop = builder.convert_while(parent, loop, indvar, second_condition, indvar, update);
        builder.remove_child(for_loop.root(), for_loop.root().size() - 1);
    }
};

WhileToForConversion::WhileToForConversion()
    : Pass() {

      };

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

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

    // Traverse structured SDFG
    std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();

        // Add children to queue
        if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
                if (auto match = dynamic_cast<structured_control_flow::While*>(&sequence_stmt->at(i).first)) {
                    if (this->can_be_applied(builder, analysis_manager, *match)) {
                        this->apply(builder, analysis_manager, *sequence_stmt, *match);
                        applied = true;
                    }
                }

                queue.push_back(&sequence_stmt->at(i).first);
            }
        } else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(current)) {
            for (size_t i = 0; i < if_else->size(); i++) {
                queue.push_back(&if_else->at(i).first);
            }
        } else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
            queue.push_back(&loop_stmt->root());
        } else if (auto sloop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {
            queue.push_back(&sloop_stmt->root());
        }
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/while_to_for_conversion.h"
2
3	#include "sdfg/analysis/data_dependency_analysis.h"
4	#include "sdfg/structured_control_flow/structured_loop.h"
5
6	namespace sdfg {
7	namespace passes {
8
NEW 9	bool WhileToForConversion::can_be_applied(	×
10	builder::StructuredSDFGBuilder& builder,
11	analysis::AnalysisManager& analysis_manager,
12	structured_control_flow::While& loop
13	) {
14	auto& sdfg = builder.subject();	×
15	auto& body = loop.root();	×
16	if (loop.root().size() < 2) {	×
17	return false;	×
18	}
19
20	// Identify break and continue conditions
21	auto end_of_body = body.at(body.size() - 1);	×
22	if (end_of_body.second.size() > 0) {	×
23	return false;	×
24	}
25	auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(&end_of_body.first);	×
26	if (!if_else_stmt \|\| if_else_stmt->size() != 2) {	×
27	return false;	×
28	}
29
30	bool first_is_continue = false;	×
31	bool first_is_break = false;	×
32	auto& first_branch = if_else_stmt->at(0).first;	×
33	if (first_branch.size() != 1) {	×
34	return false;	×
35	}
NEW 36	auto first_condition = if_else_stmt->at(0).second;	×
37	if (dynamic_cast<structured_control_flow::Break*>(&first_branch.at(0).first)) {	×
38	first_is_break = true;	×
39	} else if (dynamic_cast<structured_control_flow::Continue*>(&first_branch.at(0).first)) {	×
40	first_is_continue = true;	×
41	}	×
42	if (!first_is_break && !first_is_continue) {	×
43	return false;	×
44	}
45
46	bool second_is_continue = false;	×
47	bool second_is_break = false;	×
48	auto& second_branch = if_else_stmt->at(1).first;	×
49	if (second_branch.size() != 1) {	×
50	return false;	×
51	}
NEW 52	auto second_condition = if_else_stmt->at(1).second;	×
53	if (dynamic_cast<structured_control_flow::Break*>(&second_branch.at(0).first)) {	×
54	second_is_break = true;	×
55	} else if (dynamic_cast<structured_control_flow::Continue*>(&second_branch.at(0).first)) {	×
56	second_is_continue = true;	×
57	}	×
58	if (!second_is_break && !second_is_continue) {	×
59	return false;	×
60	}
61	if (first_is_break == second_is_break) {	×
62	return false;	×
63	}
64
65	// Check symbolic expressions
66	if (!symbolic::is_true(symbolic::Eq(symbolic::Not(first_condition), second_condition))) {	×
67	return false;	×
68	}
69
70	// Criterion: Exactly one moving iterator, which is written once
71	auto& all_users = analysis_manager.get<analysis::Users>();	×
72	analysis::UsersView body_users(all_users, body);	×
73	analysis::User* update_write = nullptr;	×
74	for (auto& atom : symbolic::atoms(first_condition)) {	×
75	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
76	if (symbolic::is_pointer(sym)) {	×
77	return false;	×
78	}
79	auto& type = sdfg.type(sym->get_name());	×
80	if (!dynamic_cast<const types::Scalar*>(&type)) {	×
81	return false;	×
82	}
83
84	auto writes = body_users.writes(sym->get_name());	×
85	if (writes.size() > 1) {	×
86	return false;	×
87	} else if (writes.size() == 1) {	×
88	if (update_write != nullptr) {	×
89	return false;	×
90	}
91	if (!dynamic_cast<structured_control_flow::Transition*>(writes.at(0)->element())) {	×
92	return false;	×
93	}
94	update_write = writes.at(0);	×
95	} else {	×
96	continue;	×
97	}
98	}	×
99	if (update_write == nullptr) {	×
100	return false;	×
101	}
102	auto indvar = symbolic::symbol(update_write->container());	×
NEW 103	auto update_element = dynamic_cast<structured_control_flow::Transition*>(update_write->element());	×
104	;
105	auto update = update_element->assignments().at(indvar);	×
106
107	std::unordered_set<std::string> update_symbols;	×
108	for (auto atom : symbolic::atoms(update)) {	×
109	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
110	update_symbols.insert(sym->get_name());	×
111	}	×
112
113	// Check that we can replace all post-usages of iterator (after increment)
114	auto users_after = body_users.all_uses_after(*update_write);	×
115	for (auto use : users_after) {	×
NEW 116	if (use->use() == analysis::Use::WRITE && update_symbols.find(use->container()) != update_symbols.end()) {	×
117	return false;	×
118	}
119	}
120
121	// No other continue, break or return inside loop body
122	std::list<const structured_control_flow::ControlFlowNode*> queue = {&loop.root()};	×
123	while (!queue.empty()) {	×
124	auto current = queue.front();	×
125	queue.pop_front();	×
126	if (dynamic_cast<const structured_control_flow::Break*>(current)) {	×
127	return false;	×
128	} else if (dynamic_cast<const structured_control_flow::Continue*>(current)) {	×
129	return false;	×
130	} else if (dynamic_cast<const structured_control_flow::Return*>(current)) {	×
131	return false;	×
132	}
133
134	if (auto sequence_stmt = dynamic_cast<const structured_control_flow::Sequence*>(current)) {	×
135	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
136	queue.push_back(&sequence_stmt->at(i).first);	×
137	}	×
138	} else if (auto if_else = dynamic_cast<const structured_control_flow::IfElse*>(current)) {	×
139	// Ignore the if_else_stmt
140	if (if_else == if_else_stmt) {	×
141	continue;	×
142	}
143	for (size_t i = 0; i < if_else->size(); i++) {	×
144	queue.push_back(&if_else->at(i).first);	×
145	}	×
146	}	×
147	}
148
149	return true;	×
150	}	×
151
NEW 152	void WhileToForConversion::apply(	×
153	builder::StructuredSDFGBuilder& builder,
154	analysis::AnalysisManager& analysis_manager,
155	structured_control_flow::Sequence& parent,
156	structured_control_flow::While& loop
157	) {
158	auto& sdfg = builder.subject();	×
159	auto& body = loop.root();	×
160
161	// Identify break and continue conditions
162	auto last_element = body.at(body.size() - 1);	×
163	auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(&last_element.first);	×
164
165	auto first_condition = if_else_stmt->at(0).second;	×
166
167	bool second_is_break = false;	×
168	auto& second_branch = if_else_stmt->at(1).first;	×
169	auto second_condition = if_else_stmt->at(1).second;	×
170	if (dynamic_cast<structured_control_flow::Break*>(&second_branch.at(0).first)) {	×
171	second_is_break = true;	×
172	}	×
173	auto& all_users = analysis_manager.get<analysis::Users>();	×
174	analysis::UsersView body_users(all_users, body);	×
175	analysis::User* write_to_indvar = nullptr;	×
176	for (auto& atom : symbolic::atoms(first_condition)) {	×
177	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
178	auto writes = body_users.writes(sym->get_name());	×
179	if (writes.size() == 1) {	×
180	write_to_indvar = writes.at(0);	×
181	} else {	×
182	continue;	×
183	}
184	}	×
NEW 185	auto update_element = dynamic_cast<structured_control_flow::Transition*>(write_to_indvar->element());	×
186
187	auto indvar = symbolic::symbol(write_to_indvar->container());	×
188	auto update = update_element->assignments().at(indvar);	×
189
190	// Add temporary symbol for uses after increment
191	auto pseudo_indvar = symbolic::symbol(builder.find_new_name(indvar->get_name()));	×
192	builder.add_container(pseudo_indvar->get_name(), sdfg.type(indvar->get_name()));	×
193
194	// All usages after increment of indvar must be replaced with pseudo_indvar
195	auto users_after = body_users.all_uses_after(*write_to_indvar);	×
196	for (auto use : users_after) {	×
197	if (use->container() != indvar->get_name()) {	×
198	continue;	×
199	}
200
201	use->element()->replace(indvar, pseudo_indvar);	×
202	}
203
204	// Remove update from transition
205	update_element->assignments().erase(indvar);	×
206	update_element->assignments()[pseudo_indvar] = update;	×
207
208	if (second_is_break) {	×
NEW 209	auto& for_loop = builder.convert_while(parent, loop, indvar, first_condition, indvar, update);	×
210	builder.remove_child(for_loop.root(), for_loop.root().size() - 1);	×
211	} else {	×
NEW 212	auto& for_loop = builder.convert_while(parent, loop, indvar, second_condition, indvar, update);	×
213	builder.remove_child(for_loop.root(), for_loop.root().size() - 1);	×
214	}
215	};	×
216
217	WhileToForConversion::WhileToForConversion()	×
218	: Pass() {	×
219
220	};	×
221
222	std::string WhileToForConversion::name() { return "WhileToForConversion"; };	×
223
NEW 224	bool WhileToForConversion::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
UNCOV 225	bool applied = false;	×
226
227	// Traverse structured SDFG
228	std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};	×
229	while (!queue.empty()) {	×
230	auto current = queue.front();	×
231	queue.pop_front();	×
232
233	// Add children to queue
234	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	×
235	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
NEW 236	if (auto match = dynamic_cast<structured_control_flow::While*>(&sequence_stmt->at(i).first)) {	×
237	if (this->can_be_applied(builder, analysis_manager, *match)) {	×
238	this->apply(builder, analysis_manager, sequence_stmt, match);	×
239	applied = true;	×
240	}	×
241	}	×
242
243	queue.push_back(&sequence_stmt->at(i).first);	×
244	}	×
245	} else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(current)) {	×
246	for (size_t i = 0; i < if_else->size(); i++) {	×
247	queue.push_back(&if_else->at(i).first);	×
248	}	×
249	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	×
250	queue.push_back(&loop_stmt->root());	×
NEW 251	} else if (auto sloop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {	×
252	queue.push_back(&sloop_stmt->root());	×
253	}	×
254	}
255
256	return applied;	×
257	};	×
258
259	} // namespace passes
260	} // namespace sdfg

daisytuner / sdfglib / 17698271146

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