Convert internal representation to use DAG. This gives us more flexibility and enables future improvements.

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

6 files changed, 366 insertions, 53 deletions

diff --git a/tools/llvmc2/Common.td b/tools/llvmc2/Common.td
index 15b9264d88..ea211e1e1e 100644
--- a/tools/llvmc2/Common.td
+++ b/tools/llvmc2/Common.td
@@ -15,6 +15,10 @@ class Tool<list<dag> l> {
       list<dag> properties = l;
 }
 
+// Special Tool instance - root of all toolchains
+
+def root : Tool<[]>;
+
 // Possible Tool properties
 
 def in_language;
@@ -52,12 +56,13 @@ class LanguageMap<list<LangToSuffixes> lst> {
       list<LangToSuffixes> map = lst;
 }
 
-// Toolchain classes
+// Compilation graph
 
-class ToolChain <list<Tool> lst> {
-      list <Tool> tools = lst;
+class Edge<Tool t1, Tool t2> {
+      Tool a = t1;
+      Tool b = t2;
 }
 
-class ToolChains <list<ToolChain> lst> {
-      list<ToolChain> chains = lst;
+class CompilationGraph<list<Edge> lst> {
+      list<Edge> edges = lst;
 }
diff --git a/tools/llvmc2/CompilationGraph.cpp b/tools/llvmc2/CompilationGraph.cpp
index 36e5fc7c0a..bff1aa5627 100644
--- a/tools/llvmc2/CompilationGraph.cpp
+++ b/tools/llvmc2/CompilationGraph.cpp
@@ -14,46 +14,120 @@
 #include "CompilationGraph.h"
 
 #include "llvm/Support/CommandLine.h"
-#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/DOTGraphTraits.h"
+#include "llvm/Support/GraphWriter.h"
 
 #include <stdexcept>
 
 using namespace llvm;
+using namespace llvmcc;
 
 extern cl::list<std::string> InputFilenames;
 extern cl::opt<std::string> OutputFilename;
 
-int llvmcc::CompilationGraph::Build (const sys::Path& tempDir) const {
-  sys::Path In(InputFilenames.at(0)), Out;
+CompilationGraph::CompilationGraph() {
+  NodesMap["root"] = Node(this);
+}
+
+Node& CompilationGraph::getNode(const std::string& ToolName) {
+  nodes_map_type::iterator I = NodesMap.find(ToolName);
+  if (I == NodesMap.end())
+    throw std::runtime_error("Node " + ToolName + " is not in graph");
+  return I->second;
+}
+
+const Node& CompilationGraph::getNode(const std::string& ToolName) const {
+  nodes_map_type::const_iterator I = NodesMap.find(ToolName);
+  if (I == NodesMap.end())
+    throw std::runtime_error("Node " + ToolName + " is not in graph!");
+  return I->second;
+}
 
-  // Find out which language corresponds to the suffix of the first input file
-  LanguageMap::const_iterator Lang = ExtsToLangs.find(In.getSuffix());
+const std::string& CompilationGraph::getLanguage(const sys::Path& File) const {
+  LanguageMap::const_iterator Lang = ExtsToLangs.find(File.getSuffix());
   if (Lang == ExtsToLangs.end())
-    throw std::runtime_error("Unknown suffix!");
+    throw std::runtime_error("Unknown suffix: " + File.getSuffix() + '!');
+  return Lang->second;
+}
+
+const CompilationGraph::tools_vector_type&
+CompilationGraph::getToolsVector(const std::string& LangName) const
+{
+  tools_map_type::const_iterator I = ToolsMap.find(LangName);
+  if (I == ToolsMap.end())
+    throw std::runtime_error("No tools corresponding to " + LangName
+                             + " found!");
+  return I->second;
+}
+
+void CompilationGraph::insertVertex(const IntrusiveRefCntPtr<Tool> V) {
+  if (!NodesMap.count(V->Name())) {
+    Node N;
+    N.OwningGraph = this;
+    N.ToolPtr = V;
+    NodesMap[V->Name()] = N;
+  }
+}
+
+void CompilationGraph::insertEdge(const std::string& A,
+                                  const std::string& B) {
+  // TOTHINK: check this at compile-time?
+  if (B == "root")
+    throw std::runtime_error("Edges back to the root are not allowed!"
+                             "Compilation graph should be acyclic!");
 
-  // Find the toolchain corresponding to this language
-  ToolChainMap::const_iterator ToolsIt = ToolChains.find(Lang->second);
-  if (ToolsIt == ToolChains.end())
-    throw std::runtime_error("Unknown language!");
-  ToolChain Tools = ToolsIt->second;
+  if (A == "root") {
+    const Node& N = getNode(B);
+    const std::string& InputLanguage = N.ToolPtr->InputLanguage();
+    ToolsMap[InputLanguage].push_back(B);
 
+    // Needed to support iteration via GraphTraits.
+    NodesMap["root"].Children.push_back(B);
+  }
+  else {
+    Node& NA = getNode(A);
+    // Check that there is a node at B.
+    getNode(B);
+    NA.Children.push_back(B);
+  }
+}
+
+// TOFIX: extend, add an ability to choose between different
+// toolchains, support more interesting graph topologies.
+int CompilationGraph::Build (const sys::Path& tempDir) const {
   PathVector JoinList;
+  const Tool* JoinTool = 0;
+  sys::Path In, Out;
 
+  // For each input file
   for (cl::list<std::string>::const_iterator B = InputFilenames.begin(),
         E = InputFilenames.end(); B != E; ++B) {
     In = sys::Path(*B);
 
-    // Pass input file through the toolchain
-    for (ToolChain::const_iterator B = Tools.begin(), E = Tools.end();
-         B != E; ++B) {
+    // Get to the head of the toolchain.
+    const tools_vector_type& TV = getToolsVector(getLanguage(In));
+    if(TV.empty())
+      throw std::runtime_error("Tool names vector is empty!");
+    const Node* N = &getNode(*TV.begin());
 
-      const Tool* CurTool = B->getPtr();
+    // Pass it through the chain until we bump into a Join node or a
+    // node that says that it is the last.
+    bool Last = false;
+    while(!Last) {
+      const Tool* CurTool = N->ToolPtr.getPtr();
 
-      // Is this the last step in the chain?
-      if (llvm::next(B) == E || CurTool->IsLast()) {
+      if(CurTool->IsJoin()) {
         JoinList.push_back(In);
+        JoinTool = CurTool;
         break;
       }
+
+      // Is this the last tool?
+      if (N->Children.empty() || CurTool->IsLast()) {
+        Out.appendComponent(In.getBasename());
+        Out.appendSuffix(CurTool->OutputSuffix());
+        Last = true;
+      }
       else {
         Out = tempDir;
         Out.appendComponent(In.getBasename());
@@ -65,24 +139,57 @@ int llvmcc::CompilationGraph::Build (const sys::Path& tempDir) const {
       if (CurTool->GenerateAction(In, Out).Execute() != 0)
         throw std::runtime_error("Tool returned error code!");
 
+      N = &getNode(*N->Children.begin());
       In = Out; Out.clear();
     }
   }
 
-  // Pass .o files to linker
-  const Tool* JoinNode = (--Tools.end())->getPtr();
+  if(JoinTool) {
+    // 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(JoinTool->OutputSuffix());
+    }
 
-  // If the final output name is empty, set it to "a.out"
-  if (!OutputFilename.empty()) {
-    Out = sys::Path(OutputFilename);
+    if (JoinTool->GenerateAction(JoinList, Out).Execute() != 0)
+      throw std::runtime_error("Tool returned error code!");
   }
-  else {
-    Out = sys::Path("a");
-    Out.appendSuffix(JoinNode->OutputSuffix());
+
+  return 0;
+}
+
+namespace llvm {
+  template <>
+  struct DOTGraphTraits<llvmcc::CompilationGraph*>
+    : public DefaultDOTGraphTraits
+  {
+
+  template<typename GraphType>
+  static std::string getNodeLabel(const Node* N, const GraphType&) {
+    if (N->ToolPtr)
+      return N->ToolPtr->Name();
+    else
+      return "root";
   }
 
-  if (JoinNode->GenerateAction(JoinList, Out).Execute() != 0)
-    throw std::runtime_error("Tool returned error code!");
+  };
+}
 
-  return 0;
+void CompilationGraph::writeGraph() {
+  std::ofstream O("CompilationGraph.dot");
+
+  if(O.good()) {
+    llvm::WriteGraph(this, "CompilationGraph");
+    O.close();
+  }
+  else {
+    throw std::runtime_error("");
+  }
+}
+
+void CompilationGraph::viewGraph() {
+  llvm::ViewGraph(this, "CompilationGraph");
 }
diff --git a/tools/llvmc2/CompilationGraph.h b/tools/llvmc2/CompilationGraph.h
index c34b58ff5e..f46b287bd5 100644
--- a/tools/llvmc2/CompilationGraph.h
+++ b/tools/llvmc2/CompilationGraph.h
@@ -17,20 +17,196 @@
 #include "AutoGenerated.h"
 #include "Tool.h"
 
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/iterator"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/System/Path.h"
 
+#include <string>
+
 namespace llvmcc {
 
-  typedef std::vector<llvm::IntrusiveRefCntPtr<Tool> > ToolChain;
-  typedef llvm::StringMap<ToolChain> ToolChainMap;
+  class CompilationGraph;
+
+  struct Node {
+    typedef llvm::SmallVector<std::string, 3> sequence_type;
+
+    Node() {}
+    Node(CompilationGraph* G) : OwningGraph(G) {}
+    Node(CompilationGraph* G, Tool* T) : OwningGraph(G), ToolPtr(T) {}
+
+    // Needed to implement NodeChildIterator/GraphTraits
+    CompilationGraph* OwningGraph;
+    // The corresponding Tool.
+    llvm::IntrusiveRefCntPtr<Tool> ToolPtr;
+    // Links to children.
+    sequence_type Children;
+  };
+
+  // This can be generalised to something like value_iterator for maps
+  class NodesIterator : public llvm::StringMap<Node>::iterator {
+    typedef llvm::StringMap<Node>::iterator super;
+    typedef NodesIterator ThisType;
+    typedef Node* pointer;
+    typedef Node& reference;
 
-  struct CompilationGraph {
-    ToolChainMap ToolChains;
+  public:
+    NodesIterator(super I) : super(I) {}
+
+    inline reference operator*() const {
+      return super::operator->()->second;
+    }
+    inline pointer operator->() const {
+      return &super::operator->()->second;
+    }
+  };
+
+  class CompilationGraph {
+    typedef llvm::StringMap<Node> nodes_map_type;
+    typedef llvm::SmallVector<std::string, 3> tools_vector_type;
+    typedef llvm::StringMap<tools_vector_type> tools_map_type;
+
+    // Map from file extensions to language names.
     LanguageMap ExtsToLangs;
+    // Map from language names to lists of tool names.
+    tools_map_type ToolsMap;
+    // Map from tool names to Tool objects.
+    nodes_map_type NodesMap;
+
+  public:
 
+    CompilationGraph();
+
+    // insertVertex - insert a new node into the graph.
+    void insertVertex(const llvm::IntrusiveRefCntPtr<Tool> T);
+
+    // insertEdge - Insert a new edge into the graph. This function
+    // assumes that both A and B have been already inserted.
+    void insertEdge(const std::string& A, const std::string& B);
+
+    // Build - Build the target(s) from the set of the input
+    // files. Command-line options are passed implicitly as global
+    // variables.
     int Build(llvm::sys::Path const& tempDir) const;
+
+    /// viewGraph - This function is meant for use from the debugger.
+    /// You can just say 'call G->viewGraph()' and a ghostview window
+    /// should pop up from the program, displaying the compilation
+    /// graph. This depends on there being a 'dot' and 'gv' program
+    /// in your path.
+    void viewGraph();
+
+    /// Write a CompilationGraph.dot file.
+    void writeGraph();
+
+    // GraphTraits support
+
+    typedef NodesIterator nodes_iterator;
+
+    nodes_iterator nodes_begin() {
+      return NodesIterator(NodesMap.begin());
+    }
+
+    nodes_iterator nodes_end() {
+      return NodesIterator(NodesMap.end());
+    }
+
+    // Return a reference to the node correponding to the given tool
+    // name. Throws std::runtime_error in case of error.
+    Node& getNode(const std::string& ToolName);
+    const Node& getNode(const std::string& ToolName) const;
+
+    // Auto-generated function.
+    friend void PopulateCompilationGraph(CompilationGraph&);
+
+  private:
+    // Helper function - find out which language corresponds to the
+    // suffix of this file
+    const std::string& getLanguage(const llvm::sys::Path& File) const;
+
+    // Return a reference to the tool names list correponding to the
+    // given language name. Throws std::runtime_error in case of
+    // error.
+    const tools_vector_type& getToolsVector(const std::string& LangName) const;
+  };
+
+  // Auxiliary class needed to implement GraphTraits support.
+  class NodeChildIterator : public bidirectional_iterator<Node, ptrdiff_t> {
+    typedef NodeChildIterator ThisType;
+    typedef Node::sequence_type::iterator iterator;
+
+    CompilationGraph* OwningGraph;
+    iterator KeyIter;
+  public:
+    typedef Node* pointer;
+    typedef Node& reference;
+
+    NodeChildIterator(Node* N, iterator I) :
+      OwningGraph(N->OwningGraph), KeyIter(I) {}
+
+    const ThisType& operator=(const ThisType& I) {
+      assert(OwningGraph == I.OwningGraph);
+      KeyIter = I.KeyIter;
+      return *this;
+    }
+
+    inline bool operator==(const ThisType& I) const
+    { return KeyIter == I.KeyIter; }
+    inline bool operator!=(const ThisType& I) const
+    { return KeyIter != I.KeyIter; }
+
+    inline pointer operator*() const {
+      return &OwningGraph->getNode(*KeyIter);
+    }
+    inline pointer operator->() const {
+      return &OwningGraph->getNode(*KeyIter);
+    }
+
+    ThisType& operator++() { ++KeyIter; return *this; } // Preincrement
+    ThisType operator++(int) { // Postincrement
+      ThisType tmp = *this;
+      ++*this;
+      return tmp;
+    }
+
+    inline ThisType& operator--() { --KeyIter; return *this; }  // Predecrement
+    inline ThisType operator--(int) { // Postdecrement
+      ThisType tmp = *this;
+      --*this;
+      return tmp;
+    }
+
+  };
+}
+
+namespace llvm {
+  template <>
+  struct GraphTraits<llvmcc::CompilationGraph*> {
+    typedef llvmcc::CompilationGraph GraphType;
+    typedef llvmcc::Node NodeType;
+    typedef llvmcc::NodeChildIterator ChildIteratorType;
+
+    static NodeType* getEntryNode(GraphType* G) {
+      return &G->getNode("root");
+    }
+
+    static ChildIteratorType child_begin(NodeType* N) {
+      return ChildIteratorType(N, N->Children.begin());
+    }
+    static ChildIteratorType child_end(NodeType* N) {
+      return ChildIteratorType(N, N->Children.end());
+    }
+
+    typedef GraphType::nodes_iterator nodes_iterator;
+    static nodes_iterator nodes_begin(GraphType *G) {
+      return G->nodes_begin();
+    }
+    static nodes_iterator nodes_end(GraphType *G) {
+      return G->nodes_end();
+    }
   };
+
 }
 
 #endif // LLVM_TOOLS_LLVMC2_COMPILATION_GRAPH_H
diff --git a/tools/llvmc2/Example.td b/tools/llvmc2/Example.td
index 68212c3010..d56f7f9635 100644
--- a/tools/llvmc2/Example.td
+++ b/tools/llvmc2/Example.td
@@ -7,7 +7,7 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This file contains toolchain descriptions used by llvmcc.
+// This file contains compilation graph description used by llvmcc.
 //
 //===----------------------------------------------------------------------===//
 
@@ -16,9 +16,14 @@ include "Tools.td"
 
 // Toolchains
 
-def ToolChains : ToolChains<[
-    ToolChain<[llvm_gcc_c, llc, llvm_gcc_assembler, llvm_gcc_linker]>,
-    ToolChain<[llvm_gcc_cpp, llc, llvm_gcc_assembler, llvm_gcc_linker]>,
-    ToolChain<[llvm_as, llc, llvm_gcc_assembler, llvm_gcc_linker]>,
-    ToolChain<[llvm_gcc_assembler, llvm_gcc_linker]>
+def CompilationGraph : CompilationGraph<[
+    Edge<root, llvm_gcc_c>,
+    Edge<root, llvm_gcc_assembler>,
+    Edge<root, llvm_gcc_cpp>,
+    Edge<root, llvm_as>,
+    Edge<llvm_gcc_c, llc>,
+    Edge<llvm_gcc_cpp, llc>,
+    Edge<llvm_as, llc>,
+    Edge<llc, llvm_gcc_assembler>,
+    Edge<llvm_gcc_assembler, llvm_gcc_linker>
     ]>;
diff --git a/tools/llvmc2/ExampleWithOpt.td b/tools/llvmc2/ExampleWithOpt.td
index 9128d311c5..64ee883ec0 100644
--- a/tools/llvmc2/ExampleWithOpt.td
+++ b/tools/llvmc2/ExampleWithOpt.td
@@ -7,7 +7,7 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This file contains toolchain descriptions used by llvmcc.
+// This file contains compilation graph description used by llvmcc.
 //
 //===----------------------------------------------------------------------===//
 
@@ -16,9 +16,15 @@ include "Tools.td"
 
 // Toolchains
 
-def ToolChains : ToolChains<[
-    ToolChain<[llvm_gcc_c, opt, llc, llvm_gcc_assembler, llvm_gcc_linker]>,
-    ToolChain<[llvm_gcc_cpp, opt, llc, llvm_gcc_assembler, llvm_gcc_linker]>,
-    ToolChain<[llvm_as, opt, llc, llvm_gcc_assembler, llvm_gcc_linker]>,
-    ToolChain<[llvm_gcc_assembler, llvm_gcc_linker]>
+def CompilationGraph : CompilationGraph<[
+    Edge<root, llvm_gcc_c>,
+    Edge<root, llvm_gcc_assembler>,
+    Edge<root, llvm_gcc_cpp>,
+    Edge<root, llvm_as>,
+    Edge<llvm_gcc_c, opt>,
+    Edge<llvm_gcc_cpp, opt>,
+    Edge<llvm_as, opt>,
+    Edge<opt, llc>,
+    Edge<llc, llvm_gcc_assembler>,
+    Edge<llvm_gcc_assembler, llvm_gcc_linker>
     ]>;
diff --git a/tools/llvmc2/llvmc.cpp b/tools/llvmc2/llvmc.cpp
index feed61f89f..65f5e11455 100644
--- a/tools/llvmc2/llvmc.cpp
+++ b/tools/llvmc2/llvmc.cpp
@@ -28,13 +28,21 @@ namespace cl = llvm::cl;
 namespace sys = llvm::sys;
 using namespace llvmcc;
 
+// Built-in command-line options.
 // External linkage here is intentional.
-cl::list<std::string> InputFilenames(cl::Positional,
-                                     cl::desc("<input file>"), cl::OneOrMore);
+
+cl::list<std::string> InputFilenames(cl::Positional, cl::desc("<input file>"),
+                                     cl::OneOrMore);
 cl::opt<std::string> OutputFilename("o", cl::desc("Output file name"),
                                     cl::value_desc("file"));
-cl::opt<bool> VerboseMode("v", cl::desc("Enable verbose mode"));
-
+cl::opt<bool> VerboseMode("v",
+                          cl::desc("Enable verbose mode"));
+cl::opt<bool> WriteGraph("write-graph",
+                         cl::desc("Write CompilationGraph.dot file"),
+                         cl::Hidden);
+cl::opt<bool> ViewGraph("view-graph",
+                         cl::desc("Show compilation graph in GhostView"),
+                         cl::Hidden);
 
 namespace {
   int BuildTargets(const CompilationGraph& graph) {
@@ -61,6 +69,12 @@ int main(int argc, char** argv) {
     cl::ParseCommandLineOptions(argc, argv,
                                 "LLVM Compiler Driver(Work In Progress)");
     PopulateCompilationGraph(graph);
+
+    if(WriteGraph)
+      graph.writeGraph();
+    if(ViewGraph)
+      graph.viewGraph();
+
     return BuildTargets(graph);
   }
   catch(const std::exception& ex) {