Merge branch 'egil/opt-compile-time/OTP-12774'

* egil/opt-compile-time/OTP-12774:
  stdlib: Relax erl_anno_SUITE:is_anno/1 test
  Update primary bootstrap
  compiler: Use Maps as type information
  compiler: Use Maps instead of dict in beam_jump
  compiler: Use cerl_sets instead of gb_sets in beam_type
  compiler: Use Maps instead of gb_trees in beam_dead
  compiler: Use cerl_sets instead of gb_sets in beam_jump
  compiler: Use cerl_sets instead of sets in v3_kernel
  compiler: Use cerl_sets instead of gb_sets in sys_core_fold
  compiler: Add cerl_sets module
  compiler: Scope uses gb_sets not gb_trees
  beam_dict: Use Maps to map function name indices
  beam_dict: Use Maps to map line indices
  beam_dict: Use Maps to map atom indices
  v3_codegen: Use Maps to map local functions
  v3_life: Refactor variable db
  compiler: Use lc instead of map/1 in v3_codegen
  stdlib: Optimize erl_anno:is_string/1

Conflicts:
	bootstrap/lib/kernel/ebin/inet_dns.beam
	bootstrap/lib/stdlib/ebin/erl_anno.beam
	bootstrap/lib/stdlib/ebin/erl_lint.beam

11 files changed, 379 insertions, 164 deletions

diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile
index 7c4cebdc28..78efc8dff0 100644
--- a/lib/compiler/src/Makefile
+++ b/lib/compiler/src/Makefile
@@ -70,6 +70,7 @@ MODULES =  \
 	cerl \
 	cerl_clauses \
 	cerl_inline \
+	cerl_sets \
 	cerl_trees \
 	compile \
 	core_lib \
diff --git a/lib/compiler/src/beam_dead.erl b/lib/compiler/src/beam_dead.erl
index 5932d8ce1d..bbe607cf19 100644
--- a/lib/compiler/src/beam_dead.erl
+++ b/lib/compiler/src/beam_dead.erl
@@ -96,7 +96,7 @@ move_move_into_block([], Acc) -> reverse(Acc).
 %%%
 
 forward(Is, Lc) ->
-    forward(Is, gb_trees:empty(), Lc, []).
+    forward(Is, #{}, Lc, []).
 
 forward([{move,_,_}=Move|[{label,L}|_]=Is], D, Lc, Acc) ->
     %% move/2 followed by jump/1 is optimized by backward/3.
@@ -115,19 +115,20 @@ forward([{label,Lbl}=LblI,{block,[{set,[Dst],[Lit],move}|BlkIs]}=Blk|Is], D, Lc,
     %% cannot be reached in any other way than through the select_val/3
     %% instruction (i.e. there can be no fallthrough to such label and
     %% it cannot be referenced by, for example, a jump/1 instruction).
-    Block = case gb_trees:lookup({Lbl,Dst}, D) of
-		{value,Lit} -> {block,BlkIs}; %Safe to remove move instruction.
-		_ -> Blk		      %Must keep move instruction.
-	    end,
+    Key = {Lbl,Dst},
+    Block = case D of
+                #{Key := Lit} -> {block,BlkIs}; %Safe to remove move instruction.
+                _ -> Blk                        %Must keep move instruction.
+            end,
     forward([Block|Is], D, Lc, [LblI|Acc]);
 forward([{label,Lbl}=LblI|[{move,Lit,Dst}|Is1]=Is0], D, Lc, Acc) ->
     %% Assumption: The target labels in a select_val/3 instruction
     %% cannot be reached in any other way than through the select_val/3
     %% instruction (i.e. there can be no fallthrough to such label and
     %% it cannot be referenced by, for example, a jump/1 instruction).
-    Is = case gb_trees:lookup({Lbl,Dst}, D) of
-	     {value,Lit} -> Is1;     %Safe to remove move instruction.
-	     _ -> Is0		     %Keep move instruction.
+    Is = case maps:find({Lbl,Dst}, D) of
+	     {ok,Lit} -> Is1;     %Safe to remove move instruction.
+	     _ -> Is0		  %Keep move instruction.
 	 end,
     forward(Is, D, Lc, [LblI|Acc]);
 forward([{test,is_eq_exact,_,[Same,Same]}|Is], D, Lc, Acc) ->
@@ -156,11 +157,11 @@ forward([], _, Lc, Acc) -> {Acc,Lc}.
 
 update_value_dict([Lit,{f,Lbl}|T], Reg, D0) ->
     Key = {Lbl,Reg},
-    D = case gb_trees:lookup(Key, D0) of
-	    none -> gb_trees:insert(Key, Lit, D0); %New.
-	    {value,inconsistent} -> D0;		%Inconsistent.
-	    {value,_} -> gb_trees:update(Key, inconsistent, D0)
-	end,
+    D = case D0 of
+            #{Key := inconsistent} -> D0;
+            #{Key := _} -> D0#{Key := inconsistent};
+            _ -> D0#{Key => Lit}
+        end,
     update_value_dict(T, Reg, D);
 update_value_dict([], _, D) -> D.
 
diff --git a/lib/compiler/src/beam_dict.erl b/lib/compiler/src/beam_dict.erl
index 68dc104dd3..b1aa98278e 100644
--- a/lib/compiler/src/beam_dict.erl
+++ b/lib/compiler/src/beam_dict.erl
@@ -31,22 +31,22 @@
 
 -type index() :: non_neg_integer().
 
--type atom_tab()   :: gb_trees:tree(atom(), index()).
+-type atom_tab()   :: #{atom() => index()}.
 -type import_tab() :: gb_trees:tree(mfa(), index()).
--type fname_tab()  :: gb_trees:tree(Name :: term(), index()).
--type line_tab()   :: gb_trees:tree({Fname :: index(), Line :: term()}, index()).
+-type fname_tab()  :: #{Name :: term() => index()}.
+-type line_tab()   :: #{{Fname :: index(), Line :: term()} => index()}.
 -type literal_tab() :: dict:dict(Literal :: term(), index()).
 
 -record(asm,
-	{atoms = gb_trees:empty()   :: atom_tab(),
+	{atoms = #{}                :: atom_tab(),
 	 exports = []		    :: [{label(), arity(), label()}],
 	 locals = []		    :: [{label(), arity(), label()}],
 	 imports = gb_trees:empty() :: import_tab(),
 	 strings = <<>>		    :: binary(),	%String pool
 	 lambdas = [],				%[{...}]
 	 literals = dict:new()	    :: literal_tab(),
-	 fnames = gb_trees:empty()  :: fname_tab(),
-	 lines = gb_trees:empty()   :: line_tab(),
+	 fnames = #{}               :: fname_tab(),
+	 lines = #{}                :: line_tab(),
 	 num_lines = 0		    :: non_neg_integer(), %Number of line instructions
 	 next_import = 0	    :: non_neg_integer(),
 	 string_offset = 0	    :: non_neg_integer(),
@@ -77,14 +77,12 @@ highest_opcode(#asm{highest_opcode=Op}) -> Op.
 %%    atom(Atom, Dict) -> {Index,Dict'}
 -spec atom(atom(), bdict()) -> {pos_integer(), bdict()}.
 
-atom(Atom, #asm{atoms=Atoms0}=Dict) when is_atom(Atom) ->
-    case gb_trees:lookup(Atom, Atoms0) of
-	{value,Index} ->
-	    {Index,Dict};
-	none ->
-	    NextIndex = gb_trees:size(Atoms0) + 1,
-	    Atoms = gb_trees:insert(Atom, NextIndex, Atoms0),
-	    {NextIndex,Dict#asm{atoms=Atoms}}
+atom(Atom, #asm{atoms=Atoms}=Dict) when is_atom(Atom) ->
+    case Atoms of
+        #{ Atom := Index} -> {Index,Dict};
+        _ ->
+            NextIndex = maps:size(Atoms) + 1,
+            {NextIndex,Dict#asm{atoms=Atoms#{Atom=>NextIndex}}}
     end.
 
 %% Remembers an exported function.
@@ -177,26 +175,22 @@ line([], #asm{num_lines=N}=Dict) ->
     %% No location available. Return the special pre-defined
     %% index 0.
     {0,Dict#asm{num_lines=N+1}};
-line([{location,Name,Line}], #asm{lines=Lines0,num_lines=N}=Dict0) ->
+line([{location,Name,Line}], #asm{lines=Lines,num_lines=N}=Dict0) ->
     {FnameIndex,Dict1} = fname(Name, Dict0),
-    case gb_trees:lookup({FnameIndex,Line}, Lines0) of
-	{value,Index} ->
-	    {Index,Dict1#asm{num_lines=N+1}};
-	none ->
-	    Index = gb_trees:size(Lines0) + 1,
-	    Lines = gb_trees:insert({FnameIndex,Line}, Index, Lines0),
-	    Dict = Dict1#asm{lines=Lines,num_lines=N+1},
-	    {Index,Dict}
+    Key = {FnameIndex,Line},
+    case Lines of
+        #{Key := Index} -> {Index,Dict1#asm{num_lines=N+1}};
+        _ ->
+	    Index = maps:size(Lines) + 1,
+            {Index, Dict1#asm{lines=Lines#{Key=>Index},num_lines=N+1}}
     end.
 
-fname(Name, #asm{fnames=Fnames0}=Dict) ->
-    case gb_trees:lookup(Name, Fnames0) of
-	{value,Index} ->
-	    {Index,Dict};
-	none ->
-	    Index = gb_trees:size(Fnames0),
-	    Fnames = gb_trees:insert(Name, Index, Fnames0),
-	    {Index,Dict#asm{fnames=Fnames}}
+fname(Name, #asm{fnames=Fnames}=Dict) ->
+    case Fnames of
+        #{Name := Index} -> {Index,Dict};
+        _ ->
+            Index = maps:size(Fnames),
+	    {Index,Dict#asm{fnames=Fnames#{Name=>Index}}}
     end.
 
 %% Returns the atom table.
@@ -204,14 +198,12 @@ fname(Name, #asm{fnames=Fnames0}=Dict) ->
 -spec atom_table(bdict()) -> {non_neg_integer(), [[non_neg_integer(),...]]}.
 
 atom_table(#asm{atoms=Atoms}) ->
-    NumAtoms = gb_trees:size(Atoms),
-    Sorted = lists:keysort(2, gb_trees:to_list(Atoms)),
-    Fun = fun({A,_}) ->
-		  L = atom_to_list(A),
-		  [length(L)|L]
-	  end,
-    AtomTab = lists:map(Fun, Sorted),
-    {NumAtoms,AtomTab}.
+    NumAtoms = maps:size(Atoms),
+    Sorted = lists:keysort(2, maps:to_list(Atoms)),
+    {NumAtoms,[begin
+                   L = atom_to_list(A),
+                   [length(L)|L]
+               end || {A,_} <- Sorted]}.
 
 %% Returns the table of local functions.
 %%    local_table(Dict) -> {NumLocals, [{Function, Arity, Label}...]}
@@ -273,11 +265,11 @@ my_term_to_binary(Term) ->
      non_neg_integer(),[{non_neg_integer(),non_neg_integer()}]}.
 
 line_table(#asm{fnames=Fnames0,lines=Lines0,num_lines=NumLineInstrs}) ->
-    NumFnames = gb_trees:size(Fnames0),
-    Fnames1 = lists:keysort(2, gb_trees:to_list(Fnames0)),
+    NumFnames = maps:size(Fnames0),
+    Fnames1 = lists:keysort(2, maps:to_list(Fnames0)),
     Fnames = [Name || {Name,_} <- Fnames1],
-    NumLines = gb_trees:size(Lines0),
-    Lines1 = lists:keysort(2, gb_trees:to_list(Lines0)),
+    NumLines = maps:size(Lines0),
+    Lines1 = lists:keysort(2, maps:to_list(Lines0)),
     Lines = [L || {L,_} <- Lines1],
     {NumLineInstrs,NumFnames,Fnames,NumLines,Lines}.
 
diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl
index 52b6464c7f..80b2998ddc 100644
--- a/lib/compiler/src/beam_jump.erl
+++ b/lib/compiler/src/beam_jump.erl
@@ -152,14 +152,14 @@ function({function,Name,Arity,CLabel,Asm0}) ->
 share(Is0) ->
     %% We will get more sharing if we never fall through to a label.
     Is = eliminate_fallthroughs(Is0, []),
-    share_1(Is, dict:new(), [], []).
+    share_1(Is, #{}, [], []).
 
 share_1([{label,_}=Lbl|Is], Dict, [], Acc) ->
     share_1(Is, Dict, [], [Lbl|Acc]);
 share_1([{label,L}=Lbl|Is], Dict0, Seq, Acc) ->
-    case dict:find(Seq, Dict0) of
+    case maps:find(Seq, Dict0) of
 	error ->
-	    Dict = dict:store(Seq, L, Dict0),
+	    Dict = maps:put(Seq, L, Dict0),
 	    share_1(Is, Dict, [], [Lbl|Seq ++ Acc]);
 	{ok,Label} ->
 	    share_1(Is, Dict0, [], [Lbl,{jump,{f,Label}}|Acc])
@@ -188,7 +188,7 @@ clean_non_sharable(Dict) ->
     %% a sequence inside the 'try' block is a sequence that ends
     %% with an instruction that causes an exception. Any sequence
     %% that causes an exception must contain a line/1 instruction.
-    dict:filter(fun(K, _V) -> sharable_with_try(K) end, Dict).
+    maps:filter(fun(K, _V) -> sharable_with_try(K) end, Dict).
 
 sharable_with_try([{line,_}|_]) ->
     %% This sequence may cause an exception and may potentially
@@ -268,13 +268,13 @@ extract_seq_1(_, _) -> no.
 -record(st, {fc,				%Label for function class errors.
 	     entry,				%Entry label (must not be moved).
 	     mlbl,				%Moved labels.
-	     labels				%Set of referenced labels.
+             labels :: cerl_sets:set()          %Set of referenced labels.
 	    }).
 
 opt([{label,Fc}|_]=Is0, CLabel) ->
     Lbls = initial_labels(Is0),
     find_fixpoint(fun(Is) ->
-			  St = #st{fc=Fc,entry=CLabel,mlbl=dict:new(),
+			  St = #st{fc=Fc,entry=CLabel,mlbl=#{},
 				   labels=Lbls},
 			  opt(Is, [], St)
 		  end, Is0).
@@ -320,11 +320,11 @@ opt([{test,_,{f,_}=Lbl,_,_,_}=I|Is], Acc, St) ->
 opt([{select,_,_R,Fail,Vls}=I|Is], Acc, St) ->
     skip_unreachable(Is, [I|Acc], label_used([Fail|Vls], St));
 opt([{label,Lbl}=I|Is], Acc, #st{mlbl=Mlbl}=St0) ->
-    case dict:find(Lbl, Mlbl) of
+    case maps:find(Lbl, Mlbl) of
 	{ok,Lbls} ->
 	    %% Essential to remove the list of labels from the dictionary,
 	    %% since we will rescan the inserted labels.  We MUST rescan.
-	    St = St0#st{mlbl=dict:erase(Lbl, Mlbl)},
+	    St = St0#st{mlbl=maps:remove(Lbl, Mlbl)},
 	    insert_labels([Lbl|Lbls], Is, Acc, St);
 	error -> opt(Is, [I|Acc], St0)
     end;
@@ -339,7 +339,7 @@ opt([{jump,{f,L}=Lbl}=I|Is], Acc0, #st{mlbl=Mlbl0}=St0) ->
     St = case Lbls of
 	     [] -> St0;
 	     [_|_] ->
-		 Mlbl = dict:append_list(L, Lbls, Mlbl0),
+		 Mlbl = maps_append_list(L, Lbls, Mlbl0),
 		 St0#st{mlbl=Mlbl}
 	 end,
     skip_unreachable(Is, [I|Acc], label_used(Lbl, St));
@@ -363,14 +363,20 @@ opt([I|Is], Acc, #st{labels=Used0}=St0) ->
     end;
 opt([], Acc, #st{fc=Fc,mlbl=Mlbl}) ->
     Code = reverse(Acc),
-    case dict:find(Fc, Mlbl) of
+    case maps:find(Fc, Mlbl) of
  	{ok,Lbls} -> insert_fc_labels(Lbls, Mlbl, Code);
  	error -> Code
     end.
 
+maps_append_list(K,Vs,M) ->
+    case M of
+        #{K:=Vs0} -> M#{K:=Vs0++Vs}; % same order as dict
+        _ -> M#{K => Vs}
+    end.
+
 insert_fc_labels([L|Ls], Mlbl, Acc0) ->
     Acc = [{label,L}|Acc0],
-    case dict:find(L, Mlbl) of
+    case maps:find(L, Mlbl) of
 	error ->
 	    insert_fc_labels(Ls, Mlbl, Acc);
 	{ok,Lbls} ->
@@ -434,7 +440,7 @@ skip_unreachable([], Acc, St) ->
 
 %% Add one or more label to the set of used labels.
 
-label_used({f,L}, St) -> St#st{labels=gb_sets:add(L, St#st.labels)};
+label_used({f,L}, St) -> St#st{labels=cerl_sets:add_element(L,St#st.labels)};
 label_used([H|T], St0) -> label_used(T, label_used(H, St0));
 label_used([], St) -> St;
 label_used(_Other, St) -> St.
@@ -442,7 +448,7 @@ label_used(_Other, St) -> St.
 %% Test if label is used.
 
 is_label_used(L, St) ->
-    gb_sets:is_member(L, St#st.labels).
+    cerl_sets:is_element(L, St#st.labels).
 
 %% is_unreachable_after(Instruction) -> boolean()
 %%  Test whether the code after Instruction is unreachable.
@@ -472,14 +478,14 @@ is_exit_instruction(_) -> false.
 %%  (including inside blocks).
 
 is_label_used_in(Lbl, Is) ->
-    is_label_used_in_1(Is, Lbl, gb_sets:empty()).
+    is_label_used_in_1(Is, Lbl, cerl_sets:new()).
 
 is_label_used_in_1([{block,Block}|Is], Lbl, Empty) ->
     lists:any(fun(I) -> is_label_used_in_block(I, Lbl) end, Block)
 	orelse is_label_used_in_1(Is, Lbl, Empty);
 is_label_used_in_1([I|Is], Lbl, Empty) ->
     Used = ulbl(I, Empty),
-    gb_sets:is_member(Lbl, Used) orelse is_label_used_in_1(Is, Lbl, Empty);
+    cerl_sets:is_element(Lbl, Used) orelse is_label_used_in_1(Is, Lbl, Empty);
 is_label_used_in_1([], _, _) -> false.
 
 is_label_used_in_block({set,_,_,Info}, Lbl) ->
@@ -506,7 +512,7 @@ remove_unused_labels(Is) ->
     rem_unused(Is, Used, []).
 
 rem_unused([{label,Lbl}=I|Is0], Used, [Prev|_]=Acc) ->
-    case gb_sets:is_member(Lbl, Used) of
+    case cerl_sets:is_element(Lbl, Used) of
 	false ->
 	    Is = case is_unreachable_after(Prev) of
 		     true -> drop_upto_label(Is0);
@@ -528,7 +534,7 @@ initial_labels([{line,_}|Is], Acc) ->
 initial_labels([{label,Lbl}|Is], Acc) ->
     initial_labels(Is, [Lbl|Acc]);
 initial_labels([{func_info,_,_,_},{label,Lbl}|_], Acc) ->
-    gb_sets:from_list([Lbl|Acc]).
+    cerl_sets:from_list([Lbl|Acc]).
 
 drop_upto_label([{label,_}|_]=Is) -> Is;
 drop_upto_label([_|Is]) -> drop_upto_label(Is);
@@ -576,10 +582,10 @@ ulbl({get_map_elements,Lbl,_Src,_List}, Used) ->
 ulbl(_, Used) -> Used.
 
 mark_used({f,0}, Used) -> Used;
-mark_used({f,L}, Used) -> gb_sets:add(L, Used).
+mark_used({f,L}, Used) -> cerl_sets:add_element(L, Used).
 
 mark_used_list([{f,L}|T], Used) ->
-    mark_used_list(T, gb_sets:add(L, Used));
+    mark_used_list(T, cerl_sets:add_element(L, Used));
 mark_used_list([_|T], Used) ->
     mark_used_list(T, Used);
 mark_used_list([], Used) -> Used.
diff --git a/lib/compiler/src/beam_type.erl b/lib/compiler/src/beam_type.erl
index 4731b5e78e..7ab548152e 100644
--- a/lib/compiler/src/beam_type.erl
+++ b/lib/compiler/src/beam_type.erl
@@ -554,10 +554,10 @@ flush(Rs, [{set,[_],[],{put_tuple,_}}|_]=Is0, Acc0) ->
     Acc = flush_all(Rs, Is0, Acc0),
     {[],Acc};
 flush(Rs0, [{set,Ds,Ss,_Op}|_], Acc0) ->
-    Save = gb_sets:from_list(Ss),
+    Save = cerl_sets:from_list(Ss),
     Acc = save_regs(Rs0, Save, Acc0),
     Rs1 = foldl(fun(S, A) -> mark(S, A, clean) end, Rs0, Ss),
-    Kill = gb_sets:from_list(Ds),
+    Kill = cerl_sets:from_list(Ds),
     Rs = kill_regs(Rs1, Kill),
     {Rs,Acc};
 flush(Rs0, Is, Acc0) ->
@@ -580,7 +580,7 @@ save_regs(Rs, Save, Acc) ->
     foldl(fun(R, A) -> save_reg(R, Save, A) end, Acc, Rs).
 
 save_reg({I,V,dirty}, Save, Acc) ->
-    case gb_sets:is_member(V, Save) of
+    case cerl_sets:is_element(V, Save) of
 	true -> [{set,[V],[{fr,I}],fmove}|checkerror(Acc)];
 	false -> Acc
     end;
@@ -590,7 +590,7 @@ kill_regs(Rs, Kill) ->
     [kill_reg(R, Kill) || R <- Rs].
 
 kill_reg({_,V,_}=R, Kill) ->
-    case gb_sets:is_member(V, Kill) of
+    case cerl_sets:is_element(V, Kill) of
 	true -> free;
 	false -> R
     end;
diff --git a/lib/compiler/src/cerl_sets.erl b/lib/compiler/src/cerl_sets.erl
new file mode 100644
index 0000000000..4df78dc432
--- /dev/null
+++ b/lib/compiler/src/cerl_sets.erl
@@ -0,0 +1,206 @@
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2000-2015. All Rights Reserved.
+%% 
+%% The contents of this file are subject to the Erlang Public License,
+%% Version 1.1, (the "License"); you may not use this file except in
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%% 
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%% 
+%% %CopyrightEnd%
+%%
+
+-module(cerl_sets).
+
+%% Standard interface.
+-export([new/0,is_set/1,size/1,to_list/1,from_list/1]).
+-export([is_element/2,add_element/2,del_element/2]).
+-export([union/2,union/1,intersection/2,intersection/1]).
+-export([is_disjoint/2]).
+-export([subtract/2,is_subset/2]).
+-export([fold/3,filter/2]).
+
+-export_type([set/0, set/1]).
+
+%%------------------------------------------------------------------------------
+
+-type set() :: set(_).
+-opaque set(Element) :: #{Element => 'ok'}.
+
+%%------------------------------------------------------------------------------
+
+%% new() -> Set
+-spec new() -> set().
+
+new() -> #{}.
+
+%% is_set(Set) -> boolean().
+%%  Return 'true' if Set is a set of elements, else 'false'.
+-spec is_set(Set) -> boolean() when
+      Set :: term().
+
+is_set(S) when is_map(S) -> true;
+is_set(_) -> false.
+
+%% size(Set) -> int().
+%%  Return the number of elements in Set.
+-spec size(Set) -> non_neg_integer() when
+      Set :: set().
+
+size(S) -> maps:size(S).
+
+%% to_list(Set) -> [Elem].
+%%  Return the elements in Set as a list.
+-spec to_list(Set) -> List when
+      Set :: set(Element),
+      List :: [Element].
+
+to_list(S) -> maps:keys(S).
+
+%% from_list([Elem]) -> Set.
+%%  Build a set from the elements in List.
+-spec from_list(List) -> Set when
+      List :: [Element],
+      Set :: set(Element).
+from_list(Ls) -> maps:from_list([{K,ok}||K<-Ls]).
+
+%% is_element(Element, Set) -> boolean().
+%%  Return 'true' if Element is an element of Set, else 'false'.
+-spec is_element(Element, Set) -> boolean() when
+      Set :: set(Element).
+
+is_element(E,S) ->
+    case S of
+        #{E := _} -> true;
+        _ -> false
+    end.
+
+%% add_element(Element, Set) -> Set.
+%%  Return Set with Element inserted in it.
+-spec add_element(Element, Set1) -> Set2 when
+      Set1 :: set(Element),
+      Set2 :: set(Element).
+
+add_element(E,S) -> S#{E=>ok}.
+
+-spec del_element(Element, Set1) -> Set2 when
+      Set1 :: set(Element),
+      Set2 :: set(Element).
+
+%% del_element(Element, Set) -> Set.
+%%  Return Set but with Element removed.
+del_element(E,S) -> maps:remove(E,S).
+
+%% union(Set1, Set2) -> Set
+%%  Return the union of Set1 and Set2.
+-spec union(Set1, Set2) -> Set3 when
+      Set1 :: set(Element),
+      Set2 :: set(Element),
+      Set3 :: set(Element).
+
+union(S1,S2) -> maps:merge(S1,S2).
+
+%% union([Set]) -> Set
+%%  Return the union of the list of sets.
+-spec union(SetList) -> Set when
+      SetList :: [set(Element)],
+      Set :: set(Element).
+
+union([S1,S2|Ss]) ->
+    union1(union(S1, S2), Ss);
+union([S]) -> S;
+union([]) -> new().
+
+union1(S1, [S2|Ss]) ->
+    union1(union(S1, S2), Ss);
+union1(S1, []) -> S1.
+
+%% intersection(Set1, Set2) -> Set.
+%%  Return the intersection of Set1 and Set2.
+-spec intersection(Set1, Set2) -> Set3 when
+      Set1 :: set(Element),
+      Set2 :: set(Element),
+      Set3 :: set(Element).
+
+intersection(S1, S2) ->
+    filter(fun (E) -> is_element(E, S1) end, S2).
+
+%% intersection([Set]) -> Set.
+%%  Return the intersection of the list of sets.
+-spec intersection(SetList) -> Set when
+      SetList :: [set(Element),...],
+      Set :: set(Element).
+
+intersection([S1,S2|Ss]) ->
+    intersection1(intersection(S1, S2), Ss);
+intersection([S]) -> S.
+
+intersection1(S1, [S2|Ss]) ->
+    intersection1(intersection(S1, S2), Ss);
+intersection1(S1, []) -> S1.
+
+%% is_disjoint(Set1, Set2) -> boolean().
+%%  Check whether Set1 and Set2 are disjoint.
+-spec is_disjoint(Set1, Set2) -> boolean() when
+      Set1 :: set(Element),
+      Set2 :: set(Element).
+
+is_disjoint(S1, S2) when map_size(S1) < map_size(S2) ->
+    fold(fun (_, false) -> false;
+	     (E, true) -> not is_element(E, S2)
+	 end, true, S1);
+is_disjoint(S1, S2) ->
+    fold(fun (_, false) -> false;
+	     (E, true) -> not is_element(E, S1)
+	 end, true, S2).
+
+%% subtract(Set1, Set2) -> Set.
+%%  Return all and only the elements of Set1 which are not also in
+%%  Set2.
+-spec subtract(Set1, Set2) -> Set3 when
+      Set1 :: set(Element),
+      Set2 :: set(Element),
+      Set3 :: set(Element).
+
+subtract(S1, S2) ->
+    filter(fun (E) -> not is_element(E, S2) end, S1).
+
+%% is_subset(Set1, Set2) -> boolean().
+%%  Return 'true' when every element of Set1 is also a member of
+%%  Set2, else 'false'.
+-spec is_subset(Set1, Set2) -> boolean() when
+      Set1 :: set(Element),
+      Set2 :: set(Element).
+
+is_subset(S1, S2) ->
+    fold(fun (E, Sub) -> Sub andalso is_element(E, S2) end, true, S1).
+
+%% fold(Fun, Accumulator, Set) -> Accumulator.
+%%  Fold function Fun over all elements in Set and return Accumulator.
+-spec fold(Function, Acc0, Set) -> Acc1 when
+      Function :: fun((Element, AccIn) -> AccOut),
+      Set :: set(Element),
+      Acc0 :: Acc,
+      Acc1 :: Acc,
+      AccIn :: Acc,
+      AccOut :: Acc.
+
+fold(F, Init, D) ->
+    lists:foldl(fun(E,Acc) -> F(E,Acc) end,Init,maps:keys(D)).
+
+%% filter(Fun, Set) -> Set.
+%%  Filter Set with Fun.
+-spec filter(Pred, Set1) -> Set2 when
+      Pred :: fun((Element) -> boolean()),
+      Set1 :: set(Element),
+      Set2 :: set(Element).
+
+filter(F, D) ->
+    maps:from_list(lists:filter(fun({K,_}) -> F(K) end, maps:to_list(D))).
diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src
index 17d1bd91ce..0bfd998301 100644
--- a/lib/compiler/src/compiler.app.src
+++ b/lib/compiler/src/compiler.app.src
@@ -45,6 +45,7 @@
 	     cerl,
 	     cerl_clauses,
 	     cerl_inline,
+             cerl_sets,
 	     cerl_trees,
 	     compile,
 	     core_scan,
diff --git a/lib/compiler/src/sys_core_fold.erl b/lib/compiler/src/sys_core_fold.erl
index 6f8279f65e..102a6951e8 100644
--- a/lib/compiler/src/sys_core_fold.erl
+++ b/lib/compiler/src/sys_core_fold.erl
@@ -92,10 +92,10 @@
 -endif.
 
 %% Variable value info.
--record(sub, {v=[],				%Variable substitutions
-	      s=[],				%Variables in scope
-	      t=[],				%Types
-	      in_guard=false}).			%In guard or not.
+-record(sub, {v=[],                                 %Variable substitutions
+              s=cerl_sets:new() :: cerl_sets:set(), %Variables in scope
+              t=#{} :: map(),                       %Types
+              in_guard=false}).                     %In guard or not.
 
 -type type_info() :: cerl:cerl() | 'bool' | 'integer'.
 -type yes_no_maybe() :: 'yes' | 'no' | 'maybe'.
@@ -1123,7 +1123,7 @@ let_substs(Vs0, As0, Sub0) ->
     {Vs2,As1,Ss} = let_substs_1(Vs1, As0, Sub1),
     Sub2 = sub_add_scope([V || #c_var{name=V} <- Vs2], Sub1),
     {Vs2,As1,
-     foldl(fun ({V,S}, Sub) -> sub_set_name(V, S, Sub) end, Sub2, Ss)}.
+    foldl(fun ({V,S}, Sub) -> sub_set_name(V, S, Sub) end, Sub2, Ss)}.
 
 let_substs_1(Vs, #c_values{es=As}, Sub) ->
     let_subst_list(Vs, As, Sub);
@@ -1242,10 +1242,10 @@ is_subst(_) -> false.
 %%  to force renaming if variables in the scope occurs as pattern
 %%  variables.
 
-sub_new() -> #sub{v=orddict:new(),s=gb_trees:empty(),t=[]}.
+sub_new() -> #sub{v=orddict:new(),s=cerl_sets:new(),t=#{}}.
 
 sub_new(#sub{}=Sub) ->
-    Sub#sub{v=orddict:new(),t=[]}.
+    Sub#sub{v=orddict:new(),t=#{}}.
 
 sub_new_preserve_types(#sub{}=Sub) ->
     Sub#sub{v=orddict:new()}.
@@ -1262,16 +1262,16 @@ sub_set_var(#c_var{name=V}, Val, Sub) ->
 sub_set_name(V, Val, #sub{v=S,s=Scope,t=Tdb0}=Sub) ->
     Tdb1 = kill_types(V, Tdb0),
     Tdb = copy_type(V, Val, Tdb1),
-    Sub#sub{v=orddict:store(V, Val, S),s=gb_sets:add(V, Scope),t=Tdb}.
+    Sub#sub{v=orddict:store(V, Val, S),s=cerl_sets:add_element(V, Scope),t=Tdb}.
 
 sub_del_var(#c_var{name=V}, #sub{v=S,s=Scope,t=Tdb}=Sub) ->
     %% Profiling shows that for programs with many record operations,
     %% sub_del_var/2 is a bottleneck. Since the scope contains all
     %% variables that are live, we know that V cannot be present in S
     %% if it is not in the scope.
-    case gb_sets:is_member(V, Scope) of
+    case cerl_sets:is_element(V, Scope) of
 	false ->
-	    Sub#sub{s=gb_sets:insert(V, Scope)};
+	    Sub#sub{s=cerl_sets:add_element(V, Scope)};
 	true ->
 	    Sub#sub{v=orddict:erase(V, S),t=kill_types(V, Tdb)}
     end.
@@ -1282,12 +1282,12 @@ sub_subst_var(#c_var{name=V}, Val, #sub{v=S0}) ->
 
 sub_add_scope(Vs, #sub{s=Scope0}=Sub) ->
     Scope = foldl(fun(V, S) when is_integer(V); is_atom(V) ->
-			  gb_sets:add(V, S)
+			  cerl_sets:add_element(V, S)
 		  end, Scope0, Vs),
     Sub#sub{s=Scope}.
 
 sub_subst_scope(#sub{v=S0,s=Scope}=Sub) ->
-    S = [{-1,#c_var{name=Sv}} || Sv <- gb_sets:to_list(Scope)]++S0,
+    S = [{-1,#c_var{name=Sv}} || Sv <- cerl_sets:to_list(Scope)]++S0,
     Sub#sub{v=S}.
 
 sub_is_val(#c_var{name=V}, #sub{v=S,s=Scope}) ->
@@ -1295,7 +1295,7 @@ sub_is_val(#c_var{name=V}, #sub{v=S,s=Scope}) ->
     %% became the new bottleneck. Since the scope contains all
     %% live variables, a variable V can only be the target for
     %% a substitution if it is in the scope.
-    gb_sets:is_member(V, Scope) andalso v_is_value(V, S).
+    cerl_sets:is_element(V, Scope) andalso v_is_value(V, S).
 
 v_is_value(Var, [{_,#c_var{name=Var}}|_]) -> true;
 v_is_value(Var, [_|T]) -> v_is_value(Var, T);
@@ -1760,8 +1760,9 @@ case_opt_compiler_generated(Core) ->
 %%  return Expr0 unchanged.
 %%
 case_expand_var(E, #sub{t=Tdb}) ->
-    case orddict:find(cerl:var_name(E), Tdb) of
-	{ok,T0} ->
+    Key = cerl:var_name(E),
+    case Tdb of
+        #{Key:=T0} ->
 	    case cerl:is_c_tuple(T0) of
 		false ->
 		    E;
@@ -1785,7 +1786,7 @@ case_expand_var(E, #sub{t=Tdb}) ->
 			    E
 		    end
 	    end;
-	error ->
+        _ ->
 	    E
     end.
 
@@ -2147,7 +2148,7 @@ is_bool_expr_list([], _) -> true.
 %%  functions, or is_record/2).
 %%
 is_safe_bool_expr(Core, Sub) ->
-    is_safe_bool_expr_1(Core, Sub, gb_sets:empty()).
+    is_safe_bool_expr_1(Core, Sub, cerl_sets:new()).
 
 is_safe_bool_expr_1(#c_call{module=#c_literal{val=erlang},
                             name=#c_literal{val=is_record},
@@ -2193,7 +2194,7 @@ is_safe_bool_expr_1(#c_let{vars=Vars,arg=Arg,body=B}, Sub, BoolVars) ->
 	true ->
 	    case {is_safe_bool_expr_1(Arg, Sub, BoolVars),Vars} of
 		{true,[#c_var{name=V}]} ->
-		    is_safe_bool_expr_1(B, Sub, gb_sets:add(V, BoolVars));
+		    is_safe_bool_expr_1(B, Sub, cerl_sets:add_element(V, BoolVars));
 		{false,_} ->
 		    is_safe_bool_expr_1(B, Sub, BoolVars)
 	    end;
@@ -2202,7 +2203,7 @@ is_safe_bool_expr_1(#c_let{vars=Vars,arg=Arg,body=B}, Sub, BoolVars) ->
 is_safe_bool_expr_1(#c_literal{val=Val}, _Sub, _) ->
     is_boolean(Val);
 is_safe_bool_expr_1(#c_var{name=V}, _Sub, BoolVars) ->
-    gb_sets:is_element(V, BoolVars);
+    cerl_sets:is_element(V, BoolVars);
 is_safe_bool_expr_1(_, _, _) -> false.
 
 is_safe_bool_expr_list([C|Cs], Sub, BoolVars) ->
@@ -2236,7 +2237,7 @@ move_let_into_expr(#c_let{vars=InnerVs0,body=InnerBody0}=Inner,
     %%    in <InnerBody>
     %%
     Arg = body(Arg0, Sub0),
-    ScopeSub0 = sub_subst_scope(Sub0#sub{t=[]}),
+    ScopeSub0 = sub_subst_scope(Sub0#sub{t=#{}}),
     {OuterVs,ScopeSub} = pattern_list(OuterVs0, ScopeSub0),
 
     OuterBody = body(OuterBody0, ScopeSub),
@@ -2275,15 +2276,15 @@ move_let_into_expr(#c_let{vars=Lvs0,body=Lbody0}=Let,
 	    CaVars0 = Ca0#c_clause.pats,
 	    G0 = Ca0#c_clause.guard,
 	    B0 = Ca0#c_clause.body,
-	    ScopeSub0 = sub_subst_scope(Sub0#sub{t=[]}),
+	    ScopeSub0 = sub_subst_scope(Sub0#sub{t=#{}}),
 	    {CaVars,ScopeSub} = pattern_list(CaVars0, ScopeSub0),
 	    G = guard(G0, ScopeSub),
 
 	    B1 = body(B0, ScopeSub),
 
 	    {Lvs,B2,Sub1} = let_substs(Lvs0, B1, Sub0),
-	    Sub2 = Sub1#sub{s=gb_sets:union(ScopeSub#sub.s,
-					    Sub1#sub.s)},
+	    Sub2 = Sub1#sub{s=cerl_sets:union(ScopeSub#sub.s,
+                                              Sub1#sub.s)},
 	    Lbody = body(Lbody0, Sub2),
 	    B = Let#c_let{vars=Lvs,arg=core_lib:make_values(B2),body=Lbody},
 
@@ -2574,7 +2575,7 @@ move_case_into_arg(#c_case{arg=#c_let{vars=OuterVars0,arg=OuterArg,
     %% let <OuterVars> = <OuterArg>
     %% in case <InnerArg> of <InnerClauses> end
     %%
-    ScopeSub0 = sub_subst_scope(Sub#sub{t=[]}),
+    ScopeSub0 = sub_subst_scope(Sub#sub{t=#{}}),
     {OuterVars,ScopeSub} = pattern_list(OuterVars0, ScopeSub0),
     InnerArg = body(InnerArg0, ScopeSub),
     Outer#c_let{vars=OuterVars,arg=OuterArg,
@@ -2603,7 +2604,7 @@ move_case_into_arg(#c_case{arg=#c_case{arg=OuterArg,
             %%     <OuterCb>
             %% end
             %%
-            ScopeSub0 = sub_subst_scope(Sub#sub{t=[]}),
+            ScopeSub0 = sub_subst_scope(Sub#sub{t=#{}}),
             {OuterPats,ScopeSub} = pattern_list(OuterPats0, ScopeSub0),
             OuterGuard = guard(OuterGuard0, ScopeSub),
             InnerArg = body(InnerArg0, ScopeSub),
@@ -2688,9 +2689,9 @@ is_any_var_used([], _) -> false.
 -spec get_type(cerl:cerl(), #sub{}) -> type_info() | 'none'.
 
 get_type(#c_var{name=V}, #sub{t=Tdb}) ->
-    case orddict:find(V, Tdb) of
-	{ok,Type} -> Type;
-	error -> none
+    case Tdb of
+        #{V:=Type} -> Type;
+        _ -> none
     end;
 get_type(C, _) ->
     case cerl:type(C) of
@@ -2805,35 +2806,38 @@ update_types_1(#c_var{name=V,anno=Anno}, Pat, Types) ->
 update_types_1(_, _, Types) -> Types.
 
 update_types_2(V, [#c_tuple{}=P], Types) ->
-    orddict:store(V, P, Types);
+    Types#{V=>P};
 update_types_2(V, [#c_literal{val=Bool}], Types) when is_boolean(Bool) ->
-    orddict:store(V, bool, Types);
+    Types#{V=>bool};
 update_types_2(V, [Type], Types) when is_atom(Type) ->
-    orddict:store(V, Type, Types);
+    Types#{V=>Type};
 update_types_2(_, _, Types) -> Types.
 
 %% kill_types(V, Tdb) -> Tdb'
 %%  Kill any entries that references the variable,
 %%  either in the key or in the value.
 
-kill_types(V, [{V,_}|Tdb]) ->
-    kill_types(V, Tdb);
-kill_types(V, [{_,#c_tuple{}=Tuple}=Entry|Tdb]) ->
+kill_types(V, Tdb) ->
+    maps:from_list(kill_types2(V,maps:to_list(Tdb))).
+
+kill_types2(V, [{V,_}|Tdb]) ->
+    kill_types2(V, Tdb);
+kill_types2(V, [{_,#c_tuple{}=Tuple}=Entry|Tdb]) ->
     case core_lib:is_var_used(V, Tuple) of
-	false -> [Entry|kill_types(V, Tdb)];
-	true -> kill_types(V, Tdb)
+	false -> [Entry|kill_types2(V, Tdb)];
+	true -> kill_types2(V, Tdb)
     end;
-kill_types(V, [{_,Atom}=Entry|Tdb]) when is_atom(Atom) ->
-    [Entry|kill_types(V, Tdb)];
-kill_types(_, []) -> [].
+kill_types2(V, [{_,Atom}=Entry|Tdb]) when is_atom(Atom) ->
+    [Entry|kill_types2(V, Tdb)];
+kill_types2(_, []) -> [].
 
 %% copy_type(DestVar, SrcVar, Tdb) -> Tdb'
 %%  If the SrcVar has a type, assign it to DestVar.
 %%
 copy_type(V, #c_var{name=Src}, Tdb) ->
-    case orddict:find(Src, Tdb) of
-	{ok,Type} -> orddict:store(V, Type, Tdb);
-	error -> Tdb
+    case Tdb of
+        #{Src:=Type} -> Tdb#{V=>Type};
+        _ -> Tdb
     end;
 copy_type(_, _, Tdb) -> Tdb.
 
@@ -3237,12 +3241,12 @@ format_error(bin_var_used_in_guard) ->
 verify_scope(E, #sub{s=Scope}) ->
     Free0 = cerl_trees:free_variables(E),
     Free = [V || V <- Free0, not is_tuple(V)],	%Ignore function names.
-    case ordsets:is_subset(Free, gb_sets:to_list(Scope)) of
+    case ordsets:is_subset(Free, cerl_sets:to_list(Scope)) of
 	true -> true;
 	false ->
 	    io:format("~p\n", [E]),
 	    io:format("~p\n", [Free]),
-	    io:format("~p\n", [gb_sets:to_list(Scope)]),
+	    io:format("~p\n", [cerl_sets:to_list(Scope)]),
 	    false
     end.
 -endif.
diff --git a/lib/compiler/src/v3_codegen.erl b/lib/compiler/src/v3_codegen.erl
index aa2ebc0f85..c9b1a45cfc 100644
--- a/lib/compiler/src/v3_codegen.erl
+++ b/lib/compiler/src/v3_codegen.erl
@@ -43,7 +43,7 @@
 -export([module/2]).
 
 -import(lists, [member/2,keymember/3,keysort/2,keydelete/3,
-		append/1,map/2,flatmap/2,filter/2,foldl/3,foldr/3,mapfoldl/3,
+		append/1,flatmap/2,filter/2,foldl/3,foldr/3,mapfoldl/3,
 		sort/1,reverse/1,reverse/2]).
 -import(v3_life, [vdb_find/2]).
 
@@ -57,8 +57,7 @@
 	     break,				%Break label
 	     recv,				%Receive label
 	     is_top_block,			%Boolean: top block or not
-	     functable=gb_trees:empty(),	%Gb tree of local functions:
-						% {{Name,Arity},Label}
+	     functable=#{},	                %Map of local functions: {Name,Arity}=>Label
 	     in_catch=false,			%Inside a catch or not.
 	     need_frame,			%Need a stack frame.
 	     ultimate_failure			%Label for ultimate match failure.
@@ -673,9 +672,7 @@ select_val_cg(Type, R, [Val, {f,Lbl}], Tf, Vf, [{label,Lbl}|Sis]) ->
     [{test,select_type_test(Type),{f,Tf},[R]},
      {test,is_eq_exact,{f,Vf},[R,{Type,Val}]}|Sis];
 select_val_cg(Type, R, Vls0, Tf, Vf, Sis) ->
-    Vls1 = map(fun ({f,_Lbl} = F) -> F;
-		   (Value) -> {Type,Value}
-	       end, Vls0),
+    Vls1 = [case Value of {f,_Lbl} -> Value; _ -> {Type,Value} end || Value <- Vls0],
     [{test,select_type_test(Type),{f,Tf},[R]}, {select_val,R,{f,Vf},{list,Vls1}}|Sis].
     
 select_type_test(integer) -> is_integer;
@@ -1080,7 +1077,7 @@ protected_cg(Ts, Rs, _Fail, I, Vdb, Bef, St0) ->
 				  St2#cg{bfail=Pfail}),
     %%ok = io:fwrite("cg ~w: ~p~n", [?LINE,{Rs,I,Vdb,Aft}]),
     %% Set return values to false.
-    Mis = map(fun ({var,V}) -> {move,{atom,false},fetch_var(V, Aft)} end, Rs),
+    Mis = [{move,{atom,false},fetch_var(V,Aft)}||{var,V} <- Rs],
     {Tis ++ [{jump,{f,Psucc}},
 	     {label,Pfail}] ++ Mis ++ [{label,Psucc}],
      Aft,St3#cg{bfail=St0#cg.bfail}}.    
@@ -1263,13 +1260,12 @@ enter_line(_, _, _) ->
 local_func_label(Name, Arity, St) ->
     local_func_label({Name,Arity}, St).
 
-local_func_label(Key, #cg{functable=Tab}=St0) ->
-    case gb_trees:lookup(Key, Tab) of
-	{value,Label} ->
-	    {Label,St0};
-	none ->
+local_func_label(Key, #cg{functable=Map}=St0) ->
+    case Map of
+        #{Key := Label} -> {Label,St0};
+        _ ->
   	    {Label,St} = new_label(St0),
-	    {Label,St#cg{functable=gb_trees:insert(Key, Label, Tab)}}
+	    {Label,St#cg{functable=Map#{Key => Label}}}
     end.
 
 %% need_stack_frame(State) -> State'
@@ -1992,25 +1988,28 @@ clear_dead(Sr, Until, Vdb) ->
 	  stk=clear_dead_stk(Sr#sr.stk, Until, Vdb)}.
 
 clear_dead_reg(Sr, Until, Vdb) ->
-    Reg = map(fun ({_I,V} = IV) ->
-		      case vdb_find(V, Vdb) of
-			  {V,_,L} when L > Until -> IV;
-			  _ -> free		%Remove anything else
-		      end;
-		  ({reserved,_I,_V} = Reserved) -> Reserved;
-		  (free) -> free
-	      end, Sr#sr.reg),
+    Reg = [case R of
+            {_I,V} = IV ->
+                case vdb_find(V, Vdb) of
+                    {V,_,L} when L > Until -> IV;
+                    _ -> free		%Remove anything else
+                end;
+            {reserved,_I,_V} = Reserved -> Reserved;
+            free -> free
+        end || R <- Sr#sr.reg],
     reserve(Sr#sr.res, Reg, Sr#sr.stk).
 
 clear_dead_stk(Stk, Until, Vdb) ->
-    map(fun ({V} = T) ->
-		case vdb_find(V, Vdb) of
-		    {V,_,L} when L > Until -> T;
-		    _ -> dead			%Remove anything else
-		end;
-	    (free) -> free;
-	    (dead) -> dead
-	end, Stk).
+    [case S of
+	    {V} = T ->
+            case vdb_find(V, Vdb) of
+                {V,_,L} when L > Until -> T;
+                _ -> dead   %Remove anything else
+            end;
+        free -> free;
+        dead -> dead
+     end || S <- Stk].
+
 
 %% sr_merge(Sr1, Sr2) -> Sr.
 %%  Merge two stack/register states keeping the longest of both stack
diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl
index 7dff58582e..c21b2a1505 100644
--- a/lib/compiler/src/v3_kernel.erl
+++ b/lib/compiler/src/v3_kernel.erl
@@ -114,7 +114,7 @@ copy_anno(Kdst, Ksrc) ->
 	       ff,				%Current function
 	       vcount=0,			%Variable counter
 	       fcount=0,			%Fun counter
-	       ds=[],				%Defined variables
+               ds=cerl_sets:new() :: cerl_sets:set(), %Defined variables
 	       funs=[],				%Fun functions
 	       free=[],				%Free variables
 	       ws=[]   :: [warning()],		%Warnings.
@@ -148,7 +148,7 @@ include_attribute(_) -> true.
 
 function({#c_var{name={F,Arity}=FA},Body}, St0) ->
     try
-	St1 = St0#kern{func=FA,ff=undefined,vcount=0,fcount=0,ds=sets:new()},
+	St1 = St0#kern{func=FA,ff=undefined,vcount=0,fcount=0,ds=cerl_sets:new()},
 	{#ifun{anno=Ab,vars=Kvs,body=B0},[],St2} = expr(Body, new_sub(), St1),
 	{B1,_,St3} = ubody(B0, return, St2),
 	%%B1 = B0, St3 = St2,				%Null second pass
@@ -715,15 +715,15 @@ force_variable(Ke, St0) ->
 %%  handling.
 
 pattern(#c_var{anno=A,name=V}, _Isub, Osub, St0) ->
-    case sets:is_element(V, St0#kern.ds) of
+    case cerl_sets:is_element(V, St0#kern.ds) of
 	true ->
 	    {New,St1} = new_var_name(St0),
 	    {#k_var{anno=A,name=New},
 	     set_vsub(V, New, Osub),
-	     St1#kern{ds=sets:add_element(New, St1#kern.ds)}};
+	     St1#kern{ds=cerl_sets:add_element(New, St1#kern.ds)}};
 	false ->
 	    {#k_var{anno=A,name=V},Osub,
-	     St0#kern{ds=sets:add_element(V, St0#kern.ds)}}
+	     St0#kern{ds=cerl_sets:add_element(V, St0#kern.ds)}}
     end;
 pattern(#c_literal{anno=A,val=Val}, _Isub, Osub, St) ->
     {#k_literal{anno=A,val=Val},Osub,St};
@@ -897,7 +897,7 @@ new_vars(0, St, Vs) -> {Vs,St}.
 make_vars(Vs) -> [ #k_var{name=V} || V <- Vs ].
 
 add_var_def(V, St) ->
-    St#kern{ds=sets:add_element(V#k_var.name, St#kern.ds)}.
+    St#kern{ds=cerl_sets:add_element(V#k_var.name, St#kern.ds)}.
 
 %%add_vars_def(Vs, St) ->
 %%    Ds = foldl(fun (#k_var{name=V}, Ds) -> add_element(V, Ds) end,
diff --git a/lib/compiler/src/v3_life.erl b/lib/compiler/src/v3_life.erl
index 4b1f1c3f71..ee0565efb6 100644
--- a/lib/compiler/src/v3_life.erl
+++ b/lib/compiler/src/v3_life.erl
@@ -411,7 +411,7 @@ is_gc_bif(Bif, Arity) ->
 %% must be sorted.
 
 init_vars(Vs) ->
-    sort([{V,0,0} || {var,V} <- Vs]).
+    vdb_new(Vs).
 
 new_vars([], _, Vdb) -> Vdb;
 new_vars([V], I, Vdb) -> vdb_store_new(V, {V,I,I}, Vdb);
@@ -430,6 +430,16 @@ use_vars(Vs, I, Vdb) -> vdb_update_vars(Vs, Vdb, I).
 add_var(V, F, L, Vdb) ->
     vdb_store_new(V, {V,F,L}, Vdb).
 
+%% is_in_guard() -> true|false.
+
+is_in_guard() ->
+    get(guard_refc) > 0.
+
+%% vdb
+
+vdb_new(Vs) ->
+    sort([{V,0,0} || {var,V} <- Vs]).
+
 vdb_find(V, Vdb) ->
     case lists:keyfind(V, 1, Vdb) of
 	false -> error;
@@ -471,8 +481,3 @@ vdb_sub(Min, Max, Vdb) ->
     [ if L >= Max -> {V,F,locked};
 	 true -> Vd
       end || {V,F,L}=Vd <- Vdb, F < Min, L >= Min ].
-
-%% is_in_guard() -> true|false.
-
-is_in_guard() ->
-    get(guard_refc) > 0.