Merge tag 'OTP-19.0' into sverker/19/binary_to_atom-utf8-crash/ERL-474/OTP-14590

1 files changed, 314 insertions, 456 deletions

diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index eb72290306..4c0cb6780a 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -1,18 +1,19 @@
 %%
 %% %CopyrightBegin%
 %%
-%% Copyright Ericsson AB 2004-2013. All Rights Reserved.
+%% Copyright Ericsson AB 2004-2016. All Rights Reserved.
 %%
-%% The contents of this file are subject to the Erlang Public License,
-%% Version 1.1, (the "License"); you may not use this file except in
-%% compliance with the License. You should have received a copy of the
-%% Erlang Public License along with this software. If not, it can be
-%% retrieved online at http://www.erlang.org/.
+%% 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
 %%
-%% Software distributed under the License is distributed on an "AS IS"
-%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
-%% the License for the specific language governing rights and limitations
-%% under the License.
+%%     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%
 
@@ -22,56 +23,20 @@
 
 %% Avoid warning for local function error/1 clashing with autoimported BIF.
 -compile({no_auto_import,[error/1]}).
--export([file/1, files/1]).
 
 %% Interface for compiler.
 -export([module/2, format_error/1]).
 
 -include("beam_disasm.hrl").
 
--import(lists, [reverse/1,foldl/3,foreach/2,member/2,dropwhile/2]).
-
--define(MAXREG, 1024).
-
-%%-define(DEBUG, 1).
--ifdef(DEBUG).
--define(DBG_FORMAT(F, D), (io:format((F), (D)))).
--else.
--define(DBG_FORMAT(F, D), ok).
--endif.
-
-%%%
-%%% API functions.
-%%%
-
--spec file(file:filename()) -> 'ok' | {'error', term()}.
-
-file(Name) when is_list(Name) ->
-    case case filename:extension(Name) of
-	     ".S" -> s_file(Name);
-	     ".beam" -> beam_file(Name)
-	 end of
-	[] -> ok;
-	Es -> {error,Es}
-    end.
-
--spec files([file:filename()]) -> 'ok'.
-
-files([F|Fs]) ->
-    ?DBG_FORMAT("# Verifying: ~p~n", [F]),
-    case file(F) of
-	ok -> ok;
-	{error,Es} -> 
-	    io:format("~tp:~n~ts~n", [F,format_error(Es)])
-    end,
-    files(Fs);
-files([]) -> ok.
+-import(lists, [reverse/1,foldl/3,foreach/2,dropwhile/2]).
 
 %% To be called by the compiler.
 module({Mod,Exp,Attr,Fs,Lc}=Code, _Opts)
   when is_atom(Mod), is_list(Exp), is_list(Attr), is_integer(Lc) ->
     case validate(Mod, Fs) of
-	[] -> {ok,Code};
+	[] ->
+	    {ok,Code};
 	Es0 ->
 	    Es = [{?MODULE,E} || E <- Es0],
 	    {error,[{atom_to_list(Mod),Es}]}
@@ -79,12 +44,6 @@ module({Mod,Exp,Attr,Fs,Lc}=Code, _Opts)
 
 -spec format_error(term()) -> iolist().
 
-format_error([]) -> [];
-format_error([{{M,F,A},{I,Off,Desc}}|Es]) ->
-    [io_lib:format("  ~p:~p/~p+~p:~n    ~p - ~p~n", 
-		   [M,F,A,Off,I,Desc])|format_error(Es)];
-format_error([Error|Es]) ->
-    [format_error(Error)|format_error(Es)];
 format_error({{_M,F,A},{I,Off,limit}}) ->
     io_lib:format(
       "function ~p/~p+~p:~n"
@@ -103,8 +62,6 @@ format_error({{_M,F,A},{I,Off,Desc}}) ->
       "  Internal consistency check failed - please report this bug.~n"
       "  Instruction: ~p~n"
       "  Error:       ~p:~n", [F,A,Off,I,Desc]);
-format_error({Module,Error}) ->
-    [Module:format_error(Error)];
 format_error(Error) ->
     io_lib:format("~p~n", [Error]).
 
@@ -112,36 +69,6 @@ format_error(Error) ->
 %%% Local functions follow.
 %%% 
 
-s_file(Name) ->
-    {ok,Is} = file:consult(Name),
-    {module,Module} = lists:keyfind(module, 1, Is),
-    Fs = find_functions(Is),
-    validate(Module, Fs).
-
-find_functions(Fs) ->
-    find_functions_1(Fs, none, [], []).
-
-find_functions_1([{function,Name,Arity,Entry}|Is], Func, FuncAcc, Acc0) ->
-    Acc = add_func(Func, FuncAcc, Acc0),
-    find_functions_1(Is, {Name,Arity,Entry}, [], Acc);
-find_functions_1([I|Is], Func, FuncAcc, Acc) ->
-    find_functions_1(Is, Func, [I|FuncAcc], Acc);
-find_functions_1([], Func, FuncAcc, Acc) ->
-    reverse(add_func(Func, FuncAcc, Acc)).
-
-add_func(none, _, Acc) -> Acc;
-add_func({Name,Arity,Entry}, Is, Acc) ->
-    [{function,Name,Arity,Entry,reverse(Is)}|Acc].
-
-beam_file(Name) ->
-    try beam_disasm:file(Name) of
-	{error,beam_lib,Reason} -> [{beam_lib,Reason}];
-	#beam_file{module=Module, code=Code0} ->
-	    Code = normalize_disassembled_code(Code0),
-	    validate(Module, Code)
-    catch _:_ -> [disassembly_failed]
-    end.
-
 %%%
 %%% The validator follows.
 %%%
@@ -196,68 +123,63 @@ validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) ->
     try validate_1(Code, Name, Ar, Entry, Ft) of
 	_ -> validate_0(Module, Fs, Ft)
     catch
-	Error ->
+	throw:Error ->
+	    %% Controlled error.
 	    [Error|validate_0(Module, Fs, Ft)];
-	  error:Error ->
-	    [validate_error(Error, Module, Name, Ar)|validate_0(Module, Fs, Ft)]
+	Class:Error ->
+	    %% Crash.
+	    Stack = erlang:get_stacktrace(),
+	    io:fwrite("Function: ~w/~w\n", [Name,Ar]),
+	    erlang:raise(Class, Error, Stack)
     end.
 
--ifdef(DEBUG).
-validate_error(Error, Module, Name, Ar) ->
-    exit(validate_error_1(Error, Module, Name, Ar)).
--else.
-validate_error(Error, Module, Name, Ar) ->
-    validate_error_1(Error, Module, Name, Ar).
--endif.
-validate_error_1(Error, Module, Name, Ar) ->
-    {{Module,Name,Ar},
-     {internal_error,'_',{Error,erlang:get_stacktrace()}}}.
+-type index() :: non_neg_integer().
+-type reg_tab() :: gb_trees:tree(index(), 'none' | {'value', _}).
 
 -record(st,				%Emulation state
-	{x=init_regs(0, term)        :: gb_tree(),	%x register info.
-	 y=init_regs(0, initialized) :: gb_tree(),	%y register info.
+	{x=init_regs(0, term)        :: reg_tab(),%x register info.
+	 y=init_regs(0, initialized) :: reg_tab(),%y register info.
 	 f=init_fregs(),                %
 	 numy=none,			%Number of y registers.
 	 h=0,				%Available heap size.
 	 hf=0,				%Available heap size for floats.
 	 fls=undefined,			%Floating point state.
 	 ct=[],				%List of hot catch/try labels
-	 bsm=undefined,			%Bit syntax matching state.
-	 bits=undefined,	        %Number of bits in bit syntax binary.
 	 setelem=false			%Previous instruction was setelement/3.
 	}).
 
+-type label()        :: integer().
+-type label_set()    :: gb_sets:set(label()).
+-type branched_tab() :: gb_trees:tree(label(), #st{}).
+-type ft_tab()       :: gb_trees:tree().
+
 -record(vst,				%Validator state
 	{current=none              :: #st{} | 'none',	%Current state
-	 branched=gb_trees:empty() :: gb_tree(),	%States at jumps
-	 labels=gb_sets:empty()    :: gb_set(),		%All defined labels
-	 ft=gb_trees:empty()       :: gb_tree()         %Some other functions
+	 branched=gb_trees:empty() :: branched_tab(),	%States at jumps
+	 labels=gb_sets:empty()    :: label_set(),	%All defined labels
+	 ft=gb_trees:empty()       :: ft_tab()          %Some other functions
 	 		% in the module (those that start with bs_start_match2).
 	}).
 
--ifdef(DEBUG).
-print_st(#st{x=Xs,y=Ys,numy=NumY,h=H,ct=Ct}) ->
-    io:format("  #st{x=~p~n"
-	      "      y=~p~n"
-	      "      numy=~p,h=~p,ct=~w~n",
-	      [gb_trees:to_list(Xs),gb_trees:to_list(Ys),NumY,H,Ct]).
--endif.
+%% Match context type.
+-record(ms,
+	{id=make_ref() :: reference(),		%Unique ID.
+	 valid=0 :: non_neg_integer(),		%Valid slots
+	 slots=0 :: non_neg_integer()		%Number of slots
+	}).
 
 validate_1(Is, Name, Arity, Entry, Ft) ->
     validate_2(labels(Is), Name, Arity, Entry, Ft).
 
 validate_2({Ls1,[{func_info,{atom,Mod},{atom,Name},Arity}=_F|Is]},
 	   Name, Arity, Entry, Ft) ->
-    lists:foreach(fun (_L) -> ?DBG_FORMAT("  ~p.~n", [{label,_L}]) end, Ls1),
-    ?DBG_FORMAT("  ~p.~n", [_F]),
     validate_3(labels(Is), Name, Arity, Entry, Mod, Ls1, Ft);
 validate_2({Ls1,Is}, Name, Arity, _Entry, _Ft) ->
     error({{'_',Name,Arity},{first(Is),length(Ls1),illegal_instruction}}).
 
 validate_3({Ls2,Is}, Name, Arity, Entry, Mod, Ls1, Ft) ->
-    lists:foreach(fun (_L) -> ?DBG_FORMAT("  ~p.~n", [{label,_L}]) end, Ls2),
     Offset = 1 + length(Ls1) + 1 + length(Ls2),
-    EntryOK = (Entry =:= undefined) orelse lists:member(Entry, Ls2),
+    EntryOK = lists:member(Entry, Ls2),
     if
 	EntryOK ->
 	    St = init_state(Arity),
@@ -300,7 +222,7 @@ labels_1([{label,L}|Is], R) ->
 labels_1([{line,_}|Is], R) ->
     labels_1(Is, R);
 labels_1(Is, R) ->
-    {lists:reverse(R),Is}.
+    {reverse(R),Is}.
 
 init_state(Arity) ->
     Xs = init_regs(Arity, term),
@@ -325,7 +247,6 @@ valfun([], MFA, _Offset, #vst{branched=Targets0,labels=Labels0}=Vst) ->
 	    error({MFA,Error})
     end;
 valfun([I|Is], MFA, Offset, Vst0) ->
-    ?DBG_FORMAT("    ~p.\n", [I]),
     valfun(Is, MFA, Offset+1,
 	   try
 	       Vst = val_dsetel(I, Vst0),
@@ -343,7 +264,6 @@ valfun_1({label,Lbl}, #vst{current=St0,branched=B,labels=Lbls}=Vst) ->
 valfun_1(_I, #vst{current=none}=Vst) ->
     %% Ignore instructions after erlang:error/1,2, which
     %% the original R10B compiler thought would return.
-    ?DBG_FORMAT("Ignoring ~p\n", [_I]),
     Vst;
 valfun_1({badmatch,Src}, Vst) ->
     assert_term(Src, Vst),
@@ -361,7 +281,7 @@ 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,{match_context,_,_}} -> term;
+		       {value,#ms{}} -> term;
 		       _ -> get_term_type(Ctx, Vst)
 		   end,
 	    set_type_reg(Type, Ctx, Vst);
@@ -395,10 +315,6 @@ valfun_1({init,{y,_}=Reg}, Vst) ->
     set_type_y(initialized, Reg, Vst);
 valfun_1({test_heap,Heap,Live}, Vst) ->
     test_heap(Heap, Live, Vst);
-valfun_1({bif,_Op,nofail,Src,Dst}, Vst) ->
-    %% The 'nofail' atom only occurs in disassembled code.
-    validate_src(Src, Vst),
-    set_type_reg(term, Dst, Vst);
 valfun_1({bif,Op,{f,_},Src,Dst}=I, Vst) ->
     case is_bif_safe(Op, length(Src)) of
 	false ->
@@ -424,18 +340,12 @@ valfun_1({put_tuple,Sz,Dst}, Vst0) when is_integer(Sz) ->
 valfun_1({put,Src}, Vst) ->
     assert_term(Src, Vst),
     eat_heap(1, Vst);
-valfun_1({put_string,Sz,_,Dst}, Vst0) when is_integer(Sz) ->
-    Vst = eat_heap(2*Sz, Vst0),
-    set_type_reg(cons, Dst, Vst);
 %% Instructions for optimization of selective receives.
 valfun_1({recv_mark,{f,Fail}}, Vst) when is_integer(Fail) ->
     Vst;
 valfun_1({recv_set,{f,Fail}}, Vst) when is_integer(Fail) ->
     Vst;
 %% Misc.
-valfun_1({'%live',Live}, Vst) ->
-    verify_live(Live, Vst),
-    Vst;
 valfun_1(remove_message, Vst) ->
     Vst;
 valfun_1({'%',_}, Vst) ->
@@ -486,37 +396,33 @@ valfun_1({'try',Dst,{f,Fail}}, Vst0) ->
     Vst = #vst{current=#st{ct=Fails}=St} = 
 	set_type_y({trytag,[Fail]}, Dst, Vst0),
     Vst#vst{current=St#st{ct=[[Fail]|Fails]}};
-valfun_1({catch_end,Reg}, #vst{current=#st{ct=[Fail|Fails]}=St0}=Vst0) ->
+valfun_1({catch_end,Reg}, #vst{current=#st{ct=[Fail|Fails]}}=Vst0) ->
     case get_special_y_type(Reg, Vst0) of
 	{catchtag,Fail} ->
-	    Vst = #vst{current=St} = 
-		set_type_y(initialized_ct, Reg, 
-			   Vst0#vst{current=St0#st{ct=Fails}}),
+	    Vst = #vst{current=St} = set_catch_end(Reg, Vst0),
 	    Xs = gb_trees_from_list([{0,term}]),
-	    Vst#vst{current=St#st{x=Xs,fls=undefined}};
+	    Vst#vst{current=St#st{x=Xs,ct=Fails,fls=undefined}};
 	Type ->
 	    error({bad_type,Type})
     end;
-valfun_1({try_end,Reg}, #vst{current=#st{ct=[Fail|Fails]}=St}=Vst0) ->
+valfun_1({try_end,Reg}, #vst{current=#st{ct=[Fail|Fails]}=St0}=Vst0) ->
     case get_special_y_type(Reg, Vst0) of
 	{trytag,Fail} ->
 	    Vst = case Fail of
 		      [FailLabel] -> branch_state(FailLabel, Vst0);
 		      _ -> Vst0
 		  end,
-	    set_type_reg(initialized_ct, Reg, 
-			 Vst#vst{current=St#st{ct=Fails,fls=undefined}});
+	    St = St0#st{ct=Fails,fls=undefined},
+	    set_catch_end(Reg, Vst#vst{current=St});
 	Type ->
 	    error({bad_type,Type})
     end;
-valfun_1({try_case,Reg}, #vst{current=#st{ct=[Fail|Fails]}=St0}=Vst0) ->
+valfun_1({try_case,Reg}, #vst{current=#st{ct=[Fail|Fails]}}=Vst0) ->
     case get_special_y_type(Reg, Vst0) of
 	{trytag,Fail} ->
-	    Vst = #vst{current=St} = 
-		set_type_y(initialized_ct, Reg, 
-			   Vst0#vst{current=St0#st{ct=Fails}}),
-	    Xs = gb_trees_from_list([{0,{atom,[]}},{1,term},{2,term}]), %XXX
-	    Vst#vst{current=St#st{x=Xs,fls=undefined}};
+	    Vst = #vst{current=St} = set_catch_end(Reg, Vst0),
+	    Xs = gb_trees_from_list([{0,{atom,[]}},{1,term},{2,term}]),
+	    Vst#vst{current=St#st{x=Xs,ct=Fails,fls=undefined}};
 	Type ->
 	    error({bad_type,Type})
     end;
@@ -530,7 +436,7 @@ valfun_2(I, #vst{current=#st{ct=[[Fail]|_]}}=Vst) when is_integer(Fail) ->
     %% Update branched state
     valfun_3(I, branch_state(Fail, Vst));
 valfun_2(_, _) ->
-    error(ambigous_catch_try_state).
+    error(ambiguous_catch_try_state).
 
 %% Handle the remaining floating point instructions here.
 %% Floating point.
@@ -574,6 +480,7 @@ valfun_4({apply,Live}, Vst) ->
 valfun_4({apply_last,Live,_}, Vst) ->
     tail_call(apply, Live+2, Vst);
 valfun_4({call_fun,Live}, Vst) ->
+    validate_src([{x,Live}], Vst),
     call('fun', Live+1, Vst);
 valfun_4({call,Live,Func}, Vst) ->
     call(Func, Live, Vst);
@@ -593,8 +500,6 @@ valfun_4({call_ext_last,Live,Func,StkSize},
     tail_call(Func, Live, Vst);
 valfun_4({call_ext_last,_,_,_}, #vst{current=#st{numy=NumY}}) ->
     error({allocated,NumY});
-valfun_4({make_fun,_,_,Live}, Vst) ->
-    call('fun', Live, Vst);
 valfun_4({make_fun2,_,_,_,Live}, Vst) ->
     call(make_fun, Live, Vst);
 %% Other BIFs
@@ -611,8 +516,9 @@ valfun_4({bif,element,{f,Fail},[Pos,Tuple],Dst}, Vst0) ->
     TupleType = upgrade_tuple_type({tuple,[get_tuple_size(PosType)]}, TupleType0),
     Vst = set_type(TupleType, Tuple, Vst1),
     set_type_reg(term, Dst, Vst);
-valfun_4({raise,{f,_}=Fail,Src,Dst}, Vst) ->
-    valfun_4({bif,raise,Fail,Src,Dst}, Vst);
+valfun_4({bif,raise,{f,0},Src,_Dst}, Vst) ->
+    validate_src(Src, Vst),
+    kill_state(Vst);
 valfun_4({bif,Op,{f,Fail},Src,Dst}, Vst0) ->
     validate_src(Src, Vst0),
     Vst = branch_state(Fail, Vst0),
@@ -628,6 +534,7 @@ valfun_4({gc_bif,Op,{f,Fail},Live,Src,Dst}, #vst{current=St0}=Vst0) ->
     Type = bif_type(Op, Src, Vst),
     set_type_reg(Type, Dst, Vst);
 valfun_4(return, #vst{current=#st{numy=none}}=Vst) ->
+    assert_term({x,0}, Vst),
     kill_state(Vst);
 valfun_4(return, #vst{current=#st{numy=NumY}}) ->
     error({stack_frame,NumY});
@@ -675,7 +582,7 @@ valfun_4({test,bs_start_match2,{f,Fail},Live,[Ctx,NeedSlots],Ctx}, Vst0) ->
     verify_live(Live, Vst0),
     Vst1 = prune_x_regs(Live, Vst0),
     BranchVst = case CtxType of
-		    {match_context,_,_} ->
+		    #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
@@ -728,32 +635,6 @@ valfun_4({bs_save2,Ctx,SavePoint}, Vst) ->
 valfun_4({bs_restore2,Ctx,SavePoint}, Vst) ->
     bsm_restore(Ctx, SavePoint, Vst);
 
-%% Bit syntax instructions.
-valfun_4({bs_start_match,{f,_Fail}=F,Src}, Vst) ->
-    valfun_4({test,bs_start_match,F,[Src]}, Vst);
-valfun_4({test,bs_start_match,{f,Fail},[Src]}, Vst) ->
-    assert_term(Src, Vst),
-    bs_start_match(branch_state(Fail, Vst));
-
-valfun_4({bs_save,SavePoint}, Vst) ->
-    bs_assert_state(Vst),
-    bs_save(SavePoint, Vst);
-valfun_4({bs_restore,SavePoint}, Vst) ->
-    bs_assert_state(Vst),
-    bs_assert_savepoint(SavePoint, Vst),
-    Vst;
-valfun_4({test,bs_skip_bits,{f,Fail},[Src,_,_]}, Vst) ->
-    bs_assert_state(Vst),
-    assert_term(Src, Vst),
-    branch_state(Fail, Vst);
-valfun_4({test,bs_test_tail,{f,Fail},_}, Vst) ->
-    bs_assert_state(Vst),
-    branch_state(Fail, Vst);
-valfun_4({test,_,{f,Fail},[_,_,_,Dst]}, Vst0) ->
-    bs_assert_state(Vst0),
-    Vst = branch_state(Fail, Vst0),
-    set_type_reg({integer,[]}, Dst, Vst);
-
 %% Other test instructions.
 valfun_4({test,is_float,{f,Lbl},[Float]}, Vst) ->
     assert_term(Float, Vst),
@@ -768,6 +649,20 @@ valfun_4({test,is_nonempty_list,{f,Lbl},[Cons]}, Vst) ->
 valfun_4({test,test_arity,{f,Lbl},[Tuple,Sz]}, Vst) when is_integer(Sz) ->
     assert_type(tuple, Tuple, Vst),
     set_type_reg({tuple,Sz}, Tuple, branch_state(Lbl, Vst));
+valfun_4({test,has_map_fields,{f,Lbl},Src,{list,List}}, Vst) ->
+    assert_type(map, Src, Vst),
+    assert_unique_map_keys(List),
+    branch_state(Lbl, Vst);
+valfun_4({test,is_map,{f,Lbl},[Src]}, Vst0) ->
+    Vst = branch_state(Lbl, Vst0),
+    case Src of
+	{Tag,_} when Tag =:= x; Tag =:= y ->
+	    set_type_reg(map, Src, Vst);
+	{literal,Map} when is_map(Map) ->
+	    Vst;
+	_ ->
+	    kill_state(Vst)
+    end;
 valfun_4({test,_Op,{f,Lbl},Src}, Vst) ->
     validate_src(Src, Vst),
     branch_state(Lbl, Vst);
@@ -781,9 +676,6 @@ valfun_4({bs_utf8_size,{f,Fail},A,Dst}, Vst) ->
 valfun_4({bs_utf16_size,{f,Fail},A,Dst}, Vst) ->
     assert_term(A, Vst),
     set_type_reg({integer,[]}, Dst, branch_state(Fail, Vst));
-valfun_4({bs_bits_to_bytes,{f,Fail},Src,Dst}, Vst) ->
-    assert_term(Src, Vst),
-    set_type_reg({integer,[]}, Dst, branch_state(Fail, Vst));
 valfun_4({bs_init2,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) ->
     verify_live(Live, Vst0),
     if
@@ -794,8 +686,7 @@ valfun_4({bs_init2,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) ->
     end,
     Vst1 = heap_alloc(Heap, Vst0),
     Vst2 = branch_state(Fail, Vst1),
-    Vst3 = prune_x_regs(Live, Vst2),
-    Vst = bs_zero_bits(Vst3),
+    Vst = prune_x_regs(Live, Vst2),
     set_type_reg(binary, Dst, Vst);
 valfun_4({bs_init_bits,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) ->
     verify_live(Live, Vst0),
@@ -807,8 +698,7 @@ valfun_4({bs_init_bits,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) ->
     end,
     Vst1 = heap_alloc(Heap, Vst0),
     Vst2 = branch_state(Fail, Vst1),
-    Vst3 = prune_x_regs(Live, Vst2),
-    Vst = bs_zero_bits(Vst3),
+    Vst = prune_x_regs(Live, Vst2),
     set_type_reg(binary, Dst, Vst);
 valfun_4({bs_append,{f,Fail},Bits,Heap,Live,_Unit,Bin,_Flags,Dst}, Vst0) ->
     verify_live(Live, Vst0),
@@ -816,57 +706,84 @@ valfun_4({bs_append,{f,Fail},Bits,Heap,Live,_Unit,Bin,_Flags,Dst}, Vst0) ->
     assert_term(Bin, Vst0),
     Vst1 = heap_alloc(Heap, Vst0),
     Vst2 = branch_state(Fail, Vst1),
-    Vst3 = prune_x_regs(Live, Vst2),
-    Vst = bs_zero_bits(Vst3),
+    Vst = prune_x_regs(Live, Vst2),
     set_type_reg(binary, Dst, Vst);
 valfun_4({bs_private_append,{f,Fail},Bits,_Unit,Bin,_Flags,Dst}, Vst0) ->
     assert_term(Bits, Vst0),
     assert_term(Bin, Vst0),
-    Vst1 = branch_state(Fail, Vst0),
-    Vst = bs_zero_bits(Vst1),
+    Vst = branch_state(Fail, Vst0),
     set_type_reg(binary, Dst, Vst);
 valfun_4({bs_put_string,Sz,_}, Vst) when is_integer(Sz) ->
     Vst;
-valfun_4({bs_put_binary,{f,Fail},Sz,_,_,Src}=I, Vst0) ->
-    assert_term(Sz, Vst0),
-    assert_term(Src, Vst0),
-    Vst = bs_align_check(I, Vst0),
+valfun_4({bs_put_binary,{f,Fail},Sz,_,_,Src}, Vst) ->
+    assert_term(Sz, Vst),
+    assert_term(Src, Vst),
     branch_state(Fail, Vst);
-valfun_4({bs_put_float,{f,Fail},Sz,_,_,Src}=I, Vst0) ->
-    assert_term(Sz, Vst0),
-    assert_term(Src, Vst0),
-    Vst = bs_align_check(I, Vst0),
+valfun_4({bs_put_float,{f,Fail},Sz,_,_,Src}, Vst) ->
+    assert_term(Sz, Vst),
+    assert_term(Src, Vst),
     branch_state(Fail, Vst);
-valfun_4({bs_put_integer,{f,Fail},Sz,_,_,Src}=I, Vst0) ->
-    assert_term(Sz, Vst0),
-    assert_term(Src, Vst0),
-    Vst = bs_align_check(I, Vst0),
+valfun_4({bs_put_integer,{f,Fail},Sz,_,_,Src}, Vst) ->
+    assert_term(Sz, Vst),
+    assert_term(Src, Vst),
     branch_state(Fail, Vst);
-valfun_4({bs_put_utf8,{f,Fail},_,Src}=I, Vst0) ->
-    assert_term(Src, Vst0),
-    Vst = bs_align_check(I, Vst0),
+valfun_4({bs_put_utf8,{f,Fail},_,Src}, Vst) ->
+    assert_term(Src, Vst),
     branch_state(Fail, Vst);
-valfun_4({bs_put_utf16,{f,Fail},_,Src}=I, Vst0) ->
-    assert_term(Src, Vst0),
-    Vst = bs_align_check(I, Vst0),
+valfun_4({bs_put_utf16,{f,Fail},_,Src}, Vst) ->
+    assert_term(Src, Vst),
     branch_state(Fail, Vst);
-valfun_4({bs_put_utf32,{f,Fail},_,Src}=I, Vst0) ->
-    assert_term(Src, Vst0),
-    Vst = bs_align_check(I, Vst0),
+valfun_4({bs_put_utf32,{f,Fail},_,Src}, Vst) ->
+    assert_term(Src, Vst),
     branch_state(Fail, Vst);
-%% Old bit syntax construction (before R10B).
-valfun_4({bs_init,_,_}, Vst) ->
-    bs_zero_bits(Vst);
-valfun_4({bs_need_buf,_}, Vst) -> Vst;
-valfun_4({bs_final,{f,Fail},Dst}, Vst0) ->
-    Vst = branch_state(Fail, Vst0),
-    set_type_reg(binary, Dst, Vst);
-valfun_4({bs_final2,Src,Dst}, Vst0) ->
-    assert_term(Src, Vst0),
-    set_type_reg(binary, Dst, Vst0);
+%% Map instructions.
+valfun_4({put_map_assoc,{f,Fail},Src,Dst,Live,{list,List}}, Vst) ->
+    verify_put_map(Fail, Src, Dst, Live, List, Vst);
+valfun_4({put_map_exact,{f,Fail},Src,Dst,Live,{list,List}}, Vst) ->
+    verify_put_map(Fail, Src, Dst, Live, List, Vst);
+valfun_4({get_map_elements,{f,Fail},Src,{list,List}}, Vst) ->
+    verify_get_map(Fail, Src, List, Vst);
 valfun_4(_, _) ->
     error(unknown_instruction).
 
+verify_get_map(Fail, Src, List, Vst0) ->
+    assert_type(map, Src, Vst0),
+    Vst1 = foldl(fun(D, Vsti) ->
+                         case is_reg_defined(D,Vsti) of
+                             true -> set_type_reg(term,D,Vsti);
+                             false -> Vsti
+                         end
+                 end, Vst0, extract_map_vals(List)),
+    Vst2 = branch_state(Fail, Vst1),
+    Keys = extract_map_keys(List),
+    assert_unique_map_keys(Keys),
+    verify_get_map_pair(List,Vst0,Vst2).
+
+extract_map_vals([_Key,Val|T]) ->
+    [Val|extract_map_vals(T)];
+extract_map_vals([]) -> [].
+
+extract_map_keys([Key,_Val|T]) ->
+    [Key|extract_map_keys(T)];
+extract_map_keys([]) -> [].
+
+verify_get_map_pair([],_,Vst) -> Vst;
+verify_get_map_pair([Src,Dst|Vs],Vst0,Vsti) ->
+    assert_term(Src, Vst0),
+    verify_get_map_pair(Vs,Vst0,set_type_reg(term,Dst,Vsti)).
+
+verify_put_map(Fail, Src, Dst, Live, List, Vst0) ->
+    assert_type(map, Src, Vst0),
+    verify_live(Live, Vst0),
+    verify_y_init(Vst0),
+    foreach(fun (Term) -> assert_term(Term, Vst0) end, List),
+    Vst1 = heap_alloc(0, Vst0),
+    Vst2 = branch_state(Fail, Vst1),
+    Vst = prune_x_regs(Live, Vst2),
+    Keys = extract_map_keys(List),
+    assert_unique_map_keys(Keys),
+    set_type_reg(map, Dst, Vst).
+
 %%
 %% Common code for validating bs_get* instructions.
 %%
@@ -887,15 +804,12 @@ validate_bs_skip_utf(Fail, Ctx, Live, Vst0) ->
     branch_state(Fail, Vst).
 
 %%
-%% Special state handling for setelement/3 and the set_tuple_element/3 instruction.
+%% Special state handling for setelement/3 and set_tuple_element/3 instructions.
 %% A possibility for garbage collection must not occur between setelement/3 and
 %% set_tuple_element/3.
 %%
 val_dsetel({move,_,_}, Vst) ->
     Vst;
-val_dsetel({put_string,0,{string,""},_}, Vst) ->
-    %% An empty string is OK since it doesn't build anything.
-    Vst;
 val_dsetel({call_ext,3,{extfunc,erlang,setelement,3}}, #vst{current=St}=Vst) ->
     Vst#vst{current=St#st{setelem=true}};
 val_dsetel({set_tuple_element,_,_,_}, #vst{current=#st{setelem=false}}) ->
@@ -923,56 +837,86 @@ kill_state_1(Vst) ->
 %%  The stackframe must be initialized.
 %%  The instruction will return to the instruction following the call.
 call(Name, Live, #vst{current=St}=Vst) ->
-    verify_live(Live, Vst),
+    verify_call_args(Name, Live, Vst),
     verify_y_init(Vst),
     case return_type(Name, Vst) of
 	Type when Type =/= exception ->
 	    %% Type is never 'exception' because it has been handled earlier.
 	    Xs = gb_trees_from_list([{0,Type}]),
-	    Vst#vst{current=St#st{x=Xs,f=init_fregs(),bsm=undefined}}
+	    Vst#vst{current=St#st{x=Xs,f=init_fregs()}}
     end.
 
 %% Tail call.
 %%  The stackframe must have a known size and be initialized.
 %%  Does not return to the instruction following the call.
-tail_call(Name, Live, Vst) ->
+tail_call(Name, Live, Vst0) ->
+    verify_y_init(Vst0),
+    Vst = deallocate(Vst0),
     verify_call_args(Name, Live, Vst),
-    verify_y_init(Vst),
     verify_no_ct(Vst),
     kill_state(Vst).
 
 verify_call_args(_, 0, #vst{}) ->
     ok;
 verify_call_args({f,Lbl}, Live, Vst) when is_integer(Live)->
-    Verify = fun(R) ->
-		     case get_move_term_type(R, Vst) of
-			 {match_context,_,_} ->
-			     verify_call_match_context(Lbl, Vst);
-			 _ ->
-			     ok
-		     end
-	     end,
-    verify_call_args_1(Live, Verify, Vst);
+    verify_local_call(Lbl, Live, Vst);
 verify_call_args(_, Live, Vst) when is_integer(Live)->
-    Verify = fun(R) -> get_term_type(R, Vst) end,
-    verify_call_args_1(Live, Verify, Vst);
+    verify_call_args_1(Live, Vst);
 verify_call_args(_, Live, _) ->
     error({bad_number_of_live_regs,Live}).
 
-verify_call_args_1(0, _, _) -> ok;
-verify_call_args_1(N, Verify, Vst) ->
+verify_call_args_1(0, _) -> ok;
+verify_call_args_1(N, Vst) ->
     X = N - 1,
-    Verify({x,X}),
-    verify_call_args_1(X, Verify, Vst).
+    get_term_type({x,X}, 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.
+
+all_ms_in_x_regs(0, _Vst) ->
+    [];
+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)
+    end.
 
-verify_call_match_context(Lbl, #vst{ft=Ft}) ->
+ms_in_y_regs(Id, #vst{current=#st{y=Ys0}}) ->
+    Ys = gb_trees:to_list(Ys0),
+    [Y || {Y,#ms{id=OtherId}} <- Ys, OtherId =:= Id].
+
+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,_,_,[Bin,_,_],Ctx}|_]} ->
-	    error({binary_and_context_regs_different,Bin,Ctx})
+	{value,[{test,bs_start_match2,_,_,_,_}=I|_]} ->
+	    error({unsuitable_bs_start_match2,I})
     end.
 
 allocate(Zero, Stk, Heap, Live, #vst{current=#st{numy=none}=St}=Vst0) ->
@@ -987,7 +931,7 @@ allocate(_, _, _, _, #vst{current=#st{numy=Numy}}) ->
     error({existing_stack_frame,{size,Numy}}).
 
 deallocate(#vst{current=St}=Vst) ->
-    Vst#vst{current=St#st{y=init_regs(0, initialized),numy=none,bsm=undefined}}.
+    Vst#vst{current=St#st{y=init_regs(0, initialized),numy=none}}.
 
 test_heap(Heap, Live, Vst0) ->
     verify_live(Live, Vst0),
@@ -995,7 +939,7 @@ test_heap(Heap, Live, Vst0) ->
     heap_alloc(Heap, Vst).
 
 heap_alloc(Heap, #vst{current=St0}=Vst) ->
-    St1 = kill_heap_allocation(St0#st{bsm=undefined}),
+    St1 = kill_heap_allocation(St0),
     St = heap_alloc_1(Heap, St1),
     Vst#vst{current=St}.
 
@@ -1056,9 +1000,9 @@ get_fls(#vst{current=#st{fls=Fls}}) when is_atom(Fls) -> Fls.
 
 init_fregs() -> 0.
 
-set_freg({fr,Fr}, #vst{current=#st{f=Fregs0}=St}=Vst)
+set_freg({fr,Fr}=Freg, #vst{current=#st{f=Fregs0}=St}=Vst)
   when is_integer(Fr), 0 =< Fr ->
-    limit_check(Fr),
+    check_limit(Freg),
     Bit = 1 bsl Fr,
     if
 	Fregs0 band Bit =:= 0 ->
@@ -1071,54 +1015,40 @@ set_freg(Fr, _) -> error({bad_target,Fr}).
 assert_freg_set({fr,Fr}=Freg, #vst{current=#st{f=Fregs}})
   when is_integer(Fr), 0 =< Fr ->
     if
-	Fregs band (1 bsl Fr) =/= 0 ->
-	    limit_check(Fr);
-	true -> error({uninitialized_reg,Freg})
+	(Fregs bsr Fr) band 1 =:= 0 ->
+	    error({uninitialized_reg,Freg});
+	true ->
+	    ok
     end;
 assert_freg_set(Fr, _) -> error({bad_source,Fr}).
 
-%%%
-%%% Binary matching.
-%%%
-%%% Possible values for the bsm field (=bit syntax matching state).
-%%%
-%%% undefined 	- Undefined (initial state). No matching instructions allowed.
-%%%		 
-%%% (gb set)	- The gb set contains the defined save points.
-%%%
-%%% The bsm field is reset to 'undefined' by instructions that may cause a
-%%% a garbage collection (might move the binary) and/or context switch
-%%% (may invalidate the save points).
-
-bs_start_match(#vst{current=#st{bsm=undefined}=St}=Vst) ->
-    Vst#vst{current=St#st{bsm=gb_sets:empty()}};
-bs_start_match(Vst) ->
-    %% Must retain save points here - it is possible to restore back
-    %% to a previous binary.
-    Vst.
-
-bs_save(Reg, #vst{current=#st{bsm=Saved}=St}=Vst)
-  when is_integer(Reg), Reg < ?MAXREG  ->
-    Vst#vst{current=St#st{bsm=gb_sets:add(Reg, Saved)}};
-bs_save(_, _) -> error(limit).
-
-bs_assert_savepoint(Reg, #vst{current=#st{bsm=Saved}}) ->
-    case gb_sets:is_member(Reg, Saved) of
-	false -> error({no_save_point,Reg});
-	true -> ok
-    end.
+%%% Maps
 
-bs_assert_state(#vst{current=#st{bsm=undefined}}) ->
-    error(no_bs_match_state);
-bs_assert_state(_) -> ok.
+%% A single item list may be either a list or a register.
+%%
+%% A list with more than item must contain unique literals.
+%%
+%% An empty list is not allowed.
 
+assert_unique_map_keys([]) ->
+    %% There is no reason to use the get_map_elements and
+    %% has_map_fields instructions with empty lists.
+    error(empty_field_list);
+assert_unique_map_keys([_]) ->
+    ok;
+assert_unique_map_keys([_,_|_]=Ls) ->
+    Vs = [get_literal(L) || L <- Ls],
+    case length(Vs) =:= sets:size(sets:from_list(Vs)) of
+	true -> ok;
+	false -> error(keys_not_unique)
+    end.
 
 %%%
 %%% New binary matching instructions.
 %%%
 
 bsm_match_state(Slots) ->
-    {match_context,0,Slots}.
+    #ms{slots=Slots}.
 
 bsm_validate_context(Reg, Vst) ->
     _ = bsm_get_context(Reg, Vst),
@@ -1126,7 +1056,7 @@ bsm_validate_context(Reg, Vst) ->
 
 bsm_get_context({x,X}=Reg, #vst{current=#st{x=Xs}}=_Vst) when is_integer(X) ->
     case gb_trees:lookup(X, Xs) of
-	{value,{match_context,_,_}=Ctx} -> Ctx;
+	{value,#ms{}=Ctx} -> Ctx;
 	_ -> error({no_bsm_context,Reg})
     end;
 bsm_get_context(Reg, _) -> error({bad_source,Reg}).
@@ -1138,8 +1068,8 @@ bsm_save(Reg, {atom,start}, Vst) ->
     Vst;
 bsm_save(Reg, SavePoint, Vst) ->
     case bsm_get_context(Reg, Vst) of
-	{match_context,Bits,Slots} when SavePoint < Slots ->
-	    Ctx = {match_context,Bits bor (1 bsl SavePoint),Slots},
+	#ms{valid=Bits,slots=Slots}=Ctxt0 when SavePoint < Slots ->
+	    Ctx = Ctxt0#ms{valid=Bits bor (1 bsl SavePoint),slots=Slots},
 	    set_type_reg(Ctx, Reg, Vst);
 	_ -> error({illegal_save,SavePoint})
     end.
@@ -1151,63 +1081,15 @@ bsm_restore(Reg, {atom,start}, Vst) ->
     Vst;
 bsm_restore(Reg, SavePoint, Vst) ->
     case bsm_get_context(Reg, Vst) of
-	{match_context,Bits,Slots} when SavePoint < Slots ->
+	#ms{valid=Bits,slots=Slots} when SavePoint < Slots ->
 	    case Bits band (1 bsl SavePoint) of
 		0 -> error({illegal_restore,SavePoint,not_set});
 		_ -> Vst
 	    end;
 	_ -> error({illegal_restore,SavePoint,range})
     end.
-    
 
 %%%
-%%% Validation of alignment in the bit syntax. (Currently, construction only.)
-%%%
-%%% We make sure that the aligned flag is only set when we can be sure of the
-%%% aligment.
-%%%
-
-bs_zero_bits(#vst{current=St}=Vst) ->
-    Vst#vst{current=St#st{bits=0}}.
-
-bs_align_check({bs_put_utf8,_,Flags,_}, #vst{current=#st{}=St}=Vst) ->
-    bs_verify_flags(Flags, St),
-    Vst;
-bs_align_check({bs_put_utf16,_,Flags,_}, #vst{current=#st{}=St}=Vst) ->
-    bs_verify_flags(Flags, St),
-    Vst;
-bs_align_check({bs_put_utf32,_,Flags,_}, #vst{current=#st{}=St}=Vst) ->
-    bs_verify_flags(Flags, St),
-    Vst;
-bs_align_check({_,_,Sz,U,Flags,_}, #vst{current=#st{bits=Bits}=St}=Vst) ->
-    bs_verify_flags(Flags, St),
-    bs_update_bits(Bits, Sz, U, St, Vst).
-
-bs_update_bits(undefined, _, _, _, Vst) -> Vst;
-bs_update_bits(Bits0, {integer,Sz}, U, St, Vst) ->
-    Bits = Bits0 + U*Sz,
-    Vst#vst{current=St#st{bits=Bits}};
-bs_update_bits(_, {atom,all}, _, _, Vst) ->
-    %% A binary will not change the alignment.
-    Vst;
-bs_update_bits(_, _, U, _, Vst) when U rem 8 =:= 0 ->
-    %% Units of 8, 16, and so on will not change the aligment.
-    Vst;
-bs_update_bits(_, _, _, St, Vst) ->
-    %% We can no longer be sure about aligment.
-    Vst#vst{current=St#st{bits=undefined}}.
-
-bs_verify_flags({field_flags,Fl}, #st{bits=Bits}) ->
-    case bs_is_aligned(Fl) of
-	false -> ok;
-	true when is_integer(Bits), Bits rem 8 =:= 0 -> ok;
-	true -> error({aligned_flag_set,{bits,Bits}})
-    end.
-
-bs_is_aligned(Fl) when is_integer(Fl) -> Fl band 1 =:= 1;
-bs_is_aligned(Fl) when is_list(Fl) -> member(aligned, Fl).
-    
-%%%
 %%% Keeping track of types.
 %%%
 
@@ -1215,42 +1097,44 @@ set_type(Type, {x,_}=Reg, Vst) -> set_type_reg(Type, Reg, Vst);
 set_type(Type, {y,_}=Reg, Vst) -> set_type_y(Type, Reg, Vst);
 set_type(_, _, #vst{}=Vst) -> Vst.
 
-set_type_reg(Type, {x,X}, #vst{current=#st{x=Xs}=St}=Vst) 
+set_type_reg(Type, {x,X}=Reg, #vst{current=#st{x=Xs}=St}=Vst)
   when is_integer(X), 0 =< X ->
-    limit_check(X),
+    check_limit(Reg),
     Vst#vst{current=St#st{x=gb_trees:enter(X, Type, Xs)}};
 set_type_reg(Type, Reg, Vst) ->
     set_type_y(Type, Reg, Vst).
 
-set_type_y(Type, {y,Y}=Reg, #vst{current=#st{y=Ys0,numy=NumY}=St}=Vst) 
+set_type_y(Type, {y,Y}=Reg, #vst{current=#st{y=Ys0}=St}=Vst)
   when is_integer(Y), 0 =< Y ->
-    limit_check(Y),
-    case {Y,NumY} of
-	{_,none} ->
-	    error({no_stack_frame,Reg});
-	{_,_} when Y > NumY ->
-	    error({y_reg_out_of_range,Reg,NumY});
-	{_,_} ->
-	    Ys = if  Type =:= initialized_ct ->
-			 gb_trees:enter(Y, initialized, Ys0);
-		     true ->
-			 case gb_trees:lookup(Y, Ys0) of
-			     none -> 
-				 gb_trees:insert(Y, Type, Ys0);
-			     {value,uinitialized} ->
-				 gb_trees:insert(Y, Type, Ys0);
-			     {value,{catchtag,_}=Tag} ->
-				 error(Tag);
-			     {value,{trytag,_}=Tag} ->
-				 error(Tag);
-			     {value,_} ->
-				 gb_trees:update(Y, Type, Ys0)
-			 end
-		 end,
-	    Vst#vst{current=St#st{y=Ys}}
-    end;
+    check_limit(Reg),
+    Ys = case gb_trees:lookup(Y, Ys0) of
+	     none ->
+		 error({invalid_store,Reg,Type});
+	     {value,{catchtag,_}=Tag} ->
+		 error(Tag);
+	     {value,{trytag,_}=Tag} ->
+		 error(Tag);
+	     {value,_} ->
+		 gb_trees:update(Y, Type, Ys0)
+	 end,
+    Vst#vst{current=St#st{y=Ys}};
 set_type_y(Type, Reg, #vst{}) -> error({invalid_store,Reg,Type}).
 
+set_catch_end({y,Y}, #vst{current=#st{y=Ys0}=St}=Vst) ->
+    Ys = gb_trees:update(Y, initialized, Ys0),
+    Vst#vst{current=St#st{y=Ys}}.
+
+
+is_reg_defined({x,_}=Reg, Vst) -> is_type_defined_x(Reg, Vst);
+is_reg_defined({y,_}=Reg, Vst) -> is_type_defined_y(Reg, Vst);
+is_reg_defined(V, #vst{}) -> error({not_a_register, V}).
+
+is_type_defined_x({x,X}, #vst{current=#st{x=Xs}}) ->
+    gb_trees:is_defined(X,Xs).
+
+is_type_defined_y({y,Y}, #vst{current=#st{y=Ys}}) ->
+    gb_trees:is_defined(Y,Ys).
+
 assert_term(Src, Vst) ->
     get_term_type(Src, Vst),
     ok.
@@ -1278,7 +1162,7 @@ assert_term(Src, Vst) ->
 %%			Thus 'exception' is never stored as type descriptor
 %%			for a register.
 %%
-%% {match_context,_,_}	A matching context for bit syntax matching. We do allow
+%% #ms{}	        A match context for bit syntax matching. We do allow
 %%			it to moved/to from stack, but otherwise it must only
 %%			be accessed by bit syntax matching instructions.
 %%
@@ -1311,6 +1195,8 @@ assert_term(Src, Vst) ->
 %%
 %% number		Integer or Float of unknown value
 %%
+%% map			Map.
+%%
 
 assert_type(WantedType, Term, Vst) ->
     assert_type(WantedType, get_term_type(Term, Vst)).
@@ -1318,16 +1204,20 @@ assert_type(WantedType, Term, Vst) ->
 assert_type(Correct, Correct) -> ok;
 assert_type(float, {float,_}) -> ok;
 assert_type(tuple, {tuple,_}) -> ok;
+assert_type(tuple, {literal,Tuple}) when is_tuple(Tuple) -> ok;
 assert_type({tuple_element,I}, {tuple,[Sz]})
   when 1 =< I, I =< Sz ->
     ok;
 assert_type({tuple_element,I}, {tuple,Sz})
   when is_integer(Sz), 1 =< I, I =< Sz ->
     ok;
+assert_type({tuple_element,I}, {literal,Lit}) when I =< tuple_size(Lit) ->
+    ok;
+assert_type(cons, {literal,[_|_]}) ->
+    ok;
 assert_type(Needed, Actual) ->
     error({bad_type,{needed,Needed},{actual,Actual}}).
 
-
 %% upgrade_tuple_type(NewTupleType, OldType) -> TupleType.
 %%  upgrade_tuple_type/2 is used when linear code finds out more and
 %%  more information about a tuple type, so that the type gets more
@@ -1379,7 +1269,7 @@ get_term_type(Src, Vst) ->
 	initialized -> error({unassigned,Src});
 	{catchtag,_} -> error({catchtag,Src});
 	{trytag,_} -> error({trytag,Src});
-	{match_context,_,_} -> error({match_context,Src});
+	#ms{} -> error({match_context,Src});
 	Type -> Type
     end.
 
@@ -1393,6 +1283,7 @@ get_term_type_1(nil=T, _) -> T;
 get_term_type_1({atom,A}=T, _) when is_atom(A) -> T;
 get_term_type_1({float,F}=T, _) when is_float(F) -> T;
 get_term_type_1({integer,I}=T, _) when is_integer(I) -> T;
+get_term_type_1({literal,Map}, _) when is_map(Map) -> map;
 get_term_type_1({literal,_}=T, _) -> T;
 get_term_type_1({x,X}=Reg, #vst{current=#st{x=Xs}}) when is_integer(X) ->
     case gb_trees:lookup(X, Xs) of
@@ -1408,6 +1299,15 @@ get_term_type_1({y,Y}=Reg, #vst{current=#st{y=Ys}}) when is_integer(Y) ->
 get_term_type_1(Src, _) -> error({bad_source,Src}).
 
 
+%% get_literal(Src) -> literal_value().
+get_literal(nil) -> [];
+get_literal({atom,A}) when is_atom(A) -> A;
+get_literal({float,F}) when is_float(F) -> F;
+get_literal({integer,I}) when is_integer(I) -> I;
+get_literal({literal,L}) -> L;
+get_literal(T) -> error({not_literal,T}).
+
+
 branch_arities([], _, #vst{}=Vst) -> Vst;
 branch_arities([Sz,{f,L}|T], Tuple, #vst{current=St}=Vst0) 
   when is_integer(Sz) ->
@@ -1438,14 +1338,13 @@ merge_states(L, St, Branched) when L =/= 0 ->
 	{value,OtherSt} -> merge_states_1(St, OtherSt)
     end.
 
-merge_states_1(#st{x=Xs0,y=Ys0,numy=NumY0,h=H0,ct=Ct0,bsm=Bsm0}=St,
-	       #st{x=Xs1,y=Ys1,numy=NumY1,h=H1,ct=Ct1,bsm=Bsm1}) ->
+merge_states_1(#st{x=Xs0,y=Ys0,numy=NumY0,h=H0,ct=Ct0},
+	       #st{x=Xs1,y=Ys1,numy=NumY1,h=H1,ct=Ct1}) ->
     NumY = merge_stk(NumY0, NumY1),
     Xs = merge_regs(Xs0, Xs1),
     Ys = merge_y_regs(Ys0, Ys1),
     Ct = merge_ct(Ct0, Ct1),
-    Bsm = merge_bsm(Bsm0, Bsm1),
-    St#st{x=Xs,y=Ys,numy=NumY,h=min(H0, H1),ct=Ct,bsm=Bsm}.
+    #st{x=Xs,y=Ys,numy=NumY,h=min(H0, H1),ct=Ct}.
 
 merge_stk(S, S) -> S;
 merge_stk(_, _) -> undecided.
@@ -1475,20 +1374,24 @@ merge_regs_1([], [_|_]) -> [];
 merge_regs_1([_|_], []) -> [].
 
 merge_y_regs(Rs0, Rs1) ->
-    Rs = merge_y_regs_1(gb_trees:to_list(Rs0), gb_trees:to_list(Rs1)),
-    gb_trees_from_list(Rs).
+    case {gb_trees:size(Rs0),gb_trees:size(Rs1)} of
+	{Sz0,Sz1} when Sz0 < Sz1 ->
+	    merge_y_regs_1(Sz0-1, Rs1, Rs0);
+	{_,Sz1} ->
+	    merge_y_regs_1(Sz1-1, Rs0, Rs1)
+    end.
 
-merge_y_regs_1([Same|Rs1], [Same|Rs2]) ->
-    [Same|merge_y_regs_1(Rs1, Rs2)];
-merge_y_regs_1([{R1,_}|Rs1], [{R2,_}|_]=Rs2) when R1 < R2 ->
-    [{R1,uninitialized}|merge_y_regs_1(Rs1, Rs2)];
-merge_y_regs_1([{R1,_}|_]=Rs1, [{R2,_}|Rs2]) when R1 > R2 ->
-    [{R2,uninitialized}|merge_y_regs_1(Rs1, Rs2)];
-merge_y_regs_1([{R,Type1}|Rs1], [{R,Type2}|Rs2]) ->
-    [{R,merge_types(Type1, Type2)}|merge_y_regs_1(Rs1, Rs2)];
-merge_y_regs_1([], []) -> [];
-merge_y_regs_1([], [_|_]=Rs) -> Rs;
-merge_y_regs_1([_|_]=Rs, []) -> Rs.
+merge_y_regs_1(Y, S, Regs0) when Y >= 0 ->
+    Type0 = gb_trees:get(Y, Regs0),
+    case gb_trees:get(Y, S) of
+	Type0 ->
+	    merge_y_regs_1(Y-1, S, Regs0);
+	Type1 ->
+	    Type = merge_types(Type0, Type1),
+	    Regs = gb_trees:update(Y, Type, Regs0),
+	    merge_y_regs_1(Y-1, S, Regs)
+    end;
+merge_y_regs_1(_, _, Regs) -> Regs.
 
 %% merge_types(Type1, Type2) -> Type
 %%  Return the most specific type possible.
@@ -1518,20 +1421,17 @@ merge_types(bool, {atom,A}) ->
     merge_bool(A);
 merge_types({atom,A}, bool) ->
     merge_bool(A);
-merge_types({match_context,B0,Slots},{match_context,B1,Slots}) ->
-    {match_context,B0 bor B1,Slots};
-merge_types({match_context,_,_}=M, _) ->
+merge_types(#ms{id=Id,valid=B0,slots=Slots}=M,
+	    #ms{id=Id,valid=B1,slots=Slots}) ->
+    M#ms{valid=B0 bor B1,slots=Slots};
+merge_types(#ms{}=M, _) ->
     M;
-merge_types(_, {match_context,_,_}=M) ->
+merge_types(_, #ms{}=M) ->
     M;
 merge_types(T1, T2) when T1 =/= T2 ->
     %% Too different. All we know is that the type is a 'term'.
     term.
 
-merge_bsm(undefined, _) -> undefined;
-merge_bsm(_, undefined) -> undefined;
-merge_bsm(Bsm0, Bsm1) -> gb_sets:intersection(Bsm0, Bsm1).
-
 tuple_sz([Sz]) -> Sz;
 tuple_sz(Sz) -> Sz.
 
@@ -1638,6 +1538,7 @@ bif_type(is_float, [_], _) -> bool;
 bif_type(is_function, [_], _) -> bool;
 bif_type(is_integer, [_], _) -> bool;
 bif_type(is_list, [_], _) -> bool;
+bif_type(is_map, [_], _) -> bool;
 bif_type(is_number, [_], _) -> bool;
 bif_type(is_pid, [_], _) -> bool;
 bif_type(is_port, [_], _) -> bool;
@@ -1649,7 +1550,6 @@ bif_type(node, [_], _) -> {atom,[]};
 bif_type(hd, [_], _) -> term;
 bif_type(tl, [_], _) -> term;
 bif_type(get, [_], _) -> term;
-bif_type(raise, [_,_], _) -> exception;
 bif_type(Bif, _, _) when is_atom(Bif) -> term.
 
 is_bif_safe('/=', 2) -> true;
@@ -1663,10 +1563,12 @@ is_bif_safe('>=', 2) -> true;
 is_bif_safe(is_atom, 1) -> true;
 is_bif_safe(is_boolean, 1) -> true;
 is_bif_safe(is_binary, 1) -> true;
+is_bif_safe(is_bitstring, 1) -> true;
 is_bif_safe(is_float, 1) -> true;
 is_bif_safe(is_function, 1) -> true;
 is_bif_safe(is_integer, 1) -> true;
 is_bif_safe(is_list, 1) -> true;
+is_bif_safe(is_map, 1) -> true;
 is_bif_safe(is_number, 1) -> true;
 is_bif_safe(is_pid, 1) -> true;
 is_bif_safe(is_port, 1) -> true;
@@ -1692,8 +1594,12 @@ return_type_1(erlang, setelement, 3, Vst) ->
     Tuple = {x,1},
     TupleType =
 	case get_term_type(Tuple, Vst) of
-	    {tuple,_}=TT -> TT;
-	    _ -> {tuple,[0]}
+	    {tuple,_}=TT ->
+		TT;
+	    {literal,Lit} when is_tuple(Lit) ->
+		{tuple,tuple_size(Lit)};
+	    _ ->
+		{tuple,[0]}
 	end,
     case get_term_type({x,0}, Vst) of
 	{integer,[]} -> TupleType;
@@ -1709,8 +1615,6 @@ return_type_1(M, F, A, _) when is_atom(M), is_atom(F), is_integer(A), A >= 0 ->
 
 return_type_erl(exit, 1) -> exception;
 return_type_erl(throw, 1) -> exception;
-return_type_erl(fault, 1) -> exception;
-return_type_erl(fault, 2) -> exception;
 return_type_erl(error, 1) -> exception;
 return_type_erl(error, 2) -> exception;
 return_type_erl(F, A) when is_atom(F), is_integer(A), A >= 0 -> term.
@@ -1731,6 +1635,7 @@ return_type_math(erf, 1) -> {float,[]};
 return_type_math(erfc, 1) -> {float,[]};
 return_type_math(exp, 1) -> {float,[]};
 return_type_math(log, 1) -> {float,[]};
+return_type_math(log2, 1) -> {float,[]};
 return_type_math(log10, 1) -> {float,[]};
 return_type_math(sqrt, 1) -> {float,[]};
 return_type_math(atan2, 2) -> {float,[]};
@@ -1738,66 +1643,19 @@ return_type_math(pow, 2) -> {float,[]};
 return_type_math(pi, 0) -> {float,[]};
 return_type_math(F, A) when is_atom(F), is_integer(A), A >= 0 -> term.
 
-limit_check(Num) when is_integer(Num), Num >= ?MAXREG ->
-    error(limit);
-limit_check(_) -> ok.
+check_limit({x,X}) when is_integer(X), X < 1023 ->
+    %% Note: x(1023) is reserved for use by the BEAM loader.
+    ok;
+check_limit({y,Y}) when is_integer(Y), Y < 1024 ->
+    ok;
+check_limit({fr,Fr}) when is_integer(Fr), Fr < 1024 ->
+    ok;
+check_limit(_) ->
+    error(limit).
 
 min(A, B) when is_integer(A), is_integer(B), A < B -> A;
 min(A, B) when is_integer(A), is_integer(B) -> B.
 
 gb_trees_from_list(L) -> gb_trees:from_orddict(lists:sort(L)).
 
--ifdef(DEBUG).
-error(Error) -> exit(Error).
--else.
 error(Error) -> throw(Error).
--endif.
-
-
-%%%
-%%% Rewrite disassembled code to the same format as we used internally
-%%% to not have to worry later.
-%%%
-
-normalize_disassembled_code(Fs) ->
-    Index = ndc_index(Fs, []),
-    ndc(Fs, Index, []).
-
-ndc_index([{function,Name,Arity,Entry,_Code}|Fs], Acc) ->
-    ndc_index(Fs, [{{Name,Arity},Entry}|Acc]);
-ndc_index([], Acc) ->
-    gb_trees:from_orddict(lists:sort(Acc)).
-
-ndc([{function,Name,Arity,Entry,Code0}|Fs], D, Acc) ->
-    Code = ndc_1(Code0, D, []),
-    ndc(Fs, D, [{function,Name,Arity,Entry,Code}|Acc]);
-ndc([], _, Acc) -> reverse(Acc).
-    
-ndc_1([{call=Op,A,{_,F,A}}|Is], D, Acc) ->
-    ndc_1(Is, D, [{Op,A,{f,gb_trees:get({F,A}, D)}}|Acc]);
-ndc_1([{call_only=Op,A,{_,F,A}}|Is], D, Acc) ->
-    ndc_1(Is, D, [{Op,A,{f,gb_trees:get({F,A}, D)}}|Acc]);
-ndc_1([{call_last=Op,A,{_,F,A},Sz}|Is], D, Acc) ->
-    ndc_1(Is, D, [{Op,A,{f,gb_trees:get({F,A}, D)},Sz}|Acc]);
-ndc_1([{arithbif,Op,F,Src,Dst}|Is], D, Acc) ->
-    ndc_1(Is, D, [{bif,Op,F,Src,Dst}|Acc]);
-ndc_1([{arithfbif,Op,F,Src,Dst}|Is], D, Acc) ->
-    ndc_1(Is, D, [{bif,Op,F,Src,Dst}|Acc]);
-ndc_1([{test,bs_start_match2=Op,F,[A1,Live,A3,Dst]}|Is], D, Acc) ->
-    ndc_1(Is, D, [{test,Op,F,Live,[A1,A3],Dst}|Acc]);
-ndc_1([{test,bs_get_binary2=Op,F,[A1,Live,A3,A4,A5,Dst]}|Is], D, Acc) ->
-    ndc_1(Is, D, [{test,Op,F,Live,[A1,A3,A4,A5],Dst}|Acc]);
-ndc_1([{test,bs_get_float2=Op,F,[A1,Live,A3,A4,A5,Dst]}|Is], D, Acc) ->
-    ndc_1(Is, D, [{test,Op,F,Live,[A1,A3,A4,A5],Dst}|Acc]);
-ndc_1([{test,bs_get_integer2=Op,F,[A1,Live,A3,A4,A5,Dst]}|Is], D, Acc) ->
-    ndc_1(Is, D, [{test,Op,F,Live,[A1,A3,A4,A5],Dst}|Acc]);
-ndc_1([{test,bs_get_utf8=Op,F,[A1,Live,A3,Dst]}|Is], D, Acc) ->
-    ndc_1(Is, D, [{test,Op,F,Live,[A1,A3],Dst}|Acc]);
-ndc_1([{test,bs_get_utf16=Op,F,[A1,Live,A3,Dst]}|Is], D, Acc) ->
-    ndc_1(Is, D, [{test,Op,F,Live,[A1,A3],Dst}|Acc]);
-ndc_1([{test,bs_get_utf32=Op,F,[A1,Live,A3,Dst]}|Is], D, Acc) ->
-    ndc_1(Is, D, [{test,Op,F,Live,[A1,A3],Dst}|Acc]);
-ndc_1([I|Is], D, Acc) ->
-    ndc_1(Is, D, [I|Acc]);
-ndc_1([], _, Acc) ->
-    reverse(Acc).