从零开始编写 C 编译器 Chapter 1.3 | Codegen

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

Assembly Generation

Assembly Generate 阶段需要将 AST 转换为 x64 汇编代码。转换过程会按照程序执行顺序遍历 AST，并为每个结点生成对应的汇编指令。由于为了兼容后续生成IR， 我们不会直接将汇编指令输出到文件，而是先构建一个中间数据结构 —— 汇编 AST。

对于汇编 AST，我们采用和 AST 相同的 ASDL 语言来进行定义。

program = Program(function_definition)
function_definition = Function(identifier name, instruction* instructions)
instruction = Mov(operand src, operand dst) | Ret
operand = Imm(int) | Register

每一行都定义了一个结点，表示一个特定的汇编结构。program 表示了整个汇编程序，包含一个函数定义。function_definition 包括两个部分：一个函数名和一个指令列表。instruction* 中的 * 表明该项可能包含多条 instruction。instruction 目前只支持两种指令：Mov(src, dst) 和 Ret。Mov 指令用于将源操作数 src 复制到目标操作数 dst。Ret 无操作数，表示函数返回。Operand 目前只支持两种操作：Imm(int) 整型常量和 Register 寄存器(当然，目前只支持 %rax 寄存器)。

目前的汇编 AST 和 AST 十分相似，我们通过一张表来表明他们的区别：

AST	Assembly AST
Program(func_def)	Program(func_def)
Function(name, body)	Function(name, instructions)
Return(exp)	1. Mov(src, dst) 2. Ret
Constant(n)	Imm(n)

可以看到，AST 中的一个结点可能会生成 多个 汇编 AST 结点(Return(exp) 生成两个 instruction 结点)，且汇编 AST 没有表达式，操作数只能为 寄存器 或 表达式经过计算后的最终值。

Implementation

对于 Assembly AST 的定义，和 AST 十分相似，只需要注意 instruction 即可。

type operand = 
  | Imm of int
  | Register

type instruction = 
  | Mov of operand * operand
  | Ret

type function_definition = 
  | Function of {name : string; instructions : instruction list}

type t = 
  | Program of function_definition

同样采用 递归下降式解析，为每一个类型编写一个 convert 函数。

let convert_exp (Ast.Constant i) = Assembly.Imm i

let convert_statement (Ast.Return e) = 
  let value = convert_exp e in
  Assembly.[Mov (value, Register);  Ret]

let convert_function (Ast.Function {name; body}) = 
  let inst_list = convert_statement body in
  Assembly.Function{name; instructions=inst_list}

let codegen (Ast.Program func_def) = 
  Assembly.Program (convert_function func_def)

将 AST 转换为汇编 AST ，目前来看纯是在 ~脱裤子放屁~。但在后续引入更复杂的语义结构时，这种结构能很容易的生成 IR，方便进行 编译器优化 和 代码生成。

Code Emission

汇编 AST 与最终的汇编代码高度对应，因此 Code Emission 实现特别简单。只需要按照汇编 AST 的结点逐一翻译即可。唯一需要注意的是需要处理平台相关的差异。这里仅考虑 Unix like 的操作系统。

目前遇到的平台差异只有两条：

• 在 Mac OS 中，所有的全局符号前需要加下划线_，例如 main 应该为 _main。
• 在 Linux 中可以在汇编文件末尾添加指令 .section .note.GNU-stack,"",@progbits。

.section .note.GNU-stack 告知链接器此程序不需要可执行栈(non-executable stack)，是一项基本的防御措施。

接下来通过几张表即可表示从汇编 AST 到 Assembly Code 的对应关系。

Assembly top-level construct	Output
Program(func_def)	当为 Linux 平台时，在末尾添加 non-exectuable stack 声明
Function(name, instructions)	.globl <name> <name>: <instructions>

Assembly instruction	Output
Mov(src, dst)	movl <src>, <dst>
Ret	ret

Assembly operand	Output
Register	%eax
Imm(int)	$<int>

Implementation

这部分没啥好说的，遍历一个 AST NODE，将其转换为对应字符串输入文件即可。注意汇编语言的格式，在合适的地方添加制表符 \t。

open Assembly

let show_operand = function
  | Register -> "%eax"
  | Imm i -> Printf.sprintf "$%d" i

let show_label name = 
  match !Settings.platform with
  | OS_X -> "_" ^ name
  | Linux -> name

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

let emit_function chan (Function {name; instructions}) = 
  let label = show_label name in
  Printf.fprintf chan {|
  .globl %s
%s:
  |} label label;
  List.iter (emit_instruction chan) instructions

let emit_stack_note chan = 
  match !Settings.platform with
  | OS_X -> ()
  | Linux -> Printf.fprintf chan "\t.section .note.GNU-stack,\"\",@progbits\n"

let emit assembly_file (Program function_def) = 
  let output_channel = open_out assembly_file in
  emit_function output_channel function_def;
  emit_stack_note output_channel;
  close_out output_channel

至此，我们的编译器能编译一个 最简 C 程序了，尽管它比 “Hello World” 还简单，但是这是从 $0$ 到 $1$ 的第一步。

结合 Compiler Driver 得到最终可执行文件，看看是否正确 return 了 $2$。

./main.exe return_2.c 
./return_2
echo $?