16861237397

Committed 10 Aug 2025 12:12PM UTC coverage: 64.492% (+0.006%) from 64.486%

Build # 16861237397

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #185 from daisytuner/memlets-tasklets

References and Memlets: Validation

Run Details

102 of 146 new or added lines in 7 files covered. (69.86%)

2 existing lines in 1 file now uncovered.

8965 of 13901 relevant lines covered (64.49%)

124.44 hits per line

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

78.74

/src/passes/dataflow/reference_propagation.cpp

#include "sdfg/passes/dataflow/reference_propagation.h"

#include "sdfg/analysis/users.h"
#include "sdfg/types/utils.h"

namespace sdfg {
namespace passes {

ReferencePropagation::ReferencePropagation()
    : Pass() {

      };

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

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

    auto& sdfg = builder.subject();

    // Replaces all views
    auto& users = analysis_manager.get<analysis::Users>();
    std::unordered_set<std::string> reduced;
    for (auto& container : sdfg.containers()) {
        if (reduced.find(container) != reduced.end()) {
            continue;
        }
        if (!sdfg.is_transient(container)) {
            continue;
        }

        // By definition, a view is a pointer
        auto& type = sdfg.type(container);
        if (type.type_id() != types::TypeID::Pointer) {
            continue;
        }

        // Criterion: Must have at least one move
        auto moves = users.moves(container);
        if (moves.empty()) {
            continue;
        }

        // Criterion: No sub-views (will be eliminated iteratively)
        if (users.views(container).size() > 0) {
            continue;
        }

        // Eliminate views
        auto uses = users.uses(container);
        for (auto& move : moves) {
            auto& access_node = static_cast<data_flow::AccessNode&>(*move->element());
            auto& dataflow = *move->parent();
            auto& move_edge = *dataflow.in_edges(access_node).begin();

            // Criterion: Must be a reference memlet
            if (move_edge.type() != data_flow::MemletType::Reference) {
                continue;
            }

            // Retrieve underlying container
            auto& viewed_node = static_cast<const data_flow::AccessNode&>(move_edge.src());
            auto& viewed_container = viewed_node.data();

            // Criterion: Must not be constant data
            if (helpers::is_number(viewed_container) || symbolic::is_nullptr(symbolic::symbol(viewed_container))) {
                continue;
            }

            // Criterion: Must not be address of
            auto& move_subset = move_edge.subset();
            if (move_subset.empty()) {
                continue;
            }

            // Replace all uses of the view by the pointer
            for (auto& user : uses) {
                // Criterion: Must be an access node
                if (!dynamic_cast<data_flow::AccessNode*>(user->element())) {
                    continue;
                }

                // Criterion: Must be dominated by the move
                if (!users.dominates(*move, *user)) {
                    continue;
                }
                // Criterion: Pointer and view are constant
                auto uses_between = users.all_uses_between(*move, *user);
                bool unsafe = false;
                for (auto& use : uses_between) {
                    if (use->use() != analysis::Use::MOVE) {
                        continue;
                    }
                    // Pointer is not constant
                    if (use->container() == viewed_container) {
                        unsafe = true;
                        break;
                    }
                    // View is reassigned
                    if (use->container() == container) {
                        unsafe = true;
                        break;
                    }
                }
                if (unsafe) {
                    continue;
                }

                auto& use_node = static_cast<data_flow::AccessNode&>(*user->element());

                // Criterion: Must be a typed-pointer at this point, no empty subset / constant data
                auto& base_type = move_edge.base_type();
                auto& pointer_type = dynamic_cast<const types::Pointer&>(base_type);

                // Criterion: Must strictly propagate into computational memlets
                // Criterion: Types must match
                auto use_graph = user->parent();

                auto& result_base_type = types::infer_type(builder.subject(), move_edge.base_type(), move_subset);
                sdfg::types::Pointer result_type(static_cast<const types::IType&>(result_base_type));

                bool safe = true;
                for (auto& oedge : use_graph->out_edges(use_node)) {
                    if (oedge.type() != data_flow::MemletType::Computational || oedge.has_range()) {
                        safe = false;
                        break;
                    }
                    if (result_base_type.type_id() != types::TypeID::Pointer && oedge.base_type() != result_type) {
                        safe = false;
                        break;
                    }
                }
                if (!safe) {
                    continue;
                }
                for (auto& iedge : use_graph->in_edges(use_node)) {
                    if (iedge.type() != data_flow::MemletType::Computational || iedge.has_range()) {
                        safe = false;
                        break;
                    }
                    if (result_base_type.type_id() != types::TypeID::Pointer && iedge.base_type() != result_type) {
                        safe = false;
                        break;
                    }
                }
                if (!safe) {
                    continue;
                }

                // Propagate pointer type

                // Step 1: Replace container
                use_node.data() = viewed_container;

                // Step 2: Update edges
                for (auto& oedge : use_graph->out_edges(use_node)) {
                    // Compute new subset
                    data_flow::Subset new_subset;
                    for (auto dim : move_subset) {
                        new_subset.push_back(dim);
                    }

                    auto old_subset = oedge.subset();

                    // Handle first trailing dimensions
                    auto& trail_dim = old_subset.front();
                    auto& current_dim = new_subset.back();
                    auto new_dim = symbolic::add(current_dim, trail_dim);
                    new_subset.back() = new_dim;
                    old_subset.erase(old_subset.begin());

                    // Add remaining trailing dimensions
                    for (auto dim : old_subset) {
                        new_subset.push_back(dim);
                    }

                    // Build new type
                    if (move_subset.size() == 1) {
                        oedge.set_subset(new_subset);
                    } else {
                        // Case 2: multi-dimensional subset
                        oedge.set_subset(new_subset);
                        oedge.set_base_type(move_edge.base_type());
                    }
                }

                for (auto& iedge : use_graph->in_edges(use_node)) {
                    // Compute new subset
                    data_flow::Subset new_subset;
                    for (auto dim : move_subset) {
                        new_subset.push_back(dim);
                    }

                    auto old_subset = iedge.subset();

                    // Handle first trailing dimensions
                    auto& trail_dim = old_subset.front();
                    auto& current_dim = new_subset.back();
                    auto new_dim = symbolic::add(current_dim, trail_dim);
                    new_subset.back() = new_dim;
                    old_subset.erase(old_subset.begin());

                    // Add remaining trailing dimensions
                    for (auto dim : old_subset) {
                        new_subset.push_back(dim);
                    }

                    // Case 1: 1D subset, "original pointer is shifted"
                    if (move_subset.size() == 1) {
                        iedge.set_subset(new_subset);
                    } else {
                        // Case 2: multi-dimensional subset
                        iedge.set_subset(new_subset);
                        iedge.set_base_type(move_edge.base_type());
                    }
                }

                applied = true;
                reduced.insert(viewed_container);
            }
        }
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/dataflow/reference_propagation.h"
2
3	#include "sdfg/analysis/users.h"
4	#include "sdfg/types/utils.h"
5
6	namespace sdfg {
7	namespace passes {
8
9	ReferencePropagation::ReferencePropagation()	5✔
10	: Pass() {	5✔
11
12	};	5✔
13
14	std::string ReferencePropagation::name() { return "ReferencePropagation"; };	×
15
16	bool ReferencePropagation::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	4✔
17	bool applied = false;	4✔
18
19	auto& sdfg = builder.subject();	4✔
20
21	// Replaces all views
22	auto& users = analysis_manager.get<analysis::Users>();	4✔
23	std::unordered_set<std::string> reduced;	4✔
24	for (auto& container : sdfg.containers()) {	12✔
25	if (reduced.find(container) != reduced.end()) {	8✔
26	continue;	2✔
27	}
28	if (!sdfg.is_transient(container)) {	6✔
29	continue;	2✔
30	}
31
32	// By definition, a view is a pointer
33	auto& type = sdfg.type(container);	4✔
34	if (type.type_id() != types::TypeID::Pointer) {	4✔
35	continue;	×
36	}
37
38	// Criterion: Must have at least one move
39	auto moves = users.moves(container);	4✔
40	if (moves.empty()) {	4✔
41	continue;	1✔
42	}
43
44	// Criterion: No sub-views (will be eliminated iteratively)
45	if (users.views(container).size() > 0) {	3✔
46	continue;	×
47	}
48
49	// Eliminate views
50	auto uses = users.uses(container);	3✔
51	for (auto& move : moves) {	6✔
52	auto& access_node = static_cast<data_flow::AccessNode&>(*move->element());	3✔
53	auto& dataflow = *move->parent();	3✔
54	auto& move_edge = *dataflow.in_edges(access_node).begin();	3✔
55
56	// Criterion: Must be a reference memlet
57	if (move_edge.type() != data_flow::MemletType::Reference) {	3✔
58	continue;	1✔
59	}
60
61	// Retrieve underlying container
62	auto& viewed_node = static_cast<const data_flow::AccessNode&>(move_edge.src());	2✔
63	auto& viewed_container = viewed_node.data();	2✔
64
65	// Criterion: Must not be constant data
66	if (helpers::is_number(viewed_container) \|\| symbolic::is_nullptr(symbolic::symbol(viewed_container))) {	2✔
67	continue;	×
68	}
69
70	// Criterion: Must not be address of
71	auto& move_subset = move_edge.subset();	2✔
72	if (move_subset.empty()) {	2✔
73	continue;	×
74	}
75
76	// Replace all uses of the view by the pointer
77	for (auto& user : uses) {	8✔
78	// Criterion: Must be an access node
79	if (!dynamic_cast<data_flow::AccessNode*>(user->element())) {	6✔
NEW 80	continue;	×
81	}
82
83	// Criterion: Must be dominated by the move
84	if (!users.dominates(move, user)) {	6✔
85	continue;	2✔
86	}
87	// Criterion: Pointer and view are constant
88	auto uses_between = users.all_uses_between(move, user);	4✔
89	bool unsafe = false;	4✔
90	for (auto& use : uses_between) {	6✔
91	if (use->use() != analysis::Use::MOVE) {	2✔
92	continue;	2✔
93	}
94	// Pointer is not constant
95	if (use->container() == viewed_container) {	×
96	unsafe = true;	×
97	break;	×
98	}
99	// View is reassigned
100	if (use->container() == container) {	×
101	unsafe = true;	×
102	break;	×
103	}
104	}
105	if (unsafe) {	4✔
106	continue;	×
107	}
108
109	auto& use_node = static_cast<data_flow::AccessNode&>(*user->element());	4✔
110
111	// Criterion: Must be a typed-pointer at this point, no empty subset / constant data
112	auto& base_type = move_edge.base_type();	4✔
113	auto& pointer_type = dynamic_cast<const types::Pointer&>(base_type);	4✔
114
115	// Criterion: Must strictly propagate into computational memlets
116	// Criterion: Types must match
117	auto use_graph = user->parent();	4✔
118
119	auto& result_base_type = types::infer_type(builder.subject(), move_edge.base_type(), move_subset);	4✔
120	sdfg::types::Pointer result_type(static_cast<const types::IType&>(result_base_type));	4✔
121
122	bool safe = true;	4✔
123	for (auto& oedge : use_graph->out_edges(use_node)) {	6✔
124	if (oedge.type() != data_flow::MemletType::Computational \|\| oedge.has_range()) {	2✔
NEW 125	safe = false;	×
NEW 126	break;	×
127	}
128	if (result_base_type.type_id() != types::TypeID::Pointer && oedge.base_type() != result_type) {	2✔
NEW 129	safe = false;	×
UNCOV 130	break;	×
131	}
132	}
133	if (!safe) {	4✔
134	continue;	×
135	}
136	for (auto& iedge : use_graph->in_edges(use_node)) {	6✔
137	if (iedge.type() != data_flow::MemletType::Computational \|\| iedge.has_range()) {	2✔
NEW 138	safe = false;	×
NEW 139	break;	×
140	}
141	if (result_base_type.type_id() != types::TypeID::Pointer && iedge.base_type() != result_type) {	2✔
NEW 142	safe = false;	×
UNCOV 143	break;	×
144	}
145	}
146	if (!safe) {	4✔
147	continue;	×
148	}
149
150	// Propagate pointer type
151
152	// Step 1: Replace container
153	use_node.data() = viewed_container;	4✔
154
155	// Step 2: Update edges
156	for (auto& oedge : use_graph->out_edges(use_node)) {	6✔
157	// Compute new subset
158	data_flow::Subset new_subset;	2✔
159	for (auto dim : move_subset) {	5✔
160	new_subset.push_back(dim);	3✔
161	}	3✔
162
163	auto old_subset = oedge.subset();	2✔
164
165	// Handle first trailing dimensions
166	auto& trail_dim = old_subset.front();	2✔
167	auto& current_dim = new_subset.back();	2✔
168	auto new_dim = symbolic::add(current_dim, trail_dim);	2✔
169	new_subset.back() = new_dim;	2✔
170	old_subset.erase(old_subset.begin());	2✔
171
172	// Add remaining trailing dimensions
173	for (auto dim : old_subset) {	2✔
174	new_subset.push_back(dim);	×
175	}	×
176
177	// Build new type
178	if (move_subset.size() == 1) {	2✔
179	oedge.set_subset(new_subset);	1✔
180	} else {	1✔
181	// Case 2: multi-dimensional subset
182	oedge.set_subset(new_subset);	1✔
183	oedge.set_base_type(move_edge.base_type());	1✔
184	}
185	}	2✔
186
187	for (auto& iedge : use_graph->in_edges(use_node)) {	6✔
188	// Compute new subset
189	data_flow::Subset new_subset;	2✔
190	for (auto dim : move_subset) {	5✔
191	new_subset.push_back(dim);	3✔
192	}	3✔
193
194	auto old_subset = iedge.subset();	2✔
195
196	// Handle first trailing dimensions
197	auto& trail_dim = old_subset.front();	2✔
198	auto& current_dim = new_subset.back();	2✔
199	auto new_dim = symbolic::add(current_dim, trail_dim);	2✔
200	new_subset.back() = new_dim;	2✔
201	old_subset.erase(old_subset.begin());	2✔
202
203	// Add remaining trailing dimensions
204	for (auto dim : old_subset) {	2✔
205	new_subset.push_back(dim);	×
206	}	×
207
208	// Case 1: 1D subset, "original pointer is shifted"
209	if (move_subset.size() == 1) {	2✔
210	iedge.set_subset(new_subset);	1✔
211	} else {	1✔
212	// Case 2: multi-dimensional subset
213	iedge.set_subset(new_subset);	1✔
214	iedge.set_base_type(move_edge.base_type());	1✔
215	}
216	}	2✔
217
218	applied = true;	4✔
219	reduced.insert(viewed_container);	4✔
220	}	4✔
221	}	2✔
222	}	4✔
223
224	return applied;	4✔
225	};	4✔
226
227	} // namespace passes
228	} // namespace sdfg

daisytuner / sdfglib / 16861237397

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