diff options
Diffstat (limited to 'lib/compiler/src/beam_ssa_type.erl')
| -rw-r--r-- | lib/compiler/src/beam_ssa_type.erl | 616 |
1 files changed, 398 insertions, 218 deletions
diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 32583f5abf..5fbb679c6f 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -23,7 +23,8 @@ -include("beam_ssa_opt.hrl"). -import(lists, [all/2,any/2,droplast/1,foldl/3,last/1,member/2, - partition/2,reverse/1,sort/1]). + keyfind/3,partition/2,reverse/1,reverse/2, + seq/2,sort/1]). -define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}). @@ -44,12 +45,13 @@ -record(t_bs_match, {type :: type()}). -record(t_tuple, {size=0 :: integer(), exact=false :: boolean(), - elements=[] :: [any()] - }). + %% 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_integer{} | #t_bs_match{} | #t_tuple{} | - {'binary',pos_integer()} | 'cons' | 'float' | 'list' | 'map' | 'nil' |'number'. + {'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 @@ -123,7 +125,7 @@ opt_continue_1(Linear0, Args, Id, Ts, FuncDb0) -> ls=#{0=>Ts,?BADARG_BLOCK=>#{}}, once=UsedOnce }, - {Linear, FuncDb, NewRet} = opt_1(Linear0, D, []), + {Linear, FuncDb, NewRet} = opt(Linear0, D, []), case FuncDb of #{ Id := Entry0 } -> @@ -166,8 +168,11 @@ opt_finish_1([Arg | Args], [TypeMap | TypeMaps], ParamInfo0) -> opt_finish_1([], [], ParamInfo) -> ParamInfo. -validator_anno(#t_tuple{size=Size,exact=Exact}) -> - beam_validator:type_anno(tuple, Size, Exact); +validator_anno(#t_tuple{size=Size,exact=Exact,elements=Elements0}) -> + Elements = maps:fold(fun(Index, Type, Acc) -> + Acc#{ Index => validator_anno(Type) } + 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{}) -> @@ -188,57 +193,42 @@ get_func_id(Anno) -> #{func_info:={_Mod, Name, Arity}} = Anno, #b_local{name=#b_literal{val=Name}, arity=Arity}. -opt_1([{L,Blk}|Bs], #d{ls=Ls}=D, Acc) -> +opt([{L,Blk}|Bs], #d{ls=Ls}=D, Acc) -> case Ls of #{L:=Ts} -> - opt_2(L, Blk, Bs, Ts, D, Acc); + opt_1(L, Blk, Bs, Ts, D, Acc); #{} -> %% This block is never reached. Discard it. - opt_1(Bs, D, Acc) + opt(Bs, D, Acc) end; -opt_1([], D, Acc) -> +opt([], D, Acc) -> #d{func_db=FuncDb,ret_type=NewRet} = D, {reverse(Acc), FuncDb, NewRet}. -opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, #d{sub=Sub}=D0, Acc) -> - case Is0 of - [#b_set{op=call,dst=Dst, - args=[#b_remote{mod=#b_literal{val=Mod}, - name=#b_literal{val=Name}}=Rem|Args0]}=I0] -> - case erl_bifs:is_exit_bif(Mod, Name, length(Args0)) of - true -> - %% This call will never reach the successor block. - %% Rewrite the terminator to a 'ret', and remove - %% all type information for this label. That will - %% simplify the phi node in the former successor. - Args = simplify_args(Args0, Sub, Ts), - I = I0#b_set{args=[Rem|Args]}, - Ret = #b_ret{arg=Dst}, - Blk = Blk0#b_blk{is=[I],last=Ret}, - Ls = maps:remove(L, D0#d.ls), - - %% We potentially lack a return value. - RetType = join([none | D0#d.ret_type]), - - D = D0#d{ls=Ls,ret_type=[RetType]}, - opt_1(Bs, D, [{L,Blk} | Acc]); - false -> - opt_3(L, Blk0, Bs, Ts, D0, Acc) - end; - _ -> - opt_3(L, Blk0, Bs, Ts, D0, 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 = 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. -opt_3(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, - #d{ds=Ds0,ls=Ls0,sub=Sub0,func_db=Fdb0}=D0, Acc) -> - {Is,Ts,Ds,Fdb,Sub} = opt_is(Is0, Ts0, Ds0, Fdb0, Ls0, D0, Sub0, []), - 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_1(Bs, D, [{L,Blk} | Acc]). - simplify_terminator(#b_br{bool=Bool}=Br, Sub, Ts, _Ds) -> Br#b_br{bool=simplify_arg(Bool, Sub, Ts)}; simplify_terminator(#b_switch{arg=Arg}=Sw, Sub, Ts, _Ds) -> @@ -252,7 +242,7 @@ simplify_terminator(#b_ret{arg=Arg}=Ret, Sub, Ts, Ds) -> end. opt_is([#b_set{op=phi,dst=Dst,args=Args0}=I0|Is], - Ts0, Ds0, Fdb, Ls, D, Sub0, Acc) -> + Ts0, Ds0, Fdb, #d{ls=Ls}=D, Sub0, Acc) -> %% Simplify the phi node by removing all predecessor blocks that no %% longer exists or no longer branches to this block. Args = [{simplify_arg(Arg, Sub0, Ts0),From} || @@ -263,37 +253,44 @@ opt_is([#b_set{op=phi,dst=Dst,args=Args0}=I0|Is], %% value or if the values are identical. [{Val,_}|_] = Args, Sub = Sub0#{Dst=>Val}, - opt_is(Is, Ts0, Ds0, Fdb, Ls, D, Sub, Acc); + opt_is(Is, Ts0, Ds0, Fdb, D, Sub, Acc); false -> I = I0#b_set{args=Args}, Ts = update_types(I, Ts0, Ds0), Ds = Ds0#{Dst=>I}, - opt_is(Is, Ts, Ds, Fdb, Ls, D, Sub0, [I|Acc]) + 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, Ls, D, Sub, Acc) -> - Args = simplify_args(Args0, Sub, Ts0), +opt_is([#b_set{op=call,args=Args0,dst=Dst}=I0|Is], + Ts0, Ds0, Fdb0, D, Sub0, Acc) -> + Args = simplify_args(Args0, Sub0, Ts0), I1 = beam_ssa:normalize(I0#b_set{args=Args}), - - %% This is a bit of a kludge; we know that any instruction whose return - %% type is 'none' will fail at runtime, but we don't yet have a way to cut - %% a block short so we move on like nothing nothing happened. - %% - %% This complicates argument type optimization as unreachable calls can - %% add types that will never occur, so we skip optimizing this call if - %% the type of any of its arguments is 'none'. - [_Callee | Rest] = Args, - case all(fun(Arg) -> get_type(Arg, Ts0) =/= none end, Rest) of - true -> - {Ts, Ds, Fdb, I} = opt_call(I1, D, Ts0, Ds0, Fdb0), - opt_is(Is, Ts, Ds, Fdb, Ls, D, Sub, [I|Acc]); - false -> - Ts = Ts0#{ Dst => any }, - Ds = Ds0#{ Dst => I1 }, - opt_is(Is, Ts, Ds, Fdb0, Ls, D, Sub, [I1|Acc]) + {Ts1,Ds,Fdb,I2} = opt_call(I1, D, Ts0, Ds0, Fdb0), + case {map_get(Dst, Ts1),Is} of + {_,[#b_set{op=succeeded}]} -> + %% This call instruction is inside a try/catch + %% block. Don't attempt to optimize it. + opt_is(Is, Ts1, 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; opt_is([#b_set{op=succeeded,args=[Arg],dst=Dst}=I], - Ts0, Ds0, Fdb, Ls, D, Sub0, Acc) -> + 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 @@ -302,22 +299,22 @@ opt_is([#b_set{op=succeeded,args=[Arg],dst=Dst}=I], Ts = update_types(I, Ts0, Ds0), Ds = Ds0#{Dst=>I}, - opt_is([], Ts, Ds, Fdb, Ls, D, Sub0, [I|Acc]); + opt_is([], Ts, Ds, Fdb, D, Sub0, [I|Acc]); #{} -> 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}, - opt_is([], Ts0, Ds0, Fdb, Ls, D, Sub, Acc); + opt_is([], Ts0, Ds0, Fdb, D, Sub, Acc); none -> Ts = Ts0#{Dst=>Type}, Ds = Ds0#{Dst=>I}, - opt_is([], Ts, Ds, Fdb, Ls, D, Sub0, [I|Acc]) + opt_is([], Ts, Ds, Fdb, D, Sub0, [I|Acc]) end end; opt_is([#b_set{args=Args0,dst=Dst}=I0|Is], - Ts0, Ds0, Fdb, Ls, D, Sub0, Acc) -> + 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 @@ -325,24 +322,66 @@ opt_is([#b_set{args=Args0,dst=Dst}=I0|Is], I = beam_ssa:normalize(I2), Ts = update_types(I, Ts0, Ds0), Ds = Ds0#{Dst=>I}, - opt_is(Is, Ts, Ds, Fdb, Ls, D, Sub0, [I|Acc]); + opt_is(Is, Ts, Ds, Fdb, D, Sub0, [I|Acc]); #b_literal{}=Lit -> Sub = Sub0#{Dst=>Lit}, - opt_is(Is, Ts0, Ds0, Fdb, Ls, D, Sub, Acc); + 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}}, - opt_is([], Ts0, Ds0, Fdb, Ls, D, Sub, Acc); + opt_is([], Ts0, Ds0, Fdb, D, Sub, Acc); _ -> Sub = Sub0#{Dst=>Var}, - opt_is(Is, Ts0, Ds0, Fdb, Ls, D, Sub, Acc) + opt_is(Is, Ts0, Ds0, Fdb, D, Sub, Acc) end end; -opt_is([], Ts, Ds, Fdb, _Ls, _D, Sub, Acc) -> +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(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), case Fdb0 of @@ -365,14 +404,13 @@ opt_call(#b_set{dst=Dst}=I, _D, Ts0, Ds0, Fdb) -> {Ts, Ds, Fdb, I}. opt_local_call(#b_set{dst=Dst,args=[Id|_]}=I0, Ts0, Ds0, Fdb) -> - %% We skip propagating 'none' as we don't yet have a good way to cut a - %% block short. Type = case Fdb of - #{ Id := #func_info{ret_type=[T]} } when T =/= none -> T; + #{ Id := #func_info{ret_type=[T]} } -> T; #{} -> any end, I = case Type of any -> I0; + none -> I0; _ -> beam_ssa:add_anno(result_type, validator_anno(Type), I0) end, Ts = Ts0#{ Dst => Type }, @@ -386,11 +424,6 @@ update_arg_types([Arg | Args], [TypeMap0 | TypeMaps], CallId, Ts) -> #t_bs_match{} -> {binary, 1}; Type -> Type end, - PrevType = maps:get(CallId, TypeMap0, NewType), - - %% The new type must be narrower than the old one. - true = meet(NewType, PrevType) =/= none, %Assertion. - TypeMap = TypeMap0#{ CallId => NewType }, [TypeMap | update_arg_types(Args, TypeMaps, CallId, Ts)]; update_arg_types([], [], _CallId, _Ts) -> @@ -418,12 +451,14 @@ simplify(#b_set{op={bif,'or'},args=Args}=I, Ts) -> false -> I end; -simplify(#b_set{op={bif,element},args=[#b_literal{val=Index},Tuple]}=I, Ts) -> +simplify(#b_set{op={bif,element},args=[#b_literal{val=Index},Tuple]}=I0, Ts) -> case t_tuple_size(get_type(Tuple, Ts)) of {_,Size} when is_integer(Index), 1 =< Index, Index =< Size -> - I#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=Index-1}]}; + I = I0#b_set{op=get_tuple_element, + args=[Tuple,#b_literal{val=Index-1}]}, + simplify(I, Ts); _ -> - eval_bif(I, Ts) + eval_bif(I0, Ts) end; simplify(#b_set{op={bif,hd},args=[List]}=I, Ts) -> case get_type(List, Ts) of @@ -471,10 +506,19 @@ simplify(#b_set{op={bif,'=='},args=Args}=I, Ts) -> end; simplify(#b_set{op={bif,'=:='},args=[Same,Same]}, _Ts) -> #b_literal{val=true}; -simplify(#b_set{op={bif,'=:='},args=Args}=I, Ts) -> - case meet(get_types(Args, Ts)) of - none -> #b_literal{val=false}; - _ -> eval_bif(I, Ts) +simplify(#b_set{op={bif,'=:='},args=[A1,_A2]=Args}=I, Ts) -> + [T1,T2] = get_types(Args, Ts), + case meet(T1, T2) of + none -> + #b_literal{val=false}; + _ -> + case {t_is_boolean(T1),T2} of + {true,#t_atom{elements=[true]}} -> + %% Bool =:= true ==> Bool + A1; + {_,_} -> + eval_bif(I, Ts) + end end; simplify(#b_set{op={bif,Op},args=Args}=I, Ts) -> Types = get_types(Args, Ts), @@ -485,11 +529,17 @@ simplify(#b_set{op={bif,Op},args=Args}=I, Ts) -> AnnoArgs = [anno_float_arg(A) || A <- Types], eval_bif(beam_ssa:add_anno(float_op, AnnoArgs, I), Ts) end; -simplify(#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=0}]}=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{elements=[First]} -> - #b_literal{val=First}; - #t_tuple{} -> + #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 + end; + none -> + %% Will never be executed because of type conflict. + %% #b_literal{val=ignored}; I end; simplify(#b_set{op=is_nonempty_list,args=[Src]}=I, Ts) -> @@ -500,24 +550,8 @@ simplify(#b_set{op=is_nonempty_list,args=[Src]}=I, Ts) -> _ -> #b_literal{val=false} end; simplify(#b_set{op=is_tagged_tuple, - args=[Src,#b_literal{val=Size},#b_literal{val=Tag}]}=I, Ts) -> - case get_type(Src, Ts) of - #t_tuple{exact=true,size=Size,elements=[Tag]} -> - #b_literal{val=true}; - #t_tuple{exact=true,size=ActualSize,elements=[]} -> - if - Size =/= ActualSize -> - #b_literal{val=false}; - true -> - I - end; - #t_tuple{exact=false} -> - I; - any -> - I; - _ -> - #b_literal{val=false} - end; + args=[Src,#b_literal{val=Size},#b_literal{}=Tag]}=I, Ts) -> + simplify_is_record(I, get_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]}; @@ -627,41 +661,49 @@ anno_float_arg(_) -> convert. opt_terminator(#b_br{bool=#b_literal{}}=Br, _Ts, _Ds) -> beam_ssa:normalize(Br); -opt_terminator(#b_br{bool=#b_var{}=V}=Br, Ts, Ds) -> - #{V:=Set} = Ds, - case Set of - #b_set{op={bif,'=:='},args=[Bool,#b_literal{val=true}]} -> - case t_is_boolean(get_type(Bool, Ts)) of - true -> - %% Bool =:= true ==> Bool - simplify_not(Br#b_br{bool=Bool}, Ts, Ds); - false -> - Br - end; - #b_set{} -> - simplify_not(Br, Ts, Ds) - end; +opt_terminator(#b_br{bool=#b_var{}}=Br, Ts, Ds) -> + simplify_not(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}=Sw0, Ts, Ds) -> - Type = get_type(V, Ts), +opt_terminator(#b_switch{arg=#b_var{}=V}=Sw, Ts, Ds) -> + case get_type(V, Ts) of + any -> + beam_ssa:normalize(Sw); + Type -> + beam_ssa:normalize(opt_switch(Sw, Type, Ts, Ds)) + end; +opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> Ret. + + +opt_switch(#b_switch{fail=Fail,list=List0}=Sw0, Type, Ts, Ds) -> + List = prune_switch_list(List0, Fail, Type, Ts), + Sw1 = Sw0#b_switch{list=List}, case Type of #t_integer{elements={_,_}=Range} -> - simplify_switch_int(Sw0, Range); - _ -> + simplify_switch_int(Sw1, Range); + #t_atom{elements=[_|_]} -> case t_is_boolean(Type) of true -> - case simplify_switch_bool(Sw0, Ts, Ds) of - #b_br{}=Br -> - opt_terminator(Br, Ts, Ds); - Sw -> - beam_ssa:normalize(Sw) - end; + #b_br{} = Br = simplify_switch_bool(Sw1, Ts, Ds), + opt_terminator(Br, Ts, Ds); false -> - beam_ssa:normalize(Sw0) - end + simplify_switch_atom(Type, Sw1) + end; + _ -> + Sw1 + end. + +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 + none -> + %% Different types. This value can never match. + prune_switch_list(T, Fail, Type, Ts); + _ -> + [Pair|prune_switch_list(T, Fail, Type, Ts)] end; -opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> Ret. +prune_switch_list([], _, _, _) -> []. update_successors(#b_br{bool=#b_literal{val=true},succ=S}, Ts, D) -> update_successor(S, Ts, D); @@ -670,38 +712,39 @@ update_successors(#b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail}, Ts0, D0) -> true -> %% This variable is defined in this block and is only %% referenced by this br terminator. Therefore, there is - %% no need to include the type database passed on to the - %% successors of this block. + %% 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(Bool, Ts, D0), + {SuccTs,FailTs} = infer_types_br(Bool, Ts, D0), D = update_successor(Fail, FailTs, D0), update_successor(Succ, SuccTs, D); false -> - {SuccTs,FailTs} = infer_types(Bool, Ts0, D0), + {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}, Ts0, D0) -> +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 the type database passed on to the - %% successors of this block. - Ts = maps:remove(V, Ts0), + %% 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) -> - update_successor(S, Ts, A) + 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, Ts0), + FailTs = subtract_sw_list(V, List, Ts), D = update_successor(Fail, FailTs, D0), F = fun({Val,S}, A) -> - T = get_type(Val, Ts0), - update_successor(S, Ts0#{V=>T}, A) + SuccTs = infer_types_switch(V, Val, Ts, D), + update_successor(S, SuccTs, A) end, foldl(F, D, List) end; @@ -785,19 +828,40 @@ type(bs_get_tail, _Args, _Ts, _Ds) -> type(call, [#b_remote{mod=#b_literal{val=Mod}, name=#b_literal{val=Name}}|Args], Ts, _Ds) -> case {Mod,Name,Args} of - {erlang,setelement,[Pos,Tuple,_]} -> + {erlang,setelement,[Pos,Tuple,Arg]} -> case {get_type(Pos, Ts),get_type(Tuple, Ts)} of - {#t_integer{elements={MinIndex,_}},#t_tuple{}=T} - when MinIndex > 1 -> - %% First element is not updated. The result - %% will have the same type. - T; + {#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,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 = maps:without(seq(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 is 1 or unknown. May update the first - %% element of the tuple. - T#t_tuple{elements=[]}; - {#t_integer{elements={MinIndex,_}},_} -> - #t_tuple{size=MinIndex}; + %% 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; @@ -820,6 +884,11 @@ type(call, [#b_remote{mod=#b_literal{val=Mod}, false -> any end end; +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); type(is_nonempty_list, [_], _Ts, _Ds) -> t_boolean(); type(is_tagged_tuple, [_,#b_literal{},#b_literal{}], _Ts, _Ds) -> @@ -828,13 +897,13 @@ type(put_map, _Args, _Ts, _Ds) -> map; type(put_list, _Args, _Ts, _Ds) -> cons; -type(put_tuple, Args, _Ts, _Ds) -> - case Args of - [#b_literal{val=First}|_] -> - #t_tuple{exact=true,size=length(Args),elements=[First]}; - _ -> - #t_tuple{exact=true,size=length(Args)} - end; +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} + end, {#{}, 1}, Args), + #t_tuple{exact=true,size=length(Args),elements=Es}; type(succeeded, [#b_var{}=Src], Ts, Ds) -> case maps:get(Src, Ds) of #b_set{op={bif,Bif},args=BifArgs} -> @@ -1031,6 +1100,17 @@ bs_match_type(utf16, _) -> bs_match_type(utf32, _) -> ?UNICODE_INT. +simplify_switch_atom(#t_atom{elements=Atoms}, #b_switch{list=List0}=Sw) -> + case sort([A || {#b_literal{val=A},_} <- List0]) of + Atoms -> + %% All possible atoms are included in the list. The + %% failure label will never be used. + [{_,Fail}|List] = List0, + Sw#b_switch{fail=Fail,list=List}; + _ -> + Sw + end. + simplify_switch_int(#b_switch{list=List0}=Sw, {Min,Max}) -> List1 = sort(List0), Vs = [V || {#b_literal{val=V},_} <- List1], @@ -1047,14 +1127,42 @@ eq_ranges([H], H, H) -> true; eq_ranges([H|T], H, Max) -> eq_ranges(T, H+1, Max); eq_ranges(_, _, _) -> false. -simplify_switch_bool(#b_switch{arg=B,list=List0}=Sw, Ts, Ds) -> - List = sort(List0), - case List of - [{#b_literal{val=false},Fail},{#b_literal{val=true},Succ}] -> - simplify_not(#b_br{bool=B,succ=Succ,fail=Fail}, Ts, Ds); - [_|_] -> - Sw - end. +simplify_is_record(I, #t_tuple{exact=Exact, + size=Size, + elements=Es}, + RecSize, RecTag, Ts) -> + TagType = maps:get(1, Es, any), + TagMatch = case get_literal_from_type(TagType) of + #b_literal{}=RecTag -> yes; + #b_literal{} -> no; + none -> + %% Is it at all possible for the tag to match? + case meet(get_type(RecTag, Ts), TagType) of + none -> no; + _ -> maybe + end + end, + if + Size =/= RecSize, Exact; Size > RecSize; TagMatch =:= no -> + #b_literal{val=false}; + Size =:= RecSize, Exact, TagMatch =:= yes -> + #b_literal{val=true}; + true -> + I + end; +simplify_is_record(I, any, _Size, _Tag, _Ts) -> + I; +simplify_is_record(_I, _Type, _Size, _Tag, _Ts) -> + #b_literal{val=false}. + +simplify_switch_bool(#b_switch{arg=B,fail=Fail,list=List0}, Ts, Ds) -> + FalseVal = #b_literal{val=false}, + TrueVal = #b_literal{val=true}, + List1 = List0 ++ [{FalseVal,Fail},{TrueVal,Fail}], + {_,FalseLbl} = keyfind(FalseVal, 1, List1), + {_,TrueLbl} = keyfind(TrueVal, 1, List1), + Br = beam_ssa:normalize(#b_br{bool=B,succ=TrueLbl,fail=FalseLbl}), + simplify_not(Br, Ts, Ds). simplify_not(#b_br{bool=#b_var{}=V,succ=Succ,fail=Fail}=Br0, Ts, Ds) -> case Ds of @@ -1068,7 +1176,8 @@ simplify_not(#b_br{bool=#b_var{}=V,succ=Succ,fail=Fail}=Br0, Ts, Ds) -> end; #{} -> Br0 - end. + end; +simplify_not(#b_br{bool=#b_literal{}}=Br, _Ts, _Ds) -> Br. %%% %%% Calculate the set of variables that are only used once in the @@ -1149,8 +1258,12 @@ get_type(#b_literal{val=Val}, _Ts) -> Val =:= {} -> #t_tuple{exact=true}; is_tuple(Val) -> - #t_tuple{exact=true,size=tuple_size(Val), - elements=[element(1, Val)]}; + {Es, _} = foldl(fun(E, {Es0, Index}) -> + Type = get_type(#b_literal{val=E}, #{}), + Es = 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}; Val =:= [] -> nil; true -> @@ -1192,7 +1305,7 @@ get_type(#b_literal{val=Val}, _Ts) -> %% 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}) -> +infer_types_br(#b_var{}=V, Ts, #d{ds=Ds}) -> #{V:=#b_set{op=Op,args=Args}} = Ds, Types0 = infer_type(Op, Args, Ds), @@ -1213,11 +1326,14 @@ infer_types(#b_var{}=V, Ts, #d{ds=Ds}) -> Types = Types1 ++ Types0, {meet_types(EqTypes++Types, Ts),subtract_types(Types, Ts)}. +infer_types_switch(V, Lit, Ts, #d{ds=Ds}) -> + Types = infer_eq_type({bif,'=:='}, [V, Lit], Ts, Ds), + meet_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)]; + [{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 @@ -1232,6 +1348,17 @@ infer_eq_type({bif,'=:='}, [#b_var{}=Arg0,#b_var{}=Arg1], Ts, _Ds) -> infer_eq_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 = set_element_type(Index, get_type(Lit, #{}), #{}), + [{Tuple,#t_tuple{size=Index,elements=Es}}]; +infer_eq_lit(_, _) -> []. + infer_type({bif,element}, [#b_literal{val=Pos},#b_var{}=Tuple], _Ds) -> if is_integer(Pos), 1 =< Pos -> @@ -1265,8 +1392,9 @@ infer_type(bs_start_match, [#b_var{}=Bin], _Ds) -> 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{val=Tag}], _Ds) -> - [{Src,#t_tuple{exact=true,size=Size,elements=[Tag]}}]; + #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) -> #b_set{op=Op,args=Args} = maps:get(Src, Ds), infer_type(Op, Args, Ds); @@ -1359,17 +1487,6 @@ 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]}, - #b_literal{val=Size}) when is_integer(Size) -> - [{Tuple,#t_tuple{exact=true,size=Size}}]; -infer_tuple_size(_, _) -> []. - -infer_first_element(#b_set{op=get_tuple_element, - args=[#b_var{}=Tuple,#b_literal{val=0}]}, - #b_literal{val=First}) -> - [{Tuple,#t_tuple{size=1,elements=[First]}}]; -infer_first_element(_, _) -> []. - is_math_bif(cos, 1) -> true; is_math_bif(cosh, 1) -> true; is_math_bif(sin, 1) -> true; @@ -1468,6 +1585,19 @@ t_tuple_size(_) -> 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 }. + %% join(Type1, Type2) -> Type %% Return the "join" of Type1 and Type2. The join is a more general %% type than Type1 and Type2. For example: @@ -1515,15 +1645,41 @@ join(#t_integer{}, number) -> number; join(number, #t_integer{}) -> number; join(float, number) -> number; join(number, float) -> number; -join(#t_tuple{size=Sz,exact=Exact1}, #t_tuple{size=Sz,exact=Exact2}) -> - Exact = Exact1 and Exact2, - #t_tuple{size=Sz,exact=Exact}; -join(#t_tuple{size=Sz1}, #t_tuple{size=Sz2}) -> - #t_tuple{size=min(Sz1, Sz2)}; +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; @@ -1620,9 +1776,6 @@ meet(_, _) -> %% Inconsistent types. There will be an exception at runtime. none. -meet_tuples(#t_tuple{elements=[E1]}, #t_tuple{elements=[E2]}) - when E1 =/= E2 -> - none; meet_tuples(#t_tuple{size=Sz1,exact=true}, #t_tuple{size=Sz2,exact=true}) when Sz1 =/= Sz2 -> none; @@ -1630,12 +1783,31 @@ 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, - Es = case {Es1,Es2} of - {[],[_|_]} -> Es2; - {[_|_],[]} -> Es1; - {_,_} -> Es1 - end, - #t_tuple{size=Size,exact=Exact,elements=Es}. + 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. @@ -1674,5 +1846,13 @@ verified_type(map=T) -> T; verified_type(nil=T) -> T; verified_type(cons=T) -> T; verified_type(number=T) -> T; -verified_type(#t_tuple{}=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. |