From 48b844b196e115b2995661ec81c108610acc4b6a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sat, 8 Sep 2018 10:52:07 +0200 Subject: beam_ssa_type: Remove repeated clauses in meet/2 --- lib/compiler/src/beam_ssa_type.erl | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index e5f15da836..ae926960bf 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -1025,13 +1025,9 @@ meet(#t_integer{elements={Min1,Max1}}, #t_integer{elements={Min2,Max2}}) -> #t_integer{elements={max(Min1, Min2),min(Max1, Max2)}}; meet(#t_integer{}=T, number) -> T; -meet(float, number) -> float; -meet(#t_integer{}=T, number) -> T; -meet(float, number) -> float; +meet(float=T, number) -> T; meet(number, #t_integer{}=T) -> T; -meet(#t_integer{}=T, number) -> T; meet(number, float=T) -> T; -meet(float=T, number) -> T; meet(list, cons) -> cons; meet(list, nil) -> nil; meet(cons, list) -> cons; -- cgit v1.2.3 From 0442b6a4587c0961febe3c6044d94d2ce7f8f469 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 6 Sep 2018 07:33:56 +0200 Subject: beam_ssa_pre_codegen: Fix bug in receive fixing When creating a phi node for the common exit block of a receive, the code failed to take into account that there could be more than one predecessor to the exit block for each remove_message. Rename exit_predessor/3 to exit_predessors/3 and make it return a list of the predecessors. --- lib/compiler/src/beam_ssa_pre_codegen.erl | 17 +++++++++++------ 1 file changed, 11 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl index 54aa2efaf6..7f67e315f5 100644 --- a/lib/compiler/src/beam_ssa_pre_codegen.erl +++ b/lib/compiler/src/beam_ssa_pre_codegen.erl @@ -1016,14 +1016,19 @@ recv_fix_common_1([], [], _Msg, Blocks) -> Blocks. fix_exit_phi_args([V|Vs], [Rm|Rms], Exit, Blocks) -> Path = beam_ssa:rpo([Rm], Blocks), - Pred = exit_predecessor(Path, Exit), - [{V,Pred}|fix_exit_phi_args(Vs, Rms, Exit, Blocks)]; + Preds = exit_predecessors(Path, Exit, Blocks), + [{V,Pred} || Pred <- Preds] ++ fix_exit_phi_args(Vs, Rms, Exit, Blocks); fix_exit_phi_args([], [], _, _) -> []. -exit_predecessor([Pred,Exit|_], Exit) -> - Pred; -exit_predecessor([_|Bs], Exit) -> - exit_predecessor(Bs, Exit). +exit_predecessors([L|Ls], Exit, Blocks) -> + Blk = map_get(L, Blocks), + case member(Exit, beam_ssa:successors(Blk)) of + true -> + [L|exit_predecessors(Ls, Exit, Blocks)]; + false -> + exit_predecessors(Ls, Exit, Blocks) + end; +exit_predecessors([], _Exit, _Blocks) -> []. %% fix_receive([Label], Defs, Blocks0, Count0) -> {Blocks,Count}. %% Add a copy instruction for all variables that are matched out and -- cgit v1.2.3 From d96778ad4631d649fe64716e07e4f3a2ba9c681d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Wed, 12 Sep 2018 11:41:43 +0200 Subject: beam_validator: Handle types for unary '-' or '+' --- lib/compiler/src/beam_validator.erl | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'lib') diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 953aced66e..d5833875ff 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -1919,6 +1919,12 @@ is_bif_safe(self, 0) -> true; is_bif_safe(node, 0) -> true; is_bif_safe(_, _) -> false. +arith_type([A], Vst) -> + %% Unary '+' or '-'. + case get_term_type(A, Vst) of + {float,_} -> {float,[]}; + _ -> number + end; arith_type([A,B], Vst) -> case {get_term_type(A, Vst),get_term_type(B, Vst)} of {{float,_},_} -> {float,[]}; -- cgit v1.2.3 From 0975c1e3fc4e05a9b4eb12ce91e240cdebc28d04 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 4 Sep 2018 04:40:54 +0200 Subject: beam_validator: Validate the literals in select_val --- lib/compiler/src/beam_validator.erl | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) (limited to 'lib') diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index d5833875ff..9fa55c5b4c 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -648,10 +648,12 @@ valfun_4({set_tuple_element,Src,Tuple,I}, Vst) -> %% Match instructions. valfun_4({select_val,Src,{f,Fail},{list,Choices}}, Vst0) -> assert_term(Src, Vst0), + assert_choices(Choices), Vst = branch_state(Fail, Vst0), kill_state(select_val_branches(Src, Choices, Vst)); valfun_4({select_tuple_arity,Tuple,{f,Fail},{list,Choices}}, Vst) -> assert_type(tuple, Tuple, Vst), + assert_arities(Choices), TupleType = case get_term_type(Tuple, Vst) of {fragile,TupleType0} -> TupleType0; TupleType0 -> TupleType0 @@ -1088,6 +1090,29 @@ prune_x_regs(Live, #vst{current=St0}=Vst) St = St0#st{x=gb_trees:from_orddict(Xs),defs=Defs,aliases=Aliases}, Vst#vst{current=St}. +%% All choices in a select_val list must be integers, floats, or atoms. +%% All must be of the same type. +assert_choices([{Tag,_},{f,_}|T]) -> + if + Tag =:= atom; Tag =:= float; Tag =:= integer -> + assert_choices_1(T, Tag); + true -> + error(bad_select_list) + end; +assert_choices([]) -> ok. + +assert_choices_1([{Tag,_},{f,_}|T], Tag) -> + assert_choices_1(T, Tag); +assert_choices_1([_,{f,_}|_], _Tag) -> + error(bad_select_list); +assert_choices_1([], _Tag) -> ok. + +assert_arities([Arity,{f,_}|T]) when is_integer(Arity) -> + assert_arities(T); +assert_arities([]) -> ok; +assert_arities(_) -> error(bad_tuple_arity_list). + + %%% %%% Floating point checking. %%% -- cgit v1.2.3 From e2a939dc4d23d75a0588722d0a08aef129b4c0be Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 7 Sep 2018 12:39:30 +0200 Subject: beam_validator: Infer more types When optimizations get more powerful, beam_validator must keep up. --- lib/compiler/src/beam_validator.erl | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 9fa55c5b4c..8d699f2abd 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -598,6 +598,14 @@ valfun_4({bif,is_map_key,{f,Fail},[_Key,Map]=Src,Dst}, Vst0) -> Vst = set_type(map, Map, Vst1), Type = propagate_fragility(bool, Src, Vst), set_type_reg(Type, Dst, Vst); +valfun_4({bif,Op,{f,Fail},[Cons]=Src,Dst}, Vst0) + when Op =:= hd; Op =:= tl -> + validate_src(Src, Vst0), + Vst1 = branch_state(Fail, Vst0), + Vst = set_type(cons, Cons, Vst1), + Type0 = bif_type(Op, Src, Vst), + Type = propagate_fragility(Type0, Src, Vst), + set_type_reg(Type, Dst, Vst); valfun_4({bif,Op,{f,Fail},Src,Dst}, Vst0) -> validate_src(Src, Vst0), Vst = branch_state(Fail, Vst0), @@ -610,7 +618,13 @@ valfun_4({gc_bif,Op,{f,Fail},Live,Src,Dst}, #vst{current=St0}=Vst0) -> St = kill_heap_allocation(St0), Vst1 = Vst0#vst{current=St}, Vst2 = branch_state(Fail, Vst1), - Vst = prune_x_regs(Live, Vst2), + Vst3 = prune_x_regs(Live, Vst2), + Vst = case Op of + map_size -> + set_type(map, hd(Src), Vst3); + _ -> + Vst3 + end, validate_src(Src, Vst), Type0 = bif_type(Op, Src, Vst), Type = propagate_fragility(Type0, Src, Vst), -- cgit v1.2.3 From d3551827cc0221437098c5afa492637072f8a771 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Mon, 27 Aug 2018 06:02:59 +0200 Subject: beam_ssa: Add normalize/1 Add normalize/1 to simplify optimizations. --- lib/compiler/src/beam_ssa.erl | 80 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 79 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl index a2766a0501..548e73cf43 100644 --- a/lib/compiler/src/beam_ssa.erl +++ b/lib/compiler/src/beam_ssa.erl @@ -27,6 +27,7 @@ fold_instrs_rpo/4, linearize/1, mapfold_instrs_rpo/4, + normalize/1, predecessors/1, rename_vars/3, rpo/1,rpo/2, @@ -102,7 +103,7 @@ -type cg_prim_op() :: 'bs_get' | 'bs_match_string' | 'bs_restore' | 'bs_skip' | 'copy' | 'put_tuple_arity' | 'put_tuple_element'. --import(lists, [foldl/3,mapfoldl/3,reverse/1]). +-import(lists, [foldl/3,keyfind/3,mapfoldl/3,reverse/1]). -spec add_anno(Key, Value, Construct) -> Construct when Key :: atom(), @@ -180,6 +181,69 @@ successors(#b_blk{last=Terminator}) -> [] end. +%% normalize(Instr0) -> Instr. +%% Normalize instructions to help optimizations. +%% +%% For commutative operators (such as '+' and 'or'), always +%% place a variable operand before a literal operand. +%% +%% Normalize #b_br{} to one of the following forms: +%% +%% #b_br{b_literal{val=true},succ=Label,fail=Label} +%% #b_br{b_var{},succ=Label1,fail=Label2} where Label1 =/= Label2 +%% +%% Simplify a #b_switch{} with a literal argument to a #b_br{}. +%% +%% Simplify a #b_switch{} with a variable argument and an empty +%% switch list to a #b_br{}. + +-spec normalize(b_set() | terminator()) -> + b_set() | terminator(). + +normalize(#b_set{op={bif,Bif},args=Args}=Set) -> + case {is_commutative(Bif),Args} of + {false,_} -> + Set; + {true,[#b_literal{}=Lit,#b_var{}=Var]} -> + Set#b_set{args=[Var,Lit]}; + {true,_} -> + Set + end; +normalize(#b_set{}=Set) -> + Set; +normalize(#b_br{}=Br) -> + case Br of + #b_br{bool=Bool,succ=Same,fail=Same} -> + case Bool of + #b_literal{val=true} -> + Br; + _ -> + Br#b_br{bool=#b_literal{val=true}} + end; + #b_br{bool=#b_literal{val=true},succ=Succ} -> + Br#b_br{fail=Succ}; + #b_br{bool=#b_literal{val=false},fail=Fail} -> + Br#b_br{bool=#b_literal{val=true},succ=Fail}; + #b_br{} -> + Br + end; +normalize(#b_switch{arg=Arg,fail=Fail,list=List}=Sw) -> + case Arg of + #b_literal{} -> + case keyfind(Arg, 1, List) of + false -> + #b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail}; + {Arg,L} -> + #b_br{bool=#b_literal{val=true},succ=L,fail=L} + end; + #b_var{} when List =:= [] -> + #b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail}; + #b_var{} -> + Sw + end; +normalize(#b_ret{}=Ret) -> + Ret. + -spec successors(label(), block_map()) -> [label()]. successors(L, Blocks) -> @@ -424,6 +488,20 @@ used(_) -> []. %%% Internal functions. %%% +is_commutative('and') -> true; +is_commutative('or') -> true; +is_commutative('xor') -> true; +is_commutative('band') -> true; +is_commutative('bor') -> true; +is_commutative('bxor') -> true; +is_commutative('+') -> true; +is_commutative('*') -> true; +is_commutative('=:=') -> true; +is_commutative('==') -> true; +is_commutative('=/=') -> true; +is_commutative('/=') -> true; +is_commutative(_) -> false. + def_used_1([#b_blk{is=Is,last=Last}|Bs], Preds, Def0, Used0) -> {Def,Used1} = def_used_is(Is, Preds, Def0, Used0), Used = gb_sets:union(gb_sets:from_list(used(Last)), Used1), -- cgit v1.2.3 From be092fb5fecfc382a45681d8de07fda27d77bf26 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 21 Aug 2018 08:17:24 +0200 Subject: Optimize 'and' and 'or' instructions --- lib/compiler/src/beam_ssa_codegen.erl | 14 ++++++++++- lib/compiler/src/beam_ssa_opt.erl | 45 ++++++++++++++++++++++++++++++----- lib/compiler/src/beam_ssa_type.erl | 5 ++++ lib/compiler/test/compile_SUITE.erl | 3 --- 4 files changed, 57 insertions(+), 10 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl index 006c41c0e0..becfe56b3a 100644 --- a/lib/compiler/src/beam_ssa_codegen.erl +++ b/lib/compiler/src/beam_ssa_codegen.erl @@ -1180,6 +1180,16 @@ cg_copy_1([#cg_set{dst=Dst0,args=Args}|T], St) -> end; cg_copy_1([], _St) -> []. +bif_to_test('and', [V1,V2], Fail) -> + [{test,is_eq_exact,Fail,[V1,{atom,true}]}, + {test,is_eq_exact,Fail,[V2,{atom,true}]}]; +bif_to_test('or', [V1,V2], {f,Lbl}=Fail) when Lbl =/= 0 -> + %% Labels are spaced 2 apart. We can create a new + %% label by incrementing the Fail label. + SuccLabel = Lbl + 1, + [{test,is_eq_exact,{f,SuccLabel},[V1,{atom,false}]}, + {test,is_eq_exact,Fail,[V2,{atom,true}]}, + {label,SuccLabel}]; bif_to_test('not', [Var], Fail) -> [{test,is_eq_exact,Fail,[Var,{atom,false}]}]; bif_to_test(Name, Args, Fail) -> @@ -1785,7 +1795,9 @@ is_gc_bif(Bif, Args) -> %% new_label(St) -> {L,St}. new_label(#cg{lcount=Next}=St) -> - {Next,St#cg{lcount=Next+1}}. + %% Advance the label counter by 2 to allow us to create + %% a label for 'or' by incrementing an existing label. + {Next,St#cg{lcount=Next+2}}. %% call_line(tail|body, Func, Anno) -> [] | [{line,...}]. %% Produce a line instruction if it will be needed by the diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index da466a3316..257e036719 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -941,6 +941,22 @@ misc_opt_is([#b_set{op=phi}=I0|Is], Sub0, Acc) -> false -> misc_opt_is(Is, Sub0, [I|Acc]) end; +misc_opt_is([#b_set{op={bif,'and'}}=I0], Sub, Acc) -> + #b_set{dst=Dst,args=Args} = I = sub(I0, Sub), + case eval_and(Args) of + error -> + misc_opt_is([], Sub, [I|Acc]); + Val -> + misc_opt_is([], Sub#{Dst=>Val}, Acc) + end; +misc_opt_is([#b_set{op={bif,'or'}}=I0], Sub, Acc) -> + #b_set{dst=Dst,args=Args} = I = sub(I0, Sub), + case eval_or(Args) of + error -> + misc_opt_is([], Sub, [I|Acc]); + Val -> + misc_opt_is([], Sub#{Dst=>Val}, Acc) + end; misc_opt_is([#b_set{}=I0|Is], Sub, Acc) -> #b_set{op=Op,dst=Dst,args=Args} = I = sub(I0, Sub), case make_literal(Op, Args) of @@ -973,6 +989,20 @@ make_literal_list([_|_], _) -> make_literal_list([], Acc) -> reverse(Acc). +eval_and(Args) -> + case Args of + [_,#b_literal{val=false}=Res] -> Res; + [Res,#b_literal{val=true}] -> Res; + [_,_] -> error + end. + +eval_or(Args) -> + case Args of + [Res,#b_literal{val=false}] -> Res; + [_,#b_literal{val=true}=Res] -> Res; + [_,_] -> error + end. + %%% %%% Merge blocks. %%% @@ -1283,20 +1313,23 @@ rel2fam(S0) -> S = sofs:rel2fam(S1), sofs:to_external(S). -sub(#b_set{op=phi,args=Args}=I, Sub) -> +sub(I, Sub) -> + beam_ssa:normalize(sub_1(I, Sub)). + +sub_1(#b_set{op=phi,args=Args}=I, Sub) -> I#b_set{args=[{sub_arg(A, Sub),P} || {A,P} <- Args]}; -sub(#b_set{args=Args}=I, Sub) -> +sub_1(#b_set{args=Args}=I, Sub) -> I#b_set{args=[sub_arg(A, Sub) || A <- Args]}; -sub(#b_br{bool=#b_var{}=Old}=Br, Sub) -> +sub_1(#b_br{bool=#b_var{}=Old}=Br, Sub) -> New = sub_arg(Old, Sub), Br#b_br{bool=New}; -sub(#b_switch{arg=#b_var{}=Old}=Sw, Sub) -> +sub_1(#b_switch{arg=#b_var{}=Old}=Sw, Sub) -> New = sub_arg(Old, Sub), Sw#b_switch{arg=New}; -sub(#b_ret{arg=#b_var{}=Old}=Ret, Sub) -> +sub_1(#b_ret{arg=#b_var{}=Old}=Ret, Sub) -> New = sub_arg(Old, Sub), Ret#b_ret{arg=New}; -sub(Last, _) -> Last. +sub_1(Last, _) -> Last. sub_arg(#b_remote{mod=Mod,name=Name}=Rem, Sub) -> Rem#b_remote{mod=sub_arg(Mod, Sub),name=sub_arg(Name, Sub)}; diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index ae926960bf..8ad520df63 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -449,6 +449,11 @@ type(succeeded, [#b_var{name=Src}], Ts, Ds) -> #b_set{op={bif,Bif},args=BifArgs} -> Types = get_types(BifArgs, Ts), case {Bif,Types} of + {BoolOp,[T1,T2]} when BoolOp =:= 'and'; BoolOp =:= 'or' -> + case t_is_boolean(T1) andalso t_is_boolean(T2) of + true -> t_atom(true); + false -> t_boolean() + end; {byte_size,[{binary,_}]} -> t_atom(true); {bit_size,[{binary,_}]} -> diff --git a/lib/compiler/test/compile_SUITE.erl b/lib/compiler/test/compile_SUITE.erl index 8d8fc23027..2ec0bfdf83 100644 --- a/lib/compiler/test/compile_SUITE.erl +++ b/lib/compiler/test/compile_SUITE.erl @@ -1250,11 +1250,8 @@ do_opt_guards_fun([]) -> []. is_exception(guard_SUITE, {'-complex_not/1-fun-4-',1}) -> true; is_exception(guard_SUITE, {'-complex_not/1-fun-5-',1}) -> true; is_exception(guard_SUITE, {bad_guards,1}) -> true; -is_exception(guard_SUITE, {bad_guards_2,2}) -> true; is_exception(guard_SUITE, {bad_guards_3,2}) -> true; -is_exception(guard_SUITE, {csemi7,3}) -> true; is_exception(guard_SUITE, {nested_not_2b,4}) -> true; -is_exception(guard_SUITE, {tricky_1,2}) -> true; is_exception(_, _) -> false. sys_pre_attributes(Config) -> -- cgit v1.2.3 From 4fa8e386984a120393ca7f028b892594a92fd44b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Mon, 27 Aug 2018 06:58:24 +0200 Subject: Use beam_ssa:normalize/1 in beam_ssa_type --- lib/compiler/src/beam_ssa_type.erl | 38 +++++++++++++++----------------------- 1 file changed, 15 insertions(+), 23 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 8ad520df63..2ba0f732f6 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -23,7 +23,7 @@ -include("beam_ssa.hrl"). -import(lists, [any/2,droplast/1,foldl/3,last/1,member/2, - reverse/1,search/2,sort/1]). + reverse/1,sort/1]). -define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}). @@ -115,7 +115,7 @@ opt_is([#b_set{op=phi,dst=#b_var{name=Dst},args=Args0}=I0|Is], Ts0, Ds0, Ls, Acc Ds = Ds0#{Dst=>I}, opt_is(Is, Ts, Ds, Ls, [I|Acc]); opt_is([#b_set{dst=#b_var{name=Dst}}=I0|Is], Ts0, Ds0, Ls, Acc) -> - I = simplify(I0, Ts0), + I = beam_ssa:normalize(simplify(I0, Ts0)), Ts = update_types(I, Ts0, Ds0), Ds = Ds0#{Dst=>I}, opt_is(Is, Ts, Ds, Ls, [I|Acc]); @@ -228,12 +228,12 @@ anno_float_arg(float) -> float; anno_float_arg(_) -> convert. opt_terminator(#b_br{bool=#b_literal{}}=Br, _Ts, _Ds) -> - Br; + beam_ssa:normalize(Br); opt_terminator(#b_br{bool=#b_var{name=V}=Var}=Br, Ts, Ds) -> BoolType = get_type(Var, Ts), case get_literal_from_type(BoolType) of #b_literal{}=BoolLit -> - Br#b_br{bool=BoolLit}; + beam_ssa:normalize(Br#b_br{bool=BoolLit}); none -> #{V:=Set} = Ds, case Set of @@ -249,19 +249,14 @@ opt_terminator(#b_br{bool=#b_var{name=V}=Var}=Br, Ts, Ds) -> simplify_not(Br, Ts, Ds) end end; -opt_terminator(#b_switch{arg=#b_literal{val=Val0}=Arg,fail=Fail,list=List}, - _Ts, _Ds) -> - {value,{_,L}} = search(fun({#b_literal{val=Val1},_}) -> - Val1 =:= Val0 - end, List ++ [{Arg,Fail}]), - #b_br{bool=#b_literal{val=true},succ=L,fail=L}; opt_terminator(#b_switch{arg=V}=Sw0, Ts, Ds) -> - case get_literal_from_type(Ts) of + Type = get_type(V, Ts), + case get_literal_from_type(Type) of #b_literal{}=Lit -> Sw = Sw0#b_switch{arg=Lit}, - opt_terminator(Sw, Ts, Ds); + beam_ssa:normalize(Sw); none -> - case get_type(V, Ts) of + case Type of #t_integer{elements={_,_}=Range} -> simplify_switch_int(Sw0, Range); Type -> @@ -271,18 +266,16 @@ opt_terminator(#b_switch{arg=V}=Sw0, Ts, Ds) -> #b_br{}=Br -> opt_terminator(Br, Ts, Ds); Sw -> - Sw + beam_ssa:normalize(Sw) end; false -> - Sw0 + beam_ssa:normalize(Sw0) end end end; opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> Ret. -update_successors(#b_br{bool=#b_literal{val=false},fail=S}, Ts, D) -> - update_successor(S, Ts, D); update_successors(#b_br{bool=#b_literal{val=true},succ=S}, Ts, D) -> update_successor(S, Ts, D); update_successors(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}, Ts, D0) -> @@ -582,8 +575,6 @@ will_succeed(is_tuple, Type) -> will_succeed(_, _) -> maybe. -band_type([#b_literal{val=Int},Other], Ts) when is_integer(Int) -> - band_type_1(Int, Other, Ts); band_type([Other,#b_literal{val=Int}], Ts) when is_integer(Int) -> band_type_1(Int, Other, Ts); band_type([_,_], _) -> t_integer(). @@ -667,17 +658,18 @@ simplify_switch_bool(#b_switch{arg=B,list=List0}=Sw, Ts, Ds) -> Sw end. -simplify_not(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}=Br, Ts, Ds) -> +simplify_not(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}=Br0, Ts, Ds) -> case Ds of #{V:=#b_set{op={bif,'not'},args=[Bool]}} -> case t_is_boolean(get_type(Bool, Ts)) of true -> - Br#b_br{bool=Bool,succ=Fail,fail=Succ}; + Br = Br0#b_br{bool=Bool,succ=Fail,fail=Succ}, + beam_ssa:normalize(Br); false -> - Br + Br0 end; #{} -> - Br + Br0 end. get_literals(Values, Ts) -> -- cgit v1.2.3 From b21098e88551580d8ab3a1e7502506e91a950ec4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Wed, 22 Aug 2018 16:14:15 +0200 Subject: beam_ssa: Extend linearize/1 to also adjust phi nodes Since beam_ssa:linearize/1 may remove blocks that are unreachable, adjust phi nodes to make sure that they don't refer to discarded blocks or to blocks that no longer branch to the phi node in question. --- lib/compiler/src/beam_ssa.erl | 36 ++++++++++++++++++++++++++++++++++-- 1 file changed, 34 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl index 548e73cf43..75d567ff87 100644 --- a/lib/compiler/src/beam_ssa.erl +++ b/lib/compiler/src/beam_ssa.erl @@ -103,7 +103,7 @@ -type cg_prim_op() :: 'bs_get' | 'bs_match_string' | 'bs_restore' | 'bs_skip' | 'copy' | 'put_tuple_arity' | 'put_tuple_element'. --import(lists, [foldl/3,keyfind/3,mapfoldl/3,reverse/1]). +-import(lists, [foldl/3,keyfind/3,mapfoldl/3,member/2,reverse/1]). -spec add_anno(Key, Value, Construct) -> Construct when Key :: atom(), @@ -376,6 +376,10 @@ fold_po(Fun, From, Acc0, Blocks) -> %% linearize(Blocks) -> [{BlockLabel,#b_blk{}}]. %% Linearize the intermediate representation of the code. +%% Unreachable blocks will be discarded, and phi nodes will +%% be adjusted so that they no longer refers to discarded +%% blocks or to blocks that no longer are predecessors of +%% the phi node block. -spec linearize(Blocks) -> Linear when Blocks :: block_map(), @@ -383,7 +387,8 @@ fold_po(Fun, From, Acc0, Blocks) -> linearize(Blocks) -> Seen = gb_sets:empty(), - {Linear,_} = linearize_1([0], Blocks, Seen, []), + {Linear0,_} = linearize_1([0], Blocks, Seen, []), + Linear = fix_phis(Linear0, #{}), Linear. -spec rpo(Blocks) -> [Label] when @@ -592,6 +597,33 @@ linearize_1([L|Ls], Blocks, Seen0, Acc0) -> linearize_1([], _, Seen, Acc) -> {Acc,Seen}. +fix_phis([{L,Blk0}|Bs], S) -> + Blk = case Blk0 of + #b_blk{is=[#b_set{op=phi}|_]=Is0} -> + Is = fix_phis_1(Is0, L, S), + Blk0#b_blk{is=Is}; + #b_blk{} -> + Blk0 + end, + Successors = successors(Blk), + [{L,Blk}|fix_phis(Bs, S#{L=>Successors})]; +fix_phis([], _) -> []. + +fix_phis_1([#b_set{op=phi,args=Args0}=I|Is], L, S) -> + Args = [{Val,Pred} || {Val,Pred} <- Args0, + is_successor(L, Pred, S)], + [I#b_set{args=Args}|fix_phis_1(Is, L, S)]; +fix_phis_1(Is, _, _) -> Is. + +is_successor(L, Pred, S) -> + case S of + #{Pred:=Successors} -> + member(L, Successors); + #{} -> + %% This block has been removed. + false + end. + rpo_1([L|Ls], Blocks, Seen0, Acc0) -> case gb_sets:is_member(L, Seen0) of true -> -- cgit v1.2.3 From 5ebd2c4e0a12af57287b0bba390fb226c7209fb1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Mon, 10 Sep 2018 15:01:05 +0200 Subject: beam_ssa: Add trim_unreachable/1 Add trim_unreachable/1 to remove unreachable blocks and adjust phi nodes. --- lib/compiler/src/beam_ssa.erl | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl index 75d567ff87..b0818b1092 100644 --- a/lib/compiler/src/beam_ssa.erl +++ b/lib/compiler/src/beam_ssa.erl @@ -33,6 +33,7 @@ rpo/1,rpo/2, split_blocks/3, successors/1,successors/2, + trim_unreachable/1, update_phi_labels/4,used/1]). -export_type([b_module/0,b_function/0,b_blk/0,b_set/0, @@ -448,6 +449,19 @@ split_blocks(P, Blocks, Count) -> Ls = beam_ssa:rpo(Blocks), split_blocks_1(Ls, P, Blocks, Count). +-spec trim_unreachable(Blocks0) -> Blocks when + Blocks0 :: block_map(), + Blocks :: block_map(). + +%% trim_unreachable(Blocks0) -> Blocks. +%% Remove all unreachable blocks. Adjust all phi nodes so +%% they don't refer to blocks that has been removed or no +%% no longer branch to the phi node in question. + +trim_unreachable(Blocks) -> + %% Could perhaps be optimized if there is any need. + maps:from_list(linearize(Blocks)). + %% update_phi_labels([BlockLabel], Old, New, Blocks0) -> Blocks. %% In the given blocks, replace label Old in with New in all %% phi nodes. This is useful after merging or splitting -- cgit v1.2.3 From ecbe1327a5da4ecc02cdbc636bd54d901b92c215 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Wed, 5 Sep 2018 06:57:36 +0200 Subject: beam_ssa: Optimize linearize/1 and rpo/2 It is faster to use cerl_sets instead of gb_sets to keep track of seen blocks. --- lib/compiler/src/beam_ssa.erl | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl index b0818b1092..2ce00990e0 100644 --- a/lib/compiler/src/beam_ssa.erl +++ b/lib/compiler/src/beam_ssa.erl @@ -387,7 +387,7 @@ fold_po(Fun, From, Acc0, Blocks) -> Linear :: [{label(),b_blk()}]. linearize(Blocks) -> - Seen = gb_sets:empty(), + Seen = cerl_sets:new(), {Linear0,_} = linearize_1([0], Blocks, Seen, []), Linear = fix_phis(Linear0, #{}), Linear. @@ -405,7 +405,7 @@ rpo(Blocks) -> Labels :: [label()]. rpo(From, Blocks) -> - Seen = gb_sets:empty(), + Seen = cerl_sets:new(), {Ls,_} = rpo_1(From, Blocks, Seen, []), Ls. @@ -416,7 +416,7 @@ rename_vars(Rename, From, Blocks) when is_list(Rename) -> rename_vars(maps:from_list(Rename), From, Blocks); rename_vars(Rename, From, Blocks) when is_map(Rename)-> Top = rpo(From, Blocks), - Preds = gb_sets:from_list(Top), + Preds = cerl_sets:from_list(Top), F = fun(#b_set{op=phi,args=Args0}=Set) -> Args = rename_phi_vars(Args0, Preds, Rename), Set#b_set{args=Args}; @@ -598,11 +598,11 @@ flatmapfold_instrs_rpo_1([], _, Blocks, Acc) -> {Blocks,Acc}. linearize_1([L|Ls], Blocks, Seen0, Acc0) -> - case gb_sets:is_member(L, Seen0) of + case cerl_sets:is_element(L, Seen0) of true -> linearize_1(Ls, Blocks, Seen0, Acc0); false -> - Seen1 = gb_sets:insert(L, Seen0), + Seen1 = cerl_sets:add_element(L, Seen0), Block = maps:get(L, Blocks), Successors = successors(Block), {Acc,Seen} = linearize_1(Successors, Blocks, Seen1, Acc0), @@ -639,12 +639,12 @@ is_successor(L, Pred, S) -> end. rpo_1([L|Ls], Blocks, Seen0, Acc0) -> - case gb_sets:is_member(L, Seen0) of + case cerl_sets:is_element(L, Seen0) of true -> rpo_1(Ls, Blocks, Seen0, Acc0); false -> Block = maps:get(L, Blocks), - Seen1 = gb_sets:insert(L, Seen0), + Seen1 = cerl_sets:add_element(L, Seen0), Successors = successors(Block), {Acc,Seen} = rpo_1(Successors, Blocks, Seen1, Acc0), rpo_1(Ls, Blocks, Seen, [L|Acc]) @@ -664,7 +664,7 @@ rename_var(#b_remote{mod=Mod0,name=Name0}=Remote, Rename) -> rename_var(Old, _) -> Old. rename_phi_vars([{Var,L}|As], Preds, Ren) -> - case gb_sets:is_member(L, Preds) of + case cerl_sets:is_element(L, Preds) of true -> [{rename_var(Var, Ren),L}|rename_phi_vars(As, Preds, Ren)]; false -> -- cgit v1.2.3 From 52abce861178bbce0dc3acb22cc8935f9a434981 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 24 Aug 2018 14:14:09 +0200 Subject: Move two optimizations from beam_dead to beam_a The 'move' instruction can be eliminated in code such as: {test,is_eq_exact,{f,42},[{x,0},{atom,value}]}. {move,{atom,value},{x,0}}. Move that optimization from beam_dead to beam_a. The optimization will be simpler because the 'move' instruction has not yet been moved into a block. Getting rid of 'move' earlier will also save work for later passes. Also move the optimization that eliminates instructions such as from beam_dead to beam_a: {test_is_eq_exact,{f,42},[{x,0},{x,0}]}. --- lib/compiler/src/beam_a.erl | 7 +++++++ lib/compiler/src/beam_dead.erl | 15 --------------- 2 files changed, 7 insertions(+), 15 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_a.erl b/lib/compiler/src/beam_a.erl index 266e8f46c8..0abc845310 100644 --- a/lib/compiler/src/beam_a.erl +++ b/lib/compiler/src/beam_a.erl @@ -52,6 +52,13 @@ function({function,Name,Arity,CLabel,Is0}) -> erlang:raise(Class, Error, Stack) end. +rename_instrs([{test,is_eq_exact,_,[Dst,Src]}=Test, + {move,Src,Dst}|Is]) -> + %% The move instruction is not needed. + rename_instrs([Test|Is]); +rename_instrs([{test,is_eq_exact,_,[Same,Same]}|Is]) -> + %% Same literal or same register. Will always succeed. + rename_instrs(Is); rename_instrs([{apply_last,A,N}|Is]) -> [{apply,A},{deallocate,N},return|rename_instrs(Is)]; rename_instrs([{call_last,A,F,N}|Is]) -> diff --git a/lib/compiler/src/beam_dead.erl b/lib/compiler/src/beam_dead.erl index 546f0461b9..f57bed0658 100644 --- a/lib/compiler/src/beam_dead.erl +++ b/lib/compiler/src/beam_dead.erl @@ -80,11 +80,6 @@ move_move_into_block([], Acc) -> reverse(Acc). %%% the register already contains the value being assigned, as in the %%% following code: %%% -%%% test is_eq_exact SomeLabel Src Dst -%%% move Src Dst -%%% -%%% or in: -%%% %%% select_val Register FailLabel [... Literal => L1...] %%% . %%% . @@ -103,9 +98,6 @@ forward([{move,_,_}=Move|[{label,L}|_]=Is], D, Lc, Acc) -> forward([{bif,_,_,_,_}=Bif|[{label,L}|_]=Is], D, Lc, Acc) -> %% bif/4 followed by jump/1 is optimized by backward/3. forward([Bif,{jump,{f,L}}|Is], D, Lc, Acc); -forward([{block,[]}|Is], D, Lc, Acc) -> - %% Empty blocks can prevent optimizations. - forward(Is, D, Lc, Acc); forward([{select,select_val,Reg,_,List}=I|Is], D0, Lc, Acc) -> D = update_value_dict(List, Reg, D0), forward(Is, D, Lc, [I|Acc]); @@ -130,13 +122,6 @@ forward([{label,Lbl}=LblI|[{move,Lit,Dst}|Is1]=Is0], D, Lc, Acc) -> _ -> Is0 %Keep move instruction. end, forward(Is, D, Lc, [LblI|Acc]); -forward([{test,is_eq_exact,_,[Same,Same]}|Is], D, Lc, Acc) -> - forward(Is, D, Lc, Acc); -forward([{test,is_eq_exact,_,[Dst,Src]}=I, - {block,[{set,[Dst],[Src],move}|Bl]}|Is], D, Lc, Acc) -> - forward([I,{block,Bl}|Is], D, Lc, Acc); -forward([{test,is_eq_exact,_,[Dst,Src]}=I,{move,Src,Dst}|Is], D, Lc, Acc) -> - forward([I|Is], D, Lc, Acc); forward([{test,_,_,_}=I|Is]=Is0, D, Lc, Acc) -> %% Help the second, backward pass to by inserting labels after %% relational operators so that they can be skipped if they are -- cgit v1.2.3 From 56a6c76f84666e3b1e0336b7eb3dfda15a1ec908 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 24 Aug 2018 14:39:36 +0200 Subject: Introduce the beam_jump:instr_labels/1 function This functionality will soon be needed. --- lib/compiler/src/beam_jump.erl | 120 +++++++++++++++++++++++------------------ 1 file changed, 69 insertions(+), 51 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl index 42b4cdaf4f..06f3cc19bb 100644 --- a/lib/compiler/src/beam_jump.erl +++ b/lib/compiler/src/beam_jump.erl @@ -23,7 +23,7 @@ -export([module/2, is_unreachable_after/1,is_exit_instruction/1, - remove_unused_labels/1]). + remove_unused_labels/1,instr_labels/1]). %%% The following optimisations are done: %%% @@ -571,58 +571,76 @@ drop_upto_label([{label,_}|_]=Is) -> Is; drop_upto_label([_|Is]) -> drop_upto_label(Is); drop_upto_label([]) -> []. -%% ulbl(Instruction, UsedGbSet) -> UsedGbSet' -%% Update the gb_set UsedGbSet with any function-local labels +%% ulbl(Instruction, UsedCerlSet) -> UsedCerlSet' +%% Update the cerl_set UsedCerlSet with any function-local labels %% (i.e. not with labels in call instructions) referenced by %% the instruction Instruction. %% %% NOTE: This function does NOT look for labels inside blocks. -ulbl({test,_,Fail,_}, Used) -> - mark_used(Fail, Used); -ulbl({test,_,Fail,_,_,_}, Used) -> - mark_used(Fail, Used); -ulbl({select,_,_,Fail,Vls}, Used) -> - mark_used_list(Vls, mark_used(Fail, Used)); -ulbl({'try',_,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({'catch',_,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({jump,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({loop_rec,Lbl,_}, Used) -> - mark_used(Lbl, Used); -ulbl({loop_rec_end,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({wait,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({wait_timeout,Lbl,_To}, Used) -> - mark_used(Lbl, Used); -ulbl({bif,_Name,Lbl,_As,_R}, Used) -> - mark_used(Lbl, Used); -ulbl({gc_bif,_Name,Lbl,_Live,_As,_R}, Used) -> - mark_used(Lbl, Used); -ulbl({bs_init,Lbl,_,_,_,_}, Used) -> - mark_used(Lbl, Used); -ulbl({bs_put,Lbl,_,_}, Used) -> - mark_used(Lbl, Used); -ulbl({put_map,Lbl,_Op,_Src,_Dst,_Live,_List}, Used) -> - mark_used(Lbl, Used); -ulbl({get_map_elements,Lbl,_Src,_List}, Used) -> - mark_used(Lbl, Used); -ulbl({recv_mark,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({recv_set,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({fcheckerror,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl(_, Used) -> Used. - -mark_used({f,0}, Used) -> Used; -mark_used({f,L}, Used) -> cerl_sets:add_element(L, Used). - -mark_used_list([{f,L}|T], Used) -> - mark_used_list(T, cerl_sets:add_element(L, Used)); -mark_used_list([_|T], Used) -> - mark_used_list(T, Used); -mark_used_list([], Used) -> Used. +ulbl(I, Used) -> + case instr_labels(I) of + [] -> + Used; + [Lbl] -> + cerl_sets:add_element(Lbl, Used); + [_|_]=L -> + ulbl_list(L, Used) + end. + +ulbl_list([L|Ls], Used) -> + ulbl_list(Ls, cerl_sets:add_element(L, Used)); +ulbl_list([], Used) -> Used. + +-spec instr_labels(Instruction) -> Labels when + Instruction :: instruction(), + Labels :: [beam_asm:label()]. + +instr_labels({test,_,Fail,_}) -> + do_instr_labels(Fail); +instr_labels({test,_,Fail,_,_,_}) -> + do_instr_labels(Fail); +instr_labels({select,_,_,Fail,Vls}) -> + do_instr_labels_list(Vls, do_instr_labels(Fail)); +instr_labels({'try',_,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({'catch',_,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({jump,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({loop_rec,Lbl,_}) -> + do_instr_labels(Lbl); +instr_labels({loop_rec_end,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({wait,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({wait_timeout,Lbl,_To}) -> + do_instr_labels(Lbl); +instr_labels({bif,_Name,Lbl,_As,_R}) -> + do_instr_labels(Lbl); +instr_labels({gc_bif,_Name,Lbl,_Live,_As,_R}) -> + do_instr_labels(Lbl); +instr_labels({bs_init,Lbl,_,_,_,_}) -> + do_instr_labels(Lbl); +instr_labels({bs_put,Lbl,_,_}) -> + do_instr_labels(Lbl); +instr_labels({put_map,Lbl,_Op,_Src,_Dst,_Live,_List}) -> + do_instr_labels(Lbl); +instr_labels({get_map_elements,Lbl,_Src,_List}) -> + do_instr_labels(Lbl); +instr_labels({recv_mark,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({recv_set,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({fcheckerror,Lbl}) -> + do_instr_labels(Lbl); +instr_labels(_) -> []. + +do_instr_labels({f,0}) -> []; +do_instr_labels({f,F}) -> [F]. + +do_instr_labels_list([{f,F}|T], Acc) -> + do_instr_labels_list(T, [F|Acc]); +do_instr_labels_list([_|T], Acc) -> + do_instr_labels_list(T, Acc); +do_instr_labels_list([], Acc) -> Acc. -- cgit v1.2.3 From 71182c868e97dac0833c710c033fde871eb3a8f0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 24 Aug 2018 15:20:01 +0200 Subject: Fix unsafe optimization in beam_dead Those optimizations are unsafe if beam_dead has been run before. --- lib/compiler/src/beam_dead.erl | 71 ++++++++++++++++++++++++++++-------------- 1 file changed, 48 insertions(+), 23 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_dead.erl b/lib/compiler/src/beam_dead.erl index f57bed0658..901ef5dc39 100644 --- a/lib/compiler/src/beam_dead.erl +++ b/lib/compiler/src/beam_dead.erl @@ -101,39 +101,56 @@ forward([{bif,_,_,_,_}=Bif|[{label,L}|_]=Is], D, Lc, Acc) -> forward([{select,select_val,Reg,_,List}=I|Is], D0, Lc, Acc) -> D = update_value_dict(List, Reg, D0), forward(Is, D, Lc, [I|Acc]); -forward([{label,Lbl}=LblI,{block,[{set,[Dst],[Lit],move}|BlkIs]}=Blk|Is], D, Lc, Acc) -> - %% Assumption: The target labels in a select_val/3 instruction - %% cannot be reached in any other way than through the select_val/3 - %% instruction (i.e. there can be no fallthrough to such label and - %% it cannot be referenced by, for example, a jump/1 instruction). - Key = {Lbl,Dst}, - Block = case D of - #{Key := Lit} -> {block,BlkIs}; %Safe to remove move instruction. - _ -> Blk %Must keep move instruction. - end, - forward([Block|Is], D, Lc, [LblI|Acc]); -forward([{label,Lbl}=LblI|[{move,Lit,Dst}|Is1]=Is0], D, Lc, Acc) -> - %% Assumption: The target labels in a select_val/3 instruction - %% cannot be reached in any other way than through the select_val/3 - %% instruction (i.e. there can be no fallthrough to such label and - %% it cannot be referenced by, for example, a jump/1 instruction). - Is = case maps:find({Lbl,Dst}, D) of - {ok,Lit} -> Is1; %Safe to remove move instruction. - _ -> Is0 %Keep move instruction. - end, - forward(Is, D, Lc, [LblI|Acc]); -forward([{test,_,_,_}=I|Is]=Is0, D, Lc, Acc) -> +forward([{label,Lbl},{block,[{set,[Dst],[Lit],move}|BlkIs]}=Blk0|Is], + D, Lc, Acc0) -> + Acc = [{label,Lbl}|Acc0], + case already_has_value(Lit, Lbl, Dst, D) andalso + no_fallthrough(Acc0) of + true -> + Blk = {block,BlkIs}, + forward([Blk|Is], D, Lc, Acc); + false -> + forward([Blk0|Is], D, Lc, Acc) + end; +forward([{label,Lbl},{move,Lit,Dst}=Move|Is], D, Lc, Acc0) -> + Acc = [{label,Lbl}|Acc0], + case already_has_value(Lit, Lbl, Dst, D) andalso + no_fallthrough(Acc0) of + true -> + %% Remove redundant 'move' instruction. + forward(Is, D, Lc, Acc); + false -> + %% Keep 'move' instruction. + forward([Move|Is], D, Lc, Acc) + end; +forward([{test,_,_,_}=I|Is]=Is0, D0, Lc, Acc) -> %% Help the second, backward pass to by inserting labels after %% relational operators so that they can be skipped if they are %% known to be true. + D = update_unsafe_labels(I, D0), case useful_to_insert_label(Is0) of false -> forward(Is, D, Lc, [I|Acc]); true -> forward(Is, D, Lc+1, [{label,Lc},I|Acc]) end; -forward([I|Is], D, Lc, Acc) -> +forward([I|Is], D0, Lc, Acc) -> + D = update_unsafe_labels(I, D0), forward(Is, D, Lc, [I|Acc]); forward([], _, Lc, Acc) -> {Acc,Lc}. +no_fallthrough([I|_]) -> + beam_jump:is_unreachable_after(I). + +already_has_value(Lit, Lbl, Reg, D) -> + Key = {Lbl,Reg}, + case D of + #{Lbl:=unsafe} -> + false; + #{Key:=Lit} -> + true; + #{} -> + false + end. + update_value_dict([Lit,{f,Lbl}|T], Reg, D0) -> Key = {Lbl,Reg}, D = case D0 of @@ -144,6 +161,14 @@ update_value_dict([Lit,{f,Lbl}|T], Reg, D0) -> update_value_dict(T, Reg, D); update_value_dict([], _, D) -> D. +update_unsafe_labels(I, D) -> + Ls = beam_jump:instr_labels(I), + update_unsafe_labels_1(Ls, D). + +update_unsafe_labels_1([L|Ls], D) -> + update_unsafe_labels_1(Ls, D#{L=>unsafe}); +update_unsafe_labels_1([], D) -> D. + useful_to_insert_label([_,{label,_}|_]) -> false; useful_to_insert_label([{test,Op,_,_}|_]) -> -- cgit v1.2.3 From 8e4f23224a90d35683dbd45007682c861c4eb354 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 30 Aug 2018 06:55:37 +0200 Subject: beam_peep: Add is_boolean optimization of select_val A select_val instruction that test whether a register is a boolean like this: {select_val,Reg,{f,Fail},{list,[{atom,true},Lbl,{atom,false},Lbl]}}. can be replaced with an is_boolean test: {test,is_boolean,{f,Fail},[Reg]}. {jump,{f,Lbl}}. This optimization is currently done in beam_dead. However, if done in the beam_peep, it can catch more opportunities to do the optimization, because after having run beam_jump, labels that were different have been coalesced. --- lib/compiler/src/beam_peep.erl | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'lib') diff --git a/lib/compiler/src/beam_peep.erl b/lib/compiler/src/beam_peep.erl index 74da6aa704..2323a439e9 100644 --- a/lib/compiler/src/beam_peep.erl +++ b/lib/compiler/src/beam_peep.erl @@ -112,6 +112,10 @@ peep([{select,Op,R,F,Vls0}|Is], SeenTests0, Acc0) -> %% Single value left. Convert to regular test Is1 = [{test,test_arity,F,[R,Arity]},{jump,Lbl}|Is], peep(Is1, SeenTests0, Acc0); + [{atom,B1},Lbl,{atom,B2},Lbl] when B1 =:= not B2 -> + %% Replace with is_boolean test. + Is1 = [{test,is_boolean,F,[R]},{jump,Lbl}|Is], + peep(Is1, SeenTests0, Acc0); [_|_]=Vls -> I = {select,Op,R,F,Vls}, peep(Is, gb_sets:empty(), [I|Acc0]) -- cgit v1.2.3 From 07dd8d0a1632d446f5bc4bde9cc10fb1b112f4a1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sat, 25 Aug 2018 10:21:17 +0200 Subject: beam_ssa_opt: Fix liveness optimization Add more instructions to the list of functions that can be safely removed if their values are not used. This is necessary for correctness when doing more aggressive optimizations. Without this change, the 'succeeded' instruction could be optimized away leaving just the instruction followed by an unconditional branch, which the beam_ssa_codegen does not know how to handle. Here is an example: _3 = bs_start_match _1 br label 13 By adding bs_start_match to the list, the bs_start_match instruction will be removed too. (If the result of bs_start_match is actually used, the succeeded instruction would not be removed.) While we are it, rename the misnamed function is_pure/1 to no_side_effect/1 and move it to beam_ssa. is_pure/1 is a bad name because bif:get has no side effect, but is not pure. --- lib/compiler/src/beam_ssa.erl | 32 ++++++++++++++++++++++++++++++++ lib/compiler/src/beam_ssa_opt.erl | 17 ++--------------- lib/compiler/test/match_SUITE.erl | 12 ++++++++++++ 3 files changed, 46 insertions(+), 15 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl index 2ce00990e0..fc13ba06de 100644 --- a/lib/compiler/src/beam_ssa.erl +++ b/lib/compiler/src/beam_ssa.erl @@ -28,6 +28,7 @@ linearize/1, mapfold_instrs_rpo/4, normalize/1, + no_side_effect/1, predecessors/1, rename_vars/3, rpo/1,rpo/2, @@ -152,6 +153,37 @@ clobbers_xregs(#b_set{op=Op}) -> _ -> false end. +%% no_side_effect(#b_set{}) -> true|false. +%% Test whether this instruction has no side effect and thus is safe +%% not to execute if its value is not used. Note that even if `true` +%% is returned, the instruction could still be impure (e.g. bif:get). + +-spec no_side_effect(b_set()) -> boolean(). + +no_side_effect(#b_set{op=Op}) -> + case Op of + {bif,_} -> true; + {float,get} -> true; + bs_init -> true; + bs_extract -> true; + bs_match -> true; + bs_start_match -> true; + bs_test_tail -> true; + bs_put -> true; + extract -> true; + get_hd -> true; + get_tl -> true; + get_tuple_element -> true; + has_map_field -> true; + is_nonempty_list -> true; + is_tagged_tuple -> true; + put_map -> true; + put_list -> true; + put_tuple -> true; + succeeded -> true; + _ -> false + end. + -spec predecessors(Blocks) -> #{BlockNumber:=[Predecessor]} when Blocks :: block_map(), BlockNumber :: label(), diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 257e036719..5f3777072a 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -769,14 +769,14 @@ live_opt_is([#b_set{op=succeeded,dst=#b_var{name=SuccDst}=SuccDstVar, end end end; -live_opt_is([#b_set{op=Op,dst=#b_var{name=Dst}}=I|Is], Live0, Acc) -> +live_opt_is([#b_set{dst=#b_var{name=Dst}}=I|Is], Live0, Acc) -> case gb_sets:is_member(Dst, Live0) of true -> Live1 = gb_sets:union(Live0, gb_sets:from_ordset(beam_ssa:used(I))), Live = gb_sets:delete_any(Dst, Live1), live_opt_is(Is, Live, [I|Acc]); false -> - case is_pure(Op) of + case beam_ssa:no_side_effect(I) of true -> live_opt_is(Is, Live0, Acc); false -> @@ -787,19 +787,6 @@ live_opt_is([#b_set{op=Op,dst=#b_var{name=Dst}}=I|Is], Live0, Acc) -> live_opt_is([], Live, Acc) -> {Acc,Live}. -is_pure({bif,_}) -> true; -is_pure({float,get}) -> true; -is_pure(bs_extract) -> true; -is_pure(extract) -> true; -is_pure(get_hd) -> true; -is_pure(get_tl) -> true; -is_pure(get_tuple_element) -> true; -is_pure(is_nonempty_list) -> true; -is_pure(is_tagged_tuple) -> true; -is_pure(put_list) -> true; -is_pure(put_tuple) -> true; -is_pure(_) -> false. - live_opt_unused(#b_set{op=get_map_element}=Set) -> {replace,Set#b_set{op=has_map_field}}; live_opt_unused(_) -> keep. diff --git a/lib/compiler/test/match_SUITE.erl b/lib/compiler/test/match_SUITE.erl index e3f842b668..46b543728d 100644 --- a/lib/compiler/test/match_SUITE.erl +++ b/lib/compiler/test/match_SUITE.erl @@ -254,6 +254,8 @@ non_matching_aliases(_Config) -> none = mixed_aliases([d]), none = mixed_aliases({a,42}), none = mixed_aliases(42), + none = mixed_aliases(<<6789:16>>), + none = mixed_aliases(#{key=>value}), {'EXIT',{{badmatch,42},_}} = (catch nomatch_alias(42)), {'EXIT',{{badmatch,job},_}} = (catch entirely()), @@ -279,6 +281,16 @@ mixed_aliases(<> = x) -> {a,X}; mixed_aliases([b] = <>) -> {b,X}; mixed_aliases(<> = {a,X}) -> {c,X}; mixed_aliases([X] = <>) -> {d,X}; +mixed_aliases(<> = X) -> {e,X}; +mixed_aliases(X = <>) -> {f,X}; +mixed_aliases(<> = X) -> {g,X}; +mixed_aliases(X = <>) -> {h,X}; +mixed_aliases(X = #{key:=X}) -> {i,X}; +mixed_aliases(#{key:=X} = X) -> {j,X}; +mixed_aliases([X] = #{key:=X}) -> {k,X}; +mixed_aliases(#{key:=X} = [X]) -> {l,X}; +mixed_aliases({a,X} = #{key:=X}) -> {m,X}; +mixed_aliases(#{key:=X} = {a,X}) -> {n,X}; mixed_aliases(_) -> none. nomatch_alias(I) -> -- cgit v1.2.3 From c49e888ecdebab753500a1f17c62849a13a18a85 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 28 Aug 2018 16:11:45 +0200 Subject: beam_ssa_opt: Add a pass for coalescing phi nodes Nested cases can led to code such as this: 10: _1 = phi {literal value1, label 8}, {Var, label 9} br 11 11: _2 = phi {_1, label 10}, {literal false, label 3} The phi nodes can be coalesced like this: 11: _2 = phi {literal value1, label 8}, {Var, label 9}, {literal false, label 3} Coalescing can help other optimizations, and can in some cases reduce register shuffling (if the phi variables for two phi nodes happens to be allocated to different registers). --- lib/compiler/src/beam_ssa_opt.erl | 97 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 97 insertions(+) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 5f3777072a..bb9c316f50 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -48,6 +48,7 @@ functions([], _Ps) -> []. passes(Opts0) -> Ps = [?PASS(ssa_opt_split_blocks), + ?PASS(ssa_opt_coalesce_phis), ?PASS(ssa_opt_element), ?PASS(ssa_opt_linearize), ?PASS(ssa_opt_record), @@ -116,6 +117,102 @@ ssa_opt_split_blocks(#st{ssa=Blocks0,cnt=Count0}=St) -> {Blocks,Count} = beam_ssa:split_blocks(P, Blocks0, Count0), St#st{ssa=Blocks,cnt=Count}. +%%% +%%% Coalesce phi nodes. +%%% +%%% Nested cases can led to code such as this: +%%% +%%% 10: +%%% _1 = phi {literal value1, label 8}, {Var, label 9} +%%% br 11 +%%% +%%% 11: +%%% _2 = phi {_1, label 10}, {literal false, label 3} +%%% +%%% The phi nodes can be coalesced like this: +%%% +%%% 11: +%%% _2 = phi {literal value1, label 8}, {Var, label 9}, {literal false, label 3} +%%% +%%% Coalescing can help other optimizations, and can in some cases reduce register +%%% shuffling (if the phi variables for two phi nodes happens to be allocated to +%%% different registers). +%%% + +ssa_opt_coalesce_phis(#st{ssa=Blocks0}=St) -> + Ls = beam_ssa:rpo(Blocks0), + Blocks = c_phis_1(Ls, Blocks0), + St#st{ssa=Blocks}. + +c_phis_1([L|Ls], Blocks0) -> + case maps:get(L, Blocks0) of + #b_blk{is=[#b_set{op=phi}|_]}=Blk -> + Blocks = c_phis_2(L, Blk, Blocks0), + c_phis_1(Ls, Blocks); + #b_blk{} -> + c_phis_1(Ls, Blocks0) + end; +c_phis_1([], Blocks) -> Blocks. + +c_phis_2(L, #b_blk{is=Is0}=Blk0, Blocks0) -> + case c_phis_args(Is0, Blocks0) of + none -> + Blocks0; + {_,_,Preds}=Info -> + Is = c_rewrite_phis(Is0, Info), + Blk = Blk0#b_blk{is=Is}, + Blocks = Blocks0#{L:=Blk}, + c_fix_branches(Preds, L, Blocks) + end. + +c_phis_args([#b_set{op=phi,args=Args0}|Is], Blocks) -> + case c_phis_args_1(Args0, Blocks) of + none -> + c_phis_args(Is, Blocks); + Res -> + Res + end; +c_phis_args(_, _Blocks) -> none. + +c_phis_args_1([{Var,Pred}|As], Blocks) -> + case c_get_pred_vars(Var, Pred, Blocks) of + none -> + c_phis_args_1(As, Blocks); + Result -> + Result + end; +c_phis_args_1([], _Blocks) -> none. + +c_get_pred_vars(Var, Pred, Blocks) -> + case maps:get(Pred, Blocks) of + #b_blk{is=[#b_set{op=phi,dst=Var,args=Args}]} -> + {Var,Pred,Args}; + #b_blk{} -> + none + end. + +c_rewrite_phis([#b_set{op=phi,args=Args0}=I|Is], Info) -> + Args = c_rewrite_phi(Args0, Info), + [I#b_set{args=Args}|c_rewrite_phis(Is, Info)]; +c_rewrite_phis(Is, _Info) -> Is. + +c_rewrite_phi([{Var,Pred}|As], {Var,Pred,Values}) -> + Values ++ As; +c_rewrite_phi([{Value,Pred}|As], {_,Pred,Values}) -> + [{Value,P} || {_,P} <- Values] ++ As; +c_rewrite_phi([A|As], Info) -> + [A|c_rewrite_phi(As, Info)]; +c_rewrite_phi([], _Info) -> []. + +c_fix_branches([{_,Pred}|As], L, Blocks0) -> + #b_blk{last=Last0} = Blk0 = maps:get(Pred, Blocks0), + #b_br{bool=#b_literal{val=true}} = Last0, %Assertion. + Last = Last0#b_br{bool=#b_literal{val=true},succ=L,fail=L}, + Blk = Blk0#b_blk{last=Last}, + Blocks = Blocks0#{Pred:=Blk}, + c_fix_branches(As, L, Blocks); +c_fix_branches([], _, Blocks) -> Blocks. + %%% %%% Order element/2 calls. %%% -- cgit v1.2.3 From f89331e61b5b6fc6eadc289d4ce126d6a4219238 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 30 Aug 2018 05:22:13 +0200 Subject: beam_ssa_opt: Add simplification of switch lists When the argument for a #b_switch{} comes from a phi node with only literal values, the switch list could be pruned to only contain the possible values. It could also be possible to eliminate the failure label. Also simplify a switch with a single value list or switch that can be replaced with an is_boolean test. --- lib/compiler/src/beam_ssa_opt.erl | 105 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 105 insertions(+) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index bb9c316f50..67c92d5ae2 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -59,6 +59,7 @@ passes(Opts0) -> ?PASS(ssa_opt_bsm), ?PASS(ssa_opt_bsm_shortcut), ?PASS(ssa_opt_misc), + ?PASS(ssa_opt_sw), ?PASS(ssa_opt_blockify), ?PASS(ssa_opt_sink), ?PASS(ssa_opt_merge_blocks)], @@ -1087,6 +1088,110 @@ eval_or(Args) -> [_,_] -> error end. +%%% +%%% Optimize #b_switch{} instructions. +%%% +%%% If the argument for a #b_switch{} comes from a phi node with all +%%% literals, any values in the switch list which are not in the phi +%%% node can be removed. +%%% +%%% If the values in the phi node and switch list are the same, +%%% the failure label can't be reached and be eliminated. +%%% +%%% A #b_switch{} with only one value can be rewritten to +%%% a #b_br{}. A switch that only verifies that the argument +%%% is 'true' or 'false' can be rewritten to a is_boolean test. +%%% + +ssa_opt_sw(#st{ssa=Linear0,cnt=Count0}=St) -> + {Linear,Count} = opt_sw(Linear0, #{}, Count0, []), + St#st{ssa=Linear,cnt=Count}. + +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 + #b_switch{arg=Arg,fail=Fail,list=[{Lit,Lbl}]} -> + %% Rewrite a single value switch to a br. + Bool = #b_var{name={'@ssa_bool',Count0}}, + Count = Count0 + 1, + 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]); + #b_switch{arg=Arg,fail=Fail, + list=[{#b_literal{val=B1},Lbl},{#b_literal{val=B2},Lbl}]} + when B1 =:= not B2 -> + %% Replace with is_boolean test. + Bool = #b_var{name={'@ssa_bool',Count0}}, + Count = Count0 + 1, + 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]) + 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) -> + {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. %%% -- cgit v1.2.3 From 4edd266876f2383ccc33b91a3bbe8550279368f5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 31 Aug 2018 07:13:05 +0200 Subject: beam_ssa_opt: Add an optimization of tuple_size/1 This optimization working on the SSA format will replace the similar optimization in beam_dead. See the comment for an explanation of what the new optimization does. --- lib/compiler/src/beam_ssa_opt.erl | 121 +++++++++++++++++++++ lib/compiler/test/guard_SUITE.erl | 10 -- .../test/guard_SUITE_data/guard_SUITE_tuple_size.S | 30 ----- 3 files changed, 121 insertions(+), 40 deletions(-) delete mode 100644 lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 67c92d5ae2..0bb4a204a2 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -59,6 +59,7 @@ passes(Opts0) -> ?PASS(ssa_opt_bsm), ?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), @@ -1088,6 +1089,126 @@ eval_or(Args) -> [_,_] -> error end. +%%% +%%% Optimize expressions such as "tuple_size(Var) =:= 2". +%%% +%%% Consider this code: +%%% +%%% 0: +%%% . +%%% . +%%% . +%%% Size = bif:tuple_size Var +%%% BoolVar1 = succeeded Size +%%% br BoolVar1, label 4, label 3 +%%% +%%% 4: +%%% BoolVar2 = bif:'=:=' Size, literal 2 +%%% br BoolVar2, label 6, label 3 +%%% +%%% 6: ... %% OK +%%% +%%% 3: ... %% Not a tuple of size 2 +%%% +%%% The BEAM code will look this: +%%% +%%% {bif,tuple_size,{f,3},[{x,0}],{x,0}}. +%%% {test,is_eq_exact,{f,3},[{x,0},{integer,2}]}. +%%% +%%% Better BEAM code will be produced if we transform the +%%% code like this: +%%% +%%% 0: +%%% . +%%% . +%%% . +%%% br label 10 +%%% +%%% 10: +%%% NewBoolVar = bif:is_tuple Var +%%% br NewBoolVar, label 11, label 3 +%%% +%%% 11: +%%% Size = bif:tuple_size Var +%%% br label 4 +%%% +%%% 4: +%%% BoolVar2 = bif:'=:=' Size, literal 2 +%%% br BoolVar2, label 6, label 3 +%%% +%%% (The key part of the transformation is the removal of +%%% the 'succeeded' instruction to signal to the code generator +%%% that the call to tuple_size/1 can't fail.) +%%% +%%% The BEAM code will look like: +%%% +%%% {test,is_tuple,{f,3},[{x,0}]}. +%%% {test_arity,{f,3},[{x,0},2]}. +%%% +%%% Those two instructions will be combined into a single +%%% is_tuple_of_arity instruction by the loader. +%%% + +ssa_opt_tuple_size(#st{ssa=Linear0,cnt=Count0}=St) -> + {Linear,Count} = opt_tup_size(Linear0, Count0, []), + St#st{ssa=Linear,cnt=Count}. + +opt_tup_size([{L,#b_blk{is=Is,last=Last}=Blk}|Bs], Count0, Acc0) -> + case {Is,Last} of + {[#b_set{op={bif,'=:='},dst=Bool,args=[#b_var{}=Tup,#b_literal{val=Arity}]}], + #b_br{bool=Bool}} when is_integer(Arity), Arity >= 0 -> + {Acc,Count} = opt_tup_size_1(Tup, L, Count0, Acc0), + opt_tup_size(Bs, Count, [{L,Blk}|Acc]); + {_,_} -> + opt_tup_size(Bs, Count0, [{L,Blk}|Acc0]) + end; +opt_tup_size([], Count, Acc) -> + {reverse(Acc),Count}. + +opt_tup_size_1(Size, EqL, Count0, [{L,Blk0}|Acc]) -> + case Blk0 of + #b_blk{is=Is0,last=#b_br{bool=Bool,succ=EqL,fail=Fail}} -> + case opt_tup_size_is(Is0, Bool, Size, []) of + none -> + {[{L,Blk0}|Acc],Count0}; + {PreIs,TupleSizeIs,Tuple} -> + opt_tup_size_2(PreIs, TupleSizeIs, L, EqL, + Tuple, Fail, Count0, Acc) + end; + #b_blk{} -> + {[{L,Blk0}|Acc],Count0} + end; +opt_tup_size_1(_, _, Count, Acc) -> + {Acc,Count}. + +opt_tup_size_2(PreIs, TupleSizeIs, PreL, EqL, Tuple, Fail, Count0, Acc) -> + IsTupleL = Count0, + TupleSizeL = Count0 + 1, + Bool = #b_var{name={'@ssa_bool',Count0+2}}, + Count = Count0 + 3, + + True = #b_literal{val=true}, + PreBr = #b_br{bool=True,succ=IsTupleL,fail=IsTupleL}, + PreBlk = #b_blk{is=PreIs,last=PreBr}, + + IsTupleIs = [#b_set{op={bif,is_tuple},dst=Bool,args=[Tuple]}], + IsTupleBr = #b_br{bool=Bool,succ=TupleSizeL,fail=Fail}, + IsTupleBlk = #b_blk{is=IsTupleIs,last=IsTupleBr}, + + TupleSizeBr = #b_br{bool=True,succ=EqL,fail=EqL}, + TupleSizeBlk = #b_blk{is=TupleSizeIs,last=TupleSizeBr}, + {[{TupleSizeL,TupleSizeBlk}, + {IsTupleL,IsTupleBlk}, + {PreL,PreBlk}|Acc],Count}. + +opt_tup_size_is([#b_set{op={bif,tuple_size},dst=Size,args=[Tuple]}=I, + #b_set{op=succeeded,dst=Bool,args=[Size]}], + Bool, Size, Acc) -> + {reverse(Acc),[I],Tuple}; +opt_tup_size_is([I|Is], Bool, Size, Acc) -> + opt_tup_size_is(Is, Bool, Size, [I|Acc]); +opt_tup_size_is([], _, _, _Acc) -> none. + %%% %%% Optimize #b_switch{} instructions. %%% diff --git a/lib/compiler/test/guard_SUITE.erl b/lib/compiler/test/guard_SUITE.erl index 73a8dc0fda..6ccc0c8fd4 100644 --- a/lib/compiler/test/guard_SUITE.erl +++ b/lib/compiler/test/guard_SUITE.erl @@ -1779,16 +1779,6 @@ t_tuple_size(Config) when is_list(Config) -> error = ludicrous_tuple_size({a,b,c}), error = ludicrous_tuple_size([a,b,c]), - %% Test the "unsafe case" - the register assigned the tuple size is - %% not killed. - DataDir = test_lib:get_data_dir(Config), - File = filename:join(DataDir, "guard_SUITE_tuple_size"), - {ok,Mod,Code} = compile:file(File, [from_asm,binary]), - code:load_binary(Mod, File, Code), - 14 = Mod:t({1,2,3,4}), - _ = code:delete(Mod), - _ = code:purge(Mod), - good_ip({1,2,3,4}), good_ip({1,2,3,4,5,6,7,8}), error = validate_ip({42,11}), diff --git a/lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S b/lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S deleted file mode 100644 index cffb792920..0000000000 --- a/lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S +++ /dev/null @@ -1,30 +0,0 @@ -{module, guard_SUITE_tuple_size}. %% version = 0 - -{exports, [{t,1}]}. - -{attributes, []}. - -{labels, 5}. - - -{function, t, 1, 2}. - {label,1}. - {func_info,{atom,guard_SUITE_tuple_size},{atom,t},1}. - {label,2}. - {bif,tuple_size,{f,4},[{x,0}],{x,1}}. - {test,is_eq_exact,{f,4},[{x,1},{integer,4}]}. - {test,is_tuple,{f,3},[{x,0}]}. - {test,test_arity,{f,3},[{x,0},4]}. - {get_tuple_element,{x,0},0,{x,5}}. - {get_tuple_element,{x,0},1,{x,2}}. - {get_tuple_element,{x,0},2,{x,3}}. - {get_tuple_element,{x,0},3,{x,4}}. - {gc_bif,'+',{f,0},6,[{x,1},{x,2}],{x,0}}. - {gc_bif,'+',{f,0},6,[{x,0},{x,3}],{x,0}}. - {gc_bif,'+',{f,0},6,[{x,0},{x,4}],{x,0}}. - {gc_bif,'+',{f,0},6,[{x,0},{x,5}],{x,0}}. - return. - {label,3}. - {badmatch,{x,0}}. - {label,4}. - {jump,{f,1}}. -- cgit v1.2.3 From b3b195fd104e7052fe31becbab43fccb652f2d0a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sat, 8 Sep 2018 10:20:07 +0200 Subject: beam_ssa_opt: Slightly optimize performance of live optimization Phi nodes with only literals are fairly common, so it's worthwhile to optimize this case. --- lib/compiler/src/beam_ssa_opt.erl | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 0bb4a204a2..6d94c38685 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -820,11 +820,16 @@ live_opt_phis(Is, L, Live0, LiveMap0) -> LiveMap; [_|_] -> PhiArgs = append([Args || #b_set{args=Args} <- Phis]), - PhiVars = [{P,V} || {#b_var{name=V},P} <- PhiArgs], - PhiLive0 = rel2fam(PhiVars), - PhiLive = [{{L,P},gb_sets:union(gb_sets:from_list(Vs), Live0)} || - {P,Vs} <- PhiLive0], - maps:merge(LiveMap, maps:from_list(PhiLive)) + case [{P,V} || {#b_var{name=V},P} <- PhiArgs] of + [_|_]=PhiVars -> + PhiLive0 = rel2fam(PhiVars), + PhiLive = [{{L,P},gb_sets:union(gb_sets:from_list(Vs), Live0)} || + {P,Vs} <- PhiLive0], + maps:merge(LiveMap, maps:from_list(PhiLive)); + [] -> + %% There were only literals in the phi node(s). + LiveMap + end end. live_opt_blk(#b_blk{is=Is0,last=Last}=Blk, Live0) -> -- cgit v1.2.3 From b241241f21bee111c9aac7185cb8fd9a751557bd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sun, 9 Sep 2018 06:30:23 +0200 Subject: beam_ssa_opt: Slightly optimize compile-time performance of CSE --- lib/compiler/src/beam_ssa_opt.erl | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 6d94c38685..9289b76f28 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -417,7 +417,13 @@ cse_successors(_Is, Blk, Es, M) -> cse_successors_1([L|Ls], Es0, M) -> case M of + #{L:=Es1} when map_size(Es1) =:= 0 -> + %% The map is already empty. No need to do anything + %% since the intersection will be empty. + cse_successors_1(Ls, Es0, M); #{L:=Es1} -> + %% Calculate the intersection of the two maps. + %% Both keys and values must match. Es = maps:filter(fun(Key, Value) -> case Es1 of #{Key:=Value} -> true; -- cgit v1.2.3 From f25448763f55d595e00fe570f2108f669f3f6b1a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sun, 9 Sep 2018 07:42:53 +0200 Subject: beam_ssa_opt: Don't do CSE for tuple_size/1 Not doing CSE for tuple_size/1 seems to generate slightly better code in most cases. --- lib/compiler/src/beam_ssa_opt.erl | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 9289b76f28..7fbc090132 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -486,6 +486,13 @@ cse_suitable(#b_set{op=get_hd}) -> true; cse_suitable(#b_set{op=get_tl}) -> true; cse_suitable(#b_set{op=put_list}) -> true; cse_suitable(#b_set{op=put_tuple}) -> true; +cse_suitable(#b_set{op={bif,tuple_size}}) -> + %% Doing CSE for tuple_size/1 can prevent the + %% creation of test_arity and select_tuple_arity + %% instructions. That could decrease performance + %% and beam_validator could fail to understand + %% that tuple operations that follow are safe. + false; cse_suitable(#b_set{op={bif,Name},args=Args}) -> %% Doing CSE for comparison operators would prevent %% creation of 'test' instructions. -- cgit v1.2.3 From 25005204cca654920c7a751bb3ada4b9d9b0b285 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Mon, 17 Sep 2018 06:31:50 +0200 Subject: beam_ssa_opt: Robustify float optimizations The floating point optimization relies on heavily on the block order in the lineararized representation. A new optimization could easily break the optimization, for example so that no `fcheckerror` instructions were emitted. Rewrite the optimization to avoid dependencies on the linear block order. --- lib/compiler/src/beam_ssa_opt.erl | 132 +++++++++++++++----------------------- 1 file changed, 51 insertions(+), 81 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 7fbc090132..2174c6aa31 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -522,14 +522,15 @@ cse_suitable(#b_set{}) -> false. {s=undefined :: 'undefined' | 'cleared', regs=#{} :: #{beam_ssa:b_var():=beam_ssa:b_var()}, fail=none :: 'none' | beam_ssa:label(), - ren=#{} :: #{beam_ssa:label():=beam_ssa:label()}, - non_guards :: gb_sets:set(beam_ssa:label()) + non_guards :: gb_sets:set(beam_ssa:label()), + bs :: beam_ssa:block_map() }). ssa_opt_float(#st{ssa=Linear0,cnt=Count0}=St) -> NonGuards0 = float_non_guards(Linear0), NonGuards = gb_sets:from_list(NonGuards0), - Fs = #fs{non_guards=NonGuards}, + Blocks = maps:from_list(Linear0), + Fs = #fs{non_guards=NonGuards,bs=Blocks}, {Linear,Count} = float_opt(Linear0, Count0, Fs), St#st{ssa=Linear,cnt=Count}. @@ -542,42 +543,35 @@ float_non_guards([{L,#b_blk{is=Is}}|Bs]) -> end; float_non_guards([]) -> [?BADARG_BLOCK]. -float_opt([{L,Blk0}|Bs], Count, Fs) -> - Blk = float_rename_phis(Blk0, Fs), - case float_need_flush(Blk, Fs) of - true -> - float_flush(L, Blk, Bs, Count, Fs); - false -> - float_opt_1(L, Blk, Bs, Count, Fs) - end; -float_opt([], Count, _Fs) -> - {[],Count}. - -float_opt_1(L, #b_blk{last=#b_br{fail=F}}=Blk, Bs0, +float_opt([{L,#b_blk{last=#b_br{fail=F}}=Blk}|Bs0], Count0, #fs{non_guards=NonGuards}=Fs) -> case gb_sets:is_member(F, NonGuards) of true -> %% This block is not inside a guard. %% We can do the optimization. - float_opt_2(L, Blk, Bs0, Count0, Fs); + float_opt_1(L, Blk, Bs0, Count0, Fs); false -> %% This block is inside a guard. Don't do %% any floating point optimizations. {Bs,Count} = float_opt(Bs0, Count0, Fs), {[{L,Blk}|Bs],Count} end; -float_opt_1(L, Blk, Bs, Count, Fs) -> - float_opt_2(L, Blk, Bs, Count, Fs). +float_opt([{L,Blk}|Bs], Count, Fs) -> + float_opt_1(L, Blk, Bs, Count, Fs); +float_opt([], Count, _Fs) -> + {[],Count}. -float_opt_2(L, #b_blk{is=Is0}=Blk0, Bs0, Count0, Fs0) -> +float_opt_1(L, #b_blk{is=Is0}=Blk0, Bs0, Count0, Fs0) -> case float_opt_is(Is0, Fs0, Count0, []) of {Is1,Fs1,Count1} -> - Fs = float_fail_label(Blk0, Fs1), - Split = float_split_conv(Is1, Blk0), - {Blks0,Count2} = float_number(Split, L, Count1), - {Blks,Count3} = float_conv(Blks0, Fs#fs.fail, Count2), - {Bs,Count} = float_opt(Bs0, Count3, Fs), - {Blks++Bs,Count}; + Fs2 = float_fail_label(Blk0, Fs1), + Fail = Fs2#fs.fail, + {Flush,Blk,Fs,Count2} = float_maybe_flush(Blk0, Fs2, Count1), + Split = float_split_conv(Is1, Blk), + {Blks0,Count3} = float_number(Split, L, Count2), + {Blks,Count4} = float_conv(Blks0, Fail, Count3), + {Bs,Count} = float_opt(Bs0, Count4, Fs), + {Blks++Flush++Bs,Count}; none -> {Bs,Count} = float_opt(Bs0, Count0, Fs0), {[{L,Blk0}|Bs],Count} @@ -637,14 +631,42 @@ float_conv([{L,#b_blk{is=Is0}=Blk0}|Bs0], Fail, Count0) -> end end. -float_need_flush(#b_blk{is=Is}, #fs{s=cleared}) -> +float_maybe_flush(Blk0, #fs{s=cleared,fail=Fail,bs=Blocks}=Fs0, Count0) -> + #b_blk{last=#b_br{bool=#b_var{},succ=Succ}=Br} = Blk0, + #b_blk{is=Is} = maps:get(Succ, Blocks), case Is of [#b_set{anno=#{float_op:=_}}|_] -> - false; + %% The next operation is also a floating point operation. + %% No flush needed. + {[],Blk0,Fs0,Count0}; _ -> - true + %% Flush needed. + {Bool0,Count1} = new_reg('@ssa_bool', Count0), + Bool = #b_var{name=Bool0}, + + %% Allocate block numbers. + CheckL = Count1, %For checkerror. + FlushL = Count1 + 1, %For flushing of float regs. + Count = Count1 + 2, + Blk = Blk0#b_blk{last=Br#b_br{succ=CheckL}}, + + %% Build the block with the checkerror instruction. + CheckIs = [#b_set{op={float,checkerror},dst=Bool}], + CheckBr = #b_br{bool=Bool,succ=FlushL,fail=Fail}, + CheckBlk = #b_blk{is=CheckIs,last=CheckBr}, + + %% Build the block that flushes all registers. + FlushIs = float_flush_regs(Fs0), + FlushBr = #b_br{bool=#b_literal{val=true},succ=Succ,fail=Succ}, + FlushBlk = #b_blk{is=FlushIs,last=FlushBr}, + + %% Update state and blocks. + Fs = Fs0#fs{s=undefined,regs=#{},fail=none}, + FlushBs = [{CheckL,CheckBlk},{FlushL,FlushBlk}], + {FlushBs,Blk,Fs,Count} end; -float_need_flush(_, _) -> false. +float_maybe_flush(Blk, Fs, Count) -> + {[],Blk,Fs,Count}. float_opt_is([#b_set{op=succeeded,args=[Src]}=I0], #fs{regs=Rs}=Fs, Count, Acc) -> @@ -669,27 +691,6 @@ float_opt_is([], Fs, _Count, _Acc) -> #fs{s=undefined} = Fs, %Assertion. none. -float_rename_phis(#b_blk{is=Is}=Blk, #fs{ren=Ren}) -> - if - map_size(Ren) =:= 0 -> - Blk; - true -> - Blk#b_blk{is=float_rename_phis_1(Is, Ren)} - end. - -float_rename_phis_1([#b_set{op=phi,args=Args0}=I|Is], Ren) -> - Args = [float_phi_arg(Arg, Ren) || Arg <- Args0], - [I#b_set{args=Args}|float_rename_phis_1(Is, Ren)]; -float_rename_phis_1(Is, _) -> Is. - -float_phi_arg({Var,OldLbl}, Ren) -> - case Ren of - #{OldLbl:=NewLbl} -> - {Var,NewLbl}; - #{} -> - {Var,OldLbl} - end. - float_make_op(#b_set{op={bif,Op},dst=Dst,args=As0}=I0, Ts, #fs{s=S,regs=Rs0}=Fs, Count0) -> {As1,Rs1,Count1} = float_load(As0, Ts, Rs0, Count0, []), @@ -746,37 +747,6 @@ new_reg(Base, Count) -> Fr = {Base,Count}, {Fr,Count+1}. -float_flush(L, Blk, Bs0, Count0, #fs{s=cleared,fail=Fail,ren=Ren0}=Fs0) -> - {Bool0,Count1} = new_reg('@ssa_bool', Count0), - Bool = #b_var{name=Bool0}, - - %% Insert two blocks before the current block. First allocate - %% block numbers. - FirstL = L, %For checkerror. - MiddleL = Count1, %For flushed float regs. - LastL = Count1 + 1, %For original block. - Count2 = Count1 + 2, - - %% Build the block with the checkerror instruction. - CheckIs = [#b_set{op={float,checkerror},dst=Bool}], - FirstBlk = #b_blk{is=CheckIs,last=#b_br{bool=Bool,succ=MiddleL,fail=Fail}}, - - %% Build the block that flushes all registers. Note that this must be a - %% separate block in case the original block begins with a phi instruction, - %% to avoid embedding a phi instruction in the middle of a block. - FlushIs = float_flush_regs(Fs0), - MiddleBlk = #b_blk{is=FlushIs,last=#b_br{bool=#b_literal{val=true}, - succ=LastL,fail=LastL}}, - - %% The last block is the original unmodified block. - LastBlk = Blk, - - %% Update state and blocks. - Ren = Ren0#{L=>LastL}, - Fs = Fs0#fs{s=undefined,regs=#{},fail=none,ren=Ren}, - Bs1 = [{FirstL,FirstBlk},{MiddleL,MiddleBlk},{LastL,LastBlk}|Bs0], - float_opt(Bs1, Count2, Fs). - float_fail_label(#b_blk{last=Last}, Fs) -> case Last of #b_br{bool=#b_var{},fail=Fail} -> -- cgit v1.2.3 From 6de7b652697ecdb17a003e64418ab297c9111faa Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 11 Sep 2018 06:33:43 +0200 Subject: beam_ssa_type: Remove clause in arith_op_types/2 that can't match Remove the following clause from the `fun` clauses in arith_op_types/2 because it cannot possibly match: (_, any) -> number; Here is why it cannot match: The second argument is the accumulator for lists:foldl/3. Its initial value is `unknown`. None of the clauses will update the accumulator to `any`, including the clause that matches `any` in the first argument -- it will set the accumulator to `number`. Thus, the accumulator (second argument) can never be `any` and the clause can never match. QED. --- lib/compiler/src/beam_ssa_type.erl | 1 - 1 file changed, 1 deletion(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 2ba0f732f6..7ef64c0c4d 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -491,7 +491,6 @@ arith_op_type(Args, Ts) -> (number, #t_integer{}) -> number; (number, float) -> float; (any, _) -> number; - (_, any) -> number; (Same, Same) -> Same; (_, _) -> none end, unknown, Types). -- cgit v1.2.3 From 1e81c5e279acbe231432d3b6e7f7d03ac04c9d86 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 31 Aug 2018 11:41:14 +0200 Subject: beam_ssa_type: Infer types for more instructions and BIFs --- lib/compiler/src/beam_ssa_type.erl | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 7ef64c0c4d..89fa5ce3d7 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -428,6 +428,8 @@ type(is_tagged_tuple, [Src,#b_literal{val=Size},#b_literal{val=Tag}], Ts, _Ds) - _ -> t_atom(false) end; +type(put_map, _Args, _Ts, _Ds) -> + map; type(put_list, _Args, _Ts, _Ds) -> cons; type(put_tuple, Args, _Ts, _Ds) -> @@ -762,6 +764,8 @@ bif_type(floor, [_]) -> t_integer(); bif_type(is_map_key, [_,_]) -> t_boolean(); bif_type(length, [_]) -> t_integer(); bif_type(map_size, [_]) -> t_integer(); +bif_type(node, []) -> #t_atom{}; +bif_type(node, [_]) -> #t_atom{}; bif_type(round, [_]) -> t_integer(); bif_type(size, [_]) -> t_integer(); bif_type(trunc, [_]) -> t_integer(); @@ -803,8 +807,12 @@ inferred_bif_type(byte_size, [_]) -> {binary,1}; inferred_bif_type(ceil, [_]) -> number; inferred_bif_type(float, [_]) -> number; inferred_bif_type(floor, [_]) -> number; +inferred_bif_type(hd, [_]) -> cons; +inferred_bif_type(length, [_]) -> list; +inferred_bif_type(map_size, [_]) -> map; inferred_bif_type(round, [_]) -> number; inferred_bif_type(trunc, [_]) -> number; +inferred_bif_type(tl, [_]) -> cons; inferred_bif_type(tuple_size, [_]) -> #t_tuple{}; inferred_bif_type(_, _) -> any. -- cgit v1.2.3 From ecea668c979af62217eefe59307c808dc339f228 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Wed, 29 Aug 2018 17:26:22 +0200 Subject: beam_ssa_type: Substitute variables that evaluate to a constant In beam_ssa_type, do substitutions similar to what ssa_opt_misc does to get rid of variables that evaluate to constant values. That somewhat simplifies the code of beam_ssa_type, and could improve performance of the compiler since instructions and variables are eliminated, reducing the amount of work for later passes. --- lib/compiler/src/beam_ssa_type.erl | 453 ++++++++++++++++++++++--------------- 1 file changed, 270 insertions(+), 183 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 89fa5ce3d7..058e40106c 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -22,13 +22,15 @@ -export([opt/2]). -include("beam_ssa.hrl"). --import(lists, [any/2,droplast/1,foldl/3,last/1,member/2, +-import(lists, [all/2,any/2,droplast/1,foldl/3,last/1,member/2, reverse/1,sort/1]). -define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}). -record(d, {ds :: #{beam_ssa:var_name():=beam_ssa:b_set()}, - ls :: #{beam_ssa:label():=type_db()}}). + ls :: #{beam_ssa:label():=type_db()}, + sub :: #{beam_ssa:var_name():=beam_ssa:value()} + }). -define(ATOM_SET_SIZE, 5). @@ -60,7 +62,7 @@ opt(Linear, Args) -> arity=0}]}, Defs = maps:from_list([{V,FakeCall#b_set{dst=Var}} || #b_var{name=V}=Var <- Args]), - D = #d{ds=Defs,ls=#{0=>Ts}}, + D = #d{ds=Defs,ls=#{0=>Ts},sub=#{}}, opt_1(Linear, D). opt_1([{L,Blk}|Bs], #d{ls=Ls}=D) -> @@ -71,9 +73,9 @@ opt_1([{L,Blk}|Bs], #d{ls=Ls}=D) -> %% This block is never reached. Discard it. opt_1(Bs, D) end; -opt_1([], _) -> []. +opt_1([], #d{}) -> []. -opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, D0) -> +opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, #d{sub=Sub}=D0) -> case Is0 of [#b_set{op=call,dst=Dst, args=[#b_remote{mod=#b_literal{val=Mod}, @@ -84,7 +86,7 @@ opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, D0) -> %% Rewrite the terminator to a 'ret', and remove %% all type information for this label. That will %% simplify the phi node in the former successor. - Args = [simplify_arg(Arg, Ts) || Arg <- Args0], + Args = simplify_args(Args0, Sub, Ts), I = I0#b_set{args=[Rem|Args]}, Ret = #b_ret{arg=Dst}, Blk = Blk0#b_blk{is=[I],last=Ret}, @@ -98,61 +100,120 @@ opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, D0) -> opt_3(L, Blk0, Bs, Ts, D0) end. -opt_3(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, #d{ds=Ds0,ls=Ls0}=D0) -> - {Is,Ts,Ds} = opt_is(Is0, Ts0, Ds0, Ls0, []), - D1 = D0#d{ds=Ds}, - Last = opt_terminator(Last0, Ts, Ds), +opt_3(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, + #d{ds=Ds0,ls=Ls0,sub=Sub0}=D0) -> + {Is,Ts,Ds,Sub} = opt_is(Is0, Ts0, Ds0, Ls0, Sub0, []), + D1 = D0#d{ds=Ds,sub=Sub}, + Last1 = simplify_terminator(Last0, Sub, Ts), + Last = opt_terminator(Last1, Ts, Ds), D = update_successors(Last, Ts, D1), Blk = Blk0#b_blk{is=Is,last=Last}, [{L,Blk}|opt_1(Bs, D)]. -opt_is([#b_set{op=phi,dst=#b_var{name=Dst},args=Args0}=I0|Is], Ts0, Ds0, Ls, Acc) -> +simplify_terminator(#b_br{bool=Bool}=Br, Sub, Ts) -> + Br#b_br{bool=simplify_arg(Bool, Sub, Ts)}; +simplify_terminator(#b_switch{arg=Arg}=Sw, Sub, Ts) -> + Sw#b_switch{arg=simplify_arg(Arg, Sub, Ts)}; +simplify_terminator(#b_ret{arg=Arg}=Ret, Sub, Ts) -> + Ret#b_ret{arg=simplify_arg(Arg, Sub, Ts)}. + +opt_is([#b_set{op=phi,dst=#b_var{name=Dst},args=Args0}=I0|Is], + Ts0, Ds0, Ls, Sub0, Acc) -> %% Simplify the phi node by removing all predecessor blocks that no %% longer exists or no longer branches to this block. - Args = [P || {_,From}=P <- Args0, maps:is_key(From, Ls)], - I = I0#b_set{args=Args}, - Ts = update_types(I, Ts0, Ds0), - Ds = Ds0#{Dst=>I}, - opt_is(Is, Ts, Ds, Ls, [I|Acc]); -opt_is([#b_set{dst=#b_var{name=Dst}}=I0|Is], Ts0, Ds0, Ls, Acc) -> - I = beam_ssa:normalize(simplify(I0, Ts0)), - Ts = update_types(I, Ts0, Ds0), - Ds = Ds0#{Dst=>I}, - opt_is(Is, Ts, Ds, Ls, [I|Acc]); -opt_is([], Ts, Ds, _Ls, Acc) -> - {reverse(Acc),Ts,Ds}. + Args = [{simplify_arg(Arg, Sub0, Ts0),From} || + {Arg,From} <- Args0, maps:is_key(From, Ls)], + case all_same(Args) of + true -> + %% Eliminate the phi node if there is just one source + %% value or if the values are identical. + [{Val,_}|_] = Args, + Sub = Sub0#{Dst=>Val}, + opt_is(Is, Ts0, Ds0, Ls, Sub, Acc); + false -> + I = I0#b_set{args=Args}, + Ts = update_types(I, Ts0, Ds0), + Ds = Ds0#{Dst=>I}, + opt_is(Is, Ts, Ds, Ls, Sub0, [I|Acc]) + end; +opt_is([#b_set{args=Args0,dst=#b_var{name=Dst}}=I0|Is], + Ts0, Ds0, Ls, Sub0, Acc) -> + Args = simplify_args(Args0, Sub0, Ts0), + I1 = beam_ssa:normalize(I0#b_set{args=Args}), + case simplify(I1, Ts0) of + #b_set{}=I2 -> + I = beam_ssa:normalize(I2), + Ts = update_types(I, Ts0, Ds0), + Ds = Ds0#{Dst=>I}, + opt_is(Is, Ts, Ds, Ls, Sub0, [I|Acc]); + #b_literal{}=Lit -> + Sub = Sub0#{Dst=>Lit}, + opt_is(Is, Ts0, Ds0, Ls, Sub, Acc); + #b_var{}=Var -> + Sub = Sub0#{Dst=>Var}, + opt_is(Is, Ts0, Ds0, Ls, Sub, Acc) + end; +opt_is([], Ts, Ds, _Ls, Sub, Acc) -> + {reverse(Acc),Ts,Ds,Sub}. +simplify(#b_set{op={bif,'and'},args=Args}=I, Ts) -> + case is_safe_bool_op(Args, Ts) of + true -> + case Args of + [_,#b_literal{val=false}=Res] -> Res; + [Res,#b_literal{val=true}] -> Res; + _ -> eval_bif(I, Ts) + end; + false -> + I + end; +simplify(#b_set{op={bif,'or'},args=Args}=I, Ts) -> + case is_safe_bool_op(Args, Ts) of + true -> + case Args of + [Res,#b_literal{val=false}] -> Res; + [_,#b_literal{val=true}=Res] -> Res; + _ -> eval_bif(I, Ts) + end; + false -> + I + end; simplify(#b_set{op={bif,element},args=[#b_literal{val=Index},Tuple]}=I, Ts) -> case t_tuple_size(get_type(Tuple, Ts)) of {_,Size} when is_integer(Index), 1 =< Index, Index =< Size -> I#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=Index-1}]}; _ -> - I + eval_bif(I, Ts) end; simplify(#b_set{op={bif,hd},args=[List]}=I, Ts) -> case get_type(List, Ts) of cons -> I#b_set{op=get_hd}; _ -> - I + eval_bif(I, Ts) end; simplify(#b_set{op={bif,tl},args=[List]}=I, Ts) -> case get_type(List, Ts) of cons -> I#b_set{op=get_tl}; _ -> - I + eval_bif(I, Ts) end; simplify(#b_set{op={bif,size},args=[Term]}=I, Ts) -> case get_type(Term, Ts) of #t_tuple{} -> - I#b_set{op={bif,tuple_size}}; + simplify(I#b_set{op={bif,tuple_size}}, Ts); + _ -> + eval_bif(I, Ts) + end; +simplify(#b_set{op={bif,tuple_size},args=[Term]}=I, Ts) -> + case get_type(Term, Ts) of + #t_tuple{size=Size,exact=true} -> + #b_literal{val=Size}; _ -> I end; -simplify(#b_set{op={bif,'=='},args=Args0}=I0, Ts) -> - Args = [simplify_arg(Arg, Ts) || Arg <- Args0], - I = I0#b_set{args=Args}, +simplify(#b_set{op={bif,'=='},args=Args}=I, Ts) -> Types = get_types(Args, Ts), EqEq = case {meet(Types),join(Types)} of {none,any} -> true; @@ -164,50 +225,147 @@ simplify(#b_set{op={bif,'=='},args=Args0}=I0, Ts) -> end, case EqEq of true -> - I#b_set{op={bif,'=:='}}; + simplify(I#b_set{op={bif,'=:='}}, Ts); false -> - I + eval_bif(I, Ts) + end; +simplify(#b_set{op={bif,'=:='},args=[Same,Same]}, _Ts) -> + #b_literal{val=true}; +simplify(#b_set{op={bif,'=:='},args=Args}=I, Ts) -> + case meet(get_types(Args, Ts)) of + none -> #b_literal{val=false}; + _ -> eval_bif(I, Ts) end; -simplify(#b_set{op={bif,Op},args=Args0}=I0, Ts) -> - Args = [simplify_arg(Arg, Ts) || Arg <- Args0], - I = I0#b_set{args=Args}, +simplify(#b_set{op={bif,Op},args=Args}=I, Ts) -> Types = get_types(Args, Ts), case is_float_op(Op, Types) of false -> - I; + eval_bif(I, Ts); true -> AnnoArgs = [anno_float_arg(A) || A <- Types], - beam_ssa:add_anno(float_op, AnnoArgs, I) + eval_bif(beam_ssa:add_anno(float_op, AnnoArgs, I), Ts) end; -simplify(#b_set{op=wait_timeout,args=[Timeout0]}=I, Ts) -> - case simplify_arg(Timeout0, Ts) of - #b_literal{val=infinity} -> - I#b_set{op=wait,args=[]}; - Timeout -> - I#b_set{args=[Timeout]} +simplify(#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=0}]}=I, Ts) -> + case get_type(Tuple, Ts) of + #t_tuple{elements=[First]} -> + #b_literal{val=First}; + #t_tuple{} -> + I end; -simplify(#b_set{op=Op,args=Args0}=I, Ts) -> - Safe = case Op of - call -> true; - put_list -> true; - put_tuple -> true; - _ -> false - end, - case Safe of - true -> - Args = [simplify_arg(Arg, Ts) || Arg <- Args0], - I#b_set{args=Args}; +simplify(#b_set{op=is_nonempty_list,args=[Src]}=I, Ts) -> + case get_type(Src, Ts) of + any -> I; + list -> I; + cons -> #b_literal{val=true}; + _ -> #b_literal{val=false} + end; +simplify(#b_set{op=is_tagged_tuple, + args=[Src,#b_literal{val=Size},#b_literal{val=Tag}]}=I, Ts) -> + case get_type(Src, Ts) of + #t_tuple{exact=true,size=Size,elements=[Tag]} -> + #b_literal{val=true}; + #t_tuple{exact=true,size=ActualSize,elements=[]} -> + if + Size =/= ActualSize -> + #b_literal{val=false}; + true -> + I + end; + #t_tuple{exact=false} -> + I; + any -> + I; + _ -> + #b_literal{val=false} + end; +simplify(#b_set{op=put_list,args=[#b_literal{val=H}, + #b_literal{val=T}]}, _Ts) -> + #b_literal{val=[H|T]}; +simplify(#b_set{op=put_tuple,args=Args}=I, _Ts) -> + case make_literal_list(Args) of + none -> I; + List -> #b_literal{val=list_to_tuple(List)} + end; +simplify(#b_set{op=succeeded,args=[#b_literal{}]}, _Ts) -> + #b_literal{val=true}; +simplify(#b_set{op=wait_timeout,args=[#b_literal{val=infinity}]}=I, _Ts) -> + I#b_set{op=wait,args=[]}; +simplify(I, _Ts) -> I. + +make_literal_list(Args) -> + make_literal_list(Args, []). + +make_literal_list([#b_literal{val=H}|T], Acc) -> + make_literal_list(T, [H|Acc]); +make_literal_list([_|_], _) -> + none; +make_literal_list([], Acc) -> + reverse(Acc). + +is_safe_bool_op(Args, Ts) -> + [T1,T2] = get_types(Args, Ts), + t_is_boolean(T1) andalso t_is_boolean(T2). + +all_same([{H,_}|T]) -> + all(fun({E,_}) -> E =:= H end, T). + +eval_bif(#b_set{op={bif,Bif},args=Args}=I, Ts) -> + Arity = length(Args), + case erl_bifs:is_pure(erlang, Bif, Arity) of false -> - I + I; + true -> + case make_literal_list(Args) of + none -> + case get_types(Args, Ts) of + [any] -> + I; + [Type] -> + case will_succeed(Bif, Type) of + yes -> + #b_literal{val=true}; + no -> + #b_literal{val=false}; + maybe -> + I + end; + _ -> + I + end; + LitArgs -> + try apply(erlang, Bif, LitArgs) of + Val -> #b_literal{val=Val} + catch + error:_ -> I + end + + end end. -simplify_arg(#b_var{}=Arg, Ts) -> - Type = get_type(Arg, Ts), - case get_literal_from_type(Type) of - none -> Arg; - #b_literal{}=Lit -> Lit +simplify_args(Args, Sub, Ts) -> + [simplify_arg(Arg, Sub, Ts) || Arg <- Args]. + +simplify_arg(#b_var{}=Arg0, Sub, Ts) -> + case sub_arg(Arg0, Sub) of + #b_literal{}=LitArg -> + LitArg; + #b_var{}=Arg -> + Type = get_type(Arg, Ts), + case get_literal_from_type(Type) of + none -> Arg; + #b_literal{}=Lit -> Lit + end end; -simplify_arg(Arg, _Ts) -> Arg. +simplify_arg(#b_remote{mod=Mod,name=Name}=Rem, Sub, Ts) -> + Rem#b_remote{mod=simplify_arg(Mod, Sub, Ts), + name=simplify_arg(Name, Sub, Ts)}; +simplify_arg(Arg, _Sub, _Ts) -> Arg. + +sub_arg(#b_var{name=V}=Old, Sub) -> + case Sub of + #{V:=New} -> New; + #{} -> Old + end. is_float_op('-', [float]) -> true; @@ -229,59 +387,48 @@ anno_float_arg(_) -> convert. opt_terminator(#b_br{bool=#b_literal{}}=Br, _Ts, _Ds) -> beam_ssa:normalize(Br); -opt_terminator(#b_br{bool=#b_var{name=V}=Var}=Br, Ts, Ds) -> - BoolType = get_type(Var, Ts), - case get_literal_from_type(BoolType) of - #b_literal{}=BoolLit -> - beam_ssa:normalize(Br#b_br{bool=BoolLit}); - none -> - #{V:=Set} = Ds, - case Set of - #b_set{op={bif,'=:='},args=[Bool,#b_literal{val=true}]} -> - case t_is_boolean(get_type(Bool, Ts)) of - true -> - %% Bool =:= true ==> Bool - simplify_not(Br#b_br{bool=Bool}, Ts, Ds); - false -> - Br - end; - #b_set{} -> - simplify_not(Br, Ts, Ds) - end +opt_terminator(#b_br{bool=#b_var{name=V}}=Br, Ts, Ds) -> + #{V:=Set} = Ds, + case Set of + #b_set{op={bif,'=:='},args=[Bool,#b_literal{val=true}]} -> + case t_is_boolean(get_type(Bool, Ts)) of + true -> + %% Bool =:= true ==> Bool + simplify_not(Br#b_br{bool=Bool}, Ts, Ds); + false -> + Br + end; + #b_set{} -> + simplify_not(Br, Ts, Ds) end; -opt_terminator(#b_switch{arg=V}=Sw0, 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), - case get_literal_from_type(Type) of - #b_literal{}=Lit -> - Sw = Sw0#b_switch{arg=Lit}, - beam_ssa:normalize(Sw); - none -> - case Type of - #t_integer{elements={_,_}=Range} -> - simplify_switch_int(Sw0, Range); - Type -> - 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; - false -> - beam_ssa:normalize(Sw0) - end + case Type of + #t_integer{elements={_,_}=Range} -> + simplify_switch_int(Sw0, Range); + _ -> + 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; + false -> + beam_ssa:normalize(Sw0) end end; -opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> - Ret. +opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> Ret. update_successors(#b_br{bool=#b_literal{val=true},succ=S}, Ts, D) -> update_successor(S, Ts, D); -update_successors(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}, Ts, D0) -> - D = update_successor(Fail, Ts#{V:=t_atom(false)}, D0), - SuccTs = infer_types(V, Ts, D0), - update_successor(Succ, SuccTs#{V:=t_atom(true)}, D); +update_successors(#b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail}, Ts, D0) -> + D = update_successor_bool(Bool, false, Fail, Ts, D0), + SuccTs = infer_types(Bool, Ts, D0), + update_successor_bool(Bool, true, Succ, SuccTs, D); update_successors(#b_switch{arg=#b_var{name=V},fail=Fail,list=List}, Ts, D0) -> D = update_successor(Fail, Ts, D0), foldl(fun({Val,S}, A) -> @@ -290,6 +437,16 @@ update_successors(#b_switch{arg=#b_var{name=V},fail=Fail,list=List}, Ts, D0) -> end, D, List); update_successors(#b_ret{}, _Ts, D) -> D. +update_successor_bool(#b_var{name=V}=Var, BoolValue, S, Ts, D) -> + case t_is_boolean(get_type(Var, Ts)) of + true -> + update_successor(S, Ts#{V:=t_atom(BoolValue)}, D); + false -> + %% The `br` terminator is preceeded by an instruction that + %% does not produce a boolean value, such a `new_try_tag`. + update_successor(S, Ts, D) + end. + update_successor(S, Ts0, #d{ls=Ls}=D) -> case Ls of #{S:=Ts1} -> @@ -306,41 +463,8 @@ update_types(#b_set{op=Op,dst=#b_var{name=Dst},args=Args}, Ts, Ds) -> type(phi, Args, Ts, _Ds) -> Types = [get_type(A, Ts) || {A,_} <- Args], join(Types); -type({bif,'=:='}, [Same,Same], _Ts, _Ds) -> - t_atom(true); -type({bif,'=:='}, [_,_]=Args, Ts, _Ds) -> - case get_literals(Args, Ts) of - [#b_literal{val=Lit1},#b_literal{val=Lit2}] -> - t_atom(Lit1 =:= Lit2); - [_,_] -> - case meet(get_types(Args, Ts)) of - none -> t_atom(false); - _ -> t_boolean() - end - end; -type({bif,tuple_size}, [Src], Ts, _Ds) -> - case t_tuple_size(get_type(Src, Ts)) of - {exact,Size} -> - t_integer(Size); - _ -> - t_integer() - end; type({bif,'band'}, Args, Ts, _Ds) -> band_type(Args, Ts); -type({bif,Bif}, [Src]=Args, Ts, _Ds) -> - case get_type(Src, Ts) of - any -> - bif_type(Bif, Args); - Type -> - case will_succeed(Bif, Type) of - yes -> - t_atom(true); - no -> - t_atom(false); - maybe -> - bif_type(Bif, Args) - end - end; type({bif,Bif}, Args, Ts, _Ds) -> case bif_type(Bif, Args) of number -> @@ -392,42 +516,10 @@ type(call, [#b_remote{mod=#b_literal{val=Mod}, false -> any end end; -type(get_tuple_element, [Tuple,#b_literal{val=0}], Ts, _Ds) -> - case get_type(Tuple, Ts) of - #t_tuple{elements=[First]} -> - get_type(#b_literal{val=First}, Ts); - #t_tuple{} -> - any - end; -type(is_nonempty_list, [Src], Ts, _Ds) -> - case get_type(Src, Ts) of - any -> - t_boolean(); - list -> - t_boolean(); - cons -> - t_atom(true); - _ -> - t_atom(false) - end; -type(is_tagged_tuple, [Src,#b_literal{val=Size},#b_literal{val=Tag}], Ts, _Ds) -> - case get_type(Src, Ts) of - #t_tuple{exact=true,size=Size,elements=[Tag]} -> - t_atom(true); - #t_tuple{exact=true,size=ActualSize,elements=[]} -> - if - Size =/= ActualSize -> - t_atom(false); - true -> - t_boolean() - end; - #t_tuple{exact=false} -> - t_boolean(); - any -> - t_boolean(); - _ -> - t_atom(false) - end; +type(is_nonempty_list, [_], _Ts, _Ds) -> + t_boolean(); +type(is_tagged_tuple, [_,#b_literal{},#b_literal{}], _Ts, _Ds) -> + t_boolean(); type(put_map, _Args, _Ts, _Ds) -> map; type(put_list, _Args, _Ts, _Ds) -> @@ -553,7 +645,6 @@ will_succeed(is_list, Type) -> case Type of list -> yes; cons -> yes; - nil -> yes; _ -> no end; will_succeed(is_map, Type) -> @@ -673,12 +764,8 @@ simplify_not(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}=Br0, Ts, Ds) -> Br0 end. -get_literals(Values, Ts) -> - [get_literal_from_type(get_type(Val, Ts)) || Val <- Values]. - get_types(Values, Ts) -> [get_type(Val, Ts) || Val <- Values]. - -spec get_type(beam_ssa:value(), type_db()) -> type(). get_type(#b_var{name=V}, Ts) -> @@ -707,7 +794,7 @@ get_type(#b_literal{val=Val}, _Ts) -> any end. -infer_types(V, Ts, #d{ds=Ds}) -> +infer_types(#b_var{name=V}, Ts, #d{ds=Ds}) -> #{V:=#b_set{op=Op,args=Args}} = Ds, Types = infer_type(Op, Args, Ds), meet_types(Types, Ts). @@ -753,7 +840,6 @@ infer_type(_Op, _Args, _Ds) -> %% Note that that the following BIFs are handle elsewhere: %% %% band/2 -%% tuple_size/1 bif_type(abs, [_]) -> number; bif_type(bit_size, [_]) -> t_integer(); @@ -769,6 +855,7 @@ bif_type(node, [_]) -> #t_atom{}; bif_type(round, [_]) -> t_integer(); bif_type(size, [_]) -> t_integer(); bif_type(trunc, [_]) -> t_integer(); +bif_type(tuple_size, [_]) -> t_integer(); bif_type('bnot', [_]) -> t_integer(); bif_type('bor', [_,_]) -> t_integer(); bif_type('bsl', [_,_]) -> t_integer(); -- cgit v1.2.3 From 354c64f4c0a568e7c4766228c21d7f5e276fd549 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sat, 8 Sep 2018 06:22:45 +0200 Subject: Cover more code in beam_ssa_type --- lib/compiler/test/beam_type_SUITE.erl | 92 +++++++++++++++++++++++++++++++++-- 1 file changed, 87 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/compiler/test/beam_type_SUITE.erl b/lib/compiler/test/beam_type_SUITE.erl index caf43dad40..a4459b95bf 100644 --- a/lib/compiler/test/beam_type_SUITE.erl +++ b/lib/compiler/test/beam_type_SUITE.erl @@ -21,8 +21,8 @@ -export([all/0,suite/0,groups/0,init_per_suite/1,end_per_suite/1, init_per_group/2,end_per_group/2, - integers/1,coverage/1,booleans/1,setelement/1,cons/1, - tuple/1,record_float/1,binary_float/1,float_compare/1, + integers/1,numbers/1,coverage/1,booleans/1,setelement/1, + cons/1,tuple/1,record_float/1,binary_float/1,float_compare/1, arity_checks/1,elixir_binaries/1,find_best/1, test_size/1]). @@ -34,6 +34,7 @@ all() -> groups() -> [{p,[parallel], [integers, + numbers, coverage, booleans, setelement, @@ -125,6 +126,59 @@ do_integers_5(X0, Y0) -> 3 -> three end. +numbers(_Config) -> + Int = id(42), + true = is_integer(Int), + true = is_number(Int), + false = is_float(Int), + + Float = id(42.0), + true = is_float(Float), + true = is_number(Float), + false = is_integer(Float), + + Number = id(1) + id(2), + true = is_number(Number), + true = is_integer(Number), + false = is_float(Number), + + AnotherNumber = id(99.0) + id(1), + true = is_float(AnotherNumber), + true = is_number(AnotherNumber), + false = is_integer(AnotherNumber), + + NotNumber = id(atom), + true = is_atom(NotNumber), + false = is_number(NotNumber), + false = is_integer(NotNumber), + false = is_float(NotNumber), + + true = is_number(Int), + true = is_number(Float), + true = is_number(Number), + true = is_number(AnotherNumber), + + %% Cover beam_ssa_type:join/2. + + Join1 = case id(a) of + a -> 3 + id(7); %Number. + b -> id(5) / id(2) %Float. + end, + true = is_integer(Join1), + + Join2 = case id(a) of + a -> id(5) / 2; %Float. + b -> 3 + id(7) %Number. + end, + true = is_float(Join2), + + %% Cover beam_ssa_type:meet/2. + + Meet1 = id(0) + -10.0, %Float. + 10.0 = abs(Meet1), %Number. + + ok. + coverage(Config) -> {'EXIT',{badarith,_}} = (catch id(1) bsl 0.5), {'EXIT',{badarith,_}} = (catch id(2.0) bsl 2), @@ -162,10 +216,31 @@ coverage(Config) -> ok. booleans(_Config) -> - {'EXIT',{{case_clause,_},_}} = (catch do_booleans(42)), + {'EXIT',{{case_clause,_},_}} = (catch do_booleans_1(42)), + + AnyAtom = id(atom), + true = is_atom(AnyAtom), + false = is_boolean(AnyAtom), + + MaybeBool = id(maybe), + case MaybeBool of + true -> ok; + maybe -> ok; + false -> ok + end, + false = is_boolean(MaybeBool), + + NotBool = id(a), + case NotBool of + a -> ok; + b -> ok; + c -> ok + end, + false = is_boolean(NotBool), + ok. -do_booleans(B) -> +do_booleans_1(B) -> case is_integer(B) of yes -> yes; no -> no @@ -223,8 +298,15 @@ cons_hdtl(B) -> id(1), {id(hd(Cons)),id(tl(Cons))}. +-record(bird, {a=a,b=id(42)}). + tuple(_Config) -> {'EXIT',{{badmatch,{necessary}},_}} = (catch do_tuple()), + + [] = [X || X <- [], #bird{a = a} == {r,X,foo}], + [] = [X || X <- [], #bird{b = b} == {bird,X}], + [] = [X || X <- [], 3 == X#bird.a], + ok. do_tuple() -> @@ -361,7 +443,7 @@ find_best([], <<"a">>) -> find_best([], nil) -> {error,<<"should not get here">>}. -test_size(Config) -> +test_size(_Config) -> 2 = do_test_size({a,b}), 4 = do_test_size(<<42:32>>), ok. -- cgit v1.2.3 From ec1f35c9f52be894ba295b9a48237020855e3c46 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 4 Sep 2018 14:16:16 +0200 Subject: beam_ssa_codegen: Don't emit kill instructions before exit BIFs Omitting `kill` instructions before BIFs that throw exceptions will reduce the code size. This optimization supersedes the same optimizations in beam_dead. --- lib/compiler/src/beam_ssa_codegen.erl | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl index becfe56b3a..40c2d8c07a 100644 --- a/lib/compiler/src/beam_ssa_codegen.erl +++ b/lib/compiler/src/beam_ssa_codegen.erl @@ -1270,21 +1270,29 @@ cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=[#b_local{}=Func0|Args0]}, Call = build_call(call, Arity, {f,FuncLbl}, Context, Dst), Is = setup_args(Args, Anno, Context, St) ++ Line ++ Call, {Is,St}; -cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=[#b_remote{}=Func0|Args0]}, +cg_call(#cg_set{anno=Anno0,op=call,dst=Dst0,args=[#b_remote{}=Func0|Args0]}, Where, Context, St) -> [Dst|Args] = beam_args([Dst0|Args0], St), #b_remote{mod=Mod0,name=Name0,arity=Arity} = Func0, case {beam_arg(Mod0, St),beam_arg(Name0, St)} of {{atom,Mod},{atom,Name}} -> Func = {extfunc,Mod,Name,Arity}, - Line = call_line(Where, Func, Anno), + Line = call_line(Where, Func, Anno0), Call = build_call(call_ext, Arity, Func, Context, Dst), + Anno = case erl_bifs:is_exit_bif(Mod, Name, Arity) of + true -> + %% There is no need to kill Y registers + %% before calling an exit BIF. + maps:remove(kill_yregs, Anno0); + false -> + Anno0 + end, Is = setup_args(Args, Anno, Context, St) ++ Line ++ Call, {Is,St}; {Mod,Name} -> Apply = build_apply(Arity, Context, Dst), - Is = setup_args(Args++[Mod,Name], Anno, Context, St) ++ - [line(Anno)] ++ Apply, + Is = setup_args(Args++[Mod,Name], Anno0, Context, St) ++ + [line(Anno0)] ++ Apply, {Is,St} end; cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=Args0}, -- cgit v1.2.3 From 70bb14fe3fd27e8c429bf402e364b144a5807d9a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 21 Aug 2018 08:58:15 +0200 Subject: Add beam_ssa_dead.erl Add beam_ssa_dead to perform the main optimizations done by beam_dead: * Shortcut branches that jump to another block with a branch. If it can be seen that the second branch will always branch to a specific block, replace the target of the first branch. * Combined nested sequences of '=:=' tests and switch instructions operating on the same variable to a single switch. Diffing the compiler output, it seems that beam_ssa_dead finds many more opportunities for optimizations than beam_dead, although it does not find all opportunities that beam_dead does. In total, beam_ssa_dead is such improvement over beam_dead that there is no reason to keep beam_dead as well as beam_ssa_dead. Note that beam_ssa_dead does not attempt to optimize away redundant bs_context_binary instructions, because that instruction will be superseded by new instructions in the near future. --- lib/compiler/src/Makefile | 2 + lib/compiler/src/beam_ssa_dead.erl | 1001 +++++++++++++++++++++++++++++++++ lib/compiler/src/beam_ssa_opt.erl | 20 +- lib/compiler/src/compile.erl | 1 + lib/compiler/src/compiler.app.src | 1 + lib/compiler/test/beam_ssa_SUITE.erl | 185 +++++- lib/compiler/test/core_fold_SUITE.erl | 11 +- lib/compiler/test/match_SUITE.erl | 4 + 8 files changed, 1217 insertions(+), 8 deletions(-) create mode 100644 lib/compiler/src/beam_ssa_dead.erl (limited to 'lib') diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile index bd35f20442..71fcfc2d2a 100644 --- a/lib/compiler/src/Makefile +++ b/lib/compiler/src/Makefile @@ -64,6 +64,7 @@ MODULES = \ beam_split \ beam_ssa \ beam_ssa_codegen \ + beam_ssa_dead \ beam_ssa_lint \ beam_ssa_opt \ beam_ssa_pp \ @@ -194,6 +195,7 @@ $(EBIN)/beam_listing.beam: core_parse.hrl v3_kernel.hrl beam_ssa.hrl $(EBIN)/beam_kernel_to_ssa.beam: v3_kernel.hrl beam_ssa.hrl $(EBIN)/beam_ssa.beam: beam_ssa.hrl $(EBIN)/beam_ssa_codegen.beam: beam_ssa.hrl +$(EBIN)/beam_ssa_dead.beam: beam_ssa.hrl $(EBIN)/beam_ssa_lint.beam: beam_ssa.hrl $(EBIN)/beam_ssa_opt.beam: beam_ssa.hrl $(EBIN)/beam_ssa_pp.beam: beam_ssa.hrl diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl new file mode 100644 index 0000000000..7cdb4315fe --- /dev/null +++ b/lib/compiler/src/beam_ssa_dead.erl @@ -0,0 +1,1001 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2018. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% +%% Dead code is code that is executed but has no effect. This +%% optimization pass either removes dead code or jumps around it, +%% potentially making it unreachable so that it can be dropped +%% the next time beam_ssa:linearize/1 is called. +%% + +-module(beam_ssa_dead). +-export([opt/1]). + +-include("beam_ssa.hrl"). +-import(lists, [append/1,last/1,member/2,takewhile/2,reverse/1]). + +-type used_vars() :: #{beam_ssa:label():=ordsets:ordset(beam_ssa:var_name())}. + +-type basic_type_test() :: atom() | {'is_tagged_tuple',pos_integer(),atom()}. +-type type_test() :: basic_type_test() | {'not',basic_type_test()}. +-type op_name() :: atom(). +-type basic_rel_op() :: {op_name(),beam_ssa:b_var(),beam_ssa:value()} | + {basic_type_test(),beam_ssa:value()}. +-type rel_op() :: {op_name(),beam_ssa:b_var(),beam_ssa:value()} | + {type_test(),beam_ssa:value()}. + +-record(st, + {bs :: beam_ssa:block_map(), + us :: used_vars(), + skippable :: #{beam_ssa:label():='true'}, + rel_op=none :: 'none' | rel_op(), + target=any :: 'any' | 'one_way' | beam_ssa:label() + }). + +-spec opt([{Label0,Block0}]) -> [{Label,Block}] when + Label0 :: beam_ssa:label(), + Block0 :: beam_ssa:b_blk(), + Label :: beam_ssa:label(), + Block :: beam_ssa:b_blk(). + +opt(Linear) -> + {Used,Skippable} = used_vars(Linear), + Blocks0 = maps:from_list(Linear), + St0 = #st{bs=Blocks0,us=Used,skippable=Skippable}, + St = shortcut_opt(St0), + #st{bs=Blocks} = combine_eqs(St), + beam_ssa:linearize(Blocks). + +%%% +%%% Shortcut br/switch targets. +%%% +%%% A br/switch may branch to another br/switch that in turn always +%%% branches to another target. Rewrite br/switch to refer to the +%%% ultimate targets directly. That will save execution time, but +%%% could also reduce the size of the code if some of the original +%%% targets become unreachable and be deleted. +%%% +%%% When rewriting branches, we must be careful not to skip instructions +%%% that have side effects or that bind variables that will be used +%%% at the new target. +%%% +%%% We must also avoid branching to phi nodes. The reason is +%%% twofold. First, we might create a critical edge which is strictly +%%% forbidden. Second, there will be a branch from a block that is not +%%% listed in the list of predecessors in the phi node. Those +%%% limitations could probably be overcome, but it is not clear how +%%% much that would improve the code. +%%% + +shortcut_opt(#st{bs=Blocks}=St) -> + %% Processing the blocks in reverse post order seems to give more + %% opportunities for optimizations compared to post order. (Based on + %% running scripts/diffable with both PO and RPO and looking at + %% the diff.) + Ls = beam_ssa:rpo(Blocks), + shortcut_opt(Ls, #{from=>0}, St). + +shortcut_opt([L|Ls], Bs0, #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 + Last0 -> + %% No change. No need to update the block. + shortcut_opt(Ls, Bs, St); + Last -> + %% The terminator was simplified in some way. + %% Update the block. + Blk = Blk0#b_blk{last=Last}, + Blocks = Blocks0#{L=>Blk}, + shortcut_opt(Ls, Bs, St#st{bs=Blocks}) + end; +shortcut_opt([], _, St) -> St. + +shortcut_terminator(#b_br{bool=#b_literal{val=true},succ=Succ0}, + _Is, Bs, St0) -> + St = St0#st{rel_op=none}, + shortcut(Succ0, Bs, St); +shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br, + Is, 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}), + FailBs = bind_var(Bool, #b_literal{val=false}, Bs), + BrFail = shortcut(Fail0, 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}} + when Succ =/= Succ0; Fail =/= Fail0 -> + %% One or both of the targets were cut short. + beam_ssa:normalize(Br#b_br{succ=Succ,fail=Fail}); + {_,_} -> + %% No change. + Br + end; +shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, Bs, St) -> + List = shortcut_switch(List0, Bool, Bs, St), + beam_ssa:normalize(Sw#b_switch{list=List}); +shortcut_terminator(Last, _Is, _Bs, _St) -> + Last. + +shortcut_switch([{Lit,L0}|T], Bool, Bs, St0) -> + St = St0#st{rel_op=normalize_op({bif,'=:='}, [Bool,Lit])}, + #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(L, Bs, St) -> + shortcut_1(L, Bs, ordsets:new(), St). + +shortcut_1(L, Bs0, UnsetVars0, St) -> + case shortcut_2(L, Bs0, UnsetVars0, St) of + none -> + %% No more shortcuts found. Package up the previous + %% label in an unconditional branch. + #b_br{bool=#b_literal{val=true},succ=L,fail=L}; + {#b_br{bool=#b_var{}}=Br,_,_} -> + %% This is a two-way branch. We can't do any better. + 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) + end. + +%% Try to shortcut this block, branching to a successor. +shortcut_2(L, Bs0, UnsetVars0, St) -> + #b_blk{is=Is,last=Last} = get_block(L, St), + case eval_is(Is, Bs0, St) of + none -> + %% It is not safe to avoid this block because it + %% has instructions with potential side effects. + none; + Bs -> + %% The instructions in the block (if any) don't + %% have any side effects and can be skipped. + %% Evaluate the terminator. + case eval_terminator(Last, Bs, St) of + none -> + %% The terminator is not suitable (could be + %% because it is a switch that can't be simplified + %% or it is a ret instruction). + none; + #b_br{}=Br -> + %% We have a potentially suitable br. + %% Now update the set of variables that will never + %% be set if this block will be skipped. + UnsetVars1 = [V || #b_set{dst=#b_var{name=V}} <- Is], + UnsetVars = ordsets:union(UnsetVars0, + ordsets:from_list(UnsetVars1)), + + %% Continue checking whether this br is suitable. + shortcut_3(Br, Bs#{from:=L}, UnsetVars, St) + end + end. + +shortcut_3(Br, Bs, UnsetVars, #st{target=Target}=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; + 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. + 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 + end. + +shortcut_two_way(#b_br{succ=Succ,fail=Fail}, Bs0, UnsetVars0, St) -> + case shortcut_2(Succ, Bs0, UnsetVars0, St#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 + {#b_br{bool=#b_literal{},succ=Succ},_,_}=Res -> + Res; + none -> + none + end + end. + +get_block(L, St) -> + #st{bs=#{L:=Blk}} = St, + Blk. + +is_br_safe(UnsetVars, Br, #st{us=Us}=St) -> + %% Check that none of the unset variables will be used. + case Br of + #b_br{bool=#b_var{name=V},succ=Succ,fail=Fail} -> + #{Succ:=Used0,Fail:=Used1} = Us, + + %% A two-way branch never branches to a phi node, so there + %% is no need to check for phi nodes here. + not member(V, UnsetVars) andalso + ordsets:is_disjoint(Used0, UnsetVars) andalso + ordsets:is_disjoint(Used1, UnsetVars); + #b_br{succ=Same,fail=Same} -> + %% An unconditional branch must not jump to + %% a phi node. + not is_forbidden(Same, St) andalso + ordsets:is_disjoint(map_get(Same, Us), UnsetVars) + end. + +is_forbidden(L, St) -> + case get_block(L, St) of + #b_blk{is=[#b_set{op=phi}|_]} -> true; + #b_blk{is=[#b_set{op=peek_message}|_]} -> true; + #b_blk{} -> false + end. + + +%% Evaluate the instructions in the block. +%% 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 = maps:get(from, Bs0), + [Val] = [Val || {Val,Pred} <- Args, Pred =:= From], + Bs = bind_var(Dst, Val, Bs0), + eval_is(Is, Bs, St); +eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], Bs, St) -> + I = sub(I0, Bs), + case eval_bif(I, St) of + #b_literal{}=Val -> + eval_is(Is, bind_var(Dst, Val, Bs), St); + none -> + eval_is(Is, Bs, St) + end; +eval_is([#b_set{op=Op,dst=Dst}=I|Is], 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); + none -> + eval_is(Is, Bs, St) + end; +eval_is([#b_set{}=I|Is], 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); + false -> + %% This instruction may have some side effect. + %% It is not safe to avoid this instruction. + none + end; +eval_is([], Bs, _St) -> Bs. + +eval_terminator(#b_br{bool=#b_var{}=Bool}=Br, Bs, _St) -> + Val = get_value(Bool, Bs), + beam_ssa:normalize(Br#b_br{bool=Val}); +eval_terminator(#b_br{bool=#b_literal{}}=Br, _Bs, _St) -> + beam_ssa:normalize(Br); +eval_terminator(#b_switch{arg=Arg,fail=Fail,list=List}=Sw, Bs, St) -> + case get_value(Arg, Bs) of + #b_literal{}=Val -> + %% Literal argument. Simplify to a `br`. + beam_ssa:normalize(Sw#b_switch{arg=Val}); + #b_var{} -> + case St of + #st{rel_op=none} -> + %% No previous relational operator is stored. + %% Give up. + none; + #st{} -> + %% There is a previous relational operator stored. + %% Try optimizing the switch. + case eval_switch(List, Arg, St, Fail) of + none -> + none; + To when is_integer(To) -> + %% Either one of the values in the switch + %% matched a previous value in a '=:=' test, or + %% none of the values matched a previous test. + #b_br{bool=#b_literal{val=true},succ=To,fail=To} + end + end + end; +eval_terminator(#b_ret{}, _Bs, _St) -> + none. + +eval_switch([{Lit,Lbl}|T], Arg, St, Fail) -> + case eval_rel_op({bif,'=:='}, [Arg,Lit], St) of + none -> + %% This label could be reached. + eval_switch(T, Arg, St, none); + #b_literal{val=false} -> + %% This branch will never be taken. + eval_switch(T, Arg, St, Fail); + #b_literal{val=true} -> + %% Success. This branch will always be taken. + Lbl + end; +eval_switch([], _Arg, _St, Fail) -> + %% Fail is now either the failure label or 'none'. + Fail. + +bind_var(Var, Val0, Bs) -> + Val = get_value(Val0, Bs), + Bs#{Var=>Val}. + +get_value(#b_var{}=Var, Bs) -> + case Bs of + #{Var:=Val} -> get_value(Val, Bs); + #{} -> Var + end; +get_value(#b_literal{}=Lit, _Bs) -> Lit. + +eval_bif(#b_set{op={bif,Bif},args=Args}, St) -> + Arity = length(Args), + case erl_bifs:is_pure(erlang, Bif, Arity) of + false -> + none; + true -> + case [Lit || #b_literal{val=Lit} <- Args] of + LitArgs when length(LitArgs) =:= Arity -> + 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. + +%%% +%%% Handling of relational operators. +%%% + +get_rel_op(Bool, [_|_]=Is) -> + case last(Is) of + #b_set{op=Op,dst=Bool,args=Args} -> + normalize_op(Op, Args); + #b_set{} -> + none + end; +get_rel_op(_, []) -> none. + +%% normalize_op(Instruction) -> {Normalized,FailLabel} | error +%% Normalized = {Operator,Variable,Variable|Literal} | +%% {TypeTest,Variable} +%% Operation = '<' | '=<' | '=:=' | '=/=' | '>=' | '>' +%% TypeTest = is_atom | is_integer ... +%% Variable = #b_var{} +%% Literal = #b_literal{} +%% +%% Normalize a relational operator to facilitate further +%% comparisons between operators. Always make the register +%% operand the first operand. If there are two registers, +%% order the registers in lexical order. +%% +%% For example, this instruction: +%% +%% #b_set{op={bif,=<},args=[#b_literal{}, #b_var{}} +%% +%% will be normalized to: +%% +%% {'=<',#b_var{},#b_literal{}} + +-spec normalize_op(Op, Args) -> NormalizedOp | 'none' when + Op :: beam_ssa:op(), + Args :: [beam_ssa:value()], + NormalizedOp :: basic_rel_op(). + +normalize_op(is_tagged_tuple, [Arg,#b_literal{val=Size},#b_literal{val=Tag}]) + when is_integer(Size), is_atom(Tag) -> + {{is_tagged_tuple,Size,Tag},Arg}; +normalize_op(is_nonempty_list, [Arg]) -> + {is_nonempty_list,Arg}; +normalize_op({bif,Bif}, [Arg]) -> + case erl_internal:new_type_test(Bif, 1) of + true -> {Bif,Arg}; + false -> none + end; +normalize_op({bif,Bif}, [_,_]=Args) -> + case erl_internal:comp_op(Bif, 2) of + true -> + normalize_op_1(Bif, Args); + false -> + none + end; +normalize_op(_, _) -> none. + +normalize_op_1(Bif, Args) -> + case Args of + [#b_literal{}=Arg1,#b_var{}=Arg2] -> + {turn_op(Bif),Arg2,Arg1}; + [#b_var{}=Arg1,#b_literal{}=Arg2] -> + {Bif,Arg1,Arg2}; + [#b_var{}=A,#b_var{}=B] -> + if A < B -> {Bif,A,B}; + true -> {turn_op(Bif),B,A} + end; + [#b_literal{},#b_literal{}] -> + none + end. + +-spec invert_op(basic_rel_op() | 'none') -> rel_op() | 'none'. + +invert_op({Op,Arg1,Arg2}) -> + {invert_op_1(Op),Arg1,Arg2}; +invert_op({TypeTest,Arg}) -> + {{'not',TypeTest},Arg}; +invert_op(none) -> none. + +invert_op_1('>=') -> '<'; +invert_op_1('<') -> '>='; +invert_op_1('=<') -> '>'; +invert_op_1('>') -> '=<'; +invert_op_1('=:=') -> '=/='; +invert_op_1('=/=') -> '=:='; +invert_op_1('==') -> '/='; +invert_op_1('/=') -> '=='. + +turn_op('<') -> '>'; +turn_op('=<') -> '>='; +turn_op('>') -> '<'; +turn_op('>=') -> '=<'; +turn_op('=:='=Op) -> Op; +turn_op('=/='=Op) -> Op; +turn_op('=='=Op) -> Op; +turn_op('/='=Op) -> Op. + +eval_rel_op(_Bif, _Args, #st{rel_op=none}) -> + none; +eval_rel_op(Bif, Args, #st{rel_op=Prev}) -> + case normalize_op(Bif, Args) of + none -> + none; + RelOp -> + case will_succeed(Prev, RelOp) of + yes -> #b_literal{val=true}; + no -> #b_literal{val=false}; + maybe -> none + end + end. + +%% will_succeed(PrevCondition, Condition) -> yes | no | maybe +%% PrevCondition is a condition known to be true. This function +%% will tell whether Condition will succeed. + +will_succeed({_Op,_Var,_Value}=Same, {_Op,_Var,_Value}=Same) -> + %% Repeated test. + yes; +will_succeed({Op1,Var,#b_literal{val=A}}, {Op2,Var,#b_literal{val=B}}) -> + will_succeed_1(Op1, A, Op2, B); +will_succeed({Op1,Var,#b_var{}=A}, {Op2,Var,#b_var{}=B}) -> + will_succeed_vars(Op1, A, Op2, B); +will_succeed({'=:=',Var,#b_literal{val=A}}, {TypeTest,Var}) -> + eval_type_test(TypeTest, A); +will_succeed({_,_}=Same, {_,_}=Same) -> + %% Repeated type test. + yes; +will_succeed({Test1,Var}, {Test2,Var}) -> + will_succeed_test(Test1, Test2); +will_succeed({_,_}, {_,_}) -> + maybe; +will_succeed({_,_}, {_,_,_}) -> + maybe; +will_succeed({_,_,_}, {_,_}) -> + maybe; +will_succeed({_,_,_}, {_,_,_}) -> + maybe. + +will_succeed_test({'not',Test1}, Test2) -> + case Test1 =:= Test2 of + true -> no; + false -> maybe + end; +will_succeed_test(is_tuple, {is_tagged_tuple,_,_}) -> + maybe; +will_succeed_test({is_tagged_tuple,_,_}, is_tuple) -> + yes; +will_succeed_test(is_list, is_nonempty_list) -> + maybe; +will_succeed_test(is_nonempty_list, is_list) -> + yes; +will_succeed_test(T1, T2) -> + case is_numeric_test(T1) andalso is_numeric_test(T2) of + true -> maybe; + false -> no + end. + +will_succeed_1('=:=', A, '<', B) -> + if + B =< A -> no; + true -> yes + end; +will_succeed_1('=:=', A, '=<', B) -> + if + B < A -> no; + true -> yes + end; +will_succeed_1('=:=', A, '=:=', B) when A =/= B -> + no; +will_succeed_1('=:=', A, '=/=', B) -> + if + A =:= B -> no; + true -> yes + end; +will_succeed_1('=:=', A, '>=', B) -> + if + B > A -> no; + true -> yes + end; +will_succeed_1('=:=', A, '>', B) -> + if + B >= A -> no; + true -> yes + end; + +will_succeed_1('=/=', A, '=:=', B) when A =:= B -> no; + +will_succeed_1('<', A, '=:=', B) when B >= A -> no; +will_succeed_1('<', A, '=/=', B) when B >= A -> yes; +will_succeed_1('<', A, '<', B) when B >= A -> yes; +will_succeed_1('<', A, '=<', B) when B > A -> yes; +will_succeed_1('<', A, '>=', B) when B > A -> no; +will_succeed_1('<', A, '>', B) when B >= A -> no; + +will_succeed_1('=<', A, '=:=', B) when B > A -> no; +will_succeed_1('=<', A, '=/=', B) when B > A -> yes; +will_succeed_1('=<', A, '<', B) when B > A -> yes; +will_succeed_1('=<', A, '=<', B) when B >= A -> yes; +will_succeed_1('=<', A, '>=', B) when B > A -> no; +will_succeed_1('=<', A, '>', B) when B >= A -> no; + +will_succeed_1('>=', A, '=:=', B) when B < A -> no; +will_succeed_1('>=', A, '=/=', B) when B < A -> yes; +will_succeed_1('>=', A, '<', B) when B =< A -> no; +will_succeed_1('>=', A, '=<', B) when B < A -> no; +will_succeed_1('>=', A, '>=', B) when B =< A -> yes; +will_succeed_1('>=', A, '>', B) when B < A -> yes; + +will_succeed_1('>', A, '=:=', B) when B =< A -> no; +will_succeed_1('>', A, '=/=', B) when B =< A -> yes; +will_succeed_1('>', A, '<', B) when B =< A -> no; +will_succeed_1('>', A, '=<', B) when B < A -> no; +will_succeed_1('>', A, '>=', B) when B =< A -> yes; +will_succeed_1('>', A, '>', B) when B < A -> yes; + +will_succeed_1('==', A, '==', B) -> + if + A == B -> yes; + true -> no + end; +will_succeed_1('==', A, '/=', B) -> + if + A == B -> no; + true -> yes + end; +will_succeed_1('/=', A, '/=', B) when A == B -> yes; +will_succeed_1('/=', A, '==', B) when A == B -> no; + +will_succeed_1(_, _, _, _) -> maybe. + +will_succeed_vars('=/=', Val, '=:=', Val) -> no; +will_succeed_vars('=:=', Val, '=/=', Val) -> no; +will_succeed_vars('=:=', Val, '>=', Val) -> yes; +will_succeed_vars('=:=', Val, '=<', Val) -> yes; + +will_succeed_vars('/=', Val1, '==', Val2) when Val1 == Val2 -> no; +will_succeed_vars('==', Val1, '/=', Val2) when Val1 == Val2 -> no; + +will_succeed_vars(_, _, _, _) -> maybe. + +is_numeric_test(is_float) -> true; +is_numeric_test(is_integer) -> true; +is_numeric_test(is_number) -> true; +is_numeric_test(_) -> false. + +eval_type_test(Test, Arg) -> + case eval_type_test_1(Test, Arg) of + true -> yes; + false -> no + end. + +eval_type_test_1(is_nonempty_list, Arg) -> + case Arg of + [_|_] -> true; + _ -> false + end; +eval_type_test_1({is_tagged_tuple,Sz,Tag}, Arg) -> + if + tuple_size(Arg) =:= Sz, element(1, Arg) =:= Tag -> + true; + true -> + false + end; +eval_type_test_1(Test, Arg) -> + erlang:Test(Arg). + +%%% +%%% Combine bif:'=:=' and switch instructions +%%% to switch instructions. +%%% +%%% Consider this code: +%%% +%%% 0: +%%% @ssa_bool = bif:'=:=' Var, literal 1 +%%% br @ssa_bool, label 2, label 3 +%%% +%%% 2: +%%% ret literal a +%%% +%%% 3: +%%% @ssa_bool:7 = bif:'=:=' Var, literal 2 +%%% br @ssa_bool:7, label 4, label 999 +%%% +%%% 4: +%%% ret literal b +%%% +%%% 999: +%%% . +%%% . +%%% . +%%% +%%% The two bif:'=:=' instructions can be combined +%%% to a switch: +%%% +%%% 0: +%%% switch Var, label 999, [ { literal 1, label 2 }, +%%% { literal 2, label 3 } ] +%%% +%%% 2: +%%% ret literal a +%%% +%%% 4: +%%% ret literal b +%%% +%%% 999: +%%% . +%%% . +%%% . +%%% + +combine_eqs(#st{bs=Blocks}=St) -> + Ls = reverse(beam_ssa:rpo(Blocks)), + combine_eqs_1(Ls, St). + +combine_eqs_1([L|Ls], #st{bs=Blocks0}=St0) -> + case comb_get_sw(L, St0) of + none -> + combine_eqs_1(Ls, St0); + {_,Arg,_,Fail0,List0} -> + case comb_get_sw(Fail0, St0) of + {true,Arg,Fail1,Fail,List1} -> + %% Another switch/br with the same arguments was + %% found. Try combining them. + case combine_lists(Fail1, List0, List1, Blocks0) of + none -> + %% Different types of literals in the lists, + %% or the success cases in the first switch + %% could branch to the second switch + %% (increasing code size and repeating tests). + combine_eqs_1(Ls, St0); + List -> + %% Everything OK! Combine the lists. + Sw0 = #b_switch{arg=Arg,fail=Fail,list=List}, + Sw = beam_ssa:normalize(Sw0), + Blk0 = maps:get(L, Blocks0), + Blk = Blk0#b_blk{last=Sw}, + Blocks = Blocks0#{L:=Blk}, + St = St0#st{bs=Blocks}, + combine_eqs_1(Ls, St) + end; + {true,_OtherArg,_,_,_} -> + %% The other switch/br uses a different Arg. + combine_eqs_1(Ls, St0); + {false,_,_,_,_} -> + %% Not safe: Bindings of variables that will be used + %% or execution of instructions with potential + %% side effects will be skipped. + combine_eqs_1(Ls, St0); + none -> + %% No switch/br at this label. + combine_eqs_1(Ls, St0) + end + end; +combine_eqs_1([], St) -> St. + +comb_get_sw(L, Blocks) -> + comb_get_sw(L, true, Blocks). + +comb_get_sw(L, Safe0, #st{bs=Blocks,skippable=Skippable}=St) -> + #b_blk{is=Is,last=Last} = maps:get(L, Blocks), + Safe1 = Safe0 andalso is_map_key(L, Skippable), + case Last of + #b_ret{} -> + none; + #b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail} -> + case comb_is(Is, Bool, Safe1) of + {none,_} -> + none; + {#b_set{op={bif,'=:='},args=[#b_var{}=Arg,#b_literal{}=Lit]},Safe} -> + {Safe,Arg,L,Fail,[{Lit,Succ}]}; + {#b_set{},_} -> + none + end; + #b_br{bool=#b_literal{val=true},succ=Succ} -> + comb_get_sw(Succ, Safe1, St); + #b_switch{arg=#b_var{}=Arg,fail=Fail,list=List} -> + {none,Safe} = comb_is(Is, none, Safe1), + {Safe,Arg,L,Fail,List} + end. + +comb_is([#b_set{dst=#b_var{}=Bool}=I], Bool, Safe) -> + {I,Safe}; +comb_is([#b_set{}=I|Is], Bool, Safe0) -> + Safe = Safe0 andalso beam_ssa:no_side_effect(I), + comb_is(Is, Bool, Safe); +comb_is([], _Bool, Safe) -> + {none,Safe}. + +%% combine_list(Fail, List1, List2, Blocks) -> List|none. +%% Try to combine two switch lists, returning the combined +%% list or 'none' if not possible. +%% +%% The values in the two lists must be all of the same type. +%% +%% The code reached from the labels in the first list must +%% not reach the failure label (if they do, tests could +%% be repeated). +%% + +combine_lists(Fail, L1, L2, Blocks) -> + Ls = beam_ssa:rpo([Lbl || {_,Lbl} <- L1], Blocks), + case member(Fail, Ls) of + true -> + %% One or more of labels in the first list + %% could reach the failure label. That + %% means that the second switch/br instruction + %% will be retained, increasing code size and + %% potentially also execution time. + none; + false -> + %% The combined switch will replace both original + %% br/switch instructions, leading to a reduction in code + %% size and potentially also in execution time. + combine_lists_1(L1, L2) + end. + +combine_lists_1(List0, List1) -> + case are_lists_compatible(List0, List1) of + true -> + First = maps:from_list(List0), + List0 ++ [{Val,Lbl} || {Val,Lbl} <- List1, + not is_map_key(Val, First)]; + false -> + none + end. + +are_lists_compatible([{#b_literal{val=Val1},_}|_], + [{#b_literal{val=Val2},_}|_]) -> + case lit_type(Val1) of + none -> false; + Type -> Type =:= lit_type(Val2) + end. + +lit_type(Val) -> + if + is_atom(Val) -> atom; + is_float(Val) -> float; + is_integer(Val) -> integer; + true -> none + end. + +%%% +%%% Calculate used variables for each block. +%%% + +used_vars(Linear) -> + used_vars(reverse(Linear), #{}, #{}). + +used_vars([{L,#b_blk{is=Is}=Blk}|Bs], UsedVars0, Skip0) -> + %% Calculate the variables used by each block and its + %% successors. This information is used by + %% shortcut_opt/1. + + Successors = beam_ssa:successors(Blk), + Used0 = used_vars_succ(Successors, L, UsedVars0), + Used = used_vars_blk(Blk, Used0), + UsedVars = used_vars_phis(Is, L, Used, UsedVars0), + + %% combine_eqs/1 needs different variable usage + %% information than shortcut_opt/1. The Skip + %% map will have an entry for each block that + %% can be skipped (does not bind any variable used + %% in successor). + + Defined0 = [Def || #b_set{dst=#b_var{name=Def}} <- Is], + Defined = ordsets:from_list(Defined0), + MaySkip = ordsets:is_disjoint(Defined, Used0), + case MaySkip of + true -> + Skip = Skip0#{L=>true}, + used_vars(Bs, UsedVars, Skip); + false -> + used_vars(Bs, UsedVars, Skip0) + end; +used_vars([], UsedVars, Skip) -> + {UsedVars,Skip}. + +used_vars_succ([S|Ss], L, UsedVars) -> + Live0 = used_vars_succ(Ss, L, UsedVars), + Key = {S,L}, + case UsedVars of + #{Key:=Live} -> + ordsets:union(Live, Live0); + #{S:=Live} -> + ordsets:union(Live, Live0); + #{} -> + Live0 + end; +used_vars_succ([], _, _) -> + ordsets:new(). + +used_vars_phis(Is, L, Live0, UsedVars0) -> + UsedVars = UsedVars0#{L=>Live0}, + Phis = takewhile(fun(#b_set{op=Op}) -> Op =:= phi end, Is), + case Phis of + [] -> + UsedVars; + [_|_] -> + PhiArgs = append([Args || #b_set{args=Args} <- Phis]), + case [{P,V} || {#b_var{name=V},P} <- PhiArgs] of + [_|_]=PhiVars -> + PhiLive0 = rel2fam(PhiVars), + PhiLive = [{{L,P},ordsets:union(ordsets:from_list(Vs), Live0)} || + {P,Vs} <- PhiLive0], + maps:merge(UsedVars, maps:from_list(PhiLive)); + [] -> + %% There were only literals in the phi node(s). + UsedVars + end + end. + +used_vars_blk(#b_blk{is=Is,last=Last}, Used0) -> + Used = ordsets:union(Used0, beam_ssa:used(Last)), + used_vars_is(reverse(Is), Used). + +used_vars_is([#b_set{op=phi}|Is], Used) -> + used_vars_is(Is, Used); +used_vars_is([#b_set{dst=#b_var{name=Dst}}=I|Is], Used0) -> + Used1 = ordsets:union(Used0, beam_ssa:used(I)), + Used = ordsets:del_element(Dst, Used1), + used_vars_is(Is, Used); +used_vars_is([], Used) -> + Used. + +%%% +%%% Common utilities. +%%% + +sub(#b_set{args=Args}=I, Sub) -> + I#b_set{args=[sub_arg(A, Sub) || A <- Args]}. + +sub_arg(Old, Sub) -> + case Sub of + #{Old:=New} -> New; + #{} -> Old + end. + +rel2fam(S0) -> + S1 = sofs:relation(S0), + S = sofs:rel2fam(S1), + sofs:to_external(S). diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 2174c6aa31..83ee918b25 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -52,10 +52,19 @@ passes(Opts0) -> ?PASS(ssa_opt_element), ?PASS(ssa_opt_linearize), ?PASS(ssa_opt_record), + + %% Run ssa_opt_cse twice, because it will help ssa_opt_dead, + %% and ssa_opt_dead will help ssa_opt_cse. Run ssa_opt_live + %% twice, because it will help ssa_opt_dead and ssa_opt_dead + %% will help ssa_opt_live. ?PASS(ssa_opt_cse), ?PASS(ssa_opt_type), - ?PASS(ssa_opt_float), ?PASS(ssa_opt_live), + ?PASS(ssa_opt_dead), + ?PASS(ssa_opt_cse), %Second time. + ?PASS(ssa_opt_float), + ?PASS(ssa_opt_live), %Second time. + ?PASS(ssa_opt_bsm), ?PASS(ssa_opt_bsm_shortcut), ?PASS(ssa_opt_misc), @@ -91,6 +100,9 @@ function(#b_function{anno=Anno,bs=Blocks0,args=Args,cnt=Count0}=F, Ps) -> %%% Trivial sub passes. %%% +ssa_opt_dead(#st{ssa=Linear}=St) -> + St#st{ssa=beam_ssa_dead:opt(Linear)}. + ssa_opt_linearize(#st{ssa=Blocks}=St) -> St#st{ssa=beam_ssa:linearize(Blocks)}. @@ -493,11 +505,13 @@ cse_suitable(#b_set{op={bif,tuple_size}}) -> %% and beam_validator could fail to understand %% that tuple operations that follow are safe. false; -cse_suitable(#b_set{op={bif,Name},args=Args}) -> +cse_suitable(#b_set{anno=Anno,op={bif,Name},args=Args}) -> + %% Doing CSE for floating point operators is unsafe. %% Doing CSE for comparison operators would prevent %% creation of 'test' instructions. Arity = length(Args), - not (erl_internal:new_type_test(Name, Arity) orelse + not (is_map_key(float_op, Anno) orelse + erl_internal:new_type_test(Name, Arity) orelse erl_internal:comp_op(Name, Arity) orelse erl_internal:bool_op(Name, Arity)); cse_suitable(#b_set{}) -> false. diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl index 0a7f723c64..a0ebfff5f7 100644 --- a/lib/compiler/src/compile.erl +++ b/lib/compiler/src/compile.erl @@ -2047,6 +2047,7 @@ pre_load() -> beam_peep, beam_ssa, beam_ssa_codegen, + beam_ssa_dead, beam_ssa_opt, beam_ssa_pre_codegen, beam_ssa_recv, diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src index 74529f7fef..f5e2b31b87 100644 --- a/lib/compiler/src/compiler.app.src +++ b/lib/compiler/src/compiler.app.src @@ -39,6 +39,7 @@ beam_peep, beam_ssa, beam_ssa_codegen, + beam_ssa_dead, beam_ssa_lint, beam_ssa_opt, beam_ssa_pp, diff --git a/lib/compiler/test/beam_ssa_SUITE.erl b/lib/compiler/test/beam_ssa_SUITE.erl index 0356c99c5a..5536abbdde 100644 --- a/lib/compiler/test/beam_ssa_SUITE.erl +++ b/lib/compiler/test/beam_ssa_SUITE.erl @@ -21,7 +21,8 @@ -export([all/0,suite/0,groups/0,init_per_suite/1,end_per_suite/1, init_per_group/2,end_per_group/2, - calls/1,tuple_matching/1,recv/1,maps/1]). + calls/1,tuple_matching/1,recv/1,maps/1, + cover_ssa_dead/1,combine_sw/1]). suite() -> [{ct_hooks,[ts_install_cth]}]. @@ -33,7 +34,9 @@ groups() -> [tuple_matching, calls, recv, - maps + maps, + cover_ssa_dead, + combine_sw ]}]. init_per_suite(Config) -> @@ -286,5 +289,183 @@ maps_1(K) -> #{K:=V} = #{}, V. +-record(wx_ref, {type=any_type,ref=any_ref}). + +cover_ssa_dead(_Config) -> + str = format_str(str, escapable, [], true), + [iolist,str] = format_str(str, escapable, iolist, true), + bad = format_str(str, not_escapable, [], true), + bad = format_str(str, not_escapable, iolist, true), + bad = format_str(str, escapable, [], false), + bad = format_str(str, escapable, [], bad), + + DefWxRef = #wx_ref{}, + {DefWxRef,77,9999,[]} = contains(#wx_ref{}, 77, 9999), + {DefWxRef,77.0,9999,[]} = contains(#wx_ref{}, 77.0, 9999), + {DefWxRef,77,9999.0,[]} = contains(#wx_ref{}, 77, 9999.0), + {DefWxRef,77.0,9999.0,[]} = contains(#wx_ref{}, 77.0, 9999.0), + {any_type,any_ref,42,43,[option]} = contains(#wx_ref{}, {42,43}, [option]), + {any_type,any_ref,42,43,[]} = contains(#wx_ref{}, {42,43}, []), + {any_type,any_ref,42.0,43,[]} = contains(#wx_ref{}, {42.0,43}, []), + {any_type,any_ref,42,43.0,[]} = contains(#wx_ref{}, {42,43.0}, []), + {any_type,any_ref,42.0,43.0,[]} = contains(#wx_ref{}, {42.0,43.0}, []), + + nope = conv_alub(false, '=:='), + ok = conv_alub(true, '=:='), + ok = conv_alub(true, none), + error = conv_alub(false, none), + + {false,false} = eval_alu(false, false, false), + {true,false} = eval_alu(false, false, true), + {false,true} = eval_alu(false, true, false), + {false,false} = eval_alu(false, true, true), + {false,true} = eval_alu(true, false, false), + {false,false} = eval_alu(true, false, true), + {true,true} = eval_alu(true, true, false), + {false,true} = eval_alu(true, true, true), + + 100.0 = percentage(1.0, 0.0), + 100.0 = percentage(1, 0), + 0.0 = percentage(0, 0), + 0.0 = percentage(0.0, 0.0), + 40.0 = percentage(4.0, 10.0), + 60.0 = percentage(6, 10), + + %% Cover '=:=', followed by '=/='. + false = 'cover__=:=__=/='(41), + true = 'cover__=:=__=/='(42), + false = 'cover__=:=__=/='(43), + + %% Cover '<', followed by '=/='. + true = 'cover__<__=/='(41), + false = 'cover__<__=/='(42), + false = 'cover__<__=/='(43), + + %% Cover '=<', followed by '=/='. + true = 'cover__=<__=/='(41), + true = 'cover__=<__=/='(42), + false = 'cover__=<__=/='(43), + + %% Cover '>=', followed by '=/='. + false = 'cover__>=__=/='(41), + true = 'cover__>=__=/='(42), + true = 'cover__>=__=/='(43), + + %% Cover '>', followed by '=/='. + false = 'cover__>__=/='(41), + false = 'cover__>__=/='(42), + true = 'cover__>__=/='(43), + + ok. + +'cover__=:=__=/='(X) when X =:= 42 -> X =/= 43; +'cover__=:=__=/='(_) -> false. + +'cover__<__=/='(X) when X < 42 -> X =/= 42; +'cover__<__=/='(_) -> false. + +'cover__=<__=/='(X) when X =< 42 -> X =/= 43; +'cover__=<__=/='(_) -> false. + +'cover__>=__=/='(X) when X >= 42 -> X =/= 41; +'cover__>=__=/='(_) -> false. + +'cover__>__=/='(X) when X > 42 -> X =/= 42; +'cover__>__=/='(_) -> false. + +format_str(Str, FormatData, IoList, EscChars) -> + Escapable = FormatData =:= escapable, + case id(Str) of + IoStr when Escapable, EscChars, IoList == [] -> + id(IoStr); + IoStr when Escapable, EscChars -> + [IoList,id(IoStr)]; + _ -> + bad + end. + +contains(This, X, Y) when is_record(This, wx_ref), is_number(X), is_number(Y) -> + {This,X,Y,[]}; +contains(#wx_ref{type=ThisT,ref=ThisRef}, {CX,CY}, Options) + when is_number(CX), is_number(CY), is_list(Options) -> + {ThisT,ThisRef,CX,CY,Options}. + +conv_alub(HasDst, CmpOp) -> + case (not HasDst) andalso CmpOp =/= none of + true -> nope; + false -> + case HasDst of + false -> error; + true -> ok + end + end. + +eval_alu(Sign1, Sign2, N) -> + V = (Sign1 andalso Sign2 andalso (not N)) + or ((not Sign1) andalso (not Sign2) andalso N), + C = (Sign1 andalso Sign2) + or ((not N) andalso (Sign1 orelse Sign2)), + {V,C}. + +percentage(Divident, Divisor) -> + if Divisor == 0 andalso Divident /= 0 -> + 100.0; + Divisor == 0 -> + 0.0; + true -> + Divident / Divisor * 100 + end. + +combine_sw(_Config) -> + [a] = do_comb_sw_1(a), + [b,b] = do_comb_sw_1(b), + [c] = do_comb_sw_1(c), + [c] = do_comb_sw_1(c), + [] = do_comb_sw_1(z), + + [a] = do_comb_sw_2(a), + [b2,b1] = do_comb_sw_2(b), + [c] = do_comb_sw_2(c), + [c] = do_comb_sw_2(c), + [] = do_comb_sw_2(z), + + ok. + +do_comb_sw_1(X) -> + put(?MODULE, []), + if + X == a; X == b -> + put(?MODULE, [X|get(?MODULE)]); + true -> + ok + end, + if + X == b; X == c -> + put(?MODULE, [X|get(?MODULE)]); + true -> + ok + end, + erase(?MODULE). + +do_comb_sw_2(X) -> + put(?MODULE, []), + case X of + a -> + put(?MODULE, [a|get(?MODULE)]); + b -> + put(?MODULE, [b1|get(?MODULE)]); + _ -> + ok + end, + case X of + b -> + put(?MODULE, [b2|get(?MODULE)]); + c -> + put(?MODULE, [c|get(?MODULE)]); + _ -> + ok + end, + erase(?MODULE). + %% The identity function. id(I) -> I. diff --git a/lib/compiler/test/core_fold_SUITE.erl b/lib/compiler/test/core_fold_SUITE.erl index 68bc5c6e2f..3fca1434ae 100644 --- a/lib/compiler/test/core_fold_SUITE.erl +++ b/lib/compiler/test/core_fold_SUITE.erl @@ -212,9 +212,14 @@ bifs(Config) when is_list(Config) -> {ok,#{K:=V}} = id(list_to_tuple([ok,#{K=>V}])), ok. --define(CMP_SAME(A0, B), (fun(A) -> true = A == B, false = A /= B end)(id(A0))). --define(CMP_DIFF(A0, B), (fun(A) -> false = A == B, true = A /= B end)(id(A0))). - +-define(CMP_SAME0(A0, B), (fun(A) -> true = A == B, false = A /= B end)(id(A0))). +-define(CMP_SAME1(A0, B), (fun(A) -> false = A /= B, true = A == B end)(id(A0))). +-define(CMP_SAME(A0, B), (true = ?CMP_SAME0(A0, B) =:= not ?CMP_SAME1(A0, B))). + +-define(CMP_DIFF0(A0, B), (fun(A) -> false = A == B, true = A /= B end)(id(A0))). +-define(CMP_DIFF1(A0, B), (fun(A) -> true = A /= B, false = A == B end)(id(A0))). +-define(CMP_DIFF(A0, B), (true = ?CMP_DIFF0(A0, B) =:= not ?CMP_DIFF1(A0, B))). + eq(Config) when is_list(Config) -> ?CMP_SAME([a,b,c], [a,b,c]), ?CMP_SAME([42.0], [42.0]), diff --git a/lib/compiler/test/match_SUITE.erl b/lib/compiler/test/match_SUITE.erl index 46b543728d..229c3093d7 100644 --- a/lib/compiler/test/match_SUITE.erl +++ b/lib/compiler/test/match_SUITE.erl @@ -446,6 +446,7 @@ letify_guard(A, B) -> selectify(Config) when is_list(Config) -> integer = sel_different_types({r,42}), atom = sel_different_types({r,forty_two}), + float = sel_different_types({r,100.0}), none = sel_different_types({r,18}), {'EXIT',_} = (catch sel_different_types([a,b,c])), @@ -456,12 +457,15 @@ selectify(Config) when is_list(Config) -> integer42 = sel_same_value2(42), integer43 = sel_same_value2(43), error = sel_same_value2(44), + ok. sel_different_types({r,_}=T) when element(2, T) =:= forty_two -> atom; sel_different_types({r,_}=T) when element(2, T) =:= 42 -> integer; +sel_different_types({r,_}=T) when element(2, T) =:= 100.0 -> + float; sel_different_types({r,_}) -> none. -- cgit v1.2.3 From 0871e4e581d3679c61b82f5552adc9192399d815 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 4 Sep 2018 14:03:52 +0200 Subject: Remove the beam_dead and beam_split passes Most of the optimizations in beam_dead have been superseded by the optimizations in beam_ssa_dead. The forward/1 pass of beam_dead has been moved to beam_jump. The beam_split pass splits blocks that contain instructions with non-zero labels. Because there are no optimizations left that optimize instructions within blocks, beam_block never needs to put such instructions into blocks in the first place. beam_split also moved 'move' instructions out block to help beam_dead. That is no longer necessary since beam_dead no longer exists. --- lib/compiler/src/Makefile | 2 - lib/compiler/src/beam_block.erl | 12 +- lib/compiler/src/beam_dead.erl | 891 ------------------------------------ lib/compiler/src/beam_jump.erl | 118 ++++- lib/compiler/src/beam_split.erl | 90 ---- lib/compiler/src/compile.erl | 6 - lib/compiler/src/compiler.app.src | 2 - lib/compiler/test/compile_SUITE.erl | 1 - lib/compiler/test/guard_SUITE.erl | 32 +- lib/compiler/test/misc_SUITE.erl | 10 - 10 files changed, 113 insertions(+), 1051 deletions(-) delete mode 100644 lib/compiler/src/beam_dead.erl delete mode 100644 lib/compiler/src/beam_split.erl (limited to 'lib') diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile index 71fcfc2d2a..522523726b 100644 --- a/lib/compiler/src/Makefile +++ b/lib/compiler/src/Makefile @@ -52,7 +52,6 @@ MODULES = \ beam_bs \ beam_bsm \ beam_clean \ - beam_dead \ beam_dict \ beam_disasm \ beam_except \ @@ -61,7 +60,6 @@ MODULES = \ beam_listing \ beam_opcodes \ beam_peep \ - beam_split \ beam_ssa \ beam_ssa_codegen \ beam_ssa_dead \ diff --git a/lib/compiler/src/beam_block.erl b/lib/compiler/src/beam_block.erl index 0ed2a03a81..d28c0fd9e4 100644 --- a/lib/compiler/src/beam_block.erl +++ b/lib/compiler/src/beam_block.erl @@ -83,8 +83,8 @@ collect({allocate_heap,Ns,Nh,R}) -> {set,[],[],{alloc,R,{nozero,Ns,Nh,[]}}}; collect({allocate_heap_zero,Ns,Nh,R}) -> {set,[],[],{alloc,R,{zero,Ns,Nh,[]}}}; collect({init,D}) -> {set,[D],[],init}; collect({test_heap,N,R}) -> {set,[],[],{alloc,R,{nozero,nostack,N,[]}}}; -collect({bif,N,F,As,D}) -> {set,[D],As,{bif,N,F}}; -collect({gc_bif,N,F,R,As,D}) -> {set,[D],As,{alloc,R,{gc_bif,N,F}}}; +collect({bif,N,{f,0},As,D}) -> {set,[D],As,{bif,N,{f,0}}}; +collect({gc_bif,N,{f,0},R,As,D}) -> {set,[D],As,{alloc,R,{gc_bif,N,{f,0}}}}; collect({move,S,D}) -> {set,[D],[S],move}; collect({put_list,S1,S2,D}) -> {set,[D],[S1,S2],put_list}; collect({put_tuple,A,D}) -> {set,[D],[],{put_tuple,A}}; @@ -95,12 +95,8 @@ collect({set_tuple_element,S,D,I}) -> {set,[],[S,D],{set_tuple_element,I}}; collect({get_hd,S,D}) -> {set,[D],[S],get_hd}; collect({get_tl,S,D}) -> {set,[D],[S],get_tl}; collect(remove_message) -> {set,[],[],remove_message}; -collect({put_map,F,Op,S,D,R,{list,Puts}}) -> - {set,[D],[S|Puts],{alloc,R,{put_map,Op,F}}}; -collect({'catch'=Op,R,L}) -> - {set,[R],[],{try_catch,Op,L}}; -collect({'try'=Op,R,L}) -> - {set,[R],[],{try_catch,Op,L}}; +collect({put_map,{f,0},Op,S,D,R,{list,Puts}}) -> + {set,[D],[S|Puts],{alloc,R,{put_map,Op,{f,0}}}}; collect(fclearerror) -> {set,[],[],fclearerror}; collect({fcheckerror,{f,0}}) -> {set,[],[],fcheckerror}; collect({fmove,S,D}) -> {set,[D],[S],fmove}; diff --git a/lib/compiler/src/beam_dead.erl b/lib/compiler/src/beam_dead.erl deleted file mode 100644 index 901ef5dc39..0000000000 --- a/lib/compiler/src/beam_dead.erl +++ /dev/null @@ -1,891 +0,0 @@ -%% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2002-2018. All Rights Reserved. -%% -%% Licensed under the Apache License, Version 2.0 (the "License"); -%% you may not use this file except in compliance with the License. -%% You may obtain a copy of the License at -%% -%% http://www.apache.org/licenses/LICENSE-2.0 -%% -%% Unless required by applicable law or agreed to in writing, software -%% distributed under the License is distributed on an "AS IS" BASIS, -%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -%% See the License for the specific language governing permissions and -%% limitations under the License. -%% -%% %CopyrightEnd% -%% - --module(beam_dead). - --export([module/2]). - -%%% Dead code is code that is executed but has no effect. This -%%% optimization pass either removes dead code or jumps around it, -%%% potentially making it unreachable and a target for the -%%% the beam_jump pass. - --import(lists, [mapfoldl/3,reverse/1]). - - --spec module(beam_utils:module_code(), [compile:option()]) -> - {'ok',beam_utils:module_code()}. - -module({Mod,Exp,Attr,Fs0,_}, _Opts) -> - {Fs1,Lc1} = beam_clean:clean_labels(Fs0), - {Fs,Lc} = mapfoldl(fun function/2, Lc1, Fs1), - %%{Fs,Lc} = {Fs1,Lc1}, - {ok,{Mod,Exp,Attr,Fs,Lc}}. - -function({function,Name,Arity,CLabel,Is0}, Lc0) -> - try - Is1 = beam_jump:remove_unused_labels(Is0), - - %% Initialize label information with the code - %% for the func_info label. Without it, a register - %% may seem to be live when it is not. - [{label,L}|FiIs] = Is1, - D0 = beam_utils:empty_label_index(), - D = beam_utils:index_label(L, FiIs, D0), - - %% Optimize away dead code. - {Is2,Lc} = forward(Is1, Lc0), - Is3 = backward(Is2, D), - Is = move_move_into_block(Is3, []), - {{function,Name,Arity,CLabel,Is},Lc} - catch - Class:Error:Stack -> - io:fwrite("Function: ~w/~w\n", [Name,Arity]), - erlang:raise(Class, Error, Stack) - end. - -%% 'move' instructions outside of blocks may thwart the jump optimizer. -%% Move them back into the block. - -move_move_into_block([{block,Bl0},{move,S,D}|Is], Acc) -> - Bl = Bl0 ++ [{set,[D],[S],move}], - move_move_into_block([{block,Bl}|Is], Acc); -move_move_into_block([{move,S,D}|Is], Acc) -> - Bl = [{set,[D],[S],move}], - move_move_into_block([{block,Bl}|Is], Acc); -move_move_into_block([I|Is], Acc) -> - move_move_into_block(Is, [I|Acc]); -move_move_into_block([], Acc) -> reverse(Acc). - -%%% -%%% Scan instructions in execution order and remove redundant 'move' -%%% instructions. 'move' instructions are redundant if we know that -%%% the register already contains the value being assigned, as in the -%%% following code: -%%% -%%% select_val Register FailLabel [... Literal => L1...] -%%% . -%%% . -%%% . -%%% L1: move Literal Register -%%% -%%% Also add extra labels to help the second backward pass. -%%% - -forward(Is, Lc) -> - forward(Is, #{}, Lc, []). - -forward([{move,_,_}=Move|[{label,L}|_]=Is], D, Lc, Acc) -> - %% move/2 followed by jump/1 is optimized by backward/3. - forward([Move,{jump,{f,L}}|Is], D, Lc, Acc); -forward([{bif,_,_,_,_}=Bif|[{label,L}|_]=Is], D, Lc, Acc) -> - %% bif/4 followed by jump/1 is optimized by backward/3. - forward([Bif,{jump,{f,L}}|Is], D, Lc, Acc); -forward([{select,select_val,Reg,_,List}=I|Is], D0, Lc, Acc) -> - D = update_value_dict(List, Reg, D0), - forward(Is, D, Lc, [I|Acc]); -forward([{label,Lbl},{block,[{set,[Dst],[Lit],move}|BlkIs]}=Blk0|Is], - D, Lc, Acc0) -> - Acc = [{label,Lbl}|Acc0], - case already_has_value(Lit, Lbl, Dst, D) andalso - no_fallthrough(Acc0) of - true -> - Blk = {block,BlkIs}, - forward([Blk|Is], D, Lc, Acc); - false -> - forward([Blk0|Is], D, Lc, Acc) - end; -forward([{label,Lbl},{move,Lit,Dst}=Move|Is], D, Lc, Acc0) -> - Acc = [{label,Lbl}|Acc0], - case already_has_value(Lit, Lbl, Dst, D) andalso - no_fallthrough(Acc0) of - true -> - %% Remove redundant 'move' instruction. - forward(Is, D, Lc, Acc); - false -> - %% Keep 'move' instruction. - forward([Move|Is], D, Lc, Acc) - end; -forward([{test,_,_,_}=I|Is]=Is0, D0, Lc, Acc) -> - %% Help the second, backward pass to by inserting labels after - %% relational operators so that they can be skipped if they are - %% known to be true. - D = update_unsafe_labels(I, D0), - case useful_to_insert_label(Is0) of - false -> forward(Is, D, Lc, [I|Acc]); - true -> forward(Is, D, Lc+1, [{label,Lc},I|Acc]) - end; -forward([I|Is], D0, Lc, Acc) -> - D = update_unsafe_labels(I, D0), - forward(Is, D, Lc, [I|Acc]); -forward([], _, Lc, Acc) -> {Acc,Lc}. - -no_fallthrough([I|_]) -> - beam_jump:is_unreachable_after(I). - -already_has_value(Lit, Lbl, Reg, D) -> - Key = {Lbl,Reg}, - case D of - #{Lbl:=unsafe} -> - false; - #{Key:=Lit} -> - true; - #{} -> - false - end. - -update_value_dict([Lit,{f,Lbl}|T], Reg, D0) -> - Key = {Lbl,Reg}, - D = case D0 of - #{Key := inconsistent} -> D0; - #{Key := _} -> D0#{Key := inconsistent}; - _ -> D0#{Key => Lit} - end, - update_value_dict(T, Reg, D); -update_value_dict([], _, D) -> D. - -update_unsafe_labels(I, D) -> - Ls = beam_jump:instr_labels(I), - update_unsafe_labels_1(Ls, D). - -update_unsafe_labels_1([L|Ls], D) -> - update_unsafe_labels_1(Ls, D#{L=>unsafe}); -update_unsafe_labels_1([], D) -> D. - -useful_to_insert_label([_,{label,_}|_]) -> - false; -useful_to_insert_label([{test,Op,_,_}|_]) -> - case Op of - is_lt -> true; - is_ge -> true; - is_eq_exact -> true; - is_ne_exact -> true; - _ -> false - end. - -%%% -%%% Scan instructions in reverse execution order and try to -%%% shortcut branch instructions. -%%% -%%% For example, in this code: -%%% -%%% move Literal Register -%%% jump L1 -%%% . -%%% . -%%% . -%%% L1: test is_{integer,atom} FailLabel Register -%%% select_val {x,0} FailLabel [... Literal => L2...] -%%% . -%%% . -%%% . -%%% L2: ... -%%% -%%% the 'selectval' instruction will always transfer control to L2, -%%% so we can just as well jump to L2 directly by rewriting the -%%% first part of the sequence like this: -%%% -%%% move Literal Register -%%% jump L2 -%%% -%%% If register Register is killed at label L2, we can remove the -%%% 'move' instruction, leaving just the 'jump' instruction: -%%% -%%% jump L2 -%%% -%%% These transformations may leave parts of the code unreachable. -%%% The beam_jump pass will remove the unreachable code. - -backward(Is, D) -> - backward(Is, D, []). - -backward([{test,is_eq_exact,Fail,[Dst,{integer,Arity}]}=I| - [{bif,tuple_size,Fail,[Reg],Dst}|Is]=Is0], D, Acc) -> - %% Provided that Dst is killed following this sequence, - %% we can rewrite the instructions like this: - %% - %% bif tuple_size Fail Reg Dst ==> is_tuple Fail Reg - %% is_eq_exact Fail Dst Integer test_arity Fail Reg Integer - %% - %% (still two instructions, but they they will be combined to - %% one by the loader). - case beam_utils:is_killed(Dst, Acc, D) andalso (Arity bsr 32) =:= 0 of - false -> - %% Not safe because the register Dst is not killed - %% (probably cannot not happen in practice) or the arity - %% does not fit in 32 bits (the loader will fail to load - %% the module). We must move the first instruction to the - %% accumulator to avoid an infinite loop. - backward(Is0, D, [I|Acc]); - true -> - %% Safe. - backward([{test,test_arity,Fail,[Reg,Arity]}, - {test,is_tuple,Fail,[Reg]}|Is], D, Acc) - end; -backward([{label,Lbl}=L|Is], D, Acc) -> - backward(Is, beam_utils:index_label(Lbl, Acc, D), [L|Acc]); -backward([{select,select_val,Reg,{f,Fail0},List0}|Is], D, Acc) -> - List1 = shortcut_select_list(List0, Reg, D, []), - Fail = shortcut_label(Fail0, D), - List = prune_redundant(List1, Fail), - case List of - [] -> - Jump = {jump,{f,Fail}}, - backward([Jump|Is], D, Acc); - [V,F] -> - Test = {test,is_eq_exact,{f,Fail},[Reg,V]}, - Jump = {jump,F}, - backward([Jump,Test|Is], D, Acc); - [{atom,B1},F,{atom,B2},F] when B1 =:= not B2 -> - Test = {test,is_boolean,{f,Fail},[Reg]}, - Jump = {jump,F}, - backward([Jump,Test|Is], D, Acc); - [_|_] -> - Sel = {select,select_val,Reg,{f,Fail},List}, - backward(Is, D, [Sel|Acc]) - end; -backward([{jump,{f,To0}},{move,Src,Reg}=Move|Is], D, Acc) -> - To = shortcut_select_label(To0, Reg, Src, D), - Jump = {jump,{f,To}}, - case is_killed_at(Reg, To, D) of - false -> backward([Move|Is], D, [Jump|Acc]); - true -> backward([Jump|Is], D, Acc) - end; -backward([{jump,{f,To}}=J|[{bif,Op,{f,BifFail},Ops,Reg}|Is]=Is0], D, Acc) -> - try replace_comp_op(To, Reg, Op, Ops, D) of - {Test,Jump} -> - backward([Jump,Test|Is], D, Acc) - catch - throw:not_possible -> - case To =:= BifFail of - true -> - %% The bif instruction is redundant. See the comment - %% in the next clause for why there is no need to - %% test for liveness of Reg at label To. - backward([J|Is], D, Acc); - false -> - backward(Is0, D, [J|Acc]) - end - end; -backward([{jump,{f,To}}=J|[{gc_bif,_,{f,To},_,_,_Dst}|Is]], D, Acc) -> - %% The gc_bif instruction is redundant, since either the gc_bif - %% instruction itself or the jump instruction will transfer control - %% to label To. Note that a gc_bif instruction does not assign its - %% destination register if the failure branch is taken; therefore, - %% the code at label To is not allowed to assume that the destination - %% register is initialized, and it is therefore no need to test - %% for liveness of the destination register at label To. - backward([J|Is], D, Acc); -backward([{test,bs_start_match2,F,Live,[Src,_]=Args,Ctxt}|Is], D, Acc0) -> - {f,To0} = F, - case test_bs_literal(F, Ctxt, D, Acc0) of - {none,Acc} -> - %% Ctxt killed immediately after bs_start_match2. - To = shortcut_bs_context_to_binary(To0, Src, D), - I = {test,is_bitstr,{f,To},[Src]}, - backward(Is, D, [I|Acc]); - {Literal,Acc} -> - %% Ctxt killed after matching a literal. - To = shortcut_bs_context_to_binary(To0, Src, D), - Eq = {test,is_eq_exact,{f,To},[Src,{literal,Literal}]}, - backward(Is, D, [Eq|Acc]); - not_killed -> - %% Ctxt not killed. Not much to do. - To = shortcut_bs_start_match(To0, Src, D), - I = {test,bs_start_match2,{f,To},Live,Args,Ctxt}, - backward(Is, D, [I|Acc0]) - end; -backward([{test,Op,{f,To0},Ops0}|Is], D, Acc) -> - To1 = shortcut_label(To0, D), - To2 = shortcut_rel_op(To1, Op, Ops0, D), - - %% Try to shortcut a repeated test: - %% - %% test Op {f,Fail1} Operands test Op {f,Fail2} Operands - %% . . . ==> ... - %% Fail1: test Op {f,Fail2} Operands Fail1: test Op {f,Fail2} Operands - %% - To = case beam_utils:code_at(To2, D) of - [{test,Op,{f,To3},Ops}|_] -> - case equal_ops(Ops0, Ops) of - true -> To3; - false -> To2 - end; - _Code -> - To2 - end, - I = case Op of - is_eq_exact -> combine_eqs(To, Ops0, D, Acc); - _ -> {test,Op,{f,To},Ops0} - end, - case I of - {test,_,_,_} -> - %% Still a test instruction. Done. - backward(Is, D, [I|Acc]); - _ -> - %% Rewritten to a select_val. Rescan. - backward([I|Is], D, Acc) - end; -backward([{test,Op,{f,To0},Live,Ops0,Dst}|Is], D, Acc) -> - To1 = shortcut_label(To0, D), - - %% Try to shortcut a repeated test: - %% - %% test Op {f,Fail1} _ Ops _ test Op {f,Fail2} _ Ops _ - %% . . . ==> ... - %% Fail1: test Op {f,Fail2} _ Ops _ Fail1: test Op {f,Fail2} _ Ops _ - %% - To = case beam_utils:code_at(To1, D) of - [{test,Op,{f,To2},_,Ops,_}|_] -> - case equal_ops(Ops0, Ops) of - true -> To2; - false -> To1 - end; - _Code -> - To1 - end, - I = {test,Op,{f,To},Live,Ops0,Dst}, - backward(Is, D, [I|Acc]); -backward([{kill,_}=I|Is], D, [{line,_},Exit|_]=Acc) -> - case beam_jump:is_exit_instruction(Exit) of - false -> backward(Is, D, [I|Acc]); - true -> backward(Is, D, Acc) - end; -backward([{bif,'or',{f,To0},[Dst,{atom,false}],Dst}=I|Is], D, - [{test,is_eq_exact,{f,To},[Dst,{atom,true}]}|_]=Acc) -> - case shortcut_label(To0, D) of - To -> - backward(Is, D, Acc); - _ -> - backward(Is, D, [I|Acc]) - end; -backward([{bif,map_get,{f,FF},[Key,Map],_}=I0, - {test,has_map_fields,{f,FT}=F,[Map|Keys0]}=I1|Is], D, Acc) when FF =/= 0 -> - case shortcut_label(FF, D) of - FT -> - case lists:delete(Key, Keys0) of - [] -> - backward([I0|Is], D, Acc); - Keys -> - Test = {test,has_map_fields,F,[Map|Keys]}, - backward([Test|Is], D, [I0|Acc]) - end; - _ -> - backward([I1|Is], D, [I0|Acc]) - end; -backward([{bif,map_get,{f,FF},[_,Map],_}=I0, - {test,is_map,{f,FT},[Map]}=I1|Is], D, Acc) when FF =/= 0 -> - case shortcut_label(FF, D) of - FT -> backward([I0|Is], D, Acc); - _ -> backward([I1|Is], D, [I0|Acc]) - end; -backward([I|Is], D, Acc) -> - backward(Is, D, [I|Acc]); -backward([], _D, Acc) -> Acc. - -equal_ops([{field_flags,FlA0}|T0], [{field_flags,FlB0}|T1]) -> - FlA = lists:keydelete(anno, 1, FlA0), - FlB = lists:keydelete(anno, 1, FlB0), - FlA =:= FlB andalso equal_ops(T0, T1); -equal_ops([Op|T0], [Op|T1]) -> - equal_ops(T0, T1); -equal_ops([], []) -> true; -equal_ops(_, _) -> false. - -shortcut_select_list([Lit,{f,To0}|T], Reg, D, Acc) -> - To = shortcut_select_label(To0, Reg, Lit, D), - shortcut_select_list(T, Reg, D, [{f,To},Lit|Acc]); -shortcut_select_list([], _, _, Acc) -> reverse(Acc). - -shortcut_label(0, _) -> - 0; -shortcut_label(To0, D) -> - case beam_utils:code_at(To0, D) of - [{jump,{f,To}}|_] -> shortcut_label(To, D); - _ -> To0 - end. - -shortcut_select_label(To, Reg, Lit, D) -> - shortcut_rel_op(To, is_ne_exact, [Reg,Lit], D). - -prune_redundant([_,{f,Fail}|T], Fail) -> - prune_redundant(T, Fail); -prune_redundant([V,F|T], Fail) -> - [V,F|prune_redundant(T, Fail)]; -prune_redundant([], _) -> []. - -%% Replace a comparison operator with a test instruction and a jump. -%% For example, if we have this code: -%% -%% bif '=:=' Fail Src1 Src2 {x,0} -%% jump L1 -%% . -%% . -%% . -%% L1: select_val {x,0} FailLabel [... true => L2..., ...false => L3...] -%% -%% the first two instructions can be replaced with -%% -%% test is_eq_exact L3 Src1 Src2 -%% jump L2 -%% -%% provided that {x,0} is killed at both L2 and L3. - -replace_comp_op(To, Reg, Op, Ops, D) -> - False = comp_op_find_shortcut(To, Reg, {atom,false}, D), - True = comp_op_find_shortcut(To, Reg, {atom,true}, D), - {bif_to_test(Op, Ops, False),{jump,{f,True}}}. - -comp_op_find_shortcut(To0, Reg, Val, D) -> - case shortcut_select_label(To0, Reg, Val, D) of - To0 -> - not_possible(); - To -> - case is_killed_at(Reg, To, D) of - false -> not_possible(); - true -> To - end - end. - -bif_to_test(Name, Args, Fail) -> - try - beam_utils:bif_to_test(Name, Args, {f,Fail}) - catch - error:_ -> not_possible() - end. - -not_possible() -> throw(not_possible). - -%% combine_eqs(To, Operands, Acc) -> Instruction. -%% Combine two is_eq_exact instructions or (an is_eq_exact -%% instruction and a select_val instruction) to a select_val -%% instruction if possible. -%% -%% Example: -%% -%% is_eq_exact F1 Reg Lit1 select_val Reg F2 [ Lit1 L1 -%% L1: . Lit2 L2 ] -%% . -%% . ==> -%% . -%% F1: is_eq_exact F2 Reg Lit2 F1: is_eq_exact F2 Reg Lit2 -%% L2: .... L2: -%% -combine_eqs(To, [Reg,{Type,_}=Lit1]=Ops, D, Acc) - when Type =:= atom; Type =:= integer -> - Next = case Acc of - [{label,Lbl}|_] -> Lbl; - [{jump,{f,Lbl}}|_] -> Lbl - end, - case beam_utils:code_at(To, D) of - [{test,is_eq_exact,{f,F2},[Reg,{Type,_}=Lit2]}, - {label,L2}|_] when Lit1 =/= Lit2 -> - {select,select_val,Reg,{f,F2},[Lit1,{f,Next},Lit2,{f,L2}]}; - [{test,is_eq_exact,{f,F2},[Reg,{Type,_}=Lit2]}, - {jump,{f,L2}}|_] when Lit1 =/= Lit2 -> - {select,select_val,Reg,{f,F2},[Lit1,{f,Next},Lit2,{f,L2}]}; - [{select,select_val,Reg,{f,F2},[{Type,_}|_]=List0}|_] -> - List = remove_from_list(Lit1, List0), - {select,select_val,Reg,{f,F2},[Lit1,{f,Next}|List]}; - _Is -> - {test,is_eq_exact,{f,To},Ops} - end; -combine_eqs(To, Ops, _D, _Acc) -> - {test,is_eq_exact,{f,To},Ops}. - -remove_from_list(Lit, [Lit,{f,_}|T]) -> - T; -remove_from_list(Lit, [Val,{f,_}=Fail|T]) -> - [Val,Fail|remove_from_list(Lit, T)]; -remove_from_list(_, []) -> []. - - -test_bs_literal(F, Ctxt, D, - [{test,bs_match_string,F,[Ctxt,Bs]}, - {test,bs_test_tail2,F,[Ctxt,0]}|Acc]) -> - test_bs_literal_1(Ctxt, Acc, D, Bs); -test_bs_literal(F, Ctxt, D, [{test,bs_test_tail2,F,[Ctxt,0]}|Acc]) -> - test_bs_literal_1(Ctxt, Acc, D, <<>>); -test_bs_literal(_, Ctxt, D, Acc) -> - test_bs_literal_1(Ctxt, Acc, D, none). - -test_bs_literal_1(Ctxt, Is, D, Literal) -> - case beam_utils:is_killed(Ctxt, Is, D) of - true -> {Literal,Is}; - false -> not_killed - end. - -%% shortcut_bs_start_match(TargetLabel, Reg) -> TargetLabel -%% A failing bs_start_match2 instruction means that the source (Reg) -%% cannot be a binary. That means that it is safe to skip -%% bs_context_to_binary instructions operating on Reg, and -%% bs_start_match2 instructions operating on Reg. - -shortcut_bs_start_match(To, Reg, D) -> - shortcut_bs_start_match_1(beam_utils:code_at(To, D), Reg, To, D). - -shortcut_bs_start_match_1([{bs_context_to_binary,Reg}|Is], Reg, To, D) -> - shortcut_bs_start_match_1(Is, Reg, To, D); -shortcut_bs_start_match_1([{jump,{f,To}}|_], Reg, _, D) -> - Code = beam_utils:code_at(To, D), - shortcut_bs_start_match_1(Code, Reg, To, D); -shortcut_bs_start_match_1([{test,bs_start_match2,{f,To},_,[Reg|_],_}|_], - Reg, _, D) -> - Code = beam_utils:code_at(To, D), - shortcut_bs_start_match_1(Code, Reg, To, D); -shortcut_bs_start_match_1(_, _, To, _) -> - To. - -%% shortcut_bs_context_to_binary(TargetLabel, Reg) -> TargetLabel -%% If a bs_start_match2 instruction has been eliminated, the -%% bs_context_to_binary instruction can be eliminated too. - -shortcut_bs_context_to_binary(To, Reg, D) -> - shortcut_bs_ctb_1(beam_utils:code_at(To, D), Reg, To, D). - -shortcut_bs_ctb_1([{bs_context_to_binary,Reg}|Is], Reg, To, D) -> - shortcut_bs_ctb_1(Is, Reg, To, D); -shortcut_bs_ctb_1([{jump,{f,To}}|_], Reg, _, D) -> - Code = beam_utils:code_at(To, D), - shortcut_bs_ctb_1(Code, Reg, To, D); -shortcut_bs_ctb_1(_, _, To, _) -> - To. - -%% shortcut_rel_op(FailLabel, Operator, [Operand], D) -> FailLabel' -%% Try to shortcut the given test instruction. Example: -%% -%% is_ge L1 {x,0} 48 -%% . -%% . -%% . -%% L1: is_ge L2 {x,0} 65 -%% -%% The first test instruction can be rewritten to "is_ge L2 {x,0} 48" -%% since the instruction at L1 will also fail. -%% -%% If there are instructions between L1 and the other test instruction -%% it may still be possible to do the shortcut. For example: -%% -%% L1: is_eq_exact L3 {x,0} 92 -%% is_ge L2 {x,0} 65 -%% -%% Since the first test instruction failed, we know that {x,0} must -%% be less than 48; therefore, we know that {x,0} cannot be equal to -%% 92 and the jump to L3 cannot happen. - -shortcut_rel_op(To, Op, Ops, D) -> - case normalize_op({test,Op,{f,To},Ops}) of - {{NormOp,A,B},_} -> - Normalized = {negate_op(NormOp),A,B}, - shortcut_rel_op_fp(To, Normalized, D); - {_,_} -> - To; - error -> - To - end. - -shortcut_rel_op_fp(To0, Normalized, D) -> - Code = beam_utils:code_at(To0, D), - case shortcut_any_label(Code, Normalized) of - error -> - To0; - To -> - shortcut_rel_op_fp(To, Normalized, D) - end. - -%% shortcut_any_label([Instruction], PrevCondition) -> FailLabel | error -%% Using PrevCondition (a previous condition known to be true), -%% try to shortcut to another failure label. - -shortcut_any_label([{jump,{f,Lbl}}|_], _Prev) -> - Lbl; -shortcut_any_label([{label,Lbl}|_], _Prev) -> - Lbl; -shortcut_any_label([{select,select_val,R,{f,Fail},L}|_], Prev) -> - shortcut_selectval(L, R, Fail, Prev); -shortcut_any_label([I|Is], Prev) -> - case normalize_op(I) of - error -> - error; - {Normalized,Fail} -> - %% We have a relational operator. - case will_succeed(Prev, Normalized) of - no -> - %% This test instruction will always branch - %% to Fail. - Fail; - yes -> - %% This test instruction will never branch, - %% so we will look at the next instruction. - shortcut_any_label(Is, Prev); - maybe -> - %% May or may not branch. From now on, we can only - %% shortcut to the this specific failure label - %% Fail. - shortcut_specific_label(Is, Fail, Prev) - end - end. - -%% shortcut_specific_label([Instruction], FailLabel, PrevCondition) -> -%% FailLabel | error -%% We have previously encountered a test instruction that may or -%% may not branch to FailLabel. Therefore we are only allowed -%% to do the shortcut to the same fail label (FailLabel). - -shortcut_specific_label([{label,_}|Is], Fail, Prev) -> - shortcut_specific_label(Is, Fail, Prev); -shortcut_specific_label([{select,select_val,R,{f,F},L}|_], Fail, Prev) -> - case shortcut_selectval(L, R, F, Prev) of - Fail -> Fail; - _ -> error - end; -shortcut_specific_label([I|Is], Fail, Prev) -> - case normalize_op(I) of - error -> - error; - {Normalized,Fail} -> - case will_succeed(Prev, Normalized) of - no -> - %% Will branch to FailLabel. - Fail; - yes -> - %% Will definitely never branch. - shortcut_specific_label(Is, Fail, Prev); - maybe -> - %% May branch, but still OK since it will branch - %% to FailLabel. - shortcut_specific_label(Is, Fail, Prev) - end; - {Normalized,_} -> - %% This test instruction will branch to a different - %% fail label, if it branches at all. - case will_succeed(Prev, Normalized) of - yes -> - %% Still OK, since the branch will never be - %% taken. - shortcut_specific_label(Is, Fail, Prev); - no -> - %% Give up. The branch will definitely be taken - %% to a different fail label. - error; - maybe -> - %% Give up. If the branch is taken, it will be - %% to a different fail label. - error - end - end. - - -%% shortcut_selectval(List, Reg, Fail, PrevCond) -> FailLabel | error -%% Try to shortcut a selectval instruction. A selectval instruction -%% is equivalent to the following instruction sequence: -%% -%% is_ne_exact L1 Reg Value1 -%% . -%% . -%% . -%% is_ne_exact LN Reg ValueN -%% jump DefaultFailLabel -%% -shortcut_selectval([Val,{f,Lbl}|T], R, Fail, Prev) -> - case will_succeed(Prev, {'=/=',R,get_literal(Val)}) of - yes -> shortcut_selectval(T, R, Fail, Prev); - no -> Lbl; - maybe -> error - end; -shortcut_selectval([], _, Fail, _) -> Fail. - -%% will_succeed(PrevCondition, Condition) -> yes | no | maybe -%% PrevCondition is a condition known to be true. This function -%% will tell whether Condition will succeed. - -will_succeed({Op1,Reg,A}, {Op2,Reg,B}) -> - will_succeed_1(Op1, A, Op2, B); -will_succeed({'=:=',Reg,{literal,A}}, {TypeTest,Reg}) -> - case erlang:TypeTest(A) of - false -> no; - true -> yes - end; -will_succeed({_,_,_}, maybe) -> - maybe; -will_succeed({_,_,_}, Test) when is_tuple(Test) -> - maybe. - -will_succeed_1('=:=', A, '<', B) -> - if - B =< A -> no; - true -> yes - end; -will_succeed_1('=:=', A, '=<', B) -> - if - B < A -> no; - true -> yes - end; -will_succeed_1('=:=', A, '=:=', B) -> - if - A =:= B -> yes; - true -> no - end; -will_succeed_1('=:=', A, '=/=', B) -> - if - A =:= B -> no; - true -> yes - end; -will_succeed_1('=:=', A, '>=', B) -> - if - B > A -> no; - true -> yes - end; -will_succeed_1('=:=', A, '>', B) -> - if - B >= A -> no; - true -> yes - end; - -will_succeed_1('=/=', A, '=/=', B) when A =:= B -> yes; -will_succeed_1('=/=', A, '=:=', B) when A =:= B -> no; - -will_succeed_1('<', A, '=:=', B) when B >= A -> no; -will_succeed_1('<', A, '=/=', B) when B >= A -> yes; -will_succeed_1('<', A, '<', B) when B >= A -> yes; -will_succeed_1('<', A, '=<', B) when B > A -> yes; -will_succeed_1('<', A, '>=', B) when B > A -> no; -will_succeed_1('<', A, '>', B) when B >= A -> no; - -will_succeed_1('=<', A, '=:=', B) when B > A -> no; -will_succeed_1('=<', A, '=/=', B) when B > A -> yes; -will_succeed_1('=<', A, '<', B) when B > A -> yes; -will_succeed_1('=<', A, '=<', B) when B >= A -> yes; -will_succeed_1('=<', A, '>=', B) when B > A -> no; -will_succeed_1('=<', A, '>', B) when B >= A -> no; - -will_succeed_1('>=', A, '=:=', B) when B < A -> no; -will_succeed_1('>=', A, '=/=', B) when B < A -> yes; -will_succeed_1('>=', A, '<', B) when B =< A -> no; -will_succeed_1('>=', A, '=<', B) when B < A -> no; -will_succeed_1('>=', A, '>=', B) when B =< A -> yes; -will_succeed_1('>=', A, '>', B) when B < A -> yes; - -will_succeed_1('>', A, '=:=', B) when B =< A -> no; -will_succeed_1('>', A, '=/=', B) when B =< A -> yes; -will_succeed_1('>', A, '<', B) when B =< A -> no; -will_succeed_1('>', A, '=<', B) when B < A -> no; -will_succeed_1('>', A, '>=', B) when B =< A -> yes; -will_succeed_1('>', A, '>', B) when B < A -> yes; - -will_succeed_1(_, _, _, _) -> maybe. - -%% normalize_op(Instruction) -> {Normalized,FailLabel} | error -%% Normalized = {Operator,Register,Literal} | -%% {TypeTest,Register} | -%% maybe -%% Operation = '<' | '=<' | '=:=' | '=/=' | '>=' | '>' -%% TypeTest = is_atom | is_integer ... -%% Literal = {literal,Term} -%% -%% Normalize a relational operator to facilitate further -%% comparisons between operators. Always make the register -%% operand the first operand. Thus the following instruction: -%% -%% {test,is_ge,{f,99},{integer,13},{x,0}} -%% -%% will be normalized to: -%% -%% {'=<',{x,0},{literal,13}} -%% -%% NOTE: Bit syntax test instructions are scary. They may change the -%% state of match contexts and update registers, so we don't dare -%% mess with them. - -normalize_op({test,is_ge,{f,Fail},Ops}) -> - normalize_op_1('>=', Ops, Fail); -normalize_op({test,is_lt,{f,Fail},Ops}) -> - normalize_op_1('<', Ops, Fail); -normalize_op({test,is_eq_exact,{f,Fail},Ops}) -> - normalize_op_1('=:=', Ops, Fail); -normalize_op({test,is_ne_exact,{f,Fail},Ops}) -> - normalize_op_1('=/=', Ops, Fail); -normalize_op({test,Op,{f,Fail},[R]}) -> - case erl_internal:new_type_test(Op, 1) of - true -> {{Op,R},Fail}; - false -> {maybe,Fail} - end; -normalize_op({test,_,{f,Fail},_}=I) -> - case beam_utils:is_pure_test(I) of - true -> {maybe,Fail}; - false -> error - end; -normalize_op(_) -> - error. - -normalize_op_1(Op, [Op1,Op2], Fail) -> - case {get_literal(Op1),get_literal(Op2)} of - {error,error} -> - %% Both operands are registers. - {maybe,Fail}; - {error,Lit} -> - {{Op,Op1,Lit},Fail}; - {Lit,error} -> - {{turn_op(Op),Op2,Lit},Fail}; - {_,_} -> - %% Both operands are literals. Can probably only - %% happen if the Core Erlang optimizations passes were - %% turned off, so don't bother trying to do something - %% smart here. - {maybe,Fail} - end. - -turn_op('<') -> '>'; -turn_op('>=') -> '=<'; -turn_op('=:='=Op) -> Op; -turn_op('=/='=Op) -> Op. - -negate_op('>=') -> '<'; -negate_op('<') -> '>='; -negate_op('=<') -> '>'; -negate_op('>') -> '=<'; -negate_op('=:=') -> '=/='; -negate_op('=/=') -> '=:='. - -get_literal({atom,Val}) -> - {literal,Val}; -get_literal({integer,Val}) -> - {literal,Val}; -get_literal({float,Val}) -> - {literal,Val}; -get_literal(nil) -> - {literal,[]}; -get_literal({literal,_}=Lit) -> - Lit; -get_literal({_,_}) -> error. - - -%%% -%%% Removing stores to Y registers is not always safe -%%% if there is an instruction that causes an exception -%%% within a catch. In practice, there are few or no -%%% opportunities for removing stores to Y registers anyway -%%% if sys_core_fold has been run. -%%% - -is_killed_at({x,_}=Reg, Lbl, D) -> - beam_utils:is_killed_at(Reg, Lbl, D); -is_killed_at({y,_}, _, _) -> - false. diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl index 06f3cc19bb..6d0a8db2dc 100644 --- a/lib/compiler/src/beam_jump.erl +++ b/lib/compiler/src/beam_jump.erl @@ -22,8 +22,8 @@ -module(beam_jump). -export([module/2, - is_unreachable_after/1,is_exit_instruction/1, - remove_unused_labels/1,instr_labels/1]). + is_exit_instruction/1, + remove_unused_labels/1]). %%% The following optimisations are done: %%% @@ -128,27 +128,123 @@ %%% on the program state. %%% --import(lists, [reverse/1,reverse/2,foldl/3]). +-import(lists, [foldl/3,mapfoldl/3,reverse/1,reverse/2]). -type instruction() :: beam_utils:instruction(). -spec module(beam_utils:module_code(), [compile:option()]) -> {'ok',beam_utils:module_code()}. -module({Mod,Exp,Attr,Fs0,Lc}, _Opt) -> - Fs = [function(F) || F <- Fs0], +module({Mod,Exp,Attr,Fs0,Lc0}, _Opt) -> + {Fs,Lc} = mapfoldl(fun function/2, Lc0, Fs0), {ok,{Mod,Exp,Attr,Fs,Lc}}. %% function(Function) -> Function' %% Optimize jumps and branches. %% %% NOTE: This function assumes that there are no labels inside blocks. -function({function,Name,Arity,CLabel,Asm0}) -> - Asm1 = share(Asm0), - Asm2 = move(Asm1), - Asm3 = opt(Asm2, CLabel), - Asm = remove_unused_labels(Asm3), - {function,Name,Arity,CLabel,Asm}. +function({function,Name,Arity,CLabel,Asm0}, Lc0) -> + Asm1 = eliminate_moves(Asm0), + {Asm2,Lc} = insert_labels(Asm1, Lc0, []), + Asm3 = share(Asm2), + Asm4 = move(Asm3), + Asm5 = opt(Asm4, CLabel), + Asm = remove_unused_labels(Asm5), + {{function,Name,Arity,CLabel,Asm},Lc}. + +%%% +%%% Scan instructions in execution order and remove redundant 'move' +%%% instructions. 'move' instructions are redundant if we know that +%%% the register already contains the value being assigned, as in the +%%% following code: +%%% +%%% select_val Register FailLabel [... Literal => L1...] +%%% . +%%% . +%%% . +%%% L1: move Literal Register +%%% + +eliminate_moves(Is) -> + eliminate_moves(Is, #{}, []). + +eliminate_moves([{select,select_val,Reg,_,List}=I|Is], D0, Acc) -> + D = update_value_dict(List, Reg, D0), + eliminate_moves(Is, D, [I|Acc]); +eliminate_moves([{label,Lbl},{block,[{set,[Dst],[Lit],move}|BlkIs]}=Blk0|Is], + D, Acc0) -> + Acc = [{label,Lbl}|Acc0], + case already_has_value(Lit, Lbl, Dst, D) andalso + no_fallthrough(Acc0) of + true -> + %% Remove redundant 'move' instruction. + Blk = {block,BlkIs}, + eliminate_moves([Blk|Is], D, Acc); + false -> + %% Keep 'move' instruction. + eliminate_moves([Blk0|Is], D, Acc) + end; +eliminate_moves([{block,[]}|Is], D, Acc) -> + %% Empty blocks can prevent further jump optimizations. + eliminate_moves(Is, D, Acc); +eliminate_moves([I|Is], D0, Acc) -> + D = update_unsafe_labels(I, D0), + eliminate_moves(Is, D, [I|Acc]); +eliminate_moves([], _, Acc) -> reverse(Acc). + +no_fallthrough([I|_]) -> + is_unreachable_after(I). + +already_has_value(Lit, Lbl, Reg, D) -> + Key = {Lbl,Reg}, + case D of + #{Lbl:=unsafe} -> + false; + #{Key:=Lit} -> + true; + #{} -> + false + end. + +update_value_dict([Lit,{f,Lbl}|T], Reg, D0) -> + Key = {Lbl,Reg}, + D = case D0 of + #{Key := inconsistent} -> D0; + #{Key := _} -> D0#{Key := inconsistent}; + _ -> D0#{Key => Lit} + end, + update_value_dict(T, Reg, D); +update_value_dict([], _, D) -> D. + +update_unsafe_labels(I, D) -> + Ls = instr_labels(I), + update_unsafe_labels_1(Ls, D). + +update_unsafe_labels_1([L|Ls], D) -> + update_unsafe_labels_1(Ls, D#{L=>unsafe}); +update_unsafe_labels_1([], D) -> D. + +%%% +%%% It seems to be useful to insert extra labels after certain +%%% test instructions. This used to be done by beam_dead. +%%% + +insert_labels([{test,Op,_,_}=I|Is], Lc, Acc) -> + Useful = case Op of + is_lt -> true; + is_ge -> true; + is_eq_exact -> true; + is_ne_exact -> true; + _ -> false + end, + case Useful of + false -> insert_labels(Is, Lc, [I|Acc]); + true -> insert_labels(Is, Lc+1, [{label,Lc},I|Acc]) + end; +insert_labels([I|Is], Lc, Acc) -> + insert_labels(Is, Lc, [I|Acc]); +insert_labels([], Lc, Acc) -> + {reverse(Acc),Lc}. %%% %%% (1) We try to share the code for identical code segments by replacing all diff --git a/lib/compiler/src/beam_split.erl b/lib/compiler/src/beam_split.erl deleted file mode 100644 index 7b18946ae0..0000000000 --- a/lib/compiler/src/beam_split.erl +++ /dev/null @@ -1,90 +0,0 @@ -%% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2011-2018. All Rights Reserved. -%% -%% Licensed under the Apache License, Version 2.0 (the "License"); -%% you may not use this file except in compliance with the License. -%% You may obtain a copy of the License at -%% -%% http://www.apache.org/licenses/LICENSE-2.0 -%% -%% Unless required by applicable law or agreed to in writing, software -%% distributed under the License is distributed on an "AS IS" BASIS, -%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -%% See the License for the specific language governing permissions and -%% limitations under the License. -%% -%% %CopyrightEnd% -%% - --module(beam_split). --export([module/2]). - --import(lists, [reverse/1]). - --spec module(beam_utils:module_code(), [compile:option()]) -> - {'ok',beam_utils:module_code()}. - -module({Mod,Exp,Attr,Fs0,Lc}, _Opts) -> - Fs = [split_blocks(F) || F <- Fs0], - {ok,{Mod,Exp,Attr,Fs,Lc}}. - -%% We must split the basic block when we encounter instructions with labels, -%% such as catches and BIFs. All labels must be visible outside the blocks. - -split_blocks({function,Name,Arity,CLabel,Is0}) -> - Is = split_blocks(Is0, []), - {function,Name,Arity,CLabel,Is}. - -split_blocks([{block,Bl}|Is], Acc0) -> - Acc = split_block(Bl, [], Acc0), - split_blocks(Is, Acc); -split_blocks([I|Is], Acc) -> - split_blocks(Is, [I|Acc]); -split_blocks([], Acc) -> reverse(Acc). - -split_block([{set,[R],As,{bif,N,{f,Lbl}=Fail}}|Is], Bl, Acc) when Lbl =/= 0 -> - split_block(Is, [], [{bif,N,Fail,As,R}|make_block(Bl, Acc)]); -split_block([{set,[],[],{line,_}=Line}, - {set,[R],As,{bif,raise,{f,_}=Fail}}|Is], Bl, Acc) -> - split_block(Is, [], [{bif,raise,Fail,As,R},Line|make_block(Bl, Acc)]); -split_block([{set,[R],As,{alloc,Live,{gc_bif,N,{f,Lbl}=Fail}}}|Is], Bl, Acc) - when Lbl =/= 0 -> - split_block(Is, [], [{gc_bif,N,Fail,Live,As,R}|make_block(Bl, Acc)]); -split_block([{set,[D],[S|Puts],{alloc,R,{put_map,Op,{f,Lbl}=Fail}}}|Is], - Bl, Acc) when Lbl =/= 0 -> - split_block(Is, [], [{put_map,Fail,Op,S,D,R,{list,Puts}}| - make_block(Bl, Acc)]); -split_block([{set,[R],[],{try_catch,Op,L}}|Is], Bl, Acc) -> - split_block(Is, [], [{Op,R,L}|make_block(Bl, Acc)]); -split_block([I|Is], Bl, Acc) -> - split_block(Is, [I|Bl], Acc); -split_block([], Bl, Acc) -> make_block(Bl, Acc). - -make_block([], Acc) -> Acc; -make_block([{set,[D],Ss,{bif,Op,Fail}}|Bl]=Bl0, Acc) -> - %% If the last instruction in the block is a comparison or boolean operator - %% (such as '=:='), move it out of the block to facilitate further - %% optimizations. - Arity = length(Ss), - case erl_internal:comp_op(Op, Arity) orelse - erl_internal:new_type_test(Op, Arity) orelse - erl_internal:bool_op(Op, Arity) of - false -> - [{block,reverse(Bl0)}|Acc]; - true -> - I = {bif,Op,Fail,Ss,D}, - case Bl =:= [] of - true -> [I|Acc]; - false -> [I,{block,reverse(Bl)}|Acc] - end - end; -make_block([{set,[Dst],[Src],move}|Bl], Acc) -> - %% Make optimization of {move,Src,Dst}, {jump,...} possible. - I = {move,Src,Dst}, - case Bl =:= [] of - true -> [I|Acc]; - false -> [I,{block,reverse(Bl)}|Acc] - end; -make_block(Bl, Acc) -> [{block,reverse(Bl)}|Acc]. diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl index a0ebfff5f7..a59a92ef8c 100644 --- a/lib/compiler/src/compile.erl +++ b/lib/compiler/src/compile.erl @@ -841,10 +841,6 @@ asm_passes() -> {iff,dexcept,{listing,"except"}}, {unless,no_bs_opt,{pass,beam_bs}}, {iff,dbs,{listing,"bs"}}, - {pass,beam_split}, - {iff,dsplit,{listing,"split"}}, - {unless,no_dead,{pass,beam_dead}}, - {iff,ddead,{listing,"dead"}}, {unless,no_jopt,{pass,beam_jump}}, {iff,djmp,{listing,"jump"}}, {unless,no_peep_opt,{pass,beam_peep}}, @@ -2037,7 +2033,6 @@ pre_load() -> beam_bs, beam_bsm, beam_clean, - beam_dead, beam_dict, beam_except, beam_flatten, @@ -2052,7 +2047,6 @@ pre_load() -> beam_ssa_pre_codegen, beam_ssa_recv, beam_ssa_type, - beam_split, beam_trim, beam_utils, beam_validator, diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src index f5e2b31b87..bb281376ef 100644 --- a/lib/compiler/src/compiler.app.src +++ b/lib/compiler/src/compiler.app.src @@ -27,7 +27,6 @@ beam_bs, beam_bsm, beam_clean, - beam_dead, beam_dict, beam_disasm, beam_except, @@ -46,7 +45,6 @@ beam_ssa_pre_codegen, beam_ssa_recv, beam_ssa_type, - beam_split, beam_trim, beam_utils, beam_validator, diff --git a/lib/compiler/test/compile_SUITE.erl b/lib/compiler/test/compile_SUITE.erl index 2ec0bfdf83..38bc928f85 100644 --- a/lib/compiler/test/compile_SUITE.erl +++ b/lib/compiler/test/compile_SUITE.erl @@ -392,7 +392,6 @@ do_file_listings(DataDir, PrivDir, [File|Files]) -> do_listing(Simple, TargetDir, dblk, ".block"), do_listing(Simple, TargetDir, dexcept, ".except"), do_listing(Simple, TargetDir, dbs, ".bs"), - do_listing(Simple, TargetDir, ddead, ".dead"), do_listing(Simple, TargetDir, djmp, ".jump"), do_listing(Simple, TargetDir, dclean, ".clean"), do_listing(Simple, TargetDir, dpeep, ".peep"), diff --git a/lib/compiler/test/guard_SUITE.erl b/lib/compiler/test/guard_SUITE.erl index 6ccc0c8fd4..e66253f8a0 100644 --- a/lib/compiler/test/guard_SUITE.erl +++ b/lib/compiler/test/guard_SUITE.erl @@ -35,8 +35,7 @@ basic_andalso_orelse/1,traverse_dcd/1, check_qlc_hrl/1,andalso_semi/1,t_tuple_size/1,binary_part/1, bad_constants/1,bad_guards/1, - guard_in_catch/1,beam_bool_SUITE/1, - cover_beam_dead/1]). + guard_in_catch/1,beam_bool_SUITE/1]). suite() -> [{ct_hooks,[ts_install_cth]}]. @@ -54,8 +53,7 @@ groups() -> rel_ops,rel_op_combinations, literal_type_tests,basic_andalso_orelse,traverse_dcd, check_qlc_hrl,andalso_semi,t_tuple_size,binary_part, - bad_constants,bad_guards,guard_in_catch,beam_bool_SUITE, - cover_beam_dead]}]. + bad_constants,bad_guards,guard_in_catch,beam_bool_SUITE]}]. init_per_suite(Config) -> test_lib:recompile(?MODULE), @@ -2211,32 +2209,6 @@ maps() -> evidence(#{0 := Charge}) when 0; #{[] => Charge} == #{[] => 42} -> ok. -cover_beam_dead(_Config) -> - Mod = ?FUNCTION_NAME, - Attr = [], - Fs = [{function,test,1,2, - [{label,1}, - {line,[]}, - {func_info,{atom,Mod},{atom,test},1}, - {label,2}, - %% Cover beam_dead:turn_op/1 using swapped operand order. - {test,is_ne_exact,{f,3},[{integer,1},{x,0}]}, - {test,is_eq_exact,{f,1},[{atom,a},{x,0}]}, - {label,3}, - {move,{atom,ok},{x,0}}, - return]}], - Exp = [{test,1}], - Asm = {Mod,Exp,Attr,Fs,3}, - {ok,Mod,Beam} = compile:forms(Asm, [from_asm,binary,report]), - {module,Mod} = code:load_binary(Mod, Mod, Beam), - ok = Mod:test(1), - ok = Mod:test(a), - {'EXIT',_} = (catch Mod:test(other)), - true = code:delete(Mod), - _ = code:purge(Mod), - - ok. - %% Call this function to turn off constant propagation. id(I) -> I. diff --git a/lib/compiler/test/misc_SUITE.erl b/lib/compiler/test/misc_SUITE.erl index beae5eb618..4c2d0116c9 100644 --- a/lib/compiler/test/misc_SUITE.erl +++ b/lib/compiler/test/misc_SUITE.erl @@ -234,16 +234,6 @@ silly_coverage(Config) when is_list(Config) -> {label,2}|non_proper_list]}],99}, expect_error(fun() -> beam_except:module(ExceptInput, []) end), - %% beam_dead. This is tricky. Our function must look OK to - %% beam_utils:clean_labels/1, but must crash beam_dead. - DeadInput = {?MODULE,[{foo,0}],[], - [{function,foo,0,2, - [{label,1}, - {func_info,{atom,?MODULE},{atom,foo},0}, - {label,2}, - {test,is_eq_exact,{f,1},[bad,operands]}]}],99}, - expect_error(fun() -> beam_dead:module(DeadInput, []) end), - %% beam_clean CleanInput = {?MODULE,[{foo,0}],[], [{function,foo,0,2, -- cgit v1.2.3