24217063461

Committed 09 Apr 2026 10:47PM UTC coverage: 64.393% (-0.006%) from 64.399%

Build # 24217063461

Build Type

Pull #661

github

Committed by

web-flow

Commit Message

Merge ff19845f9 into bb3981349

Pull Request Pull Request #661: Reduce Maximum Collapsable Depth to Collapseable Maps

Coverage Stats

22 of 34 new or added lines in 2 files covered. (64.71%)

3 existing lines in 1 file now uncovered.

29727 of 46165 relevant lines covered (64.39%)

588.09 hits per line

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

88.89

/opt/src/transformations/collapse_to_depth.cpp

#include "sdfg/transformations/collapse_to_depth.h"
#include <cstddef>

#include "sdfg/structured_control_flow/map.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/transformations/map_collapse.h"

namespace sdfg {
namespace transformations {

// ---------------------------------------------------------------------------
// Helpers
// ---------------------------------------------------------------------------

static size_t perfectly_nested_map_depth(structured_control_flow::Map& map) {
    size_t depth = 1;
    auto* current = &map;
    symbolic::SymbolSet indvars;
    indvars.insert(map.indvar());
    while (true) {
        auto& body = current->root();
        if (body.size() != 1) {
            break;
        }
        auto* next = dynamic_cast<structured_control_flow::Map*>(&body.at(0).first);
        if (!next) {
            break;
        }
        for (const auto& atom : symbolic::atoms(next->init())) {
            if (indvars.contains(atom)) {
                return depth;
            }
        }
        for (const auto& atom : symbolic::atoms(next->condition())) {
            if (indvars.contains(atom)) {
                return depth;
            }
        }
        ++depth;
        current = next;
        indvars.insert(current->indvar());
    }
    return depth;
}

// ---------------------------------------------------------------------------
// CollapseToDepth
// ---------------------------------------------------------------------------

CollapseToDepth::CollapseToDepth(structured_control_flow::Map& loop, size_t target_loops)
    : loop_(loop), target_loops_(target_loops) {}

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

bool CollapseToDepth::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    if (target_loops_ < 1 || target_loops_ > 2) {
        return false;
    }

    size_t depth = perfectly_nested_map_depth(loop_);
    if (depth <= target_loops_) {
        return false;
    }

    if (target_loops_ == 1) {
        MapCollapse t(loop_, depth);
        return t.can_be_applied(builder, analysis_manager);
    }

    // target_loops_ == 2
    size_t outer_count = (depth + 1) / 2;
    size_t inner_count = depth - outer_count;

    // Check inner half first
    if (inner_count >= 2) {
        auto* inner_start = &loop_;
        for (size_t i = 0; i < outer_count; ++i) {
            inner_start = dynamic_cast<structured_control_flow::Map*>(&inner_start->root().at(0).first);
        }
        MapCollapse t_inner(*inner_start, inner_count);
        if (!t_inner.can_be_applied(builder, analysis_manager)) {
            return false;
        }
    }

    // Check outer half
    if (outer_count >= 2) {
        MapCollapse t_outer(loop_, outer_count);
        if (!t_outer.can_be_applied(builder, analysis_manager)) {
            return false;
        }
    }

    return true;
}

void CollapseToDepth::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    size_t depth = perfectly_nested_map_depth(loop_);

    if (target_loops_ == 1) {
        MapCollapse t(loop_, depth);
        t.apply(builder, analysis_manager);
        outer_loop_ = t.collapsed_loop();
        inner_loop_ = nullptr;
    } else {
        // target_loops_ == 2
        size_t outer_count = (depth + 1) / 2;
        size_t inner_count = depth - outer_count;

        // Collapse inner half first (so that the outer map chain stays valid)
        if (inner_count >= 2) {
            auto* inner_start = &loop_;
            for (size_t i = 0; i < outer_count; ++i) {
                inner_start = dynamic_cast<structured_control_flow::Map*>(&inner_start->root().at(0).first);
            }
            MapCollapse t_inner(*inner_start, inner_count);
            t_inner.apply(builder, analysis_manager);
            inner_loop_ = t_inner.collapsed_loop();
        } else {
            // inner half is a single map, no collapse needed — find it
            auto* m = &loop_;
            for (size_t i = 0; i < outer_count; ++i) {
                m = dynamic_cast<structured_control_flow::Map*>(&m->root().at(0).first);
            }
            inner_loop_ = m;
        }

        // Collapse outer half
        if (outer_count >= 2) {
            MapCollapse t_outer(loop_, outer_count);
            t_outer.apply(builder, analysis_manager);
            outer_loop_ = t_outer.collapsed_loop();
        } else {
            outer_loop_ = &loop_;
        }
    }

    applied_ = true;
}

void CollapseToDepth::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();
    j["subgraph"] = {{"0", {{"element_id", loop_.element_id()}, {"type", "map"}}}};
    j["parameters"] = {{"target_loops", target_loops_}};
}

CollapseToDepth CollapseToDepth::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    size_t target_loops = desc["parameters"]["target_loops"].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 CollapseToDepth(*loop, target_loops);
}

structured_control_flow::Map* CollapseToDepth::outer_loop() {
    if (!applied_) {
        return &loop_;
    }
    return outer_loop_;
}

structured_control_flow::Map* CollapseToDepth::inner_loop() {
    if (!applied_) {
        throw InvalidSDFGException("Accessing collapsed loop before transformation has been applied.");
    }
    return inner_loop_;
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/collapse_to_depth.h"
2	#include <cstddef>
3
4	#include "sdfg/structured_control_flow/map.h"
5	#include "sdfg/symbolic/symbolic.h"
6	#include "sdfg/transformations/map_collapse.h"
7
8	namespace sdfg {
9	namespace transformations {
10
11	// ---------------------------------------------------------------------------
12	// Helpers
13	// ---------------------------------------------------------------------------
14
15	static size_t perfectly_nested_map_depth(structured_control_flow::Map& map) {	31✔
16	size_t depth = 1;	31✔
17	auto* current = &map;	31✔
18	symbolic::SymbolSet indvars;	31✔
19	indvars.insert(map.indvar());	31✔
20	while (true) {	81✔
21	auto& body = current->root();	81✔
22	if (body.size() != 1) {	81✔
23	break;	×
24	}	×
25	auto* next = dynamic_cast<structured_control_flow::Map*>(&body.at(0).first);	81✔
26	if (!next) {	81✔
27	break;	30✔
28	}	30✔
29	for (const auto& atom : symbolic::atoms(next->init())) {	51✔
NEW 30	if (indvars.contains(atom)) {	×
NEW 31	return depth;	×
NEW 32	}	×
NEW 33	}	×
34	for (const auto& atom : symbolic::atoms(next->condition())) {	101✔
35	if (indvars.contains(atom)) {	101✔
36	return depth;	1✔
37	}	1✔
38	}	101✔
39	++depth;	50✔
40	current = next;	50✔
41	indvars.insert(current->indvar());	50✔
42	}	50✔
43	return depth;	30✔
44	}	31✔
45
46	// ---------------------------------------------------------------------------
47	// CollapseToDepth
48	// ---------------------------------------------------------------------------
49
50	CollapseToDepth::CollapseToDepth(structured_control_flow::Map& loop, size_t target_loops)
51	: loop_(loop), target_loops_(target_loops) {}	27✔
52
53	std::string CollapseToDepth::name() const { return "CollapseToDepth"; }	1✔
54
55	bool CollapseToDepth::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	25✔
56	if (target_loops_ < 1 \|\| target_loops_ > 2) {	25✔
57	return false;	2✔
58	}	2✔
59
60	size_t depth = perfectly_nested_map_depth(loop_);	23✔
61	if (depth <= target_loops_) {	23✔
62	return false;	9✔
63	}	9✔
64
65	if (target_loops_ == 1) {	14✔
66	MapCollapse t(loop_, depth);	8✔
67	return t.can_be_applied(builder, analysis_manager);	8✔
68	}	8✔
69
70	// target_loops_ == 2
71	size_t outer_count = (depth + 1) / 2;	6✔
72	size_t inner_count = depth - outer_count;	6✔
73
74	// Check inner half first
75	if (inner_count >= 2) {	6✔
76	auto* inner_start = &loop_;	3✔
77	for (size_t i = 0; i < outer_count; ++i) {	10✔
78	inner_start = dynamic_cast<structured_control_flow::Map*>(&inner_start->root().at(0).first);	7✔
79	}	7✔
80	MapCollapse t_inner(*inner_start, inner_count);	3✔
81	if (!t_inner.can_be_applied(builder, analysis_manager)) {	3✔
82	return false;	×
83	}	×
84	}	3✔
85
86	// Check outer half
87	if (outer_count >= 2) {	6✔
88	MapCollapse t_outer(loop_, outer_count);	6✔
89	if (!t_outer.can_be_applied(builder, analysis_manager)) {	6✔
90	return false;	×
91	}	×
92	}	6✔
93
94	return true;	6✔
95	}	6✔
96
97	void CollapseToDepth::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	8✔
98	size_t depth = perfectly_nested_map_depth(loop_);	8✔
99
100	if (target_loops_ == 1) {	8✔
101	MapCollapse t(loop_, depth);	5✔
102	t.apply(builder, analysis_manager);	5✔
103	outer_loop_ = t.collapsed_loop();	5✔
104	inner_loop_ = nullptr;	5✔
105	} else {	5✔
106	// target_loops_ == 2
107	size_t outer_count = (depth + 1) / 2;	3✔
108	size_t inner_count = depth - outer_count;	3✔
109
110	// Collapse inner half first (so that the outer map chain stays valid)
111	if (inner_count >= 2) {	3✔
112	auto* inner_start = &loop_;	2✔
113	for (size_t i = 0; i < outer_count; ++i) {	7✔
114	inner_start = dynamic_cast<structured_control_flow::Map*>(&inner_start->root().at(0).first);	5✔
115	}	5✔
116	MapCollapse t_inner(*inner_start, inner_count);	2✔
117	t_inner.apply(builder, analysis_manager);	2✔
118	inner_loop_ = t_inner.collapsed_loop();	2✔
119	} else {	2✔
120	// inner half is a single map, no collapse needed — find it
121	auto* m = &loop_;	1✔
122	for (size_t i = 0; i < outer_count; ++i) {	3✔
123	m = dynamic_cast<structured_control_flow::Map*>(&m->root().at(0).first);	2✔
124	}	2✔
125	inner_loop_ = m;	1✔
126	}	1✔
127
128	// Collapse outer half
129	if (outer_count >= 2) {	3✔
130	MapCollapse t_outer(loop_, outer_count);	3✔
131	t_outer.apply(builder, analysis_manager);	3✔
132	outer_loop_ = t_outer.collapsed_loop();	3✔
133	} else {	3✔
134	outer_loop_ = &loop_;	×
135	}	×
136	}	3✔
137
138	applied_ = true;	8✔
139	}	8✔
140
141	void CollapseToDepth::to_json(nlohmann::json& j) const {	1✔
142	j["transformation_type"] = this->name();	1✔
143	j["subgraph"] = {{"0", {{"element_id", loop_.element_id()}, {"type", "map"}}}};	1✔
144	j["parameters"] = {{"target_loops", target_loops_}};	1✔
145	}	1✔
146
147	CollapseToDepth CollapseToDepth::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	1✔
148	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	1✔
149	size_t target_loops = desc["parameters"]["target_loops"].get<size_t>();	1✔
150	auto element = builder.find_element_by_id(loop_id);	1✔
151	if (!element) {	1✔
152	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
153	}	×
154	auto loop = dynamic_cast<structured_control_flow::Map*>(element);	1✔
155	return CollapseToDepth(*loop, target_loops);	1✔
156	}	1✔
157
158	structured_control_flow::Map* CollapseToDepth::outer_loop() {	9✔
159	if (!applied_) {	9✔
160	return &loop_;	1✔
161	}	1✔
162	return outer_loop_;	8✔
163	}	9✔
164
165	structured_control_flow::Map* CollapseToDepth::inner_loop() {	7✔
166	if (!applied_) {	7✔
167	throw InvalidSDFGException("Accessing collapsed loop before transformation has been applied.");	1✔
168	}	1✔
169	return inner_loop_;	6✔
170	}	7✔
171
172	} // namespace transformations
173	} // namespace sdfg

daisytuner / docc / 24217063461

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