[PR55547] fix alias regression on alpha on misaligned symbols (was: Re: do you have time to review this alpha P1 patch?)

[PR55547] fix alias regression on alpha on misaligned symbols (was: Re: do you have time to review this alpha P1 patch?)

[Alexandre Oliva]

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

On Jan 15, 2013, Richard Henderson <rth@redhat.com> wrote:

> On 01/15/2013 08:24 AM, Aldy Hernandez wrote:
>> Ok, it's really an alias.c bug, but it is Alpha, and aoliva has already
>> provided an unreviewed patch...

>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55547

> The patch in #C4 is ok.

Thanks, I'm checking it in (first patch below), but reviewing the logic
that uses negative sizes, I found a number of places that should use the
absolute value, and others in which being conservative about negative
sizes is unnecessary (e.g., when dealing with CONST_INT addresses).
That was implemented and regstrapped on x86_64-linux-gnu.  Uros, would
you give the second patch a spin on alpha to make sure it doesn't
regress?  Ok to install it?


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: alias-and-misaligned-out-of-range-pr55547.patch --]
[-- Type: text/x-diff, Size: 1954 bytes --]

Restore negative sizes for AND alignment

From: Alexandre Oliva <aoliva@redhat.com>

for  gcc/ChangeLog

	PR rtl-optimization/55547
	PR rtl-optimization/53827
	PR debug/53671
	PR debug/49888
	* alias.c (memrefs_conflict_p): Set sizes to negative after
	AND adjustments.
---

 gcc/alias.c |   18 +++++++++++++-----
 1 files changed, 13 insertions(+), 5 deletions(-)


diff --git a/gcc/alias.c b/gcc/alias.c
index df328ec..9a386dd 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -2080,14 +2080,20 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
 
   /* Deal with alignment ANDs by adjusting offset and size so as to
      cover the maximum range, without taking any previously known
-     alignment into account.  */
+     alignment into account.  Make a size negative after such an
+     adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
+     assume a potential overlap, because they may end up in contiguous
+     memory locations and the stricter-alignment access may span over
+     part of both.  */
   if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
     {
       HOST_WIDE_INT sc = INTVAL (XEXP (x, 1));
       unsigned HOST_WIDE_INT uc = sc;
-      if (xsize > 0 && sc < 0 && -uc == (uc & -uc))
+      if (sc < 0 && -uc == (uc & -uc))
 	{
-	  xsize -= sc + 1;
+	  if (xsize > 0)
+	    xsize = -xsize;
+	  xsize += sc + 1;
 	  c -= sc + 1;
 	  return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
 				     ysize, y, c);
@@ -2097,9 +2103,11 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
     {
       HOST_WIDE_INT sc = INTVAL (XEXP (y, 1));
       unsigned HOST_WIDE_INT uc = sc;
-      if (ysize > 0 && sc < 0 && -uc == (uc & -uc))
+      if (sc < 0 && -uc == (uc & -uc))
 	{
-	  ysize -= sc + 1;
+	  if (ysize > 0)
+	    ysize = -ysize;
+	  ysize += sc + 1;
 	  c += sc + 1;
 	  return memrefs_conflict_p (xsize, x,
 				     ysize, canon_rtx (XEXP (y, 0)), c);

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: alias-and-misaligned-out-of-range-more-pr55547.patch --]
[-- Type: text/x-diff, Size: 2584 bytes --]

Be conservative about negative sizes on symbols, use abs elsewhere

From: Alexandre Oliva <aoliva@redhat.com>

for  gcc/ChangeLog

	PR rtl-optimization/55547
	PR rtl-optimization/53827
	PR debug/53671
	PR debug/49888
	* alias.c (memrefs_conflict_p): Use abs of sizes all over,
	retaining the conservative special case for symbolic
	constants.
---

 gcc/alias.c |   21 ++++++++++++---------
 1 files changed, 12 insertions(+), 9 deletions(-)


diff --git a/gcc/alias.c b/gcc/alias.c
index 9a386dd..d51ba09 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -1976,21 +1976,21 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
   else if (GET_CODE (x) == LO_SUM)
     x = XEXP (x, 1);
   else
-    x = addr_side_effect_eval (x, xsize, 0);
+    x = addr_side_effect_eval (x, abs (xsize), 0);
   if (GET_CODE (y) == HIGH)
     y = XEXP (y, 0);
   else if (GET_CODE (y) == LO_SUM)
     y = XEXP (y, 1);
   else
-    y = addr_side_effect_eval (y, ysize, 0);
+    y = addr_side_effect_eval (y, abs (ysize), 0);
 
   if (rtx_equal_for_memref_p (x, y))
     {
-      if (xsize <= 0 || ysize <= 0)
+      if (xsize == 0 || ysize == 0)
 	return 1;
-      if (c >= 0 && xsize > c)
+      if (c >= 0 && abs (xsize) - c > 0)
 	return 1;
-      if (c < 0 && ysize+c > 0)
+      if (c < 0 && abs (ysize) + c > 0)
 	return 1;
       return 0;
     }
@@ -2063,7 +2063,8 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
 	  y0 = canon_rtx (XEXP (y, 0));
 	  if (rtx_equal_for_memref_p (x0, y0))
 	    return (xsize == 0 || ysize == 0
-		    || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
+		    || (c >= 0 && abs (xsize) - c > 0)
+		    || (c < 0 && abs (ysize) + c > 0));
 
 	  /* Can't properly adjust our sizes.  */
 	  if (!CONST_INT_P (x1))
@@ -2119,8 +2120,9 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
       if (CONST_INT_P (x) && CONST_INT_P (y))
 	{
 	  c += (INTVAL (y) - INTVAL (x));
-	  return (xsize <= 0 || ysize <= 0
-		  || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
+	  return (xsize == 0 || ysize == 0
+		  || (c >= 0 && abs (xsize) - c > 0)
+		  || (c < 0 && abs (ysize) + c > 0));
 	}
 
       if (GET_CODE (x) == CONST)
@@ -2139,7 +2141,8 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
       if (CONSTANT_P (y))
 	return (xsize <= 0 || ysize <= 0
 		|| (rtx_equal_for_memref_p (x, y)
-		    && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
+		    && ((c >= 0 && abs (xsize) - c > 0)
+			|| (c < 0 && abs (ysize) + c > 0))));
 
       return -1;
     }

[-- Attachment #4: Type: text/plain, Size: 258 bytes --]



-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer

Re: [PR55547] fix alias regression on alpha on misaligned symbols (was: Re: do you have time to review this alpha P1 patch?)

[Uros Bizjak]

On Wed, Jan 16, 2013 at 5:29 AM, Alexandre Oliva <aoliva@redhat.com> wrote:

>> On 01/15/2013 08:24 AM, Aldy Hernandez wrote:
>>> Ok, it's really an alias.c bug, but it is Alpha, and aoliva has already
>>> provided an unreviewed patch...
>
>>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55547
>
>> The patch in #C4 is ok.
>
> Thanks, I'm checking it in (first patch below), but reviewing the logic
> that uses negative sizes, I found a number of places that should use the
> absolute value, and others in which being conservative about negative
> sizes is unnecessary (e.g., when dealing with CONST_INT addresses).
> That was implemented and regstrapped on x86_64-linux-gnu.  Uros, would
> you give the second patch a spin on alpha to make sure it doesn't
> regress?  Ok to install it?

Thanks, I started a bootstrap/regtest run. If everything goes as
expected, the results will be available in ~10h from now...

Uros.

Re: [PR55547] fix alias regression on alpha on misaligned symbols (was: Re: do you have time to review this alpha P1 patch?)

[Uros Bizjak]

On Wed, Jan 16, 2013 at 8:33 AM, Uros Bizjak <ubizjak@gmail.com> wrote:

>>> On 01/15/2013 08:24 AM, Aldy Hernandez wrote:
>>>> Ok, it's really an alias.c bug, but it is Alpha, and aoliva has already
>>>> provided an unreviewed patch...
>>
>>>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55547
>>
>>> The patch in #C4 is ok.
>>
>> Thanks, I'm checking it in (first patch below), but reviewing the logic
>> that uses negative sizes, I found a number of places that should use the
>> absolute value, and others in which being conservative about negative
>> sizes is unnecessary (e.g., when dealing with CONST_INT addresses).
>> That was implemented and regstrapped on x86_64-linux-gnu.  Uros, would
>> you give the second patch a spin on alpha to make sure it doesn't
>> regress?  Ok to install it?
>
> Thanks, I started a bootstrap/regtest run. If everything goes as
> expected, the results will be available in ~10h from now...

The results looks good [1], no regressions with patch.

[1] http://gcc.gnu.org/ml/gcc-testresults/2013-01/msg01706.html

Uros.

Re: [PR55547] fix alias regression on alpha on misaligned symbols

[Richard Henderson]

On 01/15/2013 08:29 PM, Alexandre Oliva wrote:
>     if (rtx_equal_for_memref_p (x, y))
>       {
> -      if (xsize <= 0 || ysize <= 0)
> +      if (xsize == 0 || ysize == 0)
>   	return 1;
> -      if (c >= 0 && xsize > c)
> +      if (c >= 0 && abs (xsize) - c > 0)
>   	return 1;
> -      if (c < 0 && ysize+c > 0)
> +      if (c < 0 && abs (ysize) + c > 0)
>   	return 1;
>         return 0;
>       }
> @@ -2063,7 +2063,8 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
>   	  y0 = canon_rtx (XEXP (y, 0));
>   	  if (rtx_equal_for_memref_p (x0, y0))
>   	    return (xsize == 0 || ysize == 0
> -		    || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
> +		    || (c >= 0 && abs (xsize) - c > 0)
> +		    || (c < 0 && abs (ysize) + c > 0));
>
>   	  /* Can't properly adjust our sizes.  */
>   	  if (!CONST_INT_P (x1))
> @@ -2119,8 +2120,9 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
>         if (CONST_INT_P (x) && CONST_INT_P (y))
>   	{
>   	  c += (INTVAL (y) - INTVAL (x));
> -	  return (xsize <= 0 || ysize <= 0
> -		  || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
> +	  return (xsize == 0 || ysize == 0
> +		  || (c >= 0 && abs (xsize) - c > 0)
> +		  || (c < 0 && abs (ysize) + c > 0));
>   	}

I notice that these expressions (including the first hunk that uses ifs) 
are now all the same. It would seem extremely prudent to pull this out 
to a function so that they stay the same.

That said, I question the change of <= to == 0.  If negative, we don't 
know how much overlap there is as far as I can see.


>
>         if (GET_CODE (x) == CONST)
> @@ -2139,7 +2141,8 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
>         if (CONSTANT_P (y))
>   	return (xsize <= 0 || ysize <= 0
>   		|| (rtx_equal_for_memref_p (x, y)
> -		    && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
> +		    && ((c >= 0 && abs (xsize) - c > 0)
> +			|| (c < 0 && abs (ysize) + c > 0))));

This hunk is not needed, as we begin by eliminating <= 0.  So the abs is 
certain to do nothing.


r~

Re: [PR55547] fix alias regression on alpha on misaligned symbols

[Alexandre Oliva]

On Jan 16, 2013, Richard Henderson <rth@redhat.com> wrote:

> I notice that these expressions (including the first hunk that uses
> ifs) are now all the same.

*nod*

> It would seem extremely prudent to pull
> this out to a function so that they stay the same.

ack, will do.

> That said, I question the change of <= to == 0.  If negative, we don't
> know how much overlap there is as far as I can see.

Why not?  Since the addresses are constants, and the negative sizes are
just the adjusted sizes, negated to indicate they were conservatively
lengthened by an alignment operation, we can determine that two
references don't overlap if they're far enough from each other that,
even with the alignment adjustment, they're still clearly
non-overlapping.  Say, if x is 0x0fff and y is 0x1234, both originally
referenced with size 8 and x aligned to 0x20, it is obvious that the
accesses won't overlap, in spite of the alignment on x.  The test
applied on constant addresses wouldn't realize that and would say they
could overlap, because any alignment-adjusted size would be mistaken as
“overlaps with anything”.

>> if (GET_CODE (x) == CONST)
>> @@ -2139,7 +2141,8 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
>> if (CONSTANT_P (y))
>> return (xsize <= 0 || ysize <= 0
>> || (rtx_equal_for_memref_p (x, y)
>> -		    && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
>> +		    && ((c >= 0 && abs (xsize) - c > 0)
>> +			|| (c < 0 && abs (ysize) + c > 0))));

> This hunk is not needed, as we begin by eliminating <= 0.  So the abs
> is certain to do nothing.

The function I'll introduce to keep the expressions the same will have
the abs and I'll use it here, but you're right that after testing for
negative sizes they abses won't make much of a difference.

-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer

Re: [PR55547] fix alias regression on alpha on misaligned symbols

[Alexandre Oliva]

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

On Jan 16, 2013, Richard Henderson <rth@redhat.com> wrote:

> I notice that these expressions (including the first hunk that uses
> ifs) are now all the same. It would seem extremely prudent to pull
> this out to a function so that they stay the same.

Here's a revised patch that makes that change, making the overlap
computation clearer (to me) while at that.  The other fix was to avoid
adjusting zero sizes at alignment expressions, lest they'd lose the
special meaning.

Regstrapping on x86_64-linux-gnu and i686-linux-gnu.  Ok to install?


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: alias-and-misaligned-out-of-range-more-pr55547.patch --]
[-- Type: text/x-diff, Size: 4161 bytes --]

Be conservative about negative sizes on symbols, use abs elsewhere

From: Alexandre Oliva <aoliva@redhat.com>

for  gcc/ChangeLog

	PR rtl-optimization/55547
	PR rtl-optimization/53827
	PR debug/53671
	PR debug/49888
	* alias.c (memrefs_conflict_p): Use abs of sizes all over,
	retaining the conservative special case for symbolic
	constants.
---

 gcc/alias.c |   46 ++++++++++++++++++++++++++++------------------
 1 files changed, 28 insertions(+), 18 deletions(-)


diff --git a/gcc/alias.c b/gcc/alias.c
index 9a386dd..f3cd014 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -1904,6 +1904,20 @@ addr_side_effect_eval (rtx addr, int size, int n_refs)
   return addr;
 }
 
+/* Return TRUE if an object X sized at XSIZE bytes and another object
+   Y sized at YSIZE bytes, starting C bytes after X, may overlap.  If
+   any of the sizes is zero, assume an overlap, otherwise use the
+   absolute value of the sizes as the actual sizes.  */
+
+static inline bool
+offset_overlap_p (HOST_WIDE_INT c, int xsize, int ysize)
+{
+  return (xsize == 0 || ysize == 0
+	  || (c >= 0
+	      ? (abs (xsize) > c)
+	      : (abs (ysize) > -c)));
+}
+
 /* Return one if X and Y (memory addresses) reference the
    same location in memory or if the references overlap.
    Return zero if they do not overlap, else return
@@ -1976,23 +1990,17 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
   else if (GET_CODE (x) == LO_SUM)
     x = XEXP (x, 1);
   else
-    x = addr_side_effect_eval (x, xsize, 0);
+    x = addr_side_effect_eval (x, abs (xsize), 0);
   if (GET_CODE (y) == HIGH)
     y = XEXP (y, 0);
   else if (GET_CODE (y) == LO_SUM)
     y = XEXP (y, 1);
   else
-    y = addr_side_effect_eval (y, ysize, 0);
+    y = addr_side_effect_eval (y, abs (ysize), 0);
 
   if (rtx_equal_for_memref_p (x, y))
     {
-      if (xsize <= 0 || ysize <= 0)
-	return 1;
-      if (c >= 0 && xsize > c)
-	return 1;
-      if (c < 0 && ysize+c > 0)
-	return 1;
-      return 0;
+      return offset_overlap_p (c, xsize, ysize);
     }
 
   /* This code used to check for conflicts involving stack references and
@@ -2062,8 +2070,7 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
 	  x0 = canon_rtx (XEXP (x, 0));
 	  y0 = canon_rtx (XEXP (y, 0));
 	  if (rtx_equal_for_memref_p (x0, y0))
-	    return (xsize == 0 || ysize == 0
-		    || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
+	    return offset_overlap_p (c, xsize, ysize);
 
 	  /* Can't properly adjust our sizes.  */
 	  if (!CONST_INT_P (x1))
@@ -2093,7 +2100,8 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
 	{
 	  if (xsize > 0)
 	    xsize = -xsize;
-	  xsize += sc + 1;
+	  if (xsize)
+	    xsize += sc + 1;
 	  c -= sc + 1;
 	  return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
 				     ysize, y, c);
@@ -2107,7 +2115,8 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
 	{
 	  if (ysize > 0)
 	    ysize = -ysize;
-	  ysize += sc + 1;
+	  if (ysize)
+	    ysize += sc + 1;
 	  c += sc + 1;
 	  return memrefs_conflict_p (xsize, x,
 				     ysize, canon_rtx (XEXP (y, 0)), c);
@@ -2119,8 +2128,7 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
       if (CONST_INT_P (x) && CONST_INT_P (y))
 	{
 	  c += (INTVAL (y) - INTVAL (x));
-	  return (xsize <= 0 || ysize <= 0
-		  || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
+	  return offset_overlap_p (c, xsize, ysize);
 	}
 
       if (GET_CODE (x) == CONST)
@@ -2136,10 +2144,12 @@ memrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c)
 	return memrefs_conflict_p (xsize, x, ysize,
 				   canon_rtx (XEXP (y, 0)), c);
 
+      /* Assume a potential overlap for symbolic addresses that went
+	 through alignment adjustments (i.e., that have negative
+	 sizes), because we can't know how far they are from each
+	 other.  */
       if (CONSTANT_P (y))
-	return (xsize <= 0 || ysize <= 0
-		|| (rtx_equal_for_memref_p (x, y)
-		    && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
+	return (xsize < 0 || ysize < 0 || offset_overlap_p (c, xsize, ysize));
 
       return -1;
     }

[-- Attachment #3: Type: text/plain, Size: 258 bytes --]



-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer

Re: [PR55547] fix alias regression on alpha on misaligned symbols

[Richard Henderson]

On 2013-01-16 18:40, Alexandre Oliva wrote:
>> That said, I question the change of <= to == 0.  If negative, we don't
>> know how much overlap there is as far as I can see.
>
> Why not?  Since the addresses are constants, and the negative sizes are
> just the adjusted sizes, negated to indicate they were conservatively
> lengthened by an alignment operation...

Oh, right.

>> This hunk is not needed, as we begin by eliminating <= 0.  So the abs
>> is certain to do nothing.
>
> The function I'll introduce to keep the expressions the same will have
> the abs and I'll use it here, but you're right that after testing for
> negative sizes they abses won't make much of a difference.

Sure.


r~

Re: [PR55547] fix alias regression on alpha on misaligned symbols

[Richard Henderson]

On 2013-01-16 20:16, Alexandre Oliva wrote:
> Be conservative about negative sizes on symbols, use abs elsewhere
>
> From: Alexandre Oliva<aoliva@redhat.com>
>
> for  gcc/ChangeLog
>
> 	PR rtl-optimization/55547
> 	PR rtl-optimization/53827
> 	PR debug/53671
> 	PR debug/49888
> 	* alias.c (memrefs_conflict_p): Use abs of sizes all over,
> 	retaining the conservative special case for symbolic
> 	constants.

Ok.


r!~

Re: [PR55547] fix alias regression on alpha on misaligned symbols

[Alexandre Oliva]

On Jan 16, 2013, Uros Bizjak <ubizjak@gmail.com> wrote:

>> Thanks, I started a bootstrap/regtest run. If everything goes as
>> expected, the results will be available in ~10h from now...

> The results looks good [1], no regressions with patch.

> [1] http://gcc.gnu.org/ml/gcc-testresults/2013-01/msg01706.html

Thanks, the (cosmetically) revised patch is now in.

-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer