Phi node 是如何实现它的功能的?

看《编译原理》只明白它的起作用的机理是怎么样的,但是(到了汇编/机器码的阶段)它是如何实现的呢? 是会生成一段汇编代码,在运行时进行判断传入的变量值,然后再输出新的变量的值?
关注者
116
被浏览
6011
由于目标指令集多半不支持“Phi”的概念,编译器里通常会有一个pass是“resolution”,把Phi node给resolve为move(也叫copy insertion),经过了resolution之后再生成具体的目标代码。经过Phi resolution的IR就退出了SSA形式,所以这个动作也叫做SSA destruction,缩写de-SSA。在编译器的源码里看到名如“PhiResolver”之类的东西那就是这玩儿了。

举例来说,如果在一个基本块B2的开头有:
x2 = phi(x0, x1)
那么最简单的resolution做法就是:假如x0在基本块B0定义,x1在基本块B1定义,并且假如x0分配到了R1,x1分配到了R2,x2分配到了R3,那么在B0的末尾会生成:
move R3 <- R1
而在B1末尾则会生成:
move R3 <- R2
这样后面R3就得到正确的x2的值了。
当然举的这个例子所生成的代码比较浪费寄存器。实际上如果Phi resolution在寄存器分配之前做,那么寄存器分配器通常会想办法把Phi引发的move给coalesce到同一个寄存器,这样可能x0和x1都会被设法分配到R2上,就不需要那个额外的move来实现Phi的语义了。

这种resolution可以发生在寄存器分配之前,也可以发生在寄存器分配之后。现在比较常见的是先做了resolution再做寄存器分配,这样的话寄存器分配就不是在SSA形式上进行的;但是因为SSA形式上的干涉图是cordal graph,在它上面做寄存器分配也可以很方便,所以现在也有一些编译器选择在寄存器分配之后才做Phi resolution。