编译原理教程_10 代码优化和目标代码生成

2024-04-06 10:42:43

文章原理
https://gitee.com/fakerlove/fundamentals-of-compiling

文章目录

10. 代码优化和目标代码生成

10. 代码优化和目标代码生成

10.1 代码优化概念

1) 基本概念

「优化」

对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。
- 等价：不改变程序的运行结果
- 有效：目标代码运行时间短，占用存储空间小

「遵循的原则」

等价原则：优化不应改变程序运行的结果
有效原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小
合算原则：应尽可能以较低的代码取得较好的优化效果

「优化的级别」

局部优化、循环优化、全局优化

2) 优化的种类

「总体列举」

删除多余运算（删除公用子表达式）
合并已知量
复写传播
删除无用赋值
代码外提
强度消弱
变换循环控制条件

原代码

void quicksort(m, n);
int m, n;
{
    int i, j, v, x;
    if(n <= m) return;
    i = m-1, j = n, v = a[n];
    while(1) {
        do i = i+1; while(a[i] < v);
        do j = j-1; while(a[j] > v);
        if(i >= j) break;
        x = a[i], a[i] = a[j], a[j] = x;
    }
    x = a[i], a[i] = a[n], a[n] = x;
    quicksort(m, j); quicksort(i+1, n);
}
123456789101112131415

删除公共子表达式

T1 = 4*i
T2 = 4*i

T1 = 4*i
T2 = T1
12345

复写传播

T4 = T2
T3 = T4 + 1

T4 = T2
T3 = T2 + 1
12345

删除无用赋值

T4 = T2 // T4 无用
T3 = T2 + 1

T3 = T2 + 1
1234

强度削弱

i = i + 1
T2 = 4 * i

i = i + 1
T2 = T2 + 4
12345

删除归纳变量

如下例所示，i、j 可以被 T2、T4 取代，因此删除 i、j

3) 数据流方程

入口活跃变量 = 出口活跃变量 - 被定义的变量 + 被引用的变量

10.2 代码优化技术

10.2.1 局部优化

「局部优化」

局限于基本块范围内的优化

1) 基本块

概述

「基本块」

程序中一顺序执行语句序列，只有一个入口和一个出口。
入口就是第一个语句，出口就是最后一个语句。

「定值 & 引用」

对三地址语句为 x := y + z，称 x 定值并引用 y 和 z

「活跃的」

基本块中的一个名字在程序中的某个给定点是活跃的，指如果在程序中（本基本块 + 其它基本块）它的值在该点以后被引用

划分基本块

一、找出中间语句程序中各个基本块的入口语句（三地址语句）

程序第一个语句
能由条件转移语句或无条件转移语句转移到的语句
紧跟在条件转移语句后面的语句

二、对以上求出的每个入口语句，确定其所属的基本块

入口语句 => 下一入口语句的前一天语句
入口语句 => 转移语句
入口语句 => 停语句

三、凡未被纳入某一基本块中的语句，可以从程序中删除

基本块划分举例

2) 流图

基本块为结点，程序第一条语句所在基本块是首结点
连边
- B2 紧接着 B1 之后执行，且 B1 最后一条语句不是无条件转移语句，则 B1 => B2
- B1 最后一条语句是（无）条件转移语句，转移到 B2 的第一条语句，则 B1 => B2

3) 基本块的 DAG 表示

DAG 扩充

在 DAG 上增加标记和附加信息
- **「叶结点」**以标识符或常数作为标记，表示该结点代表该变量或常数的值
- **「内部结点」**以运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果
- **「附加」**各个结点可能附加一个或多个标识符表示这些变量具有该结点所代表的值

四元式的 DAG 表示

「0型：A := B」(:=, B, -, A)

「0型：goto (s)」(j, -, -, (s))

「1型：A := op B」(op, B, -, A)

「2型：A := B op C」(op, B, C, A)

「2型：A := B[C]」(=[], B, C, A)

「2型：if B rop C goto (s)」(jrop, B, C, (s))

「3型：D[C] := B」([]=, B, D, C)

4) 基本块的优化算法

优化算法概述

一个基本块，可用一个 DAG 来表示
对基本块中每一条四元式代码，依次构造对应的 DAG 图，最后基本块中所有四元式构造出来的 DAG 连成整个基本块的 DAG
具体流程
- 准备操作数的结点
- 合并已知量
- 删除公共子表达式
- 删除无用赋值

示例

「示例」

「优化结果」

构造基本块的 DAG 算法

参考上述示例，引入下述的具体过程。

引入函数 Node，保存和计算 DAG 中标识符与结点的对应关系
对基本块中每一四元式，依次执行以下步骤
1. 准备操作数的结点
2. 合并已知量
3. 删除公共子表达式
4. 删除无用赋值

「1. 准备操作数的结点」

如果 Node(B) 无定义，则构造一标记为 B 的叶结点并定义 Node(B) 为这个结点
- 如果四元式为 0 型（A := B），则记 Node(B) = n，转 4
- 如果四元式为 1 型（A := op B），转 2(1)
- 如果四元式为 2 型（A := B op C）
  - 如果 Node© 无定义，则构造一标记为 C 的叶结点并定义 Node© 为这个结点
  - 转 2(2)

「2. 合并已知量」

如果 Node(B) 是标记为常数的叶结点，转 2(3)，否则转 3(1)
如果 Node(B) 和 Node© 都是标记为常数的叶结点，则转 2(4)，否则转 3(2)
执行 op B（合并已知量），令得到的新常数为 P
- 如果 Node(B) 是处理当前四元式时新构造出来的结点，则删除它
- 如果 Node§ 无定义，则构造一用 P 作标识符的叶结点 n，置 Node§ = n
- 转 4
执行 B op C（合并已知量），令得到的新常数为 P
- 如果 Node(B) 或 Node© 是处理当前四元式时新构造出来的结点，则删除它
- 如果 Node§ 无定义，则构造一用 P 作标记的叶结点 n，置 Node§ = n
- 转 4

「3. 删除公共子表达式」

检查 DAG 中是否已有一结点，其唯一后继为 Node(B)，且标记为 op，即公共子表达式
- 如果没有，则构造该结点 n
- 否则，把已有的结点作为它的结点并设该结点为 n，转 4
检查 DAG 中是否已有一结点，其左后继为 Node(B)，右后继为 Node©，且标记为 op，即公共子表达式
- 如果没有，则构造该结点 n
- 否则，把已有的结点作为它的结点并设该结点为 n，转 4

「4. 删除无用赋值」

如果 Node(A) 无定义，则把 A 附加在结点 n 上并令 Node(A) = n
否则，先把 A 从 Node(A) 结点上的附加标识符集中删除
- 如果 Node(A) 为叶结点，则其 A 标记不删除
- 把 A 附加到新结点 n 上并置 Node(A) = n，转处理下一四元式

「信息总结」

在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标记符
在基本块内被定值并且该值在基本块后面可以被引用的所有标识符，就是 DAG 各结点上的那些标记或者附加标识符

10.2.2 循环优化

循环优化，主要有三大措施：

代码外提
强度消弱
删除归纳变量（变换循环控制条件）

1) 循环不变运算

具体定义
寻找算法
- 反复遍历

2) 代码外提

找到不变运算
检查是否符合代码外提条件
保持次序前提下提出代码
举例

3) 强度消弱

核心思想
- 将程序中执行时间较长的运算转换为执行时间较短的运算
- 例如将乘法换成加法
举例
适用范围
- 强度消弱通常是针对循环控制变量有先行关系的变量赋值进行
- 经过强度消弱后，循环中可能出现一些新的无用赋值
- 对于消弱下标变量地址计算的强度非常有效

4) 删除归纳变量

归纳变量

基本归纳变量、归纳变量的定义

具体算法

具体算法
举例

10.3 目标代码生成概念

1) 任务

将分析、翻译、优化后的中间代码变换成目标代码

2) 输入

源程序的中间表示，以及符号表中的信息
类型检查均已完成

3) 输出

绝对指令代码：能够立即执行的机器语言代码，所有地址已经定位
可重新定位指令代码：机器语言模块，需要与运行程序链接才能执行
汇编指令代码：需要汇编程序转换成可执行机器语言代码

10.4 目标代码生成概念

10.4.1 抽象计算机模型

其中 (M) 表示主存中 M 位置的数据。

其它指令

10.4.2 代码生成

1) 代码生成原则

以基本块为单位生成目标代码
- 依次把四元式的中间代码变换成目标代码
- 在基本块的范围内考虑如何充分利用寄存器
- 进入基本块时，所有寄存器空闲
- 离开基本块时，把存在寄存器中的现行的值存回主存中，释放所有寄存器
- 不特别说明，所有说明变量在基本块出口之后均为非活跃变量
在一个基本块的范围内考虑充分利用寄存器

2) 待用信息和活跃信息

概念解释

活跃信息 - 将来会不会被引用

待用信息 - 将来在什么地方会被引用

符号表示

二元组 (x, x) 表示变量的待用信息和活跃信息
- 第 1 元: i 表示将会在第 i 行被引用、^表示非待用
- 第 2 元: y 表示活跃，^表示非活跃
信息变化
- (x, x) -> (x, x)，用后者更新前者
计算方法

3) 变量地址、寄存器描述

目的

推出 AVALUE、RVALUE 目的：

四元式指令：指令中各变量在将来会被使用的情况
变量：每个变量现行值的存放位置
寄存器：每个寄存器当前的使用情况

概念

AVALUE（变量地址描述数组）
- 动态记录各变量现行值的存放位置
- AVALUE[A] = {R1, R2, A}
RVALUE（寄存器描述数组）
- 动态记录各寄存器的使用信息
- RVALUE[R] = {A, B}

注意，对于四元式 A:=B

如果 B 的现行值在某寄存器 R i R_iR**i 中，则无须生成目标代码
只须在 RVALUE(R i R_iR**i) 中增加一个A，并把 AVALUE(A) 改为 R i R_iR**i

4) 代码生成算法

算法描述

总体流程
寄存器分配算法

算法举例

为基本块生成代码示例

10.4.3 DAG的目标代码

作用：重排中间代码，减少目标代码

算法：

构建 DAG，结点标记写在结点圆圈中，叶结点未编号，内部结点的编号写在各结点下面
倒序填写中间代码编号，找到无父节点的结点，向左进行递归拓扑，遇到子结点或无法拓扑则停止

举例：

中间代码

T1 := A+B
T2 := A-B
F := T1*T2
T1 := A-B
T2 := A-C
T3 := B-C
T1 := T1*T2
G := T1*T3
12345678

DAG图
节点重排

码农公寓