15512041711

Committed 07 Jun 2025 09:59PM UTC coverage: 57.416% (+0.1%) from 57.315%

Build # 15512041711

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #44 from daisytuner/StructuredLoops

Add Structured Loops

Run Details

51 of 102 new or added lines in 20 files covered. (50.0%)

10 existing lines in 8 files now uncovered.

7618 of 13268 relevant lines covered (57.42%)

116.01 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/happens_before_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> indvar_symbols;
    for (auto atom : symbolic::atoms(update)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
        indvar_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 &&
            indvar_symbols.find(use->container()) != indvar_symbols.end()) {
            return false;
        }

        if (use->container() != indvar->get_name()) {
            continue;
        }
        if (use->element() == if_else_stmt) {
            continue;
        }
        if (use->element() == update_write->element()) {
            continue;
        }
        if (dynamic_cast<structured_control_flow::Transition*>(use->element())) {
            continue;
        }
        if (dynamic_cast<data_flow::Memlet*>(use->element())) {
            continue;
        }
        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);

    // All usages after increment of indvar must be updated
    analysis::HappensBeforeAnalysis body_happens_before(sdfg, body);
    body_happens_before.run(analysis_manager);

    auto users_after = body_happens_before.reads_after_write(*write_to_indvar);
    for (auto use : users_after) {
        if (use->container() != indvar->get_name()) {
            continue;
        }
        if (use->element() == if_else_stmt) {
            continue;
        }
        if (use->element() == write_to_indvar->element()) {
            continue;
        }

        if (auto transition = dynamic_cast<structured_control_flow::Transition*>(use->element())) {
            for (auto& entry : transition->assignments()) {
                if (symbolic::uses(entry.second, indvar->get_name())) {
                    entry.second = symbolic::subs(entry.second, indvar, update);
                }
            }
        } else if (auto memlet = dynamic_cast<data_flow::Memlet*>(use->element())) {
            for (auto& dim : memlet->subset()) {
                if (symbolic::uses(dim, indvar->get_name())) {
                    dim = symbolic::subs(dim, indvar, update);
                }
            }
        } else {
            throw InvalidSDFGException("WhileToForConversion: Expected Transition or Memlet");
        }
    }

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

daisytuner / sdfglib / 15512041711

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