//===- 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/DependenceAnalysis.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 { … }