[MLton] array flattening

[Stephen Weeks]

I'm planning on adding an SSA(2) optimization to flatten arrays, so
that, e.g., an "(int * int) array" can be represented with two words
per element, instead of one word pointing to a three word object as we
do now.  The plan is to change the Array type constructor in SSA so
that it is n-ary instead of unary.  For the optimization, the idea is
similar to how we flatten arguments to functions: flatten an array if
the tuple is explicitly constructed at all places where an element is
assigned.  That's all straightforward.

What I am undecided on is how to express array sub and update in SSA,
RSSA, and Machine.

Currently in SSA, sub and update look like:

	t = Array_sub (a, i)
	y = #1 t
	z = #2 t

	t = (y, z)
	Array_udpate (a, i, t)

With array elements holding "flattened" tuples, I see two possible
generalizations.

1. Add an extra "offset" field to sub and update to specify the offset
within the array element.

	y = Array_sub (a, i, #1)
	z = Array_sub (a, i, #2)
	
	Array_update (a, i, #1, y)
	Array_update (a, i, #2, z)

2. Use internal pointers, express the computation of the address of
the internal element, and express the computation of the offset from
that internal pointer.

	p = Array_offset (a, i)
	y = Pointer_sub (p, 0)
	z = Pointer_sub (p, 1)

	p = Array_offset (a, i)
	Pointer_update (p, 0, y)
	Pointer_update (p, 1, z)


As for RSSA and Machine, we have the ArrayOffset and Offset operands

      structure Operand:
	 sig
	    datatype t =
	       ArrayOffset of {base: t,
			       index: t,
			       ty: Type.t}
	     | Offset of {base: t,
			  offset: Bytes.t,
			  ty: Type.t}
            ...

Array subscript and update simply use ArrayOffset on the left-hand or
right-hand side of a Move:

	t = ArrayOffset {base = a, index = i, ...}
	y = Offset {base = t, index = 0}
	z = Offset {base = t, index = 4}

	t = Object ...
	ArrayOffset {base = a, index = i, ...} = t


Overall, I'm pretty nervous about the thought of adding internal
pointers to SSA (how do you type them, how do you get GC right, etc.),
so my gut feeling is that the right thing is to include the element
offset in subscript and update in SSA (choice 1), despite its implicit
repeated computation of the element address.  Then, for a first cut,
the translation to RSSA can just do the address computation explicitly
if needed, or use ArrayOffset if the element offset is 0 (as will be
the case for unflattened arrays, or the first component of a flattened
array element).  Later, I can add a little bit of common-subexpression
elimination to the translation or to RSSA so that repeated offsets
from the same element share the same computation of the element
address.

With this approach, there are no changes to the RSSA or Machine ILs.

Any thoughts?  Matthew, I am particularly interested to know if you
see any problems this could cause the native codegen, or if another
approach would be better.

BTW, there was a related thread that came up a couple of years ago
when I needed to express array address computations for card marking.

	http://www.mlton.org/pipermail/mlton/2002-July/012586.html

In that situation, we needed to use an array element address to
compute the right card to update and to store the new value.  Our
final solution was similar to what I propose here -- to compute the
address explicitly in RSSA with a couple of word ops, and then to use
Offset to access the value.