X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=tools%2Fllvmc2%2FCompilationGraph.cpp;h=acf391a29060f79ebf3ab9fbb59aa49a364e8130;hb=6fa1c051dc515b6fd1f9a26ac12fed985469bff5;hp=53195cbe95a20d94c5234844e494711202e416c6;hpb=2ba4c5ababa878b05a7de1e97a98df50d8bcf6c4;p=oota-llvm.git

diff --git a/tools/llvmc2/CompilationGraph.cpp b/tools/llvmc2/CompilationGraph.cpp
index 53195cbe95a..acf391a2906 100644
--- a/tools/llvmc2/CompilationGraph.cpp
+++ b/tools/llvmc2/CompilationGraph.cpp
@@ -11,43 +11,75 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "Error.h"
 #include "CompilationGraph.h"
 
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/DOTGraphTraits.h"
 #include "llvm/Support/GraphWriter.h"
 
+#include <algorithm>
+#include <iterator>
+#include <limits>
+#include <queue>
 #include <stdexcept>
 
 using namespace llvm;
-using namespace llvmcc;
+using namespace llvmc;
 
 extern cl::list<std::string> InputFilenames;
 extern cl::opt<std::string> OutputFilename;
+extern cl::list<std::string> Languages;
+
+namespace llvmc {
+  /// ExtsToLangs - Map from file extensions to language names.
+  LanguageMap GlobalLanguageMap;
+
+  /// GetLanguage -  Find the language name corresponding to the given file.
+  const std::string& GetLanguage(const sys::Path& File) {
+    LanguageMap::const_iterator Lang = GlobalLanguageMap.find(File.getSuffix());
+    if (Lang == GlobalLanguageMap.end())
+      throw std::runtime_error("Unknown suffix: " + File.getSuffix());
+    return Lang->second;
+  }
+}
 
-// Choose one of the edges based on command-line options.
-const Edge* Node::ChooseEdge() const {
-  const Edge* DefaultEdge = 0;
-  for (const_iterator B = EdgesBegin(), E = EdgesEnd();
-       B != E; ++B) {
-    const Edge* E = (*B).getPtr();
-    if (E->isDefault())
-      if (!DefaultEdge)
-        DefaultEdge = E;
-      else
-        throw std::runtime_error("Node " + Name() +
-                                 ": multiple default edges found!"
-                                 "Most probably a specification error.");
-    if (E->isEnabled())
-      return E;
+namespace {
+
+  /// ChooseEdge - Return the edge with the maximum weight.
+  template <class C>
+  const Edge* ChooseEdge(const C& EdgesContainer,
+                         const InputLanguagesSet& InLangs,
+                         const std::string& NodeName = "root") {
+    const Edge* MaxEdge = 0;
+    unsigned MaxWeight = 0;
+    bool SingleMax = true;
+
+    for (typename C::const_iterator B = EdgesContainer.begin(),
+           E = EdgesContainer.end(); B != E; ++B) {
+      const Edge* E = B->getPtr();
+      unsigned EW = E->Weight(InLangs);
+      if (EW > MaxWeight) {
+        MaxEdge = E;
+        MaxWeight = EW;
+        SingleMax = true;
+      } else if (EW == MaxWeight) {
+        SingleMax = false;
+      }
+    }
+
+    if (!SingleMax)
+      throw std::runtime_error("Node " + NodeName +
+                               ": multiple maximal outward edges found!"
+                               " Most probably a specification error.");
+    if (!MaxEdge)
+      throw std::runtime_error("Node " + NodeName +
+                               ": no maximal outward edge found!"
+                               " Most probably a specification error.");
+    return MaxEdge;
   }
 
-  if (DefaultEdge)
-    return DefaultEdge;
-  else
-    throw std::runtime_error("Node " + Name() +
-                             ": no suitable edge found! "
-                             "Most probably a specification error.");
 }
 
 CompilationGraph::CompilationGraph() {
@@ -68,25 +100,19 @@ const Node& CompilationGraph::getNode(const std::string& ToolName) const {
   return I->second;
 }
 
-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: " + File.getSuffix() + '!');
-  return Lang->second;
-}
-
+// Find the tools list corresponding to the given language name.
 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!");
+    throw std::runtime_error("No tool corresponding to the language "
+                             + LangName + " found");
   return I->second;
 }
 
 void CompilationGraph::insertNode(Tool* V) {
-  if (!NodesMap.count(V->Name())) {
+  if (NodesMap.count(V->Name()) == 0) {
     Node N;
     N.OwningGraph = this;
     N.ToolPtr = V;
@@ -94,136 +120,320 @@ void CompilationGraph::insertNode(Tool* V) {
   }
 }
 
-void CompilationGraph::insertEdge(const std::string& A, Edge* E) {
+void CompilationGraph::insertEdge(const std::string& A, Edge* Edg) {
+  Node& B = getNode(Edg->ToolName());
   if (A == "root") {
-    const Node& N = getNode(E->ToolName());
-    const std::string& InputLanguage = N.ToolPtr->InputLanguage();
-    ToolsMap[InputLanguage].push_back(E->ToolName());
-
-    // Needed to support iteration via GraphTraits.
-    NodesMap["root"].AddEdge(E);
+    const char** InLangs = B.ToolPtr->InputLanguages();
+    for (;*InLangs; ++InLangs)
+      ToolsMap[*InLangs].push_back(IntrusiveRefCntPtr<Edge>(Edg));
+    NodesMap["root"].AddEdge(Edg);
   }
   else {
     Node& N = getNode(A);
-    N.AddEdge(E);
+    N.AddEdge(Edg);
+  }
+  // Increase the inward edge counter.
+  B.IncrInEdges();
+}
+
+namespace {
+  sys::Path MakeTempFile(const sys::Path& TempDir, const std::string& BaseName,
+                         const std::string& Suffix) {
+    sys::Path Out;
+
+    // Make sure we don't end up with path names like '/file.o' if the
+    // TempDir is empty.
+    if (TempDir.empty()) {
+      Out.set(BaseName);
+    }
+    else {
+      Out = TempDir;
+      Out.appendComponent(BaseName);
+    }
+    Out.appendSuffix(Suffix);
+    // NOTE: makeUnique always *creates* a unique temporary file,
+    // which is good, since there will be no races. However, some
+    // tools do not like it when the output file already exists, so
+    // they have to be placated with -f or something like that.
+    Out.makeUnique(true, NULL);
+    return Out;
   }
 }
 
 // Pass input file through the chain until we bump into a Join node or
 // a node that says that it is the last.
-const Tool* CompilationGraph::PassThroughGraph (sys::Path& In,
-                                                sys::Path Out,
-                                                const sys::Path& TempDir,
-                                                PathVector& JoinList) const {
+void CompilationGraph::PassThroughGraph (const sys::Path& InFile,
+                                         const Node* StartNode,
+                                         const InputLanguagesSet& InLangs,
+                                         const sys::Path& TempDir) const {
   bool Last = false;
-  const Tool* ret = 0;
-
-  // 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());
+  sys::Path In = InFile;
+  const Node* CurNode = StartNode;
 
   while(!Last) {
-    const Tool* CurTool = N->ToolPtr.getPtr();
+    sys::Path Out;
+    Tool* CurTool = CurNode->ToolPtr.getPtr();
 
     if (CurTool->IsJoin()) {
-      JoinList.push_back(In);
-      ret = CurTool;
+      JoinTool& JT = dynamic_cast<JoinTool&>(*CurTool);
+      JT.AddToJoinList(In);
       break;
     }
 
-    // Is this the last tool?
-    if (!N->HasChildren() || CurTool->IsLast()) {
-      // Check if the first tool is also the last
-      if (Out.empty())
+    // Since toolchains do not have to end with a Join node, we should
+    // check if this Node is the last.
+    if (!CurNode->HasChildren() || CurTool->IsLast()) {
+      if (!OutputFilename.empty()) {
+        Out.set(OutputFilename);
+      }
+      else {
         Out.set(In.getBasename());
-      else
-        Out.appendComponent(In.getBasename());
-      Out.appendSuffix(CurTool->OutputSuffix());
+        Out.appendSuffix(CurTool->OutputSuffix());
+      }
       Last = true;
     }
     else {
-      Out = TempDir;
-      Out.appendComponent(In.getBasename());
-      Out.appendSuffix(CurTool->OutputSuffix());
-      Out.makeUnique(true, NULL);
-      Out.eraseFromDisk();
+      Out = MakeTempFile(TempDir, In.getBasename(), CurTool->OutputSuffix());
     }
 
-    if (CurTool->GenerateAction(In, Out).Execute() != 0)
-      throw std::runtime_error("Tool returned error code!");
+    if (int ret = CurTool->GenerateAction(In, Out, InLangs).Execute())
+      throw error_code(ret);
 
-    N = &getNode(N->ChooseEdge()->ToolName());
+    if (Last)
+      return;
+
+    CurNode = &getNode(ChooseEdge(CurNode->OutEdges,
+                                  InLangs,
+                                  CurNode->Name())->ToolName());
     In = Out; Out.clear();
   }
+}
+
+// Find the head of the toolchain corresponding to the given file.
+// Also, insert an input language into InLangs.
+const Node* CompilationGraph::
+FindToolChain(const sys::Path& In, const std::string* forceLanguage,
+              InputLanguagesSet& InLangs) const {
+
+  // Determine the input language.
+  const std::string& InLanguage =
+    forceLanguage ? *forceLanguage : GetLanguage(In);
 
-  return ret;
+  // Add the current input language to the input language set.
+  InLangs.insert(InLanguage);
+
+  // Find the toolchain for the input language.
+  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, InLangs)->ToolName());
 }
 
-// TOFIX: support more interesting graph topologies. We will need to
-// do topological sorting to process multiple Join nodes correctly.
-int CompilationGraph::Build (const sys::Path& TempDir) const {
-  PathVector JoinList;
-  const Tool* JoinTool = 0;
-  sys::Path In, Out;
+// Helper function used by Build().
+// Traverses initial portions of the toolchains (up to the first Join node).
+// This function is also responsible for handling the -x option.
+void CompilationGraph::BuildInitial (InputLanguagesSet& InLangs,
+                                     const sys::Path& TempDir) {
+  // This is related to -x option handling.
+  cl::list<std::string>::const_iterator xIter = Languages.begin(),
+    xBegin = xIter, xEnd = Languages.end();
+  bool xEmpty = true;
+  const std::string* xLanguage = 0;
+  unsigned xPos = 0, xPosNext = 0, filePos = 0;
+
+  if (xIter != xEnd) {
+    xEmpty = false;
+    xPos = Languages.getPosition(xIter - xBegin);
+    cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
+    xPosNext = (xNext == xEnd) ? std::numeric_limits<unsigned>::max()
+      : Languages.getPosition(xNext - xBegin);
+    xLanguage = (*xIter == "none") ? 0 : &(*xIter);
+  }
 
-  // For each input file
+  // For each input file:
   for (cl::list<std::string>::const_iterator B = InputFilenames.begin(),
-        E = InputFilenames.end(); B != E; ++B) {
-    In = sys::Path(*B);
-
-    const Tool* NewJoin = PassThroughGraph(In, Out, TempDir, JoinList);
-    if (JoinTool && NewJoin && JoinTool != NewJoin)
-      throw std::runtime_error("Graphs with multiple Join nodes"
-                               "are not yet supported!");
-    else if (NewJoin)
-      JoinTool = NewJoin;
+         CB = B, E = InputFilenames.end(); B != E; ++B) {
+    sys::Path In = sys::Path(*B);
+
+    // Code for handling the -x option.
+    // Output: std::string* xLanguage (can be NULL).
+    if (!xEmpty) {
+      filePos = InputFilenames.getPosition(B - CB);
+
+      if (xPos < filePos) {
+        if (filePos < xPosNext) {
+          xLanguage = (*xIter == "none") ? 0 : &(*xIter);
+        }
+        else { // filePos >= xPosNext
+          // Skip xIters while filePos > xPosNext
+          while (filePos > xPosNext) {
+            ++xIter;
+            xPos = xPosNext;
+
+            cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
+            if (xNext == xEnd)
+              xPosNext = std::numeric_limits<unsigned>::max();
+            else
+              xPosNext = Languages.getPosition(xNext - xBegin);
+            xLanguage = (*xIter == "none") ? 0 : &(*xIter);
+          }
+        }
+      }
+    }
+
+    // Find the toolchain corresponding to this file.
+    const Node* N = FindToolChain(In, xLanguage, InLangs);
+    // Pass file through the chain starting at head.
+    PassThroughGraph(In, N, InLangs, TempDir);
   }
+}
 
-  if (JoinTool) {
-    // If the final output name is empty, set it to "a.out"
-    if (!OutputFilename.empty()) {
-      Out = sys::Path(OutputFilename);
+// 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);
+}
+
+int CompilationGraph::Build (const sys::Path& TempDir) {
+
+  InputLanguagesSet InLangs;
+
+  // Traverse initial parts of the toolchains and fill in InLangs.
+  BuildInitial(InLangs, TempDir);
+
+  std::vector<const Node*> JTV;
+  TopologicalSortFilterJoinNodes(JTV);
+
+  // For all join nodes in topological order:
+  for (std::vector<const Node*>::iterator B = JTV.begin(), E = JTV.end();
+       B != E; ++B) {
+
+    sys::Path Out;
+    const Node* CurNode = *B;
+    JoinTool* JT = &dynamic_cast<JoinTool&>(*CurNode->ToolPtr.getPtr());
+    bool IsLast = false;
+
+    // Are there any files in the join list?
+    if (JT->JoinListEmpty())
+      continue;
+
+    // Is this the last tool in the toolchain?
+    // NOTE: we can process several toolchains in parallel.
+    if (!CurNode->HasChildren() || JT->IsLast()) {
+      if (OutputFilename.empty()) {
+        Out.set("a");
+        Out.appendSuffix(JT->OutputSuffix());
+      }
+      else
+        Out.set(OutputFilename);
+      IsLast = true;
     }
     else {
-      Out = sys::Path("a");
-      Out.appendSuffix(JoinTool->OutputSuffix());
+      Out = MakeTempFile(TempDir, "tmp", JT->OutputSuffix());
     }
 
-    if (JoinTool->GenerateAction(JoinList, Out).Execute() != 0)
-      throw std::runtime_error("Tool returned error code!");
+    if (int ret = JT->GenerateAction(Out, InLangs).Execute())
+      throw error_code(ret);
+
+    if (!IsLast) {
+      const Node* NextNode =
+        &getNode(ChooseEdge(CurNode->OutEdges, InLangs,
+                            CurNode->Name())->ToolName());
+      PassThroughGraph(Out, NextNode, InLangs, TempDir);
+    }
   }
 
   return 0;
 }
 
+// Code related to graph visualization.
+
 namespace llvm {
   template <>
-  struct DOTGraphTraits<llvmcc::CompilationGraph*>
+  struct DOTGraphTraits<llvmc::CompilationGraph*>
     : public DefaultDOTGraphTraits
   {
 
-  template<typename GraphType>
-  static std::string getNodeLabel(const Node* N, const GraphType&) {
-    if (N->ToolPtr)
-      return N->Name();
-    else
-      return "root";
-  }
+    template<typename GraphType>
+    static std::string getNodeLabel(const Node* N, const GraphType&)
+    {
+      if (N->ToolPtr)
+        if (N->ToolPtr->IsJoin())
+          return N->Name() + "\n (join" +
+            (N->HasChildren() ? ")"
+             : std::string(": ") + N->ToolPtr->OutputLanguage() + ')');
+        else
+          return N->Name();
+      else
+        return "root";
+    }
 
+    template<typename EdgeIter>
+    static std::string getEdgeSourceLabel(const Node* N, EdgeIter I) {
+      if (N->ToolPtr) {
+        return N->ToolPtr->OutputLanguage();
+      }
+      else {
+        const char** InLangs = I->ToolPtr->InputLanguages();
+        std::string ret;
+
+        for (; *InLangs; ++InLangs) {
+          if (*(InLangs + 1)) {
+            ret += *InLangs;
+            ret +=  ", ";
+          }
+          else {
+            ret += *InLangs;
+          }
+        }
+
+        return ret;
+      }
+    }
   };
+
 }
 
 void CompilationGraph::writeGraph() {
-  std::ofstream O("CompilationGraph.dot");
+  std::ofstream O("compilation-graph.dot");
 
   if (O.good()) {
-    llvm::WriteGraph(this, "CompilationGraph");
+    llvm::WriteGraph(this, "compilation-graph");
     O.close();
   }
   else {
-    throw std::runtime_error("");
+    throw std::runtime_error("Error opening file 'compilation-graph.dot'"
+                             " for writing!");
   }
 }