31009380971

Committed 05 Aug 2026 01:15PM UTC coverage: 65.103% (+0.1%) from 65.005%

Build # 31009380971

Build Type

Pull #814

github

Committed by

web-flow

Commit Message

Merge 268a080ae into 7d5b198bd

Pull Request Pull Request #814: Adds GPU reduce dispatchers

Coverage Stats

409 of 663 new or added lines in 18 files covered. (61.69%)

145 existing lines in 6 files now uncovered.

46693 of 71722 relevant lines covered (65.1%)

713.1 hits per line

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

76.37

/sdfg/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/structured_control_flow/reduce.h"
#include "sdfg/types/utils.h"

namespace sdfg {
namespace passes {

namespace {

// A Reduce node stores its accumulator container name denormalized in the
// ReductionInfo. Reference propagation rewrites accumulator access nodes
// directly, so walk up from a rewritten node and retarget any enclosing
// reduction to keep the ReductionInfo consistent with the dataflow graph.
void retarget_enclosing_reductions(
    data_flow::AccessNode& node, const std::string& old_container, const std::string& new_container
) {
    if (old_container == new_container) {
        return;
    }
    auto* current = dynamic_cast<structured_control_flow::ControlFlowNode*>(node.get_parent().get_parent());
    while (current != nullptr) {
        if (auto* reduce = dynamic_cast<structured_control_flow::Reduce*>(current)) {
            reduce->replace_reduction_container(old_container, new_container);
        }
        current = current->get_parent();
    }
}

} // namespace

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

daisytuner / docc / 31009380971

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