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::list<std::string> Languages;
36 const std::string& LanguageMap::GetLanguage(const sys::Path& File) const {
37 LanguageMap::const_iterator Lang = this->find(File.getSuffix());
38 if (Lang == this->end())
39 throw std::runtime_error("Unknown suffix: " + File.getSuffix());
46 /// ChooseEdge - Return the edge with the maximum weight.
48 const Edge* ChooseEdge(const C& EdgesContainer,
49 const InputLanguagesSet& InLangs,
50 const std::string& NodeName = "root") {
51 const Edge* MaxEdge = 0;
52 unsigned MaxWeight = 0;
53 bool SingleMax = true;
55 for (typename C::const_iterator B = EdgesContainer.begin(),
56 E = EdgesContainer.end(); B != E; ++B) {
57 const Edge* e = B->getPtr();
58 unsigned EW = e->Weight(InLangs);
63 } else if (EW == MaxWeight) {
69 throw std::runtime_error("Node " + NodeName +
70 ": multiple maximal outward edges found!"
71 " Most probably a specification error.");
73 throw std::runtime_error("Node " + NodeName +
74 ": no maximal outward edge found!"
75 " Most probably a specification error.");
81 void Node::AddEdge(Edge* Edg) {
82 // If there already was an edge between two nodes, modify it instead
83 // of adding a new edge.
84 const std::string& ToolName = Edg->ToolName();
85 for (container_type::iterator B = OutEdges.begin(), E = OutEdges.end();
87 if ((*B)->ToolName() == ToolName) {
88 llvm::IntrusiveRefCntPtr<Edge>(Edg).swap(*B);
92 OutEdges.push_back(llvm::IntrusiveRefCntPtr<Edge>(Edg));
95 CompilationGraph::CompilationGraph() {
96 NodesMap["root"] = Node(this);
99 Node& CompilationGraph::getNode(const std::string& ToolName) {
100 nodes_map_type::iterator I = NodesMap.find(ToolName);
101 if (I == NodesMap.end())
102 throw std::runtime_error("Node " + ToolName + " is not in the graph");
106 const Node& CompilationGraph::getNode(const std::string& ToolName) const {
107 nodes_map_type::const_iterator I = NodesMap.find(ToolName);
108 if (I == NodesMap.end())
109 throw std::runtime_error("Node " + ToolName + " is not in the graph!");
113 // Find the tools list corresponding to the given language name.
114 const CompilationGraph::tools_vector_type&
115 CompilationGraph::getToolsVector(const std::string& LangName) const
117 tools_map_type::const_iterator I = ToolsMap.find(LangName);
118 if (I == ToolsMap.end())
119 throw std::runtime_error("No tool corresponding to the language "
120 + LangName + " found");
124 void CompilationGraph::insertNode(Tool* V) {
125 if (NodesMap.count(V->Name()) == 0)
126 NodesMap[V->Name()] = Node(this, V);
129 void CompilationGraph::insertEdge(const std::string& A, Edge* Edg) {
130 Node& B = getNode(Edg->ToolName());
132 const char** InLangs = B.ToolPtr->InputLanguages();
133 for (;*InLangs; ++InLangs)
134 ToolsMap[*InLangs].push_back(IntrusiveRefCntPtr<Edge>(Edg));
135 NodesMap["root"].AddEdge(Edg);
138 Node& N = getNode(A);
141 // Increase the inward edge counter.
145 // Pass input file through the chain until we bump into a Join node or
146 // a node that says that it is the last.
147 void CompilationGraph::PassThroughGraph (const sys::Path& InFile,
148 const Node* StartNode,
149 const InputLanguagesSet& InLangs,
150 const sys::Path& TempDir,
151 const LanguageMap& LangMap) const {
152 sys::Path In = InFile;
153 const Node* CurNode = StartNode;
156 Tool* CurTool = CurNode->ToolPtr.getPtr();
158 if (CurTool->IsJoin()) {
159 JoinTool& JT = dynamic_cast<JoinTool&>(*CurTool);
160 JT.AddToJoinList(In);
164 Action CurAction = CurTool->GenerateAction(In, CurNode->HasChildren(),
165 TempDir, InLangs, LangMap);
167 if (int ret = CurAction.Execute())
168 throw error_code(ret);
170 if (CurAction.StopCompilation())
173 CurNode = &getNode(ChooseEdge(CurNode->OutEdges,
175 CurNode->Name())->ToolName());
176 In = CurAction.OutFile();
180 // Find the head of the toolchain corresponding to the given file.
181 // Also, insert an input language into InLangs.
182 const Node* CompilationGraph::
183 FindToolChain(const sys::Path& In, const std::string* ForceLanguage,
184 InputLanguagesSet& InLangs, const LanguageMap& LangMap) const {
186 // Determine the input language.
187 const std::string& InLanguage =
188 ForceLanguage ? *ForceLanguage : LangMap.GetLanguage(In);
190 // Add the current input language to the input language set.
191 InLangs.insert(InLanguage);
193 // Find the toolchain for the input language.
194 const tools_vector_type& TV = getToolsVector(InLanguage);
196 throw std::runtime_error("No toolchain corresponding to language "
197 + InLanguage + " found");
198 return &getNode(ChooseEdge(TV, InLangs)->ToolName());
201 // Helper function used by Build().
202 // Traverses initial portions of the toolchains (up to the first Join node).
203 // This function is also responsible for handling the -x option.
204 void CompilationGraph::BuildInitial (InputLanguagesSet& InLangs,
205 const sys::Path& TempDir,
206 const LanguageMap& LangMap) {
207 // This is related to -x option handling.
208 cl::list<std::string>::const_iterator xIter = Languages.begin(),
209 xBegin = xIter, xEnd = Languages.end();
211 const std::string* xLanguage = 0;
212 unsigned xPos = 0, xPosNext = 0, filePos = 0;
216 xPos = Languages.getPosition(xIter - xBegin);
217 cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
218 xPosNext = (xNext == xEnd) ? std::numeric_limits<unsigned>::max()
219 : Languages.getPosition(xNext - xBegin);
220 xLanguage = (*xIter == "none") ? 0 : &(*xIter);
223 // For each input file:
224 for (cl::list<std::string>::const_iterator B = InputFilenames.begin(),
225 CB = B, E = InputFilenames.end(); B != E; ++B) {
226 sys::Path In = sys::Path(*B);
228 // Code for handling the -x option.
229 // Output: std::string* xLanguage (can be NULL).
231 filePos = InputFilenames.getPosition(B - CB);
233 if (xPos < filePos) {
234 if (filePos < xPosNext) {
235 xLanguage = (*xIter == "none") ? 0 : &(*xIter);
237 else { // filePos >= xPosNext
238 // Skip xIters while filePos > xPosNext
239 while (filePos > xPosNext) {
243 cl::list<std::string>::const_iterator xNext = llvm::next(xIter);
245 xPosNext = std::numeric_limits<unsigned>::max();
247 xPosNext = Languages.getPosition(xNext - xBegin);
248 xLanguage = (*xIter == "none") ? 0 : &(*xIter);
254 // Find the toolchain corresponding to this file.
255 const Node* N = FindToolChain(In, xLanguage, InLangs, LangMap);
256 // Pass file through the chain starting at head.
257 PassThroughGraph(In, N, InLangs, TempDir, LangMap);
261 // Sort the nodes in topological order.
262 void CompilationGraph::TopologicalSort(std::vector<const Node*>& Out) {
263 std::queue<const Node*> Q;
264 Q.push(&getNode("root"));
267 const Node* A = Q.front();
270 for (Node::const_iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
272 Node* B = &getNode((*EB)->ToolName());
274 if (B->HasNoInEdges())
281 bool NotJoinNode(const Node* N) {
282 return N->ToolPtr ? !N->ToolPtr->IsJoin() : true;
286 // Call TopologicalSort and filter the resulting list to include
288 void CompilationGraph::
289 TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out) {
290 std::vector<const Node*> TopSorted;
291 TopologicalSort(TopSorted);
292 std::remove_copy_if(TopSorted.begin(), TopSorted.end(),
293 std::back_inserter(Out), NotJoinNode);
296 int CompilationGraph::Build (const sys::Path& TempDir,
297 const LanguageMap& LangMap) {
299 InputLanguagesSet InLangs;
301 // Traverse initial parts of the toolchains and fill in InLangs.
302 BuildInitial(InLangs, TempDir, LangMap);
304 std::vector<const Node*> JTV;
305 TopologicalSortFilterJoinNodes(JTV);
307 // For all join nodes in topological order:
308 for (std::vector<const Node*>::iterator B = JTV.begin(), E = JTV.end();
311 const Node* CurNode = *B;
312 JoinTool* JT = &dynamic_cast<JoinTool&>(*CurNode->ToolPtr.getPtr());
314 // Are there any files in the join list?
315 if (JT->JoinListEmpty())
318 Action CurAction = JT->GenerateAction(CurNode->HasChildren(),
319 TempDir, InLangs, LangMap);
321 if (int ret = CurAction.Execute())
322 throw error_code(ret);
324 if (CurAction.StopCompilation())
327 const Node* NextNode = &getNode(ChooseEdge(CurNode->OutEdges, InLangs,
328 CurNode->Name())->ToolName());
329 PassThroughGraph(sys::Path(CurAction.OutFile()), NextNode,
330 InLangs, TempDir, LangMap);
336 // Code related to graph visualization.
340 struct DOTGraphTraits<llvmc::CompilationGraph*>
341 : public DefaultDOTGraphTraits
344 template<typename GraphType>
345 static std::string getNodeLabel(const Node* N, const GraphType&)
348 if (N->ToolPtr->IsJoin())
349 return N->Name() + "\n (join" +
350 (N->HasChildren() ? ")"
351 : std::string(": ") + N->ToolPtr->OutputLanguage() + ')');
358 template<typename EdgeIter>
359 static std::string getEdgeSourceLabel(const Node* N, EdgeIter I) {
361 return N->ToolPtr->OutputLanguage();
364 const char** InLangs = I->ToolPtr->InputLanguages();
367 for (; *InLangs; ++InLangs) {
368 if (*(InLangs + 1)) {
384 void CompilationGraph::writeGraph() {
385 std::ofstream O("compilation-graph.dot");
388 llvm::WriteGraph(this, "compilation-graph");
392 throw std::runtime_error("Error opening file 'compilation-graph.dot'"
397 void CompilationGraph::viewGraph() {
398 llvm::ViewGraph(this, "compilation-graph");