23431117807

Committed 23 Mar 2026 09:47AM UTC coverage: 64.293% (+0.2%) from 64.115%

Build # 23431117807

Build Type

Pull #603

github

Committed by

web-flow

Commit Message

Merge 95fd5d462 into 3f0642c14

Pull Request Pull Request #603: Loop Collapse Transform

Run Details

243 of 265 new or added lines in 4 files covered. (91.7%)

1 existing line in 1 file now uncovered.

26647 of 41446 relevant lines covered (64.29%)

406.43 hits per line

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

93.62

/opt/src/transformations/map_collapse.cpp

#include "sdfg/transformations/map_collapse.h"

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/symbolic/symbolic.h"

namespace sdfg {
namespace transformations {

MapCollapse::MapCollapse(structured_control_flow::Map& loop, size_t count) : loop_(loop), count_(count) {}

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

bool MapCollapse::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    // Criterion: count must be at least 2
    if (count_ < 2) {
        return false;
    }

    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();

    // Collect the chain of count_ perfectly-nested maps
    std::vector<structured_control_flow::Map*> maps;
    maps.push_back(&loop_);

    auto* current = &loop_;
    for (size_t i = 1; i < count_; ++i) {
        auto& body = current->root();

        // Criterion: All target maps must be perfectly nested (exactly one child that is a Map)
        if (body.size() != 1) {
            return false;
        }

        auto* next = dynamic_cast<structured_control_flow::Map*>(&body.at(0).first);
        if (!next) {
            return false;
        }

        // Criterion: The Sequence holding each map must have empty transitions
        if (!body.at(0).second.empty()) {
            return false;
        }

        maps.push_back(next);
        current = next;
    }

    // Criterion: All maps must be contiguous (stride 1, starting from 0)
    for (auto* map : maps) {
        if (!analysis::LoopAnalysis::is_contiguous(map, assumptions_analysis)) {
            return false;
        }
    }

    // Collect indvars of all maps being collapsed
    symbolic::SymbolSet indvars;
    for (auto* map : maps) {
        indvars.insert(map->indvar());
    }

    // Criterion: Map bounds may not depend on any of the loop induction variables
    // of the maps being collapsed
    for (auto* map : maps) {
        auto bound = analysis::LoopAnalysis::canonical_bound(map, assumptions_analysis);
        if (bound == SymEngine::null) {
            return false;
        }
        for (auto& iv : indvars) {
            if (symbolic::uses(bound, iv)) {
                return false;
            }
        }
    }

    return true;
}

void MapCollapse::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& sdfg = builder.subject();
    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();

    // Step 1: Gather the maps to collapse and their bounds
    std::vector<structured_control_flow::Map*> maps;
    maps.push_back(&loop_);
    auto* current = &loop_;
    for (size_t i = 1; i < count_; ++i) {
        auto* next = dynamic_cast<structured_control_flow::Map*>(&current->root().at(0).first);
        maps.push_back(next);
        current = next;
    }

    std::vector<symbolic::Symbol> indvars;
    std::vector<symbolic::Expression> bounds;
    for (auto* map : maps) {
        indvars.push_back(map->indvar());
        bounds.push_back(analysis::LoopAnalysis::canonical_bound(map, assumptions_analysis));
    }

    // Step 2: Compute total iteration count = product of all bounds
    symbolic::Expression total_bound = bounds[0];
    for (size_t i = 1; i < bounds.size(); ++i) {
        total_bound = symbolic::mul(total_bound, bounds[i]);
    }

    // Step 3: Create the collapsed induction variable
    auto civ_name = builder.find_new_name(indvars[0]->get_name() + "_collapsed");
    builder.add_container(civ_name, sdfg.type(indvars[0]->get_name()));
    auto civ = symbolic::symbol(civ_name);

    // Step 4: Find the parent sequence of the outermost map
    auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&loop_));
    size_t index = parent->index(loop_);
    auto& transition = parent->at(index).second;

    // Step 5: Create the new collapsed map before the original
    auto& collapsed_map = builder.add_map_before(
        *parent,
        loop_,
        civ,
        symbolic::Lt(civ, total_bound),
        symbolic::integer(0),
        symbolic::add(civ, symbolic::integer(1)),
        loop_.schedule_type(),
        transition.assignments(),
        loop_.debug_info()
    );

    // Step 6: Add an empty block for indvar recovery before the original contents
    builder.add_block(collapsed_map.root());

    // Step 7: Move the body of the innermost map into the collapsed map
    auto* innermost = maps.back();
    builder.move_children(innermost->root(), collapsed_map.root());

    // Step 8: Add indvar recovery assignments to the transition of the empty
    // block so that all induction variables are defined before the original
    // loop contents.
    //
    // For maps [0..n-1] with bounds [B0, B1, ..., B_{n-1}]:
    //   indvar_0     = civ / (B1 * B2 * ... * B_{n-1})
    //   indvar_k     = (civ / (B_{k+1} * ... * B_{n-1})) % B_k
    //   indvar_{n-1} = civ % B_{n-1}
    auto& first_transition = collapsed_map.root().at(0).second;
    size_t n = indvars.size();

    for (size_t k = 0; k < n; ++k) {
        // Compute suffix product = B_{k+1} * ... * B_{n-1}
        symbolic::Expression suffix = symbolic::integer(1);
        for (size_t j = k + 1; j < n; ++j) {
            suffix = symbolic::mul(suffix, bounds[j]);
        }

        symbolic::Expression value;
        if (k == 0 && n == 1) {
            // Single-loop degenerate case (shouldn't happen with count>=2, but safe)
            value = civ;
        } else if (k == 0) {
            // Outermost: indvar_0 = civ / suffix
            value = symbolic::div(civ, suffix);
        } else if (k == n - 1) {
            // Innermost: indvar_{n-1} = civ % B_{n-1}
            value = symbolic::mod(civ, bounds[k]);
        } else {
            // Middle: indvar_k = (civ / suffix) % B_k
            value = symbolic::mod(symbolic::div(civ, suffix), bounds[k]);
        }

        first_transition.assignments()[indvars[k]] = value;
    }

    // Step 9: Remove the original nest
    // The index shifted by 1 because we inserted a map before
    transition.assignments().clear();
    builder.remove_child(*parent, parent->index(loop_));

    analysis_manager.invalidate_all();
    applied_ = true;
    collapsed_loop_ = &collapsed_map;
}

void MapCollapse::to_json(nlohmann::json& j) const {
    std::string loop_type;
    if (dynamic_cast<const structured_control_flow::Map*>(&loop_)) {
        loop_type = "map";
    } else {
        throw InvalidSDFGException("Unsupported loop type for serialization of map: " + loop_.indvar()->get_name());
    }

    j["transformation_type"] = this->name();
    j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};
    j["parameters"] = {{"count", count_}};
}

MapCollapse MapCollapse::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    size_t count = desc["parameters"]["count"].get<size_t>();
    auto element = builder.find_element_by_id(loop_id);
    if (!element) {
        throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");
    }
    auto loop = dynamic_cast<structured_control_flow::Map*>(element);

    return MapCollapse(*loop, count);
}

structured_control_flow::Map* MapCollapse::collapsed_loop() {
    if (!applied_) {
        return &loop_;
    }

    return collapsed_loop_;
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/map_collapse.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/analysis/loop_analysis.h"
5	#include "sdfg/analysis/scope_analysis.h"
6	#include "sdfg/builder/structured_sdfg_builder.h"
7	#include "sdfg/structured_control_flow/map.h"
8	#include "sdfg/structured_control_flow/structured_loop.h"
9	#include "sdfg/symbolic/symbolic.h"
10
11	namespace sdfg {
12	namespace transformations {
13
14	MapCollapse::MapCollapse(structured_control_flow::Map& loop, size_t count) : loop_(loop), count_(count) {}	53✔
15
16	std::string MapCollapse::name() const { return "MapCollapse"; }	2✔
17
18	bool MapCollapse::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	40✔
19	// Criterion: count must be at least 2
20	if (count_ < 2) {	40✔
21	return false;	1✔
22	}	1✔
23
24	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	39✔
25
26	// Collect the chain of count_ perfectly-nested maps
27	std::vector<structured_control_flow::Map*> maps;	39✔
28	maps.push_back(&loop_);	39✔
29
30	auto* current = &loop_;	39✔
31	for (size_t i = 1; i < count_; ++i) {	85✔
32	auto& body = current->root();	49✔
33
34	// Criterion: All target maps must be perfectly nested (exactly one child that is a Map)
35	if (body.size() != 1) {	49✔
36	return false;	1✔
37	}	1✔
38
39	auto* next = dynamic_cast<structured_control_flow::Map*>(&body.at(0).first);	48✔
40	if (!next) {	48✔
41	return false;	1✔
42	}	1✔
43
44	// Criterion: The Sequence holding each map must have empty transitions
45	if (!body.at(0).second.empty()) {	47✔
46	return false;	1✔
47	}	1✔
48
49	maps.push_back(next);	46✔
50	current = next;	46✔
51	}	46✔
52
53	// Criterion: All maps must be contiguous (stride 1, starting from 0)
54	for (auto* map : maps) {	81✔
55	if (!analysis::LoopAnalysis::is_contiguous(map, assumptions_analysis)) {	81✔
NEW 56	return false;	×
NEW 57	}	×
58	}	81✔
59
60	// Collect indvars of all maps being collapsed
61	symbolic::SymbolSet indvars;	36✔
62	for (auto* map : maps) {	81✔
63	indvars.insert(map->indvar());	81✔
64	}	81✔
65
66	// Criterion: Map bounds may not depend on any of the loop induction variables
67	// of the maps being collapsed
68	for (auto* map : maps) {	81✔
69	auto bound = analysis::LoopAnalysis::canonical_bound(map, assumptions_analysis);	81✔
70	if (bound == SymEngine::null) {	81✔
NEW 71	return false;	×
NEW 72	}	×
73	for (auto& iv : indvars) {	191✔
74	if (symbolic::uses(bound, iv)) {	191✔
75	return false;	2✔
76	}	2✔
77	}	191✔
78	}	81✔
79
80	return true;	34✔
81	}	36✔
82
83	void MapCollapse::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	25✔
84	auto& sdfg = builder.subject();	25✔
85	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	25✔
86	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	25✔
87
88	// Step 1: Gather the maps to collapse and their bounds
89	std::vector<structured_control_flow::Map*> maps;	25✔
90	maps.push_back(&loop_);	25✔
91	auto* current = &loop_;	25✔
92	for (size_t i = 1; i < count_; ++i) {	55✔
93	auto* next = dynamic_cast<structured_control_flow::Map*>(&current->root().at(0).first);	30✔
94	maps.push_back(next);	30✔
95	current = next;	30✔
96	}	30✔
97
98	std::vector<symbolic::Symbol> indvars;	25✔
99	std::vector<symbolic::Expression> bounds;	25✔
100	for (auto* map : maps) {	55✔
101	indvars.push_back(map->indvar());	55✔
102	bounds.push_back(analysis::LoopAnalysis::canonical_bound(map, assumptions_analysis));	55✔
103	}	55✔
104
105	// Step 2: Compute total iteration count = product of all bounds
106	symbolic::Expression total_bound = bounds[0];	25✔
107	for (size_t i = 1; i < bounds.size(); ++i) {	55✔
108	total_bound = symbolic::mul(total_bound, bounds[i]);	30✔
109	}	30✔
110
111	// Step 3: Create the collapsed induction variable
112	auto civ_name = builder.find_new_name(indvars[0]->get_name() + "_collapsed");	25✔
113	builder.add_container(civ_name, sdfg.type(indvars[0]->get_name()));	25✔
114	auto civ = symbolic::symbol(civ_name);	25✔
115
116	// Step 4: Find the parent sequence of the outermost map
117	auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&loop_));	25✔
118	size_t index = parent->index(loop_);	25✔
119	auto& transition = parent->at(index).second;	25✔
120
121	// Step 5: Create the new collapsed map before the original
122	auto& collapsed_map = builder.add_map_before(	25✔
123	*parent,	25✔
124	loop_,	25✔
125	civ,	25✔
126	symbolic::Lt(civ, total_bound),	25✔
127	symbolic::integer(0),	25✔
128	symbolic::add(civ, symbolic::integer(1)),	25✔
129	loop_.schedule_type(),	25✔
130	transition.assignments(),	25✔
131	loop_.debug_info()	25✔
132	);	25✔
133
134	// Step 6: Add an empty block for indvar recovery before the original contents
135	builder.add_block(collapsed_map.root());	25✔
136
137	// Step 7: Move the body of the innermost map into the collapsed map
138	auto* innermost = maps.back();	25✔
139	builder.move_children(innermost->root(), collapsed_map.root());	25✔
140
141	// Step 8: Add indvar recovery assignments to the transition of the empty
142	// block so that all induction variables are defined before the original
143	// loop contents.
144	//
145	// For maps [0..n-1] with bounds [B0, B1, ..., B_{n-1}]:
146	// indvar_0 = civ / (B1 * B2 * ... * B_{n-1})
147	// indvar_k = (civ / (B_{k+1} * ... * B_{n-1})) % B_k
148	// indvar_{n-1} = civ % B_{n-1}
149	auto& first_transition = collapsed_map.root().at(0).second;	25✔
150	size_t n = indvars.size();	25✔
151
152	for (size_t k = 0; k < n; ++k) {	80✔
153	// Compute suffix product = B_{k+1} * ... * B_{n-1}
154	symbolic::Expression suffix = symbolic::integer(1);	55✔
155	for (size_t j = k + 1; j < n; ++j) {	91✔
156	suffix = symbolic::mul(suffix, bounds[j]);	36✔
157	}	36✔
158
159	symbolic::Expression value;	55✔
160	if (k == 0 && n == 1) {	55✔
161	// Single-loop degenerate case (shouldn't happen with count>=2, but safe)
NEW 162	value = civ;	×
163	} else if (k == 0) {	55✔
164	// Outermost: indvar_0 = civ / suffix
165	value = symbolic::div(civ, suffix);	25✔
166	} else if (k == n - 1) {	30✔
167	// Innermost: indvar_{n-1} = civ % B_{n-1}
168	value = symbolic::mod(civ, bounds[k]);	25✔
169	} else {	25✔
170	// Middle: indvar_k = (civ / suffix) % B_k
171	value = symbolic::mod(symbolic::div(civ, suffix), bounds[k]);	5✔
172	}	5✔
173
174	first_transition.assignments()[indvars[k]] = value;	55✔
175	}	55✔
176
177	// Step 9: Remove the original nest
178	// The index shifted by 1 because we inserted a map before
179	transition.assignments().clear();	25✔
180	builder.remove_child(*parent, parent->index(loop_));	25✔
181
182	analysis_manager.invalidate_all();	25✔
183	applied_ = true;	25✔
184	collapsed_loop_ = &collapsed_map;	25✔
185	}	25✔
186
187	void MapCollapse::to_json(nlohmann::json& j) const {	1✔
188	std::string loop_type;	1✔
189	if (dynamic_cast<const structured_control_flow::Map*>(&loop_)) {	1✔
190	loop_type = "map";	1✔
191	} else {	1✔
NEW 192	throw InvalidSDFGException("Unsupported loop type for serialization of map: " + loop_.indvar()->get_name());	×
NEW 193	}	×
194
195	j["transformation_type"] = this->name();	1✔
196	j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};	1✔
197	j["parameters"] = {{"count", count_}};	1✔
198	}	1✔
199
200	MapCollapse MapCollapse::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	1✔
201	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	1✔
202	size_t count = desc["parameters"]["count"].get<size_t>();	1✔
203	auto element = builder.find_element_by_id(loop_id);	1✔
204	if (!element) {	1✔
NEW 205	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
NEW 206	}	×
207	auto loop = dynamic_cast<structured_control_flow::Map*>(element);	1✔
208
209	return MapCollapse(*loop, count);	1✔
210	}	1✔
211
212	structured_control_flow::Map* MapCollapse::collapsed_loop() {	26✔
213	if (!applied_) {	26✔
214	return &loop_;	1✔
215	}	1✔
216
217	return collapsed_loop_;	25✔
218	}	26✔
219
220	} // namespace transformations
221	} // namespace sdfg

daisytuner / docc / 23431117807

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