diff options
| -rw-r--r-- | erts/emulator/beam/beam_load.c | 31 | ||||
| -rw-r--r-- | erts/emulator/beam/instrs.tab | 54 | ||||
| -rw-r--r-- | erts/emulator/beam/ops.tab | 136 | ||||
| -rw-r--r-- | erts/emulator/internal_doc/CountingInstructions.md | 53 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa_opt.erl | 92 |
5 files changed, 288 insertions, 78 deletions
diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c index e9e294cd59..f4eeb54a1b 100644 --- a/erts/emulator/beam/beam_load.c +++ b/erts/emulator/beam/beam_load.c @@ -2970,6 +2970,8 @@ load_code(LoaderState* stp) #define succ(St, X, Y) ((X).type == (Y).type && (X).val + 1 == (Y).val) #define succ2(St, X, Y) ((X).type == (Y).type && (X).val + 2 == (Y).val) #define succ3(St, X, Y) ((X).type == (Y).type && (X).val + 3 == (Y).val) +#define succ4(St, X, Y) ((X).type == (Y).type && (X).val + 4 == (Y).val) + #ifdef NO_FPE_SIGNALS #define no_fpe_signals(St) 1 @@ -2986,6 +2988,35 @@ compiled_with_otp_20_or_higher(LoaderState* stp) } /* + * Predicate that tests whether the following two moves are independent: + * + * move Src1 Dst1 + * move Src2 Dst2 + * + */ +static int +independent_moves(LoaderState* stp, GenOpArg Src1, GenOpArg Dst1, + GenOpArg Src2, GenOpArg Dst2) +{ + return (Src1.type != Dst2.type || Src1.val != Dst2.val) && + (Src2.type != Dst1.type || Src2.val != Dst1.val) && + (Dst1.type != Dst2.type ||Dst1.val != Dst2.val); +} + +/* + * Predicate that tests that two registers are distinct. + * + * move Src1 Dst1 + * move Src2 Dst2 + * + */ +static int +distinct(LoaderState* stp, GenOpArg Reg1, GenOpArg Reg2) +{ + return Reg1.type != Reg2.type || Reg1.val != Reg2.val; +} + +/* * Predicate that tests whether a jump table can be used. */ diff --git a/erts/emulator/beam/instrs.tab b/erts/emulator/beam/instrs.tab index e55c4a112d..fc88cab22f 100644 --- a/erts/emulator/beam/instrs.tab +++ b/erts/emulator/beam/instrs.tab @@ -359,7 +359,7 @@ i_get_tuple_element2(Src, Element, Dst) { dst[1] = E2; } -i_get_tuple_element2y(Src, Element, D1, D2) { +i_get_tuple_element2_dst(Src, Element, D1, D2) { Eterm* src; Eterm E1, E2; src = ADD_BYTE_OFFSET(tuple_val($Src), $Element); @@ -436,6 +436,30 @@ init(Y) { make_blank($Y); } +init_seq3(Y1) { + Eterm* dst = &$Y1; + make_blank(dst[0]); + make_blank(dst[1]); + make_blank(dst[2]); +} + +init_seq4(Y1) { + Eterm* dst = &$Y1; + make_blank(dst[0]); + make_blank(dst[1]); + make_blank(dst[2]); + make_blank(dst[3]); +} + +init_seq5(Y1) { + Eterm* dst = &$Y1; + make_blank(dst[0]); + make_blank(dst[1]); + make_blank(dst[2]); + make_blank(dst[3]); + make_blank(dst[4]); +} + init2(Y1, Y2) { make_blank($Y1); make_blank($Y2); @@ -642,12 +666,6 @@ is_nonempty_list(Fail, Src) { } } -is_nonempty_list_test_heap(Fail, Need, Live) { - //| -no_prefetch - $is_nonempty_list($Fail, x(0)); - $test_heap($Need, $Live); -} - is_nonempty_list_allocate(Fail, Src, Need, Live) { //| -no_prefetch $is_nonempty_list($Fail, $Src); @@ -660,6 +678,18 @@ is_nonempty_list_get_list(Fail, Src, Hd, Tl) { $get_list($Src, $Hd, $Tl); } +is_nonempty_list_get_hd(Fail, Src, Hd) { + //| -no_prefetch + $is_nonempty_list($Fail, $Src); + $get_hd($Src, $Hd); +} + +is_nonempty_list_get_tl(Fail, Src, Tl) { + //| -no_prefetch + $is_nonempty_list($Fail, $Src); + $get_tl($Src, $Tl); +} + jump(Fail) { $JUMP($Fail); } @@ -797,6 +827,16 @@ test_arity(Fail, Pointer, Arity) { } } +test_arity_get_tuple_element(Fail, Pointer, Arity, Pos, Dst) { + Eterm* ptr = tuple_val($Pointer); + Eterm* src; + if (*ptr != $Arity) { + $FAIL($Fail); + } + src = ADD_BYTE_OFFSET(ptr, $Pos); + $Dst = *src; +} + i_is_eq_exact_immed(Fail, X, Y) { if ($X != $Y) { $FAIL($Fail); diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab index 8e730e42d6..3cfc685336 100644 --- a/erts/emulator/beam/ops.tab +++ b/erts/emulator/beam/ops.tab @@ -118,11 +118,21 @@ test_heap I t? allocate_heap S u==0 R => allocate S R allocate_heap_zero S u==0 R => allocate_zero S R -init2 y y -init3 y y y +init Y1 | init Y2 | init Y3 | succ(Y1,Y2) | succ(Y2,Y3) => init_seq3 Y1 +init_seq3 Y1 | init Y4 | succ3(Y1,Y4) => init_seq4 Y1 +init_seq4 Y1 | init Y5 | succ4(Y1,Y5) => init_seq5 Y1 + +init_seq3 y +init_seq4 y +init_seq5 y + init Y1 | init Y2 | init Y3 => init3 Y1 Y2 Y3 init Y1 | init Y2 => init2 Y1 Y2 +init2 y y +init3 y y y + + # Selecting values select_val S=aiq Fail=f Size=u Rest=* => const_select_val(S, Fail, Size, Rest) @@ -212,7 +222,8 @@ i_get_tuple_element xy P y %hot i_get_tuple_element2 x P x -i_get_tuple_element2y x P y y +i_get_tuple_element2_dst x P x x +i_get_tuple_element2_dst x P y y i_get_tuple_element3 x P x @@ -288,7 +299,7 @@ move_window4 x x x x y move_window5 x x x x x y # Swap registers. -move R1=x Tmp=x | move R2=xy R1 | move Tmp R2 => swap_temp R1 R2 Tmp +move R1=x Tmp=x | move R2=x R1 | move Tmp R2 => swap_temp R1 R2 Tmp swap_temp R1 R2 Tmp | line Loc | apply Live | is_killed_apply(Tmp, Live) => \ swap R1 R2 | line Loc | apply Live @@ -307,73 +318,84 @@ swap_temp R1 R2 Tmp | line Loc | call_ext_only Live Addr | \ swap_temp R1 R2 Tmp | line Loc | call_ext_last Live Addr D | \ is_killed(Tmp, Live) => swap R1 R2 | line Loc | call_ext_last Live Addr D -swap_temp x xy x +swap_temp x x x + +swap x x -swap x xy +# move_dup move Src=x D1=x | move Src=x D2=x => move_dup Src D1 D2 -move Src=x SD=x | move SD=x D=x => move_dup Src SD D -move Src=x D1=x | move Src=x D2=y => move_dup Src D1 D2 -move Src=y SD=x | move SD=x D=y => move_dup Src SD D -move Src=x SD=x | move SD=x D=y => move_dup Src SD D -move Src=y SD=x | move SD=x D=x => move_dup Src SD D - -move SD=x D=x | move Src=xy SD=x => move_shift Src SD D -move SD=y D=x | move Src=x SD=y => move_shift Src SD D -move SD=x D=y | move Src=x SD=x => move_shift Src SD D - -# The transformations above guarantee that the source for -# the second move is not the same as the destination for -# the first move. That means that we can do the moves in -# parallel (fetch both values, then store them) which could -# be faster. +move Src=x SD=x | move SD=x D=x => move_dup Src SD D -move X1=x Y1=y | move X2=x Y2=y => move2_par X1 Y1 X2 Y2 -move Y1=y X1=x | move Y2=y X2=x => move2_par Y1 X1 Y2 X2 +move_dup x x x -move X1=x X2=x | move X3=x X4=x => move2_par X1 X2 X3 X4 +# move_shift -move X1=x X2=x | move X3=x Y1=y => move2_par X1 X2 X3 Y1 +move SD=x D=x | move Src=xy SD=x | distinct(D, Src) => move_shift Src SD D +move SD=y D=x | move Src=x SD=y | distinct(D, Src) => move_shift Src SD D +move SD=x D=y | move Src=x SD=x | distinct(D, Src) => move_shift Src SD D -move S1=x S2=x | move X1=x Y1=y => move2_par S1 S2 X1 Y1 +move_shift x x x +move_shift y x x +move_shift x y x +move_shift x x y -move S1=y S2=x | move X1=x Y1=y => move2_par S1 S2 X1 Y1 +# move2_par x x x x -move Y1=y X1=x | move S1=x D1=x => move2_par Y1 X1 S1 D1 -move S1=x D1=x | move Y1=y X1=x => move2_par S1 D1 Y1 X1 +move X1=x X2=x | move X3=x X4=x | independent_moves(X1, X2, X3, X4) => \ + move2_par X1 X2 X3 X4 +move2_par x x x x -move2_par X1=x Y1=y X2=x Y2=y | move X3=x Y3=y => move3 X1 Y1 X2 Y2 X3 Y3 -move2_par Y1=y X1=x Y2=y X2=x | move Y3=y X3=x => move3 Y1 X1 Y2 X2 Y3 X3 -move2_par X1=x X2=x X3=x X4=x | move X5=x X6=x => move3 X1 X2 X3 X4 X5 X6 +# move2_par x y x y -move C=aiq X=x==1 => move_x1 C -move C=aiq X=x==2 => move_x2 C +move X1=x Y1=y | move X2=x Y2=y => move2_par X1 Y1 X2 Y2 +move2_par x y x y -move_x1 c -move_x2 c +# move2_par x x x y -move_shift x x x -move_shift y x x -move_shift x y x -move_shift x x y +move X1=x X2=x | move X3=x Y1=y | independent_moves(X1, X2, X3, Y1) => \ + move2_par X1 X2 X3 Y1 +move X3=x Y1=y | move X1=x X2=x | independent_moves(X3, Y1, X1, X2) => \ + move2_par X1 X2 X3 Y1 +move2_par x x x y -move_dup xy x xy +# move2_par y x y x -move2_par x y x y +move Y1=y X1=x | move Y2=y X2=x => move2_par Y1 X1 Y2 X2 move2_par y x y x -move2_par x x x x -move2_par x x x y +# move2_par y x x y +move S1=y S2=x | move X1=x Y1=y | independent_moves(S1, S2, X1, Y1) => \ + move2_par S1 S2 X1 Y1 +move X1=x Y1=y | move S1=y S2=x | independent_moves(S1, S2, X1, Y1) => \ + move2_par S1 S2 X1 Y1 move2_par y x x y -move2_par x x y x +# move2_par y x x x + +move Y1=y X1=x | move S1=x D1=x | independent_moves(Y1, X1, S1, D1) => \ + move2_par Y1 X1 S1 D1 +move S1=x D1=x | move Y1=y X1=x | independent_moves(Y1, X1, S1, D1) => \ + move2_par Y1 X1 S1 D1 move2_par y x x x -move3 x y x y x y +# move3 + +move2_par Y1=y X1=x Y2=y X2=x | move Y3=y X3=x => move3 Y1 X1 Y2 X2 Y3 X3 +move2_par X1=x X2=x X3=x X4=x | move X5=x X6=x => move3 X1 X2 X3 X4 X5 X6 + move3 y x y x y x move3 x x x x x x +# move_x1, move_x2 + +move C=aiq X=x==1 => move_x1 C +move C=aiq X=x==2 => move_x2 C + +move_x1 c +move_x2 c + # The compiler almost never generates a "move Literal y(Y)" instruction, # so let's cheat if we encounter one. move S=n D=y => init D @@ -611,9 +633,13 @@ is_tuple f? rxy test_arity Fail Literal=q Arity => move Literal x | test_arity Fail x Arity test_arity Fail=f c Arity => jump Fail +test_arity Fail Tuple=x Arity | get_tuple_element Tuple Pos Dst=x => \ + test_arity_get_tuple_element Fail Tuple Arity Pos Dst test_arity f? xy A +test_arity_get_tuple_element f? x A P x + get_tuple_element Reg=x P1 D1=x | get_tuple_element Reg=x P2 D2=x | \ get_tuple_element Reg=x P3 D3=x | \ succ(P1, P2) | succ(P2, P3) | \ @@ -622,8 +648,11 @@ get_tuple_element Reg=x P1 D1=x | get_tuple_element Reg=x P2 D2=x | \ get_tuple_element Reg=x P1 D1=x | get_tuple_element Reg=x P2 D2=x | \ succ(P1, P2) | succ(D1, D2) => i_get_tuple_element2 Reg P1 D1 +get_tuple_element Reg=x P1 D1=x | get_tuple_element Reg=x P2 D2=x | \ + succ(P1, P2) | distinct(D1, Reg) => i_get_tuple_element2_dst Reg P1 D1 D2 + get_tuple_element Reg=x P1 D1=y | get_tuple_element Reg=x P2 D2=y | \ - succ(P1, P2) => i_get_tuple_element2y Reg P1 D1 D2 + succ(P1, P2) => i_get_tuple_element2_dst Reg P1 D1 D2 get_tuple_element Reg P Dst => i_get_tuple_element Reg P Dst @@ -647,14 +676,21 @@ is_list f? y is_nonempty_list Fail=f S=x | allocate Need Rs => is_nonempty_list_allocate Fail S Need Rs -is_nonempty_list F=f x==0 | test_heap I1 I2 => is_nonempty_list_test_heap F I1 I2 - is_nonempty_list Fail=f S=x | get_list S D1=x D2=x => \ is_nonempty_list_get_list Fail S D1 D2 +is_nonempty_list Fail=f S=x | get_hd S Dst=x => \ + is_nonempty_list_get_hd Fail S Dst + +is_nonempty_list Fail=f S=x | get_tl S Dst=x => \ + is_nonempty_list_get_tl Fail S Dst + is_nonempty_list_allocate f? rx t t -is_nonempty_list_test_heap f? I t + is_nonempty_list_get_list f? rx x x +is_nonempty_list_get_hd f? x x +is_nonempty_list_get_tl f? x x + is_nonempty_list f? xy is_atom f? x diff --git a/erts/emulator/internal_doc/CountingInstructions.md b/erts/emulator/internal_doc/CountingInstructions.md new file mode 100644 index 0000000000..d4b1213d00 --- /dev/null +++ b/erts/emulator/internal_doc/CountingInstructions.md @@ -0,0 +1,53 @@ +Counting Instructions +===================== + +Here is an example that shows how to count how many times each +instruction is executed: + + $ (cd erts/emulator && make icount) + MAKE icount + make[1]: Entering directory `/home/uabbgus/otp/erts/emulator' + . + . + . + make[1]: Leaving directory `/home/uabbgus/otp/erts/emulator' + $ cat t.erl + -module(t). + -compile([export_all,nowarn_export_all]). + + count() -> + erts_debug:ic(fun benchmark/0). + + benchmark() -> + %% Run dialyzer. + Root = code:root_dir(), + Wc1 = filename:join(Root, "lib/{kernel,stdlib}/ebin/*.beam"), + Wc2 = filename:join(Root, "erts/preloaded/ebin/*.beam"), + Files = filelib:wildcard(Wc1) ++ filelib:wildcard(Wc2), + Opts = [{analysis_type,plt_build},{files,Files},{get_warnings,true}], + dialyzer:run(Opts). + $ $ERL_TOP/bin/cerl -icount + Erlang/OTP 22 [RELEASE CANDIDATE 1] [erts-10.2.4] [source-ac0d451] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:1] [hipe] [instruction-counting] + + Eshell V10.2.4 (abort with ^G) + 1> c(t). + {ok,t} + 2> t:count(). + 0 badarg_j + 0 badmatch_x + 0 bs_add_jsstx + 0 bs_context_to_binary_x + . + . + . + 536461394 move_call_last_yfQ + 552405176 allocate_tt + 619920327 i_is_eq_exact_immed_frc + 636419163 is_nonempty_list_allocate_frtt + 641859278 i_get_tuple_element_xPx + 678196718 move_return_c + 786289914 is_tagged_tuple_frAa + 865826424 i_call_f + Total: 20728870321 + [] + 3> diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl index 6e548dd529..bcf55f3fda 100644 --- a/lib/compiler/src/beam_ssa_opt.erl +++ b/lib/compiler/src/beam_ssa_opt.erl @@ -175,6 +175,7 @@ epilogue_passes(Opts) -> ?PASS(ssa_opt_blockify), ?PASS(ssa_opt_sink), ?PASS(ssa_opt_merge_blocks), + ?PASS(ssa_opt_get_tuple_element), ?PASS(ssa_opt_trim_unreachable)], passes_1(Ps, Opts). @@ -682,6 +683,14 @@ record_opt_is([#b_set{op={bif,is_tuple},dst=Bool,args=[Tuple]}=Set], no -> [Set] end; +record_opt_is([I|Is]=Is0, #b_br{bool=Bool}=Last, Blocks) -> + case is_tagged_tuple_1(Is0, Last, Blocks) of + {yes,_Fail,Tuple,Arity,Tag} -> + Args = [Tuple,Arity,Tag], + [I#b_set{op=is_tagged_tuple,dst=Bool,args=Args}]; + no -> + [I|record_opt_is(Is, Last, Blocks)] + end; record_opt_is([I|Is], Last, Blocks) -> [I|record_opt_is(Is, Last, Blocks)]; record_opt_is([], _Last, _Blocks) -> []. @@ -689,29 +698,30 @@ record_opt_is([], _Last, _Blocks) -> []. is_tagged_tuple(#b_var{}=Tuple, Bool, #b_br{bool=Bool,succ=Succ,fail=Fail}, Blocks) -> - SuccBlk = map_get(Succ, Blocks), - is_tagged_tuple_1(SuccBlk, Tuple, Fail, Blocks); + #b_blk{is=Is,last=Last} = map_get(Succ, Blocks), + case is_tagged_tuple_1(Is, Last, Blocks) of + {yes,Fail,Tuple,Arity,Tag} -> + {yes,Arity,Tag}; + _ -> + no + end; is_tagged_tuple(_, _, _, _) -> no. -is_tagged_tuple_1(#b_blk{is=Is,last=Last}, Tuple, Fail, Blocks) -> - case Is of - [#b_set{op={bif,tuple_size},dst=ArityVar, - args=[#b_var{}=Tuple]}, - #b_set{op={bif,'=:='}, - dst=Bool, - args=[ArityVar, #b_literal{val=ArityVal}=Arity]}] - when is_integer(ArityVal) -> - case Last of - #b_br{bool=Bool,succ=Succ,fail=Fail} -> - SuccBlk = map_get(Succ, Blocks), - case is_tagged_tuple_2(SuccBlk, Tuple, Fail) of - no -> - no; - {yes,Tag} -> - {yes,Arity,Tag} - end; - _ -> - no +is_tagged_tuple_1(Is, Last, Blocks) -> + case {Is,Last} of + {[#b_set{op={bif,tuple_size},dst=ArityVar, + args=[#b_var{}=Tuple]}, + #b_set{op={bif,'=:='}, + dst=Bool, + args=[ArityVar, #b_literal{val=ArityVal}=Arity]}], + #b_br{bool=Bool,succ=Succ,fail=Fail}} + when is_integer(ArityVal) -> + SuccBlk = map_get(Succ, Blocks), + case is_tagged_tuple_2(SuccBlk, Tuple, Fail) of + no -> + no; + {yes,Tag} -> + {yes,Fail,Tuple,Arity,Tag} end; _ -> no @@ -2174,6 +2184,46 @@ insert_def_is([#b_set{op=Op}=I|Is]=Is0, V, Def) -> insert_def_is([], _V, Def) -> [Def]. +%%% +%%% Order consecutive get_tuple_element instructions in ascending +%%% position order. This will give the loader more opportunities +%%% for combining get_tuple_element instructions. +%%% + +ssa_opt_get_tuple_element({#st{ssa=Blocks0}=St, FuncDb}) -> + Blocks = opt_get_tuple_element(maps:to_list(Blocks0), Blocks0), + {St#st{ssa=Blocks}, FuncDb}. + +opt_get_tuple_element([{L,#b_blk{is=Is0}=Blk0}|Bs], Blocks) -> + case opt_get_tuple_element_is(Is0, false, []) of + {yes,Is} -> + Blk = Blk0#b_blk{is=Is}, + opt_get_tuple_element(Bs, Blocks#{L:=Blk}); + no -> + opt_get_tuple_element(Bs, Blocks) + end; +opt_get_tuple_element([], Blocks) -> Blocks. + +opt_get_tuple_element_is([#b_set{op=get_tuple_element, + args=[#b_var{}=Src,_]}=I0|Is0], + _AnyChange, Acc) -> + {GetIs0,Is} = collect_get_tuple_element(Is0, Src, [I0]), + GetIs1 = sort([{Pos,I} || #b_set{args=[_,Pos]}=I <- GetIs0]), + GetIs = [I || {_,I} <- GetIs1], + opt_get_tuple_element_is(Is, true, reverse(GetIs, Acc)); +opt_get_tuple_element_is([I|Is], AnyChange, Acc) -> + opt_get_tuple_element_is(Is, AnyChange, [I|Acc]); +opt_get_tuple_element_is([], AnyChange, Acc) -> + case AnyChange of + true -> {yes,reverse(Acc)}; + false -> no + end. + +collect_get_tuple_element([#b_set{op=get_tuple_element, + args=[Src,_]}=I|Is], Src, Acc) -> + collect_get_tuple_element(Is, Src, [I|Acc]); +collect_get_tuple_element(Is, _Src, Acc) -> + {Acc,Is}. %%% %%% Common utilities. |