Форма SSAМногие услышав аббревиатуру SSA сразу подумают о прогнозирования временных рядов методом SSA или о Social Security Administration. В нашем же случае мы поговорим о технологии, которая используется в компиляторах для оптимизации процесса генерации бинарного кода. SSA (Static single assignment form) — это промежуточное представление, используемое компиляторами, в котором каждой переменной значение присваивается лишь единожды. Это представление было разработано в 80-ые годы исследователями из IBM. В процессе построения SSA переменные исходной программы разбиваются на версии, обычно с помощью добавления суффикса, таким образом, что каждое присваивание осуществляется уникальной версии переменной. В компиляторах функциональных языков программирования, таких как Scheme, ML и Haskell, вместо SSA обычно используется CPS-представление (Continuation-passing style). Формально эти представления эквивалентны, поэтому оптимизации и трансформации, сформулированные в одном из представлений, могут быть применены и для другого. К преимуществам SSA стоит отнести, то что для кода в SSA-форме проще и эффективнее выполнять многие виды компиляторной оптимизации. Например, в следующем коде:
для человека очевидно, что первое присваивание не нужно, так как значение y, использованное в третьей строчке, соответствует второму присваиванию. Однако для того, чтобы выяснить это, компилятору пришлось бы прибегнуть к анализу достигающих определений. Но с использованием SSA-представления это становится гораздо проще:
SSA делает возможными или существенно упрощает следующие оптимизационные алгоритмы:
Перевод обычного программного кода в SSA-представление достигается путём замены в каждой операции присваивания переменной из левой части на новую переменную. Для каждого использования значения переменной исходное имя заменяется на имя «версии», соответствующей нужному базовому блоку. В соответствии с определением SSA создадим вместо переменной x две новые переменные x1 и x2. Каждой из них значение будет присвоено ровно один раз. Аналогичным образом заменим остальные переменные, после чего получим следующий граф: Пока остаётся неясным, какое значение y будет использоваться в нижнем блоке. Там имя y может означать как y1, так и y2. Для того, чтобы разрешить неоднозначности такого рода, в SSA введена специальная φ-функция. Эта функция создаёт новую версию переменной y, которой будет присвоено значение либо из y1, либо из y2, в зависимости от того, из какой ветви перешло управление. Синтаксис и семантика φ-функции:
В настоящее время SSA активное используется в:
23.04.2017 |
популярные тэги
наука
интересно
новости
технологии
история
go
golang
программирование
it
искусственный интеллект
путешествия
природа
космос
ai
базы данных
медицина
science
анализ текстов
ии
text mining
робототехника
авто
музыка
роботы
интернет
нейронные сети
robots
space
вокруг света
postgresql
алгоритмы
гитара
животные
оружие
google
nosql
авиация
здоровье
техника
auto
|