将SSA转换为堆栈计算机

Question

众所周知如何将代码从SSA表示转换为寄存器机器.(基本上,图形着色寄存器分配是这种转换的核心.)

但是从SSA转换为堆栈机器的一般方法是什么？(CIL字节代码,在我看的情况下.)我希望它更简单,因为不需要寄存器分配？

Answer 1

我参与编译器构建已经超过 15 年了，所以我可能不记得所有细节了。

基本上，当走出 SSA 时，您需要在通向后续块中 phi 节点的所有块末尾的虚拟寄存器中生成加载/存储指令。这将导致生成许多虚拟寄存器，这些虚拟寄存器通常高于实际机器上的可用寄存器。因此，您对局部变量应用寄存器分配以得出真正的寄存器，将那些不适合的值溢出到堆栈上。

对于基于堆栈的机器，只需不要执行最后一步即可。您最终会得到与编译函数中的 phi 节点数量大致相同的虚拟寄存器（该算法实际上并不简单，一个很好的起点是 Ron Cytron、Jeane 的论文《高效计算单一静态赋值形式和控制依赖图》） Ferrante 等人）这些虚拟寄存器将是您的局部变量。

当从虚拟寄存器（局部变量）读取值以供操作使用时，首先使用指令将其压入堆栈。Java VMiload index指令就是这样一个例子：它加载索引处的局部变量并将其值压入堆栈。（请参阅https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.5.iload）将值写入局部变量时，会将其从堆栈中弹出。请参阅 Java VMistore index指令（请参阅https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.5.istore）。

例如，如果走出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 对 a,b,c 进行 3 次推送，然后是 MAC_TOS 运算符。

如果一个人有一系列这样的门，你可以取一个早先的门的输出，它已经在堆栈上，就像它被压入一样。

所以，SSA 计算看起来像一个 n 元的门树，输出在根处。

您可以按固定顺序遍历树，推送尚未推送的操作数，并在计算完所有操作数后生成门运算符。

所以SSA图（树）：

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

可用于生产

push a
push b
times
push c
push d
subtract
times

您会注意到 phi 节点增加了复杂性，因为它们的值可能来自非常不同的计算。他们也可能需要一个临时位置。好消息：您可以使用寄存器着色来分配临时变量 :-} 。如果您有运算符的副作用，那么您将不得不向 SSA 节点添加额外的排序弧，在需要排序的地方建模，并在代码生成过程中兑现. (5认同)
您的问题被表述为基本见解，所以我的回答处于同一级别：SSA 基本上是 *only* 表达式；它是代码块的功能等价物。真正的代码生成器过着更复杂的生活。如果您有多个共享子表达式的表达式（例如，具有多个结果的 DAG），您希望首先（递归地）评估共享子表达式，以便您可以维护计算的堆栈兼容顺序；您可能需要一个内存位置来保存共享结果。 (3认同)