Compiler Pass 0 优化简析

核心语言

下面我们来具体分析算法本身。首先定义如下核心语言：

其中 const 可以表示布尔值、整数、void（原文如此，更严谨地来说为 unit）。 ref 用于引用一个变量。 primref 用于引用内置的基本原语。 letrec 则是 Scheme 语言里的常见构造，定义了一组允许相互递归的绑定。

无限制的优化算法

对于优化算法 \(I\), 它接受一个输入表达式 \(e\)，一个用于确定执行变换目的的语境 (Context) \(\gamma\)， 一个负责映射变量名的环境 (Environment) \(\rho\)， 以及延续 \(k\) 和存储 \(\sigma\)。延续 \(k\) 的存在是因为描述算法时使用了 Continuation Passing Style (CPS) ，实践中可以用其他方式代替。 存储 \(\sigma\) 里面用于存放一些算法需要的信息。算法函数的定义域（类型签名）如下所示：

其中值得注意的是语境 \(\gamma\)。它被分为以下四种：

• Test 表示我们希望得到表达式作为布尔值的结果
• Effect 表示我们只关心表达式中的副作用
• Value 表示我们希望得到表达式的值
• App 表示我们希望在已知调用点的 Context 和操作数信息的情况下，处理被调用者，以便评估内联的效果

需要注意的是，Effect 以外的 3 种语境也都隐含了 Effect 语境（毕竟不能无故丢掉副作用）。

现在我们来看算法 \(I\) 具体是如何工作的吧。

常量

首先是最简单的情况，如何处理常量。 根据语境 \(\gamma\) 的不同，我们返回不同的结果： 在只关心表达式副作用时，我们可以直接省去常量对象的构造； 如果关心表达式作为布尔值的结果， 根据 Scheme 语言的语意，只要不是 false 的常量都为 true, 因此我们也不用构造常量本身，直接返回 true 作为结果即可。

顺序表达式

对于 (seq e1 e2) 结构来说，其只会返回 e2 的值，在处理 e1 时只需要考虑副作用。 在分别处理完 e1 和 e2 后我们仍然将其放入 seq 结构。 需要注意的是，为了暴露优化机会、消除死代码，我们使用 "seq" 函数优化了结果。它的工作原理如下所示

seq 辅助函数

如果 e1 只是常量 void，那就仅保留 e2; 如果 e2 同样是一个 seq 结果，则改变其结合性（右结合 \(\rightarrow\) 左结合），来将处理过的表达式“推到一边”。

条件表达式

条件表达式的优化侧重点是看条件能否在 Test 语境下被求值成常量。 如果可以的话，就只需要处理对应的分支，抛弃另一方向的死代码，然后保留条件的副作用，将两者放入 seq 结构，依次求值。 如果不能在优化时获得条件的具体真假，那么仍然可以在 e2 和 e3 均为相同常量的情况下， 将两个分支合二为一。 否则，我们就只能递归地处理三个子表达式，然后组合三者为一个新的条件表达式。 这里有一个细微的点就是， 如果在处理整个条件表达式时，语境 \(\gamma\) 具有 App\((op, \gamma_1, l_\gamma)\) 这样的结构， 说明我们在分析一个被调用的函数，因此我们会取出其中的调用处语境 \(\gamma_1\) 作为子表达式的语境，以期提供更多信息用于子表达式的优化。

result 函数

在处理条件表达式的时候我们使用了 result 函数。result 主要获得 seq 表达式的求值结果。

赋值表达式

赋值时需要查看变量 \(x\) 是否被使用过，这是通过在环境 \(\rho\) 中查找是否存在 ref 标志而实现的。 如果没有被实际使用，就只需要保留表达式 \(e\) 中的副作用部分。 否则就得在 Value 语境下对表达式求值，并为变量增加 assign 标志。 由于赋值表达式本身也需要返回一个值，根据语境可判断这个返回值是否需要被作为条件，选择返回 true 或者 void。

调用表达式

调用表达式的优化比较特别，体现了算法 Polyvariant 的特点，首先是我们不会预先分析操作数，而是将其封装入 Opnd 结构中。 其次我们会生成一个新的语境 App \((op, \gamma, l_{y_1})\)，在保留当前语境的同时，提供额外的操作数信息。 同时，我们会创建新的语境状态（存储的一部分），标注操作数为 unvisited 状态。

处理完被调用者后的操作颇有意思，首先我们判断是否存在 inlined 标志， 是的话，则直接用结果 \(e_1 '\) 替换掉这个 call 节点。 否则，我们需要 "visit" 操作数，并在得到结果后组合两者成为新的 call 表达式。

visit 辅助函数

"visit" 操作有何用途？ 由公式所示，它会首先判断该表达式是否已经被优化算法处理过，如果是则返回缓存的结果，否则则使用 \(I\) 对表达式进行处理， 并通过将结果放入存储 \(\sigma\) 来缓存。

原语表达式

处理原语表达式也比较轻松，和对常量表达式的处理相似，在用于条件测试和副作用时，各自返回常量 true 和 void 即可。 如果这个原语表达式出现在被调用者位置（也就是说语境为 App）， 那就使用 "fold" 函数尝试对这个表达式进行常量折叠优化。同样地，我们将 "fold" 的具体细节留到之后分析。

Lambda 表达式

Lambda 表达式在被用作布尔值或者副作用时，也如原语表达式一样，返回常量。 在被用作 Value 时，这个优化算法选择 \(\alpha\)-renaming 后对函数体进行优化，之后组合一个新的优化后的 Lambda 表示。 类似的，Lambda 表达式出现在被调用者的位置时，该优化算法也会用到 "fold" 函数。

变量引用表达式

访问变量也不会产生副作用。如果这个变量不是由 letrec 引入的或是函数的形式参数，就向存储中添加一个表示 （使用环境 \(rho\) 重命名后的）变量已被引用的标志。 否则，我们需要像处理调用表达式时一样，去 "visit" 对应的操作数 \(op\)，获取优化后的操作数表达式的结果， 并对结果使用 "copy" 进行复制传播 (Copy propagation)。

fold 常量折叠

fold 可以分为两种情况：

• 当试图折叠一个原语表达式时，我们先通过 "visit" 查看操作数能否被折叠为常量，如果可以的话，我们直接计算出结果作为折叠的结果， 并设置 inlined 标志（回想一下，我们会根据这个标志决定调用表达式的结果）。 否则我们保持表达式的原样。
• 而在折叠 Lambda 表达式时，在完成 \(\alpha\)-renaming 这一步后，我们需要判断形式参数是否被使用过。 若答案为否，且参数也没有被赋值，那只需要依次考虑参数和函数体的副作用，将其变为顺序结构； 若形式参数参数未被使用但被赋值过，则操作数仍在只保留副作用的语境下进行优化，并用对 lambda 表达式的调用来构建一个 let 绑定。 否则我们必须正常地用 Value 语境处理参数，并保留调用表达式的结构。 无论何种情况，我们都会设置 inlined 标志，以确保上层函数能用新构建的表达式替换掉旧的。

copy 复制传播

copy 的参数比较多，容易混淆。第一个参数为变量信息（这里为重命名后的），包含有变量名、与之绑定的操作数（参数）信息、标志和状态存储。 第二个参数是一个表达式，代表了操作数求值的结果。

• 当可以确定求值结果为常量时，那就进一步在上层语境下优化该常量，用结果替换掉未优化的表达式。
• 如果求值结果是另一个变量且该变量没有被赋值过（防止因为变量可变造成与期望值不同），那直接用该变量替换未优化的表达式。
• 如果求值结果可调用（原语或者 lambda 表达式）且语境为 App ，那就对结果用 fold 进行常量折叠。
• 之后两种情况比较类似，都是根据特定语境返回原语本身或者常量。
• 如果和上述所有情况都不符，那么保持对原变量的引用，并更新相关的 ref 标志表示这一变量已被使用。

受限制的优化算法

为了避免优化算法无法终止或者造成代码体积爆炸，论文作者使用了三种机制：

• 尝试计数器：对于每次内联操作数的尝试，都维护一个尝试计数器来记录调用 \(I\) 的次数。 如果超出了尝试上限，则终止该次尝试。在内联过程中，如果内嵌的子表达式同样发生了内联，则计数器将被共享。 这确保了对于程序每个可能的内联点，都会有一个固定上限。最终，整个程序的总尝试次数是和程序大小线性相关的。
• 代码体积计数器：通过该计数器来追踪算法额外产生的代码大小，如果超出限制，则放弃内联尝试。
• 循环检测：在 Opnd 结构中，我们可以附加额外的标志用于检测循环。 复制传播时会设置 outer-pending 标志来避免对 ((lambda (x) (x x)) (lambda (x) (x x))) 进行无限展开； "visit" 时则会设置 inner-pending 标志来检测操作数内的递归引用，如 (letrec ((f (lambda () (f)))) (f))。