30647115023

Committed 31 Jul 2026 04:26PM UTC coverage: 64.824% (+0.02%) from 64.806%

Build # 30647115023

Build Type

Pull #918

github

Committed by

web-flow

Commit Message

Merge b2331620d into 60edac6b5

Pull Request Pull Request #918: Loop fusion migration in normalize

Coverage Stats

46 of 49 new or added lines in 2 files covered. (93.88%)

45628 of 70387 relevant lines covered (64.82%)

724.48 hits per line

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

86.73

/sdfg/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, bool ignore_libnodes
)
    : visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager), ignore_libnodes_(ignore_libnodes) {}

struct ComponentState {
    std::unordered_set<const data_flow::AccessNode*> members;
    std::unordered_set<const data_flow::AccessNode*> exposed_access_nodes; // upwards / downwards depending on which
                                                                           // block
};

bool BlockFusion::can_be_applied(data_flow::DataFlowGraph& first_graph, data_flow::DataFlowGraph& second_graph) {
    // 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 (this->ignore_libnodes_ || 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 (this->ignore_libnodes_ || 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 and library node symbols 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* libnode : first_graph.library_nodes()) {
        for (auto& sym : libnode->symbols()) {
            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;
                }
            }
        }
    }
    for (auto* libnode : second_graph.library_nodes()) {
        for (auto& sym : libnode->symbols()) {
            if (first_write_symbols.find(sym->get_name()) != first_write_symbols.end()) {
                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<ComponentState> 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)) {
            auto& state = first_weakly_connected[comp.second];
            state.members.insert(access_node);
            if (first_graph.out_degree(*access_node) == 0) {
                state.exposed_access_nodes.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<ComponentState> 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)) {
            auto& state = second_weakly_connected[comp.second];
            state.members.insert(access_node);
            if (second_graph.in_degree(*access_node) == 0) {
                // Some form of write
                state.exposed_access_nodes.insert(access_node);
            }
        }
    }

    // For each combination of weakly connected components:
    for (size_t first = 0; first < first_num_components; first++) {
        auto& first_state = first_weakly_connected[first];
        for (size_t second = 0; second < second_num_components; second++) {
            auto& second_state = second_weakly_connected[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_state.members) {
                for (auto* second_access_node : second_state.members) {
                    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;
            }
            size_t connections = 0, excused_connections = 0;

            for (auto [first_access_node, second_access_node] : matches) {
                auto first_is_leaf_read = first_graph.in_degree(*first_access_node) == 0;
                auto first_is_leaf_write = first_graph.out_degree(*first_access_node) == 0;
                auto second_is_leaf_read = second_graph.in_degree(*second_access_node) == 0;
                if (first_is_leaf_write && second_is_leaf_read) {
                    ++connections;
                } else if (first_is_leaf_read && second_is_leaf_read) {
                    ++excused_connections;
                }
            }
            if (first_state.exposed_access_nodes.size() == 1) {
                if (connections == 0 && excused_connections == 0) {
                    return false;
                }
            } else {
                if ((connections + excused_connections) != matches.size()) {
                    return false;
                }
            }
        }
    }

    return true;
};

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

    // 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 {
                node_mapping[access_node] = &builder_.copy_node(first_block, *access_node);
            }
        } else {
            node_mapping[&node] = &builder_.copy_node(first_block, node);
        }
    }

    // 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()
        );
    }

    builder_.merge_sinks(first_block);
};

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 (dyn_cast<structured_control_flow::Block*>(&current_entry) == nullptr) {
            i++;
            continue;
        }
        auto current_block = static_cast<structured_control_flow::Block*>(&current_entry);

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

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

daisytuner / docc / 30647115023

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