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更改期间维护这些数据结构的成本将被消除)。