LLVM API Documentation

CompilationGraph.cpp

Go to the documentation of this file.
00001 //===--- CompilationGraph.cpp - The LLVM Compiler Driver --------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open
00006 // Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 //  Compilation graph - implementation.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/CompilerDriver/BuiltinOptions.h"
00015 #include "llvm/CompilerDriver/CompilationGraph.h"
00016 #include "llvm/CompilerDriver/Error.h"
00017 
00018 #include "llvm/ADT/STLExtras.h"
00019 #include "llvm/Support/DOTGraphTraits.h"
00020 #include "llvm/Support/GraphWriter.h"
00021 #include "llvm/Support/raw_ostream.h"
00022 
00023 #include <algorithm>
00024 #include <cstring>
00025 #include <iterator>
00026 #include <limits>
00027 #include <queue>
00028 #include <stdexcept>
00029 
00030 using namespace llvm;
00031 using namespace llvmc;
00032 
00033 namespace llvmc {
00034 
00035   const std::string& LanguageMap::GetLanguage(const sys::Path& File) const {
00036     LanguageMap::const_iterator Lang = this->find(File.getSuffix());
00037     if (Lang == this->end())
00038       throw std::runtime_error("Unknown suffix: " + File.getSuffix());
00039     return Lang->second;
00040   }
00041 }
00042 
00043 namespace {
00044 
00045   /// ChooseEdge - Return the edge with the maximum weight.
00046   template <class C>
00047   const Edge* ChooseEdge(const C& EdgesContainer,
00048                          const InputLanguagesSet& InLangs,
00049                          const std::string& NodeName = "root") {
00050     const Edge* MaxEdge = 0;
00051     unsigned MaxWeight = 0;
00052     bool SingleMax = true;
00053 
00054     for (typename C::const_iterator B = EdgesContainer.begin(),
00055            E = EdgesContainer.end(); B != E; ++B) {
00056       const Edge* e = B->getPtr();
00057       unsigned EW = e->Weight(InLangs);
00058       if (EW > MaxWeight) {
00059         MaxEdge = e;
00060         MaxWeight = EW;
00061         SingleMax = true;
00062       } else if (EW == MaxWeight) {
00063         SingleMax = false;
00064       }
00065     }
00066 
00067     if (!SingleMax)
00068       throw std::runtime_error("Node " + NodeName +
00069                                ": multiple maximal outward edges found!"
00070                                " Most probably a specification error.");
00071     if (!MaxEdge)
00072       throw std::runtime_error("Node " + NodeName +
00073                                ": no maximal outward edge found!"
00074                                " Most probably a specification error.");
00075     return MaxEdge;
00076   }
00077 
00078 }
00079 
00080 void Node::AddEdge(Edge* Edg) {
00081   // If there already was an edge between two nodes, modify it instead
00082   // of adding a new edge.
00083   const std::string& ToolName = Edg->ToolName();
00084   for (container_type::iterator B = OutEdges.begin(), E = OutEdges.end();
00085        B != E; ++B) {
00086     if ((*B)->ToolName() == ToolName) {
00087       llvm::IntrusiveRefCntPtr<Edge>(Edg).swap(*B);
00088       return;
00089     }
00090   }
00091   OutEdges.push_back(llvm::IntrusiveRefCntPtr<Edge>(Edg));
00092 }
00093 
00094 CompilationGraph::CompilationGraph() {
00095   NodesMap["root"] = Node(this);
00096 }
00097 
00098 Node& CompilationGraph::getNode(const std::string& ToolName) {
00099   nodes_map_type::iterator I = NodesMap.find(ToolName);
00100   if (I == NodesMap.end())
00101     throw std::runtime_error("Node " + ToolName + " is not in the graph");
00102   return I->second;
00103 }
00104 
00105 const Node& CompilationGraph::getNode(const std::string& ToolName) const {
00106   nodes_map_type::const_iterator I = NodesMap.find(ToolName);
00107   if (I == NodesMap.end())
00108     throw std::runtime_error("Node " + ToolName + " is not in the graph!");
00109   return I->second;
00110 }
00111 
00112 // Find the tools list corresponding to the given language name.
00113 const CompilationGraph::tools_vector_type&
00114 CompilationGraph::getToolsVector(const std::string& LangName) const
00115 {
00116   tools_map_type::const_iterator I = ToolsMap.find(LangName);
00117   if (I == ToolsMap.end())
00118     throw std::runtime_error("No tool corresponding to the language "
00119                              + LangName + " found");
00120   return I->second;
00121 }
00122 
00123 void CompilationGraph::insertNode(Tool* V) {
00124   if (NodesMap.count(V->Name()) == 0)
00125     NodesMap[V->Name()] = Node(this, V);
00126 }
00127 
00128 void CompilationGraph::insertEdge(const std::string& A, Edge* Edg) {
00129   Node& B = getNode(Edg->ToolName());
00130   if (A == "root") {
00131     const char** InLangs = B.ToolPtr->InputLanguages();
00132     for (;*InLangs; ++InLangs)
00133       ToolsMap[*InLangs].push_back(IntrusiveRefCntPtr<Edge>(Edg));
00134     NodesMap["root"].AddEdge(Edg);
00135   }
00136   else {
00137     Node& N = getNode(A);
00138     N.AddEdge(Edg);
00139   }
00140   // Increase the inward edge counter.
00141   B.IncrInEdges();
00142 }
00143 
00144 // Pass input file through the chain until we bump into a Join node or
00145 // a node that says that it is the last.
00146 void CompilationGraph::PassThroughGraph (const sys::Path& InFile,
00147                                          const Node* StartNode,
00148                                          const InputLanguagesSet& InLangs,
00149                                          const sys::Path& TempDir,
00150                                          const LanguageMap& LangMap) const {
00151   sys::Path In = InFile;
00152   const Node* CurNode = StartNode;
00153 
00154   while(true) {
00155     Tool* CurTool = CurNode->ToolPtr.getPtr();
00156 
00157     if (CurTool->IsJoin()) {
00158       JoinTool& JT = dynamic_cast<JoinTool&>(*CurTool);
00159       JT.AddToJoinList(In);
00160       break;
00161     }
00162 
00163     Action CurAction = CurTool->GenerateAction(In, CurNode->HasChildren(),
00164                                                TempDir, InLangs, LangMap);
00165 
00166     if (int ret = CurAction.Execute())
00167       throw error_code(ret);
00168 
00169     if (CurAction.StopCompilation())
00170       return;
00171 
00172     CurNode = &getNode(ChooseEdge(CurNode->OutEdges,
00173                                   InLangs,
00174                                   CurNode->Name())->ToolName());
00175     In = CurAction.OutFile();
00176   }
00177 }
00178 
00179 // Find the head of the toolchain corresponding to the given file.
00180 // Also, insert an input language into InLangs.
00181 const Node* CompilationGraph::
00182 FindToolChain(const sys::Path& In, const std::string* ForceLanguage,
00183               InputLanguagesSet& InLangs, const LanguageMap& LangMap) const {
00184 
00185   // Determine the input language.
00186   const std::string& InLanguage =
00187     ForceLanguage ? *ForceLanguage : LangMap.GetLanguage(In);
00188 
00189   // Add the current input language to the input language set.
00190   InLangs.insert(InLanguage);
00191 
00192   // Find the toolchain for the input language.
00193   const tools_vector_type& TV = getToolsVector(InLanguage);
00194   if (TV.empty())
00195     throw std::runtime_error("No toolchain corresponding to language "
00196                              + InLanguage + " found");
00197   return &getNode(ChooseEdge(TV, InLangs)->ToolName());
00198 }
00199 
00200 // Helper function used by Build().
00201 // Traverses initial portions of the toolchains (up to the first Join node).
00202 // This function is also responsible for handling the -x option.
00203 void CompilationGraph::BuildInitial (InputLanguagesSet& InLangs,
00204                                      const sys::Path& TempDir,
00205                                      const LanguageMap& LangMap) {
00206   // This is related to -x option handling.
00207   cl::list<std::string>::const_iterator xIter = Languages.begin(),
00208     xBegin = xIter, xEnd = Languages.end();
00209   bool xEmpty = true;
00210   const std::string* xLanguage = 0;
00211   unsigned xPos = 0, xPosNext = 0, filePos = 0;
00212 
00213   if (xIter != xEnd) {
00214     xEmpty = false;
00215     xPos = Languages.getPosition(xIter - xBegin);
00216     cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
00217     xPosNext = (xNext == xEnd) ? std::numeric_limits<unsigned>::max()
00218       : Languages.getPosition(xNext - xBegin);
00219     xLanguage = (*xIter == "none") ? 0 : &(*xIter);
00220   }
00221 
00222   // For each input file:
00223   for (cl::list<std::string>::const_iterator B = InputFilenames.begin(),
00224          CB = B, E = InputFilenames.end(); B != E; ++B) {
00225     sys::Path In = sys::Path(*B);
00226 
00227     // Code for handling the -x option.
00228     // Output: std::string* xLanguage (can be NULL).
00229     if (!xEmpty) {
00230       filePos = InputFilenames.getPosition(B - CB);
00231 
00232       if (xPos < filePos) {
00233         if (filePos < xPosNext) {
00234           xLanguage = (*xIter == "none") ? 0 : &(*xIter);
00235         }
00236         else { // filePos >= xPosNext
00237           // Skip xIters while filePos > xPosNext
00238           while (filePos > xPosNext) {
00239             ++xIter;
00240             xPos = xPosNext;
00241 
00242             cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
00243             if (xNext == xEnd)
00244               xPosNext = std::numeric_limits<unsigned>::max();
00245             else
00246               xPosNext = Languages.getPosition(xNext - xBegin);
00247             xLanguage = (*xIter == "none") ? 0 : &(*xIter);
00248           }
00249         }
00250       }
00251     }
00252 
00253     // Find the toolchain corresponding to this file.
00254     const Node* N = FindToolChain(In, xLanguage, InLangs, LangMap);
00255     // Pass file through the chain starting at head.
00256     PassThroughGraph(In, N, InLangs, TempDir, LangMap);
00257   }
00258 }
00259 
00260 // Sort the nodes in topological order.
00261 void CompilationGraph::TopologicalSort(std::vector<const Node*>& Out) {
00262   std::queue<const Node*> Q;
00263   Q.push(&getNode("root"));
00264 
00265   while (!Q.empty()) {
00266     const Node* A = Q.front();
00267     Q.pop();
00268     Out.push_back(A);
00269     for (Node::const_iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
00270          EB != EE; ++EB) {
00271       Node* B = &getNode((*EB)->ToolName());
00272       B->DecrInEdges();
00273       if (B->HasNoInEdges())
00274         Q.push(B);
00275     }
00276   }
00277 }
00278 
00279 namespace {
00280   bool NotJoinNode(const Node* N) {
00281     return N->ToolPtr ? !N->ToolPtr->IsJoin() : true;
00282   }
00283 }
00284 
00285 // Call TopologicalSort and filter the resulting list to include
00286 // only Join nodes.
00287 void CompilationGraph::
00288 TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out) {
00289   std::vector<const Node*> TopSorted;
00290   TopologicalSort(TopSorted);
00291   std::remove_copy_if(TopSorted.begin(), TopSorted.end(),
00292                       std::back_inserter(Out), NotJoinNode);
00293 }
00294 
00295 int CompilationGraph::Build (const sys::Path& TempDir,
00296                              const LanguageMap& LangMap) {
00297 
00298   InputLanguagesSet InLangs;
00299 
00300   // Traverse initial parts of the toolchains and fill in InLangs.
00301   BuildInitial(InLangs, TempDir, LangMap);
00302 
00303   std::vector<const Node*> JTV;
00304   TopologicalSortFilterJoinNodes(JTV);
00305 
00306   // For all join nodes in topological order:
00307   for (std::vector<const Node*>::iterator B = JTV.begin(), E = JTV.end();
00308        B != E; ++B) {
00309 
00310     const Node* CurNode = *B;
00311     JoinTool* JT = &dynamic_cast<JoinTool&>(*CurNode->ToolPtr.getPtr());
00312 
00313     // Are there any files in the join list?
00314     if (JT->JoinListEmpty())
00315       continue;
00316 
00317     Action CurAction = JT->GenerateAction(CurNode->HasChildren(),
00318                                           TempDir, InLangs, LangMap);
00319 
00320     if (int ret = CurAction.Execute())
00321       throw error_code(ret);
00322 
00323     if (CurAction.StopCompilation())
00324       return 0;
00325 
00326     const Node* NextNode = &getNode(ChooseEdge(CurNode->OutEdges, InLangs,
00327                                                CurNode->Name())->ToolName());
00328     PassThroughGraph(sys::Path(CurAction.OutFile()), NextNode,
00329                      InLangs, TempDir, LangMap);
00330   }
00331 
00332   return 0;
00333 }
00334 
00335 int CompilationGraph::CheckLanguageNames() const {
00336   int ret = 0;
00337   // Check that names for output and input languages on all edges do match.
00338   for (const_nodes_iterator B = this->NodesMap.begin(),
00339          E = this->NodesMap.end(); B != E; ++B) {
00340 
00341     const Node & N1 = B->second;
00342     if (N1.ToolPtr) {
00343       for (Node::const_iterator EB = N1.EdgesBegin(), EE = N1.EdgesEnd();
00344            EB != EE; ++EB) {
00345         const Node& N2 = this->getNode((*EB)->ToolName());
00346 
00347         if (!N2.ToolPtr) {
00348           ++ret;
00349           errs() << "Error: there is an edge from '" << N1.ToolPtr->Name()
00350                  << "' back to the root!\n\n";
00351           continue;
00352         }
00353 
00354         const char* OutLang = N1.ToolPtr->OutputLanguage();
00355         const char** InLangs = N2.ToolPtr->InputLanguages();
00356         bool eq = false;
00357         for (;*InLangs; ++InLangs) {
00358           if (std::strcmp(OutLang, *InLangs) == 0) {
00359             eq = true;
00360             break;
00361           }
00362         }
00363 
00364         if (!eq) {
00365           ++ret;
00366           errs() << "Error: Output->input language mismatch in the edge '"
00367                  << N1.ToolPtr->Name() << "' -> '" << N2.ToolPtr->Name()
00368                  << "'!\n"
00369                  << "Expected one of { ";
00370 
00371           InLangs = N2.ToolPtr->InputLanguages();
00372           for (;*InLangs; ++InLangs) {
00373             errs() << '\'' << *InLangs << (*(InLangs+1) ? "', " : "'");
00374           }
00375 
00376           errs() << " }, but got '" << OutLang << "'!\n\n";
00377         }
00378 
00379       }
00380     }
00381   }
00382 
00383   return ret;
00384 }
00385 
00386 int CompilationGraph::CheckMultipleDefaultEdges() const {
00387   int ret = 0;
00388   InputLanguagesSet Dummy;
00389 
00390   // For all nodes, just iterate over the outgoing edges and check if there is
00391   // more than one edge with maximum weight.
00392   for (const_nodes_iterator B = this->NodesMap.begin(),
00393          E = this->NodesMap.end(); B != E; ++B) {
00394     const Node& N = B->second;
00395     unsigned MaxWeight = 0;
00396 
00397     // Ignore the root node.
00398     if (!N.ToolPtr)
00399       continue;
00400 
00401     for (Node::const_iterator EB = N.EdgesBegin(), EE = N.EdgesEnd();
00402          EB != EE; ++EB) {
00403       unsigned EdgeWeight = (*EB)->Weight(Dummy);
00404       if (EdgeWeight > MaxWeight) {
00405         MaxWeight = EdgeWeight;
00406       }
00407       else if (EdgeWeight == MaxWeight) {
00408         ++ret;
00409         errs() << "Error: there are multiple maximal edges stemming from the '"
00410                << N.ToolPtr->Name() << "' node!\n\n";
00411         break;
00412       }
00413     }
00414   }
00415 
00416   return ret;
00417 }
00418 
00419 int CompilationGraph::CheckCycles() {
00420   unsigned deleted = 0;
00421   std::queue<Node*> Q;
00422   Q.push(&getNode("root"));
00423 
00424   // Try to delete all nodes that have no ingoing edges, starting from the
00425   // root. If there are any nodes left after this operation, then we have a
00426   // cycle. This relies on '--check-graph' not performing the topological sort.
00427   while (!Q.empty()) {
00428     Node* A = Q.front();
00429     Q.pop();
00430     ++deleted;
00431 
00432     for (Node::iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
00433          EB != EE; ++EB) {
00434       Node* B = &getNode((*EB)->ToolName());
00435       B->DecrInEdges();
00436       if (B->HasNoInEdges())
00437         Q.push(B);
00438     }
00439   }
00440 
00441   if (deleted != NodesMap.size()) {
00442     errs() << "Error: there are cycles in the compilation graph!\n"
00443            << "Try inspecting the diagram produced by "
00444            << "'llvmc --view-graph'.\n\n";
00445     return 1;
00446   }
00447 
00448   return 0;
00449 }
00450 
00451 int CompilationGraph::Check () {
00452   // We try to catch as many errors as we can in one go.
00453   int ret = 0;
00454 
00455   // Check that output/input language names match.
00456   ret += this->CheckLanguageNames();
00457 
00458   // Check for multiple default edges.
00459   ret += this->CheckMultipleDefaultEdges();
00460 
00461   // Check for cycles.
00462   ret += this->CheckCycles();
00463 
00464   return ret;
00465 }
00466 
00467 // Code related to graph visualization.
00468 
00469 namespace llvm {
00470   template <>
00471   struct DOTGraphTraits<llvmc::CompilationGraph*>
00472     : public DefaultDOTGraphTraits
00473   {
00474 
00475     template<typename GraphType>
00476     static std::string getNodeLabel(const Node* N, const GraphType&,
00477                                     bool ShortNames)
00478     {
00479       if (N->ToolPtr)
00480         if (N->ToolPtr->IsJoin())
00481           return N->Name() + "\n (join" +
00482             (N->HasChildren() ? ")"
00483              : std::string(": ") + N->ToolPtr->OutputLanguage() + ')');
00484         else
00485           return N->Name();
00486       else
00487         return "root";
00488     }
00489 
00490     template<typename EdgeIter>
00491     static std::string getEdgeSourceLabel(const Node* N, EdgeIter I) {
00492       if (N->ToolPtr) {
00493         return N->ToolPtr->OutputLanguage();
00494       }
00495       else {
00496         const char** InLangs = I->ToolPtr->InputLanguages();
00497         std::string ret;
00498 
00499         for (; *InLangs; ++InLangs) {
00500           if (*(InLangs + 1)) {
00501             ret += *InLangs;
00502             ret +=  ", ";
00503           }
00504           else {
00505             ret += *InLangs;
00506           }
00507         }
00508 
00509         return ret;
00510       }
00511     }
00512   };
00513 
00514 }
00515 
00516 void CompilationGraph::writeGraph(const std::string& OutputFilename) {
00517   std::ofstream O(OutputFilename.c_str());
00518 
00519   if (O.good()) {
00520     errs() << "Writing '"<< OutputFilename << "' file...";
00521     llvm::WriteGraph(O, this);
00522     errs() << "done.\n";
00523     O.close();
00524   }
00525   else {
00526     throw std::runtime_error("Error opening file '" + OutputFilename
00527                              + "' for writing!");
00528   }
00529 }
00530 
00531 void CompilationGraph::viewGraph() {
00532   llvm::ViewGraph(this, "compilation-graph");
00533 }