第一个JIT编译器
这是一个关于小的JITs(即时编译器)是多么简单和有趣的演示，‘JIT’这个词往往会给你一种深奥的魔法的印象，只有最核心的编译器团队才能创造这个梦想。它让你想到JVM和.NET，庞大的运行时系统和成千上万行的代码。你从来没有看到过像“Hello, World!”这样大小的JIT编译器程序，只需要少量的代码就可以做一些有趣的事情。这篇文章就是试图改变这种现状的。
如果你仔细想想，JIT实际上和一个调用sprintf()的程序没什么不同，JIT不过只是发出机器码，而不是一条像“Hello, World!”的消息。当然，像JVM这样的JIT编译器都是高度复杂的野兽，但那是因为他们实现了一个复杂的平台并且做了很多积极的优化操作。如果我们把事情处理的越简单，那么我们的程序也会更简单。
编写一个简单的JIT编译器最困难的部分是编码指令，这些指令可以被你的目标平台CPU所理解。举个例子，在x86-64平台上，指令push rbp被编码为字节0x55。实现这些编码操作是非常烦躁的并且需要阅读大量的CPU手册，所以我们将跳过那个部分。相反，我们将使用Mike Pall的库DynASM来处理编码。DynASM有一个非常新颖的方法，可以让你混合你将生成的汇编代码和你的JIT编译器的C代码，这可以让你以一种自然的和可读的方式编写JIT编译器。它支持很多CPU架构（在编写本文时已支持x86, x86-64, PowerPC, MIPS和ARM），所以你不太可能受限于硬件的支持。DynASM还出乎意料的小并且也没那么正式。它的整个运行时包含在一个500行的头文件中。
我要先简单的介绍一下我所引用的术语。我把那些执行在运行时生成的机器码的程序称为“JIT”。有些作者会在更特殊的场景中使用这个术语，并且仅认为JIT是混合解释器或编译器在小的代码片段根据需要生成机器码。这些作者将这中更一般的运行时代码生成的技术称为“动态编译”。但是“JIT”是更常见和闻名的术语，并经常被用于不同的场景中，那些不都符合JIT的最严格定义，像Berkeley Packet Filter JIT。
Hello, JIT World!
闲话少说，让我们进入第一个“JIT”。这个和所有其他的程序都在我的GitHub仓库jitdemo。这些代码是特定于Unix平台的，因为它们使用了mmap()，我们将会生成x86-64平台的代码，所以你需要一个处理器和操作系统来支持它。我在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[]) {
// Machine code for:
// mov eax, 0
// ret
unsigned char code[] = {0xb8, 0x00, 0x00, 0x00, 0x00, 0xc3};
if (argc < 2) {
fprintf(stderr, "Usage: jit1 <integer>\n");
return 1;
}
// Overwrite immediate value "0" in the instruction
// with the user's value. This will make our code:
// mov eax, <user's value>
// ret
int num = atoi(argv[1]);
memcpy(&code[1], &num, 4);
// Allocate writable/executable memory.
// Note: real programs should not map memory both writable
// and executable because it is a security risk.
void *mem = mmap(NULL, sizeof(code), PROT_WRITE | PROT_EXEC,
MAP_ANON | MAP_PRIVATE, -1, 0);
memcpy(mem, code, sizeof(code));
// The function will return the user's value.
int (*func)() = mem;
return func();
}
这可能看起来难以相信只有33行代码，但是这是一个正式的JIT。它动态的生成一个函数并运行它，这个函数返回一个运行时指定的整数。你可以这样确定它是否工作：
$ ./jit1 42 ; echo $?
42
你会注意到我必须使用mmap()而不是malloc()来申请内存，从堆中申请内存才是正常的方法。但这是必须的，因为我们需要这段内存是可执行的，这样我们才可以跳转到它来执行而不会导致程序崩溃。在大部分系统上，堆和栈被配置为不可执行，因为如果我们可以随意跳转到堆或栈上，这意味着某些方面会产生问题。更糟糕的是，黑客可以利用缓冲溢出来使用可执行堆栈从而更容易找到安全漏洞。所以，我们通常会避免将任何内存映射为即可写也可执行，在你自己的程序中遵循这条规则也是一个好习惯。在上述代码中我打破了这条规则，但是那只是为了让我们的第一个程序尽可能简单而已。
我还偷工减料没有释放我申请的内存。我们可以很快解决这个问题。mmap()有一个对应的函数munmap()，我们可以使用它将内存释放回操作系统。
你可能会想知道为啥你不能调用一个函数将你从malloc()申请的内存的权限改变呢？以一种完全不同的方式申请可执行的内存听起来似乎挺不靠谱。事实上，有一个函数可以改变你已经占用的内存的权限，这就是mprotect()。但是这些权限仅能被设置在内存页的边界，malloc()可能给你一些从内存页中间划分的内存，你无法完全拥有整个内存页。如果你开始改变内存页的权限，你将影响到任何其他可能会使用这个内存页上内存的代码。
Hello, DynASM World!
DynASM是一个令人深感敬佩的项目LuaJIT的一部分，但是是完全独立于LuaJIT代码的，并且可以单独使用。它包括两部分：
- 一个预处理器，将混合C代码和汇编代码的文件(
*.dasc)直接转化为C代码。- 一个小的运行时系统，链接必须被推迟到运行时执行的C代码。
这个设计是非常好的，因为解析汇编语言和编码机器码的所有的底层复杂的代码都可以用一个高级的，带垃圾收集的语言（Lua）来写，并且Lua只在构建时才需要，运行时不需要依赖Lua。
对于我们的第一个DynASM实例，我将编写一个程序来生成跟我们上一个实例同样的函数。这样我们就可以进行比较，看看这两种方法的区别，并了解DynASM为我们带来了什么。
// DynASM规则.
|.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”的运行时的值被替换到指令的立即数中。
| mov eax, num
| ret
// 链接代码并将它写入可执行内存。
int (*fptr)() = jitcode(&state);
// 调用JIT-ted函数
int ret = fptr();
assert(num == ret);
// 释放机器码
free_jitcode(fptr);
return ret;
}
这不是完整的程序，一些为了初始化DynASM和申请释放可执行内存的辅助功能被定义在dynasm-driver.c中。这个共享的辅助功能代码在我们所有的实例中都是一样的，所以我们这里忽略它。它相当的简单和注释良好在代码仓库中。
观察的关键区别是如何生成指令。我们的.dasc文件可以包含汇编语言，类似于如何编写.S文件。以一个管道符(|)开始的文件会被DynASM解释并且可以包含汇编语言指令或规则。这是一个比我们第一个实例更强大的方法。特别要注意参数之一到我们的mov指令是怎样引用一个C变量的。DynASM知道在生成代码时怎样把这个变量的值带入指令中。
为了了解这是如何实现的，我们可以看看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文件（现在注释掉）中我们写的源码行和用它们生成代码行。“action”列表是DynASM预处理器生成的数据的缓存。它是将被DynASM运行时解释的字节码。它将我们汇编语言指令的直接编码和DynASM运行时用来链接的代码混合并插入我们的运行时的值。在这种情况下，我们的“action”列表中的四个字节被解释为：
- 184 – x86平台
mov eax, [立即数]指令的第一个字节。- 237 – DynASM字节码指令
DASM_IMM_D，表示下一个dasm_put()的参数应该被写为一个四字节的值，这就是完全的mov指令。- 195 – x86平台
ret指令的编码- 255 – DynASM字节码指令
DASM_STOP，表示编码应该终止。
这个“action”缓存在后面会被实际产生汇编指令的部分代码引用。这些指令产生代码行会被替换为dasm_put()调用，并提供"action"缓存的偏移量并传递任何需要被替换到输出（就像我们的运行时值num）中的运行时值。dasm_put()将添加这些指令（带有我们的运行时值num）到缓存中存储在状态中（参考上面定义的#define Dst &state）。
结果就是我们得到了跟我们第一个实例完全一样的效果，但是这一次我们使用的方法让我们编写可以汇编语言。这是一种编写JIT程序的更好的方法。
一个Brainf*ck语言的简单JIT编译器
我们可以选定的最简单的图灵完备语言无疑就是带有奇幻色彩的语言Brainf*ck（以下简称为BF）。BF仅用八个命令就能实现图灵完备（甚至包含I/O）。这些命令可以被认为是一种字节码。
不会比上一个实例复杂多少，我们可以用少于100行C代码（包括我们70行左右的共享的驱动文件）实现全功能的BF JIT编译器：
#include <stdint.h>
|.arch x64
|.actionlist actions
|
|// 使用rbx作为我们的单元指针。
|// 由于rbx是一个被调用-保存寄存器，它将被保存通过调用getchar和putchar
|.define PTR, rbx
|
|// 函数调用的宏。
|// 在我们的目标地址是小于等于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;
// 函数头
| 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.");
// 每个循环获取两个pc标签：在开始和结束。
// 我们存储pc标签偏移量到一个栈中一起链接循环开始和结束。
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;
}
}
// 函数尾
| 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进行比较。它的代码生成器也有一个相似的结构（一个以字节码作为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开发者来说可能是不可接受的。如果DynASM预处理后的文件被检入Linux的git仓库，这将避免依赖Lua除非JIT实际上发生改变，但是即使这样对于Linux构建系统标准来说，这也是多此一举。在任何情况下，我们的方法都比这个JIT给力。
有几件关于我们的BF JIT我应该解释一下，因为它比前一个实例使用了更多的DynASM特性。首先，你会注意到我们使用.define规则为rbx寄存器定义别名PTR。这是相当间接地让我们指定我们预先分配的寄存器并用符号引用寄存器。这需要我们稍微注意，任何引用PTR和rbx的代码都会掩盖一个事实，它们是相同的寄存器！在JIT中我不止一次遇到像这样棘手的bug了。
其次，你会看到我用.macro定义了一个DynASM宏。一个宏就是一组DynASM代码，它将替换任何调用这个宏的代码。
我们在这里看到的最后一个新的DynASM特性是pc标签。DynASM支持三种不同的标签，我们可以用于分支目标。pc标签是最灵活的，因为我们可以在运行时调整它的值。每一个pc标签都是被一个无符号的整型（unsigned int）所标识的，他被用来定义标签并跳转到它。每一个标签都必须在[0, maxpc)范围内，但是我们可以通过调用dasm_growpc()来增长maxpc。DynASM存储pc标签作为一个动态数组，但我们不必担心会过于频繁的增长，因为DynASM是以指数级的方式增长分配的内存的。DynASM pc标签是由语法=>labelnum定义和引用的，这里的labelnum可以是一个任意的C表达式。
最后一个注意我们的BF JIT。我们生成的代码是非常简单和优雅的，应该也是非常高效的，但不是最高效的。特别是，因为我们没有寄存器分配器，我们总是直接从内存中读写单元值，而不是缓存他们到寄存器中。如果我们需要压榨出更多的性能，我们希望有种方法可以分配寄存器和进行其他的优化。比较了获得的各种方法的相对性能，我运行了一个快而乱的基准测试通过这几种不同的BF实现：
- brainf*ck.c，一个用C语言编写的简单的未经过优化的解释器。
- bff，一个适当优化的brainf*ck解释器。
- bf2c.hs，一个BF到C语言的编译器，然后我使用gcc（应用了寄存器分配和其他优化）编译生成的C代码。
我使用mandelbrot.bf作为测试程序，它打印文本渲染Mandelbrot集合。我得到的最终结果是：
| BF实现 | 时间 |
|---|---|
| brainf*ck.c | 1m0.541s |
| bff | 6.166s |
| bf2c | 1.244s |
| jit3 (our JIT) | 3.745s |
所以，尽管我们的JIT击败了优化的解释器大约65%，它仍然不敌优化的编译器。DynASM仍然是绝对适合的即使是性能最高的JIT编译器（像LuaJIT），但是要达到那么快你必须更积极的优化在执行代码生成步骤之前。
总结
我原本打算再提供一个实例：ICFP 2006年竞赛中的一个JIT，描述一个虚拟机规范叫做通用机器，据说它被一个程序员称为“绑定变量的狂热者”的虚拟远古社会所使用。在一段时间内，这个问题一直是我最喜欢的，并且受到早前的印象让我激起对于虚拟机的兴趣。这是如此有趣的问题以至于我真的很想有一天为它写一个JIT。
不幸的是，我已经花了太长的时间在这篇文章上，并且遇到了障碍（像通用机器的技术报告的参考规范就使我崩溃，这将使性能比较困难）。这显然也是一个更复杂的任务，主要是因为这个虚拟机允许自修改代码。BF是容易的，因为代码和数据被分离并且在程序执行的时候可以改变程序。如果自修改代码被允许，你必须重新生成代码在它改变时，如果你试图将新代码修补到已存在的代码序列中，这将会特别困难。当然有这样做的方法，这只是一个更复杂的任务而已，总有一天会需要一个单独的博客文章。
因此，尽管今天我没有带给你通用机器的JIT，你也可以查看一个现存使用DynASM的实现。它是32位x86平台的，不是x86-64平台的，并且在它的README中描述了其他的限制，但是它可以给你一个问题是什么样的以及一些自修改代码的不同的感觉。
也许还有更多的DynASM特性我们没有提到。一个特别新颖的特性是typemaps，它让你用符号计算结构体成员的有效地址（例如，如果你有一个struct timval*在一个寄存器中，你可以通过编写TIMEVAL->tv_usec来计算tv_usec成员的有效地址）。这使得它更容易从你生成的汇编与基于C语言的结构体进行交互。
DynASM真的是一个漂亮的作品，但是它没有太多的问题——你必须足够聪明从实例中学习。我希望这篇文章可以让你降低学习曲线，并证明JIT真的可以有“Hello, World”程序可以以一个非常小的代码量来做一些有趣和有用的事情。并且对于合适的人，他们也可以有很多兴趣来编写。
本文为原文的翻译与整理，阅读原文由此去
