Engee 文档

在Julia中以SSA形式表示IR

Julia使用带有单个赋值的静态中间表示来执行优化（https://en.wikipedia.org/wiki/Static_single-assignment_form [SSA IR])。 这种IR表示与LLVM的IR表示不同，并且是Julia独有的。 它允许你优化你的工作与朱莉娅。

  1. 基块（没有执行顺序的区域）被显式注释。

  2. If/else语句和循环转换为’goto’语句。

  3. 通过引入变量将具有多个操作的行拆分为多行。

例如，下面的Julia代码:

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

当使用`Float64`参数调用时，它将转换为以下内容:

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, если не %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 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3, если не %2

  1. 'If’语句转换为表达式`goto#3if not%2`，如果`x>5`未执行，则进入第三个基块，否则进入第二个基块。

  2. '%2’是为表示`x>5’而输入的SSA值。

<无翻译>

问题背景

从Julia0.7开始，一些编译器组件在https://en.wikipedia.org/wiki/Static_single_assignment_form [SSA形式]。 以前，编译器从简化的AST Julia表示直接生成LLVM IR表示。 在这种形式中，语法抽象大部分被消除了，但它仍然非常类似于抽象语法树。 为了简化优化，随着时间的推移，SSA值被引入到这个IR表示中，并且IR表示被简化为线性形式（即，函数参数只能是SSA值或常量）。 然而，由于IR中没有phi节点（这是条件执行顺序的反向边和重新合并所必需的），SSA（插槽）以外的值仍保留在IR中。 这否定了SSA表示在执行中间优化时的许多优点。 为了使优化在没有SSA形式的完整表示的情况下发挥作用，做出了英勇的努力，但缺乏这种表示最终被证明是一个不可逾越的障碍。

IR节点的类别

SSA IR表示中有四类IR节点：phi节点、pi节点、PHIS节点和upsilon节点（后两者仅用于异常处理）。

Phi和pi节点

Phi节点是通用SSA抽象的一部分（如果这对您来说是一个新概念，请参阅上面链接上的信息）。 在IR Julia中，这些节点表示如下:

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

其中保证两个向量始终具有相同的长度。 在规范表示（由代码生成器和解释器处理）中，边值指示源运算符的数字（即，如果边具有值`15`，则必须存在转换`goto`，`gotoifnot`或从运算符`15`隐式转移控制，其目的是此节点）。 这些值可以是SSA值或常量。 如果未定义沿此路径的变量，则可能无法分配该值。 但是，不确定性检查是在中间优化后显式添加并用布尔值表示的，因此代码生成器可以假设任何时候使用phi节点，分配的值都将在适当的插槽中。 此外，允许不完整的表示，即phi节点可能缺少传入边。 在这种情况下，要求动态地确保不使用相应的值。

请注意，在语义上，SSAS应用在相应前身的完成符号之后（"在边缘"）。 因此，如果几个phi节点出现在基块的开始处，则同时执行它们。 这意味着在下一个IR片段中，如果我们来自块`23`，%46`将在我们进入该块之前取与%45`相关联的值。

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

Pi节点编码静态验证的信息，这些信息可以在给定pi节点控制的基块中隐式假定。 根据操作原理，它们等同于文档中呈现的技术。 https://dl.acm.org/citation.cfm?id=358438.349342 [ABCD：]https://dl.acm.org/citation.cfm?id=358438.349342 []https://dl.acm.org/citation.cfm?id=358438.349342 [Eliminating Array Bounds Checks on Demand]（ABCD：按需消除数组边界检查），或LLVM中的谓词信息节点。 让我们以他们的工作为例。

%x::Union{Int, Float64} # %x — это некоторое значение ssa типа Union{Int, Float64}
if isa(x, Int)
    # используем x
else
    # используем x
end

我们可以插入谓词并将此代码转换为以下内容:

%x::Union{Int, Float64} # %x — это некоторое значение ssa типа Union{Int, Float64}
if isa(x, Int)
    %x_int = PiNode(x, Int)
    # используем %x_int
else
    %x_float = PiNode(x, Float64)
    # используем %x_float
end

Pi节点通常被解释器忽略，因为它们对值没有影响，但有时它们会导致编译器形成代码（例如，将具有联合隐式划分的表示转换为简单的未打包表示）。 Pi节点的主要好处是，值的路径条件可以通过定义-使用链的简单通道而累积，这在某种程度上是通过考虑这些条件的大多数优化进行的。

PHIS和upsilon节点

异常处理稍微使SSA操作方案复杂化，因为它在IR中引入了额外的执行顺序边，必须沿着这些边跟踪值。 LLVM中使用的方法之一是进行可以将异常传递给基本块终止符的调用，并将显式执行顺序边缘添加到拦截处理程序。:

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

regular:
# Порядок выполнения продолжается здесь

catch:
# Исключения поступают сюда

但是，在像Julia这样的语言中，在调用create exceptions的优化管道开始时不知道，这可能会有问题。 为了以防万一，我们将不得不假设每个调用都会引发异常（即Julia中的每个语句）。 这种做法将产生若干消极后果。 首先，每个基块的作用域实际上将缩减为单个调用，这将使在基块级别执行操作毫无意义。 其次，每个基本的catch块都有`n*m’节点参数（其中`n`是代码关键部分中的语句数，`m`是catch块中的活动值数）。

为了解决这个问题，我们使用节点`Upsilon`和`PhiC`的组合（其中C代表`catch`;在IR结构打印输出程序中，这被写为`φᶜ`，因为字符"c"的下标在Unicode中不可用）。 这些节点的目的可以用不同的方式解释，但将每个节点想象为"PhiC"可能是最容易的。 作为加载从一个独特的插槽进行多次保存和单次读取，并"Upsilon"作为相应的保存操作。 节点’PhiC’包含执行保存到其隐式槽的所有upsilon节点的操作数列表。 但是，"Upsilon"节点不会注册有关其保存到的"PhiC"节点的信息。 这确保了与IR SSA表示的其余部分更自然的集成。 例如，如果PhiC节点不再使用，则可以安全地将其删除。 对于’Upsilon’节点也是如此。 在大多数IR通道中，"PhiC"节点可以被视为"Phi"节点。 它们允许您遵循"使用定义"链，并且可以升级到新的’PhiC’和`Upsilon’节点（与原始`Upsilon`节点位于相同的位置）。 此方案的结果是，`Upsilon`节点（和`PhiC`参数）的数量与分配给特定变量的值（在SSA转换之前）的数量成正比，而不是代码关键部分中的语句数量。

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

@noinline opaque() = invokelatest(identity, nothing) # Что-то непрозрачное
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’的基本数据结构值得关注。 它的灵感来自LLVM和Webkit B3IR。 数据结构基于算子的平面向量。 每个运算符根据其在向量中的位置隐式分配一个SSA值（即，可以使用`SSAValue(1)`等访问位置idx1处的运算符的结果。). 对于每个SSA值，附加地确定其类型。 由于根据定义，SSA值只分配一次，因此类型也是相应索引处表达式的结果类型。 然而，尽管这种表示相当有效（因为赋值不需要显式编码），但它具有明显的缺点，即顺序具有语义意义，这就是为什么运算符编号在重新排序和插入期间变 此外，不维护使用列表（也就是说，如果没有显式计算映射，就不可能从定义到其所有用例；但是，定义列表并不构成特定的问题，因为可以通过索引找到相应的运算符），因此LLVM样式中的RAUW操作（"将所有用例替换为"）不可用。

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

  • 我们为插入保留了一个单独的节点缓冲区（包括插入位置，相应值的类型以及节点本身）。 节点根据插入缓冲区中的顺序进行编号，这允许它们的值直接在IR的其他地方使用（也就是说，如果原始运算符列表中有12个运算符，则第一个新运算符将

  • RAUW风格的操作是通过为相应的运算符索引分配一个新值来执行的。

  • 要删除一个运算符，它被分配值’nothing`（这本质上只是上述约定框架内的一个特例）。

  • 如果存在使用已删除运算符的情况，则会将它们分配为"nothing"。

有一个名为’compact！'通过在适当位置插入节点，正常分发副本以及根据新的SSA值重命名用例来压缩上述数据结构。 然而，该方案的一个显着特征是压缩可以作为后续传递的一部分"懒惰地"执行。 大多数优化过程必须经过整个操作员列表，在过程中执行分析或更改。 为了遍历运算符列表，我们提供了’IncrementalCompact’迭代器。 它执行必要的压缩并返回新的节点索引以及节点本身。 在这个阶段，允许绕过定义使用链，以及在IR中进行更改和删除元素（但是禁止插入）。

该方案的要点在于，由于优化过程在任何情况下都必须访问适当的内存区域，这需要开销，因此额外清理的成本将相对较小（并且在IR更改期间维护这些数据结构的成本将被消除）。