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 = File.getSuffix();
  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 = LangMap.GetLanguage(In);
 222   if (InLang == 0)
 223     return 0;
 224   const std::string& InLanguage = (ForceLanguage ? *ForceLanguage : *InLang);
 225
 226   // Add the current input language to the input language set.
 227   InLangs.insert(InLanguage);
 228
 229   // Find the toolchain for the input language.
 230   const tools_vector_type* pTV = getToolsVector(InLanguage);
 231   if (pTV == 0)
 232     return 0;
 233
 234   const tools_vector_type& TV = *pTV;
 235   if (TV.empty()) {
 236     PrintError("No toolchain corresponding to language "
 237                + InLanguage + " found");
 238     return 0;
 239   }
 240
 241   const Edge* Edg = ChooseEdge(TV, InLangs);
 242   if (Edg == 0)
 243     return 0;
 244
 245   return getNode(Edg->ToolName());
 246 }
 247
 248 // Helper function used by Build().
 249 // Traverses initial portions of the toolchains (up to the first Join node).
 250 // This function is also responsible for handling the -x option.
 251 int CompilationGraph::BuildInitial (InputLanguagesSet& InLangs,
 252                                     const sys::Path& TempDir,
 253                                     const LanguageMap& LangMap) {
 254   // This is related to -x option handling.
 255   cl::list<std::string>::const_iterator xIter = Languages.begin(),
 256     xBegin = xIter, xEnd = Languages.end();
 257   bool xEmpty = true;
 258   const std::string* xLanguage = 0;
 259   unsigned xPos = 0, xPosNext = 0, filePos = 0;
 260
 261   if (xIter != xEnd) {
 262     xEmpty = false;
 263     xPos = Languages.getPosition(xIter - xBegin);
 264     cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
 265     xPosNext = (xNext == xEnd) ? std::numeric_limits<unsigned>::max()
 266       : Languages.getPosition(xNext - xBegin);
 267     xLanguage = (*xIter == "none") ? 0 : &(*xIter);
 268   }
 269
 270   // For each input file:
 271   for (cl::list<std::string>::const_iterator B = InputFilenames.begin(),
 272          CB = B, E = InputFilenames.end(); B != E; ++B) {
 273     sys::Path In = sys::Path(*B);
 274
 275     // Code for handling the -x option.
 276     // Output: std::string* xLanguage (can be NULL).
 277     if (!xEmpty) {
 278       filePos = InputFilenames.getPosition(B - CB);
 279
 280       if (xPos < filePos) {
 281         if (filePos < xPosNext) {
 282           xLanguage = (*xIter == "none") ? 0 : &(*xIter);
 283         }
 284         else { // filePos >= xPosNext
 285           // Skip xIters while filePos > xPosNext
 286           while (filePos > xPosNext) {
 287             ++xIter;
 288             xPos = xPosNext;
 289
 290             cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
 291             if (xNext == xEnd)
 292               xPosNext = std::numeric_limits<unsigned>::max();
 293             else
 294               xPosNext = Languages.getPosition(xNext - xBegin);
 295             xLanguage = (*xIter == "none") ? 0 : &(*xIter);
 296           }
 297         }
 298       }
 299     }
 300
 301     // Find the toolchain corresponding to this file.
 302     const Node* N = FindToolChain(In, xLanguage, InLangs, LangMap);
 303     if (N == 0)
 304       return 1;
 305     // Pass file through the chain starting at head.
 306     if (int ret = PassThroughGraph(In, N, InLangs, TempDir, LangMap))
 307       return ret;
 308   }
 309
 310   return 0;
 311 }
 312
 313 // Sort the nodes in topological order.
 314 int CompilationGraph::TopologicalSort(std::vector<const Node*>& Out) {
 315   std::queue<const Node*> Q;
 316
 317   Node* Root = getNode("root");
 318   if (Root == 0)
 319     return 1;
 320
 321   Q.push(Root);
 322
 323   while (!Q.empty()) {
 324     const Node* A = Q.front();
 325     Q.pop();
 326     Out.push_back(A);
 327     for (Node::const_iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
 328          EB != EE; ++EB) {
 329       Node* B = getNode((*EB)->ToolName());
 330       if (B == 0)
 331         return 1;
 332
 333       B->DecrInEdges();
 334       if (B->HasNoInEdges())
 335         Q.push(B);
 336     }
 337   }
 338
 339   return 0;
 340 }
 341
 342 namespace {
 343   bool NotJoinNode(const Node* N) {
 344     return N->ToolPtr ? !N->ToolPtr->IsJoin() : true;
 345   }
 346 }
 347
 348 // Call TopologicalSort and filter the resulting list to include
 349 // only Join nodes.
 350 int CompilationGraph::
 351 TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out) {
 352   std::vector<const Node*> TopSorted;
 353   if (int ret = TopologicalSort(TopSorted))
 354     return ret;
 355   std::remove_copy_if(TopSorted.begin(), TopSorted.end(),
 356                       std::back_inserter(Out), NotJoinNode);
 357
 358   return 0;
 359 }
 360
 361 int CompilationGraph::Build (const sys::Path& TempDir,
 362                              const LanguageMap& LangMap) {
 363   InputLanguagesSet InLangs;
 364   bool WasSomeActionGenerated = !InputFilenames.empty();
 365
 366   // Traverse initial parts of the toolchains and fill in InLangs.
 367   if (int ret = BuildInitial(InLangs, TempDir, LangMap))
 368     return ret;
 369
 370   std::vector<const Node*> JTV;
 371   if (int ret = TopologicalSortFilterJoinNodes(JTV))
 372     return ret;
 373
 374   // For all join nodes in topological order:
 375   for (std::vector<const Node*>::iterator B = JTV.begin(), E = JTV.end();
 376        B != E; ++B) {
 377
 378     const Node* CurNode = *B;
 379     JoinTool* JT = &static_cast<JoinTool&>(*CurNode->ToolPtr.getPtr());
 380
 381     // Are there any files in the join list?
 382     if (JT->JoinListEmpty() && !(JT->WorksOnEmpty() && InputFilenames.empty()))
 383       continue;
 384
 385     WasSomeActionGenerated = true;
 386     Action CurAction;
 387     if (int ret = JT->GenerateAction(CurAction, CurNode->HasChildren(),
 388                                      TempDir, InLangs, LangMap)) {
 389       return ret;
 390     }
 391
 392     if (int ret = CurAction.Execute())
 393       return ret;
 394
 395     if (CurAction.StopCompilation())
 396       return 0;
 397
 398     const Edge* Edg = ChooseEdge(CurNode->OutEdges, InLangs, CurNode->Name());
 399     if (Edg == 0)
 400       return 1;
 401
 402     const Node* NextNode = getNode(Edg->ToolName());
 403     if (NextNode == 0)
 404       return 1;
 405
 406     if (int ret = PassThroughGraph(sys::Path(CurAction.OutFile()), NextNode,
 407                                    InLangs, TempDir, LangMap)) {
 408       return ret;
 409     }
 410   }
 411
 412   if (!WasSomeActionGenerated) {
 413     PrintError("no input files");
 414     return 1;
 415   }
 416
 417   return 0;
 418 }
 419
 420 int CompilationGraph::CheckLanguageNames() const {
 421   int ret = 0;
 422
 423   // Check that names for output and input languages on all edges do match.
 424   for (const_nodes_iterator B = this->NodesMap.begin(),
 425          E = this->NodesMap.end(); B != E; ++B) {
 426
 427     const Node & N1 = B->second;
 428     if (N1.ToolPtr) {
 429       for (Node::const_iterator EB = N1.EdgesBegin(), EE = N1.EdgesEnd();
 430            EB != EE; ++EB) {
 431         const Node* N2 = this->getNode((*EB)->ToolName());
 432         if (N2 == 0)
 433           return 1;
 434
 435         if (!N2->ToolPtr) {
 436           ++ret;
 437           errs() << "Error: there is an edge from '" << N1.ToolPtr->Name()
 438                  << "' back to the root!\n\n";
 439           continue;
 440         }
 441
 442         const char* OutLang = N1.ToolPtr->OutputLanguage();
 443         const char** InLangs = N2->ToolPtr->InputLanguages();
 444         bool eq = false;
 445         for (;*InLangs; ++InLangs) {
 446           if (std::strcmp(OutLang, *InLangs) == 0) {
 447             eq = true;
 448             break;
 449           }
 450         }
 451
 452         if (!eq) {
 453           ++ret;
 454           errs() << "Error: Output->input language mismatch in the edge '"
 455                  << N1.ToolPtr->Name() << "' -> '" << N2->ToolPtr->Name()
 456                  << "'!\n"
 457                  << "Expected one of { ";
 458
 459           InLangs = N2->ToolPtr->InputLanguages();
 460           for (;*InLangs; ++InLangs) {
 461             errs() << '\'' << *InLangs << (*(InLangs+1) ? "', " : "'");
 462           }
 463
 464           errs() << " }, but got '" << OutLang << "'!\n\n";
 465         }
 466
 467       }
 468     }
 469   }
 470
 471   return ret;
 472 }
 473
 474 int CompilationGraph::CheckMultipleDefaultEdges() const {
 475   int ret = 0;
 476   InputLanguagesSet Dummy;
 477
 478   // For all nodes, just iterate over the outgoing edges and check if there is
 479   // more than one edge with maximum weight.
 480   for (const_nodes_iterator B = this->NodesMap.begin(),
 481          E = this->NodesMap.end(); B != E; ++B) {
 482     const Node& N = B->second;
 483     int MaxWeight = 0;
 484
 485     // Ignore the root node.
 486     if (!N.ToolPtr)
 487       continue;
 488
 489     for (Node::const_iterator EB = N.EdgesBegin(), EE = N.EdgesEnd();
 490          EB != EE; ++EB) {
 491       int EdgeWeight = (*EB)->Weight(Dummy);
 492       if (EdgeWeight > MaxWeight) {
 493         MaxWeight = EdgeWeight;
 494       }
 495       else if (EdgeWeight == MaxWeight) {
 496         ++ret;
 497         errs() << "Error: there are multiple maximal edges stemming from the '"
 498                << N.ToolPtr->Name() << "' node!\n\n";
 499         break;
 500       }
 501     }
 502   }
 503
 504   return ret;
 505 }
 506
 507 int CompilationGraph::CheckCycles() {
 508   unsigned deleted = 0;
 509   std::queue<Node*> Q;
 510
 511   Node* Root = getNode("root");
 512   if (Root == 0)
 513     return 1;
 514
 515   Q.push(Root);
 516
 517   // Try to delete all nodes that have no ingoing edges, starting from the
 518   // root. If there are any nodes left after this operation, then we have a
 519   // cycle. This relies on '--check-graph' not performing the topological sort.
 520   while (!Q.empty()) {
 521     Node* A = Q.front();
 522     Q.pop();
 523     ++deleted;
 524
 525     for (Node::iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
 526          EB != EE; ++EB) {
 527       Node* B = getNode((*EB)->ToolName());
 528       if (B == 0)
 529         return 1;
 530
 531       B->DecrInEdges();
 532       if (B->HasNoInEdges())
 533         Q.push(B);
 534     }
 535   }
 536
 537   if (deleted != NodesMap.size()) {
 538     errs() << "Error: there are cycles in the compilation graph!\n"
 539            << "Try inspecting the diagram produced by "
 540            << "'llvmc --view-graph'.\n\n";
 541     return 1;
 542   }
 543
 544   return 0;
 545 }
 546
 547 int CompilationGraph::Check () {
 548   // We try to catch as many errors as we can in one go.
 549   int errs = 0;
 550   int ret = 0;
 551
 552   // Check that output/input language names match.
 553   ret = this->CheckLanguageNames();
 554   if (ret < 0)
 555     return 1;
 556   errs += ret;
 557
 558   // Check for multiple default edges.
 559   ret = this->CheckMultipleDefaultEdges();
 560   if (ret < 0)
 561     return 1;
 562   errs += ret;
 563
 564   // Check for cycles.
 565   ret = this->CheckCycles();
 566   if (ret < 0)
 567     return 1;
 568   errs += ret;
 569
 570   return errs;
 571 }
 572
 573 // Code related to graph visualization.
 574
 575 namespace llvm {
 576   template <>
 577   struct DOTGraphTraits<llvmc::CompilationGraph*>
 578     : public DefaultDOTGraphTraits
 579   {
 580     DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
 581
 582     template<typename GraphType>
 583     static std::string getNodeLabel(const Node* N, const GraphType&)
 584     {
 585       if (N->ToolPtr)
 586         if (N->ToolPtr->IsJoin())
 587           return N->Name() + "\n (join" +
 588             (N->HasChildren() ? ")"
 589              : std::string(": ") + N->ToolPtr->OutputLanguage() + ')');
 590         else
 591           return N->Name();
 592       else
 593         return "root";
 594     }
 595
 596     template<typename EdgeIter>
 597     static std::string getEdgeSourceLabel(const Node* N, EdgeIter I) {
 598       if (N->ToolPtr) {
 599         return N->ToolPtr->OutputLanguage();
 600       }
 601       else {
 602         const char** InLangs = I->ToolPtr->InputLanguages();
 603         std::string ret;
 604
 605         for (; *InLangs; ++InLangs) {
 606           if (*(InLangs + 1)) {
 607             ret += *InLangs;
 608             ret +=  ", ";
 609           }
 610           else {
 611             ret += *InLangs;
 612           }
 613         }
 614
 615         return ret;
 616       }
 617     }
 618   };
 619
 620 }
 621
 622 int CompilationGraph::writeGraph(const std::string& OutputFilename) {
 623   std::string ErrorInfo;
 624   raw_fd_ostream O(OutputFilename.c_str(), ErrorInfo);
 625
 626   if (ErrorInfo.empty()) {
 627     errs() << "Writing '"<< OutputFilename << "' file...";
 628     llvm::WriteGraph(O, this);
 629     errs() << "done.\n";
 630   }
 631   else {
 632     PrintError("Error opening file '" + OutputFilename + "' for writing!");
 633     return 1;
 634   }
 635
 636   return 0;
 637 }
 638
 639 void CompilationGraph::viewGraph() {
 640   llvm::ViewGraph(this, "compilation-graph");
 641 }