[gcc r12-4212] Add range intersect with 2 wide-ints.

[gcc r12-4212] Add range intersect with 2 wide-ints.

[Andrew Macleod]

https://gcc.gnu.org/g:ad451b020a24fe7111e668f8c41a3ba648104569

commit r12-4212-gad451b020a24fe7111e668f8c41a3ba648104569
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Oct 4 15:30:44 2021 -0400

    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.

Diff:
---
 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(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 91dd5a5c087..7d994798e52 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -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;
diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index bb09b751a4e..ed2fbe121cf 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -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);
 	}
     }
 }
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index f113fd7c905..147c4b04c1d 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -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.
 
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 39e8f3bcdee..ff6c0a6176d 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -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.