编译学习笔记

本节大部分内容摘抄于 <编译器设计(第二版)>

优化概述

优化的考虑

进行编译优化的时候,可以从安全性,可获利性,风险三个维度进行考虑.

安全性

如果要指出编译器必须满足的一条最重要的准则，那么它就是正确性：编译器所产生代码的语义必须与输入程序相同。

在优化器每次应用变换时，其施加的操作必须保持编译器原有转换过程的正确性。通常，语义（meaning）定义为程序的可观察行为。对于批处理程序，此即该程序停止后的内存状态及其产生的输出。如果程序终止，那么无论编译器使用的是哪种转换方案，在程序停止的前一时刻，所有可见变量的值都应该是相同的。对于交互程序，其行为更为复杂，也更难于描述。

Plotkin形式化了这一概念，称为可观察等价性（observational equivalence）。

对于两个表达式 M 和 N , 当且仅当在 M 和 N 均为封闭（即没有自由变量）的上下文 C 中，对 C[M] 和 C[N] 求值，二者或者产生相同的结果或者均不停止时，我们称 M 和 N 是 可观察等价 的。因而，如果两个表达式对可见外部环境的影响是相同的，那么二者就是可观察等价的。

实际上，与Plotkin的定义相比，编译器使用的等价性概念更简单且宽松，即如果在实际的程序上下文中，两个不同表达式 e 和 e' 产生相同的结果，那么编译器即可用 e' 替换 e。该标准只处理在程序中实际出现的上下文，而根据上下文来调整代码正是优化的本质。它没有提到计算出错或脱节时应该如何。

实际上，编译器会慎重处理，以免发生脱节的情况：即原来的代码工作正确，而优化后的代码试图除以零或无限循环。而反过来的情形，即原来的代码脱节、而优化后的代码工作正常的情况则很少被提及.

在我写数组初始化列表语义分析的时候就可以感受上述这句话的一些情况.GCC等编译器可以检测不符合语义规范的数组初始化列表,并且成功编译运行.

可获利性

类似循环展开的操作为什么可以提高性能?

• 循环迭代的总数减少.减少了由循环控制带来的开销操作:加法,比较,跳转和分支.
• 数组地址计算包含了很多重复的工作,展开后只需要计算一次,然后复用即可.
• 变换后的循环执行一次内存操作能够执行更多的工作,展开后的循环受限于内存的可能性较小.能够减少 load 操作的一些延迟.

其余很多优化最终的目的也是减少访存的延迟,精简指令的数量.

风险

进行类似循环展开的优化时,对寄存器的需求会增加,这对寄存器的分配增加了难度.地址计算的形式也会变化,会引用比原来多得多的不同内存位置,编译器必须谨慎的构造地址计算的形式.以避免重复计算和对寄存器的过多需求.

优化的时机

可以从几种不同的来源来考虑可供编译器利用的时机:

1. 减少抽象的开销
2. 利用特例
3. 将代码匹配到系统资源

优化的范围

优化的范围从小到大可以分为

1. 局部方法
2. 区域性方法
3. 全局方法
4. 过程间方法

其中全局方法这个说法有些误导性,感觉它才是最大的,所以以后我都会叫它过程内优化.

局部方法主要在单个 basic block 中进行.

区域间方法作用范围大于单个程序块,小于整个过程,一般是在 EBB(Extend Basic Block) 中进行, EBB 的定义是: 扩展基本程序块 一组基本程序块 $\beta_1$、$\beta_2$、$\cdots$、$\beta_n$，其中 $\beta_1$ 具有多个CFG前趋结点，而其它每个 $\beta_i$ 都只有一个CFG前趋结点，为集合中某个程序块 $\beta_j$。