Use Doxygen-style comments.
[oota-llvm.git] / tools / llvmc2 / CompilationGraph.h
1 //===--- CompilationGraph.h - The LLVM Compiler Driver ----------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open
6 // Source License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  Compilation graph - definition.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #ifndef LLVM_TOOLS_LLVMC2_COMPILATION_GRAPH_H
15 #define LLVM_TOOLS_LLVMC2_COMPILATION_GRAPH_H
16
17 #include "AutoGenerated.h"
18 #include "Tool.h"
19
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"
26
27 #include <cassert>
28 #include <string>
29
30 namespace llvmc {
31
32   /// StringSet - A wrapper for StringMap that provides set-like
33   /// functionality.  Only insert() and count() methods are used by my
34   /// code.
35   template <class AllocatorTy = llvm::MallocAllocator>
36   class StringSet : public llvm::StringMap<char, AllocatorTy> {
37     typedef llvm::StringMap<char, AllocatorTy> base;
38   public:
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(), '+'));
45     }
46   };
47   typedef StringSet<> InputLanguagesSet;
48
49   /// Edge - Represents an edge of the compilation graph.
50   class Edge : public llvm::RefCountedBaseVPTR<Edge> {
51   public:
52     Edge(const std::string& T) : ToolName_(T) {}
53     virtual ~Edge() {};
54
55     const std::string& ToolName() const { return ToolName_; }
56     virtual unsigned Weight(const InputLanguagesSet& InLangs) const = 0;
57   private:
58     std::string ToolName_;
59   };
60
61   /// SimpleEdge - An edge that has no properties.
62   class SimpleEdge : public Edge {
63   public:
64     SimpleEdge(const std::string& T) : Edge(T) {}
65     unsigned Weight(const InputLanguagesSet&) const { return 1; }
66   };
67
68   /// Node - A node (vertex) of the compilation graph.
69   struct Node {
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;
74
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) {}
79
80     bool HasChildren() const { return !OutEdges.empty(); }
81     const std::string Name() const
82     { return ToolPtr ? ToolPtr->Name() : "root"; }
83
84     // Iteration.
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(); }
89
90     /// AddEdge - Add an outward edge. Takes ownership of the provided
91     /// Edge object.
92     void AddEdge(Edge* E)
93     { OutEdges.push_back(llvm::IntrusiveRefCntPtr<Edge>(E)); }
94
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; }
101
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.
111     unsigned InEdges;
112   };
113
114   class NodesIterator;
115
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
123     /// vector.)
124     typedef
125     llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> tools_vector_type;
126     typedef llvm::StringMap<tools_vector_type> tools_map_type;
127
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;
134
135   public:
136
137     CompilationGraph();
138
139     /// insertNode - Insert a new node into the graph. Takes
140     /// ownership of the object.
141     void insertNode(Tool* T);
142
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);
146
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);
150
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;
155
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
160     /// in your path.
161     void viewGraph();
162
163     /// writeGraph - Write a compilation-graph.dot file.
164     void writeGraph();
165
166     // GraphTraits support.
167     friend NodesIterator GraphBegin(CompilationGraph*);
168     friend NodesIterator GraphEnd(CompilationGraph*);
169     friend void PopulateCompilationGraph(CompilationGraph&);
170
171   private:
172     // Helper functions.
173
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;
177
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;
182
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;
188
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;
193
194     /// BuildInitial - Traverse the initial parts of the toolchains.
195     void BuildInitial(InputLanguagesSet& InLangs,
196                       const llvm::sys::Path& TempDir);
197
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);
203   };
204
205   // GraphTraits support code.
206
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;
215
216   public:
217     NodesIterator(super I) : super(I) {}
218
219     inline reference operator*() const {
220       return super::operator->()->second;
221     }
222     inline pointer operator->() const {
223       return &super::operator->()->second;
224     }
225   };
226
227   inline NodesIterator GraphBegin(CompilationGraph* G) {
228     return NodesIterator(G->NodesMap.begin());
229   }
230
231   inline NodesIterator GraphEnd(CompilationGraph* G) {
232     return NodesIterator(G->NodesMap.end());
233   }
234
235
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;
240
241     CompilationGraph* OwningGraph;
242     iterator EdgeIter;
243   public:
244     typedef Node* pointer;
245     typedef Node& reference;
246
247     NodeChildIterator(Node* N, iterator I) :
248       OwningGraph(N->OwningGraph), EdgeIter(I) {}
249
250     const ThisType& operator=(const ThisType& I) {
251       assert(OwningGraph == I.OwningGraph);
252       EdgeIter = I.EdgeIter;
253       return *this;
254     }
255
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; }
260
261     inline pointer operator*() const {
262       return &OwningGraph->getNode((*EdgeIter)->ToolName());
263     }
264     inline pointer operator->() const {
265       return &OwningGraph->getNode((*EdgeIter)->ToolName());
266     }
267
268     ThisType& operator++() { ++EdgeIter; return *this; } // Preincrement
269     ThisType operator++(int) { // Postincrement
270       ThisType tmp = *this;
271       ++*this;
272       return tmp;
273     }
274
275     inline ThisType& operator--() { --EdgeIter; return *this; }  // Predecrement
276     inline ThisType operator--(int) { // Postdecrement
277       ThisType tmp = *this;
278       --*this;
279       return tmp;
280     }
281
282   };
283 }
284
285 namespace llvm {
286   template <>
287   struct GraphTraits<llvmc::CompilationGraph*> {
288     typedef llvmc::CompilationGraph GraphType;
289     typedef llvmc::Node NodeType;
290     typedef llvmc::NodeChildIterator ChildIteratorType;
291
292     static NodeType* getEntryNode(GraphType* G) {
293       return &G->getNode("root");
294     }
295
296     static ChildIteratorType child_begin(NodeType* N) {
297       return ChildIteratorType(N, N->OutEdges.begin());
298     }
299     static ChildIteratorType child_end(NodeType* N) {
300       return ChildIteratorType(N, N->OutEdges.end());
301     }
302
303     typedef llvmc::NodesIterator nodes_iterator;
304     static nodes_iterator nodes_begin(GraphType *G) {
305       return GraphBegin(G);
306     }
307     static nodes_iterator nodes_end(GraphType *G) {
308       return GraphEnd(G);
309     }
310   };
311
312 }
313
314 #endif // LLVM_TOOLS_LLVMC2_COMPILATION_GRAPH_H