20770413849

Committed 06 Jan 2026 10:50PM UTC coverage: 62.168% (+21.4%) from 40.764%

Build # 20770413849

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #433 from daisytuner/clang-coverage

updates clang coverage flags

Run Details

14988 of 24109 relevant lines covered (62.17%)

88.57 hits per line

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

59.48

/src/data_flow/data_flow_graph.cpp

#include "sdfg/data_flow/data_flow_graph.h"
#include <algorithm>
#include <queue>

namespace sdfg {
namespace data_flow {

void DataFlowGraph::validate(const Function& function) const {
    for (auto& node : this->nodes_) {
        node.second->validate(function);
        if (&node.second->get_parent() != this) {
            throw InvalidSDFGException("DataFlowGraph: Node parent mismatch.");
        }

        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::LibraryNode*> DataFlowGraph::library_nodes() const {
    std::unordered_set<const data_flow::LibraryNode*> ls;
    for (auto& node : this->nodes_) {
        if (auto lib_node = dynamic_cast<const data_flow::LibraryNode*>(node.second.get())) {
            ls.insert(lib_node);
        }
    }

    return ls;
};

std::unordered_set<data_flow::LibraryNode*> DataFlowGraph::library_nodes() {
    std::unordered_set<data_flow::LibraryNode*> ls;
    for (auto& node : this->nodes_) {
        if (auto lib_node = dynamic_cast<data_flow::LibraryNode*>(node.second.get())) {
            ls.insert(lib_node);
        }
    }

    return ls;
};

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};
};

// Helper function to get primary outgoing edge for a node with multiple outputs
const data_flow::Memlet* get_primary_outgoing_edge(const DataFlowGraph& graph, const data_flow::DataFlowNode* node) {
    if (const auto* code_node = dynamic_cast<const data_flow::CodeNode*>(node)) {
        // For CodeNodes: first output is primary
        if (code_node->outputs().empty()) {
            return nullptr;
        }

        for (const auto& oedge : graph.out_edges(*code_node)) {
            if (oedge.src_conn() == code_node->output(0)) {
                return &oedge;
            }
        }
        return nullptr;
    } else {
        // For other nodes: highest priority edge (by tasklet code or lib name)
        std::vector<std::pair<const data_flow::Memlet*, size_t>> edges_list;
        for (const auto& oedge : graph.out_edges(*node)) {
            const auto* dst = &oedge.dst();
            size_t value = 0;
            if (const auto* tasklet = dynamic_cast<const data_flow::Tasklet*>(dst)) {
                value = tasklet->code();
            } else if (const auto* libnode = dynamic_cast<const data_flow::LibraryNode*>(dst)) {
                value = 52;
                for (char c : libnode->code().value()) {
                    value += c;
                }
            }
            edges_list.push_back({&oedge, value});
        }

        if (!edges_list.empty()) {
            std::sort(edges_list.begin(), edges_list.end(), [](const auto& a, const auto& b) {
                return a.second > b.second || (a.second == b.second && a.first->element_id() < b.first->element_id());
            });
            return edges_list.front().first;
        }
    }
    return nullptr;
}

std::list<const data_flow::DataFlowNode*> DataFlowGraph::topological_sort_deterministic() const {
    auto [num_components, components_map] = graph::weakly_connected_components(this->graph_);

    // Build deterministic topological sort for each weakly connected component
    std::vector<std::list<const DataFlowNode*>> components(num_components);

    for (size_t i = 0; i < num_components; i++) {
        // Get all nodes in this component
        std::vector<const DataFlowNode*> component_nodes;
        for (auto [v, comp] : components_map) {
            if (comp == i) {
                component_nodes.push_back(this->nodes_.at(v).get());
            }
        }

        if (component_nodes.empty()) {
            continue;
        }

        // Check for cycles: if no sinks exist, it's a cycle
        bool has_sink = false;
        for (const auto* node : component_nodes) {
            if (boost::out_degree(node->vertex(), this->graph_) == 0) {
                has_sink = true;
                break;
            }
        }
        if (!has_sink) {
            throw boost::not_a_dag();
        }

        // New algorithm: Hybrid Kahn's with priority-based processing

        // Step 1: Initialize in-degree and primary_incoming_count
        std::unordered_map<const DataFlowNode*, size_t> in_degree;
        std::unordered_map<const DataFlowNode*, size_t> primary_incoming_count;

        for (const auto* node : component_nodes) {
            size_t count = 0;
            for (auto& edge : this->in_edges(*node)) {
                (void) edge; // Just count
                count++;
            }
            in_degree[node] = count;
            primary_incoming_count[node] = 0;
        }

        // Step 2: Mark primary edges
        for (const auto* node : component_nodes) {
            if (this->out_degree(*node) > 1) {
                const Memlet* primary_edge = get_primary_outgoing_edge(*this, node);
                if (primary_edge) {
                    primary_incoming_count[&primary_edge->dst()]++;
                }
            } else if (this->out_degree(*node) == 1) {
                auto edges = this->out_edges(*node);
                auto it = edges.begin();
                if (it != edges.end()) {
                    primary_incoming_count[&(*it).dst()]++;
                }
            }
        }

        // Step 3: Priority queue for node ordering
        // Use a struct to define priority
        struct NodePriority {
            const DataFlowNode* node;
            size_t primary_path_count;
            size_t element_id;

            bool operator<(const NodePriority& other) const {
                // Higher primary_path_count = higher priority (use > for max-heap behavior in std::priority_queue)
                if (primary_path_count != other.primary_path_count)
                    return primary_path_count < other.primary_path_count;
                // Lower element_id = higher priority
                return element_id > other.element_id;
            }
        };

        std::priority_queue<NodePriority> queue;

        // Add all nodes with in-degree 0 to the queue
        for (const auto* node : component_nodes) {
            if (in_degree[node] == 0) {
                queue.push({node, primary_incoming_count[node], node->element_id()});
            }
        }

        // Step 4: Process nodes
        while (!queue.empty()) {
            NodePriority current = queue.top();
            queue.pop();

            components.at(i).push_back(current.node);

            // Update successors
            for (auto& edge : this->out_edges(*current.node)) {
                const DataFlowNode* successor = &edge.dst();
                in_degree[successor]--;

                if (in_degree[successor] == 0) {
                    queue.push({successor, primary_incoming_count[successor], successor->element_id()});
                }
            }
        }
    }

    // Sort components
    std::sort(components.begin(), components.end(), [](const auto& a, const auto& b) {
        return a.size() > b.size() ||
               (a.size() == b.size() && a.size() > 0 && a.front()->element_id() < b.front()->element_id());
    });

    // Resulting data structure
    std::list<const DataFlowNode*> order;
    for (auto& component : components) {
        order.insert(order.end(), component.begin(), component.end());
    }

    return order;
};


} // namespace data_flow
} // namespace sdfg

1	#include "sdfg/data_flow/data_flow_graph.h"
2	#include <algorithm>
3	#include <queue>
4
5	namespace sdfg {
6	namespace data_flow {
7
8	void DataFlowGraph::validate(const Function& function) const {	844✔
9	for (auto& node : this->nodes_) {	1,198✔
10	node.second->validate(function);	1,198✔
11	if (&node.second->get_parent() != this) {	1,198✔
12	throw InvalidSDFGException("DataFlowGraph: Node parent mismatch.");	×
13	}	×
14
15	if (auto code_node = dynamic_cast<const data_flow::CodeNode*>(node.second.get())) {	1,198✔
16	if (this->in_degree(*code_node) != code_node->inputs().size()) {	312✔
17	throw InvalidSDFGException("DataFlowGraph: Number of input edges does not match number of inputs.");	×
18	}	×
19	if (this->out_degree(*code_node) != code_node->outputs().size()) {	312✔
20	throw InvalidSDFGException("DataFlowGraph: Number of output edges does not match number of outputs.");	×
21	}	×
22	}	312✔
23	}	1,198✔
24	for (auto& edge : this->edges_) {	844✔
25	edge.second->validate(function);	832✔
26	}	832✔
27	};	844✔
28
29	const Element* DataFlowGraph::get_parent() const { return this->parent_; };	839✔
30
31	Element* DataFlowGraph::get_parent() { return this->parent_; };	391✔
32
33	size_t DataFlowGraph::in_degree(const data_flow::DataFlowNode& node) const {	2,463✔
34	return boost::in_degree(node.vertex(), this->graph_);	2,463✔
35	};	2,463✔
36
37	size_t DataFlowGraph::out_degree(const data_flow::DataFlowNode& node) const {	2,474✔
38	return boost::out_degree(node.vertex(), this->graph_);	2,474✔
39	};	2,474✔
40
41	void DataFlowGraph::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {	4✔
42	for (auto& node : this->nodes_) {	8✔
43	node.second->replace(old_expression, new_expression);	8✔
44	}	8✔
45
46	for (auto& edge : this->edges_) {	6✔
47	edge.second->replace(old_expression, new_expression);	6✔
48	}	6✔
49	};	4✔
50
51	/*** Section: Analysis ***/
52
53	std::unordered_set<const data_flow::Tasklet*> DataFlowGraph::tasklets() const {	×
54	std::unordered_set<const data_flow::Tasklet*> ts;	×
55	for (auto& node : this->nodes_) {	×
56	if (auto tasklet = dynamic_cast<const data_flow::Tasklet*>(node.second.get())) {	×
57	ts.insert(tasklet);	×
58	}	×
59	}	×
60
61	return ts;	×
62	};	×
63
64	std::unordered_set<data_flow::Tasklet*> DataFlowGraph::tasklets() {	316✔
65	std::unordered_set<data_flow::Tasklet*> ts;	316✔
66	for (auto& node : this->nodes_) {	1,192✔
67	if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(node.second.get())) {	1,192✔
68	ts.insert(tasklet);	284✔
69	}	284✔
70	}	1,192✔
71
72	return ts;	316✔
73	};	316✔
74
75	std::unordered_set<const data_flow::LibraryNode*> DataFlowGraph::library_nodes() const {	×
76	std::unordered_set<const data_flow::LibraryNode*> ls;	×
77	for (auto& node : this->nodes_) {	×
78	if (auto lib_node = dynamic_cast<const data_flow::LibraryNode*>(node.second.get())) {	×
79	ls.insert(lib_node);	×
80	}	×
81	}	×
82
83	return ls;	×
84	};	×
85
86	std::unordered_set<data_flow::LibraryNode*> DataFlowGraph::library_nodes() {	324✔
87	std::unordered_set<data_flow::LibraryNode*> ls;	324✔
88	for (auto& node : this->nodes_) {	1,198✔
89	if (auto lib_node = dynamic_cast<data_flow::LibraryNode*>(node.second.get())) {	1,198✔
90	ls.insert(lib_node);	227✔
91	}	227✔
92	}	1,198✔
93
94	return ls;	324✔
95	};	324✔
96
97	std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::data_nodes() const {	×
98	std::unordered_set<const data_flow::AccessNode*> dnodes;	×
99	for (auto& node : this->nodes_) {	×
100	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {	×
101	dnodes.insert(access_node);	×
102	}	×
103	}	×
104
105	return dnodes;	×
106	};	×
107
108	std::unordered_set<data_flow::AccessNode*> DataFlowGraph::data_nodes() {	65✔
109	std::unordered_set<data_flow::AccessNode*> dnodes;	65✔
110	for (auto& node : this->nodes_) {	231✔
111	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node.second.get())) {	231✔
112	dnodes.insert(access_node);	160✔
113	}	160✔
114	}	231✔
115
116	return dnodes;	65✔
117	};	65✔
118
119	std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::reads() const {	×
120	std::unordered_set<const data_flow::AccessNode*> rs;	×
121	for (auto& node : this->nodes_) {	×
122	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {	×
123	if (this->out_degree(*access_node) > 0) {	×
124	rs.insert(access_node);	×
125	}	×
126	}	×
127	}	×
128
129	return rs;	×
130	};	×
131
132	std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::writes() const {	×
133	std::unordered_set<const data_flow::AccessNode*> ws;	×
134	for (auto& node : this->nodes_) {	×
135	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {	×
136	if (this->in_degree(*access_node) > 0) {	×
137	ws.insert(access_node);	×
138	}	×
139	}	×
140	}	×
141
142	return ws;	×
143	};	×
144
145	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::sources() const {	×
146	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
147	for (auto& node : this->nodes_) {	×
148	if (this->in_degree(*node.second) == 0) {	×
149	ss.insert(node.second.get());	×
150	}	×
151	}	×
152
153	return ss;	×
154	};	×
155
156	std::unordered_set<data_flow::DataFlowNode*> DataFlowGraph::sources() {	3✔
157	std::unordered_set<data_flow::DataFlowNode*> ss;	3✔
158	for (auto& node : this->nodes_) {	13✔
159	if (this->in_degree(*node.second) == 0) {	13✔
160	ss.insert(node.second.get());	7✔
161	}	7✔
162	}	13✔
163
164	return ss;	3✔
165	};	3✔
166
167	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::sinks() const {	×
168	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
169	for (auto& node : this->nodes_) {	×
170	if (this->out_degree(*node.second) == 0) {	×
171	ss.insert(node.second.get());	×
172	}	×
173	}	×
174
175	return ss;	×
176	};	×
177
178	std::unordered_set<data_flow::DataFlowNode*> DataFlowGraph::sinks() {	×
179	std::unordered_set<data_flow::DataFlowNode*> ss;	×
180	for (auto& node : this->nodes_) {	×
181	if (this->out_degree(*node.second) == 0) {	×
182	ss.insert(node.second.get());	×
183	}	×
184	}	×
185
186	return ss;	×
187	};	×
188
189	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::predecessors(const data_flow::DataFlowNode& node
190	) const {	×
191	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
192	for (auto& edge : this->in_edges(node)) {	×
193	ss.insert(&edge.src());	×
194	}	×
195
196	return ss;	×
197	};	×
198
199	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::successors(const data_flow::DataFlowNode& node
200	) const {	×
201	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
202	for (auto& edge : this->out_edges(node)) {	×
203	ss.insert(&edge.dst());	×
204	}	×
205
206	return ss;	×
207	};	×
208
209	std::list<const data_flow::DataFlowNode*> DataFlowGraph::topological_sort() const {	24✔
210	std::list<graph::Vertex> order = graph::topological_sort(this->graph_);	24✔
211
212	std::list<const data_flow::DataFlowNode*> topo_nodes;	24✔
213	for (auto& vertex : order) {	77✔
214	topo_nodes.push_back(this->nodes_.at(vertex).get());	77✔
215	}	77✔
216
217	return topo_nodes;	24✔
218	};	24✔
219
220	std::list<data_flow::DataFlowNode*> DataFlowGraph::topological_sort() {	620✔
221	std::list<graph::Vertex> order = graph::topological_sort(this->graph_);	620✔
222
223	std::list<data_flow::DataFlowNode*> topo_nodes;	620✔
224	for (auto& vertex : order) {	1,009✔
225	topo_nodes.push_back(this->nodes_.at(vertex).get());	1,009✔
226	}	1,009✔
227
228	return topo_nodes;	620✔
229	};	620✔
230
231	std::unordered_map<std::string, const data_flow::AccessNode*> DataFlowGraph::dominators() const {	×
232	std::unordered_map<std::string, const data_flow::AccessNode*> frontier;	×
233	for (auto& node : this->topological_sort()) {	×
234	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node)) {	×
235	if (frontier.find(access_node->data()) == frontier.end()) {	×
236	frontier[access_node->data()] = access_node;	×
237	}	×
238	}	×
239	}	×
240
241	return frontier;	×
242	};	×
243
244	std::unordered_map<std::string, const data_flow::AccessNode*> DataFlowGraph::post_dominators() const {	×
245	std::unordered_map<std::string, const data_flow::AccessNode*> frontier;	×
246	for (auto& node : this->topological_sort()) {	×
247	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node)) {	×
248	frontier[access_node->data()] = access_node;	×
249	}	×
250	}	×
251
252	return frontier;	×
253	};	×
254
255	std::unordered_map<std::string, data_flow::AccessNode*> DataFlowGraph::post_dominators() {	3✔
256	std::unordered_map<std::string, data_flow::AccessNode*> frontier;	3✔
257	for (auto& node : this->topological_sort()) {	13✔
258	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node)) {	13✔
259	frontier[access_node->data()] = access_node;	10✔
260	}	10✔
261	}	13✔
262
263	return frontier;	3✔
264	};	3✔
265
266	auto DataFlowGraph::all_simple_paths(const data_flow::DataFlowNode& src, const data_flow::DataFlowNode& dst) const {	×
267	std::list<std::list<graph::Edge>> all_paths_raw = graph::all_simple_paths(this->graph_, src.vertex(), dst.vertex());	×
268
269	std::list<std::list<std::reference_wrapper<data_flow::Memlet>>> all_paths;	×
270	for (auto& path_raw : all_paths_raw) {	×
271	std::list<std::reference_wrapper<data_flow::Memlet>> path;	×
272	for (auto& edge : path_raw) {	×
273	path.push_back(*this->edges_.at(edge));	×
274	}	×
275	all_paths.push_back(path);	×
276	}	×
277
278	return all_paths;	×
279	};	×
280
281	const std::pair<size_t, const std::unordered_map<const data_flow::DataFlowNode*, size_t>> DataFlowGraph::
282	weakly_connected_components() const {	8✔
283	auto ccs_vertex = graph::weakly_connected_components(this->graph_);	8✔
284
285	std::unordered_map<const data_flow::DataFlowNode*, size_t> ccs;	8✔
286	for (auto& entry : ccs_vertex.second) {	41✔
287	ccs[this->nodes_.at(entry.first).get()] = entry.second;	41✔
288	}	41✔
289
290	return {ccs_vertex.first, ccs};	8✔
291	};	8✔
292
293	// Helper function to get primary outgoing edge for a node with multiple outputs
294	const data_flow::Memlet* get_primary_outgoing_edge(const DataFlowGraph& graph, const data_flow::DataFlowNode* node) {	17✔
295	if (const auto* code_node = dynamic_cast<const data_flow::CodeNode*>(node)) {	17✔
296	// For CodeNodes: first output is primary
297	if (code_node->outputs().empty()) {	2✔
298	return nullptr;	×
299	}	×
300
301	for (const auto& oedge : graph.out_edges(*code_node)) {	2✔
302	if (oedge.src_conn() == code_node->output(0)) {	2✔
303	return &oedge;	2✔
304	}	2✔
305	}	2✔
306	return nullptr;	×
307	} else {	15✔
308	// For other nodes: highest priority edge (by tasklet code or lib name)
309	std::vector<std::pair<const data_flow::Memlet*, size_t>> edges_list;	15✔
310	for (const auto& oedge : graph.out_edges(*node)) {	33✔
311	const auto* dst = &oedge.dst();	33✔
312	size_t value = 0;	33✔
313	if (const auto* tasklet = dynamic_cast<const data_flow::Tasklet*>(dst)) {	33✔
314	value = tasklet->code();	33✔
315	} else if (const auto* libnode = dynamic_cast<const data_flow::LibraryNode*>(dst)) {	33✔
316	value = 52;	×
317	for (char c : libnode->code().value()) {	×
318	value += c;	×
319	}	×
320	}	×
321	edges_list.push_back({&oedge, value});	33✔
322	}	33✔
323
324	if (!edges_list.empty()) {	15✔
325	std::sort(edges_list.begin(), edges_list.end(), [](const auto& a, const auto& b) {	36✔
326	return a.second > b.second \|\| (a.second == b.second && a.first->element_id() < b.first->element_id());	36✔
327	});	36✔
328	return edges_list.front().first;	15✔
329	}	15✔
330	}	15✔
331	return nullptr;	×
332	}	17✔
333
334	std::list<const data_flow::DataFlowNode*> DataFlowGraph::topological_sort_deterministic() const {	24✔
335	auto [num_components, components_map] = graph::weakly_connected_components(this->graph_);	24✔
336
337	// Build deterministic topological sort for each weakly connected component
338	std::vector<std::list<const DataFlowNode*>> components(num_components);	24✔
339
340	for (size_t i = 0; i < num_components; i++) {	49✔
341	// Get all nodes in this component
342	std::vector<const DataFlowNode*> component_nodes;	25✔
343	for (auto [v, comp] : components_map) {	173✔
344	if (comp == i) {	173✔
345	component_nodes.push_back(this->nodes_.at(v).get());	151✔
346	}	151✔
347	}	173✔
348
349	if (component_nodes.empty()) {	25✔
350	continue;	×
351	}	×
352
353	// Check for cycles: if no sinks exist, it's a cycle
354	bool has_sink = false;	25✔
355	for (const auto* node : component_nodes) {	93✔
356	if (boost::out_degree(node->vertex(), this->graph_) == 0) {	93✔
357	has_sink = true;	25✔
358	break;	25✔
359	}	25✔
360	}	93✔
361	if (!has_sink) {	25✔
362	throw boost::not_a_dag();	×
363	}	×
364
365	// New algorithm: Hybrid Kahn's with priority-based processing
366
367	// Step 1: Initialize in-degree and primary_incoming_count
368	std::unordered_map<const DataFlowNode*, size_t> in_degree;	25✔
369	std::unordered_map<const DataFlowNode*, size_t> primary_incoming_count;	25✔
370
371	for (const auto* node : component_nodes) {	151✔
372	size_t count = 0;	151✔
373	for (auto& edge : this->in_edges(*node)) {	151✔
374	(void) edge; // Just count	139✔
375	count++;	139✔
376	}	139✔
377	in_degree[node] = count;	151✔
378	primary_incoming_count[node] = 0;	151✔
379	}	151✔
380
381	// Step 2: Mark primary edges
382	for (const auto* node : component_nodes) {	151✔
383	if (this->out_degree(*node) > 1) {	151✔
384	const Memlet* primary_edge = get_primary_outgoing_edge(*this, node);	17✔
385	if (primary_edge) {	17✔
386	primary_incoming_count[&primary_edge->dst()]++;	17✔
387	}	17✔
388	} else if (this->out_degree(*node) == 1) {	134✔
389	auto edges = this->out_edges(*node);	102✔
390	auto it = edges.begin();	102✔
391	if (it != edges.end()) {	102✔
392	primary_incoming_count[&(*it).dst()]++;	102✔
393	}	102✔
394	}	102✔
395	}	151✔
396
397	// Step 3: Priority queue for node ordering
398	// Use a struct to define priority
399	struct NodePriority {	25✔
400	const DataFlowNode* node;	25✔
401	size_t primary_path_count;	25✔
402	size_t element_id;	25✔
403
404	bool operator<(const NodePriority& other) const {	74✔
405	// Higher primary_path_count = higher priority (use > for max-heap behavior in std::priority_queue)
406	if (primary_path_count != other.primary_path_count)	74✔
407	return primary_path_count < other.primary_path_count;	45✔
408	// Lower element_id = higher priority
409	return element_id > other.element_id;	29✔
410	}	74✔
411	};	25✔
412
413	std::priority_queue<NodePriority> queue;	25✔
414
415	// Add all nodes with in-degree 0 to the queue
416	for (const auto* node : component_nodes) {	151✔
417	if (in_degree[node] == 0) {	151✔
418	queue.push({node, primary_incoming_count[node], node->element_id()});	33✔
419	}	33✔
420	}	151✔
421
422	// Step 4: Process nodes
423	while (!queue.empty()) {	176✔
424	NodePriority current = queue.top();	151✔
425	queue.pop();	151✔
426
427	components.at(i).push_back(current.node);	151✔
428
429	// Update successors
430	for (auto& edge : this->out_edges(*current.node)) {	151✔
431	const DataFlowNode* successor = &edge.dst();	139✔
432	in_degree[successor]--;	139✔
433
434	if (in_degree[successor] == 0) {	139✔
435	queue.push({successor, primary_incoming_count[successor], successor->element_id()});	118✔
436	}	118✔
437	}	139✔
438	}	151✔
439	}	25✔
440
441	// Sort components
442	std::sort(components.begin(), components.end(), [](const auto& a, const auto& b) {	24✔
443	return a.size() > b.size() \|\|	2✔
444	(a.size() == b.size() && a.size() > 0 && a.front()->element_id() < b.front()->element_id());	2✔
445	});	2✔
446
447	// Resulting data structure
448	std::list<const DataFlowNode*> order;	24✔
449	for (auto& component : components) {	25✔
450	order.insert(order.end(), component.begin(), component.end());	25✔
451	}	25✔
452
453	return order;	24✔
454	};	24✔
455
456
457	} // namespace data_flow
458	} // namespace sdfg

daisytuner / sdfglib / 20770413849

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