15238257521

Committed 25 May 2025 01:14PM UTC coverage: 60.342% (-0.1%) from 60.473%

Build # 15238257521

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #31 from daisytuner/exception-handling

Exception handling

Run Details

18 of 60 new or added lines in 17 files covered. (30.0%)

1 existing line in 1 file now uncovered.

8052 of 13344 relevant lines covered (60.34%)

102.27 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

53.66

/src/transformations/loop_slicing.cpp

#include "sdfg/transformations/loop_slicing.h"

#include "sdfg/deepcopy/structured_sdfg_deep_copy.h"

namespace sdfg {
namespace transformations {

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

LoopSlicing::LoopSlicing(structured_control_flow::Sequence& parent,
                         structured_control_flow::For& 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;
    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_.init() = symbolic::add(loop_.init(), symbolic::one());
            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_.condition() =
                symbolic::Lt(loop_.indvar(), symbolic::sub(loop_.condition(), symbolic::one()));
            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_.init() = condition_bound_args_bound;
            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_.init() = symbolic::add(condition_bound_args_bound, symbolic::one());
            break;
        }
    }

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

    analysis_manager.invalidate_all();
};

}  // namespace transformations
}  // namespace sdfg

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

daisytuner / sdfglib / 15238257521

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