GitHub

EscapeAnalysis

Core.Compiler.EscapeAnalysis est un module utilitaire du compilateur qui vise à analyser les informations d'évasion de Julia's SSA-form IR, également connu sous le nom de IRCode.

Cette analyse d'évasion vise à :

  • tirer parti de la sémantique de haut niveau de Julia, en particulier raisonner sur les échappements et l'aliasing via des appels inter-procédures
  • soyez suffisamment polyvalent pour être utilisé pour diverses optimisations, y compris alias-aware SROA, early finalize insertion, copy-free ImmutableArray construction, allocation de pile d'objets mutables, et ainsi de suite.
  • réaliser une implémentation simple basée sur une analyse de flux de données entièrement rétrograde ainsi qu'un nouveau design de treillis qui combine des propriétés de treillis orthogonales

Try it out!

Vous pouvez essayer l'analyse d'évasion en chargeant le script utilitaire EAUtils.jl qui définit les entrées de commodité code_escapes et @code_escapes à des fins de test et de débogage :

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

Les symboles sur le côté de chaque argument d'appel et des déclarations SSA représentent la signification suivante :

  • ◌ (plain) : cette valeur n'est pas analysée car les informations d'échappement ne seront de toute façon pas utilisées (lorsque l'objet est isbitstype par exemple)
  • ✓ (vert ou cyan) : cette valeur ne s'échappe jamais (has_no_escape(result.state[x]) est vrai), coloré en bleu si elle a également une échappée d'argument (has_arg_escape(result.state[x]) est vrai)
  • ↑ (bleu ou jaune) : cette valeur peut s'échapper vers l'appelant via le retour (has_return_escape(result.state[x]) est vrai), coloré en jaune si elle a également une échappée lancée non gérée (has_thrown_escape(result.state[x]) est vrai)
  • X (rouge) : cette valeur peut s'échapper vers un endroit que l'analyse d'évasion ne peut pas raisonner, comme des évasions vers une mémoire globale (has_all_escape(result.state[x]) est vrai)
  • * (gras) : l'état d'échappement de cette valeur se situe entre le ReturnEscape et le AllEscape dans l'ordre partiel de EscapeInfo, coloré en jaune s'il a un échappement lancé non géré également (has_thrown_escape(result.state[x]) est vrai)
  • ′: cette valeur a des informations supplémentaires sur le champ d'objet / l'élément de tableau dans sa propriété AliasInfo

Les informations d'échappement de chaque argument d'appel et de chaque valeur SSA peuvent être inspectées de manière programmatique comme suit :

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 est implémenté comme un data-flow analysis qui fonctionne sur un réseau de x::EscapeInfo, qui est composé des propriétés suivantes :

  • x.Analyzed::Bool : pas formellement partie de la structure de treillis, indique seulement que x n'a pas été analysé ou non.
  • x.ReturnEscape::BitSet: enregistre les instructions SSA où x peut s'échapper vers l'appelant via le retour
  • x.ThrownEscape::BitSet : enregistre les instructions SSA où x peut être lancé comme exception (utilisé pour le exception handling décrit ci-dessous)
  • x.AliasInfo: maintains all possible values that can be aliased to fields or array elements of x (used for the alias analysis described below)
  • x.ArgEscape::Int (pas encore implémenté) : indique qu'il s'échappera vers l'appelant via setfield! sur l'argument(s)

Ces attributs peuvent être combinés pour créer un treillis partiel qui a une hauteur finie, étant donné l'invariant qu'un programme d'entrée a un nombre fini d'instructions, ce qui est assuré par la sémantique de Julia. La partie astucieuse de ce design de treillis est qu'elle permet une mise en œuvre plus simple des opérations de treillis en leur permettant de gérer chaque propriété de treillis séparément[LatticeDesign].

Backward Escape Propagation

Cette implémentation de l'analyse d'échappement est basée sur l'algorithme de flux de données décrit dans l'article[MM02]. L'analyse fonctionne sur la structure de EscapeInfo et fait passer les éléments de la structure du bas vers le haut jusqu'à ce que chaque élément de la structure converge vers un point fixe en maintenant un ensemble de travail (conceptuel) qui contient des compteurs de programme correspondant aux instructions SSA restantes à analyser. L'analyse gère un état global unique qui suit EscapeInfo de chaque argument et instruction SSA, mais note également qu'une certaine sensibilité au flux est codée sous forme de compteurs de programme enregistrés dans la propriété ReturnEscape de EscapeInfo, qui peuvent être combinés avec l'analyse de domination par la suite pour raisonner sur la sensibilité au flux si nécessaire.

Un design distinctif de cette analyse d'évasion est qu'elle est entièrement rétrograde, c'est-à-dire que les informations d'évasion circulent des utilisations vers les définitions. Par exemple, dans l'extrait de code ci-dessous, l'AE analyse d'abord l'instruction return %1 et impose ReturnEscape sur %1 (correspondant à obj), puis elle analyse %1 = %new(Base.RefValue{String, _2})) et propage le ReturnEscape imposé sur %1 à l'argument d'appel _2 (correspondant à 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

L'observation clé ici est que cette analyse rétrograde permet à l'information d'évasion de circuler naturellement le long de la chaîne d'utilisation-définition plutôt que le flux de contrôle[BackandForth]. En conséquence, ce schéma permet une mise en œuvre simple de l'analyse d'évasion, par exemple, PhiNode peut être géré simplement en propageant l'information d'évasion imposée sur un PhiNode à ses valeurs prédécesseurs :

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 implémente une analyse de champ en arrière pour raisonner sur les échappements imposés aux champs d'objet avec une certaine précision, et la propriété x.AliasInfo de x::EscapeInfo existe à cette fin. Elle enregistre toutes les valeurs possibles qui peuvent être aliasées aux champs de x aux sites de "utilisation", puis les informations d'échappement de ces valeurs enregistrées sont propagées aux valeurs de champ réelles plus tard aux sites de "définition". Plus précisément, l'analyse enregistre une valeur qui peut être aliasée à un champ d'objet en analysant l'appel getfield, puis elle propage ses informations d'échappement au champ lors de l'analyse de l'expression %new(...) ou de l'appel 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

Dans l'exemple ci-dessus, ReturnEscape imposé sur %3 (correspondant à v) n'est pas directement propagé à %1 (correspondant à obj), mais plutôt que ReturnEscape est seulement propagé à _2 (correspondant à s). Ici, %3 est enregistré dans la propriété AliasInfo de %1 car il peut être aliasé au premier champ de %1, et ensuite, lors de l'analyse de Base.setfield!(%1, :x, _2)::String, cette information d'évasion est propagée à _2 mais pas à %1.

Donc EscapeAnalysis suit quels éléments IR peuvent être aliasés à travers une chaîne getfield-%new/setfield! afin d'analyser les échappements des champs d'objet, mais en réalité, cette analyse d'alias doit être généralisée pour gérer d'autres éléments IR également. Cela est dû au fait qu'en IR Julia, le même objet est parfois représenté par différents éléments IR et nous devons donc nous assurer que ces différents éléments IR qui peuvent en réalité représenter le même objet partagent les mêmes informations d'échappement. Les éléments IR qui retournent le même objet que leur(s) opérande(s), tels que PiNode et typeassert, peuvent provoquer cet aliasing au niveau IR et nécessitent donc que les informations d'échappement imposées à l'un de ces valeurs aliasées soient partagées entre elles. Plus intéressant encore, cela est également nécessaire pour raisonner correctement sur les mutations sur PhiNode. Considérons l'exemple suivant :

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 et ϕ2 = %6 sont aliasés et donc ReturnEscape imposé sur %8 = Base.getfield(%6, :x)::String (correspondant à y = ϕ1[]) doit être propagé à Base.setfield!(%5, :x, _3)::String (correspondant à ϕ2[] = x). Afin que ces informations d'évasion soient propagées correctement, l'analyse doit reconnaître que les prédécesseurs de ϕ1 et ϕ2 peuvent également être aliasés et égaliser leurs informations d'évasion.

Une propriété intéressante de ces informations d'aliasing est qu'elles ne sont pas connues au site de "utilisation" mais ne peuvent être dérivées qu'au site de "définition" (car l'aliasing est conceptuellement équivalent à une affectation), et donc cela ne s'intègre pas naturellement dans une analyse rétrograde. Afin de propager efficacement les informations d'évasion entre des valeurs liées, EscapeAnalysis.jl utilise une approche inspirée de l'algorithme d'analyse d'évasion expliqué dans un ancien article de la JVM[JVM05]. C'est-à-dire qu'en plus de gérer les éléments de la lattique d'évasion, l'analyse maintient également un ensemble d'alias "équi", un ensemble disjoint d'arguments et d'instructions SSA aliasés. L'ensemble d'alias gère les valeurs qui peuvent être aliasées les unes aux autres et permet d'égaliser les informations d'évasion imposées à l'une de ces valeurs aliasées entre elles.

Array Analysis

L'analyse des alias pour les champs d'objet décrite ci-dessus peut également être généralisée pour analyser les opérations sur les tableaux. EscapeAnalysis implémente des gestions pour diverses opérations de tableau primitives afin qu'il puisse propager les échappements via la chaîne d'utilisation-définition arrayref-arrayset et ne pas échapper aux tableaux alloués de manière trop conservatrice :

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

Dans l'exemple ci-dessus, EscapeAnalysis comprend que %20 et %2 (correspondant à l'objet alloué SafeRef(s)) sont aliasés via la chaîne arrayset-arrayref et impose ReturnEscape sur eux, mais ne l'impose pas sur le tableau alloué %1 (correspondant à ary). EscapeAnalysis impose toujours ThrownEscape sur ary car il doit également tenir compte des échappements potentiels via BoundsError, mais notez également que de tels ThrownEscape non gérés peuvent souvent être ignorés lors de l'optimisation de l'allocation de ary.

De plus, dans les cas où les informations sur les indices de tableau ainsi que les dimensions du tableau peuvent être connues précisément, EscapeAnalysis est capable de raisonner même sur l'aliasing "par élément" via la chaîne arrayref-arrayset, tout comme EscapeAnalysis effectue une analyse d'alias "par champ" pour les objets :

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

Notez que ReturnEscape n'est imposé que sur %2 (correspondant à SafeRef(s)) mais pas sur %4 (correspondant à SafeRef(t)). Cela est dû au fait que la dimension du tableau alloué et les indices impliqués dans toutes les opérations arrayref/arrayset sont disponibles en tant qu'informations constantes et que EscapeAnalysis peut comprendre que %6 est aliasé à %2 mais ne peut jamais être aliasé à %4. Dans ce genre de cas, les passes d'optimisation suivantes seront capables de remplacer Base.arrayref(true, %1, 1)::Any par %2 (également connu sous le nom de "load-forwarding") et finalement d'éliminer complètement l'allocation du tableau %1 (également connu sous le nom de "scalar-replacement").

Lorsqu'on compare l'analyse des champs d'objet, où un accès à un champ d'objet peut être analysé de manière triviale en utilisant des informations de type dérivées par inférence, la dimension des tableaux n'est pas encodée comme information de type et nous avons donc besoin d'une analyse supplémentaire pour en dériver cette information. EscapeAnalysis à ce moment effectue d'abord un simple scan linéaire supplémentaire pour analyser les dimensions des tableaux alloués avant de lancer la routine principale d'analyse afin que l'analyse d'échappement suivante puisse analyser précisément les opérations sur ces tableaux.

Cependant, une telle analyse d'alias "par élément" précise est souvent difficile. Essentiellement, la principale difficulté inhérente aux tableaux est que la dimension et l'index du tableau sont souvent non constants :

  • la boucle produit souvent des indices de tableau non constants et variant de boucle
  • (specific to vectors) le redimensionnement d'un tableau change la dimension du tableau et invalide sa constance.

Discutons de ces difficultés avec des exemples concrets.

Dans l'exemple suivant, EscapeAnalysis échoue l'analyse d'alias précise puisque l'index à Base.arrayset(false, %4, %8, %6)::Vector{Any} n'est pas (triviellement) constant. En particulier, Any[nothing, nothing] forme une boucle et appelle cette opération arrayset dans une boucle, où %6 est représenté comme une valeur de nœud ϕ (dont la valeur dépend du flux de contrôle). En conséquence, ReturnEscape se retrouve imposé à la fois sur %23 (correspondant à SafeRef(s)) et %25 (correspondant à SafeRef(t)), bien qu'idéalement nous souhaitions qu'il soit imposé uniquement sur %23 mais pas sur %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

L'exemple suivant illustre comment le redimensionnement des vecteurs rend l'analyse des alias précise difficile. La difficulté essentielle est que la dimension du tableau alloué %1 est d'abord initialisée à 0, mais elle change par les deux appels :jl_array_grow_end par la suite. EscapeAnalysis abandonne actuellement simplement l'analyse des alias précise chaque fois qu'il rencontre des opérations de redimensionnement de tableau et donc ReturnEscape est imposé à la fois sur %2 (correspondant à SafeRef(s)) et %20 (correspondant à SafeRef(t)):

julia> code_escapes((String,String)) do s, t
           ary = Any[]
           push!(ary, SafeRef(s))
           push!(ary, SafeRef(t))
           ary[1], length(ary)
       end#17(X s::String, X t::String) in Main at REPL[1]:2
X  1 ── %1  = Core.getproperty(Memory{Any}, :instance)::Memory{Any}
X  │    %2  = invoke Core.memoryref(%1::Memory{Any})::MemoryRef{Any}
X  │    %3  = %new(Vector{Any}, %2, (0,))::Vector{Any}
X  │    %4  = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
X  │    %5  = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %6  = Base.getfield(%5, :mem)::Memory{Any}
X  │    %7  = Base.getfield(%6, :length)::Int64
X  │    %8  = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %9  = $(Expr(:boundscheck, true))::Bool
X  │    %10 = Base.getfield(%8, 1, %9)::Int64
◌  │    %11 = Base.add_int(%10, 1)::Int64
◌  │    %12 = Base.memoryrefoffset(%5)::Int64
X  │    %13 = Core.tuple(%11)::Tuple{Int64}
◌  │          Base.setfield!(%3, :size, %13)::Tuple{Int64}
◌  │    %15 = Base.add_int(%12, %11)::Int64
◌  │    %16 = Base.sub_int(%15, 1)::Int64
◌  │    %17 = Base.slt_int(%7, %16)::Bool
◌  └───       goto #3 if not %17
X  2 ── %19 = %new(Base.var"#133#134"{Vector{Any}, Int64, Int64, Int64, Int64, Int64, Memory{Any}, MemoryRef{Any}}, %3, %16, %12, %11, %10, %7, %6, %5)::Base.var"#133#134"{Vector{Any}, Int64, Int64, Int64, Int64, Int64, Memory{Any}, MemoryRef{Any}}
✓  └───       invoke %19()::MemoryRef{Any}
◌  3 ┄─       goto #4
X  4 ── %22 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %23 = $(Expr(:boundscheck, true))::Bool
X  │    %24 = Base.getfield(%22, 1, %23)::Int64
X  │    %25 = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %26 = Base.memoryrefnew(%25, %24, false)::MemoryRef{Any}
X  │          Base.memoryrefset!(%26, %4, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #5
X  5 ── %29 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
X  │    %30 = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %31 = Base.getfield(%30, :mem)::Memory{Any}
X  │    %32 = Base.getfield(%31, :length)::Int64
X  │    %33 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %34 = $(Expr(:boundscheck, true))::Bool
X  │    %35 = Base.getfield(%33, 1, %34)::Int64
◌  │    %36 = Base.add_int(%35, 1)::Int64
◌  │    %37 = Base.memoryrefoffset(%30)::Int64
X  │    %38 = Core.tuple(%36)::Tuple{Int64}
◌  │          Base.setfield!(%3, :size, %38)::Tuple{Int64}
◌  │    %40 = Base.add_int(%37, %36)::Int64
◌  │    %41 = Base.sub_int(%40, 1)::Int64
◌  │    %42 = Base.slt_int(%32, %41)::Bool
◌  └───       goto #7 if not %42
X  6 ── %44 = %new(Base.var"#133#134"{Vector{Any}, Int64, Int64, Int64, Int64, Int64, Memory{Any}, MemoryRef{Any}}, %3, %41, %37, %36, %35, %32, %31, %30)::Base.var"#133#134"{Vector{Any}, Int64, Int64, Int64, Int64, Int64, Memory{Any}, MemoryRef{Any}}
✓  └───       invoke %44()::MemoryRef{Any}
◌  7 ┄─       goto #8
X  8 ── %47 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %48 = $(Expr(:boundscheck, true))::Bool
X  │    %49 = Base.getfield(%47, 1, %48)::Int64
X  │    %50 = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %51 = Base.memoryrefnew(%50, %49, false)::MemoryRef{Any}
X  │          Base.memoryrefset!(%51, %29, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #9
◌  9 ── %54 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #13 if not %54
◌  10 ─ %56 = Base.sub_int(1, 1)::Int64
◌  │    %57 = Base.bitcast(Base.UInt, %56)::UInt64
X  │    %58 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %59 = $(Expr(:boundscheck, true))::Bool
X  │    %60 = Base.getfield(%58, 1, %59)::Int64
◌  │    %61 = Base.bitcast(Base.UInt, %60)::UInt64
◌  │    %62 = Base.ult_int(%57, %61)::Bool
◌  └───       goto #12 if not %62
◌  11 ─       goto #13
◌  12 ─ %65 = Core.tuple(1)::Tuple{Int64}
✓  │          invoke Base.throw_boundserror(%3::Vector{Any}, %65::Tuple{Int64})::Union{}
◌  └───       unreachable
X  13 ┄ %68 = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %69 = Base.memoryrefnew(%68, 1, false)::MemoryRef{Any}
X  │    %70 = Base.memoryrefget(%69, :not_atomic, false)::Any
◌  └───       goto #14
X  14 ─ %72 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %73 = $(Expr(:boundscheck, true))::Bool
X  │    %74 = Base.getfield(%72, 1, %73)::Int64
↑′ │    %75 = Core.tuple(%70, %74)::Tuple{Any, Int64}
◌  └───       return %75

Pour résoudre ces difficultés, nous devons faire en sorte que l'inférence prenne en compte les dimensions des tableaux et propage les dimensions des tableaux de manière sensible au flux[ArrayDimension], ainsi que proposer une belle représentation des valeurs variant en boucle.

EscapeAnalysis à ce moment passe rapidement à l'analyse plus imprécise qui ne suit pas les informations d'index précises dans les cas où les dimensions du tableau ou les indices ne sont trivialement pas constants. Le changement peut naturellement être implémenté comme une opération de jointure de treillis de la propriété EscapeInfo.AliasInfo dans le cadre d'analyse de flux de données.

Exception Handling

Il convient également de noter comment EscapeAnalysis gère les éventuelles échappées via des exceptions. Naïvement, il semble suffisant de propager les informations d'échappement imposées sur l'objet :the_exception à toutes les valeurs qui peuvent être lancées dans un bloc try correspondant. Mais il existe en réalité plusieurs autres façons d'accéder à l'objet d'exception dans Julia, telles que Base.current_exceptions et rethrow. Par exemple, l'analyse d'échappement doit tenir compte de l'échappement potentiel de r dans l'exemple ci-dessous :

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

Cela nécessite une analyse globale afin de raisonner correctement sur toutes les échappatoires possibles via les interfaces d'exception existantes. Pour l'instant, nous propagons toujours les informations d'échappatoire les plus élevées à tous les objets potentiellement lancés de manière conservatrice, car une telle analyse supplémentaire pourrait ne pas valoir la peine d'être effectuée étant donné que la gestion des exceptions et les chemins d'erreur n'ont généralement pas besoin d'être très sensibles à la performance, et que les optimisations des chemins d'erreur pourraient de toute façon être très inefficaces, car elles sont souvent même "non optimisées" intentionnellement pour des raisons de latence.

x::EscapeInfo's x.ThrownEscape propriété enregistre les instructions SSA où x peut être lancé en tant qu'exception. En utilisant cette information, EscapeAnalysis peut propager les échappements possibles via des exceptions de manière limitée uniquement à ceux qui peuvent être lancés dans chaque région 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 est le point d'entrée pour analyser les informations d'évasion des éléments SSA-IR.

La plupart des optimisations comme SROA (sroa_pass!) sont plus efficaces lorsqu'elles sont appliquées à une source optimisée que le passage d'inlining (ssa_inlining_pass!) a simplifiée en résolvant les appels inter-procédures et en développant les sources des fonctions appelées. En conséquence, analyze_escapes est également capable d'analyser l'IR post-inlining et de collecter des informations sur les échappements qui sont utiles pour certaines optimisations liées à la mémoire.

Cependant, comme certaines passes d'optimisation comme l'inlining peuvent modifier les flux de contrôle et éliminer le code mort, elles peuvent rompre la validité inter-procédurale des informations d'échappement. En particulier, pour collecter des informations d'échappement valides inter-procéduralement, nous devons analyser un IR pré-inlining.

Pour cette raison, analyze_escapes peut analyser IRCode à n'importe quel stade d'optimisation au niveau de Julia, et en particulier, il est censé être utilisé aux deux étapes suivantes :

  • IPO EA : analyser l'IR pré-inlining pour générer un cache d'informations d'échappement valide pour l'IPO
  • Local EA : analyser l'IR post-inlining pour collecter des informations d'échappement valides localement.

Les informations d'évasion dérivées par IPO EA sont transformées en la structure de données ArgEscapeCache et mises en cache globalement. En passant un rappel approprié get_escape_cache à analyze_escapes, l'analyse des évasions peut améliorer la précision de l'analyse en utilisant les informations inter-procédurales mises en cache des appelés non inlinés qui ont été dérivées par le précédent IPO EA. Plus intéressant encore, il est également valide d'utiliser les informations d'évasion IPO EA pour l'inférence de type, par exemple, la précision de l'inférence peut être améliorée en formant Const/PartialStruct/MustAlias d'un objet mutable.

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

Analyse les informations d'échappement dans ir :

  • nargs : le nombre d'arguments réels de l'appel analysé
  • get_escape_cache(::MethodInstance) -> Union{Bool,ArgEscapeCache} : récupère les informations d'échappement des arguments mises en cache
source
Core.Compiler.EscapeAnalysis.EscapeState — Type
estate::EscapeState

Lattice étendu qui associe des arguments et des valeurs SSA à des informations d'évasion représentées sous la forme de EscapeInfo. Les informations d'évasion imposées sur l'élément IR SSA x peuvent être récupérées par estate[x].

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

Une structure pour les informations d'évasion, qui possède les propriétés suivantes :

  • x.Analyzed::Bool : pas formellement partie de la structure, indique seulement si x a été analysé

  • x.ReturnEscape::Bool : indique que x peut s'échapper vers l'appelant via le retour

  • x.ThrownEscape::BitSet : enregistre les numéros d'instruction SSA où x peut être lancé comme exception :

    • isempty(x.ThrownEscape) : x ne sera jamais lancé dans ce cadre d'appel (le bas)
    • pc ∈ x.ThrownEscape : x peut être lancé à l'instruction SSA à pc
    • -1 ∈ x.ThrownEscape : x peut être lancé à des points arbitraires de ce cadre d'appel (le haut)

    Cette information sera utilisée par escape_exception! pour propager les évasions potentielles via exception.

  • x.AliasInfo::Union{Bool,IndexableFields,IndexableElements,Unindexable} : maintient toutes les valeurs possibles qui peuvent être aliasées aux champs ou éléments de tableau de x :

    • x.AliasInfo === false indique que les champs/éléments de x n'ont pas encore été analysés
    • x.AliasInfo === true indique que les champs/éléments de x ne peuvent pas être analysés, par exemple, le type de x n'est pas connu ou n'est pas concret et donc ses champs/éléments ne peuvent pas être connus précisément
    • x.AliasInfo::IndexableFields enregistre toutes les valeurs possibles qui peuvent être aliasées aux champs de l'objet x avec des informations d'index précises
    • x.AliasInfo::IndexableElements enregistre toutes les valeurs possibles qui peuvent être aliasées aux éléments du tableau x avec des informations d'index précises
    • x.AliasInfo::Unindexable enregistre toutes les valeurs possibles qui peuvent être aliasées aux champs/éléments de x sans informations d'index précises

  • x.Liveness::BitSet : enregistre les numéros d'instruction SSA où x devrait être vivant, par exemple, pour être utilisé comme argument d'appel, pour être retourné à un appelant, ou préservé pour :foreigncall :

    • isempty(x.Liveness) : x n'est jamais utilisé dans ce cadre d'appel (le bas)
    • 0 ∈ x.Liveness a également la signification spéciale qu'il s'agit d'un argument d'appel du cadre d'appel actuellement analysé (et donc il est visible de l'appelant immédiatement).
    • pc ∈ x.Liveness : x peut être utilisé à l'instruction SSA à pc
    • -1 ∈ x.Liveness : x peut être utilisé à des points arbitraires de ce cadre d'appel (le haut)

Il existe des constructeurs utilitaires pour créer des EscapeInfo communs, par exemple :

  • NoEscape() : l'élément du bas (comme) de cette structure, signifiant qu'il ne s'échappera nulle part
  • AllEscape() : l'élément le plus haut de cette structure, signifiant qu'il s'échappera partout

analyze_escapes fera passer ces éléments du bas vers le haut, dans la même direction que la routine d'inférence de type native de Julia. Un état abstrait sera initialisé avec les éléments du bas (comme) :

  • les arguments d'appel sont initialisés comme ArgEscape(), dont la propriété Liveness inclut 0 pour indiquer qu'il est passé comme argument d'appel et visible immédiatement d'un appelant
  • les autres états sont initialisés comme NotAnalyzed(), qui est un élément de structure spécial qui est légèrement inférieur à NoEscape, mais en même temps ne représente aucune signification autre que le fait qu'il n'a pas encore été analysé (donc il ne fait pas formellement partie de la structure)
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.