%%
%% %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").
-include("beam_types.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 =/= #{} ->
{Dominators, _} = beam_ssa:dominators(Blocks0),
State0 = #amb{ dominators = Dominators,
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 member(AliasAfter, Dominators) of
true -> amb_create_alias(Arg, Context, Lbl, State);
false -> {Arg, State}
end;
error ->
{Arg, State}
end;
amb_get_alias(#b_remote{mod=Mod0,name=Name0}=Arg0, Lbl, State0) ->
{Mod, State1} = amb_get_alias(Mod0, Lbl, State0),
{Name, State} = amb_get_alias(Name0, Lbl, State1),
Arg = Arg0#b_remote{mod=Mod,name=Name},
{Arg, State};
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 is_var_in_args(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).
is_var_in_args(Var, [Var | _]) -> true;
is_var_in_args(Var, [#b_remote{name=Var} | _]) -> true;
is_var_in_args(Var, [#b_remote{mod=Var} | _]) -> true;
is_var_in_args(Var, [_ | Args]) -> is_var_in_args(Var, Args);
is_var_in_args(_Var, []) -> false.
%%%
%%% 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 ->
{Dominators, _} = beam_ssa:dominators(Blocks0),
{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 = Dominators,
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,
member(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([?EXCEPTION_BLOCK=Lbl | Path], Counter, Acc) ->
%% ?EXCEPTION_BLOCK is a marker and not an actual block, so renaming it
%% will break exception handling.
aca_cs_build_brs(Path, Counter, Acc#{ Lbl => Lbl });
aca_cs_build_brs([Lbl | Path], Counter0, Acc) ->
aca_cs_build_brs(Path, Counter0 + 1, Acc#{ Lbl => Counter0 });
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(#b_remote{mod=Mod0,name=Name0}=Rem, VRs) ->
Mod = aca_cs_arg(Mod0, VRs),
Name = aca_cs_arg(Name0, VRs),
Rem#b_remote{mod=Mod,name=Name};
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 => #t_bs_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]).
