Представление IR в форме SSA в Julia

История вопроса

Начиная с версии Julia 0.7 некоторые компоненты компилятора используют новое промежуточное представление (IR) в форме SSA. Ранее компилятор напрямую генерировал представление IR LLVM из пониженной формы представления AST Julia. В такой форме синтаксические абстракции по большей части устранялись, но все же она была очень похожа на абстрактное синтаксическое дерево. Чтобы упростить оптимизации, со временем в это представление IR были введены значения SSA и представление IR было приведено к линейному виду (то есть к такому, где аргументы функций могли быть только значениями SSA или константами). Однако в IR оставались и значения, отличные от SSA (слоты), из-за отсутствия в IR фи-узлов (которые необходимы для обратных ребер и повторного слияния условного порядка выполнения). Это перечеркивало многие плюсы представления в форме SSA при выполнении промежуточных оптимизаций. Были приложены героические усилия к тому, чтобы оптимизации работали без полного представления в форме SSA, однако отсутствие такого представления в конечном итоге оказалось непреодолимым препятствием.

Новые узлы IR

С введением нового представления IR компилятор научился работать с четырьмя новыми узлами IR: фи-узлами, пи-узлами, фиC-узлами и ипсилон-узлами (последние два применяются только для обработки исключений).

Фи- и пи-узлы

Фи-узлы являются частью универсальной абстракции SSA (если это новое для вас понятие, см. информацию по ссылке выше). В IR Julia эти узлы представлены следующим образом:

struct PhiNode
    edges::Vector{Int32}
    values::Vector{Any}
end

где гарантируется, что оба вектора всегда имеют одинаковую длину. В каноническом представлении (обрабатываемом генератором кода и интерпретатором) значения ребер указывают на номера операторов-источников (то есть если у ребра значение 15, должен быть переход goto, gotoifnot или неявная передача управления из оператора 15, целью которого является данный фи-узел). Значения могут представлять собой либо значения SSA, либо константы. Значение может быть не присвоено, если переменная по этому пути не определена. Однако проверки неопределенности добавляются явным образом и представлены логическими значениями после промежуточных оптимизаций, поэтому генераторы кода могут предполагать, что при любом использовании фи-узла в соответствующем слоте будет присвоенное значение. Кроме того, допускается неполное представление, то есть у фи-узла могут отсутствовать входящие ребра. В этом случае требуется динамически гарантировать, что соответствующе значение не будет использоваться.

Пи-узлы кодируют статически подтвержденную информацию, которая может неявно предполагаться в базовых блоках, контролируемых данным пи-узлом. По принципу действия они эквивалентны приему, представленному в документе ABCD:https://dl.acm.org/citation.cfm?id=358438.349342[]Eliminating Array Bounds Checks on Demand (ABCD: устранение проверок границ массивов по запросу), или узлам информации о предикатах в LLVM. Рассмотрим их работу на примере.

%x::Union{Int, Float64} # %x — это некоторое значение ssa типа Union{Int, Float64}
if isa(x, Int)
    # используем x
else
    # используем x
end

Мы можем выполнить вставку предиката и преобразовать этот код в следующий:

%x::Union{Int, Float64} # %x — это некоторое значение ssa типа Union{Int, Float64}
if isa(x, Int)
    %x_int = PiNode(x, Int)
    # используем %x_int
else
    %x_float = PiNode(x, Float64)
    # используем %x_float
end

Пи-узлы обычно игнорируются интерпретатором, так как они не оказывают никакого влияния на значения, однако иногда они могут приводить к формированию кода компилятором (например, для преобразования представления с неявным разделением объединения в простое неупакованное представление). Главная польза пи-узлов объясняется тем, что условия путей для значений могут накапливаться в результате простого прохода по цепочке «определение — использование», который так или иначе осуществляется при большинстве оптимизаций, учитывающих эти условия.

ФиC- и ипсилон-узлы

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

invoke @function_that_may_throw() to label %regular unwind to %catch

regular:
# Порядок выполнения продолжается здесь

catch:
# Исключения поступают сюда

Однако в таких языках, как Julia, в которых в начале конвейера оптимизации неизвестно, какие вызовы создают исключения, это может быть проблематично. Нам пришлось бы на всякий случай предположить, что исключение выдает каждый вызов (то есть каждый оператор в Julia). Такой подход имел бы ряд негативных последствий. Во-первых, область каждого базового блока фактически сократилась бы до одного вызова, что сделало бы бессмысленным выполнение операций на уровне базового блока. Во-вторых, каждый базовый блок catch имел бы n*m аргументов фи-узла (где n — это количество операторов в критическом участке кода, а m — количество активных значений в блоке catch).

Чтобы обойти эту проблему, мы используем сочетание узлов Upsilon и PhiC (где C означает catch; в программе структурной распечатки IR это записывается как φᶜ, так как нижний индекс для символа «c» в Юникоде недоступен). Назначение этих узлов можно объяснить по-разному, но, вероятно, проще всего будет представить каждый узел PhiC как загрузку из уникального слота для многократного сохранения и однократного считывания, а Upsilon — как соответствующую операцию сохранения. Узел PhiC содержит список операндов всех ипсилон-узлов, которые выполняют сохранение в его неявный слот. Узлы Upsilon, однако, не регистрируют информацию об узле PhiC, в который они выполняют сохранение. Таким образом обеспечивается более естественная интеграция с остальным представлением IR SSA. Например, если узел PhiC больше не используется, его можно спокойно удалить. То же самое верно и в отношении узла Upsilon. При большинстве проходов IR узлы PhiC можно обрабатывать как узлы Phi. Они позволяют следовать по цепочкам «использование — определение», и их можно повышать до новых узлов PhiC и Upsilon (в тех же местах, что и исходные узлы Upsilon). Результатом такой схемы является то, что количество узлов Upsilon (и аргументов PhiC) пропорционально количеству значений, присваиваемых определенной переменной (до преобразования SSA), а не количеству операторов в критическом участке кода.

Чтобы увидеть эту схему в действии, рассмотрим следующую функцию.

@noinline opaque() = invokelatest(identity, nothing) # Что-то непрозрачное
function foo()
    local y
    x = 1
    try
        y = 2
        opaque()
        y = 3
        error()
    catch
    end
    (x, y)
end

Соответствующее представление IR (с удалением не имеющих значения типов) выглядит так:

1 ─       nothing::Nothing
2 ─ %2  = $(Expr(:enter, #4))
3 ─ %3  = ϒ (false)
│   %4  = ϒ (#undef)
│   %5  = ϒ (1)
│   %6  = ϒ (true)
│   %7  = ϒ (2)
│         invoke Main.opaque()::Any
│   %9  = ϒ (true)
│   %10 = ϒ (3)
│         invoke Main.error()::Union{}
└──       $(Expr(:unreachable))::Union{}
4 ┄ %13 = φᶜ (%3, %6, %9)::Bool
│   %14 = φᶜ (%4, %7, %10)::Core.Compiler.MaybeUndef(Int64)
│   %15 = φᶜ (%5)::Core.Const(1)
└──       $(Expr(:leave, 1))
5 ─       $(Expr(:pop_exception, :(%2)))::Any
│         $(Expr(:throw_undef_if_not, :y, :(%13)))::Any
│   %19 = Core.tuple(%15, %14)
└──       return %19

В особенности обратите внимание, что каждое активное значение в критическом участке кода получает ипсилон-узел вверху этого критического участка. Причина в том, что блоки catch считаются имеющими невидимое ребро порядка выполнения извне функции. Поэтому блоки catch не контролируются никаким значением SSA и все входящие значения должны проходить через узел φᶜ.

Основная структура данных SSA

Основная структура данных SSAIR заслуживает внимания. Она была вдохновлена LLVM и Webkit B3 IR. В основе структуры данных лежит плоский вектор операторов. Каждому оператору неявно присваивается значение SSA в соответствии с его позицией в векторе (то есть доступ к результату оператора в позиции idx 1 можно получить с помощью SSAValue(1) и т. д.). Для каждого значения SSA дополнительно определяется его тип. Так как по определению значения SSA присваиваются только один раз, тип также является результирующим типом выражения по соответствующему индексу. Однако, хотя такое представление достаточно эффективно (поскольку присваивания не нужно кодировать явным образом), оно обладает тем очевидным недостатком, что порядок имеет смысловую значимость, из-за чего при переупорядочении и вставке номера операторов меняются. Кроме того, не ведутся списки использования (то есть от определения невозможно перейти ко всем случаям его использования, не вычисляя сопоставления явным образом; однако списки определений не представляют особой проблемы, так как найти соответствующий оператор можно по индексу), поэтому операция RAUW («заменить все случаи использования на») в стиле LLVM недоступна.

Вместо этого мы делаем следующее.

  • Мы ведем отдельный буфер узлов для вставки (включая позицию вставки, тип соответствующего значения и сам узел). Узлы нумеруются согласно порядку следования в буфере вставки, что позволяет использовать их значения напрямую в других местах IR (то есть, если в исходном списке операторов имеется 12 операторов, первый новый оператор будет доступен как SSAValue(13)).

  • Операции в стиле RAUW выполняются путем присваивания соответствующему индексу оператора нового значения.

  • Для удаления оператора ему присваивается значение nothing (это по сути просто особый случай в рамках описанного выше соглашения).

  • Если имеются случаи использования удаляемого оператора, им присваивается nothing.

Существует функция compact!, которая сжимает описанную выше структуру данных путем вставки узлов в соответствующих местах, обычного распространения копий и переименования случаев использования согласно новым значениям SSA. Однако примечательной особенностью этой схемы является то, что сжатие может выполняться «лениво» в рамках последующего прохода. Большинство проходов оптимизации должны проходить по всему списку операторов, в процессе выполняя анализ или изменения. Для перебора списка операторов мы предоставляем итератор IncrementalCompact. Он производит необходимое сжатие и возвращает новый индекс узла, а также сам узел. На этом этапе разрешено производить обход цепочек «определение — использование», а также вносить изменения и удалять элементы в IR (вставки, однако, запрещены).

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