From 84adefa331c4159d432d22840663c38f155cd4c1 Mon Sep 17 00:00:00 2001 From: Erlang/OTP Date: Fri, 20 Nov 2009 14:54:40 +0000 Subject: The R13B03 release. --- lib/compiler/src/beam_utils.erl | 858 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 858 insertions(+) create mode 100644 lib/compiler/src/beam_utils.erl (limited to 'lib/compiler/src/beam_utils.erl') diff --git a/lib/compiler/src/beam_utils.erl b/lib/compiler/src/beam_utils.erl new file mode 100644 index 0000000000..ac249e6672 --- /dev/null +++ b/lib/compiler/src/beam_utils.erl @@ -0,0 +1,858 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2007-2009. 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% +%% +%% Purpose : Common utilities used by several optimization passes. +%% + +-module(beam_utils). +-export([is_killed_block/2,is_killed/3,is_killed_at/3, + is_not_used/3,is_not_used_at/3, + empty_label_index/0,index_label/3,index_labels/1, + code_at/2,bif_to_test/3,is_pure_test/1, + live_opt/1,delete_live_annos/1,combine_heap_needs/2]). + +-import(lists, [member/2,sort/1,reverse/1]). + +-record(live, + {bl, %Block check fun. + lbl, %Label to code index. + res}). %Result cache for each label. + + +%% is_killed_block(Register, [Instruction]) -> true|false +%% Determine whether a register is killed by the instruction sequence inside +%% a block. +%% +%% If true is returned, it means that the register will not be +%% referenced in ANY way (not even indirectly by an allocate instruction); +%% i.e. it is OK to enter the instruction sequence with Register +%% containing garbage. + +is_killed_block(R, Is) -> + case check_killed_block(R, Is) of + killed -> true; + used -> false; + transparent -> false + end. + +%% is_killed(Register, [Instruction], State) -> true|false +%% Determine whether a register is killed by the instruction sequence. +%% If true is returned, it means that the register will not be +%% referenced in ANY way (not even indirectly by an allocate instruction); +%% i.e. it is OK to enter the instruction sequence with Register +%% containing garbage. +%% +%% The state (constructed by index_instructions/1) is used to allow us +%% to determine the kill state across branches. + +is_killed(R, Is, D) -> + St = #live{bl=fun check_killed_block/2,lbl=D,res=gb_trees:empty()}, + case check_liveness(R, Is, St) of + {killed,_} -> true; + {used,_} -> false; + {unknown,_} -> false + end. + +%% is_killed_at(Reg, Lbl, State) -> true|false +%% Determine whether Reg is killed at label Lbl. + +is_killed_at(R, Lbl, D) when is_integer(Lbl) -> + St0 = #live{bl=fun check_killed_block/2,lbl=D,res=gb_trees:empty()}, + case check_liveness_at(R, Lbl, St0) of + {killed,_} -> true; + {used,_} -> false; + {unknown,_} -> false + end. + +%% is_not_used(Register, [Instruction], State) -> true|false +%% Determine whether a register is never used in the instruction sequence +%% (it could still be referenced by an allocate instruction, meaning that +%% it MUST be initialized, but that its value does not matter). +%% The state is used to allow us to determine the usage state +%% across branches. + +is_not_used(R, Is, D) -> + St = #live{bl=fun check_used_block/2,lbl=D,res=gb_trees:empty()}, + case check_liveness(R, Is, St) of + {killed,_} -> true; + {used,_} -> false; + {unknown,_} -> false + end. + +%% is_not_used(Register, [Instruction], State) -> true|false +%% Determine whether a register is never used in the instruction sequence +%% (it could still be referenced by an allocate instruction, meaning that +%% it MUST be initialized, but that its value does not matter). +%% The state is used to allow us to determine the usage state +%% across branches. + +is_not_used_at(R, Lbl, D) -> + St = #live{bl=fun check_used_block/2,lbl=D,res=gb_trees:empty()}, + case check_liveness_at(R, Lbl, St) of + {killed,_} -> true; + {used,_} -> false; + {unknown,_} -> false + end. + +%% index_labels(FunctionIs) -> State +%% Index the instruction sequence so that we can quickly +%% look up the instruction following a specific label. + +index_labels(Is) -> + index_labels_1(Is, []). + +%% empty_label_index() -> State +%% Create an empty label index. + +empty_label_index() -> + gb_trees:empty(). + +%% index_label(Label, [Instruction], State) -> State +%% Add an index for a label. + +index_label(Lbl, Is0, Acc) -> + Is = lists:dropwhile(fun({label,_}) -> true; + (_) -> false end, Is0), + gb_trees:enter(Lbl, Is, Acc). + + +%% code_at(Label, State) -> [I]. +%% Retrieve the code at the given label. + +code_at(L, Ll) -> + case gb_trees:lookup(L, Ll) of + {value,Code} -> Code; + none -> none + end. + +%% bif_to_test(Bif, [Op], Fail) -> {test,Test,Fail,[Op]} +%% Convert a BIF to a test. Fail if not possible. + +bif_to_test(is_atom, [_]=Ops, Fail) -> {test,is_atom,Fail,Ops}; +bif_to_test(is_boolean, [_]=Ops, Fail) -> {test,is_boolean,Fail,Ops}; +bif_to_test(is_binary, [_]=Ops, Fail) -> {test,is_binary,Fail,Ops}; +bif_to_test(is_bitstring,[_]=Ops, Fail) -> {test,is_bitstr,Fail,Ops}; +bif_to_test(is_float, [_]=Ops, Fail) -> {test,is_float,Fail,Ops}; +bif_to_test(is_function, [_]=Ops, Fail) -> {test,is_function,Fail,Ops}; +bif_to_test(is_function, [_,_]=Ops, Fail) -> {test,is_function2,Fail,Ops}; +bif_to_test(is_integer, [_]=Ops, Fail) -> {test,is_integer,Fail,Ops}; +bif_to_test(is_list, [_]=Ops, Fail) -> {test,is_list,Fail,Ops}; +bif_to_test(is_number, [_]=Ops, Fail) -> {test,is_number,Fail,Ops}; +bif_to_test(is_pid, [_]=Ops, Fail) -> {test,is_pid,Fail,Ops}; +bif_to_test(is_port, [_]=Ops, Fail) -> {test,is_port,Fail,Ops}; +bif_to_test(is_reference, [_]=Ops, Fail) -> {test,is_reference,Fail,Ops}; +bif_to_test(is_tuple, [_]=Ops, Fail) -> {test,is_tuple,Fail,Ops}; +bif_to_test('=<', [A,B], Fail) -> {test,is_ge,Fail,[B,A]}; +bif_to_test('>', [A,B], Fail) -> {test,is_lt,Fail,[B,A]}; +bif_to_test('<', [_,_]=Ops, Fail) -> {test,is_lt,Fail,Ops}; +bif_to_test('>=', [_,_]=Ops, Fail) -> {test,is_ge,Fail,Ops}; +bif_to_test('==', [A,[]], Fail) -> {test,is_nil,Fail,[A]}; +bif_to_test('==', [_,_]=Ops, Fail) -> {test,is_eq,Fail,Ops}; +bif_to_test('/=', [_,_]=Ops, Fail) -> {test,is_ne,Fail,Ops}; +bif_to_test('=:=', [A,[]], Fail) -> {test,is_nil,Fail,[A]}; +bif_to_test('=:=', [_,_]=Ops, Fail) -> {test,is_eq_exact,Fail,Ops}; +bif_to_test('=/=', [_,_]=Ops, Fail) -> {test,is_ne_exact,Fail,Ops}; +bif_to_test(is_record, [_,_,_]=Ops, Fail) -> {test,is_record,Fail,Ops}. + + +%% is_pure_test({test,Op,Fail,Ops}) -> true|false. +%% Return 'true' if the test instruction does not modify any +%% registers and/or bit syntax matching state, nor modifies +%% any bit syntax matching state. +%% +is_pure_test({test,is_eq,_,[_,_]}) -> true; +is_pure_test({test,is_ne,_,[_,_]}) -> true; +is_pure_test({test,is_eq_exact,_,[_,_]}) -> true; +is_pure_test({test,is_ne_exact,_,[_,_]}) -> true; +is_pure_test({test,is_ge,_,[_,_]}) -> true; +is_pure_test({test,is_lt,_,[_,_]}) -> true; +is_pure_test({test,is_nil,_,[_]}) -> true; +is_pure_test({test,is_nonempty_list,_,[_]}) -> true; +is_pure_test({test,test_arity,_,[_,_]}) -> true; +is_pure_test({test,Op,_,Ops}) -> + erl_internal:new_type_test(Op, length(Ops)). + + +%% live_opt([Instruction]) -> [Instruction]. +%% Go through the instruction sequence in reverse execution +%% order, keep track of liveness and remove 'move' instructions +%% whose destination is a register that will not be used. +%% Also insert {'%live',Live} annotations at the beginning +%% and end of each block. +%% +live_opt([{label,Fail}=I1, + {func_info,_,_,Live}=I2|Is]) -> + D = gb_trees:insert(Fail, live_call(Live), gb_trees:empty()), + [I1,I2|live_opt(reverse(Is), 0, D, [])]. + + +%% delete_live_annos([Instruction]) -> [Instruction]. +%% Delete all live annotations. +%% +delete_live_annos([{block,Bl0}|Is]) -> + case delete_live_annos(Bl0) of + [] -> delete_live_annos(Is); + [_|_]=Bl -> [{block,Bl}|delete_live_annos(Is)] + end; +delete_live_annos([{'%live',_}|Is]) -> + delete_live_annos(Is); +delete_live_annos([I|Is]) -> + [I|delete_live_annos(Is)]; +delete_live_annos([]) -> []. + +%% combine_heap_needs(HeapNeed1, HeapNeed2) -> HeapNeed +%% Combine the heap need for two allocation instructions. + +combine_heap_needs({alloc,Alloc1}, {alloc,Alloc2}) -> + {alloc,combine_alloc_lists(Alloc1, Alloc2)}; +combine_heap_needs({alloc,Alloc}, Words) when is_integer(Words) -> + {alloc,combine_alloc_lists(Alloc, [{words,Words}])}; +combine_heap_needs(Words, {alloc,Alloc}) when is_integer(Words) -> + {alloc,combine_alloc_lists(Alloc, [{words,Words}])}; +combine_heap_needs(H1, H2) when is_integer(H1), is_integer(H2) -> + H1+H2. + +%%% +%%% Local functions. +%%% + + +%% check_liveness(Reg, [Instruction], {State,BlockCheckFun}) -> +%% {killed | used | unknown,UpdateState} +%% Finds out how Reg is used in the instruction sequence. Returns one of: +%% killed - Reg is assigned a new value or killed by an allocation instruction +%% used - Reg is used (or possibly referenced by an allocation instruction) +%% unknown - not possible to determine (perhaps because of an instruction +%% that we don't recognize) + +check_liveness(R, [{set,_,_,_}=I|_], St) -> + erlang:error(only_allowed_in_blocks, [R,I,St]); +check_liveness(R, [{block,Blk}|Is], #live{bl=BlockCheck}=St) -> + case BlockCheck(R, Blk) of + transparent -> check_liveness(R, Is, St); + Other when is_atom(Other) -> {Other,St} + end; +check_liveness(R, [{label,_}|Is], St) -> + check_liveness(R, Is, St); +check_liveness(R, [{test,_,{f,Fail},As}|Is], St0) -> + case member(R, As) of + true -> + {used,St0}; + false -> + case check_liveness_at(R, Fail, St0) of + {killed,St} -> check_liveness(R, Is, St); + {_,_}=Other -> Other + end + end; +check_liveness(R, [{test,_,{f,Fail},Live,Ss,_}|Is], St0) -> + case R of + {x,X} -> + case X < Live orelse member(R, Ss) of + true -> {used,St0}; + false -> check_liveness_at(R, Fail, St0) + end; + {y,_} -> + case check_liveness_at(R, Fail, St0) of + {killed,St} -> check_liveness(R, Is, St); + {_,_}=Other -> Other + end + end; +check_liveness(R, [{select_val,R,_,_}|_], St) -> + {used,St}; +check_liveness(R, [{select_val,_,Fail,{list,Branches}}|_], St) -> + check_liveness_everywhere(R, [Fail|Branches], St); +check_liveness(R, [{select_tuple_arity,R,_,_}|_], St) -> + {used,St}; +check_liveness(R, [{select_tuple_arity,_,Fail,{list,Branches}}|_], St) -> + check_liveness_everywhere(R, [Fail|Branches], St); +check_liveness(R, [{jump,{f,F}}|_], St) -> + check_liveness_at(R, F, St); +check_liveness(R, [{case_end,Used}|_], St) -> + check_liveness_ret(R, Used, St); +check_liveness(R, [{badmatch,Used}|_], St) -> + check_liveness_ret(R, Used, St); +check_liveness(_, [if_end|_], St) -> + {killed,St}; +check_liveness(R, [{func_info,_,_,Ar}|_], St) -> + case R of + {x,X} when X < Ar -> {used,St}; + _ -> {killed,St} + end; +check_liveness(R, [{kill,R}|_], St) -> + {killed,St}; +check_liveness(R, [{kill,_}|Is], St) -> + check_liveness(R, Is, St); +check_liveness(R, [bs_init_writable|Is], St) -> + if + R =:= {x,0} -> {used,St}; + true -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_private_append,_,Bits,_,Bin,_,Dst}|Is], St) -> + case R of + Bits -> {used,St}; + Bin -> {used,St}; + Dst -> {killed,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_append,_,Bits,_,_,_,Bin,_,Dst}|Is], St) -> + case R of + Bits -> {used,St}; + Bin -> {used,St}; + Dst -> {killed,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_init2,_,_,_,_,_,Dst}|Is], St) -> + if + R =:= Dst -> {killed,St}; + true -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_init_bits,_,_,_,_,_,Dst}|Is], St) -> + if + R =:= Dst -> {killed,St}; + true -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_put_string,_,_}|Is], St) -> + check_liveness(R, Is, St); +check_liveness(R, [{deallocate,_}|Is], St) -> + case R of + {y,_} -> {killed,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [return|_], St) -> + check_liveness_live_ret(R, 1, St); +check_liveness(R, [{call_last,Live,_,_}|_], St) -> + check_liveness_live_ret(R, Live, St); +check_liveness(R, [{call_only,Live,_}|_], St) -> + check_liveness_live_ret(R, Live, St); +check_liveness(R, [{call_ext_last,Live,_,_}|_], St) -> + check_liveness_live_ret(R, Live, St); +check_liveness(R, [{call_ext_only,Live,_}|_], St) -> + check_liveness_live_ret(R, Live, St); +check_liveness(R, [{call,Live,_}|Is], St) -> + case R of + {x,X} when X < Live -> {used,St}; + {x,_} -> {killed,St}; + {y,_} -> check_liveness(R, Is, St) + end; +check_liveness(R, [{call_ext,Live,Func}|Is], St) -> + case R of + {x,X} when X < Live -> + {used,St}; + {x,_} -> + {killed,St}; + {y,_} -> + {extfunc,Mod,Name,Arity} = Func, + case erl_bifs:is_exit_bif(Mod, Name, Arity) of + false -> + check_liveness(R, Is, St); + true -> + %% We must make sure we don't check beyond this instruction + %% or we will fall through into random unrelated code and + %% get stuck in a loop. + %% + %% We don't want to overwrite a 'catch', so consider this + %% register in use. + %% + {used,St} + end + end; +check_liveness(R, [{call_fun,Live}|Is], St) -> + case R of + {x,X} when X =< Live -> {used,St}; + {x,_} -> {killed,St}; + {y,_} -> check_liveness(R, Is, St) + end; +check_liveness(R, [{apply,Args}|Is], St) -> + case R of + {x,X} when X < Args+2 -> {used,St}; + {x,_} -> {killed,St}; + {y,_} -> check_liveness(R, Is, St) + end; +check_liveness(R, [{apply_last,Args,_}|_], St) -> + check_liveness_live_ret(R, Args+2, St); +check_liveness(R, [send|Is], St) -> + case R of + {x,X} when X < 2 -> {used,St}; + {x,_} -> {killed,St}; + {y,_} -> check_liveness(R, Is, St) + end; +check_liveness({x,R}, [{'%live',Live}|Is], St) -> + if + R < Live -> check_liveness(R, Is, St); + true -> {killed,St} + end; +check_liveness(R, [{bif,Op,{f,Fail},Ss,D}|Is], St0) -> + case check_liveness_fail(R, Op, Ss, Fail, St0) of + {killed,St} = Killed -> + case member(R, Ss) of + true -> {used,St}; + false when R =:= D -> Killed; + false -> check_liveness(R, Is, St) + end; + Other -> + Other + end; +check_liveness(R, [{gc_bif,Op,{f,Fail},_,Ss,D}|Is], St0) -> + case check_liveness_fail(R, Op, Ss, Fail, St0) of + {killed,St} = Killed -> + case member(R, Ss) of + true -> {used,St}; + false when R =:= D -> Killed; + false -> check_liveness(R, Is, St) + end; + Other -> + Other + end; +check_liveness(R, [{bs_add,{f,0},Ss,D}|Is], St) -> + case member(R, Ss) of + true -> {used,St}; + false when R =:= D -> {killed,St}; + false -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_bits_to_bytes2,Src,Dst}|Is], St) -> + case R of + Src -> {used,St}; + Dst -> {killed,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_put_binary,{f,0},Sz,_,_,Src}|Is], St) -> + case member(R, [Sz,Src]) of + true -> {used,St}; + false -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_put_integer,{f,0},Sz,_,_,Src}|Is], St) -> + case member(R, [Sz,Src]) of + true -> {used,St}; + false -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_put_float,{f,0},Sz,_,_,Src}|Is], St) -> + case member(R, [Sz,Src]) of + true -> {used,St}; + false -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_restore2,S,_}|Is], St) -> + case R of + S -> {used,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_save2,S,_}|Is], St) -> + case R of + S -> {used,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{move,S,D}|Is], St) -> + case R of + S -> {used,St}; + D -> {killed,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{make_fun2,_,_,_,NumFree}|Is], St) -> + case R of + {x,X} when X < NumFree -> {used,St}; + {x,_} -> {killed,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{try_end,Y}|Is], St) -> + case R of + Y -> {killed,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{catch_end,Y}|Is], St) -> + case R of + Y -> {killed,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{get_tuple_element,S,_,D}|Is], St) -> + case R of + S -> {used,St}; + D -> {killed,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{bs_context_to_binary,S}|Is], St) -> + case R of + S -> {used,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{loop_rec,{f,_},{x,0}}|Is], St) -> + case R of + {x,_} -> {killed,St}; + _ -> check_liveness(R, Is, St) + end; +check_liveness(R, [{loop_rec_end,{f,Fail}}|_], St) -> + check_liveness_at(R, Fail, St); +check_liveness(_R, Is, St) when is_list(Is) -> +%% case Is of +%% [I|_] -> +%% io:format("~p ~p\n", [_R,I]); +%% _ -> ok +%% end, + {unknown,St}. + +check_liveness_everywhere(R, [{f,Lbl}|T], St0) -> + case check_liveness_at(R, Lbl, St0) of + {killed,St} -> check_liveness_everywhere(R, T, St); + {_,_}=Other -> Other + end; +check_liveness_everywhere(R, [_|T], St) -> + check_liveness_everywhere(R, T, St); +check_liveness_everywhere(_, [], St) -> + {killed,St}. + +check_liveness_at(R, Lbl, #live{lbl=Ll,res=ResMemorized}=St0) -> + case gb_trees:lookup(Lbl, ResMemorized) of + {value,Res} -> + {Res,St0}; + none -> + {Res,St} = case gb_trees:lookup(Lbl, Ll) of + {value,Is} -> check_liveness(R, Is, St0); + none -> {unknown,St0} + end, + {Res,St#live{res=gb_trees:insert(Lbl, Res, St#live.res)}} + end. + +check_liveness_ret(R, R, St) -> {used,St}; +check_liveness_ret(_, _, St) -> {killed,St}. + +check_liveness_live_ret({x,R}, Live, St) -> + if + R < Live -> {used,St}; + true -> {killed,St} + end; +check_liveness_live_ret({y,_}, _, St) -> + {killed,St}. + +check_liveness_fail(_, _, _, 0, St) -> + {killed,St}; +check_liveness_fail(R, Op, Args, Fail, St) -> + Arity = length(Args), + case erl_internal:comp_op(Op, Arity) orelse + erl_internal:new_type_test(Op, Arity) of + true -> {killed,St}; + false -> check_liveness_at(R, Fail, St) + end. + +%% check_killed_block(Reg, [Instruction], State) -> killed | transparent | used +%% Finds out how Reg is used in the instruction sequence inside a block. +%% Returns one of: +%% killed - Reg is assigned a new value or killed by an allocation instruction +%% transparent - Reg is neither used nor killed +%% used - Reg is used or referenced by an allocation instruction. +%% +%% (Unknown instructions will cause an exception.) + +check_killed_block({x,X}, [{set,_,_,{alloc,Live,_}}|_]) -> + if + X >= Live -> killed; + true -> used + end; +check_killed_block(R, [{set,Ds,Ss,_Op}|Is]) -> + case member(R, Ss) of + true -> used; + false -> + case member(R, Ds) of + true -> killed; + false -> check_killed_block(R, Is) + end + end; +check_killed_block(R, [{'%live',Live}|Is]) -> + case R of + {x,X} when X >= Live -> killed; + _ -> check_killed_block(R, Is) + end; +check_killed_block(_, []) -> transparent. + +%% check_used_block(Reg, [Instruction], State) -> killed | transparent | used +%% Finds out how Reg is used in the instruction sequence inside a block. +%% Returns one of: +%% killed - Reg is assigned a new value or killed by an allocation instruction +%% transparent - Reg is neither used nor killed +%% used - Reg is explicitly used by an instruction +%% +%% (Unknown instructions will cause an exception.) + +check_used_block({x,X}=R, [{set,_,_,{alloc,Live,_}}|Is]) -> + if + X >= Live -> killed; + true -> check_used_block(R, Is) + end; +check_used_block(R, [{set,Ds,Ss,_Op}|Is]) -> + case member(R, Ss) of + true -> used; + false -> + case member(R, Ds) of + true -> killed; + false -> check_used_block(R, Is) + end + end; +check_used_block(R, [{'%live',Live}|Is]) -> + case R of + {x,X} when X >= Live -> killed; + _ -> check_used_block(R, Is) + end; +check_used_block(_, []) -> transparent. + +index_labels_1([{label,Lbl}|Is0], Acc) -> + Is = lists:dropwhile(fun({label,_}) -> true; + (_) -> false end, Is0), + index_labels_1(Is0, [{Lbl,Is}|Acc]); +index_labels_1([_|Is], Acc) -> + index_labels_1(Is, Acc); +index_labels_1([], Acc) -> gb_trees:from_orddict(sort(Acc)). + +%% Help functions for combine_heap_needs. + +combine_alloc_lists(Al1, Al2) -> + combine_alloc_lists_1(sort(Al1++Al2)). + +combine_alloc_lists_1([{words,W1},{words,W2}|T]) + when is_integer(W1), is_integer(W2) -> + [{words,W1+W2}|combine_alloc_lists_1(T)]; +combine_alloc_lists_1([{floats,F1},{floats,F2}|T]) + when is_integer(F1), is_integer(F2) -> + [{floats,F1+F2}|combine_alloc_lists_1(T)]; +combine_alloc_lists_1([{words,_}=W|T]) -> + [W|combine_alloc_lists_1(T)]; +combine_alloc_lists_1([{floats,_}=F|T]) -> + [F|combine_alloc_lists_1(T)]; +combine_alloc_lists_1([]) -> []. + +%% live_opt/4. + +%% Bit syntax instructions. +live_opt([{bs_context_to_binary,Src}=I|Is], Regs0, D, Acc) -> + Regs = x_live([Src], Regs0), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_add,Fail,[Src1,Src2,_],Dst}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src1,Src2], x_dead([Dst], Regs0)), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_init2,Fail,_,_,Live,_,_}=I|Is], _, D, Acc) -> + Regs1 = live_call(Live), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_init_bits,Fail,Src1,_,Live,_,Src2}=I|Is], _, D, Acc) -> + Regs1 = live_call(Live), + Regs2 = x_live([Src1,Src2], Regs1), + Regs = live_join_label(Fail, D, Regs2), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_append,Fail,Src1,_,Live,_,Src2,_,Dst}=I|Is], _Regs0, D, Acc) -> + Regs1 = x_dead([Dst], x_live([Src1,Src2], live_call(Live))), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_private_append,Fail,Src1,_,Src2,_,Dst}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src1,Src2], x_dead([Dst], Regs0)), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_put_binary,Fail,Src1,_,_,Src2}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src1,Src2], Regs0), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_put_float,Fail,Src1,_,_,Src2}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src1,Src2], Regs0), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_put_integer,Fail,Src1,_,_,Src2}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src1,Src2], Regs0), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_put_utf8,Fail,_,Src}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src], Regs0), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_put_utf16,Fail,_,Src}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src], Regs0), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_put_utf32,Fail,_,Src}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src], Regs0), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_restore2,Src,_}=I|Is], Regs0, D, Acc) -> + Regs = x_live([Src], Regs0), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_save2,Src,_}=I|Is], Regs0, D, Acc) -> + Regs = x_live([Src], Regs0), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_utf8_size,Fail,Src,Dst}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src], x_dead([Dst], Regs0)), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{bs_utf16_size,Fail,Src,Dst}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src], x_dead([Dst], Regs0)), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{test,bs_start_match2,Fail,Live,[Src,_],_}=I|Is], _, D, Acc) -> + Regs0 = live_call(Live), + Regs1 = x_live([Src], Regs0), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); + +%% Other instructions. +live_opt([{block,Bl0}|Is], Regs0, D, Acc) -> + Live0 = {'%live',live_regs(Regs0)}, + {Bl,Regs} = live_opt_block(reverse(Bl0), Regs0, D, [Live0]), + Live = {'%live',live_regs(Regs)}, + live_opt(Is, Regs, D, [{block,[Live|Bl]}|Acc]); +live_opt([{label,L}=I|Is], Regs, D0, Acc) -> + D = gb_trees:insert(L, Regs, D0), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{jump,{f,L}}=I|Is], _, D, Acc) -> + Regs = gb_trees:get(L, D), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([return=I|Is], _, D, Acc) -> + live_opt(Is, 1, D, [I|Acc]); +live_opt([{catch_end,_}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(1), D, [I|Acc]); +live_opt([{badmatch,Src}=I|Is], _, D, Acc) -> + Regs = x_live([Src], 0), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{case_end,Src}=I|Is], _, D, Acc) -> + Regs = x_live([Src], 0), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([if_end=I|Is], _, D, Acc) -> + Regs = 0, + live_opt(Is, Regs, D, [I|Acc]); +live_opt([bs_init_writable=I|Is], _, D, Acc) -> + live_opt(Is, live_call(1), D, [I|Acc]); +live_opt([{call,Arity,_}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Arity), D, [I|Acc]); +live_opt([{call_ext,Arity,_}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Arity), D, [I|Acc]); +live_opt([{call_fun,Arity}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Arity+1), D, [I|Acc]); +live_opt([{call_last,Arity,_,_}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Arity), D, [I|Acc]); +live_opt([{call_ext_last,Arity,_,_}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Arity), D, [I|Acc]); +live_opt([{apply,Arity}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Arity+2), D, [I|Acc]); +live_opt([{apply_last,Arity,_}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Arity+2), D, [I|Acc]); +live_opt([{call_only,Arity,_}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Arity), D, [I|Acc]); +live_opt([{call_ext_only,Arity,_}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Arity), D, [I|Acc]); +live_opt([{make_fun2,_,_,_,Arity}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Arity), D, [I|Acc]); +live_opt([send=I|Is], _, D, Acc) -> + live_opt(Is, live_call(2), D, [I|Acc]); +live_opt([{test,_,Fail,Ss}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live(Ss, Regs0), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{test,_,Fail,Live,Ss,_}=I|Is], _, D, Acc) -> + Regs0 = live_call(Live), + Regs1 = x_live(Ss, Regs0), + Regs = live_join_label(Fail, D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{select_val,Src,Fail,{list,List}}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src], Regs0), + Regs = live_join_labels([Fail|List], D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{select_tuple_arity,Src,Fail,{list,List}}=I|Is], Regs0, D, Acc) -> + Regs1 = x_live([Src], Regs0), + Regs = live_join_labels([Fail|List], D, Regs1), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{'try',_,Fail}=I|Is], Regs0, D, Acc) -> + Regs = live_join_label(Fail, D, Regs0), + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{try_case,_}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(1), D, [I|Acc]); +live_opt([{loop_rec,_Fail,_Dst}=I|Is], _, D, Acc) -> + live_opt(Is, 0, D, [I|Acc]); +live_opt([timeout=I|Is], _, D, Acc) -> + live_opt(Is, 0, D, [I|Acc]); + +%% Transparent instructions - they neither use nor modify x registers. +live_opt([{bs_put_string,_,_}=I|Is], Regs, D, Acc) -> + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{deallocate,_}=I|Is], Regs, D, Acc) -> + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{kill,_}=I|Is], Regs, D, Acc) -> + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{try_case_end,_}=I|Is], Regs, D, Acc) -> + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{try_end,_}=I|Is], Regs, D, Acc) -> + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{loop_rec_end,_}=I|Is], Regs, D, Acc) -> + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{wait,_}=I|Is], Regs, D, Acc) -> + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{wait_timeout,_,{Tag,_}}=I|Is], Regs, D, Acc) when Tag =/= x -> + live_opt(Is, Regs, D, [I|Acc]); + +%% The following instructions can occur if the "compilation" has been +%% started from a .S file using the 'asm' option. +live_opt([{trim,_,_}=I|Is], Regs, D, Acc) -> + live_opt(Is, Regs, D, [I|Acc]); +live_opt([{allocate,_,Live}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Live), D, [I|Acc]); +live_opt([{allocate_heap,_,_,Live}=I|Is], _, D, Acc) -> + live_opt(Is, live_call(Live), D, [I|Acc]); + +live_opt([], _, _, Acc) -> Acc. + +live_opt_block([{set,[],[],{alloc,Live,_}}=I|Is], _, D, Acc) -> + live_opt_block(Is, live_call(Live), D, [I|Acc]); +live_opt_block([{set,Ds,Ss,Op}=I|Is], Regs0, D, Acc) -> + Regs = case Op of + {alloc,Live,_} -> live_call(Live); + _ -> x_live(Ss, x_dead(Ds, Regs0)) + end, + case Ds of + [{x,X}] -> + case (not is_live(X, Regs0)) andalso Op =:= move of + true -> + live_opt_block(Is, Regs0, D, Acc); + false -> + live_opt_block(Is, Regs, D, [I|Acc]) + end; + _ -> + live_opt_block(Is, Regs, D, [I|Acc]) + end; +live_opt_block([], Regs, _, Acc) -> {Acc,Regs}. + +live_join_labels([{f,L}|T], D, Regs0) when L =/= 0 -> + Regs = gb_trees:get(L, D) bor Regs0, + live_join_labels(T, D, Regs); +live_join_labels([_|T], D, Regs) -> + live_join_labels(T, D, Regs); +live_join_labels([], _, Regs) -> Regs. + +live_join_label({f,0}, _, Regs) -> + Regs; +live_join_label({f,L}, D, Regs) -> + gb_trees:get(L, D) bor Regs. + +live_call(Live) -> (1 bsl Live) - 1. + +live_regs(Regs) -> + live_regs_1(0, Regs). + +live_regs_1(N, 0) -> N; +live_regs_1(N, Regs) -> live_regs_1(N+1, Regs bsr 1). + +x_dead([{x,N}|Rs], Regs) -> x_dead(Rs, Regs band (bnot (1 bsl N))); +x_dead([_|Rs], Regs) -> x_dead(Rs, Regs); +x_dead([], Regs) -> Regs. + +x_live([{x,N}|Rs], Regs) -> x_live(Rs, Regs bor (1 bsl N)); +x_live([_|Rs], Regs) -> x_live(Rs, Regs); +x_live([], Regs) -> Regs. + +is_live(X, Regs) -> ((Regs bsr X) band 1) =:= 1. -- cgit v1.2.3