用于堆栈机器代码的 SSA

Question

我正在为堆栈机开发编译器（特别是 CIL），并且我已经解析了代码转换为基本块图。 从这里开始，我希望将 SSA 应用于这些方法，但进展不太顺利。 我的第一次尝试（在使用平面列表而不是图表时）是迭代代码并保留一堆 SSA id（即，用于分配目标），在生成分配时推送它们，在生成分配时弹出它们他们被使用了。 这对于单个基本块来说效果很好，但我根本不知道如何处理生成 Φ 函数。

我一直在折腾的想法是将堆栈位置附加到 SSA id，然后在代码路径收敛时查看堆栈上仍然有什么，但这似乎不是做事的正确方法（TM）。

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

Answer 1

您需要查看汇聚在一个节点（基本块）上的多个SSA id 集。 保留中间的基本块结构，这样您就可以轻松使用（例如查询）块中的所有标识符。

我不确定你所说的碰撞是什么意思，但我假设你想要解决类似的问题

 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

希望这个对你有帮助！