From 846444c5add9ad08340d585096c94a7b6f5b5933 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Thu, 14 Nov 2019 10:01:05 +0100 Subject: compiler: Keep track of 'fun' return types --- erts/emulator/test/process_SUITE.erl | 9 +- lib/compiler/src/beam_call_types.erl | 123 +++++++++++++-- lib/compiler/src/beam_ssa_codegen.erl | 23 ++- lib/compiler/src/beam_ssa_type.erl | 170 +++++++++++++-------- lib/compiler/src/beam_types.erl | 33 ++-- lib/compiler/src/beam_types.hrl | 3 +- lib/compiler/src/beam_validator.erl | 31 ++-- .../test/property_test/beam_types_prop.erl | 12 +- 8 files changed, 297 insertions(+), 107 deletions(-) diff --git a/erts/emulator/test/process_SUITE.erl b/erts/emulator/test/process_SUITE.erl index 13dde12e69..1a222be9f5 100644 --- a/erts/emulator/test/process_SUITE.erl +++ b/erts/emulator/test/process_SUITE.erl @@ -2248,7 +2248,7 @@ max_heap_size_test(Option, Size, Kill, ErrorLogger) when is_map(Option); is_integer(Option) -> max_heap_size_test([{max_heap_size, Option}], Size, Kill, ErrorLogger); max_heap_size_test(Option, Size, Kill, ErrorLogger) -> - OomFun = fun F() -> timer:sleep(5),[lists:seq(1,1000)|F()] end, + OomFun = fun () -> oom_fun([]) end, Pid = spawn_opt(OomFun, Option), {max_heap_size, MHSz} = erlang:process_info(Pid, max_heap_size), ct:log("Default: ~p~nOption: ~p~nProc: ~p~n", @@ -2291,6 +2291,13 @@ max_heap_size_test(Option, Size, Kill, ErrorLogger) -> %% Make sure that there are no unexpected messages. receive_unexpected(). +oom_fun(Acc0) -> + %% This is tail-recursive since the compiler is smart enough to figure + %% out that a body-recursive variant never returns, and loops forever + %% without keeping the list alive. + timer:sleep(5), + oom_fun([lists:seq(1, 1000) | Acc0]). + receive_error_messages(Pid) -> receive {error, _, {emulator, _, [Pid|_]}} -> diff --git a/lib/compiler/src/beam_call_types.erl b/lib/compiler/src/beam_call_types.erl index 3d5f7ca0d1..457d2c274a 100644 --- a/lib/compiler/src/beam_call_types.erl +++ b/lib/compiler/src/beam_call_types.erl @@ -444,6 +444,14 @@ types(lists, suffix, [_,_]) -> %% so we can't tell if either is proper. sub_unsafe(beam_types:make_boolean(), [#t_list{}, #t_list{}]); +%% Simple folds +types(lists, foldl, [Fun, Init, List]) -> + RetType = lists_fold_type(Fun, Init, List), + sub_unsafe(RetType, [#t_fun{arity=2}, any, proper_list()]); +types(lists, foldr, [Fun, Init, List]) -> + RetType = lists_fold_type(Fun, Init, List), + sub_unsafe(RetType, [#t_fun{arity=2}, any, proper_list()]); + %% Functions returning plain lists. types(lists, droplast, [List]) -> RetType = copy_list(List, new_length, proper), @@ -460,8 +468,9 @@ types(lists, filter, [_Fun, List]) -> sub_unsafe(RetType, [#t_fun{arity=1}, proper_list()]); types(lists, flatten, [_]) -> sub_unsafe(proper_list(), [proper_list()]); -types(lists, map, [_Fun, _List]) -> - sub_unsafe(#t_list{}, [#t_fun{arity=1}, proper_list()]); +types(lists, map, [Fun, List]) -> + RetType = lists_map_type(Fun, List), + sub_unsafe(RetType, [#t_fun{arity=1}, proper_list()]); types(lists, reverse, [List]) -> RetType = copy_list(List, same_length, proper), sub_unsafe(RetType, [proper_list()]); @@ -497,9 +506,9 @@ types(lists, keyfind, [KeyType,PosType,_]) -> end, RetType = beam_types:join(TupleType, beam_types:make_atom(false)), sub_unsafe(RetType, [any, #t_integer{}, #t_list{}]); -types(lists, MapFold, [_Fun, _Init, _List]) +types(lists, MapFold, [Fun, Init, List]) when MapFold =:= mapfoldl; MapFold =:= mapfoldr -> - RetType = make_two_tuple(#t_list{}, any), + RetType = lists_mapfold_type(Fun, Init, List), sub_unsafe(RetType, [#t_fun{arity=2}, any, proper_list()]); types(lists, partition, [_Fun, List]) -> ListType = copy_list(List, new_length, proper), @@ -520,6 +529,21 @@ types(lists, unzip, [List]) -> RetType = lists_unzip_type(2, List), sub_unsafe(RetType, [proper_list()]); +%% +%% Map functions +%% + +types(maps, fold, [Fun, Init, _Map]) -> + RetType = case Fun of + #t_fun{type=Type} -> + %% The map is potentially empty, so we have to assume it + %% can return the initial value. + beam_types:join(Type, Init); + _ -> + any + end, + sub_unsafe(RetType, [#t_fun{arity=3}, any, #t_map{}]); + %% Catch-all clause for unknown functions. types(_, _, Args) -> @@ -587,6 +611,64 @@ range_masks_1(_From, To, _BitPos, Intersection0, Union0) -> Union = To bor Union0, {Intersection, Union}. +lists_fold_type(_Fun, Init, nil) -> + Init; +lists_fold_type(#t_fun{type=Type}, _Init, #t_cons{}) -> + %% The list is non-empty so it's safe to ignore Init. + Type; +lists_fold_type(#t_fun{type=Type}, Init, #t_list{}) -> + %% The list is possibly empty so we have to assume it can return the + %% initial value, whose type can differ significantly from the fun's + %% return value. + beam_types:join(Type, Init); +lists_fold_type(_Fun, _Init, _List) -> + any. + +lists_map_type(#t_fun{type=Type}, Types) -> + lists_map_type_1(Types, Type); +lists_map_type(_Fun, Types) -> + lists_map_type_1(Types, any). + +lists_map_type_1(nil, _ElementType) -> + nil; +lists_map_type_1(#t_cons{}, none) -> + %% The list is non-empty and the fun never returns. + none; +lists_map_type_1(#t_cons{}, ElementType) -> + proper_cons(ElementType); +lists_map_type_1(_, none) -> + %% The fun never returns, so the only way we could return normally is + %% if the list is empty. + nil; +lists_map_type_1(_, ElementType) -> + proper_list(ElementType). + +lists_mapfold_type(#t_fun{type=#t_tuple{size=2,elements=Es}}, Init, List) -> + ElementType = beam_types:get_tuple_element(1, Es), + AccType = beam_types:get_tuple_element(2, Es), + lists_mapfold_type_1(List, ElementType, Init, AccType); +lists_mapfold_type(#t_fun{type=none}, _Init, #t_cons{}) -> + %% The list is non-empty and the fun never returns. + none; +lists_mapfold_type(#t_fun{type=none}, Init, _List) -> + %% The fun never returns, so the only way we could return normally is + %% if the list is empty, in which case we'll return [] and the initial + %% value. + make_two_tuple(nil, Init); +lists_mapfold_type(_Fun, Init, List) -> + lists_mapfold_type_1(List, any, Init, any). + +lists_mapfold_type_1(nil, _ElementType, Init, _AccType) -> + make_two_tuple(nil, Init); +lists_mapfold_type_1(#t_cons{}, ElementType, _Init, AccType) -> + %% The list has at least one element, so it's safe to ignore Init. + make_two_tuple(proper_cons(ElementType), AccType); +lists_mapfold_type_1(_, ElementType, Init, AccType0) -> + %% We can only rely on AccType when we know the list is non-empty, so we + %% have to join it with the initial value in case the list is empty. + AccType = beam_types:join(AccType0, Init), + make_two_tuple(proper_list(ElementType), AccType). + lists_unzip_type(Size, List) -> Es = lut_make_elements(lut_list_types(Size, List), 1, #{}), #t_tuple{size=Size,exact=true,elements=Es}. @@ -646,20 +728,33 @@ lists_zip_types_1([], false, Es, N) -> ArgType = proper_list(), {RetType, ArgType}. +lists_zipwith_types(#t_fun{type=Type}, Types) -> + lists_zipwith_type_1(Types, Type); lists_zipwith_types(_Fun, Types) -> - ListType = lists_zipwith_type_1(Types), - {ListType, ListType}. + lists_zipwith_type_1(Types, any). -lists_zipwith_type_1([nil | _]) -> +lists_zipwith_type_1([nil | _], _ElementType) -> %% Early exit; we know the result is [] on success. - nil; -lists_zipwith_type_1([#t_cons{} | _Lists]) -> + {nil, nil}; +lists_zipwith_type_1([#t_cons{} | _Lists], none) -> + %% Early exit; the list is non-empty and we know the fun never + %% returns. + {none, any}; +lists_zipwith_type_1([#t_cons{} | _Lists], ElementType) -> %% Early exit; we know the result is cons on success. - proper_cons(); -lists_zipwith_type_1([_ | Lists]) -> - lists_zipwith_type_1(Lists); -lists_zipwith_type_1([]) -> - proper_list(). + RetType = proper_cons(ElementType), + ArgType = proper_cons(), + {RetType, ArgType}; +lists_zipwith_type_1([_ | Lists], ElementType) -> + lists_zipwith_type_1(Lists, ElementType); +lists_zipwith_type_1([], none) -> + %% Since we know the fun won't return, the only way we could return + %% normally is if all lists are empty. + {nil, nil}; +lists_zipwith_type_1([], ElementType) -> + RetType = proper_list(ElementType), + ArgType = proper_list(), + {RetType, ArgType}. %%% %%% Generic helpers diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl index 0653b3100b..fbb838fbd2 100644 --- a/lib/compiler/src/beam_ssa_codegen.erl +++ b/lib/compiler/src/beam_ssa_codegen.erl @@ -1237,15 +1237,24 @@ cg_block([#cg_set{op=call}=Call|T], Context, St0) -> {Is0,St1} = cg_call(Call, body, none, St0), {Is1,St} = cg_block(T, Context, St1), {Is0++Is1,St}; -cg_block([#cg_set{op=make_fun,dst=Dst0,args=[Local|Args0]}|T], +cg_block([#cg_set{anno=Anno,op=make_fun,dst=Dst0,args=[Local|Args0]}|T], Context, St0) -> #b_local{name=#b_literal{val=Func},arity=Arity} = Local, [Dst|Args] = beam_args([Dst0|Args0], St0), {FuncLbl,St1} = local_func_label(Func, Arity, St0), Is0 = setup_args(Args) ++ [{make_fun2,{f,FuncLbl},0,0,length(Args)}|copy({x,0}, Dst)], - {Is1,St} = cg_block(T, Context, St1), - {Is0++Is1,St}; + + Is1 = case Anno of + #{ result_type := Type } -> + Info = {var_info, Dst, [{fun_type, Type}]}, + Is0 ++ [{'%', Info}]; + #{} -> + Is0 + end, + + {Is2,St} = cg_block(T, Context, St1), + {Is1++Is2,St}; cg_block([#cg_set{op=copy}|_]=T0, Context, St0) -> {Is0,T} = cg_copy(T0, St0), {Is1,St} = cg_block(T, Context, St0), @@ -1549,7 +1558,13 @@ cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=Args0}, Arity = length(Args), Call = build_call(call_fun, Arity, Func, Context, Dst), Is = setup_args(Args++[Func], Anno, Context, St) ++ Line ++ Call, - {Is,St}. + case Anno of + #{ result_type := Type } -> + Info = {var_info, Dst, [{type,Type}]}, + {Is ++ [{'%', Info}], St}; + #{} -> + {Is, St} + end. cg_match_fail([{atom,function_clause}|Args], Line, Fc) -> case Fc of diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index b4def4e859..e7ba89aff8 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -234,7 +234,24 @@ sig_is([#b_set{op=call, Args = simplify_args(Args0, Ts0, Sub), I1 = beam_ssa:normalize(I0#b_set{args=Args}), - {I, State} = sig_local_call(I1, Callee, tl(Args), Ts0, Fdb, State0), + [_ | CallArgs] = Args, + {I, State} = sig_local_call(I1, Callee, CallArgs, Ts0, Fdb, State0), + + Ts = update_types(I, Ts0, Ds0), + Ds = Ds0#{ Dst => I }, + sig_is(Is, Ts, Ds, Ls, Fdb, Sub, State); +sig_is([#b_set{op=call, + args=[#b_var{} | _]=Args0, + dst=Dst}=I0 | Is], + Ts0, Ds0, Ls, Fdb, Sub, State) -> + Args = simplify_args(Args0, Ts0, Sub), + I1 = beam_ssa:normalize(I0#b_set{args=Args}), + + [Fun | _] = Args, + I = case normalized_type(Fun, Ts0) of + #t_fun{type=Type} -> beam_ssa:add_anno(result_type, Type, I1); + _ -> I1 + end, Ts = update_types(I, Ts0, Ds0), Ds = Ds0#{ Dst => I }, @@ -260,31 +277,30 @@ sig_is([], Ts, Ds, _Ls, _Fdb, Sub, State) -> {Ts, Ds, Sub, State}. sig_local_call(I0, Callee, Args, Ts, Fdb, State) -> - I = sig_local_return(I0, Callee, Args, Fdb, Ts), ArgTypes = argument_types(Args, Ts), + I = sig_local_return(I0, Callee, ArgTypes, Fdb), {I, sig_update_args(Callee, ArgTypes, State)}. -sig_local_return(I, Callee, Args, Fdb, Ts) -> - #func_info{succ_types=SuccTypes} = map_get(Callee, Fdb), - - ArgTypes = argument_types(Args, Ts), - case return_type(SuccTypes, ArgTypes) of - any -> I; - Type -> beam_ssa:add_anno(result_type, Type, 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 -%% local call. +%% While it's impossible to tell which arguments a fun will be called with +%% (someone could steal it through tracing and call it), we do know its free +%% variables and can update their types as if this were a local call. sig_make_fun(#b_set{op=make_fun, - args=[#b_local{}=Callee | FreeVars]}=I, - Ts, _Fdb, State) -> + args=[#b_local{}=Callee | FreeVars]}=I0, + Ts, Fdb, State) -> ArgCount = Callee#b_local.arity - length(FreeVars), FVTypes = [raw_type(FreeVar, Ts) || FreeVar <- FreeVars], - CallTypes = duplicate(ArgCount, any) ++ FVTypes, + ArgTypes = duplicate(ArgCount, any) ++ FVTypes, + + I = sig_local_return(I0, Callee, ArgTypes, Fdb), + {I, sig_update_args(Callee, ArgTypes, State)}. - {I, sig_update_args(Callee, CallTypes, State)}. +sig_local_return(I, Callee, ArgTypes, Fdb) -> + #func_info{succ_types=SuccTypes} = map_get(Callee, Fdb), + case return_type(SuccTypes, ArgTypes) of + any -> I; + Type -> beam_ssa:add_anno(result_type, Type, I) + end. init_sig_st(StMap, FuncDb) -> %% Start out as if all the roots have been called with 'any' for all @@ -443,7 +459,24 @@ opt_is([#b_set{op=call, Args = simplify_args(Args0, Ts0, Sub), I1 = beam_ssa:normalize(I0#b_set{args=Args}), - {I, Fdb} = opt_local_call(I1, Callee, tl(Args), Dst, Ts0, Fdb0, Meta), + [_ | CallArgs] = Args, + {I, Fdb} = opt_local_call(I1, Callee, CallArgs, Dst, Ts0, Fdb0, Meta), + + Ts = update_types(I, Ts0, Ds0), + Ds = Ds0#{ Dst => I }, + opt_is(Is, Ts, Ds, Ls, Fdb, Sub, Meta, [I | Acc]); +opt_is([#b_set{op=call, + args=[#b_var{} | _]=Args0, + dst=Dst}=I0 | Is], + Ts0, Ds0, Ls, Fdb, Sub, Meta, Acc) -> + Args = simplify_args(Args0, Ts0, Sub), + I1 = beam_ssa:normalize(I0#b_set{args=Args}), + + [Fun | _] = Args, + I = case normalized_type(Fun, Ts0) of + #t_fun{type=Type} -> beam_ssa:add_anno(result_type, Type, I1); + _ -> I1 + end, Ts = update_types(I, Ts0, Ds0), Ds = Ds0#{ Dst => I }, @@ -468,64 +501,61 @@ opt_is([I0 | Is], Ts0, Ds0, Ls, Fdb, Sub0, Meta, Acc) -> opt_is([], Ts, Ds, _Ls, Fdb, Sub, _Meta, Acc) -> {reverse(Acc), Ts, Ds, Fdb, Sub}. -opt_local_call(I0, Callee, Args, Dst, Ts, Fdb0, Meta) -> - I = opt_local_return(I0, Callee, Args, Fdb0, Ts), - case Fdb0 of - #{ Callee := #func_info{exported=false,arg_types=ArgTypes0}=Info } -> - Types = argument_types(Args, Ts), - +opt_local_call(I0, Callee, Args, Dst, Ts, Fdb, Meta) -> + ArgTypes = argument_types(Args, Ts), + I = opt_local_return(I0, Callee, ArgTypes, Fdb), + case Fdb of + #{ Callee := #func_info{exported=false,arg_types=AT0}=Info0 } -> %% Update the argument types of *this exact call*, the types %% will be joined later when the callee is optimized. CallId = {Meta#metadata.func_id, Dst}, - ArgTypes = update_arg_types(Types, ArgTypes0, CallId), - Fdb = Fdb0#{ Callee => Info#func_info{arg_types=ArgTypes} }, - {I, Fdb}; + AT = update_arg_types(ArgTypes, AT0, CallId), + Info = Info0#func_info{arg_types=AT}, + + {I, Fdb#{ Callee := Info }}; #{} -> %% We can't narrow the argument types of exported functions as they %% can receive anything as part of an external call. We can still %% rely on their return types however. - {I, Fdb0} + {I, Fdb} end. -opt_local_return(I, Callee, Args, Fdb, Ts) when Fdb =/= #{} -> - #func_info{succ_types=SuccTypes} = map_get(Callee, Fdb), - - ArgTypes = argument_types(Args, Ts), - - case return_type(SuccTypes, ArgTypes) of - any -> I; - Type -> beam_ssa:add_anno(result_type, Type, I) - end; -opt_local_return(I, _Callee, _Args, _Fdb, _Ts) -> - %% Module-level optimization is disabled, assume it returns anything. - I. - -%% 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 -%% local call. +%% See sig_make_fun/4 opt_make_fun(#b_set{op=make_fun, dst=Dst, - args=[#b_local{}=Callee | FreeVars]}=I, - Ts, Fdb0, Meta) -> - case Fdb0 of - #{ Callee := #func_info{exported=false,arg_types=ArgTypes0}=Info } -> - ArgCount = Callee#b_local.arity - length(FreeVars), + args=[#b_local{}=Callee | FreeVars]}=I0, + Ts, Fdb, Meta) -> + ArgCount = Callee#b_local.arity - length(FreeVars), + FVTypes = [raw_type(FreeVar, Ts) || FreeVar <- FreeVars], + ArgTypes = duplicate(ArgCount, any) ++ FVTypes, - FVTypes = [raw_type(FreeVar, Ts) || FreeVar <- FreeVars], - Types = duplicate(ArgCount, any) ++ FVTypes, + I = opt_local_return(I0, Callee, ArgTypes, Fdb), + case Fdb of + #{ Callee := #func_info{exported=false,arg_types=AT0}=Info0 } -> CallId = {Meta#metadata.func_id, Dst}, - ArgTypes = update_arg_types(Types, ArgTypes0, CallId), - Fdb = Fdb0#{ Callee => Info#func_info{arg_types=ArgTypes} }, - {I, Fdb}; + AT = update_arg_types(ArgTypes, AT0, CallId), + Info = Info0#func_info{arg_types=AT}, + + {I, Fdb#{ Callee := Info }}; #{} -> %% We can't narrow the argument types of exported functions as they %% can receive anything as part of an external call. - {I, Fdb0} + {I, Fdb} end. +opt_local_return(I, Callee, ArgTypes, Fdb) when Fdb =/= #{} -> + #func_info{succ_types=SuccTypes} = map_get(Callee, Fdb), + case return_type(SuccTypes, ArgTypes) of + any -> I; + Type -> beam_ssa:add_anno(result_type, Type, I) + end; +opt_local_return(I, _Callee, _ArgTyps, _Fdb) -> + %% Module-level optimization is disabled, assume it returns anything. + I. + update_arg_types([ArgType | ArgTypes], [TypeMap0 | TypeMaps], CallId) -> TypeMap = TypeMap0#{ CallId => ArgType }, [TypeMap | update_arg_types(ArgTypes, TypeMaps, CallId)]; @@ -1349,16 +1379,26 @@ type(bs_match, Args, _Anno, Ts, _Ds) -> type(bs_get_tail, [Ctx], _Anno, Ts, _Ds) -> #t_bs_context{tail_unit=Unit} = raw_type(Ctx, Ts), #t_bitstring{size_unit=Unit}; -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], _Anno, Ts, _Ds) -> ArgTypes = normalized_types(Args, Ts), {RetType, _, _} = beam_call_types:types(Mod, Name, ArgTypes), RetType; +type(call, [#b_remote{} | _Args], _Anno, _Ts, _Ds) -> + %% Remote call with variable Module and/or Function. + any; +type(call, [#b_local{} | _Args], Anno, _Ts, _Ds) -> + case Anno of + #{ result_type := Type } -> Type; + #{} -> any + end; +type(call, [#b_var{} | _Args], Anno, _Ts, _Ds) -> + case Anno of + #{ result_type := Type } -> Type; + #{} -> any + end; +type(call, [#b_literal{} | _Args], _Anno, _Ts, _Ds) -> + none; type(get_hd, [Src], _Anno, Ts, _Ds) -> SrcType = #t_cons{} = normalized_type(Src, Ts), {RetType, _, _} = beam_call_types:types(erlang, hd, [SrcType]), @@ -1376,8 +1416,12 @@ type(is_nonempty_list, [_], _Anno, _Ts, _Ds) -> beam_types:make_boolean(); type(is_tagged_tuple, [_,#b_literal{},#b_literal{}], _Anno, _Ts, _Ds) -> beam_types:make_boolean(); -type(make_fun, [#b_local{arity=TotalArity}|Env], _Anno, _Ts, _Ds) -> - #t_fun{arity=TotalArity-length(Env)}; +type(make_fun, [#b_local{arity=TotalArity} | Env], Anno, _Ts, _Ds) -> + RetType = case Anno of + #{ result_type := Type } -> Type; + #{} -> any + end, + #t_fun{arity=TotalArity - length(Env), type=RetType}; type(put_map, _Args, _Anno, _Ts, _Ds) -> #t_map{}; type(put_list, [Head, Tail], _Anno, Ts, _Ds) -> diff --git a/lib/compiler/src/beam_types.erl b/lib/compiler/src/beam_types.erl index 72c0282003..bce5da2983 100644 --- a/lib/compiler/src/beam_types.erl +++ b/lib/compiler/src/beam_types.erl @@ -569,13 +569,23 @@ limit_depth(#t_list{}=T, Depth) -> limit_depth_list(T, Depth); limit_depth(#t_tuple{}=T, Depth) -> limit_depth_tuple(T, Depth); -limit_depth(#t_union{list=List0,tuple_set=TupleSet0}=U, Depth) -> +limit_depth(#t_fun{}=T, Depth) -> + limit_depth_fun(T, Depth); +limit_depth(#t_union{list=List0,tuple_set=TupleSet0,other=Other0}=U, Depth) -> TupleSet = limit_depth_tuple(TupleSet0, Depth), List = limit_depth_list(List0, Depth), - shrink_union(U#t_union{list=List,tuple_set=TupleSet}); + Other = limit_depth(Other0, Depth), + shrink_union(U#t_union{list=List,tuple_set=TupleSet,other=Other}); limit_depth(Type, _Depth) -> Type. +limit_depth_fun(#t_fun{type=Type0}=T, Depth) -> + Type = if + Depth > 0 -> limit_depth(Type0, Depth - 1); + Depth =< 0 -> any + end, + T#t_fun{type=Type}. + limit_depth_list(#t_cons{type=Type0,terminator=Term0}=T, Depth) -> {Type, Term} = limit_depth_list_1(Type0, Term0, Depth), T#t_cons{type=Type,terminator=Term}; @@ -701,10 +711,12 @@ glb(#t_float{elements={MinA,MaxA}}, #t_float{elements={MinB,MaxB}}) MinB >= MinA, MinB =< MaxA -> true = MinA =< MaxA andalso MinB =< MaxB, %Assertion. #t_float{elements={max(MinA, MinB),min(MaxA, MaxB)}}; -glb(#t_fun{arity=any}, #t_fun{}=T) -> - T; -glb(#t_fun{}=T, #t_fun{arity=any}) -> - T; +glb(#t_fun{arity=Same,type=TypeA}, #t_fun{arity=Same,type=TypeB}=T) -> + T#t_fun{type=meet(TypeA, TypeB)}; +glb(#t_fun{arity=any,type=TypeA}, #t_fun{type=TypeB}=T) -> + T#t_fun{type=meet(TypeA, TypeB)}; +glb(#t_fun{type=TypeA}=T, #t_fun{arity=any,type=TypeB}) -> + T#t_fun{type=meet(TypeA, TypeB)}; glb(#t_integer{elements={_,_}}=T, #t_integer{elements=any}) -> T; glb(#t_integer{elements=any}, #t_integer{elements={_,_}}=T) -> @@ -851,8 +863,10 @@ lub(#t_float{}, #t_integer{}) -> number; lub(#t_float{}, number) -> number; -lub(#t_fun{}, #t_fun{}) -> - #t_fun{}; +lub(#t_fun{arity=Same,type=TypeA}, #t_fun{arity=Same,type=TypeB}) -> + #t_fun{arity=Same,type=join(TypeA, TypeB)}; +lub(#t_fun{type=TypeA}, #t_fun{type=TypeB}) -> + #t_fun{type=join(TypeA, TypeB)}; lub(#t_integer{elements={MinA,MaxA}}, #t_integer{elements={MinB,MaxB}}) -> #t_integer{elements={min(MinA,MinB),max(MaxA,MaxB)}}; @@ -1013,8 +1027,9 @@ verified_normal_type(#t_cons{type=Type,terminator=Term}=T) -> _ = verified_type(Type), _ = verified_type(Term), T; -verified_normal_type(#t_fun{arity=Arity}=T) +verified_normal_type(#t_fun{arity=Arity,type=ReturnType}=T) when Arity =:= any; is_integer(Arity) -> + _ = verified_type(ReturnType), T; verified_normal_type(#t_float{}=T) -> T; verified_normal_type(#t_integer{elements=any}=T) -> T; diff --git a/lib/compiler/src/beam_types.hrl b/lib/compiler/src/beam_types.hrl index dc05aa45b8..507ad859f0 100644 --- a/lib/compiler/src/beam_types.hrl +++ b/lib/compiler/src/beam_types.hrl @@ -57,7 +57,8 @@ valid=0 :: non_neg_integer()}). -record(t_bs_matchable, {tail_unit=1}). -record(t_float, {elements=any :: 'any' | {float(),float()}}). --record(t_fun, {arity=any :: arity() | 'any'}). +-record(t_fun, {arity=any :: arity() | 'any', + type=any :: type() }). -record(t_integer, {elements=any :: 'any' | {integer(),integer()}}). -record(t_map, {}). diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 6a7bc6d41b..a0662d171e 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -507,16 +507,7 @@ valfun_1(remove_message, Vst0) -> %% without restrictions. remove_fragility(Vst); valfun_1({'%', {var_info, Reg, Info}}, Vst) -> - case proplists:get_value(type, Info, any) of - none -> - %% Unreachable code, typically after a call that never returns. - kill_state(Vst); - Type -> - %% Explicit type information inserted by optimization passes to - %% indicate that Reg has a certain type, so that we can accept - %% cross-function type optimizations. - update_type(fun meet/2, Type, Reg, Vst) - end; + validate_var_info(Info, Reg, Vst); valfun_1({'%', {remove_fragility, Reg}}, Vst) -> %% This is a hack to make prim_eval:'receive'/2 work. %% @@ -529,6 +520,7 @@ valfun_1({'%',_}, Vst) -> Vst; valfun_1({line,_}, Vst) -> Vst; + %% %% Calls; these may be okay when the try/catch state or stack is undecided, %% depending on whether they always succeed or always fail. @@ -674,6 +666,25 @@ valfun_1(I, Vst0) -> Vst = branch_exception(Vst0), valfun_2(I, Vst). +validate_var_info([{fun_type, Type} | Info], Reg, Vst0) -> + %% Explicit type information inserted after make_fun2 instructions to mark + %% the return type of the created fun. + Vst = update_type(fun meet/2, #t_fun{type=Type}, Reg, Vst0), + validate_var_info(Info, Reg, Vst); +validate_var_info([{type, none} | _Info], _Reg, Vst) -> + %% Unreachable code, typically after a call that never returns. + kill_state(Vst); +validate_var_info([{type, Type} | Info], Reg, Vst0) -> + %% Explicit type information inserted by optimization passes to indicate + %% that Reg has a certain type, so that we can accept cross-function type + %% optimizations. + Vst = update_type(fun meet/2, Type, Reg, Vst0), + validate_var_info(Info, Reg, Vst); +validate_var_info([_ | Info], Reg, Vst) -> + validate_var_info(Info, Reg, Vst); +validate_var_info([], _Reg, Vst) -> + Vst. + validate_tail_call(Deallocate, Func, Live, #vst{current=#st{numy=NumY}}=Vst0) -> assert_float_checked(Vst0), case will_call_succeed(Func, Vst0) of diff --git a/lib/compiler/test/property_test/beam_types_prop.erl b/lib/compiler/test/property_test/beam_types_prop.erl index 1cfea9a6ba..a121535848 100644 --- a/lib/compiler/test/property_test/beam_types_prop.erl +++ b/lib/compiler/test/property_test/beam_types_prop.erl @@ -163,22 +163,22 @@ other_types() -> [any, gen_atom(), gen_bs_matchable(), - gen_fun(), none]. numerical_types() -> [gen_integer(), gen_float(), number]. nested_types(Depth) when Depth >= 3 -> [none]; -nested_types(Depth) -> list_types(Depth) ++ +nested_types(Depth) -> list_types(Depth + 1) ++ [#t_map{}, + gen_fun(Depth + 1), gen_union(Depth + 1), gen_tuple(Depth + 1)]. list_types(Depth) when Depth >= 3 -> [nil]; list_types(Depth) -> - [gen_list(Depth + 1), gen_cons(Depth + 1), nil]. + [gen_list(Depth), gen_cons(Depth), nil]. gen_atom() -> ?LET(Size, range(0, ?ATOM_SET_SIZE), @@ -200,8 +200,10 @@ gen_bs_matchable() -> ?LET(Unit, range(1, 128), #t_bs_context{tail_unit=Unit}), ?LET(Unit, range(1, 128), #t_bitstring{size_unit=Unit})]). -gen_fun() -> - oneof([?LET(Arity, range(1, 8), #t_fun{arity=Arity}), #t_fun{arity=any}]). +gen_fun(Depth) -> + oneof([?LET(Arity, range(1, 8), + #t_fun{type=type(Depth),arity=Arity}), + #t_fun{type=type(Depth),arity=any}]). gen_integer() -> oneof([gen_integer_bounded(), #t_integer{}]). -- cgit v1.2.1