tracing turns recursion into loops

Thomas Reilly treilly at adobe.com
Wed Jan 16 13:33:56 PST 2008


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
> > > 
> > 
> 


More information about the Tamarin-devel mailing list