23983017072

Committed 04 Apr 2026 04:35PM UTC coverage: 64.774% (+0.04%) from 64.736%

Build # 23983017072

Build Type

Pull #645

github

Committed by

web-flow

Commit Message

Merge e8d587946 into affb8e1db

Pull Request Pull Request #645: Handles final value of loops when normalizing

Coverage Stats

62 of 88 new or added lines in 6 files covered. (70.45%)

29164 of 45024 relevant lines covered (64.77%)

532.48 hits per line

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

42.11

/opt/src/transformations/loop_indvar_finalize.cpp

#include "sdfg/transformations/loop_indvar_finalize.h"

#include <stdexcept>

#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/symbolic/symbolic.h"

/**
 * Loop Indvar Finalize Transformation Implementation
 *
 * For a normalized loop, computes the closed-form final value of the original
 * induction variable and adds a block right after the loop with this assignment.
 *
 * closed_form = num_iterations
 *
 * SymbolPropagation will then propagate this value into any subsequent blocks
 * that reference the induction variable, breaking WAR dependencies.
 */

namespace sdfg {
namespace transformations {

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

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

bool LoopIndvarFinalize::
    can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    // Loop must be in normal form
    if (!loop_.is_loop_normal_form()) {
        return false;
    }

    return true;
}

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

    // Use max(0, num_iterations) to handle the case where the loop doesn't execute
    // (when bound <= 0, the loop body is skipped and indvar stays at 0)
    auto closed_form = symbolic::simplify(symbolic::max(symbolic::zero(), loop_.num_iterations()));

    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    auto parent_node = scope_analysis.parent_scope(&loop_);
    auto* parent = dynamic_cast<structured_control_flow::Sequence*>(parent_node);

    // Add block with closed-form assignment right after the loop
    // SymbolPropagation will propagate into subsequent blocks
    builder.add_block_after(*parent, loop_, {{indvar, closed_form}}, loop_.debug_info());

    analysis_manager.invalidate_all();
}

void LoopIndvarFinalize::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"] = {};
}

LoopIndvarFinalize LoopIndvarFinalize::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) {
        throw std::runtime_error("LoopIndvarFinalize: Element not found");
    }

    auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);
    if (!loop) {
        throw std::runtime_error("LoopIndvarFinalize: Element is not a loop");
    }

    return LoopIndvarFinalize(*loop);
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/loop_indvar_finalize.h"
2
3	#include <stdexcept>
4
5	#include "sdfg/analysis/scope_analysis.h"
6	#include "sdfg/builder/structured_sdfg_builder.h"
7	#include "sdfg/structured_control_flow/block.h"
8	#include "sdfg/structured_control_flow/map.h"
9	#include "sdfg/symbolic/symbolic.h"
10
11	/**
12	* Loop Indvar Finalize Transformation Implementation
13	*
14	* For a normalized loop, computes the closed-form final value of the original
15	* induction variable and adds a block right after the loop with this assignment.
16	*
17	* closed_form = num_iterations
18	*
19	* SymbolPropagation will then propagate this value into any subsequent blocks
20	* that reference the induction variable, breaking WAR dependencies.
21	*/
22
23	namespace sdfg {
24	namespace transformations {
25
26	LoopIndvarFinalize::LoopIndvarFinalize(structured_control_flow::StructuredLoop& loop) : loop_(loop) {}	14✔
27
NEW 28	std::string LoopIndvarFinalize::name() const { return "LoopIndvarFinalize"; }	×
29
30	bool LoopIndvarFinalize::
31	can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	14✔
32	// Loop must be in normal form
33	if (!loop_.is_loop_normal_form()) {	14✔
34	return false;	1✔
35	}	1✔
36
37	return true;	13✔
38	}	14✔
39
40	void LoopIndvarFinalize::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	13✔
41	auto indvar = loop_.indvar();	13✔
42
43	// Use max(0, num_iterations) to handle the case where the loop doesn't execute
44	// (when bound <= 0, the loop body is skipped and indvar stays at 0)
45	auto closed_form = symbolic::simplify(symbolic::max(symbolic::zero(), loop_.num_iterations()));	13✔
46
47	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	13✔
48	auto parent_node = scope_analysis.parent_scope(&loop_);	13✔
49	auto* parent = dynamic_cast<structured_control_flow::Sequence*>(parent_node);	13✔
50
51	// Add block with closed-form assignment right after the loop
52	// SymbolPropagation will propagate into subsequent blocks
53	builder.add_block_after(*parent, loop_, {{indvar, closed_form}}, loop_.debug_info());	13✔
54
55	analysis_manager.invalidate_all();	13✔
56	}	13✔
57
NEW 58	void LoopIndvarFinalize::to_json(nlohmann::json& j) const {	×
NEW 59	std::string loop_type = "for";	×
NEW 60	if (dynamic_cast<const structured_control_flow::Map*>(&loop_)) {	×
NEW 61	loop_type = "map";	×
NEW 62	}	×
63
NEW 64	j["transformation_type"] = this->name();	×
NEW 65	j["subgraph"] = {{"0", {{"element_id", loop_.element_id()}, {"type", loop_type}}}};	×
NEW 66	j["parameters"] = {};	×
NEW 67	}	×
68
NEW 69	LoopIndvarFinalize LoopIndvarFinalize::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& j) {	×
NEW 70	auto loop_id = j["subgraph"]["0"]["element_id"].get<size_t>();	×
71
NEW 72	auto element = builder.find_element_by_id(loop_id);	×
NEW 73	if (!element) {	×
NEW 74	throw std::runtime_error("LoopIndvarFinalize: Element not found");	×
NEW 75	}	×
76
NEW 77	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	×
NEW 78	if (!loop) {	×
NEW 79	throw std::runtime_error("LoopIndvarFinalize: Element is not a loop");	×
NEW 80	}	×
81
NEW 82	return LoopIndvarFinalize(*loop);	×
NEW 83	}	×
84
85	} // namespace transformations
86	} // namespace sdfg

daisytuner / docc / 23983017072

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