GitHub

EscapeAnalysis

Core.Compiler.EscapeAnalysis ist ein Compiler-Dienstprogramm-Modul, das darauf abzielt, die Escape-Informationen von Julia's SSA-form IR, auch bekannt als IRCode, zu analysieren.

Diese Escape-Analyse zielt darauf ab:

  • Nutzen Sie Julias hochgradige Semantik, insbesondere um über Ausstiege und Aliasierung durch interprozedurale Aufrufe nachzudenken.
  • seien Sie vielseitig genug, um für verschiedene Optimierungen verwendet zu werden, einschließlich alias-aware SROA, early finalize insertion, copy-free ImmutableArray construction, Stapelzuweisung von veränderlichen Objekten und so weiter.
  • erreichen Sie eine einfache Implementierung, die auf einer vollständig rückwärtsgerichteten Datenflussanalyse-Implementierung basiert, sowie ein neues Gitterdesign, das orthogonale Gittereigenschaften kombiniert.

Try it out!

Sie können die Escape-Analyse ausprobieren, indem Sie das EAUtils.jl-Hilfsskript laden, das die praktischen Einträge code_escapes und @code_escapes zu Test- und Debuggingzwecken definiert:

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

Die Symbole an der Seite jedes Aufrufarguments und der SSA-Anweisungen bedeuten Folgendes:

  • ◌ (plain): Dieser Wert wird nicht analysiert, da die Escape-Informationen davon ohnehin nicht verwendet werden (wenn das Objekt beispielsweise isbitstype ist).
  • ✓ (grün oder cyan): dieser Wert entkommt niemals (has_no_escape(result.state[x]) gilt), blau gefärbt, wenn auch has_arg_escape(result.state[x]) gilt
  • ↑ (blau oder gelb): dieser Wert kann über die Rückgabe an den Aufrufer entkommen (has_return_escape(result.state[x]) gilt), gelb gefärbt, wenn er auch unhandled thrown escape hat (has_thrown_escape(result.state[x]) gilt)
  • X (rot): dieser Wert kann an einen Ort entkommen, den die Escape-Analyse nicht nachvollziehen kann, wie das Entkommen in einen globalen Speicher (has_all_escape(result.state[x]) gilt)
  • * (fett): der Fluchtzustand dieses Wertes liegt zwischen dem ReturnEscape und AllEscape in der partiellen Ordnung von EscapeInfo, gelb gefärbt, wenn es unbehandelte geworfene Flucht gibt (has_thrown_escape(result.state[x]) gilt)
  • ′: dieser Wert hat zusätzliche Objektfeld-/Array-Elementinformationen in seiner AliasInfo-Eigenschaft

Die Escape-Information jedes Aufrufarguments und SSA-Werts kann programmgesteuert inspiziert werden, wie folgt:

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 wird als ein data-flow analysis implementiert, das auf einem Gitter von x::EscapeInfo arbeitet, das aus den folgenden Eigenschaften besteht:

  • x.Analyzed::Bool: nicht formell Teil des Lattices, zeigt nur an, ob x analysiert wurde oder nicht
  • x.ReturnEscape::BitSet: zeichnet SSA-Anweisungen auf, bei denen x über die Rückgabe an den Aufrufer entkommen kann
  • x.ThrownEscape::BitSet: zeichnet SSA-Anweisungen auf, bei denen x als Ausnahme geworfen werden kann (verwendet für die exception handling, die unten beschrieben ist)
  • x.AliasInfo: enthält alle möglichen Werte, die auf Felder oder Array-Elemente von x aliasiert werden können (verwendet für die alias analysis, die unten beschrieben ist)
  • x.ArgEscape::Int (noch nicht implementiert): zeigt an, dass es über setfield! an den Aufrufer durch Argument(e) entkommen wird.

Diese Attribute können kombiniert werden, um ein partielles Gitter zu erstellen, das eine endliche Höhe hat, vorausgesetzt, dass ein Eingabeprogramm eine endliche Anzahl von Anweisungen hat, was durch Julias Semantik gewährleistet ist. Der clevere Teil dieses Gitterdesigns besteht darin, dass es eine einfachere Implementierung von Gitteroperationen ermöglicht, indem es ihnen erlaubt, jede Gittereigenschaft separat zu behandeln[LatticeDesign].

Backward Escape Propagation

Diese Implementierung der Escape-Analyse basiert auf dem Datenflussalgorithmus, der im Papier[MM02] beschrieben ist. Die Analyse arbeitet auf dem Gitter von EscapeInfo und überführt Gitterelemente von unten nach oben, bis jedes Gitterelement zu einem festen Punkt konvergiert, indem ein (konzeptioneller) Arbeitsbereich aufrechterhalten wird, der Programmzähler enthält, die den verbleibenden SSA-Anweisungen entsprechen, die analysiert werden sollen. Die Analyse verwaltet einen einzigen globalen Zustand, der EscapeInfo jedes Arguments und jeder SSA-Anweisung verfolgt, aber beachten Sie auch, dass einige Fluss-Sensitivität als Programmzähler kodiert ist, die in der ReturnEscape-Eigenschaft von EscapeInfo aufgezeichnet sind, die später mit der Dominanzanalyse kombiniert werden kann, um bei Bedarf über Fluss-Sensitivität zu argumentieren.

Ein markantes Design dieser Fluchtanalyse ist, dass sie vollständig rückwärts ist, d.h. Fluchtinformationen fließen von Verwendungen zu Definitionen. Zum Beispiel analysiert die Fluchtanalyse im folgenden Code-Snippet zuerst die Anweisung return %1 und legt ReturnEscape auf %1 (entsprechend obj) fest, und dann analysiert sie %1 = %new(Base.RefValue{String, _2})) und propagiert das auf %1 auferlegte ReturnEscape auf das Aufrufargument _2 (entsprechend 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

Die wichtigste Beobachtung hier ist, dass diese rückwärtsgerichtete Analyse es ermöglicht, dass Fluchtinformationen natürlich entlang der Verwendung-Definition-Kette fließen, anstatt entlang des Kontrollflusses[BackandForth]. Infolgedessen ermöglicht dieses Schema eine einfache Implementierung der Fluchtanalyse, z. B. kann PhiNode einfach behandelt werden, indem Fluchtinformationen, die auf einen PhiNode auferlegt werden, an seine Vorgängerwerte propagiert werden:

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 implementiert eine rückwärtsgerichtete Feldanalyse, um über die auf Objektfelder ausgeübten Entweichungen mit gewisser Genauigkeit zu argumentieren, und die x::EscapeInfo-Eigenschaft x.AliasInfo existiert zu diesem Zweck. Sie zeichnet alle möglichen Werte auf, die an "Nutzungs"-Stellen auf Felder von x aliasiert werden können, und dann wird die Entweichungsinformation dieser aufgezeichneten Werte später an den tatsächlichen Feldwerten an "Definitions"-Stellen propagiert. Genauer gesagt, zeichnet die Analyse einen Wert auf, der an ein Feld eines Objekts aliasiert sein kann, indem sie den getfield-Aufruf analysiert, und propagiert dann seine Entweichungsinformation an das Feld, wenn sie den %new(...)-Ausdruck oder den setfield!-Aufruf analysiert[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

Im dem obigen Beispiel wird ReturnEscape, das auf %3 (entsprechend v) angewendet wird, nicht direkt an %1 (entsprechend obj) weitergegeben, sondern ReturnEscape wird nur an _2 (entsprechend s) weitergegeben. Hier wird %3 in der AliasInfo-Eigenschaft von %1 aufgezeichnet, da es auf das erste Feld von %1 aliasiert werden kann, und wenn dann Base.setfield!(%1, :x, _2)::String analysiert wird, wird diese Escape-Information an _2 weitergegeben, aber nicht an %1.

So EscapeAnalysis verfolgt, welche IR-Elemente über eine getfield-%new/setfield!-Kette aliasiert werden können, um die Entweichungen von Objektfeldern zu analysieren. Tatsächlich muss diese Alias-Analyse jedoch verallgemeinert werden, um auch andere IR-Elemente zu behandeln. Dies liegt daran, dass im Julia IR dasselbe Objekt manchmal durch verschiedene IR-Elemente dargestellt wird, und wir sollten sicherstellen, dass diese verschiedenen IR-Elemente, die tatsächlich dasselbe Objekt darstellen können, die gleichen Entweichungsinformationen teilen. IR-Elemente, die dasselbe Objekt wie ihre Operanden zurückgeben, wie PiNode und typeassert, können diese IR-Ebene-Aliasierung verursachen und erfordern daher, dass die Entweichungsinformationen, die auf einen solchen aliasierten Wert angewendet werden, zwischen ihnen geteilt werden. Interessanterweise ist es auch notwendig, um korrekt über Mutationen auf PhiNode nachzudenken. Lassen Sie uns das folgende Beispiel betrachten:

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 und ϕ2 = %6 sind aliasiert und daher muss ReturnEscape, das auf %8 = Base.getfield(%6, :x)::String (entsprechend y = ϕ1[]) auferlegt wird, auf Base.setfield!(%5, :x, _3)::String (entsprechend ϕ2[] = x) propagiert werden. Damit solche Fluchtinformationen korrekt propagiert werden, sollte die Analyse erkennen, dass auch die Vorgänger von ϕ1 und ϕ2 aliasiert sein können und ihre Fluchtinformationen gleichsetzen.

Eine interessante Eigenschaft solcher Alias-Informationen ist, dass sie am "Nutzungs"-Standort nicht bekannt sind, sondern nur am "Definitions"-Standort abgeleitet werden können (da Aliasing konzeptionell dem Zuweisen entspricht), und daher passt es nicht natürlich in eine rückwärtsgerichtete Analyse. Um Fluchtinformationen effizient zwischen verwandten Werten zu propagieren, verwendet EscapeAnalysis.jl einen Ansatz, der von dem Fluchtanalyse-Algorithmus inspiriert ist, der in einem alten JVM-Papier[JVM05] erklärt wird. Das heißt, zusätzlich zur Verwaltung von Fluchtgitterelementen verwaltet die Analyse auch eine "equi"-Alias-Menge, eine disjunkte Menge von aliasierten Argumenten und SSA-Anweisungen. Die Alias-Menge verwaltet Werte, die einander aliasiert werden können, und ermöglicht es, Fluchtinformationen, die auf einen dieser aliasierten Werte auferlegt werden, zwischen ihnen zu egalisieren.

Array Analysis

Die oben beschriebene Alias-Analyse für Objektfelder kann auch verallgemeinert werden, um Array-Operationen zu analysieren. EscapeAnalysis implementiert Handhabungen für verschiedene primitive Array-Operationen, sodass es Escapes über die arrayref-arrayset-Nutzungs-Definitionskette propagieren kann und nicht zu konservativ mit allokierten Arrays umgeht:

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

Im dem obigen Beispiel versteht EscapeAnalysis, dass %20 und %2 (entsprechend dem zugewiesenen Objekt SafeRef(s)) über die arrayset-arrayref-Kette aliasiert sind und ReturnEscape auf sie auferlegt, aber nicht auf das zugewiesene Array %1 (entsprechend ary). EscapeAnalysis auferlegt weiterhin ThrownEscape auf ary, da es auch potenzielle Fluchten über BoundsError berücksichtigen muss, aber beachten Sie auch, dass solche unbehandelten ThrownEscape oft ignoriert werden können, wenn die Zuweisung von ary optimiert wird.

Darüber hinaus kann EscapeAnalysis in Fällen, in denen die Array-Indexinformationen sowie die Array-Dimensionen genau bekannt sind, sogar über "pro-Element" Aliasing über die arrayref-arrayset-Kette nachdenken, da EscapeAnalysis eine "pro-Feld" Alias-Analyse für Objekte durchführt:

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

Beachten Sie, dass ReturnEscape nur auf %2 (entsprechend SafeRef(s)) und nicht auf %4 (entsprechend SafeRef(t)) angewendet wird. Dies liegt daran, dass die Dimension des zugewiesenen Arrays und die Indizes, die an allen arrayref/arrayset-Operationen beteiligt sind, als konstante Informationen verfügbar sind und EscapeAnalysis verstehen kann, dass %6 auf %2 verweist, aber niemals auf %4. In einem solchen Fall werden die nachfolgenden Optimierungspässe in der Lage sein, Base.arrayref(true, %1, 1)::Any durch %2 (auch bekannt als "Load-Forwarding") zu ersetzen und schließlich die Zuweisung des Arrays %1 vollständig zu eliminieren (auch bekannt als "Skalarersetzung").

Im Vergleich zur Analyse von Objektfeldern, bei der der Zugriff auf Objektfelder trivial mithilfe von durch Inferenz abgeleiteten Typinformationen analysiert werden kann, wird die Array-Dimension nicht als Typinformation kodiert, und daher benötigen wir eine zusätzliche Analyse, um diese Informationen abzuleiten. EscapeAnalysis führt in diesem Moment zunächst einen zusätzlichen einfachen linearen Scan durch, um die Dimensionen der allokierten Arrays zu analysieren, bevor die Hauptanalyse-Routine gestartet wird, damit die nachfolgende Escape-Analyse die Operationen auf diesen Arrays präzise analysieren kann.

Allerdings ist eine so präzise "pro-Element" Alias-Analyse oft schwierig. Im Wesentlichen besteht die Hauptschwierigkeit darin, dass die Array-Dimension und der Index oft nicht konstant sind:

  • Schleifen erzeugen oft schleifenvariante, nicht konstante Array-Indizes.
  • (spezifisch für Vektoren) Die Größenänderung eines Arrays ändert die Array-Dimension und macht seine Konstantheit ungültig.

Lass uns diese Schwierigkeiten mit konkreten Beispielen besprechen.

Im folgenden Beispiel schlägt die EscapeAnalysis die präzise Alias-Analyse fehl, da der Index bei Base.arrayset(false, %4, %8, %6)::Vector{Any} nicht (trivially) konstant ist. Besonders Any[nothing, nothing] bildet eine Schleife und ruft diese arrayset-Operation in einer Schleife auf, wobei %6 als ϕ-Knotenwert dargestellt wird (dessen Wert von der Kontrollflussabhängigkeit abhängt). Infolgedessen wird ReturnEscape sowohl auf %23 (entsprechend SafeRef(s)) als auch auf %25 (entsprechend SafeRef(t)) auferlegt, obwohl wir idealerweise möchten, dass es nur auf %23 und nicht auf %25 auferlegt wird:

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

Das nächste Beispiel veranschaulicht, wie das Ändern der Größe von Vektoren präzise Alias-Analysen erschwert. Die wesentliche Schwierigkeit besteht darin, dass die Dimension des zugewiesenen Arrays %1 zunächst auf 0 initialisiert wird, sich jedoch durch die beiden :jl_array_grow_end-Aufrufe danach ändert. EscapeAnalysis gibt derzeit einfach die präzise Alias-Analyse auf, wann immer es auf Array-Größenänderungen stößt, und so wird ReturnEscape sowohl auf %2 (entsprechend SafeRef(s)) als auch auf %20 (entsprechend SafeRef(t)) auferlegt:

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

Um diese Schwierigkeiten zu beheben, müssen wir sicherstellen, dass die Inferenz sich der Array-Dimensionen bewusst ist und die Array-Dimensionen auf flussabhängige Weise propagiert, sowie eine ansprechende Darstellung von schleifenvarianten Werten entwickeln.

EscapeAnalysis wechselt in diesem Moment schnell zu der ungenaueren Analyse, die keine präzisen Indexinformationen verfolgt, wenn die Array-Dimensionen oder Indizes trivialerweise nicht konstant sind. Der Wechsel kann natürlich als ein Gitter-Vereinigungsoperation der EscapeInfo.AliasInfo-Eigenschaft im Datenflussanalyse-Rahmen implementiert werden.

Exception Handling

Es wäre auch erwähnenswert, wie EscapeAnalysis mögliche Ausflüsse über Ausnahmen behandelt. Naiv scheint es ausreichend zu sein, die Ausflusinformationen, die auf das :the_exception-Objekt auferlegt werden, auf alle Werte zu propagieren, die in einem entsprechenden try-Block geworfen werden können. Es gibt jedoch tatsächlich mehrere andere Möglichkeiten, auf das Ausnahmeobjekt in Julia zuzugreifen, wie Base.current_exceptions und rethrow. Zum Beispiel muss die Ausflusanalyse den potenziellen Ausfluss von r im folgenden Beispiel berücksichtigen:

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

Es erfordert eine globale Analyse, um korrekt über alle möglichen Ausnahmen über bestehende Ausnahme-Schnittstellen nachzudenken. Derzeit propagieren wir immer die oberste Auskunft über Ausnahmen an alle potenziell geworfenen Objekte konservativ, da eine solche zusätzliche Analyse möglicherweise nicht lohnenswert ist, da die Ausnahmebehandlung und der Fehlerpfad in der Regel nicht sehr leistungsempfindlich sein müssen und auch Optimierungen von Fehlerpfaden ohnehin sehr ineffektiv sein könnten, da sie oft sogar absichtlich "nicht optimiert" aus Latenzgründen sind.

x::EscapeInfo's x.ThrownEscape-Eigenschaft zeichnet SSA-Anweisungen auf, bei denen x als Ausnahme geworfen werden kann. Mit diesen Informationen kann EscapeAnalysis mögliche Ausnahmen über Ausnahmen begrenzt nur auf die propagieren, die in jedem try-Bereich geworfen werden können:

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 ist der Einstiegspunkt zur Analyse von Escape-Informationen von SSA-IR-Elementen.

Die meisten Optimierungen wie SROA (sroa_pass!) sind effektiver, wenn sie auf einen optimierten Quellcode angewendet werden, den der Inlining-Pass (ssa_inlining_pass!) vereinfacht hat, indem er inter-prozedurale Aufrufe aufgelöst und die aufgerufenen Quellen erweitert hat. Dementsprechend kann analyze_escapes auch IR nach dem Inlining analysieren und Fluchtinformationen sammeln, die für bestimmte speicherbezogene Optimierungen nützlich sind.

Allerdings können bestimmte Optimierungspässe wie Inlining, die Kontrollflüsse ändern und toten Code eliminieren, die inter-prozedurale Gültigkeit von Escape-Informationen beeinträchtigen. Insbesondere müssen wir, um inter-prozedural gültige Escape-Informationen zu sammeln, eine IR vor dem Inlining analysieren.

Aus diesem Grund kann analyze_escapes IRCode auf jeder Optimierungsstufe von Julia analysieren, und insbesondere soll es in den folgenden beiden Phasen verwendet werden:

  • IPO EA: Analysiere die IR vor dem Inlining, um einen IPO-gültigen Escape-Informationscache zu generieren.
  • Local EA: Analysiere Post-Inlining-IR, um lokal gültige Escape-Informationen zu sammeln.

Die durch IPO EA abgeleiteten Escape-Informationen werden in die Datenstruktur ArgEscapeCache umgewandelt und global zwischengespeichert. Durch das Übergeben eines geeigneten get_escape_cache-Callbacks an analyze_escapes kann die Escape-Analyse die Analysegenauigkeit verbessern, indem sie zwischengespeicherte inter-prozedurale Informationen von nicht-inlineden Aufrufern nutzt, die durch vorherige IPO EA abgeleitet wurden. Interessanterweise ist es auch gültig, die Escape-Informationen von IPO EA für die Typinferenz zu verwenden, z. B. kann die Inferenzgenauigkeit verbessert werden, indem Const/PartialStruct/MustAlias von veränderlichen Objekten gebildet werden.

Core.Compiler.EscapeAnalysis.analyze_escapes — Function
analyze_escapes(ir::IRCode, nargs::Int, get_escape_cache) -> estate::EscapeState

Analysiert Fluchtinformationen in ir:

  • nargs: die Anzahl der tatsächlichen Argumente des analysierten Aufrufs
  • get_escape_cache(::MethodInstance) -> Union{Bool,ArgEscapeCache}: ruft zwischengespeicherte Fluchtinformationen für Argumente ab
source
Core.Compiler.EscapeAnalysis.EscapeState — Type
estate::EscapeState

Erweiterter Gitter, das Argumente und SSA-Werte auf Fluchtinformationen abbildet, die als EscapeInfo dargestellt sind. Fluchtinformationen, die auf das SSA-IR-Element x angewendet werden, können durch estate[x] abgerufen werden.

source
Core.Compiler.EscapeAnalysis.EscapeInfo — Type
x::EscapeInfo

Ein Gitter für Fluchtinformationen, das die folgenden Eigenschaften enthält:

  • x.Analyzed::Bool: nicht formell Teil des Gitters, zeigt nur an, ob x analysiert wurde

  • x.ReturnEscape::Bool: zeigt an, dass x über die Rückgabe zum Aufrufer entkommen kann

  • x.ThrownEscape::BitSet: zeichnet SSA-Anweisungsnummern auf, an denen x als Ausnahme geworfen werden kann:

    • isempty(x.ThrownEscape): x wird in diesem Aufrufrahmen niemals geworfen (das Minimum)
    • pc ∈ x.ThrownEscape: x kann an der SSA-Anweisung bei pc geworfen werden
    • -1 ∈ x.ThrownEscape: x kann an beliebigen Punkten dieses Aufrufrahmens geworfen werden (das Maximum)

    Diese Informationen werden von escape_exception! verwendet, um potenzielle Fluchten über Ausnahmen zu propagieren.

  • x.AliasInfo::Union{Bool,IndexableFields,IndexableElements,Unindexable}: verwaltet alle möglichen Werte, die auf Felder oder Array-Elemente von x aliasiert werden können:

    • x.AliasInfo === false zeigt an, dass die Felder/Elemente von x noch nicht analysiert wurden
    • x.AliasInfo === true zeigt an, dass die Felder/Elemente von x nicht analysiert werden können, z. B. ist der Typ von x nicht bekannt oder nicht konkret, und daher können seine Felder/Elemente nicht genau bekannt sein
    • x.AliasInfo::IndexableFields zeichnet alle möglichen Werte auf, die auf Felder des Objekts x mit präzisen Indexinformationen aliasiert werden können
    • x.AliasInfo::IndexableElements zeichnet alle möglichen Werte auf, die auf Elemente des Arrays x mit präzisen Indexinformationen aliasiert werden können
    • x.AliasInfo::Unindexable zeichnet alle möglichen Werte auf, die auf Felder/Elemente von x ohne präzise Indexinformationen aliasiert werden können

  • x.Liveness::BitSet: zeichnet SSA-Anweisungsnummern auf, an denen x lebendig sein sollte, z. B. um als Aufrufargument verwendet zu werden, um an einen Aufrufer zurückgegeben zu werden oder für :foreigncall erhalten zu bleiben:

    • isempty(x.Liveness): x wird in diesem Aufrufrahmen niemals verwendet (das Minimum)
    • 0 ∈ x.Liveness hat auch die besondere Bedeutung, dass es ein Aufrufargument des derzeit analysierten Aufrufrahmens ist (und somit sofort vom Aufrufer sichtbar ist).
    • pc ∈ x.Liveness: x kann an der SSA-Anweisung bei pc verwendet werden
    • -1 ∈ x.Liveness: x kann an beliebigen Punkten dieses Aufrufrahmens verwendet werden (das Maximum)

Es gibt Hilfskonstruktoren, um gängige EscapeInfos zu erstellen, z. B.:

  • NoEscape(): das Minimum(-ähnliche) Element dieses Gitters, was bedeutet, dass es nirgendwohin entkommen wird
  • AllEscape(): das oberste Element dieses Gitters, was bedeutet, dass es überallhin entkommen wird

analyze_escapes wird diese Elemente vom Minimum zum Maximum überführen, in die gleiche Richtung wie Julias native Typinferenzroutine. Ein abstrakter Zustand wird mit den Minimum(-ähnlichen) Elementen initialisiert:

  • die Aufrufargumente werden als ArgEscape() initialisiert, dessen Liveness-Eigenschaft 0 enthält, um anzuzeigen, dass es als Aufrufargument übergeben wird und sofort vom Aufrufer sichtbar ist
  • die anderen Zustände werden als NotAnalyzed() initialisiert, was ein spezielles Gitterelement ist, das etwas niedriger als NoEscape ist, aber gleichzeitig keine andere Bedeutung hat, als dass es noch nicht analysiert wurde (und somit nicht formell Teil des Gitters ist)
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.