analyzer: fix state explosions due to SCC bug
authorDavid Malcolm <dmalcolm@redhat.com>
Wed, 16 Sep 2020 13:22:06 +0000 (09:22 -0400)
committerDavid Malcolm <dmalcolm@redhat.com>
Wed, 16 Sep 2020 23:04:16 +0000 (19:04 -0400)
commitfd111c419d146ee47c7df9a36a535e8d843d4802
treeb6429bd5ef52b9590f162bbcbb64fcc76b35a6e8
parentd2c4d5199cf277becc1f377536973815d1c9519c
analyzer: fix state explosions due to SCC bug

Debugging the state explosion of the very large switch statement in
gcc.dg/analyzer/pr96653.c showed that the worklist was failing to
order the exploded nodes correctly; the in-edges at the join point
after the switch were not getting processed together, but were instead
being rocessed in smaller batches, bloating the exploded graph until the
per-point limit was reached.

The root cause turned out to be a bug in creating the strongly-connected
components for the supergraph: the code was considering interprocedural
edges as well as intraprocedural edges, leading to unpredictable
misorderings of the SCC and worklist, leading to bloating of the
exploded graph.

This patch fixes the SCC creation so it only considers intraprocedural
edges within the supergraph.  It also tweaks worklist::key_t::cmp to
give higher precedence to call_string over differences within a
supernode, since enodes with different call_strings can't be merges.
In practise, none of my test cases were affected by this latter change,
though it seems to be the right thing to do.

With this patch, the very large switch statement in
gcc.dg/analyzer/pr96653.c is handled in a single call to
exploded_graph::maybe_process_run_of_before_supernode_enodes:
   merged 358 in-enodes into 2 out-enode(s) at SN: 402
and that testcase no longer hits the per-program-point limits.

gcc/analyzer/ChangeLog:
* engine.cc (strongly_connected_components::strong_connect): Only
consider intraprocedural edges when creating SCCs.
(worklist::key_t::cmp): Add comment.  Treat call_string
differences as more important than differences of program_point
within a supernode.

gcc/testsuite/ChangeLog:
PR analyzer/96653
* gcc.dg/analyzer/loop-0-up-to-n-by-1-with-iter-obj.c: Update
expected number of exploded nodes.
* gcc.dg/analyzer/malloc-vs-local-1a.c: Update expected number
of exploded nodes.
* gcc.dg/analyzer/pr96653.c: Remove -Wno-analyzer-too-complex.
gcc/analyzer/engine.cc
gcc/testsuite/gcc.dg/analyzer/loop-0-up-to-n-by-1-with-iter-obj.c
gcc/testsuite/gcc.dg/analyzer/malloc-vs-local-1a.c
gcc/testsuite/gcc.dg/analyzer/pr96653.c