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_INCLUDE_COMPILER_DRIVER_COMPILATION_GRAPH_H
  15 #define LLVM_INCLUDE_COMPILER_DRIVER_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
  88     // Inward edge counter. Used to implement topological sort.
  89     void IncrInEdges() { ++InEdges; }
  90     void DecrInEdges() { --InEdges; }
  91     bool HasNoInEdges() const { return InEdges == 0; }
  92
  93     // Needed to implement NodeChildIterator/GraphTraits
  94     CompilationGraph* OwningGraph;
  95     // The corresponding Tool.
  96     // WARNING: ToolPtr can be NULL (for the root node).
  97     llvm::IntrusiveRefCntPtr<Tool> ToolPtr;
  98     // Links to children.
  99     container_type OutEdges;
 100     // Inward edge counter. Updated in
 101     // CompilationGraph::insertEdge(). Used for topological sorting.
 102     unsigned InEdges;
 103   };
 104
 105   class NodesIterator;
 106
 107   /// CompilationGraph - The compilation graph itself.
 108   class CompilationGraph {
 109     /// nodes_map_type - The main data structure.
 110     typedef llvm::StringMap<Node> nodes_map_type;
 111     /// tools_vector_type, tools_map_type - Data structures used to
 112     /// map from language names to tools. (We can have several tools
 113     /// associated with each language name, hence the need for a
 114     /// vector.)
 115     typedef
 116     llvm::SmallVector<llvm::IntrusiveRefCntPtr<Edge>, 3> tools_vector_type;
 117     typedef llvm::StringMap<tools_vector_type> tools_map_type;
 118
 119     /// ToolsMap - Map from language names to lists of tool names.
 120     tools_map_type ToolsMap;
 121     /// NodesMap - Map from tool names to Tool objects.
 122     nodes_map_type NodesMap;
 123
 124   public:
 125
 126     typedef nodes_map_type::iterator nodes_iterator;
 127     typedef nodes_map_type::const_iterator const_nodes_iterator;
 128
 129     CompilationGraph();
 130
 131     /// insertNode - Insert a new node into the graph. Takes
 132     /// ownership of the object.
 133     void insertNode(Tool* T);
 134
 135     /// insertEdge - Insert a new edge into the graph. Takes ownership
 136     /// of the Edge object.
 137     void insertEdge(const std::string& A, Edge* E);
 138
 139     /// Build - Build target(s) from the input file set. Command-line
 140     /// options are passed implicitly as global variables.
 141     int Build(llvm::sys::Path const& TempDir, const LanguageMap& LangMap);
 142
 143     /// Check - Check the compilation graph for common errors like
 144     /// cycles, input/output language mismatch and multiple default
 145     /// edges. Prints error messages and in case it finds any errors.
 146     int Check();
 147
 148     /// getNode - Return a reference to the node correponding to the
 149     /// given tool name. Throws std::runtime_error.
 150     Node& getNode(const std::string& ToolName);
 151     const Node& getNode(const std::string& ToolName) const;
 152
 153     /// viewGraph - This function is meant for use from the debugger.
 154     /// You can just say 'call G->viewGraph()' and a ghostview window
 155     /// should pop up from the program, displaying the compilation
 156     /// graph. This depends on there being a 'dot' and 'gv' program
 157     /// in your path.
 158     void viewGraph();
 159
 160     /// writeGraph - Write Graphviz .dot source file to the current direcotry.
 161     void writeGraph(const std::string& OutputFilename);
 162
 163     // GraphTraits support.
 164     friend NodesIterator GraphBegin(CompilationGraph*);
 165     friend NodesIterator GraphEnd(CompilationGraph*);
 166
 167   private:
 168     // Helper functions.
 169
 170     /// getToolsVector - Return a reference to the list of tool names
 171     /// corresponding to the given language name. Throws
 172     /// std::runtime_error.
 173     const tools_vector_type& getToolsVector(const std::string& LangName) const;
 174
 175     /// PassThroughGraph - Pass the input file through the toolchain
 176     /// starting at StartNode.
 177     void PassThroughGraph (const llvm::sys::Path& In, const Node* StartNode,
 178                            const InputLanguagesSet& InLangs,
 179                            const llvm::sys::Path& TempDir,
 180                            const LanguageMap& LangMap) const;
 181
 182     /// FindToolChain - Find head of the toolchain corresponding to
 183     /// the given file.
 184     const Node* FindToolChain(const llvm::sys::Path& In,
 185                               const std::string* ForceLanguage,
 186                               InputLanguagesSet& InLangs,
 187                               const LanguageMap& LangMap) const;
 188
 189     /// BuildInitial - Traverse the initial parts of the toolchains.
 190     void BuildInitial(InputLanguagesSet& InLangs,
 191                       const llvm::sys::Path& TempDir,
 192                       const LanguageMap& LangMap);
 193
 194     /// TopologicalSort - Sort the nodes in topological order.
 195     void TopologicalSort(std::vector<const Node*>& Out);
 196     /// TopologicalSortFilterJoinNodes - Call TopologicalSort and
 197     /// filter the resulting list to include only Join nodes.
 198     void TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out);
 199
 200     // Functions used to implement Check().
 201
 202     /// CheckLanguageNames - Check that output/input language names
 203     /// match for all nodes.
 204     int CheckLanguageNames() const;
 205     /// CheckMultipleDefaultEdges - check that there are no multiple
 206     /// default default edges.
 207     int CheckMultipleDefaultEdges() const;
 208     /// CheckCycles - Check that there are no cycles in the graph.
 209     int CheckCycles();
 210
 211   };
 212
 213   // GraphTraits support code.
 214
 215   /// NodesIterator - Auxiliary class needed to implement GraphTraits
 216   /// support. Can be generalised to something like value_iterator
 217   /// for map-like containers.
 218   class NodesIterator : public CompilationGraph::nodes_iterator {
 219     typedef CompilationGraph::nodes_iterator super;
 220     typedef NodesIterator ThisType;
 221     typedef Node* pointer;
 222     typedef Node& reference;
 223
 224   public:
 225     NodesIterator(super I) : super(I) {}
 226
 227     inline reference operator*() const {
 228       return super::operator->()->second;
 229     }
 230     inline pointer operator->() const {
 231       return &super::operator->()->second;
 232     }
 233   };
 234
 235   inline NodesIterator GraphBegin(CompilationGraph* G) {
 236     return NodesIterator(G->NodesMap.begin());
 237   }
 238
 239   inline NodesIterator GraphEnd(CompilationGraph* G) {
 240     return NodesIterator(G->NodesMap.end());
 241   }
 242
 243
 244   /// NodeChildIterator - Another auxiliary class needed by GraphTraits.
 245   class NodeChildIterator : public bidirectional_iterator<Node, ptrdiff_t> {
 246     typedef NodeChildIterator ThisType;
 247     typedef Node::container_type::iterator iterator;
 248
 249     CompilationGraph* OwningGraph;
 250     iterator EdgeIter;
 251   public:
 252     typedef Node* pointer;
 253     typedef Node& reference;
 254
 255     NodeChildIterator(Node* N, iterator I) :
 256       OwningGraph(N->OwningGraph), EdgeIter(I) {}
 257
 258     const ThisType& operator=(const ThisType& I) {
 259       assert(OwningGraph == I.OwningGraph);
 260       EdgeIter = I.EdgeIter;
 261       return *this;
 262     }
 263
 264     inline bool operator==(const ThisType& I) const {
 265       assert(OwningGraph == I.OwningGraph);
 266       return EdgeIter == I.EdgeIter;
 267     }
 268     inline bool operator!=(const ThisType& I) const {
 269       return !this->operator==(I);
 270     }
 271
 272     inline pointer operator*() const {
 273       return &OwningGraph->getNode((*EdgeIter)->ToolName());
 274     }
 275     inline pointer operator->() const {
 276       return this->operator*();
 277     }
 278
 279     ThisType& operator++() { ++EdgeIter; return *this; } // Preincrement
 280     ThisType operator++(int) { // Postincrement
 281       ThisType tmp = *this;
 282       ++*this;
 283       return tmp;
 284     }
 285
 286     inline ThisType& operator--() { --EdgeIter; return *this; }  // Predecrement
 287     inline ThisType operator--(int) { // Postdecrement
 288       ThisType tmp = *this;
 289       --*this;
 290       return tmp;
 291     }
 292
 293   };
 294 }
 295
 296 namespace llvm {
 297   template <>
 298   struct GraphTraits<llvmc::CompilationGraph*> {
 299     typedef llvmc::CompilationGraph GraphType;
 300     typedef llvmc::Node NodeType;
 301     typedef llvmc::NodeChildIterator ChildIteratorType;
 302
 303     static NodeType* getEntryNode(GraphType* G) {
 304       return &G->getNode("root");
 305     }
 306
 307     static ChildIteratorType child_begin(NodeType* N) {
 308       return ChildIteratorType(N, N->OutEdges.begin());
 309     }
 310     static ChildIteratorType child_end(NodeType* N) {
 311       return ChildIteratorType(N, N->OutEdges.end());
 312     }
 313
 314     typedef llvmc::NodesIterator nodes_iterator;
 315     static nodes_iterator nodes_begin(GraphType *G) {
 316       return GraphBegin(G);
 317     }
 318     static nodes_iterator nodes_end(GraphType *G) {
 319       return GraphEnd(G);
 320     }
 321   };
 322
 323 }
 324
 325 #endif // LLVM_INCLUDE_COMPILER_DRIVER_COMPILATION_GRAPH_H