23949469504

Committed 03 Apr 2026 02:21PM UTC coverage: 64.695% (-0.03%) from 64.723%

Build # 23949469504

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #638 from daisytuner/loop-shift

adds LoopShift transformation

Coverage Stats

32 of 64 new or added lines in 2 files covered. (50.0%)

3 existing lines in 1 file now uncovered.

28783 of 44490 relevant lines covered (64.7%)

471.38 hits per line

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

49.21

/opt/src/transformations/loop_shift.cpp

#include "sdfg/transformations/loop_shift.h"

#include <stdexcept>

#include "sdfg/analysis/loop_analysis.h"
#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 Shift Transformation Implementation
 *
 * This transformation shifts a loop's iteration space to start from a different
 * initial value.
 *
 * Algorithm:
 * 1. Compute the shift amount: shift = old_init - target_init
 * 2. Create a new scalar container to hold the original iteration value
 * 3. Add an empty block at the beginning of the loop body
 * 4. Add assignment in the block's transition: shifted_var = indvar + shift
 * 5. Update loop bounds: init = target_init, condition adjusted
 * 6. User should run SymbolPropagation afterwards to propagate the assignment
 */

namespace sdfg {
namespace transformations {

LoopShift::LoopShift(structured_control_flow::StructuredLoop& loop) : loop_(loop), offset_(loop.init()) {}

LoopShift::LoopShift(structured_control_flow::StructuredLoop& loop, const symbolic::Expression& offset)
    : loop_(loop), offset_(offset) {}

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

bool LoopShift::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    for (auto& atom : symbolic::atoms(offset_)) {
        if (symbolic::eq(atom, loop_.indvar())) {
            // Offset cannot contain the induction variable itself
            return false;
        }
    }
    return true;
}

void LoopShift::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    if (symbolic::eq(offset_, symbolic::zero())) {
        // No shift needed
        return;
    }

    auto indvar = loop_.indvar();
    auto old_init = loop_.init();
    auto old_condition = loop_.condition();
    auto old_update = loop_.update();

    // Compute the new init: new_init = old_init - offset
    auto new_init = symbolic::sub(old_init, offset_);

    // Create a new container for the shifted (original) value
    // Use a unique name based on the original indvar
    shifted_container_name_ = "__" + indvar->get_name() + "_orig__";

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

    auto shifted_var = symbolic::symbol(shifted_container_name_);
    auto shifted_value = symbolic::add(indvar, offset_);

    // We use symbolic substitution: replace old indvar with (indvar + shift) in condition
    auto new_condition = symbolic::subs(old_condition, indvar, symbolic::add(indvar, offset_));

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

    // Update the body to reference the original value via the new container
    loop_.root().replace(indvar, shifted_var);

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

    analysis_manager.invalidate_all();
}

void LoopShift::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}}}};
    j["parameters"] = {{"offset", offset_->__str__()}};
}

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

    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.");
    }

    auto offset = symbolic::parse(offset_str);
    return LoopShift(*loop, offset);
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/loop_shift.h"
2
3	#include <stdexcept>
4
5	#include "sdfg/analysis/loop_analysis.h"
6	#include "sdfg/builder/structured_sdfg_builder.h"
7	#include "sdfg/structured_control_flow/map.h"
8	#include "sdfg/symbolic/symbolic.h"
9	#include "sdfg/types/scalar.h"
10
11	/**
12	* Loop Shift Transformation Implementation
13	*
14	* This transformation shifts a loop's iteration space to start from a different
15	* initial value.
16	*
17	* Algorithm:
18	* 1. Compute the shift amount: shift = old_init - target_init
19	* 2. Create a new scalar container to hold the original iteration value
20	* 3. Add an empty block at the beginning of the loop body
21	* 4. Add assignment in the block's transition: shifted_var = indvar + shift
22	* 5. Update loop bounds: init = target_init, condition adjusted
23	* 6. User should run SymbolPropagation afterwards to propagate the assignment
24	*/
25
26	namespace sdfg {
27	namespace transformations {
28
29	LoopShift::LoopShift(structured_control_flow::StructuredLoop& loop) : loop_(loop), offset_(loop.init()) {}	3✔
30
31	LoopShift::LoopShift(structured_control_flow::StructuredLoop& loop, const symbolic::Expression& offset)
32	: loop_(loop), offset_(offset) {}	1✔
33
NEW 34	std::string LoopShift::name() const { return "LoopShift"; }	×
35
36	bool LoopShift::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	4✔
37	for (auto& atom : symbolic::atoms(offset_)) {	4✔
NEW 38	if (symbolic::eq(atom, loop_.indvar())) {	×
39	// Offset cannot contain the induction variable itself
NEW 40	return false;	×
NEW 41	}	×
NEW 42	}	×
43	return true;	4✔
44	}	4✔
45
46	void LoopShift::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	4✔
47	if (symbolic::eq(offset_, symbolic::zero())) {	4✔
48	// No shift needed
49	return;	1✔
50	}	1✔
51
52	auto indvar = loop_.indvar();	3✔
53	auto old_init = loop_.init();	3✔
54	auto old_condition = loop_.condition();	3✔
55	auto old_update = loop_.update();	3✔
56
57	// Compute the new init: new_init = old_init - offset
58	auto new_init = symbolic::sub(old_init, offset_);	3✔
59
60	// Create a new container for the shifted (original) value
61	// Use a unique name based on the original indvar
62	shifted_container_name_ = "__" + indvar->get_name() + "_orig__";	3✔
63
64	// Find a unique name if it already exists
65	int suffix = 0;	3✔
66	while (builder.subject().exists(shifted_container_name_)) {	3✔
NEW 67	shifted_container_name_ = "__" + indvar->get_name() + "_orig_" + std::to_string(suffix++) + "__";	×
NEW 68	}	×
69
70	// Add the container with the same type as the induction variable
71	auto& indvar_type = builder.subject().type(indvar->get_name());	3✔
72	builder.add_container(shifted_container_name_, indvar_type);	3✔
73
74	auto shifted_var = symbolic::symbol(shifted_container_name_);	3✔
75	auto shifted_value = symbolic::add(indvar, offset_);	3✔
76
77	// We use symbolic substitution: replace old indvar with (indvar + shift) in condition
78	auto new_condition = symbolic::subs(old_condition, indvar, symbolic::add(indvar, offset_));	3✔
79
80	// Update the loop
81	builder.update_loop(loop_, indvar, new_condition, new_init, old_update);	3✔
82
83	// Update the body to reference the original value via the new container
84	loop_.root().replace(indvar, shifted_var);	3✔
85
86	// Add an empty block before the first child to set the shifted variable in the transition
87	if (loop_.root().size() > 0) {	3✔
88	auto& first_child = loop_.root().at(0).first;	3✔
89	builder.add_block_before(loop_.root(), first_child, control_flow::Assignments{{shifted_var, shifted_value}});	3✔
90	} else {	3✔
NEW 91	builder.add_block(loop_.root(), control_flow::Assignments{{shifted_var, shifted_value}});	×
NEW 92	}	×
93
94	analysis_manager.invalidate_all();	3✔
95	}	3✔
96
NEW 97	void LoopShift::to_json(nlohmann::json& j) const {	×
NEW 98	std::string loop_type = "for";	×
NEW 99	if (dynamic_cast<const structured_control_flow::Map*>(&loop_)) {	×
NEW 100	loop_type = "map";	×
NEW 101	}	×
102
NEW 103	j["transformation_type"] = this->name();	×
NEW 104	j["subgraph"] = {{"0", {{"element_id", loop_.element_id()}, {"type", loop_type}}}};	×
NEW 105	j["parameters"] = {{"offset", offset_->__str__()}};	×
NEW 106	}	×
107
NEW 108	LoopShift LoopShift::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
NEW 109	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
NEW 110	auto offset_str = desc["parameters"]["offset"].get<std::string>();	×
111
NEW 112	auto element = builder.find_element_by_id(loop_id);	×
NEW 113	if (element == nullptr) {	×
NEW 114	throw std::runtime_error("Element with ID " + std::to_string(loop_id) + " not found.");	×
NEW 115	}	×
116
NEW 117	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	×
NEW 118	if (loop == nullptr) {	×
NEW 119	throw std::runtime_error("Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop.");	×
NEW 120	}	×
121
NEW 122	auto offset = symbolic::parse(offset_str);	×
NEW 123	return LoopShift(*loop, offset);	×
NEW 124	}	×
125
126	} // namespace transformations
127	} // namespace sdfg

daisytuner / docc / 23949469504

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