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/SmallVector.h"
22 #include "llvm/ADT/StringMap.h"
23 #include "llvm/ADT/StringSet.h"
24 #include "llvm/System/Path.h"
31 class CompilationGraph;
32 typedef llvm::StringSet<> InputLanguagesSet;
34 /// LanguageMap - Maps from extensions to language names.
35 class LanguageMap : public llvm::StringMap<std::string> {
38 /// GetLanguage - Find the language name corresponding to a given file.
39 const std::string* GetLanguage(const llvm::sys::Path&) const;
42 /// Edge - Represents an edge of the compilation graph.
43 class Edge : public llvm::RefCountedBaseVPTR<Edge> {
45 Edge(const std::string& T) : ToolName_(T) {}
48 const std::string& ToolName() const { return ToolName_; }
49 virtual int Weight(const InputLanguagesSet& InLangs) const = 0;
51 std::string ToolName_;
54 /// SimpleEdge - An edge that has no properties.
55 class SimpleEdge : public Edge {
57 SimpleEdge(const std::string& T) : Edge(T) {}
58 int Weight(const InputLanguagesSet&) const { return 1; }
61 /// Node - A node (vertex) of the compilation graph.
63 // A Node holds a list of the outward edges.
64 typedef llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> container_type;
65 typedef container_type::iterator iterator;
66 typedef container_type::const_iterator const_iterator;
68 Node() : OwningGraph(0), InEdges(0) {}
69 Node(CompilationGraph* G) : OwningGraph(G), InEdges(0) {}
70 Node(CompilationGraph* G, Tool* T) :
71 OwningGraph(G), ToolPtr(T), InEdges(0) {}
73 bool HasChildren() const { return !OutEdges.empty(); }
74 const std::string Name() const
75 { return ToolPtr ? ToolPtr->Name() : "root"; }
78 iterator EdgesBegin() { return OutEdges.begin(); }
79 const_iterator EdgesBegin() const { return OutEdges.begin(); }
80 iterator EdgesEnd() { return OutEdges.end(); }
81 const_iterator EdgesEnd() const { return OutEdges.end(); }
83 /// AddEdge - Add an outward edge. Takes ownership of the provided
85 void AddEdge(Edge* E);
87 // Inward edge counter. Used to implement topological sort.
88 void IncrInEdges() { ++InEdges; }
89 void DecrInEdges() { --InEdges; }
90 bool HasNoInEdges() const { return InEdges == 0; }
92 // Needed to implement NodeChildIterator/GraphTraits
93 CompilationGraph* OwningGraph;
94 // The corresponding Tool.
95 // WARNING: ToolPtr can be NULL (for the root node).
96 llvm::IntrusiveRefCntPtr<Tool> ToolPtr;
98 container_type OutEdges;
99 // Inward edge counter. Updated in
100 // CompilationGraph::insertEdge(). Used for topological sorting.
106 /// CompilationGraph - The compilation graph itself.
107 class CompilationGraph {
108 /// nodes_map_type - The main data structure.
109 typedef llvm::StringMap<Node> nodes_map_type;
110 /// tools_vector_type, tools_map_type - Data structures used to
111 /// map from language names to tools. (We can have several tools
112 /// associated with each language name, hence the need for a
115 llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> tools_vector_type;
116 typedef llvm::StringMap<tools_vector_type> tools_map_type;
118 /// ToolsMap - Map from language names to lists of tool names.
119 tools_map_type ToolsMap;
120 /// NodesMap - Map from tool names to Tool objects.
121 nodes_map_type NodesMap;
125 typedef nodes_map_type::iterator nodes_iterator;
126 typedef nodes_map_type::const_iterator const_nodes_iterator;
130 /// insertNode - Insert a new node into the graph. Takes
131 /// ownership of the object.
132 void insertNode(Tool* T);
134 /// insertEdge - Insert a new edge into the graph. Takes ownership
135 /// of the Edge object. Returns non-zero value on error.
136 int insertEdge(const std::string& A, Edge* E);
138 /// Build - Build target(s) from the input file set. Command-line options
139 /// are passed implicitly as global variables. Returns non-zero value on
140 /// error (usually the failed program's exit code).
141 int Build(llvm::sys::Path const& TempDir, const LanguageMap& LangMap);
143 /// Check - Check the compilation graph for common errors like cycles,
144 /// input/output language mismatch and multiple default edges. Prints error
145 /// messages and in case it finds any errors.
148 /// getNode - Return a reference to the node corresponding to the given tool
149 /// name. Returns 0 on 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. You can
154 /// just say 'call G->viewGraph()' and a ghostview window should pop up from
155 /// the program, displaying the compilation graph. This depends on there
156 /// being a 'dot' and 'gv' program in your path.
159 /// writeGraph - Write Graphviz .dot source file to the current direcotry.
160 int writeGraph(const std::string& OutputFilename);
162 // GraphTraits support.
163 friend NodesIterator GraphBegin(CompilationGraph*);
164 friend NodesIterator GraphEnd(CompilationGraph*);
169 /// getToolsVector - Return a reference to the list of tool names
170 /// corresponding to the given language name. Returns 0 on error.
171 const tools_vector_type* getToolsVector(const std::string& LangName) const;
173 /// PassThroughGraph - Pass the input file through the toolchain starting at
175 int PassThroughGraph (const llvm::sys::Path& In, const Node* StartNode,
176 const InputLanguagesSet& InLangs,
177 const llvm::sys::Path& TempDir,
178 const LanguageMap& LangMap) const;
180 /// FindToolChain - Find head of the toolchain corresponding to
182 const Node* FindToolChain(const llvm::sys::Path& In,
183 const std::string* ForceLanguage,
184 InputLanguagesSet& InLangs,
185 const LanguageMap& LangMap) const;
187 /// BuildInitial - Traverse the initial parts of the toolchains. Returns
188 /// non-zero value on error.
189 int BuildInitial(InputLanguagesSet& InLangs,
190 const llvm::sys::Path& TempDir,
191 const LanguageMap& LangMap);
193 /// TopologicalSort - Sort the nodes in topological order. Returns non-zero
195 int TopologicalSort(std::vector<const Node*>& Out);
196 /// TopologicalSortFilterJoinNodes - Call TopologicalSort and filter the
197 /// resulting list to include only Join nodes. Returns non-zero value on
199 int TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out);
201 // Functions used to implement Check().
203 /// CheckLanguageNames - Check that output/input language names match for
204 /// all nodes. Returns non-zero value on error (number of errors
206 int CheckLanguageNames() const;
207 /// CheckMultipleDefaultEdges - check that there are no multiple default
208 /// default edges. Returns non-zero value on error (number of errors
210 int CheckMultipleDefaultEdges() const;
211 /// CheckCycles - Check that there are no cycles in the graph. Returns
212 /// non-zero value on error (number of errors encountered).
217 // GraphTraits support code.
219 /// NodesIterator - Auxiliary class needed to implement GraphTraits
220 /// support. Can be generalised to something like value_iterator
221 /// for map-like containers.
222 class NodesIterator : public CompilationGraph::nodes_iterator {
223 typedef CompilationGraph::nodes_iterator super;
224 typedef NodesIterator ThisType;
225 typedef Node* pointer;
226 typedef Node& reference;
229 NodesIterator(super I) : super(I) {}
231 inline reference operator*() const {
232 return super::operator->()->second;
234 inline pointer operator->() const {
235 return &super::operator->()->second;
239 inline NodesIterator GraphBegin(CompilationGraph* G) {
240 return NodesIterator(G->NodesMap.begin());
243 inline NodesIterator GraphEnd(CompilationGraph* G) {
244 return NodesIterator(G->NodesMap.end());
248 /// NodeChildIterator - Another auxiliary class needed by GraphTraits.
249 class NodeChildIterator : public
250 std::iterator<std::bidirectional_iterator_tag, Node, ptrdiff_t> {
251 typedef NodeChildIterator ThisType;
252 typedef Node::container_type::iterator iterator;
254 CompilationGraph* OwningGraph;
257 typedef Node* pointer;
258 typedef Node& reference;
260 NodeChildIterator(Node* N, iterator I) :
261 OwningGraph(N->OwningGraph), EdgeIter(I) {}
263 const ThisType& operator=(const ThisType& I) {
264 assert(OwningGraph == I.OwningGraph);
265 EdgeIter = I.EdgeIter;
269 inline bool operator==(const ThisType& I) const {
270 assert(OwningGraph == I.OwningGraph);
271 return EdgeIter == I.EdgeIter;
273 inline bool operator!=(const ThisType& I) const {
274 return !this->operator==(I);
277 inline pointer operator*() const {
278 return OwningGraph->getNode((*EdgeIter)->ToolName());
280 inline pointer operator->() const {
281 return this->operator*();
284 ThisType& operator++() { ++EdgeIter; return *this; } // Preincrement
285 ThisType operator++(int) { // Postincrement
286 ThisType tmp = *this;
291 inline ThisType& operator--() { --EdgeIter; return *this; } // Predecrement
292 inline ThisType operator--(int) { // Postdecrement
293 ThisType tmp = *this;
303 struct GraphTraits<llvmc::CompilationGraph*> {
304 typedef llvmc::CompilationGraph GraphType;
305 typedef llvmc::Node NodeType;
306 typedef llvmc::NodeChildIterator ChildIteratorType;
308 static NodeType* getEntryNode(GraphType* G) {
309 return G->getNode("root");
312 static ChildIteratorType child_begin(NodeType* N) {
313 return ChildIteratorType(N, N->OutEdges.begin());
315 static ChildIteratorType child_end(NodeType* N) {
316 return ChildIteratorType(N, N->OutEdges.end());
319 typedef llvmc::NodesIterator nodes_iterator;
320 static nodes_iterator nodes_begin(GraphType *G) {
321 return GraphBegin(G);
323 static nodes_iterator nodes_end(GraphType *G) {
330 #endif // LLVM_INCLUDE_COMPILER_DRIVER_COMPILATION_GRAPH_H