tracing turns recursion into loops

Zbynek Winkler zbynek.winkler at gmail.com
Wed Jan 16 13:41:38 PST 2008


In deed. I was about to say it's way cool but hot works for me too ;-)

On 16/01/2008, Thomas Reilly <treilly at adobe.com> wrote:
>
> Wow, that's hot.  I almost fell out of my chair ;-)
>
> > -----Original Message-----
> > From: Edwin Smith
> > Sent: Wednesday, January 16, 2008 1:24 PM
> > To: Thomas Reilly; 'tamarin-devel at mozilla.org'
> > Subject: RE: tracing turns recursion into loops
> >
> > > So can a recursive call serve as the start of a tracing loop?
> >
> > yes, thats what the change I just pushed does.
> >
> > > Your stuff works when a recursive function is called from a
> > loop right?
> >
> > before this change, if you were in a loop and called a
> > recursive function, it would try and inline it forever until
> > we either exceeded our stack window, or our trace length.
> > after this change, if you're in a loop and make a recursive
> > call, its treated like being in a loop and taking a back edge
> > to a different loop.  currently that's handled by stopping
> > the trace and patching it over to the trace for the other
> > loop (if it exists).  although if you really had code like
> > that, its more likely the recursive loop would be detected
> > first since it's the inner loop.
> >
> > so if you had:
> >   function recurse() { ... recurse() ... }
> >   for (..)
> >     recurse()
> >
> > the loop structure is more like this:
> >
> >   for (..)
> >      if ..
> >        sp += d
> >      else
> >        sp -= d
> >   }
> >
> > tracing all starts when the interpreter tells the tracer "hey
> > mon, i just took a back edge".  the tracer keeps a counter
> > for the back-edge target (which is just the current PC at
> > that point), and after a threshold, tracer starts recording.
> > This change simply adds a check when the interpreter makes a
> > call, to see if the same call target is already on the call
> > stack.  if so we make an identical call to the tracer: "yo,
> > back edge, mon".  only difference between the two situations
> > is for a normal loop, sp is not loop variant, and for a
> > recursive loop, it is.
> >
> > > Like what would happen for something GCBench where it uses
> > simple recursion to create a huge binary tree with no loops
> > involved, could we handle that?
> >
> > Yup.
> >
> > -----Original Message-----
> > From: Thomas Reilly
> > Sent: Wednesday, January 16, 2008 4:00 PM
> > To: Edwin Smith; 'tamarin-devel at mozilla.org'
> > Subject: RE: tracing turns recursion into loops
> >
> >
> > Okay, this explains why identifying and hoisting loop
> > invariants is so key.   Tracing 101 I guess.  So can a
> > recursive call serve as the start of a tracing loop?   Your
> > stuff works when a recursive function is called from a loop
> > right?  So we trace all the recursive calls for the first
> > iteration and then code gen an inline'd backwards branching
> > replacement for the JIT'd version?  Or do we magically not
> > retrace the recursive function?    Like what would happen for
> > something GCBench where it uses simple recursion to create a
> > huge binary tree with no loops involved, could we handle that?
> >
> > > -----Original Message-----
> > > From: Edwin Smith
> > > Sent: Wednesday, January 16, 2008 12:38 PM
> > > To: Thomas Reilly; 'tamarin-devel at mozilla.org'
> > > Subject: RE: tracing turns recursion into loops
> > >
> > > The stack grows each time through the loop.  So the stack pointer
> > > itself is loop-variant, and therefore anything loaded relative from
> > > the stack pointer (local variables) is also loop variant and not
> > > hoisted.
> > >
> > > If you had parameters being passed along through each iteration,
> > > you'll have a load from sp[i] (the incoming parameter on
> > iteration N),
> > > then a store to sp[i+D] (the outgoing parameter for
> > iteration N+1).
> > > If the stack pointer moves by D each iteration, then you
> > could reason
> > > that the load is no longer loop variant.
> > >
> > > N
> > > ----------
> > > x = load sp0[i]
> > > store sp0[i+d] = x
> > > sp1 = sp0+d
> > >
> > > N+1
> > > ----------
> > > x = load sp1[i]
> > >   = load (sp0+d)[i]
> > >     aliases store sp0[i+d]
> > >   = load sp0[i]
> > >
> > > we don't do this but it sure would be cool if we did.  kind
> > of related
> > > to this bug
> > > https://bugzilla.mozilla.org/show_bug.cgi?id=411183
> > >
> > > and this (especially the part about through a store to the
> > expression
> > > being stored)
> > > http://andreasgal.com/2007/09/08/singleton-allocation-analysis/
> > >
> > > Ed
> > >
> > > -----Original Message-----
> > > From: Thomas Reilly
> > > Sent: Wednesday, January 16, 2008 3:15 PM
> > > To: Edwin Smith; tamarin-devel at mozilla.org
> > > Subject: RE: tracing turns recursion into loops
> > >
> > >
> > > How does it account for the nesting variables?  A normal backwords
> > > branch would just reuse the same space for variables
> > declared in the
> > > loop right but recursion needs to
> > > eat more stack right?   Or do loop variables that are reused
> > > hoisted and in the recursion case those variables just aren't
> > > elligible for hoisting?
> > >
> > > > -----Original Message-----
> > > > From: tamarin-devel-bounces at mozilla.org
> > > > [mailto:tamarin-devel-bounces at mozilla.org] On Behalf Of
> > Edwin Smith
> > > > Sent: Wednesday, January 16, 2008 11:58 AM
> > > > To: tamarin-devel at mozilla.org
> > > > Subject: tracing turns recursion into loops
> > > >
> > > > Howdy,
> > > >
> > > > For those of you following tamarin-tracing, I just pushed
> > > >
> > > > http://hg.mozilla.org/tamarin-tracing/?rev/6e740ae3ea7f
> > > >
> > > > as a fix for
> > > >
> > > > https://bugzilla.mozilla.org/show_bug.cgi?id=411554
> > > >
> > > > The core idea behind tracing is interpreting code until
> > you find a
> > > > frequently taken backwards branch that indicates a loop,
> > > then tracing
> > > > the body of that loop.  Calls could be forwards or backwards, and
> > > > generally you want tracing to inline calls.  But what about
> > > recursion?
> > > > you can bet your bottom you don't want to inline them, and unless
> > > > they're being called from inside a loop, t-t didn't even
> > > detect them.
> > > >
> > > > Ignoring stack motion, we can treat a recursive call as a
> > backwards
> > > > edge, and forward calls as direct jumps.  It just comes down to
> > > > detecting a recursive call vs a regular call.
> > > > This change does it the brute force way, by just walking up
> > > the call
> > > > stack.  If its a recursive call, we just indicate to the
> > > tracer that
> > > > we just took a back edge, and off it goes.  I almost fell
> > out of my
> > > > chair when "just worked" the first time.
> > > >
> > > > controlflow-recursion tests ack(), fib(), and tak(), three common
> > > > recursion tests.  access-binarytrees tests recursively
> > > walking a data
> > > > structure:
> > > >
> > > >                                 before  after
> > > > controlflow-recursive           1219    63
> > > > access-binary-trees             1062    125
> > > >
> > > > Ed
> > > > _______________________________________________
> > > > Tamarin-devel mailing list
> > > > Tamarin-devel at mozilla.org
> > > > https://mail.mozilla.org/listinfo/tamarin-devel
> > > >
> > >
> >
> _______________________________________________
> Tamarin-devel mailing list
> Tamarin-devel at mozilla.org
> https://mail.mozilla.org/listinfo/tamarin-devel
>


-- 
http://robotika.cz/


More information about the Tamarin-devel mailing list