diff options
Diffstat (limited to 'lib/compiler')
| -rw-r--r-- | lib/compiler/src/beam_kernel_to_ssa.erl | 10 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa_dead.erl | 364 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa_opt.erl | 92 | ||||
| -rw-r--r-- | lib/compiler/src/beam_validator.erl | 698 | ||||
| -rw-r--r-- | lib/compiler/src/v3_kernel.erl | 85 | ||||
| -rw-r--r-- | lib/compiler/test/beam_validator_SUITE.erl | 29 | ||||
| -rw-r--r-- | lib/compiler/test/beam_validator_SUITE_data/merge_undefined.S | 4 | ||||
| -rw-r--r-- | lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S | 4 |
8 files changed, 777 insertions, 509 deletions
diff --git a/lib/compiler/src/beam_kernel_to_ssa.erl b/lib/compiler/src/beam_kernel_to_ssa.erl index 410bafe0bb..df95749fb3 100644 --- a/lib/compiler/src/beam_kernel_to_ssa.erl +++ b/lib/compiler/src/beam_kernel_to_ssa.erl @@ -327,7 +327,7 @@ select_bin_seg(#k_val_clause{val=#k_bin_seg{size=Size,unit=U,type=T, {Mis,St1} = select_extract_bin(Next, Size, U, T, Fs, Fail, Ctx, LineAnno, St0), {Extracted,St2} = new_ssa_var(Seg#k_var.name, St1), - {Bis,St} = bin_match_cg(Size, B, Fail, St2), + {Bis,St} = match_cg(B, Fail, St2), BsGet = #b_set{op=bs_extract,dst=Extracted,args=[ssa_arg(Next, St)]}, Is = Mis ++ [BsGet] ++ Bis, {Is,St}; @@ -362,14 +362,6 @@ select_bin_seg(#k_val_clause{val=#k_bin_int{size=Sz,unit=U,flags=Fs, end, {Is,St}. -bin_match_cg(#k_atom{val=all}, B0, Fail, St) -> - #k_select{types=Types} = B0, - [#k_type_clause{type=k_bin_end,values=Values}] = Types, - [#k_val_clause{val=#k_bin_end{},body=B}] = Values, - match_cg(B, Fail, St); -bin_match_cg(_, B, Fail, St) -> - match_cg(B, Fail, St). - get_context(#k_var{}=Var, St) -> ssa_arg(Var, St). diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl index 2cca9ebadf..bb43a550ae 100644 --- a/lib/compiler/src/beam_ssa_dead.erl +++ b/lib/compiler/src/beam_ssa_dead.erl @@ -27,7 +27,8 @@ -export([opt/1]). -include("beam_ssa.hrl"). --import(lists, [append/1,last/1,member/2,takewhile/2,reverse/1]). +-import(lists, [append/1,keymember/3,last/1,member/2, + takewhile/2,reverse/1]). -type used_vars() :: #{beam_ssa:label():=ordsets:ordset(beam_ssa:var_name())}. @@ -58,7 +59,7 @@ opt(Linear) -> Blocks0 = maps:from_list(Linear), St0 = #st{bs=Blocks0,us=Used,skippable=Skippable}, St = shortcut_opt(St0), - #st{bs=Blocks} = combine_eqs(St), + #st{bs=Blocks} = combine_eqs(St#st{us=#{}}), beam_ssa:linearize(Blocks). %%% @@ -87,13 +88,22 @@ shortcut_opt(#st{bs=Blocks}=St) -> %% opportunities for optimizations compared to post order. (Based on %% running scripts/diffable with both PO and RPO and looking at %% the diff.) + %% + %% Unfortunately, processing the blocks in reverse post order + %% potentially makes the time complexity quadratic or even cubic if + %% the ordset of unset variables grows large, instead of + %% linear for post order processing. We try to still get reasonable + %% compilation times by optimizations that will keep the constant + %% factor as low as possible, and we try to avoid the cubic time + %% complexity by trying to keep the set of unset variables as small + %% as possible. + Ls = beam_ssa:rpo(Blocks), - shortcut_opt(Ls, #{from=>0}, St). + shortcut_opt(Ls, #{}, St). -shortcut_opt([L|Ls], Bs0, #st{bs=Blocks0}=St) -> +shortcut_opt([L|Ls], Bs, #st{bs=Blocks0}=St) -> #b_blk{is=Is,last=Last0} = Blk0 = get_block(L, St), - Bs = Bs0#{from:=L}, - case shortcut_terminator(Last0, Is, Bs, St) of + case shortcut_terminator(Last0, Is, L, Bs, St) of Last0 -> %% No change. No need to update the block. shortcut_opt(Ls, Bs, St); @@ -107,17 +117,17 @@ shortcut_opt([L|Ls], Bs0, #st{bs=Blocks0}=St) -> shortcut_opt([], _, St) -> St. shortcut_terminator(#b_br{bool=#b_literal{val=true},succ=Succ0}, - _Is, Bs, St0) -> + _Is, From, Bs, St0) -> St = St0#st{rel_op=none}, - shortcut(Succ0, Bs, St); + shortcut(Succ0, From, Bs, St); shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br, - Is, Bs, St0) -> + Is, From, Bs, St0) -> St = St0#st{target=one_way}, RelOp = get_rel_op(Bool, Is), SuccBs = bind_var(Bool, #b_literal{val=true}, Bs), - BrSucc = shortcut(Succ0, SuccBs, St#st{rel_op=RelOp}), + BrSucc = shortcut(Succ0, From, SuccBs, St#st{rel_op=RelOp}), FailBs = bind_var(Bool, #b_literal{val=false}, Bs), - BrFail = shortcut(Fail0, FailBs, St#st{rel_op=invert_op(RelOp)}), + BrFail = shortcut(Fail0, From, FailBs, St#st{rel_op=invert_op(RelOp)}), case {BrSucc,BrFail} of {#b_br{bool=#b_literal{val=true},succ=Succ}, #b_br{bool=#b_literal{val=true},succ=Fail}} @@ -128,25 +138,25 @@ shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br, %% No change. Br end; -shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, Bs, St) -> - List = shortcut_switch(List0, Bool, Bs, St), +shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, From, Bs, St) -> + List = shortcut_switch(List0, Bool, From, Bs, St), beam_ssa:normalize(Sw#b_switch{list=List}); -shortcut_terminator(Last, _Is, _Bs, _St) -> +shortcut_terminator(Last, _Is, _Bs, _From, _St) -> Last. -shortcut_switch([{Lit,L0}|T], Bool, Bs, St0) -> +shortcut_switch([{Lit,L0}|T], Bool, From, Bs, St0) -> RelOp = {'=:=',Bool,Lit}, St = St0#st{rel_op=RelOp}, #b_br{bool=#b_literal{val=true},succ=L} = - shortcut(L0, bind_var(Bool, Lit, Bs), St#st{target=one_way}), - [{Lit,L}|shortcut_switch(T, Bool, Bs, St0)]; -shortcut_switch([], _, _, _) -> []. + shortcut(L0, From, bind_var(Bool, Lit, Bs), St#st{target=one_way}), + [{Lit,L}|shortcut_switch(T, Bool, From, Bs, St0)]; +shortcut_switch([], _, _, _, _) -> []. -shortcut(L, Bs, St) -> - shortcut_1(L, Bs, ordsets:new(), St). +shortcut(L, From, Bs, St) -> + shortcut_1(L, From, Bs, ordsets:new(), St). -shortcut_1(L, Bs0, UnsetVars0, St) -> - case shortcut_2(L, Bs0, UnsetVars0, St) of +shortcut_1(L, From, Bs0, UnsetVars0, St) -> + case shortcut_2(L, From, Bs0, UnsetVars0, St) of none -> %% No more shortcuts found. Package up the previous %% label in an unconditional branch. @@ -156,13 +166,13 @@ shortcut_1(L, Bs0, UnsetVars0, St) -> Br; {#b_br{bool=#b_literal{val=true},succ=Succ},Bs,UnsetVars} -> %% This is a safe `br`, but try to find a better one. - shortcut_1(Succ, Bs#{from:=L}, UnsetVars, St) + shortcut_1(Succ, L, Bs, UnsetVars, St) end. %% Try to shortcut this block, branching to a successor. -shortcut_2(L, Bs0, UnsetVars0, St) -> +shortcut_2(L, From, Bs0, UnsetVars0, St) -> #b_blk{is=Is,last=Last} = get_block(L, St), - case eval_is(Is, Bs0, St) of + case eval_is(Is, From, Bs0, St) of none -> %% It is not safe to avoid this block because it %% has instructions with potential side effects. @@ -181,139 +191,147 @@ shortcut_2(L, Bs0, UnsetVars0, St) -> %% We have a potentially suitable br. %% Now update the set of variables that will never %% be set if this block will be skipped. - SetInThisBlock = [V || #b_set{dst=V} <- Is], - UnsetVars = update_unset_vars(L, Br, SetInThisBlock, - UnsetVars0, St), - - %% Continue checking whether this br is suitable. - shortcut_3(Br, Bs#{from:=L}, UnsetVars, St) + case update_unset_vars(L, Is, Br, UnsetVars0, St) of + unsafe -> + %% It is unsafe to use this br, + %% because it refers to a variable defined + %% in this block. + shortcut_unsafe_br(Br, L, Bs, UnsetVars0, St); + UnsetVars -> + %% Continue checking whether this br is + %% suitable. + shortcut_test_br(Br, L, Bs, UnsetVars, St) + end end end. -shortcut_3(Br, Bs, UnsetVars, #st{target=Target}=St) -> +shortcut_test_br(Br, From, Bs, UnsetVars, St) -> case is_br_safe(UnsetVars, Br, St) of false -> - %% Branching using this `br` is unsafe, either because it - %% is an unconditional branch to a phi node, or because - %% one or more of the variables that are not set will be - %% used. Try to follow branches of this `br`, to find a - %% safe `br`. - case Br of - #b_br{bool=#b_literal{val=true},succ=L} -> - case Target of - L -> - %% We have reached the forced target, and it - %% is unsafe. Give up. - none; - _ -> - %% Try following this branch to see whether it - %% leads to a safe `br`. - shortcut_2(L, Bs, UnsetVars, St) - end; - #b_br{bool=#b_var{},succ=Succ,fail=Fail} -> - case {Succ,Fail} of - {L,Target} -> - %% The failure label is the forced target. - %% Try following the success label to see - %% whether it also ultimately ends up at the - %% forced target. - shortcut_2(L, Bs, UnsetVars, St); - {Target,L} -> - %% The success label is the forced target. - %% Try following the failure label to see - %% whether it also ultimately ends up at the - %% forced target. - shortcut_2(L, Bs, UnsetVars, St); - {_,_} -> - case Target of - any -> - %% This two-way branch is unsafe. Try reducing - %% it to a one-way branch. - shortcut_two_way(Br, Bs, UnsetVars, St); - one_way -> - %% This two-way branch is unsafe. Try reducing - %% it to a one-way branch. - shortcut_two_way(Br, Bs, UnsetVars, St); - _ when is_integer(Target) -> - %% This two-way branch is unsafe, and - %% there already is a forced target. - %% Give up. - none - end - end - end; + shortcut_unsafe_br(Br, From, Bs, UnsetVars, St); true -> - %% This `br` instruction is safe. It does not - %% branch to a phi node, and all variables that - %% will be used are guaranteed to be defined. - case Br of - #b_br{bool=#b_literal{val=true},succ=L} -> - %% This is a one-way branch. + shortcut_safe_br(Br, From, Bs, UnsetVars, St) + end. + +shortcut_unsafe_br(Br, From, Bs, UnsetVars, #st{target=Target}=St) -> + %% Branching using this `br` is unsafe, either because it + %% is an unconditional branch to a phi node, or because + %% one or more of the variables that are not set will be + %% used. Try to follow branches of this `br`, to find a + %% safe `br`. + case Br of + #b_br{bool=#b_literal{val=true},succ=L} -> + case Target of + L -> + %% We have reached the forced target, and it + %% is unsafe. Give up. + none; + _ -> + %% Try following this branch to see whether it + %% leads to a safe `br`. + shortcut_2(L, From, Bs, UnsetVars, St) + end; + #b_br{bool=#b_var{},succ=Succ,fail=Fail} -> + case {Succ,Fail} of + {L,Target} -> + %% The failure label is the forced target. + %% Try following the success label to see + %% whether it also ultimately ends up at the + %% forced target. + shortcut_2(L, From, Bs, UnsetVars, St); + {Target,L} -> + %% The success label is the forced target. + %% Try following the failure label to see + %% whether it also ultimately ends up at the + %% forced target. + shortcut_2(L, From, Bs, UnsetVars, St); + {_,_} -> case Target of any -> - %% No forced target. Success! - {Br,Bs,UnsetVars}; + %% This two-way branch is unsafe. Try + %% reducing it to a one-way branch. + shortcut_two_way(Br, From, Bs, UnsetVars, St); one_way -> - %% The target must be a one-way branch, which this - %% `br` is. Success! - {Br,Bs,UnsetVars}; - L when is_integer(Target) -> - %% The forced target is L. Success! - {Br,Bs,UnsetVars}; + %% This two-way branch is unsafe. Try + %% reducing it to a one-way branch. + shortcut_two_way(Br, From, Bs, UnsetVars, St); _ when is_integer(Target) -> - %% Wrong forced target. Try following this branch - %% to see if it ultimately ends up at the forced - %% target. - shortcut_2(L, Bs, UnsetVars, St) - end; - #b_br{bool=#b_var{}} -> - %% This is a two-way branch. - if - Target =:= any; Target =:= one_way -> - %% No specific forced target. Try to reduce the - %% two-way branch to an one-way branch. - case shortcut_two_way(Br, Bs, UnsetVars, St) of - none when Target =:= any -> - %% This `br` can't be reduced to a one-way - %% branch. Return the `br` as-is. - {Br,Bs,UnsetVars}; - none when Target =:= one_way -> - %% This `br` can't be reduced to a one-way - %% branch. The caller wants a one-way branch. - %% Give up. - none; - {_,_,_}=Res -> - %% This `br` was successfully reduced to a - %% one-way branch. - Res - end; - is_integer(Target) -> - %% There is a forced target, which can't - %% be reached because this `br` is a two-way - %% branch. Give up. + %% This two-way branch is unsafe, and + %% there already is a forced target. + %% Give up. none end end end. -update_unset_vars(L, Br, SetInThisBlock, UnsetVars, #st{skippable=Skippable}) -> +shortcut_safe_br(Br, From, Bs, UnsetVars, #st{target=Target}=St) -> + %% This `br` instruction is safe. It does not branch to a phi + %% node, and all variables that will be used are guaranteed to be + %% defined. + case Br of + #b_br{bool=#b_literal{val=true},succ=L} -> + %% This is a one-way branch. + case Target of + any -> + %% No forced target. Success! + {Br,Bs,UnsetVars}; + one_way -> + %% The target must be a one-way branch, which this + %% `br` is. Success! + {Br,Bs,UnsetVars}; + L when is_integer(Target) -> + %% The forced target is L. Success! + {Br,Bs,UnsetVars}; + _ when is_integer(Target) -> + %% Wrong forced target. Try following this branch + %% to see if it ultimately ends up at the forced + %% target. + shortcut_2(L, From, Bs, UnsetVars, St) + end; + #b_br{bool=#b_var{}} -> + %% This is a two-way branch. + if + Target =:= any; Target =:= one_way -> + %% No specific forced target. Try to reduce the + %% two-way branch to an one-way branch. + case shortcut_two_way(Br, From, Bs, UnsetVars, St) of + none when Target =:= any -> + %% This `br` can't be reduced to a one-way + %% branch. Return the `br` as-is. + {Br,Bs,UnsetVars}; + none when Target =:= one_way -> + %% This `br` can't be reduced to a one-way + %% branch. The caller wants a one-way + %% branch. Give up. + none; + {_,_,_}=Res -> + %% This `br` was successfully reduced to a + %% one-way branch. + Res + end; + is_integer(Target) -> + %% There is a forced target, which can't + %% be reached because this `br` is a two-way + %% branch. Give up. + none + end + end. + +update_unset_vars(L, Is, Br, UnsetVars, #st{skippable=Skippable}) -> case is_map_key(L, Skippable) of true -> %% None of the variables used in this block are used in - %% the successors. We can speed up compilation by avoiding - %% adding variables to the UnsetVars if the presence of - %% those variable would not change the outcome of the - %% tests in is_br_safe/2. + %% the successors. Thus, there is no need to add the + %% variables to the set of unset variables. case Br of - #b_br{bool=Bool} -> - case member(Bool, SetInThisBlock) of + #b_br{bool=#b_var{}=Bool} -> + case keymember(Bool, #b_set.dst, Is) of true -> %% Bool is a variable defined in this - %% block. It will change the outcome of - %% the `not member(V, UnsetVars)` check in - %% is_br_safe/2. The other variables - %% defined in this block will not. - ordsets:add_element(Bool, UnsetVars); + %% block. Using the br instruction from + %% this block (and skipping the body of + %% the block) is unsafe. + unsafe; false -> %% Bool is either a variable not defined %% in this block or a literal. Adding it @@ -321,18 +339,24 @@ update_unset_vars(L, Br, SetInThisBlock, UnsetVars, #st{skippable=Skippable}) -> %% the outcome of the tests in %% is_br_safe/2. UnsetVars - end + end; + #b_br{} -> + UnsetVars end; false -> + %% Some variables defined in this block are used by + %% successors. We must update the set of unset variables. + SetInThisBlock = [V || #b_set{dst=V} <- Is], ordsets:union(UnsetVars, ordsets:from_list(SetInThisBlock)) end. -shortcut_two_way(#b_br{succ=Succ,fail=Fail}, Bs0, UnsetVars0, St) -> - case shortcut_2(Succ, Bs0, UnsetVars0, St#st{target=Fail}) of +shortcut_two_way(#b_br{succ=Succ,fail=Fail}, From, Bs0, UnsetVars0, St0) -> + case shortcut_2(Succ, From, Bs0, UnsetVars0, St0#st{target=Fail}) of {#b_br{bool=#b_literal{},succ=Fail},_,_}=Res -> Res; none -> - case shortcut_2(Fail, Bs0, UnsetVars0, St#st{target=Succ}) of + St = St0#st{target=Succ}, + case shortcut_2(Fail, From, Bs0, UnsetVars0, St) of {#b_br{bool=#b_literal{},succ=Succ},_,_}=Res -> Res; none -> @@ -374,40 +398,42 @@ is_forbidden(L, St) -> %% Return the updated bindings, or 'none' if there is %% any instruction with potential side effects. -eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], Bs0, St) -> - From = map_get(from, Bs0), - [Val] = [Val || {Val,Pred} <- Args, Pred =:= From], +eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], From, Bs0, St) -> + Val = get_phi_arg(Args, From), Bs = bind_var(Dst, Val, Bs0), - eval_is(Is, Bs, St); -eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], Bs, St) -> + eval_is(Is, From, Bs, St); +eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], From, Bs, St) -> I = sub(I0, Bs), case eval_bif(I, St) of #b_literal{}=Val -> - eval_is(Is, bind_var(Dst, Val, Bs), St); + eval_is(Is, From, bind_var(Dst, Val, Bs), St); none -> - eval_is(Is, Bs, St) + eval_is(Is, From, Bs, St) end; -eval_is([#b_set{op=Op,dst=Dst}=I|Is], Bs, St) +eval_is([#b_set{op=Op,dst=Dst}=I|Is], From, Bs, St) when Op =:= is_tagged_tuple; Op =:= is_nonempty_list -> #b_set{args=Args} = sub(I, Bs), case eval_rel_op(Op, Args, St) of #b_literal{}=Val -> - eval_is(Is, bind_var(Dst, Val, Bs), St); + eval_is(Is, From, bind_var(Dst, Val, Bs), St); none -> - eval_is(Is, Bs, St) + eval_is(Is, From, Bs, St) end; -eval_is([#b_set{}=I|Is], Bs, St) -> +eval_is([#b_set{}=I|Is], From, Bs, St) -> case beam_ssa:no_side_effect(I) of true -> %% This instruction has no side effects. It can %% safely be omitted. - eval_is(Is, Bs, St); + eval_is(Is, From, Bs, St); false -> %% This instruction may have some side effect. %% It is not safe to avoid this instruction. none end; -eval_is([], Bs, _St) -> Bs. +eval_is([], _From, Bs, _St) -> Bs. + +get_phi_arg([{Val,From}|_], From) -> Val; +get_phi_arg([_|As], From) -> get_phi_arg(As, From). eval_terminator(#b_br{bool=#b_var{}=Bool}=Br, Bs, _St) -> Val = get_value(Bool, Bs), @@ -477,20 +503,31 @@ eval_bif(#b_set{op={bif,Bif},args=Args}, St) -> false -> none; true -> - case [Lit || #b_literal{val=Lit} <- Args] of - LitArgs when length(LitArgs) =:= Arity -> + case get_lit_args(Args) of + none -> + %% Not literal arguments. Try to evaluate + %% it based on a previous relational operator. + eval_rel_op({bif,Bif}, Args, St); + LitArgs -> try apply(erlang, Bif, LitArgs) of Val -> #b_literal{val=Val} catch error:_ -> none - end; - _ -> - %% Not literal arguments. Try to evaluate - %% it based on a previous relational operator. - eval_rel_op({bif,Bif}, Args, St) + end end end. +get_lit_args([#b_literal{val=Lit1}]) -> + [Lit1]; +get_lit_args([#b_literal{val=Lit1}, + #b_literal{val=Lit2}]) -> + [Lit1,Lit2]; +get_lit_args([#b_literal{val=Lit1}, + #b_literal{val=Lit2}, + #b_literal{val=Lit3}]) -> + [Lit1,Lit2,Lit3]; +get_lit_args(_) -> none. + %%% %%% Handling of relational operators. %%% @@ -1026,11 +1063,12 @@ used_vars_is([], Used) -> sub(#b_set{args=Args}=I, Sub) -> I#b_set{args=[sub_arg(A, Sub) || A <- Args]}. -sub_arg(Old, Sub) -> +sub_arg(#b_var{}=Old, Sub) -> case Sub of #{Old:=New} -> New; #{} -> Old - end. + end; +sub_arg(Old, _Sub) -> Old. rel2fam(S0) -> S1 = sofs:relation(S0), diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 6e548dd529..bcf55f3fda 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -175,6 +175,7 @@ epilogue_passes(Opts) -> ?PASS(ssa_opt_blockify), ?PASS(ssa_opt_sink), ?PASS(ssa_opt_merge_blocks), + ?PASS(ssa_opt_get_tuple_element), ?PASS(ssa_opt_trim_unreachable)], passes_1(Ps, Opts). @@ -682,6 +683,14 @@ record_opt_is([#b_set{op={bif,is_tuple},dst=Bool,args=[Tuple]}=Set], no -> [Set] end; +record_opt_is([I|Is]=Is0, #b_br{bool=Bool}=Last, Blocks) -> + case is_tagged_tuple_1(Is0, Last, Blocks) of + {yes,_Fail,Tuple,Arity,Tag} -> + Args = [Tuple,Arity,Tag], + [I#b_set{op=is_tagged_tuple,dst=Bool,args=Args}]; + no -> + [I|record_opt_is(Is, Last, Blocks)] + end; record_opt_is([I|Is], Last, Blocks) -> [I|record_opt_is(Is, Last, Blocks)]; record_opt_is([], _Last, _Blocks) -> []. @@ -689,29 +698,30 @@ record_opt_is([], _Last, _Blocks) -> []. is_tagged_tuple(#b_var{}=Tuple, Bool, #b_br{bool=Bool,succ=Succ,fail=Fail}, Blocks) -> - SuccBlk = map_get(Succ, Blocks), - is_tagged_tuple_1(SuccBlk, Tuple, Fail, Blocks); + #b_blk{is=Is,last=Last} = map_get(Succ, Blocks), + case is_tagged_tuple_1(Is, Last, Blocks) of + {yes,Fail,Tuple,Arity,Tag} -> + {yes,Arity,Tag}; + _ -> + no + end; is_tagged_tuple(_, _, _, _) -> no. -is_tagged_tuple_1(#b_blk{is=Is,last=Last}, Tuple, Fail, Blocks) -> - case Is of - [#b_set{op={bif,tuple_size},dst=ArityVar, - args=[#b_var{}=Tuple]}, - #b_set{op={bif,'=:='}, - dst=Bool, - args=[ArityVar, #b_literal{val=ArityVal}=Arity]}] - when is_integer(ArityVal) -> - case Last of - #b_br{bool=Bool,succ=Succ,fail=Fail} -> - SuccBlk = map_get(Succ, Blocks), - case is_tagged_tuple_2(SuccBlk, Tuple, Fail) of - no -> - no; - {yes,Tag} -> - {yes,Arity,Tag} - end; - _ -> - no +is_tagged_tuple_1(Is, Last, Blocks) -> + case {Is,Last} of + {[#b_set{op={bif,tuple_size},dst=ArityVar, + args=[#b_var{}=Tuple]}, + #b_set{op={bif,'=:='}, + dst=Bool, + args=[ArityVar, #b_literal{val=ArityVal}=Arity]}], + #b_br{bool=Bool,succ=Succ,fail=Fail}} + when is_integer(ArityVal) -> + SuccBlk = map_get(Succ, Blocks), + case is_tagged_tuple_2(SuccBlk, Tuple, Fail) of + no -> + no; + {yes,Tag} -> + {yes,Fail,Tuple,Arity,Tag} end; _ -> no @@ -2174,6 +2184,46 @@ insert_def_is([#b_set{op=Op}=I|Is]=Is0, V, Def) -> insert_def_is([], _V, Def) -> [Def]. +%%% +%%% Order consecutive get_tuple_element instructions in ascending +%%% position order. This will give the loader more opportunities +%%% for combining get_tuple_element instructions. +%%% + +ssa_opt_get_tuple_element({#st{ssa=Blocks0}=St, FuncDb}) -> + Blocks = opt_get_tuple_element(maps:to_list(Blocks0), Blocks0), + {St#st{ssa=Blocks}, FuncDb}. + +opt_get_tuple_element([{L,#b_blk{is=Is0}=Blk0}|Bs], Blocks) -> + case opt_get_tuple_element_is(Is0, false, []) of + {yes,Is} -> + Blk = Blk0#b_blk{is=Is}, + opt_get_tuple_element(Bs, Blocks#{L:=Blk}); + no -> + opt_get_tuple_element(Bs, Blocks) + end; +opt_get_tuple_element([], Blocks) -> Blocks. + +opt_get_tuple_element_is([#b_set{op=get_tuple_element, + args=[#b_var{}=Src,_]}=I0|Is0], + _AnyChange, Acc) -> + {GetIs0,Is} = collect_get_tuple_element(Is0, Src, [I0]), + GetIs1 = sort([{Pos,I} || #b_set{args=[_,Pos]}=I <- GetIs0]), + GetIs = [I || {_,I} <- GetIs1], + opt_get_tuple_element_is(Is, true, reverse(GetIs, Acc)); +opt_get_tuple_element_is([I|Is], AnyChange, Acc) -> + opt_get_tuple_element_is(Is, AnyChange, [I|Acc]); +opt_get_tuple_element_is([], AnyChange, Acc) -> + case AnyChange of + true -> {yes,reverse(Acc)}; + false -> no + end. + +collect_get_tuple_element([#b_set{op=get_tuple_element, + args=[Src,_]}=I|Is], Src, Acc) -> + collect_get_tuple_element(Is, Src, [I|Acc]); +collect_get_tuple_element(Is, _Src, Acc) -> + {Acc,Is}. %%% %%% Common utilities. diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 296c095be2..ab8caa1a0d 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -579,7 +579,11 @@ valfun_1({get_tuple_element,Src,N,Dst}, Vst) -> Type = get_element_type(Index, Src, Vst), extract_term(Type, {bif,element}, [Index, Src], Dst, Vst); valfun_1({jump,{f,Lbl}}, Vst) -> - kill_state(branch_state(Lbl, Vst)); + branch(Lbl, Vst, + fun(SuccVst) -> + %% The next instruction is never executed. + kill_state(SuccVst) + end); valfun_1(I, Vst) -> valfun_2(I, Vst). @@ -589,14 +593,17 @@ init_try_catch_branch(Tag, Dst, Fail, Vst0) -> St = St0#st{ct=[[Fail]|Fails]}, Vst = Vst0#vst{current=St}, - complex_test(Fail, - fun(CatchVst) -> - #vst{current=#st{ys=Ys}} = CatchVst, - maps:fold(fun init_catch_handler_1/3, CatchVst, Ys) - end, - fun(SuccVst) -> - SuccVst - end, Vst). + branch(Fail, Vst, + fun(CatchVst) -> + #vst{current=#st{ys=Ys}} = CatchVst, + maps:fold(fun init_catch_handler_1/3, CatchVst, Ys) + end, + fun(SuccVst) -> + %% All potentially-throwing instructions after this + %% one will implicitly branch to the fail label; + %% see valfun_2/2 + SuccVst + end). %% Set the initial state at the try/catch label. Assume that Y registers %% contain terms or try/catch tags. @@ -607,21 +614,27 @@ init_catch_handler_1(Reg, uninitialized, Vst) -> init_catch_handler_1(_, _, Vst) -> Vst. -%% Update branched state if necessary and try next set of instructions. -valfun_2(I, #vst{current=#st{ct=[]}}=Vst) -> - valfun_3(I, Vst); valfun_2(I, #vst{current=#st{ct=[[Fail]|_]}}=Vst) when is_integer(Fail) -> - %% Update branched state. + %% We have an active try/catch tag and we can jump there from this + %% instruction, so we need to update the branched state of the try/catch + %% handler. valfun_3(I, branch_state(Fail, Vst)); +valfun_2(I, #vst{current=#st{ct=[]}}=Vst) -> + valfun_3(I, Vst); valfun_2(_, _) -> error(ambiguous_catch_try_state). %% Handle the remaining floating point instructions here. %% Floating point. -valfun_3({fconv,Src,{fr,_}=Dst}, Vst0) -> - assert_term(Src, Vst0), - Vst = update_type(fun meet/2, number, Src, Vst0), - set_freg(Dst, Vst); +valfun_3({fconv,Src,{fr,_}=Dst}, Vst) -> + assert_term(Src, Vst), + + %% An exception is raised on error, hence branching to 0. + branch(0, Vst, + fun(SuccVst0) -> + SuccVst = update_type(fun meet/2, number, Src, SuccVst0), + set_freg(Dst, SuccVst) + end); valfun_3({bif,fadd,_,[_,_]=Ss,Dst}, Vst) -> float_op(Ss, Dst, Vst); valfun_3({bif,fdiv,_,[_,_]=Ss,Dst}, Vst) -> @@ -682,67 +695,87 @@ valfun_4({call_ext_last,_,_,_}, #vst{current=#st{numy=NumY}}) -> valfun_4({make_fun2,_,_,_,Live}, Vst) -> call(make_fun, Live, Vst); %% Other BIFs -valfun_4({bif,element,{f,Fail},[Pos,Tuple],Dst}, Vst0) -> - PosType = get_term_type(Pos, Vst0), - ElementType = get_element_type(PosType, Tuple, Vst0), - InferredType = {tuple,[get_tuple_size(PosType)],#{}}, - Vst1 = branch_state(Fail, Vst0), - Vst2 = update_type(fun meet/2, InferredType, Tuple, Vst1), - Vst = update_type(fun meet/2, {integer,[]}, Pos, Vst2), - extract_term(ElementType, {bif,element}, [Pos,Tuple], Dst, Vst); +valfun_4({bif,element,{f,Fail},[Pos,Src],Dst}, Vst) -> + branch(Fail, Vst, + fun(SuccVst0) -> + PosType = get_term_type(Pos, SuccVst0), + TupleType = {tuple,[get_tuple_size(PosType)],#{}}, + + SuccVst1 = update_type(fun meet/2, TupleType, + Src, SuccVst0), + SuccVst = update_type(fun meet/2, {integer,[]}, + Pos, SuccVst1), + + ElementType = get_element_type(PosType, Src, SuccVst), + extract_term(ElementType, {bif,element}, [Pos,Src], + Dst, SuccVst) + end); valfun_4({bif,raise,{f,0},Src,_Dst}, Vst) -> validate_src(Src, Vst), kill_state(Vst); valfun_4(raw_raise=I, Vst) -> call(I, 3, Vst); -valfun_4({bif,Op,{f,Fail},[Cons]=Ss,Dst}, Vst0) - when Op =:= hd; Op =:= tl -> - validate_src(Ss, Vst0), - Vst = type_test(Fail, cons, Cons, Vst0), - Type = bif_return_type(Op, Ss, Vst), - extract_term(Type, {bif,Op}, Ss, Dst, Vst); -valfun_4({bif,Op,{f,Fail},Ss,Dst}, Vst0) -> - validate_src(Ss, Vst0), - Vst1 = branch_state(Fail, Vst0), - - %% Infer argument types. Note that we can't type_test in the general case - %% as the BIF could fail for reasons other than bad argument types. - ArgTypes = bif_arg_types(Op, Ss), - Vst = foldl(fun({Arg, T}, Vsti) -> - update_type(fun meet/2, T, Arg, Vsti) - end, Vst1, zip(Ss, ArgTypes)), - - Type = bif_return_type(Op, Ss, Vst), - extract_term(Type, {bif,Op}, Ss, Dst, Vst); +valfun_4({bif,Op,{f,Fail},[Src]=Ss,Dst}, Vst) when Op =:= hd; Op =:= tl -> + assert_term(Src, Vst), + branch(Fail, Vst, + fun(FailVst) -> + update_type(fun subtract/2, cons, Src, FailVst) + end, + fun(SuccVst0) -> + SuccVst = update_type(fun meet/2, cons, Src, SuccVst0), + extract_term(term, {bif,Op}, Ss, Dst, SuccVst) + end); +valfun_4({bif,Op,{f,Fail},Ss,Dst}, Vst) -> + validate_src(Ss, Vst), + branch(Fail, Vst, + fun(SuccVst0) -> + %% Infer argument types. Note that we can't subtract + %% types as the BIF could fail for reasons other than + %% bad argument types. + ArgTypes = bif_arg_types(Op, Ss), + SuccVst = foldl(fun({Arg, T}, V) -> + update_type(fun meet/2, T, Arg, V) + end, SuccVst0, zip(Ss, ArgTypes)), + Type = bif_return_type(Op, Ss, SuccVst), + extract_term(Type, {bif,Op}, Ss, Dst, SuccVst) + end); valfun_4({gc_bif,Op,{f,Fail},Live,Ss,Dst}, #vst{current=St0}=Vst0) -> validate_src(Ss, Vst0), verify_live(Live, Vst0), verify_y_init(Vst0), + + %% Heap allocations and X registers are killed regardless of whether we + %% fail or not, as we may fail after GC. St = kill_heap_allocation(St0), - Vst1 = Vst0#vst{current=St}, - Vst2 = branch_state(Fail, Vst1), + Vst = prune_x_regs(Live, Vst0#vst{current=St}), + + branch(Fail, Vst, + fun(SuccVst0) -> + ArgTypes = bif_arg_types(Op, Ss), + SuccVst = foldl(fun({Arg, T}, V) -> + update_type(fun meet/2, T, Arg, V) + end, SuccVst0, zip(Ss, ArgTypes)), - ArgTypes = bif_arg_types(Op, Ss), - Vst3 = foldl(fun({Arg, T}, Vsti) -> - update_type(fun meet/2, T, Arg, Vsti) - end, Vst2, zip(Ss, ArgTypes)), + Type = bif_return_type(Op, Ss, SuccVst), - Type = bif_return_type(Op, Ss, Vst3), - Vst = prune_x_regs(Live, Vst3), - extract_term(Type, {gc_bif,Op}, Ss, Dst, Vst, Vst0); + %% We're passing Vst0 as the original because the + %% registers were pruned before the branch. + extract_term(Type, {gc_bif,Op}, Ss, Dst, SuccVst, Vst0) + end); valfun_4(return, #vst{current=#st{numy=none}}=Vst) -> assert_durable_term({x,0}, Vst), kill_state(Vst); valfun_4(return, #vst{current=#st{numy=NumY}}) -> error({stack_frame,NumY}); -valfun_4({loop_rec,{f,Fail},Dst}, Vst0) -> - %% This term may not be part of the root set until - %% remove_message/0 is executed. If control transfers - %% to the loop_rec_end/1 instruction, no part of - %% this term must be stored in a Y register. - Vst1 = branch_state(Fail, Vst0), - {Ref, Vst} = new_value(term, loop_rec, [], Vst1), - mark_fragile(Dst, set_reg_vref(Ref, Dst, Vst)); +valfun_4({loop_rec,{f,Fail},Dst}, Vst) -> + %% This term may not be part of the root set until remove_message/0 is + %% executed. If control transfers to the loop_rec_end/1 instruction, no + %% part of this term must be stored in a Y register. + branch(Fail, Vst, + fun(SuccVst0) -> + {Ref, SuccVst} = new_value(term, loop_rec, [], SuccVst0), + mark_fragile(Dst, set_reg_vref(Ref, Dst, SuccVst)) + end); valfun_4({wait,_}, Vst) -> verify_y_init(Vst), kill_state(Vst); @@ -769,14 +802,14 @@ valfun_4({set_tuple_element,Src,Tuple,N}, Vst) -> Es = set_element_type({integer,I}, get_term_type(Src, Vst), Es0), override_type({tuple, Sz, Es}, Tuple, Vst); %% Match instructions. -valfun_4({select_val,Src,{f,Fail},{list,Choices}}, Vst0) -> - assert_term(Src, Vst0), +valfun_4({select_val,Src,{f,Fail},{list,Choices}}, Vst) -> + assert_term(Src, Vst), assert_choices(Choices), - select_val_branches(Fail, Src, Choices, Vst0); + validate_select_val(Fail, Choices, Src, Vst); valfun_4({select_tuple_arity,Tuple,{f,Fail},{list,Choices}}, Vst) -> assert_type(tuple, Tuple, Vst), assert_arities(Choices), - select_arity_branches(Fail, Choices, Tuple, Vst); + validate_select_tuple_arity(Fail, Choices, Tuple, Vst); %% New bit syntax matching instructions. valfun_4({test,bs_start_match3,{f,Fail},Live,[Src],Dst}, Vst) -> @@ -785,17 +818,17 @@ 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), - branch_state(Fail, 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_term(Src, Vst), - branch_state(Fail, Vst); + branch(Fail, Vst, fun(V) -> V end); valfun_4({test,bs_test_tail2,{f,Fail},[Ctx,_]}, Vst) -> bsm_validate_context(Ctx, Vst), - branch_state(Fail, Vst); + branch(Fail, Vst, fun(V) -> V end); valfun_4({test,bs_test_unit,{f,Fail},[Ctx,_]}, Vst) -> bsm_validate_context(Ctx, Vst), - branch_state(Fail, 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); valfun_4({test,bs_skip_utf16,{f,Fail},[Ctx,Live,_]}, Vst) -> @@ -830,6 +863,10 @@ valfun_4({bs_set_position, Ctx, Pos}, Vst) -> Vst; %% Other test instructions. +valfun_4({test,has_map_fields,{f,Lbl},Src,{list,List}}, Vst) -> + assert_type(map, Src, Vst), + assert_unique_map_keys(List), + branch(Lbl, Vst, fun(V) -> V end); valfun_4({test,is_atom,{f,Lbl},[Src]}, Vst) -> type_test(Lbl, {atom,[]}, Src, Vst); valfun_4({test,is_binary,{f,Lbl},[Src]}, Vst) -> @@ -850,70 +887,68 @@ valfun_4({test,is_number,{f,Lbl},[Src]}, Vst) -> type_test(Lbl, number, Src, Vst); valfun_4({test,is_list,{f,Lbl},[Src]}, Vst) -> type_test(Lbl, list, Src, Vst); +valfun_4({test,is_map,{f,Lbl},[Src]}, Vst) -> + type_test(Lbl, map, Src, Vst); valfun_4({test,is_nil,{f,Lbl},[Src]}, Vst) -> %% is_nil is an exact check against the 'nil' value, and should not be %% treated as a simple type test. assert_term(Src, Vst), - complex_test(Lbl, - fun(FailVst) -> - update_ne_types(Src, nil, FailVst) - end, - fun(SuccVst) -> - update_eq_types(Src, nil, SuccVst) - end, Vst); -valfun_4({test,is_map,{f,Lbl},[Src]}, Vst) -> - case Src of - {Tag,_} when Tag =:= x; Tag =:= y -> - type_test(Lbl, map, Src, Vst); - {literal,Map} when is_map(Map) -> - Vst; - _ -> - assert_term(Src, Vst), - kill_state(Vst) - end; -valfun_4({test,test_arity,{f,Lbl},[Tuple,Sz]}, Vst0) when is_integer(Sz) -> - assert_type(tuple, Tuple, Vst0), - Vst = branch_state(Lbl, Vst0), - update_type(fun meet/2, {tuple,Sz,#{}}, Tuple, Vst); -valfun_4({test,is_tagged_tuple,{f,Lbl},[Src,Sz,Atom]}, Vst0) -> - assert_term(Src, Vst0), - Vst = branch_state(Lbl, Vst0), - update_type(fun meet/2, {tuple,Sz,#{ {integer,1} => Atom }}, Src, Vst); -valfun_4({test,has_map_fields,{f,Lbl},Src,{list,List}}, Vst) -> - assert_type(map, Src, Vst), - assert_unique_map_keys(List), - branch_state(Lbl, Vst); + branch(Lbl, Vst, + fun(FailVst) -> + update_ne_types(Src, nil, FailVst) + end, + fun(SuccVst) -> + update_eq_types(Src, nil, SuccVst) + end); +valfun_4({test,test_arity,{f,Lbl},[Tuple,Sz]}, Vst) when is_integer(Sz) -> + assert_type(tuple, Tuple, Vst), + Type = {tuple, Sz, #{}}, + type_test(Lbl, Type, Tuple, Vst); +valfun_4({test,is_tagged_tuple,{f,Lbl},[Src,Sz,Atom]}, Vst) -> + assert_term(Src, Vst), + Type = {tuple, Sz, #{ {integer,1} => Atom }}, + type_test(Lbl, Type, Src, Vst); valfun_4({test,is_eq_exact,{f,Lbl},[Src,Val]=Ss}, Vst) -> validate_src(Ss, Vst), - complex_test(Lbl, - fun(FailVst) -> - update_ne_types(Src, Val, FailVst) - end, - fun(SuccVst) -> - update_eq_types(Src, Val, SuccVst) - end, Vst); + branch(Lbl, Vst, + fun(FailVst) -> + update_ne_types(Src, Val, FailVst) + end, + fun(SuccVst) -> + update_eq_types(Src, Val, SuccVst) + end); valfun_4({test,is_ne_exact,{f,Lbl},[Src,Val]=Ss}, Vst) -> validate_src(Ss, Vst), - complex_test(Lbl, - fun(FailVst) -> - update_eq_types(Src, Val, FailVst) - end, - fun(SuccVst) -> - update_ne_types(Src, Val, SuccVst) - end, Vst); + branch(Lbl, Vst, + fun(FailVst) -> + update_eq_types(Src, Val, FailVst) + end, + fun(SuccVst) -> + update_ne_types(Src, Val, SuccVst) + end); valfun_4({test,_Op,{f,Lbl},Src}, Vst) -> + %% is_pid, is_reference, et cetera. validate_src(Src, Vst), - branch_state(Lbl, Vst); + branch(Lbl, Vst, fun(V) -> V end); valfun_4({bs_add,{f,Fail},[A,B,_],Dst}, Vst) -> assert_term(A, Vst), assert_term(B, Vst), - create_term({integer,[]}, bs_add, [A, B], Dst, branch_state(Fail, Vst)); + branch(Fail, Vst, + fun(SuccVst) -> + create_term({integer,[]}, bs_add, [A, B], Dst, SuccVst) + end); valfun_4({bs_utf8_size,{f,Fail},A,Dst}, Vst) -> assert_term(A, Vst), - create_term({integer,[]}, bs_utf8_size, [A], Dst, branch_state(Fail, Vst)); + branch(Fail, Vst, + fun(SuccVst) -> + create_term({integer,[]}, bs_utf8_size, [A], Dst, SuccVst) + end); valfun_4({bs_utf16_size,{f,Fail},A,Dst}, Vst) -> assert_term(A, Vst), - create_term({integer,[]}, bs_utf16_size, [A], Dst, branch_state(Fail, Vst)); + branch(Fail, Vst, + fun(SuccVst) -> + create_term({integer,[]}, bs_utf16_size, [A], Dst, SuccVst) + end); valfun_4({bs_init2,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) -> verify_live(Live, Vst0), verify_y_init(Vst0), @@ -923,10 +958,12 @@ valfun_4({bs_init2,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) -> true -> assert_term(Sz, Vst0) end, - Vst1 = heap_alloc(Heap, Vst0), - Vst2 = branch_state(Fail, Vst1), - Vst = prune_x_regs(Live, Vst2), - create_term(binary, bs_init2, [], Dst, Vst, Vst0); + Vst = heap_alloc(Heap, Vst0), + branch(Fail, Vst, + fun(SuccVst0) -> + SuccVst = prune_x_regs(Live, SuccVst0), + create_term(binary, bs_init2, [], Dst, SuccVst, SuccVst0) + end); valfun_4({bs_init_bits,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) -> verify_live(Live, Vst0), verify_y_init(Vst0), @@ -936,47 +973,71 @@ valfun_4({bs_init_bits,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) -> true -> assert_term(Sz, Vst0) end, - Vst1 = heap_alloc(Heap, Vst0), - Vst2 = branch_state(Fail, Vst1), - Vst = prune_x_regs(Live, Vst2), - create_term(binary, bs_init_bits, [], Dst, Vst); + Vst = heap_alloc(Heap, Vst0), + branch(Fail, Vst, + fun(SuccVst0) -> + SuccVst = prune_x_regs(Live, SuccVst0), + create_term(binary, bs_init_bits, [], Dst, SuccVst) + end); valfun_4({bs_append,{f,Fail},Bits,Heap,Live,_Unit,Bin,_Flags,Dst}, Vst0) -> verify_live(Live, Vst0), verify_y_init(Vst0), assert_term(Bits, Vst0), assert_term(Bin, Vst0), - Vst1 = heap_alloc(Heap, Vst0), - Vst2 = branch_state(Fail, Vst1), - Vst = prune_x_regs(Live, Vst2), - create_term(binary, bs_append, [Bin], Dst, Vst, Vst0); -valfun_4({bs_private_append,{f,Fail},Bits,_Unit,Bin,_Flags,Dst}, Vst0) -> - assert_term(Bits, Vst0), - assert_term(Bin, Vst0), - Vst = branch_state(Fail, Vst0), - create_term(binary, bs_private_append, [Bin], Dst, Vst); + Vst = heap_alloc(Heap, Vst0), + branch(Fail, Vst, + fun(SuccVst0) -> + SuccVst = prune_x_regs(Live, SuccVst0), + create_term(binary, bs_append, [Bin], Dst, SuccVst, SuccVst0) + end); +valfun_4({bs_private_append,{f,Fail},Bits,_Unit,Bin,_Flags,Dst}, Vst) -> + assert_term(Bits, Vst), + assert_term(Bin, Vst), + branch(Fail, Vst, + fun(SuccVst) -> + create_term(binary, bs_private_append, [Bin], Dst, SuccVst) + end); valfun_4({bs_put_string,Sz,_}, Vst) when is_integer(Sz) -> Vst; valfun_4({bs_put_binary,{f,Fail},Sz,_,_,Src}, Vst) -> assert_term(Sz, Vst), assert_term(Src, Vst), - branch_state(Fail, Vst); + branch(Fail, Vst, + fun(SuccVst) -> + update_type(fun meet/2, binary, Src, SuccVst) + end); valfun_4({bs_put_float,{f,Fail},Sz,_,_,Src}, Vst) -> assert_term(Sz, Vst), assert_term(Src, Vst), - branch_state(Fail, Vst); + branch(Fail, Vst, + fun(SuccVst) -> + update_type(fun meet/2, {float,[]}, Src, SuccVst) + end); valfun_4({bs_put_integer,{f,Fail},Sz,_,_,Src}, Vst) -> assert_term(Sz, Vst), assert_term(Src, Vst), - branch_state(Fail, Vst); + branch(Fail, Vst, + fun(SuccVst) -> + update_type(fun meet/2, {integer,[]}, Src, SuccVst) + end); valfun_4({bs_put_utf8,{f,Fail},_,Src}, Vst) -> assert_term(Src, Vst), - branch_state(Fail, Vst); + branch(Fail, Vst, + fun(SuccVst) -> + update_type(fun meet/2, {integer,[]}, Src, SuccVst) + end); valfun_4({bs_put_utf16,{f,Fail},_,Src}, Vst) -> assert_term(Src, Vst), - branch_state(Fail, Vst); + branch(Fail, Vst, + fun(SuccVst) -> + update_type(fun meet/2, {integer,[]}, Src, SuccVst) + end); valfun_4({bs_put_utf32,{f,Fail},_,Src}, Vst) -> assert_term(Src, Vst), - branch_state(Fail, Vst); + branch(Fail, Vst, + fun(SuccVst) -> + update_type(fun meet/2, {integer,[]}, Src, SuccVst) + end); %% Map instructions. valfun_4({put_map_assoc=Op,{f,Fail},Src,Dst,Live,{list,List}}, Vst) -> verify_put_map(Op, Fail, Src, Dst, Live, List, Vst); @@ -991,15 +1052,15 @@ verify_get_map(Fail, Src, List, Vst0) -> assert_not_literal(Src), %OTP 22. assert_type(map, Src, Vst0), - complex_test(Fail, - fun(FailVst) -> - clobber_map_vals(List, Src, FailVst) - end, - fun(SuccVst) -> - Keys = extract_map_keys(List), - assert_unique_map_keys(Keys), - extract_map_vals(List, Src, SuccVst, SuccVst) - end, Vst0). + branch(Fail, Vst0, + fun(FailVst) -> + clobber_map_vals(List, Src, FailVst) + end, + fun(SuccVst) -> + Keys = extract_map_keys(List), + assert_unique_map_keys(Keys), + extract_map_vals(List, Src, SuccVst, SuccVst) + end). %% get_map_elements may leave its destinations in an inconsistent state when %% the fail label is taken. Consider the following: @@ -1033,13 +1094,16 @@ verify_put_map(Op, Fail, Src, Dst, Live, List, Vst0) -> assert_type(map, Src, Vst0), verify_live(Live, Vst0), verify_y_init(Vst0), - [assert_term(Term, Vst0) || Term <- List], - Vst1 = heap_alloc(0, Vst0), - Vst2 = branch_state(Fail, Vst1), - Vst = prune_x_regs(Live, Vst2), - Keys = extract_map_keys(List), - assert_unique_map_keys(Keys), - create_term(map, Op, [Src], Dst, Vst, Vst0). + _ = [assert_term(Term, Vst0) || Term <- List], + Vst = heap_alloc(0, Vst0), + + branch(Fail, Vst, + fun(SuccVst0) -> + SuccVst = prune_x_regs(Live, SuccVst0), + Keys = extract_map_keys(List), + assert_unique_map_keys(Keys), + create_term(map, Op, [Src], Dst, SuccVst, SuccVst0) + end). %% %% Common code for validating bs_start_match* instructions. @@ -1052,40 +1116,60 @@ validate_bs_start_match(Fail, Live, Type, Src, Dst, Vst) -> %% #ms{} can represent either a match context or a term, so we have to mark %% the source as a term if it fails with a match context as an input. This %% hack is only needed until we get proper union types. - complex_test(Fail, - fun(FailVst) -> - case get_raw_type(Src, FailVst) of - #ms{} -> override_type(term, Src, FailVst); - _ -> FailVst - end - end, - fun(SuccVst0) -> - SuccVst1 = update_type(fun meet/2, binary, Src, SuccVst0), - SuccVst = prune_x_regs(Live, SuccVst1), - extract_term(Type, bs_start_match, [Src], Dst, - SuccVst, SuccVst0) - end, Vst). + branch(Fail, Vst, + fun(FailVst) -> + case get_movable_term_type(Src, FailVst) of + #ms{} -> override_type(term, Src, FailVst); + _ -> FailVst + end + end, + fun(SuccVst0) -> + SuccVst1 = update_type(fun meet/2, binary, + Src, SuccVst0), + SuccVst = prune_x_regs(Live, SuccVst1), + extract_term(Type, bs_start_match, [Src], Dst, + SuccVst, SuccVst0) + end). %% %% Common code for validating bs_get* instructions. %% -validate_bs_get(Op, Fail, Ctx, Live, Type, Dst, Vst0) -> - bsm_validate_context(Ctx, Vst0), - verify_live(Live, Vst0), - verify_y_init(Vst0), - Vst1 = prune_x_regs(Live, Vst0), - Vst = branch_state(Fail, Vst1), - extract_term(Type, Op, [Ctx], Dst, Vst, Vst0). +validate_bs_get(Op, Fail, Ctx, Live, Type, Dst, Vst) -> + bsm_validate_context(Ctx, Vst), + verify_live(Live, Vst), + verify_y_init(Vst), + + branch(Fail, Vst, + fun(SuccVst0) -> + SuccVst = prune_x_regs(Live, SuccVst0), + extract_term(Type, Op, [Ctx], Dst, SuccVst, SuccVst0) + end). %% %% Common code for validating bs_skip_utf* instructions. %% -validate_bs_skip_utf(Fail, Ctx, Live, Vst0) -> - bsm_validate_context(Ctx, Vst0), - verify_y_init(Vst0), - verify_live(Live, Vst0), - Vst = prune_x_regs(Live, Vst0), - branch_state(Fail, Vst). +validate_bs_skip_utf(Fail, Ctx, Live, Vst) -> + bsm_validate_context(Ctx, Vst), + verify_y_init(Vst), + verify_live(Live, Vst), + + branch(Fail, Vst, + fun(SuccVst) -> + prune_x_regs(Live, SuccVst) + end). + +%% +%% Common code for is_$type instructions. +%% +type_test(Fail, Type, Reg, Vst) -> + assert_term(Reg, Vst), + branch(Fail, Vst, + fun(FailVst) -> + update_type(fun subtract/2, Type, Reg, FailVst) + end, + fun(SuccVst) -> + update_type(fun meet/2, Type, Reg, SuccVst) + end). %% %% Special state handling for setelement/3 and set_tuple_element/3 instructions. @@ -1156,9 +1240,8 @@ verify_local_args(-1, _Lbl, _CtxIds, _Vst) -> ok; verify_local_args(X, Lbl, CtxIds, Vst) -> Reg = {x, X}, - assert_movable(Reg, Vst), assert_not_fragile(Reg, Vst), - case get_raw_type(Reg, Vst) of + case get_movable_term_type(Reg, Vst) of #ms{id=Id}=Type -> case CtxIds of #{ Id := Other } -> @@ -1347,7 +1430,7 @@ assert_arities(_) -> error(bad_tuple_arity_list). %%% float_op(Ss, Dst, Vst0) -> - [assert_freg_set(S, Vst0) || S <- Ss], + _ = [assert_freg_set(S, Vst0) || S <- Ss], assert_fls(cleared, Vst0), Vst = set_fls(cleared, Vst0), set_freg(Dst, Vst). @@ -1424,7 +1507,7 @@ bsm_validate_context(Reg, Vst) -> ok. bsm_get_context({Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y-> - case get_raw_type(Reg, Vst) of + case get_movable_term_type(Reg, Vst) of #ms{}=Ctx -> Ctx; _ -> error({no_bsm_context,Reg}) end; @@ -1459,44 +1542,46 @@ bsm_restore(Reg, SavePoint, Vst) -> _ -> error({illegal_restore,SavePoint,range}) end. -select_val_branches(Fail, Src, Choices, Vst0) -> - Vst = svb_1(Choices, Src, Vst0), - kill_state(branch_state(Fail, Vst)). - -svb_1([Val,{f,L}|T], Src, Vst0) -> - Vst = complex_test(L, - fun(BranchVst) -> - update_eq_types(Src, Val, BranchVst) - end, - fun(FailVst) -> - update_ne_types(Src, Val, FailVst) - end, Vst0), - svb_1(T, Src, Vst); -svb_1([], _, Vst) -> - Vst. - -select_arity_branches(Fail, List, Tuple, Vst0) -> - Type = get_term_type(Tuple, Vst0), - Vst = sab_1(List, Tuple, Type, Vst0), - kill_state(branch_state(Fail, Vst)). - -sab_1([Sz,{f,L}|T], Tuple, {tuple,[_],Es}=Type0, Vst0) -> - #vst{current=St0} = Vst0, - Vst1 = update_type(fun meet/2, {tuple,Sz,Es}, Tuple, Vst0), - Vst2 = branch_state(L, Vst1), - Vst = Vst2#vst{current=St0}, - - sab_1(T, Tuple, Type0, Vst); -sab_1([Sz,{f,L}|T], Tuple, {tuple,Sz,_Es}=Type, Vst0) -> - %% The type is already correct. (This test is redundant.) - Vst = branch_state(L, Vst0), - sab_1(T, Tuple, Type, Vst); -sab_1([_,{f,_}|T], Tuple, Type, Vst) -> - %% We already have an established different exact size for the tuple. - %% This label can't possibly be reached. - sab_1(T, Tuple, Type, Vst); -sab_1([], _, _, #vst{}=Vst) -> - Vst. +validate_select_val(_Fail, _Choices, _Src, #vst{current=none}=Vst) -> + %% We've already branched on all of Src's possible values, so we know we + %% can't reach the fail label or any of the remaining choices. + Vst; +validate_select_val(Fail, [Val,{f,L}|T], Src, Vst0) -> + Vst = branch(L, Vst0, + fun(BranchVst) -> + update_eq_types(Src, Val, BranchVst) + end, + fun(FailVst) -> + update_ne_types(Src, Val, FailVst) + end), + validate_select_val(Fail, T, Src, Vst); +validate_select_val(Fail, [], _, Vst) -> + branch(Fail, Vst, + fun(SuccVst) -> + %% The next instruction is never executed. + kill_state(SuccVst) + end). + +validate_select_tuple_arity(_Fail, _Choices, _Src, #vst{current=none}=Vst) -> + %% We've already branched on all of Src's possible values, so we know we + %% can't reach the fail label or any of the remaining choices. + Vst; +validate_select_tuple_arity(Fail, [Arity,{f,L}|T], Tuple, Vst0) -> + Type = {tuple, Arity, #{}}, + Vst = branch(L, Vst0, + fun(BranchVst) -> + update_type(fun meet/2, Type, Tuple, BranchVst) + end, + fun(FailVst) -> + update_type(fun subtract/2, Type, Tuple, FailVst) + end), + validate_select_tuple_arity(Fail, T, Tuple, Vst); +validate_select_tuple_arity(Fail, [], _, #vst{}=Vst) -> + branch(Fail, Vst, + fun(SuccVst) -> + %% The next instruction is never executed. + kill_state(SuccVst) + end). infer_types({Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y -> infer_types(get_reg_vref(Reg, Vst), Vst); @@ -1628,26 +1713,6 @@ resolve_args([Lit | Args], Vst) -> resolve_args([], _Vst) -> []. -%% Helper functions for tests that alter state on both the success and fail -%% branches, keeping the states from tainting each other. -complex_test(Fail, FailFun, SuccFun, Vst0) -> - #vst{current=St0} = Vst0, - Vst1 = FailFun(Vst0), - Vst2 = branch_state(Fail, Vst1), - Vst = Vst2#vst{current=St0}, - SuccFun(Vst). - -%% Helper function for simple "is_type" tests. -type_test(Fail, Type, Reg, Vst) -> - assert_term(Reg, Vst), - complex_test(Fail, - fun(FailVst) -> - update_type(fun subtract/2, Type, Reg, FailVst) - end, - fun(SuccVst) -> - update_type(fun meet/2, Type, Reg, SuccVst) - end, Vst). - %% Overrides the type of Reg. This is ugly but a necessity for certain %% destructive operations. override_type(Type, Reg, Vst) -> @@ -1655,7 +1720,7 @@ override_type(Type, Reg, Vst) -> %% This is used when linear code finds out more and more information about a %% type, so that the type gets more specialized. -update_type(Merge, Type0, #value_ref{}=Ref, Vst) -> +update_type(Merge, With, #value_ref{}=Ref, Vst) -> %% If the old type can't be merged with the new one, the type information %% is inconsistent and we know that some instructions will never be %% executed at run-time. For example: @@ -1664,21 +1729,47 @@ update_type(Merge, Type0, #value_ref{}=Ref, Vst) -> %% {test,is_tuple,Fail,[Reg]}. %% {test,test_arity,Fail,[Reg,5]}. %% - %% Note that the test_arity instruction can never be reached, so we use the - %% new type instead of 'none'. - Type = case Merge(get_raw_type(Ref, Vst), Type0) of - none -> Type0; - T -> T - end, - set_type(Type, Ref, Vst); -update_type(Merge, Type, {Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y -> - update_type(Merge, Type, get_reg_vref(Reg, Vst), Vst); -update_type(_Merge, _Type, Literal, Vst) -> + %% Note that the test_arity instruction can never be reached, so we need to + %% kill the state to avoid raising an error when we encounter it. + %% + %% Simply returning `kill_state(Vst)` is unsafe however as we might be in + %% the middle of an instruction, and altering the rest of the validator + %% (eg. prune_x_regs/2) to no-op on dead states is prone to error. + %% + %% We therefore throw a 'type_conflict' error instead, which causes + %% validation to fail unless we're in a context where such errors can be + %% handled, such as in a branch handler. + Current = get_raw_type(Ref, Vst), + case Merge(Current, With) of + none -> throw({type_conflict, Current, With}); + Type -> set_type(Type, Ref, Vst) + end; +update_type(Merge, With, {Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y -> + update_type(Merge, With, get_reg_vref(Reg, Vst), Vst); +update_type(Merge, With, Literal, Vst) -> assert_literal(Literal), - Vst. + %% Literals always retain their type, but we still need to bail on type + %% conflicts. + case Merge(Literal, With) of + none -> throw({type_conflict, Literal, With}); + _Type -> Vst + end. update_ne_types(LHS, RHS, Vst) -> - update_type(fun subtract/2, get_term_type(RHS, Vst), LHS, Vst). + %% 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. + %% + %% Consider `number =/= {integer,[]}`; all we know is that LHS isn't equal + %% to some *specific integer* of unknown value, and if we were to subtract + %% {integer,[]} we would erroneously infer that the new type is {float,[]}. + %% + %% Therefore, we only subtract when we know that RHS has a specific value. + RType = get_term_type(RHS, Vst), + case is_literal(RType) of + true -> update_type(fun subtract/2, RType, LHS, Vst); + false -> Vst + end. update_eq_types(LHS, RHS, Vst0) -> Infer = infer_types(LHS, Vst0), @@ -1786,19 +1877,27 @@ assert_term(Src, Vst) -> ok. assert_movable(Src, Vst) -> - _ = get_move_term_type(Src, Vst), + _ = get_movable_term_type(Src, Vst), ok. -assert_literal(nil) -> ok; -assert_literal({atom,A}) when is_atom(A) -> ok; -assert_literal({float,F}) when is_float(F) -> ok; -assert_literal({integer,I}) when is_integer(I) -> ok; -assert_literal({literal,_L}) -> ok; -assert_literal(T) -> error({literal_required,T}). +assert_literal(Src) -> + case is_literal(Src) of + true -> ok; + false -> error({literal_required,Src}) + end. + +assert_not_literal(Src) -> + case is_literal(Src) of + true -> error({literal_not_allowed,Src}); + false -> ok + end. -assert_not_literal({x,_}) -> ok; -assert_not_literal({y,_}) -> ok; -assert_not_literal(Literal) -> error({literal_not_allowed,Literal}). +is_literal(nil) -> true; +is_literal({atom,A}) when is_atom(A) -> true; +is_literal({float,F}) when is_float(F) -> true; +is_literal({integer,I}) when is_integer(I) -> true; +is_literal({literal,_L}) -> true; +is_literal(_) -> false. %% The possible types. %% @@ -2050,6 +2149,7 @@ assert_tuple_elements(Limit, Es) -> %% Subtract Type2 from Type2. Example: %% subtract(list, nil) -> cons +subtract(Same, Same) -> none; subtract(list, nil) -> cons; subtract(list, cons) -> nil; subtract(number, {integer,[]}) -> {float,[]}; @@ -2082,11 +2182,10 @@ assert_type(Needed, Actual) -> get_element_type(Key, Src, Vst) -> get_element_type_1(Key, get_term_type(Src, Vst)). -get_element_type_1({integer,Index}=Key, {tuple,Sz,Es}) -> +get_element_type_1({integer,_}=Key, {tuple,_Sz,Es}) -> case Es of #{ Key := Type } -> Type; - #{} when Index =< Sz -> term; - #{} -> none + #{} -> term end; get_element_type_1(_Index, _Type) -> term. @@ -2103,7 +2202,7 @@ get_tuple_size({integer,Sz}) -> Sz; get_tuple_size(_) -> 0. validate_src(Ss, Vst) when is_list(Ss) -> - [assert_term(S, Vst) || S <- Ss], + _ = [assert_term(S, Vst) || S <- Ss], ok. %% get_term_type(Src, ValidatorState) -> Type @@ -2111,22 +2210,23 @@ validate_src(Ss, Vst) when is_list(Ss) -> %% a standard Erlang type (no catch/try tags or match contexts). get_term_type(Src, Vst) -> - case get_move_term_type(Src, Vst) of + case get_movable_term_type(Src, Vst) of #ms{} -> error({match_context,Src}); Type -> Type end. -%% get_move_term_type(Src, ValidatorState) -> Type +%% get_movable_term_type(Src, ValidatorState) -> Type %% Get the type of the source Src. The returned type Type will be %% a standard Erlang type (no catch/try tags). Match contexts are OK. -get_move_term_type(Src, Vst) -> +get_movable_term_type(Src, Vst) -> case get_raw_type(Src, Vst) of initialized -> error({unassigned,Src}); uninitialized -> error({uninitialized_reg,Src}); {catchtag,_} -> error({catchtag,Src}); {trytag,_} -> error({trytag,Src}); tuple_in_progress -> error({tuple_in_progress,Src}); + {literal,_}=Lit -> get_literal_type(Lit); Type -> Type end. @@ -2145,7 +2245,8 @@ get_tag_type(Src, _) -> error({invalid_tag_register,Src}). %% get_raw_type(Src, ValidatorState) -> Type -%% Return the type of a register without doing any validity checks. +%% Return the type of a register without doing any validity checks or +%% conversions. get_raw_type({x,X}=Src, #vst{current=#st{xs=Xs}}=Vst) when is_integer(X) -> check_limit(Src), case Xs of @@ -2192,10 +2293,53 @@ glt_1(T) when is_tuple(T) -> glt_1(L) -> {literal, L}. +%%% +%%% Branch tracking +%%% + +%% Forks the execution flow, with the provided funs returning the new state of +%% their respective branch; the "fail" fun returns the state where the branch +%% is taken, and the "success" fun returns the state where it's not. +%% +%% If either path is known not to be taken at runtime (eg. due to a type +%% conflict), it will simply be discarded. +-spec branch(Lbl :: label(), + Original :: #vst{}, + FailFun :: BranchFun, + SuccFun :: BranchFun) -> #vst{} when + BranchFun :: fun((#vst{}) -> #vst{}). +branch(Lbl, Vst0, FailFun, SuccFun) -> + #vst{current=St0} = Vst0, + try FailFun(Vst0) of + Vst1 -> + Vst2 = branch_state(Lbl, Vst1), + Vst = Vst2#vst{current=St0}, + try SuccFun(Vst) of + V -> V + catch + {type_conflict, _, _} -> + %% The instruction is guaranteed to fail; kill the state. + kill_state(Vst) + end + catch + {type_conflict, _, _} -> + %% This instruction is guaranteed not to fail, so we run the + %% success branch *without* catching type conflicts to avoid hiding + %% errors in the validator itself; one of the branches must + %% succeed. + SuccFun(Vst0) + end. + +%% A shorthand version of branch/4 for when the state is only altered on +%% success. +branch(Fail, Vst, SuccFun) -> + branch(Fail, Vst, fun(V) -> V end, SuccFun). + +%% Directly branches off the state. This is an "internal" operation that should +%% be used sparingly. branch_state(0, #vst{}=Vst) -> - %% If the instruction fails, the stack may be scanned - %% looking for a catch tag. Therefore the Y registers - %% must be initialized at this point. + %% If the instruction fails, the stack may be scanned looking for a catch + %% tag. Therefore the Y registers must be initialized at this point. verify_y_init(Vst), Vst; branch_state(L, #vst{current=St,branched=B,ref_ctr=Counter0}=Vst) -> diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl index 86351bc0c5..e2b8787224 100644 --- a/lib/compiler/src/v3_kernel.erl +++ b/lib/compiler/src/v3_kernel.erl @@ -1590,19 +1590,12 @@ match_var([U|Us], Cs0, Def, St) -> %% constructor/constant as first argument. Group the constructors %% according to type, the order is really irrelevant but tries to be %% smart. - -match_con(Us, Cs0, Def, St) -> - %% Expand literals at the top level. - Cs = [expand_pat_lit_clause(C) || C <- Cs0], - match_con_1(Us, Cs, Def, St). - -match_con_1([U|_Us] = L, Cs, Def, St0) -> +match_con([U|_Us] = L, Cs, Def, St0) -> %% Extract clauses for different constructors (types). %%ok = io:format("match_con ~p~n", [Cs]), - Ttcs0 = select_types([k_binary], Cs) ++ select_bin_con(Cs) ++ - select_types([k_cons,k_tuple,k_map,k_atom,k_float, - k_int,k_nil], Cs), - Ttcs = opt_single_valued(Ttcs0), + Ttcs0 = select_types(Cs, [], [], [], [], [], [], [], [], []), + Ttcs1 = [{T, Types} || {T, [_ | _] = Types} <- Ttcs0], + Ttcs = opt_single_valued(Ttcs1), %%ok = io:format("ttcs = ~p~n", [Ttcs]), {Scs,St1} = mapfoldl(fun ({T,Tcs}, St) -> @@ -1613,8 +1606,41 @@ match_con_1([U|_Us] = L, Cs, Def, St0) -> St0, Ttcs), {build_alt_1st_no_fail(build_select(U, Scs), Def),St1}. -select_types(Types, Cs) -> - [{T,Tcs} || T <- Types, begin Tcs = select(T, Cs), Tcs =/= [] end]. +select_types([NoExpC | Cs], Bin, BinCon, Cons, Tuple, Map, Atom, Float, Int, Nil) -> + C = expand_pat_lit_clause(NoExpC), + case clause_con(C) of + k_binary -> + select_types(Cs, [C |Bin], BinCon, Cons, Tuple, Map, Atom, Float, Int, Nil); + k_bin_seg -> + select_types(Cs, Bin, [C | BinCon], Cons, Tuple, Map, Atom, Float, Int, Nil); + k_bin_end -> + select_types(Cs, Bin, [C | BinCon], Cons, Tuple, Map, Atom, Float, Int, Nil); + k_cons -> + select_types(Cs, Bin, BinCon, [C | Cons], Tuple, Map, Atom, Float, Int, Nil); + k_tuple -> + select_types(Cs, Bin, BinCon, Cons, [C | Tuple], Map, Atom, Float, Int, Nil); + k_map -> + select_types(Cs, Bin, BinCon, Cons, Tuple, [C | Map], Atom, Float, Int, Nil); + k_atom -> + select_types(Cs, Bin, BinCon, Cons, Tuple, Map, [C | Atom], Float, Int, Nil); + k_float -> + select_types(Cs, Bin, BinCon, Cons, Tuple, Map, Atom, [C | Float], Int, Nil); + k_int -> + select_types(Cs, Bin, BinCon, Cons, Tuple, Map, Atom, Float, [C | Int], Nil); + k_nil -> + select_types(Cs, Bin, BinCon, Cons, Tuple, Map, Atom, Float, Int, [C | Nil]) + end; +select_types([], Bin, BinCon, Cons, Tuple, Map, Atom, Float, Int, Nil) -> + [{k_binary, reverse(Bin)}] ++ handle_bin_con(reverse(BinCon)) ++ + [ + {k_cons, reverse(Cons)}, + {k_tuple, reverse(Tuple)}, + {k_map, reverse(Map)}, + {k_atom, reverse(Atom)}, + {k_float, reverse(Float)}, + {k_int, reverse(Int)}, + {k_nil, reverse(Nil)} + ]. expand_pat_lit_clause(#iclause{pats=[#ialias{pat=#k_literal{anno=A,val=Val}}=Alias|Ps]}=C) -> P = expand_pat_lit(Val, A), @@ -1743,20 +1769,12 @@ combine_bin_segs(#k_bin_end{}) -> combine_bin_segs(_) -> throw(not_possible). -%% select_bin_con([Clause]) -> [{Type,[Clause]}]. -%% Extract clauses for the k_bin_seg constructor. As k_bin_seg +%% handle_bin_con([Clause]) -> [{Type,[Clause]}]. +%% Handle clauses for the k_bin_seg constructor. As k_bin_seg %% matching can overlap, the k_bin_seg constructors cannot be %% reordered, only grouped. -select_bin_con(Cs0) -> - Cs1 = lists:filter(fun (C) -> - Con = clause_con(C), - (Con =:= k_bin_seg) or (Con =:= k_bin_end) - end, Cs0), - select_bin_con_1(Cs1). - - -select_bin_con_1(Cs) -> +handle_bin_con(Cs) -> try %% The usual way to match literals is to first extract the %% value to a register, and then compare the register to the @@ -1795,14 +1813,14 @@ select_bin_con_1(Cs) -> end catch throw:not_possible -> - select_bin_con_2(Cs) + handle_bin_con_not_possible(Cs) end. -select_bin_con_2([C1|Cs]) -> +handle_bin_con_not_possible([C1|Cs]) -> Con = clause_con(C1), {More,Rest} = splitwith(fun (C) -> clause_con(C) =:= Con end, Cs), - [{Con,[C1|More]}|select_bin_con_2(Rest)]; -select_bin_con_2([]) -> []. + [{Con,[C1|More]}|handle_bin_con_not_possible(Rest)]; +handle_bin_con_not_possible([]) -> []. %% select_bin_int([Clause]) -> {k_bin_int,[Clause]} %% If the first pattern in each clause selects the same integer, @@ -1902,10 +1920,6 @@ select_utf8(Val0) -> throw(not_possible) end. -%% select(Con, [Clause]) -> [Clause]. - -select(T, Cs) -> [ C || C <- Cs, clause_con(C) =:= T ]. - %% match_value([Var], Con, [Clause], Default, State) -> {SelectExpr,State}. %% At this point all the clauses have the same constructor, we must %% now separate them according to value. @@ -2040,6 +2054,10 @@ get_match(#k_cons{}, St0) -> get_match(#k_binary{}, St0) -> {[V]=Mes,St1} = new_vars(1, St0), {#k_binary{segs=V},Mes,St1}; +get_match(#k_bin_seg{size=#k_atom{val=all},next={k_bin_end,[]}}=Seg, St0) -> + {[S,N0],St1} = new_vars(2, St0), + N = set_kanno(N0, [no_usage]), + {Seg#k_bin_seg{seg=S,next=N},[S],St1}; get_match(#k_bin_seg{}=Seg, St0) -> {[S,N0],St1} = new_vars(2, St0), N = set_kanno(N0, [no_usage]), @@ -2067,6 +2085,9 @@ new_clauses(Cs0, U, St) -> #k_cons{hd=H,tl=T} -> [H,T|As]; #k_tuple{es=Es} -> Es ++ As; #k_binary{segs=E} -> [E|As]; + #k_bin_seg{size=#k_atom{val=all}, + seg=S,next={k_bin_end,[]}} -> + [S|As]; #k_bin_seg{seg=S,next=N} -> [S,N|As]; #k_bin_int{next=N} -> diff --git a/lib/compiler/test/beam_validator_SUITE.erl b/lib/compiler/test/beam_validator_SUITE.erl index 265da43f9d..8b39fce479 100644 --- a/lib/compiler/test/beam_validator_SUITE.erl +++ b/lib/compiler/test/beam_validator_SUITE.erl @@ -34,7 +34,7 @@ undef_label/1,illegal_instruction/1,failing_gc_guard_bif/1, map_field_lists/1,cover_bin_opt/1, val_dsetel/1,bad_tuples/1,bad_try_catch_nesting/1, - receive_stacked/1,aliased_types/1]). + receive_stacked/1,aliased_types/1,type_conflict/1]). -include_lib("common_test/include/ct.hrl"). @@ -63,7 +63,7 @@ groups() -> undef_label,illegal_instruction,failing_gc_guard_bif, map_field_lists,cover_bin_opt,val_dsetel, bad_tuples,bad_try_catch_nesting, - receive_stacked,aliased_types]}]. + receive_stacked,aliased_types,type_conflict]}]. init_per_suite(Config) -> test_lib:recompile(?MODULE), @@ -156,8 +156,8 @@ call_last(Config) when is_list(Config) -> merge_undefined(Config) when is_list(Config) -> Errors = do_val(merge_undefined, Config), [{{t,handle_call,2}, - {{call_ext,1,{extfunc,erlang,exit,1}}, - 10, + {{call_ext,2,{extfunc,debug,filter,2}}, + 22, {uninitialized_reg,{y,_}}}}] = Errors, ok. @@ -630,6 +630,27 @@ aliased_types_3(Bug) -> hd(List) end. + +%% ERL-867; validation proceeded after a type conflict, causing incorrect types +%% to be joined. + +-record(r, { e1 = e1, e2 = e2 }). + +type_conflict(Config) when is_list(Config) -> + {e1, e2} = type_conflict_1(#r{}), + ok. + +type_conflict_1(C) -> + Src = id(C#r.e2), + TRes = try id(Src) of + R -> R + catch + %% C:R can never match, yet it assumed that the type of 'C' was + %% an atom from here on. + C:R -> R + end, + {C#r.e1, TRes}. + %%%------------------------------------------------------------------------- transform_remove(Remove, Module) -> diff --git a/lib/compiler/test/beam_validator_SUITE_data/merge_undefined.S b/lib/compiler/test/beam_validator_SUITE_data/merge_undefined.S index 481d55045d..aa344807e4 100644 --- a/lib/compiler/test/beam_validator_SUITE_data/merge_undefined.S +++ b/lib/compiler/test/beam_validator_SUITE_data/merge_undefined.S @@ -15,8 +15,9 @@ {select_val,{x,0},{f,1},{list,[{atom,gurka},{f,3},{atom,delete},{f,4}]}}. {label,3}. {allocate_heap,2,6,2}. - %% The Y registers are not initialized here. {test,is_eq_exact,{f,5},[{x,0},{atom,ok}]}. + %% This is unreachable since {x,0} is known not to be 'ok'. We should not + %% fail with "uninitialized y registers" on erlang:exit/1 {move,{atom,nisse},{x,0}}. {call_ext,1,{extfunc,erlang,exit,1}}. {label,4}. @@ -29,6 +30,7 @@ {call_ext,2,{extfunc,io,format,2}}. {test,is_ne_exact,{f,6},[{x,0},{atom,ok}]}. {label,5}. + %% The Y registers are not initialized here. {move,{atom,logReader},{x,1}}. {move,{atom,console},{x,0}}. {call_ext,2,{extfunc,debug,filter,2}}. diff --git a/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S b/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S index 5b974119c6..a878204d16 100644 --- a/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S +++ b/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S @@ -240,7 +240,7 @@ {y,0}}. {'%',{no_bin_opt,{binary_used_in,{test,is_binary,{f,34},[{y,0}]}}, [63,{file,"receive_stacked.erl"}]}}. - {test,is_binary,{f,34},[{y,0}]}. + {test,is_eq_exact,{f,34},[{y,0},{literal,<<0,1,2,3>>}]}. remove_message. {move,{integer,42},{x,0}}. {line,[{location,"receive_stacked.erl",64}]}. @@ -283,7 +283,7 @@ {y,0}}. {'%',{no_bin_opt,{[{x,1},{y,0}],{loop_rec_end,{f,38}},not_handled}, [70,{file,"receive_stacked.erl"}]}}. - {test,is_binary,{f,39},[{x,0}]}. + {test,is_eq_exact,{f,39},[{x,0},{literal,<<0,1,2,3>>}]}. remove_message. {move,{integer,42},{x,0}}. {line,[{location,"receive_stacked.erl",71}]}. |