23339691255

Committed 20 Mar 2026 10:53AM UTC coverage: 64.293% (+0.2%) from 64.115%

Build # 23339691255

Build Type

Pull #603

github

Committed by

web-flow

Commit Message

Merge cf3873416 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.67 hits per line

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

91.15

/opt/src/transformations/collapse_to_depth.cpp

#include "sdfg/transformations/collapse_to_depth.h"

#include "sdfg/structured_control_flow/map.h"
#include "sdfg/transformations/loop_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;
    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;
        }
        ++depth;
        current = next;
    }
    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) {
        LoopCollapse 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);
        }
        LoopCollapse t_inner(*inner_start, inner_count);
        if (!t_inner.can_be_applied(builder, analysis_manager)) {
            return false;
        }
    }

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

daisytuner / docc / 23339691255

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