28106147644

Committed 24 Jun 2026 02:32PM UTC coverage: 61.922% (+0.1%) from 61.779%

Build # 28106147644

Build Type

Pull #806

github

Committed by

web-flow

Commit Message

Merge 2be414d54 into 57cc1db99

Pull Request Pull Request #806: Map Collapse for Multiple targets in a neste sequence

Coverage Stats

165 of 185 new or added lines in 2 files covered. (89.19%)

419 existing lines in 30 files now uncovered.

37705 of 60891 relevant lines covered (61.92%)

1004.4 hits per line

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

83.33

/opt/src/transformations/loop_skewing.cpp

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

#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/symbolic/symbolic.h"

/**
 * Loop Skewing Transformation Implementation
 *
 * This simplified implementation of loop skewing modifies the inner loop's iteration
 * space to depend on the outer loop's iteration variable, creating a "skewed" pattern.
 *
 * The transformation:
 * - Works with any StructuredLoop (For or Map) as inner loop
 * - Adjusts inner loop init: init_j + skew_factor * (i - init_i)
 * - Adjusts inner loop condition using symbolic::subs
 * - Updates memory access patterns in loop body using root().replace()
 * - Uses builder.update_loop() to modify the loop in place
 *
 * Safety:
 * - Skewing is a pure re-indexing that preserves iteration order within the inner loop
 * - Inner loop bounds must not depend on outer loop variable
 * - Loops must be properly nested
 */

namespace sdfg {
namespace transformations {

LoopSkewing::LoopSkewing(
    structured_control_flow::StructuredLoop& outer_loop,
    structured_control_flow::StructuredLoop& inner_loop,
    int skew_factor
)
    : outer_loop_(outer_loop), inner_loop_(inner_loop), skew_factor_(skew_factor) {}

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

bool LoopSkewing::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    // Criterion 0: Skew factor must be non-zero
    if (this->skew_factor_ == 0) {
        return false;
    }

    auto& outer_indvar = this->outer_loop_.indvar();

    // Criterion 2: Inner loop must not depend on outer loop indvar
    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 3: Outer loop must have only the inner loop as a child
    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;
    }

    return true;
}

void LoopSkewing::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto outer_indvar = this->outer_loop_.indvar();
    auto inner_indvar = this->inner_loop_.indvar();

    // Calculate the skewing offset: skew_factor * (outer_indvar - outer_init)
    auto skew_offset =
        symbolic::mul(symbolic::integer(this->skew_factor_), symbolic::sub(outer_indvar, this->outer_loop_.init()));

    // New inner loop init: inner_init + skew_offset
    auto new_inner_init = symbolic::add(this->inner_loop_.init(), skew_offset);

    // New inner loop condition:
    // Substitute j with (j - skew_offset) in the condition
    // This adjusts the upper bound: j < M becomes (j - offset) < M, i.e., j < M + offset
    auto new_inner_condition =
        symbolic::subs(this->inner_loop_.condition(), inner_indvar, symbolic::sub(inner_indvar, skew_offset));

    // Inner loop update remains the same
    auto new_inner_update = this->inner_loop_.update();

    // Update the inner loop in place using builder.update_loop
    builder.update_loop(this->inner_loop_, inner_indvar, new_inner_condition, new_inner_init, new_inner_update);

    // Adjust memory access patterns in the loop body
    // Replace j with (j - skew_offset) in all expressions
    this->inner_loop_.root().replace(inner_indvar, symbolic::sub(inner_indvar, skew_offset));

    analysis_manager.invalidate_all();
}

void LoopSkewing::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();
    j["parameters"] = nlohmann::json::object();
    j["parameters"] = {{"skew_factor", this->skew_factor_}};

    serializer::JSONSerializer ser_flat(false);
    j["subgraph"] = nlohmann::json::object();
    j["subgraph"]["0"] = nlohmann::json::object();
    ser_flat.serialize_node(j["subgraph"]["0"], outer_loop_);

    j["subgraph"]["1"] = nlohmann::json::object();
    ser_flat.serialize_node(j["subgraph"]["1"], inner_loop_);
}

LoopSkewing LoopSkewing::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>();
    int skew_factor = desc["parameters"]["skew_factor"].get<int>();

    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 LoopSkewing(*outer_loop, *inner_loop, skew_factor);
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/loop_skewing.h"
2	#include <stdexcept>
3
4	#include "sdfg/builder/structured_sdfg_builder.h"
5	#include "sdfg/structured_control_flow/map.h"
6	#include "sdfg/structured_control_flow/structured_loop.h"
7	#include "sdfg/symbolic/symbolic.h"
8
9	/**
10	* Loop Skewing Transformation Implementation
11	*
12	* This simplified implementation of loop skewing modifies the inner loop's iteration
13	* space to depend on the outer loop's iteration variable, creating a "skewed" pattern.
14	*
15	* The transformation:
16	* - Works with any StructuredLoop (For or Map) as inner loop
17	* - Adjusts inner loop init: init_j + skew_factor * (i - init_i)
18	* - Adjusts inner loop condition using symbolic::subs
19	* - Updates memory access patterns in loop body using root().replace()
20	* - Uses builder.update_loop() to modify the loop in place
21	*
22	* Safety:
23	* - Skewing is a pure re-indexing that preserves iteration order within the inner loop
24	* - Inner loop bounds must not depend on outer loop variable
25	* - Loops must be properly nested
26	*/
27
28	namespace sdfg {
29	namespace transformations {
30
31	LoopSkewing::LoopSkewing(
32	structured_control_flow::StructuredLoop& outer_loop,
33	structured_control_flow::StructuredLoop& inner_loop,
34	int skew_factor
35	)
36	: outer_loop_(outer_loop), inner_loop_(inner_loop), skew_factor_(skew_factor) {}	17✔
37
38	std::string LoopSkewing::name() const { return "LoopSkewing"; }	8✔
39
40	bool LoopSkewing::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	15✔
41	// Criterion 0: Skew factor must be non-zero
42	if (this->skew_factor_ == 0) {	15✔
43	return false;	1✔
44	}	1✔
45
46	auto& outer_indvar = this->outer_loop_.indvar();	14✔
47
48	// Criterion 2: Inner loop must not depend on outer loop indvar
49	auto inner_loop_init = this->inner_loop_.init();	14✔
50	auto inner_loop_condition = this->inner_loop_.condition();	14✔
51	auto inner_loop_update = this->inner_loop_.update();	14✔
52
53	if (symbolic::uses(inner_loop_init, outer_indvar->get_name()) \|\|	14✔
54	symbolic::uses(inner_loop_condition, outer_indvar->get_name()) \|\|	14✔
55	symbolic::uses(inner_loop_update, outer_indvar->get_name())) {	14✔
56	return false;	1✔
57	}	1✔
58
59	// Criterion 3: Outer loop must have only the inner loop as a child
60	if (outer_loop_.root().size() != 1) {	13✔
61	return false;	1✔
62	}	1✔
63	if (outer_loop_.root().at(0).second.assignments().size() > 0) {	12✔
64	return false;	×
65	}	×
66	if (&outer_loop_.root().at(0).first != &inner_loop_) {	12✔
67	return false;	×
68	}	×
69
70	return true;	12✔
71	}	12✔
72
73	void LoopSkewing::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	12✔
74	auto outer_indvar = this->outer_loop_.indvar();	12✔
75	auto inner_indvar = this->inner_loop_.indvar();	12✔
76
77	// Calculate the skewing offset: skew_factor * (outer_indvar - outer_init)
78	auto skew_offset =	12✔
79	symbolic::mul(symbolic::integer(this->skew_factor_), symbolic::sub(outer_indvar, this->outer_loop_.init()));	12✔
80
81	// New inner loop init: inner_init + skew_offset
82	auto new_inner_init = symbolic::add(this->inner_loop_.init(), skew_offset);	12✔
83
84	// New inner loop condition:
85	// Substitute j with (j - skew_offset) in the condition
86	// This adjusts the upper bound: j < M becomes (j - offset) < M, i.e., j < M + offset
87	auto new_inner_condition =	12✔
88	symbolic::subs(this->inner_loop_.condition(), inner_indvar, symbolic::sub(inner_indvar, skew_offset));	12✔
89
90	// Inner loop update remains the same
91	auto new_inner_update = this->inner_loop_.update();	12✔
92
93	// Update the inner loop in place using builder.update_loop
94	builder.update_loop(this->inner_loop_, inner_indvar, new_inner_condition, new_inner_init, new_inner_update);	12✔
95
96	// Adjust memory access patterns in the loop body
97	// Replace j with (j - skew_offset) in all expressions
98	this->inner_loop_.root().replace(inner_indvar, symbolic::sub(inner_indvar, skew_offset));	12✔
99
100	analysis_manager.invalidate_all();	12✔
101	}	12✔
102
103	void LoopSkewing::to_json(nlohmann::json& j) const {	6✔
104	j["transformation_type"] = this->name();	6✔
105	j["parameters"] = nlohmann::json::object();	6✔
106	j["parameters"] = {{"skew_factor", this->skew_factor_}};	6✔
107
108	serializer::JSONSerializer ser_flat(false);	6✔
109	j["subgraph"] = nlohmann::json::object();	6✔
110	j["subgraph"]["0"] = nlohmann::json::object();	6✔
111	ser_flat.serialize_node(j["subgraph"]["0"], outer_loop_);	6✔
112
113	j["subgraph"]["1"] = nlohmann::json::object();	6✔
114	ser_flat.serialize_node(j["subgraph"]["1"], inner_loop_);	6✔
115	}	6✔
116
117	LoopSkewing LoopSkewing::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	1✔
118	auto outer_loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	1✔
119	auto inner_loop_id = desc["subgraph"]["1"]["element_id"].get<size_t>();	1✔
120	int skew_factor = desc["parameters"]["skew_factor"].get<int>();	1✔
121
122	auto outer_element = builder.find_element_by_id(outer_loop_id);	1✔
123	auto inner_element = builder.find_element_by_id(inner_loop_id);	1✔
124
125	if (outer_element == nullptr) {	1✔
UNCOV 126	throw std::runtime_error("Element with ID " + std::to_string(outer_loop_id) + " not found.");	×
UNCOV 127	}	×
128	if (inner_element == nullptr) {	1✔
UNCOV 129	throw std::runtime_error("Element with ID " + std::to_string(inner_loop_id) + " not found.");	×
UNCOV 130	}	×
131
132	auto outer_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(outer_element);	1✔
133	if (outer_loop == nullptr) {	1✔
UNCOV 134	throw std::runtime_error("Element with ID " + std::to_string(outer_loop_id) + " is not a StructuredLoop.");	×
135	}	×
136
137	auto inner_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(inner_element);	1✔
138	if (inner_loop == nullptr) {	1✔
UNCOV 139	throw std::runtime_error("Element with ID " + std::to_string(inner_loop_id) + " is not a StructuredLoop.");	×
140	}	×
141
142	return LoopSkewing(outer_loop, inner_loop, skew_factor);	1✔
143	}	1✔
144
145	} // namespace transformations
146	} // namespace sdfg

daisytuner / docc / 28106147644

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