Stack overflow in ScalarEvolution

[llvmbot]

Bugzilla Link	45201
Version	10.0
OS	Windows NT
Blocks	#44654
Reporter	LLVM Bugzilla Contributor
CC	@efriedma-quic,@ekatz,@zmodem,@LebedevRI,@zygoloid,@tstellar

Extended Description

While I don't have a repro, I'm seeing the following issue when using 10.x release branch to compile one of our codebases on Windows.

clang-cl.exe!?filt$0@0@RunSafely@CrashRecoveryContext@llvm@@() Line 229	C++
clang-cl.exe!__C_specific_handler(_EXCEPTION_RECORD * ExceptionRecord=0x00000007a2203630, void * EstablisherFrame=0x00000007a2b8de50, _CONTEXT * ContextRecord, _DISPATCHER_CONTEXT * DispatcherContext=0x00000007a2202fc0) Line 290	C++
ntdll.dll!RtlpExecuteHandlerForException()	Unknown
ntdll.dll!RtlDispatchException()	Unknown
ntdll.dll!KiUserExceptionDispatch()	Unknown
clang-cl.exe!llvm::ScalarEvolution::checkValidity(const llvm::SCEV * S=0x000001c6a0a7d1a8) Line 3810	C++
clang-cl.exe!llvm::ScalarEvolution::getExistingSCEV(llvm::Value * V) Line 3944	C++
clang-cl.exe!llvm::ScalarEvolution::getSCEV(llvm::Value * V=0x000001c6cb578e20) Line 3909	C++

clang-cl.exe!llvm::ScalarEvolution::createNodeForGEP(llvm::GEPOperator * GEP=0x000001c6dac37090) Line 5447 C++
clang-cl.exe!llvm::ScalarEvolution::createSCEV(llvm::Value * V) Line 6524 C++
clang-cl.exe!llvm::ScalarEvolution::getSCEV(llvm::Value * V=0x000001c6dac37090) Line 3911 C++
clang-cl.exe!llvm::ScalarEvolution::getGEPExpr(llvm::GEPOperator * GEP=0x000001c6dac37110, const llvm::SmallVectorImpl<const llvm::SCEV *> & IndexExprs={...}) Line 3495 C++
clang-cl.exe!llvm::ScalarEvolution::createNodeForGEP(llvm::GEPOperator * GEP=0x000001c6dac37110) Line 5448 C++
clang-cl.exe!llvm::ScalarEvolution::createSCEV(llvm::Value * V) Line 6524 C++
clang-cl.exe!llvm::ScalarEvolution::getSCEV(llvm::Value * V=0x000001c6dac37110) Line 3911 C++
clang-cl.exe!llvm::ScalarEvolution::getGEPExpr(llvm::GEPOperator * GEP=0x000001c6dac37710, const llvm::SmallVectorImpl<const llvm::SCEV *> & IndexExprs={...}) Line 3495 C++

Is this something that was fixed in master? Is this a stack size issue? (#10090 )? I'd be happy to debug if you instruct me what to do?

[efriedma-quic]

I don't think anything relevant has landed in master recently.

The repeated "getGEPExpr(llvm::GEPOperator * GEP=0x000001c6dac37110" looks suspicious; if that's actually correct, this might actually be infinite recursion, not just an issue of running out of stack. The only way I can think of to make that happen is if some other pass isn't correctly preserving the dominator tree.

Are you using an LLVM build with assertions enabled?

[llvmbot]

Yes, this is a Release build with assertions are enabled. There's a first signal triggered by the stack overflow. Then while trying to print the stack trace, it crashes on V->getName(). I can try a Debug build see if I can get more info.
If there's any specific option I should enable, please let me know!

[efriedma-quic]

Maybe build with LLVM_ENABLE_EXPENSIVE_CHECKS; that runs some extra verification for domtrees.

A Debug build would be nice to get a stack trace that describes all the arguments accurately. But it probably won't trigger any other useful messages if you're already building with assertions enabled.

[zmodem]

Can you bisect to try and see if this was introduced recently?

[llvmbot]

I've tried c-reducing it with the latest c-reduce checkout built along LLVM 10, but it keeps failing in creduce_delta.exe:

Assertion failed: getPiece(StartPiece).size() > NumBytes, file D:\llvm-project\clang\lib\Rewrite\RewriteRope.cpp, line 380

I will attempt bisection.

[llvmbot]

Rather than trying to see what broke this, I attempted to see which patch fixed this issue. git bisect leads to: 44edc6f

Although it does not cherry-pick cleanly on 10.x.

Roman, can this be backported? Are other patched needed? (there are quite a few before that change)

We can leave it for 10.0.1 if we want to ship as-it-is, I simply wanted to try it in our downstream.

[LebedevRI]

Rather than trying to see what broke this, I attempted to see which patch
fixed this issue. git bisect leads to:
https://github.com/llvm/llvm-project/commit/
44edc6f
Can you try fcc2238 + 18eae33 (D70097 "[SCEV] Add missing cache queries") instead,
maybe they also solve the issue?

Although it does not cherry-pick cleanly on 10.x.

Roman, can this be backported? Are other patched needed? (there are quite a
few before that change)

We can leave it for 10.0.1 if we want to ship as-it-is, I simply wanted to
try it in our downstream.

I would advise against backporting that patchset.
Messing with costmodelling tends to lead to performance skewing,
as reported in https://reviews.llvm.org/D73501#1905171

[llvmbot]

I applied fcc2238 and 18eae33 on 10.x as advised but I still get the crash.

[LebedevRI]

Then i'm afraid some linux-based reproducer is needed here.

[ekatz]

Hi, is there a testcase you can upload?

[llvmbot]

I'm working on it.

Currently I'm trying creduce 2.8 on Linux, along with a already preprocessed .CPP file (which is quite big, 40 MB) and a interest.sh such as:

#!/bin/bash
/mnt/f/llvm-project/buildWSL/bin/clang-cl /mnt/f/llvm-project/pre.cpp /c /W0 /EHsc /std:c++17 -Xclang -O3 -march=skylake-avx512 -fno-integrated-cc1 2>&1 | grep 'Stack dump:'

However it seems that the creduce pass "pass_clang_binsrch :: replace-function-def-with-decl" reduces too much and evicts the crashing function from the reduced .CPP.

What are the case reduction techniques you all use? Any pro tips here?

[llvmbot]

Never mind, I suppose the path to the .CPP file should be relative. But I'd be still interested to hear what other techniques can be used :)

[llvmbot]

Sorry for the delay. Turns out the repro is quite simple. The following fails for checkouts before 44edc6f (so it fails for release 10.x as well, as stated before). This only occurs for -O3, not -O2.

$ cat a.cpp
void a() {
int *b;
for (;;)
for (int c = 0; c < 128; c++)
for (int d = 0; d < 128; d++) {
*b = 0;
b++;
}
}

$ clang-cl a.cpp /c -Xclang -O3
Stack dump:
0. Program arguments: buildninjaRel\bin\clang-cl pre.cpp /c -Xclang -O3

1.  <eof> parser at end of file
   

2.  Per-module optimization passes
   

3.  Running pass 'CallGraph Pass Manager' on module 'pre.cpp'.
   

4.  Running pass 'Loop Pass Manager' on function '@"?a@@YAXXZ"'
   

5.  Running pass 'Induction Variable Simplification' on basic block '%
   

Is it worth adding a test to cover this case?

[zmodem]

$ cat a.cpp
void a() {
int *b;
for (;;)
for (int c = 0; c < 128; c++)
for (int d = 0; d < 128; d++) {
*b = 0;
b++;
}
}

$ clang-cl a.cpp /c -Xclang -O3

This also fails on the 9.x branch, which makes me less worried about it from a 10.0.0 perspective.

[llvmbot]

Hello,

It seems the repro described above occurs again after 7d572ef.

Roman, any chance that you'll reland 44edc6f?