优化的分类
- 机器无关优化: 针对中间代码
- 机器相关优化: 针对目标代码
- 局部代码优化: 单个基本块范围内的优化
- 全局代码优化: 面向多个基本块的优化
常用的优化方法
- 删除公共子表达式
- 删除无用代码
- 常量合并
- 代码移动
- 强度削弱
- 删除归纳变量
方法一 删除公共子表达式
公共子表达式
如果表达式x op y先前已被计算过，并且从先前的计算到现在，x op y中变量的值没有改变，那么x op y的这次出现就称为公共子表达式 (common subexpression)
例子
- B5基本块
B5.png
B5.png
注：因为在B5中第一个4*i和4*j到第二个4*i和4*j，i和j的值并没有改变，因此重复的4*i和4*j被删除，a[t7]和a[10]分别被a[t6]和a[t8]代替。
B5.png
注：我们沿着B5的导入符逆流而上发现4*i的值在B2中已经计算过了，而且从B2的4*i到B5的4*i之间并没有改变i的值。因此B5中的4*i还是公共子表达式。由于4*i的上一次计算是在另一个基本块中进行，因此这个公共子表达式叫做全局公共子表达式。同理4*j也是全局公共子表达式。因此删除这两个公共表达式，在使用到t6和t8时用t2和t4代替。
B5.png
B5.png
注：经过变换另一个B5中的全局公共子表达式就显露出来了，它就是a[t2]，a[t2]在基本块B2中已经被计算过了。从B2到B5并没有对a[t2]进行重新赋值，也没有对数组元素重新赋值，因此a[t2]是全局公共子表达式，同理a[4]也是全局公共子表达式。因此可以将这两个公共子表达式进行删除，在使用a[t2]和a[t4]的时候我们可以使用t3和t5进行代替，由于t9是临时变量因此t9也被删除或被t5代替。
B5.png
- B6基本块
B6.png
注：4*i和4*n都是局部公共子表达式，而这两表达式已经在B1和B2中已经被计算过，因此它们是全局公共子表达式，可以将B6中的4条子表达式都删除。其中4*i被t2替换，4*n被t1替换。
B6.png
注：B6中的a[2]在B2中已经被计算过与前面B5的情况类似，a[2]也是一个全局公共子表达式。
B6.png
注：事实上a[t1]在B1计算之后，从B1到B6之前有可能进入B5，而在B5中有对数组元素赋值，此时t2和t4有可能等于t1，因此B5中的操作有可能已经改变a[t1]的值。因此将a[t1]作为公共子表达式是不稳妥的。
B6.png
B6.png
B6.png
方法二 删除无用代码
- 复制传播
复制传播 ：在复制语句x = y之后尽可能地用y代替x，复制传播给删除无用代码带来机会。常用的公共子表达式消除算法和其它一些优化算法会引入一些复制语句(形如x = y的赋值语句）
例.png
- 无用代码(死代码Dead-Code)：其计算结果永远不会被使用的语句
例.png
例.png
方法三 常量合并(Constant Folding)
如果在编译时刻推导出 一个表达式的值是常量 ，就可以使用该常量来替代这个表达式。该技术被称为常量合并
例： l = 2*3.14*r
例.png
方法四 代码移动(Code Motion)
这个转换处理的是那些 不管循环执行多少次都得到相同结果的表达式(即循环不变计算，loop-invariant computation)，在进入循环之前就对它们求值。
例.png
循环不变计算的相对性：对于多重嵌套的循环，循环不变计算是相对于某个循环而言的。可能对于更加外层的循环，它就不是循环不变计算，例：
for(i = 1; i<10; i++)
for( n=1; n<360/(5*i); n++ )
{ S=(5*i)/360*pi*r*r*n; ... }
方法五 强度削弱(Strength Reduction)
用较快的操作代替较慢的操作，如用加代替乘
例.png
循环中的强度削弱
归纳变量：对于一个变量x，如果存在一个正的或负的常数c使得每次x 被赋值时它的值总增加c，那么x就称为归纳变量(Induction Variable)
例.png
例.png
删除归纳变量
例.png
例.png
注：如何识别公共子表达式，无用代码可参考基本块的优化
网友评论