tracing turns recursion into loops

Edwin Smith edwsmith at adobe.com
Wed Jan 16 11:57:40 PST 2008


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


More information about the Tamarin-devel mailing list