From 9212ce67e22e3f45190ded62bea82291d084351d Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 1 Nov 2018 05:19:48 +0100
Subject: beam_trim: Use maps/cerl_sets instead of gb_trees/gb_sets

---
 lib/compiler/src/beam_trim.erl | 22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)

diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl
index 1acbedd45b..61dd94d456 100644
--- a/lib/compiler/src/beam_trim.erl
+++ b/lib/compiler/src/beam_trim.erl
@@ -24,7 +24,7 @@
 -import(lists, [reverse/1,reverse/2,splitwith/2,sort/1]).
 
 -record(st,
-	{safe :: gb_sets:set(beam_asm:label()), %Safe labels.
+	{safe :: cerl_sets:set(beam_asm:label()), %Safe labels.
 	 lbl :: beam_utils:code_index()         %Code at each label.
 	 }).
 
@@ -132,16 +132,16 @@ create_map(Trim, []) ->
        (Any) -> Any
     end;
 create_map(Trim, Moves) ->
-    GbTree0 = [{Src,Dst-Trim} || {move,{y,Src},{y,Dst}} <- Moves],
-    GbTree = gb_trees:from_orddict(sort(GbTree0)),
-    IllegalTargets = gb_sets:from_list([Dst || {move,_,{y,Dst}} <- Moves]),
+    Map0 = [{Src,Dst-Trim} || {move,{y,Src},{y,Dst}} <- Moves],
+    Map = maps:from_list(Map0),
+    IllegalTargets = cerl_sets:from_list([Dst || {move,_,{y,Dst}} <- Moves]),
     fun({y,Y0}) when Y0 < Trim ->
-	    case gb_trees:lookup(Y0, GbTree) of
-		{value,Y} -> {y,Y};
-		none -> throw(not_possible)
-	    end;
+            case Map of
+                #{Y0:=Y} -> {y,Y};
+                #{} -> throw(not_possible)
+            end;
        ({y,Y}) ->
-	    case gb_sets:is_element(Y, IllegalTargets) of
+	    case cerl_sets:is_element(Y, IllegalTargets) of
 		true -> throw(not_possible);
 		false -> {y,Y-Trim}
 	    end;
@@ -225,7 +225,7 @@ safe_labels([{label,L},
     safe_labels(Is, [L|Acc]);
 safe_labels([_|Is], Acc) ->
     safe_labels(Is, Acc);
-safe_labels([], Acc) -> gb_sets:from_list(Acc).
+safe_labels([], Acc) -> cerl_sets:from_list(Acc).
 
 %% frame_layout([Instruction], [{kill,_}], St) ->
 %%      [{kill,Reg} | {live,Reg} | {dead,Reg}]
@@ -293,7 +293,7 @@ frame_size(_, _) -> throw(not_possible).
 frame_size_branch(0, Is, Safe) ->
     frame_size(Is, Safe);
 frame_size_branch(L, Is, Safe) ->
-    case gb_sets:is_member(L, Safe) of
+    case cerl_sets:is_element(L, Safe) of
 	false -> throw(not_possible);
 	true -> frame_size(Is, Safe)
     end.
-- 
cgit v1.2.3


From e7b3dcde36969be9442e05b18919ecb5b61bf6a4 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 1 Nov 2018 06:19:52 +0100
Subject: beam_trim, beam_jump: Print Name/Arity if there is a crash

This will help investigation of compiler bugs.
---
 lib/compiler/src/beam_jump.erl   | 20 +++++++++++++-------
 lib/compiler/src/beam_trim.erl   | 13 +++++++++----
 lib/compiler/test/misc_SUITE.erl |  8 ++++++++
 3 files changed, 30 insertions(+), 11 deletions(-)

diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl
index edc4522cc7..40a2211325 100644
--- a/lib/compiler/src/beam_jump.erl
+++ b/lib/compiler/src/beam_jump.erl
@@ -144,13 +144,19 @@ module({Mod,Exp,Attr,Fs0,Lc0}, _Opt) ->
 %%
 %%  NOTE: This function assumes that there are no labels inside blocks.
 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}.
+    try
+        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}
+    catch
+        Class:Error:Stack ->
+	    io:fwrite("Function: ~w/~w\n", [Name,Arity]),
+	    erlang:raise(Class, Error, Stack)
+    end.
 
 %%%
 %%% Scan instructions in execution order and remove redundant 'move'
diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl
index 61dd94d456..13cbedf3c0 100644
--- a/lib/compiler/src/beam_trim.erl
+++ b/lib/compiler/src/beam_trim.erl
@@ -36,10 +36,15 @@ module({Mod,Exp,Attr,Fs0,Lc}, _Opts) ->
     {ok,{Mod,Exp,Attr,Fs,Lc}}.
 
 function({function,Name,Arity,CLabel,Is0}) ->
-    %%ok = io:fwrite("~w: ~p\n", [?LINE,{Name,Arity}]),
-    St = #st{safe=safe_labels(Is0, []),lbl=beam_utils:index_labels(Is0)},
-    Is = trim(Is0, St, []),
-    {function,Name,Arity,CLabel,Is}.
+    try
+        St = #st{safe=safe_labels(Is0, []),lbl=beam_utils:index_labels(Is0)},
+        Is = trim(Is0, St, []),
+        {function,Name,Arity,CLabel,Is}
+    catch
+        Class:Error:Stack ->
+	    io:fwrite("Function: ~w/~w\n", [Name,Arity]),
+	    erlang:raise(Class, Error, Stack)
+    end.
 
 trim([{kill,_}|_]=Is0, St, Acc) ->
     {Kills0,Is1} = splitwith(fun({kill,_}) -> true;
diff --git a/lib/compiler/test/misc_SUITE.erl b/lib/compiler/test/misc_SUITE.erl
index c9acda2b6d..d6fc51448f 100644
--- a/lib/compiler/test/misc_SUITE.erl
+++ b/lib/compiler/test/misc_SUITE.erl
@@ -234,6 +234,10 @@ silly_coverage(Config) when is_list(Config) ->
 		      {label,2}|non_proper_list]}],99},
     expect_error(fun() -> beam_except:module(ExceptInput, []) end),
 
+    %% beam_jump
+    JumpInput = BlockInput,
+    expect_error(fun() -> beam_jump:module(JumpInput, []) end),
+
     %% beam_clean
     CleanInput = {?MODULE,[{foo,0}],[],
 		  [{function,foo,0,2,
@@ -243,6 +247,10 @@ silly_coverage(Config) when is_list(Config) ->
 		     {jump,{f,42}}]}],99},
     expect_error(fun() -> beam_clean:module(CleanInput, []) end),
 
+    %% beam_jump
+    TrimInput = BlockInput,
+    expect_error(fun() -> beam_trim:module(TrimInput, []) end),
+
     %% beam_peep. This is tricky. Use a select instruction with
     %% an odd number of elements in the list to crash
     %% prune_redundant_values/2 but not beam_clean:clean_labels/1.
-- 
cgit v1.2.3


From 181cfc4ef9d120c1188c8f28f306d7b0f106a80b Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 1 Nov 2018 07:24:46 +0100
Subject: beam_jump: Stop using beam_utils:is_killed/3

Prior to this commit, the optimizations using beam_utils:is_killed/3
were only executed a few times in the entire compiler test suite.
---
 lib/compiler/src/beam_jump.erl | 58 ++++--------------------------------------
 1 file changed, 5 insertions(+), 53 deletions(-)

diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl
index 40a2211325..d3a618d211 100644
--- a/lib/compiler/src/beam_jump.erl
+++ b/lib/compiler/src/beam_jump.erl
@@ -128,7 +128,7 @@
 %%% on the program state.
 %%% 
 
--import(lists, [dropwhile/2,foldl/3,mapfoldl/3,reverse/1,reverse/2]).
+-import(lists, [foldl/3,mapfoldl/3,reverse/1,reverse/2]).
 
 -type instruction() :: beam_utils:instruction().
 
@@ -410,7 +410,7 @@ find_fixpoint(OptFun, Is0) ->
 	Is -> find_fixpoint(OptFun, Is)
     end.
 
-opt([{test,_,{f,L}=Lbl,_}=I|[{jump,{f,L}}|_]=Is], Acc0, St0) ->
+opt([{test,_,{f,L}=Lbl,_}=I|[{jump,{f,L}}|_]=Is], Acc, St) ->
     %% We have
     %%    Test Label Ops
     %%    jump Label
@@ -419,23 +419,20 @@ opt([{test,_,{f,L}=Lbl,_}=I|[{jump,{f,L}}|_]=Is], Acc0, St0) ->
     case beam_utils:is_pure_test(I) of
 	false ->
 	    %% Test is not pure; we must keep it.
-	    opt(Is, [I|Acc0], label_used(Lbl, St0));
+	    opt(Is, [I|Acc], label_used(Lbl, St));
 	true ->
 	    %% The test is pure and its failure label is the same
 	    %% as in the jump that follows -- thus it is not needed.
-            %% Check if any of the previous instructions could also be eliminated.
-            {Acc,St} = opt_useless_loads(Acc0, L, St0),
 	    opt(Is, Acc, St)
     end;
-opt([{test,_,{f,L}=Lbl,_}=I|[{label,L}|_]=Is], Acc0, St0) ->
+opt([{test,_,{f,L}=Lbl,_}=I|[{label,L}|_]=Is], Acc, St) ->
     %% Similar to the above, except we have a fall-through rather than jump
     %%    Test Label Ops
     %%    label Label
     case beam_utils:is_pure_test(I) of
 	false ->
-	    opt(Is, [I|Acc0], label_used(Lbl, St0));
+	    opt(Is, [I|Acc], label_used(Lbl, St));
 	true ->
-            {Acc,St} = opt_useless_loads(Acc0, L, St0),
 	    opt(Is, Acc, St)
     end;
 opt([{test,Test0,{f,L}=Lbl,Ops}=I|[{jump,To}|Is]=Is0], Acc, St) ->
@@ -502,51 +499,6 @@ normalize_replace([{From,To0}|Rest], Replace, Acc) ->
 normalize_replace([], _Replace, Acc) ->
     maps:from_list(Acc).
 
-%% After eliminating a test, it might happen, that a register was only used
-%% in this test. Let's check if that was the case and if it was so, we can
-%% eliminate the load into the register completely.
-opt_useless_loads([{block,_}|_]=Is, L, #st{index={lazy,FIs}}=St) ->
-    opt_useless_loads(Is, L, St#st{index=beam_utils:index_labels(FIs)});
-opt_useless_loads([{block,Block0}|Is], L, #st{index=Index}=St) ->
-    case opt_useless_block_loads(Block0, L, Index) of
-        [] ->
-            opt_useless_loads(Is, L, St);
-        [_|_]=Block ->
-            {[{block,Block}|Is],St}
-    end;
-%% After eliminating the test and useless blocks, it might happen,
-%% that the previous test could also be eliminated.
-%% It might be that the label was already marked as used, even if ultimately,
-%% it never will be - we can't do much about it at that point, though
-opt_useless_loads([{test,_,{f,L},_}=I|Is], L, St) ->
-    case beam_utils:is_pure_test(I) of
-        false ->
-            {[I|Is],St};
-        true ->
-            opt_useless_loads(Is, L, St)
-    end;
-opt_useless_loads(Is, _L, St) ->
-    {Is,St}.
-
-opt_useless_block_loads([{set,[Dst],_,_}=I|Is0], L, Index) ->
-    BlockJump = [{block,Is0},{jump,{f,L}}],
-    case beam_utils:is_killed(Dst, BlockJump, Index) of
-        true ->
-            %% The register is killed and not used, we can remove the load.
-            %% Remove any `put` instructions in case we just
-            %% removed a `put_tuple` instruction.
-            Is = dropwhile(fun({set,_,_,put}) -> true;
-                              (_) -> false
-                           end, Is0),
-            opt_useless_block_loads(Is, L, Index);
-        false ->
-            [I|opt_useless_block_loads(Is0, L, Index)]
-    end;
-opt_useless_block_loads([I|Is], L, Index) ->
-    [I|opt_useless_block_loads(Is, L, Index)];
-opt_useless_block_loads([], _L, _Index) ->
-    [].
-
 collect_labels(Is, Label, #st{entry=Entry,replace=Replace} = St) ->
     collect_labels_1(Is, Label, Entry, Replace, St).
 
-- 
cgit v1.2.3


From ff758397d8a2e4cc6038e72bc09bcc063de1b621 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 1 Nov 2018 07:26:11 +0100
Subject: beam_trim: Stop using beam_utils:is_not_used/3

Eliminate the use of beam_utils:is_not_used/3 by implementing a simple
is_not_used() function in beam_trim itself. The new version actually
makes trimming possible in more circumstances, because
beam_utils:is_not_used/3 was too conservative for the purpose of stack
trimming (it was previously used for optimizations where it was
necessary to be more conservative).

Alternatives considered: I tried to implement stack trimming in
beam_ssa_codegen but it turned out to be a total mess. Not
surprisingly, it turns out that an optimization that renumbers
Y registers is hard to do on an intermediate representation that
still use variables instead of BEAM registers.
---
 lib/compiler/src/beam_trim.erl | 83 ++++++++++++++++++++++++++++++++++++++----
 1 file changed, 75 insertions(+), 8 deletions(-)

diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl
index 13cbedf3c0..0f1144e87f 100644
--- a/lib/compiler/src/beam_trim.erl
+++ b/lib/compiler/src/beam_trim.erl
@@ -21,12 +21,11 @@
 -module(beam_trim).
 -export([module/2]).
 
--import(lists, [reverse/1,reverse/2,splitwith/2,sort/1]).
+-import(lists, [member/2,reverse/1,reverse/2,splitwith/2,sort/1]).
 
 -record(st,
-	{safe :: cerl_sets:set(beam_asm:label()), %Safe labels.
-	 lbl :: beam_utils:code_index()         %Code at each label.
-	 }).
+	{safe :: cerl_sets:set(beam_asm:label()) %Safe labels.
+        }).
 
 -spec module(beam_utils:module_code(), [compile:option()]) ->
                     {'ok',beam_utils:module_code()}.
@@ -37,7 +36,7 @@ module({Mod,Exp,Attr,Fs0,Lc}, _Opts) ->
 
 function({function,Name,Arity,CLabel,Is0}) ->
     try
-        St = #st{safe=safe_labels(Is0, []),lbl=beam_utils:index_labels(Is0)},
+        St = #st{safe=safe_labels(Is0, [])},
         Is = trim(Is0, St, []),
         {function,Name,Arity,CLabel,Is}
     catch
@@ -236,9 +235,9 @@ safe_labels([], Acc) -> cerl_sets:from_list(Acc).
 %%      [{kill,Reg} | {live,Reg} | {dead,Reg}]
 %%  Figure out the layout of the stack frame.
 
-frame_layout(Is, Kills, #st{safe=Safe,lbl=D}) ->
+frame_layout(Is, Kills, #st{safe=Safe}) ->
     N = frame_size(Is, Safe),
-    IsKilled = fun(R) -> beam_utils:is_not_used(R, Is, D) end,
+    IsKilled = fun(R) -> is_not_used(R, Is) end,
     {N,frame_layout_1(Kills, 0, N, IsKilled, [])}.
 
 frame_layout_1([{kill,{y,Y}}=I|Ks], Y, N, IsKilled, Acc) ->
@@ -290,7 +289,8 @@ frame_size([{make_fun2,_,_,_,_}|Is], Safe) ->
     frame_size(Is, Safe);
 frame_size([{get_map_elements,{f,L},_,_}|Is], Safe) ->
     frame_size_branch(L, Is, Safe);
-frame_size([{deallocate,N}|_], _) -> N;
+frame_size([{deallocate,N}|_], _) ->
+    N;
 frame_size([{line,_}|Is], Safe) ->
     frame_size(Is, Safe);
 frame_size(_, _) -> throw(not_possible).
@@ -302,3 +302,70 @@ frame_size_branch(L, Is, Safe) ->
 	false -> throw(not_possible);
 	true -> frame_size(Is, Safe)
     end.
+
+%% is_not_used(Y, [Instruction]) -> true|false.
+%%  Test whether the value of Y is unused in the instruction sequence.
+%%  Return true if the value of Y is not used, and false if it is used.
+%%
+%%  This function handles the same instructions as frame_size/2. It
+%%  assumes that any labels in the instructions are safe labels.
+
+is_not_used(Y, [{apply,_}|Is]) ->
+    is_not_used(Y, Is);
+is_not_used(Y, [{bif,_,{f,_},Ss,Dst}|Is]) ->
+    is_not_used_ss_dst(Y, Ss, Dst, Is);
+is_not_used(Y, [{block,Bl}|Is]) ->
+    case is_not_used_block(Y, Bl) of
+        used -> false;
+        killed -> true;
+        transparent -> is_not_used(Y, Is)
+    end;
+is_not_used(Y, [{bs_init,_,_,_,Ss,Dst}|Is]) ->
+    is_not_used_ss_dst(Y, Ss, Dst, Is);
+is_not_used(Y, [{bs_put,{f,_},_,Ss}|Is]) ->
+    not member(Y, Ss) andalso is_not_used(Y, Is);
+is_not_used(Y, [{call,_,_}|Is]) ->
+    is_not_used(Y, Is);
+is_not_used(Y, [{call_ext,_,_}=I|Is]) ->
+    beam_jump:is_exit_instruction(I) orelse is_not_used(Y, Is);
+is_not_used(Y, [{call_fun,_}|Is]) ->
+    is_not_used(Y, Is);
+is_not_used(_Y, [{deallocate,_}|_]) ->
+    true;
+is_not_used(Y, [{gc_bif,_,{f,_},_Live,Ss,Dst}|Is]) ->
+    is_not_used_ss_dst(Y, Ss, Dst, Is);
+is_not_used(Y, [{get_map_elements,{f,_},S,{list,List}}|Is]) ->
+    {Ss,Ds} = beam_utils:split_even(List),
+    case member(Y, [S|Ss]) of
+	true ->
+	    false;
+	false ->
+            member(Y, Ds) orelse is_not_used(Y, Is)
+    end;
+is_not_used(Y, [{kill,Yreg}|Is]) ->
+    Y =:= Yreg orelse is_not_used(Y, Is);
+is_not_used(Y, [{line,_}|Is]) ->
+    is_not_used(Y, Is);
+is_not_used(Y, [{make_fun2,_,_,_,_}|Is]) ->
+    is_not_used(Y, Is);
+is_not_used(Y, [{test,_,_,Ss}|Is]) ->
+    not member(Y, Ss) andalso is_not_used(Y, Is);
+is_not_used(Y, [{test,_Op,{f,_},_Live,Ss,Dst}|Is]) ->
+    is_not_used_ss_dst(Y, Ss, Dst, Is).
+
+is_not_used_block(Y, [{set,Ds,Ss,_}|Is]) ->
+    case member(Y, Ss) of
+        true ->
+            used;
+        false ->
+            case member(Y, Ds) of
+                true ->
+                    killed;
+                false ->
+                    is_not_used_block(Y, Is)
+            end
+    end;
+is_not_used_block(_Y, []) -> transparent.
+
+is_not_used_ss_dst(Y, Ss, Dst, Is) ->
+    not member(Y, Ss) andalso (Y =:= Dst orelse is_not_used(Y, Is)).
-- 
cgit v1.2.3


From 4ae91649adf139aa6b2890065006203e14775a70 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 1 Nov 2018 07:35:29 +0100
Subject: beam_utils: Remove unused API functions

Remove the now unused beam_utils:is_not_used/3 and
beam_utils:is_killed/3 functions and friends.

Starting out as simple functions a long time ago, those functions have
grown and grown to support more optimizations. The number of bugs
found and fixed in beam_utils has also grown over time.
---
 lib/compiler/src/beam_utils.erl | 542 +---------------------------------------
 1 file changed, 4 insertions(+), 538 deletions(-)

diff --git a/lib/compiler/src/beam_utils.erl b/lib/compiler/src/beam_utils.erl
index 5156a04f6b..6e6574c0b3 100644
--- a/lib/compiler/src/beam_utils.erl
+++ b/lib/compiler/src/beam_utils.erl
@@ -18,23 +18,14 @@
 %% %CopyrightEnd%
 %%
 %% Purpose : Common utilities used by several optimization passes.
-%% 
+%%
 
 -module(beam_utils).
--export([is_killed/3,is_killed_at/3,is_not_used/3,
-	 empty_label_index/0,index_label/3,index_labels/1,replace_labels/4,
-	 code_at/2,is_pure_test/1,
-	 split_even/1]).
+-export([replace_labels/4,is_pure_test/1,split_even/1]).
 
 -export_type([code_index/0,module_code/0,instruction/0]).
 
--import(lists, [map/2,member/2,sort/1,reverse/1]).
-
--define(is_const(Val), (Val =:= nil orelse
-                        element(1, Val) =:= integer orelse
-                        element(1, Val) =:= float orelse
-                        element(1, Val) =:= atom orelse
-                        element(1, Val) =:= literal)).
+-import(lists, [map/2,reverse/1]).
 
 %% instruction() describes all instructions that are used during optimization
 %% (from beam_a to beam_z).
@@ -52,97 +43,6 @@
 -type fail() :: beam_asm:fail() | 'fail'.
 -type test() :: {'test',atom(),fail(),[beam_asm:src()]} |
 		{'test',atom(),fail(),integer(),list(),beam_asm:reg()}.
--type result_cache() :: gb_trees:tree(beam_asm:label(), 'killed' | 'used').
-
--record(live,
-	{lbl :: code_index(),            %Label to code index.
-	 res :: result_cache()}).        %Result cache for each label.
-
-%% is_killed(Register, [Instruction], State) -> true|false
-%%  Determine whether a register is killed by the instruction sequence.
-%%  If true is returned, it means that the register will not be
-%%  referenced in ANY way (not even indirectly by an allocate instruction);
-%%  i.e. it is OK to enter the instruction sequence with Register
-%%  containing garbage.
-%%
-%%  The state (constructed by index_instructions/1) is used to allow us
-%%  to determine the kill state across branches.
-
--spec is_killed(beam_asm:reg(), [instruction()], code_index()) -> boolean().
-
-is_killed(R, Is, D) ->
-    St = #live{lbl=D,res=gb_trees:empty()},
-    case check_liveness(R, Is, St) of
-	{killed,_} -> true;
-	{exit_not_used,_} -> false;
-	{_,_} -> false
-    end.
-
-%% is_killed_at(Reg, Lbl, State) -> true|false
-%%  Determine whether Reg is killed at label Lbl.
-
--spec is_killed_at(beam_asm:reg(), beam_asm:label(), code_index()) -> boolean().
-
-is_killed_at(R, Lbl, D) when is_integer(Lbl) ->
-    St0 = #live{lbl=D,res=gb_trees:empty()},
-    case check_liveness_at(R, Lbl, St0) of
-	{killed,_} -> true;
-	{exit_not_used,_} -> false;
-	{_,_} -> false
-    end.
-
-%% is_not_used(Register, [Instruction], State) -> true|false
-%%  Determine whether a register is never used in the instruction sequence
-%%  (it could still be referenced by an allocate instruction, meaning that
-%%  it MUST be initialized, but that its value does not matter).
-%%    The state is used to allow us to determine the usage state
-%%  across branches.
-
--spec is_not_used(beam_asm:reg(), [instruction()], code_index()) -> boolean().
-
-is_not_used(R, Is, D) ->
-    St = #live{lbl=D,res=gb_trees:empty()},
-    case check_liveness(R, Is, St) of
-	{used,_} -> false;
-	{exit_not_used,_} -> true;
-	{_,_} -> true
-    end.
-
-%% index_labels(FunctionIs) -> State
-%%  Index the instruction sequence so that we can quickly
-%%  look up the instruction following a specific label.
-
--spec index_labels([instruction()]) -> code_index().
-
-index_labels(Is) ->
-    index_labels_1(Is, []).
-
-%% empty_label_index() -> State
-%%  Create an empty label index.
-
--spec empty_label_index() -> code_index().
-
-empty_label_index() ->
-    gb_trees:empty().
-
-%% index_label(Label, [Instruction], State) -> State
-%%  Add an index for a label.
-
--spec index_label(beam_asm:label(), [instruction()], code_index()) ->
-   code_index().
-
-index_label(Lbl, Is0, Acc) ->
-    Is = drop_labels(Is0),
-    gb_trees:enter(Lbl, Is, Acc).
-
-
-%% code_at(Label, State) -> [I].
-%%  Retrieve the code at the given label.
-
--spec code_at(beam_asm:label(), code_index()) -> [instruction()].
-
-code_at(L, Ll) ->
-    gb_trees:get(L, Ll).
 
 %% replace_labels(FunctionIs, Tail, ReplaceDb, Fallback) -> FunctionIs.
 %%  Replace all labels in instructions according to the ReplaceDb.
@@ -175,7 +75,7 @@ is_pure_test({test,test_arity,_,[_,_]}) -> true;
 is_pure_test({test,has_map_fields,_,[_|_]}) -> true;
 is_pure_test({test,is_bitstr,_,[_]}) -> true;
 is_pure_test({test,is_function2,_,[_,_]}) -> true;
-is_pure_test({test,Op,_,Ops}) -> 
+is_pure_test({test,Op,_,Ops}) ->
     erl_internal:new_type_test(Op, length(Ops)).
 
 %% split_even/1
@@ -189,438 +89,6 @@ split_even(Rs) -> split_even(Rs, [], []).
 %%% Local functions.
 %%%
 
-
-%% check_liveness(Reg, [Instruction], #live{}) ->
-%%                      {killed | not_used | used, #live{}}
-%%  Find out whether Reg is used or killed in instruction sequence.
-%%
-%%    killed - Reg is assigned or killed by an allocation instruction.
-%%    not_used - the value of Reg is not used, but Reg must not be garbage
-%%    exit_not_used - the value of Reg is not used, but must not be garbage
-%%                    because the stack will be scanned because an
-%%                    exit BIF will raise an exception
-%%    used - Reg is used
-
-check_liveness({fr,_}, _, St) ->
-    %% Conservatively always consider the floating point register used.
-    {used,St};
-check_liveness(R, [{block,Blk}|Is], St0) ->
-    case check_liveness_block(R, Blk, St0) of
-	{transparent,St1} ->
-	    check_liveness(R, Is, St1);
-	{alloc_used,St1} ->
-            %% Used by an allocating instruction, but value not referenced.
-            %% Must check the rest of the instructions.
-	    not_used(check_liveness(R, Is, St1));
-	{Other,_}=Res when is_atom(Other) ->
-	    Res
-    end;
-check_liveness(R, [{label,_}|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness(R, [{test,_,{f,Fail},As}|Is], St0) ->
-    case member(R, As) of
-	true ->
-	    {used,St0};
-	false ->
-	    case check_liveness_at(R, Fail, St0) of
-		{killed,St1} ->
-		    check_liveness(R, Is, St1);
-		{exit_not_used,St1} ->
-		    not_used(check_liveness(R, Is, St1));
-		{not_used,St1} ->
-		    not_used(check_liveness(R, Is, St1));
-		{used,_}=Used ->
-		    Used
-	    end
-    end;
-check_liveness(R, [{test,Op,Fail,Live,Ss,Dst}|Is], St) ->
-    %% Check this instruction as a block to get a less conservative
-    %% result if the caller is is_not_used/3.
-    Block = [{set,[Dst],Ss,{alloc,Live,{bif,Op,Fail}}}],
-    check_liveness(R, [{block,Block}|Is], St);
-check_liveness(R, [{select,_,R,_,_}|_], St) ->
-    {used,St};
-check_liveness(R, [{select,_,_,Fail,Branches}|_], St) ->
-    check_liveness_everywhere(R, [Fail|Branches], St);
-check_liveness(R, [{jump,{f,F}}|_], St) ->
-    check_liveness_at(R, F, St);
-check_liveness(R, [{case_end,Used}|_], St) ->
-    check_liveness_exit(R, Used, St);
-check_liveness(R, [{try_case_end,Used}|_], St) ->
-    check_liveness_exit(R, Used, St);
-check_liveness(R, [{badmatch,Used}|_], St) ->
-    check_liveness_exit(R, Used, St);
-check_liveness(R, [if_end|_], St) ->
-    check_liveness_exit(R, ignore, St);
-check_liveness(R, [{func_info,_,_,Ar}|_], St) ->
-    case R of
-	{x,X} when X < Ar -> {used,St};
-	_ -> {killed,St}
-    end;
-check_liveness(R, [{kill,R}|_], St) ->
-    {killed,St};
-check_liveness(R, [{kill,_}|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness(R, [{bs_init,_,_,none,Ss,Dst}|Is], St) ->
-    case member(R, Ss) of
-	true ->
-	    {used,St};
-	false ->
-	    if
-		R =:= Dst -> {killed,St};
-		true -> check_liveness(R, Is, St)
-	    end
-    end;
-check_liveness(R, [{bs_init,_,_,Live,Ss,Dst}|Is], St) ->
-    case R of
-	{x,X} ->
-            case member(R, Ss) of
-                true ->
-                    {used,St};
-                false ->
-                    if
-                        X < Live ->
-                            not_used(check_liveness(R, Is, St));
-                        true ->
-                            {killed,St}
-                    end
-	    end;
-	{y,_} ->
-	    case member(R, Ss) of
-		true -> {used,St};
-		false ->
-                    %% If the exception is taken, the stack may
-                    %% be scanned. Therefore the register is not
-                    %% guaranteed to be killed.
-		    if
-                        R =:= Dst -> {not_used,St};
-			true -> not_used(check_liveness(R, Is, St))
-		    end
-	    end
-    end;
-check_liveness(R, [{deallocate,_}|Is], St) ->
-    case R of
-	{y,_} -> {killed,St};
-	_ -> check_liveness(R, Is, St)
-    end;
-check_liveness({x,_}=R, [return|_], St) ->
-    case R of
-	{x,0} -> {used,St};
-	{x,_} -> {killed,St}
-    end;
-check_liveness(R, [{call,Live,_}|Is], St) ->
-    case R of
-	{x,X} when X < Live -> {used,St};
-	{x,_} -> {killed,St};
-	{y,_} -> not_used(check_liveness(R, Is, St))
-    end;
-check_liveness(R, [{call_ext,Live,_}=I|Is], St) ->
-    case R of
-	{x,X} when X < Live ->
-	    {used,St};
-	{x,_} ->
-	    {killed,St};
-	{y,_} ->
-	    case beam_jump:is_exit_instruction(I) of
-		false ->
-		    not_used(check_liveness(R, Is, St));
-		true ->
-		    %% We must make sure we don't check beyond this
-		    %% instruction or we will fall through into random
-		    %% unrelated code and get stuck in a loop.
-		    {exit_not_used,St}
-	    end
-    end;
-check_liveness(R, [{call_fun,Live}|Is], St) ->
-    case R of
-	{x,X} when X =< Live -> {used,St};
-	{x,_} -> {killed,St};
-	{y,_} -> not_used(check_liveness(R, Is, St))
-    end;
-check_liveness(R, [{apply,Args}|Is], St) ->
-    case R of
-	{x,X} when X < Args+2 -> {used,St};
-	{x,_} -> {killed,St};
-	{y,_} -> not_used(check_liveness(R, Is, St))
-    end;
-check_liveness(R, [{bif,Op,Fail,Ss,D}|Is], St) ->
-    Set = {set,[D],Ss,{bif,Op,Fail}},
-    check_liveness(R, [{block,[Set]}|Is], St);
-check_liveness(R, [{gc_bif,Op,{f,Fail},Live,Ss,D}|Is], St) ->
-    Set = {set,[D],Ss,{alloc,Live,{gc_bif,Op,Fail}}},
-    check_liveness(R, [{block,[Set]}|Is], St);
-check_liveness(R, [{bs_put,{f,0},_,Ss}|Is], St) ->
-    case member(R, Ss) of
-	true -> {used,St};
-	false -> check_liveness(R, Is, St)
-    end;
-check_liveness(R, [{bs_restore2,S,_}|Is], St) ->
-    case R of
-	S -> {used,St};
-	_ -> check_liveness(R, Is, St)
-    end;
-check_liveness(R, [{bs_save2,S,_}|Is], St) ->
-    case R of
-	S -> {used,St};
-	_ -> check_liveness(R, Is, St)
-    end;
-check_liveness(R, [{move,S,D}|Is], St) ->
-    case R of
-	S -> {used,St};
-	D -> {killed,St};
-	_ -> check_liveness(R, Is, St)
-    end;
-check_liveness(R, [{make_fun2,_,_,_,NumFree}|Is], St) ->
-    case R of
-	{x,X} when X < NumFree -> {used,St};
-	{x,_} -> {killed,St};
-	{y,_} -> not_used(check_liveness(R, Is, St))
-    end;
-check_liveness(R, [{'catch'=Op,Y,Fail}|Is], St) ->
-    Set = {set,[Y],[],{try_catch,Op,Fail}},
-    check_liveness(R, [{block,[Set]}|Is], St);
-check_liveness(R, [{'try'=Op,Y,Fail}|Is], St) ->
-    Set = {set,[Y],[],{try_catch,Op,Fail}},
-    check_liveness(R, [{block,[Set]}|Is], St);
-check_liveness(R, [{try_end,Y}|Is], St) ->
-    case R of
-	Y ->
-	    {killed,St};
-	{y,_} ->
-	    %% y registers will be used if an exception occurs and
-	    %% control transfers to the label given in the previous
-	    %% try/2 instruction.
-	    {used,St};
-	_ ->
-	    check_liveness(R, Is, St)
-    end;
-check_liveness(R, [{catch_end,Y}|Is], St) ->
-    case R of
-	Y -> {killed,St};
-	_ -> check_liveness(R, Is, St)
-    end;
-check_liveness(R, [{get_tuple_element,S,_,D}|Is], St) ->
-    case R of
-	S -> {used,St};
-	D -> {killed,St};
-	_ -> check_liveness(R, Is, St)
-    end;
-check_liveness(R, [{loop_rec,{f,_},{x,0}}|_], St) ->
-    case R of
-	{x,_} ->
-	    {killed,St};
-	_ ->
-	    %% y register. Rarely happens. Be very conversative and
-	    %% assume it's used.
-	    {used,St}
-    end;
-check_liveness(R, [{loop_rec_end,{f,Fail}}|_], St) ->
-    check_liveness_at(R, Fail, St);
-check_liveness(R, [{line,_}|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness(R, [{get_map_elements,{f,Fail},S,{list,L}}|Is], St0) ->
-    {Ss,Ds} = split_even(L),
-    case member(R, [S|Ss]) of
-	true ->
-	    {used,St0};
-	false ->
-	    case check_liveness_at(R, Fail, St0) of
-		{killed,St}=Killed ->
-		    case member(R, Ds) of
-			true -> Killed;
-			false -> check_liveness(R, Is, St)
-		    end;
-		Other ->
-		    Other
-	    end
-    end;
-check_liveness(R, [{put_map,F,Op,S,D,Live,{list,Puts}}|Is], St) ->
-    Set = {set,[D],[S|Puts],{alloc,Live,{put_map,Op,F}}},
-    check_liveness(R, [{block,[Set]}||Is], St);
-check_liveness(R, [{put_tuple,Ar,D}|Is], St) ->
-    Set = {set,[D],[],{put_tuple,Ar}},
-    check_liveness(R, [{block,[Set]}||Is], St);
-check_liveness(R, [{put_list,S1,S2,D}|Is], St) ->
-    Set = {set,[D],[S1,S2],put_list},
-    check_liveness(R, [{block,[Set]}||Is], St);
-check_liveness(R, [{test_heap,N,Live}|Is], St) ->
-    I = {block,[{set,[],[],{alloc,Live,{nozero,nostack,N,[]}}}]},
-    check_liveness(R, [I|Is], St);
-check_liveness(R, [{allocate_zero,N,Live}|Is], St) ->
-    I = {block,[{set,[],[],{alloc,Live,{zero,N,0,[]}}}]},
-    check_liveness(R, [I|Is], St);
-check_liveness(R, [{get_hd,S,D}|Is], St) ->
-    I = {block,[{set,[D],[S],get_hd}]},
-    check_liveness(R, [I|Is], St);
-check_liveness(R, [{get_tl,S,D}|Is], St) ->
-    I = {block,[{set,[D],[S],get_tl}]},
-    check_liveness(R, [I|Is], St);
-check_liveness(R, [remove_message|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness({x,X}, [build_stacktrace|_], St) when X > 0 ->
-    {killed,St};
-check_liveness(R, [{recv_mark,_}|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness(R, [{recv_set,_}|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness(R, [{'%',_}|Is], St) ->
-    check_liveness(R, Is, St);
-check_liveness(_R, Is, St) when is_list(Is) ->
-    %% Not implemented. Conservatively assume that the register is used.
-    {used,St}.
-
-check_liveness_everywhere(R, Lbls, St0) ->
-    check_liveness_everywhere_1(R, Lbls, killed, St0).
-
-check_liveness_everywhere_1(R, [{f,Lbl}|T], Res0, St0) ->
-    {Res1,St} = check_liveness_at(R, Lbl, St0),
-    Res = case Res1 of
-	      killed -> Res0;
-	      _ -> Res1
-	  end,
-    case Res of
-	used -> {used,St};
-	_ -> check_liveness_everywhere_1(R, T, Res, St)
-    end;
-check_liveness_everywhere_1(R, [_|T], Res, St) ->
-    check_liveness_everywhere_1(R, T, Res, St);
-check_liveness_everywhere_1(_, [], Res, St) ->
-    {Res,St}.
-
-check_liveness_at(R, Lbl, #live{lbl=Ll,res=ResMemorized}=St0) ->
-    case gb_trees:lookup(Lbl, ResMemorized) of
-	{value,Res} ->
-	    {Res,St0};
-	none ->
-	    {Res,St} = case gb_trees:lookup(Lbl, Ll) of
-			   {value,Is} -> check_liveness(R, Is, St0);
-			   none -> {used,St0}
-		       end,
-	    {Res,St#live{res=gb_trees:insert(Lbl, Res, St#live.res)}}
-    end.
-
-not_used({used,_}=Res) -> Res;
-not_used({_,St}) -> {not_used,St}.
-
-check_liveness_exit(R, R, St) -> {used,St};
-check_liveness_exit({x,_}, _, St) -> {killed,St};
-check_liveness_exit({y,_}, _, St) -> {exit_not_used,St}.
-
-%% check_liveness_block(Reg, [Instruction], State) ->
-%%     {killed | not_used | used | alloc_used | transparent,State'}
-%%  Finds out how Reg is used in the instruction sequence inside a block.
-%%  Returns one of:
-%%    killed - Reg is assigned a new value or killed by an
-%%       allocation instruction
-%%    not_used - The value is not used, but the register is referenced
-%%       e.g. by an allocation instruction
-%%    transparent - Reg is neither used nor killed
-%%    alloc_used - Used only in an allocate instruction
-%%    used - Reg is explicitly used by an instruction
-%%
-%%  Annotations are not allowed.
-%%
-%%  (Unknown instructions will cause an exception.)
-
-check_liveness_block({x,X}=R, [{set,Ds,Ss,{alloc,Live,Op}}|Is], St0) ->
-    if 
-	X >= Live ->
-	    {killed,St0};
-	true ->
-	    case check_liveness_block_1(R, Ss, Ds, Op, Is, St0) of
-                {transparent,St} -> {alloc_used,St};
-		{_,_}=Res -> not_used(Res)
-	    end
-    end;
-check_liveness_block({y,_}=R, [{set,Ds,Ss,{alloc,_Live,Op}}|Is], St0) ->
-    case check_liveness_block_1(R, Ss, Ds, Op, Is, St0) of
-        {transparent,St} -> {alloc_used,St};
-        {_,_}=Res -> not_used(Res)
-    end;
-check_liveness_block({y,_}=R, [{set,Ds,Ss,{try_catch,_,Op}}|Is], St0) ->
-    case Ds of
-        [R] ->
-            {killed,St0};
-        _ ->
-            case check_liveness_block_1(R, Ss, Ds, Op, Is, St0) of
-                {exit_not_used,St} ->
-                    {used,St};
-                {transparent,St} ->
-                    %% Conservatively assumed that it is used.
-                    {used,St};
-                {_,_}=Res ->
-                    Res
-            end
-    end;
-check_liveness_block(R, [{set,Ds,Ss,Op}|Is], St) ->
-    check_liveness_block_1(R, Ss, Ds, Op, Is, St);
-check_liveness_block(_, [], St) -> {transparent,St}.
-
-check_liveness_block_1(R, Ss, Ds, Op, Is, St0) ->
-    case member(R, Ss) of
-	true ->
-	    {used,St0};
-	false ->
-	    case check_liveness_block_2(R, Op, Ss, St0) of
-		{killed,St} ->
-		    case member(R, Ds) of
-			true -> {killed,St};
-			false -> check_liveness_block(R, Is, St)
-		    end;
-		{exit_not_used,St} ->
-		    case member(R, Ds) of
-			true -> {exit_not_used,St};
-			false -> check_liveness_block(R, Is, St)
-		    end;
-		{not_used,St} ->
-		    not_used(case member(R, Ds) of
-				 true -> {killed,St};
-				 false -> check_liveness_block(R, Is, St)
-			     end);
-		{used,St} ->
-		    {used,St}
-	    end
-    end.
-
-check_liveness_block_2(R, {gc_bif,Op,{f,Lbl}}, Ss, St) ->
-    check_liveness_block_3(R, Lbl, {Op,length(Ss)}, St);
-check_liveness_block_2(R, {bif,Op,{f,Lbl}}, Ss, St) ->
-    Arity = length(Ss),
-    case erl_internal:comp_op(Op, Arity) orelse
-	erl_internal:new_type_test(Op, Arity) of
-	true ->
-	    {killed,St};
-	false ->
-	    check_liveness_block_3(R, Lbl, {Op,length(Ss)}, St)
-    end;
-check_liveness_block_2(R, {put_map,_Op,{f,Lbl}}, _Ss, St) ->
-    check_liveness_block_3(R, Lbl, {unsafe,0}, St);
-check_liveness_block_2(_, _, _, St) ->
-    {killed,St}.
-
-check_liveness_block_3({x,_}, 0, _FA, St) ->
-    {killed,St};
-check_liveness_block_3({y,_}, 0, {F,A}, St) ->
-    %% If the exception is thrown, the stack may be scanned,
-    %% thus implicitly using the y register.
-    case erl_bifs:is_safe(erlang, F, A) of
-        true -> {killed,St};
-        false -> {used,St}
-    end;
-check_liveness_block_3(R, Lbl, _FA, St0) ->
-    check_liveness_at(R, Lbl, St0).
-
-index_labels_1([{label,Lbl}|Is0], Acc) ->
-    Is = drop_labels(Is0),
-    index_labels_1(Is0, [{Lbl,Is}|Acc]);
-index_labels_1([_|Is], Acc) ->
-    index_labels_1(Is, Acc);
-index_labels_1([], Acc) -> gb_trees:from_orddict(sort(Acc)).
-
-drop_labels([{label,_}|Is]) -> drop_labels(Is);
-drop_labels(Is) -> Is.
-
-
 replace_labels_1([{test,Test,{f,Lbl},Ops}|Is], Acc, D, Fb) ->
     replace_labels_1(Is, [{test,Test,{f,label(Lbl, D, Fb)},Ops}|Acc], D, Fb);
 replace_labels_1([{test,Test,{f,Lbl},Live,Ops,Dst}|Is], Acc, D, Fb) ->
@@ -676,8 +144,6 @@ label(Old, D, Fb) ->
         _ -> Fb(Old)
     end.
 
-%% live_opt/4.
-
 split_even([], Ss, Ds) ->
     {reverse(Ss),reverse(Ds)};
 split_even([S,D|Rs], Ss, Ds) ->
-- 
cgit v1.2.3


From 1565b1518f77b2c078c59c2554305b7dca668f72 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 1 Nov 2018 08:18:19 +0100
Subject: beam_trim: Handle the new binary matching instructions

---
 lib/compiler/src/beam_trim.erl       | 15 +++++++++++++++
 lib/compiler/test/bs_match_SUITE.erl | 12 ++++++++++++
 2 files changed, 27 insertions(+)

diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl
index 0f1144e87f..c11ecab927 100644
--- a/lib/compiler/src/beam_trim.erl
+++ b/lib/compiler/src/beam_trim.erl
@@ -166,6 +166,12 @@ try_remap([], _, _) -> throw(not_possible).
 remap([{block,Bl0}|Is], Map, Acc) ->
     Bl = remap_block(Bl0, Map, []),
     remap(Is, Map, [{block,Bl}|Acc]);
+remap([{bs_get_tail,Src,Dst,Live}|Is], Map, Acc) ->
+    I = {bs_get_tail,Map(Src),Map(Dst),Live},
+    remap(Is, Map, [I|Acc]);
+remap([{bs_set_position,Src1,Src2}|Is], Map, Acc) ->
+    I = {bs_set_position,Map(Src1),Map(Src2)},
+    remap(Is, Map, [I|Acc]);
 remap([{call_fun,_}=I|Is], Map, Acc) ->
     remap(Is, Map, [I|Acc]);
 remap([{call,_,_}=I|Is], Map, Acc) ->
@@ -293,6 +299,10 @@ frame_size([{deallocate,N}|_], _) ->
     N;
 frame_size([{line,_}|Is], Safe) ->
     frame_size(Is, Safe);
+frame_size([{bs_set_position,_,_}|Is], Safe) ->
+    frame_size(Is, Safe);
+frame_size([{bs_get_tail,_,_,_}|Is], Safe) ->
+    frame_size(Is, Safe);
 frame_size(_, _) -> throw(not_possible).
 
 frame_size_branch(0, Is, Safe) ->
@@ -320,10 +330,15 @@ is_not_used(Y, [{block,Bl}|Is]) ->
         killed -> true;
         transparent -> is_not_used(Y, Is)
     end;
+is_not_used(Y, [{bs_get_tail,Src,Dst,_}|Is]) ->
+    is_not_used_ss_dst(Y, [Src], Dst, Is);
 is_not_used(Y, [{bs_init,_,_,_,Ss,Dst}|Is]) ->
     is_not_used_ss_dst(Y, Ss, Dst, Is);
 is_not_used(Y, [{bs_put,{f,_},_,Ss}|Is]) ->
     not member(Y, Ss) andalso is_not_used(Y, Is);
+is_not_used(Y, [{bs_set_position,Src1,Src2}|Is]) ->
+    Y =/= Src1 andalso Y =/= Src2 andalso
+        is_not_used(Y, Is);
 is_not_used(Y, [{call,_,_}|Is]) ->
     is_not_used(Y, Is);
 is_not_used(Y, [{call_ext,_,_}=I|Is]) ->
diff --git a/lib/compiler/test/bs_match_SUITE.erl b/lib/compiler/test/bs_match_SUITE.erl
index 0c6db96081..01f302ad21 100644
--- a/lib/compiler/test/bs_match_SUITE.erl
+++ b/lib/compiler/test/bs_match_SUITE.erl
@@ -742,6 +742,10 @@ coverage(Config) when is_list(Config) ->
     binary = coverage_bitstring(<<7>>),
     bitstring = coverage_bitstring(<<7:4>>),
     other = coverage_bitstring([a]),
+
+    {done,<<17,53>>,[253,155,200]} =
+        coverage_trim(<<253,155,200,17,53>>, e0, e1, e2, e3, []),
+
     ok.
 
 coverage_fold(Fun, Acc, <<H,T/binary>>) ->
@@ -836,6 +840,14 @@ coverage_bitstring(Bin) when is_binary(Bin) -> binary;
 coverage_bitstring(<<_/bitstring>>) -> bitstring;
 coverage_bitstring(_) -> other.
 
+coverage_trim(<<C:8,T/binary>> = Bin, E0, E1, E2, E3, Acc) ->
+    case id(C > 128) of
+        true ->
+            coverage_trim(T, E0, E1, E2, E3, [C|Acc]);
+        false ->
+            {done,Bin,lists:reverse(Acc)}
+    end.
+
 multiple_uses(Config) when is_list(Config) ->
     {344,62879,345,<<245,159,1,89>>} = multiple_uses_1(<<1,88,245,159,1,89>>),
     true = multiple_uses_2(<<0,0,197,18>>),
-- 
cgit v1.2.3


From ae481c6c374f4e54b6cad44aea02322c23e105b5 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 1 Nov 2018 11:58:07 +0100
Subject: beam_trim: Recognize more safe labels

Recognize more safe labels to enable stack trimming in more
circumstances.
---
 lib/compiler/src/beam_trim.erl | 57 ++++++++++++++++++++++++++++++++----------
 1 file changed, 44 insertions(+), 13 deletions(-)

diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl
index c11ecab927..f8efc38d53 100644
--- a/lib/compiler/src/beam_trim.erl
+++ b/lib/compiler/src/beam_trim.erl
@@ -21,7 +21,7 @@
 -module(beam_trim).
 -export([module/2]).
 
--import(lists, [member/2,reverse/1,reverse/2,splitwith/2,sort/1]).
+-import(lists, [any/2,member/2,reverse/1,reverse/2,splitwith/2,sort/1]).
 
 -record(st,
 	{safe :: cerl_sets:set(beam_asm:label()) %Safe labels.
@@ -221,22 +221,53 @@ remap_block([{set,Ds0,Ss0,Info}|Is], Map, Acc) ->
     Ss = [Map(S) || S <- Ss0],
     remap_block(Is, Map, [{set,Ds,Ss,Info}|Acc]);
 remap_block([], _, Acc) -> reverse(Acc).
-    
-safe_labels([{label,L},{line,_},{badmatch,{Tag,_}}|Is], Acc) when Tag =/= y ->
-    safe_labels(Is, [L|Acc]);
-safe_labels([{label,L},{line,_},{case_end,{Tag,_}}|Is], Acc) when Tag =/= y ->
-    safe_labels(Is, [L|Acc]);
-safe_labels([{label,L},{line,_},if_end|Is], Acc) ->
-    safe_labels(Is, [L|Acc]);
-safe_labels([{label,L},
-	     {block,[{set,[{x,0}],[{Tag,_}],move}]},
-	     {line,_},
-	     {call_ext,1,{extfunc,erlang,error,1}}|Is], Acc) when Tag =/= y ->
-    safe_labels(Is, [L|Acc]);
+
+%% safe_labels([Instruction], Accumulator) -> gb_set()
+%%  Build a gb_set of safe labels. The code at a safe
+%%  label does not depend on the values in a specific
+%%  Y register, only that all Y registers are initialized
+%%  so that it safe to scan the stack when an exception
+%%  is generated.
+%%
+%%  In other words, code at a safe label will continue
+%%  to work if Y registers have been renumbered and
+%%  the size of the stack frame has changed.
+
+safe_labels([{label,L}|Is], Acc) ->
+    case is_safe_label(Is) of
+        true -> safe_labels(Is, [L|Acc]);
+        false -> safe_labels(Is, Acc)
+    end;
 safe_labels([_|Is], Acc) ->
     safe_labels(Is, Acc);
 safe_labels([], Acc) -> cerl_sets:from_list(Acc).
 
+is_safe_label([{line,_}|Is]) ->
+    is_safe_label(Is);
+is_safe_label([{badmatch,{Tag,_}}|_]) ->
+    Tag =/= y;
+is_safe_label([{case_end,{Tag,_}}|_]) ->
+    Tag =/= y;
+is_safe_label([{try_case_end,{Tag,_}}|_]) ->
+    Tag =/= y;
+is_safe_label([if_end|_]) ->
+    true;
+is_safe_label([{block,Bl}|Is]) ->
+    is_safe_label_block(Bl) andalso is_safe_label(Is);
+is_safe_label([{call_ext,_,{extfunc,M,F,A}}|_]) ->
+    erl_bifs:is_exit_bif(M, F, A);
+is_safe_label(_) -> false.
+
+is_safe_label_block([{set,Ds,Ss,_}|Is]) ->
+    IsYreg = fun({y,_}) -> true;
+                (_) -> false
+             end,
+    %% This instruction is safe if the instruction
+    %% neither reads or writes Y registers.
+    not (any(IsYreg, Ss) orelse any(IsYreg, Ds)) andalso
+        is_safe_label_block(Is);
+is_safe_label_block([]) -> true.
+
 %% frame_layout([Instruction], [{kill,_}], St) ->
 %%      [{kill,Reg} | {live,Reg} | {dead,Reg}]
 %%  Figure out the layout of the stack frame.
-- 
cgit v1.2.3


From 0c374a1de1a4b880fe2f7dba8ef4eefafc975af7 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 1 Nov 2018 16:29:06 +0100
Subject: beam_trim: Add comments about how all this works

Also rename a few functions in attempt to make it clearer.
---
 lib/compiler/src/beam_trim.erl | 132 +++++++++++++++++++++++++++--------------
 1 file changed, 87 insertions(+), 45 deletions(-)

diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl
index f8efc38d53..51ff580a7a 100644
--- a/lib/compiler/src/beam_trim.erl
+++ b/lib/compiler/src/beam_trim.erl
@@ -51,14 +51,33 @@ trim([{kill,_}|_]=Is0, St, Acc) ->
 			    end, Is0),
     Kills = sort(Kills0),
     try
-	{FrameSize,Layout} = frame_layout(Is1, Kills, St),
-	Configs = trim_instructions(Layout),
-	try_remap(Configs, Is1, FrameSize)
-	of
+        %% Find out the size and layout of the stack frame.
+        %% Example of a layout:
+        %%
+        %%    [{kill,{y,0}},{dead,{y,1},{live,{y,2}},{kill,{y,3}}]
+        %%
+        %% That means that y0 and y3 are to be killed, that y1
+        %% has been killed previously, and that y2 is live.
+        {FrameSize,Layout} = frame_layout(Is1, Kills, St),
+
+        %% Calculate all recipes that are not worse in terms
+        %% of estimated execution time. The recipes are ordered
+        %% in descending order from how much they trim.
+        Recipes = trim_recipes(Layout),
+
+        %% Try the recipes in order. A recipe may not work out because
+        %% a register that was previously killed may be
+        %% resurrected. If that happens, the next recipe, which trims
+        %% less, will be tried.
+        try_remap(Recipes, Is1, FrameSize)
+    of
 	{Is,TrimInstr} ->
+            %% One of the recipes was applied.
 	    trim(Is, St, reverse(TrimInstr)++Acc)
     catch
 	not_possible ->
+            %% No recipe worked out. Use the original kill
+            %% instructions.
 	    trim(Is1, St, reverse(Kills, Acc))
     end;
 trim([I|Is], St, Acc) ->
@@ -66,34 +85,42 @@ trim([I|Is], St, Acc) ->
 trim([], _, Acc) ->
     reverse(Acc).
 
-%% trim_instructions([{kill,R}|{live,R}|{dead,R}]) -> {[Instruction],MapFun}
-%%  Figure out the sequence of moves and trim to use.
+%% trim_recipes([{kill,R}|{live,R}|{dead,R}]) -> [Recipe].
+%%      Recipe = {Kills,NumberToTrim,Moves}
+%%      Kills = [{kill,Y}]
+%%      Moves = [{move,SrcY,DstY}]
+%%
+%%  Calculate how to best trim the stack and kill the correct
+%%  Y registers. Return a list of possible recipes. The best
+%%  recipe (the one that trims the most) is first in the list.
+%%  All of the recipes are no worse in estimated execution time
+%%  than the original sequences of kill instructions.
 
-trim_instructions(Layout) ->
+trim_recipes(Layout) ->
     Cost = length([I || {kill,_}=I <- Layout]),
-    trim_instructions_1(Layout, 0, [], {Cost,[]}).
+    trim_recipes_1(Layout, 0, [], {Cost,[]}).
 
-trim_instructions_1([{kill,{y,Trim0}}|Ks], Trim0, Moves, Config0) ->
+trim_recipes_1([{kill,{y,Trim0}}|Ks], Trim0, Moves, Recipes0) ->
     Trim = Trim0 + 1,
-    Config = save_config(Ks, Trim, Moves, Config0),
-    trim_instructions_1(Ks, Trim, Moves, Config);
-trim_instructions_1([{dead,{y,Trim0}}|Ks], Trim0, Moves, Config0) ->
+    Recipes = save_recipe(Ks, Trim, Moves, Recipes0),
+    trim_recipes_1(Ks, Trim, Moves, Recipes);
+trim_recipes_1([{dead,{y,Trim0}}|Ks], Trim0, Moves, Recipes0) ->
     Trim = Trim0 + 1,
-    Config = save_config(Ks, Trim, Moves, Config0),
-    trim_instructions_1(Ks, Trim, Moves, Config);
-trim_instructions_1([{live,{y,Trim0}=Src}|Ks0], Trim0, Moves0, Config0) ->
+    Recipes = save_recipe(Ks, Trim, Moves, Recipes0),
+    trim_recipes_1(Ks, Trim, Moves, Recipes);
+trim_recipes_1([{live,{y,Trim0}=Src}|Ks0], Trim0, Moves0, Recipes0) ->
     case take_last_dead(Ks0) of
 	none ->
-	    {_,ConfigList} = Config0,
-	    ConfigList;
+            {_,RecipesList} = Recipes0,
+            RecipesList;
 	{Dst,Ks} ->
 	    Trim = Trim0 + 1,
 	    Moves = [{move,Src,Dst}|Moves0],
-	    Config = save_config(Ks, Trim, Moves, Config0),
-	    trim_instructions_1(Ks, Trim, Moves, Config)
+            Recipes = save_recipe(Ks, Trim, Moves, Recipes0),
+            trim_recipes_1(Ks, Trim, Moves, Recipes)
     end;
-trim_instructions_1([], _, _, {_,ConfigList}) ->
-    ConfigList.
+trim_recipes_1([], _, _, {_,RecipesList}) ->
+    RecipesList.
 
 take_last_dead(L) ->
     take_last_dead_1(reverse(L)).
@@ -104,28 +131,48 @@ take_last_dead_1([{dead,Reg}|Is]) ->
     {Reg,reverse(Is)};
 take_last_dead_1(_) -> none.
 
-save_config(Ks, Trim, Moves, {MaxCost,Acc}=Config) ->
-    case config_cost(Ks, Moves) of
-	Cost when Cost =< MaxCost ->
-	    {MaxCost,[{Ks,Trim,Moves}|Acc]};
+save_recipe(Ks, Trim, Moves, {MaxCost,Acc}=Recipes) ->
+    case recipe_cost(Ks, Moves) of
+        Cost when Cost =< MaxCost ->
+            %% The price is right.
+            {MaxCost,[{Ks,Trim,Moves}|Acc]};
 	_Cost ->
-	    Config
+            %% Too expensive.
+            Recipes
     end.
 
-config_cost(Ks, Moves) ->
+recipe_cost(Ks, Moves) ->
     %% We estimate that a {move,{y,_},{y,_}} instruction is roughly twice as
     %% expensive as a {kill,{y,_}} instruction. A {trim,_} instruction is
     %% roughly as expensive as a {kill,{y,_}} instruction.
 
-    config_cost_1(Ks, 1+2*length(Moves)).
+    recipe_cost_1(Ks, 1+2*length(Moves)).
+
+recipe_cost_1([{kill,_}|Ks], Cost) ->
+    recipe_cost_1(Ks, Cost+1);
+recipe_cost_1([_|Ks], Cost) ->
+    recipe_cost_1(Ks, Cost);
+recipe_cost_1([], Cost) -> Cost.
 
-config_cost_1([{kill,_}|Ks], Cost) ->
-    config_cost_1(Ks, Cost+1);
-config_cost_1([_|Ks], Cost) ->
-    config_cost_1(Ks, Cost);
-config_cost_1([], Cost) -> Cost.
+%% try_remap([Recipe], [Instruction], FrameSize) ->
+%%           {[Instruction],[TrimInstruction]}.
+%%  Try to renumber Y registers in the instruction stream. The
+%%  first rececipe that works will be used.
+%%
+%%  This function will issue a `not_possible` exception if none
+%%  of the recipes were possible to apply.
+
+try_remap([R|Rs], Is, FrameSize) ->
+    {TrimInstr,Map} = expand_recipe(R, FrameSize),
+    try
+	{remap(Is, Map, []),TrimInstr}
+    catch
+	throw:not_possible ->
+	    try_remap(Rs, Is, FrameSize)
+    end;
+try_remap([], _, _) -> throw(not_possible).
 
-expand_config({Layout,Trim,Moves}, FrameSize) ->
+expand_recipe({Layout,Trim,Moves}, FrameSize) ->
     Kills = [Kill || {kill,_}=Kill <- Layout],
     {Kills++reverse(Moves, [{trim,Trim,FrameSize-Trim}]),create_map(Trim, Moves)}.
 
@@ -153,16 +200,6 @@ create_map(Trim, Moves) ->
        (Any) -> Any
     end.
 
-try_remap([C|Cs], Is, FrameSize) ->
-    {TrimInstr,Map} = expand_config(C, FrameSize),
-    try
-	{remap(Is, Map, []),TrimInstr}
-    catch
-	throw:not_possible ->
-	    try_remap(Cs, Is, FrameSize)
-    end;
-try_remap([], _, _) -> throw(not_possible).
-
 remap([{block,Bl0}|Is], Map, Acc) ->
     Bl = remap_block(Bl0, Map, []),
     remap(Is, Map, [{block,Bl}|Acc]);
@@ -215,7 +252,7 @@ remap([return|_]=Is, _, Acc) ->
     reverse(Acc, Is);
 remap([{line,_}=I|Is], Map, Acc) ->
     remap(Is, Map, [I|Acc]).
-    
+
 remap_block([{set,Ds0,Ss0,Info}|Is], Map, Acc) ->
     Ds = [Map(D) || D <- Ds0],
     Ss = [Map(S) || S <- Ss0],
@@ -294,6 +331,11 @@ frame_layout_2(Is) -> reverse(Is).
 
 %% frame_size([Instruction], SafeLabels) -> FrameSize
 %%  Find out the frame size by looking at the code that follows.
+%%
+%%  Implicitly, also check that the instructions are a straight
+%%  sequence of code that ends in a return. Any branches are
+%%  to safe labels (i.e., the code at those labels don't depend
+%%  on the contents of any Y register).
 
 frame_size([{block,_}|Is], Safe) ->
     frame_size(Is, Safe);
-- 
cgit v1.2.3