20792180504

Committed 07 Jan 2026 06:28PM UTC coverage: 62.339% (+0.2%) from 62.168%

Build # 20792180504

Build Type

Pull #436

github

Committed by

web-flow

Commit Message

Merge 6e411abb2 into acd6225ac

Pull Request Pull Request #436: Add comprehensive tests and Doxygen documentation for SDFG transformations

Run Details

14987 of 24041 relevant lines covered (62.34%)

88.99 hits per line

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

65.03

/src/transformations/loop_interchange.cpp

#include "sdfg/transformations/loop_interchange.h"

#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/exceptions.h"
#include "sdfg/structured_control_flow/for.h"
#include "sdfg/structured_control_flow/structured_loop.h"

namespace sdfg {
namespace transformations {

LoopInterchange::LoopInterchange(
    structured_control_flow::StructuredLoop& outer_loop, structured_control_flow::StructuredLoop& inner_loop
)
    : outer_loop_(outer_loop), inner_loop_(inner_loop) {

      };

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

bool LoopInterchange::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& outer_indvar = this->outer_loop_.indvar();

    // Criterion: Inner loop must not depend on outer loop
    auto inner_loop_init = this->inner_loop_.init();
    auto inner_loop_condition = this->inner_loop_.condition();
    auto inner_loop_update = this->inner_loop_.update();
    if (symbolic::uses(inner_loop_init, outer_indvar->get_name()) ||
        symbolic::uses(inner_loop_condition, outer_indvar->get_name()) ||
        symbolic::uses(inner_loop_update, outer_indvar->get_name())) {
        return false;
    }

    // Criterion: Outer loop must not have any outer blocks
    if (outer_loop_.root().size() > 1) {
        return false;
    }
    if (outer_loop_.root().at(0).second.assignments().size() > 0) {
        return false;
    }
    if (&outer_loop_.root().at(0).first != &inner_loop_) {
        return false;
    }
    // Criterion: Any of both loops is a map
    if (dynamic_cast<structured_control_flow::Map*>(&outer_loop_) ||
        dynamic_cast<structured_control_flow::Map*>(&inner_loop_)) {
        return true;
    }

    return false;
};

void LoopInterchange::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    auto& outer_scope = static_cast<structured_control_flow::Sequence&>(*scope_analysis.parent_scope(&outer_loop_));
    auto& inner_scope = outer_loop_.root();

    int index = outer_scope.index(this->outer_loop_);
    auto& outer_transition = outer_scope.at(index).second;

    // Add new outer loop behind current outer loop
    structured_control_flow::StructuredLoop* new_outer_loop = nullptr;
    if (auto inner_map = dynamic_cast<structured_control_flow::Map*>(&inner_loop_)) {
        new_outer_loop = &builder.add_map_after(
            outer_scope,
            this->outer_loop_,
            inner_map->indvar(),
            inner_map->condition(),
            inner_map->init(),
            inner_map->update(),
            inner_map->schedule_type(),
            outer_transition.assignments(),
            this->inner_loop_.debug_info()
        );
    } else {
        new_outer_loop = &builder.add_for_after(
            outer_scope,
            this->outer_loop_,
            this->inner_loop_.indvar(),
            this->inner_loop_.condition(),
            this->inner_loop_.init(),
            this->inner_loop_.update(),
            outer_transition.assignments(),
            this->inner_loop_.debug_info()
        );
    }

    // Add new inner loop behind current inner loop
    structured_control_flow::StructuredLoop* new_inner_loop = nullptr;
    if (auto outer_map = dynamic_cast<structured_control_flow::Map*>(&outer_loop_)) {
        new_inner_loop = &builder.add_map_after(
            inner_scope,
            this->inner_loop_,
            outer_map->indvar(),
            outer_map->condition(),
            outer_map->init(),
            outer_map->update(),
            outer_map->schedule_type(),
            {},
            this->outer_loop_.debug_info()
        );
    } else {
        new_inner_loop = &builder.add_for_after(
            inner_scope,
            this->inner_loop_,
            this->outer_loop_.indvar(),
            this->outer_loop_.condition(),
            this->outer_loop_.init(),
            this->outer_loop_.update(),
            {},
            this->outer_loop_.debug_info()
        );
    }

    // Insert inner loop body into new inner loop
    builder.move_children(this->inner_loop_.root(), new_inner_loop->root());

    // Insert outer loop body into new outer loop
    builder.move_children(this->outer_loop_.root(), new_outer_loop->root());

    // Remove old loops
    builder.remove_child(new_outer_loop->root(), 0);
    builder.remove_child(outer_scope, index);

    analysis_manager.invalidate_all();
    applied_ = true;
    new_outer_loop_ = new_outer_loop;
    new_inner_loop_ = new_inner_loop;
};

void LoopInterchange::to_json(nlohmann::json& j) const {
    std::vector<std::string> loop_types;
    for (auto* loop : {&(this->outer_loop_), &(this->inner_loop_)}) {
        if (dynamic_cast<structured_control_flow::For*>(loop)) {
            loop_types.push_back("for");
        } else if (dynamic_cast<structured_control_flow::Map*>(loop)) {
            loop_types.push_back("map");
        } else {
            throw InvalidSDFGException("Unsupported loop type for serialization of loop: " + loop->indvar()->get_name());
        }
    }
    j["transformation_type"] = this->name();
    j["subgraph"] = {
        {"0", {{"element_id", this->outer_loop_.element_id()}, {"type", loop_types[0]}}},
        {"1", {{"element_id", this->inner_loop_.element_id()}, {"type", loop_types[1]}}}
    };
};

LoopInterchange LoopInterchange::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto outer_loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    auto inner_loop_id = desc["subgraph"]["1"]["element_id"].get<size_t>();
    auto outer_element = builder.find_element_by_id(outer_loop_id);
    auto inner_element = builder.find_element_by_id(inner_loop_id);
    if (outer_element == nullptr) {
        throw InvalidSDFGException("Element with ID " + std::to_string(outer_loop_id) + " not found.");
    }
    if (inner_element == nullptr) {
        throw InvalidSDFGException("Element with ID " + std::to_string(inner_loop_id) + " not found.");
    }
    auto outer_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(outer_element);
    if (outer_loop == nullptr) {
        throw InvalidSDFGException("Element with ID " + std::to_string(outer_loop_id) + " is not a StructuredLoop.");
    }
    auto inner_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(inner_element);
    if (inner_loop == nullptr) {
        throw InvalidSDFGException("Element with ID " + std::to_string(inner_loop_id) + " is not a StructuredLoop.");
    }

    return LoopInterchange(*outer_loop, *inner_loop);
};

structured_control_flow::StructuredLoop* LoopInterchange::new_outer_loop() const {
    if (!applied_) {
        throw InvalidSDFGException("Transformation has not been applied yet.");
    }
    return new_outer_loop_;
};

structured_control_flow::StructuredLoop* LoopInterchange::new_inner_loop() const {
    if (!applied_) {
        throw InvalidSDFGException("Transformation has not been applied yet.");
    }
    return new_inner_loop_;
};

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/loop_interchange.h"
2
3	#include "sdfg/analysis/scope_analysis.h"
4	#include "sdfg/exceptions.h"
5	#include "sdfg/structured_control_flow/for.h"
6	#include "sdfg/structured_control_flow/structured_loop.h"
7
8	namespace sdfg {
9	namespace transformations {
10
11	LoopInterchange::LoopInterchange(
12	structured_control_flow::StructuredLoop& outer_loop, structured_control_flow::StructuredLoop& inner_loop
13	)
14	: outer_loop_(outer_loop), inner_loop_(inner_loop) {	11✔
15
16	};	11✔
17
18	std::string LoopInterchange::name() const { return "LoopInterchange"; };	4✔
19
20	bool LoopInterchange::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	9✔
21	auto& outer_indvar = this->outer_loop_.indvar();	9✔
22
23	// Criterion: Inner loop must not depend on outer loop
24	auto inner_loop_init = this->inner_loop_.init();	9✔
25	auto inner_loop_condition = this->inner_loop_.condition();	9✔
26	auto inner_loop_update = this->inner_loop_.update();	9✔
27	if (symbolic::uses(inner_loop_init, outer_indvar->get_name()) \|\|	9✔
28	symbolic::uses(inner_loop_condition, outer_indvar->get_name()) \|\|	9✔
29	symbolic::uses(inner_loop_update, outer_indvar->get_name())) {	9✔
30	return false;	1✔
31	}	1✔
32
33	// Criterion: Outer loop must not have any outer blocks
34	if (outer_loop_.root().size() > 1) {	8✔
35	return false;	1✔
36	}	1✔
37	if (outer_loop_.root().at(0).second.assignments().size() > 0) {	7✔
38	return false;	×
39	}	×
40	if (&outer_loop_.root().at(0).first != &inner_loop_) {	7✔
41	return false;	×
42	}	×
43	// Criterion: Any of both loops is a map
44	if (dynamic_cast<structured_control_flow::Map*>(&outer_loop_) \|\|	7✔
45	dynamic_cast<structured_control_flow::Map*>(&inner_loop_)) {	7✔
46	return true;	7✔
47	}	7✔
48
49	return false;	×
50	};	7✔
51
52	void LoopInterchange::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	7✔
53	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	7✔
54	auto& outer_scope = static_cast<structured_control_flow::Sequence&>(*scope_analysis.parent_scope(&outer_loop_));	7✔
55	auto& inner_scope = outer_loop_.root();	7✔
56
57	int index = outer_scope.index(this->outer_loop_);	7✔
58	auto& outer_transition = outer_scope.at(index).second;	7✔
59
60	// Add new outer loop behind current outer loop
61	structured_control_flow::StructuredLoop* new_outer_loop = nullptr;	7✔
62	if (auto inner_map = dynamic_cast<structured_control_flow::Map*>(&inner_loop_)) {	7✔
63	new_outer_loop = &builder.add_map_after(	7✔
64	outer_scope,	7✔
65	this->outer_loop_,	7✔
66	inner_map->indvar(),	7✔
67	inner_map->condition(),	7✔
68	inner_map->init(),	7✔
69	inner_map->update(),	7✔
70	inner_map->schedule_type(),	7✔
71	outer_transition.assignments(),	7✔
72	this->inner_loop_.debug_info()	7✔
73	);	7✔
74	} else {	7✔
75	new_outer_loop = &builder.add_for_after(	×
76	outer_scope,	×
77	this->outer_loop_,	×
78	this->inner_loop_.indvar(),	×
79	this->inner_loop_.condition(),	×
80	this->inner_loop_.init(),	×
81	this->inner_loop_.update(),	×
82	outer_transition.assignments(),	×
83	this->inner_loop_.debug_info()	×
84	);	×
85	}	×
86
87	// Add new inner loop behind current inner loop
88	structured_control_flow::StructuredLoop* new_inner_loop = nullptr;	7✔
89	if (auto outer_map = dynamic_cast<structured_control_flow::Map*>(&outer_loop_)) {	7✔
90	new_inner_loop = &builder.add_map_after(	7✔
91	inner_scope,	7✔
92	this->inner_loop_,	7✔
93	outer_map->indvar(),	7✔
94	outer_map->condition(),	7✔
95	outer_map->init(),	7✔
96	outer_map->update(),	7✔
97	outer_map->schedule_type(),	7✔
98	{},	7✔
99	this->outer_loop_.debug_info()	7✔
100	);	7✔
101	} else {	7✔
102	new_inner_loop = &builder.add_for_after(	×
103	inner_scope,	×
104	this->inner_loop_,	×
105	this->outer_loop_.indvar(),	×
106	this->outer_loop_.condition(),	×
107	this->outer_loop_.init(),	×
108	this->outer_loop_.update(),	×
109	{},	×
110	this->outer_loop_.debug_info()	×
111	);	×
112	}	×
113
114	// Insert inner loop body into new inner loop
115	builder.move_children(this->inner_loop_.root(), new_inner_loop->root());	7✔
116
117	// Insert outer loop body into new outer loop
118	builder.move_children(this->outer_loop_.root(), new_outer_loop->root());	7✔
119
120	// Remove old loops
121	builder.remove_child(new_outer_loop->root(), 0);	7✔
122	builder.remove_child(outer_scope, index);	7✔
123
124	analysis_manager.invalidate_all();	7✔
125	applied_ = true;	7✔
126	new_outer_loop_ = new_outer_loop;	7✔
127	new_inner_loop_ = new_inner_loop;	7✔
128	};	7✔
129
130	void LoopInterchange::to_json(nlohmann::json& j) const {	3✔
131	std::vector<std::string> loop_types;	3✔
132	for (auto* loop : {&(this->outer_loop_), &(this->inner_loop_)}) {	6✔
133	if (dynamic_cast<structured_control_flow::For*>(loop)) {	6✔
134	loop_types.push_back("for");	×
135	} else if (dynamic_cast<structured_control_flow::Map*>(loop)) {	6✔
136	loop_types.push_back("map");	6✔
137	} else {	6✔
138	throw InvalidSDFGException("Unsupported loop type for serialization of loop: " + loop->indvar()->get_name());	×
139	}	×
140	}	6✔
141	j["transformation_type"] = this->name();	3✔
142	j["subgraph"] = {	3✔
143	{"0", {{"element_id", this->outer_loop_.element_id()}, {"type", loop_types[0]}}},	3✔
144	{"1", {{"element_id", this->inner_loop_.element_id()}, {"type", loop_types[1]}}}	3✔
145	};	3✔
146	};	3✔
147
148	LoopInterchange LoopInterchange::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	3✔
149	auto outer_loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	3✔
150	auto inner_loop_id = desc["subgraph"]["1"]["element_id"].get<size_t>();	3✔
151	auto outer_element = builder.find_element_by_id(outer_loop_id);	3✔
152	auto inner_element = builder.find_element_by_id(inner_loop_id);	3✔
153	if (outer_element == nullptr) {	3✔
154	throw InvalidSDFGException("Element with ID " + std::to_string(outer_loop_id) + " not found.");	×
155	}	×
156	if (inner_element == nullptr) {	3✔
157	throw InvalidSDFGException("Element with ID " + std::to_string(inner_loop_id) + " not found.");	×
158	}	×
159	auto outer_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(outer_element);	3✔
160	if (outer_loop == nullptr) {	3✔
161	throw InvalidSDFGException("Element with ID " + std::to_string(outer_loop_id) + " is not a StructuredLoop.");	×
162	}	×
163	auto inner_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(inner_element);	3✔
164	if (inner_loop == nullptr) {	3✔
165	throw InvalidSDFGException("Element with ID " + std::to_string(inner_loop_id) + " is not a StructuredLoop.");	×
166	}	×
167
168	return LoopInterchange(outer_loop, inner_loop);	3✔
169	};	3✔
170
171	structured_control_flow::StructuredLoop* LoopInterchange::new_outer_loop() const {	×
172	if (!applied_) {	×
173	throw InvalidSDFGException("Transformation has not been applied yet.");	×
174	}	×
175	return new_outer_loop_;	×
176	};	×
177
178	structured_control_flow::StructuredLoop* LoopInterchange::new_inner_loop() const {	×
179	if (!applied_) {	×
180	throw InvalidSDFGException("Transformation has not been applied yet.");	×
181	}	×
182	return new_inner_loop_;	×
183	};	×
184
185	} // namespace transformations
186	} // namespace sdfg

daisytuner / sdfglib / 20792180504

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