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.
