From 0b40d88912decc938d738f5531abc7e7ef3c9820 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Wed, 11 Jul 2018 11:01:05 +0200 Subject: beam_ssa_opt: Eliminate redundant match alignment tests The beam_ssa_bsm pass welds chained matches together, but the match expressions themselves are unchanged and if there's a tail alignment check it will be done each time. This subpass figures out the checks we've already done and deletes the redundant ones. --- lib/compiler/src/beam_ssa_opt.erl | 117 +++++++++++++++++++++++++++++++++++++- 1 file changed, 116 insertions(+), 1 deletion(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 89cfbd7a84..ac2d943fef 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -66,13 +66,15 @@ passes(Opts0) -> ?PASS(ssa_opt_live), %Second time. ?PASS(ssa_opt_bsm), + ?PASS(ssa_opt_bsm_units), ?PASS(ssa_opt_bsm_shortcut), ?PASS(ssa_opt_misc), ?PASS(ssa_opt_tuple_size), ?PASS(ssa_opt_sw), ?PASS(ssa_opt_blockify), ?PASS(ssa_opt_sink), - ?PASS(ssa_opt_merge_blocks)], + ?PASS(ssa_opt_merge_blocks), + ?PASS(ssa_opt_trim_unreachable)], Negations = [{list_to_atom("no_"++atom_to_list(N)),N} || {N,_} <- Ps], Opts = proplists:substitute_negations(Negations, Opts0), @@ -112,6 +114,9 @@ ssa_opt_type(#st{ssa=Linear,args=Args}=St) -> ssa_opt_blockify(#st{ssa=Linear}=St) -> St#st{ssa=maps:from_list(Linear)}. +ssa_opt_trim_unreachable(#st{ssa=Blocks}=St) -> + St#st{ssa=beam_ssa:trim_unreachable(Blocks)}. + %%% %%% Split blocks before certain instructions to enable more optimizations. %%% @@ -1001,6 +1006,110 @@ bsm_shortcut([{L,#b_blk{is=Is,last=Last0}=Blk}|Bs], PosMap) -> end; bsm_shortcut([], _PosMap) -> []. +%%% +%%% Eliminate redundant bs_test_unit2 instructions. +%%% + +ssa_opt_bsm_units(#st{ssa=Linear}=St) -> + St#st{ssa=bsm_units(Linear, #{})}. + +bsm_units([{L,#b_blk{last=#b_br{succ=Succ,fail=Fail}}=Block0} | Bs], UnitMaps0) -> + UnitsIn = maps:get(L, UnitMaps0, #{}), + {Block, UnitsOut} = bsm_units_skip(Block0, UnitsIn), + UnitMaps1 = bsm_units_join(Succ, UnitsOut, UnitMaps0), + UnitMaps = bsm_units_join(Fail, UnitsIn, UnitMaps1), + [{L, Block} | bsm_units(Bs, UnitMaps)]; +bsm_units([{L,#b_blk{last=#b_switch{fail=Fail,list=Switch}}=Block} | Bs], UnitMaps0) -> + UnitsIn = maps:get(L, UnitMaps0, #{}), + Labels = [Fail | [Lbl || {_Arg, Lbl} <- Switch]], + UnitMaps = foldl(fun(Lbl, UnitMaps) -> + bsm_units_join(Lbl, UnitsIn, UnitMaps) + end, UnitMaps0, Labels), + [{L, Block} | bsm_units(Bs, UnitMaps)]; +bsm_units([{L, Block} | Bs], UnitMaps) -> + [{L, Block} | bsm_units(Bs, UnitMaps)]; +bsm_units([], _UnitMaps) -> + []. + +bsm_units_skip(Block, Units) -> + bsm_units_skip_1(Block#b_blk.is, Block, Units). + +bsm_units_skip_1([#b_set{op=bs_start_match,dst=New}|_], Block, Units) -> + %% We bail early since there can't be more than one match per block. + {Block, Units#{ New => 1 }}; +bsm_units_skip_1([#b_set{op=bs_match, + dst=New, + args=[#b_literal{val=skip}, + Ctx, + #b_literal{val=binary}, + _Flags, + #b_literal{val=all}, + #b_literal{val=OpUnit}]}=Skip | Test], + Block0, Units) -> + [#b_set{op=succeeded,dst=Bool,args=[New]}] = Test, %Assertion. + #b_br{bool=Bool} = Last0 = Block0#b_blk.last, %Assertion. + CtxUnit = maps:get(Ctx, Units), + if + CtxUnit rem OpUnit =:= 0 -> + Is = takewhile(fun(I) -> I =/= Skip end, Block0#b_blk.is), + Last = Last0#b_br{bool=#b_literal{val=true}}, + Block = Block0#b_blk{is=Is,last=Last}, + {Block, Units#{ New => CtxUnit }}; + CtxUnit rem OpUnit =/= 0 -> + {Block0, Units#{ New => OpUnit, Ctx => OpUnit }} + end; +bsm_units_skip_1([#b_set{op=bs_match,dst=New,args=Args}|_], Block, Units) -> + [_,Ctx|_] = Args, + CtxUnit = maps:get(Ctx, Units), + OpUnit = bsm_op_unit(Args), + {Block, Units#{ New => gcd(OpUnit, CtxUnit) }}; +bsm_units_skip_1([_I | Is], Block, Units) -> + bsm_units_skip_1(Is, Block, Units); +bsm_units_skip_1([], Block, Units) -> + {Block, Units}. + +bsm_op_unit([_,_,_,Size,#b_literal{val=U}]) -> + case Size of + #b_literal{val=Sz} when is_integer(Sz) -> Sz*U; + _ -> U + end; +bsm_op_unit([#b_literal{val=string},_,#b_literal{val=String}]) -> + bit_size(String); +bsm_op_unit([#b_literal{val=utf8}|_]) -> + 8; +bsm_op_unit([#b_literal{val=utf16}|_]) -> + 16; +bsm_op_unit([#b_literal{val=utf32}|_]) -> + 32; +bsm_op_unit(_) -> + 1. + +%% Several paths can lead to the same match instruction and the inferred units +%% may differ between them, so we can only keep the information that is common +%% to all paths. +bsm_units_join(Lbl, MapA, UnitMaps0) when is_map_key(Lbl, UnitMaps0) -> + MapB = maps:get(Lbl, UnitMaps0), + Merged = if + map_size(MapB) =< map_size(MapA) -> + bsm_units_join_1(maps:keys(MapB), MapA, MapB); + map_size(MapB) > map_size(MapA) -> + bsm_units_join_1(maps:keys(MapA), MapB, MapA) + end, + maps:put(Lbl, Merged, UnitMaps0); +bsm_units_join(Lbl, MapA, UnitMaps0) when MapA =/= #{} -> + maps:put(Lbl, MapA, UnitMaps0); +bsm_units_join(_Lbl, _MapA, UnitMaps0) -> + UnitMaps0. + +bsm_units_join_1([Key | Keys], Left, Right) when is_map_key(Key, Left) -> + UnitA = maps:get(Key, Left), + UnitB = maps:get(Key, Right), + bsm_units_join_1(Keys, Left, maps:put(Key, gcd(UnitA, UnitB), Right)); +bsm_units_join_1([Key | Keys], Left, Right) -> + bsm_units_join_1(Keys, Left, maps:remove(Key, Right)); +bsm_units_join_1([], _MapA, Right) -> + Right. + %%% %%% Miscellanous optimizations in execution order. %%% @@ -1618,6 +1727,12 @@ insert_def_is([], _V, Def) -> %%% Common utilities. %%% +gcd(A, B) -> + case A rem B of + 0 -> B; + X -> gcd(B, X) + end. + rel2fam(S0) -> S1 = sofs:relation(S0), S = sofs:rel2fam(S1), -- cgit v1.2.3