"逃逸分析`
'核心。编译器。EscapeAnalysis’是一个编译器实用程序模块,旨在分析输出信息 IR SSA是Julia的一种形式,也称为`IRCode'。
这种逃逸分析的目的如下:
-
使用Julia的高级语义,使用进程间调用理解出口的操作和别名的分配;
-
具有足够的通用性,可用于各种优化,包括https://github.com/JuliaLang/julia/pull/43888 [sroa与别名支持],https://github.com/JuliaLang/julia/pull/44056 [预先插入"最后确定"],https://github.com/JuliaLang/julia/pull/42465 [在没有复制的情况下构建`ImmutableArray'],分配可变对象堆栈等。;
-
执行基于完全反向数据流分析的实现的简单实现,以及结合正交晶格的属性的新晶格设计。
试试吧!
您可以尝试通过下载脚本"EAUtils"来执行转义分析。jl',它标识合适的条目’code_escapes’和'@code_escapes’用于测试和调试。
julia> let JULIA_DIR = normpath(Sys.BINDIR, "..", "share", "julia")
# загружает модуль `EscapeAnalysis` для определения основного кода анализа
include(normpath(JULIA_DIR, "base", "compiler", "ssair", "EscapeAnalysis", "EscapeAnalysis.jl"))
using .EscapeAnalysis
# загружает `EAUtils` для определения служебных программ
include(normpath(JULIA_DIR, "test", "compiler", "EscapeAnalysis", "EAUtils.jl"))
using .EAUtils
end
julia> mutable struct SafeRef{T}
x::T
end
朱莉娅>基地。getindex(x::SafeRef)=x.x;
朱莉娅>基地。setindex!(x::SafeRef,v)=x.x=v;
朱莉娅>基地。isassigned(x::SafeRef)=true;
julia>get'(x)=isassigned(x)? x[]:投掷(x);
julia>result=code_escapes((String,String,String,String))do s1,s2,s3,s4
r1=Ref(s1)
r2=Ref(s2)
r3=SafeRef(s3)
试试
s1=得到'(r1)
ret=sizeof(s1)
抓住错误
global GV=err#肯定会退出'r1`
结束
s2=get'(r2)#仍然没有完全退出'r2`
s3=get'(r3)#仍未完全退出'r3`
S4=sizeof(s4)#参数's4'不在这里退出
返回s2,s3,s4
结束
#1(X s1::String,↑s2::String,↑s3::String,✓s4::String)在MAIN at REPL[7]:2
X1──%1=%new(Base.重新价值{String},_2)::基。重新价值{String}
*'│%2=%new(Base.重新价值{String},_3)::基。重新价值{String}
✓' └─── %3 = %新(主。安全,安全{String},_4)::主。安全,安全{String}
✓'2──%4=ϒ(%3)::Main.安全,安全{String}
*'│%5=ϒ(%2)::基数。重新价值{String}
✓│%6=ϒ(_5)::字符串
├──%7=输入#8
◌3──%8=基数。定义(%1,:x)::Bool
───转到#5如果不是%8
X4──基地。getfield(%1,:x)::字符串
───后藤第6号
<5──主.投掷(%1)::联合{}
──遥不可及
◌6──$(Expr(:leave,:(%7)))
│7──后藤#11
✓'8│─%16=φ│(%4)::Main.安全,安全{String}
*'│%17=φᶜ(%5)::基。重新价值{String}
✓=%18=φ=(%6)::弦
X├───%19=$(Expr(:the_exception))::Any
│9──无::无
№10─(主要。GV=%19)::任何
├───│(Expr(:pop_exception, :(%7)))::核心。Const(无)
✓'11÷%23=φ(#7 => %3, #10 => %16)::主要。安全,安全{String}
*'│%24=φ(#7 => %2, #10 => %17)::基地。重新价值{String}
✓<%25=φ(#7 => _5, #10 => %18)::字符串
◌ │%26=基数。定义(%24,:x)::Bool
───转到第13号,如果不是%26
↑12─%28=基数。getfield(%24,:x)::字符串
───后藤#14
№13─主。抛出(%24)::联合{}
──遥不可及
÷14─%32=基数。getfield(%23,:x)::字符串
◌ │%33=核心。大小(%25)::Int64
↑'│%34=核心。元组(%28, %32, %33)::元组{String, String, Int64}
──回报率%34
每个SSA调用参数和运算符侧面的符号具有以下含义。
-
'◌`(单色):不会分析此值,因为它的输出信息不会被使用(例如,当对象类型为`isbitstype’时)。
-
'✓'(绿色或蓝色):此值永远不会退出(包含`has_no_escape(结果。state[x])`)如果它也有一个参数输出(`has_arg_escape(result.态[x])'保存)。
-
'↑'(蓝色或黄色):此值可以通过return(contains`has_return_escape(result.state[x])
)如果它也有一个原始生成的输出(包含`has_thrown_escape(result.态[x])
)。 -
'X'(red):这个值可以去任何转义分析无法判断的地方,例如去全局内存(contains`has_all_escape(result.态[x])`)。
-
*
( 粗体字体):此值的输出状态在`ReturnEscape`和`AllEscape`之间,按部分顺序。 'EscapeInfo',如果它也有一个原始生成的输出(包含`has_thrown_escape(result.态[x])`)。 -
’:此值在其`AliasInfo`属性中有关于对象字段或数组元素的其他信息。
有关每个调用参数的输出和SSA值的信息可以通过编程方式进行检查,如下所示。
julia> result.state[Core.Argument(3)] # Получить EscapeInfo для `s2`
ReturnEscape
julia> result.state[Core.SSAValue(3)] # Получить EscapeInfo для `r3`
NoEscape′
分析的结构
网格设计
'EscapeAnalysis’实施为https://en.wikipedia.org/wiki/Data-flow_analysis [数据流分析]在网格中运行 'x::EscapeInfo`,它由以下属性组成。
这些属性可以组合起来创建一个有限高度的部分格,因为输入程序由于Julia语义而具有有限数量的运算符。 这种晶格设计最有趣的是,它允许单独处理每个晶格属性,从而更容易实现晶格操作。:LatticeDesign[在我们实现类型推断时,使用了一种替代方法,其中晶格的每个属性由晶格元素类型的特殊对象表示。 事实证明,他开始使晶格操作的实现复杂化,主要是因为他经常需要晶格元素类型的所有对象之间的变换规则。 我们正在努力https://github.com/JuliaLang/julia/pull/42596 [升级类型推理网格的实现]具有类似’EscapeInfo’的网格设计。].
反向输出的传播
逃逸分析的这种实现基于脚注:MM02[_A Graph-Free approach to Data-Flow Analysis_中描述的数据流算法。 Markas Mohnen,2002,4月。 https://api.semanticscholar.org/CorpusID:28519618 …]. 分析在EscapeInfo网格中工作,并从下到上通过网格元素,直到每个网格元素收敛于固定点,保留一个(概念)工作集,其中包含与待分析的剩余SSA运算符相对应的程 该分析管理跟踪每个SSA参数和语句的`EscapeInfo`的单个全局状态。 还要注意,对流的某些依赖性是以记录在`EscapeInfo`的`ReturnEscape’属性中的程序计数器的形式进行编码的,稍后可以结合支配分析来谈论对流的依赖性,如果需要的话。
这种转义分析的一个显着特征是它是完全可逆的,即有关输出的信息从用法到定义。 例如,在下面的代码片段中,EA首先分析’return%1’运算符并在`%1`上叠加`ReturnEscape`(对应于`obj`),然后分析`%1=%new(Base。重新价值{String, _2}))并将叠加在
%1`上的`ReturnEscape’扩展到调用参数'_2`(对应于`s')。
julia> code_escapes((String,)) do s
obj = Ref(s)
return obj
end
#3(↑ s::String) in Main at REPL[1]:2
↑′ 1 ─ %1 = %new(Base.RefValue{String}, _2)::Base.RefValue{String}
◌ └── return %1
一个重要的注意事项是,这种反向分析允许输出信息自然遵循"使用-定义"链,而不是执行顺序。:BackandForth[我们的类型推断算法,相反,被实现为直接分析,由于类型信息通常从定义到使用,因此将这些信息以直接的方式分发是更自然和有效的way.As 结果,该方案提供了逃逸分析的简单实现。 例如`可以通过简单地将与"PhiNode"相关的输出信息扩展到其前身的值来处理"PhiNode"。
julia> code_escapes((Bool, String, String)) do cnd, s, t
if cnd
obj = Ref(s)
else
obj = Ref(t)
end
return obj
end
#5(✓ cnd::Bool, ↑ s::String, ↑ t::String) in Main at REPL[1]:2
◌ 1 ─ goto #3 if not _2
↑′ 2 ─ %2 = %new(Base.RefValue{String}, _3)::Base.RefValue{String}
◌ └── goto #4
↑′ 3 ─ %4 = %new(Base.RefValue{String}, _4)::Base.RefValue{String}
↑′ 4 ┄ %5 = φ (#2 => %2, #3 => %4)::Base.RefValue{String}
◌ └── return %5
别名分析
'EscapeAnalysis’实现了反向字段分析,以便以一定的精度推理与对象字段相关的输入输出;为此,在`x::EscapeInfo`中有一个属性`x.AliasInfo`。 它记录了可以分配给使用地点的字段`x`的所有可能值,然后将有关这些记录值输出的信息分发给定义地点的字段的实际值。 更具体地说,分析记录了一个值,该值可以在分析`getfield`调用时作为别名分配给对象字段,然后在分析表达式'%new(时将其输出信息分发给字段。..)'或调用’setfield!'脚注:动态[然而,在某些情况下,对象的字段无法准确分析。 例如,一个对象可能会去到一个无法考虑内存对其可能影响的地方,或者由于缺乏类型信息,对象的字段可能只是未知。 在这种情况下,`AliasInfo’属性上升到其自己的晶格顺序内的最顶层元素,这导致更保守的后续场分析,并且与非分析对象的场相关的输出信息被分发到对象本身。].
julia> code_escapes((String,)) do s
obj = SafeRef("init")
obj[] = s
v = obj[]
return v
end
#7(↑ s::String) in Main at REPL[1]:2
◌ 1 ─ return _2
在上面的例子中,复盖在`%3`上的`ReturnEscape`(对应于`v`)不会直接扩展到`%1`(对应于`obj`),而是`ReturnEscape`仅扩展到`_2`(对应于`s')。 在这里’%3’被写入`%1`的’AliasInfo’属性,因为它可以作为别名分配给第一个字段`%1`,然后在分析`Base时。塞特菲尔德!(%1,:x,_2)::String`,此输出信息分发给`_2`,但不是由`%1’分发。
这就是`EscapeAnalysis’如何跟踪哪些IR元素可以在链`getfield`-%new
/setfield中被别名!分析对象字段的输出,但实际上这种别名分析也应该被推广到处理其他IR元素。 这是因为在IR元素中,同一个对象有时由不同的IR元素表示,因此必须确保这些实际上可以表示同一个对象的不同IR元素具有相同的输出信息。 返回与其操作数相同的对象的IR元素,例如`PiNode`和`typeassert
,可能导致IR级别的混叠,因此要求在它们之间共享有关任何此类混叠值的输出信息。 更有趣的是,正确理解`PhiNode`的变化也是必要的。 考虑以下示例。
julia> code_escapes((Bool, String,)) do cond, x
if cond
ϕ2 = ϕ1 = SafeRef("foo")
else
ϕ2 = ϕ1 = SafeRef("bar")
end
ϕ2[] = x
y = ϕ1[]
return y
end
#9(✓ cond::Bool, ↑ x::String) in Main at REPL[1]:2
◌ 1 ─ goto #3 if not _2
✓′ 2 ─ %2 = %new(Main.SafeRef{String}, "foo")::Main.SafeRef{String}
◌ └── goto #4
✓′ 3 ─ %4 = %new(Main.SafeRef{String}, "bar")::Main.SafeRef{String}
✓′ 4 ┄ %5 = φ (#2 => %2, #3 => %4)::Main.SafeRef{String}
✓′ │ %6 = φ (#2 => %2, #3 => %4)::Main.SafeRef{String}
◌ │ Base.setfield!(%5, :x, _3)::String
↑ │ %8 = Base.getfield(%6, :x)::String
◌ └── return %8
ϕ1=%5`和`ϕ2=%6`被分配别名,因此`ReturnEscape`复盖在'%8=Base上。getfield(%6,:x)::String
(对应`y=ϕ1[]),应该扩展为`Base。塞特菲尔德!(%5,:x,_3)::String
(对应`ϕ2[]=x`)。 为了使这样的输出信息正确地分布,分析必须理解`〇1’和`〇2’也可以被分配别名,并且均衡它们的输出信息。
关于别名的赋值的此类信息的一个有趣属性是,它在使用地点未知,但只能在定义地点获得(因为别名在概念上等同于赋值);因此,它不适合反向分析。 要在相关值之间有效地分发退出信息,请执行分析。jl使用了一种基于jvmfootnote上的一篇旧论文中描述的逃逸分析算法的方法:Jvm05[escape Analysis in The Context Of Dynamic Compilation and Deoptimization. Thomas Kotzmann和Hanspeter Mössenböck,2005,6月。 https://dl.acm.org/doi/10.1145/1064979.1064996 也就是说,除了控制出口网格的元素之外,分析还支持一组等效别名-一组不相关的SSA参数和具有分配别名的运算符。 一组别名控制可以作为别名分配给彼此的值,并允许它们将叠加在任何此类值上的输出信息与别名对齐。
阵列分析
上面描述的对象字段别名的分析也可以推广到分析具有数组的操作。 'EscapeAnalysis’实现了对各种原始数组操作的处理,以便它可以通过`arrayref`-`arrayset’的use-definition链分发输出,而不是过于保守地退出分配的数组。
julia> code_escapes((String,)) do s
ary = Any[]
push!(ary, SafeRef(s))
return ary[1], length(ary)
end
#11(X s::String) in Main at REPL[1]:2
X 1 ── %1 = Core.getproperty(Memory{Any}, :instance)::Memory{Any}
X │ %2 = invoke Core.memoryref(%1::Memory{Any})::MemoryRef{Any}
X │ %3 = %new(Vector{Any}, %2, (0,))::Vector{Any}
X │ %4 = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
X │ %5 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %6 = Base.getfield(%5, :mem)::Memory{Any}
X │ %7 = Base.getfield(%6, :length)::Int64
X │ %8 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %9 = $(Expr(:boundscheck, true))::Bool
X │ %10 = Base.getfield(%8, 1, %9)::Int64
◌ │ %11 = Base.add_int(%10, 1)::Int64
◌ │ %12 = Base.memoryrefoffset(%5)::Int64
X │ %13 = Core.tuple(%11)::Tuple{Int64}
◌ │ Base.setfield!(%3, :size, %13)::Tuple{Int64}
◌ │ %15 = Base.add_int(%12, %11)::Int64
◌ │ %16 = Base.sub_int(%15, 1)::Int64
◌ │ %17 = Base.slt_int(%7, %16)::Bool
◌ └─── goto #3 if not %17
X 2 ── %19 = %new(Base.var"#133#134"{Vector{Any}, Int64, Int64, Int64, Int64, Int64, Memory{Any}, MemoryRef{Any}}, %3, %16, %12, %11, %10, %7, %6, %5)::Base.var"#133#134"{Vector{Any}, Int64, Int64, Int64, Int64, Int64, Memory{Any}, MemoryRef{Any}}
✓ └─── invoke %19()::MemoryRef{Any}
◌ 3 ┄─ goto #4
X 4 ── %22 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %23 = $(Expr(:boundscheck, true))::Bool
X │ %24 = Base.getfield(%22, 1, %23)::Int64
X │ %25 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %26 = Base.memoryrefnew(%25, %24, false)::MemoryRef{Any}
X │ Base.memoryrefset!(%26, %4, :not_atomic, false)::Main.SafeRef{String}
◌ └─── goto #5
◌ 5 ── %29 = $(Expr(:boundscheck, true))::Bool
◌ └─── goto #9 if not %29
◌ 6 ── %31 = Base.sub_int(1, 1)::Int64
◌ │ %32 = Base.bitcast(Base.UInt, %31)::UInt64
X │ %33 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %34 = $(Expr(:boundscheck, true))::Bool
X │ %35 = Base.getfield(%33, 1, %34)::Int64
◌ │ %36 = Base.bitcast(Base.UInt, %35)::UInt64
◌ │ %37 = Base.ult_int(%32, %36)::Bool
◌ └─── goto #8 if not %37
◌ 7 ── goto #9
◌ 8 ── %40 = Core.tuple(1)::Tuple{Int64}
✓ │ invoke Base.throw_boundserror(%3::Vector{Any}, %40::Tuple{Int64})::Union{}
◌ └─── unreachable
X 9 ┄─ %43 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %44 = Base.memoryrefnew(%43, 1, false)::MemoryRef{Any}
X │ %45 = Base.memoryrefget(%44, :not_atomic, false)::Any
◌ └─── goto #10
X 10 ─ %47 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %48 = $(Expr(:boundscheck, true))::Bool
X │ %49 = Base.getfield(%47, 1, %48)::Int64
↑′ │ %50 = Core.tuple(%45, %49)::Tuple{Any, Int64}
◌ └─── return %50
在上面的示例中,'EscapeAnalysis’理解`%20`和`%2`(对应于选定的对象`SafeRef(s))别名是通过`arrayset
-arrayref`链分配的,并在它们上复盖`ReturnEscape
,但不会将其复盖在分配的数组`%1`(对应于`ary')上。 'EscapeAnalysis’仍然在`ary`上复盖`ThrownEscape`,因为它还需要考虑通过`BoundsError’的潜在退出。 还要注意,在优化`ary’的分配时,通常可以忽略这种原始的’ThrownEscape'。
此外,在可以精确知道有关数组索引及其维度的信息的情况下,EscapeAnalysis甚至可以通过arrayref-arrayset链谈论别名的零碎分配,因为EscapeAnalysis分析对象的每个字段的别名分配。
julia> code_escapes((String,String)) do s, t
ary = Vector{Any}(undef, 2)
ary[1] = SafeRef(s)
ary[2] = SafeRef(t)
return ary[1], length(ary)
end
#13(X s::String, X t::String) in Main at REPL[1]:2
X 1 ── %1 = $(Expr(:foreigncall, :(:jl_alloc_genericmemory), Ref{Memory{Any}}, svec(Any, Int64), 0, :(:ccall), Memory{Any}, 2, 2))::Memory{Any}
X │ %2 = Core.memoryrefnew(%1)::MemoryRef{Any}
X │ %3 = %new(Vector{Any}, %2, (2,))::Vector{Any}
X │ %4 = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
◌ │ %5 = $(Expr(:boundscheck, true))::Bool
◌ └─── goto #5 if not %5
◌ 2 ── %7 = Base.sub_int(1, 1)::Int64
◌ │ %8 = Base.bitcast(Base.UInt, %7)::UInt64
X │ %9 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %10 = $(Expr(:boundscheck, true))::Bool
X │ %11 = Base.getfield(%9, 1, %10)::Int64
◌ │ %12 = Base.bitcast(Base.UInt, %11)::UInt64
◌ │ %13 = Base.ult_int(%8, %12)::Bool
◌ └─── goto #4 if not %13
◌ 3 ── goto #5
◌ 4 ── %16 = Core.tuple(1)::Tuple{Int64}
✓ │ invoke Base.throw_boundserror(%3::Vector{Any}, %16::Tuple{Int64})::Union{}
◌ └─── unreachable
X 5 ┄─ %19 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %20 = Base.memoryrefnew(%19, 1, false)::MemoryRef{Any}
X │ Base.memoryrefset!(%20, %4, :not_atomic, false)::Main.SafeRef{String}
◌ └─── goto #6
X 6 ── %23 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
◌ │ %24 = $(Expr(:boundscheck, true))::Bool
◌ └─── goto #10 if not %24
◌ 7 ── %26 = Base.sub_int(2, 1)::Int64
◌ │ %27 = Base.bitcast(Base.UInt, %26)::UInt64
X │ %28 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %29 = $(Expr(:boundscheck, true))::Bool
X │ %30 = Base.getfield(%28, 1, %29)::Int64
◌ │ %31 = Base.bitcast(Base.UInt, %30)::UInt64
◌ │ %32 = Base.ult_int(%27, %31)::Bool
◌ └─── goto #9 if not %32
◌ 8 ── goto #10
◌ 9 ── %35 = Core.tuple(2)::Tuple{Int64}
✓ │ invoke Base.throw_boundserror(%3::Vector{Any}, %35::Tuple{Int64})::Union{}
◌ └─── unreachable
X 10 ┄ %38 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %39 = Base.memoryrefnew(%38, 2, false)::MemoryRef{Any}
X │ Base.memoryrefset!(%39, %23, :not_atomic, false)::Main.SafeRef{String}
◌ └─── goto #11
◌ 11 ─ %42 = $(Expr(:boundscheck, true))::Bool
◌ └─── goto #15 if not %42
◌ 12 ─ %44 = Base.sub_int(1, 1)::Int64
◌ │ %45 = Base.bitcast(Base.UInt, %44)::UInt64
X │ %46 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %47 = $(Expr(:boundscheck, true))::Bool
X │ %48 = Base.getfield(%46, 1, %47)::Int64
◌ │ %49 = Base.bitcast(Base.UInt, %48)::UInt64
◌ │ %50 = Base.ult_int(%45, %49)::Bool
◌ └─── goto #14 if not %50
◌ 13 ─ goto #15
◌ 14 ─ %53 = Core.tuple(1)::Tuple{Int64}
✓ │ invoke Base.throw_boundserror(%3::Vector{Any}, %53::Tuple{Int64})::Union{}
◌ └─── unreachable
X 15 ┄ %56 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %57 = Base.memoryrefnew(%56, 1, false)::MemoryRef{Any}
X │ %58 = Base.memoryrefget(%57, :not_atomic, false)::Any
◌ └─── goto #16
X 16 ─ %60 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %61 = $(Expr(:boundscheck, true))::Bool
X │ %62 = Base.getfield(%60, 1, %61)::Int64
↑′ │ %63 = Core.tuple(%58, %62)::Tuple{Any, Int64}
◌ └─── return %63
请注意,'ReturnEscape’仅适用于`%2`(对应于`SafeRef(s)),但不适用于
%4`(对应于`SafeRef(t))。 这是因为分配数组的维数和所有arrayref/arrayset操作中涉及的索引作为永久信息可用,并且EscapeAnalysis可以理解%6已被分配别名%2,但永远不会被分配别名%4。 在这种情况下,随后的优化传递将能够替换’Base。arrayref(true,%1,1)::Any`with
%2`(所谓的负载转发)并最终完全消除数组`%1`的分配(所谓的标量替换)。
与分析对象的字段相比,可以使用推理获得的类型信息对字段的访问进行琐碎分析,数组的维度不被编码为类型信息,因此我们需要额外的分析来获得 在这一点上,EscapeAnalysis首先执行额外的简单线性扫描,以在运行主分析程序之前分析分配的阵列的测量值,以便随后的escapeanalysis能够精确地分析具有这些阵列的操作。
然而,对假名进行如此准确的零碎分析往往是困难的。 实际上,数组固有的主要困难是数组的维度和索引往往不一致。
-
循环通常会生成在循环中可变的非永久性数组索引。
-
这对于向量来说是典型的:改变数组的大小会改变数组的维数并违反其恒定性。
让我们用具体的例子来讨论这些困难。
在以下示例中,'EscapeAnalysis’无法进行准确的别名分析,因为索引位于'Base中。arrayset(错误, %4, %8, %6)::向量资料{Any}'不是(平凡的)常数。 特别是,'Any[nothing,nothing]'形成一个循环,并在循环中调用`arrayset`操作,其中'%6’表示为ϕ节点的值(其值取决于执行顺序)。 结果’ReturnEscape’最终复盖在`%23`(对应于`SafeRef(s))和
%25`(对应于`SafeRef(t)')上,尽管理想情况下它应该只复盖在`%23`上,而不是复盖在`%25`上。
julia> code_escapes((String,String)) do s, t
ary = Any[nothing, nothing]
ary[1] = SafeRef(s)
ary[2] = SafeRef(t)
return ary[1], length(ary)
end
#15(X s::String, X t::String) in Main at REPL[1]:2
X 1 ── %1 = $(Expr(:foreigncall, :(:jl_alloc_genericmemory), Ref{Memory{Any}}, svec(Any, Int64), 0, :(:ccall), Memory{Any}, 2, 2))::Memory{Any}
X │ %2 = Core.memoryrefnew(%1)::MemoryRef{Any}
X └─── %3 = %new(Vector{Any}, %2, (2,))::Vector{Any}
◌ 2 ┄─ %4 = φ (#1 => 1, #6 => %14)::Int64
◌ │ %5 = φ (#1 => 1, #6 => %15)::Int64
X │ %6 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %7 = Base.memoryrefnew(%6, %4, false)::MemoryRef{Any}
◌ │ Base.memoryrefset!(%7, nothing, :not_atomic, false)::Nothing
◌ │ %9 = (%5 === 2)::Bool
◌ └─── goto #4 if not %9
◌ 3 ── goto #5
◌ 4 ── %12 = Base.add_int(%5, 1)::Int64
◌ └─── goto #5
◌ 5 ┄─ %14 = φ (#4 => %12)::Int64
◌ │ %15 = φ (#4 => %12)::Int64
◌ │ %16 = φ (#3 => true, #4 => false)::Bool
◌ │ %17 = Base.not_int(%16)::Bool
◌ └─── goto #7 if not %17
◌ 6 ── goto #2
◌ 7 ── goto #8
X 8 ── %21 = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
◌ │ %22 = $(Expr(:boundscheck, true))::Bool
◌ └─── goto #12 if not %22
◌ 9 ── %24 = Base.sub_int(1, 1)::Int64
◌ │ %25 = Base.bitcast(Base.UInt, %24)::UInt64
X │ %26 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %27 = $(Expr(:boundscheck, true))::Bool
X │ %28 = Base.getfield(%26, 1, %27)::Int64
◌ │ %29 = Base.bitcast(Base.UInt, %28)::UInt64
◌ │ %30 = Base.ult_int(%25, %29)::Bool
◌ └─── goto #11 if not %30
◌ 10 ─ goto #12
◌ 11 ─ %33 = Core.tuple(1)::Tuple{Int64}
✓ │ invoke Base.throw_boundserror(%3::Vector{Any}, %33::Tuple{Int64})::Union{}
◌ └─── unreachable
X 12 ┄ %36 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %37 = Base.memoryrefnew(%36, 1, false)::MemoryRef{Any}
X │ Base.memoryrefset!(%37, %21, :not_atomic, false)::Main.SafeRef{String}
◌ └─── goto #13
X 13 ─ %40 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
◌ │ %41 = $(Expr(:boundscheck, true))::Bool
◌ └─── goto #17 if not %41
◌ 14 ─ %43 = Base.sub_int(2, 1)::Int64
◌ │ %44 = Base.bitcast(Base.UInt, %43)::UInt64
X │ %45 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %46 = $(Expr(:boundscheck, true))::Bool
X │ %47 = Base.getfield(%45, 1, %46)::Int64
◌ │ %48 = Base.bitcast(Base.UInt, %47)::UInt64
◌ │ %49 = Base.ult_int(%44, %48)::Bool
◌ └─── goto #16 if not %49
◌ 15 ─ goto #17
◌ 16 ─ %52 = Core.tuple(2)::Tuple{Int64}
✓ │ invoke Base.throw_boundserror(%3::Vector{Any}, %52::Tuple{Int64})::Union{}
◌ └─── unreachable
X 17 ┄ %55 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %56 = Base.memoryrefnew(%55, 2, false)::MemoryRef{Any}
X │ Base.memoryrefset!(%56, %40, :not_atomic, false)::Main.SafeRef{String}
◌ └─── goto #18
◌ 18 ─ %59 = $(Expr(:boundscheck, true))::Bool
◌ └─── goto #22 if not %59
◌ 19 ─ %61 = Base.sub_int(1, 1)::Int64
◌ │ %62 = Base.bitcast(Base.UInt, %61)::UInt64
X │ %63 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %64 = $(Expr(:boundscheck, true))::Bool
X │ %65 = Base.getfield(%63, 1, %64)::Int64
◌ │ %66 = Base.bitcast(Base.UInt, %65)::UInt64
◌ │ %67 = Base.ult_int(%62, %66)::Bool
◌ └─── goto #21 if not %67
◌ 20 ─ goto #22
◌ 21 ─ %70 = Core.tuple(1)::Tuple{Int64}
✓ │ invoke Base.throw_boundserror(%3::Vector{Any}, %70::Tuple{Int64})::Union{}
◌ └─── unreachable
X 22 ┄ %73 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %74 = Base.memoryrefnew(%73, 1, false)::MemoryRef{Any}
X │ %75 = Base.memoryrefget(%74, :not_atomic, false)::Any
◌ └─── goto #23
X 23 ─ %77 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %78 = $(Expr(:boundscheck, true))::Bool
X │ %79 = Base.getfield(%77, 1, %78)::Int64
↑′ │ %80 = Core.tuple(%75, %79)::Tuple{Any, Int64}
◌ └─── return %80
下面的示例显示了如何更改向量的大小使得难以准确分析别名。 一个显着的困难在于分配数组"%1"的维度首先被初始化为"0",但随后被两次调用更改为":jl_array_grow_end"。 目前,'EscapeAnalysis’在面对数组大小调整操作时简单地拒绝准确分析别名,因此`ReturnEscape`被复盖为`%2`(对应于`SafeRef(s)),并被
%20`(对应于`SafeRef(t)`)。
julia> code_escapes((String,String)) do s, t
ary = Any[]
push!(ary, SafeRef(s))
push!(ary, SafeRef(t))
ary[1], length(ary)
end
#17(X s::String, X t::String) in Main at REPL[1]:2
X 1 ── %1 = Core.getproperty(Memory{Any}, :instance)::Memory{Any}
X │ %2 = invoke Core.memoryref(%1::Memory{Any})::MemoryRef{Any}
X │ %3 = %new(Vector{Any}, %2, (0,))::Vector{Any}
X │ %4 = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
X │ %5 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %6 = Base.getfield(%5, :mem)::Memory{Any}
X │ %7 = Base.getfield(%6, :length)::Int64
X │ %8 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %9 = $(Expr(:boundscheck, true))::Bool
X │ %10 = Base.getfield(%8, 1, %9)::Int64
◌ │ %11 = Base.add_int(%10, 1)::Int64
◌ │ %12 = Base.memoryrefoffset(%5)::Int64
X │ %13 = Core.tuple(%11)::Tuple{Int64}
◌ │ Base.setfield!(%3, :size, %13)::Tuple{Int64}
◌ │ %15 = Base.add_int(%12, %11)::Int64
◌ │ %16 = Base.sub_int(%15, 1)::Int64
◌ │ %17 = Base.slt_int(%7, %16)::Bool
◌ └─── goto #3 if not %17
X 2 ── %19 = %new(Base.var"#133#134"{Vector{Any}, Int64, Int64, Int64, Int64, Int64, Memory{Any}, MemoryRef{Any}}, %3, %16, %12, %11, %10, %7, %6, %5)::Base.var"#133#134"{Vector{Any}, Int64, Int64, Int64, Int64, Int64, Memory{Any}, MemoryRef{Any}}
✓ └─── invoke %19()::MemoryRef{Any}
◌ 3 ┄─ goto #4
X 4 ── %22 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %23 = $(Expr(:boundscheck, true))::Bool
X │ %24 = Base.getfield(%22, 1, %23)::Int64
X │ %25 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %26 = Base.memoryrefnew(%25, %24, false)::MemoryRef{Any}
X │ Base.memoryrefset!(%26, %4, :not_atomic, false)::Main.SafeRef{String}
◌ └─── goto #5
X 5 ── %29 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
X │ %30 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %31 = Base.getfield(%30, :mem)::Memory{Any}
X │ %32 = Base.getfield(%31, :length)::Int64
X │ %33 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %34 = $(Expr(:boundscheck, true))::Bool
X │ %35 = Base.getfield(%33, 1, %34)::Int64
◌ │ %36 = Base.add_int(%35, 1)::Int64
◌ │ %37 = Base.memoryrefoffset(%30)::Int64
X │ %38 = Core.tuple(%36)::Tuple{Int64}
◌ │ Base.setfield!(%3, :size, %38)::Tuple{Int64}
◌ │ %40 = Base.add_int(%37, %36)::Int64
◌ │ %41 = Base.sub_int(%40, 1)::Int64
◌ │ %42 = Base.slt_int(%32, %41)::Bool
◌ └─── goto #7 if not %42
X 6 ── %44 = %new(Base.var"#133#134"{Vector{Any}, Int64, Int64, Int64, Int64, Int64, Memory{Any}, MemoryRef{Any}}, %3, %41, %37, %36, %35, %32, %31, %30)::Base.var"#133#134"{Vector{Any}, Int64, Int64, Int64, Int64, Int64, Memory{Any}, MemoryRef{Any}}
✓ └─── invoke %44()::MemoryRef{Any}
◌ 7 ┄─ goto #8
X 8 ── %47 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %48 = $(Expr(:boundscheck, true))::Bool
X │ %49 = Base.getfield(%47, 1, %48)::Int64
X │ %50 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %51 = Base.memoryrefnew(%50, %49, false)::MemoryRef{Any}
X │ Base.memoryrefset!(%51, %29, :not_atomic, false)::Main.SafeRef{String}
◌ └─── goto #9
◌ 9 ── %54 = $(Expr(:boundscheck, true))::Bool
◌ └─── goto #13 if not %54
◌ 10 ─ %56 = Base.sub_int(1, 1)::Int64
◌ │ %57 = Base.bitcast(Base.UInt, %56)::UInt64
X │ %58 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %59 = $(Expr(:boundscheck, true))::Bool
X │ %60 = Base.getfield(%58, 1, %59)::Int64
◌ │ %61 = Base.bitcast(Base.UInt, %60)::UInt64
◌ │ %62 = Base.ult_int(%57, %61)::Bool
◌ └─── goto #12 if not %62
◌ 11 ─ goto #13
◌ 12 ─ %65 = Core.tuple(1)::Tuple{Int64}
✓ │ invoke Base.throw_boundserror(%3::Vector{Any}, %65::Tuple{Int64})::Union{}
◌ └─── unreachable
X 13 ┄ %68 = Base.getfield(%3, :ref)::MemoryRef{Any}
X │ %69 = Base.memoryrefnew(%68, 1, false)::MemoryRef{Any}
X │ %70 = Base.memoryrefget(%69, :not_atomic, false)::Any
◌ └─── goto #14
X 14 ─ %72 = Base.getfield(%3, :size)::Tuple{Int64}
◌ │ %73 = $(Expr(:boundscheck, true))::Bool
X │ %74 = Base.getfield(%72, 1, %73)::Int64
↑′ │ %75 = Core.tuple(%70, %74)::Tuple{Any, Int64}
◌ └─── return %75
为了解决这些问题,输出需要知道数组维度,并将它们分布在一个依赖于顺序的wayfootnote:ArrayDimension[否则,我们将需要另一个基于转义分析的直接数据流分析。],并且还确定了循环变量值的正确表示。
此时,EscapeAnalysis快速切换到更不精确的分析,该分析在数组维度或索引是微不足道变量的情况下不跟踪有关索引的准确信息。 切换可以自然地实现为`EscapeInfo的电网连接操作。AliasInfo的属性作为数据流分析的一部分。
异常处理
同样值得关注的是,EscapeAnalysis如何通过异常处理可能的退出。 认为将叠加在对象`:the_exception`上的输出信息扩展到相应的’try`块中可能出现的所有值就足够了,这是天真的。 实际上,Julia还有其他几种访问异常对象的方法,例如`Base。current_exceptions’和’rethrow'。 例如,逃逸分析应考虑下面示例中`r’的潜在输出。
julia> const GR = Ref{Any}();
julia> @noinline function rethrow_escape!()
try
rethrow()
catch err
GR[] = err
end
end;
julia>get'(x)=isassigned(x)? x[]:投掷(x);
朱莉娅>code_escapes()做
r=Ref{String}()
本地t
试试
t=得到'(r)
抓住错误
t=typeof(err)#'err'(其别名为'r`)在这里不起作用
重新思考!()#但是"r"来了
结束
返回t
结束
#19()In Main at REPL[4]:2
X1─%1=%new(Base.重新价值{String})::基地。重新价值{String}
◌2─%2=输入#8
◌3─%3=基数。定义(%1,:x)::Bool
──goto#5如果不是%3
X4─%5=基数。getfield(%1,:x)::字符串
──后藤#6
↑5─主。投掷(%1)::联合{}
──遥不可及
◌6─$(Expr(:leave,:(%2)))
◌7─后藤#9
✓8┄%11=$(Expr(:the_exception))::任何
X÷%12=主要。类型(%11)::数据类型
调用主。重新思考!()::任何
├──│(Expr(:pop_exception, :(%2)))::核心。Const(无)
X9÷%15=φ(#7 => %5, #8 => %12)::工会{DataType, String}
──回报%15
要正确理解通过现有异常接口的所有可能退出,需要进行全局分析。 目前,我们总是保守地将有关输出的最重要信息分发给潜在发生异常的所有对象,因为考虑到异常处理和错误路径通常不应太依赖性能,这样的额外分析可能是不可取的。 此外,优化错误路径可能非常低效,因为它们通常甚至不是出于延迟的原因故意优化的。
属性’x::EscapeInfo’x.ThrownEscape’记录SSA语句,其中`x’可以作为异常调用。 使用此信息,EscapeAnalysis可以通过异常传播可能的退出,仅限于try的每个区域中可能发生的退出。
julia> result = code_escapes((String,String)) do s1, s2
r1 = Ref(s1)
r2 = Ref(s2)
local ret
try
s1 = get′(r1)
ret = sizeof(s1)
catch err
global GV = err # обязательно выйдет из `r1`
end
s2 = get′(r2) # все еще не полностью выходит из `r2`
return s2
end
#21(X s1::String, ↑ s2::String) in Main at REPL[1]:2
X 1 ── %1 = %new(Base.RefValue{String}, _2)::Base.RefValue{String}
*′ └─── %2 = %new(Base.RefValue{String}, _3)::Base.RefValue{String}
*′ 2 ── %3 = ϒ (%2)::Base.RefValue{String}
◌ └─── %4 = enter #8
◌ 3 ── %5 = Base.isdefined(%1, :x)::Bool
◌ └─── goto #5 if not %5
X 4 ── Base.getfield(%1, :x)::String
◌ └─── goto #6
◌ 5 ── Main.throw(%1)::Union{}
◌ └─── unreachable
◌ 6 ── $(Expr(:leave, :(%4)))
◌ 7 ── goto #11
*′ 8 ┄─ %13 = φᶜ (%3)::Base.RefValue{String}
X └─── %14 = $(Expr(:the_exception))::Any
◌ 9 ── nothing::Nothing
◌ 10 ─ (Main.GV = %14)::Any
◌ └─── $(Expr(:pop_exception, :(%4)))::Core.Const(nothing)
*′ 11 ┄ %18 = φ (#7 => %2, #10 => %13)::Base.RefValue{String}
◌ │ %19 = Base.isdefined(%18, :x)::Bool
◌ └─── goto #13 if not %19
↑ 12 ─ %21 = Base.getfield(%18, :x)::String
◌ └─── goto #14
◌ 13 ─ Main.throw(%18)::Union{}
◌ └─── unreachable
◌ 14 ─ return %21
使用分析
"Analyze_escapes"是分析SSA-IR元素输出信息的入口点。
大多数优化,如SROA('sroa_pass!在嵌入过程中被简化的优化源(ssa_inlining_pass!`)通过解析进程间调用并扩展被调用对象的源。 因此,'analyze_escapes’还可以分析IR嵌入后的结果并收集有关输出的信息,这对于某些与内存相关的优化很有用。
然而,由于一些优化过程,例如嵌入,可以改变执行顺序并消除非工作代码,它们可以破坏输出信息的进程间可靠性。 特别是,为了收集关于输出的可接受的过程间信息,有必要分析IR的预嵌入。
出于这个原因,函数"analyze_escapes"可以在Julia级别的优化的任何阶段分析"IRCode",特别是,它应该在接下来的两个阶段中使用。
-
"EA IPO":分析IR的预嵌入以创建有效的进程间输出信息缓存
-
"本地EA":分析IR嵌入后的结果,以收集本地有效的输出信息
使用’IPO EA’获得的输出信息转换为’ArgEscapeCache’数据结构并全局缓存。 通过将适当的`get_escape_cache`回调传递给`analyze_escapes`函数,转义分析可以通过使用在之前的’IPO EA`分析期间获得的有关非嵌入可调用对象的缓存进程间信息来提高分析 更有趣的是,使用有关"IPO EA"输出的信息进行类型推断也是可以接受的。 例如,可以通过形成`Const`/PartialStruct
/`MustAlias’可变对象来提高输出的准确性。
# ’核心。编译器。逃逸分析。analyze_escapes'*-Function
analyze_escapes(ir::IRCode, nargs::Int, get_escape_cache) -> estate::EscapeState
分析有关输出到"ir`的信息:
-
'nargs`:分析调用的实际参数数
-
'get_escape_cache(::MethodInstance)->联合{Bool,ArgEscapeCache}`:获取有关参数输出的缓存信息
# ’核心。编译器。逃逸分析。EscapeState'*—Type
estate::EscapeState
将SSA参数和值映射到输出信息的扩展网格,显示为 'EscapeInfo'。 与IR SSA元素’x’相关的输出信息可以使用’estate[x]'获得。
# '核心。编译器。逃逸分析。EscapeInfo'—Type
x::EscapeInfo
具有以下属性的退出信息网格:
-
'X.Analyzed::Bool':不是形式上的格子的一部分,只表示`x`是否被分析过
-
'X.ReturnEscape::Bool':表示’x’可以通过return传递给调用者
-
`x.ThrownEscape::BitSet':记录可以将`x`作为异常调用的SSA运算符编号: 'isempty(x.ThrownEscape)':`x’永远不会在这个调用框架中被调用(底部) 'pc∈x.ThrownEscape'’x`可以在`pc’中的SSA运算符中调用 **'-1∈x.ThrownEscape'’x’可以在此调用帧(上部)中的任意点调用。 此信息将被`escape_exception!'通过异常传播潜在的退出。
-
'x.AliasInfo::联合{Bool,IndexableFields,IndexableElements,Unindexable}':存储所有可能的值,这些值可以是数组`x`的字段或元素的别名: 'x.AliasInfo===false’表示尚未分析’x’的字段或元素 'x.AliasInfo===true’表示无法分析’x’的字段或元素,例如,`x`的类型未知或未指定,因此无法准确地知道其字段或元素 `x.AliasInfo::IndexableFields’记录所有可能的值,这些值可以是对象`x’的字段的别名,并提供有关索引的准确信息 'x.AliasInfo::IndexableElements’记录所有可能的值,这些值可以是数组元素`x`的别名,并提供有关索引的准确信息 **'x.AliasInfo::`Unindexable’记录所有可能的值,可以是字段的别名或`x`的元素,并提供有关索引的准确信息。
-
'X.Liveness::BitSet':记录`x`可以位于的SSA运算符编号,例如,用作调用参数,返回给调用方,或存储为`:foreigncall`: 'isempty(x.Liveness)':`x’永远不会在这个框架中使用(底部) '0∈x.Liveness’还有一个特殊的含义,即它是当前分析的调用帧的调用参数(因此它对调用者立即可见)。 'pc∈x.Liveness':`x`可以在’pc’中的SSA运算符中使用 '-1∈x.Liveness'’x’可以在这个调用框架中的任意点使用(上部)
有实用程序构造函数用于创建常见的’EscapeInfo’类型。 例如:
-
'NoEscape()':这个网格的底部元素,这意味着它不会去任何地方。
-
'AllEscape(’:此网格的最顶层元素,这意味着它将在任何地方消失
'analyze_escapes’将按照Julia自己的类型推断例程的相同方向从下到上翻译这些元素。 抽象状态将由较低的元素初始化:
-
调用参数初始化为’ArgEscape()`,其中的`Liveness`属性包括'0’以指示它作为调用参数传递,并且从调用对象立即可见。;
-
其余的状态被初始化为`NotAnalyzed()',这是晶格的一个特殊元素,略低于`NoEscape`,但与此同时不代表任何意义,除了它尚未被分析(因此,形式上它不是晶格的一部分)。