From 43a386436b817e8d93fea8f6ea719f9162192241 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Wed, 29 May 2019 15:30:51 +0200 Subject: beam_validator: Use integers as tuple element keys This simplifies a later migration to a unified type format, as the literal representation may differ between passes, so passing container types keyed by literals will fail. --- lib/compiler/src/beam_ssa_type.erl | 3 +-- lib/compiler/src/beam_validator.erl | 48 +++++++++++++++++++------------------ 2 files changed, 26 insertions(+), 25 deletions(-) diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 612277393e..da73dc26f7 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -177,10 +177,9 @@ validator_anno(#t_fun{}) -> any; validator_anno(#t_tuple{size=Size,exact=Exact,elements=Elements0}) -> Elements = maps:fold(fun(Index, Type0, Acc) -> - Key = beam_validator:type_anno(integer, Index), case validator_anno(Type0) of any -> Acc; - Type -> Acc#{Key=>Type} + Type -> Acc#{ Index => Type } end end, #{}, Elements0), beam_validator:type_anno(tuple, Size, Exact, Elements); diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 717ea17475..c5e3f6ac35 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -170,7 +170,7 @@ validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) -> number | term | tuple_in_progress | - {tuple, tuple_sz(), #{ literal() => type() }} | + {tuple, tuple_sz(), #{ pos_integer() => type() }} | literal(). -type tag() :: initialized | @@ -448,7 +448,7 @@ valfun_1({put_tuple2,Dst,{list,Elements}}, Vst0) -> Vst = eat_heap(Size+1, Vst0), {Es,_} = foldl(fun(Val, {Es0, Index}) -> Type = get_term_type(Val, Vst0), - Es = set_element_type({integer,Index}, Type, Es0), + Es = set_element_type(Index, Type, Es0), {Es, Index + 1} end, {#{}, 1}, Elements), Type = {tuple,Size,Es}, @@ -467,12 +467,12 @@ valfun_1({put,Src}, Vst0) -> #st{puts_left=none} -> error(not_building_a_tuple); #st{puts_left={1,{Dst,Sz,Es0}}} -> - Es = Es0#{ {integer,Sz} => get_term_type(Src, Vst0) }, + Es = Es0#{ Sz => get_term_type(Src, Vst0) }, St = St0#st{puts_left=none}, create_term({tuple,Sz,Es}, put_tuple, [], Dst, Vst#vst{current=St}); #st{puts_left={PutsLeft,{Dst,Sz,Es0}}} when is_integer(PutsLeft) -> Index = Sz - PutsLeft + 1, - Es = Es0#{ {integer,Index} => get_term_type(Src, Vst0) }, + Es = Es0#{ Index => get_term_type(Src, Vst0) }, St = St0#st{puts_left={PutsLeft-1,{Dst,Sz,Es}}}, Vst#vst{current=St} end; @@ -590,11 +590,11 @@ valfun_1({get_tl,Src,Dst}, Vst) -> assert_type(cons, Src, Vst), extract_term(term, get_tl, [Src], Dst, Vst); valfun_1({get_tuple_element,Src,N,Dst}, Vst) -> + Index = N+1, assert_not_literal(Src), - assert_type({tuple_element,N+1}, Src, Vst), - Index = {integer,N+1}, + assert_type({tuple_element,Index}, Src, Vst), Type = get_element_type(Index, Src, Vst), - extract_term(Type, {bif,element}, [Index, Src], Dst, Vst); + extract_term(Type, {bif,element}, [{integer, Index}, Src], Dst, Vst); valfun_1({jump,{f,Lbl}}, Vst) -> branch(Lbl, Vst, fun(SuccVst) -> @@ -723,7 +723,12 @@ valfun_4({bif,element,{f,Fail},[Pos,Src],Dst}, Vst) -> SuccVst = update_type(fun meet/2, {integer,[]}, Pos, SuccVst1), - ElementType = get_element_type(PosType, Src, SuccVst), + ElementType = case PosType of + {integer,Index} -> + get_element_type(Index, Src, SuccVst); + _ -> + term + end, extract_term(ElementType, {bif,element}, [Pos,Src], Dst, SuccVst) end); @@ -816,7 +821,7 @@ valfun_4({set_tuple_element,Src,Tuple,N}, Vst) -> %% narrowing) known elements, and we can't use extract_term either since %% the source tuple may be aliased. {tuple, Sz, Es0} = get_term_type(Tuple, Vst), - Es = set_element_type({integer,I}, get_term_type(Src, Vst), Es0), + Es = set_element_type(I, get_term_type(Src, Vst), Es0), override_type({tuple, Sz, Es}, Tuple, Vst); %% Match instructions. valfun_4({select_val,Src,{f,Fail},{list,Choices}}, Vst) -> @@ -923,7 +928,7 @@ valfun_4({test,test_arity,{f,Lbl},[Tuple,Sz]}, Vst) when is_integer(Sz) -> type_test(Lbl, Type, Tuple, Vst); valfun_4({test,is_tagged_tuple,{f,Lbl},[Src,Sz,Atom]}, Vst) -> assert_term(Src, Vst), - Type = {tuple, Sz, #{ {integer,1} => Atom }}, + Type = {tuple, Sz, #{ 1 => Atom }}, type_test(Lbl, Type, Src, Vst); valfun_4({test,is_eq_exact,{f,Lbl},[Src,Val]=Ss}, Vst) -> validate_src(Ss, Vst), @@ -1619,11 +1624,11 @@ infer_types_1(#value{op={bif,'=:='},args=[LHS,RHS]}) -> Infer_R(RHS, Infer_L(LHS, S)); (_, S) -> S end; -infer_types_1(#value{op={bif,element},args=[{integer,Index}=Key,Tuple]}) -> +infer_types_1(#value{op={bif,element},args=[{integer,Index},Tuple]}) -> fun(Val, S) -> case is_value_alive(Tuple, S) of true -> - Type = {tuple,[Index], #{ Key => get_term_type(Val, S) }}, + Type = {tuple,[Index], #{ Index => get_term_type(Val, S) }}, update_type(fun meet/2, Type, Tuple, S); false -> S @@ -2048,7 +2053,7 @@ join(T1, T2) when T1 =/= T2 -> join_tuple_elements(Limit, EsA, EsB) -> Es0 = join_elements(EsA, EsB), - maps:filter(fun({integer,Index}, _Type) -> Index =< Limit end, Es0). + maps:filter(fun(Index, _Type) -> Index =< Limit end, Es0). join_elements(Es1, Es2) -> Keys = if @@ -2168,7 +2173,7 @@ meet_elements_1([], _Es1, _Es2, Acc) -> %% No tuple elements may have an index above the known size. assert_tuple_elements(Limit, Es) -> - true = maps:fold(fun({integer,Index}, _T, true) -> + true = maps:fold(fun(Index, _T, true) -> Index =< Limit end, true, Es). %Assertion. @@ -2209,13 +2214,11 @@ assert_type(Needed, Actual) -> get_element_type(Key, Src, Vst) -> get_element_type_1(Key, get_term_type(Src, Vst)). -get_element_type_1({integer,_}=Key, {tuple,_Sz,Es}) -> +get_element_type_1(Key, {tuple,_Sz,Es}) -> case Es of #{ Key := Type } -> Type; #{} -> term - end; -get_element_type_1(_Index, _Type) -> - term. + end. set_element_type(_Key, none, Es) -> Es; @@ -2316,7 +2319,7 @@ glt_1(I) when is_integer(I) -> {integer, I}; glt_1(T) when is_tuple(T) -> {Es,_} = foldl(fun(Val, {Es0, Index}) -> Type = glt_1(Val), - Es = set_element_type({integer,Index}, Type, Es0), + Es = set_element_type(Index, Type, Es0), {Es, Index + 1} end, {#{}, 1}, tuple_to_list(T)), {tuple, tuple_size(T), Es}; @@ -2843,7 +2846,7 @@ call_return_type_1(erlang, setelement, 3, Vst) -> case meet({tuple,[I],#{}}, TupleType) of {tuple, Sz, Es0} -> ValueType = get_term_type({x,2}, Vst), - Es = set_element_type({integer,I}, ValueType, Es0), + Es = set_element_type(I, ValueType, Es0), {tuple, Sz, Es}; none -> TupleType @@ -2931,7 +2934,7 @@ 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,#{ {integer,1} => ListType} }; + {tuple, 2, #{ 1 => ListType }}; lists_mod_return_type(partition, 2, _Vst) -> two_tuple(list, list); lists_mod_return_type(reverse, 1, Vst) -> @@ -2959,8 +2962,7 @@ lists_mod_return_type(_, _, _) -> term. two_tuple(Type1, Type2) -> - {tuple,2,#{ {integer,1} => Type1, - {integer,2} => Type2 }}. + {tuple, 2, #{ 1 => Type1, 2 => Type2 }}. same_length_type(Reg, Vst) -> case get_term_type(Reg, Vst) of -- cgit v1.2.3 From d6287ba96fddcad782316061a1813bbd627ae6c9 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Tue, 28 May 2019 17:22:21 +0200 Subject: beam_validator: Simplify the match context type There's no need to have an id as part of the type, as the value reference (through which the type is reached) uniquely identifies the match context. --- lib/compiler/src/beam_validator.erl | 34 ++++++++++++++-------------------- 1 file changed, 14 insertions(+), 20 deletions(-) diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index c5e3f6ac35..a89295ab72 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -154,8 +154,7 @@ validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) -> %% Match context type. -record(ms, - {id=make_ref() :: reference(), %Unique ID. - valid=0 :: non_neg_integer(), %Valid slots + {valid=0 :: non_neg_integer(), %Valid slots slots=0 :: non_neg_integer() %Number of slots }). @@ -487,7 +486,9 @@ valfun_1(remove_message, Vst) -> %% without restrictions. remove_fragility(Vst); valfun_1({'%', {type_info, Reg, match_context}}, Vst) -> - update_type(fun meet/2, #ms{}, Reg, Vst); + %% This is a gross hack, but we'll be rid of it once we have proper union + %% types. + override_type(#ms{}, Reg, Vst); valfun_1({'%', {type_info, Reg, Type}}, Vst) -> %% Explicit type information inserted by optimization passes to indicate %% that Reg has a certain type, so that we can accept cross-function type @@ -1260,21 +1261,22 @@ verify_remote_args_1(X, Vst) -> verify_local_args(-1, _Lbl, _CtxIds, _Vst) -> ok; -verify_local_args(X, Lbl, CtxIds, Vst) -> +verify_local_args(X, Lbl, CtxRefs, Vst) -> Reg = {x, X}, assert_not_fragile(Reg, Vst), case get_movable_term_type(Reg, Vst) of - #ms{id=Id}=Type -> - case CtxIds of - #{ Id := Other } -> + #ms{}=Type -> + VRef = get_reg_vref(Reg, Vst), + case CtxRefs of + #{ VRef := Other } -> error({multiple_match_contexts, [Reg, Other]}); #{} -> verify_arg_type(Lbl, Reg, Type, Vst), - verify_local_args(X - 1, Lbl, CtxIds#{ Id => Reg }, Vst) + verify_local_args(X - 1, Lbl, CtxRefs#{ VRef => Reg }, Vst) end; Type -> verify_arg_type(Lbl, Reg, Type, Vst), - verify_local_args(X - 1, Lbl, CtxIds, Vst) + verify_local_args(X - 1, Lbl, CtxRefs, Vst) end. %% Verifies that the given argument narrows to what the function expects. @@ -2039,13 +2041,9 @@ join({atom,A}, {atom,B}) when is_boolean(A), is_boolean(B) -> bool; join({atom,_}, {atom,_}) -> {atom,[]}; -join(#ms{id=Id1,valid=B1,slots=Slots1}, - #ms{id=Id2,valid=B2,slots=Slots2}) -> - Id = if - Id1 =:= Id2 -> Id1; - true -> make_ref() - end, - #ms{id=Id,valid=B1 band B2,slots=min(Slots1, Slots2)}; +join(#ms{valid=B1,slots=Slots1}, + #ms{valid=B2,slots=Slots2}) -> + #ms{valid=B1 band B2,slots=min(Slots1, Slots2)}; join(T1, T2) when T1 =/= T2 -> %% We've exhaused all other options, so the type must either be a list or %% a 'term'. @@ -2107,10 +2105,6 @@ meet(term, Other) -> Other; meet(Other, term) -> Other; -meet(#ms{}, binary) -> - #ms{}; -meet(binary, #ms{}) -> - #ms{}; meet({literal,_}, {literal,_}) -> none; meet(T1, {literal,_}=T2) -> -- cgit v1.2.3 From 9cc02ae10d1548ae1cc8c9f4b3bc98e3c29d5fd3 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Tue, 11 Jun 2019 11:38:37 +0200 Subject: beam_validator: Refactor local call validation --- lib/compiler/src/beam_validator.erl | 64 +++++++++++++++++++++---------------- 1 file changed, 36 insertions(+), 28 deletions(-) diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index a89295ab72..7eb4cbe60d 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -119,7 +119,7 @@ format_error(Error) -> %% format as used in the compiler and in .S files. validate(Module, Fs) -> - Ft = index_parameter_types(Fs, []), + Ft = build_function_table(Fs, []), validate_0(Module, Fs, Ft). validate_0(_Module, [], _) -> []; @@ -224,36 +224,36 @@ validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) -> branched=gb_trees:empty() :: branched_tab(), %% All defined labels labels=gb_sets:empty() :: label_set(), - %% Argument information of other functions in the module + %% Information of other functions in the module ft=gb_trees:empty() :: ft_tab(), %% Counter for #value_ref{} creation ref_ctr=0 :: index() }). -index_parameter_types([{function,_,_,Entry,Code0}|Fs], Acc0) -> +build_function_table([{function,_,Arity,Entry,Code0}|Fs], Acc0) -> Code = dropwhile(fun({label,L}) when L =:= Entry -> false; (_) -> true end, Code0), case Code of [{label,Entry}|Is] -> - Acc = index_parameter_types_1(Is, Entry, Acc0), - index_parameter_types(Fs, Acc); + Info = #{ arity => Arity, + parameter_types => find_parameter_types(Is, #{}) }, + build_function_table(Fs, [{Entry, Info} | Acc0]); _ -> %% Something is seriously wrong. Ignore it for now. %% It will be detected and diagnosed later. - index_parameter_types(Fs, Acc0) + build_function_table(Fs, Acc0) end; -index_parameter_types([], Acc) -> +build_function_table([], Acc) -> gb_trees:from_orddict(sort(Acc)). -index_parameter_types_1([{'%', {type_info, Reg, Type0}} | Is], Entry, Acc) -> +find_parameter_types([{'%', {type_info, Reg, Type0}} | Is], Acc) -> Type = case Type0 of match_context -> #ms{}; _ -> Type0 end, - Key = {Entry, Reg}, - index_parameter_types_1(Is, Entry, [{Key, Type} | Acc]); -index_parameter_types_1(_, _, Acc) -> + find_parameter_types(Is, Acc#{ Reg => Type }); +find_parameter_types(_, Acc) -> Acc. validate_1(Is, Name, Arity, Entry, Ft) -> @@ -1246,8 +1246,15 @@ tail_call(Name, Live, Vst0) -> verify_call_args(_, 0, #vst{}) -> ok; -verify_call_args({f,Lbl}, Live, Vst) when is_integer(Live)-> - verify_local_args(Live - 1, Lbl, #{}, Vst); +verify_call_args({f,Lbl}, Live, #vst{ft=Ft}=Vst) when is_integer(Live) -> + case gb_trees:lookup(Lbl, Ft) of + {value, FuncInfo} -> + #{ arity := Live, + parameter_types := ParamTypes } = FuncInfo, + verify_local_args(Live - 1, ParamTypes, #{}, Vst); + none -> + error(local_call_to_unknown_function) + end; verify_call_args(_, Live, Vst) when is_integer(Live)-> verify_remote_args_1(Live - 1, Vst); verify_call_args(_, Live, _) -> @@ -1259,9 +1266,9 @@ verify_remote_args_1(X, Vst) -> assert_durable_term({x, X}, Vst), verify_remote_args_1(X - 1, Vst). -verify_local_args(-1, _Lbl, _CtxIds, _Vst) -> +verify_local_args(-1, _ParamTypes, _CtxIds, _Vst) -> ok; -verify_local_args(X, Lbl, CtxRefs, Vst) -> +verify_local_args(X, ParamTypes, CtxRefs, Vst) -> Reg = {x, X}, assert_not_fragile(Reg, Vst), case get_movable_term_type(Reg, Vst) of @@ -1271,34 +1278,35 @@ verify_local_args(X, Lbl, CtxRefs, Vst) -> #{ VRef := Other } -> error({multiple_match_contexts, [Reg, Other]}); #{} -> - verify_arg_type(Lbl, Reg, Type, Vst), - verify_local_args(X - 1, Lbl, CtxRefs#{ VRef => Reg }, Vst) + verify_arg_type(Reg, Type, ParamTypes), + verify_local_args(X - 1, ParamTypes, + CtxRefs#{ VRef => Reg }, Vst) end; Type -> - verify_arg_type(Lbl, Reg, Type, Vst), - verify_local_args(X - 1, Lbl, CtxRefs, Vst) + verify_arg_type(Reg, Type, ParamTypes), + verify_local_args(X - 1, ParamTypes, CtxRefs, Vst) end. %% Verifies that the given argument narrows to what the function expects. -verify_arg_type(Lbl, Reg, #ms{}, #vst{ft=Ft}) -> +verify_arg_type(Reg, #ms{}, ParamTypes) -> %% Match contexts require explicit support, and may not be passed to a %% function that accepts arbitrary terms. - case gb_trees:lookup({Lbl, Reg}, Ft) of - {value, #ms{}} -> ok; - _ -> error(no_bs_start_match2) + case ParamTypes of + #{ Reg := #ms{}} -> ok; + #{} -> error(no_bs_start_match2) end; -verify_arg_type(Lbl, Reg, GivenType, #vst{ft=Ft}) -> - case gb_trees:lookup({Lbl, Reg}, Ft) of - {value, #ms{}} -> +verify_arg_type(Reg, GivenType, ParamTypes) -> + case ParamTypes of + #{ Reg := #ms{}} -> %% Functions that accept match contexts also accept all other %% terms. This will change once we support union types. ok; - {value, RequiredType} -> + #{ Reg := RequiredType } -> case vat_1(GivenType, RequiredType) of true -> ok; false -> error({bad_arg_type, Reg, GivenType, RequiredType}) end; - none -> + #{} -> ok end. -- cgit v1.2.3 From 5ea8e4707dfacfe94bff73336bfe07f12880c1aa Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Wed, 29 May 2019 16:16:26 +0200 Subject: beam_validator: Reduce literals to their types We didn't gain anything by tracking literals exactly, and it greatly complicates sharing types between passes. --- lib/compiler/src/beam_validator.erl | 57 +++++++------------------------------ 1 file changed, 11 insertions(+), 46 deletions(-) diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 7eb4cbe60d..4c223a93ed 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -169,8 +169,7 @@ validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) -> number | term | tuple_in_progress | - {tuple, tuple_sz(), #{ pos_integer() => type() }} | - literal(). + {tuple, tuple_sz(), #{ pos_integer() => type() }}. -type tag() :: initialized | uninitialized | @@ -1327,8 +1326,6 @@ vat_1({float,A}, {float,B}) -> A =:= B orelse is_list(A) orelse is_list(B); vat_1({float,_}, number) -> true; vat_1({integer,A}, {integer,B}) -> A =:= B orelse is_list(A) orelse is_list(B); vat_1({integer,_}, number) -> true; -vat_1(_, {literal,_}) -> false; -vat_1({literal,_}=Lit, Required) -> vat_1(get_literal_type(Lit), Required); vat_1(nil, list) -> true; vat_1({tuple,SzA,EsA}, {tuple,SzB,EsB}) -> if @@ -2015,10 +2012,6 @@ join(none, Other) -> Other; join(Other, none) -> Other; -join({literal,_}=T1, T2) -> - join_literal(T1, T2); -join(T1, {literal,_}=T2) -> - join_literal(T2, T1); join({tuple,Size,EsA}, {tuple,Size,EsB}) -> Es = join_tuple_elements(tuple_sz(Size), EsA, EsB), {tuple, Size, Es}; @@ -2079,16 +2072,6 @@ join_elements_1([Key | Keys], Es1, Es2, Acc0) -> join_elements_1([], _Es1, _Es2, Acc) -> Acc. -%% Joins types of literals; note that the left argument must either be a -%% literal or exactly equal to the second argument. -join_literal(Same, Same) -> - Same; -join_literal({literal,_}=Lit, T) -> - join_literal(T, get_literal_type(Lit)); -join_literal(T1, T2) -> - %% We're done extracting the types, try merging them again. - join(T1, T2). - join_list(nil, cons) -> list; join_list(nil, list) -> list; join_list(cons, list) -> list; @@ -2113,15 +2096,6 @@ meet(term, Other) -> Other; meet(Other, term) -> Other; -meet({literal,_}, {literal,_}) -> - none; -meet(T1, {literal,_}=T2) -> - meet(T2, T1); -meet({literal,_}=T1, T2) -> - case meet(get_literal_type(T1), T2) of - none -> none; - _ -> T1 - end; meet(T1, T2) -> case {erlang:min(T1, T2),erlang:max(T1, T2)} of {{atom,_}=A,{atom,[]}} -> A; @@ -2199,17 +2173,12 @@ assert_type(WantedType, Term, Vst) -> assert_type(Correct, Correct) -> ok; assert_type(float, {float,_}) -> ok; assert_type(tuple, {tuple,_,_}) -> ok; -assert_type(tuple, {literal,Tuple}) when is_tuple(Tuple) -> ok; assert_type({tuple_element,I}, {tuple,[Sz],_}) when 1 =< I, I =< Sz -> ok; assert_type({tuple_element,I}, {tuple,Sz,_}) when is_integer(Sz), 1 =< I, I =< Sz -> ok; -assert_type({tuple_element,I}, {literal,Lit}) when I =< tuple_size(Lit) -> - ok; -assert_type(cons, {literal,[_|_]}) -> - ok; assert_type(Needed, Actual) -> error({bad_type,{needed,Needed},{actual,Actual}}). @@ -2258,7 +2227,6 @@ get_movable_term_type(Src, Vst) -> {catchtag,_} -> error({catchtag,Src}); {trytag,_} -> error({trytag,Src}); tuple_in_progress -> error({tuple_in_progress,Src}); - {literal,_}=Lit -> get_literal_type(Lit); Type -> Type end. @@ -2303,21 +2271,20 @@ get_raw_type(Src, #vst{}) -> is_value_alive(#value_ref{}=Ref, #vst{current=#st{vs=Vs}}) -> is_map_key(Ref, Vs). -get_literal_type(nil=T) -> T; -get_literal_type({atom,A}=T) when is_atom(A) -> T; -get_literal_type({float,F}=T) when is_float(F) -> T; -get_literal_type({integer,I}=T) when is_integer(I) -> T; -get_literal_type({literal,[_|_]}) -> cons; -get_literal_type({literal,Bitstring}) when is_bitstring(Bitstring) -> binary; -get_literal_type({literal,Map}) when is_map(Map) -> map; -get_literal_type({literal,Tuple}) when is_tuple(Tuple) -> glt_1(Tuple); -get_literal_type({literal,_}) -> term; +get_literal_type(nil) -> glt_1([]); +get_literal_type({atom,A}) when is_atom(A) -> glt_1(A); +get_literal_type({float,F}) when is_float(F) -> glt_1(F); +get_literal_type({integer,I}) when is_integer(I) -> glt_1(I); +get_literal_type({literal,L}) -> glt_1(L); get_literal_type(T) -> error({not_literal,T}). glt_1([]) -> nil; +glt_1([_|_]) -> cons; glt_1(A) when is_atom(A) -> {atom, A}; +glt_1(B) when is_bitstring(B) -> binary; glt_1(F) when is_float(F) -> {float, F}; glt_1(I) when is_integer(I) -> {integer, I}; +glt_1(M) when is_map(M) -> map; glt_1(T) when is_tuple(T) -> {Es,_} = foldl(fun(Val, {Es0, Index}) -> Type = glt_1(Val), @@ -2325,8 +2292,8 @@ glt_1(T) when is_tuple(T) -> {Es, Index + 1} end, {#{}, 1}, tuple_to_list(T)), {tuple, tuple_size(T), Es}; -glt_1(L) -> - {literal, L}. +glt_1(_Term) -> + term. %%% %%% Branch tracking @@ -2839,7 +2806,6 @@ call_return_type_1(erlang, setelement, 3, Vst) -> IndexType = get_term_type({x,0}, Vst), TupleType = case get_term_type({x,1}, Vst) of - {literal,Tuple}=Lit when is_tuple(Tuple) -> get_literal_type(Lit); {tuple,_,_}=TT -> TT; _ -> {tuple,[0],#{}} end, @@ -2968,7 +2934,6 @@ two_tuple(Type1, Type2) -> same_length_type(Reg, Vst) -> case get_term_type(Reg, Vst) of - {literal,[_|_]} -> cons; cons -> cons; nil -> nil; _ -> list -- cgit v1.2.3 From c02fc618f98c9fb97b15aae97e11fa1c23e250fc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Fri, 24 May 2019 10:43:14 +0200 Subject: beam_ssa_type: Fix 'band' type determination The use of meet/2 was incorrect as we weren't guaranteed to provide a more specific type. This is unlikely to cause errors in OTP 22 as our ranges were *always* '0 .. X' or 'X .. X', and a meet/2 of two integers would take the least specific minimum value and most specific maximum value, making things work by accident. This is covered by beam_type_SUITE:integers/1, and was made visible when beam_types:meet/2 was fixed to reject integers that didn't overlap fully. --- lib/compiler/src/beam_ssa_type.erl | 49 ++++++++++++++++++++++++++------------ 1 file changed, 34 insertions(+), 15 deletions(-) diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index da73dc26f7..c163d544ce 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -1242,22 +1242,41 @@ band_type([Other,#b_literal{val=Int}], Ts) when is_integer(Int) -> band_type([_,_], _) -> t_integer(). band_type_1(Int, OtherSrc, Ts) -> - Type = band_type_2(Int, 0), OtherType = get_type(OtherSrc, Ts), - meet(Type, OtherType). - -band_type_2(N, Bits) when Bits < 64 -> - case 1 bsl Bits of - P when P =:= N + 1 -> - t_integer(0, N); - P when P > N + 1 -> - t_integer(); - _ -> - band_type_2(N, Bits+1) - end; -band_type_2(_, _) -> - %% Negative or large positive number. Give up. - t_integer(). + case OtherType of + #t_integer{elements={Min0,Max0}} when Max0 - Min0 < 1 bsl 256 -> + {Intersection, Union} = range_masks(Min0, Max0), + + Min = Intersection band Int, + Max = min(Max0, Union band Int), + + #t_integer{elements={Min,Max}}; + _ when Int >= 0 -> + %% The range is either unknown or too wide, conservatively assume + %% that the new range is 0 .. Int. + #t_integer{elements={0,Int}}; + _ when Int < 0 -> + %% We can't infer boundaries when the range is unknown and the + %% other operand is a negative number, as the latter sign-extends + %% to infinity and we can't express an inverted range at the + %% moment (cf. X band -8; either less than 7 or greater than 7). + #t_integer{} + end. + +%% Returns two bitmasks describing all possible values between From and To. +%% +%% The first contains the bits that are common to all values, and the second +%% contains the bits that are set by any value in the range. +range_masks(From, To) when From =< To -> + range_masks_1(From, To, 0, -1, 0). + +range_masks_1(From, To, BitPos, Intersection, Union) when From < To -> + range_masks_1(From + (1 bsl BitPos), To, BitPos + 1, + Intersection band From, Union bor From); +range_masks_1(_From, To, _BitPos, Intersection0, Union0) -> + Intersection = To band Intersection0, + Union = To bor Union0, + {Intersection, Union}. bs_match_type([#b_literal{val=Type}|Args]) -> bs_match_type(Type, Args). -- cgit v1.2.3 From 2821afd35f0c7223bca45e6031ea210b4fcaa2a5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Tue, 28 May 2019 17:09:42 +0200 Subject: beam_ssa_type: Fix meet/join inconsistency meet/2 and join/2 were not entirely consistent with each other, and it was possible to meet integers that didn't overlap, producing a nonsense result. None of these can cause issues in the OTP 22 track as far as we can tell, so a patch doesn't feel necessary at this time. --- lib/compiler/src/beam_ssa_type.erl | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index c163d544ce..f8fefa8936 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -1860,6 +1860,9 @@ join(#t_atom{elements=[_|_]}, #t_atom{elements=any}=T) -> T; join({binary,U1}, {binary,U2}) -> {binary,gcd(U1, U2)}; join(#t_fun{}, #t_fun{}) -> #t_fun{}; +join(#t_integer{elements={MinA,MaxA}}, + #t_integer{elements={MinB,MaxB}}) -> + #t_integer{elements={min(MinA,MinB),max(MaxA,MaxB)}}; join(#t_integer{}, #t_integer{}) -> t_integer(); join(list, cons) -> list; join(cons, list) -> list; @@ -1985,9 +1988,10 @@ meet(#t_integer{elements={_,_}}=T, #t_integer{elements=any}) -> T; meet(#t_integer{elements=any}, #t_integer{elements={_,_}}=T) -> T; -meet(#t_integer{elements={Min1,Max1}}, - #t_integer{elements={Min2,Max2}}) -> - #t_integer{elements={max(Min1, Min2),min(Max1, Max2)}}; +meet(#t_integer{elements={MinA,MaxA}}, #t_integer{elements={MinB,MaxB}}) + when MinA >= MinB, MaxA =< MaxB; + MinB >= MinA, MaxB =< MaxA -> + #t_integer{elements={max(MinA, MinB),min(MaxA, MaxB)}}; meet(#t_integer{}=T, number) -> T; meet(float=T, number) -> T; meet(number, #t_integer{}=T) -> T; @@ -1999,7 +2003,7 @@ meet(nil, list) -> nil; meet(#t_tuple{}=T1, #t_tuple{}=T2) -> meet_tuples(T1, T2); meet({binary,U1}, {binary,U2}) -> - {binary,max(U1, U2)}; + {binary, U1 * U2 div gcd(U1, U2)}; meet(any, T) -> verified_type(T); meet(T, any) -> @@ -2073,7 +2077,7 @@ verified_type({binary,U}=T) when is_integer(U) -> T; verified_type(#t_fun{arity=Arity}=T) when Arity =:= any; is_integer(Arity) -> T; verified_type(#t_integer{elements=any}=T) -> T; verified_type(#t_integer{elements={Min,Max}}=T) - when is_integer(Min), is_integer(Max) -> T; + when is_integer(Min), is_integer(Max), Min =< Max -> T; verified_type(list=T) -> T; verified_type(map=T) -> T; verified_type(nil=T) -> T; -- cgit v1.2.3 From 9bf77c86ec83853d321958dac3582fdc2f00b045 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Thu, 23 May 2019 11:47:24 +0200 Subject: compiler: Break out SSA/beam type definitions into a separate module --- lib/compiler/src/Makefile | 5 +- lib/compiler/src/beam_ssa_type.erl | 322 ++------------------- lib/compiler/src/beam_types.erl | 294 +++++++++++++++++++ lib/compiler/src/beam_types.hrl | 58 ++++ lib/compiler/src/compile.erl | 1 + lib/compiler/src/compiler.app.src | 1 + lib/compiler/test/Makefile | 3 +- lib/compiler/test/beam_types_SUITE.erl | 80 +++++ .../test/property_test/beam_types_prop.erl | 140 +++++++++ 9 files changed, 605 insertions(+), 299 deletions(-) create mode 100644 lib/compiler/src/beam_types.erl create mode 100644 lib/compiler/src/beam_types.hrl create mode 100644 lib/compiler/test/beam_types_SUITE.erl create mode 100644 lib/compiler/test/property_test/beam_types_prop.erl diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile index 0c1dc30f9c..89feb35bc2 100644 --- a/lib/compiler/src/Makefile +++ b/lib/compiler/src/Makefile @@ -71,6 +71,7 @@ MODULES = \ beam_ssa_type \ beam_kernel_to_ssa \ beam_trim \ + beam_types \ beam_utils \ beam_validator \ beam_z \ @@ -103,6 +104,7 @@ HRL_FILES= \ beam_disasm.hrl \ beam_ssa_opt.hrl \ beam_ssa.hrl \ + beam_types.hrl \ core_parse.hrl \ v3_kernel.hrl @@ -203,7 +205,8 @@ $(EBIN)/beam_ssa_pp.beam: beam_ssa.hrl $(EBIN)/beam_ssa_pre_codegen.beam: beam_ssa.hrl $(EBIN)/beam_ssa_recv.beam: beam_ssa.hrl $(EBIN)/beam_ssa_share.beam: beam_ssa.hrl -$(EBIN)/beam_ssa_type.beam: beam_ssa.hrl +$(EBIN)/beam_ssa_type.beam: beam_ssa.hrl beam_types.hrl +$(EBIN)/beam_types.beam: beam_types.hrl $(EBIN)/cerl.beam: core_parse.hrl $(EBIN)/compile.beam: core_parse.hrl ../../stdlib/include/erl_compile.hrl $(EBIN)/core_lib.beam: core_parse.hrl diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index f8fefa8936..6d697787c0 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -22,6 +22,8 @@ -export([opt_start/4, opt_continue/4, opt_finish/3]). -include("beam_ssa_opt.hrl"). +-include("beam_types.hrl"). + -import(lists, [all/2,any/2,droplast/1,foldl/3,last/1,member/2, keyfind/3,reverse/1,reverse/2, sort/1,split/2]). @@ -37,23 +39,6 @@ sub = #{} :: #{beam_ssa:b_var():=beam_ssa:value()}, ret_type = [] :: [type()]}). --define(ATOM_SET_SIZE, 5). - -%% Records that represent type information. --record(t_atom, {elements=any :: 'any' | [atom()]}). --record(t_bs_match, {type :: type()}). --record(t_fun, {arity=any :: arity() | 'any'}). --record(t_integer, {elements=any :: 'any' | {integer(),integer()}}). --record(t_tuple, {size=0 :: integer(), - exact=false :: boolean(), - %% Known element types (1-based index), unknown elements are - %% are assumed to be 'any'. - elements=#{} :: #{ non_neg_integer() => type() }}). - --type type() :: 'any' | 'none' | - #t_atom{} | #t_bs_match{} | #t_fun{} | #t_integer{} | #t_tuple{} | - {'binary',pos_integer()} | 'cons' | 'float' | - 'list' | 'map' | 'nil' | 'number'. -type type_db() :: #{beam_ssa:var_name():=type()}. -spec opt_start(Linear, Args, Anno, FuncDb) -> {Linear, FuncDb} when @@ -100,7 +85,7 @@ join_arg_types(Args, ArgTypes, Anno) -> end, Ts0, ParamTypes). join_arg_types_1([Arg | Args], [TM | TMs], Ts) when map_size(TM) =/= 0 -> - join_arg_types_1(Args, TMs, Ts#{ Arg => join(maps:values(TM))}); + join_arg_types_1(Args, TMs, Ts#{ Arg => beam_types:join(maps:values(TM))}); join_arg_types_1([Arg | Args], [_TM | TMs], Ts) -> join_arg_types_1(Args, TMs, Ts#{ Arg => any }); join_arg_types_1([], [], Ts) -> @@ -159,7 +144,7 @@ opt_finish_1([Arg | Args], [TypeMap | TypeMaps], ParamInfo) map_size(TypeMap) =:= 0 -> opt_finish_1(Args, TypeMaps, ParamInfo); opt_finish_1([Arg | Args], [TypeMap | TypeMaps], ParamInfo0) -> - JoinedType0 = verified_type(join(maps:values(TypeMap))), + JoinedType0 = beam_types:join(maps:values(TypeMap)), case validator_anno(JoinedType0) of any -> opt_finish_1(Args, TypeMaps, ParamInfo0); @@ -232,7 +217,7 @@ opt_1(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, %% potentially narrow the type of the phi node %% in the former successor. Ls = maps:remove(L, D0#d.ls), - RetType = join([none|D0#d.ret_type]), + RetType = beam_types:join([none|D0#d.ret_type]), D = D0#d{ds=Ds,ls=Ls,sub=Sub, func_db=Fdb,ret_type=[RetType]}, Blk = Blk0#b_blk{is=Is,last=Ret}, @@ -553,14 +538,14 @@ simplify(#b_set{op={bif,is_function},args=[Fun,#b_literal{val=Arity}]}=I, Ts) end; simplify(#b_set{op={bif,Op0},args=Args}=I, Ts) when Op0 =:= '=='; Op0 =:= '/=' -> Types = get_types(Args, Ts), - EqEq0 = case {meet(Types),join(Types)} of - {none,any} -> true; - {#t_integer{},#t_integer{}} -> true; - {float,float} -> true; - {{binary,_},_} -> true; - {#t_atom{},_} -> true; - {_,_} -> false - end, + EqEq0 = case {beam_types:meet(Types),beam_types:join(Types)} of + {none,any} -> true; + {#t_integer{},#t_integer{}} -> true; + {float,float} -> true; + {{binary,_},_} -> true; + {#t_atom{},_} -> true; + {_,_} -> false + end, EqEq = EqEq0 orelse any_non_numeric_argument(Args, Ts), case EqEq of true -> @@ -576,7 +561,7 @@ simplify(#b_set{op={bif,'=:='},args=[Same,Same]}, _Ts) -> #b_literal{val=true}; simplify(#b_set{op={bif,'=:='},args=[A1,_A2]=Args}=I, Ts) -> [T1,T2] = get_types(Args, Ts), - case meet(T1, T2) of + case beam_types:meet(T1, T2) of none -> #b_literal{val=false}; _ -> @@ -813,7 +798,7 @@ opt_switch(#b_switch{fail=Fail,list=List0}=Sw0, Type, Ts, Ds) -> prune_switch_list([{_,Fail}|T], Fail, Type, Ts) -> prune_switch_list(T, Fail, Type, Ts); prune_switch_list([{Arg,_}=Pair|T], Fail, Type, Ts) -> - case meet(get_type(Arg, Ts), Type) of + case beam_types:meet(get_type(Arg, Ts), Type) of none -> %% Different types. This value can never match. prune_switch_list(T, Fail, Type, Ts); @@ -873,7 +858,7 @@ update_successors(#b_ret{arg=Arg}, Ts, D) -> %% type. D; #{} -> - RetType = join([get_type(Arg, Ts) | D#d.ret_type]), + RetType = beam_types:join([get_type(Arg, Ts) | D#d.ret_type]), D#d{ret_type=[RetType]} end. @@ -882,7 +867,7 @@ subtract_sw_list(V, List, Ts) -> sub_sw_list_1(Type, [{Val,_}|T], Ts) -> ValType = get_type(Val, Ts), - sub_sw_list_1(subtract(Type, ValType), T, Ts); + sub_sw_list_1(beam_types:subtract(Type, ValType), T, Ts); sub_sw_list_1(Type, [], _Ts) -> Type. @@ -916,7 +901,7 @@ update_types(#b_set{op=Op,dst=Dst,args=Args}, Ts, Ds) -> type(phi, Args, Ts, _Ds) -> Types = [get_type(A, Ts) || {A,_} <- Args], - join(Types); + beam_types:join(Types); type({bif,'band'}, Args, Ts, _Ds) -> band_type(Args, Ts); type({bif,Bif}, Args, Ts, _Ds) -> @@ -1158,8 +1143,8 @@ t_two_tuple(Type1, Type2) -> %% Test whether TestOperation applied to an argument of type Type %% will succeed. Return yes, no, or maybe. %% -%% Type is a type as described in the comment for verified_type/1 at -%% the very end of this file, but it will *never* be 'any'. +%% Type can be any type as described in beam_types.hrl, but it must *never* be +%% any. will_succeed(is_atom, Type) -> case Type of @@ -1351,7 +1336,7 @@ simplify_is_record(I, #t_tuple{exact=Exact, #b_literal{} -> no; none -> %% Is it at all possible for the tag to match? - case meet(get_type(RecTag, Ts), TagType) of + case beam_types:meet(get_type(RecTag, Ts), TagType) of none -> no; _ -> maybe end @@ -1548,7 +1533,7 @@ infer_eq_type({bif,'=:='}, [#b_var{}=Arg0,#b_var{}=Arg1], Ts, _Ds) -> %% be inferred that L1 is 'cons' (the meet of 'cons' and 'list'). Type0 = get_type(Arg0, Ts), Type1 = get_type(Arg1, Ts), - Type = meet(Type0, Type1), + Type = beam_types:meet(Type0, Type1), [{V,MeetType} || {V,OrigType,MeetType} <- [{Arg0,Type0,Type},{Arg1,Type1,Type}], @@ -1748,7 +1733,7 @@ join_types_1([V|Vs], Ts0, Ts1) -> {#{V:=Same},#{V:=Same}} -> join_types_1(Vs, Ts0, Ts1); {#{V:=T0},#{V:=T1}} -> - case join(T0, T1) of + case beam_types:join(T0, T1) of T1 -> join_types_1(Vs, Ts0, Ts1); T -> @@ -1760,10 +1745,6 @@ join_types_1([V|Vs], Ts0, Ts1) -> join_types_1([], Ts0, Ts1) -> maps:merge(Ts0, Ts1). -join([T1,T2|Ts]) -> - join([join(T1, T2)|Ts]); -join([T]) -> T. - get_literal_from_type(#t_atom{elements=[Atom]}) -> #b_literal{val=Atom}; get_literal_from_type(#t_integer{elements={Int,Int}}) -> @@ -1825,271 +1806,18 @@ set_element_type(Key, any, Es) -> set_element_type(Key, Type, Es) -> Es#{ Key => Type }. -%% join(Type1, Type2) -> Type -%% Return the "join" of Type1 and Type2. The join is a more general -%% type than Type1 and Type2. For example: -%% -%% join(#t_integer{elements=any}, #t_integer=elements={0,3}}) -> -%% #t_integer{} -%% -%% The join for two different types result in 'any', which is -%% the top element for our type lattice: -%% -%% join(#t_integer{}, map) -> any - --spec join(type(), type()) -> type(). - -join(T, T) -> - verified_type(T); -join(none, T) -> - verified_type(T); -join(T, none) -> - verified_type(T); -join(any, _) -> any; -join(_, any) -> any; -join(#t_atom{elements=[_|_]=Set1}, #t_atom{elements=[_|_]=Set2}) -> - Set = ordsets:union(Set1, Set2), - case ordsets:size(Set) of - Size when Size =< ?ATOM_SET_SIZE -> - #t_atom{elements=Set}; - _Size -> - #t_atom{elements=any} - end; -join(#t_atom{elements=any}=T, #t_atom{elements=[_|_]}) -> T; -join(#t_atom{elements=[_|_]}, #t_atom{elements=any}=T) -> T; -join({binary,U1}, {binary,U2}) -> - {binary,gcd(U1, U2)}; -join(#t_fun{}, #t_fun{}) -> #t_fun{}; -join(#t_integer{elements={MinA,MaxA}}, - #t_integer{elements={MinB,MaxB}}) -> - #t_integer{elements={min(MinA,MinB),max(MaxA,MaxB)}}; -join(#t_integer{}, #t_integer{}) -> t_integer(); -join(list, cons) -> list; -join(cons, list) -> list; -join(nil, cons) -> list; -join(cons, nil) -> list; -join(nil, list) -> list; -join(list, nil) -> list; -join(#t_integer{}, float) -> number; -join(float, #t_integer{}) -> number; -join(#t_integer{}, number) -> number; -join(number, #t_integer{}) -> number; -join(float, number) -> number; -join(number, float) -> number; -join(#t_tuple{size=Sz,exact=ExactA,elements=EsA}, - #t_tuple{size=Sz,exact=ExactB,elements=EsB}) -> - Exact = ExactA and ExactB, - Es = join_tuple_elements(Sz, EsA, EsB), - #t_tuple{size=Sz,exact=Exact,elements=Es}; -join(#t_tuple{size=SzA,elements=EsA}, #t_tuple{size=SzB,elements=EsB}) -> - Sz = min(SzA, SzB), - Es = join_tuple_elements(Sz, EsA, EsB), - #t_tuple{size=Sz,elements=Es}; -join(_T1, _T2) -> - %%io:format("~p ~p\n", [_T1,_T2]), - any. - -join_tuple_elements(MinSize, EsA, EsB) -> - Es0 = join_elements(EsA, EsB), - maps:filter(fun(Index, _Type) -> Index =< MinSize end, Es0). - -join_elements(Es1, Es2) -> - Keys = if - map_size(Es1) =< map_size(Es2) -> maps:keys(Es1); - map_size(Es1) > map_size(Es2) -> maps:keys(Es2) - end, - join_elements_1(Keys, Es1, Es2, #{}). - -join_elements_1([Key | Keys], Es1, Es2, Acc0) -> - case {Es1, Es2} of - {#{ Key := Type1 }, #{ Key := Type2 }} -> - Acc = set_element_type(Key, join(Type1, Type2), Acc0), - join_elements_1(Keys, Es1, Es2, Acc); - {#{}, #{}} -> - join_elements_1(Keys, Es1, Es2, Acc0) - end; -join_elements_1([], _Es1, _Es2, Acc) -> - Acc. - -gcd(A, B) -> - case A rem B of - 0 -> B; - X -> gcd(B, X) - end. - meet_types([{V,T0}|Vs], Ts) -> #{V:=T1} = Ts, - case meet(T0, T1) of + case beam_types:meet(T0, T1) of T1 -> meet_types(Vs, Ts); T -> meet_types(Vs, Ts#{V:=T}) end; meet_types([], Ts) -> Ts. -meet([T1,T2|Ts]) -> - meet([meet(T1, T2)|Ts]); -meet([T]) -> T. - subtract_types([{V,T0}|Vs], Ts) -> #{V:=T1} = Ts, - case subtract(T1, T0) of + case beam_types:subtract(T1, T0) of T1 -> subtract_types(Vs, Ts); T -> subtract_types(Vs, Ts#{V:=T}) end; subtract_types([], Ts) -> Ts. - -%% subtract(Type1, Type2) -> Type. -%% Subtract Type2 from Type1. Example: -%% -%% subtract(list, cons) -> nil - -subtract(#t_atom{elements=[_|_]=Set0}, #t_atom{elements=[_|_]=Set1}) -> - case ordsets:subtract(Set0, Set1) of - [] -> none; - [_|_]=Set -> #t_atom{elements=Set} - end; -subtract(number, float) -> #t_integer{}; -subtract(number, #t_integer{elements=any}) -> float; -subtract(list, cons) -> nil; -subtract(list, nil) -> cons; -subtract(T, _) -> T. - -%% meet(Type1, Type2) -> Type -%% Return the "meet" of Type1 and Type2. The meet is a narrower -%% type than Type1 and Type2. For example: -%% -%% meet(#t_integer{elements=any}, #t_integer{elements={0,3}}) -> -%% #t_integer{elements={0,3}} -%% -%% The meet for two different types result in 'none', which is -%% the bottom element for our type lattice: -%% -%% meet(#t_integer{}, map) -> none - --spec meet(type(), type()) -> type(). - -meet(T, T) -> - verified_type(T); -meet(#t_atom{elements=[_|_]=Set1}, #t_atom{elements=[_|_]=Set2}) -> - case ordsets:intersection(Set1, Set2) of - [] -> - none; - [_|_]=Set -> - #t_atom{elements=Set} - end; -meet(#t_atom{elements=[_|_]}=T, #t_atom{elements=any}) -> - T; -meet(#t_atom{elements=any}, #t_atom{elements=[_|_]}=T) -> - T; -meet(#t_fun{arity=any}, #t_fun{}=T) -> - T; -meet(#t_fun{}=T, #t_fun{arity=any}) -> - T; -meet(#t_integer{elements={_,_}}=T, #t_integer{elements=any}) -> - T; -meet(#t_integer{elements=any}, #t_integer{elements={_,_}}=T) -> - T; -meet(#t_integer{elements={MinA,MaxA}}, #t_integer{elements={MinB,MaxB}}) - when MinA >= MinB, MaxA =< MaxB; - MinB >= MinA, MaxB =< MaxA -> - #t_integer{elements={max(MinA, MinB),min(MaxA, MaxB)}}; -meet(#t_integer{}=T, number) -> T; -meet(float=T, number) -> T; -meet(number, #t_integer{}=T) -> T; -meet(number, float=T) -> T; -meet(list, cons) -> cons; -meet(list, nil) -> nil; -meet(cons, list) -> cons; -meet(nil, list) -> nil; -meet(#t_tuple{}=T1, #t_tuple{}=T2) -> - meet_tuples(T1, T2); -meet({binary,U1}, {binary,U2}) -> - {binary, U1 * U2 div gcd(U1, U2)}; -meet(any, T) -> - verified_type(T); -meet(T, any) -> - verified_type(T); -meet(_, _) -> - %% Inconsistent types. There will be an exception at runtime. - none. - -meet_tuples(#t_tuple{size=Sz1,exact=true}, - #t_tuple{size=Sz2,exact=true}) when Sz1 =/= Sz2 -> - none; -meet_tuples(#t_tuple{size=Sz1,exact=Ex1,elements=Es1}, - #t_tuple{size=Sz2,exact=Ex2,elements=Es2}) -> - Size = max(Sz1, Sz2), - Exact = Ex1 or Ex2, - case meet_elements(Es1, Es2) of - none -> - none; - Es -> - #t_tuple{size=Size,exact=Exact,elements=Es} - end. - -meet_elements(Es1, Es2) -> - Keys = maps:keys(Es1) ++ maps:keys(Es2), - meet_elements_1(Keys, Es1, Es2, #{}). - -meet_elements_1([Key | Keys], Es1, Es2, Acc) -> - case {Es1, Es2} of - {#{ Key := Type1 }, #{ Key := Type2 }} -> - case meet(Type1, Type2) of - none -> none; - Type -> meet_elements_1(Keys, Es1, Es2, Acc#{ Key => Type }) - end; - {#{ Key := Type1 }, _} -> - meet_elements_1(Keys, Es1, Es2, Acc#{ Key => Type1 }); - {_, #{ Key := Type2 }} -> - meet_elements_1(Keys, Es1, Es2, Acc#{ Key => Type2 }) - end; -meet_elements_1([], _Es1, _Es2, Acc) -> - Acc. - -%% verified_type(Type) -> Type -%% Returns the passed in type if it is one of the defined types. -%% Crashes if there is anything wrong with the type. -%% -%% Here are all possible types: -%% -%% any Any Erlang term (top element for the type lattice). -%% -%% #t_atom{} Any atom or some specific atoms. -%% {binary,Unit} Binary/bitstring aligned to unit Unit. -%% float Floating point number. -%% #t_integer{} Integer -%% list Empty or nonempty list. -%% map Map. -%% nil Empty list. -%% cons Cons (nonempty list). -%% number A number (float or integer). -%% #t_tuple{} Tuple. -%% -%% none No type (bottom element for the type lattice). - --spec verified_type(T) -> T when - T :: type(). - -verified_type(any=T) -> T; -verified_type(none=T) -> T; -verified_type(#t_atom{elements=any}=T) -> T; -verified_type(#t_atom{elements=[_|_]}=T) -> T; -verified_type({binary,U}=T) when is_integer(U) -> T; -verified_type(#t_fun{arity=Arity}=T) when Arity =:= any; is_integer(Arity) -> T; -verified_type(#t_integer{elements=any}=T) -> T; -verified_type(#t_integer{elements={Min,Max}}=T) - when is_integer(Min), is_integer(Max), Min =< Max -> T; -verified_type(list=T) -> T; -verified_type(map=T) -> T; -verified_type(nil=T) -> T; -verified_type(cons=T) -> T; -verified_type(number=T) -> T; -verified_type(#t_tuple{size=Size,elements=Es}=T) -> - %% All known elements must have a valid index and type. 'any' is prohibited - %% since it's implicit and should never be present in the map. - maps:fold(fun(Index, Element, _) when is_integer(Index), - 1 =< Index, Index =< Size, - Element =/= any, Element =/= none -> - verified_type(Element) - end, [], Es), - T; -verified_type(float=T) -> T. diff --git a/lib/compiler/src/beam_types.erl b/lib/compiler/src/beam_types.erl new file mode 100644 index 0000000000..6fcc70a4bd --- /dev/null +++ b/lib/compiler/src/beam_types.erl @@ -0,0 +1,294 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2019. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% + +-module(beam_types). + +-include("beam_types.hrl"). + +-import(lists, [foldl/3, reverse/1]). + +-export([meet/1, meet/2, join/1, join/2, subtract/2, verified_type/1]). + +-export([call_types/3]). + +%%% +%%% Type constructors +%%% + +-spec t_boolean() -> type(). +t_boolean() -> #t_atom{elements=[false,true]}. + +%%% +%%% Type operators +%%% + +%% Return the "join" of Type1 and Type2. The join is a more general +%% type than Type1 and Type2. For example: +%% +%% join(#t_integer{elements=any}, #t_integer=elements={0,3}}) -> +%% #t_integer{} +%% +%% The join for two different types result in 'any', which is +%% the top element for our type lattice: +%% +%% join(#t_integer{}, map) -> any + +-spec join(type(), type()) -> type(). + +join(T, T) -> + verified_type(T); +join(none, T) -> + verified_type(T); +join(T, none) -> + verified_type(T); +join(any, _) -> any; +join(_, any) -> any; +join(#t_atom{elements=[_|_]=Set1}, #t_atom{elements=[_|_]=Set2}) -> + Set = ordsets:union(Set1, Set2), + case ordsets:size(Set) of + Size when Size =< ?ATOM_SET_SIZE -> + #t_atom{elements=Set}; + _Size -> + #t_atom{elements=any} + end; +join(#t_atom{elements=any}=T, #t_atom{elements=[_|_]}) -> T; +join(#t_atom{elements=[_|_]}, #t_atom{elements=any}=T) -> T; +join({binary,U1}, {binary,U2}) -> + {binary,gcd(U1, U2)}; +join(#t_fun{}, #t_fun{}) -> + #t_fun{}; +join(#t_integer{elements={MinA,MaxA}}, + #t_integer{elements={MinB,MaxB}}) -> + #t_integer{elements={min(MinA,MinB),max(MaxA,MaxB)}}; +join(#t_integer{}, #t_integer{}) -> #t_integer{}; +join(list, cons) -> list; +join(cons, list) -> list; +join(nil, cons) -> list; +join(cons, nil) -> list; +join(nil, list) -> list; +join(list, nil) -> list; +join(#t_integer{}, float) -> number; +join(float, #t_integer{}) -> number; +join(#t_integer{}, number) -> number; +join(number, #t_integer{}) -> number; +join(float, number) -> number; +join(number, float) -> number; +join(#t_tuple{size=Sz,exact=ExactA,elements=EsA}, + #t_tuple{size=Sz,exact=ExactB,elements=EsB}) -> + Exact = ExactA and ExactB, + Es = join_tuple_elements(Sz, EsA, EsB), + #t_tuple{size=Sz,exact=Exact,elements=Es}; +join(#t_tuple{size=SzA,elements=EsA}, #t_tuple{size=SzB,elements=EsB}) -> + Sz = min(SzA, SzB), + Es = join_tuple_elements(Sz, EsA, EsB), + #t_tuple{size=Sz,elements=Es}; +join(_T1, _T2) -> + %%io:format("~p ~p\n", [_T1,_T2]), + any. + +join_tuple_elements(MinSize, EsA, EsB) -> + Es0 = join_elements(EsA, EsB), + maps:filter(fun(Index, _Type) -> Index =< MinSize end, Es0). + +join_elements(Es1, Es2) -> + Keys = if + map_size(Es1) =< map_size(Es2) -> maps:keys(Es1); + map_size(Es1) > map_size(Es2) -> maps:keys(Es2) + end, + join_elements_1(Keys, Es1, Es2, #{}). + +join_elements_1([Key | Keys], Es1, Es2, Acc0) -> + case {Es1, Es2} of + {#{ Key := Type1 }, #{ Key := Type2 }} -> + Acc = set_element_type(Key, join(Type1, Type2), Acc0), + join_elements_1(Keys, Es1, Es2, Acc); + {#{}, #{}} -> + join_elements_1(Keys, Es1, Es2, Acc0) + end; +join_elements_1([], _Es1, _Es2, Acc) -> + Acc. + +gcd(A, B) -> + case A rem B of + 0 -> B; + X -> gcd(B, X) + end. + +set_element_type(_Key, none, Es) -> + Es; +set_element_type(Key, any, Es) -> + maps:remove(Key, Es); +set_element_type(Key, Type, Es) -> + Es#{ Key => Type }. + +%% Subtract Type2 from Type1. Example: +%% subtract(list, cons) -> nil + +-spec subtract(type(), type()) -> type(). + +subtract(#t_atom{elements=[_|_]=Set0}, #t_atom{elements=[_|_]=Set1}) -> + case ordsets:subtract(Set0, Set1) of + [] -> none; + [_|_]=Set -> #t_atom{elements=Set} + end; +subtract(number, float) -> #t_integer{}; +subtract(number, #t_integer{elements=any}) -> float; +subtract(list, cons) -> nil; +subtract(list, nil) -> cons; +subtract(T, _) -> T. + +%% Return the "meet" of Type1 and Type2. The meet is a narrower +%% type than Type1 and Type2. For example: +%% +%% meet(#t_integer{elements=any}, #t_integer{elements={0,3}}) -> +%% #t_integer{elements={0,3}} +%% +%% The meet for two different types result in 'none', which is +%% the bottom element for our type lattice: +%% +%% meet(#t_integer{}, map) -> none + +-spec meet(type(), type()) -> type(). + +meet(T, T) -> + verified_type(T); +meet(#t_atom{elements=[_|_]=Set1}, #t_atom{elements=[_|_]=Set2}) -> + case ordsets:intersection(Set1, Set2) of + [] -> + none; + [_|_]=Set -> + #t_atom{elements=Set} + end; +meet(#t_atom{elements=[_|_]}=T, #t_atom{elements=any}) -> + T; +meet(#t_atom{elements=any}, #t_atom{elements=[_|_]}=T) -> + T; +meet(#t_fun{arity=any}, #t_fun{}=T) -> + T; +meet(#t_fun{}=T, #t_fun{arity=any}) -> + T; +meet(#t_integer{elements={_,_}}=T, #t_integer{elements=any}) -> + T; +meet(#t_integer{elements=any}, #t_integer{elements={_,_}}=T) -> + T; +meet(#t_integer{elements={MinA,MaxA}}, #t_integer{elements={MinB,MaxB}}) + when MinA >= MinB, MaxA =< MaxB; + MinB >= MinA, MaxB =< MaxA -> + #t_integer{elements={max(MinA, MinB),min(MaxA, MaxB)}}; +meet(#t_integer{}=T, number) -> T; +meet(float=T, number) -> T; +meet(number, #t_integer{}=T) -> T; +meet(number, float=T) -> T; +meet(list, cons) -> cons; +meet(list, nil) -> nil; +meet(cons, list) -> cons; +meet(nil, list) -> nil; +meet(#t_tuple{}=T1, #t_tuple{}=T2) -> + meet_tuples(T1, T2); +meet({binary,U1}, {binary,U2}) -> + {binary, U1 * U2 div gcd(U1, U2)}; +meet(any, T) -> + verified_type(T); +meet(T, any) -> + verified_type(T); +meet(_, _) -> + %% Inconsistent types. There will be an exception at runtime. + none. + +meet_tuples(#t_tuple{size=Sz1,exact=true}, + #t_tuple{size=Sz2,exact=true}) when Sz1 =/= Sz2 -> + none; +meet_tuples(#t_tuple{size=Sz1,exact=Ex1,elements=Es1}, + #t_tuple{size=Sz2,exact=Ex2,elements=Es2}) -> + Size = max(Sz1, Sz2), + Exact = Ex1 or Ex2, + case meet_elements(Es1, Es2) of + none -> + none; + Es -> + #t_tuple{size=Size,exact=Exact,elements=Es} + end. + +meet_elements(Es1, Es2) -> + Keys = maps:keys(Es1) ++ maps:keys(Es2), + meet_elements_1(Keys, Es1, Es2, #{}). + +meet_elements_1([Key | Keys], Es1, Es2, Acc) -> + case {Es1, Es2} of + {#{ Key := Type1 }, #{ Key := Type2 }} -> + case meet(Type1, Type2) of + none -> none; + Type -> meet_elements_1(Keys, Es1, Es2, Acc#{ Key => Type }) + end; + {#{ Key := Type1 }, _} -> + meet_elements_1(Keys, Es1, Es2, Acc#{ Key => Type1 }); + {_, #{ Key := Type2 }} -> + meet_elements_1(Keys, Es1, Es2, Acc#{ Key => Type2 }) + end; +meet_elements_1([], _Es1, _Es2, Acc) -> + Acc. + +%% Returns the passed in type if it is well-formed and safe to pass to +%% arbitrary code, and crashes if there's anything wrong with it. +%% +%% Currently, all types described in beam_types.hrl except for #t_bs_match{} +%% are considered safe. + +-spec verified_type(T) -> T when + T :: type(). + +verified_type(any=T) -> T; +verified_type(none=T) -> T; +verified_type(#t_atom{elements=any}=T) -> T; +verified_type(#t_atom{elements=[_|_]}=T) -> T; +verified_type({binary,U}=T) when is_integer(U) -> T; +verified_type(#t_fun{arity=Arity}=T) when Arity =:= any; is_integer(Arity) -> T; +verified_type(#t_integer{elements=any}=T) -> T; +verified_type(#t_integer{elements={Min,Max}}=T) + when is_integer(Min), is_integer(Max), Min =< Max -> T; +verified_type(list=T) -> T; +verified_type(map=T) -> T; +verified_type(nil=T) -> T; +verified_type(cons=T) -> T; +verified_type(number=T) -> T; +verified_type(#t_tuple{size=Size,elements=Es}=T) -> + %% All known elements must have a valid index and type. 'any' is prohibited + %% since it's implicit and should never be present in the map. + maps:fold(fun(Index, Element, _) when is_integer(Index), + 1 =< Index, Index =< Size, + Element =/= any, Element =/= none -> + verified_type(Element) + end, [], Es), + T; +verified_type(float=T) -> T. + +%% Joins all the given types into a single type. +-spec join([type()]) -> type(). + +join([T1,T2|Ts]) -> + join([join(T1, T2)|Ts]); +join([T]) -> T. + +%% Meets all the given types into a single type. +-spec meet([type()]) -> type(). + +meet([T1,T2|Ts]) -> + meet([meet(T1, T2)|Ts]); +meet([T]) -> T. diff --git a/lib/compiler/src/beam_types.hrl b/lib/compiler/src/beam_types.hrl new file mode 100644 index 0000000000..dfbf104a2a --- /dev/null +++ b/lib/compiler/src/beam_types.hrl @@ -0,0 +1,58 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2019. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% + +%% Common term types for passes operating on beam SSA and assembly. Helper +%% functions for wrangling these can be found in beam_types.erl +%% +%% The type lattice is as follows: +%% +%% any Any Erlang term (top element). +%% +%% - atom An atom. +%% - {binary,Unit} A bitstring aligned to unit Unit. +%% - #t_bs_match{} A match context. +%% - #t_fun{} A fun. +%% - map A map. +%% - number A number. +%% -- float Floating point number. +%% -- integer Integer. +%% - list A list. +%% -- cons Cons (nonempty list). +%% -- nil The empty list. +%% - #t_tuple{} Tuple. +%% +%% none No type (bottom element). + +-define(ATOM_SET_SIZE, 5). + +-record(t_atom, {elements=any :: 'any' | [atom()]}). +-record(t_fun, {arity=any :: arity() | 'any'}). +-record(t_integer, {elements=any :: 'any' | {integer(),integer()}}). +-record(t_bs_match, {type :: type()}). +-record(t_tuple, {size=0 :: integer(), + exact=false :: boolean(), + %% Known element types (1-based index), unknown elements are + %% are assumed to be 'any'. + elements=#{} :: #{ non_neg_integer() => type() }}). + +-type type() :: 'any' | 'none' | + #t_atom{} | #t_bs_match{} | #t_fun{} | #t_integer{} | + #t_tuple{} | {'binary',pos_integer()} | 'cons' | 'float' | + 'list' | 'map' | 'nil' | 'number'. diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl index e5e63341b7..28ab8813ba 100644 --- a/lib/compiler/src/compile.erl +++ b/lib/compiler/src/compile.erl @@ -2111,6 +2111,7 @@ pre_load() -> beam_ssa_share, beam_ssa_type, beam_trim, + beam_types, beam_utils, beam_validator, beam_z, diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src index 9dc3b6e339..22ef67f357 100644 --- a/lib/compiler/src/compiler.app.src +++ b/lib/compiler/src/compiler.app.src @@ -46,6 +46,7 @@ beam_ssa_share, beam_ssa_type, beam_trim, + beam_types, beam_utils, beam_validator, beam_z, diff --git a/lib/compiler/test/Makefile b/lib/compiler/test/Makefile index db8eb7e2e1..2c0767b17f 100644 --- a/lib/compiler/test/Makefile +++ b/lib/compiler/test/Makefile @@ -16,6 +16,7 @@ MODULES= \ beam_reorder_SUITE \ beam_ssa_SUITE \ beam_type_SUITE \ + beam_types_SUITE \ beam_utils_SUITE \ bif_SUITE \ bs_bincomp_SUITE \ @@ -225,6 +226,6 @@ release_tests_spec: make_emakefile $(INSTALL_DATA) $(ERL_DUMMY_FILES) "$(RELSYSDIR)" rm $(ERL_DUMMY_FILES) chmod -R u+w "$(RELSYSDIR)" - @tar cf - *_SUITE_data | (cd "$(RELSYSDIR)"; tar xf -) + @tar cf - *_SUITE_data property_test | (cd "$(RELSYSDIR)"; tar xf -) release_docs_spec: diff --git a/lib/compiler/test/beam_types_SUITE.erl b/lib/compiler/test/beam_types_SUITE.erl new file mode 100644 index 0000000000..66fd517ec0 --- /dev/null +++ b/lib/compiler/test/beam_types_SUITE.erl @@ -0,0 +1,80 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2019. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% + +-module(beam_types_SUITE). + +-include_lib("compiler/src/beam_types.hrl"). + +-export([all/0, suite/0, groups/0, + init_per_suite/1, end_per_suite/1]). + +-export([consistency/1, commutativity/1, + binary_consistency/1, integer_consistency/1]). + +suite() -> + [{ct_hooks,[ts_install_cth]}]. + +all() -> + [{group,property_tests}]. + +groups() -> + [{property_tests,[], [consistency, commutativity, + binary_consistency, integer_consistency]}]. + +init_per_suite(Config) -> + ct_property_test:init_per_suite(Config). + +end_per_suite(Config) -> + Config. + +consistency(Config) when is_list(Config) -> + %% manual test: proper:quickcheck(beam_types_prop:consistency()). + true = ct_property_test:quickcheck(beam_types_prop:consistency(), Config). + +commutativity(Config) when is_list(Config) -> + %% manual test: proper:quickcheck(beam_types_prop:commutativity()). + true = ct_property_test:quickcheck(beam_types_prop:commutativity(), Config). + +binary_consistency(Config) when is_list(Config) -> + %% These binaries should meet into {binary,12} as that's the best common + %% unit for both types. + A = {binary, 4}, + B = {binary, 6}, + + {binary, 12} = beam_types:meet(A, B), + {binary, 2} = beam_types:join(A, B), + + A = beam_types:meet(A, beam_types:join(A, B)), + A = beam_types:join(A, beam_types:meet(A, B)), + + ok. + +integer_consistency(Config) when is_list(Config) -> + %% Integers that don't overlap fully should never meet. + A = #t_integer{elements={3,5}}, + B = #t_integer{elements={4,6}}, + + none = beam_types:meet(A, B), + #t_integer{elements={3,6}} = beam_types:join(A, B), + + A = beam_types:meet(A, beam_types:join(A, B)), + A = beam_types:join(A, beam_types:meet(A, B)), + + ok. diff --git a/lib/compiler/test/property_test/beam_types_prop.erl b/lib/compiler/test/property_test/beam_types_prop.erl new file mode 100644 index 0000000000..815e353853 --- /dev/null +++ b/lib/compiler/test/property_test/beam_types_prop.erl @@ -0,0 +1,140 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2019. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% + +-module(beam_types_prop). + +-compile([export_all, nowarn_export_all]). + +%% This module has only supports proper, as we don't have an eqc license to +%% test with. + +-proptest([proper]). + +-ifdef(PROPER). + +-include_lib("compiler/src/beam_types.hrl"). + +-include_lib("proper/include/proper.hrl"). +-define(MOD_eqc,proper). + +consistency() -> + ?FORALL({TypeA, TypeB}, + ?LET(TypeA, type(), + ?LET(TypeB, type(), {TypeA, TypeB})), + consistency_check(TypeA, TypeB)). + +consistency_check(A, B) -> + consistency_check_1(A, B), + consistency_check_1(B, A), + true. + +consistency_check_1(A, B) -> + A = beam_types:meet(A, beam_types:join(A, B)), + A = beam_types:join(A, beam_types:meet(A, B)), + ok. + +commutativity() -> + ?FORALL({TypeA, TypeB}, + ?LET(TypeA, type(), + ?LET(TypeB, type(), {TypeA, TypeB})), + commutativity_check(TypeA, TypeB)). + +commutativity_check(A, B) -> + true = beam_types:meet(A, B) =:= beam_types:meet(B, A), + true = beam_types:join(A, B) =:= beam_types:join(B, A), + true. + +%%% +%%% Generators +%%% + +type() -> + type(0). + +type(Depth) -> + oneof(nested_types(Depth) ++ + numerical_types() ++ + list_types() ++ + other_types()). + +other_types() -> + [any, gen_atom(), gen_binary(), none]. + +list_types() -> + [cons, list, nil]. + +numerical_types() -> + [gen_integer(), float, number]. + +nested_types(Depth) when Depth >= 3 -> []; +nested_types(Depth) -> [map, gen_tuple(Depth + 1)]. + +gen_atom() -> + ?LET(Size, range(0, ?ATOM_SET_SIZE), + case Size of + 0 -> + #t_atom{}; + _ -> + ?LET(Set, sized_list(Size, atom()), + begin + #t_atom{elements=ordsets:from_list(Set)} + end) + end). + +gen_binary() -> + ?SHRINK({binary, range(1, 128)}, + [{binary, [1, 2, 3, 5, 7, 8, 16, 32, 64]}]). + +gen_integer() -> + oneof([gen_integer_bounded(), #t_integer{}]). + +gen_integer_bounded() -> + ?LET(A, integer(), + ?LET(B, integer(), + begin + #t_integer{elements={min(A,B), max(A,B)}} + end)). + +gen_tuple(Depth) -> + ?SIZED(Size, + ?LET(Exact, oneof([true, false]), + ?LET(Elements, gen_tuple_elements(Size, Depth), + begin + #t_tuple{exact=Exact, + size=Size, + elements=Elements} + end))). + +gen_tuple_elements(Size, Depth) -> + ?LET(Types, sized_list(rand:uniform(Size div 4 + 1), gen_element(Depth)), + maps:from_list([{rand:uniform(Size), T} || T <- Types])). + +gen_element(Depth) -> + ?LAZY(?SUCHTHAT(Type, type(Depth), + case Type of + any -> false; + none -> false; + _ -> true + end)). + +sized_list(0, _Gen) -> []; +sized_list(N, Gen) -> [Gen | sized_list(N - 1, Gen)]. + +-endif. -- cgit v1.2.3 From 9cfcddacc961301733619d998833e0fe345966e7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Fri, 24 May 2019 15:26:53 +0200 Subject: compiler: Move "known functions" to beam_types --- lib/compiler/src/Makefile | 2 + lib/compiler/src/beam_call_types.erl | 466 ++++++++++++++ lib/compiler/src/beam_ssa_type.erl | 679 +++++---------------- lib/compiler/src/beam_types.erl | 202 ++++-- lib/compiler/src/beam_types.hrl | 41 +- lib/compiler/src/compile.erl | 1 + lib/compiler/src/compiler.app.src | 1 + lib/compiler/test/beam_types_SUITE.erl | 8 +- .../test/property_test/beam_types_prop.erl | 6 +- 9 files changed, 809 insertions(+), 597 deletions(-) create mode 100644 lib/compiler/src/beam_call_types.erl diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile index 89feb35bc2..f253f31d13 100644 --- a/lib/compiler/src/Makefile +++ b/lib/compiler/src/Makefile @@ -49,6 +49,7 @@ MODULES = \ beam_a \ beam_asm \ beam_block \ + beam_call_types \ beam_clean \ beam_dict \ beam_disasm \ @@ -191,6 +192,7 @@ release_docs_spec: # Dependencies -- alphabetically, please # ---------------------------------------------------- +$(EBIN)/beam_call_types.beam: beam_types.hrl $(EBIN)/beam_disasm.beam: $(EGEN)/beam_opcodes.hrl beam_disasm.hrl $(EBIN)/beam_listing.beam: core_parse.hrl v3_kernel.hrl beam_ssa.hrl $(EBIN)/beam_kernel_to_ssa.beam: v3_kernel.hrl beam_ssa.hrl diff --git a/lib/compiler/src/beam_call_types.erl b/lib/compiler/src/beam_call_types.erl new file mode 100644 index 0000000000..45fbead804 --- /dev/null +++ b/lib/compiler/src/beam_call_types.erl @@ -0,0 +1,466 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2019. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% + +-module(beam_call_types). + +-include("beam_types.hrl"). + +-import(lists, [duplicate/2,foldl/3]). + +-export([types/3]). + +%% +%% Returns the inferred return and argument types for known functions, and +%% whether it's safe to subtract argument types on failure. +%% +%% Note that the return type will be 'none' if we can statically determine that +%% the function will fail at runtime. +%% + +-spec types(Mod, Func, ArgTypes) -> {RetType, ArgTypes, CanSubtract} when + Mod :: atom(), + Func :: atom(), + ArgTypes :: [type()], + RetType :: type(), + CanSubtract :: boolean(). + +%% Functions that only fail due to bad argument *types*, meaning it's safe to +%% subtract argument types on failure. +%% +%% Note that these are all from the erlang module; suitable functions in other +%% modules could fail due to the module not being loaded. +types(erlang, 'map_size', [_]) -> + sub_safe(#t_integer{}, [#t_map{}]); +types(erlang, 'tuple_size', [_]) -> + sub_safe(#t_integer{}, [#t_tuple{}]); +types(erlang, 'bit_size', [_]) -> + sub_safe(#t_integer{}, [#t_bitstring{}]); +types(erlang, 'byte_size', [_]) -> + sub_safe(#t_integer{}, [#t_bitstring{}]); +types(erlang, 'hd', [_]) -> + sub_safe(any, [cons]); +types(erlang, 'tl', [_]) -> + sub_safe(any, [cons]); +types(erlang, 'length', [_]) -> + sub_safe(#t_integer{}, [list]); +types(erlang, 'not', [_]) -> + Bool = beam_types:make_boolean(), + sub_safe(Bool, [Bool]); + +%% Boolean ops +types(erlang, 'and', [_,_]) -> + Bool = beam_types:make_boolean(), + sub_unsafe(Bool, [Bool, Bool]); +types(erlang, 'or', [_,_]) -> + Bool = beam_types:make_boolean(), + sub_unsafe(Bool, [Bool, Bool]); +types(erlang, 'xor', [_,_]) -> + Bool = beam_types:make_boolean(), + sub_unsafe(Bool, [Bool, Bool]); + +%% Bitwise ops +types(erlang, 'band', [_,_]=Args) -> + sub_unsafe(band_return_type(Args), [#t_integer{}, #t_integer{}]); +types(erlang, 'bor', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); +types(erlang, 'bxor', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); +types(erlang, 'bsl', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); +types(erlang, 'bsr', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); +types(erlang, 'bnot', [_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}]); + +%% Fixed-type arithmetic +types(erlang, 'float', [_]) -> + sub_unsafe(float, [number]); +types(erlang, 'round', [_]) -> + sub_unsafe(#t_integer{}, [number]); +types(erlang, 'floor', [_]) -> + sub_unsafe(#t_integer{}, [number]); +types(erlang, 'ceil', [_]) -> + sub_unsafe(#t_integer{}, [number]); +types(erlang, 'trunc', [_]) -> + sub_unsafe(#t_integer{}, [number]); +types(erlang, '/', [_,_]) -> + sub_unsafe(float, [number, number]); +types(erlang, 'div', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); +types(erlang, 'rem', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); + +%% Mixed-type arithmetic; '+'/2 and friends are handled in the catch-all +%% clause for the 'erlang' module. +types(erlang, 'abs', [_]=Args) -> + mixed_arith_types(Args); + +%% List operations +types(erlang, '++', [LHS,RHS]) -> + %% `[] ++ RHS` yields RHS, even if RHS is not a list. + RetType = case {LHS, RHS} of + {cons, _} -> cons; + {_, cons} -> cons; + _ -> beam_types:join(list, RHS) + end, + sub_unsafe(RetType, [list, any]); +types(erlang, '--', [_,_]) -> + sub_unsafe(list, [list, list]); + +%% Misc ops. +types(erlang, 'binary_part', [_, _]) -> + PosLen = make_two_tuple(#t_integer{}, #t_integer{}), + Binary = #t_bitstring{unit=8}, + sub_unsafe(Binary, [Binary, PosLen]); +types(erlang, 'binary_part', [_, _, _]) -> + Binary = #t_bitstring{unit=8}, + sub_unsafe(Binary, [Binary, #t_integer{}, #t_integer{}]); +types(erlang, 'is_map_key', [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [any,#t_map{}]); +types(erlang, 'map_get', [_,_]) -> + sub_unsafe(any, [any,#t_map{}]); +types(erlang, 'node', [_]) -> + sub_unsafe(#t_atom{}, [any]); +types(erlang, 'node', []) -> + sub_unsafe(#t_atom{}, []); +types(erlang, 'size', [_]) -> + sub_unsafe(#t_integer{}, [any]); +types(erlang, 'size', [_]) -> + sub_unsafe(#t_integer{}, [any]); + +%% Tuple element ops +types(erlang, element, [PosType, TupleType]) -> + Index = case PosType of + #t_integer{elements={Same,Same}} when is_integer(Same) -> + Same; + _ -> + 0 + end, + + RetType = case TupleType of + #t_tuple{size=Sz,elements=Es} when Index =< Sz, + Index >= 1 -> + beam_types:get_element_type(Index, Es); + _ -> + any + end, + + sub_unsafe(RetType, [#t_integer{}, #t_tuple{size=Index}]); +types(erlang, setelement, [PosType, TupleType, ArgType]) -> + RetType = case {PosType,TupleType} of + {#t_integer{elements={Index,Index}}, + #t_tuple{elements=Es0,size=Size}=T} -> + %% This is an exact index, update the type of said + %% element or return 'none' if it's known to be out of + %% bounds. + Es = beam_types:set_element_type(Index, ArgType, Es0), + case T#t_tuple.exact of + false -> + T#t_tuple{size=max(Index, Size),elements=Es}; + true when Index =< Size -> + T#t_tuple{elements=Es}; + true -> + none + end; + {#t_integer{elements={Min,Max}}, + #t_tuple{elements=Es0,size=Size}=T} -> + %% We know this will land between Min and Max, so kill + %% the types for those indexes. + Es = discard_tuple_element_info(Min, Max, Es0), + case T#t_tuple.exact of + false -> + T#t_tuple{elements=Es,size=max(Min, Size)}; + true when Min =< Size -> + T#t_tuple{elements=Es,size=Size}; + true -> + none + end; + {_,#t_tuple{}=T} -> + %% Position unknown, so we have to discard all element + %% information. + T#t_tuple{elements=#{}}; + {#t_integer{elements={Min,_Max}},_} -> + #t_tuple{size=Min}; + {_,_} -> + #t_tuple{} + end, + sub_unsafe(RetType, [#t_integer{}, #t_tuple{}, any]); + +types(erlang, make_fun, [_,_,Arity0]) -> + Type = case Arity0 of + #t_integer{elements={Arity,Arity}} when Arity >= 0 -> + #t_fun{arity=Arity}; + _ -> + #t_fun{} + end, + sub_unsafe(Type, [#t_atom{}, #t_atom{}, #t_integer{}]); + +types(erlang, Name, Args) -> + Arity = length(Args), + + case erl_bifs:is_exit_bif(erlang, Name, Arity) of + true -> + {none, Args, false}; + false -> + case erl_internal:arith_op(Name, Arity) of + true -> + mixed_arith_types(Args); + false -> + IsTest = + erl_internal:new_type_test(Name, Arity) orelse + erl_internal:comp_op(Name, Arity), + + RetType = case IsTest of + true -> beam_types:make_boolean(); + false -> any + end, + + sub_unsafe(RetType, duplicate(Arity, any)) + end + end; + +%% +%% Math BIFs +%% + +types(math, cos, [_]) -> + sub_unsafe(float, [number]); +types(math, cosh, [_]) -> + sub_unsafe(float, [number]); +types(math, sin, [_]) -> + sub_unsafe(float, [number]); +types(math, sinh, [_]) -> + sub_unsafe(float, [number]); +types(math, tan, [_]) -> + sub_unsafe(float, [number]); +types(math, tanh, [_]) -> + sub_unsafe(float, [number]); +types(math, acos, [_]) -> + sub_unsafe(float, [number]); +types(math, acosh, [_]) -> + sub_unsafe(float, [number]); +types(math, asin, [_]) -> + sub_unsafe(float, [number]); +types(math, asinh, [_]) -> + sub_unsafe(float, [number]); +types(math, atan, [_]) -> + sub_unsafe(float, [number]); +types(math, atanh, [_]) -> + sub_unsafe(float, [number]); +types(math, erf, [_]) -> + sub_unsafe(float, [number]); +types(math, erfc, [_]) -> + sub_unsafe(float, [number]); +types(math, exp, [_]) -> + sub_unsafe(float, [number]); +types(math, log, [_]) -> + sub_unsafe(float, [number]); +types(math, log2, [_]) -> + sub_unsafe(float, [number]); +types(math, log10, [_]) -> + sub_unsafe(float, [number]); +types(math, sqrt, [_]) -> + sub_unsafe(float, [number]); +types(math, atan2, [_,_]) -> + sub_unsafe(float, [number, number]); +types(math, pow, [_,_]) -> + sub_unsafe(float, [number, number]); +types(math, ceil, [_]) -> + sub_unsafe(float, [number]); +types(math, floor, [_]) -> + sub_unsafe(float, [number]); +types(math, fmod, [_,_]) -> + sub_unsafe(float, [number, number]); +types(math, pi, []) -> + sub_unsafe(float, []); + +%% +%% List functions +%% + +%% Operator aliases. +types(lists, append, [_,_]=Args) -> + types(erlang, '++', Args); +types(lists, append, [_]) -> + %% This is implemented through folding the list over erlang:'++'/2, so it + %% can hypothetically return anything, but we can infer that its argument + %% is a list on success. + sub_unsafe(any, [list]); +types(lists, subtract, [_,_]) -> + sub_unsafe(list, [list, list]); + +%% Functions returning booleans. +types(lists, all, [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [#t_fun{arity=1}, list]); +types(lists, any, [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [#t_fun{arity=1}, list]); +types(lists, keymember, [_,_,_]) -> + sub_unsafe(beam_types:make_boolean(), [any, #t_integer{}, list]); +types(lists, member, [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [any, list]); +types(lists, prefix, [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [list, list]); +types(lists, suffix, [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [list, list]); + +%% Functions returning plain lists. +types(lists, dropwhile, [_,_]) -> + sub_unsafe(list, [#t_fun{arity=1}, list]); +types(lists, duplicate, [_,_]) -> + sub_unsafe(list, [#t_integer{}, any]); +types(lists, filter, [_,_]) -> + sub_unsafe(list, [#t_fun{arity=1}, list]); +types(lists, flatten, [_]) -> + sub_unsafe(list, [list]); +types(lists, map, [_Fun, List]) -> + sub_unsafe(same_length_type(List), [#t_fun{arity=1}, list]); +types(lists, reverse, [List]) -> + sub_unsafe(same_length_type(List), [list]); +types(lists, sort, [List]) -> + sub_unsafe(same_length_type(List), [list]); +types(lists, takewhile, [_,_]) -> + sub_unsafe(list, [#t_fun{arity=1}, list]); +types(lists, usort, [List]) -> + sub_unsafe(same_length_type(List), [list]); +types(lists, zip, [A,B]) -> + RetType = beam_types:join(same_length_type(A), same_length_type(B)), + sub_unsafe(RetType, [list, list]); +types(lists, zipwith, [_,A,B]) -> + RetType = beam_types:join(same_length_type(A), same_length_type(B)), + sub_unsafe(RetType, [#t_fun{arity=2}, list, list]); +types(lists, zipwith3, [_,A,B,C]) -> + RetType = beam_types:join([same_length_type(A), + same_length_type(B), + same_length_type(C)]), + sub_unsafe(RetType, [#t_fun{arity=3}, list, list, list]); + +%% Functions with complex return values. +types(lists, partition, [_,_]) -> + sub_unsafe(make_two_tuple(list, list), [#t_fun{arity=1}, list]); +types(lists, MapFold, [_Fun, _Init, List]) + when MapFold =:= mapfoldl; MapFold =:= mapfoldr -> + ListType = same_length_type(List), + RetType = #t_tuple{size=2, + exact=true, + elements=#{ 1 => ListType }}, + sub_unsafe(RetType, [#t_fun{arity=2}, any, list]); +types(lists, splitwith, [_,_]) -> + sub_unsafe(make_two_tuple(list, list), [#t_fun{arity=1}, list]); +types(lists, unzip, [List]) -> + ListType = same_length_type(List), + RetType = make_two_tuple(ListType, ListType), + sub_unsafe(RetType, [list]); + +%% Catch-all clause for unknown functions. + +types(_, _, Args) -> + sub_unsafe(any, [any || _ <- Args]). + +%% +%% Helpers +%% + +sub_unsafe(none, ArgTypes) -> + %% This is known to fail at runtime, but the type optimization pass + %% doesn't yet support cutting a block short at any point, so we + %% pretend it's raining instead. + %% + %% Actual exit BIFs get special treatment in the catch-all clause + %% for the 'erlang' module. + sub_unsafe(any, ArgTypes); +sub_unsafe(RetType, ArgTypes) -> + {RetType, ArgTypes, false}. + +sub_safe(RetType, ArgTypes) -> + {RetType, ArgTypes, true}. + +mixed_arith_types([FirstType | _]=Args0) -> + RetType = foldl(fun(#t_integer{}, #t_integer{}) -> #t_integer{}; + (#t_integer{}, number) -> number; + (#t_integer{}, float) -> float; + (float, #t_integer{}) -> float; + (float, number) -> float; + (float, float) -> float; + (number, #t_integer{}) -> number; + (number, float) -> float; + (number, number) -> number; + (any, _) -> number; + (_, _) -> none + end, FirstType, Args0), + sub_unsafe(RetType, [number || _ <- Args0]). + +band_return_type([#t_integer{elements={Int,Int}}, RHS]) when is_integer(Int) -> + band_return_type_1(RHS, Int); +band_return_type([LHS, #t_integer{elements={Int,Int}}]) when is_integer(Int) -> + band_return_type_1(LHS, Int); +band_return_type(_) -> + #t_integer{}. + +band_return_type_1(LHS, Int) -> + case LHS of + #t_integer{elements={Min0,Max0}} when Max0 - Min0 < 1 bsl 256 -> + {Intersection, Union} = range_masks(Min0, Max0), + + Min = Intersection band Int, + Max = min(Max0, Union band Int), + + #t_integer{elements={Min,Max}}; + _ when Int >= 0 -> + %% The range is either unknown or too wide, conservatively assume + %% that the new range is 0 .. Int. + #t_integer{elements={0,Int}}; + _ when Int < 0 -> + %% We can't infer boundaries when the range is unknown and the + %% other operand is a negative number, as the latter sign-extends + %% to infinity and we can't express an inverted range at the + %% moment (cf. X band -8; either less than -7 or greater than 7). + #t_integer{} + end. + +%% Returns two bitmasks describing all possible values between From and To. +%% +%% The first contains the bits that are common to all values, and the second +%% contains the bits that are set by any value in the range. +range_masks(From, To) when From =< To -> + range_masks_1(From, To, 0, -1, 0). + +range_masks_1(From, To, BitPos, Intersection, Union) when From < To -> + range_masks_1(From + (1 bsl BitPos), To, BitPos + 1, + Intersection band From, Union bor From); +range_masks_1(_From, To, _BitPos, Intersection0, Union0) -> + Intersection = To band Intersection0, + Union = To bor Union0, + {Intersection, Union}. + +discard_tuple_element_info(Min, Max, Es) -> + foldl(fun(El, Acc) when Min =< El, El =< Max -> + maps:remove(El, Acc); + (_El, Acc) -> Acc + end, Es, maps:keys(Es)). + +%% 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. + +make_two_tuple(Type1, Type2) -> + #t_tuple{size=2,exact=true, + elements=#{1=>Type1,2=>Type2}}. diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 6d697787c0..99dec0d84f 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -26,9 +26,9 @@ -import(lists, [all/2,any/2,droplast/1,foldl/3,last/1,member/2, keyfind/3,reverse/1,reverse/2, - sort/1,split/2]). + sort/1,split/2,zip/2]). --define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}). +-define(UNICODE_MAX, (16#10FFFF)). -record(d, {ds :: #{beam_ssa:b_var():=beam_ssa:b_set()}, @@ -172,12 +172,16 @@ validator_anno(#t_integer{elements={Same,Same}}) -> beam_validator:type_anno(integer, Same); validator_anno(#t_integer{}) -> beam_validator:type_anno(integer); +validator_anno(#t_bitstring{unit=U}) -> + beam_validator:type_anno({binary,U}); validator_anno(float) -> beam_validator:type_anno(float); +validator_anno(#t_map{}) -> + beam_validator:type_anno(map); validator_anno(#t_atom{elements=[Val]}) -> beam_validator:type_anno(atom, Val); validator_anno(#t_atom{}=A) -> - case t_is_boolean(A) of + case beam_types:is_boolean_type(A) of true -> beam_validator:type_anno(bool); false -> beam_validator:type_anno(atom) end; @@ -317,11 +321,11 @@ opt_is([#b_set{op=succeeded,args=[Arg],dst=Dst}=I], #{} -> Args = simplify_args([Arg], Sub0, Ts0), Type = type(succeeded, Args, Ts0, Ds0), - case get_literal_from_type(Type) of - #b_literal{}=Lit -> - Sub = Sub0#{Dst=>Lit}, + case beam_types:get_singleton_value(Type) of + {ok, Lit} -> + Sub = Sub0#{Dst=>#b_literal{val=Lit}}, opt_is([], Ts0, Ds0, Fdb, D, Sub, Acc); - none -> + error -> Ts = Ts0#{Dst=>Type}, Ds = Ds0#{Dst=>I}, opt_is([], Ts, Ds, Fdb, D, Sub0, [I|Acc]) @@ -364,7 +368,7 @@ simplify_call(#b_set{op=call,args=[#b_remote{}=Rem|Args]}=I) -> false -> I end; - #b_remote{} -> + #b_remote{} -> I end; simplify_call(I) -> I. @@ -457,7 +461,7 @@ update_arg_types([Arg | Args], [TypeMap0 | TypeMaps], CallId, Ts) -> %% Match contexts are treated as bitstrings when optimizing arguments, as %% we don't yet support removing the "bs_start_match3" instruction. NewType = case get_type(Arg, Ts) of - #t_bs_match{} -> {binary, 1}; + #t_bs_context{} -> #t_bitstring{unit=1}; Type -> Type end, TypeMap = TypeMap0#{ CallId => NewType }, @@ -488,7 +492,7 @@ simplify(#b_set{op={bif,'or'},args=Args}=I, Ts) -> I end; simplify(#b_set{op={bif,element},args=[#b_literal{val=Index},Tuple]}=I0, Ts) -> - case t_tuple_size(get_type(Tuple, Ts)) of + case beam_types:get_tuple_size(get_type(Tuple, Ts)) of {_,Size} when is_integer(Index), 1 =< Index, Index =< Size -> I = I0#b_set{op=get_tuple_element, args=[Tuple,#b_literal{val=Index-1}]}, @@ -542,7 +546,7 @@ simplify(#b_set{op={bif,Op0},args=Args}=I, Ts) when Op0 =:= '=='; Op0 =:= '/=' - {none,any} -> true; {#t_integer{},#t_integer{}} -> true; {float,float} -> true; - {{binary,_},_} -> true; + {#t_bitstring{},_} -> true; {#t_atom{},_} -> true; {_,_} -> false end, @@ -565,7 +569,7 @@ simplify(#b_set{op={bif,'=:='},args=[A1,_A2]=Args}=I, Ts) -> none -> #b_literal{val=false}; _ -> - case {t_is_boolean(T1),T2} of + case {beam_types:is_boolean_type(T1),T2} of {true,#t_atom{elements=[true]}} -> %% Bool =:= true ==> Bool A1; @@ -596,10 +600,10 @@ simplify(#b_set{op={bif,Op},args=Args}=I, Ts) -> simplify(#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=N}]}=I, Ts) -> case get_type(Tuple, Ts) of #t_tuple{size=Size,elements=Es} when Size > N -> - ElemType = get_element_type(N + 1, Es), - case get_literal_from_type(ElemType) of - #b_literal{}=Lit -> Lit; - none -> I + ElemType = beam_types:get_element_type(N + 1, Es), + case beam_types:get_singleton_value(ElemType) of + {ok, Val} -> #b_literal{val=Val}; + error -> I end; none -> %% Will never be executed because of type conflict. @@ -655,7 +659,7 @@ is_non_numeric_tuple(Tuple, El) when El >= 1 -> is_non_numeric_tuple(_Tuple, 0) -> true. is_non_numeric_type(#t_atom{}) -> true; -is_non_numeric_type({binary,_}) -> true; +is_non_numeric_type(#t_bitstring{}) -> true; is_non_numeric_type(nil) -> true; is_non_numeric_type(#t_tuple{size=Size,exact=true,elements=Types}) when map_size(Types) =:= Size -> @@ -680,7 +684,7 @@ make_literal_list([], Acc) -> is_safe_bool_op(Args, Ts) -> [T1,T2] = get_types(Args, Ts), - t_is_boolean(T1) andalso t_is_boolean(T2). + beam_types:is_boolean_type(T1) andalso beam_types:is_boolean_type(T2). all_same([{H,_}|T]) -> all(fun({E,_}) -> E =:= H end, T). @@ -727,9 +731,9 @@ simplify_arg(#b_var{}=Arg0, Sub, Ts) -> LitArg; #b_var{}=Arg -> Type = get_type(Arg, Ts), - case get_literal_from_type(Type) of - none -> Arg; - #b_literal{}=Lit -> Lit + case beam_types:get_singleton_value(Type) of + {ok, Val} -> #b_literal{val=Val}; + error -> Arg end end; simplify_arg(#b_remote{mod=Mod,name=Name}=Rem, Sub, Ts) -> @@ -784,7 +788,7 @@ opt_switch(#b_switch{fail=Fail,list=List0}=Sw0, Type, Ts, Ds) -> #t_integer{elements={_,_}=Range} -> simplify_switch_int(Sw1, Range); #t_atom{elements=[_|_]} -> - case t_is_boolean(Type) of + case beam_types:is_boolean_type(Type) of true -> #b_br{} = Br = simplify_switch_bool(Sw1, Ts, Ds), opt_terminator(Br, Ts, Ds); @@ -872,9 +876,9 @@ sub_sw_list_1(Type, [], _Ts) -> Type. update_successor_bool(#b_var{}=Var, BoolValue, S, Ts, D) -> - case t_is_boolean(get_type(Var, Ts)) of + case beam_types:is_boolean_type(get_type(Var, Ts)) of true -> - update_successor(S, Ts#{Var:=t_atom(BoolValue)}, D); + update_successor(S, Ts#{ Var := beam_types:make_atom(BoolValue) }, D); false -> %% The `br` terminator is preceeded by an instruction that %% does not produce a boolean value, such a `new_try_tag`. @@ -902,117 +906,42 @@ update_types(#b_set{op=Op,dst=Dst,args=Args}, Ts, Ds) -> type(phi, Args, Ts, _Ds) -> Types = [get_type(A, Ts) || {A,_} <- Args], beam_types:join(Types); -type({bif,'band'}, Args, Ts, _Ds) -> - band_type(Args, Ts); type({bif,Bif}, Args, Ts, _Ds) -> - case bif_type(Bif, Args) of - number -> - arith_op_type(Args, Ts); - Type -> - Type - end; + {RetType, _, _} = beam_call_types:types(erlang, Bif, get_types(Args, Ts)), + RetType; type(bs_init, _Args, _Ts, _Ds) -> - {binary, 1}; -type(bs_extract, [Ctx], Ts, _Ds) -> - #t_bs_match{type=Type} = get_type(Ctx, Ts), - Type; -type(bs_match, Args, _Ts, _Ds) -> - #t_bs_match{type=bs_match_type(Args)}; + #t_bitstring{}; +type(bs_extract, [Ctx], _Ts, Ds) -> + #b_set{op=bs_match,args=Args} = map_get(Ctx, Ds), + bs_match_type(Args); +type(bs_match, _Args, _Ts, _Ds) -> + #t_bs_context{}; type(bs_get_tail, _Args, _Ts, _Ds) -> - {binary, 1}; + #t_bitstring{}; type(call, [#b_remote{mod=#b_literal{val=Mod}, name=#b_literal{val=Name}}|Args], Ts, _Ds) -> - case {Mod,Name,Args} of - {erlang,make_fun,[_,_,Arity0]} -> - case Arity0 of - #b_literal{val=Arity} when is_integer(Arity), Arity >= 0 -> - #t_fun{arity=Arity}; - _ -> - #t_fun{} - end; - {erlang,setelement,[Pos,Tuple,Arg]} -> - case {get_type(Pos, Ts),get_type(Tuple, Ts)} of - {#t_integer{elements={Index,Index}}, - #t_tuple{elements=Es0,size=Size}=T} -> - %% This is an exact index, update the type of said element - %% or return 'none' if it's known to be out of bounds. - Es = set_element_type(Index, get_type(Arg, Ts), Es0), - case T#t_tuple.exact of - false -> - T#t_tuple{size=max(Index, Size),elements=Es}; - true when Index =< Size -> - T#t_tuple{elements=Es}; - true -> - none - end; - {#t_integer{elements={Min,_}}=IntType, - #t_tuple{elements=Es0,size=Size}=T} -> - %% Remove type information for all indices that - %% falls into the range of the integer. - Es = remove_element_info(IntType, Es0), - case T#t_tuple.exact of - false -> - T#t_tuple{elements=Es,size=max(Min, Size)}; - true when Min =< Size -> - T#t_tuple{elements=Es,size=Size}; - true -> - none - end; - {_,#t_tuple{}=T} -> - %% Position unknown, so we have to discard all element - %% information. - T#t_tuple{elements=#{}}; - {#t_integer{elements={Min,_Max}},_} -> - #t_tuple{size=Min}; - {_,_} -> - #t_tuple{} - end; - {erlang,'++',[LHS,RHS]} -> - LType = get_type(LHS, Ts), - RType = get_type(RHS, Ts), - case LType =:= cons orelse RType =:= cons of - true -> - cons; - false -> - %% `[] ++ RHS` yields RHS, even if RHS is not a list. - join(list, RType) - 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; - true -> float - end; - {_,_,_} -> - case erl_bifs:is_exit_bif(Mod, Name, length(Args)) of - true -> none; - false -> any - end - end; + {RetType, _, _} = beam_call_types:types(Mod, Name, get_types(Args, Ts)), + RetType; type(get_tuple_element, [Tuple, Offset], Ts, _Ds) -> #t_tuple{size=Size,elements=Es} = get_type(Tuple, Ts), #b_literal{val=N} = Offset, true = Size > N, %Assertion. - get_element_type(N + 1, Es); + beam_types:get_element_type(N + 1, Es); type(is_nonempty_list, [_], _Ts, _Ds) -> - t_boolean(); + beam_types:make_boolean(); type(is_tagged_tuple, [_,#b_literal{},#b_literal{}], _Ts, _Ds) -> - t_boolean(); + beam_types:make_boolean(); type(make_fun, [#b_local{arity=TotalArity}|Env], _Ts, _Ds) -> #t_fun{arity=TotalArity-length(Env)}; type(put_map, _Args, _Ts, _Ds) -> - map; + #t_map{}; type(put_list, _Args, _Ts, _Ds) -> cons; type(put_tuple, Args, Ts, _Ds) -> {Es, _} = foldl(fun(Arg, {Es0, Index}) -> - Type = get_type(Arg, Ts), - Es = set_element_type(Index, Type, Es0), - {Es, Index + 1} + Type = get_type(Arg, Ts), + Es = beam_types:set_element_type(Index, Type, Es0), + {Es, Index + 1} end, {#{}, 1}, Args), #t_tuple{exact=true,size=length(Args),elements=Es}; type(succeeded, [#b_var{}=Src], Ts, Ds) -> @@ -1021,124 +950,45 @@ type(succeeded, [#b_var{}=Src], Ts, Ds) -> Types = get_types(BifArgs, Ts), case {Bif,Types} of {BoolOp,[T1,T2]} when BoolOp =:= 'and'; BoolOp =:= 'or' -> - case t_is_boolean(T1) andalso t_is_boolean(T2) of - true -> t_atom(true); - false -> t_boolean() + BothBool = beam_types:is_boolean_type(T1) andalso + beam_types:is_boolean_type(T2), + case BothBool of + true -> beam_types:make_atom(true); + false -> beam_types:make_boolean() end; - {byte_size,[{binary,_}]} -> - t_atom(true); - {bit_size,[{binary,_}]} -> - t_atom(true); - {map_size,[map]} -> - t_atom(true); + {byte_size,[#t_bitstring{}]} -> + beam_types:make_atom(true); + {bit_size,[#t_bitstring{}]} -> + beam_types:make_atom(true); + {map_size,[#t_map{}]} -> + beam_types:make_atom(true); {'not',[Type]} -> - case t_is_boolean(Type) of - true -> t_atom(true); - false -> t_boolean() + case beam_types:is_boolean_type(Type) of + true -> beam_types:make_atom(true); + false -> beam_types:make_boolean() end; - {size,[{binary,_}]} -> - t_atom(true); + {size,[#t_bitstring{}]} -> + beam_types:make_atom(true); {tuple_size,[#t_tuple{}]} -> - t_atom(true); + beam_types:make_atom(true); {_,_} -> - t_boolean() + beam_types:make_boolean() end; #b_set{op=get_hd} -> - t_atom(true); + beam_types:make_atom(true); #b_set{op=get_tl} -> - t_atom(true); + beam_types:make_atom(true); #b_set{op=get_tuple_element} -> - t_atom(true); + beam_types:make_atom(true); #b_set{op=wait} -> - t_atom(false); + beam_types:make_atom(false); #b_set{} -> - t_boolean() + beam_types:make_boolean() end; type(succeeded, [#b_literal{}], _Ts, _Ds) -> - t_atom(true); + beam_types:make_atom(true); type(_, _, _, _) -> any. -arith_op_type(Args, Ts) -> - Types = get_types(Args, Ts), - foldl(fun(#t_integer{}, unknown) -> t_integer(); - (#t_integer{}, number) -> number; - (#t_integer{}, float) -> float; - (#t_integer{}, #t_integer{}) -> t_integer(); - (float, unknown) -> float; - (float, #t_integer{}) -> float; - (float, number) -> float; - (number, unknown) -> number; - (number, #t_integer{}) -> number; - (number, float) -> float; - (any, _) -> number; - (Same, Same) -> Same; - (_, _) -> 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. @@ -1153,13 +1003,13 @@ will_succeed(is_atom, Type) -> end; will_succeed(is_binary, Type) -> case Type of - {binary,U} when U rem 8 =:= 0 -> yes; - {binary,_} -> maybe; + #t_bitstring{unit=U} when U rem 8 =:= 0 -> yes; + #t_bitstring{} -> maybe; _ -> no end; will_succeed(is_bitstring, Type) -> case Type of - {binary,_} -> yes; + #t_bitstring{} -> yes; _ -> no end; will_succeed(is_boolean, Type) -> @@ -1167,7 +1017,7 @@ will_succeed(is_boolean, Type) -> #t_atom{elements=any} -> maybe; #t_atom{elements=Es} -> - case t_is_boolean(Type) of + case beam_types:is_boolean_type(Type) of true -> yes; false -> @@ -1204,7 +1054,7 @@ will_succeed(is_list, Type) -> end; will_succeed(is_map, Type) -> case Type of - map -> yes; + #t_map{} -> yes; _ -> no end; will_succeed(is_number, Type) -> @@ -1221,54 +1071,12 @@ will_succeed(is_tuple, Type) -> end; will_succeed(_, _) -> maybe. - -band_type([Other,#b_literal{val=Int}], Ts) when is_integer(Int) -> - band_type_1(Int, Other, Ts); -band_type([_,_], _) -> t_integer(). - -band_type_1(Int, OtherSrc, Ts) -> - OtherType = get_type(OtherSrc, Ts), - case OtherType of - #t_integer{elements={Min0,Max0}} when Max0 - Min0 < 1 bsl 256 -> - {Intersection, Union} = range_masks(Min0, Max0), - - Min = Intersection band Int, - Max = min(Max0, Union band Int), - - #t_integer{elements={Min,Max}}; - _ when Int >= 0 -> - %% The range is either unknown or too wide, conservatively assume - %% that the new range is 0 .. Int. - #t_integer{elements={0,Int}}; - _ when Int < 0 -> - %% We can't infer boundaries when the range is unknown and the - %% other operand is a negative number, as the latter sign-extends - %% to infinity and we can't express an inverted range at the - %% moment (cf. X band -8; either less than 7 or greater than 7). - #t_integer{} - end. - -%% Returns two bitmasks describing all possible values between From and To. -%% -%% The first contains the bits that are common to all values, and the second -%% contains the bits that are set by any value in the range. -range_masks(From, To) when From =< To -> - range_masks_1(From, To, 0, -1, 0). - -range_masks_1(From, To, BitPos, Intersection, Union) when From < To -> - range_masks_1(From + (1 bsl BitPos), To, BitPos + 1, - Intersection band From, Union bor From); -range_masks_1(_From, To, _BitPos, Intersection0, Union0) -> - Intersection = To band Intersection0, - Union = To bor Union0, - {Intersection, Union}. - bs_match_type([#b_literal{val=Type}|Args]) -> bs_match_type(Type, Args). bs_match_type(binary, Args) -> [_,_,_,#b_literal{val=U}] = Args, - {binary,U}; + #t_bitstring{unit=U}; bs_match_type(float, _) -> float; bs_match_type(integer, Args) -> @@ -1280,24 +1088,24 @@ bs_match_type(integer, Args) -> NumBits = Size * Unit, case member(unsigned, Flags) of true -> - t_integer(0, (1 bsl NumBits)-1); + beam_types:make_integer(0, (1 bsl NumBits)-1); false -> %% Signed integer. Don't bother. - t_integer() + #t_integer{} end; [_|_] -> - t_integer() + #t_integer{} end; bs_match_type(skip, _) -> any; bs_match_type(string, _) -> any; bs_match_type(utf8, _) -> - ?UNICODE_INT; + beam_types:make_integer(0, ?UNICODE_MAX); bs_match_type(utf16, _) -> - ?UNICODE_INT; + beam_types:make_integer(0, ?UNICODE_MAX); bs_match_type(utf32, _) -> - ?UNICODE_INT. + beam_types:make_integer(0, ?UNICODE_MAX). simplify_switch_atom(#t_atom{elements=Atoms}, #b_switch{list=List0}=Sw) -> case sort([A || {#b_literal{val=A},_} <- List0]) of @@ -1329,12 +1137,12 @@ eq_ranges(_, _, _) -> false. simplify_is_record(I, #t_tuple{exact=Exact, size=Size, elements=Es}, - RecSize, RecTag, Ts) -> + RecSize, #b_literal{val=TagVal}=RecTag, Ts) -> TagType = maps:get(1, Es, any), - TagMatch = case get_literal_from_type(TagType) of - #b_literal{}=RecTag -> yes; - #b_literal{} -> no; - none -> + TagMatch = case beam_types:get_singleton_value(TagType) of + {ok, TagVal} -> yes; + {ok, _} -> no; + error -> %% Is it at all possible for the tag to match? case beam_types:meet(get_type(RecTag, Ts), TagType) of none -> no; @@ -1366,7 +1174,7 @@ simplify_switch_bool(#b_switch{arg=B,fail=Fail,list=List0}, Ts, Ds) -> simplify_not(#b_br{bool=#b_var{}=V,succ=Succ,fail=Fail}=Br0, Ts, Ds) -> case Ds of #{V:=#b_set{op={bif,'not'},args=[Bool]}} -> - case t_is_boolean(get_type(Bool, Ts)) of + case beam_types:is_boolean_type(get_type(Bool, Ts)) of true -> Br = Br0#b_br{bool=Bool,succ=Fail,fail=Succ}, beam_ssa:normalize(Br); @@ -1445,27 +1253,29 @@ get_type(#b_var{}=V, Ts) -> get_type(#b_literal{val=Val}, _Ts) -> if is_atom(Val) -> - t_atom(Val); + beam_types:make_atom(Val); is_float(Val) -> float; is_function(Val) -> {arity,Arity} = erlang:fun_info(Val, arity), #t_fun{arity=Arity}; is_integer(Val) -> - t_integer(Val); + beam_types:make_integer(Val); is_list(Val), Val =/= [] -> cons; is_map(Val) -> - map; + #t_map{}; Val =:= {} -> - #t_tuple{exact=true}; + beam_types:make_tuple(0, true); is_tuple(Val) -> {Es, _} = foldl(fun(E, {Es0, Index}) -> - Type = get_type(#b_literal{val=E}, #{}), - Es = set_element_type(Index, Type, Es0), - {Es, Index + 1} + Type = get_type(#b_literal{val=E}, #{}), + Es = beam_types:set_element_type(Index, + Type, + Es0), + {Es, Index + 1} end, {#{}, 1}, tuple_to_list(Val)), - #t_tuple{exact=true,size=tuple_size(Val),elements=Es}; + beam_types:make_tuple(tuple_size(Val), true, Es); Val =:= [] -> nil; true -> @@ -1495,8 +1305,7 @@ get_type(#b_literal{val=Val}, _Ts) -> infer_types_br(#b_var{}=V, Ts, #d{ds=Ds}) -> #{V:=#b_set{op=Op,args=Args}} = Ds, - PosTypes0 = infer_type(Op, Args, Ds), - NegTypes0 = infer_type_negative(Op, Args, Ds), + {PosTypes0, NegTypes0} = infer_type(Op, Args, Ts, Ds), %% We must be careful with types inferred from '=:='. %% @@ -1509,7 +1318,7 @@ infer_types_br(#b_var{}=V, Ts, #d{ds=Ds}) -> %% it is single-valued, e.g. if it is [] or the atom 'true'. EqTypes = infer_eq_type(Op, Args, Ts, Ds), - NegTypes1 = [P || {_,T}=P <- EqTypes, is_singleton_type(T)], + NegTypes1 = [P || {_,T}=P <- EqTypes, beam_types:is_singleton_type(T)], PosTypes = EqTypes ++ PosTypes0, SuccTs = meet_types(PosTypes, Ts), @@ -1548,177 +1357,72 @@ infer_eq_lit(#b_set{op=get_tuple_element, args=[#b_var{}=Tuple,#b_literal{val=N}]}, #b_literal{}=Lit) -> Index = N + 1, - Es = set_element_type(Index, get_type(Lit, #{}), #{}), + Es = beam_types:set_element_type(Index, get_type(Lit, #{}), #{}), [{Tuple,#t_tuple{size=Index,elements=Es}}]; infer_eq_lit(_, _) -> []. -infer_type_negative(Op, Args, Ds) -> - case is_negative_inference_safe(Op, Args) of - true -> - infer_type(Op, Args, Ds); - false -> - [] - end. - -%% Conservative list of instructions for which negative -%% inference is safe. -is_negative_inference_safe(is_nonempty_list, _Args) -> true; -is_negative_inference_safe(_, _) -> false. - -infer_type({bif,element}, [#b_literal{val=Pos},#b_var{}=Tuple], _Ds) -> - if - is_integer(Pos), 1 =< Pos -> - [{Tuple,#t_tuple{size=Pos}}]; - true -> - [] - end; -infer_type({bif,element}, [#b_var{}=Position,#b_var{}=Tuple], _Ds) -> - [{Position,t_integer()},{Tuple,#t_tuple{}}]; -infer_type({bif,Bif}, [#b_var{}=Src]=Args, _Ds) -> - case inferred_bif_type(Bif, Args) of - any -> []; - T -> [{Src,T}] - end; -infer_type({bif,binary_part}, [#b_var{}=Src,_], _Ds) -> - [{Src,{binary,8}}]; -infer_type({bif,is_map_key}, [_,#b_var{}=Src], _Ds) -> - [{Src,map}]; -infer_type({bif,map_get}, [_,#b_var{}=Src], _Ds) -> - [{Src,map}]; -infer_type({bif,Bif}, [_,_]=Args, _Ds) -> - case inferred_bif_type(Bif, Args) of - any -> []; - T -> [{A,T} || #b_var{}=A <- Args] - end; -infer_type({bif,binary_part}, [#b_var{}=Src,Pos,Len], _Ds) -> - [{Src,{binary,8}}| - [{V,t_integer()} || #b_var{}=V <- [Pos,Len]]]; -infer_type(bs_start_match, [#b_var{}=Bin], _Ds) -> - [{Bin,{binary,1}}]; -infer_type(is_nonempty_list, [#b_var{}=Src], _Ds) -> - [{Src,cons}]; -infer_type(is_tagged_tuple, [#b_var{}=Src,#b_literal{val=Size}, - #b_literal{}=Tag], _Ds) -> - Es = set_element_type(1, get_type(Tag, #{}), #{}), - [{Src,#t_tuple{exact=true,size=Size,elements=Es}}]; -infer_type(succeeded, [#b_var{}=Src], Ds) -> +infer_type(succeeded, [#b_var{}=Src], Ts, Ds) -> #b_set{op=Op,args=Args} = maps:get(Src, Ds), - infer_type(Op, Args, Ds); -infer_type(_Op, _Args, _Ds) -> - []. - -%% bif_type(Name, Args) -> Type -%% Return the return type for the guard BIF or operator Name with -%% arguments Args. -%% -%% Note that that the following BIFs are handle elsewhere: -%% -%% band/2 - -bif_type(abs, [_]) -> number; -bif_type(bit_size, [_]) -> t_integer(); -bif_type(byte_size, [_]) -> t_integer(); -bif_type(ceil, [_]) -> t_integer(); -bif_type(float, [_]) -> float; -bif_type(floor, [_]) -> t_integer(); -bif_type(is_map_key, [_,_]) -> t_boolean(); -bif_type(length, [_]) -> t_integer(); -bif_type(map_size, [_]) -> t_integer(); -bif_type(node, []) -> #t_atom{}; -bif_type(node, [_]) -> #t_atom{}; -bif_type(round, [_]) -> t_integer(); -bif_type(size, [_]) -> t_integer(); -bif_type(trunc, [_]) -> t_integer(); -bif_type(tuple_size, [_]) -> t_integer(); -bif_type('bnot', [_]) -> t_integer(); -bif_type('bor', [_,_]) -> t_integer(); -bif_type('bsl', [_,_]) -> t_integer(); -bif_type('bsr', [_,_]) -> t_integer(); -bif_type('bxor', [_,_]) -> t_integer(); -bif_type('div', [_,_]) -> t_integer(); -bif_type('rem', [_,_]) -> t_integer(); -bif_type('/', [_,_]) -> float; -bif_type(Name, Args) -> - Arity = length(Args), - case erl_internal:new_type_test(Name, Arity) orelse - erl_internal:bool_op(Name, Arity) orelse - erl_internal:comp_op(Name, Arity) of - true -> - t_boolean(); - false -> - case erl_internal:arith_op(Name, Arity) of - true -> number; - false -> any - end - end. + infer_type(Op, Args, Ts, Ds); +infer_type(bs_start_match, [#b_var{}=Bin], _Ts, _Ds) -> + T = {Bin,#t_bitstring{}}, + {[T], [T]}; +infer_type(is_nonempty_list, [#b_var{}=Src], _Ts, _Ds) -> + T = {Src,cons}, + {[T], [T]}; +infer_type(is_tagged_tuple, [#b_var{}=Src,#b_literal{val=Size}, + #b_literal{}=Tag], _Ts, _Ds) -> + Es = beam_types:set_element_type(1, get_type(Tag, #{}), #{}), + T = {Src,#t_tuple{exact=true,size=Size,elements=Es}}, + {[T], [T]}; + +%% Type tests are handled separately from other BIFs as we're inferring types +%% based on their result rather than whether they succeeded, so we know that +%% subtraction is always safe. +infer_type({bif,is_atom}, [Arg], _Ts, _Ds) -> + T = {Arg, #t_atom{}}, + {[T], [T]}; +infer_type({bif,is_binary}, [Arg], _Ts, _Ds) -> + T = {Arg, #t_bitstring{unit=8}}, + {[T], [T]}; +infer_type({bif,is_bitstring}, [Arg], _Ts, _Ds) -> + T = {Arg, #t_bitstring{}}, + {[T], [T]}; +infer_type({bif,is_boolean}, [Arg], _Ts, _Ds) -> + T = {Arg, beam_types:make_boolean()}, + {[T], [T]}; +infer_type({bif,is_float}, [Arg], _Ts, _Ds) -> + T = {Arg, float}, + {[T], [T]}; +infer_type({bif,is_integer}, [Arg], _Ts, _Ds) -> + T = {Arg, #t_integer{}}, + {[T], [T]}; +infer_type({bif,is_list}, [Arg], _Ts, _Ds) -> + T = {Arg, list}, + {[T], [T]}; +infer_type({bif,is_map}, [Arg], _Ts, _Ds) -> + T = {Arg, #t_map{}}, + {[T], [T]}; +infer_type({bif,is_number}, [Arg], _Ts, _Ds) -> + T = {Arg, number}, + {[T], [T]}; +infer_type({bif,is_tuple}, [Arg], _Ts, _Ds) -> + T = {Arg, #t_tuple{}}, + {[T], [T]}; + +infer_type({bif,Op}, Args, Ts, _Ds) -> + ArgTypes = get_types(Args, Ts), + + {_, PosTypes0, CanSubtract} = beam_call_types:types(erlang, Op, ArgTypes), + PosTypes = [T || {#b_var{},_}=T <- zip(Args, PosTypes0)], + + case CanSubtract of + true -> {PosTypes, PosTypes}; + false -> {PosTypes, []} + end; -inferred_bif_type(is_atom, [_]) -> t_atom(); -inferred_bif_type(is_binary, [_]) -> {binary,8}; -inferred_bif_type(is_bitstring, [_]) -> {binary,1}; -inferred_bif_type(is_boolean, [_]) -> t_boolean(); -inferred_bif_type(is_float, [_]) -> float; -inferred_bif_type(is_integer, [_]) -> t_integer(); -inferred_bif_type(is_list, [_]) -> list; -inferred_bif_type(is_map, [_]) -> map; -inferred_bif_type(is_number, [_]) -> number; -inferred_bif_type(is_tuple, [_]) -> #t_tuple{}; -inferred_bif_type(abs, [_]) -> number; -inferred_bif_type(bit_size, [_]) -> {binary,1}; -inferred_bif_type('bnot', [_]) -> t_integer(); -inferred_bif_type(byte_size, [_]) -> {binary,1}; -inferred_bif_type(ceil, [_]) -> number; -inferred_bif_type(float, [_]) -> number; -inferred_bif_type(floor, [_]) -> number; -inferred_bif_type(hd, [_]) -> cons; -inferred_bif_type(length, [_]) -> list; -inferred_bif_type(map_size, [_]) -> map; -inferred_bif_type('not', [_]) -> t_boolean(); -inferred_bif_type(round, [_]) -> number; -inferred_bif_type(trunc, [_]) -> number; -inferred_bif_type(tl, [_]) -> cons; -inferred_bif_type(tuple_size, [_]) -> #t_tuple{}; -inferred_bif_type('and', [_,_]) -> t_boolean(); -inferred_bif_type('or', [_,_]) -> t_boolean(); -inferred_bif_type('xor', [_,_]) -> t_boolean(); -inferred_bif_type('band', [_,_]) -> t_integer(); -inferred_bif_type('bor', [_,_]) -> t_integer(); -inferred_bif_type('bsl', [_,_]) -> t_integer(); -inferred_bif_type('bsr', [_,_]) -> t_integer(); -inferred_bif_type('bxor', [_,_]) -> t_integer(); -inferred_bif_type('div', [_,_]) -> t_integer(); -inferred_bif_type('rem', [_,_]) -> t_integer(); -inferred_bif_type('+', [_,_]) -> number; -inferred_bif_type('-', [_,_]) -> number; -inferred_bif_type('*', [_,_]) -> number; -inferred_bif_type('/', [_,_]) -> number; -inferred_bif_type(_, _) -> any. - -is_math_bif(cos, 1) -> true; -is_math_bif(cosh, 1) -> true; -is_math_bif(sin, 1) -> true; -is_math_bif(sinh, 1) -> true; -is_math_bif(tan, 1) -> true; -is_math_bif(tanh, 1) -> true; -is_math_bif(acos, 1) -> true; -is_math_bif(acosh, 1) -> true; -is_math_bif(asin, 1) -> true; -is_math_bif(asinh, 1) -> true; -is_math_bif(atan, 1) -> true; -is_math_bif(atanh, 1) -> true; -is_math_bif(erf, 1) -> true; -is_math_bif(erfc, 1) -> true; -is_math_bif(exp, 1) -> true; -is_math_bif(log, 1) -> true; -is_math_bif(log2, 1) -> true; -is_math_bif(log10, 1) -> true; -is_math_bif(sqrt, 1) -> true; -is_math_bif(atan2, 2) -> true; -is_math_bif(pow, 2) -> true; -is_math_bif(ceil, 1) -> true; -is_math_bif(floor, 1) -> true; -is_math_bif(fmod, 2) -> true; -is_math_bif(pi, 0) -> true; -is_math_bif(_, _) -> false. +infer_type(_Op, _Args, _Ts, _Ds) -> + {[], []}. join_types(Ts0, Ts1) -> if @@ -1745,67 +1449,6 @@ join_types_1([V|Vs], Ts0, Ts1) -> join_types_1([], Ts0, Ts1) -> maps:merge(Ts0, Ts1). -get_literal_from_type(#t_atom{elements=[Atom]}) -> - #b_literal{val=Atom}; -get_literal_from_type(#t_integer{elements={Int,Int}}) -> - #b_literal{val=Int}; -get_literal_from_type(nil) -> - #b_literal{val=[]}; -get_literal_from_type(_) -> none. - -remove_element_info(#t_integer{elements={Min,Max}}, Es) -> - foldl(fun(El, Acc) when Min =< El, El =< Max -> - maps:remove(El, Acc); - (_El, Acc) -> Acc - end, Es, maps:keys(Es)). - -t_atom() -> - #t_atom{elements=any}. - -t_atom(Atom) when is_atom(Atom) -> - #t_atom{elements=[Atom]}. - -t_boolean() -> - #t_atom{elements=[false,true]}. - -t_integer() -> - #t_integer{elements=any}. - -t_integer(Int) when is_integer(Int) -> - #t_integer{elements={Int,Int}}. - -t_integer(Min, Max) when is_integer(Min), is_integer(Max) -> - #t_integer{elements={Min,Max}}. - -t_is_boolean(#t_atom{elements=[F,T]}) -> - F =:= false andalso T =:= true; -t_is_boolean(#t_atom{elements=[B]}) -> - is_boolean(B); -t_is_boolean(_) -> false. - -t_tuple_size(#t_tuple{size=Size,exact=false}) -> - {at_least,Size}; -t_tuple_size(#t_tuple{size=Size,exact=true}) -> - {exact,Size}; -t_tuple_size(_) -> - none. - -is_singleton_type(Type) -> - get_literal_from_type(Type) =/= none. - -get_element_type(Index, Es) -> - case Es of - #{ Index := T } -> T; - #{} -> any - end. - -set_element_type(_Key, none, Es) -> - Es; -set_element_type(Key, any, Es) -> - maps:remove(Key, Es); -set_element_type(Key, Type, Es) -> - Es#{ Key => Type }. - meet_types([{V,T0}|Vs], Ts) -> #{V:=T1} = Ts, case beam_types:meet(T0, T1) of diff --git a/lib/compiler/src/beam_types.erl b/lib/compiler/src/beam_types.erl index 6fcc70a4bd..c3ad594304 100644 --- a/lib/compiler/src/beam_types.erl +++ b/lib/compiler/src/beam_types.erl @@ -22,22 +22,21 @@ -include("beam_types.hrl"). --import(lists, [foldl/3, reverse/1]). +-export([meet/1, meet/2, join/1, join/2, subtract/2]). --export([meet/1, meet/2, join/1, join/2, subtract/2, verified_type/1]). +-export([get_singleton_value/1, + get_tuple_size/1, + is_singleton_type/1, + is_boolean_type/1]). --export([call_types/3]). +-export([get_element_type/2, set_element_type/3]). -%%% -%%% Type constructors -%%% - --spec t_boolean() -> type(). -t_boolean() -> #t_atom{elements=[false,true]}. - -%%% -%%% Type operators -%%% +-export([make_atom/1, + make_boolean/0, + make_integer/1, + make_integer/2, + make_tuple/2, + make_tuple/3]). %% Return the "join" of Type1 and Type2. The join is a more general %% type than Type1 and Type2. For example: @@ -48,7 +47,7 @@ t_boolean() -> #t_atom{elements=[false,true]}. %% The join for two different types result in 'any', which is %% the top element for our type lattice: %% -%% join(#t_integer{}, map) -> any +%% join(#t_integer{}, #t_map{}) -> any -spec join(type(), type()) -> type(). @@ -70,13 +69,17 @@ join(#t_atom{elements=[_|_]=Set1}, #t_atom{elements=[_|_]=Set2}) -> end; join(#t_atom{elements=any}=T, #t_atom{elements=[_|_]}) -> T; join(#t_atom{elements=[_|_]}, #t_atom{elements=any}=T) -> T; -join({binary,U1}, {binary,U2}) -> - {binary,gcd(U1, U2)}; +join(#t_bitstring{unit=U1}, #t_bitstring{unit=U2}) -> + #t_bitstring{unit=gcd(U1, U2)}; join(#t_fun{}, #t_fun{}) -> #t_fun{}; join(#t_integer{elements={MinA,MaxA}}, #t_integer{elements={MinB,MaxB}}) -> #t_integer{elements={min(MinA,MinB),max(MaxA,MaxB)}}; +join(#t_bs_context{slots=SlotsA,valid=ValidA}, + #t_bs_context{slots=SlotsB,valid=ValidB}) -> + #t_bs_context{slots=min(SlotsA, SlotsB), + valid=ValidA band ValidB}; join(#t_integer{}, #t_integer{}) -> #t_integer{}; join(list, cons) -> list; join(cons, list) -> list; @@ -131,28 +134,12 @@ gcd(A, B) -> X -> gcd(B, X) end. -set_element_type(_Key, none, Es) -> - Es; -set_element_type(Key, any, Es) -> - maps:remove(Key, Es); -set_element_type(Key, Type, Es) -> - Es#{ Key => Type }. - -%% Subtract Type2 from Type1. Example: -%% subtract(list, cons) -> nil - --spec subtract(type(), type()) -> type(). +%% Joins all the given types into a single type. +-spec join([type()]) -> type(). -subtract(#t_atom{elements=[_|_]=Set0}, #t_atom{elements=[_|_]=Set1}) -> - case ordsets:subtract(Set0, Set1) of - [] -> none; - [_|_]=Set -> #t_atom{elements=Set} - end; -subtract(number, float) -> #t_integer{}; -subtract(number, #t_integer{elements=any}) -> float; -subtract(list, cons) -> nil; -subtract(list, nil) -> cons; -subtract(T, _) -> T. +join([T1,T2|Ts]) -> + join([join(T1, T2)|Ts]); +join([T]) -> T. %% Return the "meet" of Type1 and Type2. The meet is a narrower %% type than Type1 and Type2. For example: @@ -163,7 +150,7 @@ subtract(T, _) -> T. %% The meet for two different types result in 'none', which is %% the bottom element for our type lattice: %% -%% meet(#t_integer{}, map) -> none +%% meet(#t_integer{}, #t_map{}) -> none -spec meet(type(), type()) -> type(). @@ -202,8 +189,8 @@ meet(cons, list) -> cons; meet(nil, list) -> nil; meet(#t_tuple{}=T1, #t_tuple{}=T2) -> meet_tuples(T1, T2); -meet({binary,U1}, {binary,U2}) -> - {binary, U1 * U2 div gcd(U1, U2)}; +meet(#t_bitstring{unit=U1}, #t_bitstring{unit=U2}) -> + #t_bitstring{unit=U1 * U2 div gcd(U1, U2)}; meet(any, T) -> verified_type(T); meet(T, any) -> @@ -245,11 +232,30 @@ meet_elements_1([Key | Keys], Es1, Es2, Acc) -> meet_elements_1([], _Es1, _Es2, Acc) -> Acc. -%% Returns the passed in type if it is well-formed and safe to pass to -%% arbitrary code, and crashes if there's anything wrong with it. -%% -%% Currently, all types described in beam_types.hrl except for #t_bs_match{} -%% are considered safe. +%% Meets all the given types into a single type. +-spec meet([type()]) -> type(). + +meet([T1,T2|Ts]) -> + meet([meet(T1, T2)|Ts]); +meet([T]) -> T. + +%% Subtract Type2 from Type1. Example: +%% subtract(list, cons) -> nil + +-spec subtract(type(), type()) -> type(). + +subtract(#t_atom{elements=[_|_]=Set0}, #t_atom{elements=[_|_]=Set1}) -> + case ordsets:subtract(Set0, Set1) of + [] -> none; + [_|_]=Set -> #t_atom{elements=Set} + end; +subtract(number, float) -> #t_integer{}; +subtract(number, #t_integer{elements=any}) -> float; +subtract(list, cons) -> nil; +subtract(list, nil) -> cons; +subtract(T, _) -> T. + +%% Verifies that the given type is well-formed. -spec verified_type(T) -> T when T :: type(). @@ -258,13 +264,14 @@ verified_type(any=T) -> T; verified_type(none=T) -> T; verified_type(#t_atom{elements=any}=T) -> T; verified_type(#t_atom{elements=[_|_]}=T) -> T; -verified_type({binary,U}=T) when is_integer(U) -> T; +verified_type(#t_bitstring{unit=U}=T) when is_integer(U), U >= 1 -> T; +verified_type(#t_bs_context{}=T) -> T; verified_type(#t_fun{arity=Arity}=T) when Arity =:= any; is_integer(Arity) -> T; verified_type(#t_integer{elements=any}=T) -> T; verified_type(#t_integer{elements={Min,Max}}=T) when is_integer(Min), is_integer(Max), Min =< Max -> T; verified_type(list=T) -> T; -verified_type(map=T) -> T; +verified_type(#t_map{}=T) -> T; verified_type(nil=T) -> T; verified_type(cons=T) -> T; verified_type(number=T) -> T; @@ -279,16 +286,97 @@ verified_type(#t_tuple{size=Size,elements=Es}=T) -> T; verified_type(float=T) -> T. -%% Joins all the given types into a single type. --spec join([type()]) -> type(). +%%% +%%% Type operators +%%% -join([T1,T2|Ts]) -> - join([join(T1, T2)|Ts]); -join([T]) -> T. +-spec get_singleton_value(Type) -> Result when + Type :: type(), + Result :: {ok, term()} | error. +get_singleton_value(#t_atom{elements=[Atom]}) -> + {ok, Atom}; +get_singleton_value(#t_integer{elements={Int,Int}}) -> + {ok, Int}; +get_singleton_value(nil) -> + {ok, []}; +get_singleton_value(_) -> + error. + +-spec get_tuple_size(Type) -> Result when + Type :: type(), + Result :: none | {at_least, Size} | {exact, Size}, + Size :: non_neg_integer(). +get_tuple_size(#t_tuple{size=Size,exact=false}) -> + {at_least,Size}; +get_tuple_size(#t_tuple{size=Size,exact=true}) -> + {exact,Size}; +get_tuple_size(_) -> + none. -%% Meets all the given types into a single type. --spec meet([type()]) -> type(). +-spec is_boolean_type(type()) -> boolean(). +is_boolean_type(#t_atom{elements=[F,T]}) -> + F =:= false andalso T =:= true; +is_boolean_type(#t_atom{elements=[B]}) -> + is_boolean(B); +is_boolean_type(_) -> false. + +-spec is_singleton_type(type()) -> boolean(). +is_singleton_type(Type) -> + get_singleton_value(Type) =/= error. + +-spec set_element_type(Key, Type, Elements) -> Elements when + Key :: term(), + Type :: type(), + Elements :: elements(). +set_element_type(_Key, none, Es) -> + Es; +set_element_type(Key, any, Es) -> + maps:remove(Key, Es); +set_element_type(Key, Type, Es) -> + Es#{ Key => Type }. -meet([T1,T2|Ts]) -> - meet([meet(T1, T2)|Ts]); -meet([T]) -> T. +-spec get_element_type(Key, Elements) -> type() when + Key :: term(), + Elements :: elements(). +get_element_type(Index, Es) -> + case Es of + #{ Index := T } -> T; + #{} -> any + end. + +%%% +%%% Type constructors +%%% + +-spec make_atom(atom()) -> type(). +make_atom(Atom) when is_atom(Atom) -> + #t_atom{elements=[Atom]}. + +-spec make_boolean() -> type(). +make_boolean() -> + #t_atom{elements=[false,true]}. + +-spec make_integer(integer()) -> type(). +make_integer(Int) when is_integer(Int) -> + make_integer(Int, Int). + +-spec make_integer(Min, Max) -> type() when + Min :: integer(), + Max :: integer(). +make_integer(Min, Max) when is_integer(Min), is_integer(Max), Min =< Max -> + #t_integer{elements={Min,Max}}. + +-spec make_tuple(Size, Exact) -> type() when + Size :: non_neg_integer(), + Exact :: boolean(). +make_tuple(Size, Exact) -> + make_tuple(Size, Exact, #{}). + +-spec make_tuple(Size, Exact, Elements) -> type() when + Size :: non_neg_integer(), + Exact :: boolean(), + Elements :: #{ non_neg_integer() => type() }. +make_tuple(Size, Exact, Elements) -> + #t_tuple{size=Size, + exact=Exact, + elements=Elements}. diff --git a/lib/compiler/src/beam_types.hrl b/lib/compiler/src/beam_types.hrl index dfbf104a2a..b82cdf8df2 100644 --- a/lib/compiler/src/beam_types.hrl +++ b/lib/compiler/src/beam_types.hrl @@ -25,15 +25,15 @@ %% %% any Any Erlang term (top element). %% -%% - atom An atom. -%% - {binary,Unit} A bitstring aligned to unit Unit. -%% - #t_bs_match{} A match context. -%% - #t_fun{} A fun. -%% - map A map. -%% - number A number. +%% - #t_atom{} Atom, or a set thereof. +%% - #t_bitstring{} Bitstring. +%% - #t_bs_context{} Match context. +%% - #t_fun{} Fun. +%% - #t_map{} Map. +%% - number Any number. %% -- float Floating point number. %% -- integer Integer. -%% - list A list. +%% - list Any list. %% -- cons Cons (nonempty list). %% -- nil The empty list. %% - #t_tuple{} Tuple. @@ -45,14 +45,25 @@ -record(t_atom, {elements=any :: 'any' | [atom()]}). -record(t_fun, {arity=any :: arity() | 'any'}). -record(t_integer, {elements=any :: 'any' | {integer(),integer()}}). --record(t_bs_match, {type :: type()}). +-record(t_bitstring, {unit=1 :: pos_integer()}). +-record(t_bs_context, {slots=0 :: non_neg_integer(), + valid=0 :: non_neg_integer()}). +-record(t_map, {elements=#{} :: map_elements()}). -record(t_tuple, {size=0 :: integer(), exact=false :: boolean(), - %% Known element types (1-based index), unknown elements are - %% are assumed to be 'any'. - elements=#{} :: #{ non_neg_integer() => type() }}). + elements=#{} :: tuple_elements()}). --type type() :: 'any' | 'none' | - #t_atom{} | #t_bs_match{} | #t_fun{} | #t_integer{} | - #t_tuple{} | {'binary',pos_integer()} | 'cons' | 'float' | - 'list' | 'map' | 'nil' | 'number'. +%% Known element types, unknown elements are assumed to be 'any'. The key is +%% a 1-based integer index for tuples, and a plain literal for maps (that is, +%% not wrapped in a #b_literal{}, just the value itself). + +-type tuple_elements() :: #{ Key :: pos_integer() => type() }. +-type map_elements() :: #{ Key :: term() => type() }. + +-type elements() :: tuple_elements() | map_elements(). + +-type type() :: any | none | + list | number | + #t_atom{} | #t_bitstring{} | #t_bs_context{} | #t_fun{} | + #t_integer{} | #t_map{} | #t_tuple{} | 'cons' | + 'float' | 'nil'. diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl index 28ab8813ba..098f82fdc0 100644 --- a/lib/compiler/src/compile.erl +++ b/lib/compiler/src/compile.erl @@ -2093,6 +2093,7 @@ pre_load() -> L = [beam_a, beam_asm, beam_block, + beam_call_types, beam_clean, beam_dict, beam_flatten, diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src index 22ef67f357..092757ae65 100644 --- a/lib/compiler/src/compiler.app.src +++ b/lib/compiler/src/compiler.app.src @@ -24,6 +24,7 @@ beam_a, beam_asm, beam_block, + beam_call_types, beam_clean, beam_dict, beam_disasm, diff --git a/lib/compiler/test/beam_types_SUITE.erl b/lib/compiler/test/beam_types_SUITE.erl index 66fd517ec0..297bd4026e 100644 --- a/lib/compiler/test/beam_types_SUITE.erl +++ b/lib/compiler/test/beam_types_SUITE.erl @@ -55,11 +55,11 @@ commutativity(Config) when is_list(Config) -> binary_consistency(Config) when is_list(Config) -> %% These binaries should meet into {binary,12} as that's the best common %% unit for both types. - A = {binary, 4}, - B = {binary, 6}, + A = #t_bitstring{unit=4}, + B = #t_bitstring{unit=6}, - {binary, 12} = beam_types:meet(A, B), - {binary, 2} = beam_types:join(A, B), + #t_bitstring{unit=12} = beam_types:meet(A, B), + #t_bitstring{unit=2} = beam_types:join(A, B), A = beam_types:meet(A, beam_types:join(A, B)), A = beam_types:join(A, beam_types:meet(A, B)), diff --git a/lib/compiler/test/property_test/beam_types_prop.erl b/lib/compiler/test/property_test/beam_types_prop.erl index 815e353853..9c103d3886 100644 --- a/lib/compiler/test/property_test/beam_types_prop.erl +++ b/lib/compiler/test/property_test/beam_types_prop.erl @@ -84,7 +84,7 @@ numerical_types() -> [gen_integer(), float, number]. nested_types(Depth) when Depth >= 3 -> []; -nested_types(Depth) -> [map, gen_tuple(Depth + 1)]. +nested_types(Depth) -> [#t_map{}, gen_tuple(Depth + 1)]. gen_atom() -> ?LET(Size, range(0, ?ATOM_SET_SIZE), @@ -99,8 +99,8 @@ gen_atom() -> end). gen_binary() -> - ?SHRINK({binary, range(1, 128)}, - [{binary, [1, 2, 3, 5, 7, 8, 16, 32, 64]}]). + ?SHRINK(#t_bitstring{unit=range(1, 128)}, + [#t_bitstring{unit=[1, 2, 3, 5, 7, 8, 16, 32, 64]}]). gen_integer() -> oneof([gen_integer_bounded(), #t_integer{}]). -- cgit v1.2.3 From af617aebe254da636b7d9c2ac59e1109998b0b1c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Wed, 12 Jun 2019 09:35:03 +0200 Subject: beam_call_types: Improve type handling of lists:zip/2 and friends --- lib/compiler/src/beam_call_types.erl | 31 +++++++++++++++++++++---------- 1 file changed, 21 insertions(+), 10 deletions(-) diff --git a/lib/compiler/src/beam_call_types.erl b/lib/compiler/src/beam_call_types.erl index 45fbead804..b1ff200fb6 100644 --- a/lib/compiler/src/beam_call_types.erl +++ b/lib/compiler/src/beam_call_types.erl @@ -340,16 +340,17 @@ types(lists, takewhile, [_,_]) -> types(lists, usort, [List]) -> sub_unsafe(same_length_type(List), [list]); types(lists, zip, [A,B]) -> - RetType = beam_types:join(same_length_type(A), same_length_type(B)), - sub_unsafe(RetType, [list, list]); + ZipType = lists_zip_type([A,B]), + sub_unsafe(ZipType, [ZipType, ZipType]); +types(lists, zip3, [A,B,C]) -> + ZipType = lists_zip_type([A,B,C]), + sub_unsafe(ZipType, [ZipType, ZipType, ZipType]); types(lists, zipwith, [_,A,B]) -> - RetType = beam_types:join(same_length_type(A), same_length_type(B)), - sub_unsafe(RetType, [#t_fun{arity=2}, list, list]); + ZipType = lists_zip_type([A,B]), + sub_unsafe(ZipType, [#t_fun{arity=2}, ZipType, ZipType]); types(lists, zipwith3, [_,A,B,C]) -> - RetType = beam_types:join([same_length_type(A), - same_length_type(B), - same_length_type(C)]), - sub_unsafe(RetType, [#t_fun{arity=3}, list, list, list]); + ZipType = lists_zip_type([A,B,C]), + sub_unsafe(ZipType, [#t_fun{arity=3}, ZipType, ZipType, ZipType]); %% Functions with complex return values. types(lists, partition, [_,_]) -> @@ -455,12 +456,22 @@ discard_tuple_element_info(Min, Max, Es) -> (_El, Acc) -> Acc end, Es, maps:keys(Es)). -%% For a lists function that return a list of the same -%% length as the input list, return the type of the list. +%% 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. +%% lists:zip/2 and friends only succeed when all arguments have the same +%% length, so if one of them is cons, we can infer that all of them are cons +%% on success. +lists_zip_type(Types) -> + foldl(fun(cons, _) -> cons; + (_, cons) -> cons; + (nil, _) -> nil; + (_, T) -> T + end, list, Types). + make_two_tuple(Type1, Type2) -> #t_tuple{size=2,exact=true, elements=#{1=>Type1,2=>Type2}}. -- cgit v1.2.3 From 4411b1953bfb862aad433c2269acb82a35b0cc72 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Tue, 11 Jun 2019 14:43:53 +0200 Subject: beam_validator: Subtract types when inferring type test BIFs This is a temporary solution for basic type tests. We'll need to handle more-or-less arbitrary values once we introduce union types, as we need to be able to subtract on tuple_arity tests as well. Without this, nearly all "no_opt" test suites will fail to compile after the validator is migrated to 'beam_types' as a result of atom subtraction producing 'none' when all alternatives have been exhausted. --- lib/compiler/src/beam_validator.erl | 38 ++++++++++++++++++++++++++++++++++--- 1 file changed, 35 insertions(+), 3 deletions(-) diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 4c223a93ed..17e0a4fa38 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -1673,10 +1673,14 @@ infer_types_1(_) -> fun(_, S) -> S end. infer_type_test_bif(Type, Src) -> - fun({atom,true}, S) -> + fun({atom,Bool}, S) when is_boolean(Bool) -> case is_value_alive(Src, S) of - true -> update_type(fun meet/2, Type, Src, S); - false -> S + true when Bool =:= true -> + update_type(fun meet/2, Type, Src, S); + true when Bool =:= false -> + update_type(fun subtract/2, Type, Src, S); + false -> + S end; (_, S) -> S @@ -1798,6 +1802,34 @@ update_type(Merge, With, Literal, Vst) -> _Type -> Vst end. +update_ne_types(LHS, {atom,Bool}=RHS, Vst) when is_boolean(Bool) -> + %% This is a stopgap to make negative inference work for type test BIFs + %% like is_tuple. Consider the following unoptimized code: + %% + %% {call_ext,2,{extfunc,erlang,'--',2}}. + %% {bif,is_tuple,{f,0},[{x,0}],{x,1}}. + %% {test,is_eq_exact,{x,1},{f,2},{atom,false}}. + %% ... snip ... + %% {label,1}. + %% {test,is_eq_exact,{x,1},{f,1},{atom,true}}. + %% ... unreachable because {x,0} is known to be a list, so {x,1} can't + %% be true ... + %% {label,2}. + %% ... unreachable because {x,1} is neither true nor false! ... + %% + %% If we fail to determine that the first is_eq_exact never fails, our + %% state will be inconsistent after the second is_eq_exact check; we know + %% for certain that {x,0} is a list so infer_types says it can't succeed, + %% but it can't fail either because we also know that {x,1} is a boolean, + %% and the first check ruled out 'false'. + LType = get_term_type(LHS, Vst), + if + LType =:= bool -> + update_eq_types(LHS, {atom, not Bool}, Vst); + LType =/= bool -> + RType = get_term_type(RHS, Vst), + update_type(fun subtract/2, RType, LHS, Vst) + end; update_ne_types(LHS, RHS, Vst) -> %% While updating types on equality is fairly straightforward, inequality %% is a bit trickier since all we know is that the *value* of LHS differs -- cgit v1.2.3 From 48f83e165a2dae8ed04a74ba3c6308250168f790 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Wed, 29 May 2019 16:11:46 +0200 Subject: beam_validator: Replace old type representation with beam_types --- lib/compiler/src/beam_call_types.erl | 34 +- lib/compiler/src/beam_ssa_bsm.erl | 4 +- lib/compiler/src/beam_ssa_type.erl | 59 +- lib/compiler/src/beam_types.hrl | 7 +- lib/compiler/src/beam_validator.erl | 1131 +++++++--------------------- lib/compiler/test/beam_validator_SUITE.erl | 6 +- 6 files changed, 328 insertions(+), 913 deletions(-) diff --git a/lib/compiler/src/beam_call_types.erl b/lib/compiler/src/beam_call_types.erl index b1ff200fb6..d091b7866d 100644 --- a/lib/compiler/src/beam_call_types.erl +++ b/lib/compiler/src/beam_call_types.erl @@ -24,7 +24,39 @@ -import(lists, [duplicate/2,foldl/3]). --export([types/3]). +-export([never_throws/3, types/3]). + +-spec never_throws(Mod, Func, Arity) -> boolean() when + Mod :: atom(), + Func :: atom(), + Arity :: non_neg_integer(). + +never_throws(erlang, '/=', 2) -> true; +never_throws(erlang, '<', 2) -> true; +never_throws(erlang, '=/=', 2) -> true; +never_throws(erlang, '=:=', 2) -> true; +never_throws(erlang, '=<', 2) -> true; +never_throws(erlang, '==', 2) -> true; +never_throws(erlang, '>', 2) -> true; +never_throws(erlang, '>=', 2) -> true; +never_throws(erlang, is_atom, 1) -> true; +never_throws(erlang, is_boolean, 1) -> true; +never_throws(erlang, is_binary, 1) -> true; +never_throws(erlang, is_bitstring, 1) -> true; +never_throws(erlang, is_float, 1) -> true; +never_throws(erlang, is_function, 1) -> true; +never_throws(erlang, is_integer, 1) -> true; +never_throws(erlang, is_list, 1) -> true; +never_throws(erlang, is_map, 1) -> true; +never_throws(erlang, is_number, 1) -> true; +never_throws(erlang, is_pid, 1) -> true; +never_throws(erlang, is_port, 1) -> true; +never_throws(erlang, is_reference, 1) -> true; +never_throws(erlang, is_tuple, 1) -> true; +never_throws(erlang, get, 1) -> true; +never_throws(erlang, self, 0) -> true; +never_throws(erlang, node, 0) -> true; +never_throws(_, _, _) -> false. %% %% Returns the inferred return and argument types for known functions, and diff --git a/lib/compiler/src/beam_ssa_bsm.erl b/lib/compiler/src/beam_ssa_bsm.erl index 382e6f635e..abbda2ebe4 100644 --- a/lib/compiler/src/beam_ssa_bsm.erl +++ b/lib/compiler/src/beam_ssa_bsm.erl @@ -57,6 +57,7 @@ -export([module/2, format_error/1]). -include("beam_ssa.hrl"). +-include("beam_types.hrl"). -import(lists, [member/2, reverse/1, splitwith/2, map/2, foldl/3, mapfoldl/3, nth/2, max/1, unzip/1]). @@ -879,8 +880,7 @@ annotate_context_parameters(F, ModInfo) -> %% Assertion. error(conflicting_parameter_types); (K, suitable_for_reuse, Acc) -> - T = beam_validator:type_anno(match_context), - Acc#{ K => T }; + Acc#{ K => #t_bs_context{} }; (_K, _V, Acc) -> Acc end, TypeAnno0, ParamInfo), diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 99dec0d84f..79ed0d7885 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -144,50 +144,15 @@ opt_finish_1([Arg | Args], [TypeMap | TypeMaps], ParamInfo) map_size(TypeMap) =:= 0 -> opt_finish_1(Args, TypeMaps, ParamInfo); opt_finish_1([Arg | Args], [TypeMap | TypeMaps], ParamInfo0) -> - JoinedType0 = beam_types:join(maps:values(TypeMap)), - case validator_anno(JoinedType0) of - any -> - opt_finish_1(Args, TypeMaps, ParamInfo0); - JoinedType -> - ParamInfo = ParamInfo0#{ Arg => JoinedType }, - opt_finish_1(Args, TypeMaps, ParamInfo) - end; + JoinedType = beam_types:join(maps:values(TypeMap)), + ParamInfo = case JoinedType of + any -> ParamInfo0; + _ -> ParamInfo0#{ Arg => JoinedType } + end, + opt_finish_1(Args, TypeMaps, ParamInfo); opt_finish_1([], [], ParamInfo) -> ParamInfo. -validator_anno(any) -> - any; -validator_anno(#t_fun{}) -> - %% There is no need make funs visible to beam_validator. - any; -validator_anno(#t_tuple{size=Size,exact=Exact,elements=Elements0}) -> - Elements = maps:fold(fun(Index, Type0, Acc) -> - case validator_anno(Type0) of - any -> Acc; - Type -> Acc#{ Index => Type } - end - end, #{}, Elements0), - beam_validator:type_anno(tuple, Size, Exact, Elements); -validator_anno(#t_integer{elements={Same,Same}}) -> - beam_validator:type_anno(integer, Same); -validator_anno(#t_integer{}) -> - beam_validator:type_anno(integer); -validator_anno(#t_bitstring{unit=U}) -> - beam_validator:type_anno({binary,U}); -validator_anno(float) -> - beam_validator:type_anno(float); -validator_anno(#t_map{}) -> - beam_validator:type_anno(map); -validator_anno(#t_atom{elements=[Val]}) -> - beam_validator:type_anno(atom, Val); -validator_anno(#t_atom{}=A) -> - case beam_types:is_boolean_type(A) of - true -> beam_validator:type_anno(bool); - false -> beam_validator:type_anno(atom) - end; -validator_anno(T) -> - beam_validator:type_anno(T). - get_func_id(Anno) -> #{func_info:={_Mod, Name, Arity}} = Anno, #b_local{name=#b_literal{val=Name}, arity=Arity}. @@ -443,15 +408,9 @@ opt_local_call(#b_set{dst=Dst,args=[Id|_]}=I0, Ts0, Ds0, Fdb) -> #{} -> any end, I = case Type of - none -> - I0; - _ -> - case validator_anno(Type) of - any -> - I0; - ValidatorType -> - beam_ssa:add_anno(result_type, ValidatorType, I0) - end + any -> I0; + none -> I0; + _ -> beam_ssa:add_anno(result_type, Type, I0) end, Ts = Ts0#{ Dst => Type }, Ds = Ds0#{ Dst => I }, diff --git a/lib/compiler/src/beam_types.hrl b/lib/compiler/src/beam_types.hrl index b82cdf8df2..825eca4c64 100644 --- a/lib/compiler/src/beam_types.hrl +++ b/lib/compiler/src/beam_types.hrl @@ -37,6 +37,8 @@ %% -- cons Cons (nonempty list). %% -- nil The empty list. %% - #t_tuple{} Tuple. +%% - #t_abstract{} Psuedo-type used in the validator to track tuples +% under construction, match context positions, etc. %% %% none No type (bottom element). @@ -52,6 +54,7 @@ -record(t_tuple, {size=0 :: integer(), exact=false :: boolean(), elements=#{} :: tuple_elements()}). +-record(t_abstract, {kind :: atom()}). %% Known element types, unknown elements are assumed to be 'any'. The key is %% a 1-based integer index for tuples, and a plain literal for maps (that is, @@ -65,5 +68,5 @@ -type type() :: any | none | list | number | #t_atom{} | #t_bitstring{} | #t_bs_context{} | #t_fun{} | - #t_integer{} | #t_map{} | #t_tuple{} | 'cons' | - 'float' | 'nil'. + #t_integer{} | #t_map{} | #t_tuple{} | #t_abstract{} | + 'cons' | 'float' | 'nil'. diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 17e0a4fa38..8fe7ed8b69 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -19,6 +19,10 @@ -module(beam_validator). +-include("beam_types.hrl"). + +-define(UNICODE_MAX, (16#10FFFF)). + -compile({no_auto_import,[min/2]}). %% Avoid warning for local function error/1 clashing with autoimported BIF. @@ -26,7 +30,6 @@ %% Interface for compiler. -export([module/2, format_error/1]). --export([type_anno/1, type_anno/2, type_anno/4]). -import(lists, [dropwhile/2,foldl/3,member/2,reverse/1,sort/1,zip/2]). @@ -45,34 +48,6 @@ module({Mod,Exp,Attr,Fs,Lc}=Code, _Opts) {error,[{atom_to_list(Mod),Es}]} end. -%% Provides a stable interface for type annotations, used by certain passes to -%% indicate that we can safely assume that a register has a given type. --spec type_anno(term()) -> term(). -type_anno(atom) -> {atom,[]}; -type_anno(bool) -> bool; -type_anno({binary,_}) -> binary; -type_anno(cons) -> cons; -type_anno(float) -> {float,[]}; -type_anno(integer) -> {integer,[]}; -type_anno(list) -> list; -type_anno(map) -> map; -type_anno(match_context) -> match_context; -type_anno(number) -> number; -type_anno(nil) -> nil. - --spec type_anno(term(), term()) -> term(). -type_anno(atom, Value) when is_atom(Value) -> {atom, Value}; -type_anno(float, Value) when is_float(Value) -> {float, Value}; -type_anno(integer, Value) when is_integer(Value) -> {integer, Value}. - --spec type_anno(term(), term(), term(), term()) -> term(). -type_anno(tuple, Size, Exact, Elements) when is_integer(Size), Size >= 0, - is_map(Elements) -> - case Exact of - true -> {tuple, Size, Elements}; - false -> {tuple, [Size], Elements} - end. - -spec format_error(term()) -> iolist(). format_error({{_M,F,A},{I,Off,limit}}) -> @@ -149,28 +124,6 @@ validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) -> {literal, term()} | nil. --type tuple_sz() :: [non_neg_integer()] | %% Inexact - non_neg_integer(). %% Exact. - -%% Match context type. --record(ms, - {valid=0 :: non_neg_integer(), %Valid slots - slots=0 :: non_neg_integer() %Number of slots - }). - --type type() :: binary | - cons | - list | - map | - nil | - #ms{} | - ms_position | - none | - number | - term | - tuple_in_progress | - {tuple, tuple_sz(), #{ pos_integer() => type() }}. - -type tag() :: initialized | uninitialized | {catchtag, [label()]} | @@ -246,11 +199,7 @@ build_function_table([{function,_,Arity,Entry,Code0}|Fs], Acc0) -> build_function_table([], Acc) -> gb_trees:from_orddict(sort(Acc)). -find_parameter_types([{'%', {type_info, Reg, Type0}} | Is], Acc) -> - Type = case Type0 of - match_context -> #ms{}; - _ -> Type0 - end, +find_parameter_types([{'%', {type_info, Reg, Type}} | Is], Acc) -> find_parameter_types(Is, Acc#{ Reg => Type }); find_parameter_types(_, Acc) -> Acc. @@ -324,7 +273,7 @@ init_vst(Arity, Ls1, Ls2, Ft) -> init_function_args(-1, Vst) -> Vst; init_function_args(X, Vst) -> - init_function_args(X - 1, create_term(term, argument, [], {x,X}, Vst)). + init_function_args(X - 1, create_term(any, argument, [], {x,X}, Vst)). kill_heap_allocation(St) -> St#st{h=0,hf=0}. @@ -383,7 +332,7 @@ valfun_1({bs_get_tail,Ctx,Dst,Live}, Vst0) -> verify_live(Live, Vst0), verify_y_init(Vst0), Vst = prune_x_regs(Live, Vst0), - extract_term(binary, bs_get_tail, [Ctx], Dst, Vst, Vst0); + extract_term(#t_bitstring{}, bs_get_tail, [Ctx], Dst, Vst, Vst0); valfun_1(bs_init_writable=I, Vst) -> call(I, 1, Vst); valfun_1(build_stacktrace=I, Vst) -> @@ -414,7 +363,7 @@ valfun_1({fmove,{fr,_}=Src,Dst}, Vst0) -> assert_freg_set(Src, Vst0), assert_fls(checked, Vst0), Vst = eat_heap_float(Vst0), - create_term({float,[]}, fmove, [], Dst, Vst); + create_term(float, fmove, [], Dst, Vst); valfun_1({kill,Reg}, Vst) -> create_tag(initialized, kill, [], Reg, Vst); valfun_1({init,Reg}, Vst) -> @@ -422,17 +371,16 @@ valfun_1({init,Reg}, Vst) -> valfun_1({test_heap,Heap,Live}, Vst) -> test_heap(Heap, Live, Vst); valfun_1({bif,Op,{f,_},Ss,Dst}=I, Vst) -> - case is_bif_safe(Op, length(Ss)) of - false -> - %% Since the BIF can fail, make sure that any catch state - %% is updated. - valfun_2(I, Vst); - true -> - %% It can't fail, so we finish handling it here (not updating - %% catch state). - validate_src(Ss, Vst), - Type = bif_return_type(Op, Ss, Vst), - extract_term(Type, {bif,Op}, Ss, Dst, Vst) + case beam_call_types:never_throws(erlang, Op, length(Ss)) of + true -> + %% It can't fail, so we finish handling it here (not updating + %% catch state). + {RetType, _, _} = bif_types(Op, Ss, Vst), + extract_term(RetType, {bif,Op}, Ss, Dst, Vst); + false -> + %% Since the BIF can fail, make sure that any catch state + %% is updated. + valfun_2(I, Vst) end; %% Put instructions. valfun_1({put_list,A,B,Dst}, Vst0) -> @@ -446,14 +394,15 @@ valfun_1({put_tuple2,Dst,{list,Elements}}, Vst0) -> Vst = eat_heap(Size+1, Vst0), {Es,_} = foldl(fun(Val, {Es0, Index}) -> Type = get_term_type(Val, Vst0), - Es = set_element_type(Index, Type, Es0), + Es = beam_types:set_element_type(Index, Type, Es0), {Es, Index + 1} end, {#{}, 1}, Elements), - Type = {tuple,Size,Es}, + Type = #t_tuple{exact=true,size=Size,elements=Es}, create_term(Type, put_tuple2, [], Dst, Vst); valfun_1({put_tuple,Sz,Dst}, Vst0) when is_integer(Sz) -> Vst1 = eat_heap(1, Vst0), - Vst = create_term(tuple_in_progress, put_tuple, [], Dst, Vst1), + Vst = create_term(#t_abstract{kind=tuple_in_progress}, put_tuple, [], + Dst, Vst1), #vst{current=St0} = Vst, St = St0#st{puts_left={Sz,{Dst,Sz,#{}}}}, Vst#vst{current=St}; @@ -465,12 +414,15 @@ valfun_1({put,Src}, Vst0) -> #st{puts_left=none} -> error(not_building_a_tuple); #st{puts_left={1,{Dst,Sz,Es0}}} -> - Es = Es0#{ Sz => get_term_type(Src, Vst0) }, + ElementType = get_term_type(Src, Vst0), + Es = beam_types:set_element_type(Sz, ElementType, Es0), St = St0#st{puts_left=none}, - create_term({tuple,Sz,Es}, put_tuple, [], Dst, Vst#vst{current=St}); + Type = #t_tuple{exact=true,size=Sz,elements=Es}, + create_term(Type, put_tuple, [], Dst, Vst#vst{current=St}); #st{puts_left={PutsLeft,{Dst,Sz,Es0}}} when is_integer(PutsLeft) -> Index = Sz - PutsLeft + 1, - Es = Es0#{ Index => get_term_type(Src, Vst0) }, + ElementType = get_term_type(Src, Vst0), + Es = beam_types:set_element_type(Index, ElementType, Es0), St = St0#st{puts_left={PutsLeft-1,{Dst,Sz,Es}}}, Vst#vst{current=St} end; @@ -484,10 +436,10 @@ valfun_1(remove_message, Vst) -> %% The message term is no longer fragile. It can be used %% without restrictions. remove_fragility(Vst); -valfun_1({'%', {type_info, Reg, match_context}}, Vst) -> +valfun_1({'%', {type_info, Reg, #t_bs_context{}=Type}}, Vst) -> %% This is a gross hack, but we'll be rid of it once we have proper union %% types. - override_type(#ms{}, Reg, Vst); + override_type(Type, Reg, Vst); valfun_1({'%', {type_info, Reg, Type}}, Vst) -> %% Explicit type information inserted by optimization passes to indicate %% that Reg has a certain type, so that we can accept cross-function type @@ -507,15 +459,15 @@ valfun_1({line,_}, Vst) -> Vst; %% Exception generating calls valfun_1({call_ext,Live,Func}=I, Vst) -> - case call_return_type(Func, Vst) of - exception -> - verify_live(Live, Vst), + case call_types(Func, Live, Vst) of + {none, _, _} -> + verify_live(Live, Vst), %% The stack will be scanned, so Y registers %% must be initialized. verify_y_init(Vst), - kill_state(Vst); - _ -> - valfun_2(I, Vst) + kill_state(Vst); + _ -> + valfun_2(I, Vst) end; valfun_1(_I, #vst{current=#st{ct=undecided}}) -> error(unknown_catch_try_state); @@ -551,7 +503,7 @@ valfun_1({catch_end,Reg}, #vst{current=#st{ct=[Fail|_]}}=Vst0) -> case get_tag_type(Reg, Vst0) of {catchtag,Fail} -> %% {x,0} contains the caught term, if any. - create_term(term, catch_end, [], {x,0}, kill_catch_tag(Reg, Vst0)); + create_term(any, catch_end, [], {x,0}, kill_catch_tag(Reg, Vst0)); Type -> error({wrong_tag_type,Type}) end; @@ -570,31 +522,32 @@ valfun_1({try_case,Reg}, #vst{current=#st{ct=[Fail|_]}}=Vst0) -> Vst1 = prune_x_regs(0, kill_catch_tag(Reg, Vst0)), %% Class:Error:Stacktrace - Vst2 = create_term({atom,[]}, try_case, [], {x,0}, Vst1), - Vst = create_term(term, try_case, [], {x,1}, Vst2), - create_term(term, try_case, [], {x,2}, Vst); + Vst2 = create_term(#t_atom{}, try_case, [], {x,0}, Vst1), + Vst = create_term(any, try_case, [], {x,1}, Vst2), + create_term(any, try_case, [], {x,2}, Vst); Type -> error({wrong_tag_type,Type}) end; valfun_1({get_list,Src,D1,D2}, Vst0) -> assert_not_literal(Src), assert_type(cons, Src, Vst0), - Vst = extract_term(term, get_hd, [Src], D1, Vst0), - extract_term(term, get_tl, [Src], D2, Vst); + Vst = extract_term(any, get_hd, [Src], D1, Vst0), + extract_term(any, get_tl, [Src], D2, Vst); valfun_1({get_hd,Src,Dst}, Vst) -> assert_not_literal(Src), assert_type(cons, Src, Vst), - extract_term(term, get_hd, [Src], Dst, Vst); + extract_term(any, get_hd, [Src], Dst, Vst); valfun_1({get_tl,Src,Dst}, Vst) -> assert_not_literal(Src), assert_type(cons, Src, Vst), - extract_term(term, get_tl, [Src], Dst, Vst); + extract_term(any, get_tl, [Src], Dst, Vst); valfun_1({get_tuple_element,Src,N,Dst}, Vst) -> Index = N+1, assert_not_literal(Src), - assert_type({tuple_element,Index}, Src, Vst), - Type = get_element_type(Index, Src, Vst), - extract_term(Type, {bif,element}, [{integer, Index}, Src], Dst, Vst); + assert_type(#t_tuple{size=Index}, Src, Vst), + #t_tuple{elements=Es} = get_term_type(Src, Vst), + Type = beam_types:get_element_type(Index, Es), + extract_term(Type, {bif,element}, [{integer,Index}, Src], Dst, Vst); valfun_1({jump,{f,Lbl}}, Vst) -> branch(Lbl, Vst, fun(SuccVst) -> @@ -625,9 +578,9 @@ init_try_catch_branch(Tag, Dst, Fail, Vst0) -> %% Set the initial state at the try/catch label. Assume that Y registers %% contain terms or try/catch tags. init_catch_handler_1(Reg, initialized, Vst) -> - create_term(term, 'catch_handler', [], Reg, Vst); + create_term(any, 'catch_handler', [], Reg, Vst); init_catch_handler_1(Reg, uninitialized, Vst) -> - create_term(term, 'catch_handler', [], Reg, Vst); + create_term(any, 'catch_handler', [], Reg, Vst); init_catch_handler_1(_, _, Vst) -> Vst. @@ -689,8 +642,16 @@ valfun_4({apply,Live}, Vst) -> valfun_4({apply_last,Live,_}, Vst) -> tail_call(apply, Live+2, Vst); valfun_4({call_fun,Live}, Vst) -> - validate_src([{x,Live}], Vst), - call('fun', Live+1, Vst); + Fun = {x,Live}, + assert_term(Fun, Vst), + + %% An exception is raised on error, hence branching to 0. + branch(0, Vst, + fun(SuccVst0) -> + SuccVst = update_type(fun meet/2, #t_fun{arity=Live}, + Fun, SuccVst0), + call('fun', Live+1, SuccVst) + end); valfun_4({call,Live,Func}, Vst) -> call(Func, Live, Vst); valfun_4({call_ext,Live,Func}, Vst) -> @@ -709,58 +670,26 @@ valfun_4({call_ext_last,Live,Func,StkSize}, tail_call(Func, Live, Vst); valfun_4({call_ext_last,_,_,_}, #vst{current=#st{numy=NumY}}) -> error({allocated,NumY}); -valfun_4({make_fun2,_,_,_,Live}, Vst) -> - call(make_fun, Live, Vst); +valfun_4({make_fun2,{f,Lbl},_,_,NumFree}, #vst{ft=Ft}=Vst0) -> + #{ arity := Arity0 } = gb_trees:get(Lbl, Ft), + Arity = Arity0 - NumFree, + + true = Arity >= 0, %Assertion. + + Vst = prune_x_regs(NumFree, Vst0), + verify_call_args(make_fun, NumFree, Vst), + verify_y_init(Vst), + + create_term(#t_fun{arity=Arity}, make_fun, [], {x,0}, Vst); %% Other BIFs -valfun_4({bif,element,{f,Fail},[Pos,Src],Dst}, Vst) -> - branch(Fail, Vst, - fun(SuccVst0) -> - PosType = get_term_type(Pos, SuccVst0), - TupleType = {tuple,[get_tuple_size(PosType)],#{}}, - - SuccVst1 = update_type(fun meet/2, TupleType, - Src, SuccVst0), - SuccVst = update_type(fun meet/2, {integer,[]}, - Pos, SuccVst1), - - ElementType = case PosType of - {integer,Index} -> - get_element_type(Index, Src, SuccVst); - _ -> - term - end, - extract_term(ElementType, {bif,element}, [Pos,Src], - Dst, SuccVst) - end); valfun_4({bif,raise,{f,0},Src,_Dst}, Vst) -> validate_src(Src, Vst), kill_state(Vst); valfun_4(raw_raise=I, Vst) -> call(I, 3, Vst); -valfun_4({bif,Op,{f,Fail},[Src]=Ss,Dst}, Vst) when Op =:= hd; Op =:= tl -> - assert_term(Src, Vst), - branch(Fail, Vst, - fun(FailVst) -> - update_type(fun subtract/2, cons, Src, FailVst) - end, - fun(SuccVst0) -> - SuccVst = update_type(fun meet/2, cons, Src, SuccVst0), - extract_term(term, {bif,Op}, Ss, Dst, SuccVst) - end); valfun_4({bif,Op,{f,Fail},Ss,Dst}, Vst) -> validate_src(Ss, Vst), - branch(Fail, Vst, - fun(SuccVst0) -> - %% Infer argument types. Note that we can't subtract - %% types as the BIF could fail for reasons other than - %% bad argument types. - ArgTypes = bif_arg_types(Op, Ss), - SuccVst = foldl(fun({Arg, T}, V) -> - update_type(fun meet/2, T, Arg, V) - end, SuccVst0, zip(Ss, ArgTypes)), - Type = bif_return_type(Op, Ss, SuccVst), - extract_term(Type, {bif,Op}, Ss, Dst, SuccVst) - end); + validate_bif(bif, Op, Fail, Ss, Dst, Vst, Vst); valfun_4({gc_bif,Op,{f,Fail},Live,Ss,Dst}, #vst{current=St0}=Vst0) -> validate_src(Ss, Vst0), verify_live(Live, Vst0), @@ -771,19 +700,7 @@ valfun_4({gc_bif,Op,{f,Fail},Live,Ss,Dst}, #vst{current=St0}=Vst0) -> St = kill_heap_allocation(St0), Vst = prune_x_regs(Live, Vst0#vst{current=St}), - branch(Fail, Vst, - fun(SuccVst0) -> - ArgTypes = bif_arg_types(Op, Ss), - SuccVst = foldl(fun({Arg, T}, V) -> - update_type(fun meet/2, T, Arg, V) - end, SuccVst0, zip(Ss, ArgTypes)), - - Type = bif_return_type(Op, Ss, SuccVst), - - %% We're passing Vst0 as the original because the - %% registers were pruned before the branch. - extract_term(Type, {gc_bif,Op}, Ss, Dst, SuccVst, Vst0) - end); + validate_bif(gc_bif, Op, Fail, Ss, Dst, Vst0, Vst); valfun_4(return, #vst{current=#st{numy=none}}=Vst) -> assert_durable_term({x,0}, Vst), kill_state(Vst); @@ -795,7 +712,7 @@ valfun_4({loop_rec,{f,Fail},Dst}, Vst) -> %% part of this term must be stored in a Y register. branch(Fail, Vst, fun(SuccVst0) -> - {Ref, SuccVst} = new_value(term, loop_rec, [], SuccVst0), + {Ref, SuccVst} = new_value(any, loop_rec, [], SuccVst0), mark_fragile(Dst, set_reg_vref(Ref, Dst, SuccVst)) end); valfun_4({wait,_}, Vst) -> @@ -815,21 +732,21 @@ valfun_4(send, Vst) -> valfun_4({set_tuple_element,Src,Tuple,N}, Vst) -> I = N + 1, assert_term(Src, Vst), - assert_type({tuple_element,I}, Tuple, Vst), + assert_type(#t_tuple{size=I}, Tuple, Vst), %% Manually update the tuple type; we can't rely on the ordinary update %% helpers as we must support overwriting (rather than just widening or %% narrowing) known elements, and we can't use extract_term either since %% the source tuple may be aliased. - {tuple, Sz, Es0} = get_term_type(Tuple, Vst), - Es = set_element_type(I, get_term_type(Src, Vst), Es0), - override_type({tuple, Sz, Es}, Tuple, Vst); + #t_tuple{elements=Es0}=Type = get_term_type(Tuple, Vst), + Es = beam_types:set_element_type(I, get_term_type(Src, Vst), Es0), + override_type(Type#t_tuple{elements=Es}, Tuple, Vst); %% Match instructions. valfun_4({select_val,Src,{f,Fail},{list,Choices}}, Vst) -> assert_term(Src, Vst), assert_choices(Choices), validate_select_val(Fail, Choices, Src, Vst); valfun_4({select_tuple_arity,Tuple,{f,Fail},{list,Choices}}, Vst) -> - assert_type(tuple, Tuple, Vst), + assert_type(#t_tuple{}, Tuple, Vst), assert_arities(Choices), validate_select_tuple_arity(Fail, Choices, Tuple, Vst); @@ -857,18 +774,34 @@ valfun_4({test,bs_skip_utf16,{f,Fail},[Ctx,Live,_]}, Vst) -> validate_bs_skip_utf(Fail, Ctx, Live, Vst); valfun_4({test,bs_skip_utf32,{f,Fail},[Ctx,Live,_]}, Vst) -> validate_bs_skip_utf(Fail, Ctx, Live, Vst); -valfun_4({test,bs_get_integer2=Op,{f,Fail},Live,[Ctx,_,_,_],Dst}, Vst) -> - validate_bs_get(Op, Fail, Ctx, Live, {integer, []}, Dst, Vst); +valfun_4({test,bs_get_integer2=Op,{f,Fail},Live, + [Ctx,{integer,Size},Unit,{field_flags,Flags}],Dst},Vst) + when Size * Unit =< 64 -> + Type = case member(unsigned, Flags) of + true -> + NumBits = Size * Unit, + beam_types:make_integer(0, (1 bsl NumBits)-1); + false -> + %% Signed integer or way too large, don't bother. + #t_integer{} + end, + validate_bs_get(Op, Fail, Ctx, Live, Type, Dst, Vst); +valfun_4({test,bs_get_integer2=Op,{f,Fail},Live, + [Ctx,_Size,_Unit,_Flags],Dst},Vst) -> + validate_bs_get(Op, Fail, Ctx, Live, #t_integer{}, Dst, Vst); valfun_4({test,bs_get_float2=Op,{f,Fail},Live,[Ctx,_,_,_],Dst}, Vst) -> - validate_bs_get(Op, Fail, Ctx, Live, {float, []}, Dst, Vst); -valfun_4({test,bs_get_binary2=Op,{f,Fail},Live,[Ctx,_,_,_],Dst}, Vst) -> - validate_bs_get(Op, Fail, Ctx, Live, binary, Dst, Vst); + validate_bs_get(Op, Fail, Ctx, Live, float, Dst, Vst); +valfun_4({test,bs_get_binary2=Op,{f,Fail},Live,[Ctx,_,Unit,_],Dst}, Vst) -> + validate_bs_get(Op, Fail, Ctx, Live, #t_bitstring{unit=Unit}, Dst, Vst); valfun_4({test,bs_get_utf8=Op,{f,Fail},Live,[Ctx,_],Dst}, Vst) -> - validate_bs_get(Op, Fail, Ctx, Live, {integer, []}, Dst, Vst); + Type = beam_types:make_integer(0, ?UNICODE_MAX), + validate_bs_get(Op, Fail, Ctx, Live, Type, Dst, Vst); valfun_4({test,bs_get_utf16=Op,{f,Fail},Live,[Ctx,_],Dst}, Vst) -> - validate_bs_get(Op, Fail, Ctx, Live, {integer, []}, Dst, Vst); + Type = beam_types:make_integer(0, ?UNICODE_MAX), + validate_bs_get(Op, Fail, Ctx, Live, Type, Dst, Vst); valfun_4({test,bs_get_utf32=Op,{f,Fail},Live,[Ctx,_],Dst}, Vst) -> - validate_bs_get(Op, Fail, Ctx, Live, {integer, []}, Dst, Vst); + Type = beam_types:make_integer(0, ?UNICODE_MAX), + validate_bs_get(Op, Fail, Ctx, Live, Type, Dst, Vst); valfun_4({bs_save2,Ctx,SavePoint}, Vst) -> bsm_save(Ctx, SavePoint, Vst); valfun_4({bs_restore2,Ctx,SavePoint}, Vst) -> @@ -878,31 +811,32 @@ valfun_4({bs_get_position, Ctx, Dst, Live}, Vst0) -> verify_live(Live, Vst0), verify_y_init(Vst0), Vst = prune_x_regs(Live, Vst0), - create_term(ms_position, bs_get_position, [Ctx], Dst, Vst, Vst0); + create_term(#t_abstract{kind=ms_position}, bs_get_position, [Ctx], + Dst, Vst, Vst0); valfun_4({bs_set_position, Ctx, Pos}, Vst) -> bsm_validate_context(Ctx, Vst), - assert_type(ms_position, Pos, Vst), + assert_type(#t_abstract{kind=ms_position}, Pos, Vst), Vst; %% Other test instructions. valfun_4({test,has_map_fields,{f,Lbl},Src,{list,List}}, Vst) -> - assert_type(map, Src, Vst), + assert_type(#t_map{}, Src, Vst), assert_unique_map_keys(List), branch(Lbl, Vst, fun(V) -> V end); valfun_4({test,is_atom,{f,Lbl},[Src]}, Vst) -> - type_test(Lbl, {atom,[]}, Src, Vst); + type_test(Lbl, #t_atom{}, Src, Vst); valfun_4({test,is_binary,{f,Lbl},[Src]}, Vst) -> - type_test(Lbl, binary, Src, Vst); + type_test(Lbl, #t_bitstring{unit=8}, Src, Vst); valfun_4({test,is_bitstr,{f,Lbl},[Src]}, Vst) -> - type_test(Lbl, binary, Src, Vst); + type_test(Lbl, #t_bitstring{}, Src, Vst); valfun_4({test,is_boolean,{f,Lbl},[Src]}, Vst) -> - type_test(Lbl, bool, Src, Vst); + type_test(Lbl, beam_types:make_boolean(), Src, Vst); valfun_4({test,is_float,{f,Lbl},[Src]}, Vst) -> - type_test(Lbl, {float,[]}, Src, Vst); + type_test(Lbl, float, Src, Vst); valfun_4({test,is_tuple,{f,Lbl},[Src]}, Vst) -> - type_test(Lbl, {tuple,[0],#{}}, Src, Vst); + type_test(Lbl, #t_tuple{}, Src, Vst); valfun_4({test,is_integer,{f,Lbl},[Src]}, Vst) -> - type_test(Lbl, {integer,[]}, Src, Vst); + type_test(Lbl, #t_integer{}, Src, Vst); valfun_4({test,is_nonempty_list,{f,Lbl},[Src]}, Vst) -> type_test(Lbl, cons, Src, Vst); valfun_4({test,is_number,{f,Lbl},[Src]}, Vst) -> @@ -910,7 +844,7 @@ valfun_4({test,is_number,{f,Lbl},[Src]}, Vst) -> valfun_4({test,is_list,{f,Lbl},[Src]}, Vst) -> type_test(Lbl, list, Src, Vst); valfun_4({test,is_map,{f,Lbl},[Src]}, Vst) -> - type_test(Lbl, map, Src, Vst); + type_test(Lbl, #t_map{}, Src, Vst); valfun_4({test,is_nil,{f,Lbl},[Src]}, Vst) -> %% is_nil is an exact check against the 'nil' value, and should not be %% treated as a simple type test. @@ -923,12 +857,13 @@ valfun_4({test,is_nil,{f,Lbl},[Src]}, Vst) -> update_eq_types(Src, nil, SuccVst) end); valfun_4({test,test_arity,{f,Lbl},[Tuple,Sz]}, Vst) when is_integer(Sz) -> - assert_type(tuple, Tuple, Vst), - Type = {tuple, Sz, #{}}, + assert_type(#t_tuple{}, Tuple, Vst), + Type = #t_tuple{exact=true,size=Sz}, type_test(Lbl, Type, Tuple, Vst); valfun_4({test,is_tagged_tuple,{f,Lbl},[Src,Sz,Atom]}, Vst) -> assert_term(Src, Vst), - Type = {tuple, Sz, #{ 1 => Atom }}, + Es = #{ 1 => get_literal_type(Atom) }, + Type = #t_tuple{exact=true,size=Sz,elements=Es}, type_test(Lbl, Type, Src, Vst); valfun_4({test,is_eq_exact,{f,Lbl},[Src,Val]=Ss}, Vst) -> validate_src(Ss, Vst), @@ -957,19 +892,19 @@ valfun_4({bs_add,{f,Fail},[A,B,_],Dst}, Vst) -> assert_term(B, Vst), branch(Fail, Vst, fun(SuccVst) -> - create_term({integer,[]}, bs_add, [A, B], Dst, SuccVst) + create_term(#t_integer{}, bs_add, [A, B], Dst, SuccVst) end); valfun_4({bs_utf8_size,{f,Fail},A,Dst}, Vst) -> assert_term(A, Vst), branch(Fail, Vst, fun(SuccVst) -> - create_term({integer,[]}, bs_utf8_size, [A], Dst, SuccVst) + create_term(#t_integer{}, bs_utf8_size, [A], Dst, SuccVst) end); valfun_4({bs_utf16_size,{f,Fail},A,Dst}, Vst) -> assert_term(A, Vst), branch(Fail, Vst, fun(SuccVst) -> - create_term({integer,[]}, bs_utf16_size, [A], Dst, SuccVst) + create_term(#t_integer{}, bs_utf16_size, [A], Dst, SuccVst) end); valfun_4({bs_init2,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) -> verify_live(Live, Vst0), @@ -984,7 +919,8 @@ valfun_4({bs_init2,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) -> branch(Fail, Vst, fun(SuccVst0) -> SuccVst = prune_x_regs(Live, SuccVst0), - create_term(binary, bs_init2, [], Dst, SuccVst, SuccVst0) + create_term(#t_bitstring{unit=8}, bs_init2, [], Dst, + SuccVst, SuccVst0) end); valfun_4({bs_init_bits,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) -> verify_live(Live, Vst0), @@ -999,9 +935,9 @@ valfun_4({bs_init_bits,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) -> branch(Fail, Vst, fun(SuccVst0) -> SuccVst = prune_x_regs(Live, SuccVst0), - create_term(binary, bs_init_bits, [], Dst, SuccVst) + create_term(#t_bitstring{}, bs_init_bits, [], Dst, SuccVst) end); -valfun_4({bs_append,{f,Fail},Bits,Heap,Live,_Unit,Bin,_Flags,Dst}, Vst0) -> +valfun_4({bs_append,{f,Fail},Bits,Heap,Live,Unit,Bin,_Flags,Dst}, Vst0) -> verify_live(Live, Vst0), verify_y_init(Vst0), assert_term(Bits, Vst0), @@ -1010,14 +946,16 @@ valfun_4({bs_append,{f,Fail},Bits,Heap,Live,_Unit,Bin,_Flags,Dst}, Vst0) -> branch(Fail, Vst, fun(SuccVst0) -> SuccVst = prune_x_regs(Live, SuccVst0), - create_term(binary, bs_append, [Bin], Dst, SuccVst, SuccVst0) + create_term(#t_bitstring{unit=Unit}, bs_append, + [Bin], Dst, SuccVst, SuccVst0) end); -valfun_4({bs_private_append,{f,Fail},Bits,_Unit,Bin,_Flags,Dst}, Vst) -> +valfun_4({bs_private_append,{f,Fail},Bits,Unit,Bin,_Flags,Dst}, Vst) -> assert_term(Bits, Vst), assert_term(Bin, Vst), branch(Fail, Vst, fun(SuccVst) -> - create_term(binary, bs_private_append, [Bin], Dst, SuccVst) + create_term(#t_bitstring{unit=Unit}, bs_private_append, + [Bin], Dst, SuccVst) end); valfun_4({bs_put_string,Sz,_}, Vst) when is_integer(Sz) -> Vst; @@ -1026,39 +964,39 @@ valfun_4({bs_put_binary,{f,Fail},Sz,_,_,Src}, Vst) -> assert_term(Src, Vst), branch(Fail, Vst, fun(SuccVst) -> - update_type(fun meet/2, binary, Src, SuccVst) + update_type(fun meet/2, #t_bitstring{}, Src, SuccVst) end); valfun_4({bs_put_float,{f,Fail},Sz,_,_,Src}, Vst) -> assert_term(Sz, Vst), assert_term(Src, Vst), branch(Fail, Vst, fun(SuccVst) -> - update_type(fun meet/2, {float,[]}, Src, SuccVst) + update_type(fun meet/2, float, Src, SuccVst) end); valfun_4({bs_put_integer,{f,Fail},Sz,_,_,Src}, Vst) -> assert_term(Sz, Vst), assert_term(Src, Vst), branch(Fail, Vst, fun(SuccVst) -> - update_type(fun meet/2, {integer,[]}, Src, SuccVst) + update_type(fun meet/2, #t_integer{}, Src, SuccVst) end); valfun_4({bs_put_utf8,{f,Fail},_,Src}, Vst) -> assert_term(Src, Vst), branch(Fail, Vst, fun(SuccVst) -> - update_type(fun meet/2, {integer,[]}, Src, SuccVst) + update_type(fun meet/2, #t_integer{}, Src, SuccVst) end); valfun_4({bs_put_utf16,{f,Fail},_,Src}, Vst) -> assert_term(Src, Vst), branch(Fail, Vst, fun(SuccVst) -> - update_type(fun meet/2, {integer,[]}, Src, SuccVst) + update_type(fun meet/2, #t_integer{}, Src, SuccVst) end); valfun_4({bs_put_utf32,{f,Fail},_,Src}, Vst) -> assert_term(Src, Vst), branch(Fail, Vst, fun(SuccVst) -> - update_type(fun meet/2, {integer,[]}, Src, SuccVst) + update_type(fun meet/2, #t_integer{}, Src, SuccVst) end); %% Map instructions. valfun_4({put_map_assoc=Op,{f,Fail},Src,Dst,Live,{list,List}}, Vst) -> @@ -1072,7 +1010,7 @@ valfun_4(_, _) -> verify_get_map(Fail, Src, List, Vst0) -> assert_not_literal(Src), %OTP 22. - assert_type(map, Src, Vst0), + assert_type(#t_map{}, Src, Vst0), branch(Fail, Vst0, fun(FailVst) -> @@ -1093,7 +1031,7 @@ verify_get_map(Fail, Src, List, Vst0) -> clobber_map_vals([Key,Dst|T], Map, Vst0) -> case is_reg_defined(Dst, Vst0) of true -> - Vst = extract_term(term, {bif,map_get}, [Key, Map], Dst, Vst0), + Vst = extract_term(any, {bif,map_get}, [Key, Map], Dst, Vst0), clobber_map_vals(T, Map, Vst); false -> clobber_map_vals(T, Map, Vst0) @@ -1107,13 +1045,13 @@ extract_map_keys([]) -> []. extract_map_vals([Key,Dst|Vs], Map, Vst0, Vsti0) -> assert_term(Key, Vst0), - Vsti = extract_term(term, {bif,map_get}, [Key, Map], Dst, Vsti0), + Vsti = extract_term(any, {bif,map_get}, [Key, Map], Dst, Vsti0), extract_map_vals(Vs, Map, Vst0, Vsti); extract_map_vals([], _Map, _Vst0, Vst) -> Vst. verify_put_map(Op, Fail, Src, Dst, Live, List, Vst0) -> - assert_type(map, Src, Vst0), + assert_type(#t_map{}, Src, Vst0), verify_live(Live, Vst0), verify_y_init(Vst0), _ = [assert_term(Term, Vst0) || Term <- List], @@ -1124,9 +1062,39 @@ verify_put_map(Op, Fail, Src, Dst, Live, List, Vst0) -> SuccVst = prune_x_regs(Live, SuccVst0), Keys = extract_map_keys(List), assert_unique_map_keys(Keys), - create_term(map, Op, [Src], Dst, SuccVst, SuccVst0) + create_term(#t_map{}, Op, [Src], Dst, SuccVst, SuccVst0) end). +%% +%% Common code for validating BIFs. +%% +%% OrigVst is the state we entered the instruction with, which is needed for +%% gc_bifs as X registers are pruned prior to calling this function, which may +%% have clobbered the sources. +%% +validate_bif(Kind, Op, Fail, Ss, Dst, OrigVst, Vst) -> + {Type, ArgTypes, CanSubtract} = bif_types(Op, Ss, Vst), + ZippedArgs = zip(Ss, ArgTypes), + + FailFun = case CanSubtract of + true -> + fun(FailVst0) -> + foldl(fun({A, T}, V) -> + update_type(fun subtract/2, T, A, V) + end, FailVst0, ZippedArgs) + end; + false -> + fun(S) -> S end + end, + SuccFun = fun(SuccVst0) -> + SuccVst = foldl(fun({A, T}, V) -> + update_type(fun meet/2, T, A, V) + end, SuccVst0, ZippedArgs), + extract_term(Type, {Kind,Op}, Ss, Dst, SuccVst, OrigVst) + end, + + branch(Fail, Vst, FailFun, SuccFun). + %% %% Common code for validating bs_start_match* instructions. %% @@ -1135,18 +1103,18 @@ validate_bs_start_match(Fail, Live, Type, Src, Dst, Vst) -> verify_live(Live, Vst), verify_y_init(Vst), - %% #ms{} can represent either a match context or a term, so we have to mark - %% the source as a term if it fails with a match context as an input. This - %% hack is only needed until we get proper union types. + %% #t_bs_context{} can represent either a match context or a term, so we + %% have to mark the source as a term if it fails with a match context as an + %% input. This hack is only needed until we get proper union types. branch(Fail, Vst, fun(FailVst) -> case get_movable_term_type(Src, FailVst) of - #ms{} -> override_type(term, Src, FailVst); + #t_bs_context{} -> override_type(any, Src, FailVst); _ -> FailVst end end, fun(SuccVst0) -> - SuccVst1 = update_type(fun meet/2, binary, + SuccVst1 = update_type(fun meet/2, #t_bitstring{}, Src, SuccVst0), SuccVst = prune_x_regs(Live, SuccVst1), extract_term(Type, bs_start_match, [Src], Dst, @@ -1225,12 +1193,12 @@ kill_state(Vst) -> call(Name, Live, #vst{current=St0}=Vst0) -> verify_call_args(Name, Live, Vst0), verify_y_init(Vst0), - case call_return_type(Name, Vst0) of - Type when Type =/= exception -> - %% Type is never 'exception' because it has been handled earlier. + case call_types(Name, Live, Vst0) of + {RetType, _, _} -> + %% Type is never 'none' because it has been handled earlier. St = St0#st{f=init_fregs()}, Vst = prune_x_regs(0, Vst0#vst{current=St}), - create_term(Type, call, [], {x,0}, Vst) + create_term(RetType, call, [], {x,0}, Vst) end. %% Tail call. @@ -1271,7 +1239,7 @@ verify_local_args(X, ParamTypes, CtxRefs, Vst) -> Reg = {x, X}, assert_not_fragile(Reg, Vst), case get_movable_term_type(Reg, Vst) of - #ms{}=Type -> + #t_bs_context{}=Type -> VRef = get_reg_vref(Reg, Vst), case CtxRefs of #{ VRef := Other } -> @@ -1287,65 +1255,28 @@ verify_local_args(X, ParamTypes, CtxRefs, Vst) -> end. %% Verifies that the given argument narrows to what the function expects. -verify_arg_type(Reg, #ms{}, ParamTypes) -> +verify_arg_type(Reg, #t_bs_context{}, ParamTypes) -> %% Match contexts require explicit support, and may not be passed to a %% function that accepts arbitrary terms. case ParamTypes of - #{ Reg := #ms{}} -> ok; + #{ Reg := #t_bs_context{}} -> ok; #{} -> error(no_bs_start_match2) end; verify_arg_type(Reg, GivenType, ParamTypes) -> case ParamTypes of - #{ Reg := #ms{}} -> + #{ Reg := #t_bs_context{}} -> %% Functions that accept match contexts also accept all other %% terms. This will change once we support union types. ok; #{ Reg := RequiredType } -> - case vat_1(GivenType, RequiredType) of - true -> ok; - false -> error({bad_arg_type, Reg, GivenType, RequiredType}) + case meet(GivenType, RequiredType) of + GivenType -> ok; + _ -> error({bad_arg_type, Reg, GivenType, RequiredType}) end; #{} -> ok end. -%% Checks whether the Given argument is compatible with the Required one. This -%% is essentially a relaxed version of 'meet(Given, Req) =:= Given', where we -%% accept that the Given value has the right type but not necessarily the exact -%% same value; if {atom,gurka} is required, we'll consider {atom,[]} valid. -%% -%% This will catch all problems that could crash the emulator, like passing a -%% 1-tuple when the callee expects a 3-tuple, but some value errors might slip -%% through. -vat_1(Same, Same) -> true; -vat_1({atom,A}, {atom,B}) -> A =:= B orelse is_list(A) orelse is_list(B); -vat_1({atom,A}, bool) -> is_boolean(A) orelse is_list(A); -vat_1(bool, {atom,B}) -> is_boolean(B) orelse is_list(B); -vat_1(cons, list) -> true; -vat_1({float,A}, {float,B}) -> A =:= B orelse is_list(A) orelse is_list(B); -vat_1({float,_}, number) -> true; -vat_1({integer,A}, {integer,B}) -> A =:= B orelse is_list(A) orelse is_list(B); -vat_1({integer,_}, number) -> true; -vat_1(nil, list) -> true; -vat_1({tuple,SzA,EsA}, {tuple,SzB,EsB}) -> - if - is_list(SzB) -> - tuple_sz(SzA) >= tuple_sz(SzB) andalso vat_elements(EsA, EsB); - SzA =:= SzB -> - vat_elements(EsA, EsB); - SzA =/= SzB -> - false - end; -vat_1(_, _) -> false. - -vat_elements(EsA, EsB) -> - maps:fold(fun(Key, Req, Acc) -> - case EsA of - #{ Key := Given } -> Acc andalso vat_1(Given, Req); - #{} -> false - end - end, true, EsB). - allocate(Tag, Stk, Heap, Live, #vst{current=#st{numy=none}=St}=Vst0) -> verify_live(Live, Vst0), Vst1 = Vst0#vst{current=St#st{numy=Stk}}, @@ -1527,9 +1458,9 @@ assert_unique_map_keys([_,_|_]=Ls) -> %%% bsm_match_state() -> - #ms{}. + #t_bs_context{}. bsm_match_state(Slots) -> - #ms{slots=Slots}. + #t_bs_context{slots=Slots}. bsm_validate_context(Reg, Vst) -> _ = bsm_get_context(Reg, Vst), @@ -1537,7 +1468,7 @@ bsm_validate_context(Reg, Vst) -> bsm_get_context({Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y-> case get_movable_term_type(Reg, Vst) of - #ms{}=Ctx -> Ctx; + #t_bs_context{}=Ctx -> Ctx; _ -> error({no_bsm_context,Reg}) end; bsm_get_context(Reg, _) -> @@ -1550,8 +1481,8 @@ bsm_save(Reg, {atom,start}, Vst) -> Vst; bsm_save(Reg, SavePoint, Vst) -> case bsm_get_context(Reg, Vst) of - #ms{valid=Bits,slots=Slots}=Ctxt0 when SavePoint < Slots -> - Ctx = Ctxt0#ms{valid=Bits bor (1 bsl SavePoint),slots=Slots}, + #t_bs_context{valid=Bits,slots=Slots}=Ctxt0 when SavePoint < Slots -> + Ctx = Ctxt0#t_bs_context{valid=Bits bor (1 bsl SavePoint),slots=Slots}, override_type(Ctx, Reg, Vst); _ -> error({illegal_save,SavePoint}) end. @@ -1563,7 +1494,7 @@ bsm_restore(Reg, {atom,start}, Vst) -> Vst; bsm_restore(Reg, SavePoint, Vst) -> case bsm_get_context(Reg, Vst) of - #ms{valid=Bits,slots=Slots} when SavePoint < Slots -> + #t_bs_context{valid=Bits,slots=Slots} when SavePoint < Slots -> case Bits band (1 bsl SavePoint) of 0 -> error({illegal_restore,SavePoint,not_set}); _ -> Vst @@ -1596,7 +1527,7 @@ validate_select_tuple_arity(_Fail, _Choices, _Src, #vst{current=none}=Vst) -> %% can't reach the fail label or any of the remaining choices. Vst; validate_select_tuple_arity(Fail, [Arity,{f,L}|T], Tuple, Vst0) -> - Type = {tuple, Arity, #{}}, + Type = #t_tuple{exact=true,size=Arity}, Vst = branch(L, Vst0, fun(BranchVst) -> update_type(fun meet/2, Type, Tuple, BranchVst) @@ -1635,37 +1566,42 @@ infer_types_1(#value{op={bif,element},args=[{integer,Index},Tuple]}) -> fun(Val, S) -> case is_value_alive(Tuple, S) of true -> - Type = {tuple,[Index], #{ Index => get_term_type(Val, S) }}, + ElementType = get_term_type(Val, S), + Es = beam_types:set_element_type(Index, ElementType, #{}), + Type = #t_tuple{size=Index,elements=Es}, update_type(fun meet/2, Type, Tuple, S); false -> S end end; infer_types_1(#value{op={bif,is_atom},args=[Src]}) -> - infer_type_test_bif({atom,[]}, Src); + infer_type_test_bif(#t_atom{}, Src); infer_types_1(#value{op={bif,is_boolean},args=[Src]}) -> - infer_type_test_bif(bool, Src); + infer_type_test_bif(beam_types:make_boolean(), Src); infer_types_1(#value{op={bif,is_binary},args=[Src]}) -> - infer_type_test_bif(binary, Src); + infer_type_test_bif(#t_bitstring{unit=8}, Src); infer_types_1(#value{op={bif,is_bitstring},args=[Src]}) -> - infer_type_test_bif(binary, Src); + infer_type_test_bif(#t_bitstring{}, Src); infer_types_1(#value{op={bif,is_float},args=[Src]}) -> infer_type_test_bif(float, Src); infer_types_1(#value{op={bif,is_integer},args=[Src]}) -> - infer_type_test_bif({integer,{}}, Src); + infer_type_test_bif(#t_integer{}, Src); infer_types_1(#value{op={bif,is_list},args=[Src]}) -> infer_type_test_bif(list, Src); infer_types_1(#value{op={bif,is_map},args=[Src]}) -> - infer_type_test_bif(map, Src); + infer_type_test_bif(#t_map{}, Src); infer_types_1(#value{op={bif,is_number},args=[Src]}) -> infer_type_test_bif(number, Src); infer_types_1(#value{op={bif,is_tuple},args=[Src]}) -> - infer_type_test_bif({tuple,[0],#{}}, Src); + infer_type_test_bif(#t_tuple{}, Src); infer_types_1(#value{op={bif,tuple_size}, args=[Tuple]}) -> fun({integer,Arity}, S) -> case is_value_alive(Tuple, S) of - true -> update_type(fun meet/2, {tuple,Arity,#{}}, Tuple, S); - false -> S + true -> + Type = #t_tuple{exact=true,size=Arity}, + update_type(fun meet/2, Type, Tuple, S); + false -> + S end; (_, S) -> S end; @@ -1794,11 +1730,11 @@ update_type(Merge, With, #value_ref{}=Ref, Vst) -> update_type(Merge, With, {Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y -> update_type(Merge, With, get_reg_vref(Reg, Vst), Vst); update_type(Merge, With, Literal, Vst) -> - assert_literal(Literal), %% Literals always retain their type, but we still need to bail on type %% conflicts. - case Merge(Literal, With) of - none -> throw({type_conflict, Literal, With}); + Type = get_literal_type(Literal), + case Merge(Type, With) of + none -> throw({type_conflict, Type, With}); _Type -> Vst end. @@ -1823,25 +1759,23 @@ update_ne_types(LHS, {atom,Bool}=RHS, Vst) when is_boolean(Bool) -> %% but it can't fail either because we also know that {x,1} is a boolean, %% and the first check ruled out 'false'. LType = get_term_type(LHS, Vst), - if - LType =:= bool -> - update_eq_types(LHS, {atom, not Bool}, Vst); - LType =/= bool -> - RType = get_term_type(RHS, Vst), - update_type(fun subtract/2, RType, LHS, Vst) + RType = get_term_type(RHS, Vst), + case beam_types:is_boolean_type(LType) of + true -> update_eq_types(LHS, {atom, not Bool}, Vst); + false -> update_type(fun subtract/2, RType, LHS, Vst) end; update_ne_types(LHS, RHS, Vst) -> %% While updating types on equality is fairly straightforward, inequality %% is a bit trickier since all we know is that the *value* of LHS differs %% from RHS, so we can't blindly subtract their types. %% - %% Consider `number =/= {integer,[]}`; all we know is that LHS isn't equal + %% Consider `number =/= #t_integer{}`; all we know is that LHS isn't equal %% to some *specific integer* of unknown value, and if we were to subtract - %% {integer,[]} we would erroneously infer that the new type is {float,[]}. + %% #t_integer{} we would erroneously infer that the new type is float. %% %% Therefore, we only subtract when we know that RHS has a specific value. RType = get_term_type(RHS, Vst), - case is_literal(RType) of + case beam_types:is_singleton_type(RType) of true -> update_type(fun subtract/2, RType, LHS, Vst); false -> Vst end. @@ -1974,266 +1908,41 @@ is_literal(_) -> false. %% %% First non-term types: %% -%% initialized Only for Y registers. Means that the Y register -%% has been initialized with some valid term so that -%% it is safe to pass to the garbage collector. -%% NOT safe to use in any other way (will not crash the -%% emulator, but clearly points to a bug in the compiler). -%% -%% {catchtag,[Lbl]} A special term used within a catch. Must only be used -%% by the catch instructions; NOT safe to use in other -%% instructions. -%% -%% {trytag,[Lbl]} A special term used within a try block. Must only be -%% used by the catch instructions; NOT safe to use in other -%% instructions. -%% -%% exception Can only be used as a type returned by -%% call_return_type/2 (which gives the type of the value -%% returned by a call). Thus 'exception' is never stored -%% as type descriptor for a register. -%% -%% #ms{} A match context for bit syntax matching. We do allow -%% it to moved/to from stack, but otherwise it must only -%% be accessed by bit syntax matching instructions. -%% -%% -%% Normal terms: -%% -%% term Any valid Erlang (but not of the special types above). -%% -%% binary Binary or bitstring. -%% -%% bool The atom 'true' or the atom 'false'. -%% -%% cons Cons cell: [_|_] -%% -%% nil Empty list: [] +%% initialized Only for Y registers. Means that the Y register +%% has been initialized with some valid term so that +%% it is safe to pass to the garbage collector. +%% NOT safe to use in any other way (will not crash the +%% emulator, but clearly points to a bug in the compiler). %% -%% list List: [] or [_|_] +%% {catchtag,[Lbl]} A special term used within a catch. Must only be used +%% by the catch instructions; NOT safe to use in other +%% instructions. %% -%% {tuple,[Sz],Es} Tuple. An element has been accessed using -%% element/2 or setelement/3 so that it is known that -%% the type is a tuple of size at least Sz. Es is a map -%% containing known types by tuple index. +%% {trytag,[Lbl]} A special term used within a try block. Must only be +%% used by the catch instructions; NOT safe to use in other +%% instructions. %% -%% {tuple,Sz,Es} Tuple. A test_arity instruction has been seen -%% so that it is known that the size is exactly Sz. -%% -%% {atom,[]} Atom. -%% {atom,Atom} -%% -%% {integer,[]} Integer. -%% {integer,Integer} -%% -%% {float,[]} Float. -%% {float,Float} -%% -%% number Integer or Float of unknown value -%% -%% map Map. -%% -%% none A conflict in types. There will be an exception at runtime. +%% #t_bs_context{} A match context for bit syntax matching. We do allow +%% it to moved/to from stack, but otherwise it must only +%% be accessed by bit syntax matching instructions. %% +%% These are simple wrappers around -%% join(Type1, Type2) -> Type -%% Return the most specific type possible. -join(Same, Same) -> - Same; -join(none, Other) -> - Other; -join(Other, none) -> - Other; -join({tuple,Size,EsA}, {tuple,Size,EsB}) -> - Es = join_tuple_elements(tuple_sz(Size), EsA, EsB), - {tuple, Size, Es}; -join({tuple,A,EsA}, {tuple,B,EsB}) -> - Size = min(tuple_sz(A), tuple_sz(B)), - Es = join_tuple_elements(Size, EsA, EsB), - {tuple, [Size], Es}; -join({Type,A}, {Type,B}) - when Type =:= atom; Type =:= integer; Type =:= float -> - if A =:= B -> {Type,A}; - true -> {Type,[]} - end; -join({Type,_}, number) - when Type =:= integer; Type =:= float -> - number; -join(number, {Type,_}) - when Type =:= integer; Type =:= float -> - number; -join({integer,_}, {float,_}) -> - number; -join({float,_}, {integer,_}) -> - number; -join(bool, {atom,A}) -> - join_bool(A); -join({atom,A}, bool) -> - join_bool(A); -join({atom,A}, {atom,B}) when is_boolean(A), is_boolean(B) -> - bool; -join({atom,_}, {atom,_}) -> - {atom,[]}; -join(#ms{valid=B1,slots=Slots1}, - #ms{valid=B2,slots=Slots2}) -> - #ms{valid=B1 band B2,slots=min(Slots1, Slots2)}; -join(T1, T2) when T1 =/= T2 -> - %% We've exhaused all other options, so the type must either be a list or - %% a 'term'. - join_list(T1, T2). - -join_tuple_elements(Limit, EsA, EsB) -> - Es0 = join_elements(EsA, EsB), - maps:filter(fun(Index, _Type) -> Index =< Limit end, Es0). - -join_elements(Es1, Es2) -> - Keys = if - map_size(Es1) =< map_size(Es2) -> maps:keys(Es1); - map_size(Es1) > map_size(Es2) -> maps:keys(Es2) - end, - join_elements_1(Keys, Es1, Es2, #{}). +join(#t_abstract{}=Same, #t_abstract{}=Same) -> Same; +join(A, B) -> beam_types:join(A, B). -join_elements_1([Key | Keys], Es1, Es2, Acc0) -> - Type = case {Es1, Es2} of - {#{ Key := Same }, #{ Key := Same }} -> Same; - {#{ Key := Type1 }, #{ Key := Type2 }} -> join(Type1, Type2); - {#{}, #{}} -> term - end, - Acc = set_element_type(Key, Type, Acc0), - join_elements_1(Keys, Es1, Es2, Acc); -join_elements_1([], _Es1, _Es2, Acc) -> - Acc. +meet(#t_abstract{}=Same, #t_abstract{}=Same) -> Same; +meet(A, B) -> beam_types:meet(A, B). -join_list(nil, cons) -> list; -join_list(nil, list) -> list; -join_list(cons, list) -> list; -join_list(T, nil) -> join_list(nil, T); -join_list(T, cons) -> join_list(cons, T); -join_list(_, _) -> - %% Not a list, so it must be a term. - term. - -join_bool([]) -> {atom,[]}; -join_bool(true) -> bool; -join_bool(false) -> bool; -join_bool(_) -> {atom,[]}. - -%% meet(Type1, Type2) -> Type -%% Return the meet of two types. The meet is a more specific type. -%% It will be 'none' if the types are in conflict. - -meet(Same, Same) -> - Same; -meet(term, Other) -> - Other; -meet(Other, term) -> - Other; -meet(T1, T2) -> - case {erlang:min(T1, T2),erlang:max(T1, T2)} of - {{atom,_}=A,{atom,[]}} -> A; - {bool,{atom,B}=Atom} when is_boolean(B) -> Atom; - {bool,{atom,[]}} -> bool; - {cons,list} -> cons; - {{float,_}=T,{float,[]}} -> T; - {{integer,_}=T,{integer,[]}} -> T; - {list,nil} -> nil; - {number,{integer,_}=T} -> T; - {number,{float,_}=T} -> T; - {{tuple,Size1,Es1},{tuple,Size2,Es2}} -> - Es = meet_elements(Es1, Es2), - case {Size1,Size2,Es} of - {_, _, none} -> - none; - {[Sz1],[Sz2],_} -> - Sz = erlang:max(Sz1, Sz2), - assert_tuple_elements(Sz, Es), - {tuple,[Sz],Es}; - {Sz1,[Sz2],_} when Sz2 =< Sz1 -> - assert_tuple_elements(Sz1, Es), - {tuple,Sz1,Es}; - {Sz,Sz,_} -> - assert_tuple_elements(Sz, Es), - {tuple,Sz,Es}; - {_,_,_} -> - none - end; - {_,_} -> none - end. - -meet_elements(Es1, Es2) -> - Keys = maps:keys(Es1) ++ maps:keys(Es2), - meet_elements_1(Keys, Es1, Es2, #{}). - -meet_elements_1([Key | Keys], Es1, Es2, Acc) -> - case {Es1, Es2} of - {#{ Key := Type1 }, #{ Key := Type2 }} -> - case meet(Type1, Type2) of - none -> none; - Type -> meet_elements_1(Keys, Es1, Es2, Acc#{ Key => Type }) - end; - {#{ Key := Type1 }, _} -> - meet_elements_1(Keys, Es1, Es2, Acc#{ Key => Type1 }); - {_, #{ Key := Type2 }} -> - meet_elements_1(Keys, Es1, Es2, Acc#{ Key => Type2 }) - end; -meet_elements_1([], _Es1, _Es2, Acc) -> - Acc. - -%% No tuple elements may have an index above the known size. -assert_tuple_elements(Limit, Es) -> - true = maps:fold(fun(Index, _T, true) -> - Index =< Limit - end, true, Es). %Assertion. - -%% subtract(Type1, Type2) -> Type -%% Subtract Type2 from Type2. Example: -%% subtract(list, nil) -> cons - -subtract(Same, Same) -> none; -subtract(list, nil) -> cons; -subtract(list, cons) -> nil; -subtract(number, {integer,[]}) -> {float,[]}; -subtract(number, {float,[]}) -> {integer,[]}; -subtract(bool, {atom,false}) -> {atom, true}; -subtract(bool, {atom,true}) -> {atom, false}; -subtract(Type, _) -> Type. - -assert_type(WantedType, Term, Vst) -> - Type = get_term_type(Term, Vst), - assert_type(WantedType, Type). - -assert_type(Correct, Correct) -> ok; -assert_type(float, {float,_}) -> ok; -assert_type(tuple, {tuple,_,_}) -> ok; -assert_type({tuple_element,I}, {tuple,[Sz],_}) - when 1 =< I, I =< Sz -> - ok; -assert_type({tuple_element,I}, {tuple,Sz,_}) - when is_integer(Sz), 1 =< I, I =< Sz -> - ok; -assert_type(Needed, Actual) -> - error({bad_type,{needed,Needed},{actual,Actual}}). +subtract(A, B) -> beam_types:subtract(A, B). -get_element_type(Key, Src, Vst) -> - get_element_type_1(Key, get_term_type(Src, Vst)). - -get_element_type_1(Key, {tuple,_Sz,Es}) -> - case Es of - #{ Key := Type } -> Type; - #{} -> term +assert_type(RequiredType, Term, Vst) -> + GivenType = get_term_type(Term, Vst), + case meet(RequiredType, GivenType) of + GivenType -> ok; + _RequiredType -> error({bad_type,{needed,RequiredType},{actual,GivenType}}) end. -set_element_type(_Key, none, Es) -> - Es; -set_element_type(Key, term, Es) -> - maps:remove(Key, Es); -set_element_type(Key, Type, Es) -> - Es#{ Key => Type }. - -get_tuple_size({integer,[]}) -> 0; -get_tuple_size({integer,Sz}) -> Sz; -get_tuple_size(_) -> 0. - validate_src(Ss, Vst) when is_list(Ss) -> _ = [assert_term(S, Vst) || S <- Ss], ok. @@ -2244,7 +1953,7 @@ validate_src(Ss, Vst) when is_list(Ss) -> get_term_type(Src, Vst) -> case get_movable_term_type(Src, Vst) of - #ms{} -> error({match_context,Src}); + #t_bs_context{} -> error({match_context,Src}); Type -> Type end. @@ -2254,11 +1963,11 @@ get_term_type(Src, Vst) -> get_movable_term_type(Src, Vst) -> case get_raw_type(Src, Vst) of + #t_abstract{kind=tuple_in_progress=Kind} -> error({Kind,Src}); initialized -> error({unassigned,Src}); uninitialized -> error({uninitialized_reg,Src}); {catchtag,_} -> error({catchtag,Src}); {trytag,_} -> error({trytag,Src}); - tuple_in_progress -> error({tuple_in_progress,Src}); Type -> Type end. @@ -2301,7 +2010,9 @@ get_raw_type(Src, #vst{}) -> get_literal_type(Src). is_value_alive(#value_ref{}=Ref, #vst{current=#st{vs=Vs}}) -> - is_map_key(Ref, Vs). + is_map_key(Ref, Vs); +is_value_alive(_, _) -> + false. get_literal_type(nil) -> glt_1([]); get_literal_type({atom,A}) when is_atom(A) -> glt_1(A); @@ -2312,20 +2023,23 @@ get_literal_type(T) -> error({not_literal,T}). glt_1([]) -> nil; glt_1([_|_]) -> cons; -glt_1(A) when is_atom(A) -> {atom, A}; -glt_1(B) when is_bitstring(B) -> binary; -glt_1(F) when is_float(F) -> {float, F}; -glt_1(I) when is_integer(I) -> {integer, I}; -glt_1(M) when is_map(M) -> map; +glt_1(A) when is_atom(A) -> #t_atom{elements=[A]}; +glt_1(B) when is_bitstring(B) -> #t_bitstring{}; +glt_1(F) when is_float(F) -> float; +glt_1(F) when is_function(F) -> + {arity, Arity} = erlang:fun_info(F, arity), + #t_fun{arity=Arity}; +glt_1(I) when is_integer(I) -> beam_types:make_integer(I); +glt_1(M) when is_map(M) -> #t_map{}; glt_1(T) when is_tuple(T) -> {Es,_} = foldl(fun(Val, {Es0, Index}) -> Type = glt_1(Val), - Es = set_element_type(Index, Type, Es0), + Es = beam_types:set_element_type(Index, Type, Es0), {Es, Index + 1} end, {#{}, 1}, tuple_to_list(T)), - {tuple, tuple_size(T), Es}; + #t_tuple{exact=true,size=tuple_size(T),elements=Es}; glt_1(_Term) -> - term. + any. %%% %%% Branch tracking @@ -2516,9 +2230,6 @@ merge_ct_1([C0|Ct0], [C1|Ct1]) -> merge_ct_1([], []) -> []; merge_ct_1(_, _) -> undecided. -tuple_sz([Sz]) -> Sz; -tuple_sz(Sz) -> Sz. - verify_y_init(#vst{current=#st{numy=NumY,ys=Ys}}=Vst) when is_integer(NumY) -> HighestY = maps:fold(fun({y,Y}, _, Acc) -> max(Y, Acc) end, -1, Ys), true = NumY > HighestY, %Assertion. @@ -2660,316 +2371,26 @@ assert_not_fragile(Lit, #vst{}) -> ok. %%% -%%% Return/argument types of BIFs +%%% Return/argument types of calls and BIFs %%% -bif_return_type('-', Src, Vst) -> - arith_return_type(Src, Vst); -bif_return_type('+', Src, Vst) -> - arith_return_type(Src, Vst); -bif_return_type('*', Src, Vst) -> - arith_return_type(Src, Vst); -bif_return_type(abs, [Num], Vst) -> - case get_term_type(Num, Vst) of - {float,_}=T -> T; - {integer,_}=T -> T; - _ -> number - end; -bif_return_type(float, _, _) -> {float,[]}; -bif_return_type('/', _, _) -> {float,[]}; -%% Binary operations -bif_return_type('binary_part', [_,_], _) -> binary; -bif_return_type('binary_part', [_,_,_], _) -> binary; -bif_return_type('bit_size', [_], _) -> {integer,[]}; -bif_return_type('byte_size', [_], _) -> {integer,[]}; -%% Integer operations. -bif_return_type(ceil, [_], _) -> {integer,[]}; -bif_return_type('div', [_,_], _) -> {integer,[]}; -bif_return_type(floor, [_], _) -> {integer,[]}; -bif_return_type('rem', [_,_], _) -> {integer,[]}; -bif_return_type(length, [_], _) -> {integer,[]}; -bif_return_type(size, [_], _) -> {integer,[]}; -bif_return_type(trunc, [_], _) -> {integer,[]}; -bif_return_type(round, [_], _) -> {integer,[]}; -bif_return_type('band', [_,_], _) -> {integer,[]}; -bif_return_type('bor', [_,_], _) -> {integer,[]}; -bif_return_type('bxor', [_,_], _) -> {integer,[]}; -bif_return_type('bnot', [_], _) -> {integer,[]}; -bif_return_type('bsl', [_,_], _) -> {integer,[]}; -bif_return_type('bsr', [_,_], _) -> {integer,[]}; -%% Booleans. -bif_return_type('==', [_,_], _) -> bool; -bif_return_type('/=', [_,_], _) -> bool; -bif_return_type('=<', [_,_], _) -> bool; -bif_return_type('<', [_,_], _) -> bool; -bif_return_type('>=', [_,_], _) -> bool; -bif_return_type('>', [_,_], _) -> bool; -bif_return_type('=:=', [_,_], _) -> bool; -bif_return_type('=/=', [_,_], _) -> bool; -bif_return_type('not', [_], _) -> bool; -bif_return_type('and', [_,_], _) -> bool; -bif_return_type('or', [_,_], _) -> bool; -bif_return_type('xor', [_,_], _) -> bool; -bif_return_type(is_atom, [_], _) -> bool; -bif_return_type(is_boolean, [_], _) -> bool; -bif_return_type(is_binary, [_], _) -> bool; -bif_return_type(is_float, [_], _) -> bool; -bif_return_type(is_function, [_], _) -> bool; -bif_return_type(is_function, [_,_], _) -> bool; -bif_return_type(is_integer, [_], _) -> bool; -bif_return_type(is_list, [_], _) -> bool; -bif_return_type(is_map, [_], _) -> bool; -bif_return_type(is_number, [_], _) -> bool; -bif_return_type(is_pid, [_], _) -> bool; -bif_return_type(is_port, [_], _) -> bool; -bif_return_type(is_reference, [_], _) -> bool; -bif_return_type(is_tuple, [_], _) -> bool; -%% Misc. -bif_return_type(tuple_size, [_], _) -> {integer,[]}; -bif_return_type(map_size, [_], _) -> {integer,[]}; -bif_return_type(node, [], _) -> {atom,[]}; -bif_return_type(node, [_], _) -> {atom,[]}; -bif_return_type(hd, [_], _) -> term; -bif_return_type(tl, [_], _) -> term; -bif_return_type(get, [_], _) -> term; -bif_return_type(Bif, _, _) when is_atom(Bif) -> term. - -%% Generic -bif_arg_types(tuple_size, [_]) -> [{tuple,[0],#{}}]; -bif_arg_types(map_size, [_]) -> [map]; -bif_arg_types(is_map_key, [_,_]) -> [term, map]; -bif_arg_types(map_get, [_,_]) -> [term, map]; -bif_arg_types(length, [_]) -> [list]; -bif_arg_types(hd, [_]) -> [cons]; -bif_arg_types(tl, [_]) -> [cons]; -%% Boolean -bif_arg_types('not', [_]) -> [bool]; -bif_arg_types('and', [_,_]) -> [bool, bool]; -bif_arg_types('or', [_,_]) -> [bool, bool]; -bif_arg_types('xor', [_,_]) -> [bool, bool]; -%% Binary -bif_arg_types('binary_part', [_,_]) -> - PosLen = {tuple, 2, #{ {integer,1} => {integer,[]}, - {integer,2} => {integer,[]} }}, - [binary, PosLen]; -bif_arg_types('binary_part', [_,_,_]) -> - [binary, {integer,[]}, {integer,[]}]; -bif_arg_types('bit_size', [_]) -> [binary]; -bif_arg_types('byte_size', [_]) -> [binary]; -%% Numerical -bif_arg_types('-', [_]) -> [number]; -bif_arg_types('-', [_,_]) -> [number,number]; -bif_arg_types('+', [_]) -> [number]; -bif_arg_types('+', [_,_]) -> [number,number]; -bif_arg_types('*', [_,_]) -> [number, number]; -bif_arg_types('/', [_,_]) -> [number, number]; -bif_arg_types(abs, [_]) -> [number]; -bif_arg_types(ceil, [_]) -> [number]; -bif_arg_types(float, [_]) -> [number]; -bif_arg_types(floor, [_]) -> [number]; -bif_arg_types(trunc, [_]) -> [number]; -bif_arg_types(round, [_]) -> [number]; -%% Integer-specific -bif_arg_types('div', [_,_]) -> [{integer,[]}, {integer,[]}]; -bif_arg_types('rem', [_,_]) -> [{integer,[]}, {integer,[]}]; -bif_arg_types('band', [_,_]) -> [{integer,[]}, {integer,[]}]; -bif_arg_types('bor', [_,_]) -> [{integer,[]}, {integer,[]}]; -bif_arg_types('bxor', [_,_]) -> [{integer,[]}, {integer,[]}]; -bif_arg_types('bnot', [_]) -> [{integer,[]}]; -bif_arg_types('bsl', [_,_]) -> [{integer,[]}, {integer,[]}]; -bif_arg_types('bsr', [_,_]) -> [{integer,[]}, {integer,[]}]; -%% Unsafe type tests that may fail if an argument doesn't have the right type. -bif_arg_types(is_function, [_,_]) -> [term, {integer,[]}]; -bif_arg_types(_, Args) -> [term || _Arg <- Args]. - -is_bif_safe('/=', 2) -> true; -is_bif_safe('<', 2) -> true; -is_bif_safe('=/=', 2) -> true; -is_bif_safe('=:=', 2) -> true; -is_bif_safe('=<', 2) -> true; -is_bif_safe('==', 2) -> true; -is_bif_safe('>', 2) -> true; -is_bif_safe('>=', 2) -> true; -is_bif_safe(is_atom, 1) -> true; -is_bif_safe(is_boolean, 1) -> true; -is_bif_safe(is_binary, 1) -> true; -is_bif_safe(is_bitstring, 1) -> true; -is_bif_safe(is_float, 1) -> true; -is_bif_safe(is_function, 1) -> true; -is_bif_safe(is_integer, 1) -> true; -is_bif_safe(is_list, 1) -> true; -is_bif_safe(is_map, 1) -> true; -is_bif_safe(is_number, 1) -> true; -is_bif_safe(is_pid, 1) -> true; -is_bif_safe(is_port, 1) -> true; -is_bif_safe(is_reference, 1) -> true; -is_bif_safe(is_tuple, 1) -> true; -is_bif_safe(get, 1) -> true; -is_bif_safe(self, 0) -> true; -is_bif_safe(node, 0) -> true; -is_bif_safe(_, _) -> false. - -arith_return_type([A], Vst) -> - %% Unary '+' or '-'. - case get_term_type(A, Vst) of - {integer,_} -> {integer,[]}; - {float,_} -> {float,[]}; - _ -> number - end; -arith_return_type([A,B], Vst) -> - TypeA = get_term_type(A, Vst), - TypeB = get_term_type(B, Vst), - case {TypeA, TypeB} of - {{integer,_},{integer,_}} -> {integer,[]}; - {{float,_},_} -> {float,[]}; - {_,{float,_}} -> {float,[]}; - {_,_} -> number - end; -arith_return_type(_, _) -> number. +bif_types(Op, Ss, Vst) -> + Args = [get_term_type(Arg, Vst) || Arg <- Ss], + beam_call_types:types(erlang, Op, Args). -%%% -%%% Return/argument types of calls -%%% +call_types({extfunc,M,F,A}, A, Vst) -> + Args = get_call_args(A, Vst), + beam_call_types:types(M, F, Args); +call_types(_, A, Vst) -> + {any, get_call_args(A, Vst), false}. -call_return_type({extfunc,M,F,A}, Vst) -> call_return_type_1(M, F, A, Vst); -call_return_type(_, _) -> term. +get_call_args(Arity, Vst) -> + get_call_args_1(0, Arity, Vst). -call_return_type_1(erlang, setelement, 3, Vst) -> - IndexType = get_term_type({x,0}, Vst), - TupleType = - case get_term_type({x,1}, Vst) of - {tuple,_,_}=TT -> TT; - _ -> {tuple,[0],#{}} - end, - case IndexType of - {integer,I} when is_integer(I) -> - case meet({tuple,[I],#{}}, TupleType) of - {tuple, Sz, Es0} -> - ValueType = get_term_type({x,2}, Vst), - Es = set_element_type(I, ValueType, Es0), - {tuple, Sz, Es}; - none -> - TupleType - end; - _ -> - %% The index could point anywhere, so we must discard all element - %% information. - setelement(3, TupleType, #{}) - end; -call_return_type_1(erlang, '++', 2, Vst) -> - LType = get_term_type({x,0}, Vst), - RType = get_term_type({x,1}, Vst), - case LType =:= cons orelse RType =:= cons of - true -> - cons; - false -> - %% `[] ++ RHS` yields RHS, even if RHS is not a list - join(list, RType) - end; -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 -> - term. - -erlang_mod_return_type(exit, 1) -> exception; -erlang_mod_return_type(throw, 1) -> exception; -erlang_mod_return_type(error, 1) -> exception; -erlang_mod_return_type(error, 2) -> exception; -erlang_mod_return_type(F, A) when is_atom(F), is_integer(A), A >= 0 -> term. - -math_mod_return_type(cos, 1) -> {float,[]}; -math_mod_return_type(cosh, 1) -> {float,[]}; -math_mod_return_type(sin, 1) -> {float,[]}; -math_mod_return_type(sinh, 1) -> {float,[]}; -math_mod_return_type(tan, 1) -> {float,[]}; -math_mod_return_type(tanh, 1) -> {float,[]}; -math_mod_return_type(acos, 1) -> {float,[]}; -math_mod_return_type(acosh, 1) -> {float,[]}; -math_mod_return_type(asin, 1) -> {float,[]}; -math_mod_return_type(asinh, 1) -> {float,[]}; -math_mod_return_type(atan, 1) -> {float,[]}; -math_mod_return_type(atanh, 1) -> {float,[]}; -math_mod_return_type(erf, 1) -> {float,[]}; -math_mod_return_type(erfc, 1) -> {float,[]}; -math_mod_return_type(exp, 1) -> {float,[]}; -math_mod_return_type(log, 1) -> {float,[]}; -math_mod_return_type(log2, 1) -> {float,[]}; -math_mod_return_type(log10, 1) -> {float,[]}; -math_mod_return_type(sqrt, 1) -> {float,[]}; -math_mod_return_type(atan2, 2) -> {float,[]}; -math_mod_return_type(pow, 2) -> {float,[]}; -math_mod_return_type(ceil, 1) -> {float,[]}; -math_mod_return_type(floor, 1) -> {float,[]}; -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(all, 2, _Vst) -> - bool; -lists_mod_return_type(any, 2, _Vst) -> - bool; -lists_mod_return_type(keymember, 3, _Vst) -> - bool; -lists_mod_return_type(member, 2, _Vst) -> - bool; -lists_mod_return_type(prefix, 2, _Vst) -> - bool; -lists_mod_return_type(suffix, 2, _Vst) -> - bool; -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, 1, _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(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(zip, 2, _Vst) -> - list; -lists_mod_return_type(zipwith, 3, _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 - cons -> cons; - nil -> nil; - _ -> list - end. +get_call_args_1(Arity, Arity, _) -> + []; +get_call_args_1(N, Arity, Vst) when N < Arity -> + [get_movable_term_type({x,N}, Vst) | get_call_args_1(N + 1, Arity, Vst)]. check_limit({x,X}=Src) when is_integer(X) -> if diff --git a/lib/compiler/test/beam_validator_SUITE.erl b/lib/compiler/test/beam_validator_SUITE.erl index 6b1438abdd..35dda9cc01 100644 --- a/lib/compiler/test/beam_validator_SUITE.erl +++ b/lib/compiler/test/beam_validator_SUITE.erl @@ -217,11 +217,11 @@ bad_catch_try(Config) when is_list(Config) -> {{catch_end,{x,9}}, 8,{invalid_tag_register,{x,9}}}}, {{bad_catch_try,bad_3,1}, - {{catch_end,{y,1}},9,{invalid_tag,{y,1},{atom,kalle}}}}, + {{catch_end,{y,1}},9,{invalid_tag,{y,1},{t_atom,[kalle]}}}}, {{bad_catch_try,bad_4,1}, {{'try',{x,0},{f,15}},5,{invalid_tag_register,{x,0}}}}, {{bad_catch_try,bad_5,1}, - {{try_case,{y,1}},12,{invalid_tag,{y,1},term}}}, + {{try_case,{y,1}},12,{invalid_tag,{y,1},any}}}, {{bad_catch_try,bad_6,1}, {{move,{integer,1},{y,1}},7, {invalid_store,{y,1}}}}] = Errors, @@ -232,7 +232,7 @@ cons_guard(Config) when is_list(Config) -> [{{cons,foo,1}, {{get_list,{x,0},{x,1},{x,2}}, 5, - {bad_type,{needed,cons},{actual,term}}}}] = Errors, + {bad_type,{needed,cons},{actual,any}}}}] = Errors, ok. freg_range(Config) when is_list(Config) -> -- cgit v1.2.3