[CakeML-dev] Tail calls not getting optimized away

[Yong Kiam]

Ah right, I had in mind that the transformation would still work because
foo isn't mentioned in the loop, I guess that is a bad transformation
because it will require changing the variable indexes.

On Fri, Apr 21, 2017 at 8:02 PM, Ramana Kumar <Ramana.Kumar at cl.cam.ac.uk>
wrote:

> 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/benchma
>>>> rk/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/20170421/65a163d0/attachment.html>