15919699107

Committed 27 Jun 2025 06:25AM UTC coverage: 65.002% (-0.1%) from 65.102%

Build # 15919699107

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #113 from daisytuner/block-fusion

Extends block fusion

Run Details

30 of 48 new or added lines in 2 files covered. (62.5%)

8 existing lines in 1 file now uncovered.

8540 of 13138 relevant lines covered (65.0%)

144.76 hits per line

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

82.35

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

        // Already connected
        if (connectors.find(access_node->data()) != connectors.end()) {
            continue;
        }
        // Write-after-write
        if (second_graph.in_degree(*access_node) > 0) {
            return false;
        }

        if (pdoms.find(access_node->data()) == pdoms.end()) {
            continue;
        }
        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);

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

        if (pdoms.find(access_node->data()) == pdoms.end()) {
            continue;
        }
        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_.add_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());
    }
};

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

daisytuner / sdfglib / 15919699107

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