Escape-анализ

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

Эти атрибуты могут быть объединены для создания частичной решетки с конечной высотой, учитывая тот инвариант, что входная программа имеет конечное число операторов благодаря семантике 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).

Важное замечание касается того, что этот обратный анализ позволяет информации о выходе естественным образом идти по цепочке «использование — определение», а не по порядку выполнения^[3]. В результате эта схема обеспечивает простую реализацию escape-анализа. Например, PhiNode может быть обработан путем простого распространения информации о выходе в отношении PhiNode на значения его предшественника.

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

В приведенном выше примере 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. Рассмотрим следующий пример.

ϕ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 и не выходил из выделенных массивов слишком консервативно.

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

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

Обратите внимание, что 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.

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

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

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

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

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

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