20147202960

Committed 11 Dec 2025 08:57PM UTC coverage: 40.181% (-0.09%) from 40.268%

Build # 20147202960

Build Type

push

github

Committed by

lukastruemper

Commit Message

removes timing outputs of passes

Run Details

13596 of 43795 branches covered (31.04%)

Branch coverage included in aggregate %.

11609 of 18933 relevant lines covered (61.32%)

93.45 hits per line

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

64.05

/src/passes/dataflow/reference_propagation.cpp

#include "sdfg/passes/dataflow/reference_propagation.h"
#include <unordered_set>

#include "sdfg/analysis/dominance_analysis.h"
#include "sdfg/analysis/reference_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/data_flow/access_node.h"
#include "sdfg/data_flow/memlet.h"
#include "sdfg/data_flow/tasklet.h"
#include "sdfg/element.h"
#include "sdfg/exceptions.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/types/utils.h"

namespace sdfg {
namespace passes {

bool ReferencePropagation::
    compatible_type(const Function& function, const data_flow::Memlet& reference, const data_flow::Memlet& target) {
    auto& ref_type = reference.base_type();
    if (ref_type.type_id() != types::TypeID::Pointer) {
        return false;
    }
    auto& ref_pointer_type = static_cast<const types::Pointer&>(ref_type);
    if (ref_pointer_type.pointee_type().type_id() != types::TypeID::Array &&
        ref_pointer_type.pointee_type().type_id() != types::TypeID::Structure) {
        return false;
    }
    auto& ref_subset = reference.subset();

    auto& tar_type = target.base_type();
    if (tar_type.type_id() != types::TypeID::Pointer) {
        return false;
    }
    auto& tar_pointer_type = static_cast<const types::Pointer&>(tar_type);
    if (tar_pointer_type.pointee_type().type_id() != types::TypeID::Scalar) {
        return false;
    }
    auto& tar_subset = target.subset();

    // Check if trailing zeros yield compatible type
    for (auto dim : tar_subset) {
        if (!symbolic::eq(dim, symbolic::zero())) {
            return false;
        }
    }
    auto expanded_subset = ref_subset;
    for (auto& dim : tar_subset) {
        expanded_subset.push_back(dim);
    }
    try {
        auto& new_res_type = types::infer_type(function, ref_type, expanded_subset);
        auto& tar_res_type = target.result_type(function);
        return new_res_type == tar_res_type;
    } catch (const InvalidSDFGException&) {
        return false;
    }
}

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<data_flow::AccessNode*> replaced_nodes;
    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);
                replaced_nodes.insert(&user_node);
                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 &&
                    oedge.type() != data_flow::MemletType::Reference) {
                    safe = false;
                    break;
                }
                auto& old_subset = oedge.subset();
                if (old_subset.empty()) {
                    safe = false;
                    break;
                }
                if (oedge.base_type() != ref_type) {
                    // Special case: compatible pointer types
                    if (!compatible_type(builder.subject(), move_edge, oedge)) {
                        safe = false;
                        break;
                    }
                }
            }
            if (!safe) {
                continue;
            }
            for (auto& iedge : user_graph.in_edges(user_node)) {
                if (iedge.type() != data_flow::MemletType::Computational &&
                    iedge.type() != data_flow::MemletType::Reference) {
                    safe = false;
                    break;
                }
                auto& old_subset = iedge.subset();
                if (old_subset.empty()) {
                    safe = false;
                    break;
                }
                if (iedge.base_type() != ref_type) {
                    if (!compatible_type(builder.subject(), move_edge, iedge)) {
                        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();

                if (oedge.base_type() != ref_type) {
                    for (auto& dim : old_subset) {
                        new_subset.push_back(dim);
                    }
                } else {
                    // 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
                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();
                if (iedge.base_type() != ref_type) {
                    for (auto& dim : old_subset) {
                        new_subset.push_back(dim);
                    }
                } else {
                    // 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);
                    }
                }

                iedge.set_subset(new_subset);
                iedge.set_base_type(move_edge.base_type());
            }

            applied = true;
            invalidated.insert(viewed_container);
            replaced_nodes.insert(&user_node);
        }
    }

    // Post-processing: Merge access nodes and remove dangling nodes
    // Avoid removing elements while iterating above
    for (auto* node : replaced_nodes) {
        builder.merge_siblings(*node);
    }
    for (auto* node : replaced_nodes) {
        auto& graph = node->get_parent();
        auto* block = static_cast<structured_control_flow::Block*>(graph.get_parent());
        for (auto& dnode : graph.data_nodes()) {
            if (graph.in_degree(*dnode) == 0 && graph.out_degree(*dnode) == 0) {
                builder.remove_node(*block, *dnode);
            }
        }
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/dataflow/reference_propagation.h"
2	#include <unordered_set>
3
4	#include "sdfg/analysis/dominance_analysis.h"
5	#include "sdfg/analysis/reference_analysis.h"
6	#include "sdfg/analysis/users.h"
7	#include "sdfg/data_flow/access_node.h"
8	#include "sdfg/data_flow/memlet.h"
9	#include "sdfg/data_flow/tasklet.h"
10	#include "sdfg/element.h"
11	#include "sdfg/exceptions.h"
12	#include "sdfg/structured_control_flow/block.h"
13	#include "sdfg/types/utils.h"
14
15	namespace sdfg {
16	namespace passes {
17
18	bool ReferencePropagation::
19	compatible_type(const Function& function, const data_flow::Memlet& reference, const data_flow::Memlet& target) {	6✔
20	auto& ref_type = reference.base_type();	6✔
21	if (ref_type.type_id() != types::TypeID::Pointer) {	6!
22	return false;	×
23	}
24	auto& ref_pointer_type = static_cast<const types::Pointer&>(ref_type);	6✔
25	if (ref_pointer_type.pointee_type().type_id() != types::TypeID::Array &&	6!
26	ref_pointer_type.pointee_type().type_id() != types::TypeID::Structure) {	4✔
27	return false;	×
28	}
29	auto& ref_subset = reference.subset();	6✔
30
31	auto& tar_type = target.base_type();	6!
32	if (tar_type.type_id() != types::TypeID::Pointer) {	6!
33	return false;	×
34	}
35	auto& tar_pointer_type = static_cast<const types::Pointer&>(tar_type);	6✔
36	if (tar_pointer_type.pointee_type().type_id() != types::TypeID::Scalar) {	6!
37	return false;	×
38	}
39	auto& tar_subset = target.subset();	6!
40
41	// Check if trailing zeros yield compatible type
42	for (auto dim : tar_subset) {	12!
43	if (!symbolic::eq(dim, symbolic::zero())) {	6!
44	return false;	×
45	}
46	}	6!
47	auto expanded_subset = ref_subset;	6!
48	for (auto& dim : tar_subset) {	12✔
49	expanded_subset.push_back(dim);	6!
50	}
51	try {
52	auto& new_res_type = types::infer_type(function, ref_type, expanded_subset);	6!
53	auto& tar_res_type = target.result_type(function);	6!
54	return new_res_type == tar_res_type;	6!
55	} catch (const InvalidSDFGException&) {	×
56	return false;	×
57	}	×
58	}	6✔
59
60	ReferencePropagation::ReferencePropagation()	14✔
61	: Pass() {	14✔
62
63	};	14✔
64
65	std::string ReferencePropagation::name() { return "ReferencePropagation"; };	×
66
67	bool ReferencePropagation::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	13✔
68	bool applied = false;	13✔
69
70	auto& sdfg = builder.subject();	13✔
71
72	// Replaces all views
73	auto& users_analysis = analysis_manager.get<analysis::Users>();	13✔
74	auto& dominance_analysis = analysis_manager.get<analysis::DominanceAnalysis>();	13✔
75	auto& reference_analysis = analysis_manager.get<analysis::ReferenceAnalysis>();	13✔
76
77	std::unordered_set<data_flow::AccessNode*> replaced_nodes;	13✔
78	std::unordered_set<std::string> invalidated;	13✔
79	for (auto& container : sdfg.containers()) {	44!
80	if (invalidated.find(container) != invalidated.end()) {	31!
81	continue;	9✔
82	}
83
84	// Criterion: Must be a transient pointer
85	if (!sdfg.is_transient(container)) {	22!
86	continue;	6✔
87	}
88	auto& type = sdfg.type(container);	16!
89	if (type.type_id() != types::TypeID::Pointer) {	16!
90	continue;	×
91	}
92
93	auto move_groups = reference_analysis.defined_by(container);	16!
94	for (auto& entry : move_groups) {	33✔
95	// If not exclusive write, skip
96	if (entry.second.size() != 1) {	17!
97	continue;	×
98	}
99	auto move = *entry.second.begin();	17✔
100	auto user = entry.first;	17✔
101
102	// Criterion: Must be moved by reference memlet
103	auto& access_node = static_cast<data_flow::AccessNode&>(*move->element());	17!
104	auto& dataflow = access_node.get_parent();	17!
105	auto& move_edge = *dataflow.in_edges(access_node).begin();	17!
106	if (move_edge.type() != data_flow::MemletType::Reference) {	17!
107	continue;	×
108	}
109	// Criterion: Cannot be address of (&<scalar_type>)
110	auto& move_subset = move_edge.subset();	17!
111	if (move_subset.empty()) {	17!
112	continue;	×
113	}
114
115	// Criterion: Must be viewing another container
116	auto& viewed_node = static_cast<const data_flow::AccessNode&>(move_edge.src());	17!
117	if (dynamic_cast<const data_flow::ConstantNode*>(&viewed_node) != nullptr) {	17!
118	continue;	×
119	}
120	auto& viewed_container = viewed_node.data();	17!
121
122	// Criterion: Must be an access node
123	if (!dynamic_cast<data_flow::AccessNode*>(user->element())) {	17!
124	continue;	×
125	}
126
127	// Criterion: Must be dominated by the move
128	if (!dominance_analysis.dominates(move, user)) {	17!
129	continue;	×
130	}
131
132	// Criterion: No reassignment of pointer or view in between
133	if (users_analysis.moves(viewed_container).size() > 0) {	17!
134	auto uses_between = users_analysis.all_uses_between(move, user);	2!
135	bool unsafe = false;	2✔
136	for (auto& use : uses_between) {	2!
137	if (use->use() != analysis::Use::MOVE) {	×
138	continue;	×
139	}
140	// Pointer is not constant
141	if (use->container() == viewed_container) {	×
142	unsafe = true;	×
143	break;	×
144	}
145	}
146	if (unsafe) {	2!
147	continue;	×
148	}
149	}	2!
150
151	auto& user_node = static_cast<data_flow::AccessNode&>(*user->element());	17!
152
153	// Simple case: No arithmetic on pointer, just replace container
154	if (move_subset.size() == 1 && symbolic::eq(move_subset[0], symbolic::zero())) {	32!
155	user_node.data(viewed_container);	6!
156	applied = true;	6✔
157	invalidated.insert(viewed_container);	6!
158	replaced_nodes.insert(&user_node);	6!
159	continue;	6✔
160	}
161
162	// General case: Arithmetic on pointer, need to update memlet subsets
163
164	// Criterion: Must be computational memlets
165	// Criterion: No type casting
166
167	auto& deref_type = move_edge.result_type(builder.subject());	11!
168	sdfg::types::Pointer ref_type(static_cast<const types::IType&>(deref_type));	11!
169
170	bool safe = true;	11✔
171	auto& user_graph = user_node.get_parent();	11!
172	for (auto& oedge : user_graph.out_edges(user_node)) {	15!
173	if (oedge.type() != data_flow::MemletType::Computational &&	6!
174	oedge.type() != data_flow::MemletType::Reference) {	1!
175	safe = false;	×
176	break;	×
177	}
178	auto& old_subset = oedge.subset();	5!
179	if (old_subset.empty()) {	5!
180	safe = false;	×
181	break;	×
182	}
183	if (oedge.base_type() != ref_type) {	5!
184	// Special case: compatible pointer types
185	if (!compatible_type(builder.subject(), move_edge, oedge)) {	3!
186	safe = false;	1✔
187	break;	1✔
188	}
189	}	2✔
190	}	5✔
191	if (!safe) {	11✔
192	continue;	1✔
193	}
194	for (auto& iedge : user_graph.in_edges(user_node)) {	13!
195	if (iedge.type() != data_flow::MemletType::Computational &&	8!
196	iedge.type() != data_flow::MemletType::Reference) {	2!
197	safe = false;	2✔
198	break;	2✔
199	}
200	auto& old_subset = iedge.subset();	4!
201	if (old_subset.empty()) {	4!
202	safe = false;	×
203	break;	×
204	}
205	if (iedge.base_type() != ref_type) {	4!
206	if (!compatible_type(builder.subject(), move_edge, iedge)) {	3!
207	safe = false;	1✔
208	break;	1✔
209	}
210	}	2✔
211	}	4✔
212	if (!safe) {	10✔
213	continue;	3✔
214	}
215
216	// Propagate pointer type
217
218	// Step 1: Replace container
219	user_node.data(viewed_container);	7!
220
221	// Step 2: Update edges
222	for (auto& oedge : user_graph.out_edges(user_node)) {	11!
223	// Compute new subset
224	data_flow::Subset new_subset;	4✔
225	for (auto dim : move_subset) {	9!
226	new_subset.push_back(dim);	5!
227	}	5✔
228
229	auto old_subset = oedge.subset();	4!
230
231	if (oedge.base_type() != ref_type) {	4!
232	for (auto& dim : old_subset) {	4✔
233	new_subset.push_back(dim);	2!
234	}
235	} else {	2✔
236	// Handle first trailing dimensions
237	auto& trail_dim = old_subset.front();	2✔
238	auto& current_dim = new_subset.back();	2✔
239	auto new_dim = symbolic::add(current_dim, trail_dim);	2!
240	new_subset.back() = new_dim;	2!
241	old_subset.erase(old_subset.begin());	2!
242
243	// Add remaining trailing dimensions
244	for (auto dim : old_subset) {	2!
245	new_subset.push_back(dim);	×
246	}	×
247	}	2✔
248
249	// Build new type
250	oedge.set_subset(new_subset);	4!
251	oedge.set_base_type(move_edge.base_type());	4!
252	}	4✔
253
254	for (auto& iedge : user_graph.in_edges(user_node)) {	10!
255	// Compute new subset
256	data_flow::Subset new_subset;	3✔
257	for (auto dim : move_subset) {	7!
258	new_subset.push_back(dim);	4!
259	}	4✔
260
261	auto old_subset = iedge.subset();	3!
262	if (iedge.base_type() != ref_type) {	3!
263	for (auto& dim : old_subset) {	4✔
264	new_subset.push_back(dim);	2!
265	}
266	} else {	2✔
267	// Handle first trailing dimensions
268	auto& trail_dim = old_subset.front();	1✔
269	auto& current_dim = new_subset.back();	1✔
270	auto new_dim = symbolic::add(current_dim, trail_dim);	1!
271	new_subset.back() = new_dim;	1!
272	old_subset.erase(old_subset.begin());	1!
273
274	// Add remaining trailing dimensions
275	for (auto dim : old_subset) {	1!
276	new_subset.push_back(dim);	×
277	}	×
278	}	1✔
279
280	iedge.set_subset(new_subset);	3!
281	iedge.set_base_type(move_edge.base_type());	3!
282	}	3✔
283
284	applied = true;	7✔
285	invalidated.insert(viewed_container);	7!
286	replaced_nodes.insert(&user_node);	7!
287	}	17✔
288	}	16✔
289
290	// Post-processing: Merge access nodes and remove dangling nodes
291	// Avoid removing elements while iterating above
292	for (auto* node : replaced_nodes) {	26✔
293	builder.merge_siblings(*node);	13!
294	}
295	for (auto* node : replaced_nodes) {	26✔
296	auto& graph = node->get_parent();	13!
297	auto* block = static_cast<structured_control_flow::Block*>(graph.get_parent());	13!
298	for (auto& dnode : graph.data_nodes()) {	39!
299	if (graph.in_degree(dnode) == 0 && graph.out_degree(dnode) == 0) {	26!
300	builder.remove_node(block, dnode);	×
301	}	×
302	}
303	}
304
305	return applied;	13✔
306	};	13✔
307
308	} // namespace passes
309	} // namespace sdfg

daisytuner / sdfglib / 20147202960

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