按：本文并没有严格翻译原文，只转述了原文主旨。
构造编译器充满乐趣，伴随着天马行空的想象，严谨的推理和充满智慧的算法，写下一行行代码。但创作编译器也会带来无尽的苦难，无论数学公式多么美妙，无论表达式变换多么神奇，最终都要接轨现实：在最后的最后，总要阅读那堪比垃圾堆的 CPU 标准，然后考虑指令生成和寄存器分配的事情。
寄存器分配耗时很久，即使是经典的线形扫描也需要花费很多时间。那有没有一种方法可以避免寄存器分配，或者至少大幅减少它的时间呢？本文介绍了这样一种方法，叫 Destination-Driven Code Generation (DDCG)，用于跳过寄存器分配阶段，直接在生成指令期间分配寄存器。
接下来，本文将会使用一种简单的数学语言展现这种神奇的算法，这种语言包括几个简单的元素：整数常数、加法和乘法。
# @ir 只是改装过的 dataclass 修饰器，别搭理他们
@ir
class Instr:
# ...
pass
@ir
class Const(Instr):
value: int
def __repr__(self):
return f"{self.var()} = {self.value}"
@ir
class Binary(Instr):
left: Instr
right: Instr
def operands(self):
return (self.left, self.right)
@ir
class Add(Binary):
pass
@ir
class Mul(Binary):
pass
本文中不会尝试折叠这种简单数学语言中的常数，折叠后只剩下一个整数，便没有办法再展示这种分配寄存器的方法了。
如果非要展示一下这门语言的书面表示法，大概是这样：
1 + 2 * 3
是的，只是普通数学算式。
接下来是几行求值器的代码，可以执行这门语言。
def eval_exp(exp):
if isinstance(exp, Const):
return exp.value
elif isinstance(exp, Add):
left = eval_exp(exp.left)
right = eval_exp(exp.right)
return left + right
elif isinstance(exp, Mul):
left = eval_exp(exp.left)
right = eval_exp(exp.right)
return left * right
else:
raise NotImplementedError(f"unexpected exp {exp}")
然后，下面的代码是一个编译器，可以将这门语言编译成 x86-64 的……伪代码。
def naive_compile(exp):
tmp = RCX
if isinstance(exp, Const):
return [X86.Mov(RAX, Imm(exp.value))]
elif isinstance(exp, Add):
right_code = naive_compile(exp.right)
left_code = naive_compile(exp.left)
return [
*right_code,
X86.Push(RAX),
*left_code,
X86.Pop(tmp),
X86.Add(RAX, tmp),
]
elif isinstance(exp, Mul):
right_code = naive_compile(exp.right)
left_code = naive_compile(exp.left)
return [
*right_code,
X86.Push(RAX),
*left_code,
X86.Pop(tmp),
X86.Mul(RAX, tmp),
]
else:
raise NotImplementedError(f"unexpected exp {exp}")
解释一下这个编译器：运算的终极目标是将运算结果写入 RAX 寄存器。
如果表达式是常数，就简单将它放入 RAX。
如果表达式是算式，包括加法算式和乘法算式，规定左子式和右子式的结果都存储在 RAX 中，则先计算左子式，将它的结果暂存于栈顶，然后计算右子式，最后取出缓存在栈顶的左子式的结果，求和或者相乘。
如计算 3 + 4 * 5，流程如下：
首先，这段代码可以视作 (+ 3 (* 4 5))，要计算 +，首先计算左子式。
因为左子式只是常数 3，所以，将 3 加载到 RAX。
RAX = 3
stack = []
第二步，计算右子式 (* 4 5)，为此，要先将 3 暂存于栈顶。
RAX = 3
stack = [3]
要计算 (* 4 5)，先计算左子式 4，则先加载 4 到 RAX。
RAX = 4
stack = [3]
第三步，计算 (* 4 5) 的右子式，即 5，为此，也要先把 4 推入栈顶。
RAX = 4
stack = [3, 4]
然后，将 5 加载到 RAX
RAX = 5
stack = [3, 4]
第四步，取出缓存在栈顶的 (* 4 5) 的左子式的结果，4，完成计算。
RAX = 5
tmp(RCX) = 4
stack = [3]
即
RAX = 5 * 4 = 20
stack = [3]
第五步，取出 (+ 3 (* 4 5)) 的左子式的运算结果，3，完成计算。
RAX = 20
tmp(RCX) = 3
stack = []
即
RAX = 20 + 3 = 23
参见上方 python 代码，为了将数学式子编译成这个计算过程，只需要先编译左子式，然后插入一个暂存于栈的动作，再编译右子式，再插入一个取出曾存于栈中的值的动作，最后完成计算便可。
实际上这基本就是栈机工作的原理。栈机中根本没有RAX，连暂存的动作都消失了，而每一步的计算直接存在栈顶。计算的下一步只需要取出栈顶的两个值，然后求和或者相乘就好了。
那么，这个编译器编译出的代码长什么样呢？先考虑加载常数。
class NaiveCompilerTests(unittest.TestCase):
def _alloc(self, exp):
x86 = naive_compile(exp)
return [str(op) for op in x86]
def test_const(self):
exp = Const(2)
self.assertEqual(
self._alloc(exp),
["X86.Mov(dst=rax, src=Imm(2))"],
)
接下来是算式的编译结果。
class NaiveCompilerTests(unittest.TestCase):
# ...
def test_add(self):
exp = Add(Const(2), Const(3))
self.assertEqual(
self._alloc(exp),
[
"X86.Mov(dst=rax, src=Imm(3))",
"X86.Push(src=rax)",
"X86.Mov(dst=rax, src=Imm(2))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
],
)
def test_mul(self):
exp = Mul(Const(2), Const(3))
self.assertEqual(
self._alloc(exp),
[
"X86.Mov(dst=rax, src=Imm(3))",
"X86.Push(src=rax)",
"X86.Mov(dst=rax, src=Imm(2))",
"X86.Pop(dst=rcx)",
"X86.Mul(dst=rax, src=rcx)",
],
)
指令正确，运行后能得到预期中的结果，但满是浪费运算的push和pop指令。如果能避免只用RAX存储结果，便可以解决这个问题。
以下是更多更复杂的测试。
class NaiveCompilerTests(unittest.TestCase):
# ...
def test_mul_add(self):
exp = Mul(
Add(Const(1), Const(2)),
Add(Const(3), Const(4)),
)
self.assertEqual(
self._alloc(exp),
[
"X86.Mov(dst=rax, src=Imm(4))",
"X86.Push(src=rax)",
"X86.Mov(dst=rax, src=Imm(3))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
"X86.Push(src=rax)",
"X86.Mov(dst=rax, src=Imm(2))",
"X86.Push(src=rax)",
"X86.Mov(dst=rax, src=Imm(1))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
"X86.Pop(dst=rcx)",
"X86.Mul(dst=rax, src=rcx)",
],
)
def test_add_deep(self):
exp = Add(Const(2), Add(Const(3), Add(Const(4), Const(5))))
self.assertEqual(
self._alloc(exp),
[
"X86.Mov(dst=rax, src=Imm(5))",
"X86.Push(src=rax)",
"X86.Mov(dst=rax, src=Imm(4))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
"X86.Push(src=rax)",
"X86.Mov(dst=rax, src=Imm(3))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
"X86.Push(src=rax)",
"X86.Mov(dst=rax, src=Imm(2))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
],
)
这样编译出来的满是栈操作，而 DDCG 可以优化这个问题。
Destination-Driven Code Generation
该方法最初见于这篇论文，这篇论文讲的很清楚，但 Kevin Millikin 的演讲或许更平易近人。后者解释了 JavaScript V8 引擎的第一个编译器中，如何使用这种方法生成指令。原文作者也写了一个简单的编程语言，该语言的编译器也使用了这种方法。
这种方法的核心很简单，与其规定每个子式的结果存储在RAX中，不如在递归编译语法树的时候，将子式的结果的存储的地点告诉递归函数。
本文中暂且只有两种存储结果地点，一种当然就RAX，这里被称作ACCUM，另一种是栈顶。
class Dest:
STACK = 0
ACCUM = 1
因为最终结果仍然需要存储在RAX中，自上而下编译语法树的时候，在最顶层的节点，便要将RAX指定为存储结果的地点。
def ddcg_compile(code):
return _ddcg_compile(code, Dest.ACCUM)
def _ddcg_compile(exp, dst):
tmp = RCX
if isinstance(exp, Const):
return _plug_imm(dst, exp.value)
elif isinstance(exp, Add):
return [
*_ddcg_compile(exp.left, Dest.STACK),
*_ddcg_compile(exp.right, Dest.ACCUM),
X86.Pop(tmp),
X86.Add(RAX, tmp),
*_plug_reg(dst, RAX),
]
elif isinstance(exp, Mul):
return [
*_ddcg_compile(exp.left, Dest.STACK),
*_ddcg_compile(exp.right, Dest.ACCUM),
X86.Pop(tmp),
X86.Mul(RAX, tmp),
*_plug_reg(dst, RAX),
]
else:
raise NotImplementedError(exp)
这版编译器中使用了 plug 函数，这些函数负责将数据挪动到正确的地点。如果数据已经在正确的地点了，便不需要再移动，如果没有，这些函数会插入mov或者push之类的指令。目前这种方法减少了mov的次数——如果确定目标在栈顶可以直接push，不需要先mov到RAX里了。
def _plug_imm(dst, value):
if dst == Dest.STACK:
return [X86.Push(Imm(value))]
elif dst == Dest.ACCUM:
return [X86.Mov(RAX, Imm(value))]
else:
raise NotImplementedError(dst)
def _plug_reg(dst, reg):
if dst == Dest.STACK:
return [X86.Push(reg)]
elif dst == Dest.ACCUM:
if reg == RAX:
return []
return [X86.Mov(RAX, reg)]
else:
raise NotImplementedError(dst)
以下是这种编译器的结果。
class DDCGTests(unittest.TestCase):
def _alloc(self, exp):
x86 = ddcg_compile(exp)
return [str(op) for op in x86]
def test_const(self):
exp = Const(2)
self.assertEqual(
self._alloc(exp),
["X86.Mov(dst=rax, src=Imm(2))"],
)
def test_add(self):
exp = Add(Const(2), Const(3))
self.assertEqual(
self._alloc(exp),
[
"X86.Push(src=Imm(2))",
"X86.Mov(dst=rax, src=Imm(3))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
],
)
def test_mul(self):
exp = Mul(Const(2), Const(3))
self.assertEqual(
self._alloc(exp),
[
"X86.Push(src=Imm(2))",
"X86.Mov(dst=rax, src=Imm(3))",
"X86.Pop(dst=rcx)",
"X86.Mul(dst=rax, src=rcx)",
],
)
def test_mul_add(self):
exp = Mul(
Add(Const(1), Const(2)),
Add(Const(3), Const(4)),
)
self.assertEqual(
self._alloc(exp),
[
"X86.Push(src=Imm(1))",
"X86.Mov(dst=rax, src=Imm(2))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
"X86.Push(src=rax)",
"X86.Push(src=Imm(3))",
"X86.Mov(dst=rax, src=Imm(4))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
"X86.Pop(dst=rcx)",
"X86.Mul(dst=rax, src=rcx)",
],
)
def test_add_deep(self):
exp = Add(Const(2), Add(Const(3), Add(Const(4), Const(5))))
self.assertEqual(
self._alloc(exp),
[
"X86.Push(src=Imm(2))",
"X86.Push(src=Imm(3))",
"X86.Push(src=Imm(4))",
"X86.Mov(dst=rax, src=Imm(5))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
],
)
添加控制流程相关的跳转地点
因为本文解释算法用的语言并不包含任何控制流程，如循环或者条件语句什么的，因此在这里不再展开。详情请参见原论文、V8 引擎源代码，和原文作者设计的语言的源代码。
添加虚拟栈
以下内容和原论文无关，却是进一步优化的关键。
Takashi Kokubun 写的 ruby JIT 编译器教程使用了一个寄存器组成的栈，该方法也适用于 DDCG。
这种方法是这样的，相较于使用push和pop，就好像栈一样，尽可能按照固定顺序使用寄存器。在寄存器用完之后，我们才会真正切换到栈上，使用栈完成接下来的计算。
STACK = ["r8", "r9"]
stack_size = 0
code = []
def push(src):
code = X86.Mov(STACK[stack_size], src)
stack_size += 1
return code
def pop(dst):
stack_size -= 1
return X86.Mov(dst, STACK[stack_size])
原文作者用一种更复杂的方式表现上述代码中的push和pop，但他没有给出具体的代码，包括编译器的代码，因此，我们这里也不再赘述，直接展示最终生成的结果。
class DDCGStackTests(unittest.TestCase):
def _alloc(self, exp):
gen = DDCGStack()
gen.compile(exp)
return [str(op) for op in gen.code]
def test_const(self):
exp = Const(2)
self.assertEqual(
self._alloc(exp),
["X86.Mov(dst=rax, src=Imm(2))"],
)
def test_add(self):
exp = Add(Const(2), Const(3))
self.assertEqual(
self._alloc(exp),
[
"X86.Mov(dst=r8, src=Imm(2))",
"X86.Mov(dst=rax, src=Imm(3))",
"X86.Add(dst=rax, src=r8)",
],
)
def test_mul(self):
exp = Mul(Const(2), Const(3))
self.assertEqual(
self._alloc(exp),
[
"X86.Mov(dst=r8, src=Imm(2))",
"X86.Mov(dst=rax, src=Imm(3))",
"X86.Mul(dst=rax, src=r8)",
],
)
def test_mul_add(self):
exp = Mul(
Add(Const(1), Const(2)),
Add(Const(3), Const(4)),
)
self.assertEqual(
self._alloc(exp),
[
"X86.Mov(dst=r8, src=Imm(1))",
"X86.Mov(dst=rax, src=Imm(2))",
"X86.Add(dst=rax, src=r8)",
"X86.Mov(dst=r8, src=rax)",
"X86.Mov(dst=r9, src=Imm(3))",
"X86.Mov(dst=rax, src=Imm(4))",
"X86.Add(dst=rax, src=r9)",
"X86.Mul(dst=rax, src=r8)",
],
)
def test_add_deep(self):
# This tests pushing and popping beyond the limits of our virtual
# stack.
assert len(STACK_REGS) == 2
exp = Add(Const(2), Add(Const(3), Add(Const(4), Const(5))))
self.assertEqual(
self._alloc(exp),
[
"X86.Mov(dst=r8, src=Imm(2))",
"X86.Mov(dst=r9, src=Imm(3))",
"X86.Push(src=Imm(4))",
"X86.Mov(dst=rax, src=Imm(5))",
"X86.Pop(dst=rcx)",
"X86.Add(dst=rax, src=rcx)",
"X86.Add(dst=rax, src=r9)",
"X86.Add(dst=rax, src=r8)",
],
)
可以看到这确实比之前好了不少，大多数数值直接存储进了寄存器里，这还是寄存器栈中只有两个寄存器的情况。
结语
这就是这种方式的简单介绍。实际上距离真正可用，这种方法还有需要优化的地方，不然编译函数没有递归多少层寄存器就会用尽，编译器不得不使用栈缓存数据。但总的来说这仍不失为一种充满巧思的方法，在 JIT 领域，尤其是 lua 这种语法树层级不会很大的语言中仍有用武之处，并能提供不少的启发。而使用栈缓存的数据的问题，则需要更多考虑溢出时倒腾寄存器的问题，也值得再深入思考。