Rewrite BSM optimizations in the new SSA-based intermediate format

This commit improves the bit-syntax match optimization pass,
leveraging the new SSA intermediate format to perform much more
aggressive optimizations. Some highlights:

* Watch contexts can be reused even after being passed to a
  function or being used in a try block.
* Sub-binaries are no longer eagerly extracted, making it far
  easier to keep "happy paths" free from binary creation.
* Trivial wrapper functions no longer disable context reuse.

6 files changed, 138 insertions, 36 deletions

diff --git a/lib/compiler/test/beam_validator_SUITE_data/bad_bin_match.S b/lib/compiler/test/beam_validator_SUITE_data/bad_bin_match.S
index a60ca1e89a..c7610971f1 100644
--- a/lib/compiler/test/beam_validator_SUITE_data/bad_bin_match.S
+++ b/lib/compiler/test/beam_validator_SUITE_data/bad_bin_match.S
@@ -11,5 +11,5 @@
   {label,1}.
     {func_info,{atom,t},{atom,t},1}.
   {label,2}.
-    {test,bs_start_match2,{f,1},1,[{x,0},0],{x,0}}.
+    {test,bs_start_match3,{f,1},1,[{x,0}],{x,0}}.
     return.
diff --git a/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S b/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S
index cca052a9c4..5b974119c6 100644
--- a/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S
+++ b/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S
@@ -172,7 +172,7 @@
     {allocate_zero,1,0}.
   {label,28}.
     {loop_rec,{f,30},{x,0}}.
-    {test,bs_start_match2,{f,29},1,[{x,0},0],{x,0}}.
+    {test,bs_start_match3,{f,29},1,[{x,0}],{x,0}}.
     {test,bs_get_integer2,
           {f,29},
           1,
@@ -219,7 +219,7 @@
     {allocate_zero,1,0}.
   {label,33}.
     {loop_rec,{f,35},{x,0}}.
-    {test,bs_start_match2,{f,34},1,[{x,0},0],{x,0}}.
+    {test,bs_start_match3,{f,34},1,[{x,0}],{x,0}}.
     {test,bs_get_integer2,
           {f,34},
           1,
@@ -262,7 +262,7 @@
     {allocate_zero,1,0}.
   {label,38}.
     {loop_rec,{f,40},{x,0}}.
-    {test,bs_start_match2,{f,39},1,[{x,0},0],{x,1}}.
+    {test,bs_start_match3,{f,39},1,[{x,0}],{x,1}}.
     {test,bs_get_integer2,
           {f,39},
           2,
diff --git a/lib/compiler/test/bs_match_SUITE.erl b/lib/compiler/test/bs_match_SUITE.erl
index b4277f0705..e654979a96 100644
--- a/lib/compiler/test/bs_match_SUITE.erl
+++ b/lib/compiler/test/bs_match_SUITE.erl
@@ -40,7 +40,9 @@
 	 map_and_binary/1,unsafe_branch_caching/1,
 	 bad_literals/1,good_literals/1,constant_propagation/1,
 	 parse_xml/1,get_payload/1,escape/1,num_slots_different/1,
-         beam_bsm/1,guard/1,is_ascii/1,non_opt_eq/1,erl_689/1]).
+         beam_bsm/1,guard/1,is_ascii/1,non_opt_eq/1,
+         expression_before_match/1,erl_689/1,restore_on_call/1,
+         restore_after_catch/1,matches_on_parameter/1,big_positions/1]).
 
 -export([coverage_id/1,coverage_external_ignore/2]).
 
@@ -56,7 +58,7 @@ all() ->
     [{group,p}].
 
 groups() -> 
-    [{p,[parallel],
+    [{p,[],
       [size_shadow,int_float,otp_5269,null_fields,wiger,
        bin_tail,save_restore,
        partitioned_bs_match,function_clause,unit,
@@ -72,7 +74,9 @@ groups() ->
        map_and_binary,unsafe_branch_caching,
        bad_literals,good_literals,constant_propagation,parse_xml,
        get_payload,escape,num_slots_different,
-       beam_bsm,guard,is_ascii,non_opt_eq,erl_689]}].
+       beam_bsm,guard,is_ascii,non_opt_eq,
+       expression_before_match,erl_689,restore_on_call,
+       matches_on_parameter,big_positions]}].
 
 
 init_per_suite(Config) ->
@@ -1764,4 +1768,93 @@ do_erl_689_2(_, <<Length, Data/binary>>) ->
 check(F, R) ->
     R = F().
 
+%% Make sure that an expression that comes between function start and a match
+%% expression passes validation.
+expression_before_match(Config) when is_list(Config) ->
+    <<_,R/binary>> = id(<<0,1,2,3>>),
+    {1, <<2,3>>} = expression_before_match_1(R),
+    ok.
+
+expression_before_match_1(R) ->
+    A = id(1),
+    case R of
+        <<1,Bar/binary>> -> {A, Bar};
+        <<>> -> {A, baz}
+    end.
+
+%% Make sure that context positions are updated on calls.
+restore_on_call(Config) when is_list(Config) ->
+    ok = restore_on_call_1(<<0, 1, 2>>).
+
+restore_on_call_1(<<0, Rest/binary>>) ->
+    <<2>> = restore_on_call_2(Rest),
+    <<2>> = restore_on_call_2(Rest), %% {badmatch, <<>>} on missing restore.
+    ok.
+
+restore_on_call_2(<<1, Rest/binary>>) -> Rest;
+restore_on_call_2(Other) -> Other.
+
+%% 'catch' must invalidate positions.
+restore_after_catch(Config) when is_list(Config) ->
+    <<0, 1>> = restore_after_catch_1(<<0, 1>>),
+    ok.
+
+restore_after_catch_1(<<A/binary>>) ->
+    try throw_after_byte(A) of
+        _ -> impossible
+    catch
+        throw:_Any ->
+            %% Will equal <<1>> if the bug is present.
+            A
+    end.
+
+throw_after_byte(<<_,_/binary>>) ->
+    throw(away).
+
+matches_on_parameter(Config) when is_list(Config) ->
+    %% This improves coverage for matching on "naked" parameters.
+    {<<"urka">>, <<"a">>} = matches_on_parameter_1(<<"gurka">>),
+    ok = (catch matches_on_parameter_2(<<"10001110101">>, 0)).
+
+matches_on_parameter_1(Bin) ->
+    <<"g", A/binary>> = Bin,
+    <<_,_,"rk", B/binary>> = Bin,
+    {A, B}.
+
+matches_on_parameter_2(Bin, Offset) ->
+    <<_:Offset, Bit:1, Rest/bits>> = Bin,
+    case bit_size(Rest) of
+        0 -> throw(ok);
+        _ -> [Bit | matches_on_parameter_2(Bin, Offset + 1)]
+    end.
+
+big_positions(Config) when is_list(Config) ->
+    %% This provides coverage for when match context positions no longer fit
+    %% into an immediate on 32-bit platforms.
+
+    A = <<0:((1 bsl 27) - 8), $A, 1:1, "gurka", $A>>,
+    B = <<0:((1 bsl 27) - 8), $B, "hello", $B>>,
+
+    {a,$A} = bp_start_match(A),
+    {b,$B} = bp_start_match(B),
+    {a,$A} = bp_getpos(A),
+    {b,$B} = bp_getpos(B),
+
+    ok.
+
+%% After the first iteration the context's position will no longer fit into an
+%% immediate. To improve performance the bs_start_match3 instruction will
+%% return a new context with an updated base position so that we won't have to
+%% resort to using bigints.
+bp_start_match(<<_:(1 bsl 27),T/bits>>) -> bp_start_match(T);
+bp_start_match(<<1:1,"gurka",A>>) -> {a,A};
+bp_start_match(<<"hello",B>>) -> {b,B}.
+
+%% This is a corner case where the above didn't work perfectly; if the position
+%% was _just_ small enough to fit into an immediate when bs_start_match3 was
+%% hit, but too large at bs_get_position, then it must be saved as a bigint.
+bp_getpos(<<_:((1 bsl 27) - 8),T/bits>>) -> bp_getpos(T);
+bp_getpos(<<A,1:1,"gurka",A>>) -> {a,A};
+bp_getpos(<<B,"hello",B>>) -> {b,B}.
+
 id(I) -> I.
diff --git a/lib/compiler/test/compile_SUITE.erl b/lib/compiler/test/compile_SUITE.erl
index 38bc928f85..b79b4171d3 100644
--- a/lib/compiler/test/compile_SUITE.erl
+++ b/lib/compiler/test/compile_SUITE.erl
@@ -1481,7 +1481,10 @@ bc_options(Config) ->
 
     132 = highest_opcode(DataDir, small,
                          [no_put_tuple2,no_get_hd_tl,no_ssa_opt_record,
-                          no_ssa_opt_float,no_line_info]),
+                          no_ssa_opt_float,no_line_info,no_bsm3]),
+
+    153 = highest_opcode(DataDir, small, [r20]),
+    153 = highest_opcode(DataDir, small, [r21]),
 
     136 = highest_opcode(DataDir, big, [no_put_tuple2,no_get_hd_tl,
                                         no_ssa_opt_record,no_line_info]),
diff --git a/lib/compiler/test/misc_SUITE.erl b/lib/compiler/test/misc_SUITE.erl
index 4c2d0116c9..c9acda2b6d 100644
--- a/lib/compiler/test/misc_SUITE.erl
+++ b/lib/compiler/test/misc_SUITE.erl
@@ -254,17 +254,6 @@ silly_coverage(Config) when is_list(Config) ->
 		 2},
     expect_error(fun() -> beam_peep:module(PeepInput, []) end),
 
-    %% beam_bsm. This is tricky. Our function must be sane enough to not crash
-    %% btb_index/1, but must crash the main optimization pass.
-    BsmInput = {?MODULE,[{foo,0}],[],
-		[{function,foo,0,2,
-		  [{label,1},
-		   {func_info,{atom,?MODULE},{atom,foo},0},
-		   {label,2},
-		   {test,bs_get_binary2,{f,99},0,[{x,0},{atom,all},1,[]],{x,0}},
-		   {block,[a|b]}]}],0},
-    expect_error(fun() -> beam_bsm:module(BsmInput, []) end),
-
     BeamZInput = {?MODULE,[{foo,0}],[],
 		  [{function,foo,0,2,
 		    [{label,1},
diff --git a/lib/compiler/test/warnings_SUITE.erl b/lib/compiler/test/warnings_SUITE.erl
index 33d55996ad..1f39348998 100644
--- a/lib/compiler/test/warnings_SUITE.erl
+++ b/lib/compiler/test/warnings_SUITE.erl
@@ -522,25 +522,43 @@ bin_opt_info(Config) when is_list(Config) ->
 	         <<>> -> ok
              end.
 
+             %% We use a tail in a BIF instruction, remote call, function
+             %% return, and an optimizable tail call for better coverage.
+             t2(<<A,B,T/bytes>>) ->
+                 if
+                     A > B -> t2(T);
+                     A =< B -> T
+                 end;
+             t2(<<_,T/bytes>>) when byte_size(T) < 4 ->
+                 foo;
              t2(<<_,T/bytes>>) ->
-               split_binary(T, 4).
+                 split_binary(T, 4).
            ">>,
-    Ts1 = [{bsm1,
-	    Code,
-	    [bin_opt_info],
-	    {warnings,
-	     [{4,sys_core_bsm,orig_bin_var_used_in_guard},
-	      {5,beam_bsm,{no_bin_opt,{{t1,1},no_suitable_bs_start_match}}},
-	      {9,beam_bsm,{no_bin_opt,
-			   {binary_used_in,{extfunc,erlang,split_binary,2}}}} ]}}],
-    [] = run(Config, Ts1),
+
+    Ws = (catch run_test(Config, Code, [bin_opt_info])),
+
+    %% This is an inexact match since the pass reports exact instructions as
+    %% part of the warnings, which may include annotations that vary from run
+    %% to run.
+    {warnings,
+     [{5,beam_ssa_bsm,{unsuitable_call,
+                        {{b_local,{b_literal,t1},1},
+                         {used_before_match,
+                            {b_set,_,_,{bif,byte_size},[_]}}}}},
+      {5,beam_ssa_bsm,{binary_created,_,_}},
+      {11,beam_ssa_bsm,{binary_created,_,_}}, %% A =< B -> T
+      {13,beam_ssa_bsm,context_reused},       %% A > B -> t2(T);
+      {16,beam_ssa_bsm,{binary_created,_,_}}, %% when byte_size(T) < 4 ->
+      {19,beam_ssa_bsm,{remote_call,
+                         {b_remote,
+                          {b_literal,erlang},
+                           {b_literal,split_binary},2}}},
+      {19,beam_ssa_bsm,{binary_created,_,_}}  %% split_binary(T, 4)
+     ]} = Ws,
 
     %% For coverage: don't give the bin_opt_info option.
-    Ts2 = [{bsm2,
-	    Code,
-	    [],
-	    []}],
-    [] = run(Config, Ts2),
+    [] = (catch run_test(Config, Code, [])),
+
     ok.
 
 bin_construction(Config) when is_list(Config) ->
@@ -746,7 +764,7 @@ maps_bin_opt_info(Config) when is_list(Config) ->
                  M.
            ">>,
            [bin_opt_info],
-           {warnings,[{2,beam_bsm,bin_opt}]}}],
+           {warnings,[{3,beam_ssa_bsm,context_reused}]}}],
     [] = run(Config, Ts),
     ok.
 
@@ -969,7 +987,6 @@ run(Config, Tests) ->
         end,
     lists:foldl(F, [], Tests).
 
-
 %% Compiles a test module and returns the list of errors and warnings.
 
 run_test(Conf, Test0, Warnings) ->