Re: Ada to C/C++ translator needed

[ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe)]

I mentioned the proposed 'restrict' keyword.

On Wed, 2 Oct 1996, Simon Johnston wrote:

> "restrict" what is this new keyword, where can one find out about this!

Richard Riehle <rriehle@nunic.nu.edu> writes:

>  I think he may be referring to #define Strict which is available
>  on some C/C++ compilers to enforce type checking.

Richard Riehle is wrong.  I am referring to the proposed C9x keyword
'restrict'.  It is the cleaned up and redesigned replacement for the
'noalias' keyword added at the last minute to C89 and dropped at the
last second.  To put it at its very crudest,

	void vecadd(float a[restrict],
		    float const b[restrict],
		    float const c[restrict], int n) {
	    int i;
	    for (i = 0; i < n; i++) a[i] = b[i] + c[i];
	}

tells a compiler that there is no aliasing amongst a, b, and c,
so that it doesn't have to follow the strict sequential model.
It can, for example, do
	ldf4  f0, b		- quad-word FP load
	addi  #16,b
	ldf4  f4, c
	addi  #16,c
	addf  f0, f4, f0	- S.P. FP add
	addf  f1, f5, f1
	addf  f2, f6, f2
	addf  f3, f7, f3
	stf4  f0, a				 
	addi  #16,a
inside a loop, which would _not_ give the right results if for example
a == &b[1].  On a modern superscalar RISC, this might end up taking n
cycles, whereas maintaining C semantics in the face of possible aliasing
would probably take 3n cycles.  I have something rather like the
UltraSPARC in mind, but don't mistake this for UltraSPARC code.  And you
would need loop unrolling and good scheduling to reach that 1 cycle per
FLOP result.  This kind of speedup is why noalias was wanted, and as a
tamed noalias, restrict is going to be important.

The proposal has been available over the net for enough years that I have
forgotten exactly where I got it.  It is _supported_ by one of the
compilers I use.  (Which is why that compiler is a very good compiler for
numerical performance experiments, contrary to one Tim Behrendsen's
attacks on it.)

Since this is comp.lang.ada, perhaps someone could explain clearly
whether an Ada compiler is allowed to perform this kind of optimisation
given

	type Vector is array (Positive range <>) of Float;

	procedure Vec_Add(A: out Vector; B, C: in Vector) is
	begin
	    for I in A'Range loop A(I) := B(I) + C(I); end loop;
	end Vec_Add;

I used to think that calls like

	declare
	    X, Y: Vector(3) := (1..3 => 1.0);
	begin
	    Vec_Add(X(2..3), X(1..2), Y(1..2));
	end;

were forbidden, because the result depended on whether 'in Vector' was
passed by copy or reference, but I probably got that wrong, and I am
even less sure of exactly what the rule is in Ada 95.  A factor of 3
speedup is worth having...

-- 
Mixed Member Proportional---a *great* way to vote!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.