aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/regalloc
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/regalloc')
-rw-r--r--lib/hipe/regalloc/hipe_coalescing_regalloc.erl7
-rw-r--r--lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl16
-rw-r--r--lib/hipe/regalloc/hipe_ls_regalloc.erl20
-rw-r--r--lib/hipe/regalloc/hipe_optimistic_regalloc.erl12
-rw-r--r--lib/hipe/regalloc/hipe_regalloc_loop.erl58
-rw-r--r--lib/hipe/regalloc/hipe_regalloc_prepass.erl56
6 files changed, 74 insertions, 95 deletions
diff --git a/lib/hipe/regalloc/hipe_coalescing_regalloc.erl b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl
index bbb2e3ecf0..5f4bd4e524 100644
--- a/lib/hipe/regalloc/hipe_coalescing_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl
@@ -30,7 +30,7 @@
%%-----------------------------------------------------------------------
-module(hipe_coalescing_regalloc).
--export([regalloc/5]).
+-export([regalloc/6]).
%%-ifndef(DEBUG).
%%-define(DEBUG,true).
@@ -54,10 +54,9 @@
%% SpillIndex2 -- A new spill index
%%-----------------------------------------------------------------------
-regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
+regalloc(CFG, Liveness, SpillIndex, SpillLimit, Target, _Options) ->
%% Build interference graph
?debug_msg("Build IG\n", []),
- Liveness = Target:analyze(CFG),
IG = hipe_ig:build(CFG, Liveness, Target),
%% io:format("IG: ~p\n", [IG]),
@@ -98,7 +97,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
{Coloring, SpillIndex2} =
build_namelist(Node_sets2, SpillIndex, Alias0, Color1),
?debug_msg("Coloring ~p\n", [Coloring]),
- {Coloring, SpillIndex2, Liveness}.
+ {Coloring, SpillIndex2}.
%%----------------------------------------------------------------------
%% Function: do_coloring
diff --git a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl
index f71feebfc6..225f06bded 100644
--- a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl
@@ -51,7 +51,7 @@
%%
-module(hipe_graph_coloring_regalloc).
--export([regalloc/5]).
+-export([regalloc/6]).
%%-ifndef(DO_ASSERT).
%%-define(DO_ASSERT, true).
@@ -77,12 +77,13 @@
%% that the coloring agrees with the interference graph (that is, that
%% no neighbors have the same register or spill location).
-%% @spec regalloc(#cfg{}, non_neg_fixnum(), non_neg_fixnum(), atom(), list()) -> {, non_neg_fixnum()}
+%% @spec regalloc(#cfg{}, liveness(), non_neg_fixnum(), non_neg_fixnum(),
+%% atom(), list()) -> {, non_neg_fixnum()}
-regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
+regalloc(CFG, Live, SpillIndex, SpillLimit, Target, _Options) ->
PhysRegs = Target:allocatable(),
?report2("building IG~n", []),
- {IG, Spill, Live} = build_ig(CFG, Target),
+ {IG, Spill} = build_ig(CFG, Live, Target),
%% check_ig(IG),
?report3("graph: ~p~nphysical regs: ~p~n", [list_ig(IG), PhysRegs]),
@@ -102,7 +103,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
Coloring = [{X, {reg, X}} || X <- NotAllocatable] ++ Cols,
?ASSERT(check_coloring(Coloring, IG, Target)),
- {Coloring, NewSpillIndex, Live}.
+ {Coloring, NewSpillIndex}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -112,8 +113,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
%% Returns {Interference_graph, Spill_cost_dictionary}
%%
-build_ig(CFG, Target) ->
- Live = Target:analyze(CFG),
+build_ig(CFG, Live, Target) ->
NumN = Target:number_of_temporaries(CFG), % poss. N-1?
{IG, Spill} = build_ig_bbs(Target:labels(CFG),
CFG,
@@ -121,7 +121,7 @@ build_ig(CFG, Target) ->
empty_ig(NumN),
empty_spill(NumN),
Target),
- {normalize_ig(IG), Spill, Live}.
+ {normalize_ig(IG), Spill}.
build_ig_bbs([], _CFG, _Live, IG, Spill, _Target) ->
{IG, Spill};
diff --git a/lib/hipe/regalloc/hipe_ls_regalloc.erl b/lib/hipe/regalloc/hipe_ls_regalloc.erl
index c318927077..8d9cd8f507 100644
--- a/lib/hipe/regalloc/hipe_ls_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_ls_regalloc.erl
@@ -56,7 +56,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-module(hipe_ls_regalloc).
--export([regalloc/7, regalloc/8]).
+-export([regalloc/8]).
%%-define(DEBUG,1).
-define(HIPE_INSTRUMENT_COMPILER, true).
@@ -95,19 +95,8 @@
%% </ol>
%% @end
%%- - - - - - - - - - - - - - - - - - - - - - - -
-regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
- regalloc(CFG, undefined, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target).
-
-regalloc(CFG, Liveness0, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
+regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
?debug_msg("LinearScan: ~w\n", [erlang:statistics(runtime)]),
- %% Step 1: Calculate liveness (Call external implementation.)
- Liveness = case Liveness0 of
- undefined ->
- L=liveness(CFG, Target),
- ?debug_msg("liveness (done)~w\n", [erlang:statistics(runtime)]),
- L;
- _ -> Liveness0
- end,
USIntervals = calculate_intervals(CFG, Liveness,
Entrypoints, Options, Target),
?debug_msg("intervals (done) ~w\n", [erlang:statistics(runtime)]),
@@ -119,7 +108,7 @@ regalloc(CFG, Liveness0, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options,
{Coloring, NewSpillIndex}
= allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target),
?debug_msg("allocation (done) ~w\n", [erlang:statistics(runtime)]),
- {Coloring, NewSpillIndex, Liveness}.
+ {Coloring, NewSpillIndex}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
@@ -760,9 +749,6 @@ create_freeregs([]) ->
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-liveness(CFG, Target) ->
- Target:analyze(CFG).
-
bb(CFG, L, Target) ->
Target:bb(CFG,L).
diff --git a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
index 67674be14c..43c6424655 100644
--- a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
@@ -29,7 +29,7 @@
%%-----------------------------------------------------------------------
-module(hipe_optimistic_regalloc).
--export([regalloc/5]).
+-export([regalloc/6]).
-ifndef(DEBUG).
%%-define(DEBUG,true).
@@ -81,12 +81,11 @@
%% SpillIndex2 -- A new spill index
%%-----------------------------------------------------------------------
-ifdef(COMPARE_ITERATED_OPTIMISTIC).
-regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
+regalloc(CFG, Liveness, SpillIndex, SpillLimit, Target, _Options) ->
?debug_msg("optimistic ~w\n",[Target]),
?debug_msg("CFG: ~p\n",[CFG]),
%% Build interference graph
?debug_msg("Build IG\n",[]),
- Liveness = Target:analyze(CFG),
IG_O = hipe_ig:build(CFG, Liveness, Target),
IG = hipe_ig:build(CFG, Liveness, Target),
?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]),
@@ -219,14 +218,13 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
SortedColoring_O = {sort_stack(element(1, Coloring_O)), element(2, Coloring_O)},
?debug_msg("SortedColoring_O ~p\n",[SortedColoring_O]),
sanity_compare(SortedColoring_O, SortedColoring),
- {Coloring,SpillIndex2,Liveness}.
+ {Coloring,SpillIndex2}.
-else.
-regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
+regalloc(CFG, Liveness, SpillIndex, SpillLimit, Target, _Options) ->
?debug_msg("optimistic ~w\n",[Target]),
?debug_msg("CFG: ~p\n",[CFG]),
%% Build interference graph
?debug_msg("Build IG\n",[]),
- Liveness = Target:analyze(CFG),
IG = hipe_ig:build(CFG, Liveness, Target),
?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]),
?debug_msg("IG:\n",[]),
@@ -321,7 +319,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
?debug_msg("Build mapping _N ~w\n",[Node_sets2]),
{Coloring, SpillIndex2} = build_namelist(Node_sets2,SpillIndex,Alias2,Color1),
?debug_msg("Coloring ~p\n",[Coloring]),
- {Coloring,SpillIndex2,Liveness}.
+ {Coloring,SpillIndex2}.
-endif.
%%----------------------------------------------------------------------
diff --git a/lib/hipe/regalloc/hipe_regalloc_loop.erl b/lib/hipe/regalloc/hipe_regalloc_loop.erl
index 3b21a377df..9557461244 100644
--- a/lib/hipe/regalloc/hipe_regalloc_loop.erl
+++ b/lib/hipe/regalloc/hipe_regalloc_loop.erl
@@ -21,32 +21,32 @@
%%% Common wrapper for graph_coloring and coalescing regallocs.
-module(hipe_regalloc_loop).
--export([ra/5, ra_fp/4]).
+-export([ra/6, ra_fp/5]).
%%-define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation.
-include("../main/hipe.hrl").
-ra(CFG, SpillIndex, Options, RegAllocMod, TargetMod) ->
- {NewCFG, Coloring, _NewSpillIndex} =
- ra_common(CFG, SpillIndex, Options, RegAllocMod, TargetMod),
- {NewCFG, Coloring}.
+ra(CFG, Liveness0, SpillIndex, Options, RegAllocMod, TargetMod) ->
+ {NewCFG, Liveness, Coloring, _NewSpillIndex} =
+ ra_common(CFG, Liveness0, SpillIndex, Options, RegAllocMod, TargetMod),
+ {NewCFG, Liveness, Coloring}.
-ra_fp(CFG, Options, RegAllocMod, TargetMod) ->
- ra_common(CFG, 0, Options, RegAllocMod, TargetMod).
+ra_fp(CFG, Liveness, Options, RegAllocMod, TargetMod) ->
+ ra_common(CFG, Liveness, 0, Options, RegAllocMod, TargetMod).
-ra_common(CFG0, SpillIndex, Options, RegAllocMod, TargetMod) ->
+ra_common(CFG0, Liveness0, 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),
+ {Coloring, _, CFG, Liveness} =
+ call_allocator_initial(CFG0, Liveness0, 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(Coloring, CFG, MaybeLiveness, SpillLimit, SpillIndex, Options,
+ alloc(Coloring, CFG, Liveness, SpillLimit, SpillIndex, Options,
RegAllocMod, TargetMod).
-alloc(Coloring, CFG0, MaybeLiveness0, SpillLimit, SpillIndex, Options,
+alloc(Coloring, CFG0, Liveness, SpillLimit, SpillIndex, Options,
RegAllocMod, TargetMod) ->
?inc_counter(ra_iteration_counter, 1),
{CFG, DidSpill} = TargetMod:check_and_rewrite(CFG0, Coloring),
@@ -54,7 +54,6 @@ alloc(Coloring, CFG0, MaybeLiveness0, SpillLimit, SpillIndex, Options,
false -> %% No new temps, we are done.
?add_spills(Options, _NewSpillIndex),
TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod),
- Liveness = liveness_force(TargetMod, CFG0, MaybeLiveness0),
{TempMap2, NewSpillIndex2} =
hipe_spillmin:stackalloc(CFG0, Liveness, [], SpillIndex, Options,
TargetMod, TempMap),
@@ -66,37 +65,36 @@ alloc(Coloring, CFG0, MaybeLiveness0, SpillLimit, SpillIndex, Options,
%% false ->
%% ok
%% end,
- {CFG, Coloring2, NewSpillIndex2};
+ {CFG, Liveness, Coloring2, NewSpillIndex2};
_ ->
%% Since SpillLimit is used as a low-water-mark
%% the list of temps not to spill is uninteresting.
- {NewColoring, _NewSpillIndex, Liveness} =
- call_allocator(CFG, SpillLimit, SpillIndex, Options, RegAllocMod,
- TargetMod),
+ {NewColoring, _NewSpillIndex} =
+ call_allocator(CFG, Liveness, SpillLimit, SpillIndex, Options,
+ RegAllocMod, TargetMod),
alloc(NewColoring, CFG, Liveness, SpillLimit, SpillIndex, Options,
RegAllocMod, TargetMod)
end.
-call_allocator_initial(CFG, SpillLimit, SpillIndex, Options, RegAllocMod,
- TargetMod) ->
+call_allocator_initial(CFG, Liveness, 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);
+ RegAllocMod, CFG, Liveness, SpillIndex, SpillLimit, TargetMod, Options);
false ->
- {C, SI, L} = RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit,
- TargetMod, Options),
- {C, SI, CFG, L}
+ {C, SI} = RegAllocMod:regalloc(CFG, Liveness, SpillIndex, SpillLimit,
+ TargetMod, Options),
+ {C, SI, CFG, Liveness}
end.
-call_allocator(CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
+call_allocator(CFG, Liveness, SpillLimit, SpillIndex, Options, RegAllocMod,
+ TargetMod) ->
case proplists:get_bool(ra_prespill, Options) of
true ->
hipe_regalloc_prepass:regalloc(
- RegAllocMod, CFG, SpillIndex, SpillLimit, TargetMod, Options);
+ RegAllocMod, CFG, Liveness, SpillIndex, SpillLimit, TargetMod, Options);
false ->
- RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit, TargetMod, Options)
+ RegAllocMod:regalloc(CFG, Liveness, SpillIndex, SpillLimit, TargetMod,
+ Options)
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 c2531bc451..75f377fcce 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, regalloc_initial/6]).
+-export([regalloc/7, regalloc_initial/7]).
-ifndef(DEBUG).
-compile(inline).
@@ -135,37 +135,35 @@
-type temp() :: non_neg_integer().
-type label() :: non_neg_integer().
--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),
+-spec regalloc(module(), target_cfg(), target_liveness(), spillno(), spillno(),
+ module(), proplists:proplist())
+ -> {hipe_map(), spillno()}.
+regalloc(RegAllocMod, CFG, Liveness, SpillIndex0, SpillLimit, Target,
+ Options) ->
{Coloring, SpillIndex, same} =
regalloc_1(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options,
Liveness),
- {Coloring, SpillIndex, Liveness}.
+ {Coloring, SpillIndex}.
-%% regalloc_initial/6 is allowed to introduce new temporaries, unlike
-%% regalloc/6.
-%% In order for regalloc/6 to never introduce temporaries, regalloc/6 must never
-%% choose to do split allocation unless regalloc_initial/6 does. This is the
+%% regalloc_initial/7 is allowed to introduce new temporaries, unlike
+%% regalloc/7.
+%% In order for regalloc/7 to never introduce temporaries, regalloc/7 must never
+%% choose to do split allocation unless regalloc_initial/7 does. This is the
%% reason that the splitting heuristic is solely based on the number of basic
%% blocks, which does not change during the register allocation loop.
--spec regalloc_initial(module(), target_cfg(), spillno(), spillno(), module(),
- proplists:proplist())
+-spec regalloc_initial(module(), target_cfg(), target_liveness(), 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),
+ target_liveness()}.
+regalloc_initial(RegAllocMod, CFG0, Liveness0, SpillIndex0, SpillLimit, Target,
+ Options) ->
{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}
+ {rewritten, CFG1} -> {CFG1, Target:analyze(CFG1)}
end,
{Coloring, SpillIndex, CFG, Liveness}.
@@ -204,7 +202,7 @@ regalloc_1(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, Options,
end,
check_coloring(Coloring, CFG, Target)
end), % Sanity-check
- ?ASSERT(just_as_good_as(RegAllocMod, CFG, SpillIndex0, SpillLimit,
+ ?ASSERT(just_as_good_as(RegAllocMod, CFG, Liveness, SpillIndex0, SpillLimit,
Target, Options, SpillMap, Coloring, Unused)),
{Coloring, SpillIndex, NewCFG}.
@@ -218,8 +216,8 @@ regalloc_whole(Seen, SpillMap, SpillIndex0, SpillLimit, ScanBBs,
BBs = transform_whole_cfg(ScanBBs, SubMap),
SubMod = #cfg{cfg=CFG, bbs=BBs, max_reg=MaxR},
SubTarget = #?MODULE{target=Target, max_phys=MaxPhys, inv=InvMap, sub=SubMap},
- {SubColoring, SpillIndex, _} =
- RegAllocMod:regalloc(SubMod, SpillIndex0, SubSpillLimit, SubTarget,
+ {SubColoring, SpillIndex} =
+ RegAllocMod:regalloc(SubMod, SubMod, SpillIndex0, SubSpillLimit, SubTarget,
Options),
?ASSERT(check_coloring(SubColoring, SubMod, SubTarget)),
{translate_coloring(SubColoring, InvMap), SpillIndex, same}.
@@ -249,9 +247,9 @@ regalloc_partitioned(SpillMap, SpillIndex0, SpillLimit, ScanBBs,
SubMod = #cfg{cfg=CFG, bbs=BBs, max_reg=MaxR, rpostorder=RPost},
SubTarget = #?MODULE{target=Target, max_phys=MaxPhys, inv=InvMap,
sub=SubMap},
- {SubColoring, SpillIndex2, _} =
- RegAllocMod:regalloc(SubMod, SpillIndex1, SubSpillLimit, SubTarget,
- Options),
+ {SubColoring, SpillIndex2} =
+ RegAllocMod:regalloc(SubMod, SubMod, SpillIndex1, SubSpillLimit,
+ SubTarget, Options),
?ASSERT(check_coloring(SubColoring, SubMod, SubTarget)),
{{translate_coloring(SubColoring, InvMap), Elems}, SpillIndex2}
end, SpillIndex0, PartBBsRLList),
@@ -885,10 +883,10 @@ unused_unused(Unused, CFG, Target) ->
%%%%%%%%%%%%%%%%%%%%
%% Check that no register allocation opportunities were missed due to ?MODULE
%%
-just_as_good_as(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options,
- SpillMap, Coloring, Unused) ->
- {CheckColoring, _, _} = RegAllocMod:regalloc(CFG, SpillIndex0, SpillLimit,
- Target, Options),
+just_as_good_as(RegAllocMod, CFG, Liveness, SpillIndex0, SpillLimit, Target,
+ Options, SpillMap, Coloring, Unused) ->
+ {CheckColoring, _} = RegAllocMod:regalloc(CFG, Liveness, SpillIndex0,
+ SpillLimit, Target, Options),
Now = lists:sort([{R,Kind} || {R,{Kind,_}} <- Coloring,
not ordsets:is_element(R, Unused)]),
Check = lists:sort([{R,Kind} || {R,{Kind,_}} <- CheckColoring,
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 20:52:37 +0000