mirror of
https://github.com/revng/revng
synced 2026-06-21 14:07:57 +00:00
Ivan Krysak
054f9a2b25
(the following is the original commit message) To optimize the algorithms coming from now, having a topological of the nodes of the graph is benefitial. And, considering, no new nodes will be added to the graph from this point on, we can only compute it once. To optimize the ordering even further, augmented graph is used. On top of the original (and earlier added artifical) edges, the graph used for obtaining the ordering get a few extra edges added. `llvm::ReversePostOrderTraversal` is used to convert the graph to the ordered node list.
65 lines
2.1 KiB
C++
65 lines
2.1 KiB
C++
/// \file TopologicalOrdering.cpp
|
|
/// \brief
|
|
|
|
//
|
|
// This file is distributed under the MIT License. See LICENSE.md for details.
|
|
//
|
|
|
|
#include "llvm/ADT/PostOrderIterator.h"
|
|
|
|
#include "Layout.h"
|
|
|
|
std::vector<NodeView>
|
|
extractAugmentedTopologicalOrder(InternalGraph &Graph,
|
|
const LayerContainer &Layers) {
|
|
using AugmentedNode = BidirectionalNode<NodeView>;
|
|
using AugmentedGraph = GenericGraph<AugmentedNode>;
|
|
|
|
// Define internal graph.
|
|
AugmentedGraph Augmented;
|
|
|
|
// Add original nodes in.
|
|
std::unordered_map<size_t, AugmentedNode *> LookupTable;
|
|
for (auto *Node : Graph.nodes()) {
|
|
auto NewNode = Augmented.addNode(Node);
|
|
LookupTable.emplace(Node->Index, NewNode);
|
|
}
|
|
|
|
// Add original edges in.
|
|
for (auto *From : Graph.nodes())
|
|
for (auto *To : From->successors())
|
|
LookupTable.at(From->Index)->addSuccessor(LookupTable.at(To->Index));
|
|
|
|
// Add extra edges.
|
|
for (size_t Layer = 0; Layer < Layers.size(); ++Layer) {
|
|
for (size_t From = 0; From < Layers[Layer].size(); ++From) {
|
|
for (size_t To = From + 1; To < Layers[Layer].size(); ++To) {
|
|
auto *FromNode = LookupTable.at(Layers[Layer][From]->Index);
|
|
auto *ToNode = LookupTable.at(Layers[Layer][To]->Index);
|
|
FromNode->addSuccessor(ToNode);
|
|
}
|
|
}
|
|
}
|
|
|
|
// Ensure there's a single entry point.
|
|
// \note: `EntryNode` is not added to the augmented graph and is never
|
|
// `disconnect`ed, so be careful when using the graph from this point on.
|
|
// The "broken" state is used as a minor optimization to avoid unnecessary
|
|
// cleanup since the graph is stack-allocated and only exists until this
|
|
// function is over.
|
|
AugmentedNode EntryNode;
|
|
for (auto *Node : Augmented.nodes())
|
|
if (!Node->hasPredecessors())
|
|
EntryNode.addSuccessor(Node);
|
|
revng_assert(EntryNode.hasSuccessors());
|
|
|
|
// Store the topological order for the augmented graph
|
|
std::vector<NodeView> Order;
|
|
for (auto *Node : llvm::ReversePostOrderTraversal(&EntryNode))
|
|
if (Node != &EntryNode)
|
|
Order.emplace_back(*Node);
|
|
|
|
revng_assert(Order.size() == Graph.size());
|
|
return Order;
|
|
}
|