Ahmed Bougacha
2015-Feb-02 18:55 UTC
[LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but different constant indices into a struct alias?
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>
Chandler Carruth
2015-Feb-02 18:59 UTC
[LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but different constant indices into a struct alias?
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. What are you really trying to achieve here? Why is just modeling the math not sufficient here?> > 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/38979253/attachment.html>
Ahmed Bougacha
2015-Feb-02 19:25 UTC
[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>