26293980171

Committed 22 May 2026 02:34PM UTC coverage: 60.866% (+0.03%) from 60.837%

Build # 26293980171

Build Type

Pull #721

github

Committed by

web-flow

Commit Message

Merge ffd3b10b5 into 03826c653

Pull Request Pull Request #721: Make second level tiling possible

Coverage Stats

62 of 75 new or added lines in 1 file covered. (82.67%)

22 existing lines in 2 files now uncovered.

35058 of 57599 relevant lines covered (60.87%)

11093.61 hits per line

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

87.57

/opt/src/transformations/loop_tiling.cpp

#include "sdfg/transformations/loop_tiling.h"

#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/symbolic/symbolic.h"

namespace sdfg {
namespace transformations {

LoopTiling::LoopTiling(structured_control_flow::StructuredLoop& loop, size_t tile_size)
    : loop_(loop), tile_size_(tile_size) {};

LoopTiling::LoopTiling(structured_control_flow::StructuredLoop& loop, size_t tile_size, size_t tile_size_2)
    : loop_(loop), tile_size_(tile_size), tile_size_2_(tile_size_2) {};

std::string LoopTiling::name() const { return "LoopTiling"; };

bool LoopTiling::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    if (this->tile_size_ <= 1) {
        return false;
    }
    if (this->tile_size_2_ == 1) {
        return false;
    }
    if (this->tile_size_2_ > 0 && this->tile_size_2_ >= this->tile_size_) {
        return false;
    }
    if (this->tile_size_2_ > 0 && this->tile_size_ % this->tile_size_2_ != 0) {
        return false;
    }
    // Criterion contiguous loop
    return loop_.is_contiguous();
};

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

    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&loop_));
    size_t index = parent->index(loop_);
    auto& transition = parent->at(index).second;

    auto indvar = loop_.indvar();

    // Step 1: Define new outer loop
    auto outer_indvar_str = builder.find_new_name(indvar->get_name() + "_tile");
    builder.add_container(outer_indvar_str, sdfg.type(loop_.indvar()->get_name()));

    auto outer_indvar = symbolic::symbol(outer_indvar_str);
    auto outer_condition = symbolic::subs(loop_.condition(), indvar, outer_indvar);
    auto outer_update = symbolic::add(outer_indvar, symbolic::integer(this->tile_size_));

    structured_control_flow::StructuredLoop* outer_loop = nullptr;
    if (auto map = dynamic_cast<structured_control_flow::Map*>(&loop_)) {
        outer_loop = &builder.add_map_before(
            *parent,
            loop_,
            outer_indvar,
            outer_condition,
            loop_.init(),
            outer_update,
            map->schedule_type(),
            transition.assignments(),
            loop_.debug_info()
        );
    } else {
        outer_loop = &builder.add_for_before(
            *parent,
            loop_,
            outer_indvar,
            outer_condition,
            loop_.init(),
            outer_update,
            transition.assignments(),
            loop_.debug_info()
        );
    }

    // Step 2: Redefine inner loop
    auto inner_indvar = indvar;
    auto inner_init = outer_indvar;
    auto inner_condition_tile =
        symbolic::Lt(inner_indvar, symbolic::add(outer_indvar, symbolic::integer(this->tile_size_)));

    symbolic::Condition inner_condition = symbolic::And(inner_condition_tile, loop_.condition());

    auto inner_update = symbolic::add(inner_indvar, symbolic::integer(1));
    builder.update_loop(loop_, inner_indvar, inner_condition, inner_init, inner_update);

    // Step 3: Move loop into tiling loop
    transition.assignments().clear();
    builder.move_child(*parent, index + 1, outer_loop->root());

    analysis_manager.invalidate_all();
    applied_ = true;
    inner_loop_ = &loop_;
    outer_loop_ = outer_loop;

    // Two-level tiling: tile the inner (point) loop again with tile_size_2_
    if (tile_size_2_ > 0) {
        auto& inner = *inner_loop_;
        auto inner_indvar2 = inner.indvar();

        auto middle_indvar_str = builder.find_new_name(inner_indvar2->get_name() + "_tile");
        builder.add_container(middle_indvar_str, sdfg.type(inner_indvar2->get_name()));

        auto middle_indvar = symbolic::symbol(middle_indvar_str);
        auto middle_condition = symbolic::subs(inner.condition(), inner_indvar2, middle_indvar);
        auto middle_update = symbolic::add(middle_indvar, symbolic::integer(this->tile_size_2_));

        auto& scope_analysis2 = analysis_manager.get<analysis::ScopeAnalysis>();
        auto parent2 = static_cast<structured_control_flow::Sequence*>(scope_analysis2.parent_scope(&inner));
        size_t index2 = parent2->index(inner);
        auto& transition2 = parent2->at(index2).second;

        structured_control_flow::StructuredLoop* middle_loop = nullptr;
        if (auto map = dynamic_cast<structured_control_flow::Map*>(&inner)) {
            middle_loop = &builder.add_map_before(
                *parent2,
                inner,
                middle_indvar,
                middle_condition,
                inner.init(),
                middle_update,
                map->schedule_type(),
                transition2.assignments(),
                inner.debug_info()
            );
        } else {
            middle_loop = &builder.add_for_before(
                *parent2,
                inner,
                middle_indvar,
                middle_condition,
                inner.init(),
                middle_update,
                transition2.assignments(),
                inner.debug_info()
            );
        }

        // Redefine the innermost loop
        auto innermost_init = middle_indvar;
        auto innermost_condition_tile =
            symbolic::Lt(inner_indvar2, symbolic::add(middle_indvar, symbolic::integer(this->tile_size_2_)));
        symbolic::Condition innermost_condition = symbolic::And(innermost_condition_tile, inner.condition());
        auto innermost_update = symbolic::add(inner_indvar2, symbolic::integer(1));
        builder.update_loop(inner, inner_indvar2, innermost_condition, innermost_init, innermost_update);

        // Move inner loop into middle loop
        transition2.assignments().clear();
        builder.move_child(*parent2, index2 + 1, middle_loop->root());

        analysis_manager.invalidate_all();
        middle_loop_ = middle_loop;
        inner_loop_ = &inner;
    }
};

void LoopTiling::to_json(nlohmann::json& j) const {
    std::string loop_type;
    if (dynamic_cast<structured_control_flow::For*>(&loop_)) {
        loop_type = "for";
    } else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {
        loop_type = "map";
    } else {
        throw InvalidSDFGException("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());
    }

    j["transformation_type"] = this->name();
    j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};
    j["parameters"] = {{"tile_size", tile_size_}};
    if (tile_size_2_ > 0) {
        j["parameters"]["tile_size_2"] = tile_size_2_;
    }
};

LoopTiling LoopTiling::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    size_t tile_size = desc["parameters"]["tile_size"].get<size_t>();
    auto element = builder.find_element_by_id(loop_id);
    if (!element) {
        throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");
    }
    auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);

    size_t tile_size_2 = 0;
    if (desc["parameters"].contains("tile_size_2")) {
        tile_size_2 = desc["parameters"]["tile_size_2"].get<size_t>();
    }

    if (tile_size_2 > 0) {
        return LoopTiling(*loop, tile_size, tile_size_2);
    }
    return LoopTiling(*loop, tile_size);
};

structured_control_flow::StructuredLoop* LoopTiling::inner_loop() {
    if (!applied_) {
        throw InvalidSDFGException("Accessing tiled loop before their creation.");
    }

    return inner_loop_;
}

structured_control_flow::StructuredLoop* LoopTiling::middle_loop() {
    if (!applied_) {
        throw InvalidSDFGException("Accessing tiled loop before their creation.");
    }
    return middle_loop_;
}

structured_control_flow::StructuredLoop* LoopTiling::outer_loop() {
    if (!applied_) {
        throw InvalidSDFGException("Accessing tiled loop before their creation.");
    }

    return outer_loop_;
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/loop_tiling.h"
2
3	#include "sdfg/analysis/scope_analysis.h"
4	#include "sdfg/builder/structured_sdfg_builder.h"
5	#include "sdfg/structured_control_flow/structured_loop.h"
6	#include "sdfg/symbolic/symbolic.h"
7
8	namespace sdfg {
9	namespace transformations {
10
11	LoopTiling::LoopTiling(structured_control_flow::StructuredLoop& loop, size_t tile_size)
12	: loop_(loop), tile_size_(tile_size) {};	66✔
13
14	LoopTiling::LoopTiling(structured_control_flow::StructuredLoop& loop, size_t tile_size, size_t tile_size_2)
15	: loop_(loop), tile_size_(tile_size), tile_size_2_(tile_size_2) {};	10✔
16
17	std::string LoopTiling::name() const { return "LoopTiling"; };	37✔
18
19	bool LoopTiling::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	70✔
20	if (this->tile_size_ <= 1) {	70✔
21	return false;	4✔
22	}	4✔
23	if (this->tile_size_2_ == 1) {	66✔
24	return false;	1✔
25	}	1✔
26	if (this->tile_size_2_ > 0 && this->tile_size_2_ >= this->tile_size_) {	65✔
27	return false;	2✔
28	}	2✔
29	if (this->tile_size_2_ > 0 && this->tile_size_ % this->tile_size_2_ != 0) {	63✔
30	return false;	2✔
31	}	2✔
32	// Criterion contiguous loop
33	return loop_.is_contiguous();	61✔
34	};	63✔
35
36	void LoopTiling::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	46✔
37	auto& sdfg = builder.subject();	46✔
38
39	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	46✔
40	auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&loop_));	46✔
41	size_t index = parent->index(loop_);	46✔
42	auto& transition = parent->at(index).second;	46✔
43
44	auto indvar = loop_.indvar();	46✔
45
46	// Step 1: Define new outer loop
47	auto outer_indvar_str = builder.find_new_name(indvar->get_name() + "_tile");	46✔
48	builder.add_container(outer_indvar_str, sdfg.type(loop_.indvar()->get_name()));	46✔
49
50	auto outer_indvar = symbolic::symbol(outer_indvar_str);	46✔
51	auto outer_condition = symbolic::subs(loop_.condition(), indvar, outer_indvar);	46✔
52	auto outer_update = symbolic::add(outer_indvar, symbolic::integer(this->tile_size_));	46✔
53
54	structured_control_flow::StructuredLoop* outer_loop = nullptr;	46✔
55	if (auto map = dynamic_cast<structured_control_flow::Map*>(&loop_)) {	46✔
56	outer_loop = &builder.add_map_before(	24✔
57	*parent,	24✔
58	loop_,	24✔
59	outer_indvar,	24✔
60	outer_condition,	24✔
61	loop_.init(),	24✔
62	outer_update,	24✔
63	map->schedule_type(),	24✔
64	transition.assignments(),	24✔
65	loop_.debug_info()	24✔
66	);	24✔
67	} else {	24✔
68	outer_loop = &builder.add_for_before(	22✔
69	*parent,	22✔
70	loop_,	22✔
71	outer_indvar,	22✔
72	outer_condition,	22✔
73	loop_.init(),	22✔
74	outer_update,	22✔
75	transition.assignments(),	22✔
76	loop_.debug_info()	22✔
77	);	22✔
78	}	22✔
79
80	// Step 2: Redefine inner loop
81	auto inner_indvar = indvar;	46✔
82	auto inner_init = outer_indvar;	46✔
83	auto inner_condition_tile =	46✔
84	symbolic::Lt(inner_indvar, symbolic::add(outer_indvar, symbolic::integer(this->tile_size_)));	46✔
85
86	symbolic::Condition inner_condition = symbolic::And(inner_condition_tile, loop_.condition());	46✔
87
88	auto inner_update = symbolic::add(inner_indvar, symbolic::integer(1));	46✔
89	builder.update_loop(loop_, inner_indvar, inner_condition, inner_init, inner_update);	46✔
90
91	// Step 3: Move loop into tiling loop
92	transition.assignments().clear();	46✔
93	builder.move_child(*parent, index + 1, outer_loop->root());	46✔
94
95	analysis_manager.invalidate_all();	46✔
96	applied_ = true;	46✔
97	inner_loop_ = &loop_;	46✔
98	outer_loop_ = outer_loop;	46✔
99
100	// Two-level tiling: tile the inner (point) loop again with tile_size_2_
101	if (tile_size_2_ > 0) {	46✔
102	auto& inner = *inner_loop_;	1✔
103	auto inner_indvar2 = inner.indvar();	1✔
104
105	auto middle_indvar_str = builder.find_new_name(inner_indvar2->get_name() + "_tile");	1✔
106	builder.add_container(middle_indvar_str, sdfg.type(inner_indvar2->get_name()));	1✔
107
108	auto middle_indvar = symbolic::symbol(middle_indvar_str);	1✔
109	auto middle_condition = symbolic::subs(inner.condition(), inner_indvar2, middle_indvar);	1✔
110	auto middle_update = symbolic::add(middle_indvar, symbolic::integer(this->tile_size_2_));	1✔
111
112	auto& scope_analysis2 = analysis_manager.get<analysis::ScopeAnalysis>();	1✔
113	auto parent2 = static_cast<structured_control_flow::Sequence*>(scope_analysis2.parent_scope(&inner));	1✔
114	size_t index2 = parent2->index(inner);	1✔
115	auto& transition2 = parent2->at(index2).second;	1✔
116
117	structured_control_flow::StructuredLoop* middle_loop = nullptr;	1✔
118	if (auto map = dynamic_cast<structured_control_flow::Map*>(&inner)) {	1✔
NEW 119	middle_loop = &builder.add_map_before(	×
NEW UNCOV 120	*parent2,	×
NEW UNCOV 121	inner,	×
NEW UNCOV 122	middle_indvar,	×
NEW UNCOV 123	middle_condition,	×
NEW UNCOV 124	inner.init(),	×
NEW UNCOV 125	middle_update,	×
NEW 126	map->schedule_type(),	×
NEW 127	transition2.assignments(),	×
NEW UNCOV 128	inner.debug_info()	×
NEW UNCOV 129	);	×
130	} else {	1✔
131	middle_loop = &builder.add_for_before(	1✔
132	*parent2,	1✔
133	inner,	1✔
134	middle_indvar,	1✔
135	middle_condition,	1✔
136	inner.init(),	1✔
137	middle_update,	1✔
138	transition2.assignments(),	1✔
139	inner.debug_info()	1✔
140	);	1✔
141	}	1✔
142
143	// Redefine the innermost loop
144	auto innermost_init = middle_indvar;	1✔
145	auto innermost_condition_tile =	1✔
146	symbolic::Lt(inner_indvar2, symbolic::add(middle_indvar, symbolic::integer(this->tile_size_2_)));	1✔
147	symbolic::Condition innermost_condition = symbolic::And(innermost_condition_tile, inner.condition());	1✔
148	auto innermost_update = symbolic::add(inner_indvar2, symbolic::integer(1));	1✔
149	builder.update_loop(inner, inner_indvar2, innermost_condition, innermost_init, innermost_update);	1✔
150
151	// Move inner loop into middle loop
152	transition2.assignments().clear();	1✔
153	builder.move_child(*parent2, index2 + 1, middle_loop->root());	1✔
154
155	analysis_manager.invalidate_all();	1✔
156	middle_loop_ = middle_loop;	1✔
157	inner_loop_ = &inner;	1✔
158	}	1✔
159	};	46✔
160
161	void LoopTiling::to_json(nlohmann::json& j) const {	30✔
162	std::string loop_type;	30✔
163	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	30✔
164	loop_type = "for";	17✔
165	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	17✔
166	loop_type = "map";	13✔
167	} else {	13✔
UNCOV 168	throw InvalidSDFGException("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());	×
UNCOV 169	}	×
170
171	j["transformation_type"] = this->name();	30✔
172	j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};	30✔
173	j["parameters"] = {{"tile_size", tile_size_}};	30✔
174	if (tile_size_2_ > 0) {	30✔
175	j["parameters"]["tile_size_2"] = tile_size_2_;	1✔
176	}	1✔
177	};	30✔
178
179	LoopTiling LoopTiling::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	10✔
180	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	10✔
181	size_t tile_size = desc["parameters"]["tile_size"].get<size_t>();	10✔
182	auto element = builder.find_element_by_id(loop_id);	10✔
183	if (!element) {	10✔
UNCOV 184	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
UNCOV 185	}	×
186	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	10✔
187
188	size_t tile_size_2 = 0;	10✔
189	if (desc["parameters"].contains("tile_size_2")) {	10✔
190	tile_size_2 = desc["parameters"]["tile_size_2"].get<size_t>();	1✔
191	}	1✔
192
193	if (tile_size_2 > 0) {	10✔
194	return LoopTiling(*loop, tile_size, tile_size_2);	1✔
195	}	1✔
196	return LoopTiling(*loop, tile_size);	9✔
197	};	10✔
198
199	structured_control_flow::StructuredLoop* LoopTiling::inner_loop() {	6✔
200	if (!applied_) {	6✔
UNCOV 201	throw InvalidSDFGException("Accessing tiled loop before their creation.");	×
UNCOV 202	}	×
203
204	return inner_loop_;	6✔
205	}	6✔
206
207	structured_control_flow::StructuredLoop* LoopTiling::middle_loop() {	1✔
208	if (!applied_) {	1✔
NEW UNCOV 209	throw InvalidSDFGException("Accessing tiled loop before their creation.");	×
NEW UNCOV 210	}	×
211	return middle_loop_;	1✔
212	}	1✔
213
214	structured_control_flow::StructuredLoop* LoopTiling::outer_loop() {	6✔
215	if (!applied_) {	6✔
UNCOV 216	throw InvalidSDFGException("Accessing tiled loop before their creation.");	×
UNCOV 217	}	×
218
219	return outer_loop_;	6✔
220	}	6✔
221
222	} // namespace transformations
223	} // namespace sdfg

daisytuner / docc / 26293980171

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