include/llvm/CFG.h

   1 //===-- llvm/CFG.h - CFG definitions and useful classes ----------*- C++ -*--=//
   2 //
   3 // This file contains the class definitions useful for operating on the control
   4 // flow graph.
   5 //
   6 // Currently it contains functionality for these three applications:
   7 //
   8 //  1. Iterate over the predecessors of a basic block:
   9 //     pred_iterator, pred_const_iterator, pred_begin, pred_end
  10 //  2. Iterate over the successors of a basic block:
  11 //     succ_iterator, succ_const_iterator, succ_begin, succ_end
  12 //  3. Iterate over the basic blocks of a method in depth first ordering or
  13 //     reverse depth first order.  df_iterator, df_const_iterator,
  14 //     df_begin, df_end.  df_begin takes an arg to specify reverse or not.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #ifndef LLVM_CFG_H
  19 #define LLVM_CFG_H
  20
  21 #include <set>
  22 #include <stack>
  23 #include "llvm/Method.h"
  24 #include "llvm/BasicBlock.h"
  25 #include "llvm/InstrTypes.h"
  26
  27 //===----------------------------------------------------------------------===//
  28 //                                Interface
  29 //===----------------------------------------------------------------------===//
  30
  31 #include "llvm/CFGdecls.h"      // See this file for concise interface info
  32
  33 namespace cfg {
  34
  35 //===----------------------------------------------------------------------===//
  36 //                                Implementation
  37 //===----------------------------------------------------------------------===//
  38
  39 //===----------------------------------------------------------------------===//
  40 // Basic Block Predecessor Iterator
  41 //
  42
  43 template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
  44 class PredIterator {
  45   const _Ptr BB;
  46   _USE_iterator It;
  47 public:
  48   typedef PredIterator<_Ptr,_USE_iterator> _Self;
  49
  50   typedef bidirectional_iterator_tag iterator_category;
  51   typedef _Ptr pointer;
  52
  53   inline void advancePastConstPool() {
  54     // Loop to ignore constant pool references
  55     while (It != BB->use_end() &&
  56            (((*It)->getValueType() != Value::InstructionVal) ||
  57             !(((Instruction*)(*It))->isTerminator())))
  58       ++It;
  59   }
  60
  61   inline PredIterator(_Ptr bb) : BB(bb), It(bb->use_begin()) {
  62     advancePastConstPool();
  63   }
  64   inline PredIterator(_Ptr bb, bool) : BB(bb), It(bb->use_end()) {}
  65
  66   inline bool operator==(const _Self& x) const { return It == x.It; }
  67   inline bool operator!=(const _Self& x) const { return !operator==(x); }
  68
  69   inline pointer operator*() const {
  70     assert ((*It)->getValueType() == Value::InstructionVal);
  71     return ((Instruction *)(*It))->getParent();
  72   }
  73   inline pointer *operator->() const { return &(operator*()); }
  74
  75   inline _Self& operator++() {   // Preincrement
  76     ++It; advancePastConstPool();
  77     return *this;
  78   }
  79
  80   inline _Self operator++(int) { // Postincrement
  81     _Self tmp = *this; ++*this; return tmp;
  82   }
  83
  84   inline _Self& operator--() { --It; return *this; }  // Predecrement
  85   inline _Self operator--(int) { // Postdecrement
  86     _Self tmp = *this; --*this; return tmp;
  87   }
  88 };
  89
  90 inline pred_iterator       pred_begin(      BasicBlock *BB) {
  91   return pred_iterator(BB);
  92 }
  93 inline pred_const_iterator pred_begin(const BasicBlock *BB) {
  94   return pred_const_iterator(BB);
  95 }
  96 inline pred_iterator       pred_end(      BasicBlock *BB) {
  97   return pred_iterator(BB,true);
  98 }
  99 inline pred_const_iterator pred_end(const BasicBlock *BB) {
 100   return pred_const_iterator(BB,true);
 101 }
 102
 103
 104 //===----------------------------------------------------------------------===//
 105 // Basic Block Successor Iterator
 106 //
 107
 108 template <class _Term, class _BB>           // Successor Iterator
 109 class SuccIterator {
 110   const _Term Term;
 111   unsigned idx;
 112 public:
 113   typedef SuccIterator<_Term, _BB> _Self;
 114   typedef forward_iterator_tag iterator_category;
 115   typedef _BB pointer;
 116
 117   inline SuccIterator(_Term T) : Term(T), idx(0) {}         // begin iterator
 118   inline SuccIterator(_Term T, bool)
 119     : Term(T), idx(Term->getNumSuccessors()) {}             // end iterator
 120
 121   inline bool operator==(const _Self& x) const { return idx == x.idx; }
 122   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 123
 124   inline pointer operator*() const { return Term->getSuccessor(idx); }
 125   inline pointer *operator->() const { return &(operator*()); }
 126
 127   inline _Self& operator++() { ++idx; return *this; } // Preincrement
 128   inline _Self operator++(int) { // Postincrement
 129     _Self tmp = *this; ++*this; return tmp;
 130   }
 131
 132   inline _Self& operator--() { --idx; return *this; }  // Predecrement
 133   inline _Self operator--(int) { // Postdecrement
 134     _Self tmp = *this; --*this; return tmp;
 135   }
 136 };
 137
 138 inline succ_iterator       succ_begin(      BasicBlock *BB) {
 139   return succ_iterator(BB->getTerminator());
 140 }
 141 inline succ_const_iterator succ_begin(const BasicBlock *BB) {
 142   return succ_const_iterator(BB->getTerminator());
 143 }
 144 inline succ_iterator       succ_end(      BasicBlock *BB) {
 145   return succ_iterator(BB->getTerminator(),true);
 146 }
 147 inline succ_const_iterator succ_end(const BasicBlock *BB) {
 148   return succ_const_iterator(BB->getTerminator(),true);
 149 }
 150
 151
 152 //===----------------------------------------------------------------------===//
 153 // Depth First Iterator
 154 //
 155
 156 template<class BBType, class SuccItTy>
 157 class DFIterator {            // BasicBlock Depth First Iterator
 158   set<BBType *>   Visited;    // All of the blocks visited so far...
 159   // VisitStack - Used to maintain the ordering.  Top = current block
 160   // First element is basic block pointer, second is the 'next child' to visit
 161   stack<pair<BBType *, SuccItTy> > VisitStack;
 162   const bool Reverse;         // Iterate over children before self?
 163 private:
 164   void reverseEnterNode() {
 165     pair<BBType *, SuccItTy> &Top = VisitStack.top();
 166     BBType *BB    = Top.first;
 167     SuccItTy &It  = Top.second;
 168     for (; It != succ_end(BB); ++It) {
 169       BBType *Child = *It;
 170       if (!Visited.count(Child)) {
 171         Visited.insert(Child);
 172         VisitStack.push(make_pair(Child, succ_begin(Child)));
 173         reverseEnterNode();
 174         return;
 175       }
 176     }
 177   }
 178 public:
 179   typedef DFIterator<BBType, SuccItTy> _Self;
 180
 181   typedef forward_iterator_tag iterator_category;
 182   typedef BBType *pointer;
 183   typedef BBType &reference;
 184   typedef void difference_type;
 185   typedef BBType *value_type;
 186
 187   inline DFIterator(BBType *BB, bool reverse) : Reverse(reverse) {
 188     Visited.insert(BB);
 189     VisitStack.push(make_pair(BB, succ_begin(BB)));
 190     if (Reverse) reverseEnterNode();
 191   }
 192   inline DFIterator() { /* End is when stack is empty */ }
 193
 194   inline bool operator==(const _Self& x) const {
 195     return VisitStack == x.VisitStack;
 196   }
 197   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 198
 199   inline pointer operator*() const {
 200     return VisitStack.top().first;
 201   }
 202
 203   // This is a nonstandard operator-> that dereferences the pointer an extra
 204   // time... so that you can actually call methods ON the BasicBlock, because
 205   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
 206   //
 207   inline BBType *operator->() const { return operator*(); }
 208
 209   inline _Self& operator++() {   // Preincrement
 210     if (Reverse) {               // Reverse Depth First Iterator
 211       if (VisitStack.top().second == succ_end(VisitStack.top().first))
 212         VisitStack.pop();
 213       if (!VisitStack.empty())
 214         reverseEnterNode();
 215     } else {                     // Normal Depth First Iterator
 216       do {
 217         pair<BBType *, SuccItTy> &Top = VisitStack.top();
 218         BBType *BB    = Top.first;
 219         SuccItTy &It  = Top.second;
 220
 221         while (It != succ_end(BB)) {
 222           BBType *Next = *It++;
 223           if (!Visited.count(Next)) {  // Has our next sibling been visited?
 224             // No, do it now.
 225             Visited.insert(Next);
 226             VisitStack.push(make_pair(Next, succ_begin(Next)));
 227             return *this;
 228           }
 229         }
 230
 231         // Oops, ran out of successors... go up a level on the stack.
 232         VisitStack.pop();
 233       } while (!VisitStack.empty());
 234     }
 235     return *this;
 236   }
 237
 238   inline _Self operator++(int) { // Postincrement
 239     _Self tmp = *this; ++*this; return tmp;
 240   }
 241 };
 242
 243 inline df_iterator df_begin(Method *M, bool Reverse = false) {
 244   return df_iterator(M->getBasicBlocks().front(), Reverse);
 245 }
 246
 247 inline df_const_iterator df_begin(const Method *M, bool Reverse = false) {
 248   return df_const_iterator(M->getBasicBlocks().front(), Reverse);
 249 }
 250 inline df_iterator       df_end(Method*) {
 251   return df_iterator();
 252 }
 253 inline df_const_iterator df_end(const Method*) {
 254   return df_const_iterator();
 255 }
 256
 257 inline df_iterator df_begin(BasicBlock *BB, bool Reverse = false) {
 258   return df_iterator(BB, Reverse);
 259 }
 260 inline df_const_iterator df_begin(const BasicBlock *BB, bool Reverse = false) {
 261   return df_const_iterator(BB, Reverse);
 262 }
 263
 264 inline df_iterator       df_end(BasicBlock*) {
 265   return df_iterator();
 266 }
 267 inline df_const_iterator df_end(const BasicBlock*) {
 268   return df_const_iterator();
 269 }
 270
 271
 272 //===----------------------------------------------------------------------===//
 273 // Post Order CFG iterator code
 274 //
 275
 276 template<class BBType, class SuccItTy>
 277 class POIterator {
 278   set<BBType *>   Visited;    // All of the blocks visited so far...
 279   // VisitStack - Used to maintain the ordering.  Top = current block
 280   // First element is basic block pointer, second is the 'next child' to visit
 281   stack<pair<BBType *, SuccItTy> > VisitStack;
 282
 283   void traverseChild() {
 284     while (VisitStack.top().second != succ_end(VisitStack.top().first)) {
 285       BBType *BB = *VisitStack.top().second++;
 286       if (!Visited.count(BB)) {  // If the block is not visited...
 287         Visited.insert(BB);
 288         VisitStack.push(make_pair(BB, succ_begin(BB)));
 289       }
 290     }
 291   }
 292 public:
 293   typedef POIterator<BBType, SuccItTy> _Self;
 294
 295   typedef forward_iterator_tag iterator_category;
 296   typedef BBType *pointer;
 297   typedef BBType &reference;
 298   typedef void difference_type;
 299   typedef BBType *value_type;
 300
 301   inline POIterator(BBType *BB) {
 302     Visited.insert(BB);
 303     VisitStack.push(make_pair(BB, succ_begin(BB)));
 304     traverseChild();
 305   }
 306   inline POIterator() { /* End is when stack is empty */ }
 307
 308   inline bool operator==(const _Self& x) const {
 309     return VisitStack == x.VisitStack;
 310   }
 311   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 312
 313   inline pointer operator*() const {
 314     return VisitStack.top().first;
 315   }
 316
 317   // This is a nonstandard operator-> that dereferences the pointer an extra
 318   // time... so that you can actually call methods ON the BasicBlock, because
 319   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
 320   //
 321   inline BBType *operator->() const { return operator*(); }
 322
 323   inline _Self& operator++() {   // Preincrement
 324     VisitStack.pop();
 325     if (!VisitStack.empty())
 326       traverseChild();
 327     return *this;
 328   }
 329
 330   inline _Self operator++(int) { // Postincrement
 331     _Self tmp = *this; ++*this; return tmp;
 332   }
 333 };
 334
 335 inline po_iterator       po_begin(      Method *M) {
 336   return po_iterator(M->getBasicBlocks().front());
 337 }
 338 inline po_const_iterator po_begin(const Method *M) {
 339   return po_const_iterator(M->getBasicBlocks().front());
 340 }
 341 inline po_iterator       po_end  (      Method *M) {
 342   return po_iterator();
 343 }
 344 inline po_const_iterator po_end  (const Method *M) {
 345   return po_const_iterator();
 346 }
 347
 348 inline po_iterator       po_begin(      BasicBlock *BB) {
 349   return po_iterator(BB);
 350 }
 351 inline po_const_iterator po_begin(const BasicBlock *BB) {
 352   return po_const_iterator(BB);
 353 }
 354 inline po_iterator       po_end  (      BasicBlock *BB) {
 355   return po_iterator();
 356 }
 357 inline po_const_iterator po_end  (const BasicBlock *BB) {
 358   return po_const_iterator();
 359 }
 360
 361
 362 //===----------------------------------------------------------------------===//
 363 // Reverse Post Order CFG iterator code
 364 //
 365
 366 class ReversePostOrderTraversal {
 367   vector<BasicBlock*> Blocks;       // Block list in normal PO order
 368   inline void Initialize(BasicBlock *BB) {
 369     copy(po_begin(BB), po_end(BB), back_inserter(Blocks));
 370   }
 371 public:
 372   inline ReversePostOrderTraversal(Method *M) {
 373     Initialize(M->getBasicBlocks().front());
 374   }
 375   inline ReversePostOrderTraversal(BasicBlock *BB) {
 376     Initialize(BB);
 377   }
 378
 379   // Because we want a reverse post order, use reverse iterators from the vector
 380   inline rpo_iterator begin() { return Blocks.rbegin(); }
 381   inline rpo_iterator end()   { return Blocks.rend(); }
 382 };
 383
 384 }    // End namespace cfg
 385
 386 #endif