Форма 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 := 1
y := 2
x := y

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

y1 := 1
y2 := 2
x1 := y2

SSA делает возможными или существенно упрощает следующие оптимизационные алгоритмы:

свёртка констант
удаление мёртвого кода
нумерация глобальных значений
частичное устранение избыточности
снижение стоимости операций
распределение регистров

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

В соответствии с определением SSA создадим вместо переменной x две новые переменные x1 и x2. Каждой из них значение будет присвоено ровно один раз. Аналогичным образом заменим остальные переменные, после чего получим следующий граф:

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

Синтаксис и семантика φ-функции:

находится в начале узла, в котором сходятся несколько дуг
количество операндов равно количеству входящих в узел дуг
при переходе управления по i-той входной дуге φ-функция эквивалентна присваиванию
‘y3 = yi’

В настоящее время SSA активное используется в:

LLVM
GCC
V8
PyPy
LuaJIT
Mono
Oracle JIT compiler
MS Visual C++ 2015
Go и др.

23.04.2017

ssa компиляторы