LCOV - code coverage report
Current view: top level - include/llvm/Analysis - LoopIterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 20 27 74.1 %
Date: 2018-10-14 09:39:32 Functions: 3 6 50.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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        8424 :   LoopBlocksDFS(Loop *Container) :
     117       25272 :     L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
     118        8424 :     PostBlocks.reserve(Container->getNumBlocks());
     119        8424 :   }
     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           4 :     return PostBlocks.begin();
     133             :   }
     134           4 :   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        4463 : class LoopBlocksRPO {
     174             : private:
     175             :   LoopBlocksDFS DFS;
     176             : 
     177             : public:
     178        4463 :   LoopBlocksRPO(Loop *Container) : DFS(Container) {}
     179             : 
     180             :   /// Traverse the loop blocks and store the DFS result.
     181             :   void perform(LoopInfo *LI) {
     182        4463 :     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        8400 :   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        8400 :   LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
     212        8400 :     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        8400 :   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       16800 :     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        8400 :     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       61007 :   bool visitPreorder(BasicBlock *BB) {
     233      122014 :     if (!DFS.L->contains(LI->getLoopFor(BB)))
     234             :       return false;
     235             : 
     236       44969 :     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           0 :   void finishPostorder(BasicBlock *BB) {
     242             :     assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
     243           0 :     DFS.PostBlocks.push_back(BB);
     244           0 :     DFS.PostNumbers[BB] = DFS.PostBlocks.size();
     245           0 :   }
     246             : };
     247             : 
     248           0 : inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
     249             :     Optional<BasicBlock *> From, BasicBlock *To) {
     250       61007 :   return LBT.visitPreorder(To);
     251             : }
     252             : 
     253           0 : inline void po_iterator_storage<LoopBlocksTraversal, true>::
     254             : finishPostorder(BasicBlock *BB) {
     255       29771 :   LBT.finishPostorder(BB);
     256           0 : }
     257             : 
     258             : } // End namespace llvm
     259             : 
     260             : #endif

Generated by: LCOV version 1.13