1 //===--- CompilationGraph.cpp - The LLVM Compiler Driver --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open
6 // Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Compilation graph - implementation.
12 //===----------------------------------------------------------------------===//
15 #include "llvm/CompilerDriver/CompilationGraph.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/Support/CommandLine.h"
19 #include "llvm/Support/DOTGraphTraits.h"
20 #include "llvm/Support/GraphWriter.h"
29 using namespace llvmc;
31 extern cl::list<std::string> InputFilenames;
32 extern cl::opt<std::string> OutputFilename;
33 extern cl::list<std::string> Languages;
37 const std::string& LanguageMap::GetLanguage(const sys::Path& File) const {
38 LanguageMap::const_iterator Lang = this->find(File.getSuffix());
39 if (Lang == this->end())
40 throw std::runtime_error("Unknown suffix: " + File.getSuffix());
47 /// ChooseEdge - Return the edge with the maximum weight.
49 const Edge* ChooseEdge(const C& EdgesContainer,
50 const InputLanguagesSet& InLangs,
51 const std::string& NodeName = "root") {
52 const Edge* MaxEdge = 0;
53 unsigned MaxWeight = 0;
54 bool SingleMax = true;
56 for (typename C::const_iterator B = EdgesContainer.begin(),
57 E = EdgesContainer.end(); B != E; ++B) {
58 const Edge* e = B->getPtr();
59 unsigned EW = e->Weight(InLangs);
64 } else if (EW == MaxWeight) {
70 throw std::runtime_error("Node " + NodeName +
71 ": multiple maximal outward edges found!"
72 " Most probably a specification error.");
74 throw std::runtime_error("Node " + NodeName +
75 ": no maximal outward edge found!"
76 " Most probably a specification error.");
82 void Node::AddEdge(Edge* Edg) {
83 // If there already was an edge between two nodes, modify it instead
84 // of adding a new edge.
85 const std::string& ToolName = Edg->ToolName();
86 for (container_type::iterator B = OutEdges.begin(), E = OutEdges.end();
88 if ((*B)->ToolName() == ToolName) {
89 llvm::IntrusiveRefCntPtr<Edge>(Edg).swap(*B);
93 OutEdges.push_back(llvm::IntrusiveRefCntPtr<Edge>(Edg));
96 CompilationGraph::CompilationGraph() {
97 NodesMap["root"] = Node(this);
100 Node& CompilationGraph::getNode(const std::string& ToolName) {
101 nodes_map_type::iterator I = NodesMap.find(ToolName);
102 if (I == NodesMap.end())
103 throw std::runtime_error("Node " + ToolName + " is not in the graph");
107 const Node& CompilationGraph::getNode(const std::string& ToolName) const {
108 nodes_map_type::const_iterator I = NodesMap.find(ToolName);
109 if (I == NodesMap.end())
110 throw std::runtime_error("Node " + ToolName + " is not in the graph!");
114 // Find the tools list corresponding to the given language name.
115 const CompilationGraph::tools_vector_type&
116 CompilationGraph::getToolsVector(const std::string& LangName) const
118 tools_map_type::const_iterator I = ToolsMap.find(LangName);
119 if (I == ToolsMap.end())
120 throw std::runtime_error("No tool corresponding to the language "
121 + LangName + " found");
125 void CompilationGraph::insertNode(Tool* V) {
126 if (NodesMap.count(V->Name()) == 0)
127 NodesMap[V->Name()] = Node(this, V);
130 void CompilationGraph::insertEdge(const std::string& A, Edge* Edg) {
131 Node& B = getNode(Edg->ToolName());
133 const char** InLangs = B.ToolPtr->InputLanguages();
134 for (;*InLangs; ++InLangs)
135 ToolsMap[*InLangs].push_back(IntrusiveRefCntPtr<Edge>(Edg));
136 NodesMap["root"].AddEdge(Edg);
139 Node& N = getNode(A);
142 // Increase the inward edge counter.
147 sys::Path MakeTempFile(const sys::Path& TempDir, const std::string& BaseName,
148 const std::string& Suffix) {
151 // Make sure we don't end up with path names like '/file.o' if the
153 if (TempDir.empty()) {
158 Out.appendComponent(BaseName);
160 Out.appendSuffix(Suffix);
161 // NOTE: makeUnique always *creates* a unique temporary file,
162 // which is good, since there will be no races. However, some
163 // tools do not like it when the output file already exists, so
164 // they have to be placated with -f or something like that.
165 Out.makeUnique(true, NULL);
170 // Pass input file through the chain until we bump into a Join node or
171 // a node that says that it is the last.
172 void CompilationGraph::PassThroughGraph (const sys::Path& InFile,
173 const Node* StartNode,
174 const InputLanguagesSet& InLangs,
175 const sys::Path& TempDir,
176 const LanguageMap& LangMap) const {
178 sys::Path In = InFile;
179 const Node* CurNode = StartNode;
183 Tool* CurTool = CurNode->ToolPtr.getPtr();
185 if (CurTool->IsJoin()) {
186 JoinTool& JT = dynamic_cast<JoinTool&>(*CurTool);
187 JT.AddToJoinList(In);
191 // Since toolchains do not have to end with a Join node, we should
192 // check if this Node is the last.
193 if (!CurNode->HasChildren() || CurTool->IsLast()) {
194 if (!OutputFilename.empty()) {
195 Out.set(OutputFilename);
198 Out.set(In.getBasename());
199 Out.appendSuffix(CurTool->OutputSuffix());
204 Out = MakeTempFile(TempDir, In.getBasename(), CurTool->OutputSuffix());
207 if (int ret = CurTool->GenerateAction(In, Out, InLangs, LangMap).Execute())
208 throw error_code(ret);
213 CurNode = &getNode(ChooseEdge(CurNode->OutEdges,
215 CurNode->Name())->ToolName());
216 In = Out; Out.clear();
220 // Find the head of the toolchain corresponding to the given file.
221 // Also, insert an input language into InLangs.
222 const Node* CompilationGraph::
223 FindToolChain(const sys::Path& In, const std::string* ForceLanguage,
224 InputLanguagesSet& InLangs, const LanguageMap& LangMap) const {
226 // Determine the input language.
227 const std::string& InLanguage =
228 ForceLanguage ? *ForceLanguage : LangMap.GetLanguage(In);
230 // Add the current input language to the input language set.
231 InLangs.insert(InLanguage);
233 // Find the toolchain for the input language.
234 const tools_vector_type& TV = getToolsVector(InLanguage);
236 throw std::runtime_error("No toolchain corresponding to language "
237 + InLanguage + " found");
238 return &getNode(ChooseEdge(TV, InLangs)->ToolName());
241 // Helper function used by Build().
242 // Traverses initial portions of the toolchains (up to the first Join node).
243 // This function is also responsible for handling the -x option.
244 void CompilationGraph::BuildInitial (InputLanguagesSet& InLangs,
245 const sys::Path& TempDir,
246 const LanguageMap& LangMap) {
247 // This is related to -x option handling.
248 cl::list<std::string>::const_iterator xIter = Languages.begin(),
249 xBegin = xIter, xEnd = Languages.end();
251 const std::string* xLanguage = 0;
252 unsigned xPos = 0, xPosNext = 0, filePos = 0;
256 xPos = Languages.getPosition(xIter - xBegin);
257 cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
258 xPosNext = (xNext == xEnd) ? std::numeric_limits<unsigned>::max()
259 : Languages.getPosition(xNext - xBegin);
260 xLanguage = (*xIter == "none") ? 0 : &(*xIter);
263 // For each input file:
264 for (cl::list<std::string>::const_iterator B = InputFilenames.begin(),
265 CB = B, E = InputFilenames.end(); B != E; ++B) {
266 sys::Path In = sys::Path(*B);
268 // Code for handling the -x option.
269 // Output: std::string* xLanguage (can be NULL).
271 filePos = InputFilenames.getPosition(B - CB);
273 if (xPos < filePos) {
274 if (filePos < xPosNext) {
275 xLanguage = (*xIter == "none") ? 0 : &(*xIter);
277 else { // filePos >= xPosNext
278 // Skip xIters while filePos > xPosNext
279 while (filePos > xPosNext) {
283 cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
285 xPosNext = std::numeric_limits<unsigned>::max();
287 xPosNext = Languages.getPosition(xNext - xBegin);
288 xLanguage = (*xIter == "none") ? 0 : &(*xIter);
294 // Find the toolchain corresponding to this file.
295 const Node* N = FindToolChain(In, xLanguage, InLangs, LangMap);
296 // Pass file through the chain starting at head.
297 PassThroughGraph(In, N, InLangs, TempDir, LangMap);
301 // Sort the nodes in topological order.
302 void CompilationGraph::TopologicalSort(std::vector<const Node*>& Out) {
303 std::queue<const Node*> Q;
304 Q.push(&getNode("root"));
307 const Node* A = Q.front();
310 for (Node::const_iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
312 Node* B = &getNode((*EB)->ToolName());
314 if (B->HasNoInEdges())
321 bool NotJoinNode(const Node* N) {
322 return N->ToolPtr ? !N->ToolPtr->IsJoin() : true;
326 // Call TopologicalSort and filter the resulting list to include
328 void CompilationGraph::
329 TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out) {
330 std::vector<const Node*> TopSorted;
331 TopologicalSort(TopSorted);
332 std::remove_copy_if(TopSorted.begin(), TopSorted.end(),
333 std::back_inserter(Out), NotJoinNode);
336 int CompilationGraph::Build (const sys::Path& TempDir,
337 const LanguageMap& LangMap) {
339 InputLanguagesSet InLangs;
341 // Traverse initial parts of the toolchains and fill in InLangs.
342 BuildInitial(InLangs, TempDir, LangMap);
344 std::vector<const Node*> JTV;
345 TopologicalSortFilterJoinNodes(JTV);
347 // For all join nodes in topological order:
348 for (std::vector<const Node*>::iterator B = JTV.begin(), E = JTV.end();
352 const Node* CurNode = *B;
353 JoinTool* JT = &dynamic_cast<JoinTool&>(*CurNode->ToolPtr.getPtr());
356 // Are there any files in the join list?
357 if (JT->JoinListEmpty())
360 // Is this the last tool in the toolchain?
361 // NOTE: we can process several toolchains in parallel.
362 if (!CurNode->HasChildren() || JT->IsLast()) {
363 if (OutputFilename.empty()) {
365 Out.appendSuffix(JT->OutputSuffix());
368 Out.set(OutputFilename);
372 Out = MakeTempFile(TempDir, "tmp", JT->OutputSuffix());
375 if (int ret = JT->GenerateAction(Out, InLangs, LangMap).Execute())
376 throw error_code(ret);
379 const Node* NextNode =
380 &getNode(ChooseEdge(CurNode->OutEdges, InLangs,
381 CurNode->Name())->ToolName());
382 PassThroughGraph(Out, NextNode, InLangs, TempDir, LangMap);
389 // Code related to graph visualization.
393 struct DOTGraphTraits<llvmc::CompilationGraph*>
394 : public DefaultDOTGraphTraits
397 template<typename GraphType>
398 static std::string getNodeLabel(const Node* N, const GraphType&)
401 if (N->ToolPtr->IsJoin())
402 return N->Name() + "\n (join" +
403 (N->HasChildren() ? ")"
404 : std::string(": ") + N->ToolPtr->OutputLanguage() + ')');
411 template<typename EdgeIter>
412 static std::string getEdgeSourceLabel(const Node* N, EdgeIter I) {
414 return N->ToolPtr->OutputLanguage();
417 const char** InLangs = I->ToolPtr->InputLanguages();
420 for (; *InLangs; ++InLangs) {
421 if (*(InLangs + 1)) {
437 void CompilationGraph::writeGraph() {
438 std::ofstream O("compilation-graph.dot");
441 llvm::WriteGraph(this, "compilation-graph");
445 throw std::runtime_error("Error opening file 'compilation-graph.dot'"
450 void CompilationGraph::viewGraph() {
451 llvm::ViewGraph(this, "compilation-graph");