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

86.3

/opt/src/transformations/loop_rotate.cpp

#include "sdfg/transformations/loop_rotate.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 Rotate Transformation Implementation
 *
 * This transformation converts a loop with negative stride to positive stride.
 *
 * Algorithm:
 * 1. Extract the lower bound from the loop condition (canonical_bound_lower)
 * 2. Compute new loop parameters:
 *    - new_init = lower_bound + 1 (start just above the lower bound)
 *    - new_condition = indvar < old_init + 1 (go up to but not including old_init + 1)
 *    - new_update = indvar + 1 (positive unit stride)
 * 3. Create a container for the rotated index value
 * 4. Add assignment: __i_orig__ = old_init + new_init - indvar
 * 5. Replace all uses of indvar in body with __i_orig__
 *
 * Mathematical derivation:
 * Original: i = init, init-1, ..., bound+1 (stride = -1, condition: bound < i)
 * After: i' = bound+1, bound+2, ..., init (stride = +1, condition: i' < init+1)
 * Mapping: original_i = init + (bound+1) - i' = init + new_init - i'
 */

namespace sdfg {
namespace transformations {

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

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

bool LoopRotate::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    // Check for negative unit stride
    auto stride = loop_.stride();
    if (stride.is_null()) {
        return false;
    }
    if (stride->as_int() != -1) {
        // Only support stride == -1 for now
        return false;
    }

    // Check that we can extract the lower bound
    auto lower_bound = loop_.canonical_bound_lower();
    if (lower_bound.is_null()) {
        return false;
    }

    return true;
}

void LoopRotate::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto indvar = loop_.indvar();
    auto old_init = loop_.init();

    // Get lower bound (exclusive): condition is "bound < indvar"
    // So the last valid value is bound + 1
    auto lower_bound = loop_.canonical_bound_lower();

    // New init: start at lower_bound + 1
    auto new_init = symbolic::add(lower_bound, symbolic::one());
    new_init = symbolic::expand(new_init);
    new_init = symbolic::simplify(new_init);

    // New condition: indvar < old_init + 1
    auto new_rhs = symbolic::add(old_init, symbolic::one());
    new_rhs = symbolic::expand(new_rhs);
    new_rhs = symbolic::simplify(new_rhs);
    auto new_condition = symbolic::Lt(indvar, new_rhs);

    // New update: indvar + 1 (positive unit stride)
    auto new_update = symbolic::add(indvar, symbolic::one());

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

    // Find a unique name if it already exists
    int suffix = 0;
    while (builder.subject().exists(rotated_container_name_)) {
        rotated_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(rotated_container_name_, indvar_type);

    auto rotated_var = symbolic::symbol(rotated_container_name_);

    // Compute the rotated value: original_i = old_init + new_init - indvar
    // This maps i' = new_init to original_i = old_init
    //           i' = new_init+1 to original_i = old_init - 1
    //           etc.
    auto rotated_value = symbolic::sub(symbolic::add(old_init, new_init), indvar);
    rotated_value = symbolic::expand(rotated_value);
    rotated_value = symbolic::simplify(rotated_value);

    // 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 rotated variable
    loop_.root().replace(indvar, rotated_var);

    // Add an empty block before the first child to set the rotated 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{{rotated_var, rotated_value}});
    } else {
        builder.add_block(loop_.root(), control_flow::Assignments{{rotated_var, rotated_value}});
    }

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

void LoopRotate::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_);
}

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

    auto element = builder.find_element_by_id(loop_id);
    if (element == nullptr) {
        throw std::runtime_error("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("Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop.");
    }

    return LoopRotate(*loop);
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/loop_rotate.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 Rotate Transformation Implementation
12	*
13	* This transformation converts a loop with negative stride to positive stride.
14	*
15	* Algorithm:
16	* 1. Extract the lower bound from the loop condition (canonical_bound_lower)
17	* 2. Compute new loop parameters:
18	* - new_init = lower_bound + 1 (start just above the lower bound)
19	* - new_condition = indvar < old_init + 1 (go up to but not including old_init + 1)
20	* - new_update = indvar + 1 (positive unit stride)
21	* 3. Create a container for the rotated index value
22	* 4. Add assignment: __i_orig__ = old_init + new_init - indvar
23	* 5. Replace all uses of indvar in body with __i_orig__
24	*
25	* Mathematical derivation:
26	* Original: i = init, init-1, ..., bound+1 (stride = -1, condition: bound < i)
27	* After: i' = bound+1, bound+2, ..., init (stride = +1, condition: i' < init+1)
28	* Mapping: original_i = init + (bound+1) - i' = init + new_init - i'
29	*/
30
31	namespace sdfg {
32	namespace transformations {
33
34	LoopRotate::LoopRotate(structured_control_flow::StructuredLoop& loop) : loop_(loop) {}	20✔
35
36	std::string LoopRotate::name() const { return "LoopRotate"; }	2✔
37
38	bool LoopRotate::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	18✔
39	// Check for negative unit stride
40	auto stride = loop_.stride();	18✔
41	if (stride.is_null()) {	18✔
42	return false;	×
43	}	×
44	if (stride->as_int() != -1) {	18✔
45	// Only support stride == -1 for now
46	return false;	10✔
47	}	10✔
48
49	// Check that we can extract the lower bound
50	auto lower_bound = loop_.canonical_bound_lower();	8✔
51	if (lower_bound.is_null()) {	8✔
52	return false;	×
53	}	×
54
55	return true;	8✔
56	}	8✔
57
58	void LoopRotate::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	8✔
59	auto indvar = loop_.indvar();	8✔
60	auto old_init = loop_.init();	8✔
61
62	// Get lower bound (exclusive): condition is "bound < indvar"
63	// So the last valid value is bound + 1
64	auto lower_bound = loop_.canonical_bound_lower();	8✔
65
66	// New init: start at lower_bound + 1
67	auto new_init = symbolic::add(lower_bound, symbolic::one());	8✔
68	new_init = symbolic::expand(new_init);	8✔
69	new_init = symbolic::simplify(new_init);	8✔
70
71	// New condition: indvar < old_init + 1
72	auto new_rhs = symbolic::add(old_init, symbolic::one());	8✔
73	new_rhs = symbolic::expand(new_rhs);	8✔
74	new_rhs = symbolic::simplify(new_rhs);	8✔
75	auto new_condition = symbolic::Lt(indvar, new_rhs);	8✔
76
77	// New update: indvar + 1 (positive unit stride)
78	auto new_update = symbolic::add(indvar, symbolic::one());	8✔
79
80	// Create a new container for the rotated (original) value
81	rotated_container_name_ = "__" + indvar->get_name() + "_orig__";	8✔
82
83	// Find a unique name if it already exists
84	int suffix = 0;	8✔
85	while (builder.subject().exists(rotated_container_name_)) {	10✔
86	rotated_container_name_ = "__" + indvar->get_name() + "_orig_" + std::to_string(suffix++) + "__";	2✔
87	}	2✔
88
89	// Add the container with the same type as the induction variable
90	auto& indvar_type = builder.subject().type(indvar->get_name());	8✔
91	builder.add_container(rotated_container_name_, indvar_type);	8✔
92
93	auto rotated_var = symbolic::symbol(rotated_container_name_);	8✔
94
95	// Compute the rotated value: original_i = old_init + new_init - indvar
96	// This maps i' = new_init to original_i = old_init
97	// i' = new_init+1 to original_i = old_init - 1
98	// etc.
99	auto rotated_value = symbolic::sub(symbolic::add(old_init, new_init), indvar);	8✔
100	rotated_value = symbolic::expand(rotated_value);	8✔
101	rotated_value = symbolic::simplify(rotated_value);	8✔
102
103	// Update the loop parameters
104	builder.update_loop(loop_, indvar, new_condition, new_init, new_update);	8✔
105
106	// Replace all uses of indvar in loop body with the rotated variable
107	loop_.root().replace(indvar, rotated_var);	8✔
108
109	// Add an empty block before the first child to set the rotated variable in the transition
110	if (loop_.root().size() > 0) {	8✔
111	auto& first_child = loop_.root().at(0).first;	8✔
112	builder.add_block_before(loop_.root(), first_child, control_flow::Assignments{{rotated_var, rotated_value}});	8✔
113	} else {	8✔
114	builder.add_block(loop_.root(), control_flow::Assignments{{rotated_var, rotated_value}});	×
115	}	×
116
117	// Reconstruct original indvar value after loop exit
118	// After loop, indvar holds transformed final value; we restore: indvar = old_init + new_init - indvar
119	auto parent_node = loop_.get_parent();	8✔
120	auto* parent = dynamic_cast<structured_control_flow::Sequence*>(parent_node);	8✔
121	if (parent) {	8✔
122	builder.add_block_after(*parent, loop_, {{indvar, rotated_value}}, loop_.debug_info());	8✔
123	}	8✔
124	}	8✔
125
126	void LoopRotate::to_json(nlohmann::json& j) const {	1✔
127	j["transformation_type"] = this->name();	1✔
128	j["parameters"] = nlohmann::json::object();	1✔
129
130	serializer::JSONSerializer ser_flat(false);	1✔
131	j["subgraph"] = nlohmann::json::object();	1✔
132	j["subgraph"]["0"] = nlohmann::json::object();	1✔
133	ser_flat.serialize_node(j["subgraph"]["0"], loop_);	1✔
134	}	1✔
135
136	LoopRotate LoopRotate::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	1✔
137	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	1✔
138
139	auto element = builder.find_element_by_id(loop_id);	1✔
140	if (element == nullptr) {	1✔
UNCOV 141	throw std::runtime_error("Element with ID " + std::to_string(loop_id) + " not found.");	×
142	}	×
143
144	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	1✔
145	if (loop == nullptr) {	1✔
UNCOV 146	throw std::runtime_error("Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop.");	×
147	}	×
148
149	return LoopRotate(*loop);	1✔
150	}	1✔
151
152	} // namespace transformations
153	} // 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