Implement support for maps in the compiler

To make it possible to build the entire OTP system, also define
dummys for the instructions in ops.tab.

16 files changed, 296 insertions, 7 deletions

diff --git a/lib/compiler/src/beam_block.erl b/lib/compiler/src/beam_block.erl
index 402fbe2e2e..f9e90b81d2 100644
--- a/lib/compiler/src/beam_block.erl
+++ b/lib/compiler/src/beam_block.erl
@@ -152,6 +152,10 @@ collect({get_tuple_element,S,I,D}) -> {set,[D],[S],{get_tuple_element,I}};
 collect({set_tuple_element,S,D,I}) -> {set,[],[S,D],{set_tuple_element,I}};
 collect({get_list,S,D1,D2})  -> {set,[D1,D2],[S],get_list};
 collect(remove_message)      -> {set,[],[],remove_message};
+collect({put_map,F,S,D,R,{list,Puts}}) ->
+    {set,[D],[S|Puts],{alloc,R,{put_map,F}}};
+collect({get_map_element,F,S,K,D}) ->
+    {set,[D],[S],{get_map_element,K,F}};
 collect({'catch',R,L})       -> {set,[R],[],{'catch',L}};
 collect(fclearerror)         -> {set,[],[],fclearerror};
 collect({fcheckerror,{f,0}}) -> {set,[],[],fcheckerror};
@@ -383,6 +387,7 @@ gen_init(Fs, Regs, Y, Acc) ->
 
 init_yreg([{set,_,_,{bif,_,_}}|_], Reg) -> Reg;
 init_yreg([{set,_,_,{alloc,_,{gc_bif,_,_}}}|_], Reg) -> Reg;
+init_yreg([{set,_,_,{alloc,_,{put_map,_}}}|_], Reg) -> Reg;
 init_yreg([{set,Ds,_,_}|Is], Reg) -> init_yreg(Is, add_yregs(Ds, Reg));
 init_yreg(_Is, Reg) -> Reg.
 
diff --git a/lib/compiler/src/beam_clean.erl b/lib/compiler/src/beam_clean.erl
index 9d89e21a4e..6f802d0436 100644
--- a/lib/compiler/src/beam_clean.erl
+++ b/lib/compiler/src/beam_clean.erl
@@ -234,6 +234,35 @@ replace([{bs_init,{f,Lbl},Info,Live,Ss,Dst}|Is], Acc, D) when Lbl =/= 0 ->
     replace(Is, [{bs_init,{f,label(Lbl, D)},Info,Live,Ss,Dst}|Acc], D);
 replace([{bs_put,{f,Lbl},Info,Ss}|Is], Acc, D) when Lbl =/= 0 ->
     replace(Is, [{bs_put,{f,label(Lbl, D)},Info,Ss}|Acc], D);
+replace([{bs_init2,{f,Lbl},Sz,Words,R,F,Dst}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{bs_init2,{f,label(Lbl, D)},Sz,Words,R,F,Dst}|Acc], D);
+replace([{bs_init_bits,{f,Lbl},Sz,Words,R,F,Dst}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{bs_init_bits,{f,label(Lbl, D)},Sz,Words,R,F,Dst}|Acc], D);
+replace([{bs_put_integer,{f,Lbl},Bits,Unit,Fl,Val}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{bs_put_integer,{f,label(Lbl, D)},Bits,Unit,Fl,Val}|Acc], D);
+replace([{bs_put_utf8=I,{f,Lbl},Fl,Val}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{I,{f,label(Lbl, D)},Fl,Val}|Acc], D);
+replace([{bs_put_utf16=I,{f,Lbl},Fl,Val}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{I,{f,label(Lbl, D)},Fl,Val}|Acc], D);
+replace([{bs_put_utf32=I,{f,Lbl},Fl,Val}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{I,{f,label(Lbl, D)},Fl,Val}|Acc], D);
+replace([{bs_put_binary,{f,Lbl},Bits,Unit,Fl,Val}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{bs_put_binary,{f,label(Lbl, D)},Bits,Unit,Fl,Val}|Acc], D);
+replace([{bs_put_float,{f,Lbl},Bits,Unit,Fl,Val}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{bs_put_float,{f,label(Lbl, D)},Bits,Unit,Fl,Val}|Acc], D);
+replace([{bs_add,{f,Lbl},Src,Dst}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{bs_add,{f,label(Lbl, D)},Src,Dst}|Acc], D);
+replace([{bs_append,{f,Lbl},_,_,_,_,_,_,_}=I0|Is], Acc, D) when Lbl =/= 0 ->
+    I = setelement(2, I0, {f,label(Lbl, D)}),
+    replace(Is, [I|Acc], D);
+replace([{bs_utf8_size=I,{f,Lbl},Src,Dst}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{I,{f,label(Lbl, D)},Src,Dst}|Acc], D);
+replace([{bs_utf16_size=I,{f,Lbl},Src,Dst}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{I,{f,label(Lbl, D)},Src,Dst}|Acc], D);
+replace([{put_map=I,{f,Lbl},Src,Dst,Live,List}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{I,{f,label(Lbl, D)},Src,Dst,Live,List}|Acc], D);
+replace([{get_map_element=I,{f,Lbl},Src,Key,Dst}|Is], Acc, D) when Lbl =/= 0 ->
+    replace(Is, [{I,{f,label(Lbl, D)},Src,Key,Dst}|Acc], D);
 replace([I|Is], Acc, D) ->
     replace(Is, [I|Acc], D);
 replace([], Acc, _) -> Acc.
diff --git a/lib/compiler/src/beam_flatten.erl b/lib/compiler/src/beam_flatten.erl
index 5603a677e8..ad9591ff05 100644
--- a/lib/compiler/src/beam_flatten.erl
+++ b/lib/compiler/src/beam_flatten.erl
@@ -61,6 +61,10 @@ norm({set,[],[S],put})            -> {put,S};
 norm({set,[D],[S],{get_tuple_element,I}}) -> {get_tuple_element,S,I,D};
 norm({set,[],[S,D],{set_tuple_element,I}}) -> {set_tuple_element,S,D,I};
 norm({set,[D1,D2],[S],get_list})          -> {get_list,S,D1,D2};
+norm({set,[D],[S|Puts],{alloc,R,{put_map,F}}}) ->
+    {put_map,F,S,D,R,{list,Puts}};
+norm({set,[D],[S],{get_map_element,K,F}}) ->
+    {get_map_element,F,S,K,D};
 norm({set,[],[],remove_message})   -> remove_message;
 norm({set,[],[],fclearerror}) -> fclearerror;
 norm({set,[],[],fcheckerror}) -> {fcheckerror,{f,0}}.
diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl
index d57fb80ac2..bbef75c219 100644
--- a/lib/compiler/src/beam_jump.erl
+++ b/lib/compiler/src/beam_jump.erl
@@ -527,6 +527,10 @@ ulbl({bs_init,Lbl,_,_,_,_}, Used) ->
     mark_used(Lbl, Used);
 ulbl({bs_put,Lbl,_,_}, Used) ->
     mark_used(Lbl, Used);
+ulbl({put_map,Lbl,_Src,_Dst,_Live,_List}, Used) ->
+    mark_used(Lbl, Used);
+ulbl({get_map_element,Lbl,_Src,_Key,_Dst}, Used) ->
+    mark_used(Lbl, Used);
 ulbl(_, Used) -> Used.
 
 mark_used({f,0}, Used) -> Used;
diff --git a/lib/compiler/src/beam_split.erl b/lib/compiler/src/beam_split.erl
index cacaaebffe..bbd4695289 100644
--- a/lib/compiler/src/beam_split.erl
+++ b/lib/compiler/src/beam_split.erl
@@ -49,6 +49,12 @@ split_block([{set,[R],As,{bif,N,{f,Lbl}=Fail}}|Is], Bl, Acc) when Lbl =/= 0 ->
 split_block([{set,[R],As,{alloc,Live,{gc_bif,N,{f,Lbl}=Fail}}}|Is], Bl, Acc)
   when Lbl =/= 0 ->
     split_block(Is, [], [{gc_bif,N,Fail,Live,As,R}|make_block(Bl, Acc)]);
+split_block([{set,[D],[S|Puts],{alloc,R,{put_map,{f,Lbl}=Fail}}}|Is], Bl, Acc)
+  when Lbl =/= 0 ->
+    split_block(Is, [], [{put_map,Fail,S,D,R,{list,Puts}}|make_block(Bl, Acc)]);
+split_block([{set,[D],[S],{get_map_element,K,{f,Lbl}=Fail}}|Is], Bl, Acc)
+  when Lbl =/= 0 ->
+    split_block(Is, [], [{get_map_element,Fail,S,K,D}|make_block(Bl, Acc)]);
 split_block([{set,[R],[],{'catch',L}}|Is], Bl, Acc) ->
     split_block(Is, [], [{'catch',R,L}|make_block(Bl, Acc)]);
 split_block([{set,[],[],{line,_}=Line}|Is], Bl, Acc) ->
diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index 48f5135aca..37b08f43d3 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -865,6 +865,21 @@ valfun_4({bs_final,{f,Fail},Dst}, Vst0) ->
 valfun_4({bs_final2,Src,Dst}, Vst0) ->
     assert_term(Src, Vst0),
     set_type_reg(binary, Dst, Vst0);
+%% Map instructions.
+valfun_4({put_map,{f,Fail},Src,Dst,Live,{list,List}}, Vst0) ->
+    verify_live(Live, Vst0),
+    verify_y_init(Vst0),
+    [assert_term(Term, Vst0) || Term <- List],
+    assert_term(Src, Vst0),
+    Vst1 = heap_alloc(0, Vst0),
+    Vst2 = branch_state(Fail, Vst1),
+    Vst = prune_x_regs(Live, Vst2),
+    set_type_reg(term, Dst, Vst);
+valfun_4({get_map_element,{f,Fail},Src,Key,Dst}, Vst0) ->
+    assert_term(Src, Vst0),
+    assert_term(Key, Vst0),
+    Vst = branch_state(Fail, Vst0),
+    set_type_reg(term, Dst, Vst);
 valfun_4(_, _) ->
     error(unknown_instruction).
 
diff --git a/lib/compiler/src/core_lib.erl b/lib/compiler/src/core_lib.erl
index 824be9ff7f..f506901099 100644
--- a/lib/compiler/src/core_lib.erl
+++ b/lib/compiler/src/core_lib.erl
@@ -105,6 +105,10 @@ vu_expr(V, #c_cons{hd=H,tl=T}) ->
     vu_expr(V, H) orelse vu_expr(V, T);
 vu_expr(V, #c_tuple{es=Es}) ->
     vu_expr_list(V, Es);
+vu_expr(V, #c_map{es=Es}) ->
+    vu_expr_list(V, Es);
+vu_expr(V, #c_map_pair{key=Key,val=Val}) ->
+    vu_expr_list(V, [Key,Val]);
 vu_expr(V, #c_binary{segments=Ss}) ->
     vu_seg_list(V, Ss);
 vu_expr(V, #c_fun{vars=Vs,body=B}) ->
diff --git a/lib/compiler/src/genop.tab b/lib/compiler/src/genop.tab
index ebc9b1c85b..861acd3932 100755
--- a/lib/compiler/src/genop.tab
+++ b/lib/compiler/src/genop.tab
@@ -528,3 +528,10 @@ BEAM_FORMAT_NUMBER=0
 # R15A
 
 153: line/1
+
+# R16
+
+154: put_map/5
+155: is_map/2
+156: has_map_field/3
+157: get_map_element/4
diff --git a/lib/compiler/src/sys_core_dsetel.erl b/lib/compiler/src/sys_core_dsetel.erl
index f6696992b9..c7c8343c35 100644
--- a/lib/compiler/src/sys_core_dsetel.erl
+++ b/lib/compiler/src/sys_core_dsetel.erl
@@ -102,6 +102,13 @@ visit(Env, #c_literal{}=R) ->
 visit(Env0, #c_tuple{es=Es0}=R) ->
     {Es1,Env1} = visit_list(Env0, Es0),
     {R#c_tuple{es=Es1}, Env1};
+visit(Env0, #c_map{es=Es0}=R) ->
+    {Es1,Env1} = visit_list(Env0, Es0),
+    {R#c_map{es=Es1}, Env1};
+visit(Env0, #c_map_pair{key=K0,val=V0}=R) ->
+    {K,Env1} = visit(Env0, K0),
+    {V,Env2} = visit(Env1, V0),
+    {R#c_map_pair{key=K,val=V}, Env2};
 visit(Env0, #c_cons{hd=H0,tl=T0}=R) ->
     {H1,Env1} = visit(Env0, H0),
     {T1,Env2} = visit(Env1, T0),
@@ -212,6 +219,11 @@ visit_pat(Env0, #c_var{name=V}, Vs) ->
     {[V|Vs], dict:store(V, 0, Env0)};
 visit_pat(Env0, #c_tuple{es=Es}, Vs) ->
     visit_pats(Es, Env0, Vs);
+visit_pat(Env0, #c_map{es=Es}, Vs) ->
+    visit_pats(Es, Env0, Vs);
+visit_pat(Env0, #c_map_pair{key=V,val=K}, Vs0) ->
+    {Vs1, Env1} = visit_pat(Env0, V, Vs0),
+    visit_pat(Env1, K, Vs1);
 visit_pat(Env0, #c_cons{hd=H,tl=T}, Vs0) ->
     {Vs1, Env1} = visit_pat(Env0, H, Vs0),
     visit_pat(Env1, T, Vs1);
diff --git a/lib/compiler/src/sys_core_fold.erl b/lib/compiler/src/sys_core_fold.erl
index a388960312..672a8b94c0 100644
--- a/lib/compiler/src/sys_core_fold.erl
+++ b/lib/compiler/src/sys_core_fold.erl
@@ -246,6 +246,16 @@ expr(#c_tuple{anno=Anno,es=Es0}=Tuple, Ctxt, Sub) ->
 	value ->
 	    ann_c_tuple(Anno, Es)
     end;
+expr(#c_map{var=V0,es=Es0}=Map, Ctxt, Sub) ->
+    Es = pair_list(Es0, Ctxt, Sub),
+    case Ctxt of
+	effect ->
+	    add_warning(Map, useless_building),
+	    expr(make_effect_seq(Es, Sub), Ctxt, Sub);
+	value ->
+	    V = expr(V0, Ctxt, Sub),
+	    Map#c_map{var=V,es=Es}
+    end;
 expr(#c_binary{segments=Ss}=Bin0, Ctxt, Sub) ->
     %% Warn for useless building, but always build the binary
     %% anyway to preserve a possible exception.
@@ -408,6 +418,16 @@ expr(#c_try{anno=A,arg=E0,vars=Vs0,body=B0,evars=Evs0,handler=H0}=Try, _, Sub0)
 expr_list(Es, Ctxt, Sub) ->
     [expr(E, Ctxt, Sub) || E <- Es].
 
+pair_list(Es, Ctxt, Sub) ->
+    [pair(E, Ctxt, Sub) || E <- Es].
+
+pair(#c_map_pair{key=K,val=V}, effect, Sub) ->
+    make_effect_seq([K,V], Sub);
+pair(#c_map_pair{key=K0,val=V0}=Pair, value=Ctxt, Sub) ->
+    K = expr(K0, Ctxt, Sub),
+    V = expr(V0, Ctxt, Sub),
+    Pair#c_map_pair{key=K,val=V}.
+
 bitstr_list(Es, Sub) ->
     [bitstr(E, Sub) || E <- Es].
 
@@ -1500,6 +1520,9 @@ pattern(#c_cons{anno=Anno,hd=H0,tl=T0}, Isub, Osub0) ->
 pattern(#c_tuple{anno=Anno,es=Es0}, Isub, Osub0) ->
     {Es1,Osub1} = pattern_list(Es0, Isub, Osub0),
     {ann_c_tuple(Anno, Es1),Osub1};
+pattern(#c_map{anno=Anno,es=Es0}=Map, Isub, Osub0) ->
+    {Es1,Osub1} = map_pair_pattern_list(Es0, Isub, Osub0),
+    {Map#c_map{anno=Anno,es=Es1},Osub1};
 pattern(#c_binary{segments=V0}=Pat, Isub, Osub0) ->
     {V1,Osub1} = bin_pattern_list(V0, Isub, Osub0),
     {Pat#c_binary{segments=V1},Osub1};
@@ -1509,6 +1532,15 @@ pattern(#c_alias{var=V0,pat=P0}=Pat, Isub, Osub0) ->
     Osub = update_types(V1, [P1], Osub2),
     {Pat#c_alias{var=V1,pat=P1},Osub}.
 
+map_pair_pattern_list(Ps0, Isub, Osub0) ->
+    {Ps,{_,Osub}} = mapfoldl(fun map_pair_pattern/2, {Isub,Osub0}, Ps0),
+    {Ps,Osub}.
+
+map_pair_pattern(#c_map_pair{key=K0,val=V0}=Pair, {Isub,Osub0}) ->
+    {K,Osub1} = pattern(K0, Isub, Osub0),
+    {V,Osub} = pattern(V0, Isub, Osub1),
+    {Pair#c_map_pair{key=K,val=V},{Isub,Osub}}.
+
 bin_pattern_list(Ps0, Isub, Osub0) ->
     {Ps,{_,Osub}} = mapfoldl(fun bin_pattern/2, {Isub,Osub0}, Ps0),
     {Ps,Osub}.
diff --git a/lib/compiler/src/v3_codegen.erl b/lib/compiler/src/v3_codegen.erl
index f534500671..eff43b584a 100644
--- a/lib/compiler/src/v3_codegen.erl
+++ b/lib/compiler/src/v3_codegen.erl
@@ -210,6 +210,8 @@ need_heap_0([], H, Acc) ->
 
 need_heap_1(#l{ke={set,_,{binary,_}},i=I}, H) ->
     {need_heap_need(I, H),0};
+need_heap_1(#l{ke={set,_,{map,_,_}},i=I}, H) ->
+    {need_heap_need(I, H),0};
 need_heap_1(#l{ke={set,_,Val}}, H) ->
     %% Just pass through adding to needed heap.
     {[],H + case Val of
@@ -623,6 +625,8 @@ select_cg(#l{ke={type_clause,bin_int,S}}, {var,V}, Tf, _Vf, Bef, St) ->
     select_bin_segs(S, V, Tf, Bef, St);
 select_cg(#l{ke={type_clause,bin_end,[S]}}, {var,V}, Tf, _Vf, Bef, St) ->
     select_bin_end(S, V, Tf, Bef, St);
+select_cg(#l{ke={type_clause,map,S}}, {var,V}, Tf, Vf, Bef, St) ->
+    select_map(S, V, Tf, Vf, Bef, St);
 select_cg(#l{ke={type_clause,Type,Scs}}, {var,V}, Tf, Vf, Bef, St0) ->
     {Vis,{Aft,St1}} =
 	mapfoldl(fun (S, {Int,Sta}) ->
@@ -637,6 +641,10 @@ select_val_cg(tuple, R, [Arity,{f,Lbl}], Tf, Vf, [{label,Lbl}|Sis]) ->
     [{test,is_tuple,{f,Tf},[R]},{test,test_arity,{f,Vf},[R,Arity]}|Sis];
 select_val_cg(tuple, R, Vls, Tf, Vf, Sis) ->
     [{test,is_tuple,{f,Tf},[R]},{select_tuple_arity,R,{f,Vf},{list,Vls}}|Sis];
+select_val_cg(map, R, [_Val,{f,Lbl}], Fail, Fail, [{label,Lbl}|Sis]) ->
+    [{test,is_map,{f,Fail},[R]}|Sis];
+select_val_cg(map, R, [_Val,{f,Lbl}|_], Tf, _Vf, [{label,Lbl}|Sis]) ->
+    [{test,is_map,{f,Tf},[R]}|Sis];
 select_val_cg(Type, R, [Val, {f,Lbl}], Fail, Fail, [{label,Lbl}|Sis]) ->
     [{test,is_eq_exact,{f,Fail},[R,{Type,Val}]}|Sis];
 select_val_cg(Type, R, [Val, {f,Lbl}], Tf, Vf, [{label,Lbl}|Sis]) ->
@@ -915,6 +923,36 @@ select_extract_tuple(Src, Vs, I, Vdb, Bef, St) ->
     {Es,{Aft,_}} = flatmapfoldl(F, {Bef,0}, Vs),
     {Es,Aft,St}.
 
+select_map(Scs, V, Tf, Vf, Bef, St0) ->
+    Reg = fetch_var(V, Bef),
+    {Is,Aft,St1} =
+	match_fmf(fun(#l{ke={val_clause,{map,Es},B},i=I,vdb=Vdb}, Fail, St1) ->
+			  select_map_val(V, Es, B, Fail, I, Vdb, Bef, St1)
+		  end, Vf, St0, Scs),
+    {[{test,is_map,{f,Tf},[Reg]}|Is],Aft,St1}.
+
+select_map_val(V, Es, B, Fail, I, Vdb, Bef, St0) ->
+    {Eis,Int,St1} = select_extract_map(V, Es, Fail, I, Vdb, Bef, St0),
+    {Bis,Aft,St2} = match_cg(B, Fail, Int, St1),
+    {Eis++Bis,Aft,St2}.
+
+select_extract_map(Src, Vs, Fail, I, Vdb, Bef, St) ->
+    F = fun ({map_pair,Key,{var,V}}, Int0) ->
+		Rsrc = fetch_var(Src, Int0),
+		case vdb_find(V, Vdb) of
+		    {V,_,L} when L =< I ->
+			{[{test,has_map_field,{f,Fail},[Rsrc,Key]}],Int0};
+		    _Other ->
+			Reg1 = put_reg(V, Int0#sr.reg),
+			Int1 = Int0#sr{reg=Reg1},
+			{[{get_map_element,{f,Fail},
+			   Rsrc,Key,fetch_reg(V, Reg1)}],
+			 Int1}
+		end
+	end,
+    {Es,Aft} = flatmapfoldl(F, Bef, Vs),
+    {Es,Aft,St}.
+
 select_extract_cons(Src, [{var,Hd}, {var,Tl}], I, Vdb, Bef, St) ->
     {Es,Aft} = case {vdb_find(Hd, Vdb), vdb_find(Tl, Vdb)} of
 		   {{_,_,Lhd}, {_,_,Ltl}} when Lhd =< I, Ltl =< I ->
@@ -1408,7 +1446,7 @@ catch_cg(C, {var,R}, Le, Vdb, Bef, St0) ->
 %%  annotation must reflect this and make sure that the return
 %%  variable is allocated first.
 %%
-%%  put_list for constructing a cons is an atomic instruction
+%%  put_list and put_map are atomic instructions, both of
 %%  which can safely resuse one of the source registers as target.
 
 set_cg([{var,R}], {cons,Es}, Le, Vdb, Bef, St) ->
@@ -1448,6 +1486,30 @@ set_cg([{var,R}], {binary,Segs}, Le, Vdb, Bef,
     %% Now generate the complete code for constructing the binary.
     Code = cg_binary(PutCode, Target, Temp, Fail, MaxRegs, Le#l.a),
     {Sis++Code,Aft,St};
+set_cg([{var,R}], {map,SrcMap,Es}, Le, Vdb, Bef,
+       #cg{in_catch=InCatch,bfail=Bfail}=St) ->
+    Fail = {f,Bfail},
+    {Sis,Int0} =
+	case InCatch of
+	    true -> adjust_stack(Bef, Le#l.i, Le#l.i+1, Vdb);
+	    false -> {[],Bef}
+	end,
+    Line = line(Le#l.a),
+    SrcReg = case SrcMap of
+		 {var,SrcVar} -> fetch_var(SrcVar, Int0);
+		 _ -> SrcMap
+	     end,
+    List = flatmap(fun({map_pair,K,{var,V}}) ->
+			   [K,fetch_var(V, Int0)];
+		      ({map_pair,K,E}) ->
+			   [K,E]
+		   end, sort(Es)),
+    Live = max_reg(Bef#sr.reg),
+    Int1 = clear_dead(Int0, Le#l.i, Vdb),
+    Aft = Bef#sr{reg=put_reg(R, Int1#sr.reg)},
+    Target = fetch_reg(R, Aft#sr.reg),
+    Code = [Line,{put_map,Fail,SrcReg,Target,Live,{list,List}}],
+    {Sis++Code,Aft,St};
 set_cg([{var,R}], Con, Le, Vdb, Bef, St) ->
     %% Find a place for the return register first.
     Int = Bef#sr{reg=put_reg(R, Bef#sr.reg)},
diff --git a/lib/compiler/src/v3_core.erl b/lib/compiler/src/v3_core.erl
index a5f31f3844..1ef710a260 100644
--- a/lib/compiler/src/v3_core.erl
+++ b/lib/compiler/src/v3_core.erl
@@ -487,6 +487,15 @@ expr({tuple,L,Es0}, St0) ->
     {Es1,Eps,St1} = safe_list(Es0, St0),
     A = lineno_anno(L, St1),
     {ann_c_tuple(A, Es1),Eps,St1};
+expr({map,L,Es0}, St0) ->
+    {Es1,Eps,St1} = map_pair_list(Es0, St0),
+    A = lineno_anno(L, St1),
+    {#c_map{anno=A,es=Es1},Eps,St1};
+expr({map,L,{var,Vl,Map},Es0}, St0) ->
+    {Es1,Eps,St1} = map_pair_list(Es0, St0),
+    A = lineno_anno(L, St1),
+    Av = lineno_anno(Vl, St1),
+    {#c_map{anno=A,var=#c_var{anno=Av,name=Map},es=Es1},Eps,St1};
 expr({bin,L,Es0}, St0) ->
     try expr_bin(Es0, lineno_anno(L, St0), St0) of
 	{_,_,_}=Res -> Res
@@ -695,6 +704,14 @@ make_bool_switch_guard(L, E, V, T, F) ->
       {clause,NegL,[V],[],[V]}
      ]}.
 
+map_pair_list(Es, St) ->
+    foldr(fun ({map_field,L,K0,V0}, {Ces,Esp,St0}) ->
+		  {K,Ep0,St1} = safe(K0, St0),
+		  {V,Ep1,St2} = safe(V0, St1),
+		  A = lineno_anno(L, St2),
+		  Pair = #c_map_pair{anno=A,key=K,val=V},
+		  {[Pair|Ces],Ep0 ++ Ep1 ++ Esp,St2}
+	  end, {[],[],St}, Es).
 
 %% try_exception([ExcpClause], St) -> {[ExcpVar],Handler,St}.
 
@@ -1478,6 +1495,12 @@ pattern({cons,L,H,T}, St) ->
     ann_c_cons(lineno_anno(L, St), pattern(H, St), pattern(T, St));
 pattern({tuple,L,Ps}, St) ->
     ann_c_tuple(lineno_anno(L, St), pattern_list(Ps, St));
+pattern({map,L,Ps}, St) ->
+    #c_map{anno=lineno_anno(L, St),es=sort(pattern_list(Ps, St))};
+pattern({map_field,L,K,V}, St) ->
+    #c_map_pair{anno=lineno_anno(L, St),
+		key=pattern(K, St),
+		val=pattern(V, St)};
 pattern({bin,L,Ps}, St) ->
     %% We don't create a #ibinary record here, since there is
     %% no need to hold any used/new annotations in a pattern.
@@ -1823,6 +1846,12 @@ upattern(#c_cons{hd=H0,tl=T0}=Cons, Ks, St0) ->
 upattern(#c_tuple{es=Es0}=Tuple, Ks, St0) ->
     {Es1,Esg,Esv,Eus,St1} = upattern_list(Es0, Ks, St0),
     {Tuple#c_tuple{es=Es1},Esg,Esv,Eus,St1};
+upattern(#c_map{es=Es0}=Map, Ks, St0) ->
+    {Es1,Esg,Esv,Eus,St1} = upattern_list(Es0, Ks, St0),
+    {Map#c_map{es=Es1},Esg,Esv,Eus,St1};
+upattern(#c_map_pair{val=V0}=MapPair, Ks, St0) ->
+    {V,Vg,Vv,Vu,St1} = upattern(V0, Ks, St0),
+    {MapPair#c_map_pair{val=V},Vg,Vv,Vu,St1};
 upattern(#c_binary{segments=Es0}=Bin, Ks, St0) ->
     {Es1,Esg,Esv,Eus,St1} = upat_bin(Es0, Ks, St0),
     {Bin#c_binary{segments=Es1},Esg,Esv,Eus,St1};
@@ -2152,6 +2181,9 @@ is_simple(#c_literal{}) -> true;
 is_simple(#c_cons{hd=H,tl=T}) ->
     is_simple(H) andalso is_simple(T);
 is_simple(#c_tuple{es=Es}) -> is_simple_list(Es);
+is_simple(#c_map{es=Es}) -> is_simple_list(Es);
+is_simple(#c_map_pair{key=K,val=V}) ->
+    is_simple(K) andalso is_simple(V);
 is_simple(_) -> false.
 
 -spec is_simple_list([cerl:cerl()]) -> boolean().
diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl
index 65f1251099..84b3a4e37f 100644
--- a/lib/compiler/src/v3_kernel.erl
+++ b/lib/compiler/src/v3_kernel.erl
@@ -272,6 +272,10 @@ expr(#c_cons{anno=A,hd=Ch,tl=Ct}, Sub, St0) ->
 expr(#c_tuple{anno=A,es=Ces}, Sub, St0) ->
     {Kes,Ep,St1} = atomic_list(Ces, Sub, St0),
     {#k_tuple{anno=A,es=Kes},Ep,St1};
+expr(#c_map{anno=A,var=Var0,es=Ces}, Sub, St0) ->
+    {Var,[],St1} = expr(Var0, Sub, St0),
+    {Kes,Ep,St2} = map_pairs(Ces, Sub, St1),
+    {#k_map{anno=A,var=Var,es=Kes},Ep,St2};
 expr(#c_binary{anno=A,segments=Cv}, Sub, St0) ->
     try atomic_bin(Cv, Sub, St0) of
 	{Kv,Ep,St1} ->
@@ -493,6 +497,13 @@ translate_match_fail_1(Anno, As, Sub, #kern{ff=FF}) ->
 translate_fc(Args) ->
     [#c_literal{val=function_clause},make_list(Args)].
 
+map_pairs(Es, Sub, St) ->
+    foldr(fun(#c_map_pair{key=K0,val=V0}, {Kes,Esp,St0}) ->
+		  {K,[],St1} = expr(K0, Sub, St0),
+		  {V,Ep,St2} = atomic(V0, Sub, St1),
+		  {[#k_map_pair{key=K,val=V}|Kes],Ep ++ Esp,St2}
+	  end, {[],[],St}, Es).
+
 %% call_type(Module, Function, Arity) -> call | bif | apply | error.
 %%  Classify the call.
 call_type(#c_literal{val=M}, #c_literal{val=F}, Ar) when is_atom(M), is_atom(F) ->
@@ -648,6 +659,13 @@ pattern(#c_cons{anno=A,hd=Ch,tl=Ct}, Isub, Osub0, St0) ->
 pattern(#c_tuple{anno=A,es=Ces}, Isub, Osub0, St0) ->
     {Kes,Osub1,St1} = pattern_list(Ces, Isub, Osub0, St0),
     {#k_tuple{anno=A,es=Kes},Osub1,St1};
+pattern(#c_map{anno=A,es=Ces}, Isub, Osub0, St0) ->
+    {Kes,Osub1,St1} = pattern_list(Ces, Isub, Osub0, St0),
+    {#k_map{anno=A,es=Kes},Osub1,St1};
+pattern(#c_map_pair{anno=A,key=Kk0,val=Cv},Isub, Osub0, St0) ->
+    Kk = #k_atom{val=Kk0#c_literal.val},
+    {Kv,Osub1,St1} = pattern(Cv, Isub, Osub0, St0),
+    {#k_map_pair{anno=A,key=Kk,val=Kv},Osub1,St1};
 pattern(#c_binary{anno=A,segments=Cv}, Isub, Osub0, St0) ->
     {Kv,Osub1,St1} = pattern_bin(Cv, Isub, Osub0, St0),
     {#k_binary{anno=A,segs=Kv},Osub1,St1};
@@ -1015,7 +1033,8 @@ match_con_1([U|_Us] = L, Cs, Def, St0) ->
     %% Extract clauses for different constructors (types).
     %%ok = io:format("match_con ~p~n", [Cs]),
     Ttcs = select_types([k_binary], Cs) ++ select_bin_con(Cs) ++
-	select_types([k_cons,k_tuple,k_atom,k_float,k_int,k_nil,k_literal], Cs),
+	select_types([k_cons,k_tuple,k_map,k_atom,k_float,k_int,
+		      k_nil,k_literal], Cs),
     %%ok = io:format("ttcs = ~p~n", [Ttcs]),
     {Scs,St1} =
 	mapfoldl(fun ({T,Tcs}, St) ->
@@ -1255,6 +1274,8 @@ group_value(k_bin_seg, Cs) ->
     group_bin_seg(Cs);
 group_value(k_bin_int, Cs) ->
     [Cs];
+group_value(k_map, Cs) ->
+    group_map(Cs);
 group_value(_, Cs) ->
     %% group_value(Cs).
     Cd = foldl(fun (C, Gcs0) -> dict:append(clause_val(C), C, Gcs0) end,
@@ -1267,6 +1288,12 @@ group_bin_seg([C1|Cs]) ->
     [[C1|More]|group_bin_seg(Rest)];
 group_bin_seg([]) -> [].
 
+group_map([C1|Cs]) ->
+    V1 = clause_val(C1),
+    {More,Rest} = splitwith(fun (C) -> clause_val(C) =:= V1 end, Cs),
+    [[C1|More]|group_map(Rest)];
+group_map([]) -> [].
+
 %% Profiling shows that this quadratic implementation account for a big amount
 %% of the execution time if there are many values.
 % group_value([C|Cs]) ->
@@ -1315,6 +1342,12 @@ get_match(#k_bin_int{}=BinInt, St0) ->
 get_match(#k_tuple{es=Es}, St0) ->
     {Mes,St1} = new_vars(length(Es), St0),
     {#k_tuple{es=Mes},Mes,St1};
+get_match(#k_map{es=Es0}, St0) ->
+    {Mes,St1} = new_vars(length(Es0), St0),
+    {Es,_} = mapfoldl(fun(#k_map_pair{}=Pair, [V|Vs]) ->
+			      {Pair#k_map_pair{val=V},Vs}
+		      end, Mes, Es0),
+    {#k_map{es=Es},Mes,St1};
 get_match(M, St) ->
     {M,[],St}.
 
@@ -1331,7 +1364,11 @@ new_clauses(Cs0, U, St) ->
 				     [S,N|As];
 				 #k_bin_int{next=N} ->
 				     [N|As];
-				 _Other -> As
+				 #k_map{es=Es} ->
+				     Vals = [V || #k_map_pair{val=V} <- Es],
+				     Vals ++ As;
+				 _Other ->
+				     As
 			     end,
 		      Vs = arg_alias(Arg),
 		      Osub1 = foldl(fun (#k_var{name=V}, Acc) ->
@@ -1406,6 +1443,7 @@ arg_con(Arg) ->
 	#k_nil{} -> k_nil;
 	#k_cons{} -> k_cons; 
 	#k_tuple{} -> k_tuple;
+	#k_map{} -> k_map;
 	#k_binary{} -> k_binary;
 	#k_bin_end{} -> k_bin_end;
 	#k_bin_seg{} -> k_bin_seg;
@@ -1426,7 +1464,13 @@ arg_val(Arg, C) ->
 		    {#k_var{name=get_vsub(V, Isub)},U,T,Fs};
 		_ ->
 		    {set_kanno(S, []),U,T,Fs}
-	    end
+	    end;
+	#k_map{es=Es} ->
+	    Keys = [begin
+			#k_map_pair{key=#k_atom{val=Key}} = Pair,
+			Key
+		    end || Pair <- Es],
+	    ordsets:from_list(Keys)
     end.
 
 %% ubody_used_vars(Expr, State) -> [UsedVar]
@@ -1795,6 +1839,10 @@ lit_vars(#k_atom{}) -> [];
 lit_vars(#k_nil{}) -> [];
 lit_vars(#k_cons{hd=H,tl=T}) ->
     union(lit_vars(H), lit_vars(T));
+lit_vars(#k_map{var=Var,es=Es}) ->
+    lit_list_vars([Var|Es]);
+lit_vars(#k_map_pair{key=K,val=V}) ->
+    union(lit_vars(K), lit_vars(V));
 lit_vars(#k_binary{segs=V}) -> lit_vars(V);
 lit_vars(#k_bin_end{}) -> [];
 lit_vars(#k_bin_seg{size=Size,seg=S,next=N}) ->
@@ -1830,7 +1878,11 @@ pat_vars(#k_bin_int{size=Size}) ->
     {U,[]};
 pat_vars(#k_bin_end{}) -> {[],[]};
 pat_vars(#k_tuple{es=Es}) ->
-    pat_list_vars(Es).
+    pat_list_vars(Es);
+pat_vars(#k_map{es=Es}) ->
+    pat_list_vars(Es);
+pat_vars(#k_map_pair{val=V}) ->
+    pat_vars(V).
 
 pat_list_vars(Ps) ->
     foldl(fun (P, {Used0,New0}) ->
diff --git a/lib/compiler/src/v3_kernel.hrl b/lib/compiler/src/v3_kernel.hrl
index fb8baf398b..6671109afb 100644
--- a/lib/compiler/src/v3_kernel.hrl
+++ b/lib/compiler/src/v3_kernel.hrl
@@ -38,6 +38,8 @@
 -record(k_nil, {anno=[]}).
 
 -record(k_tuple, {anno=[],es}).
+-record(k_map, {anno=[],var,es}).
+-record(k_map_pair, {anno=[],key,val}).
 -record(k_cons, {anno=[],hd,tl}).
 -record(k_binary, {anno=[],segs}).
 -record(k_bin_seg, {anno=[],size,unit,type,flags,seg,next}).
diff --git a/lib/compiler/src/v3_kernel_pp.erl b/lib/compiler/src/v3_kernel_pp.erl
index e363a5387a..1af90792d3 100644
--- a/lib/compiler/src/v3_kernel_pp.erl
+++ b/lib/compiler/src/v3_kernel_pp.erl
@@ -104,6 +104,19 @@ format_1(#k_tuple{es=Es}, Ctxt) ->
      format_hseq(Es, ",", ctxt_bump_indent(Ctxt, 1), fun format/2),
      $}
     ];
+format_1(#k_map{var=#k_var{}=Var,es=Es}, Ctxt) ->
+    [$~,${,
+     format_hseq(Es, ",", ctxt_bump_indent(Ctxt, 1), fun format/2),
+     " | ",format_1(Var, Ctxt),
+     $},$~
+    ];
+format_1(#k_map{es=Es}, Ctxt) ->
+    [$~,${,
+     format_hseq(Es, ",", ctxt_bump_indent(Ctxt, 1), fun format/2),
+     $},$~
+    ];
+format_1(#k_map_pair{key=K,val=V}, Ctxt) ->
+    ["~<",format(K, Ctxt),",",format(V, Ctxt),">"];
 format_1(#k_binary{segs=S}, Ctxt) ->
     ["#<",format(S, ctxt_bump_indent(Ctxt, 2)),">#"];
 format_1(#k_bin_seg{next=Next}=S, Ctxt) ->
diff --git a/lib/compiler/src/v3_life.erl b/lib/compiler/src/v3_life.erl
index 2cc3493570..507f5d0df1 100644
--- a/lib/compiler/src/v3_life.erl
+++ b/lib/compiler/src/v3_life.erl
@@ -323,7 +323,9 @@ type(k_tuple) -> tuple;
 type(k_binary) -> binary;
 type(k_bin_seg) -> bin_seg;
 type(k_bin_int) -> bin_int;
-type(k_bin_end) -> bin_end.
+type(k_bin_end) -> bin_end;
+type(k_map) -> map;
+type(k_map_pair) -> map_pair.
 
 %% variable(Klit) -> Lit.
 %% var_list([Klit]) -> [Lit].
@@ -365,6 +367,10 @@ literal(#k_bin_end{}, Ctxt) ->
     {bin_end,Ctxt};
 literal(#k_tuple{es=Es}, Ctxt) ->
     {tuple,literal_list(Es, Ctxt)};
+literal(#k_map{var=Var,es=Es}, Ctxt) ->
+    {map,literal(Var, Ctxt),literal_list(Es, Ctxt)};
+literal(#k_map_pair{key=K,val=V}, Ctxt) ->
+    {map_pair,literal(K, Ctxt),literal(V, Ctxt)};
 literal(#k_literal{val=V}, _Ctxt) ->
     {literal,V}.
 
@@ -393,7 +399,11 @@ literal2(#k_bin_int{size=S,unit=U,flags=Fs,val=Int,next=N}, Ctxt) ->
 literal2(#k_bin_end{}, Ctxt) ->
     {bin_end,Ctxt};
 literal2(#k_tuple{es=Es}, Ctxt) ->
-    {tuple,literal_list2(Es, Ctxt)}.
+    {tuple,literal_list2(Es, Ctxt)};
+literal2(#k_map{es=Es}, Ctxt) ->
+    {map,literal_list2(Es, Ctxt)};
+literal2(#k_map_pair{key=K,val=V}, Ctxt) ->
+    {map_pair,literal2(K, Ctxt),literal2(V, Ctxt)}.
 
 literal_list2(Ks, Ctxt) ->
     [literal2(K, Ctxt) || K <- Ks].