`EscapeAnalysis`

Core.Compiler.EscapeAnalysis 是一个编译器实用模块，旨在分析 Julia's SSA-form IR 也就是 IRCode 的逃逸信息。

此逃逸分析旨在：

利用Julia的高级语义，特别是通过跨过程调用来推理逃逸和别名。
足够灵活，可以用于各种优化，包括 alias-aware SROA、early finalize insertion、copy-free ImmutableArray construction、可变对象的栈分配等。
实现一个基于完全反向数据流分析实现的简单实现，以及一个结合正交格属性的新格设计。

Try it out!

您可以尝试逃逸分析，通过加载 EAUtils.jl 实用脚本，该脚本定义了方便的条目 code_escapes 和 @code_escapes 以用于测试和调试目的：

julia> let JULIA_DIR = normpath(Sys.BINDIR, "..", "share", "julia")
           # load `EscapeAnalysis` module to define the core analysis code
           include(normpath(JULIA_DIR, "base", "compiler", "ssair", "EscapeAnalysis", "EscapeAnalysis.jl"))
           using .EscapeAnalysis
           # load `EAUtils` module to define the utilities
           include(normpath(JULIA_DIR, "test", "compiler", "EscapeAnalysis", "EAUtils.jl"))
           using .EAUtils
       end
julia> mutable struct SafeRef{T}
           x::T
       end
julia> Base.getindex(x::SafeRef) = x.x;
julia> Base.setindex!(x::SafeRef, v) = x.x = v;
julia> Base.isassigned(x::SafeRef) = true;
julia> get′(x) = isassigned(x) ? x[] : throw(x);
julia> result = code_escapes((String,String,String,String)) do s1, s2, s3, s4
           r1 = Ref(s1)
           r2 = Ref(s2)
           r3 = SafeRef(s3)
           try
               s1 = get′(r1)
               ret = sizeof(s1)
           catch err
               global GV = err # will definitely escape `r1`
           end
           s2 = get′(r2)       # still `r2` doesn't escape fully
           s3 = get′(r3)       # still `r3` doesn't escape fully
           s4 = sizeof(s4)     # the argument `s4` doesn't escape here
           return s2, s3, s4
       end#1(X s1::String, ↑ s2::String, ↑ s3::String, ✓ s4::String) in Main at REPL[7]:2
X  1 ── %1  = %new(Base.RefValue{String}, _2)::Base.RefValue{String}
*′ │    %2  = %new(Base.RefValue{String}, _3)::Base.RefValue{String}
✓′ └─── %3  = %new(Main.SafeRef{String}, _4)::Main.SafeRef{String}
✓′ 2 ── %4  = ϒ (%3)::Main.SafeRef{String}
*′ │    %5  = ϒ (%2)::Base.RefValue{String}
✓  │    %6  = ϒ (_5)::String
◌  └─── %7  = enter #8
◌  3 ── %8  = Base.isdefined(%1, :x)::Bool
◌  └───       goto #5 if not %8
X  4 ──       Base.getfield(%1, :x)::String
◌  └───       goto #6
◌  5 ──       Main.throw(%1)::Union{}
◌  └───       unreachable
◌  6 ──       $(Expr(:leave, :(%7)))
◌  7 ──       goto #11
✓′ 8 ┄─ %16 = φᶜ (%4)::Main.SafeRef{String}
*′ │    %17 = φᶜ (%5)::Base.RefValue{String}
✓  │    %18 = φᶜ (%6)::String
X  └─── %19 = $(Expr(:the_exception))::Any
◌  9 ──       nothing::Nothing
◌  10 ─       (Main.GV = %19)::Any
◌  └───       $(Expr(:pop_exception, :(%7)))::Core.Const(nothing)
✓′ 11 ┄ %23 = φ (#7 => %3, #10 => %16)::Main.SafeRef{String}
*′ │    %24 = φ (#7 => %2, #10 => %17)::Base.RefValue{String}
✓  │    %25 = φ (#7 => _5, #10 => %18)::String
◌  │    %26 = Base.isdefined(%24, :x)::Bool
◌  └───       goto #13 if not %26
↑  12 ─ %28 = Base.getfield(%24, :x)::String
◌  └───       goto #14
◌  13 ─       Main.throw(%24)::Union{}
◌  └───       unreachable
↑  14 ─ %32 = Base.getfield(%23, :x)::String
◌  │    %33 = Core.sizeof(%25)::Int64
↑′ │    %34 = Core.tuple(%28, %32, %33)::Tuple{String, String, Int64}
◌  └───       return %34

每个调用参数和SSA语句旁边的符号表示以下含义：

◌（普通）：此值未被分析，因为它的转义信息无论如何都不会被使用（例如，当对象是isbitstype时）
✓（绿色或青色）：此值永远不会逃逸（has_no_escape(result.state[x]) 为真），如果它也有参数逃逸，则为蓝色（has_arg_escape(result.state[x]) 为真）
↑（蓝色或黄色）：此值可以通过返回逃逸到调用者（has_return_escape(result.state[x]) 为真），如果它还有未处理的抛出逃逸（has_thrown_escape(result.state[x]) 为真），则标记为黄色。
X（红色）：这个值可以逃逸到逃逸分析无法推理的地方，比如逃逸到全局内存（has_all_escape(result.state[x]) 为真）
* (bold): this value's escape state is between the ReturnEscape and AllEscape in the partial order of EscapeInfo, colored yellow if it has unhandled thrown escape also (has_thrown_escape(result.state[x]) holds)
′: 此值在其 AliasInfo 属性中具有额外的对象字段/数组元素信息

每个调用参数和SSA值的逃逸信息可以像下面这样以编程方式进行检查：

julia> result.state[Core.Argument(3)] # get EscapeInfo of `s2`ReturnEscape
julia> result.state[Core.SSAValue(3)] # get EscapeInfo of `r3`NoEscape′

Analysis Design

Lattice Design

EscapeAnalysis 被实现为一个 data-flow analysis，它在一个 x::EscapeInfo 的格上工作，该格由以下属性组成：

x.Analyzed::Bool：并不是格的正式组成部分，仅表示 x 尚未被分析或未分析。
x.ReturnEscape::BitSet: 记录 SSA 语句，其中 x 可以通过返回逃逸到调用者
x.ThrownEscape::BitSet: 记录可以作为异常抛出的 SSA 语句（用于下面描述的 exception handling）
x.AliasInfo：维护所有可能的值，这些值可以被别名为 x 的字段或数组元素（用于下面描述的 alias analysis）
x.ArgEscape::Int（尚未实现）：表示它将通过对参数使用 setfield! 来逃逸到调用者。

这些属性可以组合在一起创建一个具有有限高度的部分格，前提是输入程序的语句数量是有限的，这一点由Julia的语义保证。这个格设计的巧妙之处在于，它通过允许每个格属性单独处理，从而简化了格操作的实现^{[LatticeDesign]}。

此逃逸分析实现基于论文中描述的数据流算法^[MM02]。该分析在EscapeInfo的格上工作，并将格元素从底部过渡到顶部，直到每个格元素收敛到一个固定点，通过维护一个（概念上的）工作集，该工作集包含与待分析的剩余SSA语句对应的程序计数器。该分析管理一个单一的全局状态，跟踪每个参数和SSA语句的EscapeInfo，但还要注意，一些流敏感性被编码为记录在EscapeInfo的ReturnEscape属性中的程序计数器，这可以在必要时与支配分析结合使用，以推理流敏感性。

这种逃逸分析的一个独特设计是它完全是向后的，即逃逸信息从使用流向定义。例如，在下面的代码片段中，EA首先分析语句return %1并对%1（对应于obj）施加ReturnEscape，然后它分析%1 = %new(Base.RefValue{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]}。因此，这种方案使得逃逸分析的简单实现成为可能，例如，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

Alias Analysis

EscapeAnalysis 实现了一种向后字段分析，以便以某种准确性推理对象字段上施加的逃逸情况，而 x::EscapeInfo 的 x.AliasInfo 属性正是为此目的而存在。它记录了在“使用”位置可能与 x 的字段别名的所有可能值，然后这些记录值的逃逸信息在“定义”位置传播到实际字段值。更具体地说，该分析通过分析 getfield 调用记录一个可能与对象字段别名的值，然后在分析 %new(...) 表达式或 setfield! 调用时将其逃逸信息传播到字段^[Dynamism]。

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（对应于 v）上的 ReturnEscape 并没有 直接传播到 %1（对应于 obj），而是 ReturnEscape 仅传播到 _2（对应于 s）。在这里，%3 被记录在 %1 的 AliasInfo 属性中，因为它可以与 %1 的第一个字段别名，然后在分析 Base.setfield!(%1, :x, _2)::String 时，该逃逸信息被传播到 _2，但没有传播到 %1。

所以 EscapeAnalysis 跟踪哪些 IR 元素可以在 getfield-%new/setfield! 链中被别名化，以分析对象字段的逃逸，但实际上这种别名分析需要被推广以处理其他 IR 元素。这是因为在 Julia 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 是别名，因此对 %8 = Base.getfield(%6, :x)::String（对应于 y = ϕ1[]）施加的 ReturnEscape 需要传播到 Base.setfield!(%5, :x, _3)::String（对应于 ϕ2[] = x）。为了正确传播这种逃逸信息，分析应该识别出 ϕ1 和 ϕ2 的前驱也可能是别名，并使它们的逃逸信息相等。

这种别名信息的一个有趣特性是，它在“使用”位置是未知的，但只能在“定义”位置推导出来（因为别名在概念上等同于赋值），因此它并不自然适合向后分析。为了有效地在相关值之间传播逃逸信息，EscapeAnalysis.jl 使用了一种受旧JVM论文中解释的逃逸分析算法启发的方法^[JVM05]。也就是说，除了管理逃逸格子元素外，分析还维护一个“等价”别名集，这是一个不相交的别名参数和SSA语句的集合。别名集管理可以相互别名的值，并允许对任何这样的别名值施加的逃逸信息在它们之间进行等化。

Array Analysis

上述描述的对象字段的别名分析也可以推广到分析数组操作。EscapeAnalysis 实现了对各种原始数组操作的处理，以便通过 arrayref-arrayset 使用-定义链传播逃逸，并且不会过于保守地逃逸已分配的数组：

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 可能发生的逃逸，但也要注意，这种未处理的 ThrownEscape 在优化 ary 分配时通常可以被忽略。

此外，在能够精确知道数组索引信息以及数组维度的情况下，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 是别名。在这种情况下，后续的优化过程将能够用 %2 替换 Base.arrayref(true, %1, 1)::Any（即“加载转发”），并最终完全消除数组 %1 的分配（即“标量替换”）。

与对象字段分析相比，对象字段的访问可以通过推断得出的类型信息轻松分析，而数组维度并未作为类型信息编码，因此我们需要额外的分析来推导该信息。此时的 EscapeAnalysis 首先进行额外的简单线性扫描，以分析分配数组的维度，然后再启动主要分析例程，以便后续的逃逸分析能够准确分析对这些数组的操作。

然而，这种精确的“逐元素”别名分析往往很困难。基本上，数组固有的主要困难在于数组的维度和索引通常是非常量的：

循环经常产生循环变体，非恒定数组索引
（特定于向量）数组调整大小会改变数组维度并使其常量性失效

让我们通过具体例子来讨论这些困难。

在以下示例中，EscapeAnalysis 由于 Base.arrayset(false, %4, %8, %6)::Vector{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 目前在遇到任何数组调整大小操作时简单地放弃精确别名分析，因此对 %2（对应于 SafeRef(s)）和 %20（对应于 SafeRef(t)）施加了 ReturnEscape。

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

为了应对这些困难，我们需要推理能够意识到数组维度，并以流敏感的方式传播数组维度^{[ArrayDimension]}，同时提出循环变值的良好表示。

EscapeAnalysis 此时迅速切换到更不精确的分析，在数组维度或索引显然非常非常量的情况下，不跟踪精确的索引信息。这个切换可以自然地实现为数据流分析框架中 EscapeInfo.AliasInfo 属性的格连接操作。

Exception Handling

值得注意的是，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[] : throw(x);
julia> code_escapes() do
           r = Ref{String}()
           local t
           try
               t = get′(r)
           catch err
               t = typeof(err)   # `err` (which `r` aliases to) doesn't escape here
               rethrow_escape!() # but `r` escapes here
           end
           return t
       end#19() in Main at REPL[4]:2
X  1 ─ %1  = %new(Base.RefValue{String})::Base.RefValue{String}
◌  2 ─ %2  = enter #8
◌  3 ─ %3  = Base.isdefined(%1, :x)::Bool
◌  └──       goto #5 if not %3
X  4 ─ %5  = Base.getfield(%1, :x)::String
◌  └──       goto #6
◌  5 ─       Main.throw(%1)::Union{}
◌  └──       unreachable
◌  6 ─       $(Expr(:leave, :(%2)))
◌  7 ─       goto #9
✓  8 ┄ %11 = $(Expr(:the_exception))::Any
X  │   %12 = Main.typeof(%11)::DataType
✓  │         invoke Main.rethrow_escape!()::Any
◌  └──       $(Expr(:pop_exception, :(%2)))::Core.Const(nothing)
X  9 ┄ %15 = φ (#7 => %5, #8 => %12)::Union{DataType, String}
◌  └──       return %15

它需要进行全球分析，以便正确推理通过现有异常接口的所有可能逃逸。目前，我们总是保守地将最上层的逃逸信息传播到所有可能抛出的对象，因为考虑到异常处理和错误路径通常不需要非常敏感的性能，这样的额外分析可能不值得进行，并且错误路径的优化可能无效，因为它们通常出于延迟原因故意“未优化”。

x::EscapeInfo 的 x.ThrownEscape 属性记录了可以作为异常抛出的 SSA 语句。利用这些信息，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 # will definitely escape `r1`
           end
           s2 = get′(r2)       # still `r2` doesn't escape fully
           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

Analysis Usage

analyze_escapes 是分析 SSA-IR 元素逃逸信息的入口点。

大多数优化，如 SROA (sroa_pass!)，在应用于经过优化的源代码时更有效，这些源代码通过内联传递 (ssa_inlining_pass!) 解决了跨过程调用并扩展了被调用者源。相应地，analyze_escapes 也能够分析内联后的 IR，并收集对某些与内存相关的优化有用的逃逸信息。

然而，由于某些优化过程，如内联，可能会改变控制流并消除无效代码，因此它们可能会破坏逃逸信息的跨过程有效性。特别是，为了收集跨过程有效的逃逸信息，我们需要分析一个预内联的中间表示（IR）。

由于这个原因，analyze_escapes 可以在任何 Julia 级别的优化阶段分析 IRCode，特别是，它应该在以下两个阶段使用：

IPO EA: 分析预内联 IR 以生成 IPO 有效的逃逸信息缓存
Local EA: 分析后内联的中间表示以收集局部有效的逃逸信息

逃逸信息由 IPO EA 转换为 ArgEscapeCache 数据结构并全局缓存。通过将适当的 get_escape_cache 回调传递给 analyze_escapes，逃逸分析可以通过利用之前 IPO EA 导出的非内联被调用者的缓存跨过程信息来提高分析准确性。更有趣的是，使用 IPO EA 逃逸信息进行类型推断也是有效的，例如，通过形成可变对象的 Const/PartialStruct/MustAlias 可以提高推断准确性。

Core.Compiler.EscapeAnalysis.analyze_escapes — Function

analyze_escapes(ir::IRCode, nargs::Int, get_escape_cache) -> estate::EscapeState

分析 ir 中的逃逸信息：

nargs: 被分析调用的实际参数数量
get_escape_cache(::MethodInstance) -> Union{Bool,ArgEscapeCache}: 检索缓存的参数逃逸信息

source

Core.Compiler.EscapeAnalysis.EscapeState — Type

estate::EscapeState

扩展的格映射参数和 SSA 值到表示为 EscapeInfo 的逃逸信息。对 SSA IR 元素 x 施加的逃逸信息可以通过 estate[x] 检索。

source

Core.Compiler.EscapeAnalysis.EscapeInfo — Type

x::EscapeInfo

一个用于逃逸信息的格，它具有以下属性：

x.Analyzed::Bool：并不是格的正式部分，仅指示 x 是否已被分析
x.ReturnEscape::Bool：指示 x 可以通过返回逃逸到调用者
x.ThrownEscape::BitSet：记录 x 可以作为异常抛出的 SSA 语句编号：
- isempty(x.ThrownEscape)：x 在此调用帧中永远不会被抛出（底部）
- pc ∈ x.ThrownEscape：x 可能在 pc 的 SSA 语句处被抛出
- -1 ∈ x.ThrownEscape：x 可能在此调用帧的任意点被抛出（顶部）
这些信息将被 escape_exception! 用于通过异常传播潜在的逃逸。
x.AliasInfo::Union{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，但同时不代表任何意义，除了它尚未被分析（因此它并不是格的正式部分）

source

LatticeDesignOur type inference implementation takes the alternative approach, where each lattice property is represented by a special lattice element type object. It turns out that it started to complicate implementations of the lattice operations mainly because it often requires conversion rules between each lattice element type object. And we are working on overhauling our type inference lattice implementation with EscapeInfo-like lattice design.
MM02A Graph-Free approach to Data-Flow Analysis. Markas Mohnen, 2002, April. https://api.semanticscholar.org/CorpusID:28519618.
BackandForthOur type inference algorithm in contrast is implemented as a forward analysis, because type information usually flows from "definition" to "usage" and it is more natural and effective to propagate such information in a forward way.
DynamismIn some cases, however, object fields can't be analyzed precisely. For example, object may escape to somewhere EscapeAnalysis can't account for possible memory effects on it, or fields of the objects simply can't be known because of the lack of type information. In such cases AliasInfo property is raised to the topmost element within its own lattice order, and it causes succeeding field analysis to be conservative and escape information imposed on fields of an unanalyzable object to be propagated to the object itself.
JVM05Escape Analysis in the Context of Dynamic Compilation and Deoptimization. Thomas Kotzmann and Hanspeter Mössenböck, 2005, June. https://dl.acm.org/doi/10.1145/1064979.1064996.
ArrayDimensionOtherwise we will need yet another forward data-flow analysis on top of the escape analysis.