18558780296

Committed 16 Oct 2025 10:49AM UTC coverage: 61.233% (-0.3%) from 61.523%

Build # 18558780296

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #279 from daisytuner/ext-prefix

Separate Dominance Analysis and Codegen for Linker with Prefixes

Run Details

62 of 95 new or added lines in 26 files covered. (65.26%)

13 existing lines in 7 files now uncovered.

8981 of 14667 relevant lines covered (61.23%)

98.73 hits per line

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

76.64

/src/passes/dataflow/reference_propagation.cpp

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

#include "sdfg/analysis/users.h"
#include "sdfg/analysis/dominance_analysis.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 = analysis_manager.get<analysis::Users>();
    auto& dominance_analysis = analysis_manager.get<analysis::DominanceAnalysis>();

    std::unordered_set<std::string> invalidated;
    for (auto& container : sdfg.containers()) {
        if (invalidated.find(container) != invalidated.end()) {
            continue;
        }

        // Criterion: Must be a transient pointer
        if (!sdfg.is_transient(container)) {
            continue;
        }
        auto& type = sdfg.type(container);
        if (type.type_id() != types::TypeID::Pointer) {
            continue;
        }

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

        // Eliminate views
        for (auto& move : moves) {
            // Criterion: Must be moved by reference memlet
            auto& access_node = static_cast<data_flow::AccessNode&>(*move->element());
            auto& dataflow = *move->parent();
            auto& move_edge = *dataflow.in_edges(access_node).begin();
            if (move_edge.type() != data_flow::MemletType::Reference) {
                continue;
            }
            // Criterion: Cannot be address of (&<scalar_type>)
            auto& move_subset = move_edge.subset();
            if (move_subset.empty()) {
                continue;
            }

            // Criterion: Must be viewing another container
            auto& viewed_node = static_cast<const data_flow::AccessNode&>(move_edge.src());
            if (dynamic_cast<const data_flow::ConstantNode*>(&viewed_node) != nullptr) {
                continue;
            }
            auto& viewed_container = viewed_node.data();

            // Replace all uses of the view by the pointer
            auto uses = users_analysis.uses(container);
            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 (!dominance_analysis.dominates(*move, *user)) {
                    continue;
                }

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

daisytuner / sdfglib / 18558780296

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