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 位）时可以进行的简化。例如，如果已知操作数是小的整数，则保护子句中使用的关系运算符（例如 <）可以从 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 项，例如二进制、映射或不适合机器字的整数。
现在，让我们看看 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 会发出注释。）
现在只需要进行第一个测试，因为根据类型信息，如果该项是指向堆对象的指针，则**必须**是元组。
关系运算符的简化 #
作为另一个示例，让我们看一下如何转换保护子句中的关系运算符。考虑以下函数
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.
当关系运算符用作保护子句测试时，编译器会将它们重写为特殊指令。因此，< 运算符被重写为 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）。映射中元素的数量没有记录的上限，但是就可预见的未来而言，映射中元素的数量不会超过甚至接近 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 进行漂亮简化的潜力，但不幸的是，我们还将看到 Erlang 编译器在 OTP 25 中进行的类型分析的局限性。
让我们看一下为以下函数生成的代码
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
回到更简单的加法示例，不包含乘法，让我们添加一个守卫来确保 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 来测试一个项是否在给定范围内的整数。
同时，在我们等待 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 项。
# 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 的调用，其中位置参数是整数，而元组参数是字面元组。对于 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
拉取请求 #
以下是实现基于类型的优化的主要拉取请求：