On 3/11/13 1:17 PM, Daniel Berlin wrote:> On Mon, Mar 11, 2013 at 11:41 AM, Manman Ren <mren at apple.com> wrote: >> Based on discussions with John McCall >> >> We currently focus on field accesses of structs, more specifically, on fields that are scalars or structs. >> >> Fundamental rules from C11 >> -------------------------- >> An object shall have its stored value accessed only by an lvalue expression that has one of the following types: [footnote: The intent of this list is to specify those circumstances in which an object may or may not be aliased.] >> 1. a type compatible with the effective type of the object, >> 2. a qualified version of a type compatible with the effective type of the object, >> 3. a type that is the signed or unsigned type corresponding to the effective type of the object, >> 4. a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object, >> 5. 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 >> 6. a character type. >> >> Example >> ------- >> struct A { >> int x; >> int y; >> }; >> struct B { >> A a; >> int z; >> }; >> struct C { >> B b1; >> B b2; >> int *p; >> }; >> >> Type DAG: >> int <- A::x <- A >> int <- A::y <- A <- B::a <- B <- C::b1 <- C >> int <----------------- B::z <- B <- C::b2 <- C >> any pointer <--------------------- C::p <- C >> >> The type DAG has two types of TBAA nodes: >> 1> the existing scalar nodes >> 2> the struct nodes (this is different from the current tbaa.struct) >> A struct node has a unique name plus a list of pairs (field name, field type). >> For example, struct node for "C" should look like >> !4 = metadata !{"C", "C::b1", metadata !3, "C::b2", metadata !3, "C::p", metadata !2} >> where !3 is the struct node for "B", !2 is pointer type. >> >> Given a field access >> struct B *bp = ...; >> bp->a.x = 5; >> we annotate it as B::a.x. > In the case of multiple structures containing substructures, how are > you differentiating? > > IE given > > struct A { > struct B b; > } > struct C { > struct B b; > } > > How do you know the above struct B *bp =...; is B::b from C and not B::b from A?If I understand correct, the proposed graph is DAG, not tree, and it should be able to tackling the case where a type is included more than once. On the other hand, the info which is annotated to the memory access is kind of "immediate enclosing aggregate type", which should be unique.> > (I agree you can know in the case of direct aggregates, but I argue > you have no way to know in the case of pointer arguments without > interprocedural analysis) > It gets worse the more levels you have. > > ie if you add > struct B { > struct E e; > } > > and have struct E *e = ... > how do you know it's the B::e contained in struct C, or the B::e > contained in struct A? > > > Again, i agree you can do both scalar and direct aggregates, but not > aggregates and scalars through pointers. > >That is exactly the power of TBAA. If the both memory accesses are direct load/store, it dose not even need TBAA, check their base/offset/size is sufficient for disambiguation.
On Tue, Mar 12, 2013 at 3:44 PM, Shuxin Yang <shuxin.llvm at gmail.com> wrote:> > On 3/11/13 1:17 PM, Daniel Berlin wrote: >> >> On Mon, Mar 11, 2013 at 11:41 AM, Manman Ren <mren at apple.com> wrote: >>> >>> Based on discussions with John McCall >>> >>> We currently focus on field accesses of structs, more specifically, on >>> fields that are scalars or structs. >>> >>> Fundamental rules from C11 >>> -------------------------- >>> An object shall have its stored value accessed only by an lvalue >>> expression that has one of the following types: [footnote: The intent of >>> this list is to specify those circumstances in which an object may or may >>> not be aliased.] >>> 1. a type compatible with the effective type of the object, >>> 2. a qualified version of a type compatible with the effective type of >>> the object, >>> 3. a type that is the signed or unsigned type corresponding to the >>> effective type of the object, >>> 4. a type that is the signed or unsigned type corresponding to a >>> qualified version of the effective type of the object, >>> 5. 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 >>> 6. a character type. >>> >>> Example >>> ------- >>> struct A { >>> int x; >>> int y; >>> }; >>> struct B { >>> A a; >>> int z; >>> }; >>> struct C { >>> B b1; >>> B b2; >>> int *p; >>> }; >>> >>> Type DAG: >>> int <- A::x <- A >>> int <- A::y <- A <- B::a <- B <- C::b1 <- C >>> int <----------------- B::z <- B <- C::b2 <- C >>> any pointer <--------------------- C::p <- C >>> >>> The type DAG has two types of TBAA nodes: >>> 1> the existing scalar nodes >>> 2> the struct nodes (this is different from the current tbaa.struct) >>> A struct node has a unique name plus a list of pairs (field name, >>> field type). >>> For example, struct node for "C" should look like >>> !4 = metadata !{"C", "C::b1", metadata !3, "C::b2", metadata !3, >>> "C::p", metadata !2} >>> where !3 is the struct node for "B", !2 is pointer type. >>> >>> Given a field access >>> struct B *bp = ...; >>> bp->a.x = 5; >>> we annotate it as B::a.x. >> >> In the case of multiple structures containing substructures, how are >> you differentiating? >> >> IE given >> >> struct A { >> struct B b; >> } >> struct C { >> struct B b; >> } >> >> How do you know the above struct B *bp =...; is B::b from C and not B::b >> from A? > > If I understand correct, the proposed graph is DAG, not tree, and it should > be able to tackling the case > where a type is included more than once.This was not clear from the proposal, whether the type hierarchy is duplicated all the way down as necessary, or attempted-to-be-shared by having types with multiple parents.> > On the other hand, the info which is annotated to the memory access is kind > of "immediate enclosing aggregate type", > which should be unique. > > >> >> (I agree you can know in the case of direct aggregates, but I argue >> you have no way to know in the case of pointer arguments without >> interprocedural analysis) >> It gets worse the more levels you have. >> >> ie if you add >> struct B { >> struct E e; >> } >> >> and have struct E *e = ... >> how do you know it's the B::e contained in struct C, or the B::e >> contained in struct A? >> >> >> Again, i agree you can do both scalar and direct aggregates, but not >> aggregates and scalars through pointers. >> >> > That is exactly the power of TBAA.I understand quite a bit about TBAA :) My point was that his check will produce the wrong TBAA answer because it will have an incomplete path in his representation. He will declare no-alias, yet it it will be may-alias under the actual TBAA rules.> If the both memory accesses are direct > load/store, > it dose not even need TBAA, check their base/offset/size is sufficient for > disambiguation.False, in a lot of cases. For starters, roughly any union including aggregate, you will have overlaps that can be disambiguated using TBAA but not otherwise.
Maybe I were not clear in my previous mail, or maybe we are talking about different topics. My point was, if the pair of memory accesses are direct access, in most cases, the base/offset/size should be able to sufficient to figure out if they are alias or not. A tricky case would be subscripped variables, like a.b[i][j] vs a.c[m][n] where a.c and b.c are enclosed in a common union. If mem-dep test failure to figure out if there is dependence, in that case, TBAA might help. It seems what we discussing here is somewhat deviating the original topic:-)>> If the both memory accesses are direct >> load/store, >> it dose not even need TBAA, check their base/offset/size is sufficient for >> disambiguation. > False, in a lot of cases. For starters, roughly any union including > aggregate, you will have overlaps that can be disambiguated using TBAA > but not otherwise.