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

51.63

/src/transformations/loop_slicing.cpp

#include "sdfg/transformations/loop_slicing.h"

#include "sdfg/analysis/data_parallelism_analysis.h"
#include "sdfg/deepcopy/structured_sdfg_deep_copy.h"
#include "sdfg/structured_control_flow/structured_loop.h"

namespace sdfg {
namespace transformations {

enum class LoopSlicingType { Init, Bound, Split_Lt, Split_Le };

LoopSlicing::LoopSlicing(structured_control_flow::Sequence& parent,
                         structured_control_flow::StructuredLoop& loop)
    : parent_(parent), loop_(loop) {

      };

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

bool LoopSlicing::can_be_applied(builder::StructuredSDFGBuilder& builder,
                                 analysis::AnalysisManager& analysis_manager) {
    auto& sdfg = builder.subject();

    if (!analysis::DataParallelismAnalysis::is_contiguous(loop_)) {
        return false;
    }

    // Collect moving symbols
    std::unordered_set<std::string> moving_symbols;
    auto& all_users = analysis_manager.get<analysis::Users>();
    auto& body = loop_.root();
    analysis::UsersView users(all_users, body);
    for (auto& entry : users.writes()) {
        auto& type = sdfg.type(entry->container());
        if (!dynamic_cast<const types::Scalar*>(&type)) {
            continue;
        }
        if (!types::is_integer(type.primitive_type())) {
            continue;
        }
        moving_symbols.insert(entry->container());
    }

    // Check if loop is sliced by if-elses
    auto indvar = loop_.indvar();
    for (size_t i = 0; i < body.size(); i++) {
        auto child = body.at(i);
        if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {
            if (child.second.assignments().size() > 0) {
                return false;
            }
            if (if_else->size() != 2) {
                return false;
            }

            // Validate condition
            auto branch_1 = if_else->at(0);
            auto condition_1 = branch_1.second;
            if (!symbolic::uses(condition_1, indvar)) {
                return false;
            }
            auto condition_2 = if_else->at(1).second;
            if (!symbolic::eq(condition_1, condition_2->logical_not())) {
                return false;
            }
            for (auto& atom : symbolic::atoms(condition_1)) {
                auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
                if (moving_symbols.find(sym->get_name()) != moving_symbols.end()) {
                    return false;
                }
            }
            auto bound = analysis::DataParallelismAnalysis::bound(loop_);
            if (bound == SymEngine::null) {
                return false;
            }

            // Case: indvar == init
            if (symbolic::eq(condition_1, symbolic::Eq(indvar, loop_.init()))) {
                return true;
            }

            // Case: indvar == bound - 1
            if (symbolic::eq(condition_1,
                             symbolic::Eq(indvar, symbolic::sub(bound, symbolic::one())))) {
                return true;
            }

            // Case: indvar < new_bound
            if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition_1)) {
                return true;
            }

            // Case: indvar <= new_bound
            if (SymEngine::is_a<SymEngine::LessThan>(*condition_1)) {
                return true;
            }

            return false;
        }
    }

    return false;
};

void LoopSlicing::apply(builder::StructuredSDFGBuilder& builder,
                        analysis::AnalysisManager& analysis_manager) {
    auto& sdfg = builder.subject();

    auto& body = loop_.root();
    auto indvar = loop_.indvar();

    // Collect loop locals
    auto& users = analysis_manager.get<analysis::Users>();
    auto locals = users.locals(sdfg, body);

    // Find the if-else that slices the loop
    structured_control_flow::IfElse* if_else = nullptr;
    size_t if_else_index = 0;
    for (size_t i = 0; i < body.size(); i++) {
        auto child = body.at(i);
        auto if_else_ = dynamic_cast<structured_control_flow::IfElse*>(&child.first);
        if (if_else_) {
            if_else_index = i;
            if_else = if_else_;
            break;
        }
    }
    if (if_else == nullptr) {
        throw InvalidSDFGException("LoopSlicing: Expected IfElse");
    }

    auto branch_1 = if_else->at(0);
    auto condition_1 = branch_1.second;
    auto bound = analysis::DataParallelismAnalysis::bound(loop_);

    LoopSlicingType slice_type = LoopSlicingType::Init;
    if (symbolic::eq(condition_1, symbolic::Eq(indvar, loop_.init()))) {
        slice_type = LoopSlicingType::Init;
    } else if (symbolic::eq(condition_1,
                            symbolic::Eq(indvar, symbolic::sub(bound, symbolic::one())))) {
        slice_type = LoopSlicingType::Bound;
    } else if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition_1)) {
        slice_type = LoopSlicingType::Split_Lt;
    } else if (SymEngine::is_a<SymEngine::LessThan>(*condition_1)) {
        slice_type = LoopSlicingType::Split_Le;
    }

    // Slice loop
    auto indvar_slice_str = builder.find_new_name(indvar->get_name());
    builder.add_container(indvar_slice_str, sdfg.type(indvar->get_name()));
    auto indvar_slice = SymEngine::symbol(indvar_slice_str);
    structured_control_flow::For* loop_slice = nullptr;
    structured_control_flow::For* loop_slice_2 = nullptr;
    switch (slice_type) {
        case LoopSlicingType::Init: {
            auto init_slice = loop_.init();
            auto condition_slice =
                symbolic::Lt(indvar_slice, symbolic::add(loop_.init(), symbolic::one()));
            auto increment_slice = symbolic::add(indvar_slice, symbolic::one());
            loop_slice = &builder
                              .add_for_before(parent_, loop_, indvar_slice, condition_slice,
                                              init_slice, increment_slice)
                              .first;
            loop_slice_2 =
                &builder
                     .add_for_after(parent_, loop_, loop_.indvar(), loop_.condition(),
                                    symbolic::add(loop_.init(), symbolic::one()), loop_.update())
                     .first;
            break;
        }
        case LoopSlicingType::Bound: {
            auto init_slice = symbolic::sub(bound, symbolic::one());
            auto condition_slice = symbolic::subs(loop_.condition(), loop_.indvar(), indvar_slice);
            auto increment_slice = symbolic::add(indvar_slice, symbolic::one());
            loop_slice = &builder
                              .add_for_after(parent_, loop_, indvar_slice, condition_slice,
                                             init_slice, increment_slice)
                              .first;
            loop_slice_2 = &builder
                                .add_for_before(
                                    parent_, loop_, loop_.indvar(),
                                    symbolic::Lt(loop_.indvar(),
                                                 symbolic::sub(loop_.condition(), symbolic::one())),
                                    loop_.init(), loop_.update())
                                .first;
            break;
        }
        case LoopSlicingType::Split_Lt: {
            auto init_slice = loop_.init();
            auto condition_slice =
                symbolic::And(symbolic::subs(condition_1, indvar, indvar_slice),
                              symbolic::subs(loop_.condition(), indvar, indvar_slice));
            auto increment_slice = symbolic::add(indvar_slice, symbolic::one());
            loop_slice = &builder
                              .add_for_before(parent_, loop_, indvar_slice, condition_slice,
                                              init_slice, increment_slice)
                              .first;

            auto condition_bound =
                SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(condition_1);
            auto condition_bound_args = condition_bound->get_args();
            auto condition_bound_args_bound = condition_bound_args.at(0);
            if (symbolic::eq(condition_bound_args_bound, loop_.indvar())) {
                condition_bound_args_bound = condition_bound_args.at(1);
            }

            loop_slice_2 = &builder
                                .add_for_after(parent_, loop_, loop_.indvar(), loop_.condition(),
                                               condition_bound_args_bound, loop_.update())
                                .first;
            break;
        }
        case LoopSlicingType::Split_Le: {
            auto init_slice = loop_.init();
            auto condition_slice =
                symbolic::And(symbolic::subs(condition_1, indvar, indvar_slice),
                              symbolic::subs(loop_.condition(), indvar, indvar_slice));
            auto increment_slice = symbolic::add(indvar_slice, symbolic::one());
            loop_slice = &builder
                              .add_for_before(parent_, loop_, indvar_slice, condition_slice,
                                              init_slice, increment_slice)
                              .first;

            auto condition_bound =
                SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(condition_1);
            auto condition_bound_args = condition_bound->get_args();
            auto condition_bound_args_bound = condition_bound_args.at(0);
            if (symbolic::eq(condition_bound_args_bound, loop_.indvar())) {
                condition_bound_args_bound = condition_bound_args.at(1);
            }

            loop_slice_2 =
                &builder
                     .add_for_after(parent_, loop_, loop_.indvar(), loop_.condition(),
                                    symbolic::add(condition_bound_args_bound, symbolic::one()),
                                    loop_.update())
                     .first;
            break;
        }
    }

    // Move loop locals to the new loop slice
    auto& body_slice = loop_slice->root();

    deepcopy::StructuredSDFGDeepCopy deep_copy(builder, body_slice, body);
    deep_copy.copy();
    auto& body_body_slice =
        dynamic_cast<structured_control_flow::Sequence&>(body_slice.at(0).first);

    auto& if_else_slice =
        dynamic_cast<structured_control_flow::IfElse&>(body_body_slice.at(if_else_index).first);
    auto& slice = builder.add_sequence_before(body_body_slice, if_else_slice).first;

    deepcopy::StructuredSDFGDeepCopy deep_copy_slice(builder, slice, if_else_slice.at(0).first);
    deep_copy_slice.copy();

    builder.remove_child(body_body_slice, if_else_index + 1);

    body_body_slice.replace(indvar, indvar_slice);

    // Update remaining loop
    builder.remove_case(*if_else, 0);

    auto& else_slice = builder.add_sequence_before(body, *if_else).first;
    deepcopy::StructuredSDFGDeepCopy deep_copy_else(builder, else_slice, if_else->at(0).first);
    deep_copy_else.copy();

    builder.remove_child(body, if_else_index + 1);

    // Rename all loop-local variables to break artificial dependencies
    for (auto& local : locals) {
        auto new_local = builder.find_new_name(local);
        builder.add_container(new_local, sdfg.type(local));
        loop_slice->root().replace(symbolic::symbol(local), symbolic::symbol(new_local));
    }

    // Move loop locals to the new loop
    builder.insert_children(loop_slice_2->root(), loop_.root(), 0);
    builder.remove_child(parent_, loop_);

    analysis_manager.invalidate_all();
};

}  // namespace transformations
}  // namespace sdfg

1	#include "sdfg/transformations/loop_slicing.h"
2
3	#include "sdfg/analysis/data_parallelism_analysis.h"
4	#include "sdfg/deepcopy/structured_sdfg_deep_copy.h"
5	#include "sdfg/structured_control_flow/structured_loop.h"
6
7	namespace sdfg {
8	namespace transformations {
9
10	enum class LoopSlicingType { Init, Bound, Split_Lt, Split_Le };
11
12	LoopSlicing::LoopSlicing(structured_control_flow::Sequence& parent,	1✔
13	structured_control_flow::StructuredLoop& loop)
14	: parent_(parent), loop_(loop) {	1✔
15
16	};	1✔
17
18	std::string LoopSlicing::name() { return "LoopSlicing"; };	×
19
20	bool LoopSlicing::can_be_applied(builder::StructuredSDFGBuilder& builder,	1✔
21	analysis::AnalysisManager& analysis_manager) {
22	auto& sdfg = builder.subject();	1✔
23
24	if (!analysis::DataParallelismAnalysis::is_contiguous(loop_)) {	1✔
25	return false;	×
26	}
27
28	// Collect moving symbols
29	std::unordered_set<std::string> moving_symbols;	1✔
30	auto& all_users = analysis_manager.get<analysis::Users>();	1✔
31	auto& body = loop_.root();	1✔
32	analysis::UsersView users(all_users, body);	1✔
33	for (auto& entry : users.writes()) {	1✔
34	auto& type = sdfg.type(entry->container());	×
35	if (!dynamic_cast<const types::Scalar*>(&type)) {	×
36	continue;	×
37	}
38	if (!types::is_integer(type.primitive_type())) {	×
39	continue;	×
40	}
41	moving_symbols.insert(entry->container());	×
42	}
43
44	// Check if loop is sliced by if-elses
45	auto indvar = loop_.indvar();	1✔
46	for (size_t i = 0; i < body.size(); i++) {	1✔
47	auto child = body.at(i);	1✔
48	if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {	1✔
49	if (child.second.assignments().size() > 0) {	1✔
50	return false;	×
51	}
52	if (if_else->size() != 2) {	1✔
53	return false;	×
54	}
55
56	// Validate condition
57	auto branch_1 = if_else->at(0);	1✔
58	auto condition_1 = branch_1.second;	1✔
59	if (!symbolic::uses(condition_1, indvar)) {	1✔
60	return false;	×
61	}
62	auto condition_2 = if_else->at(1).second;	1✔
63	if (!symbolic::eq(condition_1, condition_2->logical_not())) {	1✔
64	return false;	×
65	}
66	for (auto& atom : symbolic::atoms(condition_1)) {	2✔
67	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	1✔
68	if (moving_symbols.find(sym->get_name()) != moving_symbols.end()) {	1✔
69	return false;	×
70	}
71	}	1✔
72	auto bound = analysis::DataParallelismAnalysis::bound(loop_);	1✔
73	if (bound == SymEngine::null) {	1✔
74	return false;	×
75	}
76
77	// Case: indvar == init
78	if (symbolic::eq(condition_1, symbolic::Eq(indvar, loop_.init()))) {	1✔
79	return true;	1✔
80	}
81
82	// Case: indvar == bound - 1
83	if (symbolic::eq(condition_1,	×
84	symbolic::Eq(indvar, symbolic::sub(bound, symbolic::one())))) {	×
85	return true;	×
86	}
87
88	// Case: indvar < new_bound
89	if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition_1)) {	×
90	return true;	×
91	}
92
93	// Case: indvar <= new_bound
94	if (SymEngine::is_a<SymEngine::LessThan>(*condition_1)) {	×
95	return true;	×
96	}
97
98	return false;	×
99	}	1✔
100	}	×
101
102	return false;	×
103	};	1✔
104
105	void LoopSlicing::apply(builder::StructuredSDFGBuilder& builder,	1✔
106	analysis::AnalysisManager& analysis_manager) {
107	auto& sdfg = builder.subject();	1✔
108
109	auto& body = loop_.root();	1✔
110	auto indvar = loop_.indvar();	1✔
111
112	// Collect loop locals
113	auto& users = analysis_manager.get<analysis::Users>();	1✔
114	auto locals = users.locals(sdfg, body);	1✔
115
116	// Find the if-else that slices the loop
117	structured_control_flow::IfElse* if_else = nullptr;	1✔
118	size_t if_else_index = 0;	1✔
119	for (size_t i = 0; i < body.size(); i++) {	1✔
120	auto child = body.at(i);	1✔
121	auto if_else_ = dynamic_cast<structured_control_flow::IfElse*>(&child.first);	1✔
122	if (if_else_) {	1✔
123	if_else_index = i;	1✔
124	if_else = if_else_;	1✔
125	break;	1✔
126	}
127	}	×
128	if (if_else == nullptr) {	1✔
129	throw InvalidSDFGException("LoopSlicing: Expected IfElse");	×
130	}
131
132	auto branch_1 = if_else->at(0);	1✔
133	auto condition_1 = branch_1.second;	1✔
134	auto bound = analysis::DataParallelismAnalysis::bound(loop_);	1✔
135
136	LoopSlicingType slice_type = LoopSlicingType::Init;	1✔
137	if (symbolic::eq(condition_1, symbolic::Eq(indvar, loop_.init()))) {	1✔
138	slice_type = LoopSlicingType::Init;	1✔
139	} else if (symbolic::eq(condition_1,	1✔
140	symbolic::Eq(indvar, symbolic::sub(bound, symbolic::one())))) {	×
141	slice_type = LoopSlicingType::Bound;	×
142	} else if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition_1)) {	×
143	slice_type = LoopSlicingType::Split_Lt;	×
144	} else if (SymEngine::is_a<SymEngine::LessThan>(*condition_1)) {	×
145	slice_type = LoopSlicingType::Split_Le;	×
146	}	×
147
148	// Slice loop
149	auto indvar_slice_str = builder.find_new_name(indvar->get_name());	1✔
150	builder.add_container(indvar_slice_str, sdfg.type(indvar->get_name()));	1✔
151	auto indvar_slice = SymEngine::symbol(indvar_slice_str);	1✔
152	structured_control_flow::For* loop_slice = nullptr;	1✔
153	structured_control_flow::For* loop_slice_2 = nullptr;	1✔
154	switch (slice_type) {	1✔
155	case LoopSlicingType::Init: {
156	auto init_slice = loop_.init();	1✔
157	auto condition_slice =
158	symbolic::Lt(indvar_slice, symbolic::add(loop_.init(), symbolic::one()));	1✔
159	auto increment_slice = symbolic::add(indvar_slice, symbolic::one());	1✔
160	loop_slice = &builder	2✔
161	.add_for_before(parent_, loop_, indvar_slice, condition_slice,	1✔
162	init_slice, increment_slice)
163	.first;	1✔
164	loop_slice_2 =	1✔
165	&builder	1✔
166	.add_for_after(parent_, loop_, loop_.indvar(), loop_.condition(),	2✔
167	symbolic::add(loop_.init(), symbolic::one()), loop_.update())	1✔
168	.first;	1✔
169	break;
170	}	1✔
171	case LoopSlicingType::Bound: {
172	auto init_slice = symbolic::sub(bound, symbolic::one());	×
173	auto condition_slice = symbolic::subs(loop_.condition(), loop_.indvar(), indvar_slice);	×
174	auto increment_slice = symbolic::add(indvar_slice, symbolic::one());	×
175	loop_slice = &builder	×
176	.add_for_after(parent_, loop_, indvar_slice, condition_slice,	×
177	init_slice, increment_slice)
178	.first;	×
NEW 179	loop_slice_2 = &builder	×
NEW 180	.add_for_before(	×
NEW 181	parent_, loop_, loop_.indvar(),	×
NEW 182	symbolic::Lt(loop_.indvar(),	×
NEW 183	symbolic::sub(loop_.condition(), symbolic::one())),	×
NEW 184	loop_.init(), loop_.update())	×
NEW 185	.first;	×
186	break;
187	}	×
188	case LoopSlicingType::Split_Lt: {
189	auto init_slice = loop_.init();	×
190	auto condition_slice =
191	symbolic::And(symbolic::subs(condition_1, indvar, indvar_slice),	×
192	symbolic::subs(loop_.condition(), indvar, indvar_slice));	×
193	auto increment_slice = symbolic::add(indvar_slice, symbolic::one());	×
194	loop_slice = &builder	×
195	.add_for_before(parent_, loop_, indvar_slice, condition_slice,	×
196	init_slice, increment_slice)
197	.first;	×
198
199	auto condition_bound =
200	SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(condition_1);	×
201	auto condition_bound_args = condition_bound->get_args();	×
202	auto condition_bound_args_bound = condition_bound_args.at(0);	×
203	if (symbolic::eq(condition_bound_args_bound, loop_.indvar())) {	×
204	condition_bound_args_bound = condition_bound_args.at(1);	×
205	}	×
206
NEW 207	loop_slice_2 = &builder	×
NEW 208	.add_for_after(parent_, loop_, loop_.indvar(), loop_.condition(),	×
NEW 209	condition_bound_args_bound, loop_.update())	×
NEW 210	.first;	×
211	break;
212	}	×
213	case LoopSlicingType::Split_Le: {
214	auto init_slice = loop_.init();	×
215	auto condition_slice =
216	symbolic::And(symbolic::subs(condition_1, indvar, indvar_slice),	×
217	symbolic::subs(loop_.condition(), indvar, indvar_slice));	×
218	auto increment_slice = symbolic::add(indvar_slice, symbolic::one());	×
219	loop_slice = &builder	×
220	.add_for_before(parent_, loop_, indvar_slice, condition_slice,	×
221	init_slice, increment_slice)
222	.first;	×
223
224	auto condition_bound =
225	SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(condition_1);	×
226	auto condition_bound_args = condition_bound->get_args();	×
227	auto condition_bound_args_bound = condition_bound_args.at(0);	×
228	if (symbolic::eq(condition_bound_args_bound, loop_.indvar())) {	×
229	condition_bound_args_bound = condition_bound_args.at(1);	×
230	}	×
231
NEW 232	loop_slice_2 =	×
NEW 233	&builder	×
NEW 234	.add_for_after(parent_, loop_, loop_.indvar(), loop_.condition(),	×
NEW 235	symbolic::add(condition_bound_args_bound, symbolic::one()),	×
NEW 236	loop_.update())	×
NEW 237	.first;	×
238	break;
239	}	×
240	}
241
242	// Move loop locals to the new loop slice
243	auto& body_slice = loop_slice->root();	1✔
244
245	deepcopy::StructuredSDFGDeepCopy deep_copy(builder, body_slice, body);	1✔
246	deep_copy.copy();	1✔
247	auto& body_body_slice =	1✔
248	dynamic_cast<structured_control_flow::Sequence&>(body_slice.at(0).first);	1✔
249
250	auto& if_else_slice =	1✔
251	dynamic_cast<structured_control_flow::IfElse&>(body_body_slice.at(if_else_index).first);	1✔
252	auto& slice = builder.add_sequence_before(body_body_slice, if_else_slice).first;	1✔
253
254	deepcopy::StructuredSDFGDeepCopy deep_copy_slice(builder, slice, if_else_slice.at(0).first);	1✔
255	deep_copy_slice.copy();	1✔
256
257	builder.remove_child(body_body_slice, if_else_index + 1);	1✔
258
259	body_body_slice.replace(indvar, indvar_slice);	1✔
260
261	// Update remaining loop
262	builder.remove_case(*if_else, 0);	1✔
263
264	auto& else_slice = builder.add_sequence_before(body, *if_else).first;	1✔
265	deepcopy::StructuredSDFGDeepCopy deep_copy_else(builder, else_slice, if_else->at(0).first);	1✔
266	deep_copy_else.copy();	1✔
267
268	builder.remove_child(body, if_else_index + 1);	1✔
269
270	// Rename all loop-local variables to break artificial dependencies
271	for (auto& local : locals) {	1✔
272	auto new_local = builder.find_new_name(local);	×
273	builder.add_container(new_local, sdfg.type(local));	×
274	loop_slice->root().replace(symbolic::symbol(local), symbolic::symbol(new_local));	×
275	}	×
276
277	// Move loop locals to the new loop
278	builder.insert_children(loop_slice_2->root(), loop_.root(), 0);	1✔
279	builder.remove_child(parent_, loop_);	1✔
280
281	analysis_manager.invalidate_all();	1✔
282	};	1✔
283
284	} // namespace transformations
285	} // 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