Форма 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









 
архив

подписка