From 2b5b3f1988d8ac46ba4c3de2c050af86511c7a18 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Fri, 28 Jun 2019 14:43:56 +0200 Subject: beam_types: Fix an integer consistency in meet/2 The test was brainfart; integers that don't overlap *AT ALL* should never meet. It's okay to meet as long as they overlap to some degree. --- lib/compiler/src/beam_types.erl | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_types.erl b/lib/compiler/src/beam_types.erl index 07d3c3d3f2..752dda0d2b 100644 --- a/lib/compiler/src/beam_types.erl +++ b/lib/compiler/src/beam_types.erl @@ -180,8 +180,9 @@ meet(#t_integer{elements={_,_}}=T, #t_integer{elements=any}) -> meet(#t_integer{elements=any}, #t_integer{elements={_,_}}=T) -> T; meet(#t_integer{elements={MinA,MaxA}}, #t_integer{elements={MinB,MaxB}}) - when MinA >= MinB, MaxA =< MaxB; - MinB >= MinA, MaxB =< MaxA -> + when MinA >= MinB, MinA =< MaxB; + MinB >= MinA, MinB =< MaxA -> + true = MinA =< MaxA andalso MinB =< MaxB, %Assertion. #t_integer{elements={max(MinA, MinB),min(MaxA, MaxB)}}; meet(#t_integer{}=T, number) -> T; meet(float=T, number) -> T; -- cgit v1.2.3 From db2ab3f206934926123c3d3acd33dd7b4c6e84db Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Fri, 5 Jul 2019 11:30:16 +0200 Subject: beam_call_types: Index must be >= 1 in setelement/2 --- lib/compiler/src/beam_call_types.erl | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_call_types.erl b/lib/compiler/src/beam_call_types.erl index d091b7866d..e72250ab37 100644 --- a/lib/compiler/src/beam_call_types.erl +++ b/lib/compiler/src/beam_call_types.erl @@ -198,7 +198,7 @@ types(erlang, element, [PosType, TupleType]) -> types(erlang, setelement, [PosType, TupleType, ArgType]) -> RetType = case {PosType,TupleType} of {#t_integer{elements={Index,Index}}, - #t_tuple{elements=Es0,size=Size}=T} -> + #t_tuple{elements=Es0,size=Size}=T} when Index >= 1 -> %% This is an exact index, update the type of said %% element or return 'none' if it's known to be out of %% bounds. @@ -212,7 +212,7 @@ types(erlang, setelement, [PosType, TupleType, ArgType]) -> none end; {#t_integer{elements={Min,Max}}, - #t_tuple{elements=Es0,size=Size}=T} -> + #t_tuple{elements=Es0,size=Size}=T} when Min >= 1 -> %% We know this will land between Min and Max, so kill %% the types for those indexes. Es = discard_tuple_element_info(Min, Max, Es0), -- cgit v1.2.3 From b713f93fb242e330cde1f3dcb135ec9795adccde Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Wed, 19 Jun 2019 16:09:45 +0200 Subject: beam_validator: Clean up abstract/match context type handling --- lib/compiler/src/beam_types.erl | 12 +++++ lib/compiler/src/beam_types.hrl | 7 +-- lib/compiler/src/beam_validator.erl | 98 ++++++++++++++++++++----------------- 3 files changed, 67 insertions(+), 50 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_types.erl b/lib/compiler/src/beam_types.erl index 752dda0d2b..4f8ba0ada5 100644 --- a/lib/compiler/src/beam_types.erl +++ b/lib/compiler/src/beam_types.erl @@ -171,6 +171,18 @@ meet(#t_atom{elements=[_|_]}=T, #t_atom{elements=any}) -> T; meet(#t_atom{elements=any}, #t_atom{elements=[_|_]}=T) -> T; +meet(#t_bs_context{slots=SlotCountA,valid=ValidSlotsA}, + #t_bs_context{slots=SlotCountB,valid=ValidSlotsB}) -> + CommonSlotMask = (1 bsl min(SlotCountA, SlotCountB)) - 1, + CommonSlotsA = ValidSlotsA band CommonSlotMask, + CommonSlotsB = ValidSlotsB band CommonSlotMask, + if + CommonSlotsA =:= CommonSlotsB -> + #t_bs_context{slots=max(SlotCountA, SlotCountB), + valid=ValidSlotsA bor ValidSlotsB}; + CommonSlotsA =/= CommonSlotsB -> + none + end; meet(#t_fun{arity=any}, #t_fun{}=T) -> T; meet(#t_fun{}=T, #t_fun{arity=any}) -> diff --git a/lib/compiler/src/beam_types.hrl b/lib/compiler/src/beam_types.hrl index 825eca4c64..212fe62063 100644 --- a/lib/compiler/src/beam_types.hrl +++ b/lib/compiler/src/beam_types.hrl @@ -37,8 +37,6 @@ %% -- cons Cons (nonempty list). %% -- nil The empty list. %% - #t_tuple{} Tuple. -%% - #t_abstract{} Psuedo-type used in the validator to track tuples -% under construction, match context positions, etc. %% %% none No type (bottom element). @@ -54,7 +52,6 @@ -record(t_tuple, {size=0 :: integer(), exact=false :: boolean(), elements=#{} :: tuple_elements()}). --record(t_abstract, {kind :: atom()}). %% Known element types, unknown elements are assumed to be 'any'. The key is %% a 1-based integer index for tuples, and a plain literal for maps (that is, @@ -67,6 +64,6 @@ -type type() :: any | none | list | number | - #t_atom{} | #t_bitstring{} | #t_bs_context{} | #t_fun{} | - #t_integer{} | #t_map{} | #t_tuple{} | #t_abstract{} | + #t_atom{} | #t_bitstring{} | #t_bs_context{} | + #t_fun{} | #t_integer{} | #t_map{} | #t_tuple{} | 'cons' | 'float' | 'nil'. diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 90049b3a25..9103d86fd4 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -111,8 +111,15 @@ validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) -> erlang:raise(Class, Error, Stack) end. +%% This is a psuedo-type used to track tuples under construction, match context +%% positions, and so on. It is not a part of the beam_types type lattice and +%% should not leak outside this module. +-record(t_abstract, {kind}). + +-type validator_type() :: #t_abstract{} | type(). + -record(value_ref, {id :: index()}). --record(value, {op :: term(), args :: [argument()], type :: type()}). +-record(value, {op :: term(), args :: [argument()], type :: validator_type()}). -type argument() :: #value_ref{} | literal(). @@ -328,7 +335,7 @@ valfun_1({try_case_end,Src}, Vst) -> kill_state(Vst); %% Instructions that cannot cause exceptions valfun_1({bs_get_tail,Ctx,Dst,Live}, Vst0) -> - bsm_validate_context(Ctx, Vst0), + assert_type(#t_bs_context{}, Ctx, Vst0), verify_live(Live, Vst0), verify_y_init(Vst0), Vst = prune_x_regs(Live, Vst0), @@ -401,7 +408,7 @@ valfun_1({put_tuple2,Dst,{list,Elements}}, Vst0) -> create_term(Type, put_tuple2, [], Dst, Vst); valfun_1({put_tuple,Sz,Dst}, Vst0) when is_integer(Sz) -> Vst1 = eat_heap(1, Vst0), - Vst = create_term(#t_abstract{kind=tuple_in_progress}, put_tuple, [], + Vst = create_term(#t_abstract{kind=unfinished_tuple}, put_tuple, [], Dst, Vst1), #vst{current=St0} = Vst, St = St0#st{puts_left={Sz,{Dst,Sz,#{}}}}, @@ -756,17 +763,17 @@ valfun_4({test,bs_start_match3,{f,Fail},Live,[Src],Dst}, Vst) -> valfun_4({test,bs_start_match2,{f,Fail},Live,[Src,Slots],Dst}, Vst) -> validate_bs_start_match(Fail, Live, bsm_match_state(Slots), Src, Dst, Vst); valfun_4({test,bs_match_string,{f,Fail},[Ctx,_,_]}, Vst) -> - bsm_validate_context(Ctx, Vst), + assert_type(#t_bs_context{}, Ctx, Vst), branch(Fail, Vst, fun(V) -> V end); valfun_4({test,bs_skip_bits2,{f,Fail},[Ctx,Src,_,_]}, Vst) -> - bsm_validate_context(Ctx, Vst), + assert_type(#t_bs_context{}, Ctx, Vst), assert_term(Src, Vst), branch(Fail, Vst, fun(V) -> V end); valfun_4({test,bs_test_tail2,{f,Fail},[Ctx,_]}, Vst) -> - bsm_validate_context(Ctx, Vst), + assert_type(#t_bs_context{}, Ctx, Vst), branch(Fail, Vst, fun(V) -> V end); valfun_4({test,bs_test_unit,{f,Fail},[Ctx,_]}, Vst) -> - bsm_validate_context(Ctx, Vst), + assert_type(#t_bs_context{}, Ctx, Vst), branch(Fail, Vst, fun(V) -> V end); valfun_4({test,bs_skip_utf8,{f,Fail},[Ctx,Live,_]}, Vst) -> validate_bs_skip_utf(Fail, Ctx, Live, Vst); @@ -807,14 +814,14 @@ valfun_4({bs_save2,Ctx,SavePoint}, Vst) -> valfun_4({bs_restore2,Ctx,SavePoint}, Vst) -> bsm_restore(Ctx, SavePoint, Vst); valfun_4({bs_get_position, Ctx, Dst, Live}, Vst0) -> - bsm_validate_context(Ctx, Vst0), + assert_type(#t_bs_context{}, Ctx, Vst0), verify_live(Live, Vst0), verify_y_init(Vst0), Vst = prune_x_regs(Live, Vst0), create_term(#t_abstract{kind=ms_position}, bs_get_position, [Ctx], Dst, Vst, Vst0); valfun_4({bs_set_position, Ctx, Pos}, Vst) -> - bsm_validate_context(Ctx, Vst), + assert_type(#t_bs_context{}, Ctx, Vst), assert_type(#t_abstract{kind=ms_position}, Pos, Vst), Vst; @@ -1125,7 +1132,7 @@ validate_bs_start_match(Fail, Live, Type, Src, Dst, Vst) -> %% Common code for validating bs_get* instructions. %% validate_bs_get(Op, Fail, Ctx, Live, Type, Dst, Vst) -> - bsm_validate_context(Ctx, Vst), + assert_type(#t_bs_context{}, Ctx, Vst), verify_live(Live, Vst), verify_y_init(Vst), @@ -1139,7 +1146,7 @@ validate_bs_get(Op, Fail, Ctx, Live, Type, Dst, Vst) -> %% Common code for validating bs_skip_utf* instructions. %% validate_bs_skip_utf(Fail, Ctx, Live, Vst) -> - bsm_validate_context(Ctx, Vst), + assert_type(#t_bs_context{}, Ctx, Vst), verify_y_init(Vst), verify_live(Live, Vst), @@ -1462,44 +1469,35 @@ bsm_match_state() -> bsm_match_state(Slots) -> #t_bs_context{slots=Slots}. -bsm_validate_context(Reg, Vst) -> - _ = bsm_get_context(Reg, Vst), - ok. - -bsm_get_context({Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y-> - case get_movable_term_type(Reg, Vst) of - #t_bs_context{}=Ctx -> Ctx; - _ -> error({no_bsm_context,Reg}) - end; -bsm_get_context(Reg, _) -> - error({bad_source,Reg}). - bsm_save(Reg, {atom,start}, Vst) -> %% Save point refering to where the match started. %% It is always valid. But don't forget to validate the context register. - bsm_validate_context(Reg, Vst), + assert_type(#t_bs_context{}, Reg, Vst), Vst; bsm_save(Reg, SavePoint, Vst) -> - case bsm_get_context(Reg, Vst) of - #t_bs_context{valid=Bits,slots=Slots}=Ctxt0 when SavePoint < Slots -> - Ctx = Ctxt0#t_bs_context{valid=Bits bor (1 bsl SavePoint),slots=Slots}, - override_type(Ctx, Reg, Vst); - _ -> error({illegal_save,SavePoint}) + case get_movable_term_type(Reg, Vst) of + #t_bs_context{valid=Bits,slots=Slots}=Ctxt0 when SavePoint < Slots -> + Ctx = Ctxt0#t_bs_context{valid=Bits bor (1 bsl SavePoint), + slots=Slots}, + override_type(Ctx, Reg, Vst); + _ -> + error({illegal_save, SavePoint}) end. bsm_restore(Reg, {atom,start}, Vst) -> %% (Mostly) automatic save point refering to where the match started. %% It is always valid. But don't forget to validate the context register. - bsm_validate_context(Reg, Vst), + assert_type(#t_bs_context{}, Reg, Vst), Vst; bsm_restore(Reg, SavePoint, Vst) -> - case bsm_get_context(Reg, Vst) of - #t_bs_context{valid=Bits,slots=Slots} when SavePoint < Slots -> - case Bits band (1 bsl SavePoint) of - 0 -> error({illegal_restore,SavePoint,not_set}); - _ -> Vst - end; - _ -> error({illegal_restore,SavePoint,range}) + case get_movable_term_type(Reg, Vst) of + #t_bs_context{valid=Bits,slots=Slots} when SavePoint < Slots -> + case Bits band (1 bsl SavePoint) of + 0 -> error({illegal_restore, SavePoint, not_set}); + _ -> Vst + end; + _ -> + error({illegal_restore, SavePoint, range}) end. validate_select_val(_Fail, _Choices, _Src, #vst{current=none}=Vst) -> @@ -1925,22 +1923,31 @@ is_literal(_) -> false. %% #t_bs_context{} A match context for bit syntax matching. We do allow %% it to moved/to from stack, but otherwise it must only %% be accessed by bit syntax matching instructions. -%% -%% These are simple wrappers around -join(#t_abstract{}=Same, #t_abstract{}=Same) -> Same; +%% These are just wrappers around their equivalents in beam_types, which +%% handle the validator-specific #t_abstract{} type. + +join(Same, Same) -> Same; +join(#t_abstract{}=A, B) -> #t_abstract{kind={join, A, B}}; +join(A, #t_abstract{}=B) -> #t_abstract{kind={join, A, B}}; join(A, B) -> beam_types:join(A, B). -meet(#t_abstract{}=Same, #t_abstract{}=Same) -> Same; +meet(Same, Same) -> Same; +meet(#t_abstract{}=A, B) -> #t_abstract{kind={meet, A, B}}; +meet(A, #t_abstract{}=B) -> #t_abstract{kind={meet, A, B}}; meet(A, B) -> beam_types:meet(A, B). +subtract(#t_abstract{}=A, B) -> #t_abstract{kind={subtract, A, B}}; +subtract(A, #t_abstract{}=B) -> #t_abstract{kind={subtract, A, B}}; subtract(A, B) -> beam_types:subtract(A, B). assert_type(RequiredType, Term, Vst) -> - GivenType = get_term_type(Term, Vst), + GivenType = get_movable_term_type(Term, Vst), case meet(RequiredType, GivenType) of - GivenType -> ok; - _RequiredType -> error({bad_type,{needed,RequiredType},{actual,GivenType}}) + GivenType -> + ok; + _RequiredType -> + error({bad_type,{needed,RequiredType},{actual,GivenType}}) end. validate_src(Ss, Vst) when is_list(Ss) -> @@ -1954,6 +1961,7 @@ validate_src(Ss, Vst) when is_list(Ss) -> get_term_type(Src, Vst) -> case get_movable_term_type(Src, Vst) of #t_bs_context{} -> error({match_context,Src}); + #t_abstract{} -> error({abstract_term,Src}); Type -> Type end. @@ -1963,7 +1971,7 @@ get_term_type(Src, Vst) -> get_movable_term_type(Src, Vst) -> case get_raw_type(Src, Vst) of - #t_abstract{kind=tuple_in_progress=Kind} -> error({Kind,Src}); + #t_abstract{kind=unfinished_tuple=Kind} -> error({Kind,Src}); initialized -> error({unassigned,Src}); uninitialized -> error({uninitialized_reg,Src}); {catchtag,_} -> error({catchtag,Src}); -- cgit v1.2.3 From 273099ac0e346c7324b0463e97bf6de7e96f4619 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Thu, 4 Jul 2019 12:48:11 +0200 Subject: beam_validator: Improve negative type inference The previous implementation of infer_types had a general problem with negative inference, and relied on an ugly hack to make simple subtraction work for type tests. This gets rid of that hack and makes it possible to subtract types on tuple size and element comparisons. --- lib/compiler/src/beam_validator.erl | 227 ++++++++++++++++++------------------ 1 file changed, 114 insertions(+), 113 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 9103d86fd4..5e01855ca1 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -1541,84 +1541,113 @@ validate_select_tuple_arity(Fail, [], _, #vst{}=Vst) -> kill_state(SuccVst) end). -infer_types({Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y -> - infer_types(get_reg_vref(Reg, Vst), Vst); -infer_types(#value_ref{}=Ref, #vst{current=#st{vs=Vs}}) -> +%% +%% Infers types from comparisons, looking at the expressions that produced the +%% compared values and updates their types if we've learned something new from +%% the comparison. +%% + +infer_types(CompareOp, {Kind,_}=LHS, RHS, Vst) when Kind =:= x; Kind =:= y -> + infer_types(CompareOp, get_reg_vref(LHS, Vst), RHS, Vst); +infer_types(CompareOp, LHS, {Kind,_}=RHS, Vst) when Kind =:= x; Kind =:= y -> + infer_types(CompareOp, LHS, get_reg_vref(RHS, Vst), Vst); +infer_types(CompareOp, LHS, RHS, #vst{current=#st{vs=Vs}}=Vst0) -> case Vs of - #{ Ref := Entry } -> infer_types_1(Entry); - #{} -> fun(_, S) -> S end + #{ LHS := LEntry, RHS := REntry } -> + Vst = infer_types_1(LEntry, RHS, CompareOp, Vst0), + infer_types_1(REntry, LHS, CompareOp, Vst); + #{ LHS := LEntry } -> + infer_types_1(LEntry, RHS, CompareOp, Vst0); + #{ RHS := REntry } -> + infer_types_1(REntry, LHS, CompareOp, Vst0); + #{} -> + Vst0 + end. + +infer_types_1(#value{op={bif,'=:='},args=[LHS,RHS]}, Val, Op, Vst0) -> + case Val of + {atom, Bool} when Op =:= eq_exact, Bool; Op =:= ne_exact, not Bool -> + Vst = infer_types(eq_exact, RHS, LHS, Vst0), + infer_types(eq_exact, LHS, RHS, Vst); + {atom, Bool} when Op =:= ne_exact, Bool; Op =:= eq_exact, not Bool -> + Vst = infer_types(ne_exact, RHS, LHS, Vst0), + infer_types(ne_exact, LHS, RHS, Vst); + _ -> + Vst0 end; -infer_types(_, #vst{}) -> - fun(_, S) -> S end. - -infer_types_1(#value{op={bif,'=:='},args=[LHS,RHS]}) -> - fun({atom,true}, S) -> - %% Either side might contain something worth inferring, so we need - %% to check them both. - Infer_L = infer_types(RHS, S), - Infer_R = infer_types(LHS, S), - Infer_R(RHS, Infer_L(LHS, S)); - (_, S) -> S +infer_types_1(#value{op={bif,'=/='},args=[LHS,RHS]}, Val, Op, Vst0) -> + case Val of + {atom, Bool} when Op =:= ne_exact, Bool; Op =:= eq_exact, not Bool -> + Vst = infer_types(ne_exact, RHS, LHS, Vst0), + infer_types(ne_exact, LHS, RHS, Vst); + {atom, Bool} when Op =:= eq_exact, Bool; Op =:= ne_exact, not Bool -> + Vst = infer_types(eq_exact, RHS, LHS, Vst0), + infer_types(eq_exact, LHS, RHS, Vst); + _ -> + Vst0 end; -infer_types_1(#value{op={bif,element},args=[{integer,Index},Tuple]}) -> - fun(Val, S) -> - case is_value_alive(Tuple, S) of - true -> - ElementType = get_term_type(Val, S), - Es = beam_types:set_element_type(Index, ElementType, #{}), - Type = #t_tuple{size=Index,elements=Es}, - update_type(fun meet/2, Type, Tuple, S); - false -> - S - end +infer_types_1(#value{op={bif,element},args=[{integer,Index},Tuple]}, + Val, Op, Vst) when Index >= 1 -> + Merge = case Op of + eq_exact -> fun meet/2; + ne_exact -> fun subtract/2 + end, + case is_value_alive(Tuple, Vst) of + true -> + ElementType = get_term_type(Val, Vst), + Es = beam_types:set_element_type(Index, ElementType, #{}), + Type = #t_tuple{size=Index,elements=Es}, + update_type(Merge, Type, Tuple, Vst); + false -> + Vst end; -infer_types_1(#value{op={bif,is_atom},args=[Src]}) -> - infer_type_test_bif(#t_atom{}, Src); -infer_types_1(#value{op={bif,is_boolean},args=[Src]}) -> - infer_type_test_bif(beam_types:make_boolean(), Src); -infer_types_1(#value{op={bif,is_binary},args=[Src]}) -> - infer_type_test_bif(#t_bitstring{unit=8}, Src); -infer_types_1(#value{op={bif,is_bitstring},args=[Src]}) -> - infer_type_test_bif(#t_bitstring{}, Src); -infer_types_1(#value{op={bif,is_float},args=[Src]}) -> - infer_type_test_bif(float, Src); -infer_types_1(#value{op={bif,is_integer},args=[Src]}) -> - infer_type_test_bif(#t_integer{}, Src); -infer_types_1(#value{op={bif,is_list},args=[Src]}) -> - infer_type_test_bif(list, Src); -infer_types_1(#value{op={bif,is_map},args=[Src]}) -> - infer_type_test_bif(#t_map{}, Src); -infer_types_1(#value{op={bif,is_number},args=[Src]}) -> - infer_type_test_bif(number, Src); -infer_types_1(#value{op={bif,is_tuple},args=[Src]}) -> - infer_type_test_bif(#t_tuple{}, Src); -infer_types_1(#value{op={bif,tuple_size}, args=[Tuple]}) -> - fun({integer,Arity}, S) -> - case is_value_alive(Tuple, S) of - true -> - Type = #t_tuple{exact=true,size=Arity}, - update_type(fun meet/2, Type, Tuple, S); - false -> - S - end; - (_, S) -> S +infer_types_1(#value{op={bif,is_atom},args=[Src]}, Val, Op, Vst) -> + infer_type_test_bif(#t_atom{}, Src, Val, Op, Vst); +infer_types_1(#value{op={bif,is_boolean},args=[Src]}, Val, Op, Vst) -> + infer_type_test_bif(beam_types:make_boolean(), Src, Val, Op, Vst); +infer_types_1(#value{op={bif,is_binary},args=[Src]}, Val, Op, Vst) -> + infer_type_test_bif(#t_bitstring{unit=8}, Src, Val, Op, Vst); +infer_types_1(#value{op={bif,is_bitstring},args=[Src]}, Val, Op, Vst) -> + infer_type_test_bif(#t_bitstring{}, Src, Val, Op, Vst); +infer_types_1(#value{op={bif,is_float},args=[Src]}, Val, Op, Vst) -> + infer_type_test_bif(float, Src, Val, Op, Vst); +infer_types_1(#value{op={bif,is_integer},args=[Src]}, Val, Op, Vst) -> + infer_type_test_bif(#t_integer{}, Src, Val, Op, Vst); +infer_types_1(#value{op={bif,is_list},args=[Src]}, Val, Op, Vst) -> + infer_type_test_bif(list, Src, Val, Op, Vst); +infer_types_1(#value{op={bif,is_map},args=[Src]}, Val, Op, Vst) -> + infer_type_test_bif(#t_map{}, Src, Val, Op, Vst); +infer_types_1(#value{op={bif,is_number},args=[Src]}, Val, Op, Vst) -> + infer_type_test_bif(number, Src, Val, Op, Vst); +infer_types_1(#value{op={bif,is_tuple},args=[Src]}, Val, Op, Vst) -> + infer_type_test_bif(#t_tuple{}, Src, Val, Op, Vst); +infer_types_1(#value{op={bif,tuple_size}, args=[Tuple]}, + {integer,Arity}, Op, Vst) -> + Merge = case Op of + eq_exact -> fun meet/2; + ne_exact -> fun subtract/2 + end, + case is_value_alive(Tuple, Vst) of + true -> + Type = #t_tuple{exact=true,size=Arity}, + update_type(Merge, Type, Tuple, Vst); + false -> + Vst end; -infer_types_1(_) -> - fun(_, S) -> S end. - -infer_type_test_bif(Type, Src) -> - fun({atom,Bool}, S) when is_boolean(Bool) -> - case is_value_alive(Src, S) of - true when Bool =:= true -> - update_type(fun meet/2, Type, Src, S); - true when Bool =:= false -> - update_type(fun subtract/2, Type, Src, S); - false -> - S - end; - (_, S) -> - S - end. +infer_types_1(_, _, _, Vst) -> + Vst. + +infer_type_test_bif(Type, Src, {atom, Bool}, Op, Vst) when is_boolean(Bool) -> + case is_value_alive(Src, Vst) of + true when Op =:= eq_exact, Bool; Op =:= ne_exact, not Bool -> + update_type(fun meet/2, Type, Src, Vst); + true when Op =:= ne_exact, Bool; Op =:= eq_exact, not Bool -> + update_type(fun subtract/2, Type, Src, Vst); + false -> + Vst + end; +infer_type_test_bif(_, _, _, _, Vst) -> + Vst. %%% %%% Keeping track of types. @@ -1736,33 +1765,18 @@ update_type(Merge, With, Literal, Vst) -> _Type -> Vst end. -update_ne_types(LHS, {atom,Bool}=RHS, Vst) when is_boolean(Bool) -> - %% This is a stopgap to make negative inference work for type test BIFs - %% like is_tuple. Consider the following unoptimized code: - %% - %% {call_ext,2,{extfunc,erlang,'--',2}}. - %% {bif,is_tuple,{f,0},[{x,0}],{x,1}}. - %% {test,is_eq_exact,{x,1},{f,2},{atom,false}}. - %% ... snip ... - %% {label,1}. - %% {test,is_eq_exact,{x,1},{f,1},{atom,true}}. - %% ... unreachable because {x,0} is known to be a list, so {x,1} can't - %% be true ... - %% {label,2}. - %% ... unreachable because {x,1} is neither true nor false! ... - %% - %% If we fail to determine that the first is_eq_exact never fails, our - %% state will be inconsistent after the second is_eq_exact check; we know - %% for certain that {x,0} is a list so infer_types says it can't succeed, - %% but it can't fail either because we also know that {x,1} is a boolean, - %% and the first check ruled out 'false'. - LType = get_term_type(LHS, Vst), - RType = get_term_type(RHS, Vst), - case beam_types:is_boolean_type(LType) of - true -> update_eq_types(LHS, {atom, not Bool}, Vst); - false -> update_type(fun subtract/2, RType, LHS, Vst) - end; -update_ne_types(LHS, RHS, Vst) -> +update_eq_types(LHS, RHS, Vst0) -> + Vst1 = infer_types(eq_exact, LHS, RHS, Vst0), + + T1 = get_term_type(LHS, Vst1), + T2 = get_term_type(RHS, Vst1), + + Vst = update_type(fun meet/2, T2, LHS, Vst1), + update_type(fun meet/2, T1, RHS, Vst). + +update_ne_types(LHS, RHS, Vst0) -> + Vst = infer_types(ne_exact, LHS, RHS, Vst0), + %% While updating types on equality is fairly straightforward, inequality %% is a bit trickier since all we know is that the *value* of LHS differs %% from RHS, so we can't blindly subtract their types. @@ -1778,19 +1792,6 @@ update_ne_types(LHS, RHS, Vst) -> false -> Vst end. -update_eq_types(LHS, RHS, Vst0) -> - %% Either side might contain something worth inferring, so we need - %% to check them both. - Infer_L = infer_types(RHS, Vst0), - Infer_R = infer_types(LHS, Vst0), - Vst1 = Infer_R(RHS, Infer_L(LHS, Vst0)), - - T1 = get_term_type(LHS, Vst1), - T2 = get_term_type(RHS, Vst1), - - Vst = update_type(fun meet/2, T2, LHS, Vst1), - update_type(fun meet/2, T1, RHS, Vst). - %% Helper functions for the above. assign_1(Src, Dst, Vst0) -> -- cgit v1.2.3 From 1a872b02ee81c0f2653426d4796771ec3bfaea0c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Fri, 5 Jul 2019 09:39:22 +0200 Subject: beam_validator: Slightly improve type/tag-related comments --- lib/compiler/src/beam_validator.erl | 49 ++++++++++++++++++------------------- 1 file changed, 24 insertions(+), 25 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 5e01855ca1..8064912aac 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -111,11 +111,11 @@ validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) -> erlang:raise(Class, Error, Stack) end. -%% This is a psuedo-type used to track tuples under construction, match context -%% positions, and so on. It is not a part of the beam_types type lattice and -%% should not leak outside this module. -record(t_abstract, {kind}). +%% The types are the same as in 'beam_types.hrl', with the addition of +%% #t_abstract{} that describes tuples under construction, match context +%% positions, and so on. -type validator_type() :: #t_abstract{} | type(). -record(value_ref, {id :: index()}). @@ -131,6 +131,24 @@ validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) -> {literal, term()} | nil. +%% Register tags describe the state of the register rather than the value they +%% contain (if any). +%% +%% initialized The register has been initialized with some valid term +%% so that it is safe to pass to the garbage collector. +%% NOT safe to use in any other way (will not crash the +%% emulator, but clearly points to a bug in the compiler). +%% +%% uninitialized The register contains any old garbage and can not be +%% passed to the garbage collector. +%% +%% {catchtag,[Lbl]} A special term used within a catch. Must only be used +%% by the catch instructions; NOT safe to use in other +%% instructions. +%% +%% {trytag,[Lbl]} A special term used within a try block. Must only be +%% used by the catch instructions; NOT safe to use in other +%% instructions. -type tag() :: initialized | uninitialized | {catchtag, [label()]} | @@ -1903,30 +1921,11 @@ is_literal({integer,I}) when is_integer(I) -> true; is_literal({literal,_L}) -> true; is_literal(_) -> false. -%% The possible types. -%% -%% First non-term types: -%% -%% initialized Only for Y registers. Means that the Y register -%% has been initialized with some valid term so that -%% it is safe to pass to the garbage collector. -%% NOT safe to use in any other way (will not crash the -%% emulator, but clearly points to a bug in the compiler). -%% -%% {catchtag,[Lbl]} A special term used within a catch. Must only be used -%% by the catch instructions; NOT safe to use in other -%% instructions. -%% -%% {trytag,[Lbl]} A special term used within a try block. Must only be -%% used by the catch instructions; NOT safe to use in other -%% instructions. -%% -%% #t_bs_context{} A match context for bit syntax matching. We do allow -%% it to moved/to from stack, but otherwise it must only -%% be accessed by bit syntax matching instructions. - %% These are just wrappers around their equivalents in beam_types, which %% handle the validator-specific #t_abstract{} type. +%% +%% The funny-looking abstract types produced here are intended to provoke +%% errors on actual use; they do no harm just lying around. join(Same, Same) -> Same; join(#t_abstract{}=A, B) -> #t_abstract{kind={join, A, B}}; -- cgit v1.2.3 From 950ce53fc5e4c80d10c78d0cf1fad88745b633eb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Thu, 20 Jun 2019 09:53:53 +0200 Subject: compiler: Remove beam_call_types:never_throws/3 The idea was to look at the argument types to see if we could get rid of failure branches, but this didn't turn out to be useful and the function ended up being a copy of erl_bifs:is_safe/3, so we may as well get rid of it. --- lib/compiler/src/beam_call_types.erl | 34 +--------------------------------- lib/compiler/src/beam_validator.erl | 2 +- 2 files changed, 2 insertions(+), 34 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_call_types.erl b/lib/compiler/src/beam_call_types.erl index e72250ab37..2aba6f7961 100644 --- a/lib/compiler/src/beam_call_types.erl +++ b/lib/compiler/src/beam_call_types.erl @@ -24,39 +24,7 @@ -import(lists, [duplicate/2,foldl/3]). --export([never_throws/3, types/3]). - --spec never_throws(Mod, Func, Arity) -> boolean() when - Mod :: atom(), - Func :: atom(), - Arity :: non_neg_integer(). - -never_throws(erlang, '/=', 2) -> true; -never_throws(erlang, '<', 2) -> true; -never_throws(erlang, '=/=', 2) -> true; -never_throws(erlang, '=:=', 2) -> true; -never_throws(erlang, '=<', 2) -> true; -never_throws(erlang, '==', 2) -> true; -never_throws(erlang, '>', 2) -> true; -never_throws(erlang, '>=', 2) -> true; -never_throws(erlang, is_atom, 1) -> true; -never_throws(erlang, is_boolean, 1) -> true; -never_throws(erlang, is_binary, 1) -> true; -never_throws(erlang, is_bitstring, 1) -> true; -never_throws(erlang, is_float, 1) -> true; -never_throws(erlang, is_function, 1) -> true; -never_throws(erlang, is_integer, 1) -> true; -never_throws(erlang, is_list, 1) -> true; -never_throws(erlang, is_map, 1) -> true; -never_throws(erlang, is_number, 1) -> true; -never_throws(erlang, is_pid, 1) -> true; -never_throws(erlang, is_port, 1) -> true; -never_throws(erlang, is_reference, 1) -> true; -never_throws(erlang, is_tuple, 1) -> true; -never_throws(erlang, get, 1) -> true; -never_throws(erlang, self, 0) -> true; -never_throws(erlang, node, 0) -> true; -never_throws(_, _, _) -> false. +-export([types/3]). %% %% Returns the inferred return and argument types for known functions, and diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 8064912aac..d959700b88 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -396,7 +396,7 @@ valfun_1({init,Reg}, Vst) -> valfun_1({test_heap,Heap,Live}, Vst) -> test_heap(Heap, Live, Vst); valfun_1({bif,Op,{f,_},Ss,Dst}=I, Vst) -> - case beam_call_types:never_throws(erlang, Op, length(Ss)) of + case erl_bifs:is_safe(erlang, Op, length(Ss)) of true -> %% It can't fail, so we finish handling it here (not updating %% catch state). -- cgit v1.2.3 From 1e4e506b5c3af02632da29b0802e913121403bf4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Wed, 26 Jun 2019 13:26:05 +0200 Subject: beam_ssa_type: Fix type inference on BIFs without a success check --- lib/compiler/src/beam_ssa_type.erl | 29 +++++++++++++++-------------- 1 file changed, 15 insertions(+), 14 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 79c67e5705..d88f43cb5c 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -1328,22 +1328,19 @@ infer_eq_lit(_, _) -> []. 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, #{}), #{}), 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,8 +1371,10 @@ infer_type({bif,is_number}, [Arg], _Ts, _Ds) -> infer_type({bif,is_tuple}, [Arg], _Ts, _Ds) -> T = {Arg, #t_tuple{}}, {[T], [T]}; +infer_type(_Op, _Args, _Ts, _Ds) -> + {[], []}. -infer_type({bif,Op}, Args, Ts, _Ds) -> +infer_success_type({bif,Op}, Args, Ts, _Ds) -> ArgTypes = get_types(Args, Ts), {_, PosTypes0, CanSubtract} = beam_call_types:types(erlang, Op, ArgTypes), @@ -1385,8 +1384,10 @@ infer_type({bif,Op}, Args, Ts, _Ds) -> true -> {PosTypes, PosTypes}; false -> {PosTypes, []} end; - -infer_type(_Op, _Args, _Ts, _Ds) -> +infer_success_type(bs_start_match, [#b_var{}=Bin], _Ts, _Ds) -> + T = {Bin,#t_bitstring{}}, + {[T], [T]}; +infer_success_type(_Op, _Args, _Ts, _Ds) -> {[], []}. join_types(Ts0, Ts1) -> -- cgit v1.2.3 From 02c74c89232ed72f16c2a326e0c15938c3493041 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Tue, 25 Jun 2019 12:56:24 +0200 Subject: compiler: Introduce exception trampolines When the compiler is smart enough to figure out that something will always succeed, it will get rid of the failure branch, but the inverse has not been possible because liveness optimization could end up removing the instruction altogether (since it's never used on the failure path), which is not okay when exceptions are in the picture. To prevent exception-generating instructions from being optimized away when their branches are, we introduce a dummy instruction that refers to the result on the failure path, ensuring that it won't be optimized away. --- lib/compiler/src/beam_kernel_to_ssa.erl | 167 +++++++++++++++++------------- lib/compiler/src/beam_ssa.erl | 2 +- lib/compiler/src/beam_ssa_codegen.erl | 6 ++ lib/compiler/src/beam_ssa_opt.erl | 112 ++++++++++++-------- lib/compiler/src/beam_ssa_pre_codegen.erl | 39 +++++++ 5 files changed, 208 insertions(+), 118 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_kernel_to_ssa.erl b/lib/compiler/src/beam_kernel_to_ssa.erl index df95749fb3..b2d824b648 100644 --- a/lib/compiler/src/beam_kernel_to_ssa.erl +++ b/lib/compiler/src/beam_kernel_to_ssa.erl @@ -279,7 +279,7 @@ select_binary(#k_val_clause{val=#k_binary{segs=#k_var{name=Ctx0}},body=B}, #k_var{}=Src, Tf, Vf, St0) -> {Ctx,St1} = new_ssa_var(Ctx0, St0), {Bis0,St2} = match_cg(B, Vf, St1), - {TestIs,St} = make_cond_branch(succeeded, [Ctx], Tf, St2), + {TestIs,St} = make_succeeded(Ctx, {guard, Tf}, St2), Bis1 = [#b_set{op=bs_start_match,dst=Ctx, args=[ssa_arg(Src, St)]}] ++ TestIs ++ Bis0, Bis = finish_bs_matching(Bis1), @@ -311,6 +311,35 @@ make_cond_branch(Cond, Args, Fail, St0) -> make_uncond_branch(Fail) -> #b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail}. +%% +%% The 'succeeded' instruction needs special treatment in catch blocks to +%% prevent the checked operation from being optimized away if a later pass +%% determines that it always fails. +%% + +make_succeeded(Var, {in_catch, CatchLbl}, St0) -> + {Bool, St1} = new_ssa_var('@ssa_bool', St0), + {Succ, St2} = new_label(St1), + {Fail, St} = new_label(St2), + + Check = [#b_set{op=succeeded,dst=Bool,args=[Var]}, + #b_br{bool=Bool,succ=Succ,fail=Fail}], + + %% Add a dummy block that references the checked variable, ensuring it + %% stays alive and that it won't be merged with the landing pad. + Trampoline = [{label,Fail}, + #b_set{op=exception_trampoline,args=[Var]}, + make_uncond_branch(CatchLbl)], + + {Check ++ Trampoline ++ [{label,Succ}], St}; +make_succeeded(Var, {no_catch, Fail}, St) -> + %% Ultimate failure raises an exception, so we must treat it as if it were + %% in a catch to keep it from being optimized out. + #cg{ultimate_failure=Fail} = St, %Assertion + make_succeeded(Var, {in_catch, Fail}, St); +make_succeeded(Var, {guard, Fail}, St) -> + make_cond_branch(succeeded, [Var], Fail, St). + %% Instructions for selection of binary segments. select_bin_segs(Scs, Ivar, Tf, St) -> @@ -394,7 +423,7 @@ select_extract_int(#k_var{name=Tl}, Val, #k_int{val=Sz}, U, Fs, Vf, <> end, Bits = bit_size(Bin), %Assertion. - {TestIs,St} = make_cond_branch(succeeded, [Dst], Vf, St1), + {TestIs,St} = make_succeeded(Dst, {guard, Vf}, St1), Set = #b_set{op=bs_match,dst=Dst, args=[#b_literal{val=string},Ctx,#b_literal{val=Bin}]}, {[Set|TestIs],St}. @@ -412,7 +441,7 @@ build_bs_instr(Anno, Type, Fail, Ctx, Size, Unit0, Flags0, Dst, St0) -> #b_set{anno=Anno,op=bs_match,dst=Dst, args=[TypeArg,Ctx,Flags]} end, - {Is,St} = make_cond_branch(succeeded, [Dst], Fail, St0), + {Is,St} = make_succeeded(Dst, {guard, Fail}, St0), {[Get|Is],St}. select_val(#k_val_clause{val=#k_tuple{es=Es},body=B}, V, Vf, St0) -> @@ -475,7 +504,7 @@ select_extract_map([P|Ps], Src, Fail, St0) -> Key = ssa_arg(Key0, St0), {Dst,St1} = new_ssa_var(Dst0, St0), Set = #b_set{op=get_map_element,dst=Dst,args=[MapSrc,Key]}, - {TestIs,St2} = make_cond_branch(succeeded, [Dst], Fail, St1), + {TestIs,St2} = make_succeeded(Dst, {guard, Fail}, St1), {Is,St} = select_extract_map(Ps, Src, Fail, St2), {[Set|TestIs]++Is,St}; select_extract_map([], _, _, St) -> @@ -596,7 +625,7 @@ match_fmf(F, LastFail, St0, [H|T]) -> {Rs,St3} = match_fmf(F, LastFail, St2, T), {R ++ [{label,Fail}] ++ Rs,St3}. -%% fail_label(State) -> {Where,FailureLabel}. +%% fail_context(State) -> {Where,FailureLabel}. %% Where = guard | no_catch | in_catch %% Return an indication of which part of a function code is %% being generated for and the appropriate failure label to @@ -609,7 +638,7 @@ match_fmf(F, LastFail, St0, [H|T]) -> %% a try/catch or catch. %% in_catch - In the scope of a try/catch or catch. -fail_label(#cg{catch_label=Catch,bfail=Fail,ultimate_failure=Ult}) -> +fail_context(#cg{catch_label=Catch,bfail=Fail,ultimate_failure=Ult}) -> if Fail =/= Ult -> {guard,Fail}; @@ -619,14 +648,6 @@ fail_label(#cg{catch_label=Catch,bfail=Fail,ultimate_failure=Ult}) -> {in_catch,Catch} end. -%% bif_fail_label(State) -> FailureLabel. -%% Return the appropriate failure label for a guard BIF call or -%% primop that fails. - -bif_fail_label(St) -> - {_,Fail} = fail_label(St), - Fail. - %% call_cg(Func, [Arg], [Ret], Le, State) -> %% {[Ainstr],State}. %% enter_cg(Func, [Arg], Le, St) -> {[Ainstr],St}. @@ -635,7 +656,7 @@ bif_fail_label(St) -> call_cg(Func, As, [], Le, St) -> call_cg(Func, As, [#k_var{name='@ssa_ignored'}], Le, St); call_cg(Func0, As, [#k_var{name=R}|MoreRs]=Rs, Le, St0) -> - case fail_label(St0) of + case fail_context(St0) of {guard,Fail} -> %% Inside a guard. The only allowed function call is to %% erlang:error/1,2. We will generate a branch to the @@ -645,7 +666,7 @@ call_cg(Func0, As, [#k_var{name=R}|MoreRs]=Rs, Le, St0) -> [#k_var{name=DestVar}] = Rs, St = set_ssa_var(DestVar, #b_literal{val=unused}, St0), {[make_uncond_branch(Fail),#cg_unreachable{}],St}; - {Catch,Fail} -> + FailCtx -> %% Ordinary function call in a function body. Args = ssa_args(As, St0), {Ret,St1} = new_ssa_var(R, St0), @@ -657,11 +678,12 @@ call_cg(Func0, As, [#k_var{name=R}|MoreRs]=Rs, Le, St0) -> St2 = foldl(fun(#k_var{name=Dummy}, S) -> set_ssa_var(Dummy, #b_literal{val=unused}, S) end, St1, MoreRs), - case Catch of - no_catch -> + + case FailCtx of + {no_catch, _} -> {[Call],St2}; - in_catch -> - {TestIs,St} = make_cond_branch(succeeded, [Ret], Fail, St2), + {in_catch, _} -> + {TestIs,St} = make_succeeded(Ret, FailCtx, St2), {[Call|TestIs],St} end end. @@ -748,8 +770,8 @@ bif_cg(Bif, As0, [#k_var{name=Dst0}], Le, St0) -> I = #b_set{anno=line_anno(Le),op={bif,Bif},dst=Dst,args=As}, case erl_bifs:is_safe(erlang, Bif, length(As)) of false -> - Fail = bif_fail_label(St1), - {Is,St} = make_cond_branch(succeeded, [Dst], Fail, St1), + FailCtx = fail_context(St1), + {Is,St} = make_succeeded(Dst, FailCtx, St1), {[I|Is],St}; true-> {[I],St1} @@ -797,7 +819,7 @@ cg_recv_mesg(#k_var{name=R}, Rm, Tl, Le, St0) -> {Dst,St1} = new_ssa_var(R, St0), {Mis,St2} = match_cg(Rm, none, St1), RecvLbl = St1#cg.recv, - {TestIs,St} = make_cond_branch(succeeded, [Dst], Tl, St2), + {TestIs,St} = make_succeeded(Dst, {guard, Tl}, St2), Is = [#b_br{anno=line_anno(Le),bool=#b_literal{val=true}, succ=RecvLbl,fail=RecvLbl}, {label,RecvLbl}, @@ -813,7 +835,7 @@ cg_recv_wait(Te, Es, St0) -> {Tis,St1} = cg(Es, St0), Args = [ssa_arg(Te, St1)], {WaitDst,St2} = new_ssa_var('@ssa_wait', St1), - {WaitIs,St} = make_cond_branch(succeeded, [WaitDst], St1#cg.recv, St2), + {WaitIs,St} = make_succeeded(WaitDst, {guard, St1#cg.recv}, St2), %% Infinite timeout will be optimized later. Is = [#b_set{op=wait_timeout,dst=WaitDst,args=Args}] ++ WaitIs ++ [#b_set{op=timeout}] ++ Tis, @@ -924,9 +946,9 @@ put_cg([#k_var{name=R}], #k_tuple{es=Es}, _Le, St0) -> PutTuple = #b_set{op=put_tuple,dst=Ret,args=Args}, {[PutTuple],St}; put_cg([#k_var{name=R}], #k_binary{segs=Segs}, Le, St0) -> - Fail = bif_fail_label(St0), + FailCtx = fail_context(St0), {Dst,St1} = new_ssa_var(R, St0), - cg_binary(Dst, Segs, Fail, Le, St1); + cg_binary(Dst, Segs, FailCtx, Le, St1); put_cg([#k_var{name=R}], #k_map{op=Op,var=Map, es=[#k_map_pair{key=#k_var{}=K,val=V}]}, Le, St0) -> @@ -955,14 +977,14 @@ put_cg([#k_var{name=R}], Con0, _Le, St0) -> {[],St}. put_cg_map(LineAnno, Op, SrcMap, Dst, List, St0) -> - Fail = bif_fail_label(St0), Args = [#b_literal{val=Op},SrcMap|List], PutMap = #b_set{anno=LineAnno,op=put_map,dst=Dst,args=Args}, if Op =:= assoc -> {[PutMap],St0}; true -> - {Is,St} = make_cond_branch(succeeded, [Dst], Fail, St0), + FailCtx = fail_context(St0), + {Is,St} = make_succeeded(Dst, FailCtx, St0), {[PutMap|Is],St} end. @@ -970,8 +992,8 @@ put_cg_map(LineAnno, Op, SrcMap, Dst, List, St0) -> %%% Code generation for constructing binaries. %%% -cg_binary(Dst, Segs0, Fail, Le, St0) -> - {PutCode0,SzCalc0,St1} = cg_bin_put(Segs0, Fail, St0), +cg_binary(Dst, Segs0, FailCtx, Le, St0) -> + {PutCode0,SzCalc0,St1} = cg_bin_put(Segs0, FailCtx, St0), LineAnno = line_anno(Le), Anno = Le#k.a, case PutCode0 of @@ -980,8 +1002,8 @@ cg_binary(Dst, Segs0, Fail, Le, St0) -> {label,_}|_] -> #k_bin_seg{unit=Unit0,next=Segs} = Segs0, Unit = #b_literal{val=Unit0}, - {PutCode,SzCalc1,St2} = cg_bin_put(Segs, Fail, St1), - {_,SzVar,SzCode0,St3} = cg_size_calc(1, SzCalc1, Fail, St2), + {PutCode,SzCalc1,St2} = cg_bin_put(Segs, FailCtx, St1), + {_,SzVar,SzCode0,St3} = cg_size_calc(1, SzCalc1, FailCtx, St2), SzCode = cg_bin_anno(SzCode0, LineAnno), Args = case member(single_use, Anno) of true -> @@ -990,14 +1012,14 @@ cg_binary(Dst, Segs0, Fail, Le, St0) -> [#b_literal{val=append},Src,SzVar,Unit] end, BsInit = #b_set{anno=LineAnno,op=bs_init,dst=Dst,args=Args}, - {TestIs,St} = make_cond_branch(succeeded, [Dst], Fail, St3), + {TestIs,St} = make_succeeded(Dst, FailCtx, St3), {SzCode ++ [BsInit] ++ TestIs ++ PutCode,St}; [#b_set{op=bs_put}|_] -> - {Unit,SzVar,SzCode0,St2} = cg_size_calc(8, SzCalc0, Fail, St1), + {Unit,SzVar,SzCode0,St2} = cg_size_calc(8, SzCalc0, FailCtx, St1), SzCode = cg_bin_anno(SzCode0, LineAnno), Args = [#b_literal{val=new},SzVar,Unit], BsInit = #b_set{anno=LineAnno,op=bs_init,dst=Dst,args=Args}, - {TestIs,St} = make_cond_branch(succeeded, [Dst], Fail, St2), + {TestIs,St} = make_succeeded(Dst, FailCtx, St2), {SzCode ++ [BsInit] ++ TestIs ++ PutCode0,St} end. @@ -1005,18 +1027,18 @@ cg_bin_anno([Set|Sets], Anno) -> [Set#b_set{anno=Anno}|Sets]; cg_bin_anno([], _) -> []. -%% cg_size_calc(PreferredUnit, SzCalc, Fail, St0) -> +%% cg_size_calc(PreferredUnit, SzCalc, FailCtx, St0) -> %% {ActualUnit,SizeVariable,SizeCode,St}. %% Generate size calculation code. -cg_size_calc(Unit, error, _Fail, St) -> +cg_size_calc(Unit, error, _FailCtx, St) -> {#b_literal{val=Unit},#b_literal{val=badarg},[],St}; -cg_size_calc(8, [{1,_}|_]=SzCalc, Fail, St) -> - cg_size_calc(1, SzCalc, Fail, St); -cg_size_calc(8, SzCalc, Fail, St0) -> - {Var,Pre,St} = cg_size_calc_1(SzCalc, Fail, St0), +cg_size_calc(8, [{1,_}|_]=SzCalc, FailCtx, St) -> + cg_size_calc(1, SzCalc, FailCtx, St); +cg_size_calc(8, SzCalc, FailCtx, St0) -> + {Var,Pre,St} = cg_size_calc_1(SzCalc, FailCtx, St0), {#b_literal{val=8},Var,Pre,St}; -cg_size_calc(1, SzCalc0, Fail, St0) -> +cg_size_calc(1, SzCalc0, FailCtx, St0) -> SzCalc = map(fun({8,#b_literal{val=Size}}) -> {1,#b_literal{val=8*Size}}; ({8,{{bif,byte_size},Src}}) -> @@ -1026,54 +1048,54 @@ cg_size_calc(1, SzCalc0, Fail, St0) -> ({_,_}=Pair) -> Pair end, SzCalc0), - {Var,Pre,St} = cg_size_calc_1(SzCalc, Fail, St0), + {Var,Pre,St} = cg_size_calc_1(SzCalc, FailCtx, St0), {#b_literal{val=1},Var,Pre,St}. -cg_size_calc_1(SzCalc, Fail, St0) -> - cg_size_calc_2(SzCalc, #b_literal{val=0}, Fail, St0). +cg_size_calc_1(SzCalc, FailCtx, St0) -> + cg_size_calc_2(SzCalc, #b_literal{val=0}, FailCtx, St0). -cg_size_calc_2([{_,{'*',Unit,{_,_}=Bif}}|T], Sum0, Fail, St0) -> - {Sum1,Pre0,St1} = cg_size_calc_2(T, Sum0, Fail, St0), - {BifDst,Pre1,St2} = cg_size_bif(Bif, Fail, St1), - {Sum,Pre2,St} = cg_size_add(Sum1, BifDst, Unit, Fail, St2), +cg_size_calc_2([{_,{'*',Unit,{_,_}=Bif}}|T], Sum0, FailCtx, St0) -> + {Sum1,Pre0,St1} = cg_size_calc_2(T, Sum0, FailCtx, St0), + {BifDst,Pre1,St2} = cg_size_bif(Bif, FailCtx, St1), + {Sum,Pre2,St} = cg_size_add(Sum1, BifDst, Unit, FailCtx, St2), {Sum,Pre0++Pre1++Pre2,St}; -cg_size_calc_2([{_,#b_literal{}=Sz}|T], Sum0, Fail, St0) -> - {Sum1,Pre0,St1} = cg_size_calc_2(T, Sum0, Fail, St0), - {Sum,Pre,St} = cg_size_add(Sum1, Sz, #b_literal{val=1}, Fail, St1), +cg_size_calc_2([{_,#b_literal{}=Sz}|T], Sum0, FailCtx, St0) -> + {Sum1,Pre0,St1} = cg_size_calc_2(T, Sum0, FailCtx, St0), + {Sum,Pre,St} = cg_size_add(Sum1, Sz, #b_literal{val=1}, FailCtx, St1), {Sum,Pre0++Pre,St}; -cg_size_calc_2([{_,#b_var{}=Sz}|T], Sum0, Fail, St0) -> - {Sum1,Pre0,St1} = cg_size_calc_2(T, Sum0, Fail, St0), - {Sum,Pre,St} = cg_size_add(Sum1, Sz, #b_literal{val=1}, Fail, St1), +cg_size_calc_2([{_,#b_var{}=Sz}|T], Sum0, FailCtx, St0) -> + {Sum1,Pre0,St1} = cg_size_calc_2(T, Sum0, FailCtx, St0), + {Sum,Pre,St} = cg_size_add(Sum1, Sz, #b_literal{val=1}, FailCtx, St1), {Sum,Pre0++Pre,St}; -cg_size_calc_2([{_,{_,_}=Bif}|T], Sum0, Fail, St0) -> - {Sum1,Pre0,St1} = cg_size_calc_2(T, Sum0, Fail, St0), - {BifDst,Pre1,St2} = cg_size_bif(Bif, Fail, St1), - {Sum,Pre2,St} = cg_size_add(Sum1, BifDst, #b_literal{val=1}, Fail, St2), +cg_size_calc_2([{_,{_,_}=Bif}|T], Sum0, FailCtx, St0) -> + {Sum1,Pre0,St1} = cg_size_calc_2(T, Sum0, FailCtx, St0), + {BifDst,Pre1,St2} = cg_size_bif(Bif, FailCtx, St1), + {Sum,Pre2,St} = cg_size_add(Sum1, BifDst, #b_literal{val=1}, FailCtx, St2), {Sum,Pre0++Pre1++Pre2,St}; -cg_size_calc_2([], Sum, _Fail, St) -> +cg_size_calc_2([], Sum, _FailCtx, St) -> {Sum,[],St}. -cg_size_bif(#b_var{}=Var, _Fail, St) -> +cg_size_bif(#b_var{}=Var, _FailCtx, St) -> {Var,[],St}; -cg_size_bif({Name,Src}, Fail, St0) -> +cg_size_bif({Name,Src}, FailCtx, St0) -> {Dst,St1} = new_ssa_var('@ssa_bif', St0), Bif = #b_set{op=Name,dst=Dst,args=[Src]}, - {TestIs,St} = make_cond_branch(succeeded, [Dst], Fail, St1), + {TestIs,St} = make_succeeded(Dst, FailCtx, St1), {Dst,[Bif|TestIs],St}. -cg_size_add(#b_literal{val=0}, Val, #b_literal{val=1}, _Fail, St) -> +cg_size_add(#b_literal{val=0}, Val, #b_literal{val=1}, _FailCtx, St) -> {Val,[],St}; -cg_size_add(A, B, Unit, Fail, St0) -> +cg_size_add(A, B, Unit, FailCtx, St0) -> {Dst,St1} = new_ssa_var('@ssa_sum', St0), - {TestIs,St} = make_cond_branch(succeeded, [Dst], Fail, St1), + {TestIs,St} = make_succeeded(Dst, FailCtx, St1), BsAdd = #b_set{op=bs_add,dst=Dst,args=[A,B,Unit]}, {Dst,[BsAdd|TestIs],St}. -cg_bin_put(Seg, Fail, St) -> - cg_bin_put_1(Seg, Fail, [], [], St). +cg_bin_put(Seg, FailCtx, St) -> + cg_bin_put_1(Seg, FailCtx, [], [], St). cg_bin_put_1(#k_bin_seg{size=Size0,unit=U,type=T,flags=Fs,seg=Src0,next=Next}, - Fail, Acc, SzCalcAcc, St0) -> + FailCtx, Acc, SzCalcAcc, St0) -> [Src,Size] = ssa_args([Src0,Size0], St0), NeedSize = bs_need_size(T), TypeArg = #b_literal{val=T}, @@ -1083,9 +1105,12 @@ cg_bin_put_1(#k_bin_seg{size=Size0,unit=U,type=T,flags=Fs,seg=Src0,next=Next}, true -> [TypeArg,Flags,Src,Size,Unit]; false -> [TypeArg,Flags,Src] end, - {Is,St} = make_cond_branch(bs_put, Args, Fail, St0), + %% bs_put has its own 'succeeded' logic, and should always jump directly to + %% the fail label regardless of whether it's in a catch or not. + {_, FailLbl} = FailCtx, + {Is,St} = make_cond_branch(bs_put, Args, FailLbl, St0), SzCalc = bin_size_calc(T, Src, Size, U), - cg_bin_put_1(Next, Fail, reverse(Is, Acc), [SzCalc|SzCalcAcc], St); + cg_bin_put_1(Next, FailCtx, reverse(Is, Acc), [SzCalc|SzCalcAcc], St); cg_bin_put_1(#k_bin_end{}, _, Acc, SzCalcAcc, St) -> SzCalc = fold_size_calc(SzCalcAcc, 0, []), {reverse(Acc),SzCalc,St}. diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl index 7a766623b0..f46cca1431 100644 --- a/lib/compiler/src/beam_ssa.erl +++ b/lib/compiler/src/beam_ssa.erl @@ -101,7 +101,7 @@ 'bs_match' | 'bs_put' | 'bs_start_match' | 'bs_test_tail' | 'bs_utf16_size' | 'bs_utf8_size' | 'build_stacktrace' | 'call' | 'catch_end' | - 'extract' | + 'extract' | 'exception_trampoline' | 'get_hd' | 'get_map_element' | 'get_tl' | 'get_tuple_element' | 'has_map_field' | 'is_nonempty_list' | 'is_tagged_tuple' | diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl index 7248aca5f3..7102f524d0 100644 --- a/lib/compiler/src/beam_ssa_codegen.erl +++ b/lib/compiler/src/beam_ssa_codegen.erl @@ -965,6 +965,12 @@ cg_block(Is0, Last, Next, St0) -> case Last of #cg_br{succ=Next,fail=Next} -> cg_block(Is0, none, St0); + #cg_br{succ=Same,fail=Same} when Same =:= ?BADARG_BLOCK -> + %% An expression in this block *always* throws an exception, so we + %% terminate it with an 'if_end' to make sure the validator knows + %% that the following instructions won't actually be reached. + {Is,St} = cg_block(Is0, none, St0), + {Is++[if_end],St}; #cg_br{succ=Same,fail=Same} -> {Fail,St1} = use_block_label(Same, St0), {Is,St} = cg_block(Is0, none, St1), diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 986be14e8a..f77eeecc94 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -901,6 +901,7 @@ cse_suitable(#b_set{}) -> false. -record(fs, {s=undefined :: 'undefined' | 'cleared', regs=#{} :: #{beam_ssa:b_var():=beam_ssa:b_var()}, + vars=cerl_sets:new() :: cerl_sets:set(), fail=none :: 'none' | beam_ssa:label(), non_guards :: gb_sets:set(beam_ssa:label()), bs :: beam_ssa:block_map() @@ -913,22 +914,39 @@ ssa_opt_float({#st{ssa=Linear0,cnt=Count0}=St, FuncDb}) -> {Linear,Count} = float_opt(Linear0, Count0, Fs), {St#st{ssa=Linear,cnt=Count}, FuncDb}. -float_blk_is_in_guard(#b_blk{last=#b_br{fail=F}}, #fs{non_guards=NonGuards}) -> - not gb_sets:is_member(F, NonGuards); -float_blk_is_in_guard(#b_blk{}, #fs{}) -> +%% The fconv instruction doesn't support jumping to a fail label, so we have to +%% skip this optimization if the fail block is a guard. +%% +%% We also skip the optimization in blocks that always fail, as it's both +%% difficult and pointless to rewrite them to use float ops. +float_can_optimize_blk(#b_blk{last=#b_br{bool=#b_var{},fail=F}}, + #fs{non_guards=NonGuards}) -> + gb_sets:is_member(F, NonGuards); +float_can_optimize_blk(#b_blk{}, #fs{}) -> false. +float_opt([{L,#b_blk{is=[#b_set{op=exception_trampoline,args=[Var]}]}=Blk0} | + Bs0], Count0, Fs) -> + %% If we've replaced a BIF with float operations, we'll have a lot of extra + %% blocks that jump to the same failure block, which may have a trampoline + %% that refers to the original operation. + %% + %% Since the point of the trampoline is to keep the BIF from being removed + %% by liveness optimization, we can discard it as the liveness pass leaves + %% floats alone. + Blk = case cerl_sets:is_element(Var, Fs#fs.vars) of + true -> Blk0#b_blk{is=[]}; + false -> Blk0 + end, + {Bs, Count} = float_opt(Bs0, Count0, Fs), + {[{L,Blk}|Bs],Count}; float_opt([{L,Blk}|Bs0], Count0, Fs) -> - case float_blk_is_in_guard(Blk, Fs) of + case float_can_optimize_blk(Blk, Fs) of true -> - %% This block is inside a guard. Don't do - %% any floating point optimizations. - {Bs,Count} = float_opt(Bs0, Count0, Fs), - {[{L,Blk}|Bs],Count}; + float_opt_1(L, Blk, Bs0, Count0, Fs); false -> - %% This block is not inside a guard. - %% We can do the optimization. - float_opt_1(L, Blk, Bs0, Count0, Fs) + {Bs,Count} = float_opt(Bs0, Count0, Fs), + {[{L,Blk}|Bs],Count} end; float_opt([], Count, _Fs) -> {[],Count}. @@ -1007,12 +1025,12 @@ float_maybe_flush(Blk0, #fs{s=cleared,fail=Fail,bs=Blocks}=Fs0, Count0) -> #b_blk{last=#b_br{bool=#b_var{},succ=Succ}=Br} = Blk0, %% If the success block starts with a floating point operation, we can - %% defer flushing to that block as long as it isn't a guard. + %% defer flushing to that block as long as it's suitable for optimization. #b_blk{is=Is} = SuccBlk = map_get(Succ, Blocks), - SuccIsGuard = float_blk_is_in_guard(SuccBlk, Fs0), + CanOptimizeSucc = float_can_optimize_blk(SuccBlk, Fs0), case Is of - [#b_set{anno=#{float_op:=_}}|_] when not SuccIsGuard -> + [#b_set{anno=#{float_op:=_}}|_] when CanOptimizeSucc -> %% No flush needed. {[],Blk0,Fs0,Count0}; _ -> @@ -1068,21 +1086,22 @@ float_opt_is([], Fs, _Count, _Acc) -> none. float_make_op(#b_set{op={bif,Op},dst=Dst,args=As0}=I0, - Ts, #fs{s=S,regs=Rs0}=Fs, Count0) -> + Ts, #fs{s=S,regs=Rs0,vars=Vs0}=Fs, Count0) -> {As1,Rs1,Count1} = float_load(As0, Ts, Rs0, Count0, []), {As,Is0} = unzip(As1), {Fr,Count2} = new_reg('@fr', Count1), FrDst = #b_var{name=Fr}, I = I0#b_set{op={float,Op},dst=FrDst,args=As}, + Vs = cerl_sets:add_element(Dst, Vs0), Rs = Rs1#{Dst=>FrDst}, Is = append(Is0) ++ [I], case S of undefined -> {Ignore,Count} = new_reg('@ssa_ignore', Count2), C = #b_set{op={float,clearerror},dst=#b_var{name=Ignore}}, - {[C|Is],Fs#fs{s=cleared,regs=Rs},Count}; + {[C|Is],Fs#fs{s=cleared,regs=Rs,vars=Vs},Count}; cleared -> - {Is,Fs#fs{regs=Rs},Count2} + {Is,Fs#fs{regs=Rs,vars=Vs},Count2} end. float_load([A|As], [T|Ts], Rs0, Count0, Acc) -> @@ -1211,34 +1230,31 @@ live_opt_is([#b_set{op=phi,dst=Dst}=I|Is], Live, Acc) -> false -> live_opt_is(Is, Live, Acc) end; -live_opt_is([#b_set{op=succeeded,dst=SuccDst=SuccDstVar, - args=[Dst]}=SuccI, - #b_set{dst=Dst}=I|Is], Live0, Acc) -> - case gb_sets:is_member(Dst, Live0) of - true -> - Live1 = gb_sets:add(Dst, Live0), - Live = gb_sets:delete_any(SuccDst, Live1), - live_opt_is([I|Is], Live, [SuccI|Acc]); - false -> - case live_opt_unused(I) of - {replace,NewI0} -> - NewI = NewI0#b_set{dst=SuccDstVar}, - live_opt_is([NewI|Is], Live0, Acc); - keep -> - case gb_sets:is_member(SuccDst, Live0) of - true -> - Live1 = gb_sets:add(Dst, Live0), - Live = gb_sets:delete(SuccDst, Live1), - live_opt_is([I|Is], Live, [SuccI|Acc]); - false -> - live_opt_is([I|Is], Live0, Acc) - end - end +live_opt_is([#b_set{op=succeeded,dst=SuccDst,args=[MapDst]}=SuccI, + #b_set{op=get_map_element,dst=MapDst}=MapI | Is], + Live0, Acc) -> + case {gb_sets:is_member(SuccDst, Live0), + gb_sets:is_member(MapDst, Live0)} of + {true, true} -> + Live = gb_sets:delete(SuccDst, Live0), + live_opt_is([MapI | Is], Live, [SuccI | Acc]); + {true, false} -> + %% 'get_map_element' is unused; replace 'succeeded' with + %% 'has_map_field' + NewI = MapI#b_set{op=has_map_field,dst=SuccDst}, + live_opt_is([NewI | Is], Live0, Acc); + {false, true} -> + %% 'succeeded' is unused (we know it will succeed); discard it and + %% keep 'get_map_element' + live_opt_is([MapI | Is], Live0, Acc); + {false, false} -> + live_opt_is(Is, Live0, Acc) end; live_opt_is([#b_set{dst=Dst}=I|Is], Live0, Acc) -> case gb_sets:is_member(Dst, Live0) of true -> - Live1 = gb_sets:union(Live0, gb_sets:from_ordset(beam_ssa:used(I))), + LiveUsed = gb_sets:from_ordset(beam_ssa:used(I)), + Live1 = gb_sets:union(Live0, LiveUsed), Live = gb_sets:delete(Dst, Live1), live_opt_is(Is, Live, [I|Acc]); false -> @@ -1246,17 +1262,14 @@ live_opt_is([#b_set{dst=Dst}=I|Is], Live0, Acc) -> true -> live_opt_is(Is, Live0, Acc); false -> - Live = gb_sets:union(Live0, gb_sets:from_ordset(beam_ssa:used(I))), + LiveUsed = gb_sets:from_ordset(beam_ssa:used(I)), + Live = gb_sets:union(Live0, LiveUsed), live_opt_is(Is, Live, [I|Acc]) end end; live_opt_is([], Live, Acc) -> {Acc,Live}. -live_opt_unused(#b_set{op=get_map_element}=Set) -> - {replace,Set#b_set{op=has_map_field}}; -live_opt_unused(_) -> keep. - %%% %%% Optimize binary matching. %%% @@ -1942,6 +1955,10 @@ verify_merge_is(_) -> is_merge_allowed(_, #b_blk{}, #b_blk{is=[#b_set{op=peek_message}|_]}) -> false; +is_merge_allowed(_, #b_blk{}, #b_blk{is=[#b_set{op=exception_trampoline}|_]}) -> + false; +is_merge_allowed(_, #b_blk{is=[#b_set{op=exception_trampoline}|_]}, #b_blk{}) -> + false; is_merge_allowed(L, #b_blk{last=#b_br{}}=Blk, #b_blk{}) -> %% The predecessor block must have exactly one successor (L) for %% the merge to be safe. @@ -2040,6 +2057,7 @@ unsuitable_1([{L,#b_blk{is=[#b_set{op=Op}|_]}}|Bs]) -> Unsuitable = case Op of bs_extract -> true; bs_put -> true; + exception_trampoline -> true; {float,_} -> true; landingpad -> true; peek_message -> true; @@ -2248,6 +2266,8 @@ non_guards(Linear) -> non_guards_1([{L,#b_blk{is=Is}}|Bs]) -> case Is of + [#b_set{op=exception_trampoline}|_] -> + [L | non_guards_1(Bs)]; [#b_set{op=landingpad}|_] -> [L | non_guards_1(Bs)]; _ -> diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl index a5fcb91cc0..ee55d55861 100644 --- a/lib/compiler/src/beam_ssa_pre_codegen.erl +++ b/lib/compiler/src/beam_ssa_pre_codegen.erl @@ -120,6 +120,7 @@ passes(Opts) -> %% Preliminaries. ?PASS(fix_bs), + ?PASS(exception_trampolines), ?PASS(sanitize), ?PASS(match_fail_instructions), case FixTuples of @@ -693,6 +694,44 @@ legacy_bs_is([I|Is], Last, IsYreg, Count, Copies, Acc) -> legacy_bs_is([], _Last, _IsYreg, Count, Copies, Acc) -> {reverse(Acc),Count,Copies}. +%% exception_trampolines(St0) -> St. +%% +%% Removes the "exception trampolines" that were added to prevent exceptions +%% from being optimized away. + +exception_trampolines(#st{ssa=Blocks0}=St) -> + RPO = reverse(beam_ssa:rpo(Blocks0)), + Blocks = et_1(RPO, #{}, Blocks0), + St#st{ssa=Blocks}. + +et_1([L | Ls], Trampolines, Blocks) -> + #{ L := #b_blk{is=Is,last=Last0}=Block0 } = Blocks, + case {Is, Last0} of + {[#b_set{op=exception_trampoline}], #b_br{succ=Succ}} -> + et_1(Ls, Trampolines#{ L => Succ }, maps:remove(L, Blocks)); + {_, #b_br{succ=Same,fail=Same}} when Same =:= ?BADARG_BLOCK -> + %% The "badarg block" is just a marker saying that we should raise + %% an exception (= {f,0}) instead of jumping to a particular fail + %% block. Since it's not a reachable block we can't allow + %% unconditional jumps to it except through a trampoline. + error({illegal_jump_to_badarg_block, L}); + {_, #b_br{succ=Succ0,fail=Fail0}} -> + Succ = maps:get(Succ0, Trampolines, Succ0), + Fail = maps:get(Fail0, Trampolines, Fail0), + if + Succ =/= Succ0; Fail =/= Fail0 -> + Last = Last0#b_br{succ=Succ,fail=Fail}, + Block = Block0#b_blk{last=Last}, + et_1(Ls, Trampolines, Blocks#{ L := Block }); + Succ =:= Succ0, Fail =:= Fail0 -> + et_1(Ls, Trampolines, Blocks) + end; + {_, _} -> + et_1(Ls, Trampolines, Blocks) + end; +et_1([], _Trampolines, Blocks) -> + Blocks. + %% sanitize(St0) -> St. %% Remove constructs that can cause problems later: %% -- cgit v1.2.3 From ec35aa92f49dedf4b25a78c6b8d56d629db6642d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Tue, 25 Jun 2019 09:01:01 +0200 Subject: beam_ssa_type: Skip impossible branches Whenever there's a type conflict during type inference we know that the branch will not be taken. Previously we'd go down the branch with garbage type information which would crash in some cases. There's no test case for the crashes because the ones I've found require union types to happen, and we already have good coverage once they're in place. --- lib/compiler/src/beam_ssa_type.erl | 172 ++++++++++++++++++++++--------------- 1 file changed, 104 insertions(+), 68 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index d88f43cb5c..f87acdb500 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -174,8 +174,8 @@ opt_1(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, {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), + 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]); {no_return,Ret,Is,Ds,Fdb,Sub} -> @@ -805,63 +805,86 @@ 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, + Ts0, D0) -> + Ts = 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. + maps:remove(Bool, Ts0); + false -> + Ts0 + end, + case infer_types_br(Bool, Ts, 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, UsedOnce, Ts, [], D0), + + FailTs = case UsedOnce of + true -> maps:remove(V, Ts); + false -> subtract_sw_list(V, List0, Ts) + end, + + case FailTs of + none -> + [{_, 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([get_type(Arg, Ts) | D0#d.ret_type]), + D0#d{ret_type=[RetType]} + end, + {Last, D}. + +update_switch([{Val, Lbl}=Sw | List], V, UsedOnce, Ts, Acc, D0) -> + case infer_types_switch(V, Val, Ts, D0) of + none -> + update_switch(List, V, UsedOnce, Ts, Acc, D0); + SwTs0 -> + SwTs = case UsedOnce of + true -> maps:remove(V, SwTs0); + false -> SwTs0 + end, + D = update_successor(Lbl, SwTs, D0), + update_switch(List, V, UsedOnce, Ts, [Sw | Acc], D) + end; +update_switch([], _V, _UsedOnce, _Ts, Acc, D) -> + {Acc, D}. subtract_sw_list(V, List, Ts) -> - Ts#{ V := sub_sw_list_1(get_type(V, Ts), List, Ts) }. + case sub_sw_list_1(get_type(V, Ts), List, Ts) of + none -> none; + Type -> Ts#{ V := Type } + end. sub_sw_list_1(Type, [{Val,_}|T], Ts) -> ValType = get_type(Val, Ts), @@ -869,16 +892,6 @@ sub_sw_list_1(Type, [{Val,_}|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, %% so there is no need to update the type information. That @@ -1286,12 +1299,32 @@ infer_types_br(#b_var{}=V, Ts, #d{ds=Ds}) -> NegTypes1 = [P || {_,T}=P <- EqTypes, beam_types:is_singleton_type(T)], PosTypes = EqTypes ++ PosTypes0, - SuccTs = meet_types(PosTypes, Ts), + SuccTs1 = meet_types(PosTypes, Ts), NegTypes = NegTypes0 ++ NegTypes1, - FailTs = subtract_types(NegTypes, Ts), + FailTs1 = subtract_types(NegTypes, Ts), - {SuccTs,FailTs}. + SuccTs = infer_br_value(V, Ts, true, SuccTs1), + FailTs = infer_br_value(V, Ts, false, FailTs1), + + {SuccTs, FailTs}. + +infer_br_value(_V, _OldTs, _Bool, none) -> + none; +infer_br_value(V, OldTs, Bool, NewTs) -> + case OldTs of + #{ V := T } -> + 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; + #{} -> + %% V is only used in this branch; don't propagate its type. + NewTs + end. infer_types_switch(V, Lit, Ts, #d{ds=Ds}) -> Types = infer_eq_type({bif,'=:='}, [V, Lit], Ts, Ds), @@ -1418,6 +1451,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; @@ -1426,7 +1460,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. + -- cgit v1.2.3 From a10fb1edf471602be01bd5b4c1f019cc5534b9f5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Fri, 28 Jun 2019 09:14:43 +0200 Subject: compiler: Explain and rename ?BADARG_BLOCK --- lib/compiler/src/beam_kernel_to_ssa.erl | 3 ++- lib/compiler/src/beam_ssa.hrl | 12 ++++++++++-- lib/compiler/src/beam_ssa_bsm.erl | 6 +++--- lib/compiler/src/beam_ssa_codegen.erl | 18 +++++++++--------- lib/compiler/src/beam_ssa_opt.erl | 2 +- lib/compiler/src/beam_ssa_pre_codegen.erl | 16 ++++++++-------- lib/compiler/src/beam_ssa_share.erl | 4 ++-- lib/compiler/src/beam_ssa_type.erl | 6 +++--- 8 files changed, 38 insertions(+), 29 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_kernel_to_ssa.erl b/lib/compiler/src/beam_kernel_to_ssa.erl index b2d824b648..474cb1a851 100644 --- a/lib/compiler/src/beam_kernel_to_ssa.erl +++ b/lib/compiler/src/beam_kernel_to_ssa.erl @@ -34,7 +34,7 @@ -type label() :: beam_ssa:label(). %% Main codegen structure. --record(cg, {lcount=1 :: label(), %Label counter +-record(cg, {lcount=1 :: label(), %Label counter bfail=1 :: label(), catch_label=none :: 'none' | label(), vars=#{} :: map(), %Defined variables. @@ -83,6 +83,7 @@ function(#k_fdef{anno=Anno0,func=Name,arity=Arity, cg_fun(Ke, St0) -> {UltimateFail,FailIs,St1} = make_failure(badarg, St0), + ?EXCEPTION_BLOCK = UltimateFail, %Assertion. St2 = St1#cg{bfail=UltimateFail,ultimate_failure=UltimateFail}, {B,St} = cg(Ke, St2), Asm = [{label,0}|B++FailIs], diff --git a/lib/compiler/src/beam_ssa.hrl b/lib/compiler/src/beam_ssa.hrl index fa76b08453..509a94135e 100644 --- a/lib/compiler/src/beam_ssa.hrl +++ b/lib/compiler/src/beam_ssa.hrl @@ -62,5 +62,13 @@ -record(b_local, {name :: beam_ssa:b_literal(), arity :: non_neg_integer()}). -%% If this block exists, it calls erlang:error(badarg). --define(BADARG_BLOCK, 1). +%% This is a psuedo-block used to express that certain instructions and BIFs +%% throw exceptions on failure. The code generator rewrites all branches to +%% this block to {f,0} which causes the instruction to throw an exception +%% instead of branching. +%% +%% Since this is not an ordinary block, it's illegal to merge it with other +%% blocks, and jumps are only valid when we know that an exception will be +%% thrown by the operation that branches here; the *block itself* does not +%% throw an exception. +-define(EXCEPTION_BLOCK, 1). diff --git a/lib/compiler/src/beam_ssa_bsm.erl b/lib/compiler/src/beam_ssa_bsm.erl index 927a06edbf..7a8dc127d7 100644 --- a/lib/compiler/src/beam_ssa_bsm.erl +++ b/lib/compiler/src/beam_ssa_bsm.erl @@ -684,9 +684,9 @@ aca_copy_successors(Lbl0, Blocks0, Counter0) -> Lbl = maps:get(Lbl0, BRs), {Lbl, Blocks, Counter}. -aca_cs_build_brs([?BADARG_BLOCK=Lbl | Path], Counter, Acc) -> - %% ?BADARG_BLOCK is a marker and not an actual block, so renaming it will - %% break exception handling. +aca_cs_build_brs([?EXCEPTION_BLOCK=Lbl | Path], Counter, Acc) -> + %% ?EXCEPTION_BLOCK is a marker and not an actual block, so renaming it + %% will break exception handling. aca_cs_build_brs(Path, Counter, Acc#{ Lbl => Lbl }); aca_cs_build_brs([Lbl | Path], Counter0, Acc) -> aca_cs_build_brs(Path, Counter0 + 1, Acc#{ Lbl => Counter0 }); diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl index 7102f524d0..10c3419314 100644 --- a/lib/compiler/src/beam_ssa_codegen.erl +++ b/lib/compiler/src/beam_ssa_codegen.erl @@ -115,14 +115,14 @@ functions(Forms, AtomMod) -> function(#b_function{anno=Anno,bs=Blocks}, AtomMod, St0) -> #{func_info:={_,Name,Arity}} = Anno, try - assert_badarg_block(Blocks), %Assertion. + assert_exception_block(Blocks), %Assertion. Regs = maps:get(registers, Anno), St1 = St0#cg{labels=#{},used_labels=gb_sets:empty(), regs=Regs}, {Fi,St2} = new_label(St1), %FuncInfo label {Entry,St3} = local_func_label(Name, Arity, St2), {Ult,St4} = new_label(St3), %Ultimate failure - Labels = (St4#cg.labels)#{0=>Entry,?BADARG_BLOCK=>0}, + Labels = (St4#cg.labels)#{0=>Entry,?EXCEPTION_BLOCK=>0}, St5 = St4#cg{labels=Labels,used_labels=gb_sets:singleton(Entry), ultimate_fail=Ult}, {Body,St} = cg_fun(Blocks, St5#cg{fc_label=Fi}), @@ -138,10 +138,10 @@ function(#b_function{anno=Anno,bs=Blocks}, AtomMod, St0) -> erlang:raise(Class, Error, Stack) end. -assert_badarg_block(Blocks) -> - %% Assertion: ?BADARG_BLOCK must be the call erlang:error(badarg). +assert_exception_block(Blocks) -> + %% Assertion: ?EXCEPTION_BLOCK must be a call erlang:error(badarg). case Blocks of - #{?BADARG_BLOCK:=Blk} -> + #{?EXCEPTION_BLOCK:=Blk} -> #b_blk{is=[#b_set{op=call,dst=Ret, args=[#b_remote{mod=#b_literal{val=erlang}, name=#b_literal{val=error}}, @@ -149,7 +149,7 @@ assert_badarg_block(Blocks) -> last=#b_ret{arg=Ret}} = Blk, ok; #{} -> - %% ?BADARG_BLOCK has been removed because it was never used. + %% ?EXCEPTION_BLOCK has been removed because it was never used. ok end. @@ -631,7 +631,7 @@ liveness_get(S, LiveMap) -> end. liveness_successors(Terminator) -> - successors(Terminator) -- [?BADARG_BLOCK]. + successors(Terminator) -- [?EXCEPTION_BLOCK]. liveness_is([#cg_alloc{}=I0|Is], Regs, Live, Acc) -> I = I0#cg_alloc{live=num_live(Live, Regs)}, @@ -965,7 +965,7 @@ cg_block(Is0, Last, Next, St0) -> case Last of #cg_br{succ=Next,fail=Next} -> cg_block(Is0, none, St0); - #cg_br{succ=Same,fail=Same} when Same =:= ?BADARG_BLOCK -> + #cg_br{succ=Same,fail=Same} when Same =:= ?EXCEPTION_BLOCK -> %% An expression in this block *always* throws an exception, so we %% terminate it with an 'if_end' to make sure the validator knows %% that the following instructions won't actually be reached. @@ -1839,7 +1839,7 @@ linearize(Blocks) -> Linear = beam_ssa:linearize(Blocks), linearize_1(Linear, Blocks). -linearize_1([{?BADARG_BLOCK,_}|Ls], Blocks) -> +linearize_1([{?EXCEPTION_BLOCK,_}|Ls], Blocks) -> linearize_1(Ls, Blocks); linearize_1([{L,Block0}|Ls], Blocks) -> Block = translate_block(L, Block0, Blocks), diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index f77eeecc94..a9f8daaada 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -2274,7 +2274,7 @@ non_guards_1([{L,#b_blk{is=Is}}|Bs]) -> non_guards_1(Bs) end; non_guards_1([]) -> - [?BADARG_BLOCK]. + [?EXCEPTION_BLOCK]. rel2fam(S0) -> S1 = sofs:relation(S0), diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl index ee55d55861..d3cedc3617 100644 --- a/lib/compiler/src/beam_ssa_pre_codegen.erl +++ b/lib/compiler/src/beam_ssa_pre_codegen.erl @@ -709,12 +709,12 @@ et_1([L | Ls], Trampolines, Blocks) -> case {Is, Last0} of {[#b_set{op=exception_trampoline}], #b_br{succ=Succ}} -> et_1(Ls, Trampolines#{ L => Succ }, maps:remove(L, Blocks)); - {_, #b_br{succ=Same,fail=Same}} when Same =:= ?BADARG_BLOCK -> - %% The "badarg block" is just a marker saying that we should raise + {_, #b_br{succ=Same,fail=Same}} when Same =:= ?EXCEPTION_BLOCK -> + %% The exception block is just a marker saying that we should raise %% an exception (= {f,0}) instead of jumping to a particular fail %% block. Since it's not a reachable block we can't allow %% unconditional jumps to it except through a trampoline. - error({illegal_jump_to_badarg_block, L}); + error({illegal_jump_to_exception_block, L}); {_, #b_br{succ=Succ0,fail=Fail0}} -> Succ = maps:get(Succ0, Trampolines, Succ0), Fail = maps:get(Fail0, Trampolines, Fail0), @@ -1338,10 +1338,10 @@ place_frame_here(L, Blocks, Doms, Frames) -> Descendants = beam_ssa:rpo([L], Blocks), PhiPredecessors = phi_predecessors(L, Blocks), MustDominate = ordsets:from_list(PhiPredecessors ++ Descendants), - Dominates = all(fun(?BADARG_BLOCK) -> + Dominates = all(fun(?EXCEPTION_BLOCK) -> %% This block defines no variables and calls %% erlang:error(badarg). It does not matter - %% whether L dominates ?BADARG_BLOCK or not; + %% whether L dominates ?EXCEPTION_BLOCK or not; %% it is still safe to put the frame in L. true; (Bl) -> @@ -1823,7 +1823,7 @@ collect_yregs([], Yregs) -> Yregs. copy_retval_2([L|Ls], Yregs, Copy0, Blocks0, Count0) -> #b_blk{is=Is0,last=Last} = Blk = map_get(L, Blocks0), RC = case {Last,Ls} of - {#b_br{succ=Succ,fail=?BADARG_BLOCK},[Succ|_]} -> + {#b_br{succ=Succ,fail=?EXCEPTION_BLOCK},[Succ|_]} -> true; {_,_} -> false @@ -2562,9 +2562,9 @@ reserve_xregs_is([], Res, Xs, _Used) -> {Res,Xs}. %% Pick up register hints from the successors of this blocks. -reserve_terminator(_L, _Is, #b_br{bool=#b_var{},succ=Succ,fail=?BADARG_BLOCK}, +reserve_terminator(_L, _Is, #b_br{bool=#b_var{},succ=Succ,fail=?EXCEPTION_BLOCK}, _Blocks, XsMap, _Res) -> - %% We know that no variables are used at ?BADARG_BLOCK, so + %% We know that no variables are used at ?EXCEPTION_BLOCK, so %% any register hints from the success blocks are safe to use. map_get(Succ, XsMap); reserve_terminator(L, Is, #b_br{bool=#b_var{},succ=Succ,fail=Fail}, diff --git a/lib/compiler/src/beam_ssa_share.erl b/lib/compiler/src/beam_ssa_share.erl index 426efa2cc9..85ab088d14 100644 --- a/lib/compiler/src/beam_ssa_share.erl +++ b/lib/compiler/src/beam_ssa_share.erl @@ -117,8 +117,8 @@ share_terminator(_Last, _Blocks) -> none. %% possible if the blocks are not equivalent, as that is the common %% case. -are_equivalent(_Succ, _, ?BADARG_BLOCK, _, _Blocks) -> - %% ?BADARG_BLOCK is special. Sharing could be incorrect. +are_equivalent(_Succ, _, ?EXCEPTION_BLOCK, _, _Blocks) -> + %% ?EXCEPTION_BLOCK is special. Sharing could be incorrect. false; are_equivalent(_Succ, #b_blk{is=Is1,last=#b_ret{arg=RetVal1}=Ret1}, _Fail, #b_blk{is=Is2,last=#b_ret{arg=RetVal2}=Ret2}, _Blocks) -> diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index f87acdb500..5e7b54a064 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -108,7 +108,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, []), @@ -892,8 +892,8 @@ sub_sw_list_1(Type, [{Val,_}|T], Ts) -> sub_sw_list_1(Type, [], _Ts) -> Type. -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; -- cgit v1.2.3 From bc321b89c38096a4a6148dccc41e2678d8e9feda Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Mon, 17 Jun 2019 18:01:00 +0200 Subject: compiler: Introduce union types Consider the type `{ok, #record{}} | {error,atom()}`; in our current type representation this will be flattened down to `{ok | error, #record{} | atom()}`, which is fairly useful but has no connection between the elements. Testing that the first element is 'error' lets us skip checking that it's 'ok' on failure, but the second element is still `#record{} | atom()` and we'll eventually need to test that, even though it can only be a `#record{}`. Another example would be `false | {value, term()}`, the return value of lists:keyfind/3, which we're forced to flatten to `any` since there's nothing in common between an atom and a tuple. Union types let us express these types directly, greatly improving type optimization. --- lib/compiler/src/beam_call_types.erl | 2 +- lib/compiler/src/beam_ssa_type.erl | 142 +++--- lib/compiler/src/beam_types.erl | 850 +++++++++++++++++++++++++---------- lib/compiler/src/beam_types.hrl | 29 +- lib/compiler/src/beam_validator.erl | 12 +- 5 files changed, 711 insertions(+), 324 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_call_types.erl b/lib/compiler/src/beam_call_types.erl index 2aba6f7961..a94a7caa74 100644 --- a/lib/compiler/src/beam_call_types.erl +++ b/lib/compiler/src/beam_call_types.erl @@ -37,7 +37,7 @@ -spec types(Mod, Func, ArgTypes) -> {RetType, ArgTypes, CanSubtract} when Mod :: atom(), Func :: atom(), - ArgTypes :: [type()], + ArgTypes :: [normal_type()], RetType :: type(), CanSubtract :: boolean(). diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 5e7b54a064..f4fc33bf4f 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -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) -> @@ -388,9 +389,9 @@ opt_call(#b_set{dst=Dst,args=[#b_local{}=Callee|Args]}=I0, D, Ts0, Ds0, Fdb0) -> %% 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 @@ -443,7 +444,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 +487,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 +498,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 +527,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 +538,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 +560,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,7 +597,7 @@ 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 + case normalized_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 @@ -605,7 +610,7 @@ simplify(#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=N}]}=I, Ts) -> 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 +618,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]}; @@ -631,7 +636,7 @@ simplify(I, _Ts) -> I. 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 +654,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 +681,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 +698,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 +731,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 +772,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 +802,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); @@ -860,7 +866,7 @@ update_successors(#b_ret{arg=Arg}=Last, Ts, D0) -> %% type. D0; #{} -> - RetType = beam_types:join([get_type(Arg, Ts) | D0#d.ret_type]), + RetType = beam_types:join([raw_type(Arg, Ts) | D0#d.ret_type]), D0#d{ret_type=[RetType]} end, {Last, D}. @@ -881,13 +887,13 @@ update_switch([], _V, _UsedOnce, _Ts, Acc, D) -> {Acc, D}. subtract_sw_list(V, List, Ts) -> - case sub_sw_list_1(get_type(V, Ts), List, Ts) of + case sub_sw_list_1(raw_type(V, Ts), List, Ts) of none -> none; Type -> Ts#{ V := Type } 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. @@ -911,10 +917,11 @@ update_types(#b_set{op=Op,dst=Dst,args=Args}, Ts, Ds) -> Ts#{Dst=>T}. type(phi, Args, Ts, _Ds) -> - Types = [get_type(A, Ts) || {A,_} <- Args], + 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)), + ArgTypes = normalized_types(Args, Ts), + {RetType, _, _} = beam_call_types:types(erlang, Bif, ArgTypes), RetType; type(bs_init, _Args, _Ts, _Ds) -> #t_bitstring{}; @@ -927,10 +934,11 @@ type(bs_get_tail, _Args, _Ts, _Ds) -> #t_bitstring{}; 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)), + 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), + #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); @@ -946,7 +954,7 @@ type(put_list, _Args, _Ts, _Ds) -> cons; type(put_tuple, Args, 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), @@ -954,7 +962,7 @@ type(put_tuple, Args, Ts, _Ds) -> type(succeeded, [#b_var{}=Src], Ts, Ds) -> case maps:get(Src, Ds) of #b_set{op={bif,Bif},args=BifArgs} -> - Types = get_types(BifArgs, Ts), + Types = normalized_types(BifArgs, Ts), case {Bif,Types} of {BoolOp,[T1,T2]} when BoolOp =:= 'and'; BoolOp =:= 'or' -> BothBool = beam_types:is_boolean_type(T1) andalso @@ -1151,7 +1159,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 @@ -1181,7 +1189,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); @@ -1249,16 +1257,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]. + +normalized_type(V, Ts) -> + beam_types:normalize(raw_type(V, Ts)). -get_types(Values, Ts) -> - [get_type(Val, Ts) || Val <- Values]. --spec get_type(beam_ssa:value(), type_db()) -> type(). +-spec raw_type(beam_ssa:value(), type_db()) -> type(). -get_type(#b_var{}=V, Ts) -> - #{V:=T} = Ts, - T; -get_type(#b_literal{val=Val}, _Ts) -> - beam_types:make_type_from_value(Val). +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 @@ -1332,14 +1342,14 @@ infer_types_switch(V, Lit, Ts, #d{ds=Ds}) -> infer_eq_type({bif,'=:='}, [#b_var{}=Src,#b_literal{}=Lit], Ts, Ds) -> Def = maps:get(Src, Ds), - Type = get_type(Lit, Ts), + Type = raw_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), + Type0 = raw_type(Arg0, Ts), + Type1 = raw_type(Arg1, Ts), Type = beam_types:meet(Type0, Type1), [{V,MeetType} || {V,OrigType,MeetType} <- @@ -1355,7 +1365,7 @@ 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, #{}), #{}), + Es = beam_types:set_element_type(Index, raw_type(Lit, #{}), #{}), [{Tuple,#t_tuple{size=Index,elements=Es}}]; infer_eq_lit(_, _) -> []. @@ -1368,7 +1378,7 @@ infer_type(succeeded, [#b_var{}=Src], Ts, Ds) -> %% 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]}; infer_type(is_nonempty_list, [#b_var{}=Src], _Ts, _Ds) -> @@ -1408,7 +1418,7 @@ infer_type(_Op, _Args, _Ts, _Ds) -> {[], []}. infer_success_type({bif,Op}, Args, Ts, _Ds) -> - ArgTypes = get_types(Args, Ts), + ArgTypes = normalized_types(Args, Ts), {_, PosTypes0, CanSubtract} = beam_call_types:types(erlang, Op, ArgTypes), PosTypes = [T || {#b_var{},_}=T <- zip(Args, PosTypes0)], diff --git a/lib/compiler/src/beam_types.erl b/lib/compiler/src/beam_types.erl index 4f8ba0ada5..821ccd31bb 100644 --- a/lib/compiler/src/beam_types.erl +++ b/lib/compiler/src/beam_types.erl @@ -22,14 +22,14 @@ -include("beam_types.hrl"). --import(lists, [foldl/3]). +-import(lists, [foldl/3, reverse/1, reverse/2]). -export([meet/1, meet/2, join/1, join/2, subtract/2]). -export([get_singleton_value/1, - get_tuple_size/1, is_singleton_type/1, - is_boolean_type/1]). + is_boolean_type/1, + normalize/1]). -export([get_element_type/2, set_element_type/3]). @@ -38,223 +38,276 @@ -export([make_atom/1, make_boolean/0, make_integer/1, - make_integer/2, - make_tuple/2, - make_tuple/3]). + make_integer/2]). -%% Return the "join" of Type1 and Type2. The join is a more general -%% type than Type1 and Type2. For example: +-define(IS_LIST_TYPE(N), + N =:= list orelse + N =:= cons orelse + N =:= nil). + +-define(IS_NUMBER_TYPE(N), + N =:= number orelse + N =:= float orelse + is_record(N, t_integer)). + +-define(TUPLE_SET_LIMIT, 20). + +%% Folds meet/2 over a list. + +-spec meet([type()]) -> type(). + +meet([T1, T2 | Ts]) -> + meet([meet(T1, T2) | Ts]); +meet([T]) -> T. + +%% Return the "meet" of Type1 and Type2, which is more general than Type1 and +%% Type2. This is identical to glb/2 but can operate on and produce unions. %% -%% join(#t_integer{elements=any}, #t_integer=elements={0,3}}) -> -%% #t_integer{} +%% A = #t_union{list=nil, number=[number], other=[#t_map{}]} +%% B = #t_union{number=[#t_integer{}], other=[#t_map{}]} %% -%% The join for two different types result in 'any', which is -%% the top element for our type lattice: +%% meet(A, B) -> +%% #t_union{number=[#t_integer{}], other=[#t_map{}]} %% -%% join(#t_integer{}, #t_map{}) -> any +%% The meet of two different types result in 'none', which is the bottom +%% element for our type lattice: +%% +%% meet(#t_integer{}, #t_map{}) -> none --spec join(type(), type()) -> type(). +-spec meet(type(), type()) -> type(). -join(T, T) -> +meet(T, T) -> verified_type(T); -join(none, T) -> +meet(any, T) -> verified_type(T); -join(T, none) -> +meet(T, any) -> 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} +meet(#t_union{}=A, B) -> + meet_unions(A, B); +meet(A, #t_union{}=B) -> + meet_unions(B, A); +meet(A, B) -> + glb(A, B). + +meet_unions(#t_union{atom=AtomA,list=ListA,number=NumberA, + tuple_set=TSetA,other=OtherA}, + #t_union{atom=AtomB,list=ListB,number=NumberB, + tuple_set=TSetB,other=OtherB}) -> + Union = #t_union{atom=glb(AtomA, AtomB), + list=glb(ListA, ListB), + number=glb(NumberA, NumberB), + tuple_set=meet_tuple_sets(TSetA, TSetB), + other=glb(OtherA, OtherB)}, + shrink_union(Union); +meet_unions(#t_union{atom=AtomA}, #t_atom{}=B) -> + case glb(AtomA, B) of + none -> none; + Atom -> Atom end; -join(#t_atom{elements=any}=T, #t_atom{elements=[_|_]}) -> T; -join(#t_atom{elements=[_|_]}, #t_atom{elements=any}=T) -> T; -join(#t_bitstring{unit=U1}, #t_bitstring{unit=U2}) -> - #t_bitstring{unit=gcd(U1, U2)}; -join(#t_fun{}, #t_fun{}) -> - #t_fun{}; -join(#t_integer{elements={MinA,MaxA}}, - #t_integer{elements={MinB,MaxB}}) -> - #t_integer{elements={min(MinA,MinB),max(MaxA,MaxB)}}; -join(#t_bs_context{slots=SlotsA,valid=ValidA}, - #t_bs_context{slots=SlotsB,valid=ValidB}) -> - #t_bs_context{slots=min(SlotsA, SlotsB), - valid=ValidA band ValidB}; -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=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. +meet_unions(#t_union{number=NumberA}, B) when ?IS_NUMBER_TYPE(B) -> + case glb(NumberA, B) of + none -> none; + Number -> Number + end; +meet_unions(#t_union{list=ListA}, B) when ?IS_LIST_TYPE(B) -> + case glb(ListA, B) of + none -> none; + List -> List + end; +meet_unions(#t_union{tuple_set=Tuples}, #t_tuple{}=B) -> + Set = meet_tuple_sets(Tuples, new_tuple_set(B)), + shrink_union(#t_union{tuple_set=Set}); +meet_unions(#t_union{other=OtherA}, OtherB) -> + case glb(OtherA, OtherB) of + none -> none; + Other -> Other + end. -join_tuple_elements(MinSize, EsA, EsB) -> - Es0 = join_elements(EsA, EsB), - maps:filter(fun(Index, _Type) -> Index =< MinSize end, Es0). +meet_tuple_sets(none, _) -> + none; +meet_tuple_sets(_, none) -> + none; +meet_tuple_sets(#t_tuple{}=A, #t_tuple{}=B) -> + new_tuple_set(glb(A, B)); +meet_tuple_sets(#t_tuple{}=Tuple, Records) -> + mts_tuple(Records, Tuple, []); +meet_tuple_sets(Records, #t_tuple{}=Tuple) -> + meet_tuple_sets(Tuple, Records); +meet_tuple_sets(RecordsA, RecordsB) -> + mts_records(RecordsA, RecordsB). + +mts_tuple([{Key, Type} | Records], Tuple, Acc) -> + case glb(Type, Tuple) of + none -> mts_tuple(Records, Tuple, Acc); + T -> mts_tuple(Records, Tuple, [{Key, T} | Acc]) + end; +mts_tuple([], _Tuple, [_|_]=Acc) -> + reverse(Acc); +mts_tuple([], _Tuple, []) -> + none. -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, #{}). +mts_records(RecordsA, RecordsB) -> + mts_records(RecordsA, RecordsB, []). -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) +mts_records([{Key, A} | RsA], [{Key, B} | RsB], Acc) -> + case glb(A, B) of + none -> mts_records(RsA, RsB, Acc); + T -> mts_records(RsA, RsB, [{Key, T} | Acc]) end; -join_elements_1([], _Es1, _Es2, Acc) -> - Acc. +mts_records([{KeyA, _} | _ ]=RsA, [{KeyB, _} | RsB], Acc) when KeyA > KeyB -> + mts_records(RsA, RsB, Acc); +mts_records([{KeyA, _} | RsA], [{KeyB, _} | _] = RsB, Acc) when KeyA < KeyB -> + mts_records(RsA, RsB, Acc); +mts_records(_RsA, [], [_|_]=Acc) -> + reverse(Acc); +mts_records([], _RsB, [_|_]=Acc) -> + reverse(Acc); +mts_records(_RsA, _RsB, []) -> + none. -gcd(A, B) -> - case A rem B of - 0 -> B; - X -> gcd(B, X) - end. +%% Folds join/2 over a list. -%% Joins all the given types into a single type. -spec join([type()]) -> type(). -join([T1,T2|Ts]) -> - join([join(T1, T2)|Ts]); +join([T1, T2| Ts]) -> + join([join(T1, T2) | Ts]); join([T]) -> T. -%% 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: +%% Return the "join" of Type1 and Type2, which is more general than Type1 and +%% Type2. This is identical to lub/2 but can operate on and produce unions. %% -%% meet(#t_integer{}, #t_map{}) -> none +%% join(#t_integer{}, #t_map{}) -> #t_union{number=[#t_integer{}], +%% other=[#t_map{}]} --spec meet(type(), type()) -> type(). +-spec join(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} +join(T, T) -> T; +join(_T, any) -> any; +join(any, _T) -> any; +join(T, none) -> T; +join(none, T) -> T; + +join(#t_union{}=A, B) -> + join_unions(A, B); +join(A, #t_union{}=B) -> + join_unions(B, A); + +%% Union creation... +join(#t_atom{}=A, #t_atom{}=B) -> + lub(A, B); +join(#t_atom{}=A, B) when ?IS_LIST_TYPE(B) -> + #t_union{atom=A,list=B}; +join(#t_atom{}=A, B) when ?IS_NUMBER_TYPE(B) -> + #t_union{atom=A,number=B}; +join(#t_atom{}=A, #t_tuple{}=B) -> + #t_union{atom=A,tuple_set=new_tuple_set(B)}; +join(#t_atom{}=A, B) -> + #t_union{atom=A,other=B}; +join(A, #t_atom{}=B) -> + join(B, A); + +join(A, B) when ?IS_LIST_TYPE(A), ?IS_LIST_TYPE(B) -> + lub(A, B); +join(A, B) when ?IS_LIST_TYPE(A), ?IS_NUMBER_TYPE(B) -> + #t_union{list=A,number=B}; +join(A, #t_tuple{}=B) when ?IS_LIST_TYPE(A) -> + #t_union{list=A,tuple_set=new_tuple_set(B)}; +join(A, B) when ?IS_LIST_TYPE(A) -> + #t_union{list=A,other=B}; +join(A, B) when ?IS_LIST_TYPE(B) -> + join(B, A); + +join(A, B) when ?IS_NUMBER_TYPE(A), ?IS_NUMBER_TYPE(B) -> + lub(A, B); +join(A, #t_tuple{}=B) when ?IS_NUMBER_TYPE(A) -> + #t_union{number=A,tuple_set=new_tuple_set(B)}; +join(A, B) when ?IS_NUMBER_TYPE(A) -> + #t_union{number=A,other=B}; +join(A, B) when ?IS_NUMBER_TYPE(B) -> + join(B, A); + +join(#t_tuple{}=A, #t_tuple{}=B) -> + case {record_key(A), record_key(B)} of + {Same, Same} -> + lub(A, B); + {none, _Key} -> + lub(A, B); + {_Key, none} -> + lub(A, B); + {KeyA, KeyB} when KeyA < KeyB -> + #t_union{tuple_set=[{KeyA, A}, {KeyB, B}]}; + {KeyA, KeyB} when KeyA > KeyB -> + #t_union{tuple_set=[{KeyB, B}, {KeyA, A}]} end; -meet(#t_atom{elements=[_|_]}=T, #t_atom{elements=any}) -> - T; -meet(#t_atom{elements=any}, #t_atom{elements=[_|_]}=T) -> - T; -meet(#t_bs_context{slots=SlotCountA,valid=ValidSlotsA}, - #t_bs_context{slots=SlotCountB,valid=ValidSlotsB}) -> - CommonSlotMask = (1 bsl min(SlotCountA, SlotCountB)) - 1, - CommonSlotsA = ValidSlotsA band CommonSlotMask, - CommonSlotsB = ValidSlotsB band CommonSlotMask, - if - CommonSlotsA =:= CommonSlotsB -> - #t_bs_context{slots=max(SlotCountA, SlotCountB), - valid=ValidSlotsA bor ValidSlotsB}; - CommonSlotsA =/= CommonSlotsB -> - none - end; -meet(#t_fun{arity=any}, #t_fun{}=T) -> - T; -meet(#t_fun{}=T, #t_fun{arity=any}) -> - 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={MinA,MaxA}}, #t_integer{elements={MinB,MaxB}}) - when MinA >= MinB, MinA =< MaxB; - MinB >= MinA, MinB =< MaxA -> - true = MinA =< MaxA andalso MinB =< MaxB, %Assertion. - #t_integer{elements={max(MinA, MinB),min(MaxA, MaxB)}}; -meet(#t_integer{}=T, number) -> T; -meet(float=T, number) -> T; -meet(number, #t_integer{}=T) -> T; -meet(number, float=T) -> 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(#t_bitstring{unit=U1}, #t_bitstring{unit=U2}) -> - #t_bitstring{unit=U1 * U2 div gcd(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{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, - case meet_elements(Es1, Es2) of - none -> - none; - Es -> - #t_tuple{size=Size,exact=Exact,elements=Es} +join(#t_tuple{}=A, B) -> + %% All other combinations have been tried already, so B must be 'other' + #t_union{tuple_set=new_tuple_set(A),other=B}; +join(A, #t_tuple{}=B) -> + join(B, A); + +join(A, B) -> + lub(A, B). + +join_unions(#t_union{atom=AtomA,list=ListA,number=NumberA, + tuple_set=TSetA,other=OtherA}, + #t_union{atom=AtomB,list=ListB,number=NumberB, + tuple_set=TSetB,other=OtherB}) -> + Union = #t_union{atom=lub(AtomA, AtomB), + list=lub(ListA, ListB), + number=lub(NumberA, NumberB), + tuple_set=join_tuple_sets(TSetA, TSetB), + other=lub(OtherA, OtherB)}, + shrink_union(Union); +join_unions(#t_union{atom=AtomA}=A, #t_atom{}=B) -> + A#t_union{atom=lub(AtomA, B)}; +join_unions(#t_union{list=ListA}=A, B) when ?IS_LIST_TYPE(B) -> + A#t_union{list=lub(ListA, B)}; +join_unions(#t_union{number=NumberA}=A, B) when ?IS_NUMBER_TYPE(B) -> + A#t_union{number=lub(NumberA, B)}; +join_unions(#t_union{tuple_set=TSetA}=A, #t_tuple{}=B) -> + Set = join_tuple_sets(TSetA, new_tuple_set(B)), + shrink_union(A#t_union{tuple_set=Set}); +join_unions(#t_union{other=OtherA}=A, B) -> + case lub(OtherA, B) of + any -> any; + T -> A#t_union{other=T} 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) -> +join_tuple_sets(A, none) -> + A; +join_tuple_sets(none, B) -> + B; +join_tuple_sets(#t_tuple{}=A, #t_tuple{}=B) -> + lub(A, B); +join_tuple_sets(#t_tuple{}=Tuple, Records) -> + jts_tuple(Records, Tuple); +join_tuple_sets(Records, #t_tuple{}=Tuple) -> + join_tuple_sets(Tuple, Records); +join_tuple_sets(RecordsA, RecordsB) -> + jts_records(RecordsA, RecordsB). + +jts_tuple([{_Key, Tuple} | Records], Acc) -> + jts_tuple(Records, lub(Tuple, Acc)); +jts_tuple([], Acc) -> Acc. -%% Meets all the given types into a single type. --spec meet([type()]) -> type(). - -meet([T1,T2|Ts]) -> - meet([meet(T1, T2)|Ts]); -meet([T]) -> T. +jts_records(RsA, RsB) -> + jts_records(RsA, RsB, 0, []). + +jts_records(RsA, RsB, N, Acc) when N > ?TUPLE_SET_LIMIT -> + A = normalize_tuple_set(RsA, none), + B = normalize_tuple_set(RsB, A), + #t_tuple{} = normalize_tuple_set(Acc, B); +jts_records([{Key, A} | RsA], [{Key, B} | RsB], N, Acc) -> + jts_records(RsA, RsB, N + 1, [{Key, lub(A, B)} | Acc]); +jts_records([{KeyA, _} | _]=RsA, [{KeyB, B} | RsB], N, Acc) when KeyA > KeyB -> + jts_records(RsA, RsB, N + 1, [{KeyB, B} | Acc]); +jts_records([{KeyA, A} | RsA], [{KeyB, _} | _] = RsB, N, Acc) when KeyA < KeyB -> + jts_records(RsA, RsB, N + 1, [{KeyA, A} | Acc]); +jts_records([], RsB, _N, Acc) -> + reverse(Acc, RsB); +jts_records(RsA, [], _N, Acc) -> + reverse(Acc, RsA). %% Subtract Type2 from Type1. Example: %% subtract(list, cons) -> nil @@ -270,38 +323,28 @@ subtract(number, float) -> #t_integer{}; subtract(number, #t_integer{elements=any}) -> float; subtract(list, cons) -> nil; subtract(list, nil) -> cons; -subtract(T, _) -> T. -%% Verifies that the given type is well-formed. - --spec verified_type(T) -> T when - T :: type(). +subtract(#t_union{atom=Atom}=A, #t_atom{}=B)-> + shrink_union(A#t_union{atom=subtract(Atom, B)}); +subtract(#t_union{number=Number}=A, B) when ?IS_NUMBER_TYPE(B) -> + shrink_union(A#t_union{number=subtract(Number, B)}); +subtract(#t_union{list=List}=A, B) when ?IS_LIST_TYPE(B) -> + shrink_union(A#t_union{list=subtract(List, B)}); +subtract(#t_union{tuple_set=[_|_]=Records0}=A, #t_tuple{}=B) -> + %% Filter out all records that are strictly more specific than B. + NewSet = case [{Key, T} || {Key, T} <- Records0, meet(T, B) =/= T] of + [_|_]=Records -> Records; + [] -> none + end, + shrink_union(A#t_union{tuple_set=NewSet}); +subtract(#t_union{tuple_set=#t_tuple{}=Tuple}=A, #t_tuple{}=B) -> + %% Exclude Tuple if it's strictly more specific than B. + case meet(Tuple, B) of + Tuple -> shrink_union(A#t_union{tuple_set=none}); + _ -> A + end; -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(#t_bitstring{unit=U}=T) when is_integer(U), U >= 1 -> T; -verified_type(#t_bs_context{}=T) -> T; -verified_type(#t_fun{arity=Arity}=T) when Arity =:= any; is_integer(Arity) -> T; -verified_type(#t_integer{elements=any}=T) -> T; -verified_type(#t_integer{elements={Min,Max}}=T) - when is_integer(Min), is_integer(Max), Min =< Max -> T; -verified_type(list=T) -> T; -verified_type(#t_map{}=T) -> T; -verified_type(nil=T) -> T; -verified_type(cons=T) -> T; -verified_type(number=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. +subtract(T, _) -> T. %%% %%% Type operators @@ -319,23 +362,15 @@ get_singleton_value(nil) -> get_singleton_value(_) -> error. --spec get_tuple_size(Type) -> Result when - Type :: type(), - Result :: none | {at_least, Size} | {exact, Size}, - Size :: non_neg_integer(). -get_tuple_size(#t_tuple{size=Size,exact=false}) -> - {at_least,Size}; -get_tuple_size(#t_tuple{size=Size,exact=true}) -> - {exact,Size}; -get_tuple_size(_) -> - none. - -spec is_boolean_type(type()) -> boolean(). is_boolean_type(#t_atom{elements=[F,T]}) -> F =:= false andalso T =:= true; is_boolean_type(#t_atom{elements=[B]}) -> is_boolean(B); -is_boolean_type(_) -> false. +is_boolean_type(#t_union{}=T) -> + is_boolean_type(normalize(T)); +is_boolean_type(_) -> + false. -spec is_singleton_type(type()) -> boolean(). is_singleton_type(Type) -> @@ -361,6 +396,23 @@ get_element_type(Index, Es) -> #{} -> any end. +-spec normalize(type()) -> normal_type(). +normalize(#t_union{atom=Atom,list=List,number=Number, + tuple_set=Tuples,other=Other}) -> + A = lub(Atom, List), + B = lub(A, Number), + C = lub(B, Other), + normalize_tuple_set(Tuples, C); +normalize(T) -> + verified_normal_type(T). + +normalize_tuple_set([{_, A} | Records], B) -> + normalize_tuple_set(Records, lub(A, B)); +normalize_tuple_set([], B) -> + B; +normalize_tuple_set(A, B) -> + lub(A, B). + %%% %%% Type constructors %%% @@ -408,17 +460,319 @@ make_integer(Int) when is_integer(Int) -> make_integer(Min, Max) when is_integer(Min), is_integer(Max), Min =< Max -> #t_integer{elements={Min,Max}}. --spec make_tuple(Size, Exact) -> type() when - Size :: non_neg_integer(), - Exact :: boolean(). -make_tuple(Size, Exact) -> - make_tuple(Size, Exact, #{}). - --spec make_tuple(Size, Exact, Elements) -> type() when - Size :: non_neg_integer(), - Exact :: boolean(), - Elements :: #{ non_neg_integer() => type() }. -make_tuple(Size, Exact, Elements) -> - #t_tuple{size=Size, - exact=Exact, - elements=Elements}. +%%% +%%% Helpers +%%% + +%% Return the greatest lower bound of the types Type1 and Type2. The GLB is a +%% more specific type than Type1 and Type2, and is always a normal type. +%% +%% glb(#t_integer{elements=any}, #t_integer{elements={0,3}}) -> +%% #t_integer{elements={0,3}} +%% +%% The GLB of two different types result in 'none', which is the bottom +%% element for our type lattice: +%% +%% glb(#t_integer{}, #t_map{}) -> none + +-spec glb(normal_type(), normal_type()) -> normal_type(). + +glb(T, T) -> + verified_normal_type(T); +glb(any, T) -> + verified_normal_type(T); +glb(T, any) -> + verified_normal_type(T); +glb(#t_atom{elements=[_|_]=Set1}, #t_atom{elements=[_|_]=Set2}) -> + case ordsets:intersection(Set1, Set2) of + [] -> + none; + [_|_]=Set -> + #t_atom{elements=Set} + end; +glb(#t_atom{elements=[_|_]}=T, #t_atom{elements=any}) -> + T; +glb(#t_atom{elements=any}, #t_atom{elements=[_|_]}=T) -> + T; +glb(#t_bs_context{slots=SlotCountA,valid=ValidSlotsA}, + #t_bs_context{slots=SlotCountB,valid=ValidSlotsB}) -> + CommonSlotMask = (1 bsl min(SlotCountA, SlotCountB)) - 1, + CommonSlotsA = ValidSlotsA band CommonSlotMask, + CommonSlotsB = ValidSlotsB band CommonSlotMask, + if + CommonSlotsA =:= CommonSlotsB -> + #t_bs_context{slots=max(SlotCountA, SlotCountB), + valid=ValidSlotsA bor ValidSlotsB}; + CommonSlotsA =/= CommonSlotsB -> + none + end; +glb(#t_fun{arity=any}, #t_fun{}=T) -> + T; +glb(#t_fun{}=T, #t_fun{arity=any}) -> + T; +glb(#t_integer{elements={_,_}}=T, #t_integer{elements=any}) -> + T; +glb(#t_integer{elements=any}, #t_integer{elements={_,_}}=T) -> + T; +glb(#t_integer{elements={MinA,MaxA}}, #t_integer{elements={MinB,MaxB}}) + when MinA >= MinB, MinA =< MaxB; + MinB >= MinA, MinB =< MaxA -> + true = MinA =< MaxA andalso MinB =< MaxB, %Assertion. + #t_integer{elements={max(MinA, MinB),min(MaxA, MaxB)}}; +glb(#t_integer{}=T, number) -> T; +glb(float=T, number) -> T; +glb(number, #t_integer{}=T) -> T; +glb(number, float=T) -> T; +glb(list, cons) -> cons; +glb(list, nil) -> nil; +glb(cons, list) -> cons; +glb(nil, list) -> nil; +glb(#t_tuple{}=T1, #t_tuple{}=T2) -> + glb_tuples(T1, T2); +glb(#t_bitstring{unit=U1}, #t_bitstring{unit=U2}) -> + #t_bitstring{unit=U1 * U2 div gcd(U1, U2)}; +glb(_, _) -> + %% Inconsistent types. There will be an exception at runtime. + none. + +glb_tuples(#t_tuple{size=Sz1,exact=true}, + #t_tuple{size=Sz2,exact=true}) when Sz1 =/= Sz2 -> + none; +glb_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, + case glb_elements(Es1, Es2) of + none -> + none; + Es -> + #t_tuple{size=Size,exact=Exact,elements=Es} + end. + +glb_elements(Es1, Es2) -> + Keys = maps:keys(Es1) ++ maps:keys(Es2), + glb_elements_1(Keys, Es1, Es2, #{}). + +glb_elements_1([Key | Keys], Es1, Es2, Acc) -> + case {Es1, Es2} of + {#{ Key := Type1 }, #{ Key := Type2 }} -> + %% Note the use of meet/2; elements don't need to be normal types. + case meet(Type1, Type2) of + none -> none; + Type -> glb_elements_1(Keys, Es1, Es2, Acc#{ Key => Type }) + end; + {#{ Key := Type1 }, _} -> + glb_elements_1(Keys, Es1, Es2, Acc#{ Key => Type1 }); + {_, #{ Key := Type2 }} -> + glb_elements_1(Keys, Es1, Es2, Acc#{ Key => Type2 }) + end; +glb_elements_1([], _Es1, _Es2, Acc) -> + Acc. + +%% Return the least upper bound of the types Type1 and Type2. The LUB is a more +%% general type than Type1 and Type2, and is always a normal type. +%% +%% For example: +%% +%% lub(#t_integer{elements=any}, #t_integer=elements={0,3}}) -> +%% #t_integer{} +%% +%% The LUB for two different types result in 'any' (not a union type!), which +%% is the top element for our type lattice: +%% +%% lub(#t_integer{}, #t_map{}) -> any + +-spec lub(normal_type(), normal_type()) -> normal_type(). + +lub(T, T) -> + verified_normal_type(T); +lub(none, T) -> + verified_normal_type(T); +lub(T, none) -> + verified_normal_type(T); +lub(any, _) -> + any; +lub(_, any) -> + any; +lub(#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; +lub(#t_atom{elements=any}=T, #t_atom{elements=[_|_]}) -> T; +lub(#t_atom{elements=[_|_]}, #t_atom{elements=any}=T) -> T; +lub(#t_bitstring{unit=U1}, #t_bitstring{unit=U2}) -> + #t_bitstring{unit=gcd(U1, U2)}; +lub(#t_fun{}, #t_fun{}) -> + #t_fun{}; +lub(#t_integer{elements={MinA,MaxA}}, + #t_integer{elements={MinB,MaxB}}) -> + #t_integer{elements={min(MinA,MinB),max(MaxA,MaxB)}}; +lub(#t_bs_context{slots=SlotsA,valid=ValidA}, + #t_bs_context{slots=SlotsB,valid=ValidB}) -> + #t_bs_context{slots=min(SlotsA, SlotsB), + valid=ValidA band ValidB}; +lub(#t_integer{}, #t_integer{}) -> #t_integer{}; +lub(list, cons) -> list; +lub(cons, list) -> list; +lub(nil, cons) -> list; +lub(cons, nil) -> list; +lub(nil, list) -> list; +lub(list, nil) -> list; +lub(#t_integer{}, float) -> number; +lub(float, #t_integer{}) -> number; +lub(#t_integer{}, number) -> number; +lub(number, #t_integer{}) -> number; +lub(float, number) -> number; +lub(number, float) -> number; +lub(#t_tuple{size=Sz,exact=ExactA,elements=EsA}, + #t_tuple{size=Sz,exact=ExactB,elements=EsB}) -> + Exact = ExactA and ExactB, + Es = lub_tuple_elements(Sz, EsA, EsB), + #t_tuple{size=Sz,exact=Exact,elements=Es}; +lub(#t_tuple{size=SzA,elements=EsA}, #t_tuple{size=SzB,elements=EsB}) -> + Sz = min(SzA, SzB), + Es = lub_tuple_elements(Sz, EsA, EsB), + #t_tuple{size=Sz,elements=Es}; +lub(_T1, _T2) -> + %%io:format("~p ~p\n", [_T1,_T2]), + any. + +lub_tuple_elements(MinSize, EsA, EsB) -> + Es0 = lub_elements(EsA, EsB), + maps:filter(fun(Index, _Type) -> Index =< MinSize end, Es0). + +lub_elements(Es1, Es2) -> + Keys = if + map_size(Es1) =< map_size(Es2) -> maps:keys(Es1); + map_size(Es1) > map_size(Es2) -> maps:keys(Es2) + end, + lub_elements_1(Keys, Es1, Es2, #{}). + +lub_elements_1([Key | Keys], Es1, Es2, Acc0) -> + case {Es1, Es2} of + {#{ Key := Type1 }, #{ Key := Type2 }} -> + %% Note the use of join/2; elements don't need to be normal types. + Acc = set_element_type(Key, join(Type1, Type2), Acc0), + lub_elements_1(Keys, Es1, Es2, Acc); + {#{}, #{}} -> + lub_elements_1(Keys, Es1, Es2, Acc0) + end; +lub_elements_1([], _Es1, _Es2, Acc) -> + Acc. + +%% + +gcd(A, B) -> + case A rem B of + 0 -> B; + X -> gcd(B, X) + end. + +%% + +record_key(#t_tuple{exact=true,size=Size,elements=#{ 1 := Tag }}) -> + case is_singleton_type(Tag) of + true -> {Size, Tag}; + false -> none + end; +record_key(_) -> + none. + +new_tuple_set(T) -> + case record_key(T) of + none -> T; + Key -> [{Key, T}] + end. + +%% + +shrink_union(#t_union{other=any}) -> + any; +shrink_union(#t_union{atom=Atom,list=none,number=none, + tuple_set=none,other=none}) -> + Atom; +shrink_union(#t_union{atom=none,list=List,number=none, + tuple_set=none,other=none}) -> + List; +shrink_union(#t_union{atom=none,list=none,number=Number, + tuple_set=none,other=none}) -> + Number; +shrink_union(#t_union{atom=none,list=none,number=none, + tuple_set=#t_tuple{}=Tuple,other=none}) -> + Tuple; +shrink_union(#t_union{atom=none,list=none,number=none, + tuple_set=[{_Key, Record}],other=none}) -> + #t_tuple{} = Record; %Assertion. +shrink_union(#t_union{atom=none,list=none,number=none, + tuple_set=none,other=Other}) -> + Other; +shrink_union(#t_union{}=T) -> + T. + +%% Verifies that the given type is well-formed. + +-spec verified_type(T) -> T when + T :: type(). + +verified_type(#t_union{atom=Atom, + list=List, + number=Number, + tuple_set=TSet, + other=Other}=T) -> + _ = verified_normal_type(Atom), + _ = verified_normal_type(List), + _ = verified_normal_type(Number), + _ = verify_tuple_set(TSet), + _ = verified_normal_type(Other), + T; +verified_type(T) -> + verified_normal_type(T). + +verify_tuple_set([_|_]=T) -> + _ = [verified_normal_type(Rec) || {_, Rec} <- T], + T; +verify_tuple_set(#t_tuple{}=T) -> + none = record_key(T), %Assertion. + T; +verify_tuple_set(none=T) -> + T. + +-spec verified_normal_type(T) -> T when + T :: normal_type(). + +verified_normal_type(any=T) -> T; +verified_normal_type(none=T) -> T; +verified_normal_type(#t_atom{elements=any}=T) -> T; +verified_normal_type(#t_atom{elements=[_|_]}=T) -> T; +verified_normal_type(#t_bitstring{unit=U}=T) + when is_integer(U), U >= 1 -> + T; +verified_normal_type(#t_bs_context{}=T) -> T; +verified_normal_type(#t_fun{arity=Arity}=T) + when Arity =:= any; is_integer(Arity) -> + T; +verified_normal_type(float=T) -> T; +verified_normal_type(#t_integer{elements=any}=T) -> T; +verified_normal_type(#t_integer{elements={Min,Max}}=T) + when is_integer(Min), is_integer(Max), Min =< Max -> + T; +verified_normal_type(list=T) -> T; +verified_normal_type(#t_map{}=T) -> T; +verified_normal_type(nil=T) -> T; +verified_normal_type(cons=T) -> T; +verified_normal_type(number=T) -> T; +verified_normal_type(#t_tuple{size=Size,elements=Es}=T) -> + %% All known elements must have a valid index and type (which may be a + %% union). 'any' is prohibited since it's implicit and should never be + %% present in the map, and a 'none' element ought to have reduced the + %% entire tuple to 'none'. + maps:fold(fun(Index, Element, _) when is_integer(Index), + 1 =< Index, Index =< Size, + Element =/= any, Element =/= none -> + verified_type(Element) + end, [], Es), + T. diff --git a/lib/compiler/src/beam_types.hrl b/lib/compiler/src/beam_types.hrl index 212fe62063..09f87d61ba 100644 --- a/lib/compiler/src/beam_types.hrl +++ b/lib/compiler/src/beam_types.hrl @@ -39,6 +39,13 @@ %% - #t_tuple{} Tuple. %% %% none No type (bottom element). +%% +%% We also use #t_union{} to represent conflicting types produced by certain +%% expressions, e.g. the "#t_atom{} or #t_tuple{}" of lists:keyfind/3, which is +%% very useful for preserving type information when we would otherwise have +%% reduced it to 'any'. Since few operations can make direct use of this extra +%% type information, types should generally be normalized to one of the above +%% before use. -define(ATOM_SET_SIZE, 5). @@ -62,8 +69,20 @@ -type elements() :: tuple_elements() | map_elements(). --type type() :: any | none | - list | number | - #t_atom{} | #t_bitstring{} | #t_bs_context{} | - #t_fun{} | #t_integer{} | #t_map{} | #t_tuple{} | - 'cons' | 'float' | 'nil'. +-type normal_type() :: any | none | + list | number | + #t_atom{} | #t_bitstring{} | #t_bs_context{} | + #t_fun{} | #t_integer{} | #t_map{} | #t_tuple{} | + 'cons' | 'float' | 'nil'. + +-type record_key() :: {Arity :: integer(), Tag :: normal_type() }. +-type record_set() :: ordsets:ordset({record_key(), #t_tuple{}}). +-type tuple_set() :: #t_tuple{} | record_set(). + +-record(t_union, {atom=none :: none | #t_atom{}, + list=none :: none | list | cons | nil, + number=none :: none | number | float | #t_integer{}, + tuple_set=none :: none | tuple_set(), + other=none :: normal_type()}). + +-type type() :: #t_union{} | normal_type(). diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index d959700b88..923a0b4a4e 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -570,7 +570,7 @@ valfun_1({get_tuple_element,Src,N,Dst}, Vst) -> Index = N+1, assert_not_literal(Src), assert_type(#t_tuple{size=Index}, Src, Vst), - #t_tuple{elements=Es} = get_term_type(Src, Vst), + #t_tuple{elements=Es} = normalize(get_term_type(Src, Vst)), Type = beam_types:get_element_type(Index, Es), extract_term(Type, {bif,element}, [{integer,Index}, Src], Dst, Vst); valfun_1({jump,{f,Lbl}}, Vst) -> @@ -762,7 +762,7 @@ valfun_4({set_tuple_element,Src,Tuple,N}, Vst) -> %% helpers as we must support overwriting (rather than just widening or %% narrowing) known elements, and we can't use extract_term either since %% the source tuple may be aliased. - #t_tuple{elements=Es0}=Type = get_term_type(Tuple, Vst), + #t_tuple{elements=Es0}=Type = normalize(get_term_type(Tuple, Vst)), Es = beam_types:set_element_type(I, get_term_type(Src, Vst), Es0), override_type(Type#t_tuple{elements=Es}, Tuple, Vst); %% Match instructions. @@ -1927,6 +1927,9 @@ is_literal(_) -> false. %% The funny-looking abstract types produced here are intended to provoke %% errors on actual use; they do no harm just lying around. +normalize(#t_abstract{}=A) -> error({abstract_type, A}); +normalize(T) -> beam_types:normalize(T). + join(Same, Same) -> Same; join(#t_abstract{}=A, B) -> #t_abstract{kind={join, A, B}}; join(A, #t_abstract{}=B) -> #t_abstract{kind={join, A, B}}; @@ -2369,7 +2372,7 @@ assert_not_fragile(Lit, #vst{}) -> %%% bif_types(Op, Ss, Vst) -> - Args = [get_term_type(Arg, Vst) || Arg <- Ss], + Args = [normalize(get_term_type(Arg, Vst)) || Arg <- Ss], beam_call_types:types(erlang, Op, Args). call_types({extfunc,M,F,A}, A, Vst) -> @@ -2384,7 +2387,8 @@ get_call_args(Arity, Vst) -> get_call_args_1(Arity, Arity, _) -> []; get_call_args_1(N, Arity, Vst) when N < Arity -> - [get_movable_term_type({x,N}, Vst) | get_call_args_1(N + 1, Arity, Vst)]. + ArgType = normalize(get_movable_term_type({x,N}, Vst)), + [ArgType | get_call_args_1(N + 1, Arity, Vst)]. check_limit({x,X}=Src) when is_integer(X) -> if -- cgit v1.2.3 From 2c68d8d79550a2e5fec1026359057e808d03cc4b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Wed, 3 Jul 2019 13:43:39 +0200 Subject: beam_call_types: Add lists:keyfind/3 and lists:search/2 --- lib/compiler/src/beam_call_types.erl | 29 +++++++++++++++++++++-------- 1 file changed, 21 insertions(+), 8 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_call_types.erl b/lib/compiler/src/beam_call_types.erl index a94a7caa74..e76ad79365 100644 --- a/lib/compiler/src/beam_call_types.erl +++ b/lib/compiler/src/beam_call_types.erl @@ -353,15 +353,27 @@ types(lists, zipwith3, [_,A,B,C]) -> sub_unsafe(ZipType, [#t_fun{arity=3}, ZipType, ZipType, ZipType]); %% Functions with complex return values. -types(lists, partition, [_,_]) -> - sub_unsafe(make_two_tuple(list, list), [#t_fun{arity=1}, list]); +types(lists, keyfind, [KeyType,PosType,_]) -> + TupleType = case PosType of + #t_integer{elements={Index,Index}} when is_integer(Index), + Index >= 1 -> + Es = beam_types:set_element_type(Index, KeyType, #{}), + #t_tuple{size=Index,elements=Es}; + _ -> + #t_tuple{} + end, + RetType = beam_types:join(TupleType, beam_types:make_atom(false)), + sub_unsafe(RetType, [any, #t_integer{}, list]); types(lists, MapFold, [_Fun, _Init, List]) when MapFold =:= mapfoldl; MapFold =:= mapfoldr -> - ListType = same_length_type(List), - RetType = #t_tuple{size=2, - exact=true, - elements=#{ 1 => ListType }}, + RetType = make_two_tuple(same_length_type(List), any), sub_unsafe(RetType, [#t_fun{arity=2}, any, list]); +types(lists, partition, [_,_]) -> + sub_unsafe(make_two_tuple(list, list), [#t_fun{arity=1}, list]); +types(lists, search, [_,_]) -> + TupleType = make_two_tuple(beam_types:make_atom(value), any), + RetType = beam_types:join(TupleType, beam_types:make_atom(false)), + sub_unsafe(RetType, [#t_fun{arity=1}, list]); types(lists, splitwith, [_,_]) -> sub_unsafe(make_two_tuple(list, list), [#t_fun{arity=1}, list]); types(lists, unzip, [List]) -> @@ -473,5 +485,6 @@ lists_zip_type(Types) -> end, list, Types). make_two_tuple(Type1, Type2) -> - #t_tuple{size=2,exact=true, - elements=#{1=>Type1,2=>Type2}}. + Es0 = beam_types:set_element_type(1, Type1, #{}), + Es = beam_types:set_element_type(2, Type2, Es0), + #t_tuple{size=2,exact=true,elements=Es}. -- cgit v1.2.3 From b2de9af91c1dc2dc4188986bf7a63fe48c045c33 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Wed, 3 Jul 2019 18:13:42 +0200 Subject: beam_ssa_type: Subtract more types inferred from '=:='/2 --- lib/compiler/src/beam_ssa_type.erl | 94 +++++++++++++++++++------------------- 1 file changed, 47 insertions(+), 47 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index f4fc33bf4f..8b7a31849c 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -1293,25 +1293,10 @@ raw_type(V, Ts) -> infer_types_br(#b_var{}=V, Ts, #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'. - - EqTypes = infer_eq_type(Op, Args, Ts, Ds), - NegTypes1 = [P || {_,T}=P <- EqTypes, beam_types:is_singleton_type(T)], + {PosTypes, NegTypes} = infer_type(Op, Args, Ts, Ds), - PosTypes = EqTypes ++ PosTypes0, SuccTs1 = meet_types(PosTypes, Ts), - - NegTypes = NegTypes0 ++ NegTypes1, FailTs1 = subtract_types(NegTypes, Ts), SuccTs = infer_br_value(V, Ts, true, SuccTs1), @@ -1337,37 +1322,8 @@ infer_br_value(V, OldTs, Bool, NewTs) -> end. 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 = raw_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 = raw_type(Arg0, Ts), - Type1 = raw_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_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(_, _) -> []. + {PosTypes, _} = infer_type({bif,'=:='}, [V, Lit], Ts, Ds), + meet_types(PosTypes, Ts). infer_type(succeeded, [#b_var{}=Src], Ts, Ds) -> #b_set{op=Op,args=Args} = maps:get(Src, Ds), @@ -1414,6 +1370,38 @@ 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), + + 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) -> {[], []}. @@ -1433,6 +1421,18 @@ infer_success_type(bs_start_match, [#b_var{}=Bin], _Ts, _Ds) -> 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) -> -- cgit v1.2.3 From 8fcf04006643c70078035c9af5245e3be0c33108 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Thu, 4 Jul 2019 11:28:03 +0200 Subject: beam_ssa_type: Infer types on switch failure If we know that the checked value is a singleton at the fail block, it's safe to infer types as if we've made a direct comparison against that value. --- lib/compiler/src/beam_ssa_type.erl | 118 +++++++++++++++++++----------------- lib/compiler/src/beam_validator.erl | 22 ++++++- 2 files changed, 84 insertions(+), 56 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 8b7a31849c..0912ecb2c2 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -814,18 +814,9 @@ prune_switch_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, - Ts0, D0) -> - Ts = 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. - maps:remove(Bool, Ts0); - false -> - Ts0 - end, - case infer_types_br(Bool, Ts, D0) of + 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), @@ -841,15 +832,12 @@ 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, UsedOnce, Ts, [], D0), - - FailTs = case UsedOnce of - true -> maps:remove(V, Ts); - false -> subtract_sw_list(V, List0, Ts) - end, + {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}; @@ -871,25 +859,33 @@ update_successors(#b_ret{arg=Arg}=Last, Ts, D0) -> end, {Last, D}. -update_switch([{Val, Lbl}=Sw | List], V, UsedOnce, Ts, Acc, D0) -> - case infer_types_switch(V, Val, Ts, D0) of +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, UsedOnce, Ts, Acc, D0); - SwTs0 -> - SwTs = case UsedOnce of - true -> maps:remove(V, SwTs0); - false -> SwTs0 - end, + update_switch(List, V, Ts, UsedOnce, Acc, D0); + SwTs -> D = update_successor(Lbl, SwTs, D0), - update_switch(List, V, UsedOnce, Ts, [Sw | Acc], D) + update_switch(List, V, Ts, UsedOnce, [Sw | Acc], D) end; -update_switch([], _V, _UsedOnce, _Ts, Acc, D) -> - {Acc, D}. +update_switch([], _V, _Ts, _UsedOnce, Acc, D) -> + {reverse(Acc), D}. -subtract_sw_list(V, List, Ts) -> +update_switch_failure(V, List, Ts, UsedOnce, D) -> case sub_sw_list_1(raw_type(V, Ts), List, Ts) of - none -> none; - Type -> Ts#{ V := Type } + 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) -> @@ -1291,39 +1287,51 @@ raw_type(V, 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, {PosTypes, NegTypes} = infer_type(Op, Args, Ts, Ds), - SuccTs1 = meet_types(PosTypes, Ts), - FailTs1 = subtract_types(NegTypes, Ts), - - SuccTs = infer_br_value(V, Ts, true, SuccTs1), - FailTs = infer_br_value(V, Ts, false, FailTs1), + SuccTs0 = meet_types(PosTypes, Ts), + FailTs0 = 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_br_value(_V, _OldTs, _Bool, none) -> +infer_br_value(_V, _Bool, none) -> none; -infer_br_value(V, OldTs, Bool, NewTs) -> - case OldTs of - #{ V := T } -> - 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; - #{} -> - %% V is only used in this branch; don't propagate its type. +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_types_switch(V, Lit, Ts, #d{ds=Ds}) -> - {PosTypes, _} = infer_type({bif,'=:='}, [V, Lit], Ts, Ds), - meet_types(PosTypes, Ts). +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. + +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), diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 923a0b4a4e..afede2b54d 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -1531,8 +1531,21 @@ validate_select_val(Fail, [Val,{f,L}|T], Src, Vst0) -> update_ne_types(Src, Val, FailVst) end), validate_select_val(Fail, T, Src, Vst); -validate_select_val(Fail, [], _, Vst) -> +validate_select_val(Fail, [], Src, Vst) -> branch(Fail, Vst, + fun(FailVst) -> + FailType = get_term_type(Src, FailVst), + 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 = value_to_literal(Value), + update_eq_types(Src, Lit, FailVst); + error -> + FailVst + end + end, fun(SuccVst) -> %% The next instruction is never executed. kill_state(SuccVst) @@ -1921,6 +1934,13 @@ is_literal({integer,I}) when is_integer(I) -> true; is_literal({literal,_L}) -> true; is_literal(_) -> false. +%% `dialyzer` complains about the float and general literal cases never being +%% matched and I don't like suppressing warnings. Should they become possible +%% I'm sure `dialyzer` will warn about it. +value_to_literal([]) -> nil; +value_to_literal(A) when is_atom(A) -> {atom,A}; +value_to_literal(I) when is_integer(I) -> {integer,I}. + %% These are just wrappers around their equivalents in beam_types, which %% handle the validator-specific #t_abstract{} type. %% -- cgit v1.2.3 From 39d1a52880ac90f99d5accd8df03a23fbdc05d11 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Thu, 4 Jul 2019 11:30:55 +0200 Subject: beam_ssa_opt: Sink get_tuple_element before type optimization Eagerly extracting elements can be quite problematic now that we have union types. Consider the following: 0: %% _0 is {ok, #record{}} | {error,atom()} _1 = get_tuple_element _0, literal 0 _2 = get_tuple_element _0, literal 1 switch _1, label 0, [ { literal ok, label 1 }, { literal error, label 2 } ] 1: %% _0 is known to be {ok,#record{}} here 2: %% _0 is known to be {error,atom()} here The type pass is clever enough to see that _0 has the types noted above, but because the type of _2 is set in the first block where we didn't have that information yet, it's still #record{} | atom() in both branches. Sinking these instructions to when they are used greatly improves the type information in many cases, but it does have a few limitations and using it in both of the above branches would take us back to square one. --- lib/compiler/src/beam_ssa_opt.erl | 16 +++++++++------- 1 file changed, 9 insertions(+), 7 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index a9f8daaada..cce539f582 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -158,6 +158,7 @@ repeated_passes(Opts) -> ?PASS(ssa_opt_dead), ?PASS(ssa_opt_cse), ?PASS(ssa_opt_tail_phis), + ?PASS(ssa_opt_sink), ?PASS(ssa_opt_tuple_size), ?PASS(ssa_opt_record), ?PASS(ssa_opt_type_continue)], %Must run after ssa_opt_dead to @@ -175,8 +176,8 @@ epilogue_passes(Opts) -> ?PASS(ssa_opt_bsm), ?PASS(ssa_opt_bsm_units), ?PASS(ssa_opt_bsm_shortcut), - ?PASS(ssa_opt_blockify), ?PASS(ssa_opt_sink), + ?PASS(ssa_opt_blockify), ?PASS(ssa_opt_merge_blocks), ?PASS(ssa_opt_get_tuple_element), ?PASS(ssa_opt_trim_unreachable)], @@ -1985,9 +1986,7 @@ is_merge_allowed(_, #b_blk{last=#b_switch{}}, #b_blk{}) -> %%% extracted values. %%% -ssa_opt_sink({#st{ssa=Blocks0}=St, FuncDb}) -> - Linear = beam_ssa:linearize(Blocks0), - +ssa_opt_sink({#st{ssa=Linear}=St, FuncDb}) -> %% Create a map with all variables that define get_tuple_element %% instructions. The variable name map to the block it is defined in. case def_blocks(Linear) of @@ -1996,10 +1995,12 @@ ssa_opt_sink({#st{ssa=Blocks0}=St, FuncDb}) -> {St, FuncDb}; [_|_]=Defs0 -> Defs = maps:from_list(Defs0), - {do_ssa_opt_sink(Linear, Defs, St), FuncDb} + {do_ssa_opt_sink(Defs, St), FuncDb} end. -do_ssa_opt_sink(Linear, Defs, #st{ssa=Blocks0}=St) -> +do_ssa_opt_sink(Defs, #st{ssa=Linear}=St) -> + Blocks0 = maps:from_list(Linear), + %% Now find all the blocks that use variables defined by get_tuple_element %% instructions. Used = used_blocks(Linear, Defs, []), @@ -2024,7 +2025,8 @@ do_ssa_opt_sink(Linear, Defs, #st{ssa=Blocks0}=St) -> From = map_get(V, Defs), move_defs(V, From, To, A) end, Blocks0, DefLoc), - St#st{ssa=Blocks}. + + St#st{ssa=beam_ssa:linearize(Blocks)}. def_blocks([{L,#b_blk{is=Is}}|Bs]) -> def_blocks_is(Is, L, def_blocks(Bs)); -- cgit v1.2.3