diff options
Diffstat (limited to 'lib/hipe/misc')
| -rw-r--r-- | lib/hipe/misc/Makefile | 2 | ||||
| -rw-r--r-- | lib/hipe/misc/hipe_sdi.erl | 103 | ||||
| -rw-r--r-- | lib/hipe/misc/hipe_segment_trees.erl | 181 |
3 files changed, 243 insertions, 43 deletions
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). |