From 8c796b86a081b8665fce7b36a17efb6f46884666 Mon Sep 17 00:00:00 2001
From: Hans Bolinder <hasse@erlang.org>
Date: Tue, 1 Mar 2016 15:47:12 +0100
Subject: dialyzer: Optimize the evaluation of SCC:s in module typesig

The evaluation of a single SCC has been optimized.

The parallelism when evaluating a single SCC has been removed.
---
 lib/dialyzer/src/dialyzer_typesig.erl | 251 +++++++++-------------------------
 1 file changed, 66 insertions(+), 185 deletions(-)

diff --git a/lib/dialyzer/src/dialyzer_typesig.erl b/lib/dialyzer/src/dialyzer_typesig.erl
index 50fcbc555b..dcf0947f3e 100644
--- a/lib/dialyzer/src/dialyzer_typesig.erl
+++ b/lib/dialyzer/src/dialyzer_typesig.erl
@@ -2,7 +2,7 @@
 %%-----------------------------------------------------------------------
 %% %CopyrightBegin%
 %%
-%% Copyright Ericsson AB 2006-2015. All Rights Reserved.
+%% Copyright Ericsson AB 2006-2016. All Rights Reserved.
 %%
 %% Licensed under the Apache License, Version 2.0 (the "License");
 %% you may not use this file except in compliance with the License.
@@ -66,9 +66,11 @@
 %%-----------------------------------------------------------------------------
 
 -type dep()      :: integer().  %% type variable names used as constraint ids
+-type deps()     :: ordsets:ordset(dep()).
+
 -type type_var() :: erl_types:erl_type(). %% actually: {'c','var',_,_}
 
--record(fun_var, {'fun' :: fun((_) -> erl_types:erl_type()), deps :: [dep()],
+-record(fun_var, {'fun' :: fun((_) -> erl_types:erl_type()), deps :: deps(),
 		  origin :: integer() | 'undefined'}).
 
 -type constr_op()    :: 'eq' | 'sub'.
@@ -77,20 +79,22 @@
 -record(constraint, {lhs  :: erl_types:erl_type(),
 		     op   :: constr_op(),
 		     rhs  :: fvar_or_type(),
-		     deps :: [dep()]}).
+		     deps :: deps()}).
 
 -type constraint() :: #constraint{}.
 
+-type mask() :: ordsets:ordset(non_neg_integer()).
+
 -record(constraint_list, {type :: 'conj' | 'disj',
 			  list :: [constr()],
-			  deps :: [dep()],
-                          masks = [] :: [{dep(),[non_neg_integer()]}] |
-                                  {'d',dict:dict(dep(), [non_neg_integer()])},
+                          deps :: deps(),
+                          masks = [] :: [{dep(),mask()}] |
+                                  {'d',dict:dict(dep(), mask())},
 			  id   :: {'list', dep()} | 'undefined'}).
 
 -type constraint_list() :: #constraint_list{}.
 
--record(constraint_ref, {id :: type_var(), deps :: [dep()]}).
+-record(constraint_ref, {id :: type_var(), deps :: deps()}).
 
 -type constraint_ref() :: #constraint_ref{}.
 
@@ -99,32 +103,29 @@
 -type types() :: erl_types:type_table().
 
 -type typesig_scc()    :: [{mfa(), {cerl:c_var(), cerl:c_fun()}, types()}].
--type typesig_funmap() :: [{type_var(), type_var()}]. %% Orddict
+-type typesig_funmap() :: #{type_var() => type_var()}.
 
 -type prop_types() :: dict:dict(label(), types()).
 
--type dict_or_ets() :: {'d', prop_types()} | {'e', ets:tid()}.
-
--record(state, {callgraph                    :: dialyzer_callgraph:callgraph()
-                                              | 'undefined',
-		cs          = []                :: [constr()],
-		cmap        = {'d', dict:new()} :: dict_or_ets(),
-		fun_map     = []                :: typesig_funmap(),
-		fun_arities = dict:new()        :: dict:dict(type_var(), arity()),
-		in_match    = false             :: boolean(),
-		in_guard    = false             :: boolean(),
-		module                          :: module(),
-		name_map    = dict:new()        :: dict:dict(mfa(),
-                                                             cerl:c_fun()),
-		next_label  = 0                 :: label(),
-		self_rec                        :: 'false' | erl_types:erl_type(),
-		plt                             :: dialyzer_plt:plt()
-                                                 | 'undefined',
-		prop_types  = {'d', dict:new()} :: dict_or_ets(),
-		records     = dict:new()        :: types(),
-		scc         = []                :: [type_var()],
-		mfas                            :: [tuple()],
-                solvers     = []                :: [solver()]
+-record(state, {callgraph                :: dialyzer_callgraph:callgraph()
+                                          | 'undefined',
+		cs          = []         :: [constr()],
+		cmap        = dict:new() :: dict:dict(), % FIXME
+		fun_map     = maps:new() :: typesig_funmap(),
+		fun_arities = dict:new() :: dict:dict(type_var(), arity()),
+		in_match    = false      :: boolean(),
+		in_guard    = false      :: boolean(),
+		module                   :: module(),
+		name_map    = dict:new() :: dict:dict(mfa(), cerl:c_fun()),
+		next_label  = 0          :: label(),
+		self_rec                 :: 'false' | erl_types:erl_type(),
+		plt                      :: dialyzer_plt:plt()
+                                          | 'undefined',
+		prop_types  = dict:new() :: dict:dict(), % FIXME
+		records     = dict:new() :: types(),
+		scc         = []         :: ordsets:ordset(type_var()),
+		mfas                     :: [tuple()], % FIXME?
+                solvers     = []         :: [solver()]
 	       }).
 
 -type state() :: #state{}.
@@ -1802,12 +1803,16 @@ solve([Fun], State) ->
 solve([_|_] = SCC, State) ->
   ?debug("============ Analyzing SCC: ~w ===========\n",
 	 [[debug_lookup_name(F) || F <- SCC]]),
-  {Parallel, NewState} =
-    case parallel_split(SCC) of
-      false -> {false, State};
-      SplitSCC -> {SplitSCC, minimize_state(State)}
-    end,
-  solve_scc(SCC, Parallel, map_new(), NewState, false).
+  Users = comp_users(SCC, State),
+  solve_scc(SCC, map_new(), State, Users, _ToSolve=SCC, false).
+
+comp_users(SCC, State) ->
+  Vars0 = [{Fun, state__get_rec_var(Fun, State)} || Fun <- SCC],
+  Vars = lists:sort([t_var_name(Var) || {_, {ok, Var}} <- Vars0]),
+  family([{t_var(V), F} ||
+           F <- SCC,
+           V <- ordsets:intersection(get_deps(state__get_cs(F, State)),
+                                     Vars)]).
 
 solve_fun(Fun, FunMap, State) ->
   Cs = state__get_cs(Fun, State),
@@ -1822,7 +1827,7 @@ solve_fun(Fun, FunMap, State) ->
 	       end,
   enter_type(Fun, NewType, NewFunMap1).
 
-solve_scc(SCC, Parallel, Map, State, TryingUnit) ->
+solve_scc(SCC, Map, State, Users, ToSolve, TryingUnit) ->
   Vars0 = [{Fun, state__get_rec_var(Fun, State)} || Fun <- SCC],
   Vars = [Var || {_, {ok, Var}} <- Vars0],
   Funs = [Fun || {Fun, {ok, _}} <- Vars0],
@@ -1830,16 +1835,13 @@ solve_scc(SCC, Parallel, Map, State, TryingUnit) ->
   RecTypes = [t_limit(Type, ?TYPE_LIMIT) || Type <- Types],
   CleanMap = lists:foldl(fun(Fun, AccFunMap) ->
 			     erase_type(t_var_name(Fun), AccFunMap)
-			 end, Map, SCC),
+			 end, Map, ToSolve),
   Map1 = enter_type_lists(Vars, RecTypes, CleanMap),
   ?debug("Checking SCC: ~w\n", [[debug_lookup_name(F) || F <- SCC]]),
-  FunSet = ordsets:from_list([t_var_name(F) || F <- SCC]),
-  Map2 =
-    case Parallel of
-      false -> solve_whole_scc(SCC, Map1, State);
-      SplitSCC -> solve_whole_scc_parallel(SplitSCC, Map1, State)
-    end,
-  case maps_are_equal(Map2, Map, FunSet) of
+  SolveFun = fun(X, Y) -> scc_fold_fun(X, Y, State) end,
+  Map2 = lists:foldl(SolveFun, Map1, ToSolve),
+  Updated = updated_vars_only(Vars, Map, Map2),
+  case Updated =:= [] of
     true ->
       ?debug("SCC ~w reached fixpoint\n", [SCC]),
       NewTypes = unsafe_lookup_type_list(Funs, Map2),
@@ -1852,130 +1854,21 @@ solve_scc(SCC, Parallel, Map, State, TryingUnit) ->
 	       true -> t_fun(t_fun_args(T), t_unit())
 	     end || T <- NewTypes],
 	  Map3 = enter_type_lists(Funs, UnitTypes, Map2),
-	  solve_scc(SCC, Parallel, Map3, State, true);
+	  solve_scc(SCC, Map3, State, Users, SCC, true);
 	false ->
-	  case Parallel of
-	    false -> true;
-	    _ -> dispose_state(State)
-	  end,
 	  Map2
       end;
     false ->
       ?debug("SCC ~w did not reach fixpoint\n", [SCC]),
-      solve_scc(SCC, Parallel, Map2, State, TryingUnit)
-  end.
-
-solve_whole_scc(SCC, Map, State) ->
-  SolveFun = fun(X, Y) -> scc_fold_fun(X, Y, State) end,
-  lists:foldl(SolveFun, Map, SCC).
-
-%%------------------------------------------------------------------------------
-
--define(worth_it, 42).
-
-parallel_split(SCC) ->
-  Length = length(SCC),
-  case Length > 2*?worth_it of
-    false -> false;
-    true ->
-      case min(dialyzer_utils:parallelism(), 8) of
-	1 -> false;
-	CPUs ->
-	  FullShare = Length div CPUs + 1,
-	  Unit = max(FullShare, ?worth_it),
-	  split(SCC, Unit, [])
-      end
-  end.
-
-minimize_state(#state{
-		  cmap        = {d, CMap},
-		  fun_map     = FunMap,
-		  fun_arities = FunArities,
-		  self_rec    = SelfRec,
-		  prop_types  = {d, PropTypes},
-                  solvers     = Solvers
-		 }) ->
-  Opts = [{read_concurrency, true}],
-  ETSCMap = ets:new(cmap, Opts),
-  ETSPropTypes = ets:new(prop_types, Opts),
-  true = ets:insert(ETSCMap, dict:to_list(CMap)),
-  true = ets:insert(ETSPropTypes, dict:to_list(PropTypes)),
-  #state
-    {cmap        = {e, ETSCMap},
-     fun_map     = FunMap,
-     fun_arities = FunArities,
-     self_rec    = SelfRec,
-     prop_types  = {e, ETSPropTypes},
-     solvers     = Solvers,
-     callgraph   = undefined,
-     plt         = undefined,
-     mfas        = []
-    }.
-
-dispose_state(#state{cmap = {e, ETSCMap},
-		     prop_types = {e, ETSPropTypes}}) ->
-  true = ets:delete(ETSCMap),
-  true = ets:delete(ETSPropTypes).
-
-solve_whole_scc_parallel(SplitSCC, Map, State) ->
-  Workers = spawn_workers(SplitSCC, Map, State),
-  wait_results(Workers, Map, fold_res_fun(State)).
-
-spawn_workers(SplitSCC, Map, State) ->
-  Spawner = solve_scc_spawner(self(), Map, State),
-  lists:foreach(Spawner, SplitSCC),
-  length(SplitSCC).
-
-wait_results(0, Map, _FoldResFun) ->
-  Map;
-wait_results(Pending, Map, FoldResFun) ->
-  Res = receive_scc_result(),
-  NewMap = lists:foldl(FoldResFun, Map, Res),
-  wait_results(Pending-1, NewMap, FoldResFun).
-
-solve_scc_spawner(Parent, Map, State) ->
-  fun(SCCPart) ->
-      spawn_link(fun() -> solve_scc_worker(Parent, SCCPart, Map, State) end)
+      ToSolve1 = affected(Updated, Users),
+      solve_scc(SCC, Map2, State, Users, ToSolve1, TryingUnit)
   end.
 
-split([], _Unit, Acc) ->
-  Acc;
-split(List, Unit, Acc) ->
-  {Taken, Rest} =
-    try
-      lists:split(Unit, List)
-    catch
-      _:_ -> {List, []}
-    end,
-  split(Rest, Unit, [Taken|Acc]).
-
-solve_scc_worker(Parent, SCCPart, Map, State) ->
-  SolveFun = fun(X, Y) -> scc_fold_fun(X, Y, State) end,
-  FinalMap = lists:foldl(SolveFun, Map, SCCPart),
-  Res =
-    [{F, t_limit(unsafe_lookup_type(F, FinalMap), ?TYPE_LIMIT)} ||
-      F <- SCCPart],
-  send_scc_result(Parent, Res).
-
-fold_res_fun(State) ->
-  fun({F, Type}, Map) ->
-      case state__get_rec_var(F, State) of
-	{ok, R} ->
-	  enter_type(R, Type, enter_type(F, Type, Map));
-	error ->
-	  enter_type(F, Type, Map)
-      end
-  end.
-
-receive_scc_result() ->
-    receive
-      {scc_fun, Res} -> Res
-    end.
-
-send_scc_result(Parent, Res) ->
-  Parent ! {scc_fun, Res}.
-
-%%------------------------------------------------------------------------------
+affected(Updated, Users) ->
+  lists:umerge([case lists:keyfind(V, 1, Users) of
+                  {V, Vs} -> Vs;
+                  false -> []
+                end || V <- Updated]).
 
 scc_fold_fun(F, FunMap, State) ->
   Deps = get_deps(state__get_cs(F, State)),
@@ -2322,7 +2215,7 @@ report_detected_loop(_) ->
 add_mask_to_flags(Flags, [Im|M], I, L) when I > Im ->
   add_mask_to_flags(Flags, M, I, [Im|L]);
 add_mask_to_flags(Flags, [_|M], _I, L) ->
-  {lists:umerge(Flags, M), lists:reverse(L)}.
+  {lists:umerge(M, Flags), lists:reverse(L)}.
 
 get_mask(V, {d, Masks}) ->
   case dict:find(V, Masks) of
@@ -2830,7 +2723,7 @@ new_state(SCC0, NextLabel, CallGraph, Plt, PropTypes, Solvers) ->
       _Many -> false
     end,
   #state{callgraph = CallGraph, name_map = NameMap, next_label = NextLabel,
-	 prop_types = {d, PropTypes}, plt = Plt, scc = ordsets:from_list(SCC),
+	 prop_types = PropTypes, plt = Plt, scc = ordsets:from_list(SCC),
 	 mfas = MFAs, self_rec = SelfRec, solvers = Solvers}.
 
 state__set_rec_dict(State, RecDict) ->
@@ -2926,21 +2819,14 @@ state__plt(#state{plt = PLT}) ->
 state__new_constraint_context(State) ->
   State#state{cs = []}.
 
-state__prop_domain(FunLabel, #state{prop_types = {e, ETSPropTypes}}) ->
-  try ets:lookup_element(ETSPropTypes, FunLabel, 2) of
-      {_Range_Fun, Dom} -> {ok, Dom};
-      FunType -> {ok, t_fun_args(FunType)}
-  catch
-    _:_ -> error
-  end;
-state__prop_domain(FunLabel, #state{prop_types = {d, PropTypes}}) ->
+state__prop_domain(FunLabel, #state{prop_types = PropTypes}) ->
  case dict:find(FunLabel, PropTypes) of
     error -> error;
     {ok, {_Range_Fun, Dom}} -> {ok, Dom};
     {ok, FunType} -> {ok, t_fun_args(FunType)}
   end.
 
-state__add_prop_constrs(Tree, #state{prop_types = {d, PropTypes}} = State) ->
+state__add_prop_constrs(Tree, #state{prop_types = PropTypes} = State) ->
   Label = cerl_trees:get_label(Tree),
   case dict:find(Label, PropTypes) of
     error -> State;
@@ -3003,13 +2889,11 @@ state__mk_vars(N, #state{next_label = NL} = State) ->
   Vars = [t_var(X) || X <- lists:seq(NL, NewLabel-1)],
   {State#state{next_label = NewLabel}, Vars}.
 
-state__store_constrs(Id, Cs, #state{cmap = {d, Dict}} = State) ->
+state__store_constrs(Id, Cs, #state{cmap =  Dict} = State) ->
   NewDict = dict:store(Id, Cs, Dict),
-  State#state{cmap = {d, NewDict}}.
+  State#state{cmap = NewDict}.
 
-state__get_cs(Var, #state{cmap = {e, ETSDict}}) ->
-  ets:lookup_element(ETSDict, Var, 2);
-state__get_cs(Var, #state{cmap = {d, Dict}}) ->
+state__get_cs(Var, #state{cmap = Dict}) ->
   dict:fetch(Var, Dict).
 
 state__is_self_rec(Fun, #state{self_rec = SelfRec}) ->
@@ -3019,15 +2903,12 @@ state__store_funs(Vars0, Funs0, #state{fun_map = Map} = State) ->
   debug_make_name_map(Vars0, Funs0),
   Vars = mk_var_list(Vars0),
   Funs = mk_var_list(Funs0),
-  NewMap = lists:foldl(fun({Var, Fun}, MP) -> orddict:store(Var, Fun, MP) end,
+  NewMap = lists:foldl(fun({Var, Fun}, MP) -> maps:put(Fun, Var, MP) end,
 		       Map, lists:zip(Vars, Funs)),
   State#state{fun_map = NewMap}.
 
 state__get_rec_var(Fun, #state{fun_map = Map}) ->
-  case [V || {V, FV} <- Map, FV =:= Fun] of
-    [Var] -> {ok, Var};
-    [] -> error
-  end.
+  maps:find(Fun, Map).
 
 state__finalize(State) ->
   State1 = enumerate_constraints(State),
@@ -3094,13 +2975,13 @@ mk_fun_var(Fun, Types) ->
 
 -endif.
 
--spec get_deps(constr()) -> [dep()].
+-spec get_deps(constr()) -> deps().
 
 get_deps(#constraint{deps = D}) -> D;
 get_deps(#constraint_list{deps = D}) -> D;
 get_deps(#constraint_ref{deps = D}) -> D.
 
--spec find_constraint_deps([fvar_or_type()]) -> [dep()].
+-spec find_constraint_deps([fvar_or_type()]) -> deps().
 
 find_constraint_deps(List) ->
   ordsets:from_list(find_constraint_deps(List, [])).
-- 
cgit v1.2.3


From b623624a52852447d849bde9b15b3b22e5bbbec6 Mon Sep 17 00:00:00 2001
From: Hans Bolinder <hasse@erlang.org>
Date: Wed, 2 Mar 2016 15:08:19 +0100
Subject: dialyzer: Use maps instead of dict

Optimization: A few dictionaries are maps instead of dicts.
---
 lib/dialyzer/src/dialyzer_contracts.erl |  51 ++++++-----
 lib/dialyzer/src/dialyzer_dataflow.erl  |  75 ++++++++--------
 lib/dialyzer/src/dialyzer_typesig.erl   | 154 +++++++++++++++-----------------
 lib/hipe/cerl/erl_types.erl             |  27 +++---
 4 files changed, 149 insertions(+), 158 deletions(-)

diff --git a/lib/dialyzer/src/dialyzer_contracts.erl b/lib/dialyzer/src/dialyzer_contracts.erl
index 1895a98e96..116260778c 100644
--- a/lib/dialyzer/src/dialyzer_contracts.erl
+++ b/lib/dialyzer/src/dialyzer_contracts.erl
@@ -210,10 +210,10 @@ check_contract(Contract, SuccType) ->
 
 check_contract(#contract{contracts = Contracts}, SuccType, Opaques) ->
   try
-    Contracts1 = [{Contract, insert_constraints(Constraints, dict:new())}
+    Contracts1 = [{Contract, insert_constraints(Constraints)}
 		  || {Contract, Constraints} <- Contracts],
-    Contracts2 = [erl_types:t_subst(Contract, Dict)
-		  || {Contract, Dict} <- Contracts1],
+    Contracts2 = [erl_types:t_subst(Contract, Map)
+		  || {Contract, Map} <- Contracts1],
     GenDomains = [erl_types:t_fun_args(C) || C <- Contracts2],
     case check_domains(GenDomains) of
       error ->
@@ -344,15 +344,15 @@ process_contract({Contract, Constraints}, CallTypes0) ->
 	 [erl_types:t_to_string(ContArgsFun),
 	  erl_types:t_to_string(CallTypesFun)]),
   case solve_constraints(ContArgsFun, CallTypesFun, Constraints) of
-    {ok, VarDict} ->
-      {ok, erl_types:t_subst(erl_types:t_fun_range(Contract), VarDict)};
+    {ok, VarMap} ->
+      {ok, erl_types:t_subst(erl_types:t_fun_range(Contract), VarMap)};
     error -> error
   end.
 
 solve_constraints(Contract, Call, Constraints) ->
   %% First make sure the call follows the constraints
-  CDict = insert_constraints(Constraints, dict:new()),
-  Contract1 = erl_types:t_subst(Contract, CDict),
+  CMap = insert_constraints(Constraints),
+  Contract1 = erl_types:t_subst(Contract, CMap),
   %% Just a safe over-approximation.
   %% TODO: Find the types for type variables properly
   ContrArgs = erl_types:t_fun_args(Contract1),
@@ -360,7 +360,7 @@ solve_constraints(Contract, Call, Constraints) ->
   InfList = erl_types:t_inf_lists(ContrArgs, CallArgs),
   case erl_types:any_none_or_unit(InfList) of
     true -> error;
-    false -> {ok, CDict}
+    false -> {ok, CMap}
   end.
   %%Inf = erl_types:t_inf(Contract1, Call),
   %% Then unify with the constrained call type.
@@ -390,23 +390,26 @@ warn_spec_missing_fun({M, F, A} = MFA, Contracts) ->
   {?WARN_CONTRACT_SYNTAX, WarningInfo, {spec_missing_fun, [M, F, A]}}.
 
 %% This treats the "when" constraints. It will be extended, we hope.
-insert_constraints([{subtype, Type1, Type2}|Left], Dict) ->
+insert_constraints(Constraints) ->
+  insert_constraints(Constraints, maps:new()).
+
+insert_constraints([{subtype, Type1, Type2}|Left], Map) ->
   case erl_types:t_is_var(Type1) of
     true ->
       Name = erl_types:t_var_name(Type1),
-      Dict1 = case dict:find(Name, Dict) of
-		error ->
-		  dict:store(Name, Type2, Dict);
-		{ok, VarType} ->
-		  dict:store(Name, erl_types:t_inf(VarType, Type2), Dict)
-	      end,
-      insert_constraints(Left, Dict1);
+      Map1 = case maps:find(Name, Map) of
+               error ->
+                 maps:put(Name, Type2, Map);
+               {ok, VarType} ->
+                 maps:put(Name, erl_types:t_inf(VarType, Type2), Map)
+             end,
+      insert_constraints(Left, Map1);
     false ->
       %% A lot of things should change to add supertypes
       throw({error, io_lib:format("First argument of is_subtype constraint "
 				  "must be a type variable: ~p\n", [Type1])})
   end;
-insert_constraints([], Dict) -> Dict.
+insert_constraints([], Map) -> Map.
 
 -type types() :: erl_types:type_table().
 
@@ -476,7 +479,7 @@ initialize_constraints([], _MFA, _RecDict, _ExpTypes, _AllRecords, Acc) ->
 initialize_constraints([Constr|Rest], MFA, RecDict, ExpTypes, AllRecords, Acc) ->
   case Constr of
     {type, _, constraint, [{atom, _, is_subtype}, [Type1, Type2]]} ->
-      T1 = final_form(Type1, ExpTypes, MFA, AllRecords, dict:new()),
+      T1 = final_form(Type1, ExpTypes, MFA, AllRecords, maps:new()),
       Entry = {T1, Type2},
       initialize_constraints(Rest, MFA, RecDict, ExpTypes, AllRecords, [Entry|Acc]);
     {type, _, constraint, [{atom,_,Name}, List]} ->
@@ -487,7 +490,7 @@ initialize_constraints([Constr|Rest], MFA, RecDict, ExpTypes, AllRecords, Acc) -
 
 constraints_fixpoint(Constrs, MFA, RecDict, ExpTypes, AllRecords) ->
   VarDict =
-    constraints_to_dict(Constrs, MFA, RecDict, ExpTypes, AllRecords, dict:new()),
+    constraints_to_dict(Constrs, MFA, RecDict, ExpTypes, AllRecords, maps:new()),
   constraints_fixpoint(VarDict, MFA, Constrs, RecDict, ExpTypes, AllRecords).
 
 constraints_fixpoint(OldVarDict, MFA, Constrs, RecDict, ExpTypes, AllRecords) ->
@@ -499,7 +502,7 @@ constraints_fixpoint(OldVarDict, MFA, Constrs, RecDict, ExpTypes, AllRecords) ->
 	fun(Key, Value, Acc) ->
 	    [{subtype, erl_types:t_var(Key), Value}|Acc]
 	end,
-      FinalConstrs = dict:fold(DictFold, [], NewVarDict),
+      FinalConstrs = maps:fold(DictFold, [], NewVarDict),
       {FinalConstrs, NewVarDict};
     _Other ->
       constraints_fixpoint(NewVarDict, MFA, Constrs, RecDict, ExpTypes, AllRecords)
@@ -509,7 +512,7 @@ final_form(Form, ExpTypes, MFA, AllRecords, VarDict) ->
   from_form_with_check(Form, ExpTypes, MFA, AllRecords, VarDict).
 
 from_form_with_check(Form, ExpTypes, MFA, AllRecords) ->
-  from_form_with_check(Form, ExpTypes, MFA, AllRecords, dict:new()).
+  from_form_with_check(Form, ExpTypes, MFA, AllRecords, maps:new()).
 
 from_form_with_check(Form, ExpTypes, MFA, AllRecords, VarDict) ->
   Site = {spec, MFA},
@@ -520,7 +523,7 @@ from_form_with_check(Form, ExpTypes, MFA, AllRecords, VarDict) ->
 constraints_to_dict(Constrs, MFA, RecDict, ExpTypes, AllRecords, VarDict) ->
   Subtypes =
     constraints_to_subs(Constrs, MFA, RecDict, ExpTypes, AllRecords, VarDict, []),
-  insert_constraints(Subtypes, dict:new()).
+  insert_constraints(Subtypes).
 
 constraints_to_subs([], _MFA, _RecDict, _ExpTypes, _AllRecords, _VarDict, Acc) ->
   Acc;
@@ -605,8 +608,8 @@ general_domain(List) ->
   general_domain(List, erl_types:t_none()).
 
 general_domain([{Sig, Constraints}|Left], AccSig) ->
-  Dict = insert_constraints(Constraints, dict:new()),
-  Sig1 = erl_types:t_subst(Sig, Dict),
+  Map = insert_constraints(Constraints),
+  Sig1 = erl_types:t_subst(Sig, Map),
   general_domain(Left, erl_types:t_sup(AccSig, Sig1));
 general_domain([], AccSig) ->
   %% Get rid of all variables in the domain.
diff --git a/lib/dialyzer/src/dialyzer_dataflow.erl b/lib/dialyzer/src/dialyzer_dataflow.erl
index f0fa9fbb4e..5ab0c39c04 100644
--- a/lib/dialyzer/src/dialyzer_dataflow.erl
+++ b/lib/dialyzer/src/dialyzer_dataflow.erl
@@ -2,7 +2,7 @@
 %%--------------------------------------------------------------------
 %% %CopyrightBegin%
 %%
-%% Copyright Ericsson AB 2006-2015. All Rights Reserved.
+%% Copyright Ericsson AB 2006-2016. All Rights Reserved.
 %%
 %% Licensed under the Apache License, Version 2.0 (the "License");
 %% you may not use this file except in compliance with the License.
@@ -43,7 +43,6 @@
 
 -include("dialyzer.hrl").
 
-%%-import(helper, %% 'helper' could be any module doing sanity checks...
 -import(erl_types,
         [t_inf/2, t_inf/3, t_inf_lists/2, t_inf_lists/3,
          t_inf_lists/3, t_is_equal/2, t_is_subtype/2, t_subtract/2,
@@ -126,8 +125,8 @@
                 curr_fun             :: curr_fun()
                }).
 
--record(map, {dict = dict:new()   :: type_tab(),
-              subst = dict:new()  :: subst_tab(),
+-record(map, {map = maps:new()    :: type_tab(),
+              subst = maps:new()  :: subst_tab(),
               modified = []       :: [Key :: term()],
               modified_stack = [] :: [{[Key :: term()],reference()}],
               ref = undefined     :: reference() | undefined}).
@@ -135,10 +134,10 @@
 -type env_tab()   :: dict:dict(label(), #map{}).
 -type fun_entry() :: {Args :: [type()], RetType :: type()}.
 -type fun_tab()   :: dict:dict('top' | label(),
-                             {'not_handled', fun_entry()} | fun_entry()).
+                               {'not_handled', fun_entry()} | fun_entry()).
 -type key()       :: label() | cerl:cerl().
--type type_tab()  :: dict:dict(key(), type()).
--type subst_tab() :: dict:dict(key(), cerl:cerl()).
+-type type_tab()  :: #{key() => type()}.
+-type subst_tab() :: #{key() => cerl:cerl()}.
 
 %% Exported Types
 
@@ -1766,7 +1765,7 @@ bind_opaque_pats(GenType, Type, Pat, State) ->
 %%
 
 bind_guard(Guard, Map, State) ->
-  try bind_guard(Guard, Map, dict:new(), pos, State) of
+  try bind_guard(Guard, Map, maps:new(), pos, State) of
     {Map1, _Type} -> Map1
   catch
     throw:{fail, Warning} -> {error, Warning};
@@ -1804,7 +1803,7 @@ bind_guard(Guard, Map, Env, Eval, State) ->
 	catch throw:HE ->
 	    {{Map2, t_none()}, HE}
 	end,
-      BodyEnv = dict:store(get_label(Var), Arg, Env),
+      BodyEnv = maps:put(get_label(Var), Arg, Env),
       Wanted = case Eval of pos -> t_atom(true); neg -> t_atom(false);
 		 dont_know -> t_any() end,
       case t_is_none(t_inf(HandlerType, Wanted)) of
@@ -1850,7 +1849,7 @@ bind_guard(Guard, Map, Env, Eval, State) ->
       Arg = cerl:let_arg(Guard),
       [Var] = cerl:let_vars(Guard),
       %%?debug("Storing: ~w\n", [Var]),
-      NewEnv = dict:store(get_label(Var), Arg, Env),
+      NewEnv = maps:put(get_label(Var), Arg, Env),
       bind_guard(cerl:let_body(Guard), Map, NewEnv, Eval, State);
     values ->
       Es = cerl:values_es(Guard),
@@ -1859,7 +1858,7 @@ bind_guard(Guard, Map, Env, Eval, State) ->
       {Map, Type};
     var ->
       ?debug("Looking for var(~w)...", [cerl_trees:get_label(Guard)]),
-      case dict:find(get_label(Guard), Env) of
+      case maps:find(get_label(Guard), Env) of
 	error ->
 	  ?debug("Did not find it\n", []),
 	  Type = lookup_type(Guard, Map),
@@ -2689,10 +2688,10 @@ join_maps_end(Maps, MapOut) ->
   #map{ref = Ref, modified_stack = [{M1,R1} | S]} = MapOut,
   true = lists:all(fun(M) -> M#map.ref =:= Ref end, Maps), % sanity
   Keys0 = lists:usort(lists:append([M#map.modified || M <- Maps])),
-  #map{dict = Dict, subst = Subst} = MapOut,
+  #map{map = Map, subst = Subst} = MapOut,
   Keys = [Key ||
            Key <- Keys0,
-           dict:is_key(Key, Dict) orelse dict:is_key(Key, Subst)],
+           maps:is_key(Key, Map) orelse maps:is_key(Key, Subst)],
   Out = case Maps of
           [] -> join_maps(Maps, MapOut);
           _ -> join_maps(Keys, Maps, MapOut)
@@ -2703,8 +2702,8 @@ join_maps_end(Maps, MapOut) ->
           modified_stack = S}.
 
 join_maps(Maps, MapOut) ->
-  #map{dict = Dict, subst = Subst} = MapOut,
-  Keys = ordsets:from_list(dict:fetch_keys(Dict) ++ dict:fetch_keys(Subst)),
+  #map{map = Map, subst = Subst} = MapOut,
+  Keys = ordsets:from_list(maps:keys(Map) ++ maps:keys(Subst)),
   join_maps(Keys, Maps, MapOut).
 
 join_maps(Keys, Maps, MapOut) ->
@@ -2733,11 +2732,11 @@ join_maps_one_key([], _Key, AccType) ->
 
 -ifdef(DEBUG).
 debug_join_check(Maps, MapOut, Out) ->
-  #map{dict = Dict, subst = Subst} = Out,
-  #map{dict = Dict2, subst = Subst2} = join_maps(Maps, MapOut),
-  F = fun(D) -> lists:keysort(1, dict:to_list(D)) end,
+  #map{map = Map, subst = Subst} = Out,
+  #map{map = Map2, subst = Subst2} = join_maps(Maps, MapOut),
+  F = fun(D) -> lists:keysort(1, maps:to_list(D)) end,
   [throw({bug, join_maps}) ||
-    F(Dict) =/= F(Dict2) orelse F(Subst) =/= F(Subst2)].
+    F(Map) =/= F(Map2) orelse F(Subst) =/= F(Subst2)].
 -else.
 debug_join_check(_Maps, _MapOut, _Out) -> ok.
 -endif.
@@ -2768,15 +2767,15 @@ enter_type(Key, Val, MS) ->
 	      enter_type_lists(Keys, t_to_tlist(Val), MS)
 	  end;
 	false ->
-          #map{dict = Dict, subst = Subst} = MS,
+          #map{map = Map, subst = Subst} = MS,
 	  KeyLabel = get_label(Key),
-	  case dict:find(KeyLabel, Subst) of
+	  case maps:find(KeyLabel, Subst) of
 	    {ok, NewKey} ->
 	      ?debug("Binding ~p to ~p\n", [KeyLabel, NewKey]),
 	      enter_type(NewKey, Val, MS);
 	    error ->
 	      ?debug("Entering ~p :: ~s\n", [KeyLabel, t_to_string(Val)]),
-	      case dict:find(KeyLabel, Dict) of
+	      case maps:find(KeyLabel, Map) of
 		{ok, Value} ->
                   case erl_types:t_is_equal(Val, Value) of
                     true -> MS;
@@ -2788,10 +2787,10 @@ enter_type(Key, Val, MS) ->
       end
   end.
 
-store_map(Key, Val, #map{dict = Dict, ref = undefined} = Map) ->
-  Map#map{dict = dict:store(Key, Val, Dict)};
-store_map(Key, Val, #map{dict = Dict, modified = Mod} = Map) ->
-  Map#map{dict = dict:store(Key, Val, Dict), modified = [Key | Mod]}.
+store_map(Key, Val, #map{map = Map, ref = undefined} = MapRec) ->
+  MapRec#map{map = maps:put(Key, Val, Map)};
+store_map(Key, Val, #map{map = Map, modified = Mod} = MapRec) ->
+  MapRec#map{map = maps:put(Key, Val, Map), modified = [Key | Mod]}.
 
 enter_subst(Key, Val0, #map{subst = Subst} = MS) ->
   KeyLabel = get_label(Key),
@@ -2804,7 +2803,7 @@ enter_subst(Key, Val0, #map{subst = Subst} = MS) ->
 	false -> MS;
 	true ->
 	  ValLabel = get_label(Val),
-	  case dict:find(ValLabel, Subst) of
+	  case maps:find(ValLabel, Subst) of
 	    {ok, NewVal} ->
 	      enter_subst(Key, NewVal, MS);
 	    error ->
@@ -2818,22 +2817,22 @@ enter_subst(Key, Val0, #map{subst = Subst} = MS) ->
   end.
 
 store_subst(Key, Val, #map{subst = S, ref = undefined} = Map) ->
-  Map#map{subst = dict:store(Key, Val, S)};
+  Map#map{subst = maps:put(Key, Val, S)};
 store_subst(Key, Val, #map{subst = S, modified = Mod} = Map) ->
-  Map#map{subst = dict:store(Key, Val, S), modified = [Key | Mod]}.
+  Map#map{subst = maps:put(Key, Val, S), modified = [Key | Mod]}.
 
-lookup_type(Key, #map{dict = Dict, subst = Subst}) ->
-  lookup(Key, Dict, Subst, t_none()).
+lookup_type(Key, #map{map = Map, subst = Subst}) ->
+  lookup(Key, Map, Subst, t_none()).
 
-lookup(Key, Dict, Subst, AnyNone) ->
+lookup(Key, Map, Subst, AnyNone) ->
   case cerl:is_literal(Key) of
     true -> literal_type(Key);
     false ->
       Label = get_label(Key),
-      case dict:find(Label, Subst) of
-	{ok, NewKey} -> lookup(NewKey, Dict, Subst, AnyNone);
+      case maps:find(Label, Subst) of
+	{ok, NewKey} -> lookup(NewKey, Map, Subst, AnyNone);
 	error ->
-	  case dict:find(Label, Dict) of
+	  case maps:find(Label, Map) of
 	    {ok, Val} -> Val;
 	    error -> AnyNone
 	  end
@@ -2871,12 +2870,12 @@ mark_as_fresh([], Map) ->
   Map.
 
 -ifdef(DEBUG).
-debug_pp_map(#map{dict = Dict}=Map) ->
-  Keys = dict:fetch_keys(Dict),
+debug_pp_map(#map{map = Map}=MapRec) ->
+  Keys = maps:keys(Map),
   io:format("Map:\n", []),
   lists:foreach(fun (Key) ->
 		    io:format("\t~w :: ~s\n",
-			      [Key, t_to_string(lookup_type(Key, Map))])
+			      [Key, t_to_string(lookup_type(Key, MapRec))])
 		end, Keys),
   ok.
 -else.
diff --git a/lib/dialyzer/src/dialyzer_typesig.erl b/lib/dialyzer/src/dialyzer_typesig.erl
index dcf0947f3e..1787b66192 100644
--- a/lib/dialyzer/src/dialyzer_typesig.erl
+++ b/lib/dialyzer/src/dialyzer_typesig.erl
@@ -88,8 +88,7 @@
 -record(constraint_list, {type :: 'conj' | 'disj',
 			  list :: [constr()],
                           deps :: deps(),
-                          masks = [] :: [{dep(),mask()}] |
-                                  {'d',dict:dict(dep(), mask())},
+                          masks = maps:new() :: #{dep() => mask()},
 			  id   :: {'list', dep()} | 'undefined'}).
 
 -type constraint_list() :: #constraint_list{}.
@@ -110,21 +109,21 @@
 -record(state, {callgraph                :: dialyzer_callgraph:callgraph()
                                           | 'undefined',
 		cs          = []         :: [constr()],
-		cmap        = dict:new() :: dict:dict(), % FIXME
+		cmap        = maps:new() :: #{type_var() => constr()},
 		fun_map     = maps:new() :: typesig_funmap(),
-		fun_arities = dict:new() :: dict:dict(type_var(), arity()),
+		fun_arities = maps:new() :: #{type_var() => arity()},
 		in_match    = false      :: boolean(),
 		in_guard    = false      :: boolean(),
 		module                   :: module(),
-		name_map    = dict:new() :: dict:dict(mfa(), cerl:c_fun()),
+		name_map    = maps:new() :: #{mfa() => cerl:c_fun()},
 		next_label  = 0          :: label(),
 		self_rec                 :: 'false' | erl_types:erl_type(),
 		plt                      :: dialyzer_plt:plt()
                                           | 'undefined',
-		prop_types  = dict:new() :: dict:dict(), % FIXME
+		prop_types  = dict:new() :: prop_types(),
 		records     = dict:new() :: types(),
 		scc         = []         :: ordsets:ordset(type_var()),
-		mfas                     :: [tuple()], % FIXME?
+		mfas                     :: [mfa()],
                 solvers     = []         :: [solver()]
 	       }).
 
@@ -191,7 +190,8 @@ analyze_scc(SCC, NextLabel, CallGraph, Plt, PropTypes, Solvers0) ->
   Funs = state__scc(State3),
   pp_constrs_scc(Funs, State3),
   constraints_to_dot_scc(Funs, State3),
-  solve(Funs, State3).
+  T = solve(Funs, State3),
+  dict:from_list(maps:to_list(T)).
 
 assert_format_of_scc([{_MFA, {_Var, _Fun}, _Records}|Left]) ->
   assert_format_of_scc(Left);
@@ -945,11 +945,11 @@ get_safe_underapprox(Pats, Guard) ->
     Map1 = cerl_trees:fold(fun(X, Acc) ->
 			       case cerl:is_c_var(X) of
 				 true ->
-				   dict:store(cerl_trees:get_label(X), t_any(),
-					      Acc);
+				   maps:put(cerl_trees:get_label(X), t_any(),
+                                            Acc);
 				 false -> Acc
 			       end
-			   end, dict:new(), cerl:c_values(Pats)),
+			   end, maps:new(), cerl:c_values(Pats)),
     {Type, Map2} = get_underapprox_from_guard(Guard, Map1),
     Map3 = case t_is_none(t_inf(t_from_term(true), Type)) of
 	     true -> throw(dont_know);
@@ -957,8 +957,8 @@ get_safe_underapprox(Pats, Guard) ->
 	       case cerl:is_c_var(Guard) of
 		 false -> Map2;
 		 true ->
-		   dict:store(cerl_trees:get_label(Guard),
-			      t_from_term(true), Map2)
+		   maps:put(cerl_trees:get_label(Guard),
+                            t_from_term(true), Map2)
 	       end
 	   end,
     {Ts, _Map4} = get_safe_underapprox_1(Pats, [], Map3),
@@ -984,7 +984,7 @@ get_underapprox_from_guard(Tree, Map) ->
 	      case t_is_none(Inf) of
 		true -> throw(dont_know);
 		false ->
-		  {True, dict:store(cerl_trees:get_label(Fun), Inf, Map1)}
+		  {True, maps:put(cerl_trees:get_label(Fun), Inf, Map1)}
 	      end
 	  end;
 	MFA ->
@@ -1000,7 +1000,7 @@ get_underapprox_from_guard(Tree, Map) ->
 		  case cerl:is_literal(Arg) of
 		    true -> {True, Map1};
 		    false ->
-		      {True, dict:store(cerl_trees:get_label(Arg), Inf, Map1)}
+		      {True, maps:put(cerl_trees:get_label(Arg), Inf, Map1)}
 		  end
 	      end;
 	    error ->
@@ -1032,7 +1032,7 @@ get_underapprox_from_guard(Tree, Map) ->
       end;
     var ->
       Type =
-	case dict:find(cerl_trees:get_label(Tree), Map) of
+	case maps:find(cerl_trees:get_label(Tree), Map) of
 	  error -> throw(dont_know);
 	  {ok, T} -> T
 	end,
@@ -1136,7 +1136,7 @@ get_safe_underapprox_1([Pat0|Left], Acc, Map) ->
       case t_is_none(Inf) of
 	true -> throw(dont_know);
 	false ->
-	  Map3 = dict:store(cerl_trees:get_label(AVar), Inf, Map2),
+	  Map3 = maps:put(cerl_trees:get_label(AVar), Inf, Map2),
 	  get_safe_underapprox_1(Left, [Inf|Acc], Map3)
       end;
     binary ->
@@ -1204,7 +1204,7 @@ get_safe_underapprox_1([Pat0|Left], Acc, Map) ->
       Type = t_product(Ts),
       get_safe_underapprox_1(Left, [Type|Acc], Map1);
     var ->
-      case dict:find(cerl_trees:get_label(Pat), Map) of
+      case maps:find(cerl_trees:get_label(Pat), Map) of
 	error -> throw(dont_know);
 	{ok, VarType} -> get_safe_underapprox_1(Left, [VarType|Acc], Map)
       end
@@ -1910,7 +1910,7 @@ solver(Solver, SolveFun) ->
 
 solve_fun(v1, _Fun, Cs, FunMap, State) ->
   fun() ->
-      {ok, _MapDict, NewMap} = solve_ref_or_list(Cs, FunMap, dict:new(), State),
+      {ok, _MapDict, NewMap} = solve_ref_or_list(Cs, FunMap, map_new(), State),
       {ok, NewMap}
   end;
 solve_fun(v2, Fun, _Cs, FunMap, State) ->
@@ -1950,7 +1950,7 @@ sane_maps(Map1, Map2, Keys, _S1, _S2) ->
 
 %% Solver v2
 
--record(v2_state, {constr_data = dict:new() :: dict:dict(),
+-record(v2_state, {constr_data = maps:new() :: map(),
 		   state :: state()}).
 
 v2_solve_ref(Fun, Map, State) ->
@@ -2112,30 +2112,30 @@ v2_solve_disj(Is, [C|Cs], I, Map, V2State, UL, MapL, Eval, Uneval0, Failed) ->
   v2_solve_disj(Is, Cs, I+1, Map, V2State, UL, MapL, Eval, Uneval, Failed).
 
 save_local_map(#v2_state{constr_data = ConData}=V2State, Id, U, Map) ->
-  Part0 = [{V,dict:fetch(V, Map)} || V <- U],
+  Part0 = [{V,maps:get(V, Map)} || V <- U],
   Part1 =
-    case dict:find(Id, ConData) of
+    case maps:find(Id, ConData) of
       error -> []; % cannot happen
       {ok, {Part2,[]}} -> Part2
     end,
   ?debug("save local map Id=~w:\n", [Id]),
   Part = lists:ukeymerge(1, lists:keysort(1, Part0), Part1),
-  pp_map("New Part", dict:from_list(Part0)),
-  pp_map("Old Part", dict:from_list(Part1)),
-  pp_map(" => Part", dict:from_list(Part)),
-  V2State#v2_state{constr_data = dict:store(Id, {Part,[]}, ConData)}.
+  pp_map("New Part", maps:from_list(Part0)),
+  pp_map("Old Part", maps:from_list(Part1)),
+  pp_map(" => Part", maps:from_list(Part)),
+  V2State#v2_state{constr_data = maps:put(Id, {Part,[]}, ConData)}.
 
 restore_local_map(#v2_state{constr_data = ConData}, Id, Map0) ->
-  case dict:find(Id, ConData) of
+  case maps:find(Id, ConData) of
     error -> Map0;
     {ok, failed} -> Map0;
     {ok, {[],_}} -> Map0;
     {ok, {Part0,U}} ->
       Part = [KV || {K,_V} = KV <- Part0, not lists:member(K, U)],
       ?debug("restore local map Id=~w U=~w\n", [Id, U]),
-      pp_map("Part", dict:from_list(Part)),
+      pp_map("Part", maps:from_list(Part)),
       pp_map("Map0", Map0),
-      Map = lists:foldl(fun({K,V}, D) -> dict:store(K, V, D) end, Map0, Part),
+      Map = lists:foldl(fun({K,V}, D) -> maps:put(K, V, D) end, Map0, Part),
       pp_map("Map", Map),
       Map
   end.
@@ -2217,29 +2217,24 @@ add_mask_to_flags(Flags, [Im|M], I, L) when I > Im ->
 add_mask_to_flags(Flags, [_|M], _I, L) ->
   {lists:umerge(M, Flags), lists:reverse(L)}.
 
-get_mask(V, {d, Masks}) ->
-  case dict:find(V, Masks) of
+get_mask(V, Masks) ->
+  case maps:find(V, Masks) of
     error -> [];
     {ok, M} -> M
-  end;
-get_mask(V, Masks) ->
-  case lists:keyfind(V, 1, Masks) of
-    false -> [];
-    {V, M} -> M
   end.
 
 get_flags(#v2_state{constr_data = ConData}=V2State0, C) ->
   #constraint_list{id = Id, list = Cs, masks = Masks} = C,
-  case dict:find(Id, ConData) of
+  case maps:find(Id, ConData) of
     error ->
       ?debug("get_flags Id=~w Flags=all ~w\n", [Id, length(Cs)]),
-      V2State = V2State0#v2_state{constr_data = dict:store(Id, {[],[]}, ConData)},
+      V2State = V2State0#v2_state{constr_data = maps:put(Id, {[],[]}, ConData)},
       {V2State, lists:seq(1, length(Cs))};
     {ok, failed} ->
       {V2State0, failed_list};
     {ok, {Part,U}} when U =/= [] ->
       ?debug("get_flags Id=~w U=~w\n", [Id, U]),
-      V2State = V2State0#v2_state{constr_data = dict:store(Id, {Part,[]}, ConData)},
+      V2State = V2State0#v2_state{constr_data = maps:put(Id, {Part,[]}, ConData)},
       save_updated_vars_list(Cs, vars_per_child(U, Masks), V2State)
   end.
 
@@ -2268,13 +2263,13 @@ save_updated_vars(#constraint_ref{id = Id}, U, V2State) ->
 save_updated_vars1(V2State, C, U) ->
   #v2_state{constr_data = ConData} = V2State,
   #constraint_list{id = Id} = C,
-  case dict:find(Id, ConData) of
+  case maps:find(Id, ConData) of
     error -> V2State; % error means everything is flagged
     {ok, failed} -> V2State;
     {ok, {Part,U0}} ->
       %% Duplicates are not so common; let masks/2 remove them.
       U1 = U ++ U0,
-      V2State#v2_state{constr_data = dict:store(Id, {Part,U1}, ConData)}
+      V2State#v2_state{constr_data = maps:put(Id, {Part,U1}, ConData)}
   end.
 
 -ifdef(DEBUG).
@@ -2284,12 +2279,12 @@ pp_constr_data(_Tag, #v2_state{constr_data = D}) ->
          case _PartU of
            {_Part, _U} ->
              io:format("Id: ~w Vars: ~w\n", [_Id, _U]),
-             [pp_map("Part", dict:from_list(_Part)) || _Part =/= []];
+             [pp_map("Part", maps:from_list(_Part)) || _Part =/= []];
            failed ->
              io:format("Id: ~w failed list\n", [_Id])
          end
        end ||
-        {_Id, _PartU} <- lists:keysort(1, dict:to_list(D))],
+        {_Id, _PartU} <- lists:keysort(1, maps:to_list(D))],
   ok.
 
 -else.
@@ -2299,17 +2294,17 @@ pp_constr_data(_Tag, _V2State) ->
 
 failed_list(#constraint_list{id = Id}, #v2_state{constr_data = D}=V2State) ->
   ?debug("error list ~w~n", [Id]),
-  V2State#v2_state{constr_data = dict:store(Id, failed, D)}.
+  V2State#v2_state{constr_data = maps:put(Id, failed, D)}.
 
 is_failed_list(#constraint_list{id = Id}, #v2_state{constr_data = D}) ->
-  dict:find(Id, D) =:= {ok, failed}.
+  maps:find(Id, D) =:= {ok, failed}.
 
 %% Solver v1
 
 solve_ref_or_list(#constraint_ref{id = Id, deps = Deps},
 		  Map, MapDict, State) ->
   {OldLocalMap, Check} =
-    case dict:find(Id, MapDict) of
+    case maps:find(Id, MapDict) of
       error -> {map_new(), false};
       {ok, M} -> {M, true}
     end,
@@ -2355,12 +2350,12 @@ solve_ref_or_list(#constraint_ref{id = Id, deps = Deps},
 	  {ok, Var} -> enter_type(Var, FunType, NewMap1);
 	  error -> NewMap1
 	end,
-      {ok, dict:store(Id, NewMap2, NewMapDict), NewMap2}
+      {ok, maps:put(Id, NewMap2, NewMapDict), NewMap2}
   end;
 solve_ref_or_list(#constraint_list{type=Type, list = Cs, deps = Deps, id = Id},
 		  Map, MapDict, State) ->
   {OldLocalMap, Check} =
-    case dict:find(Id, MapDict) of
+    case maps:find(Id, MapDict) of
       error -> {map_new(), false};
       {ok, M} -> {M, true}
     end,
@@ -2410,7 +2405,7 @@ solve_self_recursive(Cs, Map, MapDict, Id, RecType0, State) ->
 solve_clist(Cs, conj, Id, Deps, MapDict, Map, State) ->
   case solve_cs(Cs, Map, MapDict, State) of
     {error, NewMapDict} ->
-      {error, dict:store(Id, error, NewMapDict)};
+      {error, maps:put(Id, error, NewMapDict)};
     {ok, NewMapDict, NewMap} = Ret ->
       case Cs of
 	[_] ->
@@ -2418,7 +2413,7 @@ solve_clist(Cs, conj, Id, Deps, MapDict, Map, State) ->
 	  Ret;
 	_ ->
 	  case maps_are_equal(Map, NewMap, Deps) of
-	    true -> {ok, dict:store(Id, NewMap, NewMapDict), NewMap};
+	    true -> {ok, maps:put(Id, NewMap, NewMapDict), NewMap};
 	    false -> solve_clist(Cs, conj, Id, Deps, NewMapDict, NewMap, State)
 	  end
       end
@@ -2432,10 +2427,10 @@ solve_clist(Cs, disj, Id, _Deps, MapDict, Map, State) ->
 	end,
   {Maps, NewMapDict} = lists:mapfoldl(Fun, MapDict, Cs),
   case [X || {ok, X} <- Maps] of
-    [] -> {error, dict:store(Id, error, NewMapDict)};
+    [] -> {error, maps:put(Id, error, NewMapDict)};
     MapList ->
       NewMap = join_maps(MapList),
-      {ok, dict:store(Id, NewMap, NewMapDict), NewMap}
+      {ok, maps:put(Id, NewMap, NewMapDict), NewMap}
   end.
 
 solve_cs([#constraint_ref{} = C|Tail], Map, MapDict, State) ->
@@ -2516,7 +2511,7 @@ report_failed_constraint(_C, _Map) ->
 %% ============================================================================
 
 map_new() ->
-  dict:new().
+  maps:new().
 
 join_maps([Map]) ->
   Map;
@@ -2526,9 +2521,9 @@ join_maps(Maps) ->
 
 constrained_keys(Maps) ->
   lists:foldl(fun(TmpMap, AccKeys) ->
-                  [Key || Key <- AccKeys, dict:is_key(Key, TmpMap)]
+                  [Key || Key <- AccKeys, maps:is_key(Key, TmpMap)]
               end,
-              dict:fetch_keys(hd(Maps)), tl(Maps)).
+              maps:keys(hd(Maps)), tl(Maps)).
 
 join_maps([Key|Left], Maps = [Map|MapsLeft], AccMap) ->
   NewType = join_one_key(Key, MapsLeft, lookup_type(Key, Map)),
@@ -2574,11 +2569,11 @@ prune_keys(Map1, Map2, Deps) ->
   NofDeps = length(Deps),
   case NofDeps > ?PRUNE_LIMIT of
     true ->
-      Keys1 = dict:fetch_keys(Map1),
+      Keys1 = maps:keys(Map1),
       case length(Keys1) > NofDeps of
 	true ->
 	  Set1 = lists:sort(Keys1),
-	  Set2 = lists:sort(dict:fetch_keys(Map2)),
+	  Set2 = lists:sort(maps:keys(Map2)),
 	  ordsets:intersection(ordsets:union(Set1, Set2), Deps);
 	false ->
 	  Deps
@@ -2599,7 +2594,7 @@ enter_type(Key, Val, Map) when is_integer(Key) ->
 	true -> ok;
 	false -> ?debug("LimitedVal ~s\n", [format_type(LimitedVal)])
       end,
-      case dict:find(Key, Map) of
+      case maps:find(Key, Map) of
         {ok, Value} ->
           case is_equal(Value, LimitedVal) of
             true -> Map;
@@ -2633,16 +2628,16 @@ enter_type2(Key, Val, Map) ->
 
 map_store(Key, Val, Map) ->
   ?debug("Storing ~w :: ~s\n", [Key, format_type(Val)]),
-  dict:store(Key, Val, Map).
+  maps:put(Key, Val, Map).
 
 erase_type(Key, Map) ->
-  dict:erase(Key, Map).
+  maps:remove(Key, Map).
 
 lookup_type_list(List, Map) ->
   [lookup_type(X, Map) || X <- List].
 
 unsafe_lookup_type(Key, Map) ->
-  case dict:find(t_var_name(Key), Map) of
+  case maps:find(t_var_name(Key), Map) of
     {ok, Type} -> Type;
     error -> t_none()
   end.
@@ -2651,7 +2646,7 @@ unsafe_lookup_type_list(List, Map) ->
   [unsafe_lookup_type(X, Map) || X <- List].
 
 lookup_type(Key, Map) when is_integer(Key) ->
-  case dict:find(Key, Map) of
+  case maps:find(Key, Map) of
     error -> t_any();
     {ok, Val} -> Val
   end;
@@ -2699,7 +2694,7 @@ is_equal(Type1, Type2) ->
 pp_map(_S, _Map) ->
   ?debug("\t~s: ~p\n",
             [_S, [{X, lists:flatten(format_type(Y))} ||
-                  {X, Y} <- lists:keysort(1, dict:to_list(_Map))]]).
+                  {X, Y} <- lists:keysort(1, maps:to_list(_Map))]]).
 
 %% ============================================================================
 %%
@@ -2709,7 +2704,7 @@ pp_map(_S, _Map) ->
 
 new_state(SCC0, NextLabel, CallGraph, Plt, PropTypes, Solvers) ->
   List = [{MFA, Var} || {MFA, {Var, _Fun}, _Rec} <- SCC0],
-  NameMap = dict:from_list(List),
+  NameMap = maps:from_list(List),
   MFAs = [MFA || {MFA, _Var} <- List],
   SCC = [mk_var(Fun) || {_MFA, {_Var, Fun}, _Rec} <- SCC0],
   SelfRec =
@@ -2751,15 +2746,15 @@ state__get_fun_prototype(Op, Arity, State) ->
   end.
 
 state__lookup_rec_var_in_scope(MFA, #state{name_map = NameMap}) ->
-  dict:find(MFA, NameMap).
+  maps:find(MFA, NameMap).
 
 state__store_fun_arity(Tree, #state{fun_arities = Map} = State) ->
   Arity = length(cerl:fun_vars(Tree)),
   Id = mk_var(Tree),
-  State#state{fun_arities = dict:store(Id, Arity, Map)}.
+  State#state{fun_arities = maps:put(Id, Arity, Map)}.
 
 state__fun_arity(Id, #state{fun_arities = Map}) ->
-  dict:fetch(Id, Map).
+  maps:get(Id, Map).
 
 state__lookup_undef_var(Tree, #state{callgraph = CG, plt = Plt}) ->
   Label = cerl_trees:get_label(Tree),
@@ -2889,12 +2884,12 @@ state__mk_vars(N, #state{next_label = NL} = State) ->
   Vars = [t_var(X) || X <- lists:seq(NL, NewLabel-1)],
   {State#state{next_label = NewLabel}, Vars}.
 
-state__store_constrs(Id, Cs, #state{cmap =  Dict} = State) ->
-  NewDict = dict:store(Id, Cs, Dict),
-  State#state{cmap = NewDict}.
+state__store_constrs(Id, Cs, #state{cmap = Map} = State) ->
+  NewMap = maps:put(Id, Cs, Map),
+  State#state{cmap = NewMap}.
 
-state__get_cs(Var, #state{cmap = Dict}) ->
-  dict:fetch(Var, Dict).
+state__get_cs(Var, #state{cmap = Map}) ->
+  maps:get(Var, Map).
 
 state__is_self_rec(Fun, #state{self_rec = SelfRec}) ->
   not (SelfRec =:= 'false') andalso is_equal(Fun, SelfRec).
@@ -3229,18 +3224,11 @@ order_fun_constraints([], Funs, Acc, State) ->
 update_masks(C, Masks) ->
   C#constraint_list{masks = Masks}.
 
--define(VARS_LIMIT, 50).
-
 calculate_masks([C|Cs], I, L0) ->
   calculate_masks(Cs, I+1, [{V, I} || V <- get_deps(C)] ++ L0);
 calculate_masks([], _I, L) ->
   M = family(L),
-  case length(M) > ?VARS_LIMIT of
-    true ->
-      {d, dict:from_list(M)};
-    false ->
-      M
-  end.
+  maps:from_list(M).
 
 %% ============================================================================
 %%
@@ -3368,7 +3356,7 @@ join_chars([H|T], Sep) ->
   [H|[[Sep,X] || X <- T]].
 
 debug_lookup_name(Var) ->
-  case dict:find(t_var_name(Var), get(dialyzer_typesig_map)) of
+  case maps:find(t_var_name(Var), get(dialyzer_typesig_map)) of
     error -> Var;
     {ok, Name} -> Name
   end.
@@ -3378,7 +3366,7 @@ debug_lookup_name(Var) ->
 debug_make_name_map(Vars, Funs) ->
   Map = get(dialyzer_typesig_map),
   NewMap =
-    if Map =:= undefined -> debug_make_name_map(Vars, Funs, dict:new());
+    if Map =:= undefined -> debug_make_name_map(Vars, Funs, maps:new());
        true              -> debug_make_name_map(Vars, Funs, Map)
     end,
   put(dialyzer_typesig_map, NewMap).
@@ -3386,7 +3374,7 @@ debug_make_name_map(Vars, Funs) ->
 debug_make_name_map([Var|VarLeft], [Fun|FunLeft], Map) ->
   Name = {cerl:fname_id(Var), cerl:fname_arity(Var)},
   FunLabel = cerl_trees:get_label(Fun),
-  debug_make_name_map(VarLeft, FunLeft, dict:store(FunLabel, Name, Map));
+  debug_make_name_map(VarLeft, FunLeft, maps:put(FunLabel, Name, Map));
 debug_make_name_map([], [], Map) ->
   Map.
 
diff --git a/lib/hipe/cerl/erl_types.erl b/lib/hipe/cerl/erl_types.erl
index 02e1625965..19396a58d8 100644
--- a/lib/hipe/cerl/erl_types.erl
+++ b/lib/hipe/cerl/erl_types.erl
@@ -380,7 +380,7 @@
 -type type_table() :: dict:dict(record_key() | type_key(),
                                 record_value() | type_value()).
 
--type var_table() :: dict:dict(atom(), erl_type()).
+-opaque var_table() :: #{atom() => erl_type()}.
 
 %%-----------------------------------------------------------------------------
 %% Unions
@@ -3305,7 +3305,7 @@ findfirst(N1, N2, U1, B1, U2, B2) ->
 %% from within this module. This code duplication needs to be eliminated at
 %% some point.
 
--spec t_subst(erl_type(), dict:dict(atom(), erl_type())) -> erl_type().
+-spec t_subst(erl_type(), #{atom() => erl_type()}) -> erl_type().
 
 t_subst(T, Dict) ->
   case t_has_var(T) of
@@ -3314,7 +3314,7 @@ t_subst(T, Dict) ->
   end.
 
 t_subst_dict(?var(Id), Dict) ->
-  case dict:find(Id, Dict) of
+  case maps:find(Id, Dict) of
     error -> ?any;
     {ok, Type} -> Type
   end;
@@ -4472,7 +4472,7 @@ mod_name(Mod, Name) ->
                   site(), mod_records()) -> erl_type().
 
 t_from_form(Form, ExpTypes, Site, RecDict) ->
-  t_from_form(Form, ExpTypes, Site, RecDict, dict:new()).
+  t_from_form(Form, ExpTypes, Site, RecDict, maps:new()).
 
 -spec t_from_form(parse_form(), sets:set(mfa()),
                   site(), mod_records(), var_table()) -> erl_type().
@@ -4489,7 +4489,7 @@ t_from_form_without_remote(Form, Site, TypeTable) ->
   Module = site_module(Site),
   RecDict = dict:from_list([{Module, TypeTable}]),
   ExpTypes = replace_by_none,
-  {T, _} = t_from_form1(Form, ExpTypes, Site, RecDict, dict:new()),
+  {T, _} = t_from_form1(Form, ExpTypes, Site, RecDict, maps:new()),
   T.
 
 %% REC_TYPE_LIMIT is used for limiting the depth of recursive types.
@@ -4545,7 +4545,7 @@ t_from_form(_, _TypeNames, _ET, _S, _MR, _V, D, L) when D =< 0 ; L =< 0 ->
 t_from_form({var, _L, '_'}, _TypeNames, _ET, _S, _MR, _V, _D, L) ->
   {t_any(), L};
 t_from_form({var, _L, Name}, _TypeNames, _ET, _S, _MR, V, _D, L) ->
-  case dict:find(Name, V) of
+  case maps:find(Name, V) of
     error -> {t_var(Name), L};
     {ok, Val} -> {Val, L}
   end;
@@ -4764,7 +4764,7 @@ type_from_form(Name, Args, TypeNames, ET, Site0, MR, V, D, L) ->
           {ArgTypes, L1} =
             list_from_form(Args, TypeNames, ET, Site0, MR, V, D, L),
           List = lists:zip(ArgNames, ArgTypes),
-          TmpV = dict:from_list(List),
+          TmpV = maps:from_list(List),
           Site = TypeName,
           t_from_form(Form, NewTypeNames, ET, Site, MR, TmpV, D, L1);
         false ->
@@ -4777,7 +4777,7 @@ type_from_form(Name, Args, TypeNames, ET, Site0, MR, V, D, L) ->
           {ArgTypes, L1} =
             list_from_form(Args, NewTypeNames, ET, Site0, MR, V, D, L),
           List = lists:zip(ArgNames, ArgTypes),
-          TmpV = dict:from_list(List),
+          TmpV = maps:from_list(List),
           Site = TypeName,
           {Rep, L2} =
             t_from_form(Form, NewTypeNames, ET, Site, MR, TmpV, D, L1),
@@ -4819,7 +4819,7 @@ remote_from_form(RemMod, Name, Args, TypeNames, ET, S, MR, V, D, L) ->
                       {ArgTypes, L1} = list_from_form(Args, TypeNames,
                                                       ET, S, MR, V, D, L),
                       List = lists:zip(ArgNames, ArgTypes),
-                      TmpVarDict = dict:from_list(List),
+                      TmpVarDict = maps:from_list(List),
                       Site = RemType,
                       t_from_form(Form, NewTypeNames, ET,
                                   Site, MR, TmpVarDict, D, L1);
@@ -4833,7 +4833,7 @@ remote_from_form(RemMod, Name, Args, TypeNames, ET, S, MR, V, D, L) ->
                       {ArgTypes, L1} = list_from_form(Args, NewTypeNames,
                                                       ET, S, MR, V, D, L),
                       List = lists:zip(ArgNames, ArgTypes),
-                      TmpVarDict = dict:from_list(List),
+                      TmpVarDict = maps:from_list(List),
                       Site = RemType,
                       {NewRep, L2} =
                         t_from_form(Form, NewTypeNames, ET, Site, MR,
@@ -4904,7 +4904,7 @@ record_from_form({atom, _, Name}, ModFields, TypeNames, ET, S, MR, V, D, L) ->
             {ok, NewFields} ->
               {NewFields1, L2} =
                 fields_from_form(NewFields, NewTypeNames, ET, S1, MR,
-                                 dict:new(), D, L1),
+                                 maps:new(), D, L1),
               Rec = t_tuple(
                       [t_atom(Name)|[Type
                                      || {_FieldName, Type} <- NewFields1]]),
@@ -5023,7 +5023,7 @@ promote_to_mand(MKs, [E={K,_,V}|T]) ->
                             mod_records()) -> ok.
 
 t_check_record_fields(Form, ExpTypes, Site, RecDict) ->
-  t_check_record_fields(Form, ExpTypes, Site, RecDict, dict:new()).
+  t_check_record_fields(Form, ExpTypes, Site, RecDict, maps:new()).
 
 -spec t_check_record_fields(parse_form(), sets:set(mfa()), site(),
                             mod_records(), var_table()) -> ok.
@@ -5192,8 +5192,9 @@ t_form_to_string({type, _L, Name, []} = T) ->
      D0 = dict:new(),
      MR = dict:from_list([{M, D0}]),
      S = {type, {M,Name,0}},
+     V = #{},
      {T1, _} =
-       t_from_form(T, [], sets:new(), S, MR, D0, _Deep=1000, _ALot=100000),
+       t_from_form(T, [], sets:new(), S, MR, V, _Deep=1000, _ALot=100000),
      t_to_string(T1)
   catch throw:{error, _} -> atom_to_string(Name) ++ "()"
   end;
-- 
cgit v1.2.3


From 5767bbc4fdd4a39f90d4e99d124e58bbf78e896b Mon Sep 17 00:00:00 2001
From: Hans Bolinder <hasse@erlang.org>
Date: Fri, 29 Apr 2016 14:57:42 +0200
Subject: hipe: Use maps for unification and substitution

---
 lib/hipe/cerl/erl_types.erl | 162 +++++++++++++++-----------------------------
 1 file changed, 54 insertions(+), 108 deletions(-)

diff --git a/lib/hipe/cerl/erl_types.erl b/lib/hipe/cerl/erl_types.erl
index 19396a58d8..84addcc105 100644
--- a/lib/hipe/cerl/erl_types.erl
+++ b/lib/hipe/cerl/erl_types.erl
@@ -236,7 +236,7 @@
 -export([t_is_identifier/1]).
 -endif.
 
--export_type([erl_type/0, opaques/0, type_table/0, var_table/0]).
+-export_type([erl_type/0, opaques/0, type_table/0]).
 
 %%-define(DEBUG, true).
 
@@ -380,7 +380,7 @@
 -type type_table() :: dict:dict(record_key() | type_key(),
                                 record_value() | type_value()).
 
--opaque var_table() :: #{atom() => erl_type()}.
+-type var_table() :: #{atom() => erl_type()}.
 
 %%-----------------------------------------------------------------------------
 %% Unions
@@ -3295,87 +3295,33 @@ findfirst(N1, N2, U1, B1, U2, B2) ->
 %%-----------------------------------------------------------------------------
 %% Substitution of variables
 %%
-%% Dialyzer versions prior to R15B used a dict data structure to map variables
-%% to types. Hans Bolinder suggested the use of lists of Key-Value pairs for
-%% this data structure and measurements showed a non-trivial speedup when using
-%% them for operations within this module (e.g. in t_unify/2). However, there
-%% is code outside erl_types that still passes a dict:dict() in the 2nd argument.
-%% So, for the time being, this module provides a t_subst/2 function for these
-%% external calls and a clone of it (t_subst_kv/2) which is used from all calls
-%% from within this module. This code duplication needs to be eliminated at
-%% some point.
-
--spec t_subst(erl_type(), #{atom() => erl_type()}) -> erl_type().
-
-t_subst(T, Dict) ->
+
+-type subst_table() :: #{any() => erl_type()}.
+
+-spec t_subst(erl_type(), subst_table()) -> erl_type().
+
+t_subst(T, Map) ->
   case t_has_var(T) of
-    true -> t_subst_dict(T, Dict);
+    true -> t_subst_aux(T, Map);
     false -> T
   end.
 
-t_subst_dict(?var(Id), Dict) ->
-  case maps:find(Id, Dict) of
-    error -> ?any;
-    {ok, Type} -> Type
-  end;
-t_subst_dict(?list(Contents, Termination, Size), Dict) ->
-  case t_subst_dict(Contents, Dict) of
-    ?none -> ?none;
-    NewContents ->
-      %% Be careful here to make the termination collapse if necessary.
-      case t_subst_dict(Termination, Dict) of
-	?nil -> ?list(NewContents, ?nil, Size);
-	?any -> ?list(NewContents, ?any, Size);
-	Other ->
-	  ?list(NewContents2, NewTermination, _) = t_cons(NewContents, Other),
-	  ?list(NewContents2, NewTermination, Size)
-      end
-  end;
-t_subst_dict(?function(Domain, Range), Dict) ->
-  ?function(t_subst_dict(Domain, Dict), t_subst_dict(Range, Dict));
-t_subst_dict(?product(Types), Dict) ->
-  ?product([t_subst_dict(T, Dict) || T <- Types]);
-t_subst_dict(?tuple(?any, ?any, ?any) = T, _Dict) ->
-  T;
-t_subst_dict(?tuple(Elements, _Arity, _Tag), Dict) ->
-  t_tuple([t_subst_dict(E, Dict) || E <- Elements]);
-t_subst_dict(?tuple_set(_) = TS, Dict) ->
-  t_sup([t_subst_dict(T, Dict) || T <- t_tuple_subtypes(TS)]);
-t_subst_dict(?map(Pairs, DefK, DefV), Dict) ->
-  t_map([{K, MNess, t_subst_dict(V, Dict)} || {K, MNess, V} <- Pairs],
-	t_subst_dict(DefK, Dict), t_subst_dict(DefV, Dict));
-t_subst_dict(?opaque(Es), Dict) ->
-  List = [Opaque#opaque{args = [t_subst_dict(Arg, Dict) || Arg <- Args],
-                        struct = t_subst_dict(S, Dict)} ||
-           Opaque = #opaque{args = Args, struct = S} <- set_to_list(Es)],
-  ?opaque(ordsets:from_list(List));
-t_subst_dict(?union(List), Dict) ->
-  ?union([t_subst_dict(E, Dict) || E <- List]);
-t_subst_dict(T, _Dict) ->
-  T.
-
 -spec subst_all_vars_to_any(erl_type()) -> erl_type().
 
 subst_all_vars_to_any(T) ->
-  t_subst_kv(T, []).
+  t_subst(T, #{}).
 
-t_subst_kv(T, KVMap) ->
-  case t_has_var(T) of
-    true -> t_subst_aux(T, KVMap);
-    false -> T
-  end.
-
-t_subst_aux(?var(Id), VarMap) ->
-  case lists:keyfind(Id, 1, VarMap) of
-    false -> ?any;
-    {Id, Type} -> Type
+t_subst_aux(?var(Id), Map) ->
+  case maps:find(Id, Map) of
+    error -> ?any;
+    {ok, Type} -> Type
   end;
-t_subst_aux(?list(Contents, Termination, Size), VarMap) ->
-  case t_subst_aux(Contents, VarMap) of
+t_subst_aux(?list(Contents, Termination, Size), Map) ->
+  case t_subst_aux(Contents, Map) of
     ?none -> ?none;
     NewContents ->
       %% Be careful here to make the termination collapse if necessary.
-      case t_subst_aux(Termination, VarMap) of
+      case t_subst_aux(Termination, Map) of
 	?nil -> ?list(NewContents, ?nil, Size);
 	?any -> ?list(NewContents, ?any, Size);
 	Other ->
@@ -3383,27 +3329,27 @@ t_subst_aux(?list(Contents, Termination, Size), VarMap) ->
 	  ?list(NewContents2, NewTermination, Size)
       end
   end;
-t_subst_aux(?function(Domain, Range), VarMap) ->
-  ?function(t_subst_aux(Domain, VarMap), t_subst_aux(Range, VarMap));
-t_subst_aux(?product(Types), VarMap) ->
-  ?product([t_subst_aux(T, VarMap) || T <- Types]);
-t_subst_aux(?tuple(?any, ?any, ?any) = T, _VarMap) ->
+t_subst_aux(?function(Domain, Range), Map) ->
+  ?function(t_subst_aux(Domain, Map), t_subst_aux(Range, Map));
+t_subst_aux(?product(Types), Map) ->
+  ?product([t_subst_aux(T, Map) || T <- Types]);
+t_subst_aux(?tuple(?any, ?any, ?any) = T, _Map) ->
   T;
-t_subst_aux(?tuple(Elements, _Arity, _Tag), VarMap) ->
-  t_tuple([t_subst_aux(E, VarMap) || E <- Elements]);
-t_subst_aux(?tuple_set(_) = TS, VarMap) ->
-  t_sup([t_subst_aux(T, VarMap) || T <- t_tuple_subtypes(TS)]);
-t_subst_aux(?map(Pairs, DefK, DefV), VarMap) ->
-  t_map([{K, MNess, t_subst_aux(V, VarMap)} || {K, MNess, V} <- Pairs],
-	t_subst_aux(DefK, VarMap), t_subst_aux(DefV, VarMap));
-t_subst_aux(?opaque(Es), VarMap) ->
-   List = [Opaque#opaque{args = [t_subst_aux(Arg, VarMap) || Arg <- Args],
-                         struct = t_subst_aux(S, VarMap)} ||
-            Opaque = #opaque{args = Args, struct = S} <- set_to_list(Es)],
-   ?opaque(ordsets:from_list(List));
-t_subst_aux(?union(List), VarMap) ->
-  ?union([t_subst_aux(E, VarMap) || E <- List]);
-t_subst_aux(T, _VarMap) ->
+t_subst_aux(?tuple(Elements, _Arity, _Tag), Map) ->
+  t_tuple([t_subst_aux(E, Map) || E <- Elements]);
+t_subst_aux(?tuple_set(_) = TS, Map) ->
+  t_sup([t_subst_aux(T, Map) || T <- t_tuple_subtypes(TS)]);
+t_subst_aux(?map(Pairs, DefK, DefV), Map) ->
+  t_map([{K, MNess, t_subst_aux(V, Map)} || {K, MNess, V} <- Pairs],
+	t_subst_aux(DefK, Map), t_subst_aux(DefV, Map));
+t_subst_aux(?opaque(Es), Map) ->
+  List = [Opaque#opaque{args = [t_subst_aux(Arg, Map) || Arg <- Args],
+                        struct = t_subst_aux(S, Map)} ||
+           Opaque = #opaque{args = Args, struct = S} <- set_to_list(Es)],
+  ?opaque(ordsets:from_list(List));
+t_subst_aux(?union(List), Map) ->
+  ?union([t_subst_aux(E, Map) || E <- List]);
+t_subst_aux(T, _Map) ->
   T.
 
 %%-----------------------------------------------------------------------------
@@ -3415,33 +3361,33 @@ t_subst_aux(T, _VarMap) ->
 -spec t_unify(erl_type(), erl_type()) -> t_unify_ret().
 
 t_unify(T1, T2) ->
-  {T, VarMap} = t_unify(T1, T2, []),
-  {t_subst_kv(T, VarMap), lists:keysort(1, VarMap)}.
+  {T, VarMap} = t_unify(T1, T2, #{}),
+  {t_subst(T, VarMap), lists:keysort(1, maps:to_list(VarMap))}.
 
 t_unify(?var(Id) = T, ?var(Id), VarMap) ->
   {T, VarMap};
 t_unify(?var(Id1) = T, ?var(Id2), VarMap) ->
-  case lists:keyfind(Id1, 1, VarMap) of
-    false ->
-      case lists:keyfind(Id2, 1, VarMap) of
-	false -> {T, [{Id2, T} | VarMap]};
-	{Id2, Type} -> t_unify(T, Type, VarMap)
+  case maps:find(Id1, VarMap) of
+    error ->
+      case maps:find(Id2, VarMap) of
+	error -> {T, VarMap#{Id2 => T}};
+	{ok, Type} -> t_unify(T, Type, VarMap)
       end;
-    {Id1, Type1} ->
-      case lists:keyfind(Id2, 1, VarMap) of
-	false -> {Type1, [{Id2, T} | VarMap]};
-	{Id2, Type2} -> t_unify(Type1, Type2, VarMap)
+    {ok, Type1} ->
+      case maps:find(Id2, VarMap) of
+	error -> {Type1, VarMap#{Id2 => T}};
+	{ok, Type2} -> t_unify(Type1, Type2, VarMap)
       end
   end;
 t_unify(?var(Id), Type, VarMap) ->
-  case lists:keyfind(Id, 1, VarMap) of
-    false -> {Type, [{Id, Type} | VarMap]};
-    {Id, VarType} -> t_unify(VarType, Type, VarMap)
+  case maps:find(Id, VarMap) of
+    error -> {Type, VarMap#{Id => Type}};
+    {ok, VarType} -> t_unify(VarType, Type, VarMap)
   end;
 t_unify(Type, ?var(Id), VarMap) ->
-  case lists:keyfind(Id, 1, VarMap) of
-    false -> {Type, [{Id, Type} | VarMap]};
-    {Id, VarType} -> t_unify(VarType, Type, VarMap)
+  case maps:find(Id, VarMap) of
+    error -> {Type, VarMap#{Id => Type}};
+    {ok, VarType} -> t_unify(VarType, Type, VarMap)
   end;
 t_unify(?function(Domain1, Range1), ?function(Domain2, Range2), VarMap) ->
   {Domain, VarMap1} = t_unify(Domain1, Domain2, VarMap),
-- 
cgit v1.2.3