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