From 8aa46fd40d759de2d6a13fbafb5e88cdf1047220 Mon Sep 17 00:00:00 2001 From: Anthony Ramine Date: Tue, 9 Apr 2013 22:20:00 +0200 Subject: 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. --- lib/compiler/src/beam_receive.erl | 92 +++++++++++++++++---------------------- 1 file changed, 40 insertions(+), 52 deletions(-) (limited to 'lib/compiler/src') 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). -- cgit v1.2.3