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