Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Преимущества [ править ]

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

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

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

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

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

Переход на SSA [ править ]

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

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

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

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

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

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

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

По словам Кенни Задека [5] Φ-функции изначально назывались фальшивыми функциями, в то время как 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). См. Статью для более подробной информации. [6]

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

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

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

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

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

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

Урезанный SSA [ править ]

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

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

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

Полуобрезанный SSA [ править ]

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

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

Преобразование формы SSA [ править ]

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

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

Расширения [ править ]

Расширения формы 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 компилятором. [11]
  • Серверная часть компилятора Microsoft Visual C ++, доступная в Microsoft Visual Studio 2015 с обновлением 3, использует SSA [12]
  • 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 [13] использовал вариант SSA под названием SSU (Static Single Use), который переименовывает каждую переменную, когда ей присваивается значение, и в каждом условном контексте, в котором эта переменная используется; по сути, статическая единая информационная форма, упомянутая выше. Форма SSU задокументирована в докторской диссертации Джона Плевяка .
  • Компилятор COINS использует оптимизацию формы SSA, как описано здесь: http://www.is.titech.ac.jp/~sassa/coins-www-ssa/english/
  • Mozilla Firefox SpiderMonkey движок JavaScript использует SSA на основе ИК. [14]
  • Механизм JavaScript Chromium V8 реализует SSA в своей инфраструктуре компилятора Crankshaft, как было объявлено в декабре 2010 года.
  • PyPy использует линейное представление SSA для трассировок в своем JIT-компиляторе.
  • Android «s Dalvik виртуальная машина использует SSA в JIT компилятором.
  • Android новый оптимизирующий компилятор «s для Android Время воспроизведения использует SSA для его ИК.
  • Компилятор MLton Standard MLton использует SSA на одном из промежуточных языков.
  • LuaJIT активно использует оптимизацию на основе SSA. [15]
  • PHP и Hack компилятор HHVM использует SSA в ИК. [16]
  • Компилятор R-Stream от Reservoir Labs поддерживает формы, отличные от SSA (список квадратов), SSA и SSI (статическая единичная информация [17] ). [18]
  • Go (1.7: только для архитектуры x86-64; 1.8: для всех поддерживаемых архитектур). [19] [20]
  • SPIR-V , стандарт языка затенения для графического API Vulkan и язык ядра для API вычислений OpenCL , является представлением SSA. [21]
  • Различные драйверы Mesa через NIR, представление SSA для языков затенения. [22]
  • WebKit использует SSA в своих JIT-компиляторах. [23] [24]
  • Swift определяет свою собственную форму SSA над LLVM IR, которая называется SIL (Swift Intermediate Language). [25] [26]
  • Erlang переписал свой компилятор в OTP 22.0, чтобы «внутренне использовать промежуточное представление, основанное на статическом одиночном назначении (SSA)». С планами по дальнейшей оптимизации, основанным на SSA в будущих выпусках. [27]

Ссылки [ править ]

Заметки [ править ]

  1. ^ Барри Розен; Марк Н. Вегман; Ф. Кеннет Задек (1988). «Глобальные числа значений и избыточные вычисления» (PDF) . Материалы 15-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования .
  2. ^ Cytron, Рон; Ферранте, Жанна; Розен, Барри К .; Вегман, Марк Н. и Задек, Ф. Кеннет (1991). «Эффективное вычисление статической формы единого назначения и графика зависимости управления» (PDF) . Транзакции ACM по языкам и системам программирования . 13 (4): 451–490. CiteSeerX 10.1.1.100.6361 . DOI : 10.1145 / 115372.115320 . S2CID 13243943 .   
  3. ^ Келси, Ричард А. (1995). «Соответствие между стилем передачи продолжения и статической формой одиночного назначения» (PDF) . Материалы семинара ACM SIGPLAN 1995 года по промежуточным представлениям : 13–22. DOI : 10.1145 / 202529.202532 . ISBN  0897917545. S2CID  6207179 .
  4. ^ распространение диапазона значений
  5. ^ см. стр. 43 [«Происхождение Ф-функций и имя»] Задека, Ф. Кеннета, Презентация по истории SSA на семинаре SSA'09 , Отран, Франция, апрель 2009 г.
  6. ^ Cytron, Рон; Ферранте, Жанна; Розен, Барри К .; Wegman, Mark N .; Задек, Ф. Кеннет (1 октября 1991 г.). «Эффективное вычисление статической формы единого назначения и графика зависимости управления». Транзакции ACM по языкам и системам программирования . 13 (4): 451–490. DOI : 10.1145 / 115372.115320 . S2CID 13243943 . 
  7. ^ а б Купер, Кейт Д.; Харви, Тимоти Дж .; Кеннеди, Кен (2001). «Простой и быстрый алгоритм доминирования» (PDF) . Цитировать журнал требует |journal=( помощь )
  8. ^ Бриггс, Престон; Купер, Кейт Д.; Харви, Тимоти Дж .; Симпсон, Л. Тейлор (1998). «Практические улучшения в построении и уничтожении статической формы единого назначения» (PDF) . Архивировано из оригинального (PDF) 07.06.2010. Цитировать журнал требует |journal=( помощь )
  9. ^ фон Ронне, Джеффри; Нин Ван; Майкл Франц (2004). «Устный перевод программ в статической форме однократного задания» . Цитировать журнал требует |journal=( помощь )
  10. ^ Буассино, Бенуа; Дарте, Ален; Растелло, Фабрис; Динешин, Бенуа Дюпон де; Гийон, Кристоф (2008). «Пересмотр перевода вне SSA на предмет правильности, качества кода и эффективности» . HAL-Inria Cs.DS : 14.
  11. ^ «Архитектура Java HotSpot Performance Engine» . Корпорация Oracle.
  12. ^ «Представляем новый усовершенствованный оптимизатор кода Visual C ++» .
  13. ^ "Концертный проект Иллинойса" .
  14. ^ «Обзор IonMonkey» .,
  15. ^ «Оптимизация байт-кода» . проект LuaJIT.
  16. ^ "Представление среднего уровня HipHop (HHIR)" .
  17. ^ Ананиан, К. Скотт; Ринард, Мартин (1999). «Статическая единая информационная форма». CiteSeerX 10.1.1.1.9976 .  Цитировать журнал требует |journal=( помощь )
  18. ^ «Энциклопедия параллельных вычислений» .
  19. ^ «Примечания к выпуску Go 1.7 - язык программирования Go» . golang.org . Проверено 17 августа 2016 .
  20. ^ «Примечания к выпуску Go 1.8 - язык программирования Go» . golang.org . Проверено 17 февраля 2017 .
  21. ^ "SPIR-V spec" (PDF) .
  22. ^ Экстранд, Джейсон. «Повторное внедрение NIR, нового IR для мезы» .
  23. ^ "Представляем WebKit FTL JIT" .
  24. ^ «Представляем JIT-компилятор B3» .
  25. ^ «Swift Intermediate Language (GitHub)» .
  26. ^ «Высокоуровневый IR Swift: пример дополнения LLVM IR с языково-зависимой оптимизацией, встреча разработчиков LLVM 10/2015» .
  27. ^ «Примечания к выпуску OTP 22.0» .

Общие ссылки [ править ]

  • Аппель, Эндрю В. (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. DOI : 10.1145 / 202530.202532 .
  • Аппель, Эндрю В. (апрель 1998 г.). «SSA - это функциональное программирование». Уведомления ACM SIGPLAN . 33 (4): 17–20. DOI : 10.1145 / 278283.278285 . S2CID  207227209 .
  • Поп, Себастьян (2006). «Структура представления SSA: семантика, анализ и реализация GCC» (PDF) . Цитировать журнал требует |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.
  • В.В.АА. «Дизайн компилятора на основе SSA» (2014 г.)