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

[Ahmed Bougacha]

So, I gave it a quick shot in http://reviews.llvm.org/D7453.  Opinions
welcome, thanks again for the help!

-Ahmed


On Mon, Feb 2, 2015 at 7:47 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
>> From: "Ahmed Bougacha" <ahmed.bougacha at gmail.com>
>> To: "Chandler Carruth" <chandlerc at google.com>
>> Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu>, "Hal Finkel" <hfinkel at anl.gov>
>> Sent: Monday, February 2, 2015 1:25:40 PM
>> Subject: Re: [LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but different constant indices into a struct
>> alias?
>>
>> On Mon, Feb 2, 2015 at 10:59 AM, Chandler Carruth <
>> chandlerc at google.com > wrote:
>>
>> On Mon, Feb 2, 2015 at 10:55 AM, Ahmed Bougacha <
>> ahmed.bougacha at gmail.com > wrote:
>>
>>
>>
>> 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.
>>
>>
>> I don't really know what you're proposing. However, note that I can
>> nest arrays inside of structs and wrap structs in arrays, so I think
>> I can essentially almost always arrange to have arrays which I can
>> overflow to produce aliasing offsets.
>>
>>
>> But that doesn't matter, no? If AA is looking at two GEPs indexing
>> into say [1 x {[0 x i32], i32}]:
>> - we can state that gep 0, 0, 0 and gep 0, 0, 1 don't alias
>> - even though gep 0, 0, 0, 1 and gep 0, 0, 1 can, since this is a
>> different query.
>>
>>
>> So if you have say [1 x {i32, i32}], you can safely say that gep 0,
>> i, 0 and gep 0, j, 1 can't alias.
>>
>>
>> Or maybe this is my core misunderstanding of the problem?
>>
>> What are you really trying to achieve here? Why is just modeling the
>> math not sufficient here?
>>
>> See the originally attached testcase, where the load seems redundant,
>> but we can't prove the two GEPs don't alias.
>>
>
> Your original test case is essentially this:
>
> %struct.RECT = type { float, float, float }
> define float @basicaa_struct_geps(%struct.RECT* %rect, i64 %i, i64 %j, float %x, float %y) {
> entry:
>   %p_dx = getelementptr inbounds %struct.RECT* %rect, i64 %i, i32 0
>   %p_dy = getelementptr inbounds %struct.RECT* %rect, i64 %j, i32 1
>   ...
> }
>
> and the question is, can we conclude that %p_dx does not alias with %p_dy? The answer should be yes, but concluding this relies on more than the fact that the trailing indices differ for accesses to a compatible structure type. The lack of aliasing also involves proving the lack of partial aliasing of the base structure pointers (we know that (getelementptr inbounds %struct.RECT* %rect, i64 %i) might be equal to (getelementptr inbounds %struct.RECT* %rect, i64 %j), or disjoint from it, but won't partially overlap it). It also relies on the fact that there is no potential indexing overlap between elements of the structure type (there are no arrays, only simple member types).
>
> So I think that we can enhance BasicAA to catch this case, but it won't be quite as general as you had originally proposed.
>
>  -Hal
>
>>
>> -Ahmed
>>
>>
>>
>>
>>
>>
>>
>>
>> Anyway, the help is much appreciated, thanks Chandler & Hal!
>>
>>
>>
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory