[Bug analyzer/96653] Compile time and memory hog w/ -O1 -fanalyzer

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96653

--- Comment #2 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by David Malcolm <dmalcolm@gcc.gnu.org>:

https://gcc.gnu.org/g:799dd4e10047a4aa772fd69c910c5c6a96c36b9f

commit r11-3190-g799dd4e10047a4aa772fd69c910c5c6a96c36b9f
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Thu Sep 10 21:23:38 2020 -0400

    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.