[LLVMdev] PROPOSAL: struct-access-path aware TBAA

[Shuxin Yang]

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.