[SCEV] Add option to forget everything in SCEV.
Summary:
Create a method to forget everything in SCEV.
Add a cl::opt and PassManagerBuilder option to use this in LoopUnroll.
Motivation: Certain Halide applications spend a very long time compiling in forgetLoop, and prefer to forget everything and rebuild SCEV from scratch.
Sample difference in compile time reduction: 21.04 to 14.78 using current ToT release build.
Testcase showcasing this cannot be opensourced and is fairly large.
The option disabled by default, but it may be desirable to enable by
default. Evidence in favor (two difference runs on different days/ToT state):
File Before (s) After (s)
clang-9.bc 7267.91 6639.14
llvm-as.bc 194.12 194.12
llvm-dis.bc 62.50 62.50
opt.bc 1855.85 1857.53
File Before (s) After (s)
clang-9.bc 8588.70 7812.83
llvm-as.bc 196.20 194.78
llvm-dis.bc 61.55 61.97
opt.bc 1739.78 1886.26
Reviewers: sanjoy
Subscribers: mehdi_amini, jlebar, zzheng, javed.absar, dmgreen, jdoerfert, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D60144
llvm-svn: 358304
diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp
index 9e241aa..7491fe0 100644
--- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp
+++ b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp
@@ -158,6 +158,12 @@
"enable-order-file-instrumentation", cl::init(false), cl::Hidden,
cl::desc("Enable order file instrumentation (default = off)"));
+cl::opt<bool> ForgetSCEVInLoopUnroll(
+ "forget-scev-loop-unroll", cl::init(false), cl::Hidden,
+ cl::desc("Forget everything in SCEV when doing LoopUnroll, instead of just"
+ " the current top-most loop. This is somtimes preferred to reduce"
+ " compile time."));
+
PassManagerBuilder::PassManagerBuilder() {
OptLevel = 2;
SizeLevel = 0;
@@ -169,6 +175,7 @@
RerollLoops = RunLoopRerolling;
NewGVN = RunNewGVN;
DisableGVNLoadPRE = false;
+ ForgetAllSCEVInLoopUnroll = ForgetSCEVInLoopUnroll;
VerifyInput = false;
VerifyOutput = false;
MergeFunctions = false;
@@ -386,8 +393,9 @@
if (EnableLoopInterchange)
MPM.add(createLoopInterchangePass()); // Interchange loops
- MPM.add(createSimpleLoopUnrollPass(OptLevel,
- DisableUnrollLoops)); // Unroll small loops
+ // Unroll small loops
+ MPM.add(createSimpleLoopUnrollPass(OptLevel, DisableUnrollLoops,
+ ForgetAllSCEVInLoopUnroll));
addExtensionsToPM(EP_LoopOptimizerEnd, MPM);
// This ends the loop pass pipelines.
@@ -724,8 +732,9 @@
MPM.add(createLoopUnrollAndJamPass(OptLevel));
}
- MPM.add(createLoopUnrollPass(OptLevel,
- DisableUnrollLoops)); // Unroll small loops
+ // Unroll small loops
+ MPM.add(createLoopUnrollPass(OptLevel, DisableUnrollLoops,
+ ForgetAllSCEVInLoopUnroll));
if (!DisableUnrollLoops) {
// LoopUnroll may generate some redundency to cleanup.
@@ -919,11 +928,13 @@
if (EnableLoopInterchange)
PM.add(createLoopInterchangePass());
- PM.add(createSimpleLoopUnrollPass(OptLevel,
- DisableUnrollLoops)); // Unroll small loops
+ // Unroll small loops
+ PM.add(createSimpleLoopUnrollPass(OptLevel, DisableUnrollLoops,
+ ForgetAllSCEVInLoopUnroll));
PM.add(createLoopVectorizePass(true, !LoopVectorize));
// The vectorizer may have significantly shortened a loop body; unroll again.
- PM.add(createLoopUnrollPass(OptLevel, DisableUnrollLoops));
+ PM.add(createLoopUnrollPass(OptLevel, DisableUnrollLoops,
+ ForgetAllSCEVInLoopUnroll));
PM.add(createWarnMissedTransformationsPass());
diff --git a/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp b/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp
index ef2831d..53d4ae8 100644
--- a/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp
@@ -964,7 +964,7 @@
Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
const TargetTransformInfo &TTI, AssumptionCache &AC,
OptimizationRemarkEmitter &ORE, bool PreserveLCSSA, int OptLevel,
- bool OnlyWhenForced, Optional<unsigned> ProvidedCount,
+ bool OnlyWhenForced, bool ForgetAllSCEV, Optional<unsigned> ProvidedCount,
Optional<unsigned> ProvidedThreshold, Optional<bool> ProvidedAllowPartial,
Optional<bool> ProvidedRuntime, Optional<bool> ProvidedUpperBound,
Optional<bool> ProvidedAllowPeeling) {
@@ -1082,7 +1082,7 @@
LoopUnrollResult UnrollResult = UnrollLoop(
L, UP.Count, TripCount, UP.Force, UP.Runtime, UP.AllowExpensiveTripCount,
UseUpperBound, MaxOrZero, TripMultiple, UP.PeelCount, UP.UnrollRemainder,
- LI, &SE, &DT, &AC, &ORE, PreserveLCSSA, &RemainderLoop);
+ ForgetAllSCEV, LI, &SE, &DT, &AC, &ORE, PreserveLCSSA, &RemainderLoop);
if (UnrollResult == LoopUnrollResult::Unmodified)
return LoopUnrollResult::Unmodified;
@@ -1131,6 +1131,11 @@
/// metadata are considered. All other loops are skipped.
bool OnlyWhenForced;
+ /// If false, when SCEV is invalidated, only forget everything in the
+ /// top-most loop (call forgetTopMostLoop), of the loop being processed.
+ /// Otherwise, forgetAllLoops and rebuild when needed next.
+ bool ForgetAllSCEV;
+
Optional<unsigned> ProvidedCount;
Optional<unsigned> ProvidedThreshold;
Optional<bool> ProvidedAllowPartial;
@@ -1139,15 +1144,16 @@
Optional<bool> ProvidedAllowPeeling;
LoopUnroll(int OptLevel = 2, bool OnlyWhenForced = false,
- Optional<unsigned> Threshold = None,
+ bool ForgetAllSCEV = false, Optional<unsigned> Threshold = None,
Optional<unsigned> Count = None,
Optional<bool> AllowPartial = None, Optional<bool> Runtime = None,
Optional<bool> UpperBound = None,
Optional<bool> AllowPeeling = None)
: LoopPass(ID), OptLevel(OptLevel), OnlyWhenForced(OnlyWhenForced),
- ProvidedCount(std::move(Count)), ProvidedThreshold(Threshold),
- ProvidedAllowPartial(AllowPartial), ProvidedRuntime(Runtime),
- ProvidedUpperBound(UpperBound), ProvidedAllowPeeling(AllowPeeling) {
+ ForgetAllSCEV(ForgetAllSCEV), ProvidedCount(std::move(Count)),
+ ProvidedThreshold(Threshold), ProvidedAllowPartial(AllowPartial),
+ ProvidedRuntime(Runtime), ProvidedUpperBound(UpperBound),
+ ProvidedAllowPeeling(AllowPeeling) {
initializeLoopUnrollPass(*PassRegistry::getPassRegistry());
}
@@ -1171,8 +1177,8 @@
LoopUnrollResult Result = tryToUnrollLoop(
L, DT, LI, SE, TTI, AC, ORE, PreserveLCSSA, OptLevel, OnlyWhenForced,
- ProvidedCount, ProvidedThreshold, ProvidedAllowPartial, ProvidedRuntime,
- ProvidedUpperBound, ProvidedAllowPeeling);
+ ForgetAllSCEV, ProvidedCount, ProvidedThreshold, ProvidedAllowPartial,
+ ProvidedRuntime, ProvidedUpperBound, ProvidedAllowPeeling);
if (Result == LoopUnrollResult::FullyUnrolled)
LPM.markLoopAsDeleted(*L);
@@ -1202,14 +1208,14 @@
INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
Pass *llvm::createLoopUnrollPass(int OptLevel, bool OnlyWhenForced,
- int Threshold, int Count, int AllowPartial,
- int Runtime, int UpperBound,
+ bool ForgetAllSCEV, int Threshold, int Count,
+ int AllowPartial, int Runtime, int UpperBound,
int AllowPeeling) {
// TODO: It would make more sense for this function to take the optionals
// directly, but that's dangerous since it would silently break out of tree
// callers.
return new LoopUnroll(
- OptLevel, OnlyWhenForced,
+ OptLevel, OnlyWhenForced, ForgetAllSCEV,
Threshold == -1 ? None : Optional<unsigned>(Threshold),
Count == -1 ? None : Optional<unsigned>(Count),
AllowPartial == -1 ? None : Optional<bool>(AllowPartial),
@@ -1218,8 +1224,10 @@
AllowPeeling == -1 ? None : Optional<bool>(AllowPeeling));
}
-Pass *llvm::createSimpleLoopUnrollPass(int OptLevel, bool OnlyWhenForced) {
- return createLoopUnrollPass(OptLevel, OnlyWhenForced, -1, -1, 0, 0, 0, 0);
+Pass *llvm::createSimpleLoopUnrollPass(int OptLevel, bool OnlyWhenForced,
+ bool ForgetAllSCEV) {
+ return createLoopUnrollPass(OptLevel, OnlyWhenForced, ForgetAllSCEV, -1, -1,
+ 0, 0, 0, 0);
}
PreservedAnalyses LoopFullUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
@@ -1250,7 +1258,7 @@
bool Changed =
tryToUnrollLoop(&L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, *ORE,
/*PreserveLCSSA*/ true, OptLevel, OnlyWhenForced,
- /*Count*/ None,
+ /*ForgetAllSCEV*/ false, /*Count*/ None,
/*Threshold*/ None, /*AllowPartial*/ false,
/*Runtime*/ false, /*UpperBound*/ false,
/*AllowPeeling*/ false) != LoopUnrollResult::Unmodified;
@@ -1388,7 +1396,7 @@
LoopUnrollResult Result = tryToUnrollLoop(
&L, DT, &LI, SE, TTI, AC, ORE,
/*PreserveLCSSA*/ true, UnrollOpts.OptLevel, UnrollOpts.OnlyWhenForced,
- /*Count*/ None,
+ /*ForgetAllSCEV*/ false, /*Count*/ None,
/*Threshold*/ None, UnrollOpts.AllowPartial, UnrollOpts.AllowRuntime,
UnrollOpts.AllowUpperBound, LocalAllowPeeling);
Changed |= Result != LoopUnrollResult::Unmodified;
diff --git a/llvm/lib/Transforms/Utils/LoopUnroll.cpp b/llvm/lib/Transforms/Utils/LoopUnroll.cpp
index 0d62a81..fa8a0ab 100644
--- a/llvm/lib/Transforms/Utils/LoopUnroll.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUnroll.cpp
@@ -335,8 +335,9 @@
Loop *L, unsigned Count, unsigned TripCount, bool Force, bool AllowRuntime,
bool AllowExpensiveTripCount, bool PreserveCondBr, bool PreserveOnlyFirst,
unsigned TripMultiple, unsigned PeelCount, bool UnrollRemainder,
- LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
- OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop) {
+ bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
+ AssumptionCache *AC, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
+ Loop **RemainderLoop) {
BasicBlock *Preheader = L->getLoopPreheader();
if (!Preheader) {
@@ -469,8 +470,9 @@
if (RuntimeTripCount && TripMultiple % Count != 0 &&
!UnrollRuntimeLoopRemainder(L, Count, AllowExpensiveTripCount,
- EpilogProfitability, UnrollRemainder, LI, SE,
- DT, AC, PreserveLCSSA, RemainderLoop)) {
+ EpilogProfitability, UnrollRemainder,
+ ForgetAllSCEV, LI, SE, DT, AC, PreserveLCSSA,
+ RemainderLoop)) {
if (Force)
RuntimeTripCount = false;
else {
@@ -554,8 +556,12 @@
// and if something changes inside them then any of outer loops may also
// change. When we forget outermost loop, we also forget all contained loops
// and this is what we need here.
- if (SE)
- SE->forgetTopmostLoop(L);
+ if (SE) {
+ if (ForgetAllSCEV)
+ SE->forgetAllLoops();
+ else
+ SE->forgetTopmostLoop(L);
+ }
bool ContinueOnTrue = L->contains(BI->getSuccessor(0));
BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue);
diff --git a/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp b/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
index d5ccadd..a53ee9d 100644
--- a/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
@@ -197,8 +197,8 @@
if (TripMultiple == 1 || TripMultiple % Count != 0) {
if (!UnrollRuntimeLoopRemainder(L, Count, /*AllowExpensiveTripCount*/ false,
/*UseEpilogRemainder*/ true,
- UnrollRemainder, LI, SE, DT, AC, true,
- EpilogueLoop)) {
+ UnrollRemainder, /*ForgetAllSCEV*/ false,
+ LI, SE, DT, AC, true, EpilogueLoop)) {
LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; remainder loop could not be "
"generated when assuming runtime trip count\n");
return LoopUnrollResult::Unmodified;
diff --git a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp
index 2f1a759..20d687f 100644
--- a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp
@@ -553,10 +553,10 @@
bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
bool AllowExpensiveTripCount,
bool UseEpilogRemainder,
- bool UnrollRemainder, LoopInfo *LI,
- ScalarEvolution *SE, DominatorTree *DT,
- AssumptionCache *AC, bool PreserveLCSSA,
- Loop **ResultLoop) {
+ bool UnrollRemainder, bool ForgetAllSCEV,
+ LoopInfo *LI, ScalarEvolution *SE,
+ DominatorTree *DT, AssumptionCache *AC,
+ bool PreserveLCSSA, Loop **ResultLoop) {
LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
LLVM_DEBUG(L->dump());
LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
@@ -953,8 +953,8 @@
/*Force*/ false, /*AllowRuntime*/ false,
/*AllowExpensiveTripCount*/ false, /*PreserveCondBr*/ true,
/*PreserveOnlyFirst*/ false, /*TripMultiple*/ 1,
- /*PeelCount*/ 0, /*UnrollRemainder*/ false, LI, SE, DT, AC,
- /*ORE*/ nullptr, PreserveLCSSA);
+ /*PeelCount*/ 0, /*UnrollRemainder*/ false, ForgetAllSCEV,
+ LI, SE, DT, AC, /*ORE*/ nullptr, PreserveLCSSA);
}
if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)