18651924023

Committed 20 Oct 2025 12:26PM UTC coverage: 60.977% (-0.6%) from 61.539%

Build # 18651924023

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #286 from daisytuner/reserved-names

removes restricted globals filtering in codegen

Run Details

8 of 20 new or added lines in 2 files covered. (40.0%)

342 existing lines in 17 files now uncovered.

9174 of 15045 relevant lines covered (60.98%)

92.1 hits per line

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

71.64

/src/passes/dataflow/reference_propagation.cpp

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

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

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

        auto move_groups = reference_analysis.defined_by(container);
        for (auto& entry : move_groups) {
            // If not exclusive write, skip
            if (entry.second.size() != 1) {
                continue;
            }
            auto move = *entry.second.begin();
            auto user = entry.first;

            // Criterion: Must be moved by reference memlet
            auto& access_node = static_cast<data_flow::AccessNode&>(*move->element());
            auto& dataflow = access_node.get_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();

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

daisytuner / sdfglib / 18651924023

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