beam_bsm: Eliminate unsafe optimization

The following code causes a compiler failure:

first_after(Data, Offset) ->
    case byte_size(Data) > Offset of
	false ->
	    {First, Rest} = {ok, ok},
	    ok;
	true ->
	    <<_:Offset/binary, Rest/binary>> = Data,
	    %% 'Rest' saved in y(0) before the call.
	    {First, _} = match_first(Data, Rest),
	    %% When beam_bsm sees the code, the following line
            %% which uses y(0) has been optimized away.
	    {First, Rest} = {First, Rest},
	    First
    end.

match_first(_, <<First:1/binary, Rest/binary>>) ->
    {First, Rest}.

Here is the error message from beam_validator:

t: function first_after/2+15:
  Internal consistency check failed - please report this bug.
  Instruction: {call,2,{f,7}}
  Error:       {multiple_match_contexts,[{x,1},0]}:

Basically, what happens is that at time of code generation,
the variable 'Rest' is needed after the call to match_first/2
and is therefore saved in y(0). When beam_bsm (a late optimization
pass) sees the code, the use of y(0) following the call
to match_first/2 has been optimized away. beam_bsm therefore
assumes that the delayed sub-binary creation is safe. (Actually,
it is safe, but beam_validator does not realize it.)

The bug was caused by two separate commits:

e199e2471a reduced the number of special cases to handle in BEAM
optimization passed by breaking apart the tail-recursive call
instructions (call_only and call_last) into separate instructions.
Unfortunately, the special handling for tail calls was lost, which
resulted in worse code (i.e. the delayed sub-binary creation
optimization could not be applied).

e1aa422290 tried to compensate, but did so in a way that was not
always safe.

Teaching beam_validator that this kind of code is safe would be
expensive.

Instead, we will undo the damage caused by the two
commits. Re-introduce the special handling of tail-recursive calls in
beam_bsm that was lost in the first commit. (Effectively) revert the
change in the second commit.

ERL-268

2 files changed, 46 insertions, 11 deletions

diff --git a/lib/compiler/src/beam_bsm.erl b/lib/compiler/src/beam_bsm.erl
index 286307a4be..ae1b34ba49 100644
--- a/lib/compiler/src/beam_bsm.erl
+++ b/lib/compiler/src/beam_bsm.erl
@@ -205,8 +205,15 @@ btb_reaches_match_1(Is, Regs, D) ->
 btb_reaches_match_2([{block,Bl}|Is], Regs0, D) ->
     Regs = btb_reaches_match_block(Bl, Regs0),
     btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([{call,Arity,{f,Lbl}}|Is], Regs, D) ->
-    btb_call(Arity, Lbl, Regs, Is, D);
+btb_reaches_match_2([{call,Arity,{f,Lbl}}|Is], Regs0, D) ->
+    case is_tail_call(Is) of
+	true ->
+	    Regs1 = btb_kill_not_live(Arity, Regs0),
+	    Regs = btb_kill_yregs(Regs1),
+	    btb_tail_call(Lbl, Regs, D);
+	false ->
+	    btb_call(Arity, Lbl, Regs0, Is, D)
+    end;
 btb_reaches_match_2([{apply,Arity}|Is], Regs, D) ->
     btb_call(Arity+2, apply, Regs, Is, D);
 btb_reaches_match_2([{call_fun,Live}=I|Is], Regs, D) ->
@@ -360,6 +367,10 @@ btb_reaches_match_2([{line,_}|Is], Regs, D) ->
 btb_reaches_match_2([I|_], Regs, _) ->
     btb_error({btb_context_regs(Regs),I,not_handled}).
 
+is_tail_call([{deallocate,_}|_]) -> true;
+is_tail_call([return|_]) -> true;
+is_tail_call(_) -> false.
+
 btb_call(Arity, Lbl, Regs0, Is, D0) ->
     Regs = btb_kill_not_live(Arity, Regs0),
     case btb_are_x_registers_empty(Regs) of
@@ -369,15 +380,15 @@ btb_call(Arity, Lbl, Regs0, Is, D0) ->
 	    D = btb_tail_call(Lbl, Regs, D0),
 
 	    %% No problem so far (the called function can handle a
-	    %% match context). Now we must make sure that the rest
-	    %% of this function following the call does not attempt
-	    %% to use the match context in case there is a copy
-	    %% tucked away in a y register.
+	    %% match context). Now we must make sure that we don't
+	    %% have any copies of the match context tucked away in an
+	    %% y register.
 	    RegList = btb_context_regs(Regs),
-	    YRegs = [R || {y,_}=R <- RegList],
-	    case btb_are_all_unused(YRegs, Is, D) of
-		true -> D;
-		false -> btb_error({multiple_uses,RegList})
+	    case [R || {y,_}=R <- RegList] of
+		[] ->
+		    D;
+		[_|_] ->
+		    btb_error({multiple_uses,RegList})
 	    end;
 	true ->
 	    %% No match context in any x register. It could have been
diff --git a/lib/compiler/test/bs_match_SUITE.erl b/lib/compiler/test/bs_match_SUITE.erl
index 224abf6c29..a9bee888d9 100644
--- a/lib/compiler/test/bs_match_SUITE.erl
+++ b/lib/compiler/test/bs_match_SUITE.erl
@@ -38,7 +38,8 @@
 	 no_partition/1,calling_a_binary/1,binary_in_map/1,
 	 match_string_opt/1,select_on_integer/1,
 	 map_and_binary/1,unsafe_branch_caching/1,
-	 bad_literals/1,good_literals/1,constant_propagation/1]).
+	 bad_literals/1,good_literals/1,constant_propagation/1
+	]).
 
 -export([coverage_id/1,coverage_external_ignore/2]).
 
@@ -768,6 +769,11 @@ multiple_uses(Config) when is_list(Config) ->
     {344,62879,345,<<245,159,1,89>>} = multiple_uses_1(<<1,88,245,159,1,89>>),
     true = multiple_uses_2(<<0,0,197,18>>),
     <<42,43>> = multiple_uses_3(<<0,0,42,43>>, fun id/1),
+
+    ok = first_after(<<>>, 42),
+    <<1>> = first_after(<<1,2,3>>, 0),
+    <<2>> = first_after(<<1,2,3>>, 1),
+
     ok.
 
 multiple_uses_1(<<X:16,Tail/binary>>) ->
@@ -789,6 +795,24 @@ multiple_uses_match(<<Y:16,Z:16>>) ->
 multiple_uses_cmp(<<Y:16>>, <<Y:16>>) -> true;
 multiple_uses_cmp(<<_:16>>, <<_:16>>) -> false.
 
+first_after(Data, Offset) ->
+    case byte_size(Data) > Offset of
+	false ->
+	    {First, Rest} = {ok, ok},
+	    ok;
+	true ->
+	    <<_:Offset/binary, Rest/binary>> = Data,
+	    %% 'Rest' saved in y(0) before the call.
+            {First, _} = match_first(Data, Rest),
+            %% When beam_bsm sees the code, the following line
+            %% which uses y(0) has been optimized away.
+	    {First, Rest} = {First, Rest},
+	    First
+    end.
+
+match_first(_, <<First:1/binary, Rest/binary>>) ->
+    {First, Rest}.
+
 zero_label(Config) when is_list(Config) ->
     <<"nosemouth">> = read_pols(<<"FACE","nose","mouth">>),
     <<"CE">> = read_pols(<<"noFACE">>),