On Mar 25, 2007, at 5:22 PM, Chris Lattner wrote:> On Sun, 25 Mar 2007, Christopher Lamb wrote: >>> So far, there hasn't been a discussion. IMO, the most important >>> form is >>> for formal arguments. That could easily be added thorough the >>> use of an >>> attribute on the parameter. >> >> I assume the idea here is to avoid actually attributing the type >> (as was >> avoided with signed/unsigned integers by differentiating ops). > > Yep, exactly. > >> 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. On a related topic, I think that similar types of attributes will be needed if LLVM is to support a concurrent memory model. Perhaps these could all be rolled into the same package. Ideally I think it would be nice to be able to start off using intrinsics to communicate this kind of information, though it may end up as changes to instruction down the line, but I'm not enough of an expert to be able to say whether this is a feasible strategy. -- Christopher Lamb christopher.lamb at gmail.com
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: 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. 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.
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>
On Mon, 26 Mar 2007, Christopher Lamb wrote:>> 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 aliasingYep.> Ideally I think it would be nice to be able to start off using > intrinsics to communicate this kind of information, though it may end > up as changes to instruction down the line, but I'm not enough of an > expert to be able to say whether this is a feasible strategy.Yes, that is a preferable approach. Intrinsics are easy to add, and can do almost anything that instructions can. They are a great way to get experience with an approach. -Chris -- http://nondot.org/sabre/ http://llvm.org/