目标代码生成

1. Motivation (动机与任务)

目标代码生成是编译器的“最后一公里”，负责将中间代码转化为特定机器上的目标指令。

• 输入：中间代码 (IR) + 符号表 (Symbol Table)。

• 输出：

  • 绝对机器语言 (Absolute Machine Code) - 直接运行。

  • 可重定位机器语言 (Relocatable Machine Code, .obj) - 需链接。

  • 汇编语言 (Assembly) - 需汇编。

• 核心挑战：

  1. 正确性：语义不能变。

  2. 效率：充分利用寄存器（速度最快但资源最少），缩短指令长度。

---

2. Concept (核心概念与模型)

2.1 目标机器模型与开销 (Cost)

这里的Cost指的是内存空间的开销

假设目标机器拥有 个通用寄存器 。

指令开销计算公式：

寻址方式	形式	说明	开销 (Added Cost)	例子 (Cost)
寄存器		速度最快	0	MOV R0, R1 (1+0+0=1)
立即数		常数	1	ADD R0, #5 (1+0+1=2)
直接寻址		内存地址	1	MOV R0, M (1+0+1=2)
间接寻址	或	指针指向的值	0 (若寄存器) / 1 (若内存)	MOV R0, @R1 (1+0+0=1)
变址寻址		数组访问	1	MOV R0, 4[R1] (1+0+1=2)

2.2 关键数据结构

为了跟踪变量和寄存器的状态，维护两张表：

1. 寄存器描述符 (Register Descriptor)

   • What: 寄存器 当前存了谁？

   • Example: 存放了 (说明 a 和 b 的值都在 中)。

2. 地址描述符 (Address Descriptor)

   • What: 变量 的值现在哪里？

   • Example: 存放在 (说明寄存器和内存里都有)。

2.3 活跃性与下次引用 (Liveness & Next-Use)

这是寄存器分配的依据。

• 活跃 (Live)：该变量的值后续还会被用到，不能随便覆盖。

• 下次引用 (Next-Use)：下一次读这个变量是在哪条语句。

  • 策略：如果有两个变量都要抢寄存器，谁的“下次引用”最远，就踢掉谁（贪心策略）。

---

3. Method (核心算法)

3.1 逆序扫描算法 (计算 Next-Use)

方向：从基本块的最后一条语句向前扫描。

逻辑：对于语句 ：

1. 附加信息：把符号表中 当前的“活跃/下次引用”信息记录在语句 上（供后续正向生成代码时查阅）。

2. 更新 x (定值)：

   • 被重新赋值了，所以之前的 值失效。

   • 设置符号表： 为“非活跃”、“无下次引用”。

3. 更新 y, z (引用)：

   • 在这里被使用了。

   • 设置符号表： 为“活跃”、“下次引用为 ”。

3.2 寄存器分配函数 getreg(x := y op z)

这是代码生成的灵魂。我们需要为结果 选一个寄存器 。优先级逻辑如下：

1. 首选：复用 y 的寄存器

   • 条件： 已经在寄存器 中 中只存了 一人 在此之后不再活跃。

   • 动作：直接把 拿来当 用（无需生成 MOV 指令，直接做运算）。

2. 次选：找空闲寄存器

   • 条件：有一个寄存器是空的。

   • 动作：返回该空寄存器。

3. 下策：抢占 (Spilling)

   • 条件：没空位了。

   • 动作：基于“下次引用最远”原则，选一个受害者寄存器 。

   • 生成 MOV M, R_victim (如果需要保存旧值)。

   • 返回 。

3.3 特殊语句翻译 (Detail)

针对数组、指针和跳转的模板：

语句类型	三地址码	目标代码模板 (汇编)	说明
数组取值	x := b[i]	MOV R1, i MOV R2, b[R1] MOV x, R2	若 已在寄存器可省第一步。利用变址寻址。
数组赋值	a[i] := b	MOV R1, i MOV R2, b MOV a[R1], R2	同样利用变址写回。
指针取值	x := *p	MOV R1, p MOV R2, *R1 MOV x, R2	间接寻址。先拿地址，再取内容。
指针赋值	*p := a	MOV R1, p MOV R2, a MOV *R1, R2	将 的值写入 指向的内存。
条件跳转	if x < 0 goto L	CMP x, #0 CJ< L	CJ< 代表 Condition Jump Less。

---

4. Example (详细例题)

例题 1：代码生成全过程追踪

输入：x := a + b * c - d

假设：2 个寄存器 。

分析表格：

步骤	三地址语句	getreg 选择	生成指令 (Target Code)	寄存器描述符 (R0 / R1)	地址描述符 (变化)
1	t := b * c	选 R0 (空)	MOV R0, b MUL R0, c	: {t} : {}	t 在
2	u := a + t	选 R1 (空)	MOV R1, a ADD R1, R0	: {t} : {u}	u 在
3	v := u - d	复用 R1 (u 用完即死)	SUB R1, d	: {t} : {v}	v 在
4	x := v	-	(无指令, 更新描述符)	: {t} : {x}	x 在
5	块结束	-	MOV x, R1	-	x 存回内存

例题 2：Next-Use 逆序扫描

代码片段：

(12) t1 := a - b  
(13) t2 := t1 * 2  
(14) a := t2 + 1  

扫描过程：

1. 处理 (14) a := t2 + 1:

   • 定值 a: 之前的 死掉了 SymTab[a].live = False.

   • 引用 t2: 在这用了 SymTab[t2].live = True, NextUse = 14.

2. 处理 (13) t2 := t1 * 2:

   • 定值 t2: 之前的 死掉 (覆盖了) SymTab[t2].live = False.

   • 引用 t1: 在这用了 SymTab[t1].live = True, NextUse = 13.

3. 处理 (12) t1 := a - b:

   • 定值 t1: 之前的 死掉 SymTab[t1].live = False.

   • 引用 a: 这里的 是入口处的 SymTab[a].live = True, NextUse = 12.