This blog post is an introduction to the new SSA-based intermediate representation that has recently been merged to the master branch in the Erlang/OTP repository. It uses the same example as in the previous blog post, first looking at the generated SSA code, and then at some optimizations.

Here again is the example function that does the kind of tuple matching typically done when matching records:

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

At the end of this blog post there will be section on how to generate listing files to inspect the code from the compiler passes.

A brief introduction to the SSA intermediate format #

SSA stands for Static Single Assignment. Strictly speaking, SSA is the property of an intermediate representation where each variable is assigned exactly once, and where every variable is defined before it is used. In this blog post, we will use the term SSA code to refer to the new intermediate representation in the Erlang compiler.

Here is the SSA code for the foo/1 function:

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
}

A deeper look at the example #

We will go through the code a few lines at the time.

function blog:foo(_0) {

This is the head of the function. It gives the module name (blog), function name (foo), and the arguments (the single variable _0).

Variables named as _ followed by an integer are inherited from Core Erlang. In OTP 22, variable names in Core Erlang are integers (to avoid filling the atom table when compiling huge functions).

0:

Following the function head is one or more blocks (sometimes called nodes). A integer followed by a colon gives the number of the block that follows.

The block number 0 is special. It is the first block that will be executed in this function.

  @ssa_bool:6 = bif:is_tuple _0

Here is the first real instruction! All instructions have this basic format. First there is a variable, followed by =, followed by the name of the instruction, followed by its operands.

The variable to the left, @ssa_bool:6 in this example, will be assigned the value of the expression to right of the =.

Each variable can only be assigned once, just as in Erlang. The name of this variable consists of two parts, the base part @ssa_bool and the numeric suffix 6. Whenever the base name itself is not unique, the numeric suffix is added to make the name unique.

The instruction name is bif:is_tuple. This is one of the instructions that use a two-part name. The bif prefix means that the second part must be the name of an Erlang guard BIF, in this case is_tuple/1.

Following the name of the instruction is the operand _0, which is the name of the function argument for the foo/1 function.

Thus, this instruction will call is_tuple/1 and assign the result (either true or false) to ssa_bool:6.

  br @ssa_bool:6, label 7, label 3

This is the last instruction of block 0. Instructions at the end of a block are called terminators and they have a different format compared to instructions in the interior of a block. Terminators either transfer control to another block or returns from the function.

br transfers control to another block. The first operand is a variable, whose value must be true or false. If the value of ssa_bool:6 is true, the second operand (label 7) is used as the block number for the block where execution will continue. In this example: block 7. Similarly, if the value of ssa_bool:6 is false, the third operand (label 3) will be used to transfer control to block 3.

7:
  @ssa_arity = bif:tuple_size _0

This is the beginning of block 7. This block will be executed if _0 was found to be a tuple. @ssa_arity will be assigned the value of the call tuple_size(_0).

Note that @ssa_arity does not have a numeric suffix, since there is no other variable in this function having the same base name.

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

Here bif:=:= compares @ssa_arity and 4 and assigns the result to @ssa_bool:8. (Note that =:= is a guard BIF in Erlang; it is allowed but unusual to write erlang:'=:='(Arity, 4) instead of Arity =:= 4.)

  br @ssa_bool:8, label 5, label 3

Here is another br instruction. It will transfer control to block 5 if @ssa_bool:8 is true (that is, if @ssa_arity is equal to 4), and to block 3 otherwise.

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

Block 5 is executed if _0 has been found to be a tuple of size 4. The get_tuple_element instruction extracts an element from a tuple at the given position. The position is zero-based.

The get_tuple_element instruction in SSA in named after the BEAM instruction with the same name:

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

Notice the similarity between the SSA instruction and the BEAM instruction. The SSA form uses variables instead of registers, and the destination variable is to the left of the = as in all SSA instructions.

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

Here comes the test that the first element of the tuple is equal to the atom tag. If the first element is tag, execution continues at block 4, otherwise at block 3.

4:
  _9 = put_tuple literal ok, _7

This instruction constructs the {ok,A} tuple. The variable _7 contains the second element of the tuple.

The put_tuple instruction takes any number of operands and constructs a tuple from them. The result is assigned to the variable _9.

In this case, the put_tuple instruction in SSA does more than the corresponding BEAM instruction. To construct the same tuple, three BEAM instructions are needed:

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

Having a single instruction to construct a tuple instead of the multiple BEAM instructions simplifies optimizations immensely. Also note that SSA has no equivalent of the test_heap instruction that caused so much trouble in the previous blog post.

  ret _9

ret is another terminator instruction. ret returns from the function with the value of variable _9 as the return value.

That concludes the successful path through the function.

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

This block is executed if any of br instructions in the previous blocks were given the value false, that is if the function argument was not a tuple or had the wrong size or wrong first element.

The comment line (starting with %%) has been added by the pretty printer based on annotation in the call instruction.

It is left as an exercise to the reader to figure out exactly what the instructions in the block do. As a hint, here is the code for the block translated back to Erlang code:

erlang:error(function_clause, [_0]).

Moving on to the part of the function that is not executed at all:

%% Unreachable blocks

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

The comment (Unreachable blocks) was added by the pretty printer to indicate that the blocks that follow can never be executed, because no block will ever branch to them.

Why is there an unreachable block?

Block 1 is a special block. It generates a badarg exception, just as a call to error:error(badarg). The SSA code generator always includes block 1 with the exact same instructions in every function, even if it never actually used.

We will not go into details about the purpose of this block in this blog post (but we will see how it is used in the next blog post).

Optimizing the code #

Now it’s time to see how the SSA code can be optimized. The SSA optimizations follow the same idea as the Core Erlang optimizations of using many simple optimizations working together rather than a few complicated optimizations.

Here is the code for the function again as it looks after running a few preliminary optimization passes:

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
}

The unreachable block 1 has been deleted.

A pass that splits blocks before certain instructions has also been run (in order to make the passes for sinking get_tuple_element instructions and swapping element/2 calls more effective). This pass has split block 3 into two blocks. At the end of block 3 there is a variant of the br terminator that we have not seen before. br label 10 unconditionally continues the execution at block 10.

The first interesting optimization for our example is the ssa_opt_record optimizations, which attempts to translate tuple matching instructions with an is_tagged_tuple instruction. Here is the part of the code that will be optimized:

    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

The optimization is done in two stages. First the code is analyzed to find out whether the optimization is applicable. There must be a test for a tuple of a certain size (4 in this example) and with a certain first element (tag in this example). Furthermore all failure labels must be the same.

If all conditions are fulfilled, the optimization is done in the second stage. Here is the code again, with the optimized part of the code highlighted:

    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
    }

Yes, it really is this simple, but so far it is more of a pessimization than an optimization, because the bif:is_tuple instruction has been replaced with the more expensive is_tagged_tuple instruction.

The next optimization is a type analysis pass, which is implemented in the module beam_ssa_type. Here is the code after running 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 analyzes the code in execution order, remembering the type of each variable seen. Based on the types, beam_ssa_type replaces variables with known values with the values themselves.

Two of the conditional branches have been converted to unconditional branches.

The next optimization is liveness analysis. The code is scanned in reverse execution order, and if an expression is never used, and has no observable side effect, it can be deleted. The highlighted instructions in the code that follows was identified by the liveness analysis pass as unused:

    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
    }

Because those expressions don’t have any side effects, they can be deleted:

    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
    }

After running a pass that merges blocks, the final code looks like this:

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
}

Now it’s time to look at the resulting BEAM code. Here is the successful part of the function:

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

Since register allocation was done after the is_tagged_tuple optimization, the get_tuple_instruction will extract the second element of the tuple to the first available register, namely {x,0}. That avoids any potential problem of registers being undefined at a test_heap instruction. The put_tuple instruction will put the built tuple into {x,1} since the following {put,{x,0}} instruction still needs the contents of {x,0}. To return the built tuple, the {move,{x,1},{x,0}} instruction just before the return instruction copies the contents of {x,1} to {x,0}.

It happens that for this particular example, the OTP 21 compiler will produce slightly better code:

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

(The tuple can be built to {x,0} directly, avoiding the move instruction before the return.)

Getting rid of the move instruction #

Perhaps I should have chosen another example to avoid revealing that the SSA-based compiler sometimes produces worse code than the old compiler.

Anyway, now that the secret is out, let’s see what can been done about that extra move instruction.

Let’s look at another example:

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

The BEAM code produced by either the compiler in OTP 21 or the new SSA-based compiler looks like this:

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

Clearly, the way the tuple building instructions work, it would be impossible to avoid the move instruction. When building a tuple, the destination register for the built tuple must not be the same as one of the source registers. It seems that we will need better instructions for constructing tuples if we are to avoid the move instruction.

The problem doesn’t exist when building a list:

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

The put_list instruction can safely place the built list into the same register as either of the source registers.

Introducing a new put_tuple2 instruction that builds a tuple in a single instruction, the move instruction can be eliminated:

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

At the time of writing, the implementation of put_tuple2 has not yet been merged to the master branch, but can be found in #1947: Introduce a put_tuple2 instruction.

Next time #

As we have seen, a variable in the SSA code can only be assigned once (just as in Erlang). So how can the following code be translated to SSA code?

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

How to generate listing files #

To generate the unoptimized SSA code for a module, use the dssa option:

erlc +dssa blog.erl

The SSA code will be pretty printed into the file blog.ssa.

Use the dssaopt option to generate the optimized SSA code, printing it to the file blog.ssaopt.

erlc +dssaopt blog.erl

To see how the SSA code looked when not all optimization passes had been run, I used variations of the following command line

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

Those options are intentionally not documented. Skipping optimization is only intended for debugging or exploring how the optimization passes work. Skipping some optimizations passes that are actually mandatory will crash the compiler.

To find the names of the options for skipping passes, see the list of sub passes of beam_ssa_opt and add no_ to the name of the pass.

To generate blog.S with the BEAM code, use the -S option:

erlc -S blog.erl

To skip all SSA optimizations, use the no_ssa_opt option:

erlc +no_ssa_opt -S blog.erl