aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMagnus Lång <[email protected]>2016-08-31 14:48:45 +0200
committerMagnus Lång <[email protected]>2016-09-02 15:59:17 +0200
commit904caa71a3754e3ee7f681cc7d4106d4a9979f1f (patch)
tree69b9361610ff2a6b84d84a85f9df007616ba0705
parent0ef50d2e3ca058e94676f9ec48de805f216c6c9e (diff)
downloadotp-904caa71a3754e3ee7f681cc7d4106d4a9979f1f.tar.gz
otp-904caa71a3754e3ee7f681cc7d4106d4a9979f1f.tar.bz2
otp-904caa71a3754e3ee7f681cc7d4106d4a9979f1f.zip
hipe: Make sure prepass temps are below SpillLimit
If temps introduced by hipe_regalloc_prepass end up above SpillLimit, the register allocators will not spill them. This constraint is unnecessarily limiting the allocators and might theoretically lead to unallocatable programs (more temps above SpillLimit alive at a time than there are physical registers).
-rw-r--r--lib/hipe/regalloc/hipe_regalloc_loop.erl59
-rw-r--r--lib/hipe/regalloc/hipe_regalloc_prepass.erl54
2 files changed, 80 insertions, 33 deletions
diff --git a/lib/hipe/regalloc/hipe_regalloc_loop.erl b/lib/hipe/regalloc/hipe_regalloc_loop.erl
index 8d564c35ae..3b21a377df 100644
--- a/lib/hipe/regalloc/hipe_regalloc_loop.erl
+++ b/lib/hipe/regalloc/hipe_regalloc_loop.erl
@@ -34,31 +34,29 @@ ra(CFG, SpillIndex, Options, RegAllocMod, TargetMod) ->
ra_fp(CFG, Options, RegAllocMod, TargetMod) ->
ra_common(CFG, 0, Options, RegAllocMod, TargetMod).
-ra_common(CFG, SpillIndex, Options, RegAllocMod, TargetMod) ->
+ra_common(CFG0, SpillIndex, Options, RegAllocMod, TargetMod) ->
?inc_counter(ra_calls_counter, 1),
+ SpillLimit0 = TargetMod:number_of_temporaries(CFG0),
+ {Coloring, _, CFG, MaybeLiveness} =
+ call_allocator_initial(CFG0, SpillLimit0, SpillIndex, Options, RegAllocMod,
+ TargetMod),
+ %% The first iteration, the hipe_regalloc_prepass may create new temps, these
+ %% should not end up above SpillLimit.
SpillLimit = TargetMod:number_of_temporaries(CFG),
- alloc(CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod).
+ alloc(Coloring, CFG, MaybeLiveness, SpillLimit, SpillIndex, Options,
+ RegAllocMod, TargetMod).
-alloc(CFG0, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
+alloc(Coloring, CFG0, MaybeLiveness0, SpillLimit, SpillIndex, Options,
+ RegAllocMod, TargetMod) ->
?inc_counter(ra_iteration_counter, 1),
- {Coloring, _NewSpillIndex, CFG, MaybeLiveness} =
- case proplists:get_bool(ra_prespill, Options) of
- true ->
- hipe_regalloc_prepass:regalloc(
- RegAllocMod, CFG0, SpillIndex, SpillLimit, TargetMod, Options);
- false ->
- {C, SI, L} = RegAllocMod:regalloc(CFG0, SpillIndex, SpillLimit,
- TargetMod, Options),
- {C, SI, CFG0, L}
- end,
- {NewCFG, DidSpill} = TargetMod:check_and_rewrite(CFG, Coloring),
+ {CFG, DidSpill} = TargetMod:check_and_rewrite(CFG0, 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),
+ Liveness = liveness_force(TargetMod, CFG0, MaybeLiveness0),
{TempMap2, NewSpillIndex2} =
- hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
+ hipe_spillmin:stackalloc(CFG0, Liveness, [], SpillIndex, Options,
TargetMod, TempMap),
Coloring2 =
hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
@@ -68,11 +66,36 @@ alloc(CFG0, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
%% false ->
%% ok
%% end,
- {NewCFG, Coloring2, NewSpillIndex2};
+ {CFG, Coloring2, NewSpillIndex2};
_ ->
%% Since SpillLimit is used as a low-water-mark
%% the list of temps not to spill is uninteresting.
- alloc(NewCFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod)
+ {NewColoring, _NewSpillIndex, Liveness} =
+ call_allocator(CFG, SpillLimit, SpillIndex, Options, RegAllocMod,
+ TargetMod),
+ alloc(NewColoring, CFG, Liveness, SpillLimit, SpillIndex, Options,
+ RegAllocMod, TargetMod)
+ end.
+
+call_allocator_initial(CFG, SpillLimit, SpillIndex, Options, RegAllocMod,
+ TargetMod) ->
+ case proplists:get_bool(ra_prespill, Options) of
+ true ->
+ hipe_regalloc_prepass:regalloc_initial(
+ RegAllocMod, CFG, SpillIndex, SpillLimit, TargetMod, Options);
+ false ->
+ {C, SI, L} = RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit,
+ TargetMod, Options),
+ {C, SI, CFG, L}
+ end.
+
+call_allocator(CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
+ case proplists:get_bool(ra_prespill, Options) of
+ true ->
+ hipe_regalloc_prepass:regalloc(
+ RegAllocMod, CFG, SpillIndex, SpillLimit, TargetMod, Options);
+ false ->
+ RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit, TargetMod, Options)
end.
liveness_force(TargetMod, CFG, undefined) -> TargetMod:analyze(CFG);
diff --git a/lib/hipe/regalloc/hipe_regalloc_prepass.erl b/lib/hipe/regalloc/hipe_regalloc_prepass.erl
index 6015c4a042..5a52e5ad51 100644
--- a/lib/hipe/regalloc/hipe_regalloc_prepass.erl
+++ b/lib/hipe/regalloc/hipe_regalloc_prepass.erl
@@ -44,7 +44,7 @@
%% hipe_regalloc_loop iteration, skipping directly to rewrite without ever
%% calling RegAllocMod.
-module(hipe_regalloc_prepass).
--export([regalloc/6]).
+-export([regalloc/6, regalloc_initial/6]).
-ifndef(DEBUG).
-compile(inline).
@@ -137,12 +137,37 @@
-spec regalloc(module(), target_cfg(), spillno(), spillno(), module(),
proplists:proplist())
- -> {hipe_map(), spillno(), target_cfg(),
- undefined | target_liveness()}.
-regalloc(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, Options) ->
+ -> {hipe_map(), spillno(), target_liveness()}.
+regalloc(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options) ->
+ Liveness = Target:analyze(CFG),
+ {Coloring, SpillIndex, same} =
+ regalloc_1(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options,
+ Liveness),
+ {Coloring, SpillIndex, Liveness}.
+
+%% regalloc_initial/6 is allowed to introduce new temporaries, unlike regalloc/6
+-spec regalloc_initial(module(), target_cfg(), spillno(), spillno(), module(),
+ proplists:proplist())
+ -> {hipe_map(), spillno(), target_cfg(),
+ undefined | target_liveness()}.
+regalloc_initial(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, Options) ->
Liveness0 = Target:analyze(CFG0),
+ {Coloring, SpillIndex, NewCFG} =
+ regalloc_1(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, Options,
+ Liveness0),
+ %% 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,
+ {Coloring, SpillIndex, CFG, Liveness}.
+
+regalloc_1(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, Options,
+ Liveness) ->
{ScanBBs, Seen, SpillMap, SpillIndex1} =
- scan_cfg(CFG0, Liveness0, SpillIndex0, Target),
+ scan_cfg(CFG0, Liveness, SpillIndex0, Target),
AllPrecoloured = Target:all_precoloured(),
@@ -157,14 +182,6 @@ regalloc(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, 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)],
Coloring = SpillColors ++ PartColoring,
@@ -174,10 +191,17 @@ regalloc(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, Options) ->
SpillMap, CFG0, Target),
unused_unused(Unused, CFG0, Target)
end),
- ?ASSERT(check_coloring(Coloring, CFG, Target)), % Sanity-check
+ ?ASSERT(begin
+ CFG =
+ case NewCFG of
+ same -> CFG0;
+ {rewritten, CFG1} -> CFG1
+ end,
+ check_coloring(Coloring, CFG, Target)
+ end), % Sanity-check
?ASSERT(just_as_good_as(RegAllocMod, CFG, SpillIndex0, SpillLimit,
Target, Options, SpillMap, Coloring, Unused)),
- {Coloring, SpillIndex, CFG, Liveness}.
+ {Coloring, SpillIndex, NewCFG}.
regalloc_whole(Seen, SpillMap, SpillIndex0, SpillLimit, ScanBBs,
CFG, Target, RegAllocMod, Options) ->