diff options
Diffstat (limited to 'lib/compiler/src/beam_ssa_type.erl')
| -rw-r--r-- | lib/compiler/src/beam_ssa_type.erl | 842 |
1 files changed, 414 insertions, 428 deletions
diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 79c67e5705..d93191c689 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -25,7 +25,7 @@ -include("beam_types.hrl"). -import(lists, [all/2,any/2,droplast/1,duplicate/2,foldl/3,last/1,member/2, - keyfind/3,reverse/1,reverse/2,sort/1,split/2,zip/2]). + keyfind/3,reverse/1,sort/1,split/2,zip/2]). -define(UNICODE_MAX, (16#10FFFF)). @@ -84,7 +84,8 @@ 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 => beam_types:join(maps:values(TM))}); + Type = beam_types:join(maps:values(TM)), + join_arg_types_1(Args, TMs, Ts#{ Arg => Type }); join_arg_types_1([Arg | Args], [_TM | TMs], Ts) -> join_arg_types_1(Args, TMs, Ts#{ Arg => any }); join_arg_types_1([], [], Ts) -> @@ -108,7 +109,7 @@ opt_continue_1(Linear0, Args, Id, Ts, FuncDb0) -> D = #d{ func_db=FuncDb0, func_id=Id, ds=Defs, - ls=#{0=>Ts,?BADARG_BLOCK=>#{}}, + ls=#{0=>Ts,?EXCEPTION_BLOCK=>#{}}, once=UsedOnce }, {Linear, FuncDb, NewRet} = opt(Linear0, D, []), @@ -170,27 +171,17 @@ opt([], D, Acc) -> opt_1(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, #d{ds=Ds0,sub=Sub0,func_db=Fdb0}=D0, Acc) -> - case opt_is(Is0, Ts0, Ds0, Fdb0, D0, Sub0, []) of - {Is,Ts,Ds,Fdb,Sub} -> - D1 = D0#d{ds=Ds,sub=Sub,func_db=Fdb}, - Last1 = simplify_terminator(Last0, Sub, Ts, Ds), - Last = opt_terminator(Last1, Ts, Ds), - D = update_successors(Last, Ts, D1), - Blk = Blk0#b_blk{is=Is,last=Last}, - opt(Bs, D, [{L,Blk}|Acc]); - {no_return,Ret,Is,Ds,Fdb,Sub} -> - %% This call will never reach the successor block. - %% Rewrite the terminator to a 'ret', and remove - %% all type information for this label. That can - %% potentially narrow the type of the phi node - %% in the former successor. - Ls = maps:remove(L, D0#d.ls), - 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}, - opt(Bs, D, [{L,Blk}|Acc]) - end. + {Is,Ts,Ds,Fdb,Sub} = opt_is(Is0, Ts0, Ds0, Fdb0, D0, Sub0, []), + + D1 = D0#d{ds=Ds,sub=Sub,func_db=Fdb}, + + Last1 = simplify_terminator(Last0, Sub, Ts, Ds), + Last2 = opt_terminator(Last1, Ts, Ds), + + {Last, D} = update_successors(Last2, Ts, D1), + + Blk = Blk0#b_blk{is=Is,last=Last}, + opt(Bs, D, [{L,Blk}|Acc]). simplify_terminator(#b_br{bool=Bool}=Br, Sub, Ts, _Ds) -> Br#b_br{bool=simplify_arg(Bool, Sub, Ts)}; @@ -223,174 +214,82 @@ opt_is([#b_set{op=phi,dst=Dst,args=Args0}=I0|Is], Ds = Ds0#{Dst=>I}, opt_is(Is, Ts, Ds, Fdb, D, Sub0, [I|Acc]) end; -opt_is([#b_set{op=call,args=Args0,dst=Dst}=I0|Is], - Ts0, Ds0, Fdb0, D, Sub0, Acc) -> - Args = simplify_args(Args0, Sub0, Ts0), +opt_is([#b_set{op=call,args=Args0}=I0|Is], + Ts, Ds, Fdb0, D, Sub, Acc) -> + Args = simplify_args(Args0, Sub, Ts), I1 = beam_ssa:normalize(I0#b_set{args=Args}), - {Ts1,Ds,Fdb,I2} = opt_call(I1, D, Ts0, Ds0, Fdb0), - case {map_get(Dst, Ts1),Is} of - {Type,[#b_set{op=succeeded}]} when Type =/= none -> - %% This call instruction is inside a try/catch - %% block. Don't attempt to simplify it. - opt_is(Is, Ts1, Ds, Fdb, D, Sub0, [I2|Acc]); - {none,[#b_set{op=succeeded}]} -> - %% This call instruction is inside a try/catch - %% block, but we know it will never return and - %% later optimizations may try to exploit that. - %% - %% For example, if we have an expression that - %% either returns this call or a tuple, we know - %% that the expression always returns a tuple - %% and can turn a later element/3 into - %% get_tuple_element. - %% - %% This is sound but difficult to validate in a - %% meaningful way as try/catch currently forces - %% us to maintain the illusion that the success - %% block is reachable even when its not, so we - %% disable the optimization to keep things - %% simple. - Ts = Ts1#{ Dst := any }, - opt_is(Is, Ts, Ds, Fdb, D, Sub0, [I2|Acc]); - {none,_} -> - %% This call never returns. The rest of the - %% instructions will not be executed. - Ret = #b_ret{arg=Dst}, - {no_return,Ret,reverse(Acc, [I2]),Ds,Fdb,Sub0}; - {_,_} -> - case simplify_call(I2) of - #b_set{}=I -> - opt_is(Is, Ts1, Ds, Fdb, D, Sub0, [I|Acc]); - #b_literal{}=Lit -> - Sub = Sub0#{Dst=>Lit}, - Ts = maps:remove(Dst, Ts1), - opt_is(Is, Ts, Ds0, Fdb, D, Sub, Acc); - #b_var{}=Var -> - Ts = maps:remove(Dst, Ts1), - Sub = Sub0#{Dst=>Var}, - opt_is(Is, Ts, Ds0, Fdb, D, Sub, Acc) - end - end; + {I, Fdb} = opt_call(I1, Ts, Fdb0, D), + opt_simplify(I, Is, Ts, Ds, Fdb, D, Sub, Acc); opt_is([#b_set{op=make_fun,args=Args0}=I0|Is], Ts0, Ds0, Fdb0, D, Sub0, Acc) -> Args = simplify_args(Args0, Sub0, Ts0), I1 = beam_ssa:normalize(I0#b_set{args=Args}), {Ts,Ds,Fdb,I} = opt_make_fun(I1, D, Ts0, Ds0, Fdb0), opt_is(Is, Ts, Ds, Fdb, D, Sub0, [I|Acc]); -opt_is([#b_set{op=succeeded,args=[Arg],dst=Dst}=I], +opt_is([#b_set{op=succeeded,args=[Arg],dst=Dst,anno=Anno}=I], Ts0, Ds0, Fdb, D, Sub0, Acc) -> - case Ds0 of - #{ Arg := #b_set{op=call} } -> - %% The success check of a call is part of exception handling and - %% must not be optimized away. We still have to update its type - %% though. - Ts = update_types(I, Ts0, Ds0), - Ds = Ds0#{Dst=>I}, - - opt_is([], Ts, Ds, Fdb, D, Sub0, [I|Acc]); - #{} -> - Args = simplify_args([Arg], Sub0, Ts0), - Type = type(succeeded, Args, Ts0, Ds0), - 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); - error -> - Ts = Ts0#{Dst=>Type}, - Ds = Ds0#{Dst=>I}, - opt_is([], Ts, Ds, Fdb, D, Sub0, [I|Acc]) - end + Type = case Ds0 of + #{ Arg := #b_set{op=call} } -> + %% Calls can always throw exceptions and their return types + %% are what they return on success, so we must avoid + %% simplifying arguments in case `Arg` would become a + %% literal, which would trick 'succeeded' into thinking it + %% can't fail. + type(succeeded, [Arg], Anno, Ts0, Ds0); + #{} -> + Args = simplify_args([Arg], Sub0, Ts0), + type(succeeded, Args, Anno, Ts0, Ds0) + end, + 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); + error -> + Ts = Ts0#{ Dst => Type }, + Ds = Ds0#{ Dst => I }, + opt_is([], Ts, Ds, Fdb, D, Sub0, [I | Acc]) end; -opt_is([#b_set{args=Args0,dst=Dst}=I0|Is], - Ts0, Ds0, Fdb, D, Sub0, Acc) -> - Args = simplify_args(Args0, Sub0, Ts0), - I1 = beam_ssa:normalize(I0#b_set{args=Args}), - case simplify(I1, Ts0) of +opt_is([#b_set{args=Args0}=I0|Is], + Ts, Ds, Fdb, D, Sub, Acc) -> + Args = simplify_args(Args0, Sub, Ts), + I = beam_ssa:normalize(I0#b_set{args=Args}), + opt_simplify(I, Is, Ts, Ds, Fdb, D, Sub, Acc); +opt_is([], Ts, Ds, Fdb, _D, Sub, Acc) -> + {reverse(Acc), Ts, Ds, Fdb, Sub}. + +opt_simplify(#b_set{dst=Dst}=I0, Is, Ts0, Ds0, Fdb, D, Sub0, Acc) -> + case simplify(I0, Ts0) of #b_set{}=I2 -> I = beam_ssa:normalize(I2), Ts = update_types(I, Ts0, Ds0), - Ds = Ds0#{Dst=>I}, + Ds = Ds0#{ Dst => I }, opt_is(Is, Ts, Ds, Fdb, D, Sub0, [I|Acc]); #b_literal{}=Lit -> - Sub = Sub0#{Dst=>Lit}, + Sub = Sub0#{ Dst => Lit }, opt_is(Is, Ts0, Ds0, Fdb, D, Sub, Acc); #b_var{}=Var -> case Is of [#b_set{op=succeeded,dst=SuccDst,args=[Dst]}] -> - %% We must remove this 'succeeded' instruction. - Sub = Sub0#{Dst=>Var,SuccDst=>#b_literal{val=true}}, + %% We must remove this 'succeeded' instruction since the + %% variable it checks is gone. + Sub = Sub0#{ Dst => Var, SuccDst => #b_literal{val=true} }, opt_is([], Ts0, Ds0, Fdb, D, Sub, Acc); _ -> - Sub = Sub0#{Dst=>Var}, + Sub = Sub0#{ Dst => Var}, opt_is(Is, Ts0, Ds0, Fdb, D, Sub, Acc) end - end; -opt_is([], Ts, Ds, Fdb, _D, Sub, Acc) -> - {reverse(Acc), Ts, Ds, Fdb, Sub}. - -simplify_call(#b_set{op=call,args=[#b_remote{}=Rem|Args]}=I) -> - case Rem of - #b_remote{mod=#b_literal{val=Mod}, - name=#b_literal{val=Name}} -> - case erl_bifs:is_pure(Mod, Name, length(Args)) of - true -> - simplify_remote_call(Mod, Name, Args, I); - false -> - I - end; - #b_remote{} -> - I - end; -simplify_call(I) -> I. - -%% Simplify a remote call to a pure BIF. -simplify_remote_call(erlang, '++', [#b_literal{val=[]},Tl], _I) -> - Tl; -simplify_remote_call(erlang, setelement, - [#b_literal{val=Pos}, - #b_literal{val=Tuple}, - #b_var{}=Value], I) - when is_integer(Pos), 1 =< Pos, Pos =< tuple_size(Tuple) -> - %% Position is a literal integer and the shape of the - %% tuple is known. - Els0 = [#b_literal{val=El} || El <- tuple_to_list(Tuple)], - {Bef,[_|Aft]} = split(Pos - 1, Els0), - Els = Bef ++ [Value|Aft], - I#b_set{op=put_tuple,args=Els}; -simplify_remote_call(Mod, Name, Args0, I) -> - case make_literal_list(Args0) of - none -> - I; - Args -> - %% The arguments are literals. Try to evaluate the BIF. - try apply(Mod, Name, Args) of - Val -> - case cerl:is_literal_term(Val) of - true -> - #b_literal{val=Val}; - false -> - %% The value can't be expressed as a literal - %% (e.g. a pid). - I - end - catch - _:_ -> - %% Failed. Don't bother trying to optimize - %% the call. - I - end end. -opt_call(#b_set{dst=Dst,args=[#b_local{}=Callee|Args]}=I0, D, Ts0, Ds0, Fdb0) -> - {Ts, Ds, I} = opt_local_call(I0, Ts0, Ds0, Fdb0), +opt_call(#b_set{dst=Dst,args=[#b_local{}=Callee|Args]}=I0, Ts, Fdb0, D) -> + I = opt_local_call_return(I0, Callee, Fdb0), case Fdb0 of #{ Callee := #func_info{exported=false,arg_types=ArgTypes0}=Info } -> %% Match contexts are treated as bitstrings when optimizing %% arguments, as we don't yet support removing the %% "bs_start_match3" instruction. - Types = [case get_type(Arg, Ts) of - #t_bs_context{} -> #t_bitstring{}; - Type -> Type + Types = [case raw_type(Arg, Ts) of + #t_bs_context{} -> #t_bitstring{}; + Type -> Type end || Arg <- Args], %% Update the argument types of *this exact call*, the types @@ -399,36 +298,22 @@ opt_call(#b_set{dst=Dst,args=[#b_local{}=Callee|Args]}=I0, D, Ts0, Ds0, Fdb0) -> ArgTypes = update_arg_types(Types, ArgTypes0, CallId), Fdb = Fdb0#{ Callee => Info#func_info{arg_types=ArgTypes} }, - {Ts, Ds, Fdb, I}; + {I, Fdb}; #{} -> %% We can't narrow the argument types of exported functions as they %% can receive anything as part of an external call. - {Ts, Ds, Fdb0, I} + {I, Fdb0} end; -opt_call(#b_set{dst=Dst,args=[#b_var{}=Fun|Args]}=I, _D, Ts0, Ds0, Fdb) -> - Type = #t_fun{arity=length(Args)}, - Ts = Ts0#{ Fun => Type, Dst => any }, - Ds = Ds0#{ Dst => I }, - {Ts, Ds, Fdb, I}; -opt_call(#b_set{dst=Dst}=I, _D, Ts0, Ds0, Fdb) -> - %% #b_remote{} and literal funs - Ts = update_types(I, Ts0, Ds0), - Ds = Ds0#{ Dst => I }, - {Ts, Ds, Fdb, I}. +opt_call(I, _Ts, Fdb, _D) -> + {I, Fdb}. -opt_local_call(#b_set{dst=Dst,args=[Id|_]}=I0, Ts0, Ds0, Fdb) -> - Type = case Fdb of - #{ Id := #func_info{ret_type=[T]} } -> T; - #{} -> any - end, - I = case Type of - any -> I0; - none -> I0; - _ -> beam_ssa:add_anno(result_type, Type, I0) - end, - Ts = Ts0#{ Dst => Type }, - Ds = Ds0#{ Dst => I }, - {Ts, Ds, I}. +opt_local_call_return(I, Callee, Fdb) -> + case Fdb of + #{ Callee := #func_info{ret_type=[Type]} } when Type =/= any -> + beam_ssa:add_anno(result_type, Type, I); + #{} -> + I + end. %% While we have no way to know which arguments a fun will be called with, we %% do know its free variables and can update their types as if this were a @@ -443,7 +328,7 @@ opt_make_fun(#b_set{op=make_fun, #{ Callee := #func_info{exported=false,arg_types=ArgTypes0}=Info } -> ArgCount = Callee#b_local.arity - length(FreeVars), - FVTypes = [get_type(FreeVar, Ts) || FreeVar <- FreeVars], + FVTypes = [raw_type(FreeVar, Ts) || FreeVar <- FreeVars], Types = duplicate(ArgCount, any) ++ FVTypes, CallId = {D#d.func_id, Dst}, @@ -486,8 +371,10 @@ 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 beam_types:get_tuple_size(get_type(Tuple, Ts)) of - {_,Size} when is_integer(Index), 1 =< Index, Index =< Size -> + case normalized_type(Tuple, Ts) of + #t_tuple{size=Size} when is_integer(Index), + 1 =< Index, + Index =< Size -> I = I0#b_set{op=get_tuple_element, args=[Tuple,#b_literal{val=Index-1}]}, simplify(I, Ts); @@ -495,28 +382,28 @@ simplify(#b_set{op={bif,element},args=[#b_literal{val=Index},Tuple]}=I0, Ts) -> eval_bif(I0, Ts) end; simplify(#b_set{op={bif,hd},args=[List]}=I, Ts) -> - case get_type(List, Ts) of + case normalized_type(List, Ts) of cons -> I#b_set{op=get_hd}; _ -> eval_bif(I, Ts) end; simplify(#b_set{op={bif,tl},args=[List]}=I, Ts) -> - case get_type(List, Ts) of + case normalized_type(List, Ts) of cons -> I#b_set{op=get_tl}; _ -> eval_bif(I, Ts) end; simplify(#b_set{op={bif,size},args=[Term]}=I, Ts) -> - case get_type(Term, Ts) of + case normalized_type(Term, Ts) of #t_tuple{} -> simplify(I#b_set{op={bif,tuple_size}}, Ts); _ -> eval_bif(I, Ts) end; simplify(#b_set{op={bif,tuple_size},args=[Term]}=I, Ts) -> - case get_type(Term, Ts) of + case normalized_type(Term, Ts) of #t_tuple{size=Size,exact=true} -> #b_literal{val=Size}; _ -> @@ -524,7 +411,7 @@ simplify(#b_set{op={bif,tuple_size},args=[Term]}=I, Ts) -> end; simplify(#b_set{op={bif,is_function},args=[Fun,#b_literal{val=Arity}]}=I, Ts) when is_integer(Arity), Arity >= 0 -> - case get_type(Fun, Ts) of + case normalized_type(Fun, Ts) of #t_fun{arity=any} -> I; #t_fun{arity=Arity} -> @@ -535,15 +422,15 @@ simplify(#b_set{op={bif,is_function},args=[Fun,#b_literal{val=Arity}]}=I, Ts) #b_literal{val=false} end; simplify(#b_set{op={bif,Op0},args=Args}=I, Ts) when Op0 =:= '=='; Op0 =:= '/=' -> - Types = get_types(Args, Ts), + Types = normalized_types(Args, Ts), EqEq0 = case {beam_types:meet(Types),beam_types:join(Types)} of - {none,any} -> true; - {#t_integer{},#t_integer{}} -> true; - {float,float} -> true; - {#t_bitstring{},_} -> true; - {#t_atom{},_} -> true; - {_,_} -> false - end, + {none,any} -> true; + {#t_integer{},#t_integer{}} -> true; + {float,float} -> true; + {#t_bitstring{},_} -> true; + {#t_atom{},_} -> true; + {_,_} -> false + end, EqEq = EqEq0 orelse any_non_numeric_argument(Args, Ts), case EqEq of true -> @@ -557,33 +444,35 @@ simplify(#b_set{op={bif,Op0},args=Args}=I, Ts) when Op0 =:= '=='; Op0 =:= '/=' - end; 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 beam_types:meet(T1, T2) of +simplify(#b_set{op={bif,'=:='},args=[LHS,RHS]}=I, Ts) -> + LType = raw_type(LHS, Ts), + RType = raw_type(RHS, Ts), + case beam_types:meet(LType, RType) of none -> #b_literal{val=false}; _ -> - case {beam_types:is_boolean_type(T1),T2} of + case {beam_types:is_boolean_type(LType), + beam_types:normalize(RType)} of {true,#t_atom{elements=[true]}} -> %% Bool =:= true ==> Bool - A1; + LHS; {true,#t_atom{elements=[false]}} -> %% Bool =:= false ==> not Bool %% %% This will be further optimized to eliminate the %% 'not', swapping the success and failure - %% branches in the br instruction. If A1 comes + %% branches in the br instruction. If LHS comes %% from a type test (such as is_atom/1) or a %% comparison operator (such as >=) that can be %% translated to test instruction, this %% optimization will eliminate one instruction. - simplify(I#b_set{op={bif,'not'},args=[A1]}, Ts); + simplify(I#b_set{op={bif,'not'},args=[LHS]}, Ts); {_,_} -> eval_bif(I, Ts) end end; simplify(#b_set{op={bif,Op},args=Args}=I, Ts) -> - Types = get_types(Args, Ts), + Types = normalized_types(Args, Ts), case is_float_op(Op, Types) of false -> eval_bif(I, Ts); @@ -592,20 +481,15 @@ simplify(#b_set{op={bif,Op},args=Args}=I, Ts) -> eval_bif(beam_ssa:add_anno(float_op, AnnoArgs, I), Ts) end; 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 = 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. - %% #b_literal{val=ignored}; - I + #t_tuple{size=Size,elements=Es} = normalized_type(Tuple, Ts), + true = Size > N, %Assertion. + 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; simplify(#b_set{op=is_nonempty_list,args=[Src]}=I, Ts) -> - case get_type(Src, Ts) of + case normalized_type(Src, Ts) of any -> I; list -> I; cons -> #b_literal{val=true}; @@ -613,7 +497,7 @@ simplify(#b_set{op=is_nonempty_list,args=[Src]}=I, Ts) -> end; simplify(#b_set{op=is_tagged_tuple, args=[Src,#b_literal{val=Size},#b_literal{}=Tag]}=I, Ts) -> - simplify_is_record(I, get_type(Src, Ts), Size, Tag, Ts); + simplify_is_record(I, normalized_type(Src, Ts), Size, Tag, Ts); simplify(#b_set{op=put_list,args=[#b_literal{val=H}, #b_literal{val=T}]}, _Ts) -> #b_literal{val=[H|T]}; @@ -626,12 +510,63 @@ simplify(#b_set{op=wait_timeout,args=[#b_literal{val=0}]}, _Ts) -> #b_literal{val=true}; simplify(#b_set{op=wait_timeout,args=[#b_literal{val=infinity}]}=I, _Ts) -> I#b_set{op=wait,args=[]}; +simplify(#b_set{op=call,args=[#b_remote{}=Rem|Args]}=I, _Ts) -> + case Rem of + #b_remote{mod=#b_literal{val=Mod}, + name=#b_literal{val=Name}} -> + case erl_bifs:is_pure(Mod, Name, length(Args)) of + true -> + simplify_remote_call(Mod, Name, Args, I); + false -> + I + end; + #b_remote{} -> + I + end; simplify(I, _Ts) -> I. +%% Simplify a remote call to a pure BIF. +simplify_remote_call(erlang, '++', [#b_literal{val=[]},Tl], _I) -> + Tl; +simplify_remote_call(erlang, setelement, + [#b_literal{val=Pos}, + #b_literal{val=Tuple}, + #b_var{}=Value], I) + when is_integer(Pos), 1 =< Pos, Pos =< tuple_size(Tuple) -> + %% Position is a literal integer and the shape of the + %% tuple is known. + Els0 = [#b_literal{val=El} || El <- tuple_to_list(Tuple)], + {Bef,[_|Aft]} = split(Pos - 1, Els0), + Els = Bef ++ [Value|Aft], + I#b_set{op=put_tuple,args=Els}; +simplify_remote_call(Mod, Name, Args0, I) -> + case make_literal_list(Args0) of + none -> + I; + Args -> + %% The arguments are literals. Try to evaluate the BIF. + try apply(Mod, Name, Args) of + Val -> + case cerl:is_literal_term(Val) of + true -> + #b_literal{val=Val}; + false -> + %% The value can't be expressed as a literal + %% (e.g. a pid). + I + end + catch + _:_ -> + %% Failed. Don't bother trying to optimize + %% the call. + I + end + end. + any_non_numeric_argument([#b_literal{val=Lit}|_], _Ts) -> is_non_numeric(Lit); any_non_numeric_argument([#b_var{}=V|T], Ts) -> - is_non_numeric_type(get_type(V, Ts)) orelse any_non_numeric_argument(T, Ts); + is_non_numeric_type(raw_type(V, Ts)) orelse any_non_numeric_argument(T, Ts); any_non_numeric_argument([], _Ts) -> false. is_non_numeric([H|T]) -> @@ -649,7 +584,7 @@ is_non_numeric(_) -> true. is_non_numeric_tuple(Tuple, El) when El >= 1 -> is_non_numeric(element(El, Tuple)) andalso - is_non_numeric_tuple(Tuple, El-1); + is_non_numeric_tuple(Tuple, El-1); is_non_numeric_tuple(_Tuple, 0) -> true. is_non_numeric_type(#t_atom{}) -> true; @@ -676,9 +611,11 @@ make_literal_list([_|_], _) -> make_literal_list([], Acc) -> reverse(Acc). -is_safe_bool_op(Args, Ts) -> - [T1,T2] = get_types(Args, Ts), - beam_types:is_boolean_type(T1) andalso beam_types:is_boolean_type(T2). +is_safe_bool_op([LHS, RHS], Ts) -> + LType = raw_type(LHS, Ts), + RType = raw_type(RHS, Ts), + beam_types:is_boolean_type(LType) andalso + beam_types:is_boolean_type(RType). all_same([{H,_}|T]) -> all(fun({E,_}) -> E =:= H end, T). @@ -691,7 +628,7 @@ eval_bif(#b_set{op={bif,Bif},args=Args}=I, Ts) -> true -> case make_literal_list(Args) of none -> - case get_types(Args, Ts) of + case normalized_types(Args, Ts) of [any] -> I; [Type] -> @@ -724,8 +661,7 @@ simplify_arg(#b_var{}=Arg0, Sub, Ts) -> #b_literal{}=LitArg -> LitArg; #b_var{}=Arg -> - Type = get_type(Arg, Ts), - case beam_types:get_singleton_value(Type) of + case beam_types:get_singleton_value(raw_type(Arg, Ts)) of {ok, Val} -> #b_literal{val=Val}; error -> Arg end @@ -766,7 +702,7 @@ opt_terminator(#b_br{bool=#b_var{}}=Br, Ts, Ds) -> opt_terminator(#b_switch{arg=#b_literal{}}=Sw, _Ts, _Ds) -> beam_ssa:normalize(Sw); opt_terminator(#b_switch{arg=#b_var{}=V}=Sw, Ts, Ds) -> - case get_type(V, Ts) of + case normalized_type(V, Ts) of any -> beam_ssa:normalize(Sw); Type -> @@ -796,7 +732,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 beam_types:meet(get_type(Arg, Ts), Type) of + case beam_types:meet(raw_type(Arg, Ts), Type) of none -> %% Different types. This value can never match. prune_switch_list(T, Fail, Type, Ts); @@ -805,82 +741,91 @@ prune_switch_list([{Arg,_}=Pair|T], Fail, Type, Ts) -> end; prune_switch_list([], _, _, _) -> []. -update_successors(#b_br{bool=#b_literal{val=true},succ=S}, Ts, D) -> - update_successor(S, Ts, D); -update_successors(#b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail}, Ts0, D0) -> - case cerl_sets:is_element(Bool, D0#d.once) of - true -> - %% This variable is defined in this block and is only - %% referenced by this br terminator. Therefore, there is - %% no need to include it in the type database passed on to - %% the successors of this block. - Ts = maps:remove(Bool, Ts0), - {SuccTs,FailTs} = infer_types_br(Bool, Ts, D0), - D = update_successor(Fail, FailTs, D0), - update_successor(Succ, SuccTs, D); - false -> - {SuccTs,FailTs} = infer_types_br(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}, Ts, D0) -> - case cerl_sets:is_element(V, D0#d.once) of - true -> - %% This variable is defined in this block and is only - %% referenced by this switch terminator. Therefore, there is - %% no need to include it in the type database passed on to - %% the successors of this block. - D = update_successor(Fail, Ts, D0), - F = fun({Val,S}, A) -> - SuccTs0 = infer_types_switch(V, Val, Ts, D), - SuccTs = maps:remove(V, SuccTs0), - update_successor(S, SuccTs, A) - end, - foldl(F, D, List); - false -> - %% V can not be equal to any of the values in List at the fail - %% block. - FailTs = subtract_sw_list(V, List, Ts), - D = update_successor(Fail, FailTs, D0), - F = fun({Val,S}, A) -> - SuccTs = infer_types_switch(V, Val, Ts, D), - update_successor(S, SuccTs, A) - end, - foldl(F, D, List) +update_successors(#b_br{bool=#b_literal{val=true},succ=Succ}=Last, Ts, D0) -> + {Last, update_successor(Succ, Ts, D0)}; +update_successors(#b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail}=Last0, + Ts, D0) -> + UsedOnce = cerl_sets:is_element(Bool, D0#d.once), + case infer_types_br(Bool, Ts, UsedOnce, D0) of + {#{}=SuccTs, #{}=FailTs} -> + D1 = update_successor(Succ, SuccTs, D0), + D = update_successor(Fail, FailTs, D1), + {Last0, D}; + {#{}=SuccTs, none} -> + Last = Last0#b_br{bool=#b_literal{val=true},fail=Succ}, + {Last, update_successor(Succ, SuccTs, D0)}; + {none, #{}=FailTs} -> + Last = Last0#b_br{bool=#b_literal{val=true},succ=Fail}, + {Last, update_successor(Fail, FailTs, D0)} end; -update_successors(#b_ret{arg=Arg}, Ts, D) -> - FuncId = D#d.func_id, - case D#d.ds of - #{ Arg := #b_set{op=call,args=[FuncId | _]} } -> - %% Returning a call to ourselves doesn't affect our own return - %% type. - D; +update_successors(#b_switch{arg=#b_var{}=V,fail=Fail0,list=List0}=Last0, + Ts, D0) -> + UsedOnce = cerl_sets:is_element(V, D0#d.once), + + {List1, D1} = update_switch(List0, V, Ts, UsedOnce, [], D0), + FailTs = update_switch_failure(V, List0, Ts, UsedOnce, D1), + + case FailTs of + none -> + %% The fail block is unreachable; swap it with one of the choices. + [{_, Fail} | List] = List1, + Last = Last0#b_switch{fail=Fail,list=List}, + {Last, D1}; #{} -> - RetType = beam_types:join([get_type(Arg, Ts) | D#d.ret_type]), - D#d{ret_type=[RetType]} - end. + D = update_successor(Fail0, FailTs, D1), + Last = Last0#b_switch{list=List1}, + {Last, D} + end; +update_successors(#b_ret{arg=Arg}=Last, Ts, D0) -> + FuncId = D0#d.func_id, + D = case D0#d.ds of + #{ Arg := #b_set{op=call,args=[FuncId | _]} } -> + %% Returning a call to ourselves doesn't affect our own return + %% type. + D0; + #{} -> + RetType = beam_types:join([raw_type(Arg, Ts) | D0#d.ret_type]), + D0#d{ret_type=[RetType]} + end, + {Last, D}. + +update_switch([{Val, Lbl}=Sw | List], V, Ts, UsedOnce, Acc, D0) -> + case infer_types_switch(V, Val, Ts, UsedOnce, D0) of + none -> + update_switch(List, V, Ts, UsedOnce, Acc, D0); + SwTs -> + D = update_successor(Lbl, SwTs, D0), + update_switch(List, V, Ts, UsedOnce, [Sw | Acc], D) + end; +update_switch([], _V, _Ts, _UsedOnce, Acc, D) -> + {reverse(Acc), D}. -subtract_sw_list(V, List, Ts) -> - Ts#{ V := sub_sw_list_1(get_type(V, Ts), List, Ts) }. +update_switch_failure(V, List, Ts, UsedOnce, D) -> + case sub_sw_list_1(raw_type(V, Ts), List, Ts) of + none -> + none; + FailType -> + case beam_types:get_singleton_value(FailType) of + {ok, Value} -> + %% This is the only possible value at the fail label, so we + %% can infer types as if we matched it directly. + Lit = #b_literal{val=Value}, + infer_types_switch(V, Lit, Ts, UsedOnce, D); + error when UsedOnce -> + ts_remove_var(V, Ts); + error -> + Ts + end + end. sub_sw_list_1(Type, [{Val,_}|T], Ts) -> - ValType = get_type(Val, Ts), + ValType = raw_type(Val, Ts), sub_sw_list_1(beam_types:subtract(Type, ValType), T, Ts); sub_sw_list_1(Type, [], _Ts) -> Type. -update_successor_bool(#b_var{}=Var, BoolValue, S, Ts, D) -> - case beam_types:is_boolean_type(get_type(Var, Ts)) of - true -> - 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`. - update_successor(S, Ts, D) - end. - -update_successor(?BADARG_BLOCK, _Ts, #d{}=D) -> - %% We KNOW that no variables are used in the ?BADARG_BLOCK, +update_successor(?EXCEPTION_BLOCK, _Ts, #d{}=D) -> + %% We KNOW that no variables are used in the ?EXCEPTION_BLOCK, %% so there is no need to update the type information. That %% can be a huge timesaver for huge functions. D; @@ -893,80 +838,78 @@ update_successor(S, Ts0, #d{ls=Ls}=D) -> D#d{ls=Ls#{S=>Ts0}} end. -update_types(#b_set{op=Op,dst=Dst,args=Args}, Ts, Ds) -> - T = type(Op, Args, Ts, Ds), +update_types(#b_set{op=Op,dst=Dst,anno=Anno,args=Args}, Ts, Ds) -> + T = type(Op, Args, Anno, Ts, Ds), Ts#{Dst=>T}. -type(phi, Args, Ts, _Ds) -> - Types = [get_type(A, Ts) || {A,_} <- Args], +type(phi, Args, _Anno, Ts, _Ds) -> + Types = [raw_type(A, Ts) || {A,_} <- Args], beam_types:join(Types); -type({bif,Bif}, Args, Ts, _Ds) -> - {RetType, _, _} = beam_call_types:types(erlang, Bif, get_types(Args, Ts)), +type({bif,Bif}, Args, _Anno, Ts, _Ds) -> + ArgTypes = normalized_types(Args, Ts), + {RetType, _, _} = beam_call_types:types(erlang, Bif, ArgTypes), RetType; -type(bs_init, _Args, _Ts, _Ds) -> +type(bs_init, _Args, _Anno, _Ts, _Ds) -> #t_bitstring{}; -type(bs_extract, [Ctx], _Ts, Ds) -> +type(bs_extract, [Ctx], _Anno, _Ts, Ds) -> #b_set{op=bs_match,args=Args} = map_get(Ctx, Ds), bs_match_type(Args); -type(bs_match, _Args, _Ts, _Ds) -> +type(bs_match, _Args, _Anno, _Ts, _Ds) -> #t_bs_context{}; -type(bs_get_tail, _Args, _Ts, _Ds) -> +type(bs_get_tail, _Args, _Anno, _Ts, _Ds) -> #t_bitstring{}; +type(call, [#b_local{} | _Args], Anno, _Ts, _Ds) -> + case Anno of + #{ result_type := Type } -> Type; + #{} -> any + end; type(call, [#b_remote{mod=#b_literal{val=Mod}, - name=#b_literal{val=Name}}|Args], Ts, _Ds) -> - {RetType, _, _} = beam_call_types:types(Mod, Name, get_types(Args, Ts)), + name=#b_literal{val=Name}}|Args], _Anno, Ts, _Ds) -> + ArgTypes = normalized_types(Args, Ts), + {RetType, _, _} = beam_call_types:types(Mod, Name, ArgTypes), RetType; -type(get_tuple_element, [Tuple, Offset], Ts, _Ds) -> - #t_tuple{size=Size,elements=Es} = get_type(Tuple, Ts), +type(get_tuple_element, [Tuple, Offset], _Anno, Ts, _Ds) -> + #t_tuple{size=Size,elements=Es} = normalized_type(Tuple, Ts), #b_literal{val=N} = Offset, true = Size > N, %Assertion. beam_types:get_element_type(N + 1, Es); -type(is_nonempty_list, [_], _Ts, _Ds) -> +type(is_nonempty_list, [_], _Anno, _Ts, _Ds) -> beam_types:make_boolean(); -type(is_tagged_tuple, [_,#b_literal{},#b_literal{}], _Ts, _Ds) -> +type(is_tagged_tuple, [_,#b_literal{},#b_literal{}], _Anno, _Ts, _Ds) -> beam_types:make_boolean(); -type(make_fun, [#b_local{arity=TotalArity}|Env], _Ts, _Ds) -> +type(make_fun, [#b_local{arity=TotalArity}|Env], _Anno, _Ts, _Ds) -> #t_fun{arity=TotalArity-length(Env)}; -type(put_map, _Args, _Ts, _Ds) -> +type(put_map, _Args, _Anno, _Ts, _Ds) -> #t_map{}; -type(put_list, _Args, _Ts, _Ds) -> +type(put_list, _Args, _Anno, _Ts, _Ds) -> cons; -type(put_tuple, Args, Ts, _Ds) -> +type(put_tuple, Args, _Anno, Ts, _Ds) -> {Es, _} = foldl(fun(Arg, {Es0, Index}) -> - Type = get_type(Arg, Ts), + Type = raw_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) -> +type(succeeded, [#b_var{}=Src], _Anno, Ts, _Ds) + when map_get(Src, Ts) =:= none -> + beam_types:make_atom(false); +type(succeeded, [#b_var{}=Src], _Anno, Ts, Ds) -> case maps:get(Src, Ds) of #b_set{op={bif,Bif},args=BifArgs} -> - Types = get_types(BifArgs, Ts), - case {Bif,Types} of - {BoolOp,[T1,T2]} when BoolOp =:= 'and'; BoolOp =:= 'or' -> - 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,[#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 beam_types:is_boolean_type(Type) of - true -> beam_types:make_atom(true); - false -> beam_types:make_boolean() - end; - {size,[#t_bitstring{}]} -> - beam_types:make_atom(true); - {tuple_size,[#t_tuple{}]} -> - beam_types:make_atom(true); - {_,_} -> - beam_types:make_boolean() + ArgTypes = normalized_types(BifArgs, Ts), + case beam_call_types:will_succeed(erlang, Bif, ArgTypes) of + yes -> beam_types:make_atom(true); + no -> beam_types:make_atom(false); + maybe -> beam_types:make_boolean() + end; + #b_set{op=call,args=[#b_remote{mod=#b_literal{val=Mod}, + name=#b_literal{val=Func}} | + CallArgs]} -> + ArgTypes = normalized_types(CallArgs, Ts), + case beam_call_types:will_succeed(Mod, Func, ArgTypes) of + yes -> beam_types:make_atom(true); + no -> beam_types:make_atom(false); + maybe -> beam_types:make_boolean() end; #b_set{op=get_hd} -> beam_types:make_atom(true); @@ -974,14 +917,16 @@ type(succeeded, [#b_var{}=Src], Ts, Ds) -> beam_types:make_atom(true); #b_set{op=get_tuple_element} -> beam_types:make_atom(true); + #b_set{op=put_tuple} -> + beam_types:make_atom(true); #b_set{op=wait} -> beam_types:make_atom(false); #b_set{} -> beam_types:make_boolean() end; -type(succeeded, [#b_literal{}], _Ts, _Ds) -> +type(succeeded, [#b_literal{}], _Anno, _Ts, _Ds) -> beam_types:make_atom(true); -type(_, _, _, _) -> any. +type(_, _, _, _, _) -> any. %% will_succeed(TestOperation, Type) -> yes|no|maybe. %% Test whether TestOperation applied to an argument of type Type @@ -1138,7 +1083,7 @@ simplify_is_record(I, #t_tuple{exact=Exact, {ok, _} -> no; error -> %% Is it at all possible for the tag to match? - case beam_types:meet(get_type(RecTag, Ts), TagType) of + case beam_types:meet(raw_type(RecTag, Ts), TagType) of none -> no; _ -> maybe end @@ -1168,7 +1113,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 beam_types:is_boolean_type(get_type(Bool, Ts)) of + case beam_types:is_boolean_type(raw_type(Bool, Ts)) of true -> Br = Br0#b_br{bool=Bool,succ=Fail,fail=Succ}, beam_ssa:normalize(Br); @@ -1236,16 +1181,18 @@ used_once_last_uses([V|Vs], L, Uses) -> end; used_once_last_uses([], _, Uses) -> Uses. +normalized_types(Values, Ts) -> + [normalized_type(Val, Ts) || Val <- Values]. -get_types(Values, Ts) -> - [get_type(Val, Ts) || Val <- Values]. --spec get_type(beam_ssa:value(), type_db()) -> type(). +normalized_type(V, Ts) -> + beam_types:normalize(raw_type(V, Ts)). -get_type(#b_var{}=V, Ts) -> - #{V:=T} = Ts, - T; -get_type(#b_literal{val=Val}, _Ts) -> - beam_types:make_type_from_value(Val). +-spec raw_type(beam_ssa:value(), type_db()) -> type(). + +raw_type(#b_literal{val=Value}, _Ts) -> + beam_types:make_type_from_value(Value); +raw_type(V, Ts) -> + map_get(V, Ts). %% infer_types(Var, Types, #d{}) -> {SuccTypes,FailTypes} %% Looking at the expression that defines the variable Var, infer @@ -1268,82 +1215,67 @@ get_type(#b_literal{val=Val}, _Ts) -> %% 'cons' would give 'nil' as the only possible type. The result of the %% subtraction for L will be added to FailTypes. -infer_types_br(#b_var{}=V, Ts, #d{ds=Ds}) -> +infer_types_br(#b_var{}=V, Ts, UsedOnce, #d{ds=Ds}) -> #{V:=#b_set{op=Op,args=Args}} = Ds, - {PosTypes0, NegTypes0} = infer_type(Op, Args, Ts, 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'. + {PosTypes, NegTypes} = infer_type(Op, Args, Ts, Ds), - EqTypes = infer_eq_type(Op, Args, Ts, Ds), - NegTypes1 = [P || {_,T}=P <- EqTypes, beam_types:is_singleton_type(T)], + SuccTs0 = meet_types(PosTypes, Ts), + FailTs0 = subtract_types(NegTypes, Ts), - PosTypes = EqTypes ++ PosTypes0, - SuccTs = meet_types(PosTypes, Ts), - - NegTypes = NegTypes0 ++ NegTypes1, - FailTs = subtract_types(NegTypes, Ts), - - {SuccTs,FailTs}. + case UsedOnce of + true -> + %% The branch variable is defined in this block and is only + %% referenced by this terminator. Therefore, there is no need to + %% include it in the type database passed on to the successors of + %% of this block. + SuccTs = ts_remove_var(V, SuccTs0), + FailTs = ts_remove_var(V, FailTs0), + {SuccTs, FailTs}; + false -> + SuccTs = infer_br_value(V, true, SuccTs0), + FailTs = infer_br_value(V, false, FailTs0), + {SuccTs, FailTs} + end. -infer_types_switch(V, Lit, Ts, #d{ds=Ds}) -> - Types = infer_eq_type({bif,'=:='}, [V, Lit], Ts, Ds), - meet_types(Types, Ts). +infer_br_value(_V, _Bool, none) -> + none; +infer_br_value(V, Bool, NewTs) -> + #{ V := T } = NewTs, + case beam_types:is_boolean_type(T) of + true -> + NewTs#{ V := beam_types:make_atom(Bool) }; + false -> + %% V is a try/catch tag or similar, leave it alone. + NewTs + end. -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_eq_lit(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 = beam_types:meet(Type0, Type1), - [{V,MeetType} || - {V,OrigType,MeetType} <- - [{Arg0,Type0,Type},{Arg1,Type1,Type}], - OrigType =/= MeetType]; -infer_eq_type(_Op, _Args, _Ts, _Ds) -> - []. +infer_types_switch(V, Lit, Ts0, UsedOnce, #d{ds=Ds}) -> + {PosTypes, _} = infer_type({bif,'=:='}, [V, Lit], Ts0, Ds), + Ts = meet_types(PosTypes, Ts0), + case UsedOnce of + true -> ts_remove_var(V, Ts); + false -> Ts + end. -infer_eq_lit(#b_set{op={bif,tuple_size},args=[#b_var{}=Tuple]}, - #b_literal{val=Size}) when is_integer(Size) -> - [{Tuple,#t_tuple{exact=true,size=Size}}]; -infer_eq_lit(#b_set{op=get_tuple_element, - args=[#b_var{}=Tuple,#b_literal{val=N}]}, - #b_literal{}=Lit) -> - Index = N + 1, - Es = beam_types:set_element_type(Index, get_type(Lit, #{}), #{}), - [{Tuple,#t_tuple{size=Index,elements=Es}}]; -infer_eq_lit(_, _) -> []. +ts_remove_var(_V, none) -> none; +ts_remove_var(V, Ts) -> maps:remove(V, Ts). infer_type(succeeded, [#b_var{}=Src], Ts, Ds) -> #b_set{op=Op,args=Args} = maps:get(Src, Ds), - 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_success_type(Op, Args, Ts, Ds); + +%% Type tests are handled separately from other BIFs as we're inferring types +%% based on their result, so we know that subtraction is safe even if we're +%% not branching on 'succeeded'. 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, #{}), #{}), + Es = beam_types:set_element_type(1, raw_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(is_nonempty_list, [#b_var{}=Src], _Ts, _Ds) -> + T = {Src,cons}, + {[T], [T]}; infer_type({bif,is_atom}, [Arg], _Ts, _Ds) -> T = {Arg, #t_atom{}}, {[T], [T]}; @@ -1374,9 +1306,43 @@ infer_type({bif,is_number}, [Arg], _Ts, _Ds) -> infer_type({bif,is_tuple}, [Arg], _Ts, _Ds) -> T = {Arg, #t_tuple{}}, {[T], [T]}; +infer_type({bif,'=:='}, [#b_var{}=LHS,#b_var{}=RHS], 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'). + LType = raw_type(LHS, Ts), + RType = raw_type(RHS, Ts), + Type = beam_types:meet(LType, RType), -infer_type({bif,Op}, Args, Ts, _Ds) -> - ArgTypes = get_types(Args, Ts), + PosTypes = [{V,Type} || {V, OrigType} <- [{LHS, LType}, {RHS, RType}], + OrigType =/= Type], + + %% 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'. + NegTypes = case beam_types:is_singleton_type(Type) of + true -> PosTypes; + false -> [] + end, + + {PosTypes, NegTypes}; +infer_type({bif,'=:='}, [#b_var{}=Src,#b_literal{}=Lit], Ts, Ds) -> + Def = maps:get(Src, Ds), + Type = raw_type(Lit, Ts), + EqLitTypes = infer_eq_lit(Def, Lit), + PosTypes = [{Src,Type} | EqLitTypes], + {PosTypes, EqLitTypes}; +infer_type(_Op, _Args, _Ts, _Ds) -> + {[], []}. + +infer_success_type({bif,Op}, Args, Ts, _Ds) -> + ArgTypes = normalized_types(Args, Ts), {_, PosTypes0, CanSubtract} = beam_call_types:types(erlang, Op, ArgTypes), PosTypes = [T || {#b_var{},_}=T <- zip(Args, PosTypes0)], @@ -1385,10 +1351,27 @@ infer_type({bif,Op}, Args, Ts, _Ds) -> true -> {PosTypes, PosTypes}; false -> {PosTypes, []} end; - -infer_type(_Op, _Args, _Ts, _Ds) -> +infer_success_type(call, [#b_var{}=Fun|Args], _Ts, _Ds) -> + T = {Fun, #t_fun{arity=length(Args)}}, + {[T], []}; +infer_success_type(bs_start_match, [#b_var{}=Bin], _Ts, _Ds) -> + T = {Bin,#t_bitstring{}}, + {[T], [T]}; +infer_success_type(_Op, _Args, _Ts, _Ds) -> {[], []}. +infer_eq_lit(#b_set{op={bif,tuple_size},args=[#b_var{}=Tuple]}, + #b_literal{val=Size}) when is_integer(Size) -> + [{Tuple,#t_tuple{exact=true,size=Size}}]; +infer_eq_lit(#b_set{op=get_tuple_element, + args=[#b_var{}=Tuple,#b_literal{val=N}]}, + #b_literal{}=Lit) -> + Index = N + 1, + Es = beam_types:set_element_type(Index, raw_type(Lit, #{}), #{}), + [{Tuple,#t_tuple{size=Index,elements=Es}}]; +infer_eq_lit(_, _) -> + []. + join_types(Ts0, Ts1) -> if map_size(Ts0) < map_size(Ts1) -> @@ -1417,6 +1400,7 @@ join_types_1([], Ts0, Ts1) -> meet_types([{V,T0}|Vs], Ts) -> #{V:=T1} = Ts, case beam_types:meet(T0, T1) of + none -> none; T1 -> meet_types(Vs, Ts); T -> meet_types(Vs, Ts#{V:=T}) end; @@ -1425,7 +1409,9 @@ meet_types([], Ts) -> Ts. subtract_types([{V,T0}|Vs], Ts) -> #{V:=T1} = Ts, case beam_types:subtract(T1, T0) of + none -> none; T1 -> subtract_types(Vs, Ts); T -> subtract_types(Vs, Ts#{V:=T}) end; subtract_types([], Ts) -> Ts. + |