From c2702eb35db00ad67f922708eeea48616d908306 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 3 Oct 2013 14:06:57 +0200 Subject: compiler: Implement different instructions for => and := --- lib/compiler/src/beam_a.erl | 4 ++ lib/compiler/src/beam_block.erl | 6 +- lib/compiler/src/beam_clean.erl | 5 +- lib/compiler/src/beam_flatten.erl | 4 +- lib/compiler/src/beam_jump.erl | 2 +- lib/compiler/src/beam_split.erl | 7 ++- lib/compiler/src/beam_validator.erl | 23 +++++--- lib/compiler/src/beam_z.erl | 4 ++ lib/compiler/src/genop.tab | 9 +-- lib/compiler/src/v3_codegen.erl | 111 ++++++++++++++++++++++++++++++------ 10 files changed, 135 insertions(+), 40 deletions(-) (limited to 'lib') 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. %%% -- cgit v1.2.3