Bug 69776 - [4.9 Regression] Wrong optimization with aliasing
Summary: [4.9 Regression] Wrong optimization with aliasing
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 5.2.0
: P3 normal
Target Milestone: 5.4
Assignee: Richard Biener
URL:
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2016-02-11 22:15 UTC by Alexander Cherepanov
Modified: 2016-08-03 10:58 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.4.7, 5.4.0, 6.0
Known to fail: 4.5.4, 4.6.4, 4.7.3, 4.8.5, 4.9.3, 5.3.0
Last reconfirmed: 2016-02-12 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Alexander Cherepanov 2016-02-11 22:15:36 UTC
The program:

#include <stdlib.h>
#include <stdio.h>

int main()
{
  void *p = malloc(10);
  int *pi = p;
  double *pd = p;

  *pi = 1;
  printf("*pi = %d\n", *pi);

  int a = *pi;
  *pd = 0;
  *pi = a;

  printf("p = %p\n", p);
  printf("*pi = %d\n", *pi);
}

compiled with `gcc -std=c11 -pedantic -O2` prints this:

*pi = 1
p = 0x1165010
*pi = 0

The last value is wrong, it should be 1.

Tested on gcc 4.7.2, 4.9.2 and 5.2.0 -- all affected.
Comment 1 Andrew Pinski 2016-02-11 22:20:35 UTC
>The last value is wrong, it should be 1.

Why do you think that? 

If we look at your code:


  void *p = malloc(10);
  int *pi = p;
  double *pd = p;


<< at this point p has no effective type.

  *pi = 1;
  printf("*pi = %d\n", *pi);

<< Now it has an effective type of int or a struct containing int

  int a = *pi;

<< a read 

  *pd = 0;

<< a write to a double, it does not alias int at all so it can be moved past the next statement

  *pi = a;

<< store via an int

Since the order of pi and pd is not specified due to different aliasing of int and double so either can be done first



  printf("p = %p\n", p);
  printf("*pi = %d\n", *pi);
Comment 2 Alexander Cherepanov 2016-02-11 23:49:15 UTC
[CC'ing Martin Sebor and Joseph S. Myers as it's potentially related to 
bug 65892.]

On 2016-02-12 01:20, pinskia at gcc dot gnu.org wrote:
>> The last value is wrong, it should be 1.
>
> Why do you think that?
>
> If we look at your code:
>
>    void *p = malloc(10);
>    int *pi = p;
>    double *pd = p;
>
> << at this point p has no effective type.

Ok

>    *pi = 1;
>    printf("*pi = %d\n", *pi);
>
> << Now it has an effective type of int or a struct containing int

Structs are a separate topic (and I thinks it's still unsettled in the 
standard). Fortunately they are not relevant here. Back to int...

C11, 6.5p6: "If a value is stored into an object having no declared type 
through an lvalue having a type that is not a character type, then the 
type of the lvalue becomes the effective type of the object for that 
access and for subsequent accesses that do not modify
the stored value."

So, yes, it has an effective type of int for this store and for 
subsequent reads. But not for writes.

>    int a = *pi;
>
> << a read

Yes, a read with an effective type of int.

>    *pd = 0;
>
> << a write to a double, it does not alias int at all so it can be moved past
> the next statement

This is a write. Hence the previous effective type is not relevant. And 
effective type for this write and for subsequent reads is double.

>    *pi = a;
>
> << store via an int
>
> Since the order of pi and pd is not specified due to different aliasing of int
> and double so either can be done first

Sorry, I don't see what the talk about moving stores could be based on. 
This is another write. So it ignores the previous effective type and 
sets a new one.

Looking at it at a higher level: I think it is generally agreed that 
allocated memory could be repurposed at will -- once you don't need old 
data you just overwrite it with new data without any regard to the 
types. I have seen proposals[1] for forbidding this technique but I 
don't think it was seriously considered. Maybe I missed it.

[1] https://gcc.gnu.org/ml/gcc/2004-12/msg00193.html

The program in this bug report is loosely based on the Example 1 in DR 
236 and I was surprised that the problematic behavior is present even 
without functions involved. The variant with a function (closer to the 
Example 1 in DR 236):

// file 1
void f(int *qi, double *qd)
{
   int i = *qi;
   *qd = 0;
   *qi = i;
}

// file 2
#include <stdlib.h>
#include <stdio.h>

void f(int *qi, double *qd);

int main()
{
   void *p = malloc(10);
   int *pi = p;
   double *pd = p;

   *pi = 1;
   printf("*pi = %d\n", *pi);

   f(pi, pd);

   printf("*pi = %d\n", *pi);
}

I don't know if it should be considered the same case or a separate one. 
Most discussions about DR 236 (like in bug 65892) are concerned about 
unions and it's not clear to me if the case of allocated objects is 
settled or not, in gcc or in general. IMHO the case of allocated objects 
is easier (no tricky visibility rules) and more general but maybe I'm 
missing something.
Comment 3 Martin Sebor 2016-02-12 04:02:11 UTC
I'm not sure if the question of dynamic memory and pointers at function scope as applies to the test case is settled or not, or that there is consensus about the validity of the submitted test case.  My impression is that the weakest (mostly, within WG14) agreed-upon requirement on implementations is the visible union rule (N1520).  Under it, I would expect the following slightly changed test case to produce the expected output (1 1).  It doesn't with GCC and I would be more inclined to view that as a bug than the original test case (GCC isn't the only compiler that fails this test).  The next weakest requirement is that the effective type of an object cannot change after it's set.  I suspect that's too weak to be useful in general.

#include <stdlib.h>
#include <stdio.h>

int main()
{
  void *p = malloc(10);

  union {
    int *pi;
    double *pd;
  } u = { .pi = p };

  *u.pi = 1;

  printf("*pi = %d\n", *u.pi);

  int a = *u.pi;

  *u.pd = 0;

  *u.pi = a;

  printf("p = %p\n", p);
  printf("*pi = %d\n", *u.pi);
}
Comment 4 Richard Biener 2016-02-12 08:30:38 UTC
Actually the middle-end memory model makes this valid and FREs redundant store elimination breaks it.

Mine.
Comment 5 Richard Biener 2016-02-12 10:40:15 UTC
extern void *malloc (__SIZE_TYPE__);
extern void abort (void);

void __attribute__((noinline,noclone))
foo (int *pi)
{
  if (*pi != 1)
    abort ();
}

int
main()
{
  void *p = malloc(sizeof (double));
  int *pi = p;
  double *pd = p;

  *pi = 1;
  int a = *pi;
  *pd = 0;
  *pi = a;
  foo (pi);

  return 0;
}


FRE removes *pi = a because it stores the same value as *pi = 1 which is
found via

          val = vn_reference_lookup (gimple_assign_lhs (stmt),
                                     gimple_vuse (stmt), VN_WALK, NULL);

and thus treats the *pi = a store as a load, losing the fact that it
cannot TBAA disambiguate against other stores.
Comment 6 Richard Biener 2016-02-15 08:43:10 UTC
Author: rguenth
Date: Mon Feb 15 08:42:38 2016
New Revision: 233418

URL: https://gcc.gnu.org/viewcvs?rev=233418&root=gcc&view=rev
Log:
2016-02-15  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/69776
	* tree-ssa-sccvn.h (vn_reference_lookup): Adjust prototype.
	* tree-ssa-sccvn.c (vn_reference_lookup): Add parameter to
	indicate whether we can use TBAA to disambiguate against stores.
	Use alias-set zero if not.
	(visit_reference_op_store): Do not use TBAA when looking up
	redundant stores.
	* tree-ssa-pre.c (compute_avail): Use TBAA here.
	(eliminate_dom_walker::before_dom_children): But not when looking
	up redundant stores.

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

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr69776.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-pre.c
    trunk/gcc/tree-ssa-sccvn.c
    trunk/gcc/tree-ssa-sccvn.h
Comment 7 Richard Biener 2016-02-15 08:50:10 UTC
Fixed on trunk sofar.
Comment 8 Alexander Cherepanov 2016-02-15 17:36:39 UTC
--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
> Actually the middle-end memory model makes this valid and FREs redundant store
> elimination breaks it.

And function boundaries are not an obstacle for validity? I guess so (as 
gcc devs expressed such views several times in the past, in various 
contexts) but I'm not sure because DR 236 states otherwise. Initial 
testcase was prepared not to trigger DR 236 and, thus, it's a bit more 
tricky than necessary.

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
 > Fixed on trunk sofar.

While the reduced testcase seems to be fixed, the original testcase 
still fails for me. If a separate function is ok the following testcase 
should be easier to reason about:

extern void *malloc (__SIZE_TYPE__);
extern void abort (void);

__attribute__((noinline,noclone))
void f(int *qi, double *qd)
{
   int i = *qi;
   *qd = 0;
   *qi = i;
}

int main()
{
   int *p = malloc(sizeof(double));

   *p = 1;
   f(p, (double *)p);
   if (*p != 1)
     abort();
}

This bug report was really about optimization of the function f in the 
absence of additional info, e.g. when compiled in a separate TU. 
(noinline+noclone seem to be enough too.) All printfs in the original 
testcase are just to achieve the same outcome without explicit function. 
But maybe I accidentally triggered another gcc bug.

BTW your testcase in comment #5 is interesting because the 
implementation of the function foo seems to affect the optimization of 
the rest of the program, i.e. noinline+noclone provide only one-way 
isolation. Just last week I asked about it elsewhere and here it is. 
Thanks! :-)
Comment 9 Richard Biener 2016-02-16 10:18:59 UTC
Looks like the fix was too constrained.  I have a patch to fix it some more.
Comment 10 Richard Biener 2016-02-16 15:01:17 UTC
Author: rguenth
Date: Tue Feb 16 15:00:45 2016
New Revision: 233453

URL: https://gcc.gnu.org/viewcvs?rev=233453&root=gcc&view=rev
Log:
2016-02-16  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/69776
	* tree-ssa-alias.c (indirect_ref_may_alias_decl_p): Get alias
	sets from caller.
	(indirect_refs_may_alias_p): Likewise.
	(refs_may_alias_p_1): Pass alias sets as from ao_ref.
	* tree-ssa-sccvn.c (vn_reference_lookup): Also adjust vr alias-set
	according to tbaa_p.
	* tree-ssa-dom.c (lookup_avail_expr): Add tbaa_p flag.
	(optimize_stmt): For redundant store discovery do not allow tbaa.

	* gcc.dg/torture/pr69776-2.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr69776-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-alias.c
    trunk/gcc/tree-ssa-dom.c
    trunk/gcc/tree-ssa-sccvn.c
Comment 11 Richard Biener 2016-02-17 14:47:28 UTC
Now hopefully fixed on trunk.
Comment 12 Alexander Cherepanov 2016-02-18 01:37:17 UTC
Seems to be fixed, thanks! I've tried several variations, ok too.
Comment 13 Richard Biener 2016-02-25 09:07:40 UTC
Author: rguenth
Date: Thu Feb 25 09:07:08 2016
New Revision: 233693

URL: https://gcc.gnu.org/viewcvs?rev=233693&root=gcc&view=rev
Log:
2016-02-25  Richard Biener  <rguenther@suse.de>

	Backport from mainline
	2016-02-15  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/69776
	* tree-ssa-sccvn.h (vn_reference_lookup): Adjust prototype.
	* tree-ssa-sccvn.c (vn_reference_lookup): Add parameter to
	indicate whether we can use TBAA to disambiguate against stores.
	Use alias-set zero if not.
	(visit_reference_op_store): Do not use TBAA when looking up
	redundant stores.
	* tree-ssa-pre.c (compute_avail): Use TBAA here.
	(eliminate_dom_walker::before_dom_children): But not when looking
	up redundant stores.

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

	2016-02-16  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/69776
	* tree-ssa-alias.c (indirect_ref_may_alias_decl_p): Get alias
	sets from caller.
	(indirect_refs_may_alias_p): Likewise.
	(refs_may_alias_p_1): Pass alias sets as from ao_ref.
	* tree-ssa-sccvn.c (vn_reference_lookup): Also adjust vr alias-set
	according to tbaa_p.
	* tree-ssa-dom.c (lookup_avail_expr): Add tbaa_p flag.
	(optimize_stmt): For redundant store discovery do not allow tbaa.

	* gcc.dg/torture/pr69776-2.c: New testcase.

Added:
    branches/gcc-5-branch/gcc/testsuite/gcc.dg/torture/pr69776-2.c
    branches/gcc-5-branch/gcc/testsuite/gcc.dg/torture/pr69776.c
Modified:
    branches/gcc-5-branch/gcc/ChangeLog
    branches/gcc-5-branch/gcc/testsuite/ChangeLog
    branches/gcc-5-branch/gcc/tree-ssa-alias.c
    branches/gcc-5-branch/gcc/tree-ssa-dom.c
    branches/gcc-5-branch/gcc/tree-ssa-pre.c
    branches/gcc-5-branch/gcc/tree-ssa-sccvn.c
    branches/gcc-5-branch/gcc/tree-ssa-sccvn.h
Comment 14 Richard Biener 2016-08-03 10:58:43 UTC
Fixed in GCC 5.4+