include/llvm/Support/CFG.h

   1 //===-- llvm/Support/CFG.h - Process LLVM structures as graphs --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines specializations of GraphTraits that allow Function and
  11 // BasicBlock graphs to be treated as proper graphs for generic algorithms.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_SUPPORT_CFG_H
  16 #define LLVM_SUPPORT_CFG_H
  17
  18 #include "llvm/ADT/GraphTraits.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/InstrTypes.h"
  21 #include "llvm/ADT/iterator"
  22
  23 namespace llvm {
  24
  25 //===--------------------------------------------------------------------===//
  26 // BasicBlock pred_iterator definition
  27 //===--------------------------------------------------------------------===//
  28
  29 template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
  30 class PredIterator : public forward_iterator<_Ptr, ptrdiff_t> {
  31   typedef forward_iterator<_Ptr, ptrdiff_t> super;
  32   _USE_iterator It;
  33 public:
  34   typedef PredIterator<_Ptr,_USE_iterator> _Self;
  35   typedef typename super::pointer pointer;
  36
  37   inline void advancePastNonPreds() {
  38     // Loop to ignore non predecessor uses (for example PHI nodes)...
  39     while (!It.atEnd()) {
  40       if (isa<TerminatorInst>(*It) || isa<BasicBlock>(*It))
  41         break;
  42       ++It;
  43     }
  44   }
  45
  46   inline PredIterator(_Ptr *bb) : It(bb->use_begin()) {
  47     advancePastNonPreds();
  48   }
  49   inline PredIterator(_Ptr *bb, bool) : It(bb->use_end()) {}
  50
  51   inline bool operator==(const _Self& x) const { return It == x.It; }
  52   inline bool operator!=(const _Self& x) const { return !operator==(x); }
  53
  54   inline pointer operator*() const {
  55     assert(!It.atEnd() && "pred_iterator out of range!");
  56     return cast<TerminatorInst>(*It)->getParent();
  57   }
  58   inline pointer *operator->() const { return &(operator*()); }
  59
  60   inline _Self& operator++() {   // Preincrement
  61     assert(!It.atEnd() && "pred_iterator out of range!");
  62     ++It; advancePastNonTerminators();
  63     return *this;
  64   }
  65
  66   inline _Self operator++(int) { // Postincrement
  67     _Self tmp = *this; ++*this; return tmp;
  68   }
  69 };
  70
  71 typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator;
  72 typedef PredIterator<const BasicBlock,
  73                      Value::use_const_iterator> pred_const_iterator;
  74
  75 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
  76 inline pred_const_iterator pred_begin(const BasicBlock *BB) {
  77   return pred_const_iterator(BB);
  78 }
  79 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
  80 inline pred_const_iterator pred_end(const BasicBlock *BB) {
  81   return pred_const_iterator(BB, true);
  82 }
  83
  84
  85
  86 //===--------------------------------------------------------------------===//
  87 // BasicBlock succ_iterator definition
  88 //===--------------------------------------------------------------------===//
  89
  90 template <class Term_, class BB_>           // Successor Iterator
  91 class SuccIterator : public bidirectional_iterator<BB_, ptrdiff_t> {
  92   const Term_ Term;
  93   unsigned idx;
  94   typedef bidirectional_iterator<BB_, ptrdiff_t> super;
  95 public:
  96   typedef SuccIterator<Term_, BB_> _Self;
  97   typedef typename super::pointer pointer;
  98   // TODO: This can be random access iterator, need operator+ and stuff tho
  99
 100   inline SuccIterator(Term_ T) : Term(T), idx(0) {         // begin iterator
 101     assert(T && "getTerminator returned null!");
 102   }
 103   inline SuccIterator(Term_ T, bool)                       // end iterator
 104     : Term(T), idx(Term->getNumSuccessors()) {
 105     assert(T && "getTerminator returned null!");
 106   }
 107
 108   inline const _Self &operator=(const _Self &I) {
 109     assert(Term == I.Term &&"Cannot assign iterators to two different blocks!");
 110     idx = I.idx;
 111     return *this;
 112   }
 113
 114   /// getSuccessorIndex - This is used to interface between code that wants to
 115   /// operate on terminator instructions directly.
 116   unsigned getSuccessorIndex() const { return idx; }
 117
 118   inline bool operator==(const _Self& x) const { return idx == x.idx; }
 119   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 120
 121   inline pointer operator*() const { return Term->getSuccessor(idx); }
 122   inline pointer operator->() const { return operator*(); }
 123
 124   inline _Self& operator++() { ++idx; return *this; } // Preincrement
 125   inline _Self operator++(int) { // Postincrement
 126     _Self tmp = *this; ++*this; return tmp;
 127   }
 128
 129   inline _Self& operator--() { --idx; return *this; }  // Predecrement
 130   inline _Self operator--(int) { // Postdecrement
 131     _Self tmp = *this; --*this; return tmp;
 132   }
 133 };
 134
 135 typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator;
 136 typedef SuccIterator<const TerminatorInst*,
 137                      const BasicBlock> succ_const_iterator;
 138
 139 inline succ_iterator succ_begin(BasicBlock *BB) {
 140   return succ_iterator(BB->getTerminator());
 141 }
 142 inline succ_const_iterator succ_begin(const BasicBlock *BB) {
 143   return succ_const_iterator(BB->getTerminator());
 144 }
 145 inline succ_iterator succ_end(BasicBlock *BB) {
 146   return succ_iterator(BB->getTerminator(), true);
 147 }
 148 inline succ_const_iterator succ_end(const BasicBlock *BB) {
 149   return succ_const_iterator(BB->getTerminator(), true);
 150 }
 151
 152
 153
 154 //===--------------------------------------------------------------------===//
 155 // GraphTraits specializations for basic block graphs (CFGs)
 156 //===--------------------------------------------------------------------===//
 157
 158 // Provide specializations of GraphTraits to be able to treat a function as a
 159 // graph of basic blocks...
 160
 161 template <> struct GraphTraits<BasicBlock*> {
 162   typedef BasicBlock NodeType;
 163   typedef succ_iterator ChildIteratorType;
 164
 165   static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
 166   static inline ChildIteratorType child_begin(NodeType *N) {
 167     return succ_begin(N);
 168   }
 169   static inline ChildIteratorType child_end(NodeType *N) {
 170     return succ_end(N);
 171   }
 172 };
 173
 174 template <> struct GraphTraits<const BasicBlock*> {
 175   typedef const BasicBlock NodeType;
 176   typedef succ_const_iterator ChildIteratorType;
 177
 178   static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
 179
 180   static inline ChildIteratorType child_begin(NodeType *N) {
 181     return succ_begin(N);
 182   }
 183   static inline ChildIteratorType child_end(NodeType *N) {
 184     return succ_end(N);
 185   }
 186 };
 187
 188 // Provide specializations of GraphTraits to be able to treat a function as a
 189 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 190 // a function is considered to be when traversing the predecessor edges of a BB
 191 // instead of the successor edges.
 192 //
 193 template <> struct GraphTraits<Inverse<BasicBlock*> > {
 194   typedef BasicBlock NodeType;
 195   typedef pred_iterator ChildIteratorType;
 196   static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
 197   static inline ChildIteratorType child_begin(NodeType *N) {
 198     return pred_begin(N);
 199   }
 200   static inline ChildIteratorType child_end(NodeType *N) {
 201     return pred_end(N);
 202   }
 203 };
 204
 205 template <> struct GraphTraits<Inverse<const BasicBlock*> > {
 206   typedef const BasicBlock NodeType;
 207   typedef pred_const_iterator ChildIteratorType;
 208   static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
 209     return G.Graph;
 210   }
 211   static inline ChildIteratorType child_begin(NodeType *N) {
 212     return pred_begin(N);
 213   }
 214   static inline ChildIteratorType child_end(NodeType *N) {
 215     return pred_end(N);
 216   }
 217 };
 218
 219
 220
 221 //===--------------------------------------------------------------------===//
 222 // GraphTraits specializations for function basic block graphs (CFGs)
 223 //===--------------------------------------------------------------------===//
 224
 225 // Provide specializations of GraphTraits to be able to treat a function as a
 226 // graph of basic blocks... these are the same as the basic block iterators,
 227 // except that the root node is implicitly the first node of the function.
 228 //
 229 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
 230   static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); }
 231
 232   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 233   typedef Function::iterator nodes_iterator;
 234   static nodes_iterator nodes_begin(Function *F) { return F->begin(); }
 235   static nodes_iterator nodes_end  (Function *F) { return F->end(); }
 236 };
 237 template <> struct GraphTraits<const Function*> :
 238   public GraphTraits<const BasicBlock*> {
 239   static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();}
 240
 241   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 242   typedef Function::const_iterator nodes_iterator;
 243   static nodes_iterator nodes_begin(const Function *F) { return F->begin(); }
 244   static nodes_iterator nodes_end  (const Function *F) { return F->end(); }
 245 };
 246
 247
 248 // Provide specializations of GraphTraits to be able to treat a function as a
 249 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 250 // a function is considered to be when traversing the predecessor edges of a BB
 251 // instead of the successor edges.
 252 //
 253 template <> struct GraphTraits<Inverse<Function*> > :
 254   public GraphTraits<Inverse<BasicBlock*> > {
 255   static NodeType *getEntryNode(Inverse<Function*> G) {
 256     return &G.Graph->getEntryBlock();
 257   }
 258 };
 259 template <> struct GraphTraits<Inverse<const Function*> > :
 260   public GraphTraits<Inverse<const BasicBlock*> > {
 261   static NodeType *getEntryNode(Inverse<const Function *> G) {
 262     return &G.Graph->getEntryBlock();
 263   }
 264 };
 265
 266 } // End llvm namespace
 267
 268 #endif