From 547476f4d47c90b3d02314f5f1f327cdacf5e587 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sat, 9 Feb 2019 15:38:08 +0100 Subject: 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 --- lib/compiler/src/beam_ssa_type.erl | 67 +++++++++++++++++++++++++++++++++++++ lib/compiler/src/beam_validator.erl | 60 +++++++++++++++++++++++++++++++++ 2 files changed, 127 insertions(+) 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. diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 8ca90870c4..5175be3ad5 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -2502,6 +2502,8 @@ call_return_type_1(erlang, '--', 2, _Vst) -> list; call_return_type_1(erlang, F, A, _) -> erlang_mod_return_type(F, A); +call_return_type_1(lists, F, A, Vst) -> + lists_mod_return_type(F, A, Vst); call_return_type_1(math, F, A, _) -> math_mod_return_type(F, A); call_return_type_1(M, F, A, _) when is_atom(M), is_atom(F), is_integer(A), A >= 0 -> @@ -2540,6 +2542,64 @@ math_mod_return_type(fmod, 2) -> {float,[]}; math_mod_return_type(pi, 0) -> {float,[]}; math_mod_return_type(F, A) when is_atom(F), is_integer(A), A >= 0 -> term. +lists_mod_return_type(dropwhile, 2, _Vst) -> + list; +lists_mod_return_type(duplicate, 2, _Vst) -> + list; +lists_mod_return_type(filter, 2, _Vst) -> + list; +lists_mod_return_type(flatten, 2, _Vst) -> + list; +lists_mod_return_type(map, 2, Vst) -> + same_length_type({x,1}, Vst); +lists_mod_return_type(MF, 3, Vst) when MF =:= mapfoldl; MF =:= mapfoldr -> + ListType = same_length_type({x,2}, Vst), + {tuple,2,#{1=>ListType}}; +lists_mod_return_type(partition, 2, _Vst) -> + two_tuple(list, list); +lists_mod_return_type(reverse, 1, Vst) -> + same_length_type({x,0}, Vst); +lists_mod_return_type(seq, 2, _Vst) -> + list; +lists_mod_return_type(seq, 3, _Vst) -> + list; +lists_mod_return_type(sort, 1, Vst) -> + same_length_type({x,0}, Vst); +lists_mod_return_type(sort, 2, Vst) -> + same_length_type({x,1}, Vst); +lists_mod_return_type(splitwith, 2, _Vst) -> + two_tuple(list, list); +lists_mod_return_type(takewhile, 2, _Vst) -> + list; +lists_mod_return_type(unzip, 1, Vst) -> + ListType = same_length_type({x,0}, Vst), + two_tuple(ListType, ListType); +lists_mod_return_type(usort, 1, Vst) -> + same_length_type({x,0}, Vst); +lists_mod_return_type(usort, 2, Vst) -> + same_length_type({x,1}, Vst); +lists_mod_return_type(zip, 2, _Vst) -> + list; +lists_mod_return_type(zip3, 3, _Vst) -> + list; +lists_mod_return_type(zipwith, 3, _Vst) -> + list; +lists_mod_return_type(zipwith3, 4, _Vst) -> + list; +lists_mod_return_type(_, _, _) -> + term. + +two_tuple(Type1, Type2) -> + {tuple,2,#{1=>Type1,2=>Type2}}. + +same_length_type(Reg, Vst) -> + case get_term_type(Reg, Vst) of + {literal,[_|_]} -> cons; + cons -> cons; + nil -> nil; + _ -> list + end. + check_limit({x,X}) when is_integer(X), X < 1023 -> %% Note: x(1023) is reserved for use by the BEAM loader. ok; -- cgit v1.2.3