GitHub

EscapeAnalysis

Core.Compiler.EscapeAnalysis es un módulo de utilidad del compilador que tiene como objetivo analizar la información de escape de Julia's SSA-form IR, también conocido como IRCode.

Este análisis de escape tiene como objetivo:

  • aprovechar la semántica de alto nivel de Julia, especialmente razonar sobre escapes y aliasing a través de llamadas inter-procedurales
  • ser lo suficientemente versátil como para ser utilizado para varias optimizaciones, incluyendo alias-aware SROA, early finalize insertion, copy-free ImmutableArray construction, la asignación de pila de objetos mutables, y así sucesivamente.
  • lograr una implementación simple basada en una implementación de análisis de flujo de datos completamente hacia atrás, así como un nuevo diseño de reticulado que combine propiedades de reticulado ortogonales.

Try it out!

Puedes intentar el análisis de escape cargando el script de utilidad EAUtils.jl que define las entradas de conveniencia code_escapes y @code_escapes para fines de prueba y depuración:

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

Los símbolos al lado de cada argumento de llamada y las declaraciones SSA representan el siguiente significado:

  • ◌ (plano): este valor no se analiza porque la información de escape de él no se utilizará de todos modos (cuando el objeto es isbitstype, por ejemplo)
  • ✓ (verde o cian): este valor nunca escapa (has_no_escape(result.state[x]) se cumple), coloreado de azul si también tiene escape de argumento (has_arg_escape(result.state[x]) se cumple)
  • ↑ (azul o amarillo): este valor puede escapar al llamador a través de la devolución (has_return_escape(result.state[x]) se mantiene), coloreado de amarillo si también tiene una fuga lanzada no manejada (has_thrown_escape(result.state[x]) se mantiene)
  • X (rojo): este valor puede escapar a algún lugar sobre el cual el análisis de escape no puede razonar, como escapes a una memoria global (has_all_escape(result.state[x]) se cumple)
  • * (negrita): el estado de escape de este valor está entre el ReturnEscape y AllEscape en el orden parcial de EscapeInfo, coloreado de amarillo si tiene un escape lanzado no manejado también (has_thrown_escape(result.state[x]) se cumple)
  • ′: este valor tiene información adicional sobre el campo de objeto / elemento de matriz en su propiedad AliasInfo

La información de escape de cada argumento de llamada y valor SSA se puede inspeccionar programáticamente de la siguiente manera:

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 se implementa como un data-flow analysis que trabaja en una red de x::EscapeInfo, que se compone de las siguientes propiedades:

  • x.Analyzed::Bool: no forma parte formalmente de la red, solo indica si x no ha sido analizado o no.
  • x.ReturnEscape::BitSet: registra declaraciones SSA donde x puede escapar al llamador a través de la devolución
  • x.ThrownEscape::BitSet: registra declaraciones SSA donde x puede ser lanzado como excepción (utilizado para el exception handling descrito a continuación)
  • x.AliasInfo: mantiene todos los posibles valores que pueden ser alias a campos o elementos de array de x (utilizado para el alias analysis descrito a continuación)
  • x.ArgEscape::Int (no implementado aún): indica que se escapará al llamador a través de setfield! en el/los argumento(s)

Estos atributos se pueden combinar para crear un reticulado parcial que tiene una altura finita, dado el invariante de que un programa de entrada tiene un número finito de declaraciones, lo cual está asegurado por la semántica de Julia. La parte ingeniosa de este diseño de reticulado es que permite una implementación más simple de las operaciones de reticulado al permitir que manejen cada propiedad del reticulado por separado[LatticeDesign].

Backward Escape Propagation

Esta implementación de análisis de escape se basa en el algoritmo de flujo de datos descrito en el artículo[MM02]. El análisis trabaja en la red de EscapeInfo y transiciona los elementos de la red desde la parte inferior hasta la parte superior hasta que cada elemento de la red converge a un punto fijo, manteniendo un conjunto de trabajo (conceptual) que contiene contadores de programa correspondientes a las declaraciones SSA restantes que deben ser analizadas. El análisis gestiona un único estado global que rastrea EscapeInfo de cada argumento y declaración SSA, pero también se debe tener en cuenta que cierta sensibilidad al flujo está codificada como contadores de programa registrados en la propiedad ReturnEscape de EscapeInfo, que se puede combinar con el análisis de dominación más adelante para razonar sobre la sensibilidad al flujo si es necesario.

Un diseño distintivo de este análisis de escape es que es completamente hacia atrás, es decir, la información de escape fluye de los usos a las definiciones. Por ejemplo, en el fragmento de código a continuación, EA primero analiza la declaración return %1 e impone ReturnEscape sobre %1 (correspondiente a obj), y luego analiza %1 = %new(Base.RefValue{String, _2})) y propaga el ReturnEscape impuesto sobre %1 al argumento de llamada _2 (correspondiente a 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

La observación clave aquí es que este análisis hacia atrás permite que la información de escape fluya naturalmente a lo largo de la cadena de uso-definición en lugar de a través del flujo de control[BackandForth]. Como resultado, este esquema permite una implementación simple del análisis de escape; por ejemplo, PhiNode puede ser manejado simplemente propagando la información de escape impuesta en un PhiNode a sus valores predecesores:

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 implementa un análisis de campo hacia atrás para razonar sobre las escapadas impuestas en los campos de objeto con cierta precisión, y la propiedad x.AliasInfo de x::EscapeInfo existe para este propósito. Registra todos los valores posibles que pueden estar aliasados a los campos de x en los sitios de "uso", y luego la información de escape de esos valores registrados se propaga a los valores de campo reales más tarde en los sitios de "definición". Más específicamente, el análisis registra un valor que puede estar aliasado a un campo de objeto al analizar la llamada getfield, y luego propaga su información de escape al campo al analizar la expresión %new(...) o la llamada 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

En el ejemplo anterior, ReturnEscape impuesto sobre %3 (correspondiente a v) no se propaga directamente a %1 (correspondiente a obj), sino que ReturnEscape solo se propaga a _2 (correspondiente a s). Aquí, %3 se registra en la propiedad AliasInfo de %1 ya que puede ser alias de el primer campo de %1, y luego, al analizar Base.setfield!(%1, :x, _2)::String, esa información de escape se propaga a _2 pero no a %1.

Así que EscapeAnalysis rastrea qué elementos de IR pueden ser aliasados a través de una cadena getfield-%new/setfield! para analizar las escapadas de los campos de objeto, pero en realidad este análisis de alias necesita ser generalizado para manejar otros elementos de IR también. Esto se debe a que en IR de Julia el mismo objeto a veces se representa mediante diferentes elementos de IR y, por lo tanto, debemos asegurarnos de que esos diferentes elementos de IR que realmente pueden representar el mismo objeto compartan la misma información de escape. Los elementos de IR que devuelven el mismo objeto como su(s) operando(s), como PiNode y typeassert, pueden causar ese aliasing a nivel de IR y, por lo tanto, requieren que la información de escape impuesta sobre cualquiera de esos valores aliasados se comparta entre ellos. Más interesante aún, también es necesario para razonar correctamente sobre las mutaciones en PhiNode. Consideremos el siguiente ejemplo:

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 y ϕ2 = %6 están aliasados y, por lo tanto, ReturnEscape impuesto sobre %8 = Base.getfield(%6, :x)::String (correspondiente a y = ϕ1[]) necesita ser propagado a Base.setfield!(%5, :x, _3)::String (correspondiente a ϕ2[] = x). Para que dicha información de escape se propague correctamente, el análisis debe reconocer que los predecesores de ϕ1 y ϕ2 también pueden estar aliasados y igualar su información de escape.

Una propiedad interesante de dicha información de aliasing es que no se conoce en el sitio de "uso", sino que solo se puede derivar en el sitio de "definición" (ya que el aliasing es conceptualmente equivalente a la asignación), y por lo tanto no se ajusta naturalmente a un análisis hacia atrás. Para propagar de manera eficiente la información de escape entre valores relacionados, EscapeAnalysis.jl utiliza un enfoque inspirado en el algoritmo de análisis de escape explicado en un viejo artículo de JVM[JVM05]. Es decir, además de gestionar elementos de la red de escape, el análisis también mantiene un conjunto de alias "equi", un conjunto disjunto de argumentos y declaraciones SSA aliasados. El conjunto de alias gestiona valores que pueden estar aliasados entre sí y permite que la información de escape impuesta sobre cualquiera de esos valores aliasados se iguale entre ellos.

Array Analysis

El análisis de alias para los campos de objeto descrito anteriormente también se puede generalizar para analizar operaciones de arreglos. EscapeAnalysis implementa manejos para varias operaciones de arreglos primitivos de modo que puede propagar escapes a través de la cadena de uso-definición arrayref-arrayset y no escapa arreglos asignados de manera demasiado conservadora:

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

En el ejemplo anterior, EscapeAnalysis entiende que %20 y %2 (correspondientes al objeto asignado SafeRef(s)) están aliasados a través de la cadena arrayset-arrayref y les impone ReturnEscape, pero no lo impone en el arreglo asignado %1 (correspondiente a ary). EscapeAnalysis aún impone ThrownEscape en ary ya que también necesita tener en cuenta posibles escapes a través de BoundsError, pero también hay que notar que tal ThrownEscape no manejado a menudo puede ser ignorado al optimizar la asignación de ary.

Además, en los casos en que la información del índice del arreglo, así como las dimensiones del arreglo, se pueden conocer precisamente, EscapeAnalysis es capaz de razonar incluso sobre el aliasing "por elemento" a través de la cadena arrayref-arrayset, ya que EscapeAnalysis realiza un análisis de alias "por campo" para objetos:

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

Tenga en cuenta que ReturnEscape solo se impone en %2 (correspondiente a SafeRef(s)) pero no en %4 (correspondiente a SafeRef(t)). Esto se debe a que la dimensión del array asignado y los índices involucrados en todas las operaciones arrayref/arrayset están disponibles como información constante y EscapeAnalysis puede entender que %6 está aliasado a %2 pero nunca está aliasado a %4. En este tipo de caso, los pases de optimización sucesivos podrán reemplazar Base.arrayref(true, %1, 1)::Any con %2 (también conocido como "carga hacia adelante") y eventualmente eliminar la asignación del array %1 por completo (también conocido como "reemplazo escalar").

Cuando se compara con el análisis de campos de objetos, donde un acceso a un campo de objeto puede ser analizado de manera trivial utilizando información de tipo derivada por inferencia, la dimensión de un arreglo no está codificada como información de tipo y, por lo tanto, necesitamos un análisis adicional para derivar esa información. EscapeAnalysis en este momento primero realiza un escaneo lineal simple adicional para analizar las dimensiones de los arreglos asignados antes de activar la rutina principal de análisis, de modo que el análisis de escape subsiguiente pueda analizar con precisión las operaciones en esos arreglos.

Sin embargo, tal análisis de alias "por elemento" tan preciso a menudo es difícil. Esencialmente, la principal dificultad inherente a los arreglos es que la dimensión del arreglo y el índice a menudo son no constantes:

  • el bucle a menudo produce índices de matriz no constantes y variantes del bucle
  • (el específico para vectores) el cambio de tamaño de la matriz modifica la dimensión de la matriz e invalida su constancia.

Hablemos de esas dificultades con ejemplos concretos.

En el siguiente ejemplo, EscapeAnalysis falla en el análisis de alias preciso ya que el índice en Base.arrayset(false, %4, %8, %6)::Vector{Any} no es (trivialmente) constante. Especialmente, Any[nothing, nothing] forma un bucle y llama a esa operación arrayset en un bucle, donde %6 se representa como un valor de nodo ϕ (cuyo valor depende del flujo de control). Como resultado, ReturnEscape termina imponiéndose tanto en %23 (correspondiente a SafeRef(s)) como en %25 (correspondiente a SafeRef(t)), aunque idealmente queremos que se imponga solo en %23 pero no en %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

El siguiente ejemplo ilustra cómo el cambio de tamaño de un vector dificulta el análisis de alias preciso. La dificultad esencial es que la dimensión del arreglo asignado %1 se inicializa primero como 0, pero cambia con las dos llamadas :jl_array_grow_end posteriormente. EscapeAnalysis actualmente simplemente renuncia al análisis de alias preciso cada vez que encuentra operaciones de cambio de tamaño de arreglos y, por lo tanto, se impone ReturnEscape tanto en %2 (correspondiente a SafeRef(s)) como en %20 (correspondiente a 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

Para abordar estas dificultades, necesitamos que la inferencia sea consciente de las dimensiones de los arreglos y propague las dimensiones de los arreglos de manera sensible al flujo[ArrayDimension], así como también idear una buena representación de los valores variantes del bucle.

EscapeAnalysis en este momento cambia rápidamente a un análisis más impreciso que no rastrea información de índice precisa en casos en los que las dimensiones del arreglo o los índices son trivialmente no constantes. El cambio se puede implementar naturalmente como una operación de unión de reticulado de la propiedad EscapeInfo.AliasInfo en el marco de análisis de flujo de datos.

Exception Handling

También vale la pena señalar cómo EscapeAnalysis maneja posibles escapes a través de excepciones. A primera vista, parece suficiente propagar la información de escape impuesta sobre el objeto :the_exception a todos los valores que pueden ser lanzados en un bloque try correspondiente. Pero en realidad, hay varias otras formas de acceder al objeto de excepción en Julia, como Base.current_exceptions y rethrow. Por ejemplo, el análisis de escape necesita tener en cuenta el posible escape de r en el ejemplo a continuación:

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

Requiere un análisis global para razonar correctamente sobre todas las posibles salidas a través de las interfaces de excepción existentes. Por ahora, siempre propagamos la información de escape más alta a todos los objetos que podrían lanzarse de manera conservadora, ya que un análisis adicional podría no valer la pena realizarlo dado que el manejo de excepciones y las rutas de error generalmente no necesitan ser muy sensibles al rendimiento, y además, las optimizaciones de las rutas de error podrían ser muy ineficaces de todos modos, ya que a menudo están incluso "no optimizadas" intencionalmente por razones de latencia.

La propiedad x.ThrownEscape de x::EscapeInfo registra las declaraciones SSA donde x puede ser lanzado como una excepción. Usando esta información, EscapeAnalysis puede propagar posibles escapes a través de excepciones de manera limitada solo a aquellos que pueden ser lanzados en cada región 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 es el punto de entrada para analizar la información de escape de los elementos SSA-IR.

La mayoría de las optimizaciones como SROA (sroa_pass!) son más efectivas cuando se aplican a un código fuente optimizado que el paso de inlining (ssa_inlining_pass!) ha simplificado al resolver llamadas inter-procedimentales y expandir las fuentes de los llamados. En consecuencia, analyze_escapes también puede analizar IR posterior al inlining y recopilar información sobre escapes que es útil para ciertas optimizaciones relacionadas con la memoria.

Sin embargo, dado que ciertos pases de optimización como la inlining pueden cambiar los flujos de control y eliminar código muerto, pueden romper la validez inter-procedimental de la información de escape. En particular, para recopilar información de escape válida inter-procedimentalmente, necesitamos analizar un IR previo a la inlining.

Debido a esta razón, analyze_escapes puede analizar IRCode en cualquier etapa de optimización a nivel de Julia, y especialmente, se supone que debe usarse en las siguientes dos etapas:

  • IPO EA: analizar IR previo a la inlining para generar caché de información de escape válida para IPO
  • Local EA: analizar IR post-inlining para recopilar información de escape localmente válida

La información de escape derivada por IPO EA se transforma en la estructura de datos ArgEscapeCache y se almacena en caché globalmente. Al pasar un callback apropiado get_escape_cache a analyze_escapes, el análisis de escape puede mejorar la precisión del análisis al utilizar información interprocedimental en caché de llamadas no inlinadas que ha sido derivada por el anterior IPO EA. Más interesante aún, también es válido utilizar la información de escape de IPO EA para la inferencia de tipos, por ejemplo, la precisión de la inferencia puede mejorarse formando Const/PartialStruct/MustAlias de un objeto mutable.

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

Analiza la información de escape en ir:

  • nargs: el número de argumentos reales de la llamada analizada
  • get_escape_cache(::MethodInstance) -> Union{Bool,ArgEscapeCache}: recupera la información de escape de argumento en caché
source
Core.Compiler.EscapeAnalysis.EscapeInfo — Type
x::EscapeInfo

Una red para información de escape, que tiene las siguientes propiedades:

  • x.Analyzed::Bool: no es parte formal de la red, solo indica si x ha sido analizado

  • x.ReturnEscape::Bool: indica que x puede escapar al llamador a través de un retorno

  • x.ThrownEscape::BitSet: registra los números de declaración SSA donde x puede ser lanzado como excepción:

    • isempty(x.ThrownEscape): x nunca será lanzado en este marco de llamada (el fondo)
    • pc ∈ x.ThrownEscape: x puede ser lanzado en la declaración SSA en pc
    • -1 ∈ x.ThrownEscape: x puede ser lanzado en puntos arbitrarios de este marco de llamada (la parte superior)

    Esta información será utilizada por escape_exception! para propagar escapes potenciales a través de excepciones.

  • x.AliasInfo::Union{Bool,IndexableFields,IndexableElements,Unindexable}: mantiene todos los posibles valores que pueden ser referenciados a campos o elementos de arreglo de x:

    • x.AliasInfo === false indica que los campos/elementos de x aún no han sido analizados
    • x.AliasInfo === true indica que los campos/elementos de x no pueden ser analizados, por ejemplo, el tipo de x no es conocido o no es concreto y, por lo tanto, sus campos/elementos no pueden ser conocidos con precisión
    • x.AliasInfo::IndexableFields registra todos los posibles valores que pueden ser referenciados a campos del objeto x con información de índice precisa
    • x.AliasInfo::IndexableElements registra todos los posibles valores que pueden ser referenciados a elementos del arreglo x con información de índice precisa
    • x.AliasInfo::Unindexable registra todos los posibles valores que pueden ser referenciados a campos/elementos de x sin información de índice precisa

  • x.Liveness::BitSet: registra los números de declaración SSA donde x debería estar vivo, por ejemplo, para ser utilizado como argumento de llamada, para ser devuelto a un llamador, o preservado para :foreigncall:

    • isempty(x.Liveness): x nunca será utilizado en este marco de llamada (el fondo)
    • 0 ∈ x.Liveness también tiene el significado especial de que es un argumento de llamada del marco de llamada actualmente analizado (y por lo tanto es visible desde el llamador inmediatamente).
    • pc ∈ x.Liveness: x puede ser utilizado en la declaración SSA en pc
    • -1 ∈ x.Liveness: x puede ser utilizado en puntos arbitrarios de este marco de llamada (la parte superior)

Hay constructores utilitarios para crear EscapeInfos comunes, por ejemplo,

  • NoEscape(): el elemento inferior (similar) de esta red, lo que significa que no escapará a ningún lugar
  • AllEscape(): el elemento más alto de esta red, lo que significa que escapará a todas partes

analyze_escapes hará la transición de estos elementos del fondo a la parte superior, en la misma dirección que la rutina de inferencia de tipos nativa de Julia. Un estado abstracto será inicializado con los elementos inferiores (similares):

  • los argumentos de llamada se inicializan como ArgEscape(), cuya propiedad Liveness incluye 0 para indicar que se pasa como un argumento de llamada y es visible desde un llamador inmediatamente
  • los otros estados se inicializan como NotAnalyzed(), que es un elemento de red especial que es ligeramente inferior a NoEscape, pero al mismo tiempo no representa ningún significado más allá de que aún no ha sido analizado (por lo tanto, no es parte formal de la red)
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.