🚀 go-pugleaf

In article <1630@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes:

>One of our programmers asked me whether some transfers could be deleted
>from code.  It was possible by essentially duplicating some code, and
>making inessential changes in the program.  I doubt a compiler could
>figure this out.

Steve Carr showed me this transformation, which can be done automatically
(and *is* done, in a local experimental compiler).
This is slightly contrived, for expository simplicity.

A simple DO-loop

	DO i = 1, 2*n
	    x(i) = f(y(i))
	    z(i) = g(x(i-1))
	ENDDO

where x, y, and z are arrays and f and g are arbitrary functions.
Note the reuse of each x(i) value one iteration after it has been set.
We can take advantage of this reuse

	x1 = x(0)
	DO i = 1, 2*n
	    x0 = f(y(i))
	    x(i) = x0
	    z(i) = g(x1)
	    x1 = x0
	ENDDO

This is nice because we save a memory access per iteration.
(Assuming a smart backend (normal optimizing compiler) that
 will allocate x0 and x1 to registers.)
The problem is that we'll end up with an extra reg-reg copy
(x1=x0) at the end of the loop.
This can be avoided by unrolling slightly to subsume the copy.

	x1 = x(0)
	DO i = 1, n
	    x0 = f(y(i))
	    x(i) = x0
	    z(i) = g(x1)
	    x1 = f(y(i+1))
	    x(i+1) = x1
	    z(i) = g(x0)
	ENDDO

The first transformation, dependence-based register allocation,
is due to Randy Allan and Ken Kennedy.  The 2nd transform,
unrolling to subsume copies, is in Kennedy's thesis (1971).
Both have been implemented at Rice by Steve Carr.

Of course, this is a simple example; but these transformations
(with others of a similar nature) can give tremendous improvements
in real code.

What's the point?  Compilers are getting better.  Humans had to
come up with the original ideas (certainly compiler writers learn
from human coders), but a compiler can apply the ideas repeatedly,
without human effort, to amazingly nastly code.

Regards,
Preston Briggs