23025557374

Committed 12 Mar 2026 09:49PM UTC coverage: 63.719% (+0.2%) from 63.488%

Build # 23025557374

Build Type

Pull #580

github

Committed by

web-flow

Commit Message

Merge 2a918fd37 into 16e11e295

Pull Request Pull Request #580: Dependence Deltas, LoopInterchange with Fourier-Motzkin and Novel TileFusion Transformation

Coverage Stats

613 of 845 new or added lines in 8 files covered. (72.54%)

6 existing lines in 3 files now uncovered.

25273 of 39663 relevant lines covered (63.72%)

400.63 hits per line

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

44.16

/sdfg/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 {
    // Determine loop types for serialization
    std::string outer_type = "for";
    std::string inner_type = "for";

    if (dynamic_cast<const structured_control_flow::Map*>(&this->outer_loop_)) {
        outer_type = "map";
    }
    if (dynamic_cast<const structured_control_flow::Map*>(&this->inner_loop_)) {
        inner_type = "map";
    }

    j["transformation_type"] = this->name();
    j["subgraph"] = {
        {"0", {{"element_id", this->outer_loop_.element_id()}, {"type", outer_type}}},
        {"1", {{"element_id", this->inner_loop_.element_id()}, {"type", inner_type}}}
    };
    j["parameters"] = {{"skew_factor", this->skew_factor_}};
}

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) {}	10✔
37
38	std::string LoopSkewing::name() const { return "LoopSkewing"; }	×
39
40	bool LoopSkewing::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	10✔
41	// Criterion 0: Skew factor must be non-zero
42	if (this->skew_factor_ == 0) {	10✔
43	return false;	1✔
44	}	1✔
45
46	auto& outer_indvar = this->outer_loop_.indvar();	9✔
47
48	// Criterion 2: Inner loop must not depend on outer loop indvar
49	auto inner_loop_init = this->inner_loop_.init();	9✔
50	auto inner_loop_condition = this->inner_loop_.condition();	9✔
51	auto inner_loop_update = this->inner_loop_.update();	9✔
52
53	if (symbolic::uses(inner_loop_init, outer_indvar->get_name()) \|\|	9✔
54	symbolic::uses(inner_loop_condition, outer_indvar->get_name()) \|\|	9✔
55	symbolic::uses(inner_loop_update, outer_indvar->get_name())) {	9✔
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) {	8✔
61	return false;	1✔
62	}	1✔
63	if (outer_loop_.root().at(0).second.assignments().size() > 0) {	7✔
64	return false;	×
65	}	×
66	if (&outer_loop_.root().at(0).first != &inner_loop_) {	7✔
67	return false;	×
68	}	×
69
70	return true;	7✔
71	}	7✔
72
73	void LoopSkewing::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	7✔
74	auto outer_indvar = this->outer_loop_.indvar();	7✔
75	auto inner_indvar = this->inner_loop_.indvar();	7✔
76
77	// Calculate the skewing offset: skew_factor * (outer_indvar - outer_init)
78	auto skew_offset =	7✔
79	symbolic::mul(symbolic::integer(this->skew_factor_), symbolic::sub(outer_indvar, this->outer_loop_.init()));	7✔
80
81	// New inner loop init: inner_init + skew_offset
82	auto new_inner_init = symbolic::add(this->inner_loop_.init(), skew_offset);	7✔
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 =	7✔
88	symbolic::subs(this->inner_loop_.condition(), inner_indvar, symbolic::sub(inner_indvar, skew_offset));	7✔
89
90	// Inner loop update remains the same
91	auto new_inner_update = this->inner_loop_.update();	7✔
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);	7✔
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));	7✔
99
100	analysis_manager.invalidate_all();	7✔
101	}	7✔
102
103	void LoopSkewing::to_json(nlohmann::json& j) const {	×
104	// Determine loop types for serialization
105	std::string outer_type = "for";	×
NEW 106	std::string inner_type = "for";	×
107
108	if (dynamic_cast<const structured_control_flow::Map*>(&this->outer_loop_)) {	×
109	outer_type = "map";	×
110	}	×
NEW 111	if (dynamic_cast<const structured_control_flow::Map*>(&this->inner_loop_)) {	×
NEW 112	inner_type = "map";	×
NEW 113	}	×
114
115	j["transformation_type"] = this->name();	×
116	j["subgraph"] = {	×
117	{"0", {{"element_id", this->outer_loop_.element_id()}, {"type", outer_type}}},	×
118	{"1", {{"element_id", this->inner_loop_.element_id()}, {"type", inner_type}}}	×
119	};	×
120	j["parameters"] = {{"skew_factor", this->skew_factor_}};	×
121	}	×
122
123	LoopSkewing LoopSkewing::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
124	auto outer_loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
125	auto inner_loop_id = desc["subgraph"]["1"]["element_id"].get<size_t>();	×
126	int skew_factor = desc["parameters"]["skew_factor"].get<int>();	×
127
128	auto outer_element = builder.find_element_by_id(outer_loop_id);	×
129	auto inner_element = builder.find_element_by_id(inner_loop_id);	×
130
131	if (outer_element == nullptr) {	×
132	throw std::runtime_error("Element with ID " + std::to_string(outer_loop_id) + " not found.");	×
133	}	×
134	if (inner_element == nullptr) {	×
135	throw std::runtime_error("Element with ID " + std::to_string(inner_loop_id) + " not found.");	×
136	}	×
137
138	auto outer_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(outer_element);	×
139	if (outer_loop == nullptr) {	×
140	throw std::runtime_error("Element with ID " + std::to_string(outer_loop_id) + " is not a StructuredLoop.");	×
141	}	×
142
143	auto inner_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(inner_element);	×
144	if (inner_loop == nullptr) {	×
145	throw std::runtime_error("Element with ID " + std::to_string(inner_loop_id) + " is not a StructuredLoop.");	×
146	}	×
147
148	return LoopSkewing(outer_loop, inner_loop, skew_factor);	×
149	}	×
150
151	} // namespace transformations
152	} // namespace sdfg

daisytuner / docc / 23025557374

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