阅读更多
1 流图
1.1 基本块(Basic Block)
基本块是满足下列条件的最大的连续三地址指令序列
- 控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令
- 除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机
1.2 基本块划分算法
输入：三地址指令序列
输出：输入序列对应的基本块列表，其中每个指令恰好被分配给一个基本块
方法：
- 首先，确定指令序列中哪些指令是首指令(leaders)，即某个基本块的第一个指令
- 指令序列的第一个三地址指令是一个首指令
- 任意一个条件或无条件转移指令的目标指令是一个首指令
- 紧跟在一个条件或无条件转移指令之后的指令是一个首指令
- 然后，每个首指令对应的基本块包括了从它自己开始，直到下一个首指令（不含）或者指令序列结尾之间的所有指令
1.3 流图 (Flow Graphs)
流图的节点是一些基本块
从基本块B到基本块C之间有一条边，当且仅当基本块C的第一个指令可能紧跟在B的最后一条指令之后执行。此时称B是C的前驱(predecessor)，C是B的后继(successor)
有两种方式可以确认这样的边
- 有一个从B的结尾跳转到C的开头的条件或无条件跳转语句
- 按照原来的三地址语句序列中的顺序，C紧跟在B之后，且B的结尾不存在无条件跳转语句
2 常用的代码优化方法
优化的分类
- 机器无关优化：针对中间代码
- 机器相关优化：针对目标代码
- 局部代码优化：单个基本块范围内的优化
- 全局代码优化：面向多个基本块的优化
常用的优化方法
- 删除公共子表达式
- 删除无用代码
- 常量合并
- 代码移动
- 强度削弱
- 删除归纳变量
2.1 删除公共子表达式
如果表达式$x\;op\;y$先前已被计算过，并且从先前的计算到现在，$x\;op\;y$中变量的值没有改变，那么$x\;op\;y$的这次出现就称为公共子表达式(common subexpression)
2.2 删除无用代码
常用的公共子表达式消除算法和其它一些优化算法会引入一些复制语句(形如$x = y$的赋值语句)
复制传播：在复制语句$x = y$之后尽可能地用$y$代替$x$
无用代码（死代码Dead-Code）：其计算结果永远不会被使用的语句
2.3 常量合并(Constant Folding)
如果在编译时刻推导出一个表达式的值是常量，就可以使用该常量来替代这个表达式。该技术被称为常量合并
2.4 代码移动(Code Motion)
这个转换处理的是那些不管循环执行多少次都得到相同结果的表达式(即循环不变计算，loop-invariant computation)，在进入循环之前就对它们求值
对于多重嵌套的循环，循环不变计算是相对于某个循环而言的。可能对于更加外层的循环，它就不是循环不变计算
2.5 强度削弱(Strength Reduction)
用较快的操作代替较慢的操作
- 加代替乘
- 乘代替除
- 乘代替乘方
- 加乘复合操作代替多项式
2.5.1 循环中的强度削弱
归纳变量：对于一个变量$x$，如果存在一个正的或负的常数$c$使得每次$x$被赋值时它的值总增加$c$，那么$x$就称为归纳变量(Induction Variable)
- 归纳变量可以通过在每次循环迭代中进行一次简单的增量运算（加法或减法）来计算
2.6 删除归纳变量
在沿着循环运行时，如果有一组归纳变量的值的变化保持步调一致，常常可以将这组变量删除为只剩一个
3 基本块的优化
很多重要的局部优化技术首先把一个基本块转换成为一个无环有向图(directed acyclic graph, DAG)
3.1 基本块的DAG表示
基本块中的每个语句$s$都对应一个内部结点$N$
- 结点$N$的标号是$s$中的运算符；同时还有一个定值变量表被关联到$N$，表示$s$是在此基本块内最晚对表中变量进行定值的语句
- $N$的子结点是基本块中在$s$之前、最后一个对$s$所使用的某个运算分量进行定值的语句对应结点。如果$s$的某个运算分量在基本块内没有在$s$之前被定值，则这个运算分量对应的子结点就是代表该运算分量初始值的叶结点 (为区别起见，叶节点的定值变量表中的变量加上下脚标0)
- 在为语句$x = y + z$构造结点$N$的时候，如果$x$已经在某结点$M$的定值变量表中，则从$M$的定值变量表中删除变量$x$
3.2 基于基本块的DAG删除无用代码
从一个DAG上删除所有没有附加活跃变量（活跃变量是指其值可能会在以后被使用的变量）的根节点（即没有父节点的节点）。重复应用这样的处理过程就可以从DAG中消除所有对应于无用代码的节点
3.3 数组元素赋值指令的表示
在构造DAG时，如何防止系统将$a[i]$误判为公共子表达式
- 对于形如$a[j]=y$的三地址指令，创建一个运算符为"[]="的节点，这个节点有3个子节点，分别表示$a$、$j$、和$y$
- 该节点没有定值变量表
- 该节点的创建将杀死所有已经建立的、其值依赖于$a$的节点
- 一个被杀死的节点不能再获得任何定值变量，也就是说，它不可能成为一个公共子表达式
3.4 根据基本块的DAG可以获得一些非常有用的信息
- 确定哪些变量的值在该基本块中赋值前被引用过，即在DAG中创建了叶节点的那些变量
- 确定哪些语句计算的值可以在基本块外被引用
- 在DAG构造过程中为语句$s$（该语句为变量$x$定值）创建的节点$N$，在DAG构造结束时$x$仍然是$N$的定值变量
3.5 从DAG到基本块的重组
对每个具有若干定值变量的节点，构造一个三地址语句来计算其中某个变量的值
- 倾向于把计算得到的结果赋值给一个在基本块出口处活跃的变量（如果没有全局活跃变量的信息作为依据，就要假设所有变量都在基本块出口处活跃，但是不包含编译器为处理表达式而生成的临时变量）
- 如果结点有多个附加的活跃变量，就必须引入复制语句，以便给每一个变量都赋予正确的值
4 参考
- 《MOOC-编译原理-陈鄞》