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

91.25

/src/passes/structured_control_flow/block_fusion.cpp

#include "sdfg/passes/structured_control_flow/block_fusion.h"
#include <cstddef>
#include <unordered_set>
#include <utility>
#include "sdfg/data_flow/access_node.h"
#include "sdfg/data_flow/data_flow_node.h"

namespace sdfg {
namespace passes {

BlockFusion::BlockFusion(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}

bool BlockFusion::can_be_applied(
    data_flow::DataFlowGraph& first_graph,
    control_flow::Assignments& first_assignments,
    data_flow::DataFlowGraph& second_graph,
    control_flow::Assignments& second_assignments
) {
    // Criterion: No side-effect nodes
    std::unordered_set<std::string> first_write_symbols;
    for (auto& node : first_graph.nodes()) {
        if (auto lib_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {
            if (lib_node->side_effect()) {
                return false;
            }
        } else if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(&node)) {
            if (first_graph.in_degree(*access_node) > 0) {
                auto& type = builder_.subject().type(access_node->data());
                if (type.is_symbol()) {
                    first_write_symbols.insert(access_node->data());
                }
            }
        }
    }
    std::unordered_set<std::string> second_write_symbols;
    for (auto& node : second_graph.nodes()) {
        if (auto lib_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {
            if (lib_node->side_effect()) {
                return false;
            }
        } else if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(&node)) {
            if (second_graph.in_degree(*access_node) > 0) {
                auto& type = builder_.subject().type(access_node->data());
                if (type.is_symbol()) {
                    second_write_symbols.insert(access_node->data());
                }
            }
        }
    }

    // Criterion: Subsets may not use written symbols
    for (auto& edge : first_graph.edges()) {
        for (auto& dim : edge.subset()) {
            for (auto& sym : symbolic::atoms(dim)) {
                if (second_write_symbols.find(sym->get_name()) != second_write_symbols.end()) {
                    return false;
                }
            }
        }
    }
    for (auto& edge : second_graph.edges()) {
        for (auto& dim : edge.subset()) {
            for (auto& sym : symbolic::atoms(dim)) {
                if (first_write_symbols.find(sym->get_name()) != first_write_symbols.end()) {
                    return false;
                }
            }
        }
    }

    // Criterion: Transition must be empty
    if (!first_assignments.empty()) {
        return false;
    }

    // Criterion: Keep references and dereference in separate blocks
    for (auto& edge : first_graph.edges()) {
        if (edge.type() != data_flow::MemletType::Computational) {
            return false;
        }
    }
    for (auto& edge : second_graph.edges()) {
        if (edge.type() != data_flow::MemletType::Computational) {
            return false;
        }
    }

    // Determine sets of weakly connected components for first graph
    auto [first_num_components, first_components] = first_graph.weakly_connected_components();
    std::vector<std::unordered_set<const data_flow::AccessNode*>> first_weakly_connected(first_num_components);
    for (auto comp : first_components) {
        // Only handle access nodes of the first graph
        if (dynamic_cast<const data_flow::ConstantNode*>(comp.first)) {
            continue;
        } else if (auto* access_node = dynamic_cast<const data_flow::AccessNode*>(comp.first)) {
            first_weakly_connected[comp.second].insert(access_node);
        }
    }

    // Determine sets of weakly connected components for second graph
    auto [second_num_components, second_components] = second_graph.weakly_connected_components();
    std::vector<std::unordered_set<const data_flow::AccessNode*>> second_weakly_connected(second_num_components);
    for (auto comp : second_components) {
        // Only handle access nodes of the second graph
        if (dynamic_cast<const data_flow::ConstantNode*>(comp.first)) {
            continue;
        } else if (auto* access_node = dynamic_cast<const data_flow::AccessNode*>(comp.first)) {
            second_weakly_connected[comp.second].insert(access_node);
        }
    }

    // For each combination of weakly connected components:
    for (size_t first = 0; first < first_num_components; first++) {
        for (size_t second = 0; second < second_num_components; second++) {
            // Match all access nodes with the same container
            std::vector<std::pair<const data_flow::AccessNode*, const data_flow::AccessNode*>> matches;
            for (auto* first_access_node : first_weakly_connected[first]) {
                for (auto* second_access_node : second_weakly_connected[second]) {
                    if (first_access_node->data() == second_access_node->data()) {
                        matches.push_back({first_access_node, second_access_node});
                    }
                }
            }
            // Skip if there are no matches
            if (matches.empty()) {
                continue;
            }
            // There must be at least one sink in the first graph and one source in the second graph that match
            bool connection = false;
            for (auto [first_access_node, second_access_node] : matches) {
                if (first_graph.out_degree(*first_access_node) == 0 &&
                    second_graph.in_degree(*second_access_node) == 0) {
                    connection = true;
                    break;
                }
            }
            if (!connection) {
                return false;
            }
        }
    }

    return true;
};

void BlockFusion::apply(
    structured_control_flow::Block& first_block,
    control_flow::Assignments& first_assignments,
    structured_control_flow::Block& second_block,
    control_flow::Assignments& second_assignments
) {
    data_flow::DataFlowGraph& first_graph = first_block.dataflow();
    data_flow::DataFlowGraph& second_graph = second_block.dataflow();

    // Update symbols
    for (auto& entry : second_assignments) {
        first_assignments[entry.first] = entry.second;
    }

    // Collect nodes to connect to
    auto pdoms = first_graph.post_dominators();
    std::unordered_map<data_flow::AccessNode*, data_flow::AccessNode*> connectors;
    for (auto& node : second_graph.sources()) {
        if (!dynamic_cast<data_flow::AccessNode*>(node)) {
            continue;
        }
        auto access_node = static_cast<data_flow::AccessNode*>(node);

        // Not used in first graph
        if (!pdoms.contains(access_node->data())) {
            continue;
        }

        connectors[access_node] = pdoms.at(access_node->data());
    }

    // Copy nodes from second to first
    std::unordered_map<data_flow::DataFlowNode*, data_flow::DataFlowNode*> node_mapping;
    for (auto& node : second_graph.nodes()) {
        if (auto access_node = dynamic_cast<data_flow::AccessNode*>(&node)) {
            if (connectors.contains(access_node)) {
                // Connect by replacement
                node_mapping[access_node] = connectors[access_node];
            } else {
                if (auto const_node = dynamic_cast<data_flow::ConstantNode*>(access_node)) {
                    // Add new
                    node_mapping[const_node] =
                        &builder_
                             .add_constant(first_block, const_node->data(), const_node->type(), const_node->debug_info());
                } else {
                    // Add new
                    node_mapping[access_node] =
                        &builder_.add_access(first_block, access_node->data(), access_node->debug_info());
                }
            }
        } else if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(&node)) {
            node_mapping[tasklet] = &builder_.add_tasklet(
                first_block, tasklet->code(), tasklet->output(), tasklet->inputs(), tasklet->debug_info()
            );
        } else if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(&node)) {
            node_mapping[library_node] = &builder_.copy_library_node(first_block, *library_node);
        } else {
            throw InvalidSDFGException("BlockFusion: Unknown node type");
        }
    }

    // Connect new nodes according to edges of second graph
    for (auto& edge : second_graph.edges()) {
        auto& src_node = edge.src();
        auto& dst_node = edge.dst();

        builder_.add_memlet(
            first_block,
            *node_mapping[&src_node],
            edge.src_conn(),
            *node_mapping[&dst_node],
            edge.dst_conn(),
            edge.subset(),
            edge.base_type(),
            edge.debug_info()
        );
    }
};

bool BlockFusion::accept(structured_control_flow::Sequence& node) {
    bool applied = false;

    if (node.size() == 0) {
        return applied;
    }

    // Traverse node to find pairs of blocks
    size_t i = 0;
    while (i < (node.size() - 1)) {
        auto current_entry = node.at(i);
        if (dynamic_cast<structured_control_flow::Block*>(&current_entry.first) == nullptr) {
            i++;
            continue;
        }
        auto current_block = static_cast<structured_control_flow::Block*>(&current_entry.first);

        auto next_entry = node.at(i + 1);
        if (dynamic_cast<structured_control_flow::Block*>(&next_entry.first) == nullptr) {
            i++;
            continue;
        }
        auto next_block = static_cast<structured_control_flow::Block*>(&next_entry.first);

        if (this->can_be_applied(
                current_block->dataflow(),
                current_entry.second.assignments(),
                next_block->dataflow(),
                next_entry.second.assignments()
            )) {
            this->apply(*current_block, current_entry.second.assignments(), *next_block, next_entry.second.assignments());
            builder_.remove_child(node, i + 1);
            applied = true;

            continue;
        }

        i++;
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/block_fusion.h"
2	#include <cstddef>
3	#include <unordered_set>
4	#include <utility>
5	#include "sdfg/data_flow/access_node.h"
6	#include "sdfg/data_flow/data_flow_node.h"
7
8	namespace sdfg {
9	namespace passes {
10
11	BlockFusion::BlockFusion(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)	7✔
12	: visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}	7✔
13
14	bool BlockFusion::can_be_applied(	7✔
15	data_flow::DataFlowGraph& first_graph,
16	control_flow::Assignments& first_assignments,
17	data_flow::DataFlowGraph& second_graph,
18	control_flow::Assignments& second_assignments
19	) {
20	// Criterion: No side-effect nodes
21	std::unordered_set<std::string> first_write_symbols;	7✔
22	for (auto& node : first_graph.nodes()) {	27✔
23	if (auto lib_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {	20✔
24	if (lib_node->side_effect()) {	1✔
25	return false;	×
26	}
27	} else if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(&node)) {	20✔
28	if (first_graph.in_degree(*access_node) > 0) {	16✔
29	auto& type = builder_.subject().type(access_node->data());	6✔
30	if (type.is_symbol()) {	6✔
31	first_write_symbols.insert(access_node->data());	3✔
32	}	3✔
33	}	6✔
34	}	16✔
35	}
36	std::unordered_set<std::string> second_write_symbols;	7✔
37	for (auto& node : second_graph.nodes()) {	36✔
38	if (auto lib_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {	29✔
39	if (lib_node->side_effect()) {	1✔
40	return false;	×
41	}
42	} else if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(&node)) {	29✔
43	if (second_graph.in_degree(*access_node) > 0) {	22✔
44	auto& type = builder_.subject().type(access_node->data());	7✔
45	if (type.is_symbol()) {	7✔
46	second_write_symbols.insert(access_node->data());	2✔
47	}	2✔
48	}	7✔
49	}	22✔
50	}
51
52	// Criterion: Subsets may not use written symbols
53	for (auto& edge : first_graph.edges()) {	21✔
54	for (auto& dim : edge.subset()) {	24✔
55	for (auto& sym : symbolic::atoms(dim)) {	10✔
56	if (second_write_symbols.find(sym->get_name()) != second_write_symbols.end()) {	×
57	return false;	×
58	}
59	}
60	}
61	}
62	for (auto& edge : second_graph.edges()) {	27✔
63	for (auto& dim : edge.subset()) {	35✔
64	for (auto& sym : symbolic::atoms(dim)) {	16✔
65	if (first_write_symbols.find(sym->get_name()) != first_write_symbols.end()) {	2✔
66	return false;	1✔
67	}
68	}
69	}
70	}
71
72	// Criterion: Transition must be empty
73	if (!first_assignments.empty()) {	6✔
74	return false;	1✔
75	}
76
77	// Criterion: Keep references and dereference in separate blocks
78	for (auto& edge : first_graph.edges()) {	15✔
79	if (edge.type() != data_flow::MemletType::Computational) {	12✔
80	return false;	2✔
81	}
82	}
83	for (auto& edge : second_graph.edges()) {	13✔
84	if (edge.type() != data_flow::MemletType::Computational) {	10✔
85	return false;	×
86	}
87	}
88
89	// Determine sets of weakly connected components for first graph
90	auto [first_num_components, first_components] = first_graph.weakly_connected_components();	9✔
91	std::vector<std::unordered_set<const data_flow::AccessNode*>> first_weakly_connected(first_num_components);	3✔
92	for (auto comp : first_components) {	16✔
93	// Only handle access nodes of the first graph
94	if (dynamic_cast<const data_flow::ConstantNode*>(comp.first)) {	13✔
95	continue;	4✔
96	} else if (auto* access_node = dynamic_cast<const data_flow::AccessNode*>(comp.first)) {	9✔
97	first_weakly_connected[comp.second].insert(access_node);	6✔
98	}	6✔
99	}
100
101	// Determine sets of weakly connected components for second graph
102	auto [second_num_components, second_components] = second_graph.weakly_connected_components();	9✔
103	std::vector<std::unordered_set<const data_flow::AccessNode*>> second_weakly_connected(second_num_components);	3✔
104	for (auto comp : second_components) {	16✔
105	// Only handle access nodes of the second graph
106	if (dynamic_cast<const data_flow::ConstantNode*>(comp.first)) {	13✔
107	continue;	4✔
108	} else if (auto* access_node = dynamic_cast<const data_flow::AccessNode*>(comp.first)) {	9✔
109	second_weakly_connected[comp.second].insert(access_node);	6✔
110	}	6✔
111	}
112
113	// For each combination of weakly connected components:
114	for (size_t first = 0; first < first_num_components; first++) {	6✔
115	for (size_t second = 0; second < second_num_components; second++) {	6✔
116	// Match all access nodes with the same container
117	std::vector<std::pair<const data_flow::AccessNode, const data_flow::AccessNode>> matches;	3✔
118	for (auto* first_access_node : first_weakly_connected[first]) {	9✔
119	for (auto* second_access_node : second_weakly_connected[second]) {	18✔
120	if (first_access_node->data() == second_access_node->data()) {	12✔
121	matches.push_back({first_access_node, second_access_node});	5✔
122	}	5✔
123	}
124	}
125	// Skip if there are no matches
126	if (matches.empty()) {	3✔
127	continue;	1✔
128	}
129	// There must be at least one sink in the first graph and one source in the second graph that match
130	bool connection = false;	2✔
131	for (auto [first_access_node, second_access_node] : matches) {	6✔
132	if (first_graph.out_degree(*first_access_node) == 0 &&	10✔
133	second_graph.in_degree(*second_access_node) == 0) {	4✔
134	connection = true;	2✔
135	break;	2✔
136	}
137	}
138	if (!connection) {	2✔
NEW 139	return false;	×
140	}
141	}	3✔
142	}	3✔
143
144	return true;	3✔
145	};	7✔
146
147	void BlockFusion::apply(	3✔
148	structured_control_flow::Block& first_block,
149	control_flow::Assignments& first_assignments,
150	structured_control_flow::Block& second_block,
151	control_flow::Assignments& second_assignments
152	) {
153	data_flow::DataFlowGraph& first_graph = first_block.dataflow();	3✔
154	data_flow::DataFlowGraph& second_graph = second_block.dataflow();	3✔
155
156	// Update symbols
157	for (auto& entry : second_assignments) {	3✔
158	first_assignments[entry.first] = entry.second;	×
159	}
160
161	// Collect nodes to connect to
162	auto pdoms = first_graph.post_dominators();	3✔
163	std::unordered_map<data_flow::AccessNode, data_flow::AccessNode> connectors;	3✔
164	for (auto& node : second_graph.sources()) {	10✔
165	if (!dynamic_cast<data_flow::AccessNode*>(node)) {	7✔
UNCOV 166	continue;	×
167	}
168	auto access_node = static_cast<data_flow::AccessNode*>(node);	7✔
169
170	// Not used in first graph
171	if (!pdoms.contains(access_node->data())) {	7✔
172	continue;	3✔
173	}
174
175	connectors[access_node] = pdoms.at(access_node->data());	4✔
176	}
177
178	// Copy nodes from second to first
179	std::unordered_map<data_flow::DataFlowNode, data_flow::DataFlowNode> node_mapping;	3✔
180	for (auto& node : second_graph.nodes()) {	16✔
181	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(&node)) {	13✔
182	if (connectors.contains(access_node)) {	10✔
183	// Connect by replacement
184	node_mapping[access_node] = connectors[access_node];	4✔
185	} else {	4✔
186	if (auto const_node = dynamic_cast<data_flow::ConstantNode*>(access_node)) {	6✔
187	// Add new
188	node_mapping[const_node] =	2✔
189	&builder_	2✔
190	.add_constant(first_block, const_node->data(), const_node->type(), const_node->debug_info());	2✔
191	} else {	2✔
192	// Add new
193	node_mapping[access_node] =	4✔
194	&builder_.add_access(first_block, access_node->data(), access_node->debug_info());	4✔
195	}
196	}
197	} else if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(&node)) {	13✔
198	node_mapping[tasklet] = &builder_.add_tasklet(	4✔
199	first_block, tasklet->code(), tasklet->output(), tasklet->inputs(), tasklet->debug_info()	2✔
200	);
201	} else if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(&node)) {	3✔
202	node_mapping[library_node] = &builder_.copy_library_node(first_block, *library_node);	1✔
203	} else {	1✔
204	throw InvalidSDFGException("BlockFusion: Unknown node type");	×
205	}
206	}
207
208	// Connect new nodes according to edges of second graph
209	for (auto& edge : second_graph.edges()) {	13✔
210	auto& src_node = edge.src();	10✔
211	auto& dst_node = edge.dst();	10✔
212
213	builder_.add_memlet(	20✔
214	first_block,	10✔
215	*node_mapping[&src_node],	10✔
216	edge.src_conn(),	10✔
217	*node_mapping[&dst_node],	10✔
218	edge.dst_conn(),	10✔
219	edge.subset(),	10✔
220	edge.base_type(),	10✔
221	edge.debug_info()	10✔
222	);
223	}
224	};	3✔
225
226	bool BlockFusion::accept(structured_control_flow::Sequence& node) {	7✔
227	bool applied = false;	7✔
228
229	if (node.size() == 0) {	7✔
230	return applied;	×
231	}
232
233	// Traverse node to find pairs of blocks
234	size_t i = 0;	7✔
235	while (i < (node.size() - 1)) {	14✔
236	auto current_entry = node.at(i);	7✔
237	if (dynamic_cast<structured_control_flow::Block*>(&current_entry.first) == nullptr) {	7✔
238	i++;	×
239	continue;	×
240	}
241	auto current_block = static_cast<structured_control_flow::Block*>(&current_entry.first);	7✔
242
243	auto next_entry = node.at(i + 1);	7✔
244	if (dynamic_cast<structured_control_flow::Block*>(&next_entry.first) == nullptr) {	7✔
245	i++;	×
246	continue;	×
247	}
248	auto next_block = static_cast<structured_control_flow::Block*>(&next_entry.first);	7✔
249
250	if (this->can_be_applied(	7✔
251	current_block->dataflow(),	7✔
252	current_entry.second.assignments(),	7✔
253	next_block->dataflow(),	7✔
254	next_entry.second.assignments()	7✔
255	)) {
256	this->apply(current_block, current_entry.second.assignments(), next_block, next_entry.second.assignments());	3✔
257	builder_.remove_child(node, i + 1);	3✔
258	applied = true;	3✔
259
260	continue;	3✔
261	}
262
263	i++;	4✔
264	}
265
266	return applied;	7✔
267	};	7✔
268
269	} // namespace passes
270	} // 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