diff options
19 files changed, 541 insertions, 274 deletions
diff --git a/bootstrap/bin/no_dot_erlang.boot b/bootstrap/bin/no_dot_erlang.boot Binary files differindex 496654fcea..b48d22fe41 100644 --- a/bootstrap/bin/no_dot_erlang.boot +++ b/bootstrap/bin/no_dot_erlang.boot diff --git a/bootstrap/bin/start.boot b/bootstrap/bin/start.boot Binary files differindex 496654fcea..b48d22fe41 100644 --- a/bootstrap/bin/start.boot +++ b/bootstrap/bin/start.boot diff --git a/bootstrap/bin/start_clean.boot b/bootstrap/bin/start_clean.boot Binary files differindex 496654fcea..b48d22fe41 100644 --- a/bootstrap/bin/start_clean.boot +++ b/bootstrap/bin/start_clean.boot diff --git a/bootstrap/lib/compiler/ebin/beam_jump.beam b/bootstrap/lib/compiler/ebin/beam_jump.beam Binary files differindex e23ff4e906..a650592edf 100644 --- a/bootstrap/lib/compiler/ebin/beam_jump.beam +++ b/bootstrap/lib/compiler/ebin/beam_jump.beam diff --git a/bootstrap/lib/compiler/ebin/beam_ssa_type.beam b/bootstrap/lib/compiler/ebin/beam_ssa_type.beam Binary files differindex de9929bc92..61f3eff581 100644 --- a/bootstrap/lib/compiler/ebin/beam_ssa_type.beam +++ b/bootstrap/lib/compiler/ebin/beam_ssa_type.beam diff --git a/bootstrap/lib/compiler/ebin/beam_validator.beam b/bootstrap/lib/compiler/ebin/beam_validator.beam Binary files differindex 74590b52d7..c40e3e207c 100644 --- a/bootstrap/lib/compiler/ebin/beam_validator.beam +++ b/bootstrap/lib/compiler/ebin/beam_validator.beam diff --git a/bootstrap/lib/compiler/ebin/cerl_sets.beam b/bootstrap/lib/compiler/ebin/cerl_sets.beam Binary files differindex 4ab7584977..bda70130a6 100644 --- a/bootstrap/lib/compiler/ebin/cerl_sets.beam +++ b/bootstrap/lib/compiler/ebin/cerl_sets.beam diff --git a/bootstrap/lib/stdlib/ebin/gen_statem.beam b/bootstrap/lib/stdlib/ebin/gen_statem.beam Binary files differindex f5185696eb..925f1362fa 100644 --- a/bootstrap/lib/stdlib/ebin/gen_statem.beam +++ b/bootstrap/lib/stdlib/ebin/gen_statem.beam diff --git a/bootstrap/lib/stdlib/ebin/otp_internal.beam b/bootstrap/lib/stdlib/ebin/otp_internal.beam Binary files differindex 4dbdabbb7d..a975a43c00 100644 --- a/bootstrap/lib/stdlib/ebin/otp_internal.beam +++ b/bootstrap/lib/stdlib/ebin/otp_internal.beam diff --git a/bootstrap/lib/stdlib/ebin/slave.beam b/bootstrap/lib/stdlib/ebin/slave.beam Binary files differindex ad8763725e..c917fec99f 100644 --- a/bootstrap/lib/stdlib/ebin/slave.beam +++ b/bootstrap/lib/stdlib/ebin/slave.beam 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/erts/emulator/sys/common/erl_mmap.h b/erts/emulator/sys/common/erl_mmap.h index e1ff0fe80a..3085bf7e19 100644 --- a/erts/emulator/sys/common/erl_mmap.h +++ b/erts/emulator/sys/common/erl_mmap.h @@ -203,7 +203,7 @@ ERTS_GLB_INLINE void erts_mem_discard(void *p, UWord size); data[i] = pattern[i % sizeof(pattern)]; } } -#elif defined(HAVE_SYS_MMAN_H) +#elif defined(HAVE_SYS_MMAN_H) && !(defined(__sun) || defined(__sun__)) #include <sys/mman.h> ERTS_GLB_INLINE void erts_mem_discard(void *ptr, UWord size) { diff --git a/erts/lib_src/common/erl_printf.c b/erts/lib_src/common/erl_printf.c index 259ba8c81d..86f5da1c40 100644 --- a/erts/lib_src/common/erl_printf.c +++ b/erts/lib_src/common/erl_printf.c @@ -27,6 +27,11 @@ #include "config.h" #endif +#if defined(__sun) || defined(__sun__) + /* For flockfile(3c), putc_unlocked(3c), etc */ + #define __EXTENSIONS__ +#endif + #include <string.h> #include "erl_errno.h" #ifdef __WIN32__ diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl index 2cca9ebadf..bb43a550ae 100644 --- a/lib/compiler/src/beam_ssa_dead.erl +++ b/lib/compiler/src/beam_ssa_dead.erl @@ -27,7 +27,8 @@ -export([opt/1]). -include("beam_ssa.hrl"). --import(lists, [append/1,last/1,member/2,takewhile/2,reverse/1]). +-import(lists, [append/1,keymember/3,last/1,member/2, + takewhile/2,reverse/1]). -type used_vars() :: #{beam_ssa:label():=ordsets:ordset(beam_ssa:var_name())}. @@ -58,7 +59,7 @@ opt(Linear) -> Blocks0 = maps:from_list(Linear), St0 = #st{bs=Blocks0,us=Used,skippable=Skippable}, St = shortcut_opt(St0), - #st{bs=Blocks} = combine_eqs(St), + #st{bs=Blocks} = combine_eqs(St#st{us=#{}}), beam_ssa:linearize(Blocks). %%% @@ -87,13 +88,22 @@ shortcut_opt(#st{bs=Blocks}=St) -> %% opportunities for optimizations compared to post order. (Based on %% running scripts/diffable with both PO and RPO and looking at %% the diff.) + %% + %% Unfortunately, processing the blocks in reverse post order + %% potentially makes the time complexity quadratic or even cubic if + %% the ordset of unset variables grows large, instead of + %% linear for post order processing. We try to still get reasonable + %% compilation times by optimizations that will keep the constant + %% factor as low as possible, and we try to avoid the cubic time + %% complexity by trying to keep the set of unset variables as small + %% as possible. + Ls = beam_ssa:rpo(Blocks), - shortcut_opt(Ls, #{from=>0}, St). + shortcut_opt(Ls, #{}, St). -shortcut_opt([L|Ls], Bs0, #st{bs=Blocks0}=St) -> +shortcut_opt([L|Ls], Bs, #st{bs=Blocks0}=St) -> #b_blk{is=Is,last=Last0} = Blk0 = get_block(L, St), - Bs = Bs0#{from:=L}, - case shortcut_terminator(Last0, Is, Bs, St) of + case shortcut_terminator(Last0, Is, L, Bs, St) of Last0 -> %% No change. No need to update the block. shortcut_opt(Ls, Bs, St); @@ -107,17 +117,17 @@ shortcut_opt([L|Ls], Bs0, #st{bs=Blocks0}=St) -> shortcut_opt([], _, St) -> St. shortcut_terminator(#b_br{bool=#b_literal{val=true},succ=Succ0}, - _Is, Bs, St0) -> + _Is, From, Bs, St0) -> St = St0#st{rel_op=none}, - shortcut(Succ0, Bs, St); + shortcut(Succ0, From, Bs, St); shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br, - Is, Bs, St0) -> + Is, From, Bs, St0) -> St = St0#st{target=one_way}, RelOp = get_rel_op(Bool, Is), SuccBs = bind_var(Bool, #b_literal{val=true}, Bs), - BrSucc = shortcut(Succ0, SuccBs, St#st{rel_op=RelOp}), + BrSucc = shortcut(Succ0, From, SuccBs, St#st{rel_op=RelOp}), FailBs = bind_var(Bool, #b_literal{val=false}, Bs), - BrFail = shortcut(Fail0, FailBs, St#st{rel_op=invert_op(RelOp)}), + BrFail = shortcut(Fail0, From, FailBs, St#st{rel_op=invert_op(RelOp)}), case {BrSucc,BrFail} of {#b_br{bool=#b_literal{val=true},succ=Succ}, #b_br{bool=#b_literal{val=true},succ=Fail}} @@ -128,25 +138,25 @@ shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br, %% No change. Br end; -shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, Bs, St) -> - List = shortcut_switch(List0, Bool, Bs, St), +shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, From, Bs, St) -> + List = shortcut_switch(List0, Bool, From, Bs, St), beam_ssa:normalize(Sw#b_switch{list=List}); -shortcut_terminator(Last, _Is, _Bs, _St) -> +shortcut_terminator(Last, _Is, _Bs, _From, _St) -> Last. -shortcut_switch([{Lit,L0}|T], Bool, Bs, St0) -> +shortcut_switch([{Lit,L0}|T], Bool, From, Bs, St0) -> RelOp = {'=:=',Bool,Lit}, St = St0#st{rel_op=RelOp}, #b_br{bool=#b_literal{val=true},succ=L} = - shortcut(L0, bind_var(Bool, Lit, Bs), St#st{target=one_way}), - [{Lit,L}|shortcut_switch(T, Bool, Bs, St0)]; -shortcut_switch([], _, _, _) -> []. + shortcut(L0, From, bind_var(Bool, Lit, Bs), St#st{target=one_way}), + [{Lit,L}|shortcut_switch(T, Bool, From, Bs, St0)]; +shortcut_switch([], _, _, _, _) -> []. -shortcut(L, Bs, St) -> - shortcut_1(L, Bs, ordsets:new(), St). +shortcut(L, From, Bs, St) -> + shortcut_1(L, From, Bs, ordsets:new(), St). -shortcut_1(L, Bs0, UnsetVars0, St) -> - case shortcut_2(L, Bs0, UnsetVars0, St) of +shortcut_1(L, From, Bs0, UnsetVars0, St) -> + case shortcut_2(L, From, Bs0, UnsetVars0, St) of none -> %% No more shortcuts found. Package up the previous %% label in an unconditional branch. @@ -156,13 +166,13 @@ shortcut_1(L, Bs0, UnsetVars0, St) -> Br; {#b_br{bool=#b_literal{val=true},succ=Succ},Bs,UnsetVars} -> %% This is a safe `br`, but try to find a better one. - shortcut_1(Succ, Bs#{from:=L}, UnsetVars, St) + shortcut_1(Succ, L, Bs, UnsetVars, St) end. %% Try to shortcut this block, branching to a successor. -shortcut_2(L, Bs0, UnsetVars0, St) -> +shortcut_2(L, From, Bs0, UnsetVars0, St) -> #b_blk{is=Is,last=Last} = get_block(L, St), - case eval_is(Is, Bs0, St) of + case eval_is(Is, From, Bs0, St) of none -> %% It is not safe to avoid this block because it %% has instructions with potential side effects. @@ -181,139 +191,147 @@ shortcut_2(L, Bs0, UnsetVars0, St) -> %% We have a potentially suitable br. %% Now update the set of variables that will never %% be set if this block will be skipped. - SetInThisBlock = [V || #b_set{dst=V} <- Is], - UnsetVars = update_unset_vars(L, Br, SetInThisBlock, - UnsetVars0, St), - - %% Continue checking whether this br is suitable. - shortcut_3(Br, Bs#{from:=L}, UnsetVars, St) + case update_unset_vars(L, Is, Br, UnsetVars0, St) of + unsafe -> + %% It is unsafe to use this br, + %% because it refers to a variable defined + %% in this block. + shortcut_unsafe_br(Br, L, Bs, UnsetVars0, St); + UnsetVars -> + %% Continue checking whether this br is + %% suitable. + shortcut_test_br(Br, L, Bs, UnsetVars, St) + end end end. -shortcut_3(Br, Bs, UnsetVars, #st{target=Target}=St) -> +shortcut_test_br(Br, From, Bs, UnsetVars, St) -> case is_br_safe(UnsetVars, Br, St) of false -> - %% Branching using this `br` is unsafe, either because it - %% is an unconditional branch to a phi node, or because - %% one or more of the variables that are not set will be - %% used. Try to follow branches of this `br`, to find a - %% safe `br`. - case Br of - #b_br{bool=#b_literal{val=true},succ=L} -> - case Target of - L -> - %% We have reached the forced target, and it - %% is unsafe. Give up. - none; - _ -> - %% Try following this branch to see whether it - %% leads to a safe `br`. - shortcut_2(L, Bs, UnsetVars, St) - end; - #b_br{bool=#b_var{},succ=Succ,fail=Fail} -> - case {Succ,Fail} of - {L,Target} -> - %% The failure label is the forced target. - %% Try following the success label to see - %% whether it also ultimately ends up at the - %% forced target. - shortcut_2(L, Bs, UnsetVars, St); - {Target,L} -> - %% The success label is the forced target. - %% Try following the failure label to see - %% whether it also ultimately ends up at the - %% forced target. - shortcut_2(L, Bs, UnsetVars, St); - {_,_} -> - case Target of - any -> - %% This two-way branch is unsafe. Try reducing - %% it to a one-way branch. - shortcut_two_way(Br, Bs, UnsetVars, St); - one_way -> - %% This two-way branch is unsafe. Try reducing - %% it to a one-way branch. - shortcut_two_way(Br, Bs, UnsetVars, St); - _ when is_integer(Target) -> - %% This two-way branch is unsafe, and - %% there already is a forced target. - %% Give up. - none - end - end - end; + shortcut_unsafe_br(Br, From, Bs, UnsetVars, St); true -> - %% This `br` instruction is safe. It does not - %% branch to a phi node, and all variables that - %% will be used are guaranteed to be defined. - case Br of - #b_br{bool=#b_literal{val=true},succ=L} -> - %% This is a one-way branch. + shortcut_safe_br(Br, From, Bs, UnsetVars, St) + end. + +shortcut_unsafe_br(Br, From, Bs, UnsetVars, #st{target=Target}=St) -> + %% Branching using this `br` is unsafe, either because it + %% is an unconditional branch to a phi node, or because + %% one or more of the variables that are not set will be + %% used. Try to follow branches of this `br`, to find a + %% safe `br`. + case Br of + #b_br{bool=#b_literal{val=true},succ=L} -> + case Target of + L -> + %% We have reached the forced target, and it + %% is unsafe. Give up. + none; + _ -> + %% Try following this branch to see whether it + %% leads to a safe `br`. + shortcut_2(L, From, Bs, UnsetVars, St) + end; + #b_br{bool=#b_var{},succ=Succ,fail=Fail} -> + case {Succ,Fail} of + {L,Target} -> + %% The failure label is the forced target. + %% Try following the success label to see + %% whether it also ultimately ends up at the + %% forced target. + shortcut_2(L, From, Bs, UnsetVars, St); + {Target,L} -> + %% The success label is the forced target. + %% Try following the failure label to see + %% whether it also ultimately ends up at the + %% forced target. + shortcut_2(L, From, Bs, UnsetVars, St); + {_,_} -> case Target of any -> - %% No forced target. Success! - {Br,Bs,UnsetVars}; + %% This two-way branch is unsafe. Try + %% reducing it to a one-way branch. + shortcut_two_way(Br, From, Bs, UnsetVars, St); one_way -> - %% The target must be a one-way branch, which this - %% `br` is. Success! - {Br,Bs,UnsetVars}; - L when is_integer(Target) -> - %% The forced target is L. Success! - {Br,Bs,UnsetVars}; + %% This two-way branch is unsafe. Try + %% reducing it to a one-way branch. + shortcut_two_way(Br, From, Bs, UnsetVars, St); _ when is_integer(Target) -> - %% Wrong forced target. Try following this branch - %% to see if it ultimately ends up at the forced - %% target. - shortcut_2(L, Bs, UnsetVars, St) - end; - #b_br{bool=#b_var{}} -> - %% This is a two-way branch. - if - Target =:= any; Target =:= one_way -> - %% No specific forced target. Try to reduce the - %% two-way branch to an one-way branch. - case shortcut_two_way(Br, Bs, UnsetVars, St) of - none when Target =:= any -> - %% This `br` can't be reduced to a one-way - %% branch. Return the `br` as-is. - {Br,Bs,UnsetVars}; - none when Target =:= one_way -> - %% This `br` can't be reduced to a one-way - %% branch. The caller wants a one-way branch. - %% Give up. - none; - {_,_,_}=Res -> - %% This `br` was successfully reduced to a - %% one-way branch. - Res - end; - is_integer(Target) -> - %% There is a forced target, which can't - %% be reached because this `br` is a two-way - %% branch. Give up. + %% This two-way branch is unsafe, and + %% there already is a forced target. + %% Give up. none end end end. -update_unset_vars(L, Br, SetInThisBlock, UnsetVars, #st{skippable=Skippable}) -> +shortcut_safe_br(Br, From, Bs, UnsetVars, #st{target=Target}=St) -> + %% This `br` instruction is safe. It does not branch to a phi + %% node, and all variables that will be used are guaranteed to be + %% defined. + case Br of + #b_br{bool=#b_literal{val=true},succ=L} -> + %% This is a one-way branch. + case Target of + any -> + %% No forced target. Success! + {Br,Bs,UnsetVars}; + one_way -> + %% The target must be a one-way branch, which this + %% `br` is. Success! + {Br,Bs,UnsetVars}; + L when is_integer(Target) -> + %% The forced target is L. Success! + {Br,Bs,UnsetVars}; + _ when is_integer(Target) -> + %% Wrong forced target. Try following this branch + %% to see if it ultimately ends up at the forced + %% target. + shortcut_2(L, From, Bs, UnsetVars, St) + end; + #b_br{bool=#b_var{}} -> + %% This is a two-way branch. + if + Target =:= any; Target =:= one_way -> + %% No specific forced target. Try to reduce the + %% two-way branch to an one-way branch. + case shortcut_two_way(Br, From, Bs, UnsetVars, St) of + none when Target =:= any -> + %% This `br` can't be reduced to a one-way + %% branch. Return the `br` as-is. + {Br,Bs,UnsetVars}; + none when Target =:= one_way -> + %% This `br` can't be reduced to a one-way + %% branch. The caller wants a one-way + %% branch. Give up. + none; + {_,_,_}=Res -> + %% This `br` was successfully reduced to a + %% one-way branch. + Res + end; + is_integer(Target) -> + %% There is a forced target, which can't + %% be reached because this `br` is a two-way + %% branch. Give up. + none + end + end. + +update_unset_vars(L, Is, Br, UnsetVars, #st{skippable=Skippable}) -> case is_map_key(L, Skippable) of true -> %% None of the variables used in this block are used in - %% the successors. We can speed up compilation by avoiding - %% adding variables to the UnsetVars if the presence of - %% those variable would not change the outcome of the - %% tests in is_br_safe/2. + %% the successors. Thus, there is no need to add the + %% variables to the set of unset variables. case Br of - #b_br{bool=Bool} -> - case member(Bool, SetInThisBlock) of + #b_br{bool=#b_var{}=Bool} -> + case keymember(Bool, #b_set.dst, Is) of true -> %% Bool is a variable defined in this - %% block. It will change the outcome of - %% the `not member(V, UnsetVars)` check in - %% is_br_safe/2. The other variables - %% defined in this block will not. - ordsets:add_element(Bool, UnsetVars); + %% block. Using the br instruction from + %% this block (and skipping the body of + %% the block) is unsafe. + unsafe; false -> %% Bool is either a variable not defined %% in this block or a literal. Adding it @@ -321,18 +339,24 @@ update_unset_vars(L, Br, SetInThisBlock, UnsetVars, #st{skippable=Skippable}) -> %% the outcome of the tests in %% is_br_safe/2. UnsetVars - end + end; + #b_br{} -> + UnsetVars end; false -> + %% Some variables defined in this block are used by + %% successors. We must update the set of unset variables. + SetInThisBlock = [V || #b_set{dst=V} <- Is], ordsets:union(UnsetVars, ordsets:from_list(SetInThisBlock)) end. -shortcut_two_way(#b_br{succ=Succ,fail=Fail}, Bs0, UnsetVars0, St) -> - case shortcut_2(Succ, Bs0, UnsetVars0, St#st{target=Fail}) of +shortcut_two_way(#b_br{succ=Succ,fail=Fail}, From, Bs0, UnsetVars0, St0) -> + case shortcut_2(Succ, From, Bs0, UnsetVars0, St0#st{target=Fail}) of {#b_br{bool=#b_literal{},succ=Fail},_,_}=Res -> Res; none -> - case shortcut_2(Fail, Bs0, UnsetVars0, St#st{target=Succ}) of + St = St0#st{target=Succ}, + case shortcut_2(Fail, From, Bs0, UnsetVars0, St) of {#b_br{bool=#b_literal{},succ=Succ},_,_}=Res -> Res; none -> @@ -374,40 +398,42 @@ is_forbidden(L, St) -> %% Return the updated bindings, or 'none' if there is %% any instruction with potential side effects. -eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], Bs0, St) -> - From = map_get(from, Bs0), - [Val] = [Val || {Val,Pred} <- Args, Pred =:= From], +eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], From, Bs0, St) -> + Val = get_phi_arg(Args, From), Bs = bind_var(Dst, Val, Bs0), - eval_is(Is, Bs, St); -eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], Bs, St) -> + eval_is(Is, From, Bs, St); +eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], From, Bs, St) -> I = sub(I0, Bs), case eval_bif(I, St) of #b_literal{}=Val -> - eval_is(Is, bind_var(Dst, Val, Bs), St); + eval_is(Is, From, bind_var(Dst, Val, Bs), St); none -> - eval_is(Is, Bs, St) + eval_is(Is, From, Bs, St) end; -eval_is([#b_set{op=Op,dst=Dst}=I|Is], Bs, St) +eval_is([#b_set{op=Op,dst=Dst}=I|Is], From, Bs, St) when Op =:= is_tagged_tuple; Op =:= is_nonempty_list -> #b_set{args=Args} = sub(I, Bs), case eval_rel_op(Op, Args, St) of #b_literal{}=Val -> - eval_is(Is, bind_var(Dst, Val, Bs), St); + eval_is(Is, From, bind_var(Dst, Val, Bs), St); none -> - eval_is(Is, Bs, St) + eval_is(Is, From, Bs, St) end; -eval_is([#b_set{}=I|Is], Bs, St) -> +eval_is([#b_set{}=I|Is], From, Bs, St) -> case beam_ssa:no_side_effect(I) of true -> %% This instruction has no side effects. It can %% safely be omitted. - eval_is(Is, Bs, St); + eval_is(Is, From, Bs, St); false -> %% This instruction may have some side effect. %% It is not safe to avoid this instruction. none end; -eval_is([], Bs, _St) -> Bs. +eval_is([], _From, Bs, _St) -> Bs. + +get_phi_arg([{Val,From}|_], From) -> Val; +get_phi_arg([_|As], From) -> get_phi_arg(As, From). eval_terminator(#b_br{bool=#b_var{}=Bool}=Br, Bs, _St) -> Val = get_value(Bool, Bs), @@ -477,20 +503,31 @@ eval_bif(#b_set{op={bif,Bif},args=Args}, St) -> false -> none; true -> - case [Lit || #b_literal{val=Lit} <- Args] of - LitArgs when length(LitArgs) =:= Arity -> + case get_lit_args(Args) of + none -> + %% Not literal arguments. Try to evaluate + %% it based on a previous relational operator. + eval_rel_op({bif,Bif}, Args, St); + LitArgs -> try apply(erlang, Bif, LitArgs) of Val -> #b_literal{val=Val} catch error:_ -> none - end; - _ -> - %% Not literal arguments. Try to evaluate - %% it based on a previous relational operator. - eval_rel_op({bif,Bif}, Args, St) + end end end. +get_lit_args([#b_literal{val=Lit1}]) -> + [Lit1]; +get_lit_args([#b_literal{val=Lit1}, + #b_literal{val=Lit2}]) -> + [Lit1,Lit2]; +get_lit_args([#b_literal{val=Lit1}, + #b_literal{val=Lit2}, + #b_literal{val=Lit3}]) -> + [Lit1,Lit2,Lit3]; +get_lit_args(_) -> none. + %%% %%% Handling of relational operators. %%% @@ -1026,11 +1063,12 @@ used_vars_is([], Used) -> sub(#b_set{args=Args}=I, Sub) -> I#b_set{args=[sub_arg(A, Sub) || A <- Args]}. -sub_arg(Old, Sub) -> +sub_arg(#b_var{}=Old, Sub) -> case Sub of #{Old:=New} -> New; #{} -> Old - end. + end; +sub_arg(Old, _Sub) -> Old. rel2fam(S0) -> S1 = sofs:relation(S0), 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. diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl index 7bf1a202d9..e2b8787224 100644 --- a/lib/compiler/src/v3_kernel.erl +++ b/lib/compiler/src/v3_kernel.erl @@ -1590,19 +1590,12 @@ match_var([U|Us], Cs0, Def, St) -> %% constructor/constant as first argument. Group the constructors %% according to type, the order is really irrelevant but tries to be %% smart. - -match_con(Us, Cs0, Def, St) -> - %% Expand literals at the top level. - Cs = [expand_pat_lit_clause(C) || C <- Cs0], - match_con_1(Us, Cs, Def, St). - -match_con_1([U|_Us] = L, Cs, Def, St0) -> +match_con([U|_Us] = L, Cs, Def, St0) -> %% Extract clauses for different constructors (types). %%ok = io:format("match_con ~p~n", [Cs]), - Ttcs0 = select_types([k_binary], Cs) ++ select_bin_con(Cs) ++ - select_types([k_cons,k_tuple,k_map,k_atom,k_float, - k_int,k_nil], Cs), - Ttcs = opt_single_valued(Ttcs0), + Ttcs0 = select_types(Cs, [], [], [], [], [], [], [], [], []), + Ttcs1 = [{T, Types} || {T, [_ | _] = Types} <- Ttcs0], + Ttcs = opt_single_valued(Ttcs1), %%ok = io:format("ttcs = ~p~n", [Ttcs]), {Scs,St1} = mapfoldl(fun ({T,Tcs}, St) -> @@ -1613,8 +1606,41 @@ match_con_1([U|_Us] = L, Cs, Def, St0) -> St0, Ttcs), {build_alt_1st_no_fail(build_select(U, Scs), Def),St1}. -select_types(Types, Cs) -> - [{T,Tcs} || T <- Types, begin Tcs = select(T, Cs), Tcs =/= [] end]. +select_types([NoExpC | Cs], Bin, BinCon, Cons, Tuple, Map, Atom, Float, Int, Nil) -> + C = expand_pat_lit_clause(NoExpC), + case clause_con(C) of + k_binary -> + select_types(Cs, [C |Bin], BinCon, Cons, Tuple, Map, Atom, Float, Int, Nil); + k_bin_seg -> + select_types(Cs, Bin, [C | BinCon], Cons, Tuple, Map, Atom, Float, Int, Nil); + k_bin_end -> + select_types(Cs, Bin, [C | BinCon], Cons, Tuple, Map, Atom, Float, Int, Nil); + k_cons -> + select_types(Cs, Bin, BinCon, [C | Cons], Tuple, Map, Atom, Float, Int, Nil); + k_tuple -> + select_types(Cs, Bin, BinCon, Cons, [C | Tuple], Map, Atom, Float, Int, Nil); + k_map -> + select_types(Cs, Bin, BinCon, Cons, Tuple, [C | Map], Atom, Float, Int, Nil); + k_atom -> + select_types(Cs, Bin, BinCon, Cons, Tuple, Map, [C | Atom], Float, Int, Nil); + k_float -> + select_types(Cs, Bin, BinCon, Cons, Tuple, Map, Atom, [C | Float], Int, Nil); + k_int -> + select_types(Cs, Bin, BinCon, Cons, Tuple, Map, Atom, Float, [C | Int], Nil); + k_nil -> + select_types(Cs, Bin, BinCon, Cons, Tuple, Map, Atom, Float, Int, [C | Nil]) + end; +select_types([], Bin, BinCon, Cons, Tuple, Map, Atom, Float, Int, Nil) -> + [{k_binary, reverse(Bin)}] ++ handle_bin_con(reverse(BinCon)) ++ + [ + {k_cons, reverse(Cons)}, + {k_tuple, reverse(Tuple)}, + {k_map, reverse(Map)}, + {k_atom, reverse(Atom)}, + {k_float, reverse(Float)}, + {k_int, reverse(Int)}, + {k_nil, reverse(Nil)} + ]. expand_pat_lit_clause(#iclause{pats=[#ialias{pat=#k_literal{anno=A,val=Val}}=Alias|Ps]}=C) -> P = expand_pat_lit(Val, A), @@ -1743,20 +1769,12 @@ combine_bin_segs(#k_bin_end{}) -> combine_bin_segs(_) -> throw(not_possible). -%% select_bin_con([Clause]) -> [{Type,[Clause]}]. -%% Extract clauses for the k_bin_seg constructor. As k_bin_seg +%% handle_bin_con([Clause]) -> [{Type,[Clause]}]. +%% Handle clauses for the k_bin_seg constructor. As k_bin_seg %% matching can overlap, the k_bin_seg constructors cannot be %% reordered, only grouped. -select_bin_con(Cs0) -> - Cs1 = lists:filter(fun (C) -> - Con = clause_con(C), - (Con =:= k_bin_seg) or (Con =:= k_bin_end) - end, Cs0), - select_bin_con_1(Cs1). - - -select_bin_con_1(Cs) -> +handle_bin_con(Cs) -> try %% The usual way to match literals is to first extract the %% value to a register, and then compare the register to the @@ -1795,14 +1813,14 @@ select_bin_con_1(Cs) -> end catch throw:not_possible -> - select_bin_con_2(Cs) + handle_bin_con_not_possible(Cs) end. -select_bin_con_2([C1|Cs]) -> +handle_bin_con_not_possible([C1|Cs]) -> Con = clause_con(C1), {More,Rest} = splitwith(fun (C) -> clause_con(C) =:= Con end, Cs), - [{Con,[C1|More]}|select_bin_con_2(Rest)]; -select_bin_con_2([]) -> []. + [{Con,[C1|More]}|handle_bin_con_not_possible(Rest)]; +handle_bin_con_not_possible([]) -> []. %% select_bin_int([Clause]) -> {k_bin_int,[Clause]} %% If the first pattern in each clause selects the same integer, @@ -1902,10 +1920,6 @@ select_utf8(Val0) -> throw(not_possible) end. -%% select(Con, [Clause]) -> [Clause]. - -select(T, Cs) -> [ C || C <- Cs, clause_con(C) =:= T ]. - %% match_value([Var], Con, [Clause], Default, State) -> {SelectExpr,State}. %% At this point all the clauses have the same constructor, we must %% now separate them according to value. |