[CakeML-dev] Tail calls not getting optimized away

[Magnus Myreen]

Hmm, bvi_let ought to move it into tail position. It changes the
variable lookups to match the new position. There must be something
that mangles the Let [..; ..] (Var 1) on the way from patLang to BVI.
-- Magnus

On 22 April 2017 at 02:08, Yong Kiam <tanyongkiam at gmail.com> wrote:
> 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/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
>>>
>>
>