SSA backend

Matthew Fluet Matthew Fluet <fluet@CS.Cornell.EDU>
Tue, 16 Oct 2001 09:14:48 -0400 (EDT)


> I figured out much of what's going on.
...
> 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?

remove-unused.new.fun is generating the code I wanted it to -- it's just a
question of whether or not it is a valid transformation.

>   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

It's a simple analysis to find out that exit_0 never returns, although it
might raise.  So, the original continuations in L_3 and L_166 are really
unused in the sense of being unreachable code.  However, we can't drop the
continuations, because we have no notion of a non-tail call with only a
handler, so I replace the continuations with the L_1022 block, which is
the smallest block that can be used as a continuation; and expresses the
fact that we know think that control can't reach that point.

Do we really need a condition that says that any use of a label as a cont
in a non-tail call must always be paired with the same handler?  I was
actually thinking about this on the way up this morning in relation to the
contification pass.  If we contify a function at a continuation, under SSA
we need to know the handler to rewrite Raise's -- which must mean that
there is only one handler.

I guess this is similar to the CPS condition where every local function
had a known handler stack.  The SSA IL condition is a little weaker, I
guess -- just that every block used as continuation in a non-tail call
must be used with the same handler (or lack of handler) at every non-tail
call.

If this makes sense, then I would have remove-unused.new.fun rewrite the
above to:

   L_3 ()
     x_10: unit = Stdio_print (global_215)
     L_1022a (exit_0 (global_0, env_0)) handle L_1023
   L_166 ()
     L_1022b (exit_0 (global_12, x_21)) handle L_91   
   L_1023 (x_1614: exn)
     L_2 ()
   L_1022a () = L_1022 ()
   L_1022b () = L_1022 ()
   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

Note, this means that the shrinker needs to be aware of that CPS IL
condition, because it can't change occurences of L_1022a to L_1022.

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

O.k.  If the above condition sounds right, it should be checked here.