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_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
    182