[CakeML-dev] Tail calls not getting optimized away

[Magnus Myreen]

Hi Yong Kiam,

There is (or was meant to be) a phase around BVL or BVI that aims to turn
Let xs (Var (LENGTH xs - 1)) into the desired code with last of xs moved
into tail position.

Cheers,
Magnus
On Sat, 22 Apr 2017 at 05:48, Yong Kiam <tanyongkiam at gmail.com> wrote:

> 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.
> _______________________________________________
> Developers mailing list
> Developers at cakeml.org
> https://lists.cakeml.org/listinfo/developers
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.cakeml.org/pipermail/developers/attachments/20170421/6216be89/attachment.html>