编译优化
基本概念
- 代码优化是对被优化的程序进行的一种语义保持的变换
- 语义保持：
- 程序的可观察行为不能改变
- 变换的目的是让程序能够比变换前：
- 更小
- 更快
- cache行为更好
- 更节能
- 等等
不存在完全优化
等价于停机问题
- 给定一个程序p，把opt§和下面的程序比较：L: jmp L
编译器从业者永不失业定理
代码优化很困难
- 不能保证优化总能产生好的结果
- 优化的顺序和组合很关键
- 很多优化问题是非确定的
- 优化的正确性论证很微妙
正确的观点
- 把该做对的做对
- 不是任何程序都会同概率出现
- 所以能处理大部分常见情况的优化就可以接受
- 不期待完美编译器
- 如果一个编译器有足够多的优化，则就是一个很好的编译器
前端优化
常量折叠
- 基本思想
- 在编译期计算表达式的值
- 可以在整形、布尔型、浮点型等数据类型上进行
- 小结
- 容易实现，可以在语法树或者中间表示上进行
- 通常被实现成公共子函数被其他优化调用
- 必须很小心遵守语言的语义
代数化简
- 基本思想
- 利用代数系统的性质对程序进行化简
- 示例
- a = 0+b => a=b
- a = 1 * b => a=b
- 2*a => a+a
- 2*a => a<<1
- 同样必须非常仔细的处理语义
不可达删除
- 基本思想
- 静态移除程序中不可执行的代码
- 在控制流图上也可以进行这些优化，但在早期做这些优化可以简化代码中后端
中间表示上的优化
- 依赖于具体所使用的中间表示
- 控制流图（CFG）、控制依赖图（CDG）、静态单赋值形式（SSA）、后续传递风格（CPS）等
- 共同特点是需要进行程序分析
- 优化是全局进行的，而不是局部
- 通用的模式是：程序分析-》程序重写
