Преобразование SSA в стек

Question

Хорошо известно, как преобразовать код из представления SSA в машину регистрации. (По сути, распределение регистров раскраски графа является ядром такого преобразования.)

Но каков общий метод преобразования SSA в стековую машину? (Байт-код CIL, в случае, который я рассматриваю.) Я ожидал бы, что это будет проще, учитывая отсутствие необходимости в распределении регистров?

Answer 1

Прошло более 15 лет с тех пор, как я принимал участие в создании компилятора, поэтому я не могу вспомнить все детали.

По сути, при выходе из SSA вам необходимо генерировать инструкции загрузки / сохранения в виртуальные регистры в конце всех блоков, ведущих к фи-узлам в последующих блоках. Это приведет к созданию нескольких виртуальных регистров, которые обычно выше, чем доступные регистры на реальном компьютере. Таким образом, вы применяете распределение регистров к локальным переменным, чтобы получить реальные регистры, проливая в стек те значения, которые не подходят.

Для стековой машины просто не делайте последний шаг. В итоге вы получите примерно такое же количество виртуальных регистров, что и фи-узлов в скомпилированной функции (алгоритм на самом деле не тривиален, хорошей отправной точкой является статья "Эффективное вычисление формы одного статического назначения и график зависимостей управления" Рона Цитрона, Джин Ферранте и др.) Эти виртуальные регистры будут вашими локальными переменными.

При чтении значения из виртуального регистра (локальной переменной), которое будет использоваться операцией, сначала используйте инструкцию, чтобы поместить его в стек. Java VM iload index инструкция является таким примером: она загружает локальную переменную по индексу и помещает ее значение в стек. (см. https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html) При записи значения в локальную переменную вы извлекаете его из стека. Смотрите Java VM istore index инструкция (см. https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html).

Например, если после выхода из SSA вам необходимо кодировать

local 5 = MUL local[2], local[4]

тогда вам нужно сгенерировать что-то вроде этого:

ILOAD 4 ILOAD 2 MUL ISTORE 5

Для байт-кода CIL у вас есть эквивалент ldarg а также starg операции.

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

Answer 2

SSA - это набор логических элементов, каждый из которых имеет несколько входов и, как правило, один выход.

Таким образом, по сути, вам нужно рассматривать каждый вентиль как набор стековых толчков для входов, за которым следует оператор с нулевым операндом, который объединяет значения стека в результат для этого вентиля. Например, a + b * c в качестве SSA с оператором умножения и накопления имеет 3 нажатия для a, b, c, за которыми следует оператор MAC_TOS.

Если у кого-то есть цепочка таких шлюзов, вы можете взять вывод более раннего гейта, который уже находится в стеке, и просто действует так, как если бы он был перемещен.

Итак, вычисления SSA выглядят как n-арное дерево вентилей с выводом в корне.

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

Итак, график SSA (дерево):

a 
  \
   * 
b /  \
      +
c     /
  \  /
   -
  /
d

может быть использован для производства

push a
push b
times
push c
push d
subtract
times