On Aug 19, 2007, at 1:15 PM, Gordon Henriksen wrote:> On 2007-08-19, at 15:41, Duncan Sands wrote: > >> can you please explain more about what restrict means: it may help >> in improving code quality for Ada. In Ada you have runtime >> constants that are really constant, for example array bounds. The >> bounds are passed around by pointer, which causes LLVM to think >> they may be aliased and changed by function calls (which is >> impossible). This results on rotten code since (for example) the >> array length and bounds checks are recalculated again and again >> when one calculation would do. [The front-end outputs a bound >> check for every array access, expecting the optimizers to remove >> redundant checks, which LLVM often does not do]. If I could teach >> LLVM that array bounds are really constant that would presumably >> solve the problem.The benefits of a const * __restrict come from two different places. The const part is essentially enforced by the front-end and the restrict part is used to inform the alias analysis (it becomes a noalias parameter attribute). The noalias parameter attribute may be of use to you eventually, but full noalias implementation isn't yet complete. Specifically the case where a function with noalias parameter attributes is inlined does not currently preserve the noalias information.> Here's a thread about it: > > http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/thread.html#8291You should also take a look at PR 1373, as that is where progress is being tracked. http://llvm.org/bugs/show_bug.cgi?id=1373> I don't think anything has been implemented.Per the discussion and PR there has been work done to implement the 'noalias' parameter attribute in LLVM, and currently BasicAA will use this attribute to inform alias queries that are made. There has also been work to map __restrict C/C++ pointer and reference parameters onto the noalias parameter attribute. There is still much work to be done to fully implement noalias in LLVM, notably the intrinsic and updates to tolerate/use it, as well as to fully support all uses of the __restrict qualifier in the C/C++ front end. -- Christopher Lamb -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070819/03241375/attachment.html>
Hi Christopher,> The benefits of a const * __restrict come from two different places. > The const part is essentially enforced by the front-end and the > restrict part is used to inform the alias analysis (it becomes a > noalias parameter attribute). The noalias parameter attribute may be > of use to you eventually, but full noalias implementation isn't yet > complete. Specifically the case where a function with noalias > parameter attributes is inlined does not currently preserve the > noalias information. > > > Here's a thread about it: > > > > http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/thread.html#8291 > > You should also take a look at PR 1373, as that is where progress is > being tracked. http://llvm.org/bugs/show_bug.cgi?id=1373 > > > I don't think anything has been implemented. > > Per the discussion and PR there has been work done to implement the > 'noalias' parameter attribute in LLVM, and currently BasicAA will use > this attribute to inform alias queries that are made. There has also > been work to map __restrict C/C++ pointer and reference parameters > onto the noalias parameter attribute. There is still much work to be > done to fully implement noalias in LLVM, notably the intrinsic and > updates to tolerate/use it, as well as to fully support all uses of > the __restrict qualifier in the C/C++ front end.it looks like noalias might be very useful for Ada: for certain types, such as array types, the language standard explicitly allows the compiler to pretend that a formal argument of that type is passed by-copy (= by-value) for alias analysis purposes, while actually passing it by-reference (= via a pointer). I'm not sure, but based on Chris's suggested implementation http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/008323.html it seems that this may map exactly to "noalias". There is a subtlety though: the compiler may pretend that a copy was passed in, but it must correspond to a copy made at the moment of the function call, not later. In Chris's description " The semantics of 'noalias' are that they "define a new object" " it is not specified *when* the new object gets its value; Ada requires the pretend "new object" to act as if it got its value at the start of the function body, not later, as if a copy of the real object was made at that point. For example, suppose that there are two formal array parameters A and B, and in the function body A is read then later B is written: read from A ... write to B In general it is wrong to re-order the read after the write, since then the read might get a new value written via B, which would be inconsistent with A being a copy made at the start of the function call (instead it would correspond to A being a copy made part way through the execution of the body, after the write to B). On the other hand, if first B is written and later A is read: write to B ... read from A then it is legal to re-order the read before the write. I very much hope that noalias semantics are or can be made to be consistent with this scheme: it represents an important optimization for Ada, since the language standard permits it in many significant cases. Ciao, Duncan.
On Aug 21, 2007, at 6:12 AM, Duncan Sands wrote:> Hi Christopher, > >> The benefits of a const * __restrict come from two different places. >> The const part is essentially enforced by the front-end and the >> restrict part is used to inform the alias analysis (it becomes a >> noalias parameter attribute). The noalias parameter attribute may be >> of use to you eventually, but full noalias implementation isn't yet >> complete. Specifically the case where a function with noalias >> parameter attributes is inlined does not currently preserve the >> noalias information. >> >>> Here's a thread about it: >>> >>> http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/ >>> thread.html#8291 >> >> You should also take a look at PR 1373, as that is where progress is >> being tracked. http://llvm.org/bugs/show_bug.cgi?id=1373 >> >>> I don't think anything has been implemented. >> >> Per the discussion and PR there has been work done to implement the >> 'noalias' parameter attribute in LLVM, and currently BasicAA will use >> this attribute to inform alias queries that are made. There has also >> been work to map __restrict C/C++ pointer and reference parameters >> onto the noalias parameter attribute. There is still much work to be >> done to fully implement noalias in LLVM, notably the intrinsic and >> updates to tolerate/use it, as well as to fully support all uses of >> the __restrict qualifier in the C/C++ front end. > > it looks like noalias might be very useful for Ada: for certain types, > such as array types, the language standard explicitly allows the > compiler > to pretend that a formal argument of that type is passed by-copy (= > by-value) > for alias analysis purposes, while actually passing it by-reference > (= via a pointer). > I'm not sure, but based on Chris's suggested implementation > http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/008323.html > it seems that this may map exactly to "noalias". There is a subtlety > though: the compiler may pretend that a copy was passed in, but it > must > correspond to a copy made at the moment of the function call, not > later. > > In Chris's description > " The semantics of 'noalias' are that they "define a new object" " > it is not specified *when* the new object gets its value; Ada requires > the pretend "new object" to act as if it got its value at the start of > the function body, not later, as if a copy of the real object was made > at that point.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.> For example, suppose that there are two formal array parameters A > and B, > and in the function body A is read then later B is written: > read from A > ... > write to B > In general it is wrong to re-order the read after the write, since > then the read might get a new value written via B, which would be > inconsistent with A being a copy made at the start of the function > call (instead it would correspond to A being a copy made part way > through the execution of the body, after the write to B). On the > other hand, if first B is written and later A is read: > write to B > ... > read from A > then it is legal to re-order the read before the write.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).> I very much hope that noalias semantics are or can be made to be > consistent with this scheme: it represents an important optimization > for Ada, since the language standard permits it in many significant > cases.It seems that you may be in luck. -- Christopher Lamb -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070821/895780c8/attachment.html>