[LLVMdev] [PATCH] Vectorizing Global Structures - Take 2

[Daniel Berlin]

On Sat, Feb 16, 2013 at 8:26 AM, Arnold Schwaighofer
<aschwaighofer at apple.com> wrote:
> Daniel,
>
> Indulge me one more mail and I will go away … (or I'll try to :)
>
> On Feb 15, 2013, at 6:38 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
>
> yes, it does, but this is somewhat irrelevant to C.
>
> The pointers will not be of type struct.a[x] *, they will be of type
> int (*[100])) or int * or whatever
>
>
> But using the type system, aliasing, and language rules you can say which
> types might alias to other types:
>
> A char*, void* , int*, and an int (*)[] pointer (and others) might alias
> with int (*structS::A)[100] in C (strict aliasing).
>
> foo(struct a f, int i, int y) {
>      f.A[i] =
>              = f.B[y]
> }
>
> I believe, you could emit more expressive tbaa tags than we currently do.
Yes, I understand now you mainly are talking about the struct field access case.

What you are adding are in effect, structure field tags, not TBAA tags.

f.A and f.B in the above are *not* new types (nor are struct S.A, or
struct S.b). They are an existing type that is instantiated in a
structure.
You are really trying to tag accesses with the structure fields they
belong to, and then prove *those structure fields* are not the same,
and thus that the access cannot overlap because you can prove they are
different structure field accesses.
Honestly, you should probably *not* use TBAA for this, but new
metadata, for reasons i'll explain in one second below.

> See below.
>  And this may improve things sufficiently to be worth it. By just
> looking at LLVM IR you cannot assume no-alias in the example above, but your
> language might allow assuming so.

Yes, this is true in the exact example above (IE without pointers)
We did this in GCC, actually.

I made it tag accesses of each structure field separately, and this
was introduced in 4.2.  Look at tree-ssa-structalias.c from back then.
You can ignore all the pointer analysis related parts there, we used
TBAA as well.

About a month later, 4.2.1 was released because the compile time
regression was so bad on some cases :)

We eventually went with tagging only fields belonging locally accessed
byte ranges of structs, or parts that had their address taken, as well
as limiting struct size, etc.

This leads me to suggest  not throwing this info in the TBAA tree, for
three reasons:
1. It's not TBAA.
2. You are probably eventually want  to store a bunch of info the rest
of TBAA does not care about :)
3. It gives the frontends freedom to say things about the field
accesses that relate to whether they can alias, but are not related to
the types.  For example, maybe all the values of X in f[X] are
guaranteed to be multiples of 4, and the frontend can prove that.
Stride info like this is not always/really related to the types



> And without changing the semantics of LLVM
> IR, or doing some global range analysis (which you might not be able to do),
> or inserting runtime checks, I don't see any way to conclude no-alias in the
> above example besides some TBAA.
>
> On Feb 15, 2013, at 6:27 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
>
> On Fri, Feb 15, 2013 at 12:49 AM, Arnold Schwaighofer
> <aschwaighofer at apple.com> wrote:
>>
>> On Feb 14, 2013, at 10:21 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
>>>
>>> What I meant by saying "understanding independent objects inside a
>>> structure" to is that just by looking at an llvm type say for example struct
>>> { int A[100]; int B[100]} you and seeing two gep accesses that index into
>>> the first and second field of the type you can not necessarily say that the
>>> access is not overlapping without fully evaluating the address computation:
>>
>>
>> Yes, you need to fully evaluate it, but that's not really related to TBAA
>> :)
>>
>>
>>
>> I was thinking of type trees that encoded fields giving more guarantees
>> than LLVM IR currently conveys. Admittedly, I have not though this through,
>> whether this could even remotely work for C.
>>
>> In LLVM IR:
>>
>> struct { int A[100]; int B[100]} S;
>>
>> ptr = gep S, 0, 0, x
>> ptr2 = gep S, 0, 1, y
>>
>> = load ptr, !tbaa !"structS::A"
>> = load ptr2, !tbaa !"structS::B"
>>
>> using this you could tell that ptr and ptr2 do not alias without knowing
>> about x and y.
>
>
>
> you've basically just pushed the problem off into the frontend :)
>
>
> Backend developers like to do this ;)

Don't I know it.

>
> Something needs to know to tag this with structS::A, and not something that
> combines structS::A and structS::B.
> For simple structure accesses (IE not through pointers), this is certainly
> possible.
>
>
> An int pointer load/store would have a TBAA tag of 'int *'  which in my TBAA
> DAG aliases with structS:A/B so we would give a safe answer (albeit possibly
> more conservative than necessary).
>
>   = *(int*)ptr  // = load ptr, !tbaa !"int *"
>
> For any pointer access, it's not possible without pointer analysis.r
>
>
> I am not sure what you mean by this. I believe you can give a correct answer
> using TBAA DAGs (see farther below).

Yes, I did not mean to imply you cannot give safe answers, only that
you cannot give ones that are useful to the aliaser for proving
no-alias.

My apologies for being imprecise.
>  However, I do understand that you will
> get a better / less conservative answer in many cases by doing pointer
> analysis.
>
>   int (*ptr)[100] = S.A;
>   int *ptr2 = ptr;
>   *ptr2 ; // points-to analysis can tell me that ptr2 points-to S.A but not
> S.B while TBAA would tell me they both may-alias ptr2
Yes.

> Note, that our current chained BasicAA and TBAA approach would also catch
> simple case like the one above without doing full scale global points-to
> analysis.
>
> IE a deference of an int (*[100]) could be an access to structS::A,
> structS::B, or some other random type.
>
> Note that your TBAA DAG below does not take this into account.
>
>
> Yes, indeed I forgot int (*)[]. I admit my DAG was not complete you would
> also have to have int (*[]), void*, char* - and I am sure I forgot some more
> (structB::int*, structB::char*, stuctA::structB::int*, etc) - pointing to
> structS::A.
>
> Say you have
>
>   *&S.A[0] = val;  // The front-end knows you have a structS::A access.
>   int *ptr2 = *ptr;   // The front knows that you have a int(*)[] access.
>
>
> The front-end would generate
>
>   store sa, val, !tbaa "int (*structS::A)[]"
>   ptr2 = load %ptr, !tbaa "int(*)[]"
>
> and if we use a more complete TBAA type DAG we could conclude that they
> may-alias because the TBAA DAG tells us:
>
>   int (*structS::A)[100] <-   int*, char*, void*, structS*, int(*)[], …?
>   int (*structS::B)[100] <- /

Yes.

>
> However, for the access below we could conclude that they don't alias
> (because structS::A cannot not point to structS::B and vice versa).
>
>   foo(struct a f, int i, int y) {
>      f.A[i] = ;         // store ptr2, !tbaa !"structS::A"
>              = f.B[y]; // load ptr,    !tbaa !"structS::B"
>   }

Yes, in these cases, and other direct structure accesses, I agree it would work.
As I mentioned, it is used  in GCC, but we don't "pollute" the TBAA
tree with it.

>
> More examples:
>
> struct N{
>     int a[9];
>     struct A {
>         int f[9];
>         int g[9];
>         int *ptr;
>     } ;
> }
>
> in this case an access using a &N.a[], &N.f[] pointer would not alias (point
> to each other in the TBAA DAG) but a N.ptr integer pointer would point to
> either in the DAG.
>
>>
>> In the case of pointer loops that iterate over your example type, it will
>> properly discover that it overruns into the next field, and properly mark it
>> as pointing-to that field as well.
>>
>>
>> So for the following example it will conservatively say arrayidx and
>> arrayidx2 alias?
>>
>> %struct.anon = type { [256 x i64], i64, [256 x i64] }
>>
>> define void @foo(i32 %x, i32 %y) {
>>   %arrayidx = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 0, i32
>> %x
>>   %0 = store i64* %arrayidx, align 8
>>   %arrayidx2 = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 2,
>> i32 %y
>>   %1 = store i64* %arrayidx2, align 8
>> }
>
>
>
> Yes, when converted to may-alias info, it will.
>
>
> Okay.
>
> When I hear fields I think types. When I think types, I assume that *it is
> assumed* (I made this mistake the first time I looked at BasicAA) that you
> can treat the type as a guarantee about certain properties including things
> like that you are not allowed to walk beyond array bounds which would imply
> that you can treat an access over type of structs/arrays like a path in a
> tree (I wondered why we don't do this the first time I looked at BasicAA -
> until I dug deeper).
>
> My first (wrong) intuition was the set of possible accessible locations in
> the following two geps is disjunct
>   = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 0, ...
>   = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 1, …
>
> Hence, my initial warning about "understanding independent objects inside a
> structure".
>
> I am seeing TBAA as a way to give me similar guarantees on top of the
> existing semantics of the IR.
>
>
>
> From what I read (it's been quite a while) t's actually not valid in
> C, but valid in LLVM IR.
> At least, as written.
>
> §6.5.2.1, paragraph 2:
>
> A postfix expression followed by an expression in square brackets []
> is a subscripted designation of an element of an array object. The
> definition of the subscript operator [] is that E1[E2] is identical to
> (*((E1)+(E2))). Because of the conversion rules that apply to the
> binary + operator, if E1 is an array object (equivalently, a pointer
> to the initial element of an array object) and E2 is an integer,
> E1[E2] designates the E2-th element of E1 (counting from zero).
>
> So it's going to be a pointer plus an address.
>
> §6.5.6, paragraph 8:
>
> When an expression that has integer type is added to or subtracted
> from a pointer, the result has the type of the pointer operand. If the
> pointer operand points to an element of an array object, and the array
> is large enough, the result points to an element offset from the
> original element such that the difference of the subscripts of the
> resulting and original array elements equals the integer expression.
> In other words, if the expression P points to the i-th element of an
> array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N
> (where N has the value n) point to, respectively, the i+n-th and
> i-n-th elements of the array object, provided they exist. Moreover, if
> the expression P points to the last element of an array object, the
> expression (P)+1 points one past the last element of the array object,
> and if the expression Q points one past the last element of an array
> object, the expression (Q)-1 points to the last element of the array
> object. If both the pointer operand and the result point to elements
> of the same array object, or one past the last element of the array
> object, the evaluation shall not produce an overflow; otherwise, the
> behavior is undefined. If the result points one past the last element
> of the array object, it shall not be used as the operand of a unary *
> operator that is evaluated.
>
>
> you fall into the "otherwise, the behavior is undefined".
>
> It would be explicitly valid to convert it to char *, and read it up
> to and through B, but not using the array access operator.
>
>
> Yes, I vaguely remember reading something like this just was not 100% sure
> anymore. Thanks for looking it up.
>
> IE char * foo = &<beginning struct containing A and B>
>
> <walk through A, get to B>
>
>
>
> Thanks,
> Arnold