[CakeML-dev] Tail calls not getting optimized away

Yong Kiam tanyongkiam at gmail.com
Fri Apr 21 21:47:20 UTC 2017


Hi dev,

I'm trying to get this benchmark running: https://raw.githubusercontent.
com/MLton/mlton/master/benchmark/tests/tailfib.sml on a recent build of the
bootstrapped compiler

I ran into this strange scenario:

Writing the loop like the following makes CakeML run out of stack (I think
it fails to optimize the tail call because increasing the stack limit
manually works):

val doit =
  fn n =>
  let
    fun loop n =
      if n = 0
        then ()
        else (doit();loop(n-1))
  in loop (n * 1000000)
  end;

On the other hand, making the ; explicit:

val doit =
  fn n =>
  let
    fun loop n =
      if n = 0
        then ()
        else
*(let val foo = doit() in loop(n-1) end)*  in loop (n * 1000000)
  end;g

works fine.

I checked out the compilation down to patLang, and the only difference
between the two is that the first is compiled to a Seq while the second is
compiled to a Let.

There are actually two things of interest:

1) The ground check in exh_to_pat incorrectly says that *(let val foo =
doit() in loop(n-1) end) *is not ground, and does not compile it to doit()
; loop (n-1)

2) pat_to_clos compiles Seqs to Let [compile e1;compile e2] (Var 1) while
the Lets go to Let [compile e1] (compile e2)

I think the issue is that the tail call detector cannot / does not detect
the first tail call shape.

I'm not sure what the best fix is here, is the multiple-argument Let
compilation of Seq important? If so, I guess the tail call detector in
bvi_to_data should be updated to detect those shapes too.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.cakeml.org/pipermail/developers/attachments/20170421/c191b941/attachment.html>


More information about the Developers mailing list