search

llvm / llvm-project

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

Large case ranges take very long time to analyse #21288

Closed llvmbot closed 1 year ago

llvmbot commented 10 years ago
Bugzilla Link 20914
Version trunk
OS All
Attachments Reduced testcase
Reporter LLVM Bugzilla Contributor

Extended Description

The following small test function, reduced from production code, makes the Clang Static Analyzer crash:

void f(int i) { switch(i) { case 0 ... 1000000000: break; } }

Smaller case ranges work OK but have a execution time roughly linearly growing with the range size, up to a point at about 200000 on my machine, when it starts climbing quicker. Memory usage seems to grow roughly linearly up to a range size 400000 (using ~250MB), at which point I stopped the test.

With a one-billion range, the following is eventually printed when analyzed with r215621:

terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc 0 clang-3.6 0x00000000013b6b42 llvm::sys::PrintStackTrace(_IO_FILE) + 34 1 clang-3.6 0x00000000013b66f4 2 libpthread.so.0 0x00007fe865305340 3 libc.so.6 0x00007fe86452cbb9 gsignal + 57 4 libc.so.6 0x00007fe86452ffc8 abort + 328 5 libstdc++.so.6 0x00007fe864e386b5 __gnu_cxx::__verbose_terminate_handler() + 341 6 libstdc++.so.6 0x00007fe864e36836 7 libstdc++.so.6 0x00007fe864e36863 8 libstdc++.so.6 0x00007fe864e36aa2 9 libstdc++.so.6 0x00007fe864e36f8d operator new(unsigned long) + 125 10 clang-3.6 0x00000000020cf034 11 clang-3.6 0x00000000020d07f2 12 clang-3.6 0x00000000020d2293 13 clang-3.6 0x00000000020d27bb 14 clang-3.6 0x00000000020d4c60 15 clang-3.6 0x00000000020d5615 16 clang-3.6 0x00000000020d809c 17 clang-3.6 0x00000000020e9056 clang::ento::SimpleConstraintManager::assumeSymRel(llvm::IntrusiveRefCntPtr, clang::ento::SymExpr const, clang::BinaryOperatorKind, llvm::APSInt const&) + 1142 18 clang-3.6 0x00000000020e9501 clang::ento::SimpleConstraintManager::assumeAux(llvm::IntrusiveRefCntPtr, clang::ento::NonLoc, bool) + 913 19 clang-3.6 0x00000000020ea007 clang::ento::SimpleConstraintManager::assume(llvm::IntrusiveRefCntPtr, clang::ento::NonLoc, bool) + 87 20 clang-3.6 0x00000000020ea13d clang::ento::SimpleConstraintManager::assume(llvm::IntrusiveRefCntPtr, clang::ento::DefinedSVal, bool) + 125 21 clang-3.6 0x00000000020872e3 22 clang-3.6 0x0000000002088af4 clang::ento::ExprEngine::processSwitch(clang::ento::SwitchNodeBuilder&) + 804 23 clang-3.6 0x0000000002077c1e clang::ento::CoreEngine::HandleBlockExit(clang::CFGBlock const, clang::ento::ExplodedNode) + 526 24 clang-3.6 0x0000000002077dc0 clang::ento::CoreEngine::HandlePostStmt(clang::CFGBlock const, unsigned int, clang::ento::ExplodedNode) + 96 25 clang-3.6 0x0000000002079117 clang::ento::CoreEngine::dispatchWorkItem(clang::ento::ExplodedNode, clang::ProgramPoint, clang::ento::WorkListUnit const&) + 439 26 clang-3.6 0x00000000020791df clang::ento::CoreEngine::ExecuteWorkList(clang::LocationContext const, unsigned int, llvm::IntrusiveRefCntPtr) + 191 27 clang-3.6 0x0000000001a9485e 28 clang-3.6 0x0000000001a95005 29 clang-3.6 0x0000000001aa10a4 30 clang-3.6 0x0000000001aa2273 clang::ParseAST(clang::Sema&, bool, bool) + 483 31 clang-3.6 0x0000000001518706 clang::FrontendAction::Execute() + 118 32 clang-3.6 0x00000000014fa2d0 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) + 256 33 clang-3.6 0x0000000001585641 clang::ExecuteCompilerInvocation(clang::CompilerInstance) + 1921 34 clang-3.6 0x00000000007fd6e8 cc1_main(char const, char const, char const, void*) + 1304 35 clang-3.6 0x00000000007da3ff main + 8575 36 libc.so.6 0x00007fe864517ec5 __libc_start_main + 245 37 clang-3.6 0x00000000007fb982 Stack dump:

  1. Program arguments: /opt/llvm/215621/bin/clang-3.6 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -main-file-name case_range.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-output plist -w -mrelocation-model static -mdisable-fp-elim -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -resource-dir /opt/llvm/215621/bin/../lib/clang/3.6.0 -internal-isystem /usr/local/include -internal-isystem /opt/llvm/215621/bin/../lib/clang/3.6.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fdebug-compilation-dir /home/reftel/src/clang/case_range -ferror-limit 19 -fmessage-length 80 -mstackrealign -fobjc-runtime=gcc -fdiagnostics-show-option -fcolor-diagnostics -o case_range.plist -x c case_range.c
  2. parser at end of file clang-3.6: error: unable to execute command: Aborted (core dumped) clang-3.6: error: clang frontend command failed due to signal (use -v to see invocation) clang version 3.6.0 Target: x86_64-unknown-linux-gnu Thread model: posix clang-3.6: 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-3.6: note: diagnostic msg: ********************

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

llvmbot commented 9 years ago

Status as of revision 222788 is that ranges work a lot better, but that very large ranges still consume all memory on the system (approximately 1GB per million numbers in the range).

Endilll commented 1 year ago

Appears to be fixed in Clang 3.8.

llvmbot commented 1 year ago

@llvm/issue-subscribers-clang-static-analyzer