Add beam_ssa_dead.erl

Add beam_ssa_dead to perform the main optimizations done
by beam_dead:

* Shortcut branches that jump to another block with a branch.
If it can be seen that the second branch will always branch
to a specific block, replace the target of the first branch.

* Combined nested sequences of '=:=' tests and switch
instructions operating on the same variable to a single switch.

Diffing the compiler output, it seems that beam_ssa_dead finds
many more opportunities for optimizations than beam_dead,
although it does not find all opportunities that beam_dead does.
In total, beam_ssa_dead is such improvement over beam_dead that
there is no reason to keep beam_dead as well as beam_ssa_dead.

Note that beam_ssa_dead does not attempt to optimize away
redundant bs_context_binary instructions, because that instruction
will be superseded by new instructions in the near future.

3 files changed, 195 insertions, 5 deletions

diff --git a/lib/compiler/test/beam_ssa_SUITE.erl b/lib/compiler/test/beam_ssa_SUITE.erl
index 0356c99c5a..5536abbdde 100644
--- a/lib/compiler/test/beam_ssa_SUITE.erl
+++ b/lib/compiler/test/beam_ssa_SUITE.erl
@@ -21,7 +21,8 @@
 
 -export([all/0,suite/0,groups/0,init_per_suite/1,end_per_suite/1,
 	 init_per_group/2,end_per_group/2,
-         calls/1,tuple_matching/1,recv/1,maps/1]).
+         calls/1,tuple_matching/1,recv/1,maps/1,
+         cover_ssa_dead/1,combine_sw/1]).
 
 suite() -> [{ct_hooks,[ts_install_cth]}].
 
@@ -33,7 +34,9 @@ groups() ->
       [tuple_matching,
        calls,
        recv,
-       maps
+       maps,
+       cover_ssa_dead,
+       combine_sw
       ]}].
 
 init_per_suite(Config) ->
@@ -286,5 +289,183 @@ maps_1(K) ->
     #{K:=V} = #{},
     V.
 
+-record(wx_ref, {type=any_type,ref=any_ref}).
+
+cover_ssa_dead(_Config) ->
+    str = format_str(str, escapable, [], true),
+    [iolist,str] = format_str(str, escapable, iolist, true),
+    bad = format_str(str, not_escapable, [], true),
+    bad = format_str(str, not_escapable, iolist, true),
+    bad = format_str(str, escapable, [], false),
+    bad = format_str(str, escapable, [], bad),
+
+    DefWxRef = #wx_ref{},
+    {DefWxRef,77,9999,[]} = contains(#wx_ref{}, 77, 9999),
+    {DefWxRef,77.0,9999,[]} = contains(#wx_ref{}, 77.0, 9999),
+    {DefWxRef,77,9999.0,[]} = contains(#wx_ref{}, 77, 9999.0),
+    {DefWxRef,77.0,9999.0,[]} = contains(#wx_ref{}, 77.0, 9999.0),
+    {any_type,any_ref,42,43,[option]} = contains(#wx_ref{}, {42,43}, [option]),
+    {any_type,any_ref,42,43,[]} = contains(#wx_ref{}, {42,43}, []),
+    {any_type,any_ref,42.0,43,[]} = contains(#wx_ref{}, {42.0,43}, []),
+    {any_type,any_ref,42,43.0,[]} = contains(#wx_ref{}, {42,43.0}, []),
+    {any_type,any_ref,42.0,43.0,[]} = contains(#wx_ref{}, {42.0,43.0}, []),
+
+    nope = conv_alub(false, '=:='),
+    ok = conv_alub(true, '=:='),
+    ok = conv_alub(true, none),
+    error = conv_alub(false, none),
+
+    {false,false} = eval_alu(false, false, false),
+    {true,false}  = eval_alu(false, false, true),
+    {false,true}  = eval_alu(false, true, false),
+    {false,false} = eval_alu(false, true, true),
+    {false,true}  = eval_alu(true, false, false),
+    {false,false} = eval_alu(true, false, true),
+    {true,true}   = eval_alu(true, true, false),
+    {false,true}  = eval_alu(true, true, true),
+
+    100.0 = percentage(1.0, 0.0),
+    100.0 = percentage(1, 0),
+    0.0 = percentage(0, 0),
+    0.0 = percentage(0.0, 0.0),
+    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
+        IoStr when Escapable, EscChars, IoList == [] ->
+            id(IoStr);
+        IoStr when Escapable, EscChars ->
+            [IoList,id(IoStr)];
+        _ ->
+            bad
+    end.
+
+contains(This, X, Y) when is_record(This, wx_ref), is_number(X), is_number(Y) ->
+    {This,X,Y,[]};
+contains(#wx_ref{type=ThisT,ref=ThisRef}, {CX,CY}, Options)
+  when is_number(CX), is_number(CY), is_list(Options) ->
+    {ThisT,ThisRef,CX,CY,Options}.
+
+conv_alub(HasDst, CmpOp) ->
+    case (not HasDst) andalso CmpOp =/= none of
+        true -> nope;
+        false ->
+            case HasDst of
+                false -> error;
+                true -> ok
+            end
+    end.
+
+eval_alu(Sign1, Sign2, N) ->
+    V = (Sign1 andalso Sign2 andalso (not N))
+        or ((not Sign1) andalso (not Sign2) andalso N),
+    C = (Sign1 andalso Sign2)
+          or ((not N) andalso (Sign1 orelse Sign2)),
+    {V,C}.
+
+percentage(Divident, Divisor) ->
+    if Divisor == 0 andalso Divident /= 0 ->
+            100.0;
+       Divisor == 0 ->
+            0.0;
+       true ->
+            Divident / Divisor * 100
+    end.
+
+combine_sw(_Config) ->
+    [a] = do_comb_sw_1(a),
+    [b,b] = do_comb_sw_1(b),
+    [c] = do_comb_sw_1(c),
+    [c] = do_comb_sw_1(c),
+    [] = do_comb_sw_1(z),
+
+    [a] = do_comb_sw_2(a),
+    [b2,b1] = do_comb_sw_2(b),
+    [c] = do_comb_sw_2(c),
+    [c] = do_comb_sw_2(c),
+    [] = do_comb_sw_2(z),
+
+    ok.
+
+do_comb_sw_1(X) ->
+    put(?MODULE, []),
+    if
+        X == a; X == b ->
+            put(?MODULE, [X|get(?MODULE)]);
+        true ->
+            ok
+    end,
+    if
+        X == b; X == c ->
+            put(?MODULE, [X|get(?MODULE)]);
+        true ->
+            ok
+    end,
+    erase(?MODULE).
+
+do_comb_sw_2(X) ->
+    put(?MODULE, []),
+    case X of
+        a ->
+            put(?MODULE, [a|get(?MODULE)]);
+        b ->
+            put(?MODULE, [b1|get(?MODULE)]);
+        _ ->
+            ok
+    end,
+    case X of
+        b ->
+            put(?MODULE, [b2|get(?MODULE)]);
+        c ->
+            put(?MODULE, [c|get(?MODULE)]);
+        _ ->
+            ok
+    end,
+    erase(?MODULE).
+
 %% The identity function.
 id(I) -> I.
diff --git a/lib/compiler/test/core_fold_SUITE.erl b/lib/compiler/test/core_fold_SUITE.erl
index 68bc5c6e2f..3fca1434ae 100644
--- a/lib/compiler/test/core_fold_SUITE.erl
+++ b/lib/compiler/test/core_fold_SUITE.erl
@@ -212,9 +212,14 @@ bifs(Config) when is_list(Config) ->
     {ok,#{K:=V}} = id(list_to_tuple([ok,#{K=>V}])),
     ok.
 
--define(CMP_SAME(A0, B), (fun(A) -> true = A == B, false = A /= B end)(id(A0))).
--define(CMP_DIFF(A0, B), (fun(A) -> false = A == B, true = A /= B end)(id(A0))).
-	       
+-define(CMP_SAME0(A0, B), (fun(A) -> true = A == B, false = A /= B end)(id(A0))).
+-define(CMP_SAME1(A0, B), (fun(A) -> false = A /= B, true = A == B end)(id(A0))).
+-define(CMP_SAME(A0, B), (true = ?CMP_SAME0(A0, B) =:= not ?CMP_SAME1(A0, B))).
+
+-define(CMP_DIFF0(A0, B), (fun(A) -> false = A == B, true = A /= B end)(id(A0))).
+-define(CMP_DIFF1(A0, B), (fun(A) -> true = A /= B, false = A == B end)(id(A0))).
+-define(CMP_DIFF(A0, B), (true = ?CMP_DIFF0(A0, B) =:= not ?CMP_DIFF1(A0, B))).
+
 eq(Config) when is_list(Config) ->
     ?CMP_SAME([a,b,c], [a,b,c]),
     ?CMP_SAME([42.0], [42.0]),
diff --git a/lib/compiler/test/match_SUITE.erl b/lib/compiler/test/match_SUITE.erl
index 46b543728d..229c3093d7 100644
--- a/lib/compiler/test/match_SUITE.erl
+++ b/lib/compiler/test/match_SUITE.erl
@@ -446,6 +446,7 @@ letify_guard(A, B) ->
 selectify(Config) when is_list(Config) ->
     integer = sel_different_types({r,42}),
     atom = sel_different_types({r,forty_two}),
+    float = sel_different_types({r,100.0}),
     none = sel_different_types({r,18}),
     {'EXIT',_} = (catch sel_different_types([a,b,c])),
 
@@ -456,12 +457,15 @@ selectify(Config) when is_list(Config) ->
     integer42 = sel_same_value2(42),
     integer43 = sel_same_value2(43),
     error = sel_same_value2(44),
+
     ok.
 
 sel_different_types({r,_}=T) when element(2, T) =:= forty_two ->
     atom;
 sel_different_types({r,_}=T) when element(2, T) =:= 42 ->
     integer;
+sel_different_types({r,_}=T) when element(2, T) =:= 100.0 ->
+    float;
 sel_different_types({r,_}) ->
     none.