函数式程序员的静态单一赋值

我是说兰布达是我的部落。你知道部落主义是如何运作的：当两个部落相遇时，通常是争吵，而不是交流。

因此，我已经在Lambda演算、延续传递风格的中间语言、闭包转换和Lambda提升的知识中得到了很好的灌输。但是，当谈到来自我们部落以外的想法时，我们兰布达部落的人通常会置身事外。

在蒙特利尔的最后一次计划研讨会上，一个可怜的家伙竟然在舞台上大胆地提到了SSA。(SSA是机器部落在他们的编译器中作为中间语言使用的。)。我不认为在奥林·瑟弗斯(Olin Shivers)低沉地说起这句话之前，他已经说出了这句话。你指的是CPS？(CPS就是我们用的东西。)。观众中传来一阵笑声，包括我自己。

但是，我们可以从SSA语言和它实现的优化中学到宝贵的经验教训，尽管它可能来自另一个部落。在这篇文章中，我想看看SSA的本质是什么。要做到这一点，我将从解释中间语言的函数式编程故事开始，因为我的许多读者都不属于我的圈子。然后，我们将使用它作为一个固定点，可以与SSA进行比较。

最开始的是Lambda。上帝看到了，意识到他不需要其他任何东西，于是就止步于此。

嘿，这是真的，对吧？λ演算是伟大的，因为它的表现力和精确度。从这个意义上说，这个评估是一个实用的评估：λ演算允许我们对计算进行精确的推理，所以它值得保留。

我不认为丘奇在20世纪30年代提出λ微积分时正在考虑数字计算机，因为当时数字计算机还不存在。麦卡锡在20世纪60年代提出Lisp时也没有考虑过计算机。但是麦卡锡的一个学生确实破解了它，而且我们现在仍然在做这样的事情：在λ微积分的语言和机器语言之间进行翻译。

当然，这个翻译过程就是编译。在实践计算机科学的最初20年左右的时间里，编译器(甚至是语言)都是非常特别的。一开始它们并不存在，你只需使用控制面板上的开关或其他类似的东西直接编写机器代码，然后再用汇编语言即可。但最终人们解决了解析问题，你得到了第一批高级语言的编译器。

我以前写过关于C不是高级汇编语言的文章，但那时候FORTRAN确实是这样的语言。解析器和代码生成器之间没有太多区别。每个人都知道现在编译器是如何工作的：解析、优化，然后生成代码。你工作的媒介是你的中间语言。一种好的中间语言应该简单，这样您的优化器就可以简单；富于表现力，这样您就可以很容易地从源程序生成它；而且实用，因为它的结构支持您想要进行的各种优化。

在这方面，lambda部落已经有了一种很好的中间语言，其形式就是lambda演算本身。在很多方面，解决lambda演算中的逻辑问题非常类似于优化程序。拷贝传播是测试版缩减。内联是将复制传播扩展到lambda表达式。延续的eta-转换消除了"；转发块"；--没有语句的基本块，而只是跳转到其他延续。功能的ETA转换消除了功能蹦床。

但我有点言过其实了。你看，在lambda部落，我们实际上并不用lambda演算编程。如果你读过我们的任何一篇论文，总会在开头有一节定义我们正在使用的语言，然后将其语义定义为对lambda演算的翻译。

这种翻译对于任何编程语言都是可能的，事实上，Peter Landin在1965年为ALGOL做到了这一点。Landin的原始翻译使用他的J操作符来捕获延续，从而可以更直接地将代码翻译成lambda演算。

几年前，我写了更多关于兰丁、letrec和Y组合子的文章，但我想提一提最近的一篇论文，这篇论文对J进行了现代审视，这篇论文是对兰丁J算子的理性解构(A Rational Deconstruction of Landin'；‘s J Operator)。本文由V8黑客Kevin Millikin合著，并引用了V8黑客Mads Sig Ager和Lasse R.Nielsen的工作。事实上，这三个人似乎都有幸得到奥利维尔·丹维(Olivier Danvy)担任博士导师的殊荣。那是我的部落！

无论如何，J在Landin的抽象SECD机器的上下文中非常有用，该机器用于研究程序和编程语言的语义。然而，它并不能帮助编译器的实现者在普通机器上运行，而且中间语言都是关于实用程序的。对于函数式程序员来说，这个问题的答案是将源程序转换为所谓的延续传递样式(CPS)。

有了CPS，程序就被翻了个底朝天。因此，不是(+1(f(+23)，而是：

λ返回让c1=1让k1 t1=_+返回c1 t1让k2 t2=f k1 t2让c2=2，c3=3_+k2 c2 c3

通常会去掉外层的lambda，因为它是隐式的。出于λ演算的目的，CPS程序中的每个调用都是尾部调用。延续被显式表示为lambda表达式。每个函数调用或基元操作都将延续作为参数。这一领域的论文通常使用丘奇最初的λ微积分记法，而不是我在这里给出的ML式记法。CPS转换引入的延续通常都是这样标记的，这样以后就可以有效地编译它们，而不需要进行任何流分析。

对于函数可以作为值传递的语言，CPS能够表达高阶控制流。

所有临时值均已命名。未引用的名称表示死代码，或仅为产生效果而编译的代码。引用的名称是寄存器分配器的自然输入。

延续对应于命名的基本块。它们在源代码中的名称对应于自然流分析，只需跟踪名称的定义和使用即可。流分析支持更多优化，如代码移动。

根据您实现CPS语言的方式，您还可以将注释附加到不同的延续，以帮助您的图形进一步缩减：此延续是一个效果上下文(因为它的形参在其主体中未被引用，或者因为您在创建它时知道这一点)，因此它的调用者可以根据效果而不是值进行处理；这个变量是可变的(例如，可以接收一个或两个值)，因此我们可以根据需要直接跳到正确的处理程序；等等。Guile'；的编译器现在不在CPS中，但我正考虑出于这个原因重写它，以允许更透明地处理控制流。

请注意，在那里我没有提到Scheme'；Call-with-Current-Continue！对我来说，CPS的用处在于它显式地命名了时态、延续以及对优化的支持。Call/cc在Guile Scheme中是一个罕见的构造，使用CPS可以对其进行更好的优化，但我并不太关心它，因为通常不可能证明Continue不会转义，在这种情况下，无论如何您都是在缓慢的道路上。

所以这就是CPS。延续编译成函数内的跳转，函数编译成闭包，或者顶层函数的标签。我能给出的最好的参考资料是安德鲁·肯尼迪(Andrew Kennedy)2007年的论文，“继续编译”(Compiling With Continuations)。CWCC是一篇非常棒的论文，我强烈推荐它。

CPS在90年代失宠，取而代之的是后来被称为管理范式(ANF)的东西。ANF类似于CP，不同之处在于代码没有命名Continuations，而是将代码保留在所谓的直接样式"；中，其中的Continuations是隐式的。因此，我前面的示例如下所示：

设c2=2，c3=3，t2=+c2c3，t1=ft2，c1=1+c1t1。

与贝塔规则一样，CPS降低也有ANF对应关系。有关更多信息，请参阅“使用延续进行编译的本质”一文，其中引入了ANF并引发了原始CPS公式的衰落。

这种CPS-VS-ANF的讨论仍然在进行，即使是在2011年的今天。特别值得一提的是，肯尼迪的CWCC论文相当有说服力。但这场辩论在很大程度上是由机器部落取得的进步引起的，这一进步是由他们的SSA中间语言实现的。

机器部落没有像lambda部落那样将命名和控制的抽象概念编译到现有的硬件上，而是将可用的硬件视为给定的硬件，并试图将机器的功能暴露给程序员。

机器部落不会使用闭包、延续或尾部调用。但它们确实有循环，而且它们会处理大量数据。对于像C这样的机器部落语言的编译器来说，最重要的是为循环生成高效的机器代码。

显然，我在这里做了一些简化。但是，如果您查看一种机器部落语言(如Java)，您将处理该语言中内置的许多控制流构造(for、while等)。而不是像Scheme中的循环一样分层在递归之上。这意味着程序的大部分、重要部分已经崩溃为一阶控制流图问题。在此基础上分层其他优化，如内联(所有优化之母)，只会展开这个一阶流程图。稍后会有更多关于第一份订单的内容。

所以!。在与这个问题斗争了几十年之后，在从汇编语言抽象到三地址寄存器传输语言之后，机器专家们终于想出了一些真正伟大的东西：静态单赋值(SSA)形式。这里的圆弧远离机器，朝向更抽象的方向，以便能够更好地优化，从而生成更好的代码。

正是出于这个功利的原因，SSA应运而生。考虑一下最早的SSA论文之一，罗森、韦格曼和扎德克的“全球价值数字和冗余比较”(Global Value Number And Redundant Compare)。Rosen等人关心的是能否将不变表达式移出循环，将值编号技术扩展到跨基本块操作。但是他们一直在使用的面向赋值的中间语言阻碍了代码的移动。

为了解决这个问题，Rosen等人从机器部落的面向赋值的模型切换到了lambda部落的面向绑定的模型。

在SSA中，变量永远不会变异(赋值)；它们只绑定一次，然后就保持原样。对源程序变量的赋值会在SSA中间语言中生成新的绑定。

函数CLAMP(x，LOWER，UPPER){IF(x<；LOWER)x=LOWER；ELSE IF(x&>；UPER)x=SUPPER；RETURN x；}。

条目：x0，lower0，upper0=args；转到b0；b0：t0=x0<；lower0；转到t0？B1：b2；b1：x1=lower0；转到退出；b2：t1=x0>；upper0；转到T1？B3：退出；b3：x2=upper0；转到退出；退出：x4=phi(x0，x1，x2)；返回x4；

SSA表单将过程分解成多个基本块，每个基本块都以分支到另一个块(无论是有条件的还是无条件的)结束。通常，临时值也会收到自己的名称，因为这有助于优化。

关于SSA有趣的是最后一点，即函数。PHI函数放置在控制流连接处。在我们的例子中，x的值可能来自第一个或第二个if语句中的参数或赋值。φ函数表明了这一点。

但是你知道，兰布达部落，我真的不明白这是什么意思。什么是φ函数？考虑到这个名字是从哪里来的，最初的IBM编译器黑客放入一个假函数来合并各种值，这对他们没有帮助，但如果他们想要得到期刊编辑的认真对待，他们认为"；φ；是一个更好的名字。

也许φ函数对于机器部落来说是直观的；我不知道。我怀疑。但幸运的是，还有另一种解释：每个基本块都是一个函数，而φ函数表示基本块有一个参数。

入口x下部上部=letrec b0=让t0=x0<；如果t0那么b1()否则b2()b1=让x=下部出口(X)；b2=让t1=x>；上部0如果t1则b3()否则退出(X)b3=让x=上部出口(X)；出口x=xb0()。

在这里，我将基本块表示为命名函数，而不是标签。我们允许块接受一些参数，而不是phi函数；调用位置决定了phi函数可能采用的值。

请注意，对块的所有调用都是尾部调用。让你想起了CPS，不是吗？有关更多信息，请参阅理查德·凯尔西的经典论文“接续传球风格与静态单一赋值形式之间的对应”，或我早先关于兰丁、斯蒂尔、莱特雷克和标签的文章。

不过，如果想要一篇简短、易读、有趣的文章，请参阅阿佩尔的“SSA is Functional Programming”(SSA是函数式编程)。我同意阿佩尔的观点，我们兰布达部落的人过于拘泥于我们的形式主义，而有时正确的做法是画流程图。

如果只是这样，就像我到目前为止所说的那样，那么SSA就不会像CPS，甚至ANF那样有趣了。但是SSA不仅仅与绑定有关，它还与控制流有关。为了正确放置您的phi函数，您需要构建所谓的主控器树。如果所有控制路径在到达第二个控制路径之前必须经过第一个基本块，则称一个基本块支配另一个基本块。

例如，Entry块始终控制整个函数。在上面的示例中，b0还控制所有其他块。然而，虽然b1确实分支到出口，但它并不支配它，因为出口可能在其他路径上到达。

结果是，您需要将φ函数放在变量定义满足变量使用的任何位置，而该变量不是严格由该定义支配的。在我们的示例中，这意味着我们在出口上放置一个φ节点。主导者树是一种精确、高效的控制流分析，它允许我们回答这样的问题(我应该将φ节点放在哪里？)。

有关SSA和主控器的更多信息，请参阅Cytron、Ferrante、Rosen、Wegman和Zadeck在1991年发表的可读性很高的论文“高效计算静态单一赋值表和控制依赖图”。

SSA的典型实现在每个基本块中嵌入指向块的前导和后导的指针，以及块的主导者和(有时)后主导者。(前置任务是控制流图中给定节点之前的块；后继任务在它之后。后主控器类似于主控器，但对于反向控制流，请搜索管道以了解更多信息。)。有一些众所周知的算法可以在线性时间内计算这些链接，SSA社区在这种廉价的流量信息基础上开发了许多优化。

相反，lambda部落的焦点更多地集中在过程间控制流上，据我所知，没有人在O(N2)时间内做到这一点，正如我祖母所说，这就是Turrible"；。

我一开始就特意提到了全局值编号(GVN)。20多年后，这仍然是JIT编译器中代码移动的重要算法。HotSpot C1和V8都在使用它，它刚刚登陆了IonMonkey。GVN是众所周知的，研究得很好的，而且它是有效的。这会导致循环不变代码移动：如果不变定义到达循环标头，则可以将其提升出循环。相比之下，我不知道来自兰姆达部落的任何东西是真正堆积起来的。可能有一些东西，但肯定没有那么深入的研究。

机器部落的人们，你们能想象返回一个块作为值吗？我不这么认为。退回标签是没有意义的。但这正是λ微积分的意义所在。可以将块表示为函数，并将其作为函数使用，但也可以将它们作为参数传递并作为值返回。这样的块比作为跳转目标的正常类型的块具有更高的顺序。事实上，这是在基本的λ演算中表示递归的唯一方式。

这就是当我说CPS作为一种高级中间语言很好，以及当我说SSA是一种很好的一阶中间语言时，这就是我的意思。

如果您有一种基本上更高阶的语言，其中您需要通过递归进行循环，那么您有两个选择：进行全程序分析以积极地闭包-将您的程序转换为一阶，然后您可以使用SSA，或者使用更高阶的IL，并使用更像CPS的东西。

MLton是执行前者的编译器的一个示例。实际上，MLton的SSA实现非常可爱。它们确实将块表示为带参数的函数，而不是标签和phi函数。

但是，如果您不能进行全程序分析--可能是因为您希望在运行时扩展程序、支持单独编译等--那么您就不能将SSA用作全局IL。当然，这并不是说您不应该识别程序的一阶部分，并对其应用类似SSA的分析和优化！那才是兰姆达部落真正应该去的地方。

我写这篇文章是因为我正在编写V8'；的曲轴编译器，我意识到我不理解其中的一些习语，所以我去看了一大堆论文。同时，我想为我的诡计工作解决CPS与ANF的问题。(Guile目前有一个直接风格的编译器，针对它的优化非常少；这主要是由于难以使用IL造成的。)。

这篇帖子总结了我的发现，但我确信我在什么地方弄错了。请注意评论中的任何更正。

安德烈亚斯·兹文考(Andreas Zwinkau)说：什么是φ函数？您可能会认为这是一种有趣的表示副本的方式，因为这是它们被解构/删除的方式。我会用SSA格式编写您的示例，如下所示：

函数夹具(X0，LOWER，UPPER){if(x0；lt；LOWER)x1=LOWER；ELSE IF(X0&>；UPER)x2=UPPER；x3=Phi(x1，x2，x0)；返回x3；}。

函数CLAMP(x，LOWER，UPPER){IF(x<；LOWER)；ELSE IF(x&>；UPER)；x2=φ(LOWER，UPPER，x)；RETURN x2；}。

函数夹具(X0，LOWER，UPPER){IF(x<；LOWER)x2=LOWER；ELSE IF(x&>；UPER)x2=UPPER；ELSE x2=x；RETURN x2；}。

例如，LLVM在后端执行此操作。由于x2被分配了两次，因此它不再是SSA形式。

另外，请注意，SSA-Form不是一种或一种类型的IL。它是一种表示的属性。而且，没有任何关于SSA的东西是你不能没有它的。它只是将分析(如达到定义)编码到程序表示中。

最后，让我很恼火的是，SSA实际上让变量的概念变得不必要了。因为任何操作数都只有一个定义操作，所以您可以通过引用此操作来表示该操作。这使得像复制传播这样的东西是隐式的，因为副本是Noop。请参阅http://pp.info.uni-karlsruhe.de/publication.php?id=braun11wir。

Verte说：相比之下，Lambda部落的焦点更多地放在*程序间控制流上，据我所知，没有人在O(N^2)时间内做到这一点，正如我祖母所说，这就是说，就像我的祖母所说的那样，这就是Turrible"；。"；的焦点更多地集中在*程序间控制流上。"；据我所知，没有人在O(N^2)时间内做到这一点。

如果你做某些事情懒惰，你可以在一般情况下做到这一点。然而，你能不能做到这一点取决于你实际上想要分析的是什么。

Don Stewart说：请注意，您可以在SSA和ANF格式之间进行转换。参见2003年的论文《SSA优化算法的功能透视》，Chakravarty，Keller and Zadarnowski，其中介绍了(和imp。

.