20778790944

Committed 07 Jan 2026 10:43AM UTC coverage: 61.994% (-0.2%) from 62.168%

Build # 20778790944

Build Type

Pull #438

github

Committed by

web-flow

Commit Message

Merge e00e1c976 into 0c34ccd02

Pull Request Pull Request #438: Cuda tiling

Run Details

9 of 51 new or added lines in 6 files covered. (17.65%)

4 existing lines in 2 files now uncovered.

14904 of 24041 relevant lines covered (61.99%)

88.13 hits per line

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

83.16

/src/transformations/loop_tiling.cpp

#include "sdfg/transformations/loop_tiling.h"
#include <stdexcept>

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/loop_analysis.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) {};

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;
    }
    // Criterion contiguous loop
    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    return analysis::LoopAnalysis::is_contiguous(&loop_, assumptions_analysis);
};

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

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 std::runtime_error("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_}};
};

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 std::runtime_error("Accessing tiled loop before their creation.");
    }

    return inner_loop_;
}

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

    return outer_loop_;
}

} // namespace transformations
} // namespace sdfg

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

daisytuner / sdfglib / 20778790944

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