Статическая форма с одним заданием

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

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

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

В компиляторах функциональных языков , таких как Scheme и ML , стиль передачи продолжения обычно используется (CPS). SSA формально эквивалентен подмножеству CPS с хорошим поведением, исключая нелокальный поток управления, поэтому оптимизации и преобразования, сформулированные в терминах одного, обычно применимы и к другому. Использование CPS в качестве промежуточного представления более естественно для функций высшего порядка и межпроцедурного анализа. CPS также легко кодирует call/cc , тогда как SSA этого не делает.

История

SSA был разработан в 1980-х годах несколькими исследователями из IBM . Кеннет Задек, ключевой член команды, перешел в Университет Брауна, поскольку разработка продолжалась. В статье 1986 года были представлены точки рождения, присвоение идентификаторов и переименование переменных, так что переменные имели одно статическое назначение. Последующая статья 1987 года Жанны Ферранте и Рональда Ситрона. доказал, что переименование, выполненное в предыдущей статье, удаляет все ложные зависимости для скаляров. В 1988 году Барри Розен, Марк Н. Вегман и Кеннет Задек заменили идентификационные присвоения на Φ-функции, ввели название «статическая форма с одним присвоением» и продемонстрировали распространённую ныне оптимизацию SSA. Название Φ-функция было выбрано Розеном как более доступная для публикации версия «фальшивой функции». Альперн, Вегман и Задек представили еще одну оптимизацию, но с названием «одиночное статическое присвоение». Наконец, в 1989 году Розен, Вегман, Задек, Цитрон и Ферранте нашли эффективный способ преобразования программ в форму SSA.

Преимущества

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

y := 1
y := 2
x := y

Люди могут видеть, что первое назначение не является необходимым и что ценность y используемый в третьей строке, происходит из второго назначения y. Чтобы определить это, программе придется выполнить анализ определения . Но если программа находится в форме SSA, оба этих действия выполняются немедленно:

y1 := 1
y2 := 2
x1 := y2

Алгоритмы оптимизации компилятора , которые либо активируются, либо значительно улучшаются за счет использования SSA, включают:

• Постоянное распространение - преобразование вычислений из времени выполнения во время компиляции, например, обработка инструкции. a=3*4+5; как будто это было a=17;
• Распространение диапазона значений – предварительно рассчитать потенциальные диапазоны, в которых может быть рассчитан расчет, что позволяет заранее создавать прогнозы ветвей
• Разреженное распространение условной константы — проверка диапазона некоторых значений, что позволяет тестам предсказать наиболее вероятную ветвь.
• Устранение мертвого кода — удалите код, который не повлияет на результаты.
• Нумерация глобальных значений — замена повторяющихся вычислений, дающих тот же результат.
• Устранение частичной избыточности – удаление повторяющихся вычислений, ранее выполненных в некоторых ветках программы.
• Снижение силы – замена дорогостоящих операций менее дорогостоящими, но эквивалентными, например, замена целочисленного умножения или деления на степени 2 потенциально менее затратным сдвигом влево (для умножения) или сдвигом вправо (для деления).
• Распределение регистров – оптимизируйте использование ограниченного числа машинных регистров для вычислений.

Преобразование в SSA

Преобразование обычного кода в форму SSA — это прежде всего вопрос замены цели каждого присваивания новой переменной и замены каждого использования переменной «версией» переменной, достигающей этой точки. Например, рассмотрим следующий граф потока управления :

An example control-flow graph, before conversion to SSA

Изменение имени слева от «x» $\leftarrow$ x - 3" и изменение следующего использования x на это новое имя оставит программу без изменений. Это можно использовать в SSA, создав две новые переменные: x ₁ и x ₂ , каждая из которых назначается только один раз. Аналогично, давая различение индексов всех остальных переменных дает:

An example control-flow graph, partially converted to SSA

Понятно, к какому определению относится каждое использование, за исключением одного случая: оба использования y в нижнем блоке могут относиться либо к y ₁ , либо к y ₂ , в зависимости от того, по какому пути пошел поток управления.

Чтобы решить эту проблему, в последний блок вставляется специальный оператор, называемый функцией Φ (Phi) . Этот оператор создаст новое определение y, называемое y _3, путем «выбора» либо y ₁ , либо y ₂ , в зависимости от потока управления в прошлом.

An example control-flow graph, fully converted to SSA

Теперь последний блок может просто использовать y ₃ , и правильное значение будет получено в любом случае. Функция Φ для x не нужна: только одна версия x , а именно x _2, достигает этого места, поэтому проблем нет (другими словами, Φ( x ₂ , x ₂ ) = x ₂ ).

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

Функции Φ не реализованы как машинные операции на большинстве машин. Компилятор может реализовать функцию Φ, вставив операции «перемещения» в конец каждого предшествующего блока. В приведенном выше примере компилятор может вставить перемещение от y ₁ до y ₃ в конце среднего левого блока и перемещение от y ₂ до y ₃ в конце среднеправого блока. компилятора Эти операции перемещения могут не попасть в окончательный код в зависимости от процедуры выделения регистров . Однако этот подход может не работать, когда одновременные операции спекулятивно создают входные данные для функции Φ, что может произойти на машинах с широким спектром задач . Обычно машина широкого выпуска имеет инструкцию выбора, используемую в таких ситуациях компилятором для реализации функции Φ.

Вычисление минимального SSA с использованием границ доминирования

В графе потока управления говорят, что узел A строго доминирует над другим узлом B, если невозможно достичь B, не пройдя сначала через A. Другими словами, если достигнут узел B, то можно предположить, что A запустился. Говорят, что A доминирует над B (или B доминирует над A), если либо A строго доминирует над B, либо A = B.

Узел, передающий управление узлу А, называется непосредственным предшественником узла А.

Граница доминирования узла A — это набор узлов B, где A не доминирует строго над B, но доминирует над некоторым непосредственным предшественником B. Это точки, в которых несколько путей управления снова сливаются в один путь.

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

[1] x = random()
if x < 0.5
    [2] result = "heads"
else
    [3] result = "tails"
end
[4] print(result)

узел 1 строго доминирует над узлами 2, 3 и 4, а непосредственными предшественниками узла 4 являются узлы 2 и 3.

Границы доминирования определяют точки, в которых необходимы функции Φ. В приведенном выше примере, когда управление передается узлу 4, определение result Используемое значение зависит от того, было ли управление передано из узла 2 или 3. Функции Φ не нужны для переменных, определенных в доминаторе, поскольку существует только одно возможное определение, которое можно применить.

Существует эффективный алгоритм определения границ доминирования каждого узла. Этот алгоритм был первоначально описан в книге «Эффективное вычисление статической формы одиночного назначения и графа управления» Роном Сайтроном, Жанной Ферранте и др. в 1991 году.

Кейт Д. Купер, Тимоти Дж. Харви и Кен Кеннеди из Университета Райса описывают алгоритм в своей статье под названием «Простой и быстрый алгоритм доминирования» :

for each node b
    dominance_frontier(b) := {}
for each node b
    if the number of immediate predecessors of b ≥ 2
        for each p in immediate predecessors of b
            runner := p
            while runner ≠ idom(b)
                dominance_frontier(runner) := dominance_frontier(runner) ∪ { b }
                runner := idom(runner)

В приведенном выше коде idom(b) является непосредственным доминатором узла b, единственным узлом, который строго доминирует над b, но не доминирует строго над каким-либо другим узлом, строго доминирующим над b.

Вариации, уменьшающие количество Φ-функций

«Минимальный» SSA вставляет минимальное количество функций Φ, необходимое для того, чтобы гарантировать, что каждому имени присвоено значение ровно один раз и что каждая ссылка (использование) имени в исходной программе все еще может ссылаться на уникальное имя. (Последнее требование необходимо для того, чтобы компилятор мог записать имя для каждого операнда в каждой операции.)

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

Обрезанный SSA

Форма сокращенного SSA основана на простом наблюдении: функции Φ необходимы только для переменных, которые «живы» после функции Φ. (Здесь «живой» означает, что значение используется по некоторому пути, который начинается с рассматриваемой функции Φ.) Если переменная не является активной, результат функции Φ не может быть использован, и присвоение функцией Φ недействительно. .

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

Другая возможность — рассматривать обрезку как проблему устранения мертвого кода . Тогда функция Φ активна только в том случае, если какое-либо использование во входной программе будет переписано для нее или если она будет использоваться в качестве аргумента в другой функции Φ. При вводе формы SSA каждое использование переписывается в соответствии с ближайшим доминирующим определением. Тогда функция Φ будет считаться живой, если это ближайшее определение, которое доминирует хотя бы в одном использовании или хотя бы в одном аргументе живой Φ.

Полуобрезанный SSA

Полуобрезанная форма SSA это попытка уменьшить количество функций Φ без относительно высоких затрат на вычисление информации о текущих переменных. Он основан на следующем наблюдении: если переменная никогда не активна при входе в базовый блок, ей никогда не нужна функция Φ. При построении SSA функции Φ для любых «блочно-локальных» переменных опускаются.

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

Блокировать аргументы

Блочные аргументы — это альтернатива функциям Φ, которая визуально идентична, но на практике может быть более удобной во время оптимизации. Блоки именуются и принимают список аргументов блока, обозначенных как параметры функции. При вызове блока аргументы блока привязываются к указанным значениям. Swift SIL и MLIR используют блочные аргументы.

Преобразование из формы SSA

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

Выполнение оптимизации формы SSA обычно приводит к запутанности SSA-Web, то есть существуют инструкции Φ, операнды которых не все имеют одинаковый корневой операнд. В таких случаях раскрашивания для выхода из SSA используются алгоритмы . Наивные алгоритмы вводят копию на каждом пути предшественника, из-за чего в Φ помещался источник корневого символа, отличный от места назначения Φ. Существует несколько алгоритмов выхода из SSA с меньшим количеством копий, большинство из них используют интерференционные графы или некоторые их аппроксимации для объединения копий.

Расширения

Расширения формы SSA можно разделить на две категории.

Расширения схемы переименования изменяют критерий переименования. Напомним, что форма SSA переименовывает каждую переменную, когда ей присваивается значение. Альтернативные схемы включают статическую одноразовую форму (которая переименовывает каждую переменную в каждом операторе, когда она используется) и статическую единую информационную форму (которая переименовывает каждую переменную, когда ей присваивается значение, а также на границе пост-доминирования).

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

Составители, использующие форму SSA

с открытым исходным кодом

• Mono использует SSA в своем JIT-компиляторе Mini.
• WebKit использует SSA в своих JIT-компиляторах.
• Swift определяет собственную форму SSA над LLVM IR, называемую SIL (Swift Intermediate Language).
• Erlang переписал свой компилятор в OTP 22.0, чтобы «внутренне использовать промежуточное представление, основанное на статическом одиночном назначении (SSA)», с планами по дальнейшей оптимизации на основе SSA в будущих выпусках.
• Инфраструктура компилятора LLVM . использует форму SSA для всех значений скалярных регистров (все, кроме памяти) в своем основном представлении кода Форма SSA устраняется только после выделения регистров, на поздней стадии процесса компиляции (часто во время компоновки).
• Коллекция компиляторов GNU (GCC) широко использует SSA, начиная с версии 4 (выпущенной в апреле 2005 г.). Интерфейсы GIMPLE генерируют « ОБЩИЙ » код, который затем преобразуется в код « » с помощью «гимплификатора». Затем к форме SSA «GIMPLE» применяется оптимизация высокого уровня. Полученный оптимизированный промежуточный код затем транслируется в RTL , к которому применяются низкоуровневые оптимизации. Специализированные для архитектуры серверные части наконец превращают RTL в язык ассемблера .
• Go (1.7: только для архитектуры x86-64; 1.8: для всех поддерживаемых архитектур).
• с открытым исходным кодом IBM Адаптивная виртуальная машина Java , Jikes RVM , использует расширенный Array SSA, расширение SSA, которое позволяет анализировать скаляры, массивы и поля объектов в единой среде. Анализ SSA с расширенным массивом включен только на максимальном уровне оптимизации, который применяется к наиболее часто выполняемым частям кода.
• Движок JavaScript Mozilla Firefox SpiderMonkey использует IR на основе SSA.
• Механизм JavaScript Chromium V8 реализует SSA в своей инфраструктуре компилятора Crankshaft, как было объявлено в декабре 2010 г.
• PyPy использует линейное представление SSA для трассировок в своем JIT-компиляторе.
• Виртуальная машина Android Dalvik использует SSA в своем JIT-компиляторе.
• Android Новый оптимизирующий компилятор для Android Runtime использует SSA для своего IR.
• Компилятор Standard ML MLton использует SSA на одном из своих промежуточных языков.
• LuaJIT активно использует оптимизацию на основе SSA.
• Компилятор PHP и Hack . HHVM использует SSA в своем IR
• libFirm, библиотека для использования в качестве промежуточной и внутренней частей компилятора , использует форму SSA для всех значений скалярных регистров до генерации кода с помощью распределителя регистров, поддерживающего SSA.
• Различные драйверы Mesa через NIR, представление SSA для языков шейдеров.

Коммерческий

• своем в Виртуальная машина Oracle HotSpot Java JIT-компиляторе использует промежуточный язык на основе SSA.
• Серверная часть компилятора Microsoft Visual C++ , доступная в Microsoft Visual Studio 2015 с обновлением 3, использует SSA.
• SPIR-V , стандарт языка шейдеров для графического API Vulkan и язык ядра для вычислительного API OpenCL , является представлением SSA.
• Семейство компиляторов IBM XL, в которое входят C, C++ и Fortran.
• NVIDIA CUDA

Исследования и заброшенные

• Компилятор ETH Oberon-2 был одним из первых общедоступных проектов, включивших GSA, вариант SSA.
• Компилятор Open64 использовал форму SSA в своем глобальном скалярном оптимизаторе, хотя код сначала переводится в форму SSA, а потом выводится из формы SSA. Open64 использует расширения формы SSA для представления памяти в форме SSA, а также скалярных значений.
• В 2002 году исследователи модифицировали IBM JikesRVM (в то время называвшуюся Jalapeño) для запуска как стандартного байт-кода Java , так и типобезопасных файлов класса байт-кода SSA ( SafeTSA ), и продемонстрировали значительные преимущества в производительности при использовании байт-кода SSA.
• jackcc — это компилятор с открытым исходным кодом для академического набора инструкций Jackal 3.0. В качестве промежуточного представления он использует простой код с тремя операндами и SSA. В качестве интересного варианта он заменяет функции Φ так называемой инструкцией SAME, которая дает команду распределителю регистров поместить два действующих диапазона в один и тот же физический регистр.
• Сборник концертов Иллинойса, около 1994 г. использовал вариант SSA под названием SSU (Static Single Use), который переименовывает каждую переменную, когда ей присваивается значение, и в каждом условном контексте, в котором эта переменная используется; по сути, это статическая единая информационная форма, упомянутая выше. Форма СГУ описана в докторской диссертации Джона Плевяка .
• Компилятор COINS использует оптимизацию форм SSA, как описано здесь .
• Компилятор R-Stream от Reservoir Labs поддерживает не-SSA (четверенный список), SSA и SSI (статическую единую информацию). ) формы.
• не является компилятором, но Декомпилятор Boomerang в своем внутреннем представлении использует форму SSA. SSA используется для упрощения распространения выражений, определения параметров и результатов, анализа сохранения и многого другого.
• DotGNU Portable.NET использовал SSA в своем JIT-компиляторе.

Ссылки

Общие ссылки

• Растелло, Фабрис; Тишаду, Флоран Буше, ред. (2022). Проект компилятора на основе SSA (PDF) . Чам. дои : 10.1007/978-3-030-80515-9 . ISBN  978-3-030-80515-9 . S2CID   63274602 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
• Аппель, Эндрю В. (1999). Современная реализация компилятора в ML . Издательство Кембриджского университета. ISBN  978-0-521-58274-2 . Также доступно на Java ( ISBN   0-521-82060-X , 2002 г.) и C ( ISBN   0-521-60765-5 , 1998 г.) версии.
• Купер, Кейт Д. и Торчон, Линда (2003). Разработка компилятора . Морган Кауфманн. ISBN  978-1-55860-698-2 .
• Мучник, Стивен С. (1997). Расширенное проектирование и реализация компилятора . Морган Кауфманн. ISBN  978-1-55860-320-2 .
• Келси, Ричард А. (март 1995 г.). «Соответствие между стилем прохождения продолжения и статической формой одиночного задания» . Уведомления ACM SIGPLAN . 30 (3): 13–22. дои : 10.1145/202530.202532 .
• Аппель, Эндрю В. (апрель 1998 г.). «SSA — это функциональное программирование» . Уведомления ACM SIGPLAN . 33 (4): 17–20. дои : 10.1145/278283.278285 . S2CID   207227209 .
• Поп, Себастьян (2006). «Структура представления SSA: семантика, анализ и реализация GCC» (PDF) . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
• Маттиас Браун; Себастьян Бухвальд; Себастьян Хак; Роланд Лейсса; Кристоф Мэллон; Андреас Цвинкау (2013), «Простое и эффективное построение статической формы одиночного задания» , «Построение компилятора» , Конспекты лекций по информатике, том. 7791, Springer Berlin Heidelberg, стр. 102–122, doi : 10.1007/978-3-642-37051-9_6 , ISBN  978-3-642-37050-2 , получено 24 марта 2013 г.

Внешние ссылки

• Босшер, Стивен; и Новилло, Диего. GCC получает новую платформу оптимизатора . Статья об использовании SSA в GCC и о его преимуществах по сравнению со старыми IR.
• Библиография SSA . Обширный каталог исследовательских работ SSA.
• Задек, Ф. Кеннет. «Разработка статической формы единого задания» , декабрь 2007 г., рассказ о происхождении SSA.