lib/CompilerDriver/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 "llvm/CompilerDriver/BuiltinOptions.h"
  15 #include "llvm/CompilerDriver/CompilationGraph.h"
  16 #include "llvm/CompilerDriver/Error.h"
  17
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/Support/DOTGraphTraits.h"
  20 #include "llvm/Support/GraphWriter.h"
  21 #include "llvm/Support/raw_ostream.h"
  22
  23 #include <algorithm>
  24 #include <cstring>
  25 #include <iterator>
  26 #include <limits>
  27 #include <queue>
  28
  29 using namespace llvm;
  30 using namespace llvmc;
  31
  32 namespace llvmc {
  33
  34   const std::string* LanguageMap::GetLanguage(const sys::Path& File) const {
  35     StringRef suf = sys::path::extension(File.str());
  36     LanguageMap::const_iterator Lang =
  37       this->find(suf.empty() ? "*empty*" : suf);
  38     if (Lang == this->end()) {
  39       PrintError("File '" + File.str() + "' has unknown suffix '"
  40                  + suf.str() + '\'');
  41       return 0;
  42     }
  43     return &Lang->second;
  44   }
  45 }
  46
  47 namespace {
  48
  49   /// ChooseEdge - Return the edge with the maximum weight. Returns 0 on error.
  50   template <class C>
  51   const Edge* ChooseEdge(const C& EdgesContainer,
  52                          const InputLanguagesSet& InLangs,
  53                          const std::string& NodeName = "root") {
  54     const Edge* MaxEdge = 0;
  55     int MaxWeight = 0;
  56     bool SingleMax = true;
  57
  58     // TODO: fix calculation of SingleMax.
  59     for (typename C::const_iterator B = EdgesContainer.begin(),
  60            E = EdgesContainer.end(); B != E; ++B) {
  61       const Edge* e = B->getPtr();
  62       int EW = e->Weight(InLangs);
  63       if (EW < 0) {
  64         // (error) invocation in TableGen -> we don't need to print an error
  65         // message.
  66         return 0;
  67       }
  68       if (EW > MaxWeight) {
  69         MaxEdge = e;
  70         MaxWeight = EW;
  71         SingleMax = true;
  72       } else if (EW == MaxWeight) {
  73         SingleMax = false;
  74       }
  75     }
  76
  77     if (!SingleMax) {
  78       PrintError("Node " + NodeName + ": multiple maximal outward edges found!"
  79                  " Most probably a specification error.");
  80       return 0;
  81     }
  82     if (!MaxEdge) {
  83       PrintError("Node " + NodeName + ": no maximal outward edge found!"
  84                  " Most probably a specification error.");
  85       return 0;
  86     }
  87     return MaxEdge;
  88   }
  89
  90 }
  91
  92 void Node::AddEdge(Edge* Edg) {
  93   // If there already was an edge between two nodes, modify it instead
  94   // of adding a new edge.
  95   const std::string& ToolName = Edg->ToolName();
  96   for (container_type::iterator B = OutEdges.begin(), E = OutEdges.end();
  97        B != E; ++B) {
  98     if ((*B)->ToolName() == ToolName) {
  99       llvm::IntrusiveRefCntPtr<Edge>(Edg).swap(*B);
 100       return;
 101     }
 102   }
 103   OutEdges.push_back(llvm::IntrusiveRefCntPtr<Edge>(Edg));
 104 }
 105
 106 CompilationGraph::CompilationGraph() {
 107   NodesMap["root"] = Node(this);
 108 }
 109
 110 Node* CompilationGraph::getNode(const std::string& ToolName) {
 111   nodes_map_type::iterator I = NodesMap.find(ToolName);
 112   if (I == NodesMap.end()) {
 113     PrintError("Node " + ToolName + " is not in the graph");
 114     return 0;
 115   }
 116   return &I->second;
 117 }
 118
 119 const Node* CompilationGraph::getNode(const std::string& ToolName) const {
 120   nodes_map_type::const_iterator I = NodesMap.find(ToolName);
 121   if (I == NodesMap.end()) {
 122     PrintError("Node " + ToolName + " is not in the graph!");
 123     return 0;
 124   }
 125   return &I->second;
 126 }
 127
 128 // Find the tools list corresponding to the given language name.
 129 const CompilationGraph::tools_vector_type*
 130 CompilationGraph::getToolsVector(const std::string& LangName) const
 131 {
 132   tools_map_type::const_iterator I = ToolsMap.find(LangName);
 133   if (I == ToolsMap.end()) {
 134     PrintError("No tool corresponding to the language " + LangName + " found");
 135     return 0;
 136   }
 137   return &I->second;
 138 }
 139
 140 void CompilationGraph::insertNode(Tool* V) {
 141   if (NodesMap.count(V->Name()) == 0)
 142     NodesMap[V->Name()] = Node(this, V);
 143 }
 144
 145 int CompilationGraph::insertEdge(const std::string& A, Edge* Edg) {
 146   Node* B = getNode(Edg->ToolName());
 147   if (B == 0)
 148     return 1;
 149
 150   if (A == "root") {
 151     const char** InLangs = B->ToolPtr->InputLanguages();
 152     for (;*InLangs; ++InLangs)
 153       ToolsMap[*InLangs].push_back(IntrusiveRefCntPtr<Edge>(Edg));
 154     NodesMap["root"].AddEdge(Edg);
 155   }
 156   else {
 157     Node* N = getNode(A);
 158     if (N == 0)
 159       return 1;
 160
 161     N->AddEdge(Edg);
 162   }
 163   // Increase the inward edge counter.
 164   B->IncrInEdges();
 165
 166   return 0;
 167 }
 168
 169 // Pass input file through the chain until we bump into a Join node or
 170 // a node that says that it is the last.
 171 int CompilationGraph::PassThroughGraph (const sys::Path& InFile,
 172                                         const Node* StartNode,
 173                                         const InputLanguagesSet& InLangs,
 174                                         const sys::Path& TempDir,
 175                                         const LanguageMap& LangMap) const {
 176   sys::Path In = InFile;
 177   const Node* CurNode = StartNode;
 178
 179   while(true) {
 180     Tool* CurTool = CurNode->ToolPtr.getPtr();
 181
 182     if (CurTool->IsJoin()) {
 183       JoinTool& JT = static_cast<JoinTool&>(*CurTool);
 184       JT.AddToJoinList(In);
 185       break;
 186     }
 187
 188     Action CurAction;
 189     if (int ret = CurTool->GenerateAction(CurAction, In, CurNode->HasChildren(),
 190                                           TempDir, InLangs, LangMap)) {
 191       return ret;
 192     }
 193
 194     if (int ret = CurAction.Execute())
 195       return ret;
 196
 197     if (CurAction.StopCompilation())
 198       return 0;
 199
 200     const Edge* Edg = ChooseEdge(CurNode->OutEdges, InLangs, CurNode->Name());
 201     if (Edg == 0)
 202       return 1;
 203
 204     CurNode = getNode(Edg->ToolName());
 205     if (CurNode == 0)
 206       return 1;
 207
 208     In = CurAction.OutFile();
 209   }
 210
 211   return 0;
 212 }
 213
 214 // Find the head of the toolchain corresponding to the given file.
 215 // Also, insert an input language into InLangs.
 216 const Node* CompilationGraph::
 217 FindToolChain(const sys::Path& In, const std::string* ForceLanguage,
 218               InputLanguagesSet& InLangs, const LanguageMap& LangMap) const {
 219
 220   // Determine the input language.
 221   const std::string* InLang = (ForceLanguage ? ForceLanguage
 222                                : LangMap.GetLanguage(In));
 223   if (InLang == 0)
 224     return 0;
 225   const std::string& InLanguage = *InLang;
 226
 227   // Add the current input language to the input language set.
 228   InLangs.insert(InLanguage);
 229
 230   // Find the toolchain for the input language.
 231   const tools_vector_type* pTV = getToolsVector(InLanguage);
 232   if (pTV == 0)
 233     return 0;
 234
 235   const tools_vector_type& TV = *pTV;
 236   if (TV.empty()) {
 237     PrintError("No toolchain corresponding to language "
 238                + InLanguage + " found");
 239     return 0;
 240   }
 241
 242   const Edge* Edg = ChooseEdge(TV, InLangs);
 243   if (Edg == 0)
 244     return 0;
 245
 246   return getNode(Edg->ToolName());
 247 }
 248
 249 // Helper function used by Build().
 250 // Traverses initial portions of the toolchains (up to the first Join node).
 251 // This function is also responsible for handling the -x option.
 252 int CompilationGraph::BuildInitial (InputLanguagesSet& InLangs,
 253                                     const sys::Path& TempDir,
 254                                     const LanguageMap& LangMap) {
 255   // This is related to -x option handling.
 256   cl::list<std::string>::const_iterator xIter = Languages.begin(),
 257     xBegin = xIter, xEnd = Languages.end();
 258   bool xEmpty = true;
 259   const std::string* xLanguage = 0;
 260   unsigned xPos = 0, xPosNext = 0, filePos = 0;
 261
 262   if (xIter != xEnd) {
 263     xEmpty = false;
 264     xPos = Languages.getPosition(xIter - xBegin);
 265     cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
 266     xPosNext = (xNext == xEnd) ? std::numeric_limits<unsigned>::max()
 267       : Languages.getPosition(xNext - xBegin);
 268     xLanguage = (*xIter == "none") ? 0 : &(*xIter);
 269   }
 270
 271   // For each input file:
 272   for (cl::list<std::string>::const_iterator B = InputFilenames.begin(),
 273          CB = B, E = InputFilenames.end(); B != E; ++B) {
 274     sys::Path In = sys::Path(*B);
 275
 276     // Code for handling the -x option.
 277     // Output: std::string* xLanguage (can be NULL).
 278     if (!xEmpty) {
 279       filePos = InputFilenames.getPosition(B - CB);
 280
 281       if (xPos < filePos) {
 282         if (filePos < xPosNext) {
 283           xLanguage = (*xIter == "none") ? 0 : &(*xIter);
 284         }
 285         else { // filePos >= xPosNext
 286           // Skip xIters while filePos > xPosNext
 287           while (filePos > xPosNext) {
 288             ++xIter;
 289             xPos = xPosNext;
 290
 291             cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
 292             if (xNext == xEnd)
 293               xPosNext = std::numeric_limits<unsigned>::max();
 294             else
 295               xPosNext = Languages.getPosition(xNext - xBegin);
 296             xLanguage = (*xIter == "none") ? 0 : &(*xIter);
 297           }
 298         }
 299       }
 300     }
 301
 302     // Find the toolchain corresponding to this file.
 303     const Node* N = FindToolChain(In, xLanguage, InLangs, LangMap);
 304     if (N == 0)
 305       return 1;
 306     // Pass file through the chain starting at head.
 307     if (int ret = PassThroughGraph(In, N, InLangs, TempDir, LangMap))
 308       return ret;
 309   }
 310
 311   return 0;
 312 }
 313
 314 // Sort the nodes in topological order.
 315 int CompilationGraph::TopologicalSort(std::vector<const Node*>& Out) {
 316   std::queue<const Node*> Q;
 317
 318   Node* Root = getNode("root");
 319   if (Root == 0)
 320     return 1;
 321
 322   Q.push(Root);
 323
 324   while (!Q.empty()) {
 325     const Node* A = Q.front();
 326     Q.pop();
 327     Out.push_back(A);
 328     for (Node::const_iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
 329          EB != EE; ++EB) {
 330       Node* B = getNode((*EB)->ToolName());
 331       if (B == 0)
 332         return 1;
 333
 334       B->DecrInEdges();
 335       if (B->HasNoInEdges())
 336         Q.push(B);
 337     }
 338   }
 339
 340   return 0;
 341 }
 342
 343 namespace {
 344   bool NotJoinNode(const Node* N) {
 345     return N->ToolPtr ? !N->ToolPtr->IsJoin() : true;
 346   }
 347 }
 348
 349 // Call TopologicalSort and filter the resulting list to include
 350 // only Join nodes.
 351 int CompilationGraph::
 352 TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out) {
 353   std::vector<const Node*> TopSorted;
 354   if (int ret = TopologicalSort(TopSorted))
 355     return ret;
 356   std::remove_copy_if(TopSorted.begin(), TopSorted.end(),
 357                       std::back_inserter(Out), NotJoinNode);
 358
 359   return 0;
 360 }
 361
 362 int CompilationGraph::Build (const sys::Path& TempDir,
 363                              const LanguageMap& LangMap) {
 364   InputLanguagesSet InLangs;
 365   bool WasSomeActionGenerated = !InputFilenames.empty();
 366
 367   // Traverse initial parts of the toolchains and fill in InLangs.
 368   if (int ret = BuildInitial(InLangs, TempDir, LangMap))
 369     return ret;
 370
 371   std::vector<const Node*> JTV;
 372   if (int ret = TopologicalSortFilterJoinNodes(JTV))
 373     return ret;
 374
 375   // For all join nodes in topological order:
 376   for (std::vector<const Node*>::iterator B = JTV.begin(), E = JTV.end();
 377        B != E; ++B) {
 378
 379     const Node* CurNode = *B;
 380     JoinTool* JT = &static_cast<JoinTool&>(*CurNode->ToolPtr.getPtr());
 381
 382     // Are there any files in the join list?
 383     if (JT->JoinListEmpty() && !(JT->WorksOnEmpty() && InputFilenames.empty()))
 384       continue;
 385
 386     WasSomeActionGenerated = true;
 387     Action CurAction;
 388     if (int ret = JT->GenerateAction(CurAction, CurNode->HasChildren(),
 389                                      TempDir, InLangs, LangMap)) {
 390       return ret;
 391     }
 392
 393     if (int ret = CurAction.Execute())
 394       return ret;
 395
 396     if (CurAction.StopCompilation())
 397       return 0;
 398
 399     const Edge* Edg = ChooseEdge(CurNode->OutEdges, InLangs, CurNode->Name());
 400     if (Edg == 0)
 401       return 1;
 402
 403     const Node* NextNode = getNode(Edg->ToolName());
 404     if (NextNode == 0)
 405       return 1;
 406
 407     if (int ret = PassThroughGraph(sys::Path(CurAction.OutFile()), NextNode,
 408                                    InLangs, TempDir, LangMap)) {
 409       return ret;
 410     }
 411   }
 412
 413   if (!WasSomeActionGenerated) {
 414     PrintError("no input files");
 415     return 1;
 416   }
 417
 418   return 0;
 419 }
 420
 421 int CompilationGraph::CheckLanguageNames() const {
 422   int ret = 0;
 423
 424   // Check that names for output and input languages on all edges do match.
 425   for (const_nodes_iterator B = this->NodesMap.begin(),
 426          E = this->NodesMap.end(); B != E; ++B) {
 427
 428     const Node & N1 = B->second;
 429     if (N1.ToolPtr) {
 430       for (Node::const_iterator EB = N1.EdgesBegin(), EE = N1.EdgesEnd();
 431            EB != EE; ++EB) {
 432         const Node* N2 = this->getNode((*EB)->ToolName());
 433         if (N2 == 0)
 434           return 1;
 435
 436         if (!N2->ToolPtr) {
 437           ++ret;
 438           errs() << "Error: there is an edge from '" << N1.ToolPtr->Name()
 439                  << "' back to the root!\n\n";
 440           continue;
 441         }
 442
 443         const char** OutLangs = N1.ToolPtr->OutputLanguages();
 444         const char** InLangs = N2->ToolPtr->InputLanguages();
 445         bool eq = false;
 446         const char* OutLang = 0;
 447         for (;*OutLangs; ++OutLangs) {
 448           OutLang = *OutLangs;
 449           for (;*InLangs; ++InLangs) {
 450             if (std::strcmp(OutLang, *InLangs) == 0) {
 451               eq = true;
 452               break;
 453             }
 454           }
 455         }
 456
 457         if (!eq) {
 458           ++ret;
 459           errs() << "Error: Output->input language mismatch in the edge '"
 460                  << N1.ToolPtr->Name() << "' -> '" << N2->ToolPtr->Name()
 461                  << "'!\n"
 462                  << "Expected one of { ";
 463
 464           InLangs = N2->ToolPtr->InputLanguages();
 465           for (;*InLangs; ++InLangs) {
 466             errs() << '\'' << *InLangs << (*(InLangs+1) ? "', " : "'");
 467           }
 468
 469           errs() << " }, but got '" << OutLang << "'!\n\n";
 470         }
 471
 472       }
 473     }
 474   }
 475
 476   return ret;
 477 }
 478
 479 int CompilationGraph::CheckMultipleDefaultEdges() const {
 480   int ret = 0;
 481   InputLanguagesSet Dummy;
 482
 483   // For all nodes, just iterate over the outgoing edges and check if there is
 484   // more than one edge with maximum weight.
 485   for (const_nodes_iterator B = this->NodesMap.begin(),
 486          E = this->NodesMap.end(); B != E; ++B) {
 487     const Node& N = B->second;
 488     int MaxWeight = -1024;
 489
 490     // Ignore the root node.
 491     if (!N.ToolPtr)
 492       continue;
 493
 494     for (Node::const_iterator EB = N.EdgesBegin(), EE = N.EdgesEnd();
 495          EB != EE; ++EB) {
 496       int EdgeWeight = (*EB)->Weight(Dummy);
 497       if (EdgeWeight > MaxWeight) {
 498         MaxWeight = EdgeWeight;
 499       }
 500       else if (EdgeWeight == MaxWeight) {
 501         ++ret;
 502         errs() << "Error: there are multiple maximal edges stemming from the '"
 503                << N.ToolPtr->Name() << "' node!\n\n";
 504         break;
 505       }
 506     }
 507   }
 508
 509   return ret;
 510 }
 511
 512 int CompilationGraph::CheckCycles() {
 513   unsigned deleted = 0;
 514   std::queue<Node*> Q;
 515
 516   Node* Root = getNode("root");
 517   if (Root == 0)
 518     return 1;
 519
 520   Q.push(Root);
 521
 522   // Try to delete all nodes that have no ingoing edges, starting from the
 523   // root. If there are any nodes left after this operation, then we have a
 524   // cycle. This relies on '--check-graph' not performing the topological sort.
 525   while (!Q.empty()) {
 526     Node* A = Q.front();
 527     Q.pop();
 528     ++deleted;
 529
 530     for (Node::iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
 531          EB != EE; ++EB) {
 532       Node* B = getNode((*EB)->ToolName());
 533       if (B == 0)
 534         return 1;
 535
 536       B->DecrInEdges();
 537       if (B->HasNoInEdges())
 538         Q.push(B);
 539     }
 540   }
 541
 542   if (deleted != NodesMap.size()) {
 543     errs() << "Error: there are cycles in the compilation graph!\n"
 544            << "Try inspecting the diagram produced by "
 545            << "'llvmc --view-graph'.\n\n";
 546     return 1;
 547   }
 548
 549   return 0;
 550 }
 551
 552 int CompilationGraph::Check () {
 553   // We try to catch as many errors as we can in one go.
 554   int errs = 0;
 555   int ret = 0;
 556
 557   // Check that output/input language names match.
 558   ret = this->CheckLanguageNames();
 559   if (ret < 0)
 560     return 1;
 561   errs += ret;
 562
 563   // Check for multiple default edges.
 564   ret = this->CheckMultipleDefaultEdges();
 565   if (ret < 0)
 566     return 1;
 567   errs += ret;
 568
 569   // Check for cycles.
 570   ret = this->CheckCycles();
 571   if (ret < 0)
 572     return 1;
 573   errs += ret;
 574
 575   return errs;
 576 }
 577
 578 // Code related to graph visualization.
 579
 580 namespace {
 581
 582 std::string SquashStrArray (const char** StrArr) {
 583   std::string ret;
 584
 585   for (; *StrArr; ++StrArr) {
 586     if (*(StrArr + 1)) {
 587       ret += *StrArr;
 588       ret +=  ", ";
 589     }
 590     else {
 591       ret += *StrArr;
 592     }
 593   }
 594
 595   return ret;
 596 }
 597
 598 } // End anonymous namespace.
 599
 600 namespace llvm {
 601   template <>
 602   struct DOTGraphTraits<llvmc::CompilationGraph*>
 603     : public DefaultDOTGraphTraits
 604   {
 605     DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
 606
 607     template<typename GraphType>
 608     static std::string getNodeLabel(const Node* N, const GraphType&)
 609     {
 610       if (N->ToolPtr)
 611         if (N->ToolPtr->IsJoin())
 612           return N->Name() + "\n (join" +
 613             (N->HasChildren() ? ")"
 614              : std::string(": ") +
 615              SquashStrArray(N->ToolPtr->OutputLanguages()) + ')');
 616         else
 617           return N->Name();
 618       else
 619         return "root";
 620     }
 621
 622     template<typename EdgeIter>
 623     static std::string getEdgeSourceLabel(const Node* N, EdgeIter I) {
 624       if (N->ToolPtr) {
 625         return SquashStrArray(N->ToolPtr->OutputLanguages());
 626       }
 627       else {
 628         return SquashStrArray(I->ToolPtr->InputLanguages());
 629       }
 630     }
 631   };
 632
 633 } // End namespace llvm
 634
 635 int CompilationGraph::writeGraph(const std::string& OutputFilename) {
 636   std::string ErrorInfo;
 637   raw_fd_ostream O(OutputFilename.c_str(), ErrorInfo);
 638
 639   if (ErrorInfo.empty()) {
 640     errs() << "Writing '"<< OutputFilename << "' file...";
 641     llvm::WriteGraph(O, this);
 642     errs() << "done.\n";
 643   }
 644   else {
 645     PrintError("Error opening file '" + OutputFilename + "' for writing!");
 646     return 1;
 647   }
 648
 649   return 0;
 650 }
 651
 652 void CompilationGraph::viewGraph() {
 653   llvm::ViewGraph(this, "compilation-graph");
 654 }