[SCEV] Construct SCEV iteratively.

[fhahn]

Summary

This patch updates SCEV construction to work iteratively instead of recursively
in most cases. It resolves stack overflow issues when trying to construct SCEVs
for certain inputs, e.g. PR45201.

The basic approach is to to use a worklist to queue operands of V which
need to be created before V. To do so, the current patch adds a
getOperandsToCreate function which collects the operands SCEV
construction depends on for a given value. This is a slight duplication
with createSCEV.

At the moment, SCEVs for phis are still created recursively.

Fixes #32078, #42594, #44546, #49293, #49599, #55333, #55511

[lebedev.ri]

Thanks for looking into this!
I previously looked into this: https://github.com/LebedevRI/llvm-project/commit/6b006aa21caf018aa0f280828899d510274c8444
... but as it is apparent, never posted the diff. Nonetheless, it may be interesting to look at.

The most interesting question is, do we really want to avoid (indirect self-) recursion (through getSCEV)?
Then the api of ScalarEvolution needs more changes than what the current diff contains,
basically everything that can end up creating new SCEV expressions from IR
needs to be able to return "in-progress, requery me later" status.

[nikic]

To ask the obvious question: Can we get away with simply adding a getSCEV recursion limit instead? Is there reason to believe that a sensible recursion cutoff (similar to the many SCEV already has) would adversely affect analysis quality in practice? I'd rather avoid the additional complexity if we can.

[lebedev.ri]

In D114650#3157253, @nikic wrote:

To ask the obvious question: Can we get away with simply adding a getSCEV recursion limit instead? Is there reason to believe that a sensible recursion cutoff (similar to the many SCEV already has) would adversely affect analysis quality in practice? I'd rather avoid the additional complexity if we can.

Recursion itself is rarely the right solution in the first place, let alone working around it by introducing random cut-offs.

[fhahn]

In D114650#3156273, @lebedev.ri wrote:

Thanks for looking into this!
I previously looked into this: https://github.com/LebedevRI/llvm-project/commit/6b006aa21caf018aa0f280828899d510274c8444
... but as it is apparent, never posted the diff. Nonetheless, it may be interesting to look at.

The most interesting question is, do we really want to avoid (indirect self-) recursion (through getSCEV)?
Then the api of ScalarEvolution needs more changes than what the current diff contains,
basically everything that can end up creating new SCEV expressions from IR
needs to be able to return "in-progress, requery me later" status.

Thanks for sharing the patch. I think the current patch doesn't really need to change any existing interfaces, it just introduces a new expectation: before creating a SCEV for I, SCEVs for all of I's operands must already exist. It's up to the callers of createSCEV (and friends) to ensure that. The only additional complexity is 1) extracting operands for which we need to create SCEVs and 2) processing them in the right order.

At the moment, 1) is a bit unfortunate, because it requires some duplication of createSCEV logic, but overall it's not too bad (if no other interfaces need modifying IMO). I think we may be able to improve/unify the logic there as well, but I think first it would be good to get agreement on whether we want to handle the issue by constructing SCEVs iteratively or not. (Getting this patch to work for all cases, cleaning it up and making sure its as fast as possible will be quite a bit of additional work, which I'd only like to do once we it's clear that this is the overall direction we want to pursue :))

In D114650#3157263, @lebedev.ri wrote:

In D114650#3157253, @nikic wrote:

To ask the obvious question: Can we get away with simply adding a getSCEV recursion limit instead? Is there reason to believe that a sensible recursion cutoff (similar to the many SCEV already has) would adversely affect analysis quality in practice? I'd rather avoid the additional complexity if we can.

Recursion itself is rarely the right solution in the first place, let alone working around it by introducing random cut-offs.

I think one issue with a cut-off for the recursion is that such a cut-off would make SCEV instantiations depend on the instantiation order. I am not sure how much this would be an issue in practice, but among other things it may make verification of SCEV harder (e.g. if we compute SCEVs from scratch to the cached version we would have to make sure to use the same evaluation order as when computing the original SCEV).

[fhahn]

>>>! In D114650#3157263, @lebedev.ri wrote:

In D114650#3157253, @nikic wrote:

To ask the obvious question: Can we get away with simply adding a getSCEV recursion limit instead? Is there reason to believe that a sensible recursion cutoff (similar to the many SCEV already has) would adversely affect analysis quality in practice? I'd rather avoid the additional complexity if we can.

Recursion itself is rarely the right solution in the first place, let alone working around it by introducing random cut-offs.

I think one issue with a cut-off for the recursion is that such a cut-off would make SCEV instantiations depend on the instantiation order. I am not sure how much this would be an issue in practice, but among other things it may make verification of SCEV harder (e.g. if we compute SCEVs from scratch to the cached version we would have to make sure to use the same evaluation order as when computing the original SCEV).

https://bugs.llvm.org/show_bug.cgi?id=32731 has a bit more discussion/context on the potential issues of a cut-off.

[reames]

I want to make sure I understand the problem to be solved. The description and discussion confused me a bit, so I may in fact be wildly off here.

Is the basis issue being solved that calling createSCEV on some IR instruction can require recursing through a very deep chain of instructions which have not yet had SCEVs formed for them? More specifically, is that the *only* deep recursion we're concerned by? The discussion about new invariants for creating a SCEV seemed to indicate it might be much wider, but that discussion didn't parse for me.

If my understanding is correct, then I would have expected this to be effectively a change strictly inside createSCEV. The fact we seem to be changing things much more broadly confuses me. Maybe there's some complexity coming from the phi handling, but if so, maybe a first patch which *only* iteratively constructs arithmetic chains and relies on recursion for the tricky phi parts?

[reames]

Putting this here only because the bug database is still readonly.

Random thought: We're discussing this as a SCEV cornercase, and it's probably worth fixing the case this exposes, but it's also worth noting here that the unroller is producing a horrendously bad form here. It might be worth considering whether the unroller should be applying a peephole as it unrolls to avoid generating this massive and utterly useless IR.

Specifically for this case: if generating an unrolled IV increment with no other uses of the IV, eagerly fold the step increments if constant. That is, instead of producing:

%a = gep i8, i8 %p, i64 1
%b = gep i8, i8 %b, i64 1
%c = gep i8, i8 %c, i64 1
%d = gep i8, i8 %d, i64 1

produce:

%a = gep i8, i8 %p, i64 1
%b = gep i8, i8 %p, i64 2
%c = gep i8, i8 %p, i64 3
%d = gep i8, i8 %p, i64 4
(All of which but the last are dead.)

Doing this might be a worthwhile compile time optimization on it's own.

[fhahn]

In D114650#3159649, @reames wrote:

I want to make sure I understand the problem to be solved. The description and discussion confused me a bit, so I may in fact be wildly off here.

Is the basis issue being solved that calling createSCEV on some IR instruction can require recursing through a very deep chain of instructions which have not yet had SCEVs formed for them? More specifically, is that the *only* deep recursion we're concerned by? The discussion about new invariants for creating a SCEV seemed to indicate it might be much wider, but that discussion didn't parse for me.

Yes, this is the main issue I'd like to address with this change, thanks for summarising this concisely!

If my understanding is correct, then I would have expected this to be effectively a change strictly inside createSCEV. The fact we seem to be changing things much more broadly confuses me. Maybe there's some complexity coming from the phi handling, but if so, maybe a first patch which *only* iteratively constructs arithmetic chains and relies on recursion for the tricky phi parts?

I think most of the 'cluttering' changes are getSCEV -> getExistingSCEV. Those are not strictly necessary and I should be able to strip those from the initial version, same for excluding the phi part.

The getSCEV -> getExistingSCEV changes are related to the invariant mentioned: if we iteratively construct the operands first, then we should be able to rely on the fact that SCEVs for all operands exist when construction a new SCEV, hence using getExistingSCEV instead of getSCEV.

[fhahn]

Just a rebase so this can be applied on top of main.

[martijnotto]

I tried this patch to see if it solves the issue reported in https://github.com/llvm/llvm-project/issues/49293#issuecomment-981040924

It fails with the following error - and a request to submit a bug report:

PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
 #0 0x0000000000801b33 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/usr/lib/llvm-14/bin/ld.lld+0x801b33)
 #1 0x00000000007ffb0e llvm::sys::RunSignalHandlers() (/usr/lib/llvm-14/bin/ld.lld+0x7ffb0e)
 #2 0x000000000080212f SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f3012f663c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x153c0)
 #4 0x0000000002d3cd12 CompareSCEVComplexity(llvm::EquivalenceClasses<llvm::SCEV const*, std::less<llvm::SCEV const*> >&, llvm::EquivalenceClasses<llvm::Value const*, std::less<llvm::Value const*> >&, llvm::LoopInfo const*, llvm::SCEV const*, llvm::SCEV const*, llvm::DominatorTree&, unsigned int) ScalarEvolution.cpp:0:0
 #5 0x0000000002d0044f GroupByComplexity(llvm::SmallVectorImpl<llvm::SCEV const*>&, llvm::LoopInfo*, llvm::DominatorTree&) ScalarEvolution.cpp:0:0
 #6 0x0000000002cf4608 llvm::ScalarEvolution::getAddExpr(llvm::SmallVectorImpl<llvm::SCEV const*>&, llvm::SCEV::NoWrapFlags, unsigned int) (/usr/lib/llvm-14/bin/ld.lld+0x2cf4608)
 #7 0x0000000002d14f67 llvm::ScalarEvolution::createSCEV(llvm::Value*) (/usr/lib/llvm-14/bin/ld.lld+0x2d14f67)
 #8 0x0000000002d0714f llvm::ScalarEvolution::createSCEVIter(llvm::Value*) (/usr/lib/llvm-14/bin/ld.lld+0x2d0714f)
 #9 0x00000000025c508e llvm::SLPVectorizerPass::vectorizeGEPIndices(llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&) (/usr/lib/llvm-14/bin/ld.lld+0x25c508e)
#10 0x00000000025c280c llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) (/usr/lib/llvm-14/bin/ld.lld+0x25c280c)
#11 0x00000000025c20f1 llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/usr/lib/llvm-14/bin/ld.lld+0x25c20f1)
#12 0x00000000022c7b5d llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/usr/lib/llvm-14/bin/ld.lld+0x22c7b5d)
#13 0x0000000003181b59 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/usr/lib/llvm-14/bin/ld.lld+0x3181b59)
#14 0x0000000000dfe32d llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/usr/lib/llvm-14/bin/ld.lld+0xdfe32d)
#15 0x00000000031853f5 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/usr/lib/llvm-14/bin/ld.lld+0x31853f5)
#16 0x0000000000dfe17d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/usr/lib/llvm-14/bin/ld.lld+0xdfe17d)
#17 0x0000000003180d16 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/usr/lib/llvm-14/bin/ld.lld+0x3180d16)
#18 0x0000000001e7311c llvm::lto::opt(llvm::lto::Config const&, llvm::TargetMachine*, unsigned int, llvm::Module&, bool, llvm::ModuleSummaryIndex*, llvm::ModuleSummaryIndex const*, std::vector<unsigned char, std::allocator<unsigned char> > const&) (/usr/lib/llvm-14/bin/ld.lld+0x1e7311c)
#19 0x0000000001e75a42 llvm::lto::thinBackend(llvm::lto::Config const&, unsigned int, std::function<llvm::Expected<std::unique_ptr<llvm::CachedFileStream, std::default_delete<llvm::CachedFileStream> > > (unsigned int)>, llvm::Module&, llvm::ModuleSummaryIndex const&, llvm::StringMap<std::unordered_set<unsigned long, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<unsigned long> >, llvm::MallocAllocator> const&, llvm::DenseMap<unsigned long, llvm::GlobalValueSummary*, llvm::DenseMapInfo<unsigned long, void>, llvm::detail::DenseMapPair<unsigned long, llvm::GlobalValueSummary*> > const&, llvm::MapVector<llvm::StringRef, llvm::BitcodeModule, llvm::DenseMap<llvm::StringRef, unsigned int, llvm::DenseMapInfo<llvm::StringRef, void>, llvm::detail::DenseMapPair<llvm::StringRef, unsigned int> >, std::vector<std::pair<llvm::StringRef, llvm::BitcodeModule>, std::allocator<std::pair<llvm::StringRef, llvm::BitcodeModule> > > >*, std::vector<unsigned char, std::allocator<unsigned char> > const&)::$_3::operator()(llvm::Module&, llvm::TargetMachine*, std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> >) const LTOBackend.cpp:0:0
#20 0x0000000001e758bf llvm::lto::thinBackend(llvm::lto::Config const&, unsigned int, std::function<llvm::Expected<std::unique_ptr<llvm::CachedFileStream, std::default_delete<llvm::CachedFileStream> > > (unsigned int)>, llvm::Module&, llvm::ModuleSummaryIndex const&, llvm::StringMap<std::unordered_set<unsigned long, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<unsigned long> >, llvm::MallocAllocator> const&, llvm::DenseMap<unsigned long, llvm::GlobalValueSummary*, llvm::DenseMapInfo<unsigned long, void>, llvm::detail::DenseMapPair<unsigned long, llvm::GlobalValueSummary*> > const&, llvm::MapVector<llvm::StringRef, llvm::BitcodeModule, llvm::DenseMap<llvm::StringRef, unsigned int, llvm::DenseMapInfo<llvm::StringRef, void>, llvm::detail::DenseMapPair<llvm::StringRef, unsigned int> >, std::vector<std::pair<llvm::StringRef, llvm::BitcodeModule>, std::allocator<std::pair<llvm::StringRef, llvm::BitcodeModule> > > >*, std::vector<unsigned char, std::allocator<unsigned char> > const&) (/usr/lib/llvm-14/bin/ld.lld+0x1e758bf)
#21 0x0000000001e6ed58 (anonymous namespace)::InProcessThinBackend::runThinLTOBackendThread(std::function<llvm::Expected<std::unique_ptr<llvm::CachedFileStream, std::default_delete<llvm::CachedFileStream> > > (unsigned int)>, std::function<llvm::Expected<std::function<llvm::Expected<std::unique_ptr<llvm::CachedFileStream, std::default_delete<llvm::CachedFileStream> > > (unsigned int)> > (unsigned int, llvm::StringRef)>, unsigned int, llvm::BitcodeModule, llvm::ModuleSummaryIndex&, llvm::StringMap<std::unordered_set<unsigned long, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<unsigned long> >, llvm::MallocAllocator> const&, llvm::DenseSet<llvm::ValueInfo, llvm::DenseMapInfo<llvm::ValueInfo, void> > const&, std::map<unsigned long, llvm::GlobalValue::LinkageTypes, std::less<unsigned long>, std::allocator<std::pair<unsigned long const, llvm::GlobalValue::LinkageTypes> > > const&, llvm::DenseMap<unsigned long, llvm::GlobalValueSummary*, llvm::DenseMapInfo<unsigned long, void>, llvm::detail::DenseMapPair<unsigned long, llvm::GlobalValueSummary*> > const&, llvm::MapVector<llvm::StringRef, llvm::BitcodeModule, llvm::DenseMap<llvm::StringRef, unsigned int, llvm::DenseMapInfo<llvm::StringRef, void>, llvm::detail::DenseMapPair<llvm::StringRef, unsigned int> >, std::vector<std::pair<llvm::StringRef, llvm::BitcodeModule>, std::allocator<std::pair<llvm::StringRef, llvm::BitcodeModule> > > >&)::'lambda'(std::function<llvm::Expected<std::unique_ptr<llvm::CachedFileStream, std::default_delete<llvm::CachedFileStream> > > (unsigned int)>)::operator()(std::function<llvm::Expected<std::unique_ptr<llvm::CachedFileStream, std::default_delete<llvm::CachedFileStream> > > (unsigned int)>) const LTO.cpp:0:0
#22 0x0000000001e6e857 std::_Function_handler<void (), std::_Bind<(anonymous namespace)::InProcessThinBackend::start(unsigned int, llvm::BitcodeModule, llvm::StringMap<std::unordered_set<unsigned long, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<unsigned long> >, llvm::MallocAllocator> const&, llvm::DenseSet<llvm::ValueInfo, llvm::DenseMapInfo<llvm::ValueInfo, void> > const&, std::map<unsigned long, llvm::GlobalValue::LinkageTypes, std::less<unsigned long>, std::allocator<std::pair<unsigned long const, llvm::GlobalValue::LinkageTypes> > > const&, llvm::MapVector<llvm::StringRef, llvm::BitcodeModule, llvm::DenseMap<llvm::StringRef, unsigned int, llvm::DenseMapInfo<llvm::StringRef, void>, llvm::detail::DenseMapPair<llvm::StringRef, unsigned int> >, std::vector<std::pair<llvm::StringRef, llvm::BitcodeModule>, std::allocator<std::pair<llvm::StringRef, llvm::BitcodeModule> > > >&)::'lambda'(llvm::BitcodeModule, llvm::ModuleSummaryIndex&, llvm::StringMap<std::unordered_set<unsigned long, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<unsigned long> >, llvm::MallocAllocator> const&, llvm::DenseSet<llvm::ValueInfo, llvm::DenseMapInfo<llvm::ValueInfo, void> > const&, std::map<unsigned long, llvm::GlobalValue::LinkageTypes, std::less<unsigned long>, std::allocator<std::pair<unsigned long const, llvm::GlobalValue::LinkageTypes> > > const&, llvm::DenseMap<unsigned long, llvm::GlobalValueSummary*, llvm::DenseMapInfo<unsigned long, void>, llvm::detail::DenseMapPair<unsigned long, llvm::GlobalValueSummary*> > const&, llvm::MapVector<llvm::StringRef, llvm::BitcodeModule, llvm::DenseMap<llvm::StringRef, unsigned int, llvm::DenseMapInfo<llvm::StringRef, void>, llvm::detail::DenseMapPair<llvm::StringRef, unsigned int> >, std::vector<std::pair<llvm::StringRef, llvm::BitcodeModule>, std::allocator<std::pair<llvm::StringRef, llvm::BitcodeModule> > > >&) (llvm::BitcodeModule, std::reference_wrapper<llvm::ModuleSummaryIndex>, std::reference_wrapper<llvm::StringMap<std::unordered_set<unsigned long, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<unsigned long> >, llvm::MallocAllocator> const>, std::reference_wrapper<llvm::DenseSet<llvm::ValueInfo, llvm::DenseMapInfo<llvm::ValueInfo, void> > const>, std::reference_wrapper<std::map<unsigned long, llvm::GlobalValue::LinkageTypes, std::less<unsigned long>, std::allocator<std::pair<unsigned long const, llvm::GlobalValue::LinkageTypes> > > const>, std::reference_wrapper<llvm::DenseMap<unsigned long, llvm::GlobalValueSummary*, llvm::DenseMapInfo<unsigned long, void>, llvm::detail::DenseMapPair<unsigned long, llvm::GlobalValueSummary*> > const>, std::reference_wrapper<llvm::MapVector<llvm::StringRef, llvm::BitcodeModule, llvm::DenseMap<llvm::StringRef, unsigned int, llvm::DenseMapInfo<llvm::StringRef, void>, llvm::detail::DenseMapPair<llvm::StringRef, unsigned int> >, std::vector<std::pair<llvm::StringRef, llvm::BitcodeModule>, std::allocator<std::pair<llvm::StringRef, llvm::BitcodeModule> > > > >)> >::_M_invoke(std::_Any_data const&) LTO.cpp:0:0
#23 0x0000000000b35f0c std::_Function_handler<void (), llvm::ThreadPool::createTaskAndFuture(std::function<void ()>)::'lambda'()>::_M_invoke(std::_Any_data const&) (/usr/lib/llvm-14/bin/ld.lld+0xb35f0c)
#24 0x0000000003253d11 void* llvm::thread::ThreadProxy<std::tuple<llvm::ThreadPool::grow(int)::$_0> >(void*) ThreadPool.cpp:0:0
#25 0x00007f3012f5a609 start_thread /build/glibc-eX1tMB/glibc-2.31/nptl/pthread_create.c:478:7
#26 0x00007f301291c293 __clone /build/glibc-eX1tMB/glibc-2.31/misc/../sysdeps/unix/sysv/linux/x86_64/clone.S:97:0
fish: “/usr/lib/llvm-14/bin/ld.lld --h…” terminated by signal SIGSEGV (Address boundary error)

[fhahn]

Another rebase and attempt to reduce the diff by keeping getSCEV instead of getExistingSCEV. I am planning to further strip down the changes related to phi handling and have the initial version only construct SCEVs iteratively for IR without PHIs/cycles.

[fhahn]

Rebased and updated to keep recursive handling of phi nodes for now. I think this is as strippped down as possible for an initial version. Compile-time impact is more managable than for the initial version:

NewPM-O3: +0.11%
NewPM-ReleaseThinLTO: +0.12%
NewPM-ReleaseLTO-g: +0.08%

https://llvm-compile-time-tracker.com/compare.php?from=9d2349c78f93cba78c1f3b770355f2ac0cb98163&to=ff418d805ec44e288f4c8eb3150e1e874b26040c&stat=instructions

The patch can lead to slightly different (mostly better) results, because in some cases we do not run into various existing recursion limits.

I'd be curious to hear what people think about the latest version and the compile-time trade-off. It should fix a set of related crashes, linked to https://github.com/llvm/llvm-project/issues/44546. It fixes all crashes I was able to reproduce from the issue list on my local system.

[nlopes]

llvm/lib/Analysis/ScalarEvolution.cpp

7067

Poison, poison! :)

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

7067

This is unrelated to this patch, I created D128586. I'll update things here once/if D128586 goes in

[fhahn]

Updated to use PoisonValue after e4e22b6d8038.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

7099

Add and mul currently have special code that tries to combine multiple sequential adds/mul into one getAddExpr/getMulExpr call. This is effectively lost here (or maybe worse, we end up doing both -- each add individually here, and then a multiple-add variant in getSCEV).

I think if we're going to change this (which might well make sense), we should probably change that separately, and also in the createSCEV() code as well. I suspect that this might account for both some of the codegen changes and some of the compile-time impact.

7125

https://github.com/llvm/llvm-project/commit/327307d9d4da0045f762f75343fe66b0f10ecc63 ;)

[fhahn]

Replace isSized check with assertion, traverse add/mul chains when collecting operands.

This slightly increases compile-time, and the geoman impact is now

NewPM-O3: +0.08%
NewPM-ReleaseThinLTO: +0.08%
NewPM-ReleaseLTO-g: +0.09%

https://llvm-compile-time-tracker.com/compare.php?from=403466860b628d6ada20a4b85b5b2ecdfe97b389&to=d662c2da9dc338dd260dacab19c3fd3f5b252fc0&stat=instructions

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

7099

Thanks, I updated getOperandsToCreate to also traverse mul/add chains. This indeed removed the IndVarSimplify changes and improved compile-time a bit.

We could go even further and enqueue (Opcode, Operands) tuples to create directly, instead of going through createSCEV, but this would require a way to encode at least negations for the Add case.

7125

Replace with an assert

[fhahn]

adjust comment about traversing add/mul chains in getOperandsToCreate.

[nikic]

LG. Seems to be a recurring problem, and the solution looks sufficiently non-intrusive. I like that there is no requirement to precisely synchronize the logic between createSCEV and createSCEVIter here, which would be a PITA. If we don't queue enough operands, those will just get computed recursively.

llvm/lib/Analysis/ScalarEvolution.cpp

7185

I don't think this is strictly true due to the createNodeForSelectViaUMinSeq() code. And either way, I don't think we need to handle it this precisely here.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

7185

Thanks, I removed the check for Instruction to simplify things here.

[alexfh]

Heads up: this commit seems to cause miscompiles on some of our code. We're still working on an isolated test case.

[alexfh]

In D114650#3627627, @alexfh wrote:

Heads up: this commit seems to cause miscompiles on some of our code. We're still working on an isolated test case.

False alarm. The issue turned out to be caused by a UB in the code.

[fhahn]

In D114650#3630397, @alexfh wrote:

In D114650#3627627, @alexfh wrote:

Heads up: this commit seems to cause miscompiles on some of our code. We're still working on an isolated test case.

False alarm. The issue turned out to be caused by a UB in the code.

Great, thanks for checking!

[foad]

Hi! We are seeing some large compile time increases with this patch. For example on F23720290, the time for opt -passes=loop-unroll goes from about 2s to 14s while producing identical output.

[fhahn]

In D114650#3639074, @foad wrote:

Hi! We are seeing some large compile time increases with this patch. For example on F23720290, the time for opt -passes=loop-unroll goes from about 2s to 14s while producing identical output.

Interesting, I'll take a look

[fhahn]

In D114650#3641601, @fhahn wrote:

In D114650#3639074, @foad wrote:

Hi! We are seeing some large compile time increases with this patch. For example on F23720290, the time for opt -passes=loop-unroll goes from about 2s to 14s while producing identical output.

Interesting, I'll take a look

I put up a fix: D129731

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   /// a constant range which represents the entire recurrence.  Note that
   /// *add* recurrences with loop invariant steps aren't represented by
   /// SCEVUnknowns and thus don't use this mechanism.
   ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U);
 
   /// We know that there is no SCEV for the specified value.  Analyze the
   /// expression.
   const SCEV *createSCEV(Value *V);
+  const SCEV *createSCEVIter(Value *V);
+  void getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
 
   /// Provide the special handling we need to analyze PHI SCEVs.
   const SCEV *createNodeForPHI(PHINode *PN);
 
   /// Helper function called from createNodeForPHI.
   const SCEV *createAddRecFromPHI(PHINode *PN);
 
   /// A helper function for createAddRecFromPHI to handle simple cases.

llvm/lib/Analysis/ScalarEvolution.cpp

#endif
   // Okay, it looks like we really DO need an addrec expr.  Check to see if we
   // already have one, otherwise create a new one.
   return getOrCreateAddRecExpr(Operands, L, Flags);
 }
 
 const SCEV *
 ScalarEvolution::getGEPExpr(GEPOperator *GEP,
                             const SmallVectorImpl<const SCEV *> &IndexExprs) {
-  const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand());
+  const SCEV *BaseExpr = getExistingSCEV(GEP->getPointerOperand());
   // getSCEV(Base)->getType() has the same address space as Base->getType()
   // because SCEV::getType() preserves the address space.
   Type *IntIdxTy = getEffectiveSCEVType(BaseExpr->getType());
   const bool AssumeInBoundsFlags = [&]() {
     if (!GEP->isInBounds())
       return false;
 
     // We'd like to propagate flags from the IR to the corresponding SCEV nodes,
void ScalarEvolution::insertValueToMap(Value *V, const SCEV *S) {
   }
 }
 
 /// Return an existing SCEV if it exists, otherwise analyze the expression and
 /// create a new one.
 const SCEV *ScalarEvolution::getSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
-  const SCEV *S = getExistingSCEV(V);
-  if (S == nullptr) {
-    S = createSCEV(V);
-    // During PHI resolution, it is possible to create two SCEVs for the same
-    // V, so it is needed to double check whether V->S is inserted into
-    // ValueExprMap before insert S->{V, 0} into ExprValueMap.
-    std::pair<ValueExprMapType::iterator, bool> Pair =
-        ValueExprMap.insert({SCEVCallbackVH(V, this), S});
-    if (Pair.second) {
-      ExprValueMap[S].insert({V, nullptr});
-
-      // If S == Stripped + Offset, add Stripped -> {V, Offset} into
-      // ExprValueMap.
-      const SCEV *Stripped = S;
-      ConstantInt *Offset = nullptr;
-      std::tie(Stripped, Offset) = splitAddExpr(S);
-      // If stripped is SCEVUnknown, don't bother to save
-      // Stripped -> {V, offset}. It doesn't simplify and sometimes even
-      // increase the complexity of the expansion code.
-      // If V is GetElementPtrInst, don't save Stripped -> {V, offset}
-      // because it may generate add/sub instead of GEP in SCEV expansion.
-      if (Offset != nullptr && !isa<SCEVUnknown>(Stripped) &&
-          !isa<GetElementPtrInst>(V))
-        ExprValueMap[Stripped].insert({V, Offset});
-    }
-  }
+  if (const SCEV *S = getExistingSCEV(V))
     return S;
+  return createSCEVIter(V);
 }
 
 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   ValueExprMapType::iterator I = ValueExprMap.find_as(V);
   if (I != ValueExprMap.end()) {
     const SCEV *S = I->second;
const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
   auto BO = MatchBinaryOp(BEValueV, DT);
   if (!BO)
     return nullptr;
 
   if (BO->Opcode != Instruction::Add)
     return nullptr;
 
   const SCEV *Accum = nullptr;
-  if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
-    Accum = getSCEV(BO->RHS);
-  else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
-    Accum = getSCEV(BO->LHS);
+  if (BO->LHS == PN && L->isLoopInvariant(BO->RHS)) {
+    Accum = getExistingSCEV(BO->RHS);
+    assert(Accum);
+  } else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS)) {
+    Accum = getExistingSCEV(BO->LHS);
+    assert(Accum);
+  }
 
   if (!Accum)
     return nullptr;
 
   SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
   if (BO->IsNUW)
     Flags = setFlags(Flags, SCEV::FlagNUW);
   if (BO->IsNSW)
     Flags = setFlags(Flags, SCEV::FlagNSW);
 
-  const SCEV *StartVal = getSCEV(StartValueV);
+  const SCEV *StartVal = getExistingSCEV(StartValueV);
   const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
   insertValueToMap(PN, PHISCEV);
 
   // We can add Flags to the post-inc expression only if we
   // know that it is *undefined behavior* for BEValueV to
   // overflow.
   if (auto *BEInst = dyn_cast<Instruction>(BEValueV)) {
     assert(isLoopInvariant(Accum, L) &&
            "Accum is defined outside L, but is not invariant?");
     if (isAddRecNeverPoison(BEInst, L))
       (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
   }
 
   return PHISCEV;
 }
 
-const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
-  const Loop *L = LI.getLoopFor(PN->getParent());
+static std::pair<Value *, Value *> classifyPhiValues(PHINode *PN,
+                                                     const Loop *L) {
   if (!L || L->getHeader() != PN->getParent())
-    return nullptr;
+    return {nullptr, nullptr};
 
   // The loop may have multiple entrances or multiple exits; we can analyze
   // this phi as an addrec if it has a unique entry value and a unique
   // backedge value.
   Value *BEValueV = nullptr, *StartValueV = nullptr;
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     Value *V = PN->getIncomingValue(i);
     if (L->contains(PN->getIncomingBlock(i))) {
       if (!BEValueV) {
         BEValueV = V;
       } else if (BEValueV != V) {
         BEValueV = nullptr;
         break;
       }
     } else if (!StartValueV) {
       StartValueV = V;
     } else if (StartValueV != V) {
       StartValueV = nullptr;
       break;
     }
   }
+  return {StartValueV, BEValueV};
+}
+
+const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
+  const Loop *L = LI.getLoopFor(PN->getParent());
+  Value *BEValueV, *StartValueV;
+  std::tie(StartValueV, BEValueV) = classifyPhiValues(PN, L);
   if (!BEValueV || !StartValueV)
     return nullptr;
 
   assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
          "PHI node already processed?");
 
   // First, try to find AddRec expression without creating a fictituos symbolic
   // value for PN.
if (DT.dominates(LeftEdge, RightUse) && DT.dominates(RightEdge, LeftUse)) {
     LHS = RightUse;
     RHS = LeftUse;
     return true;
   }
 
   return false;
 }
 
-const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
+static BranchInst *getSelectPhiBr(PHINode *PN, const Loop *L, DominatorTree &DT,
+                                  LoopInfo &LI) {
   auto IsReachable =
       [&](BasicBlock *BB) { return DT.isReachableFromEntry(BB); };
+
   if (PN->getNumIncomingValues() == 2 && all_of(PN->blocks(), IsReachable)) {
-    const Loop *L = LI.getLoopFor(PN->getParent());
 
     // We don't want to break LCSSA, even in a SCEV expression tree.
     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
       if (LI.getLoopFor(PN->getIncomingBlock(i)) != L)
         return nullptr;
 
     // Try to match
     //
     //  br %cond, label %left, label %right
     // left:
     //  br label %merge
     // right:
     //  br label %merge
     // merge:
     //  V = phi [ %x, %left ], [ %y, %right ]
     //
     // as "select %cond, %x, %y"
 
     BasicBlock *IDom = DT[PN->getParent()]->getIDom()->getBlock();
     assert(IDom && "At least the entry block should dominate PN");
 
-    auto *BI = dyn_cast<BranchInst>(IDom->getTerminator());
-    Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
+    return dyn_cast<BranchInst>(IDom->getTerminator());
+  }
+  return nullptr;
+}
 
-    if (BI && BI->isConditional() &&
-        BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS) &&
-        IsAvailableOnEntry(L, DT, getSCEV(LHS), PN->getParent()) &&
-        IsAvailableOnEntry(L, DT, getSCEV(RHS), PN->getParent()))
-      return createNodeForSelectOrPHI(PN, Cond, LHS, RHS);
-  }
+const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
+  const Loop *L = LI.getLoopFor(PN->getParent());
+  BranchInst *BI = getSelectPhiBr(PN, L, DT, LI);
+  Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
+  if (BI && BI->isConditional() && BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS) &&
+      IsAvailableOnEntry(L, DT, getExistingSCEV(LHS), PN->getParent()) &&
+      IsAvailableOnEntry(L, DT, getExistingSCEV(RHS), PN->getParent()))
 
   return nullptr;
 }
 
 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
   if (const SCEV *S = createAddRecFromPHI(PN))
     return S;
 

 
 const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Instruction *I,
                                                       Value *Cond,
                                                       Value *TrueVal,
                                                       Value *FalseVal) {
   // Handle "constant" branch or select. This can occur for instance when a
   // loop pass transforms an inner loop and moves on to process the outer loop.
   if (auto *CI = dyn_cast<ConstantInt>(Cond))
-    return getSCEV(CI->isOne() ? TrueVal : FalseVal);
+    return getExistingSCEV(CI->isOne() ? TrueVal : FalseVal);
 
   // Try to match some simple smax or umax patterns.
   auto *ICI = dyn_cast<ICmpInst>(Cond);
   if (!ICI)
     return getUnknown(I);
 
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
 
   switch (ICI->getPredicate()) {
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_SLE:
   case ICmpInst::ICMP_ULT:
   case ICmpInst::ICMP_ULE:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_SGT:
   case ICmpInst::ICMP_SGE:
   case ICmpInst::ICMP_UGT:
   case ICmpInst::ICMP_UGE:
     // a > b ? a+x : b+x  ->  max(a, b)+x
     // a > b ? b+x : a+x  ->  min(a, b)+x
     if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(I->getType())) {
       bool Signed = ICI->isSigned();
+      // TODO: Use getExistingSCEV!
       const SCEV *LA = getSCEV(TrueVal);
       const SCEV *RA = getSCEV(FalseVal);
       const SCEV *LS = getSCEV(LHS);
       const SCEV *RS = getSCEV(RHS);
       if (LA->getType()->isPointerTy()) {
         // FIXME: Handle cases where LS/RS are pointers not equal to LA/RA.
         // Need to make sure we can't produce weird expressions involving
         // negated pointers.

 /// to be analyzed by regular SCEV code.
 const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) {
   // Don't attempt to analyze GEPs over unsized objects.
   if (!GEP->getSourceElementType()->isSized())
     return getUnknown(GEP);
 
   SmallVector<const SCEV *, 4> IndexExprs;
   for (Value *Index : GEP->indices())
-    IndexExprs.push_back(getSCEV(Index));
+    IndexExprs.push_back(getExistingSCEV(Index));
   return getGEPExpr(GEP, IndexExprs);
 }
 
 uint32_t ScalarEvolution::GetMinTrailingZerosImpl(const SCEV *S) {
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
     return C->getAPInt().countTrailingZeros();
 
   if (const SCEVPtrToIntExpr *I = dyn_cast<SCEVPtrToIntExpr>(S))

 
 bool ScalarEvolution::loopIsFiniteByAssumption(const Loop *L) {
   // A mustprogress loop without side effects must be finite.
   // TODO: The check used here is very conservative.  It's only *specific*
   // side effects which are well defined in infinite loops.
   return isMustProgress(L) && loopHasNoSideEffects(L);
 }
 
+const SCEV *ScalarEvolution::createSCEVIter(Value *V) {
+  SmallVector<std::pair<Value *, bool>> Stack;
+  SmallVector<Value *> Worklist;
+  SmallPtrSet<Value *, 8> Visited;
+
+  Stack.emplace_back(V, true);
+  Stack.emplace_back(V, false);
+  while (!Stack.empty()) {
+    std::pair<Value *, bool> E = Stack.pop_back_val();
+    if (E.second) {
+      auto *S = getExistingSCEV(E.first);
+      if (!S) {
+        S = createSCEV(E.first);
+        // During PHI resolution, it is possible to create two SCEVs for the
+        // same V, so it is needed to double check whether V->S is inserted into
+        // ValueExprMap before insert S->{V, 0} into ExprValueMap.
+        std::pair<ValueExprMapType::iterator, bool> Pair =
+            ValueExprMap.insert({SCEVCallbackVH(E.first, this), S});
+        if (Pair.second) {
+          ExprValueMap[S].insert({E.first, nullptr});
+
+          // If S == Stripped + Offset, add Stripped -> {V, Offset} into
+          // ExprValueMap.
+          const SCEV *Stripped = S;
+          ConstantInt *Offset = nullptr;
+          std::tie(Stripped, Offset) = splitAddExpr(S);
+          // If stripped is SCEVUnknown, don't bother to save
+          // Stripped -> {V, offset}. It doesn't simplify and sometimes even
+          // increase the complexity of the expansion code.
+          // If V is GetElementPtrInst, don't save Stripped -> {V, offset}
+          // because it may generate add/sub instead of GEP in SCEV expansion.
+          if (Offset != nullptr && !isa<SCEVUnknown>(Stripped) &&
+              !isa<GetElementPtrInst>(E.first))
+            ExprValueMap[Stripped].insert({E.first, Offset});
+        }
+      }
+    } else {
+      if (!Visited.insert(E.first).second || getExistingSCEV(E.first))
+        continue;
+      SmallVector<Value *> Ops;
+      getOperandsToCreate(E.first, Ops);
+      Stack.emplace_back(E.first, true);
+      for (Value *Op : Ops) {
+        Stack.emplace_back(Op, false);
+      }
+    }
+  }
+
+  return getExistingSCEV(V);
+}
+void ScalarEvolution::getOperandsToCreate(Value *V,
+                                          SmallVectorImpl<Value *> &Ops) {
+  if (!isSCEVable(V->getType()))
+    return;
+
+  if (Instruction *I = dyn_cast<Instruction>(V)) {
+    // Don't attempt to analyze instructions in blocks that aren't
+    // reachable. Such instructions don't matter, and they aren't required
+    // to obey basic rules for definitions dominating uses which this
+    // analysis depends on.
+    if (!DT.isReachableFromEntry(I->getParent()))
+      return;
+  } else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
+    return;
+  else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
+    if (!GA->isInterposable())
+      Ops.push_back(GA->getAliasee());
+    return;
+  } else if (!isa<ConstantExpr>(V))
+    return;
+
+  Operator *U = cast<Operator>(V);
+  if (auto BO = MatchBinaryOp(U, DT)) {
+    Ops.push_back(BO->LHS);
+    Ops.push_back(BO->RHS);
+    return;
+  }
+
+  switch (U->getOpcode()) {
+  case Instruction::Trunc:
+  case Instruction::ZExt:
+  case Instruction::SExt:
+  case Instruction::PtrToInt:
+    Ops.push_back(U->getOperand(0));
+    return;
+
+  case Instruction::BitCast:
+    if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) {
+      Ops.push_back(U->getOperand(0));
+      return;
+    }
+    break;
+
+  case Instruction::SDiv:
+  case Instruction::SRem:
+    Ops.push_back(U->getOperand(0));
+    Ops.push_back(U->getOperand(1));
+    return;
+
+  case Instruction::GetElementPtr:
+    if (cast<GEPOperator>(U)->getSourceElementType()->isSized()) {
+      for (Value *Index : U->operands())
+        Ops.push_back(Index);
+    }
+    return;
+
+  case Instruction::IntToPtr:
+    return;
+
+  case Instruction::PHI: {
+    auto *PN = cast<PHINode>(U);
+    const Loop *L = LI.getLoopFor(PN->getParent());
+    Value *BEValueV, *StartValueV;
+    std::tie(StartValueV, BEValueV) = classifyPhiValues(PN, L);
+
+    auto GetFoo = [&]() -> Value * {
+      if (!BEValueV || !StartValueV)
+        return nullptr;
+      auto BO = MatchBinaryOp(BEValueV, DT);
+      if (!BO)
+        return nullptr;
+
+      if (BO->Opcode != Instruction::Add)
+        return nullptr;
+
+      if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
+        return BO->RHS;
+      else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
+        return BO->LHS;
+      return nullptr;
+    };
+
+    if (auto *Acc = GetFoo()) {
+      Ops.push_back(StartValueV);
+      Ops.push_back(Acc);
+      return;
+    }
+    BranchInst *BI = getSelectPhiBr(PN, L, DT, LI);
+    Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
+    if (BI && BI->isConditional() &&
+        BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS)) {
+      Ops.push_back(LHS);
+      Ops.push_back(RHS);
+      return;
+    }
+    return;
+  }
+
+  case Instruction::Select:
+    // U can also be a select constant expr, which let fall through.  Since
+    // createNodeForSelect only works for a condition that is an `ICmpInst`, and
+    // constant expressions cannot have instructions as operands, we'd have
+    // returned getUnknown for a select constant expressions anyway.
+    if (isa<Instruction>(U)) {
+      for (Value *Inc : cast<Instruction>(U)->operands())
+        Ops.push_back(Inc);
+      return;
+    }
+    break;
+
+  case Instruction::Call:
+  case Instruction::Invoke:
+    if (Value *RV = cast<CallBase>(U)->getReturnedArgOperand()) {
+      Ops.push_back(RV);
+      return;
+    }
+
+    if (auto *II = dyn_cast<IntrinsicInst>(U)) {
+      switch (II->getIntrinsicID()) {
+      case Intrinsic::abs:
+        Ops.push_back(II->getArgOperand(0));
+        return;
+      case Intrinsic::umax:
+      case Intrinsic::umin:
+      case Intrinsic::smax:
+      case Intrinsic::smin:
+      case Intrinsic::usub_sat:
+      case Intrinsic::uadd_sat:
+        Ops.push_back(II->getArgOperand(0));
+        Ops.push_back(II->getArgOperand(1));
+        return;
+      case Intrinsic::start_loop_iterations:
+        Ops.push_back(II->getArgOperand(0));
+        return;
+      default:
+        break;
+      }
+    }
+    break;
+  }
+
+  return;
+}
+
 const SCEV *ScalarEvolution::createSCEV(Value *V) {
   if (!isSCEVable(V->getType()))
     return getUnknown(V);
 
   if (Instruction *I = dyn_cast<Instruction>(V)) {
     // Don't attempt to analyze instructions in blocks that aren't
     // reachable. Such instructions don't matter, and they aren't required
     // to obey basic rules for definitions dominating uses which this
     // analysis depends on.
     if (!DT.isReachableFromEntry(I->getParent()))
       return getUnknown(UndefValue::get(V->getType()));
   } else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
     return getConstant(CI);
   else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
-    return GA->isInterposable() ? getUnknown(V) : getSCEV(GA->getAliasee());
+    return GA->isInterposable() ? getUnknown(V)
+                                : getExistingSCEV(GA->getAliasee());
   else if (!isa<ConstantExpr>(V))
     return getUnknown(V);
 
   Operator *U = cast<Operator>(V);
   if (auto BO = MatchBinaryOp(U, DT)) {
     switch (BO->Opcode) {
     case Instruction::Add: {
       // The simple thing to do would be to just call getSCEV on both operands
case Instruction::Add: {
 
           // If a NUW or NSW flag can be applied to the SCEV for this
           // addition, then compute the SCEV for this addition by itself
           // with a separate call to getAddExpr. We need to do that
           // instead of pushing the operands of the addition onto AddOps,
           // since the flags are only known to apply to this particular
           // addition - they may not apply to other additions that can be
           // formed with operands from AddOps.
-          const SCEV *RHS = getSCEV(BO->RHS);
+          const SCEV *RHS = getExistingSCEV(BO->RHS);
           SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op);
           if (Flags != SCEV::FlagAnyWrap) {
-            const SCEV *LHS = getSCEV(BO->LHS);
+            const SCEV *LHS = getExistingSCEV(BO->LHS);
             if (BO->Opcode == Instruction::Sub)
               AddOps.push_back(getMinusSCEV(LHS, RHS, Flags));
             else
               AddOps.push_back(getAddExpr(LHS, RHS, Flags));
             break;
           }
         }
 
         if (BO->Opcode == Instruction::Sub)
-          AddOps.push_back(getNegativeSCEV(getSCEV(BO->RHS)));
+          AddOps.push_back(getNegativeSCEV(getExistingSCEV(BO->RHS)));
         else
-          AddOps.push_back(getSCEV(BO->RHS));
+          AddOps.push_back(getExistingSCEV(BO->RHS));
 
         auto NewBO = MatchBinaryOp(BO->LHS, DT);
         if (!NewBO || (NewBO->Opcode != Instruction::Add &&
                        NewBO->Opcode != Instruction::Sub)) {
-          AddOps.push_back(getSCEV(BO->LHS));
+          AddOps.push_back(getExistingSCEV(BO->LHS));
           break;
         }
         BO = NewBO;
       } while (true);
 
       return getAddExpr(AddOps);
     }
 
     case Instruction::Mul: {
       SmallVector<const SCEV *, 4> MulOps;
       do {
         if (BO->Op) {
           if (auto *OpSCEV = getExistingSCEV(BO->Op)) {
             MulOps.push_back(OpSCEV);
             break;
           }
 
           SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op);
           if (Flags != SCEV::FlagAnyWrap) {
-            MulOps.push_back(
-                getMulExpr(getSCEV(BO->LHS), getSCEV(BO->RHS), Flags));
+            MulOps.push_back(getMulExpr(getExistingSCEV(BO->LHS),
+                                        getExistingSCEV(BO->RHS), Flags));
             break;
           }
         }
 
-        MulOps.push_back(getSCEV(BO->RHS));
+        MulOps.push_back(getExistingSCEV(BO->RHS));
         auto NewBO = MatchBinaryOp(BO->LHS, DT);
         if (!NewBO || NewBO->Opcode != Instruction::Mul) {
-          MulOps.push_back(getSCEV(BO->LHS));
+          MulOps.push_back(getExistingSCEV(BO->LHS));
           break;
         }
         BO = NewBO;
       } while (true);
 
       return getMulExpr(MulOps);
     }
     case Instruction::UDiv:
-      return getUDivExpr(getSCEV(BO->LHS), getSCEV(BO->RHS));
+      return getUDivExpr(getExistingSCEV(BO->LHS), getExistingSCEV(BO->RHS));
     case Instruction::URem:
-      return getURemExpr(getSCEV(BO->LHS), getSCEV(BO->RHS));
+      return getURemExpr(getExistingSCEV(BO->LHS), getExistingSCEV(BO->RHS));
     case Instruction::Sub: {
       SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
       if (BO->Op)
         Flags = getNoWrapFlagsFromUB(BO->Op);
-      return getMinusSCEV(getSCEV(BO->LHS), getSCEV(BO->RHS), Flags);
+      return getMinusSCEV(getExistingSCEV(BO->LHS), getExistingSCEV(BO->RHS),
+                          Flags);
     }
     case Instruction::And:
       // For an expression like x&255 that merely masks off the high bits,
       // use zext(trunc(x)) as the SCEV expression.
       if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
         if (CI->isZero())
-          return getSCEV(BO->RHS);
+          return getExistingSCEV(BO->RHS);
         if (CI->isMinusOne())
-          return getSCEV(BO->LHS);
+          return getExistingSCEV(BO->LHS);
         const APInt &A = CI->getValue();
 
         // Instcombine's ShrinkDemandedConstant may strip bits out of
         // constants, obscuring what would otherwise be a low-bits mask.
         // Use computeKnownBits to compute what ShrinkDemandedConstant
         // knew about to reconstruct a low-bits mask value.
         unsigned LZ = A.countLeadingZeros();
         unsigned TZ = A.countTrailingZeros();
         unsigned BitWidth = A.getBitWidth();
         KnownBits Known(BitWidth);
         computeKnownBits(BO->LHS, Known, getDataLayout(),
                          0, &AC, nullptr, &DT);
 
         APInt EffectiveMask =
             APInt::getLowBitsSet(BitWidth, BitWidth - LZ - TZ).shl(TZ);
         if ((LZ != 0 || TZ != 0) && !((~A & ~Known.Zero) & EffectiveMask)) {
           const SCEV *MulCount = getConstant(APInt::getOneBitSet(BitWidth, TZ));
-          const SCEV *LHS = getSCEV(BO->LHS);
+          const SCEV *LHS = getExistingSCEV(BO->LHS);
           const SCEV *ShiftedLHS = nullptr;
           if (auto *LHSMul = dyn_cast<SCEVMulExpr>(LHS)) {
             if (auto *OpC = dyn_cast<SCEVConstant>(LHSMul->getOperand(0))) {
               // For an expression like (x * 8) & 8, simplify the multiply.
               unsigned MulZeros = OpC->getAPInt().countTrailingZeros();
               unsigned GCD = std::min(MulZeros, TZ);
               APInt DivAmt = APInt::getOneBitSet(BitWidth, TZ - GCD);
               SmallVector<const SCEV*, 4> MulOps;
if (auto BO = MatchBinaryOp(U, DT)) {
     case Instruction::Or:
       // If the RHS of the Or is a constant, we may have something like:
       // X*4+1 which got turned into X*4|1.  Handle this as an Add so loop
       // optimizations will transparently handle this case.
       //
       // In order for this transformation to be safe, the LHS must be of the
       // form X*(2^n) and the Or constant must be less than 2^n.
       if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
-        const SCEV *LHS = getSCEV(BO->LHS);
+        const SCEV *LHS = getExistingSCEV(BO->LHS);
         const APInt &CIVal = CI->getValue();
         if (GetMinTrailingZeros(LHS) >=
             (CIVal.getBitWidth() - CIVal.countLeadingZeros())) {
           // Build a plain add SCEV.
-          return getAddExpr(LHS, getSCEV(CI),
+          return getAddExpr(LHS, getExistingSCEV(CI),
                             (SCEV::NoWrapFlags)(SCEV::FlagNUW | SCEV::FlagNSW));
         }
       }
       break;
 
     case Instruction::Xor:
       if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
         // If the RHS of xor is -1, then this is a not operation.
         if (CI->isMinusOne())
-          return getNotSCEV(getSCEV(BO->LHS));
+          return getNotSCEV(getExistingSCEV(BO->LHS));
 
         // Model xor(and(x, C), C) as and(~x, C), if C is a low-bits mask.
         // This is a variant of the check for xor with -1, and it handles
         // the case where instcombine has trimmed non-demanded bits out
         // of an xor with -1.
         if (auto *LBO = dyn_cast<BinaryOperator>(BO->LHS))
           if (ConstantInt *LCI = dyn_cast<ConstantInt>(LBO->getOperand(1)))
             if (LBO->getOpcode() == Instruction::And &&
                 LCI->getValue() == CI->getValue())
               if (const SCEVZeroExtendExpr *Z =
-                      dyn_cast<SCEVZeroExtendExpr>(getSCEV(BO->LHS))) {
+                      dyn_cast<SCEVZeroExtendExpr>(getExistingSCEV(BO->LHS))) {
                 Type *UTy = BO->LHS->getType();
                 const SCEV *Z0 = Z->getOperand();
                 Type *Z0Ty = Z0->getType();
                 unsigned Z0TySize = getTypeSizeInBits(Z0Ty);
 
                 // If C is a low-bits mask, the zero extend is serving to
                 // mask off the high bits. Complement the operand and
                 // re-apply the zext.
case Instruction::Shl:
           auto MulFlags = getNoWrapFlagsFromUB(BO->Op);
           if ((MulFlags & SCEV::FlagNSW) &&
               ((MulFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1)))
             Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNSW);
           if (MulFlags & SCEV::FlagNUW)
             Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNUW);
         }
 
-        Constant *X = ConstantInt::get(
+        ConstantInt *X = ConstantInt::get(
             getContext(), APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
-        return getMulExpr(getSCEV(BO->LHS), getSCEV(X), Flags);
+        return getMulExpr(getExistingSCEV(BO->LHS), getConstant(X), Flags);
       }
       break;
 
     case Instruction::AShr: {
       // AShr X, C, where C is a constant.
       ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS);
       if (!CI)
         break;
 
       Type *OuterTy = BO->LHS->getType();
       uint64_t BitWidth = getTypeSizeInBits(OuterTy);
       // If the shift count is not less than the bitwidth, the result of
       // the shift is undefined. Don't try to analyze it, because the
       // resolution chosen here may differ from the resolution chosen in
       // other parts of the compiler.
       if (CI->getValue().uge(BitWidth))
         break;
 
       if (CI->isZero())
-        return getSCEV(BO->LHS); // shift by zero --> noop
+        return getExistingSCEV(BO->LHS); // shift by zero --> noop
 
       uint64_t AShrAmt = CI->getZExtValue();
       Type *TruncTy = IntegerType::get(getContext(), BitWidth - AShrAmt);
 
       Operator *L = dyn_cast<Operator>(BO->LHS);
       if (L && L->getOpcode() == Instruction::Shl) {
         // X = Shl A, n
         // Y = AShr X, m
         // Both n and m are constant.
 
-        const SCEV *ShlOp0SCEV = getSCEV(L->getOperand(0));
+        const SCEV *ShlOp0SCEV = getExistingSCEV(L->getOperand(0));
         if (L->getOperand(1) == BO->RHS)
           // For a two-shift sext-inreg, i.e. n = m,
           // use sext(trunc(x)) as the SCEV expression.
           return getSignExtendExpr(
               getTruncateExpr(ShlOp0SCEV, TruncTy), OuterTy);
 
         ConstantInt *ShlAmtCI = dyn_cast<ConstantInt>(L->getOperand(1));
         if (ShlAmtCI && ShlAmtCI->getValue().ult(BitWidth)) {
case Instruction::AShr: {
       }
       break;
     }
     }
   }
 
   switch (U->getOpcode()) {
   case Instruction::Trunc:
-    return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
+    return getTruncateExpr(getExistingSCEV(U->getOperand(0)), U->getType());
 
   case Instruction::ZExt:
-    return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
+    return getZeroExtendExpr(getExistingSCEV(U->getOperand(0)), U->getType());
 
   case Instruction::SExt:
     if (auto BO = MatchBinaryOp(U->getOperand(0), DT)) {
       // The NSW flag of a subtract does not always survive the conversion to
       // A + (-1)*B.  By pushing sign extension onto its operands we are much
       // more likely to preserve NSW and allow later AddRec optimisations.
       //
       // NOTE: This is effectively duplicating this logic from getSignExtend:
       //   sext((A + B + ...)<nsw>) --> (sext(A) + sext(B) + ...)<nsw>
       // but by that point the NSW information has potentially been lost.
       if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
         Type *Ty = U->getType();
-        auto *V1 = getSignExtendExpr(getSCEV(BO->LHS), Ty);
-        auto *V2 = getSignExtendExpr(getSCEV(BO->RHS), Ty);
+        auto *V1 = getSignExtendExpr(getExistingSCEV(BO->LHS), Ty);
+        auto *V2 = getSignExtendExpr(getExistingSCEV(BO->RHS), Ty);
         return getMinusSCEV(V1, V2, SCEV::FlagNSW);
       }
     }
-    return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
+    return getSignExtendExpr(getExistingSCEV(U->getOperand(0)), U->getType());
 
   case Instruction::BitCast:
     // BitCasts are no-op casts so we just eliminate the cast.
     if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType()))
-      return getSCEV(U->getOperand(0));
+      return getExistingSCEV(U->getOperand(0));
     break;
 
   case Instruction::PtrToInt: {
     // Pointer to integer cast is straight-forward, so do model it.
-    const SCEV *Op = getSCEV(U->getOperand(0));
+    const SCEV *Op = getExistingSCEV(U->getOperand(0));
     Type *DstIntTy = U->getType();
     // But only if effective SCEV (integer) type is wide enough to represent
     // all possible pointer values.
     const SCEV *IntOp = getPtrToIntExpr(Op, DstIntTy);
     if (isa<SCEVCouldNotCompute>(IntOp))
       return getUnknown(V);
     return IntOp;
   }
   case Instruction::IntToPtr:
     // Just don't deal with inttoptr casts.
     return getUnknown(V);
 
   case Instruction::SDiv:
     // If both operands are non-negative, this is just an udiv.
-    if (isKnownNonNegative(getSCEV(U->getOperand(0))) &&
-        isKnownNonNegative(getSCEV(U->getOperand(1))))
-      return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1)));
+    if (isKnownNonNegative(getExistingSCEV(U->getOperand(0))) &&
+        isKnownNonNegative(getExistingSCEV(U->getOperand(1))))
+      return getUDivExpr(getExistingSCEV(U->getOperand(0)),
+                         getExistingSCEV(U->getOperand(1)));
     break;
 
   case Instruction::SRem:
     // If both operands are non-negative, this is just an urem.
-    if (isKnownNonNegative(getSCEV(U->getOperand(0))) &&
-        isKnownNonNegative(getSCEV(U->getOperand(1))))
-      return getURemExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1)));
+    if (isKnownNonNegative(getExistingSCEV(U->getOperand(0))) &&
+        isKnownNonNegative(getExistingSCEV(U->getOperand(1))))
+      return getURemExpr(getExistingSCEV(U->getOperand(0)),
+                         getExistingSCEV(U->getOperand(1)));
     break;
 
   case Instruction::GetElementPtr:
     return createNodeForGEP(cast<GEPOperator>(U));
 
   case Instruction::PHI:
     return createNodeForPHI(cast<PHINode>(U));
 
   case Instruction::Select:
     // U can also be a select constant expr, which let fall through.  Since
     // createNodeForSelect only works for a condition that is an `ICmpInst`, and
     // constant expressions cannot have instructions as operands, we'd have
     // returned getUnknown for a select constant expressions anyway.
     if (isa<Instruction>(U))
       return createNodeForSelectOrPHI(cast<Instruction>(U), U->getOperand(0),
                                       U->getOperand(1), U->getOperand(2));
     break;
 
   case Instruction::Call:
   case Instruction::Invoke:
     if (Value *RV = cast<CallBase>(U)->getReturnedArgOperand())
-      return getSCEV(RV);
+      return getExistingSCEV(RV);
 
     if (auto *II = dyn_cast<IntrinsicInst>(U)) {
       switch (II->getIntrinsicID()) {
       case Intrinsic::abs:
         return getAbsExpr(
-            getSCEV(II->getArgOperand(0)),
+            getExistingSCEV(II->getArgOperand(0)),
             /*IsNSW=*/cast<ConstantInt>(II->getArgOperand(1))->isOne());
       case Intrinsic::umax:
-        return getUMaxExpr(getSCEV(II->getArgOperand(0)),
-                           getSCEV(II->getArgOperand(1)));
+        return getUMaxExpr(getExistingSCEV(II->getArgOperand(0)),
+                           getExistingSCEV(II->getArgOperand(1)));
       case Intrinsic::umin:
-        return getUMinExpr(getSCEV(II->getArgOperand(0)),
-                           getSCEV(II->getArgOperand(1)));
+        return getUMinExpr(getExistingSCEV(II->getArgOperand(0)),
+                           getExistingSCEV(II->getArgOperand(1)));
       case Intrinsic::smax:
-        return getSMaxExpr(getSCEV(II->getArgOperand(0)),
-                           getSCEV(II->getArgOperand(1)));
+        return getSMaxExpr(getExistingSCEV(II->getArgOperand(0)),
+                           getExistingSCEV(II->getArgOperand(1)));
       case Intrinsic::smin:
-        return getSMinExpr(getSCEV(II->getArgOperand(0)),
-                           getSCEV(II->getArgOperand(1)));
+        return getSMinExpr(getExistingSCEV(II->getArgOperand(0)),
+                           getExistingSCEV(II->getArgOperand(1)));
       case Intrinsic::usub_sat: {
-        const SCEV *X = getSCEV(II->getArgOperand(0));
-        const SCEV *Y = getSCEV(II->getArgOperand(1));
+        const SCEV *X = getExistingSCEV(II->getArgOperand(0));
+        const SCEV *Y = getExistingSCEV(II->getArgOperand(1));
         const SCEV *ClampedY = getUMinExpr(X, Y);
         return getMinusSCEV(X, ClampedY, SCEV::FlagNUW);
       }
       case Intrinsic::uadd_sat: {
-        const SCEV *X = getSCEV(II->getArgOperand(0));
-        const SCEV *Y = getSCEV(II->getArgOperand(1));
+        const SCEV *X = getExistingSCEV(II->getArgOperand(0));
+        const SCEV *Y = getExistingSCEV(II->getArgOperand(1));
         const SCEV *ClampedX = getUMinExpr(X, getNotSCEV(Y));
         return getAddExpr(ClampedX, Y, SCEV::FlagNUW);
       }
       case Intrinsic::start_loop_iterations:
         // A start_loop_iterations is just equivalent to the first operand for
         // SCEV purposes.
-        return getSCEV(II->getArgOperand(0));
+        return getExistingSCEV(II->getArgOperand(0));
       default:
         break;
       }
     }
     break;
   }
 
   return getUnknown(V);
if (BEExact != getCouldNotCompute()) {
     ++NumTripCountsComputed;
   } else if (Result.getConstantMax(this) == getCouldNotCompute() &&
              isa<PHINode>(L->getHeader()->begin())) {
     // Only count loops that have phi nodes as not being computable.
     ++NumTripCountsNotComputed;
   }
 #endif // LLVM_ENABLE_STATS || !defined(NDEBUG)
 
+  SmallVector<Value *> Recompute;
   // Now that we know more about the trip count for this loop, forget any
   // existing SCEV values for PHI nodes in this loop since they are only
   // conservative estimates made without the benefit of trip count
   // information. This invalidation is not necessary for correctness, and is
   // only done to produce more precise results.
   if (Result.hasAnyInfo()) {
     // Invalidate any expression using an addrec in this loop.
     SmallVector<const SCEV *, 8> ToForget;
     auto LoopUsersIt = LoopUsers.find(L);
-    if (LoopUsersIt != LoopUsers.end())
+    if (LoopUsersIt != LoopUsers.end()) {
       append_range(ToForget, LoopUsersIt->second);
+    }
     forgetMemoizedResults(ToForget);
 
     // Invalidate constant-evolved loop header phis.
     for (PHINode &PN : L->getHeader()->phis())
       ConstantEvolutionLoopExitValue.erase(&PN);
   }
 
   // Re-lookup the insert position, since the call to
   // computeBackedgeTakenCount above could result in a
   // recusive call to getBackedgeTakenInfo (on a different
   // loop), which would invalidate the iterator computed
   // earlier.
-  return BackedgeTakenCounts.find(L)->second = std::move(Result);
+  auto R = BackedgeTakenCounts.find(L);
+  R->second = std::move(Result);
+  for (Value *V : Recompute) {
+    getSCEV(V);
+  }
+
+  return BackedgeTakenCounts.find(L)->second;
 }
 
 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.

llvm/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp

for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
     if (GTI.isStruct())
       continue;
 
     const SCEV *OrigIndexExpr = IndexExprs[I - 1];
     IndexExprs[I - 1] = SE->getZero(OrigIndexExpr->getType());
 
     // The base of this candidate is GEP's base plus the offsets of all
     // indices except this current one.
+    SE->getSCEV(GEP);
     const SCEV *BaseExpr = SE->getGEPExpr(cast<GEPOperator>(GEP), IndexExprs);
     Value *ArrayIdx = GEP->getOperand(I);
     uint64_t ElementSize = DL->getTypeAllocSize(GTI.getIndexedType());
     if (ArrayIdx->getType()->getIntegerBitWidth() <=
         DL->getPointerSizeInBits(GEP->getAddressSpace())) {
       // Skip factoring if ArrayIdx is wider than the pointer size, because
       // ArrayIdx is implicitly truncated to the pointer size.
       factorArrayIndex(ArrayIdx, BaseExpr, ElementSize, GEP);