Excessive recursion in llvm::ScalarEvolution::getRangeRef

[Quuxplusone]

Bugzilla Link	PR50235
Status	NEW
Importance	P normal
Reported by	Martin Thomson (mt@lowentropy.net)
Reported on	2021-05-05 18:53:39 -0700
Last modified on	2021-05-09 17:41:33 -0700
Version	12.0
Hardware	PC All
CC	dcoughlin@apple.com, florian_hahn@apple.com, htmldeveloper@gmail.com, llvm-bugs@lists.llvm.org, noqnoqneo@gmail.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

This ultimately crashes for the file that I'm using.

The stack is long, but it starts with:

#0  0x00007fdfd438e39a in ?? () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#1  0x00007fdfd4377970 in ?? () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#2  0x00007fdfd438d42b in ?? () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#3  0x00007fdfd4377f26 in ?? () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#4  0x00007fdfd4377970 in ?? () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#5  0x00007fdfd43783db in llvm::computeKnownBits(llvm::Value const*, llvm::DataLayout const&, unsigned int, llvm::AssumptionCache*, llvm::Instruction const*, llvm::DominatorTree const*, llvm::OptimizationRemarkEmitter*, bool) ()
   from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#6  0x00007fdfd43151f2 in llvm::ScalarEvolution::GetMinTrailingZerosImpl(llvm::SCEV const*) ()
   from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7  0x00007fdfd4301716 in llvm::ScalarEvolution::GetMinTrailingZeros(llvm::SCEV const*) ()
   from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#8  0x00007fdfd4315525 in llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*, llvm::ScalarEvolution::RangeSignHint) ()
   from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#9  0x00007fdfd43181b0 in llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*, llvm::ScalarEvolution::RangeSignHint) ()
   from /lib/x86_64-linux-gnu/libLLVM-12.so.1

That last line repeats a few times, until it ends on:

#7575 0x00007fdfd43181b0 in llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*, llvm::ScalarEvolution::RangeSignHint) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7576 0x00007fdfd43181b0 in llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*, llvm::ScalarEvolution::RangeSignHint) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7577 0x00007fdfd43181b0 in llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*, llvm::ScalarEvolution::RangeSignHint) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7578 0x00007fdfd4309cf3 in ?? () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7579 0x00007fdfd42fd46f in llvm::ScalarEvolution::getAddExpr(llvm::SmallVectorImpl<llvm::SCEV const*>&, llvm::SCEV::NoWrapFlags, unsigned int) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7580 0x00007fdfd42febc8 in llvm::ScalarEvolution::getAddExpr(llvm::SmallVectorImpl<llvm::SCEV const*>&, llvm::SCEV::NoWrapFlags, unsigned int) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7581 0x00007fdfd430a2cb in llvm::ScalarEvolution::getGEPExpr(llvm::GEPOperator*, llvm::SmallVectorImpl<llvm::SCEV const*> const&) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7582 0x00007fdfd4314cf9 in llvm::ScalarEvolution::createNodeForGEP(llvm::GEPOperator*) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7583 0x00007fdfd430f009 in llvm::ScalarEvolution::createSCEV(llvm::Value*) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7584 0x00007fdfd430a3b7 in llvm::ScalarEvolution::getSCEV(llvm::Value*) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7585 0x00007fdfd431f611 in llvm::ScalarEvolution::computeExitLimitFromICmp(llvm::Loop const*, llvm::ICmpInst*, bool, bool, bool) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7586 0x00007fdfd431efc5 in llvm::ScalarEvolution::computeExitLimitFromCondImpl(llvm::ScalarEvolution::ExitLimitCache&, llvm::Loop const*, llvm::Value*, bool, bool, bool) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7587 0x00007fdfd431ecbf in llvm::ScalarEvolution::computeExitLimitFromCondCached(llvm::ScalarEvolution::ExitLimitCache&, llvm::Loop const*, llvm::Value*, bool, bool, bool) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7588 0x00007fdfd431e83a in llvm::ScalarEvolution::computeExitLimitFromCond(llvm::Loop const*, llvm::Value*, bool, bool, bool) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7589 0x00007fdfd431e7ba in llvm::ScalarEvolution::computeExitLimit(llvm::Loop const*, llvm::BasicBlock*, bool) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7590 0x00007fdfd431be99 in llvm::ScalarEvolution::computeBackedgeTakenCount(llvm::Loop const*, bool) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7591 0x00007fdfd431aeb3 in llvm::ScalarEvolution::getBackedgeTakenInfo(llvm::Loop const*) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7592 0x00007fdfd4330c0f in llvm::ScalarEvolution::hasLoopInvariantBackedgeTakenCount(llvm::Loop const*) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7593 0x00007fdfd3e0e955 in ?? () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7594 0x00007fdfd3e114fd in ?? () from /lib/x86_64-linux-gnu/libLLVM-12.so.1
#7595 0x00007fdfd4299211 in llvm::LPPassManager::runOnFunction(llvm::Function&) () from /lib/x86_64-linux-gnu/libLLVM-12.so.1

And a few more lines that look to be stable. The height of the stack seems stable.

This might be related to Bug 43249 but I can't tell.

The file that causes this is at https://hg.mozilla.org/projects/nss/file/e78141a928f4b1d98525aacf03043f17e56cac22/gtests/pk11_gtest/pk11_hpke_unittest.cc Building that requires a bit of work (which I'm happy to walk someone through if that is needed). I don't have a shorter repro, sorry.

I'm using the Ubuntu 21.04 distribution with clang version 12. It crashes in earlier versions as well (Ubuntu 20.04 has clang 10; Ubuntu 18.04 with whatever version that has).

[Quuxplusone]

Forgot to add that I was able to build successfully using clang 11 on an Arch Linux distro. What might differ between Ubuntu and Arch in a way that is relevant here is a mystery.

[Quuxplusone]

This is not clang / static analyzer. Moving to new bugs.

[Quuxplusone]

Do you get the same crash when emitting LLVM IR without optimisations from clang (clang -S -emit-llvm -mllvm -disable-llvm-optzns) and then running opt -O1/2/3?

[Quuxplusone]

No crash with -S -emit-llvm -mllvm -disable-llvm-optzns in place of -c.

clang++ -O1 -c crashes with the output; clang++ -c does not.

I can attach the resulting .ll file if that would help.

[Quuxplusone]

(In reply to Martin Thomson from comment #4)

No crash with -S -emit-llvm -mllvm -disable-llvm-optzns in place of -c.

clang++ -O1 -c crashes with the output; clang++ -c does not.

I can attach the resulting .ll file if that would help.

Does running opt -O1 crash with the .ll file? If it does, please attache the file.

If it doesn't, you could try to printing/dumping the IR before the crashing pass (e.g. clang -O1 -mllvm -print-before-all -mllvm -print-module-scope) and try if the last dump of the module crashes when running opt -pass .... (the above produces a lot of output, you can also use -mllvm -print-before=pass-name if you know the pass name).

[Quuxplusone]

Yes, clang++ -O1 -c file.ll crashes. However, as the file is 40M (!) - and almost 4M compressed - I can't upload it here. Here's a gist: https://gist.github.com/martinthomson/2039aeadfc23612c6b6117f254d35a3a

Now that I see that 520k lines, it's possible that this is just a case of "too bad, too big".

FWIW, while this stresses gcc, it doesn't crash (except when producing aarch64 code, for some reason). gcc is much slower than clang compiling the original source and it uses a staggering 1.5G of RAM to do so, but it manages. It produces an interesting warning at -O1, indicating that there is some inbuilt protection against things getting out of hand: note: variable tracking size limit exceeded with '-fvar-tracking-assignments', retrying without.