On Mar 26, 2007, at 10:10 AM, Dan Gohman wrote:> On Mon, Mar 26, 2007 at 02:14:56AM -0500, Christopher Lamb wrote: >> >> >> On Mar 25, 2007, at 5:22 PM, Chris Lattner wrote: >> >>> On Sun, 25 Mar 2007, Christopher Lamb wrote: >>>> What about an approach not unlike how debugging information is >>>> handled? That >>>> is have an llvm intrinsic that encodes the known alias free range >>>> for a >>>> pointer. >>> >>> That is another great possibility. One issue is that I haven't had >>> time >>> to study the implications of C99 restrict, so I don't feel >>> qualified to >>> propose a concrete solution yet. Ideally, the mechanism added to >>> LLVM >>> would be able to handle restrict as well as fortran argument >>> parameters >>> (even if the fortran functions are inlined!), etc. IOW, we don't >>> want to >>> have an feature that just implements C99 restrict, we want a more >>> general >>> mechanism which C99 restrict can be implemented in terms of. It >>> seems >>> like an intrinsic would be a good way to do that. >> >> Certainly language independence is a requirement. >> >> I think your point about inlined functions is also valid for restrict >> parameters to functions that have been inlined in C/C++. The aliasing >> guarantees are limited to within that function's scope For an >> intrinsics approach this would require intrinsics which estrict/ >> unrestrict the pointer bounding it's life within the function where >> it is declared restrict. The other approach would be to add >> attributes that mark all uses of the pointers as explicitly alias >> free, which would be much more invasive. > > For representing scoping information, a relatively non-invasive > approach is to introduce a special "copy" operation, which in LLVM > might look like > %a = copy %b > This operation has to be somewhat special in that can't be folded away > in most cases, but it can otherwise be pretty straight-forward to > optimizers. The idea is to allow %a to be used in whatever alias > intrinsics are available without tainting %b. An inliner would > generate > these special instructions for each of the arguments, and then all > references to the arguments within the inlined body would be made > through these copies. > > An alias-free attribute wouldn't be usable in general because pointers > are almost never completely alias-free. For example in C:From my understanding the 'restrict' qualifier is a directive to the compiler that the pointer or reference should be treated as alias free within the scope of the function, regardless. For the below code alias(p, q) == No, and alias(p, r) == No, even though q is "based-on" p and r may be "based-on" p. This is both the power and danger of 'restrict', as it is up to the programmer to use it correctly.> int * restrict p = ...; > p[x] = 0; > p[y] = 1; > int * q = p + z; > *q = 2; > *p = 3; > int * r = foo(p); > *r = 4; > > Translated to LLVM: > > %t0 = getelementptr %p, %x > store 0, %t0 > %t1 = getelementptr %p, %y > store 1, %t1 > %q = getelementptr %p, %z > store 2, %q > store 3, %p > %r = call @foo(%p) > store 4, %r > > C's restrict keyword allows pointers to be "based-on" restrict- > qualified > pointers, such as q in this example. The definition of "based-on" does > not require the relationship to be obvious though. r in this > example may > or may not be "based-on" p, so an optimizer must make very > conservative > assumptions unless it can get more information about foo.My understanding of 'restrict' is that the compiler isn't required to check that the semantics of restrict aren't violated. I would assume that FORTRAN arguments are the same way, since determining whether or not the semantics of are being violated is just as hard as normal alias analysis. It may even be incorrect for the compiler to enforce the semantics of restrict pointers (with an error), even when the compilers alias analysis determines that there is a may-alias relationship between to pointers. Take the following example, which the compiler is now free to unroll and reschedule: struct element { int a, b; }; void swap(element * arr, int size) { int * __restrict a = &arr[0].a; int * __restrict b = &arr[0].b; for (int i=0; i!=size; ++i) { int tmp = a[i]; a[i] = b[i]; b[i] = tmp; a += 2; b += 2; } }> Beyond C, some form of "based-on" relationship would also be needed > for > LLVM IR, at least so that it could cope with things like %t0 and %t1 > aliasing each other and %p in this example. > > Dan > > -- > Dan Gohman, Cray Inc.-- Christopher Lamb christopher.lamb at gmail.com -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070326/634d2e7a/attachment.html>
Christopher Lamb wrote:-> It may even be incorrect for the compiler to enforce the semantics of > restrict pointers (with an error), even when the compilers alias > analysis determines that there is a may-alias relationship between to > pointers.An error is an example of undefined behaviour. Neil.
On Mon, Mar 26, 2007 at 12:47:04PM -0500, Christopher Lamb wrote:> > > On Mar 26, 2007, at 10:10 AM, Dan Gohman wrote: > > >On Mon, Mar 26, 2007 at 02:14:56AM -0500, Christopher Lamb wrote: > >> > >> > >>On Mar 25, 2007, at 5:22 PM, Chris Lattner wrote: > >> > >>>On Sun, 25 Mar 2007, Christopher Lamb wrote: > >>>>What about an approach not unlike how debugging information is > >>>>handled? That > >>>>is have an llvm intrinsic that encodes the known alias free range > >>>>for a > >>>>pointer. > >>> > >>>That is another great possibility. One issue is that I haven't had > >>>time > >>>to study the implications of C99 restrict, so I don't feel > >>>qualified to > >>>propose a concrete solution yet. Ideally, the mechanism added to > >>>LLVM > >>>would be able to handle restrict as well as fortran argument > >>>parameters > >>>(even if the fortran functions are inlined!), etc. IOW, we don't > >>>want to > >>>have an feature that just implements C99 restrict, we want a more > >>>general > >>>mechanism which C99 restrict can be implemented in terms of. It > >>>seems > >>>like an intrinsic would be a good way to do that. > >> > >>Certainly language independence is a requirement. > >> > >>I think your point about inlined functions is also valid for restrict > >>parameters to functions that have been inlined in C/C++. The aliasing > >>guarantees are limited to within that function's scope For an > >>intrinsics approach this would require intrinsics which estrict/ > >>unrestrict the pointer bounding it's life within the function where > >>it is declared restrict. The other approach would be to add > >>attributes that mark all uses of the pointers as explicitly alias > >>free, which would be much more invasive. > > > >For representing scoping information, a relatively non-invasive > >approach is to introduce a special "copy" operation, which in LLVM > >might look like > > %a = copy %b > >This operation has to be somewhat special in that can't be folded away > >in most cases, but it can otherwise be pretty straight-forward to > >optimizers. The idea is to allow %a to be used in whatever alias > >intrinsics are available without tainting %b. An inliner would > >generate > >these special instructions for each of the arguments, and then all > >references to the arguments within the inlined body would be made > >through these copies.BTW, I misspoke here; this doesn't address the scoping problem.> > > >An alias-free attribute wouldn't be usable in general because pointers > >are almost never completely alias-free. For example in C: > > From my understanding the 'restrict' qualifier is a directive to the > compiler that the pointer or reference should be treated as alias > free within the scope of the function, regardless. For the below code > alias(p, q) == No, and alias(p, r) == No, even though q is "based-on" > p and r may be "based-on" p. This is both the power and danger of > 'restrict', as it is up to the programmer to use it correctly.The definition of restrict is more involved than that. A restrict-qualified pointer may alias a pointer "based-on" it. And if the "based-on" relationships aren't known, then the answer to the associated alias queries must be Maybe. In the test I posted below, the program is correct if x, y, and z are all the same, so the stores cannot be reordered.> > int * restrict p = ...; > > p[x] = 0; > > p[y] = 1; > > int * q = p + z; > > *q = 2; > > *p = 3; > > int * r = foo(p); > > *r = 4; > > > >Translated to LLVM: > > > > %t0 = getelementptr %p, %x > > store 0, %t0 > > %t1 = getelementptr %p, %y > > store 1, %t1 > > %q = getelementptr %p, %z > > store 2, %q > > store 3, %p > > %r = call @foo(%p) > > store 4, %r > > > >C's restrict keyword allows pointers to be "based-on" restrict- > >qualified > >pointers, such as q in this example. The definition of "based-on" does > >not require the relationship to be obvious though. r in this > >example may > >or may not be "based-on" p, so an optimizer must make very > >conservative > >assumptions unless it can get more information about foo. > > My understanding of 'restrict' is that the compiler isn't required to > check that the semantics of restrict aren't violated. I would assume > that FORTRAN arguments are the same way, since determining whether or > not the semantics of are being violated is just as hard as normal > alias analysis. > > It may even be incorrect for the compiler to enforce the semantics of > restrict pointers (with an error), even when the compilers alias > analysis determines that there is a may-alias relationship between to > pointers. Take the following example, which the compiler is now free > to unroll and reschedule: > > struct element { int a, b; }; > > void swap(element * arr, int size) > { > int * __restrict a = &arr[0].a; > int * __restrict b = &arr[0].b; > for (int i=0; i!=size; ++i) > { > int tmp = a[i]; > a[i] = b[i]; > b[i] = tmp; > a += 2; > b += 2; > } > }Yes; this test case is relatively simple to analyze.> >Beyond C, some form of "based-on" relationship would also be needed > >for > >LLVM IR, at least so that it could cope with things like %t0 and %t1 > >aliasing each other and %p in this example. > > > >Dan > > > >-- > >Dan Gohman, Cray Inc. > > -- > Christopher Lamb > christopher.lamb at gmail.com> _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Mar 26, 2007, at 5:53 PM, Neil Booth wrote:> Christopher Lamb wrote:- > >> It may even be incorrect for the compiler to enforce the semantics of >> restrict pointers (with an error), even when the compilers alias >> analysis determines that there is a may-alias relationship between to >> pointers. > > An error is an example of undefined behaviour.The point I was trying to make is that the 'restrict' qualifier stipulates the result of an alias query between to such qualified pointers. So even if the alias analysis returns that these two pointers may alias, it would not be correct to flag an error. This link has an example which may be useful http://www.lysator.liu.se/c/ restrict.html#overlapping-objects. -- Christopher Lamb christopher.lamb at gmail.com -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070326/1e47f46f/attachment.html>
> From my understanding the 'restrict' qualifier is a directive to > the compiler that the pointer or reference should be treated as > alias free within the scope of the function, regardless. For the > below code alias(p, q) == No, and alias(p, r) == No, even though q > is "based-on" p and r may be "based-on" p. This is both the power > and danger of 'restrict', as it is up to the programmer to use it > correctly.My understand here was incorrect. Restrict and non-restrict pointers may alias each other, so alias(p, q) == May and alias(p, r) == May. It is only the case that two restrict pointers do not alias each other. -- Christopher Lamb christopher.lamb at gmail.com -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070326/17e29b74/attachment.html>
On Mar 27, 2007, at 12:54 AM, Chris Lattner wrote:> On Mon, 26 Mar 2007, Christopher Lamb wrote: >>> For representing scoping information, a relatively non-invasive >>> approach is to introduce a special "copy" operation, which in LLVM >>> might look like >>> %a = copy %b >>> This operation has to be somewhat special in that can't be >>> folded away >>> in most cases, but it can otherwise be pretty straight-forward to >>> optimizers. The idea is to allow %a to be used in whatever alias >>> intrinsics are available without tainting %b. An inliner would >>> generate >>> these special instructions for each of the arguments, and then all >>> references to the arguments within the inlined body would be made >>> through these copies. > > I think the goal should be to capture the most important > information. The > c99 definition of restrict has some nasty and complex implementation > issues. It may not be reasonable or interesting to capture every > corner > case. > > A more interesting question is how to represent TBAA information in > LLVM > :). > > Here is a sketch of a concrete proposal to get us started: > > 1. Add a new argument attribute "noalias", which can be applied to > pointer > formals and pointer function results. > 2. Add a new intrinsic "i8* @llvm.noalias(i8*)In the C99 spec it would appear that declaring a pointer function result as restrict has no effect, as it depends purely on whether the pointer being assigned to is declared restrict or not. It's pointed out here that this also applies to using restrict on the pointer type of casts, the restrict qualifier makes no difference in the cast, only to the type that's being assigned to. In this case I'd think that pointer function results would have the intrinsic applied to them if they were assigned to a restrict pointer. Other than clearing up the pointer function results this seems like a good concise proposal.> The semantics of 'noalias' are that they "define a new object". Any > pointer derived from it ("it" being the result of a no-alias call > result, > a formal parameter, or the result of llvm.noalias) is considered to > not > alias: > > A. any other objects (e.g. global vars, allocas, functions, etc) > B. any other "noalias" objects > C. any other formal argument parameters or call results. > > For these purposes, "pointers derived" means getelementptr and > bitcast. > > Can C99 restrict be mapped onto these semantics?I just read through the C99 formal definition of restrict (http:// www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf page 110) with an eye to this proposal, and I believe that C99 restrict can be mapped onto these semantics. Primarily because the requirement is for access though a restrict pointer to be equivalent to accesses to a copy of the "object" that the pointer points to.> Is "C" really safe?I'm not sure what you mean by safe, but I think it's consistent with C99 restrict.> With these semantics, it is clear that 'calloc' could be declared > to have > a result pointer that is noalias for example, but I'm not sure if > it would > be safe to map restrict onto it.Declaring calloc() to return a restrict pointer would have no semantic difference than returning a normal pointer in C99. It would need to be assigned to a variable declared as a restrict pointer to make a difference.>> the following example, which the compiler is now free to unroll and >> reschedule: >> >> struct element { int a, b; }; >> >> void swap(element * arr, int size) >> { >> int * __restrict a = &arr[0].a; >> int * __restrict b = &arr[0].b; >> for (int i=0; i!=size; ++i) >> { >> int tmp = a[i]; >> a[i] = b[i]; >> b[i] = tmp; >> a += 2; >> b += 2; >> } >> } > > This example is also undefined because of the pointer arithmetic > you are > using.Yes. Yes it is. I think I need more sleep. =) I was trying to cook up something like Example 2 (p. 111) from the C99 spec. -- Christopher Lamb christopher.lamb at gmail.com
On Mon, 26 Mar 2007, Christopher Lamb wrote:>> For representing scoping information, a relatively non-invasive >> approach is to introduce a special "copy" operation, which in LLVM >> might look like >> %a = copy %b >> This operation has to be somewhat special in that can't be folded away >> in most cases, but it can otherwise be pretty straight-forward to >> optimizers. The idea is to allow %a to be used in whatever alias >> intrinsics are available without tainting %b. An inliner would generate >> these special instructions for each of the arguments, and then all >> references to the arguments within the inlined body would be made >> through these copies.I think the goal should be to capture the most important information. The c99 definition of restrict has some nasty and complex implementation issues. It may not be reasonable or interesting to capture every corner case. A more interesting question is how to represent TBAA information in LLVM :). Here is a sketch of a concrete proposal to get us started: 1. Add a new argument attribute "noalias", which can be applied to pointer formals and pointer function results. 2. Add a new intrinsic "i8* @llvm.noalias(i8*) The semantics of 'noalias' are that they "define a new object". Any pointer derived from it ("it" being the result of a no-alias call result, a formal parameter, or the result of llvm.noalias) is considered to not alias: A. any other objects (e.g. global vars, allocas, functions, etc) B. any other "noalias" objects C. any other formal argument parameters or call results. For these purposes, "pointers derived" means getelementptr and bitcast. Can C99 restrict be mapped onto these semantics? Is "C" really safe? With these semantics, it is clear that 'calloc' could be declared to have a result pointer that is noalias for example, but I'm not sure if it would be safe to map restrict onto it.>> An alias-free attribute wouldn't be usable in general because pointers >> are almost never completely alias-free. For example in C: > > From my understanding the 'restrict' qualifier is a directive to the compiler > that the pointer or reference should be treated as alias free within the > scope of the function, regardless. For the below code alias(p, q) == No, and > alias(p, r) == No, even though q is "based-on" p and r may be "based-on" p. > This is both the power and danger of 'restrict', as it is up to the > programmer to use it correctly.C99 Restrict is very tricky and subtle. IIRC, it is defined in terms of accesses and objects, not in terms of anything intuitive or natural :)> the following example, which the compiler is now free to unroll and > reschedule: > > struct element { int a, b; }; > > void swap(element * arr, int size) > { > int * __restrict a = &arr[0].a; > int * __restrict b = &arr[0].b; > for (int i=0; i!=size; ++i) > { > int tmp = a[i]; > a[i] = b[i]; > b[i] = tmp; > a += 2; > b += 2; > } > }This example is also undefined because of the pointer arithmetic you are using. -Chris -- http://nondot.org/sabre/ http://llvm.org/