noalias assertions in function prototypes

[David Hough]

Trying to figure out "noalias" issues at the last NCEG meeting, I came
to the conclusion, as others have, that what needs to be communicated are
three-way usage assertions between the callee writer, compiler, and caller.
Thus the noaliasness is part of the interface and belongs in the function
prototype, to the extent that you want to solve the noalias problem to
approximately the same extent as Fortran does.   It seems to be hard enough
to agree on how to solve that problem, much less more general noalias issues
that can't arise in Fortran without explicit pointers.

What follows is a proposal for assertions to be incorporated into function
prototypes.   To avoid gratuitous abstraction, the information is presented
as concrete syntax.   I don't think the syntax is good, but I think the
semantic content is at the correct level.   It doesn't seem to exactly 
correspond to any proposal that I heard at the last NCEG meeting,  but I
may well have missed some things.

The "noalias" property is a property of sets of
pointers used in a particular specific
way that is part of the implementation of a function.  Some flexibility seems
desirable to accommodate the different ways that a function's implementors
might code it, and to accommodate varying tradeoffs between caller convenience
and callee optimizability.   Noaliasness is not a property of a type or of
a particular pointer, which may be aliasable in one situation and not in
another, or may be harmlessly
aliased with some of the parameters of a function but not with others.

To start concretely, consider the ANSI-C prototypes

	void *memcpy(void *s1, const void *s2, size_t n);
	void *memmove(void *s1, const void *s2, size_t n);

n characters are copied from s2 to s1.  The behavior of memcpy is undefined
if the arrays overlap anywhere.  memmove is always defined to do the "right"
thing as if the move were through a temporary array completely disjoint from
s1 and s2.  This means that some checking must occur and so memmove may be
slower than memcpy.

Suppose that one wanted to define a function as efficient as memcpy that
explicitly put the onus on the programmer to check.  Here are two possible
approaches:

	void *na_memcpy(void *s1, const void *s2, size_t n, 
			__noalias__(s1[0..(n-1)],s2[0..(n-1)]) ));
 
	void *na_memcpy(void *s1, const void *s2, size_t n, 
			__noalias__(i,s1[i],s2[i]) );

__noalias__(s1[0..(n-1)],s2[0..(n-1)])

	means that the coder of na_memcpy and the optimizer of na_memcpy 
may assume that s1[0]..s1[n-1] is completely disjoint from s2[0]..s2[n-1].
It is not possible to change any part of s2 by writing to any part of s1.
Hence, in particular, the copy loop may be unrolled and rescheduled
as much as desired by either the coder or the optimizer.

__noalias__(i,s1[i],s2[i])

	means that the coder of na_memcpy and the optimizer of na_memcpy may
assume that s1[i] and s2[i] are disjoint for any i.  It is not possible to
change s2[i] by writing to s1[i].   Hence, in particular, the copy loop
may be unrolled as long as ld s2[i], st s1[i] aren't rescheduled to overlap
any ld s2[i+-k] or st s1[i+-k] for any k.   This allows more freedom to the
caller and less to the optimizer than the form above.   The most appropriate
form is a matter taste and judgment, as with any other aspect of an interface.
	i has to be declared
somehow - in effect as a Fortran-like dummy index variable - so that it's
not confused with any other variables.   

	The subscript expressions could be arbitrarily complicated e.g. 
__noalias__(i,s1[expr1],s2[expr2])
but complicated assertions probably won't be exploitable by callee optimizers
though they might be meaningful to the human calling programmer.

	Either type of assertion requires that the calling code must comply 
with the assertion.  
In many common cases the compiler will be able to check this
and indicate an error if the assertion is not satisfied or the compiler
can't verify it.  In general, though, the compiler can't so verify and so there
would be a lot of error messages.  This would be an inconvenience for
many legitimate uses, so the caller programmer needs a way to take
responsibility.  One syntax is

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

When __noalias__ appears in a function invocation rather than a function 
prototype, it instructs
the compiler not to check the __noalias__ assertions in the prototype.
Thus the caller
programmer is always free to bypass all such assertion checking, either by
adding the token that
turns off checking to each call,
or by calling the function without a prototype in scope.



The foregoing touches on a more general issue:  what assertions should a 
callee be able to make to the caller and to the optimizer, 
and how should they be 
incorporated into the function prototype syntax?

In the IEEE arithmetic context, a function might want to assert that it's
called only in default rounding mode, or only with invalid trap disabled or
enabled, etc.   I wouldn't expect compilers to be able to check very many
of these assertions, so the effect of putting them in the prototype would be
to make the programmer acknowledge them and take responsibility by adding
__assert__ to all calls to those functions.

How about traditional assertions like
	double a_sqrt( double x , __assert__(x >= 0) ) ;
That could be used to eliminate some argument checking in a_sqrt by moving the
intellectual or coding burden to the caller programmer.

Or more radically
	double a_fabs( double x , __assert__(x==x), __assert__(a_fabs >= 0) ) ;

The first assertion is that the argument is a number rather than a NaN,
to enable the second assertion that the result is non-negative.

A C traditionalist might well argue that all such assertions belong in the
documentation rather than the machine-readable interface description; one could
say that about the current ANSI-C
function prototypes too, although the latter are always 
compiler-checkable.