# [MLton] liveness space problem

Stephen Weeks MLton@mlton.org
Thu, 3 Jun 2004 17:58:30 -0700

```> 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.  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".  Then, for every node n in the tree, there is a
unique cut node c such that c dominates n and for all cut nodes c1 if
c1 dominates n then c1 dominates c.  That is, the cut nodes partition
the nodes in the tree according to the closest dominating cut node.
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.  For
space safety reasons, only deal with variables whose type proves that
the values they can take on are constant size.

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.

How do we choose the cut nodes?

As there are more cut nodes, there is more liveness information to
compute (during this algorithm) and more tuples to introduce into the
program.  So, we want to keep the number of cut nodes small.  However,
we also want to keep the sizes of the partitions small, since large
partitions lead to more liveness information that will be computed

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).

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.

Here's some SML code to clarify what I mean.

functor Cut (structure QuickSort:
sig
val sortVector: 'a vector * ('a * 'a -> bool) -> 'a vector
end
structure Tree:
sig
type t

val children: t -> t vector
val size: t -> int
end
structure Vector:
sig
type 'a t = 'a vector

val fold: 'a t * 'b * ('a * 'b -> 'b) -> 'b
val fromList: 'a list -> 'a t
val sub: 'a t * int -> 'a
end
):
sig
(* Cut returns the list of subtrees rooted at the cut nodes. *)
val cut: Tree.t * {cutoff: int} -> Tree.t list
end =
struct
fun cut (t: Tree.t, {cutoff}): Tree.t list =
let
fun cut (t: Tree.t, ac: Tree.t list): int * Tree.t list =
if Tree.size t <= cutoff
then (Tree.size t, ac)
else
let
(* Cut all the children so they are below the cutoff. *)
val (ts, ac) =
Vector.fold
(Tree.children t, ([], ac), fn (t, (ts, ac)) =>
let
val (n, ac) = cut (t, ac)
in
((t, n) :: ts, ac)
end)
val ts = Vector.fromList ts
val size = Vector.fold (ts, 1, fn ((_, n), ac) => n + ac)
in
if size <= cutoff
then (size, ac)
else
let
(* Sort children in decreasing order of size. *)
val ts =
QuickSort.sortVector (ts, fn ((_, n), (_, n')) =>
n >= n')
fun loop (i, size, ac) =
let
val (t, n) = Vector.sub (ts, i)
val size = size - n
in
if size <= cutoff
then (size, ac)
else
(* Add a tree to ac, i.e. add a cut node. *)
loop (i + 1, size, t :: ac)
end
in
loop (0, size, ac)
end
end
val (_, ac) = cut (t, [])
in
t :: ac
end
end

```