28101952530

Committed 24 Jun 2026 01:27PM UTC coverage: 61.988% (+0.1%) from 61.844%

Build # 28101952530

Build Type

Pull #802

github

Committed by

web-flow

Commit Message

Merge 54d7d8794 into 57cc1db99

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

Coverage Stats

604 of 780 new or added lines in 24 files covered. (77.44%)

96 existing lines in 11 files now uncovered.

38005 of 61310 relevant lines covered (61.99%)

1006.39 hits per line

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

80.9

/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 {
        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 {	1✔
66	middle_loop = &builder.add_for_before(	1✔
67	*parent2,	1✔
68	inner,	1✔
69	middle_indvar,	1✔
70	middle_condition,	1✔
71	inner.init(),	1✔
72	middle_update,	1✔
73	transition2.assignments(),	1✔
74	inner.debug_info()	1✔
75	);	1✔
76	}	1✔
77
78	// Redefine the innermost loop
79	auto innermost_init = middle_indvar;	1✔
80	auto innermost_condition_tile =	1✔
81	symbolic::Lt(inner_indvar2, symbolic::add(middle_indvar, symbolic::integer(this->tile_size_2_)));	1✔
82	symbolic::Condition innermost_condition = symbolic::And(innermost_condition_tile, inner.condition());	1✔
83	auto innermost_update = symbolic::add(inner_indvar2, symbolic::integer(1));	1✔
84	builder.update_loop(inner, inner_indvar2, innermost_condition, innermost_init, innermost_update);	1✔
85
86	// Move inner loop into middle loop
87	transition2.assignments().clear();	1✔
88	builder.move_child(*parent2, index2 + 1, middle_loop->root());	1✔
89
90	analysis_manager.invalidate_all();	1✔
91	middle_loop_ = middle_loop;	1✔
92	inner_loop_ = &inner;	1✔
93	};	1✔
94
95	void MultiLevelTiling::to_json(nlohmann::json& j) const {	1✔
96	LoopTiling::to_json(j);	1✔
97	j["transformation_type"] = this->name();	1✔
98	j["parameters"]["tile_size_2"] = tile_size_2_;	1✔
99	};	1✔
100
101	MultiLevelTiling MultiLevelTiling::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	1✔
102	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	1✔
103	size_t tile_size = desc["parameters"]["tile_size"].get<size_t>();	1✔
104	size_t tile_size_2 = desc["parameters"]["tile_size_2"].get<size_t>();	1✔
105	auto element = builder.find_element_by_id(loop_id);	1✔
106	if (!element) {	1✔
UNCOV 107	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
UNCOV 108	}	×
109	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	1✔
110
111	return MultiLevelTiling(*loop, tile_size, tile_size_2);	1✔
112	};	1✔
113
114	structured_control_flow::StructuredLoop* MultiLevelTiling::middle_loop() {	1✔
115	if (!applied_) {	1✔
UNCOV 116	throw InvalidSDFGException("Accessing tiled loop before their creation.");	×
UNCOV 117	}	×
118	return middle_loop_;	1✔
119	}	1✔
120
121	} // namespace transformations
122	} // namespace sdfg

daisytuner / docc / 28101952530

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