[New PM][IRCE] port of Inductive Range Check Elimination pass to the new pass manager
There are two nontrivial details here:
* Loop structure update interface is quite different with new pass manager,
so the code to add new loops was factored out
* BranchProbabilityInfo is not a loop analysis, so it can not be just getResult'ed from
within the loop pass. It cant even be queried through getCachedResult as LoopCanonicalization
sequence (e.g. LoopSimplify) might invalidate BPI results.
Complete solution for BPI will likely take some time to discuss and figure out,
so for now this was partially solved by making BPI optional in IRCE
(skipping a couple of profitability checks if it is absent).
Most of the IRCE tests got their corresponding new-pass-manager variant enabled.
Only two of them depend on BPI, both marked with TODO, to be turned on when BPI
starts being available for loop passes.
Reviewers: chandlerc, mkazantsev, sanjoy, asbirlea
Reviewed By: mkazantsev
Differential Revision: https://reviews.llvm.org/D43795
llvm-svn: 327619
diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
index 0288954..dc085d5 100644
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/lib/Passes/PassBuilder.cpp
@@ -103,6 +103,7 @@
#include "llvm/Transforms/Scalar/GuardWidening.h"
#include "llvm/Transforms/Scalar/IVUsersPrinter.h"
#include "llvm/Transforms/Scalar/IndVarSimplify.h"
+#include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
#include "llvm/Transforms/Scalar/JumpThreading.h"
#include "llvm/Transforms/Scalar/LICM.h"
#include "llvm/Transforms/Scalar/LoopAccessAnalysisPrinter.h"
diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def
index 916b1d5..3d916c6 100644
--- a/llvm/lib/Passes/PassRegistry.def
+++ b/llvm/lib/Passes/PassRegistry.def
@@ -237,6 +237,7 @@
LOOP_PASS("simplify-cfg", LoopSimplifyCFGPass())
LOOP_PASS("strength-reduce", LoopStrengthReducePass())
LOOP_PASS("indvars", IndVarSimplifyPass())
+LOOP_PASS("irce", IRCEPass())
LOOP_PASS("unroll-full", LoopFullUnrollPass())
LOOP_PASS("unswitch", SimpleLoopUnswitchPass())
LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs()))
diff --git a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
index 8653bed..9d965d8 100644
--- a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
@@ -43,6 +43,7 @@
//
//===----------------------------------------------------------------------===//
+#include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/None.h"
@@ -52,6 +53,7 @@
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
@@ -235,17 +237,31 @@
/// checks, and hence don't end up in \p Checks.
static void
extractRangeChecksFromBranch(BranchInst *BI, Loop *L, ScalarEvolution &SE,
- BranchProbabilityInfo &BPI,
+ BranchProbabilityInfo *BPI,
SmallVectorImpl<InductiveRangeCheck> &Checks);
};
-class InductiveRangeCheckElimination : public LoopPass {
+class InductiveRangeCheckElimination {
+ ScalarEvolution &SE;
+ BranchProbabilityInfo *BPI;
+ DominatorTree &DT;
+ LoopInfo &LI;
+
+public:
+ InductiveRangeCheckElimination(ScalarEvolution &SE,
+ BranchProbabilityInfo *BPI, DominatorTree &DT,
+ LoopInfo &LI)
+ : SE(SE), BPI(BPI), DT(DT), LI(LI) {}
+
+ bool run(Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop);
+};
+
+class IRCELegacyPass : public LoopPass {
public:
static char ID;
- InductiveRangeCheckElimination() : LoopPass(ID) {
- initializeInductiveRangeCheckEliminationPass(
- *PassRegistry::getPassRegistry());
+ IRCELegacyPass() : LoopPass(ID) {
+ initializeIRCELegacyPassPass(*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
@@ -258,14 +274,14 @@
} // end anonymous namespace
-char InductiveRangeCheckElimination::ID = 0;
+char IRCELegacyPass::ID = 0;
-INITIALIZE_PASS_BEGIN(InductiveRangeCheckElimination, "irce",
+INITIALIZE_PASS_BEGIN(IRCELegacyPass, "irce",
"Inductive range check elimination", false, false)
INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopPass)
-INITIALIZE_PASS_END(InductiveRangeCheckElimination, "irce",
- "Inductive range check elimination", false, false)
+INITIALIZE_PASS_END(IRCELegacyPass, "irce", "Inductive range check elimination",
+ false, false)
StringRef InductiveRangeCheck::rangeCheckKindToStr(
InductiveRangeCheck::RangeCheckKind RCK) {
@@ -417,15 +433,15 @@
}
void InductiveRangeCheck::extractRangeChecksFromBranch(
- BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo &BPI,
+ BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
SmallVectorImpl<InductiveRangeCheck> &Checks) {
if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
return;
BranchProbability LikelyTaken(15, 16);
- if (!SkipProfitabilityChecks &&
- BPI.getEdgeProbability(BI->getParent(), (unsigned)0) < LikelyTaken)
+ if (!SkipProfitabilityChecks && BPI &&
+ BPI->getEdgeProbability(BI->getParent(), (unsigned)0) < LikelyTaken)
return;
SmallPtrSet<Value *, 8> Visited;
@@ -516,9 +532,8 @@
}
static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
- BranchProbabilityInfo &BPI,
- Loop &,
- const char *&);
+ BranchProbabilityInfo *BPI,
+ Loop &, const char *&);
};
/// This class is used to constrain loops to run within a given iteration space.
@@ -585,7 +600,7 @@
// Create the appropriate loop structure needed to describe a cloned copy of
// `Original`. The clone is described by `VM`.
Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
- ValueToValueMapTy &VM);
+ ValueToValueMapTy &VM, bool IsSubloop);
// Rewrite the iteration space of the loop denoted by (LS, Preheader). The
// iteration space of the rewritten loop ends at ExitLoopAt. The start of the
@@ -637,8 +652,8 @@
LLVMContext &Ctx;
ScalarEvolution &SE;
DominatorTree &DT;
- LPPassManager &LPM;
LoopInfo &LI;
+ function_ref<void(Loop *, bool)> LPMAddNewLoop;
// Information about the original loop we started out with.
Loop &OriginalLoop;
@@ -658,12 +673,13 @@
LoopStructure MainLoopStructure;
public:
- LoopConstrainer(Loop &L, LoopInfo &LI, LPPassManager &LPM,
+ LoopConstrainer(Loop &L, LoopInfo &LI,
+ function_ref<void(Loop *, bool)> LPMAddNewLoop,
const LoopStructure &LS, ScalarEvolution &SE,
DominatorTree &DT, InductiveRangeCheck::Range R)
: F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
- SE(SE), DT(DT), LPM(LPM), LI(LI), OriginalLoop(L), Range(R),
- MainLoopStructure(LS) {}
+ SE(SE), DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L),
+ Range(R), MainLoopStructure(LS) {}
// Entry point for the algorithm. Returns true on success.
bool run();
@@ -726,8 +742,8 @@
Optional<LoopStructure>
LoopStructure::parseLoopStructure(ScalarEvolution &SE,
- BranchProbabilityInfo &BPI,
- Loop &L, const char *&FailureReason) {
+ BranchProbabilityInfo *BPI, Loop &L,
+ const char *&FailureReason) {
if (!L.isLoopSimplifyForm()) {
FailureReason = "loop not in LoopSimplify form";
return None;
@@ -762,7 +778,8 @@
unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
BranchProbability ExitProbability =
- BPI.getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx);
+ BPI ? BPI->getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx)
+ : BranchProbability::getZero();
if (!SkipProfitabilityChecks &&
ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
@@ -1396,13 +1413,14 @@
}
Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
- ValueToValueMapTy &VM) {
+ ValueToValueMapTy &VM,
+ bool IsSubloop) {
Loop &New = *LI.AllocateLoop();
if (Parent)
Parent->addChildLoop(&New);
else
LI.addTopLevelLoop(&New);
- LPM.addLoop(New);
+ LPMAddNewLoop(&New, IsSubloop);
// Add all of the blocks in Original to the new loop.
for (auto *BB : Original->blocks())
@@ -1411,7 +1429,7 @@
// Add all of the subloops to the new loop.
for (Loop *SubLoop : *Original)
- createClonedLoopStructure(SubLoop, &New, VM);
+ createClonedLoopStructure(SubLoop, &New, VM, /* IsSubloop */ true);
return &New;
}
@@ -1561,13 +1579,15 @@
// LI when LoopSimplifyForm is generated.
Loop *PreL = nullptr, *PostL = nullptr;
if (!PreLoop.Blocks.empty()) {
- PreL = createClonedLoopStructure(
- &OriginalLoop, OriginalLoop.getParentLoop(), PreLoop.Map);
+ PreL = createClonedLoopStructure(&OriginalLoop,
+ OriginalLoop.getParentLoop(), PreLoop.Map,
+ /* IsSubLoop */ false);
}
if (!PostLoop.Blocks.empty()) {
- PostL = createClonedLoopStructure(
- &OriginalLoop, OriginalLoop.getParentLoop(), PostLoop.Map);
+ PostL =
+ createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),
+ PostLoop.Map, /* IsSubLoop */ false);
}
// This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
@@ -1738,12 +1758,45 @@
return Ret;
}
-bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
+PreservedAnalyses IRCEPass::run(Loop &L, LoopAnalysisManager &AM,
+ LoopStandardAnalysisResults &AR,
+ LPMUpdater &U) {
+ Function *F = L.getHeader()->getParent();
+ const auto &FAM =
+ AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
+ auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
+ InductiveRangeCheckElimination IRCE(AR.SE, BPI, AR.DT, AR.LI);
+ auto LPMAddNewLoop = [&U](Loop *NL, bool IsSubloop) {
+ if (!IsSubloop)
+ U.addSiblingLoops(NL);
+ };
+ bool Changed = IRCE.run(&L, LPMAddNewLoop);
+ if (!Changed)
+ return PreservedAnalyses::all();
+
+ return getLoopPassPreservedAnalyses();
+}
+
+bool IRCELegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
if (skipLoop(L))
return false;
+ ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+ BranchProbabilityInfo &BPI =
+ getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
+ auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+ auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+ InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI);
+ auto LPMAddNewLoop = [&LPM](Loop *NL, bool /* IsSubLoop */) {
+ LPM.addLoop(*NL);
+ };
+ return IRCE.run(L, LPMAddNewLoop);
+}
+
+bool InductiveRangeCheckElimination::run(
+ Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) {
if (L->getBlocks().size() >= LoopSizeCutoff) {
- DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
+ DEBUG(dbgs() << "irce: giving up constraining loop, too large\n");
return false;
}
@@ -1755,9 +1808,6 @@
LLVMContext &Context = Preheader->getContext();
SmallVector<InductiveRangeCheck, 16> RangeChecks;
- ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
- BranchProbabilityInfo &BPI =
- getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
for (auto BBI : L->getBlocks())
if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
@@ -1823,9 +1873,8 @@
if (!SafeIterRange.hasValue())
return false;
- auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
- LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), LPM,
- LS, SE, DT, SafeIterRange.getValue());
+ LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,
+ SafeIterRange.getValue());
bool Changed = LC.run();
if (Changed) {
@@ -1855,5 +1904,5 @@
}
Pass *llvm::createInductiveRangeCheckEliminationPass() {
- return new InductiveRangeCheckElimination;
+ return new IRCELegacyPass();
}
diff --git a/llvm/lib/Transforms/Scalar/Scalar.cpp b/llvm/lib/Transforms/Scalar/Scalar.cpp
index 0798952..f5b11d5 100644
--- a/llvm/lib/Transforms/Scalar/Scalar.cpp
+++ b/llvm/lib/Transforms/Scalar/Scalar.cpp
@@ -52,7 +52,7 @@
initializeGVNHoistLegacyPassPass(Registry);
initializeGVNSinkLegacyPassPass(Registry);
initializeFlattenCFGPassPass(Registry);
- initializeInductiveRangeCheckEliminationPass(Registry);
+ initializeIRCELegacyPassPass(Registry);
initializeIndVarSimplifyLegacyPassPass(Registry);
initializeInferAddressSpacesPass(Registry);
initializeJumpThreadingPass(Registry);