luajit是lua的一款高性能虛擬機(jī)。我最近開始搗鼓它，我把目前為止所發(fā)現(xiàn)的記錄到這篇博文里。
luajit是一個(gè)tracing jit，而不是method JIT。它的工作模式并不是發(fā)現(xiàn)并優(yōu)化整個(gè)熱點(diǎn)方法(hot method)，而是發(fā)現(xiàn)并優(yōu)化執(zhí)行過程中的熱點(diǎn)軌跡(hot traces)或者路徑。luaJIT也有一個(gè)相當(dāng)有意思的翻譯器，但我不會(huì)主動(dòng)提到它，除非涉及到JIT。
翻譯器的實(shí)現(xiàn)代碼主要分布到vm_<arch>.dasc文件中，其中包含翻譯器（和其它匯編）樁函數(shù)的規(guī)格說明（以類匯編語言描述）。例如，vm_x86.dasc包含如下函數(shù)：
// Generate assembly code for a specific Lua bytecode.
static void build_ins(BuildCtx *ctx, BCOp op, int defop) {
switch (op) {
case BC_HHGTTG: // hypothetical bytecode
| mov eax, 42 // hypothetical implementation
break;
}
}
vm_86.dasc首先由dynasm.lua解析，并轉(zhuǎn)換成（lowered by）C程序。以|開頭的行被映射成對(duì)dasm_put的調(diào)用，通過這種方式，生成的C函數(shù)自動(dòng)生成(emit)匯編操作碼(assembly opcodes)。這個(gè)新生成的C程序跟buildvm.c一起鏈接，然后在編譯時(shí)生成所需的匯編樁(assembly stubs)。例如，以BC_HHGTTG（轉(zhuǎn)換后）調(diào)用build_ins，會(huì)生成把42寫到eax的匯編操作碼（不管這個(gè)指令的語義是啥）。這個(gè)匯編指令寫入到lj_vm.s，并且與luaJIT其余部分一起鏈接。
探測(cè)熱點(diǎn)軌跡
現(xiàn)在，有了一點(diǎn)背景知識(shí)后，讓我們看看lua實(shí)際上是如何找到要編譯的軌跡（traces）的。LuaJIT用一張hash表，維護(hù)了相關(guān)指令（跳轉(zhuǎn)和調(diào)用）的熱度，但是奇怪的是，它沒有解決沖突。由于熱度是啟發(fā)式的，而不密集（即是，不太可能程序中所有跳轉(zhuǎn)都是熱點(diǎn)），這個(gè)方法實(shí)際上工作得很好。下面的宏用于訪問熱點(diǎn)計(jì)數(shù)（這個(gè)宏是C語言中一個(gè)特定指令）?？纯催@個(gè)宏的實(shí)現(xiàn)，理解應(yīng)該會(huì)更清楚些：
// gg is the global state and pc points to the bytecode
// instruction whose hotcount we want.
#define hotcount_get(gg, pc) (gg)->hotcount[(u32ptr(pc)>>2) & (HOTCOUNT_SIZE-1)]
翻譯器執(zhí)行跳轉(zhuǎn)或者調(diào)用時(shí)，就會(huì)更新并檢查這些熱點(diǎn)計(jì)數(shù)器。這是通過vm_<arch>.dasc中的hotloop和hotcall宏實(shí)現(xiàn)的（我們將只關(guān)注X86架構(gòu)，所以<arch>是x86）：
|.macro hotloop, reg
| mov reg, PC
| shr reg, 1
| and reg, HOTCOUNT_PCMASK
| sub word [DISPATCH+reg+GG_DISP2HOT], HOTCOUNT_LOOP
| jb ->vm_hotloop
|.endmacro
然后，在各個(gè)地方會(huì)調(diào)用hotloop
case BC_FORL:
|.if JIT
| hotloop RB
|.endif
dynasm將這個(gè)宏調(diào)用以簡單明了的方式轉(zhuǎn)換，BC_FORL除去HOTCOUT_LOOP的計(jì)數(shù)，一旦計(jì)數(shù)小于0，則跳轉(zhuǎn)到vm_hotloop
|->vm_hotloop: // Hot loop counter underflow.
|.if JIT
| mov LFUNC:RB, [BASE-8] // Same as curr_topL(L).
| mov RB, LFUNC:RB->pc
| movzx RD, byte [RB+PC2PROTO(framesize)]
| lea RD, [BASE+RD*8]
| mov L:RB, SAVE_L
| mov L:RB->base, BASE
| mov L:RB->top, RD
| mov FCARG2, PC
| lea FCARG1, [DISPATCH+GG_DISP2J]
| mov aword [DISPATCH+DISPATCH_J(L)], L:RBa
| mov SAVE_PC, PC
| call extern lj_trace_hot@8 // (jit_State *J, const BCIns *pc)
| jmp <3
|.endif
dynasm通過.type指示符來識(shí)別C語言的結(jié)構(gòu)體和其內(nèi)部字段的偏移位置。在vm_hotloop的實(shí)現(xiàn)體內(nèi)部，LFUNC:RB告訴dynasm把RB的值當(dāng)作一個(gè)LFUNC來處理。RB和LFUNC在前面定義了：
譯注: LFUNC其實(shí)是GCfuncL，這是luajit的lua函數(shù)類型。與之對(duì)應(yīng)lua還有函數(shù)原型。兩者的差別類似Ｃ＋＋的類與對(duì)象的關(guān)系，不太像js的原型跟對(duì)象的關(guān)系。詳細(xì)分析可看這篇
|.define RB, ebp
// ...
|.type LFUNC, GCfuncL
當(dāng)然，在LFUC:RB中把RB當(dāng)作一個(gè)LFUNC并不會(huì)做什么事，它只是標(biāo)注。但是，在下一條指令中，這個(gè)標(biāo)注讓我們可以在代碼中寫出LFUNC:RB->pc，而dynasm會(huì)自動(dòng)找到pc正確的偏移位置。讓我們逐行看一遍vm_hotloop，注意BASE指向lua求值棧的棧頂，RB和RD則是寄存器，F(xiàn)CARG1和FCARG2也是寄存器，它倆是lua調(diào)用C函數(shù)時(shí)調(diào)用規(guī)范中的前兩個(gè)函數(shù)參數(shù)，SAVE_L和SAVE_PC是棧上的槽位。
首先，我們從棧頂彈出GCFuncL，并取出pc，其指向這個(gè)閉包字節(jié)碼的開頭：
| mov LFUNC:RB, [BASE-8]
| mov RB, LFUNC:RB->pc
luaJIT遵守一個(gè)通用慣例，函數(shù)字面量或者原型跟函數(shù)閉包分開保存。這樣，VM可以在相同函數(shù)原型的兩個(gè)閉包之間共享字節(jié)碼，從而節(jié)省空間。例如，在V8中，你用SharedFunctionInfo來保存一個(gè)函數(shù)字面量的特有信息，用 Function來表示實(shí)際可執(zhí)行的閉包。
在luaJIT中，函數(shù)字面量用GCproto來表示。在內(nèi)存中，一個(gè)GCproto對(duì)象后面跟著函數(shù)字面量（所有閉包共享，用GCfuncL來表示）的字節(jié)碼。因此，給定一個(gè)GCfuncL，我們能夠?qū)⒅赶蜃止?jié)碼數(shù)組開頭的指針減去sizeof(GCproto)來得到對(duì)應(yīng)的GCproto。PC2PROTO用這個(gè)技術(shù)來訪問GCproto結(jié)構(gòu)體的framesize字段，用它來計(jì)算棧上第一個(gè)可用槽。
| movzx RD, byte [RB+PC2PROTO(framesize)]
| lea RD, [BASE+RD*8]
然后，我們填好lua_state的各個(gè)字段（在lj_obj.h中定義）
| mov L:RB, SAVE_L
| mov L:RB->base, BASE
| mov L:RB->top, RD
設(shè)置參數(shù)寄存器，保存一點(diǎn)東西到棧槽中，然后調(diào)用lj_trace_hot
| mov FCARG2, PC
| lea FCARG1, [DISPATCH+GG_DISP2J]
| mov aword [DISPATCH+DISPATCH_J(L)], L:RBa
| mov SAVE_PC, PC
| call extern lj_trace_hot@8
| jmp <3
luaJIT進(jìn)入記錄模式。
記錄軌跡
軌跡是執(zhí)行一段特定代碼路徑的字節(jié)碼線性序列。軌跡由翻譯器協(xié)助記錄（記錄始于lj_trace_hot調(diào)用之時(shí)）。翻譯器使用一個(gè)指針數(shù)組，其元素指向匯編樁，并以匯編樁實(shí)現(xiàn)的字節(jié)碼指令為數(shù)組索引--原則上，翻譯一個(gè)lua程序則是把字節(jié)碼一個(gè)接一個(gè)解碼并跳轉(zhuǎn)到對(duì)應(yīng)的匯編樁上。把這個(gè)調(diào)度數(shù)組中各個(gè)元素都指向lj_vm_record（dynasm加上了lj_前綴，在vm_x86.dasc中符號(hào)其實(shí)是vm_record）從而記錄軌跡。一個(gè)簡化的vm_record如下所示：
|->vm_record:
| mov L:RB, SAVE_L
| mov L:RB->base, BASE
| mov FCARG2, PC
| mov FCARG1, L:RB
| call extern lj_dispatch_ins@8
| mov BASE, L:RB->base
| movzx RA, PC_RA
| movzx OP, PC_OP
| movzx RD, PC_RD
| jmp aword [DISPATCH+OP*8+GG_DISP2STATIC]
|.endif
可以看到這段代碼基本上是先調(diào)用lj_dispatch_ins，然后跳轉(zhuǎn)到 [DISPATCH+OP*8+GG_DISP2STATIC] 指向的地址。luajit會(huì)在相距調(diào)度數(shù)組GG_DISP2STATIC的地方保存調(diào)度數(shù)組的副本。調(diào)度數(shù)組當(dāng)下只包含指向的lj_vm_record的指針。
Lj_vm_record用這個(gè)副本數(shù)組來跳轉(zhuǎn)到真正的匯編樁。
我們不要老是紙上談兵，現(xiàn)在我們看看實(shí)實(shí)在在的代碼，理解代碼的精妙之處。
當(dāng)一次循環(huán)或者調(diào)用被度量為熱點(diǎn)后，翻譯器調(diào)用lj_trace_hot，其為記錄，編譯和安裝軌跡的入口。lj_trace_hot設(shè)置重要對(duì)象jit_State的狀態(tài)為LJ_TRACE_START，并且把CPU控制權(quán)移交給lj_trace_ins。
luajit的跟蹤子系統(tǒng)（tracing subsystem）有五個(gè)狀態(tài)：START,RECORD, END, ASM和ERR。lj_trace_ins是一個(gè)有限自動(dòng)機(jī)（finite automaton），其基于從執(zhí)行軌跡上讀出的字節(jié)碼指令來進(jìn)行狀態(tài)之間的遷移。總體方案很簡單：
START -------------------> RECORD ---> ERR
set up dispatch |
vector | [IDLE]
v /
END -----> ASM
當(dāng)然，這些狀態(tài)遷移不會(huì)同時(shí)發(fā)生--隨著調(diào)用lj_dispatch_ins解析當(dāng)前執(zhí)行軌跡的越來越多字節(jié)碼，狀態(tài)被記錄下來，狀態(tài)遷移（或者不遷移）。跟蹤器看到的字節(jié)碼流被譯作SSA形式的中間表示（intermediate SSA representation），然后再優(yōu)化和編譯成匯編。
跟蹤只會(huì)給我們一個(gè)代碼的線性路徑，而不管其它已得到的相同的有效路徑。跟蹤JIT通常通過安裝守衛(wèi)（guards）來處理這種情況。守衛(wèi)會(huì)檢查各種假設(shè)條件，當(dāng)違反假設(shè)時(shí)跳出軌跡（就luajit而言，會(huì)返回翻譯器）。例如，考慮下面這個(gè)簡單的lua程序：
total = 0
function test()
if total < 500 then
total = total + 1
end
end
for i=1,501 do
test()
end
這段代碼會(huì)編譯為如下的字節(jié)碼（去掉一些對(duì)我們的理解不重要的部分）
;; function test()
0001 GGET 0 0
0002 KSHORT 1 500
0003 ISGE 0 1
0004 JMP 0 => 0008
0005 GGET 0 0
0006 ADDVN 0 0 0
0007 GSET 0 0
0008 => RET0 0 1
;; body (instructions 0001 to 0007 removed)
0008 FORI 0 => 0012
0009 => GGET 4 2 ; "test"
0010 CALL 4 1 1
0011 FORL 0 => 0009
0012 => RET0 0 1
（用-b -l可以讓luajit以上面的形式輸出字節(jié)碼，用-jdump輸出全部的軌跡信息）
沒啥意外的--有一個(gè)for循環(huán)（以FORI和FORL來定界），調(diào)用了501次test。luajit提取下面這段SSA格式的軌跡（也刪減了代碼）
;; Instructions 0001 to 0013 removed
0014 > p32 HREFK 0013 "total" @11
0015 > num HLOAD 0014
0016 > num LT 0015 +500
0017 + num ADD 0015 +1
0018 num HSTORE 0014 0017
0019 + int ADD 0001 +1
0020 > int LE 0019 +501
0021 ------ LOOP ------------
0022 > num LT 0017 +500
0023 + num ADD 0017 +1
0024 num HSTORE 0014 0023
0025 + int ADD 0019 +1
0026 > int LE 0025 +501
0027 int PHI 0019 0025
0028 num PHI 0017 0023
LOOP之后的指令不足為奇：一個(gè)典型的循環(huán)加上一個(gè)尋常的SSA phi節(jié)點(diǎn)。注意（在跟蹤JIT（tracing JITs）中很尋常），test的一個(gè)版本被完全內(nèi)聯(lián)到一個(gè)緊湊循環(huán)中。指令0016相當(dāng)有意思：>表示這是一條特殊的指令，它是一個(gè)守衛(wèi)（guard），即如果這條指令對(duì)應(yīng)的條件不滿足則這個(gè)軌跡會(huì)退出，并返回到翻譯器。在這里，如果0015（為總的值，看看0014和0015指令你就明白了）大于等于500，則會(huì)退出。有意思的原因是跟蹤編譯器沒有自作聰明，而是當(dāng)總值大于等于500時(shí)啥也沒做，這也是正確的行為。它只知道當(dāng)總值小于500時(shí)，正確的作為是總值加1，因?yàn)檫@正是它在軌跡中所遵從的（what it has observed in the trace）。特別的是，如果總值大于等于500，路徑已經(jīng)走了足夠多次，這條路徑會(huì)被標(biāo)記為熱點(diǎn)，然后將編譯成一個(gè)副軌跡（side-trace，相對(duì)root trace而言），你應(yīng)該自己試試分析這個(gè)過程。
Lj_record.c中的lj_record_ins在字節(jié)碼執(zhí)行前，以SSA格式記錄每條字節(jié)碼指令。一個(gè)構(gòu)架上的精妙之處在于知道要生成哪個(gè)守衛(wèi)（guard）-- 假設(shè)一個(gè)條件：
IF A < B THEN {0} ELSE {1} END
是要生成A < B的守衛(wèi)還是生成NOT (A < B)的守衛(wèi)呢？這只有在條件求值之后才知道。如果在軌跡記錄階段，A < B為真，那么我們需要一個(gè)守衛(wèi)來保證A < B，反之亦然。luajit沒有在跟蹤器中實(shí)現(xiàn)一個(gè)偏翻譯器（partial interpreter），而是把守衛(wèi)指令的插入推遲到調(diào)用下一個(gè)字節(jié)碼的lj_record_ins之前。這時(shí)它就知道條件計(jì)算的結(jié)果了。
另外一個(gè)精妙之處涉及代碼路徑包含已經(jīng)編譯的軌跡。luajit通過替換正常的循環(huán)或者調(diào)用字節(jié)碼為帶有特殊標(biāo)記的字節(jié)碼來跟蹤已編譯的軌跡。這些特殊的字節(jié)碼表示軌跡的存在，并提供開始于這點(diǎn)的已編譯軌跡的位置。然而，當(dāng)跟蹤時(shí)，我們想要能看到函數(shù)字節(jié)碼。解決方案是：先臨時(shí)把特殊的JIT標(biāo)記字節(jié)碼（例如BC_JFUNCF或者BC_JLOOP）打補(bǔ)丁成原始的字節(jié)碼，再讓跟蹤器走完原始字節(jié)碼，在跟蹤結(jié)束后再把補(bǔ)丁去掉，JIT標(biāo)記字節(jié)又重新生效。這段處理在rec_func_jit（在lj_record.c中）和trace_pendpatch（在lj_trace.c中）。
快照
涉及在兩個(gè)（或者多個(gè)?。﹫?zhí)行模式轉(zhuǎn)換的VM都會(huì)面臨一個(gè)在未優(yōu)化和已優(yōu)化的堆棧布局之間的切換的問題。對(duì)luajit來說，也是這樣。luajit的棧的含義稍有不同。我們希望同一個(gè)軌跡的翻譯版本和編譯版本之間是觀測(cè)性等價(jià)（observational equivalence）的。而且編譯版本有相同的副作用，操作數(shù)棧的映射方式也要跟翻譯版本一致。然而，這種等價(jià)性不需要在已編譯的軌跡內(nèi)部保持，只需要在軌跡出口（用守衛(wèi)方式或者不用）中保持即可。
luajit解決方案是：維護(hù)一個(gè)從棧位置到SSA IR指令的映射。這些映射在luajit代碼庫中被稱為快照（snapshots）。使用一個(gè)快照，它能重新構(gòu)建操作數(shù)棧就好像軌跡被翻譯的那樣（對(duì)應(yīng)的代碼在lj_snap.c中的snap_restoreval和ln_snap_restore）。
這很慢，但套用Mike Pall的話來說：『使用數(shù)據(jù)驅(qū)動(dòng)方式的狀態(tài)恢復(fù)當(dāng)然會(huì)很慢。但是反復(fù)調(diào)用副出口（side exits）會(huì)很快觸發(fā)副軌跡（side traces）的生成?？煺沼糜诔跏蓟避壽E的IR。初始化需要必要的狀態(tài)，而狀態(tài)要用似載荷（pseudo-loads）。這些能一起用副軌跡的余下部分來優(yōu)化。通過后端讓似載荷與父軌跡的機(jī)器狀態(tài)相統(tǒng)一，從來能夠零成本的把似載荷鏈接到副軌跡中?！?/p>
