将 SSA 转换为堆叠机

Question

众所周知如何将代码从 SSA 表示形式转换为寄存器机。（基本上，图形着色寄存器分配是这种转换的核心。）

但是从SSA转栈机的一般方法是什么？（CIL 字节码，在我正在查看的情况下。）鉴于不需要寄存器分配，我希望它更简单？

Answer 1

SSA 基本上是一组 "logic" 个门，每个门都有多个输入，通常有一个输出。

因此，本质上，您需要将每个门视为输入的一组堆栈推送，然后是一个零操作数运算符，该运算符将堆栈值组合到该门的结果中。例如，a + b * c as SSA with a multiply-and-accumulate operator 对 a,b,c 进行 3 次推送，然后是 MAC_TOS 运算符。

如果有一个这样的门链，您可以获取已经在堆栈中的较早门的输出，并且就像它已被压入一样简单地工作。

因此，SSA 计算看起来像一棵 n 元门树，输出在根部。

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

因此 SSA 图（树）：

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

可以用来生产

push a
push b
times
push c
push d
subtract
times

Answer 2

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

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

对于基于堆栈的机器，不要执行最后一步。您最终得到的虚拟寄存器数量与编译函数中的 phi 节点数量大致相同（该算法实际上并不简单，一个好的起点是 Ron Cytron 的论文 Efficiently Computing Single Static Assignment Form and the Control Dependence Graph，Jeane Ferrante, et. al.) 这些虚拟寄存器将成为您的局部变量。

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

当然还有很大的优化空间，避免冗余load/store。

将 SSA 转换为堆叠机

Converting SSA to stack machine

compiler-construction

cil

stack-machine

ssa