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