From 9c852215c79ed6ec42c223463d4b5a0c221b4bf0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Wed, 16 Jan 2019 19:06:19 +0100 Subject: beam_ssa_type: Eliminate redundant 'succeeded' instructions The beam_ssa_type pass would leave redundant 'succeeded' instructions, and depend on the live optimization pass to remove them. Update beam_ssa_type to remove redundant 'succeeded' instructions. This will not improve the generated code, but will improve compilation times since it eliminates instructions and variables. --- lib/compiler/src/beam_ssa_opt.erl | 11 +++-------- lib/compiler/src/beam_ssa_type.erl | 17 +++++++++++++++-- 2 files changed, 18 insertions(+), 10 deletions(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 6bba47b4ac..e23e62b5ad 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -856,14 +856,9 @@ live_opt_is([#b_set{op=succeeded,dst=SuccDst=SuccDstVar, #b_set{dst=Dst}=I|Is], Live0, Acc) -> case gb_sets:is_member(Dst, Live0) of true -> - case gb_sets:is_member(SuccDst, Live0) of - true -> - Live1 = gb_sets:add(Dst, Live0), - Live = gb_sets:delete_any(SuccDst, Live1), - live_opt_is([I|Is], Live, [SuccI|Acc]); - false -> - live_opt_is([I|Is], Live0, Acc) - end; + Live1 = gb_sets:add(Dst, Live0), + Live = gb_sets:delete_any(SuccDst, Live1), + live_opt_is([I|Is], Live, [SuccI|Acc]); false -> case live_opt_unused(I) of {replace,NewI0} -> diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index ab5ea4b1a4..4ea3781783 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -139,6 +139,19 @@ opt_is([#b_set{op=phi,dst=Dst,args=Args0}=I0|Is], Ds = Ds0#{Dst=>I}, opt_is(Is, Ts, Ds, Ls, Sub0, [I|Acc]) end; +opt_is([#b_set{op=succeeded,args=Args0,dst=Dst}=I], + Ts0, Ds0, Ls, Sub0, Acc) -> + Args = simplify_args(Args0, Sub0, Ts0), + Type = type(succeeded, Args, Ts0, Ds0), + case get_literal_from_type(Type) of + #b_literal{}=Lit -> + Sub = Sub0#{Dst=>Lit}, + opt_is([], Ts0, Ds0, Ls, Sub, Acc); + none -> + Ts = update_types(I, Ts0, Ds0), + Ds = Ds0#{Dst=>I}, + opt_is([], Ts, Ds, Ls, Sub0, [I|Acc]) + end; opt_is([#b_set{args=Args0,dst=Dst}=I0|Is], Ts0, Ds0, Ls, Sub0, Acc) -> Args = simplify_args(Args0, Sub0, Ts0), @@ -296,8 +309,6 @@ simplify(#b_set{op=put_tuple,args=Args}=I, _Ts) -> 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. @@ -627,6 +638,8 @@ type(succeeded, [#b_var{}=Src], Ts, Ds) -> #b_set{} -> t_boolean() end; +type(succeeded, [#b_literal{}], _Ts, _Ds) -> + t_atom(true); type(_, _, _, _) -> any. arith_op_type(Args, Ts) -> -- cgit v1.2.3 From 9814a205a2cf9e1024261e2eee80e460e78600d0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Wed, 16 Jan 2019 19:31:22 +0100 Subject: beam_ssa_opt: Run the type optimization pass twice The code will be significantly improved by running the type optimization pass twice. The ssa_opt_misc pass can be eliminated because everything it does is also done by the type optimization pass. --- lib/compiler/src/beam_ssa_opt.erl | 102 ++++---------------------------------- 1 file changed, 9 insertions(+), 93 deletions(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index e23e62b5ad..df40c918b2 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -22,7 +22,7 @@ -export([module/2]). -include("beam_ssa.hrl"). --import(lists, [all/2,append/1,foldl/3,keyfind/3,member/2, +-import(lists, [append/1,foldl/3,keyfind/3,member/2, reverse/1,reverse/2, splitwith/2,takewhile/2,unzip/1]). @@ -55,9 +55,13 @@ passes(Opts0) -> ?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. + %% 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. + %% + %% Run beam_ssa_type twice, because there will be more + %% opportunities for optimizations after running beam_ssa_dead. ?PASS(ssa_opt_cse), ?PASS(ssa_opt_type), ?PASS(ssa_opt_live), @@ -65,12 +69,12 @@ passes(Opts0) -> ?PASS(ssa_opt_dead), ?PASS(ssa_opt_cse), %Second time. ?PASS(ssa_opt_float), + ?PASS(ssa_opt_type), %Second time. ?PASS(ssa_opt_live), %Second time. ?PASS(ssa_opt_bsm), ?PASS(ssa_opt_bsm_units), ?PASS(ssa_opt_bsm_shortcut), - ?PASS(ssa_opt_misc), ?PASS(ssa_opt_tuple_size), ?PASS(ssa_opt_sw), ?PASS(ssa_opt_blockify), @@ -1345,94 +1349,6 @@ opt_bs_put_split_int_1(Int, L, R) -> opt_bs_put_split_int_1(Int, Mid + 1, R) end. -%%% -%%% Miscellanous optimizations in execution order. -%%% - -ssa_opt_misc(#st{ssa=Linear}=St) -> - St#st{ssa=misc_opt(Linear, #{})}. - -misc_opt([{L,#b_blk{is=Is0,last=Last0}=Blk0}|Bs], Sub0) -> - {Is,Sub} = misc_opt_is(Is0, Sub0, []), - Last = sub(Last0, Sub), - Blk = Blk0#b_blk{is=Is,last=Last}, - [{L,Blk}|misc_opt(Bs, Sub)]; -misc_opt([], _) -> []. - -misc_opt_is([#b_set{op=phi}=I0|Is], Sub0, Acc) -> - #b_set{dst=Dst,args=Args} = I = sub(I0, Sub0), - 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}, - misc_opt_is(Is, Sub, 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 - #b_literal{}=Literal -> - misc_opt_is(Is, Sub#{Dst=>Literal}, Acc); - error -> - misc_opt_is(Is, Sub, [I|Acc]) - end; -misc_opt_is([], Sub, Acc) -> - {reverse(Acc),Sub}. - -all_same([{H,_}|T]) -> - all(fun({E,_}) -> E =:= H end, T). - -make_literal(put_tuple, Args) -> - case make_literal_list(Args, []) of - error -> - error; - List -> - #b_literal{val=list_to_tuple(List)} - end; -make_literal(put_list, [#b_literal{val=H},#b_literal{val=T}]) -> - #b_literal{val=[H|T]}; -make_literal(_, _) -> error. - -make_literal_list([#b_literal{val=H}|T], Acc) -> - make_literal_list(T, [H|Acc]); -make_literal_list([_|_], _) -> - error; -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. - %%% %%% Optimize expressions such as "tuple_size(Var) =:= 2". %%% -- cgit v1.2.3 From a9f0df66e2b4c483fc92d835ac77ded1529aa420 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 17 Jan 2019 05:17:55 +0100 Subject: beam_ssa_codegen: Remove forgotten and unreachable clause fd682dd3b1dc corrected label generation for 'or', but forgot to remove the old incorrect clause (that can no longer be reached). --- lib/compiler/src/beam_ssa_codegen.erl | 7 ------- 1 file changed, 7 deletions(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl index fa5b19228b..fe1a0c8480 100644 --- a/lib/compiler/src/beam_ssa_codegen.erl +++ b/lib/compiler/src/beam_ssa_codegen.erl @@ -1280,13 +1280,6 @@ bif_to_test(Op, Args, Fail, 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) -> -- cgit v1.2.3 From ceb43f022dcb1f461c53773392a40a4afbc291cf Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 17 Jan 2019 08:16:50 +0100 Subject: beam_ssa_opt: Run ssa_opt_tuple_size early Running ssa_opt_tuple_size early will give more opportunities for optimizations. --- lib/compiler/src/beam_ssa_opt.erl | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index df40c918b2..6f7044f006 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -52,6 +52,7 @@ passes(Opts0) -> ?PASS(ssa_opt_coalesce_phis), ?PASS(ssa_opt_element), ?PASS(ssa_opt_linearize), + ?PASS(ssa_opt_tuple_size), ?PASS(ssa_opt_record), %% Run ssa_opt_cse twice, because it will help ssa_opt_dead, @@ -75,7 +76,6 @@ passes(Opts0) -> ?PASS(ssa_opt_bsm), ?PASS(ssa_opt_bsm_units), ?PASS(ssa_opt_bsm_shortcut), - ?PASS(ssa_opt_tuple_size), ?PASS(ssa_opt_sw), ?PASS(ssa_opt_blockify), ?PASS(ssa_opt_sink), -- cgit v1.2.3 From 277331c4823e10a7bbc723a7116cb5e26596a408 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 18 Jan 2019 05:53:48 +0100 Subject: beam_ssa_type: Simplify is_singleton_type/1 --- lib/compiler/src/beam_ssa_type.erl | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 4ea3781783..ede57875e2 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -1218,10 +1218,8 @@ t_tuple_size(#t_tuple{size=Size,exact=true}) -> t_tuple_size(_) -> none. -is_singleton_type(#t_atom{elements=[_]}) -> true; -is_singleton_type(#t_integer{elements={V,V}}) -> true; -is_singleton_type(nil) -> true; -is_singleton_type(_) -> false. +is_singleton_type(Type) -> + get_literal_from_type(Type) =/= none. %% join(Type1, Type2) -> Type %% Return the "join" of Type1 and Type2. The join is a more general -- cgit v1.2.3