[LLVMbugs] [Bug 20914] New: Large case ranges take very long time to analyse

bugzilla-daemon at llvm.org bugzilla-daemon at llvm.org
Thu Sep 11 22:26:36 PDT 2014


            Bug ID: 20914
           Summary: Large case ranges take very long time to analyse
           Product: clang
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: -New Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: magnus.reftel at gmail.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Created attachment 13024
  --> http://llvm.org/bugs/attachment.cgi?id=13024&action=edit
Reduced testcase

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*) +
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
const>, clang::ento::SymExpr const*, clang::BinaryOperatorKind, llvm::APSInt
const&) + 1142
18 clang-3.6       0x00000000020e9501
const>, clang::ento::NonLoc, bool) + 913
19 clang-3.6       0x00000000020ea007
const>, clang::ento::NonLoc, bool) + 87
20 clang-3.6       0x00000000020ea13d
const>, 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::ProgramPoint, clang::ento::WorkListUnit const&) + 439
26 clang-3.6       0x00000000020791df
clang::ento::CoreEngine::ExecuteWorkList(clang::LocationContext const*,
unsigned int, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>) + 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:
0.      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.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 
1.      <eof> 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
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: 

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: 


You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20140912/429b7416/attachment.html>

More information about the llvm-bugs mailing list