From 6bee2ac7d11668888d93ec4f93730bcae3e5fa79 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 1 Feb 2018 08:33:10 +0100 Subject: Introduce a new SSA-based intermediate format v3_codegen is replaced by three new passes: * beam_kernel_to_ssa which translates the Kernel Erlang format to a new SSA-based intermediate format. * beam_ssa_pre_codegen which prepares the SSA-based format for code generation, including register allocation. Registers are allocated using the linear scan algorithm. * beam_ssa_codegen which generates BEAM assembly code from the SSA-based format. It easier and more effective to optimize the SSA-based format before X and Y registers have been assigned. The current optimization passes constantly have to make sure no "holes" in the X register assignments are created (that is, that no X register becomes undefined that an allocation instruction depends on). This commit also introduces the following optimizations: * Replacing of tuple matching of records with the is_tagged_tuple instruction. (Replacing beam_record.) * Sinking of get_tuple_element instructions to just before the first use of the extracted values. As well as potentially avoiding extracting tuple elements when they are not actually used on all executions paths, this optimization could also reduce the number values that will need to be stored in Y registers. (Similar to beam_reorder, but more effective.) * Live optimizations, removing the definition of a variable that is not subsequently used (provided that the operation has no side effects), as well strength reduction of binary matching by replacing the extraction of value from a binary with a skip instruction. (Used to be done by beam_block, beam_utils, and v3_codegen.) * Removal of redundant bs_restore2 instructions. (Formerly done by beam_bs.) * Type-based optimizations across branches. More effective than the old beam_type pass that only did type-based optimizations in basic blocks. * Optimization of floating point instructions. (Formerly done by beam_type.) * Optimization of receive statements to introduce recv_mark and recv_set instructions. More effective with far fewer restrictions on what instructions are allowed between creating the reference and entering the receive statement. * Common subexpression elimination. (Formerly done by beam_block.) --- lib/compiler/src/beam_peep.erl | 69 +++++++++++++++++++++++++++++++++--------- 1 file changed, 55 insertions(+), 14 deletions(-) (limited to 'lib/compiler/src/beam_peep.erl') diff --git a/lib/compiler/src/beam_peep.erl b/lib/compiler/src/beam_peep.erl index 2b8dd40e29..74da6aa704 100644 --- a/lib/compiler/src/beam_peep.erl +++ b/lib/compiler/src/beam_peep.erl @@ -101,23 +101,13 @@ peep([{select,Op,R,F,Vls0}|Is], SeenTests0, Acc0) -> I = {jump,F}, peep([I|Is], gb_sets:empty(), Acc0); [{atom,_}=Value,Lbl] when Op =:= select_val -> - %% Single value left. Convert to regular test and pop redundant tests. + %% Single value left. Convert to regular test. Is1 = [{test,is_eq_exact,F,[R,Value]},{jump,Lbl}|Is], - case Acc0 of - [{test,is_atom,F,[R]}|Acc] -> - peep(Is1, SeenTests0, Acc); - _ -> - peep(Is1, SeenTests0, Acc0) - end; + peep(Is1, SeenTests0, Acc0); [{integer,_}=Value,Lbl] when Op =:= select_val -> - %% Single value left. Convert to regular test and pop redundant tests. + %% Single value left. Convert to regular test. Is1 = [{test,is_eq_exact,F,[R,Value]},{jump,Lbl}|Is], - case Acc0 of - [{test,is_integer,F,[R]}|Acc] -> - peep(Is1, SeenTests0, Acc); - _ -> - peep(Is1, SeenTests0, Acc0) - end; + peep(Is1, SeenTests0, Acc0); [Arity,Lbl] when Op =:= select_tuple_arity -> %% Single value left. Convert to regular test Is1 = [{test,test_arity,F,[R,Arity]},{jump,Lbl}|Is], @@ -126,6 +116,21 @@ peep([{select,Op,R,F,Vls0}|Is], SeenTests0, Acc0) -> I = {select,Op,R,F,Vls}, peep(Is, gb_sets:empty(), [I|Acc0]) end; +peep([{get_map_elements,Fail,Src,List}=I|Is], _SeenTests, Acc0) -> + SeenTests = gb_sets:empty(), + case simplify_get_map_elements(Fail, Src, List, Acc0) of + {ok,Acc} -> + peep(Is, SeenTests, Acc); + error -> + peep(Is, SeenTests, [I|Acc0]) + end; +peep([{test,has_map_fields,Fail,Ops}=I|Is], SeenTests, Acc0) -> + case simplify_has_map_fields(Fail, Ops, Acc0) of + {ok,Acc} -> + peep(Is, SeenTests, Acc); + error -> + peep(Is, SeenTests, [I|Acc0]) + end; peep([{test,Op,_,Ops}=I|Is], SeenTests0, Acc) -> case beam_utils:is_pure_test(I) of false -> @@ -176,3 +181,39 @@ prune_redundant_values([_Val,F|Vls], F) -> prune_redundant_values([Val,Lbl|Vls], F) -> [Val,Lbl|prune_redundant_values(Vls, F)]; prune_redundant_values([], _) -> []. + +simplify_get_map_elements(Fail, Src, {list,[Key,Dst]}, + [{get_map_elements,Fail,Src,{list,List1}}|Acc]) -> + case are_keys_literals([Key]) andalso are_keys_literals(List1) of + true -> + case member(Key, List1) of + true -> + %% The key is already in the other list. That is + %% very unusual, because there are optimizations to get + %% rid of duplicate keys. Therefore, don't try to + %% do anything smart here; just keep the + %% get_map_elements instructions separate. + error; + false -> + List = [Key,Dst|List1], + {ok,[{get_map_elements,Fail,Src,{list,List}}|Acc]} + end; + false -> + error + end; +simplify_get_map_elements(_, _, _, _) -> error. + +simplify_has_map_fields(Fail, [Src|Keys0], + [{test,has_map_fields,Fail,[Src|Keys1]}|Acc]) -> + case are_keys_literals(Keys0) andalso are_keys_literals(Keys1) of + true -> + Keys = Keys0 ++ Keys1, + {ok,[{test,has_map_fields,Fail,[Src|Keys]}|Acc]}; + false -> + error + end; +simplify_has_map_fields(_, _, _) -> error. + +are_keys_literals([{x,_}|_]) -> false; +are_keys_literals([{y,_}|_]) -> false; +are_keys_literals([_|_]) -> true. -- cgit v1.2.3