aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler/src/beam_utils.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/compiler/src/beam_utils.erl')
-rw-r--r--lib/compiler/src/beam_utils.erl290
1 files changed, 124 insertions, 166 deletions
diff --git a/lib/compiler/src/beam_utils.erl b/lib/compiler/src/beam_utils.erl
index 249d9395ca..ffeff9ea81 100644
--- a/lib/compiler/src/beam_utils.erl
+++ b/lib/compiler/src/beam_utils.erl
@@ -22,7 +22,7 @@
-module(beam_utils).
-export([is_killed_block/2,is_killed/3,is_killed_at/3,
- is_not_used/3,is_not_used_at/3,
+ is_not_used/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,
@@ -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,24 +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
- 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/3,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
@@ -240,15 +229,19 @@ split_even(Rs) -> split_even(Rs, [], []).
%% 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);
@@ -258,8 +251,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) ->
@@ -329,7 +326,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
@@ -340,7 +337,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
@@ -352,43 +349,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};
@@ -414,7 +388,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.
@@ -483,18 +457,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);
@@ -507,16 +472,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
@@ -530,56 +503,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
%%
@@ -587,45 +524,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),
@@ -812,6 +768,8 @@ live_opt_block([{set,Ds,Ss,Op}=I0|Is], Regs0, D, Acc) ->
_ ->
live_opt_block(Is, Regs, D, [I|Acc])
end;
+live_opt_block([{'%live',_,_}|Is], Regs, D, Acc) ->
+ live_opt_block(Is, Regs, D, Acc);
live_opt_block([], Regs, _, Acc) -> {Acc,Regs}.
live_join_labels([{f,L}|T], D, Regs0) when L =/= 0 ->
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-14 11:42:39 +0000