From fb90ee4a0aab48dca08e9c935b26c4742d4c86ab Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 11 Jan 2019 10:31:48 +0100 Subject: beam_validator: Infer types from '=:=' As beam_ssa_type is about to get smarter, beam_validator must be smarter too. --- lib/compiler/src/beam_validator.erl | 131 ++++++++++++++++++++++++++++-------- 1 file changed, 104 insertions(+), 27 deletions(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 1945faba7f..d01013101a 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -824,16 +824,16 @@ valfun_4({test,is_eq_exact,{f,Lbl},[Src,Val]=Ss}, Vst0) -> validate_src(Ss, Vst0), Infer = infer_types(Src, Vst0), Vst1 = Infer(Val, Vst0), - Vst = branch_state(Lbl, Vst1), - case Val of - {literal,Tuple} when is_tuple(Tuple) -> - Type0 = get_term_type(Val, Vst), - Type = upgrade_tuple_type({tuple,tuple_size(Tuple)}, - Type0), - set_aliased_type(Type, Src, Vst); - _ -> - Vst - end; + Vst2 = upgrade_ne_types(Src, Val, Vst1), + Vst3 = branch_state(Lbl, Vst2), + Vst = Vst3#vst{current=Vst1#vst.current}, + upgrade_eq_types(Src, Val, Vst); +valfun_4({test,is_ne_exact,{f,Lbl},[Src,Val]=Ss}, Vst0) -> + validate_src(Ss, Vst0), + Vst1 = upgrade_eq_types(Src, Val, Vst0), + Vst2 = branch_state(Lbl, Vst1), + Vst = Vst2#vst{current=Vst0#vst.current}, + upgrade_ne_types(Src, Val, Vst); valfun_4({test,_Op,{f,Lbl},Src}, Vst) -> validate_src(Src, Vst), branch_state(Lbl, Vst); @@ -920,6 +920,25 @@ valfun_4({get_map_elements,{f,Fail},Src,{list,List}}, Vst) -> valfun_4(_, _) -> error(unknown_instruction). +upgrade_ne_types(Src1, Src2, Vst0) -> + T1 = get_durable_term_type(Src1, Vst0), + T2 = get_durable_term_type(Src2, Vst0), + Type = subtract(T1, T2), + set_aliased_type(Type, Src1, Vst0). + +upgrade_eq_types(Src1, Src2, Vst0) -> + T1 = get_durable_term_type(Src1, Vst0), + T2 = get_durable_term_type(Src2, Vst0), + Meet = meet(T1, T2), + Vst = case T1 =/= Meet of + true -> set_aliased_type(Meet, Src1, Vst0); + false -> Vst0 + end, + case T2 =/= Meet of + true -> set_aliased_type(Meet, Src2, Vst); + false -> Vst + end. + verify_get_map(Fail, Src, List, Vst0) -> assert_not_literal(Src), %OTP 22. assert_type(map, Src, Vst0), @@ -1509,6 +1528,8 @@ assert_not_literal(Literal) -> error({literal_not_allowed,Literal}). %% %% 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: [_|_] @@ -1535,7 +1556,7 @@ assert_not_literal(Literal) -> error({literal_not_allowed,Literal}). %% %% map Map. %% -%% +%% none A conflict in types. There will be an exception at runtime. %% %% FRAGILITY %% --------- @@ -1548,6 +1569,47 @@ assert_not_literal(Literal) -> error({literal_not_allowed,Literal}). %% Such terms are wrapped in a {fragile,Type} tuple, where Type is one %% of the types described above. +%% 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},{tuple,Size2}} -> + case {Size1,Size2} of + {[Sz1],[Sz2]} -> + {tuple,[erlang:max(Sz1, Sz2)]}; + {Sz1,[Sz2]} when Sz2 =< Sz1 -> + {tuple,Sz1}; + {_,_} -> + none + end; + {_,_} -> none + end. + +%% subtract(Type1, Type2) -> Type +%% Subtract Type2 from Type2. Example: +%% subtract(list, nil) -> cons + +subtract(list, nil) -> cons; +subtract(list, cons) -> nil; +subtract(Type, _) -> Type. + assert_type(WantedType, Term, Vst) -> case get_term_type(Term, Vst) of {fragile,Type} -> @@ -1581,25 +1643,27 @@ assert_type(Needed, Actual) -> %% be executed at run-time. upgrade_tuple_type(NewType, {fragile,OldType}) -> - make_fragile(upgrade_tuple_type_1(NewType, OldType)); + Type = upgrade_tuple_type_1(NewType, OldType), + make_fragile(Type); upgrade_tuple_type(NewType, OldType) -> upgrade_tuple_type_1(NewType, OldType). -upgrade_tuple_type_1({tuple,[Sz]}, {tuple,[OldSz]}=T) when Sz < OldSz -> - %% The old type has a higher value for the least tuple size. - T; -upgrade_tuple_type_1({tuple,[Sz]}, {tuple,OldSz}=T) - when is_integer(Sz), is_integer(OldSz), Sz =< OldSz -> - %% The old size is exact, and the new size is smaller than the old size. - T; -upgrade_tuple_type_1({tuple,_}=T, _) -> - %% The new type information is exact or has a higher value for - %% the least tuple size. - %% Note that inconsistencies are also handled in this - %% clause, e.g. if the old type was an integer or a tuple accessed - %% outside its size; inconsistences will generally cause an exception - %% at run-time but are safe from our point of view. - T. +upgrade_tuple_type_1(NewType, OldType) -> + case meet(NewType, OldType) of + none -> + %% Unoptimized code may look like this: + %% + %% {test,is_list,Fail,[Reg]}. + %% {test,is_tuple,Fail,[Reg]}. + %% {test,test_arity,Fail,[Reg,5]}. + %% + %% Note that the test_arity instruction can never be reached. + %% To make sure it's not rejected, set the type of Reg to + %% NewType instead of 'none'. + NewType; + Type -> + Type + end. get_tuple_size({integer,[]}) -> 0; get_tuple_size({integer,Sz}) -> Sz; @@ -1608,6 +1672,17 @@ get_tuple_size(_) -> 0. validate_src(Ss, Vst) when is_list(Ss) -> foreach(fun(S) -> get_term_type(S, Vst) end, Ss). +%% get_durable_term_type(Src, ValidatorState) -> Type +%% Get the type of the source Src. The returned type Type will be +%% a standard Erlang type (no catch/try tags or match contexts). +%% Fragility will be stripped. + +get_durable_term_type(Src, Vst) -> + case get_term_type(Src, Vst) of + {fragile,Type} -> Type; + Type -> Type + end. + %% get_move_term_type(Src, ValidatorState) -> Type %% Get the type of the source Src. The returned type Type will be %% a standard Erlang type (no catch/try tags). Match contexts are OK. @@ -1641,6 +1716,8 @@ get_term_type_1(nil=T, _) -> T; get_term_type_1({atom,A}=T, _) when is_atom(A) -> T; get_term_type_1({float,F}=T, _) when is_float(F) -> T; get_term_type_1({integer,I}=T, _) when is_integer(I) -> T; +get_term_type_1({literal,[_|_]}, _) -> cons; +get_term_type_1({literal,Bitstring}, _) when is_bitstring(Bitstring) -> binary; get_term_type_1({literal,Map}, _) when is_map(Map) -> map; get_term_type_1({literal,Tuple}, _) when is_tuple(Tuple) -> {tuple,tuple_size(Tuple)}; -- cgit v1.2.3 From f548ea888e4c63546160dcb68ee84a167ca38f8f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sat, 29 Dec 2018 08:15:02 +0100 Subject: Infer types from more BIFs --- lib/compiler/src/beam_ssa_type.erl | 36 ++++++++++++++++++++++++++++++++++++ lib/compiler/src/beam_validator.erl | 25 +++++++++++++++++++++++++ 2 files changed, 61 insertions(+) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 95fc3bb0e9..118f4d57bc 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -542,6 +542,14 @@ type(call, [#b_remote{mod=#b_literal{val=Mod}, {_,_} -> #t_tuple{} end; + {erlang,'++',[List1,List2]} -> + case get_type(List1, Ts) =:= cons orelse + get_type(List2, Ts) =:= cons of + true -> cons; + false -> list + end; + {erlang,'--',[_,_]} -> + list; {math,_,_} -> case is_math_bif(Name, length(Args)) of false -> any; @@ -885,6 +893,8 @@ infer_type({bif,element}, [#b_literal{val=Pos},#b_var{}=Tuple], _Ds) -> true -> [] end; +infer_type({bif,element}, [#b_var{}=Position,#b_var{}=Tuple], _Ds) -> + [{Position,t_integer()},{Tuple,#t_tuple{}}]; infer_type({bif,'=:='}, [#b_var{}=Src,#b_literal{}=Lit], Ds) -> Def = maps:get(Src, Ds), Type = get_type(Lit, #{}), @@ -895,10 +905,20 @@ infer_type({bif,Bif}, [#b_var{}=Src]=Args, _Ds) -> 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) -> @@ -969,6 +989,7 @@ 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; @@ -976,10 +997,25 @@ 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. infer_tuple_size(#b_set{op={bif,tuple_size},args=[#b_var{}=Tuple]}, diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index d01013101a..46c689e034 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -809,6 +809,14 @@ valfun_4({test,has_map_fields,{f,Lbl},Src,{list,List}}, Vst) -> assert_type(map, Src, Vst), assert_unique_map_keys(List), branch_state(Lbl, Vst); +valfun_4({test,is_list,{f,Lbl},[Src]}, Vst) -> + validate_src([Src], Vst), + Type = case get_term_type(Src, Vst) of + cons -> cons; + nil -> nil; + _ -> list + end, + set_aliased_type(Type, Src, branch_state(Lbl, Vst)); valfun_4({test,is_map,{f,Lbl},[Src]}, Vst0) -> Vst = branch_state(Lbl, Vst0), case Src of @@ -820,6 +828,13 @@ valfun_4({test,is_map,{f,Lbl},[Src]}, Vst0) -> _ -> kill_state(Vst0) end; +valfun_4({test,is_nil,{f,Lbl},[Src]}, Vst) -> + case get_term_type(Src, Vst) of + list -> + branch_state(Lbl, set_type_reg(cons, Src, Vst)); + _ -> + branch_state(Lbl, Vst) + end; valfun_4({test,is_eq_exact,{f,Lbl},[Src,Val]=Ss}, Vst0) -> validate_src(Ss, Vst0), Infer = infer_types(Src, Vst0), @@ -1536,6 +1551,8 @@ assert_not_literal(Literal) -> error({literal_not_allowed,Literal}). %% %% nil Empty list: [] %% +%% list List: [] or [_|_] +%% %% {tuple,[Sz]} 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. @@ -2118,6 +2135,14 @@ return_type_1(erlang, setelement, 3, Vst) -> {integer,I} -> upgrade_tuple_type({tuple,[I]}, TupleType); _ -> TupleType end; +return_type_1(erlang, '++', 2, Vst) -> + case get_term_type({x,0}, Vst) =:= cons orelse + get_term_type({x,1}, Vst) =:= cons of + true -> cons; + false -> list + end; +return_type_1(erlang, '--', 2, _Vst) -> + list; return_type_1(erlang, F, A, _) -> return_type_erl(F, A); return_type_1(math, F, A, _) -> -- cgit v1.2.3 From 48f20bd589fa69b79bda86731560513801ac89f0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 27 Nov 2018 16:05:23 +0100 Subject: Introduce subtraction of types Introduce subtraction of types to allow some redundant tests to be eliminated. Consider this function: foo(L) when is_list(L) -> case L of [_|_] -> non_empty; [] -> empty end. After entering the body of the function, L is known to be either a cons cell or nil (otherwise the is_list/1 guard would have failed). If the L is not a cons cell, it must be nil. Therefore, the test for nil in the second clause of the case can be eliminated. Here is the SSA code with some additonal comments for the function before the optimization: function t:foo(_0) { 0: @ssa_bool = bif:is_list _0 br @ssa_bool, label 4, label 3 4: %% _0 is now a list (cons or nil). @ssa_bool:8 = is_nonempty_list _0 br @ssa_bool:8, label 9, label 7 9: ret literal non_empty 7: %% _0 is not a cons (or we wouldn't be here). %% Subtracting cons from the previously known type list %% gives that _0 must be nil. @ssa_bool:10 = bif:'=:=' _0, literal [] br @ssa_bool:10, label 11, label 6 11: ret literal empty 6: _6 = put_tuple literal case_clause, _0 %% t.erl:5 @ssa_ret:12 = call remote (literal erlang):(literal error)/1, _6 ret @ssa_ret:12 3: _9 = put_list _0, literal [] %% t.erl:4 @ssa_ret:13 = call remote (literal erlang):(literal error)/2, literal function_clause, _9 ret @ssa_ret:13 } Type subtraction gives us that _0 must be nil in block 7, allowing us to remove the comparison of _0 with nil. The code for the function can be simplified to: function t:foo(_0) { 0: @ssa_bool = bif:is_list _0 br @ssa_bool, label 4, label 3 4: @ssa_bool:8 = is_nonempty_list _0 br @ssa_bool:8, label 9, label 11 9: ret literal non_empty 11: ret literal empty 3: _9 = put_list _0, literal [] %% t.erl:4 @ssa_ret:13 = call remote (literal erlang):(literal error)/2, literal function_clause, _9 ret @ssa_ret:13 } --- lib/compiler/src/beam_ssa_type.erl | 137 ++++++++++++++++++++++++++++++++----- lib/compiler/test/match_SUITE.erl | 24 ++++++- 2 files changed, 143 insertions(+), 18 deletions(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 118f4d57bc..52ac74510b 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -23,7 +23,7 @@ -include("beam_ssa.hrl"). -import(lists, [all/2,any/2,droplast/1,foldl/3,last/1,member/2, - reverse/1,sort/1]). + partition/2,reverse/1,sort/1]). -define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}). @@ -436,12 +436,12 @@ update_successors(#b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail}, Ts0, D0) -> %% no need to include the type database passed on to the %% successors of this block. Ts = maps:remove(Bool, Ts0), - D = update_successor(Fail, Ts, D0), - SuccTs = infer_types(Bool, Ts, D0), + {SuccTs,FailTs} = infer_types(Bool, Ts, D0), + D = update_successor(Fail, FailTs, D0), update_successor(Succ, SuccTs, D); false -> - D = update_successor_bool(Bool, false, Fail, Ts0, D0), - SuccTs = infer_types(Bool, Ts0, D0), + {SuccTs,FailTs} = infer_types(Bool, Ts0, D0), + D = update_successor_bool(Bool, false, Fail, FailTs, D0), update_successor_bool(Bool, true, Succ, SuccTs, D) end; update_successors(#b_switch{arg=#b_var{}=V,fail=Fail,list=List}, Ts0, D0) -> @@ -458,7 +458,8 @@ update_successors(#b_switch{arg=#b_var{}=V,fail=Fail,list=List}, Ts0, D0) -> end, foldl(F, D, List); false -> - D = update_successor(Fail, Ts0, D0), + FailTs = subtract_types([{V,join_sw_list(List, Ts0, none)}], Ts0), + D = update_successor(Fail, FailTs, D0), F = fun({Val,S}, A) -> T = get_type(Val, Ts0), update_successor(S, Ts0#{V=>T}, A) @@ -467,6 +468,10 @@ update_successors(#b_switch{arg=#b_var{}=V,fail=Fail,list=List}, Ts0, D0) -> end; update_successors(#b_ret{}, _Ts, D) -> D. +join_sw_list([{Val,_}|T], Ts, Type) -> + join_sw_list(T, Ts, join(Type, get_type(Val, Ts))); +join_sw_list([], _, Type) -> Type. + update_successor_bool(#b_var{}=Var, BoolValue, S, Ts, D) -> case t_is_boolean(get_type(Var, Ts)) of true -> @@ -881,10 +886,84 @@ get_type(#b_literal{val=Val}, _Ts) -> any end. -infer_types(#b_var{}=V, Ts, #d{ds=Ds}) -> +%% infer_types(Var, Types, #d{}) -> {SuccTypes,FailTypes} +%% Looking at the expression that defines the variable Var, infer +%% the types for the variables in the arguments. Return the updated +%% type database for the case that the expression evaluates to +%% true, and and for the case that it evaluates to false. +%% +%% Here is an example. The variable being asked about is +%% the variable Bool, which is defined like this: +%% +%% Bool = is_nonempty_list L +%% +%% If 'is_nonempty_list L' evaluates to 'true', L must +%% must be cons. The meet of the previously known type of L and 'cons' +%% will be added to SuccTypes. +%% +%% On the other hand, if 'is_nonempty_list L' evaluates to false, L +%% is not cons and cons can be subtracted from the previously known +%% type for L. For example, if L was known to be 'list', subtracting +%% 'cons' would give 'nil' as the only possible type. The result of the +%% subtraction for L will be added to FailTypes. +%% +%% Here is another example, asking about the variable Bool: +%% +%% Head = bif:hd L +%% Bool = succeeded Head +%% +%% 'succeeded Head' will evaluate to 'true' if the instrution that +%% defined Head succeeded. In this case, it is the 'bif:hd L' +%% instruction, which will succeed if L is 'cons'. Thus, the meet of +%% the previous type for L and 'cons' will be added to SuccTypes. +%% +%% If 'succeeded Head' evaluates to 'false', it means that 'bif:hd L' +%% failed and that L is not 'cons'. 'cons' can be subtracted from the +%% previously known type for L and the result put in FailTypes. + +infer_types(#b_var{}=V, Ts, #d{ds=Ds,once=Once}) -> #{V:=#b_set{op=Op,args=Args}} = Ds, - Types = infer_type(Op, Args, Ds), - meet_types(Types, Ts). + Types0 = infer_type(Op, Args, Ds), + + %% We must be careful with types inferred from '=:='. + %% + %% If we have seen L =:= [a], we know that L is 'cons' if the + %% comparison succeeds. However, if the comparison fails, L could + %% still be 'cons'. Therefore, we must not subtract 'cons' from the + %% previous type of L. + %% + %% However, it is safe to subtract a type inferred from '=:=' if + %% it is single-valued, e.g. if it is [] or the atom 'true'. + EqTypes0 = infer_eq_type(Op, Args, Ts, Ds), + {Types1,EqTypes} = partition(fun({_,T}) -> + is_singleton_type(T) + end, EqTypes0), + + %% Don't bother updating the types for variables that + %% are never used again. + Types2 = Types1 ++ Types0, + Types = [P || {InfV,_}=P <- Types2, not cerl_sets:is_element(InfV, Once)], + + {meet_types(EqTypes++Types, Ts),subtract_types(Types, Ts)}. + +infer_eq_type({bif,'=:='}, [#b_var{}=Src,#b_literal{}=Lit], Ts, Ds) -> + Def = maps:get(Src, Ds), + Type = get_type(Lit, Ts), + [{Src,Type}|infer_tuple_size(Def, Lit) ++ + infer_first_element(Def, Lit)]; +infer_eq_type({bif,'=:='}, [#b_var{}=Arg0,#b_var{}=Arg1], Ts, _Ds) -> + %% As an example, assume that L1 is known to be 'list', and L2 is + %% known to be 'cons'. Then if 'L1 =:= L2' evaluates to 'true', it can + %% 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), + [{V,MeetType} || + {V,OrigType,MeetType} <- + [{Arg0,Type0,Type},{Arg1,Type1,Type}], + OrigType =/= MeetType]; +infer_eq_type(_Op, _Args, _Ts, _Ds) -> + []. infer_type({bif,element}, [#b_literal{val=Pos},#b_var{}=Tuple], _Ds) -> if @@ -895,11 +974,6 @@ infer_type({bif,element}, [#b_literal{val=Pos},#b_var{}=Tuple], _Ds) -> end; infer_type({bif,element}, [#b_var{}=Position,#b_var{}=Tuple], _Ds) -> [{Position,t_integer()},{Tuple,#t_tuple{}}]; -infer_type({bif,'=:='}, [#b_var{}=Src,#b_literal{}=Lit], Ds) -> - Def = maps:get(Src, Ds), - Type = get_type(Lit, #{}), - [{Src,Type}|infer_tuple_size(Def, Lit) ++ - infer_first_element(Def, Lit)]; infer_type({bif,Bif}, [#b_var{}=Src]=Args, _Ds) -> case inferred_bif_type(Bif, Args) of any -> []; @@ -1124,6 +1198,11 @@ t_tuple_size(#t_tuple{size=Size,exact=true}) -> t_tuple_size(_) -> none. +is_singleton_type(#t_atom{elements=[_]}) -> true; +is_singleton_type(#t_integer{elements={V,V}}) -> true; +is_singleton_type(nil) -> true; +is_singleton_type(_) -> false. + %% join(Type1, Type2) -> Type %% Return the "join" of Type1 and Type2. The join is a more general %% type than Type1 and Type2. For example: @@ -1188,14 +1267,40 @@ gcd(A, B) -> meet_types([{V,T0}|Vs], Ts) -> #{V:=T1} = Ts, - T = meet(T0, T1), - meet_types(Vs, Ts#{V:=T}); + case 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 + 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: diff --git a/lib/compiler/test/match_SUITE.erl b/lib/compiler/test/match_SUITE.erl index 78276982eb..60ab969929 100644 --- a/lib/compiler/test/match_SUITE.erl +++ b/lib/compiler/test/match_SUITE.erl @@ -25,7 +25,7 @@ match_in_call/1,untuplify/1,shortcut_boolean/1,letify_guard/1, selectify/1,deselectify/1,underscore/1,match_map/1,map_vars_used/1, coverage/1,grab_bag/1,literal_binary/1, - unary_op/1]). + unary_op/1,eq_types/1]). -include_lib("common_test/include/ct.hrl"). @@ -40,7 +40,7 @@ groups() -> match_in_call,untuplify, shortcut_boolean,letify_guard,selectify,deselectify, underscore,match_map,map_vars_used,coverage, - grab_bag,literal_binary,unary_op]}]. + grab_bag,literal_binary,unary_op,eq_types]}]. init_per_suite(Config) -> @@ -870,5 +870,25 @@ unary_op_1(Vop@1) -> end end. +eq_types(_Config) -> + Ref = make_ref(), + Ref = eq_types(Ref, any), + ok. + +eq_types(A, B) -> + %% {put_tuple2,{y,0},{list,[{x,0},{x,1}]}}. + Term0 = {A, B}, + Term = id(Term0), + + %% {test,is_eq_exact,{f,3},[{y,0},{x,0}]}. + %% Here beam_validator must infer that {x,0} has the + %% same type as {y,0}. + Term = Term0, + + %% {get_tuple_element,{x,0},0,{x,0}}. + {Ref22,_} = Term, + + Ref22. + id(I) -> I. -- cgit v1.2.3