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/SmallVector.h"
24 #include "llvm/ADT/StringMap.h"
25 #include "llvm/System/Path.h"
32 /// StringSet - A wrapper for StringMap that provides set-like
33 /// functionality. Only insert() and count() methods are used by my
35 template <class AllocatorTy = llvm::MallocAllocator>
36 class StringSet : public llvm::StringMap<char, AllocatorTy> {
37 typedef llvm::StringMap<char, AllocatorTy> base;
39 void insert (const std::string& InLang) {
40 assert(!InLang.empty());
41 const char* KeyStart = &InLang[0];
42 const char* KeyEnd = KeyStart + InLang.size();
43 base::insert(llvm::StringMapEntry<char>::
44 Create(KeyStart, KeyEnd, base::getAllocator(), '+'));
47 typedef StringSet<> InputLanguagesSet;
49 /// Edge - Represents an edge of the compilation graph.
50 class Edge : public llvm::RefCountedBaseVPTR<Edge> {
52 Edge(const std::string& T) : ToolName_(T) {}
55 const std::string& ToolName() const { return ToolName_; }
56 virtual unsigned Weight(const InputLanguagesSet& InLangs) const = 0;
58 std::string ToolName_;
61 /// SimpleEdge - An edge that has no properties.
62 class SimpleEdge : public Edge {
64 SimpleEdge(const std::string& T) : Edge(T) {}
65 unsigned Weight(const InputLanguagesSet&) const { return 1; }
68 /// Node - A node (vertex) of the compilation graph.
70 // A Node holds a list of the outward edges.
71 typedef llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> container_type;
72 typedef container_type::iterator iterator;
73 typedef container_type::const_iterator const_iterator;
75 Node() : OwningGraph(0), InEdges(0) {}
76 Node(CompilationGraph* G) : OwningGraph(G), InEdges(0) {}
77 Node(CompilationGraph* G, Tool* T) :
78 OwningGraph(G), ToolPtr(T), InEdges(0) {}
80 bool HasChildren() const { return !OutEdges.empty(); }
81 const std::string Name() const
82 { return ToolPtr ? ToolPtr->Name() : "root"; }
85 iterator EdgesBegin() { return OutEdges.begin(); }
86 const_iterator EdgesBegin() const { return OutEdges.begin(); }
87 iterator EdgesEnd() { return OutEdges.end(); }
88 const_iterator EdgesEnd() const { return OutEdges.end(); }
90 /// AddEdge - Add an outward edge. Takes ownership of the provided
93 { OutEdges.push_back(llvm::IntrusiveRefCntPtr<Edge>(E)); }
95 // Inward edge counter. Used to implement topological sort.
96 // TOTHINK: Move the mutable counter back into Tool classes? Makes
97 // us more const-correct.
98 void IncrInEdges() { ++InEdges; }
99 void DecrInEdges() { --InEdges; }
100 bool HasNoInEdges() const { return InEdges == 0; }
102 // Needed to implement NodeChildIterator/GraphTraits
103 CompilationGraph* OwningGraph;
104 // The corresponding Tool.
105 // WARNING: ToolPtr can be NULL (for the root node).
106 llvm::IntrusiveRefCntPtr<Tool> ToolPtr;
107 // Links to children.
108 container_type OutEdges;
109 // Inward edge counter. Updated in
110 // CompilationGraph::insertEdge(). Used for topological sorting.
116 /// CompilationGraph - The compilation graph itself.
117 class CompilationGraph {
118 /// nodes_map_type - The main data structure.
119 typedef llvm::StringMap<Node> nodes_map_type;
120 /// tools_vector_type, tools_map_type - Data structures used to
121 /// map from language names to tools. (We can have several tools
122 /// associated with each language name, hence the need for a
125 llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> tools_vector_type;
126 typedef llvm::StringMap<tools_vector_type> tools_map_type;
128 /// ExtsToLangs - Map from file extensions to language names.
129 LanguageMap ExtsToLangs;
130 /// ToolsMap - Map from language names to lists of tool names.
131 tools_map_type ToolsMap;
132 /// NodesMap - Map from tool names to Tool objects.
133 nodes_map_type NodesMap;
139 /// insertNode - Insert a new node into the graph. Takes
140 /// ownership of the object.
141 void insertNode(Tool* T);
143 /// insertEdge - Insert a new edge into the graph. Takes ownership
144 /// of the Edge object.
145 void insertEdge(const std::string& A, Edge* E);
147 /// Build - Build target(s) from the input file set. Command-line
148 /// options are passed implicitly as global variables.
149 int Build(llvm::sys::Path const& tempDir);
151 /// getNode -Return a reference to the node correponding to the
152 /// given tool name. Throws std::runtime_error.
153 Node& getNode(const std::string& ToolName);
154 const Node& getNode(const std::string& ToolName) const;
156 /// viewGraph - This function is meant for use from the debugger.
157 /// You can just say 'call G->viewGraph()' and a ghostview window
158 /// should pop up from the program, displaying the compilation
159 /// graph. This depends on there being a 'dot' and 'gv' program
163 /// writeGraph - Write a compilation-graph.dot file.
166 // GraphTraits support.
167 friend NodesIterator GraphBegin(CompilationGraph*);
168 friend NodesIterator GraphEnd(CompilationGraph*);
169 friend void PopulateCompilationGraph(CompilationGraph&);
174 /// getLanguage - Find out which language corresponds to the
175 /// suffix of this file.
176 const std::string& getLanguage(const llvm::sys::Path& File) const;
178 /// getToolsVector - Return a reference to the list of tool names
179 /// corresponding to the given language name. Throws
180 /// std::runtime_error.
181 const tools_vector_type& getToolsVector(const std::string& LangName) const;
183 /// PassThroughGraph - Pass the input file through the toolchain
184 /// starting at StartNode.
185 void PassThroughGraph (const llvm::sys::Path& In, const Node* StartNode,
186 const InputLanguagesSet& InLangs,
187 const llvm::sys::Path& TempDir) const;
189 /// FindToolChain - Find head of the toolchain corresponding to the given file.
190 const Node* FindToolChain(const llvm::sys::Path& In,
191 const std::string* forceLanguage,
192 InputLanguagesSet& InLangs) const;
194 /// BuildInitial - Traverse the initial parts of the toolchains.
195 void BuildInitial(InputLanguagesSet& InLangs,
196 const llvm::sys::Path& TempDir);
198 /// TopologicalSort - Sort the nodes in topological order.
199 void TopologicalSort(std::vector<const Node*>& Out);
200 /// TopologicalSortFilterJoinNodes - Call TopologicalSort and
201 /// filter the resulting list to include only Join nodes.
202 void TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out);
205 // GraphTraits support code.
207 /// NodesIterator - Auxiliary class needed to implement GraphTraits
208 /// support. Can be generalised to something like value_iterator
209 /// for map-like containers.
210 class NodesIterator : public llvm::StringMap<Node>::iterator {
211 typedef llvm::StringMap<Node>::iterator super;
212 typedef NodesIterator ThisType;
213 typedef Node* pointer;
214 typedef Node& reference;
217 NodesIterator(super I) : super(I) {}
219 inline reference operator*() const {
220 return super::operator->()->second;
222 inline pointer operator->() const {
223 return &super::operator->()->second;
227 inline NodesIterator GraphBegin(CompilationGraph* G) {
228 return NodesIterator(G->NodesMap.begin());
231 inline NodesIterator GraphEnd(CompilationGraph* G) {
232 return NodesIterator(G->NodesMap.end());
236 /// NodeChildIterator - Another auxiliary class needed by GraphTraits.
237 class NodeChildIterator : public bidirectional_iterator<Node, ptrdiff_t> {
238 typedef NodeChildIterator ThisType;
239 typedef Node::container_type::iterator iterator;
241 CompilationGraph* OwningGraph;
244 typedef Node* pointer;
245 typedef Node& reference;
247 NodeChildIterator(Node* N, iterator I) :
248 OwningGraph(N->OwningGraph), EdgeIter(I) {}
250 const ThisType& operator=(const ThisType& I) {
251 assert(OwningGraph == I.OwningGraph);
252 EdgeIter = I.EdgeIter;
256 inline bool operator==(const ThisType& I) const
257 { return EdgeIter == I.EdgeIter; }
258 inline bool operator!=(const ThisType& I) const
259 { return EdgeIter != I.EdgeIter; }
261 inline pointer operator*() const {
262 return &OwningGraph->getNode((*EdgeIter)->ToolName());
264 inline pointer operator->() const {
265 return &OwningGraph->getNode((*EdgeIter)->ToolName());
268 ThisType& operator++() { ++EdgeIter; return *this; } // Preincrement
269 ThisType operator++(int) { // Postincrement
270 ThisType tmp = *this;
275 inline ThisType& operator--() { --EdgeIter; return *this; } // Predecrement
276 inline ThisType operator--(int) { // Postdecrement
277 ThisType tmp = *this;
287 struct GraphTraits<llvmc::CompilationGraph*> {
288 typedef llvmc::CompilationGraph GraphType;
289 typedef llvmc::Node NodeType;
290 typedef llvmc::NodeChildIterator ChildIteratorType;
292 static NodeType* getEntryNode(GraphType* G) {
293 return &G->getNode("root");
296 static ChildIteratorType child_begin(NodeType* N) {
297 return ChildIteratorType(N, N->OutEdges.begin());
299 static ChildIteratorType child_end(NodeType* N) {
300 return ChildIteratorType(N, N->OutEdges.end());
303 typedef llvmc::NodesIterator nodes_iterator;
304 static nodes_iterator nodes_begin(GraphType *G) {
305 return GraphBegin(G);
307 static nodes_iterator nodes_end(GraphType *G) {
314 #endif // LLVM_TOOLS_LLVMC2_COMPILATION_GRAPH_H