编译原理目录
1、词法分析
2、语法分析(重点)
3、语法制导翻译与抽象语法树
4、语义分析
5、代码生成
6、中间代码与程序分析
7、代码优化
七、代码优化
优化的位置
1. 基本概念
什么是代码优化?
- 代码优化是对被优化的程序进行的一种语义保持的变换(或改写)
- 语义保持:程序的可观察行为不能改变
- 变换的目的是让程序能够比变换前:更小、更快、cache行为更好、更节能等等。
不存在“完全优化”
- 等价于停机问题:给定程序p,把Opt(p) 和下面的程序比较:
L:jmp L
- 这称为“编译器从业者永不失业定理”。
代码优化很困难
- 不能保证优化总能产生“好”的结果
- 优化的顺序和组合很关键
- 很多优化问题是非确定的
- 优化的正确性论证很微妙
正确的观点
- “把该做对的做对”
- 不是任何程序都会同概率出现
- 所以能处理大部分常见情况的优化就可以接受
- “不期待完美编译器”
- 如果一个编译器有足够多的优化,则就是一个好的编译器
前端优化
- 局部的、流不敏感的
- 常量折叠、代数优化、死代码删除等
中期优化
- 全局的、流敏感的
- 常量传播、拷贝传播、死代码删除、公共字表达式删除等
后端优化
- 在后端(汇编代码级)进行
- 寄存器分配、指令调度、窥孔优化等
2. 前端优化
对 抽象语法树 进行优化
2.1 实例1 —— 常量折叠
基本思想: 在编译期计算表达式的值
- 例如:
a = 3 + 5
==>a = 8
- 例如:
if (true && false)
==>if (false)
算法:
// 语法制导的常量折叠算法
const_fold(Exp_t e)
while (e is still shrinking)
switch (e->kind)
case EXP_ADD:
Exp_t l = e->left;
Exp_t r = e->right;
if (l->kind==EXP_NUM && r->kind==EXP_NUM)
e = Exp_Num_new (l->value + r->value);
break;
case...
default:
break;
优缺点
- 容易实现、可以在语法树或者中间表示上进行
- 通常被实现成公共子函数被其它优化调用
必须要很小心遵守语言的语义:例如考虑溢出或异常的。
- 例子:
0xffffffff+1 ==> 0 (???)
- 例子:
2.2 实例2 —— 代数化简
基本思想:
利用代数系统的性质对程序进行化简,示例:
a = 0+b ==> a = b
a = 1*b ==> a = b
2*a ==> a + a (强度消弱)
2*a ==> a<<1 (强度消弱)
同样必须非常仔细的处理语义
- 示例:
(i-j) + (i-j) ==> i+ i -j -j
(×)
- 示例:
算法
// 代数化简的算法
alg_simp(Exp_t e)
while (e is still shrinking)
switch (e->kind)
case EXP_ADD:
Exp_t l = e->left;
Exp_t r = e->right;
if (l->kind==EXP_NUM && l->value==0)
e = r;
case ...
break;
case ...: ...; // 类似
2.3 实例3 —— 死代码(不可达代码)删除
基本思想:
静态移除程序中不可执行的代码,示例:
if (false) s1; else s2;
- ==>
s2;
- 在控制流图上也可以进行这些优化,但在早期做这些优化可以简化中后端。
算法:
// 不可达代码删除算法
deadcode(Stm_t s)
while(s is still shrinking)
switch (s->kind)
case STM_IF:
Exp_t e = s->condition;
if (e->kind==EXP_FALSE)
s = s->elsee;
case ...
break;
case ...: ...; // 类似
3. 中间表示层优化
3.1 中间表示上的代码优化
- 依赖于具体所使用的中间表示:控制流图(CFG)、控制依赖图(CDG)、静态单赋值形式(SSA)、后续传递风格(CPS)等
共同的特点是需要进行程序分析
- 优化是全局进行的,而不是局部
- 通用的模式是: 程序分析 → 程序重写
在这部分中,我们将基于控制流图进行讨论
- 但类似的技术可以用于其它类型的中间表示
优化的一般模式
程序分析
- 控制流分析,数据流分析,依赖分析, …
- 得到被优化程序的静态保守信息 (是对动态运行行为的近似)
程序重写
- 以上一步得到的信息制导对程序的重写
3.2 实例1 —— 常量传播
算法
// 常量传播算法
const_prop(Prog_t p)
// 第一步:程序分析,到达定义分析
reaching_definition(p);
// 第二步:程序改写
foreach (stm s in p: y = x1, ..., xn)
foreach (use of xi in s)
if(the reaching def of xi is unique: xi = n)
y = x1, ..., xi-1, n, xi+1, ..., xn
示例:
3.3 实例2 —— 拷贝传播
算法:
// 拷贝传播算法
copy_prop(Prog_t p)
// 第一步:程序分析,到达定义分析
reaching_definition(p);
// 第二步:程序改写
foreach (stm s in p: y = x1, ..., xn)
foreach (use of xi in s)
if(the reaching def of xi is unique: xi = z)
y = x1, ..., xi-1, z, xi+1, ..., xn
3.4 实例3 —— 死代码删除
live_out:最后用的到的变量值
算法:
// 死代码删除算法
dead_code(Prog_t p)
// 第一步:程序分析
liveness_analysis(p); // 得到每一个语句的out[]集合
// 第二步:程序改写
foreach (stm s in p: y = ...)
if (y is NOT in live_out[s])
remove (s);
- - - 结束 - - -