28809522800

Committed 06 Jul 2026 05:12PM UTC coverage: 62.882% (-0.08%) from 62.96%

Build # 28809522800

Build Type

Pull #843

github

Committed by

web-flow

Commit Message

Merge beb5b23d7 into 95ea95f1f

Pull Request Pull Request #843: adds type_ids for Element classes and a human-readable element_type

Coverage Stats

413 of 587 new or added lines in 121 files covered. (70.36%)

74 existing lines in 6 files now uncovered.

40564 of 64508 relevant lines covered (62.88%)

961.48 hits per line

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

94.16

/opt/src/passes/normalization/stride_minimization.cpp

#include "sdfg/passes/normalization/stride_minimization.h"

#include <sdfg/analysis/loop_analysis.h>
#include <sdfg/transformations/loop_interchange.h>
#include <unordered_map>

namespace sdfg {
namespace passes {
namespace normalization {

StrideMinimization::StrideMinimization() : Pass() {};

bool StrideMinimization::is_admissible(
    std::vector<std::string>& current, std::vector<std::string>& target, std::unordered_set<std::string>& allowed_swaps
) {
    std::vector<size_t> permutation_indices;
    for (auto& p : current) {
        auto it = std::find(target.begin(), target.end(), p);
        permutation_indices.push_back(std::distance(target.begin(), it));
    }
    for (size_t i = 0; i < permutation_indices.size(); i++) {
        for (size_t j = 0; j < permutation_indices.size() - i - 1; j++) {
            if (permutation_indices[j] > permutation_indices[j + 1]) {
                std::string swap = target[permutation_indices[j]] + "_" + target[permutation_indices[j + 1]];
                if (allowed_swaps.find(swap) == allowed_swaps.end()) {
                    return false;
                }
                size_t tmp = permutation_indices[j];
                permutation_indices[j] = permutation_indices[j + 1];
                permutation_indices[j + 1] = tmp;
            }
        }
    }

    return true;
};

std::unordered_set<std::string> StrideMinimization::allowed_swaps(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    std::vector<structured_control_flow::ControlFlowNode*>& nested_loops
) {
    std::unordered_set<std::string> allowed_swaps;
    for (size_t i = 0; i < nested_loops.size() - 1; i++) {
        if (dynamic_cast<structured_control_flow::While*>(nested_loops.at(i)) ||
            dynamic_cast<structured_control_flow::While*>(nested_loops.at(i + 1))) {
            continue;
        } else {
            auto first_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(nested_loops.at(i));
            auto second_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(nested_loops.at(i + 1));
            transformations::LoopInterchange loop_interchange(*first_loop, *second_loop);
            if (loop_interchange.can_be_applied(builder, analysis_manager)) {
                allowed_swaps.insert(first_loop->indvar()->get_name() + "_" + second_loop->indvar()->get_name());
            }
        }
    }
    return allowed_swaps;
};

std::pair<bool, std::vector<std::string>> StrideMinimization::can_be_applied(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    std::vector<structured_control_flow::ControlFlowNode*>& nested_loops
) {
    if (nested_loops.size() < 2) {
        return {false, {}};
    }

    size_t while_loops = 0;
    std::vector<std::string> permutation;
    for (auto& loop : nested_loops) {
        if (!dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
            permutation.push_back("WHILE_" + std::to_string(while_loops++));
        } else {
            auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop);
            permutation.push_back(for_loop->indvar()->get_name());
        }
    }

    auto admissible_swaps = allowed_swaps(builder, analysis_manager, nested_loops);

    // Collect all memory accesses of body
    structured_control_flow::ControlFlowNode* nested_root = nullptr;
    if (auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(nested_loops.at(0))) {
        nested_root = &for_loop->root();
    } else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(nested_loops.at(0))) {
        nested_root = &while_loop->root();
    } else {
        assert(false);
    }
    auto& all_users = analysis_manager.get<analysis::Users>();
    analysis::UsersView users(all_users, *nested_root);

    // Collect all memory accesses
    std::vector<data_flow::Subset> subsets;
    for (auto& use : users.reads()) {
        auto element = use->element();
        if (!dynamic_cast<data_flow::AccessNode*>(element)) {
            continue;
        }
        auto access = dynamic_cast<data_flow::AccessNode*>(element);
        auto& graph = access->get_parent();
        for (auto& oedge : graph.out_edges(*access)) {
            auto& subset = oedge.subset();

            // Filter the subset for only dimensions using the permutation
            data_flow::Subset filtered_subset;
            for (auto& dim : subset) {
                for (auto& perm : permutation) {
                    if (symbolic::uses(dim, perm)) {
                        filtered_subset.push_back(dim);
                        break;
                    }
                }
            }
            if (filtered_subset.empty()) {
                continue;
            }

            subsets.push_back(filtered_subset);
        }
    }
    for (auto& use : users.writes()) {
        auto element = use->element();
        if (!dynamic_cast<data_flow::AccessNode*>(element)) {
            continue;
        }
        auto access = dynamic_cast<data_flow::AccessNode*>(element);
        auto& graph = access->get_parent();
        for (auto& iedge : graph.in_edges(*access)) {
            auto& subset = iedge.subset();

            // Filter the subset for only dimensions using the permutation
            data_flow::Subset filtered_subset;
            for (auto& dim : subset) {
                for (auto& perm : permutation) {
                    if (symbolic::uses(dim, perm)) {
                        filtered_subset.push_back(dim);
                        break;
                    }
                }
            }
            if (filtered_subset.empty()) {
                continue;
            }

            subsets.push_back(filtered_subset);
        }
    }

    // No memory accesses to optimize
    if (subsets.empty()) {
        return {false, {}};
    }

    // Test all permutations (must start from a sorted sequence)
    std::vector<std::string> current = permutation;
    std::sort(current.begin(), current.end());

    std::vector<std::string> best_permutation;
    std::vector<std::map<size_t, size_t>> best_scores;
    do {
        if (!is_admissible(permutation, current, admissible_swaps)) {
            continue;
        }

        // Init scores per dimension
        std::vector<std::map<size_t, size_t>> scores;
        for (size_t i = 0; i < current.size(); i++) {
            scores.push_back({});
        }

        // Compute skipped dimensions and sum up
        for (auto& subset : subsets) {
            std::vector<size_t> strides;
            for (auto& var : current) {
                bool found = false;
                for (size_t j = 0; j < subset.size(); j++) {
                    auto& dim = subset.at(j);
                    if (symbolic::uses(dim, var)) {
                        strides.push_back(subset.size() - j);
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    strides.push_back(0);
                }
            }

            for (size_t i = 0; i < current.size(); i++) {
                auto& score_dim = scores[i];
                if (score_dim.find(strides[i]) == score_dim.end()) {
                    score_dim[strides[i]] = 1;
                } else {
                    score_dim[strides[i]]++;
                }
            }
        }

        // Compare scores
        if (best_permutation.empty()) {
            best_permutation = current;
            best_scores = scores;
        } else {
            bool better = false;
            bool equal = true;
            for (int i = scores.size() - 1; i >= 0; i--) {
                auto& best_score_dim = best_scores[i];
                auto& score_dim = scores[i];

                // Decide by maximal stride
                auto best_max_stride = best_score_dim.rbegin()->first;
                auto max_stride = score_dim.rbegin()->first;
                if (max_stride < best_max_stride) {
                    better = true;
                    equal = false;
                    break;
                } else if (max_stride == best_max_stride) {
                    // Decide by number of occurences
                    auto best_max_stride_count = best_score_dim.rbegin()->second;
                    auto max_stride_count = score_dim.rbegin()->second;
                    if (max_stride_count < best_max_stride_count) {
                        better = true;
                        equal = false;
                        break;
                    } else if (max_stride_count == best_max_stride_count) {
                        continue;
                    } else {
                        equal = false;
                        break;
                    }
                } else {
                    equal = false;
                    break;
                }
            }
            if (better) {
                best_permutation = current;
                best_scores = scores;
            } else if (equal) {
                // If equal and original permutation
                if (std::equal(current.begin(), current.end(), permutation.begin())) {
                    best_permutation = current;
                    best_scores = scores;
                }
            }
        }
    } while (std::next_permutation(current.begin(), current.end()));

    // Check if permutation is better than original
    return {best_permutation != permutation, best_permutation};
};

void StrideMinimization::apply(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    std::vector<structured_control_flow::ControlFlowNode*>& nested_loops,
    std::vector<std::string> target_permutation
) {
    size_t while_loops = 0;
    std::vector<std::string> permutation;
    for (auto& loop : nested_loops) {
        if (!dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
            permutation.push_back("WHILE_" + std::to_string(while_loops++));
        } else {
            auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop);
            permutation.push_back(for_loop->indvar()->get_name());
        }
    }
    std::vector<size_t> permutation_indices;
    for (auto& p : permutation) {
        auto it = std::find(target_permutation.begin(), target_permutation.end(), p);
        permutation_indices.push_back(std::distance(target_permutation.begin(), it));
    }

    // Bubble sort permutation indices
    for (size_t i = 0; i < permutation_indices.size(); i++) {
        for (size_t j = 0; j < permutation_indices.size() - i - 1; j++) {
            if (permutation_indices[j] > permutation_indices[j + 1]) {
                auto first_loop = static_cast<structured_control_flow::StructuredLoop*>(nested_loops.at(j));
                auto second_loop = static_cast<structured_control_flow::StructuredLoop*>(nested_loops.at(j + 1));
                transformations::LoopInterchange loop_interchange(*first_loop, *second_loop);
                // given that the permutation is admissible, the interchange must be applicable, else the permutation
                // would not be admissible
                loop_interchange.apply(builder, analysis_manager);
                std::swap(permutation_indices[j], permutation_indices[j + 1]);
            }
        }
    }
};

std::string StrideMinimization::name() { return "StrideMinimization"; };

bool StrideMinimization::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    bool applied = false;

    auto& loop_tree_analysis = analysis_manager.get<analysis::LoopAnalysis>();

    // Collect outermost loops
    std::vector<structured_control_flow::ControlFlowNode*> outer_loops = loop_tree_analysis.outermost_loops();

    std::unordered_map<
        structured_control_flow::ControlFlowNode*,
        std::vector<std::pair<std::vector<std::string>, std::vector<structured_control_flow::ControlFlowNode*>>>>
        loop_permutations;

    // Find loop nests for stride minimization
    for (auto& outer_loop : outer_loops) {
        auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
        auto paths = loop_analysis.loop_tree_paths(outer_loop);
        for (auto& path : paths) {
            auto [applicable, permutation] = this->can_be_applied(builder, analysis_manager, path);
            if (applicable) {
                if (loop_permutations.find(path.at(0)) == loop_permutations.end()) {
                    loop_permutations.insert({path.at(0), {}});
                }
                loop_permutations[path.at(0)].push_back({permutation, path});
            }
        }
    }

    // Apply stride minimization
    for (auto& [loop, permutations] : loop_permutations) {
        auto& permutation = permutations.at(0).first;
        auto& path = permutations.at(0).second;

        this->apply(builder, analysis_manager, path, permutation);
        applied = true;
    }
    return applied;
};

} // namespace normalization
} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/normalization/stride_minimization.h"
2
3	#include <sdfg/analysis/loop_analysis.h>
4	#include <sdfg/transformations/loop_interchange.h>
5	#include <unordered_map>
6
7	namespace sdfg {
8	namespace passes {
9	namespace normalization {
10
11	StrideMinimization::StrideMinimization() : Pass() {};	20✔
12
13	bool StrideMinimization::is_admissible(
14	std::vector<std::string>& current, std::vector<std::string>& target, std::unordered_set<std::string>& allowed_swaps
15	) {	383✔
16	std::vector<size_t> permutation_indices;	383✔
17	for (auto& p : current) {	1,119✔
18	auto it = std::find(target.begin(), target.end(), p);	1,119✔
19	permutation_indices.push_back(std::distance(target.begin(), it));	1,119✔
20	}	1,119✔
21	for (size_t i = 0; i < permutation_indices.size(); i++) {	867✔
22	for (size_t j = 0; j < permutation_indices.size() - i - 1; j++) {	1,280✔
23	if (permutation_indices[j] > permutation_indices[j + 1]) {	796✔
24	std::string swap = target[permutation_indices[j]] + "_" + target[permutation_indices[j + 1]];	399✔
25	if (allowed_swaps.find(swap) == allowed_swaps.end()) {	399✔
26	return false;	211✔
27	}	211✔
28	size_t tmp = permutation_indices[j];	188✔
29	permutation_indices[j] = permutation_indices[j + 1];	188✔
30	permutation_indices[j + 1] = tmp;	188✔
31	}	188✔
32	}	796✔
33	}	695✔
34
35	return true;	172✔
36	};	383✔
37
38	std::unordered_set<std::string> StrideMinimization::allowed_swaps(
39	builder::StructuredSDFGBuilder& builder,
40	analysis::AnalysisManager& analysis_manager,
41	std::vector<structured_control_flow::ControlFlowNode*>& nested_loops
42	) {	92✔
43	std::unordered_set<std::string> allowed_swaps;	92✔
44	for (size_t i = 0; i < nested_loops.size() - 1; i++) {	224✔
45	if (dynamic_cast<structured_control_flow::While*>(nested_loops.at(i)) \|\|	132✔
46	dynamic_cast<structured_control_flow::While*>(nested_loops.at(i + 1))) {	132✔
UNCOV 47	continue;	×
48	} else {	132✔
49	auto first_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(nested_loops.at(i));	132✔
50	auto second_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(nested_loops.at(i + 1));	132✔
51	transformations::LoopInterchange loop_interchange(first_loop, second_loop);	132✔
52	if (loop_interchange.can_be_applied(builder, analysis_manager)) {	132✔
53	allowed_swaps.insert(first_loop->indvar()->get_name() + "_" + second_loop->indvar()->get_name());	81✔
54	}	81✔
55	}	132✔
56	}	132✔
57	return allowed_swaps;	92✔
58	};	92✔
59
60	std::pair<bool, std::vector<std::string>> StrideMinimization::can_be_applied(
61	builder::StructuredSDFGBuilder& builder,
62	analysis::AnalysisManager& analysis_manager,
63	std::vector<structured_control_flow::ControlFlowNode*>& nested_loops
64	) {	110✔
65	if (nested_loops.size() < 2) {	110✔
66	return {false, {}};	21✔
67	}	21✔
68
69	size_t while_loops = 0;	89✔
70	std::vector<std::string> permutation;	89✔
71	for (auto& loop : nested_loops) {	218✔
72	if (!dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	218✔
73	permutation.push_back("WHILE_" + std::to_string(while_loops++));	×
74	} else {	218✔
75	auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop);	218✔
76	permutation.push_back(for_loop->indvar()->get_name());	218✔
77	}	218✔
78	}	218✔
79
80	auto admissible_swaps = allowed_swaps(builder, analysis_manager, nested_loops);	89✔
81
82	// Collect all memory accesses of body
83	structured_control_flow::ControlFlowNode* nested_root = nullptr;	89✔
84	if (auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(nested_loops.at(0))) {	89✔
85	nested_root = &for_loop->root();	89✔
86	} else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(nested_loops.at(0))) {	89✔
87	nested_root = &while_loop->root();	×
88	} else {	×
89	assert(false);	×
90	}	×
91	auto& all_users = analysis_manager.get<analysis::Users>();	89✔
92	analysis::UsersView users(all_users, *nested_root);	89✔
93
94	// Collect all memory accesses
95	std::vector<data_flow::Subset> subsets;	89✔
96	for (auto& use : users.reads()) {	1,581✔
97	auto element = use->element();	1,581✔
98	if (!dynamic_cast<data_flow::AccessNode*>(element)) {	1,581✔
99	continue;	1,275✔
100	}	1,275✔
101	auto access = dynamic_cast<data_flow::AccessNode*>(element);	306✔
102	auto& graph = access->get_parent();	306✔
103	for (auto& oedge : graph.out_edges(*access)) {	337✔
104	auto& subset = oedge.subset();	337✔
105
106	// Filter the subset for only dimensions using the permutation
107	data_flow::Subset filtered_subset;	337✔
108	for (auto& dim : subset) {	465✔
109	for (auto& perm : permutation) {	940✔
110	if (symbolic::uses(dim, perm)) {	940✔
111	filtered_subset.push_back(dim);	360✔
112	break;	360✔
113	}	360✔
114	}	940✔
115	}	465✔
116	if (filtered_subset.empty()) {	337✔
117	continue;	121✔
118	}	121✔
119
120	subsets.push_back(filtered_subset);	216✔
121	}	216✔
122	}	306✔
123	for (auto& use : users.writes()) {	568✔
124	auto element = use->element();	568✔
125	if (!dynamic_cast<data_flow::AccessNode*>(element)) {	568✔
126	continue;	378✔
127	}	378✔
128	auto access = dynamic_cast<data_flow::AccessNode*>(element);	190✔
129	auto& graph = access->get_parent();	190✔
130	for (auto& iedge : graph.in_edges(*access)) {	190✔
131	auto& subset = iedge.subset();	190✔
132
133	// Filter the subset for only dimensions using the permutation
134	data_flow::Subset filtered_subset;	190✔
135	for (auto& dim : subset) {	237✔
136	for (auto& perm : permutation) {	475✔
137	if (symbolic::uses(dim, perm)) {	475✔
138	filtered_subset.push_back(dim);	180✔
139	break;	180✔
140	}	180✔
141	}	475✔
142	}	237✔
143	if (filtered_subset.empty()) {	190✔
144	continue;	85✔
145	}	85✔
146
147	subsets.push_back(filtered_subset);	105✔
148	}	105✔
149	}	190✔
150
151	// No memory accesses to optimize
152	if (subsets.empty()) {	89✔
153	return {false, {}};	1✔
154	}	1✔
155
156	// Test all permutations (must start from a sorted sequence)
157	std::vector<std::string> current = permutation;	88✔
158	std::sort(current.begin(), current.end());	88✔
159
160	std::vector<std::string> best_permutation;	88✔
161	std::vector<std::map<size_t, size_t>> best_scores;	88✔
162	do {	378✔
163	if (!is_admissible(permutation, current, admissible_swaps)) {	378✔
164	continue;	208✔
165	}	208✔
166
167	// Init scores per dimension
168	std::vector<std::map<size_t, size_t>> scores;	170✔
169	for (size_t i = 0; i < current.size(); i++) {	610✔
170	scores.push_back({});	440✔
171	}	440✔
172
173	// Compute skipped dimensions and sum up
174	for (auto& subset : subsets) {	654✔
175	std::vector<size_t> strides;	654✔
176	for (auto& var : current) {	1,725✔
177	bool found = false;	1,725✔
178	for (size_t j = 0; j < subset.size(); j++) {	3,166✔
179	auto& dim = subset.at(j);	2,539✔
180	if (symbolic::uses(dim, var)) {	2,539✔
181	strides.push_back(subset.size() - j);	1,098✔
182	found = true;	1,098✔
183	break;	1,098✔
184	}	1,098✔
185	}	2,539✔
186	if (!found) {	1,725✔
187	strides.push_back(0);	627✔
188	}	627✔
189	}	1,725✔
190
191	for (size_t i = 0; i < current.size(); i++) {	2,379✔
192	auto& score_dim = scores[i];	1,725✔
193	if (score_dim.find(strides[i]) == score_dim.end()) {	1,725✔
194	score_dim[strides[i]] = 1;	929✔
195	} else {	929✔
196	score_dim[strides[i]]++;	796✔
197	}	796✔
198	}	1,725✔
199	}	654✔
200
201	// Compare scores
202	if (best_permutation.empty()) {	170✔
203	best_permutation = current;	88✔
204	best_scores = scores;	88✔
205	} else {	88✔
206	bool better = false;	82✔
207	bool equal = true;	82✔
208	for (int i = scores.size() - 1; i >= 0; i--) {	109✔
209	auto& best_score_dim = best_scores[i];	105✔
210	auto& score_dim = scores[i];	105✔
211
212	// Decide by maximal stride
213	auto best_max_stride = best_score_dim.rbegin()->first;	105✔
214	auto max_stride = score_dim.rbegin()->first;	105✔
215	if (max_stride < best_max_stride) {	105✔
216	better = true;	37✔
217	equal = false;	37✔
218	break;	37✔
219	} else if (max_stride == best_max_stride) {	68✔
220	// Decide by number of occurences
221	auto best_max_stride_count = best_score_dim.rbegin()->second;	29✔
222	auto max_stride_count = score_dim.rbegin()->second;	29✔
223	if (max_stride_count < best_max_stride_count) {	29✔
224	better = true;	×
225	equal = false;	×
226	break;	×
227	} else if (max_stride_count == best_max_stride_count) {	29✔
228	continue;	27✔
229	} else {	27✔
230	equal = false;	2✔
231	break;	2✔
232	}	2✔
233	} else {	39✔
234	equal = false;	39✔
235	break;	39✔
236	}	39✔
237	}	105✔
238	if (better) {	82✔
239	best_permutation = current;	37✔
240	best_scores = scores;	37✔
241	} else if (equal) {	45✔
242	// If equal and original permutation
243	if (std::equal(current.begin(), current.end(), permutation.begin())) {	4✔
244	best_permutation = current;	×
245	best_scores = scores;	×
246	}	×
247	}	4✔
248	}	82✔
249	} while (std::next_permutation(current.begin(), current.end()));	378✔
250
251	// Check if permutation is better than original
252	return {best_permutation != permutation, best_permutation};	×
253	};	89✔
254
255	void StrideMinimization::apply(
256	builder::StructuredSDFGBuilder& builder,
257	analysis::AnalysisManager& analysis_manager,
258	std::vector<structured_control_flow::ControlFlowNode*>& nested_loops,
259	std::vector<std::string> target_permutation
260	) {	11✔
261	size_t while_loops = 0;	11✔
262	std::vector<std::string> permutation;	11✔
263	for (auto& loop : nested_loops) {	31✔
264	if (!dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	31✔
265	permutation.push_back("WHILE_" + std::to_string(while_loops++));	×
266	} else {	31✔
267	auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop);	31✔
268	permutation.push_back(for_loop->indvar()->get_name());	31✔
269	}	31✔
270	}	31✔
271	std::vector<size_t> permutation_indices;	11✔
272	for (auto& p : permutation) {	31✔
273	auto it = std::find(target_permutation.begin(), target_permutation.end(), p);	31✔
274	permutation_indices.push_back(std::distance(target_permutation.begin(), it));	31✔
275	}	31✔
276
277	// Bubble sort permutation indices
278	for (size_t i = 0; i < permutation_indices.size(); i++) {	42✔
279	for (size_t j = 0; j < permutation_indices.size() - i - 1; j++) {	61✔
280	if (permutation_indices[j] > permutation_indices[j + 1]) {	30✔
281	auto first_loop = static_cast<structured_control_flow::StructuredLoop*>(nested_loops.at(j));	11✔
282	auto second_loop = static_cast<structured_control_flow::StructuredLoop*>(nested_loops.at(j + 1));	11✔
283	transformations::LoopInterchange loop_interchange(first_loop, second_loop);	11✔
284	// given that the permutation is admissible, the interchange must be applicable, else the permutation
285	// would not be admissible
286	loop_interchange.apply(builder, analysis_manager);	11✔
287	std::swap(permutation_indices[j], permutation_indices[j + 1]);	11✔
288	}	11✔
289	}	30✔
290	}	31✔
291	};	11✔
292
293	std::string StrideMinimization::name() { return "StrideMinimization"; };	×
294
295	bool StrideMinimization::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	43✔
296	bool applied = false;	43✔
297
298	auto& loop_tree_analysis = analysis_manager.get<analysis::LoopAnalysis>();	43✔
299
300	// Collect outermost loops
301	std::vector<structured_control_flow::ControlFlowNode*> outer_loops = loop_tree_analysis.outermost_loops();	43✔
302
303	std::unordered_map<	43✔
304	structured_control_flow::ControlFlowNode*,	43✔
305	std::vector<std::pair<std::vector<std::string>, std::vector<structured_control_flow::ControlFlowNode*>>>>	43✔
306	loop_permutations;	43✔
307
308	// Find loop nests for stride minimization
309	for (auto& outer_loop : outer_loops) {	97✔
310	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	97✔
311	auto paths = loop_analysis.loop_tree_paths(outer_loop);	97✔
312	for (auto& path : paths) {	110✔
313	auto [applicable, permutation] = this->can_be_applied(builder, analysis_manager, path);	110✔
314	if (applicable) {	110✔
315	if (loop_permutations.find(path.at(0)) == loop_permutations.end()) {	12✔
316	loop_permutations.insert({path.at(0), {}});	11✔
317	}	11✔
318	loop_permutations[path.at(0)].push_back({permutation, path});	12✔
319	}	12✔
320	}	110✔
321	}	97✔
322
323	// Apply stride minimization
324	for (auto& [loop, permutations] : loop_permutations) {	43✔
325	auto& permutation = permutations.at(0).first;	11✔
326	auto& path = permutations.at(0).second;	11✔
327
328	this->apply(builder, analysis_manager, path, permutation);	11✔
329	applied = true;	11✔
330	}	11✔
331	return applied;	43✔
332	};	43✔
333
334	} // namespace normalization
335	} // namespace passes
336	} // namespace sdfg

daisytuner / docc / 28809522800

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