[Bug c/32856] New: Invalid optimization in the face of aliasing

[Bug c/32856] New: Invalid optimization in the face of aliasing

[felix-gcc at fefe dot de]

This contrived example is miscompiled by gcc:

struct node {
  struct node* next, *prev;
};

void foo(struct node* n) {
  n->next->next->prev=n;
  n->next->prev->next=n;
}

This is not from real code, but I wrote it to demonstrate aliasing issues for a
talk I'm preparing now.  gcc -O2 -fno-strict-aliasing generates this code:

        movq    (%rdi), %rdx
        movq    (%rdx), %rax
        movq    %rdi, 8(%rax)
        movq    8(%rdx), %rax
        movq    %rdi, (%rax)

Note how rdx is used to cache the value of n->next.  Since we write through
some pointer that might alias other memory, gcc can not assume n still points
to the same value and n->next is unchanged after the first assignment.

Interestingly enough, changing assignments to

  n->next->next->next=n;
  n->next->prev->next=n;

properly reloads n->next.  I'm guessing that's because ->next has offset 0
relative to the pointer.


-- 
           Summary: Invalid optimization in the face of aliasing
           Product: gcc
           Version: 4.2.1
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: felix-gcc at fefe dot de
 GCC build triplet: x86_64-unknown-linux-gnu
  GCC host triplet: x86_64-unknown-linux-gnu
GCC target triplet: x86_64-unknown-linux-gnu


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

[Bug c/32856] Invalid optimization in the face of aliasing

[felix-gcc at fefe dot de]

------- Comment #1 from felix-gcc at fefe dot de  2007-07-22 17:09 -------
Well, since n is passed in a register, it can assume that n is still the same
here. :-)


-- 


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

[Bug c/32856] Invalid optimization in the face of aliasing

[felix-gcc at fefe dot de]

------- Comment #2 from felix-gcc at fefe dot de  2007-07-22 17:12 -------
FWIW, the C compilers from Intel and Sun do reload n->next.


-- 


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

[Bug middle-end/32856] Invalid optimization in the face of aliasing

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|major                       |normal
          Component|c                           |middle-end


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

[Bug middle-end/32856] Invalid optimization in the face of aliasing

[falk at debian dot org]

------- Comment #3 from falk at debian dot org  2007-07-22 23:01 -------
Can you give an example how n->next->next->prev and n->next might be at the
same address? I don't see any legal way to achieve that.

And FWIW, DEC C also optimizes like gcc does.


-- 

falk at debian dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING


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

[Bug middle-end/32856] Invalid optimization in the face of aliasing

[felix-gcc at fefe dot de]

------- Comment #4 from felix-gcc at fefe dot de  2007-07-22 23:08 -------
Falk:

  union {
    struct {
      void* unused;
      struct node n;
    } a;
    struct node b;
  } u;

Then &u.a.n.next == &u.b.n.prev;

Artificial?  Sure.  But legal.


-- 


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

[Bug middle-end/32856] Invalid optimization in the face of aliasing

[falk at debian dot org]

------- Comment #5 from falk at debian dot org  2007-07-22 23:19 -------
Well, certainly not legal in C, since there you may only access the element of
a union last written to. However, in GNU C, other accesses are allowed.


-- 

falk at debian dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW
     Ever Confirmed|0                           |1


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

[Bug middle-end/32856] Invalid optimization in the face of aliasing

[vogel at pi2 dot physik dot uni-erlangen dot de]

------- Comment #6 from vogel at pi2 dot physik dot uni-erlangen dot de  2007-07-23 10:08 -------
This program demonstrates the problem, it creates different output depending on
if compiled with or without optimisation.

Without optimisation, n->next is not cached:
n->next = 0xbfb01af0
n->next = 0xbfb01af8

With optimisation, n->next is cached, this is wrong:
n->next = 0xbfdb3da0
n->next = 0xbfdb3da0

Note that the pointer c will point exactly one pointer-width above the
structure a, so n->next->next->prev=n -- which corresponds to c->prev=n -- will
overwrite n->next with n.

#include <stdio.h>

struct node {
        struct node *next, *prev;
};

void foo(struct node* n) {
  printf("n->next = %p\n",n->next);
  n->next->next->prev=n;
  printf("n->next = %p\n",n->next);
};

int main(int argc,char **argv){
        struct node a = { },b = { };
        struct node *c = NULL;

        c = ((void*)&(a.next)) - sizeof(void*);
        b.next = c;
        a.next = &b;

        foo(&a);
}


-- 

vogel at pi2 dot physik dot uni-erlangen dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vogel at pi2 dot physik dot
                   |                            |uni-erlangen dot de


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

[Bug middle-end/32856] Invalid optimization in the face of aliasing

[falk at debian dot org]

------- Comment #7 from falk at debian dot org  2007-07-23 14:17 -------
(In reply to comment #6)
> This program demonstrates the problem, it creates different output depending on
> if compiled with or without optimisation.

This does not demonstrate the problem, since your code has undefined behavior
(already c = ... is undefined). You really need something like the union
mentioned earlier.


-- 


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

[Bug middle-end/32856] Invalid optimization in the face of aliasing

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2007-07-24 12:09 -------
You may only access union members through the union, not through other
pointers.
GCC is perfectly valid in caching n->next in the first example.  So, for
comment #4, it is true that &u.a.n.next == &u.b.n.prev, but you have to do
accesses to n->next and n->prev through the _union_, otherwise the example
is not valid.  So you you would need

  struct node {
    union u *prev;
    union u *next;
  };

  union {
    struct {
      void* unused;
      struct node n;
    } a;
    struct node b;
  } u;

or another creative way of doing all accesses to ->prev and ->next through
the union type.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID


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

[Bug middle-end/32856] Invalid optimization in the face of aliasing

[falk at debian dot org]

------- Comment #9 from falk at debian dot org  2007-07-25 08:24 -------
(In reply to comment #8)
> You may only access union members through the union, not through other
> pointers.

Where is this documented? I thought it should be in extend.texi, but I couldn't
find it...


-- 


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