From cf5094ccc73446496e33b0aa6cbbf7fe65bbbe76 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?John=20H=C3=B6gberg?= <john@erlang.org>
Date: Tue, 8 May 2018 08:51:21 +0200
Subject: Support using match contexts from Y registers

The upcoming beam_ssa_bsm pass allows match contexts to be used
across function calls that take said context as an argument, which
means it's fairly common for them to end up in Y registers.
---
 erts/emulator/beam/beam_load.c   |  1 +
 erts/emulator/beam/bs_instrs.tab | 17 +++++++---
 erts/emulator/beam/ops.tab       | 72 ++++++++++++++++++++--------------------
 3 files changed, 50 insertions(+), 40 deletions(-)

diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c
index 50cbb37f3e..c28a5c57e6 100644
--- a/erts/emulator/beam/beam_load.c
+++ b/erts/emulator/beam/beam_load.c
@@ -2868,6 +2868,7 @@ load_code(LoaderState* stp)
 	    break;
 	case op_bs_put_string_WW:
 	case op_i_bs_match_string_xfWW:
+	case op_i_bs_match_string_yfWW:
 	    new_string_patch(stp, ci-1);
 	    break;
 
diff --git a/erts/emulator/beam/bs_instrs.tab b/erts/emulator/beam/bs_instrs.tab
index 61eb02a7a2..9fd70cbbb6 100644
--- a/erts/emulator/beam/bs_instrs.tab
+++ b/erts/emulator/beam/bs_instrs.tab
@@ -102,6 +102,7 @@ i_bs_get_binary_all2(Fail, Ms, Live, Unit, Dst) {
         LIGHT_SWAPIN;
         HEAP_SPACE_VERIFIED(0);
         ASSERT(is_value(_result));
+        $REFRESH_GEN_DEST();
         $Dst = _result;
     } else {
 	HEAP_SPACE_VERIFIED(0);
@@ -123,6 +124,7 @@ i_bs_get_binary2(Fail, Ms, Live, Sz, Flags, Dst) {
     if (is_non_value(_result)) {
         $FAIL($Fail);
     } else {
+        $REFRESH_GEN_DEST();
         $Dst = _result;
     }
 }
@@ -139,6 +141,7 @@ i_bs_get_binary_imm2(Fail, Ms, Live, Sz, Flags, Dst) {
     if (is_non_value(_result)) {
         $FAIL($Fail);
     } else {
+        $REFRESH_GEN_DEST();
         $Dst = _result;
     }
 }
@@ -161,6 +164,7 @@ i_bs_get_float2(Fail, Ms, Live, Sz, Flags, Dst) {
     if (is_non_value(_result)) {
         $FAIL($Fail);
     } else {
+        $REFRESH_GEN_DEST();
         $Dst = _result;
     }
 }
@@ -731,18 +735,19 @@ bs_start_match.execute(Fail, Live, Slots, Dst) {
         Uint actual_slots = HEADER_NUM_SLOTS(header);
         ms->save_offset[0] = ms->mb.offset;
         if (actual_slots < slots) {
-            ErlBinMatchState* dst;
+            ErlBinMatchState* expanded;
             Uint live = $Live;
             Uint wordsneeded = ERL_BIN_MATCHSTATE_SIZE(slots);
 
             $GC_TEST_PRESERVE(wordsneeded, live, context);
             ms = (ErlBinMatchState *) boxed_val(context);
-            dst = (ErlBinMatchState *) HTOP;
-            *dst = *ms;
+            expanded = (ErlBinMatchState *) HTOP;
+            *expanded = *ms;
             *HTOP = HEADER_BIN_MATCHSTATE(slots);
             HTOP += wordsneeded;
             HEAP_SPACE_VERIFIED(0);
-            $Dst = make_matchstate(dst);
+            $REFRESH_GEN_DEST();
+            $Dst = make_matchstate(expanded);
         }
     } else if (is_binary_header(header)) {
         Eterm result;
@@ -758,6 +763,7 @@ bs_start_match.execute(Fail, Live, Slots, Dst) {
         if (is_non_value(result)) {
             $FAIL($Fail);
         }
+        $REFRESH_GEN_DEST();
         $Dst = result;
     } else {
         $FAIL($Fail);
@@ -906,6 +912,7 @@ i_bs_get_integer(Fail, Live, FlagsAndUnit, Ms, Sz, Dst) {
         }
         wordsneeded = 1+WSIZE(NBYTES((Uint) size));
         $GC_TEST_PRESERVE(wordsneeded, $Live, ms);
+        $REFRESH_GEN_DEST();
     }
     mb = ms_matchbuffer(ms);
     LIGHT_SWAPOUT;
@@ -939,6 +946,7 @@ i_bs_get_utf8(Ctx, Fail, Dst) {
     if (is_non_value(result)) {
         $FAIL($Fail);
     }
+    $REFRESH_GEN_DEST();
     $Dst = result;
 }
 
@@ -949,6 +957,7 @@ i_bs_get_utf16(Ctx, Fail, Flags, Dst) {
     if (is_non_value(result)) {
         $FAIL($Fail);
     }
+    $REFRESH_GEN_DEST();
     $Dst = result;
 }
 
diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab
index d859c4bb24..c3e71ff77a 100644
--- a/erts/emulator/beam/ops.tab
+++ b/erts/emulator/beam/ops.tab
@@ -1089,21 +1089,21 @@ func_info M F A => i_func_info u M F A
 %warm
 bs_start_match2 Fail=f ica X Y D => jump Fail
 bs_start_match2 Fail Bin X Y D => i_bs_start_match2 Bin Fail X Y D
-i_bs_start_match2 xy f t t x
+i_bs_start_match2 xy f t t d
 
 bs_save2 Reg Index => gen_bs_save(Reg, Index)
-i_bs_save2 x t
+i_bs_save2 xy t
 
 bs_restore2 Reg Index => gen_bs_restore(Reg, Index)
-i_bs_restore2 x t
+i_bs_restore2 xy t
 
 # Matching integers
 bs_match_string Fail Ms Bits Val => i_bs_match_string Ms Fail Bits Val
 
-i_bs_match_string x f W W
+i_bs_match_string xy f W W
 
 # Fetching integers from binaries.
-bs_get_integer2 Fail=f Ms=x Live=u Sz=sq Unit=u Flags=u Dst=d => \
+bs_get_integer2 Fail=f Ms=xy Live=u Sz=sq Unit=u Flags=u Dst=d => \
 			gen_get_integer2(Fail, Ms, Live, Sz, Unit, Flags, Dst)
 
 i_bs_get_integer_small_imm Ms Bits Fail Flags Y=y => \
@@ -1112,50 +1112,50 @@ i_bs_get_integer_small_imm Ms Bits Fail Flags Y=y => \
 i_bs_get_integer_imm Ms Bits Live Fail Flags Y=y => \
    i_bs_get_integer_imm Ms Bits Live Fail Flags x | move x Y
 
-i_bs_get_integer_small_imm x W f? t x
-i_bs_get_integer_imm x W t f? t x
-i_bs_get_integer f? t t x s xy
-i_bs_get_integer_8 x f? xy
-i_bs_get_integer_16 x f? xy
+i_bs_get_integer_small_imm xy W f? t x
+i_bs_get_integer_imm xy W t f? t x
+i_bs_get_integer f? t t xy s d
+i_bs_get_integer_8 xy f? d
+i_bs_get_integer_16 xy f? d
 
 %if ARCH_64
-i_bs_get_integer_32 x f? xy
+i_bs_get_integer_32 xy f? d
 %endif
 
 # Fetching binaries from binaries.
-bs_get_binary2 Fail=f Ms=x Live=u Sz=sq Unit=u Flags=u Dst=d => \
+bs_get_binary2 Fail=f Ms=xy Live=u Sz=sq Unit=u Flags=u Dst=d => \
 			gen_get_binary2(Fail, Ms, Live, Sz, Unit, Flags, Dst)
 
-i_bs_get_binary_imm2 f? x t W t xy
-i_bs_get_binary2 f x t? s t xy
-i_bs_get_binary_all2 f? x t t xy
-i_bs_get_binary_all_reuse x f? t
+i_bs_get_binary_imm2 f? xy t W t d
+i_bs_get_binary2 f xy t? s t d
+i_bs_get_binary_all2 f? xy t t d
+i_bs_get_binary_all_reuse xy f? t
 
 # Fetching float from binaries.
-bs_get_float2 Fail=f Ms=x Live=u Sz=s Unit=u Flags=u Dst=d => \
+bs_get_float2 Fail=f Ms=xy Live=u Sz=s Unit=u Flags=u Dst=d => \
 		gen_get_float2(Fail, Ms, Live, Sz, Unit, Flags, Dst)
 
 bs_get_float2 Fail=f Ms=x Live=u Sz=q Unit=u Flags=u Dst=d => jump Fail
 
-i_bs_get_float2 f? x t s t xy
+i_bs_get_float2 f? xy t s t d
 
 # Miscellanous
 
-bs_skip_bits2 Fail=f Ms=x Sz=sq Unit=u Flags=u => \
+bs_skip_bits2 Fail=f Ms=xy Sz=sq Unit=u Flags=u => \
 			gen_skip_bits2(Fail, Ms, Sz, Unit, Flags)
 
-i_bs_skip_bits_imm2 f? x W
-i_bs_skip_bits2 f? x xy t
-i_bs_skip_bits_all2 f? x t
+i_bs_skip_bits_imm2 f? xy W
+i_bs_skip_bits2 f? xy xy t
+i_bs_skip_bits_all2 f? xy t
 
-bs_test_tail2 Fail=f Ms=x Bits=u==0 => bs_test_zero_tail2 Fail Ms
-bs_test_tail2 Fail=f Ms=x Bits=u => bs_test_tail_imm2 Fail Ms Bits
-bs_test_zero_tail2 f? x
-bs_test_tail_imm2 f? x W
+bs_test_tail2 Fail=f Ms=xy Bits=u==0 => bs_test_zero_tail2 Fail Ms
+bs_test_tail2 Fail=f Ms=xy Bits=u => bs_test_tail_imm2 Fail Ms Bits
+bs_test_zero_tail2 f? xy
+bs_test_tail_imm2 f? xy W
 
 bs_test_unit F Ms Unit=u==8 => bs_test_unit8 F Ms
-bs_test_unit f? x t
-bs_test_unit8 f? x
+bs_test_unit f? xy t
+bs_test_unit8 f? xy
 
 # An y register operand for bs_context_to_binary is rare,
 # but can happen because of inlining.
@@ -1170,20 +1170,20 @@ bs_context_to_binary x
 #
 # Utf8/utf16/utf32 support. (R12B-5)
 #
-bs_get_utf8 Fail=f Ms=x u u Dst=d => i_bs_get_utf8 Ms Fail Dst
-i_bs_get_utf8 x f? xy
+bs_get_utf8 Fail=f Ms=xy u u Dst=d => i_bs_get_utf8 Ms Fail Dst
+i_bs_get_utf8 xy f? d
 
-bs_skip_utf8 Fail=f Ms=x u u => i_bs_get_utf8 Ms Fail x
+bs_skip_utf8 Fail=f Ms=xy u u => i_bs_get_utf8 Ms Fail x
 
-bs_get_utf16 Fail=f Ms=x u Flags=u Dst=d => i_bs_get_utf16 Ms Fail Flags Dst
-bs_skip_utf16 Fail=f Ms=x u Flags=u => i_bs_get_utf16 Ms Fail Flags x
+bs_get_utf16 Fail=f Ms=xy u Flags=u Dst=d => i_bs_get_utf16 Ms Fail Flags Dst
+bs_skip_utf16 Fail=f Ms=xy u Flags=u => i_bs_get_utf16 Ms Fail Flags x
 
-i_bs_get_utf16 x f? t xy
+i_bs_get_utf16 xy f? t d
 
-bs_get_utf32 Fail=f Ms=x Live=u Flags=u Dst=d => \
+bs_get_utf32 Fail=f Ms=xy Live=u Flags=u Dst=d => \
 	bs_get_integer2 Fail Ms Live i=32 u=1 Flags Dst | \
 	i_bs_validate_unicode_retract Fail Dst Ms
-bs_skip_utf32 Fail=f Ms=x Live=u Flags=u => \
+bs_skip_utf32 Fail=f Ms=xy Live=u Flags=u => \
 	bs_get_integer2 Fail Ms Live i=32 u=1 Flags x | \
 	i_bs_validate_unicode_retract Fail x Ms
 
-- 
cgit v1.2.3


From 2a6df910f450a4f69fbc482904e9d2e4512e6574 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?John=20H=C3=B6gberg?= <john@erlang.org>
Date: Tue, 8 May 2018 08:51:58 +0200
Subject: Remove match context reuse annotations from core/kernel passes

The upcoming beam_ssa_bsm pass makes this redundant.
---
 lib/compiler/src/beam_kernel_to_ssa.erl |   5 +-
 lib/compiler/src/sys_core_bsm.erl       | 250 ++++----------------------------
 lib/compiler/src/v3_kernel.erl          |  36 +----
 3 files changed, 30 insertions(+), 261 deletions(-)

diff --git a/lib/compiler/src/beam_kernel_to_ssa.erl b/lib/compiler/src/beam_kernel_to_ssa.erl
index c55a57ab32..747bb06d76 100644
--- a/lib/compiler/src/beam_kernel_to_ssa.erl
+++ b/lib/compiler/src/beam_kernel_to_ssa.erl
@@ -276,12 +276,11 @@ select_nil(#k_val_clause{val=#k_nil{},body=B}, V, Tf, Vf, St0) ->
     {Is ++ Bis,St}.
 
 select_binary(#k_val_clause{val=#k_binary{segs=#k_var{name=Ctx0}},body=B},
-              #k_var{anno=Anno0}=Src, Tf, Vf, St0) ->
-    Anno = #{reuse_for_context=>member(reuse_for_context, Anno0)},
+              #k_var{}=Src, Tf, Vf, St0) ->
     {Ctx,St1} = new_ssa_var(Ctx0, St0),
     {Bis0,St2} = match_cg(B, Vf, St1),
     {TestIs,St} = make_cond_branch(succeeded, [Ctx], Tf, St2),
-    Bis1 = [#b_set{anno=Anno,op=bs_start_match,dst=Ctx,
+    Bis1 = [#b_set{op=bs_start_match,dst=Ctx,
                    args=[ssa_arg(Src, St)]}] ++ TestIs ++ Bis0,
     Bis = finish_bs_matching(Bis1),
     {Bis,St}.
diff --git a/lib/compiler/src/sys_core_bsm.erl b/lib/compiler/src/sys_core_bsm.erl
index d7b26c3a56..685e807e65 100644
--- a/lib/compiler/src/sys_core_bsm.erl
+++ b/lib/compiler/src/sys_core_bsm.erl
@@ -24,161 +24,52 @@
 -export([module/2,format_error/1]).
 
 -include("core_parse.hrl").
--import(lists, [member/2,reverse/1,usort/1]).
 
 -spec module(cerl:c_module(), [compile:option()]) -> {'ok', cerl:c_module()}.
 
-module(#c_module{defs=Ds0}=Mod, Opts) ->
-    {Ds,Ws0} = function(Ds0, [], []),
-    case member(bin_opt_info, Opts) of
-        false ->
-            {ok,Mod#c_module{defs=Ds}};
-        true ->
-            Ws1 = [make_warning(Where, What) || {Where,What} <- Ws0],
-            Ws = usort(Ws1),
-            {ok,Mod#c_module{defs=Ds},Ws}
-    end.
+module(#c_module{defs=Ds}=Mod, _Opts) ->
+    {ok,Mod#c_module{defs=function(Ds)}}.
 
-function([{#c_var{name={F,Arity}}=Name,B0}|Fs], FsAcc, Ws0) ->
-    try cerl_trees:mapfold(fun bsm_an/2, Ws0, B0) of
-        {B,Ws} ->
-            function(Fs, [{Name,B}|FsAcc], Ws)
+function([{#c_var{name={F,Arity}}=Name,B0}|Fs]) ->
+    try cerl_trees:map(fun bsm_reorder/1, B0) of
+        B -> [{Name,B} | function(Fs)]
     catch
         Class:Error:Stack ->
-	    io:fwrite("Function: ~w/~w\n", [F,Arity]),
-	    erlang:raise(Class, Error, Stack)
+            io:fwrite("Function: ~w/~w\n", [F,Arity]),
+            erlang:raise(Class, Error, Stack)
     end;
-function([], Fs, Ws) ->
-    {reverse(Fs),Ws}.
+function([]) ->
+    [].
 
 -type error() :: atom().
 -spec format_error(error()) -> nonempty_string().
 
-format_error(bin_opt_alias) ->
-    "INFO: the '=' operator will prevent delayed sub binary optimization";
-format_error(bin_partition) ->
-    "INFO: matching non-variables after a previous clause matching a variable "
-	"will prevent delayed sub binary optimization";
-format_error(bin_var_used) ->
-    "INFO: using a matched out sub binary will prevent "
-	"delayed sub binary optimization";
-format_error(orig_bin_var_used_in_guard) ->
-    "INFO: using the original binary variable in a guard will prevent "
-	"delayed sub binary optimization";
-format_error(bin_var_used_in_guard) ->
-    "INFO: using a matched out sub binary in a guard will prevent "
-	"delayed sub binary optimization".
-
+format_error(_) -> error(badarg).
 
-%%%
-%%% Annotate bit syntax matching to faciliate optimization in further passes.
-%%%
+%%% Reorder bit syntax matching to faciliate optimization in further passes.
 
-bsm_an(Core0, Ws0) ->
-    case bsm_an(Core0) of
-        {ok,Core} ->
-            {Core,Ws0};
-        {ok,Core,W} ->
-            {Core,[W|Ws0]}
-    end.
+bsm_reorder(#c_case{arg=#c_var{}=V}=Case) ->
+    bsm_reorder_1([V], Case);
+bsm_reorder(#c_case{arg=#c_values{es=Es}}=Case) ->
+    bsm_reorder_1(Es, Case);
+bsm_reorder(Core) ->
+    Core.
 
-bsm_an(#c_case{arg=#c_var{}=V}=Case) ->
-    bsm_an_1([V], Case);
-bsm_an(#c_case{arg=#c_values{es=Es}}=Case) ->
-    bsm_an_1(Es, Case);
-bsm_an(Other) ->
-    {ok,Other}.
-
-bsm_an_1(Vs0, #c_case{clauses=Cs0}=Case) ->
+bsm_reorder_1(Vs0, #c_case{clauses=Cs0}=Case) ->
     case bsm_leftmost(Cs0) of
-	none ->
-            {ok,Case};
-        1 ->
-            bsm_an_2(Vs0, Cs0, Case);
-        Pos ->
-            Vs = move_from_col(Pos, Vs0),
-            Cs = [C#c_clause{pats=move_from_col(Pos, Ps)} ||
-                     #c_clause{pats=Ps}=C <- Cs0],
-            bsm_an_2(Vs, Cs, Case)
-    end.
-
-bsm_an_2(Vs, Cs, Case) ->
-    try
-        bsm_ensure_no_partition(Cs),
-        {ok,bsm_do_an(Vs, Cs, Case)}
-    catch
-        throw:{problem,Where,What} ->
-            {ok,Case,{Where,What}}
+        Pos when Pos > 0, Pos =/= none ->
+            Vs = core_lib:make_values(move_from_col(Pos, Vs0)),
+            Cs = [C#c_clause{pats=move_from_col(Pos, Ps)}
+                  || #c_clause{pats=Ps}=C <- Cs0],
+            Case#c_case{arg=Vs,clauses=Cs};
+        _ ->
+            Case
     end.
 
 move_from_col(Pos, L) ->
     {First,[Col|Rest]} = lists:split(Pos - 1, L),
     [Col|First] ++ Rest.
 
-bsm_do_an([#c_var{name=Vname}=V0|Vs0], Cs0, Case) ->
-    Cs = bsm_do_an_var(Vname, Cs0),
-    V = bsm_annotate_for_reuse(V0),
-    Vs = core_lib:make_values([V|Vs0]),
-    Case#c_case{arg=Vs,clauses=Cs};
-bsm_do_an(_Vs, _Cs, Case) -> Case.
-
-bsm_do_an_var(V, [#c_clause{pats=[P|_],guard=G,body=B0}=C0|Cs]) ->
-    case P of
-	#c_var{name=VarName} ->
-	    case core_lib:is_var_used(V, G) of
-		true -> bsm_problem(C0, orig_bin_var_used_in_guard);
-		false -> ok
-	    end,
-	    case core_lib:is_var_used(VarName, G) of
-		true -> bsm_problem(C0, bin_var_used_in_guard);
-		false -> ok
-	    end,
-	    B1 = bsm_maybe_ctx_to_binary(VarName, B0),
-	    B = bsm_maybe_ctx_to_binary(V, B1),
-	    C = C0#c_clause{body=B},
-            [C|bsm_do_an_var(V, Cs)];
-        #c_alias{} ->
-	    case bsm_could_match_binary(P) of
-		false ->
-		    [C0|bsm_do_an_var(V, Cs)];
-		true ->
-		    bsm_problem(C0, bin_opt_alias)
-	    end;
-        _ ->
-	    case bsm_could_match_binary(P) andalso bsm_is_var_used(V, G, B0) of
-		false ->
-		    [C0|bsm_do_an_var(V, Cs)];
-		true ->
-		    bsm_problem(C0, bin_var_used)
-	    end
-    end;
-bsm_do_an_var(_, []) -> [].
-
-bsm_annotate_for_reuse(#c_var{anno=Anno}=Var) ->
-    Var#c_var{anno=[reuse_for_context|Anno]}.
-
-bsm_is_var_used(V, G, B) ->
-    core_lib:is_var_used(V, G) orelse core_lib:is_var_used(V, B).
-
-bsm_maybe_ctx_to_binary(V, B) ->
-    case core_lib:is_var_used(V, B) andalso not previous_ctx_to_binary(V, B) of
-	false ->
-	    B;
-	true ->
-	    #c_seq{arg=#c_primop{name=#c_literal{val=bs_context_to_binary},
-				 args=[#c_var{name=V}]},
-		   body=B}
-    end.
-
-previous_ctx_to_binary(V, Core) ->
-    case Core of
-	#c_seq{arg=#c_primop{name=#c_literal{val=bs_context_to_binary},
-			     args=[#c_var{name=V}]}} ->
-	    true;
-	_ ->
-	    false
-    end.
-
 %% bsm_leftmost(Cs) -> none | ArgumentNumber
 %%  Find the leftmost argument that matches a nonempty binary.
 %%  Return either 'none' or the argument number (1-N).
@@ -200,94 +91,3 @@ bsm_leftmost_2([_|Ps], Cs, N, Pos) ->
     bsm_leftmost_2(Ps, Cs, N+1, Pos);
 bsm_leftmost_2([], Cs, _, Pos) ->
     bsm_leftmost_1(Cs, Pos).
-
-%% bsm_ensure_no_partition(Cs) -> ok     (exception if problem)
-%%  There must only be a single bs_start_match2 instruction if we
-%%  are to reuse the binary variable for the match context.
-%%
-%%  To make sure that there is only a single bs_start_match2
-%%  instruction, we will check for partitions such as:
-%%
-%%             foo(<<...>>) -> ...
-%%             foo(<Variable>) when ... -> ...
-%%             foo(<Non-variable pattern>) ->
-%%
-%%  If there is such partition, we reject the optimization.
-
-bsm_ensure_no_partition(Cs) ->
-    bsm_ensure_no_partition_1(Cs, before).
-
-%% Loop through each clause.
-bsm_ensure_no_partition_1([#c_clause{pats=Ps,guard=G}|Cs], State0) ->
-    State = bsm_ensure_no_partition_2(Ps, G, State0),
-    case State of
-	'after' ->
-	    bsm_ensure_no_partition_after(Cs);
-	_ ->
-	    ok
-    end,
-    bsm_ensure_no_partition_1(Cs, State);
-bsm_ensure_no_partition_1([], _) -> ok.
-
-bsm_ensure_no_partition_2([#c_binary{}|_], _, _State) ->
-    within;
-bsm_ensure_no_partition_2([#c_alias{}=Alias|_], N, State) ->
-    %% Retrieve the real pattern that the alias refers to and check that.
-    P = bsm_real_pattern(Alias),
-    bsm_ensure_no_partition_2([P], N, State);
-bsm_ensure_no_partition_2([_|_], _, before=State) ->
-    %% No binary matching yet - therefore no partition.
-    State;
-bsm_ensure_no_partition_2([P|_], _, State) ->
-    case bsm_could_match_binary(P) of
-	false ->
-            State;
-	true ->
-	    %% The pattern P *may* match a binary, so we must update the state.
-	    %% (P must be a variable.)
-            'after'
-    end.
-
-bsm_ensure_no_partition_after([#c_clause{pats=Ps}=C|Cs]) ->
-    case Ps of
-        [#c_var{}|_] ->
-            bsm_ensure_no_partition_after(Cs);
-        _ ->
-            bsm_problem(C, bin_partition)
-    end;
-bsm_ensure_no_partition_after([]) -> ok.
-
-bsm_could_match_binary(#c_alias{pat=P}) -> bsm_could_match_binary(P);
-bsm_could_match_binary(#c_cons{}) -> false;
-bsm_could_match_binary(#c_tuple{}) -> false;
-bsm_could_match_binary(#c_literal{val=Lit}) -> is_bitstring(Lit);
-bsm_could_match_binary(_) -> true.
-
-bsm_real_pattern(#c_alias{pat=P}) -> bsm_real_pattern(P);
-bsm_real_pattern(P) -> P.
-
-bsm_problem(Where, What) ->
-    throw({problem,Where,What}).
-
-make_warning(Core, Term) ->
-    case should_suppress_warning(Core) of
-	true ->
-	    ok;
-	false ->
-            Anno = cerl:get_ann(Core),
-            Line = get_line(Anno),
-            File = get_file(Anno),
-            {File,[{Line,?MODULE,Term}]}
-    end.
-
-should_suppress_warning(Core) ->
-    Ann = cerl:get_ann(Core),
-    member(compiler_generated, Ann).
-
-get_line([Line|_]) when is_integer(Line) -> Line;
-get_line([_|T]) -> get_line(T);
-get_line([]) -> none.
-
-get_file([{file,File}|_]) -> File;
-get_file([_|T]) -> get_file(T);
-get_file([]) -> "no_file". % should not happen
diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl
index fe8e252e5a..07fd1b2a0e 100644
--- a/lib/compiler/src/v3_kernel.erl
+++ b/lib/compiler/src/v3_kernel.erl
@@ -82,8 +82,7 @@
 -export([module/2,format_error/1]).
 
 -import(lists, [map/2,foldl/3,foldr/3,mapfoldl/3,splitwith/2,member/2,
-		keymember/3,keyfind/3,partition/2,droplast/1,last/1,sort/1,
-                reverse/1]).
+		keyfind/3,partition/2,droplast/1,last/1,sort/1,reverse/1]).
 -import(ordsets, [add_element/2,del_element/2,union/2,union/1,subtract/2]).
 -import(cerl, [c_tuple/1]).
 
@@ -2337,8 +2336,7 @@ uexpr(#k_bif{anno=A,op=Op,args=As}=Bif, {break,Rs}, St0) ->
     {Brs,St1} = bif_returns(Op, Rs, St0),
     {Bif#k_bif{anno=#k{us=Used,ns=lit_list_vars(Brs),a=A},ret=Brs},
      Used,St1};
-uexpr(#k_match{anno=A,vars=Vs0,body=B0}, Br, St0) ->
-    Vs = handle_reuse_annos(Vs0, St0),
+uexpr(#k_match{anno=A,vars=Vs,body=B0}, Br, St0) ->
     Rs = break_rets(Br),
     {B1,Bu,St1} = umatch(B0, Br, St0),
     case is_in_guard(St1) of
@@ -2441,33 +2439,6 @@ make_fdef(Anno, Name, Arity, Vs, Body) ->
                      vars=Vs,body=Body,ret=[]},
     #k_fdef{anno=Anno,func=Name,arity=Arity,vars=Vs,body=Match}.
 
-
-%% handle_reuse_annos([#k_var{}], State) -> State.
-%%  In general, it is only safe to reuse a variable for a match context
-%%  if the original value of the variable will no longer be needed.
-%%
-%%  If a variable has been bound in an outer letrec and is therefore
-%%  free in the current function, the variable may still be used.
-%%  We don't bother to check whether the variable is actually used,
-%%  but simply clears the 'reuse_for_context' annotation for any variable
-%%  that is free.
-handle_reuse_annos(Vs, St) ->
-    [handle_reuse_anno(V, St) || V <- Vs].
-
-handle_reuse_anno(#k_var{anno=A}=V, St) ->
-    case member(reuse_for_context, A) of
-	false -> V;
-	true -> handle_reuse_anno_1(V, St)
-    end.
-
-handle_reuse_anno_1(#k_var{anno=Anno,name=Vname}=V, #kern{ff={F,A}}=St) ->
-    FreeVs = get_free(F, A, St),
-    case keymember(Vname, #k_var.name, FreeVs) of
-	true -> V#k_var{anno=Anno--[reuse_for_context]};
-	false -> V
-    end;
-handle_reuse_anno_1(V, _St) -> V.
-
 %% get_free(Name, Arity, State) -> [Free].
 %% store_free(Name, Arity, [Free], State) -> State.
 
@@ -2511,8 +2482,7 @@ umatch(#k_alt{anno=A,first=F0,then=T0}, Br, St0) ->
     Used = union(Fu, Tu),
     {#k_alt{anno=#k{us=Used,ns=[],a=A},first=F1,then=T1},
      Used,St2};
-umatch(#k_select{anno=A,var=V0,types=Ts0}, Br, St0) ->
-    V = handle_reuse_anno(V0, St0),
+umatch(#k_select{anno=A,var=V,types=Ts0}, Br, St0) ->
     {Ts1,Tus,St1} = umatch_list(Ts0, Br, St0),
     Used = case member(no_usage, get_kanno(V)) of
 	       true -> Tus;
-- 
cgit v1.2.3


From b1726b022ad260497a1edc1cceb94935a06804e5 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?John=20H=C3=B6gberg?= <john@erlang.org>
Date: Wed, 19 Sep 2018 10:33:12 +0200
Subject: beam_ssa: Add helper functions and export more types

get_anno/3: as get_anno but with a default value
definitions/1-2: returns a map of variable definitions (#b_set{})
uses/1-2: returns a map of all uses of a given variable
mapfold_blocks_rpo/4: mapfolds over blocks
---
 lib/compiler/src/beam_ssa.erl | 87 ++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 78 insertions(+), 9 deletions(-)

diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl
index 9d10d4aec3..6e0f5fffe3 100644
--- a/lib/compiler/src/beam_ssa.erl
+++ b/lib/compiler/src/beam_ssa.erl
@@ -20,12 +20,15 @@
 %% Purpose: Type definitions and utilities for the SSA format.
 
 -module(beam_ssa).
--export([add_anno/3,get_anno/2,
-         clobbers_xregs/1,def/2,def_used/2,dominators/1,
+-export([add_anno/3,get_anno/2,get_anno/3,
+         clobbers_xregs/1,def/2,def_used/2,
+         definitions/1,
+         dominators/1,
          flatmapfold_instrs_rpo/4,
          fold_po/3,fold_po/4,fold_rpo/3,fold_rpo/4,
          fold_instrs_rpo/4,
          linearize/1,
+         mapfold_blocks_rpo/4,
          mapfold_instrs_rpo/4,
          normalize/1,
          no_side_effect/1,
@@ -35,14 +38,17 @@
          split_blocks/3,
          successors/1,successors/2,
          trim_unreachable/1,
-         update_phi_labels/4,used/1]).
+         update_phi_labels/4,used/1,
+         uses/1,uses/2]).
 
 -export_type([b_module/0,b_function/0,b_blk/0,b_set/0,
               b_ret/0,b_br/0,b_switch/0,terminator/0,
               b_var/0,b_literal/0,b_remote/0,b_local/0,
               value/0,argument/0,label/0,
               var_name/0,var_base/0,literal_value/0,
-              op/0,anno/0,block_map/0]).
+              op/0,anno/0,block_map/0,dominator_map/0,
+              rename_map/0,rename_proplist/0,usage_map/0,
+              definition_map/0]).
 
 -include("beam_ssa.hrl").
 
@@ -56,6 +62,9 @@
 -type b_switch()   :: #b_switch{}.
 -type terminator() :: b_br() | b_ret() | b_switch().
 
+-type construct()  :: b_module() | b_function() | b_blk() | b_set() |
+                      terminator().
+
 -type b_var()      :: #b_var{}.
 -type b_literal()  :: #b_literal{}.
 -type b_remote()   :: #b_remote{}.
@@ -76,6 +85,11 @@
 -type anno() :: #{atom() := any()}.
 
 -type block_map() :: #{label():=b_blk()}.
+-type dominator_map() :: #{label():=ordsets:ordset(label())}.
+-type usage_map() :: #{b_var():=[{label(),b_set() | terminator()}]}.
+-type definition_map() :: #{b_var():=b_set()}.
+-type rename_map() :: #{b_var():=value()}.
+-type rename_proplist() :: [{b_var(),value()}].
 
 %% Note: By default, dialyzer will collapse this type to atom().
 %% To avoid the collapsing, change the value of SET_LIMIT to 50 in the
@@ -103,14 +117,14 @@
 
 %% Primops only used internally during code generation.
 -type cg_prim_op() :: 'bs_get' | 'bs_match_string' | 'bs_restore' | 'bs_skip' |
-'copy' | 'put_tuple_arity' | 'put_tuple_element'.
+                      'copy' | 'put_tuple_arity' | 'put_tuple_element'.
 
 -import(lists, [foldl/3,keyfind/3,mapfoldl/3,member/2,reverse/1]).
 
 -spec add_anno(Key, Value, Construct) -> Construct when
       Key :: atom(),
       Value :: any(),
-      Construct :: b_function() | b_blk() | b_set() | terminator().
+      Construct :: construct().
 
 add_anno(Key, Val, #b_function{anno=Anno}=Bl) ->
     Bl#b_function{anno=Anno#{Key=>Val}};
@@ -125,11 +139,17 @@ add_anno(Key, Val, #b_ret{anno=Anno}=Bl) ->
 add_anno(Key, Val, #b_switch{anno=Anno}=Bl) ->
     Bl#b_switch{anno=Anno#{Key=>Val}}.
 
--spec get_anno(atom(), b_blk()|b_set()|terminator()) -> any().
+-spec get_anno(atom(), construct()) -> any().
 
 get_anno(Key, Construct) ->
     maps:get(Key, get_anno(Construct)).
 
+-spec get_anno(atom(), construct(),any()) -> any().
+
+get_anno(Key, Construct, Default) ->
+    maps:get(Key, get_anno(Construct), Default).
+
+get_anno(#b_function{anno=Anno}) -> Anno;
 get_anno(#b_blk{anno=Anno}) -> Anno;
 get_anno(#b_set{anno=Anno}) -> Anno;
 get_anno(#b_br{anno=Anno}) -> Anno;
@@ -169,6 +189,7 @@ no_side_effect(#b_set{op=Op}) ->
         bs_match -> true;
         bs_start_match -> true;
         bs_test_tail -> true;
+        bs_get_tail -> true;
         bs_put -> true;
         extract -> true;
         get_hd -> true;
@@ -306,7 +327,7 @@ def_used(Ls, Blocks) ->
 
 -spec dominators(Blocks) -> Result when
       Blocks :: block_map(),
-      Result :: #{label():=ordsets:ordset(label())}.
+      Result :: dominator_map().
 
 dominators(Blocks) ->
     Preds = predecessors(Blocks),
@@ -327,6 +348,26 @@ fold_instrs_rpo(Fun, From, Acc0, Blocks) ->
     Top = rpo(From, Blocks),
     fold_instrs_rpo_1(Top, Fun, Blocks, Acc0).
 
+%% Like mapfold_instrs_rpo but at the block level to support lookahead and
+%% scope-dependent transformations.
+-spec mapfold_blocks_rpo(Fun, From, Acc, Blocks) -> Result when
+      Fun :: fun((label(), b_blk(), any()) -> {b_blk(), any()}),
+      From :: [label()],
+      Acc :: any(),
+      Blocks :: block_map(),
+      Result :: {block_map(), any()}.
+mapfold_blocks_rpo(Fun, From, Acc, Blocks) ->
+    Successors = rpo(From, Blocks),
+    foldl(fun(Lbl, A) ->
+                  mapfold_blocks_rpo_1(Fun, Lbl, A)
+          end, {Blocks, Acc}, Successors).
+
+mapfold_blocks_rpo_1(Fun, Lbl, {Blocks0, Acc0}) ->
+    Block0 = maps:get(Lbl, Blocks0),
+    {Block, Acc} = Fun(Lbl, Block0, Acc0),
+    Blocks = maps:put(Lbl, Block, Blocks0),
+    {Blocks, Acc}.
+
 -spec mapfold_instrs_rpo(Fun, From, Acc0, Blocks0) -> {Blocks,Acc} when
       Fun :: fun((b_blk()|terminator(), any()) -> any()),
       From :: [label()],
@@ -442,7 +483,7 @@ rpo(From, Blocks) ->
     Ls.
 
 -spec rename_vars(Rename, [label()], block_map()) -> block_map() when
-      Rename :: [{var_name(),value()}] | #{var_name():=value()}.
+      Rename :: rename_map() | rename_proplist().
 
 rename_vars(Rename, From, Blocks) when is_list(Rename) ->
     rename_vars(maps:from_list(Rename), From, Blocks);
@@ -535,6 +576,34 @@ used(#b_switch{arg=#b_var{}=V}) ->
     [V];
 used(_) -> [].
 
+-spec definitions(Blocks :: block_map()) -> definition_map().
+definitions(Blocks) ->
+    beam_ssa:fold_instrs_rpo(fun(#b_set{ dst = Var }=I, Acc) ->
+                                     maps:put(Var, I, Acc);
+                                (_Terminator, Acc) ->
+                                     Acc
+                             end, [0], #{}, Blocks).
+
+-spec uses(Blocks :: block_map()) -> usage_map().
+uses(Blocks) ->
+    uses([0], Blocks).
+
+-spec uses(From, Blocks) -> usage_map() when
+      From :: [label()],
+      Blocks :: block_map().
+uses(From, Blocks) ->
+    beam_ssa:fold_rpo(fun fold_uses_block/3, From, #{}, Blocks).
+
+fold_uses_block(Lbl, #b_blk{is=Is,last=Last}, UseMap0) ->
+    F = fun(I, UseMap) ->
+                foldl(fun(Var, Acc) ->
+                              Uses0 = maps:get(Var, Acc, []),
+                              Uses = [{Lbl, I} | Uses0],
+                              maps:put(Var, Uses, Acc)
+                      end, UseMap, beam_ssa:used(I))
+        end,
+    F(Last, foldl(F, UseMap0, Is)).
+
 %%%
 %%% Internal functions.
 %%%
-- 
cgit v1.2.3


From fd6246c5191d07b80bc7100b470a37a338accecd Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?John=20H=C3=B6gberg?= <john@erlang.org>
Date: Tue, 8 May 2018 08:52:22 +0200
Subject: 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.
---
 erts/emulator/beam/bs_instrs.tab                   |  294 +++++-
 erts/emulator/beam/erl_bits.c                      |   36 +
 erts/emulator/beam/erl_bits.h                      |   13 +-
 erts/emulator/beam/ops.tab                         |   32 +
 lib/compiler/src/Makefile                          |    2 +-
 lib/compiler/src/beam_bsm.erl                      |  719 --------------
 lib/compiler/src/beam_disasm.erl                   |   10 +
 lib/compiler/src/beam_ssa_bsm.erl                  | 1027 ++++++++++++++++++++
 lib/compiler/src/beam_ssa_codegen.erl              |   46 +-
 lib/compiler/src/beam_ssa_pre_codegen.erl          |  175 +++-
 lib/compiler/src/beam_ssa_type.erl                 |    2 +
 lib/compiler/src/beam_validator.erl                |  182 ++--
 lib/compiler/src/compile.erl                       |   15 +-
 lib/compiler/src/compiler.app.src                  |    2 +-
 lib/compiler/src/genop.tab                         |   18 +
 .../test/beam_validator_SUITE_data/bad_bin_match.S |    2 +-
 .../beam_validator_SUITE_data/receive_stacked.S    |    6 +-
 lib/compiler/test/bs_match_SUITE.erl               |   99 +-
 lib/compiler/test/compile_SUITE.erl                |    5 +-
 lib/compiler/test/misc_SUITE.erl                   |   11 -
 lib/compiler/test/warnings_SUITE.erl               |   51 +-
 system/doc/efficiency_guide/binaryhandling.xml     |    8 +-
 22 files changed, 1863 insertions(+), 892 deletions(-)
 delete mode 100644 lib/compiler/src/beam_bsm.erl
 create mode 100644 lib/compiler/src/beam_ssa_bsm.erl

diff --git a/erts/emulator/beam/bs_instrs.tab b/erts/emulator/beam/bs_instrs.tab
index 9fd70cbbb6..2dde70c2e1 100644
--- a/erts/emulator/beam/bs_instrs.tab
+++ b/erts/emulator/beam/bs_instrs.tab
@@ -728,17 +728,23 @@ bs_start_match.execute(Fail, Live, Slots, Dst) {
         $FAIL($Fail);
     }
     header = *boxed_val(context);
-    slots = $Slots;
+
+    /* Reserve a slot for the start position. */
+    slots = $Slots + 1;
     live = $Live;
+
     if (header_is_bin_matchstate(header)) {
         ErlBinMatchState* ms = (ErlBinMatchState *) boxed_val(context);
         Uint actual_slots = HEADER_NUM_SLOTS(header);
+
+        /* We're not compatible with contexts created by bs_start_match3. */
+        ASSERT(actual_slots >= 1);
+
         ms->save_offset[0] = ms->mb.offset;
-        if (actual_slots < slots) {
+        if (ERTS_UNLIKELY(actual_slots < slots)) {
             ErlBinMatchState* expanded;
             Uint live = $Live;
             Uint wordsneeded = ERL_BIN_MATCHSTATE_SIZE(slots);
-
             $GC_TEST_PRESERVE(wordsneeded, live, context);
             ms = (ErlBinMatchState *) boxed_val(context);
             expanded = (ErlBinMatchState *) HTOP;
@@ -746,9 +752,10 @@ bs_start_match.execute(Fail, Live, Slots, Dst) {
             *HTOP = HEADER_BIN_MATCHSTATE(slots);
             HTOP += wordsneeded;
             HEAP_SPACE_VERIFIED(0);
+            context = make_matchstate(expanded);
             $REFRESH_GEN_DEST();
-            $Dst = make_matchstate(expanded);
         }
+        $Dst = context;
     } else if (is_binary_header(header)) {
         Eterm result;
         Uint wordsneeded = ERL_BIN_MATCHSTATE_SIZE(slots);
@@ -1038,10 +1045,289 @@ i_bs_match_string(Ctx, Fail, Bits, Ptr) {
 
 i_bs_save2(Src, Slot) {
     ErlBinMatchState* _ms = (ErlBinMatchState*) boxed_val((Eterm) $Src);
+    ASSERT(HEADER_NUM_SLOTS(_ms->thing_word) > $Slot);
     _ms->save_offset[$Slot] = _ms->mb.offset;
 }
 
 i_bs_restore2(Src, Slot) {
     ErlBinMatchState* _ms = (ErlBinMatchState*) boxed_val((Eterm) $Src);
+    ASSERT(HEADER_NUM_SLOTS(_ms->thing_word) > $Slot);
     _ms->mb.offset = _ms->save_offset[$Slot];
 }
+
+bs_get_tail(Src, Dst, Live) {
+    ErlBinMatchBuffer* mb;
+    Uint size, offs;
+    ErlSubBin* sb;
+    Eterm context;
+
+    context = $Src;
+
+    ASSERT(header_is_bin_matchstate(*boxed_val(context)));
+
+    $GC_TEST_PRESERVE(ERL_SUB_BIN_SIZE, $Live, context);
+
+    mb = ms_matchbuffer(context);
+
+    offs = mb->offset;
+    size = mb->size - offs;
+
+    sb = (ErlSubBin *) HTOP;
+    HTOP += ERL_SUB_BIN_SIZE;
+
+    sb->thing_word = HEADER_SUB_BIN;
+    sb->size = BYTE_OFFSET(size);
+    sb->bitsize = BIT_OFFSET(size);
+    sb->offs = BYTE_OFFSET(offs);
+    sb->bitoffs = BIT_OFFSET(offs);
+    sb->is_writable = 0;
+    sb->orig = mb->orig;
+
+    $REFRESH_GEN_DEST();
+    $Dst = make_binary(sb);
+}
+
+
+%if ARCH_64
+
+i_bs_start_match3_gp(Src, Live, Fail, Dst, Pos) {
+    Eterm context, header;
+    Uint position, live;
+
+    context = $Src;
+    live = $Live;
+
+    if (!is_boxed(context)) {
+        $FAIL($Fail);
+    }
+
+    header = *boxed_val(context);
+
+    if (header_is_bin_matchstate(header)) {
+        ErlBinMatchBuffer *mb;
+
+        ASSERT(HEADER_NUM_SLOTS(header) == 0);
+
+        mb = ms_matchbuffer(context);
+        position = mb->offset;
+
+        $Dst = context;
+    } else if (is_binary_header(header)) {
+        ErlBinMatchState *ms;
+
+        $GC_TEST_PRESERVE(ERL_BIN_MATCHSTATE_SIZE(0), live, context);
+        HEAP_TOP(c_p) = HTOP;
+#ifdef DEBUG
+        c_p->stop = E;	/* Needed for checking in HeapOnlyAlloc(). */
+#endif
+        ms = erts_bs_start_match_3(c_p, context);
+        HTOP = HEAP_TOP(c_p);
+        HEAP_SPACE_VERIFIED(0);
+
+        if (ms == NULL) {
+            $FAIL($Fail);
+        }
+
+        $REFRESH_GEN_DEST();
+        $Dst = make_matchstate(ms);
+        position = ms->mb.offset;
+    } else {
+        $FAIL($Fail);
+    }
+
+    ASSERT(IS_USMALL(0, position));
+    $Pos = make_small(position);
+}
+
+i_bs_start_match3(Src, Live, Fail, Dst) {
+    Eterm context, header;
+    Uint live;
+
+    context = $Src;
+    live = $Live;
+
+    if (!is_boxed(context)) {
+        $FAIL($Fail);
+    }
+
+    header = *boxed_val(context);
+
+    if (header_is_bin_matchstate(header)) {
+        ASSERT(HEADER_NUM_SLOTS(header) == 0);
+        $Dst = context;
+    } else if (is_binary_header(header)) {
+        ErlBinMatchState *ms;
+
+        $GC_TEST_PRESERVE(ERL_BIN_MATCHSTATE_SIZE(0), live, context);
+        HEAP_TOP(c_p) = HTOP;
+#ifdef DEBUG
+        c_p->stop = E;	/* Needed for checking in HeapOnlyAlloc(). */
+#endif
+        ms = erts_bs_start_match_3(c_p, context);
+        HTOP = HEAP_TOP(c_p);
+        HEAP_SPACE_VERIFIED(0);
+
+        if (ms == NULL) {
+            $FAIL($Fail);
+        }
+
+        $REFRESH_GEN_DEST();
+        $Dst = make_matchstate(ms);
+    } else {
+        $FAIL($Fail);
+    }
+}
+
+bs_set_position(Ctx, Pos) {
+    ErlBinMatchBuffer* mb;
+    Eterm context;
+
+    context = $Ctx;
+    ASSERT(header_is_bin_matchstate(*boxed_val(context)));
+
+    mb = ms_matchbuffer(context);
+    mb->offset = unsigned_val($Pos);
+}
+
+i_bs_get_position(Ctx, Dst) {
+    ErlBinMatchBuffer* mb;
+    Eterm context;
+
+    context = $Ctx;
+    ASSERT(header_is_bin_matchstate(*boxed_val(context)));
+
+    mb = ms_matchbuffer(context);
+    $Dst = make_small(mb->offset);
+}
+
+%else
+
+#
+# Unlike their 64-bit counterparts, the 32-bit position instructions operate on
+# an offset from the "base position" of the context because storing raw
+# positions would lead to the creation of far too many bigints.
+#
+# When a match context is reused we check whether its position fits into an
+# immediate, and create a new match context if it does not. This means we only
+# have to allocate stuff roughly once every 16MB rather than every time we
+# match at a position beyond 16MB.
+#
+
+bs_set_position(Ctx, Pos) {
+    Eterm context, position;
+    ErlBinMatchState *ms;
+
+    context = $Ctx;
+    position = $Pos;
+
+    ASSERT(header_is_bin_matchstate(*boxed_val(context)));
+    ms = (ErlBinMatchState*)boxed_val(context);
+
+    if (ERTS_LIKELY(is_small(position))) {
+        ms->mb.offset = ms->save_offset[0] + unsigned_val(position);
+    } else {
+        ASSERT(is_big(position));
+        ms->mb.offset = ms->save_offset[0] + *BIG_V(big_val(position));
+    }
+}
+
+bs_get_position(Ctx, Dst, Live) {
+    ErlBinMatchState *ms;
+    Eterm context;
+    Uint position;
+
+    context = $Ctx;
+
+    ASSERT(header_is_bin_matchstate(*boxed_val(context)));
+    ms = (ErlBinMatchState*)boxed_val(context);
+
+    position = ms->mb.offset - ms->save_offset[0];
+
+    if (ERTS_LIKELY(IS_USMALL(0, position))) {
+        $Dst = make_small(position);
+    } else {
+        Eterm *hp;
+
+        $GC_TEST_PRESERVE(BIG_UINT_HEAP_SIZE, $Live, context);
+
+        hp = HTOP;
+        HTOP += BIG_UINT_HEAP_SIZE;
+
+        *hp = make_pos_bignum_header(1);
+        BIG_DIGIT(hp, 0) = position;
+
+        $REFRESH_GEN_DEST();
+        $Dst = make_big(hp);
+    }
+}
+
+i_bs_start_match3(Src, Live, Fail, Dst) {
+    Eterm context, header;
+    Uint live;
+
+    context = $Src;
+    live = $Live;
+
+    if (!is_boxed(context)) {
+        $FAIL($Fail);
+    }
+
+    header = *boxed_val(context);
+
+    if (header_is_bin_matchstate(header)) {
+        ErlBinMatchState *current_ms;
+        Uint position;
+
+        ASSERT(HEADER_NUM_SLOTS(header) == 1);
+
+        current_ms = (ErlBinMatchState*)boxed_val(context);
+        position = current_ms->mb.offset - current_ms->save_offset[0];
+
+        if (ERTS_LIKELY(IS_USMALL(0, position))) {
+            $Dst = context;
+        } else {
+            ErlBinMatchState *new_ms;
+
+            $GC_TEST_PRESERVE(ERL_BIN_MATCHSTATE_SIZE(1), live, context);
+            current_ms = (ErlBinMatchState*)boxed_val(context);
+
+            new_ms = (ErlBinMatchState*)HTOP;
+            HTOP += ERL_BIN_MATCHSTATE_SIZE(1);
+
+            new_ms->thing_word = HEADER_BIN_MATCHSTATE(1);
+            new_ms->save_offset[0] = current_ms->mb.offset;
+            new_ms->mb = current_ms->mb;
+
+            $REFRESH_GEN_DEST();
+            $Dst = make_matchstate(new_ms);
+        }
+    } else if (is_binary_header(header)) {
+        Eterm result;
+
+        $GC_TEST_PRESERVE(ERL_BIN_MATCHSTATE_SIZE(1), live, context);
+        HEAP_TOP(c_p) = HTOP;
+
+#ifdef DEBUG
+        c_p->stop = E;	/* Needed for checking in HeapOnlyAlloc(). */
+#endif
+
+        /* We intentionally use erts_bs_start_match_2 so that we can use
+         * save_offset as a base for all saved positions on this context,
+         * allowing us to avoid bigints for much longer. */
+        result = erts_bs_start_match_2(c_p, context, 1);
+
+        HTOP = HEAP_TOP(c_p);
+        HEAP_SPACE_VERIFIED(0);
+
+        if (is_non_value(result)) {
+            $FAIL($Fail);
+        }
+
+        $REFRESH_GEN_DEST();
+        $Dst = result;
+    } else {
+        $FAIL($Fail);
+    }
+}
+
+%endif
diff --git a/erts/emulator/beam/erl_bits.c b/erts/emulator/beam/erl_bits.c
index 3a16913473..e82c776e70 100644
--- a/erts/emulator/beam/erl_bits.c
+++ b/erts/emulator/beam/erl_bits.c
@@ -144,6 +144,42 @@ erts_bs_start_match_2(Process *p, Eterm Binary, Uint Max)
     return make_matchstate(ms);
 }
 
+ErlBinMatchState *erts_bs_start_match_3(Process *p, Eterm Binary)
+{
+    Eterm Orig;
+    Uint offs;
+    Uint* hp;
+    Uint NeededSize;
+    ErlBinMatchState *ms;
+    Uint bitoffs;
+    Uint bitsize;
+    Uint total_bin_size;
+    ProcBin* pb;
+
+    ASSERT(is_binary(Binary));
+    total_bin_size = binary_size(Binary);
+    if ((total_bin_size >> (8*sizeof(Uint)-3)) != 0) {
+        return NULL;
+    }
+
+    NeededSize = ERL_BIN_MATCHSTATE_SIZE(0);
+    hp = HeapOnlyAlloc(p, NeededSize);
+    ms = (ErlBinMatchState *) hp;
+    ERTS_GET_REAL_BIN(Binary, Orig, offs, bitoffs, bitsize);
+    pb = (ProcBin *) boxed_val(Orig);
+    if (pb->thing_word == HEADER_PROC_BIN && pb->flags != 0) {
+        erts_emasculate_writable_binary(pb);
+    }
+
+    ms->thing_word = HEADER_BIN_MATCHSTATE(0);
+    (ms->mb).orig = Orig;
+    (ms->mb).base = binary_bytes(Orig);
+    (ms->mb).offset = 8 * offs + bitoffs;
+    (ms->mb).size = total_bin_size * 8 + (ms->mb).offset + bitsize;
+
+    return ms;
+}
+
 #ifdef DEBUG
 # define CHECK_MATCH_BUFFER(MB) check_match_buffer(MB)
 
diff --git a/erts/emulator/beam/erl_bits.h b/erts/emulator/beam/erl_bits.h
index 7beef5cfda..50d353e1fa 100644
--- a/erts/emulator/beam/erl_bits.h
+++ b/erts/emulator/beam/erl_bits.h
@@ -73,12 +73,16 @@ struct erl_bits_state {
 typedef struct erl_bin_match_struct{
   Eterm thing_word;
   ErlBinMatchBuffer mb;		/* Present match buffer */
-  Eterm save_offset[1];		/* Saved offsets */
+  Eterm save_offset[1];         /* Saved offsets, only valid for contexts
+                                 * created through bs_start_match2. */
 } ErlBinMatchState;
 
-#define ERL_BIN_MATCHSTATE_SIZE(_Max) ((sizeof(ErlBinMatchState) + (_Max)*sizeof(Eterm))/sizeof(Eterm)) 
-#define HEADER_BIN_MATCHSTATE(_Max) _make_header(ERL_BIN_MATCHSTATE_SIZE((_Max))-1, _TAG_HEADER_BIN_MATCHSTATE)
-#define HEADER_NUM_SLOTS(hdr) (header_arity(hdr)-sizeof(ErlBinMatchState)/sizeof(Eterm)+1)
+#define ERL_BIN_MATCHSTATE_SIZE(_Max) \
+    ((offsetof(ErlBinMatchState, save_offset) + (_Max)*sizeof(Eterm))/sizeof(Eterm))
+#define HEADER_BIN_MATCHSTATE(_Max) \
+    _make_header(ERL_BIN_MATCHSTATE_SIZE((_Max)) - 1, _TAG_HEADER_BIN_MATCHSTATE)
+#define HEADER_NUM_SLOTS(hdr) \
+    (header_arity(hdr) - (offsetof(ErlBinMatchState, save_offset) / sizeof(Eterm)) + 1)
 
 #define make_matchstate(_Ms) make_boxed((Eterm*)(_Ms))  
 #define ms_matchbuffer(_Ms) &(((ErlBinMatchState*) boxed_val(_Ms))->mb)
@@ -144,6 +148,7 @@ void erts_bits_destroy_state(ERL_BITS_PROTO_0);
  */
 
 Eterm erts_bs_start_match_2(Process *p, Eterm Bin, Uint Max);
+ErlBinMatchState *erts_bs_start_match_3(Process *p, Eterm Bin);
 Eterm erts_bs_get_integer_2(Process *p, Uint num_bits, unsigned flags, ErlBinMatchBuffer* mb);
 Eterm erts_bs_get_binary_2(Process *p, Uint num_bits, unsigned flags, ErlBinMatchBuffer* mb);
 Eterm erts_bs_get_float_2(Process *p, Uint num_bits, unsigned flags, ErlBinMatchBuffer* mb);
diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab
index c3e71ff77a..349034e8ac 100644
--- a/erts/emulator/beam/ops.tab
+++ b/erts/emulator/beam/ops.tab
@@ -1167,6 +1167,38 @@ bs_context_to_binary Y=y => move Y x | bs_context_to_binary x
 
 bs_context_to_binary x
 
+# Gets a bitstring from the tail of a context.
+bs_get_tail xy d t
+
+# New bs_start_match variant for contexts with external position storage.
+#
+# bs_get/set_position is used to save positions into registers instead of
+# "slots" in the context itself, which lets us continue matching even after
+# we've passed it off to another function.
+
+%if ARCH_64
+bs_start_match3 Fail Bin Live Ctx | bs_get_position Ctx Pos=x Ignored => \
+    i_bs_start_match3_gp Bin Live Fail Ctx Pos
+i_bs_start_match3_gp xy t f d x
+%endif
+
+bs_start_match3 Fail=f ica Live Dst => jump Fail
+bs_start_match3 Fail Bin Live Dst => i_bs_start_match3 Bin Live Fail Dst
+
+i_bs_start_match3 xy t f d
+
+# Match context position instructions. 64-bit assumes that all positions can
+# fit into an unsigned small.
+
+%if ARCH_64
+    bs_get_position Src Dst Live => i_bs_get_position Src Dst
+    i_bs_get_position xy xy
+    bs_set_position xy xy
+%else
+    bs_get_position xy d t?
+    bs_set_position xy xy
+%endif
+
 #
 # Utf8/utf16/utf32 support. (R12B-5)
 #
diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile
index 522523726b..26ae6566e6 100644
--- a/lib/compiler/src/Makefile
+++ b/lib/compiler/src/Makefile
@@ -50,7 +50,6 @@ MODULES =  \
 	beam_asm \
 	beam_block \
 	beam_bs \
-	beam_bsm \
 	beam_clean \
 	beam_dict \
 	beam_disasm \
@@ -61,6 +60,7 @@ MODULES =  \
 	beam_opcodes \
 	beam_peep \
 	beam_ssa \
+	beam_ssa_bsm \
 	beam_ssa_codegen \
 	beam_ssa_dead \
 	beam_ssa_lint \
diff --git a/lib/compiler/src/beam_bsm.erl b/lib/compiler/src/beam_bsm.erl
deleted file mode 100644
index abc6e96c85..0000000000
--- a/lib/compiler/src/beam_bsm.erl
+++ /dev/null
@@ -1,719 +0,0 @@
-%%
-%% %CopyrightBegin%
-%% 
-%% 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.
-%% 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_bsm).
--export([module/2,format_error/1]).
-
--import(lists, [member/2,foldl/3,reverse/1,sort/1,all/2]).
-
-%%%
-%%% We optimize bit syntax matching where the tail end of a binary is
-%%% matched out and immediately passed on to a bs_start_match2 instruction,
-%%% such as in this code sequence:
-%%%
-%%%     func_info ...
-%%% L1	test bs_start_match2 {f,...} {x,0} Live SavePositions {x,0}
-%%%              . . .
-%%%     test bs_get_binary2 {f,...} {x,0} all 1 Flags {x,0}
-%%%              . . .
-%%%     call_only 2 L1
-%%%
-%%% The sequence can be optimized simply by removing the bs_get_binary2
-%%% instruction. Another example:
-%%%
-%%%     func_info ...
-%%% L1	test bs_start_match2 {f,...} {x,0} Live SavePositions {x,0}
-%%%              . . .
-%%%     test bs_get_binary2 {f,...} {x,0} all 8 Flags {x,1}
-%%%              . . .
-%%%     move {x,1} {x,0}
-%%%     call_only 2 L1
-%%%
-%%% In this case, the bs_get_binary2 instruction must be replaced by
-%%%
-%%%	test bs_unit {x,1} 8
-%%%
-%%% to ensure that the match fail if the length of the binary in bits
-%%% is not evenly divisible by 8.
-%%%
-%%% Note that the bs_start_match2 instruction doesn't need to be in the same
-%%% function as the caller. It can be in the beginning of any function, or
-%%% follow the bs_get_binary2 instruction in the same function. The important
-%%% thing is that the match context register is not copied or built into
-%%% data structures or passed to BIFs.
-%%%
-
--type label() :: beam_asm:label().
--type func_info() :: {beam_asm:reg(),boolean()}.
-
--record(btb,
-	{f :: gb_trees:tree(label(), func_info()),
-	 index :: beam_utils:code_index(), %{Label,Code} index (for liveness).
-	 ok_br=gb_sets:empty() :: gb_sets:set(label()), %Labels that are OK.
-	 must_not_save=false :: boolean(), %Must not save position when
-					   % optimizing (reaches
-                                           % bs_context_to_binary).
-	 must_save=false :: boolean() %Must save position when optimizing.
-	}).
-
-
--spec module(beam_utils:module_code(), [compile:option()]) ->
-                    {'ok',beam_utils:module_code()}.
-
-module({Mod,Exp,Attr,Fs0,Lc}, Opts) ->
-    FIndex = btb_index(Fs0),
-    Fs = [function(F, FIndex) || F <- Fs0],
-    Code = {Mod,Exp,Attr,Fs,Lc},
-    case proplists:get_bool(bin_opt_info, Opts) of
-	true ->
-	    {ok,Code,collect_warnings(Fs)};
-	false ->
-	    {ok,Code}
-    end.
-
--spec format_error('bin_opt' | {'no_bin_opt', term()}) -> nonempty_string().
-
-format_error(bin_opt) ->
-    "OPTIMIZED: creation of sub binary delayed";
-format_error({no_bin_opt,Reason}) ->
-    lists:flatten(["NOT OPTIMIZED: "|format_error_1(Reason)]).
-
-%%%
-%%% Local functions.
-%%% 
-
-function({function,Name,Arity,Entry,Is}, FIndex) ->
-    try
-	Index = beam_utils:index_labels(Is),
-	D = #btb{f=FIndex,index=Index},
-	{function,Name,Arity,Entry,btb_opt_1(Is, D, [])}
-    catch
-        Class:Error:Stack ->
-	    io:fwrite("Function: ~w/~w\n", [Name,Arity]),
-	    erlang:raise(Class, Error, Stack)
-    end.
-
-btb_opt_1([{test,bs_get_binary2,F,_,[Reg,{atom,all},U,Fs],Reg}=I0|Is], D, Acc0) ->
-    case btb_reaches_match(Is, [Reg], D) of
-	{error,Reason} ->
-	    Comment = btb_comment_no_opt(Reason, Fs),
-	    btb_opt_1(Is, D, [Comment,I0|Acc0]);
-	{ok,MustSave} ->
-	    Comment = btb_comment_opt(Fs),
-	    Acc1 = btb_gen_save(MustSave, Reg, [Comment|Acc0]),
-	    Acc = case U of
-		      1 -> Acc1;
-		      _ -> [{test,bs_test_unit,F,[Reg,U]}|Acc1]
-		  end,
-	    btb_opt_1(Is, D, Acc)
-    end;
-btb_opt_1([{test,bs_get_binary2,F,_,[Ctx,{atom,all},U,Fs],Dst}=I0|Is0], D, Acc0) ->
-    case btb_reaches_match(Is0, [Ctx,Dst], D) of
-	{error,Reason} ->
-	    Comment = btb_comment_no_opt(Reason, Fs),
-	    btb_opt_1(Is0, D, [Comment,I0|Acc0]);
-	{ok,MustSave} when U =:= 1 ->
-	    Comment = btb_comment_opt(Fs),
-            Acc = btb_gen_save(MustSave, Ctx, [Comment|Acc0]),
-            Is = prepend_move(Ctx, Dst, Is0),
-	    btb_opt_1(Is, D, Acc);
-	{ok,MustSave} ->
-	    Comment = btb_comment_opt(Fs),
-	    Acc1 = btb_gen_save(MustSave, Ctx, [Comment|Acc0]),
-            Acc = [{test,bs_test_unit,F,[Ctx,U]}|Acc1],
-            Is = prepend_move(Ctx, Dst, Is0),
-	    btb_opt_1(Is, D, Acc)
-    end;
-btb_opt_1([I|Is], D, Acc) ->
-    %%io:format("~p\n", [I]),
-    btb_opt_1(Is, D, [I|Acc]);
-btb_opt_1([], _, Acc) ->
-    reverse(Acc).
-
-btb_gen_save(true, Reg, Acc) ->
-    [{bs_save2,Reg,{atom,start}}|Acc];
-btb_gen_save(false, _, Acc) -> Acc.
-
-prepend_move(Ctx, Dst, [{block,Bl0}|Is]) ->
-    Bl = [{set,[Dst],[Ctx],move}|Bl0],
-    [{block,Bl}|Is];
-prepend_move(Ctx, Dst, Is) ->
-    [{move,Ctx,Dst}|Is].
-
-%% btb_reaches_match([Instruction], [Register], D) ->
-%%   {ok,MustSave}|{error,Reason}
-%%
-%%  The list of Registers should be a list of registers referencing a
-%%  match context. The Register may contain one element if the
-%%  bs_get_binary2 instruction looks like
-%%
-%%    test bs_get_binary2 {f,...} Ctx all _ _ Ctx
-%%
-%%  or two elements if the instruction looks like
-%%
-%%    test bs_get_binary2 {f,...} Ctx all _ _ Dst
-%%
-%%  This function determines whether the bs_get_binary2 instruction
-%%  can be omitted (retaining the match context instead of creating
-%%  a sub binary).
-%%
-%%  The rule is that the match context ultimately must end up at a
-%%  bs_start_match2 instruction and nowhere else. That it, it must not
-%%  be passed to BIFs, or copied or put into data structures. There
-%%  must only be one copy alive when the match context reaches the
-%%  bs_start_match2 instruction.
-%%
-%%  At a branch, we must follow all branches and make sure that the above
-%%  rule is followed (or that the branch kills the match context).
-%%
-%%  The MustSave return value will be true if control may end up at
-%%  bs_context_to_binary instruction. Since that instruction uses the
-%%  saved start position, we must use "bs_save2 Ctx start" to
-%%  update the saved start position. An additional complication is that
-%%  "bs_save2 Ctx start" must not be used if Dst and Ctx are
-%%  different registers and both registers may be passed to
-%%  a bs_context_to_binary instruction.
-%% 
-
-btb_reaches_match(Is, RegList, D) ->
-    try
-	Regs = btb_regs_from_list(RegList),
-	#btb{must_not_save=MustNotSave,must_save=MustSave} =
-            btb_reaches_match_1(Is, Regs, D),
-	case MustNotSave andalso MustSave of
-	    true -> btb_error(must_and_must_not_save);
-	    false -> {ok,MustSave}
-	end
-    catch
-	throw:{error,_}=Error -> Error
-    end.
-
-btb_reaches_match_1(Is, Regs, D) ->
-    case btb_are_registers_empty(Regs) of
-	false ->
-	    btb_reaches_match_2(Is, Regs, D);
-	true ->
-	    %% The context was killed, which is OK.
-	    D
-    end.
-
-btb_reaches_match_2([{block,Bl}|Is], Regs0, D) ->
-    Regs = btb_reaches_match_block(Bl, Regs0),
-    btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([{call,Arity,{f,Lbl}}|Is], Regs0, D) ->
-    case is_tail_call(Is) of
-	true ->
-	    Regs1 = btb_kill_not_live(Arity, Regs0),
-	    Regs = btb_kill_yregs(Regs1),
-	    btb_tail_call(Lbl, Regs, D);
-	false ->
-	    btb_call(Arity, Lbl, Regs0, Is, D)
-    end;
-btb_reaches_match_2([{apply,Arity}|Is], Regs, D) ->
-    btb_call(Arity+2, apply, Regs, Is, D);
-btb_reaches_match_2([{call_fun,Live}=I|Is], Regs, D) ->
-    btb_ensure_not_used([{x,Live}], I, Regs),
-    btb_call(Live, I, Regs, Is, D);
-btb_reaches_match_2([{make_fun2,_,_,_,Live}|Is], Regs, D) ->
-    btb_call(Live, make_fun2, Regs, Is, D);
-btb_reaches_match_2([{call_ext,Arity,Func}=I|Is], Regs0, D) ->
-    %% Allow us scanning beyond the call in case the match
-    %% context is saved on the stack.
-    case beam_jump:is_exit_instruction(I) of
-	false ->
-	    btb_call(Arity, Func, Regs0, Is, D);
-	true ->
-	    Regs = btb_kill_not_live(Arity, Regs0),
-	    btb_tail_call(Func, Regs, D)
-    end;
-btb_reaches_match_2([{kill,Y}|Is], Regs, D) ->
-    btb_reaches_match_1(Is, btb_kill([Y], Regs), D);
-btb_reaches_match_2([{deallocate,_}|Is], Regs0, D) ->
-    Regs = btb_kill_yregs(Regs0),
-    btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([return=I|_], Regs0, D) ->
-    btb_ensure_not_used([{x,0}], I, Regs0),
-    D;
-btb_reaches_match_2([{gc_bif,_,{f,F},Live,Ss,Dst}=I|Is], Regs0, D0) ->
-    btb_ensure_not_used(Ss, I, Regs0),
-    Regs1 = btb_kill_not_live(Live, Regs0),
-    Regs = btb_kill([Dst], Regs1),
-    D = btb_follow_branch(F, Regs, D0),
-    btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([{bif,_,{f,F},Ss,Dst}=I|Is], Regs0, D0) ->
-    btb_ensure_not_used(Ss, I, Regs0),
-    Regs = btb_kill([Dst], Regs0),
-    D = btb_follow_branch(F, Regs, D0),
-    btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([{get_map_elements,{f,F},Src,{list,Ls}}=I|Is], Regs0, D0) ->
-    {Ss,Ds} = beam_utils:split_even(Ls),
-    btb_ensure_not_used([Src|Ss], I, Regs0),
-    Regs = btb_kill(Ds, Regs0),
-    D = btb_follow_branch(F, Regs, D0),
-    btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([{test,bs_start_match2,{f,F},Live,[Ctx,_],Ctx}=I|Is],
-		    Regs0, D0) ->
-    CtxRegs = btb_context_regs(Regs0),
-    case member(Ctx, CtxRegs) of
-	false ->
-	    %% This bs_start_match2 instruction does not use "our"
-	    %% match state. Therefore we can continue the search
-	    %% for another bs_start_match2 instruction.
-	    D = btb_follow_branch(F, Regs0, D0),
-	    Regs = btb_kill_not_live(Live, Regs0),
-	    btb_reaches_match_2(Is, Regs, D);
-	true ->
-	    %% OK. This instruction will use "our" match state,
-	    %% but we must make sure that all other copies of the
-	    %% match state are killed in the code that follows
-	    %% the instruction. (We know that the fail branch cannot
-	    %% be taken in this case.)
-	    OtherCtxRegs = CtxRegs -- [Ctx],
-	    case btb_are_all_unused(OtherCtxRegs, Is, D0) of
-		false -> btb_error({OtherCtxRegs,not_all_unused_after,I});
-		true -> D0
-	    end
-    end;
-btb_reaches_match_2([{test,bs_start_match2,{f,F},Live,[Bin,_],Ctx}|Is],
-		    Regs0, D0) ->
-    CtxRegs = btb_context_regs(Regs0),
-    case member(Bin, CtxRegs) orelse member(Ctx, CtxRegs) of
-	false ->
-	    %% This bs_start_match2 does not reference any copy of the
-	    %% match state. Therefore it can safely be passed on the
-	    %% way to another (perhaps more suitable) bs_start_match2
-	    %% instruction.
-	    D = btb_follow_branch(F, Regs0, D0),
-	    Regs = btb_kill_not_live(Live, Regs0),
-	    btb_reaches_match_2(Is, Regs, D);
-	true ->
-	    %% This variant of the bs_start_match2 instruction does
-	    %% not accept a match state as source.
-	    btb_error(unsuitable_bs_start_match)
-    end;
-btb_reaches_match_2([{test,_,{f,F},Ss}=I|Is], Regs, D0) ->
-    btb_ensure_not_used(Ss, I, Regs),
-    D1 = btb_follow_branch(F, Regs, D0),
-    D = case Is of
-            [{bs_context_to_binary,_}|_] ->
-                %% bs_context_to_binary following a test instruction
-                %% probably needs the current position to be saved as
-                %% the new start position, but we can't be sure.
-                %% Therefore, conservatively disable the optimization
-                %% (instead of forcing a saving of the position).
-                D1#btb{must_save=true,must_not_save=true};
-            _ ->
-                D1
-        end,
-    btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([{test,_,{f,F},_,Ss,_}=I|Is], Regs, D0) ->
-    btb_ensure_not_used(Ss, I, Regs),
-    D = btb_follow_branch(F, Regs, D0),
-    btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([{select,_,Src,{f,F},Conds}=I|Is], Regs, D0) ->
-    btb_ensure_not_used([Src], I, Regs),
-    D1 = btb_follow_branch(F, Regs, D0),
-    D = btb_follow_branches(Conds, Regs, D1),
-    btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([{jump,{f,Lbl}}|_], Regs, #btb{index=Li}=D) ->
-    Is = fetch_code_at(Lbl, Li),
-    btb_reaches_match_2(Is, Regs, D);
-btb_reaches_match_2([{label,_}|Is], Regs, D) ->
-    btb_reaches_match_2(Is, Regs, D);
-btb_reaches_match_2([{bs_init,{f,0},_,_,Ss,Dst}=I|Is], Regs, D) ->
-    btb_ensure_not_used(Ss, I, Regs),
-    btb_reaches_match_1(Is, btb_kill([Dst], Regs), D);
-btb_reaches_match_2([{bs_put,{f,0},_,Ss}=I|Is], Regs, D) ->
-    btb_ensure_not_used(Ss, I, Regs),
-    btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([{bs_restore2,Src,_}=I|Is], Regs0, D) ->
-    case btb_contains_context(Src, Regs0) of
-	false ->
-	    btb_reaches_match_1(Is, Regs0, D);
-	true ->
-	    %% Check that all other copies of the context registers
-	    %% are unused by the following instructions.
-	    Regs = btb_kill([Src], Regs0),
-	    CtxRegs = btb_context_regs(Regs),
-	    case btb_are_all_unused(CtxRegs, Is, D) of
-		false -> btb_error({CtxRegs,not_all_unused_after,I});
-		true -> D#btb{must_not_save=true}
-	    end
-    end;
-btb_reaches_match_2([{bs_context_to_binary,Src}=I|Is], Regs0, D) ->
-    case btb_contains_context(Src, Regs0) of
-	false ->
-	    btb_reaches_match_1(Is, Regs0, D);
-	true ->
-	    %% Check that all other copies of the context registers
-	    %% are unused by the following instructions.
-	    Regs = btb_kill([Src], Regs0),
-	    CtxRegs = btb_context_regs(Regs),
-	    case btb_are_all_unused(CtxRegs, Is, D) of
-		false -> btb_error({CtxRegs,not_all_unused_after,I});
-		true -> D#btb{must_not_save=true}
-	    end
-    end;
-btb_reaches_match_2([{badmatch,Src}=I|_], Regs, D) ->
-    btb_ensure_not_used([Src], I, Regs),
-    D;
-btb_reaches_match_2([{case_end,Src}=I|_], Regs, D) ->
-    btb_ensure_not_used([Src], I, Regs),
-    D;
-btb_reaches_match_2([if_end|_], _Regs, D) ->
-    D;
-btb_reaches_match_2([{func_info,_,_,Arity}=I|_], Regs0, D) ->
-    Regs = btb_kill_yregs(btb_kill_not_live(Arity, Regs0)),
-    case btb_context_regs(Regs) of
-	[] -> D;
-	_ -> {binary_used_in,I}
-    end;
-btb_reaches_match_2([{line,_}|Is], Regs, D) ->
-    btb_reaches_match_1(Is, Regs, D);
-btb_reaches_match_2([I|_], Regs, _) ->
-    btb_error({btb_context_regs(Regs),I,not_handled}).
-
-is_tail_call([{deallocate,_}|_]) -> true;
-is_tail_call([return|_]) -> true;
-is_tail_call(_) -> false.
-
-btb_call(Arity, Lbl, Regs0, Is, D0) ->
-    Regs = btb_kill_not_live(Arity, Regs0),
-    case btb_are_x_registers_empty(Regs) of
-	false ->
-	    %% There is a match context in one of the x registers.
-	    %% First handle the call as if it were a tail call.
-	    D = btb_tail_call(Lbl, Regs, D0),
-
-	    %% No problem so far (the called function can handle a
-	    %% match context). Now we must make sure that we don't
-	    %% have any copies of the match context tucked away in an
-	    %% y register.
-	    RegList = btb_context_regs(Regs),
-	    case [R || {y,_}=R <- RegList] of
-		[] ->
-		    D;
-		[_|_] ->
-		    btb_error({multiple_uses,RegList})
-	    end;
-	true ->
-	    %% No match context in any x register. It could have been
-	    %% saved to an y register, so continue to scan the code following
-	    %% the call.
-	    btb_reaches_match_1(Is, Regs, D0)
-    end.
-
-btb_tail_call(Lbl, Regs, #btb{f=Ftree,must_save=MustSave0}=D) ->
-    %% Ignore any y registers here.
-    case [R || {x,_}=R <- btb_context_regs(Regs)] of
-	[] ->
-	    D;
-	[{x,_}=Reg] ->
-	    case gb_trees:lookup(Lbl, Ftree) of
-		{value,{Reg,MustSave}} ->
-		    D#btb{must_save=MustSave0 or MustSave};
-		_ when is_integer(Lbl) ->
-		    btb_error({{label,Lbl},no_suitable_bs_start_match});
-		_ ->
-		    btb_error({binary_used_in,Lbl})
-	    end;
-	[_|_] when not is_integer(Lbl) ->
-	    btb_error({binary_used_in,Lbl});
-	[_|_]=RegList ->
-	    btb_error({multiple_uses,RegList})
-    end.
-
-%% btb_follow_branches([Cond], Regs, D) -> D'
-%%  Recursively follow all the branches.
-
-btb_follow_branches([{f,Lbl}|T], Regs, D0) ->
-    D = btb_follow_branch(Lbl, Regs, D0),
-    btb_follow_branches(T, Regs, D);
-btb_follow_branches([_|T], Regs, D) ->
-    btb_follow_branches(T, Regs, D);
-btb_follow_branches([], _, D) -> D.
-
-%% btb_follow_branch(Lbl, Regs, D) -> D'
-%%  Recursively follow the branch.
-
-btb_follow_branch(0, _Regs, D) -> D;
-btb_follow_branch(Lbl, Regs, #btb{ok_br=Br0,index=Li}=D) ->
-    Key = {Lbl,Regs},
-    case gb_sets:is_member(Key, Br0) of
-	true ->
-	    %% We have already followed this branch and it was OK.
-	    D;
-	false ->
-	    %% New branch. Try it.
-	    Is = fetch_code_at(Lbl, Li),
-	    #btb{ok_br=Br,must_not_save=MustNotSave,must_save=MustSave} =
-		btb_reaches_match_1(Is, Regs, D),
-
-	    %% Since we got back, this branch is OK.
-	    D#btb{ok_br=gb_sets:insert(Key, Br),must_not_save=MustNotSave,
-		  must_save=MustSave}
-    end.
-
-btb_reaches_match_block([{set,Ds,Ss,{alloc,Live,_}}=I|Is], Regs0) ->
-    %% An allocation instruction or a GC bif. We'll kill all registers
-    %% if any copy of the context is used as the source to the BIF.
-    btb_ensure_not_used(Ss, I, Regs0),
-    Regs1 = btb_kill_not_live(Live, Regs0),
-    Regs = btb_kill(Ds, Regs1),
-    btb_reaches_match_block(Is, Regs);
-btb_reaches_match_block([{set,[Dst]=Ds,[Src],move}|Is], Regs0) ->
-    Regs1 = btb_kill(Ds, Regs0),
-    Regs = case btb_contains_context(Src, Regs1) of
-	       false -> Regs1;
-	       true -> btb_set_context(Dst, Regs1)
-	   end,
-    btb_reaches_match_block(Is, Regs);
-btb_reaches_match_block([{set,Ds,Ss,_}=I|Is], Regs0) ->
-    btb_ensure_not_used(Ss, I, Regs0),
-    Regs = btb_kill(Ds, Regs0),
-    btb_reaches_match_block(Is, Regs);
-btb_reaches_match_block([], Regs) ->
-    Regs.
-
-%% btb_are_all_killed([Register], [Instruction], D) -> true|false
-%%  Test whether all of the register are unused in the instruction stream.
-
-btb_are_all_unused(RegList, Is, #btb{index=Li}) ->
-    all(fun(R) ->
-		beam_utils:is_not_used(R, Is, Li)
-	end, RegList).
-
-%% btp_regs_from_list([Register]) -> RegisterSet.
-%%  Create a register set from a list of registers.
-
-btb_regs_from_list(L) ->
-    foldl(fun(R, Regs) ->
-		  btb_set_context(R, Regs)
-	  end, {0,0}, L).
-
-%% btb_set_context(Register, RegisterSet) -> RegisterSet'
-%%  Update RegisterSet to indicate that Register contains the matching context.
-
-btb_set_context({x,N}, {Xregs,Yregs}) ->
-    {Xregs bor (1 bsl N),Yregs};
-btb_set_context({y,N}, {Xregs,Yregs}) ->
-    {Xregs,Yregs bor (1 bsl N)}.
-
-%% btb_ensure_not_used([Register], Instruction, RegisterSet) -> ok
-%%  If any register in RegisterSet (the register(s) known to contain
-%%  the match context) is used in the list of registers, generate an error.
-
-btb_ensure_not_used(Rs, I, Regs) ->
-    case lists:any(fun(R) -> btb_contains_context(R, Regs) end, Rs) of
-	true -> btb_error({binary_used_in,I});
-	false -> ok
-    end.
-
-%% btb_kill([Register], RegisterSet) -> RegisterSet'
-%%  Kill all registers mentioned in the list of registers.
-
-btb_kill([{x,N}|Rs], {Xregs,Yregs}) ->
-    btb_kill(Rs, {Xregs band (bnot (1 bsl N)),Yregs});
-btb_kill([{y,N}|Rs], {Xregs,Yregs}) ->
-    btb_kill(Rs, {Xregs,Yregs band (bnot (1 bsl N))});
-btb_kill([{fr,_}|Rs], Regs) ->
-    btb_kill(Rs, Regs);
-btb_kill([], Regs) -> Regs.
-
-%% btb_kill_not_live(Live, RegisterSet) -> RegisterSet'
-%%  Kill all registers indicated not live by Live.
-
-btb_kill_not_live(Live, {Xregs,Yregs}) ->
-    {Xregs band ((1 bsl Live)-1),Yregs}.
-
-%% btb_kill(Regs0) -> Regs
-%%  Kill all y registers.
-
-btb_kill_yregs({Xregs,_}) -> {Xregs,0}.
-
-%% btb_are_registers_empty(RegisterSet) -> true|false
-%%  Test whether the register set is empty.
-
-btb_are_registers_empty({0,0}) -> true;
-btb_are_registers_empty({_,_}) -> false.
-
-%% btb_are_x_registers_empty(Regs) -> true|false
-%%  Test whether the x registers are empty.
-
-btb_are_x_registers_empty({0,_}) -> true;
-btb_are_x_registers_empty({_,_}) -> false.
-
-%% btb_contains_context(Register, RegisterSet) -> true|false
-%%  Test whether Register contains the context.
-
-btb_contains_context({x,N}, {Regs,_}) -> Regs band (1 bsl N) =/= 0;
-btb_contains_context({y,N}, {_,Regs}) -> Regs band (1 bsl N) =/= 0;
-btb_contains_context(_, _) -> false.
-
-%% btb_context_regs(RegisterSet) -> [Register]
-%%  Convert the register set to an explicit list of registers.
-btb_context_regs({Xregs,Yregs}) ->
-    btb_context_regs_1(Xregs, 0, x, btb_context_regs_1(Yregs, 0, y, [])).
-
-btb_context_regs_1(0, _, _, Acc) ->
-    Acc;
-btb_context_regs_1(Regs, N, Tag, Acc) when (Regs band 1) =:= 1 ->
-    btb_context_regs_1(Regs bsr 1, N+1, Tag, [{Tag,N}|Acc]);
-btb_context_regs_1(Regs, N, Tag, Acc) ->
-    btb_context_regs_1(Regs bsr 1, N+1, Tag, Acc).
-
-%% btb_index([Function]) -> GbTree({EntryLabel,{Register,MustSave}})
-%%  Build an index of functions that accept a match context instead of
-%%  a binary. MustSave is true if the function may pass the match
-%%  context to the bs_context_to_binary instruction (in which case
-%%  the current position in the binary must have saved into the
-%%  start position using "bs_save_2 Ctx start").
-
-btb_index(Fs) ->
-    btb_index_1(Fs, []).
-
-btb_index_1([{function,_,_,Entry,Is0}|Fs], Acc0) ->
-    Is = drop_to_label(Is0, Entry),
-    Acc = btb_index_2(Is, Entry, false, Acc0),
-    btb_index_1(Fs, Acc);
-btb_index_1([], Acc) -> gb_trees:from_orddict(sort(Acc)).
-
-btb_index_2([{test,bs_start_match2,{f,_},_,[Reg,_],Reg}|_],
-	    Entry, MustSave, Acc) ->
-    [{Entry,{Reg,MustSave}}|Acc];
-btb_index_2(Is0, Entry, _, Acc) ->
-    try btb_index_find_start_match(Is0) of
-	Is -> btb_index_2(Is, Entry, true, Acc)
-    catch
-	throw:none -> Acc
-    end.
-
-drop_to_label([{label,L}|Is], L) -> Is;
-drop_to_label([_|Is], L) -> drop_to_label(Is, L).
-
-btb_index_find_start_match([{test,_,{f,F},_},{bs_context_to_binary,_}|Is]) ->
-    btb_index_find_label(Is, F);
-btb_index_find_start_match(_) ->
-    throw(none).
-
-btb_index_find_label([{label,L}|Is], L) -> Is;
-btb_index_find_label([_|Is], L) -> btb_index_find_label(Is, L).
-
-btb_error(Error) ->
-    throw({error,Error}).
-
-fetch_code_at(Lbl, Li) ->
-    case beam_utils:code_at(Lbl, Li) of
-	Is when is_list(Is) -> Is
-    end.
-
-%%%
-%%% Compilation information warnings.
-%%%
-
-btb_comment_opt({field_flags,[{anno,A}|_]}) ->
-    {'%',{bin_opt,A}};
-btb_comment_opt(_) ->
-    {'%',{bin_opt,[]}}.
-
-btb_comment_no_opt(Reason, {field_flags,[{anno,A}|_]}) ->
-    {'%',{no_bin_opt,Reason,A}};
-btb_comment_no_opt(Reason, _) ->
-    {'%',{no_bin_opt,Reason,[]}}.
-
-collect_warnings(Fs) ->
-    D = warning_index_functions(Fs),
-    foldl(fun(F, A) -> collect_warnings_fun(F, D, A) end, [], Fs).
-
-collect_warnings_fun({function,_,_,_,Is}, D, A) ->
-    collect_warnings_instr(Is, D, A).
-
-collect_warnings_instr([{'%',{bin_opt,Where}}|Is], D, Acc0) ->
-    Acc = add_warning(bin_opt, Where, Acc0),
-    collect_warnings_instr(Is, D, Acc);
-collect_warnings_instr([{'%',{no_bin_opt,Reason0,Where}}|Is], D, Acc0) ->
-    Reason = warning_translate_label(Reason0, D),
-    Acc = add_warning({no_bin_opt,Reason}, Where, Acc0),
-    collect_warnings_instr(Is, D, Acc);
-collect_warnings_instr([_|Is], D, Acc) ->
-    collect_warnings_instr(Is, D, Acc);
-collect_warnings_instr([], _, Acc) -> Acc.
-
-add_warning(Term, Anno, Ws) ->
-    Line = get_line(Anno),
-    File = get_file(Anno),
-    [{File,[{Line,?MODULE,Term}]}|Ws].
-
-warning_translate_label(Term, D) when is_tuple(Term) ->
-    case element(1, Term) of
-	{label,F} ->
-	    FA = gb_trees:get(F, D),
-	    setelement(1, Term, FA);
-	_ -> Term
-    end;
-warning_translate_label(Term, _) -> Term.
-
-get_line([Line|_]) when is_integer(Line) -> Line;
-get_line([_|T]) -> get_line(T);
-get_line([]) -> none.
-    
-get_file([{file,File}|_]) -> File;
-get_file([_|T]) -> get_file(T);
-get_file([]) -> "no_file". % should not happen
-
-warning_index_functions(Fs) ->
-    D = [{Entry,{F,A}} || {function,F,A,Entry,_} <- Fs],
-    gb_trees:from_orddict(sort(D)).
-
-format_error_1({binary_used_in,{extfunc,M,F,A}}) ->
-    [io_lib:format("sub binary used by ~p:~p/~p", [M,F,A])|
-     case {M,F,A} of
-	 {erlang,split_binary,2} ->
-	     "; SUGGEST using binary matching instead of split_binary/2";
-	 _ ->
-	     ""
-     end];
-format_error_1({binary_used_in,_}) ->
-    "sub binary is used or returned";
-format_error_1({multiple_uses,_}) ->
-    "sub binary is matched or used in more than one place";
-format_error_1(unsuitable_bs_start_match) ->
-    "the binary matching instruction that follows in the same function "
-	"have problems that prevent delayed sub binary optimization "
-	"(probably indicated by INFO warnings)";
-format_error_1({{F,A},no_suitable_bs_start_match}) ->
-    io_lib:format("called function ~p/~p does not begin with a suitable "
-		  "binary matching instruction", [F,A]);
-format_error_1(must_and_must_not_save) ->
-    "different control paths use different positions in the binary";
-format_error_1({_,I,not_handled}) ->
-    case I of
-	{'catch',_,_} ->
-	    "the compiler currently does not attempt the delayed sub binary "
-		"optimization when catch is used";
-	{'try',_,_} ->
-	    "the compiler currently does not attempt the delayed sub binary "
-		"optimization when try/catch is used";
-	_ ->
-	    io_lib:format("compiler limitation: instruction ~p prevents "
-			  "delayed sub binary optimization", [I])
-    end;
-format_error_1(Term) ->
-    io_lib:format("~w", [Term]).
diff --git a/lib/compiler/src/beam_disasm.erl b/lib/compiler/src/beam_disasm.erl
index d0be39f520..7d048716e4 100644
--- a/lib/compiler/src/beam_disasm.erl
+++ b/lib/compiler/src/beam_disasm.erl
@@ -1105,6 +1105,16 @@ resolve_inst({get_hd,[Src,Dst]},_,_,_) ->
 resolve_inst({get_tl,[Src,Dst]},_,_,_) ->
     {get_tl,Src,Dst};
 
+%% OTP 22
+resolve_inst({bs_start_match3,[Fail,Bin,Live,Dst]},_,_,_) ->
+    {bs_start_match3,Fail,Bin,Live,Dst};
+resolve_inst({bs_get_tail,[Src,Dst,Live]},_,_,_) ->
+    {bs_get_tail,Src,Dst,Live};
+resolve_inst({bs_get_position,[Src,Dst,Live]},_,_,_) ->
+    {bs_get_position,Src,Dst,Live};
+resolve_inst({bs_set_position,[Src,Dst]},_,_,_) ->
+    {bs_set_position,Src,Dst};
+
 %%
 %% OTP 22.
 %%
diff --git a/lib/compiler/src/beam_ssa_bsm.erl b/lib/compiler/src/beam_ssa_bsm.erl
new file mode 100644
index 0000000000..2efeb6b5b6
--- /dev/null
+++ b/lib/compiler/src/beam_ssa_bsm.erl
@@ -0,0 +1,1027 @@
+%%
+%% %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%
+%%
+
+%%%
+%%% This pass optimizes bit syntax matching, and is centered around the concept
+%%% of "match context reuse" which is best explained through example. To put it
+%%% shortly we attempt to turn this:
+%%%
+%%%    <<0,B/bits>> = A,
+%%%    <<1,C/bits>> = B,
+%%%    <<D,_/bits>> = C,
+%%%    D.
+%%%
+%%% ... Into this:
+%%%
+%%%    <<0,1,D,_/bits>>=A,
+%%%    D.
+%%%
+%%% Which is much faster as it avoids the creation of intermediate terms. This
+%%% is especially noticeable in loops where such garbage is generated on each
+%%% iteration.
+%%%
+%%% The optimization itself is very simple and can be applied whenever there's
+%%% matching on the tail end of a binary; instead of creating a new binary and
+%%% starting a new match context on it, we reuse the match context used to
+%%% extract the tail and avoid the creation of both objects.
+%%%
+%%% The catch is that a match context isn't a proper type and nothing outside
+%%% of bit syntax match operations can handle them. We therefore need to make
+%%% sure that they never "leak" into other instructions, and most of the pass
+%%% revolves around getting around that limitation.
+%%%
+%%% Unlike most other passes we look at the whole module so we can combine
+%%% matches across function boundaries, greatly increasing the performance of
+%%% complex matches and loops.
+%%%
+
+-module(beam_ssa_bsm).
+
+-export([module/2, format_error/1]).
+
+-include("beam_ssa.hrl").
+
+-import(lists, [member/2, reverse/1, splitwith/2, map/2, foldl/3, mapfoldl/3,
+                nth/2, max/1, unzip/1]).
+
+-spec format_error(term()) -> nonempty_string().
+
+format_error(OptInfo) ->
+    format_opt_info(OptInfo).
+
+-spec module(Module, Options) -> Result when
+      Module :: beam_ssa:b_module(),
+      Options :: [compile:option()],
+      Result :: {ok, beam_ssa:b_module(), list()}.
+
+-define(PASS(N), {N,fun N/1}).
+
+module(#b_module{body=Fs0}=Module, Opts) ->
+    ModInfo = analyze_module(Module),
+
+    %% combine_matches is repeated after accept_context_args as the control
+    %% flow changes can enable further optimizations, as in the example below:
+    %%
+    %%    a(<<0,X/binary>>) -> a(X);
+    %%    a(A) when bit_size(A) =:= 52 -> bar;
+    %%    a(<<1,X/binary>>) -> X. %% Match context will be reused here when
+    %%                            %% when repeated.
+
+    {Fs, _} = compile:run_sub_passes(
+                [?PASS(combine_matches),
+                 ?PASS(accept_context_args),
+                 ?PASS(combine_matches),
+                 ?PASS(allow_context_passthrough),
+                 ?PASS(skip_outgoing_tail_extraction),
+                 ?PASS(annotate_context_parameters)],
+                {Fs0, ModInfo}),
+
+    Ws = case proplists:get_bool(bin_opt_info, Opts) of
+             true -> collect_opt_info(Fs);
+             false -> []
+         end,
+
+    {ok, Module#b_module{body=Fs}, Ws}.
+
+-type module_info() :: #{ func_id() => func_info() }.
+
+-type func_id() :: {Name :: atom(), Arity :: non_neg_integer()}.
+
+-type func_info() :: #{ has_bsm_ops => boolean(),
+                        parameters => [#b_var{}],
+                        parameter_info => #{ #b_var{} => param_info() } }.
+
+-type param_info() :: suitable_for_reuse |
+                      {Problem :: atom(), Where :: term()}.
+
+-spec analyze_module(#b_module{}) -> module_info().
+
+analyze_module(#b_module{body=Fs}) ->
+    foldl(fun(#b_function{args=Parameters}=F, I) ->
+                  FuncInfo = #{ has_bsm_ops => has_bsm_ops(F),
+                                parameters => Parameters,
+                                parameter_info => #{} },
+                  FuncId = get_fa(F),
+                  I#{ FuncId => FuncInfo }
+          end, #{}, Fs).
+
+has_bsm_ops(#b_function{bs=Blocks}) ->
+    hbo_blocks(maps:to_list(Blocks)).
+
+hbo_blocks([{_,#b_blk{is=Is}} | Blocks]) ->
+    case hbo_is(Is) of
+        false -> hbo_blocks(Blocks);
+        true -> true
+    end;
+hbo_blocks([]) ->
+    false.
+
+hbo_is([#b_set{op=bs_start_match} | _]) -> true;
+hbo_is([_I | Is]) -> hbo_is(Is);
+hbo_is([]) -> false.
+
+%% Checks whether it's legal to make a call with the given argument as a match
+%% context, returning the param_info() of the relevant parameter.
+-spec check_context_call(#b_set{}, Arg, CtxChain, ModInfo) -> param_info() when
+      Arg :: #b_var{},
+      CtxChain :: [#b_var{}],
+      ModInfo :: module_info().
+check_context_call(#b_set{args=Args}, Arg, CtxChain, ModInfo) ->
+    Aliases = [Arg | CtxChain],
+    ccc_1(Args, Arg, Aliases, ModInfo).
+
+ccc_1([#b_local{}=Call | Args], Ctx, Aliases, ModInfo) ->
+    %% Matching operations assume that their context isn't aliased (as in
+    %% pointer aliasing), so we must reject calls whose arguments contain more
+    %% than one reference to the context.
+    %%
+    %% TODO: Try to fall back to passing binaries in these cases. Partial reuse
+    %% is better than nothing.
+    UseCount = foldl(fun(Arg, C) ->
+                             case member(Arg, Aliases) of
+                                 true -> C + 1;
+                                 false -> C
+                             end
+                     end, 0, Args),
+    if
+        UseCount =:= 1 ->
+            #b_local{name=#b_literal{val=Name},arity=Arity} = Call,
+            Callee = {Name, Arity},
+
+            ParamInfo = funcinfo_get(Callee, parameter_info, ModInfo),
+            Parameters = funcinfo_get(Callee, parameters, ModInfo),
+            Parameter = nth(1 + arg_index(Ctx, Args), Parameters),
+
+            case maps:find(Parameter, ParamInfo) of
+                {ok, suitable_for_reuse} ->
+                    suitable_for_reuse;
+                {ok, Other} ->
+                    {unsuitable_call, {Call, Other}};
+                error ->
+                    {no_match_on_entry, Call}
+            end;
+        UseCount > 1 ->
+            {multiple_uses_in_call, Call}
+    end;
+ccc_1([#b_remote{}=Call | _Args], _Ctx, _CtxChain, _ModInfo) ->
+    {remote_call, Call};
+ccc_1([Fun | _Args], _Ctx, _CtxChain, _ModInfo) ->
+    %% TODO: It may be possible to support this in the future for locally
+    %% defined funs, including ones with free variables.
+    {fun_call, Fun}.
+
+%% Returns the index of Var in Args.
+arg_index(Var, Args) -> arg_index_1(Var, Args, 0).
+
+arg_index_1(Var, [Var | _Args], Index) -> Index;
+arg_index_1(Var, [_Arg | Args], Index) -> arg_index_1(Var, Args, Index + 1).
+
+is_tail_binary(#b_set{op=bs_match,args=[#b_literal{val=binary} | Rest]}) ->
+    member(#b_literal{val=all}, Rest);
+is_tail_binary(#b_set{op=bs_get_tail}) ->
+    true;
+is_tail_binary(_) ->
+    false.
+
+is_tail_binary(#b_var{}=Var, Defs) ->
+    case find_match_definition(Var, Defs) of
+        {ok, Def} -> is_tail_binary(Def);
+        _ -> false
+    end;
+is_tail_binary(_Literal, _Defs) ->
+    false.
+
+assert_match_context(#b_var{}=Var, Defs) ->
+    case maps:find(Var, Defs) of
+        {ok, #b_set{op=bs_match,args=[_,#b_var{}=Ctx|_]}} ->
+            assert_match_context(Ctx, Defs);
+        {ok, #b_set{op=bs_start_match}} ->
+            ok
+    end.
+
+find_match_definition(#b_var{}=Var, Defs) ->
+    case maps:find(Var, Defs) of
+        {ok, #b_set{op=bs_extract,args=[Ctx]}} -> maps:find(Ctx, Defs);
+        {ok, #b_set{op=bs_get_tail}=Def} -> {ok, Def};
+        _ -> error
+    end.
+
+%% Returns a list of all contexts that were used to extract Var.
+context_chain_of(#b_var{}=Var, Defs) ->
+    case maps:find(Var, Defs) of
+        {ok, #b_set{op=bs_match,args=[_,#b_var{}=Ctx|_]}} ->
+            [Ctx | context_chain_of(Ctx, Defs)];
+        {ok, #b_set{op=bs_get_tail,args=[Ctx]}} ->
+            [Ctx | context_chain_of(Ctx, Defs)];
+        {ok, #b_set{op=bs_extract,args=[Ctx]}} ->
+            [Ctx | context_chain_of(Ctx, Defs)];
+        _ ->
+            []
+    end.
+
+%% Grabs the match context used to produce the given variable.
+match_context_of(#b_var{}=Var, Defs) ->
+    Ctx = match_context_of_1(Var, Defs),
+    assert_match_context(Ctx, Defs),
+    Ctx.
+
+match_context_of_1(Var, Defs) ->
+    case maps:get(Var, Defs) of
+        #b_set{op=bs_extract,args=[#b_var{}=Ctx0]} ->
+            #b_set{op=bs_match,
+                   args=[_,#b_var{}=Ctx|_]} = maps:get(Ctx0, Defs),
+            Ctx;
+        #b_set{op=bs_get_tail,args=[#b_var{}=Ctx]} ->
+            Ctx
+    end.
+
+funcinfo_get(#b_function{}=F, Attribute, ModInfo) ->
+    funcinfo_get(get_fa(F), Attribute, ModInfo);
+funcinfo_get({_,_}=Key, Attribute, ModInfo) ->
+    FuncInfo = maps:get(Key, ModInfo),
+    maps:get(Attribute, FuncInfo).
+
+funcinfo_set(#b_function{}=F, Attribute, Value, ModInfo) ->
+    funcinfo_set(get_fa(F), Attribute, Value, ModInfo);
+funcinfo_set(Key, Attribute, Value, ModInfo) ->
+    FuncInfo = maps:put(Attribute, Value, maps:get(Key, ModInfo, #{})),
+    maps:put(Key, FuncInfo, ModInfo).
+
+get_fa(#b_function{ anno = Anno }) ->
+    {_,Name,Arity} = maps:get(func_info, Anno),
+    {Name,Arity}.
+
+%% Replaces matched-out binaries with aliases that are lazily converted to
+%% binary form when used, allowing us to keep the "match path" free of binary
+%% creation.
+
+-spec alias_matched_binaries(Blocks, Counter, AliasMap) -> Result when
+      Blocks :: beam_ssa:block_map(),
+      Counter :: non_neg_integer(),
+      AliasMap :: match_alias_map(),
+      Result :: {Blocks, Counter}.
+
+-type match_alias_map() ::
+        #{ Binary :: #b_var{} =>
+                     { %% Replace all uses of Binary with an alias after this
+                       %% label.
+                       AliasAfter :: beam_ssa:label(),
+                       %% The match context whose tail is equal to Binary.
+                       Context :: #b_var{} } }.
+
+%% Keeps track of the promotions we need to insert. They're partially keyed by
+%% location because they may not be valid on all execution paths and we may
+%% need to add redundant promotions in some cases.
+-type promotion_map() ::
+        #{ { PromoteAt :: beam_ssa:label(),
+             Variable :: #b_var{} } =>
+               Instruction :: #b_set{} }.
+
+-record(amb, { dominators :: beam_ssa:dominator_map(),
+               match_aliases :: match_alias_map(),
+               cnt :: non_neg_integer(),
+               promotions = #{} :: promotion_map() }).
+
+alias_matched_binaries(Blocks0, Counter, AliasMap) when AliasMap =/= #{} ->
+    State0 = #amb{ dominators = beam_ssa:dominators(Blocks0),
+                   match_aliases = AliasMap,
+                   cnt = Counter },
+    {Blocks, State} = beam_ssa:mapfold_blocks_rpo(fun amb_1/3, [0], State0,
+                                                  Blocks0),
+    {amb_insert_promotions(Blocks, State), State#amb.cnt};
+alias_matched_binaries(Blocks, Counter, _AliasMap) ->
+    {Blocks, Counter}.
+
+amb_1(Lbl, #b_blk{is=Is0,last=Last0}=Block, State0) ->
+    {Is, State1} = mapfoldl(fun(I, State) ->
+                                    amb_assign_set(I, Lbl, State)
+                            end, State0, Is0),
+    {Last, State} = amb_assign_last(Last0, Lbl, State1),
+    {Block#b_blk{is=Is,last=Last}, State}.
+
+amb_assign_set(#b_set{op=phi,args=Args0}=I, _Lbl, State0) ->
+    %% Phi node aliases are relative to their source block, not their
+    %% containing block.
+    {Args, State} =
+        mapfoldl(fun({Arg0, Lbl}, Acc) ->
+                         {Arg, State} = amb_get_alias(Arg0, Lbl, Acc),
+                         {{Arg, Lbl}, State}
+                 end, State0, Args0),
+    {I#b_set{args=Args}, State};
+amb_assign_set(#b_set{args=Args0}=I, Lbl, State0) ->
+    {Args, State} = mapfoldl(fun(Arg0, Acc) ->
+                                     amb_get_alias(Arg0, Lbl, Acc)
+                             end, State0, Args0),
+    {I#b_set{args=Args}, State}.
+
+amb_assign_last(#b_ret{arg=Arg0}=T, Lbl, State0) ->
+    {Arg, State} = amb_get_alias(Arg0, Lbl, State0),
+    {T#b_ret{arg=Arg}, State};
+amb_assign_last(#b_switch{arg=Arg0}=T, Lbl, State0) ->
+    {Arg, State} = amb_get_alias(Arg0, Lbl, State0),
+    {T#b_switch{arg=Arg}, State};
+amb_assign_last(#b_br{bool=Arg0}=T, Lbl, State0) ->
+    {Arg, State} = amb_get_alias(Arg0, Lbl, State0),
+    {T#b_br{bool=Arg}, State}.
+
+amb_get_alias(#b_var{}=Arg, Lbl, State) ->
+    case maps:find(Arg, State#amb.match_aliases) of
+        {ok, {AliasAfter, Context}} ->
+            %% Our context may not have been created yet, so we skip assigning
+            %% an alias unless the given block is among our dominators.
+            Dominators = maps:get(Lbl, State#amb.dominators),
+            case ordsets:is_element(AliasAfter, Dominators) of
+                true -> amb_create_alias(Arg, Context, Lbl, State);
+                false -> {Arg, State}
+            end;
+        error ->
+            {Arg, State}
+    end;
+amb_get_alias(Arg, _Lbl, State) ->
+    {Arg, State}.
+
+amb_create_alias(#b_var{}=Arg0, Context, Lbl, State0) ->
+    Dominators = maps:get(Lbl, State0#amb.dominators),
+    Promotions0 = State0#amb.promotions,
+
+    PrevPromotions =
+        [maps:get({Dom, Arg0}, Promotions0)
+         || Dom <- Dominators, is_map_key({Dom, Arg0}, Promotions0)],
+
+    case PrevPromotions of
+        [_|_] ->
+            %% We've already created an alias prior to this block, so we'll
+            %% grab the most recent one to minimize stack use.
+
+            #b_set{dst=Alias} = max(PrevPromotions),
+            {Alias, State0};
+        [] ->
+            %% If we haven't created an alias we need to do so now. The
+            %% promotion will be inserted later by amb_insert_promotions/2.
+
+            Counter = State0#amb.cnt,
+            Alias = #b_var{name={'@ssa_bsm_alias', Counter}},
+            Promotion = #b_set{op=bs_get_tail,dst=Alias,args=[Context]},
+
+            Promotions = maps:put({Lbl, Arg0}, Promotion, Promotions0),
+            State = State0#amb{ promotions=Promotions, cnt=Counter+1 },
+
+            {Alias, State}
+    end.
+
+amb_insert_promotions(Blocks0, State) ->
+    F = fun({Lbl, #b_var{}}, Promotion, Blocks) ->
+                Block = maps:get(Lbl, Blocks),
+
+                Alias = Promotion#b_set.dst,
+                {Before, After} = splitwith(fun(#b_set{args=Args}) ->
+                                                    not member(Alias, Args)
+                                            end, Block#b_blk.is),
+                Is = Before ++ [Promotion | After],
+
+                maps:put(Lbl, Block#b_blk{is=Is}, Blocks)
+        end,
+    maps:fold(F, Blocks0, State#amb.promotions).
+
+%%%
+%%% Subpasses
+%%%
+
+%% Removes superflous chained bs_start_match instructions in the same
+%% function. When matching on an extracted tail binary, or on a binary we've
+%% already matched on, we reuse the original match context.
+%%
+%% This pass runs first since it makes subsequent optimizations more effective
+%% by removing spots where promotion would be required.
+
+-type prior_match_map() ::
+        #{ Binary :: #b_var{} =>
+                     [{ %% The context and success label of a previous
+                        %% bs_start_match made on this binary.
+                        ValidAfter :: beam_ssa:label(),
+                        Context :: #b_var{} }] }.
+
+-record(cm, { definitions :: beam_ssa:definition_map(),
+              dominators :: beam_ssa:dominator_map(),
+              blocks :: beam_ssa:block_map(),
+              match_aliases = #{} :: match_alias_map(),
+              prior_matches = #{} :: prior_match_map(),
+              renames = #{} :: beam_ssa:rename_map() }).
+
+combine_matches({Fs0, ModInfo}) ->
+    Fs = map(fun(F) -> combine_matches(F, ModInfo) end, Fs0),
+    {Fs, ModInfo}.
+
+combine_matches(#b_function{bs=Blocks0,cnt=Counter0}=F, ModInfo) ->
+    case funcinfo_get(F, has_bsm_ops, ModInfo) of
+        true ->
+            {Blocks1, State} =
+                beam_ssa:mapfold_blocks_rpo(
+                  fun(Lbl, #b_blk{is=Is0}=Block0, State0) ->
+                          {Is, State} = cm_1(Is0, [], Lbl, State0),
+                          {Block0#b_blk{is=Is}, State}
+                  end, [0],
+                  #cm{ definitions = beam_ssa:definitions(Blocks0),
+                       dominators = beam_ssa:dominators(Blocks0),
+                       blocks = Blocks0 },
+                  Blocks0),
+
+            Blocks2 = beam_ssa:rename_vars(State#cm.renames, [0], Blocks1),
+
+            {Blocks, Counter} = alias_matched_binaries(Blocks2, Counter0,
+                                                       State#cm.match_aliases),
+
+            F#b_function{ bs=Blocks, cnt=Counter };
+        false ->
+            F
+    end.
+
+cm_1([#b_set{ op=bs_start_match,
+              dst=Ctx,
+              args=[Src] },
+      #b_set{ op=succeeded,
+              dst=Bool,
+              args=[Ctx] }]=MatchSeq, Acc0, Lbl, State0) ->
+    Acc = reverse(Acc0),
+    case is_tail_binary(Src, State0#cm.definitions) of
+        true -> cm_combine_tail(Src, Ctx, Bool, Acc, State0);
+        false -> cm_handle_priors(Src, Ctx, Bool, Acc, MatchSeq, Lbl, State0)
+    end;
+cm_1([I | Is], Acc, Lbl, State) ->
+    cm_1(Is, [I | Acc], Lbl, State);
+cm_1([], Acc, _Lbl, State) ->
+    {reverse(Acc), State}.
+
+%% If we're dominated by at least one match on the same source, we can reuse
+%% the context created by that match.
+cm_handle_priors(Src, DstCtx, Bool, Acc, MatchSeq, Lbl, State0) ->
+    PriorCtxs = case maps:find(Src, State0#cm.prior_matches) of
+                    {ok, Priors} ->
+                        %% We've seen other match contexts on this source, but
+                        %% we can only consider the ones whose success path
+                        %% dominate us.
+                        Dominators = maps:get(Lbl, State0#cm.dominators, []),
+                        [Ctx || {ValidAfter, Ctx} <- Priors,
+                                ordsets:is_element(ValidAfter, Dominators)];
+                    error ->
+                        []
+                end,
+    case PriorCtxs of
+        [Ctx|_] ->
+            Renames0 = State0#cm.renames,
+            Renames = Renames0#{ Bool => #b_literal{val=true}, DstCtx => Ctx },
+            {Acc, State0#cm{ renames = Renames }};
+        [] ->
+            %% Since we lack a prior match, we need to register this one in
+            %% case we dominate another.
+            State = cm_register_prior(Src, DstCtx, Lbl, State0),
+            {Acc ++ MatchSeq, State}
+    end.
+
+cm_register_prior(Src, DstCtx, Lbl, State) ->
+    Block = maps:get(Lbl, State#cm.blocks),
+    #b_br{succ=ValidAfter} = Block#b_blk.last,
+
+    Priors0 = maps:get(Src, State#cm.prior_matches, []),
+    Priors = [{ValidAfter, DstCtx} | Priors0],
+
+    PriorMatches = maps:put(Src, Priors, State#cm.prior_matches),
+    State#cm{ prior_matches = PriorMatches }.
+
+cm_combine_tail(Src, DstCtx, Bool, Acc, State0) ->
+    SrcCtx = match_context_of(Src, State0#cm.definitions),
+
+    %% We replace the source with a context alias as it normally won't be used
+    %% on the happy path after being matched, and the added cost of conversion
+    %% is negligible if it is.
+    Aliases = maps:put(Src, {0, SrcCtx}, State0#cm.match_aliases),
+
+    Renames0 = State0#cm.renames,
+    Renames = Renames0#{ Bool => #b_literal{val=true}, DstCtx => SrcCtx },
+
+    State = State0#cm{ match_aliases = Aliases, renames = Renames },
+
+    {Acc, State}.
+
+%% Lets functions accept match contexts as arguments. The parameter must be
+%% unused before the bs_start_match instruction, and it must be matched in the
+%% first block.
+
+-record(aca, { unused_parameters :: ordsets:ordset(#b_var{}),
+               counter :: non_neg_integer(),
+               parameter_info = #{} :: #{ #b_var{} => param_info() },
+               match_aliases = #{} :: match_alias_map() }).
+
+accept_context_args({Fs, ModInfo}) ->
+    mapfoldl(fun accept_context_args/2, ModInfo, Fs).
+
+accept_context_args(#b_function{bs=Blocks0}=F, ModInfo0) ->
+    case funcinfo_get(F, has_bsm_ops, ModInfo0) of
+        true ->
+            Parameters = ordsets:from_list(funcinfo_get(F, parameters, ModInfo0)),
+            State0 = #aca{ unused_parameters = Parameters,
+                           counter = F#b_function.cnt },
+
+            {Blocks1, State} = aca_1(Blocks0, State0),
+            {Blocks, Counter} = alias_matched_binaries(Blocks1,
+                                                       State#aca.counter,
+                                                       State#aca.match_aliases),
+
+            ModInfo = funcinfo_set(F, parameter_info, State#aca.parameter_info,
+                                   ModInfo0),
+
+            {F#b_function{bs=Blocks,cnt=Counter}, ModInfo};
+        false ->
+            {F, ModInfo0}
+    end.
+
+aca_1(Blocks, State) ->
+    %% We only handle block 0 as we don't yet support starting a match after a
+    %% test. This is generally good enough as the sys_core_bsm pass makes the
+    %% match instruction come first if possible, and it's rare for a function
+    %% to binary-match several parameters at once.
+    EntryBlock = maps:get(0, Blocks),
+    aca_enable_reuse(EntryBlock#b_blk.is, EntryBlock, Blocks, [], State).
+
+aca_enable_reuse([#b_set{op=bs_start_match,args=[Src]}=I0 | Rest],
+                 EntryBlock, Blocks0, Acc, State0) ->
+    case aca_is_reuse_safe(Src, State0) of
+        true ->
+            {I, Last, Blocks1, State} =
+                aca_reuse_context(I0, EntryBlock, Blocks0, State0),
+
+            Is = reverse([I|Acc]) ++ Rest,
+            Blocks = maps:put(0, EntryBlock#b_blk{is=Is,last=Last}, Blocks1),
+
+            {Blocks, State};
+        false ->
+            {Blocks0, State0}
+    end;
+aca_enable_reuse([I | Is], EntryBlock, Blocks, Acc, State0) ->
+    UnusedParams0 = State0#aca.unused_parameters,
+    case ordsets:intersection(UnusedParams0, beam_ssa:used(I)) of
+        [] ->
+            aca_enable_reuse(Is, EntryBlock, Blocks, [I | Acc], State0);
+        PrematureUses ->
+            UnusedParams = ordsets:subtract(UnusedParams0, PrematureUses),
+
+            %% Mark the offending parameters as unsuitable for context reuse.
+            ParamInfo = foldl(fun(A, Ps) ->
+                                      maps:put(A, {used_before_match, I}, Ps)
+                              end, State0#aca.parameter_info, PrematureUses),
+
+            State = State0#aca{ unused_parameters = UnusedParams,
+                                parameter_info = ParamInfo },
+            aca_enable_reuse(Is, EntryBlock, Blocks, [I | Acc], State)
+    end;
+aca_enable_reuse([], _EntryBlock, Blocks, _Acc, State) ->
+    {Blocks, State}.
+
+aca_is_reuse_safe(Src, State) ->
+    %% Context reuse is unsafe unless all uses are dominated by the start_match
+    %% instruction. Since we only process block 0 it's enough to check if
+    %% they're unused so far.
+    ordsets:is_element(Src, State#aca.unused_parameters).
+
+aca_reuse_context(#b_set{dst=Dst, args=[Src]}=I0, Block, Blocks0, State0) ->
+    %% When matching fails on a reused context it needs to be converted back
+    %% to a binary. We only need to do this on the success path since it can't
+    %% be a context on the type failure path, but it's very common for these
+    %% to converge which requires special handling.
+    {State1, Last, Blocks} =
+        aca_handle_convergence(Src, State0, Block#b_blk.last, Blocks0),
+
+    Aliases = maps:put(Src, {Last#b_br.succ, Dst}, State1#aca.match_aliases),
+    ParamInfo = maps:put(Src, suitable_for_reuse, State1#aca.parameter_info),
+
+    State = State1#aca{ match_aliases = Aliases,
+                        parameter_info = ParamInfo },
+
+    I = beam_ssa:add_anno(accepts_match_contexts, true, I0),
+
+    {I, Last, Blocks, State}.
+
+aca_handle_convergence(Src, State0, Last0, Blocks0) ->
+    #b_br{fail=Fail0,succ=Succ0} = Last0,
+
+    SuccPath = beam_ssa:rpo([Succ0], Blocks0),
+    FailPath = beam_ssa:rpo([Fail0], Blocks0),
+
+    %% The promotion logic in alias_matched_binaries breaks down if the source
+    %% is used after the fail/success paths converge, as we have no way to tell
+    %% whether the source is a match context or something else past that point.
+    %%
+    %% We could handle this through clever insertion of phi nodes but it's
+    %% far simpler to copy either branch in its entirety. It doesn't matter
+    %% which one as long as they become disjoint.
+    ConvergedPaths = ordsets:intersection(
+                       ordsets:from_list(SuccPath),
+                       ordsets:from_list(FailPath)),
+
+    case maps:is_key(Src, beam_ssa:uses(ConvergedPaths, Blocks0)) of
+        true ->
+            case shortest(SuccPath, FailPath) of
+                left ->
+                    {Succ, Blocks, Counter} =
+                        aca_copy_successors(Succ0, Blocks0, State0#aca.counter),
+                    State = State0#aca{ counter = Counter },
+                    {State, Last0#b_br{succ=Succ}, Blocks};
+                right ->
+                    {Fail, Blocks, Counter} =
+                        aca_copy_successors(Fail0, Blocks0, State0#aca.counter),
+                    State = State0#aca{ counter = Counter },
+                    {State, Last0#b_br{fail=Fail}, Blocks}
+            end;
+        false ->
+            {State0, Last0, Blocks0}
+    end.
+
+shortest([_|As], [_|Bs]) -> shortest(As, Bs);
+shortest([], _) -> left;
+shortest(_, []) -> right.
+
+%% Copies all successor blocks of Lbl, returning the label to the entry block
+%% of this copy. Since the copied blocks aren't referenced anywhere else, they
+%% are all guaranteed to be dominated by Lbl.
+aca_copy_successors(Lbl0, Blocks0, Counter0) ->
+    %% Building the block rename map up front greatly simplifies phi node
+    %% handling.
+    Path = beam_ssa:rpo([Lbl0], Blocks0),
+    {BRs, Counter1} = aca_cs_build_brs(Path, Counter0, #{}),
+    {Blocks, Counter} = aca_cs_1(Path, Blocks0, Counter1, #{}, BRs, #{}),
+    Lbl = maps:get(Lbl0, BRs),
+    {Lbl, Blocks, Counter}.
+
+aca_cs_build_brs([Lbl | Path], Counter0, Acc) ->
+    aca_cs_build_brs(Path, Counter0 + 1, maps:put(Lbl, Counter0, Acc));
+aca_cs_build_brs([], Counter, Acc) ->
+    {Acc, Counter}.
+
+aca_cs_1([Lbl0 | Path], Blocks, Counter0, VRs0, BRs, Acc0) ->
+    Block0 = maps:get(Lbl0, Blocks),
+    Lbl = maps:get(Lbl0, BRs),
+    {VRs, Block, Counter} = aca_cs_block(Block0, Counter0, VRs0, BRs),
+    Acc = maps:put(Lbl, Block, Acc0),
+    aca_cs_1(Path, Blocks, Counter, VRs, BRs, Acc);
+aca_cs_1([], Blocks, Counter, _VRs, _BRs, Acc) ->
+    {maps:merge(Blocks, Acc), Counter}.
+
+aca_cs_block(#b_blk{is=Is0,last=Last0}=Block0, Counter0, VRs0, BRs) ->
+    {VRs, Is, Counter} = aca_cs_is(Is0, Counter0, VRs0, BRs, []),
+    Last = aca_cs_last(Last0, VRs, BRs),
+    Block = Block0#b_blk{is=Is,last=Last},
+    {VRs, Block, Counter}.
+
+aca_cs_is([#b_set{op=Op,
+                  dst=Dst0,
+                  args=Args0}=I0 | Is],
+          Counter0, VRs0, BRs, Acc) ->
+    Args = case Op of
+               phi -> aca_cs_args_phi(Args0, VRs0, BRs);
+               _ -> aca_cs_args(Args0, VRs0)
+           end,
+    Counter = Counter0 + 1,
+    Dst = #b_var{name={'@ssa_bsm_aca',Counter}},
+    I = I0#b_set{dst=Dst,args=Args},
+    VRs = maps:put(Dst0, Dst, VRs0),
+    aca_cs_is(Is, Counter, VRs, BRs, [I | Acc]);
+aca_cs_is([], Counter, VRs, _BRs, Acc) ->
+    {VRs, reverse(Acc), Counter}.
+
+aca_cs_last(#b_switch{arg=Arg0,list=Switch0,fail=Fail0}=Sw, VRs, BRs) ->
+    Switch = [{Literal, maps:get(Lbl, BRs)} || {Literal, Lbl} <- Switch0],
+    Sw#b_switch{arg=aca_cs_arg(Arg0, VRs),
+                fail=maps:get(Fail0, BRs),
+                list=Switch};
+aca_cs_last(#b_br{bool=Arg0,succ=Succ0,fail=Fail0}=Br, VRs, BRs) ->
+    Br#b_br{bool=aca_cs_arg(Arg0, VRs),
+            succ=maps:get(Succ0, BRs),
+            fail=maps:get(Fail0, BRs)};
+aca_cs_last(#b_ret{arg=Arg0}=Ret, VRs, _BRs) ->
+    Ret#b_ret{arg=aca_cs_arg(Arg0, VRs)}.
+
+aca_cs_args_phi([{Arg, Lbl} | Args], VRs, BRs) ->
+    case BRs of
+        #{ Lbl := New } ->
+            [{aca_cs_arg(Arg, VRs), New} | aca_cs_args_phi(Args, VRs, BRs)];
+        #{} ->
+            aca_cs_args_phi(Args, VRs, BRs)
+    end;
+aca_cs_args_phi([], _VRs, _BRs) ->
+    [].
+
+aca_cs_args([Arg | Args], VRs) ->
+    [aca_cs_arg(Arg, VRs) | aca_cs_args(Args, VRs)];
+aca_cs_args([], _VRs) ->
+    [].
+
+aca_cs_arg(Arg, VRs) ->
+    case VRs of
+        #{ Arg := New } -> New;
+        #{} -> Arg
+    end.
+
+%% Allows contexts to pass through "wrapper functions" where the context is
+%% passed directly to a function that accepts match contexts (including other
+%% wrappers).
+%%
+%% This does not alter the function in any way, it only changes parameter info
+%% so that skip_outgoing_tail_extraction is aware that it's safe to pass
+%% contexts to us.
+
+allow_context_passthrough({Fs, ModInfo0}) ->
+    ModInfo =
+        acp_forward_params([{F, beam_ssa:uses(F#b_function.bs)} || F <- Fs],
+                           ModInfo0),
+    {Fs, ModInfo}.
+
+acp_forward_params(FsUses, ModInfo0) ->
+    F = fun({#b_function{args=Parameters}=Func, UseMap}, ModInfo) ->
+                ParamInfo =
+                    foldl(fun(Param, ParamInfo) ->
+                                  Uses = maps:get(Param, UseMap, []),
+                                  acp_1(Param, Uses, ModInfo, ParamInfo)
+                          end,
+                          funcinfo_get(Func, parameter_info, ModInfo),
+                          Parameters),
+                funcinfo_set(Func, parameter_info, ParamInfo, ModInfo)
+        end,
+    %% Allowing context passthrough on one function may make it possible to
+    %% enable it on another, so it needs to be repeated for maximum effect.
+    case foldl(F, ModInfo0, FsUses) of
+        ModInfo0 -> ModInfo0;
+        Changed -> acp_forward_params(FsUses, Changed)
+    end.
+
+%% We have no way to know if an argument is a context, so it's only safe to
+%% forward them if they're passed exactly once in the first block. Any other
+%% uses are unsafe, including function_clause errors.
+acp_1(Param, [{0, #b_set{op=call}=I}], ModInfo, ParamInfo) ->
+    %% We don't need to provide a context chain as our callers make sure that
+    %% multiple arguments never reference the same context.
+    case check_context_call(I, Param, [], ModInfo) of
+        {no_match_on_entry, _} -> ParamInfo;
+        Other -> maps:put(Param, Other, ParamInfo)
+    end;
+acp_1(_Param, _Uses, _ModInfo, ParamInfo) ->
+    ParamInfo.
+
+%% This is conceptually similar to combine_matches but operates across
+%% functions. Whenever a tail binary is passed to a parameter that accepts
+%% match contexts we'll pass the context instead, improving performance by
+%% avoiding the creation of a new match context in the callee.
+%%
+%% We also create an alias to delay extraction until it's needed as an actual
+%% binary, which is often rare on the happy path. The cost of being wrong is
+%% negligible (`bs_test_unit + bs_get_tail` vs `bs_get_binary`) so we're
+%% applying it unconditionally to keep things simple.
+
+-record(sote, { definitions :: beam_ssa:definition_map(),
+                mod_info :: module_info(),
+                match_aliases = #{} :: match_alias_map() }).
+
+skip_outgoing_tail_extraction({Fs0, ModInfo}) ->
+    Fs = map(fun(F) -> skip_outgoing_tail_extraction(F, ModInfo) end, Fs0),
+    {Fs, ModInfo}.
+
+skip_outgoing_tail_extraction(#b_function{bs=Blocks0}=F, ModInfo) ->
+    case funcinfo_get(F, has_bsm_ops, ModInfo) of
+        true ->
+            State0 = #sote{ definitions = beam_ssa:definitions(Blocks0),
+                            mod_info = ModInfo },
+
+            {Blocks1, State} = beam_ssa:mapfold_instrs_rpo(
+                                 fun sote_rewrite_calls/2, [0], State0, Blocks0),
+
+            {Blocks, Counter} = alias_matched_binaries(Blocks1,
+                                                       F#b_function.cnt,
+                                                       State#sote.match_aliases),
+
+            F#b_function{bs=Blocks,cnt=Counter};
+        false ->
+            F
+    end.
+
+sote_rewrite_calls(#b_set{op=call,args=Args}=Call, State) ->
+    sote_rewrite_call(Call, Args, [], State);
+sote_rewrite_calls(I, State) ->
+    {I, State}.
+
+sote_rewrite_call(Call, [], ArgsOut, State) ->
+    {Call#b_set{args=reverse(ArgsOut)}, State};
+sote_rewrite_call(Call0, [Arg | ArgsIn], ArgsOut, State0) ->
+    case is_tail_binary(Arg, State0#sote.definitions) of
+        true ->
+            CtxChain = context_chain_of(Arg, State0#sote.definitions),
+            case check_context_call(Call0, Arg, CtxChain, State0#sote.mod_info) of
+                suitable_for_reuse ->
+                    Ctx = match_context_of(Arg, State0#sote.definitions),
+
+                    MatchAliases0 = State0#sote.match_aliases,
+                    MatchAliases = maps:put(Arg, {0, Ctx}, MatchAliases0),
+                    State = State0#sote{ match_aliases = MatchAliases },
+
+                    Call = beam_ssa:add_anno(bsm_info, context_reused, Call0),
+                    sote_rewrite_call(Call, ArgsIn, [Ctx | ArgsOut], State);
+                Other ->
+                    Call = beam_ssa:add_anno(bsm_info, Other, Call0),
+                    sote_rewrite_call(Call, ArgsIn, [Arg | ArgsOut], State0)
+            end;
+        false ->
+            sote_rewrite_call(Call0, ArgsIn, [Arg | ArgsOut], State0)
+    end.
+
+%% Adds parameter_type_info annotations to help the validator determine whether
+%% our optimizations were safe.
+
+annotate_context_parameters({Fs, ModInfo}) ->
+    mapfoldl(fun annotate_context_parameters/2, ModInfo, Fs).
+
+annotate_context_parameters(F, ModInfo) ->
+    ParamInfo = funcinfo_get(F, parameter_info, ModInfo),
+    TypeAnno0 = beam_ssa:get_anno(parameter_type_info, F, #{}),
+    TypeAnno = maps:fold(fun(K, _V, Acc) when is_map_key(K, Acc) ->
+                                 %% Assertion.
+                                 error(conflicting_parameter_types);
+                            (K, suitable_for_reuse, Acc) ->
+                                 Acc#{ K => match_context };
+                            (_K, _V, Acc) ->
+                                 Acc
+                         end, TypeAnno0, ParamInfo),
+    {beam_ssa:add_anno(parameter_type_info, TypeAnno, F), ModInfo}.
+
+%%%
+%%% +bin_opt_info
+%%%
+
+collect_opt_info(Fs) ->
+    foldl(fun(#b_function{bs=Blocks}=F, Acc0) ->
+                  UseMap = beam_ssa:uses(Blocks),
+                  Where = beam_ssa:get_anno(location, F, []),
+                  beam_ssa:fold_instrs_rpo(
+                    fun(I, Acc) ->
+                            collect_opt_info_1(I, Where, UseMap, Acc)
+                    end, [0], Acc0, Blocks)
+          end, [], Fs).
+
+collect_opt_info_1(#b_set{op=Op,anno=Anno,dst=Dst}=I, Where, UseMap, Acc0) ->
+    case is_tail_binary(I) of
+        true when Op =:= bs_match ->
+            %% The uses include when the context is passed raw, so we discard
+            %% everything but the bs_extract instruction to limit warnings to
+            %% unoptimized uses.
+            Uses0 = maps:get(Dst, UseMap, []),
+            case [E || {_, #b_set{op=bs_extract}=E} <- Uses0] of
+                [Use] -> add_unopt_binary_info(Use, false, Where, UseMap, Acc0);
+                [] -> Acc0
+            end;
+        true ->
+            %% Add a warning for each use. Note that we don't do anything
+            %% special if unused as a later pass will remove this instruction
+            %% anyway.
+            Uses = maps:get(Dst, UseMap, []),
+            foldl(fun({_Lbl, Use}, Acc) ->
+                          add_unopt_binary_info(Use, false, Where, UseMap, Acc)
+                  end, Acc0, Uses);
+        false ->
+            add_opt_info(Anno, Where, Acc0)
+    end;
+collect_opt_info_1(#b_ret{anno=Anno}, Where, _UseMap, Acc) ->
+    add_opt_info(Anno, Where, Acc);
+collect_opt_info_1(_I, _Where, _Uses, Acc) ->
+    Acc.
+
+add_opt_info(Anno, Where, Acc) ->
+    case maps:find(bsm_info, Anno) of
+        {ok, Term} -> [make_warning(Term, Anno, Where) | Acc];
+        error -> Acc
+    end.
+
+%% When an alias is promoted we need to figure out where it goes to ignore
+%% warnings for compiler-generated things, and provide more useful warnings in
+%% general.
+%%
+%% We track whether the binary has been used to build another term because it
+%% can be helpful when there's no line information.
+
+add_unopt_binary_info(#b_set{op=Follow,dst=Dst}, _Nested, Where, UseMap, Acc0)
+  when Follow =:= put_tuple;
+       Follow =:= put_list;
+       Follow =:= put_map ->
+    %% Term-building instructions.
+    {_, Uses} = unzip(maps:get(Dst, UseMap, [])),
+    foldl(fun(Use, Acc) ->
+                  add_unopt_binary_info(Use, true, Where, UseMap, Acc)
+          end, Acc0, Uses);
+add_unopt_binary_info(#b_set{op=Follow,dst=Dst}, Nested, Where, UseMap, Acc0)
+  when Follow =:= bs_extract;
+       Follow =:= phi ->
+    %% Non-building instructions that need to be followed.
+    {_, Uses} = unzip(maps:get(Dst, UseMap, [])),
+    foldl(fun(Use, Acc) ->
+                  add_unopt_binary_info(Use, Nested, Where, UseMap, Acc)
+          end, Acc0, Uses);
+add_unopt_binary_info(#b_set{op=call,
+                             args=[#b_remote{mod=#b_literal{val=erlang},
+                                             name=#b_literal{val=error}} |
+                                   _Ignored]},
+                      _Nested, _Where, _UseMap, Acc) ->
+    %% There's no nice way to tell compiler-generated exceptions apart from
+    %% user ones so we ignore them all. I doubt anyone cares.
+    Acc;
+add_unopt_binary_info(#b_switch{anno=Anno}=I, Nested, Where, _UseMap, Acc) ->
+    [make_promotion_warning(I, Nested, Anno, Where) | Acc];
+add_unopt_binary_info(#b_set{anno=Anno}=I, Nested, Where, _UseMap, Acc) ->
+    [make_promotion_warning(I, Nested, Anno, Where) | Acc];
+add_unopt_binary_info(#b_ret{anno=Anno}=I, Nested, Where, _UseMap, Acc) ->
+    [make_promotion_warning(I, Nested, Anno, Where) | Acc];
+add_unopt_binary_info(#b_br{anno=Anno}=I, Nested, Where, _UseMap, Acc) ->
+    [make_promotion_warning(I, Nested, Anno, Where) | Acc].
+
+make_promotion_warning(I, Nested, Anno, Where) ->
+    make_warning({binary_created, I, Nested}, Anno, Where).
+
+make_warning(Term, Anno, Where) ->
+    {File, Line} = maps:get(location, Anno, Where),
+    {File,[{Line,?MODULE,Term}]}.
+
+format_opt_info(context_reused) ->
+    "OPTIMIZED: match context reused";
+format_opt_info({binary_created, _, _}=Promotion) ->
+    io_lib:format("BINARY CREATED: ~s", [format_opt_info_1(Promotion)]);
+format_opt_info(Other) ->
+    io_lib:format("NOT OPTIMIZED: ~s", [format_opt_info_1(Other)]).
+
+format_opt_info_1({binary_created, #b_set{op=call,args=[Call|_]}, false}) ->
+    io_lib:format("binary is used in call to ~s which doesn't support "
+                  "context reuse", [format_call(Call)]);
+format_opt_info_1({binary_created, #b_set{op=call,args=[Call|_]}, true}) ->
+    io_lib:format("binary is used in term passed to ~s",
+                  [format_call(Call)]);
+format_opt_info_1({binary_created, #b_set{op={bif, BIF},args=Args}, false}) ->
+    io_lib:format("binary is used in ~p/~p which doesn't support context "
+                  "reuse", [BIF, length(Args)]);
+format_opt_info_1({binary_created, #b_set{op={bif, BIF},args=Args}, true}) ->
+    io_lib:format("binary is used in term passed to ~p/~p",
+                  [BIF, length(Args)]);
+format_opt_info_1({binary_created, #b_set{op=Op}, false}) ->
+    io_lib:format("binary is used in '~p' which doesn't support context "
+                  "reuse", [Op]);
+format_opt_info_1({binary_created, #b_set{op=Op}, true}) ->
+    io_lib:format("binary is used in term passed to '~p'", [Op]);
+format_opt_info_1({binary_created, #b_ret{}, false}) ->
+    io_lib:format("binary is returned from the function", []);
+format_opt_info_1({binary_created, #b_ret{}, true}) ->
+    io_lib:format("binary is used in a term that is returned from the "
+                  "function", []);
+format_opt_info_1({unsuitable_call, {Call, Inner}}) ->
+    io_lib:format("binary used in call to ~s, where ~s",
+                  [format_call(Call), format_opt_info_1(Inner)]);
+format_opt_info_1({remote_call, Call}) ->
+    io_lib:format("binary is used in remote call to ~s", [format_call(Call)]);
+format_opt_info_1({fun_call, Call}) ->
+    io_lib:format("binary is used in fun call (~s)",
+                  [format_call(Call)]);
+format_opt_info_1({multiple_uses_in_call, Call}) ->
+    io_lib:format("binary is passed as multiple arguments to ~s",
+                  [format_call(Call)]);
+format_opt_info_1({no_match_on_entry, Call}) ->
+    io_lib:format("binary is used in call to ~s which does not begin with a "
+                  "suitable binary match", [format_call(Call)]);
+format_opt_info_1({used_before_match, #b_set{op=call,args=[Call|_]}}) ->
+    io_lib:format("binary is used in call to ~s before being matched",
+                  [format_call(Call)]);
+format_opt_info_1({used_before_match, #b_set{op={bif, BIF},args=Args}}) ->
+    io_lib:format("binary is used in ~p/~p before being matched",
+                  [BIF, length(Args)]);
+format_opt_info_1({used_before_match, #b_set{op=phi}}) ->
+    io_lib:format("binary is returned from an expression before being "
+                  "matched", []);
+format_opt_info_1({used_before_match, #b_set{op=Op}}) ->
+    io_lib:format("binary is used in '~p' before being matched",[Op]);
+format_opt_info_1(Term) ->
+    io_lib:format("~w", [Term]).
+
+format_call(#b_local{name=#b_literal{val=F},arity=A}) ->
+    io_lib:format("~p/~p", [F, A]);
+format_call(#b_remote{mod=#b_literal{val=M},name=#b_literal{val=F},arity=A}) ->
+    io_lib:format("~p:~p/~p", [M, F, A]);
+format_call(Fun) ->
+    io_lib:format("~p", [Fun]).
diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl
index 5085c950b5..281e953127 100644
--- a/lib/compiler/src/beam_ssa_codegen.erl
+++ b/lib/compiler/src/beam_ssa_codegen.erl
@@ -108,7 +108,8 @@ module(#b_module{name=Mod,exports=Es,attributes=Attrs,body=Fs}, _Opts) ->
 -type ssa_register() :: xreg() | yreg() | {'fr',reg_num()} | {'z',reg_num()}.
 
 functions(Forms, AtomMod) ->
-    mapfoldl(fun (F, St) -> function(F, AtomMod, St) end, #cg{lcount=1}, Forms).
+    mapfoldl(fun (F, St) -> function(F, AtomMod, St) end,
+             #cg{lcount=1}, Forms).
 
 function(#b_function{anno=Anno,bs=Blocks}, AtomMod, St0) ->
     #{func_info:={_,Name,Arity}} = Anno,
@@ -125,8 +126,9 @@ function(#b_function{anno=Anno,bs=Blocks}, AtomMod, St0) ->
                      ultimate_fail=Ult},
         {Body,St} = cg_fun(Blocks, St5),
         Asm = [{label,Fi},line(Anno),
-               {func_info,AtomMod,{atom,Name},Arity}] ++ Body ++
-            [{label,Ult},if_end],
+               {func_info,AtomMod,{atom,Name},Arity}] ++
+               add_parameter_annos(Body, Anno) ++
+               [{label,Ult},if_end],
         Func = {function,Name,Arity,Entry,Asm},
         {Func,St}
     catch
@@ -150,6 +152,17 @@ assert_badarg_block(Blocks) ->
             ok
     end.
 
+add_parameter_annos([{label, _}=Entry | Body], Anno) ->
+    ParamInfo = maps:get(parameter_type_info, Anno, #{}),
+    Annos = maps:fold(
+        fun(K, V, Acc) when is_map_key(K, ParamInfo) ->
+                TypeInfo = maps:get(K, ParamInfo),
+                [{'%', {type_info, V, TypeInfo}} | Acc];
+           (_K, _V, Acc) ->
+                Acc
+        end, [], maps:get(registers, Anno)),
+    [Entry | Annos] ++ Body.
+
 cg_fun(Blocks, St0) ->
     Linear0 = linearize(Blocks),
     St = collect_catch_labels(Linear0, St0),
@@ -315,12 +328,15 @@ classify_heap_need(Name, _Args) ->
 
 classify_heap_need(bs_add) -> gc;
 classify_heap_need(bs_get) -> gc;
+classify_heap_need(bs_get_tail) -> gc;
 classify_heap_need(bs_init) -> gc;
 classify_heap_need(bs_init_writable) -> gc;
 classify_heap_need(bs_match_string) -> gc;
 classify_heap_need(bs_put) -> neutral;
 classify_heap_need(bs_restore) -> neutral;
 classify_heap_need(bs_save) -> neutral;
+classify_heap_need(bs_get_position) -> gc;
+classify_heap_need(bs_set_position) -> neutral;
 classify_heap_need(bs_skip) -> gc;
 classify_heap_need(bs_start_match) -> neutral;
 classify_heap_need(bs_test_tail) -> neutral;
@@ -695,6 +711,8 @@ need_live_anno(Op) ->
         {bif,_} -> true;
         bs_get -> true;
         bs_init -> true;
+        bs_get_position -> true;
+        bs_get_tail -> true;
         bs_start_match -> true;
         bs_skip -> true;
         call -> true;
@@ -794,6 +812,8 @@ def_successors([], _, DefMap) -> DefMap.
 
 need_y_init(#cg_set{anno=#{clobbers:=Clobbers}}) -> Clobbers;
 need_y_init(#cg_set{op=bs_get}) -> true;
+need_y_init(#cg_set{op=bs_get_position}) -> true;
+need_y_init(#cg_set{op=bs_get_tail}) -> true;
 need_y_init(#cg_set{op=bs_init}) -> true;
 need_y_init(#cg_set{op=bs_skip,args=[#b_literal{val=Type}|_]}) ->
     case Type of
@@ -1042,12 +1062,18 @@ cg_block([#cg_set{op=bs_init,dst=Dst0,args=Args0,anno=Anno}=I,
     end;
 cg_block([#cg_set{anno=Anno,op=bs_start_match,dst=Ctx0,args=[Bin0]}=I,
           #cg_set{op=succeeded,dst=Bool}], {Bool,Fail}, St) ->
-    #{num_slots:=Slots} = Anno,
     [Dst,Bin1] = beam_args([Ctx0,Bin0], St),
     {Bin,Pre} = force_reg(Bin1, Dst),
     Live = get_live(I),
-    Is = Pre ++ [{test,bs_start_match2,Fail,Live,[Bin,Slots],Dst}],
-    {Is,St};
+    %% num_slots is only set when using the old instructions.
+    case maps:find(num_slots, Anno) of
+        {ok, Slots} ->
+            Is = Pre ++ [{test,bs_start_match2,Fail,Live,[Bin,Slots],Dst}],
+            {Is,St};
+        error ->
+            Is = Pre ++ [{test,bs_start_match3,Fail,Live,[Bin],Dst}],
+            {Is,St}
+    end;
 cg_block([#cg_set{op=bs_get}=Set,
           #cg_set{op=succeeded,dst=Bool}], {Bool,Fail}, St) ->
     {cg_bs_get(Fail, Set, St),St};
@@ -1344,6 +1370,12 @@ build_apply(Arity, none, Dst) ->
 cg_instr(put_map, [{atom,assoc},SrcMap|Ss], Dst, Set) ->
     Live = get_live(Set),
     [{put_map_assoc,{f,0},SrcMap,Dst,Live,{list,Ss}}];
+cg_instr(bs_get_tail, [Src], Dst, Set) ->
+    Live = get_live(Set),
+    [{bs_get_tail,Src,Dst,Live}];
+cg_instr(bs_get_position, [Ctx], Dst, Set) ->
+    Live = get_live(Set),
+    [{bs_get_position,Ctx,Dst,Live}];
 cg_instr(Op, Args, Dst, _Set) ->
     cg_instr(Op, Args, Dst).
 
@@ -1359,6 +1391,8 @@ cg_instr(bs_restore, [Ctx,Slot], _Dst) ->
 cg_instr(bs_save, [Ctx,Slot], _Dst) ->
     {integer,N} = Slot,
     [{bs_save2,Ctx,N}];
+cg_instr(bs_set_position, [Ctx,Pos], _Dst) ->
+    [{bs_set_position,Ctx,Pos}];
 cg_instr(build_stacktrace, Args, Dst) ->
     setup_args(Args) ++ [build_stacktrace|copy({x,0}, Dst)];
 cg_instr(context_to_binary, [Src], _Dst) ->
diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl
index bc5609cd76..e949aab722 100644
--- a/lib/compiler/src/beam_ssa_pre_codegen.erl
+++ b/lib/compiler/src/beam_ssa_pre_codegen.erl
@@ -79,15 +79,14 @@
                     {'ok',beam_ssa:b_module()}.
 
 module(#b_module{body=Fs0}=Module, Opts) ->
-    FixTuples = proplists:get_bool(no_put_tuple2, Opts),
-    ExtraAnnos = proplists:get_bool(dprecg, Opts),
-    Ps = passes(FixTuples, ExtraAnnos),
-    Fs = functions(Fs0, Ps),
+    UseBSM3 = not proplists:get_bool(no_bsm3, Opts),
+    Ps = passes(Opts),
+    Fs = functions(Fs0, Ps, UseBSM3),
     {ok,Module#b_module{body=Fs}}.
 
-functions([F|Fs], Ps) ->
-    [function(F, Ps)|functions(Fs, Ps)];
-functions([], _Ps) -> [].
+functions([F|Fs], Ps, UseBSM3) ->
+    [function(F, Ps, UseBSM3)|functions(Fs, Ps, UseBSM3)];
+functions([], _Ps, _UseBSM3) -> [].
 
 -type b_var() :: beam_ssa:b_var().
 -type var_name() :: beam_ssa:var_name().
@@ -105,6 +104,7 @@ functions([], _Ps) -> [].
 -record(st, {ssa :: beam_ssa:block_map(),
              args :: [b_var()],
              cnt :: beam_ssa:label(),
+             use_bsm3 :: boolean(),
              frames=[] :: [beam_ssa:label()],
              intervals=[] :: [{b_var(),[range()]}],
              aliases=[] :: [{b_var(),b_var()}],
@@ -114,7 +114,9 @@ functions([], _Ps) -> [].
             }).
 -define(PASS(N), {N,fun N/1}).
 
-passes(FixTuples, ExtraAnnos) ->
+passes(Opts) ->
+    AddPrecgAnnos = proplists:get_bool(dprecg, Opts),
+    FixTuples = proplists:get_bool(no_put_tuple2, Opts),
     Ps = [?PASS(assert_no_critical_edges),
 
           %% Preliminaries.
@@ -145,7 +147,7 @@ passes(FixTuples, ExtraAnnos) ->
 
           %% If needed for a .precg file, save the live intervals
           %% so they can be included in an annotation.
-          case ExtraAnnos of
+          case AddPrecgAnnos of
               false -> ignore;
               true -> ?PASS(save_live_intervals)
           end,
@@ -157,9 +159,10 @@ passes(FixTuples, ExtraAnnos) ->
           ?PASS(turn_yregs)],
     [P || P <- Ps, P =/= ignore].
 
-function(#b_function{anno=Anno,args=Args,bs=Blocks0,cnt=Count0}=F0, Ps) ->
+function(#b_function{anno=Anno,args=Args,bs=Blocks0,cnt=Count0}=F0,
+         Ps, UseBSM3) ->
     try
-        St0 = #st{ssa=Blocks0,args=Args,cnt=Count0},
+        St0 = #st{ssa=Blocks0,args=Args,use_bsm3=UseBSM3,cnt=Count0},
         St = compile:run_sub_passes(Ps, St0),
         #st{ssa=Blocks,cnt=Count,regs=Regs,extra_annos=ExtraAnnos} = St,
         F1 = add_extra_annos(F0, ExtraAnnos),
@@ -215,7 +218,7 @@ assert_no_ces(_, _, Blocks) -> Blocks.
 %%    * Combine bs_match and bs_extract instructions to bs_get
 %%      instructions.
 
-fix_bs(#st{ssa=Blocks,cnt=Count0}=St) ->
+fix_bs(#st{ssa=Blocks,cnt=Count0,use_bsm3=UseBSM3}=St) ->
     F = fun(#b_set{op=bs_start_match,dst=Dst}, A) ->
                 %% Mark the root of the match context list.
                 [{Dst,{context,Dst}}|A];
@@ -233,8 +236,13 @@ fix_bs(#st{ssa=Blocks,cnt=Count0}=St) ->
             CtxChain = maps:from_list(M),
             Linear0 = beam_ssa:linearize(Blocks),
 
-            %% Insert bs_save / bs_restore instructions where needed.
-            {Linear1,Count} = bs_save_restore(Linear0, CtxChain, Count0),
+            %% Insert position instructions where needed.
+            {Linear1,Count} = case UseBSM3 of
+                                  true ->
+                                      bs_pos_bsm3(Linear0, CtxChain, Count0);
+                                  false ->
+                                      bs_pos_bsm2(Linear0, CtxChain, Count0)
+                              end,
 
             %% Rename instructions.
             Linear = bs_instrs(Linear1, CtxChain, []),
@@ -242,10 +250,54 @@ fix_bs(#st{ssa=Blocks,cnt=Count0}=St) ->
             St#st{ssa=maps:from_list(Linear),cnt=Count}
     end.
 
+%% Insert bs_get_position and bs_set_position instructions as needed.
+bs_pos_bsm3(Linear0, CtxChain, Count0) ->
+    Rs0 = bs_restores(Linear0, CtxChain, #{}, #{}),
+    Rs = maps:values(Rs0),
+    S0 = sofs:relation(Rs, [{context,save_point}]),
+    S1 = sofs:relation_to_family(S0),
+    S = sofs:to_external(S1),
+
+    {SavePoints,Count1} = make_bs_pos_dict(S, Count0, []),
+    {Gets,Count2} = make_bs_setpos_map(Rs, SavePoints, Count1, []),
+    {Sets,Count} = make_bs_getpos_map(maps:to_list(Rs0), SavePoints, Count2, []),
+
+    %% Now insert all saves and restores.
+    {bs_insert_bsm3(Linear0, Gets, Sets, SavePoints),Count}.
+
+make_bs_setpos_map([{Ctx,Save}=Ps|T], SavePoints, Count, Acc) ->
+    SavePoint = get_savepoint(Ps, SavePoints),
+    I = #b_set{op=bs_get_position,dst=SavePoint,args=[Ctx]},
+    make_bs_setpos_map(T, SavePoints, Count+1, [{Save,I}|Acc]);
+make_bs_setpos_map([], _, Count, Acc) ->
+    {maps:from_list(Acc),Count}.
+
+make_bs_getpos_map([{Bef,{Ctx,_}=Ps}|T], SavePoints, Count, Acc) ->
+    Ignored = #b_var{name={'@ssa_ignored',Count}},
+    Args = [Ctx, get_savepoint(Ps, SavePoints)],
+    I = #b_set{op=bs_set_position,dst=Ignored,args=Args},
+    make_bs_getpos_map(T, SavePoints, Count+1, [{Bef,I}|Acc]);
+make_bs_getpos_map([], _, Count, Acc) ->
+    {maps:from_list(Acc),Count}.
+
+get_savepoint({_,_}=Ps, SavePoints) ->
+    Name = {'@ssa_bs_position', maps:get(Ps, SavePoints)},
+    #b_var{name=Name}.
+
+make_bs_pos_dict([{Ctx,Pts}|T], Count0, Acc0) ->
+    {Acc, Count} = make_bs_pos_dict_1(Pts, Ctx, Count0, Acc0),
+    make_bs_pos_dict(T, Count, Acc);
+make_bs_pos_dict([], Count, Acc) ->
+    {maps:from_list(Acc), Count}.
 
-%% Insert bs_save and bs_restore instructions as needed.
+make_bs_pos_dict_1([H|T], Ctx, I, Acc) ->
+    make_bs_pos_dict_1(T, Ctx, I+1, [{{Ctx,H},I}|Acc]);
+make_bs_pos_dict_1([], Ctx, I, Acc) ->
+    {[{Ctx,I}|Acc], I}.
 
-bs_save_restore(Linear0, CtxChain, Count0) ->
+%% As bs_position but without OTP-22 instructions. This is only used when
+%% cross-compiling to older versions.
+bs_pos_bsm2(Linear0, CtxChain, Count0) ->
     Rs0 = bs_restores(Linear0, CtxChain, #{}, #{}),
     Rs = maps:values(Rs0),
     S0 = sofs:relation(Rs, [{context,save_point}]),
@@ -256,7 +308,7 @@ bs_save_restore(Linear0, CtxChain, Count0) ->
     {Restores,Count} = make_restore_map(maps:to_list(Rs0), Slots, Count1, []),
 
     %% Now insert all saves and restores.
-    {bs_insert(Linear0, Saves, Restores, Slots),Count}.
+    {bs_insert_bsm2(Linear0, Saves, Restores, Slots),Count}.
 
 make_save_map([{Ctx,Save}=Ps|T], Slots, Count, Acc) ->
     Ignored = #b_var{name={'@ssa_ignored',Count}},
@@ -309,8 +361,7 @@ bs_restores([], _, _, Rs) -> Rs.
 
 bs_update_successors(#b_br{succ=Succ,fail=Fail}, SPos, FPos, D) ->
     join_positions([{Succ,SPos},{Fail,FPos}], D);
-bs_update_successors(#b_switch{fail=Fail,list=List}, SPos, FPos, D) ->
-    SPos = FPos,                                %Assertion.
+bs_update_successors(#b_switch{fail=Fail,list=List}, SPos, _FPos, D) ->
     Update = [{L,SPos} || {_,L} <- List] ++ [{Fail,SPos}],
     join_positions(Update, D);
 bs_update_successors(#b_ret{}, _, _, D) -> D.
@@ -389,10 +440,19 @@ bs_restores_is([#b_set{op=bs_extract,args=[FromPos|_]}|Is],
     Start = bs_subst_ctx(FromPos, CtxChain),
     #{Start:=FromPos} = PosMap,                 %Assertion.
     bs_restores_is(Is, CtxChain, PosMap, Rs);
+bs_restores_is([#b_set{op=call,dst=Dst,args=Args}|Is],
+               CtxChain, PosMap0, Rs0) ->
+    {Rs,PosMap1} = bs_restore_args(Args, PosMap0, CtxChain, Dst, Rs0),
+    PosMap = bs_invalidate_pos(Args, PosMap1, CtxChain),
+    bs_restores_is(Is, CtxChain, PosMap, Rs);
+bs_restores_is([#b_set{op=landingpad}|Is], CtxChain, PosMap0, Rs) ->
+    %% We can land here from any point, so all positions are invalid.
+    PosMap = maps:map(fun(_Start,_Pos) -> unknown end, PosMap0),
+    bs_restores_is(Is, CtxChain, PosMap, Rs);
 bs_restores_is([#b_set{op=Op,dst=Dst,args=Args}|Is],
                CtxChain, PosMap0, Rs0)
   when Op =:= bs_test_tail;
-       Op =:= call ->
+       Op =:= bs_get_tail ->
     {Rs,PosMap} = bs_restore_args(Args, PosMap0, CtxChain, Dst, Rs0),
     bs_restores_is(Is, CtxChain, PosMap, Rs);
 bs_restores_is([_|Is], CtxChain, PosMap, Rs) ->
@@ -400,7 +460,6 @@ bs_restores_is([_|Is], CtxChain, PosMap, Rs) ->
 bs_restores_is([], _CtxChain, PosMap, Rs) ->
     {PosMap,Rs}.
 
-
 bs_match_type(#b_set{args=[#b_literal{val=skip},_Ctx,
                              #b_literal{val=binary},_Flags,
                              #b_literal{val=all},#b_literal{val=U}]}) ->
@@ -411,6 +470,23 @@ bs_match_type(#b_set{args=[#b_literal{val=skip},_Ctx,
 bs_match_type(_) ->
     plain.
 
+%% Call instructions leave the match position in an undefined state,
+%% requiring us to invalidate each affected argument.
+bs_invalidate_pos([#b_var{}=Arg|Args], PosMap0, CtxChain) ->
+    Start = bs_subst_ctx(Arg, CtxChain),
+    case PosMap0 of
+        #{Start:=_} ->
+            PosMap = PosMap0#{Start:=unknown},
+            bs_invalidate_pos(Args, PosMap, CtxChain);
+        #{} ->
+            %% Not a match context.
+            bs_invalidate_pos(Args, PosMap0, CtxChain)
+    end;
+bs_invalidate_pos([_|Args], PosMap, CtxChain) ->
+    bs_invalidate_pos(Args, PosMap, CtxChain);
+bs_invalidate_pos([], PosMap, _CtxChain) ->
+    PosMap.
+
 bs_restore_args([#b_var{}=Arg|Args], PosMap0, CtxChain, Dst, Rs0) ->
     Start = bs_subst_ctx(Arg, CtxChain),
     case PosMap0 of
@@ -433,33 +509,45 @@ bs_restore_args([], PosMap, _CtxChain, _Dst, Rs) ->
 
 %% Insert all bs_save and bs_restore instructions.
 
-bs_insert([{L,#b_blk{is=Is0}=Blk}|Bs0], Saves, Restores, Slots) ->
-    Is = bs_insert_is_1(Is0, Restores, Slots),
+bs_insert_bsm3(Blocks, Saves, Restores, SavePoints) ->
+    bs_insert_1(Blocks, Saves, Restores, SavePoints, fun(I) -> I end).
+
+bs_insert_bsm2(Blocks, Saves, Restores, SavePoints) ->
+    %% The old instructions require bs_start_match to be annotated with the
+    %% number of position slots it needs.
+    bs_insert_1(Blocks, Saves, Restores, SavePoints,
+                fun(#b_set{op=bs_start_match,dst=Dst}=I0) ->
+                        NumSlots = case SavePoints of
+                                       #{Dst:=NumSlots0} -> NumSlots0;
+                                       #{} -> 0
+                                   end,
+                        beam_ssa:add_anno(num_slots, NumSlots, I0);
+                   (I) ->
+                        I
+                end).
+
+bs_insert_1([{L,#b_blk{is=Is0}=Blk}|Bs0], Saves, Restores, Slots, XFrm) ->
+    Is = bs_insert_is_1(Is0, Restores, Slots, XFrm),
     Bs = bs_insert_saves(Is, Bs0, Saves),
-    [{L,Blk#b_blk{is=Is}}|bs_insert(Bs, Saves, Restores, Slots)];
-bs_insert([], _, _, _) -> [].
+    [{L,Blk#b_blk{is=Is}}|bs_insert_1(Bs, Saves, Restores, Slots, XFrm)];
+bs_insert_1([], _, _, _, _) -> [].
 
-bs_insert_is_1([#b_set{op=Op,dst=Dst}=I0|Is], Restores, Slots) ->
+bs_insert_is_1([#b_set{op=Op,dst=Dst}=I0|Is], Restores, SavePoints, XFrm) ->
+    I = XFrm(I0),
     if
         Op =:= bs_test_tail;
+        Op =:= bs_get_tail;
         Op =:= bs_match;
         Op =:= call ->
             Rs = case Restores of
                      #{Dst:=R} -> [R];
                      #{} -> []
                  end,
-            Rs ++ [I0|bs_insert_is_1(Is, Restores, Slots)];
-        Op =:= bs_start_match ->
-            NumSlots = case Slots of
-                           #{Dst:=NumSlots0} -> NumSlots0;
-                           #{} -> 0
-                       end,
-            I = beam_ssa:add_anno(num_slots, NumSlots, I0),
-            [I|bs_insert_is_1(Is, Restores, Slots)];
+            Rs ++ [I|bs_insert_is_1(Is, Restores, SavePoints, XFrm)];
         true ->
-            [I0|bs_insert_is_1(Is, Restores, Slots)]
+            [I|bs_insert_is_1(Is, Restores, SavePoints, XFrm)]
     end;
-bs_insert_is_1([], _, _) -> [].
+bs_insert_is_1([], _, _, _) -> [].
 
 bs_insert_saves([#b_set{dst=Dst}|Is], Bs, Saves) ->
     case Saves of
@@ -505,6 +593,8 @@ bs_instrs_is([#b_set{op=Op,args=Args0}=I0|Is], CtxChain, Acc) ->
                 I1#b_set{op=bs_skip,args=[Type,Ctx|As]};
             {bs_match,[#b_literal{val=string},Ctx|As]} ->
                 I1#b_set{op=bs_match_string,args=[Ctx|As]};
+            {bs_get_tail,[Ctx|As]} ->
+                I1#b_set{op=bs_get_tail,args=[Ctx|As]};
             {_,_} ->
                 I1
         end,
@@ -1579,17 +1669,10 @@ live_interval_blk_1([#b_set{op=phi,dst=Dst}|Is],
     Acc = [{Dst,{def,FirstNumber}}|Acc0],
     live_interval_blk_1(Is, FirstNumber, Aliases, Acc);
 live_interval_blk_1([#b_set{op=bs_start_match}=I|Is], FirstNumber,
-                    Aliases0, Acc0) ->
+                    Aliases, Acc0) ->
     N = beam_ssa:get_anno(n, I),
     #b_set{dst=Dst} = I,
     Acc1 = [{Dst,{def,N}}|Acc0],
-    Aliases = case beam_ssa:get_anno(reuse_for_context, I) of
-                  true ->
-                      #b_set{args=[Src]} = I,
-                      [{Dst,Src}|Aliases0];
-                  false ->
-                      Aliases0
-              end,
     Acc = [{V,{use,N}} || V <- beam_ssa:used(I)] ++ Acc1,
     live_interval_blk_1(Is, FirstNumber, Aliases, Acc);
 live_interval_blk_1([I|Is], FirstNumber, Aliases, Acc0) ->
@@ -1866,10 +1949,10 @@ reserve_zreg([#b_set{op={bif,tuple_size},dst=Dst}],
     reserve_zreg_1(Dst, ShortLived, A);
 reserve_zreg([#b_set{op=Op,dst=Dst}|Is], Last, ShortLived, A0) ->
     IsZReg = case Op of
-                 context_to_binary -> true;
                  bs_match_string -> true;
-                 bs_restore -> true;
                  bs_save -> true;
+                 bs_restore -> true;
+                 bs_set_position -> true;
                  {float,clearerror} -> true;
                  kill_try_tag -> true;
                  landingpad -> true;
diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl
index 5ccc9c371b..18e6e73a46 100644
--- a/lib/compiler/src/beam_ssa_type.erl
+++ b/lib/compiler/src/beam_ssa_type.erl
@@ -486,6 +486,8 @@ type(bs_extract, [Ctx], Ts, _Ds) ->
     Type;
 type(bs_match, Args, _Ts, _Ds) ->
     #t_bs_match{type=bs_match_type(Args)};
+type(bs_get_tail, _Args, _Ts, _Ds) ->
+    {binary, 1};
 type(call, [#b_remote{mod=#b_literal{val=Mod},
                       name=#b_literal{val=Name}}|Args], Ts, _Ds) ->
     case {Mod,Name,Args} of
diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index 8d699f2abd..fbcbb2cb4a 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -90,33 +90,30 @@ format_error(Error) ->
 %%  format as used in the compiler and in .S files.
 
 validate(Module, Fs) ->
-    Ft = index_bs_start_match(Fs, []),
+    Ft = index_parameter_types(Fs, []),
     validate_0(Module, Fs, Ft).
 
-index_bs_start_match([{function,_,_,Entry,Code0}|Fs], Acc0) ->
+index_parameter_types([{function,_,_,Entry,Code0}|Fs], Acc0) ->
     Code = dropwhile(fun({label,L}) when L =:= Entry -> false;
 			(_) -> true
 		     end, Code0),
     case Code of
 	[{label,Entry}|Is] ->
-	    Acc = index_bs_start_match_1(Is, Entry, Acc0),
-	    index_bs_start_match(Fs, Acc);
+	    Acc = index_parameter_types_1(Is, Entry, Acc0),
+	    index_parameter_types(Fs, Acc);
 	_ ->
 	    %% Something serious is wrong. Ignore it for now.
 	    %% It will be detected and diagnosed later.
-	    index_bs_start_match(Fs, Acc0)
+	    index_parameter_types(Fs, Acc0)
     end;
-index_bs_start_match([], Acc) ->
+index_parameter_types([], Acc) ->
     gb_trees:from_orddict(lists:sort(Acc)).
 
-index_bs_start_match_1([{test,bs_start_match2,_,_,_,_}=I|_], Entry, Acc) ->
-    [{Entry,[I]}|Acc];
-index_bs_start_match_1([{test,_,{f,F},_},{bs_context_to_binary,_}|Is0], Entry, Acc) ->
-    [{label,F}|Is] = dropwhile(fun({label,L}) when L =:= F -> false;
-				  (_)  -> true
-			       end, Is0),
-    index_bs_start_match_1(Is, Entry, Acc);
-index_bs_start_match_1(_, _, Acc) -> Acc.
+index_parameter_types_1([{'%', {type_info, Reg, Type}} | Is], Entry, Acc) ->
+    Key = {Entry, Reg},
+    index_parameter_types_1(Is, Entry, [{Key, Type} | Acc]);
+index_parameter_types_1(_, _, Acc) ->
+    Acc.
 
 validate_0(_Module, [], _) -> [];
 validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) ->
@@ -300,6 +297,21 @@ valfun_1({bs_context_to_binary,Ctx}, #vst{current=#st{x=Xs}}=Vst) ->
 	_ ->
 	    error({bad_source,Ctx})
     end;
+valfun_1({bs_get_tail,Ctx,Dst,Live}, Vst0) ->
+    verify_live(Live, Vst0),
+    verify_y_init(Vst0),
+    Vst = prune_x_regs(Live, Vst0),
+    #vst{current=#st{x=Xs,y=Ys}} = Vst,
+    {Reg, Tree} = case Ctx of
+                      {x,X} -> {X, Xs};
+                      {y,Y} -> {Y, Ys};
+                      _ -> error({bad_source,Ctx})
+                  end,
+    Type = case gb_trees:lookup(Reg, Tree) of
+               {value,#ms{}} -> propagate_fragility(term, [Ctx], Vst);
+               _ -> error({bad_context,Reg})
+           end,
+    set_type_reg(Type, Dst, Vst);
 valfun_1(bs_init_writable=I, Vst) ->
     call(I, 1, Vst);
 valfun_1(build_stacktrace=I, Vst) ->
@@ -385,6 +397,25 @@ valfun_1(remove_message, Vst) ->
     %% The message term is no longer fragile. It can be used
     %% without restrictions.
     remove_fragility(Vst);
+valfun_1({'%', {type_info, Reg, Info0}}, Vst0) ->
+    %% Explicit type information inserted by optimization passes to indicate
+    %% that Reg has a certain type, so that we can accept cross-function type
+    %% optimizations.
+    %%
+    %% At the moment we only allow this when narrowing from 'term' which is
+    %% what to expect with function parameters, but in theory any narrowing
+    %% conversion should be legal.
+    case get_move_term_type(Reg, Vst0) of
+        term ->
+            Type0 = case Info0 of
+                        match_context -> #ms{};
+                        _ -> Info0
+                    end,
+            Type = propagate_fragility(Type0, [Reg], Vst0),
+            set_type_reg(Type, Reg, Vst0);
+        _ ->
+            error(bad_type_info)
+    end;
 valfun_1({'%',_}, Vst) ->
     Vst;
 valfun_1({line,_}, Vst) ->
@@ -676,32 +707,44 @@ valfun_4({select_tuple_arity,Tuple,{f,Fail},{list,Choices}}, Vst) ->
                               branch_state(Fail, Vst)));
 
 %% New bit syntax matching instructions.
-valfun_4({test,bs_start_match2,{f,Fail},Live,[Ctx,NeedSlots],Ctx}, Vst0) ->
-    %% If source and destination registers are the same, match state
-    %% is OK as input.
-    CtxType = get_move_term_type(Ctx, Vst0),
+valfun_4({test,bs_start_match3,{f,Fail},Live,[Src],Dst}, Vst0) ->
+    %% Match states are always okay as input.
+    SrcType = get_move_term_type(Src, Vst0),
+    DstType = propagate_fragility(bsm_match_state(), [Src], Vst0),
     verify_live(Live, Vst0),
     verify_y_init(Vst0),
     Vst1 = prune_x_regs(Live, Vst0),
-    BranchVst = case CtxType of
-		    #ms{} ->
-			%% The failure branch will never be taken when Ctx
-			%% is a match context. Therefore, the type for Ctx
-			%% at the failure label must not be match_context
-			%% (or we could reject legal code).
-			set_type_reg(term, Ctx, Vst1);
-		    _ ->
-			Vst1
-		end,
+    BranchVst = case SrcType of
+                    #ms{} ->
+                        %% The failure branch will never be taken when Src is a
+                        %% match context. Therefore, the type for Src at the
+                        %% failure label must not be match_context (or we could
+                        %% reject legal code).
+                        set_type_reg(term, Src, Vst1);
+                    _ ->
+                        Vst1
+                end,
     Vst = branch_state(Fail, BranchVst),
-    set_type_reg(bsm_match_state(NeedSlots), Ctx, Vst);
+    set_type_reg(DstType, Dst, Vst);
 valfun_4({test,bs_start_match2,{f,Fail},Live,[Src,Slots],Dst}, Vst0) ->
-    assert_term(Src, Vst0),
+    %% Match states are always okay as input.
+    SrcType = get_move_term_type(Src, Vst0),
+    DstType = propagate_fragility(bsm_match_state(Slots), [Src], Vst0),
     verify_live(Live, Vst0),
     verify_y_init(Vst0),
     Vst1 = prune_x_regs(Live, Vst0),
-    Vst = branch_state(Fail, Vst1),
-    set_type_reg(bsm_match_state(Slots), Src, Dst, Vst);
+    BranchVst = case SrcType of
+                    #ms{} ->
+                        %% The failure branch will never be taken when Src is a
+                        %% match context. Therefore, the type for Src at the
+                        %% failure label must not be match_context (or we could
+                        %% reject legal code).
+                        set_type_reg(term, Src, Vst1);
+                    _ ->
+                        Vst1
+                end,
+    Vst = branch_state(Fail, BranchVst),
+    set_type_reg(DstType, Dst, Vst);
 valfun_4({test,bs_match_string,{f,Fail},[Ctx,_,_]}, Vst) ->
     bsm_validate_context(Ctx, Vst),
     branch_state(Fail, Vst);
@@ -738,6 +781,16 @@ valfun_4({bs_save2,Ctx,SavePoint}, Vst) ->
     bsm_save(Ctx, SavePoint, Vst);
 valfun_4({bs_restore2,Ctx,SavePoint}, Vst) ->
     bsm_restore(Ctx, SavePoint, Vst);
+valfun_4({bs_get_position, Ctx, Dst, Live}, Vst0) ->
+    bsm_validate_context(Ctx, Vst0),
+    verify_live(Live, Vst0),
+    verify_y_init(Vst0),
+    Vst = prune_x_regs(Live, Vst0),
+    set_type_reg(bs_position, Dst, Vst);
+valfun_4({bs_set_position, Ctx, Pos}, Vst) ->
+    bsm_validate_context(Ctx, Vst),
+    assert_type(bs_position, Pos, Vst),
+    Vst;
 
 %% Other test instructions.
 valfun_4({test,is_float,{f,Lbl},[Float]}, Vst) ->
@@ -999,26 +1052,12 @@ verify_call_args_1(N, Vst) ->
     verify_call_args_1(X, Vst).
 
 verify_local_call(Lbl, Live, Vst) ->
-    case all_ms_in_x_regs(Live, Vst) of
-	[{R,Ctx}] ->
-	    %% Verify that there is a suitable bs_start_match2 instruction.
-	    verify_call_match_context(Lbl, R, Vst),
-
-	    %% Since the callee has consumed the match context,
-	    %% there must be no additional copies in Y registers.
-	    #ms{id=Id} = Ctx,
-	    case ms_in_y_regs(Id, Vst) of
-		[] ->
-		    ok;
-		[_|_]=Ys ->
-		    error({multiple_match_contexts,[R|Ys]})
-	    end;
-	[_,_|_]=Xs0 ->
-	    Xs = [R || {R,_} <- Xs0],
-	    error({multiple_match_contexts,Xs});
-	[] ->
-	    ok
-    end.
+    F = fun({R, _Ctx}) ->
+                verify_call_match_context(Lbl, R, Vst)
+          end,
+    MsRegs = all_ms_in_x_regs(Live, Vst),
+    verify_no_ms_aliases(MsRegs),
+    foreach(F, MsRegs).
 
 all_ms_in_x_regs(0, _Vst) ->
     [];
@@ -1026,24 +1065,26 @@ all_ms_in_x_regs(Live0, Vst) ->
     Live = Live0 - 1,
     R = {x,Live},
     case get_move_term_type(R, Vst) of
-	#ms{}=M ->
-	    [{R,M}|all_ms_in_x_regs(Live, Vst)];
-	_ ->
-	    all_ms_in_x_regs(Live, Vst)
+        #ms{}=M -> [{R,M} | all_ms_in_x_regs(Live, Vst)];
+        _ -> all_ms_in_x_regs(Live, Vst)
     end.
 
-ms_in_y_regs(Id, #vst{current=#st{y=Ys0}}) ->
-    Ys = gb_trees:to_list(Ys0),
-    [{y,Y} || {Y,#ms{id=OtherId}} <- Ys, OtherId =:= Id].
+%% Verifies that the same match context isn't present twice.
+verify_no_ms_aliases(MsRegs) ->
+    CtxIds = [Id || {_, #ms{id=Id}} <- MsRegs],
+    UniqueCtxIds = ordsets:from_list(CtxIds),
+    if
+        length(UniqueCtxIds) < length(CtxIds) ->
+            error({multiple_match_contexts, MsRegs});
+        length(UniqueCtxIds) =:= length(CtxIds) ->
+            ok
+    end.
 
+%% Verifies that the target label accepts match contexts in the given register.
 verify_call_match_context(Lbl, Ctx, #vst{ft=Ft}) ->
-    case gb_trees:lookup(Lbl, Ft) of
-	none ->
-	    error(no_bs_start_match2);
-	{value,[{test,bs_start_match2,_,_,[Ctx,_],Ctx}|_]} ->
-	    ok;
-	{value,[{test,bs_start_match2,_,_,_,_}=I|_]} ->
-	    error({unsuitable_bs_start_match2,I})
+    case gb_trees:lookup({Lbl, Ctx}, Ft) of
+        {value, match_context} -> ok;
+        none -> error(no_bs_start_match2)
     end.
 
 allocate(Zero, Stk, Heap, Live, #vst{current=#st{numy=none}}=Vst0) ->
@@ -1212,6 +1253,8 @@ assert_unique_map_keys([_,_|_]=Ls) ->
 %%% New binary matching instructions.
 %%%
 
+bsm_match_state() ->
+    #ms{}.
 bsm_match_state(Slots) ->
     #ms{slots=Slots}.
 
@@ -1225,6 +1268,12 @@ bsm_get_context({x,X}=Reg, #vst{current=#st{x=Xs}}=_Vst) when is_integer(X) ->
 	{value,{fragile,#ms{}=Ctx}} -> Ctx;
 	_ -> error({no_bsm_context,Reg})
     end;
+bsm_get_context({y,Y}=Reg, #vst{current=#st{y=Ys}}=_Vst) when is_integer(Y) ->
+    case gb_trees:lookup(Y, Ys) of
+	{value,#ms{}=Ctx} -> Ctx;
+	{value,{fragile,#ms{}=Ctx}} -> Ctx;
+	_ -> error({no_bsm_context,Reg})
+    end;
 bsm_get_context(Reg, _) -> error({bad_source,Reg}).
 
 bsm_save(Reg, {atom,start}, Vst) ->
@@ -1255,6 +1304,7 @@ bsm_restore(Reg, SavePoint, Vst) ->
 	_ -> error({illegal_restore,SavePoint,range})
     end.
 
+
 select_val_branches(Src, Choices, Vst) ->
     Infer = infer_types(Src, Vst),
     select_val_branches_1(Choices, Infer, Vst).
diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl
index 74ad864163..d894694c79 100644
--- a/lib/compiler/src/compile.erl
+++ b/lib/compiler/src/compile.erl
@@ -248,6 +248,9 @@ expand_opt(report, Os) ->
     [report_errors,report_warnings|Os];
 expand_opt(return, Os) ->
     [return_errors,return_warnings|Os];
+expand_opt(no_bsm3, Os) ->
+    %% The new bsm pass requires bsm3 instructions.
+    [no_bsm3,no_bsm_opt|Os];
 expand_opt(r16, Os) ->
     expand_opt_before_21(Os);
 expand_opt(r17, Os) ->
@@ -259,13 +262,14 @@ expand_opt(r19, Os) ->
 expand_opt(r20, Os) ->
     expand_opt_before_21(Os);
 expand_opt(r21, Os) ->
-    [no_put_tuple2|Os];
+    [no_put_tuple2 | expand_opt(no_bsm3, Os)];
 expand_opt({debug_info_key,_}=O, Os) ->
     [encrypt_debug_info,O|Os];
 expand_opt(O, Os) -> [O|Os].
 
 expand_opt_before_21(Os) ->
-    [no_put_tuple2,no_get_hd_tl,no_ssa_opt_record,no_utf8_atoms|Os].
+    [no_put_tuple2, no_get_hd_tl, no_ssa_opt_record,
+     no_utf8_atoms | expand_opt(no_bsm3, Os)].
 
 %% format_error(ErrorDescriptor) -> string()
 
@@ -816,6 +820,9 @@ kernel_passes() ->
      {pass,beam_kernel_to_ssa},
      {iff,dssa,{listing,"ssa"}},
      {iff,ssalint,{pass,beam_ssa_lint}},
+     {unless,no_bsm_opt,{pass,beam_ssa_bsm}},
+     {iff,dssabsm,{listing,"ssabsm"}},
+     {iff,ssalint,{pass,beam_ssa_lint}},
      {unless,no_ssa_opt,{pass,beam_ssa_opt}},
      {iff,dssaopt,{listing,"ssaopt"}},
      {iff,ssalint,{pass,beam_ssa_lint}},
@@ -847,8 +854,6 @@ asm_passes() ->
 	 {iff,dpeep,{listing,"peep"}},
 	 {pass,beam_clean},
 	 {iff,dclean,{listing,"clean"}},
-	 {unless,no_bsm_opt,{pass,beam_bsm}},
-	 {iff,dbsm,{listing,"bsm"}},
 	 {unless,no_stack_trimming,{pass,beam_trim}},
 	 {iff,dtrim,{listing,"trim"}},
 	 {pass,beam_flatten}]},
@@ -2030,7 +2035,6 @@ pre_load() ->
 	 beam_asm,
 	 beam_block,
 	 beam_bs,
-	 beam_bsm,
 	 beam_clean,
 	 beam_dict,
 	 beam_except,
@@ -2040,6 +2044,7 @@ pre_load() ->
 	 beam_opcodes,
 	 beam_peep,
 	 beam_ssa,
+	 beam_ssa_bsm,
 	 beam_ssa_codegen,
 	 beam_ssa_dead,
 	 beam_ssa_opt,
diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src
index bb281376ef..7b802fdd62 100644
--- a/lib/compiler/src/compiler.app.src
+++ b/lib/compiler/src/compiler.app.src
@@ -25,7 +25,6 @@
 	     beam_asm,
 	     beam_block,
 	     beam_bs,
-	     beam_bsm,
 	     beam_clean,
 	     beam_dict,
 	     beam_disasm,
@@ -37,6 +36,7 @@
 	     beam_opcodes,
 	     beam_peep,
              beam_ssa,
+             beam_ssa_bsm,
              beam_ssa_codegen,
              beam_ssa_dead,
              beam_ssa_lint,
diff --git a/lib/compiler/src/genop.tab b/lib/compiler/src/genop.tab
index 8e34e3e291..86590fad87 100755
--- a/lib/compiler/src/genop.tab
+++ b/lib/compiler/src/genop.tab
@@ -574,7 +574,25 @@ BEAM_FORMAT_NUMBER=0
 ##       put it into the register Tail.
 163: get_tl/2
 
+# OTP 22
+
 ## @spec put_tuple2  Destination Elements
 ## @doc  Build a tuple with the elements in the list Elements and put it
 ##       put into register Destination.
 164: put_tuple2/2
+
+## @spec bs_get_tail Ctx Dst Live
+## @doc  Sets Dst to the tail of Ctx at the current position
+165: bs_get_tail/3
+
+## @spec bs_start_match3 Fail Bin Live Dst
+## @doc  Starts a binary match sequence
+166: bs_start_match3/4
+
+## @spec bs_get_position Ctx Dst Live
+## @doc  Sets Dst to the current position of Ctx
+167: bs_get_position/3
+
+## @spec bs_set_positon Ctx Pos
+## @doc  Sets the current position of Ctx to Pos
+168: bs_set_position/2
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) ->
diff --git a/system/doc/efficiency_guide/binaryhandling.xml b/system/doc/efficiency_guide/binaryhandling.xml
index b500329ef9..d92da17390 100644
--- a/system/doc/efficiency_guide/binaryhandling.xml
+++ b/system/doc/efficiency_guide/binaryhandling.xml
@@ -384,8 +384,8 @@ export ERL_COMPILER_OPTIONS=bin_opt_info]]></code>
     <p>The warnings look as follows:</p>
 
   <code type="erl"><![CDATA[
-./efficiency_guide.erl:60: Warning: NOT OPTIMIZED: sub binary is used or returned
-./efficiency_guide.erl:62: Warning: OPTIMIZED: creation of sub binary delayed]]></code>
+./efficiency_guide.erl:60: Warning: NOT OPTIMIZED: binary is returned from the function
+./efficiency_guide.erl:62: Warning: OPTIMIZED: match context reused]]></code>
 
     <p>To make it clearer exactly what code the warnings refer to, the
     warnings in the following examples are inserted as comments
@@ -393,10 +393,10 @@ export ERL_COMPILER_OPTIONS=bin_opt_info]]></code>
 
   <code type="erl"><![CDATA[
 after_zero(<<0,T/binary>>) ->
-         %% NOT OPTIMIZED: sub binary is used or returned
+         %% BINARY CREATED: binary is returned from the function
     T;
 after_zero(<<_,T/binary>>) ->
-         %% OPTIMIZED: creation of sub binary delayed
+         %% OPTIMIZED: match context reused
     after_zero(T);
 after_zero(<<>>) ->
     <<>>.]]></code>
-- 
cgit v1.2.3


From 0b40d88912decc938d738f5531abc7e7ef3c9820 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?John=20H=C3=B6gberg?= <john@erlang.org>
Date: Wed, 11 Jul 2018 11:01:05 +0200
Subject: beam_ssa_opt: Eliminate redundant match alignment tests

The beam_ssa_bsm pass welds chained matches together, but the match
expressions themselves are unchanged and if there's a tail
alignment check it will be done each time. This subpass figures out
the checks we've already done and deletes the redundant ones.
---
 lib/compiler/src/beam_ssa_opt.erl | 117 +++++++++++++++++++++++++++++++++++++-
 1 file changed, 116 insertions(+), 1 deletion(-)

diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl
index 89cfbd7a84..ac2d943fef 100644
--- a/lib/compiler/src/beam_ssa_opt.erl
+++ b/lib/compiler/src/beam_ssa_opt.erl
@@ -66,13 +66,15 @@ passes(Opts0) ->
           ?PASS(ssa_opt_live),                  %Second time.
 
           ?PASS(ssa_opt_bsm),
+          ?PASS(ssa_opt_bsm_units),
           ?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)],
+          ?PASS(ssa_opt_merge_blocks),
+          ?PASS(ssa_opt_trim_unreachable)],
     Negations = [{list_to_atom("no_"++atom_to_list(N)),N} ||
                     {N,_} <- Ps],
     Opts = proplists:substitute_negations(Negations, Opts0),
@@ -112,6 +114,9 @@ ssa_opt_type(#st{ssa=Linear,args=Args}=St) ->
 ssa_opt_blockify(#st{ssa=Linear}=St) ->
     St#st{ssa=maps:from_list(Linear)}.
 
+ssa_opt_trim_unreachable(#st{ssa=Blocks}=St) ->
+    St#st{ssa=beam_ssa:trim_unreachable(Blocks)}.
+
 %%%
 %%% Split blocks before certain instructions to enable more optimizations.
 %%%
@@ -1001,6 +1006,110 @@ bsm_shortcut([{L,#b_blk{is=Is,last=Last0}=Blk}|Bs], PosMap) ->
     end;
 bsm_shortcut([], _PosMap) -> [].
 
+%%%
+%%% Eliminate redundant bs_test_unit2 instructions.
+%%%
+
+ssa_opt_bsm_units(#st{ssa=Linear}=St) ->
+    St#st{ssa=bsm_units(Linear, #{})}.
+
+bsm_units([{L,#b_blk{last=#b_br{succ=Succ,fail=Fail}}=Block0} | Bs], UnitMaps0) ->
+    UnitsIn = maps:get(L, UnitMaps0, #{}),
+    {Block, UnitsOut} = bsm_units_skip(Block0, UnitsIn),
+    UnitMaps1 = bsm_units_join(Succ, UnitsOut, UnitMaps0),
+    UnitMaps = bsm_units_join(Fail, UnitsIn, UnitMaps1),
+    [{L, Block} | bsm_units(Bs, UnitMaps)];
+bsm_units([{L,#b_blk{last=#b_switch{fail=Fail,list=Switch}}=Block} | Bs], UnitMaps0) ->
+    UnitsIn = maps:get(L, UnitMaps0, #{}),
+    Labels = [Fail | [Lbl || {_Arg, Lbl} <- Switch]],
+    UnitMaps = foldl(fun(Lbl, UnitMaps) ->
+                             bsm_units_join(Lbl, UnitsIn, UnitMaps)
+                     end, UnitMaps0, Labels),
+    [{L, Block} | bsm_units(Bs, UnitMaps)];
+bsm_units([{L, Block} | Bs], UnitMaps) ->
+    [{L, Block} | bsm_units(Bs, UnitMaps)];
+bsm_units([], _UnitMaps) ->
+    [].
+
+bsm_units_skip(Block, Units) ->
+    bsm_units_skip_1(Block#b_blk.is, Block, Units).
+
+bsm_units_skip_1([#b_set{op=bs_start_match,dst=New}|_], Block, Units) ->
+    %% We bail early since there can't be more than one match per block.
+    {Block, Units#{ New => 1 }};
+bsm_units_skip_1([#b_set{op=bs_match,
+                         dst=New,
+                         args=[#b_literal{val=skip},
+                               Ctx,
+                               #b_literal{val=binary},
+                               _Flags,
+                               #b_literal{val=all},
+                               #b_literal{val=OpUnit}]}=Skip | Test],
+                 Block0, Units) ->
+    [#b_set{op=succeeded,dst=Bool,args=[New]}] = Test, %Assertion.
+    #b_br{bool=Bool} = Last0 = Block0#b_blk.last, %Assertion.
+    CtxUnit = maps:get(Ctx, Units),
+    if
+        CtxUnit rem OpUnit =:= 0 ->
+            Is = takewhile(fun(I) -> I =/= Skip end, Block0#b_blk.is),
+            Last = Last0#b_br{bool=#b_literal{val=true}},
+            Block = Block0#b_blk{is=Is,last=Last},
+            {Block, Units#{ New => CtxUnit }};
+        CtxUnit rem OpUnit =/= 0 ->
+            {Block0, Units#{ New => OpUnit, Ctx => OpUnit }}
+    end;
+bsm_units_skip_1([#b_set{op=bs_match,dst=New,args=Args}|_], Block, Units) ->
+    [_,Ctx|_] = Args,
+    CtxUnit = maps:get(Ctx, Units),
+    OpUnit = bsm_op_unit(Args),
+    {Block, Units#{ New => gcd(OpUnit, CtxUnit) }};
+bsm_units_skip_1([_I | Is], Block, Units) ->
+    bsm_units_skip_1(Is, Block, Units);
+bsm_units_skip_1([], Block, Units) ->
+    {Block, Units}.
+
+bsm_op_unit([_,_,_,Size,#b_literal{val=U}]) ->
+    case Size of
+        #b_literal{val=Sz} when is_integer(Sz) -> Sz*U;
+        _ -> U
+    end;
+bsm_op_unit([#b_literal{val=string},_,#b_literal{val=String}]) ->
+    bit_size(String);
+bsm_op_unit([#b_literal{val=utf8}|_]) ->
+    8;
+bsm_op_unit([#b_literal{val=utf16}|_]) ->
+    16;
+bsm_op_unit([#b_literal{val=utf32}|_]) ->
+    32;
+bsm_op_unit(_) ->
+    1.
+
+%% Several paths can lead to the same match instruction and the inferred units
+%% may differ between them, so we can only keep the information that is common
+%% to all paths.
+bsm_units_join(Lbl, MapA, UnitMaps0) when is_map_key(Lbl, UnitMaps0) ->
+    MapB = maps:get(Lbl, UnitMaps0),
+    Merged = if
+                 map_size(MapB) =< map_size(MapA) ->
+                     bsm_units_join_1(maps:keys(MapB), MapA, MapB);
+                 map_size(MapB) > map_size(MapA) ->
+                     bsm_units_join_1(maps:keys(MapA), MapB, MapA)
+             end,
+    maps:put(Lbl, Merged, UnitMaps0);
+bsm_units_join(Lbl, MapA, UnitMaps0) when MapA =/= #{} ->
+    maps:put(Lbl, MapA, UnitMaps0);
+bsm_units_join(_Lbl, _MapA, UnitMaps0) ->
+    UnitMaps0.
+
+bsm_units_join_1([Key | Keys], Left, Right) when is_map_key(Key, Left) ->
+    UnitA = maps:get(Key, Left),
+    UnitB = maps:get(Key, Right),
+    bsm_units_join_1(Keys, Left, maps:put(Key, gcd(UnitA, UnitB), Right));
+bsm_units_join_1([Key | Keys], Left, Right) ->
+    bsm_units_join_1(Keys, Left, maps:remove(Key, Right));
+bsm_units_join_1([], _MapA, Right) ->
+    Right.
+
 %%%
 %%% Miscellanous optimizations in execution order.
 %%%
@@ -1618,6 +1727,12 @@ insert_def_is([], _V, Def) ->
 %%% Common utilities.
 %%%
 
+gcd(A, B) ->
+    case A rem B of
+        0 -> B;
+        X -> gcd(B, X)
+    end.
+
 rel2fam(S0) ->
     S1 = sofs:relation(S0),
     S = sofs:rel2fam(S1),
-- 
cgit v1.2.3


From f9dcf726661c89c39b2c09932ba0bd5fe8339ae4 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Tue, 18 Sep 2018 14:06:59 +0200
Subject: Improve coverage of 21 compatibility

---
 lib/compiler/test/Makefile     | 15 +++++++++++++--
 lib/compiler/test/test_lib.erl |  9 +++++++--
 2 files changed, 20 insertions(+), 4 deletions(-)

diff --git a/lib/compiler/test/Makefile b/lib/compiler/test/Makefile
index 2a5004aa4c..e56594f344 100644
--- a/lib/compiler/test/Makefile
+++ b/lib/compiler/test/Makefile
@@ -97,6 +97,9 @@ INLINE= \
 	receive \
 	record
 
+R21= \
+        bs_match
+
 CORE_MODULES = \
 	lfe_andor_SUITE \
 	lfe_guard_SUITE
@@ -107,6 +110,8 @@ POST_OPT_MODULES= $(NO_OPT:%=%_post_opt_SUITE)
 POST_OPT_ERL_FILES= $(POST_OPT_MODULES:%=%.erl)
 INLINE_MODULES= $(INLINE:%=%_inline_SUITE)
 INLINE_ERL_FILES= $(INLINE_MODULES:%=%.erl)
+R21_MODULES= $(R21:%=%_r21_SUITE)
+R21_ERL_FILES= $(R21_MODULES:%=%.erl)
 
 ERL_FILES= $(MODULES:%=%.erl)
 CORE_FILES= $(CORE_MODULES:%=%.core)
@@ -135,7 +140,8 @@ EBIN = .
 # Targets
 # ----------------------------------------------------
 
-make_emakefile: $(NO_OPT_ERL_FILES) $(POST_OPT_ERL_FILES) $(INLINE_ERL_FILES)
+make_emakefile: $(NO_OPT_ERL_FILES) $(POST_OPT_ERL_FILES) \
+  $(INLINE_ERL_FILES) $(R21_ERL_FILES)
 	$(ERL_TOP)/make/make_emakefile $(ERL_COMPILE_FLAGS) -o$(EBIN) $(MODULES) \
 	> $(EMAKEFILE)
 	$(ERL_TOP)/make/make_emakefile +no_copt +no_postopt \
@@ -145,6 +151,8 @@ make_emakefile: $(NO_OPT_ERL_FILES) $(POST_OPT_ERL_FILES) $(INLINE_ERL_FILES)
 	-o$(EBIN) $(POST_OPT_MODULES) >> $(EMAKEFILE)
 	$(ERL_TOP)/make/make_emakefile +inline $(ERL_COMPILE_FLAGS) \
 	-o$(EBIN) $(INLINE_MODULES) >> $(EMAKEFILE)
+	$(ERL_TOP)/make/make_emakefile +r21 $(ERL_COMPILE_FLAGS) \
+	-o$(EBIN) $(R21_MODULES) >> $(EMAKEFILE)
 	$(ERL_TOP)/make/make_emakefile +from_core $(ERL_COMPILE_FLAGS) \
 	-o$(EBIN) $(CORE_MODULES) >> $(EMAKEFILE)
 
@@ -171,6 +179,9 @@ docs:
 %_inline_SUITE.erl: %_SUITE.erl
 	sed -e 's;-module($(basename $<));-module($(basename $@));' $< > $@
 
+%_r21_SUITE.erl: %_SUITE.erl
+	sed -e 's;-module($(basename $<));-module($(basename $@));' $< > $@
+
 # ----------------------------------------------------
 # Release Target
 # ---------------------------------------------------- 
@@ -183,7 +194,7 @@ release_tests_spec: make_emakefile
 	$(INSTALL_DATA) compiler.spec compiler.cover \
 		$(EMAKEFILE) $(ERL_FILES) "$(RELSYSDIR)"
 	$(INSTALL_DATA) $(NO_OPT_ERL_FILES) $(POST_OPT_ERL_FILES) \
-		$(INLINE_ERL_FILES) "$(RELSYSDIR)"
+		$(INLINE_ERL_FILES) $(R21_ERL_FILES) "$(RELSYSDIR)"
 	$(INSTALL_DATA) $(CORE_FILES) "$(RELSYSDIR)"
 	for file in $(ERL_DUMMY_FILES); do \
 	    module=`basename $$file .erl`; \
diff --git a/lib/compiler/test/test_lib.erl b/lib/compiler/test/test_lib.erl
index c6baa611ec..4502f5b68a 100644
--- a/lib/compiler/test/test_lib.erl
+++ b/lib/compiler/test/test_lib.erl
@@ -78,6 +78,9 @@ opt_opts(Mod) ->
 		    (no_stack_trimming) -> true;
 		    (debug_info) -> true;
 		    (inline) -> true;
+                    (no_put_tuple2) -> true;
+                    (no_bsm3) -> true;
+                    (no_bsm_opt) -> true;
 		    (_) -> false
 		 end, Opts).
 
@@ -89,8 +92,9 @@ get_data_dir(Config) ->
     Data0 = proplists:get_value(data_dir, Config),
     Opts = [{return,list}],
     Data1 = re:replace(Data0, "_no_opt_SUITE", "_SUITE", Opts),
-    Data = re:replace(Data1, "_post_opt_SUITE", "_SUITE", Opts),
-    re:replace(Data, "_inline_SUITE", "_SUITE", Opts).
+    Data2 = re:replace(Data1, "_post_opt_SUITE", "_SUITE", Opts),
+    Data = re:replace(Data2, "_inline_SUITE", "_SUITE", Opts),
+    re:replace(Data, "_r21_SUITE", "_SUITE", Opts).
 
 is_cloned_mod(Mod) ->
     is_cloned_mod_1(atom_to_list(Mod)).
@@ -100,6 +104,7 @@ is_cloned_mod(Mod) ->
 is_cloned_mod_1("no_opt_SUITE") -> true;
 is_cloned_mod_1("post_opt_SUITE") -> true;
 is_cloned_mod_1("inline_SUITE") -> true;
+is_cloned_mod_1("21_SUITE") -> true;
 is_cloned_mod_1([_|T]) -> is_cloned_mod_1(T);
 is_cloned_mod_1([]) -> false.
 
-- 
cgit v1.2.3


From 330629264c93535f352dc09b51d34f11ec791eb6 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 20 Sep 2018 15:57:09 +0200
Subject: beam_ssa_pre_codegen: Remove unused variable aliasing support

Remove the variable aliasing support that was needed for the
old beam_bsm pass.
---
 lib/compiler/src/beam_ssa_pre_codegen.erl | 120 ++++--------------------------
 1 file changed, 15 insertions(+), 105 deletions(-)

diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl
index e949aab722..9b5f52d26b 100644
--- a/lib/compiler/src/beam_ssa_pre_codegen.erl
+++ b/lib/compiler/src/beam_ssa_pre_codegen.erl
@@ -107,7 +107,6 @@ functions([], _Ps, _UseBSM3) -> [].
              use_bsm3 :: boolean(),
              frames=[] :: [beam_ssa:label()],
              intervals=[] :: [{b_var(),[range()]}],
-             aliases=[] :: [{b_var(),b_var()}],
              res=[] :: [{b_var(),reservation()}] | #{b_var():=reservation()},
              regs=#{} :: #{b_var():=ssa_register()},
              extra_annos=[] :: [{atom(),term()}]
@@ -141,9 +140,7 @@ passes(Opts) ->
           %% Calculate live intervals.
           ?PASS(number_instructions),
           ?PASS(live_intervals),
-          ?PASS(remove_unsuitable_aliases),
           ?PASS(reserve_regs),
-          ?PASS(merge_intervals),
 
           %% If needed for a .precg file, save the live intervals
           %% so they can be included in an annotation.
@@ -154,7 +151,6 @@ passes(Opts) ->
 
           %% Allocate registers.
           ?PASS(linear_scan),
-          ?PASS(fix_aliased_regs),
           ?PASS(frame_size),
           ?PASS(turn_yregs)],
     [P || P <- Ps, P =/= ignore].
@@ -178,14 +174,6 @@ function(#b_function{anno=Anno,args=Args,bs=Blocks0,cnt=Count0}=F0,
 save_live_intervals(#st{intervals=Intervals}=St) ->
     St#st{extra_annos=[{live_intervals,Intervals}]}.
 
-fix_aliased_regs(#st{aliases=Aliases,regs=Regs}=St) ->
-    St#st{regs=fix_aliased_regs(Aliases, Regs)}.
-
-fix_aliased_regs([{Alias,V}|Aliases], Regs) ->
-    #{V:=Reg} = Regs,
-    fix_aliased_regs(Aliases, Regs#{Alias=>Reg});
-fix_aliased_regs([], Regs) -> Regs.
-
 %% Add extra annotations when a .precg listing file is being produced.
 add_extra_annos(F, Annos) ->
     foldl(fun({Name,Value}, Acc) ->
@@ -1611,10 +1599,10 @@ live_intervals(#st{args=Args,ssa=Blocks}=St) ->
     Vars0 = [{V,{0,1}} || #b_var{}=V <- Args],
     F = fun(L, _, A) -> live_interval_blk(L, Blocks, A) end,
     LiveMap0 = #{},
-    Acc0 = {[],[],LiveMap0},
-    {Vars,Aliases,_} = beam_ssa:fold_po(F, Acc0, Blocks),
+    Acc0 = {[],LiveMap0},
+    {Vars,_} = beam_ssa:fold_po(F, Acc0, Blocks),
     Intervals = merge_ranges(rel2fam(Vars0++Vars)),
-    St#st{intervals=Intervals,aliases=Aliases}.
+    St#st{intervals=Intervals}.
 
 merge_ranges([{V,Rs}|T]) ->
     [{V,merge_ranges_1(Rs)}|merge_ranges(T)];
@@ -1626,7 +1614,7 @@ merge_ranges_1([R|Rs]) ->
     [R|merge_ranges_1(Rs)];
 merge_ranges_1([]) -> [].
 
-live_interval_blk(L, Blocks, {Vars0,Aliases0,LiveMap0}) ->
+live_interval_blk(L, Blocks, {Vars0,LiveMap0}) ->
     Live0 = [],
     Successors = beam_ssa:successors(L, Blocks),
     Live1 = update_successors(Successors, L, Blocks, LiveMap0, Live0),
@@ -1638,8 +1626,7 @@ live_interval_blk(L, Blocks, {Vars0,Aliases0,LiveMap0}) ->
 
     %% Determine used and defined variables in this block.
     FirstNumber = first_number(Is, Last),
-    {UseDef0,Aliases} = live_interval_blk_1([Last|reverse(Is)],
-                                            FirstNumber, Aliases0, Use),
+    UseDef0 = live_interval_blk_1([Last|reverse(Is)], FirstNumber, Use),
     UseDef = rel2fam(UseDef0),
 
     %% Update what is live at the beginning of this block and
@@ -1652,7 +1639,7 @@ live_interval_blk(L, Blocks, {Vars0,Aliases0,LiveMap0}) ->
 
     %% Construct the ranges for this block.
     Vars = make_block_ranges(UseDef, FirstNumber, Vars0),
-    {Vars,Aliases,LiveMap}.
+    {Vars,LiveMap}.
 
 make_block_ranges([{V,[{def,Def}]}|Vs], First, Acc) ->
     make_block_ranges(Vs, First, [{V,{Def,Def}}|Acc]);
@@ -1664,18 +1651,17 @@ make_block_ranges([{V,[{use,_}|_]=Uses}|Vs], First, Acc) ->
     make_block_ranges(Vs, First, [{V,{First,Last}}|Acc]);
 make_block_ranges([], _, Acc) -> Acc.
 
-live_interval_blk_1([#b_set{op=phi,dst=Dst}|Is],
-                    FirstNumber, Aliases, Acc0) ->
+live_interval_blk_1([#b_set{op=phi,dst=Dst}|Is], FirstNumber, Acc0) ->
     Acc = [{Dst,{def,FirstNumber}}|Acc0],
-    live_interval_blk_1(Is, FirstNumber, Aliases, Acc);
-live_interval_blk_1([#b_set{op=bs_start_match}=I|Is], FirstNumber,
-                    Aliases, Acc0) ->
+    live_interval_blk_1(Is, FirstNumber, Acc);
+live_interval_blk_1([#b_set{op=bs_start_match}=I|Is],
+                    FirstNumber, Acc0) ->
     N = beam_ssa:get_anno(n, I),
     #b_set{dst=Dst} = I,
     Acc1 = [{Dst,{def,N}}|Acc0],
     Acc = [{V,{use,N}} || V <- beam_ssa:used(I)] ++ Acc1,
-    live_interval_blk_1(Is, FirstNumber, Aliases, Acc);
-live_interval_blk_1([I|Is], FirstNumber, Aliases, Acc0) ->
+    live_interval_blk_1(Is, FirstNumber, Acc);
+live_interval_blk_1([I|Is], FirstNumber, Acc0) ->
     N = beam_ssa:get_anno(n, I),
     Acc1 = case I of
                #b_set{dst=Dst} ->
@@ -1685,9 +1671,9 @@ live_interval_blk_1([I|Is], FirstNumber, Aliases, Acc0) ->
            end,
     Used = beam_ssa:used(I),
     Acc = [{V,{use,N}} || V <- Used] ++ Acc1,
-    live_interval_blk_1(Is, FirstNumber, Aliases, Acc);
-live_interval_blk_1([], _FirstNumber, Aliases, Acc) ->
-    {Acc,Aliases}.
+    live_interval_blk_1(Is, FirstNumber, Acc);
+live_interval_blk_1([], _FirstNumber, Acc) ->
+    Acc.
 
 %% first_number([#b_set{}]) -> InstructionNumber.
 %%  Return the number for the first instruction for the block.
@@ -2123,82 +2109,6 @@ res_xregs_prune(Xs, Used, Res) ->
     %% preferred registers.
     maps:filter(fun(_, {x,X}) -> X < NumSafe end, Xs).
 
-%%%
-%%% Remove unsuitable aliases.
-%%%
-%%% If a binary is matched more than once, we must not put the
-%%% the match context in the same register as the binary to
-%%% avoid the following situation:
-%%%
-%%%     {test,bs_start_match2,{f,3},1,[{x,0},0],{x,0}}.
-%%%          .
-%%%          .
-%%%          .
-%%%     {test,bs_start_match2,{f,6},1,[{x,0},0],{x,1}}. %% ILLEGAL!
-%%%
-%%% The second instruction is illegal because a match context source
-%%% is only allowed if source and destination registers are identical.
-%%%
-
-remove_unsuitable_aliases(#st{aliases=[_|_]=Aliases0,ssa=Blocks}=St) ->
-    R = rem_unsuitable(maps:values(Blocks)),
-    Unsuitable0 = [V || {V,[_,_|_]} <- rel2fam(R)],
-    Unsuitable = gb_sets:from_list(Unsuitable0),
-    Aliases =[P || {_,V}=P <- Aliases0,
-                   not gb_sets:is_member(V, Unsuitable)],
-    St#st{aliases=Aliases};
-remove_unsuitable_aliases(#st{aliases=[]}=St) -> St.
-
-rem_unsuitable([#b_blk{is=Is}|Bs]) ->
-    Vs = [{Var,Dst} ||
-          #b_set{op=bs_start_match,dst=Dst,
-                 args=[#b_var{}=Var]} <- Is],
-    Vs ++ rem_unsuitable(Bs);
-rem_unsuitable([]) -> [].
-
-%%%
-%%% Merge intervals.
-%%%
-
-merge_intervals(#st{aliases=Aliases0,intervals=Intervals0,
-                    res=Reserved}=St) ->
-    Aliases1 = [A || A <- Aliases0,
-                     is_suitable_alias(A, Reserved)],
-    case Aliases1 of
-        [] ->
-            St#st{aliases=Aliases1};
-        [_|_] ->
-            Intervals1 = maps:from_list(Intervals0),
-            {Intervals,Aliases} =
-                merge_intervals_1(Aliases1, Intervals1, []),
-            St#st{aliases=Aliases,intervals=Intervals}
-    end.
-
-merge_intervals_1([{Alias,V}|Vs], Intervals0, Acc) ->
-    #{Alias:=Int1,V:=Int2} = Intervals0,
-    Int3 = lists:merge(Int1, Int2),
-    Int = merge_intervals_2(Int3),
-    Intervals1 = maps:remove(Alias, Intervals0),
-    Intervals = Intervals1#{V:=Int},
-    merge_intervals_1(Vs, Intervals, [{Alias,V}|Acc]);
-merge_intervals_1([], Intervals, Acc) ->
-    {maps:to_list(Intervals),Acc}.
-
-merge_intervals_2([{A1,B1},{A2,B2}|Is]) when A2 =< B1 ->
-    merge_intervals_2([{min(A1, A2),max(B1, B2)}|Is]);
-merge_intervals_2([{_A1,B1}=R|[{A2,_B2}|_]=Is]) when B1 < A2 ->
-    [R|merge_intervals_2(Is)];
-merge_intervals_2([_]=Is) -> Is.
-
-is_suitable_alias({V1,V2}, Reserved) ->
-    #{V1:=Res1,V2:=Res2} = Reserved,
-    case {Res1,Res2} of
-        {x,x} -> true;
-        {x,{x,_}} -> true;
-        {{x,_},x} -> true;
-        {_,_} -> false
-    end.
-
 %%%
 %%% Register allocation using linear scan.
 %%%
-- 
cgit v1.2.3


From 1fbaf155b579bfb1fdec4ac97f7b5fa2211673c6 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?John=20H=C3=B6gberg?= <john@erlang.org>
Date: Mon, 24 Sep 2018 08:10:18 +0200
Subject: Remove unused instruction bs_context_to_binary from the compiler

This has been superseded by bs_get_tail/3. Note that it is NOT
removed from the emulator or beam_disasm, as old modules are still
legal.
---
 lib/compiler/src/beam_jump.erl          |  2 --
 lib/compiler/src/beam_kernel_to_ssa.erl |  4 ----
 lib/compiler/src/beam_ssa.erl           |  2 +-
 lib/compiler/src/beam_ssa_codegen.erl   |  3 ---
 lib/compiler/src/beam_utils.erl         |  5 -----
 lib/compiler/src/beam_validator.erl     | 11 -----------
 lib/compiler/src/v3_kernel.erl          |  1 -
 7 files changed, 1 insertion(+), 27 deletions(-)

diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl
index 6d0a8db2dc..fbff4cfd79 100644
--- a/lib/compiler/src/beam_jump.erl
+++ b/lib/compiler/src/beam_jump.erl
@@ -367,8 +367,6 @@ extract_seq([{line,_}=Line|Is], Acc) ->
     extract_seq(Is, [Line|Acc]);
 extract_seq([{block,_}=Bl|Is], Acc) ->
     extract_seq_1(Is, [Bl|Acc]);
-extract_seq([{bs_context_to_binary,_}=I|Is], Acc) ->
-    extract_seq_1(Is, [I|Acc]);
 extract_seq([{label,_}|_]=Is, Acc) ->
     extract_seq_1(Is, Acc);
 extract_seq(_, _) -> no.
diff --git a/lib/compiler/src/beam_kernel_to_ssa.erl b/lib/compiler/src/beam_kernel_to_ssa.erl
index 747bb06d76..d6e675ae72 100644
--- a/lib/compiler/src/beam_kernel_to_ssa.erl
+++ b/lib/compiler/src/beam_kernel_to_ssa.erl
@@ -707,10 +707,6 @@ bif_cg(#k_bif{op=#k_remote{mod=#k_atom{val=erlang},name=#k_atom{val=Name}},
 %% internal_cg(Bif, [Arg], [Ret], Le, State) ->
 %%      {[Ainstr],State}.
 
-internal_cg(bs_context_to_binary, [Src0], [], _Le, St) ->
-    Src = ssa_arg(Src0, St),
-    Set = #b_set{op=context_to_binary,args=[Src]},
-    {[Set],St};
 internal_cg(dsetelement, [Index0,Tuple0,New0], _Rs, _Le, St) ->
     [New,Tuple,#b_literal{val=Index1}] = ssa_args([New0,Tuple0,Index0], St),
     Index = #b_literal{val=Index1-1},
diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl
index 6e0f5fffe3..1a2e759965 100644
--- a/lib/compiler/src/beam_ssa.erl
+++ b/lib/compiler/src/beam_ssa.erl
@@ -98,7 +98,7 @@
 -type prim_op() :: 'bs_add' | 'bs_extract' | 'bs_init' | 'bs_init_writable' |
                    'bs_match' | 'bs_put' | 'bs_start_match' | 'bs_test_tail' |
                    'bs_utf16_size' | 'bs_utf8_size' | 'build_stacktrace' |
-                   'call' | 'catch_end' | 'context_to_binary' |
+                   'call' | 'catch_end' |
                    'extract' |
                    'get_hd' | 'get_map_element' | 'get_tl' | 'get_tuple_element' |
                    'has_map_field' |
diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl
index 281e953127..1c7563faa0 100644
--- a/lib/compiler/src/beam_ssa_codegen.erl
+++ b/lib/compiler/src/beam_ssa_codegen.erl
@@ -345,7 +345,6 @@ classify_heap_need(bs_utf8_size) -> neutral;
 classify_heap_need(build_stacktrace) -> gc;
 classify_heap_need(call) -> gc;
 classify_heap_need(catch_end) -> gc;
-classify_heap_need(context_to_binary) -> gc;
 classify_heap_need(copy) -> neutral;
 classify_heap_need(extract) -> gc;
 classify_heap_need(get_hd) -> neutral;
@@ -1395,8 +1394,6 @@ cg_instr(bs_set_position, [Ctx,Pos], _Dst) ->
     [{bs_set_position,Ctx,Pos}];
 cg_instr(build_stacktrace, Args, Dst) ->
     setup_args(Args) ++ [build_stacktrace|copy({x,0}, Dst)];
-cg_instr(context_to_binary, [Src], _Dst) ->
-    [{bs_context_to_binary,Src}];
 cg_instr(set_tuple_element=Op, [New,Tuple,{integer,Index}], _Dst) ->
     [{Op,New,Tuple,Index}];
 cg_instr({float,clearerror}, [], _Dst) ->
diff --git a/lib/compiler/src/beam_utils.erl b/lib/compiler/src/beam_utils.erl
index 686d314c2d..626e041ea0 100644
--- a/lib/compiler/src/beam_utils.erl
+++ b/lib/compiler/src/beam_utils.erl
@@ -458,11 +458,6 @@ check_liveness(R, [{get_tuple_element,S,_,D}|Is], St) ->
 	D -> {killed,St};
 	_ -> check_liveness(R, Is, St)
     end;
-check_liveness(R, [{bs_context_to_binary,S}|Is], St) ->
-    case R of
-	S -> {used,St};
-	_ -> check_liveness(R, Is, St)
-    end;
 check_liveness(R, [{loop_rec,{f,_},{x,0}}|_], St) ->
     case R of
 	{x,_} ->
diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index fbcbb2cb4a..3d3fa10706 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -286,17 +286,6 @@ valfun_1({try_case_end,Src}, Vst) ->
     assert_term(Src, Vst),
     kill_state(Vst);
 %% Instructions that cannot cause exceptions
-valfun_1({bs_context_to_binary,Ctx}, #vst{current=#st{x=Xs}}=Vst) ->
-    case Ctx of
-	{Tag,X} when Tag =:= x; Tag =:= y ->
-	    Type = case gb_trees:lookup(X, Xs) of
-		       {value,#ms{}} -> term;
-		       _ -> get_term_type(Ctx, Vst)
-		   end,
-	    set_type_reg(Type, Ctx, Vst);
-	_ ->
-	    error({bad_source,Ctx})
-    end;
 valfun_1({bs_get_tail,Ctx,Dst,Live}, Vst0) ->
     verify_live(Live, Vst0),
     verify_y_init(Vst0),
diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl
index 07fd1b2a0e..f7ca66b1da 100644
--- a/lib/compiler/src/v3_kernel.erl
+++ b/lib/compiler/src/v3_kernel.erl
@@ -1415,7 +1415,6 @@ is_remote_bif(_, _, _) -> false.
 %%  called for effect only.
 
 bif_vals(dsetelement, 3) -> 0;
-bif_vals(bs_context_to_binary, 1) -> 0;
 bif_vals(_, _) -> 1.
 
 bif_vals(_, _, _) -> 1.
-- 
cgit v1.2.3


From afa36d2081927c46a4c3ddceb40276fc7756bb51 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?John=20H=C3=B6gberg?= <john@erlang.org>
Date: Mon, 24 Sep 2018 08:03:21 +0200
Subject: hipe: Document new limitations and disable known failing tests

---
 lib/hipe/doc/src/hipe_app.xml                      |  7 +++
 lib/hipe/test/Makefile                             |  1 -
 .../basic_SUITE_data/basic_inline_function.erl     | 73 ----------------------
 3 files changed, 7 insertions(+), 74 deletions(-)
 delete mode 100644 lib/hipe/test/basic_SUITE_data/basic_inline_function.erl

diff --git a/lib/hipe/doc/src/hipe_app.xml b/lib/hipe/doc/src/hipe_app.xml
index 99759a2f2c..480290cd9e 100644
--- a/lib/hipe/doc/src/hipe_app.xml
+++ b/lib/hipe/doc/src/hipe_app.xml
@@ -62,6 +62,13 @@
       and the runtime system that have limited or no support for HiPE compiled modules.
     </p>
     <taglist>
+      <tag>Binary matching</tag>
+      <item><p>The HiPE compiler will crash on modules containing binary
+      matching unless they have been compiled with the <c>+no_bsm3</c> flag.
+      Note that this will disable all related optimizations done by the BEAM
+      compiler.</p>
+      </item>
+
       <tag>Stack traces</tag>
       <item><p>Stack traces returned from <seealso marker="erts:erlang#get_stacktrace/0">
       <c>erlang:get_stacktrace/0</c></seealso> or as part of <c>'EXIT'</c> terms
diff --git a/lib/hipe/test/Makefile b/lib/hipe/test/Makefile
index efeb0887ab..3650cda663 100644
--- a/lib/hipe/test/Makefile
+++ b/lib/hipe/test/Makefile
@@ -13,7 +13,6 @@ MODULES= \
 # .erl files for these modules are automatically generated
 GEN_MODULES= \
 	basic_SUITE \
-	bs_SUITE \
 	maps_SUITE \
 	sanity_SUITE
 
diff --git a/lib/hipe/test/basic_SUITE_data/basic_inline_function.erl b/lib/hipe/test/basic_SUITE_data/basic_inline_function.erl
deleted file mode 100644
index 4c08064670..0000000000
--- a/lib/hipe/test/basic_SUITE_data/basic_inline_function.erl
+++ /dev/null
@@ -1,73 +0,0 @@
-%%% -*- erlang-indent-level: 2 -*-
-%%%-------------------------------------------------------------------
-%%% Author: Kostis Sagonas
-%%%
-%%% Contains tests that depend on the compiler inliner being turned on.
-%%%-------------------------------------------------------------------
--module(basic_inline_function).
-
--export([test/0]).
-
--compile({inline, [{to_objects, 3}]}).
-
-test() ->
-  ok = test_inline_match(),
-  ok.
-
-%%--------------------------------------------------------------------
-
-test_inline_match() ->
-  bad_object = test1(a, {binary, foo, set}, c),
-  bad_object = test2(a, {binary, foo, set}, c),
-  bad_object = test3(a, {binary, foo, set}, c),
-  ok.
-
-%% Inlined
-test1(KeysObjs, C, Ts) ->
-  case catch to_objects(KeysObjs, C, Ts) of
-    {'EXIT', _} ->
-      bad_object;
-    ok ->
-      ok
-  end.
-
-%% "Inlined" by hand
-test2(KeysObjs, C, _Ts) ->
-  case catch (case C of
-		{binary, _, set} ->
-		  <<_ObjSz0:32, _T/binary>> = KeysObjs;
-		_ -> ok
-	      end) of
-    {'EXIT', _} ->
-      bad_object;
-    ok ->
-      ok
-  end.
-
-%% Not inlined
-test3(KeysObjs, C, Ts) ->
-  case catch fto_objects(KeysObjs, C, Ts) of
-    {'EXIT', _} ->
-      bad_object;
-    ok ->
-      ok
-  end.
-
-%% Inlined.
-to_objects(Bin, {binary, _, set}, _Ts) ->
-  <<_ObjSz0:32, _T/binary>> = Bin,
-  ok;
-to_objects(<<_ObjSz0:32, _T/binary>> ,_, _) ->
-  ok;
-to_objects(_Bin, _, _Ts) ->
-  ok.
-
-%% Not Inlined.
-fto_objects(Bin, {binary, _, set}, _Ts) ->
-  <<_ObjSz0:32, _T/binary>> = Bin,
-  ok;
-fto_objects(<<_ObjSz0:32, _T/binary>> ,_,_) ->
-  ok;
-fto_objects(_Bin, _, _Ts) ->
-  ok.
-
-- 
cgit v1.2.3