Merge branch 'sverker/hipe-performance-algorithms/PR-1124/OTP-13810'

18 files changed, 501 insertions, 219 deletions

diff --git a/lib/hipe/flow/cfg.inc b/lib/hipe/flow/cfg.inc
index 0bad2a8dd7..a18bfbc526 100644
--- a/lib/hipe/flow/cfg.inc
+++ b/lib/hipe/flow/cfg.inc
@@ -343,7 +343,7 @@ remove_pred(HT, FromL, PredL) ->
   case gb_trees:lookup(FromL, HT) of
     {value, {Block, Succ, Preds}} ->
       Code = hipe_bb:code(Block),
-      NewCode = remove_pred_from_phis(Code, PredL, []),
+      NewCode = remove_pred_from_phis(PredL, Code),
       NewBlock = hipe_bb:code_update(Block, NewCode),      
       gb_trees:update(FromL, {NewBlock,Succ,lists:delete(PredL,Preds)}, HT);
     none ->
@@ -374,20 +374,20 @@ add_pred(HT, ToL, PredL) ->
 -ifdef(CFG_CAN_HAVE_PHI_NODES).
 %% phi-instructions in a removed block's successors must be aware of
 %% the change.
-remove_pred_from_phis(List = [I|Left], Label, Acc) ->
+remove_pred_from_phis(Label, List = [I|Left]) ->
   case is_phi(I) of
-    true -> 
-      NewAcc = [phi_remove_pred(I, Label)|Acc],
-      remove_pred_from_phis(Left, Label, NewAcc);
+    true ->
+      NewI = phi_remove_pred(I, Label),
+      [NewI | remove_pred_from_phis(Label, Left)];
     false ->
-      lists:reverse(Acc) ++ List
+      List
   end;
-remove_pred_from_phis([], _Label, Acc) ->
-  lists:reverse(Acc).
+remove_pred_from_phis(_Label, []) ->
+  [].
 -else.
 %% this is used for code representations like those of back-ends which
 %% do not have phi-nodes.
-remove_pred_from_phis(Code, _Label, _Acc) ->
+remove_pred_from_phis(_Label, Code) ->
   Code.
 -endif.
 
@@ -927,24 +927,52 @@ merge(BB, BB2, BB2_Label) ->
 
 remove_unreachable_code(CFG) ->
   Start = start_label(CFG),
-  Reachable = find_reachable([Start], CFG, gb_sets:from_list([Start])),
-  %% Reachable is an ordset: it comes from gb_sets:to_list/1.
-  %% So use ordset:subtract instead of '--' below.
-  Labels = ordsets:from_list(labels(CFG)),
-  case ordsets:subtract(Labels, Reachable) of
-    [] ->
-      CFG;
+  %% No unreachable block will make another block reachable, so no fixpoint
+  %% looping is required
+  Reachable = find_reachable([], [Start], CFG, #{Start=>[]}),
+  case [L || L <- labels(CFG), not maps:is_key(L, Reachable)] of
+    [] -> CFG;
     Remove ->
-      NewCFG = lists:foldl(fun(X, Acc) -> bb_remove(Acc, X) end, CFG, Remove),
-      remove_unreachable_code(NewCFG)
+      HT0 = CFG#cfg.table,
+      HT1 = lists:foldl(fun gb_trees:delete/2, HT0, Remove),
+      ReachableP = fun(Lbl) -> maps:is_key(Lbl, Reachable) end,
+      HT = gb_trees:map(fun(_,B)->prune_preds(B, ReachableP)end, HT1),
+      CFG#cfg{table=HT}
   end.
 
-find_reachable([Label|Left], CFG, Acc) ->
-  NewAcc = gb_sets:add(Label, Acc),
-  Succ = succ(CFG, Label),
-  find_reachable([X || X <- Succ, not gb_sets:is_member(X, Acc)] ++ Left,
-		 CFG, NewAcc);
-find_reachable([], _CFG, Acc) ->
-  gb_sets:to_list(Acc).
+find_reachable([], [], _CFG, Acc) -> Acc;
+find_reachable([Succ|Succs], Left, CFG, Acc) ->
+  case Acc of
+    #{Succ := _} -> find_reachable(Succs, Left, CFG, Acc);
+    #{} -> find_reachable(Succs, [Succ|Left], CFG, Acc#{Succ => []})
+  end;
+find_reachable([], [Label|Left], CFG, Acc) ->
+  find_reachable(succ(CFG, Label), Left, CFG, Acc).
+
+%% Batch prune unreachable predecessors. Asymptotically faster than deleting
+%% unreachable blocks one at a time with bb_remove, at least when
+%% CFG_CAN_HAVE_PHI_NODES is undefined. Otherwise a phi_remove_preds might be
+%% needed to achieve that.
+prune_preds(B={Block, Succ, Preds}, ReachableP) ->
+  case lists:partition(ReachableP, Preds) of
+    {_, []} -> B;
+    {NewPreds, Unreach} ->
+      NewCode = remove_preds_from_phis(Unreach, hipe_bb:code(Block)),
+      {hipe_bb:code_update(Block, NewCode), Succ, NewPreds}
+  end.
 
+-ifdef(CFG_CAN_HAVE_PHI_NODES).
+remove_preds_from_phis(_, []) -> [];
+remove_preds_from_phis(Preds, List=[I|Left]) ->
+  case is_phi(I) of
+    false -> List;
+    true ->
+      NewI = lists:foldl(fun(L,IA)->phi_remove_pred(IA,L)end,
+			 I, Preds),
+      [NewI | remove_preds_from_phis(Preds, Left)]
+  end.
+-else.
+remove_preds_from_phis(_, Code) -> Code.
 -endif.
+
+-endif. %% -ifdef(REMOVE_UNREACHABLE_CODE)
diff --git a/lib/hipe/flow/liveness.inc b/lib/hipe/flow/liveness.inc
index a1caa3e0ad..bffaa4e3df 100644
--- a/lib/hipe/flow/liveness.inc
+++ b/lib/hipe/flow/liveness.inc
@@ -49,6 +49,10 @@
 -endif.
 
 -include("../flow/cfg.hrl").
+-include("../main/hipe.hrl").
+
+-opaque liveness() :: map().
+-export_type([liveness/0]).
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%
@@ -72,7 +76,7 @@
 %% The generic liveness analysis
 %%
 
--spec analyze(cfg()) -> gb_trees:tree().
+-spec analyze(cfg()) -> liveness().
 
 -ifdef(HIPE_LIVENESS_CALC_LARGEST_LIVESET).
 analyze(CFG) ->
@@ -188,6 +192,7 @@ update_livein(Label, NewLiveIn, Liveness) ->
 %%
 %% LiveOut for a block is the union of the successors LiveIn
 %%
+-spec liveout(liveness(), _) -> [_].
 
 liveout(Liveness, L) ->
   Succ = successors(L, Liveness),
@@ -210,7 +215,7 @@ successors(L, Liveness) ->
   {_GK, _LiveIn, Successors} = liveness_lookup(L, Liveness),
   Successors.
 
--spec livein(gb_trees:tree(), _) -> [_].
+-spec livein(liveness(), _) -> [_].
 
 livein(Liveness, L) ->
   {_GK, LiveIn, _Successors} = liveness_lookup(L, Liveness),
@@ -292,18 +297,15 @@ strip([{_,Y}|Xs]) ->
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%
+-compile({inline, [liveness_lookup/2, liveness_update/3]}).
+
 liveness_init(List) ->
-  liveness_init(List, gb_trees:empty()).
+  maps:from_list(List).
 
-liveness_init([{Lbl, Data}|Left], Acc) ->
-  liveness_init(Left, gb_trees:insert(Lbl, Data, Acc));
-liveness_init([], Acc) ->
-  Acc.
-  
 liveness_lookup(Label, Liveness) ->
-  gb_trees:get(Label, Liveness).
+  maps:get(Label, Liveness).
 liveness_update(Label, Val, Liveness) ->
-  gb_trees:update(Label, Val, Liveness).
+  maps:update(Label, Val, Liveness).
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
diff --git a/lib/hipe/icode/hipe_icode_bincomp.erl b/lib/hipe/icode/hipe_icode_bincomp.erl
index 5a27519141..5ee6fe2c87 100644
--- a/lib/hipe/icode/hipe_icode_bincomp.erl
+++ b/lib/hipe/icode/hipe_icode_bincomp.erl
@@ -40,8 +40,8 @@
 -spec cfg(cfg()) -> cfg().
 
 cfg(Cfg1) ->
-  StartLbls = ordsets:from_list([hipe_icode_cfg:start_label(Cfg1)]),
-  find_bs_get_integer(StartLbls, Cfg1, StartLbls).
+  StartLbl = hipe_icode_cfg:start_label(Cfg1),
+  find_bs_get_integer([StartLbl], Cfg1, set_from_list([StartLbl])).
 
 find_bs_get_integer([Lbl|Rest], Cfg, Visited) ->
   BB = hipe_icode_cfg:bb(Cfg, Lbl),
@@ -55,10 +55,10 @@ find_bs_get_integer([Lbl|Rest], Cfg, Visited) ->
        not_ok ->
 	 Cfg
      end,
-  Succs = ordsets:from_list(hipe_icode_cfg:succ(NewCfg, Lbl)),
-  NewSuccs = ordsets:subtract(Succs, Visited),
-  NewLbls = ordsets:union(NewSuccs, Rest),
-  NewVisited = ordsets:union(NewSuccs, Visited),
+  Succs = hipe_icode_cfg:succ(NewCfg, Lbl),
+  NewSuccs = not_visited(Succs, Visited),
+  NewLbls = NewSuccs ++ Rest,
+  NewVisited = set_union(set_from_list(NewSuccs), Visited),
   find_bs_get_integer(NewLbls, NewCfg, NewVisited);
 find_bs_get_integer([], Cfg, _) ->
   Cfg.
@@ -177,3 +177,19 @@ make_butlast([{Res, Size}|Rest], Var) ->
 			[Var, hipe_icode:mk_const((1 bsl Size)-1)]),
    hipe_icode:mk_primop([NewVar], 'bsr', [Var, hipe_icode:mk_const(Size)])
    |make_butlast(Rest, NewVar)].
+
+%%--------------------------------------------------------------------
+%% Sets
+
+set_from_list([]) -> #{};
+set_from_list(L) ->
+  maps:from_list([{E, []} || E <- L]).
+
+not_visited([], _) -> [];
+not_visited([E|T], M) ->
+  case M of
+    #{E := _} -> not_visited(T, M);
+    _ -> [E|not_visited(T, M)]
+  end.
+
+set_union(A, B) -> maps:merge(A, B).
diff --git a/lib/hipe/icode/hipe_icode_coordinator.erl b/lib/hipe/icode/hipe_icode_coordinator.erl
index d2f8748535..b073954ce7 100644
--- a/lib/hipe/icode/hipe_icode_coordinator.erl
+++ b/lib/hipe/icode/hipe_icode_coordinator.erl
@@ -106,12 +106,29 @@ handle_no_change_done(MFA, {Queue, Busy}) ->
   {Queue, Busy -- [MFA]}.
 
 last_action(PM, ServerPid, Mod, All) ->
-  lists:foreach(fun (MFA) ->
-		    gb_trees:get(MFA, PM) ! {done, final_funs(ServerPid, Mod)},
-		    receive 
-		      {done_rewrite, MFA} -> ok
-		    end
-		end, All).
+  last_action(PM, ServerPid, Mod, All, []).
+
+last_action(_, _, _, [], []) -> ok;
+last_action(PM, ServerPid, Mod, [], [MFA|Busy]) ->
+  receive
+    {done_rewrite, MFA} ->
+      last_action(PM, ServerPid, Mod, [], Busy)
+  end;
+last_action(PM, ServerPid, Mod, All0, Busy) ->
+  receive
+    {done_rewrite, MFA} ->
+      last_action(PM, ServerPid, Mod, All0, Busy -- [MFA])
+  after 0 ->
+      case ?MAX_CONCURRENT - length(Busy) of
+	X when is_integer(X), X > 0 ->
+	  [MFA|All1] = All0,
+	  gb_trees:get(MFA, PM) ! {done, final_funs(ServerPid, Mod)},
+	  last_action(PM, ServerPid, Mod, All1, [MFA|Busy]);
+	X when is_integer(X) ->
+	  Busy1 = receive {done_rewrite, MFA} -> Busy -- [MFA] end,
+	  last_action(PM, ServerPid, Mod, All0, Busy1)
+      end
+  end.
 
 restart_funs({Queue, Busy} = QB, PM, All, ServerPid) ->
   case ?MAX_CONCURRENT - length(Busy) of
diff --git a/lib/hipe/icode/hipe_icode_range.erl b/lib/hipe/icode/hipe_icode_range.erl
index 12ed796690..af160769a1 100644
--- a/lib/hipe/icode/hipe_icode_range.erl
+++ b/lib/hipe/icode/hipe_icode_range.erl
@@ -73,8 +73,8 @@
 -type final_fun() :: fun((mfa(), [range()]) -> 'ok').
 -type data() :: {mfa(), args_fun(), call_fun(), final_fun()}.
 -type label() :: non_neg_integer().
--type info() :: gb_trees:tree().
--type work_list() :: {[label()], [label()], sets:set()}.
+-type info() :: map().
+-type work_list() :: {[label()], [label()], set(label())}.
 -type variable() :: #icode_variable{}.
 -type annotated_variable() :: #icode_variable{}.
 -type argument() :: #icode_const{} | variable().
@@ -82,10 +82,9 @@
 -type instr_split_info()  :: {icode_instr(), [{label(),info()}]}.
 -type last_instr_return() :: {instr_split_info(), range()}.
 
--record(state, {info_map = gb_trees:empty()	:: info(), 
-		counter  = dict:new()		:: dict:dict(),
-		cfg				:: cfg(), 
-		liveness = gb_trees:empty()	:: gb_trees:tree(),
+-record(state, {info_map = #{}			:: info(),
+		cfg				:: cfg(),
+		liveness			:: hipe_icode_ssa:liveness(),
 		ret_type			:: range(),
 		lookup_fun			:: call_fun(),
 		result_action			:: final_fun()}).
@@ -187,17 +186,16 @@ safe_analyse(CFG, Data={MFA,_,_,_}) ->
 rewrite_blocks(State) ->
   CFG = state__cfg(State),
   Start = hipe_icode_cfg:start_label(CFG),
-  rewrite_blocks([Start], State, [Start]).
+  rewrite_blocks([Start], State, set_from_list([Start])).
 
--spec rewrite_blocks([label()], state(), [label()]) -> state().
+-spec rewrite_blocks([label()], state(), set(label())) -> state().
 
 rewrite_blocks([Next|Rest], State, Visited) ->
   Info = state__info_in(State, Next),
   {NewState, NewLabels} = analyse_block(Next, Info, State, true),
-  NewLabelsSet = ordsets:from_list(NewLabels),
-  RealNew = ordsets:subtract(NewLabelsSet, Visited),
-  NewVisited = ordsets:union([RealNew, Visited, [Next]]),
-  NewWork = ordsets:union([RealNew, Rest]),
+  RealNew = not_visited(NewLabels, Visited),
+  NewVisited = set_union(set_from_list(RealNew), Visited),
+  NewWork = RealNew ++ Rest,
   rewrite_blocks(NewWork, NewState, NewVisited);
 rewrite_blocks([], State, _) ->
   State.
@@ -1661,8 +1659,8 @@ state__init(Cfg, {MFA, ArgsFun, CallFun, FinalFun}) ->
     false ->
       NewParams = lists:zipwith(fun update_info/2, Params, Ranges),
       NewCfg = hipe_icode_cfg:params_update(Cfg, NewParams),
-      Info = enter_defines(NewParams, gb_trees:empty()),
-      InfoMap = gb_trees:insert({Start, in}, Info, gb_trees:empty()),
+      Info = enter_defines(NewParams, #{}),
+      InfoMap = #{{Start, in} => Info},
       #state{info_map=InfoMap, cfg=NewCfg, liveness=Liveness,
 	     ret_type=none_type(),
 	     lookup_fun=CallFun, result_action=FinalFun}
@@ -1700,7 +1698,7 @@ state__info_in(S, Label) ->
   state__info(S, {Label, in}).
 
 state__info(#state{info_map=IM}, Key) ->
-  gb_trees:get(Key, IM).
+  maps:get(Key, IM).
 
 state__update_info(State, LabelInfo, Rewrite) ->
   update_info(LabelInfo, State, [], Rewrite).
@@ -1721,60 +1719,58 @@ update_info([], State, LabelAcc, _Rewrite) ->
 
 state__info_in_update(S=#state{info_map=IM,liveness=Liveness}, Label, Info) ->
   LabelIn = {Label, in},
-  case gb_trees:lookup(LabelIn, IM) of
-    none -> 
+  case IM of
+    #{LabelIn := OldInfo} ->
+      OldVars = maps:keys(OldInfo),
+      case join_info_in(OldVars, OldInfo, Info) of
+	fixpoint ->
+	  fixpoint;
+	NewInfo ->
+	  S#state{info_map=IM#{LabelIn := NewInfo}}
+      end;
+    _ ->
       LiveIn = hipe_icode_ssa:ssa_liveness__livein(Liveness, Label),
       NamesLiveIn = [hipe_icode:var_name(Var) || Var <- LiveIn,
 						 hipe_icode:is_var(Var)],
-      OldInfo = gb_trees:empty(),
+      OldInfo = #{},
       case join_info_in(NamesLiveIn, OldInfo, Info) of
 	fixpoint -> 
-	  S#state{info_map=gb_trees:insert(LabelIn, OldInfo, IM)};
-	NewInfo ->
-	  S#state{info_map=gb_trees:enter(LabelIn, NewInfo, IM)}
-      end;
-    {value, OldInfo} ->
-      OldVars = gb_trees:keys(OldInfo),
-      case join_info_in(OldVars, OldInfo, Info) of
-	fixpoint -> 
-	  fixpoint;
+	  S#state{info_map=IM#{LabelIn => OldInfo}};
 	NewInfo ->
-	  S#state{info_map=gb_trees:update(LabelIn, NewInfo, IM)}
+	  S#state{info_map=IM#{LabelIn => NewInfo}}
       end
   end.
 
 join_info_in(Vars, OldInfo, NewInfo) ->
-  case join_info_in(Vars, OldInfo, NewInfo, gb_trees:empty(), false) of
+  case join_info_in(Vars, OldInfo, NewInfo, #{}, false) of
     {Res, true} -> Res;
     {_, false} -> fixpoint
   end.
   
 join_info_in([Var|Left], Info1, Info2, Acc, Changed) ->
-  Type1 = gb_trees:lookup(Var, Info1),
-  Type2 = gb_trees:lookup(Var, Info2),
-  case {Type1, Type2} of
-    {none, none} ->
-      NewTree = gb_trees:insert(Var, none_type(), Acc),
-      join_info_in(Left, Info1, Info2, NewTree, true);
-    {none, {value, Val}} ->
-      NewTree = gb_trees:insert(Var, Val, Acc),
-      join_info_in(Left, Info1, Info2, NewTree, true);
-    {{value, Val}, none} ->
-      NewTree = gb_trees:insert(Var, Val, Acc),
+  case {Info1, Info2} of
+    {#{Var := Val}, #{Var := Val}} ->
+      NewTree = Acc#{Var => Val},
       join_info_in(Left, Info1, Info2, NewTree, Changed);
-    {{value, Val}, {value, Val}} ->
-      NewTree = gb_trees:insert(Var, Val, Acc),
-      join_info_in(Left, Info1, Info2, NewTree, Changed);
-    {{value, Val1}, {value, Val2}} ->
-      {NewChanged, NewVal} = 
+    {#{Var := Val1}, #{Var := Val2}} ->
+      {NewChanged, NewVal} =
 	case sup(Val1, Val2) of
 	  Val1 ->
 	    {Changed, Val1};
 	  Val ->
 	    {true, Val}
 	end,
-      NewTree = gb_trees:insert(Var, NewVal, Acc),
-      join_info_in(Left, Info1, Info2, NewTree, NewChanged)
+      NewTree = Acc#{Var => NewVal},
+      join_info_in(Left, Info1, Info2, NewTree, NewChanged);
+    {_, #{Var := Val}} ->
+      NewTree = Acc#{Var => Val},
+      join_info_in(Left, Info1, Info2, NewTree, true);
+    {#{Var := Val}, _} ->
+      NewTree = Acc#{Var => Val},
+      join_info_in(Left, Info1, Info2, NewTree, Changed);
+    {_, _} ->
+      NewTree = Acc#{Var => none_type()},
+      join_info_in(Left, Info1, Info2, NewTree, true)
   end;
 join_info_in([], _Info1, _Info2, Acc, NewChanged) ->
   {Acc, NewChanged}.
@@ -1786,7 +1782,7 @@ enter_defines([], Info) -> Info.
 enter_define({PossibleVar, Range = #range{}}, Info) ->
   case hipe_icode:is_var(PossibleVar) of
     true -> 
-      gb_trees:enter(hipe_icode:var_name(PossibleVar), Range, Info);
+      Info#{hipe_icode:var_name(PossibleVar) => Range};
     false ->
       Info
   end;
@@ -1795,7 +1791,7 @@ enter_define(PossibleVar, Info) ->
     true -> 
       case hipe_icode:variable_annotation(PossibleVar) of
 	{range_anno, #ann{range=Range}, _} ->
-	   gb_trees:enter(hipe_icode:var_name(PossibleVar), Range, Info);
+	   Info#{hipe_icode:var_name(PossibleVar) => Range};
 	_ ->
 	  Info
       end;
@@ -1810,11 +1806,10 @@ enter_vals(Ins, Info) ->
 lookup(PossibleVar, Info) ->
   case hipe_icode:is_var(PossibleVar) of
     true -> 
-      case gb_trees:lookup(hipe_icode:var_name(PossibleVar), Info) of
-	none ->
-	  none_type();
-	{value, Val} ->
-	  Val
+      PossibleVarName = hipe_icode:var_name(PossibleVar),
+      case Info of
+	#{PossibleVarName := Val} -> Val;
+	_ -> none_type()
       end;
     false ->
       none_type()
@@ -1828,10 +1823,10 @@ lookup(PossibleVar, Info) ->
 init_work(State) ->
   %% Labels = hipe_icode_cfg:reverse_postorder(state__cfg(State)),
   Labels = [hipe_icode_cfg:start_label(state__cfg(State))],
-  {Labels, [], sets:from_list(Labels)}.
+  {Labels, [], set_from_list(Labels)}.
 
 get_work({[Label|Left], List, Set}) ->
-  NewWork = {Left, List, sets:del_element(Label, Set)},
+  NewWork = {Left, List, maps:remove(Label, Set)},
   {Label, NewWork};
 get_work({[], [], _Set}) ->
   fixpoint;
@@ -1839,12 +1834,12 @@ get_work({[], List, Set}) ->
   get_work({lists:reverse(List), [], Set}).
 
 add_work(Work = {List1, List2, Set}, [Label|Left]) ->
-  case sets:is_element(Label, Set) of
-    true ->
+  case Set of
+    #{Label := _} ->
       add_work(Work, Left);
-    false ->
+    _ ->
       %% io:format("Adding work: ~w\n", [Label]),
-      add_work({List1, [Label|List2], sets:add_element(Label, Set)}, Left)
+      add_work({List1, [Label|List2], Set#{Label => []}}, Left)
   end;
 add_work(Work, []) ->
   Work.
@@ -1959,3 +1954,21 @@ next_down_limit(X) when is_integer(X), X > -16#8000000 -> -16#8000000;
 next_down_limit(X) when is_integer(X), X > -16#80000000 -> -16#80000000;
 next_down_limit(X) when is_integer(X), X > -16#800000000000000 -> -16#800000000000000;
 next_down_limit(_X) -> neg_inf.
+
+%%--------------------------------------------------------------------
+%% Sets
+
+-type set(E) :: #{E => []}.
+
+set_from_list([]) -> #{};
+set_from_list(L) ->
+  maps:from_list([{E, []} || E <- L]).
+
+not_visited([], _) -> [];
+not_visited([E|T], M) ->
+  case M of
+    #{E := []} -> not_visited(T, M);
+    _ -> [E|not_visited(T, M)]
+  end.
+
+set_union(A, B) -> maps:merge(A, B).
diff --git a/lib/hipe/icode/hipe_icode_ssa.erl b/lib/hipe/icode/hipe_icode_ssa.erl
index b222fbc7d2..aca13a2ff0 100644
--- a/lib/hipe/icode/hipe_icode_ssa.erl
+++ b/lib/hipe/icode/hipe_icode_ssa.erl
@@ -34,13 +34,16 @@
 -define(LIVENESS, hipe_icode_liveness).
 -define(LIVENESS_NEEDED, true).
 
+-export_type([liveness/0]).
+
 -include("hipe_icode.hrl").
 -include("../ssa/hipe_ssa.inc").
 
 %% Declarations for exported functions which are Icode-specific.
--spec ssa_liveness__analyze(#cfg{}) -> gb_trees:tree().
--spec ssa_liveness__livein(_, icode_lbl()) -> [#icode_variable{}].
-%% -spec ssa_liveness__livein(_, icode_lbl(), _) -> [#icode_var{}].
+-opaque liveness() :: liveness(icode_lbl(), #icode_variable{}).
+-spec ssa_liveness__analyze(#cfg{}) -> liveness().
+-spec ssa_liveness__livein(liveness(), icode_lbl()) -> [#icode_variable{}].
+%% -spec ssa_liveness__livein(liveness(), icode_lbl(), _) -> [#icode_var{}].
 
 %%----------------------------------------------------------------------
 %% Auxiliary operations which seriously differ between Icode and RTL.
diff --git a/lib/hipe/icode/hipe_icode_type.erl b/lib/hipe/icode/hipe_icode_type.erl
index 794c27ebcc..3f0e2998f1 100644
--- a/lib/hipe/icode/hipe_icode_type.erl
+++ b/lib/hipe/icode/hipe_icode_type.erl
@@ -100,7 +100,7 @@
 
 -record(state, {info_map  = gb_trees:empty() :: gb_trees:tree(),
 		cfg                          :: cfg(),
-		liveness  = gb_trees:empty() :: gb_trees:tree(),
+		liveness                     :: hipe_icode_ssa:liveness(),
 		arg_types                    :: [erl_types:erl_type()],
 		ret_type  = [t_none()]       :: [erl_types:erl_type()],
 		lookupfun                    :: call_fun(),
diff --git a/lib/hipe/main/hipe.app.src b/lib/hipe/main/hipe.app.src
index f8487151d7..acae2c637d 100644
--- a/lib/hipe/main/hipe.app.src
+++ b/lib/hipe/main/hipe.app.src
@@ -171,6 +171,7 @@
 	     hipe_rtl_to_sparc,
 	     hipe_rtl_to_x86,
 	     hipe_rtl_varmap,
+	     hipe_segment_trees,
 	     hipe_sdi,
 	     hipe_sparc,
 	     hipe_sparc_assemble,
diff --git a/lib/hipe/misc/Makefile b/lib/hipe/misc/Makefile
index 72cfff21a8..e5033e444b 100644
--- a/lib/hipe/misc/Makefile
+++ b/lib/hipe/misc/Makefile
@@ -44,7 +44,7 @@ RELSYSDIR = $(RELEASE_PATH)/lib/hipe-$(VSN)
 # Target Specs
 # ----------------------------------------------------
 ifdef HIPE_ENABLED
-HIPE_MODULES = hipe_data_pp hipe_pack_constants hipe_sdi 
+HIPE_MODULES = hipe_data_pp hipe_pack_constants hipe_sdi hipe_segment_trees
 else
 HIPE_MODULES =
 endif
diff --git a/lib/hipe/misc/hipe_sdi.erl b/lib/hipe/misc/hipe_sdi.erl
index fbb4b105f6..5ca64bc669 100644
--- a/lib/hipe/misc/hipe_sdi.erl
+++ b/lib/hipe/misc/hipe_sdi.erl
@@ -36,10 +36,13 @@
 %%------------------------------------------------------------------------
 
 -type hipe_array() :: integer(). % declare this in hipe.hrl or builtin?
+-type hipe_vector(E) :: {} | {E} | {E, E} | {E, E, E} | tuple().
 
 -type label()      :: non_neg_integer().
 -type address()    :: non_neg_integer().
 
+-type parents()    :: {hipe_vector(_ :: integer()), hipe_segment_trees:tree()}.
+
 %%------------------------------------------------------------------------
 
 -record(label_data, {address :: address(),
@@ -168,9 +171,11 @@ mk_long(N) ->
 %%% - Since the graph is traversed from child to parent nodes in
 %%%   Step 3, the edges are represented by a vector PARENTS[0..n-1]
 %%%   such that PARENTS[j] = { i | i is a parent of j }.
-%%% - An explicit PARENTS graph would have size O(n^2). Instead we
-%%%   compute PARENTS[j] from the SDI vector when needed. This
-%%%   reduces memory overheads, and may reduce time overheads too.
+%%% - An explicit PARENTS graph would have size O(n^2). Instead, we
+%%%   observe that (i is a parent of j) iff (j \in range(i)), where
+%%%   range(i) is a constant function. We can thus precompute all the
+%%%   ranges i and insert them into a data structure built for such
+%%%   queries. In this case, we use a segment tree.
 
 -spec mk_span(non_neg_integer(), tuple()) -> hipe_array().
 mk_span(N, SDIS) ->
@@ -188,7 +193,29 @@ initSPAN(SdiNr, N, SDIS, SPAN) ->
       initSPAN(SdiNr+1, N, SDIS, SPAN)
   end.
 
-mk_parents(N, SDIS) -> {N,SDIS}.
+-spec mk_parents(non_neg_integer(), tuple()) -> parents().
+mk_parents(N, SDIS) ->
+  PrevSDIS = vector_from_list(select_prev_sdis(N-1, SDIS, [])),
+  Ranges = parents_generate_ranges(N-1, PrevSDIS, []),
+  {PrevSDIS, hipe_segment_trees:build(Ranges)}.
+
+select_prev_sdis(-1, _SDIS, Acc) -> Acc;
+select_prev_sdis(SdiNr, SDIS, Acc) ->
+  #sdi_data{prevSdi=PrevSdi} = vector_sub(SDIS, SdiNr),
+  select_prev_sdis(SdiNr-1, SDIS, [PrevSdi|Acc]).
+
+parents_generate_ranges(-1, _PrevSDIS, Acc) -> Acc;
+parents_generate_ranges(SdiNr, PrevSDIS, Acc) ->
+  %% inclusive
+  {LO,HI} = parents_generate_range(SdiNr, PrevSDIS),
+  parents_generate_ranges(SdiNr-1, PrevSDIS, [{LO,HI}|Acc]).
+
+-compile({inline, parents_generate_range/2}).
+parents_generate_range(SdiNr, PrevSDIS) ->
+  PrevSdi = vector_sub(PrevSDIS, SdiNr),
+  if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi};	% forwards
+     true -> {PrevSdi+1, SdiNr-1}		% backwards
+  end.
 
 %%% "After the structure is built we process it as follows.
 %%% For any node i whose listed span exceeds the architectural
@@ -209,7 +236,7 @@ mk_parents(N, SDIS) -> {N,SDIS}.
 %%%   and PARENTS are no longer useful.
 
 -spec update_long(non_neg_integer(), tuple(), hipe_array(),
-		  {non_neg_integer(),tuple()},hipe_array()) -> 'ok'.
+		  parents(),hipe_array()) -> 'ok'.
 update_long(N, SDIS, SPAN, PARENTS, LONG) ->
   WKL = initWKL(N-1, SDIS, SPAN, []),
   processWKL(WKL, SDIS, SPAN, PARENTS, LONG).
@@ -225,46 +252,32 @@ initWKL(SdiNr, SDIS, SPAN, WKL) ->
   end.
 
 -spec processWKL([non_neg_integer()], tuple(), hipe_array(),
-		 {non_neg_integer(), tuple()}, hipe_array()) -> 'ok'.
+		 parents(), hipe_array()) -> 'ok'.
 processWKL([], _SDIS, _SPAN, _PARENTS, _LONG) -> ok;
-processWKL([Child|WKL], SDIS, SPAN, PARENTS, LONG) ->
-  WKL2 = updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG),
+processWKL([Child|WKL], SDIS, SPAN, PARENTS0, LONG) ->
+  {WKL2, PARENTS} =
+    case array_sub(SPAN, Child) of
+      0 -> {WKL, PARENTS0};				% removed
+      _ ->
+	SdiData = vector_sub(SDIS, Child),
+	Incr = sdiLongIncr(SdiData),
+	array_update(LONG, Child, Incr),
+	array_update(SPAN, Child, 0),			% remove child
+	PARENTS1 = deleteParent(PARENTS0, Child),
+	PS = parentsOfChild(PARENTS1, Child),
+	{updateParents(PS, Child, Incr, SDIS, SPAN, WKL), PARENTS1}
+    end,
   processWKL(WKL2, SDIS, SPAN, PARENTS, LONG).
 
--spec updateChild(non_neg_integer(), [non_neg_integer()], tuple(), hipe_array(),
-		  {non_neg_integer(),tuple()}, hipe_array()) -> [non_neg_integer()].
-updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG) ->
-  case array_sub(SPAN, Child) of
-    0 -> WKL;						% removed
-    _ ->
-      SdiData = vector_sub(SDIS, Child),
-      Incr = sdiLongIncr(SdiData),
-      array_update(LONG, Child, Incr),
-      array_update(SPAN, Child, 0),			% remove child
-      PS = parentsOfChild(PARENTS, Child),
-      updateParents(PS, Child, Incr, SDIS, SPAN, WKL)
-  end.
+-spec parentsOfChild(parents(), non_neg_integer()) -> [non_neg_integer()].
+parentsOfChild({_PrevSDIS, SegTree}, Child) ->
+  hipe_segment_trees:intersect(Child, SegTree).
 
--spec parentsOfChild({non_neg_integer(),tuple()},
-		     non_neg_integer()) -> [non_neg_integer()].
-parentsOfChild({N,SDIS}, Child) ->
-  parentsOfChild(N-1, SDIS, Child, []).
-
--spec parentsOfChild(integer(), tuple(), non_neg_integer(),
-		     [non_neg_integer()]) -> [non_neg_integer()].
-parentsOfChild(-1, _SDIS, _Child, PS) -> PS;
-parentsOfChild(SdiNr, SDIS, Child, PS) ->
-  SdiData = vector_sub(SDIS, SdiNr),
-  #sdi_data{prevSdi=PrevSdi} = SdiData,
-  {LO,HI} =	% inclusive
-    if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi};	% forwards
-       true -> {PrevSdi+1, SdiNr-1}		% backwards
-    end,
-  NewPS =
-    if LO =< Child, Child =< HI -> [SdiNr | PS];
-       true -> PS
-    end,
-  parentsOfChild(SdiNr-1, SDIS, Child, NewPS).
+-spec deleteParent(parents(), non_neg_integer()) -> parents().
+deleteParent({PrevSDIS, SegTree0}, Parent) ->
+  {LO,HI} = parents_generate_range(Parent, PrevSDIS),
+  SegTree = hipe_segment_trees:delete(Parent, LO, HI, SegTree0),
+  {PrevSDIS, SegTree}.
 
 -spec updateParents([non_neg_integer()], non_neg_integer(),
 		    byte(), tuple(), hipe_array(),
@@ -297,10 +310,12 @@ updateWKL(SdiNr, SDIS, SdiSpan, WKL) ->
     false -> [SdiNr|WKL]
   end.
 
+-compile({inline, sdiSpanIsShort/2}). %% Only called once
 -spec sdiSpanIsShort(#sdi_data{}, integer()) -> boolean().
 sdiSpanIsShort(#sdi_data{si = #sdi_info{lb = LB, ub = UB}}, SdiSpan) ->
   SdiSpan >= LB andalso SdiSpan =< UB.
 
+-compile({inline, sdiLongIncr/1}). %% Only called once
 -spec sdiLongIncr(#sdi_data{}) -> byte().
 sdiLongIncr(#sdi_data{si = #sdi_info{incr = Incr}}) -> Incr.
 
@@ -361,9 +376,11 @@ applyIncr([{Label,LabelData}|List], INCREMENT, LabelMap) ->
 %%% Currently implemented as tuples.
 %%% Used for the 'SDIS' and 'PARENTS' vectors.
 
--spec vector_from_list([#sdi_data{}]) -> tuple().
+-spec vector_from_list([E]) -> hipe_vector(E).
 vector_from_list(Values) -> list_to_tuple(Values).
 
+-compile({inline, vector_sub/2}).
+-spec vector_sub(hipe_vector(E), non_neg_integer()) -> V when V :: E.
 vector_sub(Vec, I) -> element(I+1, Vec).
 
 %%% ADT for mutable integer arrays, indexed from 0 to N-1.
@@ -373,8 +390,10 @@ vector_sub(Vec, I) -> element(I+1, Vec).
 -spec mk_array_of_zeros(non_neg_integer()) -> hipe_array().
 mk_array_of_zeros(N) -> hipe_bifs:array(N, 0).
 
+-compile({inline, array_update/3}).
 -spec array_update(hipe_array(), non_neg_integer(), integer()) -> hipe_array().
 array_update(A, I, V) -> hipe_bifs:array_update(A, I, V).
 
+-compile({inline, array_sub/2}).
 -spec array_sub(hipe_array(), non_neg_integer()) -> integer().
 array_sub(A, I) -> hipe_bifs:array_sub(A, I).
diff --git a/lib/hipe/misc/hipe_segment_trees.erl b/lib/hipe/misc/hipe_segment_trees.erl
new file mode 100644
index 0000000000..22146396c3
--- /dev/null
+++ b/lib/hipe/misc/hipe_segment_trees.erl
@@ -0,0 +1,181 @@
+%%%
+%%% %CopyrightBegin%
+%%%
+%%% Copyright Ericsson AB 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.
+%%% You may obtain a copy of the License at
+%%%
+%%%     http://www.apache.org/licenses/LICENSE-2.0
+%%%
+%%% Unless required by applicable law or agreed to in writing, software
+%%% distributed under the License is distributed on an "AS IS" BASIS,
+%%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%%% See the License for the specific language governing permissions and
+%%% limitations under the License.
+%%%
+%%% %CopyrightEnd%
+%%%
+%%% Segment trees, with a delete operation.
+%%%
+%%% Keys are the (0-based) indices into the list passed to build/1.
+%%%
+%%% Range bounds are inclusive.
+%%%
+
+-module(hipe_segment_trees).
+
+-export([build/1, intersect/2, delete/4]).
+
+-record(segment_tree, {
+	  lo            :: integer(),
+	  hi            :: integer(),
+	  root          :: tnode()
+	 }).
+
+%% X =< Mid belongs in Left
+-define(NODE(Left, Right, Mid, Segments), {Left, Right, Mid, Segments}).
+
+-define(POINT_LEAF(Val), Val).
+-define(RANGE_LEAF(Lo, Hi), {Lo, Hi}).
+
+-type segments() :: [non_neg_integer()].
+-type leaf()     :: segments().
+-type tnode()    :: ?NODE(tnode(), tnode(), integer(), segments()) | leaf().
+
+-opaque tree() :: #segment_tree{} | nil.
+-export_type([tree/0]).
+
+%% @doc Builds a segment tree of the given intervals.
+-spec build([{integer(), integer()}]) -> tree().
+build(ListOfIntervals) ->
+    case
+	lists:usort(
+	  lists:append(
+	    [[Lo, Hi] || {Lo, Hi} <- ListOfIntervals, Lo =< Hi]))
+    of
+	[] -> nil;
+	Endpoints ->
+	    Tree0 = empty_tree_from_endpoints(Endpoints),
+	    [Lo|_] = Endpoints,
+	    Hi = lists:last(Endpoints),
+	    Tree1 = insert_intervals(0, ListOfIntervals, Lo, Hi, Tree0),
+	    Tree = squash_empty_subtrees(Tree1),
+	    #segment_tree{lo=Lo, hi=Hi, root=Tree}
+    end.
+
+empty_tree_from_endpoints(Endpoints) ->
+    Leaves = leaves(Endpoints),
+    {T, [], _, _} = balanced_bst(Leaves, length(Leaves)),
+    T.
+
+leaves([Endpoint]) -> [?POINT_LEAF(Endpoint)];
+leaves([A | [B|_] = Tail]) ->
+    %% We omit the range leaf if it's empty
+    case A<B-1 of
+	true  -> [?POINT_LEAF(A),?RANGE_LEAF(A+1,B-1) | leaves(Tail)];
+	false -> [?POINT_LEAF(A) | leaves(Tail)]
+    end.
+
+balanced_bst(L, S) when S > 1 ->
+    Sm = S, %% - 1
+    S2 = Sm div 2,
+    S1 = Sm - S2,
+    {Left, L1, LeftLo, LeftHi} = balanced_bst(L, S1),
+    {Right, L2, _, RightHi} = balanced_bst(L1, S2),
+    T = ?NODE(Left, Right, LeftHi, []),
+    {T, L2, LeftLo, RightHi};
+balanced_bst([?RANGE_LEAF(Lo, Hi) | L], 1) ->
+    {[], L, Lo, Hi};
+balanced_bst([?POINT_LEAF(Val) | L], 1) ->
+    {[], L, Val, Val}.
+
+insert_intervals(_Ix, [], _Lo, _Hi, Tree) -> Tree;
+insert_intervals(Ix, [Int|Ints], Lo, Hi, Tree) ->
+    insert_intervals(Ix + 1, Ints, Lo, Hi,
+		     insert_interval(Ix, Int, Lo, Hi, Tree)).
+
+insert_interval(_, {Lo, Hi}, _, _, Node) when Lo > Hi -> Node;
+insert_interval(I, Int={Lo,Hi}, NLo, NHi,
+		?NODE(Left0, Right0, Mid, Segments)) ->
+    if Lo =< NLo, NHi =< Hi ->
+	    ?NODE(Left0, Right0, Mid, [I|Segments]);
+       true ->
+	    Left = case intervals_intersect(Lo, Hi,    NLo, Mid) of
+		       true -> insert_interval(I, Int, NLo, Mid, Left0);
+		       false -> Left0
+		   end,
+	    Right = case intervals_intersect(Lo, Hi,    Mid+1, NHi) of
+			true -> insert_interval(I, Int, Mid+1, NHi, Right0);
+			false -> Right0
+		   end,
+	    ?NODE(Left, Right, Mid, Segments)
+    end;
+insert_interval(I, {_Lo,_Hi}, _NLo, _NHi, Leaf) -> [I|Leaf].
+
+intervals_intersect(ALo, AHi, BLo, BHi) ->
+    (ALo =< AHi) andalso (BLo =< BHi) %% both nonempty
+	andalso nonempty_intervals_intersect(ALo, AHi, BLo, BHi).
+
+%% Purely optional optimisation
+squash_empty_subtrees(?NODE(Left0, Right0, Mid, Segs)) ->
+    build_squash_node(squash_empty_subtrees(Left0),
+		      squash_empty_subtrees(Right0),
+		      Mid, Segs);
+squash_empty_subtrees(Leaf) -> Leaf.
+
+build_squash_node([], [], _, Segs) -> Segs;
+build_squash_node(Left, Right, Mid, Segs) ->
+    ?NODE(Left, Right, Mid, Segs).
+
+%% @doc Returns the indices of the intervals in the tree that contains Point.
+-spec intersect(integer(), tree()) -> [non_neg_integer()].
+intersect(Point, nil) when is_integer(Point) -> [];
+intersect(Point, #segment_tree{lo=Lo, hi=Hi, root=Root})
+  when is_integer(Point) ->
+    case Lo =< Point andalso Point =< Hi of
+	false -> [];
+	true -> intersect_1(Point, Root, [])
+    end.
+
+intersect_1(Point, ?NODE(Left, Right, Mid, Segs), Acc0) ->
+    Child = if Point =< Mid -> Left; true -> Right end,
+    intersect_1(Point, Child, Segs ++ Acc0);
+intersect_1(_, LeafSegs, Acc) -> LeafSegs ++ Acc.
+
+%% @doc Deletes the interval {Lo, Hi}, which had index Index in the list passed
+%%      to build/1.
+-spec delete(non_neg_integer(), integer(), integer(), tree()) -> tree().
+delete(_, _, _, nil) -> nil;
+delete(_, Lo, Hi, Tree) when Lo > Hi -> Tree;
+delete(_, Lo, Hi, Tree = #segment_tree{lo=TLo, hi=THi})
+  when Hi < TLo; Lo > THi -> Tree;
+delete(Index, Lo, Hi, Tree = #segment_tree{lo=TLo, hi=THi, root=Root0})
+  when is_integer(Lo), is_integer(Hi) ->
+    Root = delete_1(Index, Lo, Hi, TLo, THi, Root0),
+    Tree#segment_tree{root=Root}.
+
+delete_1(I, Lo, Hi, NLo, NHi, ?NODE(Left0, Right0, Mid, Segments)) ->
+    if Lo =< NLo, NHi =< Hi ->
+	    ?NODE(Left0, Right0, Mid, delete_2(Segments, I));
+       true ->
+	    Left = case nonempty_intervals_intersect(Lo, Hi, NLo, Mid) of
+		       true -> delete_1(I, Lo, Hi, NLo, Mid, Left0);
+		       false -> Left0
+		   end,
+	    Right = case nonempty_intervals_intersect(Lo, Hi, Mid+1, NHi) of
+			true -> delete_1(I, Lo, Hi, Mid+1, NHi, Right0);
+			false -> Right0
+		   end,
+	    %% We could do build_squash_node here, is it worth it?
+	    ?NODE(Left, Right, Mid, Segments)
+    end;
+delete_1(I, _Lo, _Hi, _NLo, _NHi, Leaf) -> delete_2(Leaf, I).
+
+delete_2([I|Segs], I) -> Segs;
+delete_2([S|Segs], I) -> [S|delete_2(Segs,I)].
+
+-compile({inline,nonempty_intervals_intersect/4}).
+nonempty_intervals_intersect(ALo, AHi, BLo, BHi) ->
+    (BLo =< AHi) andalso (ALo =< BHi).
diff --git a/lib/hipe/regalloc/Makefile b/lib/hipe/regalloc/Makefile
index aaa4418f37..ceb535f1c7 100644
--- a/lib/hipe/regalloc/Makefile
+++ b/lib/hipe/regalloc/Makefile
@@ -123,7 +123,6 @@ $(EBIN)/hipe_amd64_specific_x87.beam: hipe_x86_specific_x87.erl
 $(EBIN)/hipe_coalescing_regalloc.beam: ../main/hipe.hrl
 $(EBIN)/hipe_graph_coloring_regalloc.beam: ../main/hipe.hrl
 $(EBIN)/hipe_ig.beam: ../main/hipe.hrl ../flow/cfg.hrl hipe_spillcost.hrl
-$(EBIN)/hipe_ig_moves.beam: ../util/hipe_vectors.hrl
 $(EBIN)/hipe_ls_regalloc.beam: ../main/hipe.hrl
 $(EBIN)/hipe_optimistic_regalloc.beam: ../main/hipe.hrl
 $(EBIN)/hipe_regalloc_loop.beam: ../main/hipe.hrl
diff --git a/lib/hipe/regalloc/hipe_ig_moves.erl b/lib/hipe/regalloc/hipe_ig_moves.erl
index b679453de0..2a70606dab 100644
--- a/lib/hipe/regalloc/hipe_ig_moves.erl
+++ b/lib/hipe/regalloc/hipe_ig_moves.erl
@@ -25,8 +25,6 @@
 	 new_move/3,
 	 get_moves/1]).
 
--include("../util/hipe_vectors.hrl").
-
 %%-----------------------------------------------------------------------------
 %% The main data structure; its fields are:
 %%  - movelist  : mapping from temp to set of associated move numbers
@@ -34,11 +32,13 @@
 %%  - moveinsns : list of move instructions, in descending move number order
 %%  - moveset   : set of move instructions
 
--record(ig_moves, {movelist                    :: hipe_vector(),	
+-record(ig_moves, {movelist                    :: movelist(),
 		   nrmoves   = 0               :: non_neg_integer(),
 		   moveinsns = []              :: [{_,_}],
 		   moveset   = gb_sets:empty() :: gb_sets:set()}).
 
+-type movelist() :: hipe_vectors:vector(ordsets:ordset(non_neg_integer())).
+
 %%-----------------------------------------------------------------------------
 
 -spec new(non_neg_integer()) -> #ig_moves{}.
@@ -66,7 +66,8 @@ new_move(Dst, Src, IG_moves) ->
 			moveset = gb_sets:insert(MoveInsn, MoveSet)}
   end.
 
--spec add_movelist(non_neg_integer(), non_neg_integer(), hipe_vector()) -> hipe_vector().
+-spec add_movelist(non_neg_integer(), non_neg_integer(), movelist())
+		  -> movelist().
 
 add_movelist(MoveNr, Temp, MoveList) ->
   AssocMoves = hipe_vectors:get(MoveList, Temp),
@@ -74,7 +75,7 @@ add_movelist(MoveNr, Temp, MoveList) ->
   %% ordset due to the ordsets:union in hipe_coalescing_regalloc:combine().
   hipe_vectors:set(MoveList, Temp, ordsets:add_element(MoveNr, AssocMoves)).
 
--spec get_moves(#ig_moves{}) -> {hipe_vector(), non_neg_integer(), tuple()}.
+-spec get_moves(#ig_moves{}) -> {movelist(), non_neg_integer(), tuple()}.
 
 get_moves(IG_moves) -> % -> {MoveList, NrMoves, MoveInsns}
   {IG_moves#ig_moves.movelist,
diff --git a/lib/hipe/ssa/hipe_ssa_liveness.inc b/lib/hipe/ssa/hipe_ssa_liveness.inc
index 78488c65fc..46df8b66ad 100644
--- a/lib/hipe/ssa/hipe_ssa_liveness.inc
+++ b/lib/hipe/ssa/hipe_ssa_liveness.inc
@@ -40,6 +40,15 @@
 	 ssa_liveness__livein/2]).
 %%	 ssa_liveness__livein/3],
 %%	 ssa_liveness__liveout/2]).
+-type set(E) :: gb_sets:set(E).
+-type liveness(Label, Var) ::
+	#{Label => {{Gen          :: set(Var),
+		     Kill         :: set(Var),
+		     {TotalDirGen :: set(Var),
+		      DirGen      :: gb_trees:tree(Label, set(Var))}},
+		    LiveIn        :: set(Var),
+		    LiveOut       :: set(Var),
+		    Successors    :: [Label]}}.
 -endif.
 %% -ifdef(DEBUG_LIVENESS).
 %% -export([pp_liveness/1]).
@@ -262,21 +271,15 @@ update_directed_gen({Pred, Var}, Map)->
 %%
 %% liveness
 %%
+-compile({inline, [liveness_lookup/2, liveness_update/3]}).
 
 liveness_init(List) ->
-  liveness_init1(List, gb_trees:empty()).
+  maps:from_list(List).
 
-liveness_init1([{Label, Info}|Left], Map) ->
-  liveness_init1(Left, gb_trees:insert(Label, Info, Map));
-liveness_init1([], Map) ->
-  Map.
-
-liveness_lookup(Label, Map) ->
-  {value, Info} = gb_trees:lookup(Label, Map),
-  Info.
-
-liveness_update(Label, NewInfo, Map) ->
-  gb_trees:update(Label, NewInfo, Map).
+liveness_lookup(Label, Liveness) ->
+  maps:get(Label, Liveness).
+liveness_update(Label, Val, Liveness) ->
+  maps:update(Label, Val, Liveness).
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
diff --git a/lib/hipe/util/Makefile b/lib/hipe/util/Makefile
index 66e9421c25..04de7f7823 100644
--- a/lib/hipe/util/Makefile
+++ b/lib/hipe/util/Makefile
@@ -113,4 +113,3 @@ release_docs_spec:
 
 
 $(EBIN)/hipe_timing.beam: ../main/hipe.hrl
-$(EBIN)/hipe_vectors.beam: hipe_vectors.hrl
diff --git a/lib/hipe/util/hipe_vectors.erl b/lib/hipe/util/hipe_vectors.erl
index 7f6c8e91c2..90d736d02c 100644
--- a/lib/hipe/util/hipe_vectors.erl
+++ b/lib/hipe/util/hipe_vectors.erl
@@ -33,11 +33,25 @@
 	 %% list_to_vector/1,
 	 list/1]).
 
--include("hipe_vectors.hrl").
+%%-define(USE_TUPLES, true).
+%%-define(USE_GBTREES, true).
+-define(USE_ARRAYS, true).
+
+-type vector() :: vector(_).
+-export_type([vector/0, vector/1]).
+
+-spec new(non_neg_integer(), V) -> vector(E) when V :: E.
+-spec set(vector(E), non_neg_integer(), V :: E) -> vector(E).
+-spec get(vector(E), non_neg_integer()) -> E.
+-spec size(vector(_)) -> non_neg_integer().
+-spec vector_to_list(vector(E)) -> [E].
+%% -spec list_to_vector([E]) -> vector(E).
+-spec list(vector(E)) -> [{non_neg_integer(), E}].
 
 %% ---------------------------------------------------------------------
 
 -ifdef(USE_TUPLES).
+-opaque vector(_) :: tuple().
 
 new(N, V) ->
     erlang:make_tuple(N, V).
@@ -68,8 +82,8 @@ get(Vec, Ix) -> element(Ix+1, Vec).
 %% ---------------------------------------------------------------------
 
 -ifdef(USE_GBTREES).
+-opaque vector(E) :: gb_trees:tree(non_neg_integer(), E).
 
--spec new(non_neg_integer(), _) -> hipe_vector().
 new(N, V) when is_integer(N), N >= 0 ->
     gb_trees:from_orddict(mklist(N, V)).
 
@@ -81,14 +95,11 @@ mklist(M, N, V) when M < N ->
 mklist(_, _, _) ->
     [].
 
--spec size(hipe_vector()) -> non_neg_integer().
 size(V) -> gb_trees:size(V).
 
--spec list(hipe_vector()) -> [{_, _}].
 list(Vec) ->
     gb_trees:to_list(Vec).
 
-%% -spec list_to_vector([_]) -> hipe_vector().
 %% list_to_vector(Xs) ->
 %%     gb_trees:from_orddict(index(Xs, 0)).
 %% 
@@ -97,16 +108,29 @@ list(Vec) ->
 %% index([],_) ->
 %%     [].
 
--spec vector_to_list(hipe_vector()) -> [_].
 vector_to_list(V) ->
     gb_trees:values(V).
 
--spec set(hipe_vector(), non_neg_integer(), _) -> hipe_vector().
 set(Vec, Ix, V) ->
     gb_trees:update(Ix, V, Vec).
 
--spec get(hipe_vector(), non_neg_integer()) -> any().
 get(Vec, Ix) ->
     gb_trees:get(Ix, Vec).
 
 -endif. %% ifdef USE_GBTREES
+
+%% ---------------------------------------------------------------------
+
+-ifdef(USE_ARRAYS).
+%%-opaque vector(E) :: array:array(E).
+-type vector(E) :: array:array(E). % Work around dialyzer bug
+
+new(N, V) -> array:new(N, {default, V}).
+size(V) -> array:size(V).
+list(Vec) -> array:to_orddict(Vec).
+%% list_to_vector(Xs) -> array:from_list(Xs).
+vector_to_list(V) -> array:to_list(V).
+set(Vec, Ix, V) -> array:set(Ix, V, Vec).
+get(Vec, Ix) -> array:get(Ix, Vec).
+
+-endif. %% ifdef USE_ARRAYS
diff --git a/lib/hipe/util/hipe_vectors.hrl b/lib/hipe/util/hipe_vectors.hrl
deleted file mode 100644
index d4556e9dc4..0000000000
--- a/lib/hipe/util/hipe_vectors.hrl
+++ /dev/null
@@ -1,29 +0,0 @@
-%%
-%% %CopyrightBegin%
-%% 
-%% Copyright Ericsson AB 2008-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.
-%% You may obtain a copy of the License at
-%%
-%%     http://www.apache.org/licenses/LICENSE-2.0
-%%
-%% Unless required by applicable law or agreed to in writing, software
-%% distributed under the License is distributed on an "AS IS" BASIS,
-%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-%% See the License for the specific language governing permissions and
-%% limitations under the License.
-%% 
-%% %CopyrightEnd%
-%%
-%%-define(USE_TUPLES, true).
--define(USE_GBTREES, true).
-
--ifdef(USE_TUPLES).
--type hipe_vector() :: tuple().
--endif.
-
--ifdef(USE_GBTREES).
--type hipe_vector() :: gb_trees:tree().
--endif.
diff --git a/lib/hipe/x86/hipe_x86_frame.erl b/lib/hipe/x86/hipe_x86_frame.erl
index 8851ead250..4cdc04007d 100644
--- a/lib/hipe/x86/hipe_x86_frame.erl
+++ b/lib/hipe/x86/hipe_x86_frame.erl
@@ -622,26 +622,31 @@ find_temps([I|Insns], S0) ->
 find_temps([], S) ->
   S.
 
+-compile({inline, [tset_empty/0, tset_size/1, tset_insert/2,
+		   tset_filter/2, tset_to_list/1]}).
+
 tset_empty() ->
-  gb_sets:new().
+  #{}.
 
 tset_size(S) ->
-  gb_sets:size(S).
+  map_size(S).
 
 tset_insert(S, T) ->
-  gb_sets:add_element(T, S).
+  S#{T => []}.
 
-tset_add_list(S, Ts) ->
-  gb_sets:union(S, gb_sets:from_list(Ts)).
+tset_add_list(S, []) -> S;
+tset_add_list(S, [T|Ts]) ->
+  tset_add_list(S#{T => []}, Ts).
 
-tset_del_list(S, Ts) ->
-  gb_sets:subtract(S, gb_sets:from_list(Ts)).
+tset_del_list(S, []) -> S;
+tset_del_list(S, [T|Ts]) ->
+  tset_del_list(maps:remove(T,S), Ts).
 
 tset_filter(S, F) ->
-  gb_sets:filter(F, S).
+  maps:filter(fun(K, _V) -> F(K) end, S).
 
 tset_to_list(S) ->
-  gb_sets:to_list(S).
+  maps:keys(S).
 
 %%%
 %%% Compute minimum permissible frame size, ignoring spilled temps.