[PATCH 1/2] Avoid random stmt order result in pass_waccess::use_after_inval_p

[PATCH 1/2] Avoid random stmt order result in pass_waccess::use_after_inval_p

[Richard Biener]

use_after_inval_p uses stmt UIDs to speed up repeated dominance
checks within a basic-block but it fails to assign UIDs to PHIs
which means compares with PHIs in the same block get a random
result.

The following factors renumber_gimple_stmt_uids to expose a new
renumber_gimple_stmt_uids_in_block we can share.

This XFAILs the conditional loop case in gcc.dg/Wuse-after-free-2.c

Bootstrap and regtest running on x86_64-unknown-linux-gnu.  This
makes 2/2 a net positive on the testsuite (the early waccess
would not run into this bug)

OK if testing succeeds?  (we could also special-case PHIs somehow
and assert we never get to compare two PHIs here)

	* tree-dfa.h (renumber_gimple_stmt_uids_in_block): New.
	* tree-dfa.cc (renumber_gimple_stmt_uids_in_block): Split
	out from ...
	(renumber_gimple_stmt_uids): ... here and
	(renumber_gimple_stmt_uids_in_blocks): ... here.
	* gimple-ssa-warn-access.cc (pass_waccess::use_after_inval_p):
	Use renumber_gimple_stmt_uids_in_block to also assign UIDs
	to PHIs.

	* gcc.dg/Wuse-after-free-2.c: XFAIL conditional loop case.
---
 gcc/gimple-ssa-warn-access.cc            |  8 +---
 gcc/testsuite/gcc.dg/Wuse-after-free-2.c |  4 +-
 gcc/tree-dfa.cc                          | 48 +++++++++++-------------
 gcc/tree-dfa.h                           |  1 +
 4 files changed, 25 insertions(+), 36 deletions(-)

diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc
index 8b1c1cc019e..a8ad7a6df65 100644
--- a/gcc/gimple-ssa-warn-access.cc
+++ b/gcc/gimple-ssa-warn-access.cc
@@ -3862,13 +3862,7 @@ pass_waccess::use_after_inval_p (gimple *inval_stmt, gimple *use_stmt,
        to consecutive statements in it.  Use the ids to determine which
        precedes which.  This avoids the linear traversal on subsequent
        visits to the same block.  */
-    for (auto si = gsi_start_bb (inval_bb); !gsi_end_p (si);
-	 gsi_next_nondebug (&si))
-      {
-	gimple *stmt = gsi_stmt (si);
-	unsigned uid = inc_gimple_stmt_max_uid (m_func);
-	gimple_set_uid (stmt, uid);
-      }
+    renumber_gimple_stmt_uids_in_block (m_func, inval_bb);
 
   return gimple_uid (inval_stmt) < gimple_uid (use_stmt);
 }
diff --git a/gcc/testsuite/gcc.dg/Wuse-after-free-2.c b/gcc/testsuite/gcc.dg/Wuse-after-free-2.c
index ebc051690db..cd5c43c0fa3 100644
--- a/gcc/testsuite/gcc.dg/Wuse-after-free-2.c
+++ b/gcc/testsuite/gcc.dg/Wuse-after-free-2.c
@@ -113,6 +113,6 @@ int warn_cond_loop (char *p)
   while (*q)
     ++q;
 
-  free (p);         // { dg-message "call to 'free'" }
-  return *q;        // { dg-warning "pointer 'q' used after 'free'" }
+  free (p);         // dg-message "call to 'free'"
+  return *q;        // { dg-warning "pointer 'q' used after 'free'" "" { xfail *-*-* } }
 }
diff --git a/gcc/tree-dfa.cc b/gcc/tree-dfa.cc
index ec8df0d6401..82803a8ccb1 100644
--- a/gcc/tree-dfa.cc
+++ b/gcc/tree-dfa.cc
@@ -59,6 +59,25 @@ static void collect_dfa_stats (struct dfa_stats_d *);
 			Dataflow analysis (DFA) routines
 ---------------------------------------------------------------------------*/
 
+/* Renumber the gimple stmt uids in one block.  The caller is responsible
+   of calling set_gimple_stmt_max_uid (fun, 0) at some point.  */
+
+void
+renumber_gimple_stmt_uids_in_block (struct function *fun, basic_block bb)
+{
+  gimple_stmt_iterator bsi;
+  for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+    {
+      gimple *stmt = gsi_stmt (bsi);
+      gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
+    }
+  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+    {
+      gimple *stmt = gsi_stmt (bsi);
+      gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
+    }
+}
+
 /* Renumber all of the gimple stmt uids.  */
 
 void
@@ -68,19 +87,7 @@ renumber_gimple_stmt_uids (struct function *fun)
 
   set_gimple_stmt_max_uid (fun, 0);
   FOR_ALL_BB_FN (bb, fun)
-    {
-      gimple_stmt_iterator bsi;
-      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	{
-	  gimple *stmt = gsi_stmt (bsi);
-	  gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
-	}
-      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	{
-	  gimple *stmt = gsi_stmt (bsi);
-	  gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
-	}
-    }
+    renumber_gimple_stmt_uids_in_block (fun, bb);
 }
 
 /* Like renumber_gimple_stmt_uids, but only do work on the basic blocks
@@ -93,20 +100,7 @@ renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks)
 
   set_gimple_stmt_max_uid (cfun, 0);
   for (i = 0; i < n_blocks; i++)
-    {
-      basic_block bb = blocks[i];
-      gimple_stmt_iterator bsi;
-      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	{
-	  gimple *stmt = gsi_stmt (bsi);
-	  gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
-	}
-      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	{
-	  gimple *stmt = gsi_stmt (bsi);
-	  gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
-	}
-    }
+    renumber_gimple_stmt_uids_in_block (cfun, blocks[i]);
 }
 
 
diff --git a/gcc/tree-dfa.h b/gcc/tree-dfa.h
index 1632487c3ed..074a4da3a6c 100644
--- a/gcc/tree-dfa.h
+++ b/gcc/tree-dfa.h
@@ -20,6 +20,7 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_TREE_DFA_H
 #define GCC_TREE_DFA_H
 
+extern void renumber_gimple_stmt_uids_in_block (struct function *, basic_block);
 extern void renumber_gimple_stmt_uids (struct function *);
 extern void renumber_gimple_stmt_uids_in_blocks (basic_block *, int);
 extern void dump_variable (FILE *, tree);
-- 
2.35.3

Re: [PATCH 1/2] Avoid random stmt order result in pass_waccess::use_after_inval_p

[Jakub Jelinek]

On Wed, Mar 15, 2023 at 01:07:56PM +0000, Richard Biener wrote:
> The following patch was bootstrapped and tested on 
> x86_64-unknown-linux-gnu.  It now doesn't regress anything in the
> testsuite but on its own it has the chance to (by luck maybe
> avoided previosuly due to the PHI compare bug) introduce extra
> false-positives.  Fixing only the comparison causes false negatives
> in the testsuite - as said we rely on processing PHIs before the
> invalidation stmt.
> 
> Together with the second patch I'm confident the overall experience
> will be better than what we have now.
> 
> OK?

LGTM.

	Jakub

Re: [PATCH 1/2] Avoid random stmt order result in pass_waccess::use_after_inval_p

[Richard Biener]

On Wed, 15 Mar 2023, Richard Biener wrote:

> On Wed, 15 Mar 2023, Jakub Jelinek wrote:
> 
> > On Wed, Mar 15, 2023 at 10:48:32AM +0000, Richard Biener wrote:
> > > use_after_inval_p uses stmt UIDs to speed up repeated dominance
> > > checks within a basic-block but it fails to assign UIDs to PHIs
> > > which means compares with PHIs in the same block get a random
> > > result.
> > > 
> > > The following factors renumber_gimple_stmt_uids to expose a new
> > > renumber_gimple_stmt_uids_in_block we can share.
> > > 
> > > This XFAILs the conditional loop case in gcc.dg/Wuse-after-free-2.c
> > > 
> > > Bootstrap and regtest running on x86_64-unknown-linux-gnu.  This
> > > makes 2/2 a net positive on the testsuite (the early waccess
> > > would not run into this bug)
> > > 
> > > OK if testing succeeds?  (we could also special-case PHIs somehow
> > > and assert we never get to compare two PHIs here)
> > > 
> > > 	* tree-dfa.h (renumber_gimple_stmt_uids_in_block): New.
> > > 	* tree-dfa.cc (renumber_gimple_stmt_uids_in_block): Split
> > > 	out from ...
> > > 	(renumber_gimple_stmt_uids): ... here and
> > > 	(renumber_gimple_stmt_uids_in_blocks): ... here.
> > > 	* gimple-ssa-warn-access.cc (pass_waccess::use_after_inval_p):
> > > 	Use renumber_gimple_stmt_uids_in_block to also assign UIDs
> > > 	to PHIs.
> > > 
> > > 	* gcc.dg/Wuse-after-free-2.c: XFAIL conditional loop case.
> > 
> > LGTM.
> 
> Turns out we rely very much on processing PHIs for following pointers
> (we also happily look at earlier pointer adjustments).  So while the
> comparison done to PHIs in the above function is bogus and we should
> possibly fix it it regresses things unless we process PHIs
> unconditionally.
> 
> I'm going to test an adjusted patch.

The following patch was bootstrapped and tested on 
x86_64-unknown-linux-gnu.  It now doesn't regress anything in the
testsuite but on its own it has the chance to (by luck maybe
avoided previosuly due to the PHI compare bug) introduce extra
false-positives.  Fixing only the comparison causes false negatives
in the testsuite - as said we rely on processing PHIs before the
invalidation stmt.

Together with the second patch I'm confident the overall experience
will be better than what we have now.

OK?

Thanks,
Richard.



From 4077971e24c6be2ee2b3266701f6ca14a6ce3d4b Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Wed, 15 Mar 2023 11:41:20 +0100
Subject: [PATCH] Avoid random stmt order result in
 pass_waccess::use_after_inval_p
To: gcc-patches@gcc.gnu.org

use_after_inval_p uses stmt UIDs to speed up repeated dominance
checks within a basic-block but it fails to assign UIDs to PHIs
which means compares with PHIs in the same block get a random
result.

The following factors renumber_gimple_stmt_uids to expose a new
renumber_gimple_stmt_uids_in_block we can share.

But since we rely on processing even earlier PHIs to follow
pointer adjustments (we look at those even if earlier) the patch
also moves PHI handling out of the use_after_inval_p guard.
This then also fixes PR109141.

	PR tree-optimizaton/109141
	* tree-dfa.h (renumber_gimple_stmt_uids_in_block): New.
	* tree-dfa.cc (renumber_gimple_stmt_uids_in_block): Split
	out from ...
	(renumber_gimple_stmt_uids): ... here and
	(renumber_gimple_stmt_uids_in_blocks): ... here.
	* gimple-ssa-warn-access.cc (pass_waccess::use_after_inval_p):
	Use renumber_gimple_stmt_uids_in_block to also assign UIDs
	to PHIs.
	(pass_waccess::check_pointer_uses): Process all PHIs.
---
 gcc/gimple-ssa-warn-access.cc | 37 +++++++++++----------------
 gcc/tree-dfa.cc               | 48 +++++++++++++++--------------------
 gcc/tree-dfa.h                |  1 +
 3 files changed, 37 insertions(+), 49 deletions(-)

diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc
index 8b1c1cc019e..daaa22882fa 100644
--- a/gcc/gimple-ssa-warn-access.cc
+++ b/gcc/gimple-ssa-warn-access.cc
@@ -3862,13 +3862,7 @@ pass_waccess::use_after_inval_p (gimple *inval_stmt, gimple *use_stmt,
        to consecutive statements in it.  Use the ids to determine which
        precedes which.  This avoids the linear traversal on subsequent
        visits to the same block.  */
-    for (auto si = gsi_start_bb (inval_bb); !gsi_end_p (si);
-	 gsi_next_nondebug (&si))
-      {
-	gimple *stmt = gsi_stmt (si);
-	unsigned uid = inc_gimple_stmt_max_uid (m_func);
-	gimple_set_uid (stmt, uid);
-      }
+    renumber_gimple_stmt_uids_in_block (m_func, inval_bb);
 
   return gimple_uid (inval_stmt) < gimple_uid (use_stmt);
 }
@@ -4235,27 +4229,26 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr,
 	      tree_code code = gimple_cond_code (cond);
 	      equality = code == EQ_EXPR || code == NE_EXPR;
 	    }
+	  else if (gimple_code (use_stmt) == GIMPLE_PHI)
+	    {
+	      /* Only add a PHI result to POINTERS if all its
+		 operands are related to PTR, otherwise continue.  */
+	      tree lhs = gimple_phi_result (use_stmt);
+	      if (!pointers_related_p (stmt, lhs, ptr, m_ptr_qry))
+		continue;
+
+	      if (TREE_CODE (lhs) == SSA_NAME)
+		{
+		  pointers.safe_push (lhs);
+		  continue;
+		}
+	    }
 
 	  /* Warn if USE_STMT is dominated by the deallocation STMT.
 	     Otherwise, add the pointer to POINTERS so that the uses
 	     of any other pointers derived from it can be checked.  */
 	  if (use_after_inval_p (stmt, use_stmt, check_dangling))
 	    {
-	      if (gimple_code (use_stmt) == GIMPLE_PHI)
-		{
-		  /* Only add a PHI result to POINTERS if all its
-		     operands are related to PTR, otherwise continue.  */
-		  tree lhs = gimple_phi_result (use_stmt);
-		  if (!pointers_related_p (stmt, lhs, ptr, m_ptr_qry))
-		    continue;
-
-		  if (TREE_CODE (lhs) == SSA_NAME)
-		    {
-		      pointers.safe_push (lhs);
-		      continue;
-		    }
-		}
-
 	      basic_block use_bb = gimple_bb (use_stmt);
 	      bool this_maybe
 		= (maybe
diff --git a/gcc/tree-dfa.cc b/gcc/tree-dfa.cc
index ec8df0d6401..82803a8ccb1 100644
--- a/gcc/tree-dfa.cc
+++ b/gcc/tree-dfa.cc
@@ -59,6 +59,25 @@ static void collect_dfa_stats (struct dfa_stats_d *);
 			Dataflow analysis (DFA) routines
 ---------------------------------------------------------------------------*/
 
+/* Renumber the gimple stmt uids in one block.  The caller is responsible
+   of calling set_gimple_stmt_max_uid (fun, 0) at some point.  */
+
+void
+renumber_gimple_stmt_uids_in_block (struct function *fun, basic_block bb)
+{
+  gimple_stmt_iterator bsi;
+  for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+    {
+      gimple *stmt = gsi_stmt (bsi);
+      gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
+    }
+  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+    {
+      gimple *stmt = gsi_stmt (bsi);
+      gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
+    }
+}
+
 /* Renumber all of the gimple stmt uids.  */
 
 void
@@ -68,19 +87,7 @@ renumber_gimple_stmt_uids (struct function *fun)
 
   set_gimple_stmt_max_uid (fun, 0);
   FOR_ALL_BB_FN (bb, fun)
-    {
-      gimple_stmt_iterator bsi;
-      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	{
-	  gimple *stmt = gsi_stmt (bsi);
-	  gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
-	}
-      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	{
-	  gimple *stmt = gsi_stmt (bsi);
-	  gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
-	}
-    }
+    renumber_gimple_stmt_uids_in_block (fun, bb);
 }
 
 /* Like renumber_gimple_stmt_uids, but only do work on the basic blocks
@@ -93,20 +100,7 @@ renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks)
 
   set_gimple_stmt_max_uid (cfun, 0);
   for (i = 0; i < n_blocks; i++)
-    {
-      basic_block bb = blocks[i];
-      gimple_stmt_iterator bsi;
-      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	{
-	  gimple *stmt = gsi_stmt (bsi);
-	  gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
-	}
-      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	{
-	  gimple *stmt = gsi_stmt (bsi);
-	  gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
-	}
-    }
+    renumber_gimple_stmt_uids_in_block (cfun, blocks[i]);
 }
 
 
diff --git a/gcc/tree-dfa.h b/gcc/tree-dfa.h
index 1632487c3ed..074a4da3a6c 100644
--- a/gcc/tree-dfa.h
+++ b/gcc/tree-dfa.h
@@ -20,6 +20,7 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_TREE_DFA_H
 #define GCC_TREE_DFA_H
 
+extern void renumber_gimple_stmt_uids_in_block (struct function *, basic_block);
 extern void renumber_gimple_stmt_uids (struct function *);
 extern void renumber_gimple_stmt_uids_in_blocks (basic_block *, int);
 extern void dump_variable (FILE *, tree);
-- 
2.35.3

Re: [PATCH 1/2] Avoid random stmt order result in pass_waccess::use_after_inval_p

[Richard Biener]

On Wed, 15 Mar 2023, Jakub Jelinek wrote:

> On Wed, Mar 15, 2023 at 10:48:32AM +0000, Richard Biener wrote:
> > use_after_inval_p uses stmt UIDs to speed up repeated dominance
> > checks within a basic-block but it fails to assign UIDs to PHIs
> > which means compares with PHIs in the same block get a random
> > result.
> > 
> > The following factors renumber_gimple_stmt_uids to expose a new
> > renumber_gimple_stmt_uids_in_block we can share.
> > 
> > This XFAILs the conditional loop case in gcc.dg/Wuse-after-free-2.c
> > 
> > Bootstrap and regtest running on x86_64-unknown-linux-gnu.  This
> > makes 2/2 a net positive on the testsuite (the early waccess
> > would not run into this bug)
> > 
> > OK if testing succeeds?  (we could also special-case PHIs somehow
> > and assert we never get to compare two PHIs here)
> > 
> > 	* tree-dfa.h (renumber_gimple_stmt_uids_in_block): New.
> > 	* tree-dfa.cc (renumber_gimple_stmt_uids_in_block): Split
> > 	out from ...
> > 	(renumber_gimple_stmt_uids): ... here and
> > 	(renumber_gimple_stmt_uids_in_blocks): ... here.
> > 	* gimple-ssa-warn-access.cc (pass_waccess::use_after_inval_p):
> > 	Use renumber_gimple_stmt_uids_in_block to also assign UIDs
> > 	to PHIs.
> > 
> > 	* gcc.dg/Wuse-after-free-2.c: XFAIL conditional loop case.
> 
> LGTM.

Turns out we rely very much on processing PHIs for following pointers
(we also happily look at earlier pointer adjustments).  So while the
comparison done to PHIs in the above function is bogus and we should
possibly fix it it regresses things unless we process PHIs
unconditionally.

I'm going to test an adjusted patch.

Richard.

Re: [PATCH 1/2] Avoid random stmt order result in pass_waccess::use_after_inval_p

[Jakub Jelinek]

On Wed, Mar 15, 2023 at 10:48:32AM +0000, Richard Biener wrote:
> use_after_inval_p uses stmt UIDs to speed up repeated dominance
> checks within a basic-block but it fails to assign UIDs to PHIs
> which means compares with PHIs in the same block get a random
> result.
> 
> The following factors renumber_gimple_stmt_uids to expose a new
> renumber_gimple_stmt_uids_in_block we can share.
> 
> This XFAILs the conditional loop case in gcc.dg/Wuse-after-free-2.c
> 
> Bootstrap and regtest running on x86_64-unknown-linux-gnu.  This
> makes 2/2 a net positive on the testsuite (the early waccess
> would not run into this bug)
> 
> OK if testing succeeds?  (we could also special-case PHIs somehow
> and assert we never get to compare two PHIs here)
> 
> 	* tree-dfa.h (renumber_gimple_stmt_uids_in_block): New.
> 	* tree-dfa.cc (renumber_gimple_stmt_uids_in_block): Split
> 	out from ...
> 	(renumber_gimple_stmt_uids): ... here and
> 	(renumber_gimple_stmt_uids_in_blocks): ... here.
> 	* gimple-ssa-warn-access.cc (pass_waccess::use_after_inval_p):
> 	Use renumber_gimple_stmt_uids_in_block to also assign UIDs
> 	to PHIs.
> 
> 	* gcc.dg/Wuse-after-free-2.c: XFAIL conditional loop case.

LGTM.

	Jakub