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

[Hal Finkel]

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