diff options
Diffstat (limited to 'lib/compiler/src/beam_ssa_type.erl')
| -rw-r--r-- | lib/compiler/src/beam_ssa_type.erl | 1106 |
1 files changed, 1106 insertions, 0 deletions
diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl new file mode 100644 index 0000000000..e5f15da836 --- /dev/null +++ b/lib/compiler/src/beam_ssa_type.erl @@ -0,0 +1,1106 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2018. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% + +-module(beam_ssa_type). +-export([opt/2]). + +-include("beam_ssa.hrl"). +-import(lists, [any/2,droplast/1,foldl/3,last/1,member/2, + reverse/1,search/2,sort/1]). + +-define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}). + +-record(d, {ds :: #{beam_ssa:var_name():=beam_ssa:b_set()}, + ls :: #{beam_ssa:label():=type_db()}}). + +-define(ATOM_SET_SIZE, 5). + +%% Records that represent type information. +-record(t_atom, {elements=any :: 'any' | [atom()]}). +-record(t_integer, {elements=any :: 'any' | {integer(),integer()}}). +-record(t_bs_match, {type :: type()}). +-record(t_tuple, {size=0 :: integer(), + exact=false :: boolean(), + elements=[] :: [any()] + }). + +-type type() :: 'any' | 'none' | + #t_atom{} | #t_integer{} | #t_bs_match{} | #t_tuple{} | + {'binary',pos_integer()} | 'cons' | 'float' | 'list' | 'map' | 'nil' |'number'. +-type type_db() :: #{beam_ssa:var_name():=type()}. + +-spec opt([{Label0,Block0}], Args) -> [{Label,Block}] when + Label0 :: beam_ssa:label(), + Block0 :: beam_ssa:b_blk(), + Args :: [beam_ssa:b_var()], + Label :: beam_ssa:label(), + Block :: beam_ssa:b_blk(). + +opt(Linear, Args) -> + Ts = maps:from_list([{V,any} || #b_var{name=V} <- Args]), + FakeCall = #b_set{op=call,args=[#b_remote{mod=#b_literal{val=unknown}, + name=#b_literal{val=unknown}, + arity=0}]}, + Defs = maps:from_list([{V,FakeCall#b_set{dst=Var}} || + #b_var{name=V}=Var <- Args]), + D = #d{ds=Defs,ls=#{0=>Ts}}, + opt_1(Linear, D). + +opt_1([{L,Blk}|Bs], #d{ls=Ls}=D) -> + case Ls of + #{L:=Ts} -> + opt_2(L, Blk, Bs, Ts, D); + #{} -> + %% This block is never reached. Discard it. + opt_1(Bs, D) + end; +opt_1([], _) -> []. + +opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, D0) -> + 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_arg(Arg, Ts) || Arg <- Args0], + 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), + D = D0#d{ls=Ls}, + [{L,Blk}|opt_1(Bs, D)]; + false -> + opt_3(L, Blk0, Bs, Ts, D0) + end; + _ -> + opt_3(L, Blk0, Bs, Ts, D0) + end. + +opt_3(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, #d{ds=Ds0,ls=Ls0}=D0) -> + {Is,Ts,Ds} = opt_is(Is0, Ts0, Ds0, Ls0, []), + D1 = D0#d{ds=Ds}, + Last = opt_terminator(Last0, Ts, Ds), + D = update_successors(Last, Ts, D1), + Blk = Blk0#b_blk{is=Is,last=Last}, + [{L,Blk}|opt_1(Bs, D)]. + +opt_is([#b_set{op=phi,dst=#b_var{name=Dst},args=Args0}=I0|Is], Ts0, Ds0, Ls, Acc) -> + %% Simplify the phi node by removing all predecessor blocks that no + %% longer exists or no longer branches to this block. + Args = [P || {_,From}=P <- Args0, maps:is_key(From, Ls)], + I = I0#b_set{args=Args}, + Ts = update_types(I, Ts0, Ds0), + Ds = Ds0#{Dst=>I}, + opt_is(Is, Ts, Ds, Ls, [I|Acc]); +opt_is([#b_set{dst=#b_var{name=Dst}}=I0|Is], Ts0, Ds0, Ls, Acc) -> + I = simplify(I0, Ts0), + Ts = update_types(I, Ts0, Ds0), + Ds = Ds0#{Dst=>I}, + opt_is(Is, Ts, Ds, Ls, [I|Acc]); +opt_is([], Ts, Ds, _Ls, Acc) -> + {reverse(Acc),Ts,Ds}. + +simplify(#b_set{op={bif,element},args=[#b_literal{val=Index},Tuple]}=I, 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 + end; +simplify(#b_set{op={bif,hd},args=[List]}=I, Ts) -> + case get_type(List, Ts) of + cons -> + I#b_set{op=get_hd}; + _ -> + I + end; +simplify(#b_set{op={bif,tl},args=[List]}=I, Ts) -> + case get_type(List, Ts) of + cons -> + I#b_set{op=get_tl}; + _ -> + I + end; +simplify(#b_set{op={bif,size},args=[Term]}=I, Ts) -> + case get_type(Term, Ts) of + #t_tuple{} -> + I#b_set{op={bif,tuple_size}}; + _ -> + I + end; +simplify(#b_set{op={bif,'=='},args=Args0}=I0, Ts) -> + Args = [simplify_arg(Arg, Ts) || Arg <- Args0], + I = I0#b_set{args=Args}, + Types = get_types(Args, Ts), + EqEq = case {meet(Types),join(Types)} of + {none,any} -> true; + {#t_integer{},#t_integer{}} -> true; + {float,float} -> true; + {{binary,_},_} -> true; + {#t_atom{},_} -> true; + {_,_} -> false + end, + case EqEq of + true -> + I#b_set{op={bif,'=:='}}; + false -> + I + end; +simplify(#b_set{op={bif,Op},args=Args0}=I0, Ts) -> + Args = [simplify_arg(Arg, Ts) || Arg <- Args0], + I = I0#b_set{args=Args}, + Types = get_types(Args, Ts), + case is_float_op(Op, Types) of + false -> + I; + true -> + AnnoArgs = [anno_float_arg(A) || A <- Types], + beam_ssa:add_anno(float_op, AnnoArgs, I) + end; +simplify(#b_set{op=wait_timeout,args=[Timeout0]}=I, Ts) -> + case simplify_arg(Timeout0, Ts) of + #b_literal{val=infinity} -> + I#b_set{op=wait,args=[]}; + Timeout -> + I#b_set{args=[Timeout]} + end; +simplify(#b_set{op=Op,args=Args0}=I, Ts) -> + Safe = case Op of + call -> true; + put_list -> true; + put_tuple -> true; + _ -> false + end, + case Safe of + true -> + Args = [simplify_arg(Arg, Ts) || Arg <- Args0], + I#b_set{args=Args}; + false -> + I + end. + +simplify_arg(#b_var{}=Arg, Ts) -> + Type = get_type(Arg, Ts), + case get_literal_from_type(Type) of + none -> Arg; + #b_literal{}=Lit -> Lit + end; +simplify_arg(Arg, _Ts) -> Arg. + +is_float_op('-', [float]) -> + true; +is_float_op('/', [_,_]) -> + true; +is_float_op(Op, [float,_Other]) -> + is_float_op_1(Op); +is_float_op(Op, [_Other,float]) -> + is_float_op_1(Op); +is_float_op(_, _) -> false. + +is_float_op_1('+') -> true; +is_float_op_1('-') -> true; +is_float_op_1('*') -> true; +is_float_op_1(_) -> false. + +anno_float_arg(float) -> float; +anno_float_arg(_) -> convert. + +opt_terminator(#b_br{bool=#b_literal{}}=Br, _Ts, _Ds) -> + Br; +opt_terminator(#b_br{bool=#b_var{name=V}=Var}=Br, Ts, Ds) -> + BoolType = get_type(Var, Ts), + case get_literal_from_type(BoolType) of + #b_literal{}=BoolLit -> + Br#b_br{bool=BoolLit}; + none -> + #{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 + end; +opt_terminator(#b_switch{arg=#b_literal{val=Val0}=Arg,fail=Fail,list=List}, + _Ts, _Ds) -> + {value,{_,L}} = search(fun({#b_literal{val=Val1},_}) -> + Val1 =:= Val0 + end, List ++ [{Arg,Fail}]), + #b_br{bool=#b_literal{val=true},succ=L,fail=L}; +opt_terminator(#b_switch{arg=V}=Sw0, Ts, Ds) -> + case get_literal_from_type(Ts) of + #b_literal{}=Lit -> + Sw = Sw0#b_switch{arg=Lit}, + opt_terminator(Sw, Ts, Ds); + none -> + case get_type(V, Ts) of + #t_integer{elements={_,_}=Range} -> + simplify_switch_int(Sw0, Range); + Type -> + case t_is_boolean(Type) of + true -> + case simplify_switch_bool(Sw0, Ts, Ds) of + #b_br{}=Br -> + opt_terminator(Br, Ts, Ds); + Sw -> + Sw + end; + false -> + Sw0 + end + end + end; +opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> + Ret. + +update_successors(#b_br{bool=#b_literal{val=false},fail=S}, Ts, D) -> + update_successor(S, Ts, D); +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{name=V},succ=Succ,fail=Fail}, Ts, D0) -> + D = update_successor(Fail, Ts#{V:=t_atom(false)}, D0), + SuccTs = infer_types(V, Ts, D0), + update_successor(Succ, SuccTs#{V:=t_atom(true)}, D); +update_successors(#b_switch{arg=#b_var{name=V},fail=Fail,list=List}, Ts, D0) -> + D = update_successor(Fail, Ts, D0), + foldl(fun({Val,S}, A) -> + T = get_type(Val, Ts), + update_successor(S, Ts#{V=>T}, A) + end, D, List); +update_successors(#b_ret{}, _Ts, D) -> D. + +update_successor(S, Ts0, #d{ls=Ls}=D) -> + case Ls of + #{S:=Ts1} -> + Ts = join_types(Ts0, Ts1), + D#d{ls=Ls#{S:=Ts}}; + #{} -> + D#d{ls=Ls#{S=>Ts0}} + end. + +update_types(#b_set{op=Op,dst=#b_var{name=Dst},args=Args}, Ts, Ds) -> + T = type(Op, Args, Ts, Ds), + Ts#{Dst=>T}. + +type(phi, Args, Ts, _Ds) -> + Types = [get_type(A, Ts) || {A,_} <- Args], + join(Types); +type({bif,'=:='}, [Same,Same], _Ts, _Ds) -> + t_atom(true); +type({bif,'=:='}, [_,_]=Args, Ts, _Ds) -> + case get_literals(Args, Ts) of + [#b_literal{val=Lit1},#b_literal{val=Lit2}] -> + t_atom(Lit1 =:= Lit2); + [_,_] -> + case meet(get_types(Args, Ts)) of + none -> t_atom(false); + _ -> t_boolean() + end + end; +type({bif,tuple_size}, [Src], Ts, _Ds) -> + case t_tuple_size(get_type(Src, Ts)) of + {exact,Size} -> + t_integer(Size); + _ -> + t_integer() + end; +type({bif,'band'}, Args, Ts, _Ds) -> + band_type(Args, Ts); +type({bif,Bif}, [Src]=Args, Ts, _Ds) -> + case get_type(Src, Ts) of + any -> + bif_type(Bif, Args); + Type -> + case will_succeed(Bif, Type) of + yes -> + t_atom(true); + no -> + t_atom(false); + maybe -> + bif_type(Bif, Args) + end + end; +type({bif,Bif}, Args, Ts, _Ds) -> + case bif_type(Bif, Args) of + number -> + arith_op_type(Args, Ts); + Type -> + Type + end; +type(bs_init, [#b_literal{val=Type}|Args], _Ts, _Ds) -> + case {Type,Args} of + {new,[_,#b_literal{val=Unit}]} -> + {binary,Unit}; + {append,[_,_,#b_literal{val=Unit}]} -> + {binary,Unit}; + {private_append,[_,_,#b_literal{val=Unit}]} -> + {binary,Unit} + end; +type(bs_extract, [Ctx], Ts, _Ds) -> + #t_bs_match{type=Type} = get_type(Ctx, Ts), + Type; +type(bs_match, Args, _Ts, _Ds) -> + #t_bs_match{type=bs_match_type(Args)}; +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,_]} -> + 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_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}; + {_,_} -> + #t_tuple{} + end; + {math,_,_} -> + case is_math_bif(Name, length(Args)) of + false -> any; + true -> float + end; + {_,_,_} -> + case erl_bifs:is_exit_bif(Mod, Name, length(Args)) of + true -> none; + false -> any + end + end; +type(get_tuple_element, [Tuple,#b_literal{val=0}], Ts, _Ds) -> + case get_type(Tuple, Ts) of + #t_tuple{elements=[First]} -> + get_type(#b_literal{val=First}, Ts); + #t_tuple{} -> + any + end; +type(is_nonempty_list, [Src], Ts, _Ds) -> + case get_type(Src, Ts) of + any -> + t_boolean(); + list -> + t_boolean(); + cons -> + t_atom(true); + _ -> + t_atom(false) + end; +type(is_tagged_tuple, [Src,#b_literal{val=Size},#b_literal{val=Tag}], Ts, _Ds) -> + case get_type(Src, Ts) of + #t_tuple{exact=true,size=Size,elements=[Tag]} -> + t_atom(true); + #t_tuple{exact=true,size=ActualSize,elements=[]} -> + if + Size =/= ActualSize -> + t_atom(false); + true -> + t_boolean() + end; + #t_tuple{exact=false} -> + t_boolean(); + any -> + t_boolean(); + _ -> + t_atom(false) + end; +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(succeeded, [#b_var{name=Src}], Ts, Ds) -> + case maps:get(Src, Ds) of + #b_set{op={bif,Bif},args=BifArgs} -> + Types = get_types(BifArgs, Ts), + case {Bif,Types} of + {byte_size,[{binary,_}]} -> + t_atom(true); + {bit_size,[{binary,_}]} -> + t_atom(true); + {map_size,[map]} -> + t_atom(true); + {'not',[Type]} -> + case t_is_boolean(Type) of + true -> t_atom(true); + false -> t_boolean() + end; + {size,[{binary,_}]} -> + t_atom(true); + {tuple_size,[#t_tuple{}]} -> + t_atom(true); + {_,_} -> + t_boolean() + end; + #b_set{op=get_hd} -> + t_atom(true); + #b_set{op=get_tl} -> + t_atom(true); + #b_set{op=get_tuple_element} -> + t_atom(true); + #b_set{op=wait} -> + t_atom(false); + #b_set{} -> + t_boolean() + end; +type(_, _, _, _) -> any. + +arith_op_type(Args, Ts) -> + Types = get_types(Args, Ts), + foldl(fun(#t_integer{}, unknown) -> t_integer(); + (#t_integer{}, number) -> number; + (#t_integer{}, float) -> float; + (#t_integer{}, #t_integer{}) -> t_integer(); + (float, unknown) -> float; + (float, #t_integer{}) -> float; + (float, number) -> float; + (number, unknown) -> number; + (number, #t_integer{}) -> number; + (number, float) -> float; + (any, _) -> number; + (_, any) -> number; + (Same, Same) -> Same; + (_, _) -> none + end, unknown, Types). + +%% will_succeed(TestOperation, Type) -> yes|no|maybe. +%% Test whether TestOperation applied to an argument of type Type +%% will succeed. Return yes, no, or maybe. +%% +%% Type is a type as described in the comment for verified_type/1 at +%% the very end of this file, but it will *never* be 'any'. + +will_succeed(is_atom, Type) -> + case Type of + #t_atom{} -> yes; + _ -> no + end; +will_succeed(is_binary, Type) -> + case Type of + {binary,U} when U rem 8 =:= 0 -> yes; + {binary,_} -> maybe; + _ -> no + end; +will_succeed(is_bitstring, Type) -> + case Type of + {binary,_} -> yes; + _ -> no + end; +will_succeed(is_boolean, Type) -> + case Type of + #t_atom{elements=any} -> + maybe; + #t_atom{elements=Es} -> + case t_is_boolean(Type) of + true -> + yes; + false -> + case any(fun is_boolean/1, Es) of + true -> maybe; + false -> no + end + end; + _ -> + no + end; +will_succeed(is_float, Type) -> + case Type of + float -> yes; + number -> maybe; + _ -> no + end; +will_succeed(is_integer, Type) -> + case Type of + #t_integer{} -> yes; + number -> maybe; + _ -> no + end; +will_succeed(is_list, Type) -> + case Type of + list -> yes; + cons -> yes; + nil -> yes; + _ -> no + end; +will_succeed(is_map, Type) -> + case Type of + map -> yes; + _ -> no + end; +will_succeed(is_number, Type) -> + case Type of + float -> yes; + #t_integer{} -> yes; + number -> yes; + _ -> no + end; +will_succeed(is_tuple, Type) -> + case Type of + #t_tuple{} -> yes; + _ -> no + end; +will_succeed(_, _) -> maybe. + + +band_type([#b_literal{val=Int},Other], Ts) when is_integer(Int) -> + band_type_1(Int, Other, Ts); +band_type([Other,#b_literal{val=Int}], Ts) when is_integer(Int) -> + band_type_1(Int, Other, Ts); +band_type([_,_], _) -> t_integer(). + +band_type_1(Int, OtherSrc, Ts) -> + Type = band_type_2(Int, 0), + OtherType = get_type(OtherSrc, Ts), + meet(Type, OtherType). + +band_type_2(N, Bits) when Bits < 64 -> + case 1 bsl Bits of + P when P =:= N + 1 -> + t_integer(0, N); + P when P > N + 1 -> + t_integer(); + _ -> + band_type_2(N, Bits+1) + end; +band_type_2(_, _) -> + %% Negative or large positive number. Give up. + t_integer(). + +bs_match_type([#b_literal{val=Type}|Args]) -> + bs_match_type(Type, Args). + +bs_match_type(binary, Args) -> + [_,_,_,#b_literal{val=U}] = Args, + {binary,U}; +bs_match_type(float, _) -> + float; +bs_match_type(integer, Args) -> + case Args of + [_, + #b_literal{val=Flags}, + #b_literal{val=Size}, + #b_literal{val=Unit}] when Size * Unit < 64 -> + NumBits = Size * Unit, + case member(unsigned, Flags) of + true -> + t_integer(0, (1 bsl NumBits)-1); + false -> + %% Signed integer. Don't bother. + t_integer() + end; + [_|_] -> + t_integer() + end; +bs_match_type(skip, _) -> + any; +bs_match_type(string, _) -> + any; +bs_match_type(utf8, _) -> + ?UNICODE_INT; +bs_match_type(utf16, _) -> + ?UNICODE_INT; +bs_match_type(utf32, _) -> + ?UNICODE_INT. + +simplify_switch_int(#b_switch{list=List0}=Sw, {Min,Max}) -> + List1 = sort(List0), + Vs = [V || {#b_literal{val=V},_} <- List1], + case eq_ranges(Vs, Min, Max) of + true -> + {_,LastL} = last(List1), + List = droplast(List1), + Sw#b_switch{fail=LastL,list=List}; + false -> + Sw + end. + +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_not(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}=Br, Ts, Ds) -> + case Ds of + #{V:=#b_set{op={bif,'not'},args=[Bool]}} -> + case t_is_boolean(get_type(Bool, Ts)) of + true -> + Br#b_br{bool=Bool,succ=Fail,fail=Succ}; + false -> + Br + end; + #{} -> + Br + end. + +get_literals(Values, Ts) -> + [get_literal_from_type(get_type(Val, Ts)) || Val <- Values]. + +get_types(Values, Ts) -> + [get_type(Val, Ts) || Val <- Values]. + +-spec get_type(beam_ssa:value(), type_db()) -> type(). + +get_type(#b_var{name=V}, Ts) -> + #{V:=T} = Ts, + T; +get_type(#b_literal{val=Val}, _Ts) -> + if + is_atom(Val) -> + t_atom(Val); + is_float(Val) -> + float; + is_integer(Val) -> + t_integer(Val); + is_list(Val), Val =/= [] -> + cons; + is_map(Val) -> + map; + Val =:= {} -> + #t_tuple{exact=true}; + is_tuple(Val) -> + #t_tuple{exact=true,size=tuple_size(Val), + elements=[element(1, Val)]}; + Val =:= [] -> + nil; + true -> + any + end. + +infer_types(V, Ts, #d{ds=Ds}) -> + #{V:=#b_set{op=Op,args=Args}} = Ds, + Types = infer_type(Op, Args, Ds), + meet_types(Types, Ts). + +infer_type({bif,element}, [#b_literal{val=Pos},#b_var{name=Tuple}], _Ds) -> + if + is_integer(Pos), 1 =< Pos -> + [{Tuple,#t_tuple{size=Pos}}]; + true -> + [] + end; +infer_type({bif,'=:='}, [#b_var{name=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{name=Src}]=Args, _Ds) -> + case inferred_bif_type(Bif, Args) of + any -> []; + T -> [{Src,T}] + end; +infer_type({bif,is_map_key}, [_,#b_var{name=Src}], _Ds) -> + [{Src,map}]; +infer_type({bif,map_get}, [_,#b_var{name=Src}], _Ds) -> + [{Src,map}]; +infer_type(bs_start_match, [#b_var{name=Bin}], _Ds) -> + [{Bin,{binary,1}}]; +infer_type(is_nonempty_list, [#b_var{name=Src}], _Ds) -> + [{Src,cons}]; +infer_type(is_tagged_tuple, [#b_var{name=Src},#b_literal{val=Size}, + #b_literal{val=Tag}], _Ds) -> + [{Src,#t_tuple{exact=true,size=Size,elements=[Tag]}}]; +infer_type(succeeded, [#b_var{name=Src}], Ds) -> + #b_set{op=Op,args=Args} = maps:get(Src, Ds), + infer_type(Op, Args, Ds); +infer_type(_Op, _Args, _Ds) -> + []. + +%% bif_type(Name, Args) -> Type +%% Return the return type for the guard BIF or operator Name with +%% arguments Args. +%% +%% Note that that the following BIFs are handle elsewhere: +%% +%% band/2 +%% tuple_size/1 + +bif_type(abs, [_]) -> number; +bif_type(bit_size, [_]) -> t_integer(); +bif_type(byte_size, [_]) -> t_integer(); +bif_type(ceil, [_]) -> t_integer(); +bif_type(float, [_]) -> float; +bif_type(floor, [_]) -> t_integer(); +bif_type(is_map_key, [_,_]) -> t_boolean(); +bif_type(length, [_]) -> t_integer(); +bif_type(map_size, [_]) -> t_integer(); +bif_type(round, [_]) -> t_integer(); +bif_type(size, [_]) -> t_integer(); +bif_type(trunc, [_]) -> t_integer(); +bif_type('bnot', [_]) -> t_integer(); +bif_type('bor', [_,_]) -> t_integer(); +bif_type('bsl', [_,_]) -> t_integer(); +bif_type('bsr', [_,_]) -> t_integer(); +bif_type('bxor', [_,_]) -> t_integer(); +bif_type('div', [_,_]) -> t_integer(); +bif_type('rem', [_,_]) -> t_integer(); +bif_type('/', [_,_]) -> float; +bif_type(Name, Args) -> + Arity = length(Args), + case erl_internal:new_type_test(Name, Arity) orelse + erl_internal:bool_op(Name, Arity) orelse + erl_internal:comp_op(Name, Arity) of + true -> + t_boolean(); + false -> + case erl_internal:arith_op(Name, Arity) of + true -> number; + false -> any + end + end. + +inferred_bif_type(is_atom, [_]) -> t_atom(); +inferred_bif_type(is_binary, [_]) -> {binary,8}; +inferred_bif_type(is_bitstring, [_]) -> {binary,1}; +inferred_bif_type(is_boolean, [_]) -> t_boolean(); +inferred_bif_type(is_float, [_]) -> float; +inferred_bif_type(is_integer, [_]) -> t_integer(); +inferred_bif_type(is_list, [_]) -> list; +inferred_bif_type(is_map, [_]) -> map; +inferred_bif_type(is_number, [_]) -> number; +inferred_bif_type(is_tuple, [_]) -> #t_tuple{}; +inferred_bif_type(abs, [_]) -> number; +inferred_bif_type(bit_size, [_]) -> {binary,1}; +inferred_bif_type(byte_size, [_]) -> {binary,1}; +inferred_bif_type(ceil, [_]) -> number; +inferred_bif_type(float, [_]) -> number; +inferred_bif_type(floor, [_]) -> number; +inferred_bif_type(round, [_]) -> number; +inferred_bif_type(trunc, [_]) -> number; +inferred_bif_type(tuple_size, [_]) -> #t_tuple{}; +inferred_bif_type(_, _) -> any. + +infer_tuple_size(#b_set{op={bif,tuple_size},args=[#b_var{name=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{name=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; +is_math_bif(sinh, 1) -> true; +is_math_bif(tan, 1) -> true; +is_math_bif(tanh, 1) -> true; +is_math_bif(acos, 1) -> true; +is_math_bif(acosh, 1) -> true; +is_math_bif(asin, 1) -> true; +is_math_bif(asinh, 1) -> true; +is_math_bif(atan, 1) -> true; +is_math_bif(atanh, 1) -> true; +is_math_bif(erf, 1) -> true; +is_math_bif(erfc, 1) -> true; +is_math_bif(exp, 1) -> true; +is_math_bif(log, 1) -> true; +is_math_bif(log2, 1) -> true; +is_math_bif(log10, 1) -> true; +is_math_bif(sqrt, 1) -> true; +is_math_bif(atan2, 2) -> true; +is_math_bif(pow, 2) -> true; +is_math_bif(ceil, 1) -> true; +is_math_bif(floor, 1) -> true; +is_math_bif(fmod, 2) -> true; +is_math_bif(pi, 0) -> true; +is_math_bif(_, _) -> false. + +join_types(Ts0, Ts1) -> + if + map_size(Ts0) < map_size(Ts1) -> + join_types_1(maps:keys(Ts0), Ts1, Ts0); + true -> + join_types_1(maps:keys(Ts1), Ts0, Ts1) + end. + +join_types_1([V|Vs], Ts0, Ts1) -> + case {Ts0,Ts1} of + {#{V:=Same},#{V:=Same}} -> + join_types_1(Vs, Ts0, Ts1); + {#{V:=T0},#{V:=T1}} -> + case join(T0, T1) of + T1 -> + join_types_1(Vs, Ts0, Ts1); + T -> + join_types_1(Vs, Ts0, Ts1#{V:=T}) + end; + {#{},#{V:=_}} -> + join_types_1(Vs, Ts0, Ts1) + end; +join_types_1([], Ts0, Ts1) -> + maps:merge(Ts0, Ts1). + +join([T1,T2|Ts]) -> + join([join(T1, T2)|Ts]); +join([T]) -> T. + +get_literal_from_type(#t_atom{elements=[Atom]}) -> + #b_literal{val=Atom}; +get_literal_from_type(#t_integer{elements={Int,Int}}) -> + #b_literal{val=Int}; +get_literal_from_type(nil) -> + #b_literal{val=[]}; +get_literal_from_type(_) -> none. + +t_atom() -> + #t_atom{elements=any}. + +t_atom(Atom) when is_atom(Atom) -> + #t_atom{elements=[Atom]}. + +t_boolean() -> + #t_atom{elements=[false,true]}. + +t_integer() -> + #t_integer{elements=any}. + +t_integer(Int) when is_integer(Int) -> + #t_integer{elements={Int,Int}}. + +t_integer(Min, Max) when is_integer(Min), is_integer(Max) -> + #t_integer{elements={Min,Max}}. + +t_is_boolean(#t_atom{elements=[F,T]}) -> + F =:= false andalso T =:= true; +t_is_boolean(#t_atom{elements=[B]}) -> + is_boolean(B); +t_is_boolean(_) -> false. + +t_tuple_size(#t_tuple{size=Size,exact=false}) -> + {at_least,Size}; +t_tuple_size(#t_tuple{size=Size,exact=true}) -> + {exact,Size}; +t_tuple_size(_) -> + none. + +%% join(Type1, Type2) -> Type +%% Return the "join" of Type1 and Type2. The join is a more general +%% type than Type1 and Type2. For example: +%% +%% join(#t_integer{elements=any}, #t_integer=elements={0,3}}) -> +%% #t_integer{} +%% +%% The join for two different types result in 'any', which is +%% the top element for our type lattice: +%% +%% join(#t_integer{}, map) -> any + +-spec join(type(), type()) -> type(). + +join(T, T) -> + verified_type(T); +join(none, T) -> + verified_type(T); +join(T, none) -> + verified_type(T); +join(any, _) -> any; +join(_, any) -> any; +join(#t_atom{elements=[_|_]=Set1}, #t_atom{elements=[_|_]=Set2}) -> + Set = ordsets:union(Set1, Set2), + case ordsets:size(Set) of + Size when Size =< ?ATOM_SET_SIZE -> + #t_atom{elements=Set}; + _Size -> + #t_atom{elements=any} + end; +join(#t_atom{elements=any}=T, #t_atom{elements=[_|_]}) -> T; +join(#t_atom{elements=[_|_]}, #t_atom{elements=any}=T) -> T; +join({binary,U1}, {binary,U2}) -> + {binary,gcd(U1, U2)}; +join(#t_integer{}, #t_integer{}) -> t_integer(); +join(list, cons) -> list; +join(cons, list) -> list; +join(nil, cons) -> list; +join(cons, nil) -> list; +join(nil, list) -> list; +join(list, nil) -> list; +join(#t_integer{}, float) -> number; +join(float, #t_integer{}) -> number; +join(#t_integer{}, number) -> number; +join(number, #t_integer{}) -> number; +join(float, number) -> number; +join(number, float) -> number; +join(#t_tuple{size=Sz,exact=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(_T1, _T2) -> + %%io:format("~p ~p\n", [_T1,_T2]), + any. + +gcd(A, B) -> + case A rem B of + 0 -> B; + X -> gcd(B, X) + end. + +meet_types([{V,T0}|Vs], Ts) -> + #{V:=T1} = Ts, + T = meet(T0, T1), + meet_types(Vs, Ts#{V:=T}); +meet_types([], Ts) -> Ts. + +meet([T1,T2|Ts]) -> + meet([meet(T1, T2)|Ts]); +meet([T]) -> T. + +%% meet(Type1, Type2) -> Type +%% Return the "meet" of Type1 and Type2. The meet is a narrower +%% type than Type1 and Type2. For example: +%% +%% meet(#t_integer{elements=any}, #t_integer{elements={0,3}}) -> +%% #t_integer{elements={0,3}} +%% +%% The meet for two different types result in 'none', which is +%% the bottom element for our type lattice: +%% +%% meet(#t_integer{}, map) -> none + +-spec meet(type(), type()) -> type(). + +meet(T, T) -> + verified_type(T); +meet(#t_atom{elements=[_|_]=Set1}, #t_atom{elements=[_|_]=Set2}) -> + case ordsets:intersection(Set1, Set2) of + [] -> + none; + [_|_]=Set -> + #t_atom{elements=Set} + end; +meet(#t_atom{elements=[_|_]}=T, #t_atom{elements=any}) -> + T; +meet(#t_atom{elements=any}, #t_atom{elements=[_|_]}=T) -> + T; +meet(#t_integer{elements={_,_}}=T, #t_integer{elements=any}) -> + T; +meet(#t_integer{elements=any}, #t_integer{elements={_,_}}=T) -> + T; +meet(#t_integer{elements={Min1,Max1}}, + #t_integer{elements={Min2,Max2}}) -> + #t_integer{elements={max(Min1, Min2),min(Max1, Max2)}}; +meet(#t_integer{}=T, number) -> T; +meet(float, number) -> float; +meet(#t_integer{}=T, number) -> T; +meet(float, number) -> float; +meet(number, #t_integer{}=T) -> T; +meet(#t_integer{}=T, number) -> T; +meet(number, float=T) -> T; +meet(float=T, number) -> T; +meet(list, cons) -> cons; +meet(list, nil) -> nil; +meet(cons, list) -> cons; +meet(nil, list) -> nil; +meet(#t_tuple{}=T1, #t_tuple{}=T2) -> + meet_tuples(T1, T2); +meet({binary,U1}, {binary,U2}) -> + {binary,max(U1, U2)}; +meet(any, T) -> + verified_type(T); +meet(T, any) -> + verified_type(T); +meet(_, _) -> + %% Inconsistent types. There will be an exception at runtime. + none. + +meet_tuples(#t_tuple{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; +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}. + +%% verified_type(Type) -> Type +%% Returns the passed in type if it is one of the defined types. +%% Crashes if there is anything wrong with the type. +%% +%% Here are all possible types: +%% +%% any Any Erlang term (top element for the type lattice). +%% +%% #t_atom{} Any atom or some specific atoms. +%% {binary,Unit} Binary/bitstring aligned to unit Unit. +%% float Floating point number. +%% #t_integer{} Integer +%% list Empty or nonempty list. +%% map Map. +%% nil Empty list. +%% cons Cons (nonempty list). +%% number A number (float or integer). +%% #t_tuple{} Tuple. +%% +%% none No type (bottom element for the type lattice). + +-spec verified_type(T) -> T when + T :: type(). + +verified_type(any=T) -> T; +verified_type(none=T) -> T; +verified_type(#t_atom{elements=any}=T) -> T; +verified_type(#t_atom{elements=[_|_]}=T) -> T; +verified_type({binary,U}=T) when is_integer(U) -> T; +verified_type(#t_integer{elements=any}=T) -> T; +verified_type(#t_integer{elements={Min,Max}}=T) + when is_integer(Min), is_integer(Max) -> T; +verified_type(list=T) -> T; +verified_type(map=T) -> T; +verified_type(nil=T) -> T; +verified_type(cons=T) -> T; +verified_type(number=T) -> T; +verified_type(#t_tuple{}=T) -> T; +verified_type(float=T) -> T. |