Merge pull request #2167 from bjorng/bjorn/tune-beam

Tune BEAM instructions for the new compiler (part 1)

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.