16312353091

Committed 16 Jul 2025 06:41AM UTC coverage: 64.622% (-0.2%) from 64.843%

Build # 16312353091

Build Type

Pull #141

github

Committed by

web-flow

Commit Message

Merge 750219df9 into 9bcea5e19

Pull Request Pull Request #141: Several convenience improvements for library nodes

Run Details

60 of 141 new or added lines in 14 files covered. (42.55%)

8 existing lines in 7 files now uncovered.

8556 of 13240 relevant lines covered (64.62%)

178.39 hits per line

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

83.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);

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

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

daisytuner / sdfglib / 16312353091

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