From ad451b020a24fe7111e668f8c41a3ba648104569 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Mon, 4 Oct 2021 15:30:44 -0400
Subject: [PATCH 4/4] Add range intersect with 2 wide-ints.
Add a more efficent intersect using a lower/upper bound single pair of
wide_ints.
* gimple-range-cache.cc (non_null_ref::adjust_range): Call new
intersect routine.
* gimple-range-fold.cc (adjust_pointer_diff_expr): Ditto.
(adjust_imagpart_expr): Ditto.
* value-range.cc (irange::irange_intersect): Call new routine if
RHS is a single pair.
(irange::intersect): New wide_int version.
* value-range.h (class irange): New prototype.
---
gcc/gimple-range-cache.cc | 6 ++--
gcc/gimple-range-fold.cc | 14 +++-----
gcc/value-range.cc | 69 +++++++++++++++++++++++++++++++++++++++
gcc/value-range.h | 1 +
4 files changed, 78 insertions(+), 12 deletions(-)
@@ -105,9 +105,9 @@ non_null_ref::adjust_range (irange &r, tree name, basic_block bb,
// Check if pointers have any non-null dereferences.
if (non_null_deref_p (name, bb, search_dom))
{
- int_range<2> nz;
- nz.set_nonzero (TREE_TYPE (name));
- r.intersect (nz);
+ // Remove zero from the range.
+ unsigned prec = TYPE_PRECISION (TREE_TYPE (name));
+ r.intersect (wi::one (prec), wi::max_value (prec, UNSIGNED));
return true;
}
return false;
@@ -360,12 +360,9 @@ adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt)
&& integer_zerop (gimple_call_arg (call, 1)))
{
tree max = vrp_val_max (ptrdiff_type_node);
- wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
- tree expr_type = gimple_range_type (diff_stmt);
- tree range_min = build_zero_cst (expr_type);
- tree range_max = wide_int_to_tree (expr_type, wmax - 1);
- int_range<2> r (range_min, range_max);
- res.intersect (r);
+ unsigned prec = TYPE_PRECISION (TREE_TYPE (max));
+ wide_int wmaxm1 = wi::to_wide (max, prec) - 1;
+ res.intersect (wi::zero (prec), wmaxm1);
}
}
@@ -405,9 +402,8 @@ adjust_imagpart_expr (irange &res, const gimple *stmt)
tree cst = gimple_assign_rhs1 (def_stmt);
if (TREE_CODE (cst) == COMPLEX_CST)
{
- tree imag = TREE_IMAGPART (cst);
- int_range<2> tmp (imag, imag);
- res.intersect (tmp);
+ wide_int imag = wi::to_wide (TREE_IMAGPART (cst));
+ res.intersect (imag, imag);
}
}
}
@@ -1648,6 +1648,8 @@ void
irange::irange_intersect (const irange &r)
{
gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
+ gcc_checking_assert (undefined_p () || r.undefined_p ()
+ || range_compatible_p (type (), r.type ()));
if (undefined_p () || r.varying_p ())
return;
@@ -1662,6 +1664,13 @@ irange::irange_intersect (const irange &r)
return;
}
+ if (r.num_pairs () == 1)
+ {
+ // R cannot be undefined, use more efficent pair routine.
+ intersect (r.lower_bound(), r.upper_bound ());
+ return;
+ }
+
signop sign = TYPE_SIGN (TREE_TYPE(m_base[0]));
unsigned bld_pair = 0;
unsigned bld_lim = m_max_ranges;
@@ -1737,6 +1746,66 @@ irange::irange_intersect (const irange &r)
verify_range ();
}
+// Multirange intersect for a specified wide_int [lb, ub] range.
+
+void
+irange::intersect (const wide_int& lb, const wide_int& ub)
+{
+ // Undefined remains undefined.
+ if (undefined_p ())
+ return;
+
+ if (legacy_mode_p ())
+ {
+ intersect (int_range<1> (type (), lb, ub));
+ return;
+ }
+
+ tree range_type = type();
+ signop sign = TYPE_SIGN (range_type);
+
+ gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb));
+ gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub));
+
+ unsigned bld_index = 0;
+ unsigned pair_lim = num_pairs ();
+ for (unsigned i = 0; i < pair_lim; i++)
+ {
+ tree pairl = m_base[i * 2];
+ tree pairu = m_base[i * 2 + 1];
+ // Once UB is less than a pairs lower bound, we're done.
+ if (wi::lt_p (ub, wi::to_wide (pairl), sign))
+ break;
+ // if LB is greater than this pairs upper, this pair is excluded.
+ if (wi::lt_p (wi::to_wide (pairu), lb, sign))
+ continue;
+
+ // Must be some overlap. Find the highest of the lower bounds,
+ // and set it
+ if (wi::gt_p (lb, wi::to_wide (pairl), sign))
+ m_base[bld_index * 2] = wide_int_to_tree (range_type, lb);
+ else
+ m_base[bld_index * 2] = pairl;
+
+ // ...and choose the lower of the upper bounds and if the base pair
+ // has the lower upper bound, need to check next pair too.
+ if (wi::lt_p (ub, wi::to_wide (pairu), sign))
+ {
+ m_base[bld_index++ * 2 + 1] = wide_int_to_tree (range_type, ub);
+ break;
+ }
+ else
+ m_base[bld_index++ * 2 + 1] = pairu;
+ }
+
+ m_num_ranges = bld_index;
+
+ m_kind = VR_RANGE;
+ normalize_kind ();
+
+ if (flag_checking)
+ verify_range ();
+}
// Signed 1-bits are strange. You can't subtract 1, because you can't
// represent the number 1. This works around that for the invert routine.
@@ -73,6 +73,7 @@ public:
// In-place operators.
void union_ (const irange &);
void intersect (const irange &);
+ void intersect (const wide_int& lb, const wide_int& ub);
void invert ();
// Operator overloads.
--
2.17.2