Erlang JIT中基于类型的优化

Erlang 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()生成的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，因为它肯定是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项是否为指向堆上对象的指针。如果是，则测试堆对象的head word以确保它是一个元组。第二个测试是必要的，因为堆对象可能是其他一些 Erlang 项，例如binary、map或不适合机器字的整数。

现在让我们看看 OTP 25 中的编译器和 JIT 对这条指令做了什么。BEAM 代码现在是：

 {test,is_tuple,
          {f,3},
          [{tr,{y,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 通常会生成注释）

现在只需要第一个测试，因为如果Erlang项是指向堆对象的指针，根据类型信息，它必须是一个元组。

关系运算符的简化

再举一个例子，让我们看看守卫（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 生成代码来处理各种不同的erlang项是不切实际的。因此，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的小整数。如果整数不适合，它将表示为bignum，即指向堆上对象的指针。

这是用于测试两个操作数都很小的本地代码：

 mov eax, edi
    and eax, esi
    and al, 15
    cmp al, 15
    short jne L39

如果两个操作数中的一个或者全部有超过15的其他标记（不是小整数），则控制将转移到标签L39标明的处理所有其他erlang项的代码。

接下来的几行进行小整数的比较。代码以稍微复杂的方式编写，以便条件跳转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 有可能进行很好地简化，但不幸的是，我们也会看到 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 寄存器。如果一个或两个操作数不是小整数，则跳转到 label L15，如下所示：

L15:
    call 4328985696

此代码调用一个通用例程，该例程可以添加 small、bignum 或 float 的任意组合。通用例程还将通过引发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.

雪上加霜的是，JIT 无法简化前 6 条指令，因为没有足够的类型信息。也就是说，is_lt和is_ge指令将分别包含 11 条指令。

我们的目标是改进 OTP 26 中的类型分析和优化，并为此示例生成更好的代码。我们还在考虑在 OTP 26 中添加一个新的守护 BIF，以测试一个项是否为给定范围内的整数。

同时，当我们等待 OTP 26 时，OTP 25 中有一种方法可以编写等效的守卫，这将导致更高效的代码并为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的简化

据我们所知，OTP 25中的base64模块受益于其中的大部分改进。

以下是Github 问题中包含的基准的基准结果。首先是我电脑上 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 中，编码（encode）在 OTP 24 所需时间的 80% 内完成的。解码（decode）速度也快了一秒多。

而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
PrevNext

Related Posts

2021 年你需要知道的关于 Erlang 的一切

2021 年你需要知道的关于 Erlang 的一切

今天，我们将看一个相当古老且有些古怪的东西。 你们大多数人可能没有注意到的语言。 虽然 Erlang 不像某些现代编程语言那样流行，但它安静地运行着 WhatsApp 和微信等每天为大量用户提供服务的应用程序。 在这篇文章中，我将告诉你关于这门语言的更多事情、它的历史，以及你是否应该考虑自己学习它。 ## 什么是 Erlang，它在哪里使用？ Erl

Read More
Erlang JIT中基于类型的优化

Erlang JIT中基于类型的优化

这篇文章探讨了 Erlang/OTP 25 中基于类型的新优化，其中编译器将类型信息嵌入到 BEAM 文件中，以帮助JIT（即时编译器）生成更好的代码。 ## 两全其美 OTP 22 中引入的基于SSA的编译器处理步骤进行了复杂的类型分析，允许进行更多优化和更好的生成代码。然而，Erlang 编译器可以做什么样的优化是有限制的，因为 BEAM 文件必须

Read More
Erlang JIT之路

Erlang JIT之路

自从Erlang 存在，就一直有让它更快的需求和野心。这篇博文是一堂历史课，概述了主要的 Erlang 实现以及如何尝试提高 Erlang 的性能。 ## Prolog 解释器 Erlang 的第一个版本是在 1986 年在 Prolog 中实现的。那个版本的 Erlang 对于创建真正的应用程序来说太慢了，但它对于找出Erlang语言的哪些功能有用，哪

Read More