From 09112806c15a81be86730503af36e304ac11d1ed Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Wed, 7 Jun 2017 14:27:15 +0200 Subject: Fix unsafe bit syntax matching optimization As part of sys_core_fold, variables involved in bit syntax matching would be annotated when it would be safe for a later pass to do the delayed sub-binary creation optimization. An implicit assumption regarding the annotation was that the code must not be further optimized. That assumption was broken in 05130e48555891, which introduced a fixpoint iteration (applying the optimizations until there were no more changes). That means that a variable could be annotated as safe for reusing the match context in one iteration, but a later iteration could rewrite the code in a way that would make the optimization unsafe. One way to fix this would be to clear all reuse_for_context annotations before each iteration. But that would be wasteful. Instead I chose to fix the problem by moving out the annotation code to a separate pass (sys_core_bsm) that is run later after all major optimizations of Core Erlang has been done. --- lib/compiler/src/sys_core_bsm.erl | 355 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 355 insertions(+) create mode 100644 lib/compiler/src/sys_core_bsm.erl (limited to 'lib/compiler/src/sys_core_bsm.erl') diff --git a/lib/compiler/src/sys_core_bsm.erl b/lib/compiler/src/sys_core_bsm.erl new file mode 100644 index 0000000000..3e04cc33df --- /dev/null +++ b/lib/compiler/src/sys_core_bsm.erl @@ -0,0 +1,355 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2017. 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% +%% +%% Purpose : Optimize bit syntax matching. + + +-module(sys_core_bsm). +-export([module/2,format_error/1]). + +-include("core_parse.hrl"). +-import(lists, [member/2,nth/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. + +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) + catch + Class:Error -> + Stack = erlang:get_stacktrace(), + io:fwrite("Function: ~w/~w\n", [F,Arity]), + erlang:raise(Class, Error, Stack) + end; +function([], Fs, Ws) -> + {reverse(Fs),Ws}. + +-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_left_var_used_in_guard) -> + "INFO: a variable to the left of the binary pattern is used in a guard; " + "will prevent delayed sub binary optimization"; +format_error(bin_argument_order) -> + "INFO: matching anything else but a plain variable to the left of " + "binary pattern will prevent delayed sub binary optimization; " + "SUGGEST changing argument order"; +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". + + +%%% +%%% Annotate 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_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(Vs, #c_case{clauses=Cs}=Case) -> + case bsm_leftmost(Cs) of + none -> {ok,Case}; + Pos -> bsm_an_2(Vs, Cs, Case, Pos) + end. + +bsm_an_2(Vs, Cs, Case, Pos) -> + case bsm_nonempty(Cs, Pos) of + true -> bsm_an_3(Vs, Cs, Case, Pos); + false -> {ok,Case} + end. + +bsm_an_3(Vs, Cs, Case, Pos) -> + try + bsm_ensure_no_partition(Cs, Pos), + {ok,bsm_do_an(Vs, Pos, Cs, Case)} + catch + throw:{problem,Where,What} -> + {ok,Case,{Where,What}} + end. + +bsm_do_an(Vs0, Pos, Cs0, Case) -> + case nth(Pos, Vs0) of + #c_var{name=Vname}=V0 -> + Cs = bsm_do_an_var(Vname, Pos, Cs0, []), + V = bsm_annotate_for_reuse(V0), + Bef = lists:sublist(Vs0, Pos-1), + Aft = lists:nthtail(Pos, Vs0), + case Bef ++ [V|Aft] of + [_] -> + Case#c_case{arg=V,clauses=Cs}; + Vs -> + Case#c_case{arg=#c_values{es=Vs},clauses=Cs} + end; + _ -> + Case + end. + +bsm_do_an_var(V, S, [#c_clause{pats=Ps,guard=G,body=B0}=C0|Cs], Acc) -> + case nth(S, Ps) 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}, + bsm_do_an_var(V, S, Cs, [C|Acc]); + #c_alias{}=P -> + case bsm_could_match_binary(P) of + false -> + bsm_do_an_var(V, S, Cs, [C0|Acc]); + true -> + bsm_problem(C0, bin_opt_alias) + end; + P -> + case bsm_could_match_binary(P) andalso bsm_is_var_used(V, G, B0) of + false -> + bsm_do_an_var(V, S, Cs, [C0|Acc]); + true -> + bsm_problem(C0, bin_var_used) + end + end; +bsm_do_an_var(_, _, [], Acc) -> reverse(Acc). + +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 does binary matching. Return +%% the number of the argument (1-N). + +bsm_leftmost(Cs) -> + bsm_leftmost_1(Cs, none). + +bsm_leftmost_1([#c_clause{pats=Ps}|Cs], Pos) -> + bsm_leftmost_2(Ps, Cs, 1, Pos); +bsm_leftmost_1([], Pos) -> Pos. + +bsm_leftmost_2(_, Cs, Pos, Pos) -> + bsm_leftmost_1(Cs, Pos); +bsm_leftmost_2([#c_binary{}|_], Cs, N, _) -> + bsm_leftmost_1(Cs, N); +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_nonempty(Cs, Pos) -> true|false +%% Check if at least one of the clauses matches a non-empty +%% binary in the given argument position. +%% +bsm_nonempty([#c_clause{pats=Ps}|Cs], Pos) -> + case nth(Pos, Ps) of + #c_binary{segments=[_|_]} -> + true; + _ -> + bsm_nonempty(Cs, Pos) + end; +bsm_nonempty([], _ ) -> false. + +%% bsm_ensure_no_partition(Cs, Pos) -> ok (exception if problem) +%% We must make sure that matching is not partitioned between +%% variables like this: +%% foo(<<...>>) -> ... +%% foo() when ... -> ... +%% foo() -> +%% If there is such partition, we are not allowed to reuse the binary variable +%% for the match context. +%% +%% Also, arguments to the left of the argument that is matched +%% against a binary, are only allowed to be simple variables, not +%% used in guards. The reason is that we must know that the binary is +%% only matched in one place (i.e. there must be only one bs_start_match2 +%% instruction emitted). + +bsm_ensure_no_partition(Cs, Pos) -> + bsm_ensure_no_partition_1(Cs, Pos, before). + +%% Loop through each clause. +bsm_ensure_no_partition_1([#c_clause{pats=Ps,guard=G}|Cs], Pos, State0) -> + State = bsm_ensure_no_partition_2(Ps, Pos, G, simple_vars, State0), + case State of + 'after' -> + bsm_ensure_no_partition_after(Cs, Pos); + _ -> + ok + end, + bsm_ensure_no_partition_1(Cs, Pos, State); +bsm_ensure_no_partition_1([], _, _) -> ok. + +%% Loop through each pattern for this clause. +bsm_ensure_no_partition_2([#c_binary{}=Where|_], 1, _, Vstate, State) -> + case State of + before when Vstate =:= simple_vars -> within; + before -> bsm_problem(Where, Vstate); + within when Vstate =:= simple_vars -> within; + within -> bsm_problem(Where, Vstate) + end; +bsm_ensure_no_partition_2([#c_alias{}=Alias|_], 1, N, Vstate, State) -> + %% Retrieve the real pattern that the alias refers to and check that. + P = bsm_real_pattern(Alias), + bsm_ensure_no_partition_2([P], 1, N, Vstate, State); +bsm_ensure_no_partition_2([_|_], 1, _, _Vstate, before=State) -> + %% No binary matching yet - therefore no partition. + State; +bsm_ensure_no_partition_2([P|_], 1, _, Vstate, State) -> + case bsm_could_match_binary(P) of + false -> + %% If clauses can be freely arranged (Vstate =:= simple_vars), + %% a clause that cannot match a binary will not partition the clause. + %% Example: + %% + %% a(Var, <<>>) -> ... + %% a(Var, []) -> ... + %% a(Var, <>) -> ... + %% + %% But if the clauses can't be freely rearranged, as in + %% + %% b(Var, <>) -> ... + %% b(1, 2) -> ... + %% + %% we do have a problem. + %% + case Vstate of + simple_vars -> State; + _ -> bsm_problem(P, Vstate) + end; + true -> + %% The pattern P *may* match a binary, so we must update the state. + %% (P must be a variable.) + case State of + within -> 'after'; + 'after' -> 'after' + end + end; +bsm_ensure_no_partition_2([#c_var{name=V}|Ps], N, G, Vstate, S) -> + case core_lib:is_var_used(V, G) of + false -> + bsm_ensure_no_partition_2(Ps, N-1, G, Vstate, S); + true -> + bsm_ensure_no_partition_2(Ps, N-1, G, bin_left_var_used_in_guard, S) + end; +bsm_ensure_no_partition_2([_|Ps], N, G, _, S) -> + bsm_ensure_no_partition_2(Ps, N-1, G, bin_argument_order, S). + +bsm_ensure_no_partition_after([#c_clause{pats=Ps}=C|Cs], Pos) -> + case nth(Pos, Ps) of + #c_var{} -> + bsm_ensure_no_partition_after(Cs, Pos); + _ -> + 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 -- cgit v1.2.3