Index

SSA 简介

2018 年 9 月 5 日 · Björn Gustavsson

这篇博文是对基于 SSA 的新中间表示的介绍，该中间表示最近已合并到 Erlang/OTP 存储库的 master 分支中。它使用与之前的博文中相同的示例，首先查看生成的 SSA 代码，然后再查看一些优化。

再次给出示例函数，该函数执行匹配记录时通常进行的元组匹配

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

在本博文的最后，将有一个关于如何生成列表文件以检查来自编译器传递的代码的部分。

SSA 中间格式的简要介绍 #

SSA 代表静态单赋值。严格来说，SSA 是中间表示的属性，其中每个变量只被赋值一次，并且每个变量在使用之前都被定义。在本博文中，我们将使用术语SSA 代码来指代 Erlang 编译器中的新中间表示。

以下是 foo/1 函数的 SSA 代码

function blog:foo(_0) {
0:
  @ssa_bool:6 = bif:is_tuple _0
  br @ssa_bool:6, label 7, label 3

7:
  @ssa_arity = bif:tuple_size _0
  @ssa_bool:8 = bif:'=:=' @ssa_arity, literal 4
  br @ssa_bool:8, label 5, label 3

5:
  _8 = get_tuple_element _0, literal 0
  _7 = get_tuple_element _0, literal 1
  @ssa_bool = bif:'=:=' _8, literal tag
  br @ssa_bool, label 4, label 3

4:
  _9 = put_tuple literal ok, _7
  ret _9

3:
  _4 = put_list _0, literal []

  %% blog.erl:4
  @ssa_ret:9 = call remote (literal erlang):(literal error)/2, literal function_clause, _4
  ret @ssa_ret:9

%% Unreachable blocks

1:
  @ssa_ret = call remote (literal erlang):(literal error)/1, literal badarg
  ret @ssa_ret
}

深入了解示例 #

我们将逐行浏览代码。

function blog:foo(_0) {

这是函数的头部。它给出了模块名称 (blog)、函数名称 (foo) 和参数（单个变量 _0）。

名称为 _ 后跟整数的变量继承自 Core Erlang。在 OTP 22 中，Core Erlang 中的变量名称是整数（以避免在编译大型函数时填充原子表）。

0:

函数头之后是一个或多个块（有时称为节点）。后跟冒号的整数表示后续块的编号。

块编号 0 是特殊的。它是此函数中将要执行的第一个块。

  @ssa_bool:6 = bif:is_tuple _0

这是第一个真正的指令！所有指令都具有这种基本格式。首先是一个变量，后跟 =，后跟指令的名称，后跟其操作数。

左侧的变量 @ssa_bool:6 在此示例中将被赋予 = 右侧表达式的值。

每个变量只能被赋值一次，就像在 Erlang 中一样。此变量的名称由两部分组成，基本部分 @ssa_bool 和数字后缀 6。每当基本名称本身不是唯一的时，就会添加数字后缀以使名称唯一。

指令名称是 bif:is_tuple。这是使用两部分名称的指令之一。 bif 前缀表示第二部分必须是 Erlang guard BIF 的名称，在本例中为 is_tuple/1。

指令名称后面是操作数 _0，它是 foo/1 函数的函数参数的名称。

因此，此指令将调用 is_tuple/1 并将结果（true 或 false）赋值给 ssa_bool:6。

  br @ssa_bool:6, label 7, label 3

这是块 0 的最后一条指令。块末尾的指令称为终止符，它们与块内部的指令相比具有不同的格式。终止符将控制权转移到另一个块或从函数返回。

br 将控制权转移到另一个块。第一个操作数是一个变量，其值必须为 true 或 false。如果 ssa_bool:6 的值为 true，则第二个操作数 (label 7) 用作将继续执行的块的块号。在本示例中：块 7。类似地，如果 ssa_bool:6 的值为 false，则第三个操作数 (label 3) 将用于将控制权转移到块 3。

7:
  @ssa_arity = bif:tuple_size _0

这是块 7 的开头。如果发现 _0 是一个元组，则将执行此块。 @ssa_arity 将被赋值为 tuple_size(_0) 调用的值。

请注意，@ssa_arity 没有数字后缀，因为此函数中没有其他变量具有相同的基本名称。

  @ssa_bool:8 = bif:'=:=' @ssa_arity, literal 4

此处 bif:=:= 比较 @ssa_arity 和 4，并将结果赋值给 @ssa_bool:8。（请注意，=:= 是 Erlang 中的 guard BIF；可以但通常不写 erlang:'=:='(Arity, 4) 而不是 Arity =:= 4。）

  br @ssa_bool:8, label 5, label 3

这是另一个 br 指令。如果 @ssa_bool:8 为 true（即，如果 @ssa_arity 等于 4），它将将控制权转移到块 5，否则将转移到块 3。

5:
  _8 = get_tuple_element _0, literal 0
  _7 = get_tuple_element _0, literal 1

如果发现 _0 是大小为 4 的元组，则执行块 5。 get_tuple_element 指令从给定位置的元组中提取元素。位置从零开始。

SSA 中的 get_tuple_element 指令以同名的 BEAM 指令命名

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

请注意 SSA 指令和 BEAM 指令之间的相似性。SSA 形式使用变量而不是寄存器，并且目标变量位于 = 的左侧，就像在所有 SSA 指令中一样。

  @ssa_bool = bif:'=:=' _8, literal tag
  br @ssa_bool, label 4, label 3

接下来测试元组的第一个元素是否等于原子 tag。如果第一个元素是 tag，则执行在块 4 继续，否则在块 3 继续。

4:
  _9 = put_tuple literal ok, _7

此指令构造 {ok,A} 元组。变量 _7 包含元组的第二个元素。

put_tuple 指令接受任意数量的操作数并从它们构造一个元组。结果被赋值给变量 _9。

在这种情况下，SSA 中的 put_tuple 指令比相应的 BEAM 指令执行更多操作。要构造相同的元组，需要三个 BEAM 指令

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

拥有单个指令来构造元组而不是多个 BEAM 指令极大地简化了优化。另请注意，SSA 没有与之前博文中引起很多麻烦的 test_heap 指令等效的指令。

  ret _9

ret 是另一个终止符指令。 ret 从函数返回，并以变量 _9 的值作为返回值。

至此，函数成功路径结束。

3:
  _4 = put_list _0, literal []

  %% blog.erl:4
  @ssa_ret:9 = call remote (literal erlang):(literal error)/2, literal function_clause, _4
  ret @ssa_ret:9

如果在前面的块中的任何 br 指令被赋予值 false，即如果函数参数不是元组或具有错误的大小或错误的第一个元素，则执行此块。

注释行（以 %% 开头）已由漂亮打印机根据 call 指令中的注释添加。

留给读者练习以准确弄清楚块中的指令执行什么操作。提示一下，这是块的代码转换回 Erlang 代码

erlang:error(function_clause, [_0]).

接下来转到函数中根本不执行的部分

%% Unreachable blocks

1:
  @ssa_ret = call remote (literal erlang):(literal error)/1, literal badarg
  ret @ssa_ret

注释 (Unreachable blocks) 由漂亮打印机添加，以指示永远无法执行后续的块，因为没有任何块会分支到这些块。

为什么会有一个无法到达的块？

块 1 是一个特殊块。它生成一个 badarg 异常，就像调用 error:error(badarg) 一样。SSA 代码生成器始终在每个函数中包含具有完全相同指令的块 1，即使它从未使用过。

我们不会在这篇博文中详细介绍此块的目的（但我们将在下一篇博文中看到它是如何使用的）。

优化代码 #

现在是时候看看如何优化 SSA 代码了。SSA 优化遵循与 Core Erlang 优化相同的思想，即使用许多协同工作的简单优化，而不是少数复杂的优化。

以下是再次运行一些初步优化传递后函数的代码

function blog:foo(_0) {
0:
  @ssa_bool:6 = bif:is_tuple _0
  br @ssa_bool:6, label 7, label 3

7:
  @ssa_arity = bif:tuple_size _0
  @ssa_bool:8 = bif:'=:=' @ssa_arity, literal 4
  br @ssa_bool:8, label 5, label 3

5:
  _8 = get_tuple_element _0, literal 0
  _7 = get_tuple_element _0, literal 1
  @ssa_bool = bif:'=:=' _8, literal tag
  br @ssa_bool, label 4, label 3

4:
  _9 = put_tuple literal ok, _7
  ret _9

3:
  _4 = put_list _0, literal []
  br label 10

10:
  %% blog.erl:4
  @ssa_ret:9 = call remote (literal erlang):(literal error)/2, literal function_clause, _4
  ret @ssa_ret:9
}

无法到达的块 1 已被删除。

一个在某些指令之前拆分块的传递也已运行（以便更有效地进行下沉 get_tuple_element 指令和交换 element/2 调用的传递）。此传递已将块 3 分割成两个块。在块 3 的末尾，有一个我们之前没有见过的 br 终止符的变体。 br label 10 无条件地继续在块 10 执行。

我们示例的第一个有趣的优化是ssa_opt_record 优化，它尝试使用 is_tagged_tuple 指令转换元组匹配指令。这是将被优化的代码部分

    0:
      @ssa_bool:6 = bif:is_tuple _0
      br @ssa_bool:6, label 7, label 3

    7:
      @ssa_arity = bif:tuple_size _0
      @ssa_bool:8 = bif:'=:=' @ssa_arity, literal 4
      br @ssa_bool:8, label 5, label 3

    5:
      _8 = get_tuple_element _0, literal 0
      @ssa_bool = bif:'=:=' _8, literal tag
      br @ssa_bool, label 4, label 3

优化分两个阶段完成。首先，分析代码以找出优化是否适用。必须对具有特定大小（在此示例中为 4）和特定第一个元素（在此示例中为 tag）的元组进行测试。此外，所有失败标签必须相同。

如果满足所有条件，则在第二阶段完成优化。以下是再次显示的代码，其中突出显示了优化的代码部分

    function blog:foo(_0) {
    0:
      @ssa_bool:6 = is_tagged_tuple _0, literal 4, literal tag
      br @ssa_bool:6, label 7, label 3

    7:
      @ssa_arity = bif:tuple_size _0
      @ssa_bool:8 = bif:'=:=' @ssa_arity, literal 4
      br @ssa_bool:8, label 5, label 3

    5:
      _8 = get_tuple_element _0, literal 0
      @ssa_bool = bif:'=:=' _8, literal tag
      br @ssa_bool, label 4, label 3

    4:
      _7 = get_tuple_element _0, literal 1
      _9 = put_tuple literal ok, _7
      ret _9

    3:
      _4 = put_list _0, literal []
      br label 10

    10:
      %% blog.erl:4
      @ssa_ret:9 = call remote (literal erlang):(literal error)/2, literal function_clause, _4
      ret @ssa_ret:9
    }

是的，它确实非常简单，但到目前为止，与其说是优化，不如说更像是悲观化，因为 bif:is_tuple 指令已被更昂贵的 is_tagged_tuple 指令所取代。

下一个优化步骤是类型分析，它在 beam_ssa_type 模块中实现。以下是运行 beam_ssa_type 后的代码。

    function blog:foo(_0) {
    0:
      @ssa_bool:6 = is_tagged_tuple _0, literal 4, literal tag
      br @ssa_bool:6, label 7, label 3

    7:
      @ssa_arity = bif:tuple_size _0
      @ssa_bool:8 = bif:'=:=' literal 4, literal 4
      br label 5

    5:
      _8 = get_tuple_element _0, literal 0
      @ssa_bool = bif:'=:=' literal tag, literal tag
      br label 4

    4:
      _7 = get_tuple_element _0, literal 1
      _9 = put_tuple literal ok, _7
      ret _9

    3:
      _4 = put_list _0, literal []
      br label 10

    10:
      %% blog.erl:4
      @ssa_ret:9 = call remote (literal erlang):(literal error)/2, literal function_clause, _4
      ret @ssa_ret:9
    }

beam_ssa_type 按执行顺序分析代码，记住所看到的每个变量的类型。基于这些类型，beam_ssa_type 将已知值的变量替换为实际的值。

其中两个条件分支已转换为无条件分支。

下一个优化是活跃性分析。代码以反向执行顺序扫描，如果一个表达式从未使用过，并且没有可观察的副作用，则可以删除它。以下代码中突出显示的指令是被活跃性分析步骤识别为未使用的。

    function blog:foo(_0) {
    0:
      @ssa_bool:6 = is_tagged_tuple _0, literal 4, literal tag
      br @ssa_bool:6, label 7, label 3

    7:
      @ssa_arity = bif:tuple_size _0
      @ssa_bool:8 = bif:'=:=' literal 4, literal 4
      br label 5

    5:
      _8 = get_tuple_element _0, literal 0
      @ssa_bool = bif:'=:=' literal tag, literal tag
      br label 4

    4:
      _7 = get_tuple_element _0, literal 1
      _9 = put_tuple literal ok, _7
      ret _9

    3:
      _4 = put_list _0, literal []
      br label 10

    10:
      %% blog.erl:4
      @ssa_ret:9 = call remote (literal erlang):(literal error)/2, literal function_clause, _4
      ret @ssa_ret:9
    }

由于这些表达式没有任何副作用，因此可以删除它们。

    function blog:foo(_0) {
    0:
      @ssa_bool:6 = is_tagged_tuple _0, literal 4, literal tag
      br @ssa_bool:6, label 7, label 3

    7:
      br label 5

    5:
      br label 4

    4:
      _7 = get_tuple_element _0, literal 1
      _9 = put_tuple literal ok, _7
      ret _9

    3:
      _4 = put_list _0, literal []
      br label 10

    10:
      %% blog.erl:4
      @ssa_ret:9 = call remote (literal erlang):(literal error)/2, literal function_clause, _4
      ret @ssa_ret:9
    }

运行一个合并块的步骤后，最终代码如下所示。

function blog:foo(_0) {
0:
  @ssa_bool:6 = is_tagged_tuple _0, literal 4, literal tag
  br @ssa_bool:6, label 5, label 3

5:
  _7 = get_tuple_element _0, literal 1
  _9 = put_tuple literal ok, _7
  ret _9

3:
  _4 = put_list _0, literal []

  %% blog.erl:4
  @ssa_ret:9 = call remote (literal erlang):(literal error)/2, literal function_clause, _4
  ret @ssa_ret:9
}

现在是时候看看生成的 BEAM 代码了。以下是函数成功的代码部分。

%% Block 0.
{test,is_tagged_tuple,{f,1},[{x,0},4,{atom,tag}]}.

%% Block 5.
{test_heap,3,1}.
{get_tuple_element,{x,0},1,{x,0}}.
{put_tuple,2,{x,1}}.
{put,{atom,ok}}.
{put,{x,0}}.
{move,{x,1},{x,0}}.
return.

由于寄存器分配是在 is_tagged_tuple 优化之后完成的，get_tuple_instruction 指令会将元组的第二个元素提取到第一个可用寄存器，即 {x,0}。这避免了在 test_heap 指令处寄存器可能未定义的潜在问题。由于后面的 {put,{x,0}} 指令仍然需要 {x,0} 的内容，因此 put_tuple 指令会将构建的元组放入 {x,1} 中。为了返回构建的元组，return 指令之前的 {move,{x,1},{x,0}} 指令会将 {x,1} 的内容复制到 {x,0}。

对于这个特定的例子，OTP 21 编译器会产生稍微好一点的代码。

    {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.

（可以直接将元组构建到 {x,0} 中，从而避免了 return 之前的 move 指令。）

消除 `move` 指令 #

也许我应该选择另一个例子，以避免暴露基于 SSA 的编译器有时会产生比旧编译器更糟糕的代码。

无论如何，既然秘密已经揭露，让我们看看可以如何处理额外的 move 指令。

让我们看另一个例子。

make_tuple(A) ->
    {ok,A}.

无论是 OTP 21 中的编译器还是新的基于 SSA 的编译器生成的 BEAM 代码都如下所示。

{test_heap,3,1}.
{put_tuple,2,{x,1}}.
{put,{atom,ok}}.
{put,{x,0}}.
{move,{x,1},{x,0}}.
return.

显然，元组构建指令的工作方式，不可能避免 move 指令。在构建元组时，构建的元组的目标寄存器不能与源寄存器之一相同。看来我们需要更好的指令来构造元组，才能避免 move 指令。

构建列表时不存在这个问题。

%% build_list(A) -> [A].
{test_heap,2,1}.
{put_list,{x,0},nil,{x,0}}.
return.

put_list 指令可以安全地将构建的列表放入与任何一个源寄存器相同的寄存器中。

引入一个新的 put_tuple2 指令，该指令在单个指令中构建元组，从而可以消除 move 指令。

{test_heap,3,1}.
{put_tuple2,{x,0},{list,[{atom,ok},{x,0}]}}.
return.

在撰写本文时，put_tuple2 的实现尚未合并到 master 分支，但可以在 #1947: Introduce a put_tuple2 instruction 中找到。

下次再见 #

正如我们所见，SSA 代码中的变量只能赋值一次（就像在 Erlang 中一样）。那么，以下代码如何转换为 SSA 代码？

bar(X) ->
    case X of
        none ->
            Y = 0;
        _ ->
            Y = X
    end,
    Y + 1.

如何生成列表文件 #

要为模块生成未优化的 SSA 代码，请使用 dssa 选项。

erlc +dssa blog.erl

SSA 代码将以美化的格式打印到 blog.ssa 文件中。

使用 dssaopt 选项生成优化的 SSA 代码，并将其打印到 blog.ssaopt 文件中。

erlc +dssaopt blog.erl

为了查看在未运行所有优化步骤时 SSA 代码的样子，我使用了以下命令行的一些变体。

erlc +dssaopt +no_ssa_opt_type +no_ssa_opt_live +no_ssa_opt_merge_blocks blog.erl

这些选项有意未记录在文档中。跳过优化仅用于调试或探索优化步骤的工作方式。跳过一些实际上是强制性的优化步骤将会导致编译器崩溃。

要查找跳过步骤的选项名称，请参阅 beam_ssa_opt 的子步骤列表，并在步骤名称前添加 no_。

要使用 BEAM 代码生成 blog.S，请使用 -S 选项。

erlc -S blog.erl

要跳过所有 SSA 优化，请使用 no_ssa_opt 选项。

erlc +no_ssa_opt -S blog.erl