18426522156

Committed 11 Oct 2025 07:46AM UTC coverage: 61.266% (+0.001%) from 61.265%

Build # 18426522156

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #268 from daisytuner/reference-prop

extends reference propagation for dereference props

Run Details

22 of 22 new or added lines in 1 file covered. (100.0%)

5 existing lines in 1 file now uncovered.

9003 of 14695 relevant lines covered (61.27%)

103.77 hits per line

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

76.47

/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;
        }

        // 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: Cannot be a move
                if (user->use() == analysis::Use::MOVE) {
                    continue;
                }

                // 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: No reassignment of pointer or view in between
                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& user_node = static_cast<data_flow::AccessNode&>(*user->element());

                // Simple case: No arithmetic on pointer, just replace container
                if (move_subset.size() == 1 && symbolic::eq(move_subset[0], symbolic::zero())) {
                    user_node.data() = viewed_container;
                    applied = true;
                    reduced.insert(viewed_container);
                    continue;
                }

                // General case: Arithmetic on pointer, need to update memlet subsets

                // Criterion: Must be computational memlets
                // Criterion: No type casting

                auto& deref_type = move_edge.result_type(builder.subject());
                sdfg::types::Pointer ref_type(static_cast<const types::IType&>(deref_type));

                bool safe = true;
                auto user_graph = user->parent();
                for (auto& oedge : user_graph->out_edges(user_node)) {
                    if (oedge.type() != data_flow::MemletType::Computational) {
                        safe = false;
                        break;
                    }
                    if (oedge.subset().empty()) {
                        safe = false;
                        break;
                    }
                    if (oedge.base_type() != ref_type) {
                        safe = false;
                        break;
                    }
                }
                if (!safe) {
                    continue;
                }
                for (auto& iedge : user_graph->in_edges(user_node)) {
                    if (iedge.type() != data_flow::MemletType::Computational) {
                        safe = false;
                        break;
                    }
                    if (iedge.subset().empty()) {
                        safe = false;
                        break;
                    }
                    if (iedge.base_type() != ref_type) {
                        safe = false;
                        break;
                    }
                }
                if (!safe) {
                    continue;
                }

                // Propagate pointer type

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

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

daisytuner / sdfglib / 18426522156

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