Merge branch 'bjorn/maps'

* bjorn/maps:
  Document the new {badmap,Term} and {badkey,Key} exceptions
  Raise more descriptive error messages for failed map operations
  erl_term.h: Add is_not_map() macro
  Tigthen code for the i_get_map_elements/3 instruction
  Pre-compute hash values for the general get_map_elements instruction
  Teach the loader to pre-compute the hash value for single-key lookups
  Optimize use of i_get_map_element/4
  beam_emu: Slightly optimize update_map_{assoc,exact}
  v3_codegen: Don't sort map keys in map creation/update
  beam_validator: No longer require strict literal term order
  Sort maps keys in the loader
  De-optimize the has_map_fields instructions
  erts/map_SUITE.erl: Add a test case that tests has_map_fields
  Fully evaluate is_map/1 for literals at load-time
  map_SUITE: Add tests of is_map/1 with literal maps
  Run a clone of map_SUITE without optimizations
  Remove the fail label operand of the new_map instruction
  Correct transformation of put_map_assoc to new_map
  Remove support for put_map_exact without a source map

9 files changed, 385 insertions, 209 deletions

diff --git a/erts/emulator/beam/atom.names b/erts/emulator/beam/atom.names
index ae3f30d82f..8fdcbb4058 100644
--- a/erts/emulator/beam/atom.names
+++ b/erts/emulator/beam/atom.names
@@ -104,7 +104,7 @@ atom await_sched_wall_time_modifications
 atom awaiting_load
 atom awaiting_unload
 atom backtrace backtrace_depth
-atom badarg badarith badarity badfile badmatch badsig badfun
+atom badarg badarith badarity badfile badfun badkey badmap badmatch badsig
 atom bag
 atom band
 atom big
diff --git a/erts/emulator/beam/beam_debug.c b/erts/emulator/beam/beam_debug.c
index 6bb987985d..0367ca8aba 100644
--- a/erts/emulator/beam/beam_debug.c
+++ b/erts/emulator/beam/beam_debug.c
@@ -661,10 +661,9 @@ print_op(int to, void *to_arg, int op, int size, BeamInstr* addr)
     case op_i_put_tuple_rI:
     case op_i_put_tuple_xI:
     case op_i_put_tuple_yI:
-    case op_new_map_jdII:
+    case op_new_map_dII:
     case op_update_map_assoc_jsdII:
     case op_update_map_exact_jsdII:
-    case op_i_has_map_fields_fsI:
     case op_i_get_map_elements_fsI:
 	{
 	    int n = unpacked[-1];
diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c
index 4e01d94b92..6a3415d9f4 100644
--- a/erts/emulator/beam/beam_emu.c
+++ b/erts/emulator/beam/beam_emu.c
@@ -701,8 +701,6 @@ void** beam_ops;
 
 #define IsMap(Src, Fail) if (!is_map(Src)) { Fail; }
 
-#define HasMapField(Src, Key, Fail) if (has_not_map_field(Src, Key)) { Fail; }
-
 #define GetMapElement(Src, Key, Dst, Fail)	\
   do {						\
      Eterm _res = get_map_element(Src, Key);	\
@@ -712,6 +710,15 @@ void** beam_ops;
      Dst = _res;				\
   } while (0)
 
+#define GetMapElementHash(Src, Key, Hx, Dst, Fail)	\
+  do {							\
+     Eterm _res = get_map_element_hash(Src, Key, Hx);	\
+     if (is_non_value(_res)) {				\
+        Fail;						\
+     }							\
+     Dst = _res;					\
+  } while (0)
+
 #define IsFunction(X, Action)			\
   do {						\
      if ( !(is_any_fun(X)) ) {			\
@@ -960,8 +967,8 @@ static Eterm update_map_assoc(Process* p, Eterm* reg,
 			      Eterm map, BeamInstr* I) NOINLINE;
 static Eterm update_map_exact(Process* p, Eterm* reg,
 			      Eterm map, BeamInstr* I) NOINLINE;
-static int has_not_map_field(Eterm map, Eterm key);
 static Eterm get_map_element(Eterm map, Eterm key);
+static Eterm get_map_element_hash(Eterm map, Eterm key, Uint32 hx);
 
 /*
  * Functions not directly called by process_main(). OK to inline.
@@ -2371,77 +2378,16 @@ void process_main(void)
      Goto(*I);
  }
 
- OpCase(new_map_jdII): {
+ OpCase(new_map_dII): {
      Eterm res;
 
      x(0) = r(0);
      SWAPOUT;
-     res = new_map(c_p, reg, I);
+     res = new_map(c_p, reg, I-1);
      SWAPIN;
      r(0) = x(0);
-     StoreResult(res, Arg(1));
-     Next(4+Arg(3));
- }
-
- OpCase(i_has_map_fields_fsI): {
-    flatmap_t* mp;
-    Eterm map;
-    Eterm field;
-    Eterm *ks;
-    BeamInstr* fs;
-    Uint sz,n;
-
-    GetArg1(1, map);
-    n  = (Uint)Arg(2);
-    fs = &Arg(3); /* pattern fields */
-
-    /* get term from field? */
-    if (is_hashmap(map)) {
-	Uint32 hx;
-	while(n--) {
-	    field = *fs++;
-	    hx = hashmap_make_hash(field);
-	    if (!erts_hashmap_get(hx,field,map)) {
-		SET_I((BeamInstr *) Arg(0));
-		goto has_map_fields_fail;
-	    }
-	}
-	goto has_map_fields_ok;
-    }
-
-    ASSERT(is_flatmap(map));
-
-    mp = (flatmap_t *)flatmap_val(map);
-    sz = flatmap_get_size(mp);
-
-    if (sz == 0) {
-	SET_I((BeamInstr *) Arg(0));
-	goto has_map_fields_fail;
-    }
-
-    ks = flatmap_get_keys(mp);
-
-    ASSERT(n>0);
-
-    while(sz) {
-	field = (Eterm)*fs;
-	if (EQ(field,*ks)) {
-	    n--;
-	    fs++;
-	    if (n == 0) break;
-	}
-	ks++; sz--;
-    }
-
-    if (n) {
-	SET_I((BeamInstr *) Arg(0));
-	goto has_map_fields_fail;
-    }
-has_map_fields_ok:
-    I += 4 + Arg(2);
-has_map_fields_fail:
-    ASSERT(VALID_INSTR(*I));
-    Goto(*I);
+     StoreResult(res, Arg(0));
+     Next(3+Arg(2));
  }
 
 #define PUT_TERM_REG(term, desc)				\
@@ -2473,7 +2419,7 @@ do {								\
      * i.e. that it follows a test is_map if needed.
      */
 
-    n  = (Uint)Arg(2) / 2;
+    n  = (Uint)Arg(2) / 3;
     fs = &Arg(3); /* pattern fields and target registers */
 
     if (is_flatmap(map)) {
@@ -2485,49 +2431,43 @@ do {								\
 	sz = flatmap_get_size(mp);
 
 	if (sz == 0) {
-	    SET_I((BeamInstr *) Arg(0));
-	    goto get_map_elements_fail;
+	    ClauseFail();
 	}
 
 	ks = flatmap_get_keys(mp);
 	vs = flatmap_get_values(mp);
 
 	while(sz) {
-	    if (EQ((Eterm)*fs,*ks)) {
+	    if (EQ((Eterm) fs[0], *ks)) {
 		PUT_TERM_REG(*vs, fs[1]);
 		n--;
-		fs += 2;
+		fs += 3;
 		/* no more values to fetch, we are done */
-		if (n == 0) break;
+		if (n == 0) {
+		    I = fs;
+		    Next(-1);
+		}
 	    }
-	    ks++; sz--;
-	    vs++;
+	    ks++, sz--, vs++;
 	}
 
-	if (n) {
-	    SET_I((BeamInstr *) Arg(0));
-	    goto get_map_elements_fail;
-	}
+	ClauseFail();
     } else {
 	const Eterm *v;
 	Uint32 hx;
 	ASSERT(is_hashmap(map));
 	while(n--) {
-	    hx = hashmap_make_hash((Eterm)*fs);
-	    if ((v = erts_hashmap_get(hx,(Eterm)*fs, map)) == NULL) {
-		SET_I((BeamInstr *) Arg(0));
-		goto get_map_elements_fail;
+	    hx = fs[2];
+	    ASSERT(hx == hashmap_make_hash((Eterm)fs[0]));
+	    if ((v = erts_hashmap_get(hx, (Eterm)fs[0], map)) == NULL) {
+		ClauseFail();
 	    }
 	    PUT_TERM_REG(*v, fs[1]);
-	    fs += 2;
+	    fs += 3;
 	}
+	I = fs;
+	Next(-1);
     }
-
-
-    I += 4 + Arg(2);
-get_map_elements_fail:
-    ASSERT(VALID_INSTR(*I));
-    Goto(*I);
  }
 #undef PUT_TERM_REG
 
@@ -2545,7 +2485,13 @@ get_map_elements_fail:
 	 StoreResult(res, Arg(2));
 	 Next(5+Arg(4));
      } else {
-	 goto badarg;
+	 /*
+	  * This can only happen if the code was compiled
+	  * with the compiler in OTP 17.
+	  */
+	 c_p->freason = BADMAP;
+	 c_p->fvalue = map;
+	 goto lb_Cl_error;
      }
  }
 
@@ -2563,7 +2509,7 @@ get_map_elements_fail:
 	 StoreResult(res, Arg(2));
 	 Next(5+Arg(4));
      } else {
-	 goto badarg;
+	 goto lb_Cl_error;
      }
  }
 
@@ -5313,7 +5259,9 @@ Eterm error_atom[NUMBER_EXIT_CODES] = {
   am_notalive,		/* 14 */
   am_system_limit,	/* 15 */
   am_try_clause,	/* 16 */
-  am_notsup		/* 17 */
+  am_notsup,		/* 17 */
+  am_badmap,		/* 18 */
+  am_badkey,		/* 19 */
 };
 
 /*
@@ -5569,6 +5517,8 @@ expand_error_value(Process* c_p, Uint freason, Eterm Value) {
     case (GET_EXC_INDEX(EXC_TRY_CLAUSE)):
     case (GET_EXC_INDEX(EXC_BADFUN)):
     case (GET_EXC_INDEX(EXC_BADARITY)):
+    case (GET_EXC_INDEX(EXC_BADMAP)):
+    case (GET_EXC_INDEX(EXC_BADKEY)):
         /* Some common exceptions: value -> {atom, value} */
         ASSERT(is_value(Value));
 	hp = HAlloc(c_p, 3);
@@ -6450,42 +6400,45 @@ new_fun(Process* p, Eterm* reg, ErlFunEntry* fe, int num_free)
     return make_fun(funp);
 }
 
-static int has_not_map_field(Eterm map, Eterm key)
+static Eterm get_map_element(Eterm map, Eterm key)
 {
     Uint32 hx;
+    const Eterm *vs;
     if (is_flatmap(map)) {
-	flatmap_t* mp;
-	Eterm* keys;
+	flatmap_t *mp;
+	Eterm *ks;
 	Uint i;
 	Uint n;
 
-	mp   = (flatmap_t *)flatmap_val(map);
-	keys = flatmap_get_keys(mp);
-	n    = flatmap_get_size(mp);
+	mp = (flatmap_t *)flatmap_val(map);
+	ks = flatmap_get_keys(mp);
+	vs = flatmap_get_values(mp);
+	n  = flatmap_get_size(mp);
 	if (is_immed(key)) {
 	    for (i = 0; i < n; i++) {
-		if (keys[i] == key) {
-		    return 0;
+		if (ks[i] == key) {
+		    return vs[i];
 		}
 	    }
 	} else {
-	    for (i = 0; i <  n; i++) {
-		if (EQ(keys[i], key)) {
-		    return 0;
+	    for (i = 0; i < n; i++) {
+		if (EQ(ks[i], key)) {
+		    return vs[i];
 		}
 	    }
 	}
-	return 1;
+	return THE_NON_VALUE;
     }
     ASSERT(is_hashmap(map));
     hx = hashmap_make_hash(key);
-    return erts_hashmap_get(hx,key,map) ? 0 : 1;
+    vs = erts_hashmap_get(hx,key,map);
+    return vs ? *vs : THE_NON_VALUE;
 }
 
-static Eterm get_map_element(Eterm map, Eterm key)
+static Eterm get_map_element_hash(Eterm map, Eterm key, Uint32 hx)
 {
-    Uint32 hx;
     const Eterm *vs;
+
     if (is_flatmap(map)) {
 	flatmap_t *mp;
 	Eterm *ks;
@@ -6511,9 +6464,10 @@ static Eterm get_map_element(Eterm map, Eterm key)
 	}
 	return THE_NON_VALUE;
     }
+
     ASSERT(is_hashmap(map));
-    hx = hashmap_make_hash(key);
-    vs = erts_hashmap_get(hx,key,map);
+    ASSERT(hx == hashmap_make_hash(key));
+    vs = erts_hashmap_get(hx, key, map);
     return vs ? *vs : THE_NON_VALUE;
 }
 
@@ -6648,10 +6602,9 @@ update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
 		reg[live] = res;
 		erts_garbage_collect(p, 0, reg, live+1);
 		res       = reg[live];
+		E = p->stop;
 	    }
 
-	    E = p->stop;
-
 	    new_p += 2;
 	}
 	return res;
@@ -6851,30 +6804,34 @@ update_map_exact(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
 	/* apparently the compiler does not emit is_map instructions,
 	 * bad compiler */
 
-	if (is_not_hashmap(map))
+	if (is_not_hashmap(map)) {
+	    p->freason = BADMAP;
+	    p->fvalue = map;
 	    return THE_NON_VALUE;
+	}
 
 	res = map;
 	E = p->stop;
 	while(n--) {
-	    /* assoc can't fail */
 	    GET_TERM(new_p[0], new_key);
 	    GET_TERM(new_p[1], val);
 	    hx = hashmap_make_hash(new_key);
 
 	    res = erts_hashmap_insert(p, hx, new_key, val, res,  1);
-	    if (is_non_value(res))
+	    if (is_non_value(res)) {
+		p->fvalue = new_key;
+		p->freason = BADKEY;
 		return res;
+	    }
 
 	    if (p->mbuf) {
 		Uint live = Arg(3);
 		reg[live] = res;
 		erts_garbage_collect(p, 0, reg, live+1);
 		res       = reg[live];
+		E = p->stop;
 	    }
 
-	    E = p->stop;
-
 	    new_p += 2;
 	}
 	return res;
@@ -6884,10 +6841,13 @@ update_map_exact(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
     num_old = flatmap_get_size(old_mp);
 
     /*
-     * If the old map is empty, create a new map.
+     * If the old map is empty, fail.
      */
 
     if (num_old == 0) {
+	E = p->stop;
+	p->freason = BADKEY;
+	GET_TERM(new_p[0], p->fvalue);
 	return THE_NON_VALUE;
     }
 
@@ -6957,6 +6917,8 @@ update_map_exact(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
      * update list did not previously exist.
      */
     ASSERT(hp == p->htop + need);
+    p->freason = BADKEY;
+    p->fvalue = new_key;
     return THE_NON_VALUE;
 }
 #undef GET_TERM
diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c
index 02689e5b19..8d7beb4eb4 100644
--- a/erts/emulator/beam/beam_load.c
+++ b/erts/emulator/beam/beam_load.c
@@ -36,6 +36,7 @@
 #include "beam_catches.h"
 #include "erl_binary.h"
 #include "erl_zlib.h"
+#include "erl_map.h"
 
 #ifdef HIPE
 #include "hipe_bif0.h"
@@ -4051,8 +4052,139 @@ tuple_append_put(LoaderState* stp, GenOpArg Arity, GenOpArg Dst,
 }
 
 /*
+ * Predicate to test whether the given literal is a map.
+ */
+
+static int
+literal_is_map(LoaderState* stp, GenOpArg Lit)
+{
+    Eterm term;
+
+    ASSERT(Lit.type == TAG_q);
+    term = stp->literals[Lit.val].term;
+    return is_map(term);
+}
+
+/*
+ * Predicate to test whether the given literal is an empty map.
+ */
+
+static int
+is_empty_map(LoaderState* stp, GenOpArg Lit)
+{
+    Eterm term;
+
+    if (Lit.type != TAG_q) {
+	return 0;
+    }
+    term = stp->literals[Lit.val].term;
+    return is_flatmap(term) && flatmap_get_size(flatmap_val(term)) == 0;
+}
+
+/*
+ * Pseudo predicate map_key_sort that will sort the Rest operand for
+ * map instructions as a side effect.
+ */
+
+typedef struct SortGenOpArg {
+    Eterm term;			/* Term to use for comparing  */
+    GenOpArg arg;		/* Original data */
+} SortGenOpArg;
+
+static int
+genopargtermcompare(SortGenOpArg* a, SortGenOpArg* b)
+{
+    return CMP_TERM(a->term, b->term);
+}
+
+static int
+map_key_sort(LoaderState* stp, GenOpArg Size, GenOpArg* Rest)
+{
+    SortGenOpArg* t;
+    unsigned size = Size.val;
+    unsigned i;
+
+    if (size == 2) {
+	return 1;		/* Already sorted. */
+    }
+
+
+    t = (SortGenOpArg *) erts_alloc(ERTS_ALC_T_TMP, size*sizeof(SortGenOpArg));
+
+    /*
+     * Copy original data and sort keys to a temporary array.
+     */
+    for (i = 0; i < size; i += 2) {
+	t[i].arg = Rest[i];
+	switch (Rest[i].type) {
+	case TAG_a:
+	    t[i].term = Rest[i].val;
+	    ASSERT(is_atom(t[i].term));
+	    break;
+	case TAG_i:
+	    t[i].term = make_small(Rest[i].val);
+	    break;
+	case TAG_n:
+	    t[i].term = NIL;
+	    break;
+	case TAG_q:
+	    t[i].term = stp->literals[Rest[i].val].term;
+	    break;
+	default:
+	    /*
+	     * Not a literal key. Not allowed. Only a single
+	     * variable key is allowed in each map instruction.
+	     */
+	    erts_free(ERTS_ALC_T_TMP, (void *) t);
+	    return 0;
+	}
+#ifdef DEBUG
+	t[i+1].term = THE_NON_VALUE;
+#endif
+	t[i+1].arg = Rest[i+1];
+    }
+
+    /*
+     * Sort the temporary array.
+     */
+    qsort((void *) t, size / 2, 2 * sizeof(SortGenOpArg),
+	  (int (*)(const void *, const void *)) genopargtermcompare);
+
+    /*
+     * Copy back the sorted, original data.
+     */
+    for (i = 0; i < size; i++) {
+	Rest[i] = t[i].arg;
+    }
+
+    erts_free(ERTS_ALC_T_TMP, (void *) t);
+    return 1;
+}
+
+static int
+hash_genop_arg(LoaderState* stp, GenOpArg Key, Uint32* hx)
+{
+    switch (Key.type) {
+    case TAG_a:
+	*hx = hashmap_make_hash(Key.val);
+	return 1;
+    case TAG_i:
+	*hx = hashmap_make_hash(make_small(Key.val));
+	return 1;
+    case TAG_n:
+	*hx = hashmap_make_hash(NIL);
+	return 1;
+    case TAG_q:
+	*hx = hashmap_make_hash(stp->literals[Key.val].term);
+	return 1;
+    default:
+	return 0;
+    }
+}
+
+/*
  * Replace a get_map_elements with one key to an instruction with one
- * element
+ * element.
  */
 
 static GenOp*
@@ -4060,37 +4192,99 @@ gen_get_map_element(LoaderState* stp, GenOpArg Fail, GenOpArg Src,
 		    GenOpArg Size, GenOpArg* Rest)
 {
     GenOp* op;
+    GenOpArg Key;
+    Uint32 hx = 0;
 
     ASSERT(Size.type == TAG_u);
 
     NEW_GENOP(stp, op);
     op->next = NULL;
-    op->op = genop_get_map_element_4;
-    op->arity = 4;
-
     op->a[0] = Fail;
     op->a[1] = Src;
     op->a[2] = Rest[0];
-    op->a[3] = Rest[1];
+
+    Key = Rest[0];
+    if (hash_genop_arg(stp, Key, &hx)) {
+	op->arity = 5;
+	op->op = genop_i_get_map_element_hash_5;
+	op->a[3].type = TAG_u;
+	op->a[3].val = (BeamInstr) hx;
+	op->a[4] = Rest[1];
+    } else {
+	op->arity = 4;
+	op->op = genop_i_get_map_element_4;
+	op->a[3] = Rest[1];
+    }
     return op;
 }
 
 static GenOp*
-gen_has_map_field(LoaderState* stp, GenOpArg Fail, GenOpArg Src,
-		    GenOpArg Size, GenOpArg* Rest)
+gen_get_map_elements(LoaderState* stp, GenOpArg Fail, GenOpArg Src,
+		     GenOpArg Size, GenOpArg* Rest)
 {
     GenOp* op;
+    Uint32 hx;
+    Uint i;
+    GenOpArg* dst;
+#ifdef DEBUG
+    int good_hash;
+#endif
 
     ASSERT(Size.type == TAG_u);
 
     NEW_GENOP(stp, op);
+    op->op = genop_i_get_map_elements_3;
+    GENOP_ARITY(op, 3 + 3*(Size.val/2));
     op->next = NULL;
-    op->op = genop_has_map_field_3;
-    op->arity = 4;
+    op->a[0] = Fail;
+    op->a[1] = Src;
+    op->a[2].type = TAG_u;
+    op->a[2].val = 3*(Size.val/2);
+
+    dst = op->a+3;
+    for (i = 0; i < Size.val / 2; i++) {
+	dst[0] = Rest[2*i];
+	dst[1] = Rest[2*i+1];
+#ifdef DEBUG
+	good_hash =
+#endif
+	    hash_genop_arg(stp, dst[0], &hx);
+#ifdef DEBUG
+	ASSERT(good_hash);
+#endif
+	dst[2].type = TAG_u;
+	dst[2].val = (BeamInstr) hx;
+	dst += 3;
+    }
+    return op;
+}
+
+static GenOp*
+gen_has_map_fields(LoaderState* stp, GenOpArg Fail, GenOpArg Src,
+		   GenOpArg Size, GenOpArg* Rest)
+{
+    GenOp* op;
+    Uint i;
+    Uint n;
+
+    ASSERT(Size.type == TAG_u);
+    n = Size.val;
+
+    NEW_GENOP(stp, op);
+    GENOP_ARITY(op, 3 + 2*n);
+    op->next = NULL;
+    op->op = genop_get_map_elements_3;
 
     op->a[0] = Fail;
     op->a[1] = Src;
-    op->a[2] = Rest[0];
+    op->a[2].type = TAG_u;
+    op->a[2].val = 2*n;
+
+    for (i = 0; i < n; i++) {
+	op->a[3+2*i] = Rest[i];
+	op->a[3+2*i+1].type = TAG_x;
+	op->a[3+2*i+1].val = 0;	/* x(0); normally not used */
+    }
     return op;
 }
 
diff --git a/erts/emulator/beam/erl_bif_guard.c b/erts/emulator/beam/erl_bif_guard.c
index e7d84ebda1..069327ee9d 100644
--- a/erts/emulator/beam/erl_bif_guard.c
+++ b/erts/emulator/beam/erl_bif_guard.c
@@ -467,7 +467,8 @@ Eterm erts_gc_map_size_1(Process* p, Eterm* reg, Uint live)
     } else if (is_hashmap(arg)) {
 	size = hashmap_size(arg);
     } else {
-	BIF_ERROR(p, BADARG);
+	p->fvalue = arg;
+	BIF_ERROR(p, BADMAP);
     }
     if (IS_USMALL(0, size)) {
 	return make_small(size);
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 98023bbb47..3aebbfdaa3 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -122,7 +122,8 @@ BIF_RETTYPE map_size_1(BIF_ALIST_1) {
 	BIF_RET(res);
     }
 
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_P->fvalue = BIF_ARG_1;
+    BIF_ERROR(BIF_P, BADMAP);
 }
 
 /* maps:to_list/1 */
@@ -150,7 +151,8 @@ BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) {
 	return hashmap_to_list(BIF_P, BIF_ARG_1);
     }
 
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_P->fvalue = BIF_ARG_1;
+    BIF_ERROR(BIF_P, BADMAP);
 }
 
 /* maps:find/2
@@ -217,34 +219,29 @@ BIF_RETTYPE maps_find_2(BIF_ALIST_2) {
 	}
 	BIF_RET(am_error);
     }
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_P->fvalue = BIF_ARG_2;
+    BIF_ERROR(BIF_P, BADMAP);
 }
 
 /* maps:get/2
  * return value if key *matches* a key in the map
- * exception bad_key if none matches
+ * exception badkey if none matches
  */
 
 BIF_RETTYPE maps_get_2(BIF_ALIST_2) {
     if (is_map(BIF_ARG_2)) {
-	Eterm *hp;
-        Eterm error;
         const Eterm *value;
-	char *s_error;
 
         value = erts_maps_get(BIF_ARG_1, BIF_ARG_2);
         if (value) {
             BIF_RET(*value);
 	}
 
-	s_error = "bad_key";
-	error = am_atom_put(s_error, sys_strlen(s_error));
-
-	hp = HAlloc(BIF_P, 3);
-	BIF_P->fvalue = TUPLE2(hp, error, BIF_ARG_1);
-	BIF_ERROR(BIF_P, EXC_ERROR_2);
+	BIF_P->fvalue = BIF_ARG_1;
+	BIF_ERROR(BIF_P, BADKEY);
     }
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_P->fvalue = BIF_ARG_2;
+    BIF_ERROR(BIF_P, BADMAP);
 }
 
 /* maps:from_list/1
@@ -911,7 +908,8 @@ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) {
     if (is_map(BIF_ARG_2)) {
 	BIF_RET(erts_maps_get(BIF_ARG_1, BIF_ARG_2) ? am_true : am_false);
     }
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_P->fvalue = BIF_ARG_2;
+    BIF_ERROR(BIF_P, BADMAP);
 }
 
 /* maps:keys/1 */
@@ -939,7 +937,8 @@ BIF_RETTYPE maps_keys_1(BIF_ALIST_1) {
     } else if (is_hashmap(BIF_ARG_1)) {
 	BIF_RET(hashmap_keys(BIF_P, BIF_ARG_1));
     }
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_P->fvalue = BIF_ARG_1;
+    BIF_ERROR(BIF_P, BADMAP);
 }
 /* maps:merge/2 */
 
@@ -951,6 +950,7 @@ BIF_RETTYPE maps_merge_2(BIF_ALIST_2) {
 	    /* Will always become a tree */
 	    BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_1, BIF_ARG_2, 0));
 	}
+	BIF_P->fvalue = BIF_ARG_2;
     } else if (is_hashmap(BIF_ARG_1)) {
 	if (is_hashmap(BIF_ARG_2)) {
 	    BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2));
@@ -958,8 +958,11 @@ BIF_RETTYPE maps_merge_2(BIF_ALIST_2) {
 	    /* Will always become a tree */
 	    BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_2, BIF_ARG_1, 1));
 	}
+	BIF_P->fvalue = BIF_ARG_2;
+    } else {
+	BIF_P->fvalue = BIF_ARG_1;
     }
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_ERROR(BIF_P, BADMAP);
 }
 
 static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
@@ -1398,7 +1401,8 @@ BIF_RETTYPE maps_put_3(BIF_ALIST_3) {
     if (is_map(BIF_ARG_3)) {
 	BIF_RET(erts_maps_put(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3));
     }
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_P->fvalue = BIF_ARG_3;
+    BIF_ERROR(BIF_P, BADMAP);
 }
 
 /* maps:remove/3 */
@@ -1492,7 +1496,8 @@ BIF_RETTYPE maps_remove_2(BIF_ALIST_2) {
 	    BIF_RET(res);
 	}
     }
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_P->fvalue = BIF_ARG_2;
+    BIF_ERROR(BIF_P, BADMAP);
 }
 
 int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res) {
@@ -1688,13 +1693,17 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
 /* maps:update/3 */
 
 BIF_RETTYPE maps_update_3(BIF_ALIST_3) {
-    if (is_map(BIF_ARG_3)) {
+    if (is_not_map(BIF_ARG_3)) {
+	BIF_P->fvalue = BIF_ARG_3;
+	BIF_ERROR(BIF_P, BADMAP);
+    } else {
 	Eterm res;
 	if (erts_maps_update(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, &res)) {
 	    BIF_RET(res);
 	}
+	BIF_P->fvalue = BIF_ARG_1;
+	BIF_ERROR(BIF_P, BADKEY);
     }
-    BIF_ERROR(BIF_P, BADARG);
 }
 
 
@@ -1723,7 +1732,8 @@ BIF_RETTYPE maps_values_1(BIF_ALIST_1) {
     } else if (is_hashmap(BIF_ARG_1)) {
 	BIF_RET(hashmap_values(BIF_P, BIF_ARG_1));
     }
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_P->fvalue = BIF_ARG_1;
+    BIF_ERROR(BIF_P, BADMAP);
 }
 
 static Eterm hashmap_to_list(Process *p, Eterm node) {
@@ -2546,8 +2556,12 @@ Uint hashmap_over_estimated_heap_size(Uint k)
 BIF_RETTYPE erts_debug_map_info_1(BIF_ALIST_1) {
     if (is_hashmap(BIF_ARG_1)) {
 	BIF_RET(hashmap_info(BIF_P,BIF_ARG_1));
+    } else if (is_flatmap(BIF_ARG_1)) {
+	BIF_ERROR(BIF_P, BADARG);
+    } else {
+	BIF_P->fvalue = BIF_ARG_1;
+	BIF_ERROR(BIF_P, BADMAP);
     }
-    BIF_ERROR(BIF_P, BADARG);
 }
 
 /*
@@ -2560,8 +2574,12 @@ BIF_RETTYPE erts_internal_map_to_tuple_keys_1(BIF_ALIST_1) {
     if (is_flatmap(BIF_ARG_1)) {
 	flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1);
 	BIF_RET(mp->keys);
+    } else if (is_hashmap(BIF_ARG_1)) {
+	BIF_ERROR(BIF_P, BADARG);
+    } else {
+	BIF_P->fvalue = BIF_ARG_1;
+	BIF_ERROR(BIF_P, BADMAP);
     }
-    BIF_ERROR(BIF_P, BADARG);
 }
 
 /*
@@ -2589,7 +2607,8 @@ BIF_RETTYPE erts_internal_map_type_1(BIF_ALIST_1) {
                 erl_exit(1, "bad header");
         }
     }
-    BIF_ERROR(BIF_P, BADARG);
+    BIF_P->fvalue = BIF_ARG_1;
+    BIF_ERROR(BIF_P, BADMAP);
 }
 
 /*
@@ -2629,8 +2648,12 @@ BIF_RETTYPE erts_internal_map_hashmap_children_1(BIF_ALIST_1) {
         hp = HAlloc(BIF_P, 2*sz);
         while(sz--) { res = CONS(hp, *ptr++, res); hp += 2; }
         BIF_RET(res);
+    } else if (is_flatmap(BIF_ARG_1)) {
+	BIF_ERROR(BIF_P, BADARG);
+    } else {
+	BIF_P->fvalue = BIF_ARG_1;
+	BIF_ERROR(BIF_P, BADMAP);
     }
-    BIF_ERROR(BIF_P, BADARG);
 }
 
 
diff --git a/erts/emulator/beam/erl_term.h b/erts/emulator/beam/erl_term.h
index cff012d5d1..602aab46dc 100644
--- a/erts/emulator/beam/erl_term.h
+++ b/erts/emulator/beam/erl_term.h
@@ -1027,6 +1027,7 @@ _ET_DECLARE_CHECKED(struct erl_node_*,external_ref_node,Eterm)
 
 #define is_map_header(x)       (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_MAP)
 #define is_map(x)              (is_boxed((x)) && is_map_header(*boxed_val(x)))
+#define is_not_map(x)          (!is_map(x))
 #define is_map_rel(RTERM,BASE) is_map(rterm2wterm(RTERM,BASE))
 
 /* number tests */
diff --git a/erts/emulator/beam/error.h b/erts/emulator/beam/error.h
index ddc2c1396d..e63967adb6 100644
--- a/erts/emulator/beam/error.h
+++ b/erts/emulator/beam/error.h
@@ -140,7 +140,13 @@
 #define EXC_NOTSUP		((17 << 8) | EXC_ERROR)
 					/* Not supported */
 
-#define NUMBER_EXIT_CODES 18	/* The number of exit code indices */
+#define EXC_BADMAP		((18 << 8) | EXC_ERROR)
+					/* Bad map */
+
+#define EXC_BADKEY		((19 << 8) | EXC_ERROR)
+					/* Bad key in map */
+
+#define NUMBER_EXIT_CODES 20	/* The number of exit code indices */
 
 /*
  * Internal pseudo-error codes.
@@ -152,6 +158,8 @@
  */
 #define BADARG EXC_BADARG
 #define BADARITH EXC_BADARITH
+#define BADKEY EXC_BADKEY
+#define BADMAP EXC_BADMAP
 #define BADMATCH EXC_BADMATCH
 #define SYSTEM_LIMIT EXC_SYSTEM_LIMIT
 
diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab
index d3649080dc..9bdc9cb88d 100644
--- a/erts/emulator/beam/ops.tab
+++ b/erts/emulator/beam/ops.tab
@@ -1473,79 +1473,67 @@ apply_last I P
 # Map instructions in R17.
 #
 
-put_map_assoc F n Dst Live Size Rest=* => new_map F Dst Live Size Rest
-put_map_assoc F Src=s Dst Live Size Rest=* => \
+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
+
+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) => \
+   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
-put_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
-put_map_exact F n Dst Live Size Rest=* => new_map F Dst Live Size Rest
-put_map_exact F Src=s Dst Live Size Rest=* => \
+
+sorted_put_map_exact F Src=s Dst Live Size Rest=* => \
 	      update_map_exact F Src Dst Live Size Rest
-put_map_exact F Src Dst Live Size Rest=* => \
+sorted_put_map_exact F Src Dst Live Size Rest=* => \
 	      move Src x | update_map_exact F x Dst Live Size Rest
 
-new_map j d I I
+new_map d I I
 update_map_assoc j s d I I
 update_map_exact j s d I I
 
-is_map Fail Literal=q => move Literal x | is_map Fail x
-is_map Fail c => jump Fail
+is_map Fail Lit=q | literal_is_map(Lit) =>
+is_map Fail cq => jump Fail
 
 %macro: is_map IsMap -fail_action
 is_map f r
 is_map f x
 is_map f y
 
-## Transform has_map_field(s) #{ K1 := _, K2 := _ }
-
-has_map_field/3
-
-has_map_fields Fail Src Size=u==1 Rest=* => gen_has_map_field(Fail,Src,Size,Rest)
-has_map_fields Fail Src Size Rest=* => i_has_map_fields Fail Src Size Rest
+## Transform has_map_fields #{ K1 := _, K2 := _ } to has_map_elements
 
-i_has_map_fields f s I
-
-has_map_field Fail Src=rxy Key=arxy => i_has_map_field Fail Src Key
-has_map_field Fail Src Key => move Key x | i_has_map_field Fail Src x
-
-%macro: i_has_map_field HasMapField -fail_action
-i_has_map_field f r a
-i_has_map_field f x a
-i_has_map_field f y a
-i_has_map_field f r r
-i_has_map_field f x r
-i_has_map_field f y r
-i_has_map_field f r x
-i_has_map_field f x x
-i_has_map_field f y x
-i_has_map_field f r y
-i_has_map_field f x y
-i_has_map_field f y y
+has_map_fields Fail Src Size Rest=* => \
+   gen_has_map_fields(Fail, Src, Size, Rest)
 
 ## Transform get_map_elements(s) #{ K1 := V1, K2 := V2 }
 
-get_map_element/4
-
-get_map_elements Fail Src=rxy Size=u==2 Rest=* => gen_get_map_element(Fail,Src,Size,Rest)
-get_map_elements Fail Src Size Rest=* => i_get_map_elements Fail Src Size Rest
+get_map_elements Fail Src=rxy Size=u==2 Rest=* => \
+    gen_get_map_element(Fail, Src, Size, Rest)
+get_map_elements Fail Src Size Rest=* | map_key_sort(Size, Rest) => \
+   gen_get_map_elements(Fail, Src, Size, Rest)
 
 i_get_map_elements f s I
 
-get_map_element Fail Src=rxy Key=ax Dst => i_get_map_element Fail Src Key Dst
-get_map_element Fail Src=rxy Key=rycq Dst => \
+i_get_map_element Fail Src=rxy Key=ry Dst => \
     move Key x | i_get_map_element Fail Src x Dst
-get_map_element Fail Src Key Dst => jump Fail
+
+%macro: i_get_map_element_hash GetMapElementHash -fail_action
+i_get_map_element_hash f r c I r
+i_get_map_element_hash f x c I r
+i_get_map_element_hash f y c I r
+i_get_map_element_hash f r c I x
+i_get_map_element_hash f x c I x
+i_get_map_element_hash f y c I x
+i_get_map_element_hash f r c I y
+i_get_map_element_hash f x c I y
+i_get_map_element_hash f y c I y
 
 %macro: i_get_map_element GetMapElement -fail_action
-i_get_map_element f r a r
-i_get_map_element f x a r
-i_get_map_element f y a r
-i_get_map_element f r a x
-i_get_map_element f x a x
-i_get_map_element f y a x
-i_get_map_element f r a y
-i_get_map_element f x a y
-i_get_map_element f y a y
 i_get_map_element f r x r
 i_get_map_element f x x r
 i_get_map_element f y x r