SSA backend

[Stephen Weeks]

> However, I'm getting strange errors with this and mllex (and mlyacc).  The
> resulting ssa program type-checks, but register allocation in the backend
> fails.  If you compile with -keep ssa -keep-diag backend and look at
> mllex.backend.diagnostics, you'll see that the liveness analysis computes
> that two variables are live at the beginning of main_0 -- which clearly
> doesn't make sense.  I don't claim that remove-unused.new.fun is
> 100% bug-free, but I also think that an ssa program that type checks
> (i.e., satisfies the SSA condition), shouldn't be generating bogus
> liveness info in the backend.

I figured out much of what's going on.

The control-flow graph used to check the dominator condition and the control-flow
graph used in computing liveness are subtly different.  As a consequence, a
program can satisfy the dominator condition and yet liveness can produce the
weird result you saw.  The difference between the two is for nontail calls with
a handler.  The dominator graph has an edge from the caller to the cont and the
caller to the handler, while the liveness graph has an edge from the caller to
the cont and the cont to the handler.

I don't think this ever would have shown up in the old world, because the
handler inference required a cont to have a particular handler stack.  This is
not the case in the new world (and it's not even being checked now anyways).
The main_0 function of mllex.ssa contains the following CPS functions.

  L_3 ()
    x_10: unit = Stdio_print (global_215)
    L_1022 (exit_0 (global_0, env_0)) handle L_1023
  L_166 ()
    L_1022 (exit_0 (global_12, x_21)) handle L_91
  L_1023 (x_1614: exn)
    L_2 ()
  L_1022 ()
    Bug
  L_91 (x_43: exn)
    SetHandler L_0
    case x_43 of
      Fail_0 => L_116 | SysErr_0 => L_101 | _ => L_100

Notice that the cont L_1022 has both L_1023 and L_91 as handlers.  L_91 has
out_0 live in it and L_1023 does not.  So, the liveness analysis thinks out_0 is
live at the beginning of L_3, but the dominator check does not.

I think that the liveness notion of the control-flow graph is the correct one
and have checked in a change to ssa/type-check.fun that implements this.  Now,
mllex.sml gets a "not in scope" type error.

I would like to understand why remove-unused.new.fun is generating this code and
whether it is a bug or is sensible.  Matthew, can you look into this?

It's now second on my todo list to get SSA checkhandlers working (after getting
the front-end working right with flexrecords).