[PATCH] Fix for bug 21725: wrong results with union and strict-aliasing

Yes, I am looking into it. I have a version now where ‘most things’ work, but it seems that the tbaa information that clang produces is not expressive enough when the struct/union has array members. For example:

union U03 {
short mS[4];
int mI;
};

results in:

!5 = !{!“omnipotent char”, !6, i64 0}
!6 = !{!“Simple C/C++ TBAA”}
!7 = !{!8, !8, i64 0}
!8 = !{!“int”, !5, i64 0}
!9 = !{!10, !10, i64 0}
!10 = !{!“short”, !5, i64 0}
!40 = !{!41, !8, i64 0}
!41 = !{!"_ZTS3U03", !5, i64 0, !8, i64 0}

Note that In !41, we loose the information about the ‘short’ member.

A function like:

void test_u03b(union U03* a, union U03* b)
{
a->mS[0]=1;
b->mI=2;

// CHECK: Function: _Z9test_u03b{{.}}
//FIXME: CHECK: MayAlias: store i32 2, i32
%{{.}}, align 4, !tbaa !{{.}} <-> store i16 1, i16* %{{.}}, align 2, !tbaa !{{.}}
}

results in wrong information: an access to mS[0] results in a ‘short’ (!10) access. The access to mI results in ‘!40’.

Note that for the short ‘!10’ access, we loose the information about the associated union.

Because !41 refers to char ‘!5’ and int ‘8’, but not to short ‘!10’, we cannot detect that there might
be overlap between ‘!40’ and ‘!10’.

When we have two arrays of different type, the problem becomes even worse as we now have no
connection to the union any more from the two accesses…

One issue with getting array accesses right that I see, is that the ‘offset’ field can suddenly be variable.

Maybe a good enough (and correct) fallback that we should consider is to make such union accesses alias with everything… (omnipotent char) in stead of mapping it to the basic type.

Any thoughts ?

Jeroen Dobbelaere

In http://reviews.llvm.org/D8056#141899, @jeroen.dobbelaere wrote:

> Further investigation shows that
llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp is not ready to handle struct
types where multiple members have the same (0) offset. The clang fix only
makes sense once that issue is resolved.

Can you work on this? If not (or even if you can), can you file a bug
report with an example?

http://reviews.llvm.org/D8056

EMAIL PREFERENCES
  http://reviews.llvm.org/settings/panel/emailpreferences/

Yes, I am looking into it. I have a version now where 'most things' work,
but it seems that the tbaa information that clang produces is not
expressive enough when the struct/union has array members. For example:

union U03 {
  short mS[4];
  int mI;
};

results in:

!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = !{!8, !8, i64 0}
!8 = !{!"int", !5, i64 0}
!9 = !{!10, !10, i64 0}
!10 = !{!"short", !5, i64 0}
!40 = !{!41, !8, i64 0}
!41 = !{!"_ZTS3U03", !5, i64 0, !8, i64 0}

Note that In !41, we loose the information about the 'short' member.

I would start here :slight_smile:

You should make it produce info about all the members.

A function like:

void test_u03b(union U03* a, union U03* b)
{
  a->mS[0]=1;
  b->mI=2;

  // CHECK: Function: _Z9test_u03b{{.*}}
  //FIXME: CHECK: MayAlias: store i32 2, i32* %{{.*}}, align 4, !tbaa
!{{.*}} <-> store i16 1, i16* %{{.*}}, align 2, !tbaa !{{.*}}
}

results in wrong information: an access to mS[0] results in a 'short'
(!10) access. The access to mI results in '!40'.
Note that for the short '!10' access, we loose the information about the
associated union.

Because !41 refers to char '!5' and int '8', but not to short '!10', we
cannot detect that there might
be overlap between '!40' and '!10'.

RIght, but this is clearly a bug in the info above.

When we have two arrays of different type, the problem becomes even worse
as we now have no
connection to the union any more from the two accesses...

I went through this on the whiteboard with folks when they designed this,
and pointed this out - it's pretty easy to get into situations where you
have two random pieces of memory, and they were part of a union, and you
don't know this.

You can make them as easy or as hard as you like.

The answer I got was "we're fine with people having to make this explicit".

One issue with getting array accesses right that I see, is that the
'offset' field can suddenly be variable.

Not really. You can't say where it points, so the range would be
"everything" anyway.
You should just say it accesses the entire array (but not anything else).

Maybe a good enough (and correct) fallback that we should consider is to
make such _union_ accesses alias with everything... (omnipotent char) in
stead of mapping it to the basic type.

It is possible, with the sets we have, to get the aliasing right :slight_smile:
I know this because GCC does it.

This design is nearly identical to GCC's TBAA and subvariable design :slight_smile:

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Jeroen Dobbelaere" <jeroen.dobbelaere@gmail.com>
Cc: reviews+D8056+public+7b63cedb34d51bb1@reviews.llvm.org, "Hal
Finkel" <hfinkel@anl.gov>, cfe-commits@cs.uiuc.edu,
"cfe-dev@cs.uiuc.edu Developers" <cfe-dev@cs.uiuc.edu>
Sent: Tuesday, March 17, 2015 4:24:01 PM
Subject: Re: [PATCH] Fix for bug 21725: wrong results with union and
strict-aliasing

> > In http://reviews.llvm.org/D8056#141899 , @jeroen.dobbelaere
> > wrote:
>

> > > Further investigation shows that
> > > llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp is not ready to
> > > handle struct types where multiple members have the same (0)
> > > offset. The clang fix only makes sense once that issue is
> > > resolved.
>

> > Can you work on this? If not (or even if you can), can you file a
> > bug
> > report with an example?
>

> > http://reviews.llvm.org/D8056
>

> > EMAIL PREFERENCES
>

> > http://reviews.llvm.org/settings/panel/emailpreferences/
>

> Yes, I am looking into it. I have a version now where 'most things'
> work, but it seems that the tbaa information that clang produces is
> not expressive enough when the struct/union has array members. For
> example:

> union U03 {

> short mS[4];

> int mI;

> };

> results in:

> !5 = !{!"omnipotent char", !6, i64 0}

> !6 = !{!"Simple C/C++ TBAA"}

> !7 = !{!8, !8, i64 0}

> !8 = !{!"int", !5, i64 0}

> !9 = !{!10, !10, i64 0}

> !10 = !{!"short", !5, i64 0}

> !40 = !{!41, !8, i64 0}

> !41 = !{!"_ZTS3U03", !5, i64 0, !8, i64 0}

> Note that In !41, we loose the information about the 'short'
> member.

I would start here :slight_smile:

You should make it produce info about all the members.

I agree.

> A function like:

> void test_u03b(union U03* a, union U03* b)

> {

> a->mS[0]=1;

> b->mI=2;

> // CHECK: Function: _Z9test_u03b{{.*}}

> //FIXME: CHECK: MayAlias: store i32 2, i32* %{{.*}}, align 4, !tbaa
> !{{.*}} <-> store i16 1, i16* %{{.*}}, align 2, !tbaa !{{.*}}

> }

> results in wrong information: an access to mS[0] results in a
> 'short'
> (!10) access. The access to mI results in '!40'.

> Note that for the short '!10' access, we loose the information
> about
> the associated union.

> Because !41 refers to char '!5' and int '8', but not to short
> '!10',
> we cannot detect that there might

> be overlap between '!40' and '!10'.

RIght, but this is clearly a bug in the info above.

> When we have two arrays of different type, the problem becomes even
> worse as we now have no

> connection to the union any more from the two accesses...

I went through this on the whiteboard with folks when they designed
this, and pointed this out - it's pretty easy to get into situations
where you have two random pieces of memory, and they were part of a
union, and you don't know this.

You can make them as easy or as hard as you like.

The answer I got was "we're fine with people having to make this
explicit".

I don't understand what this means. How should they do that? The language has a defined set of semantics, and we need to follow them. At the very least, if we don't want to fully represent the TBAA hierarchy for some types (I'm not sure why we'd not do this, but...) then we should omit the metadata all together.

-Hal

------------------------------

*From: *"Daniel Berlin" <dberlin@dberlin.org>
*To: *"Jeroen Dobbelaere" <jeroen.dobbelaere@gmail.com>
*Cc: *reviews+D8056+public+7b63cedb34d51bb1@reviews.llvm.org, "Hal
Finkel" <hfinkel@anl.gov>, cfe-commits@cs.uiuc.edu, "cfe-dev@cs.uiuc.edu
Developers" <cfe-dev@cs.uiuc.edu>
*Sent: *Tuesday, March 17, 2015 4:24:01 PM
*Subject: *Re: [PATCH] Fix for bug 21725: wrong results with union and
strict-aliasing

In http://reviews.llvm.org/D8056#141899, @jeroen.dobbelaere wrote:

> Further investigation shows that
llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp is not ready to handle struct
types where multiple members have the same (0) offset. The clang fix only
makes sense once that issue is resolved.

Can you work on this? If not (or even if you can), can you file a bug
report with an example?

http://reviews.llvm.org/D8056

EMAIL PREFERENCES
  http://reviews.llvm.org/settings/panel/emailpreferences/

Yes, I am looking into it. I have a version now where 'most things' work,
but it seems that the tbaa information that clang produces is not
expressive enough when the struct/union has array members. For example:

union U03 {
  short mS[4];
  int mI;
};

results in:

!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = !{!8, !8, i64 0}
!8 = !{!"int", !5, i64 0}
!9 = !{!10, !10, i64 0}
!10 = !{!"short", !5, i64 0}
!40 = !{!41, !8, i64 0}
!41 = !{!"_ZTS3U03", !5, i64 0, !8, i64 0}

Note that In !41, we loose the information about the 'short' member.

I would start here :slight_smile:

You should make it produce info about all the members.

I agree.

A function like:

void test_u03b(union U03* a, union U03* b)
{
  a->mS[0]=1;
  b->mI=2;

  // CHECK: Function: _Z9test_u03b{{.*}}
  //FIXME: CHECK: MayAlias: store i32 2, i32* %{{.*}}, align 4, !tbaa
!{{.*}} <-> store i16 1, i16* %{{.*}}, align 2, !tbaa !{{.*}}
}

results in wrong information: an access to mS[0] results in a 'short'
(!10) access. The access to mI results in '!40'.
Note that for the short '!10' access, we loose the information about the
associated union.

Because !41 refers to char '!5' and int '8', but not to short '!10', we
cannot detect that there might
be overlap between '!40' and '!10'.

RIght, but this is clearly a bug in the info above.

When we have two arrays of different type, the problem becomes even worse
as we now have no
connection to the union any more from the two accesses...

I went through this on the whiteboard with folks when they designed this,
and pointed this out - it's pretty easy to get into situations where you
have two random pieces of memory, and they were part of a union, and you
don't know this.

You can make them as easy or as hard as you like.

The answer I got was "we're fine with people having to make this explicit".

I don't understand what this means. How should they do that?

So, his point was the arrays have no connections to the union. This is not
the only case this occurs in.

Let's take the canonical example:

For example

union foo {
int a;
float b;
};

int ihateunions(int *a, float *b)
{
<do a thing with a and b>
}

int passtounion()
{
union foo bar;
ihateunions(&bar.a, &bar.b);

}

Inside ihateunions, you will have no idea that a and b are connected to
unions.

Let's say this example is easy, i mean, they are both at offset 0, so they
can alias, right?

Add two different structs in the union, and pass pointers, we'll still
generate wrong struct-path tbaa for this, because it has no idea that it is
part of a union.
:slight_smile:
You can make this arbitrarily as complex or as simple as you want (put them
in different translation units, etc).

The language has a defined set of semantics, and we need to follow them.

What do you think should happen in the above? :slight_smile:
(Last time we went around this on the GCC mailing list, this spawned a very
long 30 message thread on the gcc mailing list, with the TL;DR being
"nobody really knows, but we're fine with telling people if they want
something sane here, they should make the union access in ihateunions
visible and explicit". DR reports were filed, no good answer was given :P)

At the very least, if we don't want to fully represent the TBAA hierarchy
for some types (I'm not sure why we'd not do this, but...) then we should
omit the metadata all together.

This part isn't about not fully representing, but not knowing what part of
the hierarchy you are really in.

Remember that TBAA struct path is not really TBAA info.
It's access path info.

My understanding is that if you access members of a union in this way, the
compiler is allowed
to assume that a and b do not alias.

If you access a member (or nested member) of a union, starting from the
union itself, then it depends if the other type is also accessible through
the union.

So:

int foo(union foo* a, float* b, int* c) {
  a->a=1;
  *b=2;
  // compiler must assume a->a and *b can alias
  // compiler must not assume *b and *c alias (access not through union)
}

(Also see section 3.10 of the c++03 standard; and
http://stackoverflow.com/questions/98650/what-is-the-strict-aliasing-rule )

Greetings,

Jeroen Dobbelaere

[..]

Note that In !41, we loose the information about the 'short' member.

I would start here :slight_smile:

You should make it produce info about all the members.

Sounds reasonable.

[..]

One issue with getting array accesses right that I see, is that the
'offset' field can suddenly be variable.

Not really. You can't say where it points, so the range would be
"everything" anyway.
You should just say it accesses the entire array (but not anything else).

In order to provide as detailed and accurate feedback as possible, my
current changes to the tbaa analysis
take the (location) access size into account. This is because the tbaa path
information itself does not
contain direct size information, only offsets.

Is there today already a way how such variable array access can be
described ? Is there a way to describe that we have an array of a certain
type/size in the tbaa struct ?
Just looking at containment of types gives some information and will in
certain cases fix incorrect behavior, but it will also result in
performance degradation (due to more 'MayAliases') if offsets can not be
taken into account in the way they are used today.

Greetings,

Jeroen Dobbelaere

[..]
I don't understand what this means. How should they do that?

So, his point was the arrays have no connections to the union. This is
not the only case this occurs in.

Let's take the canonical example:

For example

union foo {
int a;
float b;
};

int ihateunions(int *a, float *b)
{
<do a thing with a and b>
}

int passtounion()
{
union foo bar;
ihateunions(&bar.a, &bar.b);

}

Inside ihateunions, you will have no idea that a and b are connected to
unions.

Let's say this example is easy, i mean, they are both at offset 0, so
they can alias, right?

My understanding is that if you access members of a union in this way,
the compiler is allowed
to assume that a and b do not alias.

In theory, the last time i remember, you weren't allow to set one member of
a union and read another.
But uh, that's not real user code :slight_smile:

(and IIRC, it does not say anything real)

If you access a member (or nested member) of a union, starting from the
union itself, then it depends if the other type is also accessible through
the union.

So:

int foo(union foo* a, float* b, int* c) {
  a->a=1;
  *b=2;
  // compiler must assume a->a and *b can alias
  // compiler must not assume *b and *c alias (access not through union)
}

(Also see section 3.10 of the c++03 standard;

This, IMHO, does not say what you seem to think it does :slight_smile:

For C++03, 3.10 only includes the word "union" here: "If a program
attempts to access the stored value of an object through an lvalue of other
than one of the following types the behavior is undefined:

— the dynamic type of the object,
— a cv-qualified version of the dynamic type of the object,
— a type that is the signed or unsigned type corresponding to the dynamic
type of the object,
— a type that is the signed or unsigned type corresponding to a
cv-qualified version of the dynamic 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),
— a type that is a (possibly cv-qualified) base class type of the dynamic
type of the object,
— a char or unsigned char type."

C++ standard experts, at least on the GCC side, did not view this as saying
"all accesses must have an explicit union access", but that "It must be
part of a union type", but about whether you try to access it through a
union that doesn't have the right actual types in it.

The type of those objects is right the type of the object. There is, IMHO,
nothing illegal about those accesses.

and
http://stackoverflow.com/questions/98650/what-is-the-strict-aliasing-rule
)

Stackoverflow is not really a good resource for this type of question.

[..]

Note that In !41, we loose the information about the 'short' member.

I would start here :slight_smile:

You should make it produce info about all the members.

Sounds reasonable.

[..]

One issue with getting array accesses right that I see, is that the
'offset' field can suddenly be variable.

Not really. You can't say where it points, so the range would be
"everything" anyway.
You should just say it accesses the entire array (but not anything else).

In order to provide as detailed and accurate feedback as possible, my
current changes to the tbaa analysis
take the (location) access size into account. This is because the tbaa
path information itself does not
contain direct size information, only offsets.

Is there today already a way how such variable array access can be
described ?

You can't do this sanely without a lot of work, because it can overlap
multiple actual variables and structs.

The way we did this in GCC was to just dynamically evaluate which parts of
which structures it could access, and then combine all those types.

Is there a way to describe that we have an array of a certain type/size in
the tbaa struct ?

you can certainly describe it, but it would require metadata structure
changes.

Just looking at containment of types gives some information and will in

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Jeroen Dobbelaere" <jeroen.dobbelaere@gmail.com>
Cc: reviews+D8056+public+7b63cedb34d51bb1@reviews.llvm.org, "Hal
Finkel" <hfinkel@anl.gov>, cfe-commits@cs.uiuc.edu,
"cfe-dev@cs.uiuc.edu Developers" <cfe-dev@cs.uiuc.edu>
Sent: Tuesday, March 17, 2015 5:59:18 PM
Subject: Re: [PATCH] Fix for bug 21725: wrong results with union and
strict-aliasing

> > [..]
>

> > Note that In !41, we loose the information about the 'short'
> > member.
>

> > I would start here :slight_smile:
>

> > You should make it produce info about all the members.
>

> Sounds reasonable.

> > > [..]
> >
>

> > > One issue with getting array accesses right that I see, is that
> > > the
> > > 'offset' field can suddenly be variable.
> >
>

> > Not really. You can't say where it points, so the range would be
> > "everything" anyway.
>

> > You should just say it accesses the entire array (but not
> > anything
> > else).
>

> In order to provide as detailed and accurate feedback as possible,
> my
> current changes to the tbaa analysis

> take the (location) access size into account. This is because the
> tbaa path information itself does not

> contain direct size information, only offsets.

> Is there today already a way how such variable array access can be
> described ?

You can't do this sanely without a lot of work, because it can
overlap multiple actual variables and structs.

The way we did this in GCC was to just dynamically evaluate which
parts of which structures it could access, and then combine all
those types.

> Is there a way to describe that we have an array of a certain
> type/size in the tbaa struct ?

you can certainly describe it, but it would require metadata
structure changes.

FWIW, I'm not opposed to such changes. We might, however, want to design them in such a way that the explicit size information can be omitted when it can be inferred from the offsets (to reduce the size of the metadata in the common case).

-Hal

BTW, the example I gave is trivially transformable into one on structs:

struct foo {
int a;
float b;
};

int ihatestructs(int *a, float *b)
{
<do a thing with a and b>
}

int passtostruct()
{
struct foo bar;
ihatestructs(&bar.a, &bar.b);
}

Given 3.10 says literally nothing different about accesses through unions
and accesses through aggregates (they are even in the same sentence), i
don't see how you can reason your way to say that unions give a different
result than strucfts in the above case.

That is, strictly on a TBAA basis, i don't see how you believe the standard
allows different answers.
(Practically, i know why we are okay with them :P)

Now, TBAA combined with other info, i can see. This is because in the
above example, with TBAA you can say "TBAA says *a and *b in ihatestructs
can't alias unless they were accessed through an structure that contained
both". So far so good (though note, this alone gives you *nothing* about
the above unless you are guaranteed to have the whole program in front of
you). Struct rules tell us that a and b must not be at the same offset,
and memory layout rules tell us that objects at different offsets can not
alias. So, combined, we have "TBAA says *a and *b can't alias unless they
are a structure, and if they were in a structure, they can't alias because
they aren't at the same offset". These two things combined tell you *a and
*b can't alias.
But either one alone does not.

This is the problems with unions. You don't get the second part easily,
because they may in fact, be at the same offset.

[..]

In theory, the last time i remember, you weren't allow to set one member
of a union and read another.
But uh, that's not real user code :slight_smile:

(and IIRC, it does not say anything real)

This is indeed correct. The main issue is that llvm thinks it is allowed to
reorder 'stores' (as it thinks they are not aliasing),
so that a legal read afterwards will result in a wrong answer (if an
optimization or the backend reorders the stores based on the wrong aliasing
information).

If you access a member (or nested member) of a union, starting from the
union itself, then it depends if the other type is also accessible through
the union.

So:

int foo(union foo* a, float* b, int* c) {
  a->a=1;
  *b=2;
  // compiler must assume a->a and *b can alias
  // compiler must not assume *b and *c alias (access not through union)
}

(Also see section 3.10 of the c++03 standard;

This, IMHO, does not say what you seem to think it does :slight_smile:

For C++03, 3.10 only includes the word "union" here: "If a program
attempts to access the stored value of an object through an lvalue of other
than one of the following types the behavior is undefined:

— the dynamic type of the object,
— a cv-qualified version of the dynamic type of the object,
— a type that is the signed or unsigned type corresponding to the dynamic
type of the object,
— a type that is the signed or unsigned type corresponding to a
cv-qualified version of the dynamic 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),
— a type that is a (possibly cv-qualified) base class type of the dynamic
type of the object,
— a char or unsigned char type."

C++ standard experts, at least on the GCC side, did not view this as
saying "all accesses must have an explicit union access", but that "It must
be part of a union type", but about whether you try to access it through a
union that doesn't have the right actual types in it.

The type of those objects is right the type of the object. There is, IMHO,
nothing illegal about those accesses.

So, with that interpretation, the mere presence of a 'union { short s; int
i; }' (in the same or a different compilation unit) should influence the
(type based) aliasing of all short and int pointers ?
This doesn't look a practical solution to me :frowning:
That's why I settled on the need of having the full access path available
as a practical solution (and one that can easily be explained)..

(btw. Do you have a pointer to the discussion on the gcc side ?)

What we currently have is definitely wrong. Question is how we want to fix
it...

Greetings,

Jeroen Dobbelaere

[..]

In theory, the last time i remember, you weren't allow to set one member
of a union and read another.
But uh, that's not real user code :slight_smile:

(and IIRC, it does not say anything real)

This is indeed correct. The main issue is that llvm thinks it is allowed
to reorder 'stores' (as it thinks they are not aliasing),
so that a legal read afterwards will result in a wrong answer (if an
optimization or the backend reorders the stores based on the wrong aliasing
information).

I thought both LLVM and GCC guaranteed type punning through unions would
work?

If you access a member (or nested member) of a union, starting from the
union itself, then it depends if the other type is also accessible through
the union.

So:

int foo(union foo* a, float* b, int* c) {
  a->a=1;
  *b=2;
  // compiler must assume a->a and *b can alias
  // compiler must not assume *b and *c alias (access not through union)
}

(Also see section 3.10 of the c++03 standard;

This, IMHO, does not say what you seem to think it does :slight_smile:

For C++03, 3.10 only includes the word "union" here: "If a program
attempts to access the stored value of an object through an lvalue of other
than one of the following types the behavior is undefined:

— the dynamic type of the object,
— a cv-qualified version of the dynamic type of the object,
— a type that is the signed or unsigned type corresponding to the dynamic
type of the object,
— a type that is the signed or unsigned type corresponding to a
cv-qualified version of the dynamic 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),
— a type that is a (possibly cv-qualified) base class type of the
dynamic type of the object,
— a char or unsigned char type."

C++ standard experts, at least on the GCC side, did not view this as
saying "all accesses must have an explicit union access", but that "It must
be part of a union type", but about whether you try to access it through a
union that doesn't have the right actual types in it.

The type of those objects is right the type of the object. There is,
IMHO, nothing illegal about those accesses.

So, with that interpretation, the mere presence of a 'union { short s; int
i; }' (in the same or a different compilation unit) should influence the
(type based) aliasing of all short and int pointers ?

It's actually worse than this interpretation, since someone pointed out on
the gcc side that "ihateunions" could be in a different TU, and you'd never
see the union at all.
While I think this is the right interpretation (as do others), that's not
the point.
I'm actually on your side here :slight_smile:

But remember that Hal said that if hte language has semantics, we should
follow them.

The whole point of this is essentially to point out that the language
semantics weren't completely thought out here :slight_smile:
Because of that, our options are either "make up a rule people can follow"
or "disable TBAA".

GCC, and every other compiler i'm aware of, has chosen the former, at least
for C++03 (I don't know what C++11 or 14 say here).

This doesn't look a practical solution to me :frowning:

That's why I settled on the need of having the full access path available
as a practical solution (and one that can easily be explained)..

(btw. Do you have a pointer to the discussion on the gcc side ?)

It's about 7-8 years old at this point. Let me see if i can find it

What we currently have is definitely wrong. Question is how we want to fix
it...

So, we have multiple wrongs here.

The first is that the short doesn't appear in the union info. Given that
it's a member of the union, it definitely should appear in the info for
that union.

I'd start there, and see how far that gets us :slight_smile:

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Jeroen Dobbelaere" <jeroen.dobbelaere@gmail.com>
Cc: "Hal Finkel" <hfinkel@anl.gov>,
reviews+D8056+public+7b63cedb34d51bb1@reviews.llvm.org,
cfe-commits@cs.uiuc.edu, "cfe-dev@cs.uiuc.edu Developers"
<cfe-dev@cs.uiuc.edu>
Sent: Wednesday, March 18, 2015 10:27:28 AM
Subject: Re: [PATCH] Fix for bug 21725: wrong results with union and
strict-aliasing

> > [..]
>

> > In theory, the last time i remember, you weren't allow to set one
> > member of a union and read another.
>

> > But uh, that's not real user code :slight_smile:
>

> > (and IIRC, it does not say anything real)
>

> This is indeed correct. The main issue is that llvm thinks it is
> allowed to reorder 'stores' (as it thinks they are not aliasing),

> so that a legal read afterwards will result in a wrong answer (if
> an
> optimization or the backend reorders the stores based on the wrong
> aliasing information).

I thought both LLVM and GCC guaranteed type punning through unions
would work?

Yes, LLVM does this (at least for "local" type punning, for some heuristic definition of local), because we always allow BasicAA to override TBAA when BasicAA is *sure* there is aliasing.

> > > If you access a member (or nested member) of a union, starting
> > > from
> > > the union itself, then it depends if the other type is also
> > > accessible through the union.
> >
>

> > > So:
> >
>

> > > int foo(union foo* a, float* b, int* c) {
> >
>

> > > a->a=1;
> >
>

> > > *b=2;
> >
>

> > > // compiler must assume a->a and *b can alias
> >
>

> > > // compiler must not assume *b and *c alias (access not through
> > > union)
> >
>

> > > }
> >
>

> > > (Also see section 3.10 of the c++03 standard;
> >
>

> > This, IMHO, does not say what you seem to think it does :slight_smile:
>

> > For C++03, 3.10 only includes the word "union" here: "If a
> > program
> > attempts to access the stored value of an object through an
> > lvalue
> > of other than one of the following types the behavior is
> > undefined:
>

> > — the dynamic type of the object,
>

> > — a cv-qualified version of the dynamic type of the object,
>

> > — a type that is the signed or unsigned type corresponding to the
> > dynamic type of the object,
>

> > — a type that is the signed or unsigned type corresponding to a
> > cv-qualified version of the dynamic 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),
>

> > — a type that is a (possibly cv-qualified) base class type of the
> > dynamic type of the object,
>

> > — a char or unsigned char type."
>

> > C++ standard experts, at least on the GCC side, did not view this
> > as
> > saying "all accesses must have an explicit union access", but
> > that
> > "It must be part of a union type", but about whether you try to
> > access it through a union that doesn't have the right actual
> > types
> > in it.
>

> > The type of those objects is right the type of the object. There
> > is,
> > IMHO, nothing illegal about those accesses.
>

> So, with that interpretation, the mere presence of a 'union { short
> s; int i; }' (in the same or a different compilation unit) should
> influence the (type based) aliasing of all short and int pointers ?

It's actually worse than this interpretation, since someone pointed
out on the gcc side that "ihateunions" could be in a different TU,
and you'd never see the union at all.

While I think this is the right interpretation (as do others), that's
not the point.
I'm actually on your side here :slight_smile:

But remember that Hal said that if hte language has semantics, we
should follow them.

I did. It is also true that standards have defects :wink: If a strict reading of the language semantics implies a 'spooky action at a distance' effect, then we'll need to draw a line in the sand somewhere to avoid that. I also think your interpretation that implies that is incorrect...

The whole point of this is essentially to point out that the language
semantics weren't completely thought out here :slight_smile:
Because of that, our options are either "make up a rule people can
follow" or "disable TBAA".

GCC, and every other compiler i'm aware of, has chosen the former, at
least for C++03 (I don't know what C++11 or 14 say here).

Yes; fair enough. What I want is that if we make up a rule, then we make that rule well defined and documented (not just whatever the implementation happens to do today); and we should also write a paper for the C++ Standards Committee proposing that as an official solution (I'll be happy to present at the next meeting, and we have approximately 1 month before the next paper deadline, IIRC).

In the current draft, I relevant wording looks equivalent:

— an aggregate or union type that includes one of the aforementioned types among its elements
or non-static data members (including, recursively, an element or non-static data member of
a subaggregate or contained union),

However, another point to consider is that, " C++ standard experts, at least on the GCC side, did not view this as saying "all accesses must have an explicit union access", but that..." may not be a reasonable reading of the standard. The text says, "If a program attempts to access the stored value of an object through a glvalue of other than one
of the following types the behavior is undefined: ...", and so I read that as saying that the access must be through a glvalue of an aggregate or union type (with a relevant type as one of its members). So the union or aggregate type *must* be explicitly present in the access. I don't believe any other interpretations, especially those which imply non-local effects, are reasonable.

Exactly what rule did GCC implement?

Thanks again,
Hal

------------------------------

*From: *"Daniel Berlin" <dberlin@dberlin.org>
*To: *"Jeroen Dobbelaere" <jeroen.dobbelaere@gmail.com>
*Cc: *"Hal Finkel" <hfinkel@anl.gov>,
reviews+D8056+public+7b63cedb34d51bb1@reviews.llvm.org,
cfe-commits@cs.uiuc.edu, "cfe-dev@cs.uiuc.edu Developers" <
cfe-dev@cs.uiuc.edu>
*Sent: *Wednesday, March 18, 2015 10:27:28 AM
*Subject: *Re: [PATCH] Fix for bug 21725: wrong results with union and
strict-aliasing

[..]

In theory, the last time i remember, you weren't allow to set one member
of a union and read another.
But uh, that's not real user code :slight_smile:

(and IIRC, it does not say anything real)

This is indeed correct. The main issue is that llvm thinks it is allowed
to reorder 'stores' (as it thinks they are not aliasing),
so that a legal read afterwards will result in a wrong answer (if an
optimization or the backend reorders the stores based on the wrong aliasing
information).

I thought both LLVM and GCC guaranteed type punning through unions would
work?

Yes, LLVM does this (at least for "local" type punning, for some heuristic
definition of local), because we always allow BasicAA to override TBAA when
BasicAA is *sure* there is aliasing.

If you access a member (or nested member) of a union, starting from the
union itself, then it depends if the other type is also accessible through
the union.

So:

int foo(union foo* a, float* b, int* c) {
  a->a=1;
  *b=2;
  // compiler must assume a->a and *b can alias
  // compiler must not assume *b and *c alias (access not through union)
}

(Also see section 3.10 of the c++03 standard;

This, IMHO, does not say what you seem to think it does :slight_smile:

For C++03, 3.10 only includes the word "union" here: "If a program
attempts to access the stored value of an object through an lvalue of other
than one of the following types the behavior is undefined:

— the dynamic type of the object,
— a cv-qualified version of the dynamic type of the object,
— a type that is the signed or unsigned type corresponding to the
dynamic type of the object,
— a type that is the signed or unsigned type corresponding to a
cv-qualified version of the dynamic 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),
— a type that is a (possibly cv-qualified) base class type of the
dynamic type of the object,
— a char or unsigned char type."

C++ standard experts, at least on the GCC side, did not view this as
saying "all accesses must have an explicit union access", but that "It must
be part of a union type", but about whether you try to access it through a
union that doesn't have the right actual types in it.

The type of those objects is right the type of the object. There is,
IMHO, nothing illegal about those accesses.

So, with that interpretation, the mere presence of a 'union { short s;
int i; }' (in the same or a different compilation unit) should influence
the (type based) aliasing of all short and int pointers ?

It's actually worse than this interpretation, since someone pointed out on
the gcc side that "ihateunions" could be in a different TU, and you'd never
see the union at all.
While I think this is the right interpretation (as do others), that's not
the point.
I'm actually on your side here :slight_smile:

But remember that Hal said that if hte language has semantics, we should
follow them.

I did. It is also true that standards have defects :wink: If a strict reading
of the language semantics implies a 'spooky action at a distance' effect,
then we'll need to draw a line in the sand somewhere to avoid that. I also
think your interpretation that implies that is incorrect...

The whole point of this is essentially to point out that the language
semantics weren't completely thought out here :slight_smile:
Because of that, our options are either "make up a rule people can follow"
or "disable TBAA".

GCC, and every other compiler i'm aware of, has chosen the former, at
least for C++03 (I don't know what C++11 or 14 say here).

Yes; fair enough. What I want is that if we make up a rule, then we make
that rule well defined and documented (not just whatever the implementation
happens to do today); and we should also write a paper for the C++
Standards Committee proposing that as an official solution (I'll be happy
to present at the next meeting, and we have approximately 1 month before
the next paper deadline, IIRC).

In the current draft, I relevant wording looks equivalent:

— an aggregate or union type that includes one of the aforementioned types
among its elements
    or non-static data members (including, recursively, an element or
non-static data member of
    a subaggregate or contained union),

However, another point to consider is that, "C++ standard experts, at
least on the GCC side, did not view this as saying "all accesses must have
an explicit union access", but that..." may not be a reasonable reading of
the standard. The text says, "If a program attempts to access the stored
value of an object through a glvalue of other than one
of the following types the behavior is undefined: ...", and so I read that
as saying that the access must be through a glvalue of an aggregate or
union type (with a relevant type as one of its members). So the union or
aggregate type *must* be explicitly present in the access. I don't believe
any other interpretations, especially those which imply non-local effects,
are reasonable.

I agree with this (and this is also what I am aiming for :wink: ). It would be
good if the standard (as a clarification), contained some examples
explaining when reordering is allowed and when not...

Greetings,

Jeroen

Exactly what rule did GCC implement?

Thanks again,
Hal

[..]

That's not what this wording literally says (nor, I think, what it
intends). The quoted text is specifically talking about the type of the
lvalue used to perform the access. In C++, this is almost never a struct or
union type; the only case where that can happen is when copying the object
representation of a union in a case like this:

  union A { int i; short s; };
  A a;
  A f() { return a; } // here, we copy the representation of 'a' through an
lvalue of type 'A'.

(In C, where largely the same wording appears, this bullet is relevant in
more cases, since copies of structs in C are performed directly by copying
the object and not via a copy constructor.)

In a case like 'ihateunions', the expression '*a = 0;' would use an lvalue
of type 'int' and the expression 'x = *b;' would use an lvalue of type
'float', so those two accesses are known to not access the same object by
3.10, irrespective of what aggregate or union types exist elsewhere in the
program. Also note that C++ does not specify any way to change the active
member of a union other than via a placement new-expression (and even that
mechanism is only implied to work, never normatively stated) so these
assignments presumably do not change the active member, and thus at least
one of them must have undefined behavior (unlike C, C++ does not imbue
storage with an effective type that can change through such an assignment;
instead, it has objects whose lifetimes are started through declarations,
when temporaries are created, and through new-expressions). As a sane
implementation, we absolutely should guarantee that accessing a union
member of primitive type and then immediately assigning to the result of
that member access expression does change the active member, but we are not
required to guarantee the same happens when the access is laundered through
a function, according to the current C++ standard's wording, and attempting
to provide such a guarantee seems largely pointless.

If you use an explicit union access, it assumes they alias, otherwise, all
bets are off.

Note: As you all know, I have really no dog in this fight, nor am i a
language lawyer. Among other things, i'm an aliasing guy. I just do the
edge of what the language lawyers tell me is allowed :slight_smile:

FWIW: I'm perfectly fine with this, as it lets me optimize more.
:slight_smile:

I propose that we implement the same behavior in llvm.
I'm quite busy right now, but I'll try to come up with some examples later
today for which we can then annotate what kind of behavior the standard
would allow (using Richards interpretation), what gcc is doing, what we
want to do.

Greetings,

Jeroen Dobbelaere

In the next set of small functions, the goal is to identify the (for llvm) wanted behavior related to aliasing.
(having a 32bit architecture in mind)

For every function, I have three fields:

  • c++11 : my interpretation of the c++11/14 standard based on a previous mail from Richard Smith
    (This is: a combination of the known layout of a structure/union/array and the types)
    (the relevant section for the types is 3.10 10)
  • llvm: what does llvm deduce today
  • future: what I would like to see in future

The question to ask is: when should it be valid to REORDER the stores, in the assumption
that after the function call, the second object is accessed (read from) in a legal way.

  • NoAlias: we are allowed to reorder the stores
  • MayAlias: we are not allowed to reorder the stores

For the ‘future’ field, my personal guideline is that:

  • if a union (sub)member is accessed (full path) and the union (or one of its members) contains a type that matches
    the other access (taking into account the access path), then aliasing must be assumed (possibly taken into account
    the offset/size of the access)

NOTE: when the standard requires a MayAlias, and we provide a NoAlias, we a have ‘wrong code’ issue
when the standard specifies a NoAlias, and we provide a MayAlias, we have a possible performance degradation.
NOTE2: for member array accesses of the same type, llvm will today always assume them as aliasing,
even if the happen at different offsets. This is acceptable as it does not result in wrong code.
NOTE3: depending on the interpretation of the standard, more or less cases will have the ‘MayAlias’ label. I try
to come with a guess on what the standard means, based on a previous mail from Richard Smith.
(Richard, please comment for those cases where I made a wrong guess :wink: )
NOTE4: it would be good if the standard can be extended with a set of examples, explicitly stating where reorderings
are allowed and where not.
NOTE5: we probably want to have a similar behavior as ‘gcc’, and we assume that gcc follows the ‘future’ rules, but
I was not able to deduce any useful information with ‘-fdump-tree-alias’. Probably I missed something :frowning:
I would be glad if somebody could extend this with information on how gcc treats the accesses.
NOTE6: In order to make unions really useful, llvm allows to read a union member with a different type than the one
that was used to write it. Once we have a correct deduction of the aliasing relation, this should also work.

So, please comment if you agree/disagree :wink:

Jeroen

In the next set of small functions, the goal is to identify the (for llvm)
wanted behavior related to aliasing.
(having a 32bit architecture in mind)

For every function, I have three fields:
- c++11 : my interpretation of the c++11/14 standard based on a previous
mail from Richard Smith
     (This is: a combination of the known layout of a
structure/union/array and the types)
     (the relevant section for the types is 3.10 10)
- llvm: what does llvm deduce today
- future: what I would like to see in future

The question to ask is: when should it be valid to REORDER the stores, in
the assumption
that after the function call, the second object is accessed (read from) in
a legal way.
- NoAlias: we are allowed to reorder the stores
- MayAlias: we are _not_ allowed to reorder the stores

For the 'future' field, my personal guideline is that:
- if a union (sub)member is accessed (full path) and the union (or one of
its members) contains a type that matches
  the other access (taking into account the access path), then aliasing
must be assumed (possibly taken into account
  the offset/size of the access)

NOTE: when the standard requires a MayAlias, and we provide a NoAlias, we
a have 'wrong code' issue
       when the standard specifies a NoAlias, and we provide a MayAlias,
we have a possible performance degradation.
NOTE2: for member array accesses of the same type, llvm will today always
assume them as aliasing,
       even if the happen at different offsets. This is acceptable as it
does not result in wrong code.
NOTE3: depending on the interpretation of the standard, more or less cases
will have the 'MayAlias' label. I try
       to come with a guess on what the standard means, based on a
previous mail from Richard Smith.
       (Richard, please comment for those cases where I made a wrong guess
:wink: )
NOTE4: it would be good if the standard can be extended with a set of
examples, explicitly stating where reorderings
        are allowed and where not.
NOTE5: we probably want to have a similar behavior as 'gcc', and we assume
that gcc follows the 'future' rules, but
       I was not able to deduce any useful information with
'-fdump-tree-alias'. Probably I missed something :frowning:

-alias is the dump for field-sensitive points-to, not "all alias info".
These are all incoming arguments, so non-IPA points-to will tell you
nothing.

But it does, of course, know things are in different places in each one:
for test3_s03c, for example, it computes:

a = &NONLOCAL
b = &NONLOCAL
derefaddrtmp = &NONLOCAL
*a + 64 = derefaddrtmp
*b + 160 = derefaddrtmp

a(D), points-to non-local, points-to vars: { }
b(D), points-to non-local, points-to vars: { }

IE they point to nothing locally, but may point to any non-local variable.

That is the best answer you can give these cases.

       I would be glad if somebody could extend this with information on

how gcc treats the accesses.

This would be complicated.
GCC builds a simple initial memory SSA form, but isn't going to
disambiguate it until an optimization asks for it to be disambiguated.

Since there is nothing to optimize in your cases, i can't tell you whether
it thinks they alias easily.
I did take the one case you have below, and added a load, to determine
aliasing.

NOTE6: In order to make unions really useful, llvm allows to read a union

member with a different type than the one
       that was used to write it. Once we have a correct deduction of the
aliasing relation, this should also work.

So, please comment if you agree/disagree :wink:

Jeroen

--

void test_s03c(struct S03* a, struct S03* b)
{
  a->mS00_1[0].mI_2=1;
  b->mS00_1[1].mI_2=2;

  // c++11: NoAlias
  // llvm: MayAlias ******** performance
  // future: NoAlias
}

I actually don't understand why we get this wrong now :slight_smile:
This should be pretty trivial offset calculation.

I transformed this into:
int test_s03c(struct S03* a, struct S03* b)
{
  a->mS00_1[0].mI_2=1;
  b->mS00_1[1].mI_2=2;
  return a->mS00_1[0].mI_2;
}

To see if GCC believes the second store clobbers the first store (IE
whether it thinks they alias).
It does not believe that, and will replace the return statement with
"return 1";

So GCC correctly determines "NoAlias" in this case.

We definitely do not.

GVN says:
GVN: load i32 %7 is clobbered by store i32 2, i32* %6, align 4

and does *not* replace the return value with 1.

We should fix this.

BasicAA, sadly, has to walk backwards because it is stateless.
It would be easier to walk forwards once, compute the actual offsets being
accessed by the GEPs, and map that to the loads/stores for later usage.
Then it is a constant time check for struct related aliasing like this.
This isn't going to get invalidated all that often (only things like load
widening/etc would change the offsets)

Anyway, i looked into BasicAA, and it fails in aliasGeps.

The logic in there confuses the heck out of me.

It seems to go to a lot of trouble, and steadfastly refuses to believe that
if you have two pointers whose underlying object is a struct argument, and
which are accessed using GEP's at provably different offsets, they can't
alias.
This is wrong.

In the case of arguments (or identified function locals) that are struct
types, it doesn't matter whether the underlying pointers are must or may
alias, it matters what the offset,size of the access is.

In particular, there should be an else branch after this block:

      if (PreciseBaseAlias == NoAlias) {

that says "if they [offsets, sizes] don't overlap different, and
UnderlyingV1/V2 is an identified local, they can't alias)

(if it can't figure out what the underlying object is, conservatively, the
right thing to do is say MayAlias)

I'll play with adding some logic here that does the right thing.

The of your answers rest looks sane to me.