assert in SCEV

[llvmbot]

Bugzilla Link	3909
Resolution	WORKSFORME
Resolved on	Apr 22, 2009 02:19
Version	unspecified
OS	Linux
Attachments	test case, generated by the LLVM D compiler and simplified manually
Reporter	LLVM Bugzilla Contributor
CC	@nlewycky

Extended Description

Assembling the attached code with 'llc bug.bc' triggers the assert

ScalarEvolutionExpressions.h:570: RetVal llvm::SCEVVisitor<SC, RetVal>::visitCouldNotCompute(llvm::SCEVCouldNotCompute*) [with SC = llvm::SCEVExpander, RetVal = llvm::Value*]: Assertion `0 && "Invalid use of SCEVCouldNotCompute!"' failed.

with LLVM 2.5. The issue seems to be i64 related: if you replace all i64s with i32s, the code is assembled fine. The backtrace is:

4 libc.so.6 0xb7d01f25 __assert_fail + 245
5 llc 0x08d0fc9a llvm::LoopBasellvm::BasicBlock::isLoopInvariant(llvm::Value*) const + 0
6 llc 0x08d10861 llvm::SCEVVisitor<llvm::SCEVExpander, llvm::Value*>::visit(llvm::SCEV*) + 337
7 llc 0x08d0e3fd llvm::SCEVExpander::expand(llvm::SCEV*) + 161
8 llc 0x08d0f0f2 llvm::SCEVExpander::visitAddRecExpr(llvm::SCEVAddRecExpr*) + 1956
9 llc 0x08d10802 llvm::SCEVVisitor<llvm::SCEVExpander, llvm::Value*>::visit(llvm::SCEV*) + 242
10 llc 0x08d0e3fd llvm::SCEVExpander::expand(llvm::SCEV*) + 161
11 llc 0x08d0e46d llvm::SCEVExpander::expandCodeFor(llvm::SCEVHandle, llvm::Instruction*) + 41
12 llc 0x08c854d0
13 llc 0x08c87748
14 llc 0x08ce83af llvm::LPPassManager::runOnFunction(llvm::Function&) + 911
15 llc 0x08d91a0e llvm::FPPassManager::runOnFunction(llvm::Function&) + 258
16 llc 0x08d91f98 llvm::FunctionPassManagerImpl::run(llvm::Function&) + 116
17 llc 0x08d920f1 llvm::FunctionPassManager::run(llvm::Function&) + 137
18 llc 0x08513503 main + 2479

[llvmbot]

This looks familiar. Offhand I think this is fixed in trunk, and was due to the rounding-up then capping of the binomial coefficient calculation to 64 bits to prevent hitting the unsupported 'arbitrary precision integer' codepath.

I'll check that hypothesis and if so, find the bug and dupe it.

[nlewycky]

That's odd. I just tried this with trunk and got an entirely different failure:

(gdb) run pr3909.bc
Starting program: /home/nicholas/llvm-commit/Debug/bin/llc pr3909.bc
[Thread debugging using libthread_db enabled]
Call result #​2 has unhandled type i32
[New Thread 0xf7c6d6d0 (LWP 10951)]

Program received signal SIGABRT, Aborted.
[Switching to Thread 0xf7c6d6d0 (LWP 10951)]
0xffffe425 in __kernel_vsyscall ()
(gdb) bt
#​0 0xffffe425 in __kernel_vsyscall ()
#​1 0xf7c9a640 in __GI_raise (sig=6)
at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#​2 0xf7c9c008 in __GI_abort () at abort.c:88
#​3 0x0856b505 in llvm::CCState::AnalyzeCallResult (this=0xffc5f1f0,
TheCall=0x8fd1bf4, Fn=0x853347d <RetCC_X86>) at CallingConvLower.cpp:135
#​4 0x0852e2eb in llvm::X86TargetLowering::LowerCallResult (this=0x8fac37c,
Chain={Node = 0x8fd1750, ResNo = 0}, InFlag={Node = 0x8fd1750, ResNo = 1},
TheCall=0x8fd1bf4, CallingConv=0, DAG=@0x8fb9190)
at X86ISelLowering.cpp:1075
#​5 0x08530e37 in llvm::X86TargetLowering::LowerCALL (this=0x8fac37c, Op=
{Node = 0x8fd1bf4, ResNo = 0}, DAG=@0x8fb9190)
at X86ISelLowering.cpp:1919
#​6 0x08531f21 in llvm::X86TargetLowering::LowerOperation (this=0x8fac37c, Op=
{Node = 0x8fd1bf4, ResNo = 0}, DAG=@0x8fb9190)
at X86ISelLowering.cpp:6966
#​7 0x086457e1 in LegalizeOp (this=0xffc60ff0, Op=
{Node = 0x8fd1bf4, ResNo = 0}) at LegalizeDAG.cpp:1559
#​8 0x0867a28f in HandleOp (this=0xffc60ff0, Op={Node = 0x8fd1bf4, ResNo = 0})
at LegalizeDAG.cpp:520
#​9 0x0867a510 in LegalizeDAG (this=0xffc60ff0) at LegalizeDAG.cpp:390
#​10 0x0867a698 in llvm::SelectionDAG::Legalize (this=0x8fb9190,
TypesNeedLegalizing=false, Fast=false) at LegalizeDAG.cpp:8652
#​11 0x0861716e in llvm::SelectionDAGISel::CodeGenAndEmitDAG (this=0x8fb8a58)
at SelectionDAGISel.cpp:624
#​12 0x0861979c in llvm::SelectionDAGISel::SelectBasicBlock (this=0x8fb8a58,
LLVMBB=0x8faaa28, Begin=
{<bidirectional_iterator<llvm::Instruction, int>> = {<std::iterator<std::bidirectional_iterator_tag, llvm::Instruction, int, llvm::Instruction, llvm::Instruction&>> = {}, }, NodePtr = 0x8fcd970}, End=
{<bidirectional_iterator<llvm::Instruction, int>> = {<std::iterator<std::bidirectional_iterator_tag, llvm::Instruction, int, llvm::Instruction, llvm::Instruction&>> = {}, }, NodePtr = 0x8faaa28})
at SelectionDAGISel.cpp:498
#​13 0x0861a19b in llvm::SelectionDAGISel::SelectAllBasicBlocks (
this=0x8fb8a58, Fn=@0x8fa9aa0, MF=@0x8fac0c8, MMI=0x8fc7990, DW=0x8fbcda0,
TII=@0x8fac2c8) at SelectionDAGISel.cpp:854
#​14 0x0861af47 in llvm::SelectionDAGISel::runOnFunction (this=0x8fb8a58,
Fn=@0x8fa9aa0) at SelectionDAGISel.cpp:325
#​15 0x089380e8 in llvm::FPPassManager::runOnFunction (this=0x8faa6f8,
F=@0x8fa9aa0) at PassManager.cpp:1324
#​16 0x08938bd6 in llvm::FunctionPassManagerImpl::run (this=0x8faa4e8,
F=@0x8fa9aa0) at PassManager.cpp:1281
#​17 0x08938d5f in llvm::FunctionPassManager::run (this=0xffc613e8,
F=@0x8fa9aa0) at PassManager.cpp:1233
#​18 0x08049cb4 in main (argc=2, argv=0xffc61514) at llc.cpp:322

Just to repeat the error in case you missed it:
"Call result #​2 has unhandled type i32"

Christian, could you please try something? With your version of LLVM, does it crash if you say "opt -analyze -scalar-evolution bug.bc"? If it does, then the SCEV issues is fixed in trunk, but a new one has emerged in the backend.

[llvmbot]

"opt -analyze -scalar-evolution bug.bc" seems to terminate normally with

Determining loop execution counts for: _Dmain
Loop whilecond3: Unpredictable iteration count.
Loop whilebody: Unpredictable iteration count.

LDC's -O3 set of optimizations does crash though. I'll try to figure out which one it is later.

[llvmbot]

I can reproduce the bug on LLVM 2.5 with "opt -indvars bug.bc"

[llvmbot]

This does not reproduce with LLVM TOT. Please reopen if you can reproduce it again.