了解静态单一分配表单

应大众要求，我正在做另一篇LLVM帖子。这一次，它是单一静态赋值(或SSA)形式，这是优化编译器的中间表示中的一个常见特性。

就像上一个一样，SSA是编译器和IR设计的主题，我大部分都能理解，但可以从一些自我指导的学习中受益。我们到了。

在最高级别，编译器的工作是单一的：将一些源语言输入转换成一些机器语言输出。在内部，这可以分解为一系列清晰描述的任务：

验证AST(例如，确保标识符的所有使用都与源语言的作用域和定义规则一致)3。

将AST翻译成机器码，及其所有复杂性(指令选择、寄存器分配、帧生成&；c)。

在单遍编译器中，(4)是整体式的：机器代码是在编译器遍历AST时生成的，不会重新访问以前生成的代码。这是非常快的(就编译器性能而言)，但有一些重要的限制：

优化潜力：因为机器代码是在一次遍历中生成的，所以不能对其进行修改以进行优化。单遍编译器倾向于生成极其缓慢和保守的机器代码。

举个例子：system V ABI(由Linux和MacOS使用)在当前堆栈指针(%rsp)之外定义了一个特殊的128字节区域，其堆栈帧可以放入其中的叶函数可以使用该区域。这又节省了函数序言和结束语中的一些堆栈管理指令。

单遍编译器将很难利用ABI提供的这种优化：它需要在每个自动变量被访问时为它们发出一个堆栈槽，并且如果所有变量都位于红色区域内，则不能重新访问其函数序言以进行擦除。

语言限制：单遍编译器很难做出公共语言设计决策，比如允许在声明或定义之前使用标识符。例如，下面的代码是有效的C++：

Class rect{public：int area(){return width()*Height()；}int width(){return 5；}int high(){return 5；}}；

C和C++通常要求预先声明和/或定义标识符，但成员函数体可以引用整个类范围。这将使单遍编译器感到沮丧，因为它希望RECT：：WIDTH和RECT：：HEIGHT已经存在于某些用于调用生成的符号查找表中。

对IR执行分析(或通道)，并根据某些优化配置文件(代码大小、性能&；c)对其进行优化。

该IR或者被翻译成机器代码，或者被降低到另一个IR，用于进一步的目标专门化或优化4。

因此，我们需要一个易于正确转换且易于优化的IR。让我们深入了解一下为什么具有静态单一赋值属性的IRS会填补这个空白。

在其核心，任何程序源程序的SSA形式只引入了一个新的约束：所有变量恰好赋值(即，存储到)一次。

举个例子：关于FLAGS变量，以下函数(实际上不是非常有用的)不是有效的SSA形式：

INT HELPUP_OPEN(char*fname){INT FLAGS=O_RDWR；IF(！Access(fname，F_OK)){FLAGS|=O_CREAT；}int fd=open(fname，flag，0644)；返回fd；}。

为什么？因为标志被存储为两次：一次用于初始化，以及(可能)在条件主体内再次存储。

作为程序员，我们可以重写HELPUP_OPEN，使每个自动变量只存储一次：

Int help_open(char*fname){if(！Access(fname，F_OK)){INT标志=O_RDWR|O_CREAT；返回OPEN(fNAME，FLAGS，0644)；}ELSE{INT FLAGS=O_RDWR；RETURN OPEN(fname，FLAGS，0644)；}}。

但这是笨拙和重复的：我们基本上需要复制任何变量后面的每一条使用链，这些变量被存储到不止一次。这不利于可读性、可维护性或代码大小。

因此，我们做我们一贯做的事情：让编译器为我们做繁重的工作。幸运的是，在两个简单规则的条件下，存在从每个有效程序到等价SSA形式的转换。

规则1：每当我们看到存储到已经存储的变量的存储时，我们就用该变量的全新“版本”替换它。

使用规则#1和上面的示例，我们可以使用_N后缀重写标志以指示版本：

INT HELPUP_OPEN(char*fname){INT FLAGS_0=O_RDWR；//在此声明以避免处理C作用域。INT FLAGS_1；如果(！Access(fname，F_OK)){FLAGS_1=FLAGS_0|O_CREAT；}int FD=OPEN(fname，FLAGS_1,0644)；返回FD；}。

打开(...，FLAGS_1，...)。是不正确的：它无条件地赋值O_CREATT，这不在原始函数语义中。

打开(...，FLAGS_0，...)。也是不正确的：它从不赋值O_CREAT，出于同样的原因，这也是错误的。

规则2：每当我们需要根据控制流选择一个变量时，我们都会使用φ函数(φ)根据我们的选择引入一个新的变量。

INT HELPUP_OPEN(char*fname){INT FLAGS_0=O_RDWR；//在此声明以避免处理C作用域。INT FLAGS_1；如果(！Access(FNAME，F_OK)){FLAGS_1=FLAGS_0|O_CREAT；}INT FLAGS_2=φ(FLAGS_0，FLAGS_1)；INT FD=OPEN(FNAME，FLAGS_2,0644)；返回FD；}。

我们的困境解决了：OPEN始终接受FLAGS_2，其中FLAGS_2是将φ应用于FLAGS_0和FLAGS_1而生成的新的ssa变量。

还要注意，φ是一个符号函数：在内部使用SSAForm的编译器不会在生成的代码5中调用真正的φ函数。φ的存在只是为了协调规则#1和控制流的存在。

因此，用C示例谈论SSA表单有点愚蠢(因为我们首先要翻译的是C和其他高级语言)。让我们深入了解LLVM的IR实际上是如何表示它们的。

首先，让我们看看当我们在没有优化的情况下通过clang运行我们的第一个help_open时会发生什么：

定义DSO_LOCAL I32@HELPUP_OPEN(i8*%fname)#0{entry：%fname.addr=alloca i8*，ALIGN 8%FLAGS=ALLOCAI32，ALIGN 4%FD=ALLOCAI32，ALIGN 4存储I8*%fname，I8**%fname.addr，ALIGN 8存储I32 2，I32*%标志，ALIGN 4%0=加载i8*，i8**%fname.addr，ALIGN 8%CALL=Call I32@Access(i8*%0，I32 0)#4%tobool=ICMP ne I32%呼叫，0 br i1%tobool，标签%if.end，标签%if.Then：；Preds=%Entry%1=加载I32、I32*%标志，对齐4%或=或I32%1，64存储I32%或I32*%标志，对齐4 br标签%if.end if.end：；Preds=%if.Then，%Entry%2=加载I8*，I8**%fname.addr，Align 8%3=加载I32，I32*%标志，Align 4%Call1=Call I32(I8*，I32，...)@OPEN(I8*%2，I32%3，I32 420)存储I32%Call1，I32*%FD，Align 4%4=加载I32，I32*%FD，Align 4 ret I32%4}。

因此，我们使用来自…的%3调用OPEN。来自名为%FLAGS的I32*的加载？φ在哪里？

这是我在阅读LLVM的IR时经常犯的错误：只有值，而不是内存，才是SSA形式。因为我们在编译时禁用了优化，所以%FLAGS只是一个堆栈槽，我们可以在其中存储任意多次，这正是LLVM在上面选择做的。

因此，当传递直接使用堆栈插槽的IR时，LLVM基于SSA的优化没有那么有用。我们希望尽可能最大限度地使用SSA变量，以使未来的优化过程尽可能有效。

此文件(优化过程)将内存引用提升为寄存器引用。它推广只有装入和存储作为用途的分配指令。通过使用主控器边界放置φ节点，然后按深度优先顺序遍历函数以适当地重写加载和存储来转换分配。这只是构建“修剪的”SSA表单的标准SSA构建算法。

定义DSO_LOCAL I32@HELPUP_OPEN(I8*nocatch readonly%fname)local_unname_addr#0{entry：%call=call I32@access(i8*%fname，I32 0)#4%tobool.not=ICMP eq I32%call，0%spec.select=select i1%tobool.not，I32 66，I32 2%Call1=call I32(i8*，I32，...)@open(i8*%fname，I32%spec.select，I32 420)#4，！dbg！22 ret I32%Call1，！dbg！23}

又被挫败了！多亏了mem2reg，我们的堆栈槽消失了，但是LLVM实际上优化得太多了：它认为我们的标志值完全依赖于我们的访问调用的返回值，并完全删除了条件。

“SELECT”指令用于根据条件选择一个值，而不需要IR级分支。

所以我们需要一个更好的例子。让我们做一些LLVM不能简单地优化为SELECT(或SELECT序列)的事情，比如使用我们只提供了声明的函数添加Else IF：

Size_t文件大小(char*)；int help_open(char*fname){int flag=O_RDWR；if(！Access(fname，F_OK)){FLAGS|=O_CREAT；}ELSE IF(fileSize(Fname)>；0){FLAGS|=O_TRUNC；}int fd=open(fname，flag，0644)；返回fd；}。

定义DSO_LOCAL I32@HELPUP_OPEN(I8*%fname)LOCAL_UNNAME_ADDR#0{entry：%call=call I32@access(i8*%fname，I32 0)#5%tobool.not=ICMP eq I32%call，0 br i1%tobool.not，Label%if.end4，Label%if.Else if.Else：；Preds=%entry%Call1=call i64@filesize(i8*%fname)#5%cmp.not=ICMP eq i64%Call1，0%spec.select=select i1%cmp.not，i32 2，i32 514 br标签%if.end4 if.end4：；Preds=%if.Else，%Entry%Flags.0=Phi I32[66，%Entry]，[%spec.select，%if.Else]%call5=call I32(i8*，I32，...)@open(i8*%fname，I32%flag s.0，I32 420)#5 ret I32%call5}。

Llvm的phi比我之前构造的φ(FLAGS_0，FLAGS_1)稍微复杂一些，但并不复杂：它接受一个配对列表(在本例中是两个)，每个配对包含一个可能的值以及该值的原始基本块(通过构造，它始终是φ节点上下文中的前导块)。

输入值的类型由第一个类型字段指定。在此之后，‘phi’指令将一组对作为参数，当前块的每个前置基本块都有一个对。只有第一类类型的值可以用作PHI节点的值参数。只有标签可以用作标签参数。

在基本块的开始和PHI指令之间不能有非PHI指令：即PHI指令必须是基本块中的第一个。

还可以看到，LLVM仍然很聪明：我们的φ选择之一是计算的SELECT(%spec.select)，因此LLVM仍然设法部分擦除了原始控制流。

所以这很酷。但是有一个控制流我们明显忽略了。

Int do_ath(int count，int base){for(int i=0；i<；count；i++){base+=base；}return base；}。

定义DSO_LOCAL I32@do_ath(I32%count，I32%base)LOCAL_UNNAME_ADDR#0{entry：%cmp5=ICMP SGT I32%count，0 br i1%cmp5，LABEL%for.body，LABEL%for.cond.leanup for.cond.leanup：；Preds=%for.body，%entry%base.addr.0.lcssa=phi I32[%base，%entry]，[%add，%for.body]ret I32%base.addr.0.lcssa for.body：；Preds=%entry，%for.body%i.07=phi I32[%Inc，%for.body]，[0，%entry]%base.addr.06=Phi I32[%add，%for.body]，[%base，%entry]%add=shl NSW I32%base.addr.06，1%Inc=添加NUW NSW I32%i.07，1%exitcond.not=ICMP eq I32%Inc，%count br i1%exitcond.not，标签%for.cond.leanup，标签%for.body，！llvm.loop！26}。

因为我们通过COUNT提供循环界限，所以LLVM无法确保我们真正进入循环体。因此，我们的第一个φ在初始的%base和%add.LLVM的PHI语法之间进行选择。LLVM的PHI语法很有帮助地告诉我们，%base来自Entry块，%add来自循环，正如我们预期的那样。我不知道为什么LLVM为结果值选择了如此可怕的名称(%base.addr.0.lcssa)。

我们的索引变量初始化一次，然后使用每次for迭代进行更新，因此它还需要一个φ。我们在这里的选择是%Inc(每个主体从%i.07计算)和0文本(即我们的初始化值)。

最后，循环体的核心：我们需要获取base，其中base是initialbase值(%base)，或者是作为前一个循环的一部分计算的值(%add)。最后一次φ到达那里。

IR的其余部分是簿记：我们需要单独的SSA变量来计算每次循环迭代的加法(%add)、增量(%Inc)和退出检查(%exitcond.not)。

现在我们知道了什么是SSA表单，以及LLVM如何表示它们6.我们为什么要关心呢？

正如我在文章前面简要提到的，归根结底是优化潜力：SSA形式的程序特别适合于许多有效的优化。

优化编译器可以做的最简单的事情之一就是删除可能无法执行的代码。这使得生成的二进制文件更小(而且通常更快，因为指令高速缓存中可以容纳更多的文件)。

“死”代码分为几类7，但常见的一类是不能影响程序行为的赋值，如冗余初始化：

Int main(Void){int x=100；if(rand()%2){x=200；}Else if(rand()%2){x=300；}Else{x=400；}返回x；}。

如果没有SSA表单，优化编译器将需要检查x的任何使用是否达到其原始定义(x=100)。单调乏味。在SSA形式中，这显然是不可能的：

Int main(Void){int x_0=100；//忽略作用域。计算机不是真实生活。If(rand()%2){int x_1=200；}Else if(rand()%2){int x_2=300；}Else{int x_3=400；}返回φ(x_1，x_2，x_3)；}。

定义DSO_LOCAL I32@main()local_unname_addr#0{entry：%call=call I32@rand()#3%0=and I32%call，1%tobool.not=ICMP eq I32%0，0 br i1%tobool.not，Label%if.Else，Label%if.end6 if.Else：；Preds=%Entry%Call1=call I32@rand()#3%1=and I32%Call1，1%tobool3.not=ICMP eq I32%1，0%.。=SELECT i1%tobool3.not，I32 400，I32 300 br标签%if.end6 if.end6：；Preds=%if.Else，%Entry%x.0=Phi I32[200，%Entry]，[%。，%if.Else]ret I32%x.0}

编译器还可以通过使用常量变量代替常量值本身来优化程序。让我们看一下C的另一个斑点：

Int SOME_MATH(Int X){int y=7；int z=10；int a；if(rand()%2){a=y+z；}Else if(rand()%2){a=y+z；}Else{a=y-z；}return x+a；}。

作为人类，我们可以看到y和z被赋予了微不足道的值，并且从未修改过8。然而，对于编译器来说，这是从上面得到的定义问题的一个变体：在它可以分别用7和10替换y和z之前，它需要确保y和z永远不会被赋予不同的值。

Int SOME_MATH(Int X){int y_0=7；int z_0=10；int a_0；if(rand()%2){int a_1=y_0+z_0；}Else if(rand()%2){int a_2=y_0+z_0；}Else{int a_3=y_0-z_0；}int a_4=φ(a_1，a_2，a_3)；返回x+a_4；}。

这实际上与我们的原始形式相同，但有一个关键的区别：编译器现在可以看到y和z的每一个加载都是原始赋值。换句话说，它们都是可以安全更换的！

Int SOME_MATH(Int X){int y=7；int z=10；int a_0；if(rand()%2){int a_1=7+10；}Else if(rand()%2){int a_2=7+10；}Else{int a_3=7-10；}int a_4=φ(a_1，a_2，a_3)；return x+a_4；}。

所以我们去掉了几个潜在的注册操作，这很好。但这里是真正关键的部分：我们已经为其他几个优化做好了准备：

现在我们已经传播了一些常量，我们可以做一些微不足道的常量折叠：7+10变成17，以此类推。

在SSA形式中，观察到只有x和a_{1..4}可以影响程序的行为是微不足道的，所以我们可以应用上面的死代码消除，并完全删除y和z！

这才是优化编译器的真正魔力：每个单独的优化都很简单，而且很大程度上是独立的，但它们一起产生了一个良性循环，可以重复进行，直到收益减少。

寄存器分配(或者：寄存器调度)本身并不是一种优化，更多的是编译器工程中不可避免的问题：假装可以访问无限数量的可寻址变量很有趣，但编译器最终坚持将运算归结为一小部分固定的CPU寄存器。

寄存器分配的约束和复杂性因体系结构而异：众所周知，x86(AMD64之前的版本)需要寄存器9(只有8个完整的通用寄存器，其中6个可能在函数的作用域10内可用)，而RISC体系结构通常使用更多数量的寄存器来弥补缺少寄存器-内存操作。

如上所述，减少到SSA形式对寄存器分配器既有间接的好处，也有直接的好处：

间接地：消除冗余加载和存储减少了寄存器分配器的总体压力，使其能够避免昂贵的溢出(即，必须临时将有效寄存器转移到主存储器以容纳另一条指令)。

直接：在历史上，编译器在寄存器分配之前将φ降低为副本，这意味着寄存器分配器传统上没有从SSA表本身中受益。然而，(半)最近有关于将SSA表直接应用于线性和着色分配器的(半)近期研究。

一个具体的例子是：现代JavaScript引擎使用JIT来加速程序评估。这些JIT经常使用线性寄存器分配器，在寄存器选择速度(顾名思义，线性)和可接受的寄存器调度之间进行可接受的折衷。从SSA格式转换出来本身就是一种及时的操作，在编译时间是执行时间一部分的JIT和其他上下文中，对SSA表示本身的线性分配很有吸引力。

关于SSA，我在这篇文章中没有涉及到很多事情：优势边界、“修剪”的SSA形式和不太优化的SSA形式之间的权衡，以及程序的SSA形式和编译器停止优化的决定之间的反馈机制等等。每一篇都可以是自己的博客帖子，也可能是将来的帖子！

从这个意义上说，每个任务在概念上都是独立的，并且都有定义良好的输入和输出。个别编译器在合并或进一步拆分任务方面具有一定的灵活性。-↩。

AST和中间表示之间的区别很模糊：Rust在编译过程的早期将它们的AST转换为HIR，并且语言可以被设计为具有可修改的AST，以进行分析，否则在IR上是最好的。-↩。

这可以分为词法验证(例如，使用未声明的标识符)和语义验证(例如，错误的初始化。

.