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

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

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

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

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

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

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

Однако в таких языках, как 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), а не количеству операторов в критическом участке кода.

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

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

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