[CakeML-dev] Tail calls not getting optimized away

[Yong Kiam]

Ah, I guess that's bvi_let. I'll have a look at whether it's actually doing
it.

On Fri, Apr 21, 2017 at 7:37 PM, Magnus Myreen <magnus.myreen at gmail.com>
wrote:

> 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/53b85698/attachment.html>