aliasing again (was Re: gcc compiler bug (sparc, ppc))

[Till Straumann]

Sergei Organov wrote:
> Till Straumann <strauman at slac.stanford.edu> writes:
>   
>> I found that gcc produces bad code for the
>> following example:
>>
>> struct node {
>>      struct node *next, *prev;
>> };
>>
>> void xtract(struct node *x)
>> {
>> struct node *n, *p;
>>     n = x->n;
>>     p = x->p;
>>     n->prev = p;
>>     p->next = n;
>> }
>>     
>
> This doesn't compile:
>
> np.c: In function ‘xtract’:
> np.c:8: error: ‘struct node’ has no member named ‘n’
> np.c:9: error: ‘struct node’ has no member named ‘p’
>
> I think you mean:
>
> void xtract(struct node *x)
> {
>     struct node *n, *p;
>     n = x->next;
>     p = x->prev;
>     n->prev = p;
>     p->next = n;
> }
>
> right?
>
>   
>> powerpc-rtems-gcc -O -fschedule-insns -fno-strict-aliasing
>> (version 4.1.1) produces:
>>     
> [...]
>   
>> The order of the last two assignments was swapped
>> which makes a difference in the special case where &p->next and
>> &n->prev are addressing the same location but n != p.
>>     
>
> You mean when *n and *p overlap like this?:
>
>   n ->  |next|prev|
>   p ->       |next|prev|
>
>   
>> The bug is apparently triggered by -fschedule-insns; if I turn
>> on all other optimizations (including -fstrict-aliasing) correct
>> code is generated.
>>     
>
> -fstrict-aliasing should have no effect here, I think, as all the
> pointers involved have the same type and are therefore allowed to alias
> each other anyway.
>   
*wrong* (for the x-th time) -- strict-aliasing *could* have an effect here.

For the alias rule it is irrelevant if
the two pointers are of the same type. What matters is that
the *underlying object* matches the pointer. In this case,
'p' would *NOT* point to a legal 'struct node', hence 'p' would be
an illegal alias (but the compiler chose not to use the rule
for any optimization here -- -fno-strict-aliasing didn't make a difference).

Consider the similar code:

struct yy {
   int a,b;
};

void corrupt(struct yy **ppy)
{
   ppy[1]->a = 1;
   ppy[0]->b = 2;
}

The compiler (4.1.1, powerpc, -O2 -fstrict-aliasing)
produces

00000014 <corrupt>:
  14:   81 43 00 00     lwz     r10,0(r3)
  18:   38 00 00 01     li      r0,1
  1c:   81 63 00 04     lwz     r11,4(r3)
  20:   39 20 00 02     li      r9,2
  24:   91 2a 00 04     stw     r9,4(r10)
  28:   90 0b 00 00     stw     r0,0(r11)
  2c:   4e 80 00 20     blr

i.e., write operations are inverted:

ppy[0]->b = 2; ppy[1]->a = 1;

which gives an incorrect result if

      | a , b |
ppy[0]--^

ppy[1]------^

This is not a compiler bug but a violation of the
alias rule (ppy[1] is an invalid alias, it doesn't point
to a legal 'struct yy').

If I compile with -O2 -fno-strict-aliasing
I get

00000014 <corrupt>:
  14:   81 23 00 04     lwz     r9,4(r3)
  18:   38 00 00 01     li      r0,1
  1c:   90 09 00 00     stw     r0,0(r9)
  20:   38 00 00 02     li      r0,2
  24:   81 63 00 00     lwz     r11,0(r3)
  28:   90 0b 00 04     stw     r0,4(r11)
  2c:   4e 80 00 20     blr

I.e., the stuff is now written in the correct order.


-- Till
> PPC GCC 2.95.2 seems to produce correct code using
>
> powerpc-rtems-gcc -O -fschedule-insns -fno-strict-aliasing:
>
> xtract:
> 	lwz %r11,0(%r3) # r11 = n = x->next
> 	lwz %r9,4(%r3)  # r9  = p = x->prev
> 	stw %r9,4(%r11) # n->prev = p
> 	stw %r11,0(%r9) # p->next = n
> 	blr
>
>
> Overall, it looks like gcc bug indeed. Did you file bug-report?
>
> -- Sergei.
>