Move grouping of map constructions from v3_core to v3_kernel

When translating a function with map construction:

  f(A) ->
    B = b,
    C = c,
    #{A=>1,B=>2,C=>3}.

v3_core would break apart the map construction into three
parts because of the way the map instructions in BEAM work --
variable keys need to be in their own instruction.

In the example, constant propagation will turn two of the
keys to literal keys. But the initial breaking apart will
not be undone, so there will still be three map constructions:

  'f'/1 =
    fun (_cor0) ->
      let <_cor3> = ~{::<_cor0,1>}~
	in let <_cor4> = ~{::<'b',2>|_cor3}~
	  in ~{::<'c',3>|_cor4}~

It would be possible to complicate the sys_core_fold pass
to regroup map operations so that we would get:

  'f'/1 =
    fun (_cor0) ->
      let <_cor3> = ~{::<_cor0,1>}~
        in ~{::<'b',2>,::<'c',3>|_cor3}~

A simpler way that allows to simplify the translation is
to skip the grouping in v3_core and translate the function
to:

  'f'/1 =
    fun (_cor0) ->
      ~{::<_cor0,1>,::<'b',2>,::<'c',3>}~

We will then let v3_kernel do the grouping while translating
from Core Erlang to Kernel Erlang.

2 files changed, 82 insertions, 99 deletions

diff --git a/lib/compiler/src/v3_core.erl b/lib/compiler/src/v3_core.erl
index 1d5eb85a1c..a9b54005d1 100644
--- a/lib/compiler/src/v3_core.erl
+++ b/lib/compiler/src/v3_core.erl
@@ -536,7 +536,7 @@ expr({tuple,L,Es0}, St0) ->
     A = record_anno(L, St1),
     {annotate_tuple(A, Es1, St1),Eps,St1};
 expr({map,L,Es0}, St0) ->
-    map_build_pair_chain(#c_literal{val=#{}},Es0,lineno_anno(L,St0),St0);
+    map_build_pairs(#c_literal{val=#{}}, Es0, lineno_anno(L, St0), St0);
 expr({map,L,M0,Es0}, St0) ->
     try expr_map(M0,Es0,lineno_anno(L, St0),St0) of
 	{_,_,_}=Res -> Res
@@ -779,66 +779,35 @@ expr_map(M0,Es0,A,St0) ->
 		    Fc = fail_clause([Fpat], A, #c_literal{val=badarg}),
 		    {#icase{anno=#a{anno=A},args=[M1],clauses=Cs,fc=Fc},Mps,St3};
 		{_,_} ->
-		    {M2,Eps,St2} = map_build_pair_chain(M1,Es0,A,St1),
+		    {M2,Eps,St2} = map_build_pairs(M1, Es0, A, St1),
 		    {M2,Mps++Eps,St2}
 	    end;
 	false -> throw({bad_map,bad_map})
     end.
 
-%% Group continuous literal blocks and single variables, i.e.
-%% M0#{ a := 1, b := V1, K1 := V2, K2 := 42}
-%% becomes equivalent to
-%% M1 = M0#{ a := 1, b := V1 },
-%% M2 = M1#{ K1 := V1 },
-%% M3 = M2#{ K2 := 42 }
-
-map_build_pair_chain(M,Es,A,St) ->
-    %% hack, remove iset if only literal
-    case map_build_pair_chain(M,Es,A,St,[]) of
-	{_,[#iset{arg=#c_literal{}=Val}],St1} -> {Val,[],St1};
-	Normal -> Normal
+map_build_pairs(Map0, Es0, Ann, St0) ->
+    {Es,Pre,St1} = map_build_pairs_1(Es0, St0),
+    case ann_c_map(Ann, Map0, Es) of
+	#c_literal{}=Map ->
+	    {Map,[],St1};
+	#c_map{}=Map ->
+	    {Var,St2} = new_var(St1),
+	    {Var,Pre++[#iset{var=Var,arg=Map}],St2}
     end.
 
-map_build_pair_chain(M0,[],_,St,Mps) ->
-    {M0,Mps,St};
-map_build_pair_chain(M0,Es0,A,St0,Mps) ->
-    % group continuous literal blocks
-    % Anno = #a{anno=[compiler_generated]},
-    % order is important, we need to reverse the literals
-    case map_pair_block(Es0,[],[],St0) of
-	{{CesL,EspL},{[],[]},Es1,St1} ->
-	    {MVar,St2} = new_var(St1),
-	    Pre = [#iset{var=MVar, arg=ann_c_map(A,M0,reverse(CesL))}],
-	    map_build_pair_chain(MVar,Es1,A,St2,Mps++EspL++Pre);
-	{{[],[]},{CesV,EspV},Es1,St1} ->
-	    {MVar,St2} = new_var(St1),
-	    Pre = [#iset{var=MVar, arg=#c_map{arg=M0,es=CesV, anno=A}}],
-	    map_build_pair_chain(MVar,Es1,A,St2,Mps ++ EspV++Pre);
-	{{CesL,EspL},{CesV,EspV},Es1,St1} ->
-	    {MVarL,St2} = new_var(St1),
-	    {MVarV,St3} = new_var(St2),
-	    Pre = [#iset{var=MVarL, arg=ann_c_map(A,M0,reverse(CesL))},
-		   #iset{var=MVarV, arg=#c_map{arg=MVarL,es=CesV,anno=A}}],
-	    map_build_pair_chain(MVarV,Es1,A,St3,Mps++EspL++EspV++Pre)
-    end.
-
-map_pair_block([{Op,L,K0,V0}|Es],Ces,Esp,St0) ->
-    {K,Ep0,St1} = safe(K0, St0),
-    {V,Ep1,St2} = safe(V0, St1),
-    A = lineno_anno(L, St2),
-    Pair0 = map_op_to_c_map_pair(Op),
-    Pair1 = Pair0#c_map_pair{anno=A,key=K,val=V},
-    case cerl:is_literal(K) of
-	true ->
-	    map_pair_block(Es,[Pair1|Ces],Ep0 ++ Ep1 ++ Esp,St2);
-	false ->
-	    {{Ces,Esp},{[Pair1],Ep0++Ep1},Es,St2}
-    end;
-map_pair_block([],Ces,Esp,St) ->
-    {{Ces,Esp},{[],[]},[],St}.
+map_build_pairs_1([{Op0,L,K0,V0}|Es], St0) ->
+    {K,Pre0,St1} = safe(K0, St0),
+    {V,Pre1,St2} = safe(V0, St1),
+    {Pairs,Pre2,St3} = map_build_pairs_1(Es, St2),
+    As = lineno_anno(L, St3),
+    Op = map_op(Op0),
+    Pair = cerl:ann_c_map_pair(As, Op, K, V),
+    {[Pair|Pairs],Pre0++Pre1++Pre2,St3};
+map_build_pairs_1([], St) ->
+    {[],[],St}.
 
-map_op_to_c_map_pair(map_field_assoc) -> #c_map_pair{op=#c_literal{val=assoc}};
-map_op_to_c_map_pair(map_field_exact) -> #c_map_pair{op=#c_literal{val=exact}}.
+map_op(map_field_assoc) -> #c_literal{val=assoc};
+map_op(map_field_exact) -> #c_literal{val=exact}.
 
 is_valid_map_src(#c_literal{val = M}) when is_map(M) -> true;
 is_valid_map_src(#c_var{})  -> true;
diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl
index 6504351c02..72e7a39333 100644
--- a/lib/compiler/src/v3_kernel.erl
+++ b/lib/compiler/src/v3_kernel.erl
@@ -521,62 +521,76 @@ is_valid_map_src(#k_var{}) -> true;
 is_valid_map_src(_) -> false.
 
 map_split_pairs(A, Var, Ces, Sub, St0) ->
-    %% two steps
-    %% 1. force variables
-    %% 2. remove multiples
-    Pairs0 = [{Op,K,V} || #c_map_pair{op=#c_literal{val=Op},key=K,val=V} <- Ces],
+    %% 1. Force variables.
+    %% 2. Group adjacent pairs with literal keys.
+    %% 3. Within each such group, remove multiple assignments to the same key.
+    %% 4. Partition each group according to operator ('=>' and ':=').
+    Pairs0 = [{Op,K,V} ||
+		 #c_map_pair{op=#c_literal{val=Op},key=K,val=V} <- Ces],
     {Pairs,Esp,St1} = foldr(fun
 	    ({Op,K0,V0}, {Ops,Espi,Sti0}) when Op =:= assoc; Op =:= exact ->
 		{K,Eps1,Sti1} = atomic(K0, Sub, Sti0),
 		{V,Eps2,Sti2} = atomic(V0, Sub, Sti1),
 		{[{Op,K,V}|Ops],Eps1 ++ Eps2 ++ Espi,Sti2}
 	end, {[],[],St0}, Pairs0),
-
-    case map_group_pairs(Pairs) of
-	{Assoc,[]} ->
-	    Kes = [#k_map_pair{key=K,val=V}||{_,{assoc,K,V}} <- Assoc],
-	    {#k_map{anno=A,op=assoc,var=Var,es=Kes},Esp,St1};
-	{[],Exact} ->
-	    Kes = [#k_map_pair{key=K,val=V}||{_,{exact,K,V}} <- Exact],
-	    {#k_map{anno=A,op=exact,var=Var,es=Kes},Esp,St1};
-	{Assoc,Exact} ->
-	    Kes1 = [#k_map_pair{key=K,val=V}||{_,{assoc,K,V}} <- Assoc],
-	    {Mvar,Em,St2} = force_atomic(#k_map{anno=A,op=assoc,var=Var,es=Kes1},St1),
-	    Kes2 = [#k_map_pair{key=K,val=V}||{_,{exact,K,V}} <- Exact],
-	    {#k_map{anno=A,op=exact,var=Mvar,es=Kes2},Esp ++ Em,St2}
-
+    map_split_pairs_1(A, Var, Pairs, Esp, St1).
+
+map_split_pairs_1(A, Map0, [{Op,Key,Val}|Pairs1]=Pairs0, Esp0, St0) ->
+    {Map1,Em,St1} = force_atomic(Map0, St0),
+    case Key of
+	#k_var{} ->
+	    %% Don't combine variable keys with other keys.
+	    Kes = [#k_map_pair{key=Key,val=Val}],
+	    Map = #k_map{anno=A,op=Op,var=Map1,es=Kes},
+	    map_split_pairs_1(A, Map, Pairs1, Esp0 ++ Em, St1);
+	_ ->
+	    %% Literal key. Split off all literal keys.
+	    {L,Pairs} = splitwith(fun({_,#k_var{},_}) -> false;
+				     ({_,_,_}) -> true
+				  end, Pairs0),
+	    {Map,Esp,St2} = map_group_pairs(A, Map1, L, Esp0 ++ Em, St1),
+	    map_split_pairs_1(A, Map, Pairs, Esp, St2)
+    end;
+map_split_pairs_1(_, Map, [], Esp, St0) ->
+    {Map,Esp,St0}.
+
+map_group_pairs(A, Var, Pairs0, Esp, St0) ->
+    Pairs = map_remove_dup_keys(Pairs0),
+    Assoc = [#k_map_pair{key=K,val=V} || {_,{assoc,K,V}} <- Pairs],
+    Exact = [#k_map_pair{key=K,val=V} || {_,{exact,K,V}} <- Pairs],
+    case {Assoc,Exact} of
+	{[_|_],[]} ->
+	    {#k_map{anno=A,op=assoc,var=Var,es=Assoc},Esp,St0};
+	{[],[_|_]} ->
+	    {#k_map{anno=A,op=exact,var=Var,es=Exact},Esp,St0};
+	{[_|_],[_|_]} ->
+	    Map = #k_map{anno=A,op=assoc,var=Var,es=Assoc},
+	    {Mvar,Em,St1} = force_atomic(Map, St0),
+	    {#k_map{anno=A,op=exact,var=Mvar,es=Exact},Esp ++ Em,St1}
     end.
 
-%% Group map by Assoc operations and Exact operations
-
-map_group_pairs(Es) ->
-    Groups = dict:to_list(map_group_pairs(Es,dict:new())),
-    partition(fun({_,{Op,_,_}}) -> Op =:= assoc end, Groups).
-
-map_group_pairs([{assoc,K,V}|Es0],Used0) ->
-    Used1 = case map_key_is_used(K,Used0) of
-	{ok, {assoc,_,_}} -> map_key_set_used(K,{assoc,K,V},Used0);
-	{ok, {exact,_,_}} -> map_key_set_used(K,{exact,K,V},Used0);
-	_                 -> map_key_set_used(K,{assoc,K,V},Used0)
-    end,
-    map_group_pairs(Es0,Used1);
-map_group_pairs([{exact,K,V}|Es0],Used0) ->
-    Used1 = case map_key_is_used(K,Used0) of
-	{ok, {assoc,_,_}} -> map_key_set_used(K,{assoc,K,V},Used0);
-	{ok, {exact,_,_}} -> map_key_set_used(K,{exact,K,V},Used0);
-	_                 -> map_key_set_used(K,{exact,K,V},Used0)
-    end,
-    map_group_pairs(Es0,Used1);
-map_group_pairs([],Used) ->
-    Used.
+map_remove_dup_keys(Es) ->
+    dict:to_list(map_remove_dup_keys(Es, dict:new())).
 
-map_key_set_used(K,How,Used) ->
-    dict:store(map_key_clean(K),How,Used).
-
-map_key_is_used(K,Used) ->
-    dict:find(map_key_clean(K),Used).
+map_remove_dup_keys([{assoc,K0,V}|Es0],Used0) ->
+    K = map_key_clean(K0),
+    Op = case dict:find(K, Used0) of
+	     {ok,{exact,_,_}} -> exact;
+	     _                -> assoc
+	 end,
+    Used1 = dict:store(K, {Op,K0,V}, Used0),
+    map_remove_dup_keys(Es0, Used1);
+map_remove_dup_keys([{exact,K0,V}|Es0],Used0) ->
+    K = map_key_clean(K0),
+    Op = case dict:find(K, Used0) of
+	     {ok,{assoc,_,_}} -> assoc;
+	     _                -> exact
+	 end,
+    Used1 = dict:store(K, {Op,K0,V}, Used0),
+    map_remove_dup_keys(Es0, Used1);
+map_remove_dup_keys([], Used) -> Used.
 
-%% Be explicit instead of using set_kanno(K,[])
+%% Be explicit instead of using set_kanno(K, []).
 map_key_clean(#k_var{name=V})    -> {var,V};
 map_key_clean(#k_literal{val=V}) -> {lit,V};
 map_key_clean(#k_int{val=V})     -> {lit,V};