16416635235

Committed 21 Jul 2025 12:12PM UTC coverage: 65.094% (-0.01%) from 65.106%

Build # 16416635235

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #154 from daisytuner/stabilize-replay

Stabilize replay

Run Details

18 of 34 new or added lines in 8 files covered. (52.94%)

1 existing line in 1 file now uncovered.

8804 of 13525 relevant lines covered (65.09%)

176.51 hits per line

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

73.53

/src/transformations/loop_interchange.cpp

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

#include "sdfg/analysis/scope_analysis.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 = static_cast<structured_control_flow::Sequence&>(*scope_analysis.parent_scope(&inner_loop_));

    // 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()
                              )
                              .first;
    } 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()
                              )
                              .first;
    }

    // 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()
                              )
                              .first;
    } 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()
                              )
                              .first;
    }

    // Insert inner loop body into new inner loop
    auto& inner_body = this->inner_loop_.root();
    builder.insert_children(new_inner_loop->root(), inner_body, 0);

    // Insert outer loop body into new outer loop
    auto& outer_body = this->outer_loop_.root();
    builder.insert_children(new_outer_loop->root(), outer_body, 0);

    // Remove old loops
    builder.remove_child(new_outer_loop->root(), this->inner_loop_);
    builder.remove_child(outer_scope, this->outer_loop_);

    analysis_manager.invalidate_all();
};

void LoopInterchange::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();
    j["outer_loop_element_id"] = this->outer_loop_.element_id();
    j["inner_loop_element_id"] = this->inner_loop_.element_id();
};

LoopInterchange LoopInterchange::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto outer_loop_id = desc["outer_loop_element_id"].get<size_t>();
    auto inner_loop_id = desc["inner_loop_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 std::runtime_error("Element with ID " + std::to_string(outer_loop_id) + " not found.");
    }
    if (inner_element == nullptr) {
        throw std::runtime_error("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 std::runtime_error("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 std::runtime_error("Element with ID " + std::to_string(inner_loop_id) + " is not a StructuredLoop.");
    }

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

} // namespace transformations
} // namespace sdfg

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

daisytuner / sdfglib / 16416635235

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