aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2019-02-28 16:25:14 +0100
committerBjörn Gustavsson <[email protected]>2019-03-01 12:52:48 +0100
commit7dce10bc84e0e8f88233cf5d8e659d5e2f58496c (patch)
tree5ad6e195ffc8cd5f618354129cfe3abbd52fef02 /lib/compiler
parentd4229d29cb4737ac74e126a197812ab60a9b556c (diff)
downloadotp-7dce10bc84e0e8f88233cf5d8e659d5e2f58496c.tar.gz
otp-7dce10bc84e0e8f88233cf5d8e659d5e2f58496c.tar.bz2
otp-7dce10bc84e0e8f88233cf5d8e659d5e2f58496c.zip
Keep the set of unset variables as small as possible
Refactor the code to avoid putting any variable from a skippable block into the set of unset variables. Keeping the set of unset variables as small as possible will make beam_ssa_dead almost twice as fast when compiling lib/unicode/tokenizer.ex in elixir.
Diffstat (limited to 'lib/compiler')
-rw-r--r--lib/compiler/src/beam_ssa_dead.erl243
1 files changed, 129 insertions, 114 deletions
diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl
index 2cca9ebadf..dc0381f105 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())}.
@@ -181,139 +182,148 @@ 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, Bs, UnsetVars0, St);
+ UnsetVars ->
+ %% Continue checking whether this br is
+ %% suitable.
+ shortcut_test_br(Br, Bs#{from:=L},
+ UnsetVars, St)
+ end
end
end.
-shortcut_3(Br, Bs, UnsetVars, #st{target=Target}=St) ->
+shortcut_test_br(Br, 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, 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, Bs, UnsetVars, St)
+ end.
+
+shortcut_unsafe_br(Br, 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, 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 ->
- %% 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, 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, 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, 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, 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.
+ 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,9 +331,14 @@ 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.