[MLton] flattening, via prefetching

[Lukasz S Ziarek]

As promised this is a short write up about my algorithm to flatten
arbitrary nested tuples:

The idea behind the algorithm is prefetching. Whenever a tuple is
introduced, we keep around both representations: a flat and non flat. For
arguments to blocks and to functions, if they are marked as flat we
recursively flatten them and then emit all coercion statements. Thus we
have a flat and non flat representations of the tuple. For arguments that
are marked as non flat, we recursively emit selects. Once again we have
both the flat and non flat representations of the tuple. For nested tuples
it is important to note that for each nesting depth we also have the flat
and non flat representation. In any block, statements Var, Select, Tuple,
introduce new tuples, though they are composed of vars and other tuples
that would have already been flattened. By keeping track of our
prefetching information we can simplify these statements based on their
labeling. New variables may be introduced, and similarly to arguments we
emit statements building back up the structure of flattened tuples. We do
not need to emit selects at this point.

Example:

Var x = Var y   (both labeled as NF)

All that needs to be done here is that the prefetch information of x is
set to the prefetch information of y.

Example 2:

Var x = Tuple (x1, ...., xn) (var is labeled as NF)

All that needs to be done in this case is to set the prefetch information
of x to (x1,....,xn).

ConApps and PrimApps, however, are different. Both can emit a tuple whose
structure is not held in previously generated prefetch data. We must also
note that ConApps and PrimApps will both always be marked as NF. We must
emit prefetch information for both ConApps and PrimApps when we come
across them in a program. Therefore, we emit selects. This will preserve
our invariant that in all places of a program we have access to the tuple
as flat and as non flat.

Datatypes are flattened down as far as their type structure permits. We
can safely do this, because at any point we have access to a tuples flat
and non flat representations.  Therefore, when we apply a constructor to a
set of args, all we need to do is recursively find the flat representation
of all the tuples (this is for the flatten all case, for other labelings
this will require more work). When we see a ConApp we recursively find all
the flat prefetch information for the args.


Transfers and Returns are thus very simple. We do not need to do anything
interesting here. We simply check what representation of the tuple we need
to pass along.

If anyone has any questions, or if I was not clear in my explenation,
please ask and I will try to answers them asap.


Current limitations:

PrimApps, if I emit selects for these none of the benchmarks work. If I
omit the selects 1/2 the benchmarks work, the others ofcourse do not
because the invariant of having both the flat and non flat representations
no longer holds.