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