<HTML><BODY style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><BR><DIV><DIV>On Aug 21, 2007, at 6:12 AM, Duncan Sands wrote:</DIV><BR class="Apple-interchange-newline"><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Hi Christopher,</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; ">The benefits of a const * __restrict come from two different places. <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">The const part is essentially enforced by the front-end and the <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">restrict part is used to inform the alias analysis (it becomes a <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">noalias parameter attribute). The noalias parameter attribute may be <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">of use to you eventually, but full noalias implementation isn't yet <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">complete. Specifically the case where a function with noalias <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">parameter attributes is inlined does not currently preserve the <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">noalias information.</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; ">Here's a thread about it:</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; "><A href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/thread.html#8291">http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/thread.html#8291</A></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; ">You should also take a look at PR 1373, as that is where progress is <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">being tracked. <A href="http://llvm.org/bugs/show_bug.cgi?id=1373">http://llvm.org/bugs/show_bug.cgi?id=1373</A></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; ">I don't think anything has been implemented.</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; ">Per the discussion and PR there has been work done to implement the <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">'noalias' parameter attribute in LLVM, and currently BasicAA will use <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">this attribute to inform alias queries that are made. There has also <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">been work to map __restrict C/C++ pointer and reference parameters <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">onto the noalias parameter attribute. There is still much work to be <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">done to fully implement noalias in LLVM, notably the intrinsic and <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">updates to tolerate/use it, as well as to fully support all uses of <SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">the __restrict qualifier in the C/C++ front end.</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; ">it looks like noalias might be very useful for Ada: for certain types,</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">such as array types, the language standard explicitly allows the compiler</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">to pretend that a formal argument of that type is passed by-copy (= by-value)</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">for alias analysis purposes, while actually passing it by-reference (= via a pointer).</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">I'm not sure, but based on Chris's suggested implementation</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><A href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/008323.html">http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/008323.html</A></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">it seems that this may map exactly to "noalias".<SPAN class="Apple-converted-space"> </SPAN>There is a subtlety</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">though: the compiler may pretend that a copy was passed in, but it must</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">correspond to a copy made at the moment of the function call, not later.</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; ">In Chris's description</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">" The semantics of 'noalias' are that they "define a new object" "</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">it is not specified *when* the new object gets its value; Ada requires</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">the pretend "new object" to act as if it got its value at the start of</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">the function body, not later, as if a copy of the real object was made</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">at that point.</DIV></BLOCKQUOTE><DIV><BR class="khtml-block-placeholder"></DIV><DIV>I can't see how the semantics could be anything other than for the "new object" that the noalias argument points to could be created at any other time than the beginning of the function. By definition a noalias argument cannot point to the same object as any other argument, or else C/C++ restrict semantics wouldn't map onto it either.</DIV><BR><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">For example, suppose that there are two formal array parameters A and B,</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">and in the function body A is read then later B is written:</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>read from A</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">...</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>write to B</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">In general it is wrong to re-order the read after the write, since</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">then the read might get a new value written via B, which would be</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">inconsistent with A being a copy made at the start of the function</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">call (instead it would correspond to A being a copy made part way</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">through the execution of the body, after the write to B).<SPAN class="Apple-converted-space"> </SPAN>On the</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">other hand, if first B is written and later A is read:</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>write to B</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">...</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN class="Apple-converted-space"> </SPAN>read from A</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">then it is legal to re-order the read before the write.</DIV></BLOCKQUOTE><DIV><BR class="khtml-block-placeholder"></DIV><DIV>In both of these cases it would be wrong to reorder the memory operations unless alias analysis concluded that they did not alias each other. If either of A or B (or both) are marked as noalias parameters then the alias analysis will return that A does not alias B, allowing either of the transforms that you mention. This applies to derived pointers to any two distinct objects where one is a noalias parameter as well (i.e. via GEP).</DIV><BR><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">I very much hope that noalias semantics are or can be made to be</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">consistent with this scheme: it represents an important optimization</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">for Ada, since the language standard permits it in many significant</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">cases.</DIV> </BLOCKQUOTE></DIV><DIV><BR class="khtml-block-placeholder"></DIV>It seems that you may be in luck.<DIV><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; "><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; "><DIV>--</DIV><DIV>Christopher Lamb</DIV><DIV><BR class="khtml-block-placeholder"></DIV><BR class="Apple-interchange-newline"></SPAN></SPAN> </DIV><BR></DIV></BODY></HTML>