原文：Hello, JIT World: The Joy of Simple JITs
標簽（空格分隔）：jit 編譯器 DynASM

這是一個關于小的JITs(即時編譯器)是多么簡單和有趣的演示，‘JIT’這個詞往往會給你一種深奧的魔法的印象缸沃，只有最核心的編譯器團隊才能創(chuàng)造這個夢想妒貌。它讓你想到JVM和.NET，龐大的運行時系統(tǒng)和成千上萬行的代碼棚蓄。你從來沒有看到過像“Hello, World!”這樣大小的JIT編譯器程序缤底，只需要少量的代碼就可以做一些有趣的事情扁耐。這篇文章就是試圖改變這種現(xiàn)狀的。

如果你仔細想想款熬，JIT實際上和一個調用sprintf()的程序沒什么不同深寥，JIT不過只是發(fā)出機器碼，而不是一條像“Hello, World!”的消息贤牛。當然惋鹅，像JVM這樣的JIT編譯器都是高度復雜的野獸，但那是因為他們實現(xiàn)了一個復雜的平臺并且做了很多積極的優(yōu)化操作殉簸。如果我們把事情處理的越簡單闰集，那么我們的程序也會更簡單。

編寫一個簡單的JIT編譯器最困難的部分是編碼指令般卑，這些指令可以被你的目標平臺CPU所理解武鲁。舉個例子，在x86-64平臺上蝠检，指令push rbp被編碼為字節(jié)0x55沐鼠。實現(xiàn)這些編碼操作是非常煩躁的并且需要閱讀大量的CPU手冊，所以我們將跳過那個部分叹谁。相反饲梭，我們將使用Mike Pall的庫DynASM來處理編碼。DynASM有一個非常新穎的方法焰檩，可以讓你混合你將生成的匯編代碼和你的JIT編譯器的C代碼憔涉，這可以讓你以一種自然的和可讀的方式編寫JIT編譯器。它支持很多CPU架構（在編寫本文時已支持x86, x86-64, PowerPC, MIPS和ARM）析苫，所以你不太可能受限于硬件的支持兜叨。DynASM還出乎意料的小并且也沒那么正式穿扳。它的整個運行時包含在一個500行的頭文件中。

我要先簡單的介紹一下我所引用的術語国旷。我把那些執(zhí)行在運行時生成的機器碼的程序稱為“JIT”纵揍。有些作者會在更特殊的場景中使用這個術語，并且僅認為JIT是混合解釋器或編譯器在小的代碼片段根據(jù)需要生成機器碼议街。這些作者將這中更一般的運行時代碼生成的技術稱為“動態(tài)編譯”。但是“JIT”是更常見和聞名的術語璧榄，并經(jīng)常被用于不同的場景中特漩，那些不都符合JIT的最嚴格定義，像Berkeley Packet Filter JIT骨杂。

Hello, JIT World!

閑話少說涂身，讓我們進入第一個“JIT”。這個和所有其他的程序都在我的GitHub倉庫jitdemo搓蚪。這些代碼是特定于Unix平臺的蛤售，因為它們使用了mmap()，我們將會生成x86-64平臺的代碼妒潭，所以你需要一個處理器和操作系統(tǒng)來支持它悴能。我在Ubuntu Linux和Mac OS X測試過他們。

我們甚至不會在第一個實例中使用DynASM雳灾，讓它盡可能的簡單漠酿。這個程序是jit1.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

int main(int argc, char *argv[]) {
  // 機器碼:
  //   mov eax, 0
  //   ret
  unsigned char code[] = {0xb8, 0x00, 0x00, 0x00, 0x00, 0xc3};

  if (argc < 2) {
    fprintf(stderr, "Usage: jit1 <integer>\n");
    return 1;
  }

  // 以指定的值argv[1]覆蓋指令中的立即數(shù)“0”：
  //   mov eax, <指定的值>
  //   ret
  int num = atoi(argv[1]);
  memcpy(&code[1], &num, 4);

  // 申請可寫可運行的內存。
  // 注意：在實際的編程中不要將內存映射為即可寫也可運行谎亩，因為這樣做是不安全的炒嘲。
  void *mem = mmap(NULL, sizeof(code), PROT_WRITE | PROT_EXEC,
                   MAP_ANON | MAP_PRIVATE, -1, 0);
  memcpy(mem, code, sizeof(code));

  // 這個函數(shù)將會返回指定的值。
  int (*func)() = mem;
  return func();
}

這可能看起來難以相信只有33行代碼匈庭，但是這是一個正式的JIT夫凸。它動態(tài)的生成一個函數(shù)并運行它，這個函數(shù)返回一個運行時指定的整數(shù)阱持。你可以這樣確定它是否工作：

$ ./jit1 42 ; echo $?
42

你會注意到我必須使用mmap()而不是malloc()來申請內存夭拌，從堆中申請內存才是正常的方法。但這是必須的衷咽，因為我們需要這段內存是可執(zhí)行的啼止，這樣我們才可以跳轉到它來執(zhí)行而不會導致程序崩潰。在大部分系統(tǒng)上兵罢，堆和棧被配置為不可執(zhí)行献烦，因為如果我們可以隨意跳轉到堆或棧上，這意味著某些方面會產(chǎn)生問題卖词。更糟糕的是巩那，黑客可以利用緩沖溢出來使用可執(zhí)行堆棧從而更容易找到安全漏洞吏夯。所以，我們通常會避免將任何內存映射為即可寫也可執(zhí)行即横，在你自己的程序中遵循這條規(guī)則也是一個好習慣噪生。在上述代碼中我打破了這條規(guī)則，但是那只是為了讓我們的第一個程序盡可能簡單而已东囚。

我還偷工減料沒有釋放我申請的內存跺嗽。我們可以很快解決這個問題。mmap()有一個對應的函數(shù)munmap()页藻，我們可以使用它將內存釋放回操作系統(tǒng)桨嫁。

你可能會想知道為啥你不能調用一個函數(shù)將你從malloc()申請的內存的權限改變呢？以一種完全不同的方式申請可執(zhí)行的內存聽起來似乎挺不靠譜份帐。事實上璃吧，有一個函數(shù)可以改變你已經(jīng)占用的內存的權限，這就是mprotect()废境。但是這些權限僅能被設置在內存頁的邊界畜挨，malloc()可能給你一些從內存頁中間劃分的內存，你無法完全擁有整個內存頁噩凹。如果你開始改變內存頁的權限巴元，你將影響到任何其他可能會使用這個內存頁上內存的代碼。

Hello, DynASM World!

DynASM是一個令人深感敬佩的項目LuaJIT的一部分驮宴，但是是完全獨立于LuaJIT代碼的务冕，并且可以單獨使用。它包括兩部分：

• 一個預處理器幻赚，將混合C代碼和匯編代碼的文件(*.dasc)直接轉化為C代碼禀忆。
• 一個小的運行時系統(tǒng)，鏈接必須被推遲到運行時執(zhí)行的C代碼落恼。

這個設計是非常好的箩退，因為解析匯編語言和編碼機器碼的所有的底層復雜的代碼都可以用一個高級的，帶垃圾收集的語言（Lua）來寫佳谦，并且Lua只在構建時才需要戴涝，運行時不需要依賴Lua。

對于我們的第一個DynASM實例，我將編寫一個程序來生成跟我們上一個實例同樣的函數(shù)。這樣我們就可以進行比較识埋，看看這兩種方法的區(qū)別，并了解DynASM為我們帶來了什么可帽。

// DynASM規(guī)則.
|.arch x64
|.actionlist actions

// 這個定義影響"|"DynASM行〈芭“Dst”必須為一個指向dasm_State*的指針dasm_State**
#define Dst &state

int main(int argc, char *argv[]) {
  if (argc < 2) {
    fprintf(stderr, "Usage: jit1 <integer>\n");
    return 1;
  }

  int num = atoi(argv[1]);
  dasm_State *state;
  initjit(&state, actions);

  // 生成代碼映跟。每一行加到“state”中的一個緩存中蓄拣，但是這個緩存中的代碼不會完全被鏈接，
  // 因為標簽可以在他們定義之前被引用努隙。
  //
  // C變量“num”的運行時的值被替換到指令的立即數(shù)中球恤。
  |  mov eax, num
  |  ret

  // 鏈接代碼并將它寫入可執(zhí)行內存。
  int (*fptr)() = jitcode(&state);

  // 調用JIT-ted函數(shù)
  int ret = fptr();
  assert(num == ret);

  // 釋放機器碼
  free_jitcode(fptr);

  return ret;
}

這不是完整的程序荸镊，一些為了初始化DynASM和申請釋放可執(zhí)行內存的輔助功能被定義在dynasm-driver.c中咽斧。這個共享的輔助功能代碼在我們所有的實例中都是一樣的，所以我們這里忽略它躬存。它相當?shù)暮唵魏妥⑨屃己迷诖a倉庫中张惹。

觀察的關鍵區(qū)別是如何生成指令。我們的.dasc文件可以包含匯編語言优构，類似于如何編寫.S文件。以一個管道符(|)開始的文件會被DynASM解釋并且可以包含匯編語言指令或規(guī)則雁竞。這是一個比我們第一個實例更強大的方法钦椭。特別要注意參數(shù)之一到我們的mov指令是怎樣引用一個C變量的。DynASM知道在生成代碼時怎樣把這個變量的值帶入指令中碑诉。

為了了解這是如何實現(xiàn)的彪腔，我們可以看看jit2.h（從jit2.dasc生成）中的預處理器的輸出。我摘錄了有趣的部分进栽，文件中其余的部分都被省略德挣。

//|.arch x64
//|.actionlist actions
static const unsigned char actions[4] = {
  184,237,195,255
};

// [...]

//|  mov eax, num
//|  ret
dasm_put(Dst, 0, num);

這里我們看到在.dasc文件（現(xiàn)在注釋掉）中我們寫的源碼行和用它們生成代碼行】烀“action”列表是DynASM預處理器生成的數(shù)據(jù)的緩存格嗅。它是將被DynASM運行時解釋的字節(jié)碼。它將我們匯編語言指令的直接編碼和DynASM運行時用來鏈接的代碼混合并插入我們的運行時的值唠帝。在這種情況下屯掖，我們的“action”列表中的四個字節(jié)被解釋為：

• 184 – x86平臺mov eax, [立即數(shù)]指令的第一個字節(jié)。
• 237 – DynASM字節(jié)碼指令DASM_IMM_D襟衰，表示下一個dasm_put()的參數(shù)應該被寫為一個四字節(jié)的值贴铜，這就是完全的mov指令。
• 195 – x86平臺ret指令的編碼
• 255 – DynASM字節(jié)碼指令DASM_STOP瀑晒，表示編碼應該終止绍坝。

這個“action”緩存在后面會被實際產(chǎn)生匯編指令的部分代碼引用。這些指令產(chǎn)生代碼行會被替換為dasm_put()調用苔悦，并提供"action"緩存的偏移量并傳遞任何需要被替換到輸出（就像我們的運行時值num）中的運行時值轩褐。dasm_put()將添加這些指令（帶有我們的運行時值num）到緩存中存儲在狀態(tài)中（參考上面定義的#define Dst &state）。

結果就是我們得到了跟我們第一個實例完全一樣的效果玖详，但是這一次我們使用的方法讓我們編寫可以匯編語言灾挨。這是一種編寫JIT程序的更好的方法邑退。

一個Brainf*ck語言的簡單JIT編譯器

我們可以選定的最簡單的圖靈完備語言無疑就是帶有奇幻色彩的語言Brainf*ck（以下簡稱為BF）。BF僅用八個命令就能實現(xiàn)圖靈完備（甚至包含I/O）劳澄。這些命令可以被認為是一種字節(jié)碼地技。

不會比上一個實例復雜多少，我們可以用少于100行C代碼（包括我們70行左右的共享的驅動文件）實現(xiàn)全功能的BF JIT編譯器：

#include <stdint.h>

|.arch x64
|.actionlist actions
|
|// 使用rbx作為我們的單元指針秒拔。
|// 由于rbx是一個被調用-保存寄存器莫矗，它將被保存通過調用getchar和putchar
|.define PTR, rbx
|
|// 函數(shù)調用的宏。
|// 在我們的目標地址是小于等于2^32的情況下我們可以使用
|//   | call &addr
|// 但是由于我們不知道它是否小于2^32砂缩，我們使用這個安全的序列代替作谚。
|.macro callp, addr
|  mov64  rax, (uintptr_t)addr
|  call   rax
|.endmacro

#define Dst &state
#define MAX_NESTING 256

void err(const char *msg) {
  fprintf(stderr, "%s\n", msg);
  exit(1);
}

int main(int argc, char *argv[]) {
  if (argc < 2) err("Usage: jit3 <bf program>");
  dasm_State *state;
  initjit(&state, actions);

  unsigned int maxpc = 0;
  int pcstack[MAX_NESTING];
  int *top = pcstack, *limit = pcstack + MAX_NESTING;

  // 函數(shù)頭
  |  push PTR
  |  mov  PTR, rdi

  for (char *p = argv[1]; *p; p++) {
    switch (*p) {
      case '>':
        |  inc  PTR
        break;
      case '<':
        |  dec  PTR
        break;
      case '+':
        |  inc  byte [PTR]
        break;
      case '-':
        |  dec  byte [PTR]
        break;
      case '.':
        |  movzx edi, byte [PTR]
        |  callp putchar
        break;
      case ',':
        |  callp getchar
        |  mov   byte [PTR], al
        break;
      case '[':
        if (top == limit) err("Nesting too deep.");
        // 每個循環(huán)獲取兩個pc標簽：在開始和結束。
        // 我們存儲pc標簽偏移量到一個棧中一起鏈接循環(huán)開始和結束庵芭。
        maxpc += 2;
        *top++ = maxpc;
        dasm_growpc(&state, maxpc);
        |  cmp  byte [PTR], 0
        |  je   =>(maxpc-2)
        |=>(maxpc-1):
        break;
      case ']':
        if (top == pcstack) err("Unmatched ']'");
        top--;
        |  cmp  byte [PTR], 0
        |  jne  =>(*top-1)
        |=>(*top-2):
        break;
    }
  }

  // 函數(shù)尾
  |  pop  PTR
  |  ret

  void (*fptr)(char*) = jitcode(&state);
  char *mem = calloc(30000, 1);
  fptr(mem);
  free(mem);
  free_jitcode(fptr);
  return 0;
}

在這個程序中妹懒，我們真正看到了DynASM方法的閃光之處。我們可以用混合C代碼和匯編代碼的方法編寫一個漂亮的易讀的的代碼生成器双吆。

與早前我提到過的Berkeley Packet Filter JIT進行比較眨唬。它的代碼生成器也有一個相似的結構（一個以字節(jié)碼作為case的大的switch()語句），但是沒有DynASM代碼就必須手動指定指令編碼好乐。而它的符號指令本身僅被包含作為注釋匾竿，讀者必須假的這是正確的。在Linux內核中的arch/x86/net/bpf_jit_comp.c:

    switch (filter[i].code) {
    case BPF_S_ALU_ADD_X: /* A += X; */
            seen |= SEEN_XREG;
            EMIT2(0x01, 0xd8);              /* add %ebx,%eax */
            break;
    case BPF_S_ALU_ADD_K: /* A += K; */
            if (!K)
                    break;
            if (is_imm8(K))
                    EMIT3(0x83, 0xc0, K);   /* add imm8,%eax */
            else
                    EMIT1_off32(0x05, K);   /* add imm32,%eax */
            break;
    case BPF_S_ALU_SUB_X: /* A -= X; */
            seen |= SEEN_XREG;
            EMIT2(0x29, 0xd8);              /* sub    %ebx,%eax */
            break;

這個JIT如果使用DynASM似乎會受益很多蔚万，但是可能會存在一些外部影響阻止使用它岭妖。舉個例子，構建時依賴Lua對于Linux開發(fā)者來說可能是不可接受的反璃。如果DynASM預處理后的文件被檢入Linux的git倉庫昵慌，這將避免依賴Lua除非JIT實際上發(fā)生改變，但是即使這樣對于Linux構建系統(tǒng)標準來說淮蜈，這也是多此一舉废离。在任何情況下，我們的方法都比這個JIT給力礁芦。

有幾件關于我們的BF JIT我應該解釋一下蜻韭，因為它比前一個實例使用了更多的DynASM特性。首先柿扣，你會注意到我們使用.define規(guī)則為rbx寄存器定義別名PTR肖方。這是相當間接地讓我們指定我們預先分配的寄存器并用符號引用寄存器。這需要我們稍微注意未状，任何引用PTR和rbx的代碼都會掩蓋一個事實俯画，它們是相同的寄存器！在JIT中我不止一次遇到像這樣棘手的bug了司草。

其次艰垂，你會看到我用.macro定義了一個DynASM宏泡仗。一個宏就是一組DynASM代碼，它將替換任何調用這個宏的代碼猜憎。

我們在這里看到的最后一個新的DynASM特性是pc標簽娩怎。DynASM支持三種不同的標簽，我們可以用于分支目標胰柑。pc標簽是最靈活的截亦，因為我們可以在運行時調整它的值。每一個pc標簽都是被一個無符號的整型（unsigned int）所標識的柬讨，他被用來定義標簽并跳轉到它崩瓤。每一個標簽都必須在[0, maxpc)范圍內，但是我們可以通過調用dasm_growpc()來增長maxpc踩官。DynASM存儲pc標簽作為一個動態(tài)數(shù)組却桶，但我們不必擔心會過于頻繁的增長，因為DynASM是以指數(shù)級的方式增長分配的內存的蔗牡。DynASM pc標簽是由語法=>labelnum定義和引用的颖系，這里的labelnum可以是一個任意的C表達式。

最后一個注意我們的BF JIT蛋逾。我們生成的代碼是非常簡單和優(yōu)雅的集晚，應該也是非常高效的窗悯，但不是最高效的区匣。特別是，因為我們沒有寄存器分配器蒋院，我們總是直接從內存中讀寫單元值亏钩，而不是緩存他們到寄存器中。如果我們需要壓榨出更多的性能欺旧，我們希望有種方法可以分配寄存器和進行其他的優(yōu)化姑丑。比較了獲得的各種方法的相對性能，我運行了一個快而亂的基準測試通過這幾種不同的BF實現(xiàn)：

• brainf*ck.c辞友，一個用C語言編寫的簡單的未經(jīng)過優(yōu)化的解釋器栅哀。
• bff，一個適當優(yōu)化的brainf*ck解釋器称龙。
• bf2c.hs留拾，一個BF到C語言的編譯器，然后我使用gcc（應用了寄存器分配和其他優(yōu)化）編譯生成的C代碼鲫尊。

我使用mandelbrot.bf作為測試程序痴柔，它打印文本渲染Mandelbrot集合。我得到的最終結果是：

所以疫向，盡管我們的JIT擊敗了優(yōu)化的解釋器大約65%咳蔚，它仍然不敵優(yōu)化的編譯器豪嚎。DynASM仍然是絕對適合的即使是性能最高的JIT編譯器（像LuaJIT），但是要達到那么快你必須更積極的優(yōu)化在執(zhí)行代碼生成步驟之前谈火。

總結

我原本打算再提供一個實例：ICFP 2006年競賽中的一個JIT侈询，描述一個虛擬機規(guī)范叫做通用機器，據(jù)說它被一個程序員稱為“綁定變量的狂熱者”的虛擬遠古社會所使用堆巧。在一段時間內妄荔，這個問題一直是我最喜歡的，并且受到早前的印象讓我激起對于虛擬機的興趣谍肤。這是如此有趣的問題以至于我真的很想有一天為它寫一個JIT啦租。

不幸的是，我已經(jīng)花了太長的時間在這篇文章上荒揣，并且遇到了障礙（像通用機器的技術報告的參考規(guī)范就使我崩潰篷角，這將使性能比較困難）。這顯然也是一個更復雜的任務系任，主要是因為這個虛擬機允許自修改代碼恳蹲。BF是容易的，因為代碼和數(shù)據(jù)被分離并且在程序執(zhí)行的時候可以改變程序俩滥。如果自修改代碼被允許嘉蕾，你必須重新生成代碼在它改變時，如果你試圖將新代碼修補到已存在的代碼序列中霜旧，這將會特別困難错忱。當然有這樣做的方法，這只是一個更復雜的任務而已挂据，總有一天會需要一個單獨的博客文章以清。

因此，盡管今天我沒有帶給你通用機器的JIT崎逃，你也可以查看一個現(xiàn)存使用DynASM的實現(xiàn)掷倔。它是32位x86平臺的，不是x86-64平臺的个绍，并且在它的README中描述了其他的限制勒葱，但是它可以給你一個問題是什么樣的以及一些自修改代碼的不同的感覺。

也許還有更多的DynASM特性我們沒有提到巴柿。一個特別新穎的特性是typemaps凛虽，它讓你用符號計算結構體成員的有效地址（例如，如果你有一個struct timval*在一個寄存器中篮洁，你可以通過編寫TIMEVAL->tv_usec來計算tv_usec成員的有效地址）涩维。這使得它更容易從你生成的匯編與基于C語言的結構體進行交互。

DynASM真的是一個漂亮的作品，但是它沒有太多的問題——你必須足夠聰明從實例中學習瓦阐。我希望這篇文章可以讓你降低學習曲線蜗侈，并證明JIT真的可以有“Hello, World”程序可以以一個非常小的代碼量來做一些有趣和有用的事情。并且對于合適的人睡蟋，他們也可以有很多興趣來編寫踏幻。