Improve optimization of redundant tests

The `beam_ssa_dead` pass is supposed to eliminate tests that are
determined to be redundant based on the outcome of a previous test.

For example, in the following example that repeats a guard test,
the second clause can never be executed:

    foo(A) when A >= 42 -> one;
    foo(A) when A >= 42 -> two;
    foo(_) -> three.

`beam_ssa_dead` should have eliminated the second clause, but
didn't:

      {test,is_ge,{f,5},[{x,0},{integer,42}]}.
      {move,{atom,one},{x,0}}.
      return.
    {label,5}.
      {test,is_ge,{f,6},[{x,0},{integer,42}]}.
      {move,{atom,two},{x,0}}.
      return.
    {label,6}.
      {move,{atom,three},{x,0}}.
      return.

Correct the optimization of four different combinations of relational
operations that were too conservate. To ensure the correctness of the
optimization, also add an exahaustive test of all combinations of
relational operations with one variable and one literal. (Also remove
the weak and now redundant coverage tests in `beam_ssa_SUITE`.) With
this correction, the following code will be generated for the example:

      {test,is_ge,{f,5},[{x,0},{integer,42}]}.
      {move,{atom,one},{x,0}}.
      return.
    {label,5}.
      {move,{atom,three},{x,0}}.
      return.

Thanks to Dániel Szoboszlay (@dszoboszlay), whose talk at Code BEAM
STO 2019 made me aware of this missed opportunity for optimization.

3 files changed, 124 insertions, 47 deletions

diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl
index bb43a550ae..423bc88c3b 100644
--- a/lib/compiler/src/beam_ssa_dead.erl
+++ b/lib/compiler/src/beam_ssa_dead.erl
@@ -719,8 +719,8 @@ 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 -> 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;
@@ -740,9 +740,9 @@ 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 -> 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) ->
     if
diff --git a/lib/compiler/test/beam_ssa_SUITE.erl b/lib/compiler/test/beam_ssa_SUITE.erl
index 15cf9bcbf3..c1086276d0 100644
--- a/lib/compiler/test/beam_ssa_SUITE.erl
+++ b/lib/compiler/test/beam_ssa_SUITE.erl
@@ -344,48 +344,8 @@ cover_ssa_dead(_Config) ->
     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
diff --git a/lib/compiler/test/guard_SUITE.erl b/lib/compiler/test/guard_SUITE.erl
index ed0a56f064..f25d8a1a46 100644
--- a/lib/compiler/test/guard_SUITE.erl
+++ b/lib/compiler/test/guard_SUITE.erl
@@ -19,7 +19,7 @@
 %%
 -module(guard_SUITE).
 
--include_lib("common_test/include/ct.hrl").
+-include_lib("syntax_tools/include/merl.hrl").
 
 -export([all/0, suite/0,groups/0,init_per_suite/1, end_per_suite/1, 
 	 init_per_group/2,end_per_group/2,
@@ -31,7 +31,8 @@
 	 old_guard_tests/1,complex_guard/1,
 	 build_in_guard/1,gbif/1,
 	 t_is_boolean/1,is_function_2/1,
-	 tricky/1,rel_ops/1,rel_op_combinations/1,literal_type_tests/1,
+	 tricky/1,rel_ops/1,rel_op_combinations/1,
+         generated_combinations/1,literal_type_tests/1,
 	 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,
@@ -50,7 +51,7 @@ groups() ->
        more_xor_guards,build_in_guard,
        old_guard_tests,complex_guard,gbif,
        t_is_boolean,is_function_2,tricky,
-       rel_ops,rel_op_combinations,
+       rel_ops,rel_op_combinations,generated_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]}].
@@ -1577,6 +1578,122 @@ redundant_12(X) when X >= 50, X =< 80 -> 2*X;
 redundant_12(X) when X < 51 -> 5*X;
 redundant_12(_) -> none.
 
+generated_combinations(Config) ->
+    case ?MODULE of
+	guard_SUITE -> generated_combinations_1(Config);
+	_ -> {skip,"Enough to run this case once."}
+    end.
+
+%% Exhaustively test all combinations of relational operators
+%% to ensure the correctness of the optimizations in beam_ssa_dead.
+
+generated_combinations_1(Config) ->
+    Mod = ?FUNCTION_NAME,
+    RelOps = ['=:=','=/=','==','/=','<','=<','>=','>'],
+    Combinations0 = [{Op1,Op2} || Op1 <- RelOps, Op2 <- RelOps],
+    Combinations1 = gen_lit_combs(Combinations0),
+    Combinations2 = [{neq,Comb} ||
+                        {_Op1,_Lit1,Op2,_Lit2}=Comb <- Combinations1,
+                        Op2 =:= '=/=' orelse Op2 =:= '/='] ++ Combinations1,
+    Combinations = gen_func_names(Combinations2, 0),
+    Fs = gen_rel_op_functions(Combinations),
+    Tree = ?Q(["-module('@Mod@').",
+               "-compile([export_all,nowarn_export_all])."]) ++ Fs,
+    %%merl:print(Tree),
+    Opts = test_lib:opt_opts(?MODULE),
+    {ok,_Bin} = merl:compile_and_load(Tree, Opts),
+    test_combinations(Combinations, Mod).
+
+gen_lit_combs([{Op1,Op2}|T]) ->
+    [{Op1,7,Op2,6},
+     {Op1,7.0,Op2,6},
+     {Op1,7,Op2,6.0},
+     {Op1,7.0,Op2,6.0},
+
+     {Op1,7,Op2,7},
+     {Op1,7.0,Op2,7},
+     {Op1,7,Op2,7.0},
+     {Op1,7.0,Op2,7.0},
+
+     {Op1,6,Op2,7},
+     {Op1,6.0,Op2,7},
+     {Op1,6,Op2,7.0},
+     {Op1,6.0,Op2,7.0}|gen_lit_combs(T)];
+gen_lit_combs([]) -> [].
+
+gen_func_names([E|Es], I) ->
+    Name = list_to_atom("f" ++ integer_to_list(I)),
+    [{Name,E}|gen_func_names(Es, I+1)];
+gen_func_names([], _) -> [].
+
+gen_rel_op_functions([{Name,{neq,{Op1,Lit1,Op2,Lit2}}}|T]) ->
+    %% Note that in the translation to SSA, '=/=' will be
+    %% translated to '=:=' in a guard (with switched success
+    %% and failure labels). Therefore, to test the optimization,
+    %% we must use '=/=' (or '/=') in a body context.
+    %%
+    %% Here is an example of a generated function:
+    %%
+    %%     f160(A) when erlang:'>='(A, 7) ->
+    %%          one;
+    %%     f160(A) ->
+    %%          true = erlang:'/='(A, 7),
+    %%          two.
+    [?Q("'@Name@'(A) when erlang:'@Op1@'(A, _@Lit1@) -> one;
+        '@Name@'(A) -> true = erlang:'@Op2@'(A, _@Lit2@), two. ")|
+     gen_rel_op_functions(T)];
+gen_rel_op_functions([{Name,{Op1,Lit1,Op2,Lit2}}|T]) ->
+    %% Example of a generated function:
+    %%
+    %% f721(A) when erlang:'=<'(A, 7.0) -> one;
+    %% f721(A) when erlang:'<'(A, 6) -> two;
+    %% f721(_) -> three.
+    [?Q("'@Name@'(A) when erlang:'@Op1@'(A, _@Lit1@) -> one;
+        '@Name@'(A) when erlang:'@Op2@'(A, _@Lit2@) -> two;
+        '@Name@'(_) -> three.")|gen_rel_op_functions(T)];
+gen_rel_op_functions([]) -> [].
+
+test_combinations([{Name,E}|T], Mod) ->
+    try
+        test_combinations_1([5,6,7,8,9], E, fun Mod:Name/1),
+        test_combination(6.5, E, fun Mod:Name/1)
+    catch
+        error:Reason:Stk ->
+            io:format("~p: ~p\n", [Name,E]),
+            erlang:raise(error, Reason, Stk)
+    end,
+    test_combinations(T, Mod);
+test_combinations([], _Mod) -> ok.
+
+test_combinations_1([V|Vs], E, Fun) ->
+    test_combination(V, E, Fun),
+    test_combination(float(V), E, Fun),
+    test_combinations_1(Vs, E, Fun);
+test_combinations_1([], _, _) -> ok.
+
+test_combination(Val, {neq,Expr}, Fun) ->
+    Result = eval_combination_expr(Expr, Val),
+    Result = try
+                 Fun(Val)                       %Returns 'one' or 'two'.
+             catch
+                 error:{badmatch,_} ->
+                     three
+             end;
+test_combination(Val, Expr, Fun) ->
+    Result = eval_combination_expr(Expr, Val),
+    Result = Fun(Val).
+
+eval_combination_expr({Op1,Lit1,Op2,Lit2}, Val) ->
+    case erlang:Op1(Val, Lit1) of
+        true ->
+            one;
+        false ->
+            case erlang:Op2(Val, Lit2) of
+                true -> two;
+                false -> three
+            end
+    end.
+
 %% Test type tests on literal values. (From emulator test suites.)
 literal_type_tests(Config) when is_list(Config) ->
     case ?MODULE of