Add TopologicalSort method to CompilationGraph.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50743 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/tools/llvmc2/CompilationGraph.h b/tools/llvmc2/CompilationGraph.h
index bf97857..dc388d0 100644
--- a/tools/llvmc2/CompilationGraph.h
+++ b/tools/llvmc2/CompilationGraph.h
@@ -61,7 +61,8 @@
OwningGraph(G), ToolPtr(T), InEdges(0) {}
bool HasChildren() const { return !OutEdges.empty(); }
- const std::string Name() const { return ToolPtr->Name(); }
+ const std::string Name() const
+ { return ToolPtr ? ToolPtr->Name() : "root"; }
// Iteration.
iterator EdgesBegin() { return OutEdges.begin(); }
@@ -75,6 +76,8 @@
// Inward edge counter. Used by Build() to implement topological
// sort.
+ // TOTHINK: Move the counter back into Tool classes? Makes us more
+ // const-correct.
void IncrInEdges() { ++InEdges; }
void DecrInEdges() { --InEdges; }
bool HasNoInEdges() const { return InEdges == 0; }
@@ -82,15 +85,17 @@
// Needed to implement NodeChildIterator/GraphTraits
CompilationGraph* OwningGraph;
// The corresponding Tool.
+ // WARNING: For the root node, ToolPtr is NULL.
llvm::IntrusiveRefCntPtr<Tool> ToolPtr;
// Links to children.
container_type OutEdges;
- // Number of parents.
+ // Number of parents. Used for topological sorting.
unsigned InEdges;
};
class NodesIterator;
+ // The compilation graph itself.
class CompilationGraph {
// Main data structure.
typedef llvm::StringMap<Node> nodes_map_type;
@@ -121,7 +126,7 @@
// Build - Build target(s) from the input file set. Command-line
// options are passed implicitly as global variables.
- int Build(llvm::sys::Path const& tempDir) const;
+ int Build(llvm::sys::Path const& tempDir);
// Return a reference to the node correponding to the given tool
// name. Throws std::runtime_error.
@@ -158,6 +163,14 @@
const Node* StartNode,
const llvm::sys::Path& TempDir) const;
+ // Find head of the toolchain corresponding to the given file.
+ const Node* FindToolChain(const llvm::sys::Path& In) const;
+
+ // Sort the nodes in topological order.
+ void TopologicalSort(std::vector<const Node*>& Out);
+ // Call TopologicalSort and filter the resulting list to include
+ // only Join nodes.
+ void TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out);
};
/// GraphTraits support code.