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

54.27

/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;
        }
    }
    assert(if_else != nullptr);

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