compiler: Implement different instructions for => and :=

10 files changed, 135 insertions, 40 deletions

diff --git a/lib/compiler/src/beam_a.erl b/lib/compiler/src/beam_a.erl
index c590c5e35b..3dfa67a771 100644
--- a/lib/compiler/src/beam_a.erl
+++ b/lib/compiler/src/beam_a.erl
@@ -88,6 +88,10 @@ rename_instr({bs_private_append=I,F,Sz,U,Src,Flags,Dst}) ->
     {bs_init,F,{I,U,Flags},none,[Sz,Src],Dst};
 rename_instr(bs_init_writable=I) ->
     {bs_init,{f,0},I,1,[{x,0}],{x,0}};
+rename_instr({put_map_assoc,Fail,S,D,R,L}) ->
+    {put_map,Fail,assoc,S,D,R,L};
+rename_instr({put_map_exact,Fail,S,D,R,L}) ->
+    {put_map,Fail,exact,S,D,R,L};
 rename_instr({select_val=I,Reg,Fail,{list,List}}) ->
     {select,I,Reg,Fail,List};
 rename_instr({select_tuple_arity=I,Reg,Fail,{list,List}}) ->
diff --git a/lib/compiler/src/beam_block.erl b/lib/compiler/src/beam_block.erl
index f9e90b81d2..d5f2ffc444 100644
--- a/lib/compiler/src/beam_block.erl
+++ b/lib/compiler/src/beam_block.erl
@@ -152,8 +152,8 @@ 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({put_map,F,Op,S,D,R,{list,Puts}}) ->
+    {set,[D],[S|Puts],{alloc,R,{put_map,Op,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}};
@@ -387,7 +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,_,_,{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 6f802d0436..55f985ad0e 100644
--- a/lib/compiler/src/beam_clean.erl
+++ b/lib/compiler/src/beam_clean.erl
@@ -259,8 +259,9 @@ 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([{put_map=I,{f,Lbl},Op,Src,Dst,Live,List}|Is], Acc, D)
+  when Lbl =/= 0 ->
+    replace(Is, [{I,{f,label(Lbl, D)},Op,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) ->
diff --git a/lib/compiler/src/beam_flatten.erl b/lib/compiler/src/beam_flatten.erl
index ad9591ff05..534bc6d954 100644
--- a/lib/compiler/src/beam_flatten.erl
+++ b/lib/compiler/src/beam_flatten.erl
@@ -61,8 +61,8 @@ 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|Puts],{alloc,R,{put_map,Op,F}}}) ->
+    {put_map,F,Op,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;
diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl
index bbef75c219..1f720b94c3 100644
--- a/lib/compiler/src/beam_jump.erl
+++ b/lib/compiler/src/beam_jump.erl
@@ -527,7 +527,7 @@ 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) ->
+ulbl({put_map,Lbl,_Op,_Src,_Dst,_Live,_List}, Used) ->
     mark_used(Lbl, Used);
 ulbl({get_map_element,Lbl,_Src,_Key,_Dst}, Used) ->
     mark_used(Lbl, Used);
diff --git a/lib/compiler/src/beam_split.erl b/lib/compiler/src/beam_split.erl
index bbd4695289..638a4826ea 100644
--- a/lib/compiler/src/beam_split.erl
+++ b/lib/compiler/src/beam_split.erl
@@ -49,9 +49,10 @@ 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|Puts],{alloc,R,{put_map,Op,{f,Lbl}=Fail}}}|Is],
+	    Bl, Acc) when Lbl =/= 0 ->
+    split_block(Is, [], [{put_map,Fail,Op,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)]);
diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index 37b08f43d3..97f84da08f 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -866,15 +866,10 @@ 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({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_element,{f,Fail},Src,Key,Dst}, Vst0) ->
     assert_term(Src, Vst0),
     assert_term(Key, Vst0),
@@ -883,6 +878,16 @@ valfun_4({get_map_element,{f,Fail},Src,Key,Dst}, Vst0) ->
 valfun_4(_, _) ->
     error(unknown_instruction).
 
+verify_put_map(Fail, Src, Dst, Live, 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).
+
 %%
 %% Common code for validating bs_get* instructions.
 %%
diff --git a/lib/compiler/src/beam_z.erl b/lib/compiler/src/beam_z.erl
index 8c6b0c916d..9953a48710 100644
--- a/lib/compiler/src/beam_z.erl
+++ b/lib/compiler/src/beam_z.erl
@@ -74,6 +74,10 @@ undo_rename({bs_init,F,{I,Extra,U,Flags},Live,[Sz,Src],Dst}) ->
     {I,F,Sz,Extra,Live,U,Src,Flags,Dst};
 undo_rename({bs_init,_,bs_init_writable=I,_,_,_}) ->
     I;
+undo_rename({put_map,Fail,assoc,S,D,R,L}) ->
+    {put_map_assoc,Fail,S,D,R,L};
+undo_rename({put_map,Fail,exact,S,D,R,L}) ->
+    {put_map_exact,Fail,S,D,R,L};
 undo_rename({select,I,Reg,Fail,List}) ->
     {I,Reg,Fail,{list,List}};
 undo_rename(I) -> I.
diff --git a/lib/compiler/src/genop.tab b/lib/compiler/src/genop.tab
index 861acd3932..79b467f949 100755
--- a/lib/compiler/src/genop.tab
+++ b/lib/compiler/src/genop.tab
@@ -531,7 +531,8 @@ BEAM_FORMAT_NUMBER=0
 
 # R16
 
-154: put_map/5
-155: is_map/2
-156: has_map_field/3
-157: get_map_element/4
+154: put_map_assoc/5
+155: put_map_exact/5
+156: is_map/2
+157: has_map_field/3
+158: get_map_element/4
diff --git a/lib/compiler/src/v3_codegen.erl b/lib/compiler/src/v3_codegen.erl
index c1d555efac..db8ea04778 100644
--- a/lib/compiler/src/v3_codegen.erl
+++ b/lib/compiler/src/v3_codegen.erl
@@ -1488,7 +1488,7 @@ 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,
+set_cg([{var,R}], {map,SrcMap,Es0}, Le, Vdb, Bef,
        #cg{in_catch=InCatch,bfail=Bfail}=St) ->
     Fail = {f,Bfail},
     {Sis,Int0} =
@@ -1501,24 +1501,41 @@ set_cg([{var,R}], {map,SrcMap,Es}, Le, Vdb, Bef,
 		 {var,SrcVar} -> fetch_var(SrcVar, Int0);
 		 _ -> SrcMap
 	     end,
-
-    %% MapPairs in put_map must be sorted in ascending Key order.
-    %% Key literals must be unique when arriving here in v3_codegen.
-
-    SortedEs = lists:sort(fun({_,{_T1,K1},_},{_,{_T2,K2},_}) ->
-				  K1 =< K2
-			  end, Es),
-    List = flatmap(fun
-	    ({map_pair_assoc,K,{var,V}}) -> [K,fetch_var(V, Int0)];
-	    ({map_pair_exact,K,{var,V}}) -> [K,fetch_var(V, Int0)];
-	    ({map_pair_assoc,K,E}) -> [K,E];
-	    ({map_pair_exact,K,E}) -> [K,E]
-	end, SortedEs),
-    Live = max_reg(Bef#sr.reg),
+    {Assoc,Exact} =
+	try
+	    cg_map_pairs(Es0)
+	catch
+	    throw:badarg ->
+		{[],[{{float,0.0},{atom,badarg}},
+		     {{integer,0},{atom,badarg}}]}
+	end,
+    F = fun ({K,{var,V}}) -> [K,fetch_var(V, Int0)];
+	    ({K,E}) -> [K,E]
+	end,
+    AssocList = flatmap(F, Assoc),
+    ExactList = flatmap(F, Exact),
+    Live0 = 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}}],
+    Code = [Line] ++
+	case {AssocList,ExactList} of
+	    {[_|_],[]} ->
+		[{put_map_assoc,Fail,SrcReg,Target,Live0,{list,AssocList}}];
+	    {[_|_],[_|_]} ->
+		Live = case Target of
+			   {x,TargetX} when TargetX =:= Live0 ->
+			       Live0 + 1;
+			   _ ->
+			       Live0
+		       end,
+		[{put_map_assoc,Fail,SrcReg,Target,Live0,{list,AssocList}},
+		 {put_map_exact,Fail,Target,Target,Live,{list,ExactList}}];
+	    {[],[_|_]} ->
+		[{put_map_exact,Fail,SrcReg,Target,Live0,{list,ExactList}}];
+	    {[],[]} ->
+		[{put_map_assoc,Fail,SrcReg,Target,Live0,{list,[]}}]
+	end,
     {Sis++Code,Aft,St};
 set_cg([{var,R}], Con, Le, Vdb, Bef, St) ->
     %% Find a place for the return register first.
@@ -1532,6 +1549,68 @@ set_cg([{var,R}], Con, Le, Vdb, Bef, St) ->
 	  end,
     {Ais,clear_dead(Int, Le#l.i, Vdb),St}.
 
+%% cg_map_pairs(MapPairs) -> {Assoc,Exact}
+%%  Assoc = Exact = [{K,V}]
+%%
+%%  Remove multiple assignments to the same key, and return
+%%  one list key-value list with all keys that may or may not exist
+%%  (Assoc), and one with keys that must exist (Exact).
+%%
+
+cg_map_pairs(Es0) ->
+    Es = cg_map_pairs_1(Es0, 0),
+    R0 = sofs:relation(Es),
+    R1 = sofs:relation_to_family(R0),
+    R2 = sofs:to_external(R1),
+
+    %% R2 is now [{KeyValue,[{Order,Op,OriginalKey,Value}]}]
+    R3 = [begin
+	      %% The value for the last pair determines the value.
+	      {_,_,_,V} = lists:last(Vs),
+	      {Op,{_,SortOrder}=K} = map_pair_op_and_key(Vs),
+	      {Op,{SortOrder,K,V}}
+	  end || {_,Vs} <- R2],
+
+    %% R3 is now [{Op,{Key,Value}}]
+    R = lists:sort(R3),
+
+    %% R4 is now sorted with all alloc first in the list, followed by
+    %% all exact.
+    {Assoc,Exact} = lists:partition(fun({Op,_}) -> Op =:= assoc end, R),
+    {[{K,V} || {_,{_,K,V}} <- Assoc],
+     [{K,V} || {_,{_,K,V}} <- Exact]}.
+
+cg_map_pairs_1([{map_pair_assoc,{_,Kv}=K,V}|T], Order) ->
+    [{Kv,{Order,assoc,K,V}}|cg_map_pairs_1(T, Order+1)];
+cg_map_pairs_1([{map_pair_exact,{_,Kv}=K,V}|T], Order) ->
+    [{Kv,{Order,exact,K,V}}|cg_map_pairs_1(T, Order+1)];
+cg_map_pairs_1([], _) -> [].
+
+%% map_pair_op_and_key({_,Op,K,_}) -> {Operator,Key}
+%%  Determine the operator and key to use. Throw a 'badarg'
+%%  exception if there are contradictory exact updates.
+
+map_pair_op_and_key(L) ->
+    case [K || {_,exact,K,_} <- L] of
+	[K] ->
+	    %% There is a single ':=' operator. Use that key.
+	    {exact,K};
+	[K|T] ->
+	    %% There is more than one ':=' operator. All of them
+	    %% must have the same key.
+	    case lists:all(fun(E) -> E =:= K end, T) of
+		true ->
+		    {exact,K};
+		false ->
+		    %% Some keys are different, e.g. 1 and 1.0.
+		    throw(badarg)
+	    end;
+	[] ->
+	    %% Only '=>' operators. Use the first key in the list.
+	    [{_,assoc,K,_}|_] = L,
+	    {assoc,K}
+    end.
+
 %%%
 %%% Code generation for constructing binaries.
 %%%