aboutsummaryrefslogtreecommitdiff
path: root/gcc/analyzer/constraint-manager.cc
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 /gcc/analyzer/constraint-manager.cc
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 'gcc/analyzer/constraint-manager.cc')
-rw-r--r--gcc/analyzer/constraint-manager.cc33
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;
}