SSA () — промежуточное представление, используемое компиляторами, в котором каждой переменной значение присваивается лишь единожды. Переменные исходной программы разбиваются на версии, обычно с помощью добавления суффикса, таким образом, что каждое присваивание осуществляется уникальной версии переменной. В SSA-представлении DU-цепи () заданы явно и содержат единственный элемент.
SSA-представление было разработано исследователями IBM Роном Ситроном (Ron Cytron), Жаном Феррантом (Jeanne Ferrante), Барри Розеном (Barry Rosen), и Кеном Задеком (Ken Zadeck) в 1980-е годы.
В компиляторах функциональных языков программирования, таких как Scheme, ML и Haskell, вместо SSA обычно используется CPS-представление (). Формально эти представления эквивалентны, поэтому оптимизации и трансформации, сформулированные в одном из представлений, могут быть применены и для другого.
Преимущества 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
HotSpot jackcc Portable.NET libFirm COINS compiler V8 PyPy Dalvik virtual machine MLton LuaJIT Go Excelsior JET
Литература
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.
Примечания
Ссылки 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.
Категория:Теория компиляторов