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

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
- the access sizes are such that there is no overlap
- the struct index is the final one

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 couldn't come up with a counterexample that would prevent us from
doing this in BasicAA.
I was surprised it wasn't; surely I missed something?

Thanks!

-Ahmed
-------------- next part --------------
A non-text attachment was scrubbed...
Name: testcase.ll
Type: application/octet-stream
Size: 795 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150120/8101e8e4/attachment.obj>

Are you counting unions, or literally just structs?


On Tue Jan 20 2015 at 12:34:38 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
> - the access sizes are such that there is no overlap
> - the struct index is the final one
>
> 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 couldn't come up with a counterexample that would prevent us from
> doing this in BasicAA.
> I was surprised it wasn't; surely I missed something?
>
> Thanks!
>
> -Ahmed
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150120/5d5aabf9/attachment.html>

On Tue, Jan 20, 2015 at 12:57 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> Are you counting unions, or literally just structs?
Just structs.

-Ahmed
>
> On Tue Jan 20 2015 at 12:34:38 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
>> - the access sizes are such that there is no overlap
>> - the struct index is the final one
>>
>> 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 couldn't come up with a counterexample that would prevent us from
>> doing this in BasicAA.
>> I was surprised it wasn't; surely I missed something?
>>
>> Thanks!
>>
>> -Ahmed
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

----- Original Message -----
> From: "Ahmed Bougacha" <ahmed.bougacha at gmail.com>
> To: "LLVM Dev" <llvmdev at cs.uiuc.edu>
> Cc: "Hal Finkel" <hfinkel at anl.gov>
> Sent: Tuesday, January 20, 2015 2:27:43 PM
> Subject: Basic AliasAnalysis: Can GEPs with the same base but different
constant indices into a struct alias?
> 
> 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
> - the access sizes are such that there is no overlap
> - the struct index is the final one
> 
> 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 couldn't come up with a counterexample that would prevent us from
> doing this in BasicAA.
> I was surprised it wasn't; surely I missed something?
I don't think you're missing anything, and you're right. BasicAA is
essentially a collection of heuristics, it is quite possible that no one has
added this one yet.

 -Hal
> 
> Thanks!
> 
> -Ahmed
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

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>

----- Original Message -----
> From: "Chandler Carruth" <chandlerc at google.com>
> To: "Ahmed Bougacha" <ahmed.bougacha at gmail.com>
> Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu>
> Sent: Saturday, January 24, 2015 7:44:50 PM
> Subject: Re: [LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but
different constant indices into a struct
> alias?
> 
> 
> 
> 
> 
> 
> 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...
Indeed, I did not read this with sufficient care ;) -- If you have:

 gep i1, j1, k1, 0
 gep i1, j1, k1, 1

If this is a struct pointer:

 gep i1, j1, k1

then the first two should not alias. Allowing for arbitrary other indices,
however, you can't reach the same conclusion (as Chandler pointed out).

 -Hal
> 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.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

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>