Phi node 是如何實現它的功能的？

看《編譯原理》只明白它的起作用的機理是怎麼樣的，但是（到了彙編/機器碼的階段）它是如何實現的呢？

是會生成一段彙編代碼，在運行時進行判斷傳入的變數值，然後再輸出新的變數的值？

---

由於目標指令集多半不支持「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。

---

RFX已經說的很好很好了，我想再直接補充一些實際例子來說明吧。

先順便補充一些背景材料。對於Phi，或者更確切的符號Φ，其主要解決的是SSA（Static Single Assignment）賦值一次的問題，如下面的例子：

a = 1;
if (v &< 10) a = 2; b = a;

由於靜態單賦值只能讓變數賦值一次，那麼這裡的b 到底取2 還是1 呢？這是無法決定的，而Phi 則是解決這樣的問題。

a1 = 1;
if (v &< 10) a2 = 2; b = PHI(a1, a2);

那麼Phi則會根據到達的是a1還是a2而選擇給b賦何值。See:Static single assignment form

而RFX提到的Resolution思路也是解決Phil的通用做法，其實也也非常容易舉例驗證，然後進行觀察。

int main()
{
int a = 47;
int b = 0;
if (a &> 47)
{
a = 47;
}
else
{
a = 1;
}
b = a + 13;
b = b + 1;
return 0;
}


這是一個非常簡單的例子，幾乎就是上面的偽代碼的翻版，我們把這個例子產生LLVM IR進行觀察。

define i32 @main() #0 {
entry:
%retval = alloca i32, align 4
%a = alloca i32, align 4
%b = alloca i32, align 4
store i32 0, i32* %retval
store i32 47, i32* %a, align 4
store i32 0, i32* %b, align 4
%0 = load i32* %a, align 4
%cmp = icmp sgt i32 %0, 47
br i1 %cmp, label %if.then, label %if.else

if.then: ; preds = %entry
store i32 47, i32* %a, align 4
br label %if.end

if.else: ; preds = %entry
store i32 1, i32* %a, align 4
br label %if.end

if.end: ; preds = %if.else, %if.then
%1 = load i32* %a, align 4
%add = add nsw i32 %1, 13
store i32 %add, i32* %b, align 4
%2 = load i32* %b, align 4
%add1 = add nsw i32 %2, 1
store i32 %add1, i32* %b, align 4
ret i32 0
}


而這裡就能看出一些端倪了，其實在判定的時候是有一個%cmp，以及載入%a給了一個臨時的%0，而最後給%b的是經過Resolution後的a，而這裡要看出來到底用了哪些寄存器，需要觀察彙編。

_main:
pushl %ebp
movl %esp, %ebp
subl $12, %esp
calll ___main
movl $0, -4(%ebp)
movl $47, -8(%ebp) # a
movl $0, -12(%ebp) # b
cmpl $47, -8(%ebp) # a compare 47
jle LBB0_2 # a &< 47 movl $47, -8(%ebp) # then branch: a = 47 jmp LBB0_3 # a &>= 47
LBB0_2:
movl $1, -8(%ebp) # a = 1
LBB0_3:
movl $0, %eax
movl -8(%ebp), %ecx # a -&> % ecx
addl $13, %ecx # %ecx + 13. i.e. a + 13
movl %ecx, -12(%ebp) # %ecx -&> b
movl -12(%ebp), %ecx # b -&> %ecx
addl $1, %ecx # %ecx + 1. i.e. b + 1
movl %ecx, -12(%ebp)
addl $12, %esp
popl %ebp
ret


這裡可以闡述RFX所說的寄存器分配辦法，以及經過Resolution後，退出舞台後的Phil，從而轉變為了具體move的彙編代碼是如何。

---

我也簡單補充下 @RednaxelaFX答案。
FX只說了Cytron原始論文中的resolution方法，即對所有的precedence blocks添加mov指令。不幸的是這個方法是錯的，主要有lost copy problem和swap problem沒考慮。如果有興趣了解，可以參考我寫的一個survey section 4.3: http://www.cse.ust.hk/~richardxx/papers/pqe.pdf。簡單介紹了這些問題以及正確的SSA resolution方法。

---

推薦閱讀：