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

8.78

/src/builder/structured_sdfg_builder.cpp

1	#include "sdfg/builder/structured_sdfg_builder.h"
2
3	#include "sdfg/analysis/scope_analysis.h"
4	#include "sdfg/codegen/language_extensions/cpp_language_extension.h"
5	#include "sdfg/data_flow/library_node.h"
6	#include "sdfg/structured_control_flow/map.h"
7	#include "sdfg/structured_control_flow/sequence.h"
8	#include "sdfg/types/utils.h"
9
10	using namespace sdfg::control_flow;
11	using namespace sdfg::structured_control_flow;
12
13	namespace sdfg {
14	namespace builder {
15
UNCOV 16	std::unordered_set<const control_flow::State*> StructuredSDFGBuilder::determine_loop_nodes(	×
17	const SDFG& sdfg, const control_flow::State& start, const control_flow::State& end) const {
UNCOV 18	std::unordered_set<const control_flow::State*> nodes;	×
UNCOV 19	std::unordered_set<const control_flow::State*> visited;	×
UNCOV 20	std::list<const control_flow::State*> queue = {&start};	×
UNCOV 21	while (!queue.empty()) {	×
UNCOV 22	auto curr = queue.front();	×
UNCOV 23	queue.pop_front();	×
UNCOV 24	if (visited.find(curr) != visited.end()) {	×
25	continue;	×
26	}
UNCOV 27	visited.insert(curr);	×
28
UNCOV 29	nodes.insert(curr);	×
UNCOV 30	if (curr == &end) {	×
UNCOV 31	continue;	×
32	}
33
UNCOV 34	for (auto& iedge : sdfg.in_edges(*curr)) {	×
UNCOV 35	queue.push_back(&iedge.src());	×
36	}
37	}
38
UNCOV 39	return nodes;	×
UNCOV 40	};	×
41
UNCOV 42	bool post_dominates(	×
43	const State* pdom, const State* node,
44	const std::unordered_map<const control_flow::State, const control_flow::State>& pdom_tree) {
UNCOV 45	if (pdom == node) {	×
UNCOV 46	return true;	×
47	}
48
UNCOV 49	auto current = pdom_tree.at(node);	×
UNCOV 50	while (current != nullptr) {	×
UNCOV 51	if (current == pdom) {	×
UNCOV 52	return true;	×
53	}
UNCOV 54	current = pdom_tree.at(current);	×
55	}
56
57	return false;	×
UNCOV 58	}	×
59
UNCOV 60	const control_flow::State* StructuredSDFGBuilder::find_end_of_if_else(	×
61	const SDFG& sdfg, const State* current, std::vector<const InterstateEdge*>& out_edges,
62	const std::unordered_map<const control_flow::State, const control_flow::State>& pdom_tree) {
63	// Best-effort approach: Check if post-dominator of current dominates all out edges
UNCOV 64	auto pdom = pdom_tree.at(current);	×
UNCOV 65	for (auto& edge : out_edges) {	×
UNCOV 66	if (!post_dominates(pdom, &edge->dst(), pdom_tree)) {	×
67	return nullptr;	×
68	}
69	}
70
UNCOV 71	return pdom;	×
UNCOV 72	}	×
73
UNCOV 74	void StructuredSDFGBuilder::traverse(const SDFG& sdfg) {	×
75	// Start of SDFGS
UNCOV 76	Sequence& root = *structured_sdfg_->root_;	×
UNCOV 77	const State* start_state = &sdfg.start_state();	×
78
UNCOV 79	auto pdom_tree = sdfg.post_dominator_tree();	×
80
UNCOV 81	std::unordered_set<const InterstateEdge*> breaks;	×
UNCOV 82	std::unordered_set<const InterstateEdge*> continues;	×
UNCOV 83	for (auto& edge : sdfg.back_edges()) {	×
UNCOV 84	continues.insert(edge);	×
85	}
86
UNCOV 87	std::unordered_set<const control_flow::State*> visited;	×
UNCOV 88	this->traverse_with_loop_detection(sdfg, root, start_state, nullptr, continues, breaks,	×
89	pdom_tree, visited);
UNCOV 90	};	×
91
UNCOV 92	void StructuredSDFGBuilder::traverse_with_loop_detection(	×
93	const SDFG& sdfg, Sequence& scope, const State* current, const State* end,
94	const std::unordered_set<const InterstateEdge*>& continues,
95	const std::unordered_set<const InterstateEdge*>& breaks,
96	const std::unordered_map<const control_flow::State, const control_flow::State>& pdom_tree,
97	std::unordered_set<const control_flow::State*>& visited) {
UNCOV 98	if (current == end) {	×
UNCOV 99	return;	×
100	}
101
UNCOV 102	auto in_edges = sdfg.in_edges(*current);	×
103
104	// Loop detection
UNCOV 105	std::unordered_set<const InterstateEdge*> loop_edges;	×
UNCOV 106	for (auto& iedge : in_edges) {	×
UNCOV 107	if (continues.find(&iedge) != continues.end()) {	×
UNCOV 108	loop_edges.insert(&iedge);	×
UNCOV 109	}	×
110	}
UNCOV 111	if (!loop_edges.empty()) {	×
112	// 1. Determine nodes of loop body
UNCOV 113	std::unordered_set<const control_flow::State*> body;	×
UNCOV 114	for (auto back_edge : loop_edges) {	×
UNCOV 115	auto loop_nodes = this->determine_loop_nodes(sdfg, back_edge->src(), back_edge->dst());	×
UNCOV 116	body.insert(loop_nodes.begin(), loop_nodes.end());	×
UNCOV 117	}	×
118
119	// 2. Determine exit states and exit edges
UNCOV 120	std::unordered_set<const control_flow::State*> exit_states;	×
UNCOV 121	std::unordered_set<const control_flow::InterstateEdge*> exit_edges;	×
UNCOV 122	for (auto node : body) {	×
UNCOV 123	for (auto& edge : sdfg.out_edges(*node)) {	×
UNCOV 124	if (body.find(&edge.dst()) == body.end()) {	×
UNCOV 125	exit_edges.insert(&edge);	×
UNCOV 126	exit_states.insert(&edge.dst());	×
UNCOV 127	}	×
128	}
129	}
UNCOV 130	if (exit_states.size() != 1) {	×
131	throw UnstructuredControlFlowException();	×
132	}
UNCOV 133	const control_flow::State* exit_state = *exit_states.begin();	×
134
UNCOV 135	for (auto& edge : breaks) {	×
136	exit_edges.insert(edge);	×
137	}
138
139	// Collect debug information (could be removed when this is computed dynamically)
UNCOV 140	DebugInfo dbg_info = current->debug_info();	×
UNCOV 141	for (auto& edge : in_edges) {	×
UNCOV 142	dbg_info = DebugInfo::merge(dbg_info, edge.debug_info());	×
143	}
UNCOV 144	for (auto node : body) {	×
UNCOV 145	dbg_info = DebugInfo::merge(dbg_info, node->debug_info());	×
146	}
UNCOV 147	for (auto edge : exit_edges) {	×
UNCOV 148	dbg_info = DebugInfo::merge(dbg_info, edge->debug_info());	×
149	}
150
151	// 3. Add while loop
UNCOV 152	While& loop = this->add_while(scope, {}, dbg_info);	×
153
UNCOV 154	std::unordered_set<const control_flow::State*> loop_visited(visited);	×
UNCOV 155	this->traverse_without_loop_detection(sdfg, loop.root(), current, exit_state, continues,	×
UNCOV 156	exit_edges, pdom_tree, loop_visited);	×
157
UNCOV 158	this->traverse_with_loop_detection(sdfg, scope, exit_state, end, continues, breaks,	×
UNCOV 159	pdom_tree, visited);	×
UNCOV 160	} else {	×
UNCOV 161	this->traverse_without_loop_detection(sdfg, scope, current, end, continues, breaks,	×
UNCOV 162	pdom_tree, visited);	×
163	}
UNCOV 164	};	×
165
UNCOV 166	void StructuredSDFGBuilder::traverse_without_loop_detection(	×
167	const SDFG& sdfg, Sequence& scope, const State* current, const State* end,
168	const std::unordered_set<const InterstateEdge*>& continues,
169	const std::unordered_set<const InterstateEdge*>& breaks,
170	const std::unordered_map<const control_flow::State, const control_flow::State>& pdom_tree,
171	std::unordered_set<const control_flow::State*>& visited) {
UNCOV 172	std::list<const State*> queue = {current};	×
UNCOV 173	while (!queue.empty()) {	×
UNCOV 174	auto curr = queue.front();	×
UNCOV 175	queue.pop_front();	×
UNCOV 176	if (curr == end) {	×
UNCOV 177	continue;	×
178	}
179
UNCOV 180	if (visited.find(curr) != visited.end()) {	×
181	throw UnstructuredControlFlowException();	×
182	}
UNCOV 183	visited.insert(curr);	×
184
UNCOV 185	auto out_edges = sdfg.out_edges(*curr);	×
UNCOV 186	auto out_degree = sdfg.out_degree(*curr);	×
187
188	// Case 1: Sink node
UNCOV 189	if (out_degree == 0) {	×
UNCOV 190	this->add_block(scope, curr->dataflow(), {}, curr->debug_info());	×
UNCOV 191	this->add_return(scope, {}, curr->debug_info());	×
UNCOV 192	continue;	×
193	}
194
195	// Case 2: Transition
UNCOV 196	if (out_degree == 1) {	×
UNCOV 197	auto& oedge = *out_edges.begin();	×
UNCOV 198	if (!oedge.is_unconditional()) {	×
199	throw UnstructuredControlFlowException();	×
200	}
UNCOV 201	this->add_block(scope, curr->dataflow(), oedge.assignments(), curr->debug_info());	×
202
UNCOV 203	if (continues.find(&oedge) != continues.end()) {	×
204	this->add_continue(scope, oedge.debug_info());	×
UNCOV 205	} else if (breaks.find(&oedge) != breaks.end()) {	×
206	this->add_break(scope, oedge.debug_info());	×
207	} else {	×
UNCOV 208	bool starts_loop = false;	×
UNCOV 209	for (auto& iedge : sdfg.in_edges(oedge.dst())) {	×
UNCOV 210	if (continues.find(&iedge) != continues.end()) {	×
211	starts_loop = true;	×
212	break;	×
213	}
214	}
UNCOV 215	if (!starts_loop) {	×
UNCOV 216	queue.push_back(&oedge.dst());	×
UNCOV 217	} else {	×
218	this->traverse_with_loop_detection(sdfg, scope, &oedge.dst(), end, continues,	×
219	breaks, pdom_tree, visited);	×
220	}
221	}
UNCOV 222	continue;	×
223	}
224
225	// Case 3: Branches
UNCOV 226	if (out_degree > 1) {	×
UNCOV 227	this->add_block(scope, curr->dataflow(), {}, curr->debug_info());	×
228
UNCOV 229	std::vector<const InterstateEdge*> out_edges_vec;	×
UNCOV 230	for (auto& edge : out_edges) {	×
UNCOV 231	out_edges_vec.push_back(&edge);	×
232	}
233
234	// Best-effort approach: Find end of if-else
235	// If not found, the branches may repeat paths yielding a large SDFG
UNCOV 236	const control_flow::State* local_end =	×
UNCOV 237	this->find_end_of_if_else(sdfg, curr, out_edges_vec, pdom_tree);	×
UNCOV 238	if (local_end == nullptr) {	×
239	local_end = end;	×
240	}	×
241
UNCOV 242	auto& if_else = this->add_if_else(scope, curr->debug_info());	×
UNCOV 243	for (size_t i = 0; i < out_degree; i++) {	×
UNCOV 244	auto& out_edge = out_edges_vec[i];	×
245
UNCOV 246	auto& branch =	×
UNCOV 247	this->add_case(if_else, out_edge->condition(), out_edge->debug_info());	×
UNCOV 248	if (!out_edge->assignments().empty()) {	×
UNCOV 249	this->add_block(branch, out_edge->assignments(), out_edge->debug_info());	×
UNCOV 250	}	×
UNCOV 251	if (continues.find(out_edge) != continues.end()) {	×
UNCOV 252	this->add_continue(branch, out_edge->debug_info());	×
UNCOV 253	} else if (breaks.find(out_edge) != breaks.end()) {	×
UNCOV 254	this->add_break(branch, out_edge->debug_info());	×
UNCOV 255	} else {	×
UNCOV 256	std::unordered_set<const control_flow::State*> branch_visited(visited);	×
UNCOV 257	this->traverse_with_loop_detection(sdfg, branch, &out_edge->dst(), local_end,	×
UNCOV 258	continues, breaks, pdom_tree,	×
259	branch_visited);
UNCOV 260	}	×
UNCOV 261	}	×
262
UNCOV 263	if (local_end != end) {	×
UNCOV 264	bool starts_loop = false;	×
UNCOV 265	for (auto& iedge : sdfg.in_edges(*local_end)) {	×
UNCOV 266	if (continues.find(&iedge) != continues.end()) {	×
267	starts_loop = true;	×
268	break;	×
269	}
270	}
UNCOV 271	if (!starts_loop) {	×
UNCOV 272	queue.push_back(local_end);	×
UNCOV 273	} else {	×
274	this->traverse_with_loop_detection(sdfg, scope, local_end, end, continues,	×
275	breaks, pdom_tree, visited);	×
276	}
UNCOV 277	}	×
278	continue;
UNCOV 279	}	×
280	}
UNCOV 281	}	×
282
283	Function& StructuredSDFGBuilder::function() const {	210✔
284	return static_cast<Function&>(*this->structured_sdfg_);	210✔
285	};
286
UNCOV 287	StructuredSDFGBuilder::StructuredSDFGBuilder(std::unique_ptr<StructuredSDFG>& sdfg)	×
UNCOV 288	: FunctionBuilder(), structured_sdfg_(std::move(sdfg)) {};	×
289
290	StructuredSDFGBuilder::StructuredSDFGBuilder(const std::string& name, FunctionType type)	17✔
291	: FunctionBuilder(), structured_sdfg_(new StructuredSDFG(name, type)) {};	17✔
292
UNCOV 293	StructuredSDFGBuilder::StructuredSDFGBuilder(const SDFG& sdfg)	×
UNCOV 294	: FunctionBuilder(), structured_sdfg_(new StructuredSDFG(sdfg.name(), sdfg.type())) {	×
UNCOV 295	for (auto& entry : sdfg.structures_) {	×
296	this->structured_sdfg_->structures_.insert({entry.first, entry.second->clone()});	×
297	}
298
UNCOV 299	for (auto& entry : sdfg.containers_) {	×
UNCOV 300	this->structured_sdfg_->containers_.insert({entry.first, entry.second->clone()});	×
301	}
302
UNCOV 303	for (auto& arg : sdfg.arguments_) {	×
UNCOV 304	this->structured_sdfg_->arguments_.push_back(arg);	×
305	}
306
UNCOV 307	for (auto& ext : sdfg.externals_) {	×
UNCOV 308	this->structured_sdfg_->externals_.push_back(ext);	×
309	}
310
UNCOV 311	for (auto& entry : sdfg.assumptions_) {	×
UNCOV 312	this->structured_sdfg_->assumptions_.insert({entry.first, entry.second});	×
313	}
314
UNCOV 315	for (auto& entry : sdfg.metadata_) {	×
UNCOV 316	this->structured_sdfg_->metadata_[entry.first] = entry.second;	×
317	}
318
UNCOV 319	this->traverse(sdfg);	×
UNCOV 320	};	×
321
322	StructuredSDFG& StructuredSDFGBuilder::subject() const { return *this->structured_sdfg_; };	62✔
323
UNCOV 324	std::unique_ptr<StructuredSDFG> StructuredSDFGBuilder::move() {	×
UNCOV 325	return std::move(this->structured_sdfg_);	×
326	};
327
UNCOV 328	Sequence& StructuredSDFGBuilder::add_sequence(Sequence& parent,	×
329	const sdfg::control_flow::Assignments& assignments,
330	const DebugInfo& debug_info) {
UNCOV 331	parent.children_.push_back(std::unique_ptr<Sequence>(new Sequence(debug_info)));	×
332
UNCOV 333	parent.transitions_.push_back(	×
NEW 334	std::unique_ptr<Transition>(new Transition(debug_info, parent, assignments)));	×
335
UNCOV 336	return static_cast<Sequence&>(*parent.children_.back().get());	×
337	};	×
338
UNCOV 339	std::pair<Sequence&, Transition&> StructuredSDFGBuilder::add_sequence_before(	×
340	Sequence& parent, ControlFlowNode& block, const DebugInfo& debug_info) {
341	// Insert block before current block
UNCOV 342	int index = -1;	×
UNCOV 343	for (size_t i = 0; i < parent.children_.size(); i++) {	×
UNCOV 344	if (parent.children_.at(i).get() == &block) {	×
UNCOV 345	index = i;	×
UNCOV 346	break;	×
347	}
UNCOV 348	}	×
UNCOV 349	if (index == -1) {	×
350	throw InvalidSDFGException("StructuredSDFGBuilder: Block not found");	×
351	}
352
UNCOV 353	parent.children_.insert(parent.children_.begin() + index,	×
UNCOV 354	std::unique_ptr<Sequence>(new Sequence(debug_info)));	×
355
UNCOV 356	parent.transitions_.insert(parent.transitions_.begin() + index,	×
NEW 357	std::unique_ptr<Transition>(new Transition(debug_info, parent)));	×
358
UNCOV 359	auto new_entry = parent.at(index);	×
UNCOV 360	auto& new_block = dynamic_cast<structured_control_flow::Sequence&>(new_entry.first);	×
361
UNCOV 362	return {new_block, new_entry.second};	×
363	};	×
364
UNCOV 365	void StructuredSDFGBuilder::remove_child(Sequence& parent, size_t i) {	×
UNCOV 366	parent.children_.erase(parent.children_.begin() + i);	×
UNCOV 367	parent.transitions_.erase(parent.transitions_.begin() + i);	×
UNCOV 368	};	×
369
UNCOV 370	void StructuredSDFGBuilder::remove_child(Sequence& parent, ControlFlowNode& child) {	×
UNCOV 371	int index = -1;	×
UNCOV 372	for (size_t i = 0; i < parent.children_.size(); i++) {	×
UNCOV 373	if (parent.children_.at(i).get() == &child) {	×
UNCOV 374	index = i;	×
UNCOV 375	break;	×
376	}
UNCOV 377	}	×
378
UNCOV 379	parent.children_.erase(parent.children_.begin() + index);	×
UNCOV 380	parent.transitions_.erase(parent.transitions_.begin() + index);	×
UNCOV 381	};	×
382
UNCOV 383	void StructuredSDFGBuilder::insert_children(Sequence& parent, Sequence& other, size_t i) {	×
UNCOV 384	parent.children_.insert(parent.children_.begin() + i,	×
UNCOV 385	std::make_move_iterator(other.children_.begin()),	×
UNCOV 386	std::make_move_iterator(other.children_.end()));	×
UNCOV 387	parent.transitions_.insert(parent.transitions_.begin() + i,	×
UNCOV 388	std::make_move_iterator(other.transitions_.begin()),	×
UNCOV 389	std::make_move_iterator(other.transitions_.end()));	×
UNCOV 390	other.children_.clear();	×
UNCOV 391	other.transitions_.clear();	×
UNCOV 392	};	×
393
394	Block& StructuredSDFGBuilder::add_block(Sequence& parent,	20✔
395	const sdfg::control_flow::Assignments& assignments,
396	const DebugInfo& debug_info) {
397	parent.children_.push_back(std::unique_ptr<Block>(new Block(debug_info)));	20✔
398
399	parent.transitions_.push_back(	20✔
400	std::unique_ptr<Transition>(new Transition(debug_info, parent, assignments)));	20✔
401
402	auto& new_block = dynamic_cast<structured_control_flow::Block&>(*parent.children_.back().get());	20✔
403	(*new_block.dataflow_).parent_ = &new_block;	20✔
404
405	return new_block;	20✔
406	};	×
407
UNCOV 408	Block& StructuredSDFGBuilder::add_block(Sequence& parent,	×
409	const data_flow::DataFlowGraph& data_flow_graph,
410	const sdfg::control_flow::Assignments& assignments,
411	const DebugInfo& debug_info) {
UNCOV 412	parent.children_.push_back(std::unique_ptr<Block>(new Block(debug_info, data_flow_graph)));	×
413
UNCOV 414	parent.transitions_.push_back(	×
NEW 415	std::unique_ptr<Transition>(new Transition(debug_info, parent, assignments)));	×
416
UNCOV 417	auto& new_block = dynamic_cast<structured_control_flow::Block&>(*parent.children_.back().get());	×
UNCOV 418	(*new_block.dataflow_).parent_ = &new_block;	×
419
UNCOV 420	return new_block;	×
421	};	×
422
UNCOV 423	std::pair<Block&, Transition&> StructuredSDFGBuilder::add_block_before(	×
424	Sequence& parent, ControlFlowNode& block, const DebugInfo& debug_info) {
425	// Insert block before current block
UNCOV 426	int index = -1;	×
UNCOV 427	for (size_t i = 0; i < parent.children_.size(); i++) {	×
UNCOV 428	if (parent.children_.at(i).get() == &block) {	×
UNCOV 429	index = i;	×
UNCOV 430	break;	×
431	}
432	}	×
UNCOV 433	assert(index > -1);	×
434
UNCOV 435	parent.children_.insert(parent.children_.begin() + index,	×
UNCOV 436	std::unique_ptr<Block>(new Block(debug_info)));	×
437
UNCOV 438	parent.transitions_.insert(parent.transitions_.begin() + index,	×
NEW 439	std::unique_ptr<Transition>(new Transition(debug_info, parent)));	×
440
UNCOV 441	auto new_entry = parent.at(index);	×
UNCOV 442	auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);	×
UNCOV 443	(*new_block.dataflow_).parent_ = &new_block;	×
444
UNCOV 445	return {new_block, new_entry.second};	×
446	};	×
447
448	std::pair<Block&, Transition&> StructuredSDFGBuilder::add_block_before(	×
449	Sequence& parent, ControlFlowNode& block, data_flow::DataFlowGraph& data_flow_graph,
450	const DebugInfo& debug_info) {
451	// Insert block before current block
452	int index = -1;	×
453	for (size_t i = 0; i < parent.children_.size(); i++) {	×
454	if (parent.children_.at(i).get() == &block) {	×
455	index = i;	×
456	break;	×
457	}
458	}	×
459	assert(index > -1);	×
460
461	parent.children_.insert(parent.children_.begin() + index,	×
462	std::unique_ptr<Block>(new Block(debug_info, data_flow_graph)));	×
463
464	parent.transitions_.insert(parent.transitions_.begin() + index,	×
NEW 465	std::unique_ptr<Transition>(new Transition(debug_info, parent)));	×
466
467	auto new_entry = parent.at(index);	×
468	auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);	×
469	(*new_block.dataflow_).parent_ = &new_block;	×
470
471	return {new_block, new_entry.second};	×
472	};	×
473
UNCOV 474	std::pair<Block&, Transition&> StructuredSDFGBuilder::add_block_after(Sequence& parent,	×
475	ControlFlowNode& block,
476	const DebugInfo& debug_info) {
477	// Insert block before current block
UNCOV 478	int index = -1;	×
UNCOV 479	for (size_t i = 0; i < parent.children_.size(); i++) {	×
UNCOV 480	if (parent.children_.at(i).get() == &block) {	×
UNCOV 481	index = i;	×
UNCOV 482	break;	×
483	}
UNCOV 484	}	×
UNCOV 485	assert(index > -1);	×
486
UNCOV 487	parent.children_.insert(parent.children_.begin() + index + 1,	×
UNCOV 488	std::unique_ptr<Block>(new Block(debug_info)));	×
489
UNCOV 490	parent.transitions_.insert(parent.transitions_.begin() + index + 1,	×
NEW 491	std::unique_ptr<Transition>(new Transition(debug_info, parent)));	×
492
UNCOV 493	auto new_entry = parent.at(index + 1);	×
UNCOV 494	auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);	×
UNCOV 495	(*new_block.dataflow_).parent_ = &new_block;	×
496
UNCOV 497	return {new_block, new_entry.second};	×
498	};	×
499
500	std::pair<Block&, Transition&> StructuredSDFGBuilder::add_block_after(	×
501	Sequence& parent, ControlFlowNode& block, data_flow::DataFlowGraph& data_flow_graph,
502	const DebugInfo& debug_info) {
503	int index = -1;	×
504	for (size_t i = 0; i < parent.children_.size(); i++) {	×
505	if (parent.children_.at(i).get() == &block) {	×
506	index = i;	×
507	break;	×
508	}
509	}	×
510	assert(index > -1);	×
511
512	parent.children_.insert(parent.children_.begin() + index + 1,	×
513	std::unique_ptr<Block>(new Block(debug_info, data_flow_graph)));	×
514
515	parent.transitions_.insert(parent.transitions_.begin() + index + 1,	×
NEW 516	std::unique_ptr<Transition>(new Transition(debug_info, parent)));	×
517
518	auto new_entry = parent.at(index + 1);	×
519	auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);	×
520	(*new_block.dataflow_).parent_ = &new_block;	×
521
522	return {new_block, new_entry.second};	×
523	};	×
524
525	For& StructuredSDFGBuilder::add_for(Sequence& parent, const symbolic::Symbol& indvar,	22✔
526	const symbolic::Condition& condition,
527	const symbolic::Expression& init,
528	const symbolic::Expression& update,
529	const sdfg::control_flow::Assignments& assignments,
530	const DebugInfo& debug_info) {
531	parent.children_.push_back(	44✔
532	std::unique_ptr<For>(new For(debug_info, indvar, init, update, condition)));	22✔
533
534	parent.transitions_.push_back(	22✔
535	std::unique_ptr<Transition>(new Transition(debug_info, parent, assignments)));	22✔
536
537	return static_cast<For&>(*parent.children_.back().get());	22✔
538	};	×
539
UNCOV 540	std::pair<For&, Transition&> StructuredSDFGBuilder::add_for_before(	×
541	Sequence& parent, ControlFlowNode& block, const symbolic::Symbol& indvar,
542	const symbolic::Condition& condition, const symbolic::Expression& init,
543	const symbolic::Expression& update, const DebugInfo& debug_info) {
544	// Insert block before current block
UNCOV 545	int index = -1;	×
UNCOV 546	for (size_t i = 0; i < parent.children_.size(); i++) {	×
UNCOV 547	if (parent.children_.at(i).get() == &block) {	×
UNCOV 548	index = i;	×
UNCOV 549	break;	×
550	}
551	}	×
UNCOV 552	assert(index > -1);	×
553
UNCOV 554	parent.children_.insert(	×
UNCOV 555	parent.children_.begin() + index,	×
UNCOV 556	std::unique_ptr<For>(new For(debug_info, indvar, init, update, condition)));	×
557
UNCOV 558	parent.transitions_.insert(parent.transitions_.begin() + index,	×
NEW 559	std::unique_ptr<Transition>(new Transition(debug_info, parent)));	×
560
UNCOV 561	auto new_entry = parent.at(index);	×
UNCOV 562	auto& new_block = dynamic_cast<structured_control_flow::For&>(new_entry.first);	×
563
UNCOV 564	return {new_block, new_entry.second};	×
565	};	×
566
UNCOV 567	std::pair<For&, Transition&> StructuredSDFGBuilder::add_for_after(	×
568	Sequence& parent, ControlFlowNode& block, const symbolic::Symbol& indvar,
569	const symbolic::Condition& condition, const symbolic::Expression& init,
570	const symbolic::Expression& update, const DebugInfo& debug_info) {
571	// Insert block before current block
UNCOV 572	int index = -1;	×
UNCOV 573	for (size_t i = 0; i < parent.children_.size(); i++) {	×
UNCOV 574	if (parent.children_.at(i).get() == &block) {	×
UNCOV 575	index = i;	×
UNCOV 576	break;	×
577	}
UNCOV 578	}	×
UNCOV 579	assert(index > -1);	×
580
UNCOV 581	parent.children_.insert(	×
UNCOV 582	parent.children_.begin() + index + 1,	×
UNCOV 583	std::unique_ptr<For>(new For(debug_info, indvar, init, update, condition)));	×
584
UNCOV 585	parent.transitions_.insert(parent.transitions_.begin() + index + 1,	×
NEW 586	std::unique_ptr<Transition>(new Transition(debug_info, parent)));	×
587
UNCOV 588	auto new_entry = parent.at(index + 1);	×
UNCOV 589	auto& new_block = dynamic_cast<structured_control_flow::For&>(new_entry.first);	×
590
UNCOV 591	return {new_block, new_entry.second};	×
592	};	×
593
UNCOV 594	IfElse& StructuredSDFGBuilder::add_if_else(Sequence& parent, const DebugInfo& debug_info) {	×
UNCOV 595	return this->add_if_else(parent, control_flow::Assignments{}, debug_info);	×
596	};	×
597
UNCOV 598	IfElse& StructuredSDFGBuilder::add_if_else(Sequence& parent,	×
599	const sdfg::control_flow::Assignments& assignments,
600	const DebugInfo& debug_info) {
UNCOV 601	parent.children_.push_back(std::unique_ptr<IfElse>(new IfElse(debug_info)));	×
602
UNCOV 603	parent.transitions_.push_back(	×
NEW 604	std::unique_ptr<Transition>(new Transition(debug_info, parent, assignments)));	×
605
UNCOV 606	return static_cast<IfElse&>(*parent.children_.back().get());	×
607	};	×
608
UNCOV 609	std::pair<IfElse&, Transition&> StructuredSDFGBuilder::add_if_else_before(	×
610	Sequence& parent, ControlFlowNode& block, const DebugInfo& debug_info) {
611	// Insert block before current block
UNCOV 612	int index = -1;	×
UNCOV 613	for (size_t i = 0; i < parent.children_.size(); i++) {	×
UNCOV 614	if (parent.children_.at(i).get() == &block) {	×
UNCOV 615	index = i;	×
UNCOV 616	break;	×
617	}
618	}	×
UNCOV 619	assert(index > -1);	×
620
UNCOV 621	parent.children_.insert(parent.children_.begin() + index,	×
UNCOV 622	std::unique_ptr<IfElse>(new IfElse(debug_info)));	×
623
UNCOV 624	parent.transitions_.insert(parent.transitions_.begin() + index,	×
NEW 625	std::unique_ptr<Transition>(new Transition(debug_info, parent)));	×
626
UNCOV 627	auto new_entry = parent.at(index);	×
UNCOV 628	auto& new_block = dynamic_cast<structured_control_flow::IfElse&>(new_entry.first);	×
629
UNCOV 630	return {new_block, new_entry.second};	×
631	};	×
632
UNCOV 633	Sequence& StructuredSDFGBuilder::add_case(IfElse& scope, const sdfg::symbolic::Condition cond,	×
634	const DebugInfo& debug_info) {
UNCOV 635	scope.cases_.push_back(std::unique_ptr<Sequence>(new Sequence(debug_info)));	×
636
UNCOV 637	scope.conditions_.push_back(cond);	×
UNCOV 638	return *scope.cases_.back();	×
639	};	×
640
UNCOV 641	void StructuredSDFGBuilder::remove_case(IfElse& scope, size_t i, const DebugInfo& debug_info) {	×
UNCOV 642	scope.cases_.erase(scope.cases_.begin() + i);	×
UNCOV 643	scope.conditions_.erase(scope.conditions_.begin() + i);	×
UNCOV 644	};	×
645
UNCOV 646	While& StructuredSDFGBuilder::add_while(Sequence& parent,	×
647	const sdfg::control_flow::Assignments& assignments,
648	const DebugInfo& debug_info) {
UNCOV 649	parent.children_.push_back(std::unique_ptr<While>(new While(debug_info)));	×
650
UNCOV 651	parent.transitions_.push_back(	×
NEW 652	std::unique_ptr<Transition>(new Transition(debug_info, parent, assignments)));	×
653
UNCOV 654	return static_cast<While&>(*parent.children_.back().get());	×
655	};	×
656
UNCOV 657	Continue& StructuredSDFGBuilder::add_continue(Sequence& parent, const DebugInfo& debug_info) {	×
UNCOV 658	return this->add_continue(parent, control_flow::Assignments{}, debug_info);	×
659	};	×
660
UNCOV 661	Continue& StructuredSDFGBuilder::add_continue(Sequence& parent,	×
662	const sdfg::control_flow::Assignments& assignments,
663	const DebugInfo& debug_info) {
664	// Check if continue is in a loop
UNCOV 665	analysis::AnalysisManager analysis_manager(this->subject());	×
UNCOV 666	auto& scope_tree_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	×
UNCOV 667	auto current_scope = scope_tree_analysis.parent_scope(&parent);	×
UNCOV 668	bool in_loop = false;	×
UNCOV 669	while (current_scope != nullptr) {	×
UNCOV 670	if (dynamic_cast<structured_control_flow::While*>(current_scope)) {	×
UNCOV 671	in_loop = true;	×
UNCOV 672	break;	×
UNCOV 673	} else if (dynamic_cast<structured_control_flow::For*>(current_scope)) {	×
674	throw UnstructuredControlFlowException();	×
675	}
UNCOV 676	current_scope = scope_tree_analysis.parent_scope(current_scope);	×
677	}
UNCOV 678	if (!in_loop) {	×
679	throw UnstructuredControlFlowException();	×
680	}
681
UNCOV 682	parent.children_.push_back(std::unique_ptr<Continue>(new Continue(debug_info)));	×
683
UNCOV 684	parent.transitions_.push_back(	×
NEW 685	std::unique_ptr<Transition>(new Transition(debug_info, parent, assignments)));	×
686
UNCOV 687	return static_cast<Continue&>(*parent.children_.back().get());	×
UNCOV 688	};	×
689
UNCOV 690	Break& StructuredSDFGBuilder::add_break(Sequence& parent, const DebugInfo& debug_info) {	×
UNCOV 691	return this->add_break(parent, control_flow::Assignments{}, debug_info);	×
692	};	×
693
UNCOV 694	Break& StructuredSDFGBuilder::add_break(Sequence& parent,	×
695	const sdfg::control_flow::Assignments& assignments,
696	const DebugInfo& debug_info) {
697	// Check if break is in a loop
UNCOV 698	analysis::AnalysisManager analysis_manager(this->subject());	×
UNCOV 699	auto& scope_tree_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	×
UNCOV 700	auto current_scope = scope_tree_analysis.parent_scope(&parent);	×
UNCOV 701	bool in_loop = false;	×
UNCOV 702	while (current_scope != nullptr) {	×
UNCOV 703	if (dynamic_cast<structured_control_flow::While*>(current_scope)) {	×
UNCOV 704	in_loop = true;	×
UNCOV 705	break;	×
UNCOV 706	} else if (dynamic_cast<structured_control_flow::For*>(current_scope)) {	×
707	throw UnstructuredControlFlowException();	×
708	}
UNCOV 709	current_scope = scope_tree_analysis.parent_scope(current_scope);	×
710	}
UNCOV 711	if (!in_loop) {	×
712	throw UnstructuredControlFlowException();	×
713	}
714
UNCOV 715	parent.children_.push_back(std::unique_ptr<Break>(new Break(debug_info)));	×
716
UNCOV 717	parent.transitions_.push_back(	×
NEW 718	std::unique_ptr<Transition>(new Transition(debug_info, parent, assignments)));	×
719
UNCOV 720	return static_cast<Break&>(*parent.children_.back().get());	×
UNCOV 721	};	×
722
UNCOV 723	Return& StructuredSDFGBuilder::add_return(Sequence& parent,	×
724	const sdfg::control_flow::Assignments& assignments,
725	const DebugInfo& debug_info) {
UNCOV 726	parent.children_.push_back(std::unique_ptr<Return>(new Return(debug_info)));	×
727
UNCOV 728	parent.transitions_.push_back(	×
NEW 729	std::unique_ptr<Transition>(new Transition(debug_info, parent, assignments)));	×
730
UNCOV 731	return static_cast<Return&>(*parent.children_.back().get());	×
732	};	×
733
UNCOV 734	Map& StructuredSDFGBuilder::add_map(Sequence& parent, const symbolic::Symbol& indvar,	×
735	const symbolic::Expression& num_iterations,
736	const ScheduleType& schedule_type,
737	const sdfg::control_flow::Assignments& assignments,
738	const DebugInfo& debug_info) {
UNCOV 739	parent.children_.push_back(	×
UNCOV 740	std::unique_ptr<Map>(new Map(debug_info, indvar, num_iterations, schedule_type)));	×
741
UNCOV 742	parent.transitions_.push_back(	×
NEW 743	std::unique_ptr<Transition>(new Transition(debug_info, parent, assignments)));	×
744
UNCOV 745	return static_cast<Map&>(*parent.children_.back().get());	×
746	};	×
747
748	For& StructuredSDFGBuilder::convert_while(Sequence& parent, While& loop,	×
749	const symbolic::Symbol& indvar,
750	const symbolic::Condition& condition,
751	const symbolic::Expression& init,
752	const symbolic::Expression& update) {
753	// Insert for loop
754	size_t index = 0;	×
755	for (auto& entry : parent.children_) {	×
756	if (entry.get() == &loop) {	×
757	break;	×
758	}
759	index++;	×
760	}
761	auto iter = parent.children_.begin() + index;	×
762	auto& new_iter = *parent.children_.insert(	×
763	iter + 1,	×
764	std::unique_ptr<For>(new For(loop.debug_info(), indvar, init, update, condition)));	×
765
766	auto& for_loop = dynamic_cast<For&>(*new_iter);	×
767	this->insert_children(for_loop.root(), loop.root(), 0);	×
768
769	// Remove while loop
770	parent.children_.erase(parent.children_.begin() + index);	×
771
772	return for_loop;	×
773	};	×
774
UNCOV 775	Map& StructuredSDFGBuilder::convert_for(Sequence& parent, For& loop,	×
776	const symbolic::Expression& num_iterations) {
777	// Insert for loop
UNCOV 778	size_t index = 0;	×
UNCOV 779	for (auto& entry : parent.children_) {	×
UNCOV 780	if (entry.get() == &loop) {	×
UNCOV 781	break;	×
782	}
783	index++;	×
784	}
UNCOV 785	auto iter = parent.children_.begin() + index;	×
UNCOV 786	auto& new_iter = *parent.children_.insert(	×
UNCOV 787	iter + 1, std::unique_ptr<Map>(new Map(loop.debug_info(), loop.indvar(), num_iterations,	×
UNCOV 788	ScheduleType_Sequential)));	×
789
UNCOV 790	auto& map = dynamic_cast<Map&>(*new_iter);	×
UNCOV 791	this->insert_children(map.root(), loop.root(), 0);	×
792
793	// Remove for loop
UNCOV 794	parent.children_.erase(parent.children_.begin() + index);	×
795
UNCOV 796	return map;	×
797	};	×
798
UNCOV 799	void StructuredSDFGBuilder::clear_sequence(Sequence& parent) {	×
UNCOV 800	parent.children_.clear();	×
UNCOV 801	parent.transitions_.clear();	×
UNCOV 802	};	×
803
UNCOV 804	Sequence& StructuredSDFGBuilder::parent(const ControlFlowNode& node) {	×
UNCOV 805	std::list<structured_control_flow::ControlFlowNode*> queue = {&this->structured_sdfg_->root()};	×
UNCOV 806	while (!queue.empty()) {	×
UNCOV 807	auto current = queue.front();	×
UNCOV 808	queue.pop_front();	×
809
UNCOV 810	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	×
UNCOV 811	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
UNCOV 812	if (&sequence_stmt->at(i).first == &node) {	×
UNCOV 813	return *sequence_stmt;	×
814	}
UNCOV 815	queue.push_back(&sequence_stmt->at(i).first);	×
UNCOV 816	}	×
UNCOV 817	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {	×
818	for (size_t i = 0; i < if_else_stmt->size(); i++) {	×
819	queue.push_back(&if_else_stmt->at(i).first);	×
820	}	×
UNCOV 821	} else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	×
822	queue.push_back(&while_stmt->root());	×
UNCOV 823	} else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {	×
UNCOV 824	queue.push_back(&for_stmt->root());	×
UNCOV 825	}	×
826	}
827
828	return this->structured_sdfg_->root();	×
UNCOV 829	};	×
830
831	/*** Section: Dataflow Graph ***/
832
833	data_flow::AccessNode& StructuredSDFGBuilder::add_access(structured_control_flow::Block& block,	45✔
834	const std::string& data,
835	const DebugInfo& debug_info) {
836	// Check: Data exists
837	if (!this->subject().exists(data)) {	45✔
838	throw InvalidSDFGException("Data does not exist in SDFG: " + data);	×
839	}
840
841	auto vertex = boost::add_vertex(block.dataflow_->graph_);	45✔
842	auto res = block.dataflow_->nodes_.insert(	90✔
843	{vertex, std::unique_ptr<data_flow::AccessNode>(	45✔
844	new data_flow::AccessNode(debug_info, vertex, block.dataflow(), data))});	45✔
845
846	return dynamic_cast<data_flow::AccessNode&>(*(res.first->second));	45✔
847	};	×
848
849	data_flow::Tasklet& StructuredSDFGBuilder::add_tasklet(	20✔
850	structured_control_flow::Block& block, const data_flow::TaskletCode code,
851	const std::pair<std::string, sdfg::types::Scalar>& output,
852	const std::vector<std::pair<std::string, sdfg::types::Scalar>>& inputs,
853	const DebugInfo& debug_info) {
854	// Check: Duplicate inputs
855	std::unordered_set<std::string> input_names;	20✔
856	for (auto& input : inputs) {	46✔
857	if (!input.first.starts_with("_in")) {	26✔
858	continue;	1✔
859	}
860	if (input_names.find(input.first) != input_names.end()) {	25✔
861	throw InvalidSDFGException("Input " + input.first + " already exists in SDFG");	×
862	}
863	input_names.insert(input.first);	25✔
864	}
865
866	auto vertex = boost::add_vertex(block.dataflow_->graph_);	20✔
867	auto res = block.dataflow_->nodes_.insert(	40✔
868	{vertex,	20✔
869	std::unique_ptr<data_flow::Tasklet>(new data_flow::Tasklet(	40✔
870	debug_info, vertex, block.dataflow(), code, output, inputs, symbolic::__true__()))});	20✔
871
872	return dynamic_cast<data_flow::Tasklet&>(*(res.first->second));	20✔
873	};	20✔
874
875	data_flow::Memlet& StructuredSDFGBuilder::add_memlet(	45✔
876	structured_control_flow::Block& block, data_flow::DataFlowNode& src,
877	const std::string& src_conn, data_flow::DataFlowNode& dst, const std::string& dst_conn,
878	const data_flow::Subset& subset, const DebugInfo& debug_info) {
879	auto& function_ = this->function();	45✔
880
881	// Check - Case 1: Access Node -> Access Node
882	// - src_conn or dst_conn must be refs. The other must be void.
883	// - The side of the memlet that is void, is dereferenced.
884	// - The dst type must always be a pointer after potential dereferencing.
885	// - The src type can be any type after dereferecing (&dereferenced_src_type).
886	if (dynamic_cast<data_flow::AccessNode>(&src) && dynamic_cast<data_flow::AccessNode>(&dst)) {	45✔
UNCOV 887	auto& src_node = dynamic_cast<data_flow::AccessNode&>(src);	×
UNCOV 888	auto& dst_node = dynamic_cast<data_flow::AccessNode&>(dst);	×
UNCOV 889	if (src_conn == "refs") {	×
890	if (dst_conn != "void") {	×
891	throw InvalidSDFGException("Invalid dst connector: " + dst_conn);	×
892	}
893
894	auto& dst_type = types::infer_type(function_, function_.type(dst_node.data()), subset);	×
895	if (!dynamic_cast<const types::Pointer*>(&dst_type)) {	×
896	throw InvalidSDFGException("dst type must be a pointer");	×
897	}
898
899	auto& src_type = function_.type(src_node.data());	×
900	if (!dynamic_cast<const types::Pointer*>(&src_type)) {	×
901	throw InvalidSDFGException("src type must be a pointer");	×
902	}
UNCOV 903	} else if (src_conn == "void") {	×
UNCOV 904	if (dst_conn != "refs") {	×
905	throw InvalidSDFGException("Invalid dst connector: " + dst_conn);	×
906	}
907
UNCOV 908	if (symbolic::is_pointer(symbolic::symbol(src_node.data()))) {	×
909	throw InvalidSDFGException("src_conn is void: src cannot be a raw pointer");	×
910	}
911
912	// Trivially correct but checks inference
UNCOV 913	auto& src_type = types::infer_type(function_, function_.type(src_node.data()), subset);	×
UNCOV 914	types::Pointer ref_type(src_type);	×
915	if (!dynamic_cast<const types::Pointer*>(&ref_type)) {
916	throw InvalidSDFGException("src type must be a pointer");
917	}
918
UNCOV 919	auto& dst_type = function_.type(dst_node.data());	×
UNCOV 920	if (!dynamic_cast<const types::Pointer*>(&dst_type)) {	×
921	throw InvalidSDFGException("dst type must be a pointer");	×
922	}
UNCOV 923	} else {	×
924	throw InvalidSDFGException("Invalid src connector: " + src_conn);	×
925	}
926	} else if (dynamic_cast<data_flow::AccessNode*>(&src) &&	69✔
927	dynamic_cast<data_flow::Tasklet*>(&dst)) {	24✔
928	auto& src_node = dynamic_cast<data_flow::AccessNode&>(src);	24✔
929	auto& dst_node = dynamic_cast<data_flow::Tasklet&>(dst);	24✔
930	if (src_conn != "void") {	24✔
931	throw InvalidSDFGException("src_conn must be void. Found: " + src_conn);	×
932	}
933	bool found = false;	24✔
934	for (auto& input : dst_node.inputs()) {	31✔
935	if (input.first == dst_conn) {	31✔
936	found = true;	24✔
937	break;	24✔
938	}
939	}
940	if (!found) {	24✔
941	throw InvalidSDFGException("dst_conn not found in tasklet: " + dst_conn);	×
942	}
943	auto& element_type = types::infer_type(function_, function_.type(src_node.data()), subset);	24✔
944	if (!dynamic_cast<const types::Scalar*>(&element_type)) {	24✔
945	throw InvalidSDFGException("Tasklets inputs must be scalars");	×
946	}
947	} else if (dynamic_cast<data_flow::Tasklet*>(&src) &&	66✔
948	dynamic_cast<data_flow::AccessNode*>(&dst)) {	21✔
949	auto& src_node = dynamic_cast<data_flow::Tasklet&>(src);	21✔
950	auto& dst_node = dynamic_cast<data_flow::AccessNode&>(dst);	21✔
951	if (src_conn != src_node.output().first) {	21✔
952	throw InvalidSDFGException("src_conn must match tasklet output name");	×
953	}
954	if (dst_conn != "void") {	21✔
955	throw InvalidSDFGException("dst_conn must be void. Found: " + dst_conn);	×
956	}
957
958	auto& element_type = types::infer_type(function_, function_.type(dst_node.data()), subset);	21✔
959	if (!dynamic_cast<const types::Scalar*>(&element_type)) {	21✔
960	throw InvalidSDFGException("Tasklet output must be a scalar");	×
961	}
962	} else if (dynamic_cast<data_flow::AccessNode*>(&src) &&	21✔
963	dynamic_cast<data_flow::LibraryNode*>(&dst)) {	×
964	auto& src_node = dynamic_cast<data_flow::AccessNode&>(src);	×
965	auto& dst_node = dynamic_cast<data_flow::LibraryNode&>(dst);	×
966	if (src_conn != "void") {	×
967	throw InvalidSDFGException("src_conn must be void. Found: " + src_conn);	×
968	}
969	bool found = false;	×
970	for (auto& input : dst_node.inputs()) {	×
971	if (input == dst_conn) {	×
972	found = true;	×
973	break;	×
974	}
975	}
976	if (!found) {	×
977	throw InvalidSDFGException("dst_conn not found in library node: " + dst_conn);	×
978	}
979
980	auto& element_type = types::infer_type(function_, function_.type(src_node.data()), subset);	×
981	if (!dynamic_cast<const types::Scalar*>(&element_type)) {	×
982	throw InvalidSDFGException("Library node inputs must be scalars");	×
983	}
984	} else if (dynamic_cast<data_flow::LibraryNode*>(&src) &&	×
985	dynamic_cast<data_flow::AccessNode*>(&dst)) {	×
986	auto& src_node = dynamic_cast<data_flow::LibraryNode&>(src);	×
987	auto& dst_node = dynamic_cast<data_flow::AccessNode&>(dst);	×
988	if (dst_conn != "void") {	×
989	throw InvalidSDFGException("dst_conn must be void. Found: " + dst_conn);	×
990	}
991	bool found = false;	×
992	for (auto& output : src_node.outputs()) {	×
993	if (output == src_conn) {	×
994	found = true;	×
995	break;	×
996	}
997	}
998	if (!found) {	×
999	throw InvalidSDFGException("src_conn not found in library node: " + src_conn);	×
1000	}
1001
1002	auto& element_type = types::infer_type(function_, function_.type(dst_node.data()), subset);	×
1003	if (!dynamic_cast<const types::Pointer*>(&element_type)) {	×
1004	throw InvalidSDFGException("Access node must be a pointer");	×
1005	}
1006	} else {	×
1007	throw InvalidSDFGException("Invalid src or dst node type");	×
1008	}
1009
1010	auto edge = boost::add_edge(src.vertex_, dst.vertex_, block.dataflow_->graph_);	45✔
1011	auto res = block.dataflow_->edges_.insert(	90✔
1012	{edge.first,	90✔
1013	std::unique_ptr<data_flow::Memlet>(new data_flow::Memlet(	45✔
1014	debug_info, edge.first, block.dataflow(), src, src_conn, dst, dst_conn, subset))});	45✔
1015
1016	return dynamic_cast<data_flow::Memlet&>(*(res.first->second));	45✔
1017	};	×
1018
1019	void StructuredSDFGBuilder::remove_memlet(structured_control_flow::Block& block,	×
1020	const data_flow::Memlet& edge) {
1021	auto& graph = block.dataflow();	×
1022	auto e = edge.edge();	×
1023	boost::remove_edge(e, graph.graph_);	×
1024	graph.edges_.erase(e);	×
1025	};	×
1026
1027	void StructuredSDFGBuilder::remove_node(structured_control_flow::Block& block,	×
1028	const data_flow::DataFlowNode& node) {
1029	auto& graph = block.dataflow();	×
1030	auto v = node.vertex();	×
1031	boost::remove_vertex(v, graph.graph_);	×
1032	graph.nodes_.erase(v);	×
1033	};	×
1034
UNCOV 1035	void StructuredSDFGBuilder::clear_node(structured_control_flow::Block& block,	×
1036	const data_flow::Tasklet& node) {
UNCOV 1037	auto& graph = block.dataflow();	×
1038
UNCOV 1039	std::unordered_set<const data_flow::DataFlowNode*> to_delete = {&node};	×
1040
1041	// Delete incoming
UNCOV 1042	std::list<const data_flow::Memlet*> iedges;	×
UNCOV 1043	for (auto& iedge : graph.in_edges(node)) {	×
UNCOV 1044	iedges.push_back(&iedge);	×
1045	}
UNCOV 1046	for (auto iedge : iedges) {	×
UNCOV 1047	auto& src = iedge->src();	×
UNCOV 1048	to_delete.insert(&src);	×
1049
UNCOV 1050	auto edge = iedge->edge();	×
UNCOV 1051	graph.edges_.erase(edge);	×
UNCOV 1052	boost::remove_edge(edge, graph.graph_);	×
1053	}
1054
1055	// Delete outgoing
UNCOV 1056	std::list<const data_flow::Memlet*> oedges;	×
UNCOV 1057	for (auto& oedge : graph.out_edges(node)) {	×
UNCOV 1058	oedges.push_back(&oedge);	×
1059	}
UNCOV 1060	for (auto oedge : oedges) {	×
UNCOV 1061	auto& dst = oedge->dst();	×
UNCOV 1062	to_delete.insert(&dst);	×
1063
UNCOV 1064	auto edge = oedge->edge();	×
UNCOV 1065	graph.edges_.erase(edge);	×
UNCOV 1066	boost::remove_edge(edge, graph.graph_);	×
1067	}
1068
1069	// Delete nodes
UNCOV 1070	for (auto obsolete_node : to_delete) {	×
UNCOV 1071	if (graph.in_degree(obsolete_node) == 0 && graph.out_degree(obsolete_node) == 0) {	×
UNCOV 1072	auto vertex = obsolete_node->vertex();	×
UNCOV 1073	graph.nodes_.erase(vertex);	×
UNCOV 1074	boost::remove_vertex(vertex, graph.graph_);	×
UNCOV 1075	}	×
1076	}
UNCOV 1077	};	×
1078
UNCOV 1079	void StructuredSDFGBuilder::clear_node(structured_control_flow::Block& block,	×
1080	const data_flow::AccessNode& node) {
UNCOV 1081	auto& graph = block.dataflow();	×
UNCOV 1082	if (graph.out_degree(node) != 0) {	×
1083	throw InvalidSDFGException("StructuredSDFGBuilder: Access node has outgoing edges");	×
1084	}
1085
UNCOV 1086	std::list<const data_flow::Memlet*> tmp;	×
UNCOV 1087	std::list<const data_flow::DataFlowNode*> queue = {&node};	×
UNCOV 1088	while (!queue.empty()) {	×
UNCOV 1089	auto current = queue.front();	×
UNCOV 1090	queue.pop_front();	×
UNCOV 1091	if (current != &node) {	×
UNCOV 1092	if (dynamic_cast<const data_flow::AccessNode*>(current)) {	×
1093	if (graph.in_degree(current) > 0 \|\| graph.out_degree(current) > 0) {	×
1094	continue;	×
1095	}
1096	}	×
UNCOV 1097	}	×
1098
UNCOV 1099	tmp.clear();	×
UNCOV 1100	for (auto& iedge : graph.in_edges(*current)) {	×
UNCOV 1101	tmp.push_back(&iedge);	×
1102	}
UNCOV 1103	for (auto iedge : tmp) {	×
UNCOV 1104	auto& src = iedge->src();	×
UNCOV 1105	queue.push_back(&src);	×
1106
UNCOV 1107	auto edge = iedge->edge();	×
UNCOV 1108	graph.edges_.erase(edge);	×
UNCOV 1109	boost::remove_edge(edge, graph.graph_);	×
1110	}
1111
UNCOV 1112	auto vertex = current->vertex();	×
UNCOV 1113	graph.nodes_.erase(vertex);	×
UNCOV 1114	boost::remove_vertex(vertex, graph.graph_);	×
1115	}
UNCOV 1116	};	×
1117
1118	data_flow::AccessNode& StructuredSDFGBuilder::symbolic_expression_to_dataflow(	×
1119	structured_control_flow::Block& parent, const symbolic::Expression& expr) {
1120	auto& sdfg = this->subject();	×
1121
1122	codegen::CPPLanguageExtension language_extension;	×
1123
1124	// Base cases
1125	if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {	×
1126	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);	×
1127
1128	// Determine type
1129	types::Scalar sym_type = types::Scalar(types::PrimitiveType::Void);	×
1130	if (symbolic::is_nv(sym)) {	×
1131	sym_type = types::Scalar(types::PrimitiveType::Int32);	×
1132	} else {	×
1133	sym_type = static_cast<const types::Scalar&>(sdfg.type(sym->get_name()));	×
1134	}
1135
1136	// Add new container for intermediate result
1137	auto tmp = this->find_new_name();	×
1138	this->add_container(tmp, sym_type);	×
1139
1140	// Create dataflow graph
1141	auto& input_node = this->add_access(parent, sym->get_name());	×
1142	auto& output_node = this->add_access(parent, tmp);	×
1143	auto& tasklet = this->add_tasklet(parent, data_flow::TaskletCode::assign,	×
1144	{"_out", sym_type}, {{"_in", sym_type}});	×
1145	this->add_memlet(parent, input_node, "void", tasklet, "_in", {});	×
1146	this->add_memlet(parent, tasklet, "_out", output_node, "void", {});	×
1147
1148	return output_node;	×
1149	} else if (SymEngine::is_a<SymEngine::Integer>(*expr)) {	×
1150	auto tmp = this->find_new_name();	×
1151	this->add_container(tmp, types::Scalar(types::PrimitiveType::Int64));	×
1152
1153	auto& output_node = this->add_access(parent, tmp);	×
1154	auto& tasklet = this->add_tasklet(	×
1155	parent, data_flow::TaskletCode::assign,	×
1156	{"_out", types::Scalar(types::PrimitiveType::Int64)},	×
1157	{{language_extension.expression(expr), types::Scalar(types::PrimitiveType::Int64)}});	×
1158	this->add_memlet(parent, tasklet, "_out", output_node, "void", {});	×
1159	return output_node;	×
1160	} else if (SymEngine::is_a<SymEngine::BooleanAtom>(*expr)) {	×
1161	auto tmp = this->find_new_name();	×
1162	this->add_container(tmp, types::Scalar(types::PrimitiveType::Bool));	×
1163
1164	auto& output_node = this->add_access(parent, tmp);	×
1165	auto& tasklet = this->add_tasklet(	×
1166	parent, data_flow::TaskletCode::assign,	×
1167	{"_out", types::Scalar(types::PrimitiveType::Bool)},	×
1168	{{language_extension.expression(expr), types::Scalar(types::PrimitiveType::Bool)}});	×
1169	this->add_memlet(parent, tasklet, "_out", output_node, "void", {});	×
1170	return output_node;	×
1171	} else if (SymEngine::is_a<SymEngine::Or>(*expr)) {	×
1172	auto or_expr = SymEngine::rcp_static_cast<const SymEngine::Or>(expr);	×
1173	if (or_expr->get_container().size() != 2) {	×
1174	throw InvalidSDFGException(	×
1175	"StructuredSDFGBuilder: Or expression must have exactly two arguments");	×
1176	}
1177
1178	std::vector<data_flow::AccessNode*> input_nodes;	×
1179	std::vector<std::pair<std::string, types::Scalar>> input_types;	×
1180	for (auto& arg : or_expr->get_container()) {	×
1181	auto& input_node = symbolic_expression_to_dataflow(parent, arg);	×
1182	input_nodes.push_back(&input_node);	×
1183	input_types.push_back(	×
1184	{"_in" + std::to_string(input_types.size() + 1),	×
1185	static_cast<const types::Scalar&>(sdfg.type(input_node.data()))});	×
1186	}
1187
1188	// Add new container for intermediate result
1189	auto tmp = this->find_new_name();	×
1190	this->add_container(tmp, types::Scalar(types::PrimitiveType::Bool));	×
1191
1192	auto& output_node = this->add_access(parent, tmp);	×
1193	auto& tasklet =	×
1194	this->add_tasklet(parent, data_flow::TaskletCode::logical_or,	×
1195	{"_out", types::Scalar(types::PrimitiveType::Bool)}, input_types);	×
1196	for (size_t i = 0; i < input_nodes.size(); i++) {	×
1197	this->add_memlet(parent, *input_nodes.at(i), "void", tasklet, input_types.at(i).first,	×
1198	{});	×
1199	}	×
1200	this->add_memlet(parent, tasklet, "_out", output_node, "void", {});	×
1201	return output_node;	×
1202	} else if (SymEngine::is_a<SymEngine::And>(*expr)) {	×
1203	auto and_expr = SymEngine::rcp_static_cast<const SymEngine::And>(expr);	×
1204	if (and_expr->get_container().size() != 2) {	×
1205	throw InvalidSDFGException(	×
1206	"StructuredSDFGBuilder: And expression must have exactly two arguments");	×
1207	}
1208
1209	std::vector<data_flow::AccessNode*> input_nodes;	×
1210	std::vector<std::pair<std::string, types::Scalar>> input_types;	×
1211	for (auto& arg : and_expr->get_container()) {	×
1212	auto& input_node = symbolic_expression_to_dataflow(parent, arg);	×
1213	input_nodes.push_back(&input_node);	×
1214	input_types.push_back(	×
1215	{"_in" + std::to_string(input_types.size() + 1),	×
1216	static_cast<const types::Scalar&>(sdfg.type(input_node.data()))});	×
1217	}
1218
1219	// Add new container for intermediate result
1220	auto tmp = this->find_new_name();	×
1221	this->add_container(tmp, types::Scalar(types::PrimitiveType::Bool));	×
1222
1223	auto& output_node = this->add_access(parent, tmp);	×
1224	auto& tasklet =	×
1225	this->add_tasklet(parent, data_flow::TaskletCode::logical_and,	×
1226	{"_out", types::Scalar(types::PrimitiveType::Bool)}, input_types);	×
1227	for (size_t i = 0; i < input_nodes.size(); i++) {	×
1228	this->add_memlet(parent, *input_nodes.at(i), "void", tasklet, input_types.at(i).first,	×
1229	{});	×
1230	}	×
1231	this->add_memlet(parent, tasklet, "_out", output_node, "void", {});	×
1232	return output_node;	×
1233	} else {	×
1234	throw std::runtime_error("Unsupported expression type");	×
1235	}
1236	};	×
1237
1238	} // namespace builder
1239	} // 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