从零开始编写 C 编译器 Chapter 2.3 | Backend

Note: 所有代码、定义、术语命名都参考 Nora Sandler 的书籍 Write a C Compiler

TACKY 是一种接近汇编语言的 IR，但仍不直接对应具体的 x86 指令。为生成可执行的汇编代码，还需要将 TACKY 程序转换为 Assembly AST，再进一步修复不合法的 x86 指令。

Assembly AST

在这节中，我们需要新维护一些东西：function prologue 和 function epilogue、一元运算符、为栈分配空间的 subq 指令。

我们可以采用许多中策略来处理 function prologue/epilogue。可以将这些指令通过一个特别的 Assembly AST 结点来表示。也可以直接将其放在 emit 阶段直接生成。这里采用一个适中的方法：AST 中显式包含 AllocateStack(n) 结点表示 subq $n, %rsp。不直接使用 Sub 结点的原因是，这里的运算符只能是 %rsp 寄存器而不能是任意地址。而对于 push %rbp 等指令，将直接在 emit 阶段生成，因为他们在所有函数中都是固定的，无须在 AST 中重复建模。

对于一元运算符，TACKY 中已经将嵌套表达式解析为指令数组了，我们只需要将其转换为更符合汇编格式的表示即可。TACKY 中使用的是三地址码，而 x86 中为就地运算。

更新后的 Assembly AST 定义如下：

program = Program(function_definition)
function_definition = Function(identifier name, instruction* instructions)
instruction = Mov(operand src, operand dst)
            | Unary(unary_operator, operand)
            | AllocateStack(int)
            | Ret
unary_operator = Neg | Not
operand = Imm(int) | Reg(reg) | Pseudo(identifier) | Stack(int)
reg = AX | R10

operan 中的 Reg 表示两个特定的寄存器，Reg(AX) 在上下文中可表示%rax、%eax或 %al，因为 AST 不因过多保留语法细节。Pseudo 表示临时变量，在后续阶段需要将他们转换为栈地址。 Stack(n) 来表示 -n(%rsp)，即存放 Pseudo 的栈地址。

可以将 Codegen 再次细分为 \(3\) 个阶段：

• TACKY -> Assembly AST (包含临时变量)
• 临时变量 -> 栈地址
• 修复非法指令(双内存操作数)，并计算需要分配的栈大小。

Codegen

转换规则依然可以用几张表来描述。

converting toplevel:

TACKY         =>            Assembly AST             

Program(func_def)           Program(func_def)      
Function(name, instrs)      Function(name, instrs) 

converting instruction:

TACKY        =>        Assembly AST

Return(val)            Mov(val, Reg(AX))
                       Ret

Unary(op, src, dst)    Mov(src, dst)
                       Unary(op, dst)

converting operand:

TACKY        =>        Assembly AST

Constant(n)            Imm(n)

Var(id)                Pseudo(id)

converting unary operator:

TACKY        =>        Assembly AST

Complement             Not
Negate                 Neg

在这个阶段，并未使用 AllocateStack 和 Stack，临时变量仍然保留。

接下来，我们通过维护一个 map，将 String 转换为 Stack offset，即临时变量存储在栈上偏移量，来为每个临时变量分配地址。

分配策略为：按首次出现顺序分配偏移量，即第一个变量 Stack(-4)、第二个 Stack(-8)，第 \(n\) 个 Stack (-4 * n)。并得到最大的偏移量值，供下一阶段使用。

之后修改 Assembly AST，将所有的 Pseudo 转换为 Stack。例如：

Mov(Imm(2), Pseudo("a"))
Unary(Neg, Pseudo("a"))

转换为:

Mov(Imm(2), Stack(-4))
Unary(Neg, Stack(-4))

最后，插入 function prologue/epilogue，并修复非法指令。

对于两个操作数均为内存地址的指令，如 movl -4(%rbp), -8(%rbp)，通过临时寄存器 %10 来进行中转，将 Mov(Stack(s), Stack(d)) 修改为 Mov(Stack(s), Reg(R10)) 和 Mov(Reg(R10), Stack(d))。这里选用 r10 作为中转是因为，r10 寄存器不用于参数传递，不被特殊指令(如 idiv 占用%rax) 占用。

此外，根据 map 中的值，生成 AllocateStack(n)，插入在 instruction list 的末尾，供 emit 阶段生成序言。

Implementation

TACKY 转换到 Assembly AST 很简单

let convert_instruction = function
  | Tacky.Return tacky_val ->
      let asm_val = convert_val tacky_val in
      Assembly.[ Mov (asm_val, Reg AX); Ret ]
  | Tacky.Unary { op; src; dst } ->
      let asm_op = convert_unop op in
      let asm_src = convert_val src in
      let asm_dst = convert_val dst in
      Assembly.[ Mov (asm_src, asm_dst); Unary (asm_op, asm_dst) ]

replace_pseudo 比较有意思。由于函数式中数据结构都是持久化的，且常量不可修改，通过一个 replacement_state 结构体来进行维护，每次更新都返回一个 state。

type replacement_state = {
  current_offset : int; (* last used stack cell *)
  offset_map : int StringMap.t (* a map from int to string(pseudoregister) *);
}

之后对于 Pseudo 操作数，如果在 map 中已经存在了，则直接读出偏移量。如果不存在，更新偏移量和新 map。

let replace_operand state = function
  | Pseudo id -> begin
      match StringMap.find_opt id state.offset_map with
      (* already have assigned this identifier, return Assembly Stack operand *)
      | Some offset -> (state, Stack offset)
      (* have not assgiend it *)
      | None ->
          let new_offset = state.current_offset - 4 in
          let new_map = StringMap.add id new_offset state.offset_map in
          let new_state =
            { current_offset = new_offset; offset_map = new_map }
          in
          (new_state, Stack new_offset)
    end
  | other -> (state, other)

对于 Ret 指令，由于没有操作数，不做任何修改。对于 Mov 指令，需要检查两个操作数。

let replace_pseudo_in_instruction state = function
  | Mov (src, dst) ->
      let state1, new_src = replace_operand state src in
      let state2, new_dst = replace_operand state1 dst in
      let new_mov = Mov (new_src, new_dst) in
      (state2, new_mov)
  | Unary (op, dst) ->
      let state1, new_dst = replace_operand state dst in
      let new_unary = Unary (op, new_dst) in
      (state1, new_unary)
  | Ret -> (state, Ret)

pseudo 在不同函数调用下应该独立，则对每个 function_definition 都初始化 StringMap。需要更新 state 的同时调用 replace_pseudo，采用 fold_left_map 遍历。最终的 state.current_offset 即为需分配的栈大小。

let replace_pseudo_in_function (Function { name; instructions }) =
  let init_state = { current_offset = 0; offset_map = StringMap.empty } in
  let final_state, fixed_instructions =
    List.fold_left_map replace_pseudo_in_instruction init_state instructions
  in
  ( Function { name; instructions = fixed_instructions },
    final_state.current_offset )

指令修改只需要检查是否两个操作数都为 Stack 即可，目前只有 Mov 需要检查。

let fixup_instruction = function
  | Mov ((Stack _ as src), (Stack _ as dst)) ->
      [ Mov (src, Reg R10); Mov (Reg R10, dst) ]
  | other -> [ other ]

一条指令可能会被修改为 instruction list，此时function_definition 中的 instruction list 会变为二维数组。通过 concat_map 拼接一下，并添加 AllocateStack 指令。

let fixup_function last_stack_slot (Function { name; instructions }) =
  Function
    {
      name;
      instructions =
        AllocateStack (-last_stack_slot)
        :: List.concat_map fixup_instruction instructions;
    }

emit

这部分没啥好说的，将 Unary (op, dst) 输出为 notl operand 即可。

let show_unary_instruction = function Neg -> "negl" | Not -> "notl"

let emit_instruction chan = function
  | Mov (src, dst) ->
      Printf.fprintf chan "\tmovl %s, %s\n" (show_operand src)
        (show_operand dst)
  | Unary (op, dst) ->
      Printf.fprintf chan "\t%s %s\n"
        (show_unary_instruction op)
        (show_operand dst)