[MLton] liveness space problem

[Stephen Weeks]

> 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?

Because the problem is not computing the set of live variables at a
particular program point, the problem is computing (and representing)
the set of live variables at *every* program point.  The solution I
proposed only has to compute the set of live variables at the cut
nodes, and there are only a few of those.  Computing the set of live
variables at a set of nodes takes time proportional to the size of the
program plus the size of the output.  Since the output will only be
the lives at the cut nodes, this should be fine.

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

I don't see this.  Pseudo-register allocation does its work one basic
block at a time.  There is no whole-procedure interference graph.

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

True, but those select variables are never live across a basic block,
so they don't cost any extra space during the 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).
> 
> 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.

Yeah.  We could use loop forests to address this.  We do use them
elsewhere, but I'm still a little nervous about their (potentially)
quadratic time.

Also, if we don't contify into main, which is now the default, then
maybe this isn't a problem.  It seems like loops can only come from
threads (?).