Slightly optimize updating of maps

The instruction put_map_assoc/5 (used for updating a map) has a
failure operand, but it can't actually fail provided that its "map"
argument is a map.

The following code:

    M#{key=>value}.

will be compiled to:

    {test,is_map,{f,3},[{x,0}]}.
    {line,[...]}.
    {put_map_assoc,{f,0},{x,0},{x,0},1,{list,[{atom,key},{atom,value}]}}.
    return.
  {label,3}.
    %% Code that produces a 'badmap' exception follows.

Because of the is_map instruction, {x,0} always contains a map when
the put_map_assoc instruction is executed. Therefore we can remove
the failure operand. That will save one word, and also eliminate
two tests at run-time.

The only problem is that the compiler in OTP 17 did not emit a
is_map instruction before the put_map_assoc instruction. Therefore,
we must add an instruction that tests for a map if the code was
compiled with the OTP 17 compiler.

Unfortunately, there is no safe and relatively easy way to known that
the OTP 17 compiler was used, so we will check whether a compiler
before OTP 20 was used. OTP 20 introduced a new chunk type for atoms,
which is trivial to check.

8 files changed, 109 insertions, 39 deletions

diff --git a/erts/emulator/beam/beam_debug.c b/erts/emulator/beam/beam_debug.c
index fa912e52e9..afe87288ce 100644
--- a/erts/emulator/beam/beam_debug.c
+++ b/erts/emulator/beam/beam_debug.c
@@ -697,7 +697,7 @@ print_op(fmtfn_t to, void *to_arg, int op, int size, BeamInstr* addr)
     case op_i_put_tuple_xI:
     case op_i_put_tuple_yI:
     case op_new_map_dII:
-    case op_update_map_assoc_jsdII:
+    case op_update_map_assoc_sdII:
     case op_update_map_exact_jsdII:
 	{
 	    int n = unpacked[-1];
diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c
index ff3c725bbc..e5935f5f02 100644
--- a/erts/emulator/beam/beam_emu.c
+++ b/erts/emulator/beam/beam_emu.c
@@ -2849,19 +2849,14 @@ update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
     Eterm new_key;
     Eterm* kp;
 
-    new_p = &Arg(5);
-    num_updates = Arg(4) / 2;
+    new_p = &Arg(4);
+    num_updates = Arg(3) / 2;
 
     if (is_not_flatmap(map)) {
 	Uint32 hx;
 	Eterm val;
 
-	/* apparently the compiler does not emit is_map instructions,
-	 * bad compiler */
-
-	if (is_not_hashmap(map))
-	    return THE_NON_VALUE;
-
+	ASSERT(is_hashmap(map));
 	res = map;
 	E = p->stop;
 	while(num_updates--) {
@@ -2885,7 +2880,7 @@ update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
      */
 
     if (num_old == 0) {
-	return new_map(p, reg, I+1);
+	return new_map(p, reg, I);
     }
 
     /*
@@ -2895,7 +2890,7 @@ update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
 
     need = 2*(num_old+num_updates) + 1 + MAP_HEADER_FLATMAP_SZ;
     if (HeapWordsLeft(p) < need) {
-	Uint live = Arg(3);
+	Uint live = Arg(2);
 	reg[live] = map;
 	erts_garbage_collect(p, need, reg, live+1);
 	map      = reg[live];
diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c
index d38e71f489..dcd312f54f 100644
--- a/erts/emulator/beam/beam_load.c
+++ b/erts/emulator/beam/beam_load.c
@@ -306,6 +306,7 @@ typedef struct LoaderState {
     int on_load;		/* Index in the code for the on_load function
 				 * (or 0 if there is no on_load function)
 				 */
+    int otp_20_or_higher;       /* Compiled with OTP 20 or higher */
 
     /*
      * Atom table.
@@ -740,6 +741,13 @@ erts_prepare_loading(Binary* magic, Process *c_p, Eterm group_leader,
     }
 
     /*
+     * Find out whether the code was compiled with OTP 20
+     * or higher.
+     */
+
+    stp->otp_20_or_higher = stp->chunks[UTF8_ATOM_CHUNK].size > 0;
+
+    /*
      * Load the code chunk.
      */
 
@@ -2731,6 +2739,12 @@ load_code(LoaderState* stp)
 
 #define never(St) 0
 
+static int
+compiled_with_otp_20_or_higher(LoaderState* stp)
+{
+    return stp->otp_20_or_higher;
+}
+
 /*
  * Predicate that tests whether a jump table can be used.
  */
diff --git a/erts/emulator/beam/macros.tab b/erts/emulator/beam/macros.tab
index 57015fac31..41dc761e90 100644
--- a/erts/emulator/beam/macros.tab
+++ b/erts/emulator/beam/macros.tab
@@ -92,6 +92,11 @@ NEXT(Addr) {
     Goto(*I);
 }
 
+FAIL_BODY() {
+    //| -no_prefetch
+    goto find_func_info;
+}
+
 FAIL_HEAD_OR_BODY(Fail) {
     //| -no_prefetch
     if ($Fail) {
diff --git a/erts/emulator/beam/map_instrs.tab b/erts/emulator/beam/map_instrs.tab
index 7f9346d029..30c3d7743f 100644
--- a/erts/emulator/beam/map_instrs.tab
+++ b/erts/emulator/beam/map_instrs.tab
@@ -19,10 +19,12 @@
 // %CopyrightEnd%
 //
 
-BADMAP(Fail, Map) {
-    c_p->freason = BADMAP;
-    c_p->fvalue = $Map;
-    $FAIL_HEAD_OR_BODY($Fail);
+ensure_map(Map) {
+    if (is_not_map($Map)) {
+        c_p->freason = BADMAP;
+        c_p->fvalue = $Map;
+        $FAIL_BODY();
+    }
 }
 
 new_map(Dst, Live, N) {
@@ -123,7 +125,7 @@ i_get_map_elements(Fail, Src, N) {
     }
 }
 
-update_map_assoc(Fail, Src, Dst, Live, N) {
+update_map_assoc(Src, Dst, Live, N) {
     Eterm res;
     Eterm map;
 
@@ -131,17 +133,10 @@ update_map_assoc(Fail, Src, Dst, Live, N) {
     HEAVY_SWAPOUT;
     res = update_map_assoc(c_p, reg, map, I);
     HEAVY_SWAPIN;
-    if (is_value(res)) {
-        $REFRESH_GEN_DEST();
-        $Dst = res;
-        $NEXT($NEXT_INSTRUCTION+$N);
-    } else {
-        /*
-         * This can only happen if the code was compiled
-         * with the compiler in OTP 17.
-         */
-        $BADMAP($Fail, map);
-    }
+    ASSERT(is_value(res));
+    $REFRESH_GEN_DEST();
+    $Dst = res;
+    $NEXT($NEXT_INSTRUCTION+$N);
 }
 
 update_map_exact(Fail, Src, Dst, Live, N) {
diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab
index fdc4506351..92e67bb470 100644
--- a/erts/emulator/beam/ops.tab
+++ b/erts/emulator/beam/ops.tab
@@ -1299,23 +1299,52 @@ apply I
 apply_last I P
 
 #
-# Map instructions in R17.
+# Handle compatibility with OTP 17 here.
 #
 
-sorted_put_map_assoc/5
-put_map_assoc F Map Dst Live Size Rest=* | map_key_sort(Size, Rest) => \
-  sorted_put_map_assoc F Map Dst Live Size Rest
+i_put_map_assoc/4
+
+# We KNOW that in OTP 20 (actually OTP 18 and higher), a put_map_assoc instruction
+# is always preceded by an is_map test. That means that put_map_assoc can never
+# fail and does not need any failure label.
+
+put_map_assoc Fail Map Dst Live Size Rest=* | compiled_with_otp_20_or_higher() => \
+	      i_put_map_assoc Map Dst Live Size Rest
+
+# Translate the put_map_assoc instruction if the module was compiled by a compiler
+# before 20. This is only necessary if the OTP 17 compiler was used, but we
+# have no safe and relatively easy way to know whether OTP 18/19 was used.
+
+put_map_assoc Fail=p Map Dst Live Size Rest=* => \
+	      ensure_map Map | i_put_map_assoc Map Dst Live Size Rest
+put_map_assoc Fail=f Map Dst Live Size Rest=* => \
+	      is_map Fail Map | i_put_map_assoc Map Dst Live Size Rest
+
+ensure_map Lit=q | literal_is_map(Lit) =>
+ensure_map Src=cqy => move Src x | ensure_map x
+
+%cold
+ensure_map x
+%hot
+
+#
+# Map instructions. First introduced in R17.
+#
+
+sorted_put_map_assoc/4
+i_put_map_assoc Map Dst Live Size Rest=* | map_key_sort(Size, Rest) => \
+  sorted_put_map_assoc Map Dst Live Size Rest
 
 sorted_put_map_exact/5
 put_map_exact F Map Dst Live Size Rest=* | map_key_sort(Size, Rest) => \
   sorted_put_map_exact F Map Dst Live Size Rest
 
-sorted_put_map_assoc j Map Dst Live Size Rest=* | is_empty_map(Map) => \
+sorted_put_map_assoc Map Dst Live Size Rest=* | is_empty_map(Map) => \
    new_map Dst Live Size Rest
-sorted_put_map_assoc F Src=s Dst Live Size Rest=* => \
-	       update_map_assoc F Src Dst Live Size Rest
-sorted_put_map_assoc F Src Dst Live Size Rest=* => \
-	       move Src x | update_map_assoc F x Dst Live Size Rest
+sorted_put_map_assoc Src=s Dst Live Size Rest=* => \
+	       update_map_assoc Src Dst Live Size Rest
+sorted_put_map_assoc Src Dst Live Size Rest=* => \
+	       move Src x | update_map_assoc x Dst Live Size Rest
 
 sorted_put_map_exact F Src=s Dst Live Size Rest=* => \
 	      update_map_exact F Src Dst Live Size Rest
@@ -1327,7 +1356,7 @@ new_map Dst Live Size Rest=* | is_small_map_literal_keys(Size, Rest) => \
 
 new_map d I I
 i_new_small_map_lit d I q
-update_map_assoc j s d I I
+update_map_assoc s d I I
 update_map_exact j s d I I
 
 is_map Fail Lit=q | literal_is_map(Lit) =>
diff --git a/erts/emulator/test/map_SUITE_data/badmap_17.beam b/erts/emulator/test/map_SUITE_data/badmap_17.beam
index 277fc34b94..6f79bb8c2c 100644
--- a/erts/emulator/test/map_SUITE_data/badmap_17.beam
+++ b/erts/emulator/test/map_SUITE_data/badmap_17.beam
diff --git a/erts/emulator/test/map_SUITE_data/badmap_17.erl b/erts/emulator/test/map_SUITE_data/badmap_17.erl
index 0ec65e0e33..887fc2e5e3 100644
--- a/erts/emulator/test/map_SUITE_data/badmap_17.erl
+++ b/erts/emulator/test/map_SUITE_data/badmap_17.erl
@@ -1,7 +1,7 @@
 -module(badmap_17).
 -export([update/1]).
 
-%% Compile this source file with OTP 17.
+%% Compile this source file with OTP 17.0.
 
 update(Map) ->
     try
@@ -17,10 +17,42 @@ update(Map) ->
     catch
 	error:{badmap,Map} ->
 	    ok
-    end.
+    end,
+    try
+	update_3(Map),
+	error(update_did_not_fail)
+    catch
+	error:{badmap,Map} ->
+	    ok
+    end,
+    ok = update_4(Map),
+    ok = update_5(Map),
+    ok.
 
 update_1(M) ->
     M#{a=>42}.
 
 update_2(M) ->
     M#{a:=42}.
+
+update_3(M) ->
+    id(M),
+    M#{a=>42}.
+
+update_4(M) when M#{a=>b} =:= M ->
+    did_not_fail;
+update_4(_) ->
+    ok.
+
+update_5(M) ->
+    id(M),
+    case id(true) of
+        true when M#{a=>b} =:= M ->
+            did_not_fail;
+        true ->
+            ok
+    end.
+
+id(I) ->
+    I.
+