[MLton] liveness space problem

[Stephen Weeks]

> 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
during the Rssa liveness pass.

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