tracing turns recursion into loops

Haghighat, Mohammad R mohammad.r.haghighat at intel.com
Thu Jan 17 09:18:27 PST 2008


One advanatge of SIMD vector code, which is particulary important here,
is its code denisty and thus small memory foot print. That is, _if_
there are such opportunities, with one instruction we'd be able to
manipulate a lot of data, and BTW it is much faster. But in dynamic
languages with late binding, existence of this opportunity is
questionable. On the other hand, specialization that is provided by
traces may enable this. There are other complexities such as data
alignment requiremenrs (and adjustments if necessary) that might require
more code. I guess, we'll look at your typical traces and figure this
out. 

- moh

-----Original Message-----
From: Edwin Smith [mailto:edwsmith at adobe.com] 
Sent: Thursday, January 17, 2008 9:09 AM
To: Haghighat, Mohammad R; tamarin-devel at mozilla.org
Subject: RE: tracing turns recursion into loops

I doubt that the majority of JS code out there is going to have much in
the way of vectorizable loops, but the faster the impl's get, the more
people will use them for computation.  in flash 9 for example people are
writing particle systems and pixel-level effects in actionscript.  so...
yes.

yes, there are probably a couple different approaches to consider, not
necessarily mutually exclusive either

* the intermediate code for a trace (LIR) is in SSA form, so it should
be possible to find instruction-level parallelism to fit into SIMD
instructions.  any code processing pixels in actionscript could
potentially benefit.  crypto code might not, by its very nature cryphers
have long dependency chains right?  at least looking at md5.

* loop unrolling ought to be easy with tracing... when you hit the
bottom of the loop, just don't stop tracing, instead go around again.
the trace is twice as long.  or 3x etc.  with that, a loop with no data
dependencies between iterations could be vectorized.  each instruction
from the 1st iteration should have a peer in the second iteration thats
a candidate for being put into a simd instruction.  we'd want a
heuristic to choose which loops are candidates for unrolling, and how
many times.  

Any loop worthy of being vectorized will use Array, or Vector<t>, and so
its important to expose array access for what it is.  when using Array,
the actual loading and storing to memory, is buried behind a couple
layers of API.  In both tamarin's, arrays have a dense portion and
sparse portion.  In tamarin-tracing weve written array accessors in
Actionscript so they can be traced.  A goal is to expose the load/store
access to the dense portion of arrays.

I'm sure I cannot do justice to the general problem of loop
vectorization, maybe the take away is that in general, compiler
algorithms tend to be easier to apply to traces than to general CFG's
because a trace is a single superblock.

Ed

-----Original Message-----
From: Haghighat, Mohammad R [mailto:mohammad.r.haghighat at intel.com] 
Sent: Thursday, January 17, 2008 12:37 AM
To: Edwin Smith; tamarin-devel at mozilla.org
Subject: RE: tracing turns recursion into loops


Ed,

In the inlined loop traces do you see any opportunities for
vectorization?  

- moh

-----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 1:24 PM
To: Thomas Reilly; tamarin-devel at mozilla.org
Subject: RE: tracing turns recursion into loops

> So can a recursive call serve as the start of a tracing loop?

yes, thats what the change I just pushed does.  

> Your stuff works when a recursive function is called from a loop
right?

before this change, if you were in a loop and called a recursive
function, it would try and inline it forever until we either exceeded
our stack window, or our trace length.  after this change, if you're in
a loop and make a recursive call, its treated like being in a loop and
taking a back edge to a different loop.  currently that's handled by
stopping the trace and patching it over to the trace for the other loop
(if it exists).  although if you really had code like that, its more
likely the recursive loop would be detected first since it's the inner
loop.

so if you had:
  function recurse() { ... recurse() ... }
  for (..)
    recurse()

the loop structure is more like this:

  for (..)
     if ..
       sp += d
     else
       sp -= d
  }

tracing all starts when the interpreter tells the tracer "hey mon, i
just took a back edge".  the tracer keeps a counter for the back-edge
target (which is just the current PC at that point), and after a
threshold, tracer starts recording.  This change simply adds a check
when the interpreter makes a call, to see if the same call target is
already on the call stack.  if so we make an identical call to the
tracer: "yo, back edge, mon".  only difference between the two
situations is for a normal loop, sp is not loop variant, and for a
recursive loop, it is.

> Like what would happen for something GCBench where it uses simple
recursion to create a huge binary tree with no loops involved, could we
handle that?

Yup.

-----Original Message-----
From: Thomas Reilly
Sent: Wednesday, January 16, 2008 4:00 PM
To: Edwin Smith; 'tamarin-devel at mozilla.org'
Subject: RE: tracing turns recursion into loops


Okay, this explains why identifying and hoisting loop invariants is so
key.   Tracing 101 I guess.  So can a recursive call serve as the start
of a tracing loop?   Your stuff works when a recursive function is
called from a loop right?  So we trace all the recursive calls for the
first iteration and then code gen an inline'd backwards branching
replacement for the JIT'd version?  Or do we magically not retrace the
recursive function?    Like what would happen for something GCBench
where it uses simple recursion to create a huge binary tree with no
loops involved, could we handle that?  

> -----Original Message-----
> From: Edwin Smith
> Sent: Wednesday, January 16, 2008 12:38 PM
> To: Thomas Reilly; 'tamarin-devel at mozilla.org'
> Subject: RE: tracing turns recursion into loops
> 
> 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
> > 
> 
_______________________________________________
Tamarin-devel mailing list
Tamarin-devel at mozilla.org
https://mail.mozilla.org/listinfo/tamarin-devel


More information about the Tamarin-devel mailing list