24143258114

Committed 08 Apr 2026 03:18PM UTC coverage: 64.874% (-0.004%) from 64.878%

Build # 24143258114

Build Type

Pull #661

github

Committed by

web-flow

Commit Message

Merge 5c4676aad into c987b8f47

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

Coverage Stats

14 of 18 new or added lines in 1 file covered. (77.78%)

3 existing lines in 1 file now uncovered.

29044 of 44770 relevant lines covered (64.87%)

602.87 hits per line

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

89.06

/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, bool single_fuse) {
    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;
        }
        if (single_fuse) {
            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_, target_loops_ == 1);
    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_, target_loops_ == 1);

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

daisytuner / docc / 24143258114

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