Use a set to store ref registers in beam_receive

In some circumstances, as when inlining code, when some optimization
passes are disabled or with hand-written but semantically correct Core
Erlang or BEAM assembly, a fresh reference may be live in more than one
register:

    ...
    {allocate_zero,2,2}.
    ...
    {call_ext,0,{extfunc,erlang,make_ref,0}}. % Ref in [x0]
    ...
    {move,{x,0},{y,0}}. % Ref in [x0,y0]
    {move,{y,1},{x,0}}. % Ref in [y0]
    ...
    {move,{y,0},{x,0}}. % Ref in [x0,y0]
    {move,{x,0},{y,1}}. % Ref in [x0,y0,y1]
  {label,5}.
    {loop_rec,{f,6},{x,0}}. % Ref in [y0,y1]
    ...
    {loop_rec_end,{f,5}}.
  {label,6}.
    {wait,{f,5}}.
    ...

Pass beam_receive expects a single live register for the ref when it
encounters the loop_rec instruction and crashes with the following
reason:

$ erlc t.S
...
crash reason: {{case_clause,
                   {'EXIT',
                       {{case_clause,[{y,1},{y,0}]},
                        [{beam_receive,opt_recv,5,
                             [{file,"beam_receive.erl"},{line,154}]},
                         ...]}}},
               ...}

This commit teaches beam_receive how to use a set of registers instead
of a single one when tracking fresh references, thus avoiding the crash.

3 files changed, 120 insertions, 56 deletions

diff --git a/lib/compiler/src/beam_receive.erl b/lib/compiler/src/beam_receive.erl
index 3dd5ed182e..97a9188ee7 100644
--- a/lib/compiler/src/beam_receive.erl
+++ b/lib/compiler/src/beam_receive.erl
@@ -151,20 +151,20 @@ opt_recv(Is, Regs, D) ->
 
 opt_recv([{label,L}=Lbl,{loop_rec,{f,Fail},_}=Loop|Is], D, R0, _, Acc) ->
     R = regs_kill_not_live(0, R0),
-    case regs_to_list(R) of
-	[{y,_}=RefReg] ->
-	    %% We now have the new reference in the Y register RefReg
+    case regs_empty(R) of
+	false ->
+	    %% We now have the new reference in Y registers
 	    %% and the current instruction is the beginning of a
 	    %% receive statement. We must now verify that only messages
 	    %% that contain the reference will be matched.
-	    case opt_ref_used(Is, RefReg, Fail, D) of
+	    case opt_ref_used(Is, R, Fail, D) of
 		false ->
 		    no;
 		true ->
 		    RecvSet = {recv_set,{f,L}},
 		    {yes,reverse(Acc, [RecvSet,Lbl,Loop|Is]),L}
 	    end;
-	[] ->
+	true ->
 	    no
     end;
 opt_recv([I|Is], D, R0, L0, Acc) ->
@@ -226,9 +226,9 @@ opt_update_regs_bl([{set,Ds,_,_}|Is], Regs0) ->
     opt_update_regs_bl(Is, Regs);
 opt_update_regs_bl([], Regs) -> Regs.
 
-%% opt_ref_used([Instruction], RefRegister, FailLabel, LabelIndex) -> true|false
+%% opt_ref_used([Instruction], RefRegs, FailLabel, LabelIndex) -> true|false
 %%  Return 'true' if it is certain that only messages that contain the same
-%%  reference as in RefRegister can be matched out. Otherwise return 'false'.
+%%  reference as in RefRegs can be matched out. Otherwise return 'false'.
 %%
 %%  Basically, we follow all possible paths through the receive statement.
 %%  If all paths are safe, we return 'true'.
@@ -236,7 +236,7 @@ opt_update_regs_bl([], Regs) -> Regs.
 %%  A branch to FailLabel is safe, because it exits the receive statement
 %%  and no further message may be matched out.
 %%
-%%  If a path hits an comparision between RefRegister and part of the message,
+%%  If a path hits an comparision between RefRegs and part of the message,
 %%  that path is safe (any messages that may be matched further down the
 %%  path is guaranteed to contain the reference).
 %%
@@ -245,11 +245,11 @@ opt_update_regs_bl([], Regs) -> Regs.
 %%  we hit an unrecognized instruction, we also give up and return
 %%  'false' (the optimization may be unsafe).
 
-opt_ref_used(Is, RefReg, Fail, D) ->
+opt_ref_used(Is, RefRegs, Fail, D) ->
     Done = gb_sets:singleton(Fail),
     Regs = regs_init_x0(),
     try
-	_ = opt_ref_used_1(Is, RefReg, D, Done, Regs),
+	_ = opt_ref_used_1(Is, RefRegs, D, Done, Regs),
 	true
     catch
 	throw:not_used ->
@@ -258,37 +258,39 @@ opt_ref_used(Is, RefReg, Fail, D) ->
 
 %% This functions only returns if all paths through the receive
 %% statement are safe, and throws an 'not_used' term otherwise.
-opt_ref_used_1([{block,Bl}|Is], RefReg, D, Done, Regs0) ->
+opt_ref_used_1([{block,Bl}|Is], RefRegs, D, Done, Regs0) ->
     Regs = opt_ref_used_bl(Bl, Regs0),
-    opt_ref_used_1(Is, RefReg, D, Done, Regs);
-opt_ref_used_1([{test,is_eq_exact,{f,Fail},Args}|Is], RefReg, D, Done0, Regs) ->
-    Done = opt_ref_used_at(Fail, RefReg, D, Done0, Regs),
-    case is_ref_msg_comparison(Args, RefReg, Regs) of
+    opt_ref_used_1(Is, RefRegs, D, Done, Regs);
+opt_ref_used_1([{test,is_eq_exact,{f,Fail},Args}|Is],
+	       RefRegs, D, Done0, Regs) ->
+    Done = opt_ref_used_at(Fail, RefRegs, D, Done0, Regs),
+    case is_ref_msg_comparison(Args, RefRegs, Regs) of
 	false ->
-	    opt_ref_used_1(Is, RefReg, D, Done, Regs);
+	    opt_ref_used_1(Is, RefRegs, D, Done, Regs);
 	true ->
 	    %% The instructions that follow (Is) can only be executed
-	    %% if the message contains the same reference as in RefReg.
+	    %% if the message contains the same reference as in RefRegs.
 	    Done
     end;
-opt_ref_used_1([{test,is_ne_exact,{f,Fail},Args}|Is], RefReg, D, Done0, Regs) ->
-    Done = opt_ref_used_1(Is, RefReg, D, Done0, Regs),
-    case is_ref_msg_comparison(Args, RefReg, Regs) of
+opt_ref_used_1([{test,is_ne_exact,{f,Fail},Args}|Is],
+	       RefRegs, D, Done0, Regs) ->
+    Done = opt_ref_used_1(Is, RefRegs, D, Done0, Regs),
+    case is_ref_msg_comparison(Args, RefRegs, Regs) of
 	false ->
-	    opt_ref_used_at(Fail, RefReg, D, Done, Regs);
+	    opt_ref_used_at(Fail, RefRegs, D, Done, Regs);
 	true ->
 	    Done
     end;
-opt_ref_used_1([{test,_,{f,Fail},_}|Is], RefReg, D, Done0, Regs) ->
-    Done = opt_ref_used_at(Fail, RefReg, D, Done0, Regs),
-    opt_ref_used_1(Is, RefReg, D, Done, Regs);
-opt_ref_used_1([{select,_,_,{f,Fail},List}|_], RefReg, D, Done, Regs) ->
+opt_ref_used_1([{test,_,{f,Fail},_}|Is], RefRegs, D, Done0, Regs) ->
+    Done = opt_ref_used_at(Fail, RefRegs, D, Done0, Regs),
+    opt_ref_used_1(Is, RefRegs, D, Done, Regs);
+opt_ref_used_1([{select,_,_,{f,Fail},List}|_], RefRegs, D, Done, Regs) ->
     Lbls = [F || {f,F} <- List] ++ [Fail],
-    opt_ref_used_in_all(Lbls, RefReg, D, Done, Regs);
-opt_ref_used_1([{label,Lbl}|Is], RefReg, D, Done, Regs) ->
+    opt_ref_used_in_all(Lbls, RefRegs, D, Done, Regs);
+opt_ref_used_1([{label,Lbl}|Is], RefRegs, D, Done, Regs) ->
     case gb_sets:is_member(Lbl, Done) of
 	true -> Done;
-	false -> opt_ref_used_1(Is, RefReg, D, Done, Regs)
+	false -> opt_ref_used_1(Is, RefRegs, D, Done, Regs)
     end;
 opt_ref_used_1([{loop_rec_end,_}|_], _, _, Done, _) ->
     Done;
@@ -296,27 +298,25 @@ opt_ref_used_1([_I|_], _RefReg, _D, _Done, _Regs) ->
     %% The optimization may be unsafe.
     throw(not_used).
 
-%% is_ref_msg_comparison(Args, RefReg, RegisterSet) -> true|false.
+%% is_ref_msg_comparison(Args, RefRegs, RegisterSet) -> true|false.
 %%  Return 'true' if Args denotes a comparison between the
 %%  reference and message or part of the message.
-is_ref_msg_comparison([R,RefReg], RefReg, Regs) ->
-    regs_is_member(R, Regs);
-is_ref_msg_comparison([RefReg,R], RefReg, Regs) ->
-    regs_is_member(R, Regs);
-is_ref_msg_comparison([_,_], _, _) -> false.
-
-opt_ref_used_in_all([L|Ls], RefReg, D, Done0, Regs) ->
-    Done = opt_ref_used_at(L, RefReg, D, Done0, Regs),
-    opt_ref_used_in_all(Ls, RefReg, D, Done, Regs);
+is_ref_msg_comparison([R1,R2], RefRegs, Regs) ->
+    (regs_is_member(R2, RefRegs) andalso regs_is_member(R1, Regs)) orelse
+    (regs_is_member(R1, RefRegs) andalso regs_is_member(R2, Regs)).
+
+opt_ref_used_in_all([L|Ls], RefRegs, D, Done0, Regs) ->
+    Done = opt_ref_used_at(L, RefRegs, D, Done0, Regs),
+    opt_ref_used_in_all(Ls, RefRegs, D, Done, Regs);
 opt_ref_used_in_all([], _, _, Done, _) -> Done.
 
-opt_ref_used_at(Fail, RefReg, D, Done0, Regs) ->
+opt_ref_used_at(Fail, RefRegs, D, Done0, Regs) ->
     case gb_sets:is_member(Fail, Done0) of
 	true ->
 	    Done0;
 	false ->
 	    Is = beam_utils:code_at(Fail, D),
-	    Done = opt_ref_used_1(Is, RefReg, D, Done0, Regs),
+	    Done = opt_ref_used_1(Is, RefRegs, D, Done0, Regs),
 	    gb_sets:add(Fail, Done)
     end.
 
@@ -408,15 +408,3 @@ regs_all_members([], _) -> true.
 regs_is_member({x,N}, {Regs,_}) -> Regs band (1 bsl N) =/= 0;
 regs_is_member({y,N}, {_,Regs}) -> Regs band (1 bsl N) =/= 0;
 regs_is_member(_, _) -> false.
-
-%% regs_to_list(RegisterSet) -> [Register]
-%%  Convert the register set to an explicit list of registers.
-regs_to_list({Xregs,Yregs}) ->
-    regs_to_list_1(Xregs, 0, x, regs_to_list_1(Yregs, 0, y, [])).
-
-regs_to_list_1(0, _, _, Acc) ->
-    Acc;
-regs_to_list_1(Regs, N, Tag, Acc) when (Regs band 1) =:= 1 ->
-    regs_to_list_1(Regs bsr 1, N+1, Tag, [{Tag,N}|Acc]);
-regs_to_list_1(Regs, N, Tag, Acc) ->
-    regs_to_list_1(Regs bsr 1, N+1, Tag, Acc).
diff --git a/lib/compiler/test/receive_SUITE.erl b/lib/compiler/test/receive_SUITE.erl
index b91f2922fb..e60584d4ab 100644
--- a/lib/compiler/test/receive_SUITE.erl
+++ b/lib/compiler/test/receive_SUITE.erl
@@ -188,7 +188,7 @@ ref_opt(Config) when is_list(Config) ->
 ref_opt_1(Config) ->
     ?line DataDir = ?config(data_dir, Config),
     ?line PrivDir = ?config(priv_dir, Config),
-    ?line Sources = filelib:wildcard(filename:join([DataDir,"ref_opt","*.erl"])),
+    Sources = filelib:wildcard(filename:join([DataDir,"ref_opt","*.{erl,S}"])),
     ?line test_lib:p_run(fun(Src) ->
 				 do_ref_opt(Src, PrivDir)
 			 end, Sources),
@@ -196,10 +196,15 @@ ref_opt_1(Config) ->
 
 do_ref_opt(Source, PrivDir) ->
     try
-	{ok,Mod} = c:c(Source, [{outdir,PrivDir}]),
+	Ext = filename:extension(Source),
+	{ok,Mod} = compile:file(Source, [report_errors,report_warnings,
+					 {outdir,PrivDir}] ++
+					[from_asm || Ext =:= ".S" ]),
+	Base = filename:rootname(filename:basename(Source), Ext),
+    code:purge(list_to_atom(Base)),
+    BeamFile = filename:join(PrivDir, Base),
+    code:load_abs(BeamFile),
 	ok = Mod:Mod(),
-	Base = filename:rootname(filename:basename(Source), ".erl"),
-	BeamFile = filename:join(PrivDir, Base),
 	{beam_file,Mod,_,_,_,Code} = beam_disasm:file(BeamFile),
 	case Base of
 	    "no_"++_ ->
diff --git a/lib/compiler/test/receive_SUITE_data/ref_opt/yes_14.S b/lib/compiler/test/receive_SUITE_data/ref_opt/yes_14.S
new file mode 100644
index 0000000000..fd14228135
--- /dev/null
+++ b/lib/compiler/test/receive_SUITE_data/ref_opt/yes_14.S
@@ -0,0 +1,71 @@
+{module, yes_14}.  %% version = 0
+
+{exports, [{f,2},{module_info,0},{module_info,1},{yes_14,0}]}.
+
+{attributes, []}.
+
+{labels, 12}.
+
+
+{function, yes_14, 0, 2}.
+  {label,1}.
+    {func_info,{atom,yes_14},{atom,yes_14},0}.
+  {label,2}.
+    {move,{atom,ok},{x,0}}.
+    return.
+
+
+{function, f, 2, 4}.
+  {label,3}.
+    {func_info,{atom,yes_14},{atom,f},2}.
+  {label,4}.
+    {allocate_heap,2,3,2}.
+    {move,{x,0},{y,1}}.
+    {put_tuple,2,{y,0}}.
+    {put,{atom,data}}.
+    {put,{x,1}}.
+    {call_ext,0,{extfunc,erlang,make_ref,0}}. % Ref in [x0]
+    {test_heap,4,1}.
+    {put_tuple,3,{x,1}}.
+    {put,{atom,request}}.
+    {put,{x,0}}.
+    {put,{y,0}}.
+    {move,{x,0},{y,0}}. % Ref in [x0,y0]
+    {move,{y,1},{x,0}}. % Ref in [y0]
+    {kill,{y,1}}.
+    send.
+    {move,{y,0},{x,0}}. % Ref in [x0,y0]
+    {move,{x,0},{y,1}}. % Ref in [x0,y0,y1]
+  {label,5}.
+    {loop_rec,{f,7},{x,0}}. % Ref in [y0,y1]
+    {test,is_tuple,{f,6},[{x,0}]}.
+    {test,test_arity,{f,6},[{x,0},2]}.
+    {get_tuple_element,{x,0},0,{x,1}}.
+    {get_tuple_element,{x,0},1,{x,2}}.
+    {test,is_eq_exact,{f,6},[{x,1},{atom,reply}]}.
+    {test,is_eq_exact,{f,6},[{x,2},{y,1}]}.
+    remove_message.
+    {move,{atom,ok},{x,0}}.
+    {deallocate,2}.
+    return.
+  {label,6}.
+    {loop_rec_end,{f,5}}.
+  {label,7}.
+    {wait,{f,5}}.
+
+
+{function, module_info, 0, 9}.
+  {label,8}.
+    {func_info,{atom,yes_14},{atom,module_info},0}.
+  {label,9}.
+    {move,{atom,yes_14},{x,0}}.
+    {call_ext_only,1,{extfunc,erlang,get_module_info,1}}.
+
+
+{function, module_info, 1, 11}.
+  {label,10}.
+    {func_info,{atom,yes_14},{atom,module_info},1}.
+  {label,11}.
+    {move,{x,0},{x,1}}.
+    {move,{atom,yes_14},{x,0}}.
+    {call_ext_only,2,{extfunc,erlang,get_module_info,2}}.