Bluish Coder

Programming Languages, Martials Arts and Computers. The Weblog of Chris Double.


2008-05-20

A Quick Introduction to Tamarin Tracing

2008-05-20: Fixed some breakage due to changes to the latest Tamarin Tracing source, and updated more recent timing.

I attended the Tamarin Tech summit at Adobe on Friday. My main interest for attending was to learn more about the tamarin-tracing project. The goal of Tamarin is to produce a high performance ECMAScript 4 implementation.

'Tamarin Tracing' is an implementation that uses a 'tracing jit'. This type of 'just in time compiler' traces code executing during hotspots and compiles it so when those hotspots are entered again the compiled code is run instead. It traces each statement executed, including within other function calls, and this entire execution path is compiled. This is different from compiling individual functions. You can gain more information for the optimizer to operate on, and remove some of the overhead of the calls. Anytime the compiled code makes a call to code that has not been jitted, the interpreter is called to continue.

Apparently the JIT for Lua is also being written using a tracing jit method and a post by Mike Pall describes the approach they are taking in some detail and lists references. A followup post provides more information and mentions Tamarin Tracing.

'Tamarin Tracing' is open source and can be obtained from the mercurial repository:

$ hg clone http://hg.mozilla.org/tamarin-tracing/

To build the source you create a directory to hold the build files, change to it, and run the configure script:

$ $ mkdir mybuild
$ cd mybuild
$ ../tamarin-tracing/configure --enable-shell
$ make

The 'enable-shell' option is required to produce the 'avmshell' binary that executes the bytecode. At the end of the build you'll see the avmshell binary in the shell subdirectory:

$ shell/avmshell
avmplus shell 1.0 build cyclone

usage: avmplus [options] scripts [--] script args
          -Dtimeout            enforce maximum 15 seconds 
                               execution
          -error               crash opens debug dialog, 
                               instead of dumping
          -suppress_stdout     don't emit anything to 
                               stdout (debug messages only)
          -interp              disable the trace optimizer 
                               and nanojit
          -Dnoloops            disable loop invariant hoisting
          -Dnocse              disable common subexpression 
                               elimination
          -Dnosse              disable SSE2 instructions
          -log                 send verbose output to 
                               <script>.log

'avmshell' operates on files containing bytecode not JavaScript. To use it you'll need to have a front end that compiles JavaScript to the 'abc' bytecode format it uses. The bytecode is the ActionScript bytecode. You'll need a compiler that generates this. This can be obtained from the Flex SDK. This is a free download from Adobe. You can also use any other tool that generates the correct bytecode.

Included with Tamarin Tracing is the source for 'esc'. This is a work-in-progress implementation of an ECMAScript 4 compiler written in ECMAScript. It generates the 'abc' bytecode but is (I think) not quite ready for prime time. In this post I'm using the 'asc' compiler from the Flex 2 SDK on Linux. This compiler is written in Java and is in the 'lib/asc.jar' file in the SDK.

A quick test that the avmshell program works:

$ echo "print('hello world!');" >>hello.as
$ java -jar asc.jar hello.as
hello.abc, 86 bytes written
$ shell/avmshell hello.abc
hello world!

'avmshell' has a number of debugging options that are only available when configuring the build with '--enable-debugger'. This allows you to get some information about the trace jit. Here's the build process with a debug enabled build and the available options:

$ mkdir mybuild
$ cd mybuild
$ ../tamarin-tracing/configure --enable-shell --enable-debugger
$ make
$ shell/avmshell
avmplus shell 1.0 build cyclone

usage: avmplus [options] scripts [--] script args
          -d                   enter debugger on start
          -Dnogc               don't collect
          -Dgcstats            generate statistics on gc
          -Dnoincgc            don't use incremental collection
          -Dastrace N          display AS execution information, 
                               where N is [1..4]
          -Dverbose            trace every instruction (verbose!)
          -Dverbose_init       trace builtins too
          -Dverbose_opt_exits  trace optimizer exit instructions
          -Dverbose_opt_detail extreme optimizer verbosity 
          -Dquiet_opt          disable verbosity for optimizer
          -Dstats              display various optimizer 
                               statistics 
          -Dsuperwords         dump basic block usage to stderr 
                               (use with -interp; 
                                2> to save to file, then 
                                superwords.py) 
          -Dtimeout            enforce maximum 15 seconds 
                               execution
          -error               crash opens debug dialog, instead of 
                               dumping
          -suppress_stdout     don't emit anything to stdout 
                               (debug messages only)
          -interp              disable the trace optimizer and 
                               nanojit
          -Dnoloops            disable loop invariant hoisting
          -Dnocse              disable common subexpression 
                               elimination
          -Dnosse              disable SSE2 instructions
          -log                 send verbose output to 
                               <script>.log

To demonstrate some of the output I'll use a simple fibonacci benchmark. This is the contents of fib.as:

function fib(n) {
 if(n <= 1)
  return 1;
 else
  return fib(n-1) + fib(n-2);
}

print("fib 30 = " + fib(30));

A comparison of times with and without the tracing jit enabled:

$ time ./shell/avmshell -interp fib.abc
fib 30 = 1346269

real    0m7.550s
user    0m7.504s
sys     0m0.004s
$ time ./shell/avmshell fib.abc
fib 30 = 1346269

real    0m0.391s
user    0m0.360s
sys     0m0.016s

A complete verbose log is very large and shows the execution of the program, the trace and the assembly code generated:

$ shell/avmshell -Dverbose fib.abc
...
  interp global$init()
  0:getlocal0
  1:pushscope ( global@20c1e61 )
  2:newfunction method_id=0 
  4:getglobalscope
  5:swap ( Function-0 global@20c1e61 )
  6:setslot 1 ( global@20c1e61 Function-0 )
 ...
 interp ()
  0:getlocal1
  1:pushbyte 1
  3:ifnle 10 ( 30 1 )
  10:getglobalscope
  11:nop
  12:getlocal1
  13:pushbyte 1
  15:subtract ( 30 1 )
  16:callproperty {public,fib.as$0}::fib 1 ( global@20c1e61 29 )
...
 10:getglobalscope
  11:nop
  12:getlocal1
  13:pushbyte 1
  15:subtract ( 28 1 )
  16:callproperty {public,fib.as$0}::fib 1 ( global@20c1e61 27 )
  interp ()
SOT  pc 107D148 ip D9DD5 sp 10100FC rp 10082E4
         trace 4314 (10DA000)
       1 in    ecx
       3 int   #20D8940
       4 arg   3
       5 arg   1
       6 call  fragenter
         reference to rp
       7 imm   #16
       8 ld    7(1)
...
   GG: pc 107D148 ip D9DD5 sp 101010C rp 100832C
 assembling pass 1 from 4311:62
       1 in    ecx
         010DF786  mov ecx,-4(ebp)                  ecx(1)
       3 int   #20D8940
       4 arg   3
         010DF789  mov edx,34441536                 ecx(1)
       5 arg   1
       6-call  fragenter
         010DF78E  call 2E96E:fragenter                
         010DF793  mov ecx,-4(ebp)                  ecx(1)
       7 imm   #16
       8-ld    7(1)
         010DF796  mov edi,16(ecx)                  ecx(1)
         010DF799  mov -12(ebp),edi                 ecx(1) edi(8)
 ...

There's a lot of other interesting stuff in the Tamarin Tracing source that I hope to dive into. For example:

  • the interpreter is written in Forth. There are .fs files in the 'core' subdirectory that contains the Forth source code. Each 'abc' bytecode is implemented in lower level instructions which are implemented in Forth. The tracing jit operates on these lower level instructions. The system can be extended with Forth code to call native C functions. The compiler from Forth to C++ is written in Python and is in 'utils/fc.py'
  • The jit has two backends. One for Intel x86 32 bit, and the other for ARM. See the 'nanojit' subdirectory.
  • The complete interpreter source can be rebuilt from the Forth using 'core/builtin.py'. This requires 'asc.jar' to be placed in the 'utils' subdirectory of Tamarin Tracing.

At the summit there was an in-depth session of the internals of the Forth code and how to extend it. I'll write more about that later when/if I get a chance to dig into it.

Tags


This site is accessable over tor as hidden service mh7mkfvezts5j6yu.onion, or Freenet using key:
USK@1ORdIvjL2H1bZblJcP8hu2LjjKtVB-rVzp8mLty~5N4,8hL85otZBbq0geDsSKkBK4sKESL2SrNVecFZz9NxGVQ,AQACAAE/bluishcoder/-30/


Tags

Archives
Links