On Mar 12, 2013, at 8:22 AM, Krzysztof Parzyszek wrote:> What cases does this proposal solve that the current analyses don't? Do you have a motivating example?Given struct A { int x; int y; }; struct B { A a; int z; }; struct C { B b1; B b2; }; struct D { C c; }; with struct-access-path aware TBAA, C::b1.a.x does not alias with D::c.b2.a.x. without it, the 2 scalar accesses can alias since both have int type. Manman> > -Krzysztof > > -- > Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
Krzysztof Parzyszek
2013-Mar-13 02:21 UTC
[LLVMdev] PROPOSAL: struct-access-path aware TBAA
On 3/12/2013 12:13 PM, Manman Ren wrote: > > Given > struct A { > int x; > int y; > }; > struct B { > A a; > int z; > }; > struct C { > B b1; > B b2; > }; > struct D { > C c; > }; > > with struct-access-path aware TBAA, C::b1.a.x does not alias with D::c.b2.a.x. > without it, the 2 scalar accesses can alias since both have int type. I browsed the 2012 standard for a while and I didn't see anything that would make this illegal: char *p = malloc(enough_bytes); intptr_t x = reinterpret_cast<intptr_t>(p); x += offsetof(C, b2); D &vd = *reinterpret_cast<D*>(p); C &vc = *reinterpret_cast<C*>(x); vd.c.b2.a.x = 1; // ..accessing the same int t = vc.b1.a.x; // ..storage I don't think that the path through the type structure is really sufficient. -Krzysztof -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
On 03/12/2013 07:21 PM, Krzysztof Parzyszek wrote:> On 3/12/2013 12:13 PM, Manman Ren wrote: > > > > Given > > struct A { > > int x; > > int y; > > }; > > struct B { > > A a; > > int z; > > }; > > struct C { > > B b1; > > B b2; > > }; > > struct D { > > C c; > > }; > > > > with struct-access-path aware TBAA, C::b1.a.x does not alias with > D::c.b2.a.x. > > without it, the 2 scalar accesses can alias since both have int type. > > I browsed the 2012 standard for a while and I didn't see anything that > would make this illegal: > > char *p = malloc(enough_bytes); > intptr_t x = reinterpret_cast<intptr_t>(p); > x += offsetof(C, b2); > D &vd = *reinterpret_cast<D*>(p); > C &vc = *reinterpret_cast<C*>(x); > vd.c.b2.a.x = 1; // ..accessing the same > int t = vc.b1.a.x; // ..storage > > I don't think that the path through the type structure is really > sufficient. > > -Krzysztof >Not 100% sure your point here, but I think you are likely arguing TBAA is not sufficiently safe. True for this case. However, in this case, TBAA is not supposed to kick in to disambiguate these two access because the base/offset/size rule is supposed to give a definite answer if these two access *definitely* alias or *definitely* not alias. Note that, to make base/offset/size more effective, analyzer need to track the base along the UD chains as far as possible. In this case, the "bases" for the memory are "p", instead of &vd and &vc, respectively.
On Tue, Mar 12, 2013 at 7:21 PM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:> On 3/12/2013 12:13 PM, Manman Ren wrote: >> >> Given >> struct A { >> int x; >> int y; >> }; >> struct B { >> A a; >> int z; >> }; >> struct C { >> B b1; >> B b2; >> }; >> struct D { >> C c; >> }; >> >> with struct-access-path aware TBAA, C::b1.a.x does not alias with >> D::c.b2.a.x. >> without it, the 2 scalar accesses can alias since both have int type. > > I browsed the 2012 standard for a while and I didn't see anything that would > make this illegal: > > char *p = malloc(enough_bytes); > intptr_t x = reinterpret_cast<intptr_t>(p); > x += offsetof(C, b2); > D &vd = *reinterpret_cast<D*>(p); > C &vc = *reinterpret_cast<C*>(x); > vd.c.b2.a.x = 1; // ..accessing the same > int t = vc.b1.a.x; // ..storage > > I don't think that the path through the type structure is really sufficient.There are simpler examples of this kind for C++, because placement new can change the dynamic type of the object (I actually haven't looked to see if they changed this in 2012, but it was definitely legal in C++98): #include <new> struct Foo { long i; }; struct Bar { void *p; }; long foo(int n) { Foo *f = new Foo; f->i = 1; for (int i=0; i<n; ++i) { Bar *b = new (f) Bar; b->p = 0; f = new (f) Foo; f->i = i; } return f->i; } Both access to the same memory, both will end up with completely different access paths, both legal by TBAA rules, but access path alone will claim no-alias. (This is taken from http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29286)