%%
%% %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([{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}|Is], D,
	  [{get_tuple_element,_,_,{x,X}}=G|Acc])
  when X+1 =:= Live ->
    %% Move allocation instruction upwards past get_tuple_element
    %% instructions to give more opportunities for moving
    %% get_tuple_element instructions.
    I = {allocate_zero,N,X},
    reorder_1([I,G|Is], D, Acc);
reorder_1([I|Is], D, Acc) ->
    reorder_1(Is, D, [I|Acc]);
reorder_1([], _, Acc) -> reverse(Acc).