28814257460

Committed 06 Jul 2026 06:31PM UTC coverage: 62.928% (-0.03%) from 62.96%

Build # 28814257460

Build Type

Pull #843

github

Committed by

web-flow

Commit Message

Merge b6b7f08d9 into 95ea95f1f

Pull Request Pull Request #843: adds type_ids for Element classes and a human-readable element_type

Coverage Stats

457 of 599 new or added lines in 121 files covered. (76.29%)

5 existing lines in 3 files now uncovered.

40598 of 64515 relevant lines covered (62.93%)

977.42 hits per line

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

71.83

/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) {
    if (symbolic::eq(offset_, symbolic::zero())) {
        // No shift needed
        return false;
    }

    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) {
    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_);
    new_init = symbolic::expand(new_init);
    new_init = symbolic::simplify(new_init);

    // 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_);
    shifted_value = symbolic::expand(shifted_value);
    shifted_value = symbolic::simplify(shifted_value);

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

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

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

void LoopShift::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();
    j["parameters"] = nlohmann::json::object();
    j["parameters"] = {{"offset", offset_->__str__()}};

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

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 = dyn_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()) {}	19✔
30
31	LoopShift::LoopShift(structured_control_flow::StructuredLoop& loop, const symbolic::Expression& offset)
32	: loop_(loop), offset_(offset) {}	1✔
33
34	std::string LoopShift::name() const { return "LoopShift"; }	1✔
35
36	bool LoopShift::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	20✔
37	if (symbolic::eq(offset_, symbolic::zero())) {	20✔
38	// No shift needed
39	return false;	6✔
40	}	6✔
41
42	for (auto& atom : symbolic::atoms(offset_)) {	14✔
43	if (symbolic::eq(atom, loop_.indvar())) {	×
44	// Offset cannot contain the induction variable itself
45	return false;	×
46	}	×
47	}	×
48	return true;	14✔
49	}	14✔
50
51	void LoopShift::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	14✔
52	auto indvar = loop_.indvar();	14✔
53	auto old_init = loop_.init();	14✔
54	auto old_condition = loop_.condition();	14✔
55	auto old_update = loop_.update();	14✔
56
57	// Compute the new init: new_init = old_init - offset
58	auto new_init = symbolic::sub(old_init, offset_);	14✔
59	new_init = symbolic::expand(new_init);	14✔
60	new_init = symbolic::simplify(new_init);	14✔
61
62	// Create a new container for the shifted (original) value
63	// Use a unique name based on the original indvar
64	shifted_container_name_ = "__" + indvar->get_name() + "_orig__";	14✔
65
66	// Find a unique name if it already exists
67	int suffix = 0;	14✔
68	while (builder.subject().exists(shifted_container_name_)) {	18✔
69	shifted_container_name_ = "__" + indvar->get_name() + "_orig_" + std::to_string(suffix++) + "__";	4✔
70	}	4✔
71
72	// Add the container with the same type as the induction variable
73	auto& indvar_type = builder.subject().type(indvar->get_name());	14✔
74	builder.add_container(shifted_container_name_, indvar_type);	14✔
75
76	auto shifted_var = symbolic::symbol(shifted_container_name_);	14✔
77	auto shifted_value = symbolic::add(indvar, offset_);	14✔
78	shifted_value = symbolic::expand(shifted_value);	14✔
79	shifted_value = symbolic::simplify(shifted_value);	14✔
80
81	// We use symbolic substitution: replace old indvar with (indvar + shift) in condition
82	auto new_condition = symbolic::subs(old_condition, indvar, shifted_value);	14✔
83
84	// Update the loop
85	builder.update_loop(loop_, indvar, new_condition, new_init, old_update);	14✔
86
87	// Update the body to reference the original value via the new container
88	loop_.root().replace(indvar, shifted_var);	14✔
89
90	// Add an empty block before the first child to set the shifted variable in the transition
91	if (loop_.root().size() > 0) {	14✔
92	auto& first_child = loop_.root().at(0).first;	14✔
93	builder.add_block_before(loop_.root(), first_child, control_flow::Assignments{{shifted_var, shifted_value}});	14✔
94	} else {	14✔
95	builder.add_block(loop_.root(), control_flow::Assignments{{shifted_var, shifted_value}});	×
96	}	×
97
98	// Reconstruct original indvar value after loop exit
99	// After loop, indvar holds transformed final value; we restore: indvar = indvar + offset
100	auto parent_node = loop_.get_parent();	14✔
101	auto* parent = dyn_cast<structured_control_flow::Sequence*>(parent_node);	14✔
102	if (parent) {	14✔
103	builder.add_block_after(*parent, loop_, {{indvar, shifted_value}}, loop_.debug_info());	14✔
104	}	14✔
105	}	14✔
106
107	void LoopShift::to_json(nlohmann::json& j) const {	1✔
108	j["transformation_type"] = this->name();	1✔
109	j["parameters"] = nlohmann::json::object();	1✔
110	j["parameters"] = {{"offset", offset_->__str__()}};	1✔
111
112	serializer::JSONSerializer ser_flat(false);	1✔
113	j["subgraph"] = nlohmann::json::object();	1✔
114	j["subgraph"]["0"] = nlohmann::json::object();	1✔
115	ser_flat.serialize_node(j["subgraph"]["0"], loop_);	1✔
116	}	1✔
117
118	LoopShift LoopShift::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
119	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
120	auto offset_str = desc["parameters"]["offset"].get<std::string>();	×
121
122	auto element = builder.find_element_by_id(loop_id);	×
123	if (element == nullptr) {	×
124	throw std::runtime_error("Element with ID " + std::to_string(loop_id) + " not found.");	×
125	}	×
126
NEW 127	auto loop = dyn_cast<structured_control_flow::StructuredLoop*>(element);	×
128	if (loop == nullptr) {	×
129	throw std::runtime_error("Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop.");	×
130	}	×
131
132	auto offset = symbolic::parse(offset_str);	×
133	return LoopShift(*loop, offset);	×
134	}	×
135
136	} // namespace transformations
137	} // namespace sdfg

daisytuner / docc / 28814257460

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