[PATCH 0/4] tree-optimization/104288 - Add more granularity to non-null tracking

[PATCH 0/4] tree-optimization/104288 - Add more granularity to non-null tracking

[Andrew MacLeod]

I have a proposal for PR 104288.

This PR highlights the shortcomings of assuming that when the non-null 
property is seen within a block, that it applies to the entire block.

This is a 3 patch set, but is less dramatic than it sounds.  I just 
wanted to split it into small bits for safety and readability. The 
changes boil down to making the same queries as before, only with more 
precision.

patch set 1 changes the nonnull tracking system from a single bit to a 
pair of bits.  This uses the aligned_chunk code previously added to the 
sparse bitmaps, and the overall impact is minimal. This allows us to 
trace whether a block is non-null throughout the entire block, or just 
part of the block.

patch set 2 added a callback into ranger to register side effects of a 
statement after ranger_vrp has folded a statement during its domwalk.  
This simply checks if infer_nonnull_range is true on the statement just 
processed, and if it is, lets the non-null class know which then changes 
the state in that block to always non-null. There is no impact to the 
on-demand clients.

patch set 3 then added a new interface to non-null in which we can ask 
more refined question about the state of nonnull in a block.  All 
queries are then audited such that
   1) All queries within a block require that the nonnull property be 
100% guaranteed to be nonull in the block, or we dont adjust the range.
   2) Range on entry queries check if any dominator block has the 
non-null property at all.
This will ensure we don't make the assumption that non-null somewhere in 
the block always applies to the entire block.

The 3rd set also adds a more complicated test to the test suite to 
ensure we cannot remove a use early in the block even if we find it is 
non-null later in the same block, but then we will remove it later in 
the block.

the 4th patch is the GCC11 version.. much simpler, it only ever checks 
if non-null is true in a dominator, and doesn't check within the current 
block.  This works fine as EVRP runs in hybrid mode by default and evrp 
will pick up the inter-block granularity.

More details are provided with each patch. I think the risk is low since 
I do not believe we can do anything worse than we did before :-).  We 
can discuss alternatives if you think its too much at this stage.

ALL patches (in sequence) bootstrap on their own and each cause no 
regressions.

Andrew

[PATCH 5/4] tree-optimization/104288 - An alternative approach

[Andrew MacLeod]

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

On 2/7/22 09:29, Andrew MacLeod wrote:
> I have a proposal for PR 104288.
>
> ALL patches (in sequence) bootstrap on their own and each cause no 
> regressions.

I've been continuing to work with this towards the GCC13 solution for 
statement side effects.  And There is another possibility we could 
pursue which is less intrusive

I adapted the portions of patch 2/4 which process nonnull, but changes 
it from being in the nonnull class to being in the cache.

THe main difference is it continues to use a single bit, just changing 
all uses of it to *always* mean its non-null on exit to the block.

Range-on-entry is changed to only check dominator blocks, and 
range_of_expr doesn't check the bit at all.. in both ranger and the cache.

When we are doing the block walk and process side effects, the on-entry 
*cache* range for the block is adjusted to be non-null instead.   The 
statements which precede this stmt have already been processed, and all 
remaining statements in this block will now pick up this new non-value 
from the on-entry cache.  This should be perfectly safe.

The final tweak is when range_of_expr is looking the def block, it 
normally does not have an on entry cache value.  (the def is in the 
block, so there is no entry cache value).  It now checks to see if we 
have set one, which can only happen when we have been doing the 
statement walk and set the on-entry cache with  a non-null value.  This 
allows us to pick up the non-null range in the def block too... (once we 
have passed a statement which set nonnull of course).

THis patch provides much less change to trunk, and is probably a better 
approach as its closer to what is going to happen in GCC13.

Im still working with it, so the patch isnt fully refined yet... but it 
bootstraps and passes all test with no regressions.  And passes the new 
tests too.   I figured I would mention this before you look to hard at 
the other patchset.    the GCC11 patch doesn't change.

Let me know if you prefer this.... I think I do :-)  less churn, and 
closer to end state.

Andrew






[-- Attachment #2: 0005.diff --]
[-- Type: text/x-patch, Size: 11694 bytes --]

commit da6185993cf85f38b08e4c2801ca8e5fe914e40d
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Feb 7 15:52:16 2022 -0500

    Change nonnull to mean nonnull at exit.
    
            * gimple-range-cache.cc (non_null_ref::set_nonnull): New.
            (ranger_cache::range_of_def): Don't check non-null.
            (ranger_cache::entry_range): Don't check non-null.
            (ranger_cache::try_update_to_always_nonnull): New.
            (ranger_cache::infer_nonnull_call_attributes): New.
            (non_null_loadstore): New.
            (ranger_cache::block_apply_nonnull): New.
            * ranger-cache.h (class non_null_ref): Update prototypes.
            (class ranger_cache): Update prototypes.
            * gimple-range-path.cc (path_range_query::range_defined_in_block): Do
            not search dominators.
            (path_range_query::adjust_for_non_null_uses): Ditto.
            * gimple-range.cc (gimple_ranger::range_of_expr): Check on-entry for
            def overrides.  Do not check nonnull.
            (gimple_ranger::range_on_entry): Check dominators for nonnull.
            (gimple_ranger::range_on_exit): Check for nonnull.
            * gimple-range.cc (gimple_ranger::register_side_effects): New.
            * gimple-range.h (gimple_ranger::register_side_effects): New.
            * tree-vrp.cc (rvrp_folder::fold_stmt): Call register_side_effects.

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 16c881b13e1..c6aefb98b42 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -29,6 +29,10 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-pretty-print.h"
 #include "gimple-range.h"
 #include "tree-cfg.h"
+#include "target.h"
+#include "attribs.h"
+#include "gimple-iterator.h"
+#include "gimple-walk.h"
 
 #define DEBUG_RANGE_CACHE (dump_file					\
 			   && (param_ranger_debug & RANGER_DEBUG_CACHE))
@@ -50,6 +54,22 @@ non_null_ref::~non_null_ref ()
   m_nn.release ();
 }
 
+// This routine will update NAME in BB to be nonnull if it is not already.
+// return TRUE if the update happens.,
+
+bool
+non_null_ref::set_nonnull (basic_block bb, tree name)
+{
+  gcc_checking_assert (gimple_range_ssa_p (name)
+		       && POINTER_TYPE_P (TREE_TYPE (name)));
+  // Only process when its not already set.
+  if (non_null_deref_p  (name, bb, false))
+    return false;
+  // From this point forward, we'll be NON-NULL for sure if we see one.
+  bitmap_set_bit (m_nn[SSA_NAME_VERSION (name)], bb->index);
+  return true;
+}
+
 // Return true if NAME has a non-null dereference in block bb.  If this is the
 // first query for NAME, calculate the summary first.
 // If SEARCH_DOM is true, the search the dominator tree as well.
@@ -1014,9 +1034,6 @@ ranger_cache::range_of_def (irange &r, tree name, basic_block bb)
       else
 	r = gimple_range_global (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.
@@ -1034,8 +1051,6 @@ ranger_cache::entry_range (irange &r, tree name, basic_block bb)
   // Otherwise pick up the best available global value.
   if (!m_on_entry.get_bb_range (r, name, bb))
     range_of_def (r, name);
-
-  m_non_null.adjust_range (r, name, bb, false);
 }
 
 // Get the range of NAME as it occurs on exit from block BB.
@@ -1467,3 +1482,107 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block bb)
     }
   return true;
 }
+
+// This routine will update NAME in block BB to the nonnull state.
+// It will then update the on-netry cache for this block to be non-null
+// if it isn't already.
+
+void
+ranger_cache::try_update_to_always_nonnull (basic_block bb, tree name)
+{
+  if (gimple_range_ssa_p (name) && POINTER_TYPE_P (TREE_TYPE (name)))
+    {
+      m_non_null.set_nonnull (bb, name);
+      // Update the on-entry cache for BB to be non-zero
+      int_range_max r;
+      exit_range (r, name, bb);
+      if (m_non_null.adjust_range (r, name, bb, false))
+	m_on_entry.set_bb_range (name, bb, r);
+    }
+}
+
+// Adapted from infer_nonnull_range_by_attribute for calls to process
+// all operands which have the nonnull attribute set in stmt.
+
+void
+ranger_cache::infer_nonnull_call_attributes (gcall *stmt)
+{
+  if (gimple_call_internal_p (stmt))
+    return;
+
+  basic_block bb = gimple_bb (stmt);
+  tree fntype = gimple_call_fntype (stmt);
+  tree attrs = TYPE_ATTRIBUTES (fntype);
+  for (; attrs; attrs = TREE_CHAIN (attrs))
+    {
+      attrs = lookup_attribute ("nonnull", attrs);
+
+      /* If "nonnull" wasn't specified, we know nothing about
+	 the argument.  */
+      if (attrs == NULL_TREE)
+	return;
+
+      /* Check if "nonnull" applies to all the arguments.  */
+      if (TREE_VALUE (attrs) == NULL_TREE)
+	{
+	  for (unsigned int i = 0; i < gimple_call_num_args (stmt); i++)
+	    {
+	      tree op = gimple_call_arg (stmt, i);
+	      try_update_to_always_nonnull (bb, op);
+	    }
+	  return;
+	}
+
+      /* Now see whats in this nonnull list.  */
+      for (tree t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
+	{
+	  unsigned int idx = TREE_INT_CST_LOW (TREE_VALUE (t)) - 1;
+	  if (idx < gimple_call_num_args (stmt))
+	    {
+	      tree op = gimple_call_arg (stmt, idx);
+	      try_update_to_always_nonnull (bb, op);
+	    }
+	}
+    }
+}
+
+// Adapted from infer_nonnull_range_by_dereference and check_loadstore
+// to work for all operands.
+
+static bool
+non_null_loadstore (gimple *s, tree op, tree, void *data)
+{
+  if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
+    {
+      /* Some address spaces may legitimately dereference zero.  */
+      addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op));
+      if (!targetm.addr_space.zero_address_valid (as))
+	{
+	  tree ssa = TREE_OPERAND (op, 0);
+	  basic_block bb = gimple_bb (s);
+	  ((ranger_cache *)data)->try_update_to_always_nonnull (bb, ssa);
+	}
+    }
+  return false;
+}
+
+// This routine is used during a block walk to move the state of non-null for
+// any operands on stmt S to always nonnull.
+
+void
+ranger_cache::block_apply_nonnull (gimple *s)
+{
+  if (!flag_delete_null_pointer_checks)
+    return;
+  if (is_a<gphi *> (s))
+    return;
+  if (gimple_code (s) == GIMPLE_ASM || gimple_clobber_p (s))
+    return;
+  if (is_a<gcall *> (s))
+    {
+      infer_nonnull_call_attributes (as_a<gcall *> (s));
+      return;
+    }
+  walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore,
+			    non_null_loadstore);
+}
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index b54b6882aa8..f189fd8898f 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -36,6 +36,7 @@ public:
   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);
+  bool set_nonnull (basic_block bb, tree name);
 private:
   vec <bitmap> m_nn;
   void process_name (tree name);
@@ -106,6 +107,8 @@ public:
 
   void propagate_updated_value (tree name, basic_block bb);
 
+  void block_apply_nonnull (gimple *s);
+  void try_update_to_always_nonnull (basic_block bb, tree name);
   non_null_ref m_non_null;
   gori_compute m_gori;
 
@@ -118,6 +121,8 @@ private:
   void fill_block_cache (tree name, basic_block bb, basic_block def_bb);
   void propagate_cache (tree name);
 
+  void infer_nonnull_call_attributes (gcall *stmt);
+
   void range_of_def (irange &r, tree name, basic_block bb = NULL);
   void entry_range (irange &r, tree expr, basic_block bb);
   void exit_range (irange &r, tree expr, basic_block bb);
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 3bf9bd1e981..483bcd2e582 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -358,7 +358,7 @@ path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb)
     }
 
   if (bb)
-    m_non_null.adjust_range (r, name, bb);
+    m_non_null.adjust_range (r, name, bb, false);
 
   if (DEBUG_SOLVER && (bb || !r.varying_p ()))
     {
@@ -528,7 +528,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb)
       else
 	r.set_varying (TREE_TYPE (name));
 
-      if (m_non_null.adjust_range (r, name, bb))
+      if (m_non_null.adjust_range (r, name, bb, false))
 	set_cache (r, name);
     }
 }
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 73398ddef99..bffda11a558 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -35,6 +35,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-scalar-evolution.h"
 #include "gimple-range.h"
 #include "gimple-fold.h"
+#include "gimple-walk.h"
 
 gimple_ranger::gimple_ranger () :
 	non_executable_edge_flag (cfun),
@@ -117,8 +118,9 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
       // If name is defined in this block, try to get an range from S.
       if (def_stmt && gimple_bb (def_stmt) == bb)
 	{
-	  range_of_stmt (r, def_stmt, expr);
-	  m_cache.m_non_null.adjust_range (r, expr, bb, true);
+	  // Check for a defintion override from a block walk.
+	  if (!m_cache.block_range (r, bb, expr, false))
+	    range_of_stmt (r, def_stmt, expr);
 	}
       // Otherwise OP comes from outside this block, use range on entry.
       else
@@ -151,7 +153,12 @@ 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);
 
-  m_cache.m_non_null.adjust_range (r, name, bb, true);
+  if (dom_info_available_p (CDI_DOMINATORS))
+    {
+      basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+      if (dom_bb)
+	m_cache.m_non_null.adjust_range (r, name, dom_bb, true);
+    }
 
   if (idx)
     tracer.trailer (idx, "range_on_entry", true, name, r);
@@ -185,6 +192,7 @@ gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name)
     range_of_expr (r, name, s);
   else
     range_on_entry (r, bb, name);
+  m_cache.m_non_null.adjust_range (r, name, bb, false);
   gcc_checking_assert (r.undefined_p ()
 		       || range_compatible_p (r.type (), TREE_TYPE (name)));
   
@@ -436,6 +444,16 @@ gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
   return ret;
 }
 
+// Called during dominator walks to register any side effects that take effect
+// from this point forward.  Current release is only for tracking non-null
+// within a block.
+
+void
+gimple_ranger::register_side_effects (gimple *s)
+{
+  m_cache.block_apply_nonnull (s);
+}
+
 // This routine will export whatever global ranges are known to GCC
 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
 
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index ec568153a8d..0733a534853 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -60,6 +60,7 @@ public:
   void dump_bb (FILE *f, basic_block bb);
   auto_edge_flag non_executable_edge_flag;
   bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree));
+  void register_side_effects (gimple *s);
 protected:
   bool fold_range_internal (irange &r, gimple *s, tree name);
   void prefill_name (irange &r, tree name);
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 62946450b13..e9f19d0c8b9 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -4309,9 +4309,11 @@ public:
 
   bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
   {
-    if (m_simplifier.simplify (gsi))
-      return true;
-    return m_ranger->fold_stmt (gsi, follow_single_use_edges);
+    bool ret = m_simplifier.simplify (gsi);
+    if (!ret)
+      ret = m_ranger->fold_stmt (gsi, follow_single_use_edges);
+    m_ranger->register_side_effects (gsi_stmt (*gsi));
+    return ret;
   }
 
 private:

Re: [PATCH 5/4] tree-optimization/104288 - An alternative approach

[Richard Biener]

On Tue, Feb 8, 2022 at 2:33 AM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> On 2/7/22 09:29, Andrew MacLeod wrote:
> > I have a proposal for PR 104288.
> >
> > ALL patches (in sequence) bootstrap on their own and each cause no
> > regressions.
>
> I've been continuing to work with this towards the GCC13 solution for
> statement side effects.  And There is another possibility we could
> pursue which is less intrusive
>
> I adapted the portions of patch 2/4 which process nonnull, but changes
> it from being in the nonnull class to being in the cache.
>
> THe main difference is it continues to use a single bit, just changing
> all uses of it to *always* mean its non-null on exit to the block.
>
> Range-on-entry is changed to only check dominator blocks, and
> range_of_expr doesn't check the bit at all.. in both ranger and the cache.
>
> When we are doing the block walk and process side effects, the on-entry
> *cache* range for the block is adjusted to be non-null instead.   The
> statements which precede this stmt have already been processed, and all
> remaining statements in this block will now pick up this new non-value
> from the on-entry cache.  This should be perfectly safe.
>
> The final tweak is when range_of_expr is looking the def block, it
> normally does not have an on entry cache value.  (the def is in the
> block, so there is no entry cache value).  It now checks to see if we
> have set one, which can only happen when we have been doing the
> statement walk and set the on-entry cache with  a non-null value.  This
> allows us to pick up the non-null range in the def block too... (once we
> have passed a statement which set nonnull of course).
>
> THis patch provides much less change to trunk, and is probably a better
> approach as its closer to what is going to happen in GCC13.
>
> Im still working with it, so the patch isnt fully refined yet... but it
> bootstraps and passes all test with no regressions.  And passes the new
> tests too.   I figured I would mention this before you look to hard at
> the other patchset.    the GCC11 patch doesn't change.
>
> Let me know if you prefer this.... I think I do :-)  less churn, and
> closer to end state.

Yes, I very much prefer this - some comments to the other patches
still apply to this one.  Like using get_nonnull_args and probably
adding a bail-out to computing ranges from stmts that can throw
internally or have abnormal control flow (to not get into range-on-exit
vs. normal vs. exceptional or abnormal edges).

Richard.

>
> Andrew
>
>
>
>
>

Re: [PATCH 5/4] tree-optimization/104288 - An alternative approach

[Andrew MacLeod]

On 2/8/22 03:32, Richard Biener wrote:
> On Tue, Feb 8, 2022 at 2:33 AM Andrew MacLeod via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> On 2/7/22 09:29, Andrew MacLeod wrote:
>>> I have a proposal for PR 104288.
>>>
>>> ALL patches (in sequence) bootstrap on their own and each cause no
>>> regressions.
>> I've been continuing to work with this towards the GCC13 solution for
>> statement side effects.  And There is another possibility we could
>> pursue which is less intrusive
>>
>> I adapted the portions of patch 2/4 which process nonnull, but changes
>> it from being in the nonnull class to being in the cache.
>>
>> THe main difference is it continues to use a single bit, just changing
>> all uses of it to *always* mean its non-null on exit to the block.
>>
>> Range-on-entry is changed to only check dominator blocks, and
>> range_of_expr doesn't check the bit at all.. in both ranger and the cache.
>>
>> When we are doing the block walk and process side effects, the on-entry
>> *cache* range for the block is adjusted to be non-null instead.   The
>> statements which precede this stmt have already been processed, and all
>> remaining statements in this block will now pick up this new non-value
>> from the on-entry cache.  This should be perfectly safe.
>>
>> The final tweak is when range_of_expr is looking the def block, it
>> normally does not have an on entry cache value.  (the def is in the
>> block, so there is no entry cache value).  It now checks to see if we
>> have set one, which can only happen when we have been doing the
>> statement walk and set the on-entry cache with  a non-null value.  This
>> allows us to pick up the non-null range in the def block too... (once we
>> have passed a statement which set nonnull of course).
>>
>> THis patch provides much less change to trunk, and is probably a better
>> approach as its closer to what is going to happen in GCC13.
>>
>> Im still working with it, so the patch isnt fully refined yet... but it
>> bootstraps and passes all test with no regressions.  And passes the new
>> tests too.   I figured I would mention this before you look to hard at
>> the other patchset.    the GCC11 patch doesn't change.
>>
>> Let me know if you prefer this.... I think I do :-)  less churn, and
>> closer to end state.
> Yes, I very much prefer this - some comments to the other patches
> still apply to this one.  Like using get_nonnull_args and probably
> adding a bail-out to computing ranges from stmts that can throw
> internally or have abnormal control flow (to not get into range-on-exit
> vs. normal vs. exceptional or abnormal edges).
>
> Richard.

Yeah, I like this one way better too.  I will address and repost

Andrew

Re: [PATCH 5/4] tree-optimization/104288 - An alternative approach

[Andrew MacLeod]

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

On 2/8/22 03:32, Richard Biener wrote:
> On Tue, Feb 8, 2022 at 2:33 AM Andrew MacLeod via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> On 2/7/22 09:29, Andrew MacLeod wrote:
>>> I have a proposal for PR 104288.
>>>
>>> ALL patches (in sequence) bootstrap on their own and each cause no
>>> regressions.
>> I've been continuing to work with this towards the GCC13 solution for
>> statement side effects.  And There is another possibility we could
>> pursue which is less intrusive
>>
>> I adapted the portions of patch 2/4 which process nonnull, but changes
>> it from being in the nonnull class to being in the cache.
>>
>> THe main difference is it continues to use a single bit, just changing
>> all uses of it to *always* mean its non-null on exit to the block.
>>
>> Range-on-entry is changed to only check dominator blocks, and
>> range_of_expr doesn't check the bit at all.. in both ranger and the cache.
>>
>> When we are doing the block walk and process side effects, the on-entry
>> *cache* range for the block is adjusted to be non-null instead.   The
>> statements which precede this stmt have already been processed, and all
>> remaining statements in this block will now pick up this new non-value
>> from the on-entry cache.  This should be perfectly safe.
>>
>> The final tweak is when range_of_expr is looking the def block, it
>> normally does not have an on entry cache value.  (the def is in the
>> block, so there is no entry cache value).  It now checks to see if we
>> have set one, which can only happen when we have been doing the
>> statement walk and set the on-entry cache with  a non-null value.  This
>> allows us to pick up the non-null range in the def block too... (once we
>> have passed a statement which set nonnull of course).
>>
>> THis patch provides much less change to trunk, and is probably a better
>> approach as its closer to what is going to happen in GCC13.
>>
>> Im still working with it, so the patch isnt fully refined yet... but it
>> bootstraps and passes all test with no regressions.  And passes the new
>> tests too.   I figured I would mention this before you look to hard at
>> the other patchset.    the GCC11 patch doesn't change.
>>
>> Let me know if you prefer this.... I think I do :-)  less churn, and
>> closer to end state.
> Yes, I very much prefer this - some comments to the other patches
> still apply to this one.  Like using get_nonnull_args and probably
> adding a bail-out to computing ranges from stmts that can throw
> internally or have abnormal control flow (to not get into range-on-exit
> vs. normal vs. exceptional or abnormal edges).
>
> Richard.

Here's the update which is going thru testing now.  I think I covered 
the comments?

Andrew



[-- Attachment #2: 0001-Register-non-null-side-effects-properly.patch --]
[-- Type: text/x-patch, Size: 12558 bytes --]

From e3286a6a185952f3acaa89b90beee33149cd7512 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Mon, 7 Feb 2022 15:52:16 -0500
Subject: [PATCH] Register non-null side effects properly.

This patch adjusts uses of nonnull to accurately reflect "somewhere in block".
It also adds the ability to register statement side effects within a block
for ranger which will apply for the rest of the block.

	PR tree-optimization/104288
	gcc/
	* gimple-range-cache.cc (non_null_ref::set_nonnull): New.
	(ranger_cache::range_of_def): Don't check non-null.
	(ranger_cache::entry_range): Don't check non-null.
	(ranger_cache::range_on_edge): Check for nonnull on normal edges.
	(ranger_cache::update_to_nonnull): New.
        (non_null_loadstore): New.
        (ranger_cache::block_apply_nonnull): New.
	* ranger-cache.h (class non_null_ref): Update prototypes.
	(class ranger_cache): Update prototypes.
	* gimple-range-path.cc (path_range_query::range_defined_in_block): Do
	not search dominators.
	(path_range_query::adjust_for_non_null_uses): Ditto.
	* gimple-range.cc (gimple_ranger::range_of_expr): Check on-entry for
	def overrides.  Do not check nonnull.
	(gimple_ranger::range_on_entry): Check dominators for nonnull.
	(gimple_ranger::range_on_edge): Check for nonnull on normal edges..
	* gimple-range.cc (gimple_ranger::register_side_effects): New.
	* gimple-range.h (gimple_ranger::register_side_effects): New.
	* tree-vrp.cc (rvrp_folder::fold_stmt): Call register_side_effects.

	testsuite/gcc/
	* gcc.dg/pr104288.c: New.
---
 gcc/gimple-range-cache.cc       | 103 ++++++++++++++++++++++++++++++--
 gcc/gimple-range-cache.h        |   3 +
 gcc/gimple-range-path.cc        |   4 +-
 gcc/gimple-range.cc             |  27 ++++++++-
 gcc/gimple-range.h              |   1 +
 gcc/testsuite/gcc.dg/pr104288.c |  23 +++++++
 gcc/tree-vrp.cc                 |   8 ++-
 7 files changed, 156 insertions(+), 13 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/pr104288.c

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 16c881b13e1..583ba97ff75 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -29,6 +29,10 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-pretty-print.h"
 #include "gimple-range.h"
 #include "tree-cfg.h"
+#include "target.h"
+#include "attribs.h"
+#include "gimple-iterator.h"
+#include "gimple-walk.h"
 
 #define DEBUG_RANGE_CACHE (dump_file					\
 			   && (param_ranger_debug & RANGER_DEBUG_CACHE))
@@ -50,6 +54,21 @@ non_null_ref::~non_null_ref ()
   m_nn.release ();
 }
 
+// This routine will update NAME in BB to be nonnull if it is not already.
+// return TRUE if the update happens.
+
+bool
+non_null_ref::set_nonnull (basic_block bb, tree name)
+{
+  gcc_checking_assert (gimple_range_ssa_p (name)
+		       && POINTER_TYPE_P (TREE_TYPE (name)));
+  // Only process when its not already set.
+  if (non_null_deref_p  (name, bb, false))
+    return false;
+  bitmap_set_bit (m_nn[SSA_NAME_VERSION (name)], bb->index);
+  return true;
+}
+
 // Return true if NAME has a non-null dereference in block bb.  If this is the
 // first query for NAME, calculate the summary first.
 // If SEARCH_DOM is true, the search the dominator tree as well.
@@ -1014,9 +1033,6 @@ ranger_cache::range_of_def (irange &r, tree name, basic_block bb)
       else
 	r = gimple_range_global (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.
@@ -1034,8 +1050,6 @@ ranger_cache::entry_range (irange &r, tree name, basic_block bb)
   // Otherwise pick up the best available global value.
   if (!m_on_entry.get_bb_range (r, name, bb))
     range_of_def (r, name);
-
-  m_non_null.adjust_range (r, name, bb, false);
 }
 
 // Get the range of NAME as it occurs on exit from block BB.
@@ -1089,6 +1103,10 @@ ranger_cache::range_of_expr (irange &r, tree name, gimple *stmt)
    if (gimple_range_ssa_p (expr))
     {
       exit_range (r, expr, e->src);
+      // If this is not an abnormal edge, check for a non-null exit.
+      if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0
+	  && POINTER_TYPE_P (TREE_TYPE (expr)))
+	m_non_null.adjust_range (r, expr, e->src, false);
       int_range_max edge_range;
       if (m_gori.outgoing_edge_range_p (edge_range, e, expr, *this))
 	r.intersect (edge_range);
@@ -1467,3 +1485,78 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block bb)
     }
   return true;
 }
+
+// This routine will update NAME in block BB to the nonnull state.
+// It will then update the on-entry cache for this block to be non-null
+// if it isn't already.
+
+void
+ranger_cache::update_to_nonnull (basic_block bb, tree name)
+{
+  if (gimple_range_ssa_p (name) && POINTER_TYPE_P (TREE_TYPE (name)))
+    {
+      m_non_null.set_nonnull (bb, name);
+      // Update the on-entry cache for BB to be non-zero.  Note this can set
+      // the on entry value in the DEF block, which can override the def.
+      int_range_max r;
+      exit_range (r, name, bb);
+      if (m_non_null.adjust_range (r, name, bb, false))
+	m_on_entry.set_bb_range (name, bb, r);
+    }
+}
+
+// Adapted from infer_nonnull_range_by_dereference and check_loadstore
+// to process nonnull ssa_name OP in S.  DATA contains the ranger_cache.
+
+static bool
+non_null_loadstore (gimple *s, tree op, tree, void *data)
+{
+  if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
+    {
+      /* Some address spaces may legitimately dereference zero.  */
+      addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op));
+      if (!targetm.addr_space.zero_address_valid (as))
+	{
+	  tree ssa = TREE_OPERAND (op, 0);
+	  basic_block bb = gimple_bb (s);
+	  ((ranger_cache *)data)->update_to_nonnull (bb, ssa);
+	}
+    }
+  return false;
+}
+
+// This routine is used during a block walk to move the state of non-null for
+// any operands on stmt S to nonnull.
+
+void
+ranger_cache::block_apply_nonnull (gimple *s)
+{
+  if (!flag_delete_null_pointer_checks)
+    return;
+  if (is_a<gphi *> (s))
+    return;
+  if (gimple_code (s) == GIMPLE_ASM || gimple_clobber_p (s))
+    return;
+  if (is_a<gcall *> (s))
+    {
+      tree fntype = gimple_call_fntype (s);
+      bitmap nonnullargs = get_nonnull_args (fntype);
+      // Process any non-null arguments
+      if (nonnullargs)
+	{
+	  basic_block bb = gimple_bb (s);
+	  for (unsigned i = 0; i < gimple_call_num_args (s); i++)
+	    {
+	      if (bitmap_empty_p (nonnullargs) || bitmap_bit_p (nonnullargs, i))
+		{
+		  tree op = gimple_call_arg (s, i);
+		  update_to_nonnull (bb, op);
+		}
+	    }
+	  BITMAP_FREE (nonnullargs);
+	}
+      // Fallthru and walk load/store ops now.
+    }
+  walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore,
+			    non_null_loadstore);
+}
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index b54b6882aa8..e0470fba3fd 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -36,6 +36,7 @@ public:
   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);
+  bool set_nonnull (basic_block bb, tree name);
 private:
   vec <bitmap> m_nn;
   void process_name (tree name);
@@ -106,6 +107,8 @@ public:
 
   void propagate_updated_value (tree name, basic_block bb);
 
+  void block_apply_nonnull (gimple *s);
+  void update_to_nonnull (basic_block bb, tree name);
   non_null_ref m_non_null;
   gori_compute m_gori;
 
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 3bf9bd1e981..483bcd2e582 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -358,7 +358,7 @@ path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb)
     }
 
   if (bb)
-    m_non_null.adjust_range (r, name, bb);
+    m_non_null.adjust_range (r, name, bb, false);
 
   if (DEBUG_SOLVER && (bb || !r.varying_p ()))
     {
@@ -528,7 +528,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb)
       else
 	r.set_varying (TREE_TYPE (name));
 
-      if (m_non_null.adjust_range (r, name, bb))
+      if (m_non_null.adjust_range (r, name, bb, false))
 	set_cache (r, name);
     }
 }
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 73398ddef99..8449aa808ea 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -35,6 +35,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-scalar-evolution.h"
 #include "gimple-range.h"
 #include "gimple-fold.h"
+#include "gimple-walk.h"
 
 gimple_ranger::gimple_ranger () :
 	non_executable_edge_flag (cfun),
@@ -117,8 +118,9 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
       // If name is defined in this block, try to get an range from S.
       if (def_stmt && gimple_bb (def_stmt) == bb)
 	{
-	  range_of_stmt (r, def_stmt, expr);
-	  m_cache.m_non_null.adjust_range (r, expr, bb, true);
+	  // Check for a definition override from a block walk.
+	  if (!m_cache.block_range (r, bb, expr, false))
+	    range_of_stmt (r, def_stmt, expr);
 	}
       // Otherwise OP comes from outside this block, use range on entry.
       else
@@ -151,7 +153,12 @@ 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);
 
-  m_cache.m_non_null.adjust_range (r, name, bb, true);
+  if (dom_info_available_p (CDI_DOMINATORS))
+    {
+      basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+      if (dom_bb && POINTER_TYPE_P (TREE_TYPE (name)))
+	m_cache.m_non_null.adjust_range (r, name, dom_bb, true);
+    }
 
   if (idx)
     tracer.trailer (idx, "range_on_entry", true, name, r);
@@ -227,6 +234,10 @@ gimple_ranger::range_on_edge (irange &r, edge e, tree name)
   else
     {
       range_on_exit (r, e->src, name);
+      // If this is not an abnormal edge, check for a non-null exit .
+      if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0
+	  && POINTER_TYPE_P (TREE_TYPE (name)))
+	m_cache.m_non_null.adjust_range (r, name, e->src, false);
       gcc_checking_assert  (r.undefined_p ()
 			    || range_compatible_p (r.type(), TREE_TYPE (name)));
 
@@ -436,6 +447,16 @@ gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
   return ret;
 }
 
+// Called during dominator walks to register any side effects that take effect
+// from this point forward.  Current release is only for tracking non-null
+// within a block.
+
+void
+gimple_ranger::register_side_effects (gimple *s)
+{
+  m_cache.block_apply_nonnull (s);
+}
+
 // This routine will export whatever global ranges are known to GCC
 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
 
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index ec568153a8d..0733a534853 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -60,6 +60,7 @@ public:
   void dump_bb (FILE *f, basic_block bb);
   auto_edge_flag non_executable_edge_flag;
   bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree));
+  void register_side_effects (gimple *s);
 protected:
   bool fold_range_internal (irange &r, gimple *s, tree name);
   void prefill_name (irange &r, tree name);
diff --git a/gcc/testsuite/gcc.dg/pr104288.c b/gcc/testsuite/gcc.dg/pr104288.c
new file mode 100644
index 00000000000..95eb196f9e4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr104288.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp -fdelete-null-pointer-checks" } */
+/* { dg-skip-if "" { keeps_null_pointer_checks } } */
+
+void keep(int result) __attribute__((noipa));
+void keep(int result)
+{
+    if (result)
+        __builtin_exit(0);
+}
+
+void foo (void *p) __attribute__((nonnull(1)));
+
+void bar (void *p)
+{
+  keep (p == 0);
+  foo (p);
+  if (!p)
+    __builtin_abort ();
+}
+
+/* { dg-final { scan-tree-dump-not "abort" "evrp" } } */
+/* { dg-final { scan-tree-dump-times  "== 0B;" 1 "evrp" } } */
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 62946450b13..e9f19d0c8b9 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -4309,9 +4309,11 @@ public:
 
   bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
   {
-    if (m_simplifier.simplify (gsi))
-      return true;
-    return m_ranger->fold_stmt (gsi, follow_single_use_edges);
+    bool ret = m_simplifier.simplify (gsi);
+    if (!ret)
+      ret = m_ranger->fold_stmt (gsi, follow_single_use_edges);
+    m_ranger->register_side_effects (gsi_stmt (*gsi));
+    return ret;
   }
 
 private:
-- 
2.17.2

[PATCH V2] tree-optimization/104288 - Register non-null side effects properly.

[Andrew MacLeod]

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

On 2/8/22 03:32, Richard Biener wrote:
> On Tue, Feb 8, 2022 at 2:33 AM Andrew MacLeod via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> On 2/7/22 09:29, Andrew MacLeod wrote:
>>> I have a proposal for PR 104288.
>>>
>>> ALL patches (in sequence) bootstrap on their own and each cause no
>>> regressions.
>> I've been continuing to work with this towards the GCC13 solution for
>> statement side effects.  And There is another possibility we could
>> pursue which is less intrusive
>>
>> I adapted the portions of patch 2/4 which process nonnull, but changes
>> it from being in the nonnull class to being in the cache.
>>
>> THe main difference is it continues to use a single bit, just changing
>> all uses of it to *always* mean its non-null on exit to the block.
>>
>> Range-on-entry is changed to only check dominator blocks, and
>> range_of_expr doesn't check the bit at all.. in both ranger and the cache.
>>
>> When we are doing the block walk and process side effects, the on-entry
>> *cache* range for the block is adjusted to be non-null instead.   The
>> statements which precede this stmt have already been processed, and all
>> remaining statements in this block will now pick up this new non-value
>> from the on-entry cache.  This should be perfectly safe.
>>
>> The final tweak is when range_of_expr is looking the def block, it
>> normally does not have an on entry cache value.  (the def is in the
>> block, so there is no entry cache value).  It now checks to see if we
>> have set one, which can only happen when we have been doing the
>> statement walk and set the on-entry cache with  a non-null value.  This
>> allows us to pick up the non-null range in the def block too... (once we
>> have passed a statement which set nonnull of course).
>>
>> THis patch provides much less change to trunk, and is probably a better
>> approach as its closer to what is going to happen in GCC13.
>>
>> Im still working with it, so the patch isnt fully refined yet... but it
>> bootstraps and passes all test with no regressions.  And passes the new
>> tests too.   I figured I would mention this before you look to hard at
>> the other patchset.    the GCC11 patch doesn't change.
>>
>> Let me know if you prefer this.... I think I do :-)  less churn, and
>> closer to end state.
> Yes, I very much prefer this - some comments to the other patches
> still apply to this one.  Like using get_nonnull_args and probably
> adding a bail-out to computing ranges from stmts that can throw
> internally or have abnormal control flow (to not get into range-on-exit
> vs. normal vs. exceptional or abnormal edges).
>
> Richard.

with some minor performance tweaks, such as moving adjust_range() to the 
header so it can be inlined .

range-on-edge now applies the non-null from the src block if 
appropriate, not in range-on-exit.   That should resolve  the internal 
throwing statements I think.  and I have switched over to 
get_nonnull_args().

Bootstraps on build-x86_64-pc-linux-gnu and passes all regressions.

OK for trunk, or did I miss something?

Andrew

PS. odd.. I haven't seen the git diff be wrong before, but it shows the 
ranger_cache::range_on_edge changes as being in 
gimple_cache::range_of_expr...  They are most definitely are not....   
and it applies/de-applies fine.. so its just an oddity I guess.


[-- Attachment #2: 0001-Register-non-null-side-effects-properly.patch --]
[-- Type: text/x-patch, Size: 15215 bytes --]

From 2f38b3de7958d83dab383c73029aedbd108d8930 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Mon, 7 Feb 2022 15:52:16 -0500
Subject: [PATCH] Register non-null side effects properly.

This patch adjusts uses of nonnull to accurately reflect "somewhere in block".
It also adds the ability to register statement side effects within a block
for ranger which will apply for the rest of the block.

	PR tree-optimization/104288
	gcc/
	* gimple-range-cache.cc (non_null_ref::set_nonnull): New.
	(non_null_ref::adjust_range): Move to header.
	(ranger_cache::range_of_def): Don't check non-null.
	(ranger_cache::entry_range): Don't check non-null.
	(ranger_cache::range_on_edge): Check for nonnull on normal edges.
	(ranger_cache::update_to_nonnull): New.
        (non_null_loadstore): New.
        (ranger_cache::block_apply_nonnull): New.
	* ranger-cache.h (class non_null_ref): Update prototypes.
	(non_null_ref::adjust_range): Move to here and inline.
	(class ranger_cache): Update prototypes.
	* gimple-range-path.cc (path_range_query::range_defined_in_block): Do
	not search dominators.
	(path_range_query::adjust_for_non_null_uses): Ditto.
	* gimple-range.cc (gimple_ranger::range_of_expr): Check on-entry for
	def overrides.  Do not check nonnull.
	(gimple_ranger::range_on_entry): Check dominators for nonnull.
	(gimple_ranger::range_on_edge): Check for nonnull on normal edges..
	* gimple-range.cc (gimple_ranger::register_side_effects): New.
	* gimple-range.h (gimple_ranger::register_side_effects): New.
	* tree-vrp.cc (rvrp_folder::fold_stmt): Call register_side_effects.

	testsuite/gcc/
	* gcc.dg/pr104288.c: New.
---
 gcc/gimple-range-cache.cc       | 135 ++++++++++++++++++++++++--------
 gcc/gimple-range-cache.h        |  31 ++++++++
 gcc/gimple-range-path.cc        |   4 +-
 gcc/gimple-range.cc             |  27 ++++++-
 gcc/gimple-range.h              |   1 +
 gcc/testsuite/gcc.dg/pr104288.c |  23 ++++++
 gcc/tree-vrp.cc                 |   8 +-
 7 files changed, 187 insertions(+), 42 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/pr104288.c

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 16c881b13e1..613135266a4 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -29,6 +29,10 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-pretty-print.h"
 #include "gimple-range.h"
 #include "tree-cfg.h"
+#include "target.h"
+#include "attribs.h"
+#include "gimple-iterator.h"
+#include "gimple-walk.h"
 
 #define DEBUG_RANGE_CACHE (dump_file					\
 			   && (param_ranger_debug & RANGER_DEBUG_CACHE))
@@ -50,6 +54,21 @@ non_null_ref::~non_null_ref ()
   m_nn.release ();
 }
 
+// This routine will update NAME in BB to be nonnull if it is not already.
+// return TRUE if the update happens.
+
+bool
+non_null_ref::set_nonnull (basic_block bb, tree name)
+{
+  gcc_checking_assert (gimple_range_ssa_p (name)
+		       && POINTER_TYPE_P (TREE_TYPE (name)));
+  // Only process when its not already set.
+  if (non_null_deref_p  (name, bb, false))
+    return false;
+  bitmap_set_bit (m_nn[SSA_NAME_VERSION (name)], bb->index);
+  return true;
+}
+
 // Return true if NAME has a non-null dereference in block bb.  If this is the
 // first query for NAME, calculate the summary first.
 // If SEARCH_DOM is true, the search the dominator tree as well.
@@ -87,35 +106,6 @@ 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)
-{
-  // 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)))
-    return false;
-  if (r.undefined_p () || r.lower_bound () != 0 || r.upper_bound () == 0)
-    return false;
-  // Check if pointers have any non-null dereferences.
-  if (non_null_deref_p (name, bb, search_dom))
-    {
-      // 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;
-}
-
 // 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
@@ -1014,9 +1004,6 @@ ranger_cache::range_of_def (irange &r, tree name, basic_block bb)
       else
 	r = gimple_range_global (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.
@@ -1034,8 +1021,6 @@ ranger_cache::entry_range (irange &r, tree name, basic_block bb)
   // Otherwise pick up the best available global value.
   if (!m_on_entry.get_bb_range (r, name, bb))
     range_of_def (r, name);
-
-  m_non_null.adjust_range (r, name, bb, false);
 }
 
 // Get the range of NAME as it occurs on exit from block BB.
@@ -1089,6 +1074,9 @@ ranger_cache::range_of_expr (irange &r, tree name, gimple *stmt)
    if (gimple_range_ssa_p (expr))
     {
       exit_range (r, expr, e->src);
+      // If this is not an abnormal edge, check for a non-null exit.
+      if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
+	m_non_null.adjust_range (r, expr, e->src, false);
       int_range_max edge_range;
       if (m_gori.outgoing_edge_range_p (edge_range, e, expr, *this))
 	r.intersect (edge_range);
@@ -1467,3 +1455,82 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block bb)
     }
   return true;
 }
+
+// This routine will update NAME in block BB to the nonnull state.
+// It will then update the on-entry cache for this block to be non-null
+// if it isn't already.
+
+void
+ranger_cache::update_to_nonnull (basic_block bb, tree name)
+{
+  tree type = TREE_TYPE (name);
+  if (gimple_range_ssa_p (name) && POINTER_TYPE_P (type))
+    {
+      m_non_null.set_nonnull (bb, name);
+      // Update the on-entry cache for BB to be non-zero.  Note this can set
+      // the on entry value in the DEF block, which can override the def.
+      int_range_max r;
+      exit_range (r, name, bb);
+      if (r.varying_p ())
+	{
+	  r.set_nonzero (type);
+	  m_on_entry.set_bb_range (name, bb, r);
+	}
+    }
+}
+
+// Adapted from infer_nonnull_range_by_dereference and check_loadstore
+// to process nonnull ssa_name OP in S.  DATA contains the ranger_cache.
+
+static bool
+non_null_loadstore (gimple *s, tree op, tree, void *data)
+{
+  if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
+    {
+      /* Some address spaces may legitimately dereference zero.  */
+      addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op));
+      if (!targetm.addr_space.zero_address_valid (as))
+	{
+	  tree ssa = TREE_OPERAND (op, 0);
+	  basic_block bb = gimple_bb (s);
+	  ((ranger_cache *)data)->update_to_nonnull (bb, ssa);
+	}
+    }
+  return false;
+}
+
+// This routine is used during a block walk to move the state of non-null for
+// any operands on stmt S to nonnull.
+
+void
+ranger_cache::block_apply_nonnull (gimple *s)
+{
+  if (!flag_delete_null_pointer_checks)
+    return;
+  if (is_a<gphi *> (s))
+    return;
+  if (gimple_code (s) == GIMPLE_ASM || gimple_clobber_p (s))
+    return;
+  if (is_a<gcall *> (s))
+    {
+      tree fntype = gimple_call_fntype (s);
+      bitmap nonnullargs = get_nonnull_args (fntype);
+      // Process any non-null arguments
+      if (nonnullargs)
+	{
+	  basic_block bb = gimple_bb (s);
+	  for (unsigned i = 0; i < gimple_call_num_args (s); i++)
+	    {
+	      if (bitmap_empty_p (nonnullargs) || bitmap_bit_p (nonnullargs, i))
+		{
+		  tree op = gimple_call_arg (s, i);
+		  update_to_nonnull (bb, op);
+		}
+	    }
+	  BITMAP_FREE (nonnullargs);
+	}
+      // Fallthru and walk load/store ops now.
+    }
+  walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore,
+			    non_null_loadstore);
+}
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index b54b6882aa8..589b649da26 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -36,12 +36,41 @@ public:
   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);
+  bool set_nonnull (basic_block bb, tree name);
 private:
   vec <bitmap> m_nn;
   void process_name (tree name);
   bitmap_obstack m_bitmaps;
 };
 
+// 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.
+
+inline bool
+non_null_ref::adjust_range (irange &r, tree name, basic_block bb,
+			    bool 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)))
+    return false;
+  if (r.undefined_p () || r.lower_bound () != 0 || r.upper_bound () == 0)
+    return false;
+  // Check if pointers have any non-null dereferences.
+  if (non_null_deref_p (name, bb, search_dom))
+    {
+      // 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;
+}
+
 // This class manages a vector of pointers to ssa_block ranges.  It
 // provides the basis for the "range on entry" cache for all
 // SSA names.
@@ -106,6 +135,8 @@ public:
 
   void propagate_updated_value (tree name, basic_block bb);
 
+  void block_apply_nonnull (gimple *s);
+  void update_to_nonnull (basic_block bb, tree name);
   non_null_ref m_non_null;
   gori_compute m_gori;
 
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 3bf9bd1e981..483bcd2e582 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -358,7 +358,7 @@ path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb)
     }
 
   if (bb)
-    m_non_null.adjust_range (r, name, bb);
+    m_non_null.adjust_range (r, name, bb, false);
 
   if (DEBUG_SOLVER && (bb || !r.varying_p ()))
     {
@@ -528,7 +528,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb)
       else
 	r.set_varying (TREE_TYPE (name));
 
-      if (m_non_null.adjust_range (r, name, bb))
+      if (m_non_null.adjust_range (r, name, bb, false))
 	set_cache (r, name);
     }
 }
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 73398ddef99..04075a98a80 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -35,6 +35,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-scalar-evolution.h"
 #include "gimple-range.h"
 #include "gimple-fold.h"
+#include "gimple-walk.h"
 
 gimple_ranger::gimple_ranger () :
 	non_executable_edge_flag (cfun),
@@ -117,8 +118,10 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
       // If name is defined in this block, try to get an range from S.
       if (def_stmt && gimple_bb (def_stmt) == bb)
 	{
-	  range_of_stmt (r, def_stmt, expr);
-	  m_cache.m_non_null.adjust_range (r, expr, bb, true);
+	  // Check for a definition override from a block walk.
+	  if (!POINTER_TYPE_P (TREE_TYPE (expr))
+	      || !m_cache.block_range (r, bb, expr, false))
+	    range_of_stmt (r, def_stmt, expr);
 	}
       // Otherwise OP comes from outside this block, use range on entry.
       else
@@ -151,7 +154,12 @@ 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);
 
-  m_cache.m_non_null.adjust_range (r, name, bb, true);
+  if (dom_info_available_p (CDI_DOMINATORS))
+    {
+      basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+      if (dom_bb)
+	m_cache.m_non_null.adjust_range (r, name, dom_bb, true);
+    }
 
   if (idx)
     tracer.trailer (idx, "range_on_entry", true, name, r);
@@ -227,6 +235,9 @@ gimple_ranger::range_on_edge (irange &r, edge e, tree name)
   else
     {
       range_on_exit (r, e->src, name);
+      // If this is not an abnormal edge, check for a non-null exit .
+      if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
+	m_cache.m_non_null.adjust_range (r, name, e->src, false);
       gcc_checking_assert  (r.undefined_p ()
 			    || range_compatible_p (r.type(), TREE_TYPE (name)));
 
@@ -436,6 +447,16 @@ gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
   return ret;
 }
 
+// Called during dominator walks to register any side effects that take effect
+// from this point forward.  Current release is only for tracking non-null
+// within a block.
+
+void
+gimple_ranger::register_side_effects (gimple *s)
+{
+  m_cache.block_apply_nonnull (s);
+}
+
 // This routine will export whatever global ranges are known to GCC
 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
 
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index ec568153a8d..0733a534853 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -60,6 +60,7 @@ public:
   void dump_bb (FILE *f, basic_block bb);
   auto_edge_flag non_executable_edge_flag;
   bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree));
+  void register_side_effects (gimple *s);
 protected:
   bool fold_range_internal (irange &r, gimple *s, tree name);
   void prefill_name (irange &r, tree name);
diff --git a/gcc/testsuite/gcc.dg/pr104288.c b/gcc/testsuite/gcc.dg/pr104288.c
new file mode 100644
index 00000000000..95eb196f9e4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr104288.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp -fdelete-null-pointer-checks" } */
+/* { dg-skip-if "" { keeps_null_pointer_checks } } */
+
+void keep(int result) __attribute__((noipa));
+void keep(int result)
+{
+    if (result)
+        __builtin_exit(0);
+}
+
+void foo (void *p) __attribute__((nonnull(1)));
+
+void bar (void *p)
+{
+  keep (p == 0);
+  foo (p);
+  if (!p)
+    __builtin_abort ();
+}
+
+/* { dg-final { scan-tree-dump-not "abort" "evrp" } } */
+/* { dg-final { scan-tree-dump-times  "== 0B;" 1 "evrp" } } */
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 62946450b13..e9f19d0c8b9 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -4309,9 +4309,11 @@ public:
 
   bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
   {
-    if (m_simplifier.simplify (gsi))
-      return true;
-    return m_ranger->fold_stmt (gsi, follow_single_use_edges);
+    bool ret = m_simplifier.simplify (gsi);
+    if (!ret)
+      ret = m_ranger->fold_stmt (gsi, follow_single_use_edges);
+    m_ranger->register_side_effects (gsi_stmt (*gsi));
+    return ret;
   }
 
 private:
-- 
2.17.2

Re: [PATCH V2] tree-optimization/104288 - Register non-null side effects properly.

[Richard Biener]

On Tue, Feb 8, 2022 at 9:58 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 2/8/22 03:32, Richard Biener wrote:
> > On Tue, Feb 8, 2022 at 2:33 AM Andrew MacLeod via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> >> On 2/7/22 09:29, Andrew MacLeod wrote:
> >>> I have a proposal for PR 104288.
> >>>
> >>> ALL patches (in sequence) bootstrap on their own and each cause no
> >>> regressions.
> >> I've been continuing to work with this towards the GCC13 solution for
> >> statement side effects.  And There is another possibility we could
> >> pursue which is less intrusive
> >>
> >> I adapted the portions of patch 2/4 which process nonnull, but changes
> >> it from being in the nonnull class to being in the cache.
> >>
> >> THe main difference is it continues to use a single bit, just changing
> >> all uses of it to *always* mean its non-null on exit to the block.
> >>
> >> Range-on-entry is changed to only check dominator blocks, and
> >> range_of_expr doesn't check the bit at all.. in both ranger and the cache.
> >>
> >> When we are doing the block walk and process side effects, the on-entry
> >> *cache* range for the block is adjusted to be non-null instead.   The
> >> statements which precede this stmt have already been processed, and all
> >> remaining statements in this block will now pick up this new non-value
> >> from the on-entry cache.  This should be perfectly safe.
> >>
> >> The final tweak is when range_of_expr is looking the def block, it
> >> normally does not have an on entry cache value.  (the def is in the
> >> block, so there is no entry cache value).  It now checks to see if we
> >> have set one, which can only happen when we have been doing the
> >> statement walk and set the on-entry cache with  a non-null value.  This
> >> allows us to pick up the non-null range in the def block too... (once we
> >> have passed a statement which set nonnull of course).
> >>
> >> THis patch provides much less change to trunk, and is probably a better
> >> approach as its closer to what is going to happen in GCC13.
> >>
> >> Im still working with it, so the patch isnt fully refined yet... but it
> >> bootstraps and passes all test with no regressions.  And passes the new
> >> tests too.   I figured I would mention this before you look to hard at
> >> the other patchset.    the GCC11 patch doesn't change.
> >>
> >> Let me know if you prefer this.... I think I do :-)  less churn, and
> >> closer to end state.
> > Yes, I very much prefer this - some comments to the other patches
> > still apply to this one.  Like using get_nonnull_args and probably
> > adding a bail-out to computing ranges from stmts that can throw
> > internally or have abnormal control flow (to not get into range-on-exit
> > vs. normal vs. exceptional or abnormal edges).
> >
> > Richard.
>
> with some minor performance tweaks, such as moving adjust_range() to the
> header so it can be inlined .
>
> range-on-edge now applies the non-null from the src block if
> appropriate, not in range-on-exit.   That should resolve  the internal
> throwing statements I think.  and I have switched over to
> get_nonnull_args().
>
> Bootstraps on build-x86_64-pc-linux-gnu and passes all regressions.
>
> OK for trunk, or did I miss something?

OK.

I do think there's some confusion about -fnon-call-exceptions.  The
comment

+  // Non-call exceptions mean we could throw in the middle of the
+  // block, so just punt on those for now.

also applies to regular exceptions, non-call vs. call EH just
adds the possibility of non-call stmts to throw.  I do not think that
value-range propagation needs to care about stmts that throw
in the middle of a block (which automatically means no EH edges
and thus !stmt_can_throw_internal).  When there are EH edges
then restrictions apply to both calls and non-calls that throw.

So whatever made those cfun->can_throw_non_call_exceptions
necessary should have shown a more general issue with EH.

That's something to look at, but not in the scope of this fix.

Richard.

> Andrew
>
> PS. odd.. I haven't seen the git diff be wrong before, but it shows the
> ranger_cache::range_on_edge changes as being in
> gimple_cache::range_of_expr...  They are most definitely are not....
> and it applies/de-applies fine.. so its just an oddity I guess.
>

Re: [PATCH V2] tree-optimization/104288 - Register non-null side effects properly.

[Andrew MacLeod]

On 2/9/22 03:45, Richard Biener wrote:
> On Tue, Feb 8, 2022 at 9:58 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>> On 2/8/22 03:32, Richard Biener wrote:
>>> On Tue, Feb 8, 2022 at 2:33 AM Andrew MacLeod via Gcc-patches
>>> <gcc-patches@gcc.gnu.org> wrote:
>>>> On 2/7/22 09:29, Andrew MacLeod wrote:
>>>>> I have a proposal for PR 104288.
>>>>>
>>>>> ALL patches (in sequence) bootstrap on their own and each cause no
>>>>> regressions.
>>>> I've been continuing to work with this towards the GCC13 solution for
>>>> statement side effects.  And There is another possibility we could
>>>> pursue which is less intrusive
>>>>
>>>> I adapted the portions of patch 2/4 which process nonnull, but changes
>>>> it from being in the nonnull class to being in the cache.
>>>>
>>>> THe main difference is it continues to use a single bit, just changing
>>>> all uses of it to *always* mean its non-null on exit to the block.
>>>>
>>>> Range-on-entry is changed to only check dominator blocks, and
>>>> range_of_expr doesn't check the bit at all.. in both ranger and the cache.
>>>>
>>>> When we are doing the block walk and process side effects, the on-entry
>>>> *cache* range for the block is adjusted to be non-null instead.   The
>>>> statements which precede this stmt have already been processed, and all
>>>> remaining statements in this block will now pick up this new non-value
>>>> from the on-entry cache.  This should be perfectly safe.
>>>>
>>>> The final tweak is when range_of_expr is looking the def block, it
>>>> normally does not have an on entry cache value.  (the def is in the
>>>> block, so there is no entry cache value).  It now checks to see if we
>>>> have set one, which can only happen when we have been doing the
>>>> statement walk and set the on-entry cache with  a non-null value.  This
>>>> allows us to pick up the non-null range in the def block too... (once we
>>>> have passed a statement which set nonnull of course).
>>>>
>>>> THis patch provides much less change to trunk, and is probably a better
>>>> approach as its closer to what is going to happen in GCC13.
>>>>
>>>> Im still working with it, so the patch isnt fully refined yet... but it
>>>> bootstraps and passes all test with no regressions.  And passes the new
>>>> tests too.   I figured I would mention this before you look to hard at
>>>> the other patchset.    the GCC11 patch doesn't change.
>>>>
>>>> Let me know if you prefer this.... I think I do :-)  less churn, and
>>>> closer to end state.
>>> Yes, I very much prefer this - some comments to the other patches
>>> still apply to this one.  Like using get_nonnull_args and probably
>>> adding a bail-out to computing ranges from stmts that can throw
>>> internally or have abnormal control flow (to not get into range-on-exit
>>> vs. normal vs. exceptional or abnormal edges).
>>>
>>> Richard.
>> with some minor performance tweaks, such as moving adjust_range() to the
>> header so it can be inlined .
>>
>> range-on-edge now applies the non-null from the src block if
>> appropriate, not in range-on-exit.   That should resolve  the internal
>> throwing statements I think.  and I have switched over to
>> get_nonnull_args().
>>
>> Bootstraps on build-x86_64-pc-linux-gnu and passes all regressions.
>>
>> OK for trunk, or did I miss something?
> OK.
>
> I do think there's some confusion about -fnon-call-exceptions.  The
> comment
>
> +  // Non-call exceptions mean we could throw in the middle of the
> +  // block, so just punt on those for now.
>
> also applies to regular exceptions, non-call vs. call EH just
> adds the possibility of non-call stmts to throw.  I do not think that
> value-range propagation needs to care about stmts that throw
> in the middle of a block (which automatically means no EH edges
> and thus !stmt_can_throw_internal).  When there are EH edges
> then restrictions apply to both calls and non-calls that throw.
>
> So whatever made those cfun->can_throw_non_call_exceptions
> necessary should have shown a more general issue with EH.

its probably paranoid carry over from a few years ago when getting off 
the ground, combined with the non-null bit originally applying to the 
entire block.

With these changes, and adjusting the outgoing values only on 
non-abnormal/EH edge, I suspect they are no longer needed.  I will look 
at pulling them all out for the next release.



>
> That's something to look at, but not in the scope of this fix.
>
> Richard.
>
>> Andrew
>>
>> PS. odd.. I haven't seen the git diff be wrong before, but it shows the
>> ranger_cache::range_on_edge changes as being in
>> gimple_cache::range_of_expr...  They are most definitely are not....
>> and it applies/de-applies fine.. so its just an oddity I guess.
>>