SSA
SSA (англ. Static single assignment form) — промежуточное представление, используемое компиляторами, в котором каждой переменной значение присваивается лишь единожды. Переменные исходной программы разбиваются на версии, обычно с помощью добавления суффикса, таким образом, что каждое присваивание осуществляется уникальной версии переменной. В SSA-представлении DU-цепи (англ. def-use) заданы явно и содержат единственный элемент.
SSA-представление было разработано исследователями IBM Роном Ситроном (Ron Cytron), Жаном Феррантом (Jeanne Ferrante), Барри Розеном (Barry Rosen), Марком Уэгменом (англ. Mark N. Wegman) и Кеном Задеком (Ken Zadeck) в 1980-е годы.
В компиляторах функциональных языков программирования, таких как Scheme, ML и Haskell, вместо SSA обычно используется CPS-представление (англ. Continuation-passing style). Формально эти представления эквивалентны, поэтому оптимизации и трансформации, сформулированные в одном из представлений, могут быть применены и для другого.
Преимущества SSA
[править | править код]Для кода в SSA-форме проще и эффективнее проводить многие виды компиляторной оптимизации. Например, в следующем коде:
y := 1 y := 2 x := y
для человека очевидно, что первое присваивание не нужно, так как значение y, использованное в третьей строчке, соответствует второму присваиванию. Однако для того, чтобы выяснить это, компилятору пришлось бы прибегнуть к анализу достигающих определений. Но с использованием SSA-представления это становится гораздо проще:
y1 := 1 y2 := 2 x1 := y2
SSA делает возможными или существенно упрощает следующие оптимизационные алгоритмы:
- свёртка констант
- удаление мёртвого кода
- нумерация глобальных значений
- частичное устранение избыточности
- снижение стоимости операций
- распределение регистров
Перевод в SSA
[править | править код]Перевод обычного программного кода в SSA-представление достигается путём замены в каждой операции присваивания переменной из левой части на новую переменную. Для каждого использования значения переменной исходное имя заменяется на имя «версии», соответствующей нужному базовому блоку. Рассмотрим следующий граф потока управления:
В соответствии с определением SSA создадим вместо переменной x две новые переменные x1 и x2. Каждой из них значение будет присвоено ровно один раз. Аналогичным образом заменим остальные переменные, после чего получим следующий граф:
Пока остаётся неясным, какое значение y будет использоваться в нижнем блоке. Там имя y может означать как y1, так и y2. Для того, чтобы разрешить неоднозначности такого рода, в SSA введена специальная Φ-функция. Эта функция создаёт новую версию переменной y, которой будет присвоено значение либо из y1, либо из y2, в зависимости от того, из какой ветви перешло управление.
При этом использовать Φ-функцию для переменной x не нужно, так как лишь одна версия x (а именно, x2) «достигает» последнего блока.
Φ-функция в действительности не реализована; она представляет собой лишь указание компилятору хранить все переменные, перечисленные в списке её аргументов, в одном и том же месте в памяти (или регистре).
Более общий вопрос состоит в том, можно ли по заданному графу потока управления понять, где и для каких переменных в SSA-представление нужно вставить Φ-функции? Ответ на этот вопрос можно получить с помощью доминаторов.
Компиляторы, использующие SSA
[править | править код]- Oberon-2
- LLVM
- Open64
- GCC
- Jikes RVM[англ.]
- HotSpot
- jackcc
- Portable.NET
- libFirm
- COINS compiler
- V8
- PyPy
- Dalvik virtual machine
- MLton
- LuaJIT
- Go [1]
- Excelsior JET
Литература
[править | править код]- Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4.
- Робин Хантер. Основные концепции компиляторов = The Essence of Compilers. — М.: Вильямс, 2002. — С. 256. — ISBN 0-13-727835-7.
- R. Allen, K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann Publishers, 2002.
- A. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998.
- S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.
Примечания
[править | править код]- ↑ New SSA Backend for the Go Compiler. Дата обращения: 16 августа 2016. Архивировано 2 октября 2016 года.
Ссылки
[править | править код]- Steven Bosscher и Diego Novillo. GCC gets a new Optimizer Framework. Статья об использовании SSA-представления в GCC.
- The SSA Bibliography. Каталог исследовательских статей по SSA-представлению.
- F. K. Zadeck. «The Development of Static Single Assignment Form», рассказ о корнях SSA-представления в декабре 2007.