LLVM IR 未定義行為 (UB) 手冊¶
摘要¶
本文檔描述 LLVM IR 中的未定義行為 (UB)，包括未定義值和毒化值，以及 freeze 指令。我們還提供了關於何時使用每種形式 UB 的指南。
簡介¶
未定義行為 (UB) 用於指定我們不希望明確指定具體結果的邊緣情況的行為。UB 也用於為最佳化器提供額外的約束（例如，前端通過語言類型系統或運行時保證的假設）。例如，我們可以將除以零的結果指定為零，但由於我們實際上對結果不感興趣，因此我們說它是 UB。
LLVM 中存在兩種形式的未定義行為：立即性 UB 和延遲性 UB。後者有兩種變體：未定義值和毒化值。還有一個 freeze 指令來控制延遲性 UB 的傳播。LLVM 中的值格狀結構為：立即性 UB > 毒化值 > 未定義值 > freeze(毒化值) > 具體值。
我們將在下面詳細解釋每個概念。
立即性 UB¶
立即性 UB 是最嚴重的 UB 形式。應盡可能避免使用。立即性 UB 應僅用於在 LLVM 支援的大多數 CPU 中會導致陷阱的操作。範例包括除以零、取消引用空指標等。
應避免使用立即性 UB 的原因是它使諸如提升之類的最佳化變得更加困難。考慮以下範例
define i32 @f(i1 %c, i32 %v) {
br i1 %c, label %then, label %else
then:
%div = udiv i32 3, %v
br label %ret
else:
br label %ret
ret:
%r = phi i32 [ %div, %then ], [ 0, %else ]
ret i32 %r
}
我們可能會想通過刪除分支並推測性地執行除法來簡化此函數，因為大多數情況下 %c 為真。我們將獲得以下 IR
define i32 @f(i1 %c, i32 %v) {
%div = udiv i32 3, %v
%r = select i1 %c, i32 %div, i32 0
ret i32 %r
}
但是，此轉換是不正確的！由於當除數為零時，除法會觸發 UB，因此只有在確定我們不會遇到該條件時，我們才能推測性地執行。上面的函數在作為 f(false, 0) 調用時，在最佳化之前將返回 0，而在最佳化之後將觸發 UB。
此範例突顯了為什麼我們應盡可能減少觸發立即性 UB 的情況。作為經驗法則，僅對於在大多數支援架構的 CPU 上會導致陷阱的情況使用立即性 UB。
時間旅行¶
LLVM IR 中的立即性 UB 允許所謂的時間旅行。這意味著，如果程式觸發了 UB，那麼我們不需要保留其任何可觀察的行為，包括 I/O。例如，以下函數在調用 printf 後觸發 UB
define void @fn() {
call void @printf(...) willreturn
unreachable
}
由於我們知道 printf 始終會返回，並且由於 LLVM 的 UB 可以時間旅行，因此完全可以刪除對 printf 的調用，並將函數最佳化為簡單的
define void @fn() {
unreachable
}
延遲性 UB¶
延遲性 UB 是一種較輕形式的 UB。它使指令能夠推測性地執行，同時將某些邊緣情況標記為具有錯誤的值。延遲性 UB 應適用於常見 CPU 提供的語義不同的情況，但 CPU 不會陷阱。
例如，考慮移位指令。x86 和 ARM 架構在移位量等於或大於位寬時提供不同的語義。我們可以通過以下兩種方式之一解決此張力：1) 為 LLVM 選擇 x86/ARM 語義之一，這將使為另一個架構發出的代碼速度變慢；2) 將這種情況定義為產生 poison。LLVM 選擇了後一種選項。對於 C 或 C++ 等語言的前端（例如，clang），它們可以將原始程式碼中的移位直接映射到 LLVM IR 中的移位，因為 C 和 C++ 的語義將此類移位定義為 UB。對於提供強語義的語言，它們必須有條件地使用移位的值，例如
define i32 @x86_shift(i32 %a, i32 %b) {
%mask = and i32 %b, 31
%shift = shl i32 %a, %mask
ret i32 %shift
}
LLVM 中有兩個延遲性 UB 值：undef 和 poison，我們將在下面介紹。
未定義值¶
警告
未定義值已被棄用，應僅在絕對必要時使用。未定義值的使用應限制為表示未初始化記憶體的載入。這是 IR 語義中唯一尚未被替代方案取代的部分（正在進行中）。
未定義值表示給定類型的任何值。此外，每次使用依賴於未定義值的指令都可以觀察到不同的值。例如
define i32 @fn() {
%add = add i32 undef, 0
%ret = add i32 %add, %add
ret i32 %ret
}
毫不奇怪，第一個加法產生 undef。但是，第二個加法的結果更微妙。我們可能會認為它產生一個偶數。但它可能不是！由於每次（傳遞）使用 undef 都可以觀察到不同的值，因此第二個加法等效於 add i32 undef, undef，這等效於 undef。因此，上面的函數等效於
define i32 @fn() {
ret i32 undef
}
每次調用此函數都可能觀察到不同的值，即任何 32 位元數字（偶數和奇數）。
由於每次使用未定義值都可以觀察到不同的值，因此如果我們不確定某個值不是未定義值，則某些最佳化是錯誤的。考慮一個將數字乘以 2 的函數
define i32 @fn(i32 %v) {
%mul2 = mul i32 %v, 2
ret i32 %mul2
}
即使 %v 是未定義值，此函數也保證返回一個偶數。但是，正如我們在上面看到的，以下函數不會
define i32 @fn(i32 %v) {
%mul2 = add i32 %v, %v
ret i32 %mul2
}
僅僅因為未定義值的存在，即使它們沒有在此程式碼部分中使用，這種最佳化也是錯誤的，因為 LLVM 無法判斷 %v 是否為未定義值。
查看值格狀結構，未定義值只能用 freeze 指令或具體值替換。一個結果是，將未定義值作為操作數提供給對於該操作數的某些值會觸發 UB 的指令會使程式碼 UB。例如，udiv %x, undef 是 UB，因為我們將未定義值替換為 0 (udiv %x, 0)，這顯然是 UB。
毒化值¶
毒化值是比未定義值更強形式的延遲性 UB。它們仍然允許指令推測性地執行，但它們會污染整個表達式 DAG（除了一些例外），類似於浮點 NaN 值。
範例
define i32 @fn(i32 %a, i32 %b, i32 %c) {
%add = add nsw i32 %a, %b
%ret = add nsw i32 %add, %c
ret i32 %ret
}
加法中的 nsw 屬性表示如果存在有號溢位，則操作產生毒化值。如果第一個加法溢位，則 %add 是毒化值，因此 %ret 也是毒化值，因為它污染了整個表達式 DAG。
毒化值可以用任何類型的值替換（未定義值、具體值或 freeze 指令）。
毒化值透過 Select 的傳播¶
如果任何輸入是毒化值，則大多數指令都會返回毒化值。一個值得注意的例外是 select 指令，它僅當條件是毒化值或選定的值是毒化值時才是毒化值。這表示 select 充當毒化值傳播的屏障，這會影響可以執行的最佳化。
例如，考慮以下函數
define i1 @fn(i32 %x, i32 %y) {
%cmp1 = icmp ne i32 %x, 0
%cmp2 = icmp ugt i32 %x, %y
%and = select i1 %cmp1, i1 %cmp2, i1 false
ret i1 %and
}
將 select 最佳化為 and 是不正確的，因為當 %cmp1 為 false 時，僅當 %x 是毒化值時，select 才是毒化值，而下面的 and 如果 %x 或 %y 是毒化值，則為毒化值。
define i1 @fn(i32 %x, i32 %y) {
%cmp1 = icmp ne i32 %x, 0
%cmp2 = icmp ugt i32 %x, %y
%and = and i1 %cmp1, %cmp2 ;; poison if %x or %y are poison
ret i1 %and
}
但是，如果值的所有操作數都在條件中使用，則可以進行最佳化（請注意 select 中翻轉的操作數）
define i1 @fn(i32 %x, i32 %y) {
%cmp1 = icmp ne i32 %x, 0
%cmp2 = icmp ugt i32 %x, %y
%and = select i1 %cmp2, i1 %cmp1, i1 false
; ok to replace with:
%and = and i1 %cmp1, %cmp2
ret i1 %and
}
Freeze 指令¶
未定義值和毒化值有時會過度向下傳播表達式 DAG。未定義值是因為每次傳遞使用都可以觀察到不同的值，而毒化值是因為它們使整個 DAG 毒化。在某些情況下，停止這種傳播非常重要。這就是 freeze 指令的用途！
以下面的範例函數為例
define i32 @fn(i32 %n, i1 %c) {
entry:
br label %loop
loop:
%i = phi i32 [ 0, %entry ], [ %i2, %loop.end ]
%cond = icmp ule i32 %i, %n
br i1 %cond, label %loop.cont, label %exit
loop.cont:
br i1 %c, label %then, label %else
then:
...
br label %loop.end
else:
...
br label %loop.end
loop.end:
%i2 = add i32 %i, 1
br label %loop
exit:
...
}
想像一下，我們想要對上面的迴圈執行迴圈展開，因為迴圈內的 branch 條件是不變的。我們將獲得以下 IR
define i32 @fn(i32 %n, i1 %c) {
entry:
br i1 %c, label %then, label %else
then:
%i = phi i32 [ 0, %entry ], [ %i2, %then.cont ]
%cond = icmp ule i32 %i, %n
br i1 %cond, label %then.cont, label %exit
then.cont:
...
%i2 = add i32 %i, 1
br label %then
else:
%i3 = phi i32 [ 0, %entry ], [ %i4, %else.cont ]
%cond = icmp ule i32 %i3, %n
br i1 %cond, label %else.cont, label %exit
else.cont:
...
%i4 = add i32 %i3, 1
br label %else
exit:
...
}
有一個微妙的陷阱：當使用 %n 為零調用函數時，原始函數不會在 %c 上分支，而最佳化後的函數會。在延遲性 UB 值上分支是立即性 UB，因此一般來說轉換是錯誤的，因為 %c 可能是未定義值或毒化值。
像這種情況需要一種方法來控制延遲性 UB 值。這正是 freeze 指令的用途！當給定具體值作為參數時，freeze 是無操作，按原樣返回參數。當給定未定義值或毒化值時，freeze 返回該類型的非確定性值。這與未定義值不同：freeze 返回的值對於所有使用者都是相同的。
在 freeze 返回的值上分支始終是安全的，因為它要麼始終如一地評估為 true，要麼始終如一地評估為 false。我們可以使上面的迴圈展開最佳化正確，如下所示
define i32 @fn(i32 %n, i1 %c) {
entry:
%c2 = freeze i1 %c
br i1 %c2, label %then, label %else
編寫不含未定義行為的測試¶
在編寫測試時，確保它們不會不必要地觸發 UB 非常重要。一些自動化測試縮減有時會使用未定義值或毒化值作為虛擬值，但如果這導致觸發 UB，則認為這是不良做法。
例如，假設我們想要編寫一個測試，並且我們不關心特定的除數值，因為我們的最佳化會無差別地啟動
define i32 @fn(i8 %a) {
%div = udiv i8 %a, poison
...
}
此測試的問題在於它會觸發立即性 UB。這阻止了 Alive 等驗證工具驗證最佳化的正確性。因此，擁有不必要的立即性 UB 的測試被認為是不良做法（除非這正是測試的目的）。上面的測試應使用虛擬函數參數而不是使用毒化值
define i32 @fn(i8 %a, i8 %dummy) {
%div = udiv i8 %a, %dummy
...
}
測試中立即性 UB 的常見來源包括在未定義值/毒化值條件上分支以及取消引用未定義值/毒化值/空指標。
注意
如果您需要一個佔位符值作為可能觸發 UB 的指令的參數傳遞，請向函數添加一個新參數，而不是使用未定義值或毒化值。
總結¶
LLVM IR 中的未定義行為 (UB) 由兩個明確定義的概念組成：立即性和延遲性 UB（未定義值和毒化值）。將延遲性 UB 值傳遞給某些操作會導致立即性 UB。在某些情況下，可以通過使用 freeze 指令來避免這種情況。
LLVM 中的值格狀結構為：立即性 UB > 毒化值 > 未定義值 > freeze(毒化值) > 具體值。僅將值從左向右轉換是有效的（例如，毒化值可以用具體值替換，但反之則不然）。
未定義值現在已被棄用，應僅用於表示未初始化記憶體的載入。