From 1858cb81391d2bce29b4b7620574ca60128cebf7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 12 Mar 2010 09:12:05 +0100 Subject: erl_expand_records: Replace is_record() with matching The compiler currently generates better code for: f(#r1{}) -> r1; f(#r2{}) -> r2; f(#r3{}) -> r3. than for: g(X) when is_record(X, r1) -> r1; g(X) when is_record(X, r2) -> r2; g(X) when is_record(X, r3) -> r3. The compiler generates good code for pattern matching (as in f/1), but in g/1 there are no patterns to match, and the clause to be executed must be chosen by evaluating the guards sequentially until one succeeds. Make the compiler generate better code by replacing calls to is_record() with matching in the function head (basically, g/1 will automatically be rewritten to do pattern matching as in f/1). Note that this rewrite will also benefit code such as: h(X) when X#r1.a =:= 1 -> ok. because it would have been rewritten to: h(X) when (is_record(X, r1, 3) orelse fail) and (element(2, X) =:= 1) -> ok. which in turn will be rewritten to: h({r1,_,_}=X) when (true orelse fail) and (element(2, X) =:= 1) -> ok. (That will be further simplified in later compiler passes.) --- lib/stdlib/src/erl_expand_records.erl | 132 +++++++++++++++++++++++++++++++++- 1 file changed, 130 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/stdlib/src/erl_expand_records.erl b/lib/stdlib/src/erl_expand_records.erl index a38b7639d8..18c467db81 100644 --- a/lib/stdlib/src/erl_expand_records.erl +++ b/lib/stdlib/src/erl_expand_records.erl @@ -95,8 +95,9 @@ forms([F | Fs0], St0) -> forms([], St) -> {[],St}. clauses([{clause,Line,H0,G0,B0} | Cs0], St0) -> - {H,St1} = head(H0, St0), - {G,St2} = guard(G0, St1), + {H1,St1} = head(H0, St0), + {G1,St2} = guard(G0, St1), + {H,G} = optimize_is_record(H1, G1), {B,St3} = exprs(B0, St2), {Cs,St4} = clauses(Cs0, St3), {[{clause,Line,H,G,B} | Cs],St4}; @@ -800,5 +801,132 @@ imported(F, A, St) -> error -> no end. +%%% +%%% Replace is_record/3 in guards with matching if possible. +%%% + +optimize_is_record(H0, G0) -> + case opt_rec_vars(G0) of + [] -> + {H0,G0}; + Rs0 -> + {H,Rs} = opt_pattern_list(H0, Rs0), + G = opt_remove(G0, Rs), + {H,G} + end. + + +%% opt_rec_vars(Guards) -> Vars. +%% Search through the guard expression, looking for +%% variables referenced in those is_record/3 calls that +%% will fail the entire guard if they evaluate to 'false' +%% +%% In the following code +%% +%% f(X, Y, Z) when is_record(X, r1) andalso +%% (is_record(Y, r2) orelse is_record(Z, r3)) +%% +%% the entire guard will be false if the record test for +%% X fails, and the clause can be rewritten to: +%% +%% f({r1,...}=X, Y, Z) when true andalso +%% (is_record(Y, r2) or is_record(Z, r3)) +%% +opt_rec_vars([G|Gs]) -> + Rs = opt_rec_vars_1(G, orddict:new()), + opt_rec_vars(Gs, Rs); +opt_rec_vars([]) -> orddict:new(). + +opt_rec_vars([G|Gs], Rs0) -> + Rs1 = opt_rec_vars_1(G, orddict:new()), + Rs = ordsets:intersection(Rs0, Rs1), + opt_rec_vars(Gs, Rs); +opt_rec_vars([], Rs) -> Rs. + +opt_rec_vars_1([T|Ts], Rs0) -> + Rs = opt_rec_vars_2(T, Rs0), + opt_rec_vars_1(Ts, Rs); +opt_rec_vars_1([], Rs) -> Rs. + +opt_rec_vars_2({op,_,'and',A1,A2}, Rs) -> + opt_rec_vars_1([A1,A2], Rs); +opt_rec_vars_2({op,_,'andalso',A1,A2}, Rs) -> + opt_rec_vars_1([A1,A2], Rs); +opt_rec_vars_2({op,_,'orelse',Arg,{atom,_,fail}}, Rs) -> + %% Since the second argument guarantees failure, + %% it is safe to inspect the first argument. + opt_rec_vars_2(Arg, Rs); +opt_rec_vars_2({call,_,{remote,_,{atom,_,erlang},{atom,_,is_record}}, + [{var,_,V},{atom,_,Tag},{integer,_,Sz}]}, Rs) -> + orddict:store(V, {Tag,Sz}, Rs); +opt_rec_vars_2({call,_,{atom,_,is_record}, + [{var,_,V},{atom,_,Tag},{integer,_,Sz}]}, Rs) -> + orddict:store(V, {Tag,Sz}, Rs); +opt_rec_vars_2(_, Rs) -> Rs. + +opt_pattern_list(Ps, Rs) -> + opt_pattern_list(Ps, Rs, []). + +opt_pattern_list([P0|Ps], Rs0, Acc) -> + {P,Rs} = opt_pattern(P0, Rs0), + opt_pattern_list(Ps, Rs, [P|Acc]); +opt_pattern_list([], Rs, Acc) -> + {reverse(Acc),Rs}. + +opt_pattern({var,_,V}=Var, Rs0) -> + case orddict:find(V, Rs0) of + {ok,{Tag,Sz}} -> + Rs = orddict:store(V, {remove,Tag,Sz}, Rs0), + {opt_var(Var, Tag, Sz),Rs}; + _ -> + {Var,Rs0} + end; +opt_pattern({cons,Line,H0,T0}, Rs0) -> + {H,Rs1} = opt_pattern(H0, Rs0), + {T,Rs} = opt_pattern(T0, Rs1), + {{cons,Line,H,T},Rs}; +opt_pattern({tuple,Line,Es0}, Rs0) -> + {Es,Rs} = opt_pattern_list(Es0, Rs0), + {{tuple,Line,Es},Rs}; +opt_pattern({match,Line,Pa0,Pb0}, Rs0) -> + {Pa,Rs1} = opt_pattern(Pa0, Rs0), + {Pb,Rs} = opt_pattern(Pb0, Rs1), + {{match,Line,Pa,Pb},Rs}; +opt_pattern(P, Rs) -> {P,Rs}. + +opt_var({var,Line,_}=Var, Tag, Sz) -> + Rp = record_pattern(2, -1, ignore, Sz, Line, [{atom,Line,Tag}]), + {match,Line,{tuple,Line,Rp},Var}. + +opt_remove(Gs, Rs) -> + [opt_remove_1(G, Rs) || G <- Gs]. + +opt_remove_1(Ts, Rs) -> + [opt_remove_2(T, Rs) || T <- Ts]. + +opt_remove_2({op,L,'and'=Op,A1,A2}, Rs) -> + {op,L,Op,opt_remove_2(A1, Rs),opt_remove_2(A2, Rs)}; +opt_remove_2({op,L,'andalso'=Op,A1,A2}, Rs) -> + {op,L,Op,opt_remove_2(A1, Rs),opt_remove_2(A2, Rs)}; +opt_remove_2({op,L,'orelse',A1,A2}, Rs) -> + {op,L,'orelse',opt_remove_2(A1, Rs),A2}; +opt_remove_2({call,Line,{remote,_,{atom,_,erlang},{atom,_,is_record}}, + [{var,_,V},{atom,_,Tag},{integer,_,Sz}]}=A, Rs) -> + case orddict:find(V, Rs) of + {ok,{remove,Tag,Sz}} -> + {atom,Line,true}; + _ -> + A + end; +opt_remove_2({call,Line,{atom,_,is_record}, + [{var,_,V},{atom,_,Tag},{integer,_,Sz}]}=A, Rs) -> + case orddict:find(V, Rs) of + {ok,{remove,Tag,Sz}} -> + {atom,Line,true}; + _ -> + A + end; +opt_remove_2(A, _) -> A. + neg_line(L) -> erl_parse:set_line(L, fun(Line) -> -abs(Line) end). -- cgit v1.2.3 From 7ac0808979534a94617c3391503c961d1ef72755 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 12 Mar 2010 09:39:23 +0100 Subject: Evaluate element/2 at compile-time using type information The erl_expand_records compiler pass translates the following code: h(X) when X#r1.a =:= 1 -> ok. to (essentially): h({r1,V1,V2}=X) when element(2, X) =:= 1 -> ok. Since the guard can only be executed when the pattern matching has succeeded, we know that the second element in the tuple X must have been bound to V2. Thus we can eliminate the call to element/2 like this: h({r1,V1,V2}=X) when V1 =:= 1 -> ok. --- lib/compiler/src/sys_core_fold.erl | 29 ++++++++++++++++------------- lib/stdlib/test/qlc_SUITE.erl | 4 +++- 2 files changed, 19 insertions(+), 14 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/sys_core_fold.erl b/lib/compiler/src/sys_core_fold.erl index 6202f07479..3e572d4b27 100644 --- a/lib/compiler/src/sys_core_fold.erl +++ b/lib/compiler/src/sys_core_fold.erl @@ -1194,19 +1194,22 @@ eval_element(Call, #c_literal{val=Pos}, #c_tuple{es=Es}, _Types) when is_integer true -> eval_failure(Call, badarg) end; -%% eval_element(Call, #c_literal{val=Pos}, #c_var{name=V}, Types) -%% when is_integer(Pos) -> -%% case orddict:find(V, Types#sub.t) of -%% {ok,#c_tuple{es=Elements}} -> -%% if -%% 1 =< Pos, Pos =< length(Elements) -> -%% lists:nth(Pos, Elements); -%% true -> -%% eval_failure(Call, badarg) -%% end; -%% error -> -%% Call -%% end; +eval_element(Call, #c_literal{val=Pos}, #c_var{name=V}, Types) + when is_integer(Pos) -> + case orddict:find(V, Types#sub.t) of + {ok,#c_tuple{es=Elements}} -> + if + 1 =< Pos, Pos =< length(Elements) -> + case lists:nth(Pos, Elements) of + #c_alias{var=Alias} -> Alias; + Res -> Res + end; + true -> + eval_failure(Call, badarg) + end; + error -> + Call + end; eval_element(Call, Pos, Tuple, _Types) -> case is_not_integer(Pos) orelse is_not_tuple(Tuple) of true -> diff --git a/lib/stdlib/test/qlc_SUITE.erl b/lib/stdlib/test/qlc_SUITE.erl index aa12ed57da..e21de8770a 100644 --- a/lib/stdlib/test/qlc_SUITE.erl +++ b/lib/stdlib/test/qlc_SUITE.erl @@ -3184,7 +3184,9 @@ lookup2(Config) when is_list(Config) -> [] = qlc:e(Q), false = lookup_keys(Q) end, [{1,b},{2,3}])">>, - {warnings,[{{3,48},qlc,nomatch_filter}]}}, + {warnings,[{2,sys_core_fold,nomatch_guard}, + {3,qlc,nomatch_filter}, + {3,sys_core_fold,{eval_failure,badarg}}]}}, <<"etsc(fun(E) -> Q = qlc:q([X || {X} <- ets:table(E), element(1,{X}) =:= 1]), -- cgit v1.2.3 From 470c91d43eae54f63661645acbce4b92d73287cc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 12 Mar 2010 09:42:40 +0100 Subject: Evaluate is_record/3 at compile-time using type information --- lib/compiler/src/sys_core_fold.erl | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'lib') diff --git a/lib/compiler/src/sys_core_fold.erl b/lib/compiler/src/sys_core_fold.erl index 3e572d4b27..96015fbe58 100644 --- a/lib/compiler/src/sys_core_fold.erl +++ b/lib/compiler/src/sys_core_fold.erl @@ -1038,6 +1038,8 @@ fold_non_lit_args(Call, lists, append, [Arg1,Arg2], _) -> eval_append(Call, Arg1, Arg2); fold_non_lit_args(Call, erlang, setelement, [Arg1,Arg2,Arg3], _) -> eval_setelement(Call, Arg1, Arg2, Arg3); +fold_non_lit_args(Call, erlang, is_record, [Arg1,Arg2,Arg3], Sub) -> + eval_is_record(Call, Arg1, Arg2, Arg3, Sub); fold_non_lit_args(Call, erlang, N, Args, Sub) -> NumArgs = length(Args), case erl_internal:comp_op(N, NumArgs) of @@ -1218,6 +1220,20 @@ eval_element(Call, Pos, Tuple, _Types) -> Call end. +%% eval_is_record(Call, Var, Tag, Size, Types) -> Val. +%% Evaluates is_record/3 using type information. +%% +eval_is_record(Call, #c_var{name=V}, #c_literal{val=NeededTag}=Lit, + #c_literal{val=Size}, Types) -> + case orddict:find(V, Types#sub.t) of + {ok,#c_tuple{es=[#c_literal{val=Tag}|_]=Es}} -> + Lit#c_literal{val=Tag =:= NeededTag andalso + length(Es) =:= Size}; + _ -> + Call + end; +eval_is_record(Call, _, _, _, _) -> Call. + %% is_not_integer(Core) -> true | false. %% Returns true if Core is definitely not an integer. -- cgit v1.2.3 From e96f49fbba499b56026735a302fbfbdf7524db66 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 12 Mar 2010 10:42:45 +0100 Subject: beam_dead: Combine is_eq_exact instructions into select_val instructions Combine a sequence of chained is_eq_exact instructions into a select_val instruction. --- lib/compiler/src/beam_dead.erl | 48 +++++++++++++++++++++++++++++++++++++----- 1 file changed, 43 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_dead.erl b/lib/compiler/src/beam_dead.erl index 7b4cd814a2..e690d1b96b 100644 --- a/lib/compiler/src/beam_dead.erl +++ b/lib/compiler/src/beam_dead.erl @@ -281,12 +281,12 @@ forward([{test,is_eq_exact,_,[Dst,Src]}=I,{move,Src,Dst}|Is], D, Lc, Acc) -> forward([I|Is], D, Lc, Acc); forward([{test,is_nil,_,[Dst]}=I,{move,nil,Dst}|Is], D, Lc, Acc) -> forward([I|Is], D, Lc, Acc); -forward([{test,is_eq_exact,_,[_,{atom,_}]}=I|Is], D, Lc, [{label,_}|_]=Acc) -> +forward([{test,is_eq_exact,_,_}=I|Is], D, Lc, Acc) -> case Is of [{label,_}|_] -> forward(Is, D, Lc, [I|Acc]); _ -> forward(Is, D, Lc+1, [{label,Lc},I|Acc]) end; -forward([{test,is_ne_exact,_,[_,{atom,_}]}=I|Is], D, Lc, [{label,_}|_]=Acc) -> +forward([{test,is_ne_exact,_,_}=I|Is], D, Lc, Acc) -> case Is of [{label,_}|_] -> forward(Is, D, Lc, [I|Acc]); _ -> forward(Is, D, Lc+1, [{label,Lc},I|Acc]) @@ -371,10 +371,10 @@ backward([{test,bs_start_match2,{f,To0},Live,[Src|_]=Info,Dst}|Is], D, Acc) -> To = shortcut_bs_start_match(To0, Src, D), I = {test,bs_start_match2,{f,To},Live,Info,Dst}, backward(Is, D, [I|Acc]); -backward([{test,is_eq_exact=Op,{f,To0},[Reg,{atom,Val}]=Ops}|Is], D, Acc) -> +backward([{test,is_eq_exact,{f,To0},[Reg,{atom,Val}]=Ops}|Is], D, Acc) -> To1 = shortcut_bs_test(To0, Is, D), To = shortcut_fail_label(To1, Reg, Val, D), - I = {test,Op,{f,To},Ops}, + I = combine_eqs(To, Ops, D, Acc), backward(Is, D, [I|Acc]); backward([{test,Op,{f,To0},Ops0}|Is], D, Acc) -> To1 = shortcut_bs_test(To0, Is, D), @@ -394,7 +394,10 @@ backward([{test,Op,{f,To0},Ops0}|Is], D, Acc) -> _Code -> To2 end, - I = {test,Op,{f,To},Ops0}, + I = case Op of + is_eq_exact -> combine_eqs(To, Ops0, D, Acc); + _ -> {test,Op,{f,To},Ops0} + end, backward(Is, D, [I|Acc]); backward([{test,Op,{f,To0},Live,Ops0,Dst}|Is], D, Acc) -> To1 = shortcut_bs_test(To0, Is, D), @@ -519,6 +522,41 @@ bif_to_test(Name, Args, Fail) -> 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, [{label,L1}|_]) + when Type =:= atom; Type =:= integer -> + case beam_utils:code_at(To, D) of + [{test,is_eq_exact,{f,F2},[Reg,{Type,_}=Lit2]}, + {label,L2}|_] when Lit1 =/= Lit2 -> + {select_val,Reg,{f,F2},{list,[Lit1,{f,L1},Lit2,{f,L2}]}}; + [{select_val,Reg,{f,F2},{list,[{Type,_}|_]=List0}}|_] -> + List = remove_from_list(Lit1, List0), + {select_val,Reg,{f,F2},{list,[Lit1,{f,L1}|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(_, []) -> []. %% shortcut_bs_test(TargetLabel, [Instruction], D) -> TargetLabel' %% Try to shortcut the failure label for a bit syntax matching. -- cgit v1.2.3 From 00471858a9be8df38e6c3abde159614feabb8262 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 12 Mar 2010 10:43:36 +0100 Subject: beam_peep: Remove optimization already done by beam_dead --- lib/compiler/src/beam_peep.erl | 48 ++---------------------------------------- 1 file changed, 2 insertions(+), 46 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_peep.erl b/lib/compiler/src/beam_peep.erl index d03ac4b1f4..a18ad72abf 100644 --- a/lib/compiler/src/beam_peep.erl +++ b/lib/compiler/src/beam_peep.erl @@ -64,22 +64,7 @@ function({function,Name,Arity,CLabel,Is0}) -> %% InEncoding =:= latin1, OutEncoding =:= unicode; %% InEncoding =:= latin1, OutEncoding =:= utf8 -> %% -%% (2) Code like -%% -%% is_ne_exact Fail Reg Literal1 -%% is_ne_exact Fail Reg Literal2 -%% is_ne_exact Fail Reg Literal3 -%% is_eq_exact UltimateFail Reg Literal4 -%% Fail: .... -%% -%% can be rewritten to -%% -%% select_val Reg UltimateFail [ Literal1 Fail -%% Literal2 Fail -%% Literal3 Fail -%% Literal4 Fail ] -%% -%% (3) A select_val/4 instruction that only verifies that +%% (2) A select_val/4 instruction that only verifies that %% its argument is either 'true' or 'false' can be %% be replaced with an is_boolean/2 instruction. That is: %% @@ -132,7 +117,7 @@ peep([{test,Op,_,Ops}=I|Is], SeenTests0, Acc) -> false -> %% Remember that we have seen this test. SeenTests = gb_sets:insert(Test, SeenTests0), - make_select_val(I, Is, SeenTests, Acc) + peep(Is, SeenTests, [I|Acc]) end end; peep([{select_val,Src,Fail, @@ -151,33 +136,6 @@ peep([I|Is], _, Acc) -> peep(Is, gb_sets:empty(), [I|Acc]); peep([], _, Acc) -> reverse(Acc). -make_select_val({test,is_ne_exact,{f,Fail},[Val,Lit]}=I0, - Is0, SeenTests, Acc) -> - try - Type = case Lit of - {atom,_} -> atom; - {integer,_} -> integer; - _ -> throw(impossible) - end, - {I,Is} = make_select_val_1(Is0, Fail, Val, Type, [Lit,{f,Fail}]), - peep([I|Is], SeenTests, Acc) - catch - impossible -> - peep(Is0, SeenTests, [I0|Acc]) - end; -make_select_val(I, Is, SeenTests, Acc) -> - peep(Is, SeenTests, [I|Acc]). - -make_select_val_1([{test,is_ne_exact,{f,Fail},[Val,{Type,_}=Lit]}|Is], - Fail, Val, Type, Acc) -> - make_select_val_1(Is, Fail, Val, Type, [Lit,{f,Fail}|Acc]); -make_select_val_1([{test,is_eq_exact,{f,UltimateFail},[Val,{Type,_}=Lit]} | - [{label,Fail}|_]=Is], Fail, Val, Type, Acc) -> - Choices = [Lit,{f,Fail}|Acc], - I = {select_val,Val,{f,UltimateFail},{list,Choices}}, - {I,Is}; -make_select_val_1(_Is, _Fail, _Val, _Type, _Acc) -> throw(impossible). - kill_seen(Dst, Seen0) -> gb_sets:from_ordset(kill_seen_1(gb_sets:to_list(Seen0), Dst)). @@ -187,5 +145,3 @@ kill_seen_1([{_,Ops}=Test|T], Dst) -> false -> [Test|kill_seen_1(T, Dst)] end; kill_seen_1([], _) -> []. - - -- cgit v1.2.3