include/llvm/Analysis/LoopIterator.h

   1 //===--------- LoopIterator.h - Iterate over loop blocks --------*- 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 // This file defines iterators to visit the basic blocks within a loop.
  10 //
  11 // These iterators currently visit blocks within subloops as well.
  12 // Unfortunately we have no efficient way of summarizing loop exits which would
  13 // allow skipping subloops during traversal.
  14 //
  15 // If you want to visit all blocks in a loop and don't need an ordered traveral,
  16 // use Loop::block_begin() instead.
  17 //
  18 // This is intentionally designed to work with ill-formed loops in which the
  19 // backedge has been deleted. The only prerequisite is that all blocks
  20 // contained within the loop according to the most recent LoopInfo analysis are
  21 // reachable from the loop header.
  22 //===----------------------------------------------------------------------===//
  23
  24 #ifndef LLVM_ANALYSIS_LOOPITERATOR_H
  25 #define LLVM_ANALYSIS_LOOPITERATOR_H
  26
  27 #include "llvm/ADT/PostOrderIterator.h"
  28 #include "llvm/Analysis/LoopInfo.h"
  29
  30 namespace llvm {
  31
  32 class LoopBlocksTraversal;
  33
  34 /// Store the result of a depth first search within basic blocks contained by a
  35 /// single loop.
  36 ///
  37 /// TODO: This could be generalized for any CFG region, or the entire CFG.
  38 class LoopBlocksDFS {
  39 public:
  40   /// Postorder list iterators.
  41   typedef std::vector<BasicBlock*>::const_iterator POIterator;
  42   typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
  43
  44   friend class LoopBlocksTraversal;
  45
  46 private:
  47   Loop *L;
  48
  49   /// Map each block to its postorder number. A block is only mapped after it is
  50   /// preorder visited by DFS. It's postorder number is initially zero and set
  51   /// to nonzero after it is finished by postorder traversal.
  52   DenseMap<BasicBlock*, unsigned> PostNumbers;
  53   std::vector<BasicBlock*> PostBlocks;
  54
  55 public:
  56   LoopBlocksDFS(Loop *Container) :
  57     L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
  58     PostBlocks.reserve(Container->getNumBlocks());
  59   }
  60
  61   Loop *getLoop() const { return L; }
  62
  63   /// Traverse the loop blocks and store the DFS result.
  64   void perform(LoopInfo *LI);
  65
  66   /// Return true if postorder numbers are assigned to all loop blocks.
  67   bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
  68
  69   /// Iterate over the cached postorder blocks.
  70   POIterator beginPostorder() const {
  71     assert(isComplete() && "bad loop DFS");
  72     return PostBlocks.begin();
  73   }
  74   POIterator endPostorder() const { return PostBlocks.end(); }
  75
  76   /// Reverse iterate over the cached postorder blocks.
  77   RPOIterator beginRPO() const {
  78     assert(isComplete() && "bad loop DFS");
  79     return PostBlocks.rbegin();
  80   }
  81   RPOIterator endRPO() const { return PostBlocks.rend(); }
  82
  83   /// Return true if this block has been preorder visited.
  84   bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
  85
  86   /// Return true if this block has a postorder number.
  87   bool hasPostorder(BasicBlock *BB) const {
  88     DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
  89     return I != PostNumbers.end() && I->second;
  90   }
  91
  92   /// Get a block's postorder number.
  93   unsigned getPostorder(BasicBlock *BB) const {
  94     DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
  95     assert(I != PostNumbers.end() && "block not visited by DFS");
  96     assert(I->second && "block not finished by DFS");
  97     return I->second;
  98   }
  99
 100   /// Get a block's reverse postorder number.
 101   unsigned getRPO(BasicBlock *BB) const {
 102     return 1 + PostBlocks.size() - getPostorder(BB);
 103   }
 104
 105   void clear() {
 106     PostNumbers.clear();
 107     PostBlocks.clear();
 108   }
 109 };
 110
 111 /// Specialize po_iterator_storage to record postorder numbers.
 112 template<> class po_iterator_storage<LoopBlocksTraversal, true> {
 113   LoopBlocksTraversal &LBT;
 114 public:
 115   po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
 116   // These functions are defined below.
 117   bool insertEdge(BasicBlock *From, BasicBlock *To);
 118   void finishPostorder(BasicBlock *BB);
 119 };
 120
 121 /// Traverse the blocks in a loop using a depth-first search.
 122 class LoopBlocksTraversal {
 123 public:
 124   /// Graph traversal iterator.
 125   typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
 126
 127 private:
 128   LoopBlocksDFS &DFS;
 129   LoopInfo *LI;
 130
 131 public:
 132   LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
 133     DFS(Storage), LI(LInfo) {}
 134
 135   /// Postorder traversal over the graph. This only needs to be done once.
 136   /// po_iterator "automatically" calls back to visitPreorder and
 137   /// finishPostorder to record the DFS result.
 138   POTIterator begin() {
 139     assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
 140     assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
 141     return po_ext_begin(DFS.L->getHeader(), *this);
 142   }
 143   POTIterator end() {
 144     // po_ext_end interface requires a basic block, but ignores its value.
 145     return po_ext_end(DFS.L->getHeader(), *this);
 146   }
 147
 148   /// Called by po_iterator upon reaching a block via a CFG edge. If this block
 149   /// is contained in the loop and has not been visited, then mark it preorder
 150   /// visited and return true.
 151   ///
 152   /// TODO: If anyone is interested, we could record preorder numbers here.
 153   bool visitPreorder(BasicBlock *BB) {
 154     if (!DFS.L->contains(LI->getLoopFor(BB)))
 155       return false;
 156
 157     return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
 158   }
 159
 160   /// Called by po_iterator each time it advances, indicating a block's
 161   /// postorder.
 162   void finishPostorder(BasicBlock *BB) {
 163     assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
 164     DFS.PostBlocks.push_back(BB);
 165     DFS.PostNumbers[BB] = DFS.PostBlocks.size();
 166   }
 167 };
 168
 169 inline bool po_iterator_storage<LoopBlocksTraversal, true>::
 170 insertEdge(BasicBlock *From, BasicBlock *To) {
 171   return LBT.visitPreorder(To);
 172 }
 173
 174 inline void po_iterator_storage<LoopBlocksTraversal, true>::
 175 finishPostorder(BasicBlock *BB) {
 176   LBT.finishPostorder(BB);
 177 }
 178
 179 } // End namespace llvm
 180
 181 #endif