tools/llvmc2/CompilationGraph.cpp

   1 //===--- CompilationGraph.cpp - The LLVM Compiler Driver --------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open
   6 // Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  Compilation graph - implementation.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "CompilationGraph.h"
  15
  16 #include "llvm/Support/CommandLine.h"
  17 #include "llvm/Support/DOTGraphTraits.h"
  18 #include "llvm/Support/GraphWriter.h"
  19
  20 #include <algorithm>
  21 #include <iostream>
  22 #include <iterator>
  23 #include <queue>
  24 #include <stdexcept>
  25
  26 using namespace llvm;
  27 using namespace llvmcc;
  28
  29 extern cl::list<std::string> InputFilenames;
  30 extern cl::opt<std::string> OutputFilename;
  31
  32 namespace {
  33
  34   // Choose edge that returns
  35   template <class C>
  36   const Edge* ChooseEdge(const C& EdgesContainer,
  37                          const std::string& NodeName = "root") {
  38     const Edge* DefaultEdge = 0;
  39
  40     for (typename C::const_iterator B = EdgesContainer.begin(),
  41            E = EdgesContainer.end(); B != E; ++B) {
  42       const Edge* E = B->getPtr();
  43
  44       if (E->isDefault())
  45         if (!DefaultEdge)
  46           DefaultEdge = E;
  47         else
  48           throw std::runtime_error("Node " + NodeName
  49                                    + ": multiple default outward edges found!"
  50                                    "Most probably a specification error.");
  51       if (E->isEnabled())
  52         return E;
  53     }
  54
  55     if (DefaultEdge)
  56       return DefaultEdge;
  57     else
  58       throw std::runtime_error("Node " + NodeName
  59                                + ": no default outward edge found!"
  60                                "Most probably a specification error.");
  61   }
  62
  63 }
  64
  65 CompilationGraph::CompilationGraph() {
  66   NodesMap["root"] = Node(this);
  67 }
  68
  69 Node& CompilationGraph::getNode(const std::string& ToolName) {
  70   nodes_map_type::iterator I = NodesMap.find(ToolName);
  71   if (I == NodesMap.end())
  72     throw std::runtime_error("Node " + ToolName + " is not in the graph");
  73   return I->second;
  74 }
  75
  76 const Node& CompilationGraph::getNode(const std::string& ToolName) const {
  77   nodes_map_type::const_iterator I = NodesMap.find(ToolName);
  78   if (I == NodesMap.end())
  79     throw std::runtime_error("Node " + ToolName + " is not in the graph!");
  80   return I->second;
  81 }
  82
  83 const std::string& CompilationGraph::getLanguage(const sys::Path& File) const {
  84   LanguageMap::const_iterator Lang = ExtsToLangs.find(File.getSuffix());
  85   if (Lang == ExtsToLangs.end())
  86     throw std::runtime_error("Unknown suffix: " + File.getSuffix() + '!');
  87   return Lang->second;
  88 }
  89
  90 const CompilationGraph::tools_vector_type&
  91 CompilationGraph::getToolsVector(const std::string& LangName) const
  92 {
  93   tools_map_type::const_iterator I = ToolsMap.find(LangName);
  94   if (I == ToolsMap.end())
  95     throw std::runtime_error("No tools corresponding to " + LangName
  96                              + " found!");
  97   return I->second;
  98 }
  99
 100 void CompilationGraph::insertNode(Tool* V) {
 101   if (NodesMap.count(V->Name()) == 0) {
 102     Node N;
 103     N.OwningGraph = this;
 104     N.ToolPtr = V;
 105     NodesMap[V->Name()] = N;
 106   }
 107 }
 108
 109 void CompilationGraph::insertEdge(const std::string& A, Edge* E) {
 110   Node& B = getNode(E->ToolName());
 111   if (A == "root") {
 112     const std::string& InputLanguage = B.ToolPtr->InputLanguage();
 113     ToolsMap[InputLanguage].push_back(IntrusiveRefCntPtr<Edge>(E));
 114     NodesMap["root"].AddEdge(E);
 115   }
 116   else {
 117     Node& N = getNode(A);
 118     N.AddEdge(E);
 119   }
 120   // Increase the inward edge counter.
 121   B.IncrInEdges();
 122 }
 123
 124 // Pass input file through the chain until we bump into a Join node or
 125 // a node that says that it is the last.
 126 const JoinTool*
 127 CompilationGraph::PassThroughGraph (sys::Path& In,
 128                                     const Node* StartNode,
 129                                     const sys::Path& TempDir) const {
 130   bool Last = false;
 131   const Node* CurNode = StartNode;
 132   JoinTool* ret = 0;
 133
 134   while(!Last) {
 135     sys::Path Out;
 136     Tool* CurTool = CurNode->ToolPtr.getPtr();
 137
 138     if (CurTool->IsJoin()) {
 139       ret = &dynamic_cast<JoinTool&>(*CurTool);
 140       ret->AddToJoinList(In);
 141       break;
 142     }
 143
 144     // Is this the last tool?
 145     if (!CurNode->HasChildren() || CurTool->IsLast()) {
 146       // Check if the first tool is also the last
 147       if (Out.empty())
 148         Out.set(In.getBasename());
 149       else
 150         Out.appendComponent(In.getBasename());
 151       Out.appendSuffix(CurTool->OutputSuffix());
 152       Last = true;
 153     }
 154     else {
 155       Out = TempDir;
 156       Out.appendComponent(In.getBasename());
 157       Out.appendSuffix(CurTool->OutputSuffix());
 158       Out.makeUnique(true, NULL);
 159       Out.eraseFromDisk();
 160     }
 161
 162     if (CurTool->GenerateAction(In, Out).Execute() != 0)
 163       throw std::runtime_error("Tool returned error code!");
 164
 165     CurNode = &getNode(ChooseEdge(CurNode->OutEdges,
 166                                   CurNode->Name())->ToolName());
 167     In = Out; Out.clear();
 168   }
 169
 170   return ret;
 171 }
 172
 173 // Sort the nodes in topological order.
 174 void CompilationGraph::TopologicalSort(std::vector<const Node*>& Out) {
 175   std::queue<const Node*> Q;
 176   Q.push(&getNode("root"));
 177
 178   while (!Q.empty()) {
 179     const Node* A = Q.front();
 180     Q.pop();
 181     Out.push_back(A);
 182     for (Node::const_iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
 183          EB != EE; ++EB) {
 184       Node* B = &getNode((*EB)->ToolName());
 185       B->DecrInEdges();
 186       if (B->HasNoInEdges())
 187         Q.push(B);
 188     }
 189   }
 190 }
 191
 192 namespace {
 193   bool NotJoinNode(const Node* N) {
 194     return N->ToolPtr ? !N->ToolPtr->IsJoin() : true;
 195   }
 196 }
 197
 198 // Call TopologicalSort and filter the resulting list to include
 199 // only Join nodes.
 200 void CompilationGraph::
 201 TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out) {
 202   std::vector<const Node*> TopSorted;
 203   TopologicalSort(TopSorted);
 204   std::remove_copy_if(TopSorted.begin(), TopSorted.end(),
 205                       std::back_inserter(Out), NotJoinNode);
 206 }
 207
 208 // Find head of the toolchain corresponding to the given file.
 209 const Node* CompilationGraph::FindToolChain(const sys::Path& In) const {
 210   const std::string& InLanguage = getLanguage(In);
 211   const tools_vector_type& TV = getToolsVector(InLanguage);
 212   if (TV.empty())
 213     throw std::runtime_error("No toolchain corresponding to language"
 214                              + InLanguage + " found!");
 215   return &getNode(ChooseEdge(TV)->ToolName());
 216 }
 217
 218 int CompilationGraph::Build (const sys::Path& TempDir) {
 219
 220   // For each input file:
 221   for (cl::list<std::string>::const_iterator B = InputFilenames.begin(),
 222         E = InputFilenames.end(); B != E; ++B) {
 223     sys::Path In = sys::Path(*B);
 224
 225     // Find the toolchain corresponding to this file.
 226     const Node* N = FindToolChain(In);
 227     // Pass file through the chain starting at head.
 228     PassThroughGraph(In, N, TempDir);
 229   }
 230
 231   std::vector<const Node*> JTV;
 232   TopologicalSortFilterJoinNodes(JTV);
 233
 234   // For all join nodes in topological order:
 235   for (std::vector<const Node*>::iterator B = JTV.begin(), E = JTV.end();
 236        B != E; ++B) {
 237     // TOFIX: more testing, merge some parts with PassThroughGraph.
 238     sys::Path Out;
 239     const Node* CurNode = *B;
 240     JoinTool* JT = &dynamic_cast<JoinTool&>(*CurNode->ToolPtr.getPtr());
 241     bool IsLast = false;
 242
 243     if (JT->JoinListEmpty())
 244       continue;
 245
 246     if (!CurNode->HasChildren() || JT->IsLast()) {
 247       if (OutputFilename.empty()) {
 248         Out.set("a");
 249         Out.appendSuffix(JT->OutputSuffix());
 250       }
 251       else
 252         Out.set(OutputFilename);
 253       IsLast = true;
 254     }
 255     else {
 256       Out = TempDir;
 257       Out.appendComponent("tmp");
 258       Out.appendSuffix(JT->OutputSuffix());
 259       Out.makeUnique(true, NULL);
 260       Out.eraseFromDisk();
 261     }
 262
 263     if (JT->GenerateAction(Out).Execute() != 0)
 264       throw std::runtime_error("Tool returned error code!");
 265
 266     if (!IsLast) {
 267       const Node* NextNode = &getNode(ChooseEdge(CurNode->OutEdges,
 268                                                  CurNode->Name())->ToolName());
 269       PassThroughGraph(Out, NextNode, TempDir);
 270     }
 271   }
 272
 273   return 0;
 274 }
 275
 276 // Code related to graph visualization.
 277
 278 namespace llvm {
 279   template <>
 280   struct DOTGraphTraits<llvmcc::CompilationGraph*>
 281     : public DefaultDOTGraphTraits
 282   {
 283
 284     template<typename GraphType>
 285     static std::string getNodeLabel(const Node* N, const GraphType&)
 286     {
 287       if (N->ToolPtr)
 288         if (N->ToolPtr->IsJoin())
 289           return N->Name() + "\n (join" +
 290             (N->HasChildren() ? ")"
 291              : std::string(": ") + N->ToolPtr->OutputLanguage() + ')');
 292         else
 293           return N->Name();
 294       else
 295         return "root";
 296     }
 297
 298     template<typename EdgeIter>
 299     static std::string getEdgeSourceLabel(const Node* N, EdgeIter I) {
 300       if (N->ToolPtr)
 301         return N->ToolPtr->OutputLanguage();
 302       else
 303         return I->ToolPtr->InputLanguage();
 304     }
 305   };
 306
 307 }
 308
 309 void CompilationGraph::writeGraph() {
 310   std::ofstream O("CompilationGraph.dot");
 311
 312   if (O.good()) {
 313     llvm::WriteGraph(this, "compilation-graph");
 314     O.close();
 315   }
 316   else {
 317     throw std::runtime_error("");
 318   }
 319 }
 320
 321 void CompilationGraph::viewGraph() {
 322   llvm::ViewGraph(this, "compilation-graph");
 323 }