aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2019-03-04 09:47:02 +0100
committerGitHub <[email protected]>2019-03-04 09:47:02 +0100
commit6316266ebb5578ce0c399a227e12f5f484ac7907 (patch)
tree86358cbe9dd76732730bda53751c3ef4d5b9a218 /lib/compiler
parent80a44304d2217079d623a7159a72cdc7366df239 (diff)
parent42603e488ba2d66857d3deff4c6ec4fa6befd833 (diff)
downloadotp-6316266ebb5578ce0c399a227e12f5f484ac7907.tar.gz
otp-6316266ebb5578ce0c399a227e12f5f484ac7907.tar.bz2
otp-6316266ebb5578ce0c399a227e12f5f484ac7907.zip
Merge pull request #2166 from bjorng/bjorn/compiler/fix-slow-beam_ssa_dead
Optimize the beam_ssa_dead sub pass
Diffstat (limited to 'lib/compiler')
-rw-r--r--lib/compiler/src/beam_ssa_dead.erl364
1 files changed, 201 insertions, 163 deletions
diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl
index 2cca9ebadf..bb43a550ae 100644
--- a/lib/compiler/src/beam_ssa_dead.erl
+++ b/lib/compiler/src/beam_ssa_dead.erl
@@ -27,7 +27,8 @@
-export([opt/1]).
-include("beam_ssa.hrl").
--import(lists, [append/1,last/1,member/2,takewhile/2,reverse/1]).
+-import(lists, [append/1,keymember/3,last/1,member/2,
+ takewhile/2,reverse/1]).
-type used_vars() :: #{beam_ssa:label():=ordsets:ordset(beam_ssa:var_name())}.
@@ -58,7 +59,7 @@ opt(Linear) ->
Blocks0 = maps:from_list(Linear),
St0 = #st{bs=Blocks0,us=Used,skippable=Skippable},
St = shortcut_opt(St0),
- #st{bs=Blocks} = combine_eqs(St),
+ #st{bs=Blocks} = combine_eqs(St#st{us=#{}}),
beam_ssa:linearize(Blocks).
%%%
@@ -87,13 +88,22 @@ shortcut_opt(#st{bs=Blocks}=St) ->
%% opportunities for optimizations compared to post order. (Based on
%% running scripts/diffable with both PO and RPO and looking at
%% the diff.)
+ %%
+ %% Unfortunately, processing the blocks in reverse post order
+ %% potentially makes the time complexity quadratic or even cubic if
+ %% the ordset of unset variables grows large, instead of
+ %% linear for post order processing. We try to still get reasonable
+ %% compilation times by optimizations that will keep the constant
+ %% factor as low as possible, and we try to avoid the cubic time
+ %% complexity by trying to keep the set of unset variables as small
+ %% as possible.
+
Ls = beam_ssa:rpo(Blocks),
- shortcut_opt(Ls, #{from=>0}, St).
+ shortcut_opt(Ls, #{}, St).
-shortcut_opt([L|Ls], Bs0, #st{bs=Blocks0}=St) ->
+shortcut_opt([L|Ls], Bs, #st{bs=Blocks0}=St) ->
#b_blk{is=Is,last=Last0} = Blk0 = get_block(L, St),
- Bs = Bs0#{from:=L},
- case shortcut_terminator(Last0, Is, Bs, St) of
+ case shortcut_terminator(Last0, Is, L, Bs, St) of
Last0 ->
%% No change. No need to update the block.
shortcut_opt(Ls, Bs, St);
@@ -107,17 +117,17 @@ shortcut_opt([L|Ls], Bs0, #st{bs=Blocks0}=St) ->
shortcut_opt([], _, St) -> St.
shortcut_terminator(#b_br{bool=#b_literal{val=true},succ=Succ0},
- _Is, Bs, St0) ->
+ _Is, From, Bs, St0) ->
St = St0#st{rel_op=none},
- shortcut(Succ0, Bs, St);
+ shortcut(Succ0, From, Bs, St);
shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br,
- Is, Bs, St0) ->
+ Is, From, Bs, St0) ->
St = St0#st{target=one_way},
RelOp = get_rel_op(Bool, Is),
SuccBs = bind_var(Bool, #b_literal{val=true}, Bs),
- BrSucc = shortcut(Succ0, SuccBs, St#st{rel_op=RelOp}),
+ BrSucc = shortcut(Succ0, From, SuccBs, St#st{rel_op=RelOp}),
FailBs = bind_var(Bool, #b_literal{val=false}, Bs),
- BrFail = shortcut(Fail0, FailBs, St#st{rel_op=invert_op(RelOp)}),
+ BrFail = shortcut(Fail0, From, FailBs, St#st{rel_op=invert_op(RelOp)}),
case {BrSucc,BrFail} of
{#b_br{bool=#b_literal{val=true},succ=Succ},
#b_br{bool=#b_literal{val=true},succ=Fail}}
@@ -128,25 +138,25 @@ shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br,
%% No change.
Br
end;
-shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, Bs, St) ->
- List = shortcut_switch(List0, Bool, Bs, St),
+shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, From, Bs, St) ->
+ List = shortcut_switch(List0, Bool, From, Bs, St),
beam_ssa:normalize(Sw#b_switch{list=List});
-shortcut_terminator(Last, _Is, _Bs, _St) ->
+shortcut_terminator(Last, _Is, _Bs, _From, _St) ->
Last.
-shortcut_switch([{Lit,L0}|T], Bool, Bs, St0) ->
+shortcut_switch([{Lit,L0}|T], Bool, From, Bs, St0) ->
RelOp = {'=:=',Bool,Lit},
St = St0#st{rel_op=RelOp},
#b_br{bool=#b_literal{val=true},succ=L} =
- shortcut(L0, bind_var(Bool, Lit, Bs), St#st{target=one_way}),
- [{Lit,L}|shortcut_switch(T, Bool, Bs, St0)];
-shortcut_switch([], _, _, _) -> [].
+ shortcut(L0, From, bind_var(Bool, Lit, Bs), St#st{target=one_way}),
+ [{Lit,L}|shortcut_switch(T, Bool, From, Bs, St0)];
+shortcut_switch([], _, _, _, _) -> [].
-shortcut(L, Bs, St) ->
- shortcut_1(L, Bs, ordsets:new(), St).
+shortcut(L, From, Bs, St) ->
+ shortcut_1(L, From, Bs, ordsets:new(), St).
-shortcut_1(L, Bs0, UnsetVars0, St) ->
- case shortcut_2(L, Bs0, UnsetVars0, St) of
+shortcut_1(L, From, Bs0, UnsetVars0, St) ->
+ case shortcut_2(L, From, Bs0, UnsetVars0, St) of
none ->
%% No more shortcuts found. Package up the previous
%% label in an unconditional branch.
@@ -156,13 +166,13 @@ shortcut_1(L, Bs0, UnsetVars0, St) ->
Br;
{#b_br{bool=#b_literal{val=true},succ=Succ},Bs,UnsetVars} ->
%% This is a safe `br`, but try to find a better one.
- shortcut_1(Succ, Bs#{from:=L}, UnsetVars, St)
+ shortcut_1(Succ, L, Bs, UnsetVars, St)
end.
%% Try to shortcut this block, branching to a successor.
-shortcut_2(L, Bs0, UnsetVars0, St) ->
+shortcut_2(L, From, Bs0, UnsetVars0, St) ->
#b_blk{is=Is,last=Last} = get_block(L, St),
- case eval_is(Is, Bs0, St) of
+ case eval_is(Is, From, Bs0, St) of
none ->
%% It is not safe to avoid this block because it
%% has instructions with potential side effects.
@@ -181,139 +191,147 @@ shortcut_2(L, Bs0, UnsetVars0, St) ->
%% We have a potentially suitable br.
%% Now update the set of variables that will never
%% be set if this block will be skipped.
- SetInThisBlock = [V || #b_set{dst=V} <- Is],
- UnsetVars = update_unset_vars(L, Br, SetInThisBlock,
- UnsetVars0, St),
-
- %% Continue checking whether this br is suitable.
- shortcut_3(Br, Bs#{from:=L}, UnsetVars, St)
+ case update_unset_vars(L, Is, Br, UnsetVars0, St) of
+ unsafe ->
+ %% It is unsafe to use this br,
+ %% because it refers to a variable defined
+ %% in this block.
+ shortcut_unsafe_br(Br, L, Bs, UnsetVars0, St);
+ UnsetVars ->
+ %% Continue checking whether this br is
+ %% suitable.
+ shortcut_test_br(Br, L, Bs, UnsetVars, St)
+ end
end
end.
-shortcut_3(Br, Bs, UnsetVars, #st{target=Target}=St) ->
+shortcut_test_br(Br, From, Bs, UnsetVars, St) ->
case is_br_safe(UnsetVars, Br, St) of
false ->
- %% Branching using this `br` is unsafe, either because it
- %% is an unconditional branch to a phi node, or because
- %% one or more of the variables that are not set will be
- %% used. Try to follow branches of this `br`, to find a
- %% safe `br`.
- case Br of
- #b_br{bool=#b_literal{val=true},succ=L} ->
- case Target of
- L ->
- %% We have reached the forced target, and it
- %% is unsafe. Give up.
- none;
- _ ->
- %% Try following this branch to see whether it
- %% leads to a safe `br`.
- shortcut_2(L, Bs, UnsetVars, St)
- end;
- #b_br{bool=#b_var{},succ=Succ,fail=Fail} ->
- case {Succ,Fail} of
- {L,Target} ->
- %% The failure label is the forced target.
- %% Try following the success label to see
- %% whether it also ultimately ends up at the
- %% forced target.
- shortcut_2(L, Bs, UnsetVars, St);
- {Target,L} ->
- %% The success label is the forced target.
- %% Try following the failure label to see
- %% whether it also ultimately ends up at the
- %% forced target.
- shortcut_2(L, Bs, UnsetVars, St);
- {_,_} ->
- case Target of
- any ->
- %% This two-way branch is unsafe. Try reducing
- %% it to a one-way branch.
- shortcut_two_way(Br, Bs, UnsetVars, St);
- one_way ->
- %% This two-way branch is unsafe. Try reducing
- %% it to a one-way branch.
- shortcut_two_way(Br, Bs, UnsetVars, St);
- _ when is_integer(Target) ->
- %% This two-way branch is unsafe, and
- %% there already is a forced target.
- %% Give up.
- none
- end
- end
- end;
+ shortcut_unsafe_br(Br, From, Bs, UnsetVars, St);
true ->
- %% This `br` instruction is safe. It does not
- %% branch to a phi node, and all variables that
- %% will be used are guaranteed to be defined.
- case Br of
- #b_br{bool=#b_literal{val=true},succ=L} ->
- %% This is a one-way branch.
+ shortcut_safe_br(Br, From, Bs, UnsetVars, St)
+ end.
+
+shortcut_unsafe_br(Br, From, Bs, UnsetVars, #st{target=Target}=St) ->
+ %% Branching using this `br` is unsafe, either because it
+ %% is an unconditional branch to a phi node, or because
+ %% one or more of the variables that are not set will be
+ %% used. Try to follow branches of this `br`, to find a
+ %% safe `br`.
+ case Br of
+ #b_br{bool=#b_literal{val=true},succ=L} ->
+ case Target of
+ L ->
+ %% We have reached the forced target, and it
+ %% is unsafe. Give up.
+ none;
+ _ ->
+ %% Try following this branch to see whether it
+ %% leads to a safe `br`.
+ shortcut_2(L, From, Bs, UnsetVars, St)
+ end;
+ #b_br{bool=#b_var{},succ=Succ,fail=Fail} ->
+ case {Succ,Fail} of
+ {L,Target} ->
+ %% The failure label is the forced target.
+ %% Try following the success label to see
+ %% whether it also ultimately ends up at the
+ %% forced target.
+ shortcut_2(L, From, Bs, UnsetVars, St);
+ {Target,L} ->
+ %% The success label is the forced target.
+ %% Try following the failure label to see
+ %% whether it also ultimately ends up at the
+ %% forced target.
+ shortcut_2(L, From, Bs, UnsetVars, St);
+ {_,_} ->
case Target of
any ->
- %% No forced target. Success!
- {Br,Bs,UnsetVars};
+ %% This two-way branch is unsafe. Try
+ %% reducing it to a one-way branch.
+ shortcut_two_way(Br, From, Bs, UnsetVars, St);
one_way ->
- %% The target must be a one-way branch, which this
- %% `br` is. Success!
- {Br,Bs,UnsetVars};
- L when is_integer(Target) ->
- %% The forced target is L. Success!
- {Br,Bs,UnsetVars};
+ %% This two-way branch is unsafe. Try
+ %% reducing it to a one-way branch.
+ shortcut_two_way(Br, From, Bs, UnsetVars, St);
_ when is_integer(Target) ->
- %% Wrong forced target. Try following this branch
- %% to see if it ultimately ends up at the forced
- %% target.
- shortcut_2(L, Bs, UnsetVars, St)
- end;
- #b_br{bool=#b_var{}} ->
- %% This is a two-way branch.
- if
- Target =:= any; Target =:= one_way ->
- %% No specific forced target. Try to reduce the
- %% two-way branch to an one-way branch.
- case shortcut_two_way(Br, Bs, UnsetVars, St) of
- none when Target =:= any ->
- %% This `br` can't be reduced to a one-way
- %% branch. Return the `br` as-is.
- {Br,Bs,UnsetVars};
- none when Target =:= one_way ->
- %% This `br` can't be reduced to a one-way
- %% branch. The caller wants a one-way branch.
- %% Give up.
- none;
- {_,_,_}=Res ->
- %% This `br` was successfully reduced to a
- %% one-way branch.
- Res
- end;
- is_integer(Target) ->
- %% There is a forced target, which can't
- %% be reached because this `br` is a two-way
- %% branch. Give up.
+ %% This two-way branch is unsafe, and
+ %% there already is a forced target.
+ %% Give up.
none
end
end
end.
-update_unset_vars(L, Br, SetInThisBlock, UnsetVars, #st{skippable=Skippable}) ->
+shortcut_safe_br(Br, From, Bs, UnsetVars, #st{target=Target}=St) ->
+ %% This `br` instruction is safe. It does not branch to a phi
+ %% node, and all variables that will be used are guaranteed to be
+ %% defined.
+ case Br of
+ #b_br{bool=#b_literal{val=true},succ=L} ->
+ %% This is a one-way branch.
+ case Target of
+ any ->
+ %% No forced target. Success!
+ {Br,Bs,UnsetVars};
+ one_way ->
+ %% The target must be a one-way branch, which this
+ %% `br` is. Success!
+ {Br,Bs,UnsetVars};
+ L when is_integer(Target) ->
+ %% The forced target is L. Success!
+ {Br,Bs,UnsetVars};
+ _ when is_integer(Target) ->
+ %% Wrong forced target. Try following this branch
+ %% to see if it ultimately ends up at the forced
+ %% target.
+ shortcut_2(L, From, Bs, UnsetVars, St)
+ end;
+ #b_br{bool=#b_var{}} ->
+ %% This is a two-way branch.
+ if
+ Target =:= any; Target =:= one_way ->
+ %% No specific forced target. Try to reduce the
+ %% two-way branch to an one-way branch.
+ case shortcut_two_way(Br, From, Bs, UnsetVars, St) of
+ none when Target =:= any ->
+ %% This `br` can't be reduced to a one-way
+ %% branch. Return the `br` as-is.
+ {Br,Bs,UnsetVars};
+ none when Target =:= one_way ->
+ %% This `br` can't be reduced to a one-way
+ %% branch. The caller wants a one-way
+ %% branch. Give up.
+ none;
+ {_,_,_}=Res ->
+ %% This `br` was successfully reduced to a
+ %% one-way branch.
+ Res
+ end;
+ is_integer(Target) ->
+ %% There is a forced target, which can't
+ %% be reached because this `br` is a two-way
+ %% branch. Give up.
+ none
+ end
+ end.
+
+update_unset_vars(L, Is, Br, UnsetVars, #st{skippable=Skippable}) ->
case is_map_key(L, Skippable) of
true ->
%% None of the variables used in this block are used in
- %% the successors. We can speed up compilation by avoiding
- %% adding variables to the UnsetVars if the presence of
- %% those variable would not change the outcome of the
- %% tests in is_br_safe/2.
+ %% the successors. Thus, there is no need to add the
+ %% variables to the set of unset variables.
case Br of
- #b_br{bool=Bool} ->
- case member(Bool, SetInThisBlock) of
+ #b_br{bool=#b_var{}=Bool} ->
+ case keymember(Bool, #b_set.dst, Is) of
true ->
%% Bool is a variable defined in this
- %% block. It will change the outcome of
- %% the `not member(V, UnsetVars)` check in
- %% is_br_safe/2. The other variables
- %% defined in this block will not.
- ordsets:add_element(Bool, UnsetVars);
+ %% block. Using the br instruction from
+ %% this block (and skipping the body of
+ %% the block) is unsafe.
+ unsafe;
false ->
%% Bool is either a variable not defined
%% in this block or a literal. Adding it
@@ -321,18 +339,24 @@ update_unset_vars(L, Br, SetInThisBlock, UnsetVars, #st{skippable=Skippable}) ->
%% the outcome of the tests in
%% is_br_safe/2.
UnsetVars
- end
+ end;
+ #b_br{} ->
+ UnsetVars
end;
false ->
+ %% Some variables defined in this block are used by
+ %% successors. We must update the set of unset variables.
+ SetInThisBlock = [V || #b_set{dst=V} <- Is],
ordsets:union(UnsetVars, ordsets:from_list(SetInThisBlock))
end.
-shortcut_two_way(#b_br{succ=Succ,fail=Fail}, Bs0, UnsetVars0, St) ->
- case shortcut_2(Succ, Bs0, UnsetVars0, St#st{target=Fail}) of
+shortcut_two_way(#b_br{succ=Succ,fail=Fail}, From, Bs0, UnsetVars0, St0) ->
+ case shortcut_2(Succ, From, Bs0, UnsetVars0, St0#st{target=Fail}) of
{#b_br{bool=#b_literal{},succ=Fail},_,_}=Res ->
Res;
none ->
- case shortcut_2(Fail, Bs0, UnsetVars0, St#st{target=Succ}) of
+ St = St0#st{target=Succ},
+ case shortcut_2(Fail, From, Bs0, UnsetVars0, St) of
{#b_br{bool=#b_literal{},succ=Succ},_,_}=Res ->
Res;
none ->
@@ -374,40 +398,42 @@ is_forbidden(L, St) ->
%% Return the updated bindings, or 'none' if there is
%% any instruction with potential side effects.
-eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], Bs0, St) ->
- From = map_get(from, Bs0),
- [Val] = [Val || {Val,Pred} <- Args, Pred =:= From],
+eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], From, Bs0, St) ->
+ Val = get_phi_arg(Args, From),
Bs = bind_var(Dst, Val, Bs0),
- eval_is(Is, Bs, St);
-eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], Bs, St) ->
+ eval_is(Is, From, Bs, St);
+eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], From, Bs, St) ->
I = sub(I0, Bs),
case eval_bif(I, St) of
#b_literal{}=Val ->
- eval_is(Is, bind_var(Dst, Val, Bs), St);
+ eval_is(Is, From, bind_var(Dst, Val, Bs), St);
none ->
- eval_is(Is, Bs, St)
+ eval_is(Is, From, Bs, St)
end;
-eval_is([#b_set{op=Op,dst=Dst}=I|Is], Bs, St)
+eval_is([#b_set{op=Op,dst=Dst}=I|Is], From, Bs, St)
when Op =:= is_tagged_tuple; Op =:= is_nonempty_list ->
#b_set{args=Args} = sub(I, Bs),
case eval_rel_op(Op, Args, St) of
#b_literal{}=Val ->
- eval_is(Is, bind_var(Dst, Val, Bs), St);
+ eval_is(Is, From, bind_var(Dst, Val, Bs), St);
none ->
- eval_is(Is, Bs, St)
+ eval_is(Is, From, Bs, St)
end;
-eval_is([#b_set{}=I|Is], Bs, St) ->
+eval_is([#b_set{}=I|Is], From, Bs, St) ->
case beam_ssa:no_side_effect(I) of
true ->
%% This instruction has no side effects. It can
%% safely be omitted.
- eval_is(Is, Bs, St);
+ eval_is(Is, From, Bs, St);
false ->
%% This instruction may have some side effect.
%% It is not safe to avoid this instruction.
none
end;
-eval_is([], Bs, _St) -> Bs.
+eval_is([], _From, Bs, _St) -> Bs.
+
+get_phi_arg([{Val,From}|_], From) -> Val;
+get_phi_arg([_|As], From) -> get_phi_arg(As, From).
eval_terminator(#b_br{bool=#b_var{}=Bool}=Br, Bs, _St) ->
Val = get_value(Bool, Bs),
@@ -477,20 +503,31 @@ eval_bif(#b_set{op={bif,Bif},args=Args}, St) ->
false ->
none;
true ->
- case [Lit || #b_literal{val=Lit} <- Args] of
- LitArgs when length(LitArgs) =:= Arity ->
+ case get_lit_args(Args) of
+ none ->
+ %% Not literal arguments. Try to evaluate
+ %% it based on a previous relational operator.
+ eval_rel_op({bif,Bif}, Args, St);
+ LitArgs ->
try apply(erlang, Bif, LitArgs) of
Val -> #b_literal{val=Val}
catch
error:_ -> none
- end;
- _ ->
- %% Not literal arguments. Try to evaluate
- %% it based on a previous relational operator.
- eval_rel_op({bif,Bif}, Args, St)
+ end
end
end.
+get_lit_args([#b_literal{val=Lit1}]) ->
+ [Lit1];
+get_lit_args([#b_literal{val=Lit1},
+ #b_literal{val=Lit2}]) ->
+ [Lit1,Lit2];
+get_lit_args([#b_literal{val=Lit1},
+ #b_literal{val=Lit2},
+ #b_literal{val=Lit3}]) ->
+ [Lit1,Lit2,Lit3];
+get_lit_args(_) -> none.
+
%%%
%%% Handling of relational operators.
%%%
@@ -1026,11 +1063,12 @@ used_vars_is([], Used) ->
sub(#b_set{args=Args}=I, Sub) ->
I#b_set{args=[sub_arg(A, Sub) || A <- Args]}.
-sub_arg(Old, Sub) ->
+sub_arg(#b_var{}=Old, Sub) ->
case Sub of
#{Old:=New} -> New;
#{} -> Old
- end.
+ end;
+sub_arg(Old, _Sub) -> Old.
rel2fam(S0) ->
S1 = sofs:relation(S0),