SSA backend

[Matthew Fluet]

> > Musings... the condition I have in mind is actually even more subtle.  For
> > example, I could imagine transforming the code to the following
> ...
> > This satisfies the cont/handler pair condition, but results in the
> > same scoping or liveness problem.  
> 
> Yep.  I think the right conclusion is that we want to go with the more
> precise dominator and liveness info, and keep them in sync.

So, dominator and liveness in SSA is computed via edges from caller to
continuation and caller to handler.  Liveness in backend needs to take
care of introducing extra blocks if necessary.

> > Here's a thought.  Is it possible to compute the backend liveness
> > information the same way as we compute the SSA liveness information --
> > i.e., do the edge from caller to handler and continuation, not edges from
> > caller to continuation to handler. 
> 
> Yep.  That's what I was referring to when I said "massaging the graph
> that liveness uses".
> 
> > Now, both continuation and handler have a set of live variables.  Is
> > it as simple as unioning these two sets (which should all be
> > refering to stack locations) and using that as the frame layout for
> > a stub that just transfers control to the real continuation label?
> ...
> > The only difference is we need a stub for each cont/handler pair,
> > rather than for each cont.
> 
> I think this is right.  We (at least I) were conflating an occurrence
> of C_2 as a continuation and as a jump target.  I like thinking of
> 
>   C_2(exit_0(...)) handle H_2
> 
> as saying create a *new* continuation that returns to C_2 and handles
> with H_2.  I would like to figure out some way to use the liveness
> algorithm in live.fun to avoid doing the union, though.

That's not that hard.  We have a map 
(Label.t * Label.t option) -> Label.t
which maps each cont/handler pair to some new stub label.
Now, when we build the graph in livenss for a non-tail call, we have edges
from caller to stub, stub to cont, and stub to handler.  So, the stub
should get the union automatically.


I was thinking about this, and there is a completely different
alternative.  The crux of the problem is that we want the label at stack
top to be able to uniquely define the frameLayout.  But, intuitively, that
label is just cont, and so we need to artificially force it to have the
variables live down the handler also live in it's frameLayout.  Is there
particular reasons why the GC doesn't scan the stack like it normally does
for cont's and their frameLayouts, and then scan the stack by looking at
handlers and their frameLayouts.  I guess there is a slight performance
penalty, because you might trace live stack slots twice.  And, maybe the
handler stack isn't as easy to traverse.

> Matthew, if you want to start on this, feel free.  I'm going to be
> busy with the flexrecord and checkhandler stuff for a while longer.

O.k.  Probably not in the next couple of days, but I'll see about getting
to it this weekend.