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

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

9 голосов
/ 27 февраля 2009

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

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

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

1 Ответ

9 голосов
/ 27 февраля 2009

Вам нужно взглянуть на множественный набор идентификаторов 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

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

...