Introduce subtraction of types

Introduce subtraction of types to allow some redundant tests to be
eliminated.

Consider this function:

    foo(L) when is_list(L) ->
        case L of
            [_|_] -> non_empty;
            [] -> empty
        end.

After entering the body of the function, L is known to be either
a cons cell or nil (otherwise the is_list/1 guard would have failed).

If the L is not a cons cell, it must be nil. Therefore, the test
for nil in the second clause of the case can be eliminated.

Here is the SSA code with some additonal comments for the function
before the optimization:

    function t:foo(_0) {
    0:
      @ssa_bool = bif:is_list _0
      br @ssa_bool, label 4, label 3

    4:
      %% _0 is now a list (cons or nil).

      @ssa_bool:8 = is_nonempty_list _0
      br @ssa_bool:8, label 9, label 7

    9:
      ret literal non_empty

    7:
      %% _0 is not a cons (or we wouldn't be here).
      %% Subtracting cons from the previously known type list
      %% gives that _0 must be nil.

      @ssa_bool:10 = bif:'=:=' _0, literal []
      br @ssa_bool:10, label 11, label 6

    11:
      ret literal empty

    6:
      _6 = put_tuple literal case_clause, _0

      %% t.erl:5
      @ssa_ret:12 = call remote (literal erlang):(literal error)/1, _6
      ret @ssa_ret:12

    3:
      _9 = put_list _0, literal []

      %% t.erl:4
      @ssa_ret:13 = call remote (literal erlang):(literal error)/2, literal function_clause, _9
      ret @ssa_ret:13
    }

Type subtraction gives us that _0 must be nil in block 7, allowing us to
remove the comparison of _0 with nil. The code for the function can be simplified
to:

    function t:foo(_0) {
    0:
      @ssa_bool = bif:is_list _0
      br @ssa_bool, label 4, label 3

    4:
      @ssa_bool:8 = is_nonempty_list _0
      br @ssa_bool:8, label 9, label 11

    9:
      ret literal non_empty

    11:
      ret literal empty

    3:
      _9 = put_list _0, literal []

      %% t.erl:4
      @ssa_ret:13 = call remote (literal erlang):(literal error)/2, literal function_clause, _9
      ret @ssa_ret:13
    }

1 files changed, 22 insertions, 2 deletions

diff --git a/lib/compiler/test/match_SUITE.erl b/lib/compiler/test/match_SUITE.erl
index 78276982eb..60ab969929 100644
--- a/lib/compiler/test/match_SUITE.erl
+++ b/lib/compiler/test/match_SUITE.erl
@@ -25,7 +25,7 @@
 	 match_in_call/1,untuplify/1,shortcut_boolean/1,letify_guard/1,
 	 selectify/1,deselectify/1,underscore/1,match_map/1,map_vars_used/1,
 	 coverage/1,grab_bag/1,literal_binary/1,
-         unary_op/1]).
+         unary_op/1,eq_types/1]).
 	 
 -include_lib("common_test/include/ct.hrl").
 
@@ -40,7 +40,7 @@ groups() ->
        match_in_call,untuplify,
        shortcut_boolean,letify_guard,selectify,deselectify,
        underscore,match_map,map_vars_used,coverage,
-       grab_bag,literal_binary,unary_op]}].
+       grab_bag,literal_binary,unary_op,eq_types]}].
 
 
 init_per_suite(Config) ->
@@ -870,5 +870,25 @@ unary_op_1(Vop@1) ->
             end
     end.
 
+eq_types(_Config) ->
+    Ref = make_ref(),
+    Ref = eq_types(Ref, any),
+    ok.
+
+eq_types(A, B) ->
+    %% {put_tuple2,{y,0},{list,[{x,0},{x,1}]}}.
+    Term0 = {A, B},
+    Term = id(Term0),
+
+    %% {test,is_eq_exact,{f,3},[{y,0},{x,0}]}.
+    %% Here beam_validator must infer that {x,0} has the
+    %% same type as {y,0}.
+    Term = Term0,
+
+    %% {get_tuple_element,{x,0},0,{x,0}}.
+    {Ref22,_} = Term,
+
+    Ref22.
+
 
 id(I) -> I.