Translation to Intermediate Code⚓︎

中间表示(intermediate representation, IR) 是一种抽象的机器语言：

• 它表达了目标机器的操作，但不过多涉及具体的机器细节
• 它与源语言的细节无关

编译器中使用了多种不同的中间表示：

• 三地址码（TAC）
• 静态单赋值形式（SSA）
• 控制流图（CFG）
• 抽象语法树（AST）
• 表达式树（IR 树，由 Tiger 编译器使用）

如果直接将源语言翻译成真实的机器码，那将会隐藏模块化和可移植性。

Three-Address Code⚓︎

三地址码(three-address code, TAC) 指的是每条指令中最多只使用三个操作数地址的编码方式。

• 三地址码最基本的指令：x = y op z
• 针对编程语言中的不同结构，需要改变三地址码的形式，比如 t2 = -t1
• 三地址码没有标准形式，原因之一是需要发明新的形式来表达语言中的特殊特性

例子

三地址码的实现：

• 整个三地址指令序列被实现为数组或链表

• 最常见的实现方式是将三地址码实现为四元组(quadruples)：

  • 一个字段表示操作
  • 三个字段表示地址

• 对于需要少于三个地址的指令，某些地址字段会被赋予空值（null）或「空」(empty) 值

  t1 = x > 0
  if_false t1 goto L1
  fact = 1
  label L2
  

  (gt, x, 0, t1)
  (if_f, t1, L1, _)
  (asn, 1, fact, _)
  (lab, L2, _, _)
  

• 其他实现方式：三元组、间接三元组

Intermediate Representation Tree⚓︎

一个好的 IR 具备以下几个特性：

• 便于语义分析阶段生成
• 便于翻译成所有目标机器语言
• 每个结构必须具有清晰简单的含义，以便能够轻松指定和实现 IR 优化转换

抽象语法可能包含具有复杂效果(complex effects, CE) 的指令，机器语言也是如此，但它们的对应关系并不良好。IR 应当足够简单，以便能够拆分抽象语法的复杂指令，然后组合起来形成真正的机器指令。

Translation into IR Trees⚓︎

Expressions⚓︎

在语言中，抽象语法树（AST）表达式 A_exp 的表示有：

• 有返回值的表达式：Ex（适用于 T_exp 指令）
• 无返回值的表达式（例如某些过程调用或 while 表达式）：Nx（适用于 T_stm 指令）

• 布尔值表达式，如 a > b：

  • 条件跳转（Cx）
  • 由 T_stm 指令和一对目标标签组合而成

  Tr_Cx(patchList trues, patchList falses, T_stm stm);
  

由于要等很久后才能知道真正的目的地和虚假的目的地，于是我们列出一个位置列表，其中包含当前填充为 NULL 的位置，这些位置需要在已知 t 时填充为 t；另外再列出所有需要填充为 f 的位置。

有时我们需要将一种表达式转换为另一种等价的表达式。比如在 Tiger 中，语句 flag := (a>b | c<d) 需要将 Cx 类型转换为 Ex 类型，有专门的方法来这种相互转换，比如 toEx(Cx)。针对不同类型的输出表达式使用不同的转换函数。

使用临时寄存器实现 toEx(Cx)：

Simple Variables⚓︎

考虑翻译在当前过程的栈帧中声明的简单变量 v：

其中：

• k：v 在帧内的偏移量
• TEMP fp：帧指针寄存器
• 对于 Tiger 编译器，所有变量的大小相同（整数 / 指针）——即机器的自然字长

要翻译 v，就得知道帧指针(frame pointer) 和字长(word size)。我们在 Frame 模块中添加一个帧指针寄存器 FP 和一个常量，其值为机器的自然字长。

/* frame.h */
...
Temp_temp F_FP(void);
extern const int F_wordSize;
T_exp F_Exp(F_access acc, T_exp framePtr);

• 在 InFrame(k) 中访问 a：F_Exp(a, T_Temp(F_FP())) 返回 MEM(BINOP(PLUS,TEMP FP,CONST(k)))
• 在 InReg(t832) 中访问 a 则直接返回 TEMP t832

我们可将 BINOP(PLUS, e1, e2) 简写为 + (e1, e2)

Array Variables⚓︎

不同的编程语言对数组变量的处理方式不同。

• Pascal：数组变量代表数组内容

  var a,b : array[1..12] of integer; 
  begin 
      b :=a
  end.
  

• C：数组类似于指针常量

  // illegal
  {
      int a[12], b[12]; 
      b = a;
  } 
  
  // legal
  { 
      int a[12], *b; 
      b = a;
  } 
  

• Tiger（如同 Java 和 ML）：数组变量表现为指针

  • 没有像 C 语言那样的命名数组常量
  • 新的数组值通过构造函数创建（并初始化）：t_a[n] of i
    • t_a：数组类型名称
    • n：元素数量
    • i：每个元素的初始值

  let
      type intArray = array of int
      var a := intArray[5] of 0
      var b := intArray[5] of 7
  in b := a
  end 
  

  

Tiger 的记录值也是指针，也就是说记录的赋值是指针赋值，并不复制所有字段。这与 C 语言中的结构体赋值不同，它会复制结构体的所有字段。

Structured L-Values⚓︎

• 左值(l-value)：可以出现在赋值语句左侧的表达式的计算结果

  • 比如 x、p.y 或 a[i+2]
  • 表示一个可被赋值的存储位置
  • 也可以出现在赋值语句的右侧

• 右值(r-value)：只能出现在赋值语句右侧的表达式的计算结果。

  • 比如 a + 3 或 f(x)
  • 不表示一个可赋值的存储位置

整型或指针值是标量，即只有一个组成部分（因此只需要 1 个字大小的空间）。

• 在 Tiger 语言中，所有变量和左值都是标量，且数组或记录变量实际上是指针（一种标量）
• 但在 C 或 Pascal 语言中，存在结构化的左值，比如 C 中的结构体、Pascal 中的数组和记录都不是标量

要将结构化左值翻译成 IR 树，需更新 T_Mem：

T_exp T_Mem(T_exp, int size);
MEM(+(TEMP fp, CONST kn), S)

S：要获取或存储的对象的大小

Subscripting and Field Selection⚓︎

计算 a[i] 的地址：(i − l) * s + a

• l：索引范围的下界
• s：每个数组元素的大小（以字节为单位）
• a：数组元素的基地址

如果 a 是全局变量，且其地址在编译时是常量，则可以在编译时完成减法运算 a – l * s。

类似地，要计算记录 a 中字段 f 的地址：offset(f) + a。

数组变量 a 是一个左值，同样地，数组下标表达式 a[i] 也是左值。要获取 a[i] 的地址，我们需要对 a 的地址进行算术运算，比如 (i − l) × s + a

在 Pascal 编译器中，

• 如果我们将左值 a 翻译成类似左侧 IR 树的形式，就无法对 a 的地址进行算术运算；因此，我们应该将左值 a 翻译成表示其地址的树表达式，就像右侧 IR 树那样
• 这个左值 a 可能会发生什么
  • 某个特定元素可能被下标化(subscripted)，产生一个（更小的）左值，例如 a[i]；一个 + 节点会将 (i − l) * s 加到 a 上
  • 该左值（代表整个数组）可能在需要右值的上下文中使用，例如 b = a；此时，通过对其应用 MEM 运算符，将左值强制转换为右值

在 Tiger 语言中，所有记录和数组的值实际上都是指向记录和数组结构的指针。数组的基地址实际上是指针变量的内容，因此需要使用 MEM。a[i] 的 IR 树如下：

• MEM(e) 表示 a
• s 是字大小
• 假设 l=0

另外，左值应表示为地址（不含顶层 MEM 节点）

• 将左值转换为右值：从该地址取值
• 对左值赋值：向该地址存储

综上，在树形 IR 中，MEM 既表示存储（当用作 MOVE 的左子节点时），也表示取值（在其他情况下使用）。

Arithmetic⚓︎

• 每个整数算术运算符对应一个树运算符

• 树语言没有一元算术运算符

  • 整数的取反：通过从零减去实现；-n => 0 - n
  • 按位取反：通过与全 1 进行 XOR 实现

• 浮点数的取反不能通过从零减去来实现，且许多浮点数表示允许存在负零

• 负零的相反数是正零，反之亦然
• 树语言对一元取反的支持并不完善

Conditionals⚓︎

比较运算符的结果将是一个 Cx 表达式：一个语句 (T_stm) s，它将跳转到任何真目标和假目标上。Cx 表示法的核心在于条件表达式可以轻松地与运算符 & 和 | 结合使用，例如 a > b | c < d。因此，像 x < 5 这样的表达式将被翻译成一个带有以下内容的 Cx：

stm = CJUMP (LT, x, CONST(5), NULLt, NULLf)
trues = {t}
falses = {f}

处理if 表达式（if e1 then e2 else e3）的直接方法：

toCx(e1)
LABEL t
r = toEx(e2)
JUMP join
LABEL f
r = toEx(e3)
JUMP join
...
LABEL join
TEMP r
...

• 如果 e2 和 e3 都是语句（不返回值的表达式），toEx 可以工作，但最好能特别识别这种情况

• 如果 e2 或 e3 是 Cx 表达式，toEx 会产生一堆混乱的跳转和标签

  • 示例：if x < 5 then a > b else 0

  • 简单的方式（视为 Ex）：

    

  • 特别识别这个情况

    • x < 5 转换为 Cx(s1)
    • a > b 将被转换为 Cx(s2)
    

While Loops⚓︎

For Loops⚓︎

Function Call⚓︎

Translation of Declarations⚓︎

Variable Definition⚓︎

Function Definition⚓︎

评论区