9. 机器无关的优化
有很多概念和公式，所以要记录一下：
基本优化技术
全局公共子表达式：如果E（某行代码）
- 在某次出现之前必然已被计算过，且
- E的运算分量在该次计算之后没有被改变
- 那么，E的本次出现就是一个公共子表达式
复制传播：形如u = v的复制语句使得语句后面的程序点上，u的值等于v的值
- 如果在某个位置上u一定等于v，那么可以把u替换为v
- 有时可以彻底消除对u的使用，从而消除对u的赋值语句
死代码消除：一般是因为消除了全局公共子表达式（并且复制传播）
- 如果一个变量在某个程序点上的值可能会在之后被使用，那么这个变量在这个点上活跃的；否则这个变量就是死的，此时对该变量的赋值就是没有用的死代码
代码移动-循环不变式：循环的同一次运行的不同迭代中，表达式的值不变
- 把循环不变表达式移动到循环入口之前计算可以提高效率
归纳变量与强度消减：
- 每次对x赋值都使x增加c
- 把赋值改为增量操作，可消减计算强度
- 两个归纳变量步调一致，可删除一个
- 例子：j=4*i, i=i+1→j=j+4, i=i+1
数据流分析-控制流图
数据流分析中的相关概念
程序点：三地址语句之前或者之后的位置
- 基本块内部：一个语句之后的程序点等于下一个语句之前的程序点
- 如果流图中有B1到B2的边，那么B2的第一个语句之前的点可能（因为可能实际上不会到，是一个may analysis）紧跟在B1的最后语句之后的点后面执行
出现在某个程序点的程序状态：
- 在某个运行时刻，当指令指针 (PC) 指向这个程序点时，各个变量和动态内存中存放的值
- 指令指针可能多次指向同一个程序点，因此一个程序点可能对应多个程序状态
- 数据流分析把可能出现在某个程序点上的程序状态集合总结为一些特性（求解这些数据 流值实际上就是推导这些性质的过程）
程序点上的性质被表示成为数据流值，求解这些数据流值实际上就是推导这些性质的过程
这里的定值的意思是被哪些式子影响，而不是 const 的意思，const 这里理解为“常量”
数据流值的域：
- 某个数据流所有可能值的集合称为该数据流值的域
- 不同的应用选用不同的域，比如到达定值
- 目标是分析在某个点上，各个变量的值由哪些语句定值
- 因此其数据流值是定值 (即三地址语句) 的集合
数据流分析
意思是求解的过程由两个部分，一个是由语句自身的作用所产生的，另一个就是前后的控制流产生的影响
这里有两个定义：
OUT[s]：s语句之后的控制流值
IN[s]：s语句之前的控制流值
还有一个和语句有关的转换函数
基本块内的数据流模式
各个语句的效果（转换函数）的复合
基本块之间的控制流约束
数据流分析-到达定值分析（may-analysis）
may analysis，就是必须要 sound （认为不会发生的就一定不会发生，但是认为会发生的可能不发生；对的就一定是对的，不对的可能是对的；尽可能多报，可能误报；相对应的是 complete，可能漏报）
定值 d: u = v + w
- 生成了对变量 u 的定值 d，杀死其它对 u 的定值
- 生成-杀死形式： \(f_d(x)={\rm gen}_d\cup(x-{\rm kill}_d)\)
- \({\rm gen}_d=\{d\},{\rm kill}_d=\) { 程序中（全局）其它对 u 的定值 }
对于一个基本块：直接复合，第 i 条语句的 gen, kill 记为 \({\rm gen}_i,{\rm kill}_i\)
这里的 \(\cup\) 不能理解成简单的集合求并，是有一定运算规则的. （不过对于定值来说应该可以合并）
到达定值的控制流方程
求解各个基本块到达定值(reaching definition)的方法
in out: bit vectors e.g., D1, D2, D3, D4, ..., D100 (100 definitions, 100 个语句) 就是 100 个 bit 位
正确性？不断向前传递各个定值，直到该定值被杀死为止
为什么不会出现死循环？因为 out 不会变小，且显然存在上界，再加上 while 的条件（gen 和 kill 不变，一旦被加入到 out 中，就不会消失，out 是有限的）
最大迭代次数？流图的结点个数 n（定值经过n步必然已经到达所有可能到达的结点）
结束时，各个OUT/IN值必然满足数据流方程
上面的算法提供了一个模板
数据流分析-活跃变量分析（may-analysis）
基本块的转换函数仍然是生成-杀死形式，但是从OUT值计算出IN值
- use B：在B中先于定值被使用
- def B：在B中被定值（definition）
定义：Live variables analysis tells whether the value of variable v at program point p could be used along some path in CFG starting at p. If so,v is live at p; otherwise,v is dead at p. (在使用前不能被 redefine)
用比特位来表示第 i 个变量（n个变量 n 个比特位），表示在这个程序点对 x 的定值在后续有没有可能活跃
初始化：（要知道在后面哪里使用了，所以最好用 backward 的方法）
- 任何变量在程序出口处不再活跃 - IN[EXIT] = 空集
- 对于所有非EXIT基本块：
为什么是 may-analysis：因为只要存在一条可能路径被使用就是不行的
必然停止分析：一样的
数据流分析-可用表达式分析（must-analysis）
- 在这之前，所有路径都必须经过 2. 在这之后，x 和 y 都不会重新定值
（相当于这句话可以到处代替）
用比特位来表示第 i 条语句（x op y，不要和定值弄混）是否 available（n个语句 n 个比特位）
只管语句，不管结果的变量（赋值号前面，因为语句可用的话，结果都可以用一个变量指示）
基本块 e_gen 和 e_kill 的生成过程：
- 初始化S = { }
- 从头到尾逐个处理基本块中的指令x = y op z
- 把y op z添加到S中
- 从S中删除任何涉及变量 x 的表达式（所以如果是 x = x+y 这种表达式 x+y 就会被删掉，同时也把这个变量相关的表达式加到 kill 中）
- 遍历结束时得到基本块生成的表达式集合
- 杀死的表达式集合
- 表达式的某个分量在基本块中被定值，并且该表达式没有被再次生成
算法如下（U 就是全 1）：
数据流分析-总结
到达定值分析的用途：
- 循环不变代码外提（Loop-Invariant Code Motion，LICM）：
对于循环内部的赋值语句，若构成赋值表达式的变量均在循环外部定义，则可以将该语句移 动到循环外侧，降低执行时的开销。
- 常量折叠（Constant Folding）： 我们可以迭代式地将程序内部可转变为常量的，降低执行的开销（程序点上有三种状态：唯一常量，NAC，UNDEF-在程序点 p 上存在至少一条从入口到程序点 p 的路径，在这条路径上，没有对变量 v 的赋值或已被赋空）
活跃变量分析的用途：
- 无用代码消除，消除未被使用的赋值与未执行的程序代码
可用表达式分析的用途：
- 进行公共子表达式消除，消除重复计算的公共子表达式
拓展（来自实验指导）：
全局优化管道：常量传播 → 公共子表达式消除 → 无用代码消除 → 循环不变代码外提 → 归纳变量强度削减
可移动代码需要关注的性质：
- 被移动前不是不可达代码
- 移动前，循环内部对该变量的赋值是唯一的
- 对变量赋值前，循环内部不存在对该变量的使用
- 变量定义的基本块能够支配所有的循环出口
部分冗余消除
作用：用于公共子表达式消除及循环不变代码外提。部分冗余消除使得表达式的求值满足以下性质：
- 不改变程序语义
- 尽可能减少子表达式的求值
- 尽可能延后子表达式求值（便于目标代码生成时，寄存器的相关优化）
懒惰代码移动
目标：
- 所有不复制代码就可消除的冗余计算都被消除
- 优化后的代码不会执行原程序中不执行的任何计算
- 表达式的计算应该尽量靠后，以利于寄存器的分配
冗余消除：
- 完全冗余
- 部分冗余：在流图中放置表达式x + y的拷贝，使得某处的x + y成为完全冗余，从而删除
基本步骤：
- 找出各程序点上预期执行的所有表达式
- 在表达式被预期执行但是不可用的程序点上，放置表达式的计算
- 把表达式尽量后延到某个程序点，在到达这个点的所有路径上，这个表达式在这个程序点之前被预期执行，但是还没有使用这个值
- 消除只使用一次的临时变量
预期执行
简单来说就是对于某个程序点 p 来说，若接下来的所有道路都一定计算 b+c，且计算时的值就是分量在 p 点时的值，就说 b+c 在 p 预期执行
这里有一个前挪的过程（会增大可用表达式的数目）
可用表达式（基本块出口处）
和前面的可用表达式类似，但假设代码已经被复制到了预期执行点上
表达式在基本块的出口处可用的条件：
- 在基本块的入口处可用，或在基本块的入口处的预期执行表达式中
- 没有被这个基本块杀死（分量被重新定值但是没有重新计算表达式，则该表达式被杀死）
（这里ppt上接下来一张图的标黑的块的意思是在入口处不可用, b3 这里此时因为前挪会计算 b+c）
上述两个分析可以达成“优化后的代码不会执行原程序中不执行的任何计算”
可后延表达式
在预期执行前提的基础上尽量靠后
在保持程序语义的情况下，尽可能延后计算表达式
ppt上那个例子的解释：首先先把b+c前挪到 B2 开头，但是因为从 b2-b7的路上都没有使用 b+c （b5 使用了所以不能延后），且 b7 开头就要用，所以顶多后延到 b4→b7 的边上
粗略地说，一个表达式将被放置在边界上，即一个表达式从可后延变成不可后延的地方
被使用的表达式
确定一个被引入的临时变量是否在它所在基本块之外的其它地方使用
- 对表达式的活跃性分析
- 如果从程序点p出发的一条路径在表达式被重新求值之前使用了该表达式，那么该表达式在点p上被使用
总结表格
循环的识别
循环的重要性
- 程序的大部分执行时间都花在循环上
- 也是数据流分析需要经过若干次迭代的原因
支配结点
- 支配
如果每条从入口结点到达 n 的路径都经过 d，那么 d 支配 n，记为 d dom n
-
支配树
-
根结点：入口结点
-
每个结点 d 支配且只支配树中的后代结点
-
直接支配结点
-
从入口结点到达 n 的任何路径 (不含 n) 中，它是路径中最后一个支配 n 的结点
- n 的直接支配结点 m 具有如下性质：如果 d ≠ n 且 d dom n，那么 d dom m（可以理解成直接支配结点 m 下一步怎么走都要走到 n）
D 表示“被哪些结点支配”，= OUT
终止：有下界，越来越小
entry 的初始化是它自己，其他结点初始化是全集(T)，理由在于做 sound 分析化要假设被所有支配（为什么是全集？还需要进一步分析，可以看李樾怎么说）
深度优先生成树（回边）
- 深度优先搜索 (Depth-First Search / DFS)
搜索过程从入口结点开始，并首先访问已知离入口结点最远的结点
- 深度优先生成树
一个深度优先过程中的搜索路线形成了一个深度优先生成树 (Depth-First Spanning Tree / DFST)
- 前序遍历
先访问一个结点，然后从左到右递归地访问该结点的子结点
-
后序遍历 首先递归地从左到右访问一个结点的子结点，然后访问该结点
-
深度优先排序 首先访问一个结点，然后递归访问该结点的最右子结点，再递归访问这个子结点左边的子结点，依次类推(与后序遍历的顺序相反)
深度优先生成树（DFST）
为一个流图构造出DFST之后，流图中的边可以分为三类
- 前进边：从结点m到达m在DFST树中的一个真后代结点的边 (DFST中的所有边都是前进边)
- 后退边：从m到达m在DFST树中的某个祖先 (包括m)的边
- 交叉边：边的src和dest都不是对方的祖先
注意这里的前进边不代表一定存在支配关系
回边
- 边 a → b，头b支配了尾a
- 每条回边都是后退边，但不是所有后退边都是回边
如果一个流图的任何深度优先生成树中的所有后退边都是回边，那么该流图就是可归约的
- 可归约流图的DFST的后退边集合就是回边集合
- 不可归约流图的DFST中可能有一些后退边不是回边
- 2 和 3 不互相支配
自然循环
自然循环的性质
- 有一个唯一的入口结点 (循环头Header)，这个结点支配循环中的所有结点
- 必然存在进入循环头的回边
自然循环的定义
- 给定回边 n→d 的自然循环是 d，加上不经过 d 就能够到达 n 的结点的集合
- d是这个循环的头
自然循环构造算法：
- 输入：流图 G 和回边 n → d
- 输出：给定回边 n→d 的自然循环中的所有结点的集合 loop
- 方法
- loop = { n, d }，d标记为visited
- 从n开始，逆向对流图进行深度优先搜索，把所有访问到的结点都加入loop，加入loop的结点都标记为visited
- 搜索过程中，不越过标记为visited的结点
循环头上头 (Preheader)
- 每个自然循环都有一个循环头header
- 一些循环相关的优化 (如循环不变量移动) 需要在循环头之前插入代码
- 常见做法是在循环头之前插入一个基本块 (称为 preheader)，用于存放相关的代码