llvm的reg2mem pass做了哪些事情？

我查到用這個pass可以消除phi指令（llvm - turn off clang optimization, remove phi instruction），但是從pass的名字來看毫無關係啊？而且生成的ir中還會多出

%"reg2mem alloca point" = bitcast i32 0 to i32 這樣奇怪的指令是為什麼？

用來測試的ll文件：https://gist.github.com/cgcgbcbc/8130f30aa25bd1ef80648ced6597a3c0

命令 opt -reg2mem -S

從代碼（LLVM: Reg2Mem.cpp Source File）上看除了和phi指令相關的，還有找到escaped instructions並demote，這裡的escaped instructions是什麼意思呢？

---

有關係，若你能知道還有一種IR是基於Stack的你就應該能明白。在Stack Machine Code中是沒有Phi的概念的，這個概念是存在於SSA中的，Phi主要解決的問題就是控制流的問題，如：

if(b)
x = 1;
else
x = 2;
y = x;


SSA:

if(b)
x1 = 1;
else
x2 = 1;
y = phi(x1, x2);


然而，在實際執行代碼中，其實phi是不存在的，目前的傳統指令集並沒有phi，所以在LLVM Backend中會有SSA destruction，然後就有phi的消除。

而要轉為所謂可實際執行的代碼，即SSA的轉換，一個最重要的就是phi的消除。

那麼，對於消除phi，一種是赤裸裸的phi. 如:

bb0:
a0 = 1
-&> bb1
bb1:
a1 = phi(a0, a3)
...
-&> bb2
bb2:
a3 = 1
...
-&> bb1


比如 我要消除bb1的 a1 的phi，那麼就是在bb1的前驅節點與後驅節點插入賦值與替換，其規則是對於xi = phi(xj, xk), 沿傳入xj的邊插入xi = xj, 沿xk的邊插入xi = xk。所以對於上文的bb1，我們要替換的話，我們就需要變為：

bb0:
a0 = 1
a1 = a0
-&>bb1
bb1:
...
-&> bb2
bb2:
a3 = 1
...
a1 = a3
-&> bb1

這樣就消除了phi，並且保持了基本不動，這一個就是DemotePHIToStack函數做的事 LLVM: Reg2Mem.cpp Source File

然後讓我們把問題變得複雜一點

bb0:
a0 = 1
-&> bb1
bb1:
a1 = phi(a0, a3)
...
-&> bb2
bb2:
b2 = 1
c3 = ...
d2 = ...
...
-&> bb3
bb3:
a3 = phi(a2, a4)
...
y = a3 + 1
i = a0 + 1
(i &< 100) -&> bb1, bb4
bb4:
return


這裡，我們注意bb1中的phi的a3在bb3，並且bb3末尾有了多個出路，即bb1, bb4. 若我們消除bb1的phi，我們依然可以在它的前驅點bb0做，但是我們不能在後驅結點bb3做，因為在bb3的terminator處（對應LLVM的TerminalInst與Terminator）引入代碼，則會導致bb3到bb4的執行。所以，為了解決這個問題，我們可以把bb3-&>bb1的邊進行拆分，引入一條新的邊，如bb5.

bb0:
a0 = 1
a1 = a0
-&> bb1
bb1:
...
-&> bb2
bb2:
b2 = 1
c3 = ...
d2 = ...
...
-&> bb3
bb3:
a3 = phi(a2, a4) // keep the same for simplify explain
...
y = a3 + 1
i = a0 + 1
(i &< 100) -&> bb5, bb4
bb4:
return
bb5:
a1 = a3
-&> bb1


這樣就可以解決，而在編譯原理中，我們把bb3-&>bb1的邊稱為關鍵邊，在LLVM中，DemoteRegToStack 就會來具體處理這樣的事情，然而在交給DemoteRegToStack前，從LLVM: Reg2Mem.cpp Source File 89行開始就是要來識別這樣的情況，尤其可關注Reg2Mem.cpp的valueEscaped函數（這裡我的bb3的phi並沒有消除，因為與我想闡述解決的問題無關，所以，我也並沒有留下a2, a4的定義）。

然而現實中的phi和指令是很複雜的，即使這樣處理，依然還有兩個問題

1. 丟失複製－－不應拆或者無法拆關鍵邊

2. 交換問題－－phi在任何其他語句之行之前並發執行，若使用樸素替換，在某些情況下的交換值可能會有問題。

這兩個問題我就不闡述了，因為大體原理是上面說的，所以總的來說，LLVM這個就是編譯原理理論的具體實現，並不特別。

最後再說說你說的這個指令：

%"reg2mem alloca point" = bitcast i32 0 to i32 這樣奇怪的指令是為什麼

參考LLVM: Reg2Mem.cpp Source File

---

@藍色 大大的回答在點子上了。俺懶得再碼字，放個有我的和藍色大大的老回答的傳送門吧：Phi node 是如何實現它的功能的？ - 編譯器

---

推薦閱讀：