[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

7141

Poison, poison! :)

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

7141

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

7173

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.

7199

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

7173

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.

7199

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

7259

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

7259

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

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);
-  }
+  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))
+  if (BO->LHS == PN && L->isLoopInvariant(BO->RHS)) {
     Accum = getSCEV(BO->RHS);
-  else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
+    assert(Accum);
+  } else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS)) {
     Accum = getSCEV(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) &&
 
   return nullptr;
 }
 
 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
   if (const SCEV *S = createAddRecFromPHI(PN))
     return S;
 
const SCEV *ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
   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.

 
 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 isFinite(L) || (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);
+      }
+    } 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

llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

 define void @test_shl6(i1 %c) {
 ; CHECK-LABEL: 'test_shl6'
 ; CHECK-NEXT:  Classifying expressions for: @test_shl6
 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ]
 ; CHECK-NEXT:    --> %iv.shl U: [4,65) S: [4,65) Exits: 16 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %shiftamt = and i64 %iv, 1
 ; CHECK-NEXT:    --> (zext i1 {false,+,true}<%loop> to i64) U: [0,2) S: [0,2) Exits: 0 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.shl.next = shl i64 %iv.shl, %shiftamt
 ; CHECK-NEXT:    --> %iv.shl.next U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: 16 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_shl6
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4