28177795453

Committed 25 Jun 2026 02:33PM UTC coverage: 61.743% (+0.1%) from 61.644%

Build # 28177795453

Build Type

Pull #802

github

Committed by

web-flow

Commit Message

Merge 08f22df91 into fe9abd1cb

Pull Request Pull Request #802: adds reduce as new structured loop type

Coverage Stats

705 of 985 new or added lines in 34 files covered. (71.57%)

5 existing lines in 4 files now uncovered.

38837 of 62901 relevant lines covered (61.74%)

978.19 hits per line

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

88.24

/opt/src/transformations/loop_tiling.cpp

#include "sdfg/transformations/loop_tiling.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) {};

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;
    }
    return loop_.is_contiguous();
};

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

    auto parent = static_cast<structured_control_flow::Sequence*>(loop_.get_parent());
    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 if (auto reduce = dynamic_cast<structured_control_flow::Reduce*>(&loop_)) {
        outer_loop = &builder.add_reduce_before(
            *parent,
            loop_,
            outer_indvar,
            outer_condition,
            loop_.init(),
            outer_update,
            reduce->reductions(),
            reduce->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;
};

void LoopTiling::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();
    j["parameters"] = nlohmann::json::object();
    j["parameters"] = {{"tile_size", tile_size_}};

    serializer::JSONSerializer ser_flat(false);
    j["subgraph"] = nlohmann::json::object();
    j["subgraph"]["0"] = nlohmann::json::object();
    ser_flat.serialize_node(j["subgraph"]["0"], loop_);
};

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

    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::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/builder/structured_sdfg_builder.h"
4	#include "sdfg/structured_control_flow/structured_loop.h"
5	#include "sdfg/symbolic/symbolic.h"
6
7	namespace sdfg {
8	namespace transformations {
9
10	LoopTiling::LoopTiling(structured_control_flow::StructuredLoop& loop, size_t tile_size)
11	: loop_(loop), tile_size_(tile_size) {};	82✔
12
13	std::string LoopTiling::name() const { return "LoopTiling"; };	35✔
14
15	bool LoopTiling::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	76✔
16	if (this->tile_size_ <= 1) {	76✔
17	return false;	5✔
18	}	5✔
19	return loop_.is_contiguous();	71✔
20	};	76✔
21
22	void LoopTiling::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	50✔
23	auto& sdfg = builder.subject();	50✔
24
25	auto parent = static_cast<structured_control_flow::Sequence*>(loop_.get_parent());	50✔
26	size_t index = parent->index(loop_);	50✔
27	auto& transition = parent->at(index).second;	50✔
28
29	auto indvar = loop_.indvar();	50✔
30
31	// Step 1: Define new outer loop
32	auto outer_indvar_str = builder.find_new_name(indvar->get_name() + "_tile");	50✔
33	builder.add_container(outer_indvar_str, sdfg.type(loop_.indvar()->get_name()));	50✔
34	auto outer_indvar = symbolic::symbol(outer_indvar_str);	50✔
35	auto outer_condition = symbolic::subs(loop_.condition(), indvar, outer_indvar);	50✔
36	auto outer_update = symbolic::add(outer_indvar, symbolic::integer(this->tile_size_));	50✔
37
38	structured_control_flow::StructuredLoop* outer_loop = nullptr;	50✔
39	if (auto map = dynamic_cast<structured_control_flow::Map*>(&loop_)) {	50✔
40	outer_loop = &builder.add_map_before(	27✔
41	*parent,	27✔
42	loop_,	27✔
43	outer_indvar,	27✔
44	outer_condition,	27✔
45	loop_.init(),	27✔
46	outer_update,	27✔
47	map->schedule_type(),	27✔
48	transition.assignments(),	27✔
49	loop_.debug_info()	27✔
50	);	27✔
51	} else if (auto reduce = dynamic_cast<structured_control_flow::Reduce*>(&loop_)) {	27✔
NEW 52	outer_loop = &builder.add_reduce_before(	×
NEW 53	*parent,	×
NEW 54	loop_,	×
NEW 55	outer_indvar,	×
NEW 56	outer_condition,	×
NEW 57	loop_.init(),	×
NEW 58	outer_update,	×
NEW 59	reduce->reductions(),	×
NEW 60	reduce->schedule_type(),	×
NEW 61	transition.assignments(),	×
NEW 62	loop_.debug_info()	×
NEW 63	);	×
64	} else {	23✔
65	outer_loop = &builder.add_for_before(	23✔
66	*parent,	23✔
67	loop_,	23✔
68	outer_indvar,	23✔
69	outer_condition,	23✔
70	loop_.init(),	23✔
71	outer_update,	23✔
72	transition.assignments(),	23✔
73	loop_.debug_info()	23✔
74	);	23✔
75	}	23✔
76
77	// Step 2: Redefine inner loop
78	auto inner_indvar = indvar;	50✔
79	auto inner_init = outer_indvar;	50✔
80	auto inner_condition_tile =	50✔
81	symbolic::Lt(inner_indvar, symbolic::add(outer_indvar, symbolic::integer(this->tile_size_)));	50✔
82
83	symbolic::Condition inner_condition = symbolic::And(inner_condition_tile, loop_.condition());	50✔
84
85	auto inner_update = symbolic::add(inner_indvar, symbolic::integer(1));	50✔
86	builder.update_loop(loop_, inner_indvar, inner_condition, inner_init, inner_update);	50✔
87
88	// Step 3: Move loop into tiling loop
89	transition.assignments().clear();	50✔
90	builder.move_child(*parent, index + 1, outer_loop->root());	50✔
91
92	analysis_manager.invalidate_all();	50✔
93	applied_ = true;	50✔
94	inner_loop_ = &loop_;	50✔
95	outer_loop_ = outer_loop;	50✔
96	};	50✔
97
98	void LoopTiling::to_json(nlohmann::json& j) const {	30✔
99	j["transformation_type"] = this->name();	30✔
100	j["parameters"] = nlohmann::json::object();	30✔
101	j["parameters"] = {{"tile_size", tile_size_}};	30✔
102
103	serializer::JSONSerializer ser_flat(false);	30✔
104	j["subgraph"] = nlohmann::json::object();	30✔
105	j["subgraph"]["0"] = nlohmann::json::object();	30✔
106	ser_flat.serialize_node(j["subgraph"]["0"], loop_);	30✔
107	};	30✔
108
109	LoopTiling LoopTiling::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	10✔
110	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	10✔
111	size_t tile_size = desc["parameters"]["tile_size"].get<size_t>();	10✔
112	auto element = builder.find_element_by_id(loop_id);	10✔
113	if (!element) {	10✔
114	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	1✔
115	}	1✔
116	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	9✔
117
118	return LoopTiling(*loop, tile_size);	9✔
119	};	10✔
120
121	structured_control_flow::StructuredLoop* LoopTiling::inner_loop() {	14✔
122	if (!applied_) {	14✔
123	throw InvalidSDFGException("Accessing tiled loop before their creation.");	4✔
124	}	4✔
125
126	return inner_loop_;	10✔
127	}	14✔
128
129	structured_control_flow::StructuredLoop* LoopTiling::outer_loop() {	14✔
130	if (!applied_) {	14✔
131	throw InvalidSDFGException("Accessing tiled loop before their creation.");	4✔
132	}	4✔
133
134	return outer_loop_;	10✔
135	}	14✔
136
137	} // namespace transformations
138	} // namespace sdfg

daisytuner / docc / 28177795453

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