1 //===--- CompilationGraph.h - 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 - definition.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_INCLUDE_COMPILER_DRIVER_COMPILATION_GRAPH_H
15 #define LLVM_INCLUDE_COMPILER_DRIVER_COMPILATION_GRAPH_H
17 #include "llvm/CompilerDriver/Tool.h"
19 #include "llvm/ADT/GraphTraits.h"
20 #include "llvm/ADT/IntrusiveRefCntPtr.h"
21 #include "llvm/ADT/iterator.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/StringMap.h"
24 #include "llvm/ADT/StringSet.h"
25 #include "llvm/System/Path.h"
32 class CompilationGraph;
33 typedef llvm::StringSet<> InputLanguagesSet;
35 /// LanguageMap - Maps from extensions to language names.
36 class LanguageMap : public llvm::StringMap<std::string> {
39 /// GetLanguage - Find the language name corresponding to a given file.
40 const std::string& GetLanguage(const llvm::sys::Path&) const;
43 /// Edge - Represents an edge of the compilation graph.
44 class Edge : public llvm::RefCountedBaseVPTR<Edge> {
46 Edge(const std::string& T) : ToolName_(T) {}
49 const std::string& ToolName() const { return ToolName_; }
50 virtual unsigned Weight(const InputLanguagesSet& InLangs) const = 0;
52 std::string ToolName_;
55 /// SimpleEdge - An edge that has no properties.
56 class SimpleEdge : public Edge {
58 SimpleEdge(const std::string& T) : Edge(T) {}
59 unsigned Weight(const InputLanguagesSet&) const { return 1; }
62 /// Node - A node (vertex) of the compilation graph.
64 // A Node holds a list of the outward edges.
65 typedef llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> container_type;
66 typedef container_type::iterator iterator;
67 typedef container_type::const_iterator const_iterator;
69 Node() : OwningGraph(0), InEdges(0) {}
70 Node(CompilationGraph* G) : OwningGraph(G), InEdges(0) {}
71 Node(CompilationGraph* G, Tool* T) :
72 OwningGraph(G), ToolPtr(T), InEdges(0) {}
74 bool HasChildren() const { return !OutEdges.empty(); }
75 const std::string Name() const
76 { return ToolPtr ? ToolPtr->Name() : "root"; }
79 iterator EdgesBegin() { return OutEdges.begin(); }
80 const_iterator EdgesBegin() const { return OutEdges.begin(); }
81 iterator EdgesEnd() { return OutEdges.end(); }
82 const_iterator EdgesEnd() const { return OutEdges.end(); }
84 /// AddEdge - Add an outward edge. Takes ownership of the provided
86 void AddEdge(Edge* E);
88 // Inward edge counter. Used to implement topological sort.
89 void IncrInEdges() { ++InEdges; }
90 void DecrInEdges() { --InEdges; }
91 bool HasNoInEdges() const { return InEdges == 0; }
93 // Needed to implement NodeChildIterator/GraphTraits
94 CompilationGraph* OwningGraph;
95 // The corresponding Tool.
96 // WARNING: ToolPtr can be NULL (for the root node).
97 llvm::IntrusiveRefCntPtr<Tool> ToolPtr;
99 container_type OutEdges;
100 // Inward edge counter. Updated in
101 // CompilationGraph::insertEdge(). Used for topological sorting.
107 /// CompilationGraph - The compilation graph itself.
108 class CompilationGraph {
109 /// nodes_map_type - The main data structure.
110 typedef llvm::StringMap<Node> nodes_map_type;
111 /// tools_vector_type, tools_map_type - Data structures used to
112 /// map from language names to tools. (We can have several tools
113 /// associated with each language name, hence the need for a
116 llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> tools_vector_type;
117 typedef llvm::StringMap<tools_vector_type> tools_map_type;
119 /// ToolsMap - Map from language names to lists of tool names.
120 tools_map_type ToolsMap;
121 /// NodesMap - Map from tool names to Tool objects.
122 nodes_map_type NodesMap;
126 typedef nodes_map_type::iterator nodes_iterator;
127 typedef nodes_map_type::const_iterator const_nodes_iterator;
131 /// insertNode - Insert a new node into the graph. Takes
132 /// ownership of the object.
133 void insertNode(Tool* T);
135 /// insertEdge - Insert a new edge into the graph. Takes ownership
136 /// of the Edge object.
137 void insertEdge(const std::string& A, Edge* E);
139 /// Build - Build target(s) from the input file set. Command-line
140 /// options are passed implicitly as global variables.
141 int Build(llvm::sys::Path const& TempDir, const LanguageMap& LangMap);
143 /// Check - Check the compilation graph for common errors like
144 /// cycles, input/output language mismatch and multiple default
145 /// edges. Prints error messages and in case it finds any errors.
148 /// getNode - Return a reference to the node correponding to the
149 /// given tool name. Throws std::runtime_error.
150 Node& getNode(const std::string& ToolName);
151 const Node& getNode(const std::string& ToolName) const;
153 /// viewGraph - This function is meant for use from the debugger.
154 /// You can just say 'call G->viewGraph()' and a ghostview window
155 /// should pop up from the program, displaying the compilation
156 /// graph. This depends on there being a 'dot' and 'gv' program
160 /// writeGraph - Write Graphviz .dot source file to the current direcotry.
161 void writeGraph(const std::string& OutputFilename);
163 // GraphTraits support.
164 friend NodesIterator GraphBegin(CompilationGraph*);
165 friend NodesIterator GraphEnd(CompilationGraph*);
170 /// getToolsVector - Return a reference to the list of tool names
171 /// corresponding to the given language name. Throws
172 /// std::runtime_error.
173 const tools_vector_type& getToolsVector(const std::string& LangName) const;
175 /// PassThroughGraph - Pass the input file through the toolchain
176 /// starting at StartNode.
177 void PassThroughGraph (const llvm::sys::Path& In, const Node* StartNode,
178 const InputLanguagesSet& InLangs,
179 const llvm::sys::Path& TempDir,
180 const LanguageMap& LangMap) const;
182 /// FindToolChain - Find head of the toolchain corresponding to
184 const Node* FindToolChain(const llvm::sys::Path& In,
185 const std::string* ForceLanguage,
186 InputLanguagesSet& InLangs,
187 const LanguageMap& LangMap) const;
189 /// BuildInitial - Traverse the initial parts of the toolchains.
190 void BuildInitial(InputLanguagesSet& InLangs,
191 const llvm::sys::Path& TempDir,
192 const LanguageMap& LangMap);
194 /// TopologicalSort - Sort the nodes in topological order.
195 void TopologicalSort(std::vector<const Node*>& Out);
196 /// TopologicalSortFilterJoinNodes - Call TopologicalSort and
197 /// filter the resulting list to include only Join nodes.
198 void TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out);
200 // Functions used to implement Check().
202 /// CheckLanguageNames - Check that output/input language names
203 /// match for all nodes.
204 int CheckLanguageNames() const;
205 /// CheckMultipleDefaultEdges - check that there are no multiple
206 /// default default edges.
207 int CheckMultipleDefaultEdges() const;
208 /// CheckCycles - Check that there are no cycles in the graph.
213 // GraphTraits support code.
215 /// NodesIterator - Auxiliary class needed to implement GraphTraits
216 /// support. Can be generalised to something like value_iterator
217 /// for map-like containers.
218 class NodesIterator : public CompilationGraph::nodes_iterator {
219 typedef CompilationGraph::nodes_iterator super;
220 typedef NodesIterator ThisType;
221 typedef Node* pointer;
222 typedef Node& reference;
225 NodesIterator(super I) : super(I) {}
227 inline reference operator*() const {
228 return super::operator->()->second;
230 inline pointer operator->() const {
231 return &super::operator->()->second;
235 inline NodesIterator GraphBegin(CompilationGraph* G) {
236 return NodesIterator(G->NodesMap.begin());
239 inline NodesIterator GraphEnd(CompilationGraph* G) {
240 return NodesIterator(G->NodesMap.end());
244 /// NodeChildIterator - Another auxiliary class needed by GraphTraits.
245 class NodeChildIterator : public bidirectional_iterator<Node, ptrdiff_t> {
246 typedef NodeChildIterator ThisType;
247 typedef Node::container_type::iterator iterator;
249 CompilationGraph* OwningGraph;
252 typedef Node* pointer;
253 typedef Node& reference;
255 NodeChildIterator(Node* N, iterator I) :
256 OwningGraph(N->OwningGraph), EdgeIter(I) {}
258 const ThisType& operator=(const ThisType& I) {
259 assert(OwningGraph == I.OwningGraph);
260 EdgeIter = I.EdgeIter;
264 inline bool operator==(const ThisType& I) const {
265 assert(OwningGraph == I.OwningGraph);
266 return EdgeIter == I.EdgeIter;
268 inline bool operator!=(const ThisType& I) const {
269 return !this->operator==(I);
272 inline pointer operator*() const {
273 return &OwningGraph->getNode((*EdgeIter)->ToolName());
275 inline pointer operator->() const {
276 return this->operator*();
279 ThisType& operator++() { ++EdgeIter; return *this; } // Preincrement
280 ThisType operator++(int) { // Postincrement
281 ThisType tmp = *this;
286 inline ThisType& operator--() { --EdgeIter; return *this; } // Predecrement
287 inline ThisType operator--(int) { // Postdecrement
288 ThisType tmp = *this;
298 struct GraphTraits<llvmc::CompilationGraph*> {
299 typedef llvmc::CompilationGraph GraphType;
300 typedef llvmc::Node NodeType;
301 typedef llvmc::NodeChildIterator ChildIteratorType;
303 static NodeType* getEntryNode(GraphType* G) {
304 return &G->getNode("root");
307 static ChildIteratorType child_begin(NodeType* N) {
308 return ChildIteratorType(N, N->OutEdges.begin());
310 static ChildIteratorType child_end(NodeType* N) {
311 return ChildIteratorType(N, N->OutEdges.end());
314 typedef llvmc::NodesIterator nodes_iterator;
315 static nodes_iterator nodes_begin(GraphType *G) {
316 return GraphBegin(G);
318 static nodes_iterator nodes_end(GraphType *G) {
325 #endif // LLVM_INCLUDE_COMPILER_DRIVER_COMPILATION_GRAPH_H