Simplify beam_utils

When beam_utils was first written, it did not have the functions
for testing whether a register was not used. Those were added
later, in sort of a hacky way.

Also, is_killed*() and is_not_used*() for Y registers would
return the same answer. Fix that to make the API more consistent
(an Y register can only be killed by a deallocate/1 instruction).
We will need to change beam_trim to call beam_utils:is_not_used/3
instead of beam_utils:is_killed/3.

2 files changed, 125 insertions, 155 deletions

diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl
index a8dc6805bc..d40669083e 100644
--- a/lib/compiler/src/beam_trim.erl
+++ b/lib/compiler/src/beam_trim.erl
@@ -230,7 +230,7 @@ safe_labels([], Acc) -> gb_sets:from_list(Acc).
 
 frame_layout(Is, Kills, #st{safe=Safe,lbl=D}) ->
     N = frame_size(Is, Safe),
-    IsKilled = fun(R) -> beam_utils:is_killed(R, Is, D) end,
+    IsKilled = fun(R) -> beam_utils:is_not_used(R, Is, D) end,
     {N,frame_layout_1(Kills, 0, N, IsKilled, [])}.
 
 frame_layout_1([{kill,{y,Y}}=I|Ks], Y, N, IsKilled, Acc) ->
diff --git a/lib/compiler/src/beam_utils.erl b/lib/compiler/src/beam_utils.erl
index a15ecf633e..c91256f6bc 100644
--- a/lib/compiler/src/beam_utils.erl
+++ b/lib/compiler/src/beam_utils.erl
@@ -31,8 +31,7 @@
 -import(lists, [member/2,sort/1,reverse/1,splitwith/2]).
 
 -record(live,
-	{bl,					%Block check fun.
-	 lbl,					%Label to code index.
+	{lbl,					%Label to code index.
 	 res}).					%Result cache for each label.
 
 
@@ -45,12 +44,16 @@
 %%  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_block({x,X}, [{set,_,_,{alloc,Live,_}}|_]) ->
+    X >= Live;
+is_killed_block(R, [{set,Ds,Ss,_Op}|Is]) ->
+    not member(R, Ss) andalso (member(R, Ds) orelse is_killed_block(R, Is));
+is_killed_block(R, [{'%live',_,Regs}|Is]) ->
+    case R of
+	{x,X} when (Regs bsr X) band 1 =:= 0 -> true;
+	_ -> is_killed_block(R, Is)
+    end;
+is_killed_block(_, []) -> false.
 
 %% is_killed(Register, [Instruction], State) -> true|false
 %%  Determine whether a register is killed by the instruction sequence.
@@ -63,20 +66,20 @@ is_killed_block(R, Is) ->
 %%  to determine the kill state across branches.
 
 is_killed(R, Is, D) ->
-    St = #live{bl=check_killed_block_fun(),lbl=D,res=gb_trees:empty()},
+    St = #live{lbl=D,res=gb_trees:empty()},
     case check_liveness(R, Is, St) of
 	{killed,_} -> true;
-	{used,_} -> false
+	{_,_} -> 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=check_killed_block_fun(),lbl=D,res=gb_trees:empty()},
+    St0 = #live{lbl=D,res=gb_trees:empty()},
     case check_liveness_at(R, Lbl, St0) of
 	{killed,_} -> true;
-	{used,_} -> false
+	{_,_} -> false
     end.
 
 %% is_not_used(Register, [Instruction], State) -> true|false
@@ -87,10 +90,10 @@ is_killed_at(R, Lbl, D) when is_integer(Lbl) ->
 %%  across branches.
 
 is_not_used(R, Is, D) ->
-    St = #live{bl=fun check_used_block/3,lbl=D,res=gb_trees:empty()},
+    St = #live{lbl=D,res=gb_trees:empty()},
     case check_liveness(R, Is, St) of
-	{killed,_} -> true;
-	{used,_} -> false
+	{used,_} -> false;
+	{_,_} -> true
     end.
 
 %% is_not_used(Register, [Instruction], State) -> true|false
@@ -101,10 +104,10 @@ is_not_used(R, Is, D) ->
 %%  across branches.
 
 is_not_used_at(R, Lbl, D) ->
-    St = #live{bl=fun check_used_block/3,lbl=D,res=gb_trees:empty()},
+    St = #live{lbl=D,res=gb_trees:empty()},
     case check_liveness_at(R, Lbl, St) of
-	{killed,_} -> true;
-	{used,_} -> false
+	{used,_} -> false;
+	{_,_} -> true
     end.
 
 %% index_labels(FunctionIs) -> State
@@ -245,15 +248,19 @@ join_even([S|Ss], [D|Ds]) -> [S,D|join_even(Ss, Ds)].
 
 
 %% check_liveness(Reg, [Instruction], #live{}) ->
-%%                      {killed | used, #live{}}
+%%                      {killed | not_used | used, #live{}}
 %%  Find out whether Reg is used or killed in instruction sequence.
-%%  'killed' means that Reg is assigned a new value or killed by an
-%%  allocation instruction. 'used' means that Reg is used in some way.
+%%
+%%    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
+%%    used - Reg is used
 
-check_liveness(R, [{block,Blk}|Is], #live{bl=BlockCheck}=St0) ->
-    case BlockCheck(R, Blk, St0) of
-	{transparent,St} -> check_liveness(R, Is, St);
-	{Other,_}=Res when is_atom(Other) -> Res
+check_liveness(R, [{block,Blk}|Is], St0) ->
+    case check_liveness_block(R, Blk, St0) of
+	{transparent,St1} ->
+	    check_liveness(R, Is, St1);
+	{Other,_}=Res when is_atom(Other) ->
+	    Res
     end;
 check_liveness(R, [{label,_}|Is], St) ->
     check_liveness(R, Is, St);
@@ -263,8 +270,12 @@ check_liveness(R, [{test,_,{f,Fail},As}|Is], St0) ->
 	    {used,St0};
 	false ->
 	    case check_liveness_at(R, Fail, St0) of
-		{killed,St} -> check_liveness(R, Is, St);
-		{_,_}=Other -> Other
+		{killed,St1} ->
+		    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) ->
@@ -334,7 +345,7 @@ 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)
+	{y,_} -> not_used(check_liveness(R, Is, St))
     end;
 check_liveness(R, [{call_ext,Live,_}=I|Is], St) ->
     case R of
@@ -345,7 +356,7 @@ check_liveness(R, [{call_ext,Live,_}=I|Is], St) ->
 	{y,_} ->
 	    case beam_jump:is_exit_instruction(I) of
 		false ->
-		    check_liveness(R, Is, St);
+		    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
@@ -357,43 +368,20 @@ 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)
+	{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,_} -> check_liveness(R, Is, 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},Live,Ss,D}|Is], St0) ->
-    case R of
-	{x,X} when X >= Live ->
-	    {killed,St0};
-	{x,_} ->
-	    {used,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
-    end;
+	{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};
@@ -419,7 +407,7 @@ 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)
+	{y,_} -> not_used(check_liveness(R, Is, St))
     end;
 check_liveness({x,_}=R, [{'catch',_,_}|Is], St) ->
     %% All x registers will be killed if an exception occurs.
@@ -488,18 +476,9 @@ check_liveness(R, [{get_map_elements,{f,Fail},S,{list,L}}|Is], St0) ->
 		    Other
 	    end
     end;
-check_liveness(R, [{put_map,{f,_},_,Src,_D,Live,{list,_}}|_], St0) ->
-    case R of
-	Src ->
-	    {used,St0};
-	{x,X} when X < Live ->
-	    {used,St0};
-	{x,_} ->
-	    {killed,St0};
-	{y,_} ->
-	    %% Conservatively mark it as used.
-	    {used,St0}
-    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, [{test_heap,N,Live}|Is], St) ->
     I = {block,[{set,[],[],{alloc,Live,{nozero,nostack,N,[]}}}]},
     check_liveness(R, [I|Is], St);
@@ -512,16 +491,24 @@ check_liveness(R, [{get_list,S,D1,D2}|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, [{f,Lbl}|T], St0) ->
-    case check_liveness_at(R, Lbl, St0) of
-	{killed,St} -> check_liveness_everywhere(R, T, St);
-	{_,_}=Other -> Other
+
+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(R, [_|T], St) ->
-    check_liveness_everywhere(R, T, St);
-check_liveness_everywhere(_, [], St) ->
-    {killed,St}.
+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
@@ -535,56 +522,20 @@ check_liveness_at(R, Lbl, #live{lbl=Ll,res=ResMemorized}=St0) ->
 	    {Res,St#live{res=gb_trees:insert(Lbl, Res, St#live.res)}}
     end.
 
+not_used({killed,St}) -> {not_used,St};
+not_used({_,_}=Res) -> Res.
+
 check_liveness_ret(R, R, St) -> {used,St};
 check_liveness_ret(_, _, 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_fun() ->
-    fun(R, Is, St) -> {check_killed_block(R, Is),St} end.
-
-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',_,Regs}|Is]) ->
-    case R of
-	{x,X} when (Regs bsr X) band 1 =:= 0 -> killed;
-	_ -> check_killed_block(R, Is)
-    end;
-check_killed_block(_, []) -> transparent.
-
-%% check_used_block(Reg, [Instruction], State) -> killed | transparent | used
+%% check_liveness_block(Reg, [Instruction], State) ->
+%%     {killed | not_used | 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
+%%    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
 %%    used - Reg is explicitly used by an instruction
 %%
@@ -592,45 +543,64 @@ check_killed_block(_, []) -> transparent.
 %%
 %%  (Unknown instructions will cause an exception.)
 
-check_used_block({x,X}=R, [{set,Ds,Ss,{alloc,Live,Op}}|Is], St) ->
+check_liveness_block({x,X}=R, [{set,Ds,Ss,{alloc,Live,Op}}|Is], St0) ->
     if 
-	X >= Live -> {killed,St};
-	true -> check_used_block_1(R, Ss, Ds, Op, Is, St)
+	X >= Live ->
+	    {killed,St0};
+	true ->
+	    case check_liveness_block_1(R, Ss, Ds, Op, Is, St0) of
+		{killed,St} -> {not_used,St};
+		{transparent,St} -> {not_used,St};
+		{_,_}=Res -> Res
+	    end
     end;
-check_used_block(R, [{set,Ds,Ss,Op}|Is], St) ->
-    check_used_block_1(R, Ss, Ds, Op, Is, St);
-check_used_block(_, [], St) -> {transparent,St}.
+check_liveness_block({y,_}=R, [{set,Ds,Ss,{alloc,_Live,Op}}|Is], St) ->
+    check_liveness_block_1(R, Ss, Ds, Op, Is, St);
+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_used_block_1(R, Ss, Ds, Op, Is, St0) ->
+check_liveness_block_1(R, Ss, Ds, Op, Is, St0) ->
     case member(R, Ss) of
 	true ->
 	    {used,St0};
 	false ->
-	    case is_reg_used_at(R, Op, St0) of
-		{true,St} ->
-		    {used,St};
-		{false,St} ->
+	    case check_liveness_block_2(R, Op, Ss, St0) of
+		{killed,St} ->
 		    case member(R, Ds) of
 			true -> {killed,St};
-			false -> check_used_block(R, Is, St)
-		    end
+			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.
 
-is_reg_used_at(R, {gc_bif,_,{f,Lbl}}, St) ->
-    is_reg_used_at_1(R, Lbl, St);
-is_reg_used_at(R, {bif,_,{f,Lbl}}, St) ->
-    is_reg_used_at_1(R, Lbl, St);
-is_reg_used_at(_, _, St) ->
-    {false,St}.
+check_liveness_block_2(R, {gc_bif,_Op,{f,Lbl}}, _Ss, St) ->
+    check_liveness_block_3(R, Lbl, 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, St)
+    end;
+check_liveness_block_2(R, {put_map,_Op,{f,Lbl}}, _Ss, St) ->
+    check_liveness_block_3(R, Lbl, St);
+check_liveness_block_2(_, _, _, St) ->
+    {killed,St}.
 
-is_reg_used_at_1(_, 0, St) ->
-    {false,St};
-is_reg_used_at_1(R, Lbl, St0) ->
-    case check_liveness_at(R, Lbl, St0) of
-	{killed,St} -> {false,St};
-	{used,St} -> {true,St}
-    end.
+check_liveness_block_3(_, 0, St) ->
+    {killed,St};
+check_liveness_block_3(R, Lbl, St0) ->
+    check_liveness_at(R, Lbl, St0).
 
 index_labels_1([{label,Lbl}|Is0], Acc) ->
     Is = drop_labels(Is0),