Bug 32856 - Invalid optimization in the face of aliasing
Summary: Invalid optimization in the face of aliasing
Status: RESOLVED INVALID
Alias: None
Product: gcc
Classification: Unclassified
Component: middle-end (show other bugs)
Version: 4.2.1
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2007-07-22 17:06 UTC by felix-gcc
Modified: 2007-07-25 08:24 UTC (History)
3 users (show)

See Also:
Host: x86_64-unknown-linux-gnu
Target: x86_64-unknown-linux-gnu
Build: x86_64-unknown-linux-gnu
Known to work:
Known to fail:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description felix-gcc 2007-07-22 17:06:04 UTC
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.
Comment 1 felix-gcc 2007-07-22 17:09:17 UTC
Well, since n is passed in a register, it can assume that n is still the same here. :-)
Comment 2 felix-gcc 2007-07-22 17:12:42 UTC
FWIW, the C compilers from Intel and Sun do reload n->next.
Comment 3 Falk Hueffner 2007-07-22 23:01:10 UTC
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.
Comment 4 felix-gcc 2007-07-22 23:08:39 UTC
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.
Comment 5 Falk Hueffner 2007-07-22 23:19:12 UTC
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.
Comment 6 Christian Vogel 2007-07-23 10:08:51 UTC
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);
}
Comment 7 Falk Hueffner 2007-07-23 14:17:28 UTC
(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.
Comment 8 Richard Biener 2007-07-24 12:09:25 UTC
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.
Comment 9 Falk Hueffner 2007-07-25 08:24:34 UTC
(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...