15948486670

Committed 28 Jun 2025 09:48PM UTC coverage: 65.154% (+0.1%) from 65.01%

Build # 15948486670

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #117 from daisytuner/while-loops

Improves lifting of for loops

Run Details

27 of 53 new or added lines in 4 files covered. (50.94%)

1 existing line in 1 file now uncovered.

8571 of 13155 relevant lines covered (65.15%)

144.59 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
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
NEW 106	std::unordered_set<std::string> update_symbols;	×
107	for (auto atom : symbolic::atoms(update)) {	×
108	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
NEW 109	update_symbols.insert(sym->get_name());	×
110	}	×
111
112	// Check that we can replace all post-usages of iterator (after increment)
113	auto users_after = body_users.all_uses_after(*update_write);	×
114	for (auto use : users_after) {	×
115	if (use->use() == analysis::Use::WRITE &&	×
NEW 116	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
152	void WhileToForConversion::apply(builder::StructuredSDFGBuilder& builder,	×
153	analysis::AnalysisManager& analysis_manager,
154	structured_control_flow::Sequence& parent,
155	structured_control_flow::While& loop) {
156	auto& sdfg = builder.subject();	×
157	auto& body = loop.root();	×
158
159	// Identify break and continue conditions
160	auto last_element = body.at(body.size() - 1);	×
161	auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(&last_element.first);	×
162
NEW 163	auto first_condition = if_else_stmt->at(0).second;	×
164
165	bool second_is_break = false;	×
166	auto& second_branch = if_else_stmt->at(1).first;	×
NEW 167	auto second_condition = if_else_stmt->at(1).second;	×
168	if (dynamic_cast<structured_control_flow::Break*>(&second_branch.at(0).first)) {	×
169	second_is_break = true;	×
170	}	×
171	auto& all_users = analysis_manager.get<analysis::Users>();	×
172	analysis::UsersView body_users(all_users, body);	×
173	analysis::User* write_to_indvar = nullptr;	×
174	for (auto& atom : symbolic::atoms(first_condition)) {	×
175	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
176	auto writes = body_users.writes(sym->get_name());	×
177	if (writes.size() == 1) {	×
178	write_to_indvar = writes.at(0);	×
179	} else {	×
180	continue;	×
181	}
182	}	×
183	auto update_element =	×
184	dynamic_cast<structured_control_flow::Transition*>(write_to_indvar->element());	×
185
186	auto indvar = symbolic::symbol(write_to_indvar->container());	×
187	auto update = update_element->assignments().at(indvar);	×
188
189	// Add temporary symbol for uses after increment
NEW 190	auto pseudo_indvar = symbolic::symbol(builder.find_new_name(indvar->get_name()));	×
NEW 191	builder.add_container(pseudo_indvar->get_name(), sdfg.type(indvar->get_name()));	×
192
193	// All usages after increment of indvar must be replaced with pseudo_indvar
NEW 194	auto users_after = body_users.all_uses_after(*write_to_indvar);	×
195	for (auto use : users_after) {	×
196	if (use->container() != indvar->get_name()) {	×
197	continue;	×
198	}
199
NEW 200	use->element()->replace(indvar, pseudo_indvar);	×
201	}
202
203	// Remove update from transition
NEW 204	update_element->assignments().erase(indvar);	×
NEW 205	update_element->assignments()[pseudo_indvar] = update;	×
206
207	if (second_is_break) {	×
208	auto& for_loop =	×
209	builder.convert_while(parent, loop, indvar, first_condition, indvar, update);	×
210	builder.remove_child(for_loop.root(), for_loop.root().size() - 1);	×
211	} else {	×
212	auto& for_loop =	×
213	builder.convert_while(parent, loop, indvar, second_condition, indvar, update);	×
214	builder.remove_child(for_loop.root(), for_loop.root().size() - 1);	×
215	}
216	};	×
217
218	WhileToForConversion::WhileToForConversion()	×
219	: Pass() {	×
220
221	};	×
222
223	std::string WhileToForConversion::name() { return "WhileToForConversion"; };	×
224
225	bool WhileToForConversion::run_pass(builder::StructuredSDFGBuilder& builder,	×
226	analysis::AnalysisManager& analysis_manager) {
227	bool applied = false;	×
228
229	// Traverse structured SDFG
230	std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};	×
231	while (!queue.empty()) {	×
232	auto current = queue.front();	×
233	queue.pop_front();	×
234
235	// Add children to queue
236	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	×
237	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
238	if (auto match = dynamic_cast<structured_control_flow::While*>(	×
239	&sequence_stmt->at(i).first)) {	×
240	if (this->can_be_applied(builder, analysis_manager, *match)) {	×
241	this->apply(builder, analysis_manager, sequence_stmt, match);	×
242	applied = true;	×
243	}	×
244	}	×
245
246	queue.push_back(&sequence_stmt->at(i).first);	×
247	}	×
248	} else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(current)) {	×
249	for (size_t i = 0; i < if_else->size(); i++) {	×
250	queue.push_back(&if_else->at(i).first);	×
251	}	×
252	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	×
253	queue.push_back(&loop_stmt->root());	×
254	} else if (auto sloop_stmt =	×
255	dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {	×
256	queue.push_back(&sloop_stmt->root());	×
257	}	×
258	}
259
260	return applied;	×
261	};	×
262
263	} // namespace passes
264	} // namespace sdfg

daisytuner / sdfglib / 15948486670

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