aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMagnus Lång <[email protected]>2016-06-20 18:57:00 +0200
committerMagnus Lång <[email protected]>2016-09-02 15:59:17 +0200
commit0ef50d2e3ca058e94676f9ec48de805f216c6c9e (patch)
tree53de0b4262804791e608d8ccd94b66b4f609ff15
parent52964d9fbc8031298c977d5e4a9ef7b5605875ae (diff)
downloadotp-0ef50d2e3ca058e94676f9ec48de805f216c6c9e.tar.gz
otp-0ef50d2e3ca058e94676f9ec48de805f216c6c9e.tar.bz2
otp-0ef50d2e3ca058e94676f9ec48de805f216c6c9e.zip
hipe_regalloc_prepass: Rename coloring collisions
-rw-r--r--lib/hipe/regalloc/hipe_regalloc_loop.erl14
-rw-r--r--lib/hipe/regalloc/hipe_regalloc_prepass.erl160
2 files changed, 149 insertions, 25 deletions
diff --git a/lib/hipe/regalloc/hipe_regalloc_loop.erl b/lib/hipe/regalloc/hipe_regalloc_loop.erl
index 34662200e5..8d564c35ae 100644
--- a/lib/hipe/regalloc/hipe_regalloc_loop.erl
+++ b/lib/hipe/regalloc/hipe_regalloc_loop.erl
@@ -39,21 +39,24 @@ ra_common(CFG, SpillIndex, Options, RegAllocMod, TargetMod) ->
SpillLimit = TargetMod:number_of_temporaries(CFG),
alloc(CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod).
-alloc(CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
+alloc(CFG0, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
?inc_counter(ra_iteration_counter, 1),
- {Coloring, _NewSpillIndex, Liveness} =
+ {Coloring, _NewSpillIndex, CFG, MaybeLiveness} =
case proplists:get_bool(ra_prespill, Options) of
true ->
hipe_regalloc_prepass:regalloc(
- RegAllocMod, CFG, SpillIndex, SpillLimit, TargetMod, Options);
+ RegAllocMod, CFG0, SpillIndex, SpillLimit, TargetMod, Options);
false ->
- RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit, TargetMod, Options)
+ {C, SI, L} = RegAllocMod:regalloc(CFG0, SpillIndex, SpillLimit,
+ TargetMod, Options),
+ {C, SI, CFG0, L}
end,
{NewCFG, DidSpill} = TargetMod:check_and_rewrite(CFG, Coloring),
case DidSpill of
false -> %% No new temps, we are done.
?add_spills(Options, _NewSpillIndex),
TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod),
+ Liveness = liveness_force(TargetMod, CFG, MaybeLiveness),
{TempMap2, NewSpillIndex2} =
hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
TargetMod, TempMap),
@@ -71,3 +74,6 @@ alloc(CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
%% the list of temps not to spill is uninteresting.
alloc(NewCFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod)
end.
+
+liveness_force(TargetMod, CFG, undefined) -> TargetMod:analyze(CFG);
+liveness_force(_TargetMod, _CFG, Defined) -> Defined.
diff --git a/lib/hipe/regalloc/hipe_regalloc_prepass.erl b/lib/hipe/regalloc/hipe_regalloc_prepass.erl
index cb383ac479..6015c4a042 100644
--- a/lib/hipe/regalloc/hipe_regalloc_prepass.erl
+++ b/lib/hipe/regalloc/hipe_regalloc_prepass.erl
@@ -137,23 +137,32 @@
-spec regalloc(module(), target_cfg(), spillno(), spillno(), module(),
proplists:proplist())
- -> {hipe_map(), spillno(), target_liveness()}.
-regalloc(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options) ->
- Liveness = Target:analyze(CFG),
+ -> {hipe_map(), spillno(), target_cfg(),
+ undefined | target_liveness()}.
+regalloc(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, Options) ->
+ Liveness0 = Target:analyze(CFG0),
{ScanBBs, Seen, SpillMap, SpillIndex1} =
- scan_cfg(CFG, Liveness, SpillIndex0, Target),
+ scan_cfg(CFG0, Liveness0, SpillIndex0, Target),
AllPrecoloured = Target:all_precoloured(),
- {PartColoring, SpillIndex} =
+ {PartColoring, SpillIndex, NewCFG} =
case proplists:get_bool(ra_partitioned, Options) of
true when map_size(Seen) - map_size(SpillMap) - length(AllPrecoloured)
> ?TUNE_MIN_SPLIT_PSEUDOS ->
regalloc_partitioned(SpillMap, SpillIndex1, SpillLimit, ScanBBs,
- CFG, Target, RegAllocMod, Options);
+ CFG0, Target, RegAllocMod, Options);
_ ->
regalloc_whole(Seen, SpillMap, SpillIndex1, SpillLimit, ScanBBs,
- CFG, Target, RegAllocMod, Options)
+ CFG0, Target, RegAllocMod, Options)
+ end,
+
+ %% It's not worth it to add rewriting of the liveness information; just return
+ %% 'undefined' and let it be recomputed when needed.
+ {CFG, Liveness} =
+ case NewCFG of
+ same -> {CFG0, Liveness0};
+ {rewritten, CFG1} -> {CFG1, undefined}
end,
SpillColors = [{T, {spill, S}} || {T, S} <- maps:to_list(SpillMap)],
@@ -162,13 +171,13 @@ regalloc(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options) ->
?ASSERT(begin
MaxPhys = lists:max(AllPrecoloured) + 1,
Unused = unused(live_pseudos(Seen, SpillMap, MaxPhys),
- SpillMap, CFG, Target),
- unused_unused(Unused, CFG, Target)
+ SpillMap, CFG0, Target),
+ unused_unused(Unused, CFG0, Target)
end),
?ASSERT(check_coloring(Coloring, CFG, Target)), % Sanity-check
- ?ASSERT(just_as_good_as(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target,
- Options, Coloring, Unused)),
- {Coloring, SpillIndex, Liveness}.
+ ?ASSERT(just_as_good_as(RegAllocMod, CFG, SpillIndex0, SpillLimit,
+ Target, Options, SpillMap, Coloring, Unused)),
+ {Coloring, SpillIndex, CFG, Liveness}.
regalloc_whole(Seen, SpillMap, SpillIndex0, SpillLimit, ScanBBs,
CFG, Target, RegAllocMod, Options) ->
@@ -184,7 +193,7 @@ regalloc_whole(Seen, SpillMap, SpillIndex0, SpillLimit, ScanBBs,
RegAllocMod:regalloc(SubMod, SpillIndex0, SubSpillLimit, SubTarget,
Options),
?ASSERT(check_coloring(SubColoring, SubMod, SubTarget)),
- {translate_coloring(SubColoring, InvMap), SpillIndex}.
+ {translate_coloring(SubColoring, InvMap), SpillIndex, same}.
regalloc_partitioned(SpillMap, SpillIndex0, SpillLimit, ScanBBs,
CFG, Target, RegAllocMod, Options) ->
@@ -215,9 +224,11 @@ regalloc_partitioned(SpillMap, SpillIndex0, SpillLimit, ScanBBs,
RegAllocMod:regalloc(SubMod, SpillIndex1, SubSpillLimit, SubTarget,
Options),
?ASSERT(check_coloring(SubColoring, SubMod, SubTarget)),
- {translate_coloring(SubColoring, InvMap), SpillIndex2}
+ {{translate_coloring(SubColoring, InvMap), Elems}, SpillIndex2}
end, SpillIndex0, PartBBsRLList),
- {combine_allocations(Allocations, MaxPhys), SpillIndex}.
+ {Coloring, NewCFG} =
+ combine_allocations(Allocations, MaxPhys, PartBBs, Target, CFG),
+ {Coloring, SpillIndex, NewCFG}.
-spec number_and_map([target_reg()], target_liveset(), target_reg())
-> {sub_map(), inv_map(), temp(), temp(), temp()}.
@@ -640,15 +651,122 @@ transform_bb(BB, SubMap) ->
%% For now, part_bb_part() and split_bb() share representation
transform_whole_bb(BB, SubMap).
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Fifth pass
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Combine colorings and substitute temps in actual cfg if there were
+%% collisions.
+
+%% A temp can sometimes appear in more than one partition. For example, defining
+%% an unused value. If these are found by combine_allocations, we have to
+%% rename this temp in one of the partitions on the real cfg.
%%
-combine_allocations([A|As], MaxPhys) ->
- {Phys, Pseuds} = lists:partition(fun({R,_}) -> R < MaxPhys end, A),
- combine_allocations_1(As, MaxPhys, Phys, Pseuds).
+%% We optimistically assume that there will be no such collisions, and when
+%% there are, we fix them up as they're found.
-combine_allocations_1([], _MaxPhys, Phys, Pseuds) -> Phys ++ Pseuds;
-combine_allocations_1([A|As], MaxPhys, Phys, Acc) ->
+-spec combine_allocations([{hipe_map(), [bb_dset_key()]}], target_reg(),
+ part_bbs(), module(), target_cfg())
+ -> {hipe_map(), same | {rewritten, target_cfg()}}.
+combine_allocations([{A,_}|As], MaxPhys, PartBBs, Target, CFG) ->
{Phys, Pseuds} = lists:partition(fun({R,_}) -> R < MaxPhys end, A),
- combine_allocations_1(As, MaxPhys, Phys, Pseuds ++ Acc).
+ {Seen, _, []} = partition_by_seen(Pseuds, #{}, [], []),
+ combine_allocations(As, MaxPhys, PartBBs, Target, Phys, Seen, Pseuds,
+ {same, CFG}).
+
+-spec combine_allocations([{hipe_map(), [bb_dset_key()]}], target_reg(),
+ part_bbs(), module(), hipe_map(), seen(), hipe_map(),
+ {same|rewritten, target_cfg()})
+ -> {hipe_map(), same | {rewritten, target_cfg()}}.
+combine_allocations([], _MaxPhys, _PartBBs, _Target, Phys, _Seen, Pseuds,
+ CFGT) ->
+ {Phys ++ Pseuds, case CFGT of
+ {same, _} -> same;
+ {rewritten, _} -> CFGT
+ end};
+combine_allocations([{A,PartElems}|As], MaxPhys, PartBBs, Target, Phys, Seen0,
+ Acc, CFGT={_,CFG0}) ->
+ {Phys, Pseuds0} = lists:partition(fun({R,_}) -> R < MaxPhys end, A),
+ {Seen, Pseuds, Collisions} = partition_by_seen(Pseuds0, Seen0, [], []),
+ case Collisions of
+ [] -> combine_allocations(As, MaxPhys, PartBBs, Target, Phys, Seen,
+ Pseuds++Acc, CFGT);
+ _ ->
+ %% There were collisions; rename all the temp numbers in Collisions
+ {CFG, Renamed} = rename(Collisions, PartElems, PartBBs, Target, CFG0),
+ combine_allocations(As, MaxPhys, PartBBs, Target, Phys, Seen,
+ Pseuds++Renamed++Acc, {rewritten,CFG})
+ end.
+
+%% @doc Partitions a coloring on whether the registers are in the Seen set,
+%% adding any new registers to the set.
+-spec partition_by_seen(hipe_map(), seen(), hipe_map(), hipe_map())
+ -> {seen(), hipe_map(), hipe_map()}.
+partition_by_seen([], Seen, Acc, Collisions) -> {Seen, Acc, Collisions};
+partition_by_seen([C={R,_}|Cs], Seen, Acc, Colls) ->
+ case Seen of
+ #{R := _} -> partition_by_seen(Cs, Seen, Acc, [C|Colls]);
+ #{} -> partition_by_seen(Cs, Seen#{R => []}, [C|Acc], Colls)
+ end.
+
+-spec rename(hipe_map(), [bb_dset_key()], part_bbs(), module(), target_cfg())
+ -> {target_cfg(), hipe_map()}.
+rename(CollisionList, PartElems, PartBBs, Target, CFG0) ->
+ {Map, Renamed} = new_names(CollisionList, Target, #{}, []),
+ Fun = fun(I) ->
+ Target:subst_temps(
+ fun(Temp) ->
+ N = Target:reg_nr(Temp),
+ case Map of
+ #{N := Subst} -> Target:update_reg_nr(Subst, Temp);
+ #{} -> Temp
+ end
+ end, I)
+ end,
+ {rename_1(PartElems, PartBBs, Target, Fun, CFG0), Renamed}.
+
+-type rename_map() :: #{target_reg() => target_reg()}.
+-type rename_fun() :: fun((target_instr()) -> target_instr()).
+
+-spec new_names(hipe_map(), module(), rename_map(), hipe_map())
+ -> {rename_map(), hipe_map()}.
+new_names([], _Target, Map, Renamed) -> {Map, Renamed};
+new_names([{R,C}|As], Target, Map, Renamed) ->
+ Subst = Target:new_reg_nr(),
+ new_names(As, Target, Map#{R => Subst}, [{Subst, C} | Renamed]).
+
+%% @doc Maps over all instructions in a partition on the original CFG.
+-spec rename_1([bb_dset_key()], part_bbs(), module(), rename_fun(),
+ target_cfg()) -> target_cfg().
+rename_1([], _PartBBs, _Target, _Fun, CFG) -> CFG;
+rename_1([{Half,L}|Es], PartBBs, Target, Fun, CFG0) ->
+ Code0 = hipe_bb:code(BB = Target:bb(CFG0, L)),
+ Code = case {Half, maps:get(L, PartBBs)} of
+ {entry, {single,_}} -> lists:map(Fun, Code0);
+ {entry, {split,PBBP,_}} ->
+ map_start(Fun, part_bb_part_len(PBBP), Code0);
+ {exit, {split,_,PBBP}} ->
+ map_end(Fun, part_bb_part_len(PBBP), Code0);
+ {exit, {single, _}} -> Code0
+ end,
+ CFG = Target:update_bb(CFG0, L, hipe_bb:code_update(BB, Code)),
+ rename_1(Es, PartBBs, Target, Fun, CFG).
+
+-spec part_bb_part_len(part_bb_part()) -> non_neg_integer().
+part_bb_part_len({Code, _Livein, _Liveout}) -> length(Code).
+
+%% @doc Map the first N elements of a list
+-spec map_start(fun((X) -> Y), non_neg_integer(), [X]) -> [X|Y].
+map_start(_Fun, 0, List) -> List;
+map_start(Fun, N, [E|Es]) ->
+ [Fun(E)|map_start(Fun, N-1, Es)].
+
+%% @doc Map the last N elements of a list
+-spec map_end(fun((X) -> Y), non_neg_integer(), [X]) -> [X|Y].
+map_end(Fun, N, List) ->
+ map_end(Fun, N, length(List), List).
+
+map_end(Fun, N, Len, [E|Es]) when Len > N -> [E|map_end(Fun, N, Len-1, Es)];
+map_end(Fun, N, Len, List) when Len =:= N -> lists:map(Fun, List).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Temp map ADT