JIT 中的類型導向優化
這篇文章探討了 Erlang/OTP 25 中新的類型導向優化，其中編譯器將類型資訊嵌入 BEAM 檔案中，以協助 JIT (即時編譯器) 產生更好的程式碼。
兩全其美 #
在 OTP 22 中引入的 基於 SSA 的編譯器傳遞執行了複雜的類型分析，這允許更多的優化和更好的程式碼生成。然而，Erlang 編譯器可以進行的優化類型有限制，因為 BEAM 檔案必須能夠在任何運行於 32 位元或 64 位元電腦上的 BEAM 機器上載入。因此，編譯器不能進行依賴於機器字中整數大小或 Erlang 項表示方式的優化。
JIT（在 OTP 24 中引入）知道它正在 64 位元電腦上運行，並且知道 Erlang 項的表示方式。JIT 在它可以進行的優化程度上仍然受到限制，因為它一次翻譯單個 BEAM 指令。例如，+ 運算子可以將浮點數或任何大小的整數或其任意組合相加。先前執行的 BEAM 指令可能已明確指出運算元只能是小整數，但 JIT 並不知道這一點，因為它一次只查看一個指令，因此它必須發出處理所有可能運算元的原生程式碼。
在 OTP 25 中，編譯器已更新為將類型資訊嵌入 BEAM 檔案中，並且 JIT 已擴展為根據該類型資訊發出更好的程式碼。
嵌入的類型資訊已版本化，以便我們可以在每個 OTP 版本中繼續改進基於類型的優化。載入器將忽略它不識別的版本，以便模組仍然可以在沒有基於類型的優化的情況下載入。
對 OTP 25 中 JIT 的期望 #
OTP 25 僅是類型導向優化的開始。我們希望在 OTP 26 中改進編譯器的類型資訊和 JIT 中的優化。
JIT 發出的原生程式碼好多少取決於模組中程式碼的性質。
最常應用的優化是簡化的測試。例如，對元組的測試通常可以從 5 個指令減少到 3 個指令，而對小整數運算元的測試通常可以從 5 個指令減少到 4 個指令。
較少應用但更重要的是，當已知整數為「小」（適合 60 位元）時可以進行簡化。例如，如果已知運算元是小整數，則 guard 中使用的關係運算子（例如 <）可以從 11 個指令減少到 4 個指令。這種優化最常應用於使用二進制模式匹配的模組中，因為從二進制中匹配出的整數具有明確定義的範圍。
在 Erlang/OTP 程式碼庫中，第一種優化（減少一兩個指令）的應用頻率大約是第二種的十倍。
我們將在本部落格文章的稍後部分看到，第二種優化應用於 base64 模組時產生了顯著的速度提升。
類型測試的簡化 #
讓我們直接深入探討一些範例。
考慮這個模組
-module(example).
-export([tuple_matching/1]).
tuple_matching(X) ->
case increment(X) of
{ok,Result} -> Result;
error -> X
end.
increment(X) when is_integer(X) -> {ok,X+1};
increment(_) -> error.
OTP 24 中編譯器發出的 tuple_matching/1 函數的 BEAM 程式碼是（經過一些簡化）
{allocate,1,1}.
{move,{x,0},{y,0}}.
{call,1,{f,5}}.
{test,is_tuple,{f,3},[{x,0}]}.
{get_tuple_element,{x,0},1,{x,0}}.
{deallocate,1}.
return.
{label,3}.
{move,{y,0},{x,0}}.
{deallocate,1}.
return.
編譯器已發現 increment/1 會回傳原子 error 或第一個元素為 ok 的二元組。因此，為了區分這兩個可能的回傳值，一個指令就足夠了
{test,is_tuple,{f,3},[{x,0}]}.
沒有必要明確測試值 error，因為如果它不是元組，則**必須**是 error。同樣，沒有必要測試元組的第一個元素是否為 ok，因為它必須是。
在 OTP 24 中，JIT 將該指令轉換為 x86_64 的 5 個原生指令序列
# i_is_tuple_fs
mov rsi, qword ptr [rbx]
rex test sil, 1
jne L2
test byte ptr [rsi-2], 63
jne L2
（以 # 開頭的行是註解。）
mov 指令將 BEAM 暫存器 {x,0} 的值提取到 CPU 暫存器 rsi。接下來的兩個指令測試該項是否是指向堆上物件的指標。如果是，則會測試堆物件的標頭字，以確保它是元組。需要第二個測試，因為堆物件可能是其他 Erlang 項，例如二進制、map 或不適合機器字的整數。
現在讓我們看看 OTP 25 中的編譯器和 JIT 如何處理這個指令。BEAM 程式碼現在是
{test,is_tuple,
{f,3},
[{tr,{x,0},
{t_union,{t_atom,[error]},
none,none,
[{{2,{t_atom,[ok]}},
{t_tuple,2,true,
#{1 => {t_atom,[ok]},
2 => {t_integer,any}}}}],
none}}]}.
在 OTP 24 中為 {x,0} 的運算元現在是一個元組
{tr,Register,Type}
也就是說，它是一個三元組，其中 tr 為第一個元素。tr 代表**類型化暫存器**。第二個元素是 BEAM 暫存器（在本例中為 {x,0}），第三個元素是編譯器內部類型表示中暫存器的類型。此類型等效於以下類型規範
'error' | {'ok', integer()}
JIT 無法利用這些類型中的詳細程度，因此編譯器將該類型的 簡化版本 嵌入到 BEAM 檔案中。嵌入的類型等效於
atom() | tuple()
通過了解 {x,0} 必須是原子或元組，OTP 25 中的 JIT 會發出以下簡化的原生程式碼
# i_is_tuple_fs
mov rsi, qword ptr [rbx]
# simplified tuple test since the source is always a tuple when boxed
rex test sil, 1
jne label_3
（當類型資訊使簡化成為可能時，JIT 通常會發出註解。）
現在只需要第一個測試，因為根據類型資訊，如果該項是指向堆物件的指標，則它**必須**是元組。
關係運算子的簡化 #
作為另一個範例，讓我們看看 guard 中的關係運算子是如何轉換的。考慮這個函數
my_less_than(A, B) ->
if
A < B -> smaller;
true -> larger_or_equal
end.
BEAM 程式碼如下所示
{test,is_lt,{f,9},[{x,0},{x,1}]}.
{move,{atom,smaller},{x,0}}.
return.
{label,9}.
{move,{atom,larger_or_equal},{x,0}}.
return.
當關係運算子用作 guard 測試時，編譯器會將它們重寫為特殊指令。因此，< 運算子會被重寫為 is_lt 指令。
< 運算子可以比較任何 Erlang 項。JIT 發出處理所有類型項的程式碼是不切實際的。因此，JIT 發出直接處理最常見情況的程式碼，並呼叫通用常式來處理其他所有情況
# is_lt_fss
mov rsi, qword ptr [rbx+8]
mov rdi, qword ptr [rbx]
mov eax, edi
and eax, esi
and al, 15
cmp al, 15
short jne L39
cmp rdi, rsi
short jmp L40
L39:
call 5447639136
L40:
jge label_9
讓我們逐步了解一下程式碼。前兩個指令
mov rsi, qword ptr [rbx+8]
mov rdi, qword ptr [rbx]
將 BEAM 暫存器 {x,1} 和 {x,0} 提取到 CPU 暫存器中。
最常見的比較是在兩個整數之間。根據大小，整數可以用兩種不同的方式表示。在 64 位元電腦上，適合 60 位元的帶符號整數將直接儲存在 64 位元字中。字中的其餘 4 位元用於 標記，對於小整數，標記為 15。如果整數不適合，它將表示為**大數**，它是指向堆上物件的指標。
以下是測試兩個運算元是否為小數的原生程式碼
mov eax, edi
and eax, esi
and al, 15
cmp al, 15
short jne L39
如果一個或兩個運算元具有其他標記而非 15（不是小整數），則控制權會轉移到標籤 L39 處的程式碼，該程式碼會處理所有其他類型的項。
接下來的幾行程式碼會比較小整數。程式碼以稍微迂迴的方式編寫，以便將控制權轉移到失敗標籤的條件跳轉 (jge label_9) 可以與通用程式碼共用
cmp rdi, rsi
short jmp L40
L39:
call 5447639136
L40:
jge label_9
因此，在沒有類型資訊的情況下，需要 11 個指令來實作 is_lt。
現在讓我們看看當類型可用時會發生什麼
my_less_than(A, B) when is_integer(A), is_integer(B) ->
.
.
.
當由 OTP 25 中的編譯器編譯時，BEAM 程式碼為
{test,is_integer,{f,7},[{x,0}]}.
{test,is_integer,{f,7},[{x,1}]}.
{test,is_lt,{f,9},[{tr,{x,0},{t_integer,any}},{tr,{x,1},{t_integer,any}}]}.
{move,{atom,smaller},{x,0}}.
return.
{label,9}.
{move,{atom,larger_or_equal},{x,0}}.
return.
現在 is_lt 指令的運算元具有類型。BEAM 暫存器 {x,0} 和 {x,1} 的類型為 {t_integer,any}，這表示具有未知範圍的整數。
了解了這些類型，JIT 可以為小整數發出稍微短一點的測試
# simplified small test since all other types are boxed
mov eax, edi
and eax, esi
test al, 1
short je L39
為了做得更好，JIT 需要更好的類型資訊。例如
map_size_less_than(Map1, Map2) ->
if
map_size(Map1) < map_size(Map2) -> smaller;
true -> larger_or_equal
end.
BEAM 程式碼如下所示
{gc_bif,map_size,{f,12},2,[{x,0}],{x,0}}.
{gc_bif,map_size,{f,12},2,[{x,1}],{x,1}}.
{test,is_lt,
{f,12},
[{tr,{x,0},{t_integer,{0,288230376151711743}}},
{tr,{x,1},{t_integer,{0,288230376151711743}}}]}.
{move,{atom,smaller},{x,0}}.
return.
{label,12}.
{move,{atom,larger_or_equal},{x,0}}.
return.
is_lt 的兩個運算元的類型現在都為 {t_integer,{0,288230376151711743}}，表示範圍在 0 到 288230376151711743 的整數（也就是說，(1 bsl 58) - 1）。map 中元素數的數量沒有明確的文件上限，但在可預見的未來，map 中元素的數量不會超過甚至接近 288230376151711743。
由於 {x,0} 和 {x,1} 的下限和上限都適合 60 位元，因此沒有必要測試運算元的類型
# is_lt_fss
mov rsi, qword ptr [rbx+8]
mov rdi, qword ptr [rbx]
# skipped test for small operands since they are always small
cmp rdi, rsi
L42:
L43:
jge label_12
由於運算元始終很小，因此已省略了對通用常式的呼叫（在標籤 L42 之後）。
加法的簡化 #
查看算術指令，我們將看到 JIT 進行良好簡化的潛力，但不幸的是，我們也會看到 OTP 25 中 Erlang 編譯器所做類型分析的限制。
讓我們看看為此函數產生的程式碼
add1(X, Y) ->
X + Y.
BEAM 程式碼如下所示
{gc_bif,'+',{f,0},2,[{x,0},{x,1}],{x,0}}.
return.
JIT 將 + 指令轉換為以下原生指令
# i_plus_ssjd
mov rsi, qword ptr [rbx]
mov rdx, qword ptr [rbx+8]
# are both operands small?
mov eax, esi
and eax, edx
and al, 15
cmp al, 15
short jne L15
# add with overflow check
mov rax, rsi
mov rcx, rdx
and rcx, -16
add rax, rcx
short jno L14
L15:
call 4328985696
L14:
mov qword ptr [rbx], rax
前兩個指令
mov rsi, qword ptr [rbx]
mov rdx, qword ptr [rbx+8]
將 + 運算 BEAM 暫存器的運算元載入到 CPU 暫存器中。
接下來的 5 個指令測試小運算元
# are both operands small?
mov eax, esi
and eax, edx
and al, 15
cmp al, 15
short jne L15
程式碼幾乎與我們先前檢查的 is_lt 指令中的程式碼相同。唯一的區別是使用了其他 CPU 暫存器。如果一個或兩個運算元不是小整數，則會跳到標籤 L15，如下所示
L15:
call 4328985696
此程式碼會呼叫通用常式，該常式可以加上小數、大數或浮點數的任意組合。通用常式還會處理非數字運算元，方法是引發 badarith 例外。
如果兩個運算元確實是小數，則以下程式碼會將它們相加並檢查是否溢位
# add with overflow check
mov rax, rsi
mov rcx, rdx
and rcx, -16
add rax, rcx
short jno L14
如果加法溢位，則會呼叫通用加法常式。否則，控制權會轉移到以下指令
mov qword ptr [rbx], rax
將結果儲存在 {x,0} 中。
總而言之，加法本身（包括處理 標記）需要 4 個指令。但是，還需要另外 10 個指令才能
- 從 BEAM 暫存器提取運算元。
- 檢查運算元是否為小整數（最多 60 位元）。
- 呼叫通用加法常式。
- 將結果儲存到 BEAM 暫存器。
現在讓我們看看如果引入類型會發生什麼。
考慮
add2(X0, Y0) ->
X = 2 * X0,
Y = 2 * Y0,
X + Y.
BEAM 程式碼如下所示
{gc_bif,'*',{f,0},2,[{x,0},{integer,2}],{x,0}}.
{gc_bif,'*',{f,0},2,[{x,1},{integer,2}],{x,1}}.
{gc_bif,'+',{f,0},2,[{tr,{x,0},number},{tr,{x,1},number}],{x,0}}.
return.
類型從算術指令傳播到其他算術指令。由於 * 的結果（如果成功）是一個數字（整數或浮點數），因此 + 指令的運算元現在具有 number 類型。
根據我們向 < 運算子新增類型的經驗，我們可能會猜到我們只會在類型測試中節省一個指令。我們會是對的
# simplified test for small operands since both are numbers
mov eax, esi
and eax, edx
test al, 1
short je L22
回到加法且沒有乘法的簡單範例，讓我們新增一個 guard 以確保 X 和 Y 是整數
add3(X, Y) when is_integer(X), is_integer(Y) ->
X + Y.
這會產生以下 BEAM 程式碼
{test,is_integer,{f,5},[{x,0}]}.
{test,is_integer,{f,5},[{x,1}]}.
{gc_bif,'+',
{f,0},
2,
[{tr,{x,0},{t_integer,any}},{tr,{x,1},{t_integer,any}}],
{x,0}}.
return.
兩個運算元的類型現在都是 {t_integer,any}。但是，這仍然會產生相同的簡化四指令序列來測試小整數，因為整數可能不適合 60 位元。
顯然，根據我們使用 is_lt 的經驗，我們需要為 X 和 Y 建立一個範圍。一個合理的方法是
add4(X, Y) when is_integer(X), 0 =< X, X < 16#400,
is_integer(Y), 0 =< Y, Y < 16#400 ->
X + Y.
然而，由於編譯器的數值範圍分析存在限制，+ 運算子的類型將不會改善
{test,is_integer,{f,19},[{x,0}]}.
{test,is_ge,{f,19},[{tr,{x,0},{t_integer,any}},{integer,0}]}.
{test,is_lt,{f,19},[{tr,{x,0},{t_integer,any}},{integer,1024}]}.
{test,is_integer,{f,19},[{x,1}]}.
{test,is_ge,{f,19},[{tr,{x,1},{t_integer,any}},{integer,0}]}.
{test,is_lt,{f,19},[{tr,{x,1},{t_integer,any}},{integer,1024}]}.
{gc_bif,'+',
{f,0},
2,
[{tr,{x,0},{t_integer,any}},{tr,{x,1},{t_integer,any}}],
{x,0}}.
return.
更糟的是，前 6 個指令無法被 JIT 簡化，因為沒有足夠的類型資訊。也就是說，is_lt 和 is_ge 指令將各自包含 11 個指令。
我們的目標是在 OTP 26 中改進類型分析和最佳化，並為此範例產生更好的程式碼。我們也考慮在 OTP 26 中新增一個新的 guard BIF，用於測試一個 term 是否在給定的整數範圍內。
同時，在我們等待 OTP 26 的同時，在 OTP 25 中有一種方法可以編寫一個等效的 guard，它將產生更有效率的程式碼，並且為 X 和 Y 建立已知的範圍
add5(X, Y) when X =:= X band 16#3FF,
Y =:= Y band 16#3FF ->
X + Y.
我們展示這種編寫 guard 的方式僅供說明之用；我們不建議以這種方式重寫你的 guard。
如果 band 運算子的兩個運算元都不是整數，則會失敗，因此不需要 is_integer/1 測試。如果相應的變數超出 0 到 16#3FF 的範圍，=:= 比較將返回 false。
這將產生以下 BEAM 程式碼，其中編譯器現在已經能夠找出 + 運算子的運算元的可能範圍
{gc_bif,'band',{f,21},2,[{x,0},{integer,1023}],{x,2}}.
{test,is_eq_exact,
{f,21},
[{tr,{x,0},{t_integer,any}},{tr,{x,2},{t_integer,{0,1023}}}]}.
{gc_bif,'band',{f,21},2,[{x,1},{integer,1023}],{x,2}}.
{test,is_eq_exact,
{f,21},
[{tr,{x,1},{t_integer,any}},{tr,{x,2},{t_integer,{0,1023}}}]}.
{gc_bif,'+',
{f,0},
2,
[{tr,{x,0},{t_integer,{0,1023}}},{tr,{x,1},{t_integer,{0,1023}}}],
{x,0}}.
return.
此外，+ 指令之前的 4 個指令現在相對有效率。
band 指令需要測試運算元，並準備處理不適合 60 位元的整數
# i_band_ssjd
mov rsi, qword ptr [rbx]
mov eax, 16383
# is the operand small?
mov edi, esi
and edi, 15
cmp edi, 15
short jne L97
and rax, rsi
short jmp L98
L97:
call 4456532680
short je label_25
L98:
mov qword ptr [rbx+16], rax
is_eq_exact 指令受益於執行 band 指令得出的類型資訊。由於已知右側運算元是一個適合機器字的短整數，因此只需進行簡單的比較，而無需使用回退程式碼來處理其他 Erlang term
# is_eq_exact_fss
# simplified check since one argument is an immediate
mov rdi, qword ptr [rbx+16]
cmp qword ptr [rbx], rdi
short jne label_25
JIT 為 + 運算子產生以下程式碼
# i_plus_ssjd
# add without overflow check
mov rax, qword ptr [rbx]
mov rsi, qword ptr [rbx+8]
and rax, -16
add rax, rsi
mov qword ptr [rbx], rax
base64 的簡化 #
據我們所知，base64 是 OTP 中從 OTP 25 的改進中受益最多的模組。
以下是在 Github issue 中包含的基準測試結果。首先是在我的電腦上 OTP 24 的結果
== Testing with 1 MB ==
fun base64:encode/1: 1000 iterations in 19805 ms: 50 it/sec
fun base64:decode/1: 1000 iterations in 20075 ms: 49 it/sec
在同一台電腦上 OTP 25 的結果
== Testing with 1 MB ==
fun base64:encode/1: 1000 iterations in 16024 ms: 62 it/sec
fun base64:decode/1: 1000 iterations in 18306 ms: 54 it/sec
在 OTP 25 中，編碼所花費的時間是 OTP 24 所需時間的 80%。解碼速度也快了一秒以上。
base64 模組在 OTP 25 中沒有修改，因此這些改進完全歸功於編譯器和 JIT 的改進。
這是 base64 模組中 encode_binary/2 的子句，它完成了將二進位編碼為 Base64 的大部分工作
encode_binary(<<B1:8, B2:8, B3:8, Ls/bits>>, A) ->
BB = (B1 bsl 16) bor (B2 bsl 8) bor B3,
encode_binary(Ls,
<<A/bits,(b64e(BB bsr 18)):8,
(b64e((BB bsr 12) band 63)):8,
(b64e((BB bsr 6) band 63)):8,
(b64e(BB band 63)):8>>).
函數頭中的二進位匹配為變數 B1、B2 和 B3 建立了範圍。（所有三個變數的類型都將是 {t_integer,{0,255}}。）
由於這些範圍，接下來的所有 bsl、bsr、band 和 bor 運算都不需要任何類型檢查。此外，在建立二進位時，由於已知所有值都是短整數，因此無需測試二進位建立是否成功。
對 b64e/1 函數的 4 個呼叫已內聯。該函數如下所示
-compile({inline, [{b64e, 1}]}).
b64e(X) ->
element(X+1,
{$A, $B, $C, $D, $E, $F, $G, $H, $I, $J, $K, $L, $M, $N,
$O, $P, $Q, $R, $S, $T, $U, $V, $W, $X, $Y, $Z,
$a, $b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n,
$o, $p, $q, $r, $s, $t, $u, $v, $w, $x, $y, $z,
$0, $1, $2, $3, $4, $5, $6, $7, $8, $9, $+, $/}).
在 OTP 25 中，JIT 將最佳化對 element/2 的呼叫，其中位置引數是一個整數，而 tuple 引數是一個字面 tuple。對於 element/2 在 be64e/1 中的使用方式，所有類型測試和範圍檢查都將被移除
# bif_element_jssd
# skipped tuple test since source is always a literal tuple
L302:
long mov rsi, 9223372036854775807
mov rdi, qword ptr [rbx+24]
lea rcx, qword ptr [rsi-2]
# skipped test for small position since it is always small
mov rax, rdi
sar rax, 4
# skipped check for position =:= 0 since it is always >= 1
# skipped check for negative position and position beyond tuple
mov rax, qword ptr [rcx+rax*8]
L300:
L301:
mov qword ptr [rbx+24], rax
這是有 7 個指令，沒有條件分支。
請在家嘗試！ #
如果你想跟著操作並檢查已載入模組的機器碼，請像這樣啟動執行階段系統
erl +JDdump true
所有已載入模組的機器碼都將轉儲到副檔名為 .asm 的檔案中。
要找到已被 JIT 簡化的程式碼，請使用此命令
egrep "simplified|skipped|without overflow" *.asm
要檢查模組的 BEAM 程式碼，請使用 -S 選項。例如
erlc -S base64.erl
提取請求 #
以下是實作基於類型的最佳化的主要提取請求