28106147644

Committed 24 Jun 2026 02:32PM UTC coverage: 61.922% (+0.1%) from 61.779%

Build # 28106147644

Build Type

Pull #806

github

Committed by

web-flow

Commit Message

Merge 2be414d54 into 57cc1db99

Pull Request Pull Request #806: Map Collapse for Multiple targets in a neste sequence

Coverage Stats

165 of 185 new or added lines in 2 files covered. (89.19%)

419 existing lines in 30 files now uncovered.

37705 of 60891 relevant lines covered (61.92%)

1004.4 hits per line

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

85.11

/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_) {
        // The outer map is not perfectly nested deeply enough for the standard
        // product-space collapse. If it is imperfectly nested (its body contains
        // sibling maps), fall back to a CUDA-style one-level collapse that
        // flattens the outer map together with the sibling maps in its body.
        if (depth == 1) {
            MapCollapse t(loop_, 2);
            return t.can_be_applied(builder, analysis_manager);
        }
        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 = static_cast<size_t>(std::ceil((depth + 1) / 2.0));
    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 (depth <= target_loops_) {
        // Imperfectly-nested fallback (see can_be_applied): flatten the outer map
        // together with the sibling maps in its body into a single map.
        MapCollapse t(loop_, 2);
        t.apply(builder, analysis_manager);
        outer_loop_ = t.collapsed_loop();
        inner_loop_ = nullptr;
        applied_ = true;
        return;
    }

    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 = static_cast<size_t>(std::ceil((depth + 1) / 2.0));
        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["parameters"] = {{"target_loops", target_loops_}};

    serializer::JSONSerializer ser_flat(false);
    j["subgraph"] = nlohmann::json::object();
    j["subgraph"]["0"] = nlohmann::json::object();
    ser_flat.serialize_node(j["subgraph"]["0"], loop_);
}

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) {	43✔
16	size_t depth = 1;	43✔
17	auto* current = &map;	43✔
18	symbolic::SymbolSet indvars;	43✔
19	indvars.insert(map.indvar());	43✔
20	while (true) {	93✔
21	auto& body = current->root();	93✔
22	if (body.size() != 1) {	93✔
23	break;	×
24	}	×
25	auto* next = dynamic_cast<structured_control_flow::Map*>(&body.at(0).first);	93✔
26	if (!next) {	93✔
27	break;	42✔
28	}	42✔
29	for (const auto& atom : symbolic::atoms(next->init())) {	51✔
30	if (indvars.contains(atom)) {	×
31	return depth;	×
32	}	×
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;	42✔
44	}	43✔
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) {}	39✔
52
53	std::string CollapseToDepth::name() const { return "CollapseToDepth"; }	1✔
54
55	bool CollapseToDepth::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	37✔
56	if (target_loops_ < 1 \|\| target_loops_ > 2) {	37✔
57	return false;	2✔
58	}	2✔
59
60	size_t depth = perfectly_nested_map_depth(loop_);	35✔
61	if (depth <= target_loops_) {	35✔
62	// The outer map is not perfectly nested deeply enough for the standard
63	// product-space collapse. If it is imperfectly nested (its body contains
64	// sibling maps), fall back to a CUDA-style one-level collapse that
65	// flattens the outer map together with the sibling maps in its body.
66	if (depth == 1) {	21✔
67	MapCollapse t(loop_, 2);	18✔
68	return t.can_be_applied(builder, analysis_manager);	18✔
69	}	18✔
70	return false;	3✔
71	}	21✔
72
73	if (target_loops_ == 1) {	14✔
74	MapCollapse t(loop_, depth);	8✔
75	return t.can_be_applied(builder, analysis_manager);	8✔
76	}	8✔
77
78	// target_loops_ == 2
79	size_t outer_count = static_cast<size_t>(std::ceil((depth + 1) / 2.0));	6✔
80	size_t inner_count = depth - outer_count;	6✔
81
82	// Check inner half first
83	if (inner_count >= 2) {	6✔
84	auto* inner_start = &loop_;	1✔
85	for (size_t i = 0; i < outer_count; ++i) {	4✔
86	inner_start = dynamic_cast<structured_control_flow::Map*>(&inner_start->root().at(0).first);	3✔
87	}	3✔
88	MapCollapse t_inner(*inner_start, inner_count);	1✔
89	if (!t_inner.can_be_applied(builder, analysis_manager)) {	1✔
90	return false;	×
91	}	×
92	}	1✔
93
94	// Check outer half
95	if (outer_count >= 2) {	6✔
96	MapCollapse t_outer(loop_, outer_count);	6✔
97	if (!t_outer.can_be_applied(builder, analysis_manager)) {	6✔
98	return false;	×
99	}	×
100	}	6✔
101
102	return true;	6✔
103	}	6✔
104
105	void CollapseToDepth::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	8✔
106	size_t depth = perfectly_nested_map_depth(loop_);	8✔
107
108	if (depth <= target_loops_) {	8✔
109	// Imperfectly-nested fallback (see can_be_applied): flatten the outer map
110	// together with the sibling maps in its body into a single map.
NEW 111	MapCollapse t(loop_, 2);	×
NEW 112	t.apply(builder, analysis_manager);	×
NEW 113	outer_loop_ = t.collapsed_loop();	×
NEW 114	inner_loop_ = nullptr;	×
NEW 115	applied_ = true;	×
NEW 116	return;	×
NEW 117	}	×
118
119	if (target_loops_ == 1) {	8✔
120	MapCollapse t(loop_, depth);	5✔
121	t.apply(builder, analysis_manager);	5✔
122	outer_loop_ = t.collapsed_loop();	5✔
123	inner_loop_ = nullptr;	5✔
124	} else {	5✔
125	// target_loops_ == 2
126	size_t outer_count = static_cast<size_t>(std::ceil((depth + 1) / 2.0));	3✔
127	size_t inner_count = depth - outer_count;	3✔
128
129	// Collapse inner half first (so that the outer map chain stays valid)
130	if (inner_count >= 2) {	3✔
131	auto* inner_start = &loop_;	1✔
132	for (size_t i = 0; i < outer_count; ++i) {	4✔
133	inner_start = dynamic_cast<structured_control_flow::Map*>(&inner_start->root().at(0).first);	3✔
134	}	3✔
135	MapCollapse t_inner(*inner_start, inner_count);	1✔
136	t_inner.apply(builder, analysis_manager);	1✔
137	inner_loop_ = t_inner.collapsed_loop();	1✔
138	} else {	2✔
139	// inner half is a single map, no collapse needed — find it
140	auto* m = &loop_;	2✔
141	for (size_t i = 0; i < outer_count; ++i) {	7✔
142	m = dynamic_cast<structured_control_flow::Map*>(&m->root().at(0).first);	5✔
143	}	5✔
144	inner_loop_ = m;	2✔
145	}	2✔
146
147	// Collapse outer half
148	if (outer_count >= 2) {	3✔
149	MapCollapse t_outer(loop_, outer_count);	3✔
150	t_outer.apply(builder, analysis_manager);	3✔
151	outer_loop_ = t_outer.collapsed_loop();	3✔
152	} else {	3✔
153	outer_loop_ = &loop_;	×
154	}	×
155	}	3✔
156
157	applied_ = true;	8✔
158	}	8✔
159
160	void CollapseToDepth::to_json(nlohmann::json& j) const {	1✔
161	j["transformation_type"] = this->name();	1✔
162	j["parameters"] = {{"target_loops", target_loops_}};	1✔
163
164	serializer::JSONSerializer ser_flat(false);	1✔
165	j["subgraph"] = nlohmann::json::object();	1✔
166	j["subgraph"]["0"] = nlohmann::json::object();	1✔
167	ser_flat.serialize_node(j["subgraph"]["0"], loop_);	1✔
168	}	1✔
169
170	CollapseToDepth CollapseToDepth::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	1✔
171	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	1✔
172	size_t target_loops = desc["parameters"]["target_loops"].get<size_t>();	1✔
173	auto element = builder.find_element_by_id(loop_id);	1✔
174	if (!element) {	1✔
UNCOV 175	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
UNCOV 176	}	×
177	auto loop = dynamic_cast<structured_control_flow::Map*>(element);	1✔
178	return CollapseToDepth(*loop, target_loops);	1✔
179	}	1✔
180
181	structured_control_flow::Map* CollapseToDepth::outer_loop() {	9✔
182	if (!applied_) {	9✔
183	return &loop_;	1✔
184	}	1✔
185	return outer_loop_;	8✔
186	}	9✔
187
188	structured_control_flow::Map* CollapseToDepth::inner_loop() {	7✔
189	if (!applied_) {	7✔
190	throw InvalidSDFGException("Accessing collapsed loop before transformation has been applied.");	1✔
191	}	1✔
192	return inner_loop_;	6✔
193	}	7✔
194
195	} // namespace transformations
196	} // namespace sdfg

daisytuner / docc / 28106147644

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