aboutsummaryrefslogtreecommitdiff
path: root/libbacktrace/internal.h
diff options
context:
space:
mode:
authorDavid Malcolm <dmalcolm@redhat.com>2020-09-10 21:23:38 -0400
committerDavid Malcolm <dmalcolm@redhat.com>2020-09-14 12:28:21 -0400
commit799dd4e10047a4aa772fd69c910c5c6a96c36b9f (patch)
treeff83864f925ce7906eb8df33a30899114a2593d7 /libbacktrace/internal.h
parent00adddd65689d995d8bdf306d0850c852ff0fd25 (diff)
downloadgcc-799dd4e10047a4aa772fd69c910c5c6a96c36b9f.zip
gcc-799dd4e10047a4aa772fd69c910c5c6a96c36b9f.tar.gz
gcc-799dd4e10047a4aa772fd69c910c5c6a96c36b9f.tar.bz2
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.
Diffstat (limited to 'libbacktrace/internal.h')
0 files changed, 0 insertions, 0 deletions