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