Merge branch 'egil/maps/hamt/OTP-12585'

* egil/maps/hamt/OTP-12585: (113 commits)
  erts: Fix bug in ESTACK and WSTACK
  kernel: Add spec for erts_debug:map_info/1
  mnesia: Update mnesia tests to reflect new ETS hash
  erts: Ensure maps uses _rel functions in halfword
  erts: Do not treat errors as fatal in erl_printf_term
  erts: Update preloaded erts_internal.beam
  erts: Add map decomposition wrappers
  erts: Ensure halfword has correct temp-heap for maps
  hipe: Handle separate hashmap tag correctly
  erts: Fix map bug in dec_term for 32-bit debug VM
  stdlib: Update qlc tests to reflect new ETS hash
  stdlib: Remove obsolete hashmap references in io_lib
  erts: Enhance maps ordering tests
  hipe: Fix maps sort order testcase
  erts: Remove unused variable in crashdump creation
  erts: Fix typo in copy_struct for halfword emulator
  erts: Restrict GCC intrinsics by compiler version
  erts: Fix windows bug in hashmap_info
  erts: Fix typo in make_hash2 for 32-bit arch
  Fix beam_load assert
  ...

Conflicts:
	erts/emulator/beam/bif.tab

8 files changed, 208 insertions, 156 deletions

diff --git a/lib/compiler/test/map_SUITE.erl b/lib/compiler/test/map_SUITE.erl
index cfa8262701..1c9574c2a2 100644
--- a/lib/compiler/test/map_SUITE.erl
+++ b/lib/compiler/test/map_SUITE.erl
@@ -543,7 +543,7 @@ t_map_sort_literals(Config) when is_list(Config) ->
     true  = id(#{ c => 1, b => 1, a => 1 }) < id(#{ b => 1, c => 1, d => 1}),
     true  = id(#{ "a" => 1 }) < id(#{ <<"a">> => 1}),
     false = id(#{ <<"a">> => 1 }) < id(#{ "a" => 1}),
-    false = id(#{ 1 => 1 }) < id(#{ 1.0 => 1}),
+    true = id(#{ 1 => 1 }) < id(#{ 1.0 => 1}),
     false = id(#{ 1.0 => 1 }) < id(#{ 1 => 1}),
 
     %% value order
diff --git a/lib/debugger/test/map_SUITE.erl b/lib/debugger/test/map_SUITE.erl
index e525484a8e..b114d29f44 100644
--- a/lib/debugger/test/map_SUITE.erl
+++ b/lib/debugger/test/map_SUITE.erl
@@ -494,7 +494,7 @@ t_map_sort_literals(Config) when is_list(Config) ->
     true  = #{ c => 1, b => 1, a => 1 } < id(#{ b => 1, c => 1, d => 1}),
     true  = #{ "a" => 1 } < id(#{ <<"a">> => 1}),
     false = #{ <<"a">> => 1 } < id(#{ "a" => 1}),
-    false = #{ 1 => 1 } < id(#{ 1.0 => 1}),
+    true  = #{ 1 => 1 } < id(#{ 1.0 => 1}),
     false = #{ 1.0 => 1 } < id(#{ 1 => 1}),
 
     %% value order
@@ -587,12 +587,11 @@ t_bif_map_is_key(Config) when is_list(Config) ->
 t_bif_map_keys(Config) when is_list(Config) ->
     [] = maps:keys(#{}),
 
-    [1,2,3,4,5] = maps:keys(#{ 1 => a, 2 => b, 3 => c, 4 => d, 5 => e}),
-    [1,2,3,4,5] = maps:keys(#{ 4 => d, 5 => e, 1 => a, 2 => b, 3 => c}),
+    [1,2,3,4,5] = lists:sort(maps:keys(#{ 1 => a, 2 => b, 3 => c, 4 => d, 5 => e})),
+    [1,2,3,4,5] = lists:sort(maps:keys(#{ 4 => d, 5 => e, 1 => a, 2 => b, 3 => c})),
 
-    % values in key order: [4,int,"hi",<<"key">>]
     M1 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>, 4 => number},
-    [4,int,"hi",<<"key">>] = maps:keys(M1),
+    [4,int,"hi",<<"key">>] = lists:sort(maps:keys(M1)),
 
     %% error case
     {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(1 bsl 65 + 3)),
@@ -634,40 +633,39 @@ t_bif_map_merge(Config) when is_list(Config) ->
 
     ok.
 
-
 t_bif_map_put(Config) when is_list(Config) ->
     M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
 	4 => number, 18446744073709551629 => wat},
 
     M1 = #{ "hi" := "hello"} = maps:put("hi", "hello", #{}),
 
-    ["hi"]    = maps:keys(M1),
-    ["hello"] = maps:values(M1),
+    true = is_members(["hi"],maps:keys(M1)),
+    true = is_members(["hello"],maps:values(M1)),
 
     M2 = #{ int := 3 } = maps:put(int, 3, M1),
 
-    [int,"hi"]  = maps:keys(M2),
-    [3,"hello"] = maps:values(M2),
+    true = is_members([int,"hi"],maps:keys(M2)),
+    true = is_members([3,"hello"],maps:values(M2)),
 
     M3 = #{ <<"key">> := <<"value">> } = maps:put(<<"key">>, <<"value">>, M2),
 
-    [int,"hi",<<"key">>]    = maps:keys(M3),
-    [3,"hello",<<"value">>] = maps:values(M3),
+    true = is_members([int,"hi",<<"key">>],maps:keys(M3)),
+    true = is_members([3,"hello",<<"value">>],maps:values(M3)),
 
     M4 = #{ 18446744073709551629 := wat } = maps:put(18446744073709551629, wat, M3),
 
-    [18446744073709551629,int,"hi",<<"key">>] = maps:keys(M4),
-    [wat,3,"hello",<<"value">>]               = maps:values(M4),
+    true = is_members([18446744073709551629,int,"hi",<<"key">>],maps:keys(M4)),
+    true = is_members([wat,3,"hello",<<"value">>],maps:values(M4)),
 
     M0 = #{ 4 := number } = M5 = maps:put(4, number, M4),
 
-    [4,18446744073709551629,int,"hi",<<"key">>] = maps:keys(M5),
-    [number,wat,3,"hello",<<"value">>]          = maps:values(M5),
+    true = is_members([4,18446744073709551629,int,"hi",<<"key">>],maps:keys(M5)),
+    true = is_members([number,wat,3,"hello",<<"value">>],maps:values(M5)),
 
     M6 = #{ <<"key">> := <<"other value">> } = maps:put(<<"key">>, <<"other value">>, M5),
 
-    [4,18446744073709551629,int,"hi",<<"key">>] = maps:keys(M6),
-    [number,wat,3,"hello",<<"other value">>]    = maps:values(M6),
+    true = is_members([4,18446744073709551629,int,"hi",<<"key">>],maps:keys(M6)),
+    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)),
@@ -675,46 +673,16 @@ t_bif_map_put(Config) when is_list(Config) ->
     {'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,<<>>)),
-     ok.
-
-t_bif_map_remove(Config) when is_list(Config) ->
-    0  = erlang:map_size(maps:remove(some_key, #{})),
-
-    M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
-	4 => number, 18446744073709551629 => wat},
-
-    M1 = maps:remove("hi", M0),
-    [4,18446744073709551629,int,<<"key">>] = maps:keys(M1),
-    [number,wat,3,<<"value">>]             = maps:values(M1),
-
-    M2 = maps:remove(int, M1),
-    [4,18446744073709551629,<<"key">>] = maps:keys(M2),
-    [number,wat,<<"value">>]           = maps:values(M2),
-
-    M3 = maps:remove(<<"key">>, M2),
-    [4,18446744073709551629] = maps:keys(M3),
-    [number,wat]             = maps:values(M3),
-
-    M4 = maps:remove(18446744073709551629, M3),
-    [4]      = maps:keys(M4),
-    [number] = maps:values(M4),
-
-    M5 = maps:remove(4, M4),
-    [] = maps:keys(M5),
-    [] = maps:values(M5),
+    ok.
 
-    M0 = maps:remove(5,M0),
-    M0 = maps:remove("hi there",M0),
+is_members(Ks,Ls) when length(Ks) =/= length(Ls) -> false;
+is_members(Ks,Ls) -> is_members_do(Ks,Ls).
 
-    #{ "hi" := "hello", int := 3, 4 := number} = maps:remove(18446744073709551629,maps:remove(<<"key">>,M0)),
+is_members_do([],[]) -> true;
+is_members_do([],_) -> false;
+is_members_do([K|Ks],Ls) ->
+    is_members_do(Ks, lists:delete(K,Ls)).
 
-    %% 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.
 
 t_bif_map_update(Config) when is_list(Config) ->
     M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
@@ -742,20 +710,57 @@ t_bif_map_update(Config) when is_list(Config) ->
 
     ok.
 
+t_bif_map_remove(Config) when is_list(Config) ->
+    0  = erlang:map_size(maps:remove(some_key, #{})),
+
+    M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
+	4 => number, 18446744073709551629 => wat},
+
+    M1 = maps:remove("hi", M0),
+    true = is_members([4,18446744073709551629,int,<<"key">>],maps:keys(M1)),
+    true = is_members([number,wat,3,<<"value">>],maps:values(M1)),
+
+    M2 = maps:remove(int, M1),
+    true = is_members([4,18446744073709551629,<<"key">>],maps:keys(M2)),
+    true = is_members([number,wat,<<"value">>],maps:values(M2)),
+
+    M3 = maps:remove(<<"key">>, M2),
+    true = is_members([4,18446744073709551629],maps:keys(M3)),
+    true = is_members([number,wat],maps:values(M3)),
 
+    M4 = maps:remove(18446744073709551629, M3),
+    true = is_members([4],maps:keys(M4)),
+    true = is_members([number],maps:values(M4)),
+
+    M5 = maps:remove(4, M4),
+    [] = maps:keys(M5),
+    [] = maps:values(M5),
+
+    M0 = maps:remove(5,M0),
+    M0 = maps:remove("hi there",M0),
+
+    #{ "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.
 
 t_bif_map_values(Config) when is_list(Config) ->
 
     [] = maps:values(#{}),
+    [1] = maps:values(#{a=>1}),
 
-    [a,b,c,d,e] = maps:values(#{ 1 => a, 2 => b, 3 => c, 4 => d, 5 => e}),
-    [a,b,c,d,e] = maps:values(#{ 4 => d, 5 => e, 1 => a, 2 => b, 3 => c}),
+    true = is_members([a,b,c,d,e],maps:values(#{ 1 => a, 2 => b, 3 => c, 4 => d, 5 => e})),
+    true = is_members([a,b,c,d,e],maps:values(#{ 4 => d, 5 => e, 1 => a, 2 => b, 3 => c})),
 
-    % values in key order: [4,int,"hi",<<"key">>]
     M1 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>, 4 => number},
     M2 = M1#{ "hi" => "hello2", <<"key">> => <<"value2">> },
-    [number,3,"hello2",<<"value2">>] = maps:values(M2),
-    [number,3,"hello",<<"value">>]   = maps:values(M1),
+    true = is_members([number,3,"hello2",<<"value2">>],maps:values(M2)),
+    true = is_members([number,3,"hello",<<"value">>],maps:values(M1)),
 
     %% error case
     {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(1 bsl 65 + 3)),
@@ -764,75 +769,74 @@ t_bif_map_values(Config) when is_list(Config) ->
     {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(<<>>)),
     ok.
 
+
+
 t_erlang_hash(Config) when is_list(Config) ->
 
     ok = t_bif_erlang_phash2(),
     ok = t_bif_erlang_phash(),
     ok = t_bif_erlang_hash(),
-
     ok.
 
 t_bif_erlang_phash2() ->
-
     39679005 = erlang:phash2(#{}),
-    78942764 = erlang:phash2(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 }),
-    37338230 = erlang:phash2(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} }),
-    14363616 = erlang:phash2(#{ 1 => a }),
-    51612236 = erlang:phash2(#{ a => 1 }),
+    33667975 = erlang:phash2(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 }), % 78942764
+    95332690 = erlang:phash2(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} }), % 37338230
+    108954384 = erlang:phash2(#{ 1 => a }), % 14363616
+    59617982 = erlang:phash2(#{ a => 1 }), % 51612236
 
-    37468437 = erlang:phash2(#{{} => <<>>}),
-    44049159 = erlang:phash2(#{<<>> => {}}),
+    42770201 = erlang:phash2(#{{} => <<>>}), % 37468437
+    71687700 = erlang:phash2(#{<<>> => {}}), % 44049159
 
     M0 = #{ a => 1, "key" => <<"value">> },
     M1 = maps:remove("key",M0),
     M2 = M1#{ "key" => <<"value">> },
 
-    118679416 = erlang:phash2(M0),
-    51612236  = erlang:phash2(M1),
-    118679416 = erlang:phash2(M2),
+    70249457 = erlang:phash2(M0), % 118679416
+    59617982 = erlang:phash2(M1), % 51612236
+    70249457 = erlang:phash2(M2), % 118679416
     ok.
 
 t_bif_erlang_phash() ->
     Sz = 1 bsl 32,
-    268440612  = erlang:phash(#{},Sz),
-    1196461908 = erlang:phash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz),
-    3944426064 = erlang:phash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz),
-    1394238263 = erlang:phash(#{ 1 => a },Sz),
-    4066388227 = erlang:phash(#{ a => 1 },Sz),
+    1113425985 = erlang:phash(#{},Sz), % 268440612
+    1510068139 = erlang:phash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz), % 1196461908
+    3182345590 = erlang:phash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz), % 3944426064
+    2927531828 = erlang:phash(#{ 1 => a },Sz), % 1394238263
+    1670235874 = erlang:phash(#{ a => 1 },Sz), % 4066388227
 
-    1578050717 = erlang:phash(#{{} => <<>>},Sz),
-    1578050717 = erlang:phash(#{<<>> => {}},Sz), % yep, broken
+    3935089469 = erlang:phash(#{{} => <<>>},Sz), % 1578050717
+    71692856   = erlang:phash(#{<<>> => {}},Sz), % 1578050717
 
     M0 = #{ a => 1, "key" => <<"value">> },
     M1 = maps:remove("key",M0),
     M2 = M1#{ "key" => <<"value">> },
 
-    3590546636 = erlang:phash(M0,Sz),
-    4066388227 = erlang:phash(M1,Sz),
-    3590546636 = erlang:phash(M2,Sz),
+    2620391445 = erlang:phash(M0,Sz), % 3590546636
+    1670235874 = erlang:phash(M1,Sz), % 4066388227
+    2620391445 = erlang:phash(M2,Sz), % 3590546636
     ok.
 
 t_bif_erlang_hash() ->
     Sz = 1 bsl 27 - 1,
-    5158      = erlang:hash(#{},Sz),
-    71555838  = erlang:hash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz),
-    5497225   = erlang:hash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz),
-    126071654 = erlang:hash(#{ 1 => a },Sz),
-    126426236 = erlang:hash(#{ a => 1 },Sz),
+    39684169 = erlang:hash(#{},Sz),  % 5158
+    33673142 = erlang:hash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz), % 71555838
+    95337869 = erlang:hash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz), % 5497225
+    108959561 = erlang:hash(#{ 1 => a },Sz), % 126071654
+    59623150 = erlang:hash(#{ a => 1 },Sz), % 126426236
 
-    101655720 = erlang:hash(#{{} => <<>>},Sz),
-    101655720 = erlang:hash(#{<<>> => {}},Sz), % yep, broken
+    42775386 = erlang:hash(#{{} => <<>>},Sz), % 101655720
+    71692856 = erlang:hash(#{<<>> => {}},Sz), % 101655720
 
     M0 = #{ a => 1, "key" => <<"value">> },
     M1 = maps:remove("key",M0),
     M2 = M1#{ "key" => <<"value">> },
 
-    38260486  = erlang:hash(M0,Sz),
-    126426236 = erlang:hash(M1,Sz),
-    38260486  = erlang:hash(M2,Sz),
+    70254632 = erlang:hash(M0,Sz), % 38260486
+    59623150 = erlang:hash(M1,Sz), % 126426236
+    70254632 = erlang:hash(M2,Sz), % 38260486
     ok.
 
-
 t_map_encode_decode(Config) when is_list(Config) ->
     <<131,116,0,0,0,0>> = erlang:term_to_binary(#{}),
     Pairs = [
@@ -895,39 +899,42 @@ t_map_encode_decode(Config) when is_list(Config) ->
 map_encode_decode_and_match([{K,V}|Pairs], EncodedPairs, M0) ->
     M1 = maps:put(K,V,M0),
     B0 = erlang:term_to_binary(M1),
-    Ls = lists:sort(fun(A,B) -> erts_internal:cmp_term(A,B) < 0 end, [{K, erlang:term_to_binary(K), erlang:term_to_binary(V)}|EncodedPairs]),
-    %% sort Ks and Vs according to term spec, then match it
-    KVbins = lists:foldr(fun({_,Kbin,Vbin}, Acc) -> [Kbin,Vbin | Acc] end, [], Ls),
-    ok = match_encoded_map(B0, length(Ls), KVbins),
+    Ls = [{erlang:term_to_binary(K), erlang:term_to_binary(V)}|EncodedPairs],
+    ok = match_encoded_map(B0, length(Ls), Ls),
     %% decode and match it
     M1 = erlang:binary_to_term(B0),
     map_encode_decode_and_match(Pairs,Ls,M1);
 map_encode_decode_and_match([],_,_) -> ok.
 
 match_encoded_map(<<131,116,Size:32,Encoded/binary>>,Size,Items) ->
-    match_encoded_map(Encoded,Items);
+    match_encoded_map_stripped_size(Encoded,Items,Items);
 match_encoded_map(_,_,_) -> no_match_size.
 
-match_encoded_map(<<>>,[]) -> ok;
-match_encoded_map(Bin,[<<131,Item/binary>>|Items]) ->
-    Size = erlang:byte_size(Item),
-    <<EncodedTerm:Size/binary, Bin1/binary>> = Bin,
-    EncodedTerm = Item, %% Asssert
-    match_encoded_map(Bin1,Items).
+match_encoded_map_stripped_size(<<>>,_,_) -> ok;
+match_encoded_map_stripped_size(B0,[{<<131,K/binary>>,<<131,V/binary>>}|Items],Ls) ->
+    Ksz = byte_size(K),
+    Vsz = byte_size(V),
+    case B0 of
+	<<K:Ksz/binary,V:Vsz/binary,B1/binary>> ->
+	    match_encoded_map_stripped_size(B1,Ls,Ls);
+	_ ->
+	    match_encoded_map_stripped_size(B0,Items,Ls)
+    end;
+match_encoded_map_stripped_size(_,[],_) -> fail.
 
 
 t_bif_map_to_list(Config) when is_list(Config) ->
     [] = maps:to_list(#{}),
-    [{a,1},{b,2}] = maps:to_list(#{a=>1,b=>2}),
-    [{a,1},{b,2},{c,3}] = maps:to_list(#{c=>3,a=>1,b=>2}),
-    [{a,1},{b,2},{g,3}] = maps:to_list(#{g=>3,a=>1,b=>2}),
-    [{a,1},{b,2},{g,3},{"c",4}] = maps:to_list(#{g=>3,a=>1,b=>2,"c"=>4}),
-    [{3,v2},{hi,v4},{{hi,3},v5},{"hi",v3},{<<"hi">>,v1}] = maps:to_list(#{
-	    <<"hi">>=>v1,3=>v2,"hi"=>v3,hi=>v4,{hi,3}=>v5}),
-
-    [{3,v7},{hi,v9},{{hi,3},v10},{"hi",v8},{<<"hi">>,v6}] = maps:to_list(#{
-	    <<"hi">>=>v1,3=>v2,"hi"=>v3,hi=>v4,{hi,3}=>v5,
-	    <<"hi">>=>v6,3=>v7,"hi"=>v8,hi=>v9,{hi,3}=>v10}),
+    [{a,1},{b,2}] = lists:sort(maps:to_list(#{a=>1,b=>2})),
+    [{a,1},{b,2},{c,3}] = lists:sort(maps:to_list(#{c=>3,a=>1,b=>2})),
+    [{a,1},{b,2},{g,3}] = lists:sort(maps:to_list(#{g=>3,a=>1,b=>2})),
+    [{a,1},{b,2},{g,3},{"c",4}] = lists:sort(maps:to_list(#{g=>3,a=>1,b=>2,"c"=>4})),
+    [{3,v2},{hi,v4},{{hi,3},v5},{"hi",v3},{<<"hi">>,v1}] =
+	lists:sort(maps:to_list(#{<<"hi">>=>v1,3=>v2,"hi"=>v3,hi=>v4,{hi,3}=>v5})),
+
+    [{3,v7},{hi,v9},{{hi,3},v10},{"hi",v8},{<<"hi">>,v6}] =
+	lists:sort(maps:to_list(#{<<"hi">>=>v1,3=>v2,"hi"=>v3,hi=>v4,{hi,3}=>v5,
+				  <<"hi">>=>v6,3=>v7,"hi"=>v8,hi=>v9,{hi,3}=>v10})),
 
     %% error cases
     {'EXIT', {badarg,_}} = (catch maps:to_list(id(a))),
diff --git a/lib/hipe/rtl/hipe_tagscheme.erl b/lib/hipe/rtl/hipe_tagscheme.erl
index c27c682915..990d01e190 100644
--- a/lib/hipe/rtl/hipe_tagscheme.erl
+++ b/lib/hipe/rtl/hipe_tagscheme.erl
@@ -109,6 +109,7 @@
 -define(TAG_HEADER_REFC_BIN,((16#8 bsl ?TAG_PRIMARY_SIZE) bor ?TAG_PRIMARY_HEADER)).
 -define(TAG_HEADER_HEAP_BIN,((16#9 bsl ?TAG_PRIMARY_SIZE) bor ?TAG_PRIMARY_HEADER)).
 -define(TAG_HEADER_SUB_BIN, ((16#A bsl ?TAG_PRIMARY_SIZE) bor ?TAG_PRIMARY_HEADER)).
+-define(TAG_HEADER_HASHMAP, ((16#B bsl ?TAG_PRIMARY_SIZE) bor ?TAG_PRIMARY_HEADER)).
 -define(TAG_HEADER_EXTERNAL_PID, ((16#C bsl ?TAG_PRIMARY_SIZE) bor ?TAG_PRIMARY_HEADER)).
 -define(TAG_HEADER_EXTERNAL_PORT,((16#D bsl ?TAG_PRIMARY_SIZE) bor ?TAG_PRIMARY_HEADER)).
 -define(TAG_HEADER_EXTERNAL_REF, ((16#E bsl ?TAG_PRIMARY_SIZE) bor ?TAG_PRIMARY_HEADER)).
@@ -257,11 +258,16 @@ test_tuple_N(X, N, TrueLab, FalseLab, Pred) ->
 test_map(X, TrueLab, FalseLab, Pred) ->
   Tmp = hipe_rtl:mk_new_reg_gcsafe(),
   HalfTrueLab = hipe_rtl:mk_new_label(),
+  OrHashmapLab = hipe_rtl:mk_new_label(),
   MapMask = ?TAG_HEADER_MASK,
   [test_is_boxed(X, hipe_rtl:label_name(HalfTrueLab), FalseLab, Pred),
    HalfTrueLab,
    get_header(Tmp, X),
-   mask_and_compare(Tmp, MapMask, ?TAG_HEADER_MAP, TrueLab, FalseLab, Pred)].
+   mask_and_compare(Tmp, MapMask, ?TAG_HEADER_MAP,
+		    TrueLab, hipe_rtl:label_name(OrHashmapLab), Pred),
+   OrHashmapLab,
+   mask_and_compare(Tmp, MapMask, ?TAG_HEADER_HASHMAP, TrueLab, FalseLab, Pred)
+  ].
 
 test_ref(X, TrueLab, FalseLab, Pred) ->
   Hdr = hipe_rtl:mk_new_reg_gcsafe(),
@@ -360,16 +366,22 @@ test_matchstate(X, TrueLab, FalseLab, Pred) ->
 test_bitstr(X, TrueLab, FalseLab, Pred) ->
   Tmp = hipe_rtl:mk_new_reg_gcsafe(),
   HalfTrueLab = hipe_rtl:mk_new_label(),
+  AndNotHashmapLab = hipe_rtl:mk_new_label(),
   Mask = ?TAG_HEADER_MASK - ?BINARY_XXX_MASK,
   [test_is_boxed(X, hipe_rtl:label_name(HalfTrueLab), FalseLab, Pred),
    HalfTrueLab,
    get_header(Tmp, X),
-   mask_and_compare(Tmp, Mask, ?TAG_HEADER_REFC_BIN, TrueLab, FalseLab, Pred)].
+   mask_and_compare(Tmp, Mask, ?TAG_HEADER_REFC_BIN,
+		    hipe_rtl:label_name(AndNotHashmapLab), FalseLab, Pred),
+   AndNotHashmapLab,
+   mask_and_compare(Tmp, ?TAG_HEADER_MASK, ?TAG_HEADER_HASHMAP, FalseLab, TrueLab, Pred)
+  ].
 
 test_binary(X, TrueLab, FalseLab, Pred) ->
   Tmp1 = hipe_rtl:mk_new_reg_gcsafe(),
   Tmp2 = hipe_rtl:mk_new_reg_gcsafe(),
   IsBoxedLab = hipe_rtl:mk_new_label(),
+  AndNotHashmapLab = hipe_rtl:mk_new_label(),
   IsBitStrLab = hipe_rtl:mk_new_label(),
   IsSubBinLab =  hipe_rtl:mk_new_label(),
   Mask = ?TAG_HEADER_MASK - ?BINARY_XXX_MASK,
@@ -377,7 +389,10 @@ test_binary(X, TrueLab, FalseLab, Pred) ->
    IsBoxedLab,
    get_header(Tmp1, X),
    mask_and_compare(Tmp1, Mask, ?TAG_HEADER_REFC_BIN,
-		    hipe_rtl:label_name(IsBitStrLab), FalseLab, Pred),
+		    hipe_rtl:label_name(AndNotHashmapLab), FalseLab, Pred),
+   AndNotHashmapLab,
+   mask_and_compare(Tmp1, ?TAG_HEADER_MASK, ?TAG_HEADER_HASHMAP,
+		    FalseLab, hipe_rtl:label_name(IsBitStrLab), Pred),
    IsBitStrLab,
    mask_and_compare(Tmp1, ?TAG_HEADER_MASK, ?TAG_HEADER_SUB_BIN,
 		    hipe_rtl:label_name(IsSubBinLab), TrueLab, 0.5),
diff --git a/lib/hipe/test/maps_SUITE_data/maps_map_sort_literals.erl b/lib/hipe/test/maps_SUITE_data/maps_map_sort_literals.erl
index 31abf15d49..ccacbfe5c8 100644
--- a/lib/hipe/test/maps_SUITE_data/maps_map_sort_literals.erl
+++ b/lib/hipe/test/maps_SUITE_data/maps_map_sort_literals.erl
@@ -10,23 +10,25 @@ test() ->
     false = #{ c => 1, b => 1, a => 1} < id(#{ c => 1, a => 1}),
 
     %% key order
-    true  = id(#{ a => 1 }) < id(#{ b => 1}),
-    false = id(#{ b => 1 }) < id(#{ a => 1}),
-    true  = id(#{ a => 1, b => 1, c => 1 }) < id(#{ b => 1, c => 1, d => 1}),
-    true  = id(#{ b => 1, c => 1, d => 1 }) > id(#{ a => 1, b => 1, c => 1}),
-    true  = id(#{ c => 1, b => 1, a => 1 }) < id(#{ b => 1, c => 1, d => 1}),
-    true  = id(#{ "a" => 1 }) < id(#{ <<"a">> => 1}),
-    false = id(#{ <<"a">> => 1 }) < id(#{ "a" => 1}),
-    false = id(#{ 1 => 1 }) < id(#{ 1.0 => 1}),
-    false = id(#{ 1.0 => 1 }) < id(#{ 1 => 1}),
+    true  = #{ a => 1 } < id(#{ b => 1}),
+    false = #{ b => 1 } < id(#{ a => 1}),
+    true  = #{ a => 1, b => 1, c => 1 } < id(#{ b => 1, c => 1, d => 1}),
+    true  = #{ b => 1, c => 1, d => 1 } > id(#{ a => 1, b => 1, c => 1}),
+    true  = #{ c => 1, b => 1, a => 1 } < id(#{ b => 1, c => 1, d => 1}),
+    true  = #{ "a" => 1 } < id(#{ <<"a">> => 1}),
+    false = #{ <<"a">> => 1 } < id(#{ "a" => 1}),
+    true  = #{ 1 => 1 } < id(#{ 1.0 => 1}),
+    false = #{ 1.0 => 1 } < id(#{ 1 => 1}),
 
     %% value order
-    true  = id(#{ a => 1 }) < id(#{ a => 2}),
-    false = id(#{ a => 2 }) < id(#{ a => 1}),
-    false = id(#{ a => 2, b => 1 }) < id(#{ a => 1, b => 3}),
-    true  = id(#{ a => 1, b => 1 }) < id(#{ a => 1, b => 3}),
+    true  = #{ a => 1 } < id(#{ a => 2}),
+    false = #{ a => 2 } < id(#{ a => 1}),
+    false = #{ a => 2, b => 1 } < id(#{ a => 1, b => 3}),
+    true  = #{ a => 1, b => 1 } < id(#{ a => 1, b => 3}),
+    false = #{ a => 1 } < id(#{ a => 1.0}),
+    false = #{ a => 1.0 } < id(#{ a => 1}),
 
-    true  = id(#{ "a" => "hi", b => 134 }) == id(#{ b => 134,"a" => "hi"}),
+    true  = #{ "a" => "hi", b => 134 } == id(#{ b => 134,"a" => "hi"}),
 
     %% lists:sort
 
@@ -34,7 +36,6 @@ test() ->
     [#{1:=ok},#{a:=ok},#{"a":=ok},#{<<"a">>:=ok}] = lists:sort([#{"a"=>ok},#{a=>ok},#{1=>ok},#{<<"a">>=>ok}]),
     [#{1:=3},#{a:=2},#{"a":=1},#{<<"a">>:=4}] = lists:sort(SortVs),
     [#{1:=3},#{a:=2},#{"a":=1},#{<<"a">>:=4}] = lists:sort(lists:reverse(SortVs)),
-
     ok.
 
 %% Use this function to avoid compile-time evaluation of an expression.
diff --git a/lib/kernel/src/erts_debug.erl b/lib/kernel/src/erts_debug.erl
index ef605d0bfe..17bee06b5e 100644
--- a/lib/kernel/src/erts_debug.erl
+++ b/lib/kernel/src/erts_debug.erl
@@ -33,7 +33,7 @@
 -export([breakpoint/2, disassemble/1, display/1, dist_ext_to_term/2,
          dump_monitors/1, dump_links/1, flat_size/1,
          get_internal_state/1, instructions/0, lock_counters/1,
-         same/2, set_internal_state/2]).
+         map_info/1, same/2, set_internal_state/2]).
 
 -spec breakpoint(MFA, Flag) -> non_neg_integer() when
       MFA :: {Module :: module(),
@@ -164,8 +164,10 @@ set_internal_state(_, _) ->
 
 -spec size(term()) -> non_neg_integer().
 
+-record(s, {seen, maps}).
+
 size(Term) ->
-    {Sum,_} = size(Term, gb_trees:empty(), 0),
+    {Sum,_} = size(Term, #s{seen=gb_trees:empty(),maps=[]}, 0),
     Sum.
 
 size([H|T]=Term, Seen0, Sum0) ->
@@ -209,10 +211,24 @@ tuple_size(I, Sz, Tuple, Seen0, Sum0) ->
     tuple_size(I+1, Sz, Tuple, Seen, Sum).
 
 map_size(Map,Seen0,Sum0) ->
-    Kt = erts_internal:map_to_tuple_keys(Map),
-    Vs = maps:values(Map),
-    {Sum1,Seen1} = size(Kt,Seen0,Sum0),
-    fold_size(Vs,Seen1,Sum1+length(Vs)+3).
+    %% Danger:
+    %% The internal nodes from erts_internal:map_hashmap_children/1
+    %% is not allowed to leak anywhere. They are only allowed in
+    %% containers (cons cells and tuples, not maps), in gc and
+    %% in erts_debug:same/2
+    case erts_internal:map_type(Map) of
+        flatmap ->
+            Kt = erts_internal:map_to_tuple_keys(Map),
+            Vs = maps:values(Map),
+            {Sum1,Seen1} = size(Kt,Seen0,Sum0),
+            fold_size(Vs,Seen1,Sum1+length(Vs)+3);
+        hashmap ->
+            Cs = erts_internal:map_hashmap_children(Map),
+            fold_size(Cs,Seen0,Sum0+length(Cs)+2);
+        hashmap_node ->
+            Cs = erts_internal:map_hashmap_children(Map),
+            fold_size(Cs,Seen0,Sum0+length(Cs)+1)
+    end.
 
 fun_size(Fun, Seen, Sum) ->
     case erlang:fun_info(Fun, type) of
@@ -229,13 +245,18 @@ fold_size([H|T], Seen0, Sum0) ->
     fold_size(T, Seen, Sum);
 fold_size([], Seen, Sum) -> {Sum,Seen}.
 
-remember_term(Term, Seen) ->
-    case gb_trees:lookup(Term, Seen) of
-	none -> gb_trees:insert(Term, [Term], Seen);
+remember_term(Term, #s{maps=Ms}=S) when is_map(Term) ->
+    case is_term_seen(Term, Ms) of
+        false -> S#s{maps=[Term|Ms]};
+        true  -> seen
+    end;
+remember_term(Term, #s{seen=T}=S) ->
+    case gb_trees:lookup(Term,T) of
+	none -> S#s{seen=gb_trees:insert(Term,[Term],T)};
 	{value,Terms} ->
 	    case is_term_seen(Term, Terms) of
-		false -> gb_trees:update(Term, [Term|Terms], Seen);
-		true -> seen
+		false -> S#s{seen=gb_trees:update(Term,[Term|Terms],T)};
+		true  -> seen
 	    end
     end.
 
@@ -313,3 +334,9 @@ cont_dis(File, {Addr,Str,MFA}, MFA) ->
     io:put_chars(File, binary_to_list(Str)),
     cont_dis(File, erts_debug:disassemble(Addr), MFA);
 cont_dis(_, {_,_,_}, _) -> ok.
+
+-spec map_info(Map) -> list() when
+      Map :: map().
+
+map_info(_) ->
+    erlang:nif_error(undef).
diff --git a/lib/mnesia/test/mnesia_trans_access_test.erl b/lib/mnesia/test/mnesia_trans_access_test.erl
index 237984978e..f906670296 100644
--- a/lib/mnesia/test/mnesia_trans_access_test.erl
+++ b/lib/mnesia/test/mnesia_trans_access_test.erl
@@ -930,20 +930,20 @@ index_update_bag(Config)when is_list(Config) ->
     [IPos] = mnesia_lib:val({Tab,index}),
     ITab = mnesia_lib:val({index_test,{index, IPos}}),
     io:format("~n Index ~p @ ~p => ~p ~n~n",[IPos,ITab, ets:tab2list(ITab)]),
-    ?match([{2,1},{2,2},{12,1}], ets:tab2list(ITab)),
+    ?match([{2,1},{2,2},{12,1}], lists:keysort(1,ets:tab2list(ITab))),
 
     ?match({atomic, ok}, mnesia:transaction(fun() -> mnesia:write(Rec5) end)),
     {atomic, R60} = mnesia:transaction(fun() -> mnesia:index_read(Tab, 2, ValPos) end),
     ?match([Rec1,Rec5,Rec2], lists:sort(R60)),
 
-    ?match([{2,1},{2,2},{12,1}], ets:tab2list(ITab)),
+    ?match([{2,1},{2,2},{12,1}], lists:keysort(1,ets:tab2list(ITab))),
 
     ?match({atomic, ok}, mnesia:transaction(fun() -> mnesia:delete_object(Rec3) end)),
     {atomic, R61} = mnesia:transaction(fun() -> mnesia:index_read(Tab, 2, ValPos) end),
     ?match([Rec1,Rec5,Rec2], lists:sort(R61)),
     {atomic, R62} = mnesia:transaction(fun() -> mnesia:index_read(Tab,12, ValPos) end),
     ?match([], lists:sort(R62)),
-    ?match([{2,1},{2,2}], ets:tab2list(ITab)),
+    ?match([{2,1},{2,2}], lists:keysort(1,ets:tab2list(ITab))),
 
     %% reset for rest of testcase
     ?match({atomic, ok}, mnesia:transaction(fun() -> mnesia:write(Rec3) end)),
diff --git a/lib/stdlib/src/io_lib.erl b/lib/stdlib/src/io_lib.erl
index e90cda0533..3378d668a5 100644
--- a/lib/stdlib/src/io_lib.erl
+++ b/lib/stdlib/src/io_lib.erl
@@ -287,6 +287,8 @@ write([H|T], D) ->
     end;
 write(F, _D) when is_function(F) ->
     erlang:fun_to_list(F);
+write(Term, D) when is_map(Term) ->
+    write_map(Term, D);
 write(T, D) when is_tuple(T) ->
     if
 	D =:= 1 -> "{...}";
@@ -295,9 +297,7 @@ write(T, D) when is_tuple(T) ->
 	     [write(element(1, T), D-1)|
               write_tail(tl(tuple_to_list(T)), D-1, $,)],
 	     $}]
-    end;
-%write(Term, D)  when is_map(Term) -> write_map(Term, D);
-write(Term, D) -> write_map(Term, D).
+    end.
 
 %% write_tail(List, Depth, CharacterBeforeDots)
 %%  Test the terminating case first as this looks better with depth.
diff --git a/lib/stdlib/test/qlc_SUITE.erl b/lib/stdlib/test/qlc_SUITE.erl
index 4173a40d14..0b7b96da8e 100644
--- a/lib/stdlib/test/qlc_SUITE.erl
+++ b/lib/stdlib/test/qlc_SUITE.erl
@@ -3418,7 +3418,8 @@ lookup2(Config) when is_list(Config) ->
            end, [{1},{2}])">>
 
        ],
-    ?line run(Config, Ts),
+
+    ok = run(Config, Ts),
 
     TsR = [
        %% is_record/2,3:
@@ -3456,7 +3457,8 @@ lookup2(Config) when is_list(Config) ->
          end, [{keypos,1}], [#r{}])">>
 
        ],
-    ?line run(Config, <<"-record(r, {a}).\n">>, TsR),
+
+    ok = run(Config, <<"-record(r, {a}).\n">>, TsR),
 
     Ts2 = [
        <<"etsc(fun(E) ->
@@ -3566,7 +3568,6 @@ lookup2(Config) when is_list(Config) ->
                        [{1,2},{2,2}] = qlc:e(Q),
                        [2] = lookup_keys(Q)
                end, [{keypos,1}], [{1},{2},{3}])">>,
-
        <<"%% Matchspec only. No cache.
           etsc(fun(E) ->
                        Q = qlc:q([{X,Y} ||
@@ -3578,7 +3579,7 @@ lookup2(Config) when is_list(Config) ->
                                {generate,_,
                                 {table,{ets,_,[_,[{traverse,_}]]}}}],[]} = 
                                        i(Q),
-                       [{1,2},{1,3},{2,2},{2,3}] = qlc:e(Q),
+                       [{1,2},{1,3},{2,2},{2,3}] = lists:sort(qlc:e(Q)),
                        false = lookup_keys(Q)
                end, [{keypos,1}], [{1},{2},{3}])">>,
        <<"%% Matchspec only. Cache
@@ -3592,7 +3593,7 @@ lookup2(Config) when is_list(Config) ->
                             {generate,_,{qlc,_,
                            [{generate,_,{table,{ets,_,[_,[{traverse,_}]]}}}],
                           [{cache,ets}]}}],[]} = i(Q),
-                       [{1,2},{1,3},{2,2},{2,3}] = qlc:e(Q),
+                       [{1,2},{1,3},{2,2},{2,3}] = lists:sort(qlc:e(Q)),
                        false = lookup_keys(Q)
                end, [{keypos,1}], [{1},{2},{3}])">>,
        <<"%% An empty list. Always unique and cached.
@@ -3645,7 +3646,7 @@ lookup2(Config) when is_list(Config) ->
 
       ],
 
-    ?line run(Config, Ts2),
+    ok = run(Config, Ts2),
 
     LTs = [
        <<"etsc(fun(E) ->
@@ -3677,7 +3678,8 @@ lookup2(Config) when is_list(Config) ->
                end, [{1,a},{2,b}])">>
 
        ],
-    ?line run(Config, LTs),
+
+    ok = run(Config, LTs),
 
     ok.