beam_utils: Remove unused API functions

Remove the now unused beam_utils:is_not_used/3 and
beam_utils:is_killed/3 functions and friends.

Starting out as simple functions a long time ago, those functions have
grown and grown to support more optimizations. The number of bugs
found and fixed in beam_utils has also grown over time.

1 files changed, 4 insertions, 538 deletions

diff --git a/lib/compiler/src/beam_utils.erl b/lib/compiler/src/beam_utils.erl
index 5156a04f6b..6e6574c0b3 100644
--- a/lib/compiler/src/beam_utils.erl
+++ b/lib/compiler/src/beam_utils.erl
@@ -18,23 +18,14 @@
 %% %CopyrightEnd%
 %%
 %% Purpose : Common utilities used by several optimization passes.
-%% 
+%%
 
 -module(beam_utils).
--export([is_killed/3,is_killed_at/3,is_not_used/3,
-	 empty_label_index/0,index_label/3,index_labels/1,replace_labels/4,
-	 code_at/2,is_pure_test/1,
-	 split_even/1]).
+-export([replace_labels/4,is_pure_test/1,split_even/1]).
 
 -export_type([code_index/0,module_code/0,instruction/0]).
 
--import(lists, [map/2,member/2,sort/1,reverse/1]).
-
--define(is_const(Val), (Val =:= nil orelse
-                        element(1, Val) =:= integer orelse
-                        element(1, Val) =:= float orelse
-                        element(1, Val) =:= atom orelse
-                        element(1, Val) =:= literal)).
+-import(lists, [map/2,reverse/1]).
 
 %% instruction() describes all instructions that are used during optimization
 %% (from beam_a to beam_z).
@@ -52,97 +43,6 @@
 -type fail() :: beam_asm:fail() | 'fail'.
 -type test() :: {'test',atom(),fail(),[beam_asm:src()]} |
 		{'test',atom(),fail(),integer(),list(),beam_asm:reg()}.
--type result_cache() :: gb_trees:tree(beam_asm:label(), 'killed' | 'used').
-
--record(live,
-	{lbl :: code_index(),            %Label to code index.
-	 res :: result_cache()}).        %Result cache for each label.
-
-%% 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.
-
--spec is_killed(beam_asm:reg(), [instruction()], code_index()) -> boolean().
-
-is_killed(R, Is, D) ->
-    St = #live{lbl=D,res=gb_trees:empty()},
-    case check_liveness(R, Is, St) of
-	{killed,_} -> true;
-	{exit_not_used,_} -> false;
-	{_,_} -> false
-    end.
-
-%% is_killed_at(Reg, Lbl, State) -> true|false
-%%  Determine whether Reg is killed at label Lbl.
-
--spec is_killed_at(beam_asm:reg(), beam_asm:label(), code_index()) -> boolean().
-
-is_killed_at(R, Lbl, D) when is_integer(Lbl) ->
-    St0 = #live{lbl=D,res=gb_trees:empty()},
-    case check_liveness_at(R, Lbl, St0) of
-	{killed,_} -> true;
-	{exit_not_used,_} -> false;
-	{_,_} -> 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.
-
--spec is_not_used(beam_asm:reg(), [instruction()], code_index()) -> boolean().
-
-is_not_used(R, Is, D) ->
-    St = #live{lbl=D,res=gb_trees:empty()},
-    case check_liveness(R, Is, St) of
-	{used,_} -> false;
-	{exit_not_used,_} -> true;
-	{_,_} -> true
-    end.
-
-%% index_labels(FunctionIs) -> State
-%%  Index the instruction sequence so that we can quickly
-%%  look up the instruction following a specific label.
-
--spec index_labels([instruction()]) -> code_index().
-
-index_labels(Is) ->
-    index_labels_1(Is, []).
-
-%% empty_label_index() -> State
-%%  Create an empty label index.
-
--spec empty_label_index() -> code_index().
-
-empty_label_index() ->
-    gb_trees:empty().
-
-%% index_label(Label, [Instruction], State) -> State
-%%  Add an index for a label.
-
--spec index_label(beam_asm:label(), [instruction()], code_index()) ->
-   code_index().
-
-index_label(Lbl, Is0, Acc) ->
-    Is = drop_labels(Is0),
-    gb_trees:enter(Lbl, Is, Acc).
-
-
-%% code_at(Label, State) -> [I].
-%%  Retrieve the code at the given label.
-
--spec code_at(beam_asm:label(), code_index()) -> [instruction()].
-
-code_at(L, Ll) ->
-    gb_trees:get(L, Ll).
 
 %% replace_labels(FunctionIs, Tail, ReplaceDb, Fallback) -> FunctionIs.
 %%  Replace all labels in instructions according to the ReplaceDb.
@@ -175,7 +75,7 @@ is_pure_test({test,test_arity,_,[_,_]}) -> true;
 is_pure_test({test,has_map_fields,_,[_|_]}) -> true;
 is_pure_test({test,is_bitstr,_,[_]}) -> true;
 is_pure_test({test,is_function2,_,[_,_]}) -> true;
-is_pure_test({test,Op,_,Ops}) -> 
+is_pure_test({test,Op,_,Ops}) ->
     erl_internal:new_type_test(Op, length(Ops)).
 
 %% split_even/1
@@ -189,438 +89,6 @@ split_even(Rs) -> split_even(Rs, [], []).
 %%% Local functions.
 %%%
 
-
-%% check_liveness(Reg, [Instruction], #live{}) ->
-%%                      {killed | not_used | used, #live{}}
-%%  Find out whether Reg is used or killed in instruction sequence.
-%%
-%%    killed - Reg is assigned or killed by an allocation instruction.
-%%    not_used - the value of Reg is not used, but Reg must not be garbage
-%%    exit_not_used - the value of Reg is not used, but must not be garbage
-%%                    because the stack will be scanned because an
-%%                    exit BIF will raise an exception
-%%    used - Reg is used
-
-check_liveness({fr,_}, _, St) ->
-    %% Conservatively always consider the floating point register used.
-    {used,St};
-check_liveness(R, [{block,Blk}|Is], St0) ->
-    case check_liveness_block(R, Blk, St0) of
-	{transparent,St1} ->
-	    check_liveness(R, Is, St1);
-	{alloc_used,St1} ->
-            %% Used by an allocating instruction, but value not referenced.
-            %% Must check the rest of the instructions.
-	    not_used(check_liveness(R, Is, St1));
-	{Other,_}=Res when is_atom(Other) ->
-	    Res
-    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,St1} ->
-		    check_liveness(R, Is, St1);
-		{exit_not_used,St1} ->
-		    not_used(check_liveness(R, Is, St1));
-		{not_used,St1} ->
-		    not_used(check_liveness(R, Is, St1));
-		{used,_}=Used ->
-		    Used
-	    end
-    end;
-check_liveness(R, [{test,Op,Fail,Live,Ss,Dst}|Is], St) ->
-    %% Check this instruction as a block to get a less conservative
-    %% result if the caller is is_not_used/3.
-    Block = [{set,[Dst],Ss,{alloc,Live,{bif,Op,Fail}}}],
-    check_liveness(R, [{block,Block}|Is], St);
-check_liveness(R, [{select,_,R,_,_}|_], St) ->
-    {used,St};
-check_liveness(R, [{select,_,_,Fail,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_exit(R, Used, St);
-check_liveness(R, [{try_case_end,Used}|_], St) ->
-    check_liveness_exit(R, Used, St);
-check_liveness(R, [{badmatch,Used}|_], St) ->
-    check_liveness_exit(R, Used, St);
-check_liveness(R, [if_end|_], St) ->
-    check_liveness_exit(R, ignore, 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,_,_,none,Ss,Dst}|Is], St) ->
-    case member(R, Ss) of
-	true ->
-	    {used,St};
-	false ->
-	    if
-		R =:= Dst -> {killed,St};
-		true -> check_liveness(R, Is, St)
-	    end
-    end;
-check_liveness(R, [{bs_init,_,_,Live,Ss,Dst}|Is], St) ->
-    case R of
-	{x,X} ->
-            case member(R, Ss) of
-                true ->
-                    {used,St};
-                false ->
-                    if
-                        X < Live ->
-                            not_used(check_liveness(R, Is, St));
-                        true ->
-                            {killed,St}
-                    end
-	    end;
-	{y,_} ->
-	    case member(R, Ss) of
-		true -> {used,St};
-		false ->
-                    %% If the exception is taken, the stack may
-                    %% be scanned. Therefore the register is not
-                    %% guaranteed to be killed.
-		    if
-                        R =:= Dst -> {not_used,St};
-			true -> not_used(check_liveness(R, Is, St))
-		    end
-	    end
-    end;
-check_liveness(R, [{deallocate,_}|Is], St) ->
-    case R of
-	{y,_} -> {killed,St};
-	_ -> check_liveness(R, Is, St)
-    end;
-check_liveness({x,_}=R, [return|_], St) ->
-    case R of
-	{x,0} -> {used,St};
-	{x,_} -> {killed,St}
-    end;
-check_liveness(R, [{call,Live,_}|Is], St) ->
-    case R of
-	{x,X} when X < Live -> {used,St};
-	{x,_} -> {killed,St};
-	{y,_} -> not_used(check_liveness(R, Is, St))
-    end;
-check_liveness(R, [{call_ext,Live,_}=I|Is], St) ->
-    case R of
-	{x,X} when X < Live ->
-	    {used,St};
-	{x,_} ->
-	    {killed,St};
-	{y,_} ->
-	    case beam_jump:is_exit_instruction(I) of
-		false ->
-		    not_used(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.
-		    {exit_not_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,_} -> not_used(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,_} -> not_used(check_liveness(R, Is, St))
-    end;
-check_liveness(R, [{bif,Op,Fail,Ss,D}|Is], St) ->
-    Set = {set,[D],Ss,{bif,Op,Fail}},
-    check_liveness(R, [{block,[Set]}|Is], St);
-check_liveness(R, [{gc_bif,Op,{f,Fail},Live,Ss,D}|Is], St) ->
-    Set = {set,[D],Ss,{alloc,Live,{gc_bif,Op,Fail}}},
-    check_liveness(R, [{block,[Set]}|Is], St);
-check_liveness(R, [{bs_put,{f,0},_,Ss}|Is], St) ->
-    case member(R, Ss) 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};
-	{y,_} -> not_used(check_liveness(R, Is, St))
-    end;
-check_liveness(R, [{'catch'=Op,Y,Fail}|Is], St) ->
-    Set = {set,[Y],[],{try_catch,Op,Fail}},
-    check_liveness(R, [{block,[Set]}|Is], St);
-check_liveness(R, [{'try'=Op,Y,Fail}|Is], St) ->
-    Set = {set,[Y],[],{try_catch,Op,Fail}},
-    check_liveness(R, [{block,[Set]}|Is], St);
-check_liveness(R, [{try_end,Y}|Is], St) ->
-    case R of
-	Y ->
-	    {killed,St};
-	{y,_} ->
-	    %% y registers will be used if an exception occurs and
-	    %% control transfers to the label given in the previous
-	    %% try/2 instruction.
-	    {used,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, [{loop_rec,{f,_},{x,0}}|_], St) ->
-    case R of
-	{x,_} ->
-	    {killed,St};
-	_ ->
-	    %% y register. Rarely happens. Be very conversative and
-	    %% assume it's used.
-	    {used,St}
-    end;
-check_liveness(R, [{loop_rec_end,{f,Fail}}|_], St) ->
-    check_liveness_at(R, Fail, St);
-check_liveness(R, [{line,_}|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness(R, [{get_map_elements,{f,Fail},S,{list,L}}|Is], St0) ->
-    {Ss,Ds} = split_even(L),
-    case member(R, [S|Ss]) of
-	true ->
-	    {used,St0};
-	false ->
-	    case check_liveness_at(R, Fail, St0) of
-		{killed,St}=Killed ->
-		    case member(R, Ds) of
-			true -> Killed;
-			false -> check_liveness(R, Is, St)
-		    end;
-		Other ->
-		    Other
-	    end
-    end;
-check_liveness(R, [{put_map,F,Op,S,D,Live,{list,Puts}}|Is], St) ->
-    Set = {set,[D],[S|Puts],{alloc,Live,{put_map,Op,F}}},
-    check_liveness(R, [{block,[Set]}||Is], St);
-check_liveness(R, [{put_tuple,Ar,D}|Is], St) ->
-    Set = {set,[D],[],{put_tuple,Ar}},
-    check_liveness(R, [{block,[Set]}||Is], St);
-check_liveness(R, [{put_list,S1,S2,D}|Is], St) ->
-    Set = {set,[D],[S1,S2],put_list},
-    check_liveness(R, [{block,[Set]}||Is], St);
-check_liveness(R, [{test_heap,N,Live}|Is], St) ->
-    I = {block,[{set,[],[],{alloc,Live,{nozero,nostack,N,[]}}}]},
-    check_liveness(R, [I|Is], St);
-check_liveness(R, [{allocate_zero,N,Live}|Is], St) ->
-    I = {block,[{set,[],[],{alloc,Live,{zero,N,0,[]}}}]},
-    check_liveness(R, [I|Is], St);
-check_liveness(R, [{get_hd,S,D}|Is], St) ->
-    I = {block,[{set,[D],[S],get_hd}]},
-    check_liveness(R, [I|Is], St);
-check_liveness(R, [{get_tl,S,D}|Is], St) ->
-    I = {block,[{set,[D],[S],get_tl}]},
-    check_liveness(R, [I|Is], St);
-check_liveness(R, [remove_message|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness({x,X}, [build_stacktrace|_], St) when X > 0 ->
-    {killed,St};
-check_liveness(R, [{recv_mark,_}|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness(R, [{recv_set,_}|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness(R, [{'%',_}|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness(_R, Is, St) when is_list(Is) ->
-    %% Not implemented. Conservatively assume that the register is used.
-    {used,St}.
-
-check_liveness_everywhere(R, Lbls, St0) ->
-    check_liveness_everywhere_1(R, Lbls, killed, St0).
-
-check_liveness_everywhere_1(R, [{f,Lbl}|T], Res0, St0) ->
-    {Res1,St} = check_liveness_at(R, Lbl, St0),
-    Res = case Res1 of
-	      killed -> Res0;
-	      _ -> Res1
-	  end,
-    case Res of
-	used -> {used,St};
-	_ -> check_liveness_everywhere_1(R, T, Res, St)
-    end;
-check_liveness_everywhere_1(R, [_|T], Res, St) ->
-    check_liveness_everywhere_1(R, T, Res, St);
-check_liveness_everywhere_1(_, [], Res, St) ->
-    {Res,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 -> {used,St0}
-		       end,
-	    {Res,St#live{res=gb_trees:insert(Lbl, Res, St#live.res)}}
-    end.
-
-not_used({used,_}=Res) -> Res;
-not_used({_,St}) -> {not_used,St}.
-
-check_liveness_exit(R, R, St) -> {used,St};
-check_liveness_exit({x,_}, _, St) -> {killed,St};
-check_liveness_exit({y,_}, _, St) -> {exit_not_used,St}.
-
-%% check_liveness_block(Reg, [Instruction], State) ->
-%%     {killed | not_used | used | alloc_used | transparent,State'}
-%%  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
-%%    not_used - The value is not used, but the register is referenced
-%%       e.g. by an allocation instruction
-%%    transparent - Reg is neither used nor killed
-%%    alloc_used - Used only in an allocate instruction
-%%    used - Reg is explicitly used by an instruction
-%%
-%%  Annotations are not allowed.
-%%
-%%  (Unknown instructions will cause an exception.)
-
-check_liveness_block({x,X}=R, [{set,Ds,Ss,{alloc,Live,Op}}|Is], St0) ->
-    if 
-	X >= Live ->
-	    {killed,St0};
-	true ->
-	    case check_liveness_block_1(R, Ss, Ds, Op, Is, St0) of
-                {transparent,St} -> {alloc_used,St};
-		{_,_}=Res -> not_used(Res)
-	    end
-    end;
-check_liveness_block({y,_}=R, [{set,Ds,Ss,{alloc,_Live,Op}}|Is], St0) ->
-    case check_liveness_block_1(R, Ss, Ds, Op, Is, St0) of
-        {transparent,St} -> {alloc_used,St};
-        {_,_}=Res -> not_used(Res)
-    end;
-check_liveness_block({y,_}=R, [{set,Ds,Ss,{try_catch,_,Op}}|Is], St0) ->
-    case Ds of
-        [R] ->
-            {killed,St0};
-        _ ->
-            case check_liveness_block_1(R, Ss, Ds, Op, Is, St0) of
-                {exit_not_used,St} ->
-                    {used,St};
-                {transparent,St} ->
-                    %% Conservatively assumed that it is used.
-                    {used,St};
-                {_,_}=Res ->
-                    Res
-            end
-    end;
-check_liveness_block(R, [{set,Ds,Ss,Op}|Is], St) ->
-    check_liveness_block_1(R, Ss, Ds, Op, Is, St);
-check_liveness_block(_, [], St) -> {transparent,St}.
-
-check_liveness_block_1(R, Ss, Ds, Op, Is, St0) ->
-    case member(R, Ss) of
-	true ->
-	    {used,St0};
-	false ->
-	    case check_liveness_block_2(R, Op, Ss, St0) of
-		{killed,St} ->
-		    case member(R, Ds) of
-			true -> {killed,St};
-			false -> check_liveness_block(R, Is, St)
-		    end;
-		{exit_not_used,St} ->
-		    case member(R, Ds) of
-			true -> {exit_not_used,St};
-			false -> check_liveness_block(R, Is, St)
-		    end;
-		{not_used,St} ->
-		    not_used(case member(R, Ds) of
-				 true -> {killed,St};
-				 false -> check_liveness_block(R, Is, St)
-			     end);
-		{used,St} ->
-		    {used,St}
-	    end
-    end.
-
-check_liveness_block_2(R, {gc_bif,Op,{f,Lbl}}, Ss, St) ->
-    check_liveness_block_3(R, Lbl, {Op,length(Ss)}, St);
-check_liveness_block_2(R, {bif,Op,{f,Lbl}}, Ss, St) ->
-    Arity = length(Ss),
-    case erl_internal:comp_op(Op, Arity) orelse
-	erl_internal:new_type_test(Op, Arity) of
-	true ->
-	    {killed,St};
-	false ->
-	    check_liveness_block_3(R, Lbl, {Op,length(Ss)}, St)
-    end;
-check_liveness_block_2(R, {put_map,_Op,{f,Lbl}}, _Ss, St) ->
-    check_liveness_block_3(R, Lbl, {unsafe,0}, St);
-check_liveness_block_2(_, _, _, St) ->
-    {killed,St}.
-
-check_liveness_block_3({x,_}, 0, _FA, St) ->
-    {killed,St};
-check_liveness_block_3({y,_}, 0, {F,A}, St) ->
-    %% If the exception is thrown, the stack may be scanned,
-    %% thus implicitly using the y register.
-    case erl_bifs:is_safe(erlang, F, A) of
-        true -> {killed,St};
-        false -> {used,St}
-    end;
-check_liveness_block_3(R, Lbl, _FA, St0) ->
-    check_liveness_at(R, Lbl, St0).
-
-index_labels_1([{label,Lbl}|Is0], Acc) ->
-    Is = drop_labels(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)).
-
-drop_labels([{label,_}|Is]) -> drop_labels(Is);
-drop_labels(Is) -> Is.
-
-
 replace_labels_1([{test,Test,{f,Lbl},Ops}|Is], Acc, D, Fb) ->
     replace_labels_1(Is, [{test,Test,{f,label(Lbl, D, Fb)},Ops}|Acc], D, Fb);
 replace_labels_1([{test,Test,{f,Lbl},Live,Ops,Dst}|Is], Acc, D, Fb) ->
@@ -676,8 +144,6 @@ label(Old, D, Fb) ->
         _ -> Fb(Old)
     end.
 
-%% live_opt/4.
-
 split_even([], Ss, Ds) ->
     {reverse(Ss),reverse(Ds)};
 split_even([S,D|Rs], Ss, Ds) ->