tracing turns recursion into loops

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


For those of you following tamarin-tracing, I just pushed

as a fix for

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

controlflow-recursion tests ack(), fib(), and tak(), three common
recursion tests.  access-binarytrees tests recursively walking a data

                                before  after
controlflow-recursive           1219    63
access-binary-trees             1062    125


More information about the Tamarin-devel mailing list