Документация Engee

Escape-анализ

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

Цель этого escape-анализа заключается в следующем:

  • использование высокоуровневой семантики Julia, понимание действий выходов и назначения псевдонимов с помощью межпроцедурных вызовов;

  • быть достаточно универсальным, чтобы использоваться для различных оптимизаций, включая SROA с поддержкой псевдонимов, заблаговременную вставку finalize, построение ImmutableArray без копирования, выделение стека изменяемых объектов и т. д.;

  • выполнение простой реализации на основе реализации полностью обратного анализа потока данных, а также новой конструкции решетки, сочетающей свойства ортогональной решетки.

Попробуйте!

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

julia> include(normpath(Sys.BINDIR, "..", "share", "julia", "test", "compiler", "EscapeAnalysis", "EAUtils.jl")); using .EAUtils


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 # обязательно выйдет из `r1`
           end
           s2 = get′(r2)       # все еще не полностью выходит из `r2`
           s3 = get′(r3)       # все еще не полностью выходит из `r3`
           s4 = sizeof(s4)     # Аргумент `s4` здесь не выходит
           return s2, s3, s4
       end
#1(X _2::String, ↑ _3::String, ↑ _4::String, ✓ _5::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  = $(Expr(: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, 1))
◌  7 ──       goto #10
✓′ 8 ┄─ %16 = φᶜ (%4)::Main.SafeRef{String}
*′ │    %17 = φᶜ (%5)::Base.RefValue{String}
✓  │    %18 = φᶜ (%6)::String
◌  └───       $(Expr(:leave, 1))
X  9 ── %20 = $(Expr(:the_exception))::Any
◌  │          (Main.GV = %20)::Any
◌  └───       $(Expr(:pop_exception, :(%7)))::Any
✓′ 10 ┄ %23 = φ (#7 => %3, #9 => %16)::Main.SafeRef{String}
*′ │    %24 = φ (#7 => %2, #9 => %17)::Base.RefValue{String}
✓  │    %25 = φ (#7 => _5, #9 => %18)::String
◌  │    %26 = Base.isdefined(%24, :x)::Bool
◌  └───       goto #12 if not %26
↑  11 ─ %28 = Base.getfield(%24, :x)::String
◌  └───       goto #13
◌  12 ─       Main.throw(%24)::Union{}
◌  └───       unreachable
↑  13 ─ %32 = Base.getfield(%23, :x)::String
◌  │    %33 = Core.sizeof(%25)::Int64
↑′ │    %34 = Core.tuple(%28, %32, %33)::Tuple{String, String, Int64}
◌  └───       return %34

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

  • ◌ (одноцветный): это значение не анализируется, поскольку его информация о выходе не будет использоваться (например, когда объект имеет тип isbitstype).

  • ✓ (зеленого или голубого цвета): это значение никогда не выходит (содержит has_no_escape(result.state[x])), окрашивается в голубой цвет, если оно также имеет выход аргумента (has_arg_escape(result.state[x]) сохраняется).

  • ↑ (синий или желтый): это значение может выйти к вызывающей стороне через возврат (содержит has_return_escape(result.state[x])), окрашивается в желтый цвет, если оно также имеет необработанный сгенерированный выход (содержит has_thrown_escape(result.state[x])).

  • X (красный): это значение может выйти в любое место, о котором escape-анализ не может судить, например выйти в глобальную память (содержит has_all_escape(result.state[x])).

  • * (жирный шрифт): состояние выхода этого значения находится между ReturnEscape и AllEscape в частичном порядке EscapeInfo, окрашивается в желтый цвет, если оно также имеет необработанный сгенерированный выход (содержит has_thrown_escape(result.state[x])).

  • ′: это значение имеет дополнительную информацию о поле объекта или элементе массива в своем свойстве AliasInfo.

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

julia> result.state[Core.Argument(3)] # Получить EscapeInfo для `s2`
ReturnEscape

julia> result.state[Core.SSAValue(3)] # Получить EscapeInfo для `r3`
NoEscape′

Структура анализа

Конструкция решетки

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

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

  • x.ReturnEscape::BitSet: записывает операторы SSA, где x может перейти к вызывающей стороне через возврат.

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

  • x.AliasInfo: хранит все возможные значения, которые могут быть псевдонимами полей или элементов x (используется для анализа псевдонимов, описанного ниже).

  • x.ArgEscape::Int (пока не реализовано): указывает, что выйдет к вызывающей стороне через setfield! в аргументах.

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

Распространение обратного выхода

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

Отличительной особенностью этого escape-анализа является то, что он является полностью обратным, то есть информация о выходе идет от использования к определениям. Например, в приведенном ниже фрагменте кода 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(↑ _2::String) in Main at REPL[1]:2
↑′ 1 ─ %1 = %new(Base.RefValue{String}, _2)::Base.RefValue{String}
◌  └──      return %1

Важное замечание касается того, что этот обратный анализ позволяет информации о выходе естественным образом идти по цепочке «использование — определение», а не по порядку выполнения[3]. В результате эта схема обеспечивает простую реализацию escape-анализа. Например, 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(✓ _2::Bool, ↑ _3::String, ↑ _4::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

Анализ псевдонимов

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

julia> code_escapes((String,)) do s
           obj = SafeRef("init")
           obj[] = s
           v = obj[]
           return v
       end
#7(↑ _2::String) in Main at REPL[1]:2
✓′ 1 ─ %1 = %new(Main.SafeRef{String}, "init")::Main.SafeRef{String}
◌  │        Base.setfield!(%1, :x, _2)::String
↑  │   %3 = Base.getfield(%1, :x)::String
◌  └──      return %3

В приведенном выше примере 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(✓ _2::Bool, ↑ _3::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 использует подход, основанный на алгоритме escape-анализа, описанном в старой работе о JVM[5]. То есть в дополнение к управлению элементами решетки выхода анализ также поддерживает набор эквивалентных псевдонимов — несвязанное множество аргументов и операторов SSA с назначенными псевдонимами. Набор псевдонимов управляет значениями, которые могут быть назначены как псевдонимы друг другу, и позволяет выравнивать между ними информацию о выходе, наложенную на любое такое значение с псевдонимом.

Анализ массивов

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

julia> code_escapes((String,)) do s
           ary = Any[]
           push!(ary, SafeRef(s))
           return ary[1], length(ary)
       end
#11(↑ _2::String) in Main at REPL[1]:2
*′ 1 ─ %1 = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Vector{Any}, svec(Any, Int64), 0, :(:ccall), Vector{Any}, 0, 0))::Vector{Any}
↑′ │   %2 = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
◌  │        $(Expr(:foreigncall, :(:jl_array_grow_end), Nothing, svec(Any, UInt64), 0, :(:ccall), :(%1), 0x0000000000000001, 0x0000000000000001))::Nothing
◌  │   %4 = Base.arraylen(%1)::Int64
◌  │        Base.arrayset(true, %1, %2, %4)::Vector{Any}
↑′ │   %6 = Base.arrayref(true, %1, 1)::Any
◌  │   %7 = Base.arraylen(%1)::Int64
↑′ │   %8 = Core.tuple(%6, %7)::Tuple{Any, Int64}
◌  └──      return %8

В приведенном выше примере 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(↑ _2::String, * _3::String) in Main at REPL[1]:2
*′ 1 ─ %1 = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Vector{Any}, svec(Any, Int64), 0, :(:ccall), Vector{Any}, 2, 2))::Vector{Any}
↑′ │   %2 = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
◌  │        Base.arrayset(true, %1, %2, 1)::Vector{Any}
*′ │   %4 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
◌  │        Base.arrayset(true, %1, %4, 2)::Vector{Any}
↑′ │   %6 = Base.arrayref(true, %1, 1)::Any
◌  │   %7 = Base.arraylen(%1)::Int64
↑′ │   %8 = Core.tuple(%6, %7)::Tuple{Any, Int64}
◌  └──      return %8

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

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

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

  • Цикл часто производит изменяемые в цикле непостоянные индексы массивов.

  • Характерно для векторов: изменение размера массива изменяет измерение массива и нарушает его постоянство.

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

В следующем примере 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(↑ _2::String, ↑ _3::String) in Main at REPL[1]:2
◌  1 ─ %1  = Main.nothing::Core.Const(nothing)
◌  │   %2  = Main.nothing::Core.Const(nothing)
◌  │   %3  = Core.tuple(%1, %2)::Core.Const((nothing, nothing))
*′ │   %4  = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Vector{Any}, svec(Any, Int64), 0, :(:ccall), Vector{Any}, 2, 2))::Vector{Any}
◌  └──       goto #7 if not true
◌  2 ┄ %6  = φ (#1 => 1, #6 => %15)::Int64
◌  │   %7  = φ (#1 => 1, #6 => %16)::Int64
↑′ │   %8  = Base.getfield(%3, %6, false)::Nothing
◌  │         Base.arrayset(false, %4, %8, %6)::Vector{Any}
◌  │   %10 = (%7 === 2)::Bool
◌  └──       goto #4 if not %10
◌  3 ─       goto #5
◌  4 ─ %13 = Base.add_int(%7, 1)::Int64
◌  └──       goto #5
◌  5 ┄ %15 = φ (#4 => %13)::Int64
◌  │   %16 = φ (#4 => %13)::Int64
◌  │   %17 = φ (#3 => true, #4 => false)::Bool
◌  │   %18 = Base.not_int(%17)::Bool
◌  └──       goto #7 if not %18
◌  6 ─       goto #2
◌  7 ┄       goto #8
↑′ 8 ─ %22 = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
◌  │         Base.arrayset(true, %4, %22, 1)::Vector{Any}
↑′ │   %24 = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
◌  │         Base.arrayset(true, %4, %24, 2)::Vector{Any}
↑′ │   %26 = Base.arrayref(true, %4, 1)::Any
◌  │   %27 = Base.arraylen(%4)::Int64
↑′ │   %28 = Core.tuple(%26, %27)::Tuple{Any, Int64}
◌  └──       return %28

В следующем примере показано, как изменение размера вектора затрудняет точный анализ псевдонимов. Существенная трудность заключается в том, что измерение выделенного массива %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(↑ _2::String, ↑ _3::String) in Main at REPL[1]:2
*′ 1 ─ %1  = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Vector{Any}, svec(Any, Int64), 0, :(:ccall), Vector{Any}, 0, 0))::Vector{Any}
↑′ │   %2  = %new(Main.SafeRef{String}, _2)::Main.SafeRef{String}
◌  │         $(Expr(:foreigncall, :(:jl_array_grow_end), Nothing, svec(Any, UInt64), 0, :(:ccall), :(%1), 0x0000000000000001, 0x0000000000000001))::Nothing
◌  │   %4  = Base.arraylen(%1)::Int64
◌  │         Base.arrayset(true, %1, %2, %4)::Vector{Any}
↑′ │   %6  = %new(Main.SafeRef{String}, _3)::Main.SafeRef{String}
◌  │         $(Expr(:foreigncall, :(:jl_array_grow_end), Nothing, svec(Any, UInt64), 0, :(:ccall), :(%1), 0x0000000000000001, 0x0000000000000001))::Nothing
◌  │   %8  = Base.arraylen(%1)::Int64
◌  │         Base.arrayset(true, %1, %6, %8)::Vector{Any}
↑′ │   %10 = Base.arrayref(true, %1, 1)::Any
◌  │   %11 = Base.arraylen(%1)::Int64
↑′ │   %12 = Core.tuple(%10, %11)::Tuple{Any, Int64}
◌  └──       return %12

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

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

Обработка исключений

Также стоит обратить внимание на то, как EscapeAnalysis обрабатывает возможные выходы через исключения. Наивно полагать, что достаточно распространить информацию о выходе, наложенную на объект :the_exception, на все значения, которые могут появляться в соответствующем блоке try. На самом же деле в Julia существует несколько других способов доступа к объекту исключения, например Base.current_exceptions и rethrow. Например, escape-анализ должен учитывать потенциальный выход 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` (псевдонимом которого является `r`) здесь не выходит
               rethrow_escape!() # Но здесь выходит `r`
           end
           return t
       end
#19() in Main at REPL[4]:2
X  1 ── %1  = %new(Base.RefValue{String})::Base.RefValue{String}
◌  2 ── %2  = $(Expr(: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, 1))
◌  7 ──       goto #10
◌  8 ┄─       $(Expr(:leave, 1))
✓  9 ── %12 = $(Expr(:the_exception))::Any
X  │    %13 = Main.typeof(%12)::DataType
X  │          invoke Main.rethrow_escape!()::Any
◌  └───       $(Expr(:pop_exception, :(%2)))::Any
X  10 ┄ %16 = φ (#7 => %5, #9 => %13)::Union{DataType, String}
◌  └───       return %16

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

Свойство 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 # обязательно выйдет из `r1`
           end
           s2 = get′(r2)       # все еще не полностью выходит из `r2`
           return s2
       end
#21(X _2::String, ↑ _3::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  = $(Expr(: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, 1))
◌  7 ──       goto #10
*′ 8 ┄─ %13 = φᶜ (%3)::Base.RefValue{String}
◌  └───       $(Expr(:leave, 1))
X  9 ── %15 = $(Expr(:the_exception))::Any
◌  │          (Main.GV = %15)::Any
◌  └───       $(Expr(:pop_exception, :(%4)))::Any
*′ 10 ┄ %18 = φ (#7 => %2, #9 => %13)::Base.RefValue{String}
◌  │    %19 = Base.isdefined(%18, :x)::Bool
◌  └───       goto #12 if not %19
↑  11 ─ %21 = Base.getfield(%18, :x)::String
◌  └───       goto #13
◌  12 ─       Main.throw(%18)::Union{}
◌  └───       unreachable
◌  13 ─       return %21

Использование анализа

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

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

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

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

  • IPO EA: анализ предварительного встраивания IR для создания кеша допустимой межпроцедурной информации о выходе

  • Local EA: анализ результатов после встраивания IR для сбора локально допустимой информации о выходе

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

Поскольку вычислительные затраты для функции analyze_escapes не так уж низки, анализ IPO EA и Local EA лучше запускать только тогда, когда можно говорить хоть о какой-то рентабельности. В настоящее время EscapeAnalysis предоставляет эвристику is_ipo_profitable для проверки рентабельности IPO EA.

# Core.Compiler.EscapeAnalysis.analyze_escapes — Function

analyze_escapes(ir::IRCode, nargs::Int, call_resolved::Bool, get_escape_cache::Callable)
    -> estate::EscapeState

Анализирует информацию о выходе в ir:

  • nargs: количество фактических аргументов анализируемого вызова

  • call_resolved: если межпроцедурные вызовы уже разрешены с помощью ssa_inlining_pass!

  • get_escape_cache(::Union{InferenceResult,MethodInstance}) -> Union{Nothing,ArgEscapeCache}: получает кэшированную информацию о выходе аргумента

# Core.Compiler.EscapeAnalysis.EscapeState — Type

estate::EscapeState

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

# 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, но в то же время не представляет никакого значения, кроме того, что он еще не проанализирован (таким образом, формально он не является частью решетки)

# Core.Compiler.EscapeAnalysis.is_ipo_profitable — Function

is_ipo_profitable(ir::IRCode, nargs::Int) -> Bool

Эвристически проверяет, есть ли смысл выполнять escape-анализ для ir и генерировать кэш информации о выходе IPO. В частности, эта функция проверяет, представляет ли какой-либо аргумент вызова интерес с точки зрения возможности выхода.

1. В нашей реализации вывода типов используется альтернативный подход, где каждое свойство решетки представлено специальным объектом типа элемента решетки. Оказалось, что он начал усложнять реализации операций решетки, главным образом потому, что часто требует правил преобразования между всеми объектами типа элемента решетки. И мы работаем над модернизацией реализации решетки вывода типов с EscapeInfo-подобной конструкцией решетки.
2. A Graph-Free approach to Data-Flow Analysis. Markas Mohnen, 2002, April. https://api.semanticscholar.org/CorpusID:28519618.
3. Наш алгоритм вывода типа, напротив, реализован как прямой анализ, поскольку информация о типе обычно идет от определения к использованию, поэтому более естественно и эффективно распространять такую информацию прямым путем.
4. Однако в некоторых случаях поля объектов не поддаются точному анализу. Например, объект может выйти в такое место, где EscapeAnalysis не сможет учесть возможное влияние памяти на него, или поля объектов просто могут быть неизвестны из-за отсутствия информации о типе. В таких случаях свойство AliasInfo поднимается до самого верхнего элемента в пределах собственного порядка решетки, что приводит к более консервативному последующему анализу полей, а информация о выходе в отношении полей неанализируемого объекта распространяется на сам объект.
5. Escape 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.
6. В противном случае нам понадобится еще один анализ прямого потока данных на основе escape-анализа.