new Cps optimization -- flattening arrays

Stephen Weeks sweeks@wasabi.epr.com
Tue, 21 Dec 1999 12:19:56 -0800 (PST)


On a completely unrelated note, I did think of another useful
optimization on Cps that can be implemented very easily (< 150 lines).
It doesn't require any analysis -- it is just based on the types.  The
idea is to translate the type ('a * 'b) array to the type 'a array *
'b array.  This can be done by rewriting subscript and update
operations appropriately - sub becomes two subs folled by a tuple,
update becomes a detuple followed by two updates.  There is a clear
win in space, since the indirection for the tuple is now represented
once per array instead of once per array element.  I also suspect it
will be a win in time, since tuples won't have to be consed to be put
in the array.

One other thing that this reminds me of is the fact that Cps isn't
run-time safe.  The problem is bounds checking, which is in fact
performed at a higher level.  That is, the Cps sub and update
operations *don't* do bounds checks.  Thus it is possible for the
optimizer to screw up an operation and access memory out of bounds. I
don't think this is a big deal, but it is a bit annoying.  However, it
does have the nice effect that the scheme described above doesn't
introduce any extra bounds checks.