为什么选择SSA？

如果你在过去二十年左右阅读过任何关于编译器的内容，几乎肯定听说过SSA编译器，这是一种流行的架构，出现在许多优化编译器中，包括提前编译器如LLVM、GCC、Go、CUDA（以及各种着色器编译器）、Swift和MSVC，以及即时编译器如HotSpot C2、V8、SpiderMonkey、LuaJIT和Android Runtime。SSA非常流行，以至于大多数编译器项目不再费心为优化使用其他IR。这是因为SSA在编译器优化想要对代码进行的程序分析和转换类型上非常灵活。但为什么？我许多不从事编译器工作的朋友经常说，编译器似乎是不透明的魔法黑盒子，而文献中出现的SSA难以理解地复杂。但事实并非如此！一旦你忘记你认为程序实际上在做什么的一切，SSA实际上非常简单。我们将开发SSA形式的概念，一个简单的SSA IR，证明关于它的事实，并设计一些优化。

注意：我之前写过关于所有现代SSA编译器的鼻祖LLVM的文章。本文是关于SSA的一般介绍，与LLVM无关。然而，阅读那篇文章可能有助于使本文中的一些内容更加具体。

什么是SSA？

SSA是中间表示（IR）的一种属性，主要用于编译器优化针对寄存器机器的命令式代码。寄存器机器是具有固定寄存器集的计算机，这些寄存器可以用作指令的操作数：这包括几乎所有物理处理器，包括CPU、GPU和像DSP这样的奇怪东西。SSA最常见于编译器中端，即前端（处理程序员编写的表面语言，并将其降为中端的IR）和后端（获取优化的IR并将其降为目标平台的汇编）之间的优化组件。然而，SSA IR通常与它们降级的表面语言或它们目标的汇编语言几乎没有相似之处。这是因为这两种表示都不容易让编译器直观地发现优化机会。

命令式代码很难

命令式代码由一系列操作组成，这些操作改变执行机器的状态以产生期望的结果。例如，考虑以下C程序：

1
2
3
4
5
6
7
8

int main(int argc, char** argv) {
  int a = argc;
  int b = a + 1;
  a = b + 2;
  b += 2;
  a -= b;
  return a;
}

这个程序无论输入什么都会返回0，所以我们可以将其优化为：

1
2
3

int main(int argc, char** argv) {
  return 0;
}

但是，你如何编写一个通用算法来检测所有操作相互抵消？你被迫记住程序顺序以执行必要的数据流分析，跟踪程序中a和b的突变。但这不是很通用，遍历所有这些路径使得大型函数的搜索空间非常大。相反，你希望重写程序，使得a和b逐渐被计算最近值的表达式替换，像这样：

1
2
3
4
5
6
7
8

int main(int argc, char** argv) {
  int a = argc;
  int b = a + 1;
  int a2 = b + 2;
  int b2 = b + 2;
  int a3 = a2 - b2;
  return a3;
}

然后我们可以递归地将每个变量的出现替换为其右侧…

1
2
3
4
5
6
7
8

int main(int argc, char** argv) {
  int a = argc;
  int b = argc + 1;
  int a2 = argc + 1 + 2;
  int b2 = argc + 1 + 2;
  int a3 = (argc + 1 + 2) - (argc + 1 + 2);
  return (argc + 1 + 2) - (argc + 1 + 2);
}

然后一起折叠常量…

1
2
3
4
5
6
7
8

int main(int argc, char** argv) {
  int a = argc;
  int b = argc + 1;
  int a2 = argc + 3;
  int b2 = argc + 3;
  int a3 = argc - argc
  return argc - argc
}

最后，我们看到我们返回的是argc - argc，可以将其替换为0。所有其他变量现在未使用，所以我们可以删除它们。这之所以如此有效，是因为我们取了一个带有突变的函数，并将其转换为组合电路，一种没有状态且非常易于分析的数字逻辑电路。电路中节点（对应于原始操作，如加法或乘法）之间的依赖关系从其结构中是显而易见的。例如，考虑以下一位乘法器的电路图：

操作程序的这种图表示有两个巨大好处：

1. 图论的强大工具可用于算法分析程序并发现有用属性，例如相互独立或结果从未使用的操作。
2. 操作除了在有依赖关系时彼此无序；这对于重新排序操作非常有用，编译器非常喜欢这样做。

组合电路是最好的电路，因为它们是有向无环图（DAG），允许非常好的算法。例如，图中的最长路径是NP难的（并且因为P≠NP，具有复杂度O(2^n)）。然而，如果图是DAG，它允许O(n)解！要理解这个好处，考虑另一个程序：

1
2
3
4
5
6
7

int f(int x) {
  int y = x * 2;
  x *= y;
  const int z = y;
  y *= y;
  return x + z;
}

假设我们想像之前一样用其定义替换每个变量。我们不能只是用定义它的表达式替换每个常量变量，因为我们会得到一个不同的程序！

1
2
3
4
5
6
7

int f(int x) {
  int y = x * 2;
  x *= y;
  // const int z = y; // 用其定义替换z。
  y *= y;
  return x + y;
}

现在，我们多了一个y项，因为平方操作不再未使用！我们可以将其放入电路形式，但这需要为每个突变插入新变量。但当涉及复杂控制流时，我们不能这样做！所以我们的所有算法都需要仔细考虑突变和程序顺序，这意味着没有仔细修改，我们不能使用好的图算法。

SSA不变量

SSA代表"静态单赋值"，并在80年代开发，作为增强现有三参数代码（其中每个语句形式为x = y op z）的一种方式，使得每个程序都是电路式的，使用与上述非常相似的过程。SSA不变量规定程序中的每个变量恰好由一个操作赋值。如果程序中的每个操作都被访问一次，它们形成一个组合电路。转换需要尊重这个不变量。

在电路形式中，程序是一个图，其中操作是节点，“寄存器”（这是SSA中通常称为变量的东西）是边（具体来说，操作的每个输出对应一个寄存器）。但是，再次，控制流。我们不能希望将循环电路化，对吧？SSA的关键观察是程序的大部分是电路式的。基本块是程序的最大电路组件。简单来说，它是一个非控制流操作序列，以及一个最终的终止操作，将控制转移到另一个基本块。基本块本身形成一个图，控制流图或CFG。这种SSA公式有时称为SSA-CFG。这个图通常不是DAG；然而，将程序分成基本块方便地分解了程序的"非DAG"部分，允许在基本块内进行更简单的分析。

SSA-CFG有两种等效的形式。传统的一种使用特殊的"phi"操作（通常称为phi节点，这是我在这里将称呼的）来跨基本块链接寄存器。这是LLVM使用的形式。一种更现代的方法，由MLIR使用，是块参数：每个基本块像函数一样指定参数，并且将控制流转移到它的块必须将那些类型的参数传递给它。

我的第一个IR

让我们看一些代码。首先，考虑以下使用循环计算斐波那契数的C函数。

1
2
3
4
5
6
7
8

int fib(int n) {
  int a = 0, b = 1;
  for (; n > 0; --n) {
    int c = a + b;
    a = b, b = c;
  }
  return a;
}

我们如何在SSA-CFG IR中表达这个？让我们开始发明我们的SSA IR！它将看起来有点像LLVM IR，因为这是我习惯看的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// 全局（包括函数）以$开头，寄存器以%开头。
// 每个函数声明一个签名。
func fib(%n: i32) -> (i32) {
    // 第一个块没有标签，不能"跳转到"。
    //
    // 单参数goto直接跳转到具有给定参数的块。
    goto @loop.start(%n, 0, 1)

  // 块标签以`!`开头，可以包含点，并定义参数。寄存器名称作用域到块。
  @loop.start(%n, %a, %b: i32):
    // 整数比较：%n > 0。
    %cont = cmp.gt %n, 0

    // 多参数goto是switch语句。编译器可以假设`%cont`在goto列出的情况中。
    goto %cont {
      0 -> @ret(%a), // Goto可以跳转到函数退出。
      1 -> @loop.body(%n, %a, %b),
    }

  @loop.body(%n, %a, %b: i32):
    // 加法和减法。
    %c    = add %a, %b
    %n.2  = sub %n, 1

    // 注意@loop.start中的赋值：
    // %n = %n.2, %a = %b, %b = %c。
    goto @loop.start(%n.2, %b, %c)
}

每个块以goto结束，它将控制转移到几个可能块之一。在此过程中，它使用给定参数调用该块。可以将基本块视为一个小函数，它尾调用同一函数中的其他基本块。

LLVM IR是…较旧的，所以它使用较旧的phi节点形式。“Phi"来自"phony”，因为它是一个不做任何操作的操作；它只是从前驱链接寄存器。phi操作本质上是前驱的switch-case，每种情况从该前驱选择寄存器（或立即数）。例如，@loop.start有两个前驱，隐式入口块@entry和@loop.body。在phi节点IR中，不是为%n取块参数，而是指定

1

%n = phi { @entry -> 0, @loop.body -> %n.2 }

phi操作的值是跳转到这个块的块的值。这对于手动键入和阅读可能很尴尬，但对于描述算法（只是"添加phi节点"而不是"添加参数和相应参数"）和内存表示更方便，但其他方面完全等效。

如果我们首先重写C使用goto而不是for循环，从C到我们的IR的转换更容易理解：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int fib(int n) {
  int a = 0, b = 1;
 start:
  if (n > 0) goto ret;

  int c = a + b;
  a = b, b = c;
  goto start

ret:
  return a;
}

然而，我们仍然有突变，所以这不是SSA。要进入SSA，我们需要用新寄存器替换每个赋值，并以某种方式插入块参数…

进入SSA形式

上面的IR代码已经部分优化；C程序中的命名变量已从内存提升到寄存器。如果我们将C程序中的每个命名变量表示为指针，我们可以避免立即将程序放入SSA形式。这种技术由降级到LLVM的前端使用，如Clang。

我们将通过为函数添加堆栈声明来增强我们的IR，该声明为函数定义堆栈上的暂存空间使用。每个堆栈槽产生一个我们可以加载和存储的指针。我们的斐波那契函数现在看起来像这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

func &fib(%n: i32) -> (i32) {
    // 声明堆栈槽。
    %np = stack i32
    %ap = stack i32
    %bp = stack i32

    // 将初始值加载到它们中。
    store %np, %n
    store %ap, 0
    store %bp, 1

    // 启动循环。
    goto @loop.start(%np, %ap, %bp)

  @loop.start(%np, %ap, %bp: ptr):
    %n = load %np
    %cont = cmp.gt %n, 0

    goto %cont {
      0 -> @exit(%ap)
      1 -> @loop.body(%n, %a, %b),
    }

  @loop.body(%np, %ap, %bp: ptr):
    %a = load %ap
    %b = load %bp
    %c = add %a, %b
    store %ap, %b
    store %bp, %c

    %n   = load %np
    %n.2 = sub %n, 1
    store %np, %n.2

    goto @loop.start(%np, %ap, %bp)

  @exit(%ap: ptr):
    %a = load %ap
    goto @ret(%ap)
}

任何时候我们引用命名变量，我们从其堆栈槽加载，任何时候我们赋值给它，我们存储到该槽。这从C很容易进入，但代码很糟糕，因为它做了许多不必要的指针操作。我们如何从这里到达我先前展示的仅寄存器函数？

我们希望程序顺序对于重新排序的目的不重要，但正如我们在这里编写的代码，程序顺序确实重要：加载依赖于先前的存储但存储不产生可用于链接两个操作的值。我们可以通过引入表示"地址空间"的操作数来恢复没有程序顺序；加载和存储将地址空间作为参数，存储返回新的地址空间。地址空间或mem表示某个内存区域的状态。当加载和存储未通过mem参数连接时，它们是独立的。例如，Go的SSA IR使用这种增强。然而，它给示例增加了一层复杂性，所以相反，我将对此轻描淡写。

支配关系

现在我们需要证明关于CFG的一些属性，这些属性对于我们的优化传递的定义和正确性很重要。首先，一些定义。

定义 基本块的前驱（或"preds"）是具有到该块的传出边的块集。块可以是自己的前驱。

一些文献称上述为"直接"或立即前驱。例如，在我们的例子中@loop.start的前驱是@entry（函数入口点的特殊名称）和@loop.body。

定义 基本块的后继（不，不是"succs"）是具有从该块传出边的块集。块可以是自己的后继。

@loop.start的后继是@exit和@loop.body。后继在循环的goto中列出。如果块@a是块@b的传递前驱，我们说@a弱支配@b，或者它是@b的弱支配者。例如，@entry、@loop.start和@loop.body都弱支配@exit。然而，这通常不是特别有用的关系。相反，我们想谈论支配者：

定义 如果@b的每个前驱都被@a支配，或者如果@a是@b本身，则块@a是支配者（或支配）@b。等效地，@b的支配者集是其前驱的支配者集的交集，加上@b。

支配关系具有一些很好的顺序属性，这些属性对于定义SSA的核心图算法是必要的。

一些图论

我们只考虑流图的CFG，即所有块可从根块@entry到达，@entry没有前驱。这对于从我们的证明中消除一些病态图是必要的。重要的是，我们总是可以要求从@entry到任何块@b的非循环路径。

陈述支配关系的等效方式是，从@entry到@b的每条路径包含@b的所有支配者。

命题 @a支配@b当且仅当从@entry到@b的每条路径包含@a。

证明 首先，假设每个@entry到@b路径包含@a。如果@b是@a，我们完成。否则我们需要证明@b的每个前驱被@a支配；我们通过对从@entry到@b的非循环路径长度归纳来做到这一点。考虑@b的前驱@p不是@a，并考虑所有从@entry到@p的非循环路径ppp；通过附加@b到它们，我们有一个从@entry到@b的非循环路径p′p’p′，必须包含@a。因为这个的最后和倒数第二个元素都不是@a，它必须在较短的路径ppp内，比p′p’p′短。因此，通过归纳，@a支配@p并因此@b。

反过来，如果@a支配@b，并考虑从@entry到@b的路径ppp。ppp的倒数第二个元素是@b的前驱@p；如果它是@a我们完成。否则，我们可以考虑通过删除末尾的@b制成的路径ppp。@p被@a支配，p′p’p′比ppp短，所以我们可以如上通过归纳进行。

继续那些好的属性。支配允许我们取任意复杂的CFG并从中提取DAG，由按支配排序的块组成。

定理 支配关系是偏序。

证明 支配根据定义是自反和传递的，所以我们只需要显示块不能相互支配。假设不同的@a和@b相互支配。选择从@entry到@a的非循环路径ppp。因为@b支配@a，有这个路径的前缀p′p’p′以@b结束。但因为@a支配@b，p′p’p′的某个前缀p′′p’‘p′′以@a结束。但现在ppp必须包含@a两次，与它是非循环矛盾。

这允许我们在@a支配@b时写@a < @b。我们可以从支配者构建更精细的图结构，这直接从偏序定理得出。

推论 基本块的支配者按支配关系全序。

证明 假设@a1 < @b和@a2 < @b，但都不支配另一个。那么，必须存在从@entry到@b的非循环路径，包含两者，但顺序不同。取那些路径的子路径，跟随@entry … @a1和@a1 … @b，都不包含@a2。连接这些路径产生从@entry到@b不包含@a2的路径，矛盾。

这告诉我们从支配关系得到的DAG实际上是一棵树，以@entry为根。这个树中节点的父节点称为其直接支配者。计算支配者可以迭代完成：块@b的支配者集是其前驱的支配者集的交集，加上@b。这个算法在二次时间运行。更好的算法是Lengauer-Tarjan算法。它相对简单，但解释如何实现有点超出本文范围。我在这里找到了一个很好的处理。重要的是我们可以在不破产的情况下计算支配树，并且给定任何节点，我们可以要求其直接支配者。

使用直接支配者，我们可以引入支配者的最终重要属性。

定义 块@a的支配边界是所有不被@a支配但至少有一个@a支配的前驱的块集。

这些是控制流从不同路径合并的点：一条包含@a，一条不包含。@loop.body的支配边界是@loop.start，其前驱是@entry和@loop.body。有许多方法计算支配边界，但手头有支配树，我们可以这样做：

算法 支配边界。对于每个具有多个前驱的块@b，对于其每个前驱，让@p是该前驱。添加@b到@p及其所有支配者的支配边界，在遇到@b的直接支配者时停止。

证明 我们需要证明算法检查的每个块最终在正确的边界中。首先，我们检查每个检查的块@b被添加到正确的边界。如果@a < @p，其中@p是@b的前驱，并且@d是@b的直接支配者，那么如果@a < @d，@b不在其边界中，因为@a必须支配@b。否则，@b必须在@a的边界中，因为@a支配前驱但它不能支配@b，因为那样它将被@i支配，矛盾。其次，我们检查每个边界是完整的。考虑块@a。如果检查的块@b在其边界中，那么@a必须在某个前驱@p的支配者中，并且它必须被@b的直接支配者支配；否则，@a将支配@b（因此@b将不在其边界中）。因此，@b被添加到@a的支配者。

你可能注意到所有这些算法都是二次的。这对于编译器相关的图算法实际上是非常好的时间复杂度。三次和四次算法并不特别罕见，是的，你的优化编译器的时间复杂度可能是程序大小的三次或四次！

提升内存

好的。让我们构建一个优化。我们想弄清楚是否可以用指向该指针的最远存储替换从指针的加载。这将允许我们通过抵消存储/加载对将值完全从内存中提升。这将使用另一个隐式图数据结构。

定义 数据流图是由每个基本块的内部电路图组成的有向图，沿块参数连接。跟踪使用定义链是向前走这个图以发现可能依赖于它的操作，或向后走以找到它可能依赖的操作。

重要的是记住数据流图，像CFG一样，没有明确定义的"向上"方向。导航它和CFG需要支配树。这里要记住的另一件重要事情是基本块中的每条指令在块执行时总是执行。在这种分析的许多部分，我们需要诉诸"程序顺序"来选择块中的最后加载，但我们总是能够这样做。这是基本块的一个重要属性，使得它们对于构建优化至关重要。

前向数据流

对于给定存储%p, %v，我们想识别所有依赖于它的加载。我们可以跟随%p的使用定义链来找到哪些块包含可能依赖于存储（称为%s）的加载。首先，我们可以消除同一基本块（称为@a）内的加载。在s之后（但在任何其他存储%p, _s之前，按程序顺序）用%v的def替换所有加载%p指令。如果s不是此块中的最后存储，我们完成。否则，跟随%p的使用定义链到使用%p的后继，即，其后继的goto情况中至少有一个参数是%p。递归到那些后继，现在将感兴趣的指针%p替换为设置为%p的后继参数（多个参数可能是%p）。如果后继@b从持有%p的寄存器之一加载，在存储到%p之前替换所有此类加载。我们现在还需要以某种方式将%v发送到@b。这是我们遇到一些困难的地方。如果@b恰好有一个前驱，我们需要添加新的块参数来传递持有%v的寄存器（通过归纳存在）。如果%v已经由另一个参数传递到@b，我们可以使用那个。然而，如果@b有多个前驱，我们需要确保从@a到@b的每条路径发送%v，并且规范化那些将很棘手。更糟糕的是，如果@b在@a的支配边界中，不同的存储可能贡献给该加载！因此，从存储到加载的数据流不是很好的策略。

相反，我们将看从加载向后到存储的数据流（通常，从使用到def的数据流往往更有用），我们可以使用它来增强上述前向数据流分析，以消除围绕支配边界的复杂问题。

依赖分析

让我们分析加载。对于@a中的每个加载%p，我们想确定可能贡献给其值的所有存储。我们可以如下找到那些存储：

我们希望能够确定给定块中的哪个寄存器对应%p的值，然后找到该块中的最后存储。为此，我们将以BFS顺序向后泛洪填充CFG。这意味着我们将递归地跟随前驱（通过使用定义链），在访问它们的前驱之前访问每个前驱，并且从不重新访问基本块（除了我们可能需要在最后回到@a）。

确定@b中%p的"等效"12（我们称为%p.b）可以递归完成：在检查@b时，跟随%p.b的def。如果%p.b是块参数，对于每个前驱@c，设置%p.c为@c的goto中@b(…)情况的相应参数。使用此信息，我们可以收集加载可能依赖的所有存储。如果前驱@b存储到%p.b，我们添加@b中最后这样的存储（按程序顺序）到我们的存储集，并且不递归到@b的前驱（因为这个存储覆盖所有过去的存储）。注意我们可能在此过程中重新访问@a，并收集从它发生的存储到%p。这在循环的情况下是必要的。

结果是存储对（存储%p.s %v.s, @s）的集合stores。在此过程中，我们还收集了所有访问块的集合subgraph，这些是@a的支配者，我们需要通过它们铺设%v.b。这个过程称为内存依赖分析，并且是许多优化的关键组件。

注意 不是所有贡献操作都是存储。有些可能是全局引用（我们忽略），或函数参数或函数调用的结果（这意味着我们可能无法提升此加载）。例如，如果%p被跟踪回函数参数，存在代码路径从我们看不到其存储的指针加载。

它也可能跟踪回可能未存储的堆栈槽。这意味着存在可能加载未初始化内存的代码路径。像LLVM一样，我们可以假设这不是可观察行为，所以我们可以忽略此类依赖。如果所有依赖都是未初始化加载，我们可能不仅可以删除加载，还可以删除依赖于它的操作（反向数据流分析是所谓"时间旅行"UB的起源）。

提升加载

现在我们有完整的依赖信息集，我们可以开始提升加载。当它们的所有依赖都是当前函数中的存储，或者由于表面语言中的UB（如空加载或未初始化加载）我们可以忽略的依赖时，加载可以安全提升。

注意 这个算法中有很多关于通过块参数铺设值的忙乱。许多IR进行简化更改，其中每个块隐式接收其支配者的寄存器作为块参数。我保留忙乱因为它更清楚地发生了什么，但在实践中，除了在支配边界，这种铺设的大部分将在后台发生。

假设我们可以安全提升一些加载。现在我们需要将存储的值铺设到加载。对于subgraph中的每个块@b（所有其他块现在将在subgraph中，除非另有说明）。我们将构建两个映射：一个(@s, @b) -> %v.s.b，这是该块中等于%v.s的寄存器。我们还将构建映射@b -> %v.b，这是%p在该块中必须具有的值。

1. 准备工作队列，最初每个@s在其中。
2. 从队列弹出块@a。对于每个后继@b（在subgraph中）：
   • 如果%v.b尚未定义，添加它作为块参数。让@a传递%v.a到该参数。
   • 如果@b尚未访问，并且不是包含我们删除的加载的块，添加它到队列。
3. 一旦我们完成，如果@a是包含加载的块，我们现在可以在任何存储到%p之前用%v.a替换所有加载到%p。

提示 有些情况可以通过应用"窥孔"优化跳过整个过程。例如，同一基本块内存储后跟加载可以在本地优化掉，为跨块存储/加载对留下重量级分析。

工作示例

这是对我们的斐波那契函数进行依赖分析的结果。每个加载用stores中的块和存储注释。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

func &fib(%n: i32) -> (i32) {
    %np = stack i32
    %ap = stack i32
    %bp = stack i32

    store %np, %n  // S1
    store %ap, 0   // S2
    store %bp, 1   // S3

    goto @loop.start(%np, %ap, %bp)

  @loop.start(%np, %ap, %bp: ptr):
    // @entry: S1
    // @loop.body: S6
    %n = load %np  // L1
    %cont = cmp.gt %n, 0

    goto %cont {
      0 -> @exit(%ap)
      1 -> @loop.body(%np, %ap, %bp),
    }

  @loop.body(%np, %ap, %bp: ptr):
    // @entry: S1
    // @loop.body: S4
    %a = load %ap  // L2
    // @entry: S2
    // @loop.body: S5
    %b = load %bp  // L3
    %c = add %a, %b
    store %ap, %b // S4
    store %bp, %c // S5

    // @entry: S1
    // @loop.body: S6
    %n   = load %np  // L3
    %n.2 = sub %n, 1
    store %np, %n.2  // S6

    goto @loop.start(%np, %ap, %bp)

  @exit(%ap: ptr):
    // @entry: S2
    // @loop.body: S5
    %a = load %ap  // L4
    goto @ret(%ap)
}

让我们看L1。贡献加载在@entry和@loop.body中。所以我们添加新参数%n：在@entry中，我们用%n调用该参数（因为它在@entry中存储到它），而在@loop.body中，我们传递%n.2。L4呢？贡献加载也在@entry和@loop.body中，但其中一个不是@exit的前驱。@loop.start也在这个加载的subgraph中，虽然。所以，从@entry开始，我们添加新参数%a到@loop.body并通过它馈送0（存储值，这次是立即数）。现在看@loop.body，我们看到已经有一个参数用于此加载（%a），所以我们只传递%b作为该参数。现在我们处理@loop.start，@entry将其推入队列。@exit获得新参数%a，它馈送@loop.start自己的%a。我们不重新处理@loop.body，即使它也出现在@loop.start的goto中，因为我们已经访问过它。在对其他两个加载执行此操作后，我们得到这个：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

func &fib(%n: i32) -> (i32) {
    %np = stack i32
    %ap = stack i32
    %bp = stack i32

    store %np, %n  // S1
    store %ap, 0   // S2
    store %bp, 1   // S3

    goto @loop.start(%np, %ap, %bp, %n, 0, 1)

  @loop.start(%np, %ap, %bp: ptr, %n, %a, %b: i32):
    // @entry: S1
    // @loop.body: S6
    // %n = load %np  // L1
    %cont = cmp.gt %n, 0

    goto %cont {
      0 -> @exit(%ap, %a)
      1 -> @loop.body(%np, %ap, %bp, %n, %a, %b),
    }

  @loop.body(%np, %ap, %bp: ptr, %n, %a, %b: i32):
    // @entry: S1
    // @loop.body: S4
    // %a = load %ap  // L2
    // @entry: S2
    // @loop.body: S5
    // %b = load %bp  // L3
    %c = add %a, %b
    store %ap, %b // S4
    store %bp, %c // S5

    // @entry: S1
    // @loop.body: S6
    // %n   = load %np  // L3
    %n.2 = sub %n, 1
    store %np, %n.2  // S6

    goto @loop.start(%np, %ap, %bp, %n.2, %b, %c)

  @exit(%ap: ptr, %a: i32):
    // @entry: S2
    // @loop.body: S5
    // %a = load %ap  // L4
    goto @ret(%a)
}

提升后，如果我们知道堆栈槽的指针不逃逸（即，它的使用都不会进入函数调用13）或写入全局（或逃逸的指针），我们可以删除指向该指针的每个存储。如果我们删除指向堆栈槽的每个存储，我们可以完全删除堆栈槽（此时该堆栈槽应该没有加载留下）。

并发症

这个分析很简单，因为它假设指针通常不别名。别名分析对于更准确的依赖分析是必要的。例如，这对于通过子对象指针提升结构字段的加载以及处理指针算术是必要的。然而，我们的依赖分析对于从不同前驱传递不同指针作为同一块的参数是稳健的。这是特别通过所有关于支配边界的忙乱处理的情况。这种稳健性最终来自SSA的电路性质。

类似地，这个分析需要调整以处理像选择%cond, %a, %b（本质上是三元）这样的东西。指针的选择需要用加载值的选择替换，这意味着我们需要"一次全部"进行提升转换：提升一些可提升加载将使IR处于不一致状态，直到所有它们都被提升。

清理传递

许多优化会把CFG搞得一团糟，所以有简单的传递"清理"转换留下的混乱是有用的。这里有一些简单的例子。

未使用结果消除

如果操作的结果有零使用，并且操作没有副作用，可以删除它。这允许我们然后删除它依赖的现在没有副作用的操作。由于SSA的电路性质，这样做非常简单：收集所有输出有零使用的指令，并删除它们。然后，检查其操作数的def；如果那些操作现在没有使用，删除它们，并递归。这一直冒泡到块参数。删除块参数有点棘手，但我们可以使用工作队列来做。将所有块放入工作队列。

1. 从队列弹出块。
2. 对其操作运行未使用结果消除。
3. 如果它现在有没有使用的参数，移除那些参数。
4. 对于每个前驱，删除到此块的相应参数。然后，将这些前驱放入工作队列（因为它们的某些操作可能失去了最后使用）。
5. 如果还有工作剩下，转到1。

简化CFG

有许多CFG配置是冗余的，可以简化以减少基本块的数量。例如，不可达代码可以帮助删除块。其他优化可能导致函数末尾的goto为空（因为它的所有后继都被优化掉了）。我们将空goto视为不可达（因为它没有情况！），所以我们可以删除块中直到最后非纯操作的每个操作。如果我们删除块中的每条指令，我们可以完全删除该块，并从其前驱的goto中删除它。这是死代码消除或DCE的一种形式，与先前的优化结合以积极删除冗余代码。

有些跳转是冗余的。例如，如果块恰好有一个前驱和一个后继，该块的前驱goto情况可以直接连接到后继。类似地，如果两个块是彼此的唯