Index: llvm/trunk/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/trunk/include/llvm/Analysis/ScalarEvolution.h +++ llvm/trunk/include/llvm/Analysis/ScalarEvolution.h @@ -782,6 +782,13 @@ /// backedge-taken count. bool hasLoopInvariantBackedgeTakenCount(const Loop *L); + // This method should be called by the client when it made any change that + // would invalidate SCEV's answers, and the client wants to remove all loop + // information held internally by ScalarEvolution. This is intended to be used + // when the alternative to forget a loop is too expensive (i.e. large loop + // bodies). + void forgetAllLoops(); + /// This method should be called by the client when it has changed a loop in /// a way that may effect ScalarEvolution's ability to compute a trip count, /// or if the loop is deleted. This call is potentially expensive for large Index: llvm/trunk/include/llvm/Transforms/IPO/PassManagerBuilder.h =================================================================== --- llvm/trunk/include/llvm/Transforms/IPO/PassManagerBuilder.h +++ llvm/trunk/include/llvm/Transforms/IPO/PassManagerBuilder.h @@ -148,6 +148,7 @@ bool RerollLoops; bool NewGVN; bool DisableGVNLoadPRE; + bool ForgetAllSCEVInLoopUnroll; bool VerifyInput; bool VerifyOutput; bool MergeFunctions; Index: llvm/trunk/include/llvm/Transforms/Scalar.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Scalar.h +++ llvm/trunk/include/llvm/Transforms/Scalar.h @@ -183,11 +183,13 @@ // LoopUnroll - This pass is a simple loop unrolling pass. // Pass *createLoopUnrollPass(int OptLevel = 2, bool OnlyWhenForced = false, - int Threshold = -1, int Count = -1, - int AllowPartial = -1, int Runtime = -1, - int UpperBound = -1, int AllowPeeling = -1); + bool ForgetAllSCEV = false, int Threshold = -1, + int Count = -1, int AllowPartial = -1, + int Runtime = -1, int UpperBound = -1, + int AllowPeeling = -1); // Create an unrolling pass for full unrolling that uses exact trip count only. -Pass *createSimpleLoopUnrollPass(int OptLevel = 2, bool OnlyWhenForced = false); +Pass *createSimpleLoopUnrollPass(int OptLevel = 2, bool OnlyWhenForced = false, + bool ForgetAllSCEV = false); //===----------------------------------------------------------------------===// // Index: llvm/trunk/include/llvm/Transforms/Utils/UnrollLoop.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/UnrollLoop.h +++ llvm/trunk/include/llvm/Transforms/Utils/UnrollLoop.h @@ -67,17 +67,17 @@ 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 = nullptr); + bool ForgetAllSCEV, LoopInfo *LI, + ScalarEvolution *SE, DominatorTree *DT, + AssumptionCache *AC, OptimizationRemarkEmitter *ORE, + bool PreserveLCSSA, Loop **RemainderLoop = nullptr); bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, - LoopInfo *LI, ScalarEvolution *SE, - DominatorTree *DT, AssumptionCache *AC, - bool PreserveLCSSA, + bool ForgetAllSCEV, LoopInfo *LI, + ScalarEvolution *SE, DominatorTree *DT, + AssumptionCache *AC, bool PreserveLCSSA, Loop **ResultLoop = nullptr); void computePeelCount(Loop *L, unsigned LoopSize, Index: llvm/trunk/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/trunk/lib/Analysis/ScalarEvolution.cpp +++ llvm/trunk/lib/Analysis/ScalarEvolution.cpp @@ -6789,6 +6789,28 @@ return BackedgeTakenCounts.find(L)->second = std::move(Result); } +void ScalarEvolution::forgetAllLoops() { + // This method is intended to forget all info about loops. It should + // invalidate caches as if the following happened: + // - The trip counts of all loops have changed arbitrarily + // - Every llvm::Value has been updated in place to produce a different + // result. + BackedgeTakenCounts.clear(); + PredicatedBackedgeTakenCounts.clear(); + LoopPropertiesCache.clear(); + ConstantEvolutionLoopExitValue.clear(); + ValueExprMap.clear(); + ValuesAtScopes.clear(); + LoopDispositions.clear(); + BlockDispositions.clear(); + UnsignedRanges.clear(); + SignedRanges.clear(); + ExprValueMap.clear(); + HasRecMap.clear(); + MinTrailingZerosCache.clear(); + PredicatedSCEVRewrites.clear(); +} + void ScalarEvolution::forgetLoop(const Loop *L) { // Drop any stored trip count value. auto RemoveLoopFromBackedgeMap = Index: llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp +++ llvm/trunk/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 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()); Index: llvm/trunk/lib/Transforms/Scalar/LoopUnrollPass.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ llvm/trunk/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 ProvidedCount, + bool OnlyWhenForced, bool ForgetAllSCEV, Optional ProvidedCount, Optional ProvidedThreshold, Optional ProvidedAllowPartial, Optional ProvidedRuntime, Optional ProvidedUpperBound, Optional 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 ProvidedCount; Optional ProvidedThreshold; Optional ProvidedAllowPartial; @@ -1139,15 +1144,16 @@ Optional ProvidedAllowPeeling; LoopUnroll(int OptLevel = 2, bool OnlyWhenForced = false, - Optional Threshold = None, + bool ForgetAllSCEV = false, Optional Threshold = None, Optional Count = None, Optional AllowPartial = None, Optional Runtime = None, Optional UpperBound = None, Optional 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(Threshold), Count == -1 ? None : Optional(Count), AllowPartial == -1 ? None : Optional(AllowPartial), @@ -1218,8 +1224,10 @@ AllowPeeling == -1 ? None : Optional(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; Index: llvm/trunk/lib/Transforms/Utils/LoopUnroll.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LoopUnroll.cpp +++ llvm/trunk/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); Index: llvm/trunk/lib/Transforms/Utils/LoopUnrollAndJam.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LoopUnrollAndJam.cpp +++ llvm/trunk/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; Index: llvm/trunk/lib/Transforms/Utils/LoopUnrollRuntime.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LoopUnrollRuntime.cpp +++ llvm/trunk/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) Index: llvm/trunk/unittests/Transforms/Utils/UnrollLoopTest.cpp =================================================================== --- llvm/trunk/unittests/Transforms/Utils/UnrollLoopTest.cpp +++ llvm/trunk/unittests/Transforms/Utils/UnrollLoopTest.cpp @@ -70,6 +70,7 @@ bool PreserveLCSSA = L->isRecursivelyLCSSAForm(DT,LI); - bool ret = UnrollRuntimeLoopRemainder(L, 4, true, false, false, &LI, &SE, &DT, &AC, PreserveLCSSA); + bool ret = UnrollRuntimeLoopRemainder(L, 4, true, false, false, false, &LI, + &SE, &DT, &AC, PreserveLCSSA); EXPECT_FALSE(ret); }