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/builder/sdfg_builder.cpp

1	#include "sdfg/builder/sdfg_builder.h"
2
3	#include "sdfg/types/utils.h"
4
5	namespace sdfg {
6	namespace builder {
7
UNCOV 8	Function& SDFGBuilder::function() const { return static_cast<Function&>(*this->sdfg_); };	×
9
10	SDFGBuilder::SDFGBuilder(std::unique_ptr<SDFG>& sdfg)	×
11	: FunctionBuilder(), sdfg_(std::move(sdfg)) {	×
12
13	};	×
14
UNCOV 15	SDFGBuilder::SDFGBuilder(const std::string& name, FunctionType type)	×
UNCOV 16	: FunctionBuilder(), sdfg_(new SDFG(name, type)) {	×
17
UNCOV 18	};	×
19
UNCOV 20	SDFG& SDFGBuilder::subject() const { return *this->sdfg_; };	×
21
UNCOV 22	std::unique_ptr<SDFG> SDFGBuilder::move() { return std::move(this->sdfg_); };	×
23
24	/*** Section: Control-Flow Graph ***/
25
UNCOV 26	control_flow::State& SDFGBuilder::add_state(bool is_start_state, const DebugInfo& debug_info) {	×
UNCOV 27	auto vertex = boost::add_vertex(this->sdfg_->graph_);	×
UNCOV 28	auto res = this->sdfg_->states_.insert(	×
UNCOV 29	{vertex,	×
UNCOV 30	std::unique_ptr<control_flow::State>(new control_flow::State(debug_info, vertex))});	×
31
UNCOV 32	assert(res.second);	×
UNCOV 33	(res.first).second->dataflow_->parent_ = (res.first).second.get();	×
34
UNCOV 35	if (is_start_state) {	×
UNCOV 36	this->sdfg_->start_state_ = (*res.first).second.get();	×
UNCOV 37	}	×
38
UNCOV 39	return (res.first).second;	×
40	};	×
41
UNCOV 42	control_flow::State& SDFGBuilder::add_state_before(const control_flow::State& state,	×
43	bool is_start_state,
44	const DebugInfo& debug_info) {
UNCOV 45	auto& new_state = this->add_state(false, debug_info);	×
46
UNCOV 47	std::vector<const control_flow::InterstateEdge*> to_redirect;	×
UNCOV 48	for (auto& e : this->sdfg_->in_edges(state)) to_redirect.push_back(&e);	×
49
50	// Redirect control-flow
UNCOV 51	for (auto edge : to_redirect) {	×
UNCOV 52	this->add_edge(edge->src(), new_state, edge->condition());	×
53
UNCOV 54	auto desc = edge->edge();	×
UNCOV 55	this->sdfg_->edges_.erase(desc);	×
UNCOV 56	boost::remove_edge(desc, this->sdfg_->graph_);	×
57	}
UNCOV 58	this->add_edge(new_state, state);	×
59
UNCOV 60	if (is_start_state) {	×
61	this->sdfg_->start_state_ = &new_state;	×
62	}	×
63
UNCOV 64	return new_state;	×
UNCOV 65	};	×
66
UNCOV 67	control_flow::State& SDFGBuilder::add_state_after(const control_flow::State& state,	×
68	bool connect_states,
69	const DebugInfo& debug_info) {
UNCOV 70	auto& new_state = this->add_state(false, debug_info);	×
71
UNCOV 72	std::vector<const control_flow::InterstateEdge*> to_redirect;	×
UNCOV 73	for (auto& e : this->sdfg_->out_edges(state)) to_redirect.push_back(&e);	×
74
75	// Redirect control-flow
UNCOV 76	for (auto& edge : to_redirect) {	×
UNCOV 77	this->add_edge(new_state, edge->dst(), edge->condition());	×
78
UNCOV 79	auto desc = edge->edge();	×
UNCOV 80	this->sdfg_->edges_.erase(desc);	×
UNCOV 81	boost::remove_edge(desc, this->sdfg_->graph_);	×
82	}
UNCOV 83	if (connect_states) {	×
UNCOV 84	this->add_edge(state, new_state);	×
UNCOV 85	}	×
86
UNCOV 87	return new_state;	×
UNCOV 88	};	×
89
UNCOV 90	control_flow::InterstateEdge& SDFGBuilder::add_edge(const control_flow::State& src,	×
91	const control_flow::State& dst,
92	const DebugInfo& debug_info) {
UNCOV 93	return this->add_edge(src, dst, control_flow::Assignments{}, SymEngine::boolTrue, debug_info);	×
94	};	×
95
UNCOV 96	control_flow::InterstateEdge& SDFGBuilder::add_edge(const control_flow::State& src,	×
97	const control_flow::State& dst,
98	const symbolic::Condition condition,
99	const DebugInfo& debug_info) {
UNCOV 100	return this->add_edge(src, dst, control_flow::Assignments{}, condition, debug_info);	×
101	};	×
102
UNCOV 103	control_flow::InterstateEdge& SDFGBuilder::add_edge(const control_flow::State& src,	×
104	const control_flow::State& dst,
105	const control_flow::Assignments& assignments,
106	const DebugInfo& debug_info) {
UNCOV 107	return this->add_edge(src, dst, assignments, SymEngine::boolTrue, debug_info);	×
108	};	×
109
UNCOV 110	control_flow::InterstateEdge& SDFGBuilder::add_edge(const control_flow::State& src,	×
111	const control_flow::State& dst,
112	const control_flow::Assignments& assignments,
113	const symbolic::Condition condition,
114	const DebugInfo& debug_info) {
UNCOV 115	auto edge = boost::add_edge(src.vertex_, dst.vertex_, this->sdfg_->graph_);	×
UNCOV 116	assert(edge.second);	×
117
UNCOV 118	auto res = this->sdfg_->edges_.insert(	×
UNCOV 119	{edge.first, std::unique_ptr<control_flow::InterstateEdge>(new control_flow::InterstateEdge(	×
UNCOV 120	debug_info, edge.first, src, dst, condition, assignments))});	×
121
UNCOV 122	assert(res.second);	×
123
UNCOV 124	return (res.first).second;	×
125	};	×
126
127	void SDFGBuilder::remove_edge(const control_flow::InterstateEdge& edge) {	×
128	auto desc = edge.edge();	×
129	this->sdfg_->edges_.erase(desc);	×
130
131	boost::remove_edge(desc, this->sdfg_->graph_);	×
132	};	×
133
UNCOV 134	std::tuple<control_flow::State&, control_flow::State&, control_flow::State&> SDFGBuilder::add_loop(	×
135	const control_flow::State& state, sdfg::symbolic::Symbol iterator,
136	sdfg::symbolic::Expression init, sdfg::symbolic::Condition cond,
137	sdfg::symbolic::Expression update, const DebugInfo& debug_info) {
138	// Init: iterator = init
UNCOV 139	auto& init_state = this->add_state_after(state, true, debug_info);	×
UNCOV 140	const graph::Edge init_edge_desc = (*this->sdfg_->in_edges(init_state).begin()).edge_;	×
UNCOV 141	auto& init_edge = this->sdfg_->edges_[init_edge_desc];	×
UNCOV 142	init_edge->assignments_.insert({iterator, init});	×
143
144	// Final state
UNCOV 145	auto& final_state = this->add_state_after(init_state, false, debug_info);	×
146
147	// Init -> early_exit -> final
UNCOV 148	auto& early_exit_state = this->add_state(false, debug_info);	×
UNCOV 149	this->add_edge(init_state, early_exit_state, symbolic::Not(cond));	×
UNCOV 150	this->add_edge(early_exit_state, final_state);	×
151
152	// Init -> header -> body
UNCOV 153	auto& header_state = this->add_state(false, debug_info);	×
UNCOV 154	this->add_edge(init_state, header_state, cond);	×
155
UNCOV 156	auto& body_state = this->add_state(false, debug_info);	×
UNCOV 157	this->add_edge(header_state, body_state);	×
158
UNCOV 159	auto& update_state = this->add_state(false, debug_info);	×
UNCOV 160	this->add_edge(body_state, update_state, {{iterator, update}});	×
161
162	// Back edge and exit edge
UNCOV 163	this->add_edge(update_state, header_state, cond);	×
UNCOV 164	this->add_edge(update_state, final_state, symbolic::Not(cond));	×
165
UNCOV 166	return {init_state, body_state, final_state};	×
167	};	×
168
169	/*** Section: Dataflow Graph ***/
170
UNCOV 171	data_flow::AccessNode& SDFGBuilder::add_access(control_flow::State& state, const std::string& data,	×
172	const DebugInfo& debug_info) {
173	// Check: Data exists
UNCOV 174	if (!this->subject().exists(data)) {	×
175	throw InvalidSDFGException("Data does not exist in SDFG: " + data);	×
176	}
177
UNCOV 178	auto& dataflow = state.dataflow();	×
UNCOV 179	auto vertex = boost::add_vertex(dataflow.graph_);	×
UNCOV 180	auto res = dataflow.nodes_.insert(	×
UNCOV 181	{vertex, std::unique_ptr<data_flow::AccessNode>(	×
UNCOV 182	new data_flow::AccessNode(debug_info, vertex, dataflow, data))});	×
183
UNCOV 184	return dynamic_cast<data_flow::AccessNode&>(*(res.first->second));	×
185	};	×
186
UNCOV 187	data_flow::Tasklet& SDFGBuilder::add_tasklet(	×
188	control_flow::State& state, const data_flow::TaskletCode code,
189	const std::pair<std::string, sdfg::types::Scalar>& output,
190	const std::vector<std::pair<std::string, sdfg::types::Scalar>>& inputs,
191	const DebugInfo& debug_info) {
192	// Check: Duplicate inputs
UNCOV 193	std::unordered_set<std::string> input_names;	×
UNCOV 194	for (auto& input : inputs) {	×
UNCOV 195	if (!input.first.starts_with("_in")) {	×
UNCOV 196	continue;	×
197	}
UNCOV 198	if (input_names.find(input.first) != input_names.end()) {	×
199	throw InvalidSDFGException("Input " + input.first + " already exists in SDFG");	×
200	}
UNCOV 201	input_names.insert(input.first);	×
202	}
203
UNCOV 204	auto& dataflow = state.dataflow();	×
UNCOV 205	auto vertex = boost::add_vertex(dataflow.graph_);	×
UNCOV 206	auto res = dataflow.nodes_.insert(	×
UNCOV 207	{vertex, std::unique_ptr<data_flow::Tasklet>(new data_flow::Tasklet(	×
UNCOV 208	debug_info, vertex, dataflow, code, output, inputs, symbolic::__true__()))});	×
209
UNCOV 210	return dynamic_cast<data_flow::Tasklet&>(*(res.first->second));	×
UNCOV 211	};	×
212
UNCOV 213	data_flow::Memlet& SDFGBuilder::add_memlet(control_flow::State& state, data_flow::DataFlowNode& src,	×
214	const std::string& src_conn,
215	data_flow::DataFlowNode& dst,
216	const std::string& dst_conn,
217	const data_flow::Subset& subset,
218	const DebugInfo& debug_info) {
UNCOV 219	auto& function_ = this->function();	×
220
221	// Check - Case 1: Access Node -> Access Node
222	// - src_conn or dst_conn must be refs. The other must be void.
223	// - The side of the memlet that is void, is dereferenced.
224	// - The dst type must always be a pointer after potential dereferencing.
225	// - The src type can be any type after dereferecing (&dereferenced_src_type).
UNCOV 226	if (dynamic_cast<data_flow::AccessNode>(&src) && dynamic_cast<data_flow::AccessNode>(&dst)) {	×
227	auto& src_node = dynamic_cast<data_flow::AccessNode&>(src);	×
228	auto& dst_node = dynamic_cast<data_flow::AccessNode&>(dst);	×
229	if (src_conn == "refs") {	×
230	if (dst_conn != "void") {	×
231	throw InvalidSDFGException("Invalid dst connector: " + dst_conn);	×
232	}
233
234	auto& dst_type = types::infer_type(function_, function_.type(dst_node.data()), subset);	×
235	if (!dynamic_cast<const types::Pointer*>(&dst_type)) {	×
236	throw InvalidSDFGException("dst type must be a pointer");	×
237	}
238
239	auto& src_type = function_.type(src_node.data());	×
240	if (!dynamic_cast<const types::Pointer*>(&src_type)) {	×
241	throw InvalidSDFGException("src type must be a pointer");	×
242	}
243	} else if (src_conn == "void") {	×
244	if (dst_conn != "refs") {	×
245	throw InvalidSDFGException("Invalid dst connector: " + dst_conn);	×
246	}
247
248	if (symbolic::is_pointer(symbolic::symbol(src_node.data()))) {	×
249	throw InvalidSDFGException("src_conn is void: src cannot be a raw pointer");	×
250	}
251
252	// Trivially correct but checks inference
253	auto& src_type = types::infer_type(function_, function_.type(src_node.data()), subset);	×
254	types::Pointer ref_type(src_type);	×
255	if (!dynamic_cast<const types::Pointer*>(&ref_type)) {
256	throw InvalidSDFGException("src type must be a pointer");
257	}
258
259	auto& dst_type = function_.type(dst_node.data());	×
260	if (!dynamic_cast<const types::Pointer*>(&dst_type)) {	×
261	throw InvalidSDFGException("dst type must be a pointer");	×
262	}
263	} else {	×
264	throw InvalidSDFGException("Invalid src connector: " + src_conn);	×
265	}
UNCOV 266	} else if (dynamic_cast<data_flow::AccessNode*>(&src) &&	×
UNCOV 267	dynamic_cast<data_flow::Tasklet*>(&dst)) {	×
UNCOV 268	auto& src_node = dynamic_cast<data_flow::AccessNode&>(src);	×
UNCOV 269	auto& dst_node = dynamic_cast<data_flow::Tasklet&>(dst);	×
UNCOV 270	if (src_conn != "void") {	×
271	throw InvalidSDFGException("src_conn must be void. Found: " + src_conn);	×
272	}
UNCOV 273	bool found = false;	×
UNCOV 274	for (auto& input : dst_node.inputs()) {	×
UNCOV 275	if (input.first == dst_conn) {	×
UNCOV 276	found = true;	×
UNCOV 277	break;	×
278	}
279	}
UNCOV 280	if (!found) {	×
281	throw InvalidSDFGException("dst_conn not found in tasklet: " + dst_conn);	×
282	}
UNCOV 283	auto& element_type = types::infer_type(function_, function_.type(src_node.data()), subset);	×
UNCOV 284	if (!dynamic_cast<const types::Scalar*>(&element_type)) {	×
285	throw InvalidSDFGException("Tasklets inputs must be scalars");	×
286	}
UNCOV 287	} else if (dynamic_cast<data_flow::Tasklet*>(&src) &&	×
UNCOV 288	dynamic_cast<data_flow::AccessNode*>(&dst)) {	×
UNCOV 289	auto& src_node = dynamic_cast<data_flow::Tasklet&>(src);	×
UNCOV 290	auto& dst_node = dynamic_cast<data_flow::AccessNode&>(dst);	×
UNCOV 291	if (src_conn != src_node.output().first) {	×
292	throw InvalidSDFGException("src_conn must match tasklet output name");	×
293	}
UNCOV 294	if (dst_conn != "void") {	×
295	throw InvalidSDFGException("dst_conn must be void. Found: " + dst_conn);	×
296	}
297
UNCOV 298	auto& element_type = types::infer_type(function_, function_.type(dst_node.data()), subset);	×
UNCOV 299	if (!dynamic_cast<const types::Scalar*>(&element_type)) {	×
300	throw InvalidSDFGException("Tasklet output must be a scalar");	×
301	}
UNCOV 302	} else if (dynamic_cast<data_flow::AccessNode*>(&src) &&	×
303	dynamic_cast<data_flow::LibraryNode*>(&dst)) {	×
304	auto& src_node = dynamic_cast<data_flow::AccessNode&>(src);	×
305	auto& dst_node = dynamic_cast<data_flow::LibraryNode&>(dst);	×
306	if (src_conn != "void") {	×
307	throw InvalidSDFGException("src_conn must be void. Found: " + src_conn);	×
308	}
309	bool found = false;	×
310	for (auto& input : dst_node.inputs()) {	×
311	if (input == dst_conn) {	×
312	found = true;	×
313	break;	×
314	}
315	}
316	if (!found) {	×
317	throw InvalidSDFGException("dst_conn not found in library node: " + dst_conn);	×
318	}
319
320	auto& element_type = types::infer_type(function_, function_.type(src_node.data()), subset);	×
321	if (!dynamic_cast<const types::Scalar*>(&element_type)) {	×
322	throw InvalidSDFGException("Library node inputs must be scalars");	×
323	}
324	} else if (dynamic_cast<data_flow::LibraryNode*>(&src) &&	×
325	dynamic_cast<data_flow::AccessNode*>(&dst)) {	×
326	auto& src_node = dynamic_cast<data_flow::LibraryNode&>(src);	×
327	auto& dst_node = dynamic_cast<data_flow::AccessNode&>(dst);	×
328	if (dst_conn != "void") {	×
329	throw InvalidSDFGException("dst_conn must be void. Found: " + dst_conn);	×
330	}
331	bool found = false;	×
332	for (auto& output : src_node.outputs()) {	×
333	if (output == src_conn) {	×
334	found = true;	×
335	break;	×
336	}
337	}
338	if (!found) {	×
339	throw InvalidSDFGException("src_conn not found in library node: " + src_conn);	×
340	}
341
342	auto& element_type = types::infer_type(function_, function_.type(dst_node.data()), subset);	×
343	if (!dynamic_cast<const types::Pointer*>(&element_type)) {	×
344	throw InvalidSDFGException("Access node must be a pointer");	×
345	}
346	} else {	×
347	throw InvalidSDFGException("Invalid src or dst node type");	×
348	}
349
UNCOV 350	auto& dataflow = state.dataflow();	×
UNCOV 351	auto edge = boost::add_edge(src.vertex_, dst.vertex_, dataflow.graph_);	×
UNCOV 352	auto res = dataflow.edges_.insert(	×
UNCOV 353	{edge.first, std::unique_ptr<data_flow::Memlet>(new data_flow::Memlet(	×
UNCOV 354	debug_info, edge.first, dataflow, src, src_conn, dst, dst_conn, subset))});	×
355
UNCOV 356	return dynamic_cast<data_flow::Memlet&>(*(res.first->second));	×
357	};	×
358
359	} // namespace builder
360	} // 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