contrib/llvm/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 // A traits type that is intended to be used in graph algorithms. The graph
  35 // traits starts at the loop header, and traverses the BasicBlocks that are in
  36 // the loop body, but not the loop header. Since the loop header is skipped,
  37 // the back edges are excluded.
  38 //
  39 // TODO: Explore the possibility to implement LoopBlocksTraversal in terms of
  40 //       LoopBodyTraits, so that insertEdge doesn't have to be specialized.
  41 struct LoopBodyTraits {
  42   using NodeRef = std::pair<const Loop *, BasicBlock *>;
  43
  44   // This wraps a const Loop * into the iterator, so we know which edges to
  45   // filter out.
  46   class WrappedSuccIterator
  47       : public iterator_adaptor_base<
  48             WrappedSuccIterator, succ_iterator,
  49             typename std::iterator_traits<succ_iterator>::iterator_category,
  50             NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {
  51     using BaseT = iterator_adaptor_base<
  52         WrappedSuccIterator, succ_iterator,
  53         typename std::iterator_traits<succ_iterator>::iterator_category,
  54         NodeRef, std::ptrdiff_t, NodeRef *, NodeRef>;
  55
  56     const Loop *L;
  57
  58   public:
  59     WrappedSuccIterator(succ_iterator Begin, const Loop *L)
  60         : BaseT(Begin), L(L) {}
  61
  62     NodeRef operator*() const { return {L, *I}; }
  63   };
  64
  65   struct LoopBodyFilter {
  66     bool operator()(NodeRef N) const {
  67       const Loop *L = N.first;
  68       return N.second != L->getHeader() && L->contains(N.second);
  69     }
  70   };
  71
  72   using ChildIteratorType =
  73       filter_iterator<WrappedSuccIterator, LoopBodyFilter>;
  74
  75   static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; }
  76
  77   static ChildIteratorType child_begin(NodeRef Node) {
  78     return make_filter_range(make_range<WrappedSuccIterator>(
  79                                  {succ_begin(Node.second), Node.first},
  80                                  {succ_end(Node.second), Node.first}),
  81                              LoopBodyFilter{})
  82         .begin();
  83   }
  84
  85   static ChildIteratorType child_end(NodeRef Node) {
  86     return make_filter_range(make_range<WrappedSuccIterator>(
  87                                  {succ_begin(Node.second), Node.first},
  88                                  {succ_end(Node.second), Node.first}),
  89                              LoopBodyFilter{})
  90         .end();
  91   }
  92 };
  93
  94 /// Store the result of a depth first search within basic blocks contained by a
  95 /// single loop.
  96 ///
  97 /// TODO: This could be generalized for any CFG region, or the entire CFG.
  98 class LoopBlocksDFS {
  99 public:
 100   /// Postorder list iterators.
 101   typedef std::vector<BasicBlock*>::const_iterator POIterator;
 102   typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
 103
 104   friend class LoopBlocksTraversal;
 105
 106 private:
 107   Loop *L;
 108
 109   /// Map each block to its postorder number. A block is only mapped after it is
 110   /// preorder visited by DFS. It's postorder number is initially zero and set
 111   /// to nonzero after it is finished by postorder traversal.
 112   DenseMap<BasicBlock*, unsigned> PostNumbers;
 113   std::vector<BasicBlock*> PostBlocks;
 114
 115 public:
 116   LoopBlocksDFS(Loop *Container) :
 117     L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
 118     PostBlocks.reserve(Container->getNumBlocks());
 119   }
 120
 121   Loop *getLoop() const { return L; }
 122
 123   /// Traverse the loop blocks and store the DFS result.
 124   void perform(LoopInfo *LI);
 125
 126   /// Return true if postorder numbers are assigned to all loop blocks.
 127   bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
 128
 129   /// Iterate over the cached postorder blocks.
 130   POIterator beginPostorder() const {
 131     assert(isComplete() && "bad loop DFS");
 132     return PostBlocks.begin();
 133   }
 134   POIterator endPostorder() const { return PostBlocks.end(); }
 135
 136   /// Reverse iterate over the cached postorder blocks.
 137   RPOIterator beginRPO() const {
 138     assert(isComplete() && "bad loop DFS");
 139     return PostBlocks.rbegin();
 140   }
 141   RPOIterator endRPO() const { return PostBlocks.rend(); }
 142
 143   /// Return true if this block has been preorder visited.
 144   bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
 145
 146   /// Return true if this block has a postorder number.
 147   bool hasPostorder(BasicBlock *BB) const {
 148     DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
 149     return I != PostNumbers.end() && I->second;
 150   }
 151
 152   /// Get a block's postorder number.
 153   unsigned getPostorder(BasicBlock *BB) const {
 154     DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
 155     assert(I != PostNumbers.end() && "block not visited by DFS");
 156     assert(I->second && "block not finished by DFS");
 157     return I->second;
 158   }
 159
 160   /// Get a block's reverse postorder number.
 161   unsigned getRPO(BasicBlock *BB) const {
 162     return 1 + PostBlocks.size() - getPostorder(BB);
 163   }
 164
 165   void clear() {
 166     PostNumbers.clear();
 167     PostBlocks.clear();
 168   }
 169 };
 170
 171 /// Wrapper class to LoopBlocksDFS that provides a standard begin()/end()
 172 /// interface for the DFS reverse post-order traversal of blocks in a loop body.
 173 class LoopBlocksRPO {
 174 private:
 175   LoopBlocksDFS DFS;
 176
 177 public:
 178   LoopBlocksRPO(Loop *Container) : DFS(Container) {}
 179
 180   /// Traverse the loop blocks and store the DFS result.
 181   void perform(LoopInfo *LI) {
 182     DFS.perform(LI);
 183   }
 184
 185   /// Reverse iterate over the cached postorder blocks.
 186   LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); }
 187   LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); }
 188 };
 189
 190 /// Specialize po_iterator_storage to record postorder numbers.
 191 template<> class po_iterator_storage<LoopBlocksTraversal, true> {
 192   LoopBlocksTraversal &LBT;
 193 public:
 194   po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
 195   // These functions are defined below.
 196   bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To);
 197   void finishPostorder(BasicBlock *BB);
 198 };
 199
 200 /// Traverse the blocks in a loop using a depth-first search.
 201 class LoopBlocksTraversal {
 202 public:
 203   /// Graph traversal iterator.
 204   typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
 205
 206 private:
 207   LoopBlocksDFS &DFS;
 208   LoopInfo *LI;
 209
 210 public:
 211   LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
 212     DFS(Storage), LI(LInfo) {}
 213
 214   /// Postorder traversal over the graph. This only needs to be done once.
 215   /// po_iterator "automatically" calls back to visitPreorder and
 216   /// finishPostorder to record the DFS result.
 217   POTIterator begin() {
 218     assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
 219     assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
 220     return po_ext_begin(DFS.L->getHeader(), *this);
 221   }
 222   POTIterator end() {
 223     // po_ext_end interface requires a basic block, but ignores its value.
 224     return po_ext_end(DFS.L->getHeader(), *this);
 225   }
 226
 227   /// Called by po_iterator upon reaching a block via a CFG edge. If this block
 228   /// is contained in the loop and has not been visited, then mark it preorder
 229   /// visited and return true.
 230   ///
 231   /// TODO: If anyone is interested, we could record preorder numbers here.
 232   bool visitPreorder(BasicBlock *BB) {
 233     if (!DFS.L->contains(LI->getLoopFor(BB)))
 234       return false;
 235
 236     return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
 237   }
 238
 239   /// Called by po_iterator each time it advances, indicating a block's
 240   /// postorder.
 241   void finishPostorder(BasicBlock *BB) {
 242     assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
 243     DFS.PostBlocks.push_back(BB);
 244     DFS.PostNumbers[BB] = DFS.PostBlocks.size();
 245   }
 246 };
 247
 248 inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
 249     Optional<BasicBlock *> From, BasicBlock *To) {
 250   return LBT.visitPreorder(To);
 251 }
 252
 253 inline void po_iterator_storage<LoopBlocksTraversal, true>::
 254 finishPostorder(BasicBlock *BB) {
 255   LBT.finishPostorder(BB);
 256 }
 257
 258 } // End namespace llvm
 259
 260 #endif