代码优化

流图

基本块

基本块是满足下列条件的最大的连续三地址指令序列（一组总是一起执行的指令）

• 控制流只能从基本块的第一条指令进入该块
• 除了基本块的最后一条指令，控制流在离开基本块之前不会跳转或者停机

基本块划分（确定首指令）

1. 指令序列的第一个三地址指令是一个首指令
2. 任意一个条件或无条件转移指令的目标指令是一个首指令
3. 紧跟在一个条件或无条件转移指令之后的指令是一个首指令

定义

• 流图的每个结点是一个基本块
• 从基本块B到基本块C之间有一条边当且仅当基本块C的第一条指令可能紧跟在B的最后一条指令之后执行
  • 存在一条从B的结尾跳转到C的开头的跳转指令
  • 按照原来的三地址指令序列中的顺序，C紧跟在B之后，且B的结尾不存在无条件跳转指令

优化的分类

第一种分类

• 机器无关优化
  • 针对中间代码
• 机器相关优化
  • 针对目标代码

第二种分类

• 局部代码优化
  • 单个基本块范围内的优化
• 全局代码优化
  • 面向多个基本块的优化

常用的优化方法

删除公共子表达式

公共子表达式：x op y先前被计算过，并且从先前的计算到现在，x op y中变量的值没有改变

删除无用代码

复制传播：常用的公共子表达式消除算法和其他一些优化算法会引入一些复制语句

• 而在复制x = y之后，尽可能地用y代替x

无用代码（死代码）：其计算结果永远不会被使用的语句

常量传播（常量合并）：如果在编译时刻推导出一个表达式的值是常量，就可以使用该常量来替代这个表达式

代码移动

循环不变计算：对那些不管循环执行多少次都得到相同结果的表达式，在进入循环之前就对它们求值

• 具有相对性，不变是相对外层循环而言的

强度削弱

用较快的操作代替较慢的操作，如用+代替*

归纳变量：对于一个变量x，如果存在一个正的或负的常数c使得每次x被赋值时它的值总增加c

• 归纳变量可以通过在每次循环迭代中进行一次简单的增量运算（加法或减法）来计算

删除归纳变量

在沿着循环运行时，如果有一组归纳变量的值的变化保持步调一致，常常可以将这组便令删除为只剩一个