From f9263b9173905d4e7a53350d4f374c5020c52738 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Magnus=20L=C3=A5ng?= Date: Thu, 16 Mar 2017 15:50:09 +0100 Subject: hipe: Extract disjoint sets to its own module --- lib/hipe/main/hipe.app.src | 1 + lib/hipe/regalloc/hipe_regalloc_prepass.erl | 71 +++++------------------- lib/hipe/util/Makefile | 2 +- lib/hipe/util/hipe_dsets.erl | 84 +++++++++++++++++++++++++++++ 4 files changed, 98 insertions(+), 60 deletions(-) create mode 100644 lib/hipe/util/hipe_dsets.erl (limited to 'lib/hipe') diff --git a/lib/hipe/main/hipe.app.src b/lib/hipe/main/hipe.app.src index af2c02006d..4c3f147d40 100644 --- a/lib/hipe/main/hipe.app.src +++ b/lib/hipe/main/hipe.app.src @@ -83,6 +83,7 @@ hipe_digraph, hipe_dominators, hipe_dot, + hipe_dsets, hipe_gen_cfg, hipe_gensym, hipe_graph_coloring_regalloc, diff --git a/lib/hipe/regalloc/hipe_regalloc_prepass.erl b/lib/hipe/regalloc/hipe_regalloc_prepass.erl index e212420ad2..5024840237 100644 --- a/lib/hipe/regalloc/hipe_regalloc_prepass.erl +++ b/lib/hipe/regalloc/hipe_regalloc_prepass.erl @@ -483,8 +483,8 @@ merge_pointless_splits_1([], _ScanBBs, DSets, Acc) -> {Acc, DSets}; merge_pointless_splits_1([P={_,{single,_}}|Ps], ScanBBs, DSets, Acc) -> merge_pointless_splits_1(Ps, ScanBBs, DSets, [P|Acc]); merge_pointless_splits_1([P0={L,{split,_,_}}|Ps], ScanBBs, DSets0, Acc) -> - {EntryRoot, DSets1} = dsets_find({entry,L}, DSets0), - {ExitRoot, DSets} = dsets_find({exit,L}, DSets1), + {EntryRoot, DSets1} = hipe_dsets:find({entry,L}, DSets0), + {ExitRoot, DSets} = hipe_dsets:find({exit,L}, DSets1), case EntryRoot =:= ExitRoot of false -> merge_pointless_splits_1(Ps, ScanBBs, DSets, [P0|Acc]); true -> @@ -501,7 +501,7 @@ merge_pointless_splits_1([P0={L,{split,_,_}}|Ps], ScanBBs, DSets0, Acc) -> -spec merge_small_parts(bb_dsets()) -> {bb_dsets_rllist(), bb_dsets()}. merge_small_parts(DSets0) -> - {RLList, DSets1} = dsets_to_rllist(DSets0), + {RLList, DSets1} = hipe_dsets:to_rllist(DSets0), RLLList = [{R, length(Elems), Elems} || {R, Elems} <- RLList], merge_small_parts_1(RLLList, DSets1, []). @@ -518,8 +518,8 @@ merge_small_parts_1([Fst,{R, L, Es}|Ps], DSets, Acc) merge_small_parts_1([Fst|Ps], DSets, [{R,Es}|Acc]); merge_small_parts_1([{R1,L1,Es1},{R2,L2,Es2}|Ps], DSets0, Acc) -> ?ASSERT(L1 < ?TUNE_TOO_FEW_BBS andalso L2 < ?TUNE_TOO_FEW_BBS), - DSets1 = dsets_union(R1, R2, DSets0), - {R, DSets} = dsets_find(R1, DSets1), + DSets1 = hipe_dsets:union(R1, R2, DSets0), + {R, DSets} = hipe_dsets:find(R1, DSets1), merge_small_parts_1([{R,L2+L1,Es2++Es1}|Ps], DSets, Acc). %% @doc Partition an ordering over BBs into subsequences for the dsets that @@ -531,8 +531,8 @@ part_order(Lbs, DSets) -> part_order(Lbs, DSets, #{}). part_order([], DSets, Acc) -> {Acc, DSets}; part_order([L|Ls], DSets0, Acc0) -> - {EntryRoot, DSets1} = dsets_find({entry,L}, DSets0), - {ExitRoot, DSets2} = dsets_find({exit,L}, DSets1), + {EntryRoot, DSets1} = hipe_dsets:find({entry,L}, DSets0), + {ExitRoot, DSets2} = hipe_dsets:find({exit,L}, DSets1), Acc1 = map_append(EntryRoot, L, Acc0), %% Only include the label once if both entry and exit is in same partition Acc2 = case EntryRoot =:= ExitRoot of @@ -558,72 +558,25 @@ map_append(Key, Elem, Map) -> %% split point, and one from the end to the last split point. -type bb_dset_key() :: {entry | exit, label()}. --type bb_dsets() :: dsets(bb_dset_key()). +-type bb_dsets() :: hipe_dsets:dsets(bb_dset_key()). -type bb_dsets_rllist() :: [{bb_dset_key(), [bb_dset_key()]}]. -spec initial_dsets(target_cfg(), module(), target_context()) -> bb_dsets(). initial_dsets(CFG, TgtMod, TgtCtx) -> Labels = TgtMod:labels(CFG, TgtCtx), - DSets0 = dsets_new(lists:append([[{entry,L},{exit,L}] || L <- Labels])), + DSets0 = hipe_dsets:new(lists:append([[{entry,L},{exit,L}] || L <- Labels])), Edges = lists:append([[{L, S} || S <- hipe_gen_cfg:succ(CFG, L)] || L <- Labels]), - lists:foldl(fun({X, Y}, DS) -> dsets_union({exit,X}, {entry,Y}, DS) end, + lists:foldl(fun({X, Y}, DS) -> hipe_dsets:union({exit,X}, {entry,Y}, DS) end, DSets0, Edges). -spec join_whole_blocks(part_bb_list(), bb_dsets()) -> bb_dsets(). join_whole_blocks(PartBBList, DSets0) -> - lists:foldl(fun({L, {single, _}}, DS) -> dsets_union({entry,L}, {exit,L}, DS); + lists:foldl(fun({L, {single, _}}, DS) -> + hipe_dsets:union({entry,L}, {exit,L}, DS); ({_, {split, _, _}}, DS) -> DS end, DSets0, PartBBList). -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% The disjoint set forests data structure, for elements of arbitrary types. -%% Note that the find operation mutates the set. -%% -%% We could do this more efficiently if we restricted the elements to integers, -%% and used the (mutable) hipe arrays. For arbitrary terms ETS could be used, -%% for a persistent interface (which isn't that nice when even accessors return -%% modified copies), the array module could be used. --type dsets(X) :: #{X => {node, X} | {root, non_neg_integer()}}. - --spec dsets_new([E]) -> dsets(E). -dsets_new(Elems) -> maps:from_list([{E,{root,0}} || E <- Elems]). - --spec dsets_find(E, dsets(E)) -> {E, dsets(E)}. -dsets_find(E, DS0) -> - case DS0 of - #{E := {root,_}} -> {E, DS0}; - #{E := {node,N}} -> - case dsets_find(N, DS0) of - {N, _}=T -> T; - {R, DS1} -> {R, DS1#{E := {node,R}}} - end - ;_ -> error(badarg, [E, DS0]) - end. - --spec dsets_union(E, E, dsets(E)) -> dsets(E). -dsets_union(X, Y, DS0) -> - {XRoot, DS1} = dsets_find(X, DS0), - case dsets_find(Y, DS1) of - {XRoot, DS2} -> DS2; - {YRoot, DS2} -> - #{XRoot := {root,XRR}, YRoot := {root,YRR}} = DS2, - if XRR < YRR -> DS2#{XRoot := {node,YRoot}}; - XRR > YRR -> DS2#{YRoot := {node,XRoot}}; - true -> DS2#{YRoot := {node,XRoot}, XRoot := {root,XRR+1}} - end - end. - --spec dsets_to_rllist(dsets(E)) -> {[{Root::E, Elems::[E]}], dsets(E)}. -dsets_to_rllist(DS0) -> - {Lists, DS} = dsets_to_rllist(maps:keys(DS0), #{}, DS0), - {maps:to_list(Lists), DS}. - -dsets_to_rllist([], Acc, DS) -> {Acc, DS}; -dsets_to_rllist([E|Es], Acc, DS0) -> - {ERoot, DS} = dsets_find(E, DS0), - dsets_to_rllist(Es, map_append(ERoot, E, Acc), DS). - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Third pass %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% diff --git a/lib/hipe/util/Makefile b/lib/hipe/util/Makefile index 04de7f7823..eeb81ac482 100644 --- a/lib/hipe/util/Makefile +++ b/lib/hipe/util/Makefile @@ -48,7 +48,7 @@ HIPE_MODULES = hipe_vectors else HIPE_MODULES = endif -MODULES = hipe_timing hipe_dot hipe_digraph $(HIPE_MODULES) +MODULES = hipe_timing hipe_dot hipe_digraph hipe_dsets $(HIPE_MODULES) HRL_FILES= ERL_FILES= $(MODULES:%=%.erl) diff --git a/lib/hipe/util/hipe_dsets.erl b/lib/hipe/util/hipe_dsets.erl new file mode 100644 index 0000000000..9492cab0ff --- /dev/null +++ b/lib/hipe/util/hipe_dsets.erl @@ -0,0 +1,84 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% 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. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%@doc +%% IMMUTABLE DISJOINT SETS OF ARBITRARY TERMS +%% +%% The disjoint set forests data structure, for elements of arbitrary types. +%% Note that the find operation mutates the set. +%% +%% We could do this more efficiently if we restricted the elements to integers, +%% and used the (mutable) hipe arrays. For arbitrary terms ETS could be used, +%% for a persistent interface (which isn't that nice when even accessors return +%% modified copies), the array module could be used. +-module(hipe_dsets). + +-export([new/1, find/2, union/3, to_map/1, to_rllist/1]). +-export_type([dsets/1]). + +-opaque dsets(X) :: #{X => {node, X} | {root, non_neg_integer()}}. + +-spec new([E]) -> dsets(E). +new(Elems) -> maps:from_list([{E,{root,0}} || E <- Elems]). + +-spec find(E, dsets(E)) -> {E, dsets(E)}. +find(E, DS0) -> + case DS0 of + #{E := {root,_}} -> {E, DS0}; + #{E := {node,N}} -> + case find(N, DS0) of + {N, _}=T -> T; + {R, DS1} -> {R, DS1#{E := {node,R}}} + end; + _ -> error(badarg, [E, DS0]) + end. + +-spec union(E, E, dsets(E)) -> dsets(E). +union(X, Y, DS0) -> + {XRoot, DS1} = find(X, DS0), + case find(Y, DS1) of + {XRoot, DS2} -> DS2; + {YRoot, DS2} -> + #{XRoot := {root,XRR}, YRoot := {root,YRR}} = DS2, + if XRR < YRR -> DS2#{XRoot := {node,YRoot}}; + XRR > YRR -> DS2#{YRoot := {node,XRoot}}; + true -> DS2#{YRoot := {node,XRoot}, XRoot := {root,XRR+1}} + end + end. + +-spec to_map(dsets(E)) -> {#{Elem::E => Root::E}, dsets(E)}. +to_map(DS) -> + to_map(maps:keys(DS), DS, #{}). + +to_map([], DS, Acc) -> {Acc, DS}; +to_map([K|Ks], DS0, Acc) -> + {KR, DS} = find(K, DS0), + to_map(Ks, DS, Acc#{K => KR}). + +-spec to_rllist(dsets(E)) -> {[{Root::E, Elems::[E]}], dsets(E)}. +to_rllist(DS0) -> + {Lists, DS} = to_rllist(maps:keys(DS0), #{}, DS0), + {maps:to_list(Lists), DS}. + +to_rllist([], Acc, DS) -> {Acc, DS}; +to_rllist([E|Es], Acc, DS0) -> + {ERoot, DS} = find(E, DS0), + to_rllist(Es, map_append(ERoot, E, Acc), DS). + +map_append(Key, Elem, Map) -> + case Map of + #{Key := List} -> Map#{Key := [Elem|List]}; + #{} -> Map#{Key => [Elem]} + end. -- cgit v1.2.3