diff mbox series

[1/2] Keep VR_UNDEFINED and VR_VARYING in sync (speeds up evrp by 8.47%).

Message ID 20210426141651.1657784-1-aldyh@redhat.com
State New
Headers show
Series [1/2] Keep VR_UNDEFINED and VR_VARYING in sync (speeds up evrp by 8.47%). | expand

Commit Message

Aldy Hernandez April 26, 2021, 2:16 p.m. UTC 
Currently multi-ranges calculate the undefined and varying bits on the
fly, whereas legacy uses the m_kind field.  Since we will always have
space in the irange class for a kind field, might as well keep it in
sync as ranges are created, thus speeding up lookups.

This patch, along with an upcoming ones for num_pairs(), speeds up EVRP
by 8.47%, VRP proper by 1.84% and overall compilation by 0.24%.

FWIW, since evrp is such a fast pass, and is hard to measure clock-wise,
we've been using callgrind to estimate improvements.  This has coincided
more or less with -ftime-report numbers (albeit having to run -ftime-report
half a dozen times and use the average).

OK?

gcc/ChangeLog:

	* value-range.cc (irange::operator=): Set m_kind.
	(irange::copy_to_legacy): Handle varying and undefined sources
	as a legacy copy since they can be easily copied.
	(irange::irange_set): Set m_kind.
	(irange::irange_set_anti_range): Same.
	(irange::set): Rename normalize_min_max to normalize_kind.
	(irange::verify_range): Adjust for multi-ranges having the
	m_kind field set.
	(irange::irange_union): Set m_kind.
	(irange::irange_intersect): Same.
	(irange::invert): Same.
	* value-range.h (irange::kind): Always return m_kind.
	(irange::varying_p): Rename to...
	(irange::irange_varying_p): ...this.
	(irange::undefined_p): Only look at m_kind.
	(irange::irange): Always set VR_UNDEFINED if applicable.
	(irange::set_undefined): Always set VR_UNDEFINED.
	(irange::set_varying): Always set m_kind to VR_VARYING.
	(irange::normalize_min_max): Rename to...
	(irange::normalize_kind): ...this.
---
 gcc/value-range.cc | 69 +++++++++++++++++++++++++++-------------------
 gcc/value-range.h  | 66 ++++++++++++++++----------------------------
 2 files changed, 63 insertions(+), 72 deletions(-)

Comments

Andrew MacLeod April 26, 2021, 3:03 p.m. UTC | #1 
On 4/26/21 10:16 AM, Aldy Hernandez wrote:
> Currently multi-ranges calculate the undefined and varying bits on the
> fly, whereas legacy uses the m_kind field.  Since we will always have
> space in the irange class for a kind field, might as well keep it in
> sync as ranges are created, thus speeding up lookups.
>
> This patch, along with an upcoming ones for num_pairs(), speeds up EVRP
> by 8.47%, VRP proper by 1.84% and overall compilation by 0.24%.
>
> FWIW, since evrp is such a fast pass, and is hard to measure clock-wise,
> we've been using callgrind to estimate improvements.  This has coincided
> more or less with -ftime-report numbers (albeit having to run -ftime-report
> half a dozen times and use the average).
>
> OK?

Guess we should have done this earlier.. varying_p is very heavily 
used.  I assume this also passes regressions and bootstrap :-)?


>   // Number of sub-ranges in a range.
> @@ -271,17 +263,18 @@ irange::max () const
>   }
>   
>   inline bool
> -irange::varying_p () const
> +irange::irange_varying_p () const
>   {
> -  if (legacy_mode_p ())
> -    return m_kind == VR_VARYING;
> -
>     if (m_num_ranges != 1)
>       return false;
>   
>     tree l = m_base[0];
>     tree u = m_base[1];
>     tree t = TREE_TYPE (l);
> +
> +  if (m_kind == VR_VARYING && t == error_mark_node)
> +    return true;
> +
>     unsigned prec = TYPE_PRECISION (t);
>     signop sign = TYPE_SIGN (t);
>     if (INTEGRAL_TYPE_P (t))
> @@ -291,22 +284,17 @@ irange::varying_p () const
>       return (wi::to_wide (l) == 0
>   	    && wi::to_wide (u) == wi::max_value (prec, sign));
>     return true;
> +}
>   
I find the routine irange_varying_p() name to be a bit confusing... 
since varying_p is also an irange routine..  Maybe call it something 
like  varying_p_compatible ()  or something along those lines?
>   
>   inline void
> -irange::normalize_min_max ()
> -{
> -  gcc_checking_assert (legacy_mode_p ());
> -  gcc_checking_assert (!undefined_p ());
> -  unsigned prec = TYPE_PRECISION (type ());
> -  signop sign = TYPE_SIGN (type ());
> -  if (wi::eq_p (wi::to_wide (min ()), wi::min_value (prec, sign))
> -      && wi::eq_p (wi::to_wide (max ()), wi::max_value (prec, sign)))
> +irange::normalize_kind ()
> +{
> +  if (m_num_ranges == 0)
> +    m_kind = VR_UNDEFINED;
> +  else if (irange_varying_p ())
>       {
>         if (m_kind == VR_RANGE)
> -	set_varying (type ());
> +	m_kind = VR_VARYING;
>         else if (m_kind == VR_ANTI_RANGE)
>   	set_undefined ();
>         else

I see that normalize_kind will turn a varying ANTI_RANGE to UNDEFINED. 
If you go into irange::set (tree min, tree max, value_range_kind kind)  
I see:

// Anti-ranges that can be represented as ranges should be so.
   if (kind == VR_ANTI_RANGE)
     {
       /* For -fstrict-enums we may receive out-of-range ranges so consider
          values < -INF and values > INF as -INF/INF as well.  */
       bool is_min = vrp_val_is_min (min);
       bool is_max = vrp_val_is_max (max);
       tree type = TREE_TYPE (min);

       if (is_min && is_max)
         {
           /* We cannot deal with empty ranges, drop to varying.
              ???  This could be VR_UNDEFINED instead.  */
           set_varying (type);
           return;
         }

should that be set_undefined?  or is that a different can of worms 
related to strict-enum?


Assuming bootstrap and regression tests, OK

Andrew
Aldy Hernandez April 26, 2021, 4:23 p.m. UTC | #2 
On 4/26/21 5:03 PM, Andrew MacLeod wrote:
> On 4/26/21 10:16 AM, Aldy Hernandez wrote:
>> Currently multi-ranges calculate the undefined and varying bits on the
>> fly, whereas legacy uses the m_kind field.  Since we will always have
>> space in the irange class for a kind field, might as well keep it in
>> sync as ranges are created, thus speeding up lookups.
>>
>> This patch, along with an upcoming ones for num_pairs(), speeds up EVRP
>> by 8.47%, VRP proper by 1.84% and overall compilation by 0.24%.
>>
>> FWIW, since evrp is such a fast pass, and is hard to measure clock-wise,
>> we've been using callgrind to estimate improvements.  This has coincided
>> more or less with -ftime-report numbers (albeit having to run 
>> -ftime-report
>> half a dozen times and use the average).
>>
>> OK?
> 
> Guess we should have done this earlier.. varying_p is very heavily 
> used.  I assume this also passes regressions and bootstrap :-)?
> 
> 
>>   // Number of sub-ranges in a range.
>> @@ -271,17 +263,18 @@ irange::max () const
>>   }
>>   inline bool
>> -irange::varying_p () const
>> +irange::irange_varying_p () const
>>   {
>> -  if (legacy_mode_p ())
>> -    return m_kind == VR_VARYING;
>> -
>>     if (m_num_ranges != 1)
>>       return false;
>>     tree l = m_base[0];
>>     tree u = m_base[1];
>>     tree t = TREE_TYPE (l);
>> +
>> +  if (m_kind == VR_VARYING && t == error_mark_node)
>> +    return true;
>> +
>>     unsigned prec = TYPE_PRECISION (t);
>>     signop sign = TYPE_SIGN (t);
>>     if (INTEGRAL_TYPE_P (t))
>> @@ -291,22 +284,17 @@ irange::varying_p () const
>>       return (wi::to_wide (l) == 0
>>           && wi::to_wide (u) == wi::max_value (prec, sign));
>>     return true;
>> +}
> I find the routine irange_varying_p() name to be a bit confusing... 
> since varying_p is also an irange routine..  Maybe call it something 
> like  varying_p_compatible ()  or something along those lines?

I've named it varying_compatible_p.

>>   inline void
>> -irange::normalize_min_max ()
>> -{
>> -  gcc_checking_assert (legacy_mode_p ());
>> -  gcc_checking_assert (!undefined_p ());
>> -  unsigned prec = TYPE_PRECISION (type ());
>> -  signop sign = TYPE_SIGN (type ());
>> -  if (wi::eq_p (wi::to_wide (min ()), wi::min_value (prec, sign))
>> -      && wi::eq_p (wi::to_wide (max ()), wi::max_value (prec, sign)))
>> +irange::normalize_kind ()
>> +{
>> +  if (m_num_ranges == 0)
>> +    m_kind = VR_UNDEFINED;
>> +  else if (irange_varying_p ())
>>       {
>>         if (m_kind == VR_RANGE)
>> -    set_varying (type ());
>> +    m_kind = VR_VARYING;
>>         else if (m_kind == VR_ANTI_RANGE)
>>       set_undefined ();
>>         else
> 
> I see that normalize_kind will turn a varying ANTI_RANGE to UNDEFINED. 
> If you go into irange::set (tree min, tree max, value_range_kind kind) I 
> see:
> 
> // Anti-ranges that can be represented as ranges should be so.
>    if (kind == VR_ANTI_RANGE)
>      {
>        /* For -fstrict-enums we may receive out-of-range ranges so consider
>           values < -INF and values > INF as -INF/INF as well.  */
>        bool is_min = vrp_val_is_min (min);
>        bool is_max = vrp_val_is_max (max);
>        tree type = TREE_TYPE (min);
> 
>        if (is_min && is_max)
>          {
>            /* We cannot deal with empty ranges, drop to varying.
>               ???  This could be VR_UNDEFINED instead.  */
>            set_varying (type);
>            return;
>          }
> 
> should that be set_undefined?  or is that a different can of worms 
> related to strict-enum?

This is a very old comment that predates me.  Let's address this as a 
follow-up.

> 
> 
> Assuming bootstrap and regression tests, OK

Oh, all my patches are tested on x86-64 Linux with no regressions.

Pushed.

Aldy
diff mbox series

Patch

diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index f5ef4808530..369eeabd7d5 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -59,6 +59,7 @@  irange::operator= (const irange &src)
     m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
 
   m_num_ranges = lim;
+  m_kind = src.m_kind;
   return *this;
 }
 
@@ -106,8 +107,8 @@  void
 irange::copy_to_legacy (const irange &src)
 {
   gcc_checking_assert (legacy_mode_p ());
-  // Copy legacy to legacy.
-  if (src.legacy_mode_p ())
+  // Handle legacy to legacy and other things that are easy to copy.
+  if (src.legacy_mode_p () || src.varying_p () || src.undefined_p ())
     {
       m_num_ranges = src.m_num_ranges;
       m_base[0] = src.m_base[0];
@@ -116,11 +117,7 @@  irange::copy_to_legacy (const irange &src)
       return;
     }
   // Copy multi-range to legacy.
-  if (src.undefined_p ())
-    set_undefined ();
-  else if (src.varying_p ())
-    set_varying (src.type ());
-  else if (src.maybe_anti_range ())
+  if (src.maybe_anti_range ())
     {
       int_range<3> r (src);
       r.invert ();
@@ -180,6 +177,9 @@  irange::irange_set (tree min, tree max)
   m_base[0] = min;
   m_base[1] = max;
   m_num_ranges = 1;
+  m_kind = VR_RANGE;
+  normalize_kind ();
+
   if (flag_checking)
     verify_range ();
 }
@@ -247,6 +247,10 @@  irange::irange_set_anti_range (tree min, tree max)
       m_base[m_num_ranges * 2 + 1] = type_range.tree_upper_bound (0);
       ++m_num_ranges;
     }
+
+  m_kind = VR_RANGE;
+  normalize_kind ();
+
   if (flag_checking)
     verify_range ();
 }
@@ -353,7 +357,7 @@  irange::set (tree min, tree max, value_range_kind kind)
   m_base[0] = min;
   m_base[1] = max;
   m_num_ranges = 1;
-  normalize_min_max ();
+  normalize_kind ();
   if (flag_checking)
     verify_range ();
 }
@@ -363,9 +367,22 @@  irange::set (tree min, tree max, value_range_kind kind)
 void
 irange::verify_range ()
 {
+  if (m_kind == VR_UNDEFINED)
+    {
+      gcc_assert (m_num_ranges == 0);
+      return;
+    }
+  gcc_assert (m_num_ranges != 0);
+
+  if (m_kind == VR_VARYING)
+    {
+      gcc_assert (m_num_ranges == 1);
+      gcc_assert (irange_varying_p ());
+      return;
+    }
   if (!legacy_mode_p ())
     {
-      gcc_checking_assert (m_kind == VR_RANGE);
+      gcc_assert (!irange_varying_p ());
       for (unsigned i = 0; i < m_num_ranges; ++i)
 	{
 	  tree lb = tree_lower_bound (i);
@@ -375,28 +392,11 @@  irange::verify_range ()
 	}
       return;
     }
-
-  switch (m_kind)
+  if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
     {
-    case VR_UNDEFINED:
-      gcc_assert (m_num_ranges == 0);
-      break;
-
-    case VR_VARYING:
       gcc_assert (m_num_ranges == 1);
-      break;
-
-    case VR_ANTI_RANGE:
-    case VR_RANGE:
-      {
-	gcc_assert (m_num_ranges == 1);
-	int cmp = compare_values (tree_lower_bound (0), tree_upper_bound (0));
-	gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
-	return;
-      }
-
-    default:
-      gcc_unreachable ();
+      int cmp = compare_values (tree_lower_bound (0), tree_upper_bound (0));
+      gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
     }
 }
 
@@ -1667,6 +1667,9 @@  irange::irange_union (const irange &r)
     m_base[j] = res [j];
   m_num_ranges = i / 2;
 
+  m_kind = VR_RANGE;
+  normalize_kind ();
+
   if (flag_checking)
     verify_range ();
 }
@@ -1758,6 +1761,10 @@  irange::irange_intersect (const irange &r)
   // At the exit of this loop, it is one of 2 things:
   // ran out of r1, or r2, but either means we are done.
   m_num_ranges = bld_pair;
+
+  m_kind = VR_RANGE;
+  normalize_kind ();
+
   if (flag_checking)
     verify_range ();
 }
@@ -1890,6 +1897,10 @@  irange::invert ()
     }
   m_num_ranges = nitems / 2;
 
+  // We disallow undefined or varying coming in, so the result can
+  // only be a VR_RANGE.
+  gcc_checking_assert (m_kind == VR_RANGE);
+
   if (flag_checking)
     verify_range ();
 }
diff --git a/gcc/value-range.h b/gcc/value-range.h
index bb27e706207..bfba1a3469e 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -111,7 +111,7 @@  protected:
   void irange_set (tree, tree);
   void irange_set_anti_range (tree, tree);
 
-  void normalize_min_max ();
+  void normalize_kind ();
 
   bool legacy_mode_p () const;
   bool legacy_equal_p (const irange &) const;
@@ -128,6 +128,7 @@  protected:
 
 private:
   void irange_set_1bit_anti_range (tree, tree);
+  bool irange_varying_p () const;
 
   unsigned char m_num_ranges;
   unsigned char m_max_ranges;
@@ -198,16 +199,7 @@  extern bool vrp_operand_equal_p (const_tree, const_tree);
 inline value_range_kind
 irange::kind () const
 {
-  if (legacy_mode_p ())
-    return m_kind;
-
-  if (undefined_p ())
-    return VR_UNDEFINED;
-
-  if (varying_p ())
-    return VR_VARYING;
-
-  return VR_RANGE;
+  return m_kind;
 }
 
 // Number of sub-ranges in a range.
@@ -271,17 +263,18 @@  irange::max () const
 }
 
 inline bool
-irange::varying_p () const
+irange::irange_varying_p () const
 {
-  if (legacy_mode_p ())
-    return m_kind == VR_VARYING;
-
   if (m_num_ranges != 1)
     return false;
 
   tree l = m_base[0];
   tree u = m_base[1];
   tree t = TREE_TYPE (l);
+
+  if (m_kind == VR_VARYING && t == error_mark_node)
+    return true;
+
   unsigned prec = TYPE_PRECISION (t);
   signop sign = TYPE_SIGN (t);
   if (INTEGRAL_TYPE_P (t))
@@ -291,22 +284,17 @@  irange::varying_p () const
     return (wi::to_wide (l) == 0
 	    && wi::to_wide (u) == wi::max_value (prec, sign));
   return true;
+}
 
+inline bool
+irange::varying_p () const
+{
+  return m_kind == VR_VARYING;
 }
 
 inline bool
 irange::undefined_p () const
 {
-  if (!legacy_mode_p ())
-    return m_num_ranges == 0;
-
-  if (CHECKING_P && legacy_mode_p ())
-    {
-      if (m_kind == VR_UNDEFINED)
-	gcc_checking_assert (m_num_ranges == 0);
-      else
-	gcc_checking_assert (m_num_ranges != 0);
-    }
   return m_kind == VR_UNDEFINED;
 }
 
@@ -389,10 +377,7 @@  irange::irange (tree *base, unsigned nranges)
   m_base = base;
   m_num_ranges = 0;
   m_max_ranges = nranges;
-  if (legacy_mode_p ())
-    m_kind = VR_UNDEFINED;
-  else
-    m_kind = VR_RANGE;
+  m_kind = VR_UNDEFINED;
 }
 
 // Constructors for int_range<>.
@@ -459,18 +444,16 @@  irange::set (tree val)
 inline void
 irange::set_undefined ()
 {
+  m_kind = VR_UNDEFINED;
   m_num_ranges = 0;
-  if (legacy_mode_p ())
-    m_kind = VR_UNDEFINED;
 }
 
 inline void
 irange::set_varying (tree type)
 {
-  if (legacy_mode_p ())
-    m_kind = VR_VARYING;
-
+  m_kind = VR_VARYING;
   m_num_ranges = 1;
+
   if (INTEGRAL_TYPE_P (type))
     {
       wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
@@ -574,17 +557,14 @@  irange::set_zero (tree type)
 // Normalize a range to VARYING or UNDEFINED if possible.
 
 inline void
-irange::normalize_min_max ()
-{
-  gcc_checking_assert (legacy_mode_p ());
-  gcc_checking_assert (!undefined_p ());
-  unsigned prec = TYPE_PRECISION (type ());
-  signop sign = TYPE_SIGN (type ());
-  if (wi::eq_p (wi::to_wide (min ()), wi::min_value (prec, sign))
-      && wi::eq_p (wi::to_wide (max ()), wi::max_value (prec, sign)))
+irange::normalize_kind ()
+{
+  if (m_num_ranges == 0)
+    m_kind = VR_UNDEFINED;
+  else if (irange_varying_p ())
     {
       if (m_kind == VR_RANGE)
-	set_varying (type ());
+	m_kind = VR_VARYING;
       else if (m_kind == VR_ANTI_RANGE)
 	set_undefined ();
       else