fiking

long long ago

0%

全局值标号和冗余计算

发表于 更新于 分类于 ，
本文字数： 20k 阅读时长 ≈ 18 分钟

简介

之前大部分的冗余消除算法都可以分为两类。词法算法处理整个程序，但是它们只能识别词法完全相同表达式的计算的冗余，这里说的表达式词法完全相同指的是，将完全相同的运算符应用于完全相同的操作数。另一方面，值标号算法，可以识别词法不同但肯定会计算相同的值的表达式间的冗余。这是通过给表达式赋一个叫值编号的特殊符号的名称来完成的。如果两个表达式的操作数的值编号完全相同，且应用于表达式的操作符完全相同，则表达式接受了相同的值编号然后一定会有相同的值。值编号的相同性允许比词法相同更广泛的优化，但是值标号过去总是限制在基本块中（没有分支的计算序列），或者扩展基本块中（没有连接的计算序列）。

我们提出一个冗余消除算法，它是全局的（即可以处理整个程序），同时可以识别词法不同的表达式间的冗余。这个算法还利用了二阶效应：基于发现两个计算式计算相同值的转换，可能会为发现其它计算式是等价的创造机会。

这个算法适用于可以表达为可归约[1] [9]控制流图的程序。如第 7 节演示的例子，我们的算法比前一个算法能更广泛的优化可归约的程序。在一个程序没有循环的特殊场景中，我们算法生成的代码，在第 8 节中的从技术意思上解释下是最优的。与前一个执行广泛优化的算法进行对比，这种优化程度是在改善最坏情况时间界限的同时达成的。

图 1 和图 2 说明了我们算法完成的优化。它移除了$A*B$计算间的冗余，识别了 $C * B$ 这个通用使用并将其移除循环，最后，移除 $X + 1$ 计算间的局部冗余。

假设程序已经被转换为使用一个标准的中间形式，其中复杂表达式的子表达式的值使用了临时名字。在一个中间文本表达式中，操作数都是变量和常量。可以说明我们算法的最坏情况时间界限，保守的说，是$O(CNE)$，其中 C 是程序中间文本中的计算式的数量，N 是控制流中节点的数量，E 是图中边的数量。最坏的情况来自 N。这个因子不是代表对图中每个节点做的任意事情；相反，它代表我们算法中，在中间状态下可能会增加的计算的数量。在可以构造的最坏情况下，扩展因子为 N。实际的扩展因子更小。因子 E 也有悲观情况，因为算法的搜索可能会探索图的大部分，但是，实际可能探索的是图的小部分。第 7 节包含了一个比较边界。

例子

本节通过详细解析图 1 来演示我们的算法。这个例子演示了算法使用的几个新技术，但不一定讨论如何处理所有情况。3-6 节给出算法的完整描述，第 7 节关联了之前相关的工作。

我们的算法首先将程序改成一个更简单的表达。在新的程序中每个变量只有一个赋值。这个转化为源程序中每个分离的变量引入了许多新的名字，至少每个赋值语句都有一个名字。在这个特定的例子中，为每个变量 V 引入的新名字是形如 $V_i$，i 是一些整数。通常，这个子任务可以用各种各样的方式完成，如 4.3 节所表述的。单赋值 这个短语已经用于在运行时每个变量只赋值一次的程序中。动态的，一个带有循环的程序会给相同变量赋值许多次，即使只有一个赋值存在程序文本中。我们的转换将程序变成静态单一赋值形式，缩写为 SSA 形式。

为了获得 SSA 形式，在程序的一些连接点我们引入一个新的赋值语句类型，这边的连接节点指的是由两个以上入边的任意节点。，我们考虑由两个入边的场景，为了方便可视化，分别称为“左”和“右”。然后新的赋值的形式是 $V_i \leftarrow \phi(V_j, V_k)$。如果控制沿着左分支到达这个连接节点，则 $V_i$ 被赋值为 $V_j$ 的值；如果控制流沿着右边到达，则 $V_i$ 被赋值为 $V_k$ 的值。这个转换如图 3 所示。这个表达形式允许我们的算法在操作词法名字时，有效地操作值标号。我们的一些变换维护了 SSA 形式，则不需要随后在立即恢复 SSA 形式。

消除冗余会有二阶效应。消除一个计算式可能会提供消除其它的计算式的机会。这激发了排序的概念。排序就像表达式树的高度。大部分为表达式产生操作数的计算式的排名会低于相应表达式的排名。（表达式涉及程序循环。）因此我们可以按排序增加的顺序处理程序，从而可以获得更多的二阶效应。图 3 每个计算式的排名显示在式子的左侧括号中。计算排名的子算法在 4.4 节中。

在一个 SSA 形式的程序中，平凡赋值（即，一个值获得另一个的值）可以被简单的移除，通过将赋值目标的所有使用改到使用赋值右侧的值。在图 4 中，赋值给 $A_3$ 和 $D_3$ 已经被移除了。使用这些变量作为操作数的 $\phi$ 函数和其它表达式一样被改变。

我们算法的第 2 阶段通过循环排名消除冗余计算。对于每个排名，程序图中的节点按照程序分析建立的顺序进行排名，在 4.1 节会解释这个分析。在本例子中，图里唯一的边画有箭头，是循环中的唯一回边。忽略回边，图变成 DAG，可能会有个拓扑序（即，节点可能会按一定的方式排列，每条边的源都在该边的目的之前）。这是顶层循序，我们可能会按顶层顺序的逆序处理节点。在图中，我们自底向上工作。

图 4 中，我们考虑的第一个计算式是赋值给 $X_1$；这是顶层顺序里最后一个节点中排名最低的表达式。直观地，我们移动表达式 Q 到拓扑序中更早的节点（图中向上）。在不改变程序语义的情况下，我们将 Q 移动的越远越好。因为 Q 在有两个入边的节点中，当它向上移动时，我们将其拆分成两个拷贝 $Q_1$ 和 $Q_2$ 。每个拷贝都有机会向上移动，然后一个或者两个最终可能会被认为是冗余的。当两个拷贝被放置在前驱节点后，原始计算式 Q 就会很快成为冗余的。因为我们将会在当前排名的计算式移动后，消除当前排名的全局冗余；在放置拷贝后将 Q 留在原始节点不会有任何的害处。图 5 给出 $Q_1$ 和 $Q_2$ 在连接节点的入边上。正常说，一个计算式不能移动到给它的操作数赋值的计算式之后，$A_4$ 在连接节点被赋值。但是给$A_4$的赋值式来自于一个 $\phi$ 函数。我们可以移动一个计算式到这类特定类型的赋值之后，重命名操作数以反应每个操作数形成之后的值。这个通用技术在 5.1.2 节中描述。

我们可以识别出同一个节点中带有完全相同的操作数和运算符的两个相同计算式。多亏了 SSA 形式，这个恒等式暗示了他们必须计算相同的值，这可以简单的消除，通过将其替换为来自其它输出的平凡赋值。平凡赋值的替换在图 6 中给出。

当新的平凡赋值被引入后，我们会尽快删除它们的。在图 7 中，这些平凡赋值已经被移除了。该图还显示了将 $C_1 * B_1$ 的计算式复制分支节点的结果。这边拷贝是可以发生的，因为分支节点的两个后继计算的值是相同的。拷贝赋值给了新的临时量$Z_3$。

能到达循环头（即，回边的目的节点）的当前等级的任意计算式可能会被拷贝到紧接在循环之前的节点，只要计算式沿着每条穿过循环体回到头部的路径是冗余的。在这个场景中，计算式 $ C_1 * B_1 $ 被拷贝出循环，如图 8 所示。这个通用的子算法在 5.2.2 节中。

现在排名 1 的计算式已经被拷贝到它们最早可以出现的位置上，然后到了可以消除所有冗余的秩为 1 的计算式 Q，因为存在相等的计算式 $E_1, …, E_2$，使得每条从程序开头到 Q 的路径在到达 Q 之前都会执行 $E_i$ 中的一个。冗余计算被替换为一个新的临时量的使用。在每个 $E_i$ 的位置上，一个从$E_i$ 的输出到新临时变量的赋值被添加了。（如果 $n = 1$，冗余计算可能被简单替换为 $E_1$ 输出的使用，没有新的临时变量。）按任意方便的顺序检查当前秩的计算式，每个冗余的计算式在继续前都被消除。这个子算法的细节呈现在 5.4 节中。

通过赋给的变量识别计算式，我们会按$X_1, L_3, L_4, Z_3$ 的顺序找到图 8 中的冗余计算式。按这个顺序找到它们的结果基本如图 9 所示，其中当前有两个给 $Z_5$ 变量的赋值。我们恢复 SSA 形式，且在继续前移除平凡的赋值。

图 9 中删除平凡的赋值在计算 $L_5$ 的 $\phi$ 函数上有二阶效应。删除过程重命名了该函数的两个操作数为 $Z_4$，所以这个 $\phi$ 可以被替换为一个新的平凡的赋值 $L_5 \leftarrow Z_4$（这个之后会被移除）。这是我们算法的子算法为彼此提供了机会的多种方式中的一个例子。

现在到了处理程序下一个秩的时候。关注的计算式是 $Y_1$ 。（操作数$X_1$ 是低一级的秩，已经被移出这个块了。）在图 10 中，我们拆分计算式，把它放到每个边上。因为它匹配右侧分支的 $S_3 + 1$ 计算，它可以被右分支的平凡赋值替换。

到 $Y_3$ 的平凡赋值现在必须被移除（未显示）。然后阶段 3 消除 $\phi$ ，返回传统形式的程序，其不限制任意变量的赋值数量。这个输出如图 2 显示。

算法概述

图 11 给出了算法的伪代码。某些行的括号里的第二个数字表示可以找到相似解释的地方。目前，上一节的直观解释应该足以满足诸如回边，顶层顺序，和循环头节点等概念的。伪代码也提到了循环着陆垫。这个指的是一些节点被加到程序控制流，为放置需要移出循环的代码提供一个方便的位置。

阶段 1：程序预处理

首先我们做一些初步的分析。然后我们在图中一些方便的位置插入一些空节点。这些节点会变成可以移动代码的地方。最后，我们执行特殊的转换和分析，使得程序可以在第二阶段简单的操作。

习惯性在各种关于程序的假设下，描述优化转换。例如，它会假设赋值给一个变量不会影响其它变量的值。也会假设程序语句要么是个简单的赋值
$$
(variable) \leftarrow (expression)
$$
或者是一个布尔变量的简单分支测试。图 1 中一些复杂语句如分支调用或 READ 语句，会导致一些微妙的问题，而这些问题会产生别名分析，副作用等重大的内容。把我们的算法应用到带有实际复杂度的程序中不会比应用前一个算法更困难，所以我们自由地做了些习惯性的假设。在第 2 节中，READ 被认为是一组来自任意不同常量的赋值。这在上下文中是正确的。通常，READ 是一个过程调用，当修改代表读入变量的参数时，会使用和修改文件参数。

分析图

如往常一样，我们假设程序文本已经被分组为基础块，且已经构建了每个基本块作为节点的控制流图，其中的边是每个控制转移。我们假设从表示代表程序入口的节点可以到达所有的节点，每个节点最多有两个出边。最后这些假设不是至关重要的，但是它们在一些地方很方便。

程序控制流图的回边指的是，在以程序入口节点为根节点的深度搜索[18]定义的树中，其目的是其源的祖先的任意边。（在可归约树中，回边的集合不依赖于在深度搜索期间做的任意选择[9]。）

当忽略回边，图会变成 DAG，可能会有个拓扑序（节点会按照每个边的源在其目的之前的顺序排列）。在深度搜索期间，注意到子搜索终止的顺序，来完成排序。Hecht 和 Ullman [10] 表明这个顺序是（有时候叫“结束序”或者“后序”）是拓扑序的逆序。（虽然当前只用于可归约图，但是根据引理 4[10]，实际也可以用于全部的图。）在整篇论文中，顶层顺序将与子搜索终止的顺序相反。

循环头节点是任意回边的目的节点。给定一个循环头节点 h，其是回边$S_1, …, S_k$ 到达的节点，相关的循环体由所有节点组成，因此由一条形如$h\rightarrow^* u \rightarrow^* s_i$ 的路径不遍历回边。一条从循环体中的节点到不在循环体外的节点的边是循环的退出边。退出边的目的节点是退出节点。

在每个循环头节点，我们希望保存一个循环入边和出边的列表。有几个计算每个循环的循环体和循环退出边的方式不用追踪路径。当程序是可归约的话，有如下简单的方式。（在可归约图中，进入循环的边只是头节点的入边，并不是回边。）

首先，我们通过搜索图来确定带有头节点的循环里的节点，从到 h 的回边的源开始。搜索是反向沿着边进行的（从目的到源），忽略回边。搜索的每个分支到达 h （或者前一个已访问的节点）终止。每个已访问的节点都被标记为 h 的循环体。退出边可以通过循环体中的审查节点确定，判断是否有任意不到达循环体中其它节点的出边。

这个算法的最坏时间在我们算法的总体时间里。更有效，但更复杂的计算循环体和循环退出边的方式可以通过已知分析技术的改编获得[19]。通过最里面到最外面的循环遍历（通过逆顶层顺序访问头节点），和将内循环的节点集合合并到下一个外循环（通过有效的并查集算法）。

修改图

这节做的修改可以在线性时间里完成，他们向图中添加了线性有界数量的节点和边。这个修改是很轻微的，前一个分析的结果简单地修改就能满足它们了。我们首先做分析，因为我们需要识别循环。

我们给每个循环一个着陆垫表示从外面进入到循环，不同于循环返回。一个 while 循环（即，一个头节点有一条退出循环的出边的循环）的着陆垫插入如图 12 和 13 所示，这是唯一不是完全顺序的场景。跟随着 [8] 我们重复了老的头节点（形成两个 TEST 节点），让循环看起来像一个由 TEST 守护的 until 循环。然后，循环体的开头变成了头节点，接收一个着陆垫。（让 while 看起来像 until ，允许更广泛的优化。）正式地，每个循环头被赋予一个新的前驱，其会是循环外唯一的前驱。头节点上进入循环的老边变成了新的前驱的入边。因为为每个头节点添加的着陆垫是新的节点，不会有节点会同时是着陆垫和循环头的。

任意直接从有超过一个出边的节点（分支节点）到超过一个入边的节点（连接节点）的边被拆分成一对边，一条从分支节点到新节点，另一条从新节点到连接节点。

拆分边将会允许算法将一个计算式从连接节点移动到它的每个前驱，不会冒着暴露的风险，将计算式暴露给通过前驱节点而不是源节点的控制路径。在图 14 中，一个节点插入到（c）和（b）中间，将会允许（b）的计算被移动，而没有把它插入到（c）到（d）的控制路径。沿着（a）到（b）的计算路径是冗余的。如果它是沿着（c）到（d）控制路径，然后它在（b）是有效的，不管哪个路径进入（b）。这个移动会改善（a）到（b）的控制路径。

为每个着陆垫关联的循环退出加入一条虚拟边到着陆垫。这个虚拟边从着陆垫到退出节点。（一系列退出边在 4.1 节计算，然后关联循环头节点。）虚拟边提供一个机制将代码移过循环，而不用移入循环，但是我们做的大部分工作会沿着初始图中的真实边进行。

转为 SSA 形式

我们在整个程序中重命名变量，将其转为静态单一赋值（SSA）形式：程序文本中的每个变量只被赋值一次。赋值语句的新类型被加到连接节点，来表示变量被赋值了一个变量的值（如果控制沿着一条入边），或者另一个变量的（如果控制沿着另一条边）。

变量 V 的每一处都会被替换为 V 的一个新名字的使用。各个新名字将会表示为$V_i$，其中 i 是整数。在重命名后，程序中的每个点都会由 V 的一个确定的名字到达（在下面解释的意义上）。直观地，到达一个点的名字代表当控制到达这个点时，V具有的任意值。新的名字已经生成或者赋值了，为了满足下面 SSA 的规则，其为只有两条入边的连接节点（“左” 和 “右”）最小化声明：

  1. 程序开头的每个变量 V 被赋予名字$V_0$。这个名字到达程序开头，和其它任意点 p，从开头到 p 的每个路径上都没有给 V 的名字赋值的。

  2. 每个给 V 的赋值都替换为赋值 $V_i$，i 是一些不重复的正数 i。名字 $V_i$ 是那个在赋值后立即到达点 p 的，对于任何其它点 q，任意从 p 到 q 的路径上都是没有给 V 的名字赋值的。

  3. 到达图中一个边的 V 的名字就是到达与这个边的源相关代码末尾的名字。

  4. 在图中 V 相同名字的任意节点到达这个节点的所有入边，名字就是到达节点 的入口点 p 的名字，对于任意的其它节点 q，任何从 p 到 q 的路径，没有给 V 这个名字赋值的。（特别是，任意由一个前驱的节点的入口点被那个能到达前驱尾部的名字到达。）

  5. 图中任意连接节点，即有两个不同 V 名字到达节点的入边的节点，会插入一个新的赋值。新的赋值格式是$V_k \leftarrow \phi(V_i, V_j)$，其中 $V_i$ 和 $V_j$ 是 V 的两个名字，到达节点的左右入边，$V_k$ 是唯一新增的名字。名字 $V_k$ 是到达节点入口 p 的，任意其它点 q，从 p 到 q 的任意路径没有赋值给 V 的名字。

    $V_k \leftarrow \phi(V_i, V_j)$ 的含义是，在节点 u ，如果控制从左入边到达 u，则$V_k \leftarrow V_i$。如果控制从右入边到达，则$V_k \leftarrow V_j$。

  6. 如果 $V_i$ 是到达已转换程序一个点的 V 的新名字，则 $V_i$ 的值总是和原始程序相同点的 V 的值相同。

    重命名的结果如图 15 所示。

SSA 形式前面的特性可以用几种方式实现。下一个子节解释了一个使用规则构建 SSA 形式的简单方法，紧接着的一个小节解释了更复杂的方法，可以导致更广泛的优化。

简单 SSA 形式

以下算法本质上来自于[8]，其中的公式看起来是不同的，因为没有使用显式的 $\phi$ 函数。

以顶层序访问节点，在每个节点上执行下面的步骤：

  1. 如果节点是循环头节点，则为每个变量插入 $ \phi$ 函数。赋值的目的是 V 的新名字。$\phi$ 函数的第一个操作数是 V 的名字到达来自着陆垫的节点。每个回边有另一个操作数，会在之后填充。
  2. 如果节点是连接节点，且不是循环头节点，则应用 SSA 规则 5。
  3. 对于节点中的每个赋值，应用 SSA 的规则 2。
  4. 如果节点是回边的源，则到达节点底部的名字被用于填充回边目的的 $\phi$ 函数的操作数。

这些规则定义了 SSA 形式的重命名，其中不同的变量具有不同的名称。这个简单的 SSA 形式可能会被使用，但是我们整个算法的时间边界为下一子节解释的更复杂的重命名留出了空间。

精简 SSA 形式

简单 SSA 的形式的算法有时候会有比需求更多的赋值，这些会导致在有循环的时候失去一些优化机会。考虑图 16。这个简单的算法将会给 P 和 Q 一个名字的分离集合，程序中的冗余不会被消除。一个更激进的算法会注意到 P 和 Q 总是有相同的值，因此可以共享存储。

7.2 节 将会简单讨论下之前关于识别程序变量之间的等价性的工作。找出所有的等价性不是一个可判定的问题，但是各种可判定的子问题是已知的。有效的，这些算法将一个程序转换为简单的 SSA 形式，然后计算一组变量对，因此给一组中的变量赋值和给另一个赋值是相同的值。如果变量 A 和 B 是一对，且如果赋值给 B 的计算式支配赋值给 A 的计算式（通过程序中的所有路径都能到达它），则将 A 的原始计算替换为语句$A \leftarrow B$ 是安全的。对于识别等价的任意给定方法，一个程序处于精简 SSA 形式，当且仅当，它是 SSA 形式且所有这样的替换都已经完成。则 4.5 节中的优化是适用的。

在图 16 中，任意可以在 P 和 Q 间各个 SSA 名字间识别等价的等价算法将会导致一个精简的 SSA 形式，其中 Q 的每个名字$Q_i$ 被来自 P 的相关 $P_i$ 赋值定义。4.5 节中的优化会高效的合并这些名字的。

给每个计算赋一个秩

在程序上向前处理，不遍历任意的循环回边，我们将会给出现在程序中任意点的任意变量或表达式赋一个秩。当计算循环头节点中的表达式的秩，我们可能需要用到沿着回边到达循环头节点的操作数变量的一个秩的值。这样一个变量的秩可能还没计算出来，但我们可以识别出这个场景，用 0 替代这个秩。在下面的规则中，一个有效的秩可能是秩（当已经计算出来了），也可能是 0（没有计算的）。因为程序是 SSA 的形式，任意变量或者表达式的秩都是明确定义的：

  • 0，如果变量是入口点的名字$V_0$。
  • 表达式的秩赋给一个变量，如果它是在程序中赋值的。
  • 0，如果表达式是常量。
  • 有效操作数的秩的最大值，如果表达式是一个变量或者 $\phi$ 函数。
  • 1 + 有效操作数秩的最大值，如果表达式不是一个常量，变量或者 $\phi$ 函数。

一个计算式的秩式变量 i 的秩赋值的。程序中每个秩的赋值都会执行下阶段 2 的步骤（从秩 0 开始）。这个保证了在任意计算处理之前，为该计算生成操作数的所有计算都已经被处理了。

秩的赋值有个有趣的属性提高了我们算法的性能。不需要保持基础块里的计算顺序。所有这些只需要记住每个表达式的秩。后面可以按秩排序计算来生成代码，最早的在前。相同秩的计算的代码可以按任意顺序生成。这是有用的，因为我们经常添加，删除，或者在一个块中查找计算。所有的这些操作很容易用哈希表实现。程序流图中的每个节点都维护着一个局部计算表（LCT）。这个 LCT 包含了一组发生在节点的计算。有三种主要的访问方式，如下：

  • 我们可以循环所有的计算。
  • 我们可以按给定秩循环所有计算。
  • 给定表达式，我们可以循环所有右侧与表达式相同的计算。

在所有的场景中，寻找 n 计算 i 所需的时间是 $O(n)$。

移除平凡赋值

由平凡的右侧（只有单个变量）的赋值语句对于 SSA 形式的程序由特殊含义。这些语句可以被认为是两个变量（一个是左侧提到的，一个是右侧提到的）表示相同值的断言。要删除的平凡赋值的初始链表包括任意程序中原本有的，以及通过等价识别添加的。这个工作表以方便的方式维持着，删除列表中的下一项可能会导致添加其它项。

给定一个平凡赋值$A\leftarrow B$，我们将一个变量的每个点替换为另一个变量的一个点。为了便于这个替换，我们将会在程序中维护每个变量的使用列表。无论 A 和 B 中哪个有更短的使用列表，则会被另一个替换。每个一个变量被替换，它必须是被一个至少使用两次的变量替换。因此，一个变量可以在删除平凡赋值中幸存的使用次数是由算法的总使用次数限制的。

一个计算式的操作数重命名可能会让右侧操作数变成与同一个结点的另一个计算式的右侧操作数相同。最初的时候同一个节点里可能也会有几个计算式有相同的相同的右侧操作数。我们维护一个工作列表，其以程序的 SSA 形式里的初始局部冗余开头。在平凡赋值移除中，工作列表会获得条目。另一方面，消除一个局部冗余会创建一个平凡赋值。移除平凡赋值和消除局部冗余会相互反馈到各自的工作列表直到两个程序由于空的工作列表静默。当两个工作列表非空，先做哪个列表是无所谓的。

我们算法的最后一步有时候会创建平凡赋值或者局部冗余。最后一步总是会重新激活这一步，然后等待直到这一步清空了它的工作列表。

消除局部冗余的细节如下。如果一个节点的 LCT 有 n 个 $V_i \leftarrow E$ 的计算式，其中 E 是一个普通表达式，i 从 1 到 n ，然后合并那些表达式的过程如下：

  1. 取表达式中的一个，如$ V_n \leftarrow E$。这个是获取的表达式是从那些需要合并的表达式中选取秩最大的一个。
  2. 将每个选取的表达式（i < n） 替换为平凡赋值$V_i \leftarrow V_n$ 的形式。
  3. 将每个平凡表达式放入待移除的工作列表中。

简言之，合并 n 个形如$V_i \leftarrow E$ 的表达式产生一个形如$V_n \leftarrow E$ 和 n - 1 个将会移除的平凡赋值。

$\phi$ 函数的操作数的重命名将会有其它二阶效应，除了创建了局部冗余以外的：

  • $V_i \leftarrow \phi(V_j, V_j)$ 被替换为 $V_i \leftarrow V_j$。
  • $V_i \leftarrow \phi(V_i, V_j)$ 被替换为 $V_i \leftarrow V_j$

在任意场景中，新的赋值都会加入到平凡赋值的工作列表中。

阶段 2：消除冗余

如第 3 节解释的，我们以递增顺序遍历秩。在这个循环中，我们首先以逆顶层顺序遍历节点，移动代码以及消除由这个移动创建的任意局部冗余。然后我们消除当前秩的全局冗余。

每个节点的基本处理过程是，从任意后继移动有效的计算式到当前节点，然后让在当前节点中的计算式对任意前驱有效。代码移动实际上分为两步，将计算式 C 拷贝到 C 将要移动到的节点的 LCT 中，然后将 C 从它移除的节点的 LCT 表中删除。当我们在以逆顶层序遍历节点时移动计算式，我们只是在做拷贝。原始的计算式临时留在原始的 LCT 中，它现在是冗余的。和其它冗余一起，这个原始的计算将会被全局冗余子过程消除。通过在代码移动时延迟删除，可以让记录保持有一些技术上的简化。

移动计算表（MCT） 在程序流图的每条不是回边的边中都有维护一个。MCT 包含了当前所有可以从边的目的节点移动的计算式。一条边的 MCT 的每个记录包含了一个计算式 c 和一个指向边的目的的 LCT 中的相关计算式 B 的指针。一些关于这个表应该记住的要点：

  1. MCT 持有移动候选者，可能移动也可能不动。在 MCT 中，这些计算式可以像 LCT 的计算式一样的方式访问。它们也算作操作数在移除平凡赋值的使用。
  2. MCT 的持续存在，像 LCT 关联的每个节点。它可能会获得或者失去单独计算，但在第 2 阶段期间它永远不会重置。
  3. 以逆顶层序访问节点确保了一个节点所有的出边的 MCT 在要处理该节点时，被填充了具有合适的秩的可移动计算式。

每个节点实际的处理依赖于节点类型。这边有三个场景：

  • 循环头。
  • 准备区。
  • 所有其它的节点（正常节点）。

回顾 4.2 节，没有节点可以同时是循环头和准备区。我们将首先考虑正常节点的场景，然后考虑其它类型作为特殊场景的算法。

正常节点的处理

在访问正常节点时的工作有两部分，对应于下面两个子节。第一部分检查正在访问的节点的所有出边的可移动计算式表，决定哪个计算可以被移入节点中。第二部分确定哪些计算可以用于移动到前驱的。

从后继中移动计算式

如果当前节点只有一个出边，则这个出边的 MCT 中的所有都会被移动到当前节点。如果当前节点有超过一个出边，那边它正好有两个出边。令 $M_1$ 和 $M_2$ 是 MCT。考虑 $M_1$ 中当前秩的每个计算式$C_1$。如果 $C_1$ 的右侧匹配了$M_2$ （不管秩是多少）中的计算式 $C_2$ 的右侧，则两个表达式都会被移到当前的节点里。类似的，$M_2$ 中当前的秩的表达式也会与 $M_1$ 的表达式再检查一遍（不管秩）。MCT 中那些不与其它 MCT 的计算式共享右侧的计算式会留在它们原本所在的位置。

移动计算式到当前节点会创建局部冗余。一个移入的计算式会与已经存在的计算式有相同的右侧。如果当前的节点有两个出边，则每个来自一条边的初入计算式与来自另一条边的传入计算式有相同的右侧，新的局部冗余会放到待移除的工作列表中。例如，在图 17 中，两个$A_1 + B_1$的计算式会被移入节点中。通过 4.5 节中的局部冗余消除算法 $X_2$ 的计算式会改成来自 $X_1$ 的平凡赋值。

检查每个移动了的计算式的 MCT 项，来决定 MCT 项指向的原始的 LCT 计算式 B 需要什么动作（如果有的话）。如果 B 有当前的秩 R，则不需要任何动作。如果 B 有比较低的秩，则晋升到秩 R，从而可以保证它在全局冗余子阶段中会被消除。当已经采取了任意需要的动作后，MCT 项会被删除。

识别可移动计算

当前节点中的 LCT 中的计算式会被识别为可移动的，当它们满足下面所有的条件：

  • 计算式有当前的秩。
  • 计算式本身不是一个 $\phi$ 函数。
  • 表达式没有操作数是作为当前节点里一些其它的非 $\phi$ 函数的输出出现的。

任意识别为移动的计算式被添加到所有的 MCT 的入边中。这个过程可能需要修改表达式 C 使之可以移动。根据下面的技术执行修改，其中 E 是 C 的右侧：

  1. 如果当前的节点只是一个真的入边，则我们为每个真的或者虚拟的入边生成一个新的唯一的变量 U ，然后将新的计算式$U \leftarrow E$ 放入这个入边的 MCT 中。
  2. 如果当前节点是一个连接节点，则所有的入边是真的，基本上就如上处理了，但 E 可能需要在每个新的 MCT 项中修改。如果任意 E 的操作数是当前节点中的 $\phi$ 函数的输出，则需要被替换成每个入边的 $\phi$ 函数的合适的操作数。我们称这个过程是 $\phi$ 重命名。例如，在图 18 中，$A_3$ 被节点中的 $\phi$ 函数定义，然后被用于计算式 $A_3 + C_1$ 中。因此，在MCT 项的左侧使用的表达式中的 $A_3$ 被替换为 $A_1$，在MCT 项的右侧使用的表达式中的 $A_3$ 被替换为 $A_2$。

循环头节点的处理

循环头节点的处理与正常节点类似。完全如 5.1.1 节中描述的计算式会被移到循环头中，但是一个不同的技术会识别出可以移出循环头的计算式。

在正常节点的场景下，仅根据一些局部条件将计算移出节点。在循环头节点，我们希望将计算式移除循环（放入着陆垫）。为了安全地完成这个，我们必须验证循环中已经存在的计算式，这会让结果是有效的，无论控制何时从循环外进入循环头节点。为了做这个，我们使用名为问题传播 的技术来确定循环中是否有些计算式会和我们希望移除的计算式计算出相同的结果一样。

问题传播

问题传播会根据需要搜素尽可能全的图，来决定给定的计算式 Q 是否式冗余的。这个搜素如同 5.1 节中的计算式移动，但是传播一个计算式的问题的规则与移动计算式本身的规则在某些地方是不同的。忽略虚拟边，其它的不同会做简短的解释。一个关于 Q 的问题是 Q 右侧的变量重命名。重命名适当地使用变量名，无论此刻问题在哪里；它就是 5.1.2 节中解释的表达式 $\phi$ 重命名。

在问题传播开始前，给定的表达式 Q 姑且被标记为冗余的。在传播的过程中，它可能被标记为非冗余的。当 Q 已经被标记为非冗余的，它将不会在被标记成冗余的，因此搜索可能会在这个点终止。当传播终止时如果 Q 仍然被标记为冗余的，则 Q 确实时冗余的，可以被消除。

如果 Q 的任意操作数被包含 Q 的节点 n 里的 LCT 中的非 $\phi$ 计算式定义，则搜索终止，Q 被标记为非冗余的。否则，为题被传播到 n 的前驱。问题没有在节点中解决会被传播到前驱（带着合适的 $\phi$ 重命名），除非被下面的某条规则阻止了。

问题传播的停止规则被声明为下面两种场景。在一个循环头节点当前段的处理中，局部搜索受限于相关的循环体，且所有的问题都源于循环头。在随后的冗余消除中，全局搜素会检查尽可能多的必要的控制流图的项，当前秩的所有计算式是问题的源头。终止搜索的规则在这两个场景中有轻微地不同。另一个不同是，全局搜索维护了一张会让 Q 冗余的计算式的列表（初始是空的）。

  1. 在局部搜索中，如果一个问题将会被传播给循环头节点的前驱，则搜索会终止，Q 会被标记为非冗余的。

  2. 在全局搜索中，如果一个问题将被传播给程序入口节点的前驱，则搜索会终止，Q 会被标记为非冗余的。

  3. 在两个搜索中，如果一个问题将沿着超过一个出边传播给一个分支节点，且问题在两个出边上是不同的，则搜素会终止且 Q 会被标记为冗余的。

  4. 在两个搜索中，如果一个问题将沿着超过一个出边传播给分支节点，且问题再两个出边上是相同的，则只有第一个到达的问题会被进一步传播。

  5. 在两个搜索中，如果问题被传播给一个包含计算式 C 的节点中，其中 C 的右侧匹配了问题，则问题在这个方向上不会进一步传播了。（Q 的标记不会被改变。）在这个场景的全局搜索中，如果 C 不是 Q，则指向会标记 Q 冗余的指针列表会增加指向 C 的指针。

  6. 在两个搜索中，如果一个问题被传播到一个节点，且这个节点的 LCT 中有一个非 $\phi$ 计算式定义了问题的一个操作数，则搜索会终止，Q 被标记为非冗余的。

    只有在前一个场景中没有找到匹配项时才会测试这个场景。这个测试和前一个测试都是不分等级的。这些测试通过使用 SSA 形式的程序来简化。如果一个表达式和一个创建这个表达式的一个操作数的赋值在同一个节点中，则使用这个操作数的表达式必须在创建这个操作数的表达式之后。

移除循环的表达式

在前一步中由局部搜索识别出为冗余的循环头节点里的任意表达式，可以移出这个循环。我们分两步进行这个操作。直观地，我们拷贝计算式到着陆垫（这会导致头节点里的旧拷贝变成冗余的），然后在消除各种其它冗余时，消除这个旧的拷贝。在头节点里临时留下旧的拷贝只是为了技术上的便利。令$V_h \leftarrow E$ 是要移除的计算式 C，令$V_p$ 是最新的生成名字。令$E_p$ 是 E 的操作数 $\phi$ 重命名之后的结果（如 5.1.2 节），为了来自着陆垫的入边。为从着陆垫到循环头节点的边，添加$V_p \leftarrow E_p$ 到 MCT 中。这个 MCT 项指回 c。如同往常的，“移动”在这个时候只是拷贝。计算式 C 一直在循环头节点里，但它现在是冗余的，会被全局冗余子过程消除。

着陆垫节点的处理

着陆垫的处理类似于正常节点的处理。完全如同 5.1.1 节那样，我们开始于将计算从它的后继（循环头节点）移入着陆垫。然后我们尝试将计算式直接从循环退出节点直接移动到着陆垫，不用将它们放入循环中中转。计算式可以从循环的退出节点移动到着陆垫，如果满足下面的条件：

  1. 要移除的计算式是在循环的着陆垫的所有虚拟出边的 MCT 中。如果有超过一个虚拟出边，我们反过来考虑每一个。对于每个虚拟出边，我们遍历当前秩的 MCT 项，为了其它的出边，尝试将它们与 MCT 项匹配（不管秩）。这些就像 5.1.1 节中的超过一个真实出边的正常节点的处理过程。
  2. 表达式的每个操作数必须在着陆垫中是有效的。因为这个程序是 SSA 形式的，这个条件等价于循环里没有到这个操作数的赋值。一个测试这个条件的简单方式是，检查包含这个操作数的定义的节点的顶层序的数值。如果它早于或者等于着陆垫的数字，则这个条件满足。

当可以移进着陆垫节点的计算式已经被识别出来，则移动它们的过程完全如同 5.1.1 节。

识别可以移出着陆垫的计算式的过程，完全如同 5.1.2 节。

消除全局冗余

在当前秩，逆顶层序遍历完节点后，执行这个子过程。我们以任意方便的顺序遍历当前秩的计算式。（例如，我们已顶层序访问节点，然后遍历每个节点的 LCT 中的当前秩的计算式。）

对于每个计算式 Q ，我们首先检查 Q 是否已经在秩中晋升了。如果有，则现在它可能会有比其它使用 Q 的结果的一些计算式有更高的秩。我们算法的整体结构大致是，它只当使用的表达式有如 Q 相同的节点时，我们遍历 Q 的结果的局部使用。如果有必要，每个局部使用被晋升，所以有秩 R+1 或者更大。当阶段 2 完成时，计算式的秩和它们操作数的秩之间的相关关系将会被存到每个节点中。

处理计算式 Q 的下一步是检测冗余，通过应用 5.2.1 节中的子算法和全局规则。如果 Q 被发现是冗余的，则它会被下面的技术消除：

  1. 创建一个新的变量 V 来记录 Q 将会计算出来的值（冗余的）。
  2. 对于那些放入标记 Q 冗余的计算式列表的每个计算式 C ，一个$V \leftarrow (C 的输出)$ 形式的赋值会被插入。
  3. Q 的表达式部分被替换成 V 的使用。

如果在上面步骤 2 中有不止一个计算式 C，则程序将不在是 SSA 形式。通过在新的变量 V 上应用 4.3.1 节的规则，可以转换为 SSA 的形式。虽然，用了写人为的方式识别新的等价，但4.3.1 节的简单规则在这里看起来是最好的。当 SSA 形式已经被重建，通过将平凡赋值放入工作列表，使用 4.5 节的算法，可以移除它们。

阶段 3：正常化

为了把程序变成更正常的形式，我们在每个非空的节点中排序代码，消除纯粹形式的 $\phi$ 函数，然后删除空节点。

在 SSA 形式中，我们将所有的计算式无顺序的保存在一个集合里。排序由秩隐含着：秩为 2 的东西依赖于秩 1 的值，因此秩 1 的表达式的值必须先计算。一个变量的秩隐含的顺序信息必须显式地通过将每个节点里的所有低秩的赋值放在高秩赋值之前。这为恢复成同一变量多个赋值的形式扫清了障碍。

形如$A \leftarrow \phi(B, C)$ 的每个计算式被替换为一个进入分支上是 $A \leftarrow B$ ，另一个是$A \leftarrow C$。每个赋值都放在代码结尾。

任意没有代码的节点将最多只有一个后继。如果它有一个后继，则在它的入边改成到后继的入边之后，可以将其删除。

程序现在变得跟它原来的一样，但有更多的变量和更少的冗余。通过图着色寄存器分配算法[5] [6]，许多变量可以合并到一起。变量的生存周期由那些在从变量赋值到变量使用的路径上的节点组成。如果两个变量有不相交的生命周期，则那些变量可以合并到一起。当我们向上移动一个计算式，可以缩短它的操作数的生命周期，但我们可能会加长它的结果的生命周期。关于生命周期的这些改变是有帮助的还是有害的，我们没有严格的信息确定。未来的一个研究题材是找到一个算法，其可以移动计算式，降低生命周期从而帮助寄存器分配。

相关工作

冗余消除

沿着一条控制流路径，如果一个计算式 C 先于等价的计算式 B 出现，则它是冗余的，可以使用 B 计算出来的值替换。如果在每条能搜索到它的路径上（从程序入口开始）它都是冗余的，则它是完全冗余的。如果计算式在搜索到它的部分路径中（从程序入口开始）是冗余的，则它是局部冗余的。许多全冗余的消除长期以来一直是优化编译器的一个主要目标[2] [12]。局部冗余只有比较少的关注。主要的相关工作是 Morel 和 Renvoise [13] （后面缩写为 MR）做的，以及在 PL.8 编译器中实现的 MR 扩展 [4]。

我们的算法的一方面与 MR 是相似的：我们通过移动计算式到移动后的拷贝可以变成全冗余的地方，来消除局部冗余。我们分析和优化的整合与 MR 更传统的组织方式是不同的，它先是分析然后是优化。Morel 和 Renvoise 使用了迭代数据流分析，有一个位向量来放置每个词法不同的表达式。联立方程组计算每个流图节点的几个位向量。每个节点的向量依赖于前驱和后继的向量。最坏时间复杂度需要 $O((E + N) * N * C)$，其中 E 是图中边的数量，B 图中节点的数量，C 是计算式的数量。

PL.8 编译器系统地选择临时名字。如果一个表示式如 $(A * B) + C$ 在程序中出现了两次，则相同的$A*B$ 使用的临时变量出现在两个地方。这个系统命名允许编译器重复应用 MR 来识别第二效应，直到没有东西在改变了。这里需要的迭代次数与秩相同，再加上一次迭代以检测稳定性。

PL.8 编译器算法的整体最坏时间复杂度是$O((E+N) * N * C * R)$，其中 E，N，C 的含义同上（MR 的单个过程），R 是秩的数量。Morel 和 Renvoise 与 PL.8 编译器组联合报告了 MR 的一次应用通常只需要 3 到 5 次迭代，而不是最坏数量 $N+1$ 次迭代。

图 1 中的例子说明了 MR，PL.8编译器，和这里给出的算法三者之间的不同。在连接节点中，现在 $AB$ 的值是沿着一条路径在$CB$ 下计算出来的，所以它对于 MR，PL.8 编译器，或者其它任意词法方法是无效的。如果我们移除原始程序中所有的平凡赋值，将所有的 C 的使用替换为 A 的使用，我们使得程序更易于优化。MR 的一个过程会为 X 消除 $A*B$ 的冗余计算。对于$X+1$ 的冗余计算，它无法做任何事情。这个局部冗余有二阶效应，它将会在 PL.8 的第二阶段消除。

对于可归约流图的程序，我们算法会获得 PL.8 编译器获得的任何东西。我们还识别了许多 PL.8 编译器错过的冗余，因为我们使用了全局值标号。我们算法的最坏时间复杂度是 $O(CNE)$。如果两个边界上所有的参数被替换为名义参数 n，则我们的算法是 $O(n^3)$ 改进了 PL.8 编译器算法的 $O(n^4)$ 。

值编号

起源于 Coke 和 Schwartz[7] 的值标号是基础块的符号执行，为进入该块的所有变量提供不同的符号值。基础块中的通用子表达式消除是直接的。如果一个符号值计算两次，在第二次会消除它。因此，代码中
$$
C \leftarrow A; D \leftarrow AB; E \leftarrow CB;
$$

D 和 E 有符号值
$$
(A@entry) *(B@entry)
$$

第二个计算式可以消除。符号值得哈希允许值标号不需要操作巨大得值就能处理。几个编译器（包括 PL.8 编译器）已经将这个原始的值标号从基础块推广到扩展的基础块。

Reif 和 Lewis [14] 在指编号中引入了全局方法。他们的方法隐含了许多方式中的一个，可以识别两个变量将会有相同的值。有其它的构造 [3] [15] 与 Reif 和 Lewis 的工作的思想相似，在大量的信息，最坏情况复杂度中做各种权衡，因此难以实现。这些算法中的任意一个都可以用于开始我们的算法，通过将程序转为精简的 SSA 形式。

启动冗余消除过程只是任务的一部分，如图 19 所示的代码。沿着一条路径上，T 的计算式与 R 的计算式是冗余的，而沿着另一条路径，T 的计算式与 S 的计算式是冗余的。E 和 A 的不同阻止了任意从纯词法的方式上消除这些冗余。值编号不会受这些不同的影响，但它仍然只能回答它看到的程序提出的问题。三个变量 R，S，T 需要有三个明确的值编号。传统的组织形式，会先分析再优化，不会进行优化。我们的算法会沿着连接节点的入边向后移动 T 的计算式。有一个拷贝会与 R 冗余，而另一个拷贝与 S 冗余。我们的算法会消除这两个冗余。只有在 T 的计算式已经被拆分成两个拷贝之后，才会提出值编号相等的相关问题。

其它问题

p-图的构造[17] 是静态单赋值形式的先导，有些时候会用于优化[11]。用于 SSA 形式的显式 $\phi$ 函数让它更易于一起工作。

Allen [2] 赋了一个局部秩（在基础块里），用它们来组织基础块里的冗余消除，以及循环不变量的外提。我们的全局秩是类似的使用方式，可以组织更广泛的消除和外提。

“着陆垫”的名字是最近有的[8]，但相似的思想已经出现了很长一段时间了[2] [12]。Morel 和 Renvoise 建议使用着陆垫来帮助分析，在必要的时候拆分一些边。我们拆分更多的边，执行一些额外的冗余消除，如 4.2 节的图 14 所示。Morel 和 Renvoise 在[13, p.102]中认识到他们的缺陷，但他们选择了在添加着陆垫之外不允许拆分的方式。

最优准则

这节中，我们将会讨论哪些限制对于消除冗余计算式是最好的。我们将会描述哪些限制我们已经放置在算法中了。我们会表明我们的算法在 DAGs 上是最佳的（在这些限制里）。然后我们会检测带有循环的程序里丢失的场景。

DAG 程序

因为下面说明的一些原因，无法从 DAG 中移除所有的冗余。我们将会枚举三种冗余，似乎消除它们是不合理的。然后，一个最优算法是可以消除所有其它冗余的。

  1. 即使在 DAG 中，仍然无法判定两个表达式是否可以计算相同的值。如果两个值由相同操作符在相同操作数上构造到，我们会说这两个值是透明等价的。因此，在
    $$
    A\leftarrow B
    $$

    $$
    C \leftarrow E +(A*3)
    $$

    $$
    D \leftarrow E+(B*3)
    $$

    我们会识别出 $C=D$，而在
    $$
    A \leftarrow B+3
    $$

    $$
    C\leftarrow A +2
    $$

    $$
    E \leftarrow B +2
    $$

    $$
    D \leftarrow E+3
    $$

    我们无法识别出$C=D$。为了这个小节的目的，在定义精简 SSA 形式中，我们只考虑透明等价这种。

    计算式是等价的但不是透明等价的造成的冗余，我们无法消除。

  2. 消除所有透明产生相同值得计算式，可能会是组合爆炸的，或者是不安全的转换。

    考虑节点 u 中的一个 DAG，由一条沿着值计算的路径。假设这个路径通过节点 v，之后在节点 w 上计算了相同的值。而且，假设在 DAG 中有一条路径会穿过 v 但不会计算这个值。发生这种情况的一个例子是图 20。节点 u 和 w 是$A*B$ 的两个计算式。节点 v 是两个 if 语句之间的任意节点。

    通过将代码的一个拷贝放入 v 来消除冗余，则在 P 条件的每个分支下的 Q 条件的拷贝。这个会允许语句 w 从在 P 的真实分支下的拷贝中移除。这样的转换会导致一个程序大小的指数爆炸。

    第二种消除冗余的方式是将计算式 $A * B$ 的一个拷贝放在 P 的测试之前。则这允许我们将语句（u）和（v）改为平凡赋值。这样的转换是不安全的，因为如果 P 和 Q 两个都是错误的，沿着路径执行它引入了$A * B$ 的计算。这个路径在之前没有这样的计算。

    更通常的，我们将会消除如下形式的冗余：（A）从执行的计算式所在的节点 u 开始，到执行的等价计算式所在的节点 w 有一条路径；（B）有另一条从根穿过 v 到 w 的路径，沿着这条路径在 w 的计算式式这个值的第一个计算式；（C）有一条从 v 到 DAG 退出节点的路径，不包含等价于 w 中的冗余的计算式。

  3. 有一个执行两个不等价计算式的程序，然后（依赖于后面的控制流）一个或者另一个会使得后面的计算变得冗余。冗余的计算不会被消除，除非额外的平凡赋值被插入程序中，来保证正确的值可以被存储到值将会获取的位置上。这个程序需要任意数量这样的赋值，存取的开销会超过计算式的开销。

    例如，考虑图 21。如果 P 是正确的，则在程序段末尾的计算式 $AB$ ，相对于计算式 $CB$ 是冗余的。如果 P 是错误的，则更早的 $A*B$ 计算式是冗余的。

    正式地说，如果有两条路径穿过节点 u，v，w，一条路径上 u 中的计算式对于 w 中的计算式 C 是冗余的；另一条路径上，v 中的计算式与 C 是冗余的；没有一条路径上，u 和 v 的计算式的值是透明等价的，则我们将无法消除这个冗余。

我们已经枚举了三种冗余，尝试消除它们似乎是不合理的，我们的算法不会尝试消除它们。在 DAG 上，成功了。

定理：在我们的算法终止在 DAG 之后，任意剩余的冗余是上面三种之一，则算法不会尝试消除它。

大致证明：

我们考虑阶段 2 末尾的程序，它仍然是精简 SSA 形式且没有平凡赋值。通过秩和路径长度的归纳，沿着路径表达式是透明等价的，当且仅当，它们是词法相同的，除了沿着路径连接节点的重命名。更准确地是，假设一个控制流沿着一个路径从节点 u 到节点 v（从 u 到自己是一个空路径），表达式 E 和 F 出现在节点 u 和 v 中。如果沿着路径将 F 移动回 u 的结果与 E 是词法相同的，我们说这些表达式是词法相同的，除了 $\phi$ 函数重命名。沿着路径连接节点的每条入边，将表达式移动回去可能回插入 $\phi$ 函数，如 5.1.2 节。

定义失败为还有剩余的冗余其没有被之前枚举的覆盖，这些应该被移除。为了证明没有失败，我们会假设这里有失败然后得到矛盾的结果。多亏了 4.5 节的局部冗余消除，任意一个失败涉及节点 u 中的计算式 B 和节点 w 中的计算式 C，这些节点是不同的，有一条从 u 到 w 的路径。（特定的路劲被认为是失败的一部分。）B 和 C 计算了相同的表达式 E，是沿着路径部分来自连接节点的重命名，E 不是一个 $\phi$ 函数。

我们可以将两个数字与任意失败联系起来：E 的秩，沿着失败发生从 u 到 w 的路径长度。如果有任意失败发生，则我们可以从中选择一个最大路径长度和一个最小秩。我们会从中产生一个矛盾，证明这个已选择的失败必须是类型 2 或者 3。

因为 E 的操作数对于 u 中的 B 是有效的（部分来自 $\phi$ 函数的应用），没有一个是在 w 中计算的。5.1.2 节中在 MCT 中放置了一个 C 的项，这个MCT 是从 u 到 w 的失败路径上的最后一条边。令 v 是这条边的源。在 5.1.1 节中不会移动 MCT 项，所以 v 有另一条出边 f，因此没有等价于 C 的计算式放置在 f 的 MCT 中。通过最大化已选择的失败里的路径长度，任意从 v 开始沿着 f 的路径没有等价于 C 的计算式。

节点 u，v，w 已经证明满足我们宣布无法消除的第二类冗余定义的条件（A）和（C）。因为已选择的失败是一个失败，条件（B）必须是错误的。沿着任意路径从根穿过 v 到 w，一个等价于 C 但在 C 之前的计算式。多亏了边拆分，分支节点 v 是 w 的唯一前驱。因此，C 是全冗余的。但是，全局问题传播，不会像 5.4 节中的冗余一样消除 C。这暗示着传播停止在问题传播的细节的第三个规则里（5.2.1 节）。因此冗余是第三类，与之前是矛盾的。

循环程序

在这个子节中，我们考虑当应用的程序带有循环时，两个被全局算法错失的场景。还有其它的场景，但已知场景中这两个看起来是最重要的。

  1. 如果被移到循环头节点的代码可能仍然是在每个从头节点到循环退出节点的路径上的代码。局部问题传播没有考虑将这样的代码放置到着陆垫节点。这个失败的一些简单场景容易被辨认出来，我们的算法简单的扩展就能处理它们。但是，通用场景是困难的。一个循环通过许多路径会有许多退出可达。有几个等价的计算式集合起来像单个计算式，这些出现在所有的相关路径上。理想地，这个算法将被扩展成能识别出这些出现的集合计算式。

  2. 这个算法不会考虑沿着回边可能的计算式移动。在图 22 中的程序段通过将循环头节点视为普通的连接节点可以得到提升。如果我们沿着循环的回边移动$A+B$ 计算式的第一个拷贝，同时移动另一个拷贝到着陆垫，则我们可以在循环里移动拷贝，就好像它最初放置在条件语句之后一样。这个拷贝的副本会出现在 then 和 else 分支，且 then 分支里的副本会与 Y 的赋值合并。这个会降低 $A+B$ 计算的数量到每次迭代恰好只有一个（部分来自着陆垫的初始计算）。

    虽然在这个例子中很有吸引力，沿着回边移动会导致一些组织上的问题。在一个计算式到达循环头节点时，循环里的当前秩的计算式移动已经完成。沿着回边的移动没有任何帮助，除非用于留在循环里的拷贝的秩被强制大于当前的秩。这会导致无限循环：一个秩为 R 的表达式到达循环头节点，沿着回边移动有秩$R+\delta $，然后再次到达循环头节点但是是以秩为$R+\delta $ 的方式到达的，沿着回边移动以秩$R+\delta + \delta $ 进行，如此一直循环。当循环是嵌套的，难以确定要怎样才能保有足够的空间来避免无限递归的同时，不失去优化机会。一个可能的方式是尝试迭代我们整个算法，基于理解，当一个计算式沿着回边移动不会再进一步了时，直到下一次迭代。但这也可能会导致无限递归，如图 23 所示。

结论

我们已经证明了如何以比较小的代价在可归约程序上获得通常比较昂贵的优化，多亏了三个创新的协助：全局表达式秩，单一静态赋值（SSA）中间表达形式，和$ \phi$ 重命名表达式。

全局秩可以让我们迅速利用二阶效应，而不需要重复分析。当另一个算法重复调用来反复利用二阶效应时，秩也帮助表征需要的迭代次数。

程序的 SSA 形式使得我们可以简单的移除平凡赋值。这也允许我们识别和利用表达式间的等价，这些表达式在通用形式上词法是不同的。如果一个程序是 SSA 形式，则词法相同的表达式总是有相同的值，不管它们在哪里出现。因此，如果一个程序是 SSA 形式，带有相同值编号的表达式将会是词法相同的，除了沿着路径的 $\phi$ 重名。

在边拆分的线性边界数量的帮助下，$\phi$ 重命名使得我们在从一个连接节点移动计算式到它的前驱时能够维持 SSA 形式。在通过中间过程期间维持 SSA 形式是重要的，因为它允许代码与每个节点关联，表示为一张表，可以高效的访问和更新。

我们还指定了一个合理的最优准则。在没有循环的程序这样一个特定场景里，我们算法生成的代码被证明是最优的。这个最优是在第 8 节解释的技术意义上的。

致谢

我们感谢 Fran Allen，Trina Avery，和 Ron Cytron，因为他们为这个文章的草稿提出了宝贵的意见。

引用

略。