LoopSimplify.cpp | Explore in Territory

//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
//
// 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 pass performs several transformations to transform natural loops into a
// simpler form, which makes subsequent analyses and transformations simpler and
// more effective.
//
// Loop pre-header insertion guarantees that there is a single, non-critical
// entry edge from outside of the loop to the loop header.  This simplifies a
// number of analyses and transformations, such as LICM.
//
// Loop exit-block insertion guarantees that all exit blocks from the loop
// (blocks which are outside of the loop that have predecessors inside of the
// loop) only have predecessors from inside of the loop (and are thus dominated
// by the loop header).  This simplifies transformations such as store-sinking
// that are built into LICM.
//
// This pass also guarantees that loops will have exactly one backedge.
//
// Indirectbr instructions introduce several complications. If the loop
// contains or is entered by an indirectbr instruction, it may not be possible
// to transform the loop and make these guarantees. Client code should check
// that these conditions are true before relying on them.
//
// Similar complications arise from callbr instructions, particularly in
// asm-goto where blockaddress expressions are used.
//
// Note that the simplifycfg pass will clean up blocks which are split out but
// end up being unnecessary, so usage of this pass should not pessimize
// generated code.
//
// This pass obviously modifies the CFG, but updates loop information and
// dominator information.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumNested  , "Number of nested loops split out");

// If the block isn't already, move the new block to right after some 'outside
// block' block.  This prevents the preheader from being placed inside the loop
// body, e.g. when the loop hasn't been rotated.
static void placeSplitBlockCarefully(BasicBlock *NewBB,
                                     SmallVectorImpl<BasicBlock *> &SplitPreds,
                                     Loop *L) { … }

/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
/// preheader, this method is called to insert one.  This method has two phases:
/// preheader insertion and analysis updating.
///
BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT,
                                         LoopInfo *LI, MemorySSAUpdater *MSSAU,
                                         bool PreserveLCSSA) { … }

/// Add the specified block, and all of its predecessors, to the specified set,
/// if it's not already in there.  Stop predecessor traversal when we reach
/// StopBlock.
static void addBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
                                  SmallPtrSetImpl<BasicBlock *> &Blocks) { … }

/// The first part of loop-nestification is to find a PHI node that tells
/// us how to partition the loops.
static PHINode *findPHIToPartitionLoops(Loop *L, DominatorTree *DT,
                                        AssumptionCache *AC) { … }

/// If this loop has multiple backedges, try to pull one of them out into
/// a nested loop.
///
/// This is important for code that looks like
/// this:
///
///  Loop:
///     ...
///     br cond, Loop, Next
///     ...
///     br cond2, Loop, Out
///
/// To identify this common case, we look at the PHI nodes in the header of the
/// loop.  PHI nodes with unchanging values on one backedge correspond to values
/// that change in the "outer" loop, but not in the "inner" loop.
///
/// If we are able to separate out a loop, return the new outer loop that was
/// created.
///
static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
                                DominatorTree *DT, LoopInfo *LI,
                                ScalarEvolution *SE, bool PreserveLCSSA,
                                AssumptionCache *AC, MemorySSAUpdater *MSSAU) { … }

/// This method is called when the specified loop has more than one
/// backedge in it.
///
/// If this occurs, revector all of these backedges to target a new basic block
/// and have that block branch to the loop header.  This ensures that loops
/// have exactly one backedge.
static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader,
                                             DominatorTree *DT, LoopInfo *LI,
                                             MemorySSAUpdater *MSSAU) { … }

/// Simplify one loop and queue further loops for simplification.
static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
                            DominatorTree *DT, LoopInfo *LI,
                            ScalarEvolution *SE, AssumptionCache *AC,
                            MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { … }

bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
                        ScalarEvolution *SE, AssumptionCache *AC,
                        MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { … }

namespace {
  struct LoopSimplify : public FunctionPass { … };
}

char LoopSimplify::ID = …;
INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
                "Canonicalize natural loops", false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
                "Canonicalize natural loops", false, false)

// Publicly exposed interface to pass...
char &llvm::LoopSimplifyID = …;
Pass *llvm::createLoopSimplifyPass() { … }

/// runOnFunction - Run down all loops in the CFG (recursively, but we could do
/// it in any convenient order) inserting preheaders...
///
bool LoopSimplify::runOnFunction(Function &F) { … }

PreservedAnalyses LoopSimplifyPass::run(Function &F,
                                        FunctionAnalysisManager &AM) { … }

// FIXME: Restore this code when we re-enable verification in verifyAnalysis
// below.
#if 0
static void verifyLoop(Loop *L) {
  // Verify subloops.
  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
    verifyLoop(*I);

  // It used to be possible to just assert L->isLoopSimplifyForm(), however
  // with the introduction of indirectbr, there are now cases where it's
  // not possible to transform a loop as necessary. We can at least check
  // that there is an indirectbr near any time there's trouble.

  // Indirectbr can interfere with preheader and unique backedge insertion.
  if (!L->getLoopPreheader() || !L->getLoopLatch()) {
    bool HasIndBrPred = false;
    for (BasicBlock *Pred : predecessors(L->getHeader()))
      if (isa<IndirectBrInst>(Pred->getTerminator())) {
        HasIndBrPred = true;
        break;
      }
    assert(HasIndBrPred &&
           "LoopSimplify has no excuse for missing loop header info!");
    (void)HasIndBrPred;
  }

  // Indirectbr can interfere with exit block canonicalization.
  if (!L->hasDedicatedExits()) {
    bool HasIndBrExiting = false;
    SmallVector<BasicBlock*, 8> ExitingBlocks;
    L->getExitingBlocks(ExitingBlocks);
    for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
      if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) {
        HasIndBrExiting = true;
        break;
      }
    }

    assert(HasIndBrExiting &&
           "LoopSimplify has no excuse for missing exit block info!");
    (void)HasIndBrExiting;
  }
}
#endif

void LoopSimplify::verifyAnalysis() const { … }
llvm/llvm/lib/Transforms/Utils/LoopSimplify.cpp
