Skip to content

机器无关优化

  • 目标：
    • 在目标代码中消除不必要的指令
    • 把一个指令序列替换为一个完成相同功能的更快的指令序列
  • 优化的主要来源：通过一些相对低层的语义等价转换来优化代码
    • 公共子表达式消除
    • 复制传播
    • 死代码消除
    • 常量折叠

代码优化常见方法

以快速排序为例进行说明

  • 局部优化：通常是指一个基本块内部的优化，如局部公共子表达式就是一个基本块就是在一个基本块内重复出现并且值不变的表达式

  • 全局优化：跨基本块的优化，如全部基本块。对于循环的全局公共子表达式则是指在一个循环的全部基本块范围内的公共子表达式

  • 公共子表达式

    • 一个表达式在某次出现之前必然被计算过，并且在计算之后就没有再改变过
    • image.png|500
    • image.png|500
  • 复制传播
    • 形如 u = v 的复制语句使得语句后面的程序点上，u 的值等于 v 的值
    • 如果在某个位置上一定有 u=v 那么就可以直接把 u 替换为 v。有时甚至可以完全消除对 u 的使用
    • image.png|500
  • 死代码消除
    • 如果一个变量在某个程序点上的值可能会在之后被使用，那么这个变量在这个点上活跃的；否则这个变量就是死的，此时对该变量的赋值就是没有用的死代码（死代码多半是因为前面的优化而形成的）
    • image.png|500
  • 代码移动
    • 循环中的代码会被执行很多次，如果循环内一个表达式在不同迭代中值始终不变，那么这就是一个循环不变表达式(即其值域迭代无关)
    • 可以把循环不变表达式移动到循环入口之前
    • image.png|500
  • 归纳变量和强度
    • 归纳变量是指在循环中，其值按照某种规律（通常是线性规律）递增或递减的变量。
    • 每次对 x 赋值都使 x 增加 c，则可以把赋值改为增量操作，可消减计算强度 (如乘法->加法)
    • image.png|500
    • 通过分析和优化，有时还可以完全去掉不必要的归纳变量

基本块和流图

  • 将中间代码划分为基本块，控制流只能从基本块的第一条指令进入，除了基本块的最后一条指令，控制流不会进行跳转/停机
  • 流图的节点就是基本块，流图的边说明了基本块之间的运行关系
    • 指出了基本块之间的控制流，可以确认一个值是否会被使用
    • 是进行优化的基础
  • 基本块的划分：三地址指令序列->基本块的列表
    • 首先找到首指令：第一个三地址指令；转移指令的目标指令；转移指令之后的指令
    • 每个首指令就对应一个基本块，块的范围就是从一个首指令开始到下一个首指令之前
    • image.png|500

  • 流图的构造

    • 两个节点之间存在一条边 \(A\to B\iff\) B 的第一个指令可能在 A 的最后一个指令之后执行；称 A 为 B 的前驱；B 为 A 的后驱
    • 入（出）口节点：入口到第一条指令有一条边；任何可能最后执行的基本块到出口有一条边
    • image.png|500

  • 循环

    • 循环入口：唯一的前驱可以在循环 L 之外的结点，到达其余结点的路径必然先经过这个入口结点；其余结点都存在到达入口结点的非空路径，且路径都在 L 中
    • 一个循环是流图中一个结点集合
    • image.png|500

DAG 分析

  • DAG 图可反映变量及其值对其他变量的依赖关系 (各变量的值之间的关系)

  • DAG 图的建立

    • 每个变量都有一个对应的 DAG 结点表示其初始值
    • 每个语句 s 有一个相关的结点 N，代表此计算得到的值；节点 𝑁 的子节点是构成该语句的运算分量的当前值。在 x = y + z 的例子中，𝑦 和 𝑧 将是 𝑁 的子节点。
    • image.png|500
    • 扫描结束后，对所有在出口处活跃的变量 x，将 x 所关联的结点设置为输出结点
    • image.png|500 p11
  • 局部公共子表达式
    • 建立某个结点 M 之前，检查是否存在一个结点 N，它和 M 具有相同的运算符和子结点
    • 如果存在则可以直接使用 N 来代表 M，不再需要生成新的节点
    • image.png|500
    • （b+c）不是，因为 b 的值改变了
  • 消除死代码
    • 在 DAG 图上消除没有附加活跃变量（未来使用如作为返回值或输出等）的根结点，即消除死代码
    • image.png|500
  • 代数恒等式优化
    • 恒等式：\(x + 0 = 0 + x = x, x – 0 = x\) 等
    • 简化运算 \(x^2=x*x,x/2=x*0.5\) 等
    • 常量编译时计算、合并
    • 利用代数规则（交换律、结合律）
  • 数组引用
    • 数组有两种操作：
      • 取数：=[] 左子节点为数组（起始）地址 \(a\)，右子节点为下标 \(i\)
      • 存数：[]= 三个子节点分别表示：数组（起始）地址 \(a\)，下标 \(i\)，要存储的值 \(x\)
    • 出现一个存数操作后，所有依赖于该数组的之前的节点都应该被“杀死”不能再被复用（尤其是写入的下标为变量时）
    • image.png|500

  • 指针赋值和过程调用

    • 通过指针访问和数组类似，可以分为写和读两种操作
    • 由于通过指针取值可以访问任何元素，这就给死代码的消除带来很大困扰；而通过指针进行赋值又可能会杀死全部其他节点
    • 可通过 (全局/局部) 指针分析部分地解决这个问题
    • 这两种操作都具有很大的不确定性

  • 重组

    • 方法：每个结点构造一个三地址语句，计算对应的值；结果应该尽量赋给一个活跃的变量；如果结点有多个关联的变量，则需要用复制语句进行赋值
    • 规则：如果两个指令之间相互影响，它们的顺序就不该改变
      • 对数组赋值要跟在原来之前的赋值/求值之后
      • 对数组求值要跟在原来之前的赋值指令之后
      • 对变量的使用必须跟在所有原来在它之前的过程调用和指针间接赋值之后
      • 任何过程调用或指针间接赋值必须跟在原来在它之前的变量求值之后
    • image.png|500 p12#^2a0fdd|9.1.1 p12#^c7fe5c|9.1.4

数据流分析

  • 用于获取数据沿着程序执行路径流动信息的相关技术
  • 程序点：三地址语句之前/之后的位置；一个语句之后的程序点就是下一个语句之前的程序点
    • 构成一条执行路径 \(P_{1},\dots,P_{n}\)
    • 程序点的程序状态：指令指针指向这个程序点时各个变量和动态内存中存放的值
    • 程序点的特性：不管程序怎么运行，到达某个点时总是满足的状态
    • image.png|500

数据流分析模式

  • 数据流值表示了程序点具有的性质
    • 和某个程序点关联的数据流值就是程序运行中经过这个点时必然满足的条件
    • 某个数据流所有可能值的集合称为该数据流值的域
  • 对一组约束求解，得到各个点上的数据流值
    • 基于语句语义的约束：一个语句之前和之后的数据流值受到其语义的约束；语句语义通常用传递函数表示，它把一个数据流值映射为另一个数据流值
    • 基于控制流的约束：在基本块内部，一个语句的输出 = 下一语句的输入
    • 使用 \(OUT[s]\) 表示一个程序点的输出数据；\(IN[s]\) 表示程序点的输入数据
  • 一个基本块的控制流很简单：无分支，不会中断

  • 传递函数：程序执行过程中的数据流关系 \(OUT[s]=f_{s}(IN[s])\)

    • 对于基本块语句 \(s_{1},\dots s_{n}\) 有 \(f_B=f_{s_n}\circ...\circ f_{s_2}\circ f_{s_1}\)

  • 前向数据流：

    • B 的传递函数根据 \(IN[B]\) 计算得到 \(OUT[B]\)
    • \(IN[B]\) 和 B 的各前驱基本块的 \(OUT\) 值之间具有约束关系
    • image.png|275
  • 逆向数据流：
    • B 的传递函数根据 \(OUT[B]\) 计算得到 \(IN[B]\)
    • \(OUT[B]\) 和 B 的各后继基本块的 \(IN\) 值之间具有约束关系
  • 数据流方程通常没有唯一解, 目标是寻找一个最“精确”且满足约束的解 (在保证安全的同时保证代码的安全性)

image.png

到达定值

  • 只要一个定值能够沿某条路径到达一个程序点，这个定值就是到达定值
    • 假定 x 有定值 d，如果存在一个路径，从紧随 d 的点到达某点 p，并且此路径上面没有 x 的其他定值点（变量被赋值的语句），则称 x 的定值 d 到达 p
    • 如果在这条路径上有对 x 的其它定值，我们说变量 x 的这个定值 d 被杀死了
    • 如果某个变量 x 的一个定值 d 到达了点 p，在 p 点使用变量 x 的时候，x 的值是由 d 最后定值的
  • 为了保证安全：分析得到的到达定值可能实际上不会到达但是实际到达的一定被分析出来，否则不安全

  • image.png|500

  • 对于定值 \(d:u=v+w\)

    • 生成了对变量 \(u\) 的定值 \(d\)，杀死其它对 \(u\) 的定值
    • 生成-杀死：\(f_{d}(x)=gen_{d}\bigcup (x-kill_{d})\)
      • \(gen_{d}\) 为新生成的定值 \(d\)
      • \(x-kill_{d}\) 为旧的定值移除被（d）杀死的其他定值
    • 嵌套公式 \(f_2(f_1(x))=gen_2\:\cup\:(gen_1\:\cup\:(x-kill_1)-kill_2)\)
      • 生成的定值：由第二部分生成、以及由第一部分生成且没有被第二部分杀死
      • 杀死的定值：被第一部分杀死、以及被第二部分杀死的定值
  • 对于有 \(n\) 个语句的 \(B\)，\(f_{B}(x)=gen_{B}\:\cup\:(x-kill_{B})\)
    • \(\begin{aligned}&gen_{B}=gen_{n}\:\cup\:(gen_{n-1}-kill_{n})\:\cup\:...\:\cup\:(gen_{1}-kill_{2}-\\&kill_{3}-...-kill_{n})\end{aligned}\)
    • \(kill_B=kill_1\:\cup\:kill_2\:\cup\:...\:\cup\:kill_n\)
    • image.png|500
  • 控制流方程的迭代解法
    • \(\mathrm{IN}[B]=\cup_{P\text{是}B\text{的前驱基本块}}\mathrm{OUT}[P]\)
      • 如果从基本块 P 到 B 有一条控制流边，那么 \(OUT[P]\) 在 \(IN[B]\) 中
    • \(\mathrm{OUT}[B]=gen_{B}\cup (\mathrm{IN}[B]-kill_{B})\)
    • 先根据公式求解 \(gen_{B}\) 和 \(kill_{B}\) （块内）；令所有 \(OUT[B]\) 为空集，不停迭代直到得到最小不动点的解
    • image.png|500
    • 大的迭代次数是流图的结点个数 n（定值经过 n 步必然已经到达所有可能到达的结点）
    • image.png|500 p13#^408300|9.2.1

活跃变量

  • 变量 x 在 p 上活跃，当且仅当存在一条从 p 开始的路径，该路径的末端使用了 x，且路径上没有对 x 进行覆盖
  • 仍然是生成-杀死形式，但是从 OUT 值计算出 IN 值 (逆向)
  • \(use_{B}\) ：在 \(B\) 中先于定值被使用
  • \(def_{B}\)：在 \(B\) 中使用之前就被定值
    • image.png|275

  • 基本块中有

    • \(\begin{aligned}&use_B=use_1\cup (use_2-def_1)\cup (use_3-def_1-def_2)\cup...\\&\cup (use_n-def_1-def_2...-def_{n-1})\end{aligned}\)
      • 用 \(use-def\) 是因为如果一个元素在使用之前被重新定义了，那么就不再是基本块入口活跃变量了
    • \(\begin{aligned}&def_B=def_1\:\cup\:(def_2-use_1)\:\cup\:(def_3-use_1-use_2)\:\cup\:...\\&\cup(def_n-use_1-use_2...-use_{n-1})\end{aligned}\)
      • 如果一个元素在重定义之前被使用了，自然是活跃变量（只要被使用了就是）

  • 活跃变量的迭代分析、

    • 任何变量在程序出口处不再活跃，\(IN[EXIT] = 空集\)
    • \(\mathrm{IN}[B]=use_B\:\cup\:(\mathrm{OUT}[B]-def_B)\)
    • \(\mathrm{OUT}[B]=\cup_{S\text{是}B\text{的后继基本块}}\mathrm{IN}[S]\)
    • image.png|500

可用表达式

  • x + y 在 p 点可用的条件：从流图入口结点到达 p 的每条路径都对 x + y 求值（即必然被求过值），且在最后一次求值之后再没有对 x 或 y 赋值
  • \(e\_gen_{B}\)：基本块求值 x + y，且之后没有对 x 或 y 赋值，那么它生成了 x + y
  • \(e\_kill_{B}\)：基本块对 x 或 y 赋值，且没有重新计算 x + y，那么它杀死了 x + y
  • 初始化 \(S = \{ \}\)
    • 从头到尾逐个处理基本块中的指令 \(x = y + z\)
    • 把 \(y + z\) 添加到 S 中
    • 从 S 中删除任何涉及变量 x 的表达式
    • 遍历结束时得到表达式的结合
    • image.png|375
  • 初始时 \(OUT[ENTRY] = 空集\)，其他 \(OUT\) 值的初始化值是全集
    • \(\mathrm{OUT}[B]=e\_gen_B\cup(\mathrm{IN}[B]-e\_kill_B)\)
    • \(\mathrm{IN}[B]=\cap_{P\text{是}B\text{的前驱基本块}}\mathrm{OUT}[P]\)
    • image.png|500

数据流分析的应用

  • 数据流分析得到的以上三个指标可以用于一些代码优化方法
  • 公共子表达式删除
    • 消除重复计算的表达式
    • 通过可用表达式分析，识别哪些表达式在某个点是可用的，即已经被计算过且其操作数没有被修改。然后，将这些重复计算的表达式替换为之前计算的结果。
  • 常量折叠
    • 在编译时计算常量表达式的值，从而减少运行时的计算量。
    • 通过常量传播分析，确定哪些变量在程序的某个点处具有常量值。然后，在编译时用这些常量值替换变量，提前计算表达式的结果。
  • 无用代码消除
    • 删除对程序的输出没有影响的代码，从而减少代码体积和提高性能。
    • 活跃变量分析：通过活跃变量分析，确定哪些变量在某个点之后不会被使用。如果一个变量在定义之后从未被使用过，那么这条定义语句是无用的，可以删除。
    • 到达定值分析：辅助活跃变量分析，确保在删除语句时不会影响到其他变量定义。

部分冗余消除

  • 同样是为了尽量减少表达式求值的次数
    • 需要更复杂的数据流分析技术
  • 目标：
    • 部分冗余：在程序按照某些路径到达这个点的时候 x + y 已经被计算过，但沿着另外一些路径到达时，x + y 尚未计算过
    • image.png|500

  • 两种操作

    • 在关键边上增加基本块（关键边：从具有多个后继的结点到达具有多个前驱的结点）
      • 关键边代表了控制流从一个复杂的决策结构转移到另一个复杂的决策结构的路径，通常是进行优化调整的重点位置
    • 进行代码复制
    • image.png|500

  • 懒惰代码移动：

    • 消除冗余计算：通过移动代码来消除所有可能的、不需要复制代码的冗余计算。
    • 避免额外的计算：保证优化后的代码不会执行原始代码中未执行的计算。
    • 推迟计算：将表达式的计算尽可能地推迟，这有助于寄存器的有效分配和使用，因为表达式的结果被延后使用时，可以减少寄存器的占用时间。
  • 基本步骤
    • 找出各程序点上预期执行的所有表达式
    • 在表达式被预期执行但是不可用的程序点上，放置表达式的计算
    • 把表达式尽量后延到某个程序点，在到达这个点的所有路径上，这个表达式在这个程序点之前被预期执行，但是还没有使用这个值
    • 消除只使用一次的临时变量

image.png

被预期执行的表达式

  • 如果从程序点 p 出发的所有路径都会计算表达式 \(b + c\) 的值 (即使用 \(p\) 处 \(b+c\) 的值)，并且 b 和 c 在那时的值就是它们在点 p 的值，那么表达式 \(b + c\) 在点 p 上被预期执行
    • image.png|225
    • 在如图中的这些入口点就被预期执行
  • 同样使用数据流分析框架
    • 逆向分析
    • 基本块内部：当表达式在 B 出口处被预期执行，且它没有被 B 杀死，那么它在 B 入口处也被预期执行
    • 基本块之间：当在 B 的所有后继基本块的入口处都（\(\cup\)）被预期执行，那么表达式在 B 出口处被预期执行
    • 在整个程序的出口处，没有表达式被预期执行
  • 与活跃变量类似，不过 \(\cup \to \cap\)

可用表达式

  • 表达式在基本块的出口处可用的条件：
    • 在基本块的入口处可用，或在基本块的入口处的预期执行表达式中
    • 且没有被这个基本块杀死
  • image.png|500

可后延表达式

  • 在保持程序语义的情况下，尽可能延后计算表达式
  • \(x + y\) 可后延到 p 的条件
    • 所有从程序入口到达 p 的路径中都会碰到一个位置较前的 \(x + y\)，且在最后一个这样的位置到 p 之间没有使用 \(x + y\)
  • image.png|500

被使用的表达式

  • 确定一个被引入的临时变量是否在它所在基本块之外的其它地方使用
    • 即对表达式的活跃性分析
    • 如果从程序点 p 出发的一条路径在表达式被重新求值之前使用了该表达式，那么该表达式在点 p 上被使用

循环的优化

  • 程序的大部分执行时间都花在循环上

支配节点

  • 如果每条从入口结点到达 n 的路径都经过 d，那么 d 支配 n，记为 \(d \ dom \ n\)
    • image.png|500
  • 支配节点树
    • 用于表示节点间的支配关系
    • 根节点就是入口节点
    • 树中每一个节点支配且只支配树中的后代节点
    • image.png|500

  • 直接支配节点

    • 从入口结点到达 n 的任何路径 (不含 n) 中，它是路径中最后一个支配 n 的结点
    • 性质：对于 \(d\neq n\&\& d \ dom \ n\to d \ dom \ m\)

  • 寻找支配节点

    • 一个结点的支配结点集合是它的所有前驱的支配结点集合的交集加上他自己，即 \(x\bigcup \{ B \}\)
  • 使用前向数据流分析问题
    • image.png|500
  • image.png|550

深度优先生成树

  • image.png|500
  • 三种边
    • 前进边
    • 后退边
    • 交叉边
  • 对于后退边 \(a\to b\) 若 \(b \ domin \ a\) 则为回边
    • 如果一个流图的任何深度优先生成树中的所有后退边都是回边，那么该流图就是可归约的
    • image.png|500
  • 流图相对于 DFST 的深度: 各条无环路径上后退边数中的最大值
    • 对可归约的流图，可使用回边来定义，且可说是流图的深度
    • image.png|275
    • 深度为 3：\(10\to{7}\to 4 \to 3\)

自然循环

  • 一个自然循环由循环头（循环的唯一入口点）和循环体（包括循环头和所有能通过一个非循环头路径到达循环头的节点）构成
  • 性质：
    • 有唯一的支配循环中所有节点的入口节点
    • 必然存在进入循环头的回边

  • 定义：

    • 给定回边 \(n\to d\) 的自然循环是 d，加上不经过 d 就能够到达 n 的结点的集合
    • \(d\) 是这个循环的头

  • image.png|500

  • image.png|500