朱莉娅SSA-表格IR

Julia使用静态单赋值中间表示（https://en.wikipedia.org/wiki/Static_single-assignment_form[SSA IR])来执行优化。该IR与LLVM IR不同，并且是Julia独有的。它允许Julia特定的优化。

基本块（没有控制流的区域）被显式注释。
if/else和循环变成 后藤 发言。
通过引入变量将具有多个操作的行拆分为多行。

例如下面的Julia代码:

function foo(x)
    y = sin(x)
    if x > 5.0
        y = y + cos(x)
    end
    return exp(2) + y
end

当用 漂浮64 论证被翻译成:

using InteractiveUtils
@code_typed foo(1.0)

CodeInfo(
1 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3 if not %2
2 ─ %4 = invoke Main.cos(x::Float64)::Float64
└── %5 = Base.add_float(%1, %4)::Float64
3 ┄ %6 = φ (#2 => %5, #1 => %1)::Float64
│   %7 = Base.add_float(7.38905609893065, %6)::Float64
└──      return %7
) => Float64

在这个例子中，我们可以看到所有这些变化。

第一个基本块是所有的东西

1 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3 if not %2

该 如果 声明被翻译成 转到#3如果不是%2 如果进入第三个基本区块 x>5 未被满足，否则转到第二个基本块。
%2 是引入SSA值来表示 x>5.

背景资料

从Julia0.7开始，编译器的部分使用新的https://en.wikipedia.org/wiki/Static_single_assignment_form[SSA-形式]中间表示（IR）。从历史上看，编译器将直接从Julia AST的降低形式生成LLVM IR。这种形式删除了大多数语法抽象，但仍然看起来很像抽象语法树。随着时间的推移，为了便于优化，SSA值被引入到这个IR中，并且IR被线性化（即变成函数参数只能是SSA值或常量的形式）。然而，由于IR中缺少Phi节点（条件控制流的后沿和重新合并所必需的），非SSA值（时隙）保留在IR中。这否定了SSA表单表示在执行中端优化时的大部分用处。在没有完整的SSA表单表示的情况下，为了使这些优化工作，付出了一些英勇的努力，但缺乏这样的表示最终被证明是令人望而却步的。

IR节点的类别

SSA IR表示有四类IR节点：Phi，Pi，PhiC和Upsilon节点（后两者仅用于异常处理）。

Phi节点和Pi节点

Phi节点是通用SSA抽象的一部分（如果您不熟悉这个概念，请参阅上面的链接）。在Julia IR中，这些节点表示为:

struct PhiNode
    edges::Vector{Int32}
    values::Vector{Any}
end

其中我们确保两个向量始终具有相同的长度。在规范表示（由codegen和解释器处理的表示）中，边值表示来自语句编号（即，如果边有一个 15，必须有一个 后藤, gotoifnot 或者隐式地从语句中消失 15 以这个phi节点为目标）。值是SSA值或常量。如果变量未在此路径上定义，则也可以取消分配值。但是，在中端优化之后，未定义检查会显式插入并表示为布尔值，因此代码生成器可能会假设任何使用Phi节点的情况都将在相应的槽中具有分配的值。映射不完整也是合法的，即Phi节点缺少传入边。在那种情况下，必须动态保证不会使用相应的值。

请注意，SSA在语义上发生在相应前身的终止符之后（"在边缘"）。因此，如果多个Phi节点出现在一个基本块的开头，它们将同时运行。这意味着在下面的IR片段中，如果我们来自block 23, %46 将取与 %45 我们进入了这个街区。

%45 = φ (#18 => %23, #23 => %50)
%46 = φ (#18 => 1.0, #23 => %45)

Pinode编码可能在由给定pi节点支配的基本块中隐式假定的静态证明的信息。它们在概念上等同于论文中介绍的技术https://dl.acm.org/citation.cfm?id=358438.349342[ABCD：按需消除数组边界检查]或LLVM中的谓词信息节点。要了解它们是如何工作的，请考虑，例如

%x::Union{Int, Float64} # %x is some Union{Int, Float64} typed ssa value
if isa(x, Int)
    # use x
else
    # use x
end

我们可以执行谓词插入并将其转换为:

%x::Union{Int, Float64} # %x is some Union{Int, Float64} typed ssa value
if isa(x, Int)
    %x_int = PiNode(x, Int)
    # use %x_int
else
    %x_float = PiNode(x, Float64)
    # use %x_float
end

Pi节点通常在解释器中被忽略，因为它们对值没有任何影响，但它们有时可能导致编译器中的代码生成（例如从隐式联合拆分表示变为普通的未装箱表示）。 Pinode的主要用途源于这样一个事实，即值的路径条件可以简单地通过def-use链式行走来累积，这对于大多数关心这些条件的优化来说通常是这样做的。

PhiC节点和Upsilon节点

异常处理使SSA故事适度复杂化，因为异常处理将额外的控制流边缘引入到必须跟踪值的IR中。这样做的一种方法是调用可能会将异常抛出到基本的块终止符中，并向catch处理程序添加显式控制流边缘:

invoke @function_that_may_throw() to label %regular unwind to %catch

regular:
# Control flow continues here

catch:
# Exceptions go here

然而，这在像Julia这样的语言中是有问题的，在优化管道的开始，我们不知道哪些调用会抛出。我们必须保守地假设每个调用（在Julia中是每个语句）都会抛出。这将有几个负面影响。一方面，它基本上会将每个基本块的范围缩小到单个调用，从而破坏了在基本块级别执行操作的目的。另一方面，每个catch基本块都会有 n*m phi节点参数（n，关键区域的语句数, m 过catch块的活值的数量）。

为了解决这个问题，我们使用 厄普西隆 和 PhiC,PhiC 节点（c代表 渔获，写 φᶜ 在IRR打印机中，因为unicode下标c不可用）。有几种方法可以考虑这些节点，但也许最简单的方法是考虑每个节点 PhiC,PhiC 作为一个负载从一个独特的存储-许多，读一次插槽，与 厄普西隆 作为相应的存储操作。该 PhiC,PhiC 具有存储到其隐式槽的所有upsilon节点的操作数列表。该 厄普西隆 节点但是，不记录哪些 PhiC,PhiC 它们存储到的节点。这样做是为了与SSA IR的其余部分更自然地集成。例如，如果没有更多的用途 PhiC,PhiC 节点，删除它是安全的，对于一个也是如此 厄普西隆 节点。在大多数IR通行证, PhiC,PhiC 节点可以像 披 节点。人们可以通过它们跟随使用-def链，它们可以被提升到新的 PhiC,PhiC 节点和新 厄普西隆 节点（与原始节点位于相同的位置 厄普西隆 节点）。该方案的结果是，数 厄普西隆 节点（和 PhiC,PhiC arguments）与特定变量（SSA转换之前）的赋值数量成正比，而不是临界区域中的语句数量。

要查看此方案的作用，请考虑以下函数

@noinline opaque() = invokelatest(identity, nothing) # Something opaque
function foo()
    local y
    x = 1
    try
        y = 2
        opaque()
        y = 3
        error()
    catch
    end
    (x, y)
end

相应的IR（与不相关的类型剥离）是:

1 ─       nothing::Nothing
2 ─ %2  = $(Expr(:enter, #4))
3 ─ %3  = ϒ (false)
│   %4  = ϒ (#undef)
│   %5  = ϒ (1)
│   %6  = ϒ (true)
│   %7  = ϒ (2)
│         invoke Main.opaque()::Any
│   %9  = ϒ (true)
│   %10 = ϒ (3)
│         invoke Main.error()::Union{}
└──       $(Expr(:unreachable))::Union{}
4 ┄ %13 = φᶜ (%3, %6, %9)::Bool
│   %14 = φᶜ (%4, %7, %10)::Core.Compiler.MaybeUndef(Int64)
│   %15 = φᶜ (%5)::Core.Const(1)
└──       $(Expr(:leave, Core.SSAValue(2)))
5 ─       $(Expr(:pop_exception, :(%2)))::Any
│         $(Expr(:throw_undef_if_not, :y, :(%13)))::Any
│   %19 = Core.tuple(%15, %14)
└──       return %19

请特别注意，每个存在于关键区域中的值都会在关键区域的顶部获得一个upsilon节点。这是因为catch块被认为具有来自函数外部的不可见控制流边缘。因此，没有SSA值支配捕获块，并且所有传入的值都必须通过 φᶜ 节点。

主要SSA数据结构

主要的 SSAIR,SSAIR 数据结构值得探讨。它从LLVM和Webkit的B3IR中汲取灵感。数据结构的核心是语句的平面向量。每个语句根据其在向量中的位置隐式分配一个SSA值（即idx1处语句的结果可以使用 萨瓦卢(1) 等）。对于每个SSA值，我们额外维护其类型。由于SSA值仅定义分配一次，因此此类型也是相应索引处表达式的结果类型。然而，虽然这种表示相当有效（因为赋值不需要显式编码），但它当然带有顺序在语义上显着的缺点，因此重新排序和插入会更改语句编号。此外，我们不保留使用列表（即，如果没有显式计算这个映射，就不可能从def走到它的所有用途-def列表然而是微不足道的，因为你可以从索引中查找相应的

相反，我们执行以下操作:

*我们保留一个单独的节点缓冲区来插入（包括插入它们的位置，相应值的类型和节点本身）。这些节点通过它们在插入缓冲区中的出现来编号，允许它们的值立即在IR的其他地方使用（即如果原始语句列表中有12个语句，则第一个新语句将作为 萨瓦卢(13)). *通过将相应的语句索引设置为替换值来执行RAUW样式操作。 *通过将相应的语句设置为 什么都没有 （这基本上只是上述的特例约定）。 *如果有任何正在擦除的语句的用途，它们将被设置为 什么都没有.

有一个 紧凑！ 通过在适当的位置执行节点的插入，琐碎的复制传播以及将用途重命名为任何更改的SSA值来压缩上述数据结构的函数。然而，这种方案的巧妙部分是，这种压实可以作为后续传递的一部分而懒惰地完成。大多数优化过程都需要遍历整个语句列表，并在此过程中执行分析或修改。我们提供 递增契约 可用于迭代语句列表的迭代器。它将执行任何必要的压缩并返回节点的新索引以及节点本身。在这一点上，走def-use链，以及对IR进行任何修改或删除是合法的（但是不允许插入）。

这种安排背后的想法是，由于优化传递无论如何都需要触及相应的内存并产生相应的内存访问惩罚，因此执行额外的内务管理应该具有相对较小的开销（并节省在IR修改期间维护这些数据结构的开销）。