This weekend I improved my prototype compiler which compiles JS to x86, using the global property jump optimization. The compiler is rather minimal and handles just enough to compile fib and similar simple code.
This prototype is mainly useful to explore various implementation approaches quickly, without the burden of the complete Tachyon compiler. It allowed me to test the performance of the global property jump optimization I proposed. Two versions were tested:
proto1 = optimization of global property calls keeping the argument count setup and check in all cases
proto2 = optimization of global property calls without the argument count setup and check when the number of parameters matches the number of arguments
The results are very good. On fib(40), proto2 generate faster code than V8 (1.5x) and SpiderMonkey (2.3x), and Tachyon (18x). There is a 1.2x difference between proto1 and proto2 (in other words, there is a 20% overhead to setup and check argument counts). Here are the detailed running times:
relative time to proto2 Tachyon 29.613 (18.3) SM 3.700 ( 2.3) V8 2.397 ( 1.5) proto1 2.000 ( 1.2) proto2 1.614 ( 1.0)
Please examine the x86 code generated by proto2. Note that it performs all the expected dynamic type checks, and also the stack overflow checks. The optimization in proto2 will replace the code of the global property jump:
call jump_global_prop_handler # perform jump to global property .long 3 # fib .byte 1,0 # number of arguments and filler
with the direct jump:
jmp fib_7
The details are in the attached file. If you have any questions please let me know.
Here's a question for Maxime and Erick... can you estimate the work needed to get Tachyon to generate similar x86 code?
Marc
# notes: # # %ecx = context register # %eax = argument 1 of function and return value of function # %edi = return address # %ebp = stack pointer # # function fib(x) # { # if (x < 2) # return x; # else # return fib(x-1) + fib(x-2); # }
fib_7: # main entry point of "fib"
subb $1,%cl # check that arg_count = 1 jne _13
_14: testb $3,%al # check that x is a fixnum jne _17
cmpl $8,%eax # compare it to 2 jge else_16
then_15: jmp *%edi # return x (which is already in %eax) when x<2
_13: addb $1,%cl # handle arg_count != param_count pushl %ecx xorb %cl,%cl call *16(%ecx) jmp _14
_17: pushl %eax # handle generic "x < 2" pushl $8 call *28(%ecx) jl then_15 jmp else_16
else_16: movl %eax,-4(%ebp) # save x for later
testb $3,%al # check that x is a fixnum jne _19
subl $8,%eax # "x - 2" jo _20 # check for overflow
_21: # no overflow movl %edi,-8(%ebp) # save return address on stack
addl $-8,%ebp # allocate frame on stack
cmpl %ebp,(%ecx) # check for stack overflow ja _22
_23: # jump to global property "fib" movl $_18,%edi # setup return address movl 4(%ecx),%esi # setup "this" argument (= global object)
call jump_global_prop_handler # perform jump to global property .long 3 # fib .byte 1,0 # number of arguments and filler
_20: addl $8,%eax # undo subtraction that overflowed _19: pushl %eax # handle generic "x - 2" pushl $8 call *28(%ecx) jmp _21
_22: call *12(%ecx) # handle stack overflow jmp _23
ALIGN_RET_POINT FRAME_DESCR .long RET_POINT_TYPE RET_POINT_HEADER_END
_18: # return point of call fib(x-2)
movl 4(%ebp),%ebx # get x
testb $3,%bl # check that x is a fixnum jne _25
subl $4,%ebx # "x - 1" jo _26 # check for overflow
_27: movl %eax,-4(%ebp) # save result of call fib(x-2)
movl %ebx,%eax # prepare argument of call fib(x-1)
addl $-4,%ebp # grow frame on stack
cmpl %ebp,(%ecx) # check for stack overflow ja _28
_29: # jump to global property "fib" movl $_24,%edi # setup return address movl 4(%ecx),%esi # setup "this" argument (= global object)
call jump_global_prop_handler # perform jump to global property .long 3 # fib .byte 1,0 # number of arguments and filler
_26: addl $4,%ebx # undo subtraction that overflowed _25: pushl %ebx # handle generic "x - 1" pushl $4 call *28(%ecx) jmp _27
_28: call *12(%ecx) # handle stack overflow jmp _29
ALIGN_RET_POINT FRAME_DESCR .long RET_POINT_TYPE RET_POINT_HEADER_END
_24: # return point of call fib(x-1)
testb $3,%al # check that result of call fib(x-1) is a fixnum jne _30 testb $3,(%ebp) # check that result of call fib(x-2) is a fixnum jne _30
addl (%ebp),%eax # add result of calls fib(x-1) and fib(x-2) jo _31 # check for overflow
_32: addl $12,%ebp # remove stack frame jmp *-8(%ebp) # jump to return address
_31: subl (%ebp),%eax # undo addition that overflowed _30: pushl %eax # handle generic "fib(x-1) + fib(x-2)" pushl -12(%ebp) call *28(%ecx) jmp _32
Afficher les réponses par date
Le 11-05-15 23:36 , Marc Feeley a écrit :
This weekend I improved my prototype compiler which compiles JS to x86, using the global property jump optimization. The compiler is rather minimal and handles just enough to compile fib and similar simple code.
This prototype is mainly useful to explore various implementation approaches quickly, without the burden of the complete Tachyon compiler.
I would be interested in using it too, is it in scheme? Could you put it in our private repository?
The results are very good. On fib(40), proto2 generate faster code than V8 (1.5x) and SpiderMonkey (2.3x), and Tachyon (18x). There is a 1.2x difference between proto1 and proto2 (in other words, there is a 20% overhead to setup and check argument counts). Here are the detailed running times:
relative time to proto2Tachyon 29.613 (18.3) SM 3.700 ( 2.3) V8 2.397 ( 1.5) proto1 2.000 ( 1.2) proto2 1.614 ( 1.0)
Those are great news, how does that compare to gcc?
If you have any questions please let me know.
You did not show how to handle closures. We would need to store the function object pointer in addition to the entry point of the code at the call site. It should only need a little modification of the patching code.
Also, what if the code or the function object is moved by the GC? Should we invalidate all the call site caches or should we patch them with the new addresses?
I could see a similar mecanism used to lazily compile functions. The function could be stored in an AST, HIR or string representation. When jumping to the function the first time, the compiler would first compile the function and then replace the entry point in the function object by the compiled code. This would be complimentary to the global call optimization by delaying the global function call site patching until the entry point of the compiled code is known.
Here's a question for Maxime and Erick... can you estimate the work needed to get Tachyon to generate similar x86 code?
Marc
To follow your current design, we could introduce a global function call instruction in the IR that would take a string property, a this object and the arguments (instead of the function object, the this object and the arguments for a regular CallInstr). This part should be simple.
Additionnally, we would need to modify the global object layout to have a pointer to the call site list in addition to the value of a property. Again, that should be simple with the layout system.
The tricky part, I think, is how to implement the different handlers. I would try to separate the implementation of those such that: 1. The layout of the call sites is known only to the backend 2. The patching code is done by the backend, including the list traversal to invalidate the call sites 3. The global object layout and property lookup is implemented using the layout and primitive system
I would guess it could be done in a couple of days.
Erick
On 2011-05-16, at 1:52 PM, Erick Lavoie wrote:
Le 11-05-15 23:36 , Marc Feeley a écrit :
This weekend I improved my prototype compiler which compiles JS to x86, using the global property jump optimization. The compiler is rather minimal and handles just enough to compile fib and similar simple code.
This prototype is mainly useful to explore various implementation approaches quickly, without the burden of the complete Tachyon compiler.
I would be interested in using it too, is it in scheme? Could you put it in our private repository?
It is in JS and I just pushed it to the repo. It is in source/parser. The main part of the compiler is js86-compile.js . Just cd source/parser and do
% ./js86 fib.js
It will generate fib.js.S and fib.js.exe, and executes it. I've tested it on Mac OS X and Linux. The compiler accepts a bunch of options to enable/disable various code generation features (see the end of js86-compile.js). For example, to call handlers through the context do:
% ./js86 -ctx-handlers fib.js
On my MacBook Pro, calling the handlers through the context gives a 10% performance boost for fib (and generates shorter code).
The results are very good. On fib(40), proto2 generate faster code than V8 (1.5x) and SpiderMonkey (2.3x), and Tachyon (18x). There is a 1.2x difference between proto1 and proto2 (in other words, there is a 20% overhead to setup and check argument counts). Here are the detailed running times:
relative time to proto2Tachyon 29.613 (18.3) SM 3.700 ( 2.3) V8 2.397 ( 1.5) proto1 2.000 ( 1.2) proto2 1.614 ( 1.0)
Those are great news, how does that compare to gcc?
You try it!
If you have any questions please let me know.
You did not show how to handle closures. We would need to store the function object pointer in addition to the entry point of the code at the call site. It should only need a little modification of the patching code.
No modifications are necessary when closures are represented as a piece of code (see my paper "Closure generation based on viewing LAMBDA as EPSILON plus COMPILE" on my web page).
Also, what if the code or the function object is moved by the GC? Should we invalidate all the call site caches or should we patch them with the new addresses?
I don't know. That's the kind of thing that has to be tried to see what works best.
I could see a similar mecanism used to lazily compile functions. The function could be stored in an AST, HIR or string representation. When jumping to the function the first time, the compiler would first compile the function and then replace the entry point in the function object by the compiled code. This would be complimentary to the global call optimization by delaying the global function call site patching until the entry point of the compiled code is known.
Interesting idea.
Here's a question for Maxime and Erick... can you estimate the work needed to get Tachyon to generate similar x86 code?
Marc
To follow your current design, we could introduce a global function call instruction in the IR that would take a string property, a this object and the arguments (instead of the function object, the this object and the arguments for a regular CallInstr). This part should be simple.
Additionnally, we would need to modify the global object layout to have a pointer to the call site list in addition to the value of a property. Again, that should be simple with the layout system.
The tricky part, I think, is how to implement the different handlers. I would try to separate the implementation of those such that:
- The layout of the call sites is known only to the backend
- The patching code is done by the backend, including the list
traversal to invalidate the call sites 3. The global object layout and property lookup is implemented using the layout and primitive system
I would guess it could be done in a couple of days.
If it can be done quickly lets do it.
Marc
On 2011-05-16, at 11:13 PM, chevalma@iro.umontreal.ca wrote:
On my MacBook Pro, calling the handlers through the context gives a 10% performance boost for fib (and generates shorter code).
Calling them through the context as opposed to static linking?
Yes. Here are the measurements on my MacBook Pro:
bash-3.2$ ./js86 fib.js;fgrep -B 1 ".long 3 # fib" fib.js.S
real 0m1.599s user 0m1.595s sys 0m0.002s call jump_global_prop_handler .long 3 # fib -- call deoptimize_global_prop_handler .long 3 # fib -- call jump_global_prop_handler .long 3 # fib -- call jump_global_prop_handler .long 3 # fib bash-3.2$ ./js86 -ctx-handlers fib.js;fgrep -B 1 ".long 3 # fib" fib.js.S
real 0m1.448s user 0m1.446s sys 0m0.002s call *24(%ecx) .long 3 # fib -- call *20(%ecx) .long 3 # fib -- call *24(%ecx) .long 3 # fib -- call *24(%ecx) .long 3 # fib
Note that a direct call takes 5 bytes to encode, and a call through the context takes 3 bytes.
I'm not ready to generalize the performance to other programs. Fib is 10% faster with handlers in the context, but this may be due to changing the alignment of instructions in the cache leading to fewer cache misses. We need to average things over many programs to see if context handlers improve performance in general.
Marc
On 2011-05-15, at 11:36 PM, Marc Feeley wrote:
The results are very good. On fib(40), proto2 generate faster code than V8 (1.5x) and SpiderMonkey (2.3x), and Tachyon (18x). There is a 1.2x difference between proto1 and proto2 (in other words, there is a 20% overhead to setup and check argument counts). Here are the detailed running times:
relative time to proto2Tachyon 29.613 (18.3) SM 3.700 ( 2.3) V8 2.397 ( 1.5) proto1 2.000 ( 1.2) proto2 1.614 ( 1.0)
I have improved the code generation of my prototype compiler. fib(40) now takes 1.42 seconds, or 1.7 times faster than V8.
The changes are on the repo.
Marc
-
chevalma＠iro.umontreal.ca -
Erick Lavoie -
Marc Feeley