analyzer: bulk merger/processing of runs of nodes at CFG join points
Prior to this patch the analyzer worklist considered only one node or
two nodes at a time, processing and/or merging state individually or
pairwise.
This could lead to explosions of merger nodes at CFG join points,
especially after switch statements, which could have large numbers
of in-edges, and thus large numbers of merger exploded_nodes could
be created, exceeding the per-point limit and thus stopping analysis
with -Wanalyzer-too-complex.
This patch special-cases the handling for runs of consecutive
nodes in the worklist at a CFG join point, processing and merging
them all together.
The patch fixes a state explosion seen in bzip2.c seen when attempting
to reproduce PR analyzer/95188, in a switch statement in a loop for
argument parsing. With this patch, the analyzer successfully
consolidates the state after the argument parsing to a single exploded
node.
In gcc.dg/analyzer/pr96653.c there is a switch statement with over 300
cases which leads to hitting the per-point limit. With this patch
the consolidation code doesn't manage to merge all of them due to other
worklist-ordering bugs, and it still hits the per-point limits, but it
does manage some very long consolidations:
merged 2 in-enodes into 2 out-enode(s) at SN: 403
merged 2 in-enodes into 2 out-enode(s) at SN: 403
merged 2 in-enodes into 1 out-enode(s) at SN: 11
merged 29 in-enodes into 1 out-enode(s) at SN: 35
merged 6 in-enodes into 1 out-enode(s) at SN: 41
merged 31 in-enodes into 1 out-enode(s) at SN: 35
and with a followup patch to fix an SCC issue it manages:
merged 358 in-enodes into 2 out-enode(s) at SN: 402
The patch appears to fix the failure on non-x86_64 of:
gcc.dg/analyzer/pr93032-mztools.c (test for excess errors)
which is PR analyzer/96616.
Unfortunately, the patch introduces a memory leak false positive in
gcc.dg/analyzer/pr94851-1.c, but this appears to be a pre-existing bug
that was hidden by state-merging failures.
gcc/analyzer/ChangeLog:
* engine.cc (exploded_node::dump_dot): Show STATUS_BULK_MERGED.
(exploded_graph::process_worklist): Call
maybe_process_run_of_before_supernode_enodes.
(exploded_graph::maybe_process_run_of_before_supernode_enodes):
New.
(exploded_graph_annotator::print_enode): Show STATUS_BULK_MERGED.
* exploded-graph.h (enum exploded_node::status): Add
STATUS_BULK_MERGED.
gcc/testsuite/ChangeLog:
* gcc.dg/analyzer/bzip2-arg-parse-1.c: New test.
* gcc.dg/analyzer/loop-n-down-to-1-by-1.c: Remove xfail.
* gcc.dg/analyzer/pr94851-1.c: Add xfail.