[PATCH] Fix PR80533

[PATCH] Fix PR80533

[Richard Biener]

When set_mem_attributes_minus_bitpos computes the MEM_EXPR for MEM RTXen
it strips outermost ARRAY_REFs (for historic efficiency reasons).
Nowadays a MEM_EXPR has to be conservative with respect to alias
analysis which means it has to cover the original access.  This means
we may _not_ end up with a MEM_EXPR accessing a trailing array as its
size is not conservative when used in overlap analysis.

The following patch fixes that (by dropping the MEM_EXPR).  This
fix should be suitable for release branches and hopefully not
pessimize things too much.

In the end my idea always was to use the full memory reference tree
and not stripping anything but I never came to implementing this.

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

No testcase, I failed to create one on x86_64 and the ppc one in
the PR is not an execute testcase so quite useless.  I tried

struct q { int n; long o[100]; };
struct r { int n; long o[0]; };

union {
    struct r r;
    struct q q;
} u;

int foo (int i, int j)
{
  long *q = u.r.o;
  u.r.o[i/j] = 1;
  return q[2];
}

but nothing convinced scheduling to move the load before the store ;)
The two memory references are seen as not aliasing though.  Stupid
scheduler.

Richard.

2017-04-27  Richard Biener  <rguenther@suse.de>

	PR middle-end/80533
	* emit-rtl.c (set_mem_attributes_minus_bitpos): When
	stripping ARRAY_REFs from MEM_EXPR make sure we're not
	keeping a reference to a trailing array.

Index: gcc/emit-rtl.c
===================================================================
--- gcc/emit-rtl.c	(revision 247277)
+++ gcc/emit-rtl.c	(working copy)
@@ -1954,7 +1954,10 @@ set_mem_attributes_minus_bitpos (rtx ref
 	  while (TREE_CODE (t2) == ARRAY_REF);
 
 	  if (DECL_P (t2)
-	      || TREE_CODE (t2) == COMPONENT_REF)
+	      || (TREE_CODE (t2) == COMPONENT_REF
+		  /* For trailing arrays t2 doesn't have a size that
+		     covers all valid accesses.  */
+		  && ! array_at_struct_end_p (t, false)))
 	    {
 	      attrs.expr = t2;
 	      attrs.offset_known_p = false;

Re: [PATCH] Fix PR80533

[Alexander Monakov]

On Thu, 27 Apr 2017, Richard Biener wrote:
> struct q { int n; long o[100]; };
> struct r { int n; long o[0]; };
> 
> union {
>     struct r r;
>     struct q q;
> } u;
> 
> int foo (int i, int j)
> {
>   long *q = u.r.o;
>   u.r.o[i/j] = 1;
>   return q[2];
> }
> 
> but nothing convinced scheduling to move the load before the store ;)
> The two memory references are seen as not aliasing though.  Stupid
> scheduler.

On x86 there's an anti-dependence on %eax that prevents the second scheduler
from performing the breaking motion; with -fschedule-insns, pre-RA scheduler
is actually able to move the load too early, but then IRA immediately undoes
that.  Also, -fselective-scheduling2 is able to move the load early via renaming
(and uncovers the miscompile, as nothing undoes it later).

Applying division to the result of the load, rather than the address of the
store, also produces code demonstrating the miscompile:

struct q { int n; long o[100]; };
struct r { int n; long o[0]; };

union {
    struct r r;
    struct q q;
} u;

int foo (int i, int j)
{
  long *q = u.r.o;
  u.r.o[i] = 1;
  return q[2]/j;
}


foo:
.LFB0:
        .cfi_startproc
        movq    u+24(%rip), %rax
        movslq  %edi, %rdi
        movslq  %esi, %rsi
        movq    $1, u+8(,%rdi,8)
        cqto
        idivq   %rsi
        ret

Alexander

Re: [PATCH] Fix PR80533

[Richard Biener]

On Thu, 27 Apr 2017, Alexander Monakov wrote:

> On Thu, 27 Apr 2017, Richard Biener wrote:
> > struct q { int n; long o[100]; };
> > struct r { int n; long o[0]; };
> > 
> > union {
> >     struct r r;
> >     struct q q;
> > } u;
> > 
> > int foo (int i, int j)
> > {
> >   long *q = u.r.o;
> >   u.r.o[i/j] = 1;
> >   return q[2];
> > }
> > 
> > but nothing convinced scheduling to move the load before the store ;)
> > The two memory references are seen as not aliasing though.  Stupid
> > scheduler.
> 
> On x86 there's an anti-dependence on %eax that prevents the second scheduler
> from performing the breaking motion; with -fschedule-insns, pre-RA scheduler
> is actually able to move the load too early, but then IRA immediately undoes
> that.  Also, -fselective-scheduling2 is able to move the load early via renaming
> (and uncovers the miscompile, as nothing undoes it later).
> 
> Applying division to the result of the load, rather than the address of the
> store, also produces code demonstrating the miscompile:
> 
> struct q { int n; long o[100]; };
> struct r { int n; long o[0]; };
> 
> union {
>     struct r r;
>     struct q q;
> } u;
> 
> int foo (int i, int j)
> {
>   long *q = u.r.o;
>   u.r.o[i] = 1;
>   return q[2]/j;
> }

Thanks.  It also is still miscompiled because array_at_struct_end_p
is somewhat confused as to what its semantics are supposed to be.
Multiple callers (including the new one) assume when it returns false
they can trust the array domain while in reality when it returns false
it says we can constrain the access even if only because we know an
underlying decls size ...

It also raises the question whether for

struct X
{
  double x;
  int a[1];
} x;

x.a is an array at struct end -- there's enough padding to provide
space for x.a[1] even though its size doesn't include that (and
whether it can depends on the alignment of 'double').  This is
sort-of what happens for the union case above -- u.r.o can be
extended into the padding (which is quite large due to u.q.o).
The question is whether we allow such access to padding in general
(not only when the array is at struct end).  Likewise do we allow, in

struct Y
{
  struct X[4][4] a;
} y;

for y.a[i][j].a[k] k == 3?  that is, allow the "last" element of
an array to be flexibly extended?  Or do we instead allow
y.a[i][j] with j == 4, thus the last dimension of a multidimensional
array to be "over-allocated"?  Or do we just allow i > 3?

There's another PR where array-bound warnings are confused by
the weird answer from array_at_struct_end_p and two other users
I skimmed would generate wrong code because they trust the array
domain after it.

Looks like I have to refactor that a bit, like with the following
which makes things a bit more explicit, and _not_ allowing to
use padding appart when using flexarrays (though that can't
happen, you can't instantiate those with decls) or the zero-size
array GNU extension.

It also corrects IMHO wrong behavior with VIEW_CONVERT_EXPRs
and the overly pessimistic handling of arrays of structs with
arrays at struct end or multi-dimensional arrays when not
dealing with the outermost dimension.

So I'm testing the following.

Richard.

2017-04-28  Richard Biener  <rguenther@suse.de>

	PR middle-end/80533
	* tree.c (array_at_struct_end_p): Handle arrays at struct
	end with size zero more conservatively.  Refactor and treat
	arrays of arrays or aggregates more strict.  Fix
	VIEW_CONVERT_EXPR handling.

	* gcc.dg/torture/pr80533.c: New testcase.

Index: gcc/tree.c
===================================================================
--- gcc/tree.c	(revision 247362)
+++ gcc/tree.c	(working copy)
@@ -13222,9 +13230,19 @@ array_ref_up_bound (tree exp)
 bool
 array_at_struct_end_p (tree ref, bool allow_compref)
 {
-  if (TREE_CODE (ref) != ARRAY_REF
-      && TREE_CODE (ref) != ARRAY_RANGE_REF
-      && (!allow_compref || TREE_CODE (ref) != COMPONENT_REF))
+  tree atype;
+
+  if (TREE_CODE (ref) == ARRAY_REF
+      || TREE_CODE (ref) == ARRAY_RANGE_REF)
+    {
+      atype = TREE_TYPE (TREE_OPERAND (ref, 0));
+      ref = TREE_OPERAND (ref, 0);
+    }
+  else if (allow_compref
+	   && TREE_CODE (ref) == COMPONENT_REF
+	   && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 1))) == ARRAY_TYPE)
+    atype = TREE_TYPE (TREE_OPERAND (ref, 1));
+  else
     return false;
 
   while (handled_component_p (ref))
@@ -13232,19 +13250,43 @@ array_at_struct_end_p (tree ref, bool al
       /* If the reference chain contains a component reference to a
          non-union type and there follows another field the reference
 	 is not at the end of a structure.  */
-      if (TREE_CODE (ref) == COMPONENT_REF
-	  && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
+      if (TREE_CODE (ref) == COMPONENT_REF)
 	{
-	  tree nextf = DECL_CHAIN (TREE_OPERAND (ref, 1));
-	  while (nextf && TREE_CODE (nextf) != FIELD_DECL)
-	    nextf = DECL_CHAIN (nextf);
-	  if (nextf)
-	    return false;
+	  if (TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
+	    {
+	      tree nextf = DECL_CHAIN (TREE_OPERAND (ref, 1));
+	      while (nextf && TREE_CODE (nextf) != FIELD_DECL)
+		nextf = DECL_CHAIN (nextf);
+	      if (nextf)
+		return false;
+	    }
 	}
+      /* If we have a multi-dimensional array we do not consider
+         a non-innermost dimension as flex array if the whole
+	 multi-dimensional array is at struct end.
+	 Same for an array of aggregates with a trailing array
+	 member.  */
+      else if (TREE_CODE (ref) == ARRAY_REF)
+	return false;
+      else if (TREE_CODE (ref) == ARRAY_RANGE_REF)
+	;
+      /* If we view an underlying object as sth else then what we
+         gathered up to now is what we have to rely on.  */
+      else if (TREE_CODE (ref) == VIEW_CONVERT_EXPR)
+	break;
+      else
+	gcc_unreachable ();
 
       ref = TREE_OPERAND (ref, 0);
     }
 
+  /* The array now is at struct end.  Treat flexible arrays and
+     zero-sized arrays as always subject to extend, even into
+     just padding constrained by an underlying decl.  */
+  if (! TYPE_SIZE (atype)
+      || integer_zerop (TYPE_SIZE (atype)))
+    return true;
+
   tree size = NULL;
 
   if (TREE_CODE (ref) == MEM_REF
Index: gcc/testsuite/gcc.dg/torture/pr80533.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr80533.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/torture/pr80533.c	(working copy)
@@ -0,0 +1,27 @@
+/* { dg-do run } */
+
+extern void abort (void);
+
+struct q { int n; long o[100]; };
+struct r { int n; long o[0]; };
+
+union {
+    struct r r;
+    struct q q;
+} u;
+
+int __attribute__((noclone,noinline))
+foo (int i, int j)
+{
+  long *q = u.r.o;
+  u.r.o[i] = 1;
+  return q[2]/j;
+}
+
+int
+main()
+{
+  if (foo (2, 1) != 1)
+    abort ();
+  return 0;
+}

Re: [PATCH] Fix PR80533

[Richard Biener]

On Fri, 28 Apr 2017, Richard Biener wrote:

> On Thu, 27 Apr 2017, Alexander Monakov wrote:
> 
> > On Thu, 27 Apr 2017, Richard Biener wrote:
> > > struct q { int n; long o[100]; };
> > > struct r { int n; long o[0]; };
> > > 
> > > union {
> > >     struct r r;
> > >     struct q q;
> > > } u;
> > > 
> > > int foo (int i, int j)
> > > {
> > >   long *q = u.r.o;
> > >   u.r.o[i/j] = 1;
> > >   return q[2];
> > > }
> > > 
> > > but nothing convinced scheduling to move the load before the store ;)
> > > The two memory references are seen as not aliasing though.  Stupid
> > > scheduler.
> > 
> > On x86 there's an anti-dependence on %eax that prevents the second scheduler
> > from performing the breaking motion; with -fschedule-insns, pre-RA scheduler
> > is actually able to move the load too early, but then IRA immediately undoes
> > that.  Also, -fselective-scheduling2 is able to move the load early via renaming
> > (and uncovers the miscompile, as nothing undoes it later).
> > 
> > Applying division to the result of the load, rather than the address of the
> > store, also produces code demonstrating the miscompile:
> > 
> > struct q { int n; long o[100]; };
> > struct r { int n; long o[0]; };
> > 
> > union {
> >     struct r r;
> >     struct q q;
> > } u;
> > 
> > int foo (int i, int j)
> > {
> >   long *q = u.r.o;
> >   u.r.o[i] = 1;
> >   return q[2]/j;
> > }
> 
> Thanks.  It also is still miscompiled because array_at_struct_end_p
> is somewhat confused as to what its semantics are supposed to be.
> Multiple callers (including the new one) assume when it returns false
> they can trust the array domain while in reality when it returns false
> it says we can constrain the access even if only because we know an
> underlying decls size ...
> 
> It also raises the question whether for
> 
> struct X
> {
>   double x;
>   int a[1];
> } x;
> 
> x.a is an array at struct end -- there's enough padding to provide
> space for x.a[1] even though its size doesn't include that (and
> whether it can depends on the alignment of 'double').  This is
> sort-of what happens for the union case above -- u.r.o can be
> extended into the padding (which is quite large due to u.q.o).
> The question is whether we allow such access to padding in general
> (not only when the array is at struct end).  Likewise do we allow, in
> 
> struct Y
> {
>   struct X[4][4] a;
> } y;
> 
> for y.a[i][j].a[k] k == 3?  that is, allow the "last" element of
> an array to be flexibly extended?  Or do we instead allow
> y.a[i][j] with j == 4, thus the last dimension of a multidimensional
> array to be "over-allocated"?  Or do we just allow i > 3?
> 
> There's another PR where array-bound warnings are confused by
> the weird answer from array_at_struct_end_p and two other users
> I skimmed would generate wrong code because they trust the array
> domain after it.
> 
> Looks like I have to refactor that a bit, like with the following
> which makes things a bit more explicit, and _not_ allowing to
> use padding appart when using flexarrays (though that can't
> happen, you can't instantiate those with decls) or the zero-size
> array GNU extension.
> 
> It also corrects IMHO wrong behavior with VIEW_CONVERT_EXPRs
> and the overly pessimistic handling of arrays of structs with
> arrays at struct end or multi-dimensional arrays when not
> dealing with the outermost dimension.
> 
> So I'm testing the following.

Bootstrapped / tested on x86_64-unknown-linux-gnu.

FAIL: g++.dg/warn/Warray-bounds-4.C  -std=gnu++11  (test for warnings, 
line 25)

looks like we explicitely want to warn about char[0] (in C++!) ...

Richard.

> Richard.
> 
> 2017-04-28  Richard Biener  <rguenther@suse.de>
> 
> 	PR middle-end/80533
> 	* tree.c (array_at_struct_end_p): Handle arrays at struct
> 	end with size zero more conservatively.  Refactor and treat
> 	arrays of arrays or aggregates more strict.  Fix
> 	VIEW_CONVERT_EXPR handling.
> 
> 	* gcc.dg/torture/pr80533.c: New testcase.
> 
> Index: gcc/tree.c
> ===================================================================
> --- gcc/tree.c	(revision 247362)
> +++ gcc/tree.c	(working copy)
> @@ -13222,9 +13230,19 @@ array_ref_up_bound (tree exp)
>  bool
>  array_at_struct_end_p (tree ref, bool allow_compref)
>  {
> -  if (TREE_CODE (ref) != ARRAY_REF
> -      && TREE_CODE (ref) != ARRAY_RANGE_REF
> -      && (!allow_compref || TREE_CODE (ref) != COMPONENT_REF))
> +  tree atype;
> +
> +  if (TREE_CODE (ref) == ARRAY_REF
> +      || TREE_CODE (ref) == ARRAY_RANGE_REF)
> +    {
> +      atype = TREE_TYPE (TREE_OPERAND (ref, 0));
> +      ref = TREE_OPERAND (ref, 0);
> +    }
> +  else if (allow_compref
> +	   && TREE_CODE (ref) == COMPONENT_REF
> +	   && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 1))) == ARRAY_TYPE)
> +    atype = TREE_TYPE (TREE_OPERAND (ref, 1));
> +  else
>      return false;
>  
>    while (handled_component_p (ref))
> @@ -13232,19 +13250,43 @@ array_at_struct_end_p (tree ref, bool al
>        /* If the reference chain contains a component reference to a
>           non-union type and there follows another field the reference
>  	 is not at the end of a structure.  */
> -      if (TREE_CODE (ref) == COMPONENT_REF
> -	  && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
> +      if (TREE_CODE (ref) == COMPONENT_REF)
>  	{
> -	  tree nextf = DECL_CHAIN (TREE_OPERAND (ref, 1));
> -	  while (nextf && TREE_CODE (nextf) != FIELD_DECL)
> -	    nextf = DECL_CHAIN (nextf);
> -	  if (nextf)
> -	    return false;
> +	  if (TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
> +	    {
> +	      tree nextf = DECL_CHAIN (TREE_OPERAND (ref, 1));
> +	      while (nextf && TREE_CODE (nextf) != FIELD_DECL)
> +		nextf = DECL_CHAIN (nextf);
> +	      if (nextf)
> +		return false;
> +	    }
>  	}
> +      /* If we have a multi-dimensional array we do not consider
> +         a non-innermost dimension as flex array if the whole
> +	 multi-dimensional array is at struct end.
> +	 Same for an array of aggregates with a trailing array
> +	 member.  */
> +      else if (TREE_CODE (ref) == ARRAY_REF)
> +	return false;
> +      else if (TREE_CODE (ref) == ARRAY_RANGE_REF)
> +	;
> +      /* If we view an underlying object as sth else then what we
> +         gathered up to now is what we have to rely on.  */
> +      else if (TREE_CODE (ref) == VIEW_CONVERT_EXPR)
> +	break;
> +      else
> +	gcc_unreachable ();
>  
>        ref = TREE_OPERAND (ref, 0);
>      }
>  
> +  /* The array now is at struct end.  Treat flexible arrays and
> +     zero-sized arrays as always subject to extend, even into
> +     just padding constrained by an underlying decl.  */
> +  if (! TYPE_SIZE (atype)
> +      || integer_zerop (TYPE_SIZE (atype)))
> +    return true;
> +
>    tree size = NULL;
>  
>    if (TREE_CODE (ref) == MEM_REF
> Index: gcc/testsuite/gcc.dg/torture/pr80533.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/torture/pr80533.c	(nonexistent)
> +++ gcc/testsuite/gcc.dg/torture/pr80533.c	(working copy)
> @@ -0,0 +1,27 @@
> +/* { dg-do run } */
> +
> +extern void abort (void);
> +
> +struct q { int n; long o[100]; };
> +struct r { int n; long o[0]; };
> +
> +union {
> +    struct r r;
> +    struct q q;
> +} u;
> +
> +int __attribute__((noclone,noinline))
> +foo (int i, int j)
> +{
> +  long *q = u.r.o;
> +  u.r.o[i] = 1;
> +  return q[2]/j;
> +}
> +
> +int
> +main()
> +{
> +  if (foo (2, 1) != 1)
> +    abort ();
> +  return 0;
> +}
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)