diff options
| -rw-r--r-- | lib/hipe/regalloc/hipe_regalloc_loop.erl | 14 | ||||
| -rw-r--r-- | lib/hipe/regalloc/hipe_regalloc_prepass.erl | 160 |
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 |