Ahmed Bougacha
2015-Jan-20 20:27 UTC
[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>
Daniel Berlin
2015-Jan-20 20:57 UTC
[LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but different constant indices into a struct alias?
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>
Ahmed Bougacha
2015-Jan-20 21:09 UTC
[LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but different constant indices into a struct alias?
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
Hal Finkel
2015-Jan-25 01:21 UTC
[LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but different constant indices into a struct alias?
----- 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
Chandler Carruth
2015-Jan-25 01:44 UTC
[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... 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>
Hal Finkel
2015-Jan-25 01:57 UTC
[LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but different constant indices into a struct alias?
----- 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
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>
Apparently Analagous Threads
- [LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but different constant indices into a struct alias?
- [LLVMdev] Basic AliasAnalysis: Can GEPs with the same base but different constant indices into a struct alias?
- [LLVMdev] [RFC] AArch64: Should we disable GlobalMerge?
- [LLVMdev] [RFC] AArch64: Should we disable GlobalMerge?
- [LLVMdev] Lifting ASM to IR