我们都知道如何将代码从SSA表示法转换为寄存器机器码。 （基本上，图形着色寄存器分配是这种转换的核心。）
但是，将代码从SSA转换为堆栈机器有什么通用方法吗？（在我正在查看的情况下，是CIL字节码。）考虑到不需要寄存器分配，我预计这会更简单一些。
2个回答
6
我参与编译器构建已经超过15年了，所以我可能不记得所有的细节。
基本上，在退出SSA时，您需要在所有导向后继块中的phi节点的所有块的末尾生成虚拟寄存器的加载/存储指令。这将导致生成许多虚拟寄存器，通常比实际机器上可用的寄存器更多。因此，您需要对局部变量进行寄存器分配，找出真正的寄存器，并将那些不适合的值溢出到堆栈中。
对于基于堆栈的机器，只需不执行最后一步即可。您最终会得到大约与编译函数中的phi节点数量相同的虚拟寄存器（该算法实际上并不简单，一个很好的起点是Ron Cytron，Jeane Ferrante等人的论文“高效计算单个静态赋值形式和控制依赖图”）。这些虚拟寄存器将成为您的局部变量。
当从虚拟寄存器（局部变量）中读取值以供操作使用时，请先使用指令将其推送到堆栈上。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操作。
当然，有很多优化空间，以避免冗余的加载/存储操作。
- memo
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
- Ira Baxter
7
1如果只需要翻译表达式，那就足够了。但是在一般情况下，SSA
a、b等可能是任意顺序的，并且可能是带有副作用的函数调用，因此需要保留顺序，所以需要对每个基本块进行前向传递，以按给定顺序执行操作。如何将此与后缀顺序的反向链接场景相协调呢？ - rwallace3你的问题提出了一个基本见解，所以我的回答也是在同样的水平上。SSA基本上只是表达式；它是你代码块的功能等效物。真正的代码生成器生活更复杂。如果你有多个表达式共享子表达式（例如，具有多个结果的DAG），你需要首先递归地评估共享的子表达式，以便可以保持堆栈兼容的计算顺序；你可能需要一个内存位置来保存共享结果。 - Ira Baxter
5请注意，Phi节点增加了一些复杂性，因为它们的值可能来自非常不同的计算。它们也可能需要一个临时位置。好消息是，您可以使用寄存器着色来分配临时变量 :-}。如果操作符具有副作用，则必须向模型化需要排序的SSA节点添加附加的序列弧，并在代码生成过程中予以考虑。 - Ira Baxter
@IraBaxter 谢谢，您的解释很有启发性！如果没有(堆)内存位置来溢出共享子表达式的结果，但在 FORTH 中有适当的堆栈操作符，例如 'dup'、'drop'、'swap'、'rot'，该怎么办呢？由于支持的堆栈操作符集在不同的实现中是不同的，所以也许解决方案类似于优化编译或查询优化？ - Robert Monfera
嗯，鉴于共享子表达式的数量可能很少，您可以对（抽象化的）代码序列进行暴力搜索，并确定具有最小堆栈顶操作数量的代码。 - Ira Baxter
显示剩余2条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接