tracing turns recursion into loops

Edwin Smith edwsmith at adobe.com
Wed Jan 16 12:38:05 PST 2008


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