clang -cc1 -analyze crashes with Assertion `(!BB || Parent == NodeTrait::getParent(const_cast<NodeT *>(BB))) && "cannot get DomTreeNode of block with different parent"' failed.

[mikaelholmen]

llvm commit: 4f07508
Reproduce with:
clang -cc1 -analyze -analyzer-checker=core bbi-98084.c
Result:

clang: ../include/llvm/Support/GenericDomTree.h:401: DomTreeNodeBase<NodeT> *llvm::DominatorTreeBase<clang::CFGBlock, true>::getNode(const NodeT *) const [NodeT = clang::CFGBlock, IsPostDom = true]: Assertion `(!BB || Parent == NodeTrait::getParent(const_cast<NodeT *>(BB))) && "cannot get DomTreeNode of block with different parent"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: build-all/bin/clang -cc1 -analyze -analyzer-checker=core bbi-98084.c
1.	<eof> parser at end of file
 #0 0x00005607f89d9a77 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (build-all/bin/clang+0x7f1ca77)
 #1 0x00005607f89d75de llvm::sys::RunSignalHandlers() (build-all/bin/clang+0x7f1a5de)
 #2 0x00005607f89da13f SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f67d9f0bcf0 __restore_rt (/lib64/libpthread.so.0+0x12cf0)
 #4 0x00007f67d7ac4acf raise (/lib64/libc.so.6+0x4eacf)
 #5 0x00007f67d7a97ea5 abort (/lib64/libc.so.6+0x21ea5)
 #6 0x00007f67d7a97d79 _nl_load_domain.cold.0 (/lib64/libc.so.6+0x21d79)
 #7 0x00007f67d7abd426 (/lib64/libc.so.6+0x47426)
 #8 0x00005607fa6878ff (build-all/bin/clang+0x9bca8ff)
 #9 0x00005607fa686d26 llvm::IDFCalculatorBase<clang::CFGBlock, true>::calculate(llvm::SmallVectorImpl<clang::CFGBlock*>&) (build-all/bin/clang+0x9bc9d26)
#10 0x00005607fa685416 clang::ControlDependencyCalculator::getControlDependencies(clang::CFGBlock*) DebugCheckers.cpp:0:0
#11 0x00005607fa9f61a1 (anonymous namespace)::TrackControlDependencyCondBRVisitor::VisitNode(clang::ento::ExplodedNode const*, clang::ento::BugReporterContext&, clang::ento::PathSensitiveBugReport&) BugReporterVisitors.cpp:0:0
#12 0x00005607fa9e1095 generateVisitorsDiagnostics(clang::ento::PathSensitiveBugReport*, clang::ento::ExplodedNode const*, clang::ento::BugReporterContext&) BugReporter.cpp:0:0
#13 0x00005607fa9dc984 clang::ento::PathSensitiveBugReporter::generatePathDiagnostics(llvm::ArrayRef<clang::ento::PathDiagnosticConsumer*>, llvm::ArrayRef<clang::ento::PathSensitiveBugReport*>&) (build-all/bin/clang+0x9f1f984)
#14 0x00005607fa9dffab clang::ento::PathSensitiveBugReporter::generateDiagnosticForConsumerMap(clang::ento::BugReport*, llvm::ArrayRef<clang::ento::PathDiagnosticConsumer*>, llvm::ArrayRef<clang::ento::BugReport*>) (build-all/bin/clang+0x9f22fab)
#15 0x00005607fa9da2f6 clang::ento::BugReporter::FlushReport(clang::ento::BugReportEquivClass&) (build-all/bin/clang+0x9f1d2f6)
#16 0x00005607fa9da0cb clang::ento::BugReporter::FlushReports() (build-all/bin/clang+0x9f1d0cb)
#17 0x00005607fa5bc7ed (anonymous namespace)::AnalysisConsumer::HandleCode(clang::Decl*, unsigned int, clang::ento::ExprEngine::InliningModes, llvm::DenseSet<clang::Decl const*, llvm::DenseMapInfo<clang::Decl const*, void>>*) AnalysisConsumer.cpp:0:0
#18 0x00005607fa5954bb (anonymous namespace)::AnalysisConsumer::HandleTranslationUnit(clang::ASTContext&) AnalysisConsumer.cpp:0:0
#19 0x00005607fab3fd37 clang::ParseAST(clang::Sema&, bool, bool) (build-all/bin/clang+0xa082d37)
#20 0x00005607f968ccf0 clang::FrontendAction::Execute() (build-all/bin/clang+0x8bcfcf0)
#21 0x00005607f95f7b4f clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (build-all/bin/clang+0x8b3ab4f)
#22 0x00005607f977a8de clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (build-all/bin/clang+0x8cbd8de)
#23 0x00005607f6249576 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (build-all/bin/clang+0x578c576)
#24 0x00005607f6245d1d ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) driver.cpp:0:0
#25 0x00005607f6244a64 clang_main(int, char**, llvm::ToolContext const&) (build-all/bin/clang+0x5787a64)
#26 0x00005607f6256247 main (build-all/bin/clang+0x5799247)
#27 0x00007f67d7ab0d85 __libc_start_main (/lib64/libc.so.6+0x3ad85)
#28 0x00005607f624362e _start (build-all/bin/clang+0x578662e)
Abort (core dumped)

This starts happening with 5ce47a5

Reland "[Support] Assert that DomTree nodes share parent" (#102782)

and I originally reported it here
#102782 (comment)
but that didn't really lead anywhere so now also writing a proper issue to not only have the problem hidden in that merged PR.

bbi-98084.c.gz

[llvmbot]

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

Author: Mikael Holmén (mikaelholmen)

llvm commit: 4f07508 Reproduce with: ```clang -cc1 -analyze -analyzer-checker=core bbi-98084.c``` Result: ``` clang: ../include/llvm/Support/GenericDomTree.h:401: DomTreeNodeBase<NodeT> *llvm::DominatorTreeBase<clang::CFGBlock, true>::getNode(const NodeT *) const [NodeT = clang::CFGBlock, IsPostDom = true]: Assertion `(!BB || Parent == NodeTrait::getParent(const_cast<NodeT *>(BB))) && "cannot get DomTreeNode of block with different parent"' failed. PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script. Stack dump: 0. Program arguments: build-all/bin/clang -cc1 -analyze -analyzer-checker=core bbi-98084.c 1. <eof> parser at end of file #0 0x00005607f89d9a77 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (build-all/bin/clang+0x7f1ca77) #1 0x00005607f89d75de llvm::sys::RunSignalHandlers() (build-all/bin/clang+0x7f1a5de) #2 0x00005607f89da13f SignalHandler(int) Signals.cpp:0:0 #3 0x00007f67d9f0bcf0 __restore_rt (/lib64/libpthread.so.0+0x12cf0) #4 0x00007f67d7ac4acf raise (/lib64/libc.so.6+0x4eacf) #5 0x00007f67d7a97ea5 abort (/lib64/libc.so.6+0x21ea5) #6 0x00007f67d7a97d79 _nl_load_domain.cold.0 (/lib64/libc.so.6+0x21d79) #7 0x00007f67d7abd426 (/lib64/libc.so.6+0x47426) #8 0x00005607fa6878ff (build-all/bin/clang+0x9bca8ff) #9 0x00005607fa686d26 llvm::IDFCalculatorBase<clang::CFGBlock, true>::calculate(llvm::SmallVectorImpl<clang::CFGBlock*>&) (build-all/bin/clang+0x9bc9d26) #10 0x00005607fa685416 clang::ControlDependencyCalculator::getControlDependencies(clang::CFGBlock*) DebugCheckers.cpp:0:0 #11 0x00005607fa9f61a1 (anonymous namespace)::TrackControlDependencyCondBRVisitor::VisitNode(clang::ento::ExplodedNode const*, clang::ento::BugReporterContext&, clang::ento::PathSensitiveBugReport&) BugReporterVisitors.cpp:0:0 #12 0x00005607fa9e1095 generateVisitorsDiagnostics(clang::ento::PathSensitiveBugReport*, clang::ento::ExplodedNode const*, clang::ento::BugReporterContext&) BugReporter.cpp:0:0 #13 0x00005607fa9dc984 clang::ento::PathSensitiveBugReporter::generatePathDiagnostics(llvm::ArrayRef<clang::ento::PathDiagnosticConsumer*>, llvm::ArrayRef<clang::ento::PathSensitiveBugReport*>&) (build-all/bin/clang+0x9f1f984) #14 0x00005607fa9dffab clang::ento::PathSensitiveBugReporter::generateDiagnosticForConsumerMap(clang::ento::BugReport*, llvm::ArrayRef<clang::ento::PathDiagnosticConsumer*>, llvm::ArrayRef<clang::ento::BugReport*>) (build-all/bin/clang+0x9f22fab) #15 0x00005607fa9da2f6 clang::ento::BugReporter::FlushReport(clang::ento::BugReportEquivClass&) (build-all/bin/clang+0x9f1d2f6) #16 0x00005607fa9da0cb clang::ento::BugReporter::FlushReports() (build-all/bin/clang+0x9f1d0cb) #17 0x00005607fa5bc7ed (anonymous namespace)::AnalysisConsumer::HandleCode(clang::Decl*, unsigned int, clang::ento::ExprEngine::InliningModes, llvm::DenseSet<clang::Decl const*, llvm::DenseMapInfo<clang::Decl const*, void>>*) AnalysisConsumer.cpp:0:0 #18 0x00005607fa5954bb (anonymous namespace)::AnalysisConsumer::HandleTranslationUnit(clang::ASTContext&) AnalysisConsumer.cpp:0:0 #19 0x00005607fab3fd37 clang::ParseAST(clang::Sema&, bool, bool) (build-all/bin/clang+0xa082d37) #20 0x00005607f968ccf0 clang::FrontendAction::Execute() (build-all/bin/clang+0x8bcfcf0) #21 0x00005607f95f7b4f clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (build-all/bin/clang+0x8b3ab4f) #22 0x00005607f977a8de clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (build-all/bin/clang+0x8cbd8de) #23 0x00005607f6249576 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (build-all/bin/clang+0x578c576) #24 0x00005607f6245d1d ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) driver.cpp:0:0 #25 0x00005607f6244a64 clang_main(int, char**, llvm::ToolContext const&) (build-all/bin/clang+0x5787a64) #26 0x00005607f6256247 main (build-all/bin/clang+0x5799247) #27 0x00007f67d7ab0d85 __libc_start_main (/lib64/libc.so.6+0x3ad85) #28 0x00005607f624362e _start (build-all/bin/clang+0x578662e) Abort (core dumped) ``` This starts happening with 5ce47a5 ``` Reland "[Support] Assert that DomTree nodes share parent" (#102782) ``` and I originally reported it here https://github.com//pull/102782#issuecomment-2291055153 but that didn't really lead anywhere so now also writing a proper issue to not only have the problem hidden in that merged PR.

bbi-98084.c.gz

[steakhal]

I'll have a look next week. Thanks.

[steakhal]

Node reclamation bites us (again).
Here is a smaller repro: https://compiler-explorer.com/z/KTjxP11vd
(Note that to make the repro reproduce, you need to use the graph-trim-interval=19. Without overriding that interval, one can only came up with really ugly reproducers otherwise to trigger the reclamation.)

struct wrapper { int member; };
void create_vla(const struct wrapper *w) {
  int vla[w->member * 1];
}
void top(struct wrapper wrp) {
  if (wrp.member != 0)
    return;
  create_vla(&wrp);
}

Basically, the VLA size checker detects the bug and creates a bug reports - and also calls bugreporter::trackExpressionValue on the report to track how we ended up with a zero size for the VLA.
That will call Tracker::create(Report)->track(E, InputNode, Opts); then that inside will decompose the expression - in our case the multiplication binop, and track the left operand of it.
It is done by:

const Expr *Inner = peelOffOuterExpr(E, N);
const ExplodedNode *LVNode = findNodeForExpression(N, Inner);
Handler->handle(Inner, N, LVNode, Opts);

Remember that the ExplodedNode that contains the report is protected from node reclamation (ExplodedGraph::shouldCollect), but the LVNode returned by findNodeForExpression is not guaranteed to live long. And in this case, node relamation will indeed reuse that ExplodedNode for a different node, turning this LVNode dangling eventually.

Now, the problem is that we will construct a BugReportVisitor saving this pointer, which will be dangling by the time we get to the report construction - when the bug report visitors kick in. It will refer to a completely different ExplodedNode :D

I'd say we could solve this by "defering" the tracking in trackExpressionValue and exploit the fact that the report node is never reclaimed.
What I'd prefer is to simply disable node reclamation and that would bring the immutability assumption back.

[steakhal]

That said, I think this happens so infrequently, without much actual consequences (without assertions), that I don't think this bug deserves an immediate action.

Users that trip on this, we can suggest setting the graph-trim-interval=0 as a mitigation.

[NagyDonat]

What I'd prefer is to simply disable node reclamation and that would bring the immutability assumption back.

I agree that node reclamation is inelegant, and I would like to see it eliminated from the sources unless that change has a prohibitive impact on performance. What prevents us from disabling it?

[necto]

What prevents us from disabling it?

We have tried to disable it and ran the analysis on a couple of hundreds of open-source projects of various sizes.
For most of them, the effect was on par with regular CI noise, but a couple of projects experienced a noticeable slowdown.
In particular, suffer translation units with large static arrays. For example, llvm/lib/Target/MSP430/MSP430ISelDAGToDAG.cpp analysis takes twice the time if node reclamation is disabled.

Some other performance losers:

| project     | translation unit                                  | w/o  | with | noise |
|-------------+---------------------------------------------------+------+------+-------|
| alibaba-mnn | express/MathOp.cpp                                | 35s  | 24s  | 24s   |
| Clang       | llvm/lib/Target/AArch64/AArch64RegisterInfo.cpp   | 33s  | 26s  | 50s   |
| Clang       | llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp           | 30s  | 23s  | 1s    |
| Clang       | llvm/lib/Target/MSP430/MSP430ISelDAGToDAG.cpp     | 50s  | 32s  | 5s    |
| CPython     | Python/compile.c                                  | 34s  | 22s  | 10s   |
| Firefox     | js/src/vm/Interpreter.cpp                         | 148s | 145s | 4s    |
| HHVM        | hphp/runtime/ext/fileinfo/libmagic/apprentice.cpp | 94s  | 65s  | 1s    |
| Linux       | drivers/media/usb/gspca/topro.c                   | 190s | 56s  | 21s   |
| PHP         | ext/opcache/jit/dynasm/minilua.c                  | 53s  | 22s  | 21s   |
| Ruby        | enc/unicode.c                                     | 55s  | 49s  | 10s   |
| taskflow    | unittests/algorithms.cpp                          | 30s  | 19s  | 16s   |
| taskflow    | unittests/control_flow.cpp                        | 47s  | 29s  | 31s   |
| taskflow    | unittests/pipelines.cpp                           | 54s  | 43s  | 23s   |
| taskflow    | unittests/scalable_pipelines.cpp                  | 43s  | 24s  | 21s   |

[bjope]

IIUC graph-trim-interval is about saving memory, rather that saving CPU time (even thought those might be a bit related). Did you perhaps measure the impact on memory usage as well, or only speed?

[necto]

I did not measure memory impact as we are usually less concerned with memory footprint as long as it is reasonable, and I can only say the footprint remained reasonable.

[bjope]

I did not measure memory impact as we are usually less concerned with memory footprint as long as it is reasonable, and I can only say the footprint remained reasonable.

Ok, thanks.

[NagyDonat]

@steakhal Could you send me the example files where you observed the large slowdowns when you disabled the node reclamation? We are planning that somebody from my team will start working on analyzing them (probably not me, but I'll contribute if needed).

By the way, what was the average performance impact of this change? I see that there were some translation units with +100% or more runtime; but what level of slowdown did you observe on whole projects or if you take an average over all the projects that you analyzed?