On 2011-05-13, at 11:17 AM, Marc Feeley wrote:

I have completed a prototype implementation of the code patching mechanism that I have been thinking of these past few days. I won't explain it in this email because it is best to use a drawing to understand how it works. I'm attaching the source code and assembly code for 2 tests I tried. I compared the execution time against spidermonkey and the code is about 2.6 times faster than spidermonkey. It is roughly 30 times faster than Tachyon. Surprisingly, test2 is 20 times faster than V8.

Maxime and Erick, we can talk about it this afternoon.

Marc

Here are a few explanations on the code. There are 3 handlers for the following operations on global properties:

- put global property - get global property - jump to global property

The "jump to global property" handler will get the global property, check that it is a function, patch the code (the "jump to global property" is replaced by a direct jump instruction to the function entry), and finally the "jump to global property" handler jumps to the function. A list of the patched locations is kept in the global object. It points to the last patched location. At the patched location is a pointer to the next patched location.

The "put global property" handler will change the global property and deoptimize the patched locations. Each patched location is deoptimized to the original code that calls the "jump to global property" handler.

There are two levels of optimization of jumps to global properties. The basic optimization retains the argument count setup and the argument count check in the function. However, if the "jump to global property" handler detects that the argument count matches the parameter count of the function, then the argument count setup and the argument count check are avoided.

To understand the details of the code patching, it is necessary to look at how the machine instructions are encoded. It is simpler if the code at the entry of functions, and at function call sites have a consistent pattern over all functions and call sites. Here are the patterns I have used.

The x86 code of the function f has the pattern:

f: 80 E9 nn subb $n,%cl 0F 85 xx xx xx xx jne f_arg_count_mismatch f_body: ...body of f

f_arg_count_mismatch: ...handle mismatch of nb args and nb parameters E9 yy yy yy yy jmp f_body # continue with body

The important point is that the argument count check can be skipped by jumping to 9 bytes past the main entry point of the function (i.e. f_body = f+9).

The call

f(...)

where f is a global property, becomes the x86 code:

BF rr rr rr rr movl $r,%edi # edi <- r = return point B1 nn movb $n,%cl # cl <- n = argument count 68 ss ss ss ss pushl $s # s = JS string "f" E8 jj jj jj jj call jump_global_prop # call jump handler

mm mm mm mm .long gc_map # GC map of return point r: ...code at return point

Note that the handler is called with a "call" instruction. This is convenient because the jump_global_prop handler can recover the address of the location to patch by popping the return address from the stack (the handler does not return to the caller). So the layout of the code is:

BF rr rr rr rr B1 nn 68 ss ss ss ss E8 jj jj jj jj mm mm mm mm ... ^ | return address points here

When the "jump to global property" handler determines that it is OK to patch the code, and that the argument count setup/check must be preserved, it will overwrite the code to get this sequence:

BF rr rr rr rr B1 nn E9 xx xx xx xx E8 yy yy yy yy mm mm mm mm ... ^ | patched location list of f points here

The opcode E9 is for a direct jump, and x is the (relative) address of f, and y is the address of the next patched location. The opcode E8 is left over from the original code, but it is not used anymore.

If the handler had determined that the argument count setup/check can be avoided, it will overwrite the code to get this sequence:

BF rr rr rr rr E9 zz zz zz zz ss ss E8 yy yy yy yy mm mm mm mm ...

Here z is the (relative) address of f_body (i.e. f+9).

Either way, when the "put global property" handler is called, these patched locations are deoptimized to the original code sequence, i.e.

BF rr rr rr rr B1 nn 68 ss ss ss ss E8 jj jj jj jj mm mm mm mm ...

So the next time the jump is performed, the "jump to global property" handler will check and perform the optimizations if possible with the new value.

Marc