第九章机器无关优化

9.1 概述

代码优化

在目标代码中消除不必要的指令，或者把一个指令序列替换为一个完成同样功能的较快的指令序列

9.2 基本块和流图

9.2.1 基本块

会画！也会考概念！

中间代码的流图表示法

中间代码划分成为基本块 (Basic block)，基本块的特点：

控制流只能从基本块的第一条指令进入

除基本块的最后一条指令外，控制流不会跳转/停机

流图的结点是基本块，流图的边指明了哪些基本块可以跟在一个基本块之后运行

基本块划分

输入：三地址指令序列

输出：基本块的列表

可能会考基本块划分

方法：

确定首指令leader (基本块的第一个指令)：

第一个三地址指令

任意一个(条件或无条件) 转移指令的目标指令

紧跟在一个(条件或无条件) 转移指令之后的指令

确定基本块：

每个首指令对应于一个基本块：从首指令开始到下一个首指令

后续使用信息

变量值的使用

i：x = … 对x赋值

j：y = x op z j语句的运算分量为x

且从i 开始有一条路径到达j，且路径上没有对x 赋值，那么j 就使用了i 处计算得到的x的值z

我们说变量x 在语句i 后的程序点上活跃：

程序执行完语句i 时，x 中存放的值将被后面的语句使用

不活跃是指变量的值不会被使用，而不是变量不会被使用

这些信息可以用于代码生成：

如果x在i处不活跃，且x占用了一个寄存器，我们可以把这个寄存器用于其它目的

如何计算活跃性与后续使用信息？

输入

基本块B，开始时B中的所有非临时变量都是活跃的

输出

各个语句i上变量的活跃性、后续使用信息

方法

从B的最后一个语句开始反向扫描

对于每个语句i：x = y + z

令语句i 和x、y、z 的当前活跃性信息/使用信息关联

设置x 为“不活跃”和“无后续使用”

设置y 和z 为“活跃”，并指明它们的下一次使用设置为语句i

9.2.2 流图

流图可以作为优化的基础
① 它指出了基本块之间的控制流
② 可以根据流图了解到一个值是否会被使用等信息

流图的构造

1. 流图的结点是基本块

两个结点B 和C之间有一条有向边 iff（当且仅当）基本块C的第一个指令可能在B 的最后一个指令之后执行

2. 存在边的原因：

B 的结尾指令是一条跳转到C 的开头的条件/无条件语句

C 紧跟在B 之后，且B 的结尾不是无条件跳转语句

我们称B 是C 的前驱，C 是B 的后继

3. 入口/出口结点：

不和任何中间指令对应

入口到第一条指令有一条边

任何可能最后执行的基本块到出口有一条边

循环

程序的大部分运行时间花费在循环上，因此循环是识别的重点 (优化的目标)

循环的定义：

循环L是一个结点集合

存在一个循环入口 (Loop entry) 结点，是唯一的、前驱可以在循环L之外的结点，到达其余结点的路径必然先经过这个入口结点

其余结点都存在到达入口结点的非空路径，且路径都在L中

9.3 全局优化

会让列出几个常用手段，要会列出！记住概念！！！

检查信息如何在一个程序的多个基本块之间流动

全局公共子表达式、复制传播、死代码消除、代码移动、归纳变量和强度消减

9.3.1 优化的主要来源

1. 全局公共子表达式

如果E

在某次出现之前必然已被计算过，且

E的运算分量在该次计算后没有被改变

那么，E的本次出现就是一个公共子表达式

如果上次E值赋给了x，且x值没有被修改过，那么我们可使用x，而无需计算E

2. 复制传播

形如u =v的复制语句使得语句后面的程序点上u的值等于v的值

如果在某个位置上u一定等于v，那么可以把u替换为v

有时可以彻底消除对u的使用，从而消除对u的赋值语句

消除公共子表达式时引入了复制语句

如果尽可能用t来替换c，可能就不需要c=t这个语句

3. 死代码消除

如果一个变量在某个程序点上的值可能会在之后被使用，那么这个变量在这个点上活跃的；否则这个变量就是死的，此时对该变量的赋值就是没有用的死代码

死代码多半是因为前面的优化而形成的

4. 代码移动

循环中的代码会被执行很多次

循环不变表达式：循环的同一次运行的不同迭代中，表达式的值不变

把循环不变表达式移动到循环入口之前计算可以提高效率

循环入口：进入循环的跳转都以这个入口为目标

5. 归纳变量和强度消减

归纳变量

每次对x赋值都使x增加c

归纳变量可以通过每次迭代进行一次简单的增量运算（加法或减法）来计算。

强度消减

把一个高代价的运算（比如乘法）替换为一个代价较低的运算（比如加法）

如果一组归纳变量的值的变化保持步调一致，可以将这组变量删剩一个。

处理循环时，可按照“从里到外”的方式进行工作。

9.3.2 数据流分析

数据流分析

用于获取数据沿着程序执行路径流动信息的相关技术

是优化的基础

数据流抽象

程序点

三地址语句之前或之后的位置

基本块内部：一个语句之后的程序点等于下一个语句之前的程序点

如果流图中有B1到B2的边，那么B2的第一个语句之前的点可能紧跟在B1的最后语句之后的点后面执行

从p1到pn的执行路径：p1, p2, …, pn

要么pi是一个语句之前的点，且pi+1是该语句之后的点

要么pi是某个基本块的结尾，且pi+1是该基本块的某个后继的开头

出现在某个程序点的程序状态

在某个运行时刻，当指令指针指向这个程序点时，各个变量和动态内存中存放的值

指令指针可能多次指向同一个程序点，因此一个程序点可能对应多个程序状态

数据流分析把可能出现在某个程序点上的程序状态集合总结为一些特性

不管程序怎么运行，当它到达某个程序点时，程序状态总是满足分析得到的特性

不同的分析技术关心不同的信息

9.4 局部优化

会让列出几个常用手段，要会列出！记住概念！！！

仅对各个基本块本身进行局部优化

局部公共子表达式、消除死代码、代数恒等式、数组引用、指针赋值和过程调用

9.4.1 基本块的优化

针对基本块的优化可以有很好的效果 (局部优化)

DAG图可反映变量及其值对其他变量的依赖关系

构造算法

①为基本块中出现的每个变量建立结点 (表示初始值)，各变量和相应结点关联

②顺序扫描各三地址指令，进行如下处理：

例：指令x = y op z

为该指令建立结点N，标号为op，令x和N关联

N的子结点为y、z当前关联的结点

例：指令x = y

假设y关联到N，那么x现在也关联到N

③扫描结束后，对所有在出口处活跃的变量x，将x 所关联的结点设置为输出结点

以DAG为基础，对代码进行转换

1. 寻找局部公共子表达式

建立某个结点M之前，检查是否存在一个结点N，它和M具有相同的运算符和子结点 (顺序也相同)

如果存在，则不需要生成新的结点，用N代表M

两个b+c不是公共子表达式，因为两个b的值不一样，在中间过程b被重新赋值了

2. 消除死代码

在DAG图上消除没有附加活跃变量的根结点，即消除死代码

如果图中c、e不是活跃变量 (但a、b是)，则可以删除标号为e、c的结点

3. 基于代数恒等式的优化

4. 数组引用的表示

a[j]可能改变a[i]的值，因此不能像普通运算符一样构造结点

x = a[i] a[j] = y z = a[i]

从数组取值的运算x = a[i]对应于=[]的结点

这个结点的左右子节点是数组初始值a0和下标i

变量x是这个结点的标号之一

对数组赋值的运算a[j] = y对应于[]=的结点

这个结点的三个子节点分别表示a0、j和y

杀死所有依赖于a0的变量

// 如果考的话会再补充

5. 指针赋值和过程调用

通过指针进行取值/赋值：x = *p、*q = y

x使用了任意变量，因此无法消除死代码

*q = y对任意变量赋值，因此杀死了全部其他结点

可通过 (全局/局部) 指针分析部分地解决这个问题

过程调用也类似，必须安全地假设它

使用了可访问范围内的所有变量

修改了可访问范围内的所有变量

从DAG到基本块的重组

重构的方法

每个结点构造一个三地址语句，计算对应的值

结果应该尽量赋给一个活跃的变量

如果结点有多个关联的变量，则需要用复制语句进行赋值

重组规则

注意求值顺序

指令顺序必须遵守DAG中结点的顺序

对数组赋值 (write) 要跟在原来之前的赋值/求值之后

对数组求值 (read) 要跟在原来之前的赋值指令之后

对变量的使用必须跟在所有原来在它之前的过程调用和指针间接赋值之后

任何过程调用或指针间接赋值必须跟在原来在它之前的变量求值之后

即保证

如果两个指令之间相互影响，它们的顺序就不该改变