Julia SSA-form IR

Julia SSA-form IR

Background

从Julia 0.7开始,部分编译器使用新的SSA形式的中间表示形式 . 从历史上看,该编译器曾经用于从Julia AST的简化形式直接生成LLVM IR. 这种形式删除了大多数语法抽象,但看起来仍然很像抽象语法树. 随着时间的流逝,为了促进优化,将SSA值引入此IR,并将IR线性化(即,函数参数只能是SSA值或常量的形式). 但是,由于IR中缺少Phi节点(对于后缘和条件控制流的重新合并是必需的),IR中仍然保留了非ssa值(插槽),从而使SSA表单表示的许多有用性丧失了.执行中端优化. 在没有完整的SSA表单表示形式的情况下,为使这些优化工作付出了巨大的努力,但最终却缺乏这种表示形式.

New IR nodes

利用新的IR表示,编译器学会了处理四个新的IR节点,即Phi节点,Pi节点以及PhiC节点和Upsilon节点(后两个仅用于异常处理).

Phi nodes and Pi nodes

Phi nodes are part of generic SSA abstraction (see the link above if you're not familiar with the concept). In the Julia IR, these nodes are represented as:

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

我们要确保两个向量的长度始终相同. 在规范表示中(由codegen和解释器处理),边沿值指示来自语句的编号(即,如果edge的条目为15 ,则必须有gotogotoifnot或隐式掉落语句15作为目标此phi节点). 值可以是SSA值或常量. 如果未在此路径上定义变量,则也可能会取消分配值. 但是,不确定性检查会在中端优化后被明确插入并表示为布尔值,因此代码生成器可能会假设任何phi节点的使用都会在相应的插槽中分配一个值. 映射不完整也是合法的,即phi节点缺少输入边缘. 在这种情况下,必须动态保证不会使用相应的值.

PiNode编码静态证明的信息,这些信息可以隐含在给定pi节点主导的基本块中. 它们在概念上等同于论文" 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节点通常在解释器中被忽略,因为它们对值没有任何影响,但是它们有时可能导致编译器中的代码生成(例如,从隐式联合拆分表示更改为纯无框表示). PiNodes的主要用途是基于这样的事实,即值的路径条件可以简单地通过def-use链走累积起来,对于大多数关心这些条件的优化通常都这样做.

PhiC nodes and Upsilon nodes

异常处理会在一定程度上使SSA复杂化,因为异常处理在IR中引入了附加的控制流边缘,必须在这些边缘上跟踪值. LLVM紧随其后的一种方法是进行调用,这些调用可能会将异常引发到基本块终止符中,并向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块的实时值数). 要解决此问题,我们结合使用UpsilonPhiC (C代表catch ,在IR漂亮的打印机中写为φᶜ ,因为Unicode下标c不可用)的组合. 有多种方法可以考虑这些节点,但最简单的方法可能是将每个PhiC视为来自唯一的存储多次读取一次插槽的负载,而Upsilon是相应的存储操作. PhiC具有存储到其隐式插槽的所有upsilon节点的操作数列表. 但是, Upsilon节点不记录它们存储到哪个PhiC节点. 这样做是为了与SSA IR的其余部分更自然地集成. 例如,如果不再使用PhiC节点,则可以安全删除,并且Upsilon节点也是如此. 在大多数IR通道中,可以像对待Phi节点一样对待PhiC节点. 可以通过它们遵循use-def链,然后可以将它们提升到新的PhiC节点和新的Upsilon节点(与原始Upsilon节点位于同一位置). 该方案的结果是Upsilon节点(和PhiC参数)的数量与为特定变量分配的值的数量(在SSA转换之前)成比例,而不是与关键区域中的语句数量成比例.

要查看该方案的实际效果,请考虑以下功能

function foo()
    x = 1
    try
        y = 2
        error()
    catch
    end
    (x, y)
end

相应的IR(去除了无关类型)是:

ir = Code
1 ─       nothing
2 ─       $(Expr(:enter, 5))
3 ─ %3  = ϒ (#undef)
│   %4  = ϒ (1)
│   %5  = ϒ (2)
│         Main.bar()
│   %7  = ϒ (3)
└──       $(Expr(:leave, 1))
4 ─       goto 6
5 ─ %10 = φᶜ (%3, %5)
│   %11 = φᶜ (%4, %7)
└──       $(Expr(:leave, 1))
6 ┄ %13 = φ (4 => 2, 5 => %10)::NotInferenceDontLookHere.MaybeUndef(NotInferenceDontLookHere.Const(2, false))
│   %14 = φ (4 => 3, 5 => %11)::Int64
│         $(Expr(:undefcheck, :y, Core.SSAValue(13)))
│   %16 = Core.tuple(%14, %13)
└──       return %17

特别要注意的是,进入临界区的每个值都会在临界区的顶部获得upsilon节点. 这是因为认为catch块从函数外部具有不可见的控制流边缘. 结果,没有SSA值控制catch块,所有输入值都必须通过φᶜ节点.

Main SSA data structure

SSAIR的主要数据结构值得讨论. 它从LLVM和Webkit的B3 IR中获得启发. 数据结构的核心是语句的平面向量. 根据每个语句在向量中的位置,为每个语句隐式分配一个SSA值(即,可以使用SSAValue(1)等访问idx 1处的语句结果). 对于每个SSA值,我们还维护其类型. 由于SSA值在定义上仅分配一次,因此该类型也是相应索引处表达式的结果类型. 但是,虽然此表示形式非常有效(因为不需要显式分配),但是如果这样做当然会带来顺序上语义上很重要的缺点,因此重新排序和插入会更改语句编号. 此外,我们不保留使用列表(即,如果不显式计算此映射,就不可能从def转到其所有用途-def列表是微不足道的,因为您可以从索引中查找相应的语句),因此LLVM样式RAUW(全部替换)操作不可用.

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

compact! 该函数通过在适当位置执行节点插入,琐碎的复制传播以及将使用重命名为任何更改的SSA值来压缩上述数据结构. 但是,该方案的巧妙之处在于,可以将压实作为后续过程的一部分而懒惰地完成. 大多数优化过程需要遍历整个语句列表,一路执行分析或修改. 我们提供了一个IncrementalCompact迭代器,该迭代器可用于遍历语句列表. 它将执行任何必要的压缩,并返回节点的新索引以及节点本身. 此时,走走def-use链以及对IR进行任何修改或删除都是合法的(但是不允许插入).

这种安排背后的思想是,由于优化过程无论如何都需要触摸相应的内存并产生相应的内存访问损失,因此执行额外的内务处理应具有相对较小的开销(并节省了IR修改期间维护这些数据结构的开销) ).

by  ICOPY.SITE