From 1039c0196a7e643c63ce71b2c6daa2b78b3aa832 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Magnus=20L=C3=A5ng?= Date: Thu, 1 Sep 2016 17:21:25 +0200 Subject: hipe: Reuse liveness between regalloc iterations This is sound because the liveness data structure only stores liveness info at basic block boundaries, and the rewrites that happen in TargetSpecific:check_and_rewrite/2 preserves all existing definitions and uses, and all new liveness intervals, belonging to newly introduced temporaries, are always local to a basic block, and thus do not show up in the liveout or livein sets for the basic block. --- lib/hipe/regalloc/hipe_coalescing_regalloc.erl | 7 ++- lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl | 16 +++--- lib/hipe/regalloc/hipe_ls_regalloc.erl | 20 ++------ lib/hipe/regalloc/hipe_optimistic_regalloc.erl | 12 ++--- lib/hipe/regalloc/hipe_regalloc_loop.erl | 58 +++++++++++----------- lib/hipe/regalloc/hipe_regalloc_prepass.erl | 56 ++++++++++----------- 6 files changed, 74 insertions(+), 95 deletions(-) (limited to 'lib/hipe/regalloc') 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 @@ %% %% @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, -- cgit v1.2.3