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