Friday, August 26, 2011

JaegerMonkey Architecture

JaegerMonkey is a JavaScript engine used in Firefox 4.0 and later versions. The SpiderMonkey JavaScript engine was used by Firefox for version 3.0 or earlier. TraceMonkey is a tracing engine which is an improvement to SpiderMonkey. Trace Monkey was used in Firefox 3.5 and above versions.  Before we will look into architecture of JaegerMonkey, lets first have a glance at TraceMonkey JavaScript engine who is a predecessor of JaegerMonkey.

TraceMonkey Overview
TraceMonkey uses a trace monitor called jstracer. The jstracer monitors a script as interpreted by SpiderMonkey. Whenever jstracer sees a code that would benefit from the native compilation, it activates it recorder. The recorder records the execution of the IR and creates NanoJIT Low Level Intermediate Representation, which is then compiled into native code. NanoJIT produces optimized code. More information on TraceMonkey and its architecture diagram is available  here.

JaegerMonkey Architecture
JaegerMonkey used in Fireox 4.0 and above version is Just-in-Time (JIT) JavaScript execution engine.  JaegerMonkey JIT engine produces native code for JavaScripts. Usually JIT engines take an intermediate representation (IR) from a compiler and produce native (machine) code and execute it on the fly.  Therefore, JIT engines do not parse the code or check its syntax, or create intermediate representation (IR) of code.
Hence, JavaScript engine in Mozilla Firefox we divide into two parts: front-end and back-end. The front-end is responsible to parse the script, check its syntax and generate intermediate representation (IR) of script required for native code generation.  The back-end is responsible for generating native code and memory management.

In Mozilla Firefox front-end is SpiderMonkey which parses script syntax and generates an intermediate representation (IR) of the script. In SpiderMonkey intermediate representation of script is bytecode of the script.  This generated bytecode is then fed to JaegerMonkey JIT engine to be compiled into machine code. JaegerMonkey is a method-base JIT JavaScript engine which compiles script into non-optimized machine code.  JaegerMoneky uses Nitro (borrowed from the WebKit project) as its back-end assembler.  
Nitro does memory management and code generation in JaegerMonkey.

Nitro contains two parts assembler and memory unit. Assembler handles the code assembly and memory unit handles allocation and deallocation of memory for native code. The bulk of the bytecode to native code translation is performed in the mjit::compiler class and it can be found in js/src/methodjit/Compiler.cpp.  This compiler class translates SpiderMonkey bytecode instructions to their native code block equivalents using the AssemblerBuffer and LinkBuffer helper classes.

JaegerMonkey uses inline cache to improve the performance. Inline cache is used to perform faster object type lookups.  JavaScript supports dynamic typing during runtime. To support this feature, in SpiderMonkey JSOP_GETPROP bytecode is responsible to return the value of a specific property by looking up its type first. SpiderMonkey uses property cache which stores the Shape of existing objects.  Shape is a structure in SpiderMonkey that defines how the object can be accessed.

Inline Caching for good locality
When JIT compiles a property access bytecode, emitted machine code look like as follows:


type                     <- load addressof(object) + offsetof(JSObject, type)
shapeIsKnown    <- type equals IMPOSSIBLE_TYPE
None                   <- goto slowLookupCode if shapeIsKnown is False
property              <- load addressof(object) + IMPOSSIBLE_SLOT

JagerMonkey uses self modifying code to inline cache the Shape of the object. Self modifying code is a code that modifies code that currently exists in memory.  When first time JaegerMonkey performs a property access on object its shape is unknown therefore shapeIsKnow will be false.  Hence slowLookupCode will be executed.  After slowLookupCode resolves the property it fills the appropriate value for IMPOSSIBLE_TYPE and IMPOSSIBLE_SLOT.  Hence, next time when this piece of code is executed, if the type of object is not change then shapeIsKnown return true and there is no need to go into slowLookupCode.  This technique of modifying JIT-compiled code to reflect a probable value is called as inline caching: inline, as in "in the emitted code";  caching, as in "cache a probable value".

However, JavaScript supports dynamic typing. This is handles by polymorphic inline caching (PIC).  Lets consider an example of PIC code:

var vals = {1, "hello", [1, 2, 3]};
for (var i in vals) {
   document.write(vals[i].toString());
}

In above code vals array contains different data types such as a Number, a String and a array. For each object in the array, the interpreter has to perform an expressive type lookup and determine the correct toString method to call.  JaegerMonkey uses PIC slots to colve this problem, that is make a chain of cache entries. It creates several blocks of native code that perform property lookups for types the object has already been seen as. It the first type does not match, then a branch is taken to the next code block to perform a lookup. If type is match then it performs a fast slot lookup.  According to our example, first time it recognizes Number object and fills cache entry for it. Second time its a String. So a new piece of code memory is created for type String and modify the jump of first lookup (that is, Number type mismatch in our example) to go to this newly created piece of code memory instead of slowLookupCode.  and so on.

References: