aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler/src
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2019-02-18 11:43:51 +0100
committerBjörn Gustavsson <[email protected]>2019-02-20 14:28:42 +0100
commitc5771f6d7adfbd0d8dd4202dce5d4a090d4ad50b (patch)
tree6b5172e48b39d52bdb0b4287ce6945b2c704f0d5 /lib/compiler/src
parentd96474de9d71705e4b68aa8b6f7e33657870873f (diff)
downloadotp-c5771f6d7adfbd0d8dd4202dce5d4a090d4ad50b.tar.gz
otp-c5771f6d7adfbd0d8dd4202dce5d4a090d4ad50b.tar.bz2
otp-c5771f6d7adfbd0d8dd4202dce5d4a090d4ad50b.zip
Improve optimization of switches
Part of the switch optimization done by `ssa_opt_sw` can be better done in `beam_ssa_type`.
Diffstat (limited to 'lib/compiler/src')
-rw-r--r--lib/compiler/src/beam_ssa_opt.erl93
-rw-r--r--lib/compiler/src/beam_ssa_type.erl79
2 files changed, 79 insertions, 93 deletions
diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl
index 0f03d0e736..f8e19d0aa7 100644
--- a/lib/compiler/src/beam_ssa_opt.erl
+++ b/lib/compiler/src/beam_ssa_opt.erl
@@ -164,12 +164,14 @@ repeated_passes(Opts) ->
epilogue_passes(Opts) ->
Ps = [?PASS(ssa_opt_type_finish),
?PASS(ssa_opt_float),
- ?PASS(ssa_opt_live), %One last time to clean up the
- %mess left by the float pass.
+ ?PASS(ssa_opt_sw),
+
+ %% Run live one more time to clean up after the float and sw
+ %% passes.
+ ?PASS(ssa_opt_live),
?PASS(ssa_opt_bsm),
?PASS(ssa_opt_bsm_units),
?PASS(ssa_opt_bsm_shortcut),
- ?PASS(ssa_opt_sw),
?PASS(ssa_opt_blockify),
?PASS(ssa_opt_sink),
?PASS(ssa_opt_merge_blocks),
@@ -1830,12 +1832,16 @@ opt_tup_size_is([], _, _, _Acc) -> none.
%%%
ssa_opt_sw({#st{ssa=Linear0,cnt=Count0}=St, FuncDb}) ->
- {Linear,Count} = opt_sw(Linear0, #{}, Count0, []),
+ {Linear,Count} = opt_sw(Linear0, Count0, []),
{St#st{ssa=Linear,cnt=Count}, FuncDb}.
-opt_sw([{L,#b_blk{is=Is,last=#b_switch{}=Last0}=Blk0}|Bs], Phis0, Count0, Acc) ->
- Phis = opt_sw_phis(Is, Phis0),
- case opt_sw_last(Last0, Phis) of
+opt_sw([{L,#b_blk{is=Is,last=#b_switch{}=Sw0}=Blk0}|Bs], Count0, Acc) ->
+ %% Ensure that no label in the switch list is the same
+ %% as the failure label.
+ #b_switch{fail=Fail,list=List0} = Sw0,
+ List = [{Val,Lbl} || {Val,Lbl} <- List0, Lbl =/= Fail],
+ Sw1 = beam_ssa:normalize(Sw0#b_switch{list=List}),
+ case Sw1 of
#b_switch{arg=Arg,fail=Fail,list=[{Lit,Lbl}]} ->
%% Rewrite a single value switch to a br.
Bool = #b_var{name={'@ssa_bool',Count0}},
@@ -1843,7 +1849,7 @@ opt_sw([{L,#b_blk{is=Is,last=#b_switch{}=Last0}=Blk0}|Bs], Phis0, Count0, Acc) -
IsEq = #b_set{op={bif,'=:='},dst=Bool,args=[Arg,Lit]},
Br = #b_br{bool=Bool,succ=Lbl,fail=Fail},
Blk = Blk0#b_blk{is=Is++[IsEq],last=Br},
- opt_sw(Bs, Phis, Count, [{L,Blk}|Acc]);
+ opt_sw(Bs, Count, [{L,Blk}|Acc]);
#b_switch{arg=Arg,fail=Fail,
list=[{#b_literal{val=B1},Lbl},{#b_literal{val=B2},Lbl}]}
when B1 =:= not B2 ->
@@ -1853,71 +1859,18 @@ opt_sw([{L,#b_blk{is=Is,last=#b_switch{}=Last0}=Blk0}|Bs], Phis0, Count0, Acc) -
IsBool = #b_set{op={bif,is_boolean},dst=Bool,args=[Arg]},
Br = #b_br{bool=Bool,succ=Lbl,fail=Fail},
Blk = Blk0#b_blk{is=Is++[IsBool],last=Br},
- opt_sw(Bs, Phis, Count, [{L,Blk}|Acc]);
- Last0 ->
- opt_sw(Bs, Phis, Count0, [{L,Blk0}|Acc]);
- Last ->
- Blk = Blk0#b_blk{last=Last},
- opt_sw(Bs, Phis, Count0, [{L,Blk}|Acc])
+ opt_sw(Bs, Count, [{L,Blk}|Acc]);
+ Sw0 ->
+ opt_sw(Bs, Count0, [{L,Blk0}|Acc]);
+ Sw ->
+ Blk = Blk0#b_blk{last=Sw},
+ opt_sw(Bs, Count0, [{L,Blk}|Acc])
end;
-opt_sw([{L,#b_blk{is=Is}=Blk}|Bs], Phis0, Count, Acc) ->
- Phis = opt_sw_phis(Is, Phis0),
- opt_sw(Bs, Phis, Count, [{L,Blk}|Acc]);
-opt_sw([], _Phis, Count, Acc) ->
+opt_sw([{L,#b_blk{}=Blk}|Bs], Count, Acc) ->
+ opt_sw(Bs, Count, [{L,Blk}|Acc]);
+opt_sw([], Count, Acc) ->
{reverse(Acc),Count}.
-opt_sw_phis([#b_set{op=phi,dst=Dst,args=Args}|Is], Phis) ->
- case opt_sw_literals(Args, []) of
- error ->
- opt_sw_phis(Is, Phis);
- Literals ->
- opt_sw_phis(Is, Phis#{Dst=>Literals})
- end;
-opt_sw_phis(_, Phis) -> Phis.
-
-opt_sw_last(#b_switch{arg=Arg,fail=Fail,list=List0}=Sw0, Phis) ->
- case Phis of
- #{Arg:=Values0} ->
- Values = gb_sets:from_list(Values0),
-
- %% Prune the switch list to only contain the possible values.
- List1 = [P || {Lit,_}=P <- List0, gb_sets:is_member(Lit, Values)],
-
- %% Now test whether the failure label can ever be reached.
- Sw = case gb_sets:size(Values) =:= length(List1) of
- true ->
- %% The switch list has the same number of values as the phi node.
- %% The values must be the same, because the values that were not
- %% possible were pruned from the switch list. Therefore, the
- %% failure label can't possibly be reached, and we can choose a
- %% a new failure label by picking a value from the list.
- case List1 of
- [{#b_literal{},Lbl}|List] ->
- Sw0#b_switch{fail=Lbl,list=List};
- [] ->
- Sw0#b_switch{list=List1}
- end;
- false ->
- %% There are some values in the phi node that are not in the
- %% switch list; thus, the failure label can still be reached.
- Sw0
- end,
- beam_ssa:normalize(Sw);
- #{} ->
- %% Ensure that no label in the switch list is the same
- %% as the failure label.
- List = [{Val,Lbl} || {Val,Lbl} <- List0, Lbl =/= Fail],
- Sw = Sw0#b_switch{list=List},
- beam_ssa:normalize(Sw)
- end.
-
-opt_sw_literals([{#b_literal{}=Lit,_}|T], Acc) ->
- opt_sw_literals(T, [Lit|Acc]);
-opt_sw_literals([_|_], _Acc) ->
- error;
-opt_sw_literals([], Acc) -> Acc.
-
-
%%%
%%% Merge blocks.
%%%
diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl
index 4b53848a74..83f8a3cc56 100644
--- a/lib/compiler/src/beam_ssa_type.erl
+++ b/lib/compiler/src/beam_ssa_type.erl
@@ -23,7 +23,8 @@
-include("beam_ssa_opt.hrl").
-import(lists, [all/2,any/2,droplast/1,foldl/3,last/1,member/2,
- partition/2,reverse/1,reverse/2,seq/2,sort/1]).
+ keyfind/3,partition/2,reverse/1,reverse/2,
+ seq/2,sort/1]).
-define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}).
@@ -664,25 +665,45 @@ opt_terminator(#b_br{bool=#b_var{}}=Br, Ts, Ds) ->
simplify_not(Br, Ts, Ds);
opt_terminator(#b_switch{arg=#b_literal{}}=Sw, _Ts, _Ds) ->
beam_ssa:normalize(Sw);
-opt_terminator(#b_switch{arg=#b_var{}=V}=Sw0, Ts, Ds) ->
- Type = get_type(V, Ts),
+opt_terminator(#b_switch{arg=#b_var{}=V}=Sw, Ts, Ds) ->
+ case get_type(V, Ts) of
+ any ->
+ beam_ssa:normalize(Sw);
+ Type ->
+ beam_ssa:normalize(opt_switch(Sw, Type, Ts, Ds))
+ end;
+opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> Ret.
+
+
+opt_switch(#b_switch{fail=Fail,list=List0}=Sw0, Type, Ts, Ds) ->
+ List = prune_switch_list(List0, Fail, Type, Ts),
+ Sw1 = Sw0#b_switch{list=List},
case Type of
#t_integer{elements={_,_}=Range} ->
- simplify_switch_int(Sw0, Range);
- _ ->
+ simplify_switch_int(Sw1, Range);
+ #t_atom{elements=[_|_]} ->
case t_is_boolean(Type) of
true ->
- case simplify_switch_bool(Sw0, Ts, Ds) of
- #b_br{}=Br ->
- opt_terminator(Br, Ts, Ds);
- Sw ->
- beam_ssa:normalize(Sw)
- end;
+ #b_br{} = Br = simplify_switch_bool(Sw1, Ts, Ds),
+ opt_terminator(Br, Ts, Ds);
false ->
- beam_ssa:normalize(Sw0)
- end
+ simplify_switch_atom(Type, Sw1)
+ end;
+ _ ->
+ Sw1
+ end.
+
+prune_switch_list([{_,Fail}|T], Fail, Type, Ts) ->
+ prune_switch_list(T, Fail, Type, Ts);
+prune_switch_list([{Arg,_}=Pair|T], Fail, Type, Ts) ->
+ case meet(get_type(Arg, Ts), Type) of
+ none ->
+ %% Different types. This value can never match.
+ prune_switch_list(T, Fail, Type, Ts);
+ _ ->
+ [Pair|prune_switch_list(T, Fail, Type, Ts)]
end;
-opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> Ret.
+prune_switch_list([], _, _, _) -> [].
update_successors(#b_br{bool=#b_literal{val=true},succ=S}, Ts, D) ->
update_successor(S, Ts, D);
@@ -1079,6 +1100,17 @@ bs_match_type(utf16, _) ->
bs_match_type(utf32, _) ->
?UNICODE_INT.
+simplify_switch_atom(#t_atom{elements=Atoms}, #b_switch{list=List0}=Sw) ->
+ case sort([A || {#b_literal{val=A},_} <- List0]) of
+ Atoms ->
+ %% All possible atoms are included in the list. The
+ %% failure label will never be used.
+ [{_,Fail}|List] = List0,
+ Sw#b_switch{fail=Fail,list=List};
+ _ ->
+ Sw
+ end.
+
simplify_switch_int(#b_switch{list=List0}=Sw, {Min,Max}) ->
List1 = sort(List0),
Vs = [V || {#b_literal{val=V},_} <- List1],
@@ -1123,14 +1155,14 @@ simplify_is_record(I, any, _Size, _Tag, _Ts) ->
simplify_is_record(_I, _Type, _Size, _Tag, _Ts) ->
#b_literal{val=false}.
-simplify_switch_bool(#b_switch{arg=B,list=List0}=Sw, Ts, Ds) ->
- List = sort(List0),
- case List of
- [{#b_literal{val=false},Fail},{#b_literal{val=true},Succ}] ->
- simplify_not(#b_br{bool=B,succ=Succ,fail=Fail}, Ts, Ds);
- [_|_] ->
- Sw
- end.
+simplify_switch_bool(#b_switch{arg=B,fail=Fail,list=List0}, Ts, Ds) ->
+ FalseVal = #b_literal{val=false},
+ TrueVal = #b_literal{val=true},
+ List1 = List0 ++ [{FalseVal,Fail},{TrueVal,Fail}],
+ {_,FalseLbl} = keyfind(FalseVal, 1, List1),
+ {_,TrueLbl} = keyfind(TrueVal, 1, List1),
+ Br = beam_ssa:normalize(#b_br{bool=B,succ=TrueLbl,fail=FalseLbl}),
+ simplify_not(Br, Ts, Ds).
simplify_not(#b_br{bool=#b_var{}=V,succ=Succ,fail=Fail}=Br0, Ts, Ds) ->
case Ds of
@@ -1144,7 +1176,8 @@ simplify_not(#b_br{bool=#b_var{}=V,succ=Succ,fail=Fail}=Br0, Ts, Ds) ->
end;
#{} ->
Br0
- end.
+ end;
+simplify_not(#b_br{bool=#b_literal{}}=Br, _Ts, _Ds) -> Br.
%%%
%%% Calculate the set of variables that are only used once in the