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_TOOLS_LLVMC2_COMPILATION_GRAPH_H
15 #define LLVM_TOOLS_LLVMC2_COMPILATION_GRAPH_H
17 #include "AutoGenerated.h"
20 #include "llvm/ADT/GraphTraits.h"
21 #include "llvm/ADT/IntrusiveRefCntPtr.h"
22 #include "llvm/ADT/iterator.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/StringMap.h"
25 #include "llvm/ADT/StringSet.h"
26 #include "llvm/System/Path.h"
33 typedef llvm::StringSet<> InputLanguagesSet;
35 /// Edge - Represents an edge of the compilation graph.
36 class Edge : public llvm::RefCountedBaseVPTR<Edge> {
38 Edge(const std::string& T) : ToolName_(T) {}
41 const std::string& ToolName() const { return ToolName_; }
42 virtual unsigned Weight(const InputLanguagesSet& InLangs) const = 0;
44 std::string ToolName_;
47 /// SimpleEdge - An edge that has no properties.
48 class SimpleEdge : public Edge {
50 SimpleEdge(const std::string& T) : Edge(T) {}
51 unsigned Weight(const InputLanguagesSet&) const { return 1; }
54 /// Node - A node (vertex) of the compilation graph.
56 // A Node holds a list of the outward edges.
57 typedef llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> container_type;
58 typedef container_type::iterator iterator;
59 typedef container_type::const_iterator const_iterator;
61 Node() : OwningGraph(0), InEdges(0) {}
62 Node(CompilationGraph* G) : OwningGraph(G), InEdges(0) {}
63 Node(CompilationGraph* G, Tool* T) :
64 OwningGraph(G), ToolPtr(T), InEdges(0) {}
66 bool HasChildren() const { return !OutEdges.empty(); }
67 const std::string Name() const
68 { return ToolPtr ? ToolPtr->Name() : "root"; }
71 iterator EdgesBegin() { return OutEdges.begin(); }
72 const_iterator EdgesBegin() const { return OutEdges.begin(); }
73 iterator EdgesEnd() { return OutEdges.end(); }
74 const_iterator EdgesEnd() const { return OutEdges.end(); }
76 /// AddEdge - Add an outward edge. Takes ownership of the provided
79 { OutEdges.push_back(llvm::IntrusiveRefCntPtr<Edge>(E)); }
81 // Inward edge counter. Used to implement topological sort.
82 void IncrInEdges() { ++InEdges; }
83 void DecrInEdges() { --InEdges; }
84 bool HasNoInEdges() const { return InEdges == 0; }
86 // Needed to implement NodeChildIterator/GraphTraits
87 CompilationGraph* OwningGraph;
88 // The corresponding Tool.
89 // WARNING: ToolPtr can be NULL (for the root node).
90 llvm::IntrusiveRefCntPtr<Tool> ToolPtr;
92 container_type OutEdges;
93 // Inward edge counter. Updated in
94 // CompilationGraph::insertEdge(). Used for topological sorting.
100 /// CompilationGraph - The compilation graph itself.
101 class CompilationGraph {
102 /// nodes_map_type - The main data structure.
103 typedef llvm::StringMap<Node> nodes_map_type;
104 /// tools_vector_type, tools_map_type - Data structures used to
105 /// map from language names to tools. (We can have several tools
106 /// associated with each language name, hence the need for a
109 llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> tools_vector_type;
110 typedef llvm::StringMap<tools_vector_type> tools_map_type;
112 /// ToolsMap - Map from language names to lists of tool names.
113 tools_map_type ToolsMap;
114 /// NodesMap - Map from tool names to Tool objects.
115 nodes_map_type NodesMap;
121 /// insertNode - Insert a new node into the graph. Takes
122 /// ownership of the object.
123 void insertNode(Tool* T);
125 /// insertEdge - Insert a new edge into the graph. Takes ownership
126 /// of the Edge object.
127 void insertEdge(const std::string& A, Edge* E);
129 /// Build - Build target(s) from the input file set. Command-line
130 /// options are passed implicitly as global variables.
131 int Build(llvm::sys::Path const& tempDir);
133 /// getNode - Return a reference to the node correponding to the
134 /// given tool name. Throws std::runtime_error.
135 Node& getNode(const std::string& ToolName);
136 const Node& getNode(const std::string& ToolName) const;
138 /// viewGraph - This function is meant for use from the debugger.
139 /// You can just say 'call G->viewGraph()' and a ghostview window
140 /// should pop up from the program, displaying the compilation
141 /// graph. This depends on there being a 'dot' and 'gv' program
145 /// writeGraph - Write a compilation-graph.dot file.
148 // GraphTraits support.
149 friend NodesIterator GraphBegin(CompilationGraph*);
150 friend NodesIterator GraphEnd(CompilationGraph*);
155 /// getToolsVector - Return a reference to the list of tool names
156 /// corresponding to the given language name. Throws
157 /// std::runtime_error.
158 const tools_vector_type& getToolsVector(const std::string& LangName) const;
160 /// PassThroughGraph - Pass the input file through the toolchain
161 /// starting at StartNode.
162 void PassThroughGraph (const llvm::sys::Path& In, const Node* StartNode,
163 const InputLanguagesSet& InLangs,
164 const llvm::sys::Path& TempDir) const;
166 /// FindToolChain - Find head of the toolchain corresponding to the given file.
167 const Node* FindToolChain(const llvm::sys::Path& In,
168 const std::string* forceLanguage,
169 InputLanguagesSet& InLangs) const;
171 /// BuildInitial - Traverse the initial parts of the toolchains.
172 void BuildInitial(InputLanguagesSet& InLangs,
173 const llvm::sys::Path& TempDir);
175 /// TopologicalSort - Sort the nodes in topological order.
176 void TopologicalSort(std::vector<const Node*>& Out);
177 /// TopologicalSortFilterJoinNodes - Call TopologicalSort and
178 /// filter the resulting list to include only Join nodes.
179 void TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out);
182 // GraphTraits support code.
184 /// NodesIterator - Auxiliary class needed to implement GraphTraits
185 /// support. Can be generalised to something like value_iterator
186 /// for map-like containers.
187 class NodesIterator : public llvm::StringMap<Node>::iterator {
188 typedef llvm::StringMap<Node>::iterator super;
189 typedef NodesIterator ThisType;
190 typedef Node* pointer;
191 typedef Node& reference;
194 NodesIterator(super I) : super(I) {}
196 inline reference operator*() const {
197 return super::operator->()->second;
199 inline pointer operator->() const {
200 return &super::operator->()->second;
204 inline NodesIterator GraphBegin(CompilationGraph* G) {
205 return NodesIterator(G->NodesMap.begin());
208 inline NodesIterator GraphEnd(CompilationGraph* G) {
209 return NodesIterator(G->NodesMap.end());
213 /// NodeChildIterator - Another auxiliary class needed by GraphTraits.
214 class NodeChildIterator : public bidirectional_iterator<Node, ptrdiff_t> {
215 typedef NodeChildIterator ThisType;
216 typedef Node::container_type::iterator iterator;
218 CompilationGraph* OwningGraph;
221 typedef Node* pointer;
222 typedef Node& reference;
224 NodeChildIterator(Node* N, iterator I) :
225 OwningGraph(N->OwningGraph), EdgeIter(I) {}
227 const ThisType& operator=(const ThisType& I) {
228 assert(OwningGraph == I.OwningGraph);
229 EdgeIter = I.EdgeIter;
233 inline bool operator==(const ThisType& I) const
234 { return EdgeIter == I.EdgeIter; }
235 inline bool operator!=(const ThisType& I) const
236 { return EdgeIter != I.EdgeIter; }
238 inline pointer operator*() const {
239 return &OwningGraph->getNode((*EdgeIter)->ToolName());
241 inline pointer operator->() const {
242 return &OwningGraph->getNode((*EdgeIter)->ToolName());
245 ThisType& operator++() { ++EdgeIter; return *this; } // Preincrement
246 ThisType operator++(int) { // Postincrement
247 ThisType tmp = *this;
252 inline ThisType& operator--() { --EdgeIter; return *this; } // Predecrement
253 inline ThisType operator--(int) { // Postdecrement
254 ThisType tmp = *this;
264 struct GraphTraits<llvmc::CompilationGraph*> {
265 typedef llvmc::CompilationGraph GraphType;
266 typedef llvmc::Node NodeType;
267 typedef llvmc::NodeChildIterator ChildIteratorType;
269 static NodeType* getEntryNode(GraphType* G) {
270 return &G->getNode("root");
273 static ChildIteratorType child_begin(NodeType* N) {
274 return ChildIteratorType(N, N->OutEdges.begin());
276 static ChildIteratorType child_end(NodeType* N) {
277 return ChildIteratorType(N, N->OutEdges.end());
280 typedef llvmc::NodesIterator nodes_iterator;
281 static nodes_iterator nodes_begin(GraphType *G) {
282 return GraphBegin(G);
284 static nodes_iterator nodes_end(GraphType *G) {
291 #endif // LLVM_TOOLS_LLVMC2_COMPILATION_GRAPH_H