Статическая форма единовременного назначения - Static single assignment form

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

SSA был предложен Барри К. Розеном , Марком Н. Вегманом и Ф. Кеннетом Задеком в 1988 году. Рон Цитрон , Жанна Ферранте и три предыдущих исследователя из IBM разработали алгоритм, который может эффективно вычислять форму SSA.

Можно ожидать найти SSA в компиляторе для Fortran , C или C ++ , тогда как в компиляторах функциональных языков , таких как для Scheme и ML , обычно используется стиль передачи с продолжением (CPS). SSA формально эквивалентен подмножеству CPS с хорошим поведением, за исключением нелокального потока управления, чего не происходит, когда CPS используется в качестве промежуточного представления. Таким образом, оптимизации и преобразования, сформулированные в терминах одного, немедленно применяются к другому.

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

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

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

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

y₁ := 1
y₂ := 2
x₁ := y₂

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

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

Переход на SSA

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

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

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

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

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

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

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

По словам Кенни Задека, Φ-функции изначально назывались фальшивыми функциями, в то время как SSA разрабатывалась в IBM Research в 1980-х годах. Формальное название функции Φ было принято только тогда, когда работа была впервые опубликована в академической статье.

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

Во-первых, нам нужна концепция доминатора : мы говорим, что узел A строго доминирует над другим узлом B в графе потока управления, если невозможно достичь B, не пройдя сначала через A. Это полезно, потому что, если мы когда-нибудь дойдем до B, мы узнаем, что любой код в A запущен. Мы говорим, что A доминирует над B (B доминирует над A), если либо A строго доминирует над B, либо A = B.

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

Границы доминирования фиксируют точные места, в которых нам нужны функции Φ: если узел A определяет определенную переменную, тогда это определение и это определение в одиночку (или переопределения) достигнут каждого узла A доминирует. Только когда мы покидаем эти узлы и выходим на границу доминирования, мы должны учитывать другие потоки, вводя другие определения той же переменной. Более того, никакие другие функции Φ не требуются в графе потока управления, чтобы иметь дело с определениями A, и мы можем обойтись не меньшим.

Существует эффективный алгоритм определения границ доминирования каждого узла. Этот алгоритм был первоначально описан в Cytron et al. 1991. Также полезна глава 19 книги Эндрю Аппеля "Современная реализация компилятора на Java" (Cambridge University Press, 2002). См. Статью для более подробной информации.

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

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)

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

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

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

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

Обрезанный SSA

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

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

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

Полуфабрикат SSA

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

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

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

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

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

Расширения

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

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

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

Компиляторы, использующие форму SSA

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

Компилятор ETH Oberon-2 был одним из первых общедоступных проектов, включающих GSA, вариант SSA.
LLVM Инфраструктура Компилятор использует SSA форму для всех скалярных значений регистров (все , кроме памяти) в своем первичном представлении кода. Форма SSA удаляется только после того, как происходит выделение регистров, в конце процесса компиляции (часто во время компоновки).
Open64 компилятор использует SSA форму в глобальном скалярном оптимизаторе, хотя код вводятся в SSA формы до и вынимает из SSA формы впоследствии. Open64 использует расширения формы SSA для представления памяти в форме SSA, а также скалярных значений.
Начиная с версии 4 (выпущенной в апреле 2005 г.) GCC, коллекция компиляторов GNU , широко использует SSA. В фронтэнды генерируют « GENERIC » код , который затем преобразуется в « GIMPLE » кода по «gimplifier». Затем к форме SSA "GIMPLE" применяются высокоуровневые оптимизации. Полученный в результате оптимизированный промежуточный код затем транслируется в RTL , к которому применяются низкоуровневые оптимизации. Архитектурно- зависимые механизмы наконец превращают RTL в язык ассемблера .
IBM с открытым исходным кодом адаптивная «s виртуальная машина Java , Jikes РВМ , использует расширенный Array , SSA, расширение SSA , что позволяет анализ скаляров, массивов и полей объекта в единой среде. Анализ SSA с расширенным массивом доступен только на максимальном уровне оптимизации, который применяется к наиболее часто выполняемым частям кода.
В 2002 году исследователи модифицировали IBM JikesRVM (в то время называвшееся Jalapeño) для запуска как стандартного байт-кода Java, так и файлов классов байт- кода безопасного типа SSA ( SafeTSA ), и продемонстрировали значительные преимущества в производительности при использовании байт-кода SSA.
Oracle «s HotSpot Java Virtual Machine использует SSA на основе промежуточного языка в его JIT компилятором.
Серверная часть компилятора Microsoft Visual C ++, доступная в Microsoft Visual Studio 2015 с обновлением 3, использует SSA
Mono использует SSA в своем JIT-компиляторе Mini.
jackcc - компилятор с открытым исходным кодом для академического набора инструкций Jackal 3.0. Он использует простой трехоперандный код с SSA для его промежуточного представления. В качестве интересного варианта он заменяет функции Φ так называемой инструкцией SAME, которая инструктирует распределителю регистров поместить два активных диапазона в один и тот же физический регистр.
Декомпилятор Boomerang, хотя и не является компилятором, использует форму SSA во внутреннем представлении. SSA используется для упрощения распространения выражений, определения параметров и возвратов, анализа сохранения и многого другого.
Portable.NET использует SSA в своем JIT-компиляторе.
libFirm полностью основанное на графах промежуточное представление SSA для компиляторов. libFirm использует форму SSA для всех значений скалярных регистров до генерации кода с помощью распределителя регистров с поддержкой SSA.
Компилятор Illinois Concert около 1994 года использовал вариант SSA под названием SSU (Static Single Use), который переименовывает каждую переменную, когда ей присваивается значение, и в каждом условном контексте, в котором эта переменная используется; по сути, статическая единая информационная форма, упомянутая выше. Форма SSU задокументирована в докторской диссертации Джона Плевяка .
Компилятор COINS использует оптимизацию формы SSA, как описано здесь: http://www.is.titech.ac.jp/~sassa/coins-www-ssa/english/
Mozilla Firefox SpiderMonkey движок JavaScript использует SSA на основе ИК.
Механизм JavaScript Chromium V8 реализует SSA в своей инфраструктуре компилятора Crankshaft, как было объявлено в декабре 2010 года.
PyPy использует линейное представление SSA для трассировок в своем JIT-компиляторе.
Android «s Dalvik виртуальная машина использует SSA в JIT компилятором.
Android новый оптимизирующий компилятор «s для Android Время воспроизведения использует SSA для его ИК.
Компилятор MLton Standard MLton использует SSA на одном из промежуточных языков.
LuaJIT активно использует оптимизацию на основе SSA.
PHP и Hack компилятор HHVM использует SSA в ИК.
Компилятор R-Stream от Reservoir Labs поддерживает формы, отличные от SSA (quad list), SSA и SSI (Static Single Information).
Go (1.7: только для архитектуры x86-64; 1.8: для всех поддерживаемых архитектур).
SPIR-V , стандарт языка затенения для графического API Vulkan и язык ядра для API вычислений OpenCL , является представлением SSA.
Различные драйверы Mesa через NIR, представление SSA для языков затенения.
WebKit использует SSA в своих JIT-компиляторах.
Swift определяет свою собственную форму SSA над LLVM IR, которая называется SIL (Swift Intermediate Language).
Erlang переписал свой компилятор в OTP 22.0, чтобы «внутренне использовать промежуточное представление, основанное на статическом одиночном назначении (SSA)». С планами по дальнейшим оптимизациям, основанным на SSA в будущих выпусках.

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

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

Languages

In other projects