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

[Hal Finkel]

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