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