从零开始编写 C 编译器 Chapter 2.2 | Intermediate Representation

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

我们成功生成了一元运算符的 AST，但将 AST 转换成 Assembly AST 却明显不如上一章简单。AST 中的 exp 结点拥有递归结构，而 Assembly AST 中的 operand 和 instruction 结点无法直接表达这种结构。我们需要将嵌套的表达式，通过一系列的 中间变量 拆解成一条条的汇编语句。这时，一种介于 C 程序和 x86 汇编中间的表达形式就呼之欲出。

TACKY IR

IR (Intermediate Representation) 是编译器架构中的核心中间层表示。它将高级语言程序转换为与 机器无关、结构规整、的较低级表示，但又不像汇编语言那样直接控制硬件细节。作为编译优化和代码生成的基础载体。

一般 IR 都采用三地址码结构(Three-Address Code, TAC)，每一条指令至多 \(1\) 个运算符和 \(3\) 个操作数，例如 add src1, scr2, dst。操作数一般为两个源操作数和一个目标操作数。每条指令的操作数只能是常量或变量，不能是嵌套表达式。为处理嵌套表达式，需要引入临时变量存储中间结果。例如 return 1 + 2 * 3 的 TACKY 表示为：

tmp.0 = 2 * 3
tmp.1 = 1 + tmp.0
return tmp1

使用 IR 可以消除嵌套表达式，进一步的将 Codegen 阶段分为多个小型、简单的阶段。IR 还能提供简单、统一的结构，便于分析程序特性，例如：此表达式的结果是否被使用？此变量是否始终具有相同值。编译器可以通过分析这些特性来对代码进行优化。此外，IR 还可以作为多种语言的共同目标和多种目标架构的共同起点。例如 LLVM 提供了统一的后端，只需要将不同语言解析生成 LLVM IR 即可完成编译器的编写。

Nora Sandler 设计了一种简单的 IR 形式 —— TACKY，使用 ASDL 可以定义为如下结构：

program = Program(function_definition)
function_definition = Funcion(identifier, instruction* body)
instruction = Return(val) | Unary(unary_operator, val src, val dst)
val = Constant(int) | Var(identifier)
unary_operator = Complement | Negate

TACKY 的定义特别像上一章的 Assembly AST，我们可以叫他 TACKY AST。val 只能为常量 Consttant(int) 或寄存器的标识符 Var(identifier)。由于 TACKY 应该机器无关，所以这里的 identifier 可以是任意不重复字符串，而不用限制于 %rax 等 ABI 规定的寄存器名称。

Unary 为三地址码，其中的dst 的类型必须是临时变量 Val(regisiter) 而不能是 Constant。因为诸如 notq $1, $2 这样的指令是不合逻辑的，不能将一个常数复制给另一个常数。

从 AST 转换为 TACKY AST 也同样是使用递归下降解析。需要注意的是，对表达式需要从最内层表达式开始，逐层向外处理，为每个子表达式结果创建唯一临时变量，并将其转换为 instruction 列表。例如：

Example 1: return ~2:

AST: Return(Unary(Complement, Constant(2)))
↓
TACKY:
  Unary(Complement, Constant(2), Var("tmp.0"))
  Return(Var("tmp.0"))

Example 2: return -~(-8):

AST: Return(Unary(Negate, 
        Unary(Complement, 
            Unary(Negate, Constant(8)))))
↓
TACKY:
  Unary(Negate, Constant(8), Var("tmp.0"))
  Unary(Complement, Var("tmp.0"), Var("tmp.1"))
  Unary(Negate, Var("tmp.1"), Var("tmp.2"))
  Return(Var("tmp.2"))

伪代码如下：

emit_tacky_for_exp(e, instructions):
    match e with
    | Constant(c) ->
        return Constant(c)
    | Unary(op, inner) ->
        src = emit_tacky_for_exp(inner, instructions)
        dst_name = make_temporary()
        dst = Var(dst_name)
        tacky_op = convert_unop(op)
        instructions.append(Unary(tacky_op, src, dst))
        return dst

make_temporary 返回一个唯一的、未被使用过的临时变量名。递归的处理 inner_exp，并通过 make_temporary 保存在一个变量中，形成一个指令数组，这样解析完了嵌套表达式。

对于 return 语句，只需要调用 emit_tacky_for_exp 处理返回值，并在生成的 instruction list 后插入 Return Val 即可。

Implementation

OCaml 的实现几乎和伪代码相同，这里不做赘述。

lib/tacky.ml

type reg = AX | R10
type operand = Imm of int | Reg of reg | Pseudo of string | Stack of int
type unary_operator = Neg | Not

type instruction =
  | Mov of operand * operand
  | Unary of unary_operator * operand
  | AllocateStack of int
  | Ret

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

type t = Program of function_definition

lib/tacky_gen.ml

module T = struct
  include Tacky
end

let convert_op = function
  | Ast.Complement -> T.Complement
  | Ast.Negate -> T.Negate

(* return a T.instruction list * T.Var *)
let rec emit_tacky_for_exp = function
  | Ast.Constant c -> ([], T.Constant c)
  | Ast.Unary (op, inner) ->
      let instrs, src = emit_tacky_for_exp inner in
      let dst = T.Var (Unique_ids.make_temporary ()) in
      let tacky_op = convert_op op in
      let tacky_node = T.Unary { op = tacky_op; src; dst } in
      (tacky_node :: instrs, dst)

(* return a instructions list.
   ocaml lists only support head insertion, we need reverse
   the list returned by exp *)
let emit_tacky_for_statement (Ast.Return exp) =
  let instr_lst, value = emit_tacky_for_exp exp in
  (T.Return value :: instr_lst) |> List.rev

let emit_tacky_for_function (Ast.Function { name; body }) =
  let instr_lst = emit_tacky_for_statement body in
  T.Function { name; body = instr_lst }

let tacky_gen (Ast.Program fn_def) = T.Program (emit_tacky_for_function fn_def)