编译器设计(十一)——标量优化

一、简介

所谓的标量优化，指的是单个控制线程下代码的优化。

大多数优化器都被构建为一系列处理趟（pass），如下图所示。每趟以IR形式的代码作为其输入，以重写后的IR代码版本作出其输出。这种结构将实现划分为若干小片段，从而避免了大型单块程序引起的部分复杂性。这允许独立地构建并测试各个处理趟，简化了开发、测试和维护。这建立的方法颇为自然，使编译器能够提供不同的优化级别，每个级别规定了一组需要运行的处理趟。趟结构使编译器编写者能够多次运行某些趟（如果需要的话）。实际上，某些趟只应该运行一次，而其他趟可能需要在优化过程中的不同时机多次运行。

在优化器的设计中，变换的选择和变换顺序的确定，对于优化器的整体有效性具有非常关键的作用。变换的选择决定了优化器能够发现IR程序中的哪些低效性，以及优化器如何重写代码以消除这些低效性。编译器应用变换的顺序则决定了各趟处理之间的交互方式，如前一趟的优化结果可能会影响后一趟的优化。

二、消除无用和不可达代码

操作可能是无用的，意即其结果没有外部可见的效应；操作可能是不可达的，意即它不可能执行。这两类代码有个术语叫“死代码”，也有书只将无用代码称为“死代码”。

删除无用或不可达代码可以缩减代码的IR形式，这会导致可执行程序更小、编译更快、通常执行也更快。同时，它还可以增强编译器改进代码的能力。

因为消除无用和不可达代码的算法会修改程序的控制流图（CFG），我们将审慎地区分术语分支（br）和跳转（jump），分支指令会根据比较的结果决定是否跳转至目标地址，跳转指令则会直接跳转至目标地址。

2.1 消除无用代码

后向支配性（postdominance ）：在CFG中，如果从i到CFG出口结点的每条路径 都经过j，则结点j后向支配结点i。可参见支配性的定义。

上CFG图各个结点的后向支配者集合如下表：

控制依赖性（control dependence）：在一个CFG中，结点j在控制上依赖于结点i，当且仅当以下条件成立。

• 存在一条 从i到j的非空路径，使得j后向支配路径上i之后的每个结点。一旦执行从该代码路径开始，那么要到达CFG的出口，控制流必定要经过j(根据后向支配性的定义）。
• j并不严格后向支配i。有另一条离开i的边，控制流可能由某条路径流向另一个不在i到j的路径上的结点。必定有一条从该边开始的路径通向CFG的出口结点，且不经过j。

换言之，有两条或更多条边离开程序块i，如上CFG图中的B₁、B₅、B₃。从i离开到CFG出口的所有路径上，有一条或多条边通向j，也有一条或多条边并不通向j。因而，在程序块i结束处的分支指令处所作的决策将会确定是否执行j。如果j中的一个操作是有用的，那么结束i的分支指令也是有用的。从概念上可知，结点j控制上依赖结点i，其实也就是结点i是结点j的反向支配边界（Reverse Dominance Frontier，记作RDF(j)），可参见支配边界。

上CFG图各个结点的支配边界如下表：

下图是消除无用代码的算法，称为为Dead，算法的输入为SSA IR。Dead由两趟组成：第一趟Mark，依赖于反向支配边界，发现有用操作的集合并对其做标记；第二趟Sweep，负责删除没有标记为有用的操作。

第一趟。Mark会遍历程序中的每个操作i：清除掉i的mark字段；若i是关键（critical）操作，则将其标记为有用的，并将i添加至WorkList。如果一个操作跟过程的返回结果有关（如对引用调用参数或全局变量赋值赋值、或通过具有歧义的指针赋值、或作为return语句的返回值），或者操作是输入输出语句，或者操作可以影响到当前过程外的可以访问的某个内存中的值，则称这个操作为关键操作。关键操作的例子包括过程的起始代码序列和收尾代码序列，以及调用位置处的调用前代码序列和返回后代码序列。

接下来，算法遍历WorkList，从中取出每个操作i（假设i形如x <- y op z）：如果y的定义def(y)没有被标记为有用的，则对其标记并添加至WorkList；z也重复y的操作；接着遍历操作i所处块的反向支配边界集，将每个反向支配边界块结束时的分支指令标记为有用的。

第二趟。Sweep会将任何未标记的分支指令替换为一个跳转指令，跳转到该程序块的第一个包含有用指令的后向支配者（post dominator）。如果分支指令未被标记，那么从其后继结点一直到其直接的后向支配者结点，都不包含有用操作。（否则，如果其中有某些操作被标记，那么该分支指令也将被标记。）如果其直接后向支配者不包含被标记的操作，也有同样的论点成立。为找到最接近的有用后向支配者，该算法可以向上遍历后向支配者树，直至找到包含有用操作的程序块。因为根据定义，出口程序块是有用的，所以该查找必定会停止。

2.2 消除无用控制流

消除无用代码的优化带有一种副作用，即可能会产生无用控制流。所以Mark、Sweep之后会再执行一趟叫做为Clean的算法，消除无用控制流来简化CFG。Clean直接运行在过程的CFG上，它使用以下4个变换。

1. 合并冗余分支指令：如果Clean发现一个程序块B_i以分支指令结束，但该分支指令的两个目标是同一个程序块B_j，则将其替换为到目标程序块的跳转指令，并调整程序块B_i的后继结点列表和B_j的前驱结点列表。
   
2. 删除空程序块：如果Clean发现一个程序块只包含一条跳转指令，再无其他指令，则可以将该程序块合并到其后继结点。当有其他趟从程序块B_i中删除了所有操作时，就会出现这种情况。
   
3. 合并程序块：如果Clean发现一个程序块B_i结束于到B_j的跳转指令，且B_j只有一个前趋结点，那么就可以合并这两个程序块。
   
4. 提升分支指令：如果Clean发现程序块B_i结束于到空程序块B_j的跳转指令，且B_j以分支指令结束，那么Clean可以将B_i程序块末尾的跳转指令替换为B_j中分支指令的副本。
   

Clean按后根次序遍历（postOrder）流图，因此B_i的后继结点会在B_i之前被简化，除非其后继结点在后根次序编号下位于某条后向边上。在这种情况下，Clean将先访问前趋结点，而后访问后继结点，在有环图中这是不可避免的。在前趋结点之前简化后继结点可以减少实现必须移动某些边的次数。Clean算法如下图所示。

Clean本身不能消除空循环。假设下图B₂为空，则B₂只有结束处的一条分支指令，且两个目标地址不同。从上文4个变换条件可知，Clean无法将其消除，但通过Clean和Dead（见上文2.1）之间的协作可以消除这个空循环。

Dead使用控制依赖性来标记有用的分支指令。如果B₁和B₃包含有用的操作，而B₂没有有用操作，那么Dead中的Mark处理趟将判断B₂结束处的分支指令不是有用的，因为B₂ $\in$ RDF(B₃)。由于该分支指令是无用的，计算分支条件的代码也是无用的。
因而，Dead可以消除B₂中所有的操作，并将其结束处的分支指令转换为一个跳转指令，跳转到其最接近且有用的后向支配者B₃。这消除了原来的循环，并产生了下图中的CFG。

在这种形式下，Clean会将B₂合并到B₁中，从而产生了下图中的CFG。

该操作也使得B₁末尾处的分支指令变成冗余的。Clean会将其重写为跳转指令，从而产生了下图中的CFG。此时，如果B₁是B₃的唯一剩余前趋结点，则Clean会将这两个程序块合并为一个程序块。

与向Clean添加一个处理空循环的变换相比，这种协作更简单且更有效。

2.3 消除不可达代码

有时候CFG中包含了不可达的代码。编译器应该找到不可达程序块并删除它们。程序块可能因两个不同的原因而变为不可达代码：可能没有穿越CFG的代码路径到达该程序块，或者到达该程序块的代码路径是不可能执行的，比如受控于一个条件判断的代码，如果条件表达式的值总是false，则该代码是不可能执行的。

第一种情况可以参考上文2.1 中的算法，在CFG上执行标记-清除风格的可达性分析。第二种情况处理起来比较复杂，需要编译器推断控制分支指令表达式的值，7.1 合并优化 中的算法可以做到。

三、代码移动

3.1 缓式代码移动

缓式代码移动（Lazy Code Motion, LCM）专注于将不变的表达式从循环中移出，从而减少循环时执行无效的操作。该变换插入代码以使这些操作在所有代码路径上都变成冗余的，并删除这些新的冗余表达式。

冗余的概念在局部值编号和超局部值编号中介绍过。

• 冗余：如果在能够到达位置p的每条路径上表达式e都巳经进行过求值，那么表达式 e在位置p处是冗余的。
• 部分冗余：如果表达式e在到达位置p的部分（而非全部）代码路径上是冗余的，则表达式e在位置p处是部分冗余的。

在下图a中，a <- b * c存在于通向汇合点的一条路径上，但在另一条路径上不存在。为使第二个计算成为冗余的，LCM向另一条代码路径插入了对a <- b * c的求值，如下图b所示。在下图c中，沿循环的后向边a <- b * c是冗余的，但在进入循环的边上却并非如此。在循环之前插入一个对a <- b * c的求值，使得该表达式在循环内部变为冗余的，如下图d所示。通过使循环中不变的计算成为冗余并消除，LCM将其从循环移出，这种优化在独立进行时被称为循环不变量代码移动（loop-invariant code motion）。

LCM算法运行在程序的IR形式及其CFG上，而非在SSA形式上。它使用3组不同的数据流方程，并从其结果 推导出额外的集合。算法为CFG中的每条边都生成了一个表达式集合，其中包含了沿该边应该求值的所有表达式，并为CFG中的每个结点都生成了一个表达式集合，其中的表达式在对应程序块中的向上展现求值应该删除。使用一个简单的重写策略即可解释这些集合并修改代码。

LCM同时计算了可用表达式和可预测表达式，使用这些分析的结果，用集合Earliest(i, j)来标注CFG中的每条边，这个集合包含了以该边为最早合法置放位置（earliest legal placement）的所有表达式。LCM接下来求解第三个数据流问题，以发现延迟置放（later placement）情况，即将表达式求值延迟至最早置放位置之后、但仍然具有同样效果的情形。延迟置放是颇为理想的清况，因为它们可以缩短由插入的求值定义的值的生命周期。最终，LCM计算其最终产物，集合Insert和Delete，这两个集合用于指引其代码重写步骤。

1) 可用表达式

在之前的文章《数据流分析2.4.1》中对可用表达式及其方程做过介绍，用一个集合AvailIn(n)来表示，过程中从程序入口处到结点n的所有可用表达式的名字。因为LCM需要程序块末尾处的可用表达式信息，所以这里使用的集合是AvailOut（AvailIn表示的是入口处），与AvailIn方程只有微小的区别。

对于表达式e和程序块b来说，如果在从程序入口块n₀到b的每条代码路径上，e都已经求值且其参数在求值后均未重新定义过，则表达式e在程序块b的出口处是可用的，用AvailOut(b)表示。定义AvailOut(b)的方程如下：

$AvailOut(n)={\bigcap }_{m\in preds(n)}(UEExpr(m)\cup (AvailOut(m)\cap \overline{ExprKill(m)}))$

方程的初始条件为：$AvailOut(n_0)=\varnothing$， A v a i l O u t ( i ) = { a l l AvailOut(i)= \{ all AvailOut(i)={all $expression\}$，$\forall n\ne n_0$

如果表达式e $\in$ AvailOut(b)，则编译器可以将e的一个求值放置在程序块b末尾，并获取从n₀到b的任一控制流路径上最近一次求值产生的结果。如果e $\notin$ AvailOut(b)，那么从e最近一次求值以来它的某个子表达式已经修改过，因而程序块b末尾处对e的求值很可能生成一个不同的值。

LCM使用AvailOut集合来帮助判断表达式在CFG中可能的放置位置，即编译器可以判断它能够将表达式e的求值在CFG中（忽略对e的使用）向前移动多远。

2) 可预测表达式

在之前的文章《数据流分析2.4.3》中对可预测表达式及其方程做过介绍。

由于LCM在每个程序块的开始和结束处都需要有关可预测表达式的信息，因而我们重构了可预测表达式的方程，引入了集合AntIn(n)，以表示在对应于CFG中结点n的程序块入口处可预测表达式的集合。定义AntIn(n)集合的方程如下：

$AntIn(m)=UEExpr(m)\cup (AntOut(m)\cap \overline{ExprKill(m)})$

$AntOut(n)={\bigcap }_{m\in succ(n)}AntIn(m)，n\ne n_f$

方程的初始条件为：$AntOut(n_f)=\varnothing$， A n t O u t ( n ) = { a l l AntOut(n)= \{ all AntOut(n)={all $expression\}$，$\forall n\ne n_f$

AntOut提供了将一个求值提升到当前程序块开始或结束处的安全性方面的信息。如果x $\in$ AntOut(b)，那么编译器可以将x的一个求值放置在b的末尾，这有两点保证。首先，b末尾处的求值结果，将与x沿过程中任一执行路径的下一次求值结果相同。其次，沿离开程序块b的任一执行路径，在重定义x的任一参数之前，程序会对x进行求值。

3) 最早置放

如果给出了可用性和可预测性的解，对于每个表达式，编译器都可以判断在程序中最早于何处可以对该表达式进行求值。为简化各个方程，LCM假定它会将求值放置在CFG的某条边上，而非某个特定程序块的起始或结束处。计算出一条边供放置表达式的求值操作之用，使得编译器可以推迟具体的放置决策：到底是将求值操作放置在边的源结点末尾处、边的目标结点的起始处，还是在边的中间插入一个新的程序块来放置表达式的求值操作。（参见数据流分析3.5 中对关键边的讨论。）

用集合Earliest(i, j)来标注CFG中的每条边。对于CFG中一条边和表达式e来说，e属于Earliest(i, j)，当且仅当：编译器可以合法地将e移动到，且无法将其移动到CFG中更早的边上。Earliest方程为处理该条件，将其编码为三个条件的交集：

$Earliest(i,j)=AntIn(j)\cap \overline{AvailOut(i)}\cap (ExprKill(i)\cap \overline{AntOut(i)})$

这些条件如下定义了e的一个最早置放：

• e $\in$ AntIn(j) 意味着编译器可以安全地将e移动到j的起始处。可预测性方程确保：e在j的起始处，将与其在离开j的任一代码路径上产生相同的值，且这些代码路径都对e进行了求值。
• e $\notin$ AvailOut(i) 说明，此前对e的求值计算结果在i的出口处均不可用。如果e $\in$ AvailOut(i)，那么在边(i,j)插入e将是冗余的。
• 第三个条件包含两种情况。如果e $\in$ ExprKill(i)，则编译器无法穿过程序块i移动e，因为有一个定义在i中。如果e $\notin$ AntOut(i)，则由于对某些边，e $\notin$ AntIn(k)，编译器无法将e移动到i中。如果二者之一成立，那么在CFG中不能将e移动到比更早的位置上。

CFG的入口结点n₀带来了一个特例。LCM无法将表达式移动到早于n₀的位置上，因此对任何k，LCM都会忽略掉Earliest(n₀, k)中的第三个条件。

4) 延迟置放

LCM中最后一个数据流问题用于判断何时一个最早置放能被推迟到CFG中稍后的一个位置，而仍然能够实现相同的效果。

延迟分析表述为CFG上的一个前向数据流问题，其目标在于为每个结点n关联一个集合LaterIn(n)，为每条边关联一个集合Later(i, j)。LCM初始化LaterIn集合如下：

$LaterIn(j)={\bigcap }_{i\in pred(j)}Later(i,j)，j\ne n_0$

$Later(i,j)=Earliest(i,j)\cup (LaterIn(i)\cap \overline{UEExpr(i)})，i\in pred(j)$

方程的初始条件为：$AntOut(n_f)=\varnothing$， A n t O u t ( n ) = { a l l AntOut(n)= \{ all AntOut(n)={all $expression\}$，$\forall n\ne n_f$

表达式e $\in$ LaterIn(k)，当且仅当：到达k的每条代码路径都包含一条边使得e $\in$ Earliest(p,q)，且从q到k的路径既未重定义e的操作数，也不包含e的最早置放能够预期的对e的求值。Later方程中的Earliest条件确保了Later(i, j)包含Earliest(i, j)。在e能够从向前（沿控制流方向）移动（即e $\in$ LaterIn(i))，且e置放在i入口处却无法预期到i中对e的使用（e $\notin$ UEExpr(i)）的情况下，Later方程的其余部分会将e置于Later(i, j)中。

给定Later和LaterIn集合，e $\in$ LaterIn(i)意味着编译器能够将e的求值穿过i向前移动而不会损失任何利益，即表达式e在程序块i中的求值（如果有的话）是无法通过早期求值来预测的，而e $\in$ Later(i, j)意味着编译器能够将e在i的求值移动到j中。

5) 重写代码

执行LCM算法的最后一步是利用从数据流计算推导出的知识重写代码。为驱动重写过程，LCM会计算两个额外的集合Insert和Delete。

Insert集合对每条边规定了LCM应该在该边插入的计算。

$Insert(i,j)=Later(i,j)\cap \overline{LaterIn(i)}$

如果i有一个后继结点，则LCM可以将计算插入到i末尾。如果j只有一个前趋结点，则算法可以将计算插入至j的入口处。如果上述两个条件均不成立，那么边是一条关键边，而且编译器应该在该边中间插入一个程序块来拆分该边，并将Insert(i, j)中表达式的求值放入该程序块。

Delete集合对每个程序块规定了LCM应该从该程序块删除的计算。

$Delete(i)=UEExpr(i)\cap \overline{LaterIn(i)},i\ne n_0$

当然，Delete(n₀)为空，因为n₀之前没有其他程序块。如果e $\in$ Delete(i)，那么在所有的插入已经进行之后，e在i中的第一次计算将变为冗余的。而e在i中的后续各次求值中，凡是具有向上展现使用的都是可以删除的，这里向上展现使用是指某个操作数并不是在i的起始位置与该次求值之间定义的。因为e的所有求值均定义了同一个名字，所以编译器无需重写对被删除求值的后续引用。这些引用仍然指向LCM已经证明了的能够产生同样结果的早期求值。

3.2 代码提升

代码提升（code hoisting）使用了可预测分析的结果，来减少指令的重复，从而减少代码长度。该变换试图发现下述情形：插入某个操作使得其他几个同样的操作变为冗余，且不改变程序计算的值。

如果对某个程序块b，表达式e $\in$ AntOut(b)，这意味着e沿离开b的每条代码路径都进行了求值，且e在b末尾处的求值使得离开b的各条路径上的第一次求值变为冗余。为减小代码长度，编译器可以在b的末尾插入对e的一个求值，并将离开b的各条路径上对e的第一次求值替换为对此前计算值的引用。这种变换的效果是，将对e的求值操作的多个副本替换为一个副本，从而减少了编译后代码中操作的总数。

为直接替换这些表达式，编译器需要定位它们。当然，编译器可以插入对e的求值，然后求解另一个数据流问题，证明在b的末尾到e的某次求值之间没有重新定义e的任何操作数。另外，编译器还可以遍历离开b的每条代码路径，通过考察代码路径上各个程序块的UEExpr集合，来找到定义e的第一个程序块。这两种方法看起来都比较复杂。

一种更简单的方法是，编译器访问每个程序块b，然后在b的末尾处对每一个表达式e $\in$ AntOut(b)插入一个对e的求值。如果编译器使用了一种统一的命名规范，正如LCM的讨论表明的那样，那么每个求值都将定义对应的适当名字。而对LCM或超局部值编号算法的后续应用，将会删除新的冗余表达式。

四、特化

用于执行特化的技术在之前文章已经介绍过。局部值编号、超局部值编号、稀疏简单常量传播、过程间常量传播，运算符强度消减（本节7.2）、以及窥孔优化（下一篇文章介绍）。

4.1 尾调用优化

如果一个调用是过程的最后一个操作，我们就称该调用为尾调用(tail call)。编译器可以针对上下文而特化尾调用，从而消除过程链接代码的大部分开销。

// case 1, not a tail call
f(x) {
  y = g(x);
  return y;
}

// case 2, not a tail call
f(x) {
  return g(x) + 1;
}

// case 3, not a tail call
f(x) {
  g(x);
}

// case 4, tail call
f() {
  x = 2;
  return g(x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

我们在过程抽象中已经介绍过运行时结构，这里会以此内容作为基础，且这块内容不再重复解释。

假设o调用p、p又调用q。如果p中对q的调用是尾调用，那么在调用q之后的返回后代码序列和p本身的收尾代码序列之间，不存在有用计算。所以，任何用于保留和恢复p的状态的代码，只要超出了从p返回到o的所需，就都是无用的。

在p中对q的调用位置处，最小的调用前代码序列必须对从p传递给q的实参求值，并根据需要调整存取链或display数组。

• 它完全没有必要保存任何由调用者保存的寄存器（caller寄存器），因为它们不可能是活跃的；
• 它也不必分配一个新的AR，因为q可以使用p的AR。
• 它决不能改动返回到o所需的上下文，即o传递到p的返回地址和调用者的ARP，以及p保存到AR中的由被调用者保存的寄存器（callee寄存器）。

这一上下文的存在，将使得q中的收尾代码序列直接将控制返回到o。然后，q必须执行一个定制的起始代码序列，以便与p中的最小调用前代码序列匹配，且p中的最小调用前代码序列必须跳转到q的起始代码序列。q的起始代码序列只保存p的状态中对返回到o有用的那部分，并不保存由被调用者保存的寄存器，这是出于两个原因。

• 其一，p在相应寄存器中的值不再是活跃的。
• 其二，p留在AR的寄存器保存区中的那些值是返回到o所需要的。

因而，q中的起始代码序列应该初始化q需要的局部变量和值，接下来它应该分支到q的实际代码执行。

在对p中的调用前代码序列和q中的起始代码序列进行上述修改后，尾调用避免了保存和恢复p的状态并消除了该调用的大部分开销。当然，一旦p中的调用前代码序列已经被用这种方法裁剪过，那么p中的返回后代码序列和p的收尾代码序列将变为不可达代码，死代码消除技术可以将其优化掉。

如果尾调用是一个自递归调用（即p和q是同一个过程），那么尾调用优化可以产生特别高效的代码。在尾递归中，整个调用前代码序列都退化为参数求值和一个返回例程顶部的分支指令。最终跳出递归的返回只需要一条分支指令，而非为每次递归调用都使用一条分支指令。结果产生的代码在效率上可以与传统的循环相匹敌。

4.2 叶调用优化

叶过程：不进行过程调用的过程称。

非叶过程中，过程起始代码序列可能会将寄存器中的返回地址保存到AR中的一个槽位里。但如果是叶过程，这个操作将是不必要的。如果因其他用途而需要保存返回地址的寄存器，那么寄存器分配器可以溢出该值。

在叶过程中，寄存器分配器应该设法优先使用由调用者保存的寄存器，而后才轮到由被调用者保存的寄存器。至于为什么这么做，参见子程序调用时寄存器的保存方式。

此外，编译器还可以避免为叶过程分配活动记录的运行时开销。在使用堆分配AR的实现中，分配AR的代价可能会非常高。在只有单个控制线程的应用程序中，编译器可以静态分配任一叶过程的AR。具有更激进分配策略的编译器，可能会分配一个足够大的静态AR供任一叶过程使用，并让所有的叶过程共享这一AR。

如果编译器能够访问到叶过程及其调用者的代码，则它可以在（叶过程的）每个调用者的AR中为叶过程的AR分配空间。这种方案将AR分配的代价均摊到至少两个调用上，即对调用者的调用和对叶过程的调用。如果调用者多次调用叶过程，那么这样所带来的节省将以乘法效应倍增。

4.3 参数提升

提升：一类将歧义值移动到局部标量名中以将其暴露给寄存器分配的变换

考虑为一个具有歧义的引用调用参数生成代码，代码可能用两个不同的参数槽位传递同一个实参，或将一个全局变量作为实参传递。除非编译器进行过程间分析来排除这些可能性，否则它必须将所有引用参数都视为可能具有歧义的引用。所以，每次使用这种参数时，都要求发出一条load指令，而每次定义其值时，都要求发出一条store指令。

如果编译器能够证明与该形参对应的实参在被调用者中必定是无歧义的，那么它可将该参数的值提升到一个局部标量值中，使被调用者能够将其保持在寄存器中。如果被调用者并不修改该实参，则提升后的参数可以直接传值。如果被调用者修改该实参且其结果在调用者中是活跃的，那么编译器必须使用传值兼传结果语义来传递提升后的参数。

为对某个过程p应用这种变换，优化器必须识别所有可以调用p的调用位置。它或者证明该变换对所有这些调用位置都是适用的，或者创建p的一个副本来处理提升后的值（参见6.2 过程复制）。

五、冗余消除

对于代码位置p和计算x+y来说，如果沿到达p的每条代码路径，x+y都已经进行过求值，且在求值后x和y均未修改过，那么x+y在位置p处是冗余的。冗余计算通常是因转换或优化所致。

我们已经阐述了用于冗余消除的3种有效技术：局部值编号（LVN）、超局部值编号（SVN）和缓式代码移动（LCM）。这些算法涵盖的跨度从简单和快速(LYN)到复杂和全面(LCM)。虽然所有这3种方法在涵盖的范围上有所不同，但它们之间的主要区别在于用来确定两个值相等的方法。

5.1 值相同与名字相同

LVN引人了一种简单的机制来证明两个表达式具有相同的值。LVN依赖于两个原则，它为每个值分配一个唯一的标识号（即其值编号）。它假定：如果两个表达式运算符相同，且其操作数均具有相同的值编号，那么两个表达式将产生相同的值。

利用这些规则，LVN可以证明2+a与a+2具有相同的值，或在a和b具有相同值编号的情况下，2+a与2+b也具有相同的值。编译器不能证明a+a和2*a具有相同的值，因为两个表达式的运算符不同。类似地，它也不可能证明a+0和a具有相同的值。因而，我们可以用代数恒等式（2.1.2 扩展LVN算法）来扩展LVN，这些恒等式能够处理定义明确但不为原来的规则涵盖的情况。

与之相对，LCM依赖于名字来证明两个值具有相同的数值。如果LCM看到表达式a+b和a+c，它会假定二者具有不同的值，因为b和c具有不同的名字。该算法依赖于词法上的比较，即要求名字相同。底层的数据流分析不能直接包容值相同的概念，数据流问题管理一个预定义的名字空间，并在CFG上传播有关这些名字的事实。LVN使用的那种特设比较不适合于数据流处理的框架。

一种改进LCM有效性的方式是，在应用LCM之前将值的相等关系编码到代码的名字空间中（本节6.4 重命名会介绍）。LCM可以识别LVN和SVN均不能发现的冗余。特别地，它可以发现穿越CFG中汇合点的路径上的冗余，包括那些沿循环控制(loop-closing)分支路径流动的值，而且它还可以发现部分冗余。而另一方面，LVN和SVN都可以发现值的冗余和简化，这些是LCM无法找到的。因而，将值的相等关系编码到名字空间中，使编译器能够同时利用这两种方法的优势。

5.2 基于支配者的值编号算法

优化简介阐述了局部值编号（LVN）及其推广到扩展基本程序块(EBB)的情形——超局部值编号（SVN）。虽然SVN能够比LVN发现更多的冗余，但它仍然会错失某些时机，因为它被限制在EBB中。

比如，在下图给出的CFG片断中，SVN将处理路径(B0，B1，B2)和(B0，B1，B3)。因而，它能够在前缀路径(B0，B1)形成的上下文中同时对B2和B3进行优化。因为B4是一个汇合点，SVN在优化B4时无法利用此前的上下文。

B4能够依赖哪个状态？B4无法依赖在B2或B3中计算的值，因为二者均未能出现在到达B4的全部路径上。与此相反，B4可以依赖B0和B1中计算的值，因为二者是B4的支配者。所以，我们可以利用关于B0和B1中计算的信息来扩展针对B4的值编号算法，但也必须考虑到B0和B1到B4之间的程序块(B2或B3)中赋值造成的影响。

考虑出现在B1末尾并再次出现在B4起始处的表达式x+y。如果B2和B3均未重定义x或y，那么B4中对x+y的求值是冗余的，优化器可以重用在B1中计算的值。在另一方面，如果(B2或B3中）有任何一个程序块重定义了x或y，那么B4中对x+y的求值将得到与B1中求值不同的结果，因而该求值不是冗余的。

幸而，SSA形式名字空间恰好包含了这一区别。在SSA形式中，在某个程序块Bi中使用的名字只能以两种方式之一进入Bi。该名字或者是由Bi入口处的某个$\varphi$函数定义的，或者是在某个支配Bi的程序块中定义的。因而，B2或B3中对x的赋值将为x创建一个新名字，并迫使在B4起始处为x插入一个$\varphi$函数。这个$\varphi$函数为x创建了一个新的SSA形式名，而相关的重命名过程修改了在后续x+y计算中使用的SSA形式名。这样，有关B2或B3中是否存在一个“半途插入”的赋值这一信息，就被SSA形式直接编码到表达式使用的名字当中。我们的算法可以依靠SSA形式名来避免该问题。

在基于支配者的值编号技术（Dominator-based Value Numbering Technique, DVNT）中，给定一个程序块Bi，如何定位到它可以依赖的最近前驱块呢？支配性和支配边界中的内容具有这种效果。Bi在支配者树中的父结点，或者Bi的直接支配结点集合{Dom(Bi) - Bi}中最接近Bi的结点，就是它可以依赖的最近前驱块。DVNT实际上使用SSA形式名作为值编号，因而表达式$a_i\ast b_i$的值编号就是$a_i\ast b_i$第一次求值时定义的SSA形式名。（即如果其第一次求值发生在$t_k\leftarrow a_i\ast b_i$，那么$a_i\ast b_i$的值编号即为$t_k$)

下图是基于支配者的值编号算法。

对每个程序块B而言，DVNT采用三步处理：首先处理B中的$\varphi$函数（如果有的话），其次对赋值进行值编号，最后将相关信息传播到B的后继结点，并对B在支配者树中的子结点进行递归处理。

• 处理B中的$\varphi$函数。DVNT必须为每个$\varphi$函数p分配一个值编号。如果p是无意义（meaningless）的（即其所有参数都具有相同的值编号），那么DVNT会将其值编号设置为其中一个参数的值编号并删除p。如果p是冗余（redundant）的（即它与B中另一个$\varphi$函数产生同样的值编号），那么DVNT会为二者分配相同的值编号并删除p。
  否则，相应的$\varphi$函数将计算一个新值。此时有两种情况。一种情况是，p的参数都有值编号，但这些参数的特定组合此前没有在该程序块中见到过；另一种情况是，p的参数中有一个或多个没有值编号，这种情况是因CFG中的后向边所致。
• 处理B中的赋值。DVNT会遍历B中的各个赋值，并以类似于LVN和SVN的方式处理它们。其中有一个微妙之处是因使用SSA形式名作为值编号所致。在算法遇到语句x <- y op z时，它完全可以将y替换为VN[y]，因为VN[y]中的名字包含了与y相同的值。
• 将信息传播到B的后继结点。一旦DVNT处理了B中所有的$\varphi$函数和赋值，它会访问B在CFG中的每个后继结点s，并更新流经边(B,s)的值对应的$\varphi$函数参数。算法通过修改参数的SSA形式名来记录$\varphi$函数参数当前的值编号。（注意这个步骤与SSA形式构造算法的重命名阶段中对应步骤的相似性。）接下来，算法对B在支配者树中的子结点进行递归处理。最后，它会释放对B使用的散列表作用域。

这种递归模式使得DVNT逄循了支配者树上的一种先根次序遍历，这确保了在访问某个程序块之前，与之相应的适当的表巳经构建完成。

六、为其他变换制造时机

6.1 超级块复制

设想在下图给出的CFG上使用SVN算法。程序块B3和B7具有多个前趋结点的事实，可能会限制优化器改进这些程序块中代码的能力。比如，如果程序块B6对x赋值7，而程序块B8对x赋值13，那么B7中使用的x看起来将接收到值$\perp$（确定是非常量值），即使沿通向B7的每条代码路径该值都是已知且可预测的（常量值）。

在这种情形下，编译器可以复制程序块以产生更适合变换的代码。编译器可以创建B7的两个副本B7a和B7b，并将B7的输入边重定向为(B6,B7a)和(B8,B7b)经过这一改变，优化器可以将x的值7传送到B7a中，将x的值13传送到B7b中。

由于B7a和B7b都具有唯一的前趋结点，编译器实际上可以将这些相关的程序块合并，由B6和B7a产生一个程序块，由B8和B7b产生另一个程序块。这种变换可以消除B6和B8程序块结束处的跳转指令，还使优化和指令调度（后续会介绍）中的进一步改进成为可能。

一种名为超级块复制的复制技术广泛用于为循环内部的指令调度产生额外的上下文环境。在超级块复制中，优化器从循环入口开始，并复制每条代码路径，直至遇到反向分支（即循环控制分支指令）。

将这一技术应用到例子CFG中，将产生下图给出的修改过的CFG。B1是循环入口。循环体中的每个结点都具有一个唯一的前趋结点。如果编译器应用一种超局部优化（基于扩展基本程序块的一种优化），那么它发现的每条路径都只包含循环体的一次迭代。（为发现更长的路径，优化器将需要展开循环，使得超级块复制包含多次迭代。）

超级块复制可以从3个主要方面来改进优化的结果：

• 它可以产生更长的程序块，更长的程序块使局部优化能够处理更多的上下文。
• 它消除了分支，合并两个程序块将消除二者之间的一个分支指令。
• 它在代码中产生了一些可供进一步优化的位置，复制在消除控制流汇合点时，也在程序中产生了一些新的位置，编译器可以在这些位置上推导出关于运行时上下文的更精确知识。

当然，复制也有其自身的代价。它产生了各个操作的多份副本，这导致代码变得更大。由于避免了一些程序块末尾的跳转，更大的代码可能运行得更快速。但如果代码长度的增长导致了一些额外的指令高速缓存失效，代码也可能运行得更慢。在用户更关心代码长度而非运行时速度的应用程序中，超级块复制可能会起相反作用。

6.2 过程复制

内联替换的效果类似于超级块复制，对于p中对q的调用，该变换会创建q的一个独立副本并将其合并到p中对应的调用位置处。

编译器通过复制过程也可以实现内联替换，而且代码增长较少，该思想类似于超级块复制中的程序块复制。编译器可以产生被调用者的多个副本，将一部分调用分配到复制的各个实例上。

通过续密地将调用分配到各个副本，每个调用都有了一个类似的上下文环境，优化可以在该环境中进行。比如，考虑下图给出的简单调用图。假定P3是一个库例程，其行为十分依赖于某个输入参数。如果参数值为1，编译器可以生成能够高效访问内存的代码，而对于其他值，编译器将生成大得多也慢得多的代码。更进一步，假定P0和P1都向P3传递参数值，而P2向其传递参数值17。

在调用图上进行常量传播不会带来帮助，因为对该参数计算出的格值为$1\wedge 1\wedge 17=\perp$。只采用常量传播，编译器仍然必须为P3生成完全通用的代码。过程复制可以创造出使参数值总是为1的代码位置，如下图中的P3a所示。在原来的调用图中阻止了优化的调用(P2,P3)，现在重新分配到P3b。编译器现在可以为P3a生成优化代码，而对P3b生成通用代码。

6.3 循环外提

循环外提将循环中不变的控制流提升到循环之外。如果if-then-else结构中的谓词是循环不变量，那么编译器可以重写循环，将if-then-else抽取到循环之外，并在新的if-then-else的两个分支中分别生成原循环的一个裁剪过的副本。

外提是一种使能变换，它使编译器能够以本来难以实现的方式来调整循环体。外提之后，剩余的循环包含较少的控制流，循环体中执行的分支指令数目较少，用于支持分支指令的其他操作也变少。这将导致更好的指令调度、更好的寄存器分配和更快速的执行。如果原来的循环在if-then-else内部包含循环不变量代码，那么LCM不可以将其移出循环。在外提之后，LCM很容易发现并删除这样的冗余。

6.4 重命名

大多数标量变换都会重写或重排代码中的各个操作。本书中已经多处提到，名字的选择会隐藏或揭示改进代码的时机。比如在LVN中，将程序块中的名字转换为SSA形式名字空间，可以揭示一些本来很难捕获的重用时机。

重命名是一个微妙的问题。各种变换可能得益于具有不同性质的名字空间。长久以来，编译器编写者已经认识到移动和重写操作可以改进程序。同样，他们也应该认识到重命名能够提高优化器的有效性。正如SSA形式巳经表明的那样，编译器不必为由程序员或编译器前端引入的名字空间所限制。重命名为未来的工作提供了丰富的基础。

七、联合优化

7.1 合并优化

有时候，在一种统一的框架下重新表述两种不同的优化并对其联合求解，可以产生以任一组合方式分别运行两种优化所无法得到的效果。举例来说，稀疏简单常量传播(SSCP)算法，它为程序的SSA形式中每个操作的结果分配一个格值。在该算法停止时，它已经为每个定义标记了一个格值：$\top$、$\perp$或某个具体的常量。仅当定义依赖于一个未初始化变量或位于不可达程序块中时，定义的格值才会为$\top$。

SSCP会为条件分支指令使用的操作数分配一个格值。如果该值为$\perp$，那么分支的两个目标均是可达的。如果其值既非$\perp$也非$\top$，那么该操作数必定具有一个已知值，因而编译器可以重写该分支指令，将其替换为到两个目标之一的跳转指令，从而简化了CFG。因为这样做从CFG中删除了一条边，这可能使得原本是分支目标的程序块变为不可达代码。常量传播可以忽略不可达程序块的任何效果。但SSCP没有相应的机制来利用这一知识。

7.2 强度削减

7.3 选择一种优化序列