跳转至

7 Translation into Intermediate Code 中间代码生成

参考资料:


7.1 中间表示概述

为什么需要IR?- 使用中间介质简化编译的路径种类:

image-20250614181540848

降低复杂性,提升复用性(hinders modularity, hinders portability

三地址码 TAC

核心特点是每条指令最多只包含一个运算符和三个“地址”

image-20250614182633389

例子:

image-20250614182656403

7.2 树形中间表示

中间表示在抽象语法树(AST)和底层汇编指令之间取得一个平衡点。一方面,它像AST一样保留了程序的层次化结构;另一方面,它的节点所代表的操作又非常接近于目标机器的指令,比如内存访问、二元运算等。

IR Tree由两大类节点构成

  • 用于计算值的表达式(Expression, Exp)
  • 用于执行动作的语句(Statement, Stmt)

文法描述:

image-20250614183733596

7.2.1 表达式

节点 (Node) 功能描述 (Description) 示例 (Example)
CONST(i) 整数常量i CONST(42) → 值为42
NAME(n) 符号常量n,通常是一个代码标签(Label),其值为该标签的内存地址 NAME(L1) → 标签L1的地址
TEMP(t) 临时变量t,可以看作是一个虚拟寄存器,在寄存器分配前我们不关心其数量 TEMP(t123) → 临时变量t123中存储的内容
BINOP(o,e1,e2) 对两个子表达式e1和e2应用二元操作o(如加减乘除、位运算等) BINOP(PLUS, TEMP(t1), CONST(1)) → 计算 t1 + 1
MEM(e) 访问内存,e是一个计算地址的表达式,MEM节点既可以表示从内存加载数据(fetch),也可以表示向内存存储数据(store),MEM(e)在左边就是写,在右边就是取 MEM(TEMP(fp)) → 访问帧指针fp所指向地址的内存内容
CALL(f,l) 调用函数f,参数列表为l,f通常是一个NAME节点,l是Exp节点的列表 CALL(NAME(print),[TEMP(t1)]) → 调用 print(t1)
ESEQ(s,e) 顺序组合,先执行语句s(为了其副作用),然后计算表达式e并返回其结果 ESEQ(MOVE(TEMP(t), CONST(1)), TEMP(t)) → (t=1; t),整个表达式的结果是t的值,即1

ESEQ的理解和副作用:

  • s可能会影响e的结果,导致有时候不可交换

  • ESEQ解决了在一个以“表达式求值”为核心的树状结构中,如何优雅地嵌入“产生副作用的语句”

  • 副作用(Side effects) 是指在计算表达式之外,对程序状态产生的任何可观察的改变,最常见的就是修改某个内存单元或临时变量(寄存器)的值
  • a=5这个赋值操作,其主要目的就是产生副作用(改变a的值),它本身不返回值
  • ESEQ(s, e)的语义是:先执行语句s,s的执行是为了其副作用,s本身不返回值。执行完s后,再计算表达式e,整个ESEQ节点的值就是e的值
    • 例如,ESEQ(MOVE(TEMP(a), CONST(5)), BINOP(PLUS, TEMP(a), CONST(5))),会先执行MOVE语句使a的值变为5,然后计算a+5,最终整个表达式的结果是10

7.2.2 语句

用于执行动作、改变状态或控制程序的执行流程,它们本身不返回任何值

节点 (Node) 功能描述 (Description) 示例 (Example)
MOVE(d,s) 将源表达式s计算出的值,移动到目标位置d;d通常是TEMP或MEM节点,如果是MEM节点,表达式通常为MOVE(MEM(e1), e2)形式 - 计算e1,得到地址a,再计算e2,放入地址a MOVE(TEMP(t1), CONST(42)) → t1 = 42
EXP(e) 计算表达式e,但完全忽略并丢弃其计算结果,这通常是为了利用e的副作用 EXP(CALL(NAME(print),...)) → 调用print()函数,不关心其返回值,只为了其打印效果
JUMP(e,labs) 无条件跳转,跳转到由表达式e计算出的地址,e通常是一个NAME节点 JUMP(NAME(L1), [L1]) → goto L1
CJUMP(o,e1,e2,t,f) 条件跳转,比较e1和e2(使用关系操作o),如果结果为真,则跳转到标签t;否则,跳转到标签f CJUMP(LT, TEMP(t1), CONST(0), L1, L2) → if t1 < 0 goto L1 else goto L2
SEQ(s1,s2) 语句序列,按顺序先执行语句s1,然后执行语句s2 SEQ(MOVE(...), JUMP(...)) → 先执行一个赋值语句,再执行一个跳转语句
LABEL(n) 定义标签,将符号名n的值定义为当前指令在内存中的地址,它作为跳转指令的目标。 LABEL(L1) → 定义一个名为L1的标签,相当于汇编中的 L1:

Name是使用这个symbol,比如goto .L,而Label是定义这个symbol,即.L

7.2.3 例子

image-20250614190436846

  • 最外层的SEQ节点将整个代码块串联起来
  • MOVE(TEMP(n), CONST(0)):对应循环前的初始化 n := 0
  • LABEL(HEAD):定义了循环开始的标签,作为循环判断和返回的锚点
  • CJUMP(LT, TEMP(n), CONST(10), BODY, END):这是循环的核心判断。如果 n < 10 为真,跳转到BODY标签;否则,跳转到END标签,退出循环
  • LABEL(BODY):定义了循环体的入口
  • MOVE(TEMP(n), BINOP(ADD, TEMP(n), CONST(1))):这是循环体的内容,对应 n := n + 1
  • JUMP(NAME(HEAD)):循环体执行完毕后,无条件跳转回HEAD标签,进行下一次循环判断
  • LABEL(END):定义了循环结束后的代码位置

7.3 翻译到IR Trees

我们的翻译以tiger文法为例:

image-20250614190728390

7.3.1 翻译框架

我们将AST表达式分为以下三类:

  • Ex - 一个能够计算出结果值的表达式
    • 它应该被翻译成一个Tree.exp节点
    • 例如a + b
  • Nx - 一个不产生任何结果值的语句
    • 它应该被翻译成一个Tree.stmt节点
    • 例如赋值语句 a := b 或一个 while 循环
  • Cx - 一个用于控制流程的条件表达式
    • 它不直接计算出0或1,而是被翻译成一个能够根据条件真假跳转到不同目标标签的Tree.stm
    • 最典型的例子就是 CJUMP

转换:例如,当if语句需要一个条件(Cx),而我们提供了一个x+1Ex)时,Ex -> Cx的转换会自动将x+1的结果与0比较,生成一个CJUMP。反之,当赋值语句需要一个值(Ex),而我们提供了一个x>0Cx)时,Cx -> Ex的转换会生成一段代码,使用一个临时变量,当条件为真时给它赋值1,为假时赋值0,最后返回这个临时变量。

7.3.2 翻译简单变量和数据结构

简单变量访问

在函数中访问一个局部变量,实际上是访问它在当前函数栈帧(Stack Frame中的存储位置,我们通过一个特殊的寄存器——帧指针(Frame Pointer, fp来定位当前的栈帧。

因此,访问一个距离帧指针偏移量为k的局部变量v,其IR Tree表示为 :

\(MEM(BINOP(PLUS,TEMP(fp),CONST(k)))\)

这棵树的含义是:取fp寄存器的值,加上常量偏移k,得到变量的实际内存地址,然后通过MEM节点访问该地址的内容。

静态链接:

对于支持嵌套函数的语言,一个内部函数可能需要访问定义在外部函数中的变量,这通过静态链接(Static Link)实现。访问一个嵌套层级为n的变量,需要沿着静态链进行n次解引用,其IR Tree会形成一个嵌套的MEM结构:

image-20250614195019938

这表示从当前帧指针fp开始,首先找到指向外层函数栈帧的静态链接,然后一层层回溯,直到找到目标变量所在的栈帧,最后加上变量在该帧内的偏移量k_x来访问它。

R值与L值 (R-Values and L-Values)

  • R值 (R-value):指表达式的“值”,通常出现在赋值号的右边,如 a+3。它是一个可以被计算但不能被赋值的量。
  • L值 (L-value):指一个可被赋值的“内存位置”,通常出现在赋值号的左边,如变量x、数组元素a[i]。它也可以出现在右边,此时表示该位置存储的“内容”。

在IR Tree中,MEM节点的角色由其上下文决定:

  • 当作为MOVE(d, s)语句的目标d时,MEM(...)代表一个L值,表示要向这个内存地址存入(Store)数据
  • 当出现在其他任何地方时,MEM(...)代表一个R值,表示要从这个内存地址取出(Fetch/Load)数据

不同语言对L值的处理方式有很大差异:

  • 标量L值 (Scalar L-value):L值所代表的内存位置只包含一个不可再分的数据单元(如一个整数或一个指针)。Tiger语言的设计极大地简化了翻译,因为它规定所有变量都是标量。数组和记录变量本身只存储一个指针,这个指针是标量。
  • 结构化L值 (Structured L-value):L值代表一块包含多个组成部分的内存区域,例如C语言中的结构体或Pascal中的数组。对结构化L值的赋值(如 struct1 = struct2)意味着要拷贝整个数据结构的内容,而不仅仅是一个指针。

Tiger的“一切皆为标量指针”的设计哲学,意味着赋值操作永远是简单的单字(word-sized)拷贝,MEM(e)足以完成所有访存操作。而对于支持结构化L值的语言,编译器在生成IR时必须考虑数据的大小和对齐,可能需要生成特殊的块拷贝(block move)指令。

算术运算

算术运算的翻译相对直接:

  • 二元运算:源语言中的加减乘除等二元运算符,直接映射到BINOP(op, e1, e2)节点
  • 一元运算:IR Tree中没有专门的一元运算节点,一元运算需要被转换为等价的二元运算
    • 一元取负 -x 被翻译为 BINOP(MINUS, CONST(0), e_x),即 0 - x
    • 一元按位取反 ~x 被翻译为 BINOP(XOR, e_x, CONST(-1)),即 x XOR 0xFF..FF

数组下标a[i]访问

数组和记录变量本身都是指针,访问数组元素a[i]需要两步:首先获取数组的基地址,然后计算元素的偏移地址。其IR Tree结构如下:

\(MEM(BINOP(PLUS,MEM(e_a),BINOP(MUL,e_i,CONST(W))))\)

解释:

  1. e_a是表示变量a的表达式,通常是 MEM(+(TEMP(fp), CONST(k_a)))
  2. MEM(e_a)第一次MEM访问。这是为了解引用指针,获取存储在变量a中的值,也就是数组在堆上的基地址
  3. e_i是计算索引i的表达式
  4. BINOP(MUL, e_i, CONST(W)):计算索引偏移。将索引i乘以每个元素的大小W(Word size,例如4字节)
  5. BINOP(PLUS,...):将基地址和索引偏移相加,得到目标元素的最终内存地址
  6. 最外层的MEM(...)第二次MEM访问。访问上一步计算出的最终地址,获取或存入元素的值

记录字段r.f访问

记录字段的访问与数组类似,但偏移量是固定的。如果字段f是记录的第n个字段(从0开始),其偏移量就是n * W。翻译结果为 :

\(MEM(BINOP(PLUS,MEM(e_r),CONST(n∗W)))\)

这里的MEM(e_r)同样是用于获取记录在堆上的基地址。

7.3.3 翻译控制流相关语句

if-else语句

一个if test then stmt1 else stmt2语句会被翻译成如下结构的IR Tree :

1
2
3
4
5
6
7
SEQ(CJUMP(op, e1, e2, t, f),
    SEQ(LABEL(t),
        SEQ(stm1,
            SEQ(JUMP(NAME(join)),
                SEQ(LABEL(f),
                    SEQ(stm2,
                        LABEL(join)))))))

解释:

  1. CJUMP(...):对test表达式进行翻译,生成条件跳转。如果为真,跳到t标签(then分支的入口);如果为假,跳到f标签(else分支的入口)
  2. LABEL(t)stm1then分支的代码
  3. JUMP(NAME(join))then分支执行完毕后,无条件跳转到join标签,跳过else分支
  4. LABEL(f)stm2else分支的代码
  5. LABEL(join)thenelse分支的汇合点,程序从这里继续往下执行

逻辑运算符的短路求值

  • AND: image-20250614201525195
  • OR: image-20250614201542767

while循环

基本框架:

1
2
3
4
5
6
SEQ(LABEL(test),
    SEQ(CJUMP(..., body, done),
        SEQ(LABEL(body),
            SEQ(body_stm,
                SEQ(JUMP(NAME(test)),
                    LABEL(done))))))
  1. LABEL(test):循环判断的入口
  2. CJUMP(...):对循环条件进行判断,若为真跳到body,否则跳到done退出循环
  3. LABEL(body)body_stm:循环体的代码
  4. JUMP(NAME(test)):循环体执行完后,无条件跳回test进行下一次判断
  5. LABEL(done):循环的出口

break则直接跳转到done

例子:

image-20250614201853854

for循环

转换为while循环

image-20250614201926531

7.3.4 函数翻译

函数调用

翻译一个函数调用f(a1,..., an),除了要处理所有参数表达式的求值外,一个关键点是处理支持嵌套函数所必需的静态链接(Static Link),翻译结果为:

\(CALL(NAME(l_f),[sl,a_1,...,a_n])\)

  • 这里的sl就是静态链接
  • 它是一个隐藏的、额外的参数,指向调用者静态父级函数的栈帧
  • 当一个内层函数需要访问外层函数中定义的非局部变量时,它就通过静态链接(以及可能由多个静态链接组成的静态链)逐层回溯,找到定义该变量的栈帧,并从中读取数据

函数声明

  1. 序言 (Prologue):函数开始执行前的一系列准备工作
    • 放置函数标签,使其可以被调用
    • 调整栈指针(sp),为当前函数分配新的栈帧
    • 将返回地址、旧的帧指针(fp)以及任何需要由被调用者保存的寄存器(callee-save registers)压入栈中,以便函数返回时恢复
    • 处理传入的参数,包括将静态链接保存到当前栈帧的特定位置
  2. 函数体 (Body):这是函数的核心逻辑。我们将函数内的表达式(在Tiger中,函数体就是一个表达式)翻译成IR Tree 。
  3. 尾声 (Epilogue):函数返回前的一系列清理工作
    • 将函数的返回值(如果有的话)移动到约定的返回值寄存器中(如eax
    • 从栈中恢复之前保存的被调用者保存寄存器、旧的帧指针和返回地址
    • 重置栈指针,释放当前函数的栈帧
    • 执行返回指令,跳转到之前保存的返回地址,将控制权交还给调用者