llvm dev - Feb 2013 - [LLVMdev] [PATCH] Vectorizing Global Structures - Take 2

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. 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. 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 ;)
> 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.
I am not sure what you mean by this. I believe you can give a correct answer
using TBAA DAGs (see farther below). 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

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] <- /

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"
  }

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130216/3684954e/attachment.html>

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

Hi Daniel,
> This leads me to suggest  not throwing this info in the TBAA tree, for
> three reasons:
> 1. It's not TBAA.
LLVM's tbaa metadata doesn't really have to have anything to do with
types: as
far as I know it's just a general way of attaching this-may[-not]-alias-that
info to memory operations.  TBAA is simply the main user.  That said, the tree
structure (as opposed to a DAG) limits things quite a lot.

Ciao, Duncan.
> 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
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>