目标代码生成及代码优化基础¶

1 二者在编译程序中的逻辑位置¶

典型的编译程序将编译过程划分为 前端 （词法分析、语法分析、语义分析）、中端 （中间代码生成、机器无关代码优化）和 后端 （目标代码生成、针对机器代码优化）三个层次。

目标代码生成与代码优化处在编译流程的 后端 阶段，直接面向目标机器，是决定生成代码质量的关键环节。

2 基本块、流图和循环¶

2.1 基本块¶

入口语句 包括三类：

• 程序的第一个语句
• 条件转移语句或无条件转移语句的转移目标语句
• 紧跟在条件转移语句后面的语句

2.2 划分基本块的算法¶

针对三地址码（TAC），划分基本块分两步：

1. 求出 TAC 程序之中各个基本块的入口语句
2. 对每一入口语句，构造其所属的基本块 — 由该语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成

凡未被纳入某一基本块的语句，都是控制流程无法到达的语句，可以删除。

2.3 流图¶

2.4 循环¶

支配结点集¶

自然循环¶

3 数据流分析基础¶

3.1 概述¶

数据流信息收集的主要途径是 建立和求解数据流方程（data-flow equation）。

典型的数据流方程（以面向基本块的某种正向数据流为例）：

其含义为：基本块 \(S\) 出口处的数据流信息（\(\text{out}[S]\)）或者是 \(S\) 内部产生的信息（\(\text{gen}[S]\)），或者是从 \(S\) 开始处进入（\(\text{in}[S]\)）但在穿过 \(S\) 的控制流时未被杀死（killed）的信息。

3.2 到达-定值数据流分析¶

数据流方程：

其中：

• \(P[B]\) 为 \(B\) 的所有前驱基本块
• \(\text{GEN}[B]\) 为 \(B\) 中定值并可到达 \(B\) 出口处的所有定值点集合
• \(\text{KILL}[B]\) 为 \(B\) 之外的能够到达 \(B\) 的入口处、且其定值的变量在 \(B\) 中又重新定值的那些定值点的集合
• \(\text{IN}[B]\) 为到 \(B\) 入口处各变量的所有可到达的定值点的集合
• \(\text{OUT}[B]\) 为到达 \(B\) 出口处各变量的所有可到达的定值点的集合

数据流方程求解算法¶

算法 3.1（到达-定值数据流方程求解）¶

求解举例¶

3.3 活跃变量数据流分析¶

数据流方程：

其中：

• \(S[B]\) 为 \(B\) 的所有后继基本块
• \(\text{LiveUse}(B)\) 为 \(B\) 中被定值之前要引用变量的集合
• \(\text{Def}(B)\) 为在 \(B\) 中定值的且定值前未曾在 \(B\) 中引用过的变量集合
• \(\text{LiveIn}(B)\) 为 \(B\) 入口处为活跃的变量的集合
• \(\text{LiveOut}(B)\) 为 \(B\) 的出口处的活跃变量的集合

求解算法¶

算法 3.2（活跃变量数据流方程求解）¶

3.4 向前流与向后流¶

3.5 UD 链与 DU 链¶

UD 链的计算（借助到达-定值数据流信息 \(\text{IN}[B]\)）：

• 如果在基本块 \(B\) 中，变量 \(A\) 的引用点 \(u\) 之前有 \(A\) 的定值点 \(d\)，并且 \(A\) 在点 \(d\) 的定值到达 \(u\)，那么 \(A\) 在点 \(u\) 的 UD 链就是 \(\{d\}\)
• 如果在基本块中，变量 \(A\) 的引用点 \(u\) 之前没有 \(A\) 的定值点，那么 \(\text{IN}[B]\) 中 \(A\) 的所有定值点均到达 \(u\)，它们就是 \(A\) 在点 \(u\) 的 UD 链

(1) x = 5
(2) y = 10
(3) x = y + 2    // y 的 UD 链 → {(2)}，可优化为 x = 12
(4) print(x)

(1) x = 5        // x 的 DU 链为空（后面的 x 被重新定值前未使用），可删除
(2) y = 10
(3) x = y + 2
(4) print(x)

3.6 基本块内变量的待用信息和活跃信息¶

计算步骤（从基本块出口到入口反向扫描每个 TAC 语句 i: A := B op C）：

4 基本块的 DAG 表示（局部优化技术）¶

4.1 DAG 的基本概念¶

4.2 DAG 的构造¶

仅考虑三种形式的 TAC 语句对应的 DAG 子图：

设函数 \(\text{node}(name)\) 返回最近创建的关联于 \(name\) 的结点。构造算法：

1. 若 \(\text{node}(y)\) 无定义，创建标记为 \(y\) 的叶结点；对第一种语句，若 \(\text{node}(z)\) 无定义，同样创建叶结点
2. 对第一种语句：若 \(\text{node}(y)\) 和 \(\text{node}(z)\) 都是常数叶结点，执行 \(y \text{ op } z\)，合并已知量；否则检查是否存在标记为 \(\text{op}\) 且左右孩子为 \(\text{node}(y), \text{node}(z)\) 的结点，若无则创建（删除多余运算）
3. 对第二种语句：类似处理，检查是否存在标记为 \(\text{op}\) 且唯一孩子为 \(\text{node}(y)\) 的结点
4. 对第三种语句：令 \(\text{node}(y)\) 为 \(n\)
5. 从 \(\text{node}(x)\) 的附加标识符表中删除 \(x\)，将 \(x\) 添加到结点 \(n\) 的附加变量名字表中，置 \(\text{node}(x) = n\)（删除无用赋值）

4.3 DAG 构造举例与优化效果¶

DAG 构造过程中自动完成的优化包括：

• 合并已知量：常数运算在编译时求值
• 删除多余运算（公共表达式删除）：相同运算只计算一次
• 删除无用赋值：后续不再使用的赋值被消除
• 复写传播：\(B := A\) 后直接用 \(A\) 替代 \(B\)

5 目标代码生成技术¶

5.1 代码生成要考虑的主要问题¶

目标代码生成需要解决三个核心问题：

1. 指令选择（instruction selection）：为每条中间语言语句选择恰当的目标机指令序列
2. 寄存器分配（register allocation）：充分、高效地使用寄存器
3. 指令调度（code scheduling）：选择好计算的次序，充分利用目标机特性

5.2 指令选择¶

指令代价 的简单模型：假设每条指令在操作数准备好后执行其操作的代价均为 \(1\)，每访问一次内存则增加代价 \(1\)。

5.3 简单的代码生成算法¶

在基本块范围内考虑如何充分利用寄存器，原则包括：

• 尽可能地让变量的值保留在寄存器中，必要时才 spill 到内存
• 尽可能引用变量在寄存器中的值
• 在取值相同的变量间共享寄存器
• 不再被引用的变量所占用的寄存器应尽早释放

算法借助基本块内变量的 待用信息链 和 活跃信息链 来决策。

算法核心数据结构：

• VALUE[R]：描述寄存器 \(R\) 当前存放哪个变量
• lookupReg(V)：查询变量 \(V\) 存放在哪个寄存器中
• allocReg(V)：为变量 \(V\) 分配新的寄存器

算法步骤：

step1：对每个 TAC 语句： - 调用 lookupReg(A) 确定目的寄存器，未分配则调用 allocReg(A) - 调用 lookupReg(B) 和 lookupReg(C) 确定操作数位置，不在寄存器中则分配并用 LD 装入 - 更新 VALUE 数组 - 生成对应目标代码（OP 或 MV） - 若 \(B(C)\) 的现行值不再被引用且非出口活跃变量，释放其寄存器

step2：处理完所有 TAC 语句后，对出口活跃的变量生成 ST 指令存入内存

LD R1, a      ; VALUE[R0]=t
LD R2, b      ; VALUE[R2]=b
SUB R0, R1, R2
MV R1, R2     ; a:=b, VALUE[R1]=a
LD R4, c
SUB R3, R1, R4 ; u:=a-c, VALUE[R3]=u
ADD R1, R0, R3 ; v:=t+u, VALUE[R1]=v
ADD R0, R1, R3 ; d:=v+u, VALUE[R0]=d
ST R0, d      ; 活跃变量存回内存
ST R2, b

allocReg 的 spill 策略：

1. 若有未使用的寄存器，直接分配
2. 若有寄存器存放的变量不再被引用且非出口活跃，复用该寄存器
3. 否则使用 LRU 算法，选择最久未使用的寄存器，将其内容 spill 到内存

5.4 高效使用寄存器 — Ershov 数与 Sethi-Ullman 算法¶

Sethi-Ullman 算法 根据 Ershov 数生成最优（使用最少寄存器）的表达式求值代码。基本策略：优先对需要更多寄存器的子树求值。

5.5 图着色物理寄存器分配¶

寄存器相干图（register-interference graph）：

• 结点：每一个伪寄存器为一个结点
• 边：如果程序中存在某点，一个结点在该点被定义，而另一个结点在紧靠该定值之后的点是活跃的，则在这两个结点间连一条边

对相干图使用 \(k\)（物理寄存器数量）种颜色进行着色，使相邻结点颜色不同。

启发式图着色算法¶

"一个图是否能用 \(k\) 种颜色着色"是 NP-完全问题。常用的启发式 \(k\)-着色算法：

6 代码优化技术¶

6.1 优化的分类¶

依优化范围划分：

依优化侧面划分：指令调度、寄存器分配、存储层次优化、存储布局优化、循环优化、控制流优化、过程优化等。

6.2 窥孔优化¶

工作方式：在目标指令序列上滑动一个包含几条指令的窗口（窥孔），发现不够优化的指令序列，用更短或更有效的指令序列替代。

常见窥孔优化类型：

// 优化前                 // 优化后
(1) LD R0, a             (1) LD R0, a
(2) LD R1, b             (2) MV R1, R0
(3) MV R1, R0

// 优化前                 // 优化后
(1) r2 := 3 * 2          (1) r2 := 6

// 优化前                 // 优化后
(1) r2 := 4              (1) r2 := 4
(2) r3 := r1 + r2        (2) r3 := r1 + 4

(1) x := x + 0    → 可删除
(n) y := y * 1    → 可删除

// 优化前                 // 优化后
      goto L1                   goto L2
      ……                        ……
L1:   goto L2             L1:   goto L2

// 优化前                 // 优化后
      debug := false             debug := false
      if (debug) print …         ……
      ……

x := 2.0 * f   →  x := f + f     // 乘法→加法
x := f / 2.0   →  x := f * 0.5   // 除法→乘法

6.3 局部优化（基本块内）¶

DAG 构造过程中已自动完成的优化：

• 合并已知量
• 删除多余运算（公共表达式删除）
• 删除无用赋值
• 复写传播

6.4 全局优化¶

借助针对流图的数据流分析进行，例如：

• 全局公共表达式删除
• 全局死代码删除（删除从流图入口不能到达的代码）

6.5 循环优化¶

代码外提（code motion）¶

将循环不变量代码从循环体内移到循环体外：

// 优化前                      // 优化后
while (i < limit/2) {         t := limit/2;
    …                         while (i < t) {
}                                 …
                              }

循环不变量 \(x := y + z\) 可以外提的充分条件：

1. 所在结点是循环的所有出口结点的支配结点
2. 循环中其它地方不再有 \(x\) 的定值点
3. 循环中 \(x\) 的所有引用点都是且仅是这个定值所能达到的
4. 若 \(y\) 或 \(z\) 是在循环中定值的，则只有当这些定值点的语句（也是循环不变量）已经被执行过代码外提

或者将条件 1 替换为：要求 \(x\) 在离开循环之后不再是活跃的。

归纳变量优化¶

可针对归纳变量进行的优化：

1. 削弱归纳变量的计算强度：将乘法形式的归纳变量转换为加法形式
2. 删除冗余归纳变量：经强度削弱后，往往可以只在寄存器中保存个别归纳变量，删除其余冗余的归纳变量

7 总结¶