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_LOOP_ITERATOR_H
  25 #define LLVM_ANALYSIS_LOOP_ITERATOR_H
  26
  27 #include "llvm/ADT/DepthFirstIterator.h"
  28 #include "llvm/ADT/PostOrderIterator.h"
  29 #include "llvm/Analysis/LoopInfo.h"
  30
  31 namespace llvm {
  32
  33 class LoopBlocksTraversal;
  34
  35 /// Store the result of a depth first search within basic blocks contained by a
  36 /// single loop.
  37 ///
  38 /// TODO: This could be generalized for any CFG region, or the entire CFG.
  39 class LoopBlocksDFS {
  40 public:
  41   /// Postorder list iterators.
  42   typedef std::vector<BasicBlock*>::const_iterator POIterator;
  43   typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
  44
  45   friend class LoopBlocksTraversal;
  46
  47 private:
  48   Loop *L;
  49
  50   /// Map each block to its postorder number. A block is only mapped after it is
  51   /// preorder visited by DFS. It's postorder number is initially zero and set
  52   /// to nonzero after it is finished by postorder traversal.
  53   DenseMap<BasicBlock*, unsigned> PostNumbers;
  54   std::vector<BasicBlock*> PostBlocks;
  55
  56 public:
  57   LoopBlocksDFS(Loop *Container) :
  58     L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
  59     PostBlocks.reserve(Container->getNumBlocks());
  60   }
  61
  62   Loop *getLoop() const { return L; }
  63
  64   /// Traverse the loop blocks and store the DFS result.
  65   void perform(LoopInfo *LI);
  66
  67   /// Return true if postorder numbers are assigned to all loop blocks.
  68   bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
  69
  70   /// Iterate over the cached postorder blocks.
  71   POIterator beginPostorder() const {
  72     assert(isComplete() && "bad loop DFS");
  73     return PostBlocks.begin();
  74   }
  75   POIterator endPostorder() const { return PostBlocks.end(); }
  76
  77   /// Reverse iterate over the cached postorder blocks.
  78   RPOIterator beginRPO() const {
  79     assert(isComplete() && "bad loop DFS");
  80     return PostBlocks.rbegin();
  81   }
  82   RPOIterator endRPO() const { return PostBlocks.rend(); }
  83
  84   /// Return true if this block has been preorder visited.
  85   bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
  86
  87   /// Return true if this block has a postorder number.
  88   bool hasPostorder(BasicBlock *BB) const {
  89     DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
  90     return I != PostNumbers.end() && I->second;
  91   }
  92
  93   /// Get a block's postorder number.
  94   unsigned getPostorder(BasicBlock *BB) const {
  95     DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
  96     assert(I != PostNumbers.end() && "block not visited by DFS");
  97     assert(I->second && "block not finished by DFS");
  98     return I->second;
  99   }
 100
 101   /// Get a block's reverse postorder number.
 102   unsigned getRPO(BasicBlock *BB) const {
 103     return 1 + PostBlocks.size() - getPostorder(BB);
 104   }
 105
 106   void clear() {
 107     PostNumbers.clear();
 108     PostBlocks.clear();
 109   }
 110 };
 111
 112 /// Define a graph of blocks within a loop. Allows LoopBlocksTraversal to
 113 /// use the generic po_iterator with specialized GraphTraits.
 114 struct LoopBlocksGraph {
 115   Loop *L;
 116
 117   LoopBlocksGraph(Loop *Container) : L(Container) {}
 118 };
 119
 120 template<> struct GraphTraits<LoopBlocksGraph> :
 121     public GraphTraits<BasicBlock*> {
 122
 123   static BasicBlock *getEntryNode(LoopBlocksGraph G) {
 124     return G.L->getHeader();
 125   }
 126 };
 127
 128 /// Traverse the blocks in a loop using a depth-first search.
 129 class LoopBlocksTraversal {
 130 public:
 131   /// Graph traversal iterator.
 132   typedef po_iterator<LoopBlocksGraph, LoopBlocksTraversal, true> POTIterator;
 133
 134 private:
 135   LoopBlocksDFS &DFS;
 136   LoopInfo *LI;
 137
 138 public:
 139   LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
 140     DFS(Storage), LI(LInfo) {}
 141
 142   /// Postorder traversal over the graph. This only needs to be done once.
 143   /// po_iterator "automatically" calls back to visitPreorder and
 144   /// finishPostorder to record the DFS result.
 145   POTIterator begin() {
 146     assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
 147     return po_ext_begin(LoopBlocksGraph(DFS.L), *this);
 148   }
 149   POTIterator end() {
 150     return po_ext_end(LoopBlocksGraph(DFS.L), *this);
 151   }
 152
 153   /// Called by po_iterator upon reaching a block via a CFG edge. If this block
 154   /// is contained in the loop and has not been visited, then mark it preorder
 155   /// visited and return true.
 156   ///
 157   /// TODO: If anyone is interested, we could record preorder numbers here.
 158   bool visitPreorder(BasicBlock *BB) {
 159     if (!DFS.L->contains(LI->getLoopFor(BB)))
 160       return false;
 161
 162     return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
 163   }
 164
 165   /// Called by po_iterator each time it advances, indicating a block's
 166   /// postorder.
 167   void finishPostorder(BasicBlock *BB) {
 168     assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
 169     DFS.PostBlocks.push_back(BB);
 170     DFS.PostNumbers[BB] = DFS.PostBlocks.size();
 171   }
 172
 173   //===----------------------------------------------------------------------
 174   // Implement part of the std::set interface for the purpose of driving the
 175   // generic po_iterator.
 176
 177   /// Return true if the block is outside the loop or has already been visited.
 178   /// Sorry if this is counterintuitive.
 179   bool count(BasicBlock *BB) const {
 180     return !DFS.L->contains(LI->getLoopFor(BB)) || DFS.PostNumbers.count(BB);
 181   }
 182
 183   /// If this block is contained in the loop and has not been visited, return
 184   /// true and assign a preorder number. This is a proxy for visitPreorder
 185   /// called by POIterator.
 186   bool insert(BasicBlock *BB) {
 187     return visitPreorder(BB);
 188   }
 189 };
 190
 191 /// Specialize DFSetTraits to record postorder numbers.
 192 template<> struct DFSetTraits<LoopBlocksTraversal> {
 193   static void finishPostorder(BasicBlock *BB, LoopBlocksTraversal& LBT) {
 194     LBT.finishPostorder(BB);
 195   }
 196 };
 197
 198 } // End namespace llvm
 199
 200 #endif