diff mbox series

tree-optimization/93586 - bogus path-based disambiguation

Message ID nycvar.YFH.7.76.2002171416580.5137@zhemvz.fhfr.qr
State New
Headers show
Series tree-optimization/93586 - bogus path-based disambiguation | expand

Commit Message

Richard Biener Feb. 17, 2020, 1:17 p.m. UTC 
This fixes bogus path-based disambiguation of mismatched array shape
accesses.

Bootstrap & regtest running on x86_64-unknown-linux-gnu.

Honza, is this the correct place to detect this or were we not
supposed to arrive there?

Thanks,
Richard.

2020-02-17  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/93586
	* tree-ssa-alias.c (nonoverlapping_array_refs_p): Fail when
	we're obviously not looking at same-shaped array accesses.

	* gcc.dg/torture/pr93586.c: New testcase.
---
 gcc/testsuite/gcc.dg/torture/pr93586.c | 21 +++++++++++++++++++++
 gcc/tree-ssa-alias.c                   |  5 +++++
 2 files changed, 26 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/torture/pr93586.c

Comments

Jan Hubicka Feb. 20, 2020, 3:58 p.m. UTC | #1 
> This fixes bogus path-based disambiguation of mismatched array shape
> accesses.
> 
> Bootstrap & regtest running on x86_64-unknown-linux-gnu.
> 
> Honza, is this the correct place to detect this or were we not
> supposed to arrive there?
> 
> Thanks,
> Richard.
> 
> 2020-02-17  Richard Biener  <rguenther@suse.de>
> 
> 	PR tree-optimization/93586
> 	* tree-ssa-alias.c (nonoverlapping_array_refs_p): Fail when
> 	we're obviously not looking at same-shaped array accesses.
> 
> 	* gcc.dg/torture/pr93586.c: New testcase.
> ---
>  gcc/testsuite/gcc.dg/torture/pr93586.c | 21 +++++++++++++++++++++
>  gcc/tree-ssa-alias.c                   |  5 +++++
>  2 files changed, 26 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/torture/pr93586.c
> 
> diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
> index b8df66ac1f2..e7caf9bee77 100644
> --- a/gcc/tree-ssa-alias.c
> +++ b/gcc/tree-ssa-alias.c
> @@ -1291,6 +1291,11 @@ nonoverlapping_array_refs_p (tree ref1, tree ref2)
>  
>    tree elmt_type1 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref1, 0)));
>    tree elmt_type2 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref2, 0)));
> +  /* If one element is an array but not the other there's an obvious
> +     mismatch in dimensionality.  */
> +  if ((TREE_CODE (elmt_type1) == ARRAY_TYPE)
> +      != (TREE_CODE (elmt_type2) == ARRAY_TYPE))
> +    return -1;

The problem happens earlier.  The function is not supposed to give
meaningful results when bases of ref1 and ref2 are not same or
completely disjoint and here it is called on c[0][j_2][0] and c[0][1] so
bases in sence of this functions are "c[0][j_2]" and "c[0]" which do
partially overlap.

The problem is in nonoverlapping_array_refs that walks
pair of array references and in this case it misses to note the fact
that if it walked across first mismatched pair it is no longer safe to
compare rest.

The reason why it continues matching is because it hopes it will
eventually get pair of COMPONENT_REFs from types of same size and use
TBAA to conclude that their addresses must be either same or completely
disjoint.

This patch makes the loop to terminate early but popping all the
remaining pairs so walking can continue.  We could re-synchronize on
arrays of same size with TBAA but this is bit fishy (because we try to
support some sort of partial array overlaps) and hard to implement
(because of zero sized arrays and VLAs) so I think it is not worth the
effort.

In addition I notied that the function is not !flag_strict_aliasing safe
and added early exits on places we set seen_unmatched_ref_p since later
we do not check that in:

       /* If we skipped array refs on type of different sizes, we can
 	 no longer be sure that there are not partial overlaps.  */
       if (seen_unmatched_ref_p
 	  && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
 	{
 	  ++alias_stats
 	    .nonoverlapping_refs_since_match_p_may_alias;
	}

Bootstrapped/regtested ppc64-linux, OK?

	* tree-ssa-alias.c (nonoverlapping_array_refs_p): Finish array walk
	after mismatched array refs; do not sure type size information to
	recover from unmatched referneces with !flag_strict_aliasing_p.
	* gcc.dg/torture/pr93586.c: New testcase.
diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
index fd78105..8509f75 100644
--- a/gcc/tree-ssa-alias.c
+++ b/gcc/tree-ssa-alias.c
@@ -1486,9 +1489,27 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
 		    .nonoverlapping_refs_since_match_p_no_alias;
 		  return 1;
 		}
-	      partial_overlap = false;
 	      if (cmp == -1)
-		seen_unmatched_ref_p = true;
+		{
+		  seen_unmatched_ref_p = true;
+		  /* We can not maintain the invariant that bases are either
+		     same or completely disjoint.  However we can still recover
+		     from type based alias analysis if we reach referneces to
+		     same sizes.  We do not attempt to match array sizes, so
+		     just finish array walking and look for component refs.  */
+		  if (!flag_strict_aliasing)
+		    {
+		      ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
+		      return -1;
+		    }
+		  for (i++; i < narray_refs1; i++)
+		    {
+		      component_refs1.pop ();
+		      component_refs2.pop ();
+		    }
+		  break;
+		}
+	      partial_overlap = false;
 	    }
 	}
 
@@ -1503,7 +1524,14 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
 	    }
 	  ref1 = component_refs1.pop ();
 	  if (TREE_CODE (ref1) != COMPONENT_REF)
-	    seen_unmatched_ref_p = true;
+	    {
+	      seen_unmatched_ref_p = true;
+	      if (!flag_strict_aliasing)
+		{
+		  ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
+		  return -1;
+		}
+	    }
 	}
       while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0))));
 
@@ -1517,7 +1545,14 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
 	    }
 	  ref2 = component_refs2.pop ();
 	  if (TREE_CODE (ref2) != COMPONENT_REF)
-	    seen_unmatched_ref_p = true;
+	    {
+	      if (!flag_strict_aliasing)
+		{
+		  ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
+		  return -1;
+		}
+	      seen_unmatched_ref_p = true;
+	    }
 	}
       while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0))));
 
@@ -1537,10 +1572,10 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
 
       partial_overlap = false;
 
+      gcc_checking_assert (!seen_unmatched_ref_p || flag_strict_aliasing);
+
       /* If we skipped array refs on type of different sizes, we can
 	 no longer be sure that there are not partial overlaps.  */
       if (seen_unmatched_ref_p
 	  && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
 	{
 	  ++alias_stats
 	    .nonoverlapping_refs_since_match_p_may_alias;
diff --git a/gcc/testsuite/gcc.dg/torture/pr93586.c b/gcc/testsuite/gcc.dg/torture/pr93586.c
new file mode 100644
index 00000000000..e861bdcd78e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr93586.c
@@ -0,0 +1,21 @@
+/* { dg-do run } */
+/* { dg-additional-options "-fgimple" } */
+
+int __GIMPLE(ssa) foo(int j)
+{
+  int c[1][10][1];
+  int _1;
+
+__BB(2):
+  c[0][1][0] = 1;
+  c[0][1] = _Literal (int[1]) {};
+  _1 = c[0][j_2(D)][0];
+  return _1;
+}
+
+int main()
+{
+  if (foo (1) != 0)
+    __builtin_abort ();
+  return 0;
+}
Richard Biener Feb. 21, 2020, 9:21 a.m. UTC | #2 
On Thu, 20 Feb 2020, Jan Hubicka wrote:

> > This fixes bogus path-based disambiguation of mismatched array shape
> > accesses.
> > 
> > Bootstrap & regtest running on x86_64-unknown-linux-gnu.
> > 
> > Honza, is this the correct place to detect this or were we not
> > supposed to arrive there?
> > 
> > Thanks,
> > Richard.
> > 
> > 2020-02-17  Richard Biener  <rguenther@suse.de>
> > 
> > 	PR tree-optimization/93586
> > 	* tree-ssa-alias.c (nonoverlapping_array_refs_p): Fail when
> > 	we're obviously not looking at same-shaped array accesses.
> > 
> > 	* gcc.dg/torture/pr93586.c: New testcase.
> > ---
> >  gcc/testsuite/gcc.dg/torture/pr93586.c | 21 +++++++++++++++++++++
> >  gcc/tree-ssa-alias.c                   |  5 +++++
> >  2 files changed, 26 insertions(+)
> >  create mode 100644 gcc/testsuite/gcc.dg/torture/pr93586.c
> > 
> > diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
> > index b8df66ac1f2..e7caf9bee77 100644
> > --- a/gcc/tree-ssa-alias.c
> > +++ b/gcc/tree-ssa-alias.c
> > @@ -1291,6 +1291,11 @@ nonoverlapping_array_refs_p (tree ref1, tree ref2)
> >  
> >    tree elmt_type1 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref1, 0)));
> >    tree elmt_type2 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref2, 0)));
> > +  /* If one element is an array but not the other there's an obvious
> > +     mismatch in dimensionality.  */
> > +  if ((TREE_CODE (elmt_type1) == ARRAY_TYPE)
> > +      != (TREE_CODE (elmt_type2) == ARRAY_TYPE))
> > +    return -1;
> 
> The problem happens earlier.  The function is not supposed to give
> meaningful results when bases of ref1 and ref2 are not same or
> completely disjoint and here it is called on c[0][j_2][0] and c[0][1] so
> bases in sence of this functions are "c[0][j_2]" and "c[0]" which do
> partially overlap.
> 
> The problem is in nonoverlapping_array_refs that walks
> pair of array references and in this case it misses to note the fact
> that if it walked across first mismatched pair it is no longer safe to
> compare rest.
> 
> The reason why it continues matching is because it hopes it will
> eventually get pair of COMPONENT_REFs from types of same size and use
> TBAA to conclude that their addresses must be either same or completely
> disjoint.
> 
> This patch makes the loop to terminate early but popping all the
> remaining pairs so walking can continue.  We could re-synchronize on
> arrays of same size with TBAA but this is bit fishy (because we try to
> support some sort of partial array overlaps) and hard to implement
> (because of zero sized arrays and VLAs) so I think it is not worth the
> effort.
> 
> In addition I notied that the function is not !flag_strict_aliasing safe
> and added early exits on places we set seen_unmatched_ref_p since later
> we do not check that in:
> 
>        /* If we skipped array refs on type of different sizes, we can
>  	 no longer be sure that there are not partial overlaps.  */
>        if (seen_unmatched_ref_p
>  	  && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
>  	{
>  	  ++alias_stats
>  	    .nonoverlapping_refs_since_match_p_may_alias;
> 	}
> 
> Bootstrapped/regtested ppc64-linux, OK?

OK.

Thanks,
Richard.

> 	* tree-ssa-alias.c (nonoverlapping_array_refs_p): Finish array walk
> 	after mismatched array refs; do not sure type size information to
> 	recover from unmatched referneces with !flag_strict_aliasing_p.
> 	* gcc.dg/torture/pr93586.c: New testcase.
> diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
> index fd78105..8509f75 100644
> --- a/gcc/tree-ssa-alias.c
> +++ b/gcc/tree-ssa-alias.c
> @@ -1486,9 +1489,27 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  		    .nonoverlapping_refs_since_match_p_no_alias;
>  		  return 1;
>  		}
> -	      partial_overlap = false;
>  	      if (cmp == -1)
> -		seen_unmatched_ref_p = true;
> +		{
> +		  seen_unmatched_ref_p = true;
> +		  /* We can not maintain the invariant that bases are either
> +		     same or completely disjoint.  However we can still recover
> +		     from type based alias analysis if we reach referneces to
> +		     same sizes.  We do not attempt to match array sizes, so
> +		     just finish array walking and look for component refs.  */
> +		  if (!flag_strict_aliasing)
> +		    {
> +		      ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
> +		      return -1;
> +		    }
> +		  for (i++; i < narray_refs1; i++)
> +		    {
> +		      component_refs1.pop ();
> +		      component_refs2.pop ();
> +		    }
> +		  break;
> +		}
> +	      partial_overlap = false;
>  	    }
>  	}
>  
> @@ -1503,7 +1524,14 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  	    }
>  	  ref1 = component_refs1.pop ();
>  	  if (TREE_CODE (ref1) != COMPONENT_REF)
> -	    seen_unmatched_ref_p = true;
> +	    {
> +	      seen_unmatched_ref_p = true;
> +	      if (!flag_strict_aliasing)
> +		{
> +		  ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
> +		  return -1;
> +		}
> +	    }
>  	}
>        while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0))));
>  
> @@ -1517,7 +1545,14 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  	    }
>  	  ref2 = component_refs2.pop ();
>  	  if (TREE_CODE (ref2) != COMPONENT_REF)
> -	    seen_unmatched_ref_p = true;
> +	    {
> +	      if (!flag_strict_aliasing)
> +		{
> +		  ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
> +		  return -1;
> +		}
> +	      seen_unmatched_ref_p = true;
> +	    }
>  	}
>        while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0))));
>  
> @@ -1537,10 +1572,10 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  
>        partial_overlap = false;
>  
> +      gcc_checking_assert (!seen_unmatched_ref_p || flag_strict_aliasing);
> +
>        /* If we skipped array refs on type of different sizes, we can
>  	 no longer be sure that there are not partial overlaps.  */
>        if (seen_unmatched_ref_p
>  	  && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
>  	{
>  	  ++alias_stats
>  	    .nonoverlapping_refs_since_match_p_may_alias;
> diff --git a/gcc/testsuite/gcc.dg/torture/pr93586.c b/gcc/testsuite/gcc.dg/torture/pr93586.c
> new file mode 100644
> index 00000000000..e861bdcd78e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/pr93586.c
> @@ -0,0 +1,21 @@
> +/* { dg-do run } */
> +/* { dg-additional-options "-fgimple" } */
> +
> +int __GIMPLE(ssa) foo(int j)
> +{
> +  int c[1][10][1];
> +  int _1;
> +
> +__BB(2):
> +  c[0][1][0] = 1;
> +  c[0][1] = _Literal (int[1]) {};
> +  _1 = c[0][j_2(D)][0];
> +  return _1;
> +}
> +
> +int main()
> +{
> +  if (foo (1) != 0)
> +    __builtin_abort ();
> +  return 0;
> +}
>
diff mbox series

Patch

diff --git a/gcc/testsuite/gcc.dg/torture/pr93586.c b/gcc/testsuite/gcc.dg/torture/pr93586.c
new file mode 100644
index 00000000000..e861bdcd78e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr93586.c
@@ -0,0 +1,21 @@ 
+/* { dg-do run } */
+/* { dg-additional-options "-fgimple" } */
+
+int __GIMPLE(ssa) foo(int j)
+{
+  int c[1][10][1];
+  int _1;
+
+__BB(2):
+  c[0][1][0] = 1;
+  c[0][1] = _Literal (int[1]) {};
+  _1 = c[0][j_2(D)][0];
+  return _1;
+}
+
+int main()
+{
+  if (foo (1) != 0)
+    __builtin_abort ();
+  return 0;
+}
diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
index b8df66ac1f2..e7caf9bee77 100644
--- a/gcc/tree-ssa-alias.c
+++ b/gcc/tree-ssa-alias.c
@@ -1291,6 +1291,11 @@  nonoverlapping_array_refs_p (tree ref1, tree ref2)
 
   tree elmt_type1 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref1, 0)));
   tree elmt_type2 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref2, 0)));
+  /* If one element is an array but not the other there's an obvious
+     mismatch in dimensionality.  */
+  if ((TREE_CODE (elmt_type1) == ARRAY_TYPE)
+      != (TREE_CODE (elmt_type2) == ARRAY_TYPE))
+    return -1;
 
   if (TREE_OPERAND (ref1, 3))
     {