> On Dec 10, 2015, at 8:09 AM, Daniel Berlin via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > > Opps, you are right in my example basicaaa could do it potentially. Correct example is slightly different: > int foo(struct S *ps, int i) { > ps->a[i] = 1; > ps->b = 2; > return ps->a[i]; > } > Here basicaa cannot make sure that 'ps->a[i]' doesn't change after 'ps->b = 2' because if 'i == 10' all 3 memory accesses will read/write the same memory. And type information about S::a is required to disambiguate. With current TBAA 'ps->a[i]' is about random 'int' read. > > Yes, and without more info, in LLVM that read can legally touch ps->b.I thought the inbounds on the GEPs would have told us that the a[] accesses and b access are both in bounds of their respective fields of the struct. Or does inbounds only tell us that the GEPs are in bounds of ‘ps’ itself?> So that makes sense. > > > Missing information here is the range inside struct S that could be accessed. > > What do you mean by "could be accessed". Do you mean "valid to access in C"? > > By access I meant read/write memory i.e. that size of S::a inside the struct or at least information that only S::a is accessed in this place i.e. not S::b. > > Okay. > > So what you want sounds reasonable to me ;-) > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20151210/efa9cfa8/attachment-0001.html>
Daniel Berlin via llvm-dev
2015-Dec-10 19:23 UTC
[llvm-dev] Field sensitive alias analysis?
The second. langref says: "The *in bounds* addresses for an allocated object are all the addresses that point into the object, plus the address one byte past the end. In cases where the base is a vector of pointers the inbounds keyword applies to each of the computations element-wise." Presumably, the allocated object here is ps, *not* the fields. Interestingly, the GEP faq says:"A common example of how this is used is arrays where the size is not known. It’s common to use array types with zero length to represent these. The fact that the static type says there are zero elements is irrelevant; it’s perfectly valid to compute arbitrary element indices, as the computation only depends on the size of the array element, not the number of elements. Note that zero-sized arrays are not a special case here. This sense is unconnected with inbounds keyword. The inbounds keyword is designed to describe low-level pointer arithmetic overflow conditions, rather than high-level array indexing rules." At least this leads me to believe you can't use the "llvm type" info much at all in conjunction with inbounds, only the size of allocas that you see. --Dan On Thu, Dec 10, 2015 at 11:00 AM, Pete Cooper <peter_cooper at apple.com> wrote:> > On Dec 10, 2015, at 8:09 AM, Daniel Berlin via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > > >>> Opps, you are right in my example basicaaa could do it potentially. >> Correct example is slightly different: >> int foo(struct S *ps, int i) { >> ps->a[i] = 1; >> ps->b = 2; >> return ps->a[i]; >> } >> Here basicaa cannot make sure that 'ps->a[i]' doesn't change after 'ps->b >> = 2' because if 'i == 10' all 3 memory accesses will read/write the same >> memory. And type information about S::a is required to disambiguate. With >> current TBAA 'ps->a[i]' is about random 'int' read. >> > > Yes, and without more info, in LLVM that read can legally touch ps->b. > > I thought the inbounds on the GEPs would have told us that the a[] > accesses and b access are both in bounds of their respective fields of the > struct. > > Or does inbounds only tell us that the GEPs are in bounds of ‘ps’ itself? > > So that makes sense. > > >> >> >>> Missing information here is the range inside struct S that could be >>>> accessed. >>>> >>> >>> What do you mean by "could be accessed". Do you mean "valid to access >>> in C"? >>> >> >> By access I meant read/write memory i.e. that size of S::a inside the >> struct or at least information that only S::a is accessed in this place >> i.e. not S::b. >> > > Okay. > > So what you want sounds reasonable to me ;-) > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20151210/37eb1229/attachment.html>
Philip Reames via llvm-dev
2015-Dec-10 22:44 UTC
[llvm-dev] Field sensitive alias analysis?
Danny's description matches my understanding of inbounds as well. In generally, the LLVM type (particular first class aggregates) has essentially no meaning. Our operations are typed, our operands generally are not. The only real exception to that is that we have a strong distinction between pointers (due to address spaces) and everything else. Philip On 12/10/2015 11:23 AM, Daniel Berlin via llvm-dev wrote:> The second. > > > langref says: > "The /in bounds/ addresses for an allocated object are all the > addresses that point into the object, plus the address one byte past > the end. In cases where the base is a vector of pointers the > inbounds keyword applies to each of the computations element-wise." > > Presumably, the allocated object here is ps, *not* the fields. > > > Interestingly, the GEP faq says:"A common example of how this is used > is arrays where the size is not known. It’s common to use array types > with zero length to represent these. The fact that the static type > says there are zero elements is irrelevant; it’s perfectly valid to > compute arbitrary element indices, as the computation only depends on > the size of the array element, not the number of elements. Note that > zero-sized arrays are not a special case here. This sense is > unconnected with inbounds keyword. The inbounds keyword is designed to > describe low-level pointer arithmetic overflow conditions, rather than > high-level array indexing rules." > > > At least this leads me to believe you can't use the "llvm type" info > much at all in conjunction with inbounds, only the size of allocas > that you see. > > --Dan > > > > On Thu, Dec 10, 2015 at 11:00 AM, Pete Cooper <peter_cooper at apple.com > <mailto:peter_cooper at apple.com>> wrote: > > >> On Dec 10, 2015, at 8:09 AM, Daniel Berlin via llvm-dev >> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: >> >> >> Opps, you are right in my example basicaaa could do it >> potentially. Correct example is slightly different: >> int foo(struct S *ps, int i) { >> ps->a[i] = 1; >> ps->b = 2; >> return ps->a[i]; >> } >> Here basicaa cannot make sure that 'ps->a[i]' doesn't change >> after 'ps->b = 2' because if 'i == 10' all 3 memory accesses >> will read/write the same memory. And type information about >> S::a is required to disambiguate. With current TBAA >> 'ps->a[i]' is about random 'int' read. >> >> >> Yes, and without more info, in LLVM that read can legally touch >> ps->b. > I thought the inbounds on the GEPs would have told us that the a[] > accesses and b access are both in bounds of their respective > fields of the struct. > > Or does inbounds only tell us that the GEPs are in bounds of ‘ps’ > itself? >> So that makes sense. >> >> Missing information here is the range inside struct S >> that could be accessed. >> >> >> What do you mean by "could be accessed". Do you mean >> "valid to access in C"? >> >> >> By access I meant read/write memory i.e. that size of S::a >> inside the struct or at least information that only S::a is >> accessed in this place i.e. not S::b. >> >> >> Okay. >> >> So what you want sounds reasonable to me ;-) >> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20151210/1499192b/attachment-0001.html>