17404796220

Committed 02 Sep 2025 01:18PM UTC coverage: 59.036% (-0.04%) from 59.078%

Build # 17404796220

Build Type

Pull #218

github

Committed by

web-flow

Commit Message

Merge fd4010d6a into 3395851ae

Pull Request Pull Request #218: adds new utility functions to builder API

Run Details

8 of 11 new or added lines in 2 files covered. (72.73%)

8 existing lines in 1 file now uncovered.

9215 of 15609 relevant lines covered (59.04%)

116.23 hits per line

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

36.05

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

daisytuner / sdfglib / 17404796220

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