Which is better: tracking the register allocations or jumping freely in and out of the code.

NanoJIT is developed as a sub-project of the Tamarin ActionScript virtual machine. It is a lightweight JIT compiler, which produces machine code from a Low-level Intermediate Language (called LIR). LIR instructions are inspired by Register Transfer Languages. Furthermore, NanoJIT has already been ported to several architectures like x86, ARM and powerpc. However, SquirellFish Extreme, the JavaScript jit compiler of WebKit has taken another approach.

At the Department, we have some experince with NanoJIT. (There is even a guy here, whom we call King LIR.) The next thing I want to show you is a simple LIR example. It may help you to understand what NanoJIT actually does.

ins0 = IMMEDIATE() [36]
ins1 = IMMEDIATE() [array_address]
ins2 = LOAD(ins1) [mem_offset_1]
ins3 = LOAD(ins1) [mem_offset_2]
ins4 = ADD(ins2, ins3)
ins5 = MUL(ins0, ins4)
       STORE(ins5, ins1) [mem_offset_3]

As you can see, a LIR instruction can depend on constants (immediate values, memory offsets) or on the result of other LIR instructions. The terms 'LIR instruction', and 'result of LIR instruction' refer to the same thing in our context. I will simply use 'instruction' from now on, because it is the shortest form. One can also notice, that physical memory addresses are calculated by adding a base instruction and an immediate offset.

During compilation, NanoJIT tries to keep the frequently used instructions in registers and trace the stack usage. It works efficiently if there aren't any back-edges. (Backward jumps, in other words. They are mainly used by loops.) In the past, NanoJIT was a tracing JIT, and the support of back edges has only been added recently. Unfortunately, NanoJIT performs poorly in the presence of back edges. A better register allocation algorithm might reduce the number of unnecessary stack stores and loads after a back-edge.

Now, let's turn our attention to JavaScriptCore. Its register allocation mechanism is much simpler, so to say. OK, there is no mechanism at all. The registers are simply divided into two groups: fixed registers and temporary registers. Fixed registers contain important values, like CallFrame pointer (which is the stack frame pointer for JavaScriptCore). Temporary registers are used during the hand-coded implementation of individual SquirrelFish instructions (a middle-level representation of a JavaScript source, generated from the Abstract Syntax Tree). Therefore, you can freely jump to the begining of any SquirrelFish instructions, which makes the generation of selection statements, loop staments and exception handling rather easy. In short: the intra-instruction optimizations are done by hand, and there is no inter-instruction (block or procedure-level) optimization.

I have to admit, that was a long read. If you are still with me, I can get to the point at last. The question is: which one is the better? NanoJIT or SquirellFish Extreme? As you can guess, we have started implementing the SquirrelFish instructions in LIR. The project was going well. As soon as it was worth to compare the two approaches (about 60% of the SquirrelFish instructions were implemented), we did measurements on an x86-based desktop system. It turned out that SquirrelFish Extreme of JavaScriptCore performed better. The typical results were the following: let A the runtime measured by SquirrelFish Extreme for a specific JavaScript, and B the runtime measured by the SquirrelFish interpereter (B > A). NanoJIT runtime was about (A + (B - A) / 3) in most of the cases, sometimes it was even slower. After some time, we decided to abandon this project, thus it got never finnished: the results were not promising.

Well, if someone is still interested in the continuation of this work, just let us know.

dido (not verified) - 12/11/2009 - 15:47

Very good post, thanks a lot.

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • No HTML tags allowed
  • Lines and paragraphs break automatically.

More information about formatting options

This question is for testing whether you are a human visitor and to prevent automated spam submissions.
Fill in the blank