[MLton] liveness space problem

[Matthew Fluet]

> > I'm currently thinking about methods for introducing the tuples and
> > hope to send mail later today with some ideas.
>
> Suppose we have some large function and we would like to cut down on
> its live variable information.

I'm getting confused as to what exactly is the liveness space problem.
That is, why should I believe that any "solution" to the problem that asks
for the set of live variables at a program point doesn't exhibit the same
space blowup?

From where the problem arises, my guess is that the real problem is in the
interference graph used for pseudo-register allocation and computing frame
sizes.

> Consider the dominator tree of the
> control-flow graph for the function.  We will choose (by some method)
> a subset of the nodes in the tree, at least including the root node,
> called "cut nodes".
...
> To transform the function, at each cut node c, allocate a tuple to
> collect all variables that are live at c.  Replace all uses of such
> variables in nodes in c's partition with selects from this tuple.

I understand the analysis and transformation.

> That's the algorithm in a nutshell.  The idea is that allocating the
> tuple at a cut node means that all of the live variable information
> for the variables in the tuple is replaced by a single live variable
> for the tuple.

Again, it depends upon what the actual problem is.  Note that if you do
this transformation in SSA, you actually have _more_ variables than you
started with, because every select induces a variable.  In RSSA, you don't
have to pay that cost, because we can use the Offset operand.

> So, we need an algorithm to take the dominator tree and choose roughly
> equally-sized partitions, keeping them below some threshold (roughly,
> say, 5000 nodes).

We'd also like some additional heuristics, I would think.  For example, we
probably don't want to choose a cut node in a "small" loop.  No sense in
allocating a 100 tuple each time around a List.tabulate.

> Here's one idea.  Prune the tree by repeatedly cutting as large as
> possible subtree smaller than the cutoff.  When a tree node has many
> children, all of which are smaller than the cutoff, but whose sum of
> sizes is larger, simply cut off enough children (starting with the
> largest and working down) until the cutoff for the node is met.

Sounds reasonable.