SSA для стекового машинного кода

Question

Я работаю над компилятором для стековой машины (в частности, CIL), и я проанализировал код в графе базовых блоков. Отсюда я ищу применение SSA к методам, но это не слишком хорошо. Моя первая попытка (при работе с плоским списком, а не с графиком) состояла в том, чтобы перебрать код и сохранить стек идентификаторов SSA (то есть для целей назначения), выдвигая их при создании назначения, выдавливая их при они используются. Это прекрасно работает для одного базового блока, но я просто не могу понять, как обрабатывать создание функций Φ.

Идея, которую я обсуждаю, заключается в том, чтобы прикрепить позицию стека к идентификаторам SSA, а затем посмотреть, что все еще находится в стеке, когда пути кода сходятся, но это не похоже на правильный путь (TM).

Существует ли простой алгоритм для отслеживания манипуляций со стеком по нескольким путям кода и определения коллизий, когда они сходятся?

Answer 1

Вам нужно взглянуть на множественный набор идентификаторов SSA, сходящихся на узле (базовый блок). Сохраняйте промежуточную базовую структуру блока, чтобы вы могли легко использовать (например, запрашивать) все идентификаторы в блоке.

Я не уверен, что вы имеете в виду под столкновением, но я предполагаю, что вы хотите решить что-то вроде

 if (bExp)                  if (bExp)
   x := 1                    x1 := 1
 else            SSA:       else
   x := 2                    x2 := 2
 y := x;                    y := Phi(x1,x2)

то есть вы хотите Фи в этом месте. Поймите, что в исполняемом коде нет Фи! Используя информацию о том, что y (зависит) от x1 или x2, вы можете переписать это на следующем шаге. Например, в представлении, ориентированном на память, Phi(x1,x2) говорит вам, что x1 и x2 должны быть двумя псевдонимами в одной и той же ячейке памяти, а именно у y. Фи просто связывает информацию вместе.

if (bExp)
  stackframe[y_index] = 1     (y_index being some offset)
else
  stackframe[y_index] = 2
nop

Надеюсь это немного поможет!