LoopIterator.h

Go to the documentation of this file.

//===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
// This file defines iterators to visit the basic blocks within a loop.
//
// These iterators currently visit blocks within subloops as well.
// Unfortunately we have no efficient way of summarizing loop exits which would
// allow skipping subloops during traversal.
//
// If you want to visit all blocks in a loop and don't need an ordered traveral,
// use Loop::block_begin() instead.
//
// This is intentionally designed to work with ill-formed loops in which the
// backedge has been deleted. The only prerequisite is that all blocks
// contained within the loop according to the most recent LoopInfo analysis are
// reachable from the loop header.
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_ANALYSIS_LOOPITERATOR_H
#define LLVM_ANALYSIS_LOOPITERATOR_H
 
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Analysis/LoopInfo.h"
 
namespace llvm {
 
class LoopBlocksTraversal;
 
/// Store the result of a depth first search within basic blocks contained by a
/// single loop.
///
/// TODO: This could be generalized for any CFG region, or the entire CFG.
class LoopBlocksDFS {
public:
  /// Postorder list iterators.
  typedef std::vector<BasicBlock*>::const_iterator POIterator;
  typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
 
  friend class LoopBlocksTraversal;
 
private:
  Loop *L;
 
  /// Map each block to its postorder number. A block is only mapped after it is
  /// preorder visited by DFS. It's postorder number is initially zero and set
  /// to nonzero after it is finished by postorder traversal.
  DenseMap<BasicBlock*, unsigned> PostNumbers;
  std::vector<BasicBlock*> PostBlocks;
 
public:
  LoopBlocksDFS(Loop *Container) :
    L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
    PostBlocks.reserve(Container->getNumBlocks());
  }
 
  Loop *getLoop() const { return L; }
 
  /// Traverse the loop blocks and store the DFS result.
  LLVM_ABI void perform(const LoopInfo *LI);
 
  /// Return true if postorder numbers are assigned to all loop blocks.
  bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
 
  /// Iterate over the cached postorder blocks.
  POIterator beginPostorder() const {
    assert(isComplete() && "bad loop DFS");
    return PostBlocks.begin();
  }
  POIterator endPostorder() const { return PostBlocks.end(); }
 
  /// Reverse iterate over the cached postorder blocks.
  RPOIterator beginRPO() const {
    assert(isComplete() && "bad loop DFS");
    return PostBlocks.rbegin();
  }
  RPOIterator endRPO() const { return PostBlocks.rend(); }
 
  /// Return true if this block has been preorder visited.
  bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
 
  /// Return true if this block has a postorder number.
  bool hasPostorder(BasicBlock *BB) const {
    auto I = PostNumbers.find(BB);
    return I != PostNumbers.end() && I->second;
  }
 
  /// Get a block's postorder number.
  unsigned getPostorder(BasicBlock *BB) const {
    auto I = PostNumbers.find(BB);
    assert(I != PostNumbers.end() && "block not visited by DFS");
    assert(I->second && "block not finished by DFS");
    return I->second;
  }
 
  /// Get a block's reverse postorder number.
  unsigned getRPO(BasicBlock *BB) const {
    return 1 + PostBlocks.size() - getPostorder(BB);
  }
 
  void clear() {
    PostNumbers.clear();
    PostBlocks.clear();
  }
};
 
/// Wrapper class to LoopBlocksDFS that provides a standard begin()/end()
/// interface for the DFS reverse post-order traversal of blocks in a loop body.
class LoopBlocksRPO {
private:
  LoopBlocksDFS DFS;
 
public:
  LoopBlocksRPO(Loop *Container) : DFS(Container) {}
 
  /// Traverse the loop blocks and store the DFS result.
  void perform(const LoopInfo *LI) {
    DFS.perform(LI);
  }
 
  /// Reverse iterate over the cached postorder blocks.
  LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); }
  LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); }
};
 
/// Traverse the blocks in a loop using a depth-first search.
class LoopBlocksTraversal
    : public PostOrderTraversalBase<LoopBlocksTraversal,
                                    GraphTraits<Function *>> {
  LoopBlocksDFS &DFS;
  const LoopInfo *LI;
 
public:
  LoopBlocksTraversal(LoopBlocksDFS &Storage, const LoopInfo *LInfo)
      : DFS(Storage), LI(LInfo) {}
 
  /// Postorder traversal over the graph. This only needs to be done once.
  /// PostOrderTraversalBase "automatically" calls back to insertEdge and
  /// finishPostorder to record the DFS result.
  iterator begin() {
    assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
    assert(DFS.L->getNumBlocks() && "cannot handle an empty graph");
    init(DFS.L->getHeader());
    return PostOrderTraversalBase::begin();
  }
  iterator end() { return PostOrderTraversalBase::end(); }
 
  /// Called upon reaching a block via a CFG edge. If this block is contained
  /// in the loop and has not been visited, then mark it preorder visited and
  /// return true (i.e., traverse the edge).
  ///
  /// TODO: If anyone is interested, we could record preorder numbers here.
  bool insertEdge(std::optional<BasicBlock *> /*From*/, BasicBlock *BB) {
    if (!DFS.L->contains(LI->getLoopFor(BB)))
      return false;
 
    return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
  }
 
  /// Called each time the iterator advances, indicating a block's postorder.
  void finishPostorder(BasicBlock *BB) {
    assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
    DFS.PostBlocks.push_back(BB);
    DFS.PostNumbers[BB] = DFS.PostBlocks.size();
  }
};
 
} // End namespace llvm
 
#endif