Add TopologicalSort method to CompilationGraph.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50743 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 78 insertions, 38 deletions

diff --git a/tools/llvmc2/CompilationGraph.cpp b/tools/llvmc2/CompilationGraph.cpp
index 079007d255..8f3918f9e4 100644
--- a/tools/llvmc2/CompilationGraph.cpp
+++ b/tools/llvmc2/CompilationGraph.cpp
@@ -17,6 +17,10 @@
 #include "llvm/Support/DOTGraphTraits.h"
 #include "llvm/Support/GraphWriter.h"
 
+#include <algorithm>
+#include <iostream>
+#include <iterator>
+#include <queue>
 #include <stdexcept>
 
 using namespace llvm;
@@ -166,46 +170,70 @@ CompilationGraph::PassThroughGraph (sys::Path& In,
   return ret;
 }
 
-int CompilationGraph::Build (const sys::Path& TempDir) const {
-  const JoinTool* JT = 0;
+// Sort the nodes in topological order.
+void CompilationGraph::TopologicalSort(std::vector<const Node*>& Out) {
+  std::queue<const Node*> Q;
+  Q.push(&getNode("root"));
+
+  while (!Q.empty()) {
+    const Node* A = Q.front();
+    Q.pop();
+    Out.push_back(A);
+    for (Node::const_iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
+         EB != EE; ++EB) {
+      Node* B = &getNode((*EB)->ToolName());
+      B->DecrInEdges();
+      if (B->HasNoInEdges())
+        Q.push(B);
+    }
+  }
+}
+
+namespace {
+  bool NotJoinNode(const Node* N) {
+    return N->ToolPtr ? !N->ToolPtr->IsJoin() : true;
+  }
+}
+
+// Call TopologicalSort and filter the resulting list to include
+// only Join nodes.
+void CompilationGraph::
+TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out) {
+  std::vector<const Node*> TopSorted;
+  TopologicalSort(TopSorted);
+  std::remove_copy_if(TopSorted.begin(), TopSorted.end(),
+                      std::back_inserter(Out), NotJoinNode);
+}
+
+// Find head of the toolchain corresponding to the given file.
+const Node* CompilationGraph::FindToolChain(const sys::Path& In) const {
+  const std::string& InLanguage = getLanguage(In);
+  const tools_vector_type& TV = getToolsVector(InLanguage);
+  if (TV.empty())
+    throw std::runtime_error("No toolchain corresponding to language"
+                             + InLanguage + " found!");
+  return &getNode(ChooseEdge(TV)->ToolName());
+}
+
+int CompilationGraph::Build (const sys::Path& TempDir) {
 
   // For each input file:
   for (cl::list<std::string>::const_iterator B = InputFilenames.begin(),
         E = InputFilenames.end(); B != E; ++B) {
     sys::Path In = sys::Path(*B);
 
-    // Get to the head of the toolchain.
-    const std::string& InLanguage = getLanguage(In);
-    const tools_vector_type& TV = getToolsVector(InLanguage);
-    if (TV.empty())
-      throw std::runtime_error("No toolchain corresponding to language"
-                               + InLanguage + " found!");
-    const Node* N = &getNode(ChooseEdge(TV)->ToolName());
-
-    // Pass it through the chain starting at head.
-    const JoinTool* NewJoin = PassThroughGraph(In, N, TempDir);
-    if (JT && NewJoin && JT != NewJoin)
-      throw std::runtime_error("Graphs with multiple Join nodes"
-                               "are not yet supported!");
-    else if (NewJoin)
-      JT = NewJoin;
+    // Find the toolchain corresponding to this file.
+    const Node* N = FindToolChain(In);
+    // Pass file through the chain starting at head.
+    PassThroughGraph(In, N, TempDir);
   }
 
-  // For all join nodes in topological order:
-  // TOFIX: implement.
-  if (JT) {
-    sys::Path Out;
-    // If the final output name is empty, set it to "a.out"
-    if (!OutputFilename.empty()) {
-      Out = sys::Path(OutputFilename);
-    }
-    else {
-      Out = sys::Path("a");
-      Out.appendSuffix(JT->OutputSuffix());
-    }
+  std::vector<const Node*> JTV;
+  TopologicalSortFilterJoinNodes(JTV);
 
-    if (JT->GenerateAction(Out).Execute() != 0)
-      throw std::runtime_error("Tool returned error code!");
+  // For all join nodes in topological order:
+  for (std::vector<const Node*>::iterator B = JTV.begin(), E = JTV.end();
+       B != E; ++B) {
   }
 
   return 0;
diff --git a/tools/llvmc2/CompilationGraph.h b/tools/llvmc2/CompilationGraph.h
index bf97857351..dc388d0fa7 100644
--- a/tools/llvmc2/CompilationGraph.h
+++ b/tools/llvmc2/CompilationGraph.h
@@ -61,7 +61,8 @@ namespace llvmcc {
       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 @@ namespace llvmcc {
 
     // 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 @@ namespace llvmcc {
     // 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 @@ namespace llvmcc {
 
     // 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 @@ namespace llvmcc {
                                       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.
diff --git a/tools/llvmc2/Tools.td b/tools/llvmc2/Tools.td
index 76ec856171..67104ec2c7 100644
--- a/tools/llvmc2/Tools.td
+++ b/tools/llvmc2/Tools.td
@@ -39,8 +39,6 @@ def opt : Tool<
 [(in_language "llvm-bitcode"),
  (out_language "llvm-bitcode"),
  (switch_option "opt", (help "Enable opt")),
- //(parameter_option "O", (help "Test Parameter")),
- //(prefix_list_option "P", (help "Test Parameter List")),
  (output_suffix "bc"),
  (cmd_line "opt $INFILE -o $OUTFILE")
 ]>;
diff --git a/tools/llvmc2/llvmc.cpp b/tools/llvmc2/llvmc.cpp
index b991202e43..aeb8b331b4 100644
--- a/tools/llvmc2/llvmc.cpp
+++ b/tools/llvmc2/llvmc.cpp
@@ -45,7 +45,7 @@ cl::opt<bool> ViewGraph("view-graph",
                          cl::Hidden);
 
 namespace {
-  int BuildTargets(const CompilationGraph& graph) {
+  int BuildTargets(CompilationGraph& graph) {
     int ret;
     sys::Path tempDir(sys::Path::GetTemporaryDirectory());
 
@@ -67,7 +67,7 @@ int main(int argc, char** argv) {
     CompilationGraph graph;
 
     cl::ParseCommandLineOptions(argc, argv,
-                                "LLVM Compiler Driver(Work In Progress)");
+                                "LLVM Compiler Driver (Work In Progress)");
     PopulateCompilationGraph(graph);
 
     if (WriteGraph) {
@@ -80,6 +80,7 @@ int main(int argc, char** argv) {
       return 0;
     }
 
+
     if (InputFilenames.empty()) {
       std::cerr << "No input files.\n";
       return 1;