diff options
Diffstat (limited to 'lib/compiler/src')
| -rw-r--r-- | lib/compiler/src/Makefile | 2 | ||||
| -rw-r--r-- | lib/compiler/src/beam_bsm.erl | 719 | ||||
| -rw-r--r-- | lib/compiler/src/beam_disasm.erl | 10 | ||||
| -rw-r--r-- | lib/compiler/src/beam_jump.erl | 2 | ||||
| -rw-r--r-- | lib/compiler/src/beam_kernel_to_ssa.erl | 9 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa.erl | 89 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa_bsm.erl | 1027 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa_codegen.erl | 49 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa_opt.erl | 117 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa_pre_codegen.erl | 293 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa_type.erl | 2 | ||||
| -rw-r--r-- | lib/compiler/src/beam_utils.erl | 5 | ||||
| -rw-r--r-- | lib/compiler/src/beam_validator.erl | 193 | ||||
| -rw-r--r-- | lib/compiler/src/compile.erl | 15 | ||||
| -rw-r--r-- | lib/compiler/src/compiler.app.src | 2 | ||||
| -rwxr-xr-x | lib/compiler/src/genop.tab | 18 | ||||
| -rw-r--r-- | lib/compiler/src/sys_core_bsm.erl | 250 | ||||
| -rw-r--r-- | lib/compiler/src/v3_kernel.erl | 37 |
18 files changed, 1593 insertions, 1246 deletions
diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile index 522523726b..26ae6566e6 100644 --- a/lib/compiler/src/Makefile +++ b/lib/compiler/src/Makefile @@ -50,7 +50,6 @@ MODULES = \ beam_asm \ beam_block \ beam_bs \ - beam_bsm \ beam_clean \ beam_dict \ beam_disasm \ @@ -61,6 +60,7 @@ MODULES = \ beam_opcodes \ beam_peep \ beam_ssa \ + beam_ssa_bsm \ beam_ssa_codegen \ beam_ssa_dead \ beam_ssa_lint \ diff --git a/lib/compiler/src/beam_bsm.erl b/lib/compiler/src/beam_bsm.erl deleted file mode 100644 index abc6e96c85..0000000000 --- a/lib/compiler/src/beam_bsm.erl +++ /dev/null @@ -1,719 +0,0 @@ -%% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2007-2018. All Rights Reserved. -%% -%% Licensed under the Apache License, Version 2.0 (the "License"); -%% you may not use this file except in compliance with the License. -%% You may obtain a copy of the License at -%% -%% http://www.apache.org/licenses/LICENSE-2.0 -%% -%% Unless required by applicable law or agreed to in writing, software -%% distributed under the License is distributed on an "AS IS" BASIS, -%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -%% See the License for the specific language governing permissions and -%% limitations under the License. -%% -%% %CopyrightEnd% -%% - --module(beam_bsm). --export([module/2,format_error/1]). - --import(lists, [member/2,foldl/3,reverse/1,sort/1,all/2]). - -%%% -%%% We optimize bit syntax matching where the tail end of a binary is -%%% matched out and immediately passed on to a bs_start_match2 instruction, -%%% such as in this code sequence: -%%% -%%% func_info ... -%%% L1 test bs_start_match2 {f,...} {x,0} Live SavePositions {x,0} -%%% . . . -%%% test bs_get_binary2 {f,...} {x,0} all 1 Flags {x,0} -%%% . . . -%%% call_only 2 L1 -%%% -%%% The sequence can be optimized simply by removing the bs_get_binary2 -%%% instruction. Another example: -%%% -%%% func_info ... -%%% L1 test bs_start_match2 {f,...} {x,0} Live SavePositions {x,0} -%%% . . . -%%% test bs_get_binary2 {f,...} {x,0} all 8 Flags {x,1} -%%% . . . -%%% move {x,1} {x,0} -%%% call_only 2 L1 -%%% -%%% In this case, the bs_get_binary2 instruction must be replaced by -%%% -%%% test bs_unit {x,1} 8 -%%% -%%% to ensure that the match fail if the length of the binary in bits -%%% is not evenly divisible by 8. -%%% -%%% Note that the bs_start_match2 instruction doesn't need to be in the same -%%% function as the caller. It can be in the beginning of any function, or -%%% follow the bs_get_binary2 instruction in the same function. The important -%%% thing is that the match context register is not copied or built into -%%% data structures or passed to BIFs. -%%% - --type label() :: beam_asm:label(). --type func_info() :: {beam_asm:reg(),boolean()}. - --record(btb, - {f :: gb_trees:tree(label(), func_info()), - index :: beam_utils:code_index(), %{Label,Code} index (for liveness). - ok_br=gb_sets:empty() :: gb_sets:set(label()), %Labels that are OK. - must_not_save=false :: boolean(), %Must not save position when - % optimizing (reaches - % bs_context_to_binary). - must_save=false :: boolean() %Must save position when optimizing. - }). - - --spec module(beam_utils:module_code(), [compile:option()]) -> - {'ok',beam_utils:module_code()}. - -module({Mod,Exp,Attr,Fs0,Lc}, Opts) -> - FIndex = btb_index(Fs0), - Fs = [function(F, FIndex) || F <- Fs0], - Code = {Mod,Exp,Attr,Fs,Lc}, - case proplists:get_bool(bin_opt_info, Opts) of - true -> - {ok,Code,collect_warnings(Fs)}; - false -> - {ok,Code} - end. - --spec format_error('bin_opt' | {'no_bin_opt', term()}) -> nonempty_string(). - -format_error(bin_opt) -> - "OPTIMIZED: creation of sub binary delayed"; -format_error({no_bin_opt,Reason}) -> - lists:flatten(["NOT OPTIMIZED: "|format_error_1(Reason)]). - -%%% -%%% Local functions. -%%% - -function({function,Name,Arity,Entry,Is}, FIndex) -> - try - Index = beam_utils:index_labels(Is), - D = #btb{f=FIndex,index=Index}, - {function,Name,Arity,Entry,btb_opt_1(Is, D, [])} - catch - Class:Error:Stack -> - io:fwrite("Function: ~w/~w\n", [Name,Arity]), - erlang:raise(Class, Error, Stack) - end. - -btb_opt_1([{test,bs_get_binary2,F,_,[Reg,{atom,all},U,Fs],Reg}=I0|Is], D, Acc0) -> - case btb_reaches_match(Is, [Reg], D) of - {error,Reason} -> - Comment = btb_comment_no_opt(Reason, Fs), - btb_opt_1(Is, D, [Comment,I0|Acc0]); - {ok,MustSave} -> - Comment = btb_comment_opt(Fs), - Acc1 = btb_gen_save(MustSave, Reg, [Comment|Acc0]), - Acc = case U of - 1 -> Acc1; - _ -> [{test,bs_test_unit,F,[Reg,U]}|Acc1] - end, - btb_opt_1(Is, D, Acc) - end; -btb_opt_1([{test,bs_get_binary2,F,_,[Ctx,{atom,all},U,Fs],Dst}=I0|Is0], D, Acc0) -> - case btb_reaches_match(Is0, [Ctx,Dst], D) of - {error,Reason} -> - Comment = btb_comment_no_opt(Reason, Fs), - btb_opt_1(Is0, D, [Comment,I0|Acc0]); - {ok,MustSave} when U =:= 1 -> - Comment = btb_comment_opt(Fs), - Acc = btb_gen_save(MustSave, Ctx, [Comment|Acc0]), - Is = prepend_move(Ctx, Dst, Is0), - btb_opt_1(Is, D, Acc); - {ok,MustSave} -> - Comment = btb_comment_opt(Fs), - Acc1 = btb_gen_save(MustSave, Ctx, [Comment|Acc0]), - Acc = [{test,bs_test_unit,F,[Ctx,U]}|Acc1], - Is = prepend_move(Ctx, Dst, Is0), - btb_opt_1(Is, D, Acc) - end; -btb_opt_1([I|Is], D, Acc) -> - %%io:format("~p\n", [I]), - btb_opt_1(Is, D, [I|Acc]); -btb_opt_1([], _, Acc) -> - reverse(Acc). - -btb_gen_save(true, Reg, Acc) -> - [{bs_save2,Reg,{atom,start}}|Acc]; -btb_gen_save(false, _, Acc) -> Acc. - -prepend_move(Ctx, Dst, [{block,Bl0}|Is]) -> - Bl = [{set,[Dst],[Ctx],move}|Bl0], - [{block,Bl}|Is]; -prepend_move(Ctx, Dst, Is) -> - [{move,Ctx,Dst}|Is]. - -%% btb_reaches_match([Instruction], [Register], D) -> -%% {ok,MustSave}|{error,Reason} -%% -%% The list of Registers should be a list of registers referencing a -%% match context. The Register may contain one element if the -%% bs_get_binary2 instruction looks like -%% -%% test bs_get_binary2 {f,...} Ctx all _ _ Ctx -%% -%% or two elements if the instruction looks like -%% -%% test bs_get_binary2 {f,...} Ctx all _ _ Dst -%% -%% This function determines whether the bs_get_binary2 instruction -%% can be omitted (retaining the match context instead of creating -%% a sub binary). -%% -%% The rule is that the match context ultimately must end up at a -%% bs_start_match2 instruction and nowhere else. That it, it must not -%% be passed to BIFs, or copied or put into data structures. There -%% must only be one copy alive when the match context reaches the -%% bs_start_match2 instruction. -%% -%% At a branch, we must follow all branches and make sure that the above -%% rule is followed (or that the branch kills the match context). -%% -%% The MustSave return value will be true if control may end up at -%% bs_context_to_binary instruction. Since that instruction uses the -%% saved start position, we must use "bs_save2 Ctx start" to -%% update the saved start position. An additional complication is that -%% "bs_save2 Ctx start" must not be used if Dst and Ctx are -%% different registers and both registers may be passed to -%% a bs_context_to_binary instruction. -%% - -btb_reaches_match(Is, RegList, D) -> - try - Regs = btb_regs_from_list(RegList), - #btb{must_not_save=MustNotSave,must_save=MustSave} = - btb_reaches_match_1(Is, Regs, D), - case MustNotSave andalso MustSave of - true -> btb_error(must_and_must_not_save); - false -> {ok,MustSave} - end - catch - throw:{error,_}=Error -> Error - end. - -btb_reaches_match_1(Is, Regs, D) -> - case btb_are_registers_empty(Regs) of - false -> - btb_reaches_match_2(Is, Regs, D); - true -> - %% The context was killed, which is OK. - D - end. - -btb_reaches_match_2([{block,Bl}|Is], Regs0, D) -> - Regs = btb_reaches_match_block(Bl, Regs0), - btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([{call,Arity,{f,Lbl}}|Is], Regs0, D) -> - case is_tail_call(Is) of - true -> - Regs1 = btb_kill_not_live(Arity, Regs0), - Regs = btb_kill_yregs(Regs1), - btb_tail_call(Lbl, Regs, D); - false -> - btb_call(Arity, Lbl, Regs0, Is, D) - end; -btb_reaches_match_2([{apply,Arity}|Is], Regs, D) -> - btb_call(Arity+2, apply, Regs, Is, D); -btb_reaches_match_2([{call_fun,Live}=I|Is], Regs, D) -> - btb_ensure_not_used([{x,Live}], I, Regs), - btb_call(Live, I, Regs, Is, D); -btb_reaches_match_2([{make_fun2,_,_,_,Live}|Is], Regs, D) -> - btb_call(Live, make_fun2, Regs, Is, D); -btb_reaches_match_2([{call_ext,Arity,Func}=I|Is], Regs0, D) -> - %% Allow us scanning beyond the call in case the match - %% context is saved on the stack. - case beam_jump:is_exit_instruction(I) of - false -> - btb_call(Arity, Func, Regs0, Is, D); - true -> - Regs = btb_kill_not_live(Arity, Regs0), - btb_tail_call(Func, Regs, D) - end; -btb_reaches_match_2([{kill,Y}|Is], Regs, D) -> - btb_reaches_match_1(Is, btb_kill([Y], Regs), D); -btb_reaches_match_2([{deallocate,_}|Is], Regs0, D) -> - Regs = btb_kill_yregs(Regs0), - btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([return=I|_], Regs0, D) -> - btb_ensure_not_used([{x,0}], I, Regs0), - D; -btb_reaches_match_2([{gc_bif,_,{f,F},Live,Ss,Dst}=I|Is], Regs0, D0) -> - btb_ensure_not_used(Ss, I, Regs0), - Regs1 = btb_kill_not_live(Live, Regs0), - Regs = btb_kill([Dst], Regs1), - D = btb_follow_branch(F, Regs, D0), - btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([{bif,_,{f,F},Ss,Dst}=I|Is], Regs0, D0) -> - btb_ensure_not_used(Ss, I, Regs0), - Regs = btb_kill([Dst], Regs0), - D = btb_follow_branch(F, Regs, D0), - btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([{get_map_elements,{f,F},Src,{list,Ls}}=I|Is], Regs0, D0) -> - {Ss,Ds} = beam_utils:split_even(Ls), - btb_ensure_not_used([Src|Ss], I, Regs0), - Regs = btb_kill(Ds, Regs0), - D = btb_follow_branch(F, Regs, D0), - btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([{test,bs_start_match2,{f,F},Live,[Ctx,_],Ctx}=I|Is], - Regs0, D0) -> - CtxRegs = btb_context_regs(Regs0), - case member(Ctx, CtxRegs) of - false -> - %% This bs_start_match2 instruction does not use "our" - %% match state. Therefore we can continue the search - %% for another bs_start_match2 instruction. - D = btb_follow_branch(F, Regs0, D0), - Regs = btb_kill_not_live(Live, Regs0), - btb_reaches_match_2(Is, Regs, D); - true -> - %% OK. This instruction will use "our" match state, - %% but we must make sure that all other copies of the - %% match state are killed in the code that follows - %% the instruction. (We know that the fail branch cannot - %% be taken in this case.) - OtherCtxRegs = CtxRegs -- [Ctx], - case btb_are_all_unused(OtherCtxRegs, Is, D0) of - false -> btb_error({OtherCtxRegs,not_all_unused_after,I}); - true -> D0 - end - end; -btb_reaches_match_2([{test,bs_start_match2,{f,F},Live,[Bin,_],Ctx}|Is], - Regs0, D0) -> - CtxRegs = btb_context_regs(Regs0), - case member(Bin, CtxRegs) orelse member(Ctx, CtxRegs) of - false -> - %% This bs_start_match2 does not reference any copy of the - %% match state. Therefore it can safely be passed on the - %% way to another (perhaps more suitable) bs_start_match2 - %% instruction. - D = btb_follow_branch(F, Regs0, D0), - Regs = btb_kill_not_live(Live, Regs0), - btb_reaches_match_2(Is, Regs, D); - true -> - %% This variant of the bs_start_match2 instruction does - %% not accept a match state as source. - btb_error(unsuitable_bs_start_match) - end; -btb_reaches_match_2([{test,_,{f,F},Ss}=I|Is], Regs, D0) -> - btb_ensure_not_used(Ss, I, Regs), - D1 = btb_follow_branch(F, Regs, D0), - D = case Is of - [{bs_context_to_binary,_}|_] -> - %% bs_context_to_binary following a test instruction - %% probably needs the current position to be saved as - %% the new start position, but we can't be sure. - %% Therefore, conservatively disable the optimization - %% (instead of forcing a saving of the position). - D1#btb{must_save=true,must_not_save=true}; - _ -> - D1 - end, - btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([{test,_,{f,F},_,Ss,_}=I|Is], Regs, D0) -> - btb_ensure_not_used(Ss, I, Regs), - D = btb_follow_branch(F, Regs, D0), - btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([{select,_,Src,{f,F},Conds}=I|Is], Regs, D0) -> - btb_ensure_not_used([Src], I, Regs), - D1 = btb_follow_branch(F, Regs, D0), - D = btb_follow_branches(Conds, Regs, D1), - btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([{jump,{f,Lbl}}|_], Regs, #btb{index=Li}=D) -> - Is = fetch_code_at(Lbl, Li), - btb_reaches_match_2(Is, Regs, D); -btb_reaches_match_2([{label,_}|Is], Regs, D) -> - btb_reaches_match_2(Is, Regs, D); -btb_reaches_match_2([{bs_init,{f,0},_,_,Ss,Dst}=I|Is], Regs, D) -> - btb_ensure_not_used(Ss, I, Regs), - btb_reaches_match_1(Is, btb_kill([Dst], Regs), D); -btb_reaches_match_2([{bs_put,{f,0},_,Ss}=I|Is], Regs, D) -> - btb_ensure_not_used(Ss, I, Regs), - btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([{bs_restore2,Src,_}=I|Is], Regs0, D) -> - case btb_contains_context(Src, Regs0) of - false -> - btb_reaches_match_1(Is, Regs0, D); - true -> - %% Check that all other copies of the context registers - %% are unused by the following instructions. - Regs = btb_kill([Src], Regs0), - CtxRegs = btb_context_regs(Regs), - case btb_are_all_unused(CtxRegs, Is, D) of - false -> btb_error({CtxRegs,not_all_unused_after,I}); - true -> D#btb{must_not_save=true} - end - end; -btb_reaches_match_2([{bs_context_to_binary,Src}=I|Is], Regs0, D) -> - case btb_contains_context(Src, Regs0) of - false -> - btb_reaches_match_1(Is, Regs0, D); - true -> - %% Check that all other copies of the context registers - %% are unused by the following instructions. - Regs = btb_kill([Src], Regs0), - CtxRegs = btb_context_regs(Regs), - case btb_are_all_unused(CtxRegs, Is, D) of - false -> btb_error({CtxRegs,not_all_unused_after,I}); - true -> D#btb{must_not_save=true} - end - end; -btb_reaches_match_2([{badmatch,Src}=I|_], Regs, D) -> - btb_ensure_not_used([Src], I, Regs), - D; -btb_reaches_match_2([{case_end,Src}=I|_], Regs, D) -> - btb_ensure_not_used([Src], I, Regs), - D; -btb_reaches_match_2([if_end|_], _Regs, D) -> - D; -btb_reaches_match_2([{func_info,_,_,Arity}=I|_], Regs0, D) -> - Regs = btb_kill_yregs(btb_kill_not_live(Arity, Regs0)), - case btb_context_regs(Regs) of - [] -> D; - _ -> {binary_used_in,I} - end; -btb_reaches_match_2([{line,_}|Is], Regs, D) -> - btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([I|_], Regs, _) -> - btb_error({btb_context_regs(Regs),I,not_handled}). - -is_tail_call([{deallocate,_}|_]) -> true; -is_tail_call([return|_]) -> true; -is_tail_call(_) -> false. - -btb_call(Arity, Lbl, Regs0, Is, D0) -> - Regs = btb_kill_not_live(Arity, Regs0), - case btb_are_x_registers_empty(Regs) of - false -> - %% There is a match context in one of the x registers. - %% First handle the call as if it were a tail call. - D = btb_tail_call(Lbl, Regs, D0), - - %% No problem so far (the called function can handle a - %% match context). Now we must make sure that we don't - %% have any copies of the match context tucked away in an - %% y register. - RegList = btb_context_regs(Regs), - case [R || {y,_}=R <- RegList] of - [] -> - D; - [_|_] -> - btb_error({multiple_uses,RegList}) - end; - true -> - %% No match context in any x register. It could have been - %% saved to an y register, so continue to scan the code following - %% the call. - btb_reaches_match_1(Is, Regs, D0) - end. - -btb_tail_call(Lbl, Regs, #btb{f=Ftree,must_save=MustSave0}=D) -> - %% Ignore any y registers here. - case [R || {x,_}=R <- btb_context_regs(Regs)] of - [] -> - D; - [{x,_}=Reg] -> - case gb_trees:lookup(Lbl, Ftree) of - {value,{Reg,MustSave}} -> - D#btb{must_save=MustSave0 or MustSave}; - _ when is_integer(Lbl) -> - btb_error({{label,Lbl},no_suitable_bs_start_match}); - _ -> - btb_error({binary_used_in,Lbl}) - end; - [_|_] when not is_integer(Lbl) -> - btb_error({binary_used_in,Lbl}); - [_|_]=RegList -> - btb_error({multiple_uses,RegList}) - end. - -%% btb_follow_branches([Cond], Regs, D) -> D' -%% Recursively follow all the branches. - -btb_follow_branches([{f,Lbl}|T], Regs, D0) -> - D = btb_follow_branch(Lbl, Regs, D0), - btb_follow_branches(T, Regs, D); -btb_follow_branches([_|T], Regs, D) -> - btb_follow_branches(T, Regs, D); -btb_follow_branches([], _, D) -> D. - -%% btb_follow_branch(Lbl, Regs, D) -> D' -%% Recursively follow the branch. - -btb_follow_branch(0, _Regs, D) -> D; -btb_follow_branch(Lbl, Regs, #btb{ok_br=Br0,index=Li}=D) -> - Key = {Lbl,Regs}, - case gb_sets:is_member(Key, Br0) of - true -> - %% We have already followed this branch and it was OK. - D; - false -> - %% New branch. Try it. - Is = fetch_code_at(Lbl, Li), - #btb{ok_br=Br,must_not_save=MustNotSave,must_save=MustSave} = - btb_reaches_match_1(Is, Regs, D), - - %% Since we got back, this branch is OK. - D#btb{ok_br=gb_sets:insert(Key, Br),must_not_save=MustNotSave, - must_save=MustSave} - end. - -btb_reaches_match_block([{set,Ds,Ss,{alloc,Live,_}}=I|Is], Regs0) -> - %% An allocation instruction or a GC bif. We'll kill all registers - %% if any copy of the context is used as the source to the BIF. - btb_ensure_not_used(Ss, I, Regs0), - Regs1 = btb_kill_not_live(Live, Regs0), - Regs = btb_kill(Ds, Regs1), - btb_reaches_match_block(Is, Regs); -btb_reaches_match_block([{set,[Dst]=Ds,[Src],move}|Is], Regs0) -> - Regs1 = btb_kill(Ds, Regs0), - Regs = case btb_contains_context(Src, Regs1) of - false -> Regs1; - true -> btb_set_context(Dst, Regs1) - end, - btb_reaches_match_block(Is, Regs); -btb_reaches_match_block([{set,Ds,Ss,_}=I|Is], Regs0) -> - btb_ensure_not_used(Ss, I, Regs0), - Regs = btb_kill(Ds, Regs0), - btb_reaches_match_block(Is, Regs); -btb_reaches_match_block([], Regs) -> - Regs. - -%% btb_are_all_killed([Register], [Instruction], D) -> true|false -%% Test whether all of the register are unused in the instruction stream. - -btb_are_all_unused(RegList, Is, #btb{index=Li}) -> - all(fun(R) -> - beam_utils:is_not_used(R, Is, Li) - end, RegList). - -%% btp_regs_from_list([Register]) -> RegisterSet. -%% Create a register set from a list of registers. - -btb_regs_from_list(L) -> - foldl(fun(R, Regs) -> - btb_set_context(R, Regs) - end, {0,0}, L). - -%% btb_set_context(Register, RegisterSet) -> RegisterSet' -%% Update RegisterSet to indicate that Register contains the matching context. - -btb_set_context({x,N}, {Xregs,Yregs}) -> - {Xregs bor (1 bsl N),Yregs}; -btb_set_context({y,N}, {Xregs,Yregs}) -> - {Xregs,Yregs bor (1 bsl N)}. - -%% btb_ensure_not_used([Register], Instruction, RegisterSet) -> ok -%% If any register in RegisterSet (the register(s) known to contain -%% the match context) is used in the list of registers, generate an error. - -btb_ensure_not_used(Rs, I, Regs) -> - case lists:any(fun(R) -> btb_contains_context(R, Regs) end, Rs) of - true -> btb_error({binary_used_in,I}); - false -> ok - end. - -%% btb_kill([Register], RegisterSet) -> RegisterSet' -%% Kill all registers mentioned in the list of registers. - -btb_kill([{x,N}|Rs], {Xregs,Yregs}) -> - btb_kill(Rs, {Xregs band (bnot (1 bsl N)),Yregs}); -btb_kill([{y,N}|Rs], {Xregs,Yregs}) -> - btb_kill(Rs, {Xregs,Yregs band (bnot (1 bsl N))}); -btb_kill([{fr,_}|Rs], Regs) -> - btb_kill(Rs, Regs); -btb_kill([], Regs) -> Regs. - -%% btb_kill_not_live(Live, RegisterSet) -> RegisterSet' -%% Kill all registers indicated not live by Live. - -btb_kill_not_live(Live, {Xregs,Yregs}) -> - {Xregs band ((1 bsl Live)-1),Yregs}. - -%% btb_kill(Regs0) -> Regs -%% Kill all y registers. - -btb_kill_yregs({Xregs,_}) -> {Xregs,0}. - -%% btb_are_registers_empty(RegisterSet) -> true|false -%% Test whether the register set is empty. - -btb_are_registers_empty({0,0}) -> true; -btb_are_registers_empty({_,_}) -> false. - -%% btb_are_x_registers_empty(Regs) -> true|false -%% Test whether the x registers are empty. - -btb_are_x_registers_empty({0,_}) -> true; -btb_are_x_registers_empty({_,_}) -> false. - -%% btb_contains_context(Register, RegisterSet) -> true|false -%% Test whether Register contains the context. - -btb_contains_context({x,N}, {Regs,_}) -> Regs band (1 bsl N) =/= 0; -btb_contains_context({y,N}, {_,Regs}) -> Regs band (1 bsl N) =/= 0; -btb_contains_context(_, _) -> false. - -%% btb_context_regs(RegisterSet) -> [Register] -%% Convert the register set to an explicit list of registers. -btb_context_regs({Xregs,Yregs}) -> - btb_context_regs_1(Xregs, 0, x, btb_context_regs_1(Yregs, 0, y, [])). - -btb_context_regs_1(0, _, _, Acc) -> - Acc; -btb_context_regs_1(Regs, N, Tag, Acc) when (Regs band 1) =:= 1 -> - btb_context_regs_1(Regs bsr 1, N+1, Tag, [{Tag,N}|Acc]); -btb_context_regs_1(Regs, N, Tag, Acc) -> - btb_context_regs_1(Regs bsr 1, N+1, Tag, Acc). - -%% btb_index([Function]) -> GbTree({EntryLabel,{Register,MustSave}}) -%% Build an index of functions that accept a match context instead of -%% a binary. MustSave is true if the function may pass the match -%% context to the bs_context_to_binary instruction (in which case -%% the current position in the binary must have saved into the -%% start position using "bs_save_2 Ctx start"). - -btb_index(Fs) -> - btb_index_1(Fs, []). - -btb_index_1([{function,_,_,Entry,Is0}|Fs], Acc0) -> - Is = drop_to_label(Is0, Entry), - Acc = btb_index_2(Is, Entry, false, Acc0), - btb_index_1(Fs, Acc); -btb_index_1([], Acc) -> gb_trees:from_orddict(sort(Acc)). - -btb_index_2([{test,bs_start_match2,{f,_},_,[Reg,_],Reg}|_], - Entry, MustSave, Acc) -> - [{Entry,{Reg,MustSave}}|Acc]; -btb_index_2(Is0, Entry, _, Acc) -> - try btb_index_find_start_match(Is0) of - Is -> btb_index_2(Is, Entry, true, Acc) - catch - throw:none -> Acc - end. - -drop_to_label([{label,L}|Is], L) -> Is; -drop_to_label([_|Is], L) -> drop_to_label(Is, L). - -btb_index_find_start_match([{test,_,{f,F},_},{bs_context_to_binary,_}|Is]) -> - btb_index_find_label(Is, F); -btb_index_find_start_match(_) -> - throw(none). - -btb_index_find_label([{label,L}|Is], L) -> Is; -btb_index_find_label([_|Is], L) -> btb_index_find_label(Is, L). - -btb_error(Error) -> - throw({error,Error}). - -fetch_code_at(Lbl, Li) -> - case beam_utils:code_at(Lbl, Li) of - Is when is_list(Is) -> Is - end. - -%%% -%%% Compilation information warnings. -%%% - -btb_comment_opt({field_flags,[{anno,A}|_]}) -> - {'%',{bin_opt,A}}; -btb_comment_opt(_) -> - {'%',{bin_opt,[]}}. - -btb_comment_no_opt(Reason, {field_flags,[{anno,A}|_]}) -> - {'%',{no_bin_opt,Reason,A}}; -btb_comment_no_opt(Reason, _) -> - {'%',{no_bin_opt,Reason,[]}}. - -collect_warnings(Fs) -> - D = warning_index_functions(Fs), - foldl(fun(F, A) -> collect_warnings_fun(F, D, A) end, [], Fs). - -collect_warnings_fun({function,_,_,_,Is}, D, A) -> - collect_warnings_instr(Is, D, A). - -collect_warnings_instr([{'%',{bin_opt,Where}}|Is], D, Acc0) -> - Acc = add_warning(bin_opt, Where, Acc0), - collect_warnings_instr(Is, D, Acc); -collect_warnings_instr([{'%',{no_bin_opt,Reason0,Where}}|Is], D, Acc0) -> - Reason = warning_translate_label(Reason0, D), - Acc = add_warning({no_bin_opt,Reason}, Where, Acc0), - collect_warnings_instr(Is, D, Acc); -collect_warnings_instr([_|Is], D, Acc) -> - collect_warnings_instr(Is, D, Acc); -collect_warnings_instr([], _, Acc) -> Acc. - -add_warning(Term, Anno, Ws) -> - Line = get_line(Anno), - File = get_file(Anno), - [{File,[{Line,?MODULE,Term}]}|Ws]. - -warning_translate_label(Term, D) when is_tuple(Term) -> - case element(1, Term) of - {label,F} -> - FA = gb_trees:get(F, D), - setelement(1, Term, FA); - _ -> Term - end; -warning_translate_label(Term, _) -> Term. - -get_line([Line|_]) when is_integer(Line) -> Line; -get_line([_|T]) -> get_line(T); -get_line([]) -> none. - -get_file([{file,File}|_]) -> File; -get_file([_|T]) -> get_file(T); -get_file([]) -> "no_file". % should not happen - -warning_index_functions(Fs) -> - D = [{Entry,{F,A}} || {function,F,A,Entry,_} <- Fs], - gb_trees:from_orddict(sort(D)). - -format_error_1({binary_used_in,{extfunc,M,F,A}}) -> - [io_lib:format("sub binary used by ~p:~p/~p", [M,F,A])| - case {M,F,A} of - {erlang,split_binary,2} -> - "; SUGGEST using binary matching instead of split_binary/2"; - _ -> - "" - end]; -format_error_1({binary_used_in,_}) -> - "sub binary is used or returned"; -format_error_1({multiple_uses,_}) -> - "sub binary is matched or used in more than one place"; -format_error_1(unsuitable_bs_start_match) -> - "the binary matching instruction that follows in the same function " - "have problems that prevent delayed sub binary optimization " - "(probably indicated by INFO warnings)"; -format_error_1({{F,A},no_suitable_bs_start_match}) -> - io_lib:format("called function ~p/~p does not begin with a suitable " - "binary matching instruction", [F,A]); -format_error_1(must_and_must_not_save) -> - "different control paths use different positions in the binary"; -format_error_1({_,I,not_handled}) -> - case I of - {'catch',_,_} -> - "the compiler currently does not attempt the delayed sub binary " - "optimization when catch is used"; - {'try',_,_} -> - "the compiler currently does not attempt the delayed sub binary " - "optimization when try/catch is used"; - _ -> - io_lib:format("compiler limitation: instruction ~p prevents " - "delayed sub binary optimization", [I]) - end; -format_error_1(Term) -> - io_lib:format("~w", [Term]). diff --git a/lib/compiler/src/beam_disasm.erl b/lib/compiler/src/beam_disasm.erl index d0be39f520..7d048716e4 100644 --- a/lib/compiler/src/beam_disasm.erl +++ b/lib/compiler/src/beam_disasm.erl @@ -1105,6 +1105,16 @@ resolve_inst({get_hd,[Src,Dst]},_,_,_) -> resolve_inst({get_tl,[Src,Dst]},_,_,_) -> {get_tl,Src,Dst}; +%% OTP 22 +resolve_inst({bs_start_match3,[Fail,Bin,Live,Dst]},_,_,_) -> + {bs_start_match3,Fail,Bin,Live,Dst}; +resolve_inst({bs_get_tail,[Src,Dst,Live]},_,_,_) -> + {bs_get_tail,Src,Dst,Live}; +resolve_inst({bs_get_position,[Src,Dst,Live]},_,_,_) -> + {bs_get_position,Src,Dst,Live}; +resolve_inst({bs_set_position,[Src,Dst]},_,_,_) -> + {bs_set_position,Src,Dst}; + %% %% OTP 22. %% diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl index 6d0a8db2dc..fbff4cfd79 100644 --- a/lib/compiler/src/beam_jump.erl +++ b/lib/compiler/src/beam_jump.erl @@ -367,8 +367,6 @@ extract_seq([{line,_}=Line|Is], Acc) -> extract_seq(Is, [Line|Acc]); extract_seq([{block,_}=Bl|Is], Acc) -> extract_seq_1(Is, [Bl|Acc]); -extract_seq([{bs_context_to_binary,_}=I|Is], Acc) -> - extract_seq_1(Is, [I|Acc]); extract_seq([{label,_}|_]=Is, Acc) -> extract_seq_1(Is, Acc); extract_seq(_, _) -> no. diff --git a/lib/compiler/src/beam_kernel_to_ssa.erl b/lib/compiler/src/beam_kernel_to_ssa.erl index c55a57ab32..d6e675ae72 100644 --- a/lib/compiler/src/beam_kernel_to_ssa.erl +++ b/lib/compiler/src/beam_kernel_to_ssa.erl @@ -276,12 +276,11 @@ select_nil(#k_val_clause{val=#k_nil{},body=B}, V, Tf, Vf, St0) -> {Is ++ Bis,St}. select_binary(#k_val_clause{val=#k_binary{segs=#k_var{name=Ctx0}},body=B}, - #k_var{anno=Anno0}=Src, Tf, Vf, St0) -> - Anno = #{reuse_for_context=>member(reuse_for_context, Anno0)}, + #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), - Bis1 = [#b_set{anno=Anno,op=bs_start_match,dst=Ctx, + Bis1 = [#b_set{op=bs_start_match,dst=Ctx, args=[ssa_arg(Src, St)]}] ++ TestIs ++ Bis0, Bis = finish_bs_matching(Bis1), {Bis,St}. @@ -708,10 +707,6 @@ bif_cg(#k_bif{op=#k_remote{mod=#k_atom{val=erlang},name=#k_atom{val=Name}}, %% internal_cg(Bif, [Arg], [Ret], Le, State) -> %% {[Ainstr],State}. -internal_cg(bs_context_to_binary, [Src0], [], _Le, St) -> - Src = ssa_arg(Src0, St), - Set = #b_set{op=context_to_binary,args=[Src]}, - {[Set],St}; internal_cg(dsetelement, [Index0,Tuple0,New0], _Rs, _Le, St) -> [New,Tuple,#b_literal{val=Index1}] = ssa_args([New0,Tuple0,Index0], St), Index = #b_literal{val=Index1-1}, diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl index 9d10d4aec3..1a2e759965 100644 --- a/lib/compiler/src/beam_ssa.erl +++ b/lib/compiler/src/beam_ssa.erl @@ -20,12 +20,15 @@ %% Purpose: Type definitions and utilities for the SSA format. -module(beam_ssa). --export([add_anno/3,get_anno/2, - clobbers_xregs/1,def/2,def_used/2,dominators/1, +-export([add_anno/3,get_anno/2,get_anno/3, + clobbers_xregs/1,def/2,def_used/2, + definitions/1, + dominators/1, flatmapfold_instrs_rpo/4, fold_po/3,fold_po/4,fold_rpo/3,fold_rpo/4, fold_instrs_rpo/4, linearize/1, + mapfold_blocks_rpo/4, mapfold_instrs_rpo/4, normalize/1, no_side_effect/1, @@ -35,14 +38,17 @@ split_blocks/3, successors/1,successors/2, trim_unreachable/1, - update_phi_labels/4,used/1]). + update_phi_labels/4,used/1, + uses/1,uses/2]). -export_type([b_module/0,b_function/0,b_blk/0,b_set/0, b_ret/0,b_br/0,b_switch/0,terminator/0, b_var/0,b_literal/0,b_remote/0,b_local/0, value/0,argument/0,label/0, var_name/0,var_base/0,literal_value/0, - op/0,anno/0,block_map/0]). + op/0,anno/0,block_map/0,dominator_map/0, + rename_map/0,rename_proplist/0,usage_map/0, + definition_map/0]). -include("beam_ssa.hrl"). @@ -56,6 +62,9 @@ -type b_switch() :: #b_switch{}. -type terminator() :: b_br() | b_ret() | b_switch(). +-type construct() :: b_module() | b_function() | b_blk() | b_set() | + terminator(). + -type b_var() :: #b_var{}. -type b_literal() :: #b_literal{}. -type b_remote() :: #b_remote{}. @@ -76,6 +85,11 @@ -type anno() :: #{atom() := any()}. -type block_map() :: #{label():=b_blk()}. +-type dominator_map() :: #{label():=ordsets:ordset(label())}. +-type usage_map() :: #{b_var():=[{label(),b_set() | terminator()}]}. +-type definition_map() :: #{b_var():=b_set()}. +-type rename_map() :: #{b_var():=value()}. +-type rename_proplist() :: [{b_var(),value()}]. %% Note: By default, dialyzer will collapse this type to atom(). %% To avoid the collapsing, change the value of SET_LIMIT to 50 in the @@ -84,7 +98,7 @@ -type prim_op() :: 'bs_add' | 'bs_extract' | 'bs_init' | 'bs_init_writable' | 'bs_match' | 'bs_put' | 'bs_start_match' | 'bs_test_tail' | 'bs_utf16_size' | 'bs_utf8_size' | 'build_stacktrace' | - 'call' | 'catch_end' | 'context_to_binary' | + 'call' | 'catch_end' | 'extract' | 'get_hd' | 'get_map_element' | 'get_tl' | 'get_tuple_element' | 'has_map_field' | @@ -103,14 +117,14 @@ %% Primops only used internally during code generation. -type cg_prim_op() :: 'bs_get' | 'bs_match_string' | 'bs_restore' | 'bs_skip' | -'copy' | 'put_tuple_arity' | 'put_tuple_element'. + 'copy' | 'put_tuple_arity' | 'put_tuple_element'. -import(lists, [foldl/3,keyfind/3,mapfoldl/3,member/2,reverse/1]). -spec add_anno(Key, Value, Construct) -> Construct when Key :: atom(), Value :: any(), - Construct :: b_function() | b_blk() | b_set() | terminator(). + Construct :: construct(). add_anno(Key, Val, #b_function{anno=Anno}=Bl) -> Bl#b_function{anno=Anno#{Key=>Val}}; @@ -125,11 +139,17 @@ add_anno(Key, Val, #b_ret{anno=Anno}=Bl) -> add_anno(Key, Val, #b_switch{anno=Anno}=Bl) -> Bl#b_switch{anno=Anno#{Key=>Val}}. --spec get_anno(atom(), b_blk()|b_set()|terminator()) -> any(). +-spec get_anno(atom(), construct()) -> any(). get_anno(Key, Construct) -> maps:get(Key, get_anno(Construct)). +-spec get_anno(atom(), construct(),any()) -> any(). + +get_anno(Key, Construct, Default) -> + maps:get(Key, get_anno(Construct), Default). + +get_anno(#b_function{anno=Anno}) -> Anno; get_anno(#b_blk{anno=Anno}) -> Anno; get_anno(#b_set{anno=Anno}) -> Anno; get_anno(#b_br{anno=Anno}) -> Anno; @@ -169,6 +189,7 @@ no_side_effect(#b_set{op=Op}) -> bs_match -> true; bs_start_match -> true; bs_test_tail -> true; + bs_get_tail -> true; bs_put -> true; extract -> true; get_hd -> true; @@ -306,7 +327,7 @@ def_used(Ls, Blocks) -> -spec dominators(Blocks) -> Result when Blocks :: block_map(), - Result :: #{label():=ordsets:ordset(label())}. + Result :: dominator_map(). dominators(Blocks) -> Preds = predecessors(Blocks), @@ -327,6 +348,26 @@ fold_instrs_rpo(Fun, From, Acc0, Blocks) -> Top = rpo(From, Blocks), fold_instrs_rpo_1(Top, Fun, Blocks, Acc0). +%% Like mapfold_instrs_rpo but at the block level to support lookahead and +%% scope-dependent transformations. +-spec mapfold_blocks_rpo(Fun, From, Acc, Blocks) -> Result when + Fun :: fun((label(), b_blk(), any()) -> {b_blk(), any()}), + From :: [label()], + Acc :: any(), + Blocks :: block_map(), + Result :: {block_map(), any()}. +mapfold_blocks_rpo(Fun, From, Acc, Blocks) -> + Successors = rpo(From, Blocks), + foldl(fun(Lbl, A) -> + mapfold_blocks_rpo_1(Fun, Lbl, A) + end, {Blocks, Acc}, Successors). + +mapfold_blocks_rpo_1(Fun, Lbl, {Blocks0, Acc0}) -> + Block0 = maps:get(Lbl, Blocks0), + {Block, Acc} = Fun(Lbl, Block0, Acc0), + Blocks = maps:put(Lbl, Block, Blocks0), + {Blocks, Acc}. + -spec mapfold_instrs_rpo(Fun, From, Acc0, Blocks0) -> {Blocks,Acc} when Fun :: fun((b_blk()|terminator(), any()) -> any()), From :: [label()], @@ -442,7 +483,7 @@ rpo(From, Blocks) -> Ls. -spec rename_vars(Rename, [label()], block_map()) -> block_map() when - Rename :: [{var_name(),value()}] | #{var_name():=value()}. + Rename :: rename_map() | rename_proplist(). rename_vars(Rename, From, Blocks) when is_list(Rename) -> rename_vars(maps:from_list(Rename), From, Blocks); @@ -535,6 +576,34 @@ used(#b_switch{arg=#b_var{}=V}) -> [V]; used(_) -> []. +-spec definitions(Blocks :: block_map()) -> definition_map(). +definitions(Blocks) -> + beam_ssa:fold_instrs_rpo(fun(#b_set{ dst = Var }=I, Acc) -> + maps:put(Var, I, Acc); + (_Terminator, Acc) -> + Acc + end, [0], #{}, Blocks). + +-spec uses(Blocks :: block_map()) -> usage_map(). +uses(Blocks) -> + uses([0], Blocks). + +-spec uses(From, Blocks) -> usage_map() when + From :: [label()], + Blocks :: block_map(). +uses(From, Blocks) -> + beam_ssa:fold_rpo(fun fold_uses_block/3, From, #{}, Blocks). + +fold_uses_block(Lbl, #b_blk{is=Is,last=Last}, UseMap0) -> + F = fun(I, UseMap) -> + foldl(fun(Var, Acc) -> + Uses0 = maps:get(Var, Acc, []), + Uses = [{Lbl, I} | Uses0], + maps:put(Var, Uses, Acc) + end, UseMap, beam_ssa:used(I)) + end, + F(Last, foldl(F, UseMap0, Is)). + %%% %%% Internal functions. %%% diff --git a/lib/compiler/src/beam_ssa_bsm.erl b/lib/compiler/src/beam_ssa_bsm.erl new file mode 100644 index 0000000000..2efeb6b5b6 --- /dev/null +++ b/lib/compiler/src/beam_ssa_bsm.erl @@ -0,0 +1,1027 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2018. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% + +%%% +%%% This pass optimizes bit syntax matching, and is centered around the concept +%%% of "match context reuse" which is best explained through example. To put it +%%% shortly we attempt to turn this: +%%% +%%% <<0,B/bits>> = A, +%%% <<1,C/bits>> = B, +%%% <<D,_/bits>> = C, +%%% D. +%%% +%%% ... Into this: +%%% +%%% <<0,1,D,_/bits>>=A, +%%% D. +%%% +%%% Which is much faster as it avoids the creation of intermediate terms. This +%%% is especially noticeable in loops where such garbage is generated on each +%%% iteration. +%%% +%%% The optimization itself is very simple and can be applied whenever there's +%%% matching on the tail end of a binary; instead of creating a new binary and +%%% starting a new match context on it, we reuse the match context used to +%%% extract the tail and avoid the creation of both objects. +%%% +%%% The catch is that a match context isn't a proper type and nothing outside +%%% of bit syntax match operations can handle them. We therefore need to make +%%% sure that they never "leak" into other instructions, and most of the pass +%%% revolves around getting around that limitation. +%%% +%%% Unlike most other passes we look at the whole module so we can combine +%%% matches across function boundaries, greatly increasing the performance of +%%% complex matches and loops. +%%% + +-module(beam_ssa_bsm). + +-export([module/2, format_error/1]). + +-include("beam_ssa.hrl"). + +-import(lists, [member/2, reverse/1, splitwith/2, map/2, foldl/3, mapfoldl/3, + nth/2, max/1, unzip/1]). + +-spec format_error(term()) -> nonempty_string(). + +format_error(OptInfo) -> + format_opt_info(OptInfo). + +-spec module(Module, Options) -> Result when + Module :: beam_ssa:b_module(), + Options :: [compile:option()], + Result :: {ok, beam_ssa:b_module(), list()}. + +-define(PASS(N), {N,fun N/1}). + +module(#b_module{body=Fs0}=Module, Opts) -> + ModInfo = analyze_module(Module), + + %% combine_matches is repeated after accept_context_args as the control + %% flow changes can enable further optimizations, as in the example below: + %% + %% a(<<0,X/binary>>) -> a(X); + %% a(A) when bit_size(A) =:= 52 -> bar; + %% a(<<1,X/binary>>) -> X. %% Match context will be reused here when + %% %% when repeated. + + {Fs, _} = compile:run_sub_passes( + [?PASS(combine_matches), + ?PASS(accept_context_args), + ?PASS(combine_matches), + ?PASS(allow_context_passthrough), + ?PASS(skip_outgoing_tail_extraction), + ?PASS(annotate_context_parameters)], + {Fs0, ModInfo}), + + Ws = case proplists:get_bool(bin_opt_info, Opts) of + true -> collect_opt_info(Fs); + false -> [] + end, + + {ok, Module#b_module{body=Fs}, Ws}. + +-type module_info() :: #{ func_id() => func_info() }. + +-type func_id() :: {Name :: atom(), Arity :: non_neg_integer()}. + +-type func_info() :: #{ has_bsm_ops => boolean(), + parameters => [#b_var{}], + parameter_info => #{ #b_var{} => param_info() } }. + +-type param_info() :: suitable_for_reuse | + {Problem :: atom(), Where :: term()}. + +-spec analyze_module(#b_module{}) -> module_info(). + +analyze_module(#b_module{body=Fs}) -> + foldl(fun(#b_function{args=Parameters}=F, I) -> + FuncInfo = #{ has_bsm_ops => has_bsm_ops(F), + parameters => Parameters, + parameter_info => #{} }, + FuncId = get_fa(F), + I#{ FuncId => FuncInfo } + end, #{}, Fs). + +has_bsm_ops(#b_function{bs=Blocks}) -> + hbo_blocks(maps:to_list(Blocks)). + +hbo_blocks([{_,#b_blk{is=Is}} | Blocks]) -> + case hbo_is(Is) of + false -> hbo_blocks(Blocks); + true -> true + end; +hbo_blocks([]) -> + false. + +hbo_is([#b_set{op=bs_start_match} | _]) -> true; +hbo_is([_I | Is]) -> hbo_is(Is); +hbo_is([]) -> false. + +%% Checks whether it's legal to make a call with the given argument as a match +%% context, returning the param_info() of the relevant parameter. +-spec check_context_call(#b_set{}, Arg, CtxChain, ModInfo) -> param_info() when + Arg :: #b_var{}, + CtxChain :: [#b_var{}], + ModInfo :: module_info(). +check_context_call(#b_set{args=Args}, Arg, CtxChain, ModInfo) -> + Aliases = [Arg | CtxChain], + ccc_1(Args, Arg, Aliases, ModInfo). + +ccc_1([#b_local{}=Call | Args], Ctx, Aliases, ModInfo) -> + %% Matching operations assume that their context isn't aliased (as in + %% pointer aliasing), so we must reject calls whose arguments contain more + %% than one reference to the context. + %% + %% TODO: Try to fall back to passing binaries in these cases. Partial reuse + %% is better than nothing. + UseCount = foldl(fun(Arg, C) -> + case member(Arg, Aliases) of + true -> C + 1; + false -> C + end + end, 0, Args), + if + UseCount =:= 1 -> + #b_local{name=#b_literal{val=Name},arity=Arity} = Call, + Callee = {Name, Arity}, + + ParamInfo = funcinfo_get(Callee, parameter_info, ModInfo), + Parameters = funcinfo_get(Callee, parameters, ModInfo), + Parameter = nth(1 + arg_index(Ctx, Args), Parameters), + + case maps:find(Parameter, ParamInfo) of + {ok, suitable_for_reuse} -> + suitable_for_reuse; + {ok, Other} -> + {unsuitable_call, {Call, Other}}; + error -> + {no_match_on_entry, Call} + end; + UseCount > 1 -> + {multiple_uses_in_call, Call} + end; +ccc_1([#b_remote{}=Call | _Args], _Ctx, _CtxChain, _ModInfo) -> + {remote_call, Call}; +ccc_1([Fun | _Args], _Ctx, _CtxChain, _ModInfo) -> + %% TODO: It may be possible to support this in the future for locally + %% defined funs, including ones with free variables. + {fun_call, Fun}. + +%% Returns the index of Var in Args. +arg_index(Var, Args) -> arg_index_1(Var, Args, 0). + +arg_index_1(Var, [Var | _Args], Index) -> Index; +arg_index_1(Var, [_Arg | Args], Index) -> arg_index_1(Var, Args, Index + 1). + +is_tail_binary(#b_set{op=bs_match,args=[#b_literal{val=binary} | Rest]}) -> + member(#b_literal{val=all}, Rest); +is_tail_binary(#b_set{op=bs_get_tail}) -> + true; +is_tail_binary(_) -> + false. + +is_tail_binary(#b_var{}=Var, Defs) -> + case find_match_definition(Var, Defs) of + {ok, Def} -> is_tail_binary(Def); + _ -> false + end; +is_tail_binary(_Literal, _Defs) -> + false. + +assert_match_context(#b_var{}=Var, Defs) -> + case maps:find(Var, Defs) of + {ok, #b_set{op=bs_match,args=[_,#b_var{}=Ctx|_]}} -> + assert_match_context(Ctx, Defs); + {ok, #b_set{op=bs_start_match}} -> + ok + end. + +find_match_definition(#b_var{}=Var, Defs) -> + case maps:find(Var, Defs) of + {ok, #b_set{op=bs_extract,args=[Ctx]}} -> maps:find(Ctx, Defs); + {ok, #b_set{op=bs_get_tail}=Def} -> {ok, Def}; + _ -> error + end. + +%% Returns a list of all contexts that were used to extract Var. +context_chain_of(#b_var{}=Var, Defs) -> + case maps:find(Var, Defs) of + {ok, #b_set{op=bs_match,args=[_,#b_var{}=Ctx|_]}} -> + [Ctx | context_chain_of(Ctx, Defs)]; + {ok, #b_set{op=bs_get_tail,args=[Ctx]}} -> + [Ctx | context_chain_of(Ctx, Defs)]; + {ok, #b_set{op=bs_extract,args=[Ctx]}} -> + [Ctx | context_chain_of(Ctx, Defs)]; + _ -> + [] + end. + +%% Grabs the match context used to produce the given variable. +match_context_of(#b_var{}=Var, Defs) -> + Ctx = match_context_of_1(Var, Defs), + assert_match_context(Ctx, Defs), + Ctx. + +match_context_of_1(Var, Defs) -> + case maps:get(Var, Defs) of + #b_set{op=bs_extract,args=[#b_var{}=Ctx0]} -> + #b_set{op=bs_match, + args=[_,#b_var{}=Ctx|_]} = maps:get(Ctx0, Defs), + Ctx; + #b_set{op=bs_get_tail,args=[#b_var{}=Ctx]} -> + Ctx + end. + +funcinfo_get(#b_function{}=F, Attribute, ModInfo) -> + funcinfo_get(get_fa(F), Attribute, ModInfo); +funcinfo_get({_,_}=Key, Attribute, ModInfo) -> + FuncInfo = maps:get(Key, ModInfo), + maps:get(Attribute, FuncInfo). + +funcinfo_set(#b_function{}=F, Attribute, Value, ModInfo) -> + funcinfo_set(get_fa(F), Attribute, Value, ModInfo); +funcinfo_set(Key, Attribute, Value, ModInfo) -> + FuncInfo = maps:put(Attribute, Value, maps:get(Key, ModInfo, #{})), + maps:put(Key, FuncInfo, ModInfo). + +get_fa(#b_function{ anno = Anno }) -> + {_,Name,Arity} = maps:get(func_info, Anno), + {Name,Arity}. + +%% Replaces matched-out binaries with aliases that are lazily converted to +%% binary form when used, allowing us to keep the "match path" free of binary +%% creation. + +-spec alias_matched_binaries(Blocks, Counter, AliasMap) -> Result when + Blocks :: beam_ssa:block_map(), + Counter :: non_neg_integer(), + AliasMap :: match_alias_map(), + Result :: {Blocks, Counter}. + +-type match_alias_map() :: + #{ Binary :: #b_var{} => + { %% Replace all uses of Binary with an alias after this + %% label. + AliasAfter :: beam_ssa:label(), + %% The match context whose tail is equal to Binary. + Context :: #b_var{} } }. + +%% Keeps track of the promotions we need to insert. They're partially keyed by +%% location because they may not be valid on all execution paths and we may +%% need to add redundant promotions in some cases. +-type promotion_map() :: + #{ { PromoteAt :: beam_ssa:label(), + Variable :: #b_var{} } => + Instruction :: #b_set{} }. + +-record(amb, { dominators :: beam_ssa:dominator_map(), + match_aliases :: match_alias_map(), + cnt :: non_neg_integer(), + promotions = #{} :: promotion_map() }). + +alias_matched_binaries(Blocks0, Counter, AliasMap) when AliasMap =/= #{} -> + State0 = #amb{ dominators = beam_ssa:dominators(Blocks0), + match_aliases = AliasMap, + cnt = Counter }, + {Blocks, State} = beam_ssa:mapfold_blocks_rpo(fun amb_1/3, [0], State0, + Blocks0), + {amb_insert_promotions(Blocks, State), State#amb.cnt}; +alias_matched_binaries(Blocks, Counter, _AliasMap) -> + {Blocks, Counter}. + +amb_1(Lbl, #b_blk{is=Is0,last=Last0}=Block, State0) -> + {Is, State1} = mapfoldl(fun(I, State) -> + amb_assign_set(I, Lbl, State) + end, State0, Is0), + {Last, State} = amb_assign_last(Last0, Lbl, State1), + {Block#b_blk{is=Is,last=Last}, State}. + +amb_assign_set(#b_set{op=phi,args=Args0}=I, _Lbl, State0) -> + %% Phi node aliases are relative to their source block, not their + %% containing block. + {Args, State} = + mapfoldl(fun({Arg0, Lbl}, Acc) -> + {Arg, State} = amb_get_alias(Arg0, Lbl, Acc), + {{Arg, Lbl}, State} + end, State0, Args0), + {I#b_set{args=Args}, State}; +amb_assign_set(#b_set{args=Args0}=I, Lbl, State0) -> + {Args, State} = mapfoldl(fun(Arg0, Acc) -> + amb_get_alias(Arg0, Lbl, Acc) + end, State0, Args0), + {I#b_set{args=Args}, State}. + +amb_assign_last(#b_ret{arg=Arg0}=T, Lbl, State0) -> + {Arg, State} = amb_get_alias(Arg0, Lbl, State0), + {T#b_ret{arg=Arg}, State}; +amb_assign_last(#b_switch{arg=Arg0}=T, Lbl, State0) -> + {Arg, State} = amb_get_alias(Arg0, Lbl, State0), + {T#b_switch{arg=Arg}, State}; +amb_assign_last(#b_br{bool=Arg0}=T, Lbl, State0) -> + {Arg, State} = amb_get_alias(Arg0, Lbl, State0), + {T#b_br{bool=Arg}, State}. + +amb_get_alias(#b_var{}=Arg, Lbl, State) -> + case maps:find(Arg, State#amb.match_aliases) of + {ok, {AliasAfter, Context}} -> + %% Our context may not have been created yet, so we skip assigning + %% an alias unless the given block is among our dominators. + Dominators = maps:get(Lbl, State#amb.dominators), + case ordsets:is_element(AliasAfter, Dominators) of + true -> amb_create_alias(Arg, Context, Lbl, State); + false -> {Arg, State} + end; + error -> + {Arg, State} + end; +amb_get_alias(Arg, _Lbl, State) -> + {Arg, State}. + +amb_create_alias(#b_var{}=Arg0, Context, Lbl, State0) -> + Dominators = maps:get(Lbl, State0#amb.dominators), + Promotions0 = State0#amb.promotions, + + PrevPromotions = + [maps:get({Dom, Arg0}, Promotions0) + || Dom <- Dominators, is_map_key({Dom, Arg0}, Promotions0)], + + case PrevPromotions of + [_|_] -> + %% We've already created an alias prior to this block, so we'll + %% grab the most recent one to minimize stack use. + + #b_set{dst=Alias} = max(PrevPromotions), + {Alias, State0}; + [] -> + %% If we haven't created an alias we need to do so now. The + %% promotion will be inserted later by amb_insert_promotions/2. + + Counter = State0#amb.cnt, + Alias = #b_var{name={'@ssa_bsm_alias', Counter}}, + Promotion = #b_set{op=bs_get_tail,dst=Alias,args=[Context]}, + + Promotions = maps:put({Lbl, Arg0}, Promotion, Promotions0), + State = State0#amb{ promotions=Promotions, cnt=Counter+1 }, + + {Alias, State} + end. + +amb_insert_promotions(Blocks0, State) -> + F = fun({Lbl, #b_var{}}, Promotion, Blocks) -> + Block = maps:get(Lbl, Blocks), + + Alias = Promotion#b_set.dst, + {Before, After} = splitwith(fun(#b_set{args=Args}) -> + not member(Alias, Args) + end, Block#b_blk.is), + Is = Before ++ [Promotion | After], + + maps:put(Lbl, Block#b_blk{is=Is}, Blocks) + end, + maps:fold(F, Blocks0, State#amb.promotions). + +%%% +%%% Subpasses +%%% + +%% Removes superflous chained bs_start_match instructions in the same +%% function. When matching on an extracted tail binary, or on a binary we've +%% already matched on, we reuse the original match context. +%% +%% This pass runs first since it makes subsequent optimizations more effective +%% by removing spots where promotion would be required. + +-type prior_match_map() :: + #{ Binary :: #b_var{} => + [{ %% The context and success label of a previous + %% bs_start_match made on this binary. + ValidAfter :: beam_ssa:label(), + Context :: #b_var{} }] }. + +-record(cm, { definitions :: beam_ssa:definition_map(), + dominators :: beam_ssa:dominator_map(), + blocks :: beam_ssa:block_map(), + match_aliases = #{} :: match_alias_map(), + prior_matches = #{} :: prior_match_map(), + renames = #{} :: beam_ssa:rename_map() }). + +combine_matches({Fs0, ModInfo}) -> + Fs = map(fun(F) -> combine_matches(F, ModInfo) end, Fs0), + {Fs, ModInfo}. + +combine_matches(#b_function{bs=Blocks0,cnt=Counter0}=F, ModInfo) -> + case funcinfo_get(F, has_bsm_ops, ModInfo) of + true -> + {Blocks1, State} = + beam_ssa:mapfold_blocks_rpo( + fun(Lbl, #b_blk{is=Is0}=Block0, State0) -> + {Is, State} = cm_1(Is0, [], Lbl, State0), + {Block0#b_blk{is=Is}, State} + end, [0], + #cm{ definitions = beam_ssa:definitions(Blocks0), + dominators = beam_ssa:dominators(Blocks0), + blocks = Blocks0 }, + Blocks0), + + Blocks2 = beam_ssa:rename_vars(State#cm.renames, [0], Blocks1), + + {Blocks, Counter} = alias_matched_binaries(Blocks2, Counter0, + State#cm.match_aliases), + + F#b_function{ bs=Blocks, cnt=Counter }; + false -> + F + end. + +cm_1([#b_set{ op=bs_start_match, + dst=Ctx, + args=[Src] }, + #b_set{ op=succeeded, + dst=Bool, + args=[Ctx] }]=MatchSeq, Acc0, Lbl, State0) -> + Acc = reverse(Acc0), + case is_tail_binary(Src, State0#cm.definitions) of + true -> cm_combine_tail(Src, Ctx, Bool, Acc, State0); + false -> cm_handle_priors(Src, Ctx, Bool, Acc, MatchSeq, Lbl, State0) + end; +cm_1([I | Is], Acc, Lbl, State) -> + cm_1(Is, [I | Acc], Lbl, State); +cm_1([], Acc, _Lbl, State) -> + {reverse(Acc), State}. + +%% If we're dominated by at least one match on the same source, we can reuse +%% the context created by that match. +cm_handle_priors(Src, DstCtx, Bool, Acc, MatchSeq, Lbl, State0) -> + PriorCtxs = case maps:find(Src, State0#cm.prior_matches) of + {ok, Priors} -> + %% We've seen other match contexts on this source, but + %% we can only consider the ones whose success path + %% dominate us. + Dominators = maps:get(Lbl, State0#cm.dominators, []), + [Ctx || {ValidAfter, Ctx} <- Priors, + ordsets:is_element(ValidAfter, Dominators)]; + error -> + [] + end, + case PriorCtxs of + [Ctx|_] -> + Renames0 = State0#cm.renames, + Renames = Renames0#{ Bool => #b_literal{val=true}, DstCtx => Ctx }, + {Acc, State0#cm{ renames = Renames }}; + [] -> + %% Since we lack a prior match, we need to register this one in + %% case we dominate another. + State = cm_register_prior(Src, DstCtx, Lbl, State0), + {Acc ++ MatchSeq, State} + end. + +cm_register_prior(Src, DstCtx, Lbl, State) -> + Block = maps:get(Lbl, State#cm.blocks), + #b_br{succ=ValidAfter} = Block#b_blk.last, + + Priors0 = maps:get(Src, State#cm.prior_matches, []), + Priors = [{ValidAfter, DstCtx} | Priors0], + + PriorMatches = maps:put(Src, Priors, State#cm.prior_matches), + State#cm{ prior_matches = PriorMatches }. + +cm_combine_tail(Src, DstCtx, Bool, Acc, State0) -> + SrcCtx = match_context_of(Src, State0#cm.definitions), + + %% We replace the source with a context alias as it normally won't be used + %% on the happy path after being matched, and the added cost of conversion + %% is negligible if it is. + Aliases = maps:put(Src, {0, SrcCtx}, State0#cm.match_aliases), + + Renames0 = State0#cm.renames, + Renames = Renames0#{ Bool => #b_literal{val=true}, DstCtx => SrcCtx }, + + State = State0#cm{ match_aliases = Aliases, renames = Renames }, + + {Acc, State}. + +%% Lets functions accept match contexts as arguments. The parameter must be +%% unused before the bs_start_match instruction, and it must be matched in the +%% first block. + +-record(aca, { unused_parameters :: ordsets:ordset(#b_var{}), + counter :: non_neg_integer(), + parameter_info = #{} :: #{ #b_var{} => param_info() }, + match_aliases = #{} :: match_alias_map() }). + +accept_context_args({Fs, ModInfo}) -> + mapfoldl(fun accept_context_args/2, ModInfo, Fs). + +accept_context_args(#b_function{bs=Blocks0}=F, ModInfo0) -> + case funcinfo_get(F, has_bsm_ops, ModInfo0) of + true -> + Parameters = ordsets:from_list(funcinfo_get(F, parameters, ModInfo0)), + State0 = #aca{ unused_parameters = Parameters, + counter = F#b_function.cnt }, + + {Blocks1, State} = aca_1(Blocks0, State0), + {Blocks, Counter} = alias_matched_binaries(Blocks1, + State#aca.counter, + State#aca.match_aliases), + + ModInfo = funcinfo_set(F, parameter_info, State#aca.parameter_info, + ModInfo0), + + {F#b_function{bs=Blocks,cnt=Counter}, ModInfo}; + false -> + {F, ModInfo0} + end. + +aca_1(Blocks, State) -> + %% We only handle block 0 as we don't yet support starting a match after a + %% test. This is generally good enough as the sys_core_bsm pass makes the + %% match instruction come first if possible, and it's rare for a function + %% to binary-match several parameters at once. + EntryBlock = maps:get(0, Blocks), + aca_enable_reuse(EntryBlock#b_blk.is, EntryBlock, Blocks, [], State). + +aca_enable_reuse([#b_set{op=bs_start_match,args=[Src]}=I0 | Rest], + EntryBlock, Blocks0, Acc, State0) -> + case aca_is_reuse_safe(Src, State0) of + true -> + {I, Last, Blocks1, State} = + aca_reuse_context(I0, EntryBlock, Blocks0, State0), + + Is = reverse([I|Acc]) ++ Rest, + Blocks = maps:put(0, EntryBlock#b_blk{is=Is,last=Last}, Blocks1), + + {Blocks, State}; + false -> + {Blocks0, State0} + end; +aca_enable_reuse([I | Is], EntryBlock, Blocks, Acc, State0) -> + UnusedParams0 = State0#aca.unused_parameters, + case ordsets:intersection(UnusedParams0, beam_ssa:used(I)) of + [] -> + aca_enable_reuse(Is, EntryBlock, Blocks, [I | Acc], State0); + PrematureUses -> + UnusedParams = ordsets:subtract(UnusedParams0, PrematureUses), + + %% Mark the offending parameters as unsuitable for context reuse. + ParamInfo = foldl(fun(A, Ps) -> + maps:put(A, {used_before_match, I}, Ps) + end, State0#aca.parameter_info, PrematureUses), + + State = State0#aca{ unused_parameters = UnusedParams, + parameter_info = ParamInfo }, + aca_enable_reuse(Is, EntryBlock, Blocks, [I | Acc], State) + end; +aca_enable_reuse([], _EntryBlock, Blocks, _Acc, State) -> + {Blocks, State}. + +aca_is_reuse_safe(Src, State) -> + %% Context reuse is unsafe unless all uses are dominated by the start_match + %% instruction. Since we only process block 0 it's enough to check if + %% they're unused so far. + ordsets:is_element(Src, State#aca.unused_parameters). + +aca_reuse_context(#b_set{dst=Dst, args=[Src]}=I0, Block, Blocks0, State0) -> + %% When matching fails on a reused context it needs to be converted back + %% to a binary. We only need to do this on the success path since it can't + %% be a context on the type failure path, but it's very common for these + %% to converge which requires special handling. + {State1, Last, Blocks} = + aca_handle_convergence(Src, State0, Block#b_blk.last, Blocks0), + + Aliases = maps:put(Src, {Last#b_br.succ, Dst}, State1#aca.match_aliases), + ParamInfo = maps:put(Src, suitable_for_reuse, State1#aca.parameter_info), + + State = State1#aca{ match_aliases = Aliases, + parameter_info = ParamInfo }, + + I = beam_ssa:add_anno(accepts_match_contexts, true, I0), + + {I, Last, Blocks, State}. + +aca_handle_convergence(Src, State0, Last0, Blocks0) -> + #b_br{fail=Fail0,succ=Succ0} = Last0, + + SuccPath = beam_ssa:rpo([Succ0], Blocks0), + FailPath = beam_ssa:rpo([Fail0], Blocks0), + + %% The promotion logic in alias_matched_binaries breaks down if the source + %% is used after the fail/success paths converge, as we have no way to tell + %% whether the source is a match context or something else past that point. + %% + %% We could handle this through clever insertion of phi nodes but it's + %% far simpler to copy either branch in its entirety. It doesn't matter + %% which one as long as they become disjoint. + ConvergedPaths = ordsets:intersection( + ordsets:from_list(SuccPath), + ordsets:from_list(FailPath)), + + case maps:is_key(Src, beam_ssa:uses(ConvergedPaths, Blocks0)) of + true -> + case shortest(SuccPath, FailPath) of + left -> + {Succ, Blocks, Counter} = + aca_copy_successors(Succ0, Blocks0, State0#aca.counter), + State = State0#aca{ counter = Counter }, + {State, Last0#b_br{succ=Succ}, Blocks}; + right -> + {Fail, Blocks, Counter} = + aca_copy_successors(Fail0, Blocks0, State0#aca.counter), + State = State0#aca{ counter = Counter }, + {State, Last0#b_br{fail=Fail}, Blocks} + end; + false -> + {State0, Last0, Blocks0} + end. + +shortest([_|As], [_|Bs]) -> shortest(As, Bs); +shortest([], _) -> left; +shortest(_, []) -> right. + +%% Copies all successor blocks of Lbl, returning the label to the entry block +%% of this copy. Since the copied blocks aren't referenced anywhere else, they +%% are all guaranteed to be dominated by Lbl. +aca_copy_successors(Lbl0, Blocks0, Counter0) -> + %% Building the block rename map up front greatly simplifies phi node + %% handling. + Path = beam_ssa:rpo([Lbl0], Blocks0), + {BRs, Counter1} = aca_cs_build_brs(Path, Counter0, #{}), + {Blocks, Counter} = aca_cs_1(Path, Blocks0, Counter1, #{}, BRs, #{}), + Lbl = maps:get(Lbl0, BRs), + {Lbl, Blocks, Counter}. + +aca_cs_build_brs([Lbl | Path], Counter0, Acc) -> + aca_cs_build_brs(Path, Counter0 + 1, maps:put(Lbl, Counter0, Acc)); +aca_cs_build_brs([], Counter, Acc) -> + {Acc, Counter}. + +aca_cs_1([Lbl0 | Path], Blocks, Counter0, VRs0, BRs, Acc0) -> + Block0 = maps:get(Lbl0, Blocks), + Lbl = maps:get(Lbl0, BRs), + {VRs, Block, Counter} = aca_cs_block(Block0, Counter0, VRs0, BRs), + Acc = maps:put(Lbl, Block, Acc0), + aca_cs_1(Path, Blocks, Counter, VRs, BRs, Acc); +aca_cs_1([], Blocks, Counter, _VRs, _BRs, Acc) -> + {maps:merge(Blocks, Acc), Counter}. + +aca_cs_block(#b_blk{is=Is0,last=Last0}=Block0, Counter0, VRs0, BRs) -> + {VRs, Is, Counter} = aca_cs_is(Is0, Counter0, VRs0, BRs, []), + Last = aca_cs_last(Last0, VRs, BRs), + Block = Block0#b_blk{is=Is,last=Last}, + {VRs, Block, Counter}. + +aca_cs_is([#b_set{op=Op, + dst=Dst0, + args=Args0}=I0 | Is], + Counter0, VRs0, BRs, Acc) -> + Args = case Op of + phi -> aca_cs_args_phi(Args0, VRs0, BRs); + _ -> aca_cs_args(Args0, VRs0) + end, + Counter = Counter0 + 1, + Dst = #b_var{name={'@ssa_bsm_aca',Counter}}, + I = I0#b_set{dst=Dst,args=Args}, + VRs = maps:put(Dst0, Dst, VRs0), + aca_cs_is(Is, Counter, VRs, BRs, [I | Acc]); +aca_cs_is([], Counter, VRs, _BRs, Acc) -> + {VRs, reverse(Acc), Counter}. + +aca_cs_last(#b_switch{arg=Arg0,list=Switch0,fail=Fail0}=Sw, VRs, BRs) -> + Switch = [{Literal, maps:get(Lbl, BRs)} || {Literal, Lbl} <- Switch0], + Sw#b_switch{arg=aca_cs_arg(Arg0, VRs), + fail=maps:get(Fail0, BRs), + list=Switch}; +aca_cs_last(#b_br{bool=Arg0,succ=Succ0,fail=Fail0}=Br, VRs, BRs) -> + Br#b_br{bool=aca_cs_arg(Arg0, VRs), + succ=maps:get(Succ0, BRs), + fail=maps:get(Fail0, BRs)}; +aca_cs_last(#b_ret{arg=Arg0}=Ret, VRs, _BRs) -> + Ret#b_ret{arg=aca_cs_arg(Arg0, VRs)}. + +aca_cs_args_phi([{Arg, Lbl} | Args], VRs, BRs) -> + case BRs of + #{ Lbl := New } -> + [{aca_cs_arg(Arg, VRs), New} | aca_cs_args_phi(Args, VRs, BRs)]; + #{} -> + aca_cs_args_phi(Args, VRs, BRs) + end; +aca_cs_args_phi([], _VRs, _BRs) -> + []. + +aca_cs_args([Arg | Args], VRs) -> + [aca_cs_arg(Arg, VRs) | aca_cs_args(Args, VRs)]; +aca_cs_args([], _VRs) -> + []. + +aca_cs_arg(Arg, VRs) -> + case VRs of + #{ Arg := New } -> New; + #{} -> Arg + end. + +%% Allows contexts to pass through "wrapper functions" where the context is +%% passed directly to a function that accepts match contexts (including other +%% wrappers). +%% +%% This does not alter the function in any way, it only changes parameter info +%% so that skip_outgoing_tail_extraction is aware that it's safe to pass +%% contexts to us. + +allow_context_passthrough({Fs, ModInfo0}) -> + ModInfo = + acp_forward_params([{F, beam_ssa:uses(F#b_function.bs)} || F <- Fs], + ModInfo0), + {Fs, ModInfo}. + +acp_forward_params(FsUses, ModInfo0) -> + F = fun({#b_function{args=Parameters}=Func, UseMap}, ModInfo) -> + ParamInfo = + foldl(fun(Param, ParamInfo) -> + Uses = maps:get(Param, UseMap, []), + acp_1(Param, Uses, ModInfo, ParamInfo) + end, + funcinfo_get(Func, parameter_info, ModInfo), + Parameters), + funcinfo_set(Func, parameter_info, ParamInfo, ModInfo) + end, + %% Allowing context passthrough on one function may make it possible to + %% enable it on another, so it needs to be repeated for maximum effect. + case foldl(F, ModInfo0, FsUses) of + ModInfo0 -> ModInfo0; + Changed -> acp_forward_params(FsUses, Changed) + end. + +%% We have no way to know if an argument is a context, so it's only safe to +%% forward them if they're passed exactly once in the first block. Any other +%% uses are unsafe, including function_clause errors. +acp_1(Param, [{0, #b_set{op=call}=I}], ModInfo, ParamInfo) -> + %% We don't need to provide a context chain as our callers make sure that + %% multiple arguments never reference the same context. + case check_context_call(I, Param, [], ModInfo) of + {no_match_on_entry, _} -> ParamInfo; + Other -> maps:put(Param, Other, ParamInfo) + end; +acp_1(_Param, _Uses, _ModInfo, ParamInfo) -> + ParamInfo. + +%% This is conceptually similar to combine_matches but operates across +%% functions. Whenever a tail binary is passed to a parameter that accepts +%% match contexts we'll pass the context instead, improving performance by +%% avoiding the creation of a new match context in the callee. +%% +%% We also create an alias to delay extraction until it's needed as an actual +%% binary, which is often rare on the happy path. The cost of being wrong is +%% negligible (`bs_test_unit + bs_get_tail` vs `bs_get_binary`) so we're +%% applying it unconditionally to keep things simple. + +-record(sote, { definitions :: beam_ssa:definition_map(), + mod_info :: module_info(), + match_aliases = #{} :: match_alias_map() }). + +skip_outgoing_tail_extraction({Fs0, ModInfo}) -> + Fs = map(fun(F) -> skip_outgoing_tail_extraction(F, ModInfo) end, Fs0), + {Fs, ModInfo}. + +skip_outgoing_tail_extraction(#b_function{bs=Blocks0}=F, ModInfo) -> + case funcinfo_get(F, has_bsm_ops, ModInfo) of + true -> + State0 = #sote{ definitions = beam_ssa:definitions(Blocks0), + mod_info = ModInfo }, + + {Blocks1, State} = beam_ssa:mapfold_instrs_rpo( + fun sote_rewrite_calls/2, [0], State0, Blocks0), + + {Blocks, Counter} = alias_matched_binaries(Blocks1, + F#b_function.cnt, + State#sote.match_aliases), + + F#b_function{bs=Blocks,cnt=Counter}; + false -> + F + end. + +sote_rewrite_calls(#b_set{op=call,args=Args}=Call, State) -> + sote_rewrite_call(Call, Args, [], State); +sote_rewrite_calls(I, State) -> + {I, State}. + +sote_rewrite_call(Call, [], ArgsOut, State) -> + {Call#b_set{args=reverse(ArgsOut)}, State}; +sote_rewrite_call(Call0, [Arg | ArgsIn], ArgsOut, State0) -> + case is_tail_binary(Arg, State0#sote.definitions) of + true -> + CtxChain = context_chain_of(Arg, State0#sote.definitions), + case check_context_call(Call0, Arg, CtxChain, State0#sote.mod_info) of + suitable_for_reuse -> + Ctx = match_context_of(Arg, State0#sote.definitions), + + MatchAliases0 = State0#sote.match_aliases, + MatchAliases = maps:put(Arg, {0, Ctx}, MatchAliases0), + State = State0#sote{ match_aliases = MatchAliases }, + + Call = beam_ssa:add_anno(bsm_info, context_reused, Call0), + sote_rewrite_call(Call, ArgsIn, [Ctx | ArgsOut], State); + Other -> + Call = beam_ssa:add_anno(bsm_info, Other, Call0), + sote_rewrite_call(Call, ArgsIn, [Arg | ArgsOut], State0) + end; + false -> + sote_rewrite_call(Call0, ArgsIn, [Arg | ArgsOut], State0) + end. + +%% Adds parameter_type_info annotations to help the validator determine whether +%% our optimizations were safe. + +annotate_context_parameters({Fs, ModInfo}) -> + mapfoldl(fun annotate_context_parameters/2, ModInfo, Fs). + +annotate_context_parameters(F, ModInfo) -> + ParamInfo = funcinfo_get(F, parameter_info, ModInfo), + TypeAnno0 = beam_ssa:get_anno(parameter_type_info, F, #{}), + TypeAnno = maps:fold(fun(K, _V, Acc) when is_map_key(K, Acc) -> + %% Assertion. + error(conflicting_parameter_types); + (K, suitable_for_reuse, Acc) -> + Acc#{ K => match_context }; + (_K, _V, Acc) -> + Acc + end, TypeAnno0, ParamInfo), + {beam_ssa:add_anno(parameter_type_info, TypeAnno, F), ModInfo}. + +%%% +%%% +bin_opt_info +%%% + +collect_opt_info(Fs) -> + foldl(fun(#b_function{bs=Blocks}=F, Acc0) -> + UseMap = beam_ssa:uses(Blocks), + Where = beam_ssa:get_anno(location, F, []), + beam_ssa:fold_instrs_rpo( + fun(I, Acc) -> + collect_opt_info_1(I, Where, UseMap, Acc) + end, [0], Acc0, Blocks) + end, [], Fs). + +collect_opt_info_1(#b_set{op=Op,anno=Anno,dst=Dst}=I, Where, UseMap, Acc0) -> + case is_tail_binary(I) of + true when Op =:= bs_match -> + %% The uses include when the context is passed raw, so we discard + %% everything but the bs_extract instruction to limit warnings to + %% unoptimized uses. + Uses0 = maps:get(Dst, UseMap, []), + case [E || {_, #b_set{op=bs_extract}=E} <- Uses0] of + [Use] -> add_unopt_binary_info(Use, false, Where, UseMap, Acc0); + [] -> Acc0 + end; + true -> + %% Add a warning for each use. Note that we don't do anything + %% special if unused as a later pass will remove this instruction + %% anyway. + Uses = maps:get(Dst, UseMap, []), + foldl(fun({_Lbl, Use}, Acc) -> + add_unopt_binary_info(Use, false, Where, UseMap, Acc) + end, Acc0, Uses); + false -> + add_opt_info(Anno, Where, Acc0) + end; +collect_opt_info_1(#b_ret{anno=Anno}, Where, _UseMap, Acc) -> + add_opt_info(Anno, Where, Acc); +collect_opt_info_1(_I, _Where, _Uses, Acc) -> + Acc. + +add_opt_info(Anno, Where, Acc) -> + case maps:find(bsm_info, Anno) of + {ok, Term} -> [make_warning(Term, Anno, Where) | Acc]; + error -> Acc + end. + +%% When an alias is promoted we need to figure out where it goes to ignore +%% warnings for compiler-generated things, and provide more useful warnings in +%% general. +%% +%% We track whether the binary has been used to build another term because it +%% can be helpful when there's no line information. + +add_unopt_binary_info(#b_set{op=Follow,dst=Dst}, _Nested, Where, UseMap, Acc0) + when Follow =:= put_tuple; + Follow =:= put_list; + Follow =:= put_map -> + %% Term-building instructions. + {_, Uses} = unzip(maps:get(Dst, UseMap, [])), + foldl(fun(Use, Acc) -> + add_unopt_binary_info(Use, true, Where, UseMap, Acc) + end, Acc0, Uses); +add_unopt_binary_info(#b_set{op=Follow,dst=Dst}, Nested, Where, UseMap, Acc0) + when Follow =:= bs_extract; + Follow =:= phi -> + %% Non-building instructions that need to be followed. + {_, Uses} = unzip(maps:get(Dst, UseMap, [])), + foldl(fun(Use, Acc) -> + add_unopt_binary_info(Use, Nested, Where, UseMap, Acc) + end, Acc0, Uses); +add_unopt_binary_info(#b_set{op=call, + args=[#b_remote{mod=#b_literal{val=erlang}, + name=#b_literal{val=error}} | + _Ignored]}, + _Nested, _Where, _UseMap, Acc) -> + %% There's no nice way to tell compiler-generated exceptions apart from + %% user ones so we ignore them all. I doubt anyone cares. + Acc; +add_unopt_binary_info(#b_switch{anno=Anno}=I, Nested, Where, _UseMap, Acc) -> + [make_promotion_warning(I, Nested, Anno, Where) | Acc]; +add_unopt_binary_info(#b_set{anno=Anno}=I, Nested, Where, _UseMap, Acc) -> + [make_promotion_warning(I, Nested, Anno, Where) | Acc]; +add_unopt_binary_info(#b_ret{anno=Anno}=I, Nested, Where, _UseMap, Acc) -> + [make_promotion_warning(I, Nested, Anno, Where) | Acc]; +add_unopt_binary_info(#b_br{anno=Anno}=I, Nested, Where, _UseMap, Acc) -> + [make_promotion_warning(I, Nested, Anno, Where) | Acc]. + +make_promotion_warning(I, Nested, Anno, Where) -> + make_warning({binary_created, I, Nested}, Anno, Where). + +make_warning(Term, Anno, Where) -> + {File, Line} = maps:get(location, Anno, Where), + {File,[{Line,?MODULE,Term}]}. + +format_opt_info(context_reused) -> + "OPTIMIZED: match context reused"; +format_opt_info({binary_created, _, _}=Promotion) -> + io_lib:format("BINARY CREATED: ~s", [format_opt_info_1(Promotion)]); +format_opt_info(Other) -> + io_lib:format("NOT OPTIMIZED: ~s", [format_opt_info_1(Other)]). + +format_opt_info_1({binary_created, #b_set{op=call,args=[Call|_]}, false}) -> + io_lib:format("binary is used in call to ~s which doesn't support " + "context reuse", [format_call(Call)]); +format_opt_info_1({binary_created, #b_set{op=call,args=[Call|_]}, true}) -> + io_lib:format("binary is used in term passed to ~s", + [format_call(Call)]); +format_opt_info_1({binary_created, #b_set{op={bif, BIF},args=Args}, false}) -> + io_lib:format("binary is used in ~p/~p which doesn't support context " + "reuse", [BIF, length(Args)]); +format_opt_info_1({binary_created, #b_set{op={bif, BIF},args=Args}, true}) -> + io_lib:format("binary is used in term passed to ~p/~p", + [BIF, length(Args)]); +format_opt_info_1({binary_created, #b_set{op=Op}, false}) -> + io_lib:format("binary is used in '~p' which doesn't support context " + "reuse", [Op]); +format_opt_info_1({binary_created, #b_set{op=Op}, true}) -> + io_lib:format("binary is used in term passed to '~p'", [Op]); +format_opt_info_1({binary_created, #b_ret{}, false}) -> + io_lib:format("binary is returned from the function", []); +format_opt_info_1({binary_created, #b_ret{}, true}) -> + io_lib:format("binary is used in a term that is returned from the " + "function", []); +format_opt_info_1({unsuitable_call, {Call, Inner}}) -> + io_lib:format("binary used in call to ~s, where ~s", + [format_call(Call), format_opt_info_1(Inner)]); +format_opt_info_1({remote_call, Call}) -> + io_lib:format("binary is used in remote call to ~s", [format_call(Call)]); +format_opt_info_1({fun_call, Call}) -> + io_lib:format("binary is used in fun call (~s)", + [format_call(Call)]); +format_opt_info_1({multiple_uses_in_call, Call}) -> + io_lib:format("binary is passed as multiple arguments to ~s", + [format_call(Call)]); +format_opt_info_1({no_match_on_entry, Call}) -> + io_lib:format("binary is used in call to ~s which does not begin with a " + "suitable binary match", [format_call(Call)]); +format_opt_info_1({used_before_match, #b_set{op=call,args=[Call|_]}}) -> + io_lib:format("binary is used in call to ~s before being matched", + [format_call(Call)]); +format_opt_info_1({used_before_match, #b_set{op={bif, BIF},args=Args}}) -> + io_lib:format("binary is used in ~p/~p before being matched", + [BIF, length(Args)]); +format_opt_info_1({used_before_match, #b_set{op=phi}}) -> + io_lib:format("binary is returned from an expression before being " + "matched", []); +format_opt_info_1({used_before_match, #b_set{op=Op}}) -> + io_lib:format("binary is used in '~p' before being matched",[Op]); +format_opt_info_1(Term) -> + io_lib:format("~w", [Term]). + +format_call(#b_local{name=#b_literal{val=F},arity=A}) -> + io_lib:format("~p/~p", [F, A]); +format_call(#b_remote{mod=#b_literal{val=M},name=#b_literal{val=F},arity=A}) -> + io_lib:format("~p:~p/~p", [M, F, A]); +format_call(Fun) -> + io_lib:format("~p", [Fun]). diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl index 5085c950b5..1c7563faa0 100644 --- a/lib/compiler/src/beam_ssa_codegen.erl +++ b/lib/compiler/src/beam_ssa_codegen.erl @@ -108,7 +108,8 @@ module(#b_module{name=Mod,exports=Es,attributes=Attrs,body=Fs}, _Opts) -> -type ssa_register() :: xreg() | yreg() | {'fr',reg_num()} | {'z',reg_num()}. functions(Forms, AtomMod) -> - mapfoldl(fun (F, St) -> function(F, AtomMod, St) end, #cg{lcount=1}, Forms). + mapfoldl(fun (F, St) -> function(F, AtomMod, St) end, + #cg{lcount=1}, Forms). function(#b_function{anno=Anno,bs=Blocks}, AtomMod, St0) -> #{func_info:={_,Name,Arity}} = Anno, @@ -125,8 +126,9 @@ function(#b_function{anno=Anno,bs=Blocks}, AtomMod, St0) -> ultimate_fail=Ult}, {Body,St} = cg_fun(Blocks, St5), Asm = [{label,Fi},line(Anno), - {func_info,AtomMod,{atom,Name},Arity}] ++ Body ++ - [{label,Ult},if_end], + {func_info,AtomMod,{atom,Name},Arity}] ++ + add_parameter_annos(Body, Anno) ++ + [{label,Ult},if_end], Func = {function,Name,Arity,Entry,Asm}, {Func,St} catch @@ -150,6 +152,17 @@ assert_badarg_block(Blocks) -> ok end. +add_parameter_annos([{label, _}=Entry | Body], Anno) -> + ParamInfo = maps:get(parameter_type_info, Anno, #{}), + Annos = maps:fold( + fun(K, V, Acc) when is_map_key(K, ParamInfo) -> + TypeInfo = maps:get(K, ParamInfo), + [{'%', {type_info, V, TypeInfo}} | Acc]; + (_K, _V, Acc) -> + Acc + end, [], maps:get(registers, Anno)), + [Entry | Annos] ++ Body. + cg_fun(Blocks, St0) -> Linear0 = linearize(Blocks), St = collect_catch_labels(Linear0, St0), @@ -315,12 +328,15 @@ classify_heap_need(Name, _Args) -> classify_heap_need(bs_add) -> gc; classify_heap_need(bs_get) -> gc; +classify_heap_need(bs_get_tail) -> gc; classify_heap_need(bs_init) -> gc; classify_heap_need(bs_init_writable) -> gc; classify_heap_need(bs_match_string) -> gc; classify_heap_need(bs_put) -> neutral; classify_heap_need(bs_restore) -> neutral; classify_heap_need(bs_save) -> neutral; +classify_heap_need(bs_get_position) -> gc; +classify_heap_need(bs_set_position) -> neutral; classify_heap_need(bs_skip) -> gc; classify_heap_need(bs_start_match) -> neutral; classify_heap_need(bs_test_tail) -> neutral; @@ -329,7 +345,6 @@ classify_heap_need(bs_utf8_size) -> neutral; classify_heap_need(build_stacktrace) -> gc; classify_heap_need(call) -> gc; classify_heap_need(catch_end) -> gc; -classify_heap_need(context_to_binary) -> gc; classify_heap_need(copy) -> neutral; classify_heap_need(extract) -> gc; classify_heap_need(get_hd) -> neutral; @@ -695,6 +710,8 @@ need_live_anno(Op) -> {bif,_} -> true; bs_get -> true; bs_init -> true; + bs_get_position -> true; + bs_get_tail -> true; bs_start_match -> true; bs_skip -> true; call -> true; @@ -794,6 +811,8 @@ def_successors([], _, DefMap) -> DefMap. need_y_init(#cg_set{anno=#{clobbers:=Clobbers}}) -> Clobbers; need_y_init(#cg_set{op=bs_get}) -> true; +need_y_init(#cg_set{op=bs_get_position}) -> true; +need_y_init(#cg_set{op=bs_get_tail}) -> true; need_y_init(#cg_set{op=bs_init}) -> true; need_y_init(#cg_set{op=bs_skip,args=[#b_literal{val=Type}|_]}) -> case Type of @@ -1042,12 +1061,18 @@ cg_block([#cg_set{op=bs_init,dst=Dst0,args=Args0,anno=Anno}=I, end; cg_block([#cg_set{anno=Anno,op=bs_start_match,dst=Ctx0,args=[Bin0]}=I, #cg_set{op=succeeded,dst=Bool}], {Bool,Fail}, St) -> - #{num_slots:=Slots} = Anno, [Dst,Bin1] = beam_args([Ctx0,Bin0], St), {Bin,Pre} = force_reg(Bin1, Dst), Live = get_live(I), - Is = Pre ++ [{test,bs_start_match2,Fail,Live,[Bin,Slots],Dst}], - {Is,St}; + %% num_slots is only set when using the old instructions. + case maps:find(num_slots, Anno) of + {ok, Slots} -> + Is = Pre ++ [{test,bs_start_match2,Fail,Live,[Bin,Slots],Dst}], + {Is,St}; + error -> + Is = Pre ++ [{test,bs_start_match3,Fail,Live,[Bin],Dst}], + {Is,St} + end; cg_block([#cg_set{op=bs_get}=Set, #cg_set{op=succeeded,dst=Bool}], {Bool,Fail}, St) -> {cg_bs_get(Fail, Set, St),St}; @@ -1344,6 +1369,12 @@ build_apply(Arity, none, Dst) -> cg_instr(put_map, [{atom,assoc},SrcMap|Ss], Dst, Set) -> Live = get_live(Set), [{put_map_assoc,{f,0},SrcMap,Dst,Live,{list,Ss}}]; +cg_instr(bs_get_tail, [Src], Dst, Set) -> + Live = get_live(Set), + [{bs_get_tail,Src,Dst,Live}]; +cg_instr(bs_get_position, [Ctx], Dst, Set) -> + Live = get_live(Set), + [{bs_get_position,Ctx,Dst,Live}]; cg_instr(Op, Args, Dst, _Set) -> cg_instr(Op, Args, Dst). @@ -1359,10 +1390,10 @@ cg_instr(bs_restore, [Ctx,Slot], _Dst) -> cg_instr(bs_save, [Ctx,Slot], _Dst) -> {integer,N} = Slot, [{bs_save2,Ctx,N}]; +cg_instr(bs_set_position, [Ctx,Pos], _Dst) -> + [{bs_set_position,Ctx,Pos}]; cg_instr(build_stacktrace, Args, Dst) -> setup_args(Args) ++ [build_stacktrace|copy({x,0}, Dst)]; -cg_instr(context_to_binary, [Src], _Dst) -> - [{bs_context_to_binary,Src}]; cg_instr(set_tuple_element=Op, [New,Tuple,{integer,Index}], _Dst) -> [{Op,New,Tuple,Index}]; cg_instr({float,clearerror}, [], _Dst) -> diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 89cfbd7a84..ac2d943fef 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -66,13 +66,15 @@ passes(Opts0) -> ?PASS(ssa_opt_live), %Second time. ?PASS(ssa_opt_bsm), + ?PASS(ssa_opt_bsm_units), ?PASS(ssa_opt_bsm_shortcut), ?PASS(ssa_opt_misc), ?PASS(ssa_opt_tuple_size), ?PASS(ssa_opt_sw), ?PASS(ssa_opt_blockify), ?PASS(ssa_opt_sink), - ?PASS(ssa_opt_merge_blocks)], + ?PASS(ssa_opt_merge_blocks), + ?PASS(ssa_opt_trim_unreachable)], Negations = [{list_to_atom("no_"++atom_to_list(N)),N} || {N,_} <- Ps], Opts = proplists:substitute_negations(Negations, Opts0), @@ -112,6 +114,9 @@ ssa_opt_type(#st{ssa=Linear,args=Args}=St) -> ssa_opt_blockify(#st{ssa=Linear}=St) -> St#st{ssa=maps:from_list(Linear)}. +ssa_opt_trim_unreachable(#st{ssa=Blocks}=St) -> + St#st{ssa=beam_ssa:trim_unreachable(Blocks)}. + %%% %%% Split blocks before certain instructions to enable more optimizations. %%% @@ -1002,6 +1007,110 @@ bsm_shortcut([{L,#b_blk{is=Is,last=Last0}=Blk}|Bs], PosMap) -> bsm_shortcut([], _PosMap) -> []. %%% +%%% Eliminate redundant bs_test_unit2 instructions. +%%% + +ssa_opt_bsm_units(#st{ssa=Linear}=St) -> + St#st{ssa=bsm_units(Linear, #{})}. + +bsm_units([{L,#b_blk{last=#b_br{succ=Succ,fail=Fail}}=Block0} | Bs], UnitMaps0) -> + UnitsIn = maps:get(L, UnitMaps0, #{}), + {Block, UnitsOut} = bsm_units_skip(Block0, UnitsIn), + UnitMaps1 = bsm_units_join(Succ, UnitsOut, UnitMaps0), + UnitMaps = bsm_units_join(Fail, UnitsIn, UnitMaps1), + [{L, Block} | bsm_units(Bs, UnitMaps)]; +bsm_units([{L,#b_blk{last=#b_switch{fail=Fail,list=Switch}}=Block} | Bs], UnitMaps0) -> + UnitsIn = maps:get(L, UnitMaps0, #{}), + Labels = [Fail | [Lbl || {_Arg, Lbl} <- Switch]], + UnitMaps = foldl(fun(Lbl, UnitMaps) -> + bsm_units_join(Lbl, UnitsIn, UnitMaps) + end, UnitMaps0, Labels), + [{L, Block} | bsm_units(Bs, UnitMaps)]; +bsm_units([{L, Block} | Bs], UnitMaps) -> + [{L, Block} | bsm_units(Bs, UnitMaps)]; +bsm_units([], _UnitMaps) -> + []. + +bsm_units_skip(Block, Units) -> + bsm_units_skip_1(Block#b_blk.is, Block, Units). + +bsm_units_skip_1([#b_set{op=bs_start_match,dst=New}|_], Block, Units) -> + %% We bail early since there can't be more than one match per block. + {Block, Units#{ New => 1 }}; +bsm_units_skip_1([#b_set{op=bs_match, + dst=New, + args=[#b_literal{val=skip}, + Ctx, + #b_literal{val=binary}, + _Flags, + #b_literal{val=all}, + #b_literal{val=OpUnit}]}=Skip | Test], + Block0, Units) -> + [#b_set{op=succeeded,dst=Bool,args=[New]}] = Test, %Assertion. + #b_br{bool=Bool} = Last0 = Block0#b_blk.last, %Assertion. + CtxUnit = maps:get(Ctx, Units), + if + CtxUnit rem OpUnit =:= 0 -> + Is = takewhile(fun(I) -> I =/= Skip end, Block0#b_blk.is), + Last = Last0#b_br{bool=#b_literal{val=true}}, + Block = Block0#b_blk{is=Is,last=Last}, + {Block, Units#{ New => CtxUnit }}; + CtxUnit rem OpUnit =/= 0 -> + {Block0, Units#{ New => OpUnit, Ctx => OpUnit }} + end; +bsm_units_skip_1([#b_set{op=bs_match,dst=New,args=Args}|_], Block, Units) -> + [_,Ctx|_] = Args, + CtxUnit = maps:get(Ctx, Units), + OpUnit = bsm_op_unit(Args), + {Block, Units#{ New => gcd(OpUnit, CtxUnit) }}; +bsm_units_skip_1([_I | Is], Block, Units) -> + bsm_units_skip_1(Is, Block, Units); +bsm_units_skip_1([], Block, Units) -> + {Block, Units}. + +bsm_op_unit([_,_,_,Size,#b_literal{val=U}]) -> + case Size of + #b_literal{val=Sz} when is_integer(Sz) -> Sz*U; + _ -> U + end; +bsm_op_unit([#b_literal{val=string},_,#b_literal{val=String}]) -> + bit_size(String); +bsm_op_unit([#b_literal{val=utf8}|_]) -> + 8; +bsm_op_unit([#b_literal{val=utf16}|_]) -> + 16; +bsm_op_unit([#b_literal{val=utf32}|_]) -> + 32; +bsm_op_unit(_) -> + 1. + +%% Several paths can lead to the same match instruction and the inferred units +%% may differ between them, so we can only keep the information that is common +%% to all paths. +bsm_units_join(Lbl, MapA, UnitMaps0) when is_map_key(Lbl, UnitMaps0) -> + MapB = maps:get(Lbl, UnitMaps0), + Merged = if + map_size(MapB) =< map_size(MapA) -> + bsm_units_join_1(maps:keys(MapB), MapA, MapB); + map_size(MapB) > map_size(MapA) -> + bsm_units_join_1(maps:keys(MapA), MapB, MapA) + end, + maps:put(Lbl, Merged, UnitMaps0); +bsm_units_join(Lbl, MapA, UnitMaps0) when MapA =/= #{} -> + maps:put(Lbl, MapA, UnitMaps0); +bsm_units_join(_Lbl, _MapA, UnitMaps0) -> + UnitMaps0. + +bsm_units_join_1([Key | Keys], Left, Right) when is_map_key(Key, Left) -> + UnitA = maps:get(Key, Left), + UnitB = maps:get(Key, Right), + bsm_units_join_1(Keys, Left, maps:put(Key, gcd(UnitA, UnitB), Right)); +bsm_units_join_1([Key | Keys], Left, Right) -> + bsm_units_join_1(Keys, Left, maps:remove(Key, Right)); +bsm_units_join_1([], _MapA, Right) -> + Right. + +%%% %%% Miscellanous optimizations in execution order. %%% @@ -1618,6 +1727,12 @@ insert_def_is([], _V, Def) -> %%% Common utilities. %%% +gcd(A, B) -> + case A rem B of + 0 -> B; + X -> gcd(B, X) + end. + rel2fam(S0) -> S1 = sofs:relation(S0), S = sofs:rel2fam(S1), diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl index ca3b792ed6..36137ef046 100644 --- a/lib/compiler/src/beam_ssa_pre_codegen.erl +++ b/lib/compiler/src/beam_ssa_pre_codegen.erl @@ -78,15 +78,14 @@ {'ok',beam_ssa:b_module()}. module(#b_module{body=Fs0}=Module, Opts) -> - FixTuples = proplists:get_bool(no_put_tuple2, Opts), - ExtraAnnos = proplists:get_bool(dprecg, Opts), - Ps = passes(FixTuples, ExtraAnnos), - Fs = functions(Fs0, Ps), + UseBSM3 = not proplists:get_bool(no_bsm3, Opts), + Ps = passes(Opts), + Fs = functions(Fs0, Ps, UseBSM3), {ok,Module#b_module{body=Fs}}. -functions([F|Fs], Ps) -> - [function(F, Ps)|functions(Fs, Ps)]; -functions([], _Ps) -> []. +functions([F|Fs], Ps, UseBSM3) -> + [function(F, Ps, UseBSM3)|functions(Fs, Ps, UseBSM3)]; +functions([], _Ps, _UseBSM3) -> []. -type b_var() :: beam_ssa:b_var(). -type var_name() :: beam_ssa:var_name(). @@ -104,16 +103,18 @@ functions([], _Ps) -> []. -record(st, {ssa :: beam_ssa:block_map(), args :: [b_var()], cnt :: beam_ssa:label(), + use_bsm3 :: boolean(), frames=[] :: [beam_ssa:label()], intervals=[] :: [{b_var(),[range()]}], - aliases=[] :: [{b_var(),b_var()}], res=[] :: [{b_var(),reservation()}] | #{b_var():=reservation()}, regs=#{} :: #{b_var():=ssa_register()}, extra_annos=[] :: [{atom(),term()}] }). -define(PASS(N), {N,fun N/1}). -passes(FixTuples, ExtraAnnos) -> +passes(Opts) -> + AddPrecgAnnos = proplists:get_bool(dprecg, Opts), + FixTuples = proplists:get_bool(no_put_tuple2, Opts), Ps = [?PASS(assert_no_critical_edges), %% Preliminaries. @@ -138,27 +139,25 @@ passes(FixTuples, ExtraAnnos) -> %% Calculate live intervals. ?PASS(number_instructions), ?PASS(live_intervals), - ?PASS(remove_unsuitable_aliases), ?PASS(reserve_regs), - ?PASS(merge_intervals), %% If needed for a .precg file, save the live intervals %% so they can be included in an annotation. - case ExtraAnnos of + case AddPrecgAnnos of false -> ignore; true -> ?PASS(save_live_intervals) end, %% Allocate registers. ?PASS(linear_scan), - ?PASS(fix_aliased_regs), ?PASS(frame_size), ?PASS(turn_yregs)], [P || P <- Ps, P =/= ignore]. -function(#b_function{anno=Anno,args=Args,bs=Blocks0,cnt=Count0}=F0, Ps) -> +function(#b_function{anno=Anno,args=Args,bs=Blocks0,cnt=Count0}=F0, + Ps, UseBSM3) -> try - St0 = #st{ssa=Blocks0,args=Args,cnt=Count0}, + St0 = #st{ssa=Blocks0,args=Args,use_bsm3=UseBSM3,cnt=Count0}, St = compile:run_sub_passes(Ps, St0), #st{ssa=Blocks,cnt=Count,regs=Regs,extra_annos=ExtraAnnos} = St, F1 = add_extra_annos(F0, ExtraAnnos), @@ -174,14 +173,6 @@ function(#b_function{anno=Anno,args=Args,bs=Blocks0,cnt=Count0}=F0, Ps) -> save_live_intervals(#st{intervals=Intervals}=St) -> St#st{extra_annos=[{live_intervals,Intervals}]}. -fix_aliased_regs(#st{aliases=Aliases,regs=Regs}=St) -> - St#st{regs=fix_aliased_regs(Aliases, Regs)}. - -fix_aliased_regs([{Alias,V}|Aliases], Regs) -> - #{V:=Reg} = Regs, - fix_aliased_regs(Aliases, Regs#{Alias=>Reg}); -fix_aliased_regs([], Regs) -> Regs. - %% Add extra annotations when a .precg listing file is being produced. add_extra_annos(F, Annos) -> foldl(fun({Name,Value}, Acc) -> @@ -214,7 +205,7 @@ assert_no_ces(_, _, Blocks) -> Blocks. %% * Combine bs_match and bs_extract instructions to bs_get %% instructions. -fix_bs(#st{ssa=Blocks,cnt=Count0}=St) -> +fix_bs(#st{ssa=Blocks,cnt=Count0,use_bsm3=UseBSM3}=St) -> F = fun(#b_set{op=bs_start_match,dst=Dst}, A) -> %% Mark the root of the match context list. [{Dst,{context,Dst}}|A]; @@ -232,8 +223,13 @@ fix_bs(#st{ssa=Blocks,cnt=Count0}=St) -> CtxChain = maps:from_list(M), Linear0 = beam_ssa:linearize(Blocks), - %% Insert bs_save / bs_restore instructions where needed. - {Linear1,Count} = bs_save_restore(Linear0, CtxChain, Count0), + %% Insert position instructions where needed. + {Linear1,Count} = case UseBSM3 of + true -> + bs_pos_bsm3(Linear0, CtxChain, Count0); + false -> + bs_pos_bsm2(Linear0, CtxChain, Count0) + end, %% Rename instructions. Linear = bs_instrs(Linear1, CtxChain, []), @@ -241,10 +237,54 @@ fix_bs(#st{ssa=Blocks,cnt=Count0}=St) -> St#st{ssa=maps:from_list(Linear),cnt=Count} end. +%% Insert bs_get_position and bs_set_position instructions as needed. +bs_pos_bsm3(Linear0, CtxChain, Count0) -> + Rs0 = bs_restores(Linear0, CtxChain, #{}, #{}), + Rs = maps:values(Rs0), + S0 = sofs:relation(Rs, [{context,save_point}]), + S1 = sofs:relation_to_family(S0), + S = sofs:to_external(S1), + + {SavePoints,Count1} = make_bs_pos_dict(S, Count0, []), + {Gets,Count2} = make_bs_setpos_map(Rs, SavePoints, Count1, []), + {Sets,Count} = make_bs_getpos_map(maps:to_list(Rs0), SavePoints, Count2, []), + + %% Now insert all saves and restores. + {bs_insert_bsm3(Linear0, Gets, Sets, SavePoints),Count}. + +make_bs_setpos_map([{Ctx,Save}=Ps|T], SavePoints, Count, Acc) -> + SavePoint = get_savepoint(Ps, SavePoints), + I = #b_set{op=bs_get_position,dst=SavePoint,args=[Ctx]}, + make_bs_setpos_map(T, SavePoints, Count+1, [{Save,I}|Acc]); +make_bs_setpos_map([], _, Count, Acc) -> + {maps:from_list(Acc),Count}. + +make_bs_getpos_map([{Bef,{Ctx,_}=Ps}|T], SavePoints, Count, Acc) -> + Ignored = #b_var{name={'@ssa_ignored',Count}}, + Args = [Ctx, get_savepoint(Ps, SavePoints)], + I = #b_set{op=bs_set_position,dst=Ignored,args=Args}, + make_bs_getpos_map(T, SavePoints, Count+1, [{Bef,I}|Acc]); +make_bs_getpos_map([], _, Count, Acc) -> + {maps:from_list(Acc),Count}. + +get_savepoint({_,_}=Ps, SavePoints) -> + Name = {'@ssa_bs_position', maps:get(Ps, SavePoints)}, + #b_var{name=Name}. -%% Insert bs_save and bs_restore instructions as needed. +make_bs_pos_dict([{Ctx,Pts}|T], Count0, Acc0) -> + {Acc, Count} = make_bs_pos_dict_1(Pts, Ctx, Count0, Acc0), + make_bs_pos_dict(T, Count, Acc); +make_bs_pos_dict([], Count, Acc) -> + {maps:from_list(Acc), Count}. -bs_save_restore(Linear0, CtxChain, Count0) -> +make_bs_pos_dict_1([H|T], Ctx, I, Acc) -> + make_bs_pos_dict_1(T, Ctx, I+1, [{{Ctx,H},I}|Acc]); +make_bs_pos_dict_1([], Ctx, I, Acc) -> + {[{Ctx,I}|Acc], I}. + +%% As bs_position but without OTP-22 instructions. This is only used when +%% cross-compiling to older versions. +bs_pos_bsm2(Linear0, CtxChain, Count0) -> Rs0 = bs_restores(Linear0, CtxChain, #{}, #{}), Rs = maps:values(Rs0), S0 = sofs:relation(Rs, [{context,save_point}]), @@ -255,7 +295,7 @@ bs_save_restore(Linear0, CtxChain, Count0) -> {Restores,Count} = make_restore_map(maps:to_list(Rs0), Slots, Count1, []), %% Now insert all saves and restores. - {bs_insert(Linear0, Saves, Restores, Slots),Count}. + {bs_insert_bsm2(Linear0, Saves, Restores, Slots),Count}. make_save_map([{Ctx,Save}=Ps|T], Slots, Count, Acc) -> Ignored = #b_var{name={'@ssa_ignored',Count}}, @@ -308,8 +348,7 @@ bs_restores([], _, _, Rs) -> Rs. bs_update_successors(#b_br{succ=Succ,fail=Fail}, SPos, FPos, D) -> join_positions([{Succ,SPos},{Fail,FPos}], D); -bs_update_successors(#b_switch{fail=Fail,list=List}, SPos, FPos, D) -> - SPos = FPos, %Assertion. +bs_update_successors(#b_switch{fail=Fail,list=List}, SPos, _FPos, D) -> Update = [{L,SPos} || {_,L} <- List] ++ [{Fail,SPos}], join_positions(Update, D); bs_update_successors(#b_ret{}, _, _, D) -> D. @@ -388,10 +427,19 @@ bs_restores_is([#b_set{op=bs_extract,args=[FromPos|_]}|Is], Start = bs_subst_ctx(FromPos, CtxChain), #{Start:=FromPos} = PosMap, %Assertion. bs_restores_is(Is, CtxChain, PosMap, Rs); +bs_restores_is([#b_set{op=call,dst=Dst,args=Args}|Is], + CtxChain, PosMap0, Rs0) -> + {Rs,PosMap1} = bs_restore_args(Args, PosMap0, CtxChain, Dst, Rs0), + PosMap = bs_invalidate_pos(Args, PosMap1, CtxChain), + bs_restores_is(Is, CtxChain, PosMap, Rs); +bs_restores_is([#b_set{op=landingpad}|Is], CtxChain, PosMap0, Rs) -> + %% We can land here from any point, so all positions are invalid. + PosMap = maps:map(fun(_Start,_Pos) -> unknown end, PosMap0), + bs_restores_is(Is, CtxChain, PosMap, Rs); bs_restores_is([#b_set{op=Op,dst=Dst,args=Args}|Is], CtxChain, PosMap0, Rs0) when Op =:= bs_test_tail; - Op =:= call -> + Op =:= bs_get_tail -> {Rs,PosMap} = bs_restore_args(Args, PosMap0, CtxChain, Dst, Rs0), bs_restores_is(Is, CtxChain, PosMap, Rs); bs_restores_is([_|Is], CtxChain, PosMap, Rs) -> @@ -399,7 +447,6 @@ bs_restores_is([_|Is], CtxChain, PosMap, Rs) -> bs_restores_is([], _CtxChain, PosMap, Rs) -> {PosMap,Rs}. - bs_match_type(#b_set{args=[#b_literal{val=skip},_Ctx, #b_literal{val=binary},_Flags, #b_literal{val=all},#b_literal{val=U}]}) -> @@ -410,6 +457,23 @@ bs_match_type(#b_set{args=[#b_literal{val=skip},_Ctx, bs_match_type(_) -> plain. +%% Call instructions leave the match position in an undefined state, +%% requiring us to invalidate each affected argument. +bs_invalidate_pos([#b_var{}=Arg|Args], PosMap0, CtxChain) -> + Start = bs_subst_ctx(Arg, CtxChain), + case PosMap0 of + #{Start:=_} -> + PosMap = PosMap0#{Start:=unknown}, + bs_invalidate_pos(Args, PosMap, CtxChain); + #{} -> + %% Not a match context. + bs_invalidate_pos(Args, PosMap0, CtxChain) + end; +bs_invalidate_pos([_|Args], PosMap, CtxChain) -> + bs_invalidate_pos(Args, PosMap, CtxChain); +bs_invalidate_pos([], PosMap, _CtxChain) -> + PosMap. + bs_restore_args([#b_var{}=Arg|Args], PosMap0, CtxChain, Dst, Rs0) -> Start = bs_subst_ctx(Arg, CtxChain), case PosMap0 of @@ -432,33 +496,45 @@ bs_restore_args([], PosMap, _CtxChain, _Dst, Rs) -> %% Insert all bs_save and bs_restore instructions. -bs_insert([{L,#b_blk{is=Is0}=Blk}|Bs0], Saves, Restores, Slots) -> - Is = bs_insert_is_1(Is0, Restores, Slots), +bs_insert_bsm3(Blocks, Saves, Restores, SavePoints) -> + bs_insert_1(Blocks, Saves, Restores, SavePoints, fun(I) -> I end). + +bs_insert_bsm2(Blocks, Saves, Restores, SavePoints) -> + %% The old instructions require bs_start_match to be annotated with the + %% number of position slots it needs. + bs_insert_1(Blocks, Saves, Restores, SavePoints, + fun(#b_set{op=bs_start_match,dst=Dst}=I0) -> + NumSlots = case SavePoints of + #{Dst:=NumSlots0} -> NumSlots0; + #{} -> 0 + end, + beam_ssa:add_anno(num_slots, NumSlots, I0); + (I) -> + I + end). + +bs_insert_1([{L,#b_blk{is=Is0}=Blk}|Bs0], Saves, Restores, Slots, XFrm) -> + Is = bs_insert_is_1(Is0, Restores, Slots, XFrm), Bs = bs_insert_saves(Is, Bs0, Saves), - [{L,Blk#b_blk{is=Is}}|bs_insert(Bs, Saves, Restores, Slots)]; -bs_insert([], _, _, _) -> []. + [{L,Blk#b_blk{is=Is}}|bs_insert_1(Bs, Saves, Restores, Slots, XFrm)]; +bs_insert_1([], _, _, _, _) -> []. -bs_insert_is_1([#b_set{op=Op,dst=Dst}=I0|Is], Restores, Slots) -> +bs_insert_is_1([#b_set{op=Op,dst=Dst}=I0|Is], Restores, SavePoints, XFrm) -> + I = XFrm(I0), if Op =:= bs_test_tail; + Op =:= bs_get_tail; Op =:= bs_match; Op =:= call -> Rs = case Restores of #{Dst:=R} -> [R]; #{} -> [] end, - Rs ++ [I0|bs_insert_is_1(Is, Restores, Slots)]; - Op =:= bs_start_match -> - NumSlots = case Slots of - #{Dst:=NumSlots0} -> NumSlots0; - #{} -> 0 - end, - I = beam_ssa:add_anno(num_slots, NumSlots, I0), - [I|bs_insert_is_1(Is, Restores, Slots)]; + Rs ++ [I|bs_insert_is_1(Is, Restores, SavePoints, XFrm)]; true -> - [I0|bs_insert_is_1(Is, Restores, Slots)] + [I|bs_insert_is_1(Is, Restores, SavePoints, XFrm)] end; -bs_insert_is_1([], _, _) -> []. +bs_insert_is_1([], _, _, _) -> []. bs_insert_saves([#b_set{dst=Dst}|Is], Bs, Saves) -> case Saves of @@ -504,6 +580,8 @@ bs_instrs_is([#b_set{op=Op,args=Args0}=I0|Is], CtxChain, Acc) -> I1#b_set{op=bs_skip,args=[Type,Ctx|As]}; {bs_match,[#b_literal{val=string},Ctx|As]} -> I1#b_set{op=bs_match_string,args=[Ctx|As]}; + {bs_get_tail,[Ctx|As]} -> + I1#b_set{op=bs_get_tail,args=[Ctx|As]}; {_,_} -> I1 end, @@ -1520,10 +1598,10 @@ live_intervals(#st{args=Args,ssa=Blocks}=St) -> Vars0 = [{V,{0,1}} || #b_var{}=V <- Args], F = fun(L, _, A) -> live_interval_blk(L, Blocks, A) end, LiveMap0 = #{}, - Acc0 = {[],[],LiveMap0}, - {Vars,Aliases,_} = beam_ssa:fold_po(F, Acc0, Blocks), + Acc0 = {[],LiveMap0}, + {Vars,_} = beam_ssa:fold_po(F, Acc0, Blocks), Intervals = merge_ranges(rel2fam(Vars0++Vars)), - St#st{intervals=Intervals,aliases=Aliases}. + St#st{intervals=Intervals}. merge_ranges([{V,Rs}|T]) -> [{V,merge_ranges_1(Rs)}|merge_ranges(T)]; @@ -1535,7 +1613,7 @@ merge_ranges_1([R|Rs]) -> [R|merge_ranges_1(Rs)]; merge_ranges_1([]) -> []. -live_interval_blk(L, Blocks, {Vars0,Aliases0,LiveMap0}) -> +live_interval_blk(L, Blocks, {Vars0,LiveMap0}) -> Live0 = [], Successors = beam_ssa:successors(L, Blocks), Live1 = update_successors(Successors, L, Blocks, LiveMap0, Live0), @@ -1547,8 +1625,7 @@ live_interval_blk(L, Blocks, {Vars0,Aliases0,LiveMap0}) -> %% Determine used and defined variables in this block. FirstNumber = first_number(Is, Last), - {UseDef0,Aliases} = live_interval_blk_1([Last|reverse(Is)], - FirstNumber, Aliases0, Use), + UseDef0 = live_interval_blk_1([Last|reverse(Is)], FirstNumber, Use), UseDef = rel2fam(UseDef0), %% Update what is live at the beginning of this block and @@ -1561,7 +1638,7 @@ live_interval_blk(L, Blocks, {Vars0,Aliases0,LiveMap0}) -> %% Construct the ranges for this block. Vars = make_block_ranges(UseDef, FirstNumber, Vars0), - {Vars,Aliases,LiveMap}. + {Vars,LiveMap}. make_block_ranges([{V,[{def,Def}]}|Vs], First, Acc) -> make_block_ranges(Vs, First, [{V,{Def,Def}}|Acc]); @@ -1573,25 +1650,17 @@ make_block_ranges([{V,[{use,_}|_]=Uses}|Vs], First, Acc) -> make_block_ranges(Vs, First, [{V,{First,Last}}|Acc]); make_block_ranges([], _, Acc) -> Acc. -live_interval_blk_1([#b_set{op=phi,dst=Dst}|Is], - FirstNumber, Aliases, Acc0) -> +live_interval_blk_1([#b_set{op=phi,dst=Dst}|Is], FirstNumber, Acc0) -> Acc = [{Dst,{def,FirstNumber}}|Acc0], - live_interval_blk_1(Is, FirstNumber, Aliases, Acc); -live_interval_blk_1([#b_set{op=bs_start_match}=I|Is], FirstNumber, - Aliases0, Acc0) -> + live_interval_blk_1(Is, FirstNumber, Acc); +live_interval_blk_1([#b_set{op=bs_start_match}=I|Is], + FirstNumber, Acc0) -> N = beam_ssa:get_anno(n, I), #b_set{dst=Dst} = I, Acc1 = [{Dst,{def,N}}|Acc0], - Aliases = case beam_ssa:get_anno(reuse_for_context, I) of - true -> - #b_set{args=[Src]} = I, - [{Dst,Src}|Aliases0]; - false -> - Aliases0 - end, Acc = [{V,{use,N}} || V <- beam_ssa:used(I)] ++ Acc1, - live_interval_blk_1(Is, FirstNumber, Aliases, Acc); -live_interval_blk_1([I|Is], FirstNumber, Aliases, Acc0) -> + live_interval_blk_1(Is, FirstNumber, Acc); +live_interval_blk_1([I|Is], FirstNumber, Acc0) -> N = beam_ssa:get_anno(n, I), Acc1 = case I of #b_set{dst=Dst} -> @@ -1601,9 +1670,9 @@ live_interval_blk_1([I|Is], FirstNumber, Aliases, Acc0) -> end, Used = beam_ssa:used(I), Acc = [{V,{use,N}} || V <- Used] ++ Acc1, - live_interval_blk_1(Is, FirstNumber, Aliases, Acc); -live_interval_blk_1([], _FirstNumber, Aliases, Acc) -> - {Acc,Aliases}. + live_interval_blk_1(Is, FirstNumber, Acc); +live_interval_blk_1([], _FirstNumber, Acc) -> + Acc. %% first_number([#b_set{}]) -> InstructionNumber. %% Return the number for the first instruction for the block. @@ -1865,10 +1934,10 @@ reserve_zreg([#b_set{op={bif,tuple_size},dst=Dst}], reserve_zreg_1(Dst, ShortLived, A); reserve_zreg([#b_set{op=Op,dst=Dst}|Is], Last, ShortLived, A0) -> IsZReg = case Op of - context_to_binary -> true; bs_match_string -> true; - bs_restore -> true; bs_save -> true; + bs_restore -> true; + bs_set_position -> true; {float,clearerror} -> true; kill_try_tag -> true; landingpad -> true; @@ -2040,82 +2109,6 @@ res_xregs_prune(Xs, Used, Res) -> maps:filter(fun(_, {x,X}) -> X < NumSafe end, Xs). %%% -%%% Remove unsuitable aliases. -%%% -%%% If a binary is matched more than once, we must not put the -%%% the match context in the same register as the binary to -%%% avoid the following situation: -%%% -%%% {test,bs_start_match2,{f,3},1,[{x,0},0],{x,0}}. -%%% . -%%% . -%%% . -%%% {test,bs_start_match2,{f,6},1,[{x,0},0],{x,1}}. %% ILLEGAL! -%%% -%%% The second instruction is illegal because a match context source -%%% is only allowed if source and destination registers are identical. -%%% - -remove_unsuitable_aliases(#st{aliases=[_|_]=Aliases0,ssa=Blocks}=St) -> - R = rem_unsuitable(maps:values(Blocks)), - Unsuitable0 = [V || {V,[_,_|_]} <- rel2fam(R)], - Unsuitable = gb_sets:from_list(Unsuitable0), - Aliases =[P || {_,V}=P <- Aliases0, - not gb_sets:is_member(V, Unsuitable)], - St#st{aliases=Aliases}; -remove_unsuitable_aliases(#st{aliases=[]}=St) -> St. - -rem_unsuitable([#b_blk{is=Is}|Bs]) -> - Vs = [{Var,Dst} || - #b_set{op=bs_start_match,dst=Dst, - args=[#b_var{}=Var]} <- Is], - Vs ++ rem_unsuitable(Bs); -rem_unsuitable([]) -> []. - -%%% -%%% Merge intervals. -%%% - -merge_intervals(#st{aliases=Aliases0,intervals=Intervals0, - res=Reserved}=St) -> - Aliases1 = [A || A <- Aliases0, - is_suitable_alias(A, Reserved)], - case Aliases1 of - [] -> - St#st{aliases=Aliases1}; - [_|_] -> - Intervals1 = maps:from_list(Intervals0), - {Intervals,Aliases} = - merge_intervals_1(Aliases1, Intervals1, []), - St#st{aliases=Aliases,intervals=Intervals} - end. - -merge_intervals_1([{Alias,V}|Vs], Intervals0, Acc) -> - #{Alias:=Int1,V:=Int2} = Intervals0, - Int3 = lists:merge(Int1, Int2), - Int = merge_intervals_2(Int3), - Intervals1 = maps:remove(Alias, Intervals0), - Intervals = Intervals1#{V:=Int}, - merge_intervals_1(Vs, Intervals, [{Alias,V}|Acc]); -merge_intervals_1([], Intervals, Acc) -> - {maps:to_list(Intervals),Acc}. - -merge_intervals_2([{A1,B1},{A2,B2}|Is]) when A2 =< B1 -> - merge_intervals_2([{min(A1, A2),max(B1, B2)}|Is]); -merge_intervals_2([{_A1,B1}=R|[{A2,_B2}|_]=Is]) when B1 < A2 -> - [R|merge_intervals_2(Is)]; -merge_intervals_2([_]=Is) -> Is. - -is_suitable_alias({V1,V2}, Reserved) -> - #{V1:=Res1,V2:=Res2} = Reserved, - case {Res1,Res2} of - {x,x} -> true; - {x,{x,_}} -> true; - {{x,_},x} -> true; - {_,_} -> false - end. - -%%% %%% Register allocation using linear scan. %%% diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index 5ccc9c371b..18e6e73a46 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -486,6 +486,8 @@ type(bs_extract, [Ctx], Ts, _Ds) -> Type; type(bs_match, Args, _Ts, _Ds) -> #t_bs_match{type=bs_match_type(Args)}; +type(bs_get_tail, _Args, _Ts, _Ds) -> + {binary, 1}; type(call, [#b_remote{mod=#b_literal{val=Mod}, name=#b_literal{val=Name}}|Args], Ts, _Ds) -> case {Mod,Name,Args} of diff --git a/lib/compiler/src/beam_utils.erl b/lib/compiler/src/beam_utils.erl index 686d314c2d..626e041ea0 100644 --- a/lib/compiler/src/beam_utils.erl +++ b/lib/compiler/src/beam_utils.erl @@ -458,11 +458,6 @@ check_liveness(R, [{get_tuple_element,S,_,D}|Is], St) -> D -> {killed,St}; _ -> check_liveness(R, Is, St) end; -check_liveness(R, [{bs_context_to_binary,S}|Is], St) -> - case R of - S -> {used,St}; - _ -> check_liveness(R, Is, St) - end; check_liveness(R, [{loop_rec,{f,_},{x,0}}|_], St) -> case R of {x,_} -> diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index e76b097500..ca065295d6 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -90,33 +90,30 @@ format_error(Error) -> %% format as used in the compiler and in .S files. validate(Module, Fs) -> - Ft = index_bs_start_match(Fs, []), + Ft = index_parameter_types(Fs, []), validate_0(Module, Fs, Ft). -index_bs_start_match([{function,_,_,Entry,Code0}|Fs], Acc0) -> +index_parameter_types([{function,_,_,Entry,Code0}|Fs], Acc0) -> Code = dropwhile(fun({label,L}) when L =:= Entry -> false; (_) -> true end, Code0), case Code of [{label,Entry}|Is] -> - Acc = index_bs_start_match_1(Is, Entry, Acc0), - index_bs_start_match(Fs, Acc); + Acc = index_parameter_types_1(Is, Entry, Acc0), + index_parameter_types(Fs, Acc); _ -> %% Something serious is wrong. Ignore it for now. %% It will be detected and diagnosed later. - index_bs_start_match(Fs, Acc0) + index_parameter_types(Fs, Acc0) end; -index_bs_start_match([], Acc) -> +index_parameter_types([], Acc) -> gb_trees:from_orddict(lists:sort(Acc)). -index_bs_start_match_1([{test,bs_start_match2,_,_,_,_}=I|_], Entry, Acc) -> - [{Entry,[I]}|Acc]; -index_bs_start_match_1([{test,_,{f,F},_},{bs_context_to_binary,_}|Is0], Entry, Acc) -> - [{label,F}|Is] = dropwhile(fun({label,L}) when L =:= F -> false; - (_) -> true - end, Is0), - index_bs_start_match_1(Is, Entry, Acc); -index_bs_start_match_1(_, _, Acc) -> Acc. +index_parameter_types_1([{'%', {type_info, Reg, Type}} | Is], Entry, Acc) -> + Key = {Entry, Reg}, + index_parameter_types_1(Is, Entry, [{Key, Type} | Acc]); +index_parameter_types_1(_, _, Acc) -> + Acc. validate_0(_Module, [], _) -> []; validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) -> @@ -289,17 +286,21 @@ valfun_1({try_case_end,Src}, Vst) -> assert_term(Src, Vst), kill_state(Vst); %% Instructions that cannot cause exceptions -valfun_1({bs_context_to_binary,Ctx}, #vst{current=#st{x=Xs}}=Vst) -> - case Ctx of - {Tag,X} when Tag =:= x; Tag =:= y -> - Type = case gb_trees:lookup(X, Xs) of - {value,#ms{}} -> term; - _ -> get_term_type(Ctx, Vst) - end, - set_type_reg(Type, Ctx, Vst); - _ -> - error({bad_source,Ctx}) - end; +valfun_1({bs_get_tail,Ctx,Dst,Live}, Vst0) -> + verify_live(Live, Vst0), + verify_y_init(Vst0), + Vst = prune_x_regs(Live, Vst0), + #vst{current=#st{x=Xs,y=Ys}} = Vst, + {Reg, Tree} = case Ctx of + {x,X} -> {X, Xs}; + {y,Y} -> {Y, Ys}; + _ -> error({bad_source,Ctx}) + end, + Type = case gb_trees:lookup(Reg, Tree) of + {value,#ms{}} -> propagate_fragility(term, [Ctx], Vst); + _ -> error({bad_context,Reg}) + end, + set_type_reg(Type, Dst, Vst); valfun_1(bs_init_writable=I, Vst) -> call(I, 1, Vst); valfun_1(build_stacktrace=I, Vst) -> @@ -385,6 +386,25 @@ valfun_1(remove_message, Vst) -> %% The message term is no longer fragile. It can be used %% without restrictions. remove_fragility(Vst); +valfun_1({'%', {type_info, Reg, Info0}}, Vst0) -> + %% Explicit type information inserted by optimization passes to indicate + %% that Reg has a certain type, so that we can accept cross-function type + %% optimizations. + %% + %% At the moment we only allow this when narrowing from 'term' which is + %% what to expect with function parameters, but in theory any narrowing + %% conversion should be legal. + case get_move_term_type(Reg, Vst0) of + term -> + Type0 = case Info0 of + match_context -> #ms{}; + _ -> Info0 + end, + Type = propagate_fragility(Type0, [Reg], Vst0), + set_type_reg(Type, Reg, Vst0); + _ -> + error(bad_type_info) + end; valfun_1({'%',_}, Vst) -> Vst; valfun_1({line,_}, Vst) -> @@ -676,32 +696,44 @@ valfun_4({select_tuple_arity,Tuple,{f,Fail},{list,Choices}}, Vst) -> branch_state(Fail, Vst))); %% New bit syntax matching instructions. -valfun_4({test,bs_start_match2,{f,Fail},Live,[Ctx,NeedSlots],Ctx}, Vst0) -> - %% If source and destination registers are the same, match state - %% is OK as input. - CtxType = get_move_term_type(Ctx, Vst0), +valfun_4({test,bs_start_match3,{f,Fail},Live,[Src],Dst}, Vst0) -> + %% Match states are always okay as input. + SrcType = get_move_term_type(Src, Vst0), + DstType = propagate_fragility(bsm_match_state(), [Src], Vst0), verify_live(Live, Vst0), verify_y_init(Vst0), Vst1 = prune_x_regs(Live, Vst0), - BranchVst = case CtxType of - #ms{} -> - %% The failure branch will never be taken when Ctx - %% is a match context. Therefore, the type for Ctx - %% at the failure label must not be match_context - %% (or we could reject legal code). - set_type_reg(term, Ctx, Vst1); - _ -> - Vst1 - end, + BranchVst = case SrcType of + #ms{} -> + %% The failure branch will never be taken when Src is a + %% match context. Therefore, the type for Src at the + %% failure label must not be match_context (or we could + %% reject legal code). + set_type_reg(term, Src, Vst1); + _ -> + Vst1 + end, Vst = branch_state(Fail, BranchVst), - set_type_reg(bsm_match_state(NeedSlots), Ctx, Vst); + set_type_reg(DstType, Dst, Vst); valfun_4({test,bs_start_match2,{f,Fail},Live,[Src,Slots],Dst}, Vst0) -> - assert_term(Src, Vst0), + %% Match states are always okay as input. + SrcType = get_move_term_type(Src, Vst0), + DstType = propagate_fragility(bsm_match_state(Slots), [Src], Vst0), verify_live(Live, Vst0), verify_y_init(Vst0), Vst1 = prune_x_regs(Live, Vst0), - Vst = branch_state(Fail, Vst1), - set_type_reg(bsm_match_state(Slots), Src, Dst, Vst); + BranchVst = case SrcType of + #ms{} -> + %% The failure branch will never be taken when Src is a + %% match context. Therefore, the type for Src at the + %% failure label must not be match_context (or we could + %% reject legal code). + set_type_reg(term, Src, Vst1); + _ -> + Vst1 + end, + Vst = branch_state(Fail, BranchVst), + set_type_reg(DstType, Dst, Vst); valfun_4({test,bs_match_string,{f,Fail},[Ctx,_,_]}, Vst) -> bsm_validate_context(Ctx, Vst), branch_state(Fail, Vst); @@ -738,6 +770,16 @@ valfun_4({bs_save2,Ctx,SavePoint}, Vst) -> bsm_save(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), + verify_live(Live, Vst0), + verify_y_init(Vst0), + Vst = prune_x_regs(Live, Vst0), + set_type_reg(bs_position, Dst, Vst); +valfun_4({bs_set_position, Ctx, Pos}, Vst) -> + bsm_validate_context(Ctx, Vst), + assert_type(bs_position, Pos, Vst), + Vst; %% Other test instructions. valfun_4({test,is_float,{f,Lbl},[Float]}, Vst) -> @@ -999,26 +1041,12 @@ verify_call_args_1(N, Vst) -> verify_call_args_1(X, Vst). verify_local_call(Lbl, Live, Vst) -> - case all_ms_in_x_regs(Live, Vst) of - [{R,Ctx}] -> - %% Verify that there is a suitable bs_start_match2 instruction. - verify_call_match_context(Lbl, R, Vst), - - %% Since the callee has consumed the match context, - %% there must be no additional copies in Y registers. - #ms{id=Id} = Ctx, - case ms_in_y_regs(Id, Vst) of - [] -> - ok; - [_|_]=Ys -> - error({multiple_match_contexts,[R|Ys]}) - end; - [_,_|_]=Xs0 -> - Xs = [R || {R,_} <- Xs0], - error({multiple_match_contexts,Xs}); - [] -> - ok - end. + F = fun({R, _Ctx}) -> + verify_call_match_context(Lbl, R, Vst) + end, + MsRegs = all_ms_in_x_regs(Live, Vst), + verify_no_ms_aliases(MsRegs), + foreach(F, MsRegs). all_ms_in_x_regs(0, _Vst) -> []; @@ -1026,24 +1054,26 @@ all_ms_in_x_regs(Live0, Vst) -> Live = Live0 - 1, R = {x,Live}, case get_move_term_type(R, Vst) of - #ms{}=M -> - [{R,M}|all_ms_in_x_regs(Live, Vst)]; - _ -> - all_ms_in_x_regs(Live, Vst) + #ms{}=M -> [{R,M} | all_ms_in_x_regs(Live, Vst)]; + _ -> all_ms_in_x_regs(Live, Vst) end. -ms_in_y_regs(Id, #vst{current=#st{y=Ys0}}) -> - Ys = gb_trees:to_list(Ys0), - [{y,Y} || {Y,#ms{id=OtherId}} <- Ys, OtherId =:= Id]. +%% Verifies that the same match context isn't present twice. +verify_no_ms_aliases(MsRegs) -> + CtxIds = [Id || {_, #ms{id=Id}} <- MsRegs], + UniqueCtxIds = ordsets:from_list(CtxIds), + if + length(UniqueCtxIds) < length(CtxIds) -> + error({multiple_match_contexts, MsRegs}); + length(UniqueCtxIds) =:= length(CtxIds) -> + ok + end. +%% Verifies that the target label accepts match contexts in the given register. verify_call_match_context(Lbl, Ctx, #vst{ft=Ft}) -> - case gb_trees:lookup(Lbl, Ft) of - none -> - error(no_bs_start_match2); - {value,[{test,bs_start_match2,_,_,[Ctx,_],Ctx}|_]} -> - ok; - {value,[{test,bs_start_match2,_,_,_,_}=I|_]} -> - error({unsuitable_bs_start_match2,I}) + case gb_trees:lookup({Lbl, Ctx}, Ft) of + {value, match_context} -> ok; + none -> error(no_bs_start_match2) end. allocate(Zero, Stk, Heap, Live, #vst{current=#st{numy=none}}=Vst0) -> @@ -1212,6 +1242,8 @@ assert_unique_map_keys([_,_|_]=Ls) -> %%% New binary matching instructions. %%% +bsm_match_state() -> + #ms{}. bsm_match_state(Slots) -> #ms{slots=Slots}. @@ -1225,6 +1257,12 @@ bsm_get_context({x,X}=Reg, #vst{current=#st{x=Xs}}=_Vst) when is_integer(X) -> {value,{fragile,#ms{}=Ctx}} -> Ctx; _ -> error({no_bsm_context,Reg}) end; +bsm_get_context({y,Y}=Reg, #vst{current=#st{y=Ys}}=_Vst) when is_integer(Y) -> + case gb_trees:lookup(Y, Ys) of + {value,#ms{}=Ctx} -> Ctx; + {value,{fragile,#ms{}=Ctx}} -> Ctx; + _ -> error({no_bsm_context,Reg}) + end; bsm_get_context(Reg, _) -> error({bad_source,Reg}). bsm_save(Reg, {atom,start}, Vst) -> @@ -1255,6 +1293,7 @@ bsm_restore(Reg, SavePoint, Vst) -> _ -> error({illegal_restore,SavePoint,range}) end. + select_val_branches(Src, Choices, Vst) -> Infer = infer_types(Src, Vst), select_val_branches_1(Choices, Infer, Vst). diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl index 74ad864163..d894694c79 100644 --- a/lib/compiler/src/compile.erl +++ b/lib/compiler/src/compile.erl @@ -248,6 +248,9 @@ expand_opt(report, Os) -> [report_errors,report_warnings|Os]; expand_opt(return, Os) -> [return_errors,return_warnings|Os]; +expand_opt(no_bsm3, Os) -> + %% The new bsm pass requires bsm3 instructions. + [no_bsm3,no_bsm_opt|Os]; expand_opt(r16, Os) -> expand_opt_before_21(Os); expand_opt(r17, Os) -> @@ -259,13 +262,14 @@ expand_opt(r19, Os) -> expand_opt(r20, Os) -> expand_opt_before_21(Os); expand_opt(r21, Os) -> - [no_put_tuple2|Os]; + [no_put_tuple2 | expand_opt(no_bsm3, Os)]; expand_opt({debug_info_key,_}=O, Os) -> [encrypt_debug_info,O|Os]; expand_opt(O, Os) -> [O|Os]. expand_opt_before_21(Os) -> - [no_put_tuple2,no_get_hd_tl,no_ssa_opt_record,no_utf8_atoms|Os]. + [no_put_tuple2, no_get_hd_tl, no_ssa_opt_record, + no_utf8_atoms | expand_opt(no_bsm3, Os)]. %% format_error(ErrorDescriptor) -> string() @@ -816,6 +820,9 @@ kernel_passes() -> {pass,beam_kernel_to_ssa}, {iff,dssa,{listing,"ssa"}}, {iff,ssalint,{pass,beam_ssa_lint}}, + {unless,no_bsm_opt,{pass,beam_ssa_bsm}}, + {iff,dssabsm,{listing,"ssabsm"}}, + {iff,ssalint,{pass,beam_ssa_lint}}, {unless,no_ssa_opt,{pass,beam_ssa_opt}}, {iff,dssaopt,{listing,"ssaopt"}}, {iff,ssalint,{pass,beam_ssa_lint}}, @@ -847,8 +854,6 @@ asm_passes() -> {iff,dpeep,{listing,"peep"}}, {pass,beam_clean}, {iff,dclean,{listing,"clean"}}, - {unless,no_bsm_opt,{pass,beam_bsm}}, - {iff,dbsm,{listing,"bsm"}}, {unless,no_stack_trimming,{pass,beam_trim}}, {iff,dtrim,{listing,"trim"}}, {pass,beam_flatten}]}, @@ -2030,7 +2035,6 @@ pre_load() -> beam_asm, beam_block, beam_bs, - beam_bsm, beam_clean, beam_dict, beam_except, @@ -2040,6 +2044,7 @@ pre_load() -> beam_opcodes, beam_peep, beam_ssa, + beam_ssa_bsm, beam_ssa_codegen, beam_ssa_dead, beam_ssa_opt, diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src index bb281376ef..7b802fdd62 100644 --- a/lib/compiler/src/compiler.app.src +++ b/lib/compiler/src/compiler.app.src @@ -25,7 +25,6 @@ beam_asm, beam_block, beam_bs, - beam_bsm, beam_clean, beam_dict, beam_disasm, @@ -37,6 +36,7 @@ beam_opcodes, beam_peep, beam_ssa, + beam_ssa_bsm, beam_ssa_codegen, beam_ssa_dead, beam_ssa_lint, diff --git a/lib/compiler/src/genop.tab b/lib/compiler/src/genop.tab index 8e34e3e291..86590fad87 100755 --- a/lib/compiler/src/genop.tab +++ b/lib/compiler/src/genop.tab @@ -574,7 +574,25 @@ BEAM_FORMAT_NUMBER=0 ## put it into the register Tail. 163: get_tl/2 +# OTP 22 + ## @spec put_tuple2 Destination Elements ## @doc Build a tuple with the elements in the list Elements and put it ## put into register Destination. 164: put_tuple2/2 + +## @spec bs_get_tail Ctx Dst Live +## @doc Sets Dst to the tail of Ctx at the current position +165: bs_get_tail/3 + +## @spec bs_start_match3 Fail Bin Live Dst +## @doc Starts a binary match sequence +166: bs_start_match3/4 + +## @spec bs_get_position Ctx Dst Live +## @doc Sets Dst to the current position of Ctx +167: bs_get_position/3 + +## @spec bs_set_positon Ctx Pos +## @doc Sets the current position of Ctx to Pos +168: bs_set_position/2 diff --git a/lib/compiler/src/sys_core_bsm.erl b/lib/compiler/src/sys_core_bsm.erl index d7b26c3a56..685e807e65 100644 --- a/lib/compiler/src/sys_core_bsm.erl +++ b/lib/compiler/src/sys_core_bsm.erl @@ -24,161 +24,52 @@ -export([module/2,format_error/1]). -include("core_parse.hrl"). --import(lists, [member/2,reverse/1,usort/1]). -spec module(cerl:c_module(), [compile:option()]) -> {'ok', cerl:c_module()}. -module(#c_module{defs=Ds0}=Mod, Opts) -> - {Ds,Ws0} = function(Ds0, [], []), - case member(bin_opt_info, Opts) of - false -> - {ok,Mod#c_module{defs=Ds}}; - true -> - Ws1 = [make_warning(Where, What) || {Where,What} <- Ws0], - Ws = usort(Ws1), - {ok,Mod#c_module{defs=Ds},Ws} - end. +module(#c_module{defs=Ds}=Mod, _Opts) -> + {ok,Mod#c_module{defs=function(Ds)}}. -function([{#c_var{name={F,Arity}}=Name,B0}|Fs], FsAcc, Ws0) -> - try cerl_trees:mapfold(fun bsm_an/2, Ws0, B0) of - {B,Ws} -> - function(Fs, [{Name,B}|FsAcc], Ws) +function([{#c_var{name={F,Arity}}=Name,B0}|Fs]) -> + try cerl_trees:map(fun bsm_reorder/1, B0) of + B -> [{Name,B} | function(Fs)] catch Class:Error:Stack -> - io:fwrite("Function: ~w/~w\n", [F,Arity]), - erlang:raise(Class, Error, Stack) + io:fwrite("Function: ~w/~w\n", [F,Arity]), + erlang:raise(Class, Error, Stack) end; -function([], Fs, Ws) -> - {reverse(Fs),Ws}. +function([]) -> + []. -type error() :: atom(). -spec format_error(error()) -> nonempty_string(). -format_error(bin_opt_alias) -> - "INFO: the '=' operator will prevent delayed sub binary optimization"; -format_error(bin_partition) -> - "INFO: matching non-variables after a previous clause matching a variable " - "will prevent delayed sub binary optimization"; -format_error(bin_var_used) -> - "INFO: using a matched out sub binary will prevent " - "delayed sub binary optimization"; -format_error(orig_bin_var_used_in_guard) -> - "INFO: using the original binary variable in a guard will prevent " - "delayed sub binary optimization"; -format_error(bin_var_used_in_guard) -> - "INFO: using a matched out sub binary in a guard will prevent " - "delayed sub binary optimization". - +format_error(_) -> error(badarg). -%%% -%%% Annotate bit syntax matching to faciliate optimization in further passes. -%%% +%%% Reorder bit syntax matching to faciliate optimization in further passes. -bsm_an(Core0, Ws0) -> - case bsm_an(Core0) of - {ok,Core} -> - {Core,Ws0}; - {ok,Core,W} -> - {Core,[W|Ws0]} - end. +bsm_reorder(#c_case{arg=#c_var{}=V}=Case) -> + bsm_reorder_1([V], Case); +bsm_reorder(#c_case{arg=#c_values{es=Es}}=Case) -> + bsm_reorder_1(Es, Case); +bsm_reorder(Core) -> + Core. -bsm_an(#c_case{arg=#c_var{}=V}=Case) -> - bsm_an_1([V], Case); -bsm_an(#c_case{arg=#c_values{es=Es}}=Case) -> - bsm_an_1(Es, Case); -bsm_an(Other) -> - {ok,Other}. - -bsm_an_1(Vs0, #c_case{clauses=Cs0}=Case) -> +bsm_reorder_1(Vs0, #c_case{clauses=Cs0}=Case) -> case bsm_leftmost(Cs0) of - none -> - {ok,Case}; - 1 -> - bsm_an_2(Vs0, Cs0, Case); - Pos -> - Vs = move_from_col(Pos, Vs0), - Cs = [C#c_clause{pats=move_from_col(Pos, Ps)} || - #c_clause{pats=Ps}=C <- Cs0], - bsm_an_2(Vs, Cs, Case) - end. - -bsm_an_2(Vs, Cs, Case) -> - try - bsm_ensure_no_partition(Cs), - {ok,bsm_do_an(Vs, Cs, Case)} - catch - throw:{problem,Where,What} -> - {ok,Case,{Where,What}} + Pos when Pos > 0, Pos =/= none -> + Vs = core_lib:make_values(move_from_col(Pos, Vs0)), + Cs = [C#c_clause{pats=move_from_col(Pos, Ps)} + || #c_clause{pats=Ps}=C <- Cs0], + Case#c_case{arg=Vs,clauses=Cs}; + _ -> + Case end. move_from_col(Pos, L) -> {First,[Col|Rest]} = lists:split(Pos - 1, L), [Col|First] ++ Rest. -bsm_do_an([#c_var{name=Vname}=V0|Vs0], Cs0, Case) -> - Cs = bsm_do_an_var(Vname, Cs0), - V = bsm_annotate_for_reuse(V0), - Vs = core_lib:make_values([V|Vs0]), - Case#c_case{arg=Vs,clauses=Cs}; -bsm_do_an(_Vs, _Cs, Case) -> Case. - -bsm_do_an_var(V, [#c_clause{pats=[P|_],guard=G,body=B0}=C0|Cs]) -> - case P of - #c_var{name=VarName} -> - case core_lib:is_var_used(V, G) of - true -> bsm_problem(C0, orig_bin_var_used_in_guard); - false -> ok - end, - case core_lib:is_var_used(VarName, G) of - true -> bsm_problem(C0, bin_var_used_in_guard); - false -> ok - end, - B1 = bsm_maybe_ctx_to_binary(VarName, B0), - B = bsm_maybe_ctx_to_binary(V, B1), - C = C0#c_clause{body=B}, - [C|bsm_do_an_var(V, Cs)]; - #c_alias{} -> - case bsm_could_match_binary(P) of - false -> - [C0|bsm_do_an_var(V, Cs)]; - true -> - bsm_problem(C0, bin_opt_alias) - end; - _ -> - case bsm_could_match_binary(P) andalso bsm_is_var_used(V, G, B0) of - false -> - [C0|bsm_do_an_var(V, Cs)]; - true -> - bsm_problem(C0, bin_var_used) - end - end; -bsm_do_an_var(_, []) -> []. - -bsm_annotate_for_reuse(#c_var{anno=Anno}=Var) -> - Var#c_var{anno=[reuse_for_context|Anno]}. - -bsm_is_var_used(V, G, B) -> - core_lib:is_var_used(V, G) orelse core_lib:is_var_used(V, B). - -bsm_maybe_ctx_to_binary(V, B) -> - case core_lib:is_var_used(V, B) andalso not previous_ctx_to_binary(V, B) of - false -> - B; - true -> - #c_seq{arg=#c_primop{name=#c_literal{val=bs_context_to_binary}, - args=[#c_var{name=V}]}, - body=B} - end. - -previous_ctx_to_binary(V, Core) -> - case Core of - #c_seq{arg=#c_primop{name=#c_literal{val=bs_context_to_binary}, - args=[#c_var{name=V}]}} -> - true; - _ -> - false - end. - %% bsm_leftmost(Cs) -> none | ArgumentNumber %% Find the leftmost argument that matches a nonempty binary. %% Return either 'none' or the argument number (1-N). @@ -200,94 +91,3 @@ bsm_leftmost_2([_|Ps], Cs, N, Pos) -> bsm_leftmost_2(Ps, Cs, N+1, Pos); bsm_leftmost_2([], Cs, _, Pos) -> bsm_leftmost_1(Cs, Pos). - -%% bsm_ensure_no_partition(Cs) -> ok (exception if problem) -%% There must only be a single bs_start_match2 instruction if we -%% are to reuse the binary variable for the match context. -%% -%% To make sure that there is only a single bs_start_match2 -%% instruction, we will check for partitions such as: -%% -%% foo(<<...>>) -> ... -%% foo(<Variable>) when ... -> ... -%% foo(<Non-variable pattern>) -> -%% -%% If there is such partition, we reject the optimization. - -bsm_ensure_no_partition(Cs) -> - bsm_ensure_no_partition_1(Cs, before). - -%% Loop through each clause. -bsm_ensure_no_partition_1([#c_clause{pats=Ps,guard=G}|Cs], State0) -> - State = bsm_ensure_no_partition_2(Ps, G, State0), - case State of - 'after' -> - bsm_ensure_no_partition_after(Cs); - _ -> - ok - end, - bsm_ensure_no_partition_1(Cs, State); -bsm_ensure_no_partition_1([], _) -> ok. - -bsm_ensure_no_partition_2([#c_binary{}|_], _, _State) -> - within; -bsm_ensure_no_partition_2([#c_alias{}=Alias|_], N, State) -> - %% Retrieve the real pattern that the alias refers to and check that. - P = bsm_real_pattern(Alias), - bsm_ensure_no_partition_2([P], N, State); -bsm_ensure_no_partition_2([_|_], _, before=State) -> - %% No binary matching yet - therefore no partition. - State; -bsm_ensure_no_partition_2([P|_], _, State) -> - case bsm_could_match_binary(P) of - false -> - State; - true -> - %% The pattern P *may* match a binary, so we must update the state. - %% (P must be a variable.) - 'after' - end. - -bsm_ensure_no_partition_after([#c_clause{pats=Ps}=C|Cs]) -> - case Ps of - [#c_var{}|_] -> - bsm_ensure_no_partition_after(Cs); - _ -> - bsm_problem(C, bin_partition) - end; -bsm_ensure_no_partition_after([]) -> ok. - -bsm_could_match_binary(#c_alias{pat=P}) -> bsm_could_match_binary(P); -bsm_could_match_binary(#c_cons{}) -> false; -bsm_could_match_binary(#c_tuple{}) -> false; -bsm_could_match_binary(#c_literal{val=Lit}) -> is_bitstring(Lit); -bsm_could_match_binary(_) -> true. - -bsm_real_pattern(#c_alias{pat=P}) -> bsm_real_pattern(P); -bsm_real_pattern(P) -> P. - -bsm_problem(Where, What) -> - throw({problem,Where,What}). - -make_warning(Core, Term) -> - case should_suppress_warning(Core) of - true -> - ok; - false -> - Anno = cerl:get_ann(Core), - Line = get_line(Anno), - File = get_file(Anno), - {File,[{Line,?MODULE,Term}]} - end. - -should_suppress_warning(Core) -> - Ann = cerl:get_ann(Core), - member(compiler_generated, Ann). - -get_line([Line|_]) when is_integer(Line) -> Line; -get_line([_|T]) -> get_line(T); -get_line([]) -> none. - -get_file([{file,File}|_]) -> File; -get_file([_|T]) -> get_file(T); -get_file([]) -> "no_file". % should not happen diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl index fe8e252e5a..f7ca66b1da 100644 --- a/lib/compiler/src/v3_kernel.erl +++ b/lib/compiler/src/v3_kernel.erl @@ -82,8 +82,7 @@ -export([module/2,format_error/1]). -import(lists, [map/2,foldl/3,foldr/3,mapfoldl/3,splitwith/2,member/2, - keymember/3,keyfind/3,partition/2,droplast/1,last/1,sort/1, - reverse/1]). + keyfind/3,partition/2,droplast/1,last/1,sort/1,reverse/1]). -import(ordsets, [add_element/2,del_element/2,union/2,union/1,subtract/2]). -import(cerl, [c_tuple/1]). @@ -1416,7 +1415,6 @@ is_remote_bif(_, _, _) -> false. %% called for effect only. bif_vals(dsetelement, 3) -> 0; -bif_vals(bs_context_to_binary, 1) -> 0; bif_vals(_, _) -> 1. bif_vals(_, _, _) -> 1. @@ -2337,8 +2335,7 @@ uexpr(#k_bif{anno=A,op=Op,args=As}=Bif, {break,Rs}, St0) -> {Brs,St1} = bif_returns(Op, Rs, St0), {Bif#k_bif{anno=#k{us=Used,ns=lit_list_vars(Brs),a=A},ret=Brs}, Used,St1}; -uexpr(#k_match{anno=A,vars=Vs0,body=B0}, Br, St0) -> - Vs = handle_reuse_annos(Vs0, St0), +uexpr(#k_match{anno=A,vars=Vs,body=B0}, Br, St0) -> Rs = break_rets(Br), {B1,Bu,St1} = umatch(B0, Br, St0), case is_in_guard(St1) of @@ -2441,33 +2438,6 @@ make_fdef(Anno, Name, Arity, Vs, Body) -> vars=Vs,body=Body,ret=[]}, #k_fdef{anno=Anno,func=Name,arity=Arity,vars=Vs,body=Match}. - -%% handle_reuse_annos([#k_var{}], State) -> State. -%% In general, it is only safe to reuse a variable for a match context -%% if the original value of the variable will no longer be needed. -%% -%% If a variable has been bound in an outer letrec and is therefore -%% free in the current function, the variable may still be used. -%% We don't bother to check whether the variable is actually used, -%% but simply clears the 'reuse_for_context' annotation for any variable -%% that is free. -handle_reuse_annos(Vs, St) -> - [handle_reuse_anno(V, St) || V <- Vs]. - -handle_reuse_anno(#k_var{anno=A}=V, St) -> - case member(reuse_for_context, A) of - false -> V; - true -> handle_reuse_anno_1(V, St) - end. - -handle_reuse_anno_1(#k_var{anno=Anno,name=Vname}=V, #kern{ff={F,A}}=St) -> - FreeVs = get_free(F, A, St), - case keymember(Vname, #k_var.name, FreeVs) of - true -> V#k_var{anno=Anno--[reuse_for_context]}; - false -> V - end; -handle_reuse_anno_1(V, _St) -> V. - %% get_free(Name, Arity, State) -> [Free]. %% store_free(Name, Arity, [Free], State) -> State. @@ -2511,8 +2481,7 @@ umatch(#k_alt{anno=A,first=F0,then=T0}, Br, St0) -> Used = union(Fu, Tu), {#k_alt{anno=#k{us=Used,ns=[],a=A},first=F1,then=T1}, Used,St2}; -umatch(#k_select{anno=A,var=V0,types=Ts0}, Br, St0) -> - V = handle_reuse_anno(V0, St0), +umatch(#k_select{anno=A,var=V,types=Ts0}, Br, St0) -> {Ts1,Tus,St1} = umatch_list(Ts0, Br, St0), Used = case member(no_usage, get_kanno(V)) of true -> Tus; |