20847660360

Committed 09 Jan 2026 09:39AM UTC coverage: 62.402% (-0.05%) from 62.448%

Build # 20847660360

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #439 from daisytuner/copilot/add-loop-skewing-transformation

Add LoopSkewing transformation with simplified in-place update approach

Run Details

37 of 77 new or added lines in 1 file covered. (48.05%)

15107 of 24209 relevant lines covered (62.4%)

89.05 hits per line

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

48.05

/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:
 * - Requires the inner loop to be a Map (parallel loop with independent iterations)
 * - 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:
 * - Inner loop must be a Map (guarantees independent iterations)
 * - 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;
    }

    // Criterion 1: Inner loop must be a Map
    // Maps guarantee independent iterations, ensuring the transformation is safe
    if (!dynamic_cast<structured_control_flow::Map*>(&inner_loop_)) {
        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 = "map"; // Inner loop must be a Map by construction

    if (dynamic_cast<const structured_control_flow::Map*>(&this->outer_loop_)) {
        outer_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	* - Requires the inner loop to be a Map (parallel loop with independent iterations)
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	* - Inner loop must be a Map (guarantees independent iterations)
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) {}	9✔
37
NEW 38	std::string LoopSkewing::name() const { return "LoopSkewing"; }	×
39
40	bool LoopSkewing::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	9✔
41	// Criterion 0: Skew factor must be non-zero
42	if (this->skew_factor_ == 0) {	9✔
43	return false;	1✔
44	}	1✔
45
46	// Criterion 1: Inner loop must be a Map
47	// Maps guarantee independent iterations, ensuring the transformation is safe
48	if (!dynamic_cast<structured_control_flow::Map*>(&inner_loop_)) {	8✔
49	return false;	1✔
50	}	1✔
51
52	auto& outer_indvar = this->outer_loop_.indvar();	7✔
53
54	// Criterion 2: Inner loop must not depend on outer loop indvar
55	auto inner_loop_init = this->inner_loop_.init();	7✔
56	auto inner_loop_condition = this->inner_loop_.condition();	7✔
57	auto inner_loop_update = this->inner_loop_.update();	7✔
58
59	if (symbolic::uses(inner_loop_init, outer_indvar->get_name()) \|\|	7✔
60	symbolic::uses(inner_loop_condition, outer_indvar->get_name()) \|\|	7✔
61	symbolic::uses(inner_loop_update, outer_indvar->get_name())) {	7✔
62	return false;	1✔
63	}	1✔
64
65	// Criterion 3: Outer loop must have only the inner loop as a child
66	if (outer_loop_.root().size() != 1) {	6✔
67	return false;	1✔
68	}	1✔
69	if (outer_loop_.root().at(0).second.assignments().size() > 0) {	5✔
NEW 70	return false;	×
NEW 71	}	×
72	if (&outer_loop_.root().at(0).first != &inner_loop_) {	5✔
NEW 73	return false;	×
NEW 74	}	×
75
76	return true;	5✔
77	}	5✔
78
79	void LoopSkewing::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	5✔
80	auto outer_indvar = this->outer_loop_.indvar();	5✔
81	auto inner_indvar = this->inner_loop_.indvar();	5✔
82
83	// Calculate the skewing offset: skew_factor * (outer_indvar - outer_init)
84	auto skew_offset =	5✔
85	symbolic::mul(symbolic::integer(this->skew_factor_), symbolic::sub(outer_indvar, this->outer_loop_.init()));	5✔
86
87	// New inner loop init: inner_init + skew_offset
88	auto new_inner_init = symbolic::add(this->inner_loop_.init(), skew_offset);	5✔
89
90	// New inner loop condition:
91	// Substitute j with (j - skew_offset) in the condition
92	// This adjusts the upper bound: j < M becomes (j - offset) < M, i.e., j < M + offset
93	auto new_inner_condition =	5✔
94	symbolic::subs(this->inner_loop_.condition(), inner_indvar, symbolic::sub(inner_indvar, skew_offset));	5✔
95
96	// Inner loop update remains the same
97	auto new_inner_update = this->inner_loop_.update();	5✔
98
99	// Update the inner loop in place using builder.update_loop
100	builder.update_loop(this->inner_loop_, inner_indvar, new_inner_condition, new_inner_init, new_inner_update);	5✔
101
102	// Adjust memory access patterns in the loop body
103	// Replace j with (j - skew_offset) in all expressions
104	this->inner_loop_.root().replace(inner_indvar, symbolic::sub(inner_indvar, skew_offset));	5✔
105
106	analysis_manager.invalidate_all();	5✔
107	}	5✔
108
NEW 109	void LoopSkewing::to_json(nlohmann::json& j) const {	×
110	// Determine loop types for serialization
NEW 111	std::string outer_type = "for";	×
NEW 112	std::string inner_type = "map"; // Inner loop must be a Map by construction	×
113
NEW 114	if (dynamic_cast<const structured_control_flow::Map*>(&this->outer_loop_)) {	×
NEW 115	outer_type = "map";	×
NEW 116	}	×
117
NEW 118	j["transformation_type"] = this->name();	×
NEW 119	j["subgraph"] = {	×
NEW 120	{"0", {{"element_id", this->outer_loop_.element_id()}, {"type", outer_type}}},	×
NEW 121	{"1", {{"element_id", this->inner_loop_.element_id()}, {"type", inner_type}}}	×
NEW 122	};	×
NEW 123	j["parameters"] = {{"skew_factor", this->skew_factor_}};	×
NEW 124	}	×
125
NEW 126	LoopSkewing LoopSkewing::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
NEW 127	auto outer_loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
NEW 128	auto inner_loop_id = desc["subgraph"]["1"]["element_id"].get<size_t>();	×
NEW 129	int skew_factor = desc["parameters"]["skew_factor"].get<int>();	×
130
NEW 131	auto outer_element = builder.find_element_by_id(outer_loop_id);	×
NEW 132	auto inner_element = builder.find_element_by_id(inner_loop_id);	×
133
NEW 134	if (outer_element == nullptr) {	×
NEW 135	throw std::runtime_error("Element with ID " + std::to_string(outer_loop_id) + " not found.");	×
NEW 136	}	×
NEW 137	if (inner_element == nullptr) {	×
NEW 138	throw std::runtime_error("Element with ID " + std::to_string(inner_loop_id) + " not found.");	×
NEW 139	}	×
140
NEW 141	auto outer_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(outer_element);	×
NEW 142	if (outer_loop == nullptr) {	×
NEW 143	throw std::runtime_error("Element with ID " + std::to_string(outer_loop_id) + " is not a StructuredLoop.");	×
NEW 144	}	×
145
NEW 146	auto inner_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(inner_element);	×
NEW 147	if (inner_loop == nullptr) {	×
NEW 148	throw std::runtime_error("Element with ID " + std::to_string(inner_loop_id) + " is not a StructuredLoop.");	×
NEW 149	}	×
150
NEW 151	return LoopSkewing(outer_loop, inner_loop, skew_factor);	×
NEW 152	}	×
153
154	} // namespace transformations
155	} // namespace sdfg

daisytuner / sdfglib / 20847660360

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