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 <dmalc...@gcc.gnu.org>: https://gcc.gnu.org/g:799dd4e10047a4aa772fd69c910c5c6a96c36b9f commit r11-3190-g799dd4e10047a4aa772fd69c910c5c6a96c36b9f Author: David Malcolm <dmalc...@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.