diff options
author | David Malcolm <dmalcolm@redhat.com> | 2020-09-10 21:23:38 -0400 |
---|---|---|
committer | David Malcolm <dmalcolm@redhat.com> | 2020-09-14 12:28:21 -0400 |
commit | 799dd4e10047a4aa772fd69c910c5c6a96c36b9f (patch) | |
tree | ff83864f925ce7906eb8df33a30899114a2593d7 /gcc/analyzer/constraint-manager.cc | |
parent | 00adddd65689d995d8bdf306d0850c852ff0fd25 (diff) | |
download | gcc-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 'gcc/analyzer/constraint-manager.cc')
-rw-r--r-- | gcc/analyzer/constraint-manager.cc | 33 |
1 files changed, 0 insertions, 33 deletions
diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc index 2f7a653..c10b770 100644 --- a/gcc/analyzer/constraint-manager.cc +++ b/gcc/analyzer/constraint-manager.cc @@ -1160,39 +1160,6 @@ constraint_manager::get_or_add_equiv_class (const svalue *sval) equiv_class_id new_id (m_equiv_classes.length () - 1); - if (sval->maybe_get_constant ()) - { - /* If we have a new EC for a constant, add constraints comparing this - to other constants we may have (so that we accumulate the transitive - closure of all constraints on constants as the constants are - added). */ - for (equiv_class_id other_id (0); other_id.m_idx < new_id.m_idx; - other_id.m_idx++) - { - const equiv_class &other_ec = other_id.get_obj (*this); - if (other_ec.m_constant - && types_compatible_p (TREE_TYPE (new_ec->m_constant), - TREE_TYPE (other_ec.m_constant))) - { - /* If we have two ECs, both with constants, the constants must be - non-equal (or they would be in the same EC). - Determine the direction of the inequality, and record that - fact. */ - tree lt - = fold_binary (LT_EXPR, boolean_type_node, - new_ec->m_constant, other_ec.m_constant); - if (lt == boolean_true_node) - add_constraint_internal (new_id, CONSTRAINT_LT, other_id); - else if (lt == boolean_false_node) - add_constraint_internal (other_id, CONSTRAINT_LT, new_id); - /* Refresh new_id, in case ECs were merged. SVAL should always - be present by now, so this should never lead to a - recursion. */ - new_id = get_or_add_equiv_class (sval); - } - } - } - return new_id; } |