26448855920

Committed 26 May 2026 12:46PM UTC coverage: 60.884% (+0.04%) from 60.848%

Build # 26448855920

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #721 from daisytuner/second-level-tiling

Make second level tiling possible

Coverage Stats

74 of 92 new or added lines in 2 files covered. (80.43%)

2 existing lines in 1 file now uncovered.

35101 of 57652 relevant lines covered (60.88%)

11087.7 hits per line

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

81.11

/opt/src/transformations/multi_level_tiling.cpp

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

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

daisytuner / docc / 26448855920

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