From 1bdaee9393a3cf45d7a62fba815c2a73ab637781 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Fri, 18 Mar 2016 11:20:42 +0100
Subject: hipe_icode_{bincomp,range}: Improve complexity

hipe_icode_bincomp:find_bs_get_integer/3 was quadratic for no good reason. By observing
that NewSuccs and Rest are always disjoint, we can see that the worklist
does not need to be a set. Furthermore, by replacing the ordset Visited
with a map, we reduce complexity to (a very low) O(n lg n).

On cuter_binlib, this change reduced the time for hipe_icode_bincomp
from 60s to .25s. Using a gb_set for Visited gives .5s, and a sets:set
1s.

We apply the same optimisation to hipe_icode_range.
---
 lib/hipe/icode/hipe_icode_bincomp.erl | 28 ++++++++++++++++++++++------
 lib/hipe/icode/hipe_icode_range.erl   | 29 +++++++++++++++++++++++------
 2 files changed, 45 insertions(+), 12 deletions(-)

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_range.erl b/lib/hipe/icode/hipe_icode_range.erl
index 12ed796690..0cacdb8caf 100644
--- a/lib/hipe/icode/hipe_icode_range.erl
+++ b/lib/hipe/icode/hipe_icode_range.erl
@@ -187,17 +187,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.
@@ -1959,3 +1958,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).
-- 
cgit v1.2.3


From e74636ef2489d436b38726ae19bca2d8e7455cec Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Fri, 18 Mar 2016 11:42:31 +0100
Subject: hipe_sdi: Use segment trees to represent PARENTS

This speeds up parentsOfChild/2 from O(n) to O(lg n + k).

A new module misc/hipe_segment_trees.erl is introduced.
---
 lib/hipe/main/hipe.app.src           |   1 +
 lib/hipe/misc/Makefile               |   2 +-
 lib/hipe/misc/hipe_sdi.erl           |  60 +++++++-------
 lib/hipe/misc/hipe_segment_trees.erl | 150 +++++++++++++++++++++++++++++++++++
 4 files changed, 184 insertions(+), 29 deletions(-)
 create mode 100644 lib/hipe/misc/hipe_segment_trees.erl

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..38a798875c 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,19 @@ 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) ->
+  Ranges = parents_generate_ranges(N-1, SDIS, []),
+  hipe_segment_trees:build(Ranges).
+
+parents_generate_ranges(-1, _SDIS, Acc) -> Acc;
+parents_generate_ranges(SdiNr, SDIS, Acc) ->
+  #sdi_data{prevSdi=PrevSdi} = vector_sub(SDIS, SdiNr),
+  {LO,HI} =	% inclusive
+    if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi};	% forwards
+       true -> {PrevSdi+1, SdiNr-1}		% backwards
+    end,
+  parents_generate_ranges(SdiNr-1, SDIS, [{LO,HI}|Acc]).
 
 %%% "After the structure is built we process it as follows.
 %%% For any node i whose listed span exceeds the architectural
@@ -209,7 +226,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,14 +242,14 @@ 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(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()].
+		  parents(), hipe_array()) -> [non_neg_integer()].
 updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG) ->
   case array_sub(SPAN, Child) of
     0 -> WKL;						% removed
@@ -245,26 +262,9 @@ updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG) ->
       updateParents(PS, Child, Incr, SDIS, SPAN, WKL)
   end.
 
--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 parentsOfChild(parents(), non_neg_integer()) -> [non_neg_integer()].
+parentsOfChild(IntervalTree, Child) ->
+  hipe_segment_trees:intersect(Child, IntervalTree).
 
 -spec updateParents([non_neg_integer()], non_neg_integer(),
 		    byte(), tuple(), hipe_array(),
@@ -361,9 +361,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 +375,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..cbee328125
--- /dev/null
+++ b/lib/hipe/misc/hipe_segment_trees.erl
@@ -0,0 +1,150 @@
+%%%
+%%% %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.
+%%%
+%%% Keys are the (0-based) indices into the list passed to build/1.
+%%%
+%%% Range bounds are inclusive.
+%%%
+%%% TODO: Change the shape of the tree to a perfect binary tree, and pack it as
+%%% an implicit data structure into tuples (like a binary heap would be) for
+%%% improved efficiency.
+
+-module(hipe_segment_trees).
+
+-export([build/1, intersect/2]).
+
+-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 could omit the range leaf if it's empty, but we want to pack this data
+    %% structure into an array (tuple) eventually, and then we *really* want
+    %% every other leaf to be a range
+    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 (BLo =< AHi) andalso (ALo =< 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.
-- 
cgit v1.2.3


From ad73c37d4af90834c62f961264dce00118309b0f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Fri, 18 Mar 2016 14:04:36 +0100
Subject: hipe: segment tree delete operation

Profiling showed that hipe_sdi spent most of its time in updateParents,
discarding nodes that were already deleted. By introducing a delete
operation to the segment trees, we can pay this cost only once, when
deleting the node from the graph.

Instead of keeping the ranges around, we recompute the range of the node
when we delete it, since this can be done in constant time, without any
memory allocation.

Although segment trees are not designed to be modified once built,
implementing a delete operation turned out to be a simple matter of
repeating insertion, but deleting the index from, instead of consing it
on, the appropriate nodes' values (segment lists).

This optimisation drastically sped up hipe_sdi to the point of no longer
being the bottleneck in the Assembly stage.
---
 lib/hipe/misc/hipe_sdi.erl           | 69 ++++++++++++++++++++++--------------
 lib/hipe/misc/hipe_segment_trees.erl | 49 ++++++++++++++++++++-----
 2 files changed, 82 insertions(+), 36 deletions(-)

diff --git a/lib/hipe/misc/hipe_sdi.erl b/lib/hipe/misc/hipe_sdi.erl
index 38a798875c..5ca64bc669 100644
--- a/lib/hipe/misc/hipe_sdi.erl
+++ b/lib/hipe/misc/hipe_sdi.erl
@@ -195,17 +195,27 @@ initSPAN(SdiNr, N, SDIS, SPAN) ->
 
 -spec mk_parents(non_neg_integer(), tuple()) -> parents().
 mk_parents(N, SDIS) ->
-  Ranges = parents_generate_ranges(N-1, SDIS, []),
-  hipe_segment_trees:build(Ranges).
+  PrevSDIS = vector_from_list(select_prev_sdis(N-1, SDIS, [])),
+  Ranges = parents_generate_ranges(N-1, PrevSDIS, []),
+  {PrevSDIS, hipe_segment_trees:build(Ranges)}.
 
-parents_generate_ranges(-1, _SDIS, Acc) -> Acc;
-parents_generate_ranges(SdiNr, SDIS, Acc) ->
+select_prev_sdis(-1, _SDIS, Acc) -> Acc;
+select_prev_sdis(SdiNr, SDIS, Acc) ->
   #sdi_data{prevSdi=PrevSdi} = vector_sub(SDIS, SdiNr),
-  {LO,HI} =	% inclusive
-    if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi};	% forwards
-       true -> {PrevSdi+1, SdiNr-1}		% backwards
-    end,
-  parents_generate_ranges(SdiNr-1, SDIS, [{LO,HI}|Acc]).
+  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
@@ -244,27 +254,30 @@ initWKL(SdiNr, SDIS, SPAN, WKL) ->
 -spec processWKL([non_neg_integer()], tuple(), hipe_array(),
 		 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(),
-		  parents(), 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(IntervalTree, Child) ->
-  hipe_segment_trees:intersect(Child, IntervalTree).
+parentsOfChild({_PrevSDIS, SegTree}, Child) ->
+  hipe_segment_trees:intersect(Child, SegTree).
+
+-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.
 
diff --git a/lib/hipe/misc/hipe_segment_trees.erl b/lib/hipe/misc/hipe_segment_trees.erl
index cbee328125..22146396c3 100644
--- a/lib/hipe/misc/hipe_segment_trees.erl
+++ b/lib/hipe/misc/hipe_segment_trees.erl
@@ -17,19 +17,16 @@
 %%%
 %%% %CopyrightEnd%
 %%%
-%%% Segment trees.
+%%% Segment trees, with a delete operation.
 %%%
 %%% Keys are the (0-based) indices into the list passed to build/1.
 %%%
 %%% Range bounds are inclusive.
 %%%
-%%% TODO: Change the shape of the tree to a perfect binary tree, and pack it as
-%%% an implicit data structure into tuples (like a binary heap would be) for
-%%% improved efficiency.
 
 -module(hipe_segment_trees).
 
--export([build/1, intersect/2]).
+-export([build/1, intersect/2, delete/4]).
 
 -record(segment_tree, {
 	  lo            :: integer(),
@@ -75,9 +72,7 @@ empty_tree_from_endpoints(Endpoints) ->
 
 leaves([Endpoint]) -> [?POINT_LEAF(Endpoint)];
 leaves([A | [B|_] = Tail]) ->
-    %% We could omit the range leaf if it's empty, but we want to pack this data
-    %% structure into an array (tuple) eventually, and then we *really* want
-    %% every other leaf to be a range
+    %% 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)]
@@ -121,7 +116,7 @@ insert_interval(I, {_Lo,_Hi}, _NLo, _NHi, Leaf) -> [I|Leaf].
 
 intervals_intersect(ALo, AHi, BLo, BHi) ->
     (ALo =< AHi) andalso (BLo =< BHi) %% both nonempty
-	andalso (BLo =< AHi) andalso (ALo =< BHi).
+	andalso nonempty_intervals_intersect(ALo, AHi, BLo, BHi).
 
 %% Purely optional optimisation
 squash_empty_subtrees(?NODE(Left0, Right0, Mid, Segs)) ->
@@ -148,3 +143,39 @@ 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).
-- 
cgit v1.2.3


From 89a6d16fa71870bf496bbe477a3f2c7854396e07 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Fri, 18 Mar 2016 12:12:58 +0100
Subject: hipe_icode_coordinator: Rewrite concurrently

---
 lib/hipe/icode/hipe_icode_coordinator.erl | 29 +++++++++++++++++++++++------
 1 file changed, 23 insertions(+), 6 deletions(-)

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
-- 
cgit v1.2.3


From fe4f60994fc0a1329629d8c56a784ccd2f414f57 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Fri, 18 Mar 2016 13:00:44 +0100
Subject: hipe_icode_range: Use maps over gb_trees,sets

Also, remove unused field 'counter' from #state{}.
---
 lib/hipe/icode/hipe_icode_range.erl | 102 +++++++++++++++++-------------------
 1 file changed, 49 insertions(+), 53 deletions(-)

diff --git a/lib/hipe/icode/hipe_icode_range.erl b/lib/hipe/icode/hipe_icode_range.erl
index 0cacdb8caf..7fea1c3d7c 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,9 +82,8 @@
 -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(), 
+-record(state, {info_map = #{}			:: info(),
+		cfg				:: cfg(),
 		liveness = gb_trees:empty()	:: gb_trees:tree(),
 		ret_type			:: range(),
 		lookup_fun			:: call_fun(),
@@ -1660,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}
@@ -1699,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).
@@ -1720,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}.
@@ -1785,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;
@@ -1794,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;
@@ -1809,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()
@@ -1827,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;
@@ -1838,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.
-- 
cgit v1.2.3


From ebc557f315c99c8e1e0563ae6111c06c7cb271dc Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Sat, 12 Mar 2016 12:24:46 +0100
Subject: hipe_x86_frame: speed up find_temps

---
 lib/hipe/x86/hipe_x86_frame.erl | 23 ++++++++++++++---------
 1 file changed, 14 insertions(+), 9 deletions(-)

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.
-- 
cgit v1.2.3


From ab4062063727d713a8eca8cf09b8a0f50744bc9b Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Sat, 12 Mar 2016 13:01:27 +0100
Subject: hipe/flow/liveness.inc: Use map for liveness type

Slightly improves performance.
---
 lib/hipe/flow/liveness.inc | 22 ++++++++++++----------
 1 file changed, 12 insertions(+), 10 deletions(-)

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).
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-- 
cgit v1.2.3


From 3f1fe056ba8673920a536093b23117f7d287cba7 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Thu, 17 Mar 2016 21:53:19 +0100
Subject: hipe_ssa_liveness: Use map as liveness ADT

---
 lib/hipe/icode/hipe_icode_range.erl |  2 +-
 lib/hipe/icode/hipe_icode_ssa.erl   |  9 ++++++---
 lib/hipe/icode/hipe_icode_type.erl  |  2 +-
 lib/hipe/ssa/hipe_ssa_liveness.inc  | 27 +++++++++++++++------------
 4 files changed, 23 insertions(+), 17 deletions(-)

diff --git a/lib/hipe/icode/hipe_icode_range.erl b/lib/hipe/icode/hipe_icode_range.erl
index 7fea1c3d7c..af160769a1 100644
--- a/lib/hipe/icode/hipe_icode_range.erl
+++ b/lib/hipe/icode/hipe_icode_range.erl
@@ -84,7 +84,7 @@
 
 -record(state, {info_map = #{}			:: info(),
 		cfg				:: cfg(),
-		liveness = gb_trees:empty()	:: gb_trees:tree(),
+		liveness			:: hipe_icode_ssa:liveness(),
 		ret_type			:: range(),
 		lookup_fun			:: call_fun(),
 		result_action			:: final_fun()}).
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/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).
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-- 
cgit v1.2.3


From 4e2d74858fbcd7b62b6538722d5bed0887897c40 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Thu, 17 Mar 2016 23:47:08 +0100
Subject: hipe: Faster unreachable basic block removal

---
 lib/hipe/flow/cfg.inc | 78 ++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 53 insertions(+), 25 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)
-- 
cgit v1.2.3


From fd97ddb2c3031140f12c98c93a31325b15ea8cb6 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Fri, 18 Mar 2016 16:31:34 +0100
Subject: hipe_vectors: Change implementation to 'array'

The 'array' module is highly optimised for the hipe_vectors use-case,
and seems to perform slightly better than the gb_trees implementation.

Also, we remove the completely unnecessary hipe_vectors.hrl header.
---
 lib/hipe/regalloc/Makefile          |  1 -
 lib/hipe/regalloc/hipe_ig_moves.erl | 11 +++++-----
 lib/hipe/util/Makefile              |  1 -
 lib/hipe/util/hipe_vectors.erl      | 40 +++++++++++++++++++++++++++++--------
 lib/hipe/util/hipe_vectors.hrl      | 29 ---------------------------
 5 files changed, 38 insertions(+), 44 deletions(-)
 delete mode 100644 lib/hipe/util/hipe_vectors.hrl

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/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.
-- 
cgit v1.2.3