15049122732

Committed 15 May 2025 03:33PM UTC coverage: 62.241% (+4.7%) from 57.525%

Build # 15049122732

Build Type

Pull #9

github

Committed by

web-flow

Commit Message

Merge b96e33e0e into 9d3b1a2b3

Pull Request Pull Request #9: Graphviz DOT Visualizer for SDFGs

Run Details

520 of 542 new or added lines in 3 files covered. (95.94%)

782 existing lines in 68 files now uncovered.

8049 of 12932 relevant lines covered (62.24%)

504.09 hits per line

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

93.15

/src/passes/schedule/stride_minimization.cpp

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

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/data_parallelism_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/transformations/loop_interchange.h"

namespace sdfg {
namespace passes {

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(
    Schedule& schedule, std::vector<structured_control_flow::ControlFlowNode*>& nested_loops) {
    auto& builder = schedule.builder();

    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::For*>(nested_loops.at(i));
            auto second_loop = dynamic_cast<structured_control_flow::For*>(nested_loops.at(i + 1));
            auto& parent = builder.parent(*first_loop);
            transformations::LoopInterchange loop_interchange(parent, *first_loop, *second_loop);
            if (loop_interchange.can_be_applied(schedule)) {
                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(
    Schedule& schedule, std::vector<structured_control_flow::ControlFlowNode*>& nested_loops) {
    if (nested_loops.size() < 2) {
        return {false, {}};
    }
    auto& builder = schedule.builder();
    auto& sdfg = builder.subject();

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

    auto admissible_swaps = allowed_swaps(schedule, nested_loops);

    // Collect all memory accesses of body
    structured_control_flow::ControlFlowNode* nested_root = nullptr;
    if (auto for_loop = dynamic_cast<structured_control_flow::For*>(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& analysis_manager = schedule.analysis_manager();
    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);
        }
    }

    // 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 (auto& var : current) {
            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(Schedule& schedule,
                               std::vector<structured_control_flow::ControlFlowNode*>& nested_loops,
                               std::vector<std::string> target_permutation) {
    auto& builder = schedule.builder();

    size_t while_loops = 0;
    std::vector<std::string> permutation;
    for (auto& loop : nested_loops) {
        if (!dynamic_cast<structured_control_flow::For*>(loop)) {
            permutation.push_back("WHILE_" + std::to_string(while_loops++));
        } else {
            auto for_loop = dynamic_cast<structured_control_flow::For*>(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::For*>(nested_loops.at(j));
                auto second_loop =
                    static_cast<structured_control_flow::For*>(nested_loops.at(j + 1));
                auto& parent = builder.parent(*first_loop);
                transformations::LoopInterchange loop_interchange(parent, *first_loop,
                                                                  *second_loop);
                if (!loop_interchange.can_be_applied(schedule)) {
                    throw std::runtime_error("Loop interchange cannot be applied");
                }
                loop_interchange.apply(schedule);
                std::swap(permutation_indices[j], permutation_indices[j + 1]);
            }
        }
    }
};

std::vector<structured_control_flow::ControlFlowNode*> StrideMinimization::children(
    structured_control_flow::ControlFlowNode* node,
    const std::unordered_map<structured_control_flow::ControlFlowNode*,
                             structured_control_flow::ControlFlowNode*>& tree) const {
    // Find unique child
    std::vector<structured_control_flow::ControlFlowNode*> c;
    for (auto& entry : tree) {
        if (entry.second == node) {
            c.push_back(entry.first);
        }
    }
    return c;
};

std::list<std::vector<structured_control_flow::ControlFlowNode*>>
StrideMinimization::loop_tree_paths(
    structured_control_flow::ControlFlowNode* loop,
    const std::unordered_map<structured_control_flow::ControlFlowNode*,
                             structured_control_flow::ControlFlowNode*>& tree) const {
    // Collect all paths in tree starting from loop recursively (DFS)
    std::list<std::vector<structured_control_flow::ControlFlowNode*>> paths;
    auto children = this->children(loop, tree);
    if (children.empty()) {
        paths.push_back({loop});
        return paths;
    }

    for (auto& child : children) {
        auto p = this->loop_tree_paths(child, tree);
        for (auto& path : p) {
            path.insert(path.begin(), loop);
            paths.push_back(path);
        }
    }

    return paths;
};

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

bool StrideMinimization::run_pass(Schedule& schedule) {
    bool applied = false;

    // Compute loop tree
    auto tree = schedule.loop_tree();

    // Collect outermost loops
    std::list<structured_control_flow::ControlFlowNode*> outer_loops;
    for (auto& node : tree) {
        if (node.second == nullptr) {
            outer_loops.push_back(node.first);
        }
    }

    // Apply stride minimization
    for (auto& outer_loop : outer_loops) {
        auto paths = this->loop_tree_paths(outer_loop, tree);
        for (auto& path : paths) {
            auto [applicable, permutation] = this->can_be_applied(schedule, path);
            if (applicable) {
                this->apply(schedule, path, permutation);
                applied = true;
                break;
            }
        }
    }

    return applied;
};

}  // namespace passes
}  // namespace sdfg

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

daisytuner / sdfglib / 15049122732

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