[CakeML-dev] Tail calls not getting optimized away
Yong Kiam
tanyongkiam at gmail.com
Sat Apr 22 00:47:19 UTC 2017
I think it didn't do the tail call properly. This is the relevant stub from
the ; version:
(123,1,
Let
[Let [Op (Const 0) []; Op (Const 0) []; Op (Const 0) []]
(If
(Op (EqualInt 1)
[Op El [Op (Const 1) []; Op (Const 0) []]])
(Call 1 NONE
[Op (Const 0) []; Var 3; Op (Const 0) [];
Op El [Op (Const 0) []; Op (Const 0) []]] NONE)
(Call 0 (SOME 53)
[Op (Const 0) []; Var 3; Op (Const 0) []] NONE))]
(If (Op (TagLenEq 1 0) [Var 0])
* (Let [Call 1 (SOME 119) [Op (Cons 0) []] NONE;
Call 1 (SOME 123) [Let [Op (Const 1) [];
Op (Const 0) []; Op (Const 0) []]
(If (Op (EqualInt 1) [Op El
[Op (Const 1) []; Op (Const 0) []]]) (Call 1
NONE [Op (Const 1) []; Var 4; Op (Const 0)
[]; Op El [Op (Const 0) []; Op (Const 0)
[]]] NONE) (Call 0 (SOME
53) [Op (Const 1) []; Var 4; Op (Const 0)
[]] NONE))] NONE] (Var 1))* (Op (Cons 0) [])))
This is the stub from the let val foo = ... version:
(123,1,
Let
[Let [Op (Const 0) []; Op (Const 0) []; Op (Const 0) []]
(If
(Op (EqualInt 1)
[Op El [Op (Const 1) []; Op (Const 0) []]])
(Call 1 NONE
[Op (Const 0) []; Var 3; Op (Const 0) [];
Op El [Op (Const 0) []; Op (Const 0) []]] NONE)
(Call 0 (SOME 53)
[Op (Const 0) []; Var 3; Op (Const 0) []] NONE))]
(If (Op (TagLenEq 1 0) [Var 0])
*(Let [Call 1 (SOME 119) [Op (Cons 0) []] NONE] (Call 1 (SOME
123) [Let [Op (Const 1) []; Op (Const 0)
[]; Op (Const 0) []] (If (Op
(EqualInt 1) [Op El [Op (Const 1) []; Op (Const 0)
[]]]) (Call 1 NONE [Op
(Const 1) []; Var 5; Op (Const 0) []; Op El [Op
(Const 0) []; Op (Const 0) []]]
NONE) (Call 0 (SOME 53) [Op
(Const 1) []; Var 5; Op (Const 0) []] NONE))]
NONE))* (Op (Cons 0) [])))
In bvl_to_bvi, it seems like bvi_let is only called on Let [] _s that are
behind a marker.
On Fri, Apr 21, 2017 at 8:15 PM, Magnus Myreen <magnus.myreen at gmail.com>
wrote:
> 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
> >>>
> >>
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.cakeml.org/pipermail/developers/attachments/20170421/02e46a5c/attachment-0001.html>
More information about the Developers
mailing list