堆栈机代码的SSA

Question

我正在为一个栈机（具体来说是CIL）编写编译器，我已经将代码解析成基本块的图形。从这里开始，我想对方法应用SSA，但进展不顺。我的第一次尝试（在使用平面列表而不是图形时）是遍历代码并保留SSA ID的堆栈（即分配目标），当我生成分配时将它们推入堆栈中，并在使用时将它们弹出。这对于单个基本块很好用，但我无法弄清楚如何处理产生Φ函数。

我一直在考虑的想法是将一个堆栈位置附加到SSA ID上，然后查看在代码路径汇合时仍在堆栈上的内容，但这似乎不是正确的做法。

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

- Cody Brocious

---

编译器的事情有进展了吗？我正在考虑做完全相同的事情。 - David Given

我正在将LLVM IR转换为SSA到堆栈机器代码。您能否在这里分享一下您的经验？如果有Github链接会更好。 - sinoTrinity

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

希望这能够有所帮助！

- vs

---

非常感谢。我已经掌握了其中99%，但由于某种原因，堆栈位置似乎不够。在您的回答和微软研究的Marmot编译器论文之间，现在我已经全都懂了 :) - Serafina Brocious