EscapeAnalysis

Compiler.EscapeAnalysisは、Julia's SSA-form IR(別名IRCode)のエスケープ情報を解析するためのコンパイラユーティリティモジュールです。

このエスケープ解析の目的は次のとおりです。

  • Juliaの高水準な意味論を活用し、特にプロシージャ間呼び出しを通じたエスケープやエイリアシングを推論する
  • alias-aware SROA、early finalize insertion、copy-free ImmutableArray construction、可変オブジェクトのスタック割り当てなど、さまざまな最適化に利用できる汎用性を備える
  • 完全な後向きデータフロー解析の実装と、直交する格子の性質を組み合わせた新しい格子設計に基づき、シンプルに実装する

Try it out!

テストやデバッグ用の便利なエントリポイントcode_escapesと@code_escapesを定義するユーティリティスクリプトEAUtils.jlを読み込むと、エスケープ解析を試すことができます。

julia> # InteractiveUtils.@activate Compiler # to use the stdlib version of the Compiler
       
       let JULIA_DIR = normpath(Sys.BINDIR, Base.DATAROOTDIR, "julia")
           include(normpath(JULIA_DIR, "Compiler", "test", "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((Base.RefValue{String},String,String,)) do r1, s2, s3 r2 = Ref(s2) r3 = SafeRef(s3) try s1 = get′(r1) ret = sizeof(s1) catch err global GV = err # `r1` may escape end s2 = get′(r2) # `r2` doesn't escape s3 = get′(r3) # `r3` doesn't escape return s2, s3, s4 end#2(X r1::Base.RefValue{String}, ✓ s2::String, ✓ s3::String) in Main at REPL[7]:2 ✓′ 1 ── %1 = %new(Base.RefValue{String}, _3)::Base.RefValue{String} ✓′ └─── %2 = %new(Main.SafeRef{String}, _4)::Main.SafeRef{String} ✓′ 2 ── %3 = ϒ (%2)::Main.SafeRef{String} ✓′ │ %4 = ϒ (%1)::Core.PartialStruct(Base.RefValue{String}, Union{Nothing, Bool}[0], Any[String]) ◌ └─── %5 = enter #8 ◌ 3 ── %6 = builtin Base.isdefined(_2, :x)::Bool ◌ └─── goto #5 if not %6 ◌ 4 ── goto #6 ◌ 5 ── builtin Main.throw(_2)::Union{} ◌ └─── unreachable ◌ 6 ── $(Expr(:leave, :(%5))) ◌ 7 ── goto #11 ✓′ 8 ┄─ %13 = φᶜ (%3)::Main.SafeRef{String} ✓′ │ %14 = φᶜ (%4)::Core.PartialStruct(Base.RefValue{String}, Union{Nothing, Bool}[0], Any[String]) X └─── %15 = $(Expr(:the_exception))::Base.RefValue{String} ◌ 9 ── nothing::Nothing X 10 ─ builtin Core.setglobal!(Main, :GV, %15)::Base.RefValue{String} ◌ └─── $(Expr(:pop_exception, :(%5)))::Core.Const(nothing) ✓′ 11 ┄ %19 = φ (#7 => %2, #10 => %13)::Main.SafeRef{String} ✓′ │ %20 = φ (#7 => %1, #10 => %14)::Core.PartialStruct(Base.RefValue{String}, Union{Nothing, Bool}[0], Any[String]) ✓ │ %21 = builtin Base.getfield(%20, :x)::String ✓ │ %22 = builtin Base.getfield(%19, :x)::String X │ %23 = Main.s4::Any ↑′ │ %24 = builtin Core.tuple(%21, %22, %23)::Tuple{String, String, Any} ◌ └─── return %24

各呼び出し引数と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])が成立)
  • *(太字):この値のエスケープ状態は、ReturnEscapeとAllEscapeの間にあります(EscapeInfoの半順序において)。未処理の例外エスケープもある場合は黄色で表示されます(has_thrown_escape(result.state[x])が成立)
  • ′:この値のAliasInfoプロパティには、オブジェクトのフィールドや配列要素に関する追加情報があります

各呼び出し引数とSSA値のエスケープ情報は、次のようにプログラムから調べられます。

julia> result.state[Core.Argument(3)] # get EscapeInfo of `s2`ArgEscape
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:xが戻り値を通じて呼び出し元へエスケープする可能性のあるSSA文を記録します
  • x.ThrownEscape::BitSet:xが例外としてスローされる可能性のあるSSA文を記録します(後述するexception handlingで使用)
  • x.AliasInfo:xのフィールドや配列要素にエイリアスされる可能性のある値をすべて保持します(後述するalias analysisで使用)
  • x.ArgEscape::Int(未実装):引数のsetfield!を通じて呼び出し元へエスケープすることを示します

入力プログラムの文数が有限であるという不変条件(Juliaの意味論によって保証されます)のもとでは、これらの属性を組み合わせて有限の高さを持つ半順序格子を構成できます。この格子設計の巧妙な点は、各格子プロパティを個別に扱えるため、格子演算をよりシンプルに実装できることです[LatticeDesign]。

Backward Escape Propagation

このエスケープ解析の実装は、論文[MM02]で説明されているデータフローアルゴリズムに基づいています。解析ではEscapeInfoの格子を使い、未解析のSSA文に対応するプログラムカウンタを保持する(概念上の)作業集合を管理しながら、すべての格子要素が不動点に収束するまで、格子要素を底から上へ遷移させます。解析は、各引数とSSA文のEscapeInfoを追跡する単一のグローバル状態を管理します。ただし、ある程度のフロー感度は、EscapeInfoのReturnEscapeプロパティに記録されたプログラムカウンタによって表現されている点にも注意してください。必要に応じて、後から支配関係解析と組み合わせ、フロー感度を推論できます。

このエスケープ解析の特徴的な設計の一つは、完全な後向き解析であることです。つまり、エスケープ情報は使用箇所から定義へ流れます。たとえば、以下のコード片では、EAはまず文return %1を解析し、%1(objに対応)にReturnEscapeを課します。次に%1 = %new(Base.RefValue{Base.RefValue{String}, _2}))を解析し、%1に課されたReturnEscapeを、呼び出し引数_2(sに対応)へ伝播します。

julia> code_escapes((Base.RefValue{String},)) do s
           obj = Ref(s)
           return obj
       end#5(↑ s::Base.RefValue{String}) in Main at REPL[1]:2
↑′ 1 ─ %1 = %new(Base.RefValue{Base.RefValue{String}}, _2)::Base.RefValue{Base.RefValue{String}}
◌  └──      return %1

重要なのは、この後向き解析では、エスケープ情報が制御フローではなく、使用・定義チェーンに沿って自然に流れることです[BackandForth]。その結果、エスケープ解析をシンプルに実装できます。たとえばPhiNodeは、PhiNodeに課されたエスケープ情報を、その先行値へ伝播するだけで処理できます。

julia> code_escapes((Bool, Base.RefValue{String}, Base.RefValue{String})) do cnd, s, t
           if cnd
               obj = Ref(s)
           else
               obj = Ref(t)
           end
           return obj
       end#8(✓ cnd::Bool, ↑ s::Base.RefValue{String}, ↑ t::Base.RefValue{String}) in Main at REPL[1]:2
◌  1 ─      goto #3 if not _2
↑′ 2 ─ %2 = %new(Base.RefValue{Base.RefValue{String}}, _3)::Base.RefValue{Base.RefValue{String}}
◌  └──      goto #4
↑′ 3 ─ %4 = %new(Base.RefValue{Base.RefValue{String}}, _4)::Base.RefValue{Base.RefValue{String}}
↑′ 4 ┄ %5 = φ (#2 => %2, #3 => %4)::Core.PartialStruct(Base.RefValue{Base.RefValue{String}}, Union{Nothing, Bool}[0], Any[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#11(✓ s::String) in Main at REPL[1]:2
◌  1 ─     return _2

上の例では、%3(vに対応)に課されたReturnEscapeは、%1(objに対応)へ直接伝播するのではなく、ReturnEscapeだけが_2(sに対応)へ伝播します。ここでは、%3が%1のAliasInfoプロパティに記録されます。これは、%1の第1フィールドにエイリアスされる可能性があるためです。その後、Base.setfield!(%1, :x, _2)::Stringを解析すると、そのエスケープ情報は_2へ伝播しますが、%1へは伝播しません。

つまり、EscapeAnalysisは、オブジェクトのフィールドのエスケープを解析するため、getfield-%new/setfield!チェーンをまたいで、どのIR要素がエイリアスされるかを追跡します。しかし、このエイリアス解析は、ほかのIR要素も扱えるよう一般化する必要があります。Julia IRでは、同じオブジェクトが異なるIR要素で表されることがあるため、実際には同じオブジェクトを表し得るIR要素どうしで、同じエスケープ情報を共有する必要があるからです。PiNodeやtypeassertのように、オペランドの値をそのまま返すIR要素は、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#14(✓ 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}
◌  │          builtin Base.setfield!(%5, :x, _3)::String
✓  │   %8 =   builtin 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#17(✓ s::String) in Main at REPL[1]:2
X  1 ── %1  =   builtin Core.memorynew(Memory{Any}, 0)::Memory{Any}
X  │    %2  =   builtin Core.memoryrefnew(%1)::MemoryRef{Any}
X  │    %3  = %new(Vector{Any}, %2, (0,))::Vector{Any}
X  │    %4  = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
X  │    %5  =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %6  =   builtin Base.getfield(%5, :mem)::Memory{Any}
X  │    %7  =   builtin Base.getfield(%6, :length)::Int64
X  │    %8  =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %9  =   builtin Core.getfield(%8, 1)::Int64
◌  │    %10 = intrinsic Base.add_int(%9, 1)::Int64
◌  │    %11 =   builtin Base.memoryrefoffset(%5)::Int64
◌  │    %12 = intrinsic Base.add_int(%11, %10)::Int64
◌  │    %13 = intrinsic Base.sub_int(%12, 1)::Int64
◌  │    %14 = intrinsic Base.slt_int(%7, %13)::Bool
◌  └───       goto #3 if not %14
◌  2 ──          invoke Base._growend_internal!(%3::Vector{Any}, 1::Int64, %9::Int64)::Nothing
X  3 ┄─ %17 =   builtin Core.tuple(%10)::Tuple{Int64}
◌  │            builtin Base.setfield!(%3, :size, %17)::Tuple{Int64}
◌  └───       goto #4
X  4 ── %20 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %21 =   builtin Core.getfield(%20, 1)::Int64
X  │    %22 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %23 =   builtin Base.memoryrefnew(%22, %21, false)::MemoryRef{Any}
X  │            builtin Base.memoryrefset!(%23, %4, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #5
◌  5 ── %26 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #10 if not %26
◌  6 ── %28 = intrinsic Base.sub_int(1, 1)::Int64
◌  │    %29 = intrinsic Base.bitcast(Base.UInt, %28)::UInt64
X  │    %30 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %31 =   builtin Core.getfield(%30, 1)::Int64
◌  │    %32 = intrinsic Base.bitcast(Base.UInt, %31)::UInt64
◌  │    %33 = intrinsic Base.ult_int(%29, %32)::Bool
◌  └───       goto #8 if not %33
◌  7 ──       goto #9
◌  8 ── %36 =   builtin Core.tuple(1)::Tuple{Int64}
✓  │             invoke Base.throw_boundserror(%3::Vector{Any}, %36::Tuple{Int64})::Union{}
◌  └───       unreachable
◌  9 ──       nothing::Nothing
X  10 ┄ %40 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %41 =   builtin Base.memoryrefnew(%40, 1, false)::MemoryRef{Any}
X  │    %42 =   builtin Base.memoryrefget(%41, :not_atomic, false)::Any
◌  └───       goto #11
X  11 ─ %44 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %45 =   builtin Core.getfield(%44, 1)::Int64
↑′ │    %46 =   builtin Core.tuple(%42, %45)::Tuple{Any, Int64}
◌  └───       return %46

上の例では、EscapeAnalysisは、%20と%2(割り当てられたオブジェクトSafeRef(s)に対応)が、arrayset-arrayrefチェーンを通じてエイリアスされることを認識し、それらにReturnEscapeを課します。一方、割り当てられた配列%1(aryに対応)には課しません。EscapeAnalysisは、aryにもThrownEscapeを課します。これは、BoundsErrorを通じたエスケープの可能性も考慮する必要があるためです。ただし、最適化時には、このように未処理のThrownEscapeを無視できることが多い点にも注意してください。たとえば、aryの割り当てを最適化する場合が該当します。

さらに、配列のインデックス情報と次元を正確に把握できる場合、EscapeAnalysisは、オブジェクトに対してEscapeAnalysisが「フィールドごと」のエイリアス解析を行うのと同様に、arrayref-arraysetチェーンを通じた「要素ごと」のエイリアシングまで推論できます。

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#20(✓ s::String, ✓ t::String) in Main at REPL[1]:2
X  1 ── %1  =   builtin Core.memorynew(Memory{Any}, 2)::Core.PartialStruct(Memory{Any}, Union{Nothing, Bool}[0, 0], Any[Core.Const(2), Ptr{Nothing}])
X  │    %2  =   builtin 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 #6 if not %5
◌  2 ── %7  = intrinsic Base.sub_int(1, 1)::Int64
◌  │    %8  = intrinsic Base.bitcast(Base.UInt, %7)::UInt64
X  │    %9  =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %10 =   builtin Core.getfield(%9, 1)::Int64
◌  │    %11 = intrinsic Base.bitcast(Base.UInt, %10)::UInt64
◌  │    %12 = intrinsic Base.ult_int(%8, %11)::Bool
◌  └───       goto #4 if not %12
◌  3 ──       goto #5
◌  4 ── %15 =   builtin Core.tuple(1)::Tuple{Int64}
✓  │             invoke Base.throw_boundserror(%3::Vector{Any}, %15::Tuple{Int64})::Union{}
◌  └───       unreachable
◌  5 ──       nothing::Nothing
X  6 ┄─ %19 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %20 =   builtin Base.memoryrefnew(%19, 1, false)::MemoryRef{Any}
X  │            builtin Base.memoryrefset!(%20, %4, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #7
X  7 ── %23 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
◌  │    %24 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #12 if not %24
◌  8 ── %26 = intrinsic Base.sub_int(2, 1)::Int64
◌  │    %27 = intrinsic Base.bitcast(Base.UInt, %26)::UInt64
X  │    %28 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %29 =   builtin Core.getfield(%28, 1)::Int64
◌  │    %30 = intrinsic Base.bitcast(Base.UInt, %29)::UInt64
◌  │    %31 = intrinsic Base.ult_int(%27, %30)::Bool
◌  └───       goto #10 if not %31
◌  9 ──       goto #11
◌  10 ─ %34 =   builtin Core.tuple(2)::Tuple{Int64}
✓  │             invoke Base.throw_boundserror(%3::Vector{Any}, %34::Tuple{Int64})::Union{}
◌  └───       unreachable
◌  11 ─       nothing::Nothing
X  12 ┄ %38 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %39 =   builtin Base.memoryrefnew(%38, 2, false)::MemoryRef{Any}
X  │            builtin Base.memoryrefset!(%39, %23, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #13
◌  13 ─ %42 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #18 if not %42
◌  14 ─ %44 = intrinsic Base.sub_int(1, 1)::Int64
◌  │    %45 = intrinsic Base.bitcast(Base.UInt, %44)::UInt64
X  │    %46 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %47 =   builtin Core.getfield(%46, 1)::Int64
◌  │    %48 = intrinsic Base.bitcast(Base.UInt, %47)::UInt64
◌  │    %49 = intrinsic Base.ult_int(%45, %48)::Bool
◌  └───       goto #16 if not %49
◌  15 ─       goto #17
◌  16 ─ %52 =   builtin Core.tuple(1)::Tuple{Int64}
✓  │             invoke Base.throw_boundserror(%3::Vector{Any}, %52::Tuple{Int64})::Union{}
◌  └───       unreachable
◌  17 ─       nothing::Nothing
X  18 ┄ %56 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %57 =   builtin Base.memoryrefnew(%56, 1, false)::MemoryRef{Any}
X  │    %58 =   builtin Base.memoryrefget(%57, :not_atomic, false)::Any
◌  └───       goto #19
X  19 ─ %60 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %61 =   builtin Core.getfield(%60, 1)::Int64
↑′ │    %62 =   builtin Core.tuple(%58, %61)::Tuple{Any, Int64}
◌  └───       return %62

ReturnEscapeは%2(SafeRef(s)に対応)にのみ課され、%4(SafeRef(t)に対応)には課されない点に注意してください。これは、割り当てられた配列の次元と、すべてのarrayref/arrayset操作で使われるインデックスが定数情報として得られるためです。EscapeAnalysisは、%6が%2にエイリアスされる一方、%4には決してエイリアスされないと推論できます。このような場合、後続の最適化パスでBase.arrayref(true, %1, 1)::Anyを%2に置き換えられます(「ロード転送」とも呼ばれます)。最終的には、配列%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#23(✓ s::String, ✓ t::String) in Main at REPL[1]:2
X  1 ── %1  =   builtin Core.memorynew(Memory{Any}, 2)::Memory{Any}
X  │    %2  =   builtin 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  =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %7  =   builtin Base.memoryrefnew(%6, %4, false)::MemoryRef{Any}
◌  │            builtin Base.memoryrefset!(%7, nothing, :not_atomic, false)::Nothing
◌  │    %9  =   builtin (%5 === 2)::Bool
◌  └───       goto #4 if not %9
◌  3 ──       goto #5
◌  4 ── %12 = intrinsic Base.add_int(%5, 1)::Int64
◌  └───       goto #5
◌  5 ┄─ %14 = φ (#4 => %12)::Int64
◌  │    %15 = φ (#4 => %12)::Int64
◌  │    %16 = φ (#3 => true, #4 => false)::Bool
◌  │    %17 = intrinsic 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 #13 if not %22
◌  9 ── %24 = intrinsic Base.sub_int(1, 1)::Int64
◌  │    %25 = intrinsic Base.bitcast(Base.UInt, %24)::UInt64
X  │    %26 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %27 =   builtin Core.getfield(%26, 1)::Int64
◌  │    %28 = intrinsic Base.bitcast(Base.UInt, %27)::UInt64
◌  │    %29 = intrinsic Base.ult_int(%25, %28)::Bool
◌  └───       goto #11 if not %29
◌  10 ─       goto #12
◌  11 ─ %32 =   builtin Core.tuple(1)::Tuple{Int64}
✓  │             invoke Base.throw_boundserror(%3::Vector{Any}, %32::Tuple{Int64})::Union{}
◌  └───       unreachable
◌  12 ─       nothing::Nothing
X  13 ┄ %36 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %37 =   builtin Base.memoryrefnew(%36, 1, false)::MemoryRef{Any}
X  │            builtin Base.memoryrefset!(%37, %21, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #14
X  14 ─ %40 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
◌  │    %41 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #19 if not %41
◌  15 ─ %43 = intrinsic Base.sub_int(2, 1)::Int64
◌  │    %44 = intrinsic Base.bitcast(Base.UInt, %43)::UInt64
X  │    %45 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %46 =   builtin Core.getfield(%45, 1)::Int64
◌  │    %47 = intrinsic Base.bitcast(Base.UInt, %46)::UInt64
◌  │    %48 = intrinsic Base.ult_int(%44, %47)::Bool
◌  └───       goto #17 if not %48
◌  16 ─       goto #18
◌  17 ─ %51 =   builtin Core.tuple(2)::Tuple{Int64}
✓  │             invoke Base.throw_boundserror(%3::Vector{Any}, %51::Tuple{Int64})::Union{}
◌  └───       unreachable
◌  18 ─       nothing::Nothing
X  19 ┄ %55 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %56 =   builtin Base.memoryrefnew(%55, 2, false)::MemoryRef{Any}
X  │            builtin Base.memoryrefset!(%56, %40, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #20
◌  20 ─ %59 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #25 if not %59
◌  21 ─ %61 = intrinsic Base.sub_int(1, 1)::Int64
◌  │    %62 = intrinsic Base.bitcast(Base.UInt, %61)::UInt64
X  │    %63 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %64 =   builtin Core.getfield(%63, 1)::Int64
◌  │    %65 = intrinsic Base.bitcast(Base.UInt, %64)::UInt64
◌  │    %66 = intrinsic Base.ult_int(%62, %65)::Bool
◌  └───       goto #23 if not %66
◌  22 ─       goto #24
◌  23 ─ %69 =   builtin Core.tuple(1)::Tuple{Int64}
✓  │             invoke Base.throw_boundserror(%3::Vector{Any}, %69::Tuple{Int64})::Union{}
◌  └───       unreachable
◌  24 ─       nothing::Nothing
X  25 ┄ %73 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %74 =   builtin Base.memoryrefnew(%73, 1, false)::MemoryRef{Any}
X  │    %75 =   builtin Base.memoryrefget(%74, :not_atomic, false)::Any
◌  └───       goto #26
X  26 ─ %77 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %78 =   builtin Core.getfield(%77, 1)::Int64
↑′ │    %79 =   builtin Core.tuple(%75, %78)::Tuple{Any, Int64}
◌  └───       return %79

次の例では、ベクトルのリサイズによって正確なエイリアス解析が難しくなる様子を示します。主な問題は、割り当てられた配列%1の次元が最初は0として初期化されるものの、その後の2回の: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#26(✓ s::String, ✓ t::String) in Main at REPL[1]:2
X  1 ── %1  =   builtin Core.memorynew(Memory{Any}, 0)::Memory{Any}
X  │    %2  =   builtin Core.memoryrefnew(%1)::MemoryRef{Any}
X  │    %3  = %new(Vector{Any}, %2, (0,))::Vector{Any}
X  │    %4  = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
X  │    %5  =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %6  =   builtin Base.getfield(%5, :mem)::Memory{Any}
X  │    %7  =   builtin Base.getfield(%6, :length)::Int64
X  │    %8  =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %9  =   builtin Core.getfield(%8, 1)::Int64
◌  │    %10 = intrinsic Base.add_int(%9, 1)::Int64
◌  │    %11 =   builtin Base.memoryrefoffset(%5)::Int64
◌  │    %12 = intrinsic Base.add_int(%11, %10)::Int64
◌  │    %13 = intrinsic Base.sub_int(%12, 1)::Int64
◌  │    %14 = intrinsic Base.slt_int(%7, %13)::Bool
◌  └───       goto #3 if not %14
◌  2 ──          invoke Base._growend_internal!(%3::Vector{Any}, 1::Int64, %9::Int64)::Nothing
X  3 ┄─ %17 =   builtin Core.tuple(%10)::Tuple{Int64}
◌  │            builtin Base.setfield!(%3, :size, %17)::Tuple{Int64}
◌  └───       goto #4
X  4 ── %20 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %21 =   builtin Core.getfield(%20, 1)::Int64
X  │    %22 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %23 =   builtin Base.memoryrefnew(%22, %21, false)::MemoryRef{Any}
X  │            builtin Base.memoryrefset!(%23, %4, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #5
X  5 ── %26 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
X  │    %27 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %28 =   builtin Base.getfield(%27, :mem)::Memory{Any}
X  │    %29 =   builtin Base.getfield(%28, :length)::Int64
X  │    %30 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %31 =   builtin Core.getfield(%30, 1)::Int64
◌  │    %32 = intrinsic Base.add_int(%31, 1)::Int64
◌  │    %33 =   builtin Base.memoryrefoffset(%27)::Int64
◌  │    %34 = intrinsic Base.add_int(%33, %32)::Int64
◌  │    %35 = intrinsic Base.sub_int(%34, 1)::Int64
◌  │    %36 = intrinsic Base.slt_int(%29, %35)::Bool
◌  └───       goto #7 if not %36
◌  6 ──          invoke Base._growend_internal!(%3::Vector{Any}, 1::Int64, %31::Int64)::Nothing
X  7 ┄─ %39 =   builtin Core.tuple(%32)::Tuple{Int64}
◌  │            builtin Base.setfield!(%3, :size, %39)::Tuple{Int64}
◌  └───       goto #8
X  8 ── %42 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %43 =   builtin Core.getfield(%42, 1)::Int64
X  │    %44 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %45 =   builtin Base.memoryrefnew(%44, %43, false)::MemoryRef{Any}
X  │            builtin Base.memoryrefset!(%45, %26, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #9
◌  9 ── %48 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #14 if not %48
◌  10 ─ %50 = intrinsic Base.sub_int(1, 1)::Int64
◌  │    %51 = intrinsic Base.bitcast(Base.UInt, %50)::UInt64
X  │    %52 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %53 =   builtin Core.getfield(%52, 1)::Int64
◌  │    %54 = intrinsic Base.bitcast(Base.UInt, %53)::UInt64
◌  │    %55 = intrinsic Base.ult_int(%51, %54)::Bool
◌  └───       goto #12 if not %55
◌  11 ─       goto #13
◌  12 ─ %58 =   builtin Core.tuple(1)::Tuple{Int64}
✓  │             invoke Base.throw_boundserror(%3::Vector{Any}, %58::Tuple{Int64})::Union{}
◌  └───       unreachable
◌  13 ─       nothing::Nothing
X  14 ┄ %62 =   builtin Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %63 =   builtin Base.memoryrefnew(%62, 1, false)::MemoryRef{Any}
X  │    %64 =   builtin Base.memoryrefget(%63, :not_atomic, false)::Any
◌  └───       goto #15
X  15 ─ %66 =   builtin Base.getfield(%3, :size)::Tuple{Int64}
X  │    %67 =   builtin Core.getfield(%66, 1)::Int64
↑′ │    %68 =   builtin Core.tuple(%64, %67)::Tuple{Any, Int64}
◌  └───       return %68

こうした問題に対処するには、推論で配列の次元を扱い、フロー感度を保って次元情報を伝播する必要があります[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#29() in Main at REPL[4]:2 X 1 ─ %1 = %new(Base.RefValue{String})::Base.RefValue{String} ◌ 2 ─ %2 = enter #8 ◌ 3 ─ %3 = builtin Base.isdefined(%1, :x)::Bool ◌ └── goto #5 if not %3 X 4 ─ %5 = builtin Base.getfield(%1, :x)::String ◌ └── goto #6 ◌ 5 ─ builtin Main.throw(%1)::Union{} ◌ └── unreachable ◌ 6 ─ $(Expr(:leave, :(%2))) ◌ 7 ─ goto #9 ✓ 8 ┄ invoke Main.rethrow_escape!()::Any ◌ └── $(Expr(:pop_exception, :(%2)))::Core.Const(nothing) X 9 ┄ %13 = φ (#7 => %5, #8 => Base.RefValue{String})::Union{String, Type{Base.RefValue{String}}} ◌ └── return %13

既存の例外インターフェースを通じたエスケープの可能性をすべて正しく推論するには、グローバル解析が必要です。現時点では、スローされる可能性のあるすべてのオブジェクトに、最上位のエスケープ情報を常に保守的に伝播しています。例外処理やエラーパスは通常、性能にそれほど敏感ではなく、エラーパスの最適化も、レイテンシ上の理由から意図的に「最適化されていない」ことが多いため、追加の解析を行う価値は低いと考えられるからです。

x::EscapeInfoのx.ThrownEscapeプロパティは、xが例外としてスローされる可能性のある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#32(✓ s1::String, ✓ s2::String) in Main at REPL[1]:2
◌  1 ─     nothing::Nothing
◌  2 ─     nothing::Nothing
◌  3 ─     nothing::Nothing
◌  4 ─     nothing::Nothing
◌  5 ─     return _3

Analysis Usage

analyze_escapesは、SSA-IR要素のエスケープ情報を解析するためのエントリポイントです。

SROA(sroa_pass!)などの最適化は、インライン化パス(ssa_inlining_pass!)がプロシージャ間呼び出しを解決し、呼び出し先のソースを展開して簡素化したソースに適用すると、より効果的です。そのため、analyze_escapesはインライン化後のIRも解析でき、特定のメモリ関連最適化に役立つエスケープ情報を収集できます。

ただし、インライン化などの最適化パスは制御フローを変更したり、デッドコードを除去したりするため、エスケープ情報のプロシージャ間での妥当性を損なうことがあります。特に、プロシージャ間で有効なエスケープ情報を収集するには、インライン化前のIRを解析する必要があります。

このため、analyze_escapesはJuliaレベルの任意の最適化段階でIRCodeを解析できます。特に、次の2つの段階で使うことを想定しています。

  • IPO EA:インライン化前のIRを解析し、IPOで有効なエスケープ情報のキャッシュを生成する
  • Local EA:インライン化後のIRを解析し、ローカルで有効なエスケープ情報を収集する

IPO EAから得られたエスケープ情報は、ArgEscapeCacheデータ構造に変換され、グローバルにキャッシュされます。適切なget_escape_cacheコールバックをanalyze_escapesに渡すと、以前のIPO EAで導出された、インライン化されていない呼び出し先のプロシージャ間情報を利用して、エスケープ解析の精度を高められます。さらに、IPO EAのエスケープ情報を型推論に使うこともできます。たとえば、可変オブジェクトのConst/PartialStruct/MustAliasを形成することで、推論精度を高められます。

Base.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
Base.Compiler.EscapeAnalysis.EscapeState — Type
estate::EscapeState

引数とSSA値をエスケープ情報に対応付ける拡張ラティス。エスケープ情報はEscapeInfoとして表されます。SSA IR要素xに設定されたエスケープ情報は、estate[x]で取得できます。

source
Base.Compiler.EscapeAnalysis.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: SSA文pcでxがスローされる可能性があります
    • -1 ∈ x.ThrownEscape: この呼び出しフレーム内の任意の箇所でxがスローされる可能性があります(最上位)

    この情報は、escape_exception!が例外による潜在的なエスケープを伝播するために使用されます。

  • x.AliasInfo::Union{Bool,IndexableFields,Unindexable}: xのフィールドまたは配列要素にエイリアスされる可能性のある値をすべて保持します。

    • x.AliasInfo === falseは、xのフィールド/要素がまだ解析されていないことを示します
    • x.AliasInfo === trueは、xのフィールド/要素を解析できないことを示します。たとえば、xの型が不明、または具象型ではないため、フィールド/要素を正確に特定できない場合です
    • x.AliasInfo::IndexableFieldsは、正確なインデックス情報とともに、オブジェクトxのフィールドにエイリアスされる可能性のある値をすべて記録します
    • x.AliasInfo::Unindexableは、正確なインデックス情報なしで、xのフィールド/要素にエイリアスされる可能性のある値をすべて記録します
  • x.Liveness::BitSet: xが生存しているべきSSA文番号を記録します。たとえば、呼び出し引数として使われる場合、呼び出し元に返される場合、または:foreigncallのために保持される場合です。

    • isempty(x.Liveness): この呼び出しフレームではxは決して使われません(最下位)
    • 0 ∈ x.Livenessには、現在解析中の呼び出しフレームの呼び出し引数であるという特別な意味もあります(そのため、呼び出し元から直ちに参照できます)。
    • pc ∈ x.Liveness: SSA文pcでxが使われる可能性があります
    • -1 ∈ x.Liveness: この呼び出しフレーム内の任意の箇所でxが使われる可能性があります(最上位)

一般的なEscapeInfoを作成するためのユーティリティコンストラクターがあります。たとえば、

  • NoEscape(): この格子の最下位(に相当する)要素で、どこにもエスケープしないことを意味します
  • AllEscape(): この格子の最上位要素で、あらゆる場所へエスケープすることを意味します

analyze_escapesは、Julia標準の型推論ルーチンと同じ方向に、これらの要素を最下位から最上位へ遷移させます。抽象状態は、最下位(に相当する)要素で初期化されます。

  • 呼び出し引数はArgEscape()として初期化されます。そのLivenessプロパティには、呼び出し引数として渡され、呼び出し元から直ちに参照できることを示す0が含まれます
  • その他の状態はNotAnalyzed()として初期化されます。これはNoEscapeよりわずかに下位にある特別な格子要素ですが、まだ解析されていないこと以外の意味は持ちません(したがって、格子の正式な要素ではありません)
source