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 <string>
  28
  29 namespace llvmc {
  30
  31   // An edge of the compilation graph.
  32   class Edge : public llvm::RefCountedBaseVPTR<Edge> {
  33   public:
  34     Edge(const std::string& T) : ToolName_(T) {}
  35     virtual ~Edge() {};
  36
  37     const std::string& ToolName() const { return ToolName_; }
  38     virtual bool isEnabled() const = 0;
  39     virtual bool isDefault() const = 0;
  40   private:
  41     std::string ToolName_;
  42   };
  43
  44   // Edges that have no properties are instances of this class.
  45   class SimpleEdge : public Edge {
  46   public:
  47     SimpleEdge(const std::string& T) : Edge(T) {}
  48     bool isEnabled() const { return false;}
  49     bool isDefault() const { return true;}
  50   };
  51
  52   // A node of the compilation graph.
  53   struct Node {
  54     // A Node holds a list of the outward edges.
  55     typedef llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> container_type;
  56     typedef container_type::iterator iterator;
  57     typedef container_type::const_iterator const_iterator;
  58
  59     Node() : OwningGraph(0), InEdges(0) {}
  60     Node(CompilationGraph* G) : OwningGraph(G), InEdges(0) {}
  61     Node(CompilationGraph* G, Tool* T) :
  62       OwningGraph(G), ToolPtr(T), InEdges(0) {}
  63
  64     bool HasChildren() const { return !OutEdges.empty(); }
  65     const std::string Name() const
  66     { return ToolPtr ? ToolPtr->Name() : "root"; }
  67
  68     // Iteration.
  69     iterator EdgesBegin() { return OutEdges.begin(); }
  70     const_iterator EdgesBegin() const { return OutEdges.begin(); }
  71     iterator EdgesEnd() { return OutEdges.end(); }
  72     const_iterator EdgesEnd() const { return OutEdges.end(); }
  73
  74     // Add an outward edge. Takes ownership of the Edge object.
  75     void AddEdge(Edge* E)
  76     { OutEdges.push_back(llvm::IntrusiveRefCntPtr<Edge>(E)); }
  77
  78     // Inward edge counter. Used to implement topological sort.
  79     // TOTHINK: Move the mutable counter back into Tool classes? Makes
  80     // us more const-correct.
  81     void IncrInEdges() { ++InEdges; }
  82     void DecrInEdges() { --InEdges; }
  83     bool HasNoInEdges() const { return InEdges == 0; }
  84
  85     // Needed to implement NodeChildIterator/GraphTraits
  86     CompilationGraph* OwningGraph;
  87     // The corresponding Tool.
  88     // WARNING: ToolPtr can be NULL (for the root node).
  89     llvm::IntrusiveRefCntPtr<Tool> ToolPtr;
  90     // Links to children.
  91     container_type OutEdges;
  92     // Inward edge counter. Updated in
  93     // CompilationGraph::insertEdge(). Used for topological sorting.
  94     unsigned InEdges;
  95   };
  96
  97   class NodesIterator;
  98
  99   // The compilation graph itself.
 100   class CompilationGraph {
 101     // Main data structure.
 102     typedef llvm::StringMap<Node> nodes_map_type;
 103     // These are used to map from language names to tools. (We can
 104     // have several tools associated with each language name, hence
 105     // the need for a vector of Edges.)
 106     typedef
 107     llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> tools_vector_type;
 108     typedef llvm::StringMap<tools_vector_type> tools_map_type;
 109
 110     // Map from file extensions to language names.
 111     LanguageMap ExtsToLangs;
 112     // Map from language names to lists of tool names.
 113     tools_map_type ToolsMap;
 114     // Map from tool names to Tool objects.
 115     nodes_map_type NodesMap;
 116
 117   public:
 118
 119     CompilationGraph();
 120
 121     // insertVertex - insert a new node into the graph. Takes
 122     // ownership of the object.
 123     void insertNode(Tool* T);
 124
 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);
 128
 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);
 132
 133     // Return a reference to the node correponding to the given tool
 134     // name. Throws std::runtime_error.
 135     Node& getNode(const std::string& ToolName);
 136     const Node& getNode(const std::string& ToolName) const;
 137
 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
 142     // in your path.
 143     void viewGraph();
 144
 145     // Write a CompilationGraph.dot file.
 146     void writeGraph();
 147
 148     // GraphTraits support
 149     friend NodesIterator GraphBegin(CompilationGraph*);
 150     friend NodesIterator GraphEnd(CompilationGraph*);
 151     friend void PopulateCompilationGraph(CompilationGraph&);
 152
 153   private:
 154     // Helper functions.
 155
 156     // Find out which language corresponds to the suffix of this file.
 157     const std::string& getLanguage(const llvm::sys::Path& File) const;
 158
 159     // Return a reference to the list of tool names corresponding to
 160     // the given language name. Throws std::runtime_error.
 161     const tools_vector_type& getToolsVector(const std::string& LangName) const;
 162
 163     // Pass the input file through the toolchain.
 164     void PassThroughGraph (const llvm::sys::Path& In, const Node* StartNode,
 165                            const llvm::sys::Path& TempDir) const;
 166
 167     // Find head of the toolchain corresponding to the given file.
 168     const Node* FindToolChain(const llvm::sys::Path& In) const;
 169
 170     // Sort the nodes in topological order.
 171     void TopologicalSort(std::vector<const Node*>& Out);
 172     // Call TopologicalSort and filter the resulting list to include
 173     // only Join nodes.
 174     void TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out);
 175   };
 176
 177   /// GraphTraits support code.
 178
 179   // Auxiliary class needed to implement GraphTraits support.  Can be
 180   // generalised to something like value_iterator for map-like
 181   // containers.
 182   class NodesIterator : public llvm::StringMap<Node>::iterator {
 183     typedef llvm::StringMap<Node>::iterator super;
 184     typedef NodesIterator ThisType;
 185     typedef Node* pointer;
 186     typedef Node& reference;
 187
 188   public:
 189     NodesIterator(super I) : super(I) {}
 190
 191     inline reference operator*() const {
 192       return super::operator->()->second;
 193     }
 194     inline pointer operator->() const {
 195       return &super::operator->()->second;
 196     }
 197   };
 198
 199   inline NodesIterator GraphBegin(CompilationGraph* G) {
 200     return NodesIterator(G->NodesMap.begin());
 201   }
 202
 203   inline NodesIterator GraphEnd(CompilationGraph* G) {
 204     return NodesIterator(G->NodesMap.end());
 205   }
 206
 207
 208   // Another auxiliary class needed by GraphTraits.
 209   class NodeChildIterator : public bidirectional_iterator<Node, ptrdiff_t> {
 210     typedef NodeChildIterator ThisType;
 211     typedef Node::container_type::iterator iterator;
 212
 213     CompilationGraph* OwningGraph;
 214     iterator EdgeIter;
 215   public:
 216     typedef Node* pointer;
 217     typedef Node& reference;
 218
 219     NodeChildIterator(Node* N, iterator I) :
 220       OwningGraph(N->OwningGraph), EdgeIter(I) {}
 221
 222     const ThisType& operator=(const ThisType& I) {
 223       assert(OwningGraph == I.OwningGraph);
 224       EdgeIter = I.EdgeIter;
 225       return *this;
 226     }
 227
 228     inline bool operator==(const ThisType& I) const
 229     { return EdgeIter == I.EdgeIter; }
 230     inline bool operator!=(const ThisType& I) const
 231     { return EdgeIter != I.EdgeIter; }
 232
 233     inline pointer operator*() const {
 234       return &OwningGraph->getNode((*EdgeIter)->ToolName());
 235     }
 236     inline pointer operator->() const {
 237       return &OwningGraph->getNode((*EdgeIter)->ToolName());
 238     }
 239
 240     ThisType& operator++() { ++EdgeIter; return *this; } // Preincrement
 241     ThisType operator++(int) { // Postincrement
 242       ThisType tmp = *this;
 243       ++*this;
 244       return tmp;
 245     }
 246
 247     inline ThisType& operator--() { --EdgeIter; return *this; }  // Predecrement
 248     inline ThisType operator--(int) { // Postdecrement
 249       ThisType tmp = *this;
 250       --*this;
 251       return tmp;
 252     }
 253
 254   };
 255 }
 256
 257 namespace llvm {
 258   template <>
 259   struct GraphTraits<llvmc::CompilationGraph*> {
 260     typedef llvmc::CompilationGraph GraphType;
 261     typedef llvmc::Node NodeType;
 262     typedef llvmc::NodeChildIterator ChildIteratorType;
 263
 264     static NodeType* getEntryNode(GraphType* G) {
 265       return &G->getNode("root");
 266     }
 267
 268     static ChildIteratorType child_begin(NodeType* N) {
 269       return ChildIteratorType(N, N->OutEdges.begin());
 270     }
 271     static ChildIteratorType child_end(NodeType* N) {
 272       return ChildIteratorType(N, N->OutEdges.end());
 273     }
 274
 275     typedef llvmc::NodesIterator nodes_iterator;
 276     static nodes_iterator nodes_begin(GraphType *G) {
 277       return GraphBegin(G);
 278     }
 279     static nodes_iterator nodes_end(GraphType *G) {
 280       return GraphEnd(G);
 281     }
 282   };
 283
 284 }
 285
 286 #endif // LLVM_TOOLS_LLVMC2_COMPILATION_GRAPH_H