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     assert(T && "getTerminator returned null!");
 113   }
 114   inline SuccIterator(_Term T, bool)                       // end iterator
 115     : Term(T), idx(Term->getNumSuccessors()) {
 116     assert(T && "getTerminator returned null!");
 117   }
 118
 119   inline bool operator==(const _Self& x) const { return idx == x.idx; }
 120   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 121
 122   inline pointer operator*() const { return Term->getSuccessor(idx); }
 123   inline pointer operator->() const { return operator*(); }
 124
 125   inline _Self& operator++() { ++idx; return *this; } // Preincrement
 126   inline _Self operator++(int) { // Postincrement
 127     _Self tmp = *this; ++*this; return tmp;
 128   }
 129
 130   inline _Self& operator--() { --idx; return *this; }  // Predecrement
 131   inline _Self operator--(int) { // Postdecrement
 132     _Self tmp = *this; --*this; return tmp;
 133   }
 134 };
 135
 136 inline succ_iterator       succ_begin(      BasicBlock *BB) {
 137   return succ_iterator(BB->getTerminator());
 138 }
 139 inline succ_const_iterator succ_begin(const BasicBlock *BB) {
 140   return succ_const_iterator(BB->getTerminator());
 141 }
 142 inline succ_iterator       succ_end(      BasicBlock *BB) {
 143   return succ_iterator(BB->getTerminator(),true);
 144 }
 145 inline succ_const_iterator succ_end(const BasicBlock *BB) {
 146   return succ_const_iterator(BB->getTerminator(),true);
 147 }
 148
 149
 150 //===----------------------------------------------------------------------===//
 151 // Graph Type Declarations
 152 //
 153 //             BasicBlockGraph - Represent a standard traversal of a CFG
 154 //        ConstBasicBlockGraph - Represent a standard traversal of a const CFG
 155 //      InverseBasicBlockGraph - Represent a inverse traversal of a CFG
 156 // ConstInverseBasicBlockGraph - Represent a inverse traversal of a const CFG
 157 //
 158 // An Inverse traversal of a graph is where we chase predecessors, instead of
 159 // successors.
 160 //
 161 struct BasicBlockGraph {
 162   typedef BasicBlock NodeType;
 163   typedef succ_iterator ChildIteratorType;
 164   static inline ChildIteratorType child_begin(NodeType *N) {
 165     return succ_begin(N);
 166   }
 167   static inline ChildIteratorType child_end(NodeType *N) {
 168     return succ_end(N);
 169   }
 170 };
 171
 172 struct ConstBasicBlockGraph {
 173   typedef const BasicBlock NodeType;
 174   typedef succ_const_iterator ChildIteratorType;
 175   static inline ChildIteratorType child_begin(NodeType *N) {
 176     return succ_begin(N);
 177   }
 178   static inline ChildIteratorType child_end(NodeType *N) {
 179     return succ_end(N);
 180   }
 181 };
 182
 183 struct InverseBasicBlockGraph {
 184   typedef BasicBlock NodeType;
 185   typedef pred_iterator ChildIteratorType;
 186   static inline ChildIteratorType child_begin(NodeType *N) {
 187     return pred_begin(N);
 188   }
 189   static inline ChildIteratorType child_end(NodeType *N) {
 190     return pred_end(N);
 191   }
 192 };
 193
 194 struct ConstInverseBasicBlockGraph {
 195   typedef const BasicBlock NodeType;
 196   typedef pred_const_iterator ChildIteratorType;
 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
 206 //===----------------------------------------------------------------------===//
 207 // Depth First Iterator
 208 //
 209
 210 // Generic Depth First Iterator
 211 template<class GI>
 212 class DFIterator : public std::forward_iterator<typename GI::NodeType,
 213                                                 ptrdiff_t> {
 214   typedef typename GI::NodeType          NodeType;
 215   typedef typename GI::ChildIteratorType ChildItTy;
 216
 217   set<NodeType *>   Visited;    // All of the blocks visited so far...
 218   // VisitStack - Used to maintain the ordering.  Top = current block
 219   // First element is node pointer, second is the 'next child' to visit
 220   stack<pair<NodeType *, ChildItTy> > VisitStack;
 221   const bool Reverse;         // Iterate over children before self?
 222 private:
 223   void reverseEnterNode() {
 224     pair<NodeType *, ChildItTy> &Top = VisitStack.top();
 225     NodeType *Node = Top.first;
 226     ChildItTy &It  = Top.second;
 227     for (; It != GI::child_end(Node); ++It) {
 228       NodeType *Child = *It;
 229       if (!Visited.count(Child)) {
 230         Visited.insert(Child);
 231         VisitStack.push(make_pair(Child, GI::child_begin(Child)));
 232         reverseEnterNode();
 233         return;
 234       }
 235     }
 236   }
 237 public:
 238   typedef DFIterator<GI> _Self;
 239
 240   inline DFIterator(NodeType *Node, bool reverse) : Reverse(reverse) {
 241     Visited.insert(Node);
 242     VisitStack.push(make_pair(Node, GI::child_begin(Node)));
 243     if (Reverse) reverseEnterNode();
 244   }
 245   inline DFIterator() { /* End is when stack is empty */ }
 246
 247   inline bool operator==(const _Self& x) const {
 248     return VisitStack == x.VisitStack;
 249   }
 250   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 251
 252   inline pointer operator*() const {
 253     return VisitStack.top().first;
 254   }
 255
 256   // This is a nonstandard operator-> that dereferences the pointer an extra
 257   // time... so that you can actually call methods ON the Node, because
 258   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
 259   //
 260   inline NodeType *operator->() const { return operator*(); }
 261
 262   inline _Self& operator++() {   // Preincrement
 263     if (Reverse) {               // Reverse Depth First Iterator
 264       if (VisitStack.top().second == GI::child_end(VisitStack.top().first))
 265         VisitStack.pop();
 266       if (!VisitStack.empty())
 267         reverseEnterNode();
 268     } else {                     // Normal Depth First Iterator
 269       do {
 270         pair<NodeType *, ChildItTy> &Top = VisitStack.top();
 271         NodeType *Node = Top.first;
 272         ChildItTy &It  = Top.second;
 273
 274         while (It != GI::child_end(Node)) {
 275           NodeType *Next = *It++;
 276           if (!Visited.count(Next)) {  // Has our next sibling been visited?
 277             // No, do it now.
 278             Visited.insert(Next);
 279             VisitStack.push(make_pair(Next, GI::child_begin(Next)));
 280             return *this;
 281           }
 282         }
 283
 284         // Oops, ran out of successors... go up a level on the stack.
 285         VisitStack.pop();
 286       } while (!VisitStack.empty());
 287     }
 288     return *this;
 289   }
 290
 291   inline _Self operator++(int) { // Postincrement
 292     _Self tmp = *this; ++*this; return tmp;
 293   }
 294
 295   // nodeVisited - return true if this iterator has already visited the
 296   // specified node.  This is public, and will probably be used to iterate over
 297   // nodes that a depth first iteration did not find: ie unreachable nodes.
 298   //
 299   inline bool nodeVisited(NodeType *Node) const {
 300     return Visited.count(Node) != 0;
 301   }
 302 };
 303
 304 inline df_iterator df_begin(Method *M, bool Reverse = false) {
 305   return df_iterator(M->front(), Reverse);
 306 }
 307
 308 inline df_const_iterator df_begin(const Method *M, bool Reverse = false) {
 309   return df_const_iterator(M->front(), Reverse);
 310 }
 311 inline df_iterator       df_end(Method*) {
 312   return df_iterator();
 313 }
 314 inline df_const_iterator df_end(const Method*) {
 315   return df_const_iterator();
 316 }
 317
 318 inline df_iterator df_begin(BasicBlock *BB, bool Reverse = false) {
 319   return df_iterator(BB, Reverse);
 320 }
 321 inline df_const_iterator df_begin(const BasicBlock *BB, bool Reverse = false) {
 322   return df_const_iterator(BB, Reverse);
 323 }
 324
 325 inline df_iterator       df_end(BasicBlock*) {
 326   return df_iterator();
 327 }
 328 inline df_const_iterator df_end(const BasicBlock*) {
 329   return df_const_iterator();
 330 }
 331
 332
 333
 334 inline idf_iterator idf_begin(BasicBlock *BB, bool Reverse = false) {
 335   return idf_iterator(BB, Reverse);
 336 }
 337 inline idf_const_iterator idf_begin(const BasicBlock *BB, bool Reverse = false) {
 338   return idf_const_iterator(BB, Reverse);
 339 }
 340
 341 inline idf_iterator       idf_end(BasicBlock*) {
 342   return idf_iterator();
 343 }
 344 inline idf_const_iterator idf_end(const BasicBlock*) {
 345   return idf_const_iterator();
 346 }
 347
 348 //===----------------------------------------------------------------------===//
 349 // Post Order CFG iterator code
 350 //
 351
 352 template<class BBType, class SuccItTy>
 353 class POIterator : public std::forward_iterator<BBType, ptrdiff_t> {
 354   set<BBType *>   Visited;    // All of the blocks visited so far...
 355   // VisitStack - Used to maintain the ordering.  Top = current block
 356   // First element is basic block pointer, second is the 'next child' to visit
 357   stack<pair<BBType *, SuccItTy> > VisitStack;
 358
 359   void traverseChild() {
 360     while (VisitStack.top().second != succ_end(VisitStack.top().first)) {
 361       BBType *BB = *VisitStack.top().second++;
 362       if (!Visited.count(BB)) {  // If the block is not visited...
 363         Visited.insert(BB);
 364         VisitStack.push(make_pair(BB, succ_begin(BB)));
 365       }
 366     }
 367   }
 368 public:
 369   typedef POIterator<BBType, SuccItTy> _Self;
 370
 371   inline POIterator(BBType *BB) {
 372     Visited.insert(BB);
 373     VisitStack.push(make_pair(BB, succ_begin(BB)));
 374     traverseChild();
 375   }
 376   inline POIterator() { /* End is when stack is empty */ }
 377
 378   inline bool operator==(const _Self& x) const {
 379     return VisitStack == x.VisitStack;
 380   }
 381   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 382
 383   inline pointer operator*() const {
 384     return VisitStack.top().first;
 385   }
 386
 387   // This is a nonstandard operator-> that dereferences the pointer an extra
 388   // time... so that you can actually call methods ON the BasicBlock, because
 389   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
 390   //
 391   inline BBType *operator->() const { return operator*(); }
 392
 393   inline _Self& operator++() {   // Preincrement
 394     VisitStack.pop();
 395     if (!VisitStack.empty())
 396       traverseChild();
 397     return *this;
 398   }
 399
 400   inline _Self operator++(int) { // Postincrement
 401     _Self tmp = *this; ++*this; return tmp;
 402   }
 403 };
 404
 405 inline po_iterator       po_begin(      Method *M) {
 406   return po_iterator(M->front());
 407 }
 408 inline po_const_iterator po_begin(const Method *M) {
 409   return po_const_iterator(M->front());
 410 }
 411 inline po_iterator       po_end  (      Method *M) {
 412   return po_iterator();
 413 }
 414 inline po_const_iterator po_end  (const Method *M) {
 415   return po_const_iterator();
 416 }
 417
 418 inline po_iterator       po_begin(      BasicBlock *BB) {
 419   return po_iterator(BB);
 420 }
 421 inline po_const_iterator po_begin(const BasicBlock *BB) {
 422   return po_const_iterator(BB);
 423 }
 424 inline po_iterator       po_end  (      BasicBlock *BB) {
 425   return po_iterator();
 426 }
 427 inline po_const_iterator po_end  (const BasicBlock *BB) {
 428   return po_const_iterator();
 429 }
 430
 431
 432 //===----------------------------------------------------------------------===//
 433 // Reverse Post Order CFG iterator code
 434 //
 435
 436 class ReversePostOrderTraversal {
 437   vector<BasicBlock*> Blocks;       // Block list in normal PO order
 438   inline void Initialize(BasicBlock *BB) {
 439     copy(po_begin(BB), po_end(BB), back_inserter(Blocks));
 440   }
 441 public:
 442   inline ReversePostOrderTraversal(Method *M) {
 443     Initialize(M->front());
 444   }
 445   inline ReversePostOrderTraversal(BasicBlock *BB) {
 446     Initialize(BB);
 447   }
 448
 449   // Because we want a reverse post order, use reverse iterators from the vector
 450   inline rpo_iterator begin() { return Blocks.rbegin(); }
 451   inline rpo_iterator end()   { return Blocks.rend(); }
 452 };
 453
 454 }    // End namespace cfg
 455
 456 #endif