18

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

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

4

2 回答 2

6

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

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

对于基于堆栈的机器，不要做最后一步。您最终会得到与编译函数中的 phi 节点大致相同数量的虚拟寄存器（该算法实际上并不简单，一个好的起点是 Ron Cytron 的论文 Efficiently Computing Single Static Assignment Form and the Control Dependence Graph，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操作。

当然，还有很大的优化空间，以避免多余的加载/存储。

于 2018-07-23T12:49:33.657 回答
5

SSA 基本上是一组“逻辑”门，每个门都有多个输入，通常有一个输出。

因此，基本上您需要将每个门视为输入的一组堆栈推送，然后是一个零操作数运算符，将堆栈值组合到该门的结果中。例如，作为 SSA 的 a + b * c 使用乘法和累加运算符对 a、b、c 进行 3 次推送，然后是 MAC_TOS 运算符。

如果一个人有一串这样的门，你可以取一个较早的门的输出，它已经在堆栈上，就像它被推送一样。

因此，SSA 计算看起来像一个 n 叉树，其输出从根开始。

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

所以SSA图（树）：

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

可用于生产

push a
push b
times
push c
push d
subtract
times
于 2018-07-17T03:48:28.397 回答