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/SmallSet.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/StringMap.h"
  26 #include "llvm/System/Path.h"
  27
  28 #include <string>
  29
  30 namespace llvmc {
  31
  32   typedef llvm::SmallSet<std::string, 5> InputLanguagesSet;
  33
  34   // An edge of the compilation graph.
  35   class Edge : public llvm::RefCountedBaseVPTR<Edge> {
  36   public:
  37     Edge(const std::string& T) : ToolName_(T) {}
  38     virtual ~Edge() {};
  39
  40     const std::string& ToolName() const { return ToolName_; }
  41     virtual unsigned Weight(const InputLanguagesSet& InLangs) const = 0;
  42   private:
  43     std::string ToolName_;
  44   };
  45
  46   // Edges that have no properties are instances of this class.
  47   class SimpleEdge : public Edge {
  48   public:
  49     SimpleEdge(const std::string& T) : Edge(T) {}
  50     unsigned Weight(const InputLanguagesSet&) const { return 1; }
  51   };
  52
  53   // A node of the compilation graph.
  54   struct Node {
  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;
  59
  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) {}
  64
  65     bool HasChildren() const { return !OutEdges.empty(); }
  66     const std::string Name() const
  67     { return ToolPtr ? ToolPtr->Name() : "root"; }
  68
  69     // Iteration.
  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(); }
  74
  75     // Add an outward edge. Takes ownership of the Edge object.
  76     void AddEdge(Edge* E)
  77     { OutEdges.push_back(llvm::IntrusiveRefCntPtr<Edge>(E)); }
  78
  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; }
  85
  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;
  91     // Links to children.
  92     container_type OutEdges;
  93     // Inward edge counter. Updated in
  94     // CompilationGraph::insertEdge(). Used for topological sorting.
  95     unsigned InEdges;
  96   };
  97
  98   class NodesIterator;
  99
 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.)
 107     typedef
 108     llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> tools_vector_type;
 109     typedef llvm::StringMap<tools_vector_type> tools_map_type;
 110
 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;
 117
 118   public:
 119
 120     CompilationGraph();
 121
 122     // insertVertex - insert a new node into the graph. Takes
 123     // ownership of the object.
 124     void insertNode(Tool* T);
 125
 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);
 129
 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);
 133
 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;
 138
 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
 143     // in your path.
 144     void viewGraph();
 145
 146     // Write a CompilationGraph.dot file.
 147     void writeGraph();
 148
 149     // GraphTraits support
 150     friend NodesIterator GraphBegin(CompilationGraph*);
 151     friend NodesIterator GraphEnd(CompilationGraph*);
 152     friend void PopulateCompilationGraph(CompilationGraph&);
 153
 154   private:
 155     // Helper functions.
 156
 157     // Find out which language corresponds to the suffix of this file.
 158     const std::string& getLanguage(const llvm::sys::Path& File) const;
 159
 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;
 163
 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;
 168
 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;
 173
 174     // Traverse the initial parts of the toolchains.
 175     void BuildInitial(InputLanguagesSet& InLangs,
 176                       const llvm::sys::Path& TempDir);
 177
 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
 181     // only Join nodes.
 182     void TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out);
 183   };
 184
 185   /// GraphTraits support code.
 186
 187   // Auxiliary class needed to implement GraphTraits support.  Can be
 188   // generalised to something like value_iterator for map-like
 189   // containers.
 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;
 195
 196   public:
 197     NodesIterator(super I) : super(I) {}
 198
 199     inline reference operator*() const {
 200       return super::operator->()->second;
 201     }
 202     inline pointer operator->() const {
 203       return &super::operator->()->second;
 204     }
 205   };
 206
 207   inline NodesIterator GraphBegin(CompilationGraph* G) {
 208     return NodesIterator(G->NodesMap.begin());
 209   }
 210
 211   inline NodesIterator GraphEnd(CompilationGraph* G) {
 212     return NodesIterator(G->NodesMap.end());
 213   }
 214
 215
 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;
 220
 221     CompilationGraph* OwningGraph;
 222     iterator EdgeIter;
 223   public:
 224     typedef Node* pointer;
 225     typedef Node& reference;
 226
 227     NodeChildIterator(Node* N, iterator I) :
 228       OwningGraph(N->OwningGraph), EdgeIter(I) {}
 229
 230     const ThisType& operator=(const ThisType& I) {
 231       assert(OwningGraph == I.OwningGraph);
 232       EdgeIter = I.EdgeIter;
 233       return *this;
 234     }
 235
 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; }
 240
 241     inline pointer operator*() const {
 242       return &OwningGraph->getNode((*EdgeIter)->ToolName());
 243     }
 244     inline pointer operator->() const {
 245       return &OwningGraph->getNode((*EdgeIter)->ToolName());
 246     }
 247
 248     ThisType& operator++() { ++EdgeIter; return *this; } // Preincrement
 249     ThisType operator++(int) { // Postincrement
 250       ThisType tmp = *this;
 251       ++*this;
 252       return tmp;
 253     }
 254
 255     inline ThisType& operator--() { --EdgeIter; return *this; }  // Predecrement
 256     inline ThisType operator--(int) { // Postdecrement
 257       ThisType tmp = *this;
 258       --*this;
 259       return tmp;
 260     }
 261
 262   };
 263 }
 264
 265 namespace llvm {
 266   template <>
 267   struct GraphTraits<llvmc::CompilationGraph*> {
 268     typedef llvmc::CompilationGraph GraphType;
 269     typedef llvmc::Node NodeType;
 270     typedef llvmc::NodeChildIterator ChildIteratorType;
 271
 272     static NodeType* getEntryNode(GraphType* G) {
 273       return &G->getNode("root");
 274     }
 275
 276     static ChildIteratorType child_begin(NodeType* N) {
 277       return ChildIteratorType(N, N->OutEdges.begin());
 278     }
 279     static ChildIteratorType child_end(NodeType* N) {
 280       return ChildIteratorType(N, N->OutEdges.end());
 281     }
 282
 283     typedef llvmc::NodesIterator nodes_iterator;
 284     static nodes_iterator nodes_begin(GraphType *G) {
 285       return GraphBegin(G);
 286     }
 287     static nodes_iterator nodes_end(GraphType *G) {
 288       return GraphEnd(G);
 289     }
 290   };
 291
 292 }
 293
 294 #endif // LLVM_TOOLS_LLVMC2_COMPILATION_GRAPH_H