include/llvm/Analysis/LoopIterator.h

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