代码优化/改进：
- 在目标代码中消除不必要的指令
- 把一个指令序列替换为一个完成相同功能的更快的指令序列
全局优化：
- 具体的优化实现基于数据流分析技术
- 用以收集程序相关信息的算法
9.1 优化的主要来源
优化的主要来源：
- 冗余运算
- 源程序中的冗余
- 高级程序设计语言编程的副产品
- 语义不变的优化
- 公共子表达式
- 复制传播
- 死代码消除
- 常量折叠
9.1.4 全局公共子表达式
如果$E$在某次出现之前必然已被计算过，且$E$的运算分量在该次计算之后没有被改变，那么$E$的本次出现就是一个公共子表达式。
9.1.5 复制传播
形如$u = v$的复制语句使得语句后面的程序点上，$u$的值等于$v$的值。
- 如果在某个位置上$u$一定等于$v$，那么可以把$u$替换为$v$
- 有时可以彻底消除对$u$的使用，从而消除对$u$的赋值语句
9.1.6 死代码消除
- 如果一个变量在某个程序点上的值可能会在之后被使用，那么这个变量在这个点上是活跃的；否则就是死的，此时对该变量的赋值就是没有用的死代码
- 死代码多半是因为前面的优化而形成的
9.1.7 代码移动
- 循环中的代码会被执行很多次
- 循环不变表达式：循环的同一次运行的不同迭代中，表达式的值不变
- 把循环不变表达式移动到循环入口之前计算可以提高效率
- 如
while (i <= limit - 2)中的limit - 2可以被优化
9.1.8 归纳变量和强度消减
- 每次对$x$赋值都使得$x$增加$c$，则可以把赋值改为增量操作
9.2 数据流分析
数据流分析：用于获取数据沿着程序执行路径流动信息的相关技术是优化的基础
- 两个表达式是否一定计算得到相同的值？
- 一个语句的计算结果是否可能被后续语句使用？
9.2.1 数据流抽象
程序点：三地址语句之前或之后的位置
对于基本块内部，一条语句之后的程序点等于下一个语句之前的语句点。
出现在某个程序点的程序状态：
- 在某个运行时刻，当指令指针指向这个程序点时，各个变量和动态内存中存放的值；
- 指令指针可能多次指向同一个程序点，因此一个程序点可能对应多个程序状态
数据流分析把可能出现在某个程序点上的程序状态集合总结为一些特性：
- 不管程序怎么运行，当它到达某个程序点时，程序状态总是满足分析得到的特性
- 不同的分析技术关心不同的信息
性质和算法：根据不同的需要来设置不同的性质集合，然后设计分析算法
- 程序点上的性质被表示称为数据流值，求解这些数据流值实际上就是推导这些性质的过程
- 例如：到达定值、常量赋值等
9.2.2 数据流分析模式
数据流分析中，程序点和数据流值关联起来：
- 数据流值表示了程序点具有的性质
- 和某个程序点关联的数据流值：程序运行中经过这个点时必然满足的条件（安全）
域：某个数据流所有可能值的集合成为该数据流值的域。不同的应用选用不同的域，比如到达定值。
对一组约束求解，得到各个点上的数据流值。共有两类约束：基于语句语义和基于控制流。
- 基于语句语义的约束：
- 一个语句之前和之后的数据流值收到其语义的约束
- 语句语义通常用传递函数表示，它把一个数据流值映射到另一个数据流值
- 基于控制流的约束
- 在基本块内部，一个语句的输出 = 下一个语句的输入
- 流图的控制流边也对应新的约束
9.2.3 基本块上的数据流模式
基本块内的数据流模式：
- 基本块的效果就是各个语句的效果的复合
- 可以预先处理基本块内部的数据流关系，给出基本块对应的传递函数
- 即$f_B = f_n \circ \dots \circ f_2 \circ f_1$
基本块之间的控制流约束：
- 前向数据流问题：$IN[B]$和$B$的各前驱基本块的$OUT$值之间具有约束关系
- 逆向数据流问题：$OUT[B]$和$B$的各后继基本块的$IN$值之间具有约束关系
数据流方程解的精确性和安全性：
- 数据流方程通常没有唯一解
- 目标是寻找一个最“精确”且满足约束的解
- 精确：能够进行更多的改进
- 满足约束：根据分析结果来改进代码是安全的
9.2.4 到达定值
假设$x$有定值$d$（在$d$处进行了赋值），如果存在一个路径，从紧随$d$的点到达某点$p$，并且此路径上面没有$x$的其他定值点，则称$x$的定值$d$到达$p$。
如果在这条路径上有对$x$的其他定值，我们说变量$x$的这个定值$d$被杀死了。
到达定值的解允许不精确，但必须是安全的：
- 分析得到的到达定值可能实际上不会到达
- 但是实际到达的一定会被分析出来，否则不安全（不能忽略实际的到达定值，但定值过多不会导致不安全）
语句/基本块的传递方程：
- 定值$d: u = v + w$
- 生成了对变量$u$的定值$d$，杀死其他对$u$的定值
- 生成-杀死形式：$f_d(x) = gen_d \cup (x - kill_d)$
- 生成-杀死形式的函数复合仍具有该形式
到达定值的控制流方程：
- 只要一个定值能够沿某条路径到达一个程序点，这个定值就是到达定值
- $IN[B] = \cup_{pred} OUT[P]$
- 如果从基本块$P$到$B$有一条控制流边，那么$OUT[P]$在$IN[B]$中
- 一个定值必然先在某个前驱的$OUT$值中，才能出现在$B$的$IN$中
- $\cup$称为到达定值的交汇运算符
到达定值的迭代算法：
- $OUT[ENTRY] = \emptyset$
- 每次迭代过程更新计算：
- 基本块内部：$OUT[B] = gen_B \cup (IN[B] - kill_B)$
- 基本块之间：$IN[B] = \cup OUT[P]$
9.2.5 活跃变量分析
- 活跃变量的定义：
- $x$在$p$上的值是否会在某条从$p$出发的路径中使用
- 变量$x$在$p$上活跃，当且仅当存在一条从$p$开始的路径，该路径的末端使用了$x$，且路径上没有对$x$进行覆盖
- 用途：寄存器分配、死代码消除、……
- 数据流值：活跃变量的集合
基本块内的数据流方程：
- 基本块的传递函数仍然是生成-杀死形式，但是是从$OUT$值计算$IN$值（逆向）
- $use_B$：在$B$中先于定值被使用
- $def_B$：在$B$中先于使用被定值
活跃变量数据流方程：
- 任何变量在程序出口处不再活跃$IN[EXIT] = \emptyset$
- 对于所有非出口的基本块：
- 基本块内部：$IN[B] = use_B \cup (OUT[B] - def_B)$
- 基本块之间：$OUT[B] = \cup IN[S]$
9.2.6 可用表达式
- $x + y$在$p$点可用的条件：从流图入口结点到$p$的每条路径都对$x + y$求值，且在最后一次求值后没有对$x$或$y$赋值
- 主要用途：寻找全局公共子表达式
- 生成-杀死的定义：
- 生成：基本块求值$x + y$，且之后没有对$x$或$y$赋值，那么它生成了$x + y$
- 杀死：基本块对$x$或$y$赋值，且没有重新计算$x + y$，那么它杀死了$x + y$
计算基本块生成的表达式：
- 初始化$S = {}$
- 从头到尾逐个处理基本块中的指令$x = y + z$
- 把$y + z$添加到$S$中
- 删除任何涉及变量$x$的表达式
- 遍历结束得到基本块生成的表达式集合
计算基本块杀死的表达式：某个分量在基本块中被赋值，并且表达式没有重新被运算
可用表达式的数据流方程：
- 入口结点的出口处没有可用表达式：$OUT[ENTRY] = \emptyset$
- 其他基本块的方程：
- 基本块内部：$OUT[B] = egen_B \cup (IN[B] - ekill_B)$
- 基本块之间：$IN[B] = \cap OUT[P]$
注意此处交汇运算是求前驱$OUT$集合的交集。
9.5 部分冗余消除
目标：尽量减少表达式求值的次数
对于表达式$x + y$：
- 全局公共子表达式
- 循环不变表达式
- 部分冗余：在程序按照某些路径到达这个点的时候$x + y$已经被计算过，但沿着另外一些路径到达这个点时未被计算过
消除冗余的方式：
- 关键边：从具有多个后继的节点到达具有多个前驱的节点的边
- 在关键边上增加基本块并进行代码复制
9.5.5 懒惰代码移动
- 找出各程序点上预期执行的所有表达式
- 在表达式被预期执行但是不可用的程序点上，放置表达式的计算
- 把表达式尽量后延到某个程序点，在到达这个点的所有路径上，这个表达式在这个程序点之前被预期执行，但是还没有使用这个值
- 消除只使用一次的临时变量
Loading Comments By Disqus