tracing turns recursion into loops

Thomas Reilly treilly at adobe.com
Wed Jan 16 12:14:43 PST 2008


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