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.)

1 files changed, 4 insertions, 139 deletions

diff --git a/lib/compiler/src/beam_clean.erl b/lib/compiler/src/beam_clean.erl
index 5a9023c259..f5f0ac2218 100644
--- a/lib/compiler/src/beam_clean.erl
+++ b/lib/compiler/src/beam_clean.erl
@@ -23,7 +23,7 @@
 
 -export([module/2]).
 -export([clean_labels/1]).
--import(lists, [foldl/3,reverse/1]).
+-import(lists, [foldl/3]).
 
 -spec module(beam_utils:module_code(), [compile:option()]) ->
                     {'ok',beam_utils:module_code()}.
@@ -36,8 +36,7 @@ module({Mod,Exp,Attr,Fs0,_}, Opts) ->
     Used = find_all_used(WorkList, All, sets:from_list(WorkList)),
     Fs1 = remove_unused(Order, Used, All),
     {Fs2,Lc} = clean_labels(Fs1),
-    Fs3 = bs_fix(Fs2),
-    Fs = maybe_remove_lines(Fs3, Opts),
+    Fs = maybe_remove_lines(Fs2, Opts),
     {ok,{Mod,Exp,Attr,Fs,Lc}}.
 
 %% Determine the rootset, i.e. exported functions and
@@ -87,12 +86,8 @@ add_to_work_list(F, {Fs,Used}=Sets) ->
 
 %%%
 %%% Coalesce adjacent labels. Renumber all labels to eliminate gaps.
-%%% This cleanup will slightly reduce file size and slightly speed up loading.
-%%%
-%%% We also expand is_record/3 to a sequence of instructions. It is done
-%%% here merely because this module will always be called even if optimization
-%%% is turned off. We don't want to do the expansion in beam_asm because we
-%%% want to see the expanded code in a .S file.
+%%% This cleanup will slightly reduce file size and slightly speed up
+%%% loading.
 %%%
 
 -type label() :: beam_asm:label().
@@ -117,45 +112,6 @@ function_renumber([{function,Name,Arity,_Entry,Asm0}|Fs], St0, Acc) ->
     function_renumber(Fs, St, [{function,Name,Arity,St#st.entry,Asm}|Acc]);
 function_renumber([], St, Acc) -> {Acc,St}.
 
-renumber_labels([{bif,is_record,{f,_},
-		  [Term,{atom,Tag}=TagAtom,{integer,Arity}],Dst}|Is0], Acc, St) ->
-    ContLabel = 900000000+2*St#st.lc,
-    FailLabel = ContLabel+1,
-    Fail = {f,FailLabel},
-    Tmp = Dst,
-    Is = case is_record_tuple(Term, Tag, Arity) of
-	     yes ->
-		 [{move,{atom,true},Dst}|Is0];
-	     no ->
-		 [{move,{atom,false},Dst}|Is0];
-	     maybe ->
-		 [{test,is_tuple,Fail,[Term]},
-		  {test,test_arity,Fail,[Term,Arity]},
-		  {get_tuple_element,Term,0,Tmp},
-		  {test,is_eq_exact,Fail,[Tmp,TagAtom]},
-		  {move,{atom,true},Dst},
-		  {jump,{f,ContLabel}},
-		  {label,FailLabel},
-		  {move,{atom,false},Dst},
-		  {jump,{f,ContLabel}},	%Improves optimization by beam_dead.
-		  {label,ContLabel}|Is0]
-	 end,
-    renumber_labels(Is, Acc, St);
-renumber_labels([{test,is_record,{f,_}=Fail,
-		  [Term,{atom,Tag}=TagAtom,{integer,Arity}]}|Is0], Acc, St) ->
-    Tmp = {x,1022},
-    Is = case is_record_tuple(Term, Tag, Arity) of
-	     yes ->
-		 Is0;
-	     no ->
-		 [{jump,Fail}|Is0];
-	     maybe ->
-		 [{test,is_tuple,Fail,[Term]},
-		  {test,test_arity,Fail,[Term,Arity]},
-		  {get_tuple_element,Term,0,Tmp},
-		  {test,is_eq_exact,Fail,[Tmp,TagAtom]}|Is0]
-	 end,
-    renumber_labels(Is, Acc, St);
 renumber_labels([{label,Old}|Is], [{label,New}|_]=Acc, #st{lmap=D0}=St) ->
     D = [{Old,New}|D0],
     renumber_labels(Is, Acc, St#st{lmap=D});
@@ -169,12 +125,6 @@ renumber_labels([I|Is], Acc, St0) ->
     renumber_labels(Is, [I|Acc], St0);
 renumber_labels([], Acc, St) -> {Acc,St}.
 
-is_record_tuple({x,_}, _, _) -> maybe;
-is_record_tuple({y,_}, _, _) -> maybe;
-is_record_tuple({literal,Tuple}, Tag, Arity)
-  when element(1, Tuple) =:= Tag, tuple_size(Tuple) =:= Arity -> yes;
-is_record_tuple(_, _, _) -> no.
-
 function_replace([{function,Name,Arity,Entry,Asm0}|Fs], Dict, Acc) ->
     Asm = try
               Fb = fun(Old) -> throw({error,{undefined_label,Old}}) end,
@@ -189,91 +139,6 @@ function_replace([{function,Name,Arity,Entry,Asm0}|Fs], Dict, Acc) ->
 function_replace([], _, Acc) -> Acc.
 
 %%%
-%%% Final fixup of bs_start_match2/5,bs_save2/bs_restore2 instructions for
-%%% new bit syntax matching (introduced in R11B).
-%%%
-%%% Pass 1: Scan the code, looking for bs_restore2/2 instructions.
-%%%
-%%% Pass 2: Update bs_save2/2 and bs_restore/2 instructions. Remove
-%%% any bs_save2/2 instruction whose save position are never referenced
-%%% by any bs_restore2/2 instruction.
-%%%
-%%% Note this module can be invoked several times, so we must be careful
-%%% not to touch instructions that have already been fixed up.
-%%%
-
-bs_fix(Fs) ->
-    bs_fix(Fs, []).
-
-bs_fix([{function,Name,Arity,Entry,Asm0}|Fs], Acc) ->
-    Asm = bs_function(Asm0),
-    bs_fix(Fs, [{function,Name,Arity,Entry,Asm}|Acc]);
-bs_fix([], Acc) -> reverse(Acc).
-
-bs_function(Is) ->
-    Dict0 = bs_restores(Is, []),
-    S0 = sofs:relation(Dict0, [{context,save_point}]),
-    S1 = sofs:relation_to_family(S0),
-    S = sofs:to_external(S1),
-    Dict = make_save_point_dict(S, []),
-    bs_replace(Is, Dict, []).
-
-make_save_point_dict([{Ctx,Pts}|T], Acc0) ->
-    Acc = make_save_point_dict_1(Pts, Ctx, 0, Acc0),
-    make_save_point_dict(T, Acc);
-make_save_point_dict([], Acc) ->
-    gb_trees:from_orddict(ordsets:from_list(Acc)).
-
-make_save_point_dict_1([H|T], Ctx, I, Acc) ->
-    make_save_point_dict_1(T, Ctx, I+1, [{{Ctx,H},I}|Acc]);
-make_save_point_dict_1([], Ctx, I, Acc) ->
-    [{Ctx,I}|Acc].
-
-%% Pass 1.
-bs_restores([{bs_restore2,_,{Same,Same}}|Is], Dict) ->
-    %% This save point is special. No explicit save is needed.
-    bs_restores(Is, Dict);
-bs_restores([{bs_restore2,_,{atom,start}}|Is], Dict) ->
-    %% This instruction can occur if "compilation"
-    %% started from a .S file.
-    bs_restores(Is, Dict);
-bs_restores([{bs_restore2,_,{_,_}=SavePoint}|Is], Dict) ->
-    bs_restores(Is, [SavePoint|Dict]);
-bs_restores([_|Is], Dict) ->
-    bs_restores(Is, Dict);
-bs_restores([], Dict) -> Dict.
-    
-%% Pass 2.
-bs_replace([{test,bs_start_match2,F,Live,[Src,{context,Ctx}],CtxR}|T], Dict, Acc) ->
-    Slots = case gb_trees:lookup(Ctx, Dict) of
-		{value,Slots0} -> Slots0;
-		none -> 0
-	    end,
-    I = {test,bs_start_match2,F,Live,[Src,Slots],CtxR},
-    bs_replace(T, Dict, [I|Acc]);
-bs_replace([{bs_save2,CtxR,{_,_}=SavePoint}|T], Dict, Acc) ->
-    case gb_trees:lookup(SavePoint, Dict) of
-	{value,N} ->
-	    bs_replace(T, Dict, [{bs_save2,CtxR,N}|Acc]);
-	none ->
-	    bs_replace(T, Dict, Acc)
-    end;
-bs_replace([{bs_restore2,_,{atom,start}}=I|T], Dict, Acc) ->
-    %% This instruction can occur if "compilation"
-    %% started from a .S file.
-    bs_replace(T, Dict, [I|Acc]);    
-bs_replace([{bs_restore2,CtxR,{Same,Same}}|T], Dict, Acc) ->
-    %% This save point refers to the point in the binary where the match
-    %% started. It has a special name.
-    bs_replace(T, Dict, [{bs_restore2,CtxR,{atom,start}}|Acc]);
-bs_replace([{bs_restore2,CtxR,{_,_}=SavePoint}|T], Dict, Acc) ->
-    N = gb_trees:get(SavePoint, Dict),
-    bs_replace(T, Dict, [{bs_restore2,CtxR,N}|Acc]);
-bs_replace([I|Is], Dict, Acc) ->
-    bs_replace(Is, Dict, [I|Acc]);
-bs_replace([], _, Acc) -> reverse(Acc).
-
-%%%
 %%% Remove line instructions if requested.
 %%%