aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler/src
diff options
context:
space:
mode:
Diffstat (limited to 'lib/compiler/src')
-rw-r--r--lib/compiler/src/Makefile1
-rw-r--r--lib/compiler/src/beam_disasm.erl18
-rw-r--r--lib/compiler/src/beam_receive.erl388
-rw-r--r--lib/compiler/src/beam_validator.erl5
-rw-r--r--lib/compiler/src/compile.erl6
-rw-r--r--lib/compiler/src/compiler.app.src11
-rw-r--r--lib/compiler/src/genop.tab5
7 files changed, 424 insertions, 10 deletions
diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile
index 70ddd54145..0f6d2f6193 100644
--- a/lib/compiler/src/Makefile
+++ b/lib/compiler/src/Makefile
@@ -58,6 +58,7 @@ MODULES = \
beam_listing \
beam_opcodes \
beam_peep \
+ beam_receive \
beam_trim \
beam_type \
beam_utils \
diff --git a/lib/compiler/src/beam_disasm.erl b/lib/compiler/src/beam_disasm.erl
index c956f2f000..9571f817e3 100644
--- a/lib/compiler/src/beam_disasm.erl
+++ b/lib/compiler/src/beam_disasm.erl
@@ -1,19 +1,19 @@
%%
%% %CopyrightBegin%
-%%
-%% Copyright Ericsson AB 2000-2009. All Rights Reserved.
-%%
+%%
+%% Copyright Ericsson AB 2000-2010. All Rights Reserved.
+%%
%% The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved online at http://www.erlang.org/.
-%%
+%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
-%%
+%%
%% %CopyrightEnd%
%%=======================================================================
%% Notes:
@@ -1096,6 +1096,14 @@ resolve_inst({on_load,[]},_,_,_) ->
on_load;
%%
+%% R14A.
+%%
+resolve_inst({recv_mark,[Lbl]},_,_,_) ->
+ {recv_mark,Lbl};
+resolve_inst({recv_set,[Lbl]},_,_,_) ->
+ {recv_set,Lbl};
+
+%%
%% Catches instructions that are not yet handled.
%%
resolve_inst(X,_,_,_) -> ?exit({resolve_inst,X}).
diff --git a/lib/compiler/src/beam_receive.erl b/lib/compiler/src/beam_receive.erl
new file mode 100644
index 0000000000..9ed44ad5d7
--- /dev/null
+++ b/lib/compiler/src/beam_receive.erl
@@ -0,0 +1,388 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2010. All Rights Reserved.
+%%
+%% The contents of this file are subject to the Erlang Public License,
+%% Version 1.1, (the "License"); you may not use this file except in
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%%
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%%
+%% %CopyrightEnd%
+%%
+
+-module(beam_receive).
+-export([module/2]).
+-import(lists, [foldl/3,reverse/1,reverse/2]).
+
+%%%
+%%% In code such as:
+%%%
+%%% Ref = make_ref(), %Or erlang:monitor(process, Pid)
+%%% .
+%%% .
+%%% .
+%%% receive
+%%% {Ref,Reply} -> Reply
+%%% end.
+%%%
+%%% we know that none of the messages that exist in the message queue
+%%% before the call to make_ref/0 can be matched out in the receive
+%%% statement. Therefore we can avoid going through the entire message
+%%% queue if we introduce two new instructions (here written as
+%%% BIFs in pseudo-Erlang):
+%%%
+%%% recv_mark(SomeUniqInteger),
+%%% Ref = make_ref(),
+%%% .
+%%% .
+%%% .
+%%% recv_set(SomeUniqInteger),
+%%% receive
+%%% {Ref,Reply} -> Reply
+%%% end.
+%%%
+%%% The recv_mark/1 instruction will save the current position and
+%%% SomeUniqInteger in the process context. The recv_set
+%%% instruction will verify that SomeUniqInteger is still stored
+%%% in the process context. If it is, it will set the current pointer
+%%% for the message queue (the next message to be read out) to the
+%%% position that was saved by recv_mark/1.
+%%%
+%%% The remove_message instruction must be modified to invalidate
+%%% the information stored by the previous recv_mark/1, in case there
+%%% is another receive executed between the calls to recv_mark/1 and
+%%% recv_set/1.
+%%%
+%%% We use a reference to a label (i.e. a position in the loaded code)
+%%% as the SomeUniqInteger.
+%%%
+
+module({Mod,Exp,Attr,Fs0,Lc}, _Opts) ->
+ Fs = [function(F) || F <- Fs0],
+ Code = {Mod,Exp,Attr,Fs,Lc},
+ {ok,Code}.
+
+%%%
+%%% Local functions.
+%%%
+
+function({function,Name,Arity,Entry,Is}) ->
+ try
+ D = beam_utils:index_labels(Is),
+ {function,Name,Arity,Entry,opt(Is, D, [])}
+ catch
+ Class:Error ->
+ Stack = erlang:get_stacktrace(),
+ io:fwrite("Function: ~w/~w\n", [Name,Arity]),
+ erlang:raise(Class, Error, Stack)
+ end.
+
+opt([{call_ext,Arity,{extfunc,erlang,Name,Arity}}=I|Is0], D, Acc) ->
+ case creates_new_ref(Name, Arity) of
+ true ->
+ %% The call creates a brand new reference. Now
+ %% search for a receive statement in the same
+ %% function that will match against the reference.
+ case opt_recv(Is0, D) of
+ no ->
+ opt(Is0, D, [I|Acc]);
+ {yes,Is,Lbl} ->
+ opt(Is, D, [I,{recv_mark,{f,Lbl}}|Acc])
+ end;
+ false ->
+ opt(Is0, D, [I|Acc])
+ end;
+opt([I|Is], D, Acc) ->
+ opt(Is, D, [I|Acc]);
+opt([], _, Acc) ->
+ reverse(Acc).
+
+%% creates_new_ref(Name, Arity) -> true|false.
+%% Return 'true' if the BIF Name/Arity will create a new reference.
+creates_new_ref(monitor, 2) -> true;
+creates_new_ref(make_ref, 0) -> true;
+creates_new_ref(_, _) -> false.
+
+%% opt_recv([Instruction], LabelIndex) -> no|{yes,[Instruction]}
+%% Search for a receive statement that will only retrieve messages
+%% that contain the newly created reference (which is currently in {x,0}).
+opt_recv(Is, D) ->
+ R = regs_init_x0(),
+ L = gb_sets:empty(),
+ opt_recv(Is, D, R, L, []).
+
+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
+ %% 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
+ false ->
+ no;
+ true ->
+ RecvSet = {recv_set,{f,L}},
+ {yes,reverse(Acc, [RecvSet,Lbl,Loop|Is]),L}
+ end;
+ [] ->
+ no
+ end;
+opt_recv([I|Is], D, R0, L0, Acc) ->
+ {R,L} = opt_update_regs(I, R0, L0),
+ case regs_empty(R) of
+ true ->
+ %% The reference is no longer alive. There is no
+ %% point in continuing the search.
+ no;
+ false ->
+ opt_recv(Is, D, R, L, [I|Acc])
+ end.
+
+opt_update_regs({block,Bl}, R, L) ->
+ {opt_update_regs_bl(Bl, R),L};
+opt_update_regs({call,_,_}, R, L) ->
+ {regs_kill_not_live(0, R),L};
+opt_update_regs({call_ext,_,_}, R, L) ->
+ {regs_kill_not_live(0, R),L};
+opt_update_regs({call_fun,_}, R, L) ->
+ {regs_kill_not_live(0, R),L};
+opt_update_regs({kill,Y}, R, L) ->
+ {regs_kill([Y], R),L};
+opt_update_regs(send, R, L) ->
+ {regs_kill_not_live(0, R),L};
+opt_update_regs({'catch',_,{f,Lbl}}, R, L) ->
+ {R,gb_sets:add(Lbl, L)};
+opt_update_regs({catch_end,_}, R, L) ->
+ {R,L};
+opt_update_regs({label,Lbl}, R, L) ->
+ case gb_sets:is_member(Lbl, L) of
+ false ->
+ %% We can't allow arbitrary labels (since the receive
+ %% could be entered without first creating the reference).
+ {regs_init(),L};
+ true ->
+ %% A catch label for a previously seen catch instruction is OK.
+ {R,L}
+ end;
+opt_update_regs({try_end,_}, R, L) ->
+ {R,L};
+opt_update_regs(_I, _R, L) ->
+ %% Unrecognized instruction. Abort the search.
+ {regs_init(),L}.
+
+opt_update_regs_bl([{set,Ds,_,{alloc,Live,_}}|Is], Regs0) ->
+ Regs1 = regs_kill_not_live(Live, Regs0),
+ Regs = regs_kill(Ds, Regs1),
+ opt_update_regs_bl(Is, Regs);
+opt_update_regs_bl([{set,[Dst]=Ds,[Src],move}|Is], Regs0) ->
+ Regs1 = regs_kill(Ds, Regs0),
+ Regs = case regs_is_member(Src, Regs1) of
+ false -> Regs1;
+ true -> regs_add(Dst, Regs1)
+ end,
+ opt_update_regs_bl(Is, Regs);
+opt_update_regs_bl([{set,Ds,_,_}|Is], Regs0) ->
+ Regs = regs_kill(Ds, Regs0),
+ opt_update_regs_bl(Is, Regs);
+opt_update_regs_bl([], Regs) -> Regs.
+
+%% opt_ref_used([Instruction], RefRegister, 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'.
+%%
+%% Basically, we follow all possible paths through the receive statement.
+%% If all paths are safe, we return 'true'.
+%%
+%% 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,
+%% that path is safe (any messages that may be matched further down the
+%% path is guaranteed to contain the reference).
+%%
+%% Otherwise, if we hit a 'remove_message' instruction, we give up
+%% and return 'false' (the optimization is definitely unsafe). If
+%% we hit an unrecognized instruction, we also give up and return
+%% 'false' (the optimization may be unsafe).
+
+opt_ref_used(Is, RefReg, Fail, D) ->
+ Done = gb_sets:singleton(Fail),
+ Regs = regs_init_x0(),
+ try
+ opt_ref_used_1(Is, RefReg, D, Done, Regs),
+ true
+ catch
+ throw:not_used ->
+ false
+ end.
+
+%% 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) ->
+ 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
+ false ->
+ opt_ref_used_1(Is, RefReg, D, Done, Regs);
+ true ->
+ %% The instructions that follow (Is) can only be executed
+ %% if the message contains the same reference as in RefReg.
+ 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
+ false ->
+ opt_ref_used_at(Fail, RefReg, 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_tuple_arity,_,{f,Fail},{list,List}}|_], RefReg, D, Done, Regs) ->
+ Lbls = [F || {f,F} <- List] ++ [Fail],
+ opt_ref_used_in_all(Lbls, RefReg, D, Done, Regs);
+opt_ref_used_1([{select_val,_,{f,Fail},{list,List}}|_], RefReg, 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) ->
+ case gb_sets:is_member(Lbl, Done) of
+ true -> Done;
+ false -> opt_ref_used_1(Is, RefReg, D, Done, Regs)
+ end;
+opt_ref_used_1([{loop_rec_end,_}|_], _, _, Done, _) ->
+ Done;
+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.
+%% 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);
+opt_ref_used_in_all([], _, _, Done, _) -> Done.
+
+opt_ref_used_at(Fail, RefReg, 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),
+ gb_sets:add(Fail, Done)
+ end.
+
+opt_ref_used_bl([{set,[],[],remove_message}|_], _) ->
+ %% We have proved that a message that does not depend on the
+ %% reference can be matched out.
+ throw(not_used);
+opt_ref_used_bl([{set,Ds,Ss,_}|Is], Regs0) ->
+ case regs_all_members(Ss, Regs0) of
+ false ->
+ %% The destination registers may be assigned values that
+ %% are not dependent on the message being matched.
+ Regs = regs_kill(Ds, Regs0),
+ opt_ref_used_bl(Is, Regs);
+ true ->
+ %% All the sources depend on the message directly or
+ %% indirectly.
+ Regs = regs_add_list(Ds, Regs0),
+ opt_ref_used_bl(Is, Regs)
+ end;
+opt_ref_used_bl([], Regs) -> Regs.
+
+%%%
+%%% Functions for keeping track of a set of registers.
+%%%
+
+%% regs_init() -> RegisterSet
+%% Return an empty set of registers.
+
+regs_init() ->
+ {0,0}.
+
+%% regs_init_x0() -> RegisterSet
+%% Return a set that only contains the {x,0} register.
+
+regs_init_x0() ->
+ {1 bsl 0,0}.
+
+%% regs_empty(Register) -> true|false
+%% Test whether the register set is empty.
+
+regs_empty(R) ->
+ R =:= {0,0}.
+
+%% regs_kill_not_live(Live, RegisterSet) -> RegisterSet'
+%% Kill all registers indicated not live by Live.
+
+regs_kill_not_live(Live, {Xregs,Yregs}) ->
+ {Xregs band ((1 bsl Live)-1),Yregs}.
+
+%% regs_kill([Register], RegisterSet) -> RegisterSet'
+%% Kill all registers mentioned in the list of registers.
+
+regs_kill([{x,N}|Rs], {Xregs,Yregs}) ->
+ regs_kill(Rs, {Xregs band (bnot (1 bsl N)),Yregs});
+regs_kill([{y,N}|Rs], {Xregs,Yregs}) ->
+ regs_kill(Rs, {Xregs,Yregs band (bnot (1 bsl N))});
+regs_kill([{fr,_}|Rs], Regs) ->
+ regs_kill(Rs, Regs);
+regs_kill([], Regs) -> Regs.
+
+regs_add_list(List, Regs) ->
+ foldl(fun(R, A) -> regs_add(R, A) end, Regs, List).
+
+%% regs_add(Register, RegisterSet) -> RegisterSet'
+%% Add a new register to the set of registers.
+
+regs_add({x,N}, {Xregs,Yregs}) ->
+ {Xregs bor (1 bsl N),Yregs};
+regs_add({y,N}, {Xregs,Yregs}) ->
+ {Xregs,Yregs bor (1 bsl N)}.
+
+%% regs_all_members([Register], RegisterSet) -> true|false
+%% Test whether all of the registers are part of the register set.
+
+regs_all_members([R|Rs], Regs) ->
+ regs_is_member(R, Regs) andalso regs_all_members(Rs, Regs);
+regs_all_members([], _) -> true.
+
+%% regs_is_member(Register, RegisterSet) -> true|false
+%% Test whether Register is part of the register set.
+
+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/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index 1fd61831e0..34065cfdce 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -416,6 +416,11 @@ valfun_1({put,Src}, Vst) ->
valfun_1({put_string,Sz,_,Dst}, Vst0) when is_integer(Sz) ->
Vst = eat_heap(2*Sz, Vst0),
set_type_reg(cons, Dst, Vst);
+%% Instructions for optimization of selective receives.
+valfun_1({recv_mark,{f,Fail}}, Vst) when is_integer(Fail) ->
+ Vst;
+valfun_1({recv_set,{f,Fail}}, Vst) when is_integer(Fail) ->
+ Vst;
%% Misc.
valfun_1({'%live',Live}, Vst) ->
verify_live(Live, Vst),
diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl
index 5017fd2c23..3f250a6d5a 100644
--- a/lib/compiler/src/compile.erl
+++ b/lib/compiler/src/compile.erl
@@ -162,6 +162,10 @@ expand_opt(report, Os) ->
[report_errors,report_warnings|Os];
expand_opt(return, Os) ->
[return_errors,return_warnings|Os];
+expand_opt(r12, Os) ->
+ [no_recv_opt|Os];
+expand_opt(r13, Os) ->
+ [no_recv_opt|Os];
expand_opt({debug_info_key,_}=O, Os) ->
[encrypt_debug_info,O|Os];
expand_opt(no_float_opt, Os) ->
@@ -621,6 +625,8 @@ asm_passes() ->
{iff,dclean,{listing,"clean"}},
{unless,no_bsm_opt,{pass,beam_bsm}},
{iff,dbsm,{listing,"bsm"}},
+ {unless,no_recv_opt,{pass,beam_receive}},
+ {iff,drecv,{listing,"recv"}},
{unless,no_stack_trimming,{pass,beam_trim}},
{iff,dtrim,{listing,"trim"}},
{pass,beam_flatten}]},
diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src
index b0311365c4..4ac879c9a4 100644
--- a/lib/compiler/src/compiler.app.src
+++ b/lib/compiler/src/compiler.app.src
@@ -1,19 +1,19 @@
% This is an -*- erlang -*- file.
%% %CopyrightBegin%
-%%
-%% Copyright Ericsson AB 1997-2009. All Rights Reserved.
-%%
+%%
+%% Copyright Ericsson AB 1997-2010. All Rights Reserved.
+%%
%% The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved online at http://www.erlang.org/.
-%%
+%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
-%%
+%%
%% %CopyrightEnd%
{application, compiler,
@@ -33,6 +33,7 @@
beam_listing,
beam_opcodes,
beam_peep,
+ beam_receive,
beam_trim,
beam_type,
beam_utils,
diff --git a/lib/compiler/src/genop.tab b/lib/compiler/src/genop.tab
index 47e6e72402..b57508ea8e 100644
--- a/lib/compiler/src/genop.tab
+++ b/lib/compiler/src/genop.tab
@@ -274,3 +274,8 @@ BEAM_FORMAT_NUMBER=0
# R13B03
149: on_load/0
+
+# R14A
+
+150: recv_mark/1
+151: recv_set/1
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-05 05:48:56 +0000