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/ADT/STLExtras.h"
  17 #include "llvm/Support/CommandLine.h"
  18 #include "llvm/Support/DOTGraphTraits.h"
  19 #include "llvm/Support/GraphWriter.h"
  20
  21 #include <algorithm>
  22 #include <iterator>
  23 #include <limits>
  24 #include <queue>
  25 #include <stdexcept>
  26
  27 using namespace llvm;
  28 using namespace llvmc;
  29
  30 extern cl::list<std::string> InputFilenames;
  31 extern cl::opt<std::string> OutputFilename;
  32 extern cl::list<std::string> Languages;
  33
  34 namespace {
  35
  36   // Go through the list C and find the edge that isEnabled(); if
  37   // there is no such edge, return the default edge; if there is no
  38   // default edge, throw an exception.
  39   template <class C>
  40   const Edge* ChooseEdge(const C& EdgesContainer,
  41                          const std::string& NodeName = "root") {
  42     const Edge* DefaultEdge = 0;
  43
  44     for (typename C::const_iterator B = EdgesContainer.begin(),
  45            E = EdgesContainer.end(); B != E; ++B) {
  46       const Edge* E = B->getPtr();
  47
  48       if (E->isDefault())
  49         if (!DefaultEdge)
  50           DefaultEdge = E;
  51         else
  52           throw std::runtime_error("Node " + NodeName
  53                                    + ": multiple default outward edges found!"
  54                                    " Most probably a specification error.");
  55       if (E->isEnabled())
  56         return E;
  57     }
  58
  59     if (DefaultEdge)
  60       return DefaultEdge;
  61     else
  62       throw std::runtime_error("Node " + NodeName
  63                                + ": no default outward edge found!"
  64                                " Most probably a specification error.");
  65   }
  66
  67 }
  68
  69 CompilationGraph::CompilationGraph() {
  70   NodesMap["root"] = Node(this);
  71 }
  72
  73 Node& CompilationGraph::getNode(const std::string& ToolName) {
  74   nodes_map_type::iterator I = NodesMap.find(ToolName);
  75   if (I == NodesMap.end())
  76     throw std::runtime_error("Node " + ToolName + " is not in the graph");
  77   return I->second;
  78 }
  79
  80 const Node& CompilationGraph::getNode(const std::string& ToolName) const {
  81   nodes_map_type::const_iterator I = NodesMap.find(ToolName);
  82   if (I == NodesMap.end())
  83     throw std::runtime_error("Node " + ToolName + " is not in the graph!");
  84   return I->second;
  85 }
  86
  87 const std::string& CompilationGraph::getLanguage(const sys::Path& File) const {
  88   LanguageMap::const_iterator Lang = ExtsToLangs.find(File.getSuffix());
  89   if (Lang == ExtsToLangs.end())
  90     throw std::runtime_error("Unknown suffix: " + File.getSuffix() + '!');
  91   return Lang->second;
  92 }
  93
  94 const CompilationGraph::tools_vector_type&
  95 CompilationGraph::getToolsVector(const std::string& LangName) const
  96 {
  97   tools_map_type::const_iterator I = ToolsMap.find(LangName);
  98   if (I == ToolsMap.end())
  99     throw std::runtime_error("No tool corresponding to the language "
 100                              + LangName + "found!");
 101   return I->second;
 102 }
 103
 104 void CompilationGraph::insertNode(Tool* V) {
 105   if (NodesMap.count(V->Name()) == 0) {
 106     Node N;
 107     N.OwningGraph = this;
 108     N.ToolPtr = V;
 109     NodesMap[V->Name()] = N;
 110   }
 111 }
 112
 113 void CompilationGraph::insertEdge(const std::string& A, Edge* E) {
 114   Node& B = getNode(E->ToolName());
 115   if (A == "root") {
 116     const std::string& InputLanguage = B.ToolPtr->InputLanguage();
 117     ToolsMap[InputLanguage].push_back(IntrusiveRefCntPtr<Edge>(E));
 118     NodesMap["root"].AddEdge(E);
 119   }
 120   else {
 121     Node& N = getNode(A);
 122     N.AddEdge(E);
 123   }
 124   // Increase the inward edge counter.
 125   B.IncrInEdges();
 126 }
 127
 128 namespace {
 129   sys::Path MakeTempFile(const sys::Path& TempDir, const std::string& BaseName,
 130                          const std::string& Suffix) {
 131     sys::Path Out = TempDir;
 132     Out.appendComponent(BaseName);
 133     Out.appendSuffix(Suffix);
 134     Out.makeUnique(true, NULL);
 135     return Out;
 136   }
 137 }
 138
 139 // Pass input file through the chain until we bump into a Join node or
 140 // a node that says that it is the last.
 141 void CompilationGraph::PassThroughGraph (const sys::Path& InFile,
 142                                          const Node* StartNode,
 143                                          const sys::Path& TempDir) const {
 144   bool Last = false;
 145   sys::Path In = InFile;
 146   const Node* CurNode = StartNode;
 147
 148   while(!Last) {
 149     sys::Path Out;
 150     Tool* CurTool = CurNode->ToolPtr.getPtr();
 151
 152     if (CurTool->IsJoin()) {
 153       JoinTool& JT = dynamic_cast<JoinTool&>(*CurTool);
 154       JT.AddToJoinList(In);
 155       break;
 156     }
 157
 158     // Since toolchains do not have to end with a Join node, we should
 159     // check if this Node is the last.
 160     if (!CurNode->HasChildren() || CurTool->IsLast()) {
 161       if (!OutputFilename.empty()) {
 162         Out.set(OutputFilename);
 163       }
 164       else {
 165         Out.set(In.getBasename());
 166         Out.appendSuffix(CurTool->OutputSuffix());
 167       }
 168       Last = true;
 169     }
 170     else {
 171       Out = MakeTempFile(TempDir, In.getBasename(), CurTool->OutputSuffix());
 172     }
 173
 174     if (CurTool->GenerateAction(In, Out).Execute() != 0)
 175       throw std::runtime_error("Tool returned error code!");
 176
 177     if (Last)
 178       return;
 179
 180     CurNode = &getNode(ChooseEdge(CurNode->OutEdges,
 181                                   CurNode->Name())->ToolName());
 182     In = Out; Out.clear();
 183   }
 184 }
 185
 186 // Sort the nodes in topological order.
 187 void CompilationGraph::TopologicalSort(std::vector<const Node*>& Out) {
 188   std::queue<const Node*> Q;
 189   Q.push(&getNode("root"));
 190
 191   while (!Q.empty()) {
 192     const Node* A = Q.front();
 193     Q.pop();
 194     Out.push_back(A);
 195     for (Node::const_iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
 196          EB != EE; ++EB) {
 197       Node* B = &getNode((*EB)->ToolName());
 198       B->DecrInEdges();
 199       if (B->HasNoInEdges())
 200         Q.push(B);
 201     }
 202   }
 203 }
 204
 205 namespace {
 206   bool NotJoinNode(const Node* N) {
 207     return N->ToolPtr ? !N->ToolPtr->IsJoin() : true;
 208   }
 209 }
 210
 211 // Call TopologicalSort and filter the resulting list to include
 212 // only Join nodes.
 213 void CompilationGraph::
 214 TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out) {
 215   std::vector<const Node*> TopSorted;
 216   TopologicalSort(TopSorted);
 217   std::remove_copy_if(TopSorted.begin(), TopSorted.end(),
 218                       std::back_inserter(Out), NotJoinNode);
 219 }
 220
 221 // Find head of the toolchain corresponding to the given file.
 222 const Node* CompilationGraph::
 223 FindToolChain(const sys::Path& In, const std::string* forceLanguage) const {
 224   const std::string& InLanguage =
 225     forceLanguage ? *forceLanguage : getLanguage(In);
 226   const tools_vector_type& TV = getToolsVector(InLanguage);
 227   if (TV.empty())
 228     throw std::runtime_error("No toolchain corresponding to language"
 229                              + InLanguage + " found!");
 230   return &getNode(ChooseEdge(TV)->ToolName());
 231 }
 232
 233 // Build the targets. Command-line options are passed through
 234 // temporary variables.
 235 int CompilationGraph::Build (const sys::Path& TempDir) {
 236
 237   // This is related to -x option handling.
 238   cl::list<std::string>::const_iterator xIter = Languages.begin(),
 239     xBegin = xIter, xEnd = Languages.end();
 240   bool xEmpty = true;
 241   const std::string* xLanguage = 0;
 242   unsigned xPos = 0, xPosNext = 0, filePos = 0;
 243
 244   if (xIter != xEnd) {
 245     xEmpty = false;
 246     xPos = Languages.getPosition(xIter - xBegin);
 247     cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
 248     xPosNext = (xNext == xEnd) ? std::numeric_limits<unsigned>::max()
 249       : Languages.getPosition(xNext - xBegin);
 250     xLanguage = (*xIter == "none") ? 0 : &(*xIter);
 251   }
 252
 253   // For each input file:
 254   for (cl::list<std::string>::const_iterator B = InputFilenames.begin(),
 255          CB = B, E = InputFilenames.end(); B != E; ++B) {
 256     sys::Path In = sys::Path(*B);
 257
 258     // Code for handling the -x option.
 259     // Output: std::string* xLanguage (can be NULL).
 260     if (!xEmpty) {
 261       filePos = InputFilenames.getPosition(B - CB);
 262
 263       if (xPos < filePos) {
 264         if (filePos < xPosNext) {
 265           xLanguage = (*xIter == "none") ? 0 : &(*xIter);
 266         }
 267         else { // filePos >= xPosNext
 268           // Skip xIters while filePos > xPosNext
 269           while (filePos > xPosNext) {
 270             ++xIter;
 271             xPos = xPosNext;
 272
 273             cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
 274             if (xNext == xEnd)
 275               xPosNext = std::numeric_limits<unsigned>::max();
 276             else
 277               xPosNext = Languages.getPosition(xNext - xBegin);
 278             xLanguage = (*xIter == "none") ? 0 : &(*xIter);
 279           }
 280         }
 281       }
 282     }
 283
 284     // Find the toolchain corresponding to this file.
 285     const Node* N = FindToolChain(In, xLanguage);
 286     // Pass file through the chain starting at head.
 287     PassThroughGraph(In, N, TempDir);
 288   }
 289
 290   std::vector<const Node*> JTV;
 291   TopologicalSortFilterJoinNodes(JTV);
 292
 293   // For all join nodes in topological order:
 294   for (std::vector<const Node*>::iterator B = JTV.begin(), E = JTV.end();
 295        B != E; ++B) {
 296
 297     sys::Path Out;
 298     const Node* CurNode = *B;
 299     JoinTool* JT = &dynamic_cast<JoinTool&>(*CurNode->ToolPtr.getPtr());
 300     bool IsLast = false;
 301
 302     // Are there any files to be joined?
 303     if (JT->JoinListEmpty())
 304       continue;
 305
 306     // Is this the last tool in the chain?
 307     // NOTE: we can process several chains in parallel.
 308     if (!CurNode->HasChildren() || JT->IsLast()) {
 309       if (OutputFilename.empty()) {
 310         Out.set("a");
 311         Out.appendSuffix(JT->OutputSuffix());
 312       }
 313       else
 314         Out.set(OutputFilename);
 315       IsLast = true;
 316     }
 317     else {
 318       Out = MakeTempFile(TempDir, "tmp", JT->OutputSuffix());
 319     }
 320
 321     if (JT->GenerateAction(Out).Execute() != 0)
 322       throw std::runtime_error("Tool returned error code!");
 323
 324     if (!IsLast) {
 325       const Node* NextNode = &getNode(ChooseEdge(CurNode->OutEdges,
 326                                                  CurNode->Name())->ToolName());
 327       PassThroughGraph(Out, NextNode, TempDir);
 328     }
 329   }
 330
 331   return 0;
 332 }
 333
 334 // Code related to graph visualization.
 335
 336 namespace llvm {
 337   template <>
 338   struct DOTGraphTraits<llvmc::CompilationGraph*>
 339     : public DefaultDOTGraphTraits
 340   {
 341
 342     template<typename GraphType>
 343     static std::string getNodeLabel(const Node* N, const GraphType&)
 344     {
 345       if (N->ToolPtr)
 346         if (N->ToolPtr->IsJoin())
 347           return N->Name() + "\n (join" +
 348             (N->HasChildren() ? ")"
 349              : std::string(": ") + N->ToolPtr->OutputLanguage() + ')');
 350         else
 351           return N->Name();
 352       else
 353         return "root";
 354     }
 355
 356     template<typename EdgeIter>
 357     static std::string getEdgeSourceLabel(const Node* N, EdgeIter I) {
 358       if (N->ToolPtr)
 359         return N->ToolPtr->OutputLanguage();
 360       else
 361         return I->ToolPtr->InputLanguage();
 362     }
 363   };
 364
 365 }
 366
 367 void CompilationGraph::writeGraph() {
 368   std::ofstream O("CompilationGraph.dot");
 369
 370   if (O.good()) {
 371     llvm::WriteGraph(this, "compilation-graph");
 372     O.close();
 373   }
 374   else {
 375     throw std::runtime_error("");
 376   }
 377 }
 378
 379 void CompilationGraph::viewGraph() {
 380   llvm::ViewGraph(this, "compilation-graph");
 381 }