堆栈机器代码的SSA

我正在为堆栈机器(特别是CIL)编译器,我已经将代码解析为基本块的图形.从这里开始,我希望将SSA应用于这些方法,但这并不是太顺利.我的第一次尝试(使用平面列表,而不是图形)是迭代代码并保留一堆SSA ID(即,对于分配目标),在我生成赋值时推送它们,当它们弹出时弹出它们他们被使用了.这适用于单个基本块,但我根本无法弄清楚如何处理生成Φ函数.

我一直在徘徊的想法是将堆栈位置附加到SSA ID,然后在代码路径收敛时查看堆栈中仍然存在的内容,但这似乎不是做事的Right Way(TM).

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

您需要查看在节点上聚合的多组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

希望这个对你有帮助!