[PATCH] alias: Fix offset checks involving section anchors [PR92294]

[PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Sandiford]

Richard Sandiford <richard.sandiford@arm.com> writes:
> [...]
>> I'm not sure given the issues you've introduced if I could actually
>> fill out the matrix of answers without more underlying information. 
>> ie, when can we get symbols without source level decls, 
>> anchors+interposition issues, etc.
>
> OK.  In that case, I wonder whether it would be safer to have a
> fourth state on top of the three above:
>
>   - known distance apart
>   - independent
>   - known distance apart or independent
>   - don't know
>
> with "don't know" being anything that involves bare symbols?
>
> Richard

How does this look?  Tested on aarch64-linux-gnu and
x86_64-linux-gnu.

Full description from scratch:

memrefs_conflict_p has a slightly odd structure.  It first checks
whether two addresses based on SYMBOL_REFs refer to the same object,
with a tristate result:

      int cmp = compare_base_symbol_refs (x,y);

If the addresses do refer to the same object, we can use offset-based checks:

      /* If both decls are the same, decide by offsets.  */
      if (cmp == 1)
        return offset_overlap_p (c, xsize, ysize);

But then, apart from the special case of forced address alignment,
we use an offset-based check even if we don't know whether the
addresses refer to the same object:

      /* 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 (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
	return -1;
      /* If decls are different or we know by offsets that there is no overlap,
	 we win.  */
      if (!cmp || !offset_overlap_p (c, xsize, ysize))
	return 0;

This somewhat contradicts:

  /* In general we assume that memory locations pointed to by different labels
     may overlap in undefined ways.  */

at the end of compare_base_symbol_refs.  In other words, we're taking -1
to mean that either (a) the symbols are equal (via aliasing) or (b) the
references access non-overlapping objects.

But even assuming that's true for normal symbols, it doesn't cope
correctly with section anchors.  If a symbol X at ANCHOR+OFFSET
is preemptible, either (a) X = ANDHOR+OFFSET or (b) X and ANCHOR
reference non-overlapping objects.

And an offset-based comparison makes no sense for an anchor symbol
vs. a bare symbol with no decl.  If the bare symbol is allowed to
alias other symbols then it can surely alias any symbol in the
anchor's block, so there are multiple anchor offsets that might
induce an alias.

This patch therefore replaces the current tristate:

  - known equal
  - known independent (two accesses can't alias)
  - equal or independent

with:

  - known distance apart
  - known independent (two accesses can't alias)
  - known distance apart or independent
  - don't know

For safety, the patch puts all bare symbols in the "don't know"
category.  If that turns out to be too conservative, we at least
need that behaviour for combinations involving a bare symbol
and a section anchor.

2020-02-04  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	PR rtl-optimization/92294
	* alias.c (compare_base_symbol_refs): Take an extra parameter
	and add the distance between two symbols to it.  Enshrine in
	comments that -1 means "either 0 or 1, but we can't tell
	which at compile time".  Return -2 for symbols whose
	relationship is unknown.
	(memrefs_conflict_p): Update call accordingly.
	(rtx_equal_for_memref_p): Likewise.  Punt for a return value of -2,
	without even checking the offset.  Take the distance between symbols
	into account.
---
 gcc/alias.c | 53 ++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 38 insertions(+), 15 deletions(-)

diff --git a/gcc/alias.c b/gcc/alias.c
index 3794f9b6a9e..c8b53df0b48 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -159,7 +159,8 @@ static tree decl_for_component_ref (tree);
 static int write_dependence_p (const_rtx,
 			       const_rtx, machine_mode, rtx,
 			       bool, bool, bool);
-static int compare_base_symbol_refs (const_rtx, const_rtx);
+static int compare_base_symbol_refs (const_rtx, const_rtx,
+				     HOST_WIDE_INT * = NULL);
 
 static void memory_modified_1 (rtx, const_rtx, void *);
 
@@ -1806,7 +1807,11 @@ rtx_equal_for_memref_p (const_rtx x, const_rtx y)
       return label_ref_label (x) == label_ref_label (y);
 
     case SYMBOL_REF:
-      return compare_base_symbol_refs (x, y) == 1;
+      {
+	HOST_WIDE_INT distance = 0;
+	return (compare_base_symbol_refs (x, y, &distance) == 1
+		&& distance == 0);
+      }
 
     case ENTRY_VALUE:
       /* This is magic, don't go through canonicalization et al.  */
@@ -2138,10 +2143,24 @@ compare_base_decls (tree base1, tree base2)
   return ret;
 }
 
-/* Same as compare_base_decls but for SYMBOL_REF.  */
+/* Compare SYMBOL_REFs X_BASE and Y_BASE.
+
+   - Return 1 if Y_BASE - X_BASE is constant, adding that constant
+     to *DISTANCE if DISTANCE is nonnull.
+
+   - Return 0 if no valid accesses based on X_BASE can alias valid
+     accesses based on Y_BASE.
+
+   - Return -1 if one of the two results above applies, but we can't
+     tell which at compile time.  Update DISTANCE in the same way as
+     for a return value of 1, for the case in which that result holds
+     at runtime.
+
+   - Return -2 otherwise.  */
 
 static int
-compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
+compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
+			  HOST_WIDE_INT *distance)
 {
   tree x_decl = SYMBOL_REF_DECL (x_base);
   tree y_decl = SYMBOL_REF_DECL (y_base);
@@ -2161,7 +2180,7 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
       /* We handle specially only section anchors and assume that other
  	 labels may overlap with user variables in an arbitrary way.  */
       if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
-        return -1;
+	return -2;
       /* Anchors contains static VAR_DECLs and CONST_DECLs.  We are safe
 	 to ignore CONST_DECLs because they are readonly.  */
       if (!VAR_P (x_decl)
@@ -2188,15 +2207,14 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
     {
       if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
 	return 0;
-      if (SYMBOL_REF_BLOCK_OFFSET (x_base) == SYMBOL_REF_BLOCK_OFFSET (y_base))
-	return binds_def ? 1 : -1;
-      if (SYMBOL_REF_ANCHOR_P (x_base) != SYMBOL_REF_ANCHOR_P (y_base))
-	return -1;
-      return 0;
+      if (distance)
+	*distance += (SYMBOL_REF_BLOCK_OFFSET (y_base)
+		      - SYMBOL_REF_BLOCK_OFFSET (x_base));
+      return binds_def ? 1 : -1;
     }
   /* In general we assume that memory locations pointed to by different labels
      may overlap in undefined ways.  */
-  return -1;
+  return -2;
 }
 
 /* Return 0 if the addresses X and Y are known to point to different
@@ -2479,11 +2497,16 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
 
   if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
     {
-      int cmp = compare_base_symbol_refs (x,y);
+      HOST_WIDE_INT distance = 0;
+      int cmp = compare_base_symbol_refs (x, y, &distance);
 
-      /* If both decls are the same, decide by offsets.  */
+      /* Punt if we have no information about the relationship between
+	 X and Y.  */
+      if (cmp == -2)
+	return -1;
+      /* If the symbols are a known distance apart, decide by offsets.  */
       if (cmp == 1)
-        return offset_overlap_p (c, xsize, ysize);
+	return offset_overlap_p (c + distance, xsize, ysize);
       /* 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
@@ -2492,7 +2515,7 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
 	return -1;
       /* If decls are different or we know by offsets that there is no overlap,
 	 we win.  */
-      if (!cmp || !offset_overlap_p (c, xsize, ysize))
+      if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
 	return 0;
       /* Decls may or may not be different and offsets overlap....*/
       return -1;

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Biener]

On Tue, Feb 4, 2020 at 6:44 PM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> Richard Sandiford <richard.sandiford@arm.com> writes:
> > [...]
> >> I'm not sure given the issues you've introduced if I could actually
> >> fill out the matrix of answers without more underlying information.
> >> ie, when can we get symbols without source level decls,
> >> anchors+interposition issues, etc.
> >
> > OK.  In that case, I wonder whether it would be safer to have a
> > fourth state on top of the three above:
> >
> >   - known distance apart
> >   - independent
> >   - known distance apart or independent
> >   - don't know
> >
> > with "don't know" being anything that involves bare symbols?
> >
> > Richard
>
> How does this look?  Tested on aarch64-linux-gnu and
> x86_64-linux-gnu.
>
> Full description from scratch:
>
> memrefs_conflict_p has a slightly odd structure.  It first checks
> whether two addresses based on SYMBOL_REFs refer to the same object,
> with a tristate result:
>
>       int cmp = compare_base_symbol_refs (x,y);
>
> If the addresses do refer to the same object, we can use offset-based checks:
>
>       /* If both decls are the same, decide by offsets.  */
>       if (cmp == 1)
>         return offset_overlap_p (c, xsize, ysize);
>
> But then, apart from the special case of forced address alignment,
> we use an offset-based check even if we don't know whether the
> addresses refer to the same object:
>
>       /* 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 (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
>         return -1;
>       /* If decls are different or we know by offsets that there is no overlap,
>          we win.  */
>       if (!cmp || !offset_overlap_p (c, xsize, ysize))
>         return 0;
>
> This somewhat contradicts:
>
>   /* In general we assume that memory locations pointed to by different labels
>      may overlap in undefined ways.  */

Sorry for not chiming in earlier but isn't the bug that



> at the end of compare_base_symbol_refs.  In other words, we're taking -1
> to mean that either (a) the symbols are equal (via aliasing) or (b) the
> references access non-overlapping objects.
>
> But even assuming that's true for normal symbols, it doesn't cope
> correctly with section anchors.  If a symbol X at ANCHOR+OFFSET
> is preemptible, either (a) X = ANDHOR+OFFSET or (b) X and ANCHOR
> reference non-overlapping objects.
>
> And an offset-based comparison makes no sense for an anchor symbol
> vs. a bare symbol with no decl.  If the bare symbol is allowed to
> alias other symbols then it can surely alias any symbol in the
> anchor's block, so there are multiple anchor offsets that might
> induce an alias.

But then isn't the simple fix to honor the -1 and do

diff --git a/gcc/alias.c b/gcc/alias.c
index 3794f9b6a9e..bf13d37c0f7 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -2490,9 +2490,8 @@ memrefs_conflict_p (poly_int64 xsize, rtx x,
poly_int64 ysize, rtx y,
         other.  */
       if (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
        return -1;
-      /* If decls are different or we know by offsets that there is no overlap,
-        we win.  */
-      if (!cmp || !offset_overlap_p (c, xsize, ysize))
+      /* If decls are different, we win.  */
+      if (cmp == 0)
        return 0;
       /* Decls may or may not be different and offsets overlap....*/
       return -1;

?

> This patch therefore replaces the current tristate:
>
>   - known equal
>   - known independent (two accesses can't alias)
>   - equal or independent
>
> with:
>
>   - known distance apart
>   - known independent (two accesses can't alias)
>   - known distance apart or independent
>   - don't know
>
> For safety, the patch puts all bare symbols in the "don't know"
> category.  If that turns out to be too conservative, we at least
> need that behaviour for combinations involving a bare symbol
> and a section anchor.

This sounds complicated (for this stage).  Do you have any statistics as
to how it affects actual alias queries (thus outcome in {true,...}_dependence)
when you do the "simple" fix?

Thanks,
Richard.

> 2020-02-04  Richard Sandiford  <richard.sandiford@arm.com>
>
> gcc/
>         PR rtl-optimization/92294
>         * alias.c (compare_base_symbol_refs): Take an extra parameter
>         and add the distance between two symbols to it.  Enshrine in
>         comments that -1 means "either 0 or 1, but we can't tell
>         which at compile time".  Return -2 for symbols whose
>         relationship is unknown.
>         (memrefs_conflict_p): Update call accordingly.
>         (rtx_equal_for_memref_p): Likewise.  Punt for a return value of -2,
>         without even checking the offset.  Take the distance between symbols
>         into account.
> ---
>  gcc/alias.c | 53 ++++++++++++++++++++++++++++++++++++++---------------
>  1 file changed, 38 insertions(+), 15 deletions(-)
>
> diff --git a/gcc/alias.c b/gcc/alias.c
> index 3794f9b6a9e..c8b53df0b48 100644
> --- a/gcc/alias.c
> +++ b/gcc/alias.c
> @@ -159,7 +159,8 @@ static tree decl_for_component_ref (tree);
>  static int write_dependence_p (const_rtx,
>                                const_rtx, machine_mode, rtx,
>                                bool, bool, bool);
> -static int compare_base_symbol_refs (const_rtx, const_rtx);
> +static int compare_base_symbol_refs (const_rtx, const_rtx,
> +                                    HOST_WIDE_INT * = NULL);
>
>  static void memory_modified_1 (rtx, const_rtx, void *);
>
> @@ -1806,7 +1807,11 @@ rtx_equal_for_memref_p (const_rtx x, const_rtx y)
>        return label_ref_label (x) == label_ref_label (y);
>
>      case SYMBOL_REF:
> -      return compare_base_symbol_refs (x, y) == 1;
> +      {
> +       HOST_WIDE_INT distance = 0;
> +       return (compare_base_symbol_refs (x, y, &distance) == 1
> +               && distance == 0);
> +      }
>
>      case ENTRY_VALUE:
>        /* This is magic, don't go through canonicalization et al.  */
> @@ -2138,10 +2143,24 @@ compare_base_decls (tree base1, tree base2)
>    return ret;
>  }
>
> -/* Same as compare_base_decls but for SYMBOL_REF.  */
> +/* Compare SYMBOL_REFs X_BASE and Y_BASE.
> +
> +   - Return 1 if Y_BASE - X_BASE is constant, adding that constant
> +     to *DISTANCE if DISTANCE is nonnull.
> +
> +   - Return 0 if no valid accesses based on X_BASE can alias valid
> +     accesses based on Y_BASE.
> +
> +   - Return -1 if one of the two results above applies, but we can't
> +     tell which at compile time.  Update DISTANCE in the same way as
> +     for a return value of 1, for the case in which that result holds
> +     at runtime.
> +
> +   - Return -2 otherwise.  */
>
>  static int
> -compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
> +compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
> +                         HOST_WIDE_INT *distance)
>  {
>    tree x_decl = SYMBOL_REF_DECL (x_base);
>    tree y_decl = SYMBOL_REF_DECL (y_base);
> @@ -2161,7 +2180,7 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
>        /* We handle specially only section anchors and assume that other
>          labels may overlap with user variables in an arbitrary way.  */
>        if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
> -        return -1;
> +       return -2;
>        /* Anchors contains static VAR_DECLs and CONST_DECLs.  We are safe
>          to ignore CONST_DECLs because they are readonly.  */
>        if (!VAR_P (x_decl)
> @@ -2188,15 +2207,14 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
>      {
>        if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
>         return 0;
> -      if (SYMBOL_REF_BLOCK_OFFSET (x_base) == SYMBOL_REF_BLOCK_OFFSET (y_base))
> -       return binds_def ? 1 : -1;
> -      if (SYMBOL_REF_ANCHOR_P (x_base) != SYMBOL_REF_ANCHOR_P (y_base))
> -       return -1;
> -      return 0;
> +      if (distance)
> +       *distance += (SYMBOL_REF_BLOCK_OFFSET (y_base)
> +                     - SYMBOL_REF_BLOCK_OFFSET (x_base));
> +      return binds_def ? 1 : -1;
>      }
>    /* In general we assume that memory locations pointed to by different labels
>       may overlap in undefined ways.  */
> -  return -1;
> +  return -2;
>  }
>
>  /* Return 0 if the addresses X and Y are known to point to different
> @@ -2479,11 +2497,16 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
>
>    if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
>      {
> -      int cmp = compare_base_symbol_refs (x,y);
> +      HOST_WIDE_INT distance = 0;
> +      int cmp = compare_base_symbol_refs (x, y, &distance);
>
> -      /* If both decls are the same, decide by offsets.  */
> +      /* Punt if we have no information about the relationship between
> +        X and Y.  */
> +      if (cmp == -2)
> +       return -1;
> +      /* If the symbols are a known distance apart, decide by offsets.  */
>        if (cmp == 1)
> -        return offset_overlap_p (c, xsize, ysize);
> +       return offset_overlap_p (c + distance, xsize, ysize);
>        /* 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
> @@ -2492,7 +2515,7 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
>         return -1;
>        /* If decls are different or we know by offsets that there is no overlap,
>          we win.  */
> -      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> +      if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
>         return 0;
>        /* Decls may or may not be different and offsets overlap....*/
>        return -1;

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Sandiford]

Richard Biener <richard.guenther@gmail.com> writes:
> On Tue, Feb 4, 2020 at 6:44 PM Richard Sandiford
> <richard.sandiford@arm.com> wrote:
>>
>> Richard Sandiford <richard.sandiford@arm.com> writes:
>> > [...]
>> >> I'm not sure given the issues you've introduced if I could actually
>> >> fill out the matrix of answers without more underlying information.
>> >> ie, when can we get symbols without source level decls,
>> >> anchors+interposition issues, etc.
>> >
>> > OK.  In that case, I wonder whether it would be safer to have a
>> > fourth state on top of the three above:
>> >
>> >   - known distance apart
>> >   - independent
>> >   - known distance apart or independent
>> >   - don't know
>> >
>> > with "don't know" being anything that involves bare symbols?
>> >
>> > Richard
>>
>> How does this look?  Tested on aarch64-linux-gnu and
>> x86_64-linux-gnu.
>>
>> Full description from scratch:
>>
>> memrefs_conflict_p has a slightly odd structure.  It first checks
>> whether two addresses based on SYMBOL_REFs refer to the same object,
>> with a tristate result:
>>
>>       int cmp = compare_base_symbol_refs (x,y);
>>
>> If the addresses do refer to the same object, we can use offset-based checks:
>>
>>       /* If both decls are the same, decide by offsets.  */
>>       if (cmp == 1)
>>         return offset_overlap_p (c, xsize, ysize);
>>
>> But then, apart from the special case of forced address alignment,
>> we use an offset-based check even if we don't know whether the
>> addresses refer to the same object:
>>
>>       /* 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 (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
>>         return -1;
>>       /* If decls are different or we know by offsets that there is no overlap,
>>          we win.  */
>>       if (!cmp || !offset_overlap_p (c, xsize, ysize))
>>         return 0;
>>
>> This somewhat contradicts:
>>
>>   /* In general we assume that memory locations pointed to by different labels
>>      may overlap in undefined ways.  */
>
> Sorry for not chiming in earlier but isn't the bug that
>
>
>
>> at the end of compare_base_symbol_refs.  In other words, we're taking -1
>> to mean that either (a) the symbols are equal (via aliasing) or (b) the
>> references access non-overlapping objects.
>>
>> But even assuming that's true for normal symbols, it doesn't cope
>> correctly with section anchors.  If a symbol X at ANCHOR+OFFSET
>> is preemptible, either (a) X = ANDHOR+OFFSET or (b) X and ANCHOR
>> reference non-overlapping objects.
>>
>> And an offset-based comparison makes no sense for an anchor symbol
>> vs. a bare symbol with no decl.  If the bare symbol is allowed to
>> alias other symbols then it can surely alias any symbol in the
>> anchor's block, so there are multiple anchor offsets that might
>> induce an alias.
>
> But then isn't the simple fix to honor the -1 and do
>
> diff --git a/gcc/alias.c b/gcc/alias.c
> index 3794f9b6a9e..bf13d37c0f7 100644
> --- a/gcc/alias.c
> +++ b/gcc/alias.c
> @@ -2490,9 +2490,8 @@ memrefs_conflict_p (poly_int64 xsize, rtx x,
> poly_int64 ysize, rtx y,
>          other.  */
>        if (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
>         return -1;
> -      /* If decls are different or we know by offsets that there is no overlap,
> -        we win.  */
> -      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> +      /* If decls are different, we win.  */
> +      if (cmp == 0)
>         return 0;
>        /* Decls may or may not be different and offsets overlap....*/
>        return -1;
>
> ?

The code was deliberately written this way from the ouset though
(rather than it ending up like this through many cuts).  It was
added in g:54363f8a92920f5559c83ddd53e480a27205e6b7:

2015-12-08  Jan Hubicka  <hubicka@ucw.cz>

	PR ipa/61886
	PR middle-end/25140
	* tree-ssa-alias.c (ptr_deref_may_alias_decl_p): Use compare_base_decls
	(nonoverlapping_component_refs_of_decl_p): Update sanity check.
	(decl_refs_may_alias_p): Use compare_base_decls.
	* alias.c: Include cgraph.h
	(get_alias_set): Add cut-off for recursion.
	(rtx_equal_for_memref_p): Use rtx_equal_for_memref_p.
	(compare_base_decls): New function.
	(base_alias_check): Likewise.
	(memrefs_conflict_p): Likewise.
	(nonoverlapping_memrefs_p): Likewise.
	* alias.h (compare_base_decls): Declare.

which included:

-  if (rtx_equal_for_memref_p (x, y))
+  if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
+    {
+      tree x_decl = SYMBOL_REF_DECL (x);
+      tree y_decl = SYMBOL_REF_DECL (y);
+      int cmp;
+
+      if (!x_decl || !y_decl)
+	{
+	  /* Label and normal symbol are never the same. */
+	  if (x_decl != y_decl)
+	    return 0;
+	  return offset_overlap_p (c, xsize, ysize);
+	}
+      else
+        cmp = compare_base_decls (x_decl, y_decl);
+
+      /* If both decls are the same, decide by offsets.  */
+      if (cmp == 1)
+        return offset_overlap_p (c, xsize, ysize);
+      /* If decls are different or we know by offsets that there is no overlap,
+	 we win.  */
+      if (!cmp || !offset_overlap_p (c, xsize, ysize))
+	return 0;
+      /* Decls may or may not be different and offsets overlap....*/
+      return -1;
+    }
+  else if (rtx_equal_for_memref_p (x, y))

The only significant change since them was to add compare_base_symbol_refs
(g:73e48cb322152bf504ced8694fa748544ecaa6eb):

   if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
     {
-      tree x_decl = SYMBOL_REF_DECL (x);
-      tree y_decl = SYMBOL_REF_DECL (y);
-      int cmp;
-
-      if (!x_decl || !y_decl)
-	{
-	  /* Label and normal symbol are never the same. */
-	  if (x_decl != y_decl)
-	    return 0;
-	  return offset_overlap_p (c, xsize, ysize);
-	}
-      else
-        cmp = compare_base_decls (x_decl, y_decl);
+      int cmp = compare_base_symbol_refs (x,y);

>> This patch therefore replaces the current tristate:
>>
>>   - known equal
>>   - known independent (two accesses can't alias)
>>   - equal or independent
>>
>> with:
>>
>>   - known distance apart
>>   - known independent (two accesses can't alias)
>>   - known distance apart or independent
>>   - don't know
>>
>> For safety, the patch puts all bare symbols in the "don't know"
>> category.  If that turns out to be too conservative, we at least
>> need that behaviour for combinations involving a bare symbol
>> and a section anchor.
>
> This sounds complicated (for this stage).  Do you have any statistics as
> to how it affects actual alias queries (thus outcome in {true,...}_dependence)
> when you do the "simple" fix?

For a stage3 build of gcc on aarch64-linux-gnu I get:

   ("positive" == conflict, "negative" == no conflict)

   16191  cmp ==  1,    disjoint offsets :  true negative
   19698  cmp ==  1, overlapping offsets :  true positive
   79363  cmp == -1,    disjoint offsets :  true negative
    6965  cmp == -1,    disjoint offsets : false negative <== bug
      48  cmp == -1, overlapping offsets :  true positive
     928  cmp == -1, overlapping offsets : false positive <== missed opt
  123193  total queries

where the cmp == -1 cases are divided into true and false results
according to whether we get the same answer when taking the (hopefully)
correct offset into account.  cmp == 0 and what would be cmp == -2 never
occured.

So it looks like we're relying on the cmp == -1 offset_overlap_p
check to get true "no conflict" results for ~64% of all queries
(or ~83% of all true "no conflict" results).  I expect this is
very dependent on the fact that the port uses section anchors.

The number of buggy cases seems surprisingly high, but I've tried
to re-check it a couple of times and it looks to be accurate.
They come from cases where we compare things like:

x: (symbol_ref:DI ("*.LANCHOR0") [flags 0x182])
y: (symbol_ref:DI ("_ZL23yy_last_accepting_state") [flags 0x82] <var_decl ... yy_last_accepting_state>)
c: -48

where yy_last_accepting_state is at offset 48 from the anchor.
I haven't checked where the buggy queries are coming from though;
might be debug-related and so hard to spot.

Thanks,
Richard

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Sandiford]

What should we do about this?  The PR is a wrong-code regression from
GCC 9 and it doesn't look like we can remove the second offset_overlap_p
check, given how many cases currently rely on it.

Thanks,
Richard

Richard Sandiford <richard.sandiford@arm.com> writes:
> Richard Biener <richard.guenther@gmail.com> writes:
>> On Tue, Feb 4, 2020 at 6:44 PM Richard Sandiford
>> <richard.sandiford@arm.com> wrote:
>>>
>>> Richard Sandiford <richard.sandiford@arm.com> writes:
>>> > [...]
>>> >> I'm not sure given the issues you've introduced if I could actually
>>> >> fill out the matrix of answers without more underlying information.
>>> >> ie, when can we get symbols without source level decls,
>>> >> anchors+interposition issues, etc.
>>> >
>>> > OK.  In that case, I wonder whether it would be safer to have a
>>> > fourth state on top of the three above:
>>> >
>>> >   - known distance apart
>>> >   - independent
>>> >   - known distance apart or independent
>>> >   - don't know
>>> >
>>> > with "don't know" being anything that involves bare symbols?
>>> >
>>> > Richard
>>>
>>> How does this look?  Tested on aarch64-linux-gnu and
>>> x86_64-linux-gnu.
>>>
>>> Full description from scratch:
>>>
>>> memrefs_conflict_p has a slightly odd structure.  It first checks
>>> whether two addresses based on SYMBOL_REFs refer to the same object,
>>> with a tristate result:
>>>
>>>       int cmp = compare_base_symbol_refs (x,y);
>>>
>>> If the addresses do refer to the same object, we can use offset-based checks:
>>>
>>>       /* If both decls are the same, decide by offsets.  */
>>>       if (cmp == 1)
>>>         return offset_overlap_p (c, xsize, ysize);
>>>
>>> But then, apart from the special case of forced address alignment,
>>> we use an offset-based check even if we don't know whether the
>>> addresses refer to the same object:
>>>
>>>       /* 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 (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
>>>         return -1;
>>>       /* If decls are different or we know by offsets that there is no overlap,
>>>          we win.  */
>>>       if (!cmp || !offset_overlap_p (c, xsize, ysize))
>>>         return 0;
>>>
>>> This somewhat contradicts:
>>>
>>>   /* In general we assume that memory locations pointed to by different labels
>>>      may overlap in undefined ways.  */
>>
>> Sorry for not chiming in earlier but isn't the bug that
>>
>>
>>
>>> at the end of compare_base_symbol_refs.  In other words, we're taking -1
>>> to mean that either (a) the symbols are equal (via aliasing) or (b) the
>>> references access non-overlapping objects.
>>>
>>> But even assuming that's true for normal symbols, it doesn't cope
>>> correctly with section anchors.  If a symbol X at ANCHOR+OFFSET
>>> is preemptible, either (a) X = ANDHOR+OFFSET or (b) X and ANCHOR
>>> reference non-overlapping objects.
>>>
>>> And an offset-based comparison makes no sense for an anchor symbol
>>> vs. a bare symbol with no decl.  If the bare symbol is allowed to
>>> alias other symbols then it can surely alias any symbol in the
>>> anchor's block, so there are multiple anchor offsets that might
>>> induce an alias.
>>
>> But then isn't the simple fix to honor the -1 and do
>>
>> diff --git a/gcc/alias.c b/gcc/alias.c
>> index 3794f9b6a9e..bf13d37c0f7 100644
>> --- a/gcc/alias.c
>> +++ b/gcc/alias.c
>> @@ -2490,9 +2490,8 @@ memrefs_conflict_p (poly_int64 xsize, rtx x,
>> poly_int64 ysize, rtx y,
>>          other.  */
>>        if (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
>>         return -1;
>> -      /* If decls are different or we know by offsets that there is no overlap,
>> -        we win.  */
>> -      if (!cmp || !offset_overlap_p (c, xsize, ysize))
>> +      /* If decls are different, we win.  */
>> +      if (cmp == 0)
>>         return 0;
>>        /* Decls may or may not be different and offsets overlap....*/
>>        return -1;
>>
>> ?
>
> The code was deliberately written this way from the ouset though
> (rather than it ending up like this through many cuts).  It was
> added in g:54363f8a92920f5559c83ddd53e480a27205e6b7:
>
> 2015-12-08  Jan Hubicka  <hubicka@ucw.cz>
>
> 	PR ipa/61886
> 	PR middle-end/25140
> 	* tree-ssa-alias.c (ptr_deref_may_alias_decl_p): Use compare_base_decls
> 	(nonoverlapping_component_refs_of_decl_p): Update sanity check.
> 	(decl_refs_may_alias_p): Use compare_base_decls.
> 	* alias.c: Include cgraph.h
> 	(get_alias_set): Add cut-off for recursion.
> 	(rtx_equal_for_memref_p): Use rtx_equal_for_memref_p.
> 	(compare_base_decls): New function.
> 	(base_alias_check): Likewise.
> 	(memrefs_conflict_p): Likewise.
> 	(nonoverlapping_memrefs_p): Likewise.
> 	* alias.h (compare_base_decls): Declare.
>
> which included:
>
> -  if (rtx_equal_for_memref_p (x, y))
> +  if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
> +    {
> +      tree x_decl = SYMBOL_REF_DECL (x);
> +      tree y_decl = SYMBOL_REF_DECL (y);
> +      int cmp;
> +
> +      if (!x_decl || !y_decl)
> +	{
> +	  /* Label and normal symbol are never the same. */
> +	  if (x_decl != y_decl)
> +	    return 0;
> +	  return offset_overlap_p (c, xsize, ysize);
> +	}
> +      else
> +        cmp = compare_base_decls (x_decl, y_decl);
> +
> +      /* If both decls are the same, decide by offsets.  */
> +      if (cmp == 1)
> +        return offset_overlap_p (c, xsize, ysize);
> +      /* If decls are different or we know by offsets that there is no overlap,
> +	 we win.  */
> +      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> +	return 0;
> +      /* Decls may or may not be different and offsets overlap....*/
> +      return -1;
> +    }
> +  else if (rtx_equal_for_memref_p (x, y))
>
> The only significant change since them was to add compare_base_symbol_refs
> (g:73e48cb322152bf504ced8694fa748544ecaa6eb):
>
>    if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
>      {
> -      tree x_decl = SYMBOL_REF_DECL (x);
> -      tree y_decl = SYMBOL_REF_DECL (y);
> -      int cmp;
> -
> -      if (!x_decl || !y_decl)
> -	{
> -	  /* Label and normal symbol are never the same. */
> -	  if (x_decl != y_decl)
> -	    return 0;
> -	  return offset_overlap_p (c, xsize, ysize);
> -	}
> -      else
> -        cmp = compare_base_decls (x_decl, y_decl);
> +      int cmp = compare_base_symbol_refs (x,y);
>
>>> This patch therefore replaces the current tristate:
>>>
>>>   - known equal
>>>   - known independent (two accesses can't alias)
>>>   - equal or independent
>>>
>>> with:
>>>
>>>   - known distance apart
>>>   - known independent (two accesses can't alias)
>>>   - known distance apart or independent
>>>   - don't know
>>>
>>> For safety, the patch puts all bare symbols in the "don't know"
>>> category.  If that turns out to be too conservative, we at least
>>> need that behaviour for combinations involving a bare symbol
>>> and a section anchor.
>>
>> This sounds complicated (for this stage).  Do you have any statistics as
>> to how it affects actual alias queries (thus outcome in {true,...}_dependence)
>> when you do the "simple" fix?
>
> For a stage3 build of gcc on aarch64-linux-gnu I get:
>
>    ("positive" == conflict, "negative" == no conflict)
>
>    16191  cmp ==  1,    disjoint offsets :  true negative
>    19698  cmp ==  1, overlapping offsets :  true positive
>    79363  cmp == -1,    disjoint offsets :  true negative
>     6965  cmp == -1,    disjoint offsets : false negative <== bug
>       48  cmp == -1, overlapping offsets :  true positive
>      928  cmp == -1, overlapping offsets : false positive <== missed opt
>   123193  total queries
>
> where the cmp == -1 cases are divided into true and false results
> according to whether we get the same answer when taking the (hopefully)
> correct offset into account.  cmp == 0 and what would be cmp == -2 never
> occured.
>
> So it looks like we're relying on the cmp == -1 offset_overlap_p
> check to get true "no conflict" results for ~64% of all queries
> (or ~83% of all true "no conflict" results).  I expect this is
> very dependent on the fact that the port uses section anchors.
>
> The number of buggy cases seems surprisingly high, but I've tried
> to re-check it a couple of times and it looks to be accurate.
> They come from cases where we compare things like:
>
> x: (symbol_ref:DI ("*.LANCHOR0") [flags 0x182])
> y: (symbol_ref:DI ("_ZL23yy_last_accepting_state") [flags 0x82] <var_decl ... yy_last_accepting_state>)
> c: -48
>
> where yy_last_accepting_state is at offset 48 from the anchor.
> I haven't checked where the buggy queries are coming from though;
> might be debug-related and so hard to spot.
>
> Thanks,
> Richard

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Biener]

On Wed, Feb 19, 2020 at 1:19 PM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> What should we do about this?  The PR is a wrong-code regression from
> GCC 9 and it doesn't look like we can remove the second offset_overlap_p
> check, given how many cases currently rely on it.

Did you check whether we eventually disambiguate those via rtx_refs_may_alias_p
(so using MEM_EXPR)?  I would guess all but those that have no MEM_EXPR?

Ideally we'd rely more on MEM_EXPR for alias disambiguation than the ad-hoc
ways of recovering "details" from the actual MEM.

If numbers are still in the same ballpark when factoring in alias
disambiguations
run after memrefs_conflict_p calls then let's go with your patch, it
looks technically
correct if all the facts about section anchors are correct (where I
know not very much
about them or representational issues wrt aliasing).

Thanks,
Richard.

> Thanks,
> Richard
>
> Richard Sandiford <richard.sandiford@arm.com> writes:
> > Richard Biener <richard.guenther@gmail.com> writes:
> >> On Tue, Feb 4, 2020 at 6:44 PM Richard Sandiford
> >> <richard.sandiford@arm.com> wrote:
> >>>
> >>> Richard Sandiford <richard.sandiford@arm.com> writes:
> >>> > [...]
> >>> >> I'm not sure given the issues you've introduced if I could actually
> >>> >> fill out the matrix of answers without more underlying information.
> >>> >> ie, when can we get symbols without source level decls,
> >>> >> anchors+interposition issues, etc.
> >>> >
> >>> > OK.  In that case, I wonder whether it would be safer to have a
> >>> > fourth state on top of the three above:
> >>> >
> >>> >   - known distance apart
> >>> >   - independent
> >>> >   - known distance apart or independent
> >>> >   - don't know
> >>> >
> >>> > with "don't know" being anything that involves bare symbols?
> >>> >
> >>> > Richard
> >>>
> >>> How does this look?  Tested on aarch64-linux-gnu and
> >>> x86_64-linux-gnu.
> >>>
> >>> Full description from scratch:
> >>>
> >>> memrefs_conflict_p has a slightly odd structure.  It first checks
> >>> whether two addresses based on SYMBOL_REFs refer to the same object,
> >>> with a tristate result:
> >>>
> >>>       int cmp = compare_base_symbol_refs (x,y);
> >>>
> >>> If the addresses do refer to the same object, we can use offset-based checks:
> >>>
> >>>       /* If both decls are the same, decide by offsets.  */
> >>>       if (cmp == 1)
> >>>         return offset_overlap_p (c, xsize, ysize);
> >>>
> >>> But then, apart from the special case of forced address alignment,
> >>> we use an offset-based check even if we don't know whether the
> >>> addresses refer to the same object:
> >>>
> >>>       /* 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 (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
> >>>         return -1;
> >>>       /* If decls are different or we know by offsets that there is no overlap,
> >>>          we win.  */
> >>>       if (!cmp || !offset_overlap_p (c, xsize, ysize))
> >>>         return 0;
> >>>
> >>> This somewhat contradicts:
> >>>
> >>>   /* In general we assume that memory locations pointed to by different labels
> >>>      may overlap in undefined ways.  */
> >>
> >> Sorry for not chiming in earlier but isn't the bug that
> >>
> >>
> >>
> >>> at the end of compare_base_symbol_refs.  In other words, we're taking -1
> >>> to mean that either (a) the symbols are equal (via aliasing) or (b) the
> >>> references access non-overlapping objects.
> >>>
> >>> But even assuming that's true for normal symbols, it doesn't cope
> >>> correctly with section anchors.  If a symbol X at ANCHOR+OFFSET
> >>> is preemptible, either (a) X = ANDHOR+OFFSET or (b) X and ANCHOR
> >>> reference non-overlapping objects.
> >>>
> >>> And an offset-based comparison makes no sense for an anchor symbol
> >>> vs. a bare symbol with no decl.  If the bare symbol is allowed to
> >>> alias other symbols then it can surely alias any symbol in the
> >>> anchor's block, so there are multiple anchor offsets that might
> >>> induce an alias.
> >>
> >> But then isn't the simple fix to honor the -1 and do
> >>
> >> diff --git a/gcc/alias.c b/gcc/alias.c
> >> index 3794f9b6a9e..bf13d37c0f7 100644
> >> --- a/gcc/alias.c
> >> +++ b/gcc/alias.c
> >> @@ -2490,9 +2490,8 @@ memrefs_conflict_p (poly_int64 xsize, rtx x,
> >> poly_int64 ysize, rtx y,
> >>          other.  */
> >>        if (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
> >>         return -1;
> >> -      /* If decls are different or we know by offsets that there is no overlap,
> >> -        we win.  */
> >> -      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> >> +      /* If decls are different, we win.  */
> >> +      if (cmp == 0)
> >>         return 0;
> >>        /* Decls may or may not be different and offsets overlap....*/
> >>        return -1;
> >>
> >> ?
> >
> > The code was deliberately written this way from the ouset though
> > (rather than it ending up like this through many cuts).  It was
> > added in g:54363f8a92920f5559c83ddd53e480a27205e6b7:
> >
> > 2015-12-08  Jan Hubicka  <hubicka@ucw.cz>
> >
> >       PR ipa/61886
> >       PR middle-end/25140
> >       * tree-ssa-alias.c (ptr_deref_may_alias_decl_p): Use compare_base_decls
> >       (nonoverlapping_component_refs_of_decl_p): Update sanity check.
> >       (decl_refs_may_alias_p): Use compare_base_decls.
> >       * alias.c: Include cgraph.h
> >       (get_alias_set): Add cut-off for recursion.
> >       (rtx_equal_for_memref_p): Use rtx_equal_for_memref_p.
> >       (compare_base_decls): New function.
> >       (base_alias_check): Likewise.
> >       (memrefs_conflict_p): Likewise.
> >       (nonoverlapping_memrefs_p): Likewise.
> >       * alias.h (compare_base_decls): Declare.
> >
> > which included:
> >
> > -  if (rtx_equal_for_memref_p (x, y))
> > +  if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
> > +    {
> > +      tree x_decl = SYMBOL_REF_DECL (x);
> > +      tree y_decl = SYMBOL_REF_DECL (y);
> > +      int cmp;
> > +
> > +      if (!x_decl || !y_decl)
> > +     {
> > +       /* Label and normal symbol are never the same. */
> > +       if (x_decl != y_decl)
> > +         return 0;
> > +       return offset_overlap_p (c, xsize, ysize);
> > +     }
> > +      else
> > +        cmp = compare_base_decls (x_decl, y_decl);
> > +
> > +      /* If both decls are the same, decide by offsets.  */
> > +      if (cmp == 1)
> > +        return offset_overlap_p (c, xsize, ysize);
> > +      /* If decls are different or we know by offsets that there is no overlap,
> > +      we win.  */
> > +      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> > +     return 0;
> > +      /* Decls may or may not be different and offsets overlap....*/
> > +      return -1;
> > +    }
> > +  else if (rtx_equal_for_memref_p (x, y))
> >
> > The only significant change since them was to add compare_base_symbol_refs
> > (g:73e48cb322152bf504ced8694fa748544ecaa6eb):
> >
> >    if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
> >      {
> > -      tree x_decl = SYMBOL_REF_DECL (x);
> > -      tree y_decl = SYMBOL_REF_DECL (y);
> > -      int cmp;
> > -
> > -      if (!x_decl || !y_decl)
> > -     {
> > -       /* Label and normal symbol are never the same. */
> > -       if (x_decl != y_decl)
> > -         return 0;
> > -       return offset_overlap_p (c, xsize, ysize);
> > -     }
> > -      else
> > -        cmp = compare_base_decls (x_decl, y_decl);
> > +      int cmp = compare_base_symbol_refs (x,y);
> >
> >>> This patch therefore replaces the current tristate:
> >>>
> >>>   - known equal
> >>>   - known independent (two accesses can't alias)
> >>>   - equal or independent
> >>>
> >>> with:
> >>>
> >>>   - known distance apart
> >>>   - known independent (two accesses can't alias)
> >>>   - known distance apart or independent
> >>>   - don't know
> >>>
> >>> For safety, the patch puts all bare symbols in the "don't know"
> >>> category.  If that turns out to be too conservative, we at least
> >>> need that behaviour for combinations involving a bare symbol
> >>> and a section anchor.
> >>
> >> This sounds complicated (for this stage).  Do you have any statistics as
> >> to how it affects actual alias queries (thus outcome in {true,...}_dependence)
> >> when you do the "simple" fix?
> >
> > For a stage3 build of gcc on aarch64-linux-gnu I get:
> >
> >    ("positive" == conflict, "negative" == no conflict)
> >
> >    16191  cmp ==  1,    disjoint offsets :  true negative
> >    19698  cmp ==  1, overlapping offsets :  true positive
> >    79363  cmp == -1,    disjoint offsets :  true negative
> >     6965  cmp == -1,    disjoint offsets : false negative <== bug
> >       48  cmp == -1, overlapping offsets :  true positive
> >      928  cmp == -1, overlapping offsets : false positive <== missed opt
> >   123193  total queries
> >
> > where the cmp == -1 cases are divided into true and false results
> > according to whether we get the same answer when taking the (hopefully)
> > correct offset into account.  cmp == 0 and what would be cmp == -2 never
> > occured.
> >
> > So it looks like we're relying on the cmp == -1 offset_overlap_p
> > check to get true "no conflict" results for ~64% of all queries
> > (or ~83% of all true "no conflict" results).  I expect this is
> > very dependent on the fact that the port uses section anchors.
> >
> > The number of buggy cases seems surprisingly high, but I've tried
> > to re-check it a couple of times and it looks to be accurate.
> > They come from cases where we compare things like:
> >
> > x: (symbol_ref:DI ("*.LANCHOR0") [flags 0x182])
> > y: (symbol_ref:DI ("_ZL23yy_last_accepting_state") [flags 0x82] <var_decl ... yy_last_accepting_state>)
> > c: -48
> >
> > where yy_last_accepting_state is at offset 48 from the anchor.
> > I haven't checked where the buggy queries are coming from though;
> > might be debug-related and so hard to spot.
> >
> > Thanks,
> > Richard

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Biener]

On Wed, Feb 19, 2020 at 3:20 PM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Wed, Feb 19, 2020 at 1:19 PM Richard Sandiford
> <richard.sandiford@arm.com> wrote:
> >
> > What should we do about this?  The PR is a wrong-code regression from
> > GCC 9 and it doesn't look like we can remove the second offset_overlap_p
> > check, given how many cases currently rely on it.
>
> Did you check whether we eventually disambiguate those via rtx_refs_may_alias_p
> (so using MEM_EXPR)?  I would guess all but those that have no MEM_EXPR?
>
> Ideally we'd rely more on MEM_EXPR for alias disambiguation than the ad-hoc
> ways of recovering "details" from the actual MEM.
>
> If numbers are still in the same ballpark when factoring in alias
> disambiguations
> run after memrefs_conflict_p calls then let's go with your patch, it
> looks technically
> correct if all the facts about section anchors are correct (where I
> know not very much
> about them or representational issues wrt aliasing).

See the patch attached to https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49330
for how I did this kind of statistics for base_alias_check.  But as
said, counting
!MEM_EXPR cases might be a good enough hint.

Richard.

> Thanks,
> Richard.
>
> > Thanks,
> > Richard
> >
> > Richard Sandiford <richard.sandiford@arm.com> writes:
> > > Richard Biener <richard.guenther@gmail.com> writes:
> > >> On Tue, Feb 4, 2020 at 6:44 PM Richard Sandiford
> > >> <richard.sandiford@arm.com> wrote:
> > >>>
> > >>> Richard Sandiford <richard.sandiford@arm.com> writes:
> > >>> > [...]
> > >>> >> I'm not sure given the issues you've introduced if I could actually
> > >>> >> fill out the matrix of answers without more underlying information.
> > >>> >> ie, when can we get symbols without source level decls,
> > >>> >> anchors+interposition issues, etc.
> > >>> >
> > >>> > OK.  In that case, I wonder whether it would be safer to have a
> > >>> > fourth state on top of the three above:
> > >>> >
> > >>> >   - known distance apart
> > >>> >   - independent
> > >>> >   - known distance apart or independent
> > >>> >   - don't know
> > >>> >
> > >>> > with "don't know" being anything that involves bare symbols?
> > >>> >
> > >>> > Richard
> > >>>
> > >>> How does this look?  Tested on aarch64-linux-gnu and
> > >>> x86_64-linux-gnu.
> > >>>
> > >>> Full description from scratch:
> > >>>
> > >>> memrefs_conflict_p has a slightly odd structure.  It first checks
> > >>> whether two addresses based on SYMBOL_REFs refer to the same object,
> > >>> with a tristate result:
> > >>>
> > >>>       int cmp = compare_base_symbol_refs (x,y);
> > >>>
> > >>> If the addresses do refer to the same object, we can use offset-based checks:
> > >>>
> > >>>       /* If both decls are the same, decide by offsets.  */
> > >>>       if (cmp == 1)
> > >>>         return offset_overlap_p (c, xsize, ysize);
> > >>>
> > >>> But then, apart from the special case of forced address alignment,
> > >>> we use an offset-based check even if we don't know whether the
> > >>> addresses refer to the same object:
> > >>>
> > >>>       /* 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 (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
> > >>>         return -1;
> > >>>       /* If decls are different or we know by offsets that there is no overlap,
> > >>>          we win.  */
> > >>>       if (!cmp || !offset_overlap_p (c, xsize, ysize))
> > >>>         return 0;
> > >>>
> > >>> This somewhat contradicts:
> > >>>
> > >>>   /* In general we assume that memory locations pointed to by different labels
> > >>>      may overlap in undefined ways.  */
> > >>
> > >> Sorry for not chiming in earlier but isn't the bug that
> > >>
> > >>
> > >>
> > >>> at the end of compare_base_symbol_refs.  In other words, we're taking -1
> > >>> to mean that either (a) the symbols are equal (via aliasing) or (b) the
> > >>> references access non-overlapping objects.
> > >>>
> > >>> But even assuming that's true for normal symbols, it doesn't cope
> > >>> correctly with section anchors.  If a symbol X at ANCHOR+OFFSET
> > >>> is preemptible, either (a) X = ANDHOR+OFFSET or (b) X and ANCHOR
> > >>> reference non-overlapping objects.
> > >>>
> > >>> And an offset-based comparison makes no sense for an anchor symbol
> > >>> vs. a bare symbol with no decl.  If the bare symbol is allowed to
> > >>> alias other symbols then it can surely alias any symbol in the
> > >>> anchor's block, so there are multiple anchor offsets that might
> > >>> induce an alias.
> > >>
> > >> But then isn't the simple fix to honor the -1 and do
> > >>
> > >> diff --git a/gcc/alias.c b/gcc/alias.c
> > >> index 3794f9b6a9e..bf13d37c0f7 100644
> > >> --- a/gcc/alias.c
> > >> +++ b/gcc/alias.c
> > >> @@ -2490,9 +2490,8 @@ memrefs_conflict_p (poly_int64 xsize, rtx x,
> > >> poly_int64 ysize, rtx y,
> > >>          other.  */
> > >>        if (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
> > >>         return -1;
> > >> -      /* If decls are different or we know by offsets that there is no overlap,
> > >> -        we win.  */
> > >> -      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> > >> +      /* If decls are different, we win.  */
> > >> +      if (cmp == 0)
> > >>         return 0;
> > >>        /* Decls may or may not be different and offsets overlap....*/
> > >>        return -1;
> > >>
> > >> ?
> > >
> > > The code was deliberately written this way from the ouset though
> > > (rather than it ending up like this through many cuts).  It was
> > > added in g:54363f8a92920f5559c83ddd53e480a27205e6b7:
> > >
> > > 2015-12-08  Jan Hubicka  <hubicka@ucw.cz>
> > >
> > >       PR ipa/61886
> > >       PR middle-end/25140
> > >       * tree-ssa-alias.c (ptr_deref_may_alias_decl_p): Use compare_base_decls
> > >       (nonoverlapping_component_refs_of_decl_p): Update sanity check.
> > >       (decl_refs_may_alias_p): Use compare_base_decls.
> > >       * alias.c: Include cgraph.h
> > >       (get_alias_set): Add cut-off for recursion.
> > >       (rtx_equal_for_memref_p): Use rtx_equal_for_memref_p.
> > >       (compare_base_decls): New function.
> > >       (base_alias_check): Likewise.
> > >       (memrefs_conflict_p): Likewise.
> > >       (nonoverlapping_memrefs_p): Likewise.
> > >       * alias.h (compare_base_decls): Declare.
> > >
> > > which included:
> > >
> > > -  if (rtx_equal_for_memref_p (x, y))
> > > +  if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
> > > +    {
> > > +      tree x_decl = SYMBOL_REF_DECL (x);
> > > +      tree y_decl = SYMBOL_REF_DECL (y);
> > > +      int cmp;
> > > +
> > > +      if (!x_decl || !y_decl)
> > > +     {
> > > +       /* Label and normal symbol are never the same. */
> > > +       if (x_decl != y_decl)
> > > +         return 0;
> > > +       return offset_overlap_p (c, xsize, ysize);
> > > +     }
> > > +      else
> > > +        cmp = compare_base_decls (x_decl, y_decl);
> > > +
> > > +      /* If both decls are the same, decide by offsets.  */
> > > +      if (cmp == 1)
> > > +        return offset_overlap_p (c, xsize, ysize);
> > > +      /* If decls are different or we know by offsets that there is no overlap,
> > > +      we win.  */
> > > +      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> > > +     return 0;
> > > +      /* Decls may or may not be different and offsets overlap....*/
> > > +      return -1;
> > > +    }
> > > +  else if (rtx_equal_for_memref_p (x, y))
> > >
> > > The only significant change since them was to add compare_base_symbol_refs
> > > (g:73e48cb322152bf504ced8694fa748544ecaa6eb):
> > >
> > >    if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
> > >      {
> > > -      tree x_decl = SYMBOL_REF_DECL (x);
> > > -      tree y_decl = SYMBOL_REF_DECL (y);
> > > -      int cmp;
> > > -
> > > -      if (!x_decl || !y_decl)
> > > -     {
> > > -       /* Label and normal symbol are never the same. */
> > > -       if (x_decl != y_decl)
> > > -         return 0;
> > > -       return offset_overlap_p (c, xsize, ysize);
> > > -     }
> > > -      else
> > > -        cmp = compare_base_decls (x_decl, y_decl);
> > > +      int cmp = compare_base_symbol_refs (x,y);
> > >
> > >>> This patch therefore replaces the current tristate:
> > >>>
> > >>>   - known equal
> > >>>   - known independent (two accesses can't alias)
> > >>>   - equal or independent
> > >>>
> > >>> with:
> > >>>
> > >>>   - known distance apart
> > >>>   - known independent (two accesses can't alias)
> > >>>   - known distance apart or independent
> > >>>   - don't know
> > >>>
> > >>> For safety, the patch puts all bare symbols in the "don't know"
> > >>> category.  If that turns out to be too conservative, we at least
> > >>> need that behaviour for combinations involving a bare symbol
> > >>> and a section anchor.
> > >>
> > >> This sounds complicated (for this stage).  Do you have any statistics as
> > >> to how it affects actual alias queries (thus outcome in {true,...}_dependence)
> > >> when you do the "simple" fix?
> > >
> > > For a stage3 build of gcc on aarch64-linux-gnu I get:
> > >
> > >    ("positive" == conflict, "negative" == no conflict)
> > >
> > >    16191  cmp ==  1,    disjoint offsets :  true negative
> > >    19698  cmp ==  1, overlapping offsets :  true positive
> > >    79363  cmp == -1,    disjoint offsets :  true negative
> > >     6965  cmp == -1,    disjoint offsets : false negative <== bug
> > >       48  cmp == -1, overlapping offsets :  true positive
> > >      928  cmp == -1, overlapping offsets : false positive <== missed opt
> > >   123193  total queries
> > >
> > > where the cmp == -1 cases are divided into true and false results
> > > according to whether we get the same answer when taking the (hopefully)
> > > correct offset into account.  cmp == 0 and what would be cmp == -2 never
> > > occured.
> > >
> > > So it looks like we're relying on the cmp == -1 offset_overlap_p
> > > check to get true "no conflict" results for ~64% of all queries
> > > (or ~83% of all true "no conflict" results).  I expect this is
> > > very dependent on the fact that the port uses section anchors.
> > >
> > > The number of buggy cases seems surprisingly high, but I've tried
> > > to re-check it a couple of times and it looks to be accurate.
> > > They come from cases where we compare things like:
> > >
> > > x: (symbol_ref:DI ("*.LANCHOR0") [flags 0x182])
> > > y: (symbol_ref:DI ("_ZL23yy_last_accepting_state") [flags 0x82] <var_decl ... yy_last_accepting_state>)
> > > c: -48
> > >
> > > where yy_last_accepting_state is at offset 48 from the anchor.
> > > I haven't checked where the buggy queries are coming from though;
> > > might be debug-related and so hard to spot.
> > >
> > > Thanks,
> > > Richard

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Sandiford]

Richard Biener <richard.guenther@gmail.com> writes:
> On Wed, Feb 19, 2020 at 1:19 PM Richard Sandiford
> <richard.sandiford@arm.com> wrote:
>>
>> What should we do about this?  The PR is a wrong-code regression from
>> GCC 9 and it doesn't look like we can remove the second offset_overlap_p
>> check, given how many cases currently rely on it.
>
> Did you check whether we eventually disambiguate those via rtx_refs_may_alias_p
> (so using MEM_EXPR)?  I would guess all but those that have no MEM_EXPR?

Good point, I should have checked that.

Here are the numbers after excluding cases that
mems_in_disjoint_alias_sets_p, nonoverlapping_memrefs_p and
rtx_refs_may_alias_p would disambiguate later.  This time I didn't
divide based on false/true, just based on the path taken:

  cmp == 1, overlap:    : 66.72%
  cmp == 1, no overlap  :  6.51%
  cmp == -1, overlap    :  0.06%
  cmp == -1. no overlap : 26.71% <--- the number that matters

The number of cases being disambiguated only by this function seems
surprisingly high.  Maybe that's a sign that we're losing too much
information somewhere?  Or maybe it's rtl constants vs. other stuff.

> Ideally we'd rely more on MEM_EXPR for alias disambiguation than the ad-hoc
> ways of recovering "details" from the actual MEM.

Yeah, agreed.

Thanks,
Richard

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Biener]

On Wed, Feb 19, 2020 at 4:12 PM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> Richard Biener <richard.guenther@gmail.com> writes:
> > On Wed, Feb 19, 2020 at 1:19 PM Richard Sandiford
> > <richard.sandiford@arm.com> wrote:
> >>
> >> What should we do about this?  The PR is a wrong-code regression from
> >> GCC 9 and it doesn't look like we can remove the second offset_overlap_p
> >> check, given how many cases currently rely on it.
> >
> > Did you check whether we eventually disambiguate those via rtx_refs_may_alias_p
> > (so using MEM_EXPR)?  I would guess all but those that have no MEM_EXPR?
>
> Good point, I should have checked that.
>
> Here are the numbers after excluding cases that
> mems_in_disjoint_alias_sets_p, nonoverlapping_memrefs_p and
> rtx_refs_may_alias_p would disambiguate later.  This time I didn't
> divide based on false/true, just based on the path taken:
>
>   cmp == 1, overlap:    : 66.72%
>   cmp == 1, no overlap  :  6.51%
>   cmp == -1, overlap    :  0.06%
>   cmp == -1. no overlap : 26.71% <--- the number that matters
>
> The number of cases being disambiguated only by this function seems
> surprisingly high.  Maybe that's a sign that we're losing too much
> information somewhere?  Or maybe it's rtl constants vs. other stuff.

No idea - you could print the rtxen involved to a temporary file and
look at them...
when I did that other statistic most cases were from postreload DSE
(which does O(n^2)
disambiguations...) against stack slots.

From what I've seen we're definitely eager to drop MEM_EXPR and lack
handling of late allocated stack space there.

> > Ideally we'd rely more on MEM_EXPR for alias disambiguation than the ad-hoc
> > ways of recovering "details" from the actual MEM.
>
> Yeah, agreed.
>
> Thanks,
> Richard

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Sandiford]

Jan Hubicka <hubicka@ucw.cz> writes:
>> On Mon, 18 Jan 2021, Richard Sandiford wrote:
>> 
>> > Jan Hubicka <hubicka@ucw.cz> writes:
>> > >> >> 
>> > >> >> Well, in tree-ssa code we do assume these to be either disjoint objects
>> > >> >> or equal (in decl_refs_may_alias_p that continues in case
>> > >> >> compare_base_decls is -1).  I am not sure if we win much by threating
>> > >> >> them differently on RTL level. I would preffer staying consistent here.
>> > >> 
>> > >> Yeah, I see your point.  My concern here was that the fallback case
>> > >> applies to SYMBOL_REFs without decls, which might not have been visible
>> > >> at the tree-ssa level.  E.g. they might be ABI-defined symbols that have
>> > >> no known relation to source-level constructs.
>> > >> 
>> > >> E.g. the small-data base symbol _gp on MIPS points at a fixed offset
>> > >> from the start of the small-data area (0x7ff0 IIRC).  If the target
>> > >> generated rtl code that used _gp directly, we could wrongly assume
>> > >> that _gp+X can't alias BASE+Y when X != Y, even though the real test
>> > >> for small-data BASEs would be whether X + 0x7ff0 != Y.
>> > >> 
>> > >> I don't think that could occur in tree-ssa.  No valid C code would
>> > >> be able to refer directly to _gp in this way.
>> > >> 
>> > >> On the other hand, I don't have a specific example of where this does
>> > >> go wrong, it's just a feeling that it might.  I can drop it if you
>> > >> think that's better.
>> > >
>> > > I would lean towards not disabling optimization when we have no good
>> > > reason for that - we already did it bit too many times in aliasing code
>> > > and it is hard to figure out what optimizations are missed purposefully
>> > > and what are missed just as omission.
>> > >
>> > > We already comitted to a very conservative assumption that every
>> > > external symbol can be alias of another. I think we should have
>> > > originally required units that reffers to same memory location via
>> > > different symbols to declare it explicitly (i.e. make external alias to
>> > > external symbol), but we do not even allow external aliases (symtab
>> > > supports that though) and also it may depend on use of the module what
>> > > symbols are aliased.
>> > >
>> > > We also decided to disable TBAA for direct accesses to decls to allow
>> > > type punning using unions.
>> > >
>> > > This keeps the offset+range check to be only means of disambiguation.
>> > > While for modern programs global arrays are not common, for Fortran
>> > > stuff they are, so I would preffer to not cripple them even more.
>> > > (I am not sure how often the arrays are external though)
>> > 
>> > OK, the version below drops the new -2 return value and tries to
>> > clarify the comments in compare_base_symbol_refs.
>> > 
>> > Lightly tested on aarch64-linux-gnu so far.  Does it look OK if
>> > full tests pass?
>> 
>> OK from my side.
>
> OK too, thanks!
> Honza

Thanks, pushed to master after testing on aarch64-linux-gnu,
aarch64_be-elf and x86_64-linux-gnu.  I don't think it's suitable
for backports.

Richard

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Jan Hubicka]

> On Mon, 18 Jan 2021, Richard Sandiford wrote:
> 
> > Jan Hubicka <hubicka@ucw.cz> writes:
> > >> >> 
> > >> >> Well, in tree-ssa code we do assume these to be either disjoint objects
> > >> >> or equal (in decl_refs_may_alias_p that continues in case
> > >> >> compare_base_decls is -1).  I am not sure if we win much by threating
> > >> >> them differently on RTL level. I would preffer staying consistent here.
> > >> 
> > >> Yeah, I see your point.  My concern here was that the fallback case
> > >> applies to SYMBOL_REFs without decls, which might not have been visible
> > >> at the tree-ssa level.  E.g. they might be ABI-defined symbols that have
> > >> no known relation to source-level constructs.
> > >> 
> > >> E.g. the small-data base symbol _gp on MIPS points at a fixed offset
> > >> from the start of the small-data area (0x7ff0 IIRC).  If the target
> > >> generated rtl code that used _gp directly, we could wrongly assume
> > >> that _gp+X can't alias BASE+Y when X != Y, even though the real test
> > >> for small-data BASEs would be whether X + 0x7ff0 != Y.
> > >> 
> > >> I don't think that could occur in tree-ssa.  No valid C code would
> > >> be able to refer directly to _gp in this way.
> > >> 
> > >> On the other hand, I don't have a specific example of where this does
> > >> go wrong, it's just a feeling that it might.  I can drop it if you
> > >> think that's better.
> > >
> > > I would lean towards not disabling optimization when we have no good
> > > reason for that - we already did it bit too many times in aliasing code
> > > and it is hard to figure out what optimizations are missed purposefully
> > > and what are missed just as omission.
> > >
> > > We already comitted to a very conservative assumption that every
> > > external symbol can be alias of another. I think we should have
> > > originally required units that reffers to same memory location via
> > > different symbols to declare it explicitly (i.e. make external alias to
> > > external symbol), but we do not even allow external aliases (symtab
> > > supports that though) and also it may depend on use of the module what
> > > symbols are aliased.
> > >
> > > We also decided to disable TBAA for direct accesses to decls to allow
> > > type punning using unions.
> > >
> > > This keeps the offset+range check to be only means of disambiguation.
> > > While for modern programs global arrays are not common, for Fortran
> > > stuff they are, so I would preffer to not cripple them even more.
> > > (I am not sure how often the arrays are external though)
> > 
> > OK, the version below drops the new -2 return value and tries to
> > clarify the comments in compare_base_symbol_refs.
> > 
> > Lightly tested on aarch64-linux-gnu so far.  Does it look OK if
> > full tests pass?
> 
> OK from my side.

OK too, thanks!
Honza
> 
> Richard.
> 
> > Thanks,
> > Richard
> > 
> > ----
> > 
> > memrefs_conflict_p assumes that:
> > 
> >   [XB + XO, XB + XO + XS)
> > 
> > does not alias
> > 
> >   [YB + YO, YB + YO + YS)
> > 
> > whenever:
> > 
> >   [XO, XO + XS)
> > 
> > does not intersect
> > 
> >   [YO, YO + YS)
> > 
> > In other words, the accesses can alias only if XB == YB at runtime.
> > 
> > However, this doesn't cope correctly with section anchors.
> > For example, if XB is an anchor symbol and YB is at offset
> > XO from the anchor, then:
> > 
> >   [XB + XO, XB + XO + XS)
> > 
> > overlaps
> > 
> >   [YB, YB + YS)
> > 
> > whatever the value of XO is.  In other words, when doing the
> > alias check for two symbols whose local definitions are in
> > the same block, we should apply the known difference between
> > their block offsets to the intersection test above.
> > 
> > gcc/
> > 	PR rtl-optimization/92294
> > 	* alias.c (compare_base_symbol_refs): Take an extra parameter
> > 	and add the distance between two symbols to it.  Enshrine in
> > 	comments that -1 means "either 0 or 1, but we can't tell
> > 	which at compile time".
> > 	(memrefs_conflict_p): Update call accordingly.
> > 	(rtx_equal_for_memref_p): Likewise.  Take the distance between symbols
> > 	into account.
> > ---
> >  gcc/alias.c | 47 +++++++++++++++++++++++++++++++----------------
> >  1 file changed, 31 insertions(+), 16 deletions(-)
> > 
> > diff --git a/gcc/alias.c b/gcc/alias.c
> > index 8d3575e4e27..69e1eb89ac6 100644
> > --- a/gcc/alias.c
> > +++ b/gcc/alias.c
> > @@ -159,7 +159,8 @@ static tree decl_for_component_ref (tree);
> >  static int write_dependence_p (const_rtx,
> >  			       const_rtx, machine_mode, rtx,
> >  			       bool, bool, bool);
> > -static int compare_base_symbol_refs (const_rtx, const_rtx);
> > +static int compare_base_symbol_refs (const_rtx, const_rtx,
> > +				     HOST_WIDE_INT * = NULL);
> >  
> >  static void memory_modified_1 (rtx, const_rtx, void *);
> >  
> > @@ -1837,7 +1838,11 @@ rtx_equal_for_memref_p (const_rtx x, const_rtx y)
> >        return label_ref_label (x) == label_ref_label (y);
> >  
> >      case SYMBOL_REF:
> > -      return compare_base_symbol_refs (x, y) == 1;
> > +      {
> > +	HOST_WIDE_INT distance = 0;
> > +	return (compare_base_symbol_refs (x, y, &distance) == 1
> > +		&& distance == 0);
> > +      }
> >  
> >      case ENTRY_VALUE:
> >        /* This is magic, don't go through canonicalization et al.  */
> > @@ -2172,10 +2177,20 @@ compare_base_decls (tree base1, tree base2)
> >    return ret;
> >  }
> >  
> > -/* Same as compare_base_decls but for SYMBOL_REF.  */
> > +/* Compare SYMBOL_REFs X_BASE and Y_BASE.
> > +
> > +   - Return 1 if Y_BASE - X_BASE is constant, adding that constant
> > +     to *DISTANCE if DISTANCE is nonnull.
> > +
> > +   - Return 0 if no accesses based on X_BASE can alias Y_BASE.
> > +
> > +   - Return -1 if one of the two results applies, but we can't tell
> > +     which at compile time.  Update DISTANCE in the same way as
> > +     for a return value of 1, for the case in which that holds.  */
> >  
> >  static int
> > -compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
> > +compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
> > +			  HOST_WIDE_INT *distance)
> >  {
> >    tree x_decl = SYMBOL_REF_DECL (x_base);
> >    tree y_decl = SYMBOL_REF_DECL (y_base);
> > @@ -2192,8 +2207,8 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
> >  	  std::swap (x_decl, y_decl);
> >  	  std::swap (x_base, y_base);
> >  	}
> > -      /* We handle specially only section anchors and assume that other
> > - 	 labels may overlap with user variables in an arbitrary way.  */
> > +      /* We handle specially only section anchors.  Other symbols are
> > +	 either equal (via aliasing) or refer to different objects.  */
> >        if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
> >          return -1;
> >        /* Anchors contains static VAR_DECLs and CONST_DECLs.  We are safe
> > @@ -2222,14 +2237,13 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
> >      {
> >        if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
> >  	return 0;
> > -      if (SYMBOL_REF_BLOCK_OFFSET (x_base) == SYMBOL_REF_BLOCK_OFFSET (y_base))
> > -	return binds_def ? 1 : -1;
> > -      if (SYMBOL_REF_ANCHOR_P (x_base) != SYMBOL_REF_ANCHOR_P (y_base))
> > -	return -1;
> > -      return 0;
> > +      if (distance)
> > +	*distance += (SYMBOL_REF_BLOCK_OFFSET (y_base)
> > +		      - SYMBOL_REF_BLOCK_OFFSET (x_base));
> > +      return binds_def ? 1 : -1;
> >      }
> > -  /* In general we assume that memory locations pointed to by different labels
> > -     may overlap in undefined ways.  */
> > +  /* Either the symbols are equal (via aliasing) or they refer to
> > +     different objects.  */
> >    return -1;
> >  }
> >  
> > @@ -2513,11 +2527,12 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
> >  
> >    if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
> >      {
> > -      int cmp = compare_base_symbol_refs (x,y);
> > +      HOST_WIDE_INT distance = 0;
> > +      int cmp = compare_base_symbol_refs (x, y, &distance);
> >  
> >        /* If both decls are the same, decide by offsets.  */
> >        if (cmp == 1)
> > -        return offset_overlap_p (c, xsize, ysize);
> > +	return offset_overlap_p (c + distance, xsize, ysize);
> >        /* 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
> > @@ -2526,7 +2541,7 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
> >  	return -1;
> >        /* If decls are different or we know by offsets that there is no overlap,
> >  	 we win.  */
> > -      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> > +      if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
> >  	return 0;
> >        /* Decls may or may not be different and offsets overlap....*/
> >        return -1;
> > 
> 
> -- 
> Richard Biener <rguenther@suse.de>
> SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
> Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Biener]

On Mon, 18 Jan 2021, Richard Sandiford wrote:

> Jan Hubicka <hubicka@ucw.cz> writes:
> >> >> 
> >> >> Well, in tree-ssa code we do assume these to be either disjoint objects
> >> >> or equal (in decl_refs_may_alias_p that continues in case
> >> >> compare_base_decls is -1).  I am not sure if we win much by threating
> >> >> them differently on RTL level. I would preffer staying consistent here.
> >> 
> >> Yeah, I see your point.  My concern here was that the fallback case
> >> applies to SYMBOL_REFs without decls, which might not have been visible
> >> at the tree-ssa level.  E.g. they might be ABI-defined symbols that have
> >> no known relation to source-level constructs.
> >> 
> >> E.g. the small-data base symbol _gp on MIPS points at a fixed offset
> >> from the start of the small-data area (0x7ff0 IIRC).  If the target
> >> generated rtl code that used _gp directly, we could wrongly assume
> >> that _gp+X can't alias BASE+Y when X != Y, even though the real test
> >> for small-data BASEs would be whether X + 0x7ff0 != Y.
> >> 
> >> I don't think that could occur in tree-ssa.  No valid C code would
> >> be able to refer directly to _gp in this way.
> >> 
> >> On the other hand, I don't have a specific example of where this does
> >> go wrong, it's just a feeling that it might.  I can drop it if you
> >> think that's better.
> >
> > I would lean towards not disabling optimization when we have no good
> > reason for that - we already did it bit too many times in aliasing code
> > and it is hard to figure out what optimizations are missed purposefully
> > and what are missed just as omission.
> >
> > We already comitted to a very conservative assumption that every
> > external symbol can be alias of another. I think we should have
> > originally required units that reffers to same memory location via
> > different symbols to declare it explicitly (i.e. make external alias to
> > external symbol), but we do not even allow external aliases (symtab
> > supports that though) and also it may depend on use of the module what
> > symbols are aliased.
> >
> > We also decided to disable TBAA for direct accesses to decls to allow
> > type punning using unions.
> >
> > This keeps the offset+range check to be only means of disambiguation.
> > While for modern programs global arrays are not common, for Fortran
> > stuff they are, so I would preffer to not cripple them even more.
> > (I am not sure how often the arrays are external though)
> 
> OK, the version below drops the new -2 return value and tries to
> clarify the comments in compare_base_symbol_refs.
> 
> Lightly tested on aarch64-linux-gnu so far.  Does it look OK if
> full tests pass?

OK from my side.

Richard.

> Thanks,
> Richard
> 
> ----
> 
> memrefs_conflict_p assumes that:
> 
>   [XB + XO, XB + XO + XS)
> 
> does not alias
> 
>   [YB + YO, YB + YO + YS)
> 
> whenever:
> 
>   [XO, XO + XS)
> 
> does not intersect
> 
>   [YO, YO + YS)
> 
> In other words, the accesses can alias only if XB == YB at runtime.
> 
> However, this doesn't cope correctly with section anchors.
> For example, if XB is an anchor symbol and YB is at offset
> XO from the anchor, then:
> 
>   [XB + XO, XB + XO + XS)
> 
> overlaps
> 
>   [YB, YB + YS)
> 
> whatever the value of XO is.  In other words, when doing the
> alias check for two symbols whose local definitions are in
> the same block, we should apply the known difference between
> their block offsets to the intersection test above.
> 
> gcc/
> 	PR rtl-optimization/92294
> 	* alias.c (compare_base_symbol_refs): Take an extra parameter
> 	and add the distance between two symbols to it.  Enshrine in
> 	comments that -1 means "either 0 or 1, but we can't tell
> 	which at compile time".
> 	(memrefs_conflict_p): Update call accordingly.
> 	(rtx_equal_for_memref_p): Likewise.  Take the distance between symbols
> 	into account.
> ---
>  gcc/alias.c | 47 +++++++++++++++++++++++++++++++----------------
>  1 file changed, 31 insertions(+), 16 deletions(-)
> 
> diff --git a/gcc/alias.c b/gcc/alias.c
> index 8d3575e4e27..69e1eb89ac6 100644
> --- a/gcc/alias.c
> +++ b/gcc/alias.c
> @@ -159,7 +159,8 @@ static tree decl_for_component_ref (tree);
>  static int write_dependence_p (const_rtx,
>  			       const_rtx, machine_mode, rtx,
>  			       bool, bool, bool);
> -static int compare_base_symbol_refs (const_rtx, const_rtx);
> +static int compare_base_symbol_refs (const_rtx, const_rtx,
> +				     HOST_WIDE_INT * = NULL);
>  
>  static void memory_modified_1 (rtx, const_rtx, void *);
>  
> @@ -1837,7 +1838,11 @@ rtx_equal_for_memref_p (const_rtx x, const_rtx y)
>        return label_ref_label (x) == label_ref_label (y);
>  
>      case SYMBOL_REF:
> -      return compare_base_symbol_refs (x, y) == 1;
> +      {
> +	HOST_WIDE_INT distance = 0;
> +	return (compare_base_symbol_refs (x, y, &distance) == 1
> +		&& distance == 0);
> +      }
>  
>      case ENTRY_VALUE:
>        /* This is magic, don't go through canonicalization et al.  */
> @@ -2172,10 +2177,20 @@ compare_base_decls (tree base1, tree base2)
>    return ret;
>  }
>  
> -/* Same as compare_base_decls but for SYMBOL_REF.  */
> +/* Compare SYMBOL_REFs X_BASE and Y_BASE.
> +
> +   - Return 1 if Y_BASE - X_BASE is constant, adding that constant
> +     to *DISTANCE if DISTANCE is nonnull.
> +
> +   - Return 0 if no accesses based on X_BASE can alias Y_BASE.
> +
> +   - Return -1 if one of the two results applies, but we can't tell
> +     which at compile time.  Update DISTANCE in the same way as
> +     for a return value of 1, for the case in which that holds.  */
>  
>  static int
> -compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
> +compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
> +			  HOST_WIDE_INT *distance)
>  {
>    tree x_decl = SYMBOL_REF_DECL (x_base);
>    tree y_decl = SYMBOL_REF_DECL (y_base);
> @@ -2192,8 +2207,8 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
>  	  std::swap (x_decl, y_decl);
>  	  std::swap (x_base, y_base);
>  	}
> -      /* We handle specially only section anchors and assume that other
> - 	 labels may overlap with user variables in an arbitrary way.  */
> +      /* We handle specially only section anchors.  Other symbols are
> +	 either equal (via aliasing) or refer to different objects.  */
>        if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
>          return -1;
>        /* Anchors contains static VAR_DECLs and CONST_DECLs.  We are safe
> @@ -2222,14 +2237,13 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
>      {
>        if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
>  	return 0;
> -      if (SYMBOL_REF_BLOCK_OFFSET (x_base) == SYMBOL_REF_BLOCK_OFFSET (y_base))
> -	return binds_def ? 1 : -1;
> -      if (SYMBOL_REF_ANCHOR_P (x_base) != SYMBOL_REF_ANCHOR_P (y_base))
> -	return -1;
> -      return 0;
> +      if (distance)
> +	*distance += (SYMBOL_REF_BLOCK_OFFSET (y_base)
> +		      - SYMBOL_REF_BLOCK_OFFSET (x_base));
> +      return binds_def ? 1 : -1;
>      }
> -  /* In general we assume that memory locations pointed to by different labels
> -     may overlap in undefined ways.  */
> +  /* Either the symbols are equal (via aliasing) or they refer to
> +     different objects.  */
>    return -1;
>  }
>  
> @@ -2513,11 +2527,12 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
>  
>    if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
>      {
> -      int cmp = compare_base_symbol_refs (x,y);
> +      HOST_WIDE_INT distance = 0;
> +      int cmp = compare_base_symbol_refs (x, y, &distance);
>  
>        /* If both decls are the same, decide by offsets.  */
>        if (cmp == 1)
> -        return offset_overlap_p (c, xsize, ysize);
> +	return offset_overlap_p (c + distance, xsize, ysize);
>        /* 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
> @@ -2526,7 +2541,7 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
>  	return -1;
>        /* If decls are different or we know by offsets that there is no overlap,
>  	 we win.  */
> -      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> +      if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
>  	return 0;
>        /* Decls may or may not be different and offsets overlap....*/
>        return -1;
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Sandiford]

Jan Hubicka <hubicka@ucw.cz> writes:
>> >> 
>> >> Well, in tree-ssa code we do assume these to be either disjoint objects
>> >> or equal (in decl_refs_may_alias_p that continues in case
>> >> compare_base_decls is -1).  I am not sure if we win much by threating
>> >> them differently on RTL level. I would preffer staying consistent here.
>> 
>> Yeah, I see your point.  My concern here was that the fallback case
>> applies to SYMBOL_REFs without decls, which might not have been visible
>> at the tree-ssa level.  E.g. they might be ABI-defined symbols that have
>> no known relation to source-level constructs.
>> 
>> E.g. the small-data base symbol _gp on MIPS points at a fixed offset
>> from the start of the small-data area (0x7ff0 IIRC).  If the target
>> generated rtl code that used _gp directly, we could wrongly assume
>> that _gp+X can't alias BASE+Y when X != Y, even though the real test
>> for small-data BASEs would be whether X + 0x7ff0 != Y.
>> 
>> I don't think that could occur in tree-ssa.  No valid C code would
>> be able to refer directly to _gp in this way.
>> 
>> On the other hand, I don't have a specific example of where this does
>> go wrong, it's just a feeling that it might.  I can drop it if you
>> think that's better.
>
> I would lean towards not disabling optimization when we have no good
> reason for that - we already did it bit too many times in aliasing code
> and it is hard to figure out what optimizations are missed purposefully
> and what are missed just as omission.
>
> We already comitted to a very conservative assumption that every
> external symbol can be alias of another. I think we should have
> originally required units that reffers to same memory location via
> different symbols to declare it explicitly (i.e. make external alias to
> external symbol), but we do not even allow external aliases (symtab
> supports that though) and also it may depend on use of the module what
> symbols are aliased.
>
> We also decided to disable TBAA for direct accesses to decls to allow
> type punning using unions.
>
> This keeps the offset+range check to be only means of disambiguation.
> While for modern programs global arrays are not common, for Fortran
> stuff they are, so I would preffer to not cripple them even more.
> (I am not sure how often the arrays are external though)

OK, the version below drops the new -2 return value and tries to
clarify the comments in compare_base_symbol_refs.

Lightly tested on aarch64-linux-gnu so far.  Does it look OK if
full tests pass?

Thanks,
Richard

----

memrefs_conflict_p assumes that:

  [XB + XO, XB + XO + XS)

does not alias

  [YB + YO, YB + YO + YS)

whenever:

  [XO, XO + XS)

does not intersect

  [YO, YO + YS)

In other words, the accesses can alias only if XB == YB at runtime.

However, this doesn't cope correctly with section anchors.
For example, if XB is an anchor symbol and YB is at offset
XO from the anchor, then:

  [XB + XO, XB + XO + XS)

overlaps

  [YB, YB + YS)

whatever the value of XO is.  In other words, when doing the
alias check for two symbols whose local definitions are in
the same block, we should apply the known difference between
their block offsets to the intersection test above.

gcc/
	PR rtl-optimization/92294
	* alias.c (compare_base_symbol_refs): Take an extra parameter
	and add the distance between two symbols to it.  Enshrine in
	comments that -1 means "either 0 or 1, but we can't tell
	which at compile time".
	(memrefs_conflict_p): Update call accordingly.
	(rtx_equal_for_memref_p): Likewise.  Take the distance between symbols
	into account.
---
 gcc/alias.c | 47 +++++++++++++++++++++++++++++++----------------
 1 file changed, 31 insertions(+), 16 deletions(-)

diff --git a/gcc/alias.c b/gcc/alias.c
index 8d3575e4e27..69e1eb89ac6 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -159,7 +159,8 @@ static tree decl_for_component_ref (tree);
 static int write_dependence_p (const_rtx,
 			       const_rtx, machine_mode, rtx,
 			       bool, bool, bool);
-static int compare_base_symbol_refs (const_rtx, const_rtx);
+static int compare_base_symbol_refs (const_rtx, const_rtx,
+				     HOST_WIDE_INT * = NULL);
 
 static void memory_modified_1 (rtx, const_rtx, void *);
 
@@ -1837,7 +1838,11 @@ rtx_equal_for_memref_p (const_rtx x, const_rtx y)
       return label_ref_label (x) == label_ref_label (y);
 
     case SYMBOL_REF:
-      return compare_base_symbol_refs (x, y) == 1;
+      {
+	HOST_WIDE_INT distance = 0;
+	return (compare_base_symbol_refs (x, y, &distance) == 1
+		&& distance == 0);
+      }
 
     case ENTRY_VALUE:
       /* This is magic, don't go through canonicalization et al.  */
@@ -2172,10 +2177,20 @@ compare_base_decls (tree base1, tree base2)
   return ret;
 }
 
-/* Same as compare_base_decls but for SYMBOL_REF.  */
+/* Compare SYMBOL_REFs X_BASE and Y_BASE.
+
+   - Return 1 if Y_BASE - X_BASE is constant, adding that constant
+     to *DISTANCE if DISTANCE is nonnull.
+
+   - Return 0 if no accesses based on X_BASE can alias Y_BASE.
+
+   - Return -1 if one of the two results applies, but we can't tell
+     which at compile time.  Update DISTANCE in the same way as
+     for a return value of 1, for the case in which that holds.  */
 
 static int
-compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
+compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
+			  HOST_WIDE_INT *distance)
 {
   tree x_decl = SYMBOL_REF_DECL (x_base);
   tree y_decl = SYMBOL_REF_DECL (y_base);
@@ -2192,8 +2207,8 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
 	  std::swap (x_decl, y_decl);
 	  std::swap (x_base, y_base);
 	}
-      /* We handle specially only section anchors and assume that other
- 	 labels may overlap with user variables in an arbitrary way.  */
+      /* We handle specially only section anchors.  Other symbols are
+	 either equal (via aliasing) or refer to different objects.  */
       if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
         return -1;
       /* Anchors contains static VAR_DECLs and CONST_DECLs.  We are safe
@@ -2222,14 +2237,13 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
     {
       if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
 	return 0;
-      if (SYMBOL_REF_BLOCK_OFFSET (x_base) == SYMBOL_REF_BLOCK_OFFSET (y_base))
-	return binds_def ? 1 : -1;
-      if (SYMBOL_REF_ANCHOR_P (x_base) != SYMBOL_REF_ANCHOR_P (y_base))
-	return -1;
-      return 0;
+      if (distance)
+	*distance += (SYMBOL_REF_BLOCK_OFFSET (y_base)
+		      - SYMBOL_REF_BLOCK_OFFSET (x_base));
+      return binds_def ? 1 : -1;
     }
-  /* In general we assume that memory locations pointed to by different labels
-     may overlap in undefined ways.  */
+  /* Either the symbols are equal (via aliasing) or they refer to
+     different objects.  */
   return -1;
 }
 
@@ -2513,11 +2527,12 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
 
   if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
     {
-      int cmp = compare_base_symbol_refs (x,y);
+      HOST_WIDE_INT distance = 0;
+      int cmp = compare_base_symbol_refs (x, y, &distance);
 
       /* If both decls are the same, decide by offsets.  */
       if (cmp == 1)
-        return offset_overlap_p (c, xsize, ysize);
+	return offset_overlap_p (c + distance, xsize, ysize);
       /* 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
@@ -2526,7 +2541,7 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
 	return -1;
       /* If decls are different or we know by offsets that there is no overlap,
 	 we win.  */
-      if (!cmp || !offset_overlap_p (c, xsize, ysize))
+      if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
 	return 0;
       /* Decls may or may not be different and offsets overlap....*/
       return -1;

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Jan Hubicka]

> >> 
> >> Well, in tree-ssa code we do assume these to be either disjoint objects
> >> or equal (in decl_refs_may_alias_p that continues in case
> >> compare_base_decls is -1).  I am not sure if we win much by threating
> >> them differently on RTL level. I would preffer staying consistent here.
> 
> Yeah, I see your point.  My concern here was that the fallback case
> applies to SYMBOL_REFs without decls, which might not have been visible
> at the tree-ssa level.  E.g. they might be ABI-defined symbols that have
> no known relation to source-level constructs.
> 
> E.g. the small-data base symbol _gp on MIPS points at a fixed offset
> from the start of the small-data area (0x7ff0 IIRC).  If the target
> generated rtl code that used _gp directly, we could wrongly assume
> that _gp+X can't alias BASE+Y when X != Y, even though the real test
> for small-data BASEs would be whether X + 0x7ff0 != Y.
> 
> I don't think that could occur in tree-ssa.  No valid C code would
> be able to refer directly to _gp in this way.
> 
> On the other hand, I don't have a specific example of where this does
> go wrong, it's just a feeling that it might.  I can drop it if you
> think that's better.

I would lean towards not disabling optimization when we have no good
reason for that - we already did it bit too many times in aliasing code
and it is hard to figure out what optimizations are missed purposefully
and what are missed just as omission.

We already comitted to a very conservative assumption that every
external symbol can be alias of another. I think we should have
originally required units that reffers to same memory location via
different symbols to declare it explicitly (i.e. make external alias to
external symbol), but we do not even allow external aliases (symtab
supports that though) and also it may depend on use of the module what
symbols are aliased.

We also decided to disable TBAA for direct accesses to decls to allow
type punning using unions.

This keeps the offset+range check to be only means of disambiguation.
While for modern programs global arrays are not common, for Fortran
stuff they are, so I would preffer to not cripple them even more.
(I am not sure how often the arrays are external though)

Perhaps we could simply test if symbol has associated decl and be
conservative for symbols w/o decl.

It is however just my preference.  I can live with being conservative
everywhere.

Honza
> 
> > So that's because if an alias (via alias attribute) is not visible
> > then it can be assumed to not exist.  Which means the bug is that
> > with section anchors we do not know which variables can be refered
> > to via the specific anchor?
> 
> No, we do know that.
> 
> > (if there's something like a "specific"
> > anchor)  That looks like the actual defect to me?  I see we have
> > block_symbol and object_block which may have all the data needed
> > in case accesses are somehow well-constrained?
> 
> Right.  And the patch does take advantage of that information.
> E.g. the existing:
> 
>       if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
> 	return 0;
> 
> says that symbols can't alias if they're known to belong to different
> blocks.  And if symbols are in the same block, the behaviour of the
> patch is to adjust the relative offsets to account for the positions
> of the symbols in the block.
> 
> The problem is just that “unequal offsets imply no alias” doesn't
> hold for section anchors.  The offset of the symbol from an anchor
> has to be taken into account.  If we have:
> 
>   (symbol_ref X)
>   (plus (symbol_ref ANCHOR) Y) == unpreempted X
> 
> then ignoring Y gives two false results, a false positive and a false
> negative:
> 
> (a) the existing code might wrongly assume that an access to X+0 could
>     alias an access to ANCHOR+0, because the offsets are equal.
> 
> (b) the existing code would wrongly assume that an access to X+0 can't
>     alias an access to ANCHOR+Y, because the offsets are unequal.
> 
> The relative offset has to be adjusted by Y first, before applying
> the “unequal offsets imply no alias” rule.
> 
> >> Otheriwse the patch looks good to me.
> >
> > So let's go with it?  It looks like for decl vs. section anchor we
> > can identify the offset of the decl in the anchor block and thus
> > determine a offset adjustment necessary to perform an offset based
> > check, no?
> 
> Yeah, that's what the patch is trying to do.
> 
> Thanks,
> Richard

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Sandiford]

Richard Biener <rguenther@suse.de> writes:
> On Mon, 18 Jan 2021, Jan Hubicka wrote:
>
>> > This is a repost of:
>> > 
>> >   https://gcc.gnu.org/pipermail/gcc-patches/2020-February/539763.html
>> > 
>> > which was initially posted during stage 4.  (And yeah, I only just
>> > missed stage 4 again.)
>> > 
>> > IMO it would be better to fix the bug directly (as the patch tries
>> > to do) instead of wait for a more thorough redesign of this area.
>> > See the end of:
>> > 
>> >   https://gcc.gnu.org/pipermail/gcc-patches/2020-February/540002.html
>> > 
>> > for some stats.
>> > 
>> > Honza: Richard said he'd like your opinion on the patch.
>> > 
>> > 
>> > memrefs_conflict_p has a slightly odd structure.  It first checks
>> > whether two addresses based on SYMBOL_REFs refer to the same object,
>> > with a tristate result:
>> > 
>> >       int cmp = compare_base_symbol_refs (x,y);
>> > 
>> > If the addresses do refer to the same object, we can use offset-based checks:
>> > 
>> >       /* If both decls are the same, decide by offsets.  */
>> >       if (cmp == 1)
>> >         return offset_overlap_p (c, xsize, ysize);
>> > 
>> > But then, apart from the special case of forced address alignment,
>> > we use an offset-based check even if we don't know whether the
>> > addresses refer to the same object:
>> > 
>> >       /* 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 (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
>> > 	return -1;
>> >       /* If decls are different or we know by offsets that there is no overlap,
>> > 	 we win.  */
>> >       if (!cmp || !offset_overlap_p (c, xsize, ysize))
>> > 	return 0;
>> > 
>> > This somewhat contradicts:
>> > 
>> >   /* In general we assume that memory locations pointed to by different labels
>> >      may overlap in undefined ways.  */
>> 
>> I suppose it is becuase the code above check for SYMBOL_REF and not
>> label (that is probably about jumptables and constpool injected into
>> text segment).
>> 
>> I assume this is also bit result of GCC not being very systematic about
>> aliases.  Sometimes it assumes that two different symbols do not point
>> to same object while in other cases it is worried about aliases.
>> 
>> I see that anchors are special since they point to "same object" with
>> different offests.
>> > 
>> > at the end of compare_base_symbol_refs.  In other words, we're taking -1
>> > to mean that either (a) the symbols are equal (via aliasing) or (b) the
>> > references access non-overlapping objects.
>> 
>> I for symbol refs yes, I think so.
>> > 
>> > But even assuming that's true for normal symbols, it doesn't cope
>> > correctly with section anchors.  If a symbol X at ANCHOR+OFFSET is
>> > preemptible, either (a) X = ANCHOR+OFFSET (rather than the X = ANCHOR
>> > assumed above) or (b) X and ANCHOR reference non-overlapping objects.
>> > 
>> > And an offset-based comparison makes no sense for an anchor symbol
>> > vs. a bare symbol with no decl.  If the bare symbol is allowed to
>> > alias other symbols then it can surely alias any symbol in the
>> > anchor's block, so there are multiple anchor offsets that might
>> > induce an alias.
>> > 
>> > This patch therefore replaces the current tristate:
>> > 
>> >   - known equal
>> >   - known independent (two accesses can't alias)
>> >   - equal or independent
>> > 
>> > with:
>> > 
>> >   - known distance apart
>> >   - known independent (two accesses can't alias)
>> >   - known distance apart or independent
>> >   - don't know
>> > 
>> > For safety, the patch puts all bare symbols in the "don't know"
>> > category.  If that turns out to be too conservative, we at least
>> > need that behaviour for combinations involving a bare symbol
>> > and a section anchor.  However, bare symbols should be relatively
>> > rare these days.
>> 
>> Well, in tree-ssa code we do assume these to be either disjoint objects
>> or equal (in decl_refs_may_alias_p that continues in case
>> compare_base_decls is -1).  I am not sure if we win much by threating
>> them differently on RTL level. I would preffer staying consistent here.

Yeah, I see your point.  My concern here was that the fallback case
applies to SYMBOL_REFs without decls, which might not have been visible
at the tree-ssa level.  E.g. they might be ABI-defined symbols that have
no known relation to source-level constructs.

E.g. the small-data base symbol _gp on MIPS points at a fixed offset
from the start of the small-data area (0x7ff0 IIRC).  If the target
generated rtl code that used _gp directly, we could wrongly assume
that _gp+X can't alias BASE+Y when X != Y, even though the real test
for small-data BASEs would be whether X + 0x7ff0 != Y.

I don't think that could occur in tree-ssa.  No valid C code would
be able to refer directly to _gp in this way.

On the other hand, I don't have a specific example of where this does
go wrong, it's just a feeling that it might.  I can drop it if you
think that's better.

> So that's because if an alias (via alias attribute) is not visible
> then it can be assumed to not exist.  Which means the bug is that
> with section anchors we do not know which variables can be refered
> to via the specific anchor?

No, we do know that.

> (if there's something like a "specific"
> anchor)  That looks like the actual defect to me?  I see we have
> block_symbol and object_block which may have all the data needed
> in case accesses are somehow well-constrained?

Right.  And the patch does take advantage of that information.
E.g. the existing:

      if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
	return 0;

says that symbols can't alias if they're known to belong to different
blocks.  And if symbols are in the same block, the behaviour of the
patch is to adjust the relative offsets to account for the positions
of the symbols in the block.

The problem is just that “unequal offsets imply no alias” doesn't
hold for section anchors.  The offset of the symbol from an anchor
has to be taken into account.  If we have:

  (symbol_ref X)
  (plus (symbol_ref ANCHOR) Y) == unpreempted X

then ignoring Y gives two false results, a false positive and a false
negative:

(a) the existing code might wrongly assume that an access to X+0 could
    alias an access to ANCHOR+0, because the offsets are equal.

(b) the existing code would wrongly assume that an access to X+0 can't
    alias an access to ANCHOR+Y, because the offsets are unequal.

The relative offset has to be adjusted by Y first, before applying
the “unequal offsets imply no alias” rule.

>> Otheriwse the patch looks good to me.
>
> So let's go with it?  It looks like for decl vs. section anchor we
> can identify the offset of the decl in the anchor block and thus
> determine a offset adjustment necessary to perform an offset based
> check, no?

Yeah, that's what the patch is trying to do.

Thanks,
Richard

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Biener]

On Mon, 18 Jan 2021, Jan Hubicka wrote:

> > This is a repost of:
> > 
> >   https://gcc.gnu.org/pipermail/gcc-patches/2020-February/539763.html
> > 
> > which was initially posted during stage 4.  (And yeah, I only just
> > missed stage 4 again.)
> > 
> > IMO it would be better to fix the bug directly (as the patch tries
> > to do) instead of wait for a more thorough redesign of this area.
> > See the end of:
> > 
> >   https://gcc.gnu.org/pipermail/gcc-patches/2020-February/540002.html
> > 
> > for some stats.
> > 
> > Honza: Richard said he'd like your opinion on the patch.
> > 
> > 
> > memrefs_conflict_p has a slightly odd structure.  It first checks
> > whether two addresses based on SYMBOL_REFs refer to the same object,
> > with a tristate result:
> > 
> >       int cmp = compare_base_symbol_refs (x,y);
> > 
> > If the addresses do refer to the same object, we can use offset-based checks:
> > 
> >       /* If both decls are the same, decide by offsets.  */
> >       if (cmp == 1)
> >         return offset_overlap_p (c, xsize, ysize);
> > 
> > But then, apart from the special case of forced address alignment,
> > we use an offset-based check even if we don't know whether the
> > addresses refer to the same object:
> > 
> >       /* 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 (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
> > 	return -1;
> >       /* If decls are different or we know by offsets that there is no overlap,
> > 	 we win.  */
> >       if (!cmp || !offset_overlap_p (c, xsize, ysize))
> > 	return 0;
> > 
> > This somewhat contradicts:
> > 
> >   /* In general we assume that memory locations pointed to by different labels
> >      may overlap in undefined ways.  */
> 
> I suppose it is becuase the code above check for SYMBOL_REF and not
> label (that is probably about jumptables and constpool injected into
> text segment).
> 
> I assume this is also bit result of GCC not being very systematic about
> aliases.  Sometimes it assumes that two different symbols do not point
> to same object while in other cases it is worried about aliases.
> 
> I see that anchors are special since they point to "same object" with
> different offests.
> > 
> > at the end of compare_base_symbol_refs.  In other words, we're taking -1
> > to mean that either (a) the symbols are equal (via aliasing) or (b) the
> > references access non-overlapping objects.
> 
> I for symbol refs yes, I think so.
> > 
> > But even assuming that's true for normal symbols, it doesn't cope
> > correctly with section anchors.  If a symbol X at ANCHOR+OFFSET is
> > preemptible, either (a) X = ANCHOR+OFFSET (rather than the X = ANCHOR
> > assumed above) or (b) X and ANCHOR reference non-overlapping objects.
> > 
> > And an offset-based comparison makes no sense for an anchor symbol
> > vs. a bare symbol with no decl.  If the bare symbol is allowed to
> > alias other symbols then it can surely alias any symbol in the
> > anchor's block, so there are multiple anchor offsets that might
> > induce an alias.
> > 
> > This patch therefore replaces the current tristate:
> > 
> >   - known equal
> >   - known independent (two accesses can't alias)
> >   - equal or independent
> > 
> > with:
> > 
> >   - known distance apart
> >   - known independent (two accesses can't alias)
> >   - known distance apart or independent
> >   - don't know
> > 
> > For safety, the patch puts all bare symbols in the "don't know"
> > category.  If that turns out to be too conservative, we at least
> > need that behaviour for combinations involving a bare symbol
> > and a section anchor.  However, bare symbols should be relatively
> > rare these days.
> 
> Well, in tree-ssa code we do assume these to be either disjoint objects
> or equal (in decl_refs_may_alias_p that continues in case
> compare_base_decls is -1).  I am not sure if we win much by threating
> them differently on RTL level. I would preffer staying consistent here.

So that's because if an alias (via alias attribute) is not visible
then it can be assumed to not exist.  Which means the bug is that
with section anchors we do not know which variables can be refered
to via the specific anchor? (if there's something like a "specific"
anchor)  That looks like the actual defect to me?  I see we have
block_symbol and object_block which may have all the data needed
in case accesses are somehow well-constrained?

> Otheriwse the patch looks good to me.

So let's go with it?  It looks like for decl vs. section anchor we
can identify the offset of the decl in the anchor block and thus
determine a offset adjustment necessary to perform an offset based
check, no?

Richard.

> Honza
> > 
> > Retested on aarch64-linux-gnu, aarch64_be-elf and x86_64-linux-gnu.
> > OK to install?
> > 
> > Richard
> > 
> > 
> > gcc/
> > 	PR rtl-optimization/92294
> > 	* alias.c (compare_base_symbol_refs): Take an extra parameter
> > 	and add the distance between two symbols to it.  Enshrine in
> > 	comments that -1 means "either 0 or 1, but we can't tell
> > 	which at compile time".  Return -2 for symbols whose
> > 	relationship is unknown.
> > 	(memrefs_conflict_p): Update call accordingly.
> > 	(rtx_equal_for_memref_p): Likewise.  Punt for a return value of -2,
> > 	without even checking the offset.  Take the distance between symbols
> > 	into account.
> > ---
> >  gcc/alias.c | 53 ++++++++++++++++++++++++++++++++++++++---------------
> >  1 file changed, 38 insertions(+), 15 deletions(-)
> > 
> > diff --git a/gcc/alias.c b/gcc/alias.c
> > index 8d3575e4e27..e22863a929a 100644
> > --- a/gcc/alias.c
> > +++ b/gcc/alias.c
> > @@ -159,7 +159,8 @@ static tree decl_for_component_ref (tree);
> >  static int write_dependence_p (const_rtx,
> >  			       const_rtx, machine_mode, rtx,
> >  			       bool, bool, bool);
> > -static int compare_base_symbol_refs (const_rtx, const_rtx);
> > +static int compare_base_symbol_refs (const_rtx, const_rtx,
> > +				     HOST_WIDE_INT * = NULL);
> >  
> >  static void memory_modified_1 (rtx, const_rtx, void *);
> >  
> > @@ -1837,7 +1838,11 @@ rtx_equal_for_memref_p (const_rtx x, const_rtx y)
> >        return label_ref_label (x) == label_ref_label (y);
> >  
> >      case SYMBOL_REF:
> > -      return compare_base_symbol_refs (x, y) == 1;
> > +      {
> > +	HOST_WIDE_INT distance = 0;
> > +	return (compare_base_symbol_refs (x, y, &distance) == 1
> > +		&& distance == 0);
> > +      }
> >  
> >      case ENTRY_VALUE:
> >        /* This is magic, don't go through canonicalization et al.  */
> > @@ -2172,10 +2177,24 @@ compare_base_decls (tree base1, tree base2)
> >    return ret;
> >  }
> >  
> > -/* Same as compare_base_decls but for SYMBOL_REF.  */
> > +/* Compare SYMBOL_REFs X_BASE and Y_BASE.
> > +
> > +   - Return 1 if Y_BASE - X_BASE is constant, adding that constant
> > +     to *DISTANCE if DISTANCE is nonnull.
> > +
> > +   - Return 0 if no valid accesses based on X_BASE can alias valid
> > +     accesses based on Y_BASE.
> > +
> > +   - Return -1 if one of the two results above applies, but we can't
> > +     tell which at compile time.  Update DISTANCE in the same way as
> > +     for a return value of 1, for the case in which that result holds
> > +     at runtime.
> > +
> > +   - Return -2 otherwise.  */
> >  
> >  static int
> > -compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
> > +compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
> > +			  HOST_WIDE_INT *distance)
> >  {
> >    tree x_decl = SYMBOL_REF_DECL (x_base);
> >    tree y_decl = SYMBOL_REF_DECL (y_base);
> > @@ -2195,7 +2214,7 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
> >        /* We handle specially only section anchors and assume that other
> >   	 labels may overlap with user variables in an arbitrary way.  */
> >        if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
> > -        return -1;
> > +	return -2;
> >        /* Anchors contains static VAR_DECLs and CONST_DECLs.  We are safe
> >  	 to ignore CONST_DECLs because they are readonly.  */
> >        if (!VAR_P (x_decl)
> > @@ -2222,15 +2241,14 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
> >      {
> >        if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
> >  	return 0;
> > -      if (SYMBOL_REF_BLOCK_OFFSET (x_base) == SYMBOL_REF_BLOCK_OFFSET (y_base))
> > -	return binds_def ? 1 : -1;
> > -      if (SYMBOL_REF_ANCHOR_P (x_base) != SYMBOL_REF_ANCHOR_P (y_base))
> > -	return -1;
> > -      return 0;
> > +      if (distance)
> > +	*distance += (SYMBOL_REF_BLOCK_OFFSET (y_base)
> > +		      - SYMBOL_REF_BLOCK_OFFSET (x_base));
> > +      return binds_def ? 1 : -1;
> >      }
> >    /* In general we assume that memory locations pointed to by different labels
> >       may overlap in undefined ways.  */
> > -  return -1;
> > +  return -2;
> >  }
> >  
> >  /* Return 0 if the addresses X and Y are known to point to different
> > @@ -2513,11 +2531,16 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
> >  
> >    if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
> >      {
> > -      int cmp = compare_base_symbol_refs (x,y);
> > +      HOST_WIDE_INT distance = 0;
> > +      int cmp = compare_base_symbol_refs (x, y, &distance);
> >  
> > -      /* If both decls are the same, decide by offsets.  */
> > +      /* Punt if we have no information about the relationship between
> > +	 X and Y.  */
> > +      if (cmp == -2)
> > +	return -1;
> > +      /* If the symbols are a known distance apart, decide by offsets.  */
> >        if (cmp == 1)
> > -        return offset_overlap_p (c, xsize, ysize);
> > +	return offset_overlap_p (c + distance, xsize, ysize);
> >        /* 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
> > @@ -2526,7 +2549,7 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
> >  	return -1;
> >        /* If decls are different or we know by offsets that there is no overlap,
> >  	 we win.  */
> > -      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> > +      if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
> >  	return 0;
> >        /* Decls may or may not be different and offsets overlap....*/
> >        return -1;
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)

Re: [PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Jan Hubicka]

> This is a repost of:
> 
>   https://gcc.gnu.org/pipermail/gcc-patches/2020-February/539763.html
> 
> which was initially posted during stage 4.  (And yeah, I only just
> missed stage 4 again.)
> 
> IMO it would be better to fix the bug directly (as the patch tries
> to do) instead of wait for a more thorough redesign of this area.
> See the end of:
> 
>   https://gcc.gnu.org/pipermail/gcc-patches/2020-February/540002.html
> 
> for some stats.
> 
> Honza: Richard said he'd like your opinion on the patch.
> 
> 
> memrefs_conflict_p has a slightly odd structure.  It first checks
> whether two addresses based on SYMBOL_REFs refer to the same object,
> with a tristate result:
> 
>       int cmp = compare_base_symbol_refs (x,y);
> 
> If the addresses do refer to the same object, we can use offset-based checks:
> 
>       /* If both decls are the same, decide by offsets.  */
>       if (cmp == 1)
>         return offset_overlap_p (c, xsize, ysize);
> 
> But then, apart from the special case of forced address alignment,
> we use an offset-based check even if we don't know whether the
> addresses refer to the same object:
> 
>       /* 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 (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
> 	return -1;
>       /* If decls are different or we know by offsets that there is no overlap,
> 	 we win.  */
>       if (!cmp || !offset_overlap_p (c, xsize, ysize))
> 	return 0;
> 
> This somewhat contradicts:
> 
>   /* In general we assume that memory locations pointed to by different labels
>      may overlap in undefined ways.  */

I suppose it is becuase the code above check for SYMBOL_REF and not
label (that is probably about jumptables and constpool injected into
text segment).

I assume this is also bit result of GCC not being very systematic about
aliases.  Sometimes it assumes that two different symbols do not point
to same object while in other cases it is worried about aliases.

I see that anchors are special since they point to "same object" with
different offests.
> 
> at the end of compare_base_symbol_refs.  In other words, we're taking -1
> to mean that either (a) the symbols are equal (via aliasing) or (b) the
> references access non-overlapping objects.

I for symbol refs yes, I think so.
> 
> But even assuming that's true for normal symbols, it doesn't cope
> correctly with section anchors.  If a symbol X at ANCHOR+OFFSET is
> preemptible, either (a) X = ANCHOR+OFFSET (rather than the X = ANCHOR
> assumed above) or (b) X and ANCHOR reference non-overlapping objects.
> 
> And an offset-based comparison makes no sense for an anchor symbol
> vs. a bare symbol with no decl.  If the bare symbol is allowed to
> alias other symbols then it can surely alias any symbol in the
> anchor's block, so there are multiple anchor offsets that might
> induce an alias.
> 
> This patch therefore replaces the current tristate:
> 
>   - known equal
>   - known independent (two accesses can't alias)
>   - equal or independent
> 
> with:
> 
>   - known distance apart
>   - known independent (two accesses can't alias)
>   - known distance apart or independent
>   - don't know
> 
> For safety, the patch puts all bare symbols in the "don't know"
> category.  If that turns out to be too conservative, we at least
> need that behaviour for combinations involving a bare symbol
> and a section anchor.  However, bare symbols should be relatively
> rare these days.

Well, in tree-ssa code we do assume these to be either disjoint objects
or equal (in decl_refs_may_alias_p that continues in case
compare_base_decls is -1).  I am not sure if we win much by threating
them differently on RTL level. I would preffer staying consistent here.

Otheriwse the patch looks good to me.

Honza
> 
> Retested on aarch64-linux-gnu, aarch64_be-elf and x86_64-linux-gnu.
> OK to install?
> 
> Richard
> 
> 
> gcc/
> 	PR rtl-optimization/92294
> 	* alias.c (compare_base_symbol_refs): Take an extra parameter
> 	and add the distance between two symbols to it.  Enshrine in
> 	comments that -1 means "either 0 or 1, but we can't tell
> 	which at compile time".  Return -2 for symbols whose
> 	relationship is unknown.
> 	(memrefs_conflict_p): Update call accordingly.
> 	(rtx_equal_for_memref_p): Likewise.  Punt for a return value of -2,
> 	without even checking the offset.  Take the distance between symbols
> 	into account.
> ---
>  gcc/alias.c | 53 ++++++++++++++++++++++++++++++++++++++---------------
>  1 file changed, 38 insertions(+), 15 deletions(-)
> 
> diff --git a/gcc/alias.c b/gcc/alias.c
> index 8d3575e4e27..e22863a929a 100644
> --- a/gcc/alias.c
> +++ b/gcc/alias.c
> @@ -159,7 +159,8 @@ static tree decl_for_component_ref (tree);
>  static int write_dependence_p (const_rtx,
>  			       const_rtx, machine_mode, rtx,
>  			       bool, bool, bool);
> -static int compare_base_symbol_refs (const_rtx, const_rtx);
> +static int compare_base_symbol_refs (const_rtx, const_rtx,
> +				     HOST_WIDE_INT * = NULL);
>  
>  static void memory_modified_1 (rtx, const_rtx, void *);
>  
> @@ -1837,7 +1838,11 @@ rtx_equal_for_memref_p (const_rtx x, const_rtx y)
>        return label_ref_label (x) == label_ref_label (y);
>  
>      case SYMBOL_REF:
> -      return compare_base_symbol_refs (x, y) == 1;
> +      {
> +	HOST_WIDE_INT distance = 0;
> +	return (compare_base_symbol_refs (x, y, &distance) == 1
> +		&& distance == 0);
> +      }
>  
>      case ENTRY_VALUE:
>        /* This is magic, don't go through canonicalization et al.  */
> @@ -2172,10 +2177,24 @@ compare_base_decls (tree base1, tree base2)
>    return ret;
>  }
>  
> -/* Same as compare_base_decls but for SYMBOL_REF.  */
> +/* Compare SYMBOL_REFs X_BASE and Y_BASE.
> +
> +   - Return 1 if Y_BASE - X_BASE is constant, adding that constant
> +     to *DISTANCE if DISTANCE is nonnull.
> +
> +   - Return 0 if no valid accesses based on X_BASE can alias valid
> +     accesses based on Y_BASE.
> +
> +   - Return -1 if one of the two results above applies, but we can't
> +     tell which at compile time.  Update DISTANCE in the same way as
> +     for a return value of 1, for the case in which that result holds
> +     at runtime.
> +
> +   - Return -2 otherwise.  */
>  
>  static int
> -compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
> +compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
> +			  HOST_WIDE_INT *distance)
>  {
>    tree x_decl = SYMBOL_REF_DECL (x_base);
>    tree y_decl = SYMBOL_REF_DECL (y_base);
> @@ -2195,7 +2214,7 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
>        /* We handle specially only section anchors and assume that other
>   	 labels may overlap with user variables in an arbitrary way.  */
>        if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
> -        return -1;
> +	return -2;
>        /* Anchors contains static VAR_DECLs and CONST_DECLs.  We are safe
>  	 to ignore CONST_DECLs because they are readonly.  */
>        if (!VAR_P (x_decl)
> @@ -2222,15 +2241,14 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
>      {
>        if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
>  	return 0;
> -      if (SYMBOL_REF_BLOCK_OFFSET (x_base) == SYMBOL_REF_BLOCK_OFFSET (y_base))
> -	return binds_def ? 1 : -1;
> -      if (SYMBOL_REF_ANCHOR_P (x_base) != SYMBOL_REF_ANCHOR_P (y_base))
> -	return -1;
> -      return 0;
> +      if (distance)
> +	*distance += (SYMBOL_REF_BLOCK_OFFSET (y_base)
> +		      - SYMBOL_REF_BLOCK_OFFSET (x_base));
> +      return binds_def ? 1 : -1;
>      }
>    /* In general we assume that memory locations pointed to by different labels
>       may overlap in undefined ways.  */
> -  return -1;
> +  return -2;
>  }
>  
>  /* Return 0 if the addresses X and Y are known to point to different
> @@ -2513,11 +2531,16 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
>  
>    if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
>      {
> -      int cmp = compare_base_symbol_refs (x,y);
> +      HOST_WIDE_INT distance = 0;
> +      int cmp = compare_base_symbol_refs (x, y, &distance);
>  
> -      /* If both decls are the same, decide by offsets.  */
> +      /* Punt if we have no information about the relationship between
> +	 X and Y.  */
> +      if (cmp == -2)
> +	return -1;
> +      /* If the symbols are a known distance apart, decide by offsets.  */
>        if (cmp == 1)
> -        return offset_overlap_p (c, xsize, ysize);
> +	return offset_overlap_p (c + distance, xsize, ysize);
>        /* 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
> @@ -2526,7 +2549,7 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
>  	return -1;
>        /* If decls are different or we know by offsets that there is no overlap,
>  	 we win.  */
> -      if (!cmp || !offset_overlap_p (c, xsize, ysize))
> +      if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
>  	return 0;
>        /* Decls may or may not be different and offsets overlap....*/
>        return -1;

[PATCH] alias: Fix offset checks involving section anchors [PR92294]

[Richard Sandiford]

This is a repost of:

  https://gcc.gnu.org/pipermail/gcc-patches/2020-February/539763.html

which was initially posted during stage 4.  (And yeah, I only just
missed stage 4 again.)

IMO it would be better to fix the bug directly (as the patch tries
to do) instead of wait for a more thorough redesign of this area.
See the end of:

  https://gcc.gnu.org/pipermail/gcc-patches/2020-February/540002.html

for some stats.

Honza: Richard said he'd like your opinion on the patch.


memrefs_conflict_p has a slightly odd structure.  It first checks
whether two addresses based on SYMBOL_REFs refer to the same object,
with a tristate result:

      int cmp = compare_base_symbol_refs (x,y);

If the addresses do refer to the same object, we can use offset-based checks:

      /* If both decls are the same, decide by offsets.  */
      if (cmp == 1)
        return offset_overlap_p (c, xsize, ysize);

But then, apart from the special case of forced address alignment,
we use an offset-based check even if we don't know whether the
addresses refer to the same object:

      /* 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 (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
	return -1;
      /* If decls are different or we know by offsets that there is no overlap,
	 we win.  */
      if (!cmp || !offset_overlap_p (c, xsize, ysize))
	return 0;

This somewhat contradicts:

  /* In general we assume that memory locations pointed to by different labels
     may overlap in undefined ways.  */

at the end of compare_base_symbol_refs.  In other words, we're taking -1
to mean that either (a) the symbols are equal (via aliasing) or (b) the
references access non-overlapping objects.

But even assuming that's true for normal symbols, it doesn't cope
correctly with section anchors.  If a symbol X at ANCHOR+OFFSET is
preemptible, either (a) X = ANCHOR+OFFSET (rather than the X = ANCHOR
assumed above) or (b) X and ANCHOR reference non-overlapping objects.

And an offset-based comparison makes no sense for an anchor symbol
vs. a bare symbol with no decl.  If the bare symbol is allowed to
alias other symbols then it can surely alias any symbol in the
anchor's block, so there are multiple anchor offsets that might
induce an alias.

This patch therefore replaces the current tristate:

  - known equal
  - known independent (two accesses can't alias)
  - equal or independent

with:

  - known distance apart
  - known independent (two accesses can't alias)
  - known distance apart or independent
  - don't know

For safety, the patch puts all bare symbols in the "don't know"
category.  If that turns out to be too conservative, we at least
need that behaviour for combinations involving a bare symbol
and a section anchor.  However, bare symbols should be relatively
rare these days.

Retested on aarch64-linux-gnu, aarch64_be-elf and x86_64-linux-gnu.
OK to install?

Richard


gcc/
	PR rtl-optimization/92294
	* alias.c (compare_base_symbol_refs): Take an extra parameter
	and add the distance between two symbols to it.  Enshrine in
	comments that -1 means "either 0 or 1, but we can't tell
	which at compile time".  Return -2 for symbols whose
	relationship is unknown.
	(memrefs_conflict_p): Update call accordingly.
	(rtx_equal_for_memref_p): Likewise.  Punt for a return value of -2,
	without even checking the offset.  Take the distance between symbols
	into account.
---
 gcc/alias.c | 53 ++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 38 insertions(+), 15 deletions(-)

diff --git a/gcc/alias.c b/gcc/alias.c
index 8d3575e4e27..e22863a929a 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -159,7 +159,8 @@ static tree decl_for_component_ref (tree);
 static int write_dependence_p (const_rtx,
 			       const_rtx, machine_mode, rtx,
 			       bool, bool, bool);
-static int compare_base_symbol_refs (const_rtx, const_rtx);
+static int compare_base_symbol_refs (const_rtx, const_rtx,
+				     HOST_WIDE_INT * = NULL);
 
 static void memory_modified_1 (rtx, const_rtx, void *);
 
@@ -1837,7 +1838,11 @@ rtx_equal_for_memref_p (const_rtx x, const_rtx y)
       return label_ref_label (x) == label_ref_label (y);
 
     case SYMBOL_REF:
-      return compare_base_symbol_refs (x, y) == 1;
+      {
+	HOST_WIDE_INT distance = 0;
+	return (compare_base_symbol_refs (x, y, &distance) == 1
+		&& distance == 0);
+      }
 
     case ENTRY_VALUE:
       /* This is magic, don't go through canonicalization et al.  */
@@ -2172,10 +2177,24 @@ compare_base_decls (tree base1, tree base2)
   return ret;
 }
 
-/* Same as compare_base_decls but for SYMBOL_REF.  */
+/* Compare SYMBOL_REFs X_BASE and Y_BASE.
+
+   - Return 1 if Y_BASE - X_BASE is constant, adding that constant
+     to *DISTANCE if DISTANCE is nonnull.
+
+   - Return 0 if no valid accesses based on X_BASE can alias valid
+     accesses based on Y_BASE.
+
+   - Return -1 if one of the two results above applies, but we can't
+     tell which at compile time.  Update DISTANCE in the same way as
+     for a return value of 1, for the case in which that result holds
+     at runtime.
+
+   - Return -2 otherwise.  */
 
 static int
-compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
+compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
+			  HOST_WIDE_INT *distance)
 {
   tree x_decl = SYMBOL_REF_DECL (x_base);
   tree y_decl = SYMBOL_REF_DECL (y_base);
@@ -2195,7 +2214,7 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
       /* We handle specially only section anchors and assume that other
  	 labels may overlap with user variables in an arbitrary way.  */
       if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
-        return -1;
+	return -2;
       /* Anchors contains static VAR_DECLs and CONST_DECLs.  We are safe
 	 to ignore CONST_DECLs because they are readonly.  */
       if (!VAR_P (x_decl)
@@ -2222,15 +2241,14 @@ compare_base_symbol_refs (const_rtx x_base, const_rtx y_base)
     {
       if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
 	return 0;
-      if (SYMBOL_REF_BLOCK_OFFSET (x_base) == SYMBOL_REF_BLOCK_OFFSET (y_base))
-	return binds_def ? 1 : -1;
-      if (SYMBOL_REF_ANCHOR_P (x_base) != SYMBOL_REF_ANCHOR_P (y_base))
-	return -1;
-      return 0;
+      if (distance)
+	*distance += (SYMBOL_REF_BLOCK_OFFSET (y_base)
+		      - SYMBOL_REF_BLOCK_OFFSET (x_base));
+      return binds_def ? 1 : -1;
     }
   /* In general we assume that memory locations pointed to by different labels
      may overlap in undefined ways.  */
-  return -1;
+  return -2;
 }
 
 /* Return 0 if the addresses X and Y are known to point to different
@@ -2513,11 +2531,16 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
 
   if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
     {
-      int cmp = compare_base_symbol_refs (x,y);
+      HOST_WIDE_INT distance = 0;
+      int cmp = compare_base_symbol_refs (x, y, &distance);
 
-      /* If both decls are the same, decide by offsets.  */
+      /* Punt if we have no information about the relationship between
+	 X and Y.  */
+      if (cmp == -2)
+	return -1;
+      /* If the symbols are a known distance apart, decide by offsets.  */
       if (cmp == 1)
-        return offset_overlap_p (c, xsize, ysize);
+	return offset_overlap_p (c + distance, xsize, ysize);
       /* 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
@@ -2526,7 +2549,7 @@ memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
 	return -1;
       /* If decls are different or we know by offsets that there is no overlap,
 	 we win.  */
-      if (!cmp || !offset_overlap_p (c, xsize, ysize))
+      if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
 	return 0;
       /* Decls may or may not be different and offsets overlap....*/
       return -1;