Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -172,7 +172,7 @@ void initializeLocalStackSlotPassPass(PassRegistry&); void initializeLoopAccessAnalysisPass(PassRegistry&); void initializeLoopDataPrefetchPass(PassRegistry&); -void initializeLoopDeletionPass(PassRegistry&); +void initializeLoopDeletionLegacyPassPass(PassRegistry&); void initializeLoopDistributePass(PassRegistry&); void initializeLoopExtractorPass(PassRegistry&); void initializeLoopIdiomRecognizePass(PassRegistry&); Index: include/llvm/Transforms/Scalar/LoopDeletion.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Scalar/LoopDeletion.h @@ -0,0 +1,38 @@ +//===- LoopDeletion.h - Loop Deletion -------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface for the Loop Deletion Pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H +#define LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class LoopDeletionPass : public PassInfoMixin { +public: + LoopDeletionPass() {} + PreservedAnalyses run(Loop &L, AnalysisManager &AM); + bool runImpl(Loop *L, DominatorTree &DT, ScalarEvolution &SE, + LoopInfo &loopInfo); + +private: + bool isLoopDead(Loop *L, ScalarEvolution &SE, + SmallVectorImpl &exitingBlocks, + SmallVectorImpl &exitBlocks, bool &Changed, + BasicBlock *Preheader); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -78,6 +78,7 @@ #include "llvm/Transforms/Scalar/GuardWidening.h" #include "llvm/Transforms/Scalar/IndVarSimplify.h" #include "llvm/Transforms/Scalar/JumpThreading.h" +#include "llvm/Transforms/Scalar/LoopDeletion.h" #include "llvm/Transforms/Scalar/LoopRotation.h" #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h" #include "llvm/Transforms/Scalar/LowerAtomic.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -176,4 +176,5 @@ LOOP_PASS("print", PrintLoopPass(dbgs())) LOOP_PASS("simplify-cfg", LoopSimplifyCFGPass()) LOOP_PASS("indvars", IndVarSimplifyPass()) +LOOP_PASS("loop-deletion", LoopDeletionPass()) #undef LOOP_PASS Index: lib/Transforms/Scalar/LoopDeletion.cpp =================================================================== --- lib/Transforms/Scalar/LoopDeletion.cpp +++ lib/Transforms/Scalar/LoopDeletion.cpp @@ -14,13 +14,14 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/LoopDeletion.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LoopPass.h" -#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/LoopPassManager.h" #include "llvm/IR/Dominators.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/LoopUtils.h" using namespace llvm; @@ -28,47 +29,13 @@ STATISTIC(NumDeleted, "Number of loops deleted"); -namespace { - class LoopDeletion : public LoopPass { - public: - static char ID; // Pass ID, replacement for typeid - LoopDeletion() : LoopPass(ID) { - initializeLoopDeletionPass(*PassRegistry::getPassRegistry()); - } - - // Possibly eliminate loop L if it is dead. - bool runOnLoop(Loop *L, LPPassManager &) override; - - void getAnalysisUsage(AnalysisUsage &AU) const override { - getLoopAnalysisUsage(AU); - } - - private: - bool isLoopDead(Loop *L, ScalarEvolution &SE, - SmallVectorImpl &exitingBlocks, - SmallVectorImpl &exitBlocks, bool &Changed, - BasicBlock *Preheader); - }; -} - -char LoopDeletion::ID = 0; -INITIALIZE_PASS_BEGIN(LoopDeletion, "loop-deletion", - "Delete dead loops", false, false) -INITIALIZE_PASS_DEPENDENCY(LoopPass) -INITIALIZE_PASS_END(LoopDeletion, "loop-deletion", - "Delete dead loops", false, false) - -Pass *llvm::createLoopDeletionPass() { - return new LoopDeletion(); -} - /// isLoopDead - Determined if a loop is dead. This assumes that we've already /// checked for unique exit and exiting blocks, and that the code is in LCSSA /// form. -bool LoopDeletion::isLoopDead(Loop *L, ScalarEvolution &SE, - SmallVectorImpl &exitingBlocks, - SmallVectorImpl &exitBlocks, - bool &Changed, BasicBlock *Preheader) { +bool LoopDeletionPass::isLoopDead(Loop *L, ScalarEvolution &SE, + SmallVectorImpl &exitingBlocks, + SmallVectorImpl &exitBlocks, + bool &Changed, BasicBlock *Preheader) { BasicBlock *exitBlock = exitBlocks[0]; // Make sure that all PHI entries coming from the loop are loop invariant. @@ -115,27 +82,23 @@ // information to identify readonly and readnone calls. for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); LI != LE; ++LI) { - for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); - BI != BE; ++BI) { + for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); BI != BE; + ++BI) { if (BI->mayHaveSideEffects()) return false; } } - return true; } -/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the -/// observable behavior of the program other than finite running time. Note -/// we do ensure that this never remove a loop that might be infinite, as doing -/// so could change the halting/non-halting nature of a program. -/// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA -/// in order to make various safety checks work. -bool LoopDeletion::runOnLoop(Loop *L, LPPassManager &) { - if (skipLoop(L)) - return false; - - DominatorTree &DT = getAnalysis().getDomTree(); +/// Remove dead loops, by which we mean loops that do not impact the observable +/// behavior of the program other than finite running time. Note we do ensure +/// that this never remove a loop that might be infinite, as doing so could +/// change the halting/non-halting nature of a program. NOTE: This entire +/// process relies pretty heavily on LoopSimplify and LCSSA in order to make +/// various safety checks work. +bool LoopDeletionPass::runImpl(Loop *L, DominatorTree &DT, ScalarEvolution &SE, + LoopInfo &loopInfo) { assert(L->isLCSSAForm(DT) && "Expected LCSSA!"); // We can only remove the loop if there is a preheader that we can @@ -153,10 +116,10 @@ if (L->begin() != L->end()) return false; - SmallVector exitingBlocks; + SmallVector exitingBlocks; L->getExitingBlocks(exitingBlocks); - SmallVector exitBlocks; + SmallVector exitBlocks; L->getUniqueExitBlocks(exitBlocks); // We require that the loop only have a single exit block. Otherwise, we'd @@ -166,8 +129,6 @@ if (exitBlocks.size() != 1) return false; - ScalarEvolution &SE = getAnalysis().getSE(); - // Finally, we have to check that the loop really is dead. bool Changed = false; if (!isLoopDead(L, SE, exitingBlocks, exitBlocks, Changed, preheader)) @@ -211,14 +172,15 @@ // Update the dominator tree and remove the instructions and blocks that will // be deleted from the reference counting scheme. - SmallVector ChildNodes; + SmallVector ChildNodes; for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); LI != LE; ++LI) { // Move all of the block's children to be children of the preheader, which // allows us to remove the domtree entry for the block. ChildNodes.insert(ChildNodes.begin(), DT[*LI]->begin(), DT[*LI]->end()); for (SmallVectorImpl::iterator DI = ChildNodes.begin(), - DE = ChildNodes.end(); DI != DE; ++DI) { + DE = ChildNodes.end(); + DI != DE; ++DI) { DT.changeImmediateDominator(*DI, DT[preheader]); } @@ -240,8 +202,8 @@ // Finally, the blocks from loopinfo. This has to happen late because // otherwise our loop iterators won't work. - LoopInfo &loopInfo = getAnalysis().getLoopInfo(); - SmallPtrSet blocks; + + SmallPtrSet blocks; blocks.insert(L->block_begin(), L->block_end()); for (BasicBlock *BB : blocks) loopInfo.removeBlock(BB); @@ -254,3 +216,56 @@ return Changed; } + +PreservedAnalyses LoopDeletionPass::run(Loop &L, AnalysisManager &AM) { + auto &FAM = AM.getResult(L).getManager(); + Function *F = L.getHeader()->getParent(); + + auto &DT = *FAM.getCachedResult(*F); + auto &SE = *FAM.getCachedResult(*F); + auto &LI = *FAM.getCachedResult(*F); + + bool Changed = runImpl(&L, DT, SE, LI); + if (!Changed) + return PreservedAnalyses::all(); + + return getLoopPassPreservedAnalyses(); +} + +namespace { +class LoopDeletionLegacyPass : public LoopPass { +public: + static char ID; // Pass ID, replacement for typeid + LoopDeletionLegacyPass() : LoopPass(ID) { + initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + // Possibly eliminate loop L if it is dead. + bool runOnLoop(Loop *L, LPPassManager &) override; + + void getAnalysisUsage(AnalysisUsage &AU) const override { + getLoopAnalysisUsage(AU); + } +}; +} + +char LoopDeletionLegacyPass::ID = 0; +INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion", + "Delete dead loops", false, false) +INITIALIZE_PASS_DEPENDENCY(LoopPass) +INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion", + "Delete dead loops", false, false) + +Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); } + +bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &) { + if (skipLoop(L)) + return false; + + DominatorTree &DT = getAnalysis().getDomTree(); + ScalarEvolution &SE = getAnalysis().getSE(); + LoopInfo &loopInfo = getAnalysis().getLoopInfo(); + + LoopDeletionPass Impl; + return Impl.runImpl(L, DT, SE, loopInfo); +} Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -50,7 +50,7 @@ initializeJumpThreadingPass(Registry); initializeLICMPass(Registry); initializeLoopDataPrefetchPass(Registry); - initializeLoopDeletionPass(Registry); + initializeLoopDeletionLegacyPassPass(Registry); initializeLoopAccessAnalysisPass(Registry); initializeLoopInstSimplifyPass(Registry); initializeLoopInterchangePass(Registry); Index: test/Transforms/LoopDeletion/multiple-exit-conditions.ll =================================================================== --- test/Transforms/LoopDeletion/multiple-exit-conditions.ll +++ test/Transforms/LoopDeletion/multiple-exit-conditions.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -loop-deletion -S | FileCheck %s +; RUN: opt < %s -passes='require,loop(loop-deletion)' -S | FileCheck %s ; ScalarEvolution can prove the loop iteration is finite, even though ; it can't represent the exact trip count as an expression. That's