analyzer: fix constraint explosion on many-cased switch [PR96653]
authorDavid Malcolm <dmalcolm@redhat.com>
Fri, 11 Sep 2020 01:23:38 +0000 (21:23 -0400)
committerDavid Malcolm <dmalcolm@redhat.com>
Mon, 14 Sep 2020 16:28:21 +0000 (12:28 -0400)
commit799dd4e10047a4aa772fd69c910c5c6a96c36b9f
treeff83864f925ce7906eb8df33a30899114a2593d7
parent00adddd65689d995d8bdf306d0850c852ff0fd25
analyzer: fix constraint explosion on many-cased switch [PR96653]

PR analyzer/96653 reports a CPU-time and memory explosion in -fanalyzer
seen in Linux 5.9-rc1:drivers/media/v4l2-core/v4l2-ctrls.c on a switch
statement with many cases.

The issue is some old code in constraint_manager::get_or_add_equiv_class
for ensuring that comparisons between equivalence classes containing
constants work correctly.  The old code added constraints for every
pair of ECs containing constants, leading to O(N^2) constraints (for
N constants).  Given that get_or_add_equiv_class also involves O(N)
comparisons, this led to at least O(N^3) CPU time, and O(N^2) memory
consumption when handling the "default" case, where N is the number of
other cases in the switch statement.

The state rewrite of r11-2694-g808f4dfeb3a95f50f15e71148e5c1067f90a126d
added checking for comparisons between constants, making these explicit
constraints redundant, but failed to remove the code mentioned above.

This patch removes it, fixing the blow-up of constraints in the default
case.

gcc/analyzer/ChangeLog:
PR analyzer/96653
* constraint-manager.cc
(constraint_manager::get_or_add_equiv_class): Don't accumulate
transitive closure of all constraints on constants.

gcc/testsuite/ChangeLog:
PR analyzer/96653
* gcc.dg/analyzer/pr96653.c: New test.
gcc/analyzer/constraint-manager.cc
gcc/testsuite/gcc.dg/analyzer/pr96653.c [new file with mode: 0644]