summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBjörn Gustavsson <bjorn@erlang.org>2019-09-19 14:20:30 +0200
committerGitHub <noreply@github.com>2019-09-19 14:20:30 +0200
commitaeb981bcf48be40027e5332831026dd440daf348 (patch)
treec10e6501988ae92093ab8174b38c4b02dde37966
parent43d8e4299d49141bab2d1145de64c3593252b073 (diff)
parent148567a6b9258ae74138566c9109d348b1768583 (diff)
downloaderlang-aeb981bcf48be40027e5332831026dd440daf348.tar.gz
Merge pull request #2387 from bjorng/bjorn/compiler/bool-opt
Move guard optimizations from v3_kernel to a new beam_ssa_bool pass
-rw-r--r--lib/compiler/src/Makefile1
-rw-r--r--lib/compiler/src/beam_kernel_to_ssa.erl22
-rw-r--r--lib/compiler/src/beam_ssa_bool.erl1701
-rw-r--r--lib/compiler/src/beam_ssa_dead.erl58
-rw-r--r--lib/compiler/src/compile.erl5
-rw-r--r--lib/compiler/src/compiler.app.src1
-rw-r--r--lib/compiler/src/v3_core.erl5
-rw-r--r--lib/compiler/src/v3_kernel.erl476
-rw-r--r--lib/compiler/src/v3_kernel.hrl2
-rw-r--r--lib/compiler/src/v3_kernel_pp.erl9
-rw-r--r--lib/compiler/test/andor_SUITE.erl30
-rw-r--r--lib/compiler/test/compile_SUITE.erl2
-rw-r--r--lib/compiler/test/guard_SUITE.erl107
-rw-r--r--lib/compiler/test/lfe_andor_SUITE.core2
-rw-r--r--lib/compiler/test/lfe_guard_SUITE.core2
-rw-r--r--lib/compiler/test/misc_SUITE.erl2
-rw-r--r--lib/compiler/test/record_SUITE.erl20
-rw-r--r--lib/compiler/test/test_lib.erl18
18 files changed, 1951 insertions, 512 deletions
diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile
index f253f31d13..071b8c9d3f 100644
--- a/lib/compiler/src/Makefile
+++ b/lib/compiler/src/Makefile
@@ -59,6 +59,7 @@ MODULES = \
beam_opcodes \
beam_peep \
beam_ssa \
+ beam_ssa_bool \
beam_ssa_bsm \
beam_ssa_codegen \
beam_ssa_dead \
diff --git a/lib/compiler/src/beam_kernel_to_ssa.erl b/lib/compiler/src/beam_kernel_to_ssa.erl
index 2406a634e6..42a3bba8b7 100644
--- a/lib/compiler/src/beam_kernel_to_ssa.erl
+++ b/lib/compiler/src/beam_kernel_to_ssa.erl
@@ -533,9 +533,9 @@ guard_clause_cg(#k_guard_clause{guard=G,body=B}, Fail, St0) ->
guard_cg(#k_protected{arg=Ts,ret=Rs,inner=Inner}, Fail, St) ->
protected_cg(Ts, Rs, Inner, Fail, St);
-guard_cg(#k_test{op=Test0,args=As,inverted=Inverted}, Fail, St0) ->
+guard_cg(#k_test{op=Test0,args=As}, Fail, St0) ->
#k_remote{mod=#k_atom{val=erlang},name=#k_atom{val=Test}} = Test0,
- test_cg(Test, Inverted, As, Fail, St0);
+ test_cg(Test, false, As, Fail, St0);
guard_cg(#k_seq{arg=Arg,body=Body}, Fail, St0) ->
{ArgIs,St1} = guard_cg(Arg, Fail, St0),
{BodyIs,St} = guard_cg(Body, Fail, St1),
@@ -552,7 +552,8 @@ test_cg(Test, Inverted, As0, Fail, St0) ->
case {Test,ssa_args(As0, St0)} of
{is_record,[Tuple,#b_literal{val=Atom}=Tag,#b_literal{val=Int}=Arity]}
when is_atom(Atom), is_integer(Int) ->
- test_is_record_cg(Inverted, Fail, Tuple, Tag, Arity, St0);
+ false = Inverted, %Assertion.
+ test_is_record_cg(Fail, Tuple, Tag, Arity, St0);
{_,As} ->
{Bool,St1} = new_ssa_var('@ssa_bool', St0),
{Succ,St} = new_label(St1),
@@ -564,7 +565,7 @@ test_cg(Test, Inverted, As0, Fail, St0) ->
{[Bif,Br,{label,Succ}],St}
end.
-test_is_record_cg(false, Fail, Tuple, TagVal, ArityVal, St0) ->
+test_is_record_cg(Fail, Tuple, TagVal, ArityVal, St0) ->
{Arity,St1} = new_ssa_var('@ssa_arity', St0),
{Tag,St2} = new_ssa_var('@ssa_tag', St1),
{Is0,St3} = make_cond_branch({bif,is_tuple}, [Tuple], Fail, St2),
@@ -574,19 +575,6 @@ test_is_record_cg(false, Fail, Tuple, TagVal, ArityVal, St0) ->
args=[Tuple,#b_literal{val=0}]},
{Is2,St} = make_cond_branch({bif,'=:='}, [Tag,TagVal], Fail, St4),
Is = Is0 ++ [GetArity] ++ Is1 ++ [GetTag] ++ Is2,
- {Is,St};
-test_is_record_cg(true, Fail, Tuple, TagVal, ArityVal, St0) ->
- {Succ,St1} = new_label(St0),
- {Arity,St2} = new_ssa_var('@ssa_arity', St1),
- {Tag,St3} = new_ssa_var('@ssa_tag', St2),
- {Is0,St4} = make_cond_branch({bif,is_tuple}, [Tuple], Succ, St3),
- GetArity = #b_set{op={bif,tuple_size},dst=Arity,args=[Tuple]},
- {Is1,St5} = make_cond_branch({bif,'=:='}, [Arity,ArityVal], Succ, St4),
- GetTag = #b_set{op=get_tuple_element,dst=Tag,
- args=[Tuple,#b_literal{val=0}]},
- {Is2,St} = make_cond_branch({bif,'=:='}, [Tag,TagVal], Succ, St5),
- Is3 = [make_uncond_branch(Fail),{label,Succ}],
- Is = Is0 ++ [GetArity] ++ Is1 ++ [GetTag] ++ Is2 ++ Is3,
{Is,St}.
%% protected_cg([Kexpr], [Ret], Fail, St) -> {[Ainstr],St}.
diff --git a/lib/compiler/src/beam_ssa_bool.erl b/lib/compiler/src/beam_ssa_bool.erl
new file mode 100644
index 0000000000..3e36d0fc47
--- /dev/null
+++ b/lib/compiler/src/beam_ssa_bool.erl
@@ -0,0 +1,1701 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2019. 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%
+%%
+%% The purpose of this pass is to optimize boolean expressions in
+%% guards. Instead of evaluating a boolean expression and finally
+%% comparing it to 'true', evaluate the expression using control flow.
+%%
+%% This pass is run directly after conversion to SSA code because some
+%% optimizations in beam_ssa_opt (especially sinking of
+%% get_tuple_element instructions) would prevent these optimizations
+%% or at least make them much more difficult to perform.
+%%
+%% As an example, take the guard:
+%%
+%% when is_integer(V0), is_atom(V1) ->
+%%
+%% The unoptimized SSA code translated to pseudo BEAM code would look
+%% like:
+%%
+%% bif is_integer V0 => Bool0
+%% bif is_atom V1 => Bool1
+%% bif and Bool0 Bool1 => Bool
+%% test Bool =:= true else goto Fail
+%% ...
+%% Fail:
+%% ...
+%%
+%% The optimized code would look like:
+%%
+%% test is_integer V0 else goto Fail
+%% test is_atom V1 else goto Fail
+%% ...
+%% Fail:
+%% ...
+%%
+%% An 'or' operation is only slightly more complicated:
+%%
+%% test is_integer V0 else goto NotFailedYet
+%% goto Success
+%%
+%% NotFailedYet:
+%% test is_atom V1 else goto Fail
+%%
+%% Success:
+%% ...
+%% Fail:
+%% ...
+%%
+%% The unoptimized SSA code for the first example looks like:
+%%
+%% 0:
+%% _2 = bif:is_integer _0
+%% _3 = bif:is_atom _1
+%% _7 = bif:'and' _2, _3
+%% @ssa_bool = succeeded _7
+%% br @ssa_bool, label 4, label 3
+%%
+%% 4:
+%% @ssa_bool:5 = bif:'=:=' _7, literal true
+%% br @ssa_bool:5, label 6, label 3
+%%
+%% 6:
+%% ret literal ok
+%%
+%% 3: Error.
+%% ...
+%%
+%% The optimized SSA code looks like:
+%%
+%% 0:
+%% _2 = bif:is_integer _0
+%% br _2, label 11, label 3
+%%
+%% 11:
+%% _3 = bif:is_atom _1
+%% br _3, label 6, label 3
+%%
+%% 6:
+%% ret literal ok
+%%
+%% 3: Error.
+%% ...
+
+-module(beam_ssa_bool).
+-export([module/2]).
+
+%% Debugging.
+-define(DEBUG, false).
+-if(?DEBUG).
+-export([dump/1]).
+-endif.
+
+-import(lists, [all/2,foldl/3,keyfind/3,last/1,partition/2,
+ reverse/1,reverse/2,sort/1]).
+
+-include("beam_ssa.hrl").
+
+-record(st, {defs=#{},
+ ldefs=#{},
+ count :: beam_ssa:label(),
+ dom,
+ uses}).
+
+-spec module(beam_ssa:b_module(), [compile:option()]) ->
+ {'ok',beam_ssa:b_module()}.
+
+module(#b_module{body=Fs0}=Module, _Opts) ->
+ Fs = [function(F) || F <- Fs0],
+ {ok,Module#b_module{body=Fs}}.
+
+function(#b_function{anno=Anno}=F) ->
+ try
+ opt_function(F)
+ catch
+ Class:Error:Stack ->
+ #{func_info:={_,Name,Arity}} = Anno,
+ io:fwrite("Function: ~w/~w\n", [Name,Arity]),
+ erlang:raise(Class, Error, Stack)
+ end.
+
+opt_function(#b_function{bs=Blocks0,cnt=Count0}=F) ->
+ {Blocks1,Count1} = pre_opt(Blocks0, Count0),
+ DefVars = interesting_defs(Blocks1),
+ if
+ map_size(DefVars) > 1 ->
+ Dom = beam_ssa:dominators(Blocks1),
+ Uses = beam_ssa:uses(Blocks1),
+ St0 = #st{defs=DefVars,count=Count1,dom=Dom,uses=Uses},
+ {Blocks,St} = bool_opt(Blocks1, St0),
+ Count = St#st.count,
+ F#b_function{bs=Blocks,cnt=Count};
+ true ->
+ %% There are no boolean operators that can be optimized in
+ %% this function.
+ F#b_function{bs=Blocks1,cnt=Count1}
+ end.
+
+%%%
+%%% Do some optimizations to help the main boolean optimization pass:
+%%%
+%%% * Remove `succeeded` instructions that can't fail after `and`,
+%%% `or`, and `not`. The main optimization pass can only optimize
+%%% boolean operators that are known not to fail.
+%%%
+%%% * Rewrite a boolean #b_switch{} to a #b_br{} if the fail label
+%%% can't be reached or is not important. (The main optimization
+%%% can't handle #b_switch{}.)
+%%%
+%%% * Simplify phi nodes, eliminating them if they only have one
+%%% value. Also annotate phi nodes that are known to evaluate
+%%% to a boolean.
+%%%
+
+-type var() :: beam_ssa:b_var().
+
+%% Note: We use the substitution map for both substitutions and type
+%% information. If the associated value for a variable is a #b_set{},
+%% it means that the value is a boolean.
+-type pre_sub_val() ::
+ beam_ssa:value() | %Value to be substituted.
+ beam_ssa:b_set() | %This variable is a boolean.
+ {'true_or_any',beam_ssa:label()} |
+ '=:='.
+
+-type pre_sub_map() :: #{'uses' => {'uses',beam_ssa:block_map() | list()},
+ var() => pre_sub_val()}.
+
+pre_opt(Blocks, Count) ->
+ Top = beam_ssa:rpo(Blocks),
+
+ %% Collect information to help the pre_opt pass to optimize
+ %% `switch` instructions.
+ Sub0 = #{uses => {uses,Blocks}},
+ Sub1 = get_phi_info(Top, Blocks, Sub0),
+ Sub = maps:remove(uses, Sub1),
+
+ %% Now do the actual optimizations.
+ Reached = gb_sets:singleton(hd(Top)),
+ pre_opt(Top, Sub, Reached, Count, Blocks).
+
+-spec get_phi_info(Ls, Blocks, Sub0) -> Sub when
+ Ls :: [beam_ssa:label()],
+ Blocks :: beam_ssa:block_map(),
+ Sub0 :: pre_sub_map(),
+ Sub :: pre_sub_map().
+
+%% get_phi_info([Label], Blocks, Sub0) -> Sub.
+%% Collect information to help us optimize `switch` instructions
+%% such as:
+%%
+%% switch SomeVar, label _, [ {literal false, _ }, {literal true, _ } ]
+%% .
+%% .
+%% .
+%% PhiVar = phi { SomeVar, _ }, { literal fail, _ }, { literal false, _}
+%% EqBool = bif:'=:=' PhiVar, literal true
+%%
+%% Here it can be seen that `SomeVar` is compared to `true`. If
+%% `SomeVar` is not `true`, it does not matter whether its value is
+%% `false` or some other value. That means that the `switch` can be
+%% replaced with a two-way `br`:
+%%
+%% NewBoolVar = bif:'=:=' SomeVar, literal true
+%% br NewBoolVar, label _, label _
+%%
+%% For this example, the value {true_or_any,LabelOfPhiBlock} will be
+%% added for the key `SomeVar` in the substitution map.
+
+get_phi_info([L|Ls], Blocks, Sub0) ->
+ Sub = get_phi_info(Ls, Blocks, Sub0),
+ #b_blk{is=Is} = map_get(L, Blocks),
+ get_phi_info_is(Is, L, Sub);
+get_phi_info([], _, Sub) -> Sub.
+
+get_phi_info_is([I|Is], From, Sub0) ->
+ Sub = get_phi_info_is(Is, From, Sub0),
+ get_phi_info_instr(I, From, Sub);
+get_phi_info_is([], _, Sub) -> Sub.
+
+get_phi_info_instr(#b_set{op={bif,'=:='},
+ args=[#b_var{}=Bool,#b_literal{val=true}]},
+ _From, Sub) ->
+ Sub#{Bool=>'=:='};
+get_phi_info_instr(#b_set{op=phi,dst=Dst,args=Args}, From, Sub0) ->
+ {Safe,Sub} =
+ case Sub0 of
+ #{Dst:='=:='} ->
+ get_phi_info_single_use(Dst, Sub0);
+ #{Dst:={true_or_any,_}} ->
+ {true,Sub0};
+ #{} ->
+ {false,Sub0}
+ end,
+ case Safe of
+ true ->
+ foldl(fun({#b_var{}=V,_}, A) ->
+ A#{V => {true_or_any,From}};
+ (_, A) -> A
+ end, Sub, Args);
+ false -> Sub
+ end;
+get_phi_info_instr(_, _, Sub) -> Sub.
+
+get_phi_info_single_use(Var, Sub) ->
+ case map_get(uses, Sub) of
+ Uses when is_map(Uses) ->
+ {case Uses of
+ #{Var:=[_]} -> true;
+ #{Var:=[_|_]} -> false
+ end,Sub};
+ {uses,Blocks} ->
+ Uses = beam_ssa:uses(Blocks),
+ get_phi_info_single_use(Var, Sub#{uses => Uses})
+ end.
+
+-spec pre_opt(Ls, Sub, Reached, Count0, Blocks0) -> {Blocks,Count} when
+ Ls :: [beam_ssa:label()],
+ Reached :: gb_sets:set(beam_ssa:label()),
+ Count0 :: beam_ssa:label(),
+ Blocks0 :: beam_ssa:block_map(),
+ Sub :: pre_sub_map(),
+ Count :: beam_ssa:label(),
+ Blocks :: beam_ssa:block_map().
+
+pre_opt([L|Ls], Sub0, Reached0, Count0, Blocks) ->
+ case gb_sets:is_member(L, Reached0) of
+ false ->
+ %% This block will never be reached.
+ pre_opt(Ls, Sub0, Reached0, Count0, maps:remove(L, Blocks));
+ true ->
+ #b_blk{is=Is0,last=Last0} = Blk0 = map_get(L, Blocks),
+ {Is,Sub} = pre_opt_is(Is0, Reached0, Sub0, []),
+ case pre_opt_terminator(Last0, Sub, Blocks) of
+ {#b_set{}=Test0,#b_br{}=Br0} ->
+ %% Here is a #b_switch{} that has been reduced to
+ %% a '=:=' followed by a two-way `br`.
+ Bool = #b_var{name={'@ssa_bool',Count0}},
+ Count = Count0 + 1,
+ Test = Test0#b_set{dst=Bool},
+ Br = Br0#b_br{bool=Bool},
+ Blk = Blk0#b_blk{is=Is++[Test],last=Br},
+ Successors = beam_ssa:successors(Blk),
+ Reached = gb_sets:union(Reached0,
+ gb_sets:from_list(Successors)),
+ pre_opt(Ls, Sub, Reached, Count, Blocks#{L:=Blk});
+ Last ->
+ Blk = Blk0#b_blk{is=Is,last=Last},
+ Successors = beam_ssa:successors(Blk),
+ Reached = gb_sets:union(Reached0,
+ gb_sets:from_list(Successors)),
+ pre_opt(Ls, Sub, Reached, Count0, Blocks#{L:=Blk})
+ end
+ end;
+pre_opt([], _, _, Count, Blocks) ->
+ {Blocks,Count}.
+
+pre_opt_is([#b_set{op=phi,dst=Dst,args=Args0}=I0|Is], Reached, Sub0, Acc) ->
+ Args1 = [{Val,From} || {Val,From} <- Args0,
+ gb_sets:is_member(From, Reached)],
+ Args = sub_args(Args1, Sub0),
+ case all_same(Args) of
+ true ->
+ %% Single value or all values are the same. We can remove
+ %% the phi node.
+ {Arg,_} = hd(Args),
+ Sub = Sub0#{Dst=>Arg},
+ pre_opt_is(Is, Reached, Sub, Acc);
+ false ->
+ case pre_is_phi_bool(Args, Sub0) of
+ true ->
+ %% The value of the phi node is always a
+ %% boolean. Update type information in the sub map
+ %% and add an annotation.
+ Anno = I0#b_set.anno,
+ I = I0#b_set{args=Args,anno=Anno#{boolean_phi=>true}},
+ Sub = Sub0#{Dst=>I},
+ pre_opt_is(Is, Reached, Sub, [I|Acc]);
+ false ->
+ I = I0#b_set{args=Args},
+ pre_opt_is(Is, Reached, Sub0, [I|Acc])
+ end
+ end;
+pre_opt_is([#b_set{op=succeeded,dst=Dst,args=Args0}=I0|Is], Reached, Sub0, Acc) ->
+ [Arg] = Args = sub_args(Args0, Sub0),
+ I = I0#b_set{args=Args},
+ case pre_is_safe_bool(Arg, Sub0) of
+ true ->
+ %% The preceding boolean operation can't fail. Get rid
+ %% of this `succeeded` instruction.
+ Sub = Sub0#{Dst=>#b_literal{val=true}},
+ pre_opt_is(Is, Reached, Sub, Acc);
+ false ->
+ pre_opt_is(Is, Reached, Sub0, [I|Acc])
+ end;
+pre_opt_is([#b_set{dst=Dst,args=Args0}=I0|Is], Reached, Sub0, Acc) ->
+ Args = sub_args(Args0, Sub0),
+ I = I0#b_set{args=Args},
+ case is_bool_expr(I) of
+ true ->
+ case pre_eval_op(I, Sub0) of
+ none ->
+ Sub = Sub0#{Dst=>I},
+ pre_opt_is(Is, Reached, Sub, [I|Acc]);
+ #b_var{}=Var ->
+ %% We must remove the 'succeeded' instruction that
+ %% follows since the variable it checks is gone.
+ [#b_set{op=succeeded,dst=SuccDst,args=[Dst]}] = Is,
+ Sub = Sub0#{Dst=>Var,SuccDst=>#b_literal{val=true}},
+ pre_opt_is([], Reached, Sub, Acc);
+ #b_literal{}=Lit ->
+ Sub = Sub0#{Dst=>Lit},
+ pre_opt_is(Is, Reached, Sub, Acc)
+ end;
+ false ->
+ pre_opt_is(Is, Reached, Sub0, [I|Acc])
+ end;
+pre_opt_is([], _Reached, Sub, Acc) ->
+ {reverse(Acc),Sub}.
+
+pre_opt_terminator(#b_br{bool=#b_literal{}}=Br, _Sub, _Blocks) ->
+ Br;
+pre_opt_terminator(#b_br{bool=Bool}=Br0, Sub, Blocks) ->
+ case beam_ssa:normalize(Br0#b_br{bool=sub_arg(Bool, Sub)}) of
+ Br0 ->
+ Br0;
+ #b_br{bool=#b_literal{val=true},succ=Next}=Br ->
+ %% See if the terminator from the successor block
+ %% can be incorporated into this block to give
+ %% more opportunities for optimization.
+ #b_blk{is=Is,last=Last} = map_get(Next, Blocks),
+ case {Is,Last} of
+ {[],#b_switch{}} ->
+ pre_opt_terminator(Last, Sub, Blocks);
+ {_,_} ->
+ Br
+ end
+ end;
+pre_opt_terminator(#b_ret{arg=Arg}=Ret, Sub, _Blocks) ->
+ Ret#b_ret{arg=sub_arg(Arg, Sub)};
+pre_opt_terminator(#b_switch{arg=Arg0,list=List}=Sw0, Sub, Blocks) ->
+ Arg = sub_arg(Arg0, Sub),
+ Sw = Sw0#b_switch{arg=Arg},
+ case sort(List) of
+ [{#b_literal{val=false},Fail},
+ {#b_literal{val=true},Succ}] ->
+ case pre_is_arg_bool(Arg, Sub) of
+ false ->
+ pre_opt_sw(Sw, Fail, Succ, Sub, Blocks);
+ true ->
+ beam_ssa:normalize(#b_br{bool=Arg,succ=Succ,fail=Fail})
+ end;
+ _ ->
+ Sw
+ end.
+
+pre_opt_sw(#b_switch{arg=Arg,fail=Fail}=Sw, False, True, Sub, Blocks) ->
+ case Sub of
+ #{Arg:={true_or_any,PhiL}} ->
+ #{Fail:=FailBlk,False:=FalseBlk,PhiL:=PhiBlk} = Blocks,
+ case {FailBlk,FalseBlk,PhiBlk} of
+ {#b_blk{is=[],last=#b_br{succ=PhiL,fail=PhiL}},
+ #b_blk{is=[],last=#b_br{succ=PhiL,fail=PhiL}},
+ #b_blk{is=[#b_set{op=phi,args=PhiArgs}|_]}} ->
+ case keyfind(False, 2, PhiArgs) of
+ {#b_literal{val=Bool},False} when Bool =/= true ->
+ %% This is an `andalso` in a guard. The code
+ %% can be simplified to a two-way `br` because
+ %% the actual value of the variable does not
+ %% matter if it is not equal to `true`.
+ DummyDst = #b_var{name=0},
+ {#b_set{op={bif,'=:='},dst=DummyDst,
+ args=[Arg,#b_literal{val=true}]},
+ #b_br{bool=DummyDst,succ=True,fail=False}};
+ {_,_} ->
+ Sw
+ end;
+ {_,_,_} ->
+ Sw
+ end;
+ #{} ->
+ Sw
+ end.
+
+pre_eval_op(#b_set{op={bif,Op},args=Args}, Sub) ->
+ case pre_are_args_bool(Args, Sub) of
+ true ->
+ case {Op,Args} of
+ {'and',[#b_literal{val=true},#b_var{}=Res]} -> Res;
+ {'and',[#b_literal{val=false}=Res,#b_var{}]} -> Res;
+ {'and',[#b_var{}=Res,#b_literal{val=true}]} -> Res;
+ {'and',[#b_var{},#b_literal{val=false}=Res]} -> Res;
+ {'or',[#b_literal{val=true}=Res,#b_var{}]} -> Res;
+ {'or',[#b_literal{val=false},#b_var{}=Res]} -> Res;
+ {'or',[#b_var{},#b_literal{val=true}=Res]} -> Res;
+ {'or',[#b_var{}=Res,#b_literal{val=false}]} -> Res;
+ _ -> none
+ end;
+ false ->
+ none
+ end.
+
+all_same([{H,_}|T]) ->
+ all(fun({E,_}) -> E =:= H end, T).
+
+pre_is_phi_bool([{#b_literal{val=Lit},_}|As], Sub) ->
+ is_boolean(Lit) andalso pre_is_phi_bool(As, Sub);
+pre_is_phi_bool([{#b_var{}=A,_}|As], Sub) ->
+ case Sub of
+ #{A:=#b_set{}} ->
+ pre_is_phi_bool(As, Sub);
+ #{} ->
+ false
+ end;
+pre_is_phi_bool([], _Sub) -> true.
+
+pre_is_safe_bool(#b_literal{}, _Sub) ->
+ true;
+pre_is_safe_bool(Var, Sub) ->
+ case Sub of
+ #{Var:=#b_set{op={bif,is_function},
+ args=[_,Arity]}} ->
+ case Arity of
+ #b_literal{val=Lit} ->
+ is_integer(Lit) andalso Lit >= 0;
+ #b_var{} ->
+ false
+ end;
+ #{Var:=#b_set{op={bif,Op},args=Args}} ->
+ Arity = length(Args),
+ erl_internal:bool_op(Op, Arity) andalso
+ pre_are_args_bool(Args, Sub);
+ #{} ->
+ false
+ end.
+
+pre_are_args_bool([A|As], Sub) ->
+ pre_is_arg_bool(A, Sub) andalso pre_are_args_bool(As, Sub);
+pre_are_args_bool([], _Sub) -> true.
+
+pre_is_arg_bool(#b_literal{val=Lit}, _Sub) ->
+ is_boolean(Lit);
+pre_is_arg_bool(#b_var{}=A, Sub) ->
+ case Sub of
+ #{A:=#b_set{}} ->
+ true;
+ #{} ->
+ false
+ end.
+
+%%%
+%%% Build a map from variable to definitions for boolean expressions
+%%% phi nodes. This map will be used by collect_bool_vars() and by
+%%% shortcut_branches().
+%%%
+
+interesting_defs(Blocks) ->
+ interesting_defs(maps:to_list(Blocks), []).
+
+interesting_defs([{L,#b_blk{is=Is}}|Bs], Acc) ->
+ interesting_defs(Bs, interesting_defs_is(Is, L, Acc));
+interesting_defs([], Acc) ->
+ maps:from_list(Acc).
+
+interesting_defs_is([#b_set{op={bif,_},dst=V}=I|Is], L, Acc) ->
+ case is_bool_expr(I) of
+ true ->
+ interesting_defs_is(Is, L, [{V,{L,I}}|Acc]);
+ false ->
+ interesting_defs_is(Is, L, Acc)
+ end;
+interesting_defs_is([#b_set{op=phi,dst=V}=Set|Is], L, Acc) ->
+ interesting_defs_is(Is, L, [{V,{L,Set}}|Acc]);
+interesting_defs_is([#b_set{}|Is], L, Acc) ->
+ interesting_defs_is(Is, L, Acc);
+interesting_defs_is([], _L, Acc) -> Acc.
+
+%%%
+%%% Search for boolean expressions to optimize.
+%%%
+%%% The main purpose of this module is to optimize guards. A guard ends in the
+%%% following instructions:
+%%%
+%%% Bool = bif:'=:=' Var, literal true
+%%% br BoolVar, label Success, label Failure
+%%%
+%%% To make sure that we'll find the end of the guard instead of some
+%%% interior '=:=' instruction we will visit the blocks in postorder.
+%%%
+
+bool_opt(Blocks, St) ->
+ bool_opt(beam_ssa:rpo(Blocks), Blocks, St).
+
+bool_opt([L|Ls], Blocks0, St0) ->
+ {Blocks,St1} = bool_opt(Ls, Blocks0, St0),
+ case Blocks of
+ #{L:=#b_blk{is=[_|_]=Is,last=#b_br{bool=#b_var{}=Bool}=Br}} ->
+ case last(Is) of
+ #b_set{op={bif,'=:='},dst=Bool,
+ args=[#b_var{},#b_literal{val=true}]} ->
+ try
+ bool_opt_rewrite(Bool, L, Br, Blocks, St1)
+ catch
+ throw:not_possible ->
+ {Blocks,St1}
+ end;
+ #b_set{} ->
+ {Blocks,St1}
+ end;
+ #{} ->
+ %% Either this block was removed by a previous successful
+ %% optimization, it is empty, or its terminator is not a
+ %% two-way `br` instruction.
+ {Blocks,St1}
+ end;
+bool_opt([], Blocks, St) ->
+ {Blocks,St}.
+
+bool_opt_rewrite(Bool, From, Br, Blocks0, St0) ->
+ TreeVars = collect_bool_vars(Bool, St0),
+ case TreeVars of
+ [Bool] ->
+ %% Only one variable means that there is nothing to
+ %% optimize. (The variable is either a function argument,
+ %% or has been defined by an instruction such as `call` or
+ %% `get_tuple_element`.)
+ not_possible();
+ [_|_] ->
+ ok
+ end,
+
+ %% Find the common dominator block for all the blocks with boolean
+ %% variables.
+ Dom = bool_opt_dom(TreeVars, St0),
+
+ %% Split out non-boolean instruction from the block that dominates
+ %% all the boolean operators. Splitting will save some work, and
+ %% it could also make more optimizations possible since phi nodes
+ %% could be difficult to handle later when they have been included
+ %% in the graph.
+ {DomPreIs,Blocks1} = split_dom_block(Dom, Blocks0),
+
+ %% Collect all blocks from the Dom block up to and including
+ %% the From block.
+ Bs = collect_digraph_blocks(Dom, From, Br, Blocks1),
+
+ %% Build a digraph from the collected blocks.
+ {Root,G0,St1} = build_digraph(Bs, Br, St0),
+
+ %% Optimize the digraph.
+ LDefs = digraph_bool_def(G0),
+ St = St1#st{ldefs=LDefs},
+ G1 = opt_digraph_top(Bool, G0, St),
+ G = shortcut_branches(Root, G1, St),
+
+ %% Make sure that every variable that is used will be defined
+ %% on every path to its use.
+ ensure_init(Root, G),
+
+ %% Delete the original blocks. This is important so that we will not
+ %% try optimize the already optimized code. That would not work
+ %% because the map of definitions in St#st.defs would not be updated
+ %% to include the newly optimized blocks.
+ DomBlk0 = map_get(Dom, Blocks1),
+ Blocks2 = maps:without([L || {L,#b_blk{}} <- Bs], Blocks1),
+
+ %% Convert the optimized digraph back to SSA code.
+ Blocks3 = digraph_to_ssa([Root], G, Blocks2),
+
+ %% Add a branch from the pre-sequence in the dominating block to
+ %% the first block of the optimized code.
+ DomBlk = DomBlk0#b_blk{is=DomPreIs,last=oneway_br(Root)},
+ Blocks = Blocks3#{Dom => DomBlk},
+ {Blocks,St#st{ldefs=#{}}}.
+
+%%%
+%%% Collect boolean variables recursively reachable from the root
+%%% boolean variable.
+%%%
+
+collect_bool_vars(RootBool, St) ->
+ #b_set{args=[#b_var{}=Var,#b_literal{}]} = get_def(RootBool, St),
+ collect_bool_vars([Var], St, [RootBool]).
+
+collect_bool_vars([V|Vs], St, Acc) ->
+ case get_def(V, St) of
+ #b_set{op=phi,anno=Anno,args=Args} ->
+ {Vars,Ls} = collect_phi_args(Args, Anno),
+ collect_bool_vars(Vars ++ Vs, St, Ls ++ Vars ++ Acc);
+ #b_set{args=Args}=I ->
+ %% This is a boolean expression.
+ Vars = [Arg || #b_var{}=Arg <- Args],
+ case is_rewritable_bool_op(I) of
+ true ->
+ %% This is a bool op ('and', 'or', or
+ %% 'not'). Recursively collect more boolean
+ %% variables from its arguments.
+ collect_bool_vars(Vars ++ Vs, St, [V|Acc]);
+ false ->
+ %% This is a comparison operator (such as `<`) or
+ %% type test. Don't visit its arguments
+ %% recursively.
+ collect_bool_vars(Vs, St, [V|Acc])
+ end;
+ none ->
+ collect_bool_vars(Vs, St, Acc)
+ end;
+collect_bool_vars([], _St, Acc) ->
+ ordsets:from_list(Acc).
+
+is_rewritable_bool_op(#b_set{op={bif,Bif}}) ->
+ %% `xor` is a bool op, but it is not practical to rewrite it.
+ case Bif of
+ 'and' -> true;
+ 'or' -> true;
+ 'not' -> true;
+ _ -> false
+ end.
+
+collect_phi_args(Args, Anno) ->
+ case is_map_key(boolean_phi, Anno) of
+ true ->
+ Vars = [V || {#b_var{}=V,_} <- Args],
+ case Vars of
+ [_|_] ->
+ {Vars,[]};
+ [] ->
+ %% This phi node only contains literal values.
+ %% Force the inclusion of referenced blocks.
+ Ls = [{block,L} || {_,L} <- Args],
+ {[],Ls}
+ end;
+ false ->
+ %% We can't rewrite phi nodes that don't return
+ %% a boolean value.
+ {[],[]}
+ end.
+
+%%%
+%%% Dominator utility functions.
+%%%
+
+bool_opt_dom(TreeVars, #st{defs=Defs,dom={DomBy,Num}}) ->
+ Ls0 = foldl(fun({block,L}, A) ->
+ [L|A];
+ (V, A) ->
+ {L,_} = map_get(V, Defs),
+ [L|A]
+ end, [], TreeVars),
+ Ls = ordsets:from_list(Ls0),
+ [Common|_] = beam_ssa:common_dominators(Ls, DomBy, Num),
+ Common.
+
+split_dom_block(L, Blocks0) ->
+ #b_blk{is=Is} = Blk0 = map_get(L, Blocks0),
+ {PreIs,TailIs} = split_dom_block_is(Is, []),
+ Blk = Blk0#b_blk{is=TailIs},
+ Blocks = Blocks0#{L:=Blk},
+ {PreIs,Blocks}.
+
+split_dom_block_is([#b_set{},#b_set{op=succeeded}]=Is, PreAcc) ->
+ {reverse(PreAcc),Is};
+split_dom_block_is([#b_set{}=I|Is]=Is0, PreAcc) ->
+ case is_bool_expr(I) of
+ true ->
+ {reverse(PreAcc),Is0};
+ false ->
+ split_dom_block_is(Is, [I|PreAcc])
+ end;
+split_dom_block_is([], PreAcc) ->
+ {reverse(PreAcc),[]}.
+
+%%%
+%%% Find and collect the blocks that should be converted to a digraph.
+%%%
+
+collect_digraph_blocks(FirstL, LastL, #b_br{succ=Succ,fail=Fail}, Blocks) ->
+ Ws = gb_sets:singleton(FirstL),
+ Seen = cerl_sets:from_list([Succ,Fail]),
+ collect_digraph_blocks(Ws, LastL, Blocks, Seen, []).
+
+collect_digraph_blocks(Ws0, LastL, Blocks, Seen0, Acc0) ->
+ case gb_sets:is_empty(Ws0) of
+ true ->
+ Acc0;
+ false ->
+ {L,Ws1} = gb_sets:take_smallest(Ws0),
+ Seen = cerl_sets:add_element(L, Seen0),
+ Blk = map_get(L, Blocks),
+ Acc = [{L,Blk}|Acc0],
+ Ws = cdb_update_workset(L, Blk, LastL, Seen, Ws1),
+ collect_digraph_blocks(Ws, LastL, Blocks, Seen, Acc)
+ end.
+
+cdb_update_workset(LastL, _Blk, LastL, _Seen, Ws) ->
+ Ws;
+cdb_update_workset(_L, Blk, _LastL, Seen, Ws) ->
+ Successors = beam_ssa:successors(Blk),
+ cdb_update_workset(Successors, Seen, Ws).
+
+cdb_update_workset([L|Ls], Seen, Ws) ->
+ case cerl_sets:is_element(L, Seen) of
+ true ->
+ cdb_update_workset(Ls, Seen, Ws);
+ false ->
+ cdb_update_workset(Ls, Seen, gb_sets:add_element(L, Ws))
+ end;
+cdb_update_workset([], _Seen, Ws) -> Ws.
+
+%%%
+%%% For the blocks from the dominating block up to the last block,
+%%% build a digraph where each vertex is an instruction. This is just
+%%% a more convenient way to represent the code, more suitable for
+%%% the optimizations we are about to do.
+%%%
+
+build_digraph(Bs, #b_br{succ=Succ,fail=Fail}, St0) ->
+ Ignore = ordsets:from_list([Succ,Fail]),
+ G0 = dg_new(),
+ {Map0,G1,St1} = build_mapping(Bs, #{}, G0, St0),
+ {Map,G2} = add_external_vertices(Ignore, Map0, G1),
+ {G,St} = build_digraph_1(Bs, G2, Map, St1),
+
+ %% Find the root node now. After we have done optimizations,
+ %% there may be more than one root node (that is, nodes without
+ %% any incident vertices).
+ [Root] = digraph_roots(G),
+ {Root,G,St}.
+
+build_mapping([{L,Blk}|Bs], Map0, G0, St0) ->
+ {Vtx,St} = new_label(St0),
+ Map = Map0#{L=>Vtx},
+ Label = case Blk of
+ #b_blk{is=[]} -> br;
+ #b_blk{} -> initial
+ end,
+ G = dg_add_vertex(G0, Vtx, Label),
+ build_mapping(Bs, Map, G, St);
+build_mapping([], Map, G, St) ->
+ {Map,G,St}.
+
+add_external_vertices([V|Vs], Map0, G0) ->
+ G = dg_add_vertex(G0, V, {external,#{}}),
+ Map = Map0#{V=>V},
+ add_external_vertices(Vs, Map, G);
+add_external_vertices([], Map, G) ->
+ {Map,G}.
+
+build_digraph_1([{L,Blk}|Bs], G0, Map, St0) ->
+ #b_blk{is=Is,last=Last} = Blk,
+ Vtx = map_get(L, Map),
+ {G,St} = build_digraph_is(Is, Last, Vtx, Map, G0, St0),
+ build_digraph_1(Bs, G, Map, St);
+build_digraph_1([], G, _Map, St) ->
+ {G,St}.
+
+build_digraph_is([#b_set{op=phi,args=Args0}=I0|Is], Last, Vtx, Map, G, St) ->
+ Args = [{V,map_get(L, Map)} || {V,L} <- Args0],
+ I = I0#b_set{args=Args},
+ build_digraph_is_1(I, Is, Last, Vtx, Map, G, St);
+build_digraph_is([#b_set{}=I|Is], Last, Vtx, Map, G, St) ->
+ case beam_ssa:no_side_effect(I) of
+ true ->
+ build_digraph_is_1(I, Is, Last, Vtx, Map, G, St);
+ false ->
+ not_possible()
+ end;
+build_digraph_is([], Last, From, Map, G0, St) ->
+ case Last of
+ #b_br{bool=#b_literal{val=true},succ=To0,fail=To0} ->
+ To = map_get(To0, Map),
+ G = dg_add_edge(G0, From, To, next),
+ {G,St};
+ #b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0} ->
+ #{Succ0:=Succ,Fail0:=Fail} = Map,
+ case dg_vertex(G0, From) of
+ #b_set{dst=Bool} ->
+ G = add_succ_fail_edges(From, Succ, Fail, G0),
+ {G,St};
+ #b_set{} ->
+ %% Wrong variable being tested. This is rare.
+ not_possible();
+ br ->
+ G1 = add_succ_fail_edges(From, Succ, Fail, G0),
+ G = dg_add_vertex(G1, From, {br,Bool}),
+ {G,St}
+ end;
+ _ ->
+ not_possible()
+ end.
+
+build_digraph_is_1(I, Is, Last, Vtx, Map, G0, St0) ->
+ G1 = dg_add_vertex(G0, Vtx, I),
+ case Is of
+ [] ->
+ build_digraph_is(Is, Last, Vtx, Map, G1, St0);
+ [_|_] ->
+ {NextVtx,St} = new_label(St0),
+ G2 = dg_add_vertex(G1, NextVtx, initial),
+ G = dg_add_edge(G2, Vtx, NextVtx, next),
+ build_digraph_is(Is, Last, NextVtx, Map, G, St)
+ end.
+
+%%%
+%%% Optimize the graph, attempting to eliminating 'and', 'or', and 'not'
+%%% instructions.
+%%%
+
+opt_digraph_top(Arg, G0, St) ->
+ I = get_def(Arg, G0, St),
+ #b_set{op={bif,'=:='},dst=Dst,
+ args=[#b_var{}=Bool,#b_literal{val=true}]} = I,
+ {br,Succ,Fail} = get_targets(Dst, G0, St),
+ G1 = ensure_single_use(Dst, G0, St),
+ G = convert_to_br_node(I, Succ, G1, St),
+ redirect_test(Bool, {fail,Fail}, G, St).
+
+do_opt_digraph([A|As], G0, St) ->
+ I = get_def(A, G0, St),
+ try opt_digraph_instr(I, G0, St) of
+ G ->
+ do_opt_digraph(As, G, St)
+ catch
+ throw:not_possible ->
+ do_opt_digraph(As, G0, St)
+ end;
+do_opt_digraph([], G, _St) -> G.
+
+opt_digraph_instr(#b_set{dst=Dst}=I, G0, St) ->
+ %% We KNOW that this node has two outgoing edges (one labeled
+ %% `succ` and one `fail`).
+ {br,Succ,Fail} = get_targets(Dst, G0, St),
+ G1 = ensure_single_use(Dst, G0, St),
+ case I of
+ #b_set{op={bif,'and'},args=Args} ->
+ G2 = convert_to_br_node(I, Succ, G1, St),
+ {First,Second} = order_args(Args, G2, St),
+ G = redirect_test(First, {fail,Fail}, G2, St),
+ redirect_test(Second, {fail,Fail}, G, St);
+ #b_set{op={bif,'or'},args=Args} ->
+ {First,Second} = order_args(Args, G1, St),
+
+ %% Here we give up the optimization if the optimization
+ %% would skip instructions that may fail. A possible
+ %% future improvement would be to hoist the failing
+ %% instructions so that they would always be executed.
+ ensure_no_failing_instructions(First, Second, G1, St),
+
+ G2 = convert_to_br_node(I, Succ, G1, St),
+ G = redirect_test(First, {succ,Succ}, G2, St),
+ redirect_test(Second, {fail,Fail}, G, St);
+ #b_set{op={bif,'xor'}} ->
+ %% Rewriting 'xor' is not practical. Fortunately,
+ %% 'xor' is almost never used in practice.
+ not_possible();
+ #b_set{op={bif,'not'},args=[#b_var{}=Bool]} ->
+ G = convert_to_br_node(I, Fail, G1, St),
+ redirect_test(Bool, {fail,Succ}, G, St);
+ #b_set{op=phi,dst=Bool} ->
+ Vtx = get_vertex(Bool, St),
+ G2 = del_out_edges(Vtx, G1),
+ G = dg_add_edge(G2, Vtx, Succ, next),
+ redirect_test(Bool, {fail,Fail}, G, St);
+ #b_set{} ->
+ G1
+ end.
+
+ensure_single_use(Bool, G, #st{uses=U}=St) ->
+ case map_get(Bool, U) of
+ [_] ->
+ G;
+ Uses ->
+ Vtx = get_vertex(Bool, St),
+ ensure_single_use_1(Bool, Vtx, Uses, G)
+ end.
+
+ensure_single_use_1(Bool, Vtx, Uses, G) ->
+ Fail = case get_targets(Vtx, G) of
+ {br,_,Fail0} -> Fail0;
+ _ -> not_possible()
+ end,
+ case partition(fun({L,#b_set{}}) when L =:= Fail -> true;
+ (_) -> false
+ end, Uses) of
+ {[_],[_]} ->
+ case dg_vertex(G, Fail) of
+ {external,Bs0} ->
+ %% The only other use of the variable Bool
+ %% is in the failure block. It can be
+ %% replaced with the literal `false`
+ %% in that block.
+ Bs = Bs0#{Bool => #b_literal{val=false}},
+ dg_add_vertex(G, Fail, {external,Bs});
+ _ ->
+ not_possible()
+ end;
+ {_,_} ->
+ not_possible()
+ end.
+
+convert_to_br_node(I, Target, G0, St) ->
+ Vtx = get_vertex(I, St),
+ G1 = del_out_edges(Vtx, G0),
+ G = dg_add_vertex(G1, Vtx, br),
+ dg_add_edge(G, Vtx, Target, next).
+
+
+%% ensure_no_failing_instructions(First, Second, G, St) -> ok.
+%% Ensure that there are no instructions that can fail that would not
+%% be executed if right-hand side of the `or` would be skipped. That
+%% means that the `or` could succeed when it was supposed to
+%% fail. Example:
+%%
+%% (element(1, T) =:= tag) or
+%% (element(10, T) =:= y)
+
+ensure_no_failing_instructions(First, Second, G, St) ->
+ Vs0 = covered(get_vertex(First, St), get_vertex(Second, St), G),
+ Vs = [{V,dg_vertex(G, V)} || V <- Vs0],
+ Failing = [P || {V,#b_set{op=succeeded}}=P <- Vs,
+ not eaten_by_phi(V, G)],
+ case Failing of
+ [] -> ok;
+ [_|_] -> not_possible()
+ end.
+
+eaten_by_phi(V, G) ->
+ {br,_,Fail} = get_targets(V, G),
+ case dg_vertex(G, Fail) of
+ br ->
+ [To] = dg_out_neighbours(G, Fail),
+ case dg_vertex(G, To) of
+ #b_set{op=phi} ->
+ true;
+ _ ->
+ false
+ end;
+ _ ->
+ false
+ end.
+
+%% order_args([Arg1,Arg2], G, St) -> {First,Second}.
+%% Order arguments for a boolean operator so that there is path in the
+%% digraph from the instruction referered to by the first operand to
+%% the instruction refered to by the second operand.
+
+order_args([#b_var{}=VarA,#b_var{}=VarB], G, St) ->
+ {VA,VB} = {get_vertex(VarA, St),get_vertex(VarB, St)},
+ case dg_is_path(G, VA, VB) of
+ true ->
+ %% Core Erlang code generated by v3_core always
+ %% has operands already in correct order.
+ {VarA,VarB};
+ false ->
+ %% Core Erlang code generated by other frontends
+ %% such as LFE may have the operands swapped.
+ true = dg_is_path(G, VB, VA), %Assertion.
+ {VarB,VarB}
+ end;
+order_args(_Args, _G, _St) ->
+ %% Literal operands. Can only happen if the Core Erlang optimization
+ %% passes have been turned off.
+ not_possible().
+
+redirect_test(Bool, SuccFail, G0, St) ->
+ V = get_vertex(Bool, St),
+ I = get_def(Bool, G0, St),
+ case I of
+ #b_set{op=phi,args=Args} ->
+ G = ensure_single_use(Bool, G0, St),
+ redirect_phi(Bool, Args, SuccFail, G, St);
+ #b_set{} ->
+ G1 = redirect_test_1(V, SuccFail, G0),
+ G = ensure_single_use(Bool, G1, St),
+ do_opt_digraph([Bool], G, St)
+ end.
+
+redirect_test_1(V, SuccFail, G) ->
+ case get_targets(V, G) of
+ {br,_Succ,Fail} ->
+ %% I have only seen this happen in code generated by LFE
+ %% (in lfe_andor_SUITE.core and lfe_guard_SUITE.core)
+ case SuccFail of
+ {fail,Fail} -> G;
+ {succ,_} -> not_possible()
+ end;
+ {br,Next} ->
+ case SuccFail of
+ {succ,Succ} ->
+ add_succ_fail_edges(V, Succ, Next, G);
+ {fail,Fail} ->
+ add_succ_fail_edges(V, Next, Fail, G)
+ end
+ end.
+
+redirect_phi(Phi, Args, SuccFail, G0, St) ->
+ PhiVtx = get_vertex(Phi, St),
+ G = dg_add_vertex(G0, PhiVtx, br),
+ redirect_phi_1(PhiVtx, sort(Args), SuccFail, G, St).
+
+redirect_phi_1(PhiVtx, [{#b_literal{val=false},FalseExit},
+ {#b_var{}=SuccBool,_BoolExit}],
+ SuccFail, G0, St) ->
+ BoolVtx = get_vertex(SuccBool, St),
+ [FalseOut] = dg_out_edges(G0, FalseExit),
+ G1 = dg_del_edge(G0, FalseOut),
+ case SuccFail of
+ {fail,Fail} ->
+ G2 = dg_add_edge(G1, FalseExit, Fail, next),
+ G = add_succ_fail_edges(BoolVtx, PhiVtx, FalseExit, G2),
+ do_opt_digraph([SuccBool], G, St);
+ {succ,Succ} ->
+ G2 = dg_add_edge(G1, FalseExit, PhiVtx, next),
+ G = add_succ_fail_edges(BoolVtx, Succ, PhiVtx, G2),
+ do_opt_digraph([SuccBool], G, St)
+ end;
+redirect_phi_1(PhiVtx, [{#b_literal{val=true},TrueExit},
+ {#b_var{}=SuccBool,_BoolExit}],
+ {fail,Fail}, G0, St) ->
+ %% This was probably an `orelse` in the source code.
+ BoolVtx = get_vertex(SuccBool, St),
+ [TrueOut] = dg_out_edges(G0, TrueExit),
+ G1 = dg_del_edge(G0, TrueOut),
+ G2 = dg_add_edge(G1, TrueExit, PhiVtx, next),
+ G = add_succ_fail_edges(BoolVtx, PhiVtx, Fail, G2),
+ %% As as future improvement, we could follow TrueExit
+ %% back to its originating boolean expression and
+ %% optimize that too.
+ do_opt_digraph([SuccBool], G, St);
+redirect_phi_1(_PhiVtx, [{#b_literal{val=false},FalseExit},
+ {#b_literal{val=true},TrueExit}],
+ SuccFail, G0, _St) ->
+ case SuccFail of
+ {fail,Fail} ->
+ [FalseOut] = dg_out_edges(G0, FalseExit),
+ G = dg_del_edge(G0, FalseOut),
+ dg_add_edge(G, FalseExit, Fail, next);
+ {succ,Succ} ->
+ [TrueOut] = dg_out_edges(G0, TrueExit),
+ G = dg_del_edge(G0, TrueOut),
+ dg_add_edge(G, TrueExit, Succ, next)
+ end;
+redirect_phi_1(_PhiVtx, _Args, _SuccFail, _G, _St) ->
+ not_possible().
+
+digraph_bool_def(G) ->
+ Vs = dg_vertices(G),
+ Ds = [{Dst,Vtx} || {Vtx,#b_set{dst=Dst}} <- Vs],
+ maps:from_list(Ds).
+
+%%%
+%%% Shortcut branches that branch to other branches.
+%%%
+%%% Shortcutting may eliminate problems with variables that
+%%% are not defined on all paths to their use. For example,
+%%% code such as the following can be made safe again:
+%%%
+%%% ensure_written(Head, false) when not Head#head.ram_file -> ...
+%%%
+%%% Shortcutting also simplifies the conversion from the digraph
+%%% back to the standard SSA format.
+%%%
+
+shortcut_branches(Vtx, G, St) ->
+ Vs = reverse(dg_reverse_postorder(G, [Vtx])),
+ do_shortcut_branches(Vs, G, St).
+
+do_shortcut_branches([V|Vs], G0, St) ->
+ case get_targets(V, G0) of
+ {br,Succ0,Fail0} ->
+ {SuccBs,FailBs} = eval_bs(V, G0, St),
+ Succ = eval_instr(Succ0, G0, SuccBs),
+ G1 = redirect_edge(V, Succ0, {succ,Succ}, G0),
+ Fail = eval_instr(Fail0, G1, FailBs),
+ G = redirect_edge(V, Fail0, {fail,Fail}, G1),
+ do_shortcut_branches(Vs, G, St);
+ {br,Next0} ->
+ Next = eval_instr(Next0, G0, #{}),
+ G = redirect_edge(V, Next0, {next,Next}, G0),
+ do_shortcut_branches(Vs, G, St);
+ none ->
+ %% This is an external vertex.
+ do_shortcut_branches(Vs, G0, St)
+ end;
+do_shortcut_branches([], G, _St) -> G.
+
+redirect_edge(_From, To, {_Label,To}, G) ->
+ G;
+redirect_edge(From, To0, {Label,To}, G0) ->
+ G = dg_del_edge(G0, {From,To0,Label}),
+ dg_add_edge(G, From, To, Label).
+
+eval_bs(Vtx, G, St) ->
+ case dg_vertex(G, Vtx) of
+ #b_set{op={bif,'=:='},args=[#b_var{}=Bool,#b_literal{val=true}]} ->
+ case get_def(Bool, G, St) of
+ #b_set{op=phi}=Phi ->
+ phi_bs(Phi);
+ _ ->
+ {#{},#{}}
+ end;
+ _ ->
+ {#{},#{}}
+ end.
+
+phi_bs(#b_set{op=phi,dst=PhiDst,args=PhiArgs}) ->
+ Literals0 = [Lit || {#b_literal{}=Lit,_} <- PhiArgs],
+ case length(Literals0) =:= length(PhiArgs) of
+ true ->
+ %% The values in the phi node are all literals.
+ Literals = ordsets:from_list(Literals0),
+ case partition(fun(#b_literal{val=Val}) ->
+ Val =:= true
+ end, Literals) of
+ {[True],[FailVal]} ->
+ %% As there is only two possible values, we can
+ %% predict the value of the phi node on both
+ %% branches.
+ SuccBs = #{PhiDst => True},
+ FailBs = #{PhiDst => FailVal},
+ {SuccBs,FailBs};
+ {_,_} ->
+ {#{},#{}}
+ end;
+ false ->
+ {#{},#{}}
+ end.
+
+eval_instr(Vtx, G, Bs) ->
+ case dg_vertex(G, Vtx) of
+ #b_set{} when map_size(Bs) =:= 0 ->
+ %% With no bindings, eval_safe_bool_expr() is
+ %% unlikely to do anything useful. If we would
+ %% call it anyway, the time complexity would be
+ %% quadratic, which would be slow for large
+ %% graphs.
+ Vtx;
+ #b_set{}=I ->
+ case is_safe_bool_expr(I) of
+ true -> eval_safe_bool_expr(I, Vtx, G, Bs);
+ false -> Vtx
+ end;
+ br ->
+ %% We can shortcut this branch unless its
+ %% target is a phi node.
+ [Next] = dg_out_neighbours(G, Vtx),
+ case dg_vertex(G, Next) of
+ #b_set{op=phi} -> Vtx;
+ _ -> eval_instr(Next, G, Bs)
+ end;
+ {br,#b_var{}} ->
+ Vtx;
+ {external,_} ->
+ Vtx
+ end.
+
+eval_safe_bool_expr(#b_set{op={bif,Bif},dst=Dst,args=Args0}, Vtx, G, Bs) ->
+ case get_targets(Vtx, G) of
+ {br,Succ,Fail} ->
+ True = #b_literal{val=true},
+ False = #b_literal{val=false},
+ Args = sub_args(Args0, Bs),
+ case eval_bif(Bif, Args) of
+ none ->
+ case {eval_instr(Succ, G, Bs#{Dst=>True}),
+ eval_instr(Fail, G, Bs#{Dst=>False})} of
+ {Same,Same} -> Same;
+ {_,_} -> Vtx
+ end;
+ true ->
+ eval_instr(Succ, G, Bs#{Dst=>True});
+ false ->
+ eval_instr(Fail, G, Bs#{Dst=>False})
+ end;
+ {br,_} ->
+ Vtx
+ end.
+
+eval_bif(Bif, Args0) ->
+ case eval_literal_args(Args0, []) of
+ none ->
+ none;
+ Args ->
+ %% We have already made sure that this expression can't
+ %% fail; thus there is no need for a `try`.
+ apply(erlang, Bif, Args)
+ end.
+
+eval_literal_args([#b_literal{val=Val}|As], Acc) ->
+ eval_literal_args(As, [Val|Acc]);
+eval_literal_args([_|_], _) ->
+ none;
+eval_literal_args([], Acc) ->
+ reverse(Acc).
+
+%%%
+%%% Check that variables are initialized on all paths and abort
+%%% the optimization if not.
+%%%
+%%% Expressions that use `or` and `not` may have added
+%%% `bif:is_boolean` instructions at the end of the boolean
+%%% expression. It can happen that the variables tested by
+%%% `bif:is_boolean` are not initialized on all paths.
+%%%
+
+ensure_init(Root, G) ->
+ Vs = dg_vertices(G),
+
+ %% Build a map of all variables that are set by instructions in
+ %% the digraph. Variables not included in this map have been
+ %% defined by code before the code in the digraph.
+ Vars = maps:from_list([{Dst,unset} ||
+ {_,#b_set{dst=Dst}} <- Vs]),
+ RPO = dg_reverse_postorder(G, [Root]),
+ ensure_init_1(RPO, G, #{Root=>Vars}).
+
+ensure_init_1([V|Vs], G, InitMaps0) ->
+ InitMaps = ensure_init_instr(V, G, InitMaps0),
+ ensure_init_1(Vs, G, InitMaps);
+ensure_init_1([], _, _) -> ok.
+
+ensure_init_instr(Vtx, G, InitMaps0) ->
+ VarMap0 = map_get(Vtx, InitMaps0),
+ case dg_vertex(G, Vtx) of
+ #b_set{dst=Dst}=I ->
+ do_ensure_init_instr(I, VarMap0, InitMaps0),
+ OutVs = dg_out_neighbours(G, Vtx),
+ VarMap = VarMap0#{Dst=>set},
+ InitMaps = InitMaps0#{Vtx:=VarMap},
+ ensure_init_successors(OutVs, G, VarMap, InitMaps);
+ _ ->
+ OutVs = dg_out_neighbours(G, Vtx),
+ ensure_init_successors(OutVs, G, VarMap0, InitMaps0)
+ end.
+
+do_ensure_init_instr(#b_set{op=phi,args=Args},
+ _VarMap, InitMaps) ->
+ _ = [ensure_init_used(Var, map_get(From, InitMaps)) ||
+ {#b_var{}=Var,From} <- Args],
+ ok;
+do_ensure_init_instr(#b_set{}=I, VarMap, _InitMaps) ->
+ Used = beam_ssa:used(I),
+ _ = [ensure_init_used(Var, VarMap) || Var <- Used],
+ ok.
+
+ensure_init_used(Var, VarMap) ->
+ case VarMap of
+ #{Var:=unset} -> not_possible();
+ #{Var:=set} -> ok;
+ #{} -> ok
+ end.
+
+ensure_init_successors([To|Vs], G, Vars0, InitMaps0) ->
+ case InitMaps0 of
+ #{To:=Vars1} ->
+ Vars = join_inits(Vars0, Vars1),
+ InitMaps = InitMaps0#{To:=Vars},
+ ensure_init_successors(Vs, G, Vars0, InitMaps);
+ #{} ->
+ InitMaps = InitMaps0#{To=>Vars0},
+ ensure_init_successors(Vs, G, Vars0, InitMaps)
+ end;
+ensure_init_successors([], _, _, InitMaps) ->
+ InitMaps.
+
+join_inits(VarMap0, VarMap1) ->
+ join_inits_1(maps:to_list(VarMap0), VarMap1).
+
+join_inits_1([{V,State0}|Vs], VarMap) ->
+ State1 = map_get(V, VarMap),
+ State = case {State0,State1} of
+ {set,set} -> set;
+ {_,_} -> unset
+ end,
+ case State =:= State1 of
+ true ->
+ join_inits_1(Vs, VarMap);
+ false ->
+ join_inits_1(Vs, VarMap#{V:=State})
+ end;
+join_inits_1([], VarMap) ->
+ VarMap.
+
+%%%
+%%% Transform the digraph back to standard SSA code.
+%%%
+
+digraph_to_ssa(Ls, G, Blocks0) ->
+ Seen = cerl_sets:new(),
+ {Blocks,_} = digraph_to_ssa(Ls, G, Blocks0, Seen),
+ Blocks.
+
+digraph_to_ssa([L|Ls], G, Blocks0, Seen0) ->
+ Seen1 = cerl_sets:add_element(L, Seen0),
+ {Blk,Successors0} = digraph_to_ssa_blk(L, G, Blocks0, []),
+ Blocks1 = Blocks0#{L=>Blk},
+ Successors = [S || S <- Successors0,
+ not cerl_sets:is_element(S, Seen1)],
+ {Blocks,Seen} = digraph_to_ssa(Successors, G, Blocks1, Seen1),
+ digraph_to_ssa(Ls, G, Blocks, Seen);
+digraph_to_ssa([], _G, Blocks, Seen) ->
+ {Blocks,Seen}.
+
+digraph_to_ssa_blk(From, G, Blocks, Acc) ->
+ case dg_vertex(G, From) of
+ #b_set{dst=Dst}=I ->
+ case get_targets(From, G) of
+ {br,Succ,Fail} ->
+ %% This is a two-way branch that ends the current block.
+ Br = #b_br{bool=Dst,succ=Succ,fail=Fail},
+ Is = reverse(Acc, [I]),
+ Blk = #b_blk{is=Is,last=Br},
+ {Blk,beam_ssa:successors(Blk)};
+ {br,Next} ->
+ case dg_in_degree(G, Next) of
+ 1 ->
+ digraph_to_ssa_blk(Next, G, Blocks, [I|Acc]);
+ _ ->
+ %% The Next node has multiple incident edge. That
+ %% means that it can't be part of the current block,
+ %% but must start a new block.
+ Br = oneway_br(Next),
+ Is = reverse(Acc, [I]),
+ Blk = #b_blk{is=Is,last=Br},
+ {Blk,beam_ssa:successors(Blk)}
+ end
+ end;
+ br ->
+ case Acc of
+ [] ->
+ %% Create an empty block.
+ {br,Next} = get_targets(From, G),
+ Blk = #b_blk{is=[],last=oneway_br(Next)},
+ {Blk,beam_ssa:successors(Blk)};
+ [_|_] ->
+ %% Finish up the block, and let the block
+ %% transfer control to the `br` node at From.
+ Br = oneway_br(From),
+ Is = reverse(Acc),
+ Blk = #b_blk{is=Is,last=Br},
+ {Blk,beam_ssa:successors(Blk)}
+ end;
+ {br,Bool} ->
+ %% This is a two-way `br` instruction. The most common
+ %% reason for its existence in the graph is that the root
+ %% node only contained a phi instruction (which was taken
+ %% out of the block before building the graph).
+ [] = Acc, %Assertion.
+ {br,Succ,Fail} = get_targets(From, G),
+ Br = #b_br{bool=Bool,succ=Succ,fail=Fail},
+ Blk = #b_blk{is=[],last=Br},
+ {Blk,beam_ssa:successors(Blk)};
+ {external,Sub} ->
+ #b_blk{is=Is0} = Blk = map_get(From, Blocks),
+ Is = [I#b_set{args=sub_args(Args0, Sub)} ||
+ #b_set{args=Args0}=I <- Is0],
+ {Blk#b_blk{is=Is},[]}
+ end.
+
+%%%
+%%% Helper functions follow.
+%%%
+
+%% get_def(Var, #st{}) -> #b_set{} | none.
+%% Find the definition for a variable. Only boolean
+%% expressions and phi nodes can be found.
+
+get_def(#b_var{}=Bool, #st{defs=Defs}) ->
+ case Defs of
+ #{Bool:={_,Def}} ->
+ Def;
+ #{} ->
+ none
+ end.
+
+%% get_def(Var, Graph, #st{}) -> #b_set{} | none.
+%% Find the definition for a variable, looking first in the digraph
+%% Graph. If it is not found there, look in the global map of
+%% interesting definitions from the entire functions.
+
+get_def(Var, G, #st{ldefs=LDefs,defs=Defs}) ->
+ case LDefs of
+ #{Var:=Vtx} ->
+ dg_vertex(G, Vtx);
+ #{} ->
+ %% Not in the graph. Returning definitions for phi nodes
+ %% outside the graph is useful for shortcut_branches().
+ case Defs of
+ #{Var:={_,Def}} -> Def;
+ #{} -> none
+ end
+ end.
+
+add_succ_fail_edges(From, Succ, Fail, G0) ->
+ G1 = dg_add_edge(G0, From, Succ, succ),
+ G = dg_add_edge(G1, From, Fail, fail),
+ case dg_out_edges(G0, From) of
+ [{From,_,next}=E] -> dg_del_edge(G, E);
+ [] -> G
+ end.
+
+get_vertex(#b_set{dst=Dst}, St) ->
+ get_vertex(Dst, St);
+get_vertex(#b_var{}=Var, #st{ldefs=LDefs}) ->
+ map_get(Var, LDefs).
+
+get_targets(Vtx, G) when is_integer(Vtx) ->
+ case dg_out_edges(G, Vtx) of
+ [{_,To,next}] ->
+ {br,To};
+ [{_,Succ,succ},{_,Fail,fail}] ->
+ {br,Succ,Fail};
+ [{_,Fail,fail},{_,Succ,succ}] ->
+ {br,Succ,Fail};
+ [] ->
+ none
+ end.
+
+get_targets(#b_var{}=Var, G, #st{ldefs=LDefs}) ->
+ get_targets(map_get(Var, LDefs), G).
+
+del_out_edges(V, G) ->
+ dg_del_edges(G, dg_out_edges(G, V)).
+
+covered(From, To, G) ->
+ Seen0 = gb_sets:empty(),
+ {yes,Seen} = covered_1(From, To, G, Seen0),
+ gb_sets:to_list(Seen).
+
+covered_1(To, To, _G, Seen) ->
+ {yes,Seen};
+covered_1(From, To, G, Seen0) ->
+ Vs0 = dg_out_neighbours(G, From),
+ Vs = [V || V <- Vs0, not gb_sets:is_member(V, Seen0)],
+ Seen = gb_sets:union(gb_sets:from_list(Vs), Seen0),
+ case Vs of
+ [] ->
+ no;
+ [_|_] ->
+ covered_list(Vs, To, G, Seen, false)
+ end.
+
+covered_list([V|Vs], To, G, Seen0, AnyFound) ->
+ case covered_1(V, To, G, Seen0) of
+ {yes,Seen} ->
+ covered_list(Vs, To, G, Seen, true);
+ no ->
+ covered_list(Vs, To, G, Seen0, AnyFound)
+ end;
+covered_list([], _, _, Seen, AnyFound) ->
+ case AnyFound of
+ true -> {yes,Seen};
+ false -> no
+ end.
+
+digraph_roots(G) ->
+ digraph_roots_1(dg_vertices(G), G).
+
+digraph_roots_1([{V,_}|Vs], G) ->
+ case dg_in_degree(G, V) of
+ 0 ->
+ [V|digraph_roots_1(Vs, G)];
+ _ ->
+ digraph_roots_1(Vs, G)
+ end;
+digraph_roots_1([], _G) -> [].
+
+not_possible() ->
+ throw(not_possible).
+
+new_label(#st{count=Count}=St) ->
+ {Count,St#st{count=Count+1}}.
+
+sub_args(Args, Sub) ->
+ [sub_arg(Arg, Sub) || Arg <- Args].
+
+sub_arg({#b_var{}=Arg,From}, Sub) when is_integer(From) ->
+ {do_sub_arg(Arg, Sub),From};
+sub_arg(#b_var{}=Arg, Sub) ->
+ do_sub_arg(Arg, Sub);
+sub_arg(#b_remote{mod=Mod,name=Name}=Rem, Sub) ->
+ Rem#b_remote{mod=do_sub_arg(Mod, Sub),
+ name=do_sub_arg(Name, Sub)};
+sub_arg(Arg, _Sub) -> Arg.
+
+do_sub_arg(#b_var{}=Old, Sub) ->
+ case Sub of
+ #{Old:=#b_literal{}=New} -> New;
+ #{Old:=#b_var{}=New} -> New;
+ #{} -> Old
+ end;
+do_sub_arg(#b_literal{}=Old, _Sub) -> Old.
+
+is_bool_expr(#b_set{op={bif,Op},args=Args}) ->
+ Arity = length(Args),
+ erl_internal:comp_op(Op, Arity) orelse
+ erl_internal:new_type_test(Op, Arity) orelse
+ erl_internal:bool_op(Op, Arity);
+is_bool_expr(_) -> false.
+
+%% Test whether the expression always succeeds and
+%% always returns a boolean.
+is_safe_bool_expr(#b_set{op={bif,Op},args=Args}) ->
+ Arity = length(Args),
+ erl_internal:comp_op(Op, Arity) orelse
+ erl_internal:new_type_test(Op, Arity);
+is_safe_bool_expr(#b_set{}) -> false.
+
+oneway_br(To) ->
+ #b_br{bool=#b_literal{val=true},succ=To,fail=To}.
+
+%%%
+%%% Digraph data type. Similar to the digraph module, but provides a
+%%% functional API. The functional API allows us to revert to a
+%%% previous version of the digraph when an optimization that may have
+%%% damaged the digraph has failed.
+%%%
+
+-record(dg, {vs,
+ in_es,
+ out_es}).
+
+dg_new() ->
+ Vs = #{},
+ EsMap = #{},
+ #dg{vs=Vs,in_es=EsMap,out_es=EsMap}.
+
+dg_add_vertex(Dg, V, Label) ->
+ #dg{in_es=InEsMap0,out_es=OutEsMap0,vs=Vs0} = Dg,
+ InEsMap = dg__init_edge_map(V, InEsMap0),
+ OutEsMap = dg__init_edge_map(V, OutEsMap0),
+ Vs = Vs0#{V=>Label},
+ Dg#dg{vs=Vs,in_es=InEsMap,out_es=OutEsMap}.
+
+dg_add_edge(Dg, From, To, Label) ->
+ #dg{in_es=InEsMap0,out_es=OutEsMap0} = Dg,
+ Name = {From,To,Label},
+ InEsMap = dg__edge_map_add(To, Name, InEsMap0),
+ OutEsMap = dg__edge_map_add(From, Name, OutEsMap0),
+ Dg#dg{in_es=InEsMap,out_es=OutEsMap}.
+
+dg_out_edges(#dg{out_es=OutEsMap}, V) ->
+ map_get(V, OutEsMap).
+
+dg_out_neighbours(#dg{out_es=OutEsMap}, V) ->
+ [To || {_,To,_} <- map_get(V, OutEsMap)].
+
+dg_del_edge(Dg, {From,To,_}=E) ->
+ #dg{in_es=InEsMap0,out_es=OutEsMap0} = Dg,
+ InEsMap = dg__edge_map_del(To, E, InEsMap0),
+ OutEsMap = dg__edge_map_del(From, E, OutEsMap0),
+ Dg#dg{in_es=InEsMap,out_es=OutEsMap}.
+
+dg_del_edges(G, Es) when is_list(Es) ->
+ foldl(fun(E, A) -> dg_del_edge(A, E) end, G, Es).
+
+dg_in_degree(#dg{in_es=InEsMap}, V) ->
+ length(map_get(V, InEsMap)).
+
+dg_vertex(#dg{vs=Vs}, V) ->
+ map_get(V, Vs).
+
+dg_vertices(#dg{vs=Vs}) ->
+ maps:to_list(Vs).
+
+dg_is_path(G, From, To) ->
+ Seen = cerl_sets:new(),
+ try
+ _ = dg__is_path([From], To, G, Seen),
+ false
+ catch
+ throw:true ->
+ true
+ end.
+
+dg_reverse_postorder(G, Vs) ->
+ Seen = cerl_sets:new(),
+ {RPO,_} = dg__rpo(Vs, G, Seen, []),
+ RPO.
+
+dg__rpo([V|Vs], G, Seen0, Acc0) ->
+ case cerl_sets:is_element(V, Seen0) of
+ true ->
+ dg__rpo(Vs, G, Seen0, Acc0);
+ false ->
+ Seen1 = cerl_sets:add_element(V, Seen0),
+ Successors = dg_out_neighbours(G, V),
+ {Acc,Seen} = dg__rpo(Successors, G, Seen1, Acc0),
+ dg__rpo(Vs, G, Seen, [V|Acc])
+ end;
+dg__rpo([], _, Seen, Acc) ->
+ {Acc,Seen}.
+
+dg__is_path([To|_], To, _G, _Seen) ->
+ throw(true);
+dg__is_path([V|Vs], To, G, Seen0) ->
+ case cerl_sets:is_element(V, Seen0) of
+ true ->
+ dg__is_path(Vs, To, G, Seen0);
+ false ->
+ Seen1 = cerl_sets:add_element(V, Seen0),
+ Successors = dg_out_neighbours(G, V),
+ Seen = dg__is_path(Successors, To, G, Seen1),
+ dg__is_path(Vs, To, G, Seen)
+ end;
+dg__is_path([], _To, _G, Seen) ->
+ Seen.
+
+dg__init_edge_map(V, EsMap) ->
+ case is_map_key(V, EsMap) of
+ true ->
+ EsMap;
+ false ->
+ EsMap#{V=>ordsets:new()}
+ end.
+
+dg__edge_map_add(V, E, EsMap) ->
+ Es0 = map_get(V, EsMap),
+ Es = ordsets:add_element(E, Es0),
+ EsMap#{V:=Es}.
+
+dg__edge_map_del(V, E, EsMap) ->
+ Es0 = map_get(V, EsMap),
+ Es = Es0 -- [E],
+ EsMap#{V:=Es}.
+
+-if(?DEBUG).
+
+-spec dump(any()) -> any().
+dump(G) ->
+ dump_topsort(topsort(G), G),
+ io:nl(),
+ G.
+
+topsort(G) ->
+ Roots = digraph_roots(G),
+ dg_reverse_postorder(G, Roots).
+
+dump_topsort([V|Vs], G) ->
+ Info = dg_vertex(G, V),
+ Out = dg_out_neighbours(G, V),
+ io:format("~p ~p ~w\n", [V,Info,Out]),
+ dump_topsort(Vs, G);
+dump_topsort([], _G) -> ok.
+
+-endif.
diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl
index 55ded77d43..35785861a2 100644
--- a/lib/compiler/src/beam_ssa_dead.erl
+++ b/lib/compiler/src/beam_ssa_dead.erl
@@ -28,7 +28,7 @@
-include("beam_ssa.hrl").
-import(lists, [append/1,keymember/3,last/1,member/2,
- takewhile/2,reverse/1]).
+ reverse/1,sort/1,takewhile/2]).
-type used_vars() :: #{beam_ssa:label():=cerl_sets:set(beam_ssa:var_name())}.
@@ -141,19 +141,34 @@ shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br,
%% No change.
Br
end;
-shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, From, Bs, St) ->
- List = shortcut_switch(List0, Bool, From, Bs, St),
- beam_ssa:normalize(Sw#b_switch{list=List});
+shortcut_terminator(#b_switch{arg=Bool,fail=Fail0,list=List0}=Sw,
+ _Is, From, Bs, St) ->
+ Fail = shortcut_sw_fail(Fail0, List0, Bool, From, Bs, St),
+ List = shortcut_sw_list(List0, Bool, From, Bs, St),
+ beam_ssa:normalize(Sw#b_switch{fail=Fail,list=List});
shortcut_terminator(Last, _Is, _Bs, _From, _St) ->
Last.
-shortcut_switch([{Lit,L0}|T], Bool, From, Bs, St0) ->
+shortcut_sw_fail(Fail0, List, Bool, From, Bs, St0) ->
+ case sort(List) of
+ [{#b_literal{val=false},_},
+ {#b_literal{val=true},_}] ->
+ RelOp = {{'not',is_boolean},Bool},
+ St = St0#st{rel_op=RelOp,target=one_way},
+ #b_br{bool=#b_literal{val=true},succ=Fail} =
+ shortcut(Fail0, From, Bs, St),
+ Fail;
+ _ ->
+ Fail0
+ end.
+
+shortcut_sw_list([{Lit,L0}|T], Bool, From, Bs, St0) ->
RelOp = {'=:=',Bool,Lit},
St = St0#st{rel_op=RelOp},
#b_br{bool=#b_literal{val=true},succ=L} =
shortcut(L0, From, bind_var(Bool, Lit, Bs), St#st{target=one_way}),
- [{Lit,L}|shortcut_switch(T, Bool, From, Bs, St0)];
-shortcut_switch([], _, _, _, _) -> [].
+ [{Lit,L}|shortcut_sw_list(T, Bool, From, Bs, St0)];
+shortcut_sw_list([], _, _, _, _) -> [].
shortcut(L, _From, Bs, #st{rel_op=none,target=one_way}) when map_size(Bs) =:= 0 ->
%% There is no way that we can find a suitable branch, because there is no
@@ -423,11 +438,22 @@ eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], From, Bs0, St) ->
Val = get_phi_arg(Args, From),
Bs = bind_var(Dst, Val, Bs0),
eval_is(Is, From, Bs, St);
+eval_is([#b_set{op=succeeded,dst=Dst,args=[Var]}], _From, Bs, _St) ->
+ case Bs of
+ #{Var:=failed} ->
+ bind_var(Dst, #b_literal{val=false}, Bs);
+ #{Var:=#b_literal{}} ->
+ bind_var(Dst, #b_literal{val=true}, Bs);
+ #{} ->
+ Bs
+ end;
eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], From, Bs, St) ->
I = sub(I0, Bs),
case eval_bif(I, St) of
#b_literal{}=Val ->
eval_is(Is, From, bind_var(Dst, Val, Bs), St);
+ failed ->
+ eval_is(Is, From, bind_var(Dst, failed, Bs), St);
none ->
eval_is(Is, From, Bs, St)
end;
@@ -530,6 +556,8 @@ bind_var_if_used(L, Var, Val0, Bs, #st{us=Us}) ->
Bs
end.
+bind_var(Var, failed, Bs) ->
+ Bs#{Var=>failed};
bind_var(Var, Val0, Bs) ->
Val = get_value(Val0, Bs),
Bs#{Var=>Val}.
@@ -675,7 +703,7 @@ eval_rel_op(_Bif, _Args, #st{rel_op=none}) ->
eval_rel_op(Bif, Args, #st{rel_op=Prev}) ->
case normalize_op(Bif, Args) of
none ->
- none;
+ eval_boolean(Prev, Bif, Args);
RelOp ->
case will_succeed(Prev, RelOp) of
yes -> #b_literal{val=true};
@@ -684,6 +712,17 @@ eval_rel_op(Bif, Args, #st{rel_op=Prev}) ->
end
end.
+eval_boolean({{'not',is_boolean},Var}, {bif,'not'}, [Var]) ->
+ failed;
+eval_boolean({{'not',is_boolean},Var}, {bif,Op}, Args)
+ when Op =:= 'and'; Op =:= 'or' ->
+ case member(Var, Args) of
+ true -> failed;
+ false -> none
+ end;
+eval_boolean(_, _, _) ->
+ none.
+
%% will_succeed(PrevCondition, Condition) -> yes | no | maybe
%% PrevCondition is a condition known to be true. This function
%% will tell whether Condition will succeed.
@@ -702,6 +741,9 @@ will_succeed({_,_}=Same, {_,_}=Same) ->
yes;
will_succeed({Test1,Var}, {Test2,Var}) ->
will_succeed_test(Test1, Test2);
+will_succeed({{'not',is_boolean},Var}, {'=:=',Var,#b_literal{val=Lit}})
+ when is_boolean(Lit) ->
+ no;
will_succeed({_,_}, {_,_}) ->
maybe;
will_succeed({_,_}, {_,_,_}) ->
diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl
index 21d67f5649..5e0ea9247e 100644
--- a/lib/compiler/src/compile.erl
+++ b/lib/compiler/src/compile.erl
@@ -837,7 +837,9 @@ kernel_passes() ->
{iff,dssa,{listing,"ssa"}},
{iff,ssalint,{pass,beam_ssa_lint}},
{delay,
- [{unless,no_share_opt,{pass,beam_ssa_share}},
+ [{unless,no_bool_opt,{pass,beam_ssa_bool}},
+ {iff,dbool,{listing,"bool"}},
+ {unless,no_share_opt,{pass,beam_ssa_share}},
{iff,dssashare,{listing,"ssashare"}},
{iff,ssalint,{pass,beam_ssa_lint}},
{unless,no_bsm_opt,{pass,beam_ssa_bsm}},
@@ -2107,6 +2109,7 @@ pre_load() ->
beam_opcodes,
beam_peep,
beam_ssa,
+ beam_ssa_bool,
beam_ssa_bsm,
beam_ssa_codegen,
beam_ssa_dead,
diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src
index 092757ae65..4185627aee 100644
--- a/lib/compiler/src/compiler.app.src
+++ b/lib/compiler/src/compiler.app.src
@@ -35,6 +35,7 @@
beam_opcodes,
beam_peep,
beam_ssa,
+ beam_ssa_bool,
beam_ssa_bsm,
beam_ssa_codegen,
beam_ssa_dead,
diff --git a/lib/compiler/src/v3_core.erl b/lib/compiler/src/v3_core.erl
index 007a0247f4..68da63299d 100644
--- a/lib/compiler/src/v3_core.erl
+++ b/lib/compiler/src/v3_core.erl
@@ -420,8 +420,11 @@ gexpr_test(E0, Bools0, St0) ->
%% Generate "top-level" test and argument calls.
case E1 of
#icall{anno=Anno,module=#c_literal{val=erlang},name=#c_literal{val=N},args=As} ->
+ %% Note that erl_expand_records has renamed type
+ %% tests to the new names; thus, float/1 as a type
+ %% test will now be named is_float/1.
Ar = length(As),
- case erl_internal:type_test(N, Ar) orelse
+ case erl_internal:new_type_test(N, Ar) orelse
erl_internal:comp_op(N, Ar) orelse
erl_internal:bool_op(N, Ar) of
true -> {E1,Eps0,Bools0,St1};
diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl
index 49fb66126f..3f7f7f95d6 100644
--- a/lib/compiler/src/v3_kernel.erl
+++ b/lib/compiler/src/v3_kernel.erl
@@ -85,7 +85,7 @@
map/2,mapfoldl/3,member/2,
keyfind/3,keyreplace/4,
last/1,partition/2,reverse/1,
- splitwith/2,sort/1]).
+ splitwith/2]).
-import(ordsets, [add_element/2,del_element/2,union/2,union/1,subtract/2]).
-import(cerl, [c_tuple/1]).
@@ -111,7 +111,6 @@ copy_anno(Kdst, Ksrc) ->
-record(iclause, {anno=[],isub,osub,pats,guard,body}).
-record(ireceive_accept, {anno=[],arg}).
-record(ireceive_next, {anno=[],arg}).
--record(ignored, {anno=[]}).
-type warning() :: term(). % XXX: REFINE
@@ -206,478 +205,9 @@ guard(G0, Sub, St0) ->
{G1,St1} = wrap_guard(G0, St0),
{Ge0,Pre,St2} = expr(G1, Sub, St1),
{Ge1,St3} = gexpr_test(Ge0, St2),
- {Ge,St} = guard_opt(Ge1, St3),
+ {Ge,St} = {Ge1,St3},
{pre_seq(Pre, Ge),St}.
-%% guard_opt(Kexpr, State) -> {Kexpr,State}.
-%% Optimize the Kexpr for the guard. Instead of evaluating a boolean
-%% expression comparing it to 'true' in a final #k_test{},
-%% replace BIF calls with #k_test{} in the expression.
-%%
-%% As an example, take the guard:
-%%
-%% when is_integer(V0), is_atom(V1) ->
-%%
-%% The unoptimized Kexpr translated to pseudo BEAM assembly
-%% code would look like:
-%%
-%% bif is_integer V0 => Bool0
-%% bif is_atom V1 => Bool1
-%% bif and Bool0 Bool1 => Bool
-%% test Bool =:= true else goto Fail
-%% ...
-%% Fail:
-%% ...
-%%
-%% The optimized code would look like:
-%%
-%% test is_integer V0 else goto Fail
-%% test is_atom V1 else goto Fail
-%% ...
-%% Fail:
-%% ...
-%%
-%% An 'or' operation is only slightly more complicated:
-%%
-%% test is_integer V0 else goto NotFailedYet
-%% goto Success
-%%
-%% NotFailedYet:
-%% test is_atom V1 else goto Fail
-%%
-%% Success:
-%% ...
-%% Fail:
-%% ...
-
-guard_opt(G, St0) ->
- {Root,Forest0,St1} = make_forest(G, St0),
- {Exprs,Forest,St} = rewrite_bool(Root, Forest0, false, St1),
- E = forest_pre_seq(Exprs, Forest),
- {G#k_try{arg=E},St}.
-
-%% rewrite_bool(Kexpr, Forest, Inv, St) -> {[Kexpr],Forest,St}.
-%% Rewrite Kexpr to use #k_test{} operations instead of comparison
-%% and type test BIFs.
-%%
-%% If Kexpr is a #k_test{} operation, the call will always
-%% succeed. Otherwise, a 'not_possible' exception will be
-%% thrown if Kexpr cannot be rewritten.
-
-rewrite_bool(#k_test{op=#k_remote{mod=#k_atom{val=erlang},name=#k_atom{val='=:='}},
- args=[#k_var{}=V,#k_atom{val=true}]}=Test, Forest0, Inv, St0) ->
- try rewrite_bool_var(V, Forest0, Inv, St0) of
- {_,_,_}=Res ->
- Res
- catch
- throw:not_possible ->
- {[Test],Forest0,St0}
- end;
-rewrite_bool(#k_test{op=#k_remote{mod=#k_atom{val=erlang},name=#k_atom{val='=:='}},
- args=[#k_var{}=V,#k_atom{val=false}]}=Test, Forest0, Inv, St0) ->
- try rewrite_bool_var(V, Forest0, not Inv, St0) of
- {_,_,_}=Res ->
- Res
- catch
- throw:not_possible ->
- {[Test],Forest0,St0}
- end;
-rewrite_bool(#k_test{op=#k_remote{mod=#k_atom{val=erlang},name=#k_atom{val='=:='}},
- args=[#k_atom{val=V1},#k_atom{val=V2}]}, Forest0, false, St0) ->
- case V1 =:= V2 of
- true ->
- {[make_test(is_boolean, [#k_atom{val=true}])],Forest0,St0};
- false ->
- {[make_failing_test()],Forest0,St0}
- end;
-rewrite_bool(#k_test{}=Test, Forest, false, St) ->
- {[Test],Forest,St};
-rewrite_bool(#k_try{vars=[#k_var{name=X}],body=#k_var{name=X},
- handler=#k_atom{val=false},ret=[]}=Prot,
- Forest0, Inv, St0) ->
- {Root,Forest1,St1} = make_forest(Prot, Forest0, St0),
- {Exprs,Forest2,St} = rewrite_bool(Root, Forest1, Inv, St1),
- InnerForest = maps:without(maps:keys(Forest0), Forest2),
- Forest = maps:without(maps:keys(InnerForest), Forest2),
- E = forest_pre_seq(Exprs, InnerForest),
- {[Prot#k_try{arg=E}],Forest,St};
-rewrite_bool(#k_match{body=Body,ret=[]}, Forest, Inv, St) ->
- rewrite_match(Body, Forest, Inv, St);
-rewrite_bool(Other, Forest, Inv, St) ->
- case extract_bif(Other) of
- {Name,Args} ->
- rewrite_bif(Name, Args, Forest, Inv, St);
- error ->
- throw(not_possible)
- end.
-
-%% rewrite_bool_var(Var, Forest, Inv, St) -> {[Kexpr],Forest,St}.
-%% Rewrite the boolean expression whose key in Forest is
-%% given by Var. Throw a 'not_possible' expression if something
-%% prevents the rewriting.
-
-rewrite_bool_var(Arg, Forest0, Inv, St) ->
- {Expr,Forest} = forest_take_expr(Arg, Forest0),
- rewrite_bool(Expr, Forest, Inv, St).
-
-%% rewrite_bool_args([Kexpr], Forest, Inv, St) -> {[[Kexpr]],Forest,St}.
-%% Rewrite each Kexpr in the list. The input Kexpr should be variables
-%% or boolean values. Throw a 'not_possible' expression if something
-%% prevents the rewriting.
-%%
-%% This function is suitable for handling the arguments for both
-%% 'and' and 'or'.
-
-rewrite_bool_args([#k_atom{val=B}=A|Vs], Forest0, false=Inv, St0) when is_boolean(B) ->
- {Tail,Forest1,St1} = rewrite_bool_args(Vs, Forest0, Inv, St0),
- Bif = make_bif('=:=', [A,#k_atom{val=true}]),
- {Exprs,Forest,St} = rewrite_bool(Bif, Forest1, Inv, St1),
- {[Exprs|Tail],Forest,St};
-rewrite_bool_args([#k_var{}=Var|Vs], Forest0, false=Inv, St0) ->
- {Tail,Forest1,St1} = rewrite_bool_args(Vs, Forest0, Inv, St0),
- {Exprs,Forest,St} =
- case is_bool_expr(Var, Forest0) of
- true ->
- rewrite_bool_var(Var, Forest1, Inv, St1);
- false ->
- Bif = make_bif('=:=', [Var,#k_atom{val=true}]),
- rewrite_bool(Bif, Forest1, Inv, St1)
- end,
- {[Exprs|Tail],Forest,St};
-rewrite_bool_args([_|_], _Forest, _Inv, _St) ->
- throw(not_possible);
-rewrite_bool_args([], Forest, _Inv, St) ->
- {[],Forest,St}.
-
-%% rewrite_bif(Name, [Kexpr], Forest, Inv, St) -> {[Kexpr],Forest,St}.
-%% Rewrite a BIF. Throw a 'not_possible' expression if something
-%% prevents the rewriting.
-
-rewrite_bif('or', Args, Forest, true, St) ->
- rewrite_not_args('and', Args, Forest, St);
-rewrite_bif('and', Args, Forest, true, St) ->
- rewrite_not_args('or', Args, Forest, St);
-rewrite_bif('and', [#k_atom{val=Val},Arg], Forest0, Inv, St0) ->
- false = Inv, %Assertion.
- case Val of
- true ->
- %% The result only depends on Arg.
- rewrite_bool_var(Arg, Forest0, Inv, St0);
- _ ->
- %% Will fail. There is no need to evalute the expression
- %% represented by Arg. Take it out from the forest and
- %% discard the expression.
- Failing = make_failing_test(),
- try rewrite_bool_var(Arg, Forest0, Inv, St0) of
- {_,Forest,St} ->
- {[Failing],Forest,St}
- catch
- throw:not_possible ->
- try forest_take_expr(Arg, Forest0) of
- {_,Forest} ->
- {[Failing],Forest,St0}
- catch
- throw:not_possible ->
- %% Arg is probably a variable bound in an
- %% outer scope.
- {[Failing],Forest0,St0}
- end
- end
- end;
-rewrite_bif('and', [Arg,#k_atom{}=Atom], Forest, Inv, St) ->
- false = Inv, %Assertion.
- rewrite_bif('and', [Atom,Arg], Forest, Inv, St);
-rewrite_bif('and', Args, Forest0, Inv, St0) ->
- false = Inv, %Assertion.
- {[Es1,Es2],Forest,St} = rewrite_bool_args(Args, Forest0, Inv, St0),
- {Es1 ++ Es2,Forest,St};
-rewrite_bif('or', Args, Forest0, Inv, St0) ->
- false = Inv, %Assertion.
- {[First,Then],Forest,St} = rewrite_bool_args(Args, Forest0, Inv, St0),
- Alt = make_alt(First, Then),
- {[Alt],Forest,St};
-rewrite_bif('xor', [_,_], _Forest, _Inv, _St) ->
- %% Rewriting 'xor' is not practical. Fortunately, 'xor' is
- %% almost never used in practice.
- throw(not_possible);
-rewrite_bif('not', [Arg], Forest0, Inv, St) ->
- {Expr,Forest} = forest_take_expr(Arg, Forest0),
- rewrite_bool(Expr, Forest, not Inv, St);
-rewrite_bif(Op, Args, Forest, Inv, St) ->
- case is_test(Op, Args) of
- true ->
- rewrite_bool(make_test(Op, Args, Inv), Forest, false, St);
- false ->
- throw(not_possible)
- end.
-
-rewrite_not_args(Op, [A0,B0], Forest0, St0) ->
- {A,Forest1,St1} = rewrite_not_args_1(A0, Forest0, St0),
- {B,Forest2,St2} = rewrite_not_args_1(B0, Forest1, St1),
- rewrite_bif(Op, [A,B], Forest2, false, St2).
-
-rewrite_not_args_1(Arg, Forest, St) ->
- Not = make_bif('not', [Arg]),
- forest_add_expr(Not, Forest, St).
-
-%% rewrite_match(Kvar, TypeClause, Forest, Inv, St) ->
-%% {[Kexpr],Forest,St}.
-%% Try to rewrite a #k_match{} originating from an 'andalso' or an 'orelse'.
-
-rewrite_match(#k_alt{first=First,then=Then}, Forest, Inv, St) ->
- case {First,Then} of
- {#k_select{var=#k_var{name=V}=Var,types=[TypeClause]},#k_var{name=V}} ->
- rewrite_match_1(Var, TypeClause, Forest, Inv, St);
- {_,_} ->
- throw(not_possible)
- end.
-
-rewrite_match_1(Var, #k_type_clause{values=Cs0}, Forest0, Inv, St0) ->
- Cs = sort([{Val,B} || #k_val_clause{val=#k_atom{val=Val},body=B} <- Cs0]),
- case Cs of
- [{false,False},{true,True}] ->
- rewrite_match_2(Var, False, True, Forest0, Inv, St0);
- _ ->
- throw(not_possible)
- end.
-
-rewrite_match_2(Var, False, #k_atom{val=true}, Forest0, Inv, St0) ->
- %% Originates from an 'orelse'.
- case False of
- #k_atom{val=NotBool} when not is_boolean(NotBool) ->
- rewrite_bool(Var, Forest0, Inv, St0);
- _ ->
- {CodeVar,Forest1,St1} = add_protected_expr(False, Forest0, St0),
- rewrite_bif('or', [Var,CodeVar], Forest1, Inv, St1)
- end;
-rewrite_match_2(Var, #k_atom{val=false}, True, Forest0, Inv, St0) ->
- %% Originates from an 'andalso'.
- {CodeVar,Forest1,St1} = add_protected_expr(True, Forest0, St0),
- rewrite_bif('and', [Var,CodeVar], Forest1, Inv, St1);
-rewrite_match_2(_V, _, _, _Forest, _Inv, _St) ->
- throw(not_possible).
-
-%% is_bool_expr(#k_var{}, Forest) -> true|false.
-%% Return true if the variable refers to a boolean expression
-%% that does not need an explicit '=:= true' test.
-
-is_bool_expr(V, Forest) ->
- case forest_peek_expr(V, Forest) of
- error ->
- %% Defined outside of the guard. We can't know.
- false;
- Expr ->
- case extract_bif(Expr) of
- {Name,Args} ->
- is_test(Name, Args) orelse
- erl_internal:bool_op(Name, length(Args));
- error ->
- %% Not a BIF. Should be possible to rewrite
- %% to a boolean. Definitely does not need
- %% a '=:= true' test.
- true
- end
- end.
-
-make_bif(Op, Args) ->
- #k_bif{op=#k_remote{mod=#k_atom{val=erlang},
- name=#k_atom{val=Op},
- arity=length(Args)},
- args=Args}.
-
-extract_bif(#k_bif{op=#k_remote{mod=#k_atom{val=erlang},
- name=#k_atom{val=Name}},
- args=Args}) ->
- {Name,Args};
-extract_bif(_) ->
- error.
-
-%% make_alt(First, Then) -> KMatch.
-%% Make a #k_alt{} within a #k_match{} to implement
-%% 'or' or 'orelse'.
-
-make_alt(First0, Then0) ->
- First1 = pre_seq(droplast(First0), last(First0)),
- Then1 = pre_seq(droplast(Then0), last(Then0)),
- First2 = make_protected(First1),
- Then2 = make_protected(Then1),
- Body = #ignored{},
- First3 = #k_guard_clause{guard=First2,body=Body},
- Then3 = #k_guard_clause{guard=Then2,body=Body},
- First = #k_guard{clauses=[First3]},
- Then = #k_guard{clauses=[Then3]},
- Alt = #k_alt{first=First,then=Then},
- #k_match{vars=[],body=Alt}.
-
-add_protected_expr(#k_atom{}=Atom, Forest, St) ->
- {Atom,Forest,St};
-add_protected_expr(#k_var{}=Var, Forest, St) ->
- {Var,Forest,St};
-add_protected_expr(E0, Forest, St) ->
- E = make_protected(E0),
- forest_add_expr(E, Forest, St).
-
-make_protected(#k_try{}=Try) ->
- Try;
-make_protected(B) ->
- #k_try{arg=B,vars=[#k_var{name=''}],body=#k_var{name=''},
- handler=#k_atom{val=false}}.
-
-make_failing_test() ->
- make_test(is_boolean, [#k_atom{val=fail}]).
-
-make_test(Op, Args) ->
- make_test(Op, Args, false).
-
-make_test(Op, Args, Inv) ->
- Remote = #k_remote{mod=#k_atom{val=erlang},
- name=#k_atom{val=Op},
- arity=length(Args)},
- #k_test{op=Remote,args=Args,inverted=Inv}.
-
-is_test(Op, Args) ->
- A = length(Args),
- erl_internal:new_type_test(Op, A) orelse erl_internal:comp_op(Op, A).
-
-%% make_forest(Kexpr, St) -> {RootKexpr,Forest,St}.
-%% Build a forest out of Kexpr. RootKexpr is the final expression
-%% nested inside Kexpr.
-
-make_forest(G, St) ->
- make_forest_1(G, #{}, 0, St).
-
-%% make_forest(Kexpr, St) -> {RootKexpr,Forest,St}.
-%% Add to Forest from Kexpr. RootKexpr is the final expression
-%% nested inside Kexpr.
-
-make_forest(G, Forest0, St) ->
- N = forest_next_index(Forest0),
- make_forest_1(G, Forest0, N, St).
-
-make_forest_1(#k_try{arg=B}, Forest, I, St) ->
- make_forest_1(B, Forest, I, St);
-make_forest_1(#iset{vars=[]}=Iset0, Forest, I, St0) ->
- {UnrefVar,St} = new_var(St0),
- Iset = Iset0#iset{vars=[UnrefVar]},
- make_forest_1(Iset, Forest, I, St);
-make_forest_1(#iset{vars=[#k_var{name=V}],arg=Arg,body=B}, Forest0, I, St) ->
- Forest = Forest0#{V => {I,Arg}, {untaken,V} => true},
- make_forest_1(B, Forest, I+1, St);
-make_forest_1(Innermost, Forest, _I, St) ->
- {Innermost,Forest,St}.
-
-%% forest_take_expr(Kexpr, Forest) -> {Expr,Forest}.
-%% If Kexpr is a variable, take out the expression corresponding
-%% to variable in Forest. Expressions that have been taken out
-%% of the forest will not be included the Kexpr returned
-%% by forest_pre_seq/2.
-%%
-%% Throw a 'not_possible' exception if Kexpr is not a variable or
-%% if the name of the variable is not a key in Forest.
-
-forest_take_expr(#k_var{name=V}, Forest0) ->
- %% v3_core currently always generates guard expressions that can
- %% be represented as a tree. Other code generators (such as LFE)
- %% could generate guard expressions that can only be represented
- %% as a DAG (i.e. some nodes are referenced more than once). To
- %% handle DAGs, we must never remove a node from the forest, but
- %% just remove the {untaken,V} marker. That will effectively convert
- %% the DAG to a tree by duplicating the shared nodes and their
- %% descendants.
-
- case maps:find(V, Forest0) of
- {ok,{_,Expr}} ->
- Forest = maps:remove({untaken,V}, Forest0),
- {Expr,Forest};
- error ->
- throw(not_possible)
- end;
-forest_take_expr(_, _) ->
- throw(not_possible).
-
-%% forest_peek_expr(Kvar, Forest) -> Kexpr | error.
-%% Return the expression corresponding to Kvar in Forest or
-%% return 'error' if there is a corresponding expression.
-
-forest_peek_expr(#k_var{name=V}, Forest0) ->
- case maps:find(V, Forest0) of
- {ok,{_,Expr}} -> Expr;
- error -> error
- end.
-
-%% forest_add_expr(Kexpr, Forest, St) -> {Kvar,Forest,St}.
-%% Add a new expression to Forest.
-
-forest_add_expr(Expr, Forest0, St0) ->
- {#k_var{name=V}=Var,St} = new_var(St0),
- N = forest_next_index(Forest0),
- Forest = Forest0#{V => {N,Expr}},
- {Var,Forest,St}.
-
-forest_next_index(Forest) ->
- 1 + lists:max([N || {N,_} <- maps:values(Forest),
- is_integer(N)] ++ [0]).
-
-%% forest_pre_seq([Kexpr], Forest) -> Kexpr.
-%% Package the list of Kexprs into a nested Kexpr, prepending all
-%% expressions in Forest that have not been taken out using
-%% forest_take_expr/2.
-
-forest_pre_seq(Exprs, Forest) ->
- Es0 = [#k_var{name=V} || {untaken,V} <- maps:keys(Forest)],
- Es = Es0 ++ Exprs,
- Vs = extract_all_vars(Es, Forest, []),
- Pre0 = sort([{maps:get(V, Forest),V} || V <- Vs]),
- Pre = [#iset{vars=[#k_var{name=V}],arg=A} ||
- {{_,A},V} <- Pre0],
- pre_seq(Pre++droplast(Exprs), last(Exprs)).
-
-extract_all_vars(Es, Forest, Acc0) ->
- case extract_var_list(Es) of
- [] ->
- Acc0;
- [_|_]=Vs0 ->
- Vs = [V || V <- Vs0, maps:is_key(V, Forest)],
- NewVs = ordsets:subtract(Vs, Acc0),
- NewEs = [begin
- {_,E} = maps:get(V, Forest),
- E
- end || V <- NewVs],
- Acc = union(NewVs, Acc0),
- extract_all_vars(NewEs, Forest, Acc)
- end.
-
-extract_vars(#iset{arg=A,body=B}) ->
- union(extract_vars(A), extract_vars(B));
-extract_vars(#k_bif{args=Args}) ->
- ordsets:from_list(lit_list_vars(Args));
-extract_vars(#k_call{}) ->
- [];
-extract_vars(#k_test{args=Args}) ->
- ordsets:from_list(lit_list_vars(Args));
-extract_vars(#k_match{body=Body}) ->
- extract_vars(Body);
-extract_vars(#k_alt{first=First,then=Then}) ->
- union(extract_vars(First), extract_vars(Then));
-extract_vars(#k_guard{clauses=Cs}) ->
- extract_var_list(Cs);
-extract_vars(#k_guard_clause{guard=G}) ->
- extract_vars(G);
-extract_vars(#k_select{var=Var,types=Types}) ->
- union(ordsets:from_list(lit_vars(Var)),
- extract_var_list(Types));
-extract_vars(#k_type_clause{values=Values}) ->
- extract_var_list(Values);
-extract_vars(#k_val_clause{body=Body}) ->
- extract_vars(Body);
-extract_vars(#k_try{arg=Arg}) ->
- extract_vars(Arg);
-extract_vars(Lit) ->
- ordsets:from_list(lit_vars(Lit)).
-
-extract_var_list(L) ->
- union([extract_vars(E) || E <- L]).
-
%% Wrap the entire guard in a try/catch if needed.
wrap_guard(#c_try{}=Try, St) -> {Try,St};
@@ -2356,8 +1886,6 @@ ubody(E, return, St0) ->
{Ea,Pa,St1} = force_atomic(E, St0),
ubody(pre_seq(Pa, #ivalues{args=[Ea]}), return, St1)
end;
-ubody(#ignored{}, {break,_} = Break, St) ->
- ubody(#ivalues{args=[]}, Break, St);
ubody(E, {break,[_]} = Break, St0) ->
%%ok = io:fwrite("ubody ~w:~p~n", [?LINE,{E,Br}]),
%% Exiting expressions need no trailing break.
diff --git a/lib/compiler/src/v3_kernel.hrl b/lib/compiler/src/v3_kernel.hrl
index e26360a6da..31816846cf 100644
--- a/lib/compiler/src/v3_kernel.hrl
+++ b/lib/compiler/src/v3_kernel.hrl
@@ -58,7 +58,7 @@
-record(k_seq, {anno=[],arg,body}).
-record(k_put, {anno=[],arg,ret=[]}).
-record(k_bif, {anno=[],op,args,ret=[]}).
--record(k_test, {anno=[],op,args,inverted=false}).
+-record(k_test, {anno=[],op,args}).
-record(k_call, {anno=[],op,args,ret=[]}).
-record(k_enter, {anno=[],op,args}).
-record(k_receive, {anno=[],var,body,timeout,action,ret=[]}).
diff --git a/lib/compiler/src/v3_kernel_pp.erl b/lib/compiler/src/v3_kernel_pp.erl
index c12c301ee2..3ebe957657 100644
--- a/lib/compiler/src/v3_kernel_pp.erl
+++ b/lib/compiler/src/v3_kernel_pp.erl
@@ -235,13 +235,8 @@ format_1(#k_bif{op=Op,args=As,ret=Rs}, Ctxt) ->
[Txt,format_args(As, Ctxt1),
format_ret(Rs, Ctxt1)
];
-format_1(#k_test{op=Op,args=As,inverted=Inverted}, Ctxt) ->
- Txt = case Inverted of
- false ->
- ["test (",format(Op, ctxt_bump_indent(Ctxt, 6)),$)];
- true ->
- ["inverted_test (",format(Op, ctxt_bump_indent(Ctxt, 6)),$)]
- end,
+format_1(#k_test{op=Op,args=As}, Ctxt) ->
+ Txt = ["test (",format(Op, ctxt_bump_indent(Ctxt, 6)),$)],
Ctxt1 = ctxt_bump_indent(Ctxt, 2),
[Txt,format_args(As, Ctxt1)];
format_1(#k_put{arg=A,ret=Rs}, Ctxt) ->
diff --git a/lib/compiler/test/andor_SUITE.erl b/lib/compiler/test/andor_SUITE.erl
index 5c463063c1..7232eb0ffd 100644
--- a/lib/compiler/test/andor_SUITE.erl
+++ b/lib/compiler/test/andor_SUITE.erl
@@ -66,6 +66,17 @@ t_case(Config) when is_list(Config) ->
true = (catch t_case_e({a,b}, {a,b})),
false = (catch t_case_e({a,b}, 42)),
+ {true,false} = t_case_f1(true, pos),
+ {false,true} = t_case_f1(true, whatever),
+ {false,true} = t_case_f1(false, pos),
+ {false,true} = t_case_f1(false, whatever),
+ {false,false} = t_case_f1(not_boolean, pos),
+ {false,false} = t_case_f1(not_boolean, whatever),
+
+ false = t_case_f2(true),
+ true = t_case_f2(false),
+ false = t_case_f2(whatever),
+
true = t_case_xy(42, 100, 700),
true = t_case_xy(42, 100, whatever),
false = t_case_xy(42, wrong, 700),
@@ -109,6 +120,25 @@ t_case_e(A, B) ->
Bool when is_tuple(A) -> id(Bool)
end.
+t_case_f1(IsInt, Eval) ->
+ B = case IsInt of
+ true -> Eval =:= pos;
+ false -> false;
+ _ -> IsInt
+ end,
+
+ %% The above is the same as `IsInt andalso Eval =:= pos` in a guard.
+ %% In a real guard, variable `B` will only be used once.
+ {B =:= true, B =:= false}.
+
+t_case_f2(IsInt) ->
+ B = case IsInt of
+ true -> false;
+ false -> true;
+ _ -> IsInt
+ end,
+ B =:= true.
+
t_case_xy(X, Y, Z) ->
Res = t_case_x(X, Y, Z),
Res = t_case_y(X, Y, Z).
diff --git a/lib/compiler/test/compile_SUITE.erl b/lib/compiler/test/compile_SUITE.erl
index 453debc0c1..264a3c2b67 100644
--- a/lib/compiler/test/compile_SUITE.erl
+++ b/lib/compiler/test/compile_SUITE.erl
@@ -374,6 +374,8 @@ do_file_listings(DataDir, PrivDir, [File|Files]) ->
{dcbsm, ".core_bsm"},
{dkern, ".kernel"},
{dssa, ".ssa"},
+ {dbool, ".bool"},
+ {dssashare, ".ssashare"},
{dssaopt, ".ssaopt"},
{dprecg, ".precodegen"},
{dcg, ".codegen"},
diff --git a/lib/compiler/test/guard_SUITE.erl b/lib/compiler/test/guard_SUITE.erl
index d3d62b53f5..fd11a66a18 100644
--- a/lib/compiler/test/guard_SUITE.erl
+++ b/lib/compiler/test/guard_SUITE.erl
@@ -1213,6 +1213,10 @@ tricky(Config) when is_list(Config) ->
error = tricky_3(#{}),
error = tricky_3({a,b}),
+ {'EXIT',_} = (catch tricky_4(x)),
+ {'EXIT',_} = (catch tricky_4(42)),
+ {'EXIT',_} = (catch tricky_4(true)),
+
ok.
tricky_1(X, Y) when abs((X == 1) or (Y == 2)) -> ok;
@@ -1230,6 +1234,13 @@ tricky_3(X)
tricky_3(_) ->
error.
+tricky_4(X) ->
+ B = (abs(X) or abs(X)) =:= true,
+ case B of
+ true -> ok;
+ false -> error
+ end.
+
%% From dets_v9:read_buckets/11, simplified.
rb(Size, ToRead, SoFar) when SoFar + Size < 81920; ToRead == [] -> true;
@@ -1931,6 +1942,15 @@ andalso_semi(Config) when is_list(Config) ->
ok = andalso_semi_bar([a,b,c]),
ok = andalso_semi_bar(1),
fc(catch andalso_semi_bar([a,b])),
+
+ ok = andalso_semi_dispatch(name, fun andalso_semi/1),
+ ok = andalso_semi_dispatch(name, fun ?MODULE:andalso_semi/1),
+ ok = andalso_semi_dispatch(name, {?MODULE,andalso_semi,1}),
+ fc(catch andalso_semi_dispatch(42, fun andalso_semi/1)),
+ fc(catch andalso_semi_dispatch(name, not_fun)),
+ fc(catch andalso_semi_dispatch(name, fun andalso_semi_dispatch/2)),
+ fc(catch andalso_semi_dispatch(42, {a,b})),
+
ok.
andalso_semi_foo(Bar) when is_integer(Bar) andalso Bar =:= 0; Bar =:= 1 ->
@@ -1939,6 +1959,10 @@ andalso_semi_foo(Bar) when is_integer(Bar) andalso Bar =:= 0; Bar =:= 1 ->
andalso_semi_bar(Bar) when is_list(Bar) andalso length(Bar) =:= 3; Bar =:= 1 ->
ok.
+andalso_semi_dispatch(Registry, MFAOrFun) when
+ is_atom(Registry) andalso is_function(MFAOrFun, 1);
+ is_atom(Registry) andalso tuple_size(MFAOrFun) == 3 ->
+ ok.
t_tuple_size(Config) when is_list(Config) ->
10 = do_tuple_size({1,2,3,4}),
@@ -2234,7 +2258,8 @@ do_guard_in_catch_bin(From) ->
%%%
%%% The beam_bool pass has been eliminated. Here are the tests from
-%%% beam_bool_SUITE.
+%%% beam_bool_SUITE, as well as new tests to test the new beam_ssa_bool
+%%% module.
%%%
beam_bool_SUITE(_Config) ->
@@ -2243,6 +2268,9 @@ beam_bool_SUITE(_Config) ->
y_registers(),
protected(),
maps(),
+ cover_shortcut_branches(),
+ wrong_order(),
+ megaco(),
ok.
before_and_inside_if() ->
@@ -2380,6 +2408,83 @@ maps() ->
evidence(#{0 := Charge}) when 0; #{[] => Charge} == #{[] => 42} ->
ok.
+cover_shortcut_branches() ->
+ ok = cover_shortcut_branches({r1}, 0, 42, false),
+ ok = cover_shortcut_branches({r1}, 42, 42, true),
+ error = cover_shortcut_branches({r1}, same, same, false),
+ error = cover_shortcut_branches({r1}, x, y, true),
+ error = cover_shortcut_branches({r2}, 0, 42, false),
+ error = cover_shortcut_branches({}, 0, 42, false),
+ error = cover_shortcut_branches(not_tuple, 0, 42, false),
+ ok.
+
+cover_shortcut_branches(St, X, Y, Z) ->
+ if
+ %% The ((Y =:= X) =:= Z) part will test handling of a comparison
+ %% operator followed by a one-way `br`.
+ ((element(1, St) =:= r1) orelse fail) and ((Y =:= X) =:= Z) ->
+ ok;
+ true ->
+ error
+ end.
+
+wrong_order() ->
+ ok = wrong_order(repeat_until_fail, true),
+ ok = wrong_order(repeat_until_fail, whatever),
+ error = wrong_order(repeat_until_fail, false),
+ error = wrong_order(nope, true),
+ ok.
+
+wrong_order(RepeatType, Mode) ->
+ Parallel = Mode =/= false,
+ RepeatStop = RepeatType =:= repeat_until_fail,
+ if
+ Parallel andalso RepeatStop ->
+ ok;
+ true ->
+ error
+ end.
+
+megaco() ->
+ ok = megaco('NULL', 0),
+ ok = megaco('NULL', 7),
+ ok = megaco('NULL', 15),
+ ok = megaco('NULL', asn1_NOVALUE),
+ ok = megaco(asn1_NOVALUE, 0),
+ ok = megaco(asn1_NOVALUE, 7),
+ ok = megaco(asn1_NOVALUE, 15),
+ ok = megaco(asn1_NOVALUE, asn1_NOVALUE),
+
+ error = megaco(bad, 0),
+ error = megaco(bad, 7),
+ error = megaco(bad, 15),
+ error = megaco(bad, asn1_NOVALUE),
+
+ error = megaco('NULL', not_integer),
+ error = megaco('NULL', -1),
+ error = megaco('NULL', 16),
+ error = megaco(asn1_NOVALUE, not_integer),
+ error = megaco(asn1_NOVALUE, -1),
+ error = megaco(asn1_NOVALUE, 16),
+
+ error = megaco(bad, bad),
+ error = megaco(bad, -1),
+ error = megaco(bad, 42),
+
+ ok.
+
+megaco(Top, SelPrio)
+ when (Top =:= 'NULL' orelse Top =:= asn1_NOVALUE) andalso
+ ((is_integer(SelPrio) andalso ((0 =< SelPrio) and (SelPrio =< 15))) orelse
+ SelPrio =:= asn1_NOVALUE) ->
+ ok;
+megaco(_, _) ->
+ error.
+
+%%%
+%%% End of beam_bool_SUITE tests.
+%%%
+
repeated_type_tests(_Config) ->
binary = repeated_type_test(<<42>>),
bitstring = repeated_type_test(<<1:1>>),
diff --git a/lib/compiler/test/lfe_andor_SUITE.core b/lib/compiler/test/lfe_andor_SUITE.core
index df58b39ae6..e8cb0919a0 100644
--- a/lib/compiler/test/lfe_andor_SUITE.core
+++ b/lib/compiler/test/lfe_andor_SUITE.core
@@ -34,6 +34,8 @@ module 'lfe_andor_SUITE' ['$handle_undefined_function'/2,
'init_per_suite'/1 =
%% Line 48
fun (_config) ->
+ do
+ call 'test_lib':'recompile_core'('lfe_andor_SUITE')
_config
'end_per_suite'/1 =
%% Line 50
diff --git a/lib/compiler/test/lfe_guard_SUITE.core b/lib/compiler/test/lfe_guard_SUITE.core
index 920be82f61..9d184ed166 100644
--- a/lib/compiler/test/lfe_guard_SUITE.core
+++ b/lib/compiler/test/lfe_guard_SUITE.core
@@ -53,6 +53,8 @@ module 'lfe_guard_SUITE' ['$handle_undefined_function'/2,
'init_per_suite'/1 =
%% Line 62
fun (_config) ->
+ do
+ call 'test_lib':'recompile_core'('lfe_guard_SUITE')
_config
'end_per_suite'/1 =
%% Line 64
diff --git a/lib/compiler/test/misc_SUITE.erl b/lib/compiler/test/misc_SUITE.erl
index 20fadc4fdb..fe1cf2ed25 100644
--- a/lib/compiler/test/misc_SUITE.erl
+++ b/lib/compiler/test/misc_SUITE.erl
@@ -181,6 +181,7 @@ silly_coverage(Config) when is_list(Config) ->
expect_error(fun() -> beam_kernel_to_ssa:module(BadKernel, []) end),
%% beam_ssa_lint
+ %% beam_ssa_bool
%% beam_ssa_recv
%% beam_ssa_share
%% beam_ssa_pre_codegen
@@ -188,6 +189,7 @@ silly_coverage(Config) when is_list(Config) ->
BadSSA = {b_module,#{},a,b,c,
[{b_function,#{func_info=>{mod,foo,0}},args,bad_blocks,0}]},
expect_error(fun() -> beam_ssa_lint:module(BadSSA, []) end),
+ expect_error(fun() -> beam_ssa_bool:module(BadSSA, []) end),
expect_error(fun() -> beam_ssa_recv:module(BadSSA, []) end),
expect_error(fun() -> beam_ssa_share:module(BadSSA, []) end),
expect_error(fun() -> beam_ssa_pre_codegen:module(BadSSA, []) end),
diff --git a/lib/compiler/test/record_SUITE.erl b/lib/compiler/test/record_SUITE.erl
index 4ed7f39780..3a2453dd4b 100644
--- a/lib/compiler/test/record_SUITE.erl
+++ b/lib/compiler/test/record_SUITE.erl
@@ -608,8 +608,9 @@ coverage(Config) when is_list(Config) ->
-record(gb_nil, {}).
-record(gb_foo, {hello=1}).
-record(gb_bar, {hello=2,there=3}).
+-record(gb_rh, {mod,mid}).
-%% Taken from compilation_SUITE.
+%% Taken from compilation_SUITE and other places.
grab_bag(_Config) ->
T1 = fun() ->
X = #foo{},
@@ -653,6 +654,23 @@ grab_bag(_Config) ->
end,
T4(),
+ %% Used to crash beam_ssa_bool during its development.
+ T5 = fun(RH) ->
+ if
+ is_record(RH, gb_rh) andalso
+ is_atom(RH#gb_rh.mod) andalso
+ RH#gb_rh.mid /= 42 -> ok;
+ true -> error
+ end
+ end,
+ ok = T5(#gb_rh{}),
+ ok = T5(#gb_rh{mod=atom,mid=0}),
+ error = T5(#gb_rh{mod=100,mid=0}),
+ error = T5(#gb_rh{mod=atom,mid=42}),
+ error = T5(#gb_nil{}),
+ error = T5(#gb_bar{}),
+ error = T5(atom),
+
ok.
first_arg(First, _) -> First.
diff --git a/lib/compiler/test/test_lib.erl b/lib/compiler/test/test_lib.erl
index 4b68e663cd..66f45aad5e 100644
--- a/lib/compiler/test/test_lib.erl
+++ b/lib/compiler/test/test_lib.erl
@@ -21,7 +21,8 @@
-include_lib("common_test/include/ct.hrl").
-compile({no_auto_import,[binary_part/2]}).
--export([id/1,recompile/1,parallel/0,uniq/0,opt_opts/1,get_data_dir/1,
+-export([id/1,recompile/1,recompile_core/1,parallel/0,
+ uniq/0,opt_opts/1,get_data_dir/1,
is_cloned_mod/1,smoke_disasm/1,p_run/2,
highest_opcode/1]).
@@ -45,6 +46,21 @@ recompile(Mod) when is_atom(Mod) ->
%% Smoke-test of beam disassembler.
smoke_disasm(Mod).
+recompile_core(Mod) when is_atom(Mod) ->
+ case whereis(cover_server) of
+ undefined -> ok;
+ _ ->
+ %% Re-compile the test suite if the cover server is running.
+ Beam = code:which(Mod),
+ Src = filename:rootname(Beam, ".beam"),
+ Opts = [bin_opt_info|opt_opts(Mod)],
+ io:format("Recompiling ~p (~p)\n", [Mod,Opts]),
+ c:c(Src, [from_core,{outdir,filename:dirname(Src)}|Opts])
+ end,
+
+ %% Smoke-test of beam disassembler.
+ smoke_disasm(Mod).
+
smoke_disasm(Mod) when is_atom(Mod) ->
smoke_disasm(code:which(Mod));
smoke_disasm(File) when is_list(File) ->