GCC aliasing rules: more aggressive than C99?
The aliasing policies that GCC implements seem to be more strict than
what is in the C99 standard. I am wondering if this is true or whether
I am mistaken (I am not an expert on the standard, so the latter is
definitely possible).
The relevant text is:
An object shall have its stored value accessed only by an lvalue
expression that has one of the following types:
* a type compatible with the effective type of the object,
[...]
* an aggregate or union type that includes one of the aforementioned
types among its members (including, recursively, a member of a
subaggregate or contained union), or
To me this allows the following:
int i;
union u { int x; } *pu = (union u*)&i;
printf("%d\n", pu->x);
In this example, the object "i", which is of type "int", is having its
stored value accessed by an lvalue expression of type "union u", which
includes the type "int" among its members.
I have seen other articles that interpret the standard in this way.
See section "Casting through a union (2)" from this article, which
claims that casts of this sort are legal and that GCC's warnings
against them are false positives:
http://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html
However, this appears to be contrary to GCC's documentation. From the
manpage:
Similarly, access by taking the address, casting the resulting
pointer and dereferencing the result has undefined behavior, even
if the cast uses a union type, e.g.:
int f() {
double d = 3.0;
return ((union a_union *) &d)->i;
}
I have also been able to experimentally verify that GCC will mis-compile
this fragment if we expect the behavior the standard specifies:
int g;
struct A { int x; };
int foo(struct A *a) {
if(g) a->x = 5;
return g;
}
With GCC 4.3.3 -O3 on x86-64 (Ubuntu), g is only loaded once:
:
0: 8b 05 00 00 00 00 moveax,DWORD PTR [rip+0x0]# 6
6: 85 c0 test eax,eax
8: 74 06 je 10
a: c7 07 05 00 00 00 movDWORD PTR [rdi],0x5
10: f3 c3 repz ret
But this is incorrect if foo() was called as:
foo((struct A*)&g);
Here is another example:
struct A { int x; };
struct B { int x; };
int foo(struct A *a, struct B *b) {
if(a->x) b->x = 5;
return a->x;
}
When I compile this, a->x is only loaded once, even though foo()
could have been called like this:
int i;
foo((struct A*)&i, (struct B*)&i);
>From this I conclude that GCC diverges from the standard, in that it does not
allow casts of this sort. In one sense this is good (because the policy GCC
implements is more aggressive, and yet still reasonable) but on the other hand
it means (if I am not mistaken) that GCC will incorrectly optimize strictly
conforming programs.
Clarifications are most welcome!
Josh
Re: GCC aliasing rules: more aggressive than C99?
Richard Guenther gmail.com> writes:
> On Sun, Jan 3, 2010 at 6:46 AM, Joshua Haberman
gmail.com> wrote:
> > The aliasing policies that GCC implements seem to be more strict than
> > what is in the C99 standard. I am wondering if this is true or whether
> > I am mistaken (I am not an expert on the standard, so the latter is
> > definitely possible).
> >
> > The relevant text is:
> >
> > An object shall have its stored value accessed only by an lvalue
> > expression that has one of the following types:
> >
> > * a type compatible with the effective type of the object,
> > [...]
> > * an aggregate or union type that includes one of the aforementioned
> >types among its members (including, recursively, a member of a
> >subaggregate or contained union), or
>
> Literally interpreting this sentence the way you do removes nearly all
> advantages of type-based aliasing that you have when dealing with
> disambiguating a pointer dereference vs. an object reference
> and thus cannot be the desired interpretation (and thus we do not allow this).
Thank you for the information. I am very interested in distilling this
issue into a concise and easy to understand guideline that C and C++
programmers can use to determine whether they are following the rules
correctly or not, especially since the warnings are not perfect. The
GCC manpage gives a basic rule:
In particular, an object of one type is assumed never to reside at the
same address as an object of a different type, unless the types are
almost the same. For example, an "unsigned int" can alias an "int",
but not a "void*" or a "double". A character type may alias any other
type.
However, this explanation does not address how the rule applies to
aggregates (structures and arrays) and unions. Here is my attempt;
please correct anything that looks wrong.
The best way I have had this explained to me so far is that
dereferencing "upcasted" pointers is ok, but "downcasted" pointers not.
For the purposes of this explanation only, we define "upcasts" and
"downcasts" as:
struct A { int x; } a;
int i;
int *pi = &a.x; // upcast
int foo = *pi; // ok
struct A *pa = (struct A*)&i; // downcast
int bar = pa->x;// NOT ok
struct A a2 = *pa; // NOT ok
A distinguishing feature of the downcast is that it requires an actual
cast. So in general, casts from one pointer type to another indicate
a likely problem. Pointer casts *can* be valid, but only if you know
that the object was previously written as the casted-to type:
struct A { int x; } a;
int i;
int *pi = &a.x; // upcast
// this downcast is just "undoing" the previous upcast.
struct A *pa = (struct A*)&i;
int foo = pa->x; // ok
This is why perfect warnings about this issue are not possible; if we
see a downcast in isolation, we do not know if it is undoing a previous
upcast or not. Only a tool like valgrind could check this perfectly, by
observing reads and writes at runtime and checking the types of pointers
that were used to perform the read/write.
It is possible in C (not C++) to run into trouble even without pointer
casts, since void* can assign to any pointer type without a cast:
int i;
void *voidp = &i;
// Effective downcast.
struct A *pa = voidp;
int foo = pa->x; // NOT ok
But since chars can alias anything, it is always allowed to read or
write an object's representation via char*.
int i;
char ch = *(char*)&i; // ok
char charray[sizeof(long)] = {...};
long l = *(long*)charray; // ok
This does not mean that casts to/from char* are always safe, for the
same reason that we have to watch out for void*: the object may have
previously been written as a different type.
Besides observing the upcast/downcast rule, the other major rule is that
pointers to union members may only be dereferenced for the *active*
union member, which can only be set by using the union directly.
union U {
int i;
long l;
} u;
int *pi = &u.i;
long *pl = &u.l;
u.i = 5;
int foo = *pi; // ok, u.i is the active member.
long bar = *pl; // NOT ok, u.l is not the active member.
Josh
Re: GCC aliasing rules: more aggressive than C99?
Andrew Haley redhat.com> writes:
> On 01/03/2010 10:53 AM, Richard Guenther wrote:
> > GCC follows its own documentation here, not some random
> > websites and maybe not the strict reading of the standard.
>
> GCC is compatible with C99 in this regard.
I do not believe this is true. Your argument that GCC complies with C99
(which you moved to gcc-help@) is based on the argument that these are
not compatible types:
union u { int x; }
int x;
However, I did not claim that they are compatible types, nor does my
argument rely on them being compatible types. Rather, my argument is
based on section 6.5, paragraph 7 of C99, which I quoted, which
specifies the circumstances under which an object may or may not be
aliased. The case of compatible types is one case, but not the only
case, in which values may be aliased according to the standard.
Josh
Re: GCC aliasing rules: more aggressive than C99?
Patrick Horgan yahoo.com> writes: > Since it would be hard to read this any other way, it seems then you- > maintain that you found a bug in the standard, has it been brought up to- > the committee? The latest draft I see still has that wording. Doesn't- > seem to be on the radar for C1x. I strongly agree that the standard should be brought into line with common practice, and that if this is not currently on the committee's radar someone with connections should raise the issue to them. Josh
Re: GCC aliasing rules: more aggressive than C99?
Richard Guenther gmail.com> writes:
> On Sun, Jan 3, 2010 at 10:55 PM, Joshua Haberman
gmail.com> wrote:
> > This is why perfect warnings about this issue are not possible; if we
> > see a downcast in isolation, we do not know if it is undoing a previous
> > upcast or not. Only a tool like valgrind could check this perfectly, by
> > observing reads and writes at runtime and checking the types of pointers
> > that were used to perform the read/write.
>
> Correct (though valgrind operates at a too low level to know access types).
Do the DWARF debugging symbols have enough information to determine the
pointer type that was used for each load/store?
> > char charray[sizeof(long)] = {...};
> > long l = *(long*)charray; // ok
>
> not correct ;) (the lvalue has to be of character type, yours is of
> type 'long' - the type of the actual object does not matter)
I see -- good catch. To make it valid, I suppose "memcpy" could be used
instead.
> Correct. C++ has the notion of dynamic types, so with C++
>
> int i;
> *(foat *)&i = 0.0;
> float f = *(float *)&i;
>-
> is ok (well - it's ok with a placement new, but a pointer cast is all
> GCC sees here). The store changes the dynamic type of the
> memory stored to and thus further reads are only valid using
> the same type. GCC implements this also for C, but only starting
> with GCC 4.5.
C++'s notion of a "dynamic type" seems to be the same as what C99 calls
the "effective type." See C99, Section 6.5, paragraph 6. Also see
Defect Report #236 where the issue is raised, though the committee's
reasoning does not make sense to me:
http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_236.htm
(Thanks to Daniel Berlin for pointing me to the DR).
Josh
Re: GCC aliasing rules: more aggressive than C99?
By the way, here is one case I tested where I was surprised GCC was not
more aggressive:
extern void bar();
int foo(int *i) {
if(*i) bar();
return *i;
}
With GCC 4.4.1 -O3 (Ubuntu, x86-64) this reloads *i if bar is called. I
suppose you have to allow that either "i" or "*i" is accessible as a
global. But this is a pretty big bummer, because it means that any
function call forces reloads of any data that was read from a pointer.
"restrict" doesn't help here, nor does "const". The only way to prevent
these reloads is to manually read the data into stack variable(s):
extern void bar();
int foo(int *i) {
int i_val = *i;
if(i_val) bar();
return i_val;
}
Josh
Re: GCC aliasing rules: more aggressive than C99?
Andrew Haley redhat.com> writes: > On 01/03/2010 10:14 PM, Joshua Haberman wrote: > > Andrew Haley redhat.com> writes: > "6.3.2.3 > > "A pointer to an object or incomplete type may be converted to a > pointer to a different object or incomplete type. If the resulting > pointer is not correctly aligned for the pointed-to type, the > behavior is undefined. Otherwise, when converted back again, the > result shall compare equal to the original pointer." > > This is *all* you are allowed to do with the converted pointer. You > may not dereference it. The text you quoted does not contain any "shall not" language about dereferencing, so this conclusion does not follow. > [Section 6.3.2.3] is the core rule that governs C's aliasing. Section 6.5 paragraph 7 contains this footnote: The intent of this list is to specify those circumstances in which an object may or may not be aliased. I am not sure why you discard the significance of this section. Also under your interpretation memcpy(&some_int, ..., ...) is illegal, because memcpy() will write to the int's storage with a pointer type other than int. Josh
Re: GCC aliasing rules: more aggressive than C99?
Erik Trulsson student.uu.se> writes: > On Mon, Jan 04, 2010 at 08:17:00PM +, Joshua Haberman wrote: > > The text you quoted does not contain any "shall not" language about > > dereferencing, so this conclusion does not follow. > > It doesn't have to use any "shall not" language. If the standard does not > say that any particular action is allowed or otherwise defines what it > does, then that action implicitly has undefined behaviour. Section 6.5 does define circumstances under which converted pointers may be dereferenced. Section 6.3.2.3 does not include any language prohibiting it, so it does not support the assertion it was quoted to support, and it is irrelevant in the context of this discussion. > > > [Section 6.3.2.3] is the core rule that governs C's aliasing. > > > > Section 6.5 paragraph 7 contains this footnote: > > > > The intent of this list is to specify those circumstances in which an > > object may or may not be aliased. > > > > I am not sure why you discard the significance of this section. Also > > under your interpretation memcpy(&some_int, ..., ...) is illegal, > > because memcpy() will write to the int's storage with a pointer type > > other than int. > > Your conclusion does not follow since the standard does not say what (if > any) pointer type memcpy() will use internally. It is not even necessary > that memcpy() is implemented in C. It says that it will copy characters. More importantly, you are still ignoring section 6.5 without saying why. Josh
Re: GCC aliasing rules: more aggressive than C99?
Robert Dewar adacore.com> writes: > In any case the gcc interpretation is clearly what's > intended in my view, so if it can be argued that the > standard is inconsistent with this interpretation (I > am unconvinced that this burden has been met), then > the conclusion is to add a clarification to the > standard, not to modify the gcc behavior. I agree with you completely on this point. My position throughout this thread has been that GCC should keep its existing type-based aliasing behavior. I think the GCC policy represents a good trade-off between a policy that is not aggressive enough and a policy that is too hard to follow. In my view the C99 standard quite clearly specifies a policy that is less aggressive than what GCC implements. I think it's hard to come to any other conclusion; section 6.5 paragraph 7 contains a footnote explicitly stating that the intention is to specify conditions under which values may be aliased, and one of the rules allows for an aliasing condition that GCC does not respect. I have not heard any credible rebuttal to this point, or any explanation of what 6.5 paragraph 7 *does* mean, if it is not intended to specify aliasing rules. I am guessing that the committee didn't have enough practical experience with aliasing policies to come to Richard's conclusion that the standard's policy "removes nearly all advantages of type-based aliasing that you have when dealing with disambiguating a pointer dereference vs. an object reference." In this sense I think this is a bug in the standard, and I hope the committee will take it up in C1x. Josh
Re: GCC aliasing rules: more aggressive than C99?
Andrew Haley redhat.com> writes: > but > > (union u*)&i > > is not a legal lvalue expression because the dereference is undefined > behaviour. Your example does not contain a dereference. > You may only dereference a pointer as permitted by 6.3.2.3. 6.3.2.3 does not mention dereferencing at all; it only addresses pointer conversion. Dereferencing is defined in 6.5.3.2. But let me ask you this. What do you think 6.5 paragraph 7 means? For example, are you also of the opinion that this is illegal? int i; unsigned int *pui = (unsigned int*)&i; unsigned int ui = *pui; I believe that GCC allows this (Richard can correct me if I am wrong), but under your interpretation this would be illegal because "int" and "unsigned int" are not compatible types. The only thing that makes this legal is 6.5 paragraph 7, where one of the allowed aliasing scenarios is: a type that is the signed or unsigned type corresponding to the effective type of the object Josh
Re: GCC aliasing rules: more aggressive than C99?
Erik Trulsson student.uu.se> writes:
> On Sun, Jan 03, 2010 at 05:46:48AM +, Joshua Haberman wrote:
> > The aliasing policies that GCC implements seem to be more strict than
> > what is in the C99 standard. I am wondering if this is true or whether
> > I am mistaken (I am not an expert on the standard, so the latter is
> > definitely possible).
> >-
> > The relevant text is:
> >-
> > An object shall have its stored value accessed only by an lvalue
> > expression that has one of the following types:
> >-
> > * a type compatible with the effective type of the object,
> > [...]
> > * an aggregate or union type that includes one of the aforementioned
> > types among its members (including, recursively, a member of a
> > subaggregate or contained union), or
> >-
> > To me this allows the following:
> >-
> > int i;
> > union u { int x; } *pu = (union u*)&i;
> > printf("%d\n", pu->x);
> >-
> > In this example, the object "i", which is of type "int", is having its
> > stored value accessed by an lvalue expression of type "union u", which
> > includes the type "int" among its members.
>-
> Even with your interpretation of the C99 standard that example would be
> allowed only if '*pu' is a valid lvalue of type 'union u'. (Since pu->x
> is equivalent to (*pu).x)
>-
> First of all the conversion (union u*)&i is valid only if the alignment
> of 'i' is suitable for an object of type 'union u'. Lets assume that is the
> case. (Otherwise just making that conversion would result in undefined
> behaviour.) (See 6.3.2.3 clause 7.)
This is true. You could get around this particular point by saying:
int *i = malloc(sizeof(*i));
*i = 5;
union u { int x; } *pu = (union u*)i;
printf("%d\n", pu->x);
...since the return from malloc() is guaranteed to be suitably aligned for
any object (7.20.3). But your point is taken.
> There is however no guarantee that the conversion yields a valid "pointer to
> union u". If not then dereferencing it (with the expression '*pu') has
> undefined behaviour. (See 6.5.3.2 clause 4)
I think this is a bit of a stretch. It is true that 6.5.3.2 says that
dereferencing invalid values has undefined behavior. But if you are
saying that the standard has to explicitly say that a pointer conversion
will not result in an invalid value (even when suitably aligned), then
the following is also undefined:
int i;
unsigned int *pui = (unsigned int*)&i;
unsigned int ui = *pui;
Andrew cited 6.3.2.3p2 as support for why this is defined, but that
paragraph deals with qualifiers (const, volatile, and restrict).
"unsigned" is not a qualifier. There is no part of the standard that
guarantees that a pointer conversion from "int*" to "unsigned int*" will
not result in an invalid value.
> So your example contains undefined behaviour even without considering the
> parts of 6.5 clause 7 that you quoted.
>-
> Moreover I think you are misinterpreting 6.5 clause 7 (which I concede is
> fairly easy since it is not quite as unambiguous as one could wish).
> I believe that paragraph should not be interpreted as automatically allowing
> all accesses that correspond to one of the sorts listed. Rather it should
> be interpreted as saying that if an access is not included in that list then
> it is not allowed, but even if it is included in that list there could be
> other reasons why it is not allowed. (I.e. just as the attached footnote
> suggests it is a list of what types of aliasing are allowed, not of which
> pointers may be dereferenced.)
Interesting. I think it is plausible that this is what the committee
intended. It like the committee wanted to give a heads-up to
implementations that pointers to primitive types can alias pointers to
those same types within unions and aggregates, just as a result of
taking the address of a member.
In any case I definitely agree that this could be clarified, and I hope the
standards committee will take this up for C1x.
Thank you for your thoughtful analysis.
Josh
Re: GCC aliasing rules: more aggressive than C99?
Richard Guenther gmail.com> writes:
> On Wed, Jan 6, 2010 at 7:20 PM, Nick Stoughton msbit.com>
wrote:
> > The C1x timetable has us finishing the draft for an initial ballot this
> > summer (the April Florence meeting being the last chance to submit new
> > material). The best expert I know on the type based aliasing stuff is
> > Clark Nelson at Intel (clark.nelson intel.com). We did spend a
> > considerable amount of time at the recent Santa Cruz meeting discussing
> > this subject ... see N1409 and N1422 (the minutes including a summary of
> > the discussion on N1409).
> > http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1409.htm
> >
> > http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1422.pdf
> [...]
> I have no idea on how to raise this issue with the std body, somebody
> else might and can pass on the above example please.
In the notes that Nick referenced it says:
Is there anybody that thinks the rules are clear enough? No one is
really able to interpret them. So it seems that they are not
clear enough. The problem is how to state them.
[...]
ACTION: Clark to work on a clearer formulation of what the rules are,
re: N1409.
So it wounds like Clark is already working on this. We should just write
to him and point him to this thread. I can do this.
With regard to a clearer way to state the rules: I think the rules would
be easier to understand if the normative part only addressed the ways in
which object aliases could be *created*. For example, the rules could
state that:
struct A { int x; } a;
int *pi = &a.x;
...is a valid way to create an int* that aliases a struct member, whereas:
int i;
struct A { int x; } *a = (struct u*)&i;
...is not. Then an informative section could address the consequences of
those rules with respect to the assumptions you can make when optimizing
a function in isolation:
type3 x;
void foo(type1 *a, type2 *b) {
// can a and b alias each other? can either of them alias x?
}
The root of my confusion at least was thinking that the standard was
describing legal ways aliases could be created, but it was actually
describing what aliases could come to exist through other processes.
Since the rules governing how aliases may be created are simpler, it
makes sense to me to have the normative rules about alising describe the
creation of aliases, and then let compilers implement whatever
optimizations they can dream up that still respect those rules.
I also think the aliasing rules should more directly address the issue
raised in DR#236:
http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_236.htm
Josh
Re: GCC aliasing rules: more aggressive than C99?
Erik Trulsson student.uu.se> writes: > > int i; > > unsigned int *pui = (unsigned int*)&i; > > unsigned int ui = *pui; > > (First I will assume that 'i' will be assigned some value, to make sure it > does not contain a trap-representation, or the assignment to 'ui' would have > undefined behaviour.) > > I think 6.2.5 clause 27 is very relevant for this. It says that 'pointer to > int' and 'pointer to union' do not need to have the same representation as > each other. It also seems that 'pointer to int' and 'pointer to unsigned > int' do not need to have the same representation requirements (at least I > cannot find anything that says that signed and unsigned variants are > compatible types.) (Which I must admit comes as a bit of a surprise to me.) > > So, yes, that example does technically seem to be undefined (but I don't > know of any real-world implementation where it would not work as expected.) I am wondering how, under this interpretation, an "int" and "unsigned int" could ever alias each other, as 6.5p7 says they can. I believe now (especially after the notes Nick pointed us to) that your interpretation of 6.5p7 is the intended one. But if that is the case, then we should expect to find some legal way in which "int" and "unsigned int" could come to be aliased. With your interpretation about pointer conversions, I don't see how this could be. Josh
useless stores generated when returning a struct -- bug?
I have a case where I think useless stores are being generated, but I
want to be sure before I file a bug. This is with gcc 4.4.3 on Ubuntu
10.04, x86-64.
I have been experimenting with returning structs from functions instead
of passing pointers to "out" parameters. This seems like it should be
more optimizer-friendly because you can avoid taking addresses of local
variables, which prevents them from possibly being aliased.
However in this test case, gcc is generating four stores that appear to
be completely useless:
#include
struct twoints { uint64_t a, b; } foo();
void bar(uint64_t a, uint64_t b);
void func() {
struct twoints s = foo();
bar(s.a, s.b);
}
$ gcc -Wall -c -o testbad.o -msse2 -O3 -fomit-frame-pointer testbad.c-
$ objdump -d -r -M intel testbad.o
testbad.o: file format elf64-x86-64
Disassembly of section .text:
:
0: 48 83 ec 28 subrsp,0x28
4: 31 c0 xoreax,eax
6: e8 00 00 00 00 call b
7: R_X86_64_PC32foo-0x4
b: 48 89 04 24 movQWORD PTR [rsp],rax
f: 48 89 54 24 08 movQWORD PTR [rsp+0x8],rdx
14: 48 89 d6movrsi,rdx
17: 48 89 44 24 10 movQWORD PTR [rsp+0x10],rax
1c: 48 89 54 24 18 movQWORD PTR [rsp+0x18],rdx
21: 48 89 c7movrdi,rax
24: 48 83 c4 28 addrsp,0x28
28: e9 00 00 00 00 jmp2d
29: R_X86_64_PC32 bar-0x4
Why is it storing rax and rdx to the stack twice? These stores are never
used AFAICS.
Josh
Re: useless stores generated when returning a struct -- bug?
Ian Lance Taylor google.com> writes: > Joshua Haberman gmail.com> writes: > > > I have a case where I think useless stores are being generated, but I > > want to be sure before I file a bug. This is with gcc 4.4.3 on Ubuntu > > 10.04, x86-64. > > I concur that this is a missed optimization bug. Thanks Ian. I'll file it as a bug. Josh
