17656823807

Committed 11 Sep 2025 08:42PM UTC coverage: 60.447% (+1.1%) from 59.335%

Build # 17656823807

Build Type

Pull #219

github

Committed by

web-flow

Commit Message

Merge d5416236f into 6c1992b40

Pull Request Pull Request #219: stdlib Library Nodes and ConstantNodes

Run Details

460 of 1635 new or added lines in 81 files covered. (28.13%)

93 existing lines in 35 files now uncovered.

9385 of 15526 relevant lines covered (60.45%)

107.21 hits per line

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

37.64

/src/data_flow/data_flow_graph.cpp

#include "sdfg/data_flow/data_flow_graph.h"

namespace sdfg {
namespace data_flow {

void DataFlowGraph::validate(const Function& function) const {
    for (auto& node : this->nodes_) {
        node.second->validate(function);

        if (auto code_node = dynamic_cast<const data_flow::CodeNode*>(node.second.get())) {
            if (this->in_degree(*code_node) != code_node->inputs().size()) {
                throw InvalidSDFGException("DataFlowGraph: Number of input edges does not match number of inputs.");
            }
            if (this->out_degree(*code_node) != code_node->outputs().size()) {
                throw InvalidSDFGException("DataFlowGraph: Number of output edges does not match number of outputs.");
            }
        }
    }
    for (auto& edge : this->edges_) {
        edge.second->validate(function);
    }
};

const Element* DataFlowGraph::get_parent() const { return this->parent_; };

Element* DataFlowGraph::get_parent() { return this->parent_; };

size_t DataFlowGraph::in_degree(const data_flow::DataFlowNode& node) const {
    return boost::in_degree(node.vertex(), this->graph_);
};

size_t DataFlowGraph::out_degree(const data_flow::DataFlowNode& node) const {
    return boost::out_degree(node.vertex(), this->graph_);
};

void DataFlowGraph::replace(const symbolic::Expression& old_expression, const symbolic::Expression& new_expression) {
    for (auto& node : this->nodes_) {
        node.second->replace(old_expression, new_expression);
    }

    for (auto& edge : this->edges_) {
        edge.second->replace(old_expression, new_expression);
    }
};

/***** Section: Analysis *****/

std::unordered_set<const data_flow::Tasklet*> DataFlowGraph::tasklets() const {
    std::unordered_set<const data_flow::Tasklet*> ts;
    for (auto& node : this->nodes_) {
        if (auto tasklet = dynamic_cast<const data_flow::Tasklet*>(node.second.get())) {
            ts.insert(tasklet);
        }
    }

    return ts;
};

std::unordered_set<data_flow::Tasklet*> DataFlowGraph::tasklets() {
    std::unordered_set<data_flow::Tasklet*> ts;
    for (auto& node : this->nodes_) {
        if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(node.second.get())) {
            ts.insert(tasklet);
        }
    }

    return ts;
};

std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::data_nodes() const {
    std::unordered_set<const data_flow::AccessNode*> dnodes;
    for (auto& node : this->nodes_) {
        if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {
            dnodes.insert(access_node);
        }
    }

    return dnodes;
};

std::unordered_set<data_flow::AccessNode*> DataFlowGraph::data_nodes() {
    std::unordered_set<data_flow::AccessNode*> dnodes;
    for (auto& node : this->nodes_) {
        if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node.second.get())) {
            dnodes.insert(access_node);
        }
    }

    return dnodes;
};

std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::reads() const {
    std::unordered_set<const data_flow::AccessNode*> rs;
    for (auto& node : this->nodes_) {
        if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {
            if (this->out_degree(*access_node) > 0) {
                rs.insert(access_node);
            }
        }
    }

    return rs;
};

std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::writes() const {
    std::unordered_set<const data_flow::AccessNode*> ws;
    for (auto& node : this->nodes_) {
        if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {
            if (this->in_degree(*access_node) > 0) {
                ws.insert(access_node);
            }
        }
    }

    return ws;
};

std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::sources() const {
    std::unordered_set<const data_flow::DataFlowNode*> ss;
    for (auto& node : this->nodes_) {
        if (this->in_degree(*node.second) == 0) {
            ss.insert(node.second.get());
        }
    }

    return ss;
};

std::unordered_set<data_flow::DataFlowNode*> DataFlowGraph::sources() {
    std::unordered_set<data_flow::DataFlowNode*> ss;
    for (auto& node : this->nodes_) {
        if (this->in_degree(*node.second) == 0) {
            ss.insert(node.second.get());
        }
    }

    return ss;
};

std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::sinks() const {
    std::unordered_set<const data_flow::DataFlowNode*> ss;
    for (auto& node : this->nodes_) {
        if (this->out_degree(*node.second) == 0) {
            ss.insert(node.second.get());
        }
    }

    return ss;
};

std::unordered_set<data_flow::DataFlowNode*> DataFlowGraph::sinks() {
    std::unordered_set<data_flow::DataFlowNode*> ss;
    for (auto& node : this->nodes_) {
        if (this->out_degree(*node.second) == 0) {
            ss.insert(node.second.get());
        }
    }

    return ss;
};

std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::predecessors(const data_flow::DataFlowNode& node
) const {
    std::unordered_set<const data_flow::DataFlowNode*> ss;
    for (auto& edge : this->in_edges(node)) {
        ss.insert(&edge.src());
    }

    return ss;
};

std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::successors(const data_flow::DataFlowNode& node
) const {
    std::unordered_set<const data_flow::DataFlowNode*> ss;
    for (auto& edge : this->out_edges(node)) {
        ss.insert(&edge.dst());
    }

    return ss;
};

std::list<const data_flow::DataFlowNode*> DataFlowGraph::topological_sort() const {
    std::list<graph::Vertex> order = graph::topological_sort(this->graph_);

    std::list<const data_flow::DataFlowNode*> topo_nodes;
    for (auto& vertex : order) {
        topo_nodes.push_back(this->nodes_.at(vertex).get());
    }

    return topo_nodes;
};

std::list<data_flow::DataFlowNode*> DataFlowGraph::topological_sort() {
    std::list<graph::Vertex> order = graph::topological_sort(this->graph_);

    std::list<data_flow::DataFlowNode*> topo_nodes;
    for (auto& vertex : order) {
        topo_nodes.push_back(this->nodes_.at(vertex).get());
    }

    return topo_nodes;
};

std::unordered_map<std::string, const data_flow::AccessNode*> DataFlowGraph::dominators() const {
    std::unordered_map<std::string, const data_flow::AccessNode*> frontier;
    for (auto& node : this->topological_sort()) {
        if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node)) {
            if (frontier.find(access_node->data()) == frontier.end()) {
                frontier[access_node->data()] = access_node;
            }
        }
    }

    return frontier;
};

std::unordered_map<std::string, const data_flow::AccessNode*> DataFlowGraph::post_dominators() const {
    std::unordered_map<std::string, const data_flow::AccessNode*> frontier;
    for (auto& node : this->topological_sort()) {
        if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node)) {
            frontier[access_node->data()] = access_node;
        }
    }

    return frontier;
};

std::unordered_map<std::string, data_flow::AccessNode*> DataFlowGraph::post_dominators() {
    std::unordered_map<std::string, data_flow::AccessNode*> frontier;
    for (auto& node : this->topological_sort()) {
        if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node)) {
            frontier[access_node->data()] = access_node;
        }
    }

    return frontier;
};

auto DataFlowGraph::all_simple_paths(const data_flow::DataFlowNode& src, const data_flow::DataFlowNode& dst) const {
    std::list<std::list<graph::Edge>> all_paths_raw = graph::all_simple_paths(this->graph_, src.vertex(), dst.vertex());

    std::list<std::list<std::reference_wrapper<data_flow::Memlet>>> all_paths;
    for (auto& path_raw : all_paths_raw) {
        std::list<std::reference_wrapper<data_flow::Memlet>> path;
        for (auto& edge : path_raw) {
            path.push_back(*this->edges_.at(edge));
        }
        all_paths.push_back(path);
    }

    return all_paths;
};

const std::pair<size_t, const std::unordered_map<const data_flow::DataFlowNode*, size_t>> DataFlowGraph::
    weakly_connected_components() const {
    auto ccs_vertex = graph::weakly_connected_components(this->graph_);

    std::unordered_map<const data_flow::DataFlowNode*, size_t> ccs;
    for (auto& entry : ccs_vertex.second) {
        ccs[this->nodes_.at(entry.first).get()] = entry.second;
    }

    return {ccs_vertex.first, ccs};
};

} // namespace data_flow
} // namespace sdfg

1	#include "sdfg/data_flow/data_flow_graph.h"
2
3	namespace sdfg {
4	namespace data_flow {
5
6	void DataFlowGraph::validate(const Function& function) const {	471✔
7	for (auto& node : this->nodes_) {	1,104✔
8	node.second->validate(function);	633✔
9
10	if (auto code_node = dynamic_cast<const data_flow::CodeNode*>(node.second.get())) {	633✔
11	if (this->in_degree(*code_node) != code_node->inputs().size()) {	173✔
NEW 12	throw InvalidSDFGException("DataFlowGraph: Number of input edges does not match number of inputs.");	×
13	}
14	if (this->out_degree(*code_node) != code_node->outputs().size()) {	173✔
NEW 15	throw InvalidSDFGException("DataFlowGraph: Number of output edges does not match number of outputs.");	×
16	}
17	}	173✔
18	}
19	for (auto& edge : this->edges_) {	917✔
20	edge.second->validate(function);	446✔
21	}
22	};	471✔
23
24	const Element* DataFlowGraph::get_parent() const { return this->parent_; };	454✔
25
26	Element* DataFlowGraph::get_parent() { return this->parent_; };	298✔
27
28	size_t DataFlowGraph::in_degree(const data_flow::DataFlowNode& node) const {	1,121✔
29	return boost::in_degree(node.vertex(), this->graph_);	1,121✔
30	};
31
32	size_t DataFlowGraph::out_degree(const data_flow::DataFlowNode& node) const {	977✔
33	return boost::out_degree(node.vertex(), this->graph_);	977✔
34	};
35
36	void DataFlowGraph::replace(const symbolic::Expression& old_expression, const symbolic::Expression& new_expression) {	2✔
37	for (auto& node : this->nodes_) {	10✔
38	node.second->replace(old_expression, new_expression);	8✔
39	}
40
41	for (auto& edge : this->edges_) {	8✔
42	edge.second->replace(old_expression, new_expression);	6✔
43	}
44	};	2✔
45
46	/*** Section: Analysis ***/
47
48	std::unordered_set<const data_flow::Tasklet*> DataFlowGraph::tasklets() const {	×
49	std::unordered_set<const data_flow::Tasklet*> ts;	×
50	for (auto& node : this->nodes_) {	×
51	if (auto tasklet = dynamic_cast<const data_flow::Tasklet*>(node.second.get())) {	×
52	ts.insert(tasklet);	×
53	}	×
54	}
55
56	return ts;	×
57	};	×
58
59	std::unordered_set<data_flow::Tasklet*> DataFlowGraph::tasklets() {	29✔
60	std::unordered_set<data_flow::Tasklet*> ts;	29✔
61	for (auto& node : this->nodes_) {	145✔
62	if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(node.second.get())) {	116✔
63	ts.insert(tasklet);	31✔
64	}	31✔
65	}
66
67	return ts;	29✔
68	};	29✔
69
70	std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::data_nodes() const {	×
71	std::unordered_set<const data_flow::AccessNode*> dnodes;	×
72	for (auto& node : this->nodes_) {	×
73	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {	×
74	dnodes.insert(access_node);	×
75	}	×
76	}
77
78	return dnodes;	×
79	};	×
80
81	std::unordered_set<data_flow::AccessNode*> DataFlowGraph::data_nodes() {	3✔
82	std::unordered_set<data_flow::AccessNode*> dnodes;	3✔
83	for (auto& node : this->nodes_) {	18✔
84	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node.second.get())) {	15✔
85	dnodes.insert(access_node);	12✔
86	}	12✔
87	}
88
89	return dnodes;	3✔
90	};	3✔
91
92	std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::reads() const {	×
93	std::unordered_set<const data_flow::AccessNode*> rs;	×
94	for (auto& node : this->nodes_) {	×
95	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {	×
96	if (this->out_degree(*access_node) > 0) {	×
97	rs.insert(access_node);	×
98	}	×
99	}	×
100	}
101
102	return rs;	×
103	};	×
104
105	std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::writes() const {	×
106	std::unordered_set<const data_flow::AccessNode*> ws;	×
107	for (auto& node : this->nodes_) {	×
108	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {	×
109	if (this->in_degree(*access_node) > 0) {	×
110	ws.insert(access_node);	×
111	}	×
112	}	×
113	}
114
115	return ws;	×
116	};	×
117
118	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::sources() const {	×
119	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
120	for (auto& node : this->nodes_) {	×
121	if (this->in_degree(*node.second) == 0) {	×
122	ss.insert(node.second.get());	×
123	}	×
124	}
125
126	return ss;	×
127	};	×
128
129	std::unordered_set<data_flow::DataFlowNode*> DataFlowGraph::sources() {	×
130	std::unordered_set<data_flow::DataFlowNode*> ss;	×
131	for (auto& node : this->nodes_) {	×
132	if (this->in_degree(*node.second) == 0) {	×
133	ss.insert(node.second.get());	×
134	}	×
135	}
136
137	return ss;	×
138	};	×
139
140	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::sinks() const {	×
141	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
142	for (auto& node : this->nodes_) {	×
143	if (this->out_degree(*node.second) == 0) {	×
144	ss.insert(node.second.get());	×
145	}	×
146	}
147
148	return ss;	×
149	};	×
150
151	std::unordered_set<data_flow::DataFlowNode*> DataFlowGraph::sinks() {	×
152	std::unordered_set<data_flow::DataFlowNode*> ss;	×
153	for (auto& node : this->nodes_) {	×
154	if (this->out_degree(*node.second) == 0) {	×
155	ss.insert(node.second.get());	×
156	}	×
157	}
158
159	return ss;	×
160	};	×
161
162	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::predecessors(const data_flow::DataFlowNode& node	×
163	) const {
164	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
165	for (auto& edge : this->in_edges(node)) {	×
166	ss.insert(&edge.src());	×
167	}
168
169	return ss;	×
170	};	×
171
172	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::successors(const data_flow::DataFlowNode& node	×
173	) const {
174	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
175	for (auto& edge : this->out_edges(node)) {	×
176	ss.insert(&edge.dst());	×
177	}
178
179	return ss;	×
180	};	×
181
182	std::list<const data_flow::DataFlowNode*> DataFlowGraph::topological_sort() const {	192✔
183	std::list<graph::Vertex> order = graph::topological_sort(this->graph_);	192✔
184
185	std::list<const data_flow::DataFlowNode*> topo_nodes;	192✔
186	for (auto& vertex : order) {	618✔
187	topo_nodes.push_back(this->nodes_.at(vertex).get());	426✔
188	}
189
190	return topo_nodes;	192✔
191	};	192✔
192
193	std::list<data_flow::DataFlowNode*> DataFlowGraph::topological_sort() {	381✔
194	std::list<graph::Vertex> order = graph::topological_sort(this->graph_);	381✔
195
196	std::list<data_flow::DataFlowNode*> topo_nodes;	381✔
197	for (auto& vertex : order) {	1,032✔
198	topo_nodes.push_back(this->nodes_.at(vertex).get());	651✔
199	}
200
201	return topo_nodes;	381✔
202	};	381✔
203
204	std::unordered_map<std::string, const data_flow::AccessNode*> DataFlowGraph::dominators() const {	×
205	std::unordered_map<std::string, const data_flow::AccessNode*> frontier;	×
206	for (auto& node : this->topological_sort()) {	×
207	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node)) {	×
208	if (frontier.find(access_node->data()) == frontier.end()) {	×
209	frontier[access_node->data()] = access_node;	×
210	}	×
211	}	×
212	}
213
214	return frontier;	×
215	};	×
216
217	std::unordered_map<std::string, const data_flow::AccessNode*> DataFlowGraph::post_dominators() const {	×
218	std::unordered_map<std::string, const data_flow::AccessNode*> frontier;	×
219	for (auto& node : this->topological_sort()) {	×
220	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node)) {	×
221	frontier[access_node->data()] = access_node;	×
222	}	×
223	}
224
225	return frontier;	×
226	};	×
227
228	std::unordered_map<std::string, data_flow::AccessNode*> DataFlowGraph::post_dominators() {	6✔
229	std::unordered_map<std::string, data_flow::AccessNode*> frontier;	6✔
230	for (auto& node : this->topological_sort()) {	32✔
231	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node)) {	26✔
232	frontier[access_node->data()] = access_node;	20✔
233	}	20✔
234	}
235
236	return frontier;	6✔
237	};	6✔
238
239	auto DataFlowGraph::all_simple_paths(const data_flow::DataFlowNode& src, const data_flow::DataFlowNode& dst) const {	×
240	std::list<std::list<graph::Edge>> all_paths_raw = graph::all_simple_paths(this->graph_, src.vertex(), dst.vertex());	×
241
242	std::list<std::list<std::reference_wrapper<data_flow::Memlet>>> all_paths;	×
243	for (auto& path_raw : all_paths_raw) {	×
244	std::list<std::reference_wrapper<data_flow::Memlet>> path;	×
245	for (auto& edge : path_raw) {	×
246	path.push_back(*this->edges_.at(edge));	×
247	}
248	all_paths.push_back(path);	×
249	}	×
250
251	return all_paths;	×
252	};	×
253
254	const std::pair<size_t, const std::unordered_map<const data_flow::DataFlowNode*, size_t>> DataFlowGraph::
255	weakly_connected_components() const {	2✔
256	auto ccs_vertex = graph::weakly_connected_components(this->graph_);	2✔
257
258	std::unordered_map<const data_flow::DataFlowNode*, size_t> ccs;	2✔
259	for (auto& entry : ccs_vertex.second) {	17✔
260	ccs[this->nodes_.at(entry.first).get()] = entry.second;	15✔
261	}
262
263	return {ccs_vertex.first, ccs};	2✔
264	};	2✔
265
266	} // namespace data_flow
267	} // namespace sdfg

daisytuner / sdfglib / 17656823807

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