Index

深入探索 SSA

2018年9月20日 · 作者：Björn Gustavsson

这篇博文通过多个示例继续探索基于 SSA 的新中间表示。如果你错过了，请务必阅读SSA 介绍。

调用可能失败的 BIF #

第一个示例调用一个可能因异常而失败的 guard BIF

element_body(T) ->
    element(2, T).

（优化的）SSA 代码如下所示

function blog:element_body(_0) {
0:
  %% blog.erl:5
  _1 = bif:element literal 2, _0
  @ssa_bool = succeeded _1
  br @ssa_bool, label 3, label 1

3:
  ret _1

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

让我们一次几行地浏览代码

  %% blog.erl:5
  _1 = bif:element literal 2, _0
  @ssa_bool = succeeded _1

bif:element 指令调用 guard BIF element/2，如果调用成功，则将值赋给变量 _1。

如果调用不成功会怎么样？

succeeded _1 指令测试先前赋值给 _1 的指令是否成功。如果成功从元组中获取第二个元素，则将 true 赋值给 @ssa_bool，否则赋值为 false。

  br @ssa_bool, label 3, label 1

br 指令测试 @ssa_bool 是否为 true。如果为 true，则执行在块 3 中继续，该块从元组返回第二个元素的值。如果为 false，则执行在块 1 中继续。

在之前的博客文章中提到，块 1 是 SSA 代码生成器始终发出的一个特殊块。在前面的示例中，它从未被引用，因此被其中一个优化过程删除了。

在此示例中，当调用 element/2 失败时，它用作目标。

BEAM 代码生成器特别处理对块 1 的引用。以下是该函数的 BEAM 代码。像往常一样，我省略了函数头。

  %% Block 0.
  {line,[{location,"blog.erl",5}]}.
  {bif,element,{f,0},[{integer,2},{x,0}],{x,0}}.
  return.

请注意，没有为块 1 生成任何代码。

line 指令给出源文件的文件名和行号。如果以下指令失败，它将在堆栈回溯中使用。

bif 指令调用给定的 guard BIF，在本例中为 element/2。{f,0} 操作数给出了如果 element/2 失败要采取的操作。数字 0 是一种特殊情况，表示如果 element/2 的调用失败，则应引发 badarg 异常。

guard 中失败的 BIF 调用 #

在下一个示例中，在 guard 中调用 element/2

element_guard(T) when element(2, T) =:= true ->
    ok;
element_guard(_) ->
    error.

SSA 代码如下所示

function blog:element_guard(_0) {
0:
  %% blog.erl:7
  _1 = bif:element literal 2, _0
  @ssa_bool = succeeded _1
  br @ssa_bool, label 4, label 3

4:
  @ssa_bool:5 = bif:'=:=' _1, literal true
  br @ssa_bool:5, label 6, label 3

6:
  ret literal ok

3:
  ret literal error
}

块 0 中的前两个指令与上一个示例中的相同。但是，br 指令具有不同的标签。失败标签是指块 3，该块返回 error 值。成功标签继续在块 4 执行。

4:
  @ssa_bool:5 = bif:'=:=' _1, literal true
  br @ssa_bool:5, label 6, label 3

块 4 是 Erlang 代码中 =:= true 部分的转换。如果元组中的第二个元素等于 true，则执行在块 6 中继续，该块返回 ok 值。否则，执行在块 3 中继续，该块返回 error 值。

这是 BEAM 代码

  {bif,element,{f,5},[{integer,2},{x,0}],{x,0}}.
  {test,is_eq_exact,{f,5},[{x,0},{atom,true}]}.
  {move,{atom,ok},{x,0}}.
  return.
{label,5}.
  {move,{atom,error},{x,0}}.
  return.

在 bif 指令中，{f,5} 表示如果 element/2 调用失败，执行应在标签 5 继续。否则，执行将继续在下一条指令处。

我们的第一个案例 #

这是下一个示例

case1(X) ->
    case X of
        1 -> a;
        2 -> b;
        _ -> c
    end.

转换为 SSA 代码

function blog:case1(_0) {
0:
  switch _0, label 3, [ { literal 2, label 5 }, { literal 1, label 4 } ]

4:
  ret literal a

5:
  ret literal b

3:
  ret literal c
}

switch 指令是根据变量的值，多路分支到任何数量的其他块之一。在此示例中，它根据变量 _0 的值进行分支。如果 _0 等于 2，则执行在块 5 中继续。如果 _0 等于 1，则执行在块 4 中继续。如果该值不等于开关列表中的任何值，则执行继续在失败标签引用的块中，在本例中为块 3。

BEAM 代码如下所示

  {select_val,{x,0},{f,10},{list,[{integer,2},{f,9},{integer,1},{f,8}]}}.
{label,8}.
  {move,{atom,a},{x,0}}.
  return.
{label,9}.
  {move,{atom,b},{x,0}}.
  return.
{label,10}.
  {move,{atom,c},{x,0}}.
  return.

终止符 #

如之前的博客文章中所述，块中的最后一条指令称为终止符。终止符要么从函数返回，要么将控制权转移到另一个块。随着 switch 的引入，终止符的故事就完整了。总而言之，一个块可以以下列终止符之一结束

ret 从函数返回值。
br 要么分支到另一个块（单向分支），要么根据变量分支到两个可能的其他块之一（双向分支）。
switch 分支到任何数量的其他块之一。

另一个案例 #

这是一个略有不同的示例

case2(X) ->
    case X of
        1 -> a;
        2 -> b;
        3 -> c
    end.

在这种情况下，X 必须是整数 1、2 或 3 之一。否则，将出现 {case_clause,X} 异常。以下是 SSA 代码

function blog:case2(_0) {
0:
  switch _0, label 3, [ { literal 3, label 6 }, { literal 2, label 5 }, { literal 1, label 4 } ]

4:
  ret literal a

5:
  ret literal b

6:
  ret literal c

3:
  _2 = put_tuple literal case_clause, _0

  %% blog.erl:20
  @ssa_ret:7 = call remote (literal erlang):(literal error)/1, _2
  ret @ssa_ret:7
}

switch 的失败标签为 3。块 3 构建 {case_clause,X} 元组并调用 erlang:error/1。

这是 BEAM 代码

  {select_val,{x,0},
              {f,16},
              {list,[{integer,3},
                     {f,15},
                     {integer,2},
                     {f,14},
                     {integer,1},
                     {f,13}]}}.
{label,13}.
  {move,{atom,a},{x,0}}.
  return.
{label,14}.
  {move,{atom,b},{x,0}}.
  return.
{label,15}.
  {move,{atom,c},{x,0}}.
  return.
{label,16}.
  {line,[{location,"blog.erl",20}]}.
  {case_end,{x,0}}.

case_end 指令是一种优化，用于节省空间。它比等效的指令短

  {test_heap,3,1}.
  {put_tuple2,{x,0},{list,[{atom,case_clause},{x,0}]}}.
  {line,[{location,"blog.erl",20}]}.
  {call_ext_only,1,{extfunc,erlang,error,1}}.

（put_tuple2 指令在#1947：引入 put_tuple2 指令中引入，最近已合并到 master。）

我们的最终案例 #

现在是时候处理类似于上一篇博客文章末尾预告的那种 case 了。

在此示例中，变量 Y 将在 case 的每个子句中被赋予不同的值

case3a(X) ->
    case X of
        zero ->
            Y = 0;
        something ->
            Y = X;
        _ ->
            Y = no_idea
    end,
    {ok,Y}.

也许更常见的编写此 case 的方法是

case3b(X) ->
    Y = case X of
            zero -> 0;
            something -> X;
            _ -> no_idea
        end,
    {ok,Y}.

无论哪种情况，问题依然存在。静态单赋值意味着每个变量只能被赋值一次。那么如何将此示例转换为 SSA 代码？

以下是 case3a/1 的 SSA 代码。case3b/1 的 SSA 代码几乎相同，只是变量命名不同。

function blog:case3a(_0) {
0:
  switch _0, label 4, [ { literal something, label 6 }, { literal zero, label 5 } ]

5:
  br label 3

6:
  br label 3

4:
  br label 3

3:
  Y = phi { literal no_idea, 4 }, { literal 0, 5 }, { _0, 6 }
  _7 = put_tuple literal ok, Y
  ret _7
}

让我们直接跳到代码中令人感兴趣（且令人困惑）的部分

3:
  Y = phi { literal no_idea, 4 }, { literal 0, 5 }, { _0, 6 }

显然，Y 只被赋值一次，因此保留了 SSA 属性。

这很好，但被赋予的值到底是什么？

指令的名称是 phi，这是希腊字母 φ 的名称。由于具有不寻常的名称，因此该指令也应该具有不寻常的操作数。每个操作数都是一对，该对中的第一个元素是一个值，第二个元素是前驱块的块号。phi 节点的值将是来自其中一对的值之一。但是来自哪对呢？这取决于分支到 phi 指令的前一个块的编号。

为了更清楚地说明这一点，让我们看一下所有操作数

{ literal no_idea, 4 }：如果执行 br label 3 的块的编号为 4，则 phi 指令的值将是该对中的值，即原子 no_idea。switch 指令的失败标签是 4，因此当 _0 与开关列表中的任何值都不匹配时，将选择此对。
{ literal 0, 5 }：如果执行 br label 3 的块的编号为 5，则 phi 指令的值将是整数 0。如果 _0 的值为原子 zero，则 switch 指令会将控制权转移到块 5。
{ _0, 6 }：最后，如果 _0 是原子 something，则 switch 会将控制权转移到块 6，然后块 6 会将控制权转移到块 3。phi 指令的值将是变量 _0 的值。

phi 指令的概念乍一看（以及第二眼看）可能感觉有点奇怪，而且人们可能还会认为它们肯定效率很低。

抛开奇怪之处不谈，让我们来谈谈效率。phi 指令是一种方便的虚构，用于表示和优化代码。在转换为 BEAM 代码时，phi 指令将被消除。

以下是一个不是 SSA 代码的示例，因为它将变量 Y 赋值了三次，但给出了如何消除 phi 指令的想法

%% Not SSA code!
function blog:case3a(_0) {
0:
  switch _0, label 4, [ { literal something, label 6 }, { literal zero, label 5 } ]

5:
  Y := literal 0
  br label 3

6:
  Y := _0
  br label 3

4:
  Y := no_idea
  br label 3

3:
  _7 = put_tuple literal ok, Y
  ret _7
}

BEAM 代码生成器（beam_ssa_codegen）在代码生成期间进行类似的重写。

以下是未优化的 BEAM 代码，为了清楚起见略作编辑

%% Block 0.
{select_val,{x,0},
            {f,53},
            {list,[{atom,something},{f,55},{atom,zero},{f,57}]}}.

%% Block 5.
{label,57}.
  {move,{integer,0},{x,0}}.
  {jump,{f,59}}.

%% Block 6.
{label,55}.
  %% The result is already in {x,0}.
  {jump,{f,59}}.

%% Block 4.
{label,53}.
  {move,{atom,no_idea},{x,0}}.
  {jump,{f,59}}.

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

这是经过一些优化的最终 BEAM 代码

{label,18}.
  {select_val,{x,0},
              {f,20},
              {list,[{atom,something},{f,21},{atom,zero},{f,19}]}}.
{label,19}.
  {move,{integer,0},{x,0}}.
  {jump,{f,21}}.
{label,20}.
  {move,{atom,no_idea},{x,0}}.
{label,21}.
  {test_heap,3,1}.
  {put_tuple2,{x,0},{list,[{atom,ok},{x,0}]}}.
  return.

冷案例 #

这是上一篇博客文章末尾的示例

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

这是 SSA 代码

function blog:bar(_0) {
0:
  @ssa_bool = bif:'=:=' _0, literal none
  br @ssa_bool, label 5, label 4

5:
  br label 3

4:
  br label 3

3:
  Y = phi { _0, 4 }, { literal 0, 5 }

  %% blog.erl:52
  _6 = bif:'+' Y, literal 1
  @ssa_bool:6 = succeeded _6
  br @ssa_bool:6, label 7, label 1

7:
  ret _6

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

留给读者作为练习来阅读和理解代码。

这是 BEAM 代码

{label,28}.
  {test,is_eq_exact,{f,29},[{x,0},{atom,none}]}.
  {move,{integer,0},{x,0}}.
{label,29}.
  {line,[{location,"blog.erl",52}]}.
  {gc_bif,'+',{f,0},1,[{x,0},{integer,1}],{x,0}}.
  return.

gc_bif 指令调用一个可能需要进行垃圾回收的 guard BIF。由于 Erlang 中的整数的大小本质上不受限制，因此 + 的结果可能不适合一个字。{f,0} 后的 1 是必须保留的寄存器数量；在本例中，仅为 {x,0}。