23953339753

Committed 03 Apr 2026 04:22PM UTC coverage: 64.653%. First build

Build # 23953339753

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #641 from daisytuner/loop-unit-stride

adds LoopUnitStride transformation

Coverage Stats

55 of 69 new or added lines in 1 file covered. (79.71%)

29024 of 44892 relevant lines covered (64.65%)

468.33 hits per line

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

79.71

/opt/src/transformations/loop_unit_stride.cpp

#include "sdfg/transformations/loop_unit_stride.h"

#include <stdexcept>

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

/**
 * Loop Unit Stride Transformation Implementation
 *
 * This transformation converts a loop with non-unit stride to unit stride
 * using symbolic substitution on the condition. Direction is preserved.
 *
 * Precondition: init == 0 (apply LoopShift first if needed)
 *
 * Algorithm:
 * 1. Verify init == 0 and stride != 1 and stride != -1
 * 2. Compute strided expression: strided_expr = |stride| * i
 * 3. Substitute indvar with strided_expr in the condition
 * 4. Create new loop: for i = 0; cond(strided_expr); i++ or i--
 * 5. Add assignment: __i_orig__ = strided_expr
 * 6. Replace all uses of indvar with __i_orig__
 *
 * Example (positive stride s = 2):
 *   Original: for (i = 0; i < 8; i += 2)  // iterations: 0, 2, 4, 6
 *   After:    for (i = 0; 2*i < 8; i++)
 *             __i_orig__ = 2 * i
 *
 * Example (negative stride s = -2):
 *   Original: for (i = 0; -10 < i; i -= 2)  // iterations: 0, -2, -4, -6, -8
 *   After:    for (i = 0; -10 < 2*i; i--)   // Note: |stride| used, direction preserved
 *             __i_orig__ = 2 * i            // i' = 0, -1, -2, -3, -4 -> 0, -2, -4, -6, -8
 *
 */

namespace sdfg {
namespace transformations {

LoopUnitStride::LoopUnitStride(structured_control_flow::StructuredLoop& loop) : loop_(loop) {}

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

bool LoopUnitStride::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    // Require init == 0 (apply LoopShift first)
    if (!symbolic::eq(loop_.init(), symbolic::zero())) {
        return false;
    }

    // Check for non-unit stride
    auto stride = loop_.stride();
    if (stride.is_null()) {
        return false;
    }

    int stride_val = stride->as_int();
    if (stride_val == 1 || stride_val == -1) {
        // Already unit stride, nothing to do
        // Use LoopRotate for stride = -1
        return false;
    }

    if (stride_val == 0) {
        // Zero stride is invalid
        return false;
    }

    return true;
}

void LoopUnitStride::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto indvar = loop_.indvar();
    auto old_condition = loop_.condition();
    auto stride = loop_.stride();
    int stride_val = stride->as_int();
    bool positive = stride_val > 0;
    int stride_val_abs = std::abs(stride_val);

    // Compute the strided expression: stride * i
    // (init is guaranteed to be 0 by can_be_applied)
    auto strided_expr = symbolic::mul(symbolic::integer(stride_val_abs), indvar);

    // New loop parameters:
    // - init = 0
    // - condition = old_condition with indvar substituted by strided_expr
    // - update = i + 1 or i - 1
    auto new_init = symbolic::zero();
    auto new_condition = symbolic::subs(old_condition, indvar, strided_expr);
    auto new_update = positive ? symbolic::add(indvar, symbolic::one()) : symbolic::sub(indvar, symbolic::one());

    // Create a new container for the strided (original) value
    strided_container_name_ = "__" + indvar->get_name() + "_orig__";

    // Find a unique name if it already exists
    int suffix = 0;
    while (builder.subject().exists(strided_container_name_)) {
        strided_container_name_ = "__" + indvar->get_name() + "_orig_" + std::to_string(suffix++) + "__";
    }

    // Add the container with the same type as the induction variable
    auto& indvar_type = builder.subject().type(indvar->get_name());
    builder.add_container(strided_container_name_, indvar_type);

    auto strided_var = symbolic::symbol(strided_container_name_);

    // Update the loop parameters
    builder.update_loop(loop_, indvar, new_condition, new_init, new_update);

    // Replace all uses of indvar in loop body with the strided variable
    loop_.root().replace(indvar, strided_var);

    // Add an empty block before the first child to set the strided variable in the transition
    if (loop_.root().size() > 0) {
        auto& first_child = loop_.root().at(0).first;
        builder.add_block_before(loop_.root(), first_child, control_flow::Assignments{{strided_var, strided_expr}});
    } else {
        builder.add_block(loop_.root(), control_flow::Assignments{{strided_var, strided_expr}});
    }

    analysis_manager.invalidate_all();
}

void LoopUnitStride::to_json(nlohmann::json& j) const {
    std::string loop_type = "for";
    if (dynamic_cast<const structured_control_flow::Map*>(&loop_)) {
        loop_type = "map";
    }

    j["transformation_type"] = this->name();
    j["subgraph"] = {{"0", {{"element_id", loop_.element_id()}, {"type", loop_type}}}};
}

LoopUnitStride LoopUnitStride::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& j) {
    auto loop_id = j["subgraph"]["0"]["element_id"].get<size_t>();

    auto element = builder.find_element_by_id(loop_id);
    if (element == nullptr) {
        throw std::runtime_error("LoopUnitStride: Element with ID " + std::to_string(loop_id) + " not found.");
    }

    auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);
    if (loop == nullptr) {
        throw std::runtime_error("LoopUnitStride: Element with ID " + std::to_string(loop_id) + " is not a loop.");
    }

    return LoopUnitStride(*loop);
}

std::string LoopUnitStride::strided_container_name() const { return strided_container_name_; }

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/loop_unit_stride.h"
2
3	#include <stdexcept>
4
5	#include "sdfg/builder/structured_sdfg_builder.h"
6	#include "sdfg/structured_control_flow/map.h"
7	#include "sdfg/symbolic/symbolic.h"
8	#include "sdfg/types/scalar.h"
9
10	/**
11	* Loop Unit Stride Transformation Implementation
12	*
13	* This transformation converts a loop with non-unit stride to unit stride
14	* using symbolic substitution on the condition. Direction is preserved.
15	*
16	* Precondition: init == 0 (apply LoopShift first if needed)
17	*
18	* Algorithm:
19	* 1. Verify init == 0 and stride != 1 and stride != -1
20	* 2. Compute strided expression: strided_expr = \|stride\| * i
21	* 3. Substitute indvar with strided_expr in the condition
22	* 4. Create new loop: for i = 0; cond(strided_expr); i++ or i--
23	* 5. Add assignment: __i_orig__ = strided_expr
24	* 6. Replace all uses of indvar with __i_orig__
25	*
26	* Example (positive stride s = 2):
27	* Original: for (i = 0; i < 8; i += 2) // iterations: 0, 2, 4, 6
28	* After: for (i = 0; 2*i < 8; i++)
29	* __i_orig__ = 2 * i
30	*
31	* Example (negative stride s = -2):
32	* Original: for (i = 0; -10 < i; i -= 2) // iterations: 0, -2, -4, -6, -8
33	* After: for (i = 0; -10 < 2*i; i--) // Note: \|stride\| used, direction preserved
34	* __i_orig__ = 2 * i // i' = 0, -1, -2, -3, -4 -> 0, -2, -4, -6, -8
35	*
36	*/
37
38	namespace sdfg {
39	namespace transformations {
40
41	LoopUnitStride::LoopUnitStride(structured_control_flow::StructuredLoop& loop) : loop_(loop) {}	11✔
42
43	std::string LoopUnitStride::name() const { return "LoopUnitStride"; }	2✔
44
45	bool LoopUnitStride::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	10✔
46	// Require init == 0 (apply LoopShift first)
47	if (!symbolic::eq(loop_.init(), symbolic::zero())) {	10✔
48	return false;	2✔
49	}	2✔
50
51	// Check for non-unit stride
52	auto stride = loop_.stride();	8✔
53	if (stride.is_null()) {	8✔
NEW 54	return false;	×
NEW 55	}	×
56
57	int stride_val = stride->as_int();	8✔
58	if (stride_val == 1 \|\| stride_val == -1) {	8✔
59	// Already unit stride, nothing to do
60	// Use LoopRotate for stride = -1
61	return false;	1✔
62	}	1✔
63
64	if (stride_val == 0) {	7✔
65	// Zero stride is invalid
NEW 66	return false;	×
NEW 67	}	×
68
69	return true;	7✔
70	}	7✔
71
72	void LoopUnitStride::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	6✔
73	auto indvar = loop_.indvar();	6✔
74	auto old_condition = loop_.condition();	6✔
75	auto stride = loop_.stride();	6✔
76	int stride_val = stride->as_int();	6✔
77	bool positive = stride_val > 0;	6✔
78	int stride_val_abs = std::abs(stride_val);	6✔
79
80	// Compute the strided expression: stride * i
81	// (init is guaranteed to be 0 by can_be_applied)
82	auto strided_expr = symbolic::mul(symbolic::integer(stride_val_abs), indvar);	6✔
83
84	// New loop parameters:
85	// - init = 0
86	// - condition = old_condition with indvar substituted by strided_expr
87	// - update = i + 1 or i - 1
88	auto new_init = symbolic::zero();	6✔
89	auto new_condition = symbolic::subs(old_condition, indvar, strided_expr);	6✔
90	auto new_update = positive ? symbolic::add(indvar, symbolic::one()) : symbolic::sub(indvar, symbolic::one());	6✔
91
92	// Create a new container for the strided (original) value
93	strided_container_name_ = "__" + indvar->get_name() + "_orig__";	6✔
94
95	// Find a unique name if it already exists
96	int suffix = 0;	6✔
97	while (builder.subject().exists(strided_container_name_)) {	6✔
NEW 98	strided_container_name_ = "__" + indvar->get_name() + "_orig_" + std::to_string(suffix++) + "__";	×
NEW 99	}	×
100
101	// Add the container with the same type as the induction variable
102	auto& indvar_type = builder.subject().type(indvar->get_name());	6✔
103	builder.add_container(strided_container_name_, indvar_type);	6✔
104
105	auto strided_var = symbolic::symbol(strided_container_name_);	6✔
106
107	// Update the loop parameters
108	builder.update_loop(loop_, indvar, new_condition, new_init, new_update);	6✔
109
110	// Replace all uses of indvar in loop body with the strided variable
111	loop_.root().replace(indvar, strided_var);	6✔
112
113	// Add an empty block before the first child to set the strided variable in the transition
114	if (loop_.root().size() > 0) {	6✔
115	auto& first_child = loop_.root().at(0).first;	6✔
116	builder.add_block_before(loop_.root(), first_child, control_flow::Assignments{{strided_var, strided_expr}});	6✔
117	} else {	6✔
NEW 118	builder.add_block(loop_.root(), control_flow::Assignments{{strided_var, strided_expr}});	×
NEW 119	}	×
120
121	analysis_manager.invalidate_all();	6✔
122	}	6✔
123
124	void LoopUnitStride::to_json(nlohmann::json& j) const {	1✔
125	std::string loop_type = "for";	1✔
126	if (dynamic_cast<const structured_control_flow::Map*>(&loop_)) {	1✔
NEW 127	loop_type = "map";	×
NEW 128	}	×
129
130	j["transformation_type"] = this->name();	1✔
131	j["subgraph"] = {{"0", {{"element_id", loop_.element_id()}, {"type", loop_type}}}};	1✔
132	}	1✔
133
134	LoopUnitStride LoopUnitStride::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& j) {	1✔
135	auto loop_id = j["subgraph"]["0"]["element_id"].get<size_t>();	1✔
136
137	auto element = builder.find_element_by_id(loop_id);	1✔
138	if (element == nullptr) {	1✔
NEW 139	throw std::runtime_error("LoopUnitStride: Element with ID " + std::to_string(loop_id) + " not found.");	×
NEW 140	}	×
141
142	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	1✔
143	if (loop == nullptr) {	1✔
NEW 144	throw std::runtime_error("LoopUnitStride: Element with ID " + std::to_string(loop_id) + " is not a loop.");	×
NEW 145	}	×
146
147	return LoopUnitStride(*loop);	1✔
148	}	1✔
149
150	std::string LoopUnitStride::strided_container_name() const { return strided_container_name_; }	6✔
151
152	} // namespace transformations
153	} // namespace sdfg

daisytuner / docc / 23953339753

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