28851442347

Committed 07 Jul 2026 08:09AM UTC coverage: 62.959% (+1.3%) from 61.644%

Build # 28851442347

Build Type

Pull #810

github

Committed by

web-flow

Commit Message

Merge 768a26f80 into e7f8bfb2e

Pull Request Pull Request #810: Add DOCC_REUSE_SOURCES envar to recompile the shared library from locally edited sources

Coverage Stats

37 of 46 new or added lines in 1 file covered. (80.43%)

3687 existing lines in 112 files now uncovered.

40560 of 64423 relevant lines covered (62.96%)

963.15 hits per line

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

86.11

/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}});
    }

    // Reconstruct original indvar value after loop exit
    // After loop, indvar holds transformed final value; we restore: indvar = |stride| * indvar
    auto* parent = dynamic_cast<structured_control_flow::Sequence*>(loop_.get_parent());
    if (parent) {
        builder.add_block_after(*parent, loop_, {{indvar, strided_expr}}, loop_.debug_info());
    }
}

void LoopUnitStride::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();
    j["parameters"] = nlohmann::json::object();

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

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) {}	23✔
42
43	std::string LoopUnitStride::name() const { return "LoopUnitStride"; }	2✔
44
45	bool LoopUnitStride::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	22✔
46	// Require init == 0 (apply LoopShift first)
47	if (!symbolic::eq(loop_.init(), symbolic::zero())) {	22✔
48	return false;	2✔
49	}	2✔
50
51	// Check for non-unit stride
52	auto stride = loop_.stride();	20✔
53	if (stride.is_null()) {	20✔
UNCOV 54	return false;	×
55	}	×
56
57	int stride_val = stride->as_int();	20✔
58	if (stride_val == 1 \|\| stride_val == -1) {	20✔
59	// Already unit stride, nothing to do
60	// Use LoopRotate for stride = -1
61	return false;	5✔
62	}	5✔
63
64	if (stride_val == 0) {	15✔
65	// Zero stride is invalid
UNCOV 66	return false;	×
67	}	×
68
69	return true;	15✔
70	}	15✔
71
72	void LoopUnitStride::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	14✔
73	auto indvar = loop_.indvar();	14✔
74	auto old_condition = loop_.condition();	14✔
75	auto stride = loop_.stride();	14✔
76	int stride_val = stride->as_int();	14✔
77	bool positive = stride_val > 0;	14✔
78	int stride_val_abs = std::abs(stride_val);	14✔
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);	14✔
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();	14✔
89	auto new_condition = symbolic::subs(old_condition, indvar, strided_expr);	14✔
90	auto new_update = positive ? symbolic::add(indvar, symbolic::one()) : symbolic::sub(indvar, symbolic::one());	14✔
91
92	// Create a new container for the strided (original) value
93	strided_container_name_ = "__" + indvar->get_name() + "_orig__";	14✔
94
95	// Find a unique name if it already exists
96	int suffix = 0;	14✔
97	while (builder.subject().exists(strided_container_name_)) {	17✔
98	strided_container_name_ = "__" + indvar->get_name() + "_orig_" + std::to_string(suffix++) + "__";	3✔
99	}	3✔
100
101	// Add the container with the same type as the induction variable
102	auto& indvar_type = builder.subject().type(indvar->get_name());	14✔
103	builder.add_container(strided_container_name_, indvar_type);	14✔
104
105	auto strided_var = symbolic::symbol(strided_container_name_);	14✔
106
107	// Update the loop parameters
108	builder.update_loop(loop_, indvar, new_condition, new_init, new_update);	14✔
109
110	// Replace all uses of indvar in loop body with the strided variable
111	loop_.root().replace(indvar, strided_var);	14✔
112
113	// Add an empty block before the first child to set the strided variable in the transition
114	if (loop_.root().size() > 0) {	14✔
115	auto& first_child = loop_.root().at(0).first;	14✔
116	builder.add_block_before(loop_.root(), first_child, control_flow::Assignments{{strided_var, strided_expr}});	14✔
117	} else {	14✔
UNCOV 118	builder.add_block(loop_.root(), control_flow::Assignments{{strided_var, strided_expr}});	×
119	}	×
120
121	// Reconstruct original indvar value after loop exit
122	// After loop, indvar holds transformed final value; we restore: indvar = \|stride\| * indvar
123	auto* parent = dynamic_cast<structured_control_flow::Sequence*>(loop_.get_parent());	14✔
124	if (parent) {	14✔
125	builder.add_block_after(*parent, loop_, {{indvar, strided_expr}}, loop_.debug_info());	14✔
126	}	14✔
127	}	14✔
128
129	void LoopUnitStride::to_json(nlohmann::json& j) const {	1✔
130	j["transformation_type"] = this->name();	1✔
131	j["parameters"] = nlohmann::json::object();	1✔
132
133	serializer::JSONSerializer ser_flat(false);	1✔
134	j["subgraph"] = nlohmann::json::object();	1✔
135	j["subgraph"]["0"] = nlohmann::json::object();	1✔
136	ser_flat.serialize_node(j["subgraph"]["0"], loop_);	1✔
137	}	1✔
138
139	LoopUnitStride LoopUnitStride::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& j) {	1✔
140	auto loop_id = j["subgraph"]["0"]["element_id"].get<size_t>();	1✔
141
142	auto element = builder.find_element_by_id(loop_id);	1✔
143	if (element == nullptr) {	1✔
UNCOV 144	throw std::runtime_error("LoopUnitStride: Element with ID " + std::to_string(loop_id) + " not found.");	×
145	}	×
146
147	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	1✔
148	if (loop == nullptr) {	1✔
UNCOV 149	throw std::runtime_error("LoopUnitStride: Element with ID " + std::to_string(loop_id) + " is not a loop.");	×
150	}	×
151
152	return LoopUnitStride(*loop);	1✔
153	}	1✔
154
155	std::string LoopUnitStride::strided_container_name() const { return strided_container_name_; }	6✔
156
157	} // namespace transformations
158	} // namespace sdfg

daisytuner / docc / 28851442347

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