[gcc r13-441] Add a return value to intersect and speed it up.

[gcc r13-441] Add a return value to intersect and speed it up.

[Andrew Macleod]

https://gcc.gnu.org/g:1d3d7e88aac0db20a4b59044f9b7cd35e847e8d3

commit r13-441-g1d3d7e88aac0db20a4b59044f9b7cd35e847e8d3
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon May 9 13:20:06 2022 -0400

    Add a return value to intersect and speed it up.
    
    Return true if the intersection of ranges changed the original value.
    Speed up the case when there is no change by calling an efficient
    contains routine.
    
            * value-range.cc (irange::legacy_verbose_intersect): Add return value.
            (irange::irange_contains_p): New.
            (irange::irange_intersect): Add return value.
            * value-range.h (class irange): Adjust prototypes.

Diff:
---
 gcc/value-range.cc | 94 +++++++++++++++++++++++++++++++++++++++++++-----------
 gcc/value-range.h  | 14 ++++----
 2 files changed, 84 insertions(+), 24 deletions(-)

diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 94301b32c37..190d7fb6f22 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -1481,7 +1481,7 @@ irange::legacy_verbose_union_ (const irange *other)
     irange_union (*other);
 }
 
-void
+bool
 irange::legacy_verbose_intersect (const irange *other)
 {
   if (legacy_mode_p ())
@@ -1490,7 +1490,7 @@ irange::legacy_verbose_intersect (const irange *other)
 	{
 	  int_range<1> tmp = *other;
 	  legacy_intersect (this, &tmp);
-	  return;
+	  return true;
 	}
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
@@ -1509,17 +1509,17 @@ irange::legacy_verbose_intersect (const irange *other)
 	  dump_value_range (dump_file, this);
 	  fprintf (dump_file, "\n");
 	}
-      return;
+      return true;
     }
 
   if (other->legacy_mode_p ())
     {
       int_range<2> wider;
       wider = *other;
-      irange_intersect (wider);
+      return irange_intersect (wider);
     }
   else
-    irange_intersect (*other);
+    return irange_intersect (*other);
 }
 
 // union_ for multi-ranges.
@@ -1630,9 +1630,55 @@ irange::irange_union (const irange &r)
     verify_range ();
 }
 
-// intersect for multi-ranges.
+// Return TRUE if THIS fully contains R.  No undefined or varying cases.
 
-void
+bool
+irange::irange_contains_p (const irange &r) const
+{
+  gcc_checking_assert (!undefined_p () && !varying_p ());
+  gcc_checking_assert (!r.undefined_p () && !varying_p ());
+
+  // In order for THIS to fully contain R, all of the pairs within R must
+  // be fully contained by the pairs in this object.
+  signop sign = TYPE_SIGN (TREE_TYPE(m_base[0]));
+  unsigned ri = 0;
+  unsigned i = 0;
+  tree rl = r.m_base[0];
+  tree ru = r.m_base[1];
+  tree l = m_base[0];
+  tree u = m_base[1];
+  while (1)
+    {
+      // If r is contained within this range, move to the next R
+      if (wi::ge_p (wi::to_wide (rl), wi::to_wide (l), sign)
+	  && wi::le_p (wi::to_wide (ru), wi::to_wide (u), sign))
+	{
+	  // This pair is OK, Either done, or bump to the next.
+	  if (++ri >= r.num_pairs ())
+	    return true;
+	  rl = r.m_base[ri * 2];
+	  ru = r.m_base[ri * 2 + 1];
+	  continue;
+	}
+      // Otherwise, check if this's pair occurs before R's.
+      if (wi::lt_p (wi::to_wide (u), wi::to_wide (rl), sign))
+	{
+	  // THere's still at leats one pair of R left.
+	  if (++i >= num_pairs ())
+	    return false;
+	  l = m_base[i * 2];
+	  u = m_base[i * 2 + 1];
+	  continue;
+	}
+      return false;
+    }
+  return false;
+}
+
+
+// Intersect for multi-ranges.  Return TRUE if anything changes.
+
+bool
 irange::irange_intersect (const irange &r)
 {
   gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
@@ -1640,24 +1686,24 @@ irange::irange_intersect (const irange &r)
 		       || range_compatible_p (type (), r.type ()));
 
   if (undefined_p () || r.varying_p ())
-    return;
+    return false;
   if (r.undefined_p ())
     {
       set_undefined ();
-      return;
+      return true;
     }
   if (varying_p ())
     {
       operator= (r);
-      return;
+      return true;
     }
 
   if (r.num_pairs () == 1)
-   {
-     // R cannot be undefined, use more efficent pair routine.
-     intersect (r.lower_bound(), r.upper_bound ());
-     return;
-   }
+    return intersect (r.lower_bound (), r.upper_bound ());
+
+  // If R fully contains this, then intersection will change nothing.
+  if (r.irange_contains_p (*this))
+    return false;
 
   signop sign = TYPE_SIGN (TREE_TYPE(m_base[0]));
   unsigned bld_pair = 0;
@@ -1732,21 +1778,25 @@ irange::irange_intersect (const irange &r)
 
   if (flag_checking)
     verify_range ();
+
+  return true;
 }
 
+
 // Multirange intersect for a specified wide_int [lb, ub] range.
+// Return TRUE if intersect changed anything.
 
-void
+bool
 irange::intersect (const wide_int& lb, const wide_int& ub)
 {
   // Undefined remains undefined.
   if (undefined_p ())
-    return;
+    return false;
 
   if (legacy_mode_p ())
     {
       intersect (int_range<1> (type (), lb, ub));
-      return;
+      return true;
     }
 
   tree range_type = type();
@@ -1755,6 +1805,11 @@ irange::intersect (const wide_int& lb, const wide_int& ub)
   gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb));
   gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub));
 
+  // If this range is fuly contained, then intersection will do nothing.
+  if (wi::ge_p (lower_bound (), lb, sign)
+      && wi::le_p (upper_bound (), ub, sign))
+    return false;
+
   unsigned bld_index = 0;
   unsigned pair_lim = num_pairs ();
   for (unsigned i = 0; i < pair_lim; i++)
@@ -1793,7 +1848,10 @@ irange::intersect (const wide_int& lb, const wide_int& ub)
 
   if (flag_checking)
     verify_range ();
+  return true;
 }
+
+
 // 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 90a395f4d73..419860247fc 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -72,7 +72,7 @@ public:
 
   // In-place operators.
   void union_ (const irange &);
-  void intersect (const irange &);
+  bool intersect (const irange &);
   void invert ();
 
   // Operator overloads.
@@ -97,7 +97,7 @@ public:
   void set (tree);				// DEPRECATED
   bool equal_p (const irange &) const;		// DEPRECATED
   void legacy_verbose_union_ (const class irange *);	// DEPRECATED
-  void legacy_verbose_intersect (const irange *);	// DEPRECATED
+  bool legacy_verbose_intersect (const irange *);	// DEPRECATED
 
 protected:
   irange (tree *, unsigned);
@@ -108,9 +108,10 @@ protected:
 
    // In-place operators.
   void irange_union (const irange &);
-  void irange_intersect (const irange &);
+  bool irange_intersect (const irange &);
   void irange_set (tree, tree);
   void irange_set_anti_range (tree, tree);
+  bool irange_contains_p (const irange &) const;
 
   void normalize_kind ();
 
@@ -134,7 +135,7 @@ private:
   void irange_set_1bit_anti_range (tree, tree);
   bool varying_compatible_p () const;
 
-  void intersect (const wide_int& lb, const wide_int& ub);
+  bool intersect (const wide_int& lb, const wide_int& ub);
   unsigned char m_num_ranges;
   unsigned char m_max_ranges;
   ENUM_BITFIELD(value_range_kind) m_kind : 8;
@@ -553,13 +554,14 @@ irange::union_ (const irange &r)
   dump_flags = m_flags;
 }
 
-inline void
+inline bool
 irange::intersect (const irange &r)
 {
   dump_flags_t m_flags = dump_flags;
   dump_flags &= ~TDF_DETAILS;
-  irange::legacy_verbose_intersect (&r);
+  bool ret = irange::legacy_verbose_intersect (&r);
   dump_flags = m_flags;
+  return ret;
 }
 
 // Set value range VR to a nonzero range of type TYPE.