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