%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 1999-2016. 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,_},[Src|_]}=I|Is], D,
	  [{get_tuple_element,Src,_,_}|_]=Acc) ->
    %% We want to avoid code that can confuse beam_validator such as:
    %%   is_tuple Fail Src
    %%   test_arity Fail Src Arity
    %%   is_map Fail Src
    %%   get_tuple_element Src Pos Dst
    %% Therefore, don't reorder the instructions in such cases.
    reorder_1(Is, D, [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.