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     if (isa<TerminatorInst>(*It))      // not dyn_cast due to const-correctness
  57       return cast<TerminatorInst>(*It)->getParent();
  58
  59     return cast<_Ptr>(*It);
  60   }
  61   inline pointer *operator->() const { return &(operator*()); }
  62
  63   inline _Self& operator++() {   // Preincrement
  64     assert(!It.atEnd() && "pred_iterator out of range!");
  65     ++It; advancePastNonPreds();
  66     return *this;
  67   }
  68
  69   inline _Self operator++(int) { // Postincrement
  70     _Self tmp = *this; ++*this; return tmp;
  71   }
  72 };
  73
  74 typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator;
  75 typedef PredIterator<const BasicBlock,
  76                      Value::use_const_iterator> pred_const_iterator;
  77
  78 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
  79 inline pred_const_iterator pred_begin(const BasicBlock *BB) {
  80   return pred_const_iterator(BB);
  81 }
  82 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
  83 inline pred_const_iterator pred_end(const BasicBlock *BB) {
  84   return pred_const_iterator(BB, true);
  85 }
  86
  87
  88
  89 //===--------------------------------------------------------------------===//
  90 // BasicBlock succ_iterator definition
  91 //===--------------------------------------------------------------------===//
  92
  93 template <class Term_, class BB_>           // Successor Iterator
  94 class SuccIterator : public bidirectional_iterator<BB_, ptrdiff_t> {
  95   const Term_ Term;
  96   unsigned idx;
  97   typedef bidirectional_iterator<BB_, ptrdiff_t> super;
  98 public:
  99   typedef SuccIterator<Term_, BB_> _Self;
 100   typedef typename super::pointer pointer;
 101   // TODO: This can be random access iterator, need operator+ and stuff tho
 102
 103   inline SuccIterator(Term_ T) : Term(T), idx(0) {         // begin iterator
 104     assert(T && "getTerminator returned null!");
 105   }
 106   inline SuccIterator(Term_ T, bool)                       // end iterator
 107     : Term(T), idx(Term->getNumSuccessors()) {
 108     assert(T && "getTerminator returned null!");
 109     if (Term->getParent()->getUnwindDest())
 110       ++idx;
 111   }
 112
 113   inline const _Self &operator=(const _Self &I) {
 114     assert(Term == I.Term &&"Cannot assign iterators to two different blocks!");
 115     idx = I.idx;
 116     return *this;
 117   }
 118
 119   /// getSuccessorIndex - This is used to interface between code that wants to
 120   /// operate on terminator instructions directly.
 121   unsigned getSuccessorIndex() const { return idx; }
 122
 123   inline bool operator==(const _Self& x) const { return idx == x.idx; }
 124   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 125
 126   inline pointer operator*() const {
 127     if (idx == Term->getNumSuccessors())
 128       return Term->getParent()->getUnwindDest();
 129
 130     return Term->getSuccessor(idx);
 131   }
 132   inline pointer operator->() const { return operator*(); }
 133
 134   inline _Self& operator++() { ++idx; return *this; } // Preincrement
 135   inline _Self operator++(int) { // Postincrement
 136     _Self tmp = *this; ++*this; return tmp;
 137   }
 138
 139   inline _Self& operator--() { --idx; return *this; }  // Predecrement
 140   inline _Self operator--(int) { // Postdecrement
 141     _Self tmp = *this; --*this; return tmp;
 142   }
 143 };
 144
 145 typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator;
 146 typedef SuccIterator<const TerminatorInst*,
 147                      const BasicBlock> succ_const_iterator;
 148
 149 inline succ_iterator succ_begin(BasicBlock *BB) {
 150   return succ_iterator(BB->getTerminator());
 151 }
 152 inline succ_const_iterator succ_begin(const BasicBlock *BB) {
 153   return succ_const_iterator(BB->getTerminator());
 154 }
 155 inline succ_iterator succ_end(BasicBlock *BB) {
 156   return succ_iterator(BB->getTerminator(), true);
 157 }
 158 inline succ_const_iterator succ_end(const BasicBlock *BB) {
 159   return succ_const_iterator(BB->getTerminator(), true);
 160 }
 161
 162
 163
 164 //===--------------------------------------------------------------------===//
 165 // GraphTraits specializations for basic block graphs (CFGs)
 166 //===--------------------------------------------------------------------===//
 167
 168 // Provide specializations of GraphTraits to be able to treat a function as a
 169 // graph of basic blocks...
 170
 171 template <> struct GraphTraits<BasicBlock*> {
 172   typedef BasicBlock NodeType;
 173   typedef succ_iterator ChildIteratorType;
 174
 175   static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
 176   static inline ChildIteratorType child_begin(NodeType *N) {
 177     return succ_begin(N);
 178   }
 179   static inline ChildIteratorType child_end(NodeType *N) {
 180     return succ_end(N);
 181   }
 182 };
 183
 184 template <> struct GraphTraits<const BasicBlock*> {
 185   typedef const BasicBlock NodeType;
 186   typedef succ_const_iterator ChildIteratorType;
 187
 188   static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
 189
 190   static inline ChildIteratorType child_begin(NodeType *N) {
 191     return succ_begin(N);
 192   }
 193   static inline ChildIteratorType child_end(NodeType *N) {
 194     return succ_end(N);
 195   }
 196 };
 197
 198 // Provide specializations of GraphTraits to be able to treat a function as a
 199 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 200 // a function is considered to be when traversing the predecessor edges of a BB
 201 // instead of the successor edges.
 202 //
 203 template <> struct GraphTraits<Inverse<BasicBlock*> > {
 204   typedef BasicBlock NodeType;
 205   typedef pred_iterator ChildIteratorType;
 206   static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
 207   static inline ChildIteratorType child_begin(NodeType *N) {
 208     return pred_begin(N);
 209   }
 210   static inline ChildIteratorType child_end(NodeType *N) {
 211     return pred_end(N);
 212   }
 213 };
 214
 215 template <> struct GraphTraits<Inverse<const BasicBlock*> > {
 216   typedef const BasicBlock NodeType;
 217   typedef pred_const_iterator ChildIteratorType;
 218   static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
 219     return G.Graph;
 220   }
 221   static inline ChildIteratorType child_begin(NodeType *N) {
 222     return pred_begin(N);
 223   }
 224   static inline ChildIteratorType child_end(NodeType *N) {
 225     return pred_end(N);
 226   }
 227 };
 228
 229
 230
 231 //===--------------------------------------------------------------------===//
 232 // GraphTraits specializations for function basic block graphs (CFGs)
 233 //===--------------------------------------------------------------------===//
 234
 235 // Provide specializations of GraphTraits to be able to treat a function as a
 236 // graph of basic blocks... these are the same as the basic block iterators,
 237 // except that the root node is implicitly the first node of the function.
 238 //
 239 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
 240   static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); }
 241
 242   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 243   typedef Function::iterator nodes_iterator;
 244   static nodes_iterator nodes_begin(Function *F) { return F->begin(); }
 245   static nodes_iterator nodes_end  (Function *F) { return F->end(); }
 246 };
 247 template <> struct GraphTraits<const Function*> :
 248   public GraphTraits<const BasicBlock*> {
 249   static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();}
 250
 251   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 252   typedef Function::const_iterator nodes_iterator;
 253   static nodes_iterator nodes_begin(const Function *F) { return F->begin(); }
 254   static nodes_iterator nodes_end  (const Function *F) { return F->end(); }
 255 };
 256
 257
 258 // Provide specializations of GraphTraits to be able to treat a function as a
 259 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 260 // a function is considered to be when traversing the predecessor edges of a BB
 261 // instead of the successor edges.
 262 //
 263 template <> struct GraphTraits<Inverse<Function*> > :
 264   public GraphTraits<Inverse<BasicBlock*> > {
 265   static NodeType *getEntryNode(Inverse<Function*> G) {
 266     return &G.Graph->getEntryBlock();
 267   }
 268 };
 269 template <> struct GraphTraits<Inverse<const Function*> > :
 270   public GraphTraits<Inverse<const BasicBlock*> > {
 271   static NodeType *getEntryNode(Inverse<const Function *> G) {
 272     return &G.Graph->getEntryBlock();
 273   }
 274 };
 275
 276 } // End llvm namespace
 277
 278 #endif