Interested Article - SSA

SSA ( англ. Static single assignment form ) — промежуточное представление, используемое компиляторами , в котором каждой переменной значение присваивается лишь единожды. Переменные исходной программы разбиваются на версии, обычно с помощью добавления суффикса, таким образом, что каждое присваивание осуществляется уникальной версии переменной. В SSA-представлении DU-цепи ( англ. def-use ) заданы явно и содержат единственный элемент.

SSA-представление было разработано исследователями IBM Роном Ситроном ( Ron Cytron ), Жаном Феррантом ( Jeanne Ferrante ), Барри Розеном ( Barry Rosen ), ( англ. ) и Кеном Задеком ( 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 две новые переменные x ₁ и x ₂ . Каждой из них значение будет присвоено ровно один раз. Аналогичным образом заменим остальные переменные, после чего получим следующий граф:

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

При этом использовать Φ-функцию для переменной x не нужно, так как лишь одна версия x (а именно, x ₂ ) «достигает» последнего блока.

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

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

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

Литература

Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = 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.

Примечания

. Дата обращения: 16 августа 2016. 2 октября 2016 года.

Ссылки

Steven Bosscher и Diego Novillo. . Статья об использовании SSA-представления в GCC .
. Каталог исследовательских статей по SSA-представлению.
F. K. Zadeck. , рассказ о корнях SSA-представления в декабре 2007.