<HTML><BODY style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><DIV><SPAN class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><BR class="Apple-interchange-newline"></SPAN> </DIV><BR><DIV><DIV>On Mar 26, 2007, at 10:10 AM, Dan Gohman wrote:</DIV><BR class="Apple-interchange-newline"><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">On Mon, Mar 26, 2007 at 02:14:56AM -0500, Christopher Lamb wrote:</DIV> <BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">On Mar 25, 2007, at 5:22 PM, Chris Lattner wrote:</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV> <BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">On Sun, 25 Mar 2007, Christopher Lamb wrote:</DIV> <BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">What about an approach not unlike how debugging information is <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">handled? That</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">is have an llvm intrinsic that encodes the known alias free range <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">for a</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">pointer.</DIV> </BLOCKQUOTE><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">That is another great possibility.<SPAN class="Apple-converted-space"> </SPAN>One issue is that I haven't had <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">time</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">to study the implications of C99 restrict, so I don't feel <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">qualified to</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">propose a concrete solution yet.<SPAN class="Apple-converted-space"> </SPAN>Ideally, the mechanism added to LLVM</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">would be able to handle restrict as well as fortran argument <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">parameters</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">(even if the fortran functions are inlined!), etc.<SPAN class="Apple-converted-space"> </SPAN>IOW, we don't <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">want to</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">have an feature that just implements C99 restrict, we want a more <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">general</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">mechanism which C99 restrict can be implemented in terms of.<SPAN class="Apple-converted-space"> </SPAN>It seems</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">like an intrinsic would be a good way to do that.</DIV> </BLOCKQUOTE><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Certainly language independence is a requirement.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">I think your point about inlined functions is also valid for restrict <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">parameters to functions that have been inlined in C/C++. The aliasing <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">guarantees are limited to within that function's scope For an <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">intrinsics approach this would require intrinsics which estrict/<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">unrestrict the pointer bounding it's life within the function where <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">it is declared restrict. The other approach would be to add <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">attributes that mark all uses of the pointers as explicitly alias <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">free, which would be much more invasive.</DIV> </BLOCKQUOTE><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">For representing scoping information, a relatively non-invasive</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">approach is to introduce a special "copy" operation, which in LLVM</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">might look like</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>%a = copy %b</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">This operation has to be somewhat special in that can't be folded away</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">in most cases, but it can otherwise be pretty straight-forward to</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">optimizers. The idea is to allow %a to be used in whatever alias</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">intrinsics are available without tainting %b. An inliner would generate</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">these special instructions for each of the arguments, and then all</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">references to the arguments within the inlined body would be made</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">through these copies.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">An alias-free attribute wouldn't be usable in general because pointers</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">are almost never completely alias-free. For example in C:</DIV></BLOCKQUOTE><DIV><BR class="khtml-block-placeholder"></DIV><DIV>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.</DIV><BR><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>int * restrict p = ...;</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>p[x] = 0;</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>p[y] = 1;</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>int * q = p + z;</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>*q = 2;</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>*p = 3;</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>int * r = foo(p);</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>*r = 4;</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Translated to LLVM:</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>%t0 = getelementptr %p, %x</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>store 0, %t0</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>%t1 = getelementptr %p, %y</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>store 1, %t1</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>%q = getelementptr %p, %z</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>store 2, %q</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>store 3, %p</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>%r = call @foo(%p)</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>store 4, %r</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">C's restrict keyword allows pointers to be "based-on" restrict-qualified</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">pointers, such as q in this example. The definition of "based-on" does</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">not require the relationship to be obvious though. r in this example may</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">or may not be "based-on" p, so an optimizer must make very conservative</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">assumptions unless it can get more information about foo.</DIV></BLOCKQUOTE><DIV><BR class="khtml-block-placeholder"></DIV><DIV>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.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>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:</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>struct element { int a, b; };</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>void swap(element * arr, int size)</DIV><DIV>{</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>int * __restrict a = &arr[0].a;</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>int * __restrict b = &arr[0].b;</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>for (int i=0; i!=size; ++i)</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>{</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>int tmp = a[i];</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>a[i] = b[i];</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>b[i] = tmp;</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>a += 2;</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>b += 2;</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>}</DIV><DIV>}</DIV><DIV><BR class="khtml-block-placeholder"></DIV><BR><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Beyond C, some form of "based-on" relationship would also be needed for</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">LLVM IR, at least so that it could cope with things like %t0 and %t1<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">aliasing each other and %p in this example.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Dan</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">--<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Dan Gohman, Cray Inc.</DIV></BLOCKQUOTE></DIV><DIV><BR><DIV><DIV>--</DIV><DIV>Christopher Lamb</DIV><DIV><A href="mailto:christopher.lamb@gmail.com">christopher.lamb@gmail.com</A></DIV></DIV></DIV></BODY></HTML>