diff options
Diffstat (limited to 'lib/compiler/src/beam_ssa_pre_codegen.erl')
| -rw-r--r-- | lib/compiler/src/beam_ssa_pre_codegen.erl | 265 |
1 files changed, 173 insertions, 92 deletions
diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl index 7f816b9802..61c42fdb6d 100644 --- a/lib/compiler/src/beam_ssa_pre_codegen.erl +++ b/lib/compiler/src/beam_ssa_pre_codegen.erl @@ -108,7 +108,8 @@ functions([], _Ps, _UseBSM3) -> []. intervals=[] :: [{b_var(),[range()]}], res=[] :: [{b_var(),reservation()}] | #{b_var():=reservation()}, regs=#{} :: #{b_var():=ssa_register()}, - extra_annos=[] :: [{atom(),term()}] + extra_annos=[] :: [{atom(),term()}], + location :: term() }). -define(PASS(N), {N,fun N/1}). @@ -119,7 +120,9 @@ passes(Opts) -> %% Preliminaries. ?PASS(fix_bs), + ?PASS(exception_trampolines), ?PASS(sanitize), + ?PASS(match_fail_instructions), case FixTuples of false -> ignore; true -> ?PASS(fix_tuples) @@ -164,7 +167,9 @@ passes(Opts) -> function(#b_function{anno=Anno,args=Args,bs=Blocks0,cnt=Count0}=F0, Ps, UseBSM3) -> try - St0 = #st{ssa=Blocks0,args=Args,use_bsm3=UseBSM3,cnt=Count0}, + Location = maps:get(location, Anno, none), + St0 = #st{ssa=Blocks0,args=Args,use_bsm3=UseBSM3, + cnt=Count0,location=Location}, St = compile:run_sub_passes(Ps, St0), #st{ssa=Blocks,cnt=Count,regs=Regs,extra_annos=ExtraAnnos} = St, F1 = add_extra_annos(F0, ExtraAnnos), @@ -598,6 +603,10 @@ bs_instrs([{L,#b_blk{is=Is0}=Blk}|Bs], CtxChain, Acc0) -> bs_instrs([], _, Acc) -> reverse(Acc). +bs_instrs_is([#b_set{op=succeeded}=I|Is], CtxChain, Acc) -> + %% This instruction refers to a specific operation, so we must not + %% substitute the context argument. + bs_instrs_is(Is, CtxChain, [I | Acc]); bs_instrs_is([#b_set{op=Op,args=Args0}=I0|Is], CtxChain, Acc) -> Args = [bs_subst_ctx(A, CtxChain) || A <- Args0], I1 = I0#b_set{args=Args}, @@ -691,6 +700,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 =:= ?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_exception_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: %% @@ -856,6 +903,114 @@ prune_phi(#b_set{args=Args0}=Phi, Reachable) -> gb_sets:is_element(Pred, Reachable)], Phi#b_set{args=Args}. +%%% Rewrite certain calls to erlang:error/{1,2} to specialized +%%% instructions: +%%% +%%% erlang:error({badmatch,Value}) => badmatch Value +%%% erlang:error({case_clause,Value}) => case_end Value +%%% erlang:error({try_clause,Value}) => try_case_end Value +%%% erlang:error(if_clause) => if_end +%%% erlang:error(function_clause, Args) => jump FuncInfoLabel +%%% +%%% In SSA code, we represent those instructions as a 'match_fail' +%%% instruction with the name of the BEAM instruction as the first +%%% argument. + +match_fail_instructions(#st{ssa=Blocks0,args=Args,location=Location}=St) -> + Ls = maps:to_list(Blocks0), + Info = {length(Args),Location}, + Blocks = match_fail_instrs_1(Ls, Info, Blocks0), + St#st{ssa=Blocks}. + +match_fail_instrs_1([{L,#b_blk{is=Is0}=Blk}|Bs], Arity, Blocks0) -> + case match_fail_instrs_blk(Is0, Arity, []) of + none -> + match_fail_instrs_1(Bs, Arity, Blocks0); + Is -> + Blocks = Blocks0#{L:=Blk#b_blk{is=Is}}, + match_fail_instrs_1(Bs, Arity, Blocks) + end; +match_fail_instrs_1([], _Arity, Blocks) -> Blocks. + +match_fail_instrs_blk([#b_set{op=put_tuple,dst=Dst, + args=[#b_literal{val=Tag},Val]}, + #b_set{op=call, + args=[#b_remote{mod=#b_literal{val=erlang}, + name=#b_literal{val=error}}, + Dst]}=Call|Is], + _Arity, Acc) -> + match_fail_instr(Call, Tag, Val, Is, Acc); +match_fail_instrs_blk([#b_set{op=call, + args=[#b_remote{mod=#b_literal{val=erlang}, + name=#b_literal{val=error}}, + #b_literal{val={Tag,Val}}]}=Call|Is], + _Arity, Acc) -> + match_fail_instr(Call, Tag, #b_literal{val=Val}, Is, Acc); +match_fail_instrs_blk([#b_set{op=call, + args=[#b_remote{mod=#b_literal{val=erlang}, + name=#b_literal{val=error}}, + #b_literal{val=if_clause}]}=Call|Is], + _Arity, Acc) -> + I = Call#b_set{op=match_fail,args=[#b_literal{val=if_end}]}, + reverse(Acc, [I|Is]); +match_fail_instrs_blk([#b_set{op=call,anno=Anno, + args=[#b_remote{mod=#b_literal{val=erlang}, + name=#b_literal{val=error}}, + #b_literal{val=function_clause}, + Stk]}=Call], + {Arity,Location}, Acc) -> + case match_fail_stk(Stk, Acc, [], []) of + {[_|_]=Vars,Is} when length(Vars) =:= Arity -> + case maps:get(location, Anno, none) of + Location -> + I = Call#b_set{op=match_fail, + args=[#b_literal{val=function_clause}|Vars]}, + Is ++ [I]; + _ -> + %% erlang:error/2 has a different location than the + %% func_info instruction at the beginning of the function + %% (probably because of inlining). Keep the original call. + reverse(Acc, [Call]) + end; + _ -> + %% Either the stacktrace could not be picked apart (for example, + %% if the call to erlang:error/2 was handwritten) or the number + %% of arguments in the stacktrace was different from the arity + %% of the host function (because it is the implementation of a + %% fun). Keep the original call. + reverse(Acc, [Call]) + end; +match_fail_instrs_blk([I|Is], Arity, Acc) -> + match_fail_instrs_blk(Is, Arity, [I|Acc]); +match_fail_instrs_blk(_, _, _) -> + none. + +match_fail_instr(Call, Tag, Val, Is, Acc) -> + Op = case Tag of + badmatch -> Tag; + case_clause -> case_end; + try_clause -> try_case_end; + _ -> none + end, + case Op of + none -> + none; + _ -> + I = Call#b_set{op=match_fail,args=[#b_literal{val=Op},Val]}, + reverse(Acc, [I|Is]) + end. + +match_fail_stk(#b_var{}=V, [#b_set{op=put_list,dst=V,args=[H,T]}|Is], IAcc, VAcc) -> + match_fail_stk(T, Is, IAcc, [H|VAcc]); +match_fail_stk(#b_literal{val=[H|T]}, Is, IAcc, VAcc) -> + match_fail_stk(#b_literal{val=T}, Is, IAcc, [#b_literal{val=H}|VAcc]); +match_fail_stk(#b_literal{val=[]}, [], IAcc, VAcc) -> + {reverse(VAcc),IAcc}; +match_fail_stk(T, [#b_set{op=Op}=I|Is], IAcc, VAcc) + when Op =:= bs_get_tail; Op =:= bs_set_position -> + match_fail_stk(T, Is, [I|IAcc], VAcc); +match_fail_stk(_, _, _, _) -> none. + %%% %%% Fix tuples. %%% @@ -911,9 +1066,8 @@ use_set_tuple_element(#st{ssa=Blocks0}=St) -> Blocks = use_ste_1(RPO, Uses, Blocks0), St#st{ssa=Blocks}. -use_ste_1([L|Ls], Uses, Blocks0) -> - {Blk0,Blocks} = use_ste_across(L, Uses, Blocks0), - #b_blk{is=Is0} = Blk0, +use_ste_1([L|Ls], Uses, Blocks) -> + #b_blk{is=Is0} = Blk0 = map_get(L, Blocks), case use_ste_is(Is0, Uses) of Is0 -> use_ste_1(Ls, Uses, Blocks); @@ -976,69 +1130,6 @@ extract_ste(#b_set{op=call,dst=Dst, end; extract_ste(#b_set{}) -> none. -%%% Optimize accross blocks within a try/catch block. - -use_ste_across(L, Uses, Blocks) -> - case map_get(L, Blocks) of - #b_blk{last=#b_br{bool=#b_var{}}}=Blk -> - try - use_ste_across_1(L, Blk, Uses, Blocks) - catch - throw:not_possible -> - {Blk,Blocks} - end; - #b_blk{}=Blk -> - {Blk,Blocks} - end. - -use_ste_across_1(L, Blk0, Uses, Blocks0) -> - #b_blk{is=IsThis,last=#b_br{bool=Bool,succ=Next}} = Blk0, - case reverse(IsThis) of - [#b_set{op=succeeded,dst=Bool,args=[Result]}=Succ0, - #b_set{op=call,args=[#b_remote{}|_],dst=Result}=Call1|Prefix] -> - case is_single_use(Bool, Uses) andalso - is_n_uses(2, Result, Uses) of - true -> ok; - false -> throw(not_possible) - end, - Call2 = use_ste_across_next(Next, Uses, Blocks0), - Is = [Call1,Call2], - case use_ste_is(Is, decrement_uses(Result, Uses)) of - [#b_set{}=Call,#b_set{op=set_tuple_element}=Ste] -> - Blocks1 = use_ste_fix_next(Ste, Next, Blocks0), - Succ = Succ0#b_set{args=[Call#b_set.dst]}, - Blk = Blk0#b_blk{is=reverse(Prefix, [Call,Succ])}, - Blocks = Blocks1#{L:=Blk}, - {Blk,Blocks}; - _ -> - throw(not_possible) - end; - _ -> - throw(not_possible) - end. - -use_ste_across_next(Next, Uses, Blocks) -> - case map_get(Next, Blocks) of - #b_blk{is=[#b_set{op=call,dst=Result,args=[#b_remote{}|_]}=Call, - #b_set{op=succeeded,dst=Bool,args=[Result]}], - last=#b_br{bool=Bool}} -> - case is_single_use(Bool, Uses) andalso - is_n_uses(2, Result, Uses) of - true -> ok; - false -> throw(not_possible) - end, - Call; - #b_blk{} -> - throw(not_possible) - end. - -use_ste_fix_next(Ste, Next, Blocks) -> - Blk0 = map_get(Next, Blocks), - #b_blk{is=[#b_set{op=call},#b_set{op=succeeded}],last=Br0} = Blk0, - Br = beam_ssa:normalize(Br0#b_br{bool=#b_literal{val=true}}), - Blk = Blk0#b_blk{is=[Ste],last=Br}, - Blocks#{Next:=Blk}. - %% Count how many times each variable is used. count_uses(Blocks) -> @@ -1048,7 +1139,7 @@ count_uses_blk([#b_blk{is=Is,last=Last}|Bs], CountMap0) -> F = fun(I, CountMap) -> foldl(fun(Var, Acc) -> case Acc of - #{Var:=3} -> Acc; + #{Var:=2} -> Acc; #{Var:=C} -> Acc#{Var:=C+1}; #{} -> Acc#{Var=>1} end @@ -1058,16 +1149,6 @@ count_uses_blk([#b_blk{is=Is,last=Last}|Bs], CountMap0) -> count_uses_blk(Bs, CountMap); count_uses_blk([], CountMap) -> CountMap. -decrement_uses(V, Uses) -> - #{V:=C} = Uses, - Uses#{V:=C-1}. - -is_n_uses(N, V, Uses) -> - case Uses of - #{V:=N} -> true; - #{} -> false - end. - is_single_use(V, Uses) -> case Uses of #{V:=1} -> true; @@ -1189,10 +1270,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) -> @@ -1340,9 +1421,9 @@ recv_common(_Defs, none, _Blocks) -> %% in the tail position of a function. []; recv_common(Defs, Exit, Blocks) -> - {ExitDefs,ExitUsed} = beam_ssa:def_used([Exit], Blocks), + {ExitDefs,ExitUnused} = beam_ssa:def_unused([Exit], Defs, Blocks), Def = ordsets:subtract(Defs, ExitDefs), - ordsets:intersection(Def, ExitUsed). + ordsets:subtract(Def, ExitUnused). %% recv_crit_edges([RemoveMessageLabel], LoopExit, %% Blocks0, Count0) -> {Blocks,Count}. @@ -1447,9 +1528,9 @@ exit_predecessors([], _Exit, _Blocks) -> []. %% later used within a clause of the receive. fix_receive([L|Ls], Defs, Blocks0, Count0) -> - {RmDefs,Used0} = beam_ssa:def_used([L], Blocks0), + {RmDefs,Unused} = beam_ssa:def_unused([L], Defs, Blocks0), Def = ordsets:subtract(Defs, RmDefs), - Used = ordsets:intersection(Def, Used0), + Used = ordsets:subtract(Def, Unused), {NewVars,Count} = new_vars([Base || #b_var{name=Base} <- Used], Count0), Ren = zip(Used, NewVars), Blocks1 = beam_ssa:rename_vars(Ren, [L], Blocks0), @@ -1483,8 +1564,8 @@ find_loop_exit(_, _) -> %% loop exit block. none. -find_loop_exit_1([?BADARG_BLOCK|Ls], RmSet, Dominators) -> - %% ?BADARG_BLOCK is a marker and not an actual block, so it is not +find_loop_exit_1([?EXCEPTION_BLOCK|Ls], RmSet, Dominators) -> + %% ?EXCEPTION_BLOCK is a marker and not an actual block, so it is not %% the block we are looking for. find_loop_exit_1(Ls, RmSet, Dominators); find_loop_exit_1([L|Ls], RmSet, Dominators) -> @@ -1756,7 +1837,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 @@ -2105,8 +2186,8 @@ reserve_yregs(#st{frames=Frames}=St0) -> reserve_yregs_1(L, #st{ssa=Blocks0,cnt=Count0,res=Res0}=St) -> Blk = map_get(L, Blocks0), Yregs = beam_ssa:get_anno(yregs, Blk), - {Def,Used} = beam_ssa:def_used([L], Blocks0), - UsedYregs = ordsets:intersection(Yregs, Used), + {Def,Unused} = beam_ssa:def_unused([L], Yregs, Blocks0), + UsedYregs = ordsets:subtract(Yregs, Unused), DefBefore = ordsets:subtract(UsedYregs, Def), {BeforeVars,Blocks,Count} = rename_vars(DefBefore, L, Blocks0, Count0), InsideVars = ordsets:subtract(UsedYregs, DefBefore), @@ -2495,9 +2576,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}, |