Home | History | Annotate | Download | only in Analysis 
      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 /// Traverse the blocks in a loop using a depth-first search.
    113 class LoopBlocksTraversal {
    114 public:
    115   /// Graph traversal iterator.
    116   typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
    117 
    118 private:
    119   LoopBlocksDFS &DFS;
    120   LoopInfo *LI;
    121 
    122 public:
    123   LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
    124     DFS(Storage), LI(LInfo) {}
    125 
    126   /// Postorder traversal over the graph. This only needs to be done once.
    127   /// po_iterator "automatically" calls back to visitPreorder and
    128   /// finishPostorder to record the DFS result.
    129   POTIterator begin() {
    130     assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
    131     assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
    132     return po_ext_begin(DFS.L->getHeader(), *this);
    133   }
    134   POTIterator end() {
    135     // po_ext_end interface requires a basic block, but ignores its value.
    136     return po_ext_end(DFS.L->getHeader(), *this);
    137   }
    138 
    139   /// Called by po_iterator upon reaching a block via a CFG edge. If this block
    140   /// is contained in the loop and has not been visited, then mark it preorder
    141   /// visited and return true.
    142   ///
    143   /// TODO: If anyone is interested, we could record preorder numbers here.
    144   bool visitPreorder(BasicBlock *BB) {
    145     if (!DFS.L->contains(LI->getLoopFor(BB)))
    146       return false;
    147 
    148     return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
    149   }
    150 
    151   /// Called by po_iterator each time it advances, indicating a block's
    152   /// postorder.
    153   void finishPostorder(BasicBlock *BB) {
    154     assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
    155     DFS.PostBlocks.push_back(BB);
    156     DFS.PostNumbers[BB] = DFS.PostBlocks.size();
    157   }
    158 
    159   //===----------------------------------------------------------------------
    160   // Implement part of the std::set interface for the purpose of driving the
    161   // generic po_iterator.
    162 
    163   /// Return true if the block is outside the loop or has already been visited.
    164   /// Sorry if this is counterintuitive.
    165   bool count(BasicBlock *BB) const {
    166     return !DFS.L->contains(LI->getLoopFor(BB)) || DFS.PostNumbers.count(BB);
    167   }
    168 
    169   /// If this block is contained in the loop and has not been visited, return
    170   /// true and assign a preorder number. This is a proxy for visitPreorder
    171   /// called by POIterator.
    172   bool insert(BasicBlock *BB) {
    173     return visitPreorder(BB);
    174   }
    175 };
    176 
    177 /// Specialize DFSetTraits to record postorder numbers.
    178 template<> struct DFSetTraits<LoopBlocksTraversal> {
    179   static void finishPostorder(BasicBlock *BB, LoopBlocksTraversal& LBT) {
    180     LBT.finishPostorder(BB);
    181   }
    182 };
    183 
    184 } // End namespace llvm
    185 
    186 #endif
    187