15656007340

Committed 14 Jun 2025 08:51PM UTC coverage: 13.234% (-49.9%) from 63.144%

Build # 15656007340

Build Type

Pull #76

github

Committed by

web-flow

Commit Message

Merge 9586c8161 into 413c53212

Pull Request Pull Request #76: New Loop Dependency Analysis

Run Details

361 of 465 new or added lines in 7 files covered. (77.63%)

6215 existing lines in 110 files now uncovered.

1612 of 12181 relevant lines covered (13.23%)

13.64 hits per line

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

0.0

/src/passes/structured_control_flow/block_fusion.cpp

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

daisytuner / sdfglib / 15656007340

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