aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2014-12-31 11:11:57 +0100
committerBjörn Gustavsson <[email protected]>2015-03-09 09:59:37 +0100
commite914206e11b439a5794b7a8c3c527af395609ddd (patch)
tree7d790e2af9194479b42a753e453a00b92086ef93 /lib
parent4f365a9b80bab48c4478a6910624244f88637bcb (diff)
downloadotp-e914206e11b439a5794b7a8c3c527af395609ddd.tar.gz
otp-e914206e11b439a5794b7a8c3c527af395609ddd.tar.bz2
otp-e914206e11b439a5794b7a8c3c527af395609ddd.zip
sys_core_fold: Improve optimization of 'not'
Optimize away 'not' in sys_core_fold instead of in beam_block and beam_dead, as we can do a better job in sys_core_fold. I modified the test suite temporarily to never turn off Core Erlang modifications and looked at the coverage. With the new optimizations active in sys_core_fold, the code in beam_block and beam_dead did not find a single 'not' that it could optimize. That proves that the new optimization is at least as good as the old one. Manually, I could also verify that the new optimization would optimize some variations of 'not' that the old one would not handle.
Diffstat (limited to 'lib')
-rw-r--r--lib/compiler/src/beam_block.erl19
-rw-r--r--lib/compiler/src/beam_dead.erl16
-rw-r--r--lib/compiler/src/cerl.erl3
-rw-r--r--lib/compiler/src/sys_core_fold.erl124
-rw-r--r--lib/compiler/test/andor_SUITE.erl12
5 files changed, 133 insertions, 41 deletions
diff --git a/lib/compiler/src/beam_block.erl b/lib/compiler/src/beam_block.erl
index 92f09e400c..5216f39296 100644
--- a/lib/compiler/src/beam_block.erl
+++ b/lib/compiler/src/beam_block.erl
@@ -252,13 +252,6 @@ combine_alloc({_,Ns,Nh1,Init}, {_,nostack,Nh2,[]}) ->
%% opt([Instruction]) -> [Instruction]
%% Optimize the instruction stream inside a basic block.
-opt([{set,[Dst],As,{bif,Bif,Fail}}=I1,
- {set,[Dst],[Dst],{bif,'not',Fail}}=I2|Is]) ->
- %% Get rid of the 'not' if the operation can be inverted.
- case inverse_comp_op(Bif) of
- none -> [I1,I2|opt(Is)];
- RevBif -> [{set,[Dst],As,{bif,RevBif,Fail}}|opt(Is)]
- end;
opt([{set,[X],[X],move}|Is]) -> opt(Is);
opt([{set,_,_,{line,_}}=Line1,
{set,[D1],[{integer,Idx1},Reg],{bif,element,{f,0}}}=I1,
@@ -428,18 +421,6 @@ x_live([{x,N}|Rs], Regs) -> x_live(Rs, Regs bor (1 bsl N));
x_live([_|Rs], Regs) -> x_live(Rs, Regs);
x_live([], Regs) -> Regs.
-%% inverse_comp_op(Op) -> none|RevOp
-
-inverse_comp_op('=:=') -> '=/=';
-inverse_comp_op('=/=') -> '=:=';
-inverse_comp_op('==') -> '/=';
-inverse_comp_op('/=') -> '==';
-inverse_comp_op('>') -> '=<';
-inverse_comp_op('<') -> '>=';
-inverse_comp_op('>=') -> '<';
-inverse_comp_op('=<') -> '>';
-inverse_comp_op(_) -> none.
-
%%%
%%% Evaluation of constant bit fields.
%%%
diff --git a/lib/compiler/src/beam_dead.erl b/lib/compiler/src/beam_dead.erl
index 7cd07dc3be..7f28575a65 100644
--- a/lib/compiler/src/beam_dead.erl
+++ b/lib/compiler/src/beam_dead.erl
@@ -234,10 +234,8 @@ backward([{select,select_val,Reg,{f,Fail0},List0}|Is], D, Acc) ->
Fail = shortcut_bs_test(Fail1, Is, D),
Sel = {select,select_val,Reg,{f,Fail},List},
backward(Is, D, [Sel|Acc]);
-backward([{jump,{f,To0}},{move,Src0,Reg}|Is], D, Acc) ->
- To1 = shortcut_select_label(To0, Reg, Src0, D),
- {To,Src} = shortcut_boolean_label(To1, Reg, Src0, D),
- Move = {move,Src,Reg},
+backward([{jump,{f,To0}},{move,Src,Reg}=Move|Is], D, Acc) ->
+ To = shortcut_select_label(To0, Reg, Src, D),
Jump = {jump,{f,To}},
case beam_utils:is_killed_at(Reg, To, D) of
false -> backward([Move|Is], D, [Jump|Acc]);
@@ -330,16 +328,6 @@ shortcut_label(To0, D) ->
shortcut_select_label(To, Reg, Lit, D) ->
shortcut_rel_op(To, is_ne_exact, [Reg,Lit], D).
-shortcut_boolean_label(To0, Reg, {atom,Bool0}=Lit, D) when is_boolean(Bool0) ->
- case beam_utils:code_at(To0, D) of
- [{line,_},{bif,'not',_,[Reg],Reg},{jump,{f,To}}|_] ->
- Bool = {atom,not Bool0},
- {shortcut_select_label(To, Reg, Bool, D),Bool};
- _ ->
- {To0,Lit}
- end;
-shortcut_boolean_label(To, _, Bool, _) -> {To,Bool}.
-
%% Replace a comparison operator with a test instruction and a jump.
%% For example, if we have this code:
%%
diff --git a/lib/compiler/src/cerl.erl b/lib/compiler/src/cerl.erl
index 3d4b9ee0c6..8367a1e19e 100644
--- a/lib/compiler/src/cerl.erl
+++ b/lib/compiler/src/cerl.erl
@@ -138,7 +138,8 @@
]).
-export_type([c_binary/0, c_bitstr/0, c_call/0, c_clause/0, c_cons/0, c_fun/0,
- c_literal/0, c_map/0, c_map_pair/0, c_module/0, c_tuple/0,
+ c_let/0, c_literal/0, c_map/0, c_map_pair/0,
+ c_module/0, c_tuple/0,
c_values/0, c_var/0, cerl/0, var_name/0]).
-include("core_parse.hrl").
diff --git a/lib/compiler/src/sys_core_fold.erl b/lib/compiler/src/sys_core_fold.erl
index 68272689c2..dc996dc73f 100644
--- a/lib/compiler/src/sys_core_fold.erl
+++ b/lib/compiler/src/sys_core_fold.erl
@@ -1965,6 +1965,107 @@ letify(Bs, Body) ->
cerl:ann_c_let(Ann, [V], Val, B)
end, Body, Bs).
+%% opt_not_in_let(Let) -> Cerl
+%% Try to optimize away a 'not' operator in a 'let'.
+
+-spec opt_not_in_let(cerl:c_let()) -> cerl:cerl().
+
+opt_not_in_let(#c_let{vars=[_]=Vs0,arg=Arg0,body=Body0}=Let) ->
+ case opt_not_in_let(Vs0, Arg0, Body0) of
+ {[],#c_values{es=[]},Body} ->
+ Body;
+ {Vs,Arg,Body} ->
+ Let#c_let{vars=Vs,arg=Arg,body=Body}
+ end;
+opt_not_in_let(Let) -> Let.
+
+%% opt_not_in_let(Vs, Arg, Body) -> {Vs',Arg',Body'}
+%% Try to optimize away a 'not' operator in a 'let'.
+
+-spec opt_not_in_let([cerl:c_var()], cerl:cerl(), cerl:cerl()) ->
+ {[cerl:c_var()],cerl:cerl(),cerl:cerl()}.
+
+opt_not_in_let([#c_var{name=V}]=Vs0, Arg0, Body0) ->
+ case cerl:type(Body0) of
+ call ->
+ %% let <V> = Expr in not V ==>
+ %% let <> = <> in notExpr
+ case opt_not_in_let_1(V, Body0, Arg0) of
+ no ->
+ {Vs0,Arg0,Body0};
+ {yes,Body} ->
+ {[],#c_values{es=[]},Body}
+ end;
+ 'let' ->
+ %% let <V> = Expr in let <Var> = not V in Body ==>
+ %% let <Var> = notExpr in Body
+ %% V must not be used in Body.
+ LetArg = cerl:let_arg(Body0),
+ case opt_not_in_let_1(V, LetArg, Arg0) of
+ no ->
+ {Vs0,Arg0,Body0};
+ {yes,Arg} ->
+ LetBody = cerl:let_body(Body0),
+ case core_lib:is_var_used(V, LetBody) of
+ true ->
+ {Vs0,Arg0,Body0};
+ false ->
+ LetVars = cerl:let_vars(Body0),
+ {LetVars,Arg,LetBody}
+ end
+ end;
+ _ ->
+ {Vs0,Arg0,Body0}
+ end;
+opt_not_in_let(Vs, Arg, Body) ->
+ {Vs,Arg,Body}.
+
+opt_not_in_let_1(V, Call, Body) ->
+ case Call of
+ #c_call{module=#c_literal{val=erlang},
+ name=#c_literal{val='not'},
+ args=[#c_var{name=V}]} ->
+ opt_not_in_let_2(Body);
+ _ ->
+ no
+ end.
+
+opt_not_in_let_2(#c_case{clauses=Cs0}=Case) ->
+ Vars = make_vars([], 1),
+ Body = #c_call{module=#c_literal{val=erlang},
+ name=#c_literal{val='not'},
+ args=Vars},
+ Cs = [begin
+ Let = #c_let{vars=Vars,arg=B,body=Body},
+ C#c_clause{body=opt_not_in_let(Let)}
+ end || #c_clause{body=B}=C <- Cs0],
+ {yes,Case#c_case{clauses=Cs}};
+opt_not_in_let_2(#c_call{}=Call0) ->
+ invert_call(Call0);
+opt_not_in_let_2(_) -> no.
+
+invert_call(#c_call{module=#c_literal{val=erlang},
+ name=#c_literal{val=Name0},
+ args=[_,_]}=Call) ->
+ case inverse_rel_op(Name0) of
+ no -> no;
+ Name -> {yes,Call#c_call{name=#c_literal{val=Name}}}
+ end;
+invert_call(#c_call{}) -> no.
+
+%% inverse_rel_op(Op) -> no | RevOp
+
+inverse_rel_op('=:=') -> '=/=';
+inverse_rel_op('=/=') -> '=:=';
+inverse_rel_op('==') -> '/=';
+inverse_rel_op('/=') -> '==';
+inverse_rel_op('>') -> '=<';
+inverse_rel_op('<') -> '>=';
+inverse_rel_op('>=') -> '<';
+inverse_rel_op('=<') -> '>';
+inverse_rel_op(_) -> no.
+
+
%% opt_case_in_let(LetExpr) -> LetExpr'
opt_case_in_let(#c_let{vars=Vs,arg=Arg,body=B}=Let, Sub) ->
@@ -2272,19 +2373,28 @@ is_failing_clause(#c_clause{body=B}) ->
%% Optimize a let construct that does not contain any lets in
%% in its argument.
-opt_simple_let(#c_let{arg=Arg0}=Let, Ctxt, Sub0) ->
- Arg = body(Arg0, value, Sub0), %This is a body
+opt_simple_let(Let0, Ctxt, Sub) ->
+ case opt_not_in_let(Let0) of
+ #c_let{}=Let ->
+ opt_simple_let_0(Let, Ctxt, Sub);
+ Expr ->
+ expr(Expr, Ctxt, Sub)
+ end.
+
+opt_simple_let_0(#c_let{arg=Arg0}=Let, Ctxt, Sub) ->
+ Arg = body(Arg0, value, Sub), %This is a body
case will_fail(Arg) of
true -> Arg;
- false -> opt_simple_let_1(Let, Arg, Ctxt, Sub0)
+ false -> opt_simple_let_1(Let, Arg, Ctxt, Sub)
end.
opt_simple_let_1(#c_let{vars=Vs0,body=B0}=Let, Arg0, Ctxt, Sub0) ->
%% Optimise let and add new substitutions.
- {Vs,Args,Sub1} = let_substs(Vs0, Arg0, Sub0),
- BodySub = update_let_types(Vs, Args, Sub1),
- B = body(B0, Ctxt, BodySub),
- Arg = core_lib:make_values(Args),
+ {Vs1,Args,Sub1} = let_substs(Vs0, Arg0, Sub0),
+ BodySub = update_let_types(Vs1, Args, Sub1),
+ B1 = body(B0, Ctxt, BodySub),
+ Arg1 = core_lib:make_values(Args),
+ {Vs,Arg,B} = opt_not_in_let(Vs1, Arg1, B1),
opt_simple_let_2(Let, Vs, Arg, B, B0, Ctxt, Sub1).
opt_simple_let_2(Let0, Vs0, Arg0, Body, PrevBody, Ctxt, Sub) ->
diff --git a/lib/compiler/test/andor_SUITE.erl b/lib/compiler/test/andor_SUITE.erl
index 3199440d84..4d7f444c4f 100644
--- a/lib/compiler/test/andor_SUITE.erl
+++ b/lib/compiler/test/andor_SUITE.erl
@@ -370,6 +370,11 @@ combined(Config) when is_list(Config) ->
?line true = ?COMB(false, blurf, true),
?line true = ?COMB(true, true, blurf),
+ false = simple_comb(false, false),
+ false = simple_comb(false, true),
+ false = simple_comb(true, false),
+ true = simple_comb(true, true),
+
ok.
-undef(COMB).
@@ -396,6 +401,13 @@ comb(A, B, C) ->
end,
id(Res).
+simple_comb(A, B) ->
+ %% Use Res twice, to ensure that a careless optimization of 'not'
+ %% doesn't leave Res as a free variable.
+ Res = A andalso B,
+ _ = id(not Res),
+ Res.
+
%% Test that a boolean expression in a case expression is properly
%% optimized (in particular, that the error behaviour is correct).
in_case(Config) when is_list(Config) ->