Bug 14319 - incorrect optimization of union of structs with common initial sequences
Summary: incorrect optimization of union of structs with common initial sequences
Status: SUSPENDED
Alias: None
Product: gcc
Classification: Unclassified
Component: rtl-optimization (show other bugs)
Version: tree-ssa
: P2 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: alias, wrong-code
: 42432 (view as bug list)
Depends on:
Blocks:
 
Reported: 2004-02-27 05:29 UTC by Jeff Sturm
Modified: 2015-04-26 00:14 UTC (History)
3 users (show)

See Also:
Host: i686-pc-linux-gnu
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2005-12-28 06:34:39


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Jeff Sturm 2004-02-27 05:29:21 UTC
Given:

struct X {int x;};
struct Y {int y;};
                                                                                
union U {struct X x; struct Y y;};
                                                                                
int f(struct X *xp, struct Y *yp) {
    xp->x = 0;
    yp->y = 1;
    return xp->x;
}
                                                                                
int main(void) {
    union U u;
    return f(&u.x, &u.y);
}

gcc from tree-ssa decides that xp->x and yp->y do not conflict, despite the
presence of a union.  Compiled with -O2, this program returns 1 for mainline, 0
for tree-ssa.

See discussion in http://gcc.gnu.org/ml/gcc/2004-02/msg01070.html and DR 257
(http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/dr_257.htm).

6.5.2.3#5 reads:

    [#5] One special guarantee is made in order to simplify the use of unions:
if a union contains several structures that share a common initial sequence (see
below), and if the union object currently contains one of these structures, it
is permitted to inspect the common initial part of any of them anywhere that a
declaration of the complete type of the union is visible. Two structures share a
common initial sequence if corresponding members have compatible types (and, for
bit-fields, the same widths) for a sequence of one or more initial members.


The structs X and Y in the example above have a common initial sequence and are
contained in a visible union declaration, so depending on how one interprets the
statement in 6.5.2.3#5 (I am certainly not an expert) either the code example is
invalid, or the compiler must assume the members of X and Y can alias.
Comment 1 Richard Henderson 2004-02-27 08:37:46 UTC
As gcc currently reads 6.5.2.3#5, you must actually use the union type
at the point of reference.  I.e. u.x.x and u.y.y will be considered to
conflict, as would up->x.x and up->y.y.  This implementation detail is
even documented in the -fstrict-aliasing option summary.

Any change in behaviour here will have to wait until DR 257 is resolved.
Comment 2 Wolfgang Bangerth 2004-02-27 15:19:35 UTC
I can't believe the wording means what you imply. Assume that caller 
and callee are in different translation units, then there is no 
way for the compiler to see that the two arguments to the called function 
may in fact be members of the same union. 
 
So the only way to assume that they could alias each other is to 
search the universe for a union type in which both of them are members. 
That certainly can't be the intent of the standard or DR. It only makes 
sense, if as RTH says the access is through such a union. 
 
W. 
Comment 3 Jeff Sturm 2004-02-27 19:07:59 UTC
(In reply to comment #2)
> I can't believe the wording means what you imply. Assume that caller 
> and callee are in different translation units, then there is no 
> way for the compiler to see that the two arguments to the called function 
> may in fact be members of the same union. 

Isn't that the reason for the visibility rule?  Read the committee's response to
DR 257.

> So the only way to assume that they could alias each other is to 
> search the universe for a union type in which both of them are members. 
> That certainly can't be the intent of the standard or DR. It only makes 
> sense, if as RTH says the access is through such a union. 

Yet it intrigues me then that the committee would have a need to create a
special exception for this one case.  In all other situations (type-punning) the
behavior seems to be implementation defined.

The 2nd example in 6.5.2.3#8 is equivalent to mine, except for the scope of the
union declaration.

Despite RTH's comment I don't see any mention of this exception for common
initial sequences in the -fstrict-aliasing docs.  There are general examples of
type-punning though.

Anyhow... folks, I don't really care one way or other.  I wasn't even aware of
DR 257 prior to Dan Nicolaescu's message.  If this is considered settled for GCC
pending any clarification from the committee, then the PR might as well be closed.
Comment 4 Wolfgang Bangerth 2004-02-27 19:24:10 UTC
Leaving aside questions of what the standard actually (is supposed to) mean: 
if the aliasing rules are changed as you propose, then 
- adding a union somewhere to a code will change the code generated for 
  the function in your example, even if this union is not actually used 
  anywhere 
- this takes away quite a number of opportunities for optimization, since 
  it is certainly not uncommon for code to use small structures that have, 
  say, an integer or pointer as first argument (think iterators and 
  accessors). 
 
In my eyes, both are not exactly positive consequences. But that's a personal 
opinion, not a language lawyer's statement. 
 
W. 
Comment 5 Richard Henderson 2004-03-03 01:05:27 UTC
confirming in order to...
Comment 6 Richard Henderson 2004-03-03 01:06:24 UTC
... suspend it until we can figure out what the language is supposed to mean.
Comment 7 Andrew Pinski 2009-12-19 03:45:20 UTC
*** Bug 42432 has been marked as a duplicate of this bug. ***
Comment 8 Daniel Villeneuve 2009-12-19 14:41:14 UTC
(In reply to comment #7)
> *** Bug 42432 has been marked as a duplicate of this bug. ***
> 

Sorry for the duplicate.  Seems I did not search enough...

The resolution I've found for DR 257 is that there are no defects and that the standard does not need to be changed.

The argument of DR 257 is about asking why the wording of 6.5.2.3#5 would be necessary (i.e., not redundant with the rest of the standard).

DR 257 mentions 2 possibilities:
a) padding: DR 257 rules that out, concluding that 6.5.2.3#5 is not needed for that case.
b) aliasing from two different structs: DR 257 raises a special case with no common initial prefix and concludes on that specific case that 6.5.2.3#5 is not needed for that case too.

However, the bug currently raised falls in neither a) nor b).  It's about aliasing two different structs that actually have a common initial prefix.  So maybe the wording of 6.5.2.3#5 is needed for _that_ case.

But if we choose the interpretation brought by RTH in comment #1, to the effect that the common initial sequence should be accessed through a union, then there is no need for the wording of 6.5.2.3#5 specifying "anywhere that a declaration of the complete type of the union is visible", because it's not possible to access u.x.x without such a declaration in scope.

Since resolution to DR 257 seems to confirm that the wording is the intended one (including that no words are meaningless and redundant), then the above interpretation cannot stand.

Therefore, I would say that the mere visibility of the union when compiling f in the example instructs the compiler that xp and yp are possible aliases.  Again from DR 257, if one wants to tell the compiler that no such aliasing occurs, the "restrict" keyword can then be used.
Comment 9 Andrew Pinski 2015-04-26 00:14:59 UTC
*** Bug 65892 has been marked as a duplicate of this bug. ***