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.

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) ->