[MLton] liveness space problem
Matthew Fluet
fluet@cs.cornell.edu
Fri, 4 Jun 2004 07:43:54 -0400 (EDT)
> > 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.