15340968114

Committed 30 May 2025 06:47AM UTC coverage: 58.553% (+0.2%) from 58.324%

Build # 15340968114

Build Type

push

github

Committed by

web-flow

Commit Message

Add parallel Map node

* Introduce Map data structure

* Prepare infrastructure

* implement analysis support

* Add basic infrastructure

* visualizer/serializer

* include fix

* update from main

* remove default

* happens before test + fixes

* builder test

* dispatcher test

* visitor, copy and serializer tests

* for2map structures

* for2map conversion draft

* add tests

* Bug fixes

* small updates from feedback

* Visitor style pass implementation

* cleanup

* fixes linting errors

---------

Co-authored-by: Lukas Truemper <lukas.truemper@outlook.de>

Run Details

258 of 381 new or added lines in 26 files covered. (67.72%)

17 existing lines in 14 files now uncovered.

8184 of 13977 relevant lines covered (58.55%)

109.83 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"

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

daisytuner / sdfglib / 15340968114

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