GitHub

EscapeAnalysis

Core.Compiler.EscapeAnalysis — это модуль утилиты компилятора, который предназначен для анализа информации о выходе Julia's SSA-form IR, также известного как IRCode.

Этот анализ побега направлен на:

  • использовать высокоуровневую семантику Julia, особенно рассматривать побеги и алиасинг через межпроцедурные вызовы
  • быть достаточно универсальным, чтобы использоваться для различных оптимизаций, включая alias-aware SROA, early finalize insertion, copy-free ImmutableArray construction, стековое выделение изменяемых объектов и так далее.
  • достигнуть простой реализации на основе полностью обратного анализа данных, а также нового проектирования решётки, которое сочетает в себе ортогональные свойства решётки

Try it out!

Вы можете попробовать анализ утечек, загрузив утилитный скрипт EAUtils.jl, который определяет удобные записи code_escapes и @code_escapes для тестирования и отладки:

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

Символы сбоку от каждого аргумента вызова и операторов SSA представляют следующее значение:

  • ◌ (plain): это значение не анализируется, потому что информация об экранировании в любом случае не будет использована (например, когда объект является isbitstype)
  • ✓ (зеленый или циановый): это значение никогда не уходит (has_no_escape(result.state[x]) верно), окрашено в синий, если также есть аргумент уходит (has_arg_escape(result.state[x]) верно)
  • ↑ (синий или желтый): это значение может выйти к вызывающему через возврат (has_return_escape(result.state[x]) истинно), окрашено в желтый, если также есть необработанное выброшенное значение (has_thrown_escape(result.state[x]) истинно)
  • X (красный): это значение может уйти куда-то, о чем анализ побегов не может рассуждать, например, уйти в глобальную память (has_all_escape(result.state[x]) верно)
  • * (жирный): состояние экранирования этого значения находится между ReturnEscape и AllEscape в частичном порядке EscapeInfo, окрашено в желтый, если оно имеет необработанное выброшенное экранирование также (has_thrown_escape(result.state[x]) истинно)
  • ′: это значение имеет дополнительную информацию о поле объекта / элементе массива в его свойстве AliasInfo

Информацию о каждом аргументе вызова и значении SSA можно просмотреть программно, как:

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

Analysis Design

Lattice Design

EscapeAnalysis реализован как data-flow analysis, который работает на решетке x::EscapeInfo, которая состоит из следующих свойств:

  • x.Analyzed::Bool: не является формальной частью решетки, только указывает на то, что x не был проанализирован или нет
  • x.ReturnEscape::BitSet: записывает SSA-операторы, где x может выйти к вызывающему через возврат
  • x.ThrownEscape::BitSet: записывает SSA-операторы, где x может быть выброшен как исключение (используется для exception handling, описанного ниже)
  • x.AliasInfo: поддерживает все возможные значения, которые могут быть алиасированы к полям или элементам массива x (используется для alias analysis, описанного ниже)
  • x.ArgEscape::Int (пока не реализовано): указывает, что оно будет передано вызывающему через setfield! на аргумент(ах)

Эти атрибуты можно комбинировать для создания частичной решетки, которая имеет конечную высоту, при условии, что входная программа имеет конечное количество операторов, что гарантируется семантикой Julia. Умная часть этого дизайна решетки заключается в том, что она позволяет более простой реализации операций решетки, позволяя им обрабатывать каждое свойство решетки отдельно[LatticeDesign].

Backward Escape Propagation

Этот вариант реализации анализа выхода основан на алгоритме потоков данных, описанном в статье[MM02]. Анализ работает на решетке EscapeInfo и переводит элементы решетки снизу вверх, пока каждый элемент решетки не сойдется к фиксированной точке, поддерживая (концептуальный) рабочий набор, который содержит счетчики программы, соответствующие оставшимся инструкциям SSA, которые необходимо проанализировать. Анализ управляет единственным глобальным состоянием, которое отслеживает EscapeInfo каждого аргумента и инструкции SSA, но также следует отметить, что некоторый потокочувствительный анализ закодирован в счетчиках программы, записанных в свойстве ReturnEscape EscapeInfo, которые могут быть объединены с анализом доминирования позже для обоснования потокочувствительности, если это необходимо.

Одним из отличительных дизайнов этого анализа выхода является то, что он полностью обратный, т.е. информация о выходе течет от использований к определениям. Например, в приведенном ниже фрагменте кода EA сначала анализирует оператор return %1 и накладывает ReturnEscape на %1 (соответствующий obj), а затем анализирует %1 = %new(Base.RefValue{String, _2})) и распространяет ReturnEscape, наложенный на %1, на аргумент вызова _2 (соответствующий s):

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

Ключевое наблюдение здесь заключается в том, что этот обратный анализ позволяет информации о выходе естественным образом течь вдоль цепочки использования-определения, а не по потоку управления[BackandForth]. В результате эта схема позволяет просто реализовать анализ выхода, например, PhiNode можно просто обрабатывать, распространяя информацию о выходе, наложенную на PhiNode, на его предшествующие значения:

julia> code_escapes((Bool, String, String)) do cnd, s, t
           if cnd
               obj = Ref(s)
           else
               obj = Ref(t)
           end
           return obj
       end#5(✓ cnd::Bool, ↑ s::String, ↑ t::String) in Main at REPL[1]:2
◌  1 ─      goto #3 if not _2
↑′ 2 ─ %2 = %new(Base.RefValue{String}, _3)::Base.RefValue{String}
◌  └──      goto #4
↑′ 3 ─ %4 = %new(Base.RefValue{String}, _4)::Base.RefValue{String}
↑′ 4 ┄ %5 = φ (#2 => %2, #3 => %4)::Base.RefValue{String}
◌  └──      return %5

Alias Analysis

EscapeAnalysis реализует обратный анализ полей для того, чтобы рассуждать о побегах, накладываемых на поля объектов с определенной точностью, и свойство x::EscapeInfo's x.AliasInfo существует для этой цели. Оно записывает все возможные значения, которые могут быть алиасированы к полям x на "местах использования", а затем информация о побегах этих записанных значений распространяется на фактические значения полей позже на "местах определения". Более конкретно, анализ записывает значение, которое может быть алиасировано к полю объекта, анализируя вызов getfield, а затем распространяет его информацию о побегах на поле при анализе выражения %new(...) или вызова setfield![Dynamism].

julia> code_escapes((String,)) do s
           obj = SafeRef("init")
           obj[] = s
           v = obj[]
           return v
       end#7(↑ s::String) in Main at REPL[1]:2
◌  1 ─     return _2

В приведенном примере ReturnEscape, наложенный на %3 (соответствующий v), не передается напрямую на %1 (соответствующий obj), а скорее ReturnEscape передается только на _2 (соответствующий s). Здесь %3 записывается в свойстве AliasInfo %1, так как он может быть связан с первым полем %1, и затем, при анализе Base.setfield!(%1, :x, _2)::String, эта информация о выходе передается на _2, но не на %1.

Итак, EscapeAnalysis отслеживает, какие элементы IR могут быть алиасированы в цепочке getfield-%new/setfield!, чтобы проанализировать утечки полей объектов, но на самом деле этот анализ алиасов необходимо обобщить, чтобы обрабатывать и другие элементы IR. Это связано с тем, что в IR Julia один и тот же объект иногда представляется разными элементами IR, и поэтому мы должны убедиться, что эти разные элементы IR, которые на самом деле могут представлять один и тот же объект, имеют одинаковую информацию о утечках. Элементы IR, которые возвращают один и тот же объект в качестве своих операндов, такие как PiNode и typeassert, могут вызывать алиасинг на уровне IR и, следовательно, требуют, чтобы информация о утечках, наложенная на любые из таких алиасированных значений, была общей между ними. Более интересно, это также необходимо для правильного рассуждения о мутациях на PhiNode. Рассмотрим следующий пример:

julia> code_escapes((Bool, String,)) do cond, x
           if cond
               ϕ2 = ϕ1 = SafeRef("foo")
           else
               ϕ2 = ϕ1 = SafeRef("bar")
           end
           ϕ2[] = x
           y = ϕ1[]
           return y
       end#9(✓ cond::Bool, ↑ x::String) in Main at REPL[1]:2
◌  1 ─      goto #3 if not _2
✓′ 2 ─ %2 = %new(Main.SafeRef{String}, "foo")::Main.SafeRef{String}
◌  └──      goto #4
✓′ 3 ─ %4 = %new(Main.SafeRef{String}, "bar")::Main.SafeRef{String}
✓′ 4 ┄ %5 = φ (#2 => %2, #3 => %4)::Main.SafeRef{String}
✓′ │   %6 = φ (#2 => %2, #3 => %4)::Main.SafeRef{String}
◌  │        Base.setfield!(%5, :x, _3)::String
↑  │   %8 = Base.getfield(%6, :x)::String
◌  └──      return %8

ϕ1 = %5 и ϕ2 = %6 являются алиасами, и поэтому ReturnEscape, наложенный на %8 = Base.getfield(%6, :x)::String (соответствующий y = ϕ1[]), необходимо распространить на Base.setfield!(%5, :x, _3)::String (соответствующий ϕ2[] = x). Для того чтобы такая информация об уходе была правильно распространена, анализ должен распознать, что предшественники ϕ1 и ϕ2 также могут быть алиасами и уравнять их информацию об уходе.

Одним из интересных свойств такой информации об алиасах является то, что она не известна на сайте "использования", но может быть получена только на сайте "определения" (так как алиасинг концептуально эквивалентен присваиванию), и, следовательно, она не подходит для обратного анализа. Для эффективного распространения информации об эскейпе между связанными значениями EscapeAnalysis.jl использует подход, вдохновленный алгоритмом анализа эскейпа, объясненным в старой статье по JVM[JVM05]. То есть, помимо управления элементами решетки эскейпа, анализ также поддерживает набор "эквивалентных" алиасов, раздельный набор алиасированных аргументов и операторов SSA. Набор алиасов управляет значениями, которые могут быть алиасированы друг к другу, и позволяет уравнивать информацию об эскейпе, наложенную на любое из таких алиасированных значений, между ними.

Array Analysis

Анализ алиасов для полей объектов, описанный выше, также можно обобщить для анализа операций с массивами. EscapeAnalysis реализует обработку различных примитивных операций с массивами, чтобы он мог распространять утечки через цепочку использования-определения arrayref-arrayset и не утекал выделенные массивы слишком консервативно:

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

В приведенном выше примере EscapeAnalysis понимает, что %20 и %2 (соответствующие выделенному объекту SafeRef(s)) являются алиасами через цепочку arrayset-arrayref и накладывает на них ReturnEscape, но не накладывает его на выделенный массив %1 (соответствующий ary). EscapeAnalysis все еще накладывает ThrownEscape на ary, поскольку также необходимо учитывать потенциальные утечки через BoundsError, но также стоит отметить, что такие необработанные ThrownEscape часто можно игнорировать при оптимизации выделения ary.

Кроме того, в случаях, когда информация об индексах массива, а также размеры массива могут быть известны точно, EscapeAnalysis может даже рассуждать о "поэлементном" алиасинге через цепочку arrayref-arrayset, так как EscapeAnalysis выполняет анализ алиасов "по полям" для объектов:

julia> code_escapes((String,String)) do s, t
           ary = Vector{Any}(undef, 2)
           ary[1] = SafeRef(s)
           ary[2] = SafeRef(t)
           return ary[1], length(ary)
       end#13(X s::String, X t::String) in Main at REPL[1]:2
X  1 ── %1  = $(Expr(:foreigncall, :(:jl_alloc_genericmemory), Ref{Memory{Any}}, svec(Any, Int64), 0, :(:ccall), Memory{Any}, 2, 2))::Memory{Any}
X  │    %2  = Core.memoryrefnew(%1)::MemoryRef{Any}
X  │    %3  = %new(Vector{Any}, %2, (2,))::Vector{Any}
X  │    %4  = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
◌  │    %5  = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #5 if not %5
◌  2 ── %7  = Base.sub_int(1, 1)::Int64
◌  │    %8  = Base.bitcast(Base.UInt, %7)::UInt64
X  │    %9  = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %10 = $(Expr(:boundscheck, true))::Bool
X  │    %11 = Base.getfield(%9, 1, %10)::Int64
◌  │    %12 = Base.bitcast(Base.UInt, %11)::UInt64
◌  │    %13 = Base.ult_int(%8, %12)::Bool
◌  └───       goto #4 if not %13
◌  3 ──       goto #5
◌  4 ── %16 = Core.tuple(1)::Tuple{Int64}
✓  │          invoke Base.throw_boundserror(%3::Vector{Any}, %16::Tuple{Int64})::Union{}
◌  └───       unreachable
X  5 ┄─ %19 = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %20 = Base.memoryrefnew(%19, 1, false)::MemoryRef{Any}
X  │          Base.memoryrefset!(%20, %4, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #6
X  6 ── %23 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
◌  │    %24 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #10 if not %24
◌  7 ── %26 = Base.sub_int(2, 1)::Int64
◌  │    %27 = Base.bitcast(Base.UInt, %26)::UInt64
X  │    %28 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %29 = $(Expr(:boundscheck, true))::Bool
X  │    %30 = Base.getfield(%28, 1, %29)::Int64
◌  │    %31 = Base.bitcast(Base.UInt, %30)::UInt64
◌  │    %32 = Base.ult_int(%27, %31)::Bool
◌  └───       goto #9 if not %32
◌  8 ──       goto #10
◌  9 ── %35 = Core.tuple(2)::Tuple{Int64}
✓  │          invoke Base.throw_boundserror(%3::Vector{Any}, %35::Tuple{Int64})::Union{}
◌  └───       unreachable
X  10 ┄ %38 = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %39 = Base.memoryrefnew(%38, 2, false)::MemoryRef{Any}
X  │          Base.memoryrefset!(%39, %23, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #11
◌  11 ─ %42 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #15 if not %42
◌  12 ─ %44 = Base.sub_int(1, 1)::Int64
◌  │    %45 = Base.bitcast(Base.UInt, %44)::UInt64
X  │    %46 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %47 = $(Expr(:boundscheck, true))::Bool
X  │    %48 = Base.getfield(%46, 1, %47)::Int64
◌  │    %49 = Base.bitcast(Base.UInt, %48)::UInt64
◌  │    %50 = Base.ult_int(%45, %49)::Bool
◌  └───       goto #14 if not %50
◌  13 ─       goto #15
◌  14 ─ %53 = Core.tuple(1)::Tuple{Int64}
✓  │          invoke Base.throw_boundserror(%3::Vector{Any}, %53::Tuple{Int64})::Union{}
◌  └───       unreachable
X  15 ┄ %56 = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %57 = Base.memoryrefnew(%56, 1, false)::MemoryRef{Any}
X  │    %58 = Base.memoryrefget(%57, :not_atomic, false)::Any
◌  └───       goto #16
X  16 ─ %60 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %61 = $(Expr(:boundscheck, true))::Bool
X  │    %62 = Base.getfield(%60, 1, %61)::Int64
↑′ │    %63 = Core.tuple(%58, %62)::Tuple{Any, Int64}
◌  └───       return %63

Обратите внимание, что ReturnEscape применяется только к %2 (соответствующему SafeRef(s)), но не к %4 (соответствующему SafeRef(t)). Это связано с тем, что размерность выделенного массива и индексы, участвующие во всех операциях arrayref/arrayset, доступны как постоянная информация, и EscapeAnalysis может понять, что %6 ссылается на %2, но никогда не будет ссылаться на %4. В таком случае последующие оптимизационные проходы смогут заменить Base.arrayref(true, %1, 1)::Any на %2 (так называемая "перемотка загрузки") и в конечном итоге полностью устранить выделение массива %1 (так называемая "замена скаляров").

Когда сравнивать с анализом полей объектов, где доступ к полю объекта может быть проанализирован тривиально с использованием информации о типе, полученной путем вывода, размерность массива не закодирована как информация о типе, и поэтому нам нужен дополнительный анализ для получения этой информации. EscapeAnalysis в данный момент сначала выполняет дополнительный простой линейный проход для анализа размерностей выделенных массивов, прежде чем запустить основную рутинную процедуру анализа, чтобы последующий анализ утечек мог точно анализировать операции с этими массивами.

Однако такая точная "поэлементная" анализ алиасов часто бывает сложной. По сути, основная трудность, присущая массивам, заключается в том, что размерность массива и индекс часто являются неконстантными:

  • цикл часто производит изменяющиеся, неконстантные индексы массива
  • (специфично для векторов) изменение размера массива изменяет размерность массива и делает его неконстантным

Давайте обсудим эти трудности на конкретных примерах.

В следующем примере EscapeAnalysis не проходит точный анализ алиасов, поскольку индекс в Base.arrayset(false, %4, %8, %6)::Vector{Any} не является (тривиально) константным. Особенно Any[nothing, nothing] образует цикл и вызывает эту операцию arrayset в цикле, где %6 представлен как значение ϕ-узла (значение которого зависит от управления потоком). В результате ReturnEscape накладывается на оба %23 (соответствующий SafeRef(s)) и %25 (соответствующий SafeRef(t)), хотя в идеале мы хотим, чтобы он накладывался только на %23, но не на %25:

julia> code_escapes((String,String)) do s, t
           ary = Any[nothing, nothing]
           ary[1] = SafeRef(s)
           ary[2] = SafeRef(t)
           return ary[1], length(ary)
       end#15(X s::String, X t::String) in Main at REPL[1]:2
X  1 ── %1  = $(Expr(:foreigncall, :(:jl_alloc_genericmemory), Ref{Memory{Any}}, svec(Any, Int64), 0, :(:ccall), Memory{Any}, 2, 2))::Memory{Any}
X  │    %2  = Core.memoryrefnew(%1)::MemoryRef{Any}
X  └─── %3  = %new(Vector{Any}, %2, (2,))::Vector{Any}
◌  2 ┄─ %4  = φ (#1 => 1, #6 => %14)::Int64
◌  │    %5  = φ (#1 => 1, #6 => %15)::Int64
X  │    %6  = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %7  = Base.memoryrefnew(%6, %4, false)::MemoryRef{Any}
◌  │          Base.memoryrefset!(%7, nothing, :not_atomic, false)::Nothing
◌  │    %9  = (%5 === 2)::Bool
◌  └───       goto #4 if not %9
◌  3 ──       goto #5
◌  4 ── %12 = Base.add_int(%5, 1)::Int64
◌  └───       goto #5
◌  5 ┄─ %14 = φ (#4 => %12)::Int64
◌  │    %15 = φ (#4 => %12)::Int64
◌  │    %16 = φ (#3 => true, #4 => false)::Bool
◌  │    %17 = Base.not_int(%16)::Bool
◌  └───       goto #7 if not %17
◌  6 ──       goto #2
◌  7 ──       goto #8
X  8 ── %21 = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
◌  │    %22 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #12 if not %22
◌  9 ── %24 = Base.sub_int(1, 1)::Int64
◌  │    %25 = Base.bitcast(Base.UInt, %24)::UInt64
X  │    %26 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %27 = $(Expr(:boundscheck, true))::Bool
X  │    %28 = Base.getfield(%26, 1, %27)::Int64
◌  │    %29 = Base.bitcast(Base.UInt, %28)::UInt64
◌  │    %30 = Base.ult_int(%25, %29)::Bool
◌  └───       goto #11 if not %30
◌  10 ─       goto #12
◌  11 ─ %33 = Core.tuple(1)::Tuple{Int64}
✓  │          invoke Base.throw_boundserror(%3::Vector{Any}, %33::Tuple{Int64})::Union{}
◌  └───       unreachable
X  12 ┄ %36 = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %37 = Base.memoryrefnew(%36, 1, false)::MemoryRef{Any}
X  │          Base.memoryrefset!(%37, %21, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #13
X  13 ─ %40 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
◌  │    %41 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #17 if not %41
◌  14 ─ %43 = Base.sub_int(2, 1)::Int64
◌  │    %44 = Base.bitcast(Base.UInt, %43)::UInt64
X  │    %45 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %46 = $(Expr(:boundscheck, true))::Bool
X  │    %47 = Base.getfield(%45, 1, %46)::Int64
◌  │    %48 = Base.bitcast(Base.UInt, %47)::UInt64
◌  │    %49 = Base.ult_int(%44, %48)::Bool
◌  └───       goto #16 if not %49
◌  15 ─       goto #17
◌  16 ─ %52 = Core.tuple(2)::Tuple{Int64}
✓  │          invoke Base.throw_boundserror(%3::Vector{Any}, %52::Tuple{Int64})::Union{}
◌  └───       unreachable
X  17 ┄ %55 = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %56 = Base.memoryrefnew(%55, 2, false)::MemoryRef{Any}
X  │          Base.memoryrefset!(%56, %40, :not_atomic, false)::Main.SafeRef{String}
◌  └───       goto #18
◌  18 ─ %59 = $(Expr(:boundscheck, true))::Bool
◌  └───       goto #22 if not %59
◌  19 ─ %61 = Base.sub_int(1, 1)::Int64
◌  │    %62 = Base.bitcast(Base.UInt, %61)::UInt64
X  │    %63 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %64 = $(Expr(:boundscheck, true))::Bool
X  │    %65 = Base.getfield(%63, 1, %64)::Int64
◌  │    %66 = Base.bitcast(Base.UInt, %65)::UInt64
◌  │    %67 = Base.ult_int(%62, %66)::Bool
◌  └───       goto #21 if not %67
◌  20 ─       goto #22
◌  21 ─ %70 = Core.tuple(1)::Tuple{Int64}
✓  │          invoke Base.throw_boundserror(%3::Vector{Any}, %70::Tuple{Int64})::Union{}
◌  └───       unreachable
X  22 ┄ %73 = Base.getfield(%3, :ref)::MemoryRef{Any}
X  │    %74 = Base.memoryrefnew(%73, 1, false)::MemoryRef{Any}
X  │    %75 = Base.memoryrefget(%74, :not_atomic, false)::Any
◌  └───       goto #23
X  23 ─ %77 = Base.getfield(%3, :size)::Tuple{Int64}
◌  │    %78 = $(Expr(:boundscheck, true))::Bool
X  │    %79 = Base.getfield(%77, 1, %78)::Int64
↑′ │    %80 = Core.tuple(%75, %79)::Tuple{Any, Int64}
◌  └───       return %80

Следующий пример иллюстрирует, как изменение размера векторов усложняет точный анализ алиасов. Основная трудность заключается в том, что размер выделенного массива %1 сначала инициализируется как 0, но затем изменяется двумя вызовами :jl_array_grow_end. В настоящее время EscapeAnalysis просто отказывается от точного анализа алиасов, когда сталкивается с любыми операциями изменения размера массива, и поэтому ReturnEscape накладывается на оба %2 (соответствующий SafeRef(s)) и %20 (соответствующий SafeRef(t)):

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

Чтобы справиться с этими трудностями, нам нужно, чтобы вывод был осведомлён о размерах массивов и передавал размеры массивов в зависимости от потока[ArrayDimension], а также придумал хорошее представление для значений, зависящих от цикла.

EscapeAnalysis в данный момент быстро переключается на более неточный анализ, который не отслеживает точную информацию об индексах в случаях, когда размеры массивов или индексы тривиально не константны. Переключение можно естественно реализовать как операцию объединения решеток свойства EscapeInfo.AliasInfo в рамках анализа потоков данных.

Exception Handling

Стоит также отметить, как EscapeAnalysis обрабатывает возможные утечки через исключения. Наивно кажется, что достаточно распространить информацию об утечках, наложенную на объект :the_exception, на все значения, которые могут быть выброшены в соответствующем блоке try. Но на самом деле существует несколько других способов доступа к объекту исключения в Julia, таких как Base.current_exceptions и rethrow. Например, анализ утечек должен учитывать потенциальную утечку r в приведенном ниже примере:

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

Требуется глобальный анализ, чтобы правильно рассуждать обо всех возможных выходах через существующие интерфейсы исключений. На данный момент мы всегда консервативно передаем информацию о самом верхнем выходе всем потенциально выбрасываемым объектам, поскольку такой дополнительный анализ может не стоить того, учитывая, что обработка исключений и пути ошибок обычно не требуют высокой производительности, а также оптимизации путей ошибок могут быть очень неэффективными, поскольку они часто даже "неоптимизированы" намеренно по причинам задержки.

x::EscapeInfo свойство x.ThrownEscape записывает SSA-операторы, где x может быть выброшен как исключение. Используя эту информацию, EscapeAnalysis может ограниченно распространять возможные утечки через исключения только на те, которые могут быть выброшены в каждом регионе try:

julia> result = code_escapes((String,String)) do s1, s2
           r1 = Ref(s1)
           r2 = Ref(s2)
           local ret
           try
               s1 = get′(r1)
               ret = sizeof(s1)
           catch err
               global GV = err # will definitely escape `r1`
           end
           s2 = get′(r2)       # still `r2` doesn't escape fully
           return s2
       end#21(X s1::String, ↑ s2::String) in Main at REPL[1]:2
X  1 ── %1  = %new(Base.RefValue{String}, _2)::Base.RefValue{String}
*′ └─── %2  = %new(Base.RefValue{String}, _3)::Base.RefValue{String}
*′ 2 ── %3  = ϒ (%2)::Base.RefValue{String}
◌  └─── %4  = enter #8
◌  3 ── %5  = Base.isdefined(%1, :x)::Bool
◌  └───       goto #5 if not %5
X  4 ──       Base.getfield(%1, :x)::String
◌  └───       goto #6
◌  5 ──       Main.throw(%1)::Union{}
◌  └───       unreachable
◌  6 ──       $(Expr(:leave, :(%4)))
◌  7 ──       goto #11
*′ 8 ┄─ %13 = φᶜ (%3)::Base.RefValue{String}
X  └─── %14 = $(Expr(:the_exception))::Any
◌  9 ──       nothing::Nothing
◌  10 ─       (Main.GV = %14)::Any
◌  └───       $(Expr(:pop_exception, :(%4)))::Core.Const(nothing)
*′ 11 ┄ %18 = φ (#7 => %2, #10 => %13)::Base.RefValue{String}
◌  │    %19 = Base.isdefined(%18, :x)::Bool
◌  └───       goto #13 if not %19
↑  12 ─ %21 = Base.getfield(%18, :x)::String
◌  └───       goto #14
◌  13 ─       Main.throw(%18)::Union{}
◌  └───       unreachable
◌  14 ─       return %21

Analysis Usage

analyze_escapes является точкой входа для анализа информации об экранировании элементов SSA-IR.

Большинство оптимизаций, таких как SROA (sroa_pass!), более эффективны, когда применяются к оптимизированному исходному коду, который упрощен проходом инлайнинга (ssa_inlining_pass!) за счет разрешения межпроцедурных вызовов и расширения источников вызываемых функций. Соответственно, analyze_escapes также может анализировать IR после инлайнинга и собирать информацию об утечках, которая полезна для определенных оптимизаций, связанных с памятью.

Однако, поскольку определенные оптимизационные проходы, такие как инлайнинг, могут изменять потоки управления и устранять мертвый код, они могут нарушить межпроцедурную корректность информации о выходе. В частности, для того чтобы собрать межпроцедурно корректную информацию о выходе, нам необходимо проанализировать IR до инлайнинга.

По этой причине analyze_escapes может анализировать IRCode на любом уровне оптимизации Julia, и особенно его предполагается использовать на следующих двух этапах:

  • IPO EA: анализировать IR до инлайнинга для генерации кэша информации об эскейпах, действительного для IPO
  • Local EA: анализировать IR после инлайнинга для сбора локально-валидной информации об утечках

Информация о побегах, полученная с помощью IPO EA, преобразуется в структуру данных ArgEscapeCache и кэшируется глобально. Передавая соответствующий обратный вызов get_escape_cache в analyze_escapes, анализ побегов может улучшить точность анализа, используя кэшированную межпроцедурную информацию о неинлайненных вызываемых функциях, полученную в результате предыдущего IPO EA. Более интересно, что также допустимо использовать информацию о побегах IPO EA для вывода типов, например, точность вывода может быть улучшена за счет формирования Const/PartialStruct/MustAlias изменяемого объекта.

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

Анализирует информацию об эскапах в ir:

  • nargs: количество фактических аргументов анализируемого вызова
  • get_escape_cache(::MethodInstance) -> Union{Bool,ArgEscapeCache}: извлекает кэшированную информацию об эскапах аргументов
source
Core.Compiler.EscapeAnalysis.EscapeState — Type
estate::EscapeState

Расширенная решетка, которая сопоставляет аргументы и значения SSA с информацией о выходе, представленной как EscapeInfo. Информация о выходе, наложенная на элемент SSA IR x, может быть получена с помощью estate[x].

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

Латтеца для информации об уходе, которая содержит следующие свойства:

  • x.Analyzed::Bool: не является формально частью латтецы, только указывает, была ли проанализирована x

  • x.ReturnEscape::Bool: указывает, что x может уйти к вызывающему через возврат

  • x.ThrownEscape::BitSet: записывает номера операторов SSA, где x может быть выброшен как исключение:

    • isempty(x.ThrownEscape): x никогда не будет выброшен в этом кадре вызова (низ)
    • pc ∈ x.ThrownEscape: x может быть выброшен на операторе SSA в pc
    • -1 ∈ x.ThrownEscape: x может быть выброшен в произвольных точках этого кадра вызова (верх)

    Эта информация будет использоваться escape_exception! для распространения потенциальных уходов через исключение.

  • x.AliasInfo::Union{Bool,IndexableFields,IndexableElements,Unindexable}: поддерживает все возможные значения, которые могут быть алиасированы к полям или элементам массива x:

    • x.AliasInfo === false указывает, что поля/элементы x еще не были проанализированы
    • x.AliasInfo === true указывает, что поля/элементы x не могут быть проанализированы, например, тип x не известен или не является конкретным, и, следовательно, его поля/элементы не могут быть точно известны
    • x.AliasInfo::IndexableFields записывает все возможные значения, которые могут быть алиасированы к полям объекта x с точной информацией об индексах
    • x.AliasInfo::IndexableElements записывает все возможные значения, которые могут быть алиасированы к элементам массива x с точной информацией об индексах
    • x.AliasInfo::Unindexable записывает все возможные значения, которые могут быть алиасированы к полям/элементам x без точной информации об индексах

  • x.Liveness::BitSet: записывает номера операторов SSA, где x должен быть жив, например, чтобы быть использованным как аргумент вызова, чтобы быть возвращенным вызывающему или сохраненным для :foreigncall:

    • isempty(x.Liveness): x никогда не будет использован в этом кадре вызова (низ)
    • 0 ∈ x.Liveness также имеет специальное значение, что это аргумент вызова текущего анализируемого кадра вызова (и, следовательно, он виден из вызывающего немедленно).
    • pc ∈ x.Liveness: x может быть использован на операторе SSA в pc
    • -1 ∈ x.Liveness: x может быть использован в произвольных точках этого кадра вызова (верх)

Существуют утилитарные конструкторы для создания общих EscapeInfo, например,

  • NoEscape(): нижний (подобный) элемент этой латтецы, означающий, что он не уйдет никуда
  • AllEscape(): самый верхний элемент этой латтецы, означающий, что он уйдет повсюду

analyze_escapes будет переводить эти элементы снизу вверх, в том же направлении, что и родная процедура вывода типов Julia. Абстрактное состояние будет инициализировано нижними (подобными) элементами:

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