15919699107

Committed 27 Jun 2025 06:25AM UTC coverage: 65.002% (-0.1%) from 65.102%

Build # 15919699107

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #113 from daisytuner/block-fusion

Extends block fusion

Run Details

30 of 48 new or added lines in 2 files covered. (62.5%)

8 existing lines in 1 file now uncovered.

8540 of 13138 relevant lines covered (65.0%)

144.76 hits per line

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

31.01

/src/data_flow/data_flow_graph.cpp

#include "sdfg/data_flow/data_flow_graph.h"

namespace sdfg {
namespace data_flow {

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

daisytuner / sdfglib / 15919699107

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