411554 - TT: detect recursion as a loop backedge and trace recursive loops

Status: VERIFIED FIXED

(Tamarin Graveyard :: Virtual Machine, defect)

Description

[Edwin Smith]

When a function calls itself, even indirectly through some circle in the call graph, count it as a loop iteration and enable tracing the recursive path.

The tracer already can handle stack growth or shrinkage through each loop iteration, but we need an efficient way to identify recursion while interpreting.

one simplistic way is to set a bit in MethodEnv on entry, and clear on exit, and if we call something with its bit set, invoke taken() on the call target which tags the target as a loop header (and maybe starts tracing).  its simplistic because the bit is tied to MethodEnv and there can be more than one env for the same piece of code.

sunspider/controlflow-recursion.as is an obvious example

anything traversing trees recursively is another, include XML trees and UI object layout trees.

Comment 1

[Edwin Smith]

AS3Chess_Headless is recursive too, see AlphaBeta()

Comment 2

[Edwin Smith]

This turned out fairly simple.  In enterabc(), search up the call stack for the same function we're about to enter, and if we find it, call TAKEN() the same way IFTRUE/IFFALSE do for back edges.  the trace engine takes care of the rest.  this essentially transforms recursive functions into loops that explicitly grow or shrink the stack on each iteration.

tests like fib(), ack(), and tak() (all part of controlflow-recursive.as) become loops with branchy bodies that would benefit from trace tree compilation.

Comment 3

[Edwin Smith]

Attachment: Detect recursion as a back edge for tracing purposes.

salient results: 

                                before  after
access-binary-trees             1078    125
controlflow-recursive           1234    62
AS3Chess_Headless               4705    4984   (bigger is better here)

                                t-c     t-t
access-binary-trees             78      125
controlflow-recursive           62      62

Comment 4

[Rick Reitmaier]

Comment on attachment 297375 [details] [diff] [review]
Detect recursion as a back edge for tracing purposes.

Looks like you also cleaned up some of the forth.

Comment 5

[Edwin Smith]

pushed as 
http://hg.mozilla.org/tamarin-tracing/?rev/6e740ae3ea7f

Comment 6

[Edwin Smith]

From SJ:

er, I think you need to add this to interpScript:

        f->next = NULL;

otherwise I tend to crash in -interp mode since the toplevel frame has a next of 0xfbfbfbfb

Comment 7

[Steven Johnson]

I think Rick already checked in a fix for this under a different bug, should this be closed (again)?

Comment 8

[Rick Reitmaier]

i checked in a fix for compiling but not the f->next = NULL , was there also a memset() that needed to be added for macs?

Comment 9

[Steven Johnson]

Hmm, guess I was mistaken. The f->next=NULL is suffificient for this, but I'll push a change with memset() later.

Comment 10

[Edwin Smith]

(In reply to comment #7)
> I think Rick already checked in a fix for this under a different bug, should
> this be closed (again)?
> 

closing again

Comment 11

[Chris Peyer]

Closing out all TT: transfer bugs that are resolved fixed.