18874944176

Committed 28 Oct 2025 12:35PM UTC coverage: 62.303% (+0.3%) from 61.966%

Build # 18874944176

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #303 from daisytuner/tasklet-fusion

Implemented TaskletFusion pass and adapted ReferencePropagation & BlockFusion pass

Run Details

180 of 207 new or added lines in 5 files covered. (86.96%)

1 existing line in 1 file now uncovered.

10113 of 16232 relevant lines covered (62.3%)

101.89 hits per line

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

67.46

/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 {

void ReferencePropagation::merge_access_nodes(builder::StructuredSDFGBuilder& builder, data_flow::AccessNode& user_node) {
    auto& user_graph = user_node.get_parent();
    auto* block = dynamic_cast<structured_control_flow::Block*>(user_graph.get_parent());
    if (!block) {
        throw InvalidSDFGException("Parent of user graph must be a block!");
    }

    // Merge access nodes if they access the same container on a tasklet
    for (auto& oedge : user_graph.out_edges(user_node)) {
        if (auto* tasklet = dynamic_cast<data_flow::Tasklet*>(&oedge.dst())) {
            std::unordered_set<data_flow::Memlet*> iedges;
            for (auto& iedge : user_graph.in_edges(*tasklet)) {
                iedges.insert(&iedge);
            }
            for (auto* iedge : iedges) {
                if (dynamic_cast<data_flow::ConstantNode*>(&iedge->src())) {
                    continue;
                } else if (auto* access_node = dynamic_cast<data_flow::AccessNode*>(&iedge->src())) {
                    if (access_node == &user_node || access_node->data() != user_node.data()) {
                        continue;
                    }
                    builder.add_memlet(
                        *block,
                        user_node,
                        iedge->src_conn(),
                        *tasklet,
                        iedge->dst_conn(),
                        iedge->subset(),
                        iedge->base_type(),
                        iedge->debug_info()
                    );
                    builder.remove_memlet(*block, *iedge);
                    user_node.set_debug_info(DebugInfo::merge(user_node.debug_info(), access_node->debug_info()));
                    if (user_graph.in_degree(*access_node) == 0 && user_graph.out_degree(*access_node)) {
                        builder.remove_node(*block, *access_node);
                    }
                }
            }
        }
    }
}

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;
                this->merge_access_nodes(builder, user_node);
                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());
                }
            }

            this->merge_access_nodes(builder, user_node);

            applied = true;
            invalidated.insert(viewed_container);
        }
    }

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

daisytuner / sdfglib / 18874944176

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