[MLton] Converting recursive functions to SSA

[Matthew Fluet]

> So, we're almost done (hopefully) with converting the CPS code back into SSA.

"back into SSA"?  It's been my impression from your earlier e-mails that 
you were converting from SXML into CPS; I'd think your job would be 
easiest if you converted from CPS into SXML, although that assumes that 
all of the environment analyses/optimizations that are being effectively 
translated back into SXML.

If you are converting CPS into SSA, then you'll want to follow the 
behavior of mlton/closure-convert/closure-convert.{sig,fun}.

It might help as well if you could point us at your code and/or a diff 
patch.

> We just hit what we think is our last major stumbling block.  How do you handle
> recursive functions when you produce the SSA code?

The semantics of the SSA IL is that all of the functions in an SSA IL 
program are mutually recursive (i.e., an SSA IL program is a giant LetRec 
with a set of global variables and a distinguished (nullary) main 
function).  IIRC, almost every SXML lambda becomes its own SSA function in 
the initial conversion to SSA; subsequent inlining and contification 
optimization passes rapidly get rid of the very small functions and 
functions with determined control flow.

> The problem is, it seems like if we choose the wrong mechanism it
> could break a lot of the intelligence that is built into later stages of the
> compiler, bu producing code that is not in the style that the optimizations have
> been tuned for.

That is a valid concern, which is why it seems that converting from CPS 
back into SXML would be the easiest way to avoid this problem.  Otherwise, 
I suggest you study closure-convert.{sig,fun} and supporting analyses to 
see how we convert an SXML program to SSA.

> That's why we decided to ask and see how you handle compilation
> of recursive functions.  For example, if I had the ML code:
>
> let fun fib (n, a, b) = if n = 0 then a else fib (n - 1, b, a + b)
> in fib (5, 0, 1)
> end
>
> How do I convert this to SSA?

Converting the "let" to a "local" and "fib (5, 0, 1)" to
"val n = fib (5, 0, 1)" and compiling with -keepPass closureConvert, I see 
the following:

Datatypes:
...
lambdas_3 = Env_66 of (unit)
...

Globals:
...
tuple_25 = ()
fib_0 = Env_66 (tuple_25)
...

Main: main_0

Functions:
...
fun main_0 () = L_0 ()
   ...
   L_341 (x_1024)
     x_1026 = Env_100 (tuple_26)
     Ref_assign (x_841, x_1026)
     x_1025 = Env_98 (exit_0)
     Ref_assign (x_844, x_1025)
     case fib_0 of
       Env_66 => L_342
   L_342 (env_103)
     fib_1 (env_103, x_837) NonTail {cont = L_343, handler = Handle L_6}
   ...
fun fib_1 (env_109, x_1037) = L_351 ()
   L_351 ()
     b_0 = #2 x_1037
     a_0 = #1 x_1037
     n_1 = #0 x_1037
     x_1038 = (n_1, x_832)
     case x_11 of
       Env_2 => L_352
   L_352 (env_110)
     x_1039 (env_110, x_1038) NonTail {cont = L_353, handler = Caller}
   L_353 (x_1040)
     case x_1040 of
       true => L_355 | false => L_354
   L_354 ()
     x_1041 = (n_1, x_833)
     case x_72 of
       Env_10 => L_356
   L_356 (env_111)
     x_1042 (env_111, x_1041) NonTail {cont = L_357, handler = Caller}
   L_357 (x_1043)
     x_1044 = (a_0, b_0)
     case x_68 of
       Env_9 => L_358
   L_358 (env_112)
     x_873 (env_112, x_1044) NonTail {cont = L_359, handler = Caller}
   L_359 (x_1045)
     x_1046 = (x_1043, b_0, x_1045)
     case fib_0 of
       Env_66 => L_360
   L_360 (env_113)
     fib_1 (env_113, x_1046) Tail
   L_355 ()
     return a_0
...

So, you can see that fib_1 may freely call itself.

> It's made even more difficult if the function
> being converted has free variables, and is mutually recursive with other
> functions who also have free variables.

I believe that in this case, the environment for each function in the 
mutually recursive set is the union of the free variables in all functions 
in the mutually recursive set.  See 
mlton/closure-convert/lambda-free.{sig,fun}.