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"
23 #include "llvm/ADT/SmallSet.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/StringMap.h"
26 #include "llvm/System/Path.h"
32 typedef llvm::SmallSet<std::string, 5> InputLanguagesSet;
34 // An edge of the compilation graph.
35 class Edge : public llvm::RefCountedBaseVPTR<Edge> {
37 Edge(const std::string& T) : ToolName_(T) {}
40 const std::string& ToolName() const { return ToolName_; }
41 virtual unsigned Weight(const InputLanguagesSet& InLangs) const = 0;
43 std::string ToolName_;
46 // Edges that have no properties are instances of this class.
47 class SimpleEdge : public Edge {
49 SimpleEdge(const std::string& T) : Edge(T) {}
50 unsigned Weight(const InputLanguagesSet&) const { return 1; }
53 // A node of the compilation graph.
55 // A Node holds a list of the outward edges.
56 typedef llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> container_type;
57 typedef container_type::iterator iterator;
58 typedef container_type::const_iterator const_iterator;
60 Node() : OwningGraph(0), InEdges(0) {}
61 Node(CompilationGraph* G) : OwningGraph(G), InEdges(0) {}
62 Node(CompilationGraph* G, Tool* T) :
63 OwningGraph(G), ToolPtr(T), InEdges(0) {}
65 bool HasChildren() const { return !OutEdges.empty(); }
66 const std::string Name() const
67 { return ToolPtr ? ToolPtr->Name() : "root"; }
70 iterator EdgesBegin() { return OutEdges.begin(); }
71 const_iterator EdgesBegin() const { return OutEdges.begin(); }
72 iterator EdgesEnd() { return OutEdges.end(); }
73 const_iterator EdgesEnd() const { return OutEdges.end(); }
75 // Add an outward edge. Takes ownership of the Edge object.
77 { OutEdges.push_back(llvm::IntrusiveRefCntPtr<Edge>(E)); }
79 // Inward edge counter. Used to implement topological sort.
80 // TOTHINK: Move the mutable counter back into Tool classes? Makes
81 // us more const-correct.
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 // The compilation graph itself.
101 class CompilationGraph {
102 // Main data structure.
103 typedef llvm::StringMap<Node> nodes_map_type;
104 // These are used to map from language names to tools. (We can
105 // have several tools associated with each language name, hence
106 // the need for a vector of Edges.)
108 llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> tools_vector_type;
109 typedef llvm::StringMap<tools_vector_type> tools_map_type;
111 // Map from file extensions to language names.
112 LanguageMap ExtsToLangs;
113 // Map from language names to lists of tool names.
114 tools_map_type ToolsMap;
115 // Map from tool names to Tool objects.
116 nodes_map_type NodesMap;
122 // insertVertex - insert a new node into the graph. Takes
123 // ownership of the object.
124 void insertNode(Tool* T);
126 // insertEdge - Insert a new edge into the graph. Takes ownership
127 // of the Edge object.
128 void insertEdge(const std::string& A, Edge* E);
130 // Build - Build target(s) from the input file set. Command-line
131 // options are passed implicitly as global variables.
132 int Build(llvm::sys::Path const& tempDir);
134 // Return a reference to the node correponding to the given tool
135 // name. Throws std::runtime_error.
136 Node& getNode(const std::string& ToolName);
137 const Node& getNode(const std::string& ToolName) const;
139 // viewGraph - This function is meant for use from the debugger.
140 // You can just say 'call G->viewGraph()' and a ghostview window
141 // should pop up from the program, displaying the compilation
142 // graph. This depends on there being a 'dot' and 'gv' program
146 // Write a CompilationGraph.dot file.
149 // GraphTraits support
150 friend NodesIterator GraphBegin(CompilationGraph*);
151 friend NodesIterator GraphEnd(CompilationGraph*);
152 friend void PopulateCompilationGraph(CompilationGraph&);
157 // Find out which language corresponds to the suffix of this file.
158 const std::string& getLanguage(const llvm::sys::Path& File) const;
160 // Return a reference to the list of tool names corresponding to
161 // the given language name. Throws std::runtime_error.
162 const tools_vector_type& getToolsVector(const std::string& LangName) const;
164 // Pass the input file through the toolchain starting at StartNode.
165 void PassThroughGraph (const llvm::sys::Path& In, const Node* StartNode,
166 const InputLanguagesSet& InLangs,
167 const llvm::sys::Path& TempDir) const;
169 // Find head of the toolchain corresponding to the given file.
170 const Node* FindToolChain(const llvm::sys::Path& In,
171 const std::string* forceLanguage,
172 InputLanguagesSet& InLangs) const;
174 // Traverse the initial parts of the toolchains.
175 void BuildInitial(InputLanguagesSet& InLangs,
176 const llvm::sys::Path& TempDir);
178 // Sort the nodes in topological order.
179 void TopologicalSort(std::vector<const Node*>& Out);
180 // Call TopologicalSort and filter the resulting list to include
182 void TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out);
185 /// GraphTraits support code.
187 // Auxiliary class needed to implement GraphTraits support. Can be
188 // generalised to something like value_iterator for map-like
190 class NodesIterator : public llvm::StringMap<Node>::iterator {
191 typedef llvm::StringMap<Node>::iterator super;
192 typedef NodesIterator ThisType;
193 typedef Node* pointer;
194 typedef Node& reference;
197 NodesIterator(super I) : super(I) {}
199 inline reference operator*() const {
200 return super::operator->()->second;
202 inline pointer operator->() const {
203 return &super::operator->()->second;
207 inline NodesIterator GraphBegin(CompilationGraph* G) {
208 return NodesIterator(G->NodesMap.begin());
211 inline NodesIterator GraphEnd(CompilationGraph* G) {
212 return NodesIterator(G->NodesMap.end());
216 // Another auxiliary class needed by GraphTraits.
217 class NodeChildIterator : public bidirectional_iterator<Node, ptrdiff_t> {
218 typedef NodeChildIterator ThisType;
219 typedef Node::container_type::iterator iterator;
221 CompilationGraph* OwningGraph;
224 typedef Node* pointer;
225 typedef Node& reference;
227 NodeChildIterator(Node* N, iterator I) :
228 OwningGraph(N->OwningGraph), EdgeIter(I) {}
230 const ThisType& operator=(const ThisType& I) {
231 assert(OwningGraph == I.OwningGraph);
232 EdgeIter = I.EdgeIter;
236 inline bool operator==(const ThisType& I) const
237 { return EdgeIter == I.EdgeIter; }
238 inline bool operator!=(const ThisType& I) const
239 { return EdgeIter != I.EdgeIter; }
241 inline pointer operator*() const {
242 return &OwningGraph->getNode((*EdgeIter)->ToolName());
244 inline pointer operator->() const {
245 return &OwningGraph->getNode((*EdgeIter)->ToolName());
248 ThisType& operator++() { ++EdgeIter; return *this; } // Preincrement
249 ThisType operator++(int) { // Postincrement
250 ThisType tmp = *this;
255 inline ThisType& operator--() { --EdgeIter; return *this; } // Predecrement
256 inline ThisType operator--(int) { // Postdecrement
257 ThisType tmp = *this;
267 struct GraphTraits<llvmc::CompilationGraph*> {
268 typedef llvmc::CompilationGraph GraphType;
269 typedef llvmc::Node NodeType;
270 typedef llvmc::NodeChildIterator ChildIteratorType;
272 static NodeType* getEntryNode(GraphType* G) {
273 return &G->getNode("root");
276 static ChildIteratorType child_begin(NodeType* N) {
277 return ChildIteratorType(N, N->OutEdges.begin());
279 static ChildIteratorType child_end(NodeType* N) {
280 return ChildIteratorType(N, N->OutEdges.end());
283 typedef llvmc::NodesIterator nodes_iterator;
284 static nodes_iterator nodes_begin(GraphType *G) {
285 return GraphBegin(G);
287 static nodes_iterator nodes_end(GraphType *G) {
294 #endif // LLVM_TOOLS_LLVMC2_COMPILATION_GRAPH_H