被发配到中端优化后，才发觉我之前写的前端那都是什么弱智东西，感觉要是把分析 visitor 的那篇博文写完，提溜 c 语言还写不顺畅的我妹过来看看，都能给我照葫芦画瓢地写出来……我的队友真是辛苦了。

前阵子不停地迭代式调研，愣是没写几行代码，好在收获不小，希望这两天能赶紧把自己的那份工作做完吧。

简介

编译器的前端将源代码形式的程序转换为中间表示 IR，后端将 IR 程序转换为某种可以直接在目标机上执行的形式（目标及可以是硬件平台或虚拟机，比如常见的微处理器或者 Java 中的 JVM），在这两个过程之间，是编译器的中间部分优化器。优化器的任务是转换前端产生的 IR 程序，以提高后端生成的代码的质量。为了提高所生成代码的质量，优化编译器需要分析代码并将其重写为一种更加高效的形式。

这里，“提高”的含义通常意味着使编译后的代码执行得更快速，当然也可能意味着使可执行程序在运行时耗费较少的资源或者占用较少的内存空间。所有这些目标，都属于优化的领域。我们把它概括为编译器中端优化。

对优化的考虑

代码优化的目标是在编译时发现有关程序运行时行为的信息，并且利用该信息来改进编译器生成的代码。改进可以有多种形式。

正如上文所说，编译优化最常见的目标是提高编译后代码的运行速度。但对于某些应用程序来说，编译后代码的长度比其执行速度更重要，比如说，考虑某个将烧录到只读存储器的应用程序，其代码长度会影响整个系统的成本；或者说执行之前需要通过带宽有限的信道进行传输的代码，其代码长度将对完成时间有直接影响。对这些程序进行优化时，应该生成占用更少空间的代码。优化的其他目标包括降低执行的能耗、提高代码对实时事件的响应或降低对内存的总访问量等。

在介绍优化器的技术之前，先引入两个名词：安全性（safe）和获利 / 有利可图（profitable），在各种优化相关的论文中我们也会经常看到这两个词。有一说一，我第一次看到 profitable 这个词的时候绞尽脑汁想翻译出那种，“可以获得性能提升的 / bonus”，这种感觉，但感觉实在是太迂了，而且发现各种官方书籍里也自然而然地译成了难听的“有利可图”，那我就不管了。

• 安全性

如果一个变换不会改变程序的运行结果，那么该变换就是安全（safe）的。

如果要指出编译器必须满足的一条最重要的准则，那么它就是正确性：编译器所产生代码的语义必须与输入程序相同。在优化器每次应用变换时，其施加的操作必须保持编译器原有转换过程的正确性。

通常，语义（meaning）指代程序的可观察行为。如果程序终止，无论编译器使用的是哪种转换方案，对于一个安全的编译器来说，在程序停止的前一时刻，所有可见变量的值都应该是相同的。

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

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

因而，如果两个表达式对可见外部环境的影响是相同的，那么二者就是可观察等价的。

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

• 获利

当在某个位置上应用一种变换可以带来实际的改进时，我们就说这种变换是有利可图（profitable）的。

虽然感觉这个翻译很生草，但我也想不到更合适的词了。

优化的时机可能是由许多来源导致的。低效性的主要来源是对源语言抽象的实现，因为从前端的解析过程我们可以知道，从源代码到 IR 的转换是一个局部的解析过程，进行转换的时候我们只关心当前解析到的文法（也就是递归下降），而没有对语句的外围上下文进行广泛分析，因此该转换生成的 IR 通常是为了处理各种源语言结构的最一般情形。在具有上下文背景的情况下，优化器通常可以判断代码是否需要这种完全的一般性，如果不需要的话，优化器完全可以用更受限、更高效的方式来重写代码。

比如，我们给出如下的 C 程序：

1
2
3
4
5

int main() {
    int a = 5;
    int b = a + 3;
    return b;
}

如果不开启优化，我们得到的是一个一般性的 IR，几乎等同于直译，看着就很烦：

1
2
3
4
5
6
7
8
9
10
11

define dso_local i32 @main() {
0:
	%2 = alloca i32
	%1 = alloca i32
	store i32 5, i32* %1
	%3 = load i32, i32* %1
	%4 = add i32 %3, 3
	store i32 %4, i32* %2
	%5 = load i32, i32* %2
	ret i32 %5
}

但开启优化后，我们得到一段受限但是明显更高效的 IR 代码：

1
2
3
4

define dso_local i32 @main() {
0:
	ret i32 8
}

优化时机的另一个重要来源是目标机。编译器必须详细了解目标机影响性能的哪些属性，诸如功能单元的数目和能力、内存层次结构中各个层次的延迟和带宽、指令集支持的各种寻址方式、罕见或复杂操作的可用性等问题，都会影响到编译器应该为某个给定应用程序生成代码的种类。不过，这倒不是我需要负责的那部分工作，因此后面就不对之进行叙述了。

优化的时机

一般来说，可供优化编译器利用的时机有几种不同的来源：

1. 减少抽象的开销：程序设计语言印入的数据结构和类型需要运行时支持，优化器可以通过分析和变换来减少这种开销。
2. 利用特例：通常，编译器可以利用操作执行时所处上下文的相关背景，来特化该操作，从而减少该操作的一些代价。
3. 将代码匹配到系统资源：如果程序的资源需求与处理器的能力不符，则编译器可能需要变换该程序，使其需求更加切合可用的资源。

优化的范围

优化可以在不同的粒度或者范围上运作，它们向优化器提供了不同的优化时机。总地来说，变换和支持变换的分析作用于 4 种不同的范围之一：局部的、区域性的、全局的或者整个程序。

在我的工作中，我主要关注全局的代码优化。

局部方法

局部方法作用于单个基本程序块：最长的一个无分支代码序列。在我们的 LLVM IR 中，就是一个 Basicblock。

在基本程序块内，有两个重要的性质：

1. 语句是顺序执行的。
2. 如果任意一个语句执行，那么整个程序块也必定执行，除非发生运行时异常。

与更大的代码范围相比，这两个性质使得编译器能够利用相对简单的分析来证明更强的事实。因此，局部方法有时能够做出在更大范围上无法达到的改进。但是，局部方法只能改进出现在同一基本程序块中的各个操作。

区域性方法

区域性方法的作用范围大于单个基本程序块，小于一个完整的过程。我们用一个控制流图（Control Flow Graph，CFG）作为例子进行说明：

在这个例子中，编译器可能将整个循环 {, , , , , , } 作为一个区域考虑。有时候，与考虑整个过程相比，考虑完整过程代码的一个子集能够使我们进行更敏锐的分析并得到更好的变换结果。例如，在循环嵌套的内部，编译器也许能够证明一个被大量使用的指针是不变量（单值），尽管该指针可能在过程中的其他地方被修改。这样的背景能够用来进行一些优化，比如将该指针引用的值保存在寄存器中等。

编译器可以用许多不同的方式来选择需要优化的区域。区域可以用某种源代码控制结构（比如循环嵌套）定义。编译器可以考察区域中形成扩展基本程序块（Extended Basic Block，EBB）的基本程序块集合。

扩展基本程序块：一组基本程序块 ，其中 具有多个 CFG 前驱结点，而其他每个 都只有一个 CFG 前驱结点，为集合中某个程序块 。

比如，上面的例子包含 3 个 EBB：{ ~ }, {} 和 {}。虽然两个单程序块的 EBB 相对于纯粹的局部视图并没有什么优势，但较大的那个 EBB 是可以提供优化时机的。最后，编译器可以考虑通过某种图论性质定义的 CFG 子集，比如 CFG 中的支配关系或者强连通分量。

支配者：在一个 CFG 图中，当且仅当从根结点到 y 的每条路径都包含结点 x 时，x 支配 y。

区域性方法可以使得编译器将工作重点集中在频繁执行的区域上，例如循环体，编译器可以对不同的区域应用不同的优化策略。同时，对代码中有限区域的关注通常可以使编译器推导出有关程序行为的更准确信息，这又进一步暴露了改进和优化的时机。

全局方法

这种方法（global）也被称为过程内（描述用于单个过程的技术）方法，它使用整个过程作为上下文，初见 global 这个词语，或许很容易将它跟整个程序范围（whole program）混淆，正如词法作用域规则的讨论中所说的 “global” 那样，事实上在分析和优化中，全局意味着与单个过程相关的上下文，千万不要混淆了——“全局”在这里是不“通用”的！

它的动机很简单，就是局部最优的决策在更大的上下文中可能带来坏的结果。对于分析和变换来说，过程为编译器提供了一个自然的边界——它是一种抽象，封装和隔离了运行时环境；同时，过程在许多系统中也充当了分离编译的单位。

全局方法通常的工作方法是：

1. 建立过程的一个表示（通常是 CFG，因为这样就可以利用更多的图论性质）
2. 分析该表示
3. 变换底层的代码

如果 CFG 有环，则编译器必须首先分析整个过程，然后才能确定在特定基本程序块的入口上哪些事实是成立的（这让我想到了解析循环时需要构造的 conditionBlock）。因而，大多数全局变换的分析阶段和变换阶段是分离的：分析阶段收集事实并对其进行推断；变换阶段使用这些事实来确定具体变换的安全性和可获利性。

借助于全局视图，这些方法可以发现局部方法和区域性方法都无法发现的优化时机。

过程间方法 / 全程序方法

“过程间”这个术语创造出来是为了解决上一节提出的语义混淆问题，描述从两个过程到一个完整程序范围内的分析，直接理解成“全程序”的概念即可。它的考虑范围大于单个过程。任何涉及多于一个过程的变换，我们都认为是过程间变换。

至少在概念上，过程间分析和优化作用于程序的调用图。有时候，这些技术会分析整个程序；在其他情况下编译器可以只考察源代码的一个子集。过程间优化的两个经典例子是内联替换（inline substitution）和过程间常数传递（interprocedural constant propagation），前者将过程调用原地替换为被调用过程体的一个副本，后者在整个程序中传播并合并有关常数的信息。

上文讲到的都是非常广泛的领域，因此本文对编译器优化的描述自然只是走马观花。我们需要知道的其实就是以下三点：

• 安全性
• 可获利性
• 寻找合适的时机对代码进行优化，比如既安全又有利可图地应用给定变换。

本人的优化工作重点是关注全局优化和过程间优化，但其中也用到了不少局部优化等领域的定义与技术，因此也得一并学习记录。（sigh）具体的算法内容分文记录，这里只留下概述内容，就到这儿吧。

参考：

• Engineer a Compiler, Second Edition

豆瓣评论：“Keith Cooper人非常好，书也写得不错，酷爱穿花衬衫。”