用于堆栈机器代码的SSA

Question

我正在为堆栈机器(特别是CIL)开发一个编译器，我已经将代码解析成一个基本块的图形。从这里开始，我希望将SSA应用到方法中，但进展不是很顺利。我的第一个尝试(使用平面列表，而不是图形)是遍历代码并保留一堆SSA (即，用于赋值目标)，在我生成赋值时推送它们，在使用它们时弹出它们。这对于单个基本块来说工作得很好，但我就是想不出如何处理Φ函数的生成。

我一直在考虑的想法是将堆栈位置附加到SSA，然后在代码路径收敛时查看堆栈上还有什么，但这似乎不是正确的处理方式(TM)。

有没有一种简单的算法来跟踪多个代码路径上的堆栈操作，并在它们收敛时确定冲突？

Answer 1

您需要查看在一个节点(基本块)上聚合的SSA 的多个集。保留中间的基本块结构，这样你就可以很容易地使用(例如查询)块中的所有标识符。

我不知道你说的碰撞是什么意思，但我假设你想要解决像这样的问题

 if (bExp)                  if (bExp)
   x := 1                    x1 := 1
 else            SSA:       else
   x := 2                    x2 := 2
 y := x;                    y := Phi(x1,x2)

也就是说，你想要这个地方的Phi。认识到可执行代码中没有Phi！使用y依赖于x1或x2的信息，您可以在下一步中重写此信息。例如，在以内存为中心的表示中，Phi( x1，x2)告诉您x1和x2应该是同一内存位置的两个别名，即y的别名。Phi只是将信息绑定在一起。

if (bExp)
  stackframe[y_index] = 1     (y_index being some offset)
else
  stackframe[y_index] = 2
nop

希望这能对你有所帮助！