search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
29.01k stars 11.95k forks source link

clang crashes on valid code at -O1 and above: Assertion `I != ValueState.end() && "V not found in ValueState nor Paramstate map!"' failed #34705

Closed zhendongsu closed 6 years ago

zhendongsu commented 6 years ago
Bugzilla Link 35357
Resolution FIXED
Resolved on Nov 21, 2017 19:05
Version unspecified
OS All

Extended Description

$ clangpolly -v clang version 6.0.0 (http://llvm.org/git/clang.git d80246686d6ad2a749d11470afbbd1bbe4d1b561) (llvm/trunk 318634) Target: x86_64-unknown-linux-gnu Thread model: posix InstalledDir: /home/su/bin Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/4.9 Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/4.9.4 Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/5 Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/5.3.0 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.4 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.4.7 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.6 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.6.4 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.7 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.7.3 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8.5 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9.4 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5.3.0 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6.2.0 Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9 Candidate multilib: .;@m64 Candidate multilib: 32;@m32 Candidate multilib: x32;@mx32 Selected multilib: .;@m64 $ $ clangpolly -O0 -w small.c $ $ clangpolly -O1 -w small.c clang-6.0: /home/su/software/tmp/polly/llvm/lib/Transforms/Scalar/SCCP.cpp:337: llvm::ValueLatticeElement {anonymous}::SCCPSolver::getLatticeValueFor(llvm::Value*): Assertion `I != ValueState.end() && "V not found in ValueState nor Paramstate map!"' failed.

​0 0x00000000023b798a llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/su/software/tmp/polly/llvm/lib/Support/Unix/Signals.inc:402:0

​1 0x00000000023b5b3e llvm::sys::RunSignalHandlers() /home/su/software/tmp/polly/llvm/lib/Support/Signals.cpp:50:0

​2 0x00000000023b5ca0 SignalHandler(int) /home/su/software/tmp/polly/llvm/lib/Support/Unix/Signals.inc:242:0

​3 0x00007fa35cd44330 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x10330)

​4 0x00007fa35bb2cc37 gsignal /build/eglibc-SvCtMH/eglibc-2.19/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0

​5 0x00007fa35bb30028 abort /build/eglibc-SvCtMH/eglibc-2.19/stdlib/abort.c:91:0

​6 0x00007fa35bb25bf6 __assert_fail_base /build/eglibc-SvCtMH/eglibc-2.19/assert/assert.c:92:0

​7 0x00007fa35bb25ca2 (/lib/x86_64-linux-gnu/libc.so.6+0x2fca2)

​8 0x00000000022dbf00 llvm::APInt::operator=(llvm::APInt&&) /home/su/software/tmp/polly/llvm/lib/Transforms/Scalar/SCCP.cpp:336:0

​9 0x00000000022dbf00 operator= /home/su/software/tmp/polly/llvm/include/llvm/IR/ConstantRange.h:47:0

​10 0x00000000022dbf00 operator= /home/su/software/tmp/polly/llvm/include/llvm/Analysis/ValueLattice.h:27:0

​11 0x00000000022dbf00 (anonymous namespace)::SCCPSolver::getLatticeValueFor(llvm::Value*) /home/su/software/tmp/polly/llvm/lib/Transforms/Scalar/SCCP.cpp:338:0

​12 0x00000000022e0693 tryToReplaceWithConstantRange /home/su/software/tmp/polly/llvm/lib/Transforms/Scalar/SCCP.cpp:1619:0

​13 0x00000000022e0693 runIPSCCP(llvm::Module&, llvm::DataLayout const&, llvm::TargetLibraryInfo const*) /home/su/software/tmp/polly/llvm/lib/Transforms/Scalar/SCCP.cpp:1872:0

​14 0x0000000001f1d77a runOnModule /home/su/software/tmp/polly/llvm/lib/IR/LegacyPassManager.cpp:1591:0

​15 0x0000000001f1d77a llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/su/software/tmp/polly/llvm/lib/IR/LegacyPassManager.cpp:1694:0

​16 0x000000000254f2c5 ~PrettyStackTraceString /home/su/software/tmp/polly/llvm/include/llvm/Support/PrettyStackTrace.h:52:0

​17 0x000000000254f2c5 (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete >) /home/su/software/tmp/polly/llvm/tools/clang/lib/CodeGen/BackendUtil.cpp:790:0

​18 0x0000000002550690 ~unique_ptr /usr/include/c++/4.9/bits/unique_ptr.h:235:0

​19 0x0000000002550690 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete >) /home/su/software/tmp/polly/llvm/tools/clang/lib/CodeGen/BackendUtil.cpp:1161:0

​20 0x0000000002d79b5c ~unique_ptr /usr/include/c++/4.9/bits/unique_ptr.h:235:0

​21 0x0000000002d79b5c clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) /home/su/software/tmp/polly/llvm/tools/clang/lib/CodeGen/CodeGenAction.cpp:294:0

​22 0x0000000002f5736c swap /usr/include/c++/4.9/bits/move.h:177:0

​23 0x0000000002f5736c clang::ParseAST(clang::Sema&, bool, bool) /home/su/software/tmp/polly/llvm/tools/clang/lib/Parse/ParseAST.cpp:161:0

​24 0x0000000002d78ff0 clang::CodeGenAction::ExecuteAction() /home/su/software/tmp/polly/llvm/tools/clang/lib/CodeGen/CodeGenAction.cpp:1032:0

​25 0x000000000291199e clang::FrontendAction::Execute() /home/su/software/tmp/polly/llvm/tools/clang/lib/Frontend/FrontendAction.cpp:897:0

​26 0x00000000028e5636 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /home/su/software/tmp/polly/llvm/tools/clang/lib/Frontend/CompilerInstance.cpp:992:0

​27 0x00000000029a89f1 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /home/su/software/tmp/polly/llvm/tools/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:252:0

​28 0x0000000000da2ce8 cc1_main(llvm::ArrayRef<char const>, char const, void*) /home/su/software/tmp/polly/llvm/tools/clang/tools/driver/cc1_main.cpp:221:0

​29 0x0000000000d2e1d3 ExecuteCC1Tool /home/su/software/tmp/polly/llvm/tools/clang/tools/driver/driver.cpp:309:0

​30 0x0000000000d2e1d3 main /home/su/software/tmp/polly/llvm/tools/clang/tools/driver/driver.cpp:388:0

​31 0x00007fa35bb17f45 __libc_start_main /build/eglibc-SvCtMH/eglibc-2.19/csu/libc-start.c:321:0

​32 0x0000000000d9ef29 _start (/home/su/software/tmp/polly/llvm_build/bin/clang-6.0+0xd9ef29)

Stack dump:

  1. Program arguments: /home/su/software/tmp/polly/llvm_build/bin/clang-6.0 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -disable-free -main-file-name small.c -mrelocation-model static -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -resource-dir /home/su/software/tmp/polly/llvm_build/lib/clang/6.0.0 -internal-isystem /usr/local/include -internal-isystem /home/su/software/tmp/polly/llvm_build/lib/clang/6.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O1 -w -fdebug-compilation-dir /data2/c-hunter/test/compilertesting/scripts/speculative-execution/good/clangpolly/build/20171113-clangpolly-m64-O3-build-172531/delta -ferror-limit 19 -fmessage-length 116 -fobjc-runtime=gcc -fdiagnostics-show-option -fcolor-diagnostics -o /tmp/small-7669e2.o -x c small.c
  2. parser at end of file
  3. Per-module optimization passes
  4. Running pass 'Interprocedural Sparse Conditional Constant Propagation' on module 'small.c'. clang-6.0: error: unable to execute command: Aborted (core dumped) clang-6.0: error: clang frontend command failed due to signal (use -v to see invocation) clang version 6.0.0 (http://llvm.org/git/clang.git d80246686d6ad2a749d11470afbbd1bbe4d1b561) (llvm/trunk 318634) Target: x86_64-unknown-linux-gnu Thread model: posix InstalledDir: /home/su/bin clang-6.0: note: diagnostic msg: PLEASE submit a bug report to http://llvm.org/bugs/ and include the crash backtrace, preprocessed source, and associated run script. clang-6.0: note: diagnostic msg:

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT: Preprocessed source(s) and associated run script(s) are located at: clang-6.0: note: diagnostic msg: /tmp/small-574883.c clang-6.0: note: diagnostic msg: /tmp/small-574883.sh clang-6.0: note: diagnostic msg:

$

static int a = 2;

static void f (int c, int d) { c != d; }

int main () { f (a, 1); f (a, 0); return 0; }

llvmbot commented 6 years ago

Fixed:

commit ae8a2fe7f4dbc5220cc827bd8a8e02cef68aba15 Author: Davide Italiano dccitaliano@gmail.com Date: Tue Nov 21 19:00:59 2017 -0800

[SCCP] Pick the right lattice value for constants.

After the dataflow algorithm proves that an argument is constant,
it replaces it value with the integer constant and drops the lattice
value associated to the DEF.

e.g. in the example we have @&#8203;f() that's called twice:
call @&#8203;f(undef, ...)
call @&#8203;f(2, ...)

`undef` MEET 2 = 2 so we replace the argument and all its uses with
the constant 2.

Shortly after, tryToReplaceWithConstantRange() tries to get the lattice
value for the argument we just replaced, causing an assertion.
This function is a little peculiar as it runs when we're doing replacement
and not as part of the solver but still queries the solver.

The fix is that of checking whether we replaced the value already and
get a temporary lattice value for the constant.

Thanks to Zhendong Su for the report!

Fixes llvm/llvm-project#34705 .
llvmbot commented 6 years ago

Patch:

$ git diff HEAD diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 192ba13..30b01ec 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -1615,8 +1615,19 @@ static bool tryToReplaceWithConstantRange(SCCPSolver &Solver, Value *V) { if (!Icmp || !Solver.isBlockExecutable(Icmp->getParent())) continue;

I'll commit once I get home (after a round of testing). Thanks again (and thanks to Florian as he discussed the bug/fix with me).

llvmbot commented 6 years ago

If you run IPSCCP on the example, in the lattice framework you have a value associated to the first argument of @​f, i.e. %c.

The dataflow algorithm you discover the fact that %c can only assume two values:

undef and %0 (i.e. 2)

so: undef MEET 2 == 2

so you can replace %c with 2

and you can get rid of the argument, this happens here if (!AI->use_empty() && tryToReplaceWithConstantRange(Solver,&*AI)) ++IPNumRangeInfoUsed;

but shortly after, tryToReplaceWithConstantRange on a non-existent lattice value, causing the assertion. I'll submit a fix for this soon, thanks for the bug Zhendong.

llvmbot commented 6 years ago

Reduced (run with opt -ipsccp):

@​a = internal global i32 2

define i32 @​main() { entry: call void @​f(i32 undef, i32 1) %0 = load i32, i32* @​a call void @​f(i32 %0, i32 0) ret i32 0 }

define internal void @​f(i32 %c, i32 %d) { entry: %cmp = icmp ne i32 %c, %d ret void }