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

71.57

/opt/src/transformations/multi_level_tiling.cpp

#include "sdfg/transformations/multi_level_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 {

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

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

bool MultiLevelTiling::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    if (!LoopTiling::can_be_applied(builder, analysis_manager)) {
        return false;
    }
    if (this->tile_size_2_ <= 1) {
        return false;
    }
    if (this->tile_size_2_ >= this->tile_size_) {
        return false;
    }
    if (this->tile_size_ % this->tile_size_2_ != 0) {
        return false;
    }
    return true;
};

void MultiLevelTiling::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    // First apply single-level tiling
    LoopTiling::apply(builder, analysis_manager);

    auto& sdfg = builder.subject();

    // Now tile the inner (point) loop again with tile_size_2_
    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 parent2 = static_cast<structured_control_flow::Sequence*>(inner.get_parent());
    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 if (auto reduce = dynamic_cast<structured_control_flow::Reduce*>(&inner)) {
        middle_loop = &builder.add_reduce_before(
            *parent2,
            inner,
            middle_indvar,
            middle_condition,
            inner.init(),
            middle_update,
            reduce->reductions(),
            reduce->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 MultiLevelTiling::to_json(nlohmann::json& j) const {
    LoopTiling::to_json(j);
    j["transformation_type"] = this->name();
    j["parameters"]["tile_size_2"] = tile_size_2_;
};

MultiLevelTiling MultiLevelTiling::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>();
    size_t tile_size_2 = desc["parameters"]["tile_size_2"].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 MultiLevelTiling(*loop, tile_size, tile_size_2);
};

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

} // namespace transformations
} // namespace sdfg

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