llvm dev - Feb 2015 - [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.

-Ahmed

> Anyway, the help is much appreciated, thanks Chandler & Hal!
>>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150202/62439cb7/attachment.html>

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

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