Possible gcc bug in strict type aliasing

Possible gcc bug in strict type aliasing

[David Brown]

Hi,

I have been involved in a discussion in the comp.lang.c newsgroup, 
concerning a possible case of gcc being a bit too aggressive in 
optimising based on strict type alias analysis.  In the code below, gcc 
gives the result 100 when optimising -O2 or above on 64-bit targets (in 
which "int64_t" is a typedef for "long"), but 200 for lower 
optimisations, or with -fno-strict-aliasing, or on 32-bit targets (where 
"int64_t" is a typedef for "long long").  Other compilers such as clang 
and icc consistently give 200.

On x86-64 (linux target), the functions blah3 and test3 are compiled 
(-O2) to:

blah3:
         movq    $100, (%rdi)
         movl    $100, %eax
         movq    $200, (%rsi)
         ret
test3:
         movl    $100, %eax
         ret


With -O1 (or -O2 -fno-strict-aliasing), it compiles to:

blah3:
         movq    $100, (%rdi)
         movq    $200, (%rsi)
         movq    (%rdi), %rax
         ret
test3:
         movl    $200, %eax
         ret


gcc 4.7 onwards have this same code.  gcc 4.5 does less optimisation, 
and always returns 200.  gcc 4.6 is interesting - blah3 returns 100, 
while test3 returns 200, giving a mixture of the two.



The question is, is gcc's -O2 optimisation valid here?  Does the fact 
that the pointers come from dynamic memory (and therefore the buffer's 
effective type is only decided when written) affect that?

An interesting effect is that if the line "*t1p2 = temp;" is changed to 
"*t1p2 = temp + 1;", the compiled code is the same at -O1 and -O2, and 
returns 201 as the final result.



I have been testing this using the online compiler at gcc.godbolt.org, 
as this lets me easily pick different compiler versions and different 
settings, and view the resulting assembly code:

<https://gcc.godbolt.org/#compilers:!((compiler:g62,options:'-O2+-Wall+-Wextra+-x+c+-fstrict-aliasing',sourcez:FAAjGIEsDsGMBsCuATApiAPAZwC7JjgHQAWAfKGCFHEmprgE4wDmJ5lVMCK62e8kAEZsKELrV658AexGiQOAJ4AHVGgBmIeNOjMtOvQBUAjAG55S1RpAEAbABYA%2BjhCGATOY7gNMdCYBiALKGIABEAKTw8Mih8t6o6r6uxgBqAIIAMgCqAKIgxgAMBXE%2B0H5u6dl5bkXA8iYggvAAhsQAzAAUAG7SkMggAFTKxgA0ID19g8puAJTyAN7yYA0DOMbKY6vrHkuuboM4bsqeHMkKqAC2x3WnCusgALwgwycch8qPzzu3Wx9PJpVcqZKAB6EEgADqTBw6GaWGSu1WR0%2B7kBOWBYDBkOhsPh7l2MKunyRx1uWIASqhmv04XsCdtPh0TAMZu8MViUpAsEJ4OUFNIzspetAYQwQLAdF1UAxuTpEWtpp9CaSOFioZAYSBaSZdgxUDhEAxoAd1hjVeDKdStXjjPIAL43SgNGG4ToTZBzDiLW7uqafC7NKLSWAdbkAL1Q0k0TOMMxAAGoQOHI9H3DMZq8ncYQHqsIh4C4nk1Wp0NsoM7t1HrUB1y5mwHqDUac6g8wXMw6OAQQAGYN1eh6FrsGrn84Xzq6OhXbsomCL1B1QoZiOhRwWbPDQskgoYxmucNPTo3DcaCmbKPagAA%3D%3D)),filterAsm:(commentOnly:!t,directives:!t,labels:!t),version:3>

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

     typedef long long T1;
     typedef int64_t T2;
     #define T1FMT "%lld"
     #define T1VALUE 100
     #define T2VALUE 200

     T1 blah3(void *p1, void *p2)
     {
       T1 *t1p, *t1p2;
       T2 *t2p;
       T1 temp;

       t1p = p1;
       t2p = p2;
       *t1p = T1VALUE;   // Write as T1
       *t2p = T2VALUE;   // Write as T2
       temp = *t2p;      // Read as T2
       t1p2 = (T1*)t2p;  // Visible T2 to T1 pointer conversion
       *t1p2 = temp;     // Write as T1
       return *t1p;      // Read as T1
     }

     T1 test3(void)
     {
       void *p = malloc(sizeof (T1) + sizeof (T2));
       T1 result = blah3(p,p);
       free(p);
       return result;
     }
     int main(void)
     {
       T1 result = test3();
       printf("The result is " T1FMT, result);
       return 0;
     }

Re: Possible gcc bug in strict type aliasing

[Andrew Haley]

On 25/09/16 22:46, David Brown wrote:

I think the bug is here:

>        temp = *t2p;      // Read as T2
>        t1p2 = (T1*)t2p;  // Visible T2 to T1 pointer conversion
>        *t1p2 = temp;     // Write as T1

6.3.2.3 Pointers

7 A pointer to an object type may be converted to a pointer to a
  different object type. If the resulting pointer is not correctly
  aligned for the referenced type, the behavior is undefined.
  Otherwise, when converted back again, the result shall compare equal
  to the original pointer.

Note that you have permission only to convert the pointer back to the
original type and compare it.  You don't have permission to
dereference it as a different type.  IMO your program is undefined.

This is key to alias analysis: we know that a pointer to T1 can only
point to objects compatible with T1.  It's not possible to "hide" a
pointer to T2 from the compiler by converting it to T1, passing it to
a function, and then converting it back to T2 and dereferencing it.

If you lie to the compiler, it will get its revenge.

Andrew.

Re: Possible gcc bug in strict type aliasing

[David Brown]

On 26/09/16 11:32, Andrew Haley wrote:
> On 25/09/16 22:46, David Brown wrote:
> 
> I think the bug is here:
> 
>>        temp = *t2p;      // Read as T2
>>        t1p2 = (T1*)t2p;  // Visible T2 to T1 pointer conversion
>>        *t1p2 = temp;     // Write as T1
> 
> 6.3.2.3 Pointers
> 
> 7 A pointer to an object type may be converted to a pointer to a
>   different object type. If the resulting pointer is not correctly
>   aligned for the referenced type, the behavior is undefined.
>   Otherwise, when converted back again, the result shall compare equal
>   to the original pointer.
> 
> Note that you have permission only to convert the pointer back to the
> original type and compare it.  You don't have permission to
> dereference it as a different type.  IMO your program is undefined.
> 
> This is key to alias analysis: we know that a pointer to T1 can only
> point to objects compatible with T1.  It's not possible to "hide" a
> pointer to T2 from the compiler by converting it to T1, passing it to
> a function, and then converting it back to T2 and dereferencing it.

But with "*t1p2 = temp;", we are writing as a T1 through a pointer to
T1.  Then the return value is also read via a pointer to a T1 ("return
*t1p;").

It looks like gcc is simply ignoring the "*t1p2 = temp;" statement.
This may be because it knows any attempt to dereference t1p2 is
undefined (since it was created from a cast from a different pointer
type), or it may be because it knows that the effective type of *t1p2 is
actually a T2 since that's what was first stored at that address (from
"*t2p = T2VALUE").

Does that make sense?



If so, it seems like quite an aggressive optimisation, and one that may
surprise people.  Other compilers (clang, icc) treat it differently. And
the code generation for gcc here is quite fragile - changing "*t1p2 =
temp;" to "*t1p2 = temp + 1" changes the result from 100 to 201.  This
can be a true pain to debug when you have code that appears to work
correctly in your testing, but a small change somewhere leads - through
inlining and LTO - to this code later jumping silently in the output it
generates.

While I fully appreciate (and agree with) the policy of using undefined
behaviour effects to generate more efficient code, this looks like a
fairly subtle effect which silently generates unexpected code.

Perhaps it would be worth filing a request for better warnings here?
With -Wstrict-aliasing=1, gcc gives a warning "dereferencing type-punned
pointer might break strict-aliasing rules".  But the warning does not
appear with -Wstrict-aliasing=3, which is generally supposed to be more
accurate and which is the default (when -fstrict-aliasing and -Wall are
in effect).  If gcc uses strict aliasing in order to remove statements
entirely, should it not be able to give a warning with a wider variety
of warning options?


> 
> If you lie to the compiler, it will get its revenge.
> 

Yes, I know.  (I didn't write the code - it was created as an example of
code that may show questionable code generation in gcc.)

I'm okay with the compiler getting its revenge - but I would /really/
like it to tell me about it!

Re: Possible gcc bug in strict type aliasing

[Andrew Haley]

On 26/09/16 12:35, David Brown wrote:
> On 26/09/16 11:32, Andrew Haley wrote:
>> On 25/09/16 22:46, David Brown wrote:
>>
>> I think the bug is here:
>>
>>>        temp = *t2p;      // Read as T2
>>>        t1p2 = (T1*)t2p;  // Visible T2 to T1 pointer conversion
>>>        *t1p2 = temp;     // Write as T1
>>
>> 6.3.2.3 Pointers
>>
>> 7 A pointer to an object type may be converted to a pointer to a
>>   different object type. If the resulting pointer is not correctly
>>   aligned for the referenced type, the behavior is undefined.
>>   Otherwise, when converted back again, the result shall compare equal
>>   to the original pointer.
>>
>> Note that you have permission only to convert the pointer back to the
>> original type and compare it.  You don't have permission to
>> dereference it as a different type.  IMO your program is undefined.
>>
>> This is key to alias analysis: we know that a pointer to T1 can only
>> point to objects compatible with T1.  It's not possible to "hide" a
>> pointer to T2 from the compiler by converting it to T1, passing it to
>> a function, and then converting it back to T2 and dereferencing it.
> 
> But with "*t1p2 = temp;", we are writing as a T1 through a pointer to
> T1.  Then the return value is also read via a pointer to a T1 ("return
> *t1p;").

Sure, but we already have UB at that point, so the program can do
anything.  Once you have UB, all bets are off.

> It looks like gcc is simply ignoring the "*t1p2 = temp;" statement.
> This may be because it knows any attempt to dereference t1p2 is
> undefined (since it was created from a cast from a different pointer
> type),

I think so.

> If so, it seems like quite an aggressive optimisation, and one that
> may surprise people.

Probably, but it's the rule which makes type-based alias optimization
possible.

>> If you lie to the compiler, it will get its revenge.
>>
> 
> Yes, I know.  (I didn't write the code - it was created as an example of
> code that may show questionable code generation in gcc.)
> 
> I'm okay with the compiler getting its revenge - but I would /really/
> like it to tell me about it!

I'm sure, but it's not always even possible to detect this kind of
thing, at least not without a lot of additional complication in the
compiler and some more false positives.

Having said all of that, while I'm pretty sure that GCC is within its
rights as a C compiler to do what it does, there is no warning and
even -fsanitize=undefined does not warn.  And it really should, so
at the minimum there is some opportunity to improve GCC.

Andrew.

Re: Possible gcc bug in strict type aliasing

[Alexander Monakov]

I think there's an inconsistency in what's GCC is doing here.

I concede the original example may invoke UB if the first write to malloc'ed
region determines its type until free(). However, internally memory model in
GCC allowes writes to dynamically change the effective type of the underlying
storage: this is required to support C++ placement new, but the middle-end
rules are the same for C and C++.

So if you rewrite the original testcase in C++:

#include <new>
long foo(char *c1, char *c2)
{
     long      *p1 = new(c1) long;
     *p1 = 100;
     long long *p2 = new(c2) long long;
     *p2 = 200;
     long      *p3 = new(c2) long;
     *p3 = 200;
     return *p1;
}

you get very surprising results: the optimization happens depending on the value
of the last constant (switching 200 to 300 suppresses the transformation), or
depending on whether long and long long match in size (using a 32-bit target
suppresses the transformation). This points at least to an internal
inconsistency in GCC if not to a real bug; I've opened a Bugzilla PR:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77745 .

Alexander

Re: Possible gcc bug in strict type aliasing

[Vincent Lefevre]

On 2016-09-26 10:32:14 +0100, Andrew Haley wrote:
> On 25/09/16 22:46, David Brown wrote:
> 
> I think the bug is here:
> 
> >        temp = *t2p;      // Read as T2
> >        t1p2 = (T1*)t2p;  // Visible T2 to T1 pointer conversion
> >        *t1p2 = temp;     // Write as T1
> 
> 6.3.2.3 Pointers
> 
> 7 A pointer to an object type may be converted to a pointer to a
>   different object type. If the resulting pointer is not correctly
>   aligned for the referenced type, the behavior is undefined.
>   Otherwise, when converted back again, the result shall compare equal
>   to the original pointer.
> 
> Note that you have permission only to convert the pointer back to the
> original type and compare it.  You don't have permission to
> dereference it as a different type.  IMO your program is undefined.

I disagree. The above paragraph says nothing about dereferencing the
pointer; in particular, it does not disallow one to dereference it
as a different type. The restrictions about dereferencing are given
by 6.5#7 (itself based on 6.5#6, which defines the "effective type").
Moreover 6.5#7 restrictions are about write-read combinations, not
about read-write like in the above 3 lines of code.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

Re: Possible gcc bug in strict type aliasing

[Vincent Lefevre]

On 2016-09-26 17:28:38 +0300, Alexander Monakov wrote:
> I concede the original example may invoke UB if the first write to
> malloc'ed region determines its type until free().

No, the effective type is determined by the last write, not the
first one. The C standard says (6.5#6): "[...] 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, the effective type of an object is allowed to change.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

Re: Possible gcc bug in strict type aliasing

[Andrew Haley]

On 27/09/16 13:49, Vincent Lefevre wrote:
> On 2016-09-26 10:32:14 +0100, Andrew Haley wrote:
>> On 25/09/16 22:46, David Brown wrote:
>>
>> I think the bug is here:
>>
>>>        temp = *t2p;      // Read as T2
>>>        t1p2 = (T1*)t2p;  // Visible T2 to T1 pointer conversion
>>>        *t1p2 = temp;     // Write as T1
>>
>> 6.3.2.3 Pointers
>>
>> 7 A pointer to an object type may be converted to a pointer to a
>>   different object type. If the resulting pointer is not correctly
>>   aligned for the referenced type, the behavior is undefined.
>>   Otherwise, when converted back again, the result shall compare equal
>>   to the original pointer.
>>
>> Note that you have permission only to convert the pointer back to the
>> original type and compare it.  You don't have permission to
>> dereference it as a different type.  IMO your program is undefined.
> 
> I disagree. The above paragraph says nothing about dereferencing the
> pointer; in particular, it does not disallow one to dereference it
> as a different type.

Perhaps you are right with regard to original intent, but if so it's
very oddly worded.

AIUI without any explicit description of what should happen in any
situation, all bets are off.  This is the usual way of writing
language specifications, and indeed standards in general.  6.3.2.3
does not say that the converted pointer may be used for anything other
than an equality comparison; if there was the intention that anything
else was possible, why only mention equality comparisons?

Andrew.

Re: Possible gcc bug in strict type aliasing

[Markus Trippelsdorf]

On 2016.09.27 at 15:08 +0200, Vincent Lefevre wrote:
> On 2016-09-26 17:28:38 +0300, Alexander Monakov wrote:
> > I concede the original example may invoke UB if the first write to
> > malloc'ed region determines its type until free().
> 
> No, the effective type is determined by the last write, not the
> first one. The C standard says (6.5#6): "[...] 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, the effective type of an object is allowed to change.

Both examples are now fixed on trunk by Richi's patch. See:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77745

-- 
Markus

Re: Possible gcc bug in strict type aliasing

[Vincent Lefevre]

On 2016-09-27 14:10:13 +0100, Andrew Haley wrote:
> On 27/09/16 13:49, Vincent Lefevre wrote:
> > On 2016-09-26 10:32:14 +0100, Andrew Haley wrote:
> >> On 25/09/16 22:46, David Brown wrote:
> >>
> >> I think the bug is here:
> >>
> >>>        temp = *t2p;      // Read as T2
> >>>        t1p2 = (T1*)t2p;  // Visible T2 to T1 pointer conversion
> >>>        *t1p2 = temp;     // Write as T1
> >>
> >> 6.3.2.3 Pointers
> >>
> >> 7 A pointer to an object type may be converted to a pointer to a
> >>   different object type. If the resulting pointer is not correctly
> >>   aligned for the referenced type, the behavior is undefined.
> >>   Otherwise, when converted back again, the result shall compare equal
> >>   to the original pointer.
> >>
> >> Note that you have permission only to convert the pointer back to the
> >> original type and compare it.  You don't have permission to
> >> dereference it as a different type.  IMO your program is undefined.
> > 
> > I disagree. The above paragraph says nothing about dereferencing the
> > pointer; in particular, it does not disallow one to dereference it
> > as a different type.
> 
> Perhaps you are right with regard to original intent, but if so it's
> very oddly worded.

Hmm... I think I see your point. If I understand correctly you meant
that the standard does not define how the pointer is converted, and
it may magically point to some completely different place (address),
the only requirement being that when doing the reverse conversion,
one would get the original address.

I'm thinking of an example like the following one. Assume that you
have two different types T1 and T2 (not character types, otherwise
the conversion is well-defined by the standard) with the same size
and alignment requirements.

  T1 t;
  T1 *p1;
  T2 *p2;

  p1 = &t;
  p2 = (T2 *) p1;

I suppose that the compiler may choose as conversion rules:
  * When converting T1 * to T2 *, sizeof(T1) is added to the address.
  * When converting T2 * to T1 *, sizeof(T2) is subtracted from the
    address.

I suppose that such an implementation could be conforming. But David's
example would no longer work.

A solution could be:

  p2 = (T2 *) (void *) p1;

> AIUI without any explicit description of what should happen in any
> situation, all bets are off.  This is the usual way of writing
> language specifications, and indeed standards in general.  6.3.2.3
> does not say that the converted pointer may be used for anything other
> than an equality comparison; if there was the intention that anything
> else was possible, why only mention equality comparisons?

No, with the above point, one cannot even use this in a useful way
for comparisons (but one could use void * for comparisons).

But it might be a defect in the standard (or something I haven't
seen).

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

Re: Possible gcc bug in strict type aliasing

[Vincent Lefevre]

On 2016-09-27 15:38:52 +0200, Vincent Lefevre wrote:
> A solution could be:
> 
>   p2 = (T2 *) (void *) p1;

Oops, that would be incorrect too.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)