15827874660

Committed 23 Jun 2025 03:03PM UTC coverage: 64.193% (+0.4%) from 63.824%

Build # 15827874660

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #100 from daisytuner/transformations

new definition of map and adapts transformations

Run Details

148 of 194 new or added lines in 13 files covered. (76.29%)

45 existing lines in 4 files now uncovered.

8193 of 12763 relevant lines covered (64.19%)

136.04 hits per line

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

75.58

/src/transformations/loop_interchange.cpp

#include "sdfg/transformations/loop_interchange.h"

#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) {
        throw InvalidTransformationDescriptionException(
            "Element with ID " + std::to_string(outer_loop_id) + " not found.");
    }
    if (!inner_element) {
        throw InvalidTransformationDescriptionException(
            "Element with ID " + std::to_string(inner_loop_id) + " not found.");
    }
    auto outer_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(outer_element);
    auto inner_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(inner_element);

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

}  // namespace transformations
}  // namespace sdfg

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

daisytuner / sdfglib / 15827874660

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