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

34 files changed, 907 insertions, 477 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
diff --git a/erts/emulator/test/Makefile b/erts/emulator/test/Makefile
index dd2e2cb504..4dc4b5027d 100644
--- a/erts/emulator/test/Makefile
+++ b/erts/emulator/test/Makefile
@@ -125,7 +125,8 @@ NO_OPT= bs_bincomp \
 	bs_match_tail \
 	bs_match_misc \
 	bs_utf \
-	guard
+	guard \
+	map
 
 NATIVE= hibernate
 
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index ad8411cd68..39549282c0 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -38,6 +38,7 @@
 	t_map_equal/1,
 	t_map_compare/1,
 	t_map_size/1,
+	t_is_map/1,
 
 	%% Specific Map BIFs
 	t_bif_map_get/1,
@@ -74,7 +75,12 @@
 	t_pdict/1,
 	t_ets/1,
 	t_dets/1,
-	t_tracing/1
+	t_tracing/1,
+
+	%% instruction-level tests
+	t_has_map_fields/1,
+	y_regs/1,
+	badmap_17/1
     ]).
 
 -include_lib("stdlib/include/ms_transform.hrl").
@@ -114,7 +120,7 @@ all() -> [
 
 	%% erlang
 	t_erlang_hash, t_map_encode_decode,
-	t_map_size,
+	t_map_size, t_is_map,
 
 	%% non specific BIF related
 	t_bif_build_and_check,
@@ -131,7 +137,12 @@ all() -> [
         t_erts_internal_hash,
 	t_pdict,
 	t_ets,
-	t_tracing
+	t_tracing,
+
+	%% instruction-level tests
+	t_has_map_fields,
+	y_regs,
+	badmap_17
     ].
 
 groups() -> [].
@@ -157,6 +168,9 @@ t_build_and_match_literals(Config) when is_list(Config) ->
     #{1:=a,2:=b,3:="c","4":="d",<<"5">>:=<<"e">>,{"6",7}:="f",8:=g} =
 	id(#{1=>a,2=>b,3=>"c","4"=>"d",<<"5">>=><<"e">>,{"6",7}=>"f",8=>g}),
 
+    #{[]:=a,42.0:=b,x:={x,y},[a,b]:=list} =
+         id(#{[]=>a,42.0=>b,x=>{x,y},[a,b]=>list}),
+
     #{<<"hi all">> := 1} = id(#{<<"hi",32,"all">> => 1}),
 
     #{a:=X,a:=X=3,b:=4} = id(#{a=>3,b=>4}), % weird but ok =)
@@ -664,9 +678,10 @@ t_map_size(Config) when is_list(Config) ->
     N  = map_size(maps:from_list([{float(I),I}||I<-Is])),
 
     %% Error cases.
-    {'EXIT',{badarg,_}} = (catch map_size([])),
-    {'EXIT',{badarg,_}} = (catch map_size(<<1,2,3>>)),
-    {'EXIT',{badarg,_}} = (catch map_size(1)),
+    do_badmap(fun(T) ->
+                    {'EXIT',{{badmap,T},_}} =
+                      (catch map_size(T))
+              end),
     ok.
 
 build_and_check_size([K|Ks],N,M0) ->
@@ -680,6 +695,17 @@ build_and_check_size([],N,M) ->
 map_is_size(M,N) when map_size(M) =:= N -> true;
 map_is_size(_,_) -> false.
 
+t_is_map(Config) when is_list(Config) ->
+    true = is_map(#{}),
+    true = is_map(#{a=>1}),
+    false = is_map({a,b}),
+    false = is_map(x),
+    if is_map(#{}) -> ok end,
+    if is_map(#{b=>1}) -> ok end,
+    if not is_map([1,2,3]) -> ok end,
+    if not is_map(x) -> ok end,
+    ok.
+
 % test map updates without matching
 t_update_literals_large(Config) when is_list(Config) ->
     Map = id(#{ 10=>id(a0),20=>b0,30=>id("c0"),"40"=>"d0",<<"50">>=>id("e0"),{["00"]}=>"10",
@@ -855,9 +881,11 @@ t_update_map_expressions(Config) when is_list(Config) ->
     #{ "aa" := {$a,$a}, "ac":=41, "dc":=42 } =
         (maps:from_list([{[K1,K2],{K1,K2}}|| K1 <- Ks, K2 <- Ks]))#{ "ac" := 41, "dc" => 42 },
 
-    %% Error cases, FIXME: should be 'badmap'?
-    {'EXIT',{badarg,_}} = (catch (id(<<>>))#{ a := 42, b => 2 }),
-    {'EXIT',{badarg,_}} = (catch (id([]))#{ a := 42, b => 2 }),
+    %% Error cases.
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},_}} =
+			  (catch (T)#{a:=42,b=>2})
+	      end),
     ok.
 
 t_update_assoc(Config) when is_list(Config) ->
@@ -872,8 +900,10 @@ t_update_assoc(Config) when is_list(Config) ->
     M2 = M0#{3.0:=wrong,3.0=>new},
 
     %% Errors cases.
-    BadMap = id(badmap),
-    {'EXIT',{badarg,_}} = (catch BadMap#{nonexisting=>val}),
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},_}} =
+			  (catch T#{nonexisting=>val})
+	      end),
     ok.
 
 
@@ -940,9 +970,6 @@ t_update_assoc_large(Config) when is_list(Config) ->
     #{10:=a0,20:=b0,13.0:=new,"40":="d0",<<"50">>:="e0"} = M2,
     M2 = M0#{13.0:=wrong,13.0=>new},
 
-    %% Errors cases.
-    BadMap = id(badmap),
-    {'EXIT',{badarg,_}} = (catch BadMap#{nonexisting=>M0}),
     ok.
 
 t_update_exact(Config) when is_list(Config) ->
@@ -964,12 +991,17 @@ t_update_exact(Config) when is_list(Config) ->
 	1 := update2, 1.0 := new_val2, 1.0 => new_val3,
 	1.0 => new_val4 },
 
-
     %% Errors cases.
-    {'EXIT',{badarg,_}} = (catch M0#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{1.0:=v,1.0=>v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42.0:=v,42:=v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},_}} =
+			  (catch T#{nonexisting=>val})
+	      end),
+    Empty = id(#{}),
+    {'EXIT',{{badkey,nonexisting},_}} = (catch Empty#{nonexisting:=val}),
+    {'EXIT',{{badkey,nonexisting},_}} = (catch M0#{nonexisting:=val}),
+    {'EXIT',{{badkey,1.0},_}} = (catch M0#{1.0:=v,1.0=>v2}),
+    {'EXIT',{{badkey,42},_}} = (catch M0#{42.0:=v,42:=v2}),
+    {'EXIT',{{badkey,42.0},_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
 
     ok.
 
@@ -1048,10 +1080,10 @@ t_update_exact_large(Config) when is_list(Config) ->
     M2 = M0#{13.0=>wrong,13.0:=new},
 
     %% Errors cases.
-    {'EXIT',{badarg,_}} = (catch M0#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{1.0:=v,1.0=>v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42.0:=v,42:=v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+    {'EXIT',{{badkey,nonexisting},_}} = (catch M0#{nonexisting:=val}),
+    {'EXIT',{{badkey,1.0},_}} = (catch M0#{1.0:=v,1.0=>v2}),
+    {'EXIT',{{badkey,42},_}} = (catch M0#{42.0:=v,42:=v2}),
+    {'EXIT',{{badkey,42.0},_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
 
     ok.
 
@@ -1743,12 +1775,17 @@ t_bif_map_get(Config) when is_list(Config) ->
     "tuple hi" = maps:get({1,1.0}, M1),
     "v3" = maps:get(<<"k2">>, M1),
 
-    %% error case
-    {'EXIT',{badarg, [{maps,get,_,_}|_]}} = (catch maps:get(a,[])),
-    {'EXIT',{badarg, [{maps,get,_,_}|_]}} = (catch maps:get(a,<<>>)),
-    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get({1,1}, #{{1,1.0} => "tuple"})),
-    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get(a,#{})),
-    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get(a,#{b=>1, c=>2})),
+    %% error cases
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},[{maps,get,_,_}|_]}} =
+			  (catch maps:get(a, T))
+	      end),
+
+    {'EXIT',{{badkey,{1,1}},[{maps,get,_,_}|_]}} =
+	(catch maps:get({1,1}, #{{1,1.0} => "tuple"})),
+    {'EXIT',{{badkey,a},[{maps,get,_,_}|_]}} = (catch maps:get(a, #{})),
+    {'EXIT',{{badkey,a},[{maps,get,_,_}|_]}} =
+	(catch maps:get(a, #{b=>1, c=>2})),
     ok.
 
 t_bif_map_find(Config) when is_list(Config) ->
@@ -1781,8 +1818,10 @@ t_bif_map_find(Config) when is_list(Config) ->
     error = maps:find(1, #{ 1.0  => "float"}),
     error = maps:find({1.0,1}, #{ a=>a, {1,1.0} => "tuple hi"}), % reverse types in tuple key
 
-    {'EXIT',{badarg,[{maps,find,_,_}|_]}} = (catch maps:find(a,id([]))),
-    {'EXIT',{badarg,[{maps,find,_,_}|_]}} = (catch maps:find(a,id(<<>>))),
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},[{maps,find,_,_}|_]}} =
+			  (catch maps:find(a, T))
+	      end),
     ok.
 
 
@@ -1807,8 +1846,10 @@ t_bif_map_is_key(Config) when is_list(Config) ->
     false = maps:is_key(1.0, maps:put(1, "number", M1)),
 
     %% error case
-    {'EXIT',{badarg,[{maps,is_key,_,_}|_]}} = (catch maps:is_key(a,id([]))),
-    {'EXIT',{badarg,[{maps,is_key,_,_}|_]}} = (catch maps:is_key(a,id(<<>>))),
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},[{maps,is_key,_,_}|_]}} =
+			  (catch maps:is_key(a, T))
+	      end),
     ok.
 
 t_bif_map_keys(Config) when is_list(Config) ->
@@ -1822,11 +1863,10 @@ t_bif_map_keys(Config) when is_list(Config) ->
     [4,int,"hi",<<"key">>] = lists:sort(maps:keys(M1)),
 
     %% error case
-    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(1 bsl 65 + 3)),
-    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(154)),
-    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(atom)),
-    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys([])),
-    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(<<>>)),
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},[{maps,keys,_,_}|_]}} =
+			  (catch maps:keys(T))
+	      end),
     ok.
 
 t_bif_map_new(Config) when is_list(Config) ->
@@ -1898,9 +1938,14 @@ t_bif_map_merge(Config) when is_list(Config) ->
     ok = check_keys_exist(Ks1 ++ Ks2, M11),
 
     %% error case
-    {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge((1 bsl 65 + 3), <<>>)),
-    {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(<<>>, id(#{ a => 1}))),
-    {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(id(#{ a => 2}), <<>> )),
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},[{maps,merge,_,_}|_]}} =
+			  (catch maps:merge(#{}, T)),
+		      {'EXIT',{{badmap,T},[{maps,merge,_,_}|_]}} =
+			  (catch maps:merge(T, #{})),
+		      {'EXIT',{{badmap,T},[{maps,merge,_,_}|_]}} =
+			  (catch maps:merge(T, T))
+	      end),
     ok.
 
 
@@ -1939,11 +1984,10 @@ t_bif_map_put(Config) when is_list(Config) ->
     true = is_members([number,wat,3,"hello",<<"other value">>],maps:values(M6)),
 
     %% error case
-    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,1 bsl 65 + 3)),
-    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,154)),
-    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,atom)),
-    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,[])),
-    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,<<>>)),
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},[{maps,put,_,_}|_]}} =
+			  (catch maps:put(1, a, T))
+	      end),
     ok.
 
 is_members(Ks,Ls) when length(Ks) =/= length(Ls) -> false;
@@ -1986,11 +2030,10 @@ t_bif_map_remove(Config) when is_list(Config) ->
     #{ "hi" := "hello", int := 3, 4 := number} = maps:remove(18446744073709551629,maps:remove(<<"key">>,M0)),
 
     %% error case
-    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(a,1 bsl 65 + 3)),
-    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(1,154)),
-    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(a,atom)),
-    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(1,[])),
-    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(a,<<>>)),
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},[{maps,remove,_,_}|_]}} =
+	(catch maps:remove(a, T))
+	      end),
      ok.
 
 t_bif_map_update(Config) when is_list(Config) ->
@@ -2013,10 +2056,10 @@ t_bif_map_update(Config) when is_list(Config) ->
 	4 := number, 18446744073709551629 := wazzup} = maps:update(18446744073709551629, wazzup, M0),
 
     %% error case
-    {'EXIT',{badarg,[{maps,update,_,_}|_]}} = (catch maps:update(1,none,{})),
-    {'EXIT',{badarg,[{maps,update,_,_}|_]}} = (catch maps:update(1,none,<<"value">>)),
-    {'EXIT',{badarg,[{maps,update,_,_}|_]}} = (catch maps:update(5,none,M0)),
-
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},[{maps,update,_,_}|_]}} =
+			  (catch maps:update(1, none, T))
+	      end),
     ok.
 
 
@@ -2043,10 +2086,10 @@ t_bif_map_values(Config) when is_list(Config) ->
     true = is_members([number,3,"hello2",<<"value2">>]++Vs,maps:values(M5)),
 
     %% error case
-    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(1 bsl 65 + 3)),
-    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(atom)),
-    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values([])),
-    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(<<>>)),
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},[{maps,values,_,_}|_]}} =
+			  (catch maps:values(T))
+	      end),
     ok.
 
 t_erlang_hash(Config) when is_list(Config) ->
@@ -2245,8 +2288,10 @@ t_bif_map_to_list(Config) when is_list(Config) ->
 				  <<"hi">>=>v6,3=>v7,"hi"=>v8,hi=>v9,{hi,3}=>v10})),
 
     %% error cases
-    {'EXIT', {badarg,_}} = (catch maps:to_list(id(a))),
-    {'EXIT', {badarg,_}} = (catch maps:to_list(id(42))),
+    do_badmap(fun(T) ->
+		      {'EXIT', {{badmap,T},_}} =
+			  (catch maps:to_list(T))
+	      end),
     ok.
 
 
@@ -2703,5 +2748,111 @@ trace_collector(Msg,Parent) ->
     Parent ! Msg,
     Parent.
 
+t_has_map_fields(Config) when is_list(Config) ->
+    true = has_map_fields_1(#{one=>1}),
+    true = has_map_fields_1(#{one=>1,two=>2}),
+    false = has_map_fields_1(#{two=>2}),
+    false = has_map_fields_1(#{}),
+
+    true = has_map_fields_2(#{c=>1,b=>2,a=>3}),
+    true = has_map_fields_2(#{c=>1,b=>2,a=>3,x=>42}),
+    false = has_map_fields_2(#{b=>2,c=>1}),
+    false = has_map_fields_2(#{x=>y}),
+    false = has_map_fields_2(#{}),
+
+    true = has_map_fields_3(#{c=>1,b=>2,a=>3}),
+    true = has_map_fields_3(#{c=>1,b=>2,a=>3,[]=>42}),
+    true = has_map_fields_3(#{b=>2,a=>3,[]=>42,42.0=>43}),
+    true = has_map_fields_3(#{a=>3,[]=>42,42.0=>43}),
+    true = has_map_fields_3(#{[]=>42,42.0=>43}),
+    false = has_map_fields_3(#{b=>2,c=>1}),
+    false = has_map_fields_3(#{[]=>y}),
+    false = has_map_fields_3(#{42.0=>x,a=>99}),
+    false = has_map_fields_3(#{}),
+
+    ok.
+
+has_map_fields_1(#{one:=_}) -> true;
+has_map_fields_1(#{}) -> false.
+
+has_map_fields_2(#{a:=_,b:=_,c:=_}) -> true;
+has_map_fields_2(#{}) -> false.
+
+has_map_fields_3(#{a:=_,b:=_}) -> true;
+has_map_fields_3(#{[]:=_,42.0:=_}) -> true;
+has_map_fields_3(#{}) -> false.
+
+y_regs(Config) when is_list(Config) ->
+    Val = [length(Config)],
+    Map0 = y_regs_update(#{}, Val),
+    Map2 = y_regs_update(Map0, Val),
+
+    Map3 = maps:from_list([{I,I*I} || I <- lists:seq(1, 100)]),
+    Map4 = y_regs_update(Map3, Val),
+
+    true = is_map(Map2) andalso is_map(Map4),
+
+    ok.
+
+y_regs_update(Map0, Val0) ->
+    Val1 = {t,Val0},
+    K1 = id({key,1}),
+    K2 = id({key,2}),
+    Map1 = Map0#{K1=>K1,
+		 a=>Val0,b=>Val0,c=>Val0,d=>Val0,e=>Val0,
+		 f=>Val0,g=>Val0,h=>Val0,i=>Val0,j=>Val0,
+		 k=>Val0,l=>Val0,m=>Val0,n=>Val0,o=>Val0,
+		 p=>Val0,q=>Val0,r=>Val0,s=>Val0,t=>Val0,
+		 u=>Val0,v=>Val0,w=>Val0,x=>Val0,y=>Val0,
+		 z=>Val0,
+		 aa=>Val0,ab=>Val0,ac=>Val0,ad=>Val0,ae=>Val0,
+		 af=>Val0,ag=>Val0,ah=>Val0,ai=>Val0,aj=>Val0,
+		 ak=>Val0,al=>Val0,am=>Val0,an=>Val0,ao=>Val0,
+		 ap=>Val0,aq=>Val0,ar=>Val0,as=>Val0,at=>Val0,
+		 au=>Val0,av=>Val0,aw=>Val0,ax=>Val0,ay=>Val0,
+		 az=>Val0,
+		 K2=>[a,b,c]},
+    Map2 = Map1#{K1=>K1,
+		 a:=Val1,b:=Val1,c:=Val1,d:=Val1,e:=Val1,
+		 f:=Val1,g:=Val1,h:=Val1,i:=Val1,j:=Val1,
+		 k:=Val1,l:=Val1,m:=Val1,n:=Val1,o:=Val1,
+		 p:=Val1,q:=Val1,r:=Val1,s:=Val1,t:=Val1,
+		 u:=Val1,v:=Val1,w:=Val1,x:=Val1,y:=Val1,
+		 z:=Val1,
+		 aa:=Val1,ab:=Val1,ac:=Val1,ad:=Val1,ae:=Val1,
+		 af:=Val1,ag:=Val1,ah:=Val1,ai:=Val1,aj:=Val1,
+		 ak:=Val1,al:=Val1,am:=Val1,an:=Val1,ao:=Val1,
+		 ap:=Val1,aq:=Val1,ar:=Val1,as:=Val1,at:=Val1,
+		 au:=Val1,av:=Val1,aw:=Val1,ax:=Val1,ay:=Val1,
+		 az:=Val1,
+		 K2=>[a,b,c]},
+
+    %% Traverse the maps to validate them.
+    _ = erlang:phash2({Map1,Map2}, 100000),
+
+    _ = id({K1,K2,Val0,Val1}),			%Force use of Y registers.
+    Map2.
+
+do_badmap(Test) ->
+    Terms = [Test,fun erlang:abs/1,make_ref(),self(),0.0/id(-1),
+	     <<0:1024>>,<<1:1>>,<<>>,<<1,2,3>>,
+	     [],{a,b,c},[a,b],atom,10.0,42,(1 bsl 65) + 3],
+    [Test(T) || T <- Terms].
+
+%% Test that a module compiled with the OTP 17 compiler will
+%% generate the correct 'badmap' exception.
+badmap_17(Config) ->
+    case ?MODULE of
+	map_SUITE -> do_badmap_17(Config);
+	_ -> {skip,"Run in map_SUITE"}
+    end.
+
+do_badmap_17(Config) ->
+    Mod = badmap_17,
+    DataDir = test_server:lookup_config(data_dir, Config),
+    Beam = filename:join(DataDir, Mod),
+    {module,Mod} = code:load_abs(Beam),
+    do_badmap(fun Mod:update/1).
+
 %% Use this function to avoid compile-time evaluation of an expression.
 id(I) -> I.
diff --git a/erts/emulator/test/map_SUITE_data/badmap_17.beam b/erts/emulator/test/map_SUITE_data/badmap_17.beam
new file mode 100644
index 0000000000..277fc34b94
--- /dev/null
+++ 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
new file mode 100644
index 0000000000..0ec65e0e33
--- /dev/null
+++ b/erts/emulator/test/map_SUITE_data/badmap_17.erl
@@ -0,0 +1,26 @@
+-module(badmap_17).
+-export([update/1]).
+
+%% Compile this source file with OTP 17.
+
+update(Map) ->
+    try
+	update_1(Map),
+	error(update_did_not_fail)
+    catch
+	error:{badmap,Map} ->
+	    ok
+    end,
+    try
+	update_2(Map),
+	error(update_did_not_fail)
+    catch
+	error:{badmap,Map} ->
+	    ok
+    end.
+
+update_1(M) ->
+    M#{a=>42}.
+
+update_2(M) ->
+    M#{a:=42}.
diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index 4d4536b79c..c55919dc73 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -667,7 +667,7 @@ valfun_4({test,test_arity,{f,Lbl},[Tuple,Sz]}, Vst) when is_integer(Sz) ->
     set_type_reg({tuple,Sz}, Tuple, branch_state(Lbl, Vst));
 valfun_4({test,has_map_fields,{f,Lbl},Src,{list,List}}, Vst) ->
     assert_type(map, Src, Vst),
-    assert_strict_literal_termorder(List),
+    assert_unique_map_keys(List),
     branch_state(Lbl, Vst);
 valfun_4({test,is_map,{f,Lbl},[Src]}, Vst0) ->
     Vst = branch_state(Lbl, Vst0),
@@ -774,7 +774,7 @@ verify_get_map(Fail, Src, List, Vst0) ->
     assert_type(map, Src, Vst0),
     Vst1 = branch_state(Fail, Vst0),
     Keys = extract_map_keys(List),
-    assert_strict_literal_termorder(Keys),
+    assert_unique_map_keys(Keys),
     verify_get_map_pair(List,Vst0,Vst1).
 
 extract_map_keys([Key,_Val|T]) ->
@@ -794,6 +794,8 @@ verify_put_map(Fail, Src, Dst, Live, List, Vst0) ->
     Vst1 = heap_alloc(0, Vst0),
     Vst2 = branch_state(Fail, Vst1),
     Vst = prune_x_regs(Live, Vst2),
+    Keys = extract_map_keys(List),
+    assert_unique_map_keys(Keys),
     set_type_reg(map, Dst, Vst).
 
 %%
@@ -1007,29 +1009,23 @@ assert_freg_set(Fr, _) -> error({bad_source,Fr}).
 
 %% A single item list may be either a list or a register.
 %%
-%% A list with more than item must contain literals in
-%% ascending term order.
+%% A list with more than item must contain unique literals.
 %%
 %% An empty list is not allowed.
 
-assert_strict_literal_termorder([]) ->
+assert_unique_map_keys([]) ->
     %% There is no reason to use the get_map_elements and
     %% has_map_fields instructions with empty lists.
     error(empty_field_list);
-assert_strict_literal_termorder([_]) ->
+assert_unique_map_keys([_]) ->
     ok;
-assert_strict_literal_termorder([_,_|_]=Ls) ->
+assert_unique_map_keys([_,_|_]=Ls) ->
     Vs = [get_literal(L) || L <- Ls],
-    case check_strict_value_termorder(Vs) of
-	true ->  ok;
-	false -> error(not_strict_order)
+    case length(Vs) =:= sets:size(sets:from_list(Vs)) of
+	true -> ok;
+	false -> error(keys_not_unique)
     end.
 
-check_strict_value_termorder([V1|[V2|_]=Vs]) ->
-    erts_internal:cmp_term(V1, V2) < 0 andalso
-	check_strict_value_termorder(Vs);
-check_strict_value_termorder([_]) -> true.
-
 %%%
 %%% New binary matching instructions.
 %%%
diff --git a/lib/compiler/src/sys_core_fold.erl b/lib/compiler/src/sys_core_fold.erl
index 0d020578f5..beab2ce897 100644
--- a/lib/compiler/src/sys_core_fold.erl
+++ b/lib/compiler/src/sys_core_fold.erl
@@ -70,7 +70,8 @@
 -export([module/2,format_error/1]).
 
 -import(lists, [map/2,foldl/3,foldr/3,mapfoldl/3,all/2,any/2,
-		reverse/1,reverse/2,member/2,nth/2,flatten/1,unzip/1]).
+		reverse/1,reverse/2,member/2,nth/2,flatten/1,
+		unzip/1,keyfind/3]).
 
 -import(cerl, [ann_c_cons/3,ann_c_map/3,ann_c_tuple/2]).
 
@@ -1624,12 +1625,11 @@ eval_case(Case, _) -> Case.
 
 eval_case_warn(#c_primop{anno=Anno,
 			 name=#c_literal{val=match_fail},
-			 args=[#c_literal{val=Reason}]}=Core)
-  when is_atom(Reason) ->
-    case member(eval_failure, Anno) of
+			 args=[_]}=Core) ->
+    case keyfind(eval_failure, 1, Anno) of
 	false ->
 	    ok;
-	true ->
+	{eval_failure,Reason} ->
 	    %% Example: M = not_map, M#{k:=v}
 	    add_warning(Core, {eval_failure,Reason})
     end;
diff --git a/lib/compiler/src/v3_codegen.erl b/lib/compiler/src/v3_codegen.erl
index 7eec9dd62b..40235d6767 100644
--- a/lib/compiler/src/v3_codegen.erl
+++ b/lib/compiler/src/v3_codegen.erl
@@ -1549,11 +1549,8 @@ set_cg([{var,R}], {map,Op,Map,Es}, Le, Vdb, Bef,
     SrcReg = cg_reg_arg(Map,Int0),
     Line = line(Le#l.a),
 
-    %% The instruction needs to store keys in term sorted order
-    %% All keys has to be unique here
-    Pairs = map_pair_strip_and_termsort(Es),
-
     %% fetch registers for values to be put into the map
+    Pairs = [{K,V} || {_,K,V} <- Es],
     List = flatmap(fun({K,V}) -> [K,cg_reg_arg(V,Int0)] end, Pairs),
 
     Live = max_reg(Bef#sr.reg),
@@ -1580,16 +1577,6 @@ set_cg([{var,R}], Con, Le, Vdb, Bef, St) ->
 	  end,
     {Ais,clear_dead(Int, Le#l.i, Vdb),St}.
 
-map_pair_strip_and_termsort(Es) ->
-    %% format in
-    %%    [{map_pair,K,V}]
-    %% where K is for example {integer, 1} and we want to sort on 1.
-    Ls = [{K,V}||{_,K,V}<-Es],
-    lists:sort(fun ({{_,A},_}, {{_,B},_}) -> erts_internal:cmp_term(A,B) =< 0;
-                   ({nil,_},   {{_,B},_}) -> [] =< B;
-                   ({{_,A},_}, {nil,_})   -> A =< []
-               end, Ls).
-
 %%%
 %%% Code generation for constructing binaries.
 %%%
diff --git a/lib/compiler/src/v3_core.erl b/lib/compiler/src/v3_core.erl
index c954d21e59..ed7b55df07 100644
--- a/lib/compiler/src/v3_core.erl
+++ b/lib/compiler/src/v3_core.erl
@@ -538,19 +538,8 @@ expr({tuple,L,Es0}, St0) ->
     {annotate_tuple(A, Es1, St1),Eps,St1};
 expr({map,L,Es0}, St0) ->
     map_build_pairs(#c_literal{val=#{}}, Es0, full_anno(L, St0), St0);
-expr({map,L,M0,Es0}, St0) ->
-    try expr_map(M0,Es0,lineno_anno(L, St0),St0) of
-	{_,_,_}=Res -> Res
-    catch
-	throw:{bad_map,Warning} ->
-	    St = add_warning(L, Warning, St0),
-	    LineAnno = lineno_anno(L, St),
-	    As = [#c_literal{anno=LineAnno,val=badarg}],
-	    {#icall{anno=#a{anno=LineAnno},	%Must have an #a{}
-		    module=#c_literal{anno=LineAnno,val=erlang},
-		    name=#c_literal{anno=LineAnno,val=error},
-		    args=As},[],St}
-    end;
+expr({map,L,M,Es}, St) ->
+    expr_map(M, Es, L, St);
 expr({bin,L,Es0}, St0) ->
     try expr_bin(Es0, full_anno(L, St0), St0) of
 	{_,_,_}=Res -> Res
@@ -758,11 +747,14 @@ make_bool_switch_guard(L, E, V, T, F) ->
       {clause,NegL,[V],[],[V]}
      ]}.
 
-expr_map(M0, Es0, A, St0) ->
+expr_map(M0, Es0, L, St0) ->
     {M1,Eps0,St1} = safe(M0, St0),
+    Badmap = badmap_term(M1, St1),
+    A = lineno_anno(L, St1),
+    Fc = fail_clause([], [{eval_failure,badmap}|A], Badmap),
     case is_valid_map_src(M1) of
 	true ->
-	    {M2,Eps1,St2} = map_build_pairs(M1, Es0, A, St1),
+	    {M2,Eps1,St2} = map_build_pairs(M1, Es0, full_anno(L, St1), St1),
 	    M3 = case Es0 of
 		     [] -> M1;
 		     [_|_] -> M2
@@ -775,13 +767,23 @@ expr_map(M0, Es0, A, St0) ->
 			           name=#c_literal{anno=A,val=is_map},
 				   args=[M1]}],
 		     body=[M3]}],
-	    Fc = fail_clause([], [eval_failure|A], #c_literal{val=badarg}),
 	    Eps = Eps0 ++ Eps1,
 	    {#icase{anno=#a{anno=A},args=[],clauses=Cs,fc=Fc},Eps,St2};
 	false ->
-	    throw({bad_map,bad_map})
+	    %% Not a map source. The update will always fail.
+	    St2 = add_warning(L, badmap, St1),
+	    #iclause{body=[Fail]} = Fc,
+	    {Fail,Eps0,St2}
     end.
 
+badmap_term(_Map, #core{in_guard=true}) ->
+    %% The code generator cannot handle complex error reasons
+    %% in guards. But the exact error reason does not matter anyway
+    %% since it is not user-visible.
+    #c_literal{val=badmap};
+badmap_term(Map, #core{in_guard=false}) ->
+    #c_tuple{es=[#c_literal{val=badmap},Map]}.
+
 map_build_pairs(Map, Es0, Ann, St0) ->
     {Es,Pre,St1} = map_build_pairs_1(Es0, St0),
     {ann_c_map(Ann, Map, Es),Pre,St1}.
@@ -2395,7 +2397,7 @@ format_error(nomatch) ->
     "pattern cannot possibly match";
 format_error(bad_binary) ->
     "binary construction will fail because of a type mismatch";
-format_error(bad_map) ->
+format_error(badmap) ->
     "map construction will fail because of a type mismatch".
 
 add_warning(Line, Term, #core{ws=Ws,file=[{file,File}]}=St) when Line >= 0 ->
diff --git a/lib/compiler/test/beam_validator_SUITE.erl b/lib/compiler/test/beam_validator_SUITE.erl
index 1b1c7db0e8..551cf7661b 100644
--- a/lib/compiler/test/beam_validator_SUITE.erl
+++ b/lib/compiler/test/beam_validator_SUITE.erl
@@ -420,9 +420,9 @@ map_field_lists(Config) ->
     Errors = do_val(map_field_lists, Config),
     [{{map_field_lists,x,1},
       {{test,has_map_fields,{f,1},{x,0},
-	{list,[{atom,z},{atom,a}]}},
+	{list,[{atom,a},{atom,a}]}},
        5,
-       not_strict_order}},
+       keys_not_unique}},
      {{map_field_lists,y,1},
       {{test,has_map_fields,{f,3},{x,0},{list,[]}},
        5,
diff --git a/lib/compiler/test/beam_validator_SUITE_data/map_field_lists.S b/lib/compiler/test/beam_validator_SUITE_data/map_field_lists.S
index 9af68c82d4..5e7ccc1e5d 100644
--- a/lib/compiler/test/beam_validator_SUITE_data/map_field_lists.S
+++ b/lib/compiler/test/beam_validator_SUITE_data/map_field_lists.S
@@ -13,7 +13,7 @@
     {func_info,{atom,map_field_lists},{atom,x},1}.
   {label,2}.
     {test,is_map,{f,1},[{x,0}]}.
-    {test,has_map_fields,{f,1},{x,0},{list,[{atom,z},{atom,a}]}}.
+    {test,has_map_fields,{f,1},{x,0},{list,[{atom,a},{atom,a}]}}.
     {move,{atom,ok},{x,0}}.
     return.
 
diff --git a/lib/compiler/test/map_SUITE.erl b/lib/compiler/test/map_SUITE.erl
index 8870315084..8768e47b65 100644
--- a/lib/compiler/test/map_SUITE.erl
+++ b/lib/compiler/test/map_SUITE.erl
@@ -37,6 +37,7 @@
 	t_map_sort_literals/1,
 	t_map_size/1,
 	t_build_and_match_aliasing/1,
+	t_is_map/1,
 
 	%% variables
 	t_build_and_match_variables/1,
@@ -84,6 +85,7 @@ all() ->
 	t_map_sort_literals,
 	t_map_size,
 	t_build_and_match_aliasing,
+	t_is_map,
 
 	%% variables
 	t_build_and_match_variables,
@@ -667,14 +669,25 @@ t_map_size(Config) when is_list(Config) ->
     false = map_is_size(M#{ "c" => 2}, 2),
 
     %% Error cases.
-    {'EXIT',{badarg,_}} = (catch map_size([])),
-    {'EXIT',{badarg,_}} = (catch map_size(<<1,2,3>>)),
-    {'EXIT',{badarg,_}} = (catch map_size(1)),
+    {'EXIT',{{badmap,[]},_}} = (catch map_size([])),
+    {'EXIT',{{badmap,<<1,2,3>>},_}} = (catch map_size(<<1,2,3>>)),
+    {'EXIT',{{badmap,1},_}} = (catch map_size(1)),
     ok.
 
 map_is_size(M,N) when map_size(M) =:= N -> true;
 map_is_size(_,_) -> false.
 
+t_is_map(Config) when is_list(Config) ->
+    true = is_map(#{}),
+    true = is_map(#{a=>1}),
+    false = is_map({a,b}),
+    false = is_map(x),
+    if is_map(#{}) -> ok end,
+    if is_map(#{b=>1}) -> ok end,
+    if not is_map([1,2,3]) -> ok end,
+    if not is_map(x) -> ok end,
+    ok.
+
 % test map updates without matching
 t_update_literals(Config) when is_list(Config) ->
     Map = #{x=>1,y=>2,z=>3,q=>4},
@@ -861,9 +874,9 @@ t_update_map_expressions(Config) when is_list(Config) ->
 
     #{ "a" := b } = F(),
 
-    %% Error cases, FIXME: should be 'badmap'?
-    {'EXIT',{badarg,_}} = (catch (id(<<>>))#{ a := 42, b => 2 }),
-    {'EXIT',{badarg,_}} = (catch (id([]))#{ a := 42, b => 2 }),
+    %% Error cases.
+    {'EXIT',{{badmap,<<>>},_}} = (catch (id(<<>>))#{ a := 42, b => 2 }),
+    {'EXIT',{{badmap,[]},_}} = (catch (id([]))#{ a := 42, b => 2 }),
     ok.
 
 
@@ -884,8 +897,14 @@ t_update_assoc(Config) when is_list(Config) ->
 
     %% Errors cases.
     BadMap = id(badmap),
-    {'EXIT',{badarg,_}} = (catch BadMap#{nonexisting=>val}),
-    {'EXIT',{badarg,_}} = (catch <<>>#{nonexisting=>val}),
+    {'EXIT',{{badmap,BadMap},_}} = (catch BadMap#{nonexisting=>val}),
+    {'EXIT',{{badmap,<<>>},_}} = (catch <<>>#{nonexisting=>val}),
+
+    %% Evaluation order.
+    {'EXIT',{blurf,_}} =
+	(catch BadMap#{whatever=>id(error(blurf))}),
+    {'EXIT',{blurf,_}} =
+	(catch BadMap#{id(error(blurf))=>whatever}),
     ok.
 
 t_update_assoc_large(Config) when is_list(Config) ->
@@ -952,8 +971,8 @@ t_update_assoc_large(Config) when is_list(Config) ->
     M2 = M0#{13.0:=wrong,13.0=>new},
 
     %% Errors cases.
-    BadMap = id(badmap),
-    {'EXIT',{badarg,_}} = (catch BadMap#{nonexisting=>M0}),
+    BadMap = id({no,map}),
+    {'EXIT',{{badmap,BadMap},_}} = (catch BadMap#{nonexisting=>M0}),
     ok.
 
 
@@ -978,19 +997,29 @@ t_update_exact(Config) when is_list(Config) ->
 	1.0 => new_val4 },
 
     %% Errors cases.
-    {'EXIT',{badarg,_}} = (catch ((id(nil))#{ a := b })),
-    {'EXIT',{badarg,_}} = (catch M0#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{1.0:=v,1.0=>v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42.0:=v,42:=v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
-    {'EXIT',{badarg,_}} = (catch <<>>#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{<<0:257>> := val}), %% limitation
+    {'EXIT',{{badmap,nil},_}} = (catch ((id(nil))#{ a := b })),
+    {'EXIT',{{badkey,nonexisting},_}} = (catch M0#{nonexisting:=val}),
+    {'EXIT',{{badkey,1.0},_}} = (catch M0#{1.0:=v,1.0=>v2}),
+    {'EXIT',{{badkey,42},_}} = (catch M0#{42.0:=v,42:=v2}),
+    {'EXIT',{{badkey,42.0},_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+    {'EXIT',{{badmap,<<>>},_}} = (catch <<>>#{nonexisting:=val}),
+    {'EXIT',{{badkey,<<0:257>>},_}} =
+	(catch M0#{<<0:257>> := val}),		%limitation
 
     %% A workaround for a bug allowed an empty map to be updated.
-    {'EXIT',{badarg,_}} = (catch (id(#{}))#{a:=1}),
-    {'EXIT',{badarg,_}} = (catch #{}#{a:=1}),
+    {'EXIT',{{badkey,a},_}} = (catch (id(#{}))#{a:=1}),
+    {'EXIT',{{badkey,a},_}} = (catch #{}#{a:=1}),
     Empty = #{},
-    {'EXIT',{badarg,_}} = (catch Empty#{a:=1}),
+    {'EXIT',{{badkey,a},_}} = (catch Empty#{a:=1}),
+
+    %% Evaluation order.
+    BadMap = id([no,map]),
+    {'EXIT',{blurf,_}} =
+	(catch BadMap#{whatever:=id(error(blurf))}),
+    {'EXIT',{blurf,_}} =
+	(catch BadMap#{id(error(blurf)):=whatever}),
+    {'EXIT',{{badmap,BadMap},_}} =
+	(catch BadMap#{id(nonexisting):=whatever}),
     ok.
 
 t_update_exact_large(Config) when is_list(Config) ->
@@ -1068,10 +1097,10 @@ t_update_exact_large(Config) when is_list(Config) ->
     M2 = M0#{13.0=>wrong,13.0:=new},
 
     %% Errors cases.
-    {'EXIT',{badarg,_}} = (catch M0#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{1.0:=v,1.0=>v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42.0:=v,42:=v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+    {'EXIT',{{badkey,nonexisting},_}} = (catch M0#{nonexisting:=val}),
+    {'EXIT',{{badkey,1.0},_}} = (catch M0#{1.0:=v,1.0=>v2}),
+    {'EXIT',{{badkey,42},_}} = (catch M0#{42.0:=v,42:=v2}),
+    {'EXIT',{{badkey,42.0},_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
 
     ok.
 
@@ -1653,8 +1682,8 @@ t_update_assoc_variables(Config) when is_list(Config) ->
 
     %% Errors cases.
     BadMap = id(badmap),
-    {'EXIT',{badarg,_}} = (catch BadMap#{nonexisting=>val}),
-    {'EXIT',{badarg,_}} = (catch <<>>#{nonexisting=>val}),
+    {'EXIT',{{badmap,BadMap},_}} = (catch BadMap#{nonexisting=>val}),
+    {'EXIT',{{badmap,<<>>},_}} = (catch <<>>#{nonexisting=>val}),
     ok.
 
 t_update_exact_variables(Config) when is_list(Config) ->
@@ -1684,13 +1713,14 @@ t_update_exact_variables(Config) when is_list(Config) ->
     #{ "wat" := 3, 2 := a } = id(#{ "wat" => 1, K2 => 2 }#{ K2 := a, "wat" := 3 }),
 
     %% Errors cases.
-    {'EXIT',{badarg,_}} = (catch ((id(nil))#{ a := b })),
-    {'EXIT',{badarg,_}} = (catch M0#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{1.0:=v,1.0=>v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42.0:=v,42:=v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
-    {'EXIT',{badarg,_}} = (catch <<>>#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{<<0:257>> := val}), %% limitation
+    {'EXIT',{{badmap,nil},_}} = (catch ((id(nil))#{ a := b })),
+    {'EXIT',{{badkey,nonexisting},_}} = (catch M0#{nonexisting:=val}),
+    {'EXIT',{{badkey,1.0},_}} = (catch M0#{1.0:=v,1.0=>v2}),
+    {'EXIT',{{badkey,42},_}} = (catch M0#{42.0:=v,42:=v2}),
+    {'EXIT',{{badkey,42.0},_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+    {'EXIT',{{badmap,<<>>},_}} = (catch <<>>#{nonexisting:=val}),
+    {'EXIT',{{badkey,<<0:257>>},_}} =
+	(catch M0#{<<0:257>> := val}),		%limitation
     ok.
 
 t_nested_pattern_expressions(Config) when is_list(Config) ->
diff --git a/lib/compiler/test/warnings_SUITE.erl b/lib/compiler/test/warnings_SUITE.erl
index d0b7c71be8..e996a55db6 100644
--- a/lib/compiler/test/warnings_SUITE.erl
+++ b/lib/compiler/test/warnings_SUITE.erl
@@ -583,7 +583,7 @@ maps(Config) when is_list(Config) ->
 		 ok.
            ">>,
            [],
-	   {warnings,[{4,sys_core_fold,{eval_failure,badarg}}]}},
+	   {warnings,[{4,sys_core_fold,{eval_failure,badmap}}]}},
 	   {bad_map_src2,
            <<"
              t() ->
@@ -601,7 +601,7 @@ maps(Config) when is_list(Config) ->
 		 ok.
            ">>,
            [],
-	   {warnings,[{3,v3_core,bad_map}]}},
+	   {warnings,[{3,v3_core,badmap}]}},
 	   {ok_map_literal_key,
            <<"
              t() ->
diff --git a/lib/debugger/src/dbg_ieval.erl b/lib/debugger/src/dbg_ieval.erl
index 96f9f91808..cfc2a19ccd 100644
--- a/lib/debugger/src/dbg_ieval.erl
+++ b/lib/debugger/src/dbg_ieval.erl
@@ -658,16 +658,12 @@ expr({map,Line,Fs0}, Bs0, Ieval) ->
 expr({map,Line,E0,Fs0}, Bs0, Ieval0) ->
     Ieval = Ieval0#ieval{line=Line,top=false},
     {value,E,Bs1} = expr(E0, Bs0, Ieval),
-    case E of
-        #{} ->
-            {Fs,Bs2} = eval_map_fields(Fs0, Bs0, Ieval),
-            Value = lists:foldl(fun ({map_assoc,K,V}, Mi) -> maps:put(K,V,Mi);
-                                    ({map_exact,K,V}, Mi) -> maps:update(K,V,Mi)
-                                end, E, Fs),
-            {value,Value,merge_bindings(Bs2, Bs1, Ieval)};
-        _ ->
-            exception(error, {badarg,E}, Bs1, Ieval)
-    end;
+    {Fs,Bs2} = eval_map_fields(Fs0, Bs0, Ieval),
+    _ = maps:put(k, v, E),			%Validate map.
+    Value = lists:foldl(fun ({map_assoc,K,V}, Mi) -> maps:put(K,V,Mi);
+			    ({map_exact,K,V}, Mi) -> maps:update(K,V,Mi)
+			end, E, Fs),
+    {value,Value,merge_bindings(Bs2, Bs1, Ieval)};
 %% A block of statements
 expr({block,Line,Es},Bs,Ieval) ->
     seq(Es, Bs, Ieval#ieval{line=Line});
diff --git a/lib/debugger/test/int_eval_SUITE.erl b/lib/debugger/test/int_eval_SUITE.erl
index 9d7ef238e3..cda5c97ec4 100644
--- a/lib/debugger/test/int_eval_SUITE.erl
+++ b/lib/debugger/test/int_eval_SUITE.erl
@@ -293,7 +293,7 @@ stacktrace(Config) when is_list(Config) ->
 
 maps(Config) when is_list(Config) ->
     Fun = fun () -> ?IM:empty_map_update([camembert]) end,
-    {'EXIT',{{badarg,[camembert]},_}} = spawn_eval(Fun),
+    {'EXIT',{{badmap,[camembert]},_}} = spawn_eval(Fun),
     [#{hello := 0, price := 0}] = spawn_eval(fun () -> ?IM:update_in_fun() end),
     ok.
 
diff --git a/lib/debugger/test/map_SUITE.erl b/lib/debugger/test/map_SUITE.erl
index ac2e16f00a..457863d982 100644
--- a/lib/debugger/test/map_SUITE.erl
+++ b/lib/debugger/test/map_SUITE.erl
@@ -671,9 +671,10 @@ t_map_size(Config) when is_list(Config) ->
     false = map_is_size(M#{ "c" => 2}, 2),
 
     %% Error cases.
-    {'EXIT',{badarg,_}} = (catch map_size([])),
-    {'EXIT',{badarg,_}} = (catch map_size(<<1,2,3>>)),
-    {'EXIT',{badarg,_}} = (catch map_size(1)),
+    do_badmap(fun(T) ->
+                    {'EXIT',{{badmap,T},_}} =
+                      (catch map_size(T))
+              end),
     ok.
 
 map_is_size(M,N) when map_size(M) =:= N -> true;
@@ -849,9 +850,9 @@ t_update_map_expressions(Config) when is_list(Config) ->
     #{ a :=42, b:=42, c:=42 } = (maps:from_list([{a,1},{b,2},{c,3}]))#{ a := 42, b := 42, c := 42 },
     #{ "a" :=1, "b":=42, "c":=42 } = (maps:from_list([{"a",1},{"b",2}]))#{ "b" := 42, "c" => 42 },
 
-    %% Error cases, FIXME: should be 'badmap'?
-    {'EXIT',{{badarg,<<>>},_}} = (catch (id(<<>>))#{ a := 42, b => 2 }),
-    {'EXIT',{{badarg,[]},_}} = (catch (id([]))#{ a := 42, b => 2 }),
+    %% Error cases.
+    {'EXIT',{{badmap,<<>>},_}} = (catch (id(<<>>))#{ a := 42, b => 2 }),
+    {'EXIT',{{badmap,[]},_}} = (catch (id([]))#{ a := 42, b => 2 }),
     ok.
 
 
@@ -867,8 +868,8 @@ t_update_assoc(Config) when is_list(Config) ->
     M2 = M0#{3.0:=wrong,3.0=>new},
 
     %% Errors cases.
-    BadMap = id(badmap),
-    {'EXIT',{{badarg,BadMap},_}} = (catch BadMap#{nonexisting=>val}),
+    BadMap = id(not_a_good_map),
+    {'EXIT',{{badmap,BadMap},_}} = (catch BadMap#{nonexisting=>val}),
 
     ok.
 
@@ -936,8 +937,8 @@ t_update_assoc_large(Config) when is_list(Config) ->
     M2 = M0#{13.0:=wrong,13.0=>new},
 
     %% Errors cases.
-    BadMap = id(badmap),
-    {'EXIT',{{badarg,BadMap},_}} = (catch BadMap#{nonexisting=>M0}),
+    BadMap = id(a_bad_map),
+    {'EXIT',{{badmap,BadMap},_}} = (catch BadMap#{nonexisting=>M0}),
     ok.
 
 
@@ -954,10 +955,25 @@ t_update_exact(Config) when is_list(Config) ->
     %% M2 = M0#{3=>wrong,3.0:=new}, %% FIXME
 
     %% Errors cases.
-    {'EXIT',{badarg,_}} = (catch M0#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{1.0:=v,1.0=>v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42.0:=v,42:=v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+    do_badmap(fun(T) ->
+		      {'EXIT',{{badmap,T},_}} =
+			  (catch T#{nonexisting=>val})
+	      end),
+    Empty = id(#{}),
+    {'EXIT',{{badkey,nonexisting},_}} = (catch Empty#{nonexisting:=val}),
+    {'EXIT',{{badkey,nonexisting},_}} = (catch M0#{nonexisting:=val}),
+    {'EXIT',{{badkey,1.0},_}} = (catch M0#{1.0:=v,1.0=>v2}),
+    {'EXIT',{{badkey,_},_}} = (catch M0#{42.0:=v,42:=v2}),
+    {'EXIT',{{badkey,_},_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+
+    %% Evaluation order.
+    BadMap = id([no,map]),
+    {'EXIT',{blurf,_}} =
+	(catch BadMap#{whatever:=id(error(blurf))}),
+    {'EXIT',{blurf,_}} =
+	(catch BadMap#{id(error(blurf)):=whatever}),
+    {'EXIT',{{badmap,BadMap},_}} =
+	(catch BadMap#{nonexisting:=whatever}),
     ok.
 
 t_update_exact_large(Config) when is_list(Config) ->
@@ -1035,10 +1051,10 @@ t_update_exact_large(Config) when is_list(Config) ->
     M2 = M0#{13.0=>wrong,13.0:=new},
 
     %% Errors cases.
-    {'EXIT',{badarg,_}} = (catch M0#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{1.0:=v,1.0=>v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42.0:=v,42:=v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+    {'EXIT',{{badkey,nonexisting},_}} = (catch M0#{nonexisting:=val}),
+    {'EXIT',{{badkey,1.0},_}} = (catch M0#{1.0:=v,1.0=>v2}),
+    {'EXIT',{{badkey,_},_}} = (catch M0#{42.0:=v,42:=v2}),
+    {'EXIT',{{badkey,_},_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
 
     ok.
 
@@ -1443,11 +1459,11 @@ t_bif_map_get(Config) when is_list(Config) ->
     "v4" = maps:get(<<"k2">>, M#{ <<"k2">> => "v4" }),
 
     %% error case
-    {'EXIT',{badarg, [{maps,get,_,_}|_]}} = (catch maps:get(a,[])),
-    {'EXIT',{badarg, [{maps,get,_,_}|_]}} = (catch maps:get(a,<<>>)),
-    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get({1,1}, #{{1,1.0} => "tuple"})),
-    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get(a,#{})),
-    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get(a,#{ b=>1, c=>2})),
+    {'EXIT',{{badmap,[]},[{maps,get,_,_}|_]}} = (catch maps:get(a, [])),
+    {'EXIT',{{badmap,<<>>},[{maps,get,_,_}|_]}} = (catch maps:get(a, <<>>)),
+    {'EXIT',{{badkey,{1,1}},[{maps,get,_,_}|_]}} = (catch maps:get({1,1}, #{{1,1.0} => "tuple"})),
+    {'EXIT',{{badkey,a},[{maps,get,_,_}|_]}} = (catch maps:get(a, #{})),
+    {'EXIT',{{badkey,a},[{maps,get,_,_}|_]}} = (catch maps:get(a, #{ b=>1, c=>2})),
     ok.
 
 t_bif_map_find(Config) when is_list(Config) ->
@@ -1471,8 +1487,10 @@ t_bif_map_find(Config) when is_list(Config) ->
     error = maps:find({1.0,1}, #{ a=>a, {1,1.0} => "tuple hi"}), % reverse types in tuple key
 
 
-    {'EXIT',{badarg,[{maps,find,_,_}|_]}} = (catch maps:find(a,id([]))),
-    {'EXIT',{badarg,[{maps,find,_,_}|_]}} = (catch maps:find(a,id(<<>>))),
+    {'EXIT',{{badmap,[]},[{maps,find,_,_}|_]}} =
+	(catch maps:find(a, id([]))),
+    {'EXIT',{{badmap,<<>>},[{maps,find,_,_}|_]}} =
+	(catch maps:find(a, id(<<>>))),
     ok.
 
 
@@ -1497,8 +1515,8 @@ t_bif_map_is_key(Config) when is_list(Config) ->
     false = maps:is_key(1.0, maps:put(1, "number", M1)),
 
     %% error case
-    {'EXIT',{badarg,[{maps,is_key,_,_}|_]}} = (catch maps:is_key(a,id([]))),
-    {'EXIT',{badarg,[{maps,is_key,_,_}|_]}} = (catch maps:is_key(a,id(<<>>))),
+    {'EXIT',{{badmap,[]},[{maps,is_key,_,_}|_]}} = (catch maps:is_key(a, id([]))),
+    {'EXIT',{{badmap,<<>>},[{maps,is_key,_,_}|_]}} = (catch maps:is_key(a, id(<<>>))),
     ok.
 
 t_bif_map_keys(Config) when is_list(Config) ->
@@ -1511,11 +1529,12 @@ t_bif_map_keys(Config) when is_list(Config) ->
     [4,int,"hi",<<"key">>] = lists:sort(maps:keys(M1)),
 
     %% error case
-    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(1 bsl 65 + 3)),
-    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(154)),
-    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(atom)),
-    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys([])),
-    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(<<>>)),
+    BigNum = 1 bsl 65 + 3,
+    {'EXIT',{{badmap,BigNum},[{maps,keys,_,_}|_]}} = (catch maps:keys(BigNum)),
+    {'EXIT',{{badmap,154},[{maps,keys,_,_}|_]}} = (catch maps:keys(154)),
+    {'EXIT',{{badmap,atom},[{maps,keys,_,_}|_]}} = (catch maps:keys(atom)),
+    {'EXIT',{{badmap,[]},[{maps,keys,_,_}|_]}} = (catch maps:keys([])),
+    {'EXIT',{{badmap,<<>>},[{maps,keys,_,_}|_]}} = (catch maps:keys(<<>>)),
     ok.
 
 t_bif_map_new(Config) when is_list(Config) ->
@@ -1544,9 +1563,10 @@ t_bif_map_merge(Config) when is_list(Config) ->
 	{1,2} := "tuple", "hi" := "hello again", <<"key">> := <<"value">>} = maps:merge(M0,M1),
 
     %% error case
-    {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge((1 bsl 65 + 3), <<>>)),
-    {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(<<>>, id(#{ a => 1}))),
-    {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(id(#{ a => 2}), <<>> )),
+    BigNum = 1 bsl 65 + 3,
+    {'EXIT',{{badmap,BigNum},[{maps,merge,_,_}|_]}} = (catch maps:merge(BigNum, <<>>)),
+    {'EXIT',{{badmap,<<>>},[{maps,merge,_,_}|_]}} = (catch maps:merge(<<>>, id(#{ a => 1}))),
+    {'EXIT',{{badmap,<<>>},[{maps,merge,_,_}|_]}} = (catch maps:merge(id(#{ a => 2}), <<>> )),
 
     ok.
 
@@ -1585,11 +1605,12 @@ t_bif_map_put(Config) when is_list(Config) ->
     true = is_members([number,wat,3,"hello",<<"other value">>],maps:values(M6)),
 
     %% error case
-    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,1 bsl 65 + 3)),
-    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,154)),
-    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,atom)),
-    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,[])),
-    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,<<>>)),
+    BigNum = 1 bsl 65 + 3,
+    {'EXIT',{{badmap,BigNum},[{maps,put,_,_}|_]}} = (catch maps:put(1, a, BigNum)),
+    {'EXIT',{{badmap,154},[{maps,put,_,_}|_]}} = (catch maps:put(1, a, 154)),
+    {'EXIT',{{badmap,atom},[{maps,put,_,_}|_]}} = (catch maps:put(1, a, atom)),
+    {'EXIT',{{badmap,[]},[{maps,put,_,_}|_]}} = (catch maps:put(1, a, [])),
+    {'EXIT',{{badmap,<<>>},[{maps,put,_,_}|_]}} = (catch maps:put(1, a, <<>>)),
     ok.
 
 is_members(Ks,Ls) when length(Ks) =/= length(Ls) -> false;
@@ -1621,9 +1642,10 @@ t_bif_map_update(Config) when is_list(Config) ->
 	4 := number, 18446744073709551629 := wazzup} = maps:update(18446744073709551629, wazzup, M0),
 
     %% error case
-    {'EXIT',{badarg,[{maps,update,_,_}|_]}} = (catch maps:update(1,none,{})),
-    {'EXIT',{badarg,[{maps,update,_,_}|_]}} = (catch maps:update(1,none,<<"value">>)),
-    {'EXIT',{badarg,[{maps,update,_,_}|_]}} = (catch maps:update(5,none,M0)),
+    {'EXIT',{{badmap,{}},[{maps,update,_,_}|_]}} = (catch maps:update(1, none, {})),
+    {'EXIT',{{badmap,<<"value">>},[{maps,update,_,_}|_]}} =
+	(catch maps:update(1, none, <<"value">>)),
+    {'EXIT',{{badkey,5},[{maps,update,_,_}|_]}} = (catch maps:update(5, none, M0)),
 
     ok.
 
@@ -1659,12 +1681,13 @@ t_bif_map_remove(Config) when is_list(Config) ->
     #{ "hi" := "hello", int := 3, 4 := number} = maps:remove(18446744073709551629,maps:remove(<<"key">>,M0)),
 
     %% error case
-    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(a,1 bsl 65 + 3)),
-    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(1,154)),
-    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(a,atom)),
-    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(1,[])),
-    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(a,<<>>)),
-     ok.
+    BigNum = 1 bsl 65 + 3,
+    {'EXIT',{{badmap,BigNum},[{maps,remove,_,_}|_]}} = (catch maps:remove(a, BigNum)),
+    {'EXIT',{{badmap,154},[{maps,remove,_,_}|_]}} = (catch maps:remove(1, 154)),
+    {'EXIT',{{badmap,atom},[{maps,remove,_,_}|_]}} = (catch maps:remove(a, atom)),
+    {'EXIT',{{badmap,[]},[{maps,remove,_,_}|_]}} = (catch maps:remove(1, [])),
+    {'EXIT',{{badmap,<<>>},[{maps,remove,_,_}|_]}} = (catch maps:remove(a, <<>>)),
+    ok.
 
 t_bif_map_values(Config) when is_list(Config) ->
 
@@ -1680,10 +1703,11 @@ t_bif_map_values(Config) when is_list(Config) ->
     true = is_members([number,3,"hello",<<"value">>],maps:values(M1)),
 
     %% error case
-    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(1 bsl 65 + 3)),
-    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(atom)),
-    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values([])),
-    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(<<>>)),
+    BigNum = 1 bsl 65 + 3,
+    {'EXIT',{{badmap,BigNum},[{maps,values,_,_}|_]}} = (catch maps:values(BigNum)),
+    {'EXIT',{{badmap,atom},[{maps,values,_,_}|_]}} = (catch maps:values(atom)),
+    {'EXIT',{{badmap,[]},[{maps,values,_,_}|_]}} = (catch maps:values([])),
+    {'EXIT',{{badmap,<<>>},[{maps,values,_,_}|_]}} = (catch maps:values(<<>>)),
     ok.
 
 
@@ -1854,8 +1878,8 @@ t_bif_map_to_list(Config) when is_list(Config) ->
 				  <<"hi">>=>v6,3=>v7,"hi"=>v8,hi=>v9,{hi,3}=>v10})),
 
     %% error cases
-    {'EXIT', {badarg,_}} = (catch maps:to_list(id(a))),
-    {'EXIT', {badarg,_}} = (catch maps:to_list(id(42))),
+    {'EXIT', {{badmap,a},_}} = (catch maps:to_list(id(a))),
+    {'EXIT', {{badmap,42},_}} = (catch maps:to_list(id(42))),
     ok.
 
 
@@ -2071,9 +2095,9 @@ t_update_assoc_variables(Config) when is_list(Config) ->
     #{ <<0:258>> := val } = id(M0#{<<0:258>> => val}), %% binary limitation
 
     %% Errors cases.
-    BadMap = id(badmap),
-    {'EXIT',{{badarg,_},_}} = (catch BadMap#{nonexisting=>val}),
-    {'EXIT',{{badarg,_},_}} = (catch <<>>#{nonexisting=>val}),
+    BadMap = id(a_bad_map),
+    {'EXIT',{{badmap,BadMap},_}} = (catch BadMap#{nonexisting=>val}),
+    {'EXIT',{{badmap,<<>>},_}} = (catch <<>>#{nonexisting=>val}),
     ok.
 
 t_update_exact_variables(Config) when is_list(Config) ->
@@ -2101,14 +2125,14 @@ t_update_exact_variables(Config) when is_list(Config) ->
 	1.0 => new_val4 },
 
     %% Errors cases.
-    {'EXIT',{{badarg,_},_}} = (catch ((id(nil))#{ a := b })),
-    {'EXIT',{{badarg,_},_}} = (catch <<>>#{nonexisting:=val}),
-
-    {'EXIT',{badarg,_}} = (catch M0#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{1.0:=v,1.0=>v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42.0:=v,42:=v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
-    {'EXIT',{badarg,_}} = (catch M0#{<<0:257>> := val}), %% limitation
+    {'EXIT',{{badmap,_},_}} = (catch ((id(nil))#{ a := b })),
+    {'EXIT',{{badmap,_},_}} = (catch <<>>#{nonexisting:=val}),
+
+    {'EXIT',{{badkey,nonexisting},_}} = (catch M0#{nonexisting:=val}),
+    {'EXIT',{{badkey,1.0},_}} = (catch M0#{1.0:=v,1.0=>v2}),
+    {'EXIT',{{badkey,_},_}} = (catch M0#{42.0:=v,42:=v2}),
+    {'EXIT',{{badkey,_},_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+    {'EXIT',{{badkey,_},_}} = (catch M0#{<<0:257>> := val}), %% limitation
     ok.
 
 t_nested_pattern_expressions(Config) when is_list(Config) ->
@@ -2359,6 +2383,11 @@ t_build_and_match_structure(Config) when is_list(Config) ->
     ok.
 
 
+do_badmap(Test) ->
+    Terms = [Test,fun erlang:abs/1,make_ref(),self(),0.0/id(-1),
+	     <<1:1>>,<<>>,<<1,2,3>>,
+	     [],{a,b,c},[a,b],atom,10.0,42,(1 bsl 65) + 3],
+    [Test(T) || T <- Terms].
 
 %% Use this function to avoid compile-time evaluation of an expression.
 id(I) -> I.
diff --git a/lib/hipe/icode/hipe_beam_to_icode.erl b/lib/hipe/icode/hipe_beam_to_icode.erl
index 4691662f9f..3e099fcc25 100644
--- a/lib/hipe/icode/hipe_beam_to_icode.erl
+++ b/lib/hipe/icode/hipe_beam_to_icode.erl
@@ -1584,11 +1584,7 @@ gen_put_map_instrs(exists, Op, TempMapVar, Dst, FailLbl, Pairs, Env) ->
       end,
   {[IsMapCode, TrueLabel, PutInstructions, ReturnLbl], Env1};
 gen_put_map_instrs(new, Op, TempMapVar, Dst, new, Pairs, Env) ->
-  TrueLabel = mk_label(new),
   FailLbl = mk_label(new),
-  IsMapCode = hipe_icode:mk_type([TempMapVar], map,
-				 hipe_icode:label_name(TrueLabel),
-				 hipe_icode:label_name(FailLbl)),
   DstMapVar = mk_var(Dst),
   {ReturnLbl, PutInstructions, Env1}
     = case Op of
@@ -1596,10 +1592,10 @@ gen_put_map_instrs(new, Op, TempMapVar, Dst, new, Pairs, Env) ->
 	  trans_put_map_assoc(TempMapVar, DstMapVar, Pairs, Env, []);
 	exact ->
 	  trans_put_map_exact(TempMapVar, DstMapVar,
-	    hipe_icode:label_name(FailLbl), Pairs, Env, [])
+			      none, Pairs, Env, [])
       end,
   Fail = hipe_icode:mk_fail([hipe_icode:mk_const(badarg)], error),
-  {[IsMapCode, TrueLabel, PutInstructions, FailLbl, Fail, ReturnLbl], Env1}.
+  {[PutInstructions, FailLbl, Fail, ReturnLbl], Env1}.
 
 %%-----------------------------------------------------------------------
 %% This function generates the instructions needed to insert several
@@ -1629,6 +1625,13 @@ trans_put_map_exact(MapVar, DestMapVar, _FLbl, [], Env, Acc) ->
   ReturnLbl = mk_label(new),
   GotoReturn = hipe_icode:mk_goto(hipe_icode:label_name(ReturnLbl)),
   {ReturnLbl, lists:reverse([GotoReturn, MoveToReturnVar | Acc]), Env};
+trans_put_map_exact(MapVar, DestMapVar, none, [Key, Value | Rest], Env, Acc) ->
+  {MoveKey, KeyVar, Env1} = mk_move_and_var(Key, Env),
+  {MoveVal, ValVar, Env2} = mk_move_and_var(Value, Env1),
+  BifCallPut = hipe_icode:mk_call([MapVar], maps, update,
+				  [KeyVar, ValVar, MapVar], remote),
+  Acc1 = [BifCallPut, MoveVal, MoveKey | Acc],
+  trans_put_map_exact(MapVar, DestMapVar, none, Rest, Env2, Acc1);
 trans_put_map_exact(MapVar, DestMapVar, FLbl, [Key, Value | Rest], Env, Acc) ->
   SuccLbl = mk_label(new),
   {MoveKey, KeyVar, Env1} = mk_move_and_var(Key, Env),
diff --git a/lib/hipe/test/maps_SUITE_data/maps_map_size.erl b/lib/hipe/test/maps_SUITE_data/maps_map_size.erl
index 25c8e5d4c7..3cd2d90dfb 100644
--- a/lib/hipe/test/maps_SUITE_data/maps_map_size.erl
+++ b/lib/hipe/test/maps_SUITE_data/maps_map_size.erl
@@ -17,9 +17,9 @@ test() ->
     false = map_is_size(M#{ "c" => 2}, 2),
 
     %% Error cases.
-    {'EXIT',{badarg,_}} = (catch map_size([])),
-    {'EXIT',{badarg,_}} = (catch map_size(<<1,2,3>>)),
-    {'EXIT',{badarg,_}} = (catch map_size(1)),
+    {'EXIT',{{badmap,[]},_}} = (catch map_size([])),
+    {'EXIT',{{badmap,<<1,2,3>>},_}} = (catch map_size(<<1,2,3>>)),
+    {'EXIT',{{badmap,1},_}} = (catch map_size(1)),
     ok.
 
 map_is_size(M,N) when map_size(M) =:= N -> true;
diff --git a/lib/hipe/test/maps_SUITE_data/maps_put_map_assoc.erl b/lib/hipe/test/maps_SUITE_data/maps_put_map_assoc.erl
index 72ac9ce078..2fe4f204d1 100644
--- a/lib/hipe/test/maps_SUITE_data/maps_put_map_assoc.erl
+++ b/lib/hipe/test/maps_SUITE_data/maps_put_map_assoc.erl
@@ -8,7 +8,7 @@ test() ->
   true  = assoc_guard(#{}),
   false = assoc_guard(not_a_map),
   #{a := true} = assoc_update(#{}),
-  {'EXIT', {badarg, [{?MODULE, assoc_update, 1, _}|_]}}
+  {'EXIT', {{badmap, not_a_map}, [{?MODULE, assoc_update, 1, _}|_]}}
     = (catch assoc_update(not_a_map)),
   ok = assoc_guard_clause(#{}),
   {'EXIT', {function_clause, [{?MODULE, assoc_guard_clause, _, _}|_]}}
diff --git a/lib/hipe/test/maps_SUITE_data/maps_put_map_exact.erl b/lib/hipe/test/maps_SUITE_data/maps_put_map_exact.erl
index 1cfcd80180..3c85289a36 100644
--- a/lib/hipe/test/maps_SUITE_data/maps_put_map_exact.erl
+++ b/lib/hipe/test/maps_SUITE_data/maps_put_map_exact.erl
@@ -9,9 +9,9 @@ test() ->
   false = exact_guard(not_a_map),
   true  = exact_guard(#{a => false}),
   #{a := true} = exact_update(#{a => false}),
-  {'EXIT', {badarg, [{?MODULE, exact_update, 1, _}|_]}}
+  {'EXIT', {{badmap, not_a_map}, [{?MODULE, exact_update, 1, _}|_]}}
     = (catch exact_update(not_a_map)),
-  {'EXIT', {badarg, [{?MODULE, exact_update, 1, _}|_]}}
+  {'EXIT', {{badkey, a}, [{?MODULE, exact_update, 1, _}|_]}}
     = (catch exact_update(#{})),
   ok = exact_guard_clause(#{a => yes}),
   {'EXIT', {function_clause, [{?MODULE, exact_guard_clause, _, _}|_]}}
diff --git a/lib/hipe/test/maps_SUITE_data/maps_update_assoc.erl b/lib/hipe/test/maps_SUITE_data/maps_update_assoc.erl
index cc7c1353de..99228a1927 100644
--- a/lib/hipe/test/maps_SUITE_data/maps_update_assoc.erl
+++ b/lib/hipe/test/maps_SUITE_data/maps_update_assoc.erl
@@ -14,7 +14,7 @@ test() ->
 
     %% Errors cases.
     BadMap = id(badmap),
-    {'EXIT',{badarg,_}} = (catch BadMap#{nonexisting=>val}),
+    {'EXIT',{{badmap,badmap},_}} = (catch BadMap#{nonexisting=>val}),
 
     ok.
 
diff --git a/lib/hipe/test/maps_SUITE_data/maps_update_exact.erl b/lib/hipe/test/maps_SUITE_data/maps_update_exact.erl
index 6e5acb3283..1c38820a7c 100644
--- a/lib/hipe/test/maps_SUITE_data/maps_update_exact.erl
+++ b/lib/hipe/test/maps_SUITE_data/maps_update_exact.erl
@@ -21,11 +21,11 @@ test() ->
 	1.0 => new_val4 },
 
     %% Errors cases.
-    {'EXIT',{badarg,_}} = (catch ((id(nil))#{ a := b })),
-    {'EXIT',{badarg,_}} = (catch M0#{nonexisting:=val}),
-    {'EXIT',{badarg,_}} = (catch M0#{1.0:=v,1.0=>v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42.0:=v,42:=v2}),
-    {'EXIT',{badarg,_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+    {'EXIT',{{badmap,nil},_}} = (catch ((id(nil))#{ a := b })),
+    {'EXIT',{{badkey,nonexisting},_}} = (catch M0#{nonexisting:=val}),
+    {'EXIT',{{badkey,_},_}} = (catch M0#{1.0:=v,1.0=>v2}),
+    {'EXIT',{{badkey,_},_}} = (catch M0#{42.0:=v,42:=v2}),
+    {'EXIT',{{badkey,_},_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
     ok.
 
 %% Use this function to avoid compile-time evaluation of an expression.
diff --git a/lib/hipe/test/maps_SUITE_data/maps_update_map_expressions.erl b/lib/hipe/test/maps_SUITE_data/maps_update_map_expressions.erl
index 181e3f18f7..213fc33d97 100644
--- a/lib/hipe/test/maps_SUITE_data/maps_update_map_expressions.erl
+++ b/lib/hipe/test/maps_SUITE_data/maps_update_map_expressions.erl
@@ -23,9 +23,9 @@ test() ->
 
     #{ "a" := b } = F(),
 
-    %% Error cases, FIXME: should be 'badmap'?
-    {'EXIT',{badarg,_}} = (catch (id(<<>>))#{ a := 42, b => 2 }),
-    {'EXIT',{badarg,_}} = (catch (id([]))#{ a := 42, b => 2 }),
+    %% Error cases.
+    {'EXIT',{{badmap,<<>>},_}} = (catch (id(<<>>))#{ a := 42, b => 2 }),
+    {'EXIT',{{badmap,[]},_}} = (catch (id([]))#{ a := 42, b => 2 }),
     ok.
 
 %% Use this function to avoid compile-time evaluation of an expression.
diff --git a/lib/stdlib/doc/src/maps.xml b/lib/stdlib/doc/src/maps.xml
index f766c843be..59c26d9896 100644
--- a/lib/stdlib/doc/src/maps.xml
+++ b/lib/stdlib/doc/src/maps.xml
@@ -40,6 +40,9 @@
 					Returns a tuple <c>{ok, Value}</c> where <c><anno>Value</anno></c> is the value associated with <c><anno>Key</anno></c>,
 					or <c>error</c> if no value is associated with <c><anno>Key</anno></c> in <c><anno>Map</anno></c>. 
 				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map</anno></c> is not a map.
+				</p>
 				<p>Example:</p>
 				<code type="none">
 > Map = #{"hi" => 42},
@@ -95,8 +98,10 @@
 				<p>
 					Returns the value <c><anno>Value</anno></c> associated with <c><anno>Key</anno></c> if
 					<c><anno>Map</anno></c> contains <c><anno>Key</anno></c>.
-					If no value is associated with <c><anno>Key</anno></c> then the call will
-					fail with an exception.
+				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map</anno></c> is not a map,
+					or with a <c>{badkey,Key}</c> exception if no value is associated with <c><anno>Key</anno></c>.
 				</p>
 				<p>Example:</p>
 				<code type="none">
@@ -116,6 +121,10 @@
 					<c><anno>Map</anno></c> contains <c><anno>Key</anno></c>.
 					If no value is associated with <c><anno>Key</anno></c> then returns <c><anno>Default</anno></c>.
 				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map</anno></c> is not a map.
+
+				</p>
 				<p>Example:</p>
 				<code type="none">
 > Map = #{ key1 => val1, key2 => val2 }.
@@ -134,7 +143,9 @@ val1
 				<p>
 					Returns <c>true</c> if map <c><anno>Map</anno></c> contains <c><anno>Key</anno></c> and returns
 					<c>false</c> if it does not contain the <c><anno>Key</anno></c>.
-					The function will fail with an exception if <c><anno>Map</anno></c> is not a Map.
+				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map</anno></c> is not a map.
 				</p>
 				<p>Example:</p>
 				<code type="none">
@@ -154,6 +165,9 @@ false</code>
 				<p>
 					Returns a complete list of keys, in arbitrary order, which resides within <c><anno>Map</anno></c>.
 				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map</anno></c> is not a map.
+				</p>
 				<p>Example:</p>
 				<code type="none">
 > Map = #{42 => value_three,1337 => "value two","a" => 1},
@@ -189,6 +203,10 @@ false</code>
 					Merges two maps into a single map <c><anno>Map3</anno></c>. If two keys exists in both maps the
 					value in <c><anno>Map1</anno></c> will be superseded by the value in <c><anno>Map2</anno></c>.
 				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map1</anno></c> or
+					<c><anno>Map2</anno></c> is not a map.
+				</p>
 				<p>Example:</p>
 				<code type="none">
 > Map1 = #{a => "value_one", b => "value_two"},
@@ -222,6 +240,10 @@ false</code>
 					replaced by value <c><anno>Value</anno></c>. The function returns a new map <c><anno>Map2</anno></c> containing the new association and
 					the old associations in <c><anno>Map1</anno></c>.
 				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map1</anno></c> is not a map.
+				</p>
+
 				<p>Example:</p>
 				<code type="none">
 > Map = #{"a" => 1}.
@@ -241,6 +263,9 @@ false</code>
 					The function removes the <c><anno>Key</anno></c>, if it exists, and its associated value from
 					<c><anno>Map1</anno></c> and returns a new map <c><anno>Map2</anno></c> without key <c><anno>Key</anno></c>.
 				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map1</anno></c> is not a map.
+				</p>
 				<p>Example:</p>
 				<code type="none">
 > Map = #{"a" => 1}.
@@ -276,6 +301,9 @@ false</code>
 					The fuction returns a list of pairs representing the key-value associations of <c><anno>Map</anno></c>,
 					where the pairs, <c>[{K1,V1}, ..., {Kn,Vn}]</c>, are returned in arbitrary order.
 				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map</anno></c> is not a map.
+				</p>
 				<p>Example:</p>
 				<code type="none">
 > Map = #{42 => value_three,1337 => "value two","a" => 1},
@@ -291,8 +319,11 @@ false</code>
 				<p>
 					If <c><anno>Key</anno></c> exists in <c><anno>Map1</anno></c> the old associated value is
 					replaced by value <c><anno>Value</anno></c>. The function returns a new map <c><anno>Map2</anno></c> containing
-					the new associated value. If <c><anno>Key</anno></c> does not exist in <c><anno>Map1</anno></c> an exception is
-					generated.
+					the new associated value.
+				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map1</anno></c> is not a map,
+					or with a <c>{badkey,Key}</c> exception if no value is associated with <c><anno>Key</anno></c>.
 				</p>
 				<p>Example:</p>
 				<code type="none">
@@ -310,6 +341,9 @@ false</code>
 				<p>
 					Returns a complete list of values, in arbitrary order, contained in map <c>M</c>.
 				</p>
+				<p>
+					The call will fail with a <c>{badmap,Map}</c> exception if <c><anno>Map</anno></c> is not a map.
+				</p>
 				<p>Example:</p>
 				<code type="none">
 > Map = #{42 => value_three,1337 => "value two","a" => 1},
diff --git a/lib/stdlib/src/erl_eval.erl b/lib/stdlib/src/erl_eval.erl
index 371573dc23..e86e10b170 100644
--- a/lib/stdlib/src/erl_eval.erl
+++ b/lib/stdlib/src/erl_eval.erl
@@ -246,18 +246,14 @@ expr({record,_,_,Name,_}, _Bs, _Lf, _Ef, _RBs) ->
 %% map
 expr({map,_,Binding,Es}, Bs0, Lf, Ef, RBs) ->
     {value, Map0, Bs1} = expr(Binding, Bs0, Lf, Ef, none),
-    case Map0 of
-        #{} ->
-            {Vs,Bs2} = eval_map_fields(Es, Bs0, Lf, Ef),
-            Map1 = lists:foldl(fun ({map_assoc,K,V}, Mi) ->
-                                       maps:put(K, V, Mi);
-                                   ({map_exact,K,V}, Mi) ->
-                                       maps:update(K, V, Mi)
-                               end, Map0, Vs),
-            ret_expr(Map1, merge_bindings(Bs2, Bs1), RBs);
-        _ ->
-            erlang:raise(error, {badarg,Map0}, stacktrace())
-    end;
+    {Vs,Bs2} = eval_map_fields(Es, Bs0, Lf, Ef),
+    _ = maps:put(k, v, Map0),			%Validate map.
+    Map1 = lists:foldl(fun ({map_assoc,K,V}, Mi) ->
+			       maps:put(K, V, Mi);
+			   ({map_exact,K,V}, Mi) ->
+			       maps:update(K, V, Mi)
+		       end, Map0, Vs),
+    ret_expr(Map1, merge_bindings(Bs2, Bs1), RBs);
 expr({map,_,Es}, Bs0, Lf, Ef, RBs) ->
     {Vs,Bs} = eval_map_fields(Es, Bs0, Lf, Ef),
     ret_expr(lists:foldl(fun
diff --git a/lib/stdlib/test/erl_eval_SUITE.erl b/lib/stdlib/test/erl_eval_SUITE.erl
index 3427f431c5..a750c5cace 100644
--- a/lib/stdlib/test/erl_eval_SUITE.erl
+++ b/lib/stdlib/test/erl_eval_SUITE.erl
@@ -1482,8 +1482,11 @@ eep43(Config) when is_list(Config) ->
 	  "    #{ K1 := 1, K2 := 2, K3 := 3, {2,2} := 4} = Map "
 	  "end.",
 	  #{ 1 => 1, <<42:301>> => 2, {3,<<42:301>>} => 3, {2,2} => 4}),
-    error_check("[camembert]#{}.", {badarg,[camembert]}),
+    error_check("[camembert]#{}.", {badmap,[camembert]}),
+    error_check("[camembert]#{nonexisting:=v}.", {badmap,[camembert]}),
     error_check("#{} = 1.", {badmatch,1}),
+    error_check("[]#{a=>error(bad)}.", bad),
+    error_check("(#{})#{nonexisting:=value}.", {badkey,nonexisting}),
     ok.
 
 %% Check the string in different contexts: as is; in fun; from compiled code.