https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96653
--- Comment #2 from CVS Commits ---
The master branch has been updated by David Malcolm :
https://gcc.gnu.org/g:799dd4e10047a4aa772fd69c910c5c6a96c36b9f
commit r11-3190-g799dd4e10047a4aa772fd69c910c5c6a96c36b9f
Author: David Malcolm
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.
