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