JIT版 fib が動いた - JIT 実験

いろいろと制限付きではあるが JIT 版の fib が動いた。（正確には JIT コンパイラが吐くコードが動いた。Just in time なコンパイルはしてない）

速度比較

通常の (fib 30)	250msec
JIT (fib 30)	200msec

JIT 版の fib はまだ速くなる余地がある。

• VM の仮想レジスタを実レジスタにのせる
• peephole optimization で不要命令削除

など。

150 msec くらいになるならやる価値ありそう。

JIT コード

 (let* ([code1 (let ([label (gensym)])
                 (assemble
                  (append
                   (REFER_LOCAL_PUSH_CONSTANT 0 (vm-make-fixnum 2))
                   (BRANCH_NOT_LT label)
                   (CONSTANT (vm-make-fixnum 1))
                   (RETURN 1)
                   `((label ,label))
                   (FRAME)
                   (REFER_LOCAL_PUSH_CONSTANT 0 (vm-make-fixnum 2))
                   (NUMBER_SUB_PUSH)
                   (REFER_GLOBAL 'fib)
                   (CALL 1)
                   (PUSH_FRAME)
                   (REFER_LOCAL_PUSH_CONSTANT 0 (vm-make-fixnum 1))
                   (NUMBER_SUB_PUSH)
                   (REFER_GLOBAL 'fib)
                   (CALL 1)
                   (NUMBER_ADD)
                   (RETURN 1)
                   )))]
        [fib (u8*->c-procedure+retq code1)])
   (set-symbol-value! 'fib proc)
   (time (test-eq 1346269 (proc 30)))))

出力アセンブラ

(movq rcx (& rdi 40))
(movq rdx 1)
(movq rax (& rdi 32))
(sarq rdx 2)
(movq rax (& rax (* rdx 8))) 
(movq (& rcx) rax) 
(addq rcx 8)
(movq (& rdi 40) rcx)
(movq rcx 9)
(movq (& rdi 8) rcx)
(movq rax (& rdi 40))
(leaq rdx (& rax -8))
(movq (& rdi 40) rdx)
(movq rdx (& rax -8))
(movl eax edx)
(andl eax 3)
(subb al 1)
(je mO2e)
(movq r8 3001)
(int 3)
(label mO2f)
(movq r8 3002)
(int 3)
(label mO2e)
(movq rcx (& rdi 8))
(movl eax ecx)
(andl eax 3)
(subb al 1)
(jne mO2f)
(sarq rdx 2)
(sarq rcx 2)
(movq rax 8930096)
(cmpq rdx rcx)
(movq rdx 8930088)
(cmovl rax rdx)
(movq rax (& rax))
(movq (& rdi 8) rax)
(cmpq (& rdi 8) 86)
(je mO2d)
(movq (& rdi 8) 5)
(movq rax (& rdi 8))
(movq rdx 1)
(leaq rdx (& (* rdx 8)))
(negq rdx)
(addq rdx (& rdi 40))
(movq rax (& rdx -8))
(movq (& rdi 32) rax)
(movq rax (& rdx -16))
(movq (& rdi 24) rax)
(movq rax (& rdx -24))
(movq (& rdi 16) rax)
(movq rax (& rdx -32))
(leaq rcx (& rdx -32))
(movq (& rdi 48) rax)
(movq (& rdi 40) rcx)
(movq rax (& rdi 8))
(retq)
(label mO2d)
(movq rdx (& rdi 40))
(movq rax (& rdi 48))
(movq (& rdx) rax)
(movq rax (& rdi 16))
(movq (& rdx 8) rax)
(movq rax (& rdi 24))
(movq (& rdx 16) rax)
(movq rax (& rdi 32))
(movq (& rdx 24) rax)
(addq rdx 32)
(movq (& rdi 40) rdx)
(movq rcx (& rdi 40))
(movq rdx 1)
(movq rax (& rdi 32))
(sarq rdx 2)
(movslq rdx edx)
(movq rax (& rax (* rdx 8)))
(movq (& rcx) rax)
(addq rcx 8)
(movq (& rdi 40) rcx)
(movq rcx 9)
(movq (& rdi 8) rcx)
(movq rax (& rdi 40))
(leaq rdx (& rax -8))
(movq (& rdi 40) rdx)
(movq rbp (& rax -8))
(movl eax ebp)
(andl eax 3)
(subb al 1)
(je mO30)
(movq r8 3030)
(int 3)
(label mO31)
(int 3)
(label mO32)
(movq r8 3031)
(int 3)
(label mO30)
(movq rdx (& rdi 8))
(movl eax edx)
(andl eax 3)
(subb al 1)
(jne mO31)
(movq rax rbp)
(sarq rdx 2)
(sarq rax 2)
(subl eax edx)
(movslq r12 eax)
(leaq rax (& r12 536870912))
(leaq rdx (& 1 (* r12 4)))
(cmpq rax 1073741823)
(ja mO32)
(movq (& rdi 8) rdx)
(movq rax (& rdi 40))
(movq (& rax) rdx)
(addq rax 8)
(movq (& rdi 40) rax)
(movq rbx 33389120)
(testb bl 3)
(jne mO34)
(movq rax (& rbx))
(movq rdx rax)
(andl edx 3)
(cmpq rdx 3)
(je mO34)
(movq r8 3009)
(int 3)
(label mO35)
(movq r8 3010)
(int 3)
(label mO33)
(movq r8 3011)
(int 3)
(label mO34)
(movq rax (& rdi 80))
(push rdi)
(push rsi)
(push rdx)
(movq rdx (& rdi 88))
(movq rsi rbx)
(movq rdi (& rax 8))
(movq rax (& rdi))
(callq (& rax 24))
(pop rdx)
(pop rsi)
(pop rdi)
(cmpq (& rdi 88) rax)
(je mO33)
(movq rdx (& rax 8))
(movq rdx (& rdx))
(movq (& rdi 8) rdx)
(push rdi)
(push rsi)
(push rdx)
(movq rax 1)
(leaq rcx (& (* rax 8)))
(negq rcx)
(addq rcx (& rdi 40))
(movq (& rdi 32) rcx)
(movq rdx 1)
(movq rsi rdi)
(movq rax (& rdi 8))
(movq rdi (& rax 8))
(movq rax 4324928)
(callq rax)
(pop rdx)
(pop rsi)
(pop rdi)
(push rax)
(pop rax)
(movq (& rdi 8) rax)
(push rcx)
(push rax)
(movq rcx (& rdi 40))
(movq rax (& rdi 8))
(movq (& rcx) rax)
(addq rcx 8)
(movq (& rdi 40) rcx)
(pop rax)
(pop rcx)
(movq rdx (& rdi 40))
(movq rax (& rdi 48))
(movq (& rdx) rax)
(movq rax (& rdi 16))
(movq (& rdx 8) rax)
(movq rax (& rdi 24))
(movq (& rdx 16) rax)
(movq rax (& rdi 32))
(movq (& rdx 24) rax)
(addq rdx 32)
(movq (& rdi 40) rdx)
(movq rcx (& rdi 40))
(movq rdx 1)
(movq rax (& rdi 32))
(sarq rdx 2)
(movslq rdx edx)
(movq rax (& rax (* rdx 8)))
(movq (& rcx) rax)
(addq rcx 8)
(movq (& rdi 40) rcx)
(movq rcx 5)
(movq (& rdi 8) rcx)
(movq rax (& rdi 40))
(leaq rdx (& rax -8))
(movq (& rdi 40) rdx)
(movq rbp (& rax -8))
(movl eax ebp)
(andl eax 3)
(subb al 1)
(je mO36)
(movq r8 3030)
(int 3)
(label mO37)
(int 3)
(label mO38)
(movq r8 3031)
(int 3)
(label mO36)
(movq rdx (& rdi 8))
(movl eax edx)
(andl eax 3)
(subb al 1)
(jne mO37)
(movq rax rbp)
(sarq rdx 2)
(sarq rax 2)
(subl eax edx)
(movslq r12 eax)
(leaq rax (& r12 536870912))
(leaq rdx (& 1 (* r12 4)))
(cmpq rax 1073741823)
(ja mO38)
(movq (& rdi 8) rdx)
(movq rax (& rdi 40))
(movq (& rax) rdx)
(addq rax 8)
(movq (& rdi 40) rax)
(movq rbx 33389120)
(testb bl 3)
(jne mO3a)
(movq rax (& rbx))
(movq rdx rax)
(andl edx 3)
(cmpq rdx 3)
(je mO3a)
(movq r8 3009)
(int 3)
(label mO3b)
(movq r8 3010)
(int 3)
(label mO39)
(movq r8 3011)
(int 3)
(label mO3a)
(movq rax (& rdi 80))
(push rdi)
(push rsi)
(push rdx)
(movq rdx (& rdi 88))
(movq rsi rbx)
(movq rdi (& rax 8))
(movq rax (& rdi))
(callq (& rax 24))
(pop rdx)
(pop rsi)
(pop rdi)
(cmpq (& rdi 88) rax)
(je mO39)
(movq rdx (& rax 8))
(movq rdx (& rdx))
(movq (& rdi 8) rdx)
(push rdi)
(push rsi)
(push rdx)
(movq rax 1)
(leaq rcx (& (* rax 8)))
(negq rcx)
(addq rcx (& rdi 40))
(movq (& rdi 32) rcx)
(movq rdx 1)
(movq rsi rdi)
(movq rax (& rdi 8))
(movq rdi (& rax 8))
(movq rax 4324928)
(callq rax)
(pop rdx)
(pop rsi)
(pop rdi)
(push rax)
(pop rax)
(movq (& rdi 8) rax)
(movq rax (& rdi 40))
(leaq rdx (& rax -8))
(movq (& rdi 40) rdx)
(movq rbp (& rax -8))
(movl eax ebp)
(andl eax 3)
(subb al 1)
(je mO3c)
(movq r8 3020)
(int 3)
(label mO3d)
(movq r8 3021)
(int 3)
(label mO3e)
(movq r8 3022)
(int 3)
(label mO3c)
(movq rdx (& rdi 8))
(movl eax edx)
(andl eax 3)
(subb al 1)
(jne mO3d)
(movq rax rbp)
(sarq rdx 2)
(sarq rax 2)
(addl eax edx)
(movslq r12 eax)
(leaq rax (& r12 536870912))
(leaq rdx (& 1 (* r12 4)))
(cmpq rax 1073741823)
(ja mO3e)
(movq (& rdi 8) rdx)
(movq rax rdx)
(movq rdx 1)
(leaq rdx (& (* rdx 8)))
(negq rdx)
(addq rdx (& rdi 40))
(movq rax (& rdx -8))
(movq (& rdi 32) rax)
(movq rax (& rdx -16))
(movq (& rdi 24) rax)
(movq rax (& rdx -24))
(movq (& rdi 16) rax)
(movq rax (& rdx -32))
(leaq rcx (& rdx -32))
(movq (& rdi 48) rax)
(movq (& rdi 40) rcx)
(movq rax (& rdi 8))
(retq)