SSA backend

[Matthew Fluet]

> > Could you put those in the exceptions paper directory?  I'd just like to
> > make sure I've got a good feel for exactly what we want the semantics of
> > the exceptions to be.
> 
> It's #3 on my todo after (#1) getting flexrecords working properly and
> (#2) testing out Ssa.Function.checkHandlers.  Would you like me to
> move it to #2?

If they were typed up, I'd say just drop them in there; I don't care how
readable they are.  Otherwise, leave the todo as is.  At worst, I'll
figure it out from looking at Ssa.Function.checkHandlers.

> > O.k.  This makes the contification marginally more complicated if we don't
> > impose the cont/handler pairing condition.  Essentially, the notion of
> > place in "function returns to only one place" is not just cont's, it is
> > cont/handler pairs.  I think everything in the safety conditions, analysis
> > and transformations goes through if we just use cont/handler pairs
> > wherever we were using conts.
> 
> > The implementation of the analysis get's a
> > little harder, but not too bad.  For all the nice property list stuff, we
> > need a Label.t * Label.t -> PropertyList.t function.  I guess a
> > hash-table (since Label.t's are HashId's).
> 
> I'd probably go for property on conts with an alist for the exception
> piece, but who knows ... linear is scary.  The interesting thing is
> that we wouldn't need this if we imposed the condition -- does that
> mean that this cost would be shifted somewhere else, like the
> shrinker?

Well, some cost would be shifted to different places.  If it is a strict
condition, then I would expect the type-checker to check it.  In the
type-checker, it's not bad -- we just have a Label.t option option on each
Label.t; when we see a non-tail call with continuation l, we record the
handler; next time we see l used as a continuation, either the handler
matches and we're happy or it doesn't match and we raise an error.

The shrinker would have some burden -- it's got to make sure that it
doesn't produce a program that violates that condition; or it takes a
program that does violate that condition and fixes it.


Musings... the condition I have in mind is actually even more subtle.  For
example, I could imagine transforming the code to the following

L_1()
  C_1(exit_0(...)) handle H_1
L_2()
  C_2(exit_0(...)) handle H_2
C_1 ()
  C_2()
H_1 ()
  ... nothing live ...
C_2 ()
  Bug
H_2 ()
  ... something live ...

This satisfies the cont/handler pair condition, but results in the
same scoping or liveness problem.  

> > The condition is there because of implementation decisions.  We need a way
> > of passing roots to the GC, and we accomplish that by having the
> > frameLayouts of the continuation label indicate the live roots of the
> > corresponding handler.  Other implementations might not require that.  I'm
> > happy with leaving less conditions on the SSA IL.
> 
> Agreed.  This reminds me though, if we go this way, we need to change
> dominators back to the way it was and fix the backend liveness
> computation to match that.  Namely, the variables that are live in a
> continuation due to a handler should not be propagated to calls with
> that continuation.  I think this can be fixed by massaging the graph
> that liveness uses.

O.k.

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.  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?  Note, this isn't that dissimilar from what is really
going on in backend; we create this stub to copy returned values and
adjust stack top.  (Yes, maybe the copy of returned values will go away
with the new ideas for non-tail call conventions.)  The only difference is
we need a stub for each cont/handler pair, rather than for each cont.