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

Question

Я работаю над компилятором для стековой машины (в частности КИЛ), и я разобрал код в граф основных блоков.Отсюда я хочу подать заявку ССА к методам, но дела идут не очень хорошо.Моя первая попытка (при работе с плоским списком, а не с графиком) заключалась в том, чтобы перебирать код и сохранять стек идентификаторов 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

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