tracing turns recursion into loops

Edwin Smith edwsmith at adobe.com
Wed Jan 16 13:23:51 PST 2008


> 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