16352412282

Committed 17 Jul 2025 05:58PM UTC coverage: 64.93% (+0.07%) from 64.863%

Build # 16352412282

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #149 from daisytuner/library-node-subsets

Extends handling of library nodes in passes

Run Details

30 of 54 new or added lines in 2 files covered. (55.56%)

2 existing lines in 1 file now uncovered.

8750 of 13476 relevant lines covered (64.93%)

175.84 hits per line

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

86.49

/src/passes/structured_control_flow/block_fusion.cpp

#include "sdfg/passes/structured_control_flow/block_fusion.h"

namespace sdfg {
namespace passes {

BlockFusion::BlockFusion(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : visitor::StructuredSDFGVisitor(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
    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 tasklet = dynamic_cast<const data_flow::Tasklet*>(&node)) {
            if (tasklet->is_conditional()) {
                return false;
            }
        }
    }
    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 tasklet = dynamic_cast<const data_flow::Tasklet*>(&node)) {
            if (tasklet->is_conditional()) {
                return false;
            }
        }
    }
    // Criterion: No data races cause by transition
    if (!first_assignments.empty()) {
        return false;
    }

    // Numerical stability: Unique order of nodes
    auto pdoms = first_graph.post_dominators();
    std::unordered_map<std::string, const data_flow::AccessNode*> connectors;
    for (auto& node : second_graph.topological_sort()) {
        if (!dynamic_cast<const data_flow::AccessNode*>(node)) {
            continue;
        }
        auto access_node = static_cast<const data_flow::AccessNode*>(node);

        // Not used in first graph
        if (pdoms.find(access_node->data()) == pdoms.end()) {
            continue;
        }
        // Already connected
        if (connectors.find(access_node->data()) != connectors.end()) {
            continue;
        }

        // Write-after-write
        if (second_graph.in_degree(*access_node) > 0) {
            return false;
        }
        connectors[access_node->data()] = pdoms.at(access_node->data());
    }

    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_set<std::string> already_connected;
    std::unordered_map<data_flow::AccessNode*, data_flow::AccessNode*> connectors;
    for (auto& node : second_graph.topological_sort()) {
        if (!dynamic_cast<data_flow::AccessNode*>(node)) {
            continue;
        }
        auto access_node = static_cast<data_flow::AccessNode*>(node);

        // Not used in first graph
        if (pdoms.find(access_node->data()) == pdoms.end()) {
            continue;
        }
        // Already connected
        if (already_connected.find(access_node->data()) != already_connected.end()) {
            continue;
        }
        // Write-after-write
        if (second_graph.in_degree(*access_node) > 0) {
            throw InvalidSDFGException("BlockFusion: Write-after-write");
        }
        connectors[access_node] = pdoms.at(access_node->data());
        already_connected.insert(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.find(access_node) != connectors.end()) {
                // Connect by replacement
                node_mapping[access_node] = connectors[access_node];
            } else {
                // Add new
                node_mapping[access_node] = &builder_.add_access(first_block, access_node->data());
            }
        } else if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(&node)) {
            node_mapping[tasklet] =
                &builder_.add_tasklet(first_block, tasklet->code(), tasklet->output(), tasklet->inputs());
        } 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.begin_subset(),
            edge.end_subset(),
            edge.debug_info()
        );
    }
};

bool BlockFusion::accept(structured_control_flow::Sequence& parent, 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 = dynamic_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 = dynamic_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;
        } else {
            i++;
        }
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/block_fusion.h"
2
3	namespace sdfg {
4	namespace passes {
5
6	BlockFusion::BlockFusion(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)	3✔
7	: visitor::StructuredSDFGVisitor(builder, analysis_manager) {}	3✔
8
9	bool BlockFusion::can_be_applied(	3✔
10	data_flow::DataFlowGraph& first_graph,
11	control_flow::Assignments& first_assignments,
12	data_flow::DataFlowGraph& second_graph,
13	control_flow::Assignments& second_assignments
14	) {
15	// Criterion: No side-effect nodes
16	for (auto& node : first_graph.nodes()) {	12✔
17	if (auto lib_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {	9✔
18	if (lib_node->side_effect()) {	1✔
19	return false;	×
20	}
21	} else if (auto tasklet = dynamic_cast<const data_flow::Tasklet*>(&node)) {	9✔
22	if (tasklet->is_conditional()) {	2✔
23	return false;	×
24	}
25	}	2✔
26	}
27	for (auto& node : second_graph.nodes()) {	12✔
28	if (auto lib_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {	9✔
29	if (lib_node->side_effect()) {	1✔
30	return false;	×
31	}
32	} else if (auto tasklet = dynamic_cast<const data_flow::Tasklet*>(&node)) {	9✔
33	if (tasklet->is_conditional()) {	2✔
34	return false;	×
35	}
36	}	2✔
37	}
38	// Criterion: No data races cause by transition
39	if (!first_assignments.empty()) {	3✔
40	return false;	×
41	}
42
43	// Numerical stability: Unique order of nodes
44	auto pdoms = first_graph.post_dominators();	3✔
45	std::unordered_map<std::string, const data_flow::AccessNode*> connectors;	3✔
46	for (auto& node : second_graph.topological_sort()) {	12✔
47	if (!dynamic_cast<const data_flow::AccessNode*>(node)) {	9✔
48	continue;	3✔
49	}
50	auto access_node = static_cast<const data_flow::AccessNode*>(node);	6✔
51
52	// Not used in first graph
53	if (pdoms.find(access_node->data()) == pdoms.end()) {	6✔
54	continue;	3✔
55	}
56	// Already connected
57	if (connectors.find(access_node->data()) != connectors.end()) {	3✔
58	continue;	1✔
59	}
60
61	// Write-after-write
62	if (second_graph.in_degree(*access_node) > 0) {	2✔
UNCOV 63	return false;	×
64	}
65	connectors[access_node->data()] = pdoms.at(access_node->data());	2✔
66	}
67
68	return true;	3✔
69	};	3✔
70
71	void BlockFusion::apply(	3✔
72	structured_control_flow::Block& first_block,
73	control_flow::Assignments& first_assignments,
74	structured_control_flow::Block& second_block,
75	control_flow::Assignments& second_assignments
76	) {
77	data_flow::DataFlowGraph& first_graph = first_block.dataflow();	3✔
78	data_flow::DataFlowGraph& second_graph = second_block.dataflow();	3✔
79
80	// Update symbols
81	for (auto& entry : second_assignments) {	3✔
82	first_assignments[entry.first] = entry.second;	×
83	}
84
85	// Collect nodes to connect to
86	auto pdoms = first_graph.post_dominators();	3✔
87	std::unordered_set<std::string> already_connected;	3✔
88	std::unordered_map<data_flow::AccessNode, data_flow::AccessNode> connectors;	3✔
89	for (auto& node : second_graph.topological_sort()) {	12✔
90	if (!dynamic_cast<data_flow::AccessNode*>(node)) {	9✔
91	continue;	3✔
92	}
93	auto access_node = static_cast<data_flow::AccessNode*>(node);	6✔
94
95	// Not used in first graph
96	if (pdoms.find(access_node->data()) == pdoms.end()) {	6✔
97	continue;	3✔
98	}
99	// Already connected
100	if (already_connected.find(access_node->data()) != already_connected.end()) {	3✔
101	continue;	1✔
102	}
103	// Write-after-write
104	if (second_graph.in_degree(*access_node) > 0) {	2✔
105	throw InvalidSDFGException("BlockFusion: Write-after-write");	×
106	}
107	connectors[access_node] = pdoms.at(access_node->data());	2✔
108	already_connected.insert(access_node->data());	2✔
109	}
110
111	// Copy nodes from second to first
112	std::unordered_map<data_flow::DataFlowNode, data_flow::DataFlowNode> node_mapping;	3✔
113	for (auto& node : second_graph.nodes()) {	12✔
114	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(&node)) {	9✔
115	if (connectors.find(access_node) != connectors.end()) {	6✔
116	// Connect by replacement
117	node_mapping[access_node] = connectors[access_node];	2✔
118	} else {	2✔
119	// Add new
120	node_mapping[access_node] = &builder_.add_access(first_block, access_node->data());	4✔
121	}
122	} else if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(&node)) {	9✔
123	node_mapping[tasklet] =	2✔
124	&builder_.add_tasklet(first_block, tasklet->code(), tasklet->output(), tasklet->inputs());	2✔
125	} else if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(&node)) {	3✔
126	node_mapping[library_node] = &builder_.copy_library_node(first_block, *library_node);	1✔
127	} else {	1✔
128	throw InvalidSDFGException("BlockFusion: Unknown node type");	×
129	}
130	}
131
132	// Connect new nodes according to edges of second graph
133	for (auto& edge : second_graph.edges()) {	9✔
134	auto& src_node = edge.src();	6✔
135	auto& dst_node = edge.dst();	6✔
136
137	builder_.add_memlet(	12✔
138	first_block,	6✔
139	*node_mapping[&src_node],	6✔
140	edge.src_conn(),	6✔
141	*node_mapping[&dst_node],	6✔
142	edge.dst_conn(),	6✔
143	edge.begin_subset(),	6✔
144	edge.end_subset(),	6✔
145	edge.debug_info()	6✔
146	);
147	}
148	};	3✔
149
150	bool BlockFusion::accept(structured_control_flow::Sequence& parent, structured_control_flow::Sequence& node) {	3✔
151	bool applied = false;	3✔
152
153	if (node.size() == 0) {	3✔
154	return applied;	×
155	}
156
157	// Traverse node to find pairs of blocks
158	size_t i = 0;	3✔
159	while (i < (node.size() - 1)) {	6✔
160	auto current_entry = node.at(i);	3✔
161	if (dynamic_cast<structured_control_flow::Block*>(&current_entry.first) == nullptr) {	3✔
162	i++;	×
163	continue;	×
164	}
165	auto current_block = dynamic_cast<structured_control_flow::Block*>(&current_entry.first);	3✔
166
167	auto next_entry = node.at(i + 1);	3✔
168	if (dynamic_cast<structured_control_flow::Block*>(&next_entry.first) == nullptr) {	3✔
169	i++;	×
170	continue;	×
171	}
172	auto next_block = dynamic_cast<structured_control_flow::Block*>(&next_entry.first);	3✔
173
174	if (this->can_be_applied(	3✔
175	current_block->dataflow(),	3✔
176	current_entry.second.assignments(),	3✔
177	next_block->dataflow(),	3✔
178	next_entry.second.assignments()	3✔
179	)) {
180	this->apply(current_block, current_entry.second.assignments(), next_block, next_entry.second.assignments());	3✔
181	builder_.remove_child(node, i + 1);	3✔
182	applied = true;	3✔
183	} else {	3✔
UNCOV 184	i++;	×
185	}
186	}
187
188	return applied;	3✔
189	};	3✔
190
191	} // namespace passes
192	} // namespace sdfg

daisytuner / sdfglib / 16352412282

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