[Bug c/14319] New: incorrect optimization of union of structs with common initial sequences

[Bug c/14319] New: incorrect optimization of union of structs with common initial sequences

[jsturm at gcc dot gnu dot org]

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.

-- 
           Summary: incorrect optimization of union of structs with common
                    initial sequences
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P2
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: jsturm at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org
  GCC host triplet: i686-pc-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug c/14319] incorrect optimization of union of structs with common initial sequences

[rth at gcc dot gnu dot org]

------- Additional Comments From rth at gcc dot gnu dot org  2004-02-27 08:37 -------
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.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug c/14319] incorrect optimization of union of structs with common initial sequences

[bangerth at dealii dot org]

------- Additional Comments From bangerth at dealii dot org  2004-02-27 15:19 -------
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. 

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug c/14319] incorrect optimization of union of structs with common initial sequences

[jsturm at gcc dot gnu dot org]

------- Additional Comments From jsturm at gcc dot gnu dot org  2004-02-27 19:07 -------
(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.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug c/14319] incorrect optimization of union of structs with common initial sequences

[bangerth at dealii dot org]

------- Additional Comments From bangerth at dealii dot org  2004-02-27 19:24 -------
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. 

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug optimization/14319] [tree-ssa] incorrect optimization of union of structs with common initial sequences

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c                           |optimization
            Summary|incorrect optimization of   |[tree-ssa] incorrect
                   |union of structs with common|optimization of union of
                   |initial sequences           |structs with common initial
                   |                            |sequences
   Target Milestone|---                         |tree-ssa


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug optimization/14319] incorrect optimization of union of structs with common initial sequences

[rth at gcc dot gnu dot org]

------- Additional Comments From rth at gcc dot gnu dot org  2004-03-03 01:05 -------
confirming in order to...

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-03-03 01:05:27
               date|                            |
            Summary|[tree-ssa] incorrect        |incorrect optimization of
                   |optimization of union of    |union of structs with common
                   |structs with common initial |initial sequences
                   |sequences                   |
   Target Milestone|tree-ssa                    |3.5.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug optimization/14319] incorrect optimization of union of structs with common initial sequences

[rth at gcc dot gnu dot org]

------- Additional Comments From rth at gcc dot gnu dot org  2004-03-03 01:06 -------
... suspend it until we can figure out what the language is supposed to mean.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |SUSPENDED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug rtl-optimization/14319] incorrect optimization of union of structs with common initial sequences

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.5.0                       |---


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug rtl-optimization/14319] incorrect optimization of union of structs with common initial sequences

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |alias
   Last reconfirmed|2005-05-26 12:37:22         |2005-09-26 15:42:20
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug rtl-optimization/14319] incorrect optimization of union of structs with common initial sequences

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ghazi at gcc dot gnu.org

--- Comment #19 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 43495 has been marked as a duplicate of this bug. ***

[Bug rtl-optimization/14319] incorrect optimization of union of structs with common initial sequences

[jameskuyper at alumni dot caltech.edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

--- Comment #18 from James Kuyper Jr. <jameskuyper at alumni dot caltech.edu> ---
(In reply to Vincent Lefèvre from comment #17)
> (In reply to Tim Rentsch from comment #10)
> > Four:  Despite the last observation, the "one special guarantee" clause
> > (and hence also DR 257) is clearly not germane to this problem.  The
> > reason for this is that the "one special guarantee" clause is concerned
> > with read access ("inspect" is the word used in the Standard),
> [...]
> 
> In any case, the aliasing rule is only about read access: "An object shall
> have its stored value accessed only by [...]" (6.5#7). If you are accessing
> a stored value, this means that you are reading it. Thus the "yp->y = 1;"
> does not imply undefined behavior, in case this is what you were thinking
> about.

Agreed, the aliasing rule only produces undefined behavior for a read access,
not a write access. As Tim pointed out, when the "one special guarantee"
applies, it overrides the aliasing rules to give defined behavior for such a
read, and isn't relevant to the write. However, as I pointed out in comment 11
(and as was conceded by Tim in comment 13 and comment 14), the issue is not the
write access in

    yp->y = 1;

it's the read access in

    return xp->x;

The guarantee does apply to that read (though others have disagreed about
that), and therefore gives that read well-defined behavior, behavior that is
inconsistent with the actual behavior reported by Jeff Sturm.

[Bug rtl-optimization/14319] incorrect optimization of union of structs with common initial sequences

[vincent-gcc at vinc17 dot net]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

Vincent Lefèvre <vincent-gcc at vinc17 dot net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vincent-gcc at vinc17 dot net

--- Comment #17 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
(In reply to Tim Rentsch from comment #10)
> Four:  Despite the last observation, the "one special guarantee" clause
> (and hence also DR 257) is clearly not germane to this problem.  The
> reason for this is that the "one special guarantee" clause is concerned
> with read access ("inspect" is the word used in the Standard),
[...]

In any case, the aliasing rule is only about read access: "An object shall have
its stored value accessed only by [...]" (6.5#7). If you are accessing a stored
value, this means that you are reading it. Thus the "yp->y = 1;" does not imply
undefined behavior, in case this is what you were thinking about.

Note: Forbidding write accesses with a different effective type would make "for
subsequent accesses that do not modify the value" from 6.5#6 pointless.

[Bug rtl-optimization/14319] incorrect optimization of union of structs with common initial sequences

[fxcoudert at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fxcoudert at gcc dot gnu.org

--- Comment #16 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
There is a case in our testsuite that is exercising this check:
gcc.c-torture/execute/20000603-1.c

It was kept in the testsuite because "the exact DR resolution is
as yet unclear but it seems very likely that the modified version will be
considered OK" https://gcc.gnu.org/legacy-ml/gcc-patches/2004-02/msg00498.html

Either this is OK, and the bug should be reconfirmed/unsuspended. Or the test
case should be removed from the GCC testsuite.

[Bug rtl-optimization/14319] incorrect optimization of union of structs with common initial sequences

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |iains at gcc dot gnu.org

--- Comment #15 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 96875 has been marked as a duplicate of this bug. ***

[Bug rtl-optimization/14319] incorrect optimization of union of structs with common initial sequences

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |msebor at gcc dot gnu.org

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 65892 has been marked as a duplicate of this bug. ***

[Bug rtl-optimization/14319] incorrect optimization of union of structs with common initial sequences

[dvilleneuve at kronos dot com]

------- Comment #8 from dvilleneuve at kronos dot com  2009-12-19 14:41 -------
(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.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319

[Bug rtl-optimization/14319] incorrect optimization of union of structs with common initial sequences

[pinskia at gcc dot gnu dot org]

------- Comment #7 from pinskia at gcc dot gnu dot org  2009-12-19 03:45 -------
*** Bug 42432 has been marked as a duplicate of this bug. ***


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dvilleneuve at kronos dot
                   |                            |com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14319