Julia SSA-form IR

Julia использует статическое промежуточное представление единственного присвоения (SSA IR) для выполнения оптимизации. Это IR отличается от LLVM IR и уникально для Julia. Оно позволяет выполнять специфические для Julia оптимизации.

Базовые блоки (регионы без управления потоком) явно аннотированы.
if/else и циклы превращаются в операторы goto.
строки с несколькими операциями разбиваются на несколько строк путем введения переменных.

Например, следующий код на Julia:

function foo(x)
    y = sin(x)
    if x > 5.0
        y = y + cos(x)
    end
    return exp(2) + y
end

когда вызывается с аргументом Float64, переводится в:

using InteractiveUtils
@code_typed foo(1.0)

CodeInfo(
1 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3 if not %2
2 ─ %4 = invoke Main.cos(x::Float64)::Float64
└── %5 = Base.add_float(%1, %4)::Float64
3 ┄ %6 = φ (#2 => %5, #1 => %1)::Float64
│   %7 = Base.add_float(7.38905609893065, %6)::Float64
└──      return %7
) => Float64

В этом примере мы можем увидеть все эти изменения.

Первый базовый блок — это всё в

1 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3 if not %2

Оператор if переводится в goto #3 if not %2, который переходит к третьему базовому блоку, если условие x>5 не выполняется, и в противном случае переходит ко второму базовому блоку.
%2 является значением SSA, введенным для представления x > 5.

Background

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

Categories of IR nodes

Представление SSA IR имеет четыре категории узлов IR: узлы Phi, Pi, PhiC и Upsilon (последние два используются только для обработки исключений).

Phi nodes and Pi nodes

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

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

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

Обратите внимание, что SSA использует семантически происходящее после терминатора соответствующего предшественника ("на границе"). Следовательно, если несколько узлов Phi появляются в начале базового блока, они выполняются одновременно. Это означает, что в следующем фрагменте IR, если мы пришли из блока 23, %46 примет значение, связанное с %45 до того, как мы вошли в этот блок.

%45 = φ (#18 => %23, #23 => %50)
%46 = φ (#18 => 1.0, #23 => %45)

PiNodes кодируют статически доказанную информацию, которую можно неявно предполагать в базовых блоках, доминируемых данным pi-узлом. Они концептуально эквивалентны технике, представленной в статье ABCD: Eliminating Array Bounds Checks on Demand. Чтобы увидеть, как они работают, рассмотрим, например,

%x::Union{Int, Float64} # %x is some Union{Int, Float64} typed ssa value
if isa(x, Int)
    # use x
else
    # use x
end

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

%x::Union{Int, Float64} # %x is some Union{Int, Float64} typed ssa value
if isa(x, Int)
    %x_int = PiNode(x, Int)
    # use %x_int
else
    %x_float = PiNode(x, Float64)
    # use %x_float
end

Узлы Pi обычно игнорируются в интерпретаторе, так как они не влияют на значения, но иногда могут привести к генерации кода в компиляторе (например, для изменения неявного представления объединения на простое представление без упаковки). Основная полезность узлов Pi заключается в том, что условия пути значений могут быть накоплены просто путем обхода цепочки определения-использования, что обычно делается для большинства оптимизаций, которые все равно заботятся об этих условиях.

PhiC nodes and Upsilon nodes

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

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

regular:
# Control flow continues here

catch:
# Exceptions go here

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

Чтобы обойти это, мы используем комбинацию узлов Upsilon и PhiC (C означает catch, записывается как φᶜ в формате IR, потому что символ подстрочного c в юникоде недоступен). Существует несколько способов рассматривать эти узлы, но, возможно, самый простой способ — думать о каждом PhiC как о загрузке из уникального слота store-many, read-once, при этом Upsilon является соответствующей операцией хранения. У PhiC есть список операндов всех узлов upsilon, которые хранят в его неявный слот. Однако узлы Upsilon не фиксируют, в какой узел PhiC они хранят. Это сделано для более естественной интеграции с остальной частью SSA IR. Например, если больше нет использований узла PhiC, его можно безопасно удалить, и то же самое верно для узла Upsilon. В большинстве проходов IR узлы PhiC можно рассматривать как узлы Phi. Можно следовать цепочкам использования-определения через них, и их можно поднимать до новых узлов PhiC и новых узлов Upsilon (в тех же местах, что и оригинальные узлы Upsilon). Результатом этой схемы является то, что количество узлов Upsilon (и аргументов PhiC) пропорционально количеству присвоенных значений конкретной переменной (до преобразования SSA), а не количеству операторов в критической области.

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

@noinline opaque() = invokelatest(identity, nothing) # Something opaque
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, Core.SSAValue(2)))
5 ─       $(Expr(:pop_exception, :(%2)))::Any
│         $(Expr(:throw_undef_if_not, :y, :(%13)))::Any
│   %19 = Core.tuple(%15, %14)
└──       return %19

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

Main SSA data structure

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

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

Мы храним отдельный буфер узлов для вставки (включая позицию для их вставки, тип соответствующего значения и сам узел). Эти узлы нумеруются по их появлению в буфере вставки, что позволяет их значениям немедленно использоваться в других местах IR (т.е. если в исходном списке операторов 12 операторов, первый новый оператор будет доступен как SSAValue(13)).
Операции RAUW выполняются путем установки соответствующего индекса оператора на значение замены.
Утверждения стираются, устанавливая соответствующее утверждение в nothing (это по сути просто специальный случай соглашения выше).
Если есть какие-либо использования удаляемого утверждения, они будут установлены в nothing.

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

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