[CakeML-dev] Tail calls not getting optimized away

[Ramana Kumar]

Regarding point 1, the term is not ground because it has free variables "n"
and "loop" in it.

On 22 April 2017 at 09:42, Yong Kiam <tanyongkiam at gmail.com> wrote:

> 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
>>>
>>
>
> _______________________________________________
> 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/20170422/97477525/attachment-0001.html>