28190635525

Committed 25 Jun 2026 06:08PM UTC coverage: 61.743% (+0.1%) from 61.644%

Build # 28190635525

Build Type

push

github

Committed by

web-flow

Commit Message

adds reduce as new structured loop type (#802)

* adds Reduce loop to structured loops

* extends For2Map into a general detection of reduce and map

* makes serialization of reduce backward compatible

* counts reduce as fors in loop analysis

* renames serializer for structured loops

* updates verifier

* adds support for FMA

* updates loop report to count map, reduce, for separately

* updates verifier after merge

* removes non-existent api function in tests after merge

* updates transformations to handle reduce

* adds vectorize dispatcher for reduce

* updates xfail for incorrect output

* updates go fast

* updates llvm verifier

* removes torchaudio dependency

Coverage Stats

705 of 985 new or added lines in 34 files covered. (71.57%)

5 existing lines in 4 files now uncovered.

38837 of 62901 relevant lines covered (61.74%)

978.17 hits per line

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

68.35

/opt/src/transformations/loop_split.cpp

#include "sdfg/transformations/loop_split.h"

#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/deepcopy/structured_sdfg_deep_copy.h"
#include "sdfg/structured_control_flow/for.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/symbolic/symbolic.h"

namespace sdfg {
namespace transformations {

LoopSplit::LoopSplit(structured_control_flow::StructuredLoop& loop, const symbolic::Expression& split_point)
    : loop_(loop), split_point_(split_point) {};

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

bool LoopSplit::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    // Loop must be contiguous (unit stride)
    if (!loop_.is_contiguous()) {
        return false;
    }

    // Loop must have a canonical bound (well-formed upper bound)
    auto bound = loop_.canonical_bound();
    if (bound == SymEngine::null) {
        return false;
    }

    // split_point must not be null
    if (split_point_ == SymEngine::null) {
        return false;
    }

    return true;
};

void LoopSplit::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& sdfg = builder.subject();

    auto indvar = loop_.indvar();
    auto condition = loop_.condition();
    auto init = loop_.init();
    auto update = loop_.update();
    auto bound = loop_.canonical_bound();

    // Get parent scope
    auto parent = static_cast<structured_control_flow::Sequence*>(loop_.get_parent());

    // Create the first loop (before the original): for (i = init; i < split_point && original_cond; i++)
    //
    // We conjoin the original loop condition so that downstream symbolic
    // analysis (assumptions, MLA delinearization) sees the FULL bound on the
    // in-panel iteration space, not just the split point. Without this, when
    // `split_point` may exceed the original upper bound (a runtime-dependent
    // case), the in-panel loop's effective range would be unrepresentable in
    // the symbolic model.
    auto first_condition = symbolic::And(symbolic::Lt(indvar, split_point_), condition);

    structured_control_flow::StructuredLoop* first_loop = nullptr;
    if (auto map = dynamic_cast<structured_control_flow::Map*>(&loop_)) {
        first_loop = &builder.add_map_before(
            *parent, loop_, indvar, first_condition, init, update, map->schedule_type(), {}, loop_.debug_info()
        );
    } else if (auto reduce = dynamic_cast<structured_control_flow::Reduce*>(&loop_)) {
        first_loop = &builder.add_reduce_before(
            *parent,
            loop_,
            indvar,
            first_condition,
            init,
            update,
            reduce->reductions(),
            reduce->schedule_type(),
            {},
            loop_.debug_info()
        );
    } else {
        first_loop =
            &builder.add_for_before(*parent, loop_, indvar, first_condition, init, update, {}, loop_.debug_info());
    }

    // Deep copy the original loop body into the first loop
    deepcopy::StructuredSDFGDeepCopy deep_copy(builder, first_loop->root(), loop_.root());
    deep_copy.insert();

    // Give the first loop a fresh induction variable (to avoid name collision)
    std::string new_indvar_name = builder.find_new_name(indvar->get_name());
    builder.add_container(new_indvar_name, sdfg.type(indvar->get_name()));
    first_loop->replace(indvar, symbolic::symbol(new_indvar_name));

    // Update the original loop to start at split_point: for (i = split_point; i < bound; i++)
    builder.update_loop(loop_, indvar, condition, split_point_, update);

    analysis_manager.invalidate_all();
};

void LoopSplit::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();
    j["parameters"] = nlohmann::json::object();
    j["parameters"] = {{"split_point", split_point_->__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_);
};

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

    auto element = builder.find_element_by_id(loop_id);
    if (element == nullptr) {
        throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");
    }

    auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);
    if (loop == nullptr) {
        throw InvalidTransformationDescriptionException(
            "Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop."
        );
    }

    auto split_point = symbolic::parse(split_point_str);
    return LoopSplit(*loop, split_point);
};

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/loop_split.h"
2
3	#include "sdfg/analysis/scope_analysis.h"
4	#include "sdfg/builder/structured_sdfg_builder.h"
5	#include "sdfg/deepcopy/structured_sdfg_deep_copy.h"
6	#include "sdfg/structured_control_flow/for.h"
7	#include "sdfg/structured_control_flow/map.h"
8	#include "sdfg/structured_control_flow/sequence.h"
9	#include "sdfg/symbolic/symbolic.h"
10
11	namespace sdfg {
12	namespace transformations {
13
14	LoopSplit::LoopSplit(structured_control_flow::StructuredLoop& loop, const symbolic::Expression& split_point)
15	: loop_(loop), split_point_(split_point) {};	9✔
16
17	std::string LoopSplit::name() const { return "LoopSplit"; };	3✔
18
19	bool LoopSplit::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	7✔
20	// Loop must be contiguous (unit stride)
21	if (!loop_.is_contiguous()) {	7✔
22	return false;	1✔
23	}	1✔
24
25	// Loop must have a canonical bound (well-formed upper bound)
26	auto bound = loop_.canonical_bound();	6✔
27	if (bound == SymEngine::null) {	6✔
28	return false;	×
29	}	×
30
31	// split_point must not be null
32	if (split_point_ == SymEngine::null) {	6✔
33	return false;	×
34	}	×
35
36	return true;	6✔
37	};	6✔
38
39	void LoopSplit::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	5✔
40	auto& sdfg = builder.subject();	5✔
41
42	auto indvar = loop_.indvar();	5✔
43	auto condition = loop_.condition();	5✔
44	auto init = loop_.init();	5✔
45	auto update = loop_.update();	5✔
46	auto bound = loop_.canonical_bound();	5✔
47
48	// Get parent scope
49	auto parent = static_cast<structured_control_flow::Sequence*>(loop_.get_parent());	5✔
50
51	// Create the first loop (before the original): for (i = init; i < split_point && original_cond; i++)
52	//
53	// We conjoin the original loop condition so that downstream symbolic
54	// analysis (assumptions, MLA delinearization) sees the FULL bound on the
55	// in-panel iteration space, not just the split point. Without this, when
56	// `split_point` may exceed the original upper bound (a runtime-dependent
57	// case), the in-panel loop's effective range would be unrepresentable in
58	// the symbolic model.
59	auto first_condition = symbolic::And(symbolic::Lt(indvar, split_point_), condition);	5✔
60
61	structured_control_flow::StructuredLoop* first_loop = nullptr;	5✔
62	if (auto map = dynamic_cast<structured_control_flow::Map*>(&loop_)) {	5✔
63	first_loop = &builder.add_map_before(	×
64	*parent, loop_, indvar, first_condition, init, update, map->schedule_type(), {}, loop_.debug_info()	×
65	);	×
66	} else if (auto reduce = dynamic_cast<structured_control_flow::Reduce*>(&loop_)) {	5✔
NEW 67	first_loop = &builder.add_reduce_before(	×
NEW 68	*parent,	×
NEW 69	loop_,	×
NEW 70	indvar,	×
NEW 71	first_condition,	×
NEW 72	init,	×
NEW 73	update,	×
NEW 74	reduce->reductions(),	×
NEW 75	reduce->schedule_type(),	×
NEW 76	{},	×
NEW 77	loop_.debug_info()	×
NEW 78	);	×
79	} else {	5✔
80	first_loop =	5✔
81	&builder.add_for_before(*parent, loop_, indvar, first_condition, init, update, {}, loop_.debug_info());	5✔
82	}	5✔
83
84	// Deep copy the original loop body into the first loop
85	deepcopy::StructuredSDFGDeepCopy deep_copy(builder, first_loop->root(), loop_.root());	5✔
86	deep_copy.insert();	5✔
87
88	// Give the first loop a fresh induction variable (to avoid name collision)
89	std::string new_indvar_name = builder.find_new_name(indvar->get_name());	5✔
90	builder.add_container(new_indvar_name, sdfg.type(indvar->get_name()));	5✔
91	first_loop->replace(indvar, symbolic::symbol(new_indvar_name));	5✔
92
93	// Update the original loop to start at split_point: for (i = split_point; i < bound; i++)
94	builder.update_loop(loop_, indvar, condition, split_point_, update);	5✔
95
96	analysis_manager.invalidate_all();	5✔
97	};	5✔
98
99	void LoopSplit::to_json(nlohmann::json& j) const {	2✔
100	j["transformation_type"] = this->name();	2✔
101	j["parameters"] = nlohmann::json::object();	2✔
102	j["parameters"] = {{"split_point", split_point_->__str__()}};	2✔
103
104	serializer::JSONSerializer ser_flat(false);	2✔
105	j["subgraph"] = nlohmann::json::object();	2✔
106	j["subgraph"]["0"] = nlohmann::json::object();	2✔
107	ser_flat.serialize_node(j["subgraph"]["0"], loop_);	2✔
108	};	2✔
109
110	LoopSplit LoopSplit::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	1✔
111	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	1✔
112	auto split_point_str = desc["parameters"]["split_point"].get<std::string>();	1✔
113
114	auto element = builder.find_element_by_id(loop_id);	1✔
115	if (element == nullptr) {	1✔
116	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
117	}	×
118
119	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	1✔
120	if (loop == nullptr) {	1✔
121	throw InvalidTransformationDescriptionException(	×
122	"Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop."	×
123	);	×
124	}	×
125
126	auto split_point = symbolic::parse(split_point_str);	1✔
127	return LoopSplit(*loop, split_point);	1✔
128	};	1✔
129
130	} // namespace transformations
131	} // namespace sdfg

daisytuner / docc / 28190635525

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