Merge branch 'master' into sverk/master/halt-INT_MIN

1 files changed, 139 insertions, 0 deletions

diff --git a/lib/compiler/src/beam_reorder.erl b/lib/compiler/src/beam_reorder.erl
new file mode 100644
index 0000000000..41586a7bf2
--- /dev/null
+++ b/lib/compiler/src/beam_reorder.erl
@@ -0,0 +1,139 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 1999-2013. All Rights Reserved.
+%%
+%% Licensed under the Apache License, Version 2.0 (the "License");
+%% you may not use this file except in compliance with the License.
+%% You may obtain a copy of the License at
+%%
+%%     http://www.apache.org/licenses/LICENSE-2.0
+%%
+%% Unless required by applicable law or agreed to in writing, software
+%% distributed under the License is distributed on an "AS IS" BASIS,
+%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%% See the License for the specific language governing permissions and
+%% limitations under the License.
+%%
+%% %CopyrightEnd%
+%%
+
+-module(beam_reorder).
+
+-export([module/2]).
+-import(lists, [member/2,reverse/1]).
+
+module({Mod,Exp,Attr,Fs0,Lc}, _Opt) ->
+    Fs = [function(F) || F <- Fs0],
+    {ok,{Mod,Exp,Attr,Fs,Lc}}.
+
+function({function,Name,Arity,CLabel,Is0}) ->
+    try
+	Is = reorder(Is0),
+	{function,Name,Arity,CLabel,Is}
+    catch
+	Class:Error ->
+	    Stack = erlang:get_stacktrace(),
+	    io:fwrite("Function: ~w/~w\n", [Name,Arity]),
+	    erlang:raise(Class, Error, Stack)
+    end.
+
+%% reorder(Instructions0) -> Instructions
+%%  Reorder instructions before the beam_block pass, because reordering
+%%  will be more cumbersome when the blocks are in place.
+%%
+%%  Execution of get_tuple_element instructions can be delayed until
+%%  they are actually needed. Consider the sequence:
+%%
+%%      get_tuple_element Tuple Pos Dst
+%%      test Test Fail Operands
+%%
+%%  If Dst is killed at label Fail (and not referenced in Operands),
+%%  we can can swap the instructions:
+%%
+%%      test Test Fail Operands
+%%      get_tuple_element Tuple Pos Dst
+%%
+%%  That can be beneficial in two ways: Firstly, if the branch is taken
+%%  we have avoided execution of the get_tuple_element instruction.
+%%  Secondly, even if the branch is not taken, subsequent optimization
+%%  (opt_blocks/1) may be able to change Dst to the final destination
+%%  register and eliminate a 'move' instruction.
+
+reorder(Is) ->
+    D = beam_utils:index_labels(Is),
+    reorder_1(Is, D, []).
+
+reorder_1([{Op,_,_}=TryCatch|[I|Is]=Is0], D, Acc)
+  when Op =:= 'catch'; Op =:= 'try' ->
+    %% Don't allow 'try' or 'catch' instructions to split blocks if
+    %% it can be avoided.
+    case is_safe(I) of
+	false ->
+	    reorder_1(Is0, D, [TryCatch|Acc]);
+	true ->
+	    reorder_1([TryCatch|Is], D, [I|Acc])
+    end;
+reorder_1([{label,L}=I|_], D, Acc) ->
+    Is = beam_utils:code_at(L, D),
+    reorder_1(Is, D, [I|Acc]);
+reorder_1([{test,is_nonempty_list,_,_}=I|Is], D, Acc) ->
+    %% The run-time system may combine the is_nonempty_list test with
+    %% the following get_list instruction.
+    reorder_1(Is, D, [I|Acc]);
+reorder_1([{test,_,_,_}=I,
+	   {select,_,_,_,_}=S|Is], D, Acc) ->
+    %% There is nothing to gain by inserting a get_tuple_element
+    %% instruction between the test instruction and the select
+    %% instruction.
+    reorder_1(Is, D, [S,I|Acc]);
+reorder_1([{test,_,{f,L},Ss}=I|Is0], D0,
+	  [{get_tuple_element,_,_,El}=G|Acc0]=Acc) ->
+    case member(El, Ss) of
+	true ->
+	    reorder_1(Is0, D0, [I|Acc]);
+	false ->
+	    case beam_utils:is_killed_at(El, L, D0) of
+		true ->
+		    Is = [I,G|Is0],
+		    reorder_1(Is, D0, Acc0);
+		false ->
+		    case beam_utils:is_killed(El, Is0, D0) of
+			true ->
+			    Code0 = beam_utils:code_at(L, D0),
+			    Code = [G|Code0],
+			    D = beam_utils:index_label(L, Code, D0),
+			    Is = [I|Is0],
+			    reorder_1(Is, D, Acc0);
+			false ->
+			    reorder_1(Is0, D0, [I|Acc])
+		    end
+	    end
+    end;
+reorder_1([{allocate_zero,N,Live}=I0|Is], D,
+	  [{get_tuple_element,{x,Tup},_,{x,Dst}}=G|Acc]=Acc0) ->
+    case Tup < Dst andalso Dst+1 =:= Live of
+	true ->
+	    %% Move allocation instruction upwards past
+	    %% get_tuple_element instructions to create more
+	    %% opportunities for moving get_tuple_element
+	    %% instructions.
+	    I = {allocate_zero,N,Dst},
+	    reorder_1([I,G|Is], D, Acc);
+	false ->
+	    reorder_1(Is, D, [I0|Acc0])
+    end;
+reorder_1([I|Is], D, Acc) ->
+    reorder_1(Is, D, [I|Acc]);
+reorder_1([], _, Acc) -> reverse(Acc).
+
+%% is_safe(Instruction) -> true|false
+%%  Test whether an instruction is safe (cannot cause an exception).
+
+is_safe({kill,_}) -> true;
+is_safe({move,_,_}) -> true;
+is_safe({put,_}) -> true;
+is_safe({put_list,_,_,_}) -> true;
+is_safe({put_tuple,_,_}) -> true;
+is_safe({test_heap,_,_}) -> true;
+is_safe(_) -> false.