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

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

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

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

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

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

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

у := 1у := 2х := у

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

у 1  := 1у 2  := 2х 1  := у 2

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

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

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

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

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

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

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

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

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

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

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

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

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

[1] x = случайный()если х < 0,5 [2] результат = "орел"еще [3] результат = "решка"конец[4] печать(результат)

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

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

Существует эффективный алгоритм для поиска границ доминирования каждого узла. Этот алгоритм был первоначально описан в "Efficiently Computing Static Single Assignment Form and the Control Graph" Рона Ситрона, Жанны Ферранте и др. в 1991 году. ^[10]

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

для каждого узла b граница_доминирования(б) := {}для каждого узла b , если число непосредственных предшественников b ≥ 2 для каждого p в непосредственных предшественниках b бегун := p пока бегун ≠ idom(b) доминирование_граница(бегун) := доминирование_граница(бегун) ∪ { b } бегун := idom(бегун)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этот раздел может содержать избыточные или нерелевантные примеры . Пожалуйста, помогите улучшить статью, добавив описательный текст и удалив менее релевантные примеры . ( Август 2018 )

• Mono использует SSA в своем JIT-компиляторе под названием Mini
• WebKit использует SSA в своих JIT-компиляторах. ^{[16] [17]}
• Swift определяет собственную форму SSA над LLVM IR, называемую SIL (Swift Intermediate Language). ^{[18] [19]}
• Erlang переписал свой компилятор в OTP 22.0, чтобы «внутренне использовать промежуточное представление, основанное на статическом одиночном присваивании (SSA)», с планами дальнейшей оптимизации, построенной поверх SSA в будущих выпусках. ^[20]
• Инфраструктура компилятора LLVM использует форму SSA для всех значений скалярных регистров (все, кроме памяти) в своем первичном представлении кода. Форма SSA устраняется только после выделения регистра, на поздних этапах процесса компиляции (часто во время компоновки) .
• GNU Compiler Collection (GCC) широко использует SSA, начиная с версии 4 (выпущенной в апреле 2005 г.). Фронтенды генерируют код " GENERIC ", который затем преобразуется в код " GIMPLE " с помощью "gimplifier". Затем к форме SSA "GIMPLE" применяются высокоуровневые оптимизации. Полученный оптимизированный промежуточный код затем транслируется в RTL , к которому применяются низкоуровневые оптимизации. Архитектурно-специфические бэкенды в конечном итоге превращают RTL в язык ассемблера .
• Go (1.7: только для архитектуры x86-64; 1.8: для всех поддерживаемых архитектур). ^{[21] [22]}
• Адаптивная виртуальная машина Java с открытым исходным кодом от IBM , Jikes RVM , использует расширенный Array SSA, расширение SSA, которое позволяет анализировать скаляры, массивы и поля объектов в единой среде. Анализ Extended Array SSA доступен только на максимальном уровне оптимизации, который применяется к наиболее часто выполняемым частям кода.
• Движок Mozilla Firefox SpiderMonkey JavaScript использует IR на основе SSA. ^[23]
• Движок JavaScript Chromium V8 реализует SSA в своей инфраструктуре компилятора Crankshaft, как было объявлено в декабре 2010 г.
• PyPy использует линейное представление SSA для трассировок в своем JIT-компиляторе.
• Виртуальная машина Android Dalvik использует SSA в своем JIT-компиляторе.
• Новый оптимизирующий компилятор Android для Android Runtime использует SSA для своего IR. ^[24]
• Стандартный компилятор MLton использует SSA в одном из своих промежуточных языков.
• LuaJIT активно использует оптимизации на основе SSA. ^[25]
• Компилятор PHP и Hack HHVM использует SSA в своем IR. [ ^26]
• libFirm, библиотека для использования в качестве среднего и внутреннего интерфейсов компилятора , использует форму SSA для всех скалярных значений регистров до генерации кода с использованием распределителя регистров, поддерживающего SSA. ^[27]
• Различные драйверы Mesa через NIR, представление SSA для языков затенения. ^[28]

• Виртуальная машина Java HotSpot компании Oracle использует в своем JIT-компиляторе промежуточный язык на основе SSA. ^[29]
• Бэкэнд компилятора Microsoft Visual C++ , доступный в Microsoft Visual Studio 2015 Update 3, использует SSA ^[30]
• SPIR-V , стандарт языка шейдеров для графического API Vulkan и языка ядра для вычислительного API OpenCL , является представлением SSA. ^[31]
• Семейство компиляторов IBM XL, включающее C, C++ и Fortran. ^[32]
• NVIDIA CUDA ^[33]

• Компилятор ETH Oberon-2 был одним из первых публичных проектов, включавших «GSA», вариант SSA.
• Компилятор Open64 использовал форму SSA в своем глобальном скалярном оптимизаторе, хотя код приводится в форму SSA до этого и выводится из формы SSA после. Open64 использует расширения формы SSA для представления памяти в форме SSA, а также скалярных значений.
• В 2002 году исследователи модифицировали JikesRVM компании IBM (тогда называвшуюся Jalapeño) для запуска как стандартного байт-кода Java , так и файлов классов байт-кода типобезопасного SSA ( SafeTSA ), и продемонстрировали значительные преимущества в производительности при использовании байт-кода SSA.
• jackcc — это компилятор с открытым исходным кодом для набора академических инструкций Jackal 3.0. Он использует простой 3-операндный код с SSA для промежуточного представления. В качестве интересного варианта он заменяет функции Φ так называемой инструкцией SAME, которая предписывает распределителю регистров поместить два активных диапазона в один и тот же физический регистр.
• Illinois Concert Compiler около 1994 года ^[34] использовал вариант SSA под названием SSU (Static Single Use), который переименовывает каждую переменную, когда ей присваивается значение, и в каждом условном контексте, в котором эта переменная используется; по сути, это статическая единая информационная форма, упомянутая выше. Форма SSU задокументирована в докторской диссертации Джона Плевиака.
• Компилятор COINS использует оптимизацию форм SSA, как описано здесь.
• Компилятор R-Stream от Reservoir Labs поддерживает формы, отличные от SSA (квад-список), SSA и SSI (статическая одиночная информация ^[35] ). ^[36]
• Хотя декомпилятор 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). Современная реализация компилятора в машинном обучении . Cambridge University Press. 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.
• Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation . Морган Кауфманн. ISBN 978-1-55860-320-2.
• Келси, Ричард А. (март 1995 г.). «Соответствие между стилем передачи продолжения и формой статического одиночного назначения». Уведомления ACM SIGPLAN . 30 (3): 13– 22. doi : 10.1145/202530.202532 .
• Appel, Andrew W. (апрель 1998 г.). «SSA — функциональное программирование». ACM SIGPLAN Notices . 33 (4): 17– 20. doi : 10.1145/278283.278285 . S2CID  207227209.
• Поп, Себастьян (2006). «Структура представления SSA: семантика, анализ и реализация GCC» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
• Маттиас Браун; Себастьян Бухвальд; Себастьян Хак; Роланд Лейсса; Кристоф Маллон; Андреас Цвинкау (2013), «Простая и эффективная конструкция статической одиночной формы присваивания», Compiler Construction , Lecture Notes in Computer Science, т. 7791, Springer Berlin Heidelberg, стр.  102–122 , doi : 10.1007/978-3-642-37051-9_6 , ISBN 978-3-642-37050-2, получено 24 марта 2013 г.

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