aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2015-01-27 09:16:07 +0100
committerBjörn Gustavsson <[email protected]>2015-01-29 09:37:17 +0100
commit25603134a658a64d5b024fe1668d9db6f331b2e2 (patch)
tree351a0310742d6730b87c1285de20ad1b46664621
parent440c54f6a6b78015e8c8e0c7d16ad3cbb3d22147 (diff)
downloadotp-25603134a658a64d5b024fe1668d9db6f331b2e2.tar.gz
otp-25603134a658a64d5b024fe1668d9db6f331b2e2.tar.bz2
otp-25603134a658a64d5b024fe1668d9db6f331b2e2.zip
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.
-rw-r--r--lib/compiler/src/v3_core.erl75
-rw-r--r--lib/compiler/src/v3_kernel.erl106
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};