LLVM API Documentation
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 }