beam_ssa_type: Use types from some 'lists' functions

This commit lets the compiler know about the return
type of some of the functions in the `lists` module.
Knowing about the return will allow the compiler to emit
fewer type test instructions, and also fewer instructions
for throwing `case_clause` or `badmatch` exceptions, thus
producing slightly faster and more compact code.

This change makes the `lists` module a part of the language, but it
could be argued that it already is because several functions
(e.g. `member/2` and `keymember/3`) are implemented in as BIFs in the
runtime system. Therefore, a user cannot simply change the
`lists` module and expect everything to continue working as before.

The compiler will now know the return types for the following
functions:

    all/2
    any/2
    keymember/3
    member/2
    prefix/2
    suffix/2

    dropwhile/2
    duplicate/2
    filter/2
    flatten/1
    map/2
    mapfoldl/3
    mapfoldr/3
    partition/2
    reverse/1
    sort/1
    splitwith/1
    takewhile/1
    unzip/1
    usort/1
    zip/2
    zipwith/3

1 files changed, 67 insertions, 0 deletions

diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl
index 5fbb679c6f..ce4e43f619 100644
--- a/lib/compiler/src/beam_ssa_type.erl
+++ b/lib/compiler/src/beam_ssa_type.erl
@@ -873,6 +873,9 @@ type(call, [#b_remote{mod=#b_literal{val=Mod},
             end;
         {erlang,'--',[_,_]} ->
             list;
+        {lists,F,Args} ->
+            Types = get_types(Args, Ts),
+            lists_function_type(F, Types);
         {math,_,_} ->
             case is_math_bif(Name, length(Args)) of
                 false -> any;
@@ -964,6 +967,70 @@ arith_op_type(Args, Ts) ->
              (_, _) -> none
           end, unknown, Types).
 
+lists_function_type(F, Types) ->
+    case {F,Types} of
+        %% Functions that return booleans.
+        {all,[_,_]} ->
+            t_boolean();
+        {any,[_,_]} ->
+            t_boolean();
+        {keymember,[_,_,_]} ->
+            t_boolean();
+        {member,[_,_]} ->
+            t_boolean();
+        {prefix,[_,_]} ->
+            t_boolean();
+        {suffix,[_,_]} ->
+            t_boolean();
+
+        %% Functions that return lists.
+        {dropwhile,[_,_]} ->
+            list;
+        {duplicate,[_,_]} ->
+            list;
+        {filter,[_,_]} ->
+            list;
+        {flatten,[_]} ->
+            list;
+        {map,[_Fun,List]} ->
+            same_length_type(List);
+        {MapFold,[_Fun,_Acc,List]} when MapFold =:= mapfoldl;
+                                        MapFold =:= mapfoldr ->
+            #t_tuple{size=2,exact=true,
+                     elements=#{1=>same_length_type(List)}};
+        {partition,[_,_]} ->
+            t_two_tuple(list, list);
+        {reverse,[List]} ->
+            same_length_type(List);
+        {sort,[List]} ->
+            same_length_type(List);
+        {splitwith,[_,_]} ->
+            t_two_tuple(list, list);
+        {takewhile,[_,_]} ->
+            list;
+        {unzip,[List]} ->
+            ListType = same_length_type(List),
+            t_two_tuple(ListType, ListType);
+        {usort,[List]} ->
+            same_length_type(List);
+        {zip,[_,_]} ->
+            list;
+        {zipwith,[_,_,_]} ->
+            list;
+        {_,_} ->
+            any
+    end.
+
+%% For a lists function that return a list of the same
+%% length as the input list, return the type of the list.
+same_length_type(cons) -> cons;
+same_length_type(nil) -> nil;
+same_length_type(_) -> list.
+
+t_two_tuple(Type1, Type2) ->
+    #t_tuple{size=2,exact=true,
+             elements=#{1=>Type1,2=>Type2}}.
+
 %% will_succeed(TestOperation, Type) -> yes|no|maybe.
 %%  Test whether TestOperation applied to an argument of type Type
 %%  will succeed.  Return yes, no, or maybe.