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