[LLVMdev] c const

[Duncan Sands]

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.