20770413849

Committed 06 Jan 2026 10:50PM UTC coverage: 62.168% (+21.4%) from 40.764%

Build # 20770413849

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #433 from daisytuner/clang-coverage

updates clang coverage flags

Run Details

14988 of 24109 relevant lines covered (62.17%)

88.57 hits per line

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

84.19

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

daisytuner / sdfglib / 20770413849

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