analyzer: bulk merger/processing of runs of nodes at CFG join points
authorDavid Malcolm <dmalcolm@redhat.com>
Tue, 18 Aug 2020 22:52:17 +0000 (18:52 -0400)
committerDavid Malcolm <dmalcolm@redhat.com>
Wed, 16 Sep 2020 23:01:58 +0000 (19:01 -0400)
commitb28491dc2d79763ecbff4f0b9f1f3e48a443be1d
treee65d9b4badac7ef5e1bfffd03dc6510c6594134b
parentb9b5fc0c2175b34131d9fd0805b1b307f754f4f0
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.
gcc/analyzer/engine.cc
gcc/analyzer/exploded-graph.h
gcc/testsuite/gcc.dg/analyzer/bzip2-arg-parse-1.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/analyzer/loop-n-down-to-1-by-1.c
gcc/testsuite/gcc.dg/analyzer/pr94851-1.c