<html>
<head>
<base href="https://bugs.llvm.org/">
</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 - Analyzer crashes on switch statement with many fall-through case statements"
href="https://bugs.llvm.org/show_bug.cgi?id=52033">52033</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Analyzer crashes on switch statement with many fall-through case statements
</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>Windows NT
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Static Analyzer
</td>
</tr>
<tr>
<th>Assignee</th>
<td>dcoughlin@apple.com
</td>
</tr>
<tr>
<th>Reporter</th>
<td>tauchris@utexas.edu
</td>
</tr>
<tr>
<th>CC</th>
<td>dcoughlin@apple.com, llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=25314" name="attach_25314" title="Reproducer generator script">attachment 25314</a> <a href="attachment.cgi?id=25314&action=edit" title="Reproducer generator script">[details]</a></span>
Reproducer generator script
Given source code that includes a large switch statement with many fall-through
cases, as in:
int f(int m) {
switch (m) {
case 1000:
case 1001:
case 1002:
case 1003:
case 1004:
... <snipped for brevity>
case 28994:
case 28995:
case 28996:
case 28997:
case 28998:
case 28999:
case 29000:
return m + 29070;
}
}
the analyzer crashes (segfault). Such an input file will compile without
error, however. Rather than post a 29000-line reproducer, I've attached
'genhuge.sh' which is a simple bash script that generates the reproducer. The
crash can be reproduced as follows:
CMD> cat genhuge.sh
#!/bin/bash
echo "int f(int m) {"
echo " switch (m) {"
for i in {1000..29000}; do echo " case $i:"; done
echo " return m + 29070;"
echo " }"
echo "}"
CMD> ./genhuge.sh > huge.c
CMD> clang --analyze huge.c
Segmentation fault
Here are the bottom few dozen frames in the stack at the time of the SEGV:
#18676 0x0000000007115f7a in BuildParentMap (M=..., S=0xe0876b8,
OVMode=OV_Transparent) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/AST/ParentMap.cpp:102
#18677 0x0000000007115f7a in BuildParentMap (M=..., S=0xe087658,
OVMode=OV_Transparent) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/AST/ParentMap.cpp:102
#18678 0x0000000007115f7a in BuildParentMap (M=..., S=0xe0875f8,
OVMode=OV_Transparent) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/AST/ParentMap.cpp:102
#18679 0x0000000007115f7a in BuildParentMap (M=..., S=0xe087598,
OVMode=OV_Transparent) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/AST/ParentMap.cpp:102
#18680 0x0000000007115f7a in BuildParentMap (M=..., S=0xe087538,
OVMode=OV_Transparent) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/AST/ParentMap.cpp:102
#18681 0x0000000007115f7a in BuildParentMap (M=..., S=0xe33f180,
OVMode=OV_Transparent) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/AST/ParentMap.cpp:102
#18682 0x0000000007115f7a in BuildParentMap (M=..., S=0xe0874d8,
OVMode=OV_Transparent) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/AST/ParentMap.cpp:102
#18683 0x0000000007115f7a in BuildParentMap (M=..., S=0xe33f198,
OVMode=OV_Transparent) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/AST/ParentMap.cpp:102
#18684 0x0000000007115ff7 in clang::ParentMap::ParentMap (this=0xe08bc70,
S=0xe33f198) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/AST/ParentMap.cpp:112
#18685 0x000000000697d635 in clang::AnalysisDeclContext::getParentMap
(this=0xe08bb10) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/Analysis/AnalysisDeclContext.cpp:281
#18686 0x000000000500db6d in clang::ento::AnalysisManager::getParentMap
(this=0xe040970, D=0xe0873b0) at
/repo/eahcmrh/upstream-llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h:118
#18687 0x0000000004fa3aa5 in (anonymous
namespace)::DeadStoresChecker::checkASTCodeBody (this=0xe034160, D=0xe0873b0,
mgr=..., BR=...) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp:550
#18688 0x0000000004fdc28f in
clang::ento::check::ASTCodeBody::_checkBody<(anonymous
namespace)::DeadStoresChecker> (checker=0xe034160, D=0xe0873b0, mgr=...,
BR=...) at
/repo/eahcmrh/upstream-llvm-project/clang/include/clang/StaticAnalyzer/Core/Checker.h:52
#18689 0x00000000057141cd in clang::ento::CheckerFn<void (clang::Decl const*,
clang::ento::AnalysisManager&,
clang::ento::BugReporter&)>::operator()(clang::Decl const*,
clang::ento::AnalysisManager&, clang::ento::BugReporter&) const
(this=0xe011f60, ps#0=0xe0873b0, ps#1=..., ps#2=...) at
/repo/eahcmrh/upstream-llvm-project/clang/include/clang/StaticAnalyzer/Core/CheckerManager.h:73
#18690 0x000000000570e7b6 in clang::ento::CheckerManager::runCheckersOnASTBody
(this=0xe02ba90, D=0xe0873b0, mgr=..., BR=...) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp:102
#18691 0x0000000004ddf748 in (anonymous
namespace)::AnalysisConsumer::HandleCode (this=0xe02a3f0, D=0xe0873b0, Mode=1,
IMode=clang::ento::ExprEngine::Inline_Minimal, VisitedCallees=0x0) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp:636
#18692 0x0000000004dde6a8 in (anonymous
namespace)::AnalysisConsumer::VisitFunctionDecl (this=0xe02a3f0, FD=0xe0873b0)
at
/repo/eahcmrh/upstream-llvm-project/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp:325
#18693 0x0000000004df37d6 in clang::RecursiveASTVisitor<(anonymous
namespace)::AnalysisConsumer>::WalkUpFromFunctionDecl (this=0xe02a3f0,
D=0xe0873b0) at tools/clang/include/clang/AST/DeclNodes.inc:421
#18694 0x0000000004de8148 in clang::RecursiveASTVisitor<(anonymous
namespace)::AnalysisConsumer>::TraverseFunctionDecl (this=0xe02a3f0,
D=0xe0873b0) at
/repo/eahcmrh/upstream-llvm-project/clang/include/clang/AST/RecursiveASTVisitor.h:2107
#18695 0x0000000004de09f6 in clang::RecursiveASTVisitor<(anonymous
namespace)::AnalysisConsumer>::TraverseDecl (this=0xe02a3f0, D=0xe0873b0) at
tools/clang/include/clang/AST/DeclNodes.inc:421
#18696 0x0000000004ddf043 in (anonymous
namespace)::AnalysisConsumer::runAnalysisOnTranslationUnit (this=0xe02a3f0,
C=...) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp:530
#18697 0x0000000004ddf251 in (anonymous
namespace)::AnalysisConsumer::HandleTranslationUnit (this=0xe02a3f0, C=...) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp:564
#18698 0x00000000058e5073 in clang::ParseAST (S=..., PrintStats=false,
SkipFunctionBodies=false) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/Parse/ParseAST.cpp:171
#18699 0x00000000034dc8e9 in clang::ASTFrontendAction::ExecuteAction
(this=0xe012290) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/Frontend/FrontendAction.cpp:1063
#18700 0x00000000034dc219 in clang::FrontendAction::Execute (this=0xe012290) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/Frontend/FrontendAction.cpp:956
#18701 0x000000000342444b in clang::CompilerInstance::ExecuteAction
(this=0xe006200, Act=...) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/Frontend/CompilerInstance.cpp:974
#18702 0x000000000366366f in clang::ExecuteCompilerInvocation (Clang=0xe006200)
at
/repo/eahcmrh/upstream-llvm-project/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:278
#18703 0x0000000000c5dbfd in cc1_main (Argv=..., Argv0=0xe0026d0
"/repo/eahcmrh/upstream-llvm-project/debug-build-upstream-main/bin/clang-13",
MainAddr=0xc51622 <GetExecutablePath[abi:cxx11](char const*, bool)>) at
/repo/eahcmrh/upstream-llvm-project/clang/tools/driver/cc1_main.cpp:246
#18704 0x0000000000c52bf5 in ExecuteCC1Tool (ArgV=...) at
/repo/eahcmrh/upstream-llvm-project/clang/tools/driver/driver.cpp:317
#18705 0x000000000330bd2f in operator() (__closure=0x7fffffffc280) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/Driver/Job.cpp:405
#18706 0x000000000330c27a in
llvm::function_ref<void()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef>
<span class="quote">>, std::string*, bool*) const::<lambda()> >(intptr_t)</span >
(callable=140737488339584) at
/repo/eahcmrh/upstream-llvm-project/llvm/include/llvm/ADT/STLExtras.h:177
#18707 0x000000000268c57c in llvm::function_ref<void ()>::operator()() const
(this=0x7fffffffbdb0) at
/repo/eahcmrh/upstream-llvm-project/llvm/include/llvm/ADT/STLExtras.h:200
#18708 0x0000000002697c4c in
llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>)
(this=0x7fffffffbe40, Fn=...) at
/repo/eahcmrh/upstream-llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:425
#18709 0x000000000330bf0b in clang::driver::CC1Command::Execute
(this=0xe005d10, Redirects=..., ErrMsg=0x7fffffffc310,
ExecutionFailed=0x7fffffffc30f) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/Driver/Job.cpp:405
#18710 0x00000000032c1cd1 in clang::driver::Compilation::ExecuteCommand
(this=0xe00d880, C=..., FailingCommand=@0x7fffffffc418: 0x0) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/Driver/Compilation.cpp:196
#18711 0x00000000032c2003 in clang::driver::Compilation::ExecuteJobs
(this=0xe00d880, Jobs=..., FailingCommands=...) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/Driver/Compilation.cpp:249
#18712 0x00000000032d0e95 in clang::driver::Driver::ExecuteCompilation
(this=0x7fffffffc6b0, C=..., FailingCommands=...) at
/repo/eahcmrh/upstream-llvm-project/clang/lib/Driver/Driver.cpp:1547
#18713 0x0000000000c53c4c in main (Argc=3, Argv=0x7fffffffde28) at
/repo/eahcmrh/upstream-llvm-project/clang/tools/driver/driver.cpp:489
The recursive call in ParentMap.cpp at line 102 is not infinite -- but the AST
for this syntax is as deep as the number of fall-through cases, and the
recursion is as deep as the AST; so this blows the stack. Looks to me like
this ParentMap models a tree of Stmt pointers, which is information that is
already available in the AST. This "tree" could be built non-recursively and
that would probably avoid blowing the stack (at the cost of some additional
memory, of course). But I'm not completely sure that would be correct.
Obviously, it's true that no implementation of this AST traversal can avoid
crashing. One can always concoct some pathological input pattern that would
blow this algorithm. But in general, I would hope that any syntax that the
compiler can successfully compile should be handled by the analyzer without
crashing. And here, the compiler can easily handle switch statements with an
order of magnitude more cases...</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>