summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/InitializePasses.h2
-rw-r--r--llvm/include/llvm/Transforms/Scalar/LoopDeletion.h38
-rw-r--r--llvm/lib/Passes/PassBuilder.cpp1
-rw-r--r--llvm/lib/Passes/PassRegistry.def1
-rw-r--r--llvm/lib/Transforms/Scalar/LoopDeletion.cpp129
-rw-r--r--llvm/lib/Transforms/Scalar/Scalar.cpp2
-rw-r--r--llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll1
7 files changed, 115 insertions, 59 deletions
diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h
index 34b156e8270..3042ec2c318 100644
--- a/llvm/include/llvm/InitializePasses.h
+++ b/llvm/include/llvm/InitializePasses.h
@@ -175,7 +175,7 @@ void initializeLoadStoreVectorizerPass(PassRegistry&);
void initializeLocalStackSlotPassPass(PassRegistry&);
void initializeLoopAccessLegacyAnalysisPass(PassRegistry&);
void initializeLoopDataPrefetchPass(PassRegistry&);
-void initializeLoopDeletionPass(PassRegistry&);
+void initializeLoopDeletionLegacyPassPass(PassRegistry&);
void initializeLoopDistributePass(PassRegistry&);
void initializeLoopExtractorPass(PassRegistry&);
void initializeLoopIdiomRecognizeLegacyPassPass(PassRegistry&);
diff --git a/llvm/include/llvm/Transforms/Scalar/LoopDeletion.h b/llvm/include/llvm/Transforms/Scalar/LoopDeletion.h
new file mode 100644
index 00000000000..ed5a9833e57
--- /dev/null
+++ b/llvm/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<LoopDeletionPass> {
+public:
+ LoopDeletionPass() {}
+ PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM);
+ bool runImpl(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
+ LoopInfo &loopInfo);
+
+private:
+ bool isLoopDead(Loop *L, ScalarEvolution &SE,
+ SmallVectorImpl<BasicBlock *> &exitingBlocks,
+ SmallVectorImpl<BasicBlock *> &exitBlocks, bool &Changed,
+ BasicBlock *Preheader);
+};
+}
+
+#endif // LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H
diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
index eed8b2d36b9..285d9e88eed 100644
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/lib/Passes/PassBuilder.cpp
@@ -89,6 +89,7 @@
#include "llvm/Transforms/Scalar/IndVarSimplify.h"
#include "llvm/Transforms/Scalar/JumpThreading.h"
#include "llvm/Transforms/Scalar/LICM.h"
+#include "llvm/Transforms/Scalar/LoopDeletion.h"
#include "llvm/Transforms/Scalar/LoopIdiomRecognize.h"
#include "llvm/Transforms/Scalar/LoopRotation.h"
#include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def
index ffa0864edc2..dcda4610bdc 100644
--- a/llvm/lib/Passes/PassRegistry.def
+++ b/llvm/lib/Passes/PassRegistry.def
@@ -192,6 +192,7 @@ LOOP_PASS("loop-idiom", LoopIdiomRecognizePass())
LOOP_PASS("rotate", LoopRotatePass())
LOOP_PASS("no-op-loop", NoOpLoopPass())
LOOP_PASS("print", PrintLoopPass(dbgs()))
+LOOP_PASS("loop-deletion", LoopDeletionPass())
LOOP_PASS("simplify-cfg", LoopSimplifyCFGPass())
LOOP_PASS("indvars", IndVarSimplifyPass())
LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs()))
diff --git a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
index daf0eb9dc2c..19b2f89555c 100644
--- a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
+++ b/llvm/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 @@ using namespace llvm;
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<BasicBlock *> &exitingBlocks,
- SmallVectorImpl<BasicBlock *> &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<BasicBlock *> &exitingBlocks,
- SmallVectorImpl<BasicBlock *> &exitBlocks,
- bool &Changed, BasicBlock *Preheader) {
+bool LoopDeletionPass::isLoopDead(Loop *L, ScalarEvolution &SE,
+ SmallVectorImpl<BasicBlock *> &exitingBlocks,
+ SmallVectorImpl<BasicBlock *> &exitBlocks,
+ bool &Changed, BasicBlock *Preheader) {
BasicBlock *exitBlock = exitBlocks[0];
// Make sure that all PHI entries coming from the loop are loop invariant.
@@ -124,17 +91,14 @@ bool LoopDeletion::isLoopDead(Loop *L, ScalarEvolution &SE,
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<DominatorTreeWrapperPass>().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
@@ -152,10 +116,10 @@ bool LoopDeletion::runOnLoop(Loop *L, LPPassManager &) {
if (L->begin() != L->end())
return false;
- SmallVector<BasicBlock*, 4> exitingBlocks;
+ SmallVector<BasicBlock *, 4> exitingBlocks;
L->getExitingBlocks(exitingBlocks);
- SmallVector<BasicBlock*, 4> exitBlocks;
+ SmallVector<BasicBlock *, 4> exitBlocks;
L->getUniqueExitBlocks(exitBlocks);
// We require that the loop only have a single exit block. Otherwise, we'd
@@ -165,8 +129,6 @@ bool LoopDeletion::runOnLoop(Loop *L, LPPassManager &) {
if (exitBlocks.size() != 1)
return false;
- ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-
// Finally, we have to check that the loop really is dead.
bool Changed = false;
if (!isLoopDead(L, SE, exitingBlocks, exitBlocks, Changed, preheader))
@@ -238,8 +200,8 @@ bool LoopDeletion::runOnLoop(Loop *L, LPPassManager &) {
// Finally, the blocks from loopinfo. This has to happen late because
// otherwise our loop iterators won't work.
- LoopInfo &loopInfo = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
- SmallPtrSet<BasicBlock*, 8> blocks;
+
+ SmallPtrSet<BasicBlock *, 8> blocks;
blocks.insert(L->block_begin(), L->block_end());
for (BasicBlock *BB : blocks)
loopInfo.removeBlock(BB);
@@ -252,3 +214,56 @@ bool LoopDeletion::runOnLoop(Loop *L, LPPassManager &) {
return Changed;
}
+
+PreservedAnalyses LoopDeletionPass::run(Loop &L, AnalysisManager<Loop> &AM) {
+ auto &FAM = AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
+ Function *F = L.getHeader()->getParent();
+
+ auto &DT = *FAM.getCachedResult<DominatorTreeAnalysis>(*F);
+ auto &SE = *FAM.getCachedResult<ScalarEvolutionAnalysis>(*F);
+ auto &LI = *FAM.getCachedResult<LoopAnalysis>(*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<DominatorTreeWrapperPass>().getDomTree();
+ ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+ LoopInfo &loopInfo = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+
+ LoopDeletionPass Impl;
+ return Impl.runImpl(L, DT, SE, loopInfo);
+}
diff --git a/llvm/lib/Transforms/Scalar/Scalar.cpp b/llvm/lib/Transforms/Scalar/Scalar.cpp
index 13610fa55e4..f1a6524138c 100644
--- a/llvm/lib/Transforms/Scalar/Scalar.cpp
+++ b/llvm/lib/Transforms/Scalar/Scalar.cpp
@@ -50,7 +50,7 @@ void llvm::initializeScalarOpts(PassRegistry &Registry) {
initializeJumpThreadingPass(Registry);
initializeLegacyLICMPassPass(Registry);
initializeLoopDataPrefetchPass(Registry);
- initializeLoopDeletionPass(Registry);
+ initializeLoopDeletionLegacyPassPass(Registry);
initializeLoopAccessLegacyAnalysisPass(Registry);
initializeLoopInstSimplifyPass(Registry);
initializeLoopInterchangePass(Registry);
diff --git a/llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll b/llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll
index 87f8f461050..d7d6badb165 100644
--- a/llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll
+++ b/llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll
@@ -1,4 +1,5 @@
; RUN: opt < %s -loop-deletion -S | FileCheck %s
+; RUN: opt < %s -passes='require<scalar-evolution>,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
OpenPOWER on IntegriCloud