noalias assertions

[David Hough]

Peter Shenkin raises some good points.  I'm no noalias expert either, which
is why my posting was just to raise some issues rather than a formal NCEG
proposal.  But I can explain what I was thinking of:

> in how much detail do we need to allow the callee 
> to specify noaliasing?

My shot at the answer is "enough detail to allow the desired optimization
of the particular algorithm that the callee implements"

> On question (1), suppose that the callee needs only to assert that in any 
> invocation of the function, no portion of some particular argument that is
> assigned to can overlap any portion of some other argument.

> void *na_memcpy(void *s1, const void *s2, size_t n, noalias(s1[],s2[]) )

The last line asserts only that s1 != s2.  The compiler of the caller
can't tell from
this prototype what the extent of s1 and s2 are, hence whether it's OK or
not for s2 to point into the last half of s1.  That's different from
asserting that s1[0..n] and s2[0..n] are completely disjoint.  The prototype
above doesn't associate n with s1 and s2.

> The noalias statement is intended to convey the same meaning as described 
> above for:
> 
> > __noalias__(i,s1[i],s2[i])

This also means s1 != s2 - maybe it should have been

	__assert__(s1 != s2)

but either way it doesn't tell whether the whole objects
must be disjoint or not.  The assertions have to include n to imply something
about the whole object.

> are the complications wrought by the
> possibility of specifications such as:
> 
> > __noalias__(i,s1[expr1],s2[expr2])

> really worth it, in terms of the amount of optimization that is made possible
> due to the additional flexibility?

This is the nub of the matter - how complicated can assertions get before
they won't be useful to compilers?

Anyway if you wanted to unroll a copy loop three times you might want an
assertion to the effect that abs(s1-s2) > 3.
There are many ways to formulate such an assertion, and I wouldn't claim
to know the best way to formulate it for automatic interpretation by compilers.

> whether we really need to add something to the language to
> allow a caller to override a noalias specification in the callee.  Wouldn't
> the same thing be accomplished by having two similar functions, one
> with a no-alias specification and one without, that the caller could
> have access to?  He could then call the one he wanted.  Or, alternatively, 
> one could write a dispatch function which, by means of a flag specified in 
> the caller, itself called either the lower-level function that allows aliasing
> of arguments or the one that doesn't.  

Right or wrong, the chain of reasoning is this:

a) The callee has been compiled as if certain assertions are true.

b) When compiling the callee, the compiler can't always verify these
assertions - that's equivalent to the halting problem.  If the compiler
can't verify the assertions, then it must indicate an error in case the
programmer didn't notice the assertion requirement or made a mistake.

c) But the programmer may know that the assertions are true or that
there is no harm in assuming they are true.   While one could define another
callee function with no assertions, that one might not be as optimizable.
The blanket noalias assertion on the caller side doesn't really override
the assertion as much as represent an acceptance of responsibility by
the programmer, for instance for the case that
the pointers in question are themselves inherited from far away
in a separately compiled procedure, of which the programmer knows something
but the compiler can't.

> It just strikes me that a function call
> such as:
> 
> > 	(void) na_memcpy(s1, s2, n, __noalias__) ;
> 
> where __noalias__ is part of the language rather than an ordinary function
> argument is a really a big change in the way the language works.

Certainly putting assertions in function prototypes is a big change
no matter how you dress it up.
Stallman has already proposed using a ; to separate the list of
function parameters from the list of other information declared in a
prototype.   So if we are going to optionally pass any other "machine-readable"
information in NCEG function prototypes, it might well be done that way:

> >     (void) na_memcpy(s1, s2, n; __noalias__) ;
                                  ^
                                  ^

which may be slightly more tolerable from the point of view of language design.

I'm hopeful that better syntax can be invented, but I am convinced
that some kind of noalias feature is necessary and I doubt that putting
that information into the type of a variable can be the right solution.

I should mention that my thinking on this was stimulated by a Dave Prosser
comment to the effect that you might well want to distinguish situations like

char s1[10];

umemcpy(s1+5,s1,5)     defined
umemcpy(s1+5,s1,6)     undefined

(umemcpy means a user-defined function just like memcpy for which the compiler
can't refer to the ANSI-C standard for semantic information!)

Merely specifying something in the umemcpy prototype about s1 and s2 being 
noaliased might seem overly restrictive.

Code like that actually bit me.  One of the IMSL libraries used the BLA
SCOPY incorrectly for an overlapped move.   
Yet it worked correctly in the face of numerous aggressive
optimizing compilers on many different platforms, including Sun-4.  But it 
failed on the last Sun-3 Fortran compiler which was quite a bit less
advanced overall but did have an optimization which unrolled loops and
scheduled different 68881 loads and stores past each other.   
The Fortran standard
grants license for the compiler to blame the programmer in that case, but
wouldn't it have been better if the SCOPY programmer could have specified
exactly what overlap was or wasn't permitted in a way that could be checked?