时间戳

首页 > 解决方案 > 将 SSA 转换为堆栈机

compiler-construction - 将 SSA 转换为堆栈机

问题描述

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

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

标签： compiler-constructioncilssastack-machine

解决方案

自从我参与编译器构建以来已经超过 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操作。

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

推荐阅读