[PUSHED] Abstract out non_null adjustments in ranger.

[PUSHED] Abstract out non_null adjustments in ranger.

[Aldy Hernandez]

There are 4 exact copies of the non-null range adjusting code in the
ranger.  This patch abstracts the functionality into a separate method.

As a follow-up I would like to remove the varying_p check, since I have
seen incoming ranges such as [0, 0xff....ef] which are not varying, but
are not-null.  Removing the varying restriction catches those.

Tested on x86-64 Linux.

Pushed to trunk.

p.s. Andrew, what are your thoughts on removing the varying_p() check as
a follow-up?

gcc/ChangeLog:

	* gimple-range-cache.cc (non_null_ref::adjust_range): New.
	(ranger_cache::range_of_def): Call adjust_range.
	(ranger_cache::entry_range): Same.
	* gimple-range-cache.h (non_null_ref::adjust_range): New.
	* gimple-range.cc (gimple_ranger::range_of_expr): Call
	adjust_range.
	(gimple_ranger::range_on_entry): Same.
---
 gcc/gimple-range-cache.cc | 35 ++++++++++++++++++++++++++---------
 gcc/gimple-range-cache.h  |  2 ++
 gcc/gimple-range.cc       |  8 ++------
 3 files changed, 30 insertions(+), 15 deletions(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 98ecdbbd68e..23597ade802 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -81,6 +81,29 @@ non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom)
   return false;
 }
 
+// If NAME has a non-null dereference in block BB, adjust R with the
+// non-zero information from non_null_deref_p, and return TRUE.  If
+// SEARCH_DOM is true, non_null_deref_p should search the dominator tree.
+
+bool
+non_null_ref::adjust_range (irange &r, tree name, basic_block bb,
+			    bool search_dom)
+{
+  // Check if pointers have any non-null dereferences.  Non-call
+  // exceptions mean we could throw in the middle of the block, so just
+  // punt for now on those.
+  if (!cfun->can_throw_non_call_exceptions
+      && r.varying_p ()
+      && non_null_deref_p (name, bb, search_dom))
+    {
+      int_range<2> nz;
+      nz.set_nonzero (TREE_TYPE (name));
+      r.intersect (nz);
+      return true;
+    }
+  return false;
+}
+
 // Allocate an populate the bitmap for NAME.  An ON bit for a block
 // index indicates there is a non-null reference in that block.  In
 // order to populate the bitmap, a quick run of all the immediate uses
@@ -857,9 +880,8 @@ ranger_cache::range_of_def (irange &r, tree name, basic_block bb)
 	r = gimple_range_global (name);
     }
 
-  if (bb && r.varying_p () && m_non_null.non_null_deref_p (name, bb, false) &&
-      !cfun->can_throw_non_call_exceptions)
-    r = range_nonzero (TREE_TYPE (name));
+  if (bb)
+    m_non_null.adjust_range (r, name, bb, false);
 }
 
 // Get the range of NAME as it occurs on entry to block BB.
@@ -878,12 +900,7 @@ ranger_cache::entry_range (irange &r, tree name, basic_block bb)
   if (!m_on_entry.get_bb_range (r, name, bb))
     range_of_def (r, name);
 
-  // Check if pointers have any non-null dereferences.  Non-call
-  // exceptions mean we could throw in the middle of the block, so just
-  // punt for now on those.
-  if (r.varying_p () && m_non_null.non_null_deref_p (name, bb, false) &&
-      !cfun->can_throw_non_call_exceptions)
-    r = range_nonzero (TREE_TYPE (name));
+  m_non_null.adjust_range (r, name, bb, false);
 }
 
 // Get the range of NAME as it occurs on exit from block BB.
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index ecf63dc01b3..f842e9c092a 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -34,6 +34,8 @@ public:
   non_null_ref ();
   ~non_null_ref ();
   bool non_null_deref_p (tree name, basic_block bb, bool search_dom = true);
+  bool adjust_range (irange &r, tree name, basic_block bb,
+		     bool search_dom = true);
 private:
   vec <bitmap> m_nn;
   void process_name (tree name);
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 1851339c528..b210787d0b7 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -69,9 +69,7 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
   if (def_stmt && gimple_bb (def_stmt) == bb)
     {
       range_of_stmt (r, def_stmt, expr);
-      if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
-	  m_cache.m_non_null.non_null_deref_p (expr, bb))
-	r = range_nonzero (TREE_TYPE (expr));
+      m_cache.m_non_null.adjust_range (r, expr, bb, true);
     }
   else
     // Otherwise OP comes from outside this block, use range on entry.
@@ -95,9 +93,7 @@ gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name)
   if (m_cache.block_range (entry_range, bb, name))
     r.intersect (entry_range);
 
-  if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
-      m_cache.m_non_null.non_null_deref_p (name, bb))
-    r = range_nonzero (TREE_TYPE (name));
+  m_cache.m_non_null.adjust_range (r, name, bb, true);
 }
 
 // Calculate the range for NAME at the end of block BB and return it in R.
-- 
2.31.1

Re: [PUSHED] Abstract out non_null adjustments in ranger.

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 5849 bytes --]

As I mentioned when I pushed the patch in this thread, I have run into
cases where a pointer has a non-varying range, but it includes 0.  The
varying check causes no further refinements to be done.  The previous
cases I had seen were in follow-up threader work, so I was delaying
pushing this until then.  But I'm now going through VRP cases that
evrp is missing, and this is one of the main culprits.

I will push this once tests are done.  If for some reason, varying
restrictions are needed, we can always adjust the callers to
adjust_range.

Aldy

On Thu, Jul 15, 2021 at 2:21 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> There are 4 exact copies of the non-null range adjusting code in the
> ranger.  This patch abstracts the functionality into a separate method.
>
> As a follow-up I would like to remove the varying_p check, since I have
> seen incoming ranges such as [0, 0xff....ef] which are not varying, but
> are not-null.  Removing the varying restriction catches those.
>
> Tested on x86-64 Linux.
>
> Pushed to trunk.
>
> p.s. Andrew, what are your thoughts on removing the varying_p() check as
> a follow-up?
>
> gcc/ChangeLog:
>
>         * gimple-range-cache.cc (non_null_ref::adjust_range): New.
>         (ranger_cache::range_of_def): Call adjust_range.
>         (ranger_cache::entry_range): Same.
>         * gimple-range-cache.h (non_null_ref::adjust_range): New.
>         * gimple-range.cc (gimple_ranger::range_of_expr): Call
>         adjust_range.
>         (gimple_ranger::range_on_entry): Same.
> ---
>  gcc/gimple-range-cache.cc | 35 ++++++++++++++++++++++++++---------
>  gcc/gimple-range-cache.h  |  2 ++
>  gcc/gimple-range.cc       |  8 ++------
>  3 files changed, 30 insertions(+), 15 deletions(-)
>
> diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
> index 98ecdbbd68e..23597ade802 100644
> --- a/gcc/gimple-range-cache.cc
> +++ b/gcc/gimple-range-cache.cc
> @@ -81,6 +81,29 @@ non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom)
>    return false;
>  }
>
> +// If NAME has a non-null dereference in block BB, adjust R with the
> +// non-zero information from non_null_deref_p, and return TRUE.  If
> +// SEARCH_DOM is true, non_null_deref_p should search the dominator tree.
> +
> +bool
> +non_null_ref::adjust_range (irange &r, tree name, basic_block bb,
> +                           bool search_dom)
> +{
> +  // Check if pointers have any non-null dereferences.  Non-call
> +  // exceptions mean we could throw in the middle of the block, so just
> +  // punt for now on those.
> +  if (!cfun->can_throw_non_call_exceptions
> +      && r.varying_p ()
> +      && non_null_deref_p (name, bb, search_dom))
> +    {
> +      int_range<2> nz;
> +      nz.set_nonzero (TREE_TYPE (name));
> +      r.intersect (nz);
> +      return true;
> +    }
> +  return false;
> +}
> +
>  // Allocate an populate the bitmap for NAME.  An ON bit for a block
>  // index indicates there is a non-null reference in that block.  In
>  // order to populate the bitmap, a quick run of all the immediate uses
> @@ -857,9 +880,8 @@ ranger_cache::range_of_def (irange &r, tree name, basic_block bb)
>         r = gimple_range_global (name);
>      }
>
> -  if (bb && r.varying_p () && m_non_null.non_null_deref_p (name, bb, false) &&
> -      !cfun->can_throw_non_call_exceptions)
> -    r = range_nonzero (TREE_TYPE (name));
> +  if (bb)
> +    m_non_null.adjust_range (r, name, bb, false);
>  }
>
>  // Get the range of NAME as it occurs on entry to block BB.
> @@ -878,12 +900,7 @@ ranger_cache::entry_range (irange &r, tree name, basic_block bb)
>    if (!m_on_entry.get_bb_range (r, name, bb))
>      range_of_def (r, name);
>
> -  // Check if pointers have any non-null dereferences.  Non-call
> -  // exceptions mean we could throw in the middle of the block, so just
> -  // punt for now on those.
> -  if (r.varying_p () && m_non_null.non_null_deref_p (name, bb, false) &&
> -      !cfun->can_throw_non_call_exceptions)
> -    r = range_nonzero (TREE_TYPE (name));
> +  m_non_null.adjust_range (r, name, bb, false);
>  }
>
>  // Get the range of NAME as it occurs on exit from block BB.
> diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
> index ecf63dc01b3..f842e9c092a 100644
> --- a/gcc/gimple-range-cache.h
> +++ b/gcc/gimple-range-cache.h
> @@ -34,6 +34,8 @@ public:
>    non_null_ref ();
>    ~non_null_ref ();
>    bool non_null_deref_p (tree name, basic_block bb, bool search_dom = true);
> +  bool adjust_range (irange &r, tree name, basic_block bb,
> +                    bool search_dom = true);
>  private:
>    vec <bitmap> m_nn;
>    void process_name (tree name);
> diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
> index 1851339c528..b210787d0b7 100644
> --- a/gcc/gimple-range.cc
> +++ b/gcc/gimple-range.cc
> @@ -69,9 +69,7 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
>    if (def_stmt && gimple_bb (def_stmt) == bb)
>      {
>        range_of_stmt (r, def_stmt, expr);
> -      if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
> -         m_cache.m_non_null.non_null_deref_p (expr, bb))
> -       r = range_nonzero (TREE_TYPE (expr));
> +      m_cache.m_non_null.adjust_range (r, expr, bb, true);
>      }
>    else
>      // Otherwise OP comes from outside this block, use range on entry.
> @@ -95,9 +93,7 @@ gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name)
>    if (m_cache.block_range (entry_range, bb, name))
>      r.intersect (entry_range);
>
> -  if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
> -      m_cache.m_non_null.non_null_deref_p (name, bb))
> -    r = range_nonzero (TREE_TYPE (name));
> +  m_cache.m_non_null.adjust_range (r, name, bb, true);
>  }
>
>  // Calculate the range for NAME at the end of block BB and return it in R.
> --
> 2.31.1
>

[-- Attachment #2: 0001-Allow-non-null-adjustments-for-pointers-even-when-th.patch --]
[-- Type: text/x-patch, Size: 1072 bytes --]

From fc7e0e7755af48f15f3eae8cfb8782ed07274e91 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Wed, 21 Jul 2021 17:14:43 +0200
Subject: [PATCH] Allow non-null adjustments for pointers even when there is a
 known range.

I have run into yet another case where there is a known range for a
pointer, but it does not exclude non-null, so no adjustments are
performed.

gcc/ChangeLog:

	* gimple-range-cache.cc (non_null_ref::adjust_range): Do not
	check for varying.
---
 gcc/gimple-range-cache.cc | 1 -
 1 file changed, 1 deletion(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 23597ade802..95500ed6dc1 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -93,7 +93,6 @@ non_null_ref::adjust_range (irange &r, tree name, basic_block bb,
   // exceptions mean we could throw in the middle of the block, so just
   // punt for now on those.
   if (!cfun->can_throw_non_call_exceptions
-      && r.varying_p ()
       && non_null_deref_p (name, bb, search_dom))
     {
       int_range<2> nz;
-- 
2.31.1

Re: [PUSHED] Abstract out non_null adjustments in ranger.

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 6521 bytes --]

Well, arbitrarily allowing everything caused some -Wnonnull
regressions.  I've changed the check to !r.zero_p() && !r.nonzero_p(),
as the only reasonable ranges for pointers besides varying/undefined
are zero and non-zero.

Attached is the final version of the patch I have pushed.

Tested on x86-64 Linux.

On Wed, Jul 21, 2021 at 5:29 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> As I mentioned when I pushed the patch in this thread, I have run into
> cases where a pointer has a non-varying range, but it includes 0.  The
> varying check causes no further refinements to be done.  The previous
> cases I had seen were in follow-up threader work, so I was delaying
> pushing this until then.  But I'm now going through VRP cases that
> evrp is missing, and this is one of the main culprits.
>
> I will push this once tests are done.  If for some reason, varying
> restrictions are needed, we can always adjust the callers to
> adjust_range.
>
> Aldy
>
> On Thu, Jul 15, 2021 at 2:21 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > There are 4 exact copies of the non-null range adjusting code in the
> > ranger.  This patch abstracts the functionality into a separate method.
> >
> > As a follow-up I would like to remove the varying_p check, since I have
> > seen incoming ranges such as [0, 0xff....ef] which are not varying, but
> > are not-null.  Removing the varying restriction catches those.
> >
> > Tested on x86-64 Linux.
> >
> > Pushed to trunk.
> >
> > p.s. Andrew, what are your thoughts on removing the varying_p() check as
> > a follow-up?
> >
> > gcc/ChangeLog:
> >
> >         * gimple-range-cache.cc (non_null_ref::adjust_range): New.
> >         (ranger_cache::range_of_def): Call adjust_range.
> >         (ranger_cache::entry_range): Same.
> >         * gimple-range-cache.h (non_null_ref::adjust_range): New.
> >         * gimple-range.cc (gimple_ranger::range_of_expr): Call
> >         adjust_range.
> >         (gimple_ranger::range_on_entry): Same.
> > ---
> >  gcc/gimple-range-cache.cc | 35 ++++++++++++++++++++++++++---------
> >  gcc/gimple-range-cache.h  |  2 ++
> >  gcc/gimple-range.cc       |  8 ++------
> >  3 files changed, 30 insertions(+), 15 deletions(-)
> >
> > diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
> > index 98ecdbbd68e..23597ade802 100644
> > --- a/gcc/gimple-range-cache.cc
> > +++ b/gcc/gimple-range-cache.cc
> > @@ -81,6 +81,29 @@ non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom)
> >    return false;
> >  }
> >
> > +// If NAME has a non-null dereference in block BB, adjust R with the
> > +// non-zero information from non_null_deref_p, and return TRUE.  If
> > +// SEARCH_DOM is true, non_null_deref_p should search the dominator tree.
> > +
> > +bool
> > +non_null_ref::adjust_range (irange &r, tree name, basic_block bb,
> > +                           bool search_dom)
> > +{
> > +  // Check if pointers have any non-null dereferences.  Non-call
> > +  // exceptions mean we could throw in the middle of the block, so just
> > +  // punt for now on those.
> > +  if (!cfun->can_throw_non_call_exceptions
> > +      && r.varying_p ()
> > +      && non_null_deref_p (name, bb, search_dom))
> > +    {
> > +      int_range<2> nz;
> > +      nz.set_nonzero (TREE_TYPE (name));
> > +      r.intersect (nz);
> > +      return true;
> > +    }
> > +  return false;
> > +}
> > +
> >  // Allocate an populate the bitmap for NAME.  An ON bit for a block
> >  // index indicates there is a non-null reference in that block.  In
> >  // order to populate the bitmap, a quick run of all the immediate uses
> > @@ -857,9 +880,8 @@ ranger_cache::range_of_def (irange &r, tree name, basic_block bb)
> >         r = gimple_range_global (name);
> >      }
> >
> > -  if (bb && r.varying_p () && m_non_null.non_null_deref_p (name, bb, false) &&
> > -      !cfun->can_throw_non_call_exceptions)
> > -    r = range_nonzero (TREE_TYPE (name));
> > +  if (bb)
> > +    m_non_null.adjust_range (r, name, bb, false);
> >  }
> >
> >  // Get the range of NAME as it occurs on entry to block BB.
> > @@ -878,12 +900,7 @@ ranger_cache::entry_range (irange &r, tree name, basic_block bb)
> >    if (!m_on_entry.get_bb_range (r, name, bb))
> >      range_of_def (r, name);
> >
> > -  // Check if pointers have any non-null dereferences.  Non-call
> > -  // exceptions mean we could throw in the middle of the block, so just
> > -  // punt for now on those.
> > -  if (r.varying_p () && m_non_null.non_null_deref_p (name, bb, false) &&
> > -      !cfun->can_throw_non_call_exceptions)
> > -    r = range_nonzero (TREE_TYPE (name));
> > +  m_non_null.adjust_range (r, name, bb, false);
> >  }
> >
> >  // Get the range of NAME as it occurs on exit from block BB.
> > diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
> > index ecf63dc01b3..f842e9c092a 100644
> > --- a/gcc/gimple-range-cache.h
> > +++ b/gcc/gimple-range-cache.h
> > @@ -34,6 +34,8 @@ public:
> >    non_null_ref ();
> >    ~non_null_ref ();
> >    bool non_null_deref_p (tree name, basic_block bb, bool search_dom = true);
> > +  bool adjust_range (irange &r, tree name, basic_block bb,
> > +                    bool search_dom = true);
> >  private:
> >    vec <bitmap> m_nn;
> >    void process_name (tree name);
> > diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
> > index 1851339c528..b210787d0b7 100644
> > --- a/gcc/gimple-range.cc
> > +++ b/gcc/gimple-range.cc
> > @@ -69,9 +69,7 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
> >    if (def_stmt && gimple_bb (def_stmt) == bb)
> >      {
> >        range_of_stmt (r, def_stmt, expr);
> > -      if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
> > -         m_cache.m_non_null.non_null_deref_p (expr, bb))
> > -       r = range_nonzero (TREE_TYPE (expr));
> > +      m_cache.m_non_null.adjust_range (r, expr, bb, true);
> >      }
> >    else
> >      // Otherwise OP comes from outside this block, use range on entry.
> > @@ -95,9 +93,7 @@ gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name)
> >    if (m_cache.block_range (entry_range, bb, name))
> >      r.intersect (entry_range);
> >
> > -  if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
> > -      m_cache.m_non_null.non_null_deref_p (name, bb))
> > -    r = range_nonzero (TREE_TYPE (name));
> > +  m_cache.m_non_null.adjust_range (r, name, bb, true);
> >  }
> >
> >  // Calculate the range for NAME at the end of block BB and return it in R.
> > --
> > 2.31.1
> >

[-- Attachment #2: 0001-Allow-non-null-adjustments-for-pointers-even-when-th.patch --]
[-- Type: text/x-patch, Size: 1754 bytes --]

From a95e917c48e62209383b5f81097af75f93a7a1c5 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Thu, 22 Jul 2021 16:03:53 +0200
Subject: [PATCH] Allow non-null adjustments for pointers even when there is a
 known range.

Fix non_null_ref::adjust_range so it always adjust ranges, not just
varying ranges.  This will allow pointers that have a range, but are not
necessarily non-null, to be adjusted.

gcc/ChangeLog:

	* gimple-range-cache.cc (non_null_ref::adjust_range): Replace
	varying_p check for null/non-null check.
---
 gcc/gimple-range-cache.cc | 17 +++++++++++------
 1 file changed, 11 insertions(+), 6 deletions(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 23597ade802..265a64bacca 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -89,12 +89,17 @@ bool
 non_null_ref::adjust_range (irange &r, tree name, basic_block bb,
 			    bool search_dom)
 {
-  // Check if pointers have any non-null dereferences.  Non-call
-  // exceptions mean we could throw in the middle of the block, so just
-  // punt for now on those.
-  if (!cfun->can_throw_non_call_exceptions
-      && r.varying_p ()
-      && non_null_deref_p (name, bb, search_dom))
+  // Non-call exceptions mean we could throw in the middle of the
+  // block, so just punt on those for now.
+  if (cfun->can_throw_non_call_exceptions)
+    return false;
+
+  // We only care about the null / non-null property of pointers.
+  if (!POINTER_TYPE_P (TREE_TYPE (name)) || r.zero_p () || r.nonzero_p ())
+    return false;
+
+  // 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));
-- 
2.31.1