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

[Ahmed Bougacha]

On Sat, Jan 24, 2015 at 5:44 PM, Chandler Carruth <chandlerc at google.com>
wrote:

>
> 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.
>

Ah yes, the structs are what make it messy.

How about the more useful constraint:
- the (identical) base must point to a (possibly multidimensional) array of
structs.

Then, the above holds, no?  No matter which path you take, you must point
to a one of the contiguous structs, and if the index is different then the
pointers can't alias.

Anyway, the help is much appreciated, thanks Chandler & Hal!

-Ahmed
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150202/795136cc/attachment.html>