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>
Hi Christopher,> > 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.no! In the Ada case, the arguments can point to the same object (I think this is the same for Fortran too - not sure). For example, if the same array pointer is passed for two arguments, the compiler is allowed to pretend that the two arguments point to different objects as long as it only performs transforms that would be correct if pointers to two distinct copies of the array had been passed, copies made at the point of the call. Of course no such copies are made, and the same pointer is actually passed for both arguments. Programmers who are not aware of this will of course be surprised at the results, but will be shot down by the language lawyers :) Also, I don't understand your remark about C/C++ restrict semantics: I thought noalias meant that you can *pretend* that two noalias arguments point to different objects; and if you pass the same object then you get what you deserve, and C/C++ doesn't define what happens in this case. Since C/C++ doesn't define this case, we can define it to mean what we like. I would like to define the set of legal transformations to be as described above, when aliased pointers are passed. Further, in the Ada case you are allowed to suppose that the parameter doesn't alias anything, including global variables and all other parameters, even if it fact it does. Subject of course to the restriction that the transforms should result in a program that would be correct if pointers to copies of each object pointed to by a noalias pointer had been passed in.> > 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).This is bad, and means that noalias is useless for Ada. The first transformation is not allowed, because it is not consistent with a pointer to a copy being passed in. Is it clear why it is inconsistent? Suppose A and B point to the same object, an array of one element. Suppose the array element equals 0 at the point of the call. If I do x = A[0] B[0] = 1 in Ada, then the value of x must be 0 not 1: if copies C, D of the array had been made at the point of the call, and C and D had been passed in instead of A and B, then x would be equal to 0 because the assignment D[0]=1 won't change the value of C[0]. Thus the "as-if-copies-had-been-passed" rule means that x must equal 0. If you switch the order B[0] = 1 x = A[0] then x would equal 1 not 0, which would not be possible if copies had been passed. Thus this transform is illegal in Ada, because it is inconsistent with what would happen if pointers to copies had been passed in. [Note that in Ada you pass arrays not pointers to arrays, but they will usually be passed "by-reference" and end up being passed as pointers in LLVM, which is why I talked about pointers to arrays above.]> > 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.No, it seems I am out of luck unless the definition of noalias is modified. Ciao, Duncan.
On Aug 21, 2007, at 10:17 AM, Duncan Sands wrote:> Hi Christopher, > >>> 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.Please excuse this atrocious sentence. It's completely misleading (I don't drink coffee, but maybe I should start?) It should read: I can't see how the semantics could be anything but for the "new object" to be created at the beginning of the function. I merged the wrong parts of two sentences in my earlier email. Sorry for the grief! -- Christopher Lamb -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070821/2f37745d/attachment.html>
On Aug 21, 2007, at 11:10 PM, Duncan Sands wrote:> Hi Christopher, > >> In C/C++ a restrict pointer is also assumed not to alias any other >> parameters, global values or local value. However the compiler must >> not assume that pointers "based on" a restrict pointer do not alias. > > does "based on" mean something like: copies of the pointer made in the > function body?To be precise (brackets mine): In what follows, a pointer expression E is said to be based on object P [a pointer] if (at some sequence point in the execution of B [the enclosing block] prior to the evaluation of E) modifying P to point to a copy of the array object into which it formerly pointed would change the value of E. Note that ‘‘based’’ is defined only for expressions with pointer types. This is from http://www.open-std.org/jtc1/sc22/wg14/www/docs/ n1124.pdf Sec 6.7.3.1 para 3>> Your example strikes me as contradictory to your description of Ada >> aliasing rules above. If A and B were in fact copies of an object >> then in your first example x would always be 0, no matter which order >> the reads and writes are performed. Thus if permuting those memory >> operations is safe when copies are passed then that same transform >> is, by your definition, allowed when the same array is passed as both >> parameters by reference. >> >> I can't reconcile your statement that in Ada array parameters can be >> assumed to not alias, but that that the compiler must be careful to >> limit the transforms it applies in the case that they do alias. >> >> Is there a reference that you can point to in the Ada spec that >> describes this concretely? > > Sure, check out > http://www.adaic.com/standards/05aarm/html/AA-6-2.html > Some types, like array types, are neither by-copy types nor by- > reference > types. The candidates I have in mind for noalias are formal > parameters > of such a type. The parameter passing mechanism used for the > parameter > is then not specified (6.2.11). As explained in 6.2.12, if you write > to the passed object via some other parameter or a global variable, > then read via this parameter, it is undefined as to whether you read > the new value or some old value (or raise an exception). The rest of > section 6.2 discusses this rule, see especially 6.2.12.j.I'll take a look as time permits. -- Christopher Lamb -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070822/1585dcca/attachment.html>
Hi Christopher,> >> In C/C++ a restrict pointer is also assumed not to alias any other > >> parameters, global values or local value. However the compiler must > >> not assume that pointers "based on" a restrict pointer do not alias. > > > > does "based on" mean something like: copies of the pointer made in the > > function body? > > To be precise (brackets mine): > > In what follows, a pointer expression E is said to be based on object > P [a pointer] if (at some > sequence point in the execution of B [the enclosing block] prior to > the evaluation of E) modifying P to point to > a copy of the array object into which it formerly pointed would > change the value of E. > Note that ‘‘based’’ is defined only for expressions with pointer types. > > This is from http://www.open-std.org/jtc1/sc22/wg14/www/docs/ > n1124.pdf Sec 6.7.3.1 para 3suppose A and B are array pointers, and are in fact equal. Consider the code sequences (i) x = A[0] (a) B[0] = 1 (b) and (ii) B[0] = 1 (b) x = A[0] (a) If I understand right, (i)(b) is not based on A, either because it has no value (not sure what "the value of E" means) or because changing A to point to a copy would make no difference because (i)(a) is only a read. Also (i)(a) is not based on B because this is the first instruction. On the other hand (ii)(a) is based on B because the value of x is 1, but would be something else if B was changed to point to a copy. Does this mean that if B is a restricted pointer, then the lines can be swapped in (i). That if A is a restricted pointer then the lines can be swapped in (i) and (ii)? This sounds very similar to the Ada setup, though somehow "dual" to it. Ciao, Duncan.