<html>
<head>
<base href="http://llvm.org/bugs/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW --- - Large case ranges take very long time to analyse"
href="http://llvm.org/bugs/show_bug.cgi?id=20914">20914</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Large case ranges take very long time to analyse
</td>
</tr>
<tr>
<th>Product</th>
<td>clang
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>-New Bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedclangbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>magnus.reftel@gmail.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvmbugs@cs.uiuc.edu
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=13024" name="attach_13024" title="Reduced testcase">attachment 13024</a> <a href="attachment.cgi?id=13024&action=edit" title="Reduced testcase">[details]</a></span>
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*) +
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::ProgramState
const>, clang::ento::SymExpr const*, clang::BinaryOperatorKind, llvm::APSInt
const&) + 1142
18 clang-3.6 0x00000000020e9501
clang::ento::SimpleConstraintManager::assumeAux(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState
const>, clang::ento::NonLoc, bool) + 913
19 clang-3.6 0x00000000020ea007
clang::ento::SimpleConstraintManager::assume(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState
const>, clang::ento::NonLoc, bool) + 87
20 clang-3.6 0x00000000020ea13d
clang::ento::SimpleConstraintManager::assume(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState
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::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<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.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
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
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
<a href="http://llvm.org/bugs/">http://llvm.org/bugs/</a> 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:
********************</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>