编译原理之代码优化

代码优化的目标、对象、范围和策略

代码优化的目标

• 代码优化的目标，是优化程序对计算机资源的使用。我们平常最关心的就是 CPU 资源，最大效率地利用 CPU 资源可以提高程序的性能。代码优化有时候还会有其他目标，比如代码大小、内存占用大小、磁盘访问次数、网络通讯次数等等。

代码优化的对象

从代码优化的对象看，大多数的代码优化都是在 IR 上做的，而不是在前一阶段的 AST 和后一阶段汇编代码上进行的，为什么呢？

• 其实，在 AST 上也能做一些优化，比如在讲前端内容的时候，我们曾经会把一些不必要的AST 层次削减掉（例如 add->mul->pri->Int，每个父节点只有一个子节点，可以直接简化为一个 Int 节点），但它抽象层次太高，含有的硬件架构信息太少，难以执行很多优化算法。 在汇编代码上进行优化会让算法跟机器相关，当换一个目标机器的时候，还要重新编写优化代码。所以，在 IR 上是最合适的，它能尽量做到机器独立，同时又暴露出很多的优化机会。

代码优化的范围

从优化的范围看，分为本地优化、全局优化和过程间优化。

• 优化通常针对一组指令，最常用也是最重要的指令组，就是基本块。基本块的特点是：每个基本块只能从入口进入，从最后一条指令退出，每条指令都会被顺序执行。因着这个特点，我们在做某些优化时会比较方便。比如，针对下面的基本块，我们可以很安全地把第 3 行的“y:=t+x”改成“y:= 3 * x”，因为 t 的赋值一定是在 y 的前面：

BB1:
	t:=2 * x 
	y:=t + x 
	Goto BB2

• 这种针对基本块的优化，我们叫做本地优化（Local Optimization）。
• 超越基本块的范围进行分析，我们需要用到控制流图（Control Flow Graph，CFG）。CFG 是一种有向图，它体现了基本块之前的指令流转关系。如果从 BB1 的最后一条指令是跳转到 BB2，那么从 BB1 到 BB2 就有一条边。一个函数（或过程）里如果包含多个基本块，可以表达为一个 CFG
  
• 比全局优化更大范围的优化，叫做过程间优化（Inter-procedural Optimization），它能跨越函数的边界，对多个函数之间的关系进行优化，而不是仅针对一个函数做优化。

代码优化的策略

• 最后，你不需要每次都把代码优化做彻底，因为做代码优化本身也需要消耗计算机的资源。所以，你需要权衡代码优化带来的好处和优化本身的开支这两个方面，然后确定做多少优化。比如，在浏览器里加载 JavaScript 的时候，JavaScript 引擎一定会对 JavaScript 做优化，但如果优化消耗的时间太长，界面的响应会变慢，反倒影响用户使用页面的体验，所以JavaScript 引擎做优化时要掌握合适的度或调整优化时机。

一些优化的场景

代数优化（Algebraic Optimazation）

• 代数优化是最简单的一种优化，当操作符是代数运算的时候，你可以根据学过的数学知识进行优化。
• 比如“x:=x+0 ”这行代码，操作前后 x 没有任何变化，所以这样的代码可以删掉；又比如“x:=x0” 可以简化成“x:=0”；对某些机器来说，移位运算的速度比乘法的快，那么“x:=x8”可以优化成“x:=x<<3”。

常数折叠（Constant Folding）

• 它是指，对常数的运算可以在编译时计算，比如 “x:= 20 * 3 ”可以优化成“x:=60”。另外，在 if 条件中，如果条件是一个常量，那就可以确定地取某个分支。比如：“If 2>0Goto BB2” 可以简化成“Goto BB2”就好了。

删除不可达的基本块

• 有些代码永远不可能被激活。比如在条件编译的场景中，我们会写这样的程序：“if(DEBUG) {…}”。如果编译时，DEBUG 是一个常量 false，那这个代码块就没必要编译了。

删除公共子表达式（Common Subexpression Elimination）

• 下面这两行代码，x 和 y 右边的形式是一样的，如果这两行代码之间，a 和 b 的值没有发生变化（比如采用 SSA 形式），那么 x 和 y 的值一定是一样的。

x := a + b 
y := a + b

• 那我们就可以让 y 等于 x，从而减少了一次“a+b”的计算，这种优化叫做删除公共子表达式。

x := a + b 
y := x

拷贝传播（Copy Propagation）和常数传播（Constant Propagation）

• 下面的示例代码中，第三行可以被替换成“z:= 2 * x”， 因为 y 的值就等于 x，这叫做拷贝传播。

x := a + b
y := x
z := 2 * y

• 如果 y := 10，常数 10 也可以传播下去，把最后一行替换成 z:= 2 * 10，这叫做常数传播。再做一次常数折叠，就变成 z:=20 了。

死代码删除（Ded code elimintation）

• 在上面的拷贝传播中，如果没有其他地方使用 y 变量了，那么第二行就是死代码，就可以删除掉，这种优化叫做死代码删除。

一个优化可能导致另一个优化，比如，拷贝传播导致 y 不再被使用，我们又可以进行死代码删除的优化。所以，一般进行多次优化、多次扫描。

数据流分析

基于 CFG 做优化分析的方法框架，就叫做数据流分析。

实例图示

• 在做全局优化时，情况就要复杂一些：代码不是在一个基本块里简单地顺序执行，而可能经过控制流图（CFG）中的多条路径。我们来看一个例子（例子由 if 语句形成了两条分支语句）：
  

基于这个 CFG，我们可以做全局的活跃性分析。从最底下的基本块开始，倒着向前计算活跃变量的集合（也就是从基本块 5 倒着向基本块 1 计算）。

• 需要注意，对基本块 1 进行计算的时候，它的输入是基本块 2 的输出，也就是{a, b,c}，和基本块 3 的输出，也就是{a, c}，计算结果是这两个集合的并集{a, b, c}。也就是说，基本块 1 的后序基本块，有可能用到这三个变量。这里就是与本地优化不同的地方，我们要基于多条路径来计算。
  
• 基于这个分析图，我们马上发现 y 变量可以被删掉（因为它前面的活变量集合{a}不包括y，也就是不被后面的代码所使用），并且影响到了活跃变量的集合。
  
• 删掉 y 变量以后，再继续优化一轮，会发现 d 也可以删掉。
  
• d 删掉以后，2 号基本块里面已经没有代码了，也可以被删掉，最后的 CFG 是下面这样：
  
• 到目前为止，我们发现：全局优化总体来说跟本地优化很相似，唯一的不同，就是要基于多个分支计算集合的内容（也就是 V 值）。在进入基本块 1 时，2 和 3 两个分支相遇（meet），我们取了 2 和 3V 值的并集。这就是数据流分析的基本特征。

半格理论

• 首先，半格是一种偏序集。偏序集就是集合中只有部分成员能够互相比较大小。举例来说会比较直观。在做全局活跃性分析的时候，{a, b, c}和{a, c}相遇，产生的新值是{a, b, c}。我们形式化地写成{a, b, c} Λ {a, c} = {a, b, c}。这时候我们说{a, b, c}是可以跟{a, c}比较大小的。那么哪个大哪个小呢？
  • 如果 XΛY=X，我们说 X<=Y。
• 所以，{a, b, c}是比较小的，{a, c}是比较大的。
• 当然，{a, b, c}也可以跟{a, b}比较大小，但它没有办法跟{c, d}比较大小。所以把包含了{{a,b, c}、{a, c}、{a, b}、{c, d}…}这样的一个集合，叫做偏序集，它们中只有部分成员之间可以比较大小。哪些成员可以比较呢？就是下面的半格图中，可以通过有方向的线连起来的。
• 半格可以画成图形，理解起来更直观，假设我们的程序只有 a, b, c 三个变量，那么这个半格画成图形是这样的：
  
• 沿着上面图中的线，两个值是可以比较大小的，按箭头的方向依次减少：{}>{a}>{a, b}> {a,b, c}。如果两个值之间没有一条路径，那么它们之间就是不能比较大小的，就像{a}和{b}就不能比较大小。
• 对于这个半格，我们把{}（空集）叫做 Top，Top 大于所有的其他的值。而{a, b, c}叫做Bottom，它是最小的值。
  • 如果一个偏序集中，任意两个元素都有最大下界，那么这个偏序集就叫做交半格（MeetSemilattice）。
  • 与此相对应的，如果集合中的每个元素都有最小上界（Least Upper Bound），那么这个偏序集叫做并半格（Join Semilattice）。
  • 如果一个偏序集既是交半格，又是并半格，我们说这个偏序集是一个格，示例的这个偏序集就是一个格。