15044057891

Committed 15 May 2025 11:42AM UTC coverage: 59.37% (+1.8%) from 57.525%

Build # 15044057891

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #14 from daisytuner/sanitizers

enables sanitizer on unit tests

Run Details

63 of 67 new or added lines in 47 files covered. (94.03%)

570 existing lines in 62 files now uncovered.

7356 of 12390 relevant lines covered (59.37%)

505.93 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 (auto break_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {
            return false;
        } else if (auto continue_stmt =
                       dynamic_cast<const structured_control_flow::Continue*>(current)) {
            return false;
        } else if (auto return_stmt =
                       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);

    bool first_is_continue = false;
    bool first_is_break = false;
    auto& first_branch = if_else_stmt->at(0).first;
    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;
    }

    bool second_is_continue = false;
    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;
    } else if (dynamic_cast<structured_control_flow::Continue*>(&second_branch.at(0).first)) {
        second_is_continue = 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 {
            assert(false);
        }
    }

    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());
        }
    }

    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;	×
UNCOV 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;	×
UNCOV 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);	×
UNCOV 92	} else {	×
93	continue;	×
94	}
95	}	×
96	if (update_write == nullptr) {	×
97	return false;	×
98	}
99	auto indvar = symbolic::symbol(update_write->container());	×
UNCOV 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 (auto break_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {	×
142	return false;	×
143	} else if (auto continue_stmt =	×
144	dynamic_cast<const structured_control_flow::Continue*>(current)) {	×
145	return false;	×
146	} else if (auto return_stmt =	×
147	dynamic_cast<const structured_control_flow::Return*>(current)) {	×
148	return false;	×
149	}
150
151	if (auto sequence_stmt = dynamic_cast<const structured_control_flow::Sequence*>(current)) {	×
152	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
153	queue.push_back(&sequence_stmt->at(i).first);	×
UNCOV 154	}	×
155	} else if (auto if_else = dynamic_cast<const structured_control_flow::IfElse*>(current)) {	×
156	// Ignore the if_else_stmt
157	if (if_else == if_else_stmt) {	×
158	continue;	×
159	}
160	for (size_t i = 0; i < if_else->size(); i++) {	×
161	queue.push_back(&if_else->at(i).first);	×
UNCOV 162	}	×
UNCOV 163	}	×
164	}
165
166	return true;	×
167	}	×
168
169	void WhileToForConversion::apply(builder::StructuredSDFGBuilder& builder,	×
170	analysis::AnalysisManager& analysis_manager,
171	structured_control_flow::Sequence& parent,
172	structured_control_flow::While& loop) {
173	auto& sdfg = builder.subject();	×
174	auto& body = loop.root();	×
175
176	// Identify break and continue conditions
177	auto last_element = body.at(body.size() - 1);	×
178	auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(&last_element.first);	×
179
180	bool first_is_continue = false;	×
181	bool first_is_break = false;	×
182	auto& first_branch = if_else_stmt->at(0).first;	×
183	auto& first_condition = if_else_stmt->at(0).second;	×
184	if (dynamic_cast<structured_control_flow::Break*>(&first_branch.at(0).first)) {	×
185	first_is_break = true;	×
186	} else if (dynamic_cast<structured_control_flow::Continue*>(&first_branch.at(0).first)) {	×
187	first_is_continue = true;	×
UNCOV 188	}	×
189
190	bool second_is_continue = false;	×
191	bool second_is_break = false;	×
192	auto& second_branch = if_else_stmt->at(1).first;	×
193	auto& second_condition = if_else_stmt->at(1).second;	×
194	if (dynamic_cast<structured_control_flow::Break*>(&second_branch.at(0).first)) {	×
195	second_is_break = true;	×
196	} else if (dynamic_cast<structured_control_flow::Continue*>(&second_branch.at(0).first)) {	×
197	second_is_continue = true;	×
UNCOV 198	}	×
199
200	auto& all_users = analysis_manager.get<analysis::Users>();	×
201	analysis::UsersView body_users(all_users, body);	×
202	analysis::User* write_to_indvar = nullptr;	×
203	for (auto& atom : symbolic::atoms(first_condition)) {	×
204	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
205	auto writes = body_users.writes(sym->get_name());	×
206	if (writes.size() == 1) {	×
207	write_to_indvar = writes.at(0);	×
UNCOV 208	} else {	×
209	continue;	×
210	}
211	}	×
UNCOV 212	auto update_element =	×
213	dynamic_cast<structured_control_flow::Transition*>(write_to_indvar->element());	×
214
215	auto indvar = symbolic::symbol(write_to_indvar->container());	×
216	auto update = update_element->assignments().at(indvar);	×
217
218	// All usages after increment of indvar must be updated
219	analysis::HappensBeforeAnalysis body_happens_before(sdfg, body);	×
220	body_happens_before.run(analysis_manager);	×
221
222	auto users_after = body_happens_before.reads_after_write(*write_to_indvar);	×
223	for (auto use : users_after) {	×
224	if (use->container() != indvar->get_name()) {	×
225	continue;	×
226	}
227	if (use->element() == if_else_stmt) {	×
228	continue;	×
229	}
230	if (use->element() == write_to_indvar->element()) {	×
231	continue;	×
232	}
233
234	if (auto transition = dynamic_cast<structured_control_flow::Transition*>(use->element())) {	×
235	for (auto& entry : transition->assignments()) {	×
236	if (symbolic::uses(entry.second, indvar->get_name())) {	×
237	entry.second = symbolic::subs(entry.second, indvar, update);	×
UNCOV 238	}	×
239	}
240	} else if (auto memlet = dynamic_cast<data_flow::Memlet*>(use->element())) {	×
241	for (auto& dim : memlet->subset()) {	×
242	if (symbolic::uses(dim, indvar->get_name())) {	×
243	dim = symbolic::subs(dim, indvar, update);	×
UNCOV 244	}	×
245	}
UNCOV 246	} else {	×
247	assert(false);	×
248	}
249	}
250
251	if (second_is_break) {	×
252	update_element->assignments().erase(indvar);	×
UNCOV 253	auto& for_loop =	×
254	builder.convert_while(parent, loop, indvar, first_condition, indvar, update);	×
255	builder.remove_child(for_loop.root(), for_loop.root().size() - 1);	×
UNCOV 256	} else {	×
257	update_element->assignments().erase(indvar);	×
UNCOV 258	auto& for_loop =	×
259	builder.convert_while(parent, loop, indvar, second_condition, indvar, update);	×
260	builder.remove_child(for_loop.root(), for_loop.root().size() - 1);	×
261	}
262	};	×
263
264	WhileToForConversion::WhileToForConversion()	×
265	: Pass(){	×
266
267	};	×
268
269	std::string WhileToForConversion::name() { return "WhileToForConversion"; };	×
270
271	bool WhileToForConversion::run_pass(builder::StructuredSDFGBuilder& builder,	×
272	analysis::AnalysisManager& analysis_manager) {
273	bool applied = false;	×
274
275	// Traverse structured SDFG
276	std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};	×
277	while (!queue.empty()) {	×
278	auto current = queue.front();	×
279	queue.pop_front();	×
280
281	// Add children to queue
282	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	×
283	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
284	if (auto match = dynamic_cast<structured_control_flow::While*>(	×
285	&sequence_stmt->at(i).first)) {	×
286	if (this->can_be_applied(builder, analysis_manager, *match)) {	×
287	this->apply(builder, analysis_manager, sequence_stmt, match);	×
288	applied = true;	×
UNCOV 289	}	×
UNCOV 290	}	×
291
292	queue.push_back(&sequence_stmt->at(i).first);	×
UNCOV 293	}	×
294	} else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(current)) {	×
295	for (size_t i = 0; i < if_else->size(); i++) {	×
296	queue.push_back(&if_else->at(i).first);	×
UNCOV 297	}	×
298	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	×
299	queue.push_back(&loop_stmt->root());	×
300	} else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {	×
301	queue.push_back(&for_stmt->root());	×
302	} else if (auto kern_stmt = dynamic_cast<const structured_control_flow::Kernel*>(current)) {	×
303	queue.push_back(&kern_stmt->root());	×
UNCOV 304	}	×
305	}
306
307	return applied;	×
308	};	×
309
310	} // namespace passes
311	} // namespace sdfg

daisytuner / sdfglib / 15044057891

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