20540617027

Committed 27 Dec 2025 03:02PM UTC coverage: 39.518% (+0.4%) from 39.111%

Build # 20540617027

Build Type

Pull #407

github

Committed by

web-flow

Commit Message

Merge b064c4fd4 into 4e1d3209f

Pull Request Pull Request #407: Multi-Edges in Topological Sort

Run Details

13690 of 44966 branches covered (30.45%)

Branch coverage included in aggregate %.

55 of 69 new or added lines in 2 files covered. (79.71%)

61 existing lines in 2 files now uncovered.

11793 of 19518 relevant lines covered (60.42%)

84.39 hits per line

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

42.99

/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 (&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};
};

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 sinks of the current component
        std::vector<const DataFlowNode*> sinks;
        bool component_empty = true;
        for (auto [v, comp] : components_map) {
            if (comp == i) {
                component_empty = false;
                if (boost::out_degree(v, this->graph_) == 0) {
                    sinks.push_back(this->nodes_.at(v).get());
                }
            }
        }
        if (sinks.size() == 0) {
            if (component_empty) {
                continue;
            } else {
                throw boost::not_a_dag();
            }
        }

        // Go over all sinks
        const DataFlowNode* primary_sink = nullptr;
        std::unordered_map<const DataFlowNode*, std::list<const DataFlowNode*>> lists;
        std::unordered_map<const DataFlowNode*, std::list<const Memlet*>> memlet_queues;
        std::unordered_map<const Memlet*, const DataFlowNode*> memlet_map;
        for (const auto* sink : sinks) {
            lists.insert({sink, {}});
            memlet_queues.insert({sink, {}});
            std::unordered_set<const DataFlowNode*> primary_blocker;

            // Perform reversed DFS starting form sink node
            std::unordered_set<const DataFlowNode*> visited;
            std::stack<std::pair<const DataFlowNode*, const DataFlowNode*>> stack({{sink, nullptr}});
            while (!stack.empty()) {
                const auto [current, successor] = stack.top();
                stack.pop();

                // Special case: Only handle primary edges
                if (this->out_degree(*current) > 1) {
                    if (const auto* code_node = dynamic_cast<const CodeNode*>(current)) {
                        std::unordered_map<std::string, const Memlet*> edges_map;
                        const Memlet* memlet = nullptr; // Memlet from current to successor
                        for (const auto& oedge : this->out_edges(*code_node)) {
                            edges_map.insert({oedge.src_conn(), &oedge});
                            if (&oedge.dst() == successor) {
                                memlet = &oedge;
                            }
                        }
                        const auto* primary_dst = &edges_map.at(code_node->output(0))->dst();
                        if (primary_dst == successor) {
                            for (size_t j = 1; j < code_node->outputs().size(); j++) {
                                const auto* edge = edges_map.at(code_node->output(j));
                                if (&edge->dst() != successor) {
                                    memlet_queues.at(sink).push_back(edge);
                                }
                            }
                        } else {
                            if (primary_blocker.empty()) {
                                memlet_map.insert({memlet, sink});
                            } else {
                                memlet_map.insert({memlet, nullptr});
                            }
                            primary_blocker.insert(current);
                            continue;
                        }
                    } else {
                        std::vector<std::pair<const Memlet*, size_t>> edges_list;
                        const Memlet* memlet = nullptr; // Memlet from current to successor
                        for (const auto& oedge : this->out_edges(*current)) {
                            const auto* dst = &oedge.dst();
                            size_t value = 0;
                            if (const auto* tasklet = dynamic_cast<const Tasklet*>(dst)) {
                                value = tasklet->code();
                            } else if (const auto* libnode = dynamic_cast<const LibraryNode*>(dst)) {
                                value = 52;
                                for (char c : libnode->code().value()) {
                                    value += c;
                                }
                            }
                            edges_list.push_back({&oedge, value});
                            if (&oedge.dst() == successor) {
                                memlet = &oedge;
                            }
                        }
                        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());
                        });
                        const auto* primary_dst = &edges_list.front().first->dst();
                        if (primary_dst == successor) {
                            for (size_t j = 1; j < edges_list.size(); j++) {
                                const auto* edge = edges_list.at(j).first;
                                if (&edge->dst() != successor) {
                                    memlet_queues.at(sink).push_back(edge);
                                }
                            }
                        } else {
                            if (primary_blocker.empty()) {
                                memlet_map.insert({memlet, sink});
                            } else {
                                memlet_map.insert({memlet, nullptr});
                            }
                            primary_blocker.insert(current);
                            continue;
                        }
                    }
                }

                // Put the current element in the list
                if (visited.contains(current)) {
                    throw boost::not_a_dag();
                }
                visited.insert(current);
                if (primary_blocker.contains(current)) {
                    primary_blocker.erase(current);
                }
                lists.at(sink).push_front(current);

                // Put all predecessors on the stack
                if (const auto* code_node = dynamic_cast<const CodeNode*>(current)) {
                    std::unordered_set<const DataFlowNode*> pushed_predecessors;
                    for (const auto& input : code_node->inputs()) {
                        const Memlet* iedge = nullptr;
                        for (auto& in_edge : this->in_edges(*code_node)) {
                            if (in_edge.dst_conn() == input) {
                                iedge = &in_edge;
                                break;
                            }
                        }
                        if (!iedge) {
                            continue;
                        }
                        const auto* src = &iedge->src();
                        if (pushed_predecessors.contains(src)) {
                            continue;
                        }
                        stack.push({src, current});
                        pushed_predecessors.insert(src);
                    }
                } else {
                    std::vector<std::pair<const DataFlowNode*, size_t>> tmp_inputs;
                    for (const auto& iedge : this->in_edges(*current)) {
                        const auto* src = &iedge.src();
                        size_t value = 0;
                        if (const auto* tasklet = dynamic_cast<const Tasklet*>(src)) {
                            value = tasklet->code();
                        } else if (const auto* libnode = dynamic_cast<const LibraryNode*>(src)) {
                            value = 52;
                            for (char c : libnode->code().value()) {
                                value += c;
                            }
                        }
                        tmp_inputs.push_back({src, value});
                    }
                    std::sort(tmp_inputs.begin(), tmp_inputs.end(), [](const auto& a, const auto& b) {
                        return a.second > b.second ||
                               (a.second == b.second && a.first->element_id() < b.first->element_id());
                    });
                    std::unordered_set<const DataFlowNode*> pushed_predecessors;
                    for (const auto& tmp_input : tmp_inputs) {
                        if (pushed_predecessors.contains(tmp_input.first)) {
                            continue;
                        }
                        stack.push({tmp_input.first, current});
                        pushed_predecessors.insert(tmp_input.first);
                    }
                }
            }

            // Store primary sink
            if (primary_blocker.empty()) {
                primary_sink = sink;
            }
        }
        if (!primary_sink) {
            throw boost::not_a_dag();
        }

        std::list<const DataFlowNode*> queue = {primary_sink};
        std::unordered_set<const DataFlowNode*> visited;
        while (!queue.empty()) {
            const auto* current = queue.front();
            queue.pop_front();
            if (visited.contains(current)) {
                continue;
            }

            // Fill global list
            components.at(i).insert(components.at(i).end(), lists.at(current).begin(), lists.at(current).end());
            visited.insert(current);

            // Fill queue
            for (const auto* memlet : memlet_queues.at(current)) {
                const auto* node = memlet_map.at(memlet);
                if (node) {
                    queue.push_back(node);
                }
            }
        }
    }

    // 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
3	namespace sdfg {
4	namespace data_flow {
5
6	void DataFlowGraph::validate(const Function& function) const {	620✔
7	for (auto& node : this->nodes_) {	1,694✔
8	node.second->validate(function);	1,074✔
9	if (&node.second->get_parent() != this) {	1,074!
NEW 10	throw InvalidSDFGException("DataFlowGraph: Node parent mismatch.");	×
11	}
12
13	if (auto code_node = dynamic_cast<const data_flow::CodeNode*>(node.second.get())) {	1,074!
14	if (this->in_degree(*code_node) != code_node->inputs().size()) {	283!
15	throw InvalidSDFGException("DataFlowGraph: Number of input edges does not match number of inputs.");	×
16	}
17	if (this->out_degree(*code_node) != code_node->outputs().size()) {	283!
UNCOV 18	throw InvalidSDFGException("DataFlowGraph: Number of output edges does not match number of outputs.");	×
19	}
20	}	283✔
21	}
22	for (auto& edge : this->edges_) {	1,366✔
23	edge.second->validate(function);	746✔
24	}
25	};	620✔
26
27	const Element* DataFlowGraph::get_parent() const { return this->parent_; };	620✔
28
29	Element* DataFlowGraph::get_parent() { return this->parent_; };	279✔
30
31	size_t DataFlowGraph::in_degree(const data_flow::DataFlowNode& node) const {	1,929✔
32	return boost::in_degree(node.vertex(), this->graph_);	1,929✔
33	};
34
35	size_t DataFlowGraph::out_degree(const data_flow::DataFlowNode& node) const {	1,749✔
36	return boost::out_degree(node.vertex(), this->graph_);	1,749✔
37	};
38
39	void DataFlowGraph::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {	2✔
40	for (auto& node : this->nodes_) {	10✔
41	node.second->replace(old_expression, new_expression);	8!
42	}
43
44	for (auto& edge : this->edges_) {	8✔
45	edge.second->replace(old_expression, new_expression);	6!
46	}
47	};	2✔
48
49	/*** Section: Analysis ***/
50
UNCOV 51	std::unordered_set<const data_flow::Tasklet*> DataFlowGraph::tasklets() const {	×
UNCOV 52	std::unordered_set<const data_flow::Tasklet*> ts;	×
UNCOV 53	for (auto& node : this->nodes_) {	×
UNCOV 54	if (auto tasklet = dynamic_cast<const data_flow::Tasklet*>(node.second.get())) {	×
UNCOV 55	ts.insert(tasklet);	×
56	}	×
57	}
58
59	return ts;	×
60	};	×
61
62	std::unordered_set<data_flow::Tasklet*> DataFlowGraph::tasklets() {	76✔
63	std::unordered_set<data_flow::Tasklet*> ts;	76✔
64	for (auto& node : this->nodes_) {	346✔
65	if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(node.second.get())) {	270!
66	ts.insert(tasklet);	60!
67	}	60✔
68	}
69
70	return ts;	76✔
71	};	76!
72
UNCOV 73	std::unordered_set<const data_flow::LibraryNode*> DataFlowGraph::library_nodes() const {	×
UNCOV 74	std::unordered_set<const data_flow::LibraryNode*> ls;	×
UNCOV 75	for (auto& node : this->nodes_) {	×
UNCOV 76	if (auto lib_node = dynamic_cast<const data_flow::LibraryNode*>(node.second.get())) {	×
UNCOV 77	ls.insert(lib_node);	×
78	}	×
79	}
80
81	return ls;	×
82	};	×
83
84	std::unordered_set<data_flow::LibraryNode*> DataFlowGraph::library_nodes() {	153✔
85	std::unordered_set<data_flow::LibraryNode*> ls;	153✔
86	for (auto& node : this->nodes_) {	608✔
87	if (auto lib_node = dynamic_cast<data_flow::LibraryNode*>(node.second.get())) {	455!
88	ls.insert(lib_node);	88!
89	}	88✔
90	}
91
92	return ls;	153✔
93	};	153!
94
UNCOV 95	std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::data_nodes() const {	×
UNCOV 96	std::unordered_set<const data_flow::AccessNode*> dnodes;	×
UNCOV 97	for (auto& node : this->nodes_) {	×
UNCOV 98	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {	×
UNCOV 99	dnodes.insert(access_node);	×
100	}	×
101	}
102
103	return dnodes;	×
104	};	×
105
106	std::unordered_set<data_flow::AccessNode*> DataFlowGraph::data_nodes() {	65✔
107	std::unordered_set<data_flow::AccessNode*> dnodes;	65✔
108	for (auto& node : this->nodes_) {	296✔
109	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node.second.get())) {	231!
110	dnodes.insert(access_node);	160!
111	}	160✔
112	}
113
114	return dnodes;	65✔
115	};	65!
116
UNCOV 117	std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::reads() const {	×
UNCOV 118	std::unordered_set<const data_flow::AccessNode*> rs;	×
UNCOV 119	for (auto& node : this->nodes_) {	×
UNCOV 120	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {	×
UNCOV 121	if (this->out_degree(*access_node) > 0) {	×
122	rs.insert(access_node);	×
123	}	×
124	}	×
125	}
126
127	return rs;	×
128	};	×
129
UNCOV 130	std::unordered_set<const data_flow::AccessNode*> DataFlowGraph::writes() const {	×
UNCOV 131	std::unordered_set<const data_flow::AccessNode*> ws;	×
132	for (auto& node : this->nodes_) {	×
133	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node.second.get())) {	×
UNCOV 134	if (this->in_degree(*access_node) > 0) {	×
135	ws.insert(access_node);	×
136	}	×
137	}	×
138	}
139
140	return ws;	×
141	};	×
142
UNCOV 143	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::sources() const {	×
UNCOV 144	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
145	for (auto& node : this->nodes_) {	×
146	if (this->in_degree(*node.second) == 0) {	×
UNCOV 147	ss.insert(node.second.get());	×
148	}	×
149	}
150
151	return ss;	×
152	};	×
153
154	std::unordered_set<data_flow::DataFlowNode*> DataFlowGraph::sources() {	3✔
155	std::unordered_set<data_flow::DataFlowNode*> ss;	3✔
156	for (auto& node : this->nodes_) {	16✔
157	if (this->in_degree(*node.second) == 0) {	13!
158	ss.insert(node.second.get());	7!
159	}	7✔
160	}
161
162	return ss;	3✔
163	};	3!
164
UNCOV 165	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::sinks() const {	×
UNCOV 166	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
UNCOV 167	for (auto& node : this->nodes_) {	×
UNCOV 168	if (this->out_degree(*node.second) == 0) {	×
UNCOV 169	ss.insert(node.second.get());	×
170	}	×
171	}
172
173	return ss;	×
174	};	×
175
UNCOV 176	std::unordered_set<data_flow::DataFlowNode*> DataFlowGraph::sinks() {	×
UNCOV 177	std::unordered_set<data_flow::DataFlowNode*> ss;	×
178	for (auto& node : this->nodes_) {	×
179	if (this->out_degree(*node.second) == 0) {	×
UNCOV 180	ss.insert(node.second.get());	×
181	}	×
182	}
183
184	return ss;	×
185	};	×
186
UNCOV 187	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::predecessors(const data_flow::DataFlowNode& node	×
188	) const {
189	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
190	for (auto& edge : this->in_edges(node)) {	×
UNCOV 191	ss.insert(&edge.src());	×
192	}
193
194	return ss;	×
195	};	×
196
UNCOV 197	std::unordered_set<const data_flow::DataFlowNode*> DataFlowGraph::successors(const data_flow::DataFlowNode& node	×
198	) const {
199	std::unordered_set<const data_flow::DataFlowNode*> ss;	×
200	for (auto& edge : this->out_edges(node)) {	×
UNCOV 201	ss.insert(&edge.dst());	×
202	}
203
204	return ss;	×
205	};	×
206
207	std::list<const data_flow::DataFlowNode*> DataFlowGraph::topological_sort() const {	34✔
208	std::list<graph::Vertex> order = graph::topological_sort(this->graph_);	34✔
209
210	std::list<const data_flow::DataFlowNode*> topo_nodes;	34✔
211	for (auto& vertex : order) {	136✔
212	topo_nodes.push_back(this->nodes_.at(vertex).get());	102!
213	}
214
215	return topo_nodes;	34✔
216	};	34!
217
218	std::list<data_flow::DataFlowNode*> DataFlowGraph::topological_sort() {	519✔
219	std::list<graph::Vertex> order = graph::topological_sort(this->graph_);	519✔
220
221	std::list<data_flow::DataFlowNode*> topo_nodes;	519✔
222	for (auto& vertex : order) {	1,508✔
223	topo_nodes.push_back(this->nodes_.at(vertex).get());	989!
224	}
225
226	return topo_nodes;	519✔
227	};	519!
228
UNCOV 229	std::unordered_map<std::string, const data_flow::AccessNode*> DataFlowGraph::dominators() const {	×
UNCOV 230	std::unordered_map<std::string, const data_flow::AccessNode*> frontier;	×
UNCOV 231	for (auto& node : this->topological_sort()) {	×
UNCOV 232	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node)) {	×
UNCOV 233	if (frontier.find(access_node->data()) == frontier.end()) {	×
234	frontier[access_node->data()] = access_node;	×
235	}	×
236	}	×
237	}
238
239	return frontier;	×
240	};	×
241
UNCOV 242	std::unordered_map<std::string, const data_flow::AccessNode*> DataFlowGraph::post_dominators() const {	×
UNCOV 243	std::unordered_map<std::string, const data_flow::AccessNode*> frontier;	×
244	for (auto& node : this->topological_sort()) {	×
245	if (auto access_node = dynamic_cast<const data_flow::AccessNode*>(node)) {	×
UNCOV 246	frontier[access_node->data()] = access_node;	×
247	}	×
248	}
249
250	return frontier;	×
251	};	×
252
253	std::unordered_map<std::string, data_flow::AccessNode*> DataFlowGraph::post_dominators() {	3✔
254	std::unordered_map<std::string, data_flow::AccessNode*> frontier;	3✔
255	for (auto& node : this->topological_sort()) {	16!
256	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node)) {	13!
257	frontier[access_node->data()] = access_node;	10!
258	}	10✔
259	}
260
261	return frontier;	3✔
262	};	3!
263
UNCOV 264	auto DataFlowGraph::all_simple_paths(const data_flow::DataFlowNode& src, const data_flow::DataFlowNode& dst) const {	×
UNCOV 265	std::list<std::list<graph::Edge>> all_paths_raw = graph::all_simple_paths(this->graph_, src.vertex(), dst.vertex());	×
266
UNCOV 267	std::list<std::list<std::reference_wrapper<data_flow::Memlet>>> all_paths;	×
UNCOV 268	for (auto& path_raw : all_paths_raw) {	×
269	std::list<std::reference_wrapper<data_flow::Memlet>> path;	×
270	for (auto& edge : path_raw) {	×
UNCOV 271	path.push_back(*this->edges_.at(edge));	×
272	}
273	all_paths.push_back(path);	×
274	}	×
275
276	return all_paths;	×
UNCOV 277	};	×
278
279	const std::pair<size_t, const std::unordered_map<const data_flow::DataFlowNode*, size_t>> DataFlowGraph::
280	weakly_connected_components() const {	8✔
281	auto ccs_vertex = graph::weakly_connected_components(this->graph_);	8✔
282
283	std::unordered_map<const data_flow::DataFlowNode*, size_t> ccs;	8✔
284	for (auto& entry : ccs_vertex.second) {	49✔
285	ccs[this->nodes_.at(entry.first).get()] = entry.second;	41!
286	}
287
288	return {ccs_vertex.first, ccs};	8!
289	};	8✔
290
291	std::list<const data_flow::DataFlowNode*> DataFlowGraph::topological_sort_deterministic() const {	3✔
292	auto [num_components, components_map] = graph::weakly_connected_components(this->graph_);	10✔
293
294	// Build deterministic topological sort for each weakly connected component
295	std::vector<std::list<const DataFlowNode*>> components(num_components);	3!
296	for (size_t i = 0; i < num_components; i++) {	7✔
297	// Get all sinks of the current component
298	std::vector<const DataFlowNode*> sinks;	4✔
299	bool component_empty = true;	4✔
300	for (auto [v, comp] : components_map) {	63✔
301	if (comp == i) {	54✔
302	component_empty = false;	32✔
303	if (boost::out_degree(v, this->graph_) == 0) {	32!
304	sinks.push_back(this->nodes_.at(v).get());	10!
305	}	5✔
306	}	32✔
307	}
308	if (sinks.size() == 0) {	4!
309	if (component_empty) {	×
310	continue;	×
311	} else {
UNCOV 312	throw boost::not_a_dag();	×
313	}
314	}
315
316	// Go over all sinks
317	const DataFlowNode* primary_sink = nullptr;	4✔
318	std::unordered_map<const DataFlowNode, std::list<const DataFlowNode>> lists;	4✔
319	std::unordered_map<const DataFlowNode, std::list<const Memlet>> memlet_queues;	4✔
320	std::unordered_map<const Memlet, const DataFlowNode> memlet_map;	4✔
321	for (const auto* sink : sinks) {	9✔
322	lists.insert({sink, {}});	5!
323	memlet_queues.insert({sink, {}});	5!
324	std::unordered_set<const DataFlowNode*> primary_blocker;	5✔
325
326	// Perform reversed DFS starting form sink node
327	std::unordered_set<const DataFlowNode*> visited;	5✔
328	std::stack<std::pair<const DataFlowNode, const DataFlowNode>> stack({{sink, nullptr}});	5!
329	while (!stack.empty()) {	40!
330	const auto [current, successor] = stack.top();	225!
331	stack.pop();	35!
332
333	// Special case: Only handle primary edges
334	if (this->out_degree(*current) > 1) {	35!
335	if (const auto* code_node = dynamic_cast<const CodeNode*>(current)) {	7!
NEW 336	std::unordered_map<std::string, const Memlet*> edges_map;	×
NEW 337	const Memlet* memlet = nullptr; // Memlet from current to successor	×
338	for (const auto& oedge : this->out_edges(*code_node)) {	×
339	edges_map.insert({oedge.src_conn(), &oedge});	×
340	if (&oedge.dst() == successor) {	×
UNCOV 341	memlet = &oedge;	×
342	}	×
343	}
344	const auto* primary_dst = &edges_map.at(code_node->output(0))->dst();	×
345	if (primary_dst == successor) {	×
UNCOV 346	for (size_t j = 1; j < code_node->outputs().size(); j++) {	×
UNCOV 347	const auto* edge = edges_map.at(code_node->output(j));	×
348	if (&edge->dst() != successor) {	×
349	memlet_queues.at(sink).push_back(edge);	×
350	}	×
351	}	×
352	} else {	×
353	if (primary_blocker.empty()) {	×
354	memlet_map.insert({memlet, sink});	×
NEW 355	} else {	×
356	memlet_map.insert({memlet, nullptr});	×
357	}
NEW 358	primary_blocker.insert(current);	×
NEW 359	continue;	×
360	}
UNCOV 361	} else {	×
362	std::vector<std::pair<const Memlet*, size_t>> edges_list;	7✔
363	const Memlet* memlet = nullptr; // Memlet from current to successor	7✔
364	for (const auto& oedge : this->out_edges(*current)) {	21!
365	const auto* dst = &oedge.dst();	14!
366	size_t value = 0;	14✔
367	if (const auto* tasklet = dynamic_cast<const Tasklet*>(dst)) {	14!
368	value = tasklet->code();	14!
369	} else if (const auto* libnode = dynamic_cast<const LibraryNode*>(dst)) {	14!
370	value = 52;	×
371	for (char c : libnode->code().value()) {	×
372	value += c;	×
373	}
UNCOV 374	}	×
375	edges_list.push_back({&oedge, value});	14!
376	if (&oedge.dst() == successor) {	14!
377	memlet = &oedge;	8✔
378	}	8✔
379	}
380	std::sort(edges_list.begin(), edges_list.end(), [](const auto& a, const auto& b) {	21!
381	return a.second > b.second \|\|	28!
382	(a.second == b.second && a.first->element_id() < b.first->element_id());	14✔
383	});
384	const auto* primary_dst = &edges_list.front().first->dst();	7!
385	if (primary_dst == successor) {	14✔
386	for (size_t j = 1; j < edges_list.size(); j++) {	8✔
387	const auto* edge = edges_list.at(j).first;	4!
388	if (&edge->dst() != successor) {	4!
389	memlet_queues.at(sink).push_back(edge);	3!
390	}	3✔
391	}	4✔
392	} else {	4✔
393	if (primary_blocker.empty()) {	3!
394	memlet_map.insert({memlet, sink});	3!
395	} else {	3✔
NEW 396	memlet_map.insert({memlet, nullptr});	×
397	}
398	primary_blocker.insert(current);	3!
399	continue;	3✔
400	}
401	}	7✔
402	}	4✔
403
404	// Put the current element in the list
405	if (visited.contains(current)) {	32!
NEW 406	throw boost::not_a_dag();	×
407	}
408	visited.insert(current);	32!
409	if (primary_blocker.contains(current)) {	32!
410	primary_blocker.erase(current);	2!
411	}	2✔
412	lists.at(sink).push_front(current);	32!
413
414	// Put all predecessors on the stack
415	if (const auto* code_node = dynamic_cast<const CodeNode*>(current)) {	32!
416	std::unordered_set<const DataFlowNode*> pushed_predecessors;	12✔
417	for (const auto& input : code_node->inputs()) {	31!
418	const Memlet* iedge = nullptr;	19✔
419	for (auto& in_edge : this->in_edges(*code_node)) {	26!
420	if (in_edge.dst_conn() == input) {	26!
421	iedge = &in_edge;	19✔
422	break;	19✔
423	}
424	}
425	if (!iedge) {	19!
NEW 426	continue;	×
427	}
428	const auto* src = &iedge->src();	19!
429	if (pushed_predecessors.contains(src)) {	19!
430	continue;	1✔
431	}
432	stack.push({src, current});	18!
433	pushed_predecessors.insert(src);	18!
434	}
435	} else {	12✔
436	std::vector<std::pair<const DataFlowNode*, size_t>> tmp_inputs;	20✔
437	for (const auto& iedge : this->in_edges(*current)) {	32!
438	const auto* src = &iedge.src();	12!
439	size_t value = 0;	12✔
440	if (const auto* tasklet = dynamic_cast<const Tasklet*>(src)) {	12!
441	value = tasklet->code();	12!
442	} else if (const auto* libnode = dynamic_cast<const LibraryNode*>(src)) {	12!
443	value = 52;	×
444	for (char c : libnode->code().value()) {	×
UNCOV 445	value += c;	×
446	}
NEW 447	}	×
448	tmp_inputs.push_back({src, value});	12!
449	}
450	std::sort(tmp_inputs.begin(), tmp_inputs.end(), [](const auto& a, const auto& b) {	20!
NEW 451	return a.second > b.second \|\|	×
NEW 452	(a.second == b.second && a.first->element_id() < b.first->element_id());	×
453	});
454	std::unordered_set<const DataFlowNode*> pushed_predecessors;	20✔
455	for (const auto& tmp_input : tmp_inputs) {	32✔
456	if (pushed_predecessors.contains(tmp_input.first)) {	12!
NEW 457	continue;	×
458	}
459	stack.push({tmp_input.first, current});	24!
460	pushed_predecessors.insert(tmp_input.first);	12!
461	}
462	}	20✔
463	}
464
465	// Store primary sink
466	if (primary_blocker.empty()) {	5✔
467	primary_sink = sink;	4✔
468	}	4✔
469	}	5✔
470	if (!primary_sink) {	4!
NEW 471	throw boost::not_a_dag();	×
472	}
473
474	std::list<const DataFlowNode*> queue = {primary_sink};	4!
475	std::unordered_set<const DataFlowNode*> visited;	4✔
476	while (!queue.empty()) {	11✔
477	const auto* current = queue.front();	7✔
478	queue.pop_front();	7✔
479	if (visited.contains(current)) {	7!
480	continue;	2✔
481	}
482
483	// Fill global list
484	components.at(i).insert(components.at(i).end(), lists.at(current).begin(), lists.at(current).end());	5!
485	visited.insert(current);	5!
486
487	// Fill queue
488	for (const auto* memlet : memlet_queues.at(current)) {	8!
489	const auto* node = memlet_map.at(memlet);	3!
490	if (node) {	3!
491	queue.push_back(node);	3!
492	}	3✔
493	}
494	}
495	}	4!
496
497	// Sort components
498	std::sort(components.begin(), components.end(), [](const auto& a, const auto& b) {	5!
499	return a.size() > b.size() \|\|	4!
500	(a.size() == b.size() && a.size() > 0 && a.front()->element_id() < b.front()->element_id());	2!
501	});
502
503	// Resulting data structure
504	std::list<const DataFlowNode*> order;	3✔
505	for (auto& component : components) {	7✔
506	order.insert(order.end(), component.begin(), component.end());	4!
507	}
508
509	return order;	3✔
510	};	3!
511
512
513	} // namespace data_flow
514	} // namespace sdfg

daisytuner / sdfglib / 20540617027

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