diff options
Diffstat (limited to 'lib/compiler')
45 files changed, 2538 insertions, 1502 deletions
diff --git a/lib/compiler/doc/src/Makefile b/lib/compiler/doc/src/Makefile index 661415899f..32f150eef8 100644 --- a/lib/compiler/doc/src/Makefile +++ b/lib/compiler/doc/src/Makefile @@ -1,7 +1,7 @@ # # %CopyrightBegin% # -# Copyright Ericsson AB 1997-2017. All Rights Reserved. +# Copyright Ericsson AB 1997-2018. All Rights Reserved. # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. diff --git a/lib/compiler/doc/src/notes.xml b/lib/compiler/doc/src/notes.xml index 671126b73b..440b50d509 100644 --- a/lib/compiler/doc/src/notes.xml +++ b/lib/compiler/doc/src/notes.xml @@ -32,6 +32,22 @@ <p>This document describes the changes made to the Compiler application.</p> +<section><title>Compiler 7.2.4</title> + + <section><title>Fixed Bugs and Malfunctions</title> + <list> + <item> + <p>Fix a regression in OTP-15204 that removed + <c>.beam</c> file metadata that some external build tools + relied on.</p> + <p> + Own Id: OTP-15292</p> + </item> + </list> + </section> + +</section> + <section><title>Compiler 7.2.3</title> <section><title>Fixed Bugs and Malfunctions</title> @@ -314,6 +330,22 @@ </section> +<section><title>Compiler 7.1.5.2</title> + + <section><title>Fixed Bugs and Malfunctions</title> + <list> + <item> + <p>Fix a regression in OTP-15204 that removed + <c>.beam</c> file metadata that some external build tools + relied on.</p> + <p> + Own Id: OTP-15292</p> + </item> + </list> + </section> + +</section> + <section><title>Compiler 7.1.5.1</title> <section><title>Fixed Bugs and Malfunctions</title> diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile index bd35f20442..522523726b 100644 --- a/lib/compiler/src/Makefile +++ b/lib/compiler/src/Makefile @@ -52,7 +52,6 @@ MODULES = \ beam_bs \ beam_bsm \ beam_clean \ - beam_dead \ beam_dict \ beam_disasm \ beam_except \ @@ -61,9 +60,9 @@ MODULES = \ beam_listing \ beam_opcodes \ beam_peep \ - beam_split \ beam_ssa \ beam_ssa_codegen \ + beam_ssa_dead \ beam_ssa_lint \ beam_ssa_opt \ beam_ssa_pp \ @@ -194,6 +193,7 @@ $(EBIN)/beam_listing.beam: core_parse.hrl v3_kernel.hrl beam_ssa.hrl $(EBIN)/beam_kernel_to_ssa.beam: v3_kernel.hrl beam_ssa.hrl $(EBIN)/beam_ssa.beam: beam_ssa.hrl $(EBIN)/beam_ssa_codegen.beam: beam_ssa.hrl +$(EBIN)/beam_ssa_dead.beam: beam_ssa.hrl $(EBIN)/beam_ssa_lint.beam: beam_ssa.hrl $(EBIN)/beam_ssa_opt.beam: beam_ssa.hrl $(EBIN)/beam_ssa_pp.beam: beam_ssa.hrl diff --git a/lib/compiler/src/beam_a.erl b/lib/compiler/src/beam_a.erl index 266e8f46c8..0abc845310 100644 --- a/lib/compiler/src/beam_a.erl +++ b/lib/compiler/src/beam_a.erl @@ -52,6 +52,13 @@ function({function,Name,Arity,CLabel,Is0}) -> erlang:raise(Class, Error, Stack) end. +rename_instrs([{test,is_eq_exact,_,[Dst,Src]}=Test, + {move,Src,Dst}|Is]) -> + %% The move instruction is not needed. + rename_instrs([Test|Is]); +rename_instrs([{test,is_eq_exact,_,[Same,Same]}|Is]) -> + %% Same literal or same register. Will always succeed. + rename_instrs(Is); rename_instrs([{apply_last,A,N}|Is]) -> [{apply,A},{deallocate,N},return|rename_instrs(Is)]; rename_instrs([{call_last,A,F,N}|Is]) -> diff --git a/lib/compiler/src/beam_block.erl b/lib/compiler/src/beam_block.erl index 0ed2a03a81..d28c0fd9e4 100644 --- a/lib/compiler/src/beam_block.erl +++ b/lib/compiler/src/beam_block.erl @@ -83,8 +83,8 @@ collect({allocate_heap,Ns,Nh,R}) -> {set,[],[],{alloc,R,{nozero,Ns,Nh,[]}}}; collect({allocate_heap_zero,Ns,Nh,R}) -> {set,[],[],{alloc,R,{zero,Ns,Nh,[]}}}; collect({init,D}) -> {set,[D],[],init}; collect({test_heap,N,R}) -> {set,[],[],{alloc,R,{nozero,nostack,N,[]}}}; -collect({bif,N,F,As,D}) -> {set,[D],As,{bif,N,F}}; -collect({gc_bif,N,F,R,As,D}) -> {set,[D],As,{alloc,R,{gc_bif,N,F}}}; +collect({bif,N,{f,0},As,D}) -> {set,[D],As,{bif,N,{f,0}}}; +collect({gc_bif,N,{f,0},R,As,D}) -> {set,[D],As,{alloc,R,{gc_bif,N,{f,0}}}}; collect({move,S,D}) -> {set,[D],[S],move}; collect({put_list,S1,S2,D}) -> {set,[D],[S1,S2],put_list}; collect({put_tuple,A,D}) -> {set,[D],[],{put_tuple,A}}; @@ -95,12 +95,8 @@ collect({set_tuple_element,S,D,I}) -> {set,[],[S,D],{set_tuple_element,I}}; collect({get_hd,S,D}) -> {set,[D],[S],get_hd}; collect({get_tl,S,D}) -> {set,[D],[S],get_tl}; collect(remove_message) -> {set,[],[],remove_message}; -collect({put_map,F,Op,S,D,R,{list,Puts}}) -> - {set,[D],[S|Puts],{alloc,R,{put_map,Op,F}}}; -collect({'catch'=Op,R,L}) -> - {set,[R],[],{try_catch,Op,L}}; -collect({'try'=Op,R,L}) -> - {set,[R],[],{try_catch,Op,L}}; +collect({put_map,{f,0},Op,S,D,R,{list,Puts}}) -> + {set,[D],[S|Puts],{alloc,R,{put_map,Op,{f,0}}}}; collect(fclearerror) -> {set,[],[],fclearerror}; collect({fcheckerror,{f,0}}) -> {set,[],[],fcheckerror}; collect({fmove,S,D}) -> {set,[D],[S],fmove}; diff --git a/lib/compiler/src/beam_dead.erl b/lib/compiler/src/beam_dead.erl deleted file mode 100644 index 546f0461b9..0000000000 --- a/lib/compiler/src/beam_dead.erl +++ /dev/null @@ -1,881 +0,0 @@ -%% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2002-2018. All Rights Reserved. -%% -%% Licensed under the Apache License, Version 2.0 (the "License"); -%% you may not use this file except in compliance with the License. -%% You may obtain a copy of the License at -%% -%% http://www.apache.org/licenses/LICENSE-2.0 -%% -%% Unless required by applicable law or agreed to in writing, software -%% distributed under the License is distributed on an "AS IS" BASIS, -%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -%% See the License for the specific language governing permissions and -%% limitations under the License. -%% -%% %CopyrightEnd% -%% - --module(beam_dead). - --export([module/2]). - -%%% Dead code is code that is executed but has no effect. This -%%% optimization pass either removes dead code or jumps around it, -%%% potentially making it unreachable and a target for the -%%% the beam_jump pass. - --import(lists, [mapfoldl/3,reverse/1]). - - --spec module(beam_utils:module_code(), [compile:option()]) -> - {'ok',beam_utils:module_code()}. - -module({Mod,Exp,Attr,Fs0,_}, _Opts) -> - {Fs1,Lc1} = beam_clean:clean_labels(Fs0), - {Fs,Lc} = mapfoldl(fun function/2, Lc1, Fs1), - %%{Fs,Lc} = {Fs1,Lc1}, - {ok,{Mod,Exp,Attr,Fs,Lc}}. - -function({function,Name,Arity,CLabel,Is0}, Lc0) -> - try - Is1 = beam_jump:remove_unused_labels(Is0), - - %% Initialize label information with the code - %% for the func_info label. Without it, a register - %% may seem to be live when it is not. - [{label,L}|FiIs] = Is1, - D0 = beam_utils:empty_label_index(), - D = beam_utils:index_label(L, FiIs, D0), - - %% Optimize away dead code. - {Is2,Lc} = forward(Is1, Lc0), - Is3 = backward(Is2, D), - Is = move_move_into_block(Is3, []), - {{function,Name,Arity,CLabel,Is},Lc} - catch - Class:Error:Stack -> - io:fwrite("Function: ~w/~w\n", [Name,Arity]), - erlang:raise(Class, Error, Stack) - end. - -%% 'move' instructions outside of blocks may thwart the jump optimizer. -%% Move them back into the block. - -move_move_into_block([{block,Bl0},{move,S,D}|Is], Acc) -> - Bl = Bl0 ++ [{set,[D],[S],move}], - move_move_into_block([{block,Bl}|Is], Acc); -move_move_into_block([{move,S,D}|Is], Acc) -> - Bl = [{set,[D],[S],move}], - move_move_into_block([{block,Bl}|Is], Acc); -move_move_into_block([I|Is], Acc) -> - move_move_into_block(Is, [I|Acc]); -move_move_into_block([], Acc) -> reverse(Acc). - -%%% -%%% Scan instructions in execution order and remove redundant 'move' -%%% instructions. 'move' instructions are redundant if we know that -%%% the register already contains the value being assigned, as in the -%%% following code: -%%% -%%% test is_eq_exact SomeLabel Src Dst -%%% move Src Dst -%%% -%%% or in: -%%% -%%% select_val Register FailLabel [... Literal => L1...] -%%% . -%%% . -%%% . -%%% L1: move Literal Register -%%% -%%% Also add extra labels to help the second backward pass. -%%% - -forward(Is, Lc) -> - forward(Is, #{}, Lc, []). - -forward([{move,_,_}=Move|[{label,L}|_]=Is], D, Lc, Acc) -> - %% move/2 followed by jump/1 is optimized by backward/3. - forward([Move,{jump,{f,L}}|Is], D, Lc, Acc); -forward([{bif,_,_,_,_}=Bif|[{label,L}|_]=Is], D, Lc, Acc) -> - %% bif/4 followed by jump/1 is optimized by backward/3. - forward([Bif,{jump,{f,L}}|Is], D, Lc, Acc); -forward([{block,[]}|Is], D, Lc, Acc) -> - %% Empty blocks can prevent optimizations. - forward(Is, D, Lc, Acc); -forward([{select,select_val,Reg,_,List}=I|Is], D0, Lc, Acc) -> - D = update_value_dict(List, Reg, D0), - forward(Is, D, Lc, [I|Acc]); -forward([{label,Lbl}=LblI,{block,[{set,[Dst],[Lit],move}|BlkIs]}=Blk|Is], D, Lc, Acc) -> - %% Assumption: The target labels in a select_val/3 instruction - %% cannot be reached in any other way than through the select_val/3 - %% instruction (i.e. there can be no fallthrough to such label and - %% it cannot be referenced by, for example, a jump/1 instruction). - Key = {Lbl,Dst}, - Block = case D of - #{Key := Lit} -> {block,BlkIs}; %Safe to remove move instruction. - _ -> Blk %Must keep move instruction. - end, - forward([Block|Is], D, Lc, [LblI|Acc]); -forward([{label,Lbl}=LblI|[{move,Lit,Dst}|Is1]=Is0], D, Lc, Acc) -> - %% Assumption: The target labels in a select_val/3 instruction - %% cannot be reached in any other way than through the select_val/3 - %% instruction (i.e. there can be no fallthrough to such label and - %% it cannot be referenced by, for example, a jump/1 instruction). - Is = case maps:find({Lbl,Dst}, D) of - {ok,Lit} -> Is1; %Safe to remove move instruction. - _ -> Is0 %Keep move instruction. - end, - forward(Is, D, Lc, [LblI|Acc]); -forward([{test,is_eq_exact,_,[Same,Same]}|Is], D, Lc, Acc) -> - forward(Is, D, Lc, Acc); -forward([{test,is_eq_exact,_,[Dst,Src]}=I, - {block,[{set,[Dst],[Src],move}|Bl]}|Is], D, Lc, Acc) -> - forward([I,{block,Bl}|Is], D, Lc, Acc); -forward([{test,is_eq_exact,_,[Dst,Src]}=I,{move,Src,Dst}|Is], D, Lc, Acc) -> - forward([I|Is], D, Lc, Acc); -forward([{test,_,_,_}=I|Is]=Is0, D, Lc, Acc) -> - %% Help the second, backward pass to by inserting labels after - %% relational operators so that they can be skipped if they are - %% known to be true. - case useful_to_insert_label(Is0) of - false -> forward(Is, D, Lc, [I|Acc]); - true -> forward(Is, D, Lc+1, [{label,Lc},I|Acc]) - end; -forward([I|Is], D, Lc, Acc) -> - forward(Is, D, Lc, [I|Acc]); -forward([], _, Lc, Acc) -> {Acc,Lc}. - -update_value_dict([Lit,{f,Lbl}|T], Reg, D0) -> - Key = {Lbl,Reg}, - D = case D0 of - #{Key := inconsistent} -> D0; - #{Key := _} -> D0#{Key := inconsistent}; - _ -> D0#{Key => Lit} - end, - update_value_dict(T, Reg, D); -update_value_dict([], _, D) -> D. - -useful_to_insert_label([_,{label,_}|_]) -> - false; -useful_to_insert_label([{test,Op,_,_}|_]) -> - case Op of - is_lt -> true; - is_ge -> true; - is_eq_exact -> true; - is_ne_exact -> true; - _ -> false - end. - -%%% -%%% Scan instructions in reverse execution order and try to -%%% shortcut branch instructions. -%%% -%%% For example, in this code: -%%% -%%% move Literal Register -%%% jump L1 -%%% . -%%% . -%%% . -%%% L1: test is_{integer,atom} FailLabel Register -%%% select_val {x,0} FailLabel [... Literal => L2...] -%%% . -%%% . -%%% . -%%% L2: ... -%%% -%%% the 'selectval' instruction will always transfer control to L2, -%%% so we can just as well jump to L2 directly by rewriting the -%%% first part of the sequence like this: -%%% -%%% move Literal Register -%%% jump L2 -%%% -%%% If register Register is killed at label L2, we can remove the -%%% 'move' instruction, leaving just the 'jump' instruction: -%%% -%%% jump L2 -%%% -%%% These transformations may leave parts of the code unreachable. -%%% The beam_jump pass will remove the unreachable code. - -backward(Is, D) -> - backward(Is, D, []). - -backward([{test,is_eq_exact,Fail,[Dst,{integer,Arity}]}=I| - [{bif,tuple_size,Fail,[Reg],Dst}|Is]=Is0], D, Acc) -> - %% Provided that Dst is killed following this sequence, - %% we can rewrite the instructions like this: - %% - %% bif tuple_size Fail Reg Dst ==> is_tuple Fail Reg - %% is_eq_exact Fail Dst Integer test_arity Fail Reg Integer - %% - %% (still two instructions, but they they will be combined to - %% one by the loader). - case beam_utils:is_killed(Dst, Acc, D) andalso (Arity bsr 32) =:= 0 of - false -> - %% Not safe because the register Dst is not killed - %% (probably cannot not happen in practice) or the arity - %% does not fit in 32 bits (the loader will fail to load - %% the module). We must move the first instruction to the - %% accumulator to avoid an infinite loop. - backward(Is0, D, [I|Acc]); - true -> - %% Safe. - backward([{test,test_arity,Fail,[Reg,Arity]}, - {test,is_tuple,Fail,[Reg]}|Is], D, Acc) - end; -backward([{label,Lbl}=L|Is], D, Acc) -> - backward(Is, beam_utils:index_label(Lbl, Acc, D), [L|Acc]); -backward([{select,select_val,Reg,{f,Fail0},List0}|Is], D, Acc) -> - List1 = shortcut_select_list(List0, Reg, D, []), - Fail = shortcut_label(Fail0, D), - List = prune_redundant(List1, Fail), - case List of - [] -> - Jump = {jump,{f,Fail}}, - backward([Jump|Is], D, Acc); - [V,F] -> - Test = {test,is_eq_exact,{f,Fail},[Reg,V]}, - Jump = {jump,F}, - backward([Jump,Test|Is], D, Acc); - [{atom,B1},F,{atom,B2},F] when B1 =:= not B2 -> - Test = {test,is_boolean,{f,Fail},[Reg]}, - Jump = {jump,F}, - backward([Jump,Test|Is], D, Acc); - [_|_] -> - Sel = {select,select_val,Reg,{f,Fail},List}, - backward(Is, D, [Sel|Acc]) - end; -backward([{jump,{f,To0}},{move,Src,Reg}=Move|Is], D, Acc) -> - To = shortcut_select_label(To0, Reg, Src, D), - Jump = {jump,{f,To}}, - case is_killed_at(Reg, To, D) of - false -> backward([Move|Is], D, [Jump|Acc]); - true -> backward([Jump|Is], D, Acc) - end; -backward([{jump,{f,To}}=J|[{bif,Op,{f,BifFail},Ops,Reg}|Is]=Is0], D, Acc) -> - try replace_comp_op(To, Reg, Op, Ops, D) of - {Test,Jump} -> - backward([Jump,Test|Is], D, Acc) - catch - throw:not_possible -> - case To =:= BifFail of - true -> - %% The bif instruction is redundant. See the comment - %% in the next clause for why there is no need to - %% test for liveness of Reg at label To. - backward([J|Is], D, Acc); - false -> - backward(Is0, D, [J|Acc]) - end - end; -backward([{jump,{f,To}}=J|[{gc_bif,_,{f,To},_,_,_Dst}|Is]], D, Acc) -> - %% The gc_bif instruction is redundant, since either the gc_bif - %% instruction itself or the jump instruction will transfer control - %% to label To. Note that a gc_bif instruction does not assign its - %% destination register if the failure branch is taken; therefore, - %% the code at label To is not allowed to assume that the destination - %% register is initialized, and it is therefore no need to test - %% for liveness of the destination register at label To. - backward([J|Is], D, Acc); -backward([{test,bs_start_match2,F,Live,[Src,_]=Args,Ctxt}|Is], D, Acc0) -> - {f,To0} = F, - case test_bs_literal(F, Ctxt, D, Acc0) of - {none,Acc} -> - %% Ctxt killed immediately after bs_start_match2. - To = shortcut_bs_context_to_binary(To0, Src, D), - I = {test,is_bitstr,{f,To},[Src]}, - backward(Is, D, [I|Acc]); - {Literal,Acc} -> - %% Ctxt killed after matching a literal. - To = shortcut_bs_context_to_binary(To0, Src, D), - Eq = {test,is_eq_exact,{f,To},[Src,{literal,Literal}]}, - backward(Is, D, [Eq|Acc]); - not_killed -> - %% Ctxt not killed. Not much to do. - To = shortcut_bs_start_match(To0, Src, D), - I = {test,bs_start_match2,{f,To},Live,Args,Ctxt}, - backward(Is, D, [I|Acc0]) - end; -backward([{test,Op,{f,To0},Ops0}|Is], D, Acc) -> - To1 = shortcut_label(To0, D), - To2 = shortcut_rel_op(To1, Op, Ops0, D), - - %% Try to shortcut a repeated test: - %% - %% test Op {f,Fail1} Operands test Op {f,Fail2} Operands - %% . . . ==> ... - %% Fail1: test Op {f,Fail2} Operands Fail1: test Op {f,Fail2} Operands - %% - To = case beam_utils:code_at(To2, D) of - [{test,Op,{f,To3},Ops}|_] -> - case equal_ops(Ops0, Ops) of - true -> To3; - false -> To2 - end; - _Code -> - To2 - end, - I = case Op of - is_eq_exact -> combine_eqs(To, Ops0, D, Acc); - _ -> {test,Op,{f,To},Ops0} - end, - case I of - {test,_,_,_} -> - %% Still a test instruction. Done. - backward(Is, D, [I|Acc]); - _ -> - %% Rewritten to a select_val. Rescan. - backward([I|Is], D, Acc) - end; -backward([{test,Op,{f,To0},Live,Ops0,Dst}|Is], D, Acc) -> - To1 = shortcut_label(To0, D), - - %% Try to shortcut a repeated test: - %% - %% test Op {f,Fail1} _ Ops _ test Op {f,Fail2} _ Ops _ - %% . . . ==> ... - %% Fail1: test Op {f,Fail2} _ Ops _ Fail1: test Op {f,Fail2} _ Ops _ - %% - To = case beam_utils:code_at(To1, D) of - [{test,Op,{f,To2},_,Ops,_}|_] -> - case equal_ops(Ops0, Ops) of - true -> To2; - false -> To1 - end; - _Code -> - To1 - end, - I = {test,Op,{f,To},Live,Ops0,Dst}, - backward(Is, D, [I|Acc]); -backward([{kill,_}=I|Is], D, [{line,_},Exit|_]=Acc) -> - case beam_jump:is_exit_instruction(Exit) of - false -> backward(Is, D, [I|Acc]); - true -> backward(Is, D, Acc) - end; -backward([{bif,'or',{f,To0},[Dst,{atom,false}],Dst}=I|Is], D, - [{test,is_eq_exact,{f,To},[Dst,{atom,true}]}|_]=Acc) -> - case shortcut_label(To0, D) of - To -> - backward(Is, D, Acc); - _ -> - backward(Is, D, [I|Acc]) - end; -backward([{bif,map_get,{f,FF},[Key,Map],_}=I0, - {test,has_map_fields,{f,FT}=F,[Map|Keys0]}=I1|Is], D, Acc) when FF =/= 0 -> - case shortcut_label(FF, D) of - FT -> - case lists:delete(Key, Keys0) of - [] -> - backward([I0|Is], D, Acc); - Keys -> - Test = {test,has_map_fields,F,[Map|Keys]}, - backward([Test|Is], D, [I0|Acc]) - end; - _ -> - backward([I1|Is], D, [I0|Acc]) - end; -backward([{bif,map_get,{f,FF},[_,Map],_}=I0, - {test,is_map,{f,FT},[Map]}=I1|Is], D, Acc) when FF =/= 0 -> - case shortcut_label(FF, D) of - FT -> backward([I0|Is], D, Acc); - _ -> backward([I1|Is], D, [I0|Acc]) - end; -backward([I|Is], D, Acc) -> - backward(Is, D, [I|Acc]); -backward([], _D, Acc) -> Acc. - -equal_ops([{field_flags,FlA0}|T0], [{field_flags,FlB0}|T1]) -> - FlA = lists:keydelete(anno, 1, FlA0), - FlB = lists:keydelete(anno, 1, FlB0), - FlA =:= FlB andalso equal_ops(T0, T1); -equal_ops([Op|T0], [Op|T1]) -> - equal_ops(T0, T1); -equal_ops([], []) -> true; -equal_ops(_, _) -> false. - -shortcut_select_list([Lit,{f,To0}|T], Reg, D, Acc) -> - To = shortcut_select_label(To0, Reg, Lit, D), - shortcut_select_list(T, Reg, D, [{f,To},Lit|Acc]); -shortcut_select_list([], _, _, Acc) -> reverse(Acc). - -shortcut_label(0, _) -> - 0; -shortcut_label(To0, D) -> - case beam_utils:code_at(To0, D) of - [{jump,{f,To}}|_] -> shortcut_label(To, D); - _ -> To0 - end. - -shortcut_select_label(To, Reg, Lit, D) -> - shortcut_rel_op(To, is_ne_exact, [Reg,Lit], D). - -prune_redundant([_,{f,Fail}|T], Fail) -> - prune_redundant(T, Fail); -prune_redundant([V,F|T], Fail) -> - [V,F|prune_redundant(T, Fail)]; -prune_redundant([], _) -> []. - -%% Replace a comparison operator with a test instruction and a jump. -%% For example, if we have this code: -%% -%% bif '=:=' Fail Src1 Src2 {x,0} -%% jump L1 -%% . -%% . -%% . -%% L1: select_val {x,0} FailLabel [... true => L2..., ...false => L3...] -%% -%% the first two instructions can be replaced with -%% -%% test is_eq_exact L3 Src1 Src2 -%% jump L2 -%% -%% provided that {x,0} is killed at both L2 and L3. - -replace_comp_op(To, Reg, Op, Ops, D) -> - False = comp_op_find_shortcut(To, Reg, {atom,false}, D), - True = comp_op_find_shortcut(To, Reg, {atom,true}, D), - {bif_to_test(Op, Ops, False),{jump,{f,True}}}. - -comp_op_find_shortcut(To0, Reg, Val, D) -> - case shortcut_select_label(To0, Reg, Val, D) of - To0 -> - not_possible(); - To -> - case is_killed_at(Reg, To, D) of - false -> not_possible(); - true -> To - end - end. - -bif_to_test(Name, Args, Fail) -> - try - beam_utils:bif_to_test(Name, Args, {f,Fail}) - catch - error:_ -> not_possible() - end. - -not_possible() -> throw(not_possible). - -%% combine_eqs(To, Operands, Acc) -> Instruction. -%% Combine two is_eq_exact instructions or (an is_eq_exact -%% instruction and a select_val instruction) to a select_val -%% instruction if possible. -%% -%% Example: -%% -%% is_eq_exact F1 Reg Lit1 select_val Reg F2 [ Lit1 L1 -%% L1: . Lit2 L2 ] -%% . -%% . ==> -%% . -%% F1: is_eq_exact F2 Reg Lit2 F1: is_eq_exact F2 Reg Lit2 -%% L2: .... L2: -%% -combine_eqs(To, [Reg,{Type,_}=Lit1]=Ops, D, Acc) - when Type =:= atom; Type =:= integer -> - Next = case Acc of - [{label,Lbl}|_] -> Lbl; - [{jump,{f,Lbl}}|_] -> Lbl - end, - case beam_utils:code_at(To, D) of - [{test,is_eq_exact,{f,F2},[Reg,{Type,_}=Lit2]}, - {label,L2}|_] when Lit1 =/= Lit2 -> - {select,select_val,Reg,{f,F2},[Lit1,{f,Next},Lit2,{f,L2}]}; - [{test,is_eq_exact,{f,F2},[Reg,{Type,_}=Lit2]}, - {jump,{f,L2}}|_] when Lit1 =/= Lit2 -> - {select,select_val,Reg,{f,F2},[Lit1,{f,Next},Lit2,{f,L2}]}; - [{select,select_val,Reg,{f,F2},[{Type,_}|_]=List0}|_] -> - List = remove_from_list(Lit1, List0), - {select,select_val,Reg,{f,F2},[Lit1,{f,Next}|List]}; - _Is -> - {test,is_eq_exact,{f,To},Ops} - end; -combine_eqs(To, Ops, _D, _Acc) -> - {test,is_eq_exact,{f,To},Ops}. - -remove_from_list(Lit, [Lit,{f,_}|T]) -> - T; -remove_from_list(Lit, [Val,{f,_}=Fail|T]) -> - [Val,Fail|remove_from_list(Lit, T)]; -remove_from_list(_, []) -> []. - - -test_bs_literal(F, Ctxt, D, - [{test,bs_match_string,F,[Ctxt,Bs]}, - {test,bs_test_tail2,F,[Ctxt,0]}|Acc]) -> - test_bs_literal_1(Ctxt, Acc, D, Bs); -test_bs_literal(F, Ctxt, D, [{test,bs_test_tail2,F,[Ctxt,0]}|Acc]) -> - test_bs_literal_1(Ctxt, Acc, D, <<>>); -test_bs_literal(_, Ctxt, D, Acc) -> - test_bs_literal_1(Ctxt, Acc, D, none). - -test_bs_literal_1(Ctxt, Is, D, Literal) -> - case beam_utils:is_killed(Ctxt, Is, D) of - true -> {Literal,Is}; - false -> not_killed - end. - -%% shortcut_bs_start_match(TargetLabel, Reg) -> TargetLabel -%% A failing bs_start_match2 instruction means that the source (Reg) -%% cannot be a binary. That means that it is safe to skip -%% bs_context_to_binary instructions operating on Reg, and -%% bs_start_match2 instructions operating on Reg. - -shortcut_bs_start_match(To, Reg, D) -> - shortcut_bs_start_match_1(beam_utils:code_at(To, D), Reg, To, D). - -shortcut_bs_start_match_1([{bs_context_to_binary,Reg}|Is], Reg, To, D) -> - shortcut_bs_start_match_1(Is, Reg, To, D); -shortcut_bs_start_match_1([{jump,{f,To}}|_], Reg, _, D) -> - Code = beam_utils:code_at(To, D), - shortcut_bs_start_match_1(Code, Reg, To, D); -shortcut_bs_start_match_1([{test,bs_start_match2,{f,To},_,[Reg|_],_}|_], - Reg, _, D) -> - Code = beam_utils:code_at(To, D), - shortcut_bs_start_match_1(Code, Reg, To, D); -shortcut_bs_start_match_1(_, _, To, _) -> - To. - -%% shortcut_bs_context_to_binary(TargetLabel, Reg) -> TargetLabel -%% If a bs_start_match2 instruction has been eliminated, the -%% bs_context_to_binary instruction can be eliminated too. - -shortcut_bs_context_to_binary(To, Reg, D) -> - shortcut_bs_ctb_1(beam_utils:code_at(To, D), Reg, To, D). - -shortcut_bs_ctb_1([{bs_context_to_binary,Reg}|Is], Reg, To, D) -> - shortcut_bs_ctb_1(Is, Reg, To, D); -shortcut_bs_ctb_1([{jump,{f,To}}|_], Reg, _, D) -> - Code = beam_utils:code_at(To, D), - shortcut_bs_ctb_1(Code, Reg, To, D); -shortcut_bs_ctb_1(_, _, To, _) -> - To. - -%% shortcut_rel_op(FailLabel, Operator, [Operand], D) -> FailLabel' -%% Try to shortcut the given test instruction. Example: -%% -%% is_ge L1 {x,0} 48 -%% . -%% . -%% . -%% L1: is_ge L2 {x,0} 65 -%% -%% The first test instruction can be rewritten to "is_ge L2 {x,0} 48" -%% since the instruction at L1 will also fail. -%% -%% If there are instructions between L1 and the other test instruction -%% it may still be possible to do the shortcut. For example: -%% -%% L1: is_eq_exact L3 {x,0} 92 -%% is_ge L2 {x,0} 65 -%% -%% Since the first test instruction failed, we know that {x,0} must -%% be less than 48; therefore, we know that {x,0} cannot be equal to -%% 92 and the jump to L3 cannot happen. - -shortcut_rel_op(To, Op, Ops, D) -> - case normalize_op({test,Op,{f,To},Ops}) of - {{NormOp,A,B},_} -> - Normalized = {negate_op(NormOp),A,B}, - shortcut_rel_op_fp(To, Normalized, D); - {_,_} -> - To; - error -> - To - end. - -shortcut_rel_op_fp(To0, Normalized, D) -> - Code = beam_utils:code_at(To0, D), - case shortcut_any_label(Code, Normalized) of - error -> - To0; - To -> - shortcut_rel_op_fp(To, Normalized, D) - end. - -%% shortcut_any_label([Instruction], PrevCondition) -> FailLabel | error -%% Using PrevCondition (a previous condition known to be true), -%% try to shortcut to another failure label. - -shortcut_any_label([{jump,{f,Lbl}}|_], _Prev) -> - Lbl; -shortcut_any_label([{label,Lbl}|_], _Prev) -> - Lbl; -shortcut_any_label([{select,select_val,R,{f,Fail},L}|_], Prev) -> - shortcut_selectval(L, R, Fail, Prev); -shortcut_any_label([I|Is], Prev) -> - case normalize_op(I) of - error -> - error; - {Normalized,Fail} -> - %% We have a relational operator. - case will_succeed(Prev, Normalized) of - no -> - %% This test instruction will always branch - %% to Fail. - Fail; - yes -> - %% This test instruction will never branch, - %% so we will look at the next instruction. - shortcut_any_label(Is, Prev); - maybe -> - %% May or may not branch. From now on, we can only - %% shortcut to the this specific failure label - %% Fail. - shortcut_specific_label(Is, Fail, Prev) - end - end. - -%% shortcut_specific_label([Instruction], FailLabel, PrevCondition) -> -%% FailLabel | error -%% We have previously encountered a test instruction that may or -%% may not branch to FailLabel. Therefore we are only allowed -%% to do the shortcut to the same fail label (FailLabel). - -shortcut_specific_label([{label,_}|Is], Fail, Prev) -> - shortcut_specific_label(Is, Fail, Prev); -shortcut_specific_label([{select,select_val,R,{f,F},L}|_], Fail, Prev) -> - case shortcut_selectval(L, R, F, Prev) of - Fail -> Fail; - _ -> error - end; -shortcut_specific_label([I|Is], Fail, Prev) -> - case normalize_op(I) of - error -> - error; - {Normalized,Fail} -> - case will_succeed(Prev, Normalized) of - no -> - %% Will branch to FailLabel. - Fail; - yes -> - %% Will definitely never branch. - shortcut_specific_label(Is, Fail, Prev); - maybe -> - %% May branch, but still OK since it will branch - %% to FailLabel. - shortcut_specific_label(Is, Fail, Prev) - end; - {Normalized,_} -> - %% This test instruction will branch to a different - %% fail label, if it branches at all. - case will_succeed(Prev, Normalized) of - yes -> - %% Still OK, since the branch will never be - %% taken. - shortcut_specific_label(Is, Fail, Prev); - no -> - %% Give up. The branch will definitely be taken - %% to a different fail label. - error; - maybe -> - %% Give up. If the branch is taken, it will be - %% to a different fail label. - error - end - end. - - -%% shortcut_selectval(List, Reg, Fail, PrevCond) -> FailLabel | error -%% Try to shortcut a selectval instruction. A selectval instruction -%% is equivalent to the following instruction sequence: -%% -%% is_ne_exact L1 Reg Value1 -%% . -%% . -%% . -%% is_ne_exact LN Reg ValueN -%% jump DefaultFailLabel -%% -shortcut_selectval([Val,{f,Lbl}|T], R, Fail, Prev) -> - case will_succeed(Prev, {'=/=',R,get_literal(Val)}) of - yes -> shortcut_selectval(T, R, Fail, Prev); - no -> Lbl; - maybe -> error - end; -shortcut_selectval([], _, Fail, _) -> Fail. - -%% will_succeed(PrevCondition, Condition) -> yes | no | maybe -%% PrevCondition is a condition known to be true. This function -%% will tell whether Condition will succeed. - -will_succeed({Op1,Reg,A}, {Op2,Reg,B}) -> - will_succeed_1(Op1, A, Op2, B); -will_succeed({'=:=',Reg,{literal,A}}, {TypeTest,Reg}) -> - case erlang:TypeTest(A) of - false -> no; - true -> yes - end; -will_succeed({_,_,_}, maybe) -> - maybe; -will_succeed({_,_,_}, Test) when is_tuple(Test) -> - maybe. - -will_succeed_1('=:=', A, '<', B) -> - if - B =< A -> no; - true -> yes - end; -will_succeed_1('=:=', A, '=<', B) -> - if - B < A -> no; - true -> yes - end; -will_succeed_1('=:=', A, '=:=', B) -> - if - A =:= B -> yes; - true -> no - end; -will_succeed_1('=:=', A, '=/=', B) -> - if - A =:= B -> no; - true -> yes - end; -will_succeed_1('=:=', A, '>=', B) -> - if - B > A -> no; - true -> yes - end; -will_succeed_1('=:=', A, '>', B) -> - if - B >= A -> no; - true -> yes - end; - -will_succeed_1('=/=', A, '=/=', B) when A =:= B -> yes; -will_succeed_1('=/=', A, '=:=', B) when A =:= B -> no; - -will_succeed_1('<', A, '=:=', B) when B >= A -> no; -will_succeed_1('<', A, '=/=', B) when B >= A -> yes; -will_succeed_1('<', A, '<', B) when B >= A -> yes; -will_succeed_1('<', A, '=<', B) when B > A -> yes; -will_succeed_1('<', A, '>=', B) when B > A -> no; -will_succeed_1('<', A, '>', B) when B >= A -> no; - -will_succeed_1('=<', A, '=:=', B) when B > A -> no; -will_succeed_1('=<', A, '=/=', B) when B > A -> yes; -will_succeed_1('=<', A, '<', B) when B > A -> yes; -will_succeed_1('=<', A, '=<', B) when B >= A -> yes; -will_succeed_1('=<', A, '>=', B) when B > A -> no; -will_succeed_1('=<', A, '>', B) when B >= A -> no; - -will_succeed_1('>=', A, '=:=', B) when B < A -> no; -will_succeed_1('>=', A, '=/=', B) when B < A -> yes; -will_succeed_1('>=', A, '<', B) when B =< A -> no; -will_succeed_1('>=', A, '=<', B) when B < A -> no; -will_succeed_1('>=', A, '>=', B) when B =< A -> yes; -will_succeed_1('>=', A, '>', B) when B < A -> yes; - -will_succeed_1('>', A, '=:=', B) when B =< A -> no; -will_succeed_1('>', A, '=/=', B) when B =< A -> yes; -will_succeed_1('>', A, '<', B) when B =< A -> no; -will_succeed_1('>', A, '=<', B) when B < A -> no; -will_succeed_1('>', A, '>=', B) when B =< A -> yes; -will_succeed_1('>', A, '>', B) when B < A -> yes; - -will_succeed_1(_, _, _, _) -> maybe. - -%% normalize_op(Instruction) -> {Normalized,FailLabel} | error -%% Normalized = {Operator,Register,Literal} | -%% {TypeTest,Register} | -%% maybe -%% Operation = '<' | '=<' | '=:=' | '=/=' | '>=' | '>' -%% TypeTest = is_atom | is_integer ... -%% Literal = {literal,Term} -%% -%% Normalize a relational operator to facilitate further -%% comparisons between operators. Always make the register -%% operand the first operand. Thus the following instruction: -%% -%% {test,is_ge,{f,99},{integer,13},{x,0}} -%% -%% will be normalized to: -%% -%% {'=<',{x,0},{literal,13}} -%% -%% NOTE: Bit syntax test instructions are scary. They may change the -%% state of match contexts and update registers, so we don't dare -%% mess with them. - -normalize_op({test,is_ge,{f,Fail},Ops}) -> - normalize_op_1('>=', Ops, Fail); -normalize_op({test,is_lt,{f,Fail},Ops}) -> - normalize_op_1('<', Ops, Fail); -normalize_op({test,is_eq_exact,{f,Fail},Ops}) -> - normalize_op_1('=:=', Ops, Fail); -normalize_op({test,is_ne_exact,{f,Fail},Ops}) -> - normalize_op_1('=/=', Ops, Fail); -normalize_op({test,Op,{f,Fail},[R]}) -> - case erl_internal:new_type_test(Op, 1) of - true -> {{Op,R},Fail}; - false -> {maybe,Fail} - end; -normalize_op({test,_,{f,Fail},_}=I) -> - case beam_utils:is_pure_test(I) of - true -> {maybe,Fail}; - false -> error - end; -normalize_op(_) -> - error. - -normalize_op_1(Op, [Op1,Op2], Fail) -> - case {get_literal(Op1),get_literal(Op2)} of - {error,error} -> - %% Both operands are registers. - {maybe,Fail}; - {error,Lit} -> - {{Op,Op1,Lit},Fail}; - {Lit,error} -> - {{turn_op(Op),Op2,Lit},Fail}; - {_,_} -> - %% Both operands are literals. Can probably only - %% happen if the Core Erlang optimizations passes were - %% turned off, so don't bother trying to do something - %% smart here. - {maybe,Fail} - end. - -turn_op('<') -> '>'; -turn_op('>=') -> '=<'; -turn_op('=:='=Op) -> Op; -turn_op('=/='=Op) -> Op. - -negate_op('>=') -> '<'; -negate_op('<') -> '>='; -negate_op('=<') -> '>'; -negate_op('>') -> '=<'; -negate_op('=:=') -> '=/='; -negate_op('=/=') -> '=:='. - -get_literal({atom,Val}) -> - {literal,Val}; -get_literal({integer,Val}) -> - {literal,Val}; -get_literal({float,Val}) -> - {literal,Val}; -get_literal(nil) -> - {literal,[]}; -get_literal({literal,_}=Lit) -> - Lit; -get_literal({_,_}) -> error. - - -%%% -%%% Removing stores to Y registers is not always safe -%%% if there is an instruction that causes an exception -%%% within a catch. In practice, there are few or no -%%% opportunities for removing stores to Y registers anyway -%%% if sys_core_fold has been run. -%%% - -is_killed_at({x,_}=Reg, Lbl, D) -> - beam_utils:is_killed_at(Reg, Lbl, D); -is_killed_at({y,_}, _, _) -> - false. diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl index 42b4cdaf4f..6d0a8db2dc 100644 --- a/lib/compiler/src/beam_jump.erl +++ b/lib/compiler/src/beam_jump.erl @@ -22,7 +22,7 @@ -module(beam_jump). -export([module/2, - is_unreachable_after/1,is_exit_instruction/1, + is_exit_instruction/1, remove_unused_labels/1]). %%% The following optimisations are done: @@ -128,27 +128,123 @@ %%% on the program state. %%% --import(lists, [reverse/1,reverse/2,foldl/3]). +-import(lists, [foldl/3,mapfoldl/3,reverse/1,reverse/2]). -type instruction() :: beam_utils:instruction(). -spec module(beam_utils:module_code(), [compile:option()]) -> {'ok',beam_utils:module_code()}. -module({Mod,Exp,Attr,Fs0,Lc}, _Opt) -> - Fs = [function(F) || F <- Fs0], +module({Mod,Exp,Attr,Fs0,Lc0}, _Opt) -> + {Fs,Lc} = mapfoldl(fun function/2, Lc0, Fs0), {ok,{Mod,Exp,Attr,Fs,Lc}}. %% function(Function) -> Function' %% Optimize jumps and branches. %% %% NOTE: This function assumes that there are no labels inside blocks. -function({function,Name,Arity,CLabel,Asm0}) -> - Asm1 = share(Asm0), - Asm2 = move(Asm1), - Asm3 = opt(Asm2, CLabel), - Asm = remove_unused_labels(Asm3), - {function,Name,Arity,CLabel,Asm}. +function({function,Name,Arity,CLabel,Asm0}, Lc0) -> + Asm1 = eliminate_moves(Asm0), + {Asm2,Lc} = insert_labels(Asm1, Lc0, []), + Asm3 = share(Asm2), + Asm4 = move(Asm3), + Asm5 = opt(Asm4, CLabel), + Asm = remove_unused_labels(Asm5), + {{function,Name,Arity,CLabel,Asm},Lc}. + +%%% +%%% Scan instructions in execution order and remove redundant 'move' +%%% instructions. 'move' instructions are redundant if we know that +%%% the register already contains the value being assigned, as in the +%%% following code: +%%% +%%% select_val Register FailLabel [... Literal => L1...] +%%% . +%%% . +%%% . +%%% L1: move Literal Register +%%% + +eliminate_moves(Is) -> + eliminate_moves(Is, #{}, []). + +eliminate_moves([{select,select_val,Reg,_,List}=I|Is], D0, Acc) -> + D = update_value_dict(List, Reg, D0), + eliminate_moves(Is, D, [I|Acc]); +eliminate_moves([{label,Lbl},{block,[{set,[Dst],[Lit],move}|BlkIs]}=Blk0|Is], + D, Acc0) -> + Acc = [{label,Lbl}|Acc0], + case already_has_value(Lit, Lbl, Dst, D) andalso + no_fallthrough(Acc0) of + true -> + %% Remove redundant 'move' instruction. + Blk = {block,BlkIs}, + eliminate_moves([Blk|Is], D, Acc); + false -> + %% Keep 'move' instruction. + eliminate_moves([Blk0|Is], D, Acc) + end; +eliminate_moves([{block,[]}|Is], D, Acc) -> + %% Empty blocks can prevent further jump optimizations. + eliminate_moves(Is, D, Acc); +eliminate_moves([I|Is], D0, Acc) -> + D = update_unsafe_labels(I, D0), + eliminate_moves(Is, D, [I|Acc]); +eliminate_moves([], _, Acc) -> reverse(Acc). + +no_fallthrough([I|_]) -> + is_unreachable_after(I). + +already_has_value(Lit, Lbl, Reg, D) -> + Key = {Lbl,Reg}, + case D of + #{Lbl:=unsafe} -> + false; + #{Key:=Lit} -> + true; + #{} -> + false + end. + +update_value_dict([Lit,{f,Lbl}|T], Reg, D0) -> + Key = {Lbl,Reg}, + D = case D0 of + #{Key := inconsistent} -> D0; + #{Key := _} -> D0#{Key := inconsistent}; + _ -> D0#{Key => Lit} + end, + update_value_dict(T, Reg, D); +update_value_dict([], _, D) -> D. + +update_unsafe_labels(I, D) -> + Ls = instr_labels(I), + update_unsafe_labels_1(Ls, D). + +update_unsafe_labels_1([L|Ls], D) -> + update_unsafe_labels_1(Ls, D#{L=>unsafe}); +update_unsafe_labels_1([], D) -> D. + +%%% +%%% It seems to be useful to insert extra labels after certain +%%% test instructions. This used to be done by beam_dead. +%%% + +insert_labels([{test,Op,_,_}=I|Is], Lc, Acc) -> + Useful = case Op of + is_lt -> true; + is_ge -> true; + is_eq_exact -> true; + is_ne_exact -> true; + _ -> false + end, + case Useful of + false -> insert_labels(Is, Lc, [I|Acc]); + true -> insert_labels(Is, Lc+1, [{label,Lc},I|Acc]) + end; +insert_labels([I|Is], Lc, Acc) -> + insert_labels(Is, Lc, [I|Acc]); +insert_labels([], Lc, Acc) -> + {reverse(Acc),Lc}. %%% %%% (1) We try to share the code for identical code segments by replacing all @@ -571,58 +667,76 @@ drop_upto_label([{label,_}|_]=Is) -> Is; drop_upto_label([_|Is]) -> drop_upto_label(Is); drop_upto_label([]) -> []. -%% ulbl(Instruction, UsedGbSet) -> UsedGbSet' -%% Update the gb_set UsedGbSet with any function-local labels +%% ulbl(Instruction, UsedCerlSet) -> UsedCerlSet' +%% Update the cerl_set UsedCerlSet with any function-local labels %% (i.e. not with labels in call instructions) referenced by %% the instruction Instruction. %% %% NOTE: This function does NOT look for labels inside blocks. -ulbl({test,_,Fail,_}, Used) -> - mark_used(Fail, Used); -ulbl({test,_,Fail,_,_,_}, Used) -> - mark_used(Fail, Used); -ulbl({select,_,_,Fail,Vls}, Used) -> - mark_used_list(Vls, mark_used(Fail, Used)); -ulbl({'try',_,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({'catch',_,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({jump,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({loop_rec,Lbl,_}, Used) -> - mark_used(Lbl, Used); -ulbl({loop_rec_end,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({wait,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({wait_timeout,Lbl,_To}, Used) -> - mark_used(Lbl, Used); -ulbl({bif,_Name,Lbl,_As,_R}, Used) -> - mark_used(Lbl, Used); -ulbl({gc_bif,_Name,Lbl,_Live,_As,_R}, Used) -> - mark_used(Lbl, Used); -ulbl({bs_init,Lbl,_,_,_,_}, Used) -> - mark_used(Lbl, Used); -ulbl({bs_put,Lbl,_,_}, Used) -> - mark_used(Lbl, Used); -ulbl({put_map,Lbl,_Op,_Src,_Dst,_Live,_List}, Used) -> - mark_used(Lbl, Used); -ulbl({get_map_elements,Lbl,_Src,_List}, Used) -> - mark_used(Lbl, Used); -ulbl({recv_mark,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({recv_set,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl({fcheckerror,Lbl}, Used) -> - mark_used(Lbl, Used); -ulbl(_, Used) -> Used. - -mark_used({f,0}, Used) -> Used; -mark_used({f,L}, Used) -> cerl_sets:add_element(L, Used). - -mark_used_list([{f,L}|T], Used) -> - mark_used_list(T, cerl_sets:add_element(L, Used)); -mark_used_list([_|T], Used) -> - mark_used_list(T, Used); -mark_used_list([], Used) -> Used. +ulbl(I, Used) -> + case instr_labels(I) of + [] -> + Used; + [Lbl] -> + cerl_sets:add_element(Lbl, Used); + [_|_]=L -> + ulbl_list(L, Used) + end. + +ulbl_list([L|Ls], Used) -> + ulbl_list(Ls, cerl_sets:add_element(L, Used)); +ulbl_list([], Used) -> Used. + +-spec instr_labels(Instruction) -> Labels when + Instruction :: instruction(), + Labels :: [beam_asm:label()]. + +instr_labels({test,_,Fail,_}) -> + do_instr_labels(Fail); +instr_labels({test,_,Fail,_,_,_}) -> + do_instr_labels(Fail); +instr_labels({select,_,_,Fail,Vls}) -> + do_instr_labels_list(Vls, do_instr_labels(Fail)); +instr_labels({'try',_,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({'catch',_,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({jump,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({loop_rec,Lbl,_}) -> + do_instr_labels(Lbl); +instr_labels({loop_rec_end,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({wait,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({wait_timeout,Lbl,_To}) -> + do_instr_labels(Lbl); +instr_labels({bif,_Name,Lbl,_As,_R}) -> + do_instr_labels(Lbl); +instr_labels({gc_bif,_Name,Lbl,_Live,_As,_R}) -> + do_instr_labels(Lbl); +instr_labels({bs_init,Lbl,_,_,_,_}) -> + do_instr_labels(Lbl); +instr_labels({bs_put,Lbl,_,_}) -> + do_instr_labels(Lbl); +instr_labels({put_map,Lbl,_Op,_Src,_Dst,_Live,_List}) -> + do_instr_labels(Lbl); +instr_labels({get_map_elements,Lbl,_Src,_List}) -> + do_instr_labels(Lbl); +instr_labels({recv_mark,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({recv_set,Lbl}) -> + do_instr_labels(Lbl); +instr_labels({fcheckerror,Lbl}) -> + do_instr_labels(Lbl); +instr_labels(_) -> []. + +do_instr_labels({f,0}) -> []; +do_instr_labels({f,F}) -> [F]. + +do_instr_labels_list([{f,F}|T], Acc) -> + do_instr_labels_list(T, [F|Acc]); +do_instr_labels_list([_|T], Acc) -> + do_instr_labels_list(T, Acc); +do_instr_labels_list([], Acc) -> Acc. diff --git a/lib/compiler/src/beam_peep.erl b/lib/compiler/src/beam_peep.erl index 74da6aa704..2323a439e9 100644 --- a/lib/compiler/src/beam_peep.erl +++ b/lib/compiler/src/beam_peep.erl @@ -112,6 +112,10 @@ peep([{select,Op,R,F,Vls0}|Is], SeenTests0, Acc0) -> %% Single value left. Convert to regular test Is1 = [{test,test_arity,F,[R,Arity]},{jump,Lbl}|Is], peep(Is1, SeenTests0, Acc0); + [{atom,B1},Lbl,{atom,B2},Lbl] when B1 =:= not B2 -> + %% Replace with is_boolean test. + Is1 = [{test,is_boolean,F,[R]},{jump,Lbl}|Is], + peep(Is1, SeenTests0, Acc0); [_|_]=Vls -> I = {select,Op,R,F,Vls}, peep(Is, gb_sets:empty(), [I|Acc0]) diff --git a/lib/compiler/src/beam_split.erl b/lib/compiler/src/beam_split.erl deleted file mode 100644 index 7b18946ae0..0000000000 --- a/lib/compiler/src/beam_split.erl +++ /dev/null @@ -1,90 +0,0 @@ -%% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2011-2018. All Rights Reserved. -%% -%% Licensed under the Apache License, Version 2.0 (the "License"); -%% you may not use this file except in compliance with the License. -%% You may obtain a copy of the License at -%% -%% http://www.apache.org/licenses/LICENSE-2.0 -%% -%% Unless required by applicable law or agreed to in writing, software -%% distributed under the License is distributed on an "AS IS" BASIS, -%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -%% See the License for the specific language governing permissions and -%% limitations under the License. -%% -%% %CopyrightEnd% -%% - --module(beam_split). --export([module/2]). - --import(lists, [reverse/1]). - --spec module(beam_utils:module_code(), [compile:option()]) -> - {'ok',beam_utils:module_code()}. - -module({Mod,Exp,Attr,Fs0,Lc}, _Opts) -> - Fs = [split_blocks(F) || F <- Fs0], - {ok,{Mod,Exp,Attr,Fs,Lc}}. - -%% We must split the basic block when we encounter instructions with labels, -%% such as catches and BIFs. All labels must be visible outside the blocks. - -split_blocks({function,Name,Arity,CLabel,Is0}) -> - Is = split_blocks(Is0, []), - {function,Name,Arity,CLabel,Is}. - -split_blocks([{block,Bl}|Is], Acc0) -> - Acc = split_block(Bl, [], Acc0), - split_blocks(Is, Acc); -split_blocks([I|Is], Acc) -> - split_blocks(Is, [I|Acc]); -split_blocks([], Acc) -> reverse(Acc). - -split_block([{set,[R],As,{bif,N,{f,Lbl}=Fail}}|Is], Bl, Acc) when Lbl =/= 0 -> - split_block(Is, [], [{bif,N,Fail,As,R}|make_block(Bl, Acc)]); -split_block([{set,[],[],{line,_}=Line}, - {set,[R],As,{bif,raise,{f,_}=Fail}}|Is], Bl, Acc) -> - split_block(Is, [], [{bif,raise,Fail,As,R},Line|make_block(Bl, Acc)]); -split_block([{set,[R],As,{alloc,Live,{gc_bif,N,{f,Lbl}=Fail}}}|Is], Bl, Acc) - when Lbl =/= 0 -> - split_block(Is, [], [{gc_bif,N,Fail,Live,As,R}|make_block(Bl, Acc)]); -split_block([{set,[D],[S|Puts],{alloc,R,{put_map,Op,{f,Lbl}=Fail}}}|Is], - Bl, Acc) when Lbl =/= 0 -> - split_block(Is, [], [{put_map,Fail,Op,S,D,R,{list,Puts}}| - make_block(Bl, Acc)]); -split_block([{set,[R],[],{try_catch,Op,L}}|Is], Bl, Acc) -> - split_block(Is, [], [{Op,R,L}|make_block(Bl, Acc)]); -split_block([I|Is], Bl, Acc) -> - split_block(Is, [I|Bl], Acc); -split_block([], Bl, Acc) -> make_block(Bl, Acc). - -make_block([], Acc) -> Acc; -make_block([{set,[D],Ss,{bif,Op,Fail}}|Bl]=Bl0, Acc) -> - %% If the last instruction in the block is a comparison or boolean operator - %% (such as '=:='), move it out of the block to facilitate further - %% optimizations. - Arity = length(Ss), - case erl_internal:comp_op(Op, Arity) orelse - erl_internal:new_type_test(Op, Arity) orelse - erl_internal:bool_op(Op, Arity) of - false -> - [{block,reverse(Bl0)}|Acc]; - true -> - I = {bif,Op,Fail,Ss,D}, - case Bl =:= [] of - true -> [I|Acc]; - false -> [I,{block,reverse(Bl)}|Acc] - end - end; -make_block([{set,[Dst],[Src],move}|Bl], Acc) -> - %% Make optimization of {move,Src,Dst}, {jump,...} possible. - I = {move,Src,Dst}, - case Bl =:= [] of - true -> [I|Acc]; - false -> [I,{block,reverse(Bl)}|Acc] - end; -make_block(Bl, Acc) -> [{block,reverse(Bl)}|Acc]. diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl index a2766a0501..fc13ba06de 100644 --- a/lib/compiler/src/beam_ssa.erl +++ b/lib/compiler/src/beam_ssa.erl @@ -27,11 +27,14 @@ fold_instrs_rpo/4, linearize/1, mapfold_instrs_rpo/4, + normalize/1, + no_side_effect/1, predecessors/1, rename_vars/3, rpo/1,rpo/2, split_blocks/3, successors/1,successors/2, + trim_unreachable/1, update_phi_labels/4,used/1]). -export_type([b_module/0,b_function/0,b_blk/0,b_set/0, @@ -102,7 +105,7 @@ -type cg_prim_op() :: 'bs_get' | 'bs_match_string' | 'bs_restore' | 'bs_skip' | 'copy' | 'put_tuple_arity' | 'put_tuple_element'. --import(lists, [foldl/3,mapfoldl/3,reverse/1]). +-import(lists, [foldl/3,keyfind/3,mapfoldl/3,member/2,reverse/1]). -spec add_anno(Key, Value, Construct) -> Construct when Key :: atom(), @@ -150,6 +153,37 @@ clobbers_xregs(#b_set{op=Op}) -> _ -> false end. +%% no_side_effect(#b_set{}) -> true|false. +%% Test whether this instruction has no side effect and thus is safe +%% not to execute if its value is not used. Note that even if `true` +%% is returned, the instruction could still be impure (e.g. bif:get). + +-spec no_side_effect(b_set()) -> boolean(). + +no_side_effect(#b_set{op=Op}) -> + case Op of + {bif,_} -> true; + {float,get} -> true; + bs_init -> true; + bs_extract -> true; + bs_match -> true; + bs_start_match -> true; + bs_test_tail -> true; + bs_put -> true; + extract -> true; + get_hd -> true; + get_tl -> true; + get_tuple_element -> true; + has_map_field -> true; + is_nonempty_list -> true; + is_tagged_tuple -> true; + put_map -> true; + put_list -> true; + put_tuple -> true; + succeeded -> true; + _ -> false + end. + -spec predecessors(Blocks) -> #{BlockNumber:=[Predecessor]} when Blocks :: block_map(), BlockNumber :: label(), @@ -180,6 +214,69 @@ successors(#b_blk{last=Terminator}) -> [] end. +%% normalize(Instr0) -> Instr. +%% Normalize instructions to help optimizations. +%% +%% For commutative operators (such as '+' and 'or'), always +%% place a variable operand before a literal operand. +%% +%% Normalize #b_br{} to one of the following forms: +%% +%% #b_br{b_literal{val=true},succ=Label,fail=Label} +%% #b_br{b_var{},succ=Label1,fail=Label2} where Label1 =/= Label2 +%% +%% Simplify a #b_switch{} with a literal argument to a #b_br{}. +%% +%% Simplify a #b_switch{} with a variable argument and an empty +%% switch list to a #b_br{}. + +-spec normalize(b_set() | terminator()) -> + b_set() | terminator(). + +normalize(#b_set{op={bif,Bif},args=Args}=Set) -> + case {is_commutative(Bif),Args} of + {false,_} -> + Set; + {true,[#b_literal{}=Lit,#b_var{}=Var]} -> + Set#b_set{args=[Var,Lit]}; + {true,_} -> + Set + end; +normalize(#b_set{}=Set) -> + Set; +normalize(#b_br{}=Br) -> + case Br of + #b_br{bool=Bool,succ=Same,fail=Same} -> + case Bool of + #b_literal{val=true} -> + Br; + _ -> + Br#b_br{bool=#b_literal{val=true}} + end; + #b_br{bool=#b_literal{val=true},succ=Succ} -> + Br#b_br{fail=Succ}; + #b_br{bool=#b_literal{val=false},fail=Fail} -> + Br#b_br{bool=#b_literal{val=true},succ=Fail}; + #b_br{} -> + Br + end; +normalize(#b_switch{arg=Arg,fail=Fail,list=List}=Sw) -> + case Arg of + #b_literal{} -> + case keyfind(Arg, 1, List) of + false -> + #b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail}; + {Arg,L} -> + #b_br{bool=#b_literal{val=true},succ=L,fail=L} + end; + #b_var{} when List =:= [] -> + #b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail}; + #b_var{} -> + Sw + end; +normalize(#b_ret{}=Ret) -> + Ret. + -spec successors(label(), block_map()) -> [label()]. successors(L, Blocks) -> @@ -312,14 +409,19 @@ fold_po(Fun, From, Acc0, Blocks) -> %% linearize(Blocks) -> [{BlockLabel,#b_blk{}}]. %% Linearize the intermediate representation of the code. +%% Unreachable blocks will be discarded, and phi nodes will +%% be adjusted so that they no longer refers to discarded +%% blocks or to blocks that no longer are predecessors of +%% the phi node block. -spec linearize(Blocks) -> Linear when Blocks :: block_map(), Linear :: [{label(),b_blk()}]. linearize(Blocks) -> - Seen = gb_sets:empty(), - {Linear,_} = linearize_1([0], Blocks, Seen, []), + Seen = cerl_sets:new(), + {Linear0,_} = linearize_1([0], Blocks, Seen, []), + Linear = fix_phis(Linear0, #{}), Linear. -spec rpo(Blocks) -> [Label] when @@ -335,7 +437,7 @@ rpo(Blocks) -> Labels :: [label()]. rpo(From, Blocks) -> - Seen = gb_sets:empty(), + Seen = cerl_sets:new(), {Ls,_} = rpo_1(From, Blocks, Seen, []), Ls. @@ -346,7 +448,7 @@ rename_vars(Rename, From, Blocks) when is_list(Rename) -> rename_vars(maps:from_list(Rename), From, Blocks); rename_vars(Rename, From, Blocks) when is_map(Rename)-> Top = rpo(From, Blocks), - Preds = gb_sets:from_list(Top), + Preds = cerl_sets:from_list(Top), F = fun(#b_set{op=phi,args=Args0}=Set) -> Args = rename_phi_vars(Args0, Preds, Rename), Set#b_set{args=Args}; @@ -379,6 +481,19 @@ split_blocks(P, Blocks, Count) -> Ls = beam_ssa:rpo(Blocks), split_blocks_1(Ls, P, Blocks, Count). +-spec trim_unreachable(Blocks0) -> Blocks when + Blocks0 :: block_map(), + Blocks :: block_map(). + +%% trim_unreachable(Blocks0) -> Blocks. +%% Remove all unreachable blocks. Adjust all phi nodes so +%% they don't refer to blocks that has been removed or no +%% no longer branch to the phi node in question. + +trim_unreachable(Blocks) -> + %% Could perhaps be optimized if there is any need. + maps:from_list(linearize(Blocks)). + %% update_phi_labels([BlockLabel], Old, New, Blocks0) -> Blocks. %% In the given blocks, replace label Old in with New in all %% phi nodes. This is useful after merging or splitting @@ -424,6 +539,20 @@ used(_) -> []. %%% Internal functions. %%% +is_commutative('and') -> true; +is_commutative('or') -> true; +is_commutative('xor') -> true; +is_commutative('band') -> true; +is_commutative('bor') -> true; +is_commutative('bxor') -> true; +is_commutative('+') -> true; +is_commutative('*') -> true; +is_commutative('=:=') -> true; +is_commutative('==') -> true; +is_commutative('=/=') -> true; +is_commutative('/=') -> true; +is_commutative(_) -> false. + def_used_1([#b_blk{is=Is,last=Last}|Bs], Preds, Def0, Used0) -> {Def,Used1} = def_used_is(Is, Preds, Def0, Used0), Used = gb_sets:union(gb_sets:from_list(used(Last)), Used1), @@ -501,11 +630,11 @@ flatmapfold_instrs_rpo_1([], _, Blocks, Acc) -> {Blocks,Acc}. linearize_1([L|Ls], Blocks, Seen0, Acc0) -> - case gb_sets:is_member(L, Seen0) of + case cerl_sets:is_element(L, Seen0) of true -> linearize_1(Ls, Blocks, Seen0, Acc0); false -> - Seen1 = gb_sets:insert(L, Seen0), + Seen1 = cerl_sets:add_element(L, Seen0), Block = maps:get(L, Blocks), Successors = successors(Block), {Acc,Seen} = linearize_1(Successors, Blocks, Seen1, Acc0), @@ -514,13 +643,40 @@ linearize_1([L|Ls], Blocks, Seen0, Acc0) -> linearize_1([], _, Seen, Acc) -> {Acc,Seen}. +fix_phis([{L,Blk0}|Bs], S) -> + Blk = case Blk0 of + #b_blk{is=[#b_set{op=phi}|_]=Is0} -> + Is = fix_phis_1(Is0, L, S), + Blk0#b_blk{is=Is}; + #b_blk{} -> + Blk0 + end, + Successors = successors(Blk), + [{L,Blk}|fix_phis(Bs, S#{L=>Successors})]; +fix_phis([], _) -> []. + +fix_phis_1([#b_set{op=phi,args=Args0}=I|Is], L, S) -> + Args = [{Val,Pred} || {Val,Pred} <- Args0, + is_successor(L, Pred, S)], + [I#b_set{args=Args}|fix_phis_1(Is, L, S)]; +fix_phis_1(Is, _, _) -> Is. + +is_successor(L, Pred, S) -> + case S of + #{Pred:=Successors} -> + member(L, Successors); + #{} -> + %% This block has been removed. + false + end. + rpo_1([L|Ls], Blocks, Seen0, Acc0) -> - case gb_sets:is_member(L, Seen0) of + case cerl_sets:is_element(L, Seen0) of true -> rpo_1(Ls, Blocks, Seen0, Acc0); false -> Block = maps:get(L, Blocks), - Seen1 = gb_sets:insert(L, Seen0), + Seen1 = cerl_sets:add_element(L, Seen0), Successors = successors(Block), {Acc,Seen} = rpo_1(Successors, Blocks, Seen1, Acc0), rpo_1(Ls, Blocks, Seen, [L|Acc]) @@ -540,7 +696,7 @@ rename_var(#b_remote{mod=Mod0,name=Name0}=Remote, Rename) -> rename_var(Old, _) -> Old. rename_phi_vars([{Var,L}|As], Preds, Ren) -> - case gb_sets:is_member(L, Preds) of + case cerl_sets:is_element(L, Preds) of true -> [{rename_var(Var, Ren),L}|rename_phi_vars(As, Preds, Ren)]; false -> diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl index 006c41c0e0..40c2d8c07a 100644 --- a/lib/compiler/src/beam_ssa_codegen.erl +++ b/lib/compiler/src/beam_ssa_codegen.erl @@ -1180,6 +1180,16 @@ cg_copy_1([#cg_set{dst=Dst0,args=Args}|T], St) -> end; cg_copy_1([], _St) -> []. +bif_to_test('and', [V1,V2], Fail) -> + [{test,is_eq_exact,Fail,[V1,{atom,true}]}, + {test,is_eq_exact,Fail,[V2,{atom,true}]}]; +bif_to_test('or', [V1,V2], {f,Lbl}=Fail) when Lbl =/= 0 -> + %% Labels are spaced 2 apart. We can create a new + %% label by incrementing the Fail label. + SuccLabel = Lbl + 1, + [{test,is_eq_exact,{f,SuccLabel},[V1,{atom,false}]}, + {test,is_eq_exact,Fail,[V2,{atom,true}]}, + {label,SuccLabel}]; bif_to_test('not', [Var], Fail) -> [{test,is_eq_exact,Fail,[Var,{atom,false}]}]; bif_to_test(Name, Args, Fail) -> @@ -1260,21 +1270,29 @@ cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=[#b_local{}=Func0|Args0]}, Call = build_call(call, Arity, {f,FuncLbl}, Context, Dst), Is = setup_args(Args, Anno, Context, St) ++ Line ++ Call, {Is,St}; -cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=[#b_remote{}=Func0|Args0]}, +cg_call(#cg_set{anno=Anno0,op=call,dst=Dst0,args=[#b_remote{}=Func0|Args0]}, Where, Context, St) -> [Dst|Args] = beam_args([Dst0|Args0], St), #b_remote{mod=Mod0,name=Name0,arity=Arity} = Func0, case {beam_arg(Mod0, St),beam_arg(Name0, St)} of {{atom,Mod},{atom,Name}} -> Func = {extfunc,Mod,Name,Arity}, - Line = call_line(Where, Func, Anno), + Line = call_line(Where, Func, Anno0), Call = build_call(call_ext, Arity, Func, Context, Dst), + Anno = case erl_bifs:is_exit_bif(Mod, Name, Arity) of + true -> + %% There is no need to kill Y registers + %% before calling an exit BIF. + maps:remove(kill_yregs, Anno0); + false -> + Anno0 + end, Is = setup_args(Args, Anno, Context, St) ++ Line ++ Call, {Is,St}; {Mod,Name} -> Apply = build_apply(Arity, Context, Dst), - Is = setup_args(Args++[Mod,Name], Anno, Context, St) ++ - [line(Anno)] ++ Apply, + Is = setup_args(Args++[Mod,Name], Anno0, Context, St) ++ + [line(Anno0)] ++ Apply, {Is,St} end; cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=Args0}, @@ -1785,7 +1803,9 @@ is_gc_bif(Bif, Args) -> %% new_label(St) -> {L,St}. new_label(#cg{lcount=Next}=St) -> - {Next,St#cg{lcount=Next+1}}. + %% Advance the label counter by 2 to allow us to create + %% a label for 'or' by incrementing an existing label. + {Next,St#cg{lcount=Next+2}}. %% call_line(tail|body, Func, Anno) -> [] | [{line,...}]. %% Produce a line instruction if it will be needed by the diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl new file mode 100644 index 0000000000..7cdb4315fe --- /dev/null +++ b/lib/compiler/src/beam_ssa_dead.erl @@ -0,0 +1,1001 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2018. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% +%% Dead code is code that is executed but has no effect. This +%% optimization pass either removes dead code or jumps around it, +%% potentially making it unreachable so that it can be dropped +%% the next time beam_ssa:linearize/1 is called. +%% + +-module(beam_ssa_dead). +-export([opt/1]). + +-include("beam_ssa.hrl"). +-import(lists, [append/1,last/1,member/2,takewhile/2,reverse/1]). + +-type used_vars() :: #{beam_ssa:label():=ordsets:ordset(beam_ssa:var_name())}. + +-type basic_type_test() :: atom() | {'is_tagged_tuple',pos_integer(),atom()}. +-type type_test() :: basic_type_test() | {'not',basic_type_test()}. +-type op_name() :: atom(). +-type basic_rel_op() :: {op_name(),beam_ssa:b_var(),beam_ssa:value()} | + {basic_type_test(),beam_ssa:value()}. +-type rel_op() :: {op_name(),beam_ssa:b_var(),beam_ssa:value()} | + {type_test(),beam_ssa:value()}. + +-record(st, + {bs :: beam_ssa:block_map(), + us :: used_vars(), + skippable :: #{beam_ssa:label():='true'}, + rel_op=none :: 'none' | rel_op(), + target=any :: 'any' | 'one_way' | beam_ssa:label() + }). + +-spec opt([{Label0,Block0}]) -> [{Label,Block}] when + Label0 :: beam_ssa:label(), + Block0 :: beam_ssa:b_blk(), + Label :: beam_ssa:label(), + Block :: beam_ssa:b_blk(). + +opt(Linear) -> + {Used,Skippable} = used_vars(Linear), + Blocks0 = maps:from_list(Linear), + St0 = #st{bs=Blocks0,us=Used,skippable=Skippable}, + St = shortcut_opt(St0), + #st{bs=Blocks} = combine_eqs(St), + beam_ssa:linearize(Blocks). + +%%% +%%% Shortcut br/switch targets. +%%% +%%% A br/switch may branch to another br/switch that in turn always +%%% branches to another target. Rewrite br/switch to refer to the +%%% ultimate targets directly. That will save execution time, but +%%% could also reduce the size of the code if some of the original +%%% targets become unreachable and be deleted. +%%% +%%% When rewriting branches, we must be careful not to skip instructions +%%% that have side effects or that bind variables that will be used +%%% at the new target. +%%% +%%% We must also avoid branching to phi nodes. The reason is +%%% twofold. First, we might create a critical edge which is strictly +%%% forbidden. Second, there will be a branch from a block that is not +%%% listed in the list of predecessors in the phi node. Those +%%% limitations could probably be overcome, but it is not clear how +%%% much that would improve the code. +%%% + +shortcut_opt(#st{bs=Blocks}=St) -> + %% Processing the blocks in reverse post order seems to give more + %% opportunities for optimizations compared to post order. (Based on + %% running scripts/diffable with both PO and RPO and looking at + %% the diff.) + Ls = beam_ssa:rpo(Blocks), + shortcut_opt(Ls, #{from=>0}, St). + +shortcut_opt([L|Ls], Bs0, #st{bs=Blocks0}=St) -> + #b_blk{is=Is,last=Last0} = Blk0 = get_block(L, St), + Bs = Bs0#{from:=L}, + case shortcut_terminator(Last0, Is, Bs, St) of + Last0 -> + %% No change. No need to update the block. + shortcut_opt(Ls, Bs, St); + Last -> + %% The terminator was simplified in some way. + %% Update the block. + Blk = Blk0#b_blk{last=Last}, + Blocks = Blocks0#{L=>Blk}, + shortcut_opt(Ls, Bs, St#st{bs=Blocks}) + end; +shortcut_opt([], _, St) -> St. + +shortcut_terminator(#b_br{bool=#b_literal{val=true},succ=Succ0}, + _Is, Bs, St0) -> + St = St0#st{rel_op=none}, + shortcut(Succ0, Bs, St); +shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br, + Is, Bs, St0) -> + St = St0#st{target=one_way}, + RelOp = get_rel_op(Bool, Is), + SuccBs = bind_var(Bool, #b_literal{val=true}, Bs), + BrSucc = shortcut(Succ0, SuccBs, St#st{rel_op=RelOp}), + FailBs = bind_var(Bool, #b_literal{val=false}, Bs), + BrFail = shortcut(Fail0, FailBs, St#st{rel_op=invert_op(RelOp)}), + case {BrSucc,BrFail} of + {#b_br{bool=#b_literal{val=true},succ=Succ}, + #b_br{bool=#b_literal{val=true},succ=Fail}} + when Succ =/= Succ0; Fail =/= Fail0 -> + %% One or both of the targets were cut short. + beam_ssa:normalize(Br#b_br{succ=Succ,fail=Fail}); + {_,_} -> + %% No change. + Br + end; +shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, Bs, St) -> + List = shortcut_switch(List0, Bool, Bs, St), + beam_ssa:normalize(Sw#b_switch{list=List}); +shortcut_terminator(Last, _Is, _Bs, _St) -> + Last. + +shortcut_switch([{Lit,L0}|T], Bool, Bs, St0) -> + St = St0#st{rel_op=normalize_op({bif,'=:='}, [Bool,Lit])}, + #b_br{bool=#b_literal{val=true},succ=L} = + shortcut(L0, bind_var(Bool, Lit, Bs), St#st{target=one_way}), + [{Lit,L}|shortcut_switch(T, Bool, Bs, St0)]; +shortcut_switch([], _, _, _) -> []. + +shortcut(L, Bs, St) -> + shortcut_1(L, Bs, ordsets:new(), St). + +shortcut_1(L, Bs0, UnsetVars0, St) -> + case shortcut_2(L, Bs0, UnsetVars0, St) of + none -> + %% No more shortcuts found. Package up the previous + %% label in an unconditional branch. + #b_br{bool=#b_literal{val=true},succ=L,fail=L}; + {#b_br{bool=#b_var{}}=Br,_,_} -> + %% This is a two-way branch. We can't do any better. + Br; + {#b_br{bool=#b_literal{val=true},succ=Succ},Bs,UnsetVars} -> + %% This is a safe `br`, but try to find a better one. + shortcut_1(Succ, Bs#{from:=L}, UnsetVars, St) + end. + +%% Try to shortcut this block, branching to a successor. +shortcut_2(L, Bs0, UnsetVars0, St) -> + #b_blk{is=Is,last=Last} = get_block(L, St), + case eval_is(Is, Bs0, St) of + none -> + %% It is not safe to avoid this block because it + %% has instructions with potential side effects. + none; + Bs -> + %% The instructions in the block (if any) don't + %% have any side effects and can be skipped. + %% Evaluate the terminator. + case eval_terminator(Last, Bs, St) of + none -> + %% The terminator is not suitable (could be + %% because it is a switch that can't be simplified + %% or it is a ret instruction). + none; + #b_br{}=Br -> + %% We have a potentially suitable br. + %% Now update the set of variables that will never + %% be set if this block will be skipped. + UnsetVars1 = [V || #b_set{dst=#b_var{name=V}} <- Is], + UnsetVars = ordsets:union(UnsetVars0, + ordsets:from_list(UnsetVars1)), + + %% Continue checking whether this br is suitable. + shortcut_3(Br, Bs#{from:=L}, UnsetVars, St) + end + end. + +shortcut_3(Br, Bs, UnsetVars, #st{target=Target}=St) -> + case is_br_safe(UnsetVars, Br, St) of + false -> + %% Branching using this `br` is unsafe, either because it + %% is an unconditional branch to a phi node, or because + %% one or more of the variables that are not set will be + %% used. Try to follow branches of this `br`, to find a + %% safe `br`. + case Br of + #b_br{bool=#b_literal{val=true},succ=L} -> + case Target of + L -> + %% We have reached the forced target, and it + %% is unsafe. Give up. + none; + _ -> + %% Try following this branch to see whether it + %% leads to a safe `br`. + shortcut_2(L, Bs, UnsetVars, St) + end; + #b_br{bool=#b_var{},succ=Succ,fail=Fail} -> + case {Succ,Fail} of + {L,Target} -> + %% The failure label is the forced target. + %% Try following the success label to see + %% whether it also ultimately ends up at the + %% forced target. + shortcut_2(L, Bs, UnsetVars, St); + {Target,L} -> + %% The success label is the forced target. + %% Try following the failure label to see + %% whether it also ultimately ends up at the + %% forced target. + shortcut_2(L, Bs, UnsetVars, St); + {_,_} -> + case Target of + any -> + %% This two-way branch is unsafe. Try reducing + %% it to a one-way branch. + shortcut_two_way(Br, Bs, UnsetVars, St); + one_way -> + %% This two-way branch is unsafe. Try reducing + %% it to a one-way branch. + shortcut_two_way(Br, Bs, UnsetVars, St); + _ when is_integer(Target) -> + %% This two-way branch is unsafe, and + %% there already is a forced target. + %% Give up. + none + end + end + end; + true -> + %% This `br` instruction is safe. It does not + %% branch to a phi node, and all variables that + %% will be used are guaranteed to be defined. + case Br of + #b_br{bool=#b_literal{val=true},succ=L} -> + %% This is a one-way branch. + case Target of + any -> + %% No forced target. Success! + {Br,Bs,UnsetVars}; + one_way -> + %% The target must be a one-way branch, which this + %% `br` is. Success! + {Br,Bs,UnsetVars}; + L when is_integer(Target) -> + %% The forced target is L. Success! + {Br,Bs,UnsetVars}; + _ when is_integer(Target) -> + %% Wrong forced target. Try following this branch + %% to see if it ultimately ends up at the forced + %% target. + shortcut_2(L, Bs, UnsetVars, St) + end; + #b_br{bool=#b_var{}} -> + %% This is a two-way branch. + if + Target =:= any; Target =:= one_way -> + %% No specific forced target. Try to reduce the + %% two-way branch to an one-way branch. + case shortcut_two_way(Br, Bs, UnsetVars, St) of + none when Target =:= any -> + %% This `br` can't be reduced to a one-way + %% branch. Return the `br` as-is. + {Br,Bs,UnsetVars}; + none when Target =:= one_way -> + %% This `br` can't be reduced to a one-way + %% branch. The caller wants a one-way branch. + %% Give up. + none; + {_,_,_}=Res -> + %% This `br` was successfully reduced to a + %% one-way branch. + Res + end; + is_integer(Target) -> + %% There is a forced target, which can't + %% be reached because this `br` is a two-way + %% branch. Give up. + none + end + end + end. + +shortcut_two_way(#b_br{succ=Succ,fail=Fail}, Bs0, UnsetVars0, St) -> + case shortcut_2(Succ, Bs0, UnsetVars0, St#st{target=Fail}) of + {#b_br{bool=#b_literal{},succ=Fail},_,_}=Res -> + Res; + none -> + case shortcut_2(Fail, Bs0, UnsetVars0, St#st{target=Succ}) of + {#b_br{bool=#b_literal{},succ=Succ},_,_}=Res -> + Res; + none -> + none + end + end. + +get_block(L, St) -> + #st{bs=#{L:=Blk}} = St, + Blk. + +is_br_safe(UnsetVars, Br, #st{us=Us}=St) -> + %% Check that none of the unset variables will be used. + case Br of + #b_br{bool=#b_var{name=V},succ=Succ,fail=Fail} -> + #{Succ:=Used0,Fail:=Used1} = Us, + + %% A two-way branch never branches to a phi node, so there + %% is no need to check for phi nodes here. + not member(V, UnsetVars) andalso + ordsets:is_disjoint(Used0, UnsetVars) andalso + ordsets:is_disjoint(Used1, UnsetVars); + #b_br{succ=Same,fail=Same} -> + %% An unconditional branch must not jump to + %% a phi node. + not is_forbidden(Same, St) andalso + ordsets:is_disjoint(map_get(Same, Us), UnsetVars) + end. + +is_forbidden(L, St) -> + case get_block(L, St) of + #b_blk{is=[#b_set{op=phi}|_]} -> true; + #b_blk{is=[#b_set{op=peek_message}|_]} -> true; + #b_blk{} -> false + end. + + +%% Evaluate the instructions in the block. +%% Return the updated bindings, or 'none' if there is +%% any instruction with potential side effects. + +eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], Bs0, St) -> + From = maps:get(from, Bs0), + [Val] = [Val || {Val,Pred} <- Args, Pred =:= From], + Bs = bind_var(Dst, Val, Bs0), + eval_is(Is, Bs, St); +eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], Bs, St) -> + I = sub(I0, Bs), + case eval_bif(I, St) of + #b_literal{}=Val -> + eval_is(Is, bind_var(Dst, Val, Bs), St); + none -> + eval_is(Is, Bs, St) + end; +eval_is([#b_set{op=Op,dst=Dst}=I|Is], Bs, St) + when Op =:= is_tagged_tuple; Op =:= is_nonempty_list -> + #b_set{args=Args} = sub(I, Bs), + case eval_rel_op(Op, Args, St) of + #b_literal{}=Val -> + eval_is(Is, bind_var(Dst, Val, Bs), St); + none -> + eval_is(Is, Bs, St) + end; +eval_is([#b_set{}=I|Is], Bs, St) -> + case beam_ssa:no_side_effect(I) of + true -> + %% This instruction has no side effects. It can + %% safely be omitted. + eval_is(Is, Bs, St); + false -> + %% This instruction may have some side effect. + %% It is not safe to avoid this instruction. + none + end; +eval_is([], Bs, _St) -> Bs. + +eval_terminator(#b_br{bool=#b_var{}=Bool}=Br, Bs, _St) -> + Val = get_value(Bool, Bs), + beam_ssa:normalize(Br#b_br{bool=Val}); +eval_terminator(#b_br{bool=#b_literal{}}=Br, _Bs, _St) -> + beam_ssa:normalize(Br); +eval_terminator(#b_switch{arg=Arg,fail=Fail,list=List}=Sw, Bs, St) -> + case get_value(Arg, Bs) of + #b_literal{}=Val -> + %% Literal argument. Simplify to a `br`. + beam_ssa:normalize(Sw#b_switch{arg=Val}); + #b_var{} -> + case St of + #st{rel_op=none} -> + %% No previous relational operator is stored. + %% Give up. + none; + #st{} -> + %% There is a previous relational operator stored. + %% Try optimizing the switch. + case eval_switch(List, Arg, St, Fail) of + none -> + none; + To when is_integer(To) -> + %% Either one of the values in the switch + %% matched a previous value in a '=:=' test, or + %% none of the values matched a previous test. + #b_br{bool=#b_literal{val=true},succ=To,fail=To} + end + end + end; +eval_terminator(#b_ret{}, _Bs, _St) -> + none. + +eval_switch([{Lit,Lbl}|T], Arg, St, Fail) -> + case eval_rel_op({bif,'=:='}, [Arg,Lit], St) of + none -> + %% This label could be reached. + eval_switch(T, Arg, St, none); + #b_literal{val=false} -> + %% This branch will never be taken. + eval_switch(T, Arg, St, Fail); + #b_literal{val=true} -> + %% Success. This branch will always be taken. + Lbl + end; +eval_switch([], _Arg, _St, Fail) -> + %% Fail is now either the failure label or 'none'. + Fail. + +bind_var(Var, Val0, Bs) -> + Val = get_value(Val0, Bs), + Bs#{Var=>Val}. + +get_value(#b_var{}=Var, Bs) -> + case Bs of + #{Var:=Val} -> get_value(Val, Bs); + #{} -> Var + end; +get_value(#b_literal{}=Lit, _Bs) -> Lit. + +eval_bif(#b_set{op={bif,Bif},args=Args}, St) -> + Arity = length(Args), + case erl_bifs:is_pure(erlang, Bif, Arity) of + false -> + none; + true -> + case [Lit || #b_literal{val=Lit} <- Args] of + LitArgs when length(LitArgs) =:= Arity -> + try apply(erlang, Bif, LitArgs) of + Val -> #b_literal{val=Val} + catch + error:_ -> none + end; + _ -> + %% Not literal arguments. Try to evaluate + %% it based on a previous relational operator. + eval_rel_op({bif,Bif}, Args, St) + end + end. + +%%% +%%% Handling of relational operators. +%%% + +get_rel_op(Bool, [_|_]=Is) -> + case last(Is) of + #b_set{op=Op,dst=Bool,args=Args} -> + normalize_op(Op, Args); + #b_set{} -> + none + end; +get_rel_op(_, []) -> none. + +%% normalize_op(Instruction) -> {Normalized,FailLabel} | error +%% Normalized = {Operator,Variable,Variable|Literal} | +%% {TypeTest,Variable} +%% Operation = '<' | '=<' | '=:=' | '=/=' | '>=' | '>' +%% TypeTest = is_atom | is_integer ... +%% Variable = #b_var{} +%% Literal = #b_literal{} +%% +%% Normalize a relational operator to facilitate further +%% comparisons between operators. Always make the register +%% operand the first operand. If there are two registers, +%% order the registers in lexical order. +%% +%% For example, this instruction: +%% +%% #b_set{op={bif,=<},args=[#b_literal{}, #b_var{}} +%% +%% will be normalized to: +%% +%% {'=<',#b_var{},#b_literal{}} + +-spec normalize_op(Op, Args) -> NormalizedOp | 'none' when + Op :: beam_ssa:op(), + Args :: [beam_ssa:value()], + NormalizedOp :: basic_rel_op(). + +normalize_op(is_tagged_tuple, [Arg,#b_literal{val=Size},#b_literal{val=Tag}]) + when is_integer(Size), is_atom(Tag) -> + {{is_tagged_tuple,Size,Tag},Arg}; +normalize_op(is_nonempty_list, [Arg]) -> + {is_nonempty_list,Arg}; +normalize_op({bif,Bif}, [Arg]) -> + case erl_internal:new_type_test(Bif, 1) of + true -> {Bif,Arg}; + false -> none + end; +normalize_op({bif,Bif}, [_,_]=Args) -> + case erl_internal:comp_op(Bif, 2) of + true -> + normalize_op_1(Bif, Args); + false -> + none + end; +normalize_op(_, _) -> none. + +normalize_op_1(Bif, Args) -> + case Args of + [#b_literal{}=Arg1,#b_var{}=Arg2] -> + {turn_op(Bif),Arg2,Arg1}; + [#b_var{}=Arg1,#b_literal{}=Arg2] -> + {Bif,Arg1,Arg2}; + [#b_var{}=A,#b_var{}=B] -> + if A < B -> {Bif,A,B}; + true -> {turn_op(Bif),B,A} + end; + [#b_literal{},#b_literal{}] -> + none + end. + +-spec invert_op(basic_rel_op() | 'none') -> rel_op() | 'none'. + +invert_op({Op,Arg1,Arg2}) -> + {invert_op_1(Op),Arg1,Arg2}; +invert_op({TypeTest,Arg}) -> + {{'not',TypeTest},Arg}; +invert_op(none) -> none. + +invert_op_1('>=') -> '<'; +invert_op_1('<') -> '>='; +invert_op_1('=<') -> '>'; +invert_op_1('>') -> '=<'; +invert_op_1('=:=') -> '=/='; +invert_op_1('=/=') -> '=:='; +invert_op_1('==') -> '/='; +invert_op_1('/=') -> '=='. + +turn_op('<') -> '>'; +turn_op('=<') -> '>='; +turn_op('>') -> '<'; +turn_op('>=') -> '=<'; +turn_op('=:='=Op) -> Op; +turn_op('=/='=Op) -> Op; +turn_op('=='=Op) -> Op; +turn_op('/='=Op) -> Op. + +eval_rel_op(_Bif, _Args, #st{rel_op=none}) -> + none; +eval_rel_op(Bif, Args, #st{rel_op=Prev}) -> + case normalize_op(Bif, Args) of + none -> + none; + RelOp -> + case will_succeed(Prev, RelOp) of + yes -> #b_literal{val=true}; + no -> #b_literal{val=false}; + maybe -> none + end + end. + +%% will_succeed(PrevCondition, Condition) -> yes | no | maybe +%% PrevCondition is a condition known to be true. This function +%% will tell whether Condition will succeed. + +will_succeed({_Op,_Var,_Value}=Same, {_Op,_Var,_Value}=Same) -> + %% Repeated test. + yes; +will_succeed({Op1,Var,#b_literal{val=A}}, {Op2,Var,#b_literal{val=B}}) -> + will_succeed_1(Op1, A, Op2, B); +will_succeed({Op1,Var,#b_var{}=A}, {Op2,Var,#b_var{}=B}) -> + will_succeed_vars(Op1, A, Op2, B); +will_succeed({'=:=',Var,#b_literal{val=A}}, {TypeTest,Var}) -> + eval_type_test(TypeTest, A); +will_succeed({_,_}=Same, {_,_}=Same) -> + %% Repeated type test. + yes; +will_succeed({Test1,Var}, {Test2,Var}) -> + will_succeed_test(Test1, Test2); +will_succeed({_,_}, {_,_}) -> + maybe; +will_succeed({_,_}, {_,_,_}) -> + maybe; +will_succeed({_,_,_}, {_,_}) -> + maybe; +will_succeed({_,_,_}, {_,_,_}) -> + maybe. + +will_succeed_test({'not',Test1}, Test2) -> + case Test1 =:= Test2 of + true -> no; + false -> maybe + end; +will_succeed_test(is_tuple, {is_tagged_tuple,_,_}) -> + maybe; +will_succeed_test({is_tagged_tuple,_,_}, is_tuple) -> + yes; +will_succeed_test(is_list, is_nonempty_list) -> + maybe; +will_succeed_test(is_nonempty_list, is_list) -> + yes; +will_succeed_test(T1, T2) -> + case is_numeric_test(T1) andalso is_numeric_test(T2) of + true -> maybe; + false -> no + end. + +will_succeed_1('=:=', A, '<', B) -> + if + B =< A -> no; + true -> yes + end; +will_succeed_1('=:=', A, '=<', B) -> + if + B < A -> no; + true -> yes + end; +will_succeed_1('=:=', A, '=:=', B) when A =/= B -> + no; +will_succeed_1('=:=', A, '=/=', B) -> + if + A =:= B -> no; + true -> yes + end; +will_succeed_1('=:=', A, '>=', B) -> + if + B > A -> no; + true -> yes + end; +will_succeed_1('=:=', A, '>', B) -> + if + B >= A -> no; + true -> yes + end; + +will_succeed_1('=/=', A, '=:=', B) when A =:= B -> no; + +will_succeed_1('<', A, '=:=', B) when B >= A -> no; +will_succeed_1('<', A, '=/=', B) when B >= A -> yes; +will_succeed_1('<', A, '<', B) when B >= A -> yes; +will_succeed_1('<', A, '=<', B) when B > A -> yes; +will_succeed_1('<', A, '>=', B) when B > A -> no; +will_succeed_1('<', A, '>', B) when B >= A -> no; + +will_succeed_1('=<', A, '=:=', B) when B > A -> no; +will_succeed_1('=<', A, '=/=', B) when B > A -> yes; +will_succeed_1('=<', A, '<', B) when B > A -> yes; +will_succeed_1('=<', A, '=<', B) when B >= A -> yes; +will_succeed_1('=<', A, '>=', B) when B > A -> no; +will_succeed_1('=<', A, '>', B) when B >= A -> no; + +will_succeed_1('>=', A, '=:=', B) when B < A -> no; +will_succeed_1('>=', A, '=/=', B) when B < A -> yes; +will_succeed_1('>=', A, '<', B) when B =< A -> no; +will_succeed_1('>=', A, '=<', B) when B < A -> no; +will_succeed_1('>=', A, '>=', B) when B =< A -> yes; +will_succeed_1('>=', A, '>', B) when B < A -> yes; + +will_succeed_1('>', A, '=:=', B) when B =< A -> no; +will_succeed_1('>', A, '=/=', B) when B =< A -> yes; +will_succeed_1('>', A, '<', B) when B =< A -> no; +will_succeed_1('>', A, '=<', B) when B < A -> no; +will_succeed_1('>', A, '>=', B) when B =< A -> yes; +will_succeed_1('>', A, '>', B) when B < A -> yes; + +will_succeed_1('==', A, '==', B) -> + if + A == B -> yes; + true -> no + end; +will_succeed_1('==', A, '/=', B) -> + if + A == B -> no; + true -> yes + end; +will_succeed_1('/=', A, '/=', B) when A == B -> yes; +will_succeed_1('/=', A, '==', B) when A == B -> no; + +will_succeed_1(_, _, _, _) -> maybe. + +will_succeed_vars('=/=', Val, '=:=', Val) -> no; +will_succeed_vars('=:=', Val, '=/=', Val) -> no; +will_succeed_vars('=:=', Val, '>=', Val) -> yes; +will_succeed_vars('=:=', Val, '=<', Val) -> yes; + +will_succeed_vars('/=', Val1, '==', Val2) when Val1 == Val2 -> no; +will_succeed_vars('==', Val1, '/=', Val2) when Val1 == Val2 -> no; + +will_succeed_vars(_, _, _, _) -> maybe. + +is_numeric_test(is_float) -> true; +is_numeric_test(is_integer) -> true; +is_numeric_test(is_number) -> true; +is_numeric_test(_) -> false. + +eval_type_test(Test, Arg) -> + case eval_type_test_1(Test, Arg) of + true -> yes; + false -> no + end. + +eval_type_test_1(is_nonempty_list, Arg) -> + case Arg of + [_|_] -> true; + _ -> false + end; +eval_type_test_1({is_tagged_tuple,Sz,Tag}, Arg) -> + if + tuple_size(Arg) =:= Sz, element(1, Arg) =:= Tag -> + true; + true -> + false + end; +eval_type_test_1(Test, Arg) -> + erlang:Test(Arg). + +%%% +%%% Combine bif:'=:=' and switch instructions +%%% to switch instructions. +%%% +%%% Consider this code: +%%% +%%% 0: +%%% @ssa_bool = bif:'=:=' Var, literal 1 +%%% br @ssa_bool, label 2, label 3 +%%% +%%% 2: +%%% ret literal a +%%% +%%% 3: +%%% @ssa_bool:7 = bif:'=:=' Var, literal 2 +%%% br @ssa_bool:7, label 4, label 999 +%%% +%%% 4: +%%% ret literal b +%%% +%%% 999: +%%% . +%%% . +%%% . +%%% +%%% The two bif:'=:=' instructions can be combined +%%% to a switch: +%%% +%%% 0: +%%% switch Var, label 999, [ { literal 1, label 2 }, +%%% { literal 2, label 3 } ] +%%% +%%% 2: +%%% ret literal a +%%% +%%% 4: +%%% ret literal b +%%% +%%% 999: +%%% . +%%% . +%%% . +%%% + +combine_eqs(#st{bs=Blocks}=St) -> + Ls = reverse(beam_ssa:rpo(Blocks)), + combine_eqs_1(Ls, St). + +combine_eqs_1([L|Ls], #st{bs=Blocks0}=St0) -> + case comb_get_sw(L, St0) of + none -> + combine_eqs_1(Ls, St0); + {_,Arg,_,Fail0,List0} -> + case comb_get_sw(Fail0, St0) of + {true,Arg,Fail1,Fail,List1} -> + %% Another switch/br with the same arguments was + %% found. Try combining them. + case combine_lists(Fail1, List0, List1, Blocks0) of + none -> + %% Different types of literals in the lists, + %% or the success cases in the first switch + %% could branch to the second switch + %% (increasing code size and repeating tests). + combine_eqs_1(Ls, St0); + List -> + %% Everything OK! Combine the lists. + Sw0 = #b_switch{arg=Arg,fail=Fail,list=List}, + Sw = beam_ssa:normalize(Sw0), + Blk0 = maps:get(L, Blocks0), + Blk = Blk0#b_blk{last=Sw}, + Blocks = Blocks0#{L:=Blk}, + St = St0#st{bs=Blocks}, + combine_eqs_1(Ls, St) + end; + {true,_OtherArg,_,_,_} -> + %% The other switch/br uses a different Arg. + combine_eqs_1(Ls, St0); + {false,_,_,_,_} -> + %% Not safe: Bindings of variables that will be used + %% or execution of instructions with potential + %% side effects will be skipped. + combine_eqs_1(Ls, St0); + none -> + %% No switch/br at this label. + combine_eqs_1(Ls, St0) + end + end; +combine_eqs_1([], St) -> St. + +comb_get_sw(L, Blocks) -> + comb_get_sw(L, true, Blocks). + +comb_get_sw(L, Safe0, #st{bs=Blocks,skippable=Skippable}=St) -> + #b_blk{is=Is,last=Last} = maps:get(L, Blocks), + Safe1 = Safe0 andalso is_map_key(L, Skippable), + case Last of + #b_ret{} -> + none; + #b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail} -> + case comb_is(Is, Bool, Safe1) of + {none,_} -> + none; + {#b_set{op={bif,'=:='},args=[#b_var{}=Arg,#b_literal{}=Lit]},Safe} -> + {Safe,Arg,L,Fail,[{Lit,Succ}]}; + {#b_set{},_} -> + none + end; + #b_br{bool=#b_literal{val=true},succ=Succ} -> + comb_get_sw(Succ, Safe1, St); + #b_switch{arg=#b_var{}=Arg,fail=Fail,list=List} -> + {none,Safe} = comb_is(Is, none, Safe1), + {Safe,Arg,L,Fail,List} + end. + +comb_is([#b_set{dst=#b_var{}=Bool}=I], Bool, Safe) -> + {I,Safe}; +comb_is([#b_set{}=I|Is], Bool, Safe0) -> + Safe = Safe0 andalso beam_ssa:no_side_effect(I), + comb_is(Is, Bool, Safe); +comb_is([], _Bool, Safe) -> + {none,Safe}. + +%% combine_list(Fail, List1, List2, Blocks) -> List|none. +%% Try to combine two switch lists, returning the combined +%% list or 'none' if not possible. +%% +%% The values in the two lists must be all of the same type. +%% +%% The code reached from the labels in the first list must +%% not reach the failure label (if they do, tests could +%% be repeated). +%% + +combine_lists(Fail, L1, L2, Blocks) -> + Ls = beam_ssa:rpo([Lbl || {_,Lbl} <- L1], Blocks), + case member(Fail, Ls) of + true -> + %% One or more of labels in the first list + %% could reach the failure label. That + %% means that the second switch/br instruction + %% will be retained, increasing code size and + %% potentially also execution time. + none; + false -> + %% The combined switch will replace both original + %% br/switch instructions, leading to a reduction in code + %% size and potentially also in execution time. + combine_lists_1(L1, L2) + end. + +combine_lists_1(List0, List1) -> + case are_lists_compatible(List0, List1) of + true -> + First = maps:from_list(List0), + List0 ++ [{Val,Lbl} || {Val,Lbl} <- List1, + not is_map_key(Val, First)]; + false -> + none + end. + +are_lists_compatible([{#b_literal{val=Val1},_}|_], + [{#b_literal{val=Val2},_}|_]) -> + case lit_type(Val1) of + none -> false; + Type -> Type =:= lit_type(Val2) + end. + +lit_type(Val) -> + if + is_atom(Val) -> atom; + is_float(Val) -> float; + is_integer(Val) -> integer; + true -> none + end. + +%%% +%%% Calculate used variables for each block. +%%% + +used_vars(Linear) -> + used_vars(reverse(Linear), #{}, #{}). + +used_vars([{L,#b_blk{is=Is}=Blk}|Bs], UsedVars0, Skip0) -> + %% Calculate the variables used by each block and its + %% successors. This information is used by + %% shortcut_opt/1. + + Successors = beam_ssa:successors(Blk), + Used0 = used_vars_succ(Successors, L, UsedVars0), + Used = used_vars_blk(Blk, Used0), + UsedVars = used_vars_phis(Is, L, Used, UsedVars0), + + %% combine_eqs/1 needs different variable usage + %% information than shortcut_opt/1. The Skip + %% map will have an entry for each block that + %% can be skipped (does not bind any variable used + %% in successor). + + Defined0 = [Def || #b_set{dst=#b_var{name=Def}} <- Is], + Defined = ordsets:from_list(Defined0), + MaySkip = ordsets:is_disjoint(Defined, Used0), + case MaySkip of + true -> + Skip = Skip0#{L=>true}, + used_vars(Bs, UsedVars, Skip); + false -> + used_vars(Bs, UsedVars, Skip0) + end; +used_vars([], UsedVars, Skip) -> + {UsedVars,Skip}. + +used_vars_succ([S|Ss], L, UsedVars) -> + Live0 = used_vars_succ(Ss, L, UsedVars), + Key = {S,L}, + case UsedVars of + #{Key:=Live} -> + ordsets:union(Live, Live0); + #{S:=Live} -> + ordsets:union(Live, Live0); + #{} -> + Live0 + end; +used_vars_succ([], _, _) -> + ordsets:new(). + +used_vars_phis(Is, L, Live0, UsedVars0) -> + UsedVars = UsedVars0#{L=>Live0}, + Phis = takewhile(fun(#b_set{op=Op}) -> Op =:= phi end, Is), + case Phis of + [] -> + UsedVars; + [_|_] -> + PhiArgs = append([Args || #b_set{args=Args} <- Phis]), + case [{P,V} || {#b_var{name=V},P} <- PhiArgs] of + [_|_]=PhiVars -> + PhiLive0 = rel2fam(PhiVars), + PhiLive = [{{L,P},ordsets:union(ordsets:from_list(Vs), Live0)} || + {P,Vs} <- PhiLive0], + maps:merge(UsedVars, maps:from_list(PhiLive)); + [] -> + %% There were only literals in the phi node(s). + UsedVars + end + end. + +used_vars_blk(#b_blk{is=Is,last=Last}, Used0) -> + Used = ordsets:union(Used0, beam_ssa:used(Last)), + used_vars_is(reverse(Is), Used). + +used_vars_is([#b_set{op=phi}|Is], Used) -> + used_vars_is(Is, Used); +used_vars_is([#b_set{dst=#b_var{name=Dst}}=I|Is], Used0) -> + Used1 = ordsets:union(Used0, beam_ssa:used(I)), + Used = ordsets:del_element(Dst, Used1), + used_vars_is(Is, Used); +used_vars_is([], Used) -> + Used. + +%%% +%%% Common utilities. +%%% + +sub(#b_set{args=Args}=I, Sub) -> + I#b_set{args=[sub_arg(A, Sub) || A <- Args]}. + +sub_arg(Old, Sub) -> + case Sub of + #{Old:=New} -> New; + #{} -> Old + end. + +rel2fam(S0) -> + S1 = sofs:relation(S0), + S = sofs:rel2fam(S1), + sofs:to_external(S). diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index da466a3316..83ee918b25 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -48,16 +48,28 @@ functions([], _Ps) -> []. passes(Opts0) -> Ps = [?PASS(ssa_opt_split_blocks), + ?PASS(ssa_opt_coalesce_phis), ?PASS(ssa_opt_element), ?PASS(ssa_opt_linearize), ?PASS(ssa_opt_record), + + %% Run ssa_opt_cse twice, because it will help ssa_opt_dead, + %% and ssa_opt_dead will help ssa_opt_cse. Run ssa_opt_live + %% twice, because it will help ssa_opt_dead and ssa_opt_dead + %% will help ssa_opt_live. ?PASS(ssa_opt_cse), ?PASS(ssa_opt_type), - ?PASS(ssa_opt_float), ?PASS(ssa_opt_live), + ?PASS(ssa_opt_dead), + ?PASS(ssa_opt_cse), %Second time. + ?PASS(ssa_opt_float), + ?PASS(ssa_opt_live), %Second time. + ?PASS(ssa_opt_bsm), ?PASS(ssa_opt_bsm_shortcut), ?PASS(ssa_opt_misc), + ?PASS(ssa_opt_tuple_size), + ?PASS(ssa_opt_sw), ?PASS(ssa_opt_blockify), ?PASS(ssa_opt_sink), ?PASS(ssa_opt_merge_blocks)], @@ -88,6 +100,9 @@ function(#b_function{anno=Anno,bs=Blocks0,args=Args,cnt=Count0}=F, Ps) -> %%% Trivial sub passes. %%% +ssa_opt_dead(#st{ssa=Linear}=St) -> + St#st{ssa=beam_ssa_dead:opt(Linear)}. + ssa_opt_linearize(#st{ssa=Blocks}=St) -> St#st{ssa=beam_ssa:linearize(Blocks)}. @@ -117,6 +132,102 @@ ssa_opt_split_blocks(#st{ssa=Blocks0,cnt=Count0}=St) -> St#st{ssa=Blocks,cnt=Count}. %%% +%%% Coalesce phi nodes. +%%% +%%% Nested cases can led to code such as this: +%%% +%%% 10: +%%% _1 = phi {literal value1, label 8}, {Var, label 9} +%%% br 11 +%%% +%%% 11: +%%% _2 = phi {_1, label 10}, {literal false, label 3} +%%% +%%% The phi nodes can be coalesced like this: +%%% +%%% 11: +%%% _2 = phi {literal value1, label 8}, {Var, label 9}, {literal false, label 3} +%%% +%%% Coalescing can help other optimizations, and can in some cases reduce register +%%% shuffling (if the phi variables for two phi nodes happens to be allocated to +%%% different registers). +%%% + +ssa_opt_coalesce_phis(#st{ssa=Blocks0}=St) -> + Ls = beam_ssa:rpo(Blocks0), + Blocks = c_phis_1(Ls, Blocks0), + St#st{ssa=Blocks}. + +c_phis_1([L|Ls], Blocks0) -> + case maps:get(L, Blocks0) of + #b_blk{is=[#b_set{op=phi}|_]}=Blk -> + Blocks = c_phis_2(L, Blk, Blocks0), + c_phis_1(Ls, Blocks); + #b_blk{} -> + c_phis_1(Ls, Blocks0) + end; +c_phis_1([], Blocks) -> Blocks. + +c_phis_2(L, #b_blk{is=Is0}=Blk0, Blocks0) -> + case c_phis_args(Is0, Blocks0) of + none -> + Blocks0; + {_,_,Preds}=Info -> + Is = c_rewrite_phis(Is0, Info), + Blk = Blk0#b_blk{is=Is}, + Blocks = Blocks0#{L:=Blk}, + c_fix_branches(Preds, L, Blocks) + end. + +c_phis_args([#b_set{op=phi,args=Args0}|Is], Blocks) -> + case c_phis_args_1(Args0, Blocks) of + none -> + c_phis_args(Is, Blocks); + Res -> + Res + end; +c_phis_args(_, _Blocks) -> none. + +c_phis_args_1([{Var,Pred}|As], Blocks) -> + case c_get_pred_vars(Var, Pred, Blocks) of + none -> + c_phis_args_1(As, Blocks); + Result -> + Result + end; +c_phis_args_1([], _Blocks) -> none. + +c_get_pred_vars(Var, Pred, Blocks) -> + case maps:get(Pred, Blocks) of + #b_blk{is=[#b_set{op=phi,dst=Var,args=Args}]} -> + {Var,Pred,Args}; + #b_blk{} -> + none + end. + +c_rewrite_phis([#b_set{op=phi,args=Args0}=I|Is], Info) -> + Args = c_rewrite_phi(Args0, Info), + [I#b_set{args=Args}|c_rewrite_phis(Is, Info)]; +c_rewrite_phis(Is, _Info) -> Is. + +c_rewrite_phi([{Var,Pred}|As], {Var,Pred,Values}) -> + Values ++ As; +c_rewrite_phi([{Value,Pred}|As], {_,Pred,Values}) -> + [{Value,P} || {_,P} <- Values] ++ As; +c_rewrite_phi([A|As], Info) -> + [A|c_rewrite_phi(As, Info)]; +c_rewrite_phi([], _Info) -> []. + +c_fix_branches([{_,Pred}|As], L, Blocks0) -> + #b_blk{last=Last0} = Blk0 = maps:get(Pred, Blocks0), + #b_br{bool=#b_literal{val=true}} = Last0, %Assertion. + Last = Last0#b_br{bool=#b_literal{val=true},succ=L,fail=L}, + Blk = Blk0#b_blk{last=Last}, + Blocks = Blocks0#{Pred:=Blk}, + c_fix_branches(As, L, Blocks); +c_fix_branches([], _, Blocks) -> Blocks. + +%%% %%% Order element/2 calls. %%% %%% Order an unbroken chain of element/2 calls for the same tuple @@ -318,7 +429,13 @@ cse_successors(_Is, Blk, Es, M) -> cse_successors_1([L|Ls], Es0, M) -> case M of + #{L:=Es1} when map_size(Es1) =:= 0 -> + %% The map is already empty. No need to do anything + %% since the intersection will be empty. + cse_successors_1(Ls, Es0, M); #{L:=Es1} -> + %% Calculate the intersection of the two maps. + %% Both keys and values must match. Es = maps:filter(fun(Key, Value) -> case Es1 of #{Key:=Value} -> true; @@ -381,11 +498,20 @@ cse_suitable(#b_set{op=get_hd}) -> true; cse_suitable(#b_set{op=get_tl}) -> true; cse_suitable(#b_set{op=put_list}) -> true; cse_suitable(#b_set{op=put_tuple}) -> true; -cse_suitable(#b_set{op={bif,Name},args=Args}) -> +cse_suitable(#b_set{op={bif,tuple_size}}) -> + %% Doing CSE for tuple_size/1 can prevent the + %% creation of test_arity and select_tuple_arity + %% instructions. That could decrease performance + %% and beam_validator could fail to understand + %% that tuple operations that follow are safe. + false; +cse_suitable(#b_set{anno=Anno,op={bif,Name},args=Args}) -> + %% Doing CSE for floating point operators is unsafe. %% Doing CSE for comparison operators would prevent %% creation of 'test' instructions. Arity = length(Args), - not (erl_internal:new_type_test(Name, Arity) orelse + not (is_map_key(float_op, Anno) orelse + erl_internal:new_type_test(Name, Arity) orelse erl_internal:comp_op(Name, Arity) orelse erl_internal:bool_op(Name, Arity)); cse_suitable(#b_set{}) -> false. @@ -410,14 +536,15 @@ cse_suitable(#b_set{}) -> false. {s=undefined :: 'undefined' | 'cleared', regs=#{} :: #{beam_ssa:b_var():=beam_ssa:b_var()}, fail=none :: 'none' | beam_ssa:label(), - ren=#{} :: #{beam_ssa:label():=beam_ssa:label()}, - non_guards :: gb_sets:set(beam_ssa:label()) + non_guards :: gb_sets:set(beam_ssa:label()), + bs :: beam_ssa:block_map() }). ssa_opt_float(#st{ssa=Linear0,cnt=Count0}=St) -> NonGuards0 = float_non_guards(Linear0), NonGuards = gb_sets:from_list(NonGuards0), - Fs = #fs{non_guards=NonGuards}, + Blocks = maps:from_list(Linear0), + Fs = #fs{non_guards=NonGuards,bs=Blocks}, {Linear,Count} = float_opt(Linear0, Count0, Fs), St#st{ssa=Linear,cnt=Count}. @@ -430,42 +557,35 @@ float_non_guards([{L,#b_blk{is=Is}}|Bs]) -> end; float_non_guards([]) -> [?BADARG_BLOCK]. -float_opt([{L,Blk0}|Bs], Count, Fs) -> - Blk = float_rename_phis(Blk0, Fs), - case float_need_flush(Blk, Fs) of - true -> - float_flush(L, Blk, Bs, Count, Fs); - false -> - float_opt_1(L, Blk, Bs, Count, Fs) - end; -float_opt([], Count, _Fs) -> - {[],Count}. - -float_opt_1(L, #b_blk{last=#b_br{fail=F}}=Blk, Bs0, +float_opt([{L,#b_blk{last=#b_br{fail=F}}=Blk}|Bs0], Count0, #fs{non_guards=NonGuards}=Fs) -> case gb_sets:is_member(F, NonGuards) of true -> %% This block is not inside a guard. %% We can do the optimization. - float_opt_2(L, Blk, Bs0, Count0, Fs); + float_opt_1(L, Blk, Bs0, Count0, Fs); false -> %% This block is inside a guard. Don't do %% any floating point optimizations. {Bs,Count} = float_opt(Bs0, Count0, Fs), {[{L,Blk}|Bs],Count} end; -float_opt_1(L, Blk, Bs, Count, Fs) -> - float_opt_2(L, Blk, Bs, Count, Fs). +float_opt([{L,Blk}|Bs], Count, Fs) -> + float_opt_1(L, Blk, Bs, Count, Fs); +float_opt([], Count, _Fs) -> + {[],Count}. -float_opt_2(L, #b_blk{is=Is0}=Blk0, Bs0, Count0, Fs0) -> +float_opt_1(L, #b_blk{is=Is0}=Blk0, Bs0, Count0, Fs0) -> case float_opt_is(Is0, Fs0, Count0, []) of {Is1,Fs1,Count1} -> - Fs = float_fail_label(Blk0, Fs1), - Split = float_split_conv(Is1, Blk0), - {Blks0,Count2} = float_number(Split, L, Count1), - {Blks,Count3} = float_conv(Blks0, Fs#fs.fail, Count2), - {Bs,Count} = float_opt(Bs0, Count3, Fs), - {Blks++Bs,Count}; + Fs2 = float_fail_label(Blk0, Fs1), + Fail = Fs2#fs.fail, + {Flush,Blk,Fs,Count2} = float_maybe_flush(Blk0, Fs2, Count1), + Split = float_split_conv(Is1, Blk), + {Blks0,Count3} = float_number(Split, L, Count2), + {Blks,Count4} = float_conv(Blks0, Fail, Count3), + {Bs,Count} = float_opt(Bs0, Count4, Fs), + {Blks++Flush++Bs,Count}; none -> {Bs,Count} = float_opt(Bs0, Count0, Fs0), {[{L,Blk0}|Bs],Count} @@ -525,14 +645,42 @@ float_conv([{L,#b_blk{is=Is0}=Blk0}|Bs0], Fail, Count0) -> end end. -float_need_flush(#b_blk{is=Is}, #fs{s=cleared}) -> +float_maybe_flush(Blk0, #fs{s=cleared,fail=Fail,bs=Blocks}=Fs0, Count0) -> + #b_blk{last=#b_br{bool=#b_var{},succ=Succ}=Br} = Blk0, + #b_blk{is=Is} = maps:get(Succ, Blocks), case Is of [#b_set{anno=#{float_op:=_}}|_] -> - false; + %% The next operation is also a floating point operation. + %% No flush needed. + {[],Blk0,Fs0,Count0}; _ -> - true + %% Flush needed. + {Bool0,Count1} = new_reg('@ssa_bool', Count0), + Bool = #b_var{name=Bool0}, + + %% Allocate block numbers. + CheckL = Count1, %For checkerror. + FlushL = Count1 + 1, %For flushing of float regs. + Count = Count1 + 2, + Blk = Blk0#b_blk{last=Br#b_br{succ=CheckL}}, + + %% Build the block with the checkerror instruction. + CheckIs = [#b_set{op={float,checkerror},dst=Bool}], + CheckBr = #b_br{bool=Bool,succ=FlushL,fail=Fail}, + CheckBlk = #b_blk{is=CheckIs,last=CheckBr}, + + %% Build the block that flushes all registers. + FlushIs = float_flush_regs(Fs0), + FlushBr = #b_br{bool=#b_literal{val=true},succ=Succ,fail=Succ}, + FlushBlk = #b_blk{is=FlushIs,last=FlushBr}, + + %% Update state and blocks. + Fs = Fs0#fs{s=undefined,regs=#{},fail=none}, + FlushBs = [{CheckL,CheckBlk},{FlushL,FlushBlk}], + {FlushBs,Blk,Fs,Count} end; -float_need_flush(_, _) -> false. +float_maybe_flush(Blk, Fs, Count) -> + {[],Blk,Fs,Count}. float_opt_is([#b_set{op=succeeded,args=[Src]}=I0], #fs{regs=Rs}=Fs, Count, Acc) -> @@ -557,27 +705,6 @@ float_opt_is([], Fs, _Count, _Acc) -> #fs{s=undefined} = Fs, %Assertion. none. -float_rename_phis(#b_blk{is=Is}=Blk, #fs{ren=Ren}) -> - if - map_size(Ren) =:= 0 -> - Blk; - true -> - Blk#b_blk{is=float_rename_phis_1(Is, Ren)} - end. - -float_rename_phis_1([#b_set{op=phi,args=Args0}=I|Is], Ren) -> - Args = [float_phi_arg(Arg, Ren) || Arg <- Args0], - [I#b_set{args=Args}|float_rename_phis_1(Is, Ren)]; -float_rename_phis_1(Is, _) -> Is. - -float_phi_arg({Var,OldLbl}, Ren) -> - case Ren of - #{OldLbl:=NewLbl} -> - {Var,NewLbl}; - #{} -> - {Var,OldLbl} - end. - float_make_op(#b_set{op={bif,Op},dst=Dst,args=As0}=I0, Ts, #fs{s=S,regs=Rs0}=Fs, Count0) -> {As1,Rs1,Count1} = float_load(As0, Ts, Rs0, Count0, []), @@ -634,37 +761,6 @@ new_reg(Base, Count) -> Fr = {Base,Count}, {Fr,Count+1}. -float_flush(L, Blk, Bs0, Count0, #fs{s=cleared,fail=Fail,ren=Ren0}=Fs0) -> - {Bool0,Count1} = new_reg('@ssa_bool', Count0), - Bool = #b_var{name=Bool0}, - - %% Insert two blocks before the current block. First allocate - %% block numbers. - FirstL = L, %For checkerror. - MiddleL = Count1, %For flushed float regs. - LastL = Count1 + 1, %For original block. - Count2 = Count1 + 2, - - %% Build the block with the checkerror instruction. - CheckIs = [#b_set{op={float,checkerror},dst=Bool}], - FirstBlk = #b_blk{is=CheckIs,last=#b_br{bool=Bool,succ=MiddleL,fail=Fail}}, - - %% Build the block that flushes all registers. Note that this must be a - %% separate block in case the original block begins with a phi instruction, - %% to avoid embedding a phi instruction in the middle of a block. - FlushIs = float_flush_regs(Fs0), - MiddleBlk = #b_blk{is=FlushIs,last=#b_br{bool=#b_literal{val=true}, - succ=LastL,fail=LastL}}, - - %% The last block is the original unmodified block. - LastBlk = Blk, - - %% Update state and blocks. - Ren = Ren0#{L=>LastL}, - Fs = Fs0#fs{s=undefined,regs=#{},fail=none,ren=Ren}, - Bs1 = [{FirstL,FirstBlk},{MiddleL,MiddleBlk},{LastL,LastBlk}|Bs0], - float_opt(Bs1, Count2, Fs). - float_fail_label(#b_blk{last=Last}, Fs) -> case Last of #b_br{bool=#b_var{},fail=Fail} -> @@ -721,11 +817,16 @@ live_opt_phis(Is, L, Live0, LiveMap0) -> LiveMap; [_|_] -> PhiArgs = append([Args || #b_set{args=Args} <- Phis]), - PhiVars = [{P,V} || {#b_var{name=V},P} <- PhiArgs], - PhiLive0 = rel2fam(PhiVars), - PhiLive = [{{L,P},gb_sets:union(gb_sets:from_list(Vs), Live0)} || - {P,Vs} <- PhiLive0], - maps:merge(LiveMap, maps:from_list(PhiLive)) + case [{P,V} || {#b_var{name=V},P} <- PhiArgs] of + [_|_]=PhiVars -> + PhiLive0 = rel2fam(PhiVars), + PhiLive = [{{L,P},gb_sets:union(gb_sets:from_list(Vs), Live0)} || + {P,Vs} <- PhiLive0], + maps:merge(LiveMap, maps:from_list(PhiLive)); + [] -> + %% There were only literals in the phi node(s). + LiveMap + end end. live_opt_blk(#b_blk{is=Is0,last=Last}=Blk, Live0) -> @@ -769,14 +870,14 @@ live_opt_is([#b_set{op=succeeded,dst=#b_var{name=SuccDst}=SuccDstVar, end end end; -live_opt_is([#b_set{op=Op,dst=#b_var{name=Dst}}=I|Is], Live0, Acc) -> +live_opt_is([#b_set{dst=#b_var{name=Dst}}=I|Is], Live0, Acc) -> case gb_sets:is_member(Dst, Live0) of true -> Live1 = gb_sets:union(Live0, gb_sets:from_ordset(beam_ssa:used(I))), Live = gb_sets:delete_any(Dst, Live1), live_opt_is(Is, Live, [I|Acc]); false -> - case is_pure(Op) of + case beam_ssa:no_side_effect(I) of true -> live_opt_is(Is, Live0, Acc); false -> @@ -787,19 +888,6 @@ live_opt_is([#b_set{op=Op,dst=#b_var{name=Dst}}=I|Is], Live0, Acc) -> live_opt_is([], Live, Acc) -> {Acc,Live}. -is_pure({bif,_}) -> true; -is_pure({float,get}) -> true; -is_pure(bs_extract) -> true; -is_pure(extract) -> true; -is_pure(get_hd) -> true; -is_pure(get_tl) -> true; -is_pure(get_tuple_element) -> true; -is_pure(is_nonempty_list) -> true; -is_pure(is_tagged_tuple) -> true; -is_pure(put_list) -> true; -is_pure(put_tuple) -> true; -is_pure(_) -> false. - live_opt_unused(#b_set{op=get_map_element}=Set) -> {replace,Set#b_set{op=has_map_field}}; live_opt_unused(_) -> keep. @@ -941,6 +1029,22 @@ misc_opt_is([#b_set{op=phi}=I0|Is], Sub0, Acc) -> false -> misc_opt_is(Is, Sub0, [I|Acc]) end; +misc_opt_is([#b_set{op={bif,'and'}}=I0], Sub, Acc) -> + #b_set{dst=Dst,args=Args} = I = sub(I0, Sub), + case eval_and(Args) of + error -> + misc_opt_is([], Sub, [I|Acc]); + Val -> + misc_opt_is([], Sub#{Dst=>Val}, Acc) + end; +misc_opt_is([#b_set{op={bif,'or'}}=I0], Sub, Acc) -> + #b_set{dst=Dst,args=Args} = I = sub(I0, Sub), + case eval_or(Args) of + error -> + misc_opt_is([], Sub, [I|Acc]); + Val -> + misc_opt_is([], Sub#{Dst=>Val}, Acc) + end; misc_opt_is([#b_set{}=I0|Is], Sub, Acc) -> #b_set{op=Op,dst=Dst,args=Args} = I = sub(I0, Sub), case make_literal(Op, Args) of @@ -973,6 +1077,244 @@ make_literal_list([_|_], _) -> make_literal_list([], Acc) -> reverse(Acc). +eval_and(Args) -> + case Args of + [_,#b_literal{val=false}=Res] -> Res; + [Res,#b_literal{val=true}] -> Res; + [_,_] -> error + end. + +eval_or(Args) -> + case Args of + [Res,#b_literal{val=false}] -> Res; + [_,#b_literal{val=true}=Res] -> Res; + [_,_] -> error + end. + +%%% +%%% Optimize expressions such as "tuple_size(Var) =:= 2". +%%% +%%% Consider this code: +%%% +%%% 0: +%%% . +%%% . +%%% . +%%% Size = bif:tuple_size Var +%%% BoolVar1 = succeeded Size +%%% br BoolVar1, label 4, label 3 +%%% +%%% 4: +%%% BoolVar2 = bif:'=:=' Size, literal 2 +%%% br BoolVar2, label 6, label 3 +%%% +%%% 6: ... %% OK +%%% +%%% 3: ... %% Not a tuple of size 2 +%%% +%%% The BEAM code will look this: +%%% +%%% {bif,tuple_size,{f,3},[{x,0}],{x,0}}. +%%% {test,is_eq_exact,{f,3},[{x,0},{integer,2}]}. +%%% +%%% Better BEAM code will be produced if we transform the +%%% code like this: +%%% +%%% 0: +%%% . +%%% . +%%% . +%%% br label 10 +%%% +%%% 10: +%%% NewBoolVar = bif:is_tuple Var +%%% br NewBoolVar, label 11, label 3 +%%% +%%% 11: +%%% Size = bif:tuple_size Var +%%% br label 4 +%%% +%%% 4: +%%% BoolVar2 = bif:'=:=' Size, literal 2 +%%% br BoolVar2, label 6, label 3 +%%% +%%% (The key part of the transformation is the removal of +%%% the 'succeeded' instruction to signal to the code generator +%%% that the call to tuple_size/1 can't fail.) +%%% +%%% The BEAM code will look like: +%%% +%%% {test,is_tuple,{f,3},[{x,0}]}. +%%% {test_arity,{f,3},[{x,0},2]}. +%%% +%%% Those two instructions will be combined into a single +%%% is_tuple_of_arity instruction by the loader. +%%% + +ssa_opt_tuple_size(#st{ssa=Linear0,cnt=Count0}=St) -> + {Linear,Count} = opt_tup_size(Linear0, Count0, []), + St#st{ssa=Linear,cnt=Count}. + +opt_tup_size([{L,#b_blk{is=Is,last=Last}=Blk}|Bs], Count0, Acc0) -> + case {Is,Last} of + {[#b_set{op={bif,'=:='},dst=Bool,args=[#b_var{}=Tup,#b_literal{val=Arity}]}], + #b_br{bool=Bool}} when is_integer(Arity), Arity >= 0 -> + {Acc,Count} = opt_tup_size_1(Tup, L, Count0, Acc0), + opt_tup_size(Bs, Count, [{L,Blk}|Acc]); + {_,_} -> + opt_tup_size(Bs, Count0, [{L,Blk}|Acc0]) + end; +opt_tup_size([], Count, Acc) -> + {reverse(Acc),Count}. + +opt_tup_size_1(Size, EqL, Count0, [{L,Blk0}|Acc]) -> + case Blk0 of + #b_blk{is=Is0,last=#b_br{bool=Bool,succ=EqL,fail=Fail}} -> + case opt_tup_size_is(Is0, Bool, Size, []) of + none -> + {[{L,Blk0}|Acc],Count0}; + {PreIs,TupleSizeIs,Tuple} -> + opt_tup_size_2(PreIs, TupleSizeIs, L, EqL, + Tuple, Fail, Count0, Acc) + end; + #b_blk{} -> + {[{L,Blk0}|Acc],Count0} + end; +opt_tup_size_1(_, _, Count, Acc) -> + {Acc,Count}. + +opt_tup_size_2(PreIs, TupleSizeIs, PreL, EqL, Tuple, Fail, Count0, Acc) -> + IsTupleL = Count0, + TupleSizeL = Count0 + 1, + Bool = #b_var{name={'@ssa_bool',Count0+2}}, + Count = Count0 + 3, + + True = #b_literal{val=true}, + PreBr = #b_br{bool=True,succ=IsTupleL,fail=IsTupleL}, + PreBlk = #b_blk{is=PreIs,last=PreBr}, + + IsTupleIs = [#b_set{op={bif,is_tuple},dst=Bool,args=[Tuple]}], + IsTupleBr = #b_br{bool=Bool,succ=TupleSizeL,fail=Fail}, + IsTupleBlk = #b_blk{is=IsTupleIs,last=IsTupleBr}, + + TupleSizeBr = #b_br{bool=True,succ=EqL,fail=EqL}, + TupleSizeBlk = #b_blk{is=TupleSizeIs,last=TupleSizeBr}, + {[{TupleSizeL,TupleSizeBlk}, + {IsTupleL,IsTupleBlk}, + {PreL,PreBlk}|Acc],Count}. + +opt_tup_size_is([#b_set{op={bif,tuple_size},dst=Size,args=[Tuple]}=I, + #b_set{op=succeeded,dst=Bool,args=[Size]}], + Bool, Size, Acc) -> + {reverse(Acc),[I],Tuple}; +opt_tup_size_is([I|Is], Bool, Size, Acc) -> + opt_tup_size_is(Is, Bool, Size, [I|Acc]); +opt_tup_size_is([], _, _, _Acc) -> none. + +%%% +%%% Optimize #b_switch{} instructions. +%%% +%%% If the argument for a #b_switch{} comes from a phi node with all +%%% literals, any values in the switch list which are not in the phi +%%% node can be removed. +%%% +%%% If the values in the phi node and switch list are the same, +%%% the failure label can't be reached and be eliminated. +%%% +%%% A #b_switch{} with only one value can be rewritten to +%%% a #b_br{}. A switch that only verifies that the argument +%%% is 'true' or 'false' can be rewritten to a is_boolean test. +%%% + +ssa_opt_sw(#st{ssa=Linear0,cnt=Count0}=St) -> + {Linear,Count} = opt_sw(Linear0, #{}, Count0, []), + St#st{ssa=Linear,cnt=Count}. + +opt_sw([{L,#b_blk{is=Is,last=#b_switch{}=Last0}=Blk0}|Bs], Phis0, Count0, Acc) -> + Phis = opt_sw_phis(Is, Phis0), + case opt_sw_last(Last0, Phis) of + #b_switch{arg=Arg,fail=Fail,list=[{Lit,Lbl}]} -> + %% Rewrite a single value switch to a br. + Bool = #b_var{name={'@ssa_bool',Count0}}, + Count = Count0 + 1, + IsEq = #b_set{op={bif,'=:='},dst=Bool,args=[Arg,Lit]}, + Br = #b_br{bool=Bool,succ=Lbl,fail=Fail}, + Blk = Blk0#b_blk{is=Is++[IsEq],last=Br}, + opt_sw(Bs, Phis, Count, [{L,Blk}|Acc]); + #b_switch{arg=Arg,fail=Fail, + list=[{#b_literal{val=B1},Lbl},{#b_literal{val=B2},Lbl}]} + when B1 =:= not B2 -> + %% Replace with is_boolean test. + Bool = #b_var{name={'@ssa_bool',Count0}}, + Count = Count0 + 1, + IsBool = #b_set{op={bif,is_boolean},dst=Bool,args=[Arg]}, + Br = #b_br{bool=Bool,succ=Lbl,fail=Fail}, + Blk = Blk0#b_blk{is=Is++[IsBool],last=Br}, + opt_sw(Bs, Phis, Count, [{L,Blk}|Acc]); + Last0 -> + opt_sw(Bs, Phis, Count0, [{L,Blk0}|Acc]); + Last -> + Blk = Blk0#b_blk{last=Last}, + opt_sw(Bs, Phis, Count0, [{L,Blk}|Acc]) + end; +opt_sw([{L,#b_blk{is=Is}=Blk}|Bs], Phis0, Count, Acc) -> + Phis = opt_sw_phis(Is, Phis0), + opt_sw(Bs, Phis, Count, [{L,Blk}|Acc]); +opt_sw([], _Phis, Count, Acc) -> + {reverse(Acc),Count}. + +opt_sw_phis([#b_set{op=phi,dst=Dst,args=Args}|Is], Phis) -> + case opt_sw_literals(Args, []) of + error -> + opt_sw_phis(Is, Phis); + Literals -> + opt_sw_phis(Is, Phis#{Dst=>Literals}) + end; +opt_sw_phis(_, Phis) -> Phis. + +opt_sw_last(#b_switch{arg=Arg,fail=Fail,list=List0}=Sw0, Phis) -> + case Phis of + #{Arg:=Values0} -> + Values = gb_sets:from_list(Values0), + + %% Prune the switch list to only contain the possible values. + List1 = [P || {Lit,_}=P <- List0, gb_sets:is_member(Lit, Values)], + + %% Now test whether the failure label can ever be reached. + Sw = case gb_sets:size(Values) =:= length(List1) of + true -> + %% The switch list has the same number of values as the phi node. + %% The values must be the same, because the values that were not + %% possible were pruned from the switch list. Therefore, the + %% failure label can't possibly be reached, and we can choose a + %% a new failure label by picking a value from the list. + case List1 of + [{#b_literal{},Lbl}|List] -> + Sw0#b_switch{fail=Lbl,list=List}; + [] -> + Sw0#b_switch{list=List1} + end; + false -> + %% There are some values in the phi node that are not in the + %% switch list; thus, the failure label can still be reached. + Sw0 + end, + beam_ssa:normalize(Sw); + #{} -> + %% Ensure that no label in the switch list is the same + %% as the failure label. + List = [{Val,Lbl} || {Val,Lbl} <- List0, Lbl =/= Fail], + Sw = Sw0#b_switch{list=List}, + beam_ssa:normalize(Sw) + end. + +opt_sw_literals([{#b_literal{}=Lit,_}|T], Acc) -> + opt_sw_literals(T, [Lit|Acc]); +opt_sw_literals([_|_], _Acc) -> + error; +opt_sw_literals([], Acc) -> Acc. + + %%% %%% Merge blocks. %%% @@ -1283,20 +1625,23 @@ rel2fam(S0) -> S = sofs:rel2fam(S1), sofs:to_external(S). -sub(#b_set{op=phi,args=Args}=I, Sub) -> +sub(I, Sub) -> + beam_ssa:normalize(sub_1(I, Sub)). + +sub_1(#b_set{op=phi,args=Args}=I, Sub) -> I#b_set{args=[{sub_arg(A, Sub),P} || {A,P} <- Args]}; -sub(#b_set{args=Args}=I, Sub) -> +sub_1(#b_set{args=Args}=I, Sub) -> I#b_set{args=[sub_arg(A, Sub) || A <- Args]}; -sub(#b_br{bool=#b_var{}=Old}=Br, Sub) -> +sub_1(#b_br{bool=#b_var{}=Old}=Br, Sub) -> New = sub_arg(Old, Sub), Br#b_br{bool=New}; -sub(#b_switch{arg=#b_var{}=Old}=Sw, Sub) -> +sub_1(#b_switch{arg=#b_var{}=Old}=Sw, Sub) -> New = sub_arg(Old, Sub), Sw#b_switch{arg=New}; -sub(#b_ret{arg=#b_var{}=Old}=Ret, Sub) -> +sub_1(#b_ret{arg=#b_var{}=Old}=Ret, Sub) -> New = sub_arg(Old, Sub), Ret#b_ret{arg=New}; -sub(Last, _) -> Last. +sub_1(Last, _) -> Last. sub_arg(#b_remote{mod=Mod,name=Name}=Rem, Sub) -> Rem#b_remote{mod=sub_arg(Mod, Sub),name=sub_arg(Name, Sub)}; diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl index 54aa2efaf6..7f67e315f5 100644 --- a/lib/compiler/src/beam_ssa_pre_codegen.erl +++ b/lib/compiler/src/beam_ssa_pre_codegen.erl @@ -1016,14 +1016,19 @@ recv_fix_common_1([], [], _Msg, Blocks) -> Blocks. fix_exit_phi_args([V|Vs], [Rm|Rms], Exit, Blocks) -> Path = beam_ssa:rpo([Rm], Blocks), - Pred = exit_predecessor(Path, Exit), - [{V,Pred}|fix_exit_phi_args(Vs, Rms, Exit, Blocks)]; + Preds = exit_predecessors(Path, Exit, Blocks), + [{V,Pred} || Pred <- Preds] ++ fix_exit_phi_args(Vs, Rms, Exit, Blocks); fix_exit_phi_args([], [], _, _) -> []. -exit_predecessor([Pred,Exit|_], Exit) -> - Pred; -exit_predecessor([_|Bs], Exit) -> - exit_predecessor(Bs, Exit). +exit_predecessors([L|Ls], Exit, Blocks) -> + Blk = map_get(L, Blocks), + case member(Exit, beam_ssa:successors(Blk)) of + true -> + [L|exit_predecessors(Ls, Exit, Blocks)]; + false -> + exit_predecessors(Ls, Exit, Blocks) + end; +exit_predecessors([], _Exit, _Blocks) -> []. %% fix_receive([Label], Defs, Blocks0, Count0) -> {Blocks,Count}. %% Add a copy instruction for all variables that are matched out and diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index e5f15da836..058e40106c 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -22,13 +22,15 @@ -export([opt/2]). -include("beam_ssa.hrl"). --import(lists, [any/2,droplast/1,foldl/3,last/1,member/2, - reverse/1,search/2,sort/1]). +-import(lists, [all/2,any/2,droplast/1,foldl/3,last/1,member/2, + reverse/1,sort/1]). -define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}). -record(d, {ds :: #{beam_ssa:var_name():=beam_ssa:b_set()}, - ls :: #{beam_ssa:label():=type_db()}}). + ls :: #{beam_ssa:label():=type_db()}, + sub :: #{beam_ssa:var_name():=beam_ssa:value()} + }). -define(ATOM_SET_SIZE, 5). @@ -60,7 +62,7 @@ opt(Linear, Args) -> arity=0}]}, Defs = maps:from_list([{V,FakeCall#b_set{dst=Var}} || #b_var{name=V}=Var <- Args]), - D = #d{ds=Defs,ls=#{0=>Ts}}, + D = #d{ds=Defs,ls=#{0=>Ts},sub=#{}}, opt_1(Linear, D). opt_1([{L,Blk}|Bs], #d{ls=Ls}=D) -> @@ -71,9 +73,9 @@ opt_1([{L,Blk}|Bs], #d{ls=Ls}=D) -> %% This block is never reached. Discard it. opt_1(Bs, D) end; -opt_1([], _) -> []. +opt_1([], #d{}) -> []. -opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, D0) -> +opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, #d{sub=Sub}=D0) -> case Is0 of [#b_set{op=call,dst=Dst, args=[#b_remote{mod=#b_literal{val=Mod}, @@ -84,7 +86,7 @@ opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, D0) -> %% Rewrite the terminator to a 'ret', and remove %% all type information for this label. That will %% simplify the phi node in the former successor. - Args = [simplify_arg(Arg, Ts) || Arg <- Args0], + Args = simplify_args(Args0, Sub, Ts), I = I0#b_set{args=[Rem|Args]}, Ret = #b_ret{arg=Dst}, Blk = Blk0#b_blk{is=[I],last=Ret}, @@ -98,61 +100,120 @@ opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, D0) -> opt_3(L, Blk0, Bs, Ts, D0) end. -opt_3(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, #d{ds=Ds0,ls=Ls0}=D0) -> - {Is,Ts,Ds} = opt_is(Is0, Ts0, Ds0, Ls0, []), - D1 = D0#d{ds=Ds}, - Last = opt_terminator(Last0, Ts, Ds), +opt_3(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, + #d{ds=Ds0,ls=Ls0,sub=Sub0}=D0) -> + {Is,Ts,Ds,Sub} = opt_is(Is0, Ts0, Ds0, Ls0, Sub0, []), + D1 = D0#d{ds=Ds,sub=Sub}, + Last1 = simplify_terminator(Last0, Sub, Ts), + Last = opt_terminator(Last1, Ts, Ds), D = update_successors(Last, Ts, D1), Blk = Blk0#b_blk{is=Is,last=Last}, [{L,Blk}|opt_1(Bs, D)]. -opt_is([#b_set{op=phi,dst=#b_var{name=Dst},args=Args0}=I0|Is], Ts0, Ds0, Ls, Acc) -> +simplify_terminator(#b_br{bool=Bool}=Br, Sub, Ts) -> + Br#b_br{bool=simplify_arg(Bool, Sub, Ts)}; +simplify_terminator(#b_switch{arg=Arg}=Sw, Sub, Ts) -> + Sw#b_switch{arg=simplify_arg(Arg, Sub, Ts)}; +simplify_terminator(#b_ret{arg=Arg}=Ret, Sub, Ts) -> + Ret#b_ret{arg=simplify_arg(Arg, Sub, Ts)}. + +opt_is([#b_set{op=phi,dst=#b_var{name=Dst},args=Args0}=I0|Is], + Ts0, Ds0, Ls, Sub0, Acc) -> %% Simplify the phi node by removing all predecessor blocks that no %% longer exists or no longer branches to this block. - Args = [P || {_,From}=P <- Args0, maps:is_key(From, Ls)], - I = I0#b_set{args=Args}, - Ts = update_types(I, Ts0, Ds0), - Ds = Ds0#{Dst=>I}, - opt_is(Is, Ts, Ds, Ls, [I|Acc]); -opt_is([#b_set{dst=#b_var{name=Dst}}=I0|Is], Ts0, Ds0, Ls, Acc) -> - I = simplify(I0, Ts0), - Ts = update_types(I, Ts0, Ds0), - Ds = Ds0#{Dst=>I}, - opt_is(Is, Ts, Ds, Ls, [I|Acc]); -opt_is([], Ts, Ds, _Ls, Acc) -> - {reverse(Acc),Ts,Ds}. + Args = [{simplify_arg(Arg, Sub0, Ts0),From} || + {Arg,From} <- Args0, maps:is_key(From, Ls)], + case all_same(Args) of + true -> + %% Eliminate the phi node if there is just one source + %% value or if the values are identical. + [{Val,_}|_] = Args, + Sub = Sub0#{Dst=>Val}, + opt_is(Is, Ts0, Ds0, Ls, Sub, Acc); + false -> + I = I0#b_set{args=Args}, + Ts = update_types(I, Ts0, Ds0), + Ds = Ds0#{Dst=>I}, + opt_is(Is, Ts, Ds, Ls, Sub0, [I|Acc]) + end; +opt_is([#b_set{args=Args0,dst=#b_var{name=Dst}}=I0|Is], + Ts0, Ds0, Ls, Sub0, Acc) -> + Args = simplify_args(Args0, Sub0, Ts0), + I1 = beam_ssa:normalize(I0#b_set{args=Args}), + case simplify(I1, Ts0) of + #b_set{}=I2 -> + I = beam_ssa:normalize(I2), + Ts = update_types(I, Ts0, Ds0), + Ds = Ds0#{Dst=>I}, + opt_is(Is, Ts, Ds, Ls, Sub0, [I|Acc]); + #b_literal{}=Lit -> + Sub = Sub0#{Dst=>Lit}, + opt_is(Is, Ts0, Ds0, Ls, Sub, Acc); + #b_var{}=Var -> + Sub = Sub0#{Dst=>Var}, + opt_is(Is, Ts0, Ds0, Ls, Sub, Acc) + end; +opt_is([], Ts, Ds, _Ls, Sub, Acc) -> + {reverse(Acc),Ts,Ds,Sub}. +simplify(#b_set{op={bif,'and'},args=Args}=I, Ts) -> + case is_safe_bool_op(Args, Ts) of + true -> + case Args of + [_,#b_literal{val=false}=Res] -> Res; + [Res,#b_literal{val=true}] -> Res; + _ -> eval_bif(I, Ts) + end; + false -> + I + end; +simplify(#b_set{op={bif,'or'},args=Args}=I, Ts) -> + case is_safe_bool_op(Args, Ts) of + true -> + case Args of + [Res,#b_literal{val=false}] -> Res; + [_,#b_literal{val=true}=Res] -> Res; + _ -> eval_bif(I, Ts) + end; + false -> + I + end; simplify(#b_set{op={bif,element},args=[#b_literal{val=Index},Tuple]}=I, Ts) -> case t_tuple_size(get_type(Tuple, Ts)) of {_,Size} when is_integer(Index), 1 =< Index, Index =< Size -> I#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=Index-1}]}; _ -> - I + eval_bif(I, Ts) end; simplify(#b_set{op={bif,hd},args=[List]}=I, Ts) -> case get_type(List, Ts) of cons -> I#b_set{op=get_hd}; _ -> - I + eval_bif(I, Ts) end; simplify(#b_set{op={bif,tl},args=[List]}=I, Ts) -> case get_type(List, Ts) of cons -> I#b_set{op=get_tl}; _ -> - I + eval_bif(I, Ts) end; simplify(#b_set{op={bif,size},args=[Term]}=I, Ts) -> case get_type(Term, Ts) of #t_tuple{} -> - I#b_set{op={bif,tuple_size}}; + simplify(I#b_set{op={bif,tuple_size}}, Ts); + _ -> + eval_bif(I, Ts) + end; +simplify(#b_set{op={bif,tuple_size},args=[Term]}=I, Ts) -> + case get_type(Term, Ts) of + #t_tuple{size=Size,exact=true} -> + #b_literal{val=Size}; _ -> I end; -simplify(#b_set{op={bif,'=='},args=Args0}=I0, Ts) -> - Args = [simplify_arg(Arg, Ts) || Arg <- Args0], - I = I0#b_set{args=Args}, +simplify(#b_set{op={bif,'=='},args=Args}=I, Ts) -> Types = get_types(Args, Ts), EqEq = case {meet(Types),join(Types)} of {none,any} -> true; @@ -164,50 +225,147 @@ simplify(#b_set{op={bif,'=='},args=Args0}=I0, Ts) -> end, case EqEq of true -> - I#b_set{op={bif,'=:='}}; + simplify(I#b_set{op={bif,'=:='}}, Ts); false -> - I + eval_bif(I, Ts) + end; +simplify(#b_set{op={bif,'=:='},args=[Same,Same]}, _Ts) -> + #b_literal{val=true}; +simplify(#b_set{op={bif,'=:='},args=Args}=I, Ts) -> + case meet(get_types(Args, Ts)) of + none -> #b_literal{val=false}; + _ -> eval_bif(I, Ts) end; -simplify(#b_set{op={bif,Op},args=Args0}=I0, Ts) -> - Args = [simplify_arg(Arg, Ts) || Arg <- Args0], - I = I0#b_set{args=Args}, +simplify(#b_set{op={bif,Op},args=Args}=I, Ts) -> Types = get_types(Args, Ts), case is_float_op(Op, Types) of false -> - I; + eval_bif(I, Ts); true -> AnnoArgs = [anno_float_arg(A) || A <- Types], - beam_ssa:add_anno(float_op, AnnoArgs, I) + eval_bif(beam_ssa:add_anno(float_op, AnnoArgs, I), Ts) end; -simplify(#b_set{op=wait_timeout,args=[Timeout0]}=I, Ts) -> - case simplify_arg(Timeout0, Ts) of - #b_literal{val=infinity} -> - I#b_set{op=wait,args=[]}; - Timeout -> - I#b_set{args=[Timeout]} +simplify(#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=0}]}=I, Ts) -> + case get_type(Tuple, Ts) of + #t_tuple{elements=[First]} -> + #b_literal{val=First}; + #t_tuple{} -> + I end; -simplify(#b_set{op=Op,args=Args0}=I, Ts) -> - Safe = case Op of - call -> true; - put_list -> true; - put_tuple -> true; - _ -> false - end, - case Safe of - true -> - Args = [simplify_arg(Arg, Ts) || Arg <- Args0], - I#b_set{args=Args}; +simplify(#b_set{op=is_nonempty_list,args=[Src]}=I, Ts) -> + case get_type(Src, Ts) of + any -> I; + list -> I; + cons -> #b_literal{val=true}; + _ -> #b_literal{val=false} + end; +simplify(#b_set{op=is_tagged_tuple, + args=[Src,#b_literal{val=Size},#b_literal{val=Tag}]}=I, Ts) -> + case get_type(Src, Ts) of + #t_tuple{exact=true,size=Size,elements=[Tag]} -> + #b_literal{val=true}; + #t_tuple{exact=true,size=ActualSize,elements=[]} -> + if + Size =/= ActualSize -> + #b_literal{val=false}; + true -> + I + end; + #t_tuple{exact=false} -> + I; + any -> + I; + _ -> + #b_literal{val=false} + end; +simplify(#b_set{op=put_list,args=[#b_literal{val=H}, + #b_literal{val=T}]}, _Ts) -> + #b_literal{val=[H|T]}; +simplify(#b_set{op=put_tuple,args=Args}=I, _Ts) -> + case make_literal_list(Args) of + none -> I; + List -> #b_literal{val=list_to_tuple(List)} + end; +simplify(#b_set{op=succeeded,args=[#b_literal{}]}, _Ts) -> + #b_literal{val=true}; +simplify(#b_set{op=wait_timeout,args=[#b_literal{val=infinity}]}=I, _Ts) -> + I#b_set{op=wait,args=[]}; +simplify(I, _Ts) -> I. + +make_literal_list(Args) -> + make_literal_list(Args, []). + +make_literal_list([#b_literal{val=H}|T], Acc) -> + make_literal_list(T, [H|Acc]); +make_literal_list([_|_], _) -> + none; +make_literal_list([], Acc) -> + reverse(Acc). + +is_safe_bool_op(Args, Ts) -> + [T1,T2] = get_types(Args, Ts), + t_is_boolean(T1) andalso t_is_boolean(T2). + +all_same([{H,_}|T]) -> + all(fun({E,_}) -> E =:= H end, T). + +eval_bif(#b_set{op={bif,Bif},args=Args}=I, Ts) -> + Arity = length(Args), + case erl_bifs:is_pure(erlang, Bif, Arity) of false -> - I + I; + true -> + case make_literal_list(Args) of + none -> + case get_types(Args, Ts) of + [any] -> + I; + [Type] -> + case will_succeed(Bif, Type) of + yes -> + #b_literal{val=true}; + no -> + #b_literal{val=false}; + maybe -> + I + end; + _ -> + I + end; + LitArgs -> + try apply(erlang, Bif, LitArgs) of + Val -> #b_literal{val=Val} + catch + error:_ -> I + end + + end end. -simplify_arg(#b_var{}=Arg, Ts) -> - Type = get_type(Arg, Ts), - case get_literal_from_type(Type) of - none -> Arg; - #b_literal{}=Lit -> Lit +simplify_args(Args, Sub, Ts) -> + [simplify_arg(Arg, Sub, Ts) || Arg <- Args]. + +simplify_arg(#b_var{}=Arg0, Sub, Ts) -> + case sub_arg(Arg0, Sub) of + #b_literal{}=LitArg -> + LitArg; + #b_var{}=Arg -> + Type = get_type(Arg, Ts), + case get_literal_from_type(Type) of + none -> Arg; + #b_literal{}=Lit -> Lit + end end; -simplify_arg(Arg, _Ts) -> Arg. +simplify_arg(#b_remote{mod=Mod,name=Name}=Rem, Sub, Ts) -> + Rem#b_remote{mod=simplify_arg(Mod, Sub, Ts), + name=simplify_arg(Name, Sub, Ts)}; +simplify_arg(Arg, _Sub, _Ts) -> Arg. + +sub_arg(#b_var{name=V}=Old, Sub) -> + case Sub of + #{V:=New} -> New; + #{} -> Old + end. is_float_op('-', [float]) -> true; @@ -228,67 +386,49 @@ anno_float_arg(float) -> float; anno_float_arg(_) -> convert. opt_terminator(#b_br{bool=#b_literal{}}=Br, _Ts, _Ds) -> - Br; -opt_terminator(#b_br{bool=#b_var{name=V}=Var}=Br, Ts, Ds) -> - BoolType = get_type(Var, Ts), - case get_literal_from_type(BoolType) of - #b_literal{}=BoolLit -> - Br#b_br{bool=BoolLit}; - none -> - #{V:=Set} = Ds, - case Set of - #b_set{op={bif,'=:='},args=[Bool,#b_literal{val=true}]} -> - case t_is_boolean(get_type(Bool, Ts)) of - true -> - %% Bool =:= true ==> Bool - simplify_not(Br#b_br{bool=Bool}, Ts, Ds); - false -> - Br - end; - #b_set{} -> - simplify_not(Br, Ts, Ds) - end + beam_ssa:normalize(Br); +opt_terminator(#b_br{bool=#b_var{name=V}}=Br, Ts, Ds) -> + #{V:=Set} = Ds, + case Set of + #b_set{op={bif,'=:='},args=[Bool,#b_literal{val=true}]} -> + case t_is_boolean(get_type(Bool, Ts)) of + true -> + %% Bool =:= true ==> Bool + simplify_not(Br#b_br{bool=Bool}, Ts, Ds); + false -> + Br + end; + #b_set{} -> + simplify_not(Br, Ts, Ds) end; -opt_terminator(#b_switch{arg=#b_literal{val=Val0}=Arg,fail=Fail,list=List}, - _Ts, _Ds) -> - {value,{_,L}} = search(fun({#b_literal{val=Val1},_}) -> - Val1 =:= Val0 - end, List ++ [{Arg,Fail}]), - #b_br{bool=#b_literal{val=true},succ=L,fail=L}; -opt_terminator(#b_switch{arg=V}=Sw0, Ts, Ds) -> - case get_literal_from_type(Ts) of - #b_literal{}=Lit -> - Sw = Sw0#b_switch{arg=Lit}, - opt_terminator(Sw, Ts, Ds); - none -> - case get_type(V, Ts) of - #t_integer{elements={_,_}=Range} -> - simplify_switch_int(Sw0, Range); - Type -> - case t_is_boolean(Type) of - true -> - case simplify_switch_bool(Sw0, Ts, Ds) of - #b_br{}=Br -> - opt_terminator(Br, Ts, Ds); - Sw -> - Sw - end; - false -> - Sw0 - end +opt_terminator(#b_switch{arg=#b_literal{}}=Sw, _Ts, _Ds) -> + beam_ssa:normalize(Sw); +opt_terminator(#b_switch{arg=#b_var{}=V}=Sw0, Ts, Ds) -> + Type = get_type(V, Ts), + case Type of + #t_integer{elements={_,_}=Range} -> + simplify_switch_int(Sw0, Range); + _ -> + case t_is_boolean(Type) of + true -> + case simplify_switch_bool(Sw0, Ts, Ds) of + #b_br{}=Br -> + opt_terminator(Br, Ts, Ds); + Sw -> + beam_ssa:normalize(Sw) + end; + false -> + beam_ssa:normalize(Sw0) end end; -opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> - Ret. +opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> Ret. -update_successors(#b_br{bool=#b_literal{val=false},fail=S}, Ts, D) -> - update_successor(S, Ts, D); update_successors(#b_br{bool=#b_literal{val=true},succ=S}, Ts, D) -> update_successor(S, Ts, D); -update_successors(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}, Ts, D0) -> - D = update_successor(Fail, Ts#{V:=t_atom(false)}, D0), - SuccTs = infer_types(V, Ts, D0), - update_successor(Succ, SuccTs#{V:=t_atom(true)}, D); +update_successors(#b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail}, Ts, D0) -> + D = update_successor_bool(Bool, false, Fail, Ts, D0), + SuccTs = infer_types(Bool, Ts, D0), + update_successor_bool(Bool, true, Succ, SuccTs, D); update_successors(#b_switch{arg=#b_var{name=V},fail=Fail,list=List}, Ts, D0) -> D = update_successor(Fail, Ts, D0), foldl(fun({Val,S}, A) -> @@ -297,6 +437,16 @@ update_successors(#b_switch{arg=#b_var{name=V},fail=Fail,list=List}, Ts, D0) -> end, D, List); update_successors(#b_ret{}, _Ts, D) -> D. +update_successor_bool(#b_var{name=V}=Var, BoolValue, S, Ts, D) -> + case t_is_boolean(get_type(Var, Ts)) of + true -> + update_successor(S, Ts#{V:=t_atom(BoolValue)}, D); + false -> + %% The `br` terminator is preceeded by an instruction that + %% does not produce a boolean value, such a `new_try_tag`. + update_successor(S, Ts, D) + end. + update_successor(S, Ts0, #d{ls=Ls}=D) -> case Ls of #{S:=Ts1} -> @@ -313,41 +463,8 @@ update_types(#b_set{op=Op,dst=#b_var{name=Dst},args=Args}, Ts, Ds) -> type(phi, Args, Ts, _Ds) -> Types = [get_type(A, Ts) || {A,_} <- Args], join(Types); -type({bif,'=:='}, [Same,Same], _Ts, _Ds) -> - t_atom(true); -type({bif,'=:='}, [_,_]=Args, Ts, _Ds) -> - case get_literals(Args, Ts) of - [#b_literal{val=Lit1},#b_literal{val=Lit2}] -> - t_atom(Lit1 =:= Lit2); - [_,_] -> - case meet(get_types(Args, Ts)) of - none -> t_atom(false); - _ -> t_boolean() - end - end; -type({bif,tuple_size}, [Src], Ts, _Ds) -> - case t_tuple_size(get_type(Src, Ts)) of - {exact,Size} -> - t_integer(Size); - _ -> - t_integer() - end; type({bif,'band'}, Args, Ts, _Ds) -> band_type(Args, Ts); -type({bif,Bif}, [Src]=Args, Ts, _Ds) -> - case get_type(Src, Ts) of - any -> - bif_type(Bif, Args); - Type -> - case will_succeed(Bif, Type) of - yes -> - t_atom(true); - no -> - t_atom(false); - maybe -> - bif_type(Bif, Args) - end - end; type({bif,Bif}, Args, Ts, _Ds) -> case bif_type(Bif, Args) of number -> @@ -399,42 +516,12 @@ type(call, [#b_remote{mod=#b_literal{val=Mod}, false -> any end end; -type(get_tuple_element, [Tuple,#b_literal{val=0}], Ts, _Ds) -> - case get_type(Tuple, Ts) of - #t_tuple{elements=[First]} -> - get_type(#b_literal{val=First}, Ts); - #t_tuple{} -> - any - end; -type(is_nonempty_list, [Src], Ts, _Ds) -> - case get_type(Src, Ts) of - any -> - t_boolean(); - list -> - t_boolean(); - cons -> - t_atom(true); - _ -> - t_atom(false) - end; -type(is_tagged_tuple, [Src,#b_literal{val=Size},#b_literal{val=Tag}], Ts, _Ds) -> - case get_type(Src, Ts) of - #t_tuple{exact=true,size=Size,elements=[Tag]} -> - t_atom(true); - #t_tuple{exact=true,size=ActualSize,elements=[]} -> - if - Size =/= ActualSize -> - t_atom(false); - true -> - t_boolean() - end; - #t_tuple{exact=false} -> - t_boolean(); - any -> - t_boolean(); - _ -> - t_atom(false) - end; +type(is_nonempty_list, [_], _Ts, _Ds) -> + t_boolean(); +type(is_tagged_tuple, [_,#b_literal{},#b_literal{}], _Ts, _Ds) -> + t_boolean(); +type(put_map, _Args, _Ts, _Ds) -> + map; type(put_list, _Args, _Ts, _Ds) -> cons; type(put_tuple, Args, _Ts, _Ds) -> @@ -449,6 +536,11 @@ type(succeeded, [#b_var{name=Src}], Ts, Ds) -> #b_set{op={bif,Bif},args=BifArgs} -> Types = get_types(BifArgs, Ts), case {Bif,Types} of + {BoolOp,[T1,T2]} when BoolOp =:= 'and'; BoolOp =:= 'or' -> + case t_is_boolean(T1) andalso t_is_boolean(T2) of + true -> t_atom(true); + false -> t_boolean() + end; {byte_size,[{binary,_}]} -> t_atom(true); {bit_size,[{binary,_}]} -> @@ -493,7 +585,6 @@ arith_op_type(Args, Ts) -> (number, #t_integer{}) -> number; (number, float) -> float; (any, _) -> number; - (_, any) -> number; (Same, Same) -> Same; (_, _) -> none end, unknown, Types). @@ -554,7 +645,6 @@ will_succeed(is_list, Type) -> case Type of list -> yes; cons -> yes; - nil -> yes; _ -> no end; will_succeed(is_map, Type) -> @@ -577,8 +667,6 @@ will_succeed(is_tuple, Type) -> will_succeed(_, _) -> maybe. -band_type([#b_literal{val=Int},Other], Ts) when is_integer(Int) -> - band_type_1(Int, Other, Ts); band_type([Other,#b_literal{val=Int}], Ts) when is_integer(Int) -> band_type_1(Int, Other, Ts); band_type([_,_], _) -> t_integer(). @@ -662,25 +750,22 @@ simplify_switch_bool(#b_switch{arg=B,list=List0}=Sw, Ts, Ds) -> Sw end. -simplify_not(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}=Br, Ts, Ds) -> +simplify_not(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}=Br0, Ts, Ds) -> case Ds of #{V:=#b_set{op={bif,'not'},args=[Bool]}} -> case t_is_boolean(get_type(Bool, Ts)) of true -> - Br#b_br{bool=Bool,succ=Fail,fail=Succ}; + Br = Br0#b_br{bool=Bool,succ=Fail,fail=Succ}, + beam_ssa:normalize(Br); false -> - Br + Br0 end; #{} -> - Br + Br0 end. -get_literals(Values, Ts) -> - [get_literal_from_type(get_type(Val, Ts)) || Val <- Values]. - get_types(Values, Ts) -> [get_type(Val, Ts) || Val <- Values]. - -spec get_type(beam_ssa:value(), type_db()) -> type(). get_type(#b_var{name=V}, Ts) -> @@ -709,7 +794,7 @@ get_type(#b_literal{val=Val}, _Ts) -> any end. -infer_types(V, Ts, #d{ds=Ds}) -> +infer_types(#b_var{name=V}, Ts, #d{ds=Ds}) -> #{V:=#b_set{op=Op,args=Args}} = Ds, Types = infer_type(Op, Args, Ds), meet_types(Types, Ts). @@ -755,7 +840,6 @@ infer_type(_Op, _Args, _Ds) -> %% Note that that the following BIFs are handle elsewhere: %% %% band/2 -%% tuple_size/1 bif_type(abs, [_]) -> number; bif_type(bit_size, [_]) -> t_integer(); @@ -766,9 +850,12 @@ bif_type(floor, [_]) -> t_integer(); bif_type(is_map_key, [_,_]) -> t_boolean(); bif_type(length, [_]) -> t_integer(); bif_type(map_size, [_]) -> t_integer(); +bif_type(node, []) -> #t_atom{}; +bif_type(node, [_]) -> #t_atom{}; bif_type(round, [_]) -> t_integer(); bif_type(size, [_]) -> t_integer(); bif_type(trunc, [_]) -> t_integer(); +bif_type(tuple_size, [_]) -> t_integer(); bif_type('bnot', [_]) -> t_integer(); bif_type('bor', [_,_]) -> t_integer(); bif_type('bsl', [_,_]) -> t_integer(); @@ -807,8 +894,12 @@ inferred_bif_type(byte_size, [_]) -> {binary,1}; inferred_bif_type(ceil, [_]) -> number; inferred_bif_type(float, [_]) -> number; inferred_bif_type(floor, [_]) -> number; +inferred_bif_type(hd, [_]) -> cons; +inferred_bif_type(length, [_]) -> list; +inferred_bif_type(map_size, [_]) -> map; inferred_bif_type(round, [_]) -> number; inferred_bif_type(trunc, [_]) -> number; +inferred_bif_type(tl, [_]) -> cons; inferred_bif_type(tuple_size, [_]) -> #t_tuple{}; inferred_bif_type(_, _) -> any. @@ -1025,13 +1116,9 @@ meet(#t_integer{elements={Min1,Max1}}, #t_integer{elements={Min2,Max2}}) -> #t_integer{elements={max(Min1, Min2),min(Max1, Max2)}}; meet(#t_integer{}=T, number) -> T; -meet(float, number) -> float; -meet(#t_integer{}=T, number) -> T; -meet(float, number) -> float; +meet(float=T, number) -> T; meet(number, #t_integer{}=T) -> T; -meet(#t_integer{}=T, number) -> T; meet(number, float=T) -> T; -meet(float=T, number) -> T; meet(list, cons) -> cons; meet(list, nil) -> nil; meet(cons, list) -> cons; diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 953aced66e..8d699f2abd 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -598,6 +598,14 @@ valfun_4({bif,is_map_key,{f,Fail},[_Key,Map]=Src,Dst}, Vst0) -> Vst = set_type(map, Map, Vst1), Type = propagate_fragility(bool, Src, Vst), set_type_reg(Type, Dst, Vst); +valfun_4({bif,Op,{f,Fail},[Cons]=Src,Dst}, Vst0) + when Op =:= hd; Op =:= tl -> + validate_src(Src, Vst0), + Vst1 = branch_state(Fail, Vst0), + Vst = set_type(cons, Cons, Vst1), + Type0 = bif_type(Op, Src, Vst), + Type = propagate_fragility(Type0, Src, Vst), + set_type_reg(Type, Dst, Vst); valfun_4({bif,Op,{f,Fail},Src,Dst}, Vst0) -> validate_src(Src, Vst0), Vst = branch_state(Fail, Vst0), @@ -610,7 +618,13 @@ valfun_4({gc_bif,Op,{f,Fail},Live,Src,Dst}, #vst{current=St0}=Vst0) -> St = kill_heap_allocation(St0), Vst1 = Vst0#vst{current=St}, Vst2 = branch_state(Fail, Vst1), - Vst = prune_x_regs(Live, Vst2), + Vst3 = prune_x_regs(Live, Vst2), + Vst = case Op of + map_size -> + set_type(map, hd(Src), Vst3); + _ -> + Vst3 + end, validate_src(Src, Vst), Type0 = bif_type(Op, Src, Vst), Type = propagate_fragility(Type0, Src, Vst), @@ -648,10 +662,12 @@ valfun_4({set_tuple_element,Src,Tuple,I}, Vst) -> %% Match instructions. valfun_4({select_val,Src,{f,Fail},{list,Choices}}, Vst0) -> assert_term(Src, Vst0), + assert_choices(Choices), Vst = branch_state(Fail, Vst0), kill_state(select_val_branches(Src, Choices, Vst)); valfun_4({select_tuple_arity,Tuple,{f,Fail},{list,Choices}}, Vst) -> assert_type(tuple, Tuple, Vst), + assert_arities(Choices), TupleType = case get_term_type(Tuple, Vst) of {fragile,TupleType0} -> TupleType0; TupleType0 -> TupleType0 @@ -1088,6 +1104,29 @@ prune_x_regs(Live, #vst{current=St0}=Vst) St = St0#st{x=gb_trees:from_orddict(Xs),defs=Defs,aliases=Aliases}, Vst#vst{current=St}. +%% All choices in a select_val list must be integers, floats, or atoms. +%% All must be of the same type. +assert_choices([{Tag,_},{f,_}|T]) -> + if + Tag =:= atom; Tag =:= float; Tag =:= integer -> + assert_choices_1(T, Tag); + true -> + error(bad_select_list) + end; +assert_choices([]) -> ok. + +assert_choices_1([{Tag,_},{f,_}|T], Tag) -> + assert_choices_1(T, Tag); +assert_choices_1([_,{f,_}|_], _Tag) -> + error(bad_select_list); +assert_choices_1([], _Tag) -> ok. + +assert_arities([Arity,{f,_}|T]) when is_integer(Arity) -> + assert_arities(T); +assert_arities([]) -> ok; +assert_arities(_) -> error(bad_tuple_arity_list). + + %%% %%% Floating point checking. %%% @@ -1919,6 +1958,12 @@ is_bif_safe(self, 0) -> true; is_bif_safe(node, 0) -> true; is_bif_safe(_, _) -> false. +arith_type([A], Vst) -> + %% Unary '+' or '-'. + case get_term_type(A, Vst) of + {float,_} -> {float,[]}; + _ -> number + end; arith_type([A,B], Vst) -> case {get_term_type(A, Vst),get_term_type(B, Vst)} of {{float,_},_} -> {float,[]}; diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl index 0a7f723c64..74ad864163 100644 --- a/lib/compiler/src/compile.erl +++ b/lib/compiler/src/compile.erl @@ -841,10 +841,6 @@ asm_passes() -> {iff,dexcept,{listing,"except"}}, {unless,no_bs_opt,{pass,beam_bs}}, {iff,dbs,{listing,"bs"}}, - {pass,beam_split}, - {iff,dsplit,{listing,"split"}}, - {unless,no_dead,{pass,beam_dead}}, - {iff,ddead,{listing,"dead"}}, {unless,no_jopt,{pass,beam_jump}}, {iff,djmp,{listing,"jump"}}, {unless,no_peep_opt,{pass,beam_peep}}, @@ -1673,7 +1669,6 @@ effects_code_generation(Option) -> binary -> false; verbose -> false; {cwd,_} -> false; - {i,_} -> false; {outdir, _} -> false; _ -> true end. @@ -2037,7 +2032,6 @@ pre_load() -> beam_bs, beam_bsm, beam_clean, - beam_dead, beam_dict, beam_except, beam_flatten, @@ -2047,11 +2041,11 @@ pre_load() -> beam_peep, beam_ssa, beam_ssa_codegen, + beam_ssa_dead, beam_ssa_opt, beam_ssa_pre_codegen, beam_ssa_recv, beam_ssa_type, - beam_split, beam_trim, beam_utils, beam_validator, diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src index 74529f7fef..bb281376ef 100644 --- a/lib/compiler/src/compiler.app.src +++ b/lib/compiler/src/compiler.app.src @@ -27,7 +27,6 @@ beam_bs, beam_bsm, beam_clean, - beam_dead, beam_dict, beam_disasm, beam_except, @@ -39,13 +38,13 @@ beam_peep, beam_ssa, beam_ssa_codegen, + beam_ssa_dead, beam_ssa_lint, beam_ssa_opt, beam_ssa_pp, beam_ssa_pre_codegen, beam_ssa_recv, beam_ssa_type, - beam_split, beam_trim, beam_utils, beam_validator, diff --git a/lib/compiler/test/andor_SUITE.erl b/lib/compiler/test/andor_SUITE.erl index 721f77f0f6..5c463063c1 100644 --- a/lib/compiler/test/andor_SUITE.erl +++ b/lib/compiler/test/andor_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. +%% Copyright Ericsson AB 2001-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/apply_SUITE.erl b/lib/compiler/test/apply_SUITE.erl index be49cff9b9..0f82a56fb7 100644 --- a/lib/compiler/test/apply_SUITE.erl +++ b/lib/compiler/test/apply_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2005-2016. All Rights Reserved. +%% Copyright Ericsson AB 2005-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/beam_except_SUITE.erl b/lib/compiler/test/beam_except_SUITE.erl index 1eb07c8c85..2b4a780899 100644 --- a/lib/compiler/test/beam_except_SUITE.erl +++ b/lib/compiler/test/beam_except_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2011-2016. All Rights Reserved. +%% Copyright Ericsson AB 2011-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/beam_jump_SUITE.erl b/lib/compiler/test/beam_jump_SUITE.erl index 488c30919b..c61e4ab65c 100644 --- a/lib/compiler/test/beam_jump_SUITE.erl +++ b/lib/compiler/test/beam_jump_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2016. All Rights Reserved. +%% Copyright Ericsson AB 2016-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/beam_reorder_SUITE.erl b/lib/compiler/test/beam_reorder_SUITE.erl index 33b27b9f9f..c8a4f9a75f 100644 --- a/lib/compiler/test/beam_reorder_SUITE.erl +++ b/lib/compiler/test/beam_reorder_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2015-2016. All Rights Reserved. +%% Copyright Ericsson AB 2015-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/beam_ssa_SUITE.erl b/lib/compiler/test/beam_ssa_SUITE.erl index 0356c99c5a..5536abbdde 100644 --- a/lib/compiler/test/beam_ssa_SUITE.erl +++ b/lib/compiler/test/beam_ssa_SUITE.erl @@ -21,7 +21,8 @@ -export([all/0,suite/0,groups/0,init_per_suite/1,end_per_suite/1, init_per_group/2,end_per_group/2, - calls/1,tuple_matching/1,recv/1,maps/1]). + calls/1,tuple_matching/1,recv/1,maps/1, + cover_ssa_dead/1,combine_sw/1]). suite() -> [{ct_hooks,[ts_install_cth]}]. @@ -33,7 +34,9 @@ groups() -> [tuple_matching, calls, recv, - maps + maps, + cover_ssa_dead, + combine_sw ]}]. init_per_suite(Config) -> @@ -286,5 +289,183 @@ maps_1(K) -> #{K:=V} = #{}, V. +-record(wx_ref, {type=any_type,ref=any_ref}). + +cover_ssa_dead(_Config) -> + str = format_str(str, escapable, [], true), + [iolist,str] = format_str(str, escapable, iolist, true), + bad = format_str(str, not_escapable, [], true), + bad = format_str(str, not_escapable, iolist, true), + bad = format_str(str, escapable, [], false), + bad = format_str(str, escapable, [], bad), + + DefWxRef = #wx_ref{}, + {DefWxRef,77,9999,[]} = contains(#wx_ref{}, 77, 9999), + {DefWxRef,77.0,9999,[]} = contains(#wx_ref{}, 77.0, 9999), + {DefWxRef,77,9999.0,[]} = contains(#wx_ref{}, 77, 9999.0), + {DefWxRef,77.0,9999.0,[]} = contains(#wx_ref{}, 77.0, 9999.0), + {any_type,any_ref,42,43,[option]} = contains(#wx_ref{}, {42,43}, [option]), + {any_type,any_ref,42,43,[]} = contains(#wx_ref{}, {42,43}, []), + {any_type,any_ref,42.0,43,[]} = contains(#wx_ref{}, {42.0,43}, []), + {any_type,any_ref,42,43.0,[]} = contains(#wx_ref{}, {42,43.0}, []), + {any_type,any_ref,42.0,43.0,[]} = contains(#wx_ref{}, {42.0,43.0}, []), + + nope = conv_alub(false, '=:='), + ok = conv_alub(true, '=:='), + ok = conv_alub(true, none), + error = conv_alub(false, none), + + {false,false} = eval_alu(false, false, false), + {true,false} = eval_alu(false, false, true), + {false,true} = eval_alu(false, true, false), + {false,false} = eval_alu(false, true, true), + {false,true} = eval_alu(true, false, false), + {false,false} = eval_alu(true, false, true), + {true,true} = eval_alu(true, true, false), + {false,true} = eval_alu(true, true, true), + + 100.0 = percentage(1.0, 0.0), + 100.0 = percentage(1, 0), + 0.0 = percentage(0, 0), + 0.0 = percentage(0.0, 0.0), + 40.0 = percentage(4.0, 10.0), + 60.0 = percentage(6, 10), + + %% Cover '=:=', followed by '=/='. + false = 'cover__=:=__=/='(41), + true = 'cover__=:=__=/='(42), + false = 'cover__=:=__=/='(43), + + %% Cover '<', followed by '=/='. + true = 'cover__<__=/='(41), + false = 'cover__<__=/='(42), + false = 'cover__<__=/='(43), + + %% Cover '=<', followed by '=/='. + true = 'cover__=<__=/='(41), + true = 'cover__=<__=/='(42), + false = 'cover__=<__=/='(43), + + %% Cover '>=', followed by '=/='. + false = 'cover__>=__=/='(41), + true = 'cover__>=__=/='(42), + true = 'cover__>=__=/='(43), + + %% Cover '>', followed by '=/='. + false = 'cover__>__=/='(41), + false = 'cover__>__=/='(42), + true = 'cover__>__=/='(43), + + ok. + +'cover__=:=__=/='(X) when X =:= 42 -> X =/= 43; +'cover__=:=__=/='(_) -> false. + +'cover__<__=/='(X) when X < 42 -> X =/= 42; +'cover__<__=/='(_) -> false. + +'cover__=<__=/='(X) when X =< 42 -> X =/= 43; +'cover__=<__=/='(_) -> false. + +'cover__>=__=/='(X) when X >= 42 -> X =/= 41; +'cover__>=__=/='(_) -> false. + +'cover__>__=/='(X) when X > 42 -> X =/= 42; +'cover__>__=/='(_) -> false. + +format_str(Str, FormatData, IoList, EscChars) -> + Escapable = FormatData =:= escapable, + case id(Str) of + IoStr when Escapable, EscChars, IoList == [] -> + id(IoStr); + IoStr when Escapable, EscChars -> + [IoList,id(IoStr)]; + _ -> + bad + end. + +contains(This, X, Y) when is_record(This, wx_ref), is_number(X), is_number(Y) -> + {This,X,Y,[]}; +contains(#wx_ref{type=ThisT,ref=ThisRef}, {CX,CY}, Options) + when is_number(CX), is_number(CY), is_list(Options) -> + {ThisT,ThisRef,CX,CY,Options}. + +conv_alub(HasDst, CmpOp) -> + case (not HasDst) andalso CmpOp =/= none of + true -> nope; + false -> + case HasDst of + false -> error; + true -> ok + end + end. + +eval_alu(Sign1, Sign2, N) -> + V = (Sign1 andalso Sign2 andalso (not N)) + or ((not Sign1) andalso (not Sign2) andalso N), + C = (Sign1 andalso Sign2) + or ((not N) andalso (Sign1 orelse Sign2)), + {V,C}. + +percentage(Divident, Divisor) -> + if Divisor == 0 andalso Divident /= 0 -> + 100.0; + Divisor == 0 -> + 0.0; + true -> + Divident / Divisor * 100 + end. + +combine_sw(_Config) -> + [a] = do_comb_sw_1(a), + [b,b] = do_comb_sw_1(b), + [c] = do_comb_sw_1(c), + [c] = do_comb_sw_1(c), + [] = do_comb_sw_1(z), + + [a] = do_comb_sw_2(a), + [b2,b1] = do_comb_sw_2(b), + [c] = do_comb_sw_2(c), + [c] = do_comb_sw_2(c), + [] = do_comb_sw_2(z), + + ok. + +do_comb_sw_1(X) -> + put(?MODULE, []), + if + X == a; X == b -> + put(?MODULE, [X|get(?MODULE)]); + true -> + ok + end, + if + X == b; X == c -> + put(?MODULE, [X|get(?MODULE)]); + true -> + ok + end, + erase(?MODULE). + +do_comb_sw_2(X) -> + put(?MODULE, []), + case X of + a -> + put(?MODULE, [a|get(?MODULE)]); + b -> + put(?MODULE, [b1|get(?MODULE)]); + _ -> + ok + end, + case X of + b -> + put(?MODULE, [b2|get(?MODULE)]); + c -> + put(?MODULE, [c|get(?MODULE)]); + _ -> + ok + end, + erase(?MODULE). + %% The identity function. id(I) -> I. diff --git a/lib/compiler/test/beam_type_SUITE.erl b/lib/compiler/test/beam_type_SUITE.erl index caf43dad40..a4459b95bf 100644 --- a/lib/compiler/test/beam_type_SUITE.erl +++ b/lib/compiler/test/beam_type_SUITE.erl @@ -21,8 +21,8 @@ -export([all/0,suite/0,groups/0,init_per_suite/1,end_per_suite/1, init_per_group/2,end_per_group/2, - integers/1,coverage/1,booleans/1,setelement/1,cons/1, - tuple/1,record_float/1,binary_float/1,float_compare/1, + integers/1,numbers/1,coverage/1,booleans/1,setelement/1, + cons/1,tuple/1,record_float/1,binary_float/1,float_compare/1, arity_checks/1,elixir_binaries/1,find_best/1, test_size/1]). @@ -34,6 +34,7 @@ all() -> groups() -> [{p,[parallel], [integers, + numbers, coverage, booleans, setelement, @@ -125,6 +126,59 @@ do_integers_5(X0, Y0) -> 3 -> three end. +numbers(_Config) -> + Int = id(42), + true = is_integer(Int), + true = is_number(Int), + false = is_float(Int), + + Float = id(42.0), + true = is_float(Float), + true = is_number(Float), + false = is_integer(Float), + + Number = id(1) + id(2), + true = is_number(Number), + true = is_integer(Number), + false = is_float(Number), + + AnotherNumber = id(99.0) + id(1), + true = is_float(AnotherNumber), + true = is_number(AnotherNumber), + false = is_integer(AnotherNumber), + + NotNumber = id(atom), + true = is_atom(NotNumber), + false = is_number(NotNumber), + false = is_integer(NotNumber), + false = is_float(NotNumber), + + true = is_number(Int), + true = is_number(Float), + true = is_number(Number), + true = is_number(AnotherNumber), + + %% Cover beam_ssa_type:join/2. + + Join1 = case id(a) of + a -> 3 + id(7); %Number. + b -> id(5) / id(2) %Float. + end, + true = is_integer(Join1), + + Join2 = case id(a) of + a -> id(5) / 2; %Float. + b -> 3 + id(7) %Number. + end, + true = is_float(Join2), + + %% Cover beam_ssa_type:meet/2. + + Meet1 = id(0) + -10.0, %Float. + 10.0 = abs(Meet1), %Number. + + ok. + coverage(Config) -> {'EXIT',{badarith,_}} = (catch id(1) bsl 0.5), {'EXIT',{badarith,_}} = (catch id(2.0) bsl 2), @@ -162,10 +216,31 @@ coverage(Config) -> ok. booleans(_Config) -> - {'EXIT',{{case_clause,_},_}} = (catch do_booleans(42)), + {'EXIT',{{case_clause,_},_}} = (catch do_booleans_1(42)), + + AnyAtom = id(atom), + true = is_atom(AnyAtom), + false = is_boolean(AnyAtom), + + MaybeBool = id(maybe), + case MaybeBool of + true -> ok; + maybe -> ok; + false -> ok + end, + false = is_boolean(MaybeBool), + + NotBool = id(a), + case NotBool of + a -> ok; + b -> ok; + c -> ok + end, + false = is_boolean(NotBool), + ok. -do_booleans(B) -> +do_booleans_1(B) -> case is_integer(B) of yes -> yes; no -> no @@ -223,8 +298,15 @@ cons_hdtl(B) -> id(1), {id(hd(Cons)),id(tl(Cons))}. +-record(bird, {a=a,b=id(42)}). + tuple(_Config) -> {'EXIT',{{badmatch,{necessary}},_}} = (catch do_tuple()), + + [] = [X || X <- [], #bird{a = a} == {r,X,foo}], + [] = [X || X <- [], #bird{b = b} == {bird,X}], + [] = [X || X <- [], 3 == X#bird.a], + ok. do_tuple() -> @@ -361,7 +443,7 @@ find_best([], <<"a">>) -> find_best([], nil) -> {error,<<"should not get here">>}. -test_size(Config) -> +test_size(_Config) -> 2 = do_test_size({a,b}), 4 = do_test_size(<<42:32>>), ok. diff --git a/lib/compiler/test/bif_SUITE.erl b/lib/compiler/test/bif_SUITE.erl index c4c709eb3a..42ba5d5365 100644 --- a/lib/compiler/test/bif_SUITE.erl +++ b/lib/compiler/test/bif_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2016. All Rights Reserved. +%% Copyright Ericsson AB 2016-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/bs_bincomp_SUITE.erl b/lib/compiler/test/bs_bincomp_SUITE.erl index a5d49020a9..0419b16eea 100644 --- a/lib/compiler/test/bs_bincomp_SUITE.erl +++ b/lib/compiler/test/bs_bincomp_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2006-2016. All Rights Reserved. +%% Copyright Ericsson AB 2006-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/bs_bit_binaries_SUITE.erl b/lib/compiler/test/bs_bit_binaries_SUITE.erl index 17faa012bc..526769f3a6 100644 --- a/lib/compiler/test/bs_bit_binaries_SUITE.erl +++ b/lib/compiler/test/bs_bit_binaries_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2006-2016. All Rights Reserved. +%% Copyright Ericsson AB 2006-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/bs_utf_SUITE.erl b/lib/compiler/test/bs_utf_SUITE.erl index 4330677260..8ea4a849ec 100644 --- a/lib/compiler/test/bs_utf_SUITE.erl +++ b/lib/compiler/test/bs_utf_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2008-2016. All Rights Reserved. +%% Copyright Ericsson AB 2008-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/compilation_SUITE.erl b/lib/compiler/test/compilation_SUITE.erl index def7a60f45..74f9dbd9b4 100644 --- a/lib/compiler/test/compilation_SUITE.erl +++ b/lib/compiler/test/compilation_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 1997-2017. All Rights Reserved. +%% Copyright Ericsson AB 1997-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/compile_SUITE.erl b/lib/compiler/test/compile_SUITE.erl index 8d8fc23027..38bc928f85 100644 --- a/lib/compiler/test/compile_SUITE.erl +++ b/lib/compiler/test/compile_SUITE.erl @@ -392,7 +392,6 @@ do_file_listings(DataDir, PrivDir, [File|Files]) -> do_listing(Simple, TargetDir, dblk, ".block"), do_listing(Simple, TargetDir, dexcept, ".except"), do_listing(Simple, TargetDir, dbs, ".bs"), - do_listing(Simple, TargetDir, ddead, ".dead"), do_listing(Simple, TargetDir, djmp, ".jump"), do_listing(Simple, TargetDir, dclean, ".clean"), do_listing(Simple, TargetDir, dpeep, ".peep"), @@ -1250,11 +1249,8 @@ do_opt_guards_fun([]) -> []. is_exception(guard_SUITE, {'-complex_not/1-fun-4-',1}) -> true; is_exception(guard_SUITE, {'-complex_not/1-fun-5-',1}) -> true; is_exception(guard_SUITE, {bad_guards,1}) -> true; -is_exception(guard_SUITE, {bad_guards_2,2}) -> true; is_exception(guard_SUITE, {bad_guards_3,2}) -> true; -is_exception(guard_SUITE, {csemi7,3}) -> true; is_exception(guard_SUITE, {nested_not_2b,4}) -> true; -is_exception(guard_SUITE, {tricky_1,2}) -> true; is_exception(_, _) -> false. sys_pre_attributes(Config) -> diff --git a/lib/compiler/test/core_alias_SUITE.erl b/lib/compiler/test/core_alias_SUITE.erl index 4f96576621..737b1567d4 100644 --- a/lib/compiler/test/core_alias_SUITE.erl +++ b/lib/compiler/test/core_alias_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2007-2016. All Rights Reserved. +%% Copyright Ericsson AB 2007-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/core_fold_SUITE.erl b/lib/compiler/test/core_fold_SUITE.erl index 68bc5c6e2f..3fca1434ae 100644 --- a/lib/compiler/test/core_fold_SUITE.erl +++ b/lib/compiler/test/core_fold_SUITE.erl @@ -212,9 +212,14 @@ bifs(Config) when is_list(Config) -> {ok,#{K:=V}} = id(list_to_tuple([ok,#{K=>V}])), ok. --define(CMP_SAME(A0, B), (fun(A) -> true = A == B, false = A /= B end)(id(A0))). --define(CMP_DIFF(A0, B), (fun(A) -> false = A == B, true = A /= B end)(id(A0))). - +-define(CMP_SAME0(A0, B), (fun(A) -> true = A == B, false = A /= B end)(id(A0))). +-define(CMP_SAME1(A0, B), (fun(A) -> false = A /= B, true = A == B end)(id(A0))). +-define(CMP_SAME(A0, B), (true = ?CMP_SAME0(A0, B) =:= not ?CMP_SAME1(A0, B))). + +-define(CMP_DIFF0(A0, B), (fun(A) -> false = A == B, true = A /= B end)(id(A0))). +-define(CMP_DIFF1(A0, B), (fun(A) -> true = A /= B, false = A == B end)(id(A0))). +-define(CMP_DIFF(A0, B), (true = ?CMP_DIFF0(A0, B) =:= not ?CMP_DIFF1(A0, B))). + eq(Config) when is_list(Config) -> ?CMP_SAME([a,b,c], [a,b,c]), ?CMP_SAME([42.0], [42.0]), diff --git a/lib/compiler/test/error_SUITE.erl b/lib/compiler/test/error_SUITE.erl index da291bdc8b..8b9dbe4aa0 100644 --- a/lib/compiler/test/error_SUITE.erl +++ b/lib/compiler/test/error_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 1998-2016. All Rights Reserved. +%% Copyright Ericsson AB 1998-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/float_SUITE.erl b/lib/compiler/test/float_SUITE.erl index 39867021cb..012810aba2 100644 --- a/lib/compiler/test/float_SUITE.erl +++ b/lib/compiler/test/float_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2002-2016. All Rights Reserved. +%% Copyright Ericsson AB 2002-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/guard_SUITE.erl b/lib/compiler/test/guard_SUITE.erl index 73a8dc0fda..1c05129dc4 100644 --- a/lib/compiler/test/guard_SUITE.erl +++ b/lib/compiler/test/guard_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2001-2017. All Rights Reserved. +%% Copyright Ericsson AB 2001-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. @@ -35,8 +35,7 @@ basic_andalso_orelse/1,traverse_dcd/1, check_qlc_hrl/1,andalso_semi/1,t_tuple_size/1,binary_part/1, bad_constants/1,bad_guards/1, - guard_in_catch/1,beam_bool_SUITE/1, - cover_beam_dead/1]). + guard_in_catch/1,beam_bool_SUITE/1]). suite() -> [{ct_hooks,[ts_install_cth]}]. @@ -54,8 +53,7 @@ groups() -> rel_ops,rel_op_combinations, literal_type_tests,basic_andalso_orelse,traverse_dcd, check_qlc_hrl,andalso_semi,t_tuple_size,binary_part, - bad_constants,bad_guards,guard_in_catch,beam_bool_SUITE, - cover_beam_dead]}]. + bad_constants,bad_guards,guard_in_catch,beam_bool_SUITE]}]. init_per_suite(Config) -> test_lib:recompile(?MODULE), @@ -1779,16 +1777,6 @@ t_tuple_size(Config) when is_list(Config) -> error = ludicrous_tuple_size({a,b,c}), error = ludicrous_tuple_size([a,b,c]), - %% Test the "unsafe case" - the register assigned the tuple size is - %% not killed. - DataDir = test_lib:get_data_dir(Config), - File = filename:join(DataDir, "guard_SUITE_tuple_size"), - {ok,Mod,Code} = compile:file(File, [from_asm,binary]), - code:load_binary(Mod, File, Code), - 14 = Mod:t({1,2,3,4}), - _ = code:delete(Mod), - _ = code:purge(Mod), - good_ip({1,2,3,4}), good_ip({1,2,3,4,5,6,7,8}), error = validate_ip({42,11}), @@ -2221,32 +2209,6 @@ maps() -> evidence(#{0 := Charge}) when 0; #{[] => Charge} == #{[] => 42} -> ok. -cover_beam_dead(_Config) -> - Mod = ?FUNCTION_NAME, - Attr = [], - Fs = [{function,test,1,2, - [{label,1}, - {line,[]}, - {func_info,{atom,Mod},{atom,test},1}, - {label,2}, - %% Cover beam_dead:turn_op/1 using swapped operand order. - {test,is_ne_exact,{f,3},[{integer,1},{x,0}]}, - {test,is_eq_exact,{f,1},[{atom,a},{x,0}]}, - {label,3}, - {move,{atom,ok},{x,0}}, - return]}], - Exp = [{test,1}], - Asm = {Mod,Exp,Attr,Fs,3}, - {ok,Mod,Beam} = compile:forms(Asm, [from_asm,binary,report]), - {module,Mod} = code:load_binary(Mod, Mod, Beam), - ok = Mod:test(1), - ok = Mod:test(a), - {'EXIT',_} = (catch Mod:test(other)), - true = code:delete(Mod), - _ = code:purge(Mod), - - ok. - %% Call this function to turn off constant propagation. id(I) -> I. diff --git a/lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S b/lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S deleted file mode 100644 index cffb792920..0000000000 --- a/lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S +++ /dev/null @@ -1,30 +0,0 @@ -{module, guard_SUITE_tuple_size}. %% version = 0 - -{exports, [{t,1}]}. - -{attributes, []}. - -{labels, 5}. - - -{function, t, 1, 2}. - {label,1}. - {func_info,{atom,guard_SUITE_tuple_size},{atom,t},1}. - {label,2}. - {bif,tuple_size,{f,4},[{x,0}],{x,1}}. - {test,is_eq_exact,{f,4},[{x,1},{integer,4}]}. - {test,is_tuple,{f,3},[{x,0}]}. - {test,test_arity,{f,3},[{x,0},4]}. - {get_tuple_element,{x,0},0,{x,5}}. - {get_tuple_element,{x,0},1,{x,2}}. - {get_tuple_element,{x,0},2,{x,3}}. - {get_tuple_element,{x,0},3,{x,4}}. - {gc_bif,'+',{f,0},6,[{x,1},{x,2}],{x,0}}. - {gc_bif,'+',{f,0},6,[{x,0},{x,3}],{x,0}}. - {gc_bif,'+',{f,0},6,[{x,0},{x,4}],{x,0}}. - {gc_bif,'+',{f,0},6,[{x,0},{x,5}],{x,0}}. - return. - {label,3}. - {badmatch,{x,0}}. - {label,4}. - {jump,{f,1}}. diff --git a/lib/compiler/test/inline_SUITE.erl b/lib/compiler/test/inline_SUITE.erl index e03769012b..69c9dcba69 100644 --- a/lib/compiler/test/inline_SUITE.erl +++ b/lib/compiler/test/inline_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2000-2016. All Rights Reserved. +%% Copyright Ericsson AB 2000-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/match_SUITE.erl b/lib/compiler/test/match_SUITE.erl index e3f842b668..229c3093d7 100644 --- a/lib/compiler/test/match_SUITE.erl +++ b/lib/compiler/test/match_SUITE.erl @@ -254,6 +254,8 @@ non_matching_aliases(_Config) -> none = mixed_aliases([d]), none = mixed_aliases({a,42}), none = mixed_aliases(42), + none = mixed_aliases(<<6789:16>>), + none = mixed_aliases(#{key=>value}), {'EXIT',{{badmatch,42},_}} = (catch nomatch_alias(42)), {'EXIT',{{badmatch,job},_}} = (catch entirely()), @@ -279,6 +281,16 @@ mixed_aliases(<<X:8>> = x) -> {a,X}; mixed_aliases([b] = <<X:8>>) -> {b,X}; mixed_aliases(<<X:8>> = {a,X}) -> {c,X}; mixed_aliases([X] = <<X:8>>) -> {d,X}; +mixed_aliases(<<X:16>> = X) -> {e,X}; +mixed_aliases(X = <<X:16>>) -> {f,X}; +mixed_aliases(<<X:16,_/binary>> = X) -> {g,X}; +mixed_aliases(X = <<X:16,_/binary>>) -> {h,X}; +mixed_aliases(X = #{key:=X}) -> {i,X}; +mixed_aliases(#{key:=X} = X) -> {j,X}; +mixed_aliases([X] = #{key:=X}) -> {k,X}; +mixed_aliases(#{key:=X} = [X]) -> {l,X}; +mixed_aliases({a,X} = #{key:=X}) -> {m,X}; +mixed_aliases(#{key:=X} = {a,X}) -> {n,X}; mixed_aliases(_) -> none. nomatch_alias(I) -> @@ -434,6 +446,7 @@ letify_guard(A, B) -> selectify(Config) when is_list(Config) -> integer = sel_different_types({r,42}), atom = sel_different_types({r,forty_two}), + float = sel_different_types({r,100.0}), none = sel_different_types({r,18}), {'EXIT',_} = (catch sel_different_types([a,b,c])), @@ -444,12 +457,15 @@ selectify(Config) when is_list(Config) -> integer42 = sel_same_value2(42), integer43 = sel_same_value2(43), error = sel_same_value2(44), + ok. sel_different_types({r,_}=T) when element(2, T) =:= forty_two -> atom; sel_different_types({r,_}=T) when element(2, T) =:= 42 -> integer; +sel_different_types({r,_}=T) when element(2, T) =:= 100.0 -> + float; sel_different_types({r,_}) -> none. diff --git a/lib/compiler/test/misc_SUITE.erl b/lib/compiler/test/misc_SUITE.erl index beae5eb618..4c2d0116c9 100644 --- a/lib/compiler/test/misc_SUITE.erl +++ b/lib/compiler/test/misc_SUITE.erl @@ -234,16 +234,6 @@ silly_coverage(Config) when is_list(Config) -> {label,2}|non_proper_list]}],99}, expect_error(fun() -> beam_except:module(ExceptInput, []) end), - %% beam_dead. This is tricky. Our function must look OK to - %% beam_utils:clean_labels/1, but must crash beam_dead. - DeadInput = {?MODULE,[{foo,0}],[], - [{function,foo,0,2, - [{label,1}, - {func_info,{atom,?MODULE},{atom,foo},0}, - {label,2}, - {test,is_eq_exact,{f,1},[bad,operands]}]}],99}, - expect_error(fun() -> beam_dead:module(DeadInput, []) end), - %% beam_clean CleanInput = {?MODULE,[{foo,0}],[], [{function,foo,0,2, diff --git a/lib/compiler/test/overridden_bif_SUITE.erl b/lib/compiler/test/overridden_bif_SUITE.erl index a46abe8dcf..6b8a9591c9 100644 --- a/lib/compiler/test/overridden_bif_SUITE.erl +++ b/lib/compiler/test/overridden_bif_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. +%% Copyright Ericsson AB 2001-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/record_SUITE.erl b/lib/compiler/test/record_SUITE.erl index 118e0a241c..4ed7f39780 100644 --- a/lib/compiler/test/record_SUITE.erl +++ b/lib/compiler/test/record_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2003-2016. All Rights Reserved. +%% Copyright Ericsson AB 2003-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/regressions_SUITE.erl b/lib/compiler/test/regressions_SUITE.erl index f448d54933..9b0b9b0c38 100644 --- a/lib/compiler/test/regressions_SUITE.erl +++ b/lib/compiler/test/regressions_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2015-2016. All Rights Reserved. +%% Copyright Ericsson AB 2015-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/test/warnings_SUITE.erl b/lib/compiler/test/warnings_SUITE.erl index 42ff4f6133..33d55996ad 100644 --- a/lib/compiler/test/warnings_SUITE.erl +++ b/lib/compiler/test/warnings_SUITE.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2003-2017. All Rights Reserved. +%% Copyright Ericsson AB 2003-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. diff --git a/lib/compiler/vsn.mk b/lib/compiler/vsn.mk index 355113a94d..bb6ee00cd7 100644 --- a/lib/compiler/vsn.mk +++ b/lib/compiler/vsn.mk @@ -1 +1 @@ -COMPILER_VSN = 7.2.3 +COMPILER_VSN = 7.2.4 |