暑假过后，本博客将改变方向，开始一系列关于静态单赋值（SSA）的博客文章。第一篇文章将为后续文章奠定基础，探讨在尝试优化 BEAM 汇编代码时可能陷入的陷阱和误区。

BEAM 汇编语言简介 #

我们将研究以下函数的 BEAM 代码

foo({tag,A,_,_}) ->
    {ok,A}.

（未优化的）BEAM 代码如下所示

{function, foo, 1, 2}.
  {label,1}.
    {line,[{location,"ex1.erl",4}]}.
    {func_info,{atom,ex1},{atom,foo},1}.
  {label,2}.
    {test,is_tuple,{f,3},[{x,0}]}.
    {test,test_arity,{f,3},[{x,0},4]}.
    {get_tuple_element,{x,0},0,{x,1}}.
    {get_tuple_element,{x,0},1,{x,2}}.
    {test,is_eq_exact,{f,3},[{x,1},{atom,tag}]}.
    {test_heap,3,3}.
    {put_tuple,2,{x,0}}.
    {put,{atom,ok}}.
    {put,{x,2}}.
    return.
  {label,3}.
    {test_heap,2,1}.
    {put_list,{x,0},nil,{x,1}}.
    {move,{atom,function_clause},{x,0}}.
    {line,[{location,"ex1.erl",4}]}.
    {call_ext_only,2,{extfunc,erlang,error,2}}.

我们将专注于执行实际工作的代码部分

    {test,is_tuple,{f,3},[{x,0}]}.
    {test,test_arity,{f,3},[{x,0},4]}.
    {get_tuple_element,{x,0},0,{x,1}}.
    {get_tuple_element,{x,0},1,{x,2}}.
    {test,is_eq_exact,{f,3},[{x,1},{atom,tag}]}.
    {test_heap,3,3}.
    {put_tuple,2,{x,0}}.
    {put,{atom,ok}}.
    {put,{x,2}}.
    return.
  {label,3}.
    %% Cause a function_clause exception.

现在我们将解释每个指令的作用。

    {test,is_tuple,{f,3},[{x,0}]}.

test 指令测试条件是否为真。如果为真，将执行下一条指令。否则，将跳转到失败标签。

此指令测试的条件是 is_tuple，即其操作数是否为元组。操作数是 {x,0}，它是该函数的第一个参数的寄存器。如果 {x,0} 不包含元组，则执行将继续在失败标签处。{f,3} 表示失败标签为 3。标签 3 处的代码将导致 function_clause 异常。

    {test,test_arity,{f,3},[{x,0},4]}.

test_arity 指令测试第一个操作数（必须是元组）的大小是否与第二个操作数给定的值相同。第一个操作数是 {x,0}，第二个操作数是 4。失败标签与前一个指令的相同。

    {get_tuple_element,{x,0},0,{x,1}}.
    {get_tuple_element,{x,0},1,{x,2}}.

当执行这两个指令时，之前的指令已确定 {x,0} 包含一个大小为 4 的元组。get_tuple_element 接收三个操作数。第一个是源元组 {x,0}，第二个是元组的 从零开始的 索引，第三个操作数是应在其中存储来自元组的元素的寄存器。请注意，没有失败标签，因为它不会失败。

因此，第一个 get_tuple_element 指令获取元组的第一个元素并将其存储在 {x,1} 寄存器中，第二个 get_tuple_element 指令获取第二个元素并将其存储在 {x,2} 寄存器中。

    {test,is_eq_exact,{f,3},[{x,1},{atom,tag}]}.

is_eq_exact 再次是一个 test 指令。它测试 {x,1} 的内容是否与原子 tag 完全相等（即，=:=）。如果不是，则执行将继续在失败标签 3 处。

函数头部分到此结束。下一个指令位于函数体中，它将构建 {ok,A} 元组

    {test_heap,3,3}.

test_heap 指令确保堆上有足够的可用空间来构造一个项。第一个操作数（第一个 3）表示以下指令需要在堆上占用 3 个字。元组有一个头字，后跟元素，因此包含 2 个元素的元组总共需要 3 个堆字。

如果堆上没有足够的空间，test_heap 指令将执行垃圾回收以找到一些新的堆空间。第二个操作数（第二个 3）是在垃圾回收期间必须保留其值的 x 寄存器的数量。3 表示 {x,0}、{x,1} 和 {x,2} 具有活动值。

    {put_tuple,2,{x,0}}.
    {put,{atom,ok}}.
    {put,{x,2}}.

这三个指令构建了元组，将指向元组的标记指针放入 {x,0} 中。

    return.

return 从函数返回。返回值是 {x,0} 中的值。

优化这段代码 #

测试一个项是否为具有特定原子作为第一个元素的特定大小的元组是一种常见操作（想想记录）。因此，BEAM 机器有一个 is_tagged_tuple 指令，它完成其他 4 个指令的工作。

使用该指令，此代码

    {test,is_tuple,{f,3},[{x,0}]}.
    {test,test_arity,{f,3},[{x,0},4]}.
    {get_tuple_element,{x,0},0,{x,1}}.
    {get_tuple_element,{x,0},1,{x,2}}.
    {test,is_eq_exact,{f,3},[{x,1},{atom,tag}]}.
    {test_heap,3,3}.
    {put_tuple,2,{x,0}}.
    {put,{atom,ok}}.
    {put,{x,2}}.
    return.

可以像这样重写

    {test,is_tagged_tuple,{f,1},[{x,0},4,{atom,tag}]}.
    {get_tuple_element,{x,0},1,{x,2}}.
    {test_heap,3,3}.
    {put_tuple,2,{x,0}}.
    {put,{atom,ok}}.
    {put,{x,2}}.
    return.

这在代码大小和执行时间方面都有很好的减少。但是，此优化并不安全。

为什么？

考虑 {test_heap,3,3} 指令。第二个 3 表示有 3 个 x 寄存器处于活动状态，即 {x,0}、{x,1} 和 {x,2}。显然，{x,0} 和 {x,2} 处于活动状态，但 {x,1} 呢？我们删除了为 {x,1} 分配值的 get_tuple_element 指令，因此 {x,1} 的值是未定义的。

将未定义的寄存器值传递给垃圾回收器是一种可能需要数周才能跟踪到的错误。事实上，未来可能会有一篇博客文章介绍这种错误以及作为该错误的结果而诞生的两个工具。

不情愿地，为了使优化安全，我们必须保留分配给 {x,1} 的 get_tuple_element 指令

    {test,is_tagged_tuple,{f,1},[{x,0},4,{atom,tag}]}.
    {get_tuple_element,{x,0},0,{x,1}}.
    {get_tuple_element,{x,0},1,{x,2}}.
    {test_heap,3,3}.
    {put_tuple,2,{x,0}}.
    {put,{atom,ok}}.
    {put,{x,2}}.
    return.

在这种情况下，另一种可能性是将空列表（在 BEAM 汇编语言中称为 nil）分配给 {x,1}

    {test,is_tagged_tuple,{f,1},[{x,0},4,{atom,tag}]}.
    {move,nil,{x,1}}.
    {get_tuple_element,{x,0},1,{x,2}}.
    {test_heap,3,3}.
    {put_tuple,2,{x,0}}.
    {put,{atom,ok}}.
    {put,{x,2}}.
    return.

然而，在这个非常简单的示例中，另一个优化实际上允许编译器删除对 {x,1} 的赋值

    {test,is_tagged_tuple,{f,1},[{x,0},4,{atom,tag}]}.
    {test_heap,3,1}.
    {get_tuple_element,{x,0},1,{x,2}}.
    {put_tuple,2,{x,0}}.
    {put,{atom,ok}}.
    {put,{x,2}}.
    return.

test_heap 和 get_tuple_element 指令已交换。请注意，test_heap 指令中活动的寄存器数量已调整。现在是 1 而不是 3。

但总的来说，编译器可能必须放弃优化或保留将寄存器赋值的指令，以避免将未定义的值传递给垃圾回收器。

最后一根稻草 #

在 OTP 21 的开发过程中，我们意识到我们已经达到了改进在 BEAM 汇编语言上进行优化的极限。特别是，我们希望使称为 延迟子二进制创建 的优化在更多情况下适用。事实证明，通过在 BEAM 汇编语言上工作来大幅改进优化将是困难的或不可能的。

除了像之前的优化示例中说明的那样留下未定义寄存器的问题外，还存在遍历和分析 BEAM 指令的复杂性。BEAM 指令集的设计并非对优化友好。

结论 #

正如我试图通过上面的示例展示的那样，使用 BEAM 代码最困难的部分之一是寄存器分配已经完成，并且可能执行垃圾回收的指令（例如 test_heap）也已经添加。

今年年初（2018 年），我们决定应该引入一种新的中间格式，以缓解优化 BEAM 代码的问题。它应该足够接近 BEAM 代码，以允许低级优化，例如此博客文章中描述的 is_tagged_tuple 优化，但寄存器分配不应完成，并且不应添加 test_heap 和类似的指令。它也应该更规则，以便在进行优化时更容易遍历。

我们决定使新的中间格式基于 SSA。在下一篇博客文章中，我们将重新审视本博客文章中的示例，看看它在 新的基于 SSA 的中间格式中是什么样子。