[LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but different constant indices into a struct alias?

[Chandler Carruth]

On Tue, Jan 20, 2015 at 12:27 PM, Ahmed Bougacha <ahmed.bougacha at gmail.com>
wrote:

> Hi all,
>
> This is covered by (struct-path aware) TBAA, but BasicAA disagrees.
> See the attached testcase, where it prevents us from removing the
> redundant load.
> For arbitrary GEPs, we can't decide based on constant indices (because
> of e.g., &A[0][1] and &A[1][0], with *A a one-element array).  BasicAA
> has some logic to "try to distinguish something like &A[i][1] against
> &A[42][0]".  For the testcase, it works for instance when the struct
> has an even number of floats.
>
> However, I think we can safely say GEPs with different constant
> indices into a struct can't alias, at least when:
> - the GEP is inbounds
>

I'm afraid that this is irrelevant. The only property conferred by inbounds
is that none of the intermediate pointers fall outside the allocated
object. It has nothing to do with indexing past the bounds (in either
positive or negative directions) of an array element within a struct. See
http://llvm.org/docs/GetElementPtr.html#what-happens-if-an-array-index-is-out-of-bounds
and the immediately following entry.

- the access sizes are such that there is no overlap
>

I think this is what you have to prove, and once you do


> - the struct index is the final one
>

I think this stops mattering.


>
> That is, these can't alias:
>     gep i1, j1, k1, 0
>     gep i2, j2, k2, 1
> If this is a struct pointer:
>     gep i1, j1, k1
>

I don't think this holds in general... Consider the type which contains 4
i32 objects: { [1 x { i32, i32 }], [2 x { i32 }] }.

A) gep 0, 1, 1, 0 -> points at the 4th i32 object

and

B) gep 0, 0, 1, 1 -> points at the 4th i32 object

Unless I've missed the math somewhere, I think this works, and both gep 0,
1, 1 and gep 0, 0, 1 point at a struct.


In general, you can use an array element of the struct to do just about
anything. And I can wrap any struct in an another struct, prefix it by an
array, and then use that array to form GEPs that do crazy aliasing.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150124/06ce67b8/attachment.html>