diff options
Diffstat (limited to 'lib/hipe/regalloc')
28 files changed, 3949 insertions, 876 deletions
diff --git a/lib/hipe/regalloc/Makefile b/lib/hipe/regalloc/Makefile index aaa4418f37..662efc9707 100644 --- a/lib/hipe/regalloc/Makefile +++ b/lib/hipe/regalloc/Makefile @@ -1,7 +1,7 @@ # # %CopyrightBegin% # -# Copyright Ericsson AB 2001-2016. All Rights Reserved. +# Copyright Ericsson AB 2001-2017. All Rights Reserved. # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. @@ -50,7 +50,10 @@ MODULES = hipe_ig hipe_ig_moves hipe_moves \ hipe_optimistic_regalloc \ hipe_coalescing_regalloc \ hipe_graph_coloring_regalloc \ + hipe_range_split \ hipe_regalloc_loop \ + hipe_regalloc_prepass \ + hipe_restore_reuse \ hipe_ls_regalloc \ hipe_ppc_specific hipe_ppc_specific_fp \ hipe_sparc_specific hipe_sparc_specific_fp \ @@ -123,7 +126,6 @@ $(EBIN)/hipe_amd64_specific_x87.beam: hipe_x86_specific_x87.erl $(EBIN)/hipe_coalescing_regalloc.beam: ../main/hipe.hrl $(EBIN)/hipe_graph_coloring_regalloc.beam: ../main/hipe.hrl $(EBIN)/hipe_ig.beam: ../main/hipe.hrl ../flow/cfg.hrl hipe_spillcost.hrl -$(EBIN)/hipe_ig_moves.beam: ../util/hipe_vectors.hrl $(EBIN)/hipe_ls_regalloc.beam: ../main/hipe.hrl $(EBIN)/hipe_optimistic_regalloc.beam: ../main/hipe.hrl $(EBIN)/hipe_regalloc_loop.beam: ../main/hipe.hrl diff --git a/lib/hipe/regalloc/hipe_adj_list.erl b/lib/hipe/regalloc/hipe_adj_list.erl index de59da2410..5066106074 100644 --- a/lib/hipe/regalloc/hipe_adj_list.erl +++ b/lib/hipe/regalloc/hipe_adj_list.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,8 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% %% %%---------------------------------------------------------------------- %% File : hipe_adj_list.erl diff --git a/lib/hipe/regalloc/hipe_amd64_specific.erl b/lib/hipe/regalloc/hipe_amd64_specific.erl index 6937e71ac7..72900563e6 100644 --- a/lib/hipe/regalloc/hipe_amd64_specific.erl +++ b/lib/hipe/regalloc/hipe_amd64_specific.erl @@ -1,8 +1,3 @@ -%% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2004-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -14,8 +9,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% + -define(HIPE_AMD64, true). -include("hipe_x86_specific.erl"). diff --git a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl index 50e5869d45..d592ba391c 100644 --- a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl +++ b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2004-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,44 +11,58 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -module(hipe_amd64_specific_sse2). --export([number_of_temporaries/1]). +-export([number_of_temporaries/2]). % The following exports are used as M:F(...) calls from other modules; %% e.g. hipe_amd64_ra_ls. --export([analyze/1, - bb/2, - args/1, - labels/1, - livein/2, - liveout/2, - uses/1, - defines/1, - def_use/1, - is_arg/1, %% used by hipe_ls_regalloc - is_move/1, - is_fixed/1, %% used by hipe_graph_coloring_regalloc - is_global/1, - is_precoloured/1, - reg_nr/1, - non_alloc/1, - allocatable/0, - physical_name/1, - all_precoloured/0, - new_spill_index/1, %% used by hipe_ls_regalloc - var_range/1, - breadthorder/1, - postorder/1, - reverse_postorder/1]). +-export([analyze/2, + bb/3, + args/2, + labels/2, + livein/3, + liveout/3, + uses/2, + defines/2, + defines_all_alloc/2, + def_use/2, + is_arg/2, %% used by hipe_ls_regalloc + is_move/2, + is_spill_move/2, + is_fixed/2, %% used by hipe_graph_coloring_regalloc + is_global/2, + is_precoloured/2, + reg_nr/2, + non_alloc/2, + allocatable/1, + allocatable/2, + temp0/1, + physical_name/2, + all_precoloured/1, + new_spill_index/2, %% used by hipe_ls_regalloc + var_range/2, + breadthorder/2, + postorder/2, + reverse_postorder/2]). %% callbacks for hipe_regalloc_loop --export([defun_to_cfg/1, - check_and_rewrite/2]). +-export([check_and_rewrite/3, + check_and_rewrite/4]). + +%% callbacks for hipe_regalloc_prepass, hipe_range_split +-export([mk_move/3, + mk_goto/2, + redirect_jmp/4, + new_label/1, + new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). + +%% callbacks for hipe_bb_weights +-export([branch_preds/2]). %%---------------------------------------------------------------------------- @@ -60,86 +70,102 @@ %%---------------------------------------------------------------------------- -defun_to_cfg(Defun) -> - hipe_x86_cfg:init(Defun). +check_and_rewrite(CFG, Coloring, no_context) -> + hipe_amd64_ra_sse2_postconditions:check_and_rewrite(CFG, Coloring). -check_and_rewrite(Defun, Coloring) -> - hipe_amd64_ra_sse2_postconditions:check_and_rewrite(Defun, Coloring). +check_and_rewrite(CFG, Coloring, Strategy, no_context) -> + hipe_amd64_ra_sse2_postconditions:check_and_rewrite( + CFG, Coloring, Strategy). -reverse_postorder(CFG) -> +reverse_postorder(CFG, _) -> hipe_x86_cfg:reverse_postorder(CFG). -breadthorder(CFG) -> +breadthorder(CFG, _) -> hipe_x86_cfg:breadthorder(CFG). -postorder(CFG) -> +postorder(CFG, _) -> hipe_x86_cfg:postorder(CFG). -is_global(_Reg) -> - false. +is_global(Reg, _) -> + hipe_amd64_registers:sse2_temp0() =:= Reg. -is_fixed(_Reg) -> +is_fixed(_Reg, _) -> false. -is_arg(_Reg) -> +is_arg(_Reg, _) -> false. --spec args(#cfg{}) -> []. -args(_CFG) -> +-spec args(#cfg{}, no_context) -> []. +args(_CFG, _) -> []. -non_alloc(_) -> +non_alloc(_, _) -> []. %% Liveness stuff -analyze(CFG) -> +analyze(CFG, _) -> hipe_amd64_liveness:analyze(CFG). -livein(Liveness, L) -> +livein(Liveness, L, _) -> [X || X <- hipe_amd64_liveness:livein(Liveness, L), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_type(X) =:= 'double']. -liveout(BB_in_out_liveness, Label) -> +liveout(BB_in_out_liveness, Label, _) -> [X || X <- hipe_amd64_liveness:liveout(BB_in_out_liveness, Label), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_type(X) =:= 'double']. %% Registers stuff -allocatable() -> - hipe_amd64_registers:allocatable_sse2(). +allocatable(Ctx) -> + allocatable('normal', Ctx). + +allocatable('normal', _) -> + hipe_amd64_registers:allocatable_sse2(); +allocatable('linearscan', _) -> + hipe_amd64_registers:allocatable_sse2() -- + [hipe_amd64_registers:sse2_temp0()]. + +temp0(_) -> + hipe_amd64_registers:sse2_temp0(). -all_precoloured() -> - allocatable(). +all_precoloured(Ctx) -> + allocatable(Ctx). -is_precoloured(Reg) -> - lists:member(Reg,all_precoloured()). +is_precoloured(Reg, _) -> + hipe_amd64_registers:is_precoloured_sse2(Reg). -physical_name(Reg) -> +physical_name(Reg, _) -> Reg. %% CFG stuff -labels(CFG) -> +labels(CFG, _) -> hipe_x86_cfg:labels(CFG). -var_range(_CFG) -> +var_range(_CFG, _) -> hipe_gensym:var_range(x86). --spec number_of_temporaries(#cfg{}) -> non_neg_integer(). -number_of_temporaries(_CFG) -> +-spec number_of_temporaries(#cfg{}, no_context) -> non_neg_integer(). +number_of_temporaries(_CFG, _) -> Highest_temporary = hipe_gensym:get_var(x86), %% Since we can have temps from 0 to Max adjust by +1. Highest_temporary + 1. -bb(CFG, L) -> +bb(CFG, L, _) -> hipe_x86_cfg:bb(CFG, L). +update_bb(CFG,L,BB,_) -> + hipe_x86_cfg:bb_add(CFG,L,BB). + +branch_preds(Instr,_) -> + hipe_x86_cfg:branch_preds(Instr). + %% AMD64 stuff -def_use(Instruction) -> +def_use(Instruction, _) -> {[X || X <- hipe_amd64_defuse:insn_def(Instruction), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_type(X) =:= 'double'], @@ -148,17 +174,19 @@ def_use(Instruction) -> hipe_x86:temp_type(X) =:= 'double'] }. -uses(I) -> +uses(I, _) -> [X || X <- hipe_amd64_defuse:insn_use(I), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_type(X) =:= 'double']. -defines(I) -> +defines(I, _) -> [X || X <- hipe_amd64_defuse:insn_def(I), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_type(X) =:= 'double']. -is_move(Instruction) -> +defines_all_alloc(I, _) -> hipe_amd64_defuse:insn_defs_all(I). + +is_move(Instruction, _) -> case hipe_x86:is_fmove(Instruction) of true -> Src = hipe_x86:fmove_src(Instruction), @@ -167,10 +195,51 @@ is_move(Instruction) -> andalso hipe_x86:is_temp(Dst) andalso hipe_x86:temp_is_allocatable(Dst); false -> false end. + +is_spill_move(Instruction,_) -> + hipe_x86:is_pseudo_spill_fmove(Instruction). -reg_nr(Reg) -> +reg_nr(Reg, _) -> hipe_x86:temp_reg(Reg). --spec new_spill_index(non_neg_integer()) -> pos_integer(). -new_spill_index(SpillIndex) when is_integer(SpillIndex) -> +mk_move(Src, Dst, _) -> + hipe_x86:mk_fmove(Src, Dst). + +mk_goto(Label, _) -> + hipe_x86:mk_jmp_label(Label). + +redirect_jmp(Jmp, ToOld, ToNew, _) when is_integer(ToOld), is_integer(ToNew) -> + Ref = make_ref(), + put(Ref, false), + I = hipe_x86_subst:insn_lbls( + fun(Tgt) -> + if Tgt =:= ToOld -> put(Ref, true), ToNew; + is_integer(Tgt) -> Tgt + end + end, Jmp), + true = erase(Ref), % Assert that something was rewritten + I. + +new_label(_) -> + hipe_gensym:get_next_label(x86). + +new_reg_nr(_) -> + hipe_gensym:get_next_var(x86). + +update_reg_nr(Nr, _Temp, _) -> + hipe_x86:mk_temp(Nr, 'double'). + +subst_temps(SubstFun, Instr, _) -> + hipe_amd64_subst:insn_temps( + fun(Op) -> + case hipe_x86:temp_is_allocatable(Op) + andalso hipe_x86:temp_type(Op) =:= 'double' + of + true -> SubstFun(Op); + false -> Op + end + end, Instr). + +-spec new_spill_index(non_neg_integer(), no_context) -> pos_integer(). +new_spill_index(SpillIndex, _) when is_integer(SpillIndex) -> SpillIndex + 1. diff --git a/lib/hipe/regalloc/hipe_amd64_specific_x87.erl b/lib/hipe/regalloc/hipe_amd64_specific_x87.erl index 2160e93d24..918f72f5f2 100644 --- a/lib/hipe/regalloc/hipe_amd64_specific_x87.erl +++ b/lib/hipe/regalloc/hipe_amd64_specific_x87.erl @@ -1,8 +1,3 @@ -%% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2004-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -14,8 +9,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% + -define(HIPE_AMD64, true). -include("hipe_x86_specific_x87.erl"). diff --git a/lib/hipe/regalloc/hipe_arm_specific.erl b/lib/hipe/regalloc/hipe_arm_specific.erl index 4e34cb1d99..7ebc6aa336 100644 --- a/lib/hipe/regalloc/hipe_arm_specific.erl +++ b/lib/hipe/regalloc/hipe_arm_specific.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2005-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,121 +11,138 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -module(hipe_arm_specific). %% for hipe_coalescing_regalloc: --export([number_of_temporaries/1 - ,analyze/1 - ,labels/1 - ,all_precoloured/0 - ,bb/2 - ,liveout/2 - ,reg_nr/1 - ,def_use/1 - ,is_move/1 - ,is_precoloured/1 - ,var_range/1 - ,allocatable/0 - ,non_alloc/1 - ,physical_name/1 - ,reverse_postorder/1 - ,livein/2 - ,uses/1 - ,defines/1 +-export([number_of_temporaries/2 + ,analyze/2 + ,labels/2 + ,all_precoloured/1 + ,bb/3 + ,liveout/3 + ,reg_nr/2 + ,def_use/2 + ,is_move/2 + ,is_spill_move/2 + ,is_precoloured/2 + ,var_range/2 + ,allocatable/1 + ,non_alloc/2 + ,physical_name/2 + ,reverse_postorder/2 + ,livein/3 + ,uses/2 + ,defines/2 + ,defines_all_alloc/2 ]). %% for hipe_graph_coloring_regalloc: --export([is_fixed/1]). +-export([is_fixed/2]). %% for hipe_ls_regalloc: --export([args/1, is_arg/1, is_global/1, new_spill_index/1]). --export([breadthorder/1, postorder/1]). +-export([args/2, is_arg/2, is_global/2, new_spill_index/2]). +-export([breadthorder/2, postorder/2]). %% callbacks for hipe_regalloc_loop --export([defun_to_cfg/1, - check_and_rewrite/2]). +-export([check_and_rewrite/3]). + +%% callbacks for hipe_regalloc_prepass, hipe_range_split +-export([mk_move/3, + mk_goto/2, + redirect_jmp/4, + new_label/1, + new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -defun_to_cfg(Defun) -> - hipe_arm_cfg:init(Defun). +%% callbacks for hipe_bb_weights, hipe_range_split +-export([branch_preds/2]). -check_and_rewrite(Defun, Coloring) -> - hipe_arm_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal'). +check_and_rewrite(CFG, Coloring, no_context) -> + hipe_arm_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal'). -reverse_postorder(CFG) -> +reverse_postorder(CFG, _) -> hipe_arm_cfg:reverse_postorder(CFG). -non_alloc(CFG) -> - non_alloc(hipe_arm_registers:nr_args(), hipe_arm_cfg:params(CFG)). +non_alloc(CFG, no_context) -> + non_alloc_1(hipe_arm_registers:nr_args(), hipe_arm_cfg:params(CFG)). %% same as hipe_arm_frame:fix_formals/2 -non_alloc(0, Rest) -> Rest; -non_alloc(N, [_|Rest]) -> non_alloc(N-1, Rest); -non_alloc(_, []) -> []. +non_alloc_1(0, Rest) -> Rest; +non_alloc_1(N, [_|Rest]) -> non_alloc_1(N-1, Rest); +non_alloc_1(_, []) -> []. %% Liveness stuff -analyze(CFG) -> +analyze(CFG, _) -> hipe_arm_liveness_gpr:analyse(CFG). -livein(Liveness,L) -> +livein(Liveness,L,_) -> [X || X <- hipe_arm_liveness_gpr:livein(Liveness,L), hipe_arm:temp_is_allocatable(X)]. -liveout(BB_in_out_liveness,Label) -> +liveout(BB_in_out_liveness,Label,_) -> [X || X <- hipe_arm_liveness_gpr:liveout(BB_in_out_liveness,Label), hipe_arm:temp_is_allocatable(X)]. %% Registers stuff -allocatable() -> +allocatable(no_context) -> hipe_arm_registers:allocatable_gpr(). -all_precoloured() -> +all_precoloured(no_context) -> hipe_arm_registers:all_precoloured(). -is_precoloured(Reg) -> +is_precoloured(Reg, _) -> hipe_arm_registers:is_precoloured_gpr(Reg). -is_fixed(R) -> +is_fixed(R, _) -> hipe_arm_registers:is_fixed(R). -physical_name(Reg) -> +physical_name(Reg, _) -> Reg. %% CFG stuff -labels(CFG) -> +labels(CFG, _) -> hipe_arm_cfg:labels(CFG). -var_range(_CFG) -> +var_range(_CFG, _) -> hipe_gensym:var_range(arm). -number_of_temporaries(_CFG) -> +number_of_temporaries(_CFG, _) -> Highest_temporary = hipe_gensym:get_var(arm), %% Since we can have temps from 0 to Max adjust by +1. Highest_temporary + 1. -bb(CFG,L) -> +bb(CFG,L,_) -> hipe_arm_cfg:bb(CFG,L). +update_bb(CFG,L,BB,_) -> + hipe_arm_cfg:bb_add(CFG,L,BB). + +branch_preds(Branch,_) -> + hipe_arm_cfg:branch_preds(Branch). + %% ARM stuff -def_use(Instruction) -> - {defines(Instruction), uses(Instruction)}. +def_use(Instruction, Ctx) -> + {defines(Instruction, Ctx), uses(Instruction, Ctx)}. -uses(I) -> +uses(I, _) -> [X || X <- hipe_arm_defuse:insn_use_gpr(I), hipe_arm:temp_is_allocatable(X)]. -defines(I) -> +defines(I, _) -> [X || X <- hipe_arm_defuse:insn_def_gpr(I), hipe_arm:temp_is_allocatable(X)]. -is_move(Instruction) -> +defines_all_alloc(I, _) -> + hipe_arm_defuse:insn_defs_all_gpr(I). + +is_move(Instruction, _) -> case hipe_arm:is_pseudo_move(Instruction) of true -> Dst = hipe_arm:pseudo_move_dst(Instruction), @@ -142,28 +155,67 @@ is_move(Instruction) -> false -> false end. -reg_nr(Reg) -> +is_spill_move(Instruction, _) -> + hipe_arm:is_pseudo_spill_move(Instruction). + +reg_nr(Reg, _) -> hipe_arm:temp_reg(Reg). +mk_move(Src, Dst, _) -> + hipe_arm:mk_pseudo_move(Dst, Src). + +mk_goto(Label, _) -> + hipe_arm:mk_b_label(Label). + +redirect_jmp(Jmp, ToOld, ToNew, _) when is_integer(ToOld), is_integer(ToNew) -> + Ref = make_ref(), + put(Ref, false), + I = hipe_arm_subst:insn_lbls( + fun(Tgt) -> + if Tgt =:= ToOld -> put(Ref, true), ToNew; + is_integer(Tgt) -> Tgt + end + end, Jmp), + true = erase(Ref), % Assert that something was rewritten + I. + +new_label(_) -> + hipe_gensym:get_next_label(arm). + +new_reg_nr(_) -> + hipe_gensym:get_next_var(arm). + +update_reg_nr(Nr, Temp, _) -> + hipe_arm:mk_temp(Nr, hipe_arm:temp_type(Temp)). + +subst_temps(SubstFun, Instr, _) -> + hipe_arm_subst:insn_temps( + fun(Op) -> + case hipe_arm:temp_is_allocatable(Op) of + true -> SubstFun(Op); + false -> Op + end + end, Instr). + %%% Linear Scan stuff -new_spill_index(SpillIndex) when is_integer(SpillIndex) -> +new_spill_index(SpillIndex, _) when is_integer(SpillIndex) -> SpillIndex+1. -breadthorder(CFG) -> +breadthorder(CFG, _) -> hipe_arm_cfg:breadthorder(CFG). -postorder(CFG) -> +postorder(CFG, _) -> hipe_arm_cfg:postorder(CFG). -is_global(R) -> +is_global(R, _) -> R =:= hipe_arm_registers:temp1() orelse R =:= hipe_arm_registers:temp2() orelse R =:= hipe_arm_registers:temp3() orelse hipe_arm_registers:is_fixed(R). -is_arg(R) -> +is_arg(R, _) -> hipe_arm_registers:is_arg(R). -args(CFG) -> +args(CFG, _) -> hipe_arm_registers:args(hipe_arm_cfg:arity(CFG)). diff --git a/lib/hipe/regalloc/hipe_coalescing_regalloc.erl b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl index e2f817d369..b8f0a1974c 100644 --- a/lib/hipe/regalloc/hipe_coalescing_regalloc.erl +++ b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,8 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% %% %%----------------------------------------------------------------------- %% File : hipe_coalescing_regalloc.erl @@ -30,7 +24,7 @@ %%----------------------------------------------------------------------- -module(hipe_coalescing_regalloc). --export([regalloc/5]). +-export([regalloc/7]). %%-ifndef(DEBUG). %%-define(DEBUG,true). @@ -51,19 +45,21 @@ %% %% Returns: %% Coloring -- A coloring for specified CFG -%% SpillIndex0 -- A new spill index +%% SpillIndex2 -- A new spill index %%----------------------------------------------------------------------- -regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> +regalloc(CFG, Liveness, SpillIndex, SpillLimit, TargetMod, TargetContext, + _Options) -> + Target = {TargetMod, TargetContext}, %% Build interference graph ?debug_msg("Build IG\n", []), - IG = hipe_ig:build(CFG, Target), + IG = hipe_ig:build(CFG, Liveness, TargetMod, TargetContext), %% io:format("IG: ~p\n", [IG]), ?debug_msg("Init\n", []), - Num_Temps = Target:number_of_temporaries(CFG), + Num_Temps = TargetMod:number_of_temporaries(CFG,TargetContext), ?debug_msg("Coalescing RA: num_temps = ~p~n", [Num_Temps]), - Allocatable = Target:allocatable(), + Allocatable = TargetMod:allocatable(TargetContext), K = length(Allocatable), All_colors = colset_from_list(Allocatable), @@ -72,7 +68,8 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> Move_sets = hipe_moves:new(IG), ?debug_msg("Build Worklist\n", []), - Worklists = hipe_reg_worklists:new(IG, Target, CFG, Move_sets, K, Num_Temps), + Worklists = hipe_reg_worklists:new(IG, TargetMod, TargetContext, CFG, + Move_sets, K, Num_Temps), Alias = initAlias(Num_Temps), ?debug_msg("Do coloring\n~p~n", [Worklists]), @@ -81,10 +78,10 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> %% io:format("SelStk0 ~w\n",[SelStk0]), ?debug_msg("Init node sets\n", []), Node_sets = hipe_node_sets:new(), - %% io:format("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,Target:non_alloc(CFG)]), + %% io:format("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,non_alloc(CFG,Target)]), ?debug_msg("Default coloring\n", []), {Color0,Node_sets1} = - defaultColoring(Target:all_precoloured(), + defaultColoring(TargetMod:all_precoloured(TargetContext), initColor(Num_Temps), Node_sets, Target), ?debug_msg("Assign colors\n", []), @@ -94,9 +91,10 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> %% io:format("color0:~w\nColor1:~w\nNodes:~w\nNodes2:~w\nNum_Temps:~w\n",[Color0,Color1,Node_sets,Node_sets2,Num_Temps]), ?debug_msg("Build mapping ~p\n", [Node_sets2]), - Coloring = build_namelist(Node_sets2, SpillIndex, Alias0, Color1), + {Coloring, SpillIndex2} = + build_namelist(Node_sets2, SpillIndex, Alias0, Color1), ?debug_msg("Coloring ~p\n", [Coloring]), - Coloring. + {Coloring, SpillIndex2}. %%---------------------------------------------------------------------- %% Function: do_coloring @@ -379,7 +377,7 @@ assignColors(Stack, NodeSets, Color, Alias, AllColors, Target) -> false -> % Colour case Col = colset_smallest(OkColors), NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), - Color1 = setColor(Node, Target:physical_name(Col), Color), + Color1 = setColor(Node, physical_name(Col,Target), Color), assignColors(Stack1, NodeSets1, Color1, Alias, AllColors, Target) end end. @@ -402,7 +400,7 @@ assignColors(Stack, NodeSets, Color, Alias, AllColors, Target) -> defaultColoring([], Color, NodeSets, _Target) -> {Color,NodeSets}; defaultColoring([Reg|Regs], Color, NodeSets, Target) -> - Color1 = setColor(Reg,Target:physical_name(Reg), Color), + Color1 = setColor(Reg,physical_name(Reg,Target), Color), NodeSets1 = hipe_node_sets:add_colored(Reg, NodeSets), defaultColoring(Regs, Color1, NodeSets1, Target). @@ -567,7 +565,7 @@ coalesce(Moves, IG, Worklists, Alias, K, Target) -> ?debug_msg("Testing nodes ~p and ~p for coalescing~n",[Dest,Source]), Alias_src = getAlias(Source, Alias), Alias_dst = getAlias(Dest, Alias), - {U,V} = case Target:is_precoloured(Alias_dst) of + {U,V} = case is_precoloured(Alias_dst,Target) of true -> {Alias_dst, Alias_src}; false -> {Alias_src, Alias_dst} end, @@ -577,7 +575,7 @@ coalesce(Moves, IG, Worklists, Alias, K, Target) -> Worklists1 = add_worklist(Worklists, U, K, Moves1, IG, Target), {Moves1, IG, Worklists1, Alias}; true -> - case (Target:is_precoloured(V) orelse + case (is_precoloured(V,Target) orelse hipe_ig:nodes_are_adjacent(U, V, IG)) of true -> Moves1 = Moves0, % drop constrained move Move @@ -585,7 +583,7 @@ coalesce(Moves, IG, Worklists, Alias, K, Target) -> Worklists2 = add_worklist(Worklists1, V, K, Moves1, IG, Target), {Moves1, IG, Worklists2, Alias}; false -> - case (case Target:is_precoloured(U) of + case (case is_precoloured(U,Target) of true -> AdjV = hipe_ig:node_adj_list(V, IG), all_adjacent_ok(AdjV, U, Worklists, IG, K, Target); @@ -627,7 +625,7 @@ coalesce(Moves, IG, Worklists, Alias, K, Target) -> %%---------------------------------------------------------------------- add_worklist(Worklists, U, K, Moves, IG, Target) -> - case (not(Target:is_precoloured(U)) + case (not(is_precoloured(U,Target)) andalso not(hipe_moves:move_related(U, Moves)) andalso (hipe_ig:is_trivially_colourable(U, K, IG))) of true -> @@ -711,7 +709,7 @@ combine(U, V, IG, Worklists, Moves, Alias, K, Target) -> combine_edges([], _U, IG, Worklists, Moves, _K, _Target) -> {IG, Worklists, Moves}; -combine_edges([T|Ts], U, IG, Worklists, Moves, K, Target) -> +combine_edges([T|Ts], U, IG, Worklists, Moves, K, Target={TgtMod,TgtCtx}) -> case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of true -> combine_edges(Ts, U, IG, Worklists, Moves, K, Target); _ -> @@ -728,7 +726,7 @@ combine_edges([T|Ts], U, IG, Worklists, Moves, K, Target) -> %% worklist, and that's where decrement_degree() expects to find it. %% This issue is not covered in the published algorithm. OldDegree = hipe_ig:get_node_degree(T, IG), - IG1 = hipe_ig:add_edge(T, U, IG, Target), + IG1 = hipe_ig:add_edge(T, U, IG, TgtMod, TgtCtx), NewDegree = hipe_ig:get_node_degree(T, IG1), Worklists0 = if NewDegree =:= K, OldDegree =:= K-1 -> @@ -767,7 +765,7 @@ combine_edges([T|Ts], U, IG, Worklists, Moves, K, Target) -> ok(T, R, IG, K, Target) -> ((hipe_ig:is_trivially_colourable(T, K, IG)) - orelse Target:is_precoloured(T) + orelse is_precoloured(T,Target) orelse hipe_ig:nodes_are_adjacent(T, R, IG)). %%---------------------------------------------------------------------- @@ -916,7 +914,7 @@ findCheapest([Node|Nodes], IG, Cost, Cheapest, SpillLimit) -> %% limit are extremely expensive. getCost(Node, IG, SpillLimit) -> - case Node > SpillLimit of + case Node >= SpillLimit of true -> inf; false -> hipe_ig:node_spill_cost(Node, IG) end. @@ -1028,3 +1026,15 @@ freezeEm3(_U, V, _M, K, WorkLists, Moves, IG, _Alias) -> false -> {WorkLists, Moves1} end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Interface to external functions. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +is_precoloured(R, {TgtMod,TgtCtx}) -> + TgtMod:is_precoloured(R,TgtCtx). + +physical_name(R, {TgtMod,TgtCtx}) -> + TgtMod:physical_name(R,TgtCtx). diff --git a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl index bc6e442236..f82d3a2cbc 100644 --- a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl +++ b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,8 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%@doc @@ -51,7 +45,7 @@ %% -module(hipe_graph_coloring_regalloc). --export([regalloc/5]). +-export([regalloc/7]). %%-ifndef(DO_ASSERT). %%-define(DO_ASSERT, true). @@ -77,18 +71,21 @@ %% 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(), +%% module(), tgt_ctx(), list()) -> {, non_neg_fixnum()} -regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> - PhysRegs = Target:allocatable(), +regalloc(CFG, Live, SpillIndex, SpillLimit, TargetMod, TargetContext, + _Options) -> + Target = {TargetMod, TargetContext}, + PhysRegs = allocatable(Target), ?report2("building IG~n", []), - {IG, Spill} = 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]), %% These nodes *can't* be allocated to registers. - NotAllocatable = [Target:reg_nr(X) || X <- Target:non_alloc(CFG)], + NotAllocatable = non_alloc(CFG, Target), %% i.e. Arguments on x86 ?report2("Nonalloc ~w~n", [NotAllocatable]), @@ -97,7 +94,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ordsets:from_list(PhysRegs), SpillIndex, SpillLimit, - Target:number_of_temporaries(CFG), + number_of_temporaries(CFG, Target), Target, NotAllocatable), Coloring = [{X, {reg, X}} || X <- NotAllocatable] ++ Cols, ?ASSERT(check_coloring(Coloring, IG, Target)), @@ -112,15 +109,9 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> %% Returns {Interference_graph, Spill_cost_dictionary} %% -build_ig(CFG, Target) -> - try build_ig0(CFG, Target) - catch error:Rsn -> exit({?MODULE, build_ig, Rsn}) - end. - -build_ig0(CFG, Target) -> - Live = Target:analyze(CFG), - NumN = Target:number_of_temporaries(CFG), % poss. N-1? - {IG, Spill} = build_ig_bbs(Target:labels(CFG), +build_ig(CFG, Live, Target) -> + NumN = number_of_temporaries(CFG, Target), % poss. N-1? + {IG, Spill} = build_ig_bbs(labels(CFG, Target), CFG, Live, empty_ig(NumN), @@ -208,17 +199,8 @@ set_spill_cost(X, N, Spill) -> %% * add low-degree neighbors of z to low %% * restart the while-loop above -color(IG, Spill, PhysRegs, SpillIx, SpillLimit, NumNodes, Target, NotAllocatable) -> - try color_0(IG, Spill, PhysRegs, SpillIx, SpillLimit, - NumNodes, Target, NotAllocatable) - catch - error:Rsn -> - ?error_msg("Coloring failed with ~p~n", [Rsn]), - ?EXIT(Rsn) - end. - -color_0(IG, Spill, PhysRegs, SpillIx, SpillLimit, NumNodes, Target, - NotAllocatable) -> +color(IG, Spill, PhysRegs, SpillIx, SpillLimit, NumNodes, Target, + NotAllocatable) -> ?report("simplification of IG~n", []), K = ordsets:size(PhysRegs), Nodes = list_ig(IG), @@ -227,14 +209,14 @@ color_0(IG, Spill, PhysRegs, SpillIx, SpillLimit, NumNodes, Target, %% Any nodes above the spillimit must be colored first... MustNotSpill = - if NumNodes > SpillLimit+1 -> - sort_on_degree(lists:seq(SpillLimit+1,NumNodes-1) -- Low,IG); + if NumNodes > SpillLimit -> + sort_on_degree(lists:seq(SpillLimit,NumNodes-1) -- Low,IG); true -> [] end, ?report(" starting with low degree nodes ~p~n",[Low]), EmptyStk = [], - Precolored = Target:all_precoloured(), + Precolored = all_precoloured(Target), {Stk, NewSpillIx} = simplify(Low, NumNodes, Precolored, IG, Spill, K, SpillIx, EmptyStk, @@ -415,11 +397,11 @@ spill_costs([{N,Info}|Ns], IG, Vis, Spill, SpillLimit, Target) -> true -> spill_costs(Ns,IG,Vis,Spill, SpillLimit, Target); _ -> - case Target:is_fixed(N) of + case is_fixed(N, Target) of true -> spill_costs(Ns, IG, Vis, Spill, SpillLimit, Target); false -> - if N > SpillLimit -> + if N >= SpillLimit -> spill_costs(Ns, IG, Vis, Spill, SpillLimit, Target); true -> [{spill_cost_of(N,Spill)/Deg,N} | @@ -772,18 +754,36 @@ valid_coloring(X, C, [_|Ys]) -> %% *** INTERFACES TO OTHER MODULES *** %% -liveout(CFG, L, Target) -> - ordsets:from_list(reg_names(Target:liveout(CFG, L), Target)). +all_precoloured({TgtMod,TgtCtx}) -> + TgtMod:all_precoloured(TgtCtx). + +allocatable({TgtMod,TgtCtx}) -> + TgtMod:allocatable(TgtCtx). + +is_fixed(Reg, {TgtMod,TgtCtx}) -> + TgtMod:is_fixed(Reg, TgtCtx). + +labels(CFG, {TgtMod,TgtCtx}) -> + TgtMod:labels(CFG, TgtCtx). + +liveout(CFG, L, Target={TgtMod,TgtCtx}) -> + ordsets:from_list(reg_names(TgtMod:liveout(CFG, L, TgtCtx), Target)). + +bb(CFG, L, {TgtMod,TgtCtx}) -> + hipe_bb:code(TgtMod:bb(CFG, L, TgtCtx)). + +def_use(X, Target={TgtMod,TgtCtx}) -> + {ordsets:from_list(reg_names(TgtMod:defines(X,TgtCtx), Target)), + ordsets:from_list(reg_names(TgtMod:uses(X,TgtCtx), Target))}. -bb(CFG, L, Target) -> - hipe_bb:code(Target:bb(CFG, L)). +non_alloc(CFG, Target={TgtMod,TgtCtx}) -> + reg_names(TgtMod:non_alloc(CFG, TgtCtx), Target). -def_use(X, Target) -> - {ordsets:from_list(reg_names(Target:defines(X), Target)), - ordsets:from_list(reg_names(Target:uses(X), Target))}. +number_of_temporaries(CFG, {TgtMod,TgtCtx}) -> + TgtMod:number_of_temporaries(CFG, TgtCtx). -reg_names(Regs, Target) -> - [Target:reg_nr(X) || X <- Regs]. +reg_names(Regs, {TgtMod,TgtCtx}) -> + [TgtMod:reg_nr(X,TgtCtx) || X <- Regs]. %% %% Precoloring: use this version when a proper implementation of @@ -803,5 +803,5 @@ precolor0([R|Rs], Cols, Target) -> {[{R, {reg, physical_name(R, Target)}}|Cs], set_color(R, physical_name(R, Target), Cols1)}. -physical_name(X, Target) -> - Target:physical_name(X). +physical_name(X, {TgtMod,TgtCtx}) -> + TgtMod:physical_name(X, TgtCtx). diff --git a/lib/hipe/regalloc/hipe_ig.erl b/lib/hipe/regalloc/hipe_ig.erl index 8fd5d0df1f..14a1ae77f2 100644 --- a/lib/hipe/regalloc/hipe_ig.erl +++ b/lib/hipe/regalloc/hipe_ig.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,8 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% %% %%---------------------------------------------------------------------- %% File : hipe_ig.erl @@ -28,7 +22,7 @@ -module(hipe_ig). --export([build/2, +-export([build/4, nodes_are_adjacent/3, node_spill_cost/2, node_adj_list/2, @@ -38,8 +32,8 @@ spill_costs/1, adj_list/1, %% adj_set/1, - add_edge/4, - remove_edge/4, + add_edge/5, + remove_edge/5, %% set_adj_set/2, %% set_adj_list/2, %% set_ig_moves/2, @@ -64,6 +58,9 @@ -include("../flow/cfg.hrl"). -include("hipe_spillcost.hrl"). +-type target_context() :: any(). +-type target() :: {TargetMod :: module(), TargetContext :: target_context()}. + %%---------------------------------------------------------------------- -record(igraph, {adj_set, adj_list, ig_moves, degree, @@ -78,11 +75,11 @@ %% degree, and testing for trivial colourability (degree < K). %%---------------------------------------------------------------------- -degree_new(No_temporaries, Target) -> +degree_new(No_temporaries, {TargetMod, TargetCtx}) -> Degree = hipe_bifs:array(No_temporaries, 0), - K = length(Target:allocatable()), + K = length(TargetMod:allocatable(TargetCtx)), Inf = K + No_temporaries, - precoloured_to_inf_degree(Target:all_precoloured(), Inf, Degree). + precoloured_to_inf_degree(TargetMod:all_precoloured(TargetCtx), Inf, Degree). precoloured_to_inf_degree([], _Inf, Degree) -> Degree; precoloured_to_inf_degree([P|Ps], Inf, Degree) -> @@ -344,7 +341,7 @@ set_spill_costs(Spill_costs, IG) -> IG#igraph{spill_costs = Spill_costs}. %% A new interference record %%---------------------------------------------------------------------- --spec initial_ig(non_neg_integer(), atom()) -> #igraph{}. +-spec initial_ig(non_neg_integer(), target()) -> #igraph{}. initial_ig(NumTemps, Target) -> #igraph{adj_set = adjset_new(NumTemps), @@ -361,20 +358,21 @@ initial_ig(NumTemps, Target) -> %% Description: Constructs an interference graph for the specifyed CFG. %% %% Parameters: -%% CFG -- A Control Flow Graph -%% Target -- The module that contains the target-specific functions +%% CFG -- A Control Flow Graph +%% TargetMod -- The module that contains the target-specific functions +%% TargetCtx -- Context data to pass to TargetMod %% %% Returns: %% An interference graph for the given CFG. %%---------------------------------------------------------------------- --spec build(#cfg{}, atom()) -> #igraph{}. +-spec build(#cfg{}, Liveness::_, module(), target_context()) -> #igraph{}. -build(CFG, Target) -> - BBs_in_out_liveness = Target:analyze(CFG), - Labels = Target:labels(CFG), +build(CFG, BBs_in_out_liveness, TargetMod, TargetCtx) -> + Target = {TargetMod, TargetCtx}, + Labels = TargetMod:labels(CFG, TargetCtx), %% How many temporaries exist? - NumTemps = Target:number_of_temporaries(CFG), + NumTemps = TargetMod:number_of_temporaries(CFG, TargetCtx), IG0 = initial_ig(NumTemps, Target), %%?debug_msg("initial adjset: ~p\n",[element(2, IG0)]), %%?debug_msg("initial adjset array: ~.16b\n",[element(3, element(2, IG0))]), @@ -395,7 +393,7 @@ build(CFG, Target) -> %% CFG -- The Control Flow Graph that we constructs %% the interference graph from. %% Target -- The module containing the target-specific -%% functions +%% functions, along with its context data %% %% Returns: %% An interference graph for the given CFG. @@ -404,13 +402,11 @@ build(CFG, Target) -> analyze_bbs([], _, IG, _, _) -> IG; analyze_bbs([L|Ls], BBs_in_out_liveness, IG, CFG, Target) -> % Get basic block associated with label L - BB = Target:bb(CFG, L), + BB = bb(CFG, L, Target), % Get basic block code BB_code = hipe_bb:code(BB), - % Temporaries that are live out from this basic block - BB_liveout = Target:liveout(BBs_in_out_liveness, L), - % Only temporary numbers - BB_liveout_numbers = reg_numbers(BB_liveout, Target), + % Temporaries that are live out from this basic block, only numbers + BB_liveout_numbers = liveout(BBs_in_out_liveness, L, Target), % {Liveness, New Interference Graph} {_, New_ig, Ref} = analyze_bb_instructions(BB_code, ordsets:from_list(BB_liveout_numbers), @@ -433,7 +429,8 @@ analyze_bbs([L|Ls], BBs_in_out_liveness, IG, CFG, Target) -> %% Live -- All temporaries that are live at the time. %% Live is a set of temporary "numbers only". %% IG -- The interference graph in it's current state -%% Target -- The mopdule containing the target-specific functions +%% Target -- The mopdule containing the target-specific functions, +%% along with its context data. %% %% Returns: %% Live -- Temporaries that are live at entery of basic block @@ -449,7 +446,7 @@ analyze_bb_instructions([Instruction|Instructions], Live, IG, Target) -> {Live0, IG0, Ref} = analyze_bb_instructions(Instructions, Live, IG, Target), %% Check for temporaries that are defined and used in instruction - {Def, Use} = Target:def_use(Instruction), + {Def, Use} = def_use(Instruction, Target), %% Convert to register numbers Def_numbers = ordsets:from_list(reg_numbers(Def, Target)), Use_numbers = ordsets:from_list(reg_numbers(Use, Target)), @@ -501,14 +498,15 @@ analyze_bb_instructions([Instruction|Instructions], Live, IG, Target) -> %% Def_numbers -- Temporaries that are defined at this instruction %% Use_numbers -- Temporaries that are used at this instruction %% IG -- The interference graph in its current state -%% Target -- The module containing the target-specific functions +%% Target -- The module containing the target-specific functions, along +%% with its context data %% Returns: %% Live -- An updated live set %% IG -- An updated interference graph %%---------------------------------------------------------------------- analyze_move(Instruction, Live, Def_numbers, Use_numbers, IG, Target) -> - case Target:is_move(Instruction) of + case is_move(Instruction,Target) of true -> case {Def_numbers, Use_numbers} of {[Dst], [Src]} -> @@ -554,8 +552,9 @@ interfere([Define|Defines], Living, IG, Target) -> %% Live -- Current live set %% Lives -- Rest of living temporaries. %% IG -- An interference graph -%% Target -- The module containing the target-specific functions -%% Returns: +%% Target -- The module containing the target-specific functions, along +%% with its context data. +%% Returns: %% An updated interference graph %%---------------------------------------------------------------------- @@ -623,11 +622,15 @@ get_moves(IG) -> %% Parameters: %% U -- A temporary number %% V -- A temporary number -%% Target -- The module containing the target-specific functions +%% TargetMod -- The module containing the target-specific functions. +%% TargetCtx -- Context data to pass to TargetMod %% Returns: %% An updated interference graph. %%---------------------------------------------------------------------- +add_edge(U, V, IG, TargetMod, TargetCtx) -> + add_edge(U, V, IG, {TargetMod, TargetCtx}). + add_edge(U, U, IG, _) -> IG; add_edge(U, V, IG, Target) -> case nodes_are_adjacent(U, V, IG) of @@ -652,11 +655,15 @@ add_edge(U, V, IG, Target) -> %% Parameters: %% U -- A temporary number %% V -- A temporary number -%% Target -- The module containing the target-specific functions +%% TargetMod -- The module containing the target-specific functions. +%% TargetCtx -- Context data for TargetMod. %% Returns: %% An updated interference graph. %%---------------------------------------------------------------------- +remove_edge(U, V, IG, TargetMod, TargetCtx) -> + remove_edge(U, V, IG, {TargetMod, TargetCtx}). + remove_edge(U, U, IG, _) -> IG; remove_edge(U, V, IG, Target) -> case nodes_are_adjacent(U, V, IG) of @@ -683,8 +690,8 @@ remove_edge(U, V, IG, Target) -> %% precoloured. %% Adj_list -- An adj_list %% Degree -- The degree that all nodes currently have -%% Target -- The module containing the target-specific -%% functions +%% Target -- The module containing the target-specific +%% functions, along with its context data. %% %% Returns: %% Adj_list -- An updated adj_list data structure @@ -692,7 +699,7 @@ remove_edge(U, V, IG, Target) -> %%---------------------------------------------------------------------- remove_if_uncolored(Temp, InterfereTemp, Adj_list, Degree, Target) -> - case Target:is_precoloured(Temp) of + case is_precoloured(Temp,Target) of false -> New_adj_list = hipe_adj_list:remove_edge(Temp, InterfereTemp, Adj_list), degree_dec(Temp, Degree), @@ -714,8 +721,8 @@ remove_if_uncolored(Temp, InterfereTemp, Adj_list, Degree, Target) -> %% precoloured. %% Adj_list -- An adj_list %% Degree -- The degree that all nodes currently have -%% Target -- The module containing the target-specific -%% functions +%% Target -- The module containing the target-specific +%% functions, along with its context data. %% %% Returns: %% Adj_list -- An updated adj_list data structure @@ -723,7 +730,7 @@ remove_if_uncolored(Temp, InterfereTemp, Adj_list, Degree, Target) -> %%---------------------------------------------------------------------- interfere_if_uncolored(Temp, InterfereTemp, Adj_list, Degree, Target) -> - case Target:is_precoloured(Temp) of + case is_precoloured(Temp, Target) of false -> New_adj_list = hipe_adj_list:add_edge(Temp, InterfereTemp, Adj_list), degree_inc(Temp, Degree), @@ -740,13 +747,14 @@ interfere_if_uncolored(Temp, InterfereTemp, Adj_list, Degree, Target) -> %% %% Parameters: %% TRs -- A list of temporary registers -%% Target -- The module containing the target-specific functions +%% Target -- The module containing the target-specific functions, along with +%% its context data. %% Returns: %% A list of register numbers. %%---------------------------------------------------------------------- -reg_numbers(Regs, Target) -> - [Target:reg_nr(X) || X <- Regs]. +reg_numbers(Regs, {TgtMod, TgtCtx}) -> + [TgtMod:reg_nr(X,TgtCtx) || X <- Regs]. %%--------------------------------------------------------------------- %% Print functions - only used for debugging @@ -775,3 +783,24 @@ dec_node_degree(Node, IG) -> is_trivially_colourable(Node, K, IG) -> degree_is_trivially_colourable(Node, K, degree(IG)). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Interface to external functions. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +bb(CFG, L, {TgtMod,TgtCtx}) -> + TgtMod:bb(CFG,L,TgtCtx). + +def_use(Instruction, {TgtMod,TgtCtx}) -> + TgtMod:def_use(Instruction, TgtCtx). + +is_move(Instruction, {TgtMod,TgtCtx}) -> + TgtMod:is_move(Instruction, TgtCtx). + +is_precoloured(R, {TgtMod,TgtCtx}) -> + TgtMod:is_precoloured(R,TgtCtx). + +liveout(Liveness,L, Target={TgtMod,TgtCtx}) -> + reg_numbers(TgtMod:liveout(Liveness,L,TgtCtx), Target). diff --git a/lib/hipe/regalloc/hipe_ig_moves.erl b/lib/hipe/regalloc/hipe_ig_moves.erl index b679453de0..e193a682bf 100644 --- a/lib/hipe/regalloc/hipe_ig_moves.erl +++ b/lib/hipe/regalloc/hipe_ig_moves.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,8 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% %% %%============================================================================= @@ -25,8 +19,6 @@ new_move/3, get_moves/1]). --include("../util/hipe_vectors.hrl"). - %%----------------------------------------------------------------------------- %% The main data structure; its fields are: %% - movelist : mapping from temp to set of associated move numbers @@ -34,11 +26,13 @@ %% - moveinsns : list of move instructions, in descending move number order %% - moveset : set of move instructions --record(ig_moves, {movelist :: hipe_vector(), +-record(ig_moves, {movelist :: movelist(), nrmoves = 0 :: non_neg_integer(), moveinsns = [] :: [{_,_}], moveset = gb_sets:empty() :: gb_sets:set()}). +-type movelist() :: hipe_vectors:vector(ordsets:ordset(non_neg_integer())). + %%----------------------------------------------------------------------------- -spec new(non_neg_integer()) -> #ig_moves{}. @@ -66,7 +60,8 @@ new_move(Dst, Src, IG_moves) -> moveset = gb_sets:insert(MoveInsn, MoveSet)} end. --spec add_movelist(non_neg_integer(), non_neg_integer(), hipe_vector()) -> hipe_vector(). +-spec add_movelist(non_neg_integer(), non_neg_integer(), movelist()) + -> movelist(). add_movelist(MoveNr, Temp, MoveList) -> AssocMoves = hipe_vectors:get(MoveList, Temp), @@ -74,7 +69,7 @@ add_movelist(MoveNr, Temp, MoveList) -> %% ordset due to the ordsets:union in hipe_coalescing_regalloc:combine(). hipe_vectors:set(MoveList, Temp, ordsets:add_element(MoveNr, AssocMoves)). --spec get_moves(#ig_moves{}) -> {hipe_vector(), non_neg_integer(), tuple()}. +-spec get_moves(#ig_moves{}) -> {movelist(), non_neg_integer(), tuple()}. get_moves(IG_moves) -> % -> {MoveList, NrMoves, MoveInsns} {IG_moves#ig_moves.movelist, diff --git a/lib/hipe/regalloc/hipe_ls_regalloc.erl b/lib/hipe/regalloc/hipe_ls_regalloc.erl index d24b803524..785aa2b080 100644 --- a/lib/hipe/regalloc/hipe_ls_regalloc.erl +++ b/lib/hipe/regalloc/hipe_ls_regalloc.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,8 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% %% %% ===================================================================== %% @doc @@ -56,7 +50,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -module(hipe_ls_regalloc). --export([regalloc/7]). +-export([regalloc/9]). %%-define(DEBUG,1). -define(HIPE_INSTRUMENT_COMPILER, true). @@ -95,11 +89,10 @@ %% </ol> %% @end %%- - - - - - - - - - - - - - - - - - - - - - - - -regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) -> +regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, + TargetMod, TargetContext) -> + Target = {TargetMod, TargetContext}, ?debug_msg("LinearScan: ~w\n", [erlang:statistics(runtime)]), - %% Step 1: Calculate liveness (Call external implementation.) - Liveness = liveness(CFG, Target), - ?debug_msg("liveness (done)~w\n", [erlang:statistics(runtime)]), USIntervals = calculate_intervals(CFG, Liveness, Entrypoints, Options, Target), ?debug_msg("intervals (done) ~w\n", [erlang:statistics(runtime)]), @@ -108,10 +101,10 @@ regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) -> %% ?debug_msg("Intervals ~w\n", [Intervals]), ?debug_msg("No intervals: ~w\n",[length(Intervals)]), ?debug_msg("count intervals (done) ~w\n", [erlang:statistics(runtime)]), - Allocation = allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target), + {Coloring, NewSpillIndex} + = allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target), ?debug_msg("allocation (done) ~w\n", [erlang:statistics(runtime)]), - Allocation. - + {Coloring, NewSpillIndex}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% @@ -125,32 +118,33 @@ regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) -> %% Liveness: A map of live-in and live-out sets for each Basic-Block. %% Entrypoints: A set of BB names that have external entrypoints. %% -calculate_intervals(CFG,Liveness,_Entrypoints, Options, Target) -> +calculate_intervals(CFG,Liveness,_Entrypoints, Options, + Target={TgtMod,TgtCtx}) -> %% Add start point for the argument registers. Args = arg_vars(CFG, Target), Interval = - add_def_point(Args, 0, empty_interval(Target:number_of_temporaries(CFG))), + add_def_point(Args, 0, empty_interval(number_of_temporaries(CFG, Target))), %% Interval = add_livepoint(Args, 0, empty_interval()), Worklist = case proplists:get_value(ls_order, Options) of reversepostorder -> - Target:reverse_postorder(CFG); + TgtMod:reverse_postorder(CFG, TgtCtx); breadth -> - Target:breadthorder(CFG); + TgtMod:breadthorder(CFG, TgtCtx); postorder -> - Target:postorder(CFG); + TgtMod:postorder(CFG, TgtCtx); inorder -> - Target:inorder(CFG); + TgtMod:inorder(CFG, TgtCtx); reverse_inorder -> - Target:reverse_inorder(CFG); + TgtMod:reverse_inorder(CFG, TgtCtx); preorder -> - Target:preorder(CFG); + TgtMod:preorder(CFG, TgtCtx); prediction -> - Target:predictionorder(CFG); + TgtMod:predictionorder(CFG, TgtCtx); random -> - Target:labels(CFG); + TgtMod:labels(CFG, TgtCtx); _ -> - Target:reverse_postorder(CFG) + TgtMod:reverse_postorder(CFG, TgtCtx) end, %% ?inc_counter(bbs_counter, length(Worklist)), %% ?debug_msg("No BBs ~w\n",[length(Worklist)]), @@ -290,7 +284,7 @@ allocate([RegInt|RIS], Free, Active, Alloc, SpillIndex, DontSpill, Target) -> alloc(OtherTemp,NewPhys,NewAlloc), SpillIndex, DontSpill, Target); false -> - NewSpillIndex = Target:new_spill_index(SpillIndex), + NewSpillIndex = new_spill_index(SpillIndex, Target), {NewAlloc2, NewActive4} = spill(OtherTemp, OtherEnd, OtherStart, NewActive3, NewAlloc, SpillIndex, DontSpill, Target), @@ -306,7 +300,7 @@ allocate([RegInt|RIS], Free, Active, Alloc, SpillIndex, DontSpill, Target) -> case NewFree of [] -> %% No physical registers available, we have to spill. - NewSpillIndex = Target:new_spill_index(SpillIndex), + NewSpillIndex = new_spill_index(SpillIndex, Target), {NewAlloc, NewActive2} = spill(Temp, endpoint(RegInt), startpoint(RegInt), Active, Alloc, SpillIndex, DontSpill, Target), @@ -752,38 +746,41 @@ create_freeregs([]) -> %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -liveness(CFG, Target) -> - Target:analyze(CFG). +bb(CFG, L, {TgtMod, TgtCtx}) -> + TgtMod:bb(CFG,L,TgtCtx). + +livein(Liveness,L, Target={TgtMod,TgtCtx}) -> + regnames(TgtMod:livein(Liveness,L,TgtCtx), Target). -bb(CFG, L, Target) -> - Target:bb(CFG,L). +liveout(Liveness,L, Target={TgtMod,TgtCtx}) -> + regnames(TgtMod:liveout(Liveness,L,TgtCtx), Target). -livein(Liveness,L, Target) -> - regnames(Target:livein(Liveness,L), Target). +uses(I, Target={TgtMod,TgtCtx}) -> + regnames(TgtMod:uses(I,TgtCtx), Target). -liveout(Liveness,L, Target) -> - regnames(Target:liveout(Liveness,L), Target). +defines(I, Target={TgtMod,TgtCtx}) -> + regnames(TgtMod:defines(I,TgtCtx), Target). -uses(I, Target) -> - regnames(Target:uses(I), Target). +is_precoloured(R, {TgtMod,TgtCtx}) -> + TgtMod:is_precoloured(R,TgtCtx). -defines(I, Target) -> - regnames(Target:defines(I), Target). +is_global(R, {TgtMod,TgtCtx}) -> + TgtMod:is_global(R,TgtCtx). -is_precoloured(R, Target) -> - Target:is_precoloured(R). +new_spill_index(SpillIndex, {TgtMod,TgtCtx}) -> + TgtMod:new_spill_index(SpillIndex, TgtCtx). -is_global(R, Target) -> - Target:is_global(R). +number_of_temporaries(CFG, {TgtMod,TgtCtx}) -> + TgtMod:number_of_temporaries(CFG, TgtCtx). -physical_name(R, Target) -> - Target:physical_name(R). +physical_name(R, {TgtMod,TgtCtx}) -> + TgtMod:physical_name(R,TgtCtx). -regnames(Regs, Target) -> - [Target:reg_nr(X) || X <- Regs]. +regnames(Regs, {TgtMod,TgtCtx}) -> + [TgtMod:reg_nr(X,TgtCtx) || X <- Regs]. -arg_vars(CFG, Target) -> - Target:args(CFG). +arg_vars(CFG, {TgtMod,TgtCtx}) -> + TgtMod:args(CFG,TgtCtx). -is_arg(Reg, Target) -> - Target:is_arg(Reg). +is_arg(Reg, {TgtMod,TgtCtx}) -> + TgtMod:is_arg(Reg,TgtCtx). diff --git a/lib/hipe/regalloc/hipe_moves.erl b/lib/hipe/regalloc/hipe_moves.erl index 39ccfb4a2f..409217bb03 100644 --- a/lib/hipe/regalloc/hipe_moves.erl +++ b/lib/hipe/regalloc/hipe_moves.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,9 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -module(hipe_moves). -export([new/1, diff --git a/lib/hipe/regalloc/hipe_node_sets.erl b/lib/hipe/regalloc/hipe_node_sets.erl index 01922a34d4..3cdfb62090 100644 --- a/lib/hipe/regalloc/hipe_node_sets.erl +++ b/lib/hipe/regalloc/hipe_node_sets.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,9 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -module(hipe_node_sets). diff --git a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl index 2ed9ec3b45..a019c46b90 100644 --- a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl +++ b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2005-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,8 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% %% %%----------------------------------------------------------------------- %% File : hipe_optimistic_regalloc.erl @@ -29,7 +23,7 @@ %%----------------------------------------------------------------------- -module(hipe_optimistic_regalloc). --export([regalloc/5]). +-export([regalloc/7]). -ifndef(DEBUG). %%-define(DEBUG,true). @@ -74,20 +68,22 @@ %% SpillLimit -- Temporaris with numbers higher than this have %% infinit spill cost. %% Consider changing this to a set. -%% Target -- The module containing the target-specific functions. +%% TgtMod -- The module containing the target-specific functions. +%% TgtCtx -- Context data for TgtMod %% %% Returns: %% Coloring -- A coloring for specified CFG -%% SpillIndex0 -- A new spill index +%% SpillIndex2 -- A new spill index %%----------------------------------------------------------------------- -ifdef(COMPARE_ITERATED_OPTIMISTIC). -regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> - ?debug_msg("optimistic ~w\n",[Target]), +regalloc(CFG, Liveness, SpillIndex, SpillLimit, TgtMod, TgtCtx, _Options) -> + Target = {TgtMod, TgtCtx}, + ?debug_msg("optimistic ~w\n",[TgtMod]), ?debug_msg("CFG: ~p\n",[CFG]), %% Build interference graph ?debug_msg("Build IG\n",[]), - IG_O = hipe_ig:build(CFG, Target), - IG = hipe_ig:build(CFG, Target), + IG_O = hipe_ig:build(CFG, Liveness, TgtMod, TgtCtx), + IG = hipe_ig:build(CFG, Liveness, TgtMod, TgtCtx), ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]), ?debug_msg("IG:\n",[]), ?print_adjacent(IG), @@ -98,9 +94,9 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> SavedAdjList = hipe_ig:adj_list(IG), ?debug_msg("Init\n",[]), - No_temporaries = Target:number_of_temporaries(CFG), + No_temporaries = number_of_temporaries(CFG, Target), ?debug_msg("Coalescing RA: num_temps = ~p~n", [No_temporaries]), - Allocatable = Target:allocatable(), + Allocatable = allocatable(Target), K = length(Allocatable), All_colors = colset_from_list(Allocatable), ?debug_msg("K: ~w~nAll_colors: ~p\n",[K, All_colors]), @@ -113,11 +109,13 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ?mov_print_memberships(Move_sets), ?debug_msg("Build Worklist\n",[]), - Worklists_O = hipe_reg_worklists:new(IG_O, Target, CFG, Move_sets_O, K, No_temporaries), + Worklists_O = hipe_reg_worklists:new(IG_O, TgtMod, TgtCtx, CFG, Move_sets_O, + K, No_temporaries), ?debug_msg("Worklists:\n ~p\n", [Worklists_O]), ?reg_print_memberships(Worklists_O), - Worklists = hipe_reg_worklists:new(IG, Target, CFG, K, No_temporaries), + Worklists = hipe_reg_worklists:new(IG, TgtMod, TgtCtx, CFG, K, + No_temporaries), ?debug_msg("New Worklists:\n ~p\n", [Worklists]), ?reg_print_memberships(Worklists), @@ -175,10 +173,10 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ?debug_msg("Init node sets\n",[]), Node_sets = hipe_node_sets:new(), - %% ?debug_msg("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,Target:non_alloc(CFG)]), + %% ?debug_msg("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,non_alloc(CFG,Target)]), ?debug_msg("Default coloring\n",[]), {Color0,Node_sets1} = - defaultColoring(Target:all_precoloured(), + defaultColoring(all_precoloured(Target), initColor(No_temporaries), Node_sets, Target), ?debug_msg("Color0\n",[]), ?print_colors(No_temporaries, Color0), @@ -199,9 +197,10 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]), ?debug_msg("Build mapping _N ~w\n",[Node_sets2]), - Coloring = build_namelist(Node_sets2,SpillIndex,Alias2,Color1), + {Coloring,SpillIndex2} = + build_namelist(Node_sets2,SpillIndex,Alias2,Color1), ?debug_msg("Coloring ~p\n",[Coloring]), - SortedColoring = { sort_stack(element(1, Coloring)), element(2, Coloring)}, + SortedColoring = {sort_stack(Coloring), SpillIndex2}, ?debug_msg("SortedColoring ~p\n",[SortedColoring]), %%Coloring. ?debug_msg("----------------------Assign colors _O\n",[]), @@ -217,14 +216,15 @@ 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. + {Coloring,SpillIndex2}. -else. -regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> - ?debug_msg("optimistic ~w\n",[Target]), +regalloc(CFG, Liveness, SpillIndex, SpillLimit, TgtMod, TgtCtx, _Options) -> + Target = {TgtMod, TgtCtx}, + ?debug_msg("optimistic ~w\n",[TgtMod]), ?debug_msg("CFG: ~p\n",[CFG]), %% Build interference graph ?debug_msg("Build IG\n",[]), - IG = hipe_ig:build(CFG, Target), + IG = hipe_ig:build(CFG, Liveness, TgtMod, TgtCtx), ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]), ?debug_msg("IG:\n",[]), ?print_adjacent(IG), @@ -235,9 +235,9 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> SavedAdjList = hipe_ig:adj_list(IG), ?debug_msg("Init\n",[]), - No_temporaries = Target:number_of_temporaries(CFG), + No_temporaries = number_of_temporaries(CFG, Target), ?debug_msg("Coalescing RA: num_temps = ~p~n", [No_temporaries]), - Allocatable = Target:allocatable(), + Allocatable = allocatable(Target), K = length(Allocatable), All_colors = colset_from_list(Allocatable), ?debug_msg("K: ~w~nAll_colors: ~p\n",[K, All_colors]), @@ -250,7 +250,8 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ?debug_msg("Build Worklist\n",[]), - Worklists = hipe_reg_worklists:new(IG, Target, CFG, K, No_temporaries), + Worklists = hipe_reg_worklists:new(IG, TgtMod, TgtCtx, CFG, K, + No_temporaries), ?debug_msg("New Worklists:\n ~p\n", [Worklists]), ?reg_print_memberships(Worklists), @@ -292,10 +293,10 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ?debug_msg("Init node sets\n",[]), Node_sets = hipe_node_sets:new(), - %% ?debug_msg("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,Target:non_alloc(CFG)]), + %% ?debug_msg("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,non_alloc(CFG,Target)]), ?debug_msg("Default coloring\n",[]), {Color0,Node_sets1} = - defaultColoring(Target:all_precoloured(), + defaultColoring(all_precoloured(Target), initColor(No_temporaries), Node_sets, Target), ?debug_msg("Color0\n",[]), ?print_colors(No_temporaries, Color0), @@ -316,9 +317,9 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]), ?debug_msg("Build mapping _N ~w\n",[Node_sets2]), - Coloring = build_namelist(Node_sets2,SpillIndex,Alias2,Color1), + {Coloring, SpillIndex2} = build_namelist(Node_sets2,SpillIndex,Alias2,Color1), ?debug_msg("Coloring ~p\n",[Coloring]), - Coloring. + {Coloring,SpillIndex2}. -endif. %%---------------------------------------------------------------------- @@ -834,7 +835,8 @@ sort_stack_split(Pivot, [H|T], Smaller, Bigger) -> %% been coalesced, this mapping shows the alias for that %% node. %% AllColors -- This is an ordset containing all the available colors -%% Target -- The module containing the target-specific functions. +%% Target -- The module containing the target-specific functions, +%% along with its context data. %% %% Returns: %% Color -- A mapping from nodes to their respective color. @@ -874,7 +876,7 @@ assignColors(Worklists, Stack, NodeSets, Color, No_Temporaries, false -> % Color case Col = colset_smallest(OkColors), NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), - Color1 = setColor(Node, Target:physical_name(Col), Color), + Color1 = setColor(Node, physical_name(Col,Target), Color), ?debug_msg("Color case. Assigning color ~p to node.~n", [Col]), assignColors(Worklists, Stack1, NodeSets1, Color1, No_Temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, AllColors, Target) end @@ -902,7 +904,8 @@ assignColors(Worklists, Stack, NodeSets, Color, No_Temporaries, %% Alias -- This is a mapping from nodes to nodes. If a node has %% been coalesced, this mapping shows the alias for that %% node. -%% Target -- The module containing the target-specific functions. +%% Target -- The module containing the target-specific functions, +%% along with its context data. %% %% Returns: %% Alias -- The restored aliases after the uncoalescing. @@ -1006,7 +1009,7 @@ colorSplit([], _Col, NodeSets, Color, _Target) -> colorSplit([Node|Nodes], Col, NodeSets, Color, Target) -> ?debug_msg(" Coloring node ~p with color ~p.~n", [Node, Col]), NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), - Color1 = setColor(Node, Target:physical_name(Col), Color), + Color1 = setColor(Node, physical_name(Col,Target), Color), colorSplit(Nodes, Col, NodeSets1, Color1, Target). %% Place non-colorable nodes in a split at the bottom of the SelectStack. @@ -1035,7 +1038,8 @@ enqueueSplit([Node|Nodes], IG, Stack) -> %% node. %% AllColors -- This is an ordset containing all the available colors %% -%% Target -- The module containing the target-specific functions. +%% Target -- The module containing the target-specific functions, +%% along with its context data. %% %% Returns: %% Color -- A mapping from nodes to their respective color. @@ -1065,7 +1069,7 @@ assignColors_O(Stack,NodeSets,Color,Alias,AllColors,Target) -> false -> % Colour case Col = colset_smallest(OkColors), NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), - Color1 = setColor(Node, Target:physical_name(Col), Color), + Color1 = setColor(Node, physical_name(Col,Target), Color), assignColors_O(Stack1, NodeSets1, Color1, Alias, AllColors, Target) end end. @@ -1079,7 +1083,8 @@ assignColors_O(Stack,NodeSets,Color,Alias,AllColors,Target) -> %% Regs -- The list of registers to be default colored %% Color -- The color mapping that shall be changed %% NodeSets -- The node sets that shall be updated -%% Target -- The module containing the target-specific functions. +%% Target -- The module containing the target-specific functions, +%% along with its context data. %% %% Returns: %% NewColor -- The updated color mapping @@ -1089,7 +1094,7 @@ assignColors_O(Stack,NodeSets,Color,Alias,AllColors,Target) -> defaultColoring([], Color, NodeSets, _Target) -> {Color,NodeSets}; defaultColoring([Reg|Regs], Color, NodeSets, Target) -> - Color1 = setColor(Reg,Target:physical_name(Reg), Color), + Color1 = setColor(Reg,physical_name(Reg,Target), Color), NodeSets1 = hipe_node_sets:add_colored(Reg, NodeSets), defaultColoring(Regs, Color1, NodeSets1, Target). @@ -1283,7 +1288,7 @@ coalesce(Moves, IG, Worklists, Alias, K, Target) -> ?debug_msg("Testing nodes ~p and ~p for coalescing~n",[Dest,Source]), Alias_src = getAlias(Source, Alias), Alias_dst = getAlias(Dest, Alias), - {U,V} = case Target:is_precoloured(Alias_dst) of + {U,V} = case is_precoloured(Alias_dst, Target) of true -> {Alias_dst, Alias_src}; false -> {Alias_src, Alias_dst} end, @@ -1293,13 +1298,13 @@ coalesce(Moves, IG, Worklists, Alias, K, Target) -> %% drop coalesced move Move {Moves0, IG, Alias, Worklists}; _ -> - case (Target:is_precoloured(V) orelse + case (is_precoloured(V, Target) orelse hipe_ig:nodes_are_adjacent(U, V, IG)) of true -> %% drop constrained move Move {Moves0, IG, Alias, Worklists}; false -> - case (case Target:is_precoloured(U) of + case (case is_precoloured(U, Target) of true -> AdjV = hipe_ig:node_adj_list(V, IG), all_adjacent_ok(AdjV, U, Worklists, IG, K, Target); @@ -1350,7 +1355,7 @@ coalesce_O(Moves, IG, Worklists, Alias, K, Target) -> ?debug_msg("Testing nodes ~p and ~p for coalescing~n",[Dest,Source]), Alias_src = getAlias(Source, Alias), Alias_dst = getAlias(Dest, Alias), - {U,V} = case Target:is_precoloured(Alias_dst) of + {U,V} = case is_precoloured(Alias_dst, Target) of true -> {Alias_dst, Alias_src}; false -> {Alias_src, Alias_dst} end, @@ -1361,7 +1366,7 @@ coalesce_O(Moves, IG, Worklists, Alias, K, Target) -> Worklists1 = add_worklist(Worklists, U, K, Moves1, IG, Target), {Moves1, IG, Worklists1, Alias}; _ -> - case (Target:is_precoloured(V) orelse + case (is_precoloured(V, Target) orelse hipe_ig:nodes_are_adjacent(U, V, IG)) of true -> Moves1 = Moves0, % drop constrained move Move @@ -1369,7 +1374,7 @@ coalesce_O(Moves, IG, Worklists, Alias, K, Target) -> Worklists2 = add_worklist(Worklists1, V, K, Moves1, IG, Target), {Moves1, IG, Worklists2, Alias}; false -> - case (case Target:is_precoloured(U) of + case (case is_precoloured(U, Target) of true -> AdjV = hipe_ig:node_adj_list(V, IG), all_adjacent_ok(AdjV, U, Worklists, IG, K, Target); @@ -1405,7 +1410,8 @@ coalesce_O(Moves, IG, Worklists, Alias, K, Target) -> %% K -- Number of registers %% Moves -- Current move information %% IG -- Interference graph -%% Target -- The containing the target-specific functions +%% Target -- The containing the target-specific functions, along with +%% its context data. %% %% Returns: %% Worklists (updated) @@ -1413,7 +1419,7 @@ coalesce_O(Moves, IG, Worklists, Alias, K, Target) -> -ifdef(COMPARE_ITERATED_OPTIMISTIC). add_worklist(Worklists, U, K, Moves, IG, Target) -> - case (not(Target:is_precoloured(U)) + case (not(is_precoloured(U, Target)) andalso not(hipe_moves:move_related(U, Moves)) andalso (hipe_ig:is_trivially_colourable(U, K, IG))) of true -> @@ -1524,12 +1530,12 @@ combine(U, V, IG, Alias, Worklists, K, Target) -> combine_edges([], _U, IG, _Worklists, _K, _Target) -> IG; -combine_edges([T|Ts], U, IG, Worklists, K, Target) -> +combine_edges([T|Ts], U, IG, Worklists, K, Target={TgtMod,TgtCtx}) -> case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of true -> combine_edges(Ts, U, IG, Worklists, K, Target); _ -> - IG1 = hipe_ig:add_edge(T, U, IG, Target), - IG2 = case Target:is_precoloured(T) of + IG1 = hipe_ig:add_edge(T, U, IG, TgtMod, TgtCtx), + IG2 = case is_precoloured(T, Target) of true -> IG1; false -> hipe_ig:dec_node_degree(T, IG1) end, @@ -1559,7 +1565,7 @@ combine_edges([T|Ts], U, IG, Worklists, K, Target) -> -ifdef(COMPARE_ITERATED_OPTIMISTIC). combine_edges_O([], _U, IG, Worklists, Moves, _K, _Target) -> {IG, Worklists, Moves}; -combine_edges_O([T|Ts], U, IG, Worklists, Moves, K, Target) -> +combine_edges_O([T|Ts], U, IG, Worklists, Moves, K, Target={TgtMod,TgtCtx}) -> case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of true -> combine_edges_O(Ts, U, IG, Worklists, Moves, K, Target); _ -> @@ -1576,7 +1582,7 @@ combine_edges_O([T|Ts], U, IG, Worklists, Moves, K, Target) -> %% worklist, and that's where decrement_degree() expects to find it. %% This issue is not covered in the published algorithm. OldDegree = hipe_ig:get_node_degree(T, IG), - IG1 = hipe_ig:add_edge(T, U, IG, Target), + IG1 = hipe_ig:add_edge(T, U, IG, TgtMod, TgtCtx), NewDegree = hipe_ig:get_node_degree(T, IG1), Worklists0 = if NewDegree =:= K, OldDegree =:= K-1 -> @@ -1609,7 +1615,8 @@ combine_edges_O([T|Ts], U, IG, Worklists, Moves, K, Target) -> %% Alias -- The Alias vector before undoing %% SavedAdj -- Saved adjacency list %% IG -- Interference graph -%% Target -- The module containing the target-specific functions. +%% Target -- The module containing the target-specific functions, +%% along with its context data. %% %% Returns: %% list of primitive nodes, that is all nodes that were previously @@ -1676,7 +1683,8 @@ findPrimitiveNodes(Node, N, Alias, PrimitiveNodes) -> %% N -- Node that should be uncoalesced %% SavedAdj -- Saved adjacency list %% IG -- Interference graph -%% Target -- The module containing the target-specific functions. +%% Target -- The module containing the target-specific functions, along +%% with its context data. %% %% Returns: %% updated Interferece graph @@ -1702,16 +1710,16 @@ fixAdj(N, SavedAdj, IG, Target) -> removeAdj([], _N, _IG, _Target) -> true; -removeAdj([V| New], N, IG, Target) -> - hipe_ig:remove_edge(V, N, IG, Target), +removeAdj([V| New], N, IG, Target={TgtMod,TgtCtx}) -> + hipe_ig:remove_edge(V, N, IG, TgtMod, TgtCtx), removeAdj(New, N, IG, Target). %%restoreAdj([], _N, IG, _Alias, _Target) -> %% %%?debug_msg("adj_lists__after_restore_o ~n~p~n", [hipe_ig:adj_list(IG)]), %% IG; -%%restoreAdj([V| AdjToN], N, IG, Alias, Target) -> +%%restoreAdj([V| AdjToN], N, IG, Alias, Target={TgtMod,TgtCtx}) -> %% AliasToV = getAlias(V, Alias), -%% IG1 = hipe_ig:add_edge(N, AliasToV, IG, Target), +%% IG1 = hipe_ig:add_edge(N, AliasToV, IG, TgtMod, TgtCtx), %% restoreAdj(AdjToN, N, IG1, Alias, Target). %% XXX This is probably a clumsy way of doing it @@ -1744,7 +1752,8 @@ findNew([A| Adj], Saved, New) -> %% R -- Other node to test %% IG -- Interference graph %% K -- Number of registers -%% Target -- The module containing the target-specific functions +%% Target -- The module containing the target-specific functions, along +%% with its context data. %% %% Returns: %% true iff coalescing is OK @@ -1752,7 +1761,7 @@ findNew([A| Adj], Saved, New) -> ok(T, R, IG, K, Target) -> ((hipe_ig:is_trivially_colourable(T, K, IG)) - orelse Target:is_precoloured(T) + orelse is_precoloured(T, Target) orelse hipe_ig:nodes_are_adjacent(T, R, IG)). %%---------------------------------------------------------------------- @@ -1765,7 +1774,8 @@ ok(T, R, IG, K, Target) -> %% U -- Node to test for coalescing %% IG -- Interference graph %% K -- Number of registers -%% Target -- The module containing the target-specific functions +%% Target -- The module containing the target-specific functions, along +%% with its context data. %% %% Returns: %% true iff coalescing is OK for all nodes in the list @@ -1923,7 +1933,7 @@ findCheapest([Node|Nodes], IG, Cost, Cheapest, SpillLimit) -> %% limit are extremely expensive. getCost(Node, IG, SpillLimit) -> - case Node > SpillLimit of + case Node >= SpillLimit of true -> inf; false -> SpillCost = hipe_ig:node_spill_cost(Node, IG), @@ -2042,3 +2052,24 @@ freezeEm3(_U,V,_M,K,WorkLists,Moves,IG,_Alias) -> {WorkLists,Moves1} end. -endif. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Interface to external functions. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +all_precoloured({TgtMod,TgtCtx}) -> + TgtMod:all_precoloured(TgtCtx). + +allocatable({TgtMod,TgtCtx}) -> + TgtMod:allocatable(TgtCtx). + +is_precoloured(R, {TgtMod,TgtCtx}) -> + TgtMod:is_precoloured(R,TgtCtx). + +number_of_temporaries(CFG, {TgtMod,TgtCtx}) -> + TgtMod:number_of_temporaries(CFG, TgtCtx). + +physical_name(R, {TgtMod,TgtCtx}) -> + TgtMod:physical_name(R,TgtCtx). diff --git a/lib/hipe/regalloc/hipe_ppc_specific.erl b/lib/hipe/regalloc/hipe_ppc_specific.erl index c49b1e510f..81bb551bd2 100644 --- a/lib/hipe/regalloc/hipe_ppc_specific.erl +++ b/lib/hipe/regalloc/hipe_ppc_specific.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2004-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,121 +11,138 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -module(hipe_ppc_specific). %% for hipe_coalescing_regalloc: --export([number_of_temporaries/1 - ,analyze/1 - ,labels/1 - ,all_precoloured/0 - ,bb/2 - ,liveout/2 - ,reg_nr/1 - ,def_use/1 - ,is_move/1 - ,is_precoloured/1 - ,var_range/1 - ,allocatable/0 - ,non_alloc/1 - ,physical_name/1 - ,reverse_postorder/1 - ,livein/2 - ,uses/1 - ,defines/1 +-export([number_of_temporaries/2 + ,analyze/2 + ,labels/2 + ,all_precoloured/1 + ,bb/3 + ,liveout/3 + ,reg_nr/2 + ,def_use/2 + ,is_move/2 + ,is_spill_move/2 + ,is_precoloured/2 + ,var_range/2 + ,allocatable/1 + ,non_alloc/2 + ,physical_name/2 + ,reverse_postorder/2 + ,livein/3 + ,uses/2 + ,defines/2 + ,defines_all_alloc/2 ]). %% for hipe_graph_coloring_regalloc: --export([is_fixed/1]). +-export([is_fixed/2]). %% for hipe_ls_regalloc: --export([args/1, is_arg/1, is_global/1, new_spill_index/1]). --export([breadthorder/1, postorder/1]). +-export([args/2, is_arg/2, is_global/2, new_spill_index/2]). +-export([breadthorder/2, postorder/2]). %% callbacks for hipe_regalloc_loop --export([defun_to_cfg/1, - check_and_rewrite/2]). +-export([check_and_rewrite/3]). + +%% callbacks for hipe_regalloc_prepass, hipe_range_split +-export([mk_move/3, + mk_goto/2, + redirect_jmp/4, + new_label/1, + new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -defun_to_cfg(Defun) -> - hipe_ppc_cfg:init(Defun). +%% callbacks for hipe_bb_weights +-export([branch_preds/2]). -check_and_rewrite(Defun, Coloring) -> - hipe_ppc_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal'). +check_and_rewrite(CFG, Coloring, _) -> + hipe_ppc_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal'). -reverse_postorder(CFG) -> +reverse_postorder(CFG, _) -> hipe_ppc_cfg:reverse_postorder(CFG). -non_alloc(CFG) -> - non_alloc(hipe_ppc_registers:nr_args(), hipe_ppc_cfg:params(CFG)). +non_alloc(CFG, no_context) -> + non_alloc_1(hipe_ppc_registers:nr_args(), hipe_ppc_cfg:params(CFG)). %% same as hipe_ppc_frame:fix_formals/2 -non_alloc(0, Rest) -> Rest; -non_alloc(N, [_|Rest]) -> non_alloc(N-1, Rest); -non_alloc(_, []) -> []. +non_alloc_1(0, Rest) -> Rest; +non_alloc_1(N, [_|Rest]) -> non_alloc_1(N-1, Rest); +non_alloc_1(_, []) -> []. %% Liveness stuff -analyze(CFG) -> +analyze(CFG, _) -> hipe_ppc_liveness_gpr:analyse(CFG). -livein(Liveness,L) -> +livein(Liveness,L,_) -> [X || X <- hipe_ppc_liveness_gpr:livein(Liveness,L), hipe_ppc:temp_is_allocatable(X)]. -liveout(BB_in_out_liveness,Label) -> +liveout(BB_in_out_liveness,Label,_) -> [X || X <- hipe_ppc_liveness_gpr:liveout(BB_in_out_liveness,Label), hipe_ppc:temp_is_allocatable(X)]. %% Registers stuff -allocatable() -> +allocatable(no_context) -> hipe_ppc_registers:allocatable_gpr(). -all_precoloured() -> +all_precoloured(no_context) -> hipe_ppc_registers:all_precoloured(). -is_precoloured(Reg) -> +is_precoloured(Reg, _) -> hipe_ppc_registers:is_precoloured_gpr(Reg). -is_fixed(R) -> +is_fixed(R, _) -> hipe_ppc_registers:is_fixed(R). -physical_name(Reg) -> +physical_name(Reg, _) -> Reg. %% CFG stuff -labels(CFG) -> +labels(CFG, _) -> hipe_ppc_cfg:labels(CFG). -var_range(_CFG) -> +var_range(_CFG, _) -> hipe_gensym:var_range(ppc). -number_of_temporaries(_CFG) -> +number_of_temporaries(_CFG, _) -> Highest_temporary = hipe_gensym:get_var(ppc), %% Since we can have temps from 0 to Max adjust by +1. Highest_temporary + 1. -bb(CFG,L) -> +bb(CFG,L,_) -> hipe_ppc_cfg:bb(CFG,L). +update_bb(CFG,L,BB,_) -> + hipe_ppc_cfg:bb_add(CFG,L,BB). + +branch_preds(Instr,_) -> + hipe_ppc_cfg:branch_preds(Instr). + %% PowerPC stuff -def_use(Instruction) -> - {defines(Instruction), uses(Instruction)}. +def_use(Instruction, Ctx) -> + {defines(Instruction, Ctx), uses(Instruction, Ctx)}. -uses(I) -> +uses(I, _) -> [X || X <- hipe_ppc_defuse:insn_use_gpr(I), hipe_ppc:temp_is_allocatable(X)]. -defines(I) -> +defines(I, _) -> [X || X <- hipe_ppc_defuse:insn_def_gpr(I), hipe_ppc:temp_is_allocatable(X)]. -is_move(Instruction) -> +defines_all_alloc(I, _) -> + hipe_ppc_defuse:insn_defs_all_gpr(I). + +is_move(Instruction, _) -> case hipe_ppc:is_pseudo_move(Instruction) of true -> Dst = hipe_ppc:pseudo_move_dst(Instruction), @@ -142,28 +155,60 @@ is_move(Instruction) -> false -> false end. -reg_nr(Reg) -> +is_spill_move(Instruction, _) -> + hipe_ppc:is_pseudo_spill_move(Instruction). + +reg_nr(Reg, _) -> hipe_ppc:temp_reg(Reg). +mk_move(Src, Dst, _) -> + hipe_ppc:mk_pseudo_move(Dst, Src). + +mk_goto(Label, _) -> + hipe_ppc:mk_b_label(Label). + +redirect_jmp(Jmp, ToOld, ToNew, _) when is_integer(ToOld), is_integer(ToNew) -> + hipe_ppc_cfg:redirect_jmp(Jmp, ToOld, ToNew). + +new_label(_) -> + hipe_gensym:get_next_label(ppc). + +new_reg_nr(_) -> + hipe_gensym:get_next_var(ppc). + +update_reg_nr(Nr, Temp, _) -> + hipe_ppc:mk_temp(Nr, hipe_ppc:temp_type(Temp)). + +subst_temps(SubstFun, Instr, _) -> + hipe_ppc_subst:insn_temps( + fun(Op) -> + case hipe_ppc:temp_is_allocatable(Op) + andalso hipe_ppc:temp_type(Op) =/= 'double' + of + true -> SubstFun(Op); + false -> Op + end + end, Instr). + %%% Linear Scan stuff -new_spill_index(SpillIndex) when is_integer(SpillIndex) -> +new_spill_index(SpillIndex, _) when is_integer(SpillIndex) -> SpillIndex+1. -breadthorder(CFG) -> +breadthorder(CFG, _) -> hipe_ppc_cfg:breadthorder(CFG). -postorder(CFG) -> +postorder(CFG, _) -> hipe_ppc_cfg:postorder(CFG). -is_global(R) -> +is_global(R, _) -> R =:= hipe_ppc_registers:temp1() orelse R =:= hipe_ppc_registers:temp2() orelse R =:= hipe_ppc_registers:temp3() orelse hipe_ppc_registers:is_fixed(R). -is_arg(R) -> +is_arg(R, _) -> hipe_ppc_registers:is_arg(R). -args(CFG) -> +args(CFG, _) -> hipe_ppc_registers:args(hipe_ppc_cfg:arity(CFG)). diff --git a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl index 454aa4c686..dcfdf6592c 100644 --- a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl +++ b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2004-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,133 +11,182 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -module(hipe_ppc_specific_fp). %% for hipe_coalescing_regalloc: --export([number_of_temporaries/1 - ,analyze/1 - ,labels/1 - ,all_precoloured/0 - ,bb/2 - ,liveout/2 - ,reg_nr/1 - ,def_use/1 - ,is_move/1 - ,is_precoloured/1 - ,var_range/1 - ,allocatable/0 - ,non_alloc/1 - ,physical_name/1 - ,reverse_postorder/1 - ,livein/2 - ,uses/1 - ,defines/1 +-export([number_of_temporaries/2 + ,analyze/2 + ,labels/2 + ,all_precoloured/1 + ,bb/3 + ,liveout/3 + ,reg_nr/2 + ,def_use/2 + ,is_move/2 + ,is_spill_move/2 + ,is_precoloured/2 + ,var_range/2 + ,allocatable/1 + ,non_alloc/2 + ,physical_name/2 + ,reverse_postorder/2 + ,livein/3 + ,uses/2 + ,defines/2 + ,defines_all_alloc/2 ]). %% for hipe_graph_coloring_regalloc: --export([is_fixed/1]). +-export([is_fixed/2]). %% for hipe_ls_regalloc: -%%-export([args/1, is_arg/1, is_global, new_spill_index/1]). -%%-export([breadthorder/1, postorder/1]). +%%-export([args/2, is_arg/2, is_global, new_spill_index/2]). +%%-export([breadthorder/2, postorder/2]). %% callbacks for hipe_regalloc_loop --export([defun_to_cfg/1, - check_and_rewrite/2]). +-export([check_and_rewrite/3]). + +%% callbacks for hipe_regalloc_prepass, hipe_range_split +-export([mk_move/3, + mk_goto/2, + redirect_jmp/4, + new_label/1, + new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -defun_to_cfg(Defun) -> - hipe_ppc_cfg:init(Defun). +%% callbacks for hipe_bb_weights +-export([branch_preds/2]). -check_and_rewrite(Defun, Coloring) -> - hipe_ppc_ra_postconditions_fp:check_and_rewrite(Defun, Coloring). +check_and_rewrite(CFG, Coloring, _) -> + hipe_ppc_ra_postconditions_fp:check_and_rewrite(CFG, Coloring). -reverse_postorder(CFG) -> +reverse_postorder(CFG, _) -> hipe_ppc_cfg:reverse_postorder(CFG). -non_alloc(_CFG) -> +non_alloc(_CFG, _) -> []. %% Liveness stuff -analyze(CFG) -> +analyze(CFG, _) -> hipe_ppc_liveness_fpr:analyse(CFG). -livein(Liveness, L) -> +livein(Liveness, L, _) -> hipe_ppc_liveness_fpr:livein(Liveness, L). -liveout(BB_in_out_liveness, Label) -> +liveout(BB_in_out_liveness, Label, _) -> hipe_ppc_liveness_fpr:liveout(BB_in_out_liveness, Label). %% Registers stuff -allocatable() -> +allocatable(no_context) -> hipe_ppc_registers:allocatable_fpr(). -all_precoloured() -> - allocatable(). +all_precoloured(Ctx) -> + allocatable(Ctx). -is_precoloured(Reg) -> +is_precoloured(Reg, _) -> hipe_ppc_registers:is_precoloured_fpr(Reg). -is_fixed(_Reg) -> +is_fixed(_Reg, _) -> false. -physical_name(Reg) -> +physical_name(Reg, _) -> Reg. %% CFG stuff -labels(CFG) -> +labels(CFG, _) -> hipe_ppc_cfg:labels(CFG). -var_range(_CFG) -> +var_range(_CFG, _) -> hipe_gensym:var_range(ppc). -number_of_temporaries(_CFG) -> +number_of_temporaries(_CFG, _) -> Highest_temporary = hipe_gensym:get_var(ppc), %% Since we can have temps from 0 to Max adjust by +1. Highest_temporary + 1. -bb(CFG, L) -> +bb(CFG, L, _) -> hipe_ppc_cfg:bb(CFG, L). +update_bb(CFG,L,BB,_) -> + hipe_ppc_cfg:bb_add(CFG,L,BB). + +branch_preds(Instr,_) -> + hipe_ppc_cfg:branch_preds(Instr). + %% PowerPC stuff -def_use(I) -> - {defines(I), uses(I)}. +def_use(I, Ctx) -> + {defines(I, Ctx), uses(I, Ctx)}. -uses(I) -> +uses(I, _) -> hipe_ppc_defuse:insn_use_fpr(I). -defines(I) -> +defines(I, _) -> hipe_ppc_defuse:insn_def_fpr(I). -is_move(I) -> +defines_all_alloc(I, _) -> + hipe_ppc_defuse:insn_defs_all_fpr(I). + +is_move(I, _) -> hipe_ppc:is_pseudo_fmove(I). -reg_nr(Reg) -> +is_spill_move(I, _) -> + hipe_ppc:is_pseudo_spill_fmove(I). + +reg_nr(Reg, _) -> hipe_ppc:temp_reg(Reg). +mk_move(Src, Dst, _) -> + hipe_ppc:mk_pseudo_fmove(Dst, Src). + +mk_goto(Label, _) -> + hipe_ppc:mk_b_label(Label). + +redirect_jmp(Jmp, ToOld, ToNew, _) when is_integer(ToOld), is_integer(ToNew) -> + hipe_ppc_cfg:redirect_jmp(Jmp, ToOld, ToNew). + +new_label(_) -> + hipe_gensym:get_next_label(ppc). + +new_reg_nr(_) -> + hipe_gensym:get_next_var(ppc). + +update_reg_nr(Nr, _Temp, _) -> + hipe_ppc:mk_temp(Nr, 'double'). + +subst_temps(SubstFun, Instr, _) -> + hipe_ppc_subst:insn_temps( + fun(Op) -> + case hipe_ppc:temp_is_allocatable(Op) + andalso hipe_ppc:temp_type(Op) =:= 'double' + of + true -> SubstFun(Op); + false -> Op + end + end, Instr). + -ifdef(notdef). -new_spill_index(SpillIndex) -> +new_spill_index(SpillIndex, _) -> SpillIndex+1. -breadthorder(CFG) -> +breadthorder(CFG, _) -> hipe_ppc_cfg:breadthorder(CFG). -postorder(CFG) -> +postorder(CFG, _) -> hipe_ppc_cfg:postorder(CFG). -is_global(_R) -> +is_global(_R, _) -> false. -is_arg(_R) -> +is_arg(_R, _) -> false. -args(_CFG) -> +args(_CFG, _) -> []. -endif. diff --git a/lib/hipe/regalloc/hipe_range_split.erl b/lib/hipe/regalloc/hipe_range_split.erl new file mode 100644 index 0000000000..385df695f2 --- /dev/null +++ b/lib/hipe/regalloc/hipe_range_split.erl @@ -0,0 +1,1187 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%@doc +%% TEMPORARY LIVE RANGE SPLITTING PASS +%% +%% Live range splitting is useful to allow a register allocator to allocate a +%% temporary to register for a part of its lifetime, even if it cannot be for +%% the entirety. This improves register allocation quality, at the cost of +%% making the allocation problem more time and memory intensive to solve. +%% +%% Optimal allocation can be achieved if all temporaries are split at every +%% program point (between all instructions), but this makes register allocation +%% infeasably slow in practice. Instead, this module uses heuristics to choose +%% which temporaries should have their live ranges split, and at which points. +%% +%% The range splitter only considers temps which are live during a call +%% instruction, since they're known to be spilled. The control-flow graph is +%% partitioned at call instructions and splitting decisions are made separately +%% for each partition. The register copy of a temp (if any) gets a separate name +%% in each partition. +%% +%% There are three different ways the range splitter may choose to split a +%% temporary in a program partition: +%% +%% * Mode1: Spill the temp before calls, and restore it after them +%% * Mode2: Spill the temp after definitions, restore it after calls +%% * Mode3: Spill the temp after definitions, restore it before uses +%% +%% To pick which of these should be used for each temp×partiton pair, the range +%% splitter uses a cost function. The cost is simply the sum of the cost of all +%% expected stack accesses, and the cost for an individual stack access is based +%% on the probability weight of the basic block that it resides in. This biases +%% the range splitter so that it attempts moving stack accesses from a functions +%% hot path to the cold path. +%% +%% The heuristic has a couple of tuning knobs, adjusting its preference for +%% different spilling modes, aggressiveness, and how much influence the basic +%% block probability weights have. +%% +%% Edge case not handled: Call instructions directly defining a pseudo. In that +%% case, if that pseudo has been selected for mode2 spills, no spill is inserted +%% after the call. +-module(hipe_range_split). + +-export([split/5]). + +-compile(inline). + +%% -define(DO_ASSERT, 1). +%% -define(DEBUG, 1). +-include("../main/hipe.hrl"). + +%% Heuristic tuning constants +-define(DEFAULT_MIN_GAIN, 1.1). % option: range_split_min_gain +-define(DEFAULT_MODE1_FUDGE, 1.1). % option: range_split_mode1_fudge +-define(DEFAULT_WEIGHT_POWER, 2). % option: range_split_weight_power +-define(WEIGHT_CONST_FUN(Power), math:log(Power)/math:log(100)). +-define(WEIGHT_FUN(Wt, Const), math:pow(Wt, Const)). +-define(HEUR_MAX_TEMPS, 20000). + +-type target_cfg() :: any(). +-type target_instr() :: any(). +-type target_temp() :: any(). +-type liveness() :: any(). +-type target_module() :: module(). +-type target_context() :: any(). +-type target() :: {target_module(), target_context()}. +-type liveset() :: ordsets:ordset(temp()). +-type temp() :: non_neg_integer(). +-type label() :: non_neg_integer(). + +-spec split(target_cfg(), liveness(), target_module(), target_context(), + comp_options()) + -> target_cfg(). +split(TCFG0, Liveness, TargetMod, TargetContext, Options) -> + Target = {TargetMod, TargetContext}, + NoTemps = number_of_temporaries(TCFG0, Target), + if NoTemps > ?HEUR_MAX_TEMPS -> + ?debug_msg("~w: Too many temps (~w), falling back on restore_reuse.~n", + [?MODULE, NoTemps]), + hipe_restore_reuse:split(TCFG0, Liveness, TargetMod, TargetContext); + true -> + Wts = compute_weights(TCFG0, TargetMod, TargetContext, Options), + {CFG0, Temps} = convert(TCFG0, Target), + Avail = avail_analyse(TCFG0, Liveness, Target), + Defs = def_analyse(CFG0, TCFG0), + RDefs = rdef_analyse(CFG0), + PLive = plive_analyse(CFG0), + {CFG, DUCounts, Costs, DSets0} = + scan(CFG0, Liveness, PLive, Wts, Defs, RDefs, Avail, Target), + {DSets, _} = hipe_dsets:to_map(DSets0), + Renames = decide(DUCounts, Costs, Target, Options), + rewrite(CFG, TCFG0, Target, Liveness, PLive, Defs, Avail, DSets, Renames, + Temps) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Internal program representation +%% +%% Second pass: Convert cfg to internal representation + +-record(cfg, { + rpo_labels :: [label()], + bbs :: #{label() => bb()} + }). +-type cfg() :: #cfg{}. + +cfg_bb(L, #cfg{bbs=BBS}) -> maps:get(L, BBS). + +cfg_postorder(#cfg{rpo_labels=RPO}) -> lists:reverse(RPO). + +-record(bb, { + code :: [code_elem()], + %% If the last instruction of code defines all allocatable registers + has_call :: boolean(), + succ :: [label()] + }). +-type bb() :: #bb{}. +-type code_elem() :: instr() | mode2_spills() | mode3_restores(). + +bb_code(#bb{code=Code}) -> Code. +bb_has_call(#bb{has_call=HasCall}) -> HasCall. +bb_succ(#bb{succ=Succ}) -> Succ. + +bb_butlast(#bb{code=Code}) -> + bb_butlast_1(Code). + +bb_butlast_1([_Last]) -> []; +bb_butlast_1([I|Is]) -> [I|bb_butlast_1(Is)]. + +bb_last(#bb{code=Code}) -> lists:last(Code). + +-record(instr, { + i :: target_instr(), + def :: ordsets:ordset(temp()), + use :: ordsets:ordset(temp()) + }). +-type instr() :: #instr{}. + +-record(mode2_spills, { + temps :: ordsets:ordset(temp()) + }). +-type mode2_spills() :: #mode2_spills{}. + +-record(mode3_restores, { + temps :: ordsets:ordset(temp()) + }). +-type mode3_restores() :: #mode3_restores{}. + +-spec convert(target_cfg(), target()) -> {cfg(), temps()}. +convert(CFG, Target) -> + RPO = reverse_postorder(CFG, Target), + {BBsList, Temps} = convert_bbs(RPO, CFG, Target, #{}, []), + {#cfg{rpo_labels = RPO, + bbs = maps:from_list(BBsList)}, + Temps}. + +convert_bbs([], _CFG, _Target, Temps, Acc) -> {Acc, Temps}; +convert_bbs([L|Ls], CFG, Target, Temps0, Acc) -> + Succs = hipe_gen_cfg:succ(CFG, L), + TBB = bb(CFG, L, Target), + TCode = hipe_bb:code(TBB), + {Code, Last, Temps} = convert_code(TCode, Target, Temps0, []), + HasCall = defines_all_alloc(Last#instr.i, Target), + BB = #bb{code = Code, + has_call = HasCall, + succ = Succs}, + convert_bbs(Ls, CFG, Target, Temps, [{L,BB}|Acc]). + +convert_code([], _Target, Temps, [Last|_]=Acc) -> + {lists:reverse(Acc), Last, Temps}; +convert_code([TI|TIs], Target, Temps0, Acc) -> + {TDef, TUse} = def_use(TI, Target), + I = #instr{i = TI, + def = ordsets:from_list(reg_names(TDef, Target)), + use = ordsets:from_list(reg_names(TUse, Target))}, + Temps = add_temps(TUse, Target, add_temps(TDef, Target, Temps0)), + convert_code(TIs, Target, Temps, [I|Acc]). + +-type temps() :: #{temp() => target_temp()}. +add_temps([], _Target, Temps) -> Temps; +add_temps([T|Ts], Target, Temps) -> + add_temps(Ts, Target, Temps#{reg_nr(T, Target) => T}). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Fourth pass: P({DEF}) lattice fwd dataflow (for eliding stores at SPILL +%% splits) +-type defsi() :: #{label() => defseti() | {call, defseti(), defseti()}}. +-type defs() :: #{label() => defsetf()}. + +-spec def_analyse(cfg(), target_cfg()) -> defs(). +def_analyse(CFG = #cfg{rpo_labels = RPO}, TCFG) -> + Defs0 = def_init(CFG), + def_dataf(RPO, TCFG, Defs0). + +-spec def_init(cfg()) -> defsi(). +def_init(#cfg{bbs = BBs}) -> + maps:from_list( + [begin + {L, case HasCall of + false -> def_init_scan(bb_code(BB), defseti_new()); + true -> + {call, def_init_scan(bb_butlast(BB), defseti_new()), + defseti_from_ordset((bb_last(BB))#instr.def)} + end} + end || {L, BB = #bb{has_call=HasCall}} <- maps:to_list(BBs)]). + +def_init_scan([], Defset) -> Defset; +def_init_scan([#instr{def=Def}|Is], Defset0) -> + Defset = defseti_add_ordset(Def, Defset0), + def_init_scan(Is, Defset). + +-spec def_dataf([label()], target_cfg(), defsi()) -> defs(). +def_dataf(Labels, TCFG, Defs0) -> + case def_dataf_once(Labels, TCFG, Defs0, 0) of + {Defs, 0} -> + def_finalise(Defs); + {Defs, _Changed} -> + def_dataf(Labels, TCFG, Defs) + end. + +-spec def_finalise(defsi()) -> defs(). +def_finalise(Defs) -> + maps:from_list([{K, defseti_finalise(BL)} + || {K, {call, BL, _}} <- maps:to_list(Defs)]). + +-spec def_dataf_once([label()], target_cfg(), defsi(), non_neg_integer()) + -> {defsi(), non_neg_integer()}. +def_dataf_once([], _TCFG, Defs, Changed) -> {Defs, Changed}; +def_dataf_once([L|Ls], TCFG, Defs0, Changed0) -> + AddPreds = + fun(Defset1) -> + lists:foldl(fun(P, Defset2) -> + defseti_union(defout(P, Defs0), Defset2) + end, Defset1, hipe_gen_cfg:pred(TCFG, L)) + end, + Defset = + case Defset0 = maps:get(L, Defs0) of + {call, Butlast, Defout} -> {call, AddPreds(Butlast), Defout}; + _ -> AddPreds(Defset0) + end, + Changed = case Defset =:= Defset0 of + true -> Changed0; + false -> Changed0+1 + end, + def_dataf_once(Ls, TCFG, Defs0#{L := Defset}, Changed). + +-spec defout(label(), defsi()) -> defseti(). +defout(L, Defs) -> + case maps:get(L, Defs) of + {call, _DefButLast, Defout} -> Defout; + Defout -> Defout + end. + +-spec defbutlast(label(), defs()) -> defsetf(). +defbutlast(L, Defs) -> maps:get(L, Defs). + +-spec defseti_new() -> defseti(). +-spec defseti_union(defseti(), defseti()) -> defseti(). +-spec defseti_add_ordset(ordsets:ordset(temp()), defseti()) -> defseti(). +-spec defseti_from_ordset(ordsets:ordset(temp())) -> defseti(). +-spec defseti_finalise(defseti()) -> defsetf(). +-spec defsetf_member(temp(), defsetf()) -> boolean(). +-spec defsetf_intersect_ordset(ordsets:ordset(temp()), defsetf()) + -> ordsets:ordset(temp()). + +-type defseti() :: bitord(). +defseti_new() -> bitord_new(). +defseti_union(A, B) -> bitord_union(A, B). +defseti_add_ordset(OS, D) -> defseti_union(defseti_from_ordset(OS), D). +defseti_from_ordset(OS) -> bitord_from_ordset(OS). +defseti_finalise(D) -> bitarr_from_bitord(D). + +-type defsetf() :: bitarr(). +defsetf_member(E, D) -> bitarr_get(E, D). + +defsetf_intersect_ordset([], _D) -> []; +defsetf_intersect_ordset([E|Es], D) -> + case bitarr_get(E, D) of + true -> [E|defsetf_intersect_ordset(Es,D)]; + false -> defsetf_intersect_ordset(Es,D) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Fifth pass: P({DEF}) lattice reverse dataflow (for eliding stores at defines +%% in mode2) +-type rdefsi() :: #{label() => + {call, rdefseti(), [label()]} + | {nocall, rdefseti(), rdefseti(), [label()]}}. +-type rdefs() :: #{label() => {final, rdefsetf(), [label()]}}. + +-spec rdef_analyse(cfg()) -> rdefs(). +rdef_analyse(CFG = #cfg{rpo_labels=RPO}) -> + Defs0 = rdef_init(CFG), + PO = rdef_postorder(RPO, CFG, []), + rdef_dataf(PO, Defs0). + +%% Filter out 'call' labels, since they don't change +-spec rdef_postorder([label()], cfg(), [label()]) -> [label()]. +rdef_postorder([], _CFG, Acc) -> Acc; +rdef_postorder([L|Ls], CFG, Acc) -> + case bb_has_call(cfg_bb(L, CFG)) of + true -> rdef_postorder(Ls, CFG, Acc); + false -> rdef_postorder(Ls, CFG, [L|Acc]) + end. + +-spec rdef_init(cfg()) -> rdefsi(). +rdef_init(#cfg{bbs = BBs}) -> + maps:from_list( + [{L, case HasCall of + true -> + Defin = rdef_init_scan(bb_butlast(BB), rdefseti_empty()), + {call, Defin, Succs}; + false -> + Gen = rdef_init_scan(bb_code(BB), rdefseti_empty()), + {nocall, Gen, rdefseti_top(), Succs} + end} + || {L, BB = #bb{has_call=HasCall, succ=Succs}} <- maps:to_list(BBs)]). + +-spec rdef_init_scan([instr()], rdefseti()) -> rdefseti(). +rdef_init_scan([], Defset) -> Defset; +rdef_init_scan([#instr{def=Def}|Is], Defset0) -> + Defset = rdefseti_add_ordset(Def, Defset0), + rdef_init_scan(Is, Defset). + +-spec rdef_dataf([label()], rdefsi()) -> rdefs(). +rdef_dataf(Labels, Defs0) -> + case rdef_dataf_once(Labels, Defs0, 0) of + {Defs, 0} -> + rdef_finalise(Defs); + {Defs, _Changed} -> + rdef_dataf(Labels, Defs) + end. + +-spec rdef_finalise(rdefsi()) -> rdefs(). +rdef_finalise(Defs) -> + maps:map(fun(L, V) -> + Succs = rsuccs_val(V), + Defout0 = rdefout_intersect(L, Defs, rdefseti_top()), + {final, rdefset_finalise(Defout0), Succs} + end, Defs). + +-spec rdef_dataf_once([label()], rdefsi(), non_neg_integer()) + -> {rdefsi(), non_neg_integer()}. +rdef_dataf_once([], Defs, Changed) -> {Defs, Changed}; +rdef_dataf_once([L|Ls], Defs0, Changed0) -> + #{L := {nocall, Gen, Defin0, Succs}} = Defs0, + Defin = rdefseti_union(Gen, rdefout_intersect(L, Defs0, Defin0)), + Defset = {nocall, Gen, Defin, Succs}, + Changed = case Defin =:= Defin0 of + true -> Changed0; + false -> Changed0+1 + end, + rdef_dataf_once(Ls, Defs0#{L := Defset}, Changed). + +-spec rdefin(label(), rdefsi()) -> rdefseti(). +rdefin(L, Defs) -> rdefin_val(maps:get(L, Defs)). +rdefin_val({nocall, _Gen, Defin, _Succs}) -> Defin; +rdefin_val({call, Defin, _Succs}) -> Defin. + +-spec rsuccs(label(), rdefsi()) -> [label()]. +rsuccs(L, Defs) -> rsuccs_val(maps:get(L, Defs)). +rsuccs_val({nocall, _Gen, _Defin, Succs}) -> Succs; +rsuccs_val({call, _Defin, Succs}) -> Succs. + +-spec rdefout(label(), rdefs()) -> rdefsetf(). +rdefout(L, Defs) -> + #{L := {final, Defout, _Succs}} = Defs, + Defout. + +-spec rdefout_intersect(label(), rdefsi(), rdefseti()) -> rdefseti(). +rdefout_intersect(L, Defs, Init) -> + lists:foldl(fun(S, Acc) -> + rdefseti_intersect(rdefin(S, Defs), Acc) + end, Init, rsuccs(L, Defs)). + +-type rdefseti() :: bitord() | top. +rdefseti_top() -> top. +rdefseti_empty() -> bitord_new(). +-spec rdefseti_from_ordset(ordsets:ordset(temp())) -> rdefseti(). +rdefseti_from_ordset(OS) -> bitord_from_ordset(OS). + +-spec rdefseti_add_ordset(ordsets:ordset(temp()), rdefseti()) -> rdefseti(). +rdefseti_add_ordset(_, top) -> top; % Should never happen in rdef_dataf +rdefseti_add_ordset(OS, D) -> rdefseti_union(rdefseti_from_ordset(OS), D). + +-spec rdefseti_union(rdefseti(), rdefseti()) -> rdefseti(). +rdefseti_union(top, _) -> top; +rdefseti_union(_, top) -> top; +rdefseti_union(A, B) -> bitord_union(A, B). + +-spec rdefseti_intersect(rdefseti(), rdefseti()) -> rdefseti(). +rdefseti_intersect(top, D) -> D; +rdefseti_intersect(D, top) -> D; +rdefseti_intersect(A, B) -> bitord_intersect(A, B). + +-type rdefsetf() :: {arr, bitarr()} | top. +-spec rdefset_finalise(rdefseti()) -> rdefsetf(). +rdefset_finalise(top) -> top; +rdefset_finalise(Ord) -> {arr, bitarr_from_bitord(Ord)}. + +%% rdefsetf_top() -> top. +rdefsetf_empty() -> {arr, bitarr_new()}. + +-spec rdefsetf_add_ordset(ordsets:ordset(temp()), rdefsetf()) -> rdefsetf(). +rdefsetf_add_ordset(_, top) -> top; +rdefsetf_add_ordset(OS, {arr, Arr}) -> + {arr, lists:foldl(fun bitarr_set/2, Arr, OS)}. + +-spec rdef_step(instr(), rdefsetf()) -> rdefsetf(). +rdef_step(#instr{def=Def}, Defset) -> + %% ?ASSERT(not defines_all_alloc(I, Target)), + rdefsetf_add_ordset(Def, Defset). + +-spec ordset_subtract_rdefsetf(ordsets:ordset(temp()), rdefsetf()) + -> ordsets:ordset(temp()). +ordset_subtract_rdefsetf(_, top) -> []; +ordset_subtract_rdefsetf(OS, {arr, Arr}) -> + %% Lazy implementation; could do better if OS can grow + lists:filter(fun(E) -> not bitarr_get(E, Arr) end, OS). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Integer sets represented as bit sets +%% +%% Two representations; bitord() and bitarr() +-define(LIMB_IX_BITS, 11). +-define(LIMB_BITS, (1 bsl ?LIMB_IX_BITS)). +-define(LIMB_IX(Index), (Index bsr ?LIMB_IX_BITS)). +-define(BIT_IX(Index), (Index band (?LIMB_BITS - 1))). +-define(BIT_MASK(Index), (1 bsl ?BIT_IX(Index))). + +%% bitord(): fast at union/2 and can be compared for equality with '=:=' +-type bitord() :: orddict:orddict(non_neg_integer(), 0..((1 bsl ?LIMB_BITS)-1)). + +-spec bitord_new() -> bitord(). +bitord_new() -> []. + +-spec bitord_union(bitord(), bitord()) -> bitord(). +bitord_union(Lhs, Rhs) -> + orddict:merge(fun(_, L, R) -> L bor R end, Lhs, Rhs). + +-spec bitord_intersect(bitord(), bitord()) -> bitord(). +bitord_intersect([], _) -> []; +bitord_intersect(_, []) -> []; +bitord_intersect([{K, L}|Ls], [{K, R}|Rs]) -> + [{K, L band R} | bitord_intersect(Ls, Rs)]; +bitord_intersect([{LK, _}|Ls], [{RK, _}|_]=Rs) when LK < RK -> + bitord_intersect(Ls, Rs); +bitord_intersect([{LK, _}|_]=Ls, [{RK, _}|Rs]) when LK > RK -> + bitord_intersect(Ls, Rs). + +-spec bitord_from_ordset(ordsets:ordset(non_neg_integer())) -> bitord(). +bitord_from_ordset([]) -> []; +bitord_from_ordset([B|Bs]) -> + bitord_from_ordset_1(Bs, ?LIMB_IX(B), ?BIT_MASK(B)). + +bitord_from_ordset_1([B|Bs], Key, Val) when Key =:= ?LIMB_IX(B) -> + bitord_from_ordset_1(Bs, Key, Val bor ?BIT_MASK(B)); +bitord_from_ordset_1([B|Bs], Key, Val) -> + [{Key,Val} | bitord_from_ordset_1(Bs, ?LIMB_IX(B), ?BIT_MASK(B))]; +bitord_from_ordset_1([], Key, Val) -> [{Key, Val}]. + +%% bitarr(): fast (enough) at get/2 +-type bitarr() :: array:array(0..((1 bsl ?LIMB_BITS)-1)). + +-spec bitarr_new() -> bitarr(). +bitarr_new() -> array:new({default, 0}). + +-spec bitarr_get(non_neg_integer(), bitarr()) -> boolean(). +bitarr_get(Index, Array) -> + Limb = array:get(?LIMB_IX(Index), Array), + 0 =/= (Limb band ?BIT_MASK(Index)). + +-spec bitarr_set(non_neg_integer(), bitarr()) -> bitarr(). +bitarr_set(Index, Array) -> + Limb0 = array:get(?LIMB_IX(Index), Array), + Limb = Limb0 bor ?BIT_MASK(Index), + array:set(?LIMB_IX(Index), Limb, Array). + +-spec bitarr_from_bitord(bitord()) -> bitarr(). +bitarr_from_bitord(Ord) -> + array:from_orddict(Ord, 0). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Sixth pass: Partition-local liveness analysis +%% +%% As temps are not spilled when exiting a partition in mode2, only +%% partition-local uses need to be considered when deciding which temps need +%% restoring at partition entry. + +-type plive() :: #{label() => + {call, liveset(), [label()]} + | {nocall, {liveset(), liveset()}, liveset(), [label()]}}. + +-spec plive_analyse(cfg()) -> plive(). +plive_analyse(CFG) -> + Defs0 = plive_init(CFG), + PO = cfg_postorder(CFG), + plive_dataf(PO, Defs0). + +-spec plive_init(cfg()) -> plive(). +plive_init(#cfg{bbs = BBs}) -> + maps:from_list( + [begin + {L, case HasCall of + true -> + {Gen, _} = plive_init_scan(bb_code(BB)), + {call, Gen, Succs}; + false -> + GenKill = plive_init_scan(bb_code(BB)), + {nocall, GenKill, liveset_empty(), Succs} + end} + end || {L, BB = #bb{has_call=HasCall, succ=Succs}} <- maps:to_list(BBs)]). + +-spec plive_init_scan([instr()]) -> {liveset(), liveset()}. +plive_init_scan([]) -> {liveset_empty(), liveset_empty()}; +plive_init_scan([#instr{def=InstrKill, use=InstrGen}|Is]) -> + {Gen0, Kill0} = plive_init_scan(Is), + Gen1 = liveset_subtract(Gen0, InstrKill), + Gen = liveset_union(Gen1, InstrGen), + Kill1 = liveset_union(Kill0, InstrKill), + Kill = liveset_subtract(Kill1, InstrGen), + {Gen, Kill}. + +-spec plive_dataf([label()], plive()) -> plive(). +plive_dataf(Labels, PLive0) -> + case plive_dataf_once(Labels, PLive0, 0) of + {PLive, 0} -> PLive; + {PLive, _Changed} -> + plive_dataf(Labels, PLive) + end. + +-spec plive_dataf_once([label()], plive(), non_neg_integer()) -> + {plive(), non_neg_integer()}. +plive_dataf_once([], PLive, Changed) -> {PLive, Changed}; +plive_dataf_once([L|Ls], PLive0, Changed0) -> + Liveset = + case Liveset0 = maps:get(L, PLive0) of + {call, Livein, Succs} -> + {call, Livein, Succs}; + {nocall, {Gen, Kill} = GenKill, _OldLivein, Succs} -> + Liveout = pliveout(L, PLive0), + Livein = liveset_union(Gen, liveset_subtract(Liveout, Kill)), + {nocall, GenKill, Livein, Succs} + end, + Changed = case Liveset =:= Liveset0 of + true -> Changed0; + false -> Changed0+1 + end, + plive_dataf_once(Ls, PLive0#{L := Liveset}, Changed). + +-spec pliveout(label(), plive()) -> liveset(). +pliveout(L, PLive) -> + liveset_union([plivein(S, PLive) || S <- psuccs(L, PLive)]). + +-spec psuccs(label(), plive()) -> [label()]. +psuccs(L, PLive) -> psuccs_val(maps:get(L, PLive)). +psuccs_val({call, _Livein, Succs}) -> Succs; +psuccs_val({nocall, _GenKill, _Livein, Succs}) -> Succs. + +-spec plivein(label(), plive()) -> liveset(). +plivein(L, PLive) -> plivein_val(maps:get(L, PLive)). +plivein_val({call, Livein, _Succs}) -> Livein; +plivein_val({nocall, _GenKill, Livein, _Succs}) -> Livein. + +liveset_empty() -> ordsets:new(). +liveset_subtract(A, B) -> ordsets:subtract(A, B). +liveset_union(A, B) -> ordsets:union(A, B). +liveset_union(LivesetList) -> ordsets:union(LivesetList). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Third pass: Compute dataflow analyses required for placing mode3 +%% spills/restores. +%% Reuse analysis implementation in hipe_restore_reuse. +%% XXX: hipe_restore_reuse has it's own "rdef"; we would like to reuse that one +%% too. +-type avail() :: hipe_restore_reuse:avail(). + +-spec avail_analyse(target_cfg(), liveness(), target()) -> avail(). +avail_analyse(CFG, Liveness, Target) -> + hipe_restore_reuse:analyse(CFG, Liveness, Target). + +-spec mode3_split_in_block(label(), avail()) -> ordsets:ordset(temp()). +mode3_split_in_block(L, Avail) -> + hipe_restore_reuse:split_in_block(L, Avail). + +-spec mode3_block_renameset(label(), avail()) -> ordsets:ordset(temp()). +mode3_block_renameset(L, Avail) -> + hipe_restore_reuse:renamed_in_block(L, Avail). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Seventh pass +%% +%% Compute program space partitioning, collect information required by the +%% heuristic. +-type part_key() :: label(). +-type part_dsets() :: hipe_dsets:dsets(part_key()). +-type part_dsets_map() :: #{part_key() => part_key()}. +-type ducounts() :: #{part_key() => ducount()}. + +-spec scan(cfg(), liveness(), plive(), weights(), defs(), rdefs(), avail(), + target()) -> {cfg(), ducounts(), costs(), part_dsets()}. +scan(CFG0, Liveness, PLive, Weights, Defs, RDefs, Avail, Target) -> + #cfg{rpo_labels = Labels, bbs = BBs0} = CFG0, + CFG = CFG0#cfg{bbs=#{}}, % kill reference + DSets0 = hipe_dsets:new(Labels), + Costs0 = costs_new(), + {BBs, DUCounts0, Costs1, DSets1} = + scan_bbs(maps:to_list(BBs0), Liveness, PLive, Weights, Defs, RDefs, Avail, + Target, #{}, Costs0, DSets0, []), + {RLList, DSets2} = hipe_dsets:to_rllist(DSets1), + {Costs, DSets} = costs_map_roots(DSets2, Costs1), + DUCounts = collect_ducounts(RLList, DUCounts0, #{}), + {CFG#cfg{bbs=maps:from_list(BBs)}, DUCounts, Costs, DSets}. + +-spec collect_ducounts([{label(), [label()]}], ducounts(), ducounts()) + -> ducounts(). +collect_ducounts([], _, Acc) -> Acc; +collect_ducounts([{R,Ls}|RLs], DUCounts, Acc) -> + DUCount = lists:foldl( + fun(Key, FAcc) -> + ducount_merge(maps:get(Key, DUCounts, ducount_new()), FAcc) + end, ducount_new(), Ls), + collect_ducounts(RLs, DUCounts, Acc#{R => DUCount}). + +-spec scan_bbs([{label(), bb()}], liveness(), plive(), weights(), defs(), + rdefs(), avail(), target(), ducounts(), costs(), part_dsets(), + [{label(), bb()}]) + -> {[{label(), bb()}], ducounts(), costs(), part_dsets()}. +scan_bbs([], _Liveness, _PLive, _Weights, _Defs, _RDefs, _Avail, _Target, + DUCounts, Costs, DSets, Acc) -> + {Acc, DUCounts, Costs, DSets}; +scan_bbs([{L,BB}|BBs], Liveness, PLive, Weights, Defs, RDefs, Avail, Target, + DUCounts0, Costs0, DSets0, Acc) -> + Wt = weight(L, Weights), + {DSets, Costs5, EntryCode, ExitCode, RDefout, Liveout} = + case bb_has_call(BB) of + false -> + DSets1 = lists:foldl(fun(S, DS) -> hipe_dsets:union(L, S, DS) end, + DSets0, bb_succ(BB)), + {DSets1, Costs0, bb_code(BB), [], rdefout(L, RDefs), + liveout(Liveness, L, Target)}; + true -> + LastI = #instr{def=LastDef} = bb_last(BB), + LiveBefore = ordsets:subtract(liveout(Liveness, L, Target), LastDef), + %% We can omit the spill of a temp that has not been defined since the + %% last time it was spilled + SpillSet = defsetf_intersect_ordset(LiveBefore, defbutlast(L, Defs)), + Costs1 = costs_insert(exit, L, Wt, SpillSet, Costs0), + Costs4 = lists:foldl(fun({S, BranchWt}, Costs2) -> + SLivein = livein(Liveness, S, Target), + SPLivein = plivein(S, PLive), + SWt = weight_scaled(L, BranchWt, Weights), + Costs3 = costs_insert(entry1, S, SWt, SLivein, Costs2), + costs_insert(entry2, S, SWt, SPLivein, Costs3) + end, Costs1, branch_preds(LastI#instr.i, Target)), + {DSets0, Costs4, bb_butlast(BB), [LastI], rdefsetf_empty(), LiveBefore} + end, + Mode3Splits = mode3_split_in_block(L, Avail), + {RevEntryCode, Restored} = scan_bb_fwd(EntryCode, Mode3Splits, [], []), + {Code, DUCount, Mode2Spills} = + scan_bb(RevEntryCode, Wt, RDefout, Liveout, ducount_new(), [], ExitCode), + DUCounts = DUCounts0#{L => DUCount}, + M2SpillSet = ordsets:from_list(Mode2Spills), + Costs6 = costs_insert(spill, L, Wt, M2SpillSet, Costs5), + Mode3Renames = mode3_block_renameset(L, Avail), + Costs7 = costs_insert(restore, L, Wt, ordsets:intersection(M2SpillSet, Mode3Renames), Costs6), + Costs8 = costs_insert(restore, L, Wt, ordsets:from_list(Restored), Costs7), + Costs = add_unsplit_mode3_costs(DUCount, Mode3Renames, L, Costs8), + scan_bbs(BBs, Liveness, PLive, Weights, Defs, RDefs, Avail, Target, DUCounts, + Costs, DSets, [{L,BB#bb{code=Code}}|Acc]). + +-spec add_unsplit_mode3_costs(ducount(), ordsets:ordset(temp()), label(), costs()) + -> costs(). +add_unsplit_mode3_costs(DUCount, Mode3Renames, L, Costs) -> + Unsplit = orddict_without_ordset(Mode3Renames, + orddict:from_list(ducount_to_list(DUCount))), + add_unsplit_mode3_costs_1(Unsplit, L, Costs). + +-spec add_unsplit_mode3_costs_1([{temp(),float()}], label(), costs()) + -> costs(). +add_unsplit_mode3_costs_1([], _L, Costs) -> Costs; +add_unsplit_mode3_costs_1([{T,C}|Cs], L, Costs) -> + add_unsplit_mode3_costs_1(Cs, L, costs_insert(restore, L, C, [T], Costs)). + +%% @doc Returns a new orddict without keys in Set and their associated values. +-spec orddict_without_ordset(ordsets:ordset(K), orddict:orddict(K, V)) + -> orddict:orddict(K, V). +orddict_without_ordset([S|Ss], [{K,_}|_]=Dict) when S < K -> + orddict_without_ordset(Ss, Dict); +orddict_without_ordset([S|_]=Set, [D={K,_}|Ds]) when S > K -> + [D|orddict_without_ordset(Set, Ds)]; +orddict_without_ordset([_S|Ss], [{_K,_}|Ds]) -> % _S == _K + orddict_without_ordset(Ss, Ds); +orddict_without_ordset(_, []) -> []; +orddict_without_ordset([], Dict) -> Dict. + +%% Scans the code forward, collecting and inserting mode3 restores +-spec scan_bb_fwd([instr()], ordsets:ordset(temp()), ordsets:ordset(temp()), + [code_elem()]) + -> {[code_elem()], ordsets:ordset(temp())}. +scan_bb_fwd([], [], Restored, Acc) -> {Acc, Restored}; +scan_bb_fwd([I|Is], SplitHere0, Restored0, Acc0) -> + #instr{def=Def, use=Use} = I, + {ToRestore, SplitHere1} = + lists:partition(fun(R) -> lists:member(R, Use) end, SplitHere0), + SplitHere = lists:filter(fun(R) -> not lists:member(R, Def) end, SplitHere1), + Acc = + case ToRestore of + [] -> [I | Acc0]; + _ -> [I, #mode3_restores{temps=ToRestore} | Acc0] + end, + scan_bb_fwd(Is, SplitHere, ToRestore ++ Restored0, Acc). + +%% Scans the code backwards, collecting def/use counts and mode2 spills +-spec scan_bb([code_elem()], float(), rdefsetf(), liveset(), ducount(), + [temp()], [code_elem()]) + -> {[code_elem()], ducount(), [temp()]}. +scan_bb([], _Wt, _RDefout, _Liveout, DUCount, Spills, Acc) -> + {Acc, DUCount, Spills}; +scan_bb([I=#mode3_restores{}|Is], Wt, RDefout, Liveout, DUCount, Spills, Acc) -> + scan_bb(Is, Wt, RDefout, Liveout, DUCount, Spills, [I|Acc]); +scan_bb([I|Is], Wt, RDefout, Liveout, DUCount0, Spills0, Acc0) -> + #instr{def=Def,use=Use} = I, + DUCount = ducount_add(Use, Wt, ducount_add(Def, Wt, DUCount0)), + Livein = liveness_step(I, Liveout), + RDefin = rdef_step(I, RDefout), + %% The temps that would be spilled after I in mode 2 + NewSpills = ordset_subtract_rdefsetf( + ordsets:intersection(Def, Liveout), + RDefout), + ?ASSERT(NewSpills =:= (NewSpills -- Spills0)), + Spills = NewSpills ++ Spills0, + Acc1 = case NewSpills of + [] -> Acc0; + _ -> [#mode2_spills{temps=NewSpills}|Acc0] + end, + scan_bb(Is, Wt, RDefin, Livein, DUCount, Spills, [I|Acc1]). + +-spec liveness_step(instr(), liveset()) -> liveset(). +liveness_step(#instr{def=Def, use=Use}, Liveout) -> + ordsets:union(Use, ordsets:subtract(Liveout, Def)). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% First pass: compute basic-block weighting + +-type weights() :: no_bb_weights + | {hipe_bb_weights:bb_weights(), float()}. + +-spec weight(label(), weights()) -> float(). +weight(L, Weights) -> weight_scaled(L, 1.0, Weights). + +-spec compute_weights(target_cfg(), target_module(), target_context(), + comp_options()) -> weights(). +compute_weights(CFG, TargetMod, TargetContext, Options) -> + case proplists:get_bool(range_split_weights, Options) of + false -> no_bb_weights; + true -> + {hipe_bb_weights:compute(CFG, TargetMod, TargetContext), + ?WEIGHT_CONST_FUN(proplists:get_value(range_split_weight_power, + Options, ?DEFAULT_WEIGHT_POWER))} + end. + +-spec weight_scaled(label(), float(), weights()) -> float(). +weight_scaled(_L, _Scale, no_bb_weights) -> 1.0; +weight_scaled(L, Scale, {Weights, Const}) -> + Wt0 = hipe_bb_weights:weight(L, Weights) * Scale, + Wt = erlang:min(erlang:max(Wt0, 0.0000000000000000001), 10000.0), + ?WEIGHT_FUN(Wt, Const). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Heuristic splitting decision. +%% +%% Decide which temps to split, in which parts, and pick new names for them. +-type spill_mode() :: mode1 % Spill temps at partition exits + | mode2 % Spill temps at definitions + | mode3.% Spill temps at definitions, restore temps at uses +-type ren() :: #{temp() => {spill_mode(), temp()}}. +-type renames() :: #{label() => ren()}. + +-record(heur_par, { + mode1_fudge :: float(), + min_gain :: float() + }). +-type heur_par() :: #heur_par{}. + +-spec decide(ducounts(), costs(), target(), comp_options()) -> renames(). +decide(DUCounts, Costs, Target, Options) -> + Par = #heur_par{ + mode1_fudge = proplists:get_value(range_split_mode1_fudge, Options, + ?DEFAULT_MODE1_FUDGE), + min_gain = proplists:get_value(range_split_min_gain, Options, + ?DEFAULT_MIN_GAIN)}, + decide_parts(maps:to_list(DUCounts), Costs, Target, Par, #{}). + +-spec decide_parts([{part_key(), ducount()}], costs(), target(), + heur_par(), renames()) + -> renames(). +decide_parts([], _Costs, _Target, _Par, Acc) -> Acc; +decide_parts([{Part,DUCount}|Ps], Costs, Target, Par, Acc) -> + Spills = decide_temps(ducount_to_list(DUCount), Part, Costs, Target, Par, + #{}), + decide_parts(Ps, Costs, Target, Par, Acc#{Part => Spills}). + +-spec decide_temps([{temp(), float()}], part_key(), costs(), target(), + heur_par(), ren()) + -> ren(). +decide_temps([], _Part, _Costs, _Target, _Par, Acc) -> Acc; +decide_temps([{Temp, SpillGain}|Ts], Part, Costs, Target, Par, Acc0) -> + SpillCost1 = costs_query(Temp, entry1, Part, Costs) + + costs_query(Temp, exit, Part, Costs), + SpillCost2 = costs_query(Temp, entry2, Part, Costs) + + costs_query(Temp, spill, Part, Costs), + SpillCost3 = costs_query(Temp, restore, Part, Costs), + Acc = + %% SpillCost1 =:= 0.0 usually means the temp is local to the partition; + %% hence no need to split it + case (SpillCost1 =/= 0.0) %% maps:is_key(Temp, S) + andalso (not is_precoloured(Temp, Target)) + andalso ((Par#heur_par.min_gain*SpillCost1 < SpillGain) + orelse (Par#heur_par.min_gain*SpillCost2 < SpillGain) + orelse (Par#heur_par.min_gain*SpillCost3 < SpillGain)) + of + false -> Acc0; + true -> + Mode = + if Par#heur_par.mode1_fudge*SpillCost1 < SpillCost2, + Par#heur_par.mode1_fudge*SpillCost1 < SpillCost3 -> + mode1; + SpillCost2 < SpillCost3 -> + mode2; + true -> + mode3 + end, + Acc0#{Temp => {Mode, new_reg_nr(Target)}} + end, + decide_temps(Ts, Part, Costs, Target, Par, Acc). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Eighth pass: Rewrite program performing range splitting. + +-spec rewrite(cfg(), target_cfg(), target(), liveness(), plive(), defs(), + avail(), part_dsets_map(), renames(), temps()) + -> target_cfg(). +rewrite(#cfg{bbs=BBs}, TCFG, Target, Liveness, PLive, Defs, Avail, DSets, + Renames, Temps) -> + rewrite_bbs(maps:to_list(BBs), Target, Liveness, PLive, Defs, Avail, DSets, + Renames, Temps, TCFG). + +-spec rewrite_bbs([{label(), bb()}], target(), liveness(), plive(), defs(), + avail(), part_dsets_map(), renames(), temps(), target_cfg()) + -> target_cfg(). +rewrite_bbs([], _Target, _Liveness, _PLive, _Defs, _Avail, _DSets, _Renames, + _Temps, TCFG) -> + TCFG; +rewrite_bbs([{L,BB}|BBs], Target, Liveness, PLive, Defs, Avail, DSets, Renames, + Temps, TCFG0) -> + Code0Rev = lists:reverse(bb_code(BB)), + EntryRen = maps:get(maps:get(L,DSets), Renames), + M3Ren = mode3_block_renameset(L, Avail), + SubstFun = rewrite_subst_fun(Target, EntryRen, M3Ren), + Fun = fun(I) -> subst_temps(SubstFun, I, Target) end, + {Code, TCFG} = + case bb_has_call(BB) of + false -> + Code1 = rewrite_instrs(Code0Rev, Fun, EntryRen, M3Ren, Temps, Target, + []), + {Code1, TCFG0}; + true -> + CallI0 = hd(Code0Rev), + Succ = bb_succ(BB), + {CallTI, TCFG1} = inject_restores(Succ, Target, Liveness, PLive, DSets, + Renames, Temps, CallI0#instr.i, TCFG0), + Liveout1 = liveness_step(CallI0, liveout(Liveness, L, Target)), + Defout = defbutlast(L, Defs), + SpillMap = mk_spillmap(EntryRen, Liveout1, Defout, Temps, Target), + Code1 = rewrite_instrs(tl(Code0Rev), Fun, EntryRen, M3Ren, Temps, + Target, []), + Code2 = lift_spills(lists:reverse(Code1), Target, SpillMap, [CallTI]), + {Code2, TCFG1} + end, + TBB = hipe_bb:code_update(bb(TCFG, L, Target), Code), + rewrite_bbs(BBs, Target, Liveness, PLive, Defs, Avail, DSets, Renames, Temps, + update_bb(TCFG, L, TBB, Target)). + +-spec rewrite_instrs([code_elem()], rewrite_fun(), ren(), + ordsets:ordset(temp()), temps(), target(), + [target_instr()]) + -> [target_instr()]. +rewrite_instrs([], _Fun, _Ren, _M3Ren, _Temps, _Target, Acc) -> Acc; +rewrite_instrs([I|Is], Fun, Ren, M3Ren, Temps, Target, Acc0) -> + Acc = + case I of + #instr{i=TI} -> [Fun(TI)|Acc0]; + #mode2_spills{temps=Mode2Spills} -> + add_mode2_spills(Mode2Spills, Target, Ren, M3Ren, Temps, Acc0); + #mode3_restores{temps=Mode3Restores} -> + add_mode3_restores(Mode3Restores, Target, Ren, Temps, Acc0) + end, + rewrite_instrs(Is, Fun, Ren, M3Ren, Temps, Target, Acc). + +-spec add_mode2_spills(ordsets:ordset(temp()), target(), ren(), + ordsets:ordset(temp()), temps(), [target_instr()]) + -> [target_instr()]. +add_mode2_spills([], _Target, _Ren, _M3Ren, _Temps, Acc) -> Acc; +add_mode2_spills([R|Rs], Target, Ren, M3Ren, Temps, Acc0) -> + Acc = + case Ren of + #{R := {Mode, NewName}} when Mode =:= mode2; Mode =:= mode3 -> + case Mode =/= mode3 orelse lists:member(R, M3Ren) of + false -> Acc0; + true -> + #{R := T} = Temps, + SpillInstr = mk_move(update_reg_nr(NewName, T, Target), T, Target), + [SpillInstr|Acc0] + end; + #{} -> + Acc0 + end, + add_mode2_spills(Rs, Target, Ren, M3Ren, Temps, Acc). + +-spec add_mode3_restores(ordsets:ordset(temp()), target(), ren(), temps(), + [target_instr()]) + -> [target_instr()]. +add_mode3_restores([], _Target, _Ren, _Temps, Acc) -> Acc; +add_mode3_restores([R|Rs], Target, Ren, Temps, Acc) -> + case Ren of + #{R := {mode3, NewName}} -> + #{R := T} = Temps, + RestoreInstr = mk_move(T, update_reg_nr(NewName, T, Target), Target), + add_mode3_restores(Rs, Target, Ren, Temps, [RestoreInstr|Acc]); + #{} -> + add_mode3_restores(Rs, Target, Ren, Temps, Acc) + end. + +-type rewrite_fun() :: fun((target_instr()) -> target_instr()). +-type subst_fun() :: fun((target_temp()) -> target_temp()). +-spec rewrite_subst_fun(target(), ren(), ordsets:ordset(temp())) -> subst_fun(). +rewrite_subst_fun(Target, Ren, M3Ren) -> + fun(Temp) -> + Reg = reg_nr(Temp, Target), + case Ren of + #{Reg := {Mode, NewName}} -> + case Mode =/= mode3 orelse lists:member(Reg, M3Ren) of + false -> Temp; + true -> update_reg_nr(NewName, Temp, Target) + end; + #{} -> Temp + end + end. + +-type spillmap() :: [{temp(), target_instr()}]. +-spec mk_spillmap(ren(), liveset(), defsetf(), temps(), target()) + -> spillmap(). +mk_spillmap(Ren, Livein, Defout, Temps, Target) -> + [begin + Temp = maps:get(Reg, Temps), + {NewName, mk_move(update_reg_nr(NewName, Temp, Target), Temp, Target)} + end || {Reg, {mode1, NewName}} <- maps:to_list(Ren), + lists:member(Reg, Livein), defsetf_member(Reg, Defout)]. + +-spec mk_restores(ren(), liveset(), liveset(), temps(), target()) + -> [target_instr()]. +mk_restores(Ren, Livein, PLivein, Temps, Target) -> + [begin + Temp = maps:get(Reg, Temps), + mk_move(Temp, update_reg_nr(NewName, Temp, Target), Target) + end || {Reg, {Mode, NewName}} <- maps:to_list(Ren), + ( (Mode =:= mode1 andalso lists:member(Reg, Livein )) + orelse (Mode =:= mode2 andalso lists:member(Reg, PLivein)))]. + +-spec inject_restores([label()], target(), liveness(), plive(), + part_dsets_map(), renames(), temps(), target_instr(), + target_cfg()) + -> {target_instr(), target_cfg()}. +inject_restores([], _Target, _Liveness, _PLive, _DSets, _Renames, _Temps, CFTI, + TCFG) -> + {CFTI, TCFG}; +inject_restores([L|Ls], Target, Liveness, PLive, DSets, Renames, Temps, CFTI0, + TCFG0) -> + Ren = maps:get(maps:get(L,DSets), Renames), + Livein = livein(Liveness, L, Target), + PLivein = plivein(L, PLive), + {CFTI, TCFG} = + case mk_restores(Ren, Livein, PLivein, Temps, Target) of + [] -> {CFTI0, TCFG0}; % optimisation + Restores -> + RestBBLbl = new_label(Target), + Code = Restores ++ [mk_goto(L, Target)], + CFTI1 = redirect_jmp(CFTI0, L, RestBBLbl, Target), + TCFG1 = update_bb(TCFG0, RestBBLbl, hipe_bb:mk_bb(Code), Target), + {CFTI1, TCFG1} + end, + inject_restores(Ls, Target, Liveness, PLive, DSets, Renames, Temps, CFTI, + TCFG). + +%% Heuristic. Move spills up until we meet the edge of the BB or a definition of +%% that temp. +-spec lift_spills([target_instr()], target(), spillmap(), [target_instr()]) + -> [target_instr()]. +lift_spills([], _Target, SpillMap, Acc) -> + [SpillI || {_, SpillI} <- SpillMap] ++ Acc; +lift_spills([I|Is], Target, SpillMap0, Acc) -> + Def = reg_defines(I, Target), + {Spills0, SpillMap} = + lists:partition(fun({Reg,_}) -> lists:member(Reg, Def) end, SpillMap0), + Spills = [SpillI || {_, SpillI} <- Spills0], + lift_spills(Is, Target, SpillMap, [I|Spills ++ Acc]). + +reg_defines(I, Target) -> + reg_names(defines(I,Target), Target). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Costs ADT +%% +%% Keeps track of cumulative cost of spilling temps in particular partitions +%% using particular spill modes. +-type cost_map() :: #{[part_key()|temp()] => float()}. +-type cost_key() :: entry1 | entry2 | exit | spill | restore. +-record(costs, {entry1 = #{} :: cost_map() + ,entry2 = #{} :: cost_map() + ,exit = #{} :: cost_map() + ,spill = #{} :: cost_map() + ,restore = #{} :: cost_map() + }). +-type costs() :: #costs{}. + +-spec costs_new() -> costs(). +costs_new() -> #costs{}. + +-spec costs_insert(cost_key(), part_key(), float(), liveset(), costs()) + -> costs(). +costs_insert(entry1, A, Weight, Liveset, Costs=#costs{entry1=Entry1}) -> + Costs#costs{entry1=costs_insert_1(A, Weight, Liveset, Entry1)}; +costs_insert(entry2, A, Weight, Liveset, Costs=#costs{entry2=Entry2}) -> + Costs#costs{entry2=costs_insert_1(A, Weight, Liveset, Entry2)}; +costs_insert(exit, A, Weight, Liveset, Costs=#costs{exit=Exit}) -> + Costs#costs{exit=costs_insert_1(A, Weight, Liveset, Exit)}; +costs_insert(spill, A, Weight, Liveset, Costs=#costs{spill=Spill}) -> + Costs#costs{spill=costs_insert_1(A, Weight, Liveset, Spill)}; +costs_insert(restore, A, Weight, Liveset, Costs=#costs{restore=Restore}) -> + Costs#costs{restore=costs_insert_1(A, Weight, Liveset, Restore)}. + +costs_insert_1(A, Weight, Liveset, CostMap0) when is_float(Weight) -> + lists:foldl(fun(Live, CostMap1) -> + map_update_counter([A|Live], Weight, CostMap1) + end, CostMap0, Liveset). + +-spec costs_map_roots(part_dsets(), costs()) -> {costs(), part_dsets()}. +costs_map_roots(DSets0, Costs) -> + {Entry1, DSets1} = costs_map_roots_1(DSets0, Costs#costs.entry1), + {Entry2, DSets2} = costs_map_roots_1(DSets1, Costs#costs.entry2), + {Exit, DSets3} = costs_map_roots_1(DSets2, Costs#costs.exit), + {Spill, DSets4} = costs_map_roots_1(DSets3, Costs#costs.spill), + {Restore, DSets} = costs_map_roots_1(DSets4, Costs#costs.restore), + {#costs{entry1=Entry1,entry2=Entry2,exit=Exit,spill=Spill,restore=Restore}, + DSets}. + +costs_map_roots_1(DSets0, CostMap) -> + {NewEs, DSets} = lists:mapfoldl(fun({[A|T], Wt}, DSets1) -> + {AR, DSets2} = hipe_dsets:find(A, DSets1), + {{[AR|T], Wt}, DSets2} + end, DSets0, maps:to_list(CostMap)), + {maps_from_list_merge(NewEs, fun erlang:'+'/2, #{}), DSets}. + +maps_from_list_merge([], _MF, Acc) -> Acc; +maps_from_list_merge([{K,V}|Ps], MF, Acc) -> + maps_from_list_merge(Ps, MF, case Acc of + #{K := OV} -> Acc#{K := MF(V, OV)}; + #{} -> Acc#{K => V} + end). + +-spec costs_query(temp(), cost_key(), part_key(), costs()) -> float(). +costs_query(Temp, entry1, Part, #costs{entry1=Entry1}) -> + costs_query_1(Temp, Part, Entry1); +costs_query(Temp, entry2, Part, #costs{entry2=Entry2}) -> + costs_query_1(Temp, Part, Entry2); +costs_query(Temp, exit, Part, #costs{exit=Exit}) -> + costs_query_1(Temp, Part, Exit); +costs_query(Temp, spill, Part, #costs{spill=Spill}) -> + costs_query_1(Temp, Part, Spill); +costs_query(Temp, restore, Part, #costs{restore=Restore}) -> + costs_query_1(Temp, Part, Restore). + +costs_query_1(Temp, Part, CostMap) -> + Key = [Part|Temp], + case CostMap of + #{Key := Wt} -> Wt; + #{} -> 0.0 + end. + +-spec map_update_counter(Key, number(), #{Key => number(), OK => OV}) + -> #{Key := number(), OK => OV}. +map_update_counter(Key, Incr, Map) -> + case Map of + #{Key := Orig} -> Map#{Key := Orig + Incr}; + #{} -> Map#{Key => Incr} + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Def and use counting ADT +-type ducount() :: #{temp() => float()}. + +-spec ducount_new() -> ducount(). +ducount_new() -> #{}. + +-spec ducount_add([temp()], float(), ducount()) -> ducount(). +ducount_add([], _Weight, DUCount) -> DUCount; +ducount_add([T|Ts], Weight, DUCount0) -> + DUCount = + case DUCount0 of + #{T := Count} -> DUCount0#{T := Count + Weight}; + #{} -> DUCount0#{T => Weight} + end, + ducount_add(Ts, Weight, DUCount). + +ducount_to_list(DUCount) -> maps:to_list(DUCount). + +-spec ducount_merge(ducount(), ducount()) -> ducount(). +ducount_merge(DCA, DCB) when map_size(DCA) < map_size(DCB) -> + ducount_merge_1(ducount_to_list(DCA), DCB); +ducount_merge(DCA, DCB) when map_size(DCA) >= map_size(DCB) -> + ducount_merge_1(ducount_to_list(DCB), DCA). + +ducount_merge_1([], DUCount) -> DUCount; +ducount_merge_1([{T,AC}|Ts], DUCount0) -> + DUCount = + case DUCount0 of + #{T := BC} -> DUCount0#{T := AC + BC}; + #{} -> DUCount0#{T => AC} + end, + ducount_merge_1(Ts, DUCount). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Target module interface functions +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-define(TGT_IFACE_0(N), N( {M,C}) -> M:N( C)). +-define(TGT_IFACE_1(N), N(A1, {M,C}) -> M:N(A1, C)). +-define(TGT_IFACE_2(N), N(A1,A2, {M,C}) -> M:N(A1,A2, C)). +-define(TGT_IFACE_3(N), N(A1,A2,A3,{M,C}) -> M:N(A1,A2,A3,C)). + +?TGT_IFACE_2(bb). +?TGT_IFACE_1(def_use). +?TGT_IFACE_1(defines). +?TGT_IFACE_1(defines_all_alloc). +?TGT_IFACE_1(is_precoloured). +?TGT_IFACE_1(mk_goto). +?TGT_IFACE_2(mk_move). +?TGT_IFACE_0(new_label). +?TGT_IFACE_0(new_reg_nr). +?TGT_IFACE_1(number_of_temporaries). +?TGT_IFACE_3(redirect_jmp). +?TGT_IFACE_1(reg_nr). +?TGT_IFACE_1(reverse_postorder). +?TGT_IFACE_2(subst_temps). +?TGT_IFACE_3(update_bb). +?TGT_IFACE_2(update_reg_nr). + +branch_preds(Instr, {TgtMod,TgtCtx}) -> + merge_sorted_preds(lists:keysort(1, TgtMod:branch_preds(Instr, TgtCtx))). + +livein(Liveness, L, Target={TgtMod,TgtCtx}) -> + ordsets:from_list(reg_names(TgtMod:livein(Liveness, L, TgtCtx), Target)). + +liveout(Liveness, L, Target={TgtMod,TgtCtx}) -> + ordsets:from_list(reg_names(TgtMod:liveout(Liveness, L, TgtCtx), Target)). + +merge_sorted_preds([]) -> []; +merge_sorted_preds([{L, P1}, {L, P2}|LPs]) -> + merge_sorted_preds([{L, P1+P2}|LPs]); +merge_sorted_preds([LP|LPs]) -> [LP|merge_sorted_preds(LPs)]. + +reg_names(Regs, {TgtMod,TgtCtx}) -> + [TgtMod:reg_nr(X,TgtCtx) || X <- Regs]. diff --git a/lib/hipe/regalloc/hipe_reg_worklists.erl b/lib/hipe/regalloc/hipe_reg_worklists.erl index 88585f9f38..415f1d6122 100644 --- a/lib/hipe/regalloc/hipe_reg_worklists.erl +++ b/lib/hipe/regalloc/hipe_reg_worklists.erl @@ -1,9 +1,5 @@ %%% -*- erlang-indent-level: 2 -*- %%% -%%% %CopyrightBegin% -%%% -%%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%%% %%% Licensed under the Apache License, Version 2.0 (the "License"); %%% you may not use this file except in compliance with the License. %%% You may obtain a copy of the License at @@ -15,8 +11,6 @@ %%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %%% See the License for the specific language governing permissions and %%% limitations under the License. -%%% -%%% %CopyrightEnd% %%% %%%---------------------------------------------------------------------- %%% File : hipe_reg_worklists.erl @@ -30,8 +24,8 @@ -module(hipe_reg_worklists). -author(['Andreas Wallin', 'Thorild Selén']). --export([new/5, % only used by optimistic allocator - new/6, +-export([new/6, % only used by optimistic allocator + new/7, simplify/1, spill/1, freeze/1, @@ -90,29 +84,32 @@ %% %%%---------------------------------------------------------------------- -new(IG, Target, CFG, K, No_temporaries) -> % only used by optimistic allocator +%% only used by optimistic allocator +new(IG, TargetMod, TargetCtx, CFG, K, No_temporaries) -> CoalescedTo = hipe_bifs:array(No_temporaries, 'none'), - init(initial(Target, CFG), K, IG, empty(No_temporaries, CoalescedTo)). + init(initial(TargetMod, TargetCtx, CFG), K, IG, + empty(No_temporaries, CoalescedTo)). -new(IG, Target, CFG, Move_sets, K, No_temporaries) -> - init(initial(Target, CFG), K, IG, Move_sets, empty(No_temporaries, [])). +new(IG, TargetMod, TargetCtx, CFG, Move_sets, K, No_temporaries) -> + init(initial(TargetMod, TargetCtx, CFG), K, IG, Move_sets, + empty(No_temporaries, [])). -initial(Target, CFG) -> - {Min_temporary, Max_temporary} = Target:var_range(CFG), - NonAlloc = Target:non_alloc(CFG), - non_precoloured(Target, Min_temporary, Max_temporary, []) - -- [Target:reg_nr(X) || X <- NonAlloc]. +initial(TargetMod, TargetCtx, CFG) -> + {Min_temporary, Max_temporary} = TargetMod:var_range(CFG, TargetCtx), + NonAlloc = TargetMod:non_alloc(CFG, TargetCtx), + non_precoloured(TargetMod, TargetCtx, Min_temporary, Max_temporary, []) + -- [TargetMod:reg_nr(X, TargetCtx) || X <- NonAlloc]. -non_precoloured(Target, Current, Max_temporary, Initial) -> +non_precoloured(TargetMod, TargetCtx, Current, Max_temporary, Initial) -> if Current > Max_temporary -> Initial; true -> NewInitial = - case Target:is_precoloured(Current) of + case TargetMod:is_precoloured(Current, TargetCtx) of true -> Initial; false -> [Current|Initial] end, - non_precoloured(Target, Current+1, Max_temporary, NewInitial) + non_precoloured(TargetMod, TargetCtx, Current+1, Max_temporary, NewInitial) end. %% construct an empty initialized worklists data structure diff --git a/lib/hipe/regalloc/hipe_regalloc_loop.erl b/lib/hipe/regalloc/hipe_regalloc_loop.erl index d29615a3a0..29ef3adcc2 100644 --- a/lib/hipe/regalloc/hipe_regalloc_loop.erl +++ b/lib/hipe/regalloc/hipe_regalloc_loop.erl @@ -1,9 +1,5 @@ %%% -*- erlang-indent-level: 2 -*- %%% -%%% %CopyrightBegin% -%%% -%%% Copyright Ericsson AB 2004-2016. All Rights Reserved. -%%% %%% Licensed under the Apache License, Version 2.0 (the "License"); %%% you may not use this file except in compliance with the License. %%% You may obtain a copy of the License at @@ -15,44 +11,50 @@ %%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %%% See the License for the specific language governing permissions and %%% limitations under the License. -%%% -%%% %CopyrightEnd% %%% %%% Common wrapper for graph_coloring and coalescing regallocs. -module(hipe_regalloc_loop). --export([ra/5, ra_fp/4]). +-export([ra/7, ra_fp/6]). %%-define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation. -include("../main/hipe.hrl"). -ra(Defun, SpillIndex, Options, RegAllocMod, TargetMod) -> - {NewDefun, Coloring, _NewSpillIndex} = - ra_common(Defun, SpillIndex, Options, RegAllocMod, TargetMod), - {NewDefun, Coloring}. +ra(CFG, Liveness0, SpillIndex, Options, RegAllocMod, TargetMod, TargetCtx) -> + {NewCFG, Liveness, Coloring, _NewSpillIndex} = + ra_common(CFG, Liveness0, SpillIndex, Options, RegAllocMod, TargetMod, + TargetCtx), + {NewCFG, Liveness, Coloring}. -ra_fp(Defun, Options, RegAllocMod, TargetMod) -> - ra_common(Defun, 0, Options, RegAllocMod, TargetMod). +ra_fp(CFG, Liveness, Options, RegAllocMod, TargetMod, TargetCtx) -> + ra_common(CFG, Liveness, 0, Options, RegAllocMod, TargetMod, TargetCtx). -ra_common(Defun, SpillIndex, Options, RegAllocMod, TargetMod) -> +ra_common(CFG0, Liveness0, SpillIndex, Options, RegAllocMod, TargetMod, + TargetCtx) -> ?inc_counter(ra_calls_counter, 1), - CFG = TargetMod:defun_to_cfg(Defun), - SpillLimit = TargetMod:number_of_temporaries(CFG), - alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod). + {CFG1, Liveness1} = + do_range_split(CFG0, Liveness0, TargetMod, TargetCtx, Options), + SpillLimit0 = TargetMod:number_of_temporaries(CFG1, TargetCtx), + {Coloring, _, CFG, Liveness} = + call_allocator_initial(CFG1, Liveness1, SpillLimit0, SpillIndex, Options, + RegAllocMod, TargetMod, TargetCtx), + %% The first iteration, the hipe_regalloc_prepass may create new temps, these + %% should not end up above SpillLimit. + SpillLimit = TargetMod:number_of_temporaries(CFG, TargetCtx), + alloc(Coloring, CFG, Liveness, SpillLimit, SpillIndex, Options, + RegAllocMod, TargetMod, TargetCtx). -alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) -> +alloc(Coloring, CFG0, Liveness, SpillLimit, SpillIndex, Options, + RegAllocMod, TargetMod, TargetCtx) -> ?inc_counter(ra_iteration_counter, 1), - CFG = TargetMod:defun_to_cfg(Defun), - {Coloring, _NewSpillIndex} = - RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit, TargetMod, Options), - {NewDefun, DidSpill} = TargetMod:check_and_rewrite(Defun, Coloring), + {CFG, DidSpill} = TargetMod:check_and_rewrite(CFG0, Coloring, TargetCtx), case DidSpill of false -> %% No new temps, we are done. ?add_spills(Options, _NewSpillIndex), - TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod), - {TempMap2, NewSpillIndex2} = - hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options, - TargetMod, TempMap), + TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod, TargetCtx), + {TempMap2, NewSpillIndex2} = + hipe_spillmin:stackalloc(CFG0, Liveness, [], SpillIndex, Options, + TargetMod, TargetCtx, TempMap), Coloring2 = hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2), %% case proplists:get_bool(verbose_spills, Options) of @@ -61,9 +63,55 @@ alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) -> %% false -> %% ok %% end, - {NewDefun, Coloring2, NewSpillIndex2}; + {CFG, Liveness, Coloring2, NewSpillIndex2}; _ -> %% Since SpillLimit is used as a low-water-mark %% the list of temps not to spill is uninteresting. - alloc(NewDefun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) + {NewColoring, _NewSpillIndex} = + call_allocator(CFG, Liveness, SpillLimit, SpillIndex, Options, + RegAllocMod, TargetMod, TargetCtx), + alloc(NewColoring, CFG, Liveness, SpillLimit, SpillIndex, Options, + RegAllocMod, TargetMod, TargetCtx) + end. + +call_allocator_initial(CFG, Liveness, SpillLimit, SpillIndex, Options, + RegAllocMod, TargetMod, TargetCtx) -> + case proplists:get_bool(ra_prespill, Options) of + true -> + hipe_regalloc_prepass:regalloc_initial( + RegAllocMod, CFG, Liveness, SpillIndex, SpillLimit, TargetMod, + TargetCtx, Options); + false -> + {C, SI} = RegAllocMod:regalloc(CFG, Liveness, SpillIndex, SpillLimit, + TargetMod, TargetCtx, Options), + {C, SI, CFG, Liveness} + end. + +call_allocator(CFG, Liveness, SpillLimit, SpillIndex, Options, RegAllocMod, + TargetMod, TargetCtx) -> + case proplists:get_bool(ra_prespill, Options) of + true -> + hipe_regalloc_prepass:regalloc( + RegAllocMod, CFG, Liveness, SpillIndex, SpillLimit, TargetMod, + TargetCtx, Options); + false -> + RegAllocMod:regalloc(CFG, Liveness, SpillIndex, SpillLimit, TargetMod, + TargetCtx, Options) + end. + +do_range_split(CFG0, Liveness0, TgtMod, TgtCtx, Options) -> + {CFG2, Liveness1} = + case proplists:get_bool(ra_restore_reuse, Options) of + true -> + CFG1 = hipe_restore_reuse:split(CFG0, Liveness0, TgtMod, TgtCtx), + {CFG1, TgtMod:analyze(CFG1, TgtCtx)}; + false -> + {CFG0, Liveness0} + end, + case proplists:get_bool(ra_range_split, Options) of + true -> + CFG3 = hipe_range_split:split(CFG2, Liveness1, TgtMod, TgtCtx, Options), + {CFG3, TgtMod:analyze(CFG3, TgtCtx)}; + false -> + {CFG2, Liveness1} end. diff --git a/lib/hipe/regalloc/hipe_regalloc_prepass.erl b/lib/hipe/regalloc/hipe_regalloc_prepass.erl new file mode 100644 index 0000000000..5024840237 --- /dev/null +++ b/lib/hipe/regalloc/hipe_regalloc_prepass.erl @@ -0,0 +1,953 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%@doc +%% PREPASS FOR ITERATED REGISTER ALLOCATORS +%% +%% Implements a trivial partial but optimal fast register allocator to be used +%% as the first pass of the register allocation loop. +%% +%% The idea is to drastically reduce the number of temporaries, so as to speed +%% up the real register allocators. +%% +%% * Spills trivially unallocatable temps +%% This relies on the fact that calls intentionally clobber all registers. +%% Since this is the case, any temp that is alive over a call can't possibly +%% be allocated to anything but a spill slot. +%% +%% * Partitions the program at points where no pseudos that were not spiled are +%% live, and then do register allocation on these partitions independently. +%% These program points are commonly, but not exclusively, the call +%% instructions. +%% +%% TODO +%% * This module seems very successful at finding every single spill; register +%% allocation performance should be improved if we short-circuit the first +%% hipe_regalloc_loop iteration, skipping directly to rewrite without ever +%% calling RegAllocMod. +-module(hipe_regalloc_prepass). +-export([regalloc/8, regalloc_initial/8]). + +-ifndef(DEBUG). +-compile(inline). +-endif. + +%%-define(DO_ASSERT, 1). +-include("../main/hipe.hrl"). + +%%% TUNABLES + +%% Partitions with fewer than ?TUNE_TOO_FEW_BBS basic block halves are merged +%% together before register allocation. +-define(TUNE_TOO_FEW_BBS, 256). + +%% Ignore the ra_partitioned option (and do whole function RA instead) when +%% there are fewer than ?TUNE_MIN_SPLIT_BBS basic blocks. +-define(TUNE_MIN_SPLIT_BBS, 384). + +%% We present a "pseudo-target" to the register allocator we wrap. +-export([analyze/2, + all_precoloured/1, + allocatable/1, + args/2, + bb/3, + def_use/2, + defines/2, + is_fixed/2, % used by hipe_graph_coloring_regalloc + is_global/2, + is_move/2, + is_precoloured/2, + labels/2, + livein/3, + liveout/3, + non_alloc/2, + number_of_temporaries/2, + physical_name/2, + postorder/2, + reg_nr/2, + uses/2, + var_range/2, + reverse_postorder/2]). + +-record(prepass_ctx, + {target_mod :: module() + ,target_ctx :: target_context() + ,sub :: sub_map() % Translates temp numbers found in CFG and understood by + % Target to temp numbers passed to RegAllocMod. + ,inv :: inv_map() % Translates temp numbers passed to RegAllocMod + % to temp numbers found in CFG and understood by + % Target + ,max_phys :: temp() % Exclusive upper bound on physical registers + }). + +-record(cfg, + {cfg :: target_cfg() + ,bbs :: transformed_bbs() + ,max_reg :: temp() % Exclusive upper bound on temp numbers + ,rpostorder :: undefined % Only precomputed with partitioned cfg + | [label()] + }). + +-type bb() :: hipe_bb:bb(). % containing instr() +-type liveset() :: ordsets:ordset(temp()). +-record(transformed_bb, + {bb :: bb() + ,livein :: liveset() + ,liveout :: liveset() + }). +-type transformed_bb() :: #transformed_bb{}. +-type transformed_bbs() :: #{label() => transformed_bb()}. + +-record(instr, + {defuse :: {[temp()], [temp()]} + ,is_move :: boolean() + }). +-type instr() :: #instr{}. + +-type target_cfg() :: any(). +-type target_instr() :: any(). +-type target_temp() :: any(). +-type target_reg() :: non_neg_integer(). +-type target_liveness() :: any(). +-type target_liveset() :: ordsets:ordset(target_reg()). +-type target_context() :: any(). +-type spillno() :: non_neg_integer(). +-type temp() :: non_neg_integer(). +-type label() :: non_neg_integer(). + +-spec regalloc(module(), target_cfg(), target_liveness(), spillno(), spillno(), + module(), target_context(), proplists:proplist()) + -> {hipe_map(), spillno()}. +regalloc(RegAllocMod, CFG, Liveness, SpillIndex0, SpillLimit, TargetMod, + TargetCtx, Options) -> + {Coloring, SpillIndex, same} = + regalloc_1(RegAllocMod, CFG, SpillIndex0, SpillLimit, TargetMod, + TargetCtx, Options, Liveness), + {Coloring, SpillIndex}. + +%% 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(), target_liveness(), spillno(), + spillno(), module(), target_context(), + proplists:proplist()) + -> {hipe_map(), spillno(), target_cfg(), + target_liveness()}. +regalloc_initial(RegAllocMod, CFG0, Liveness0, SpillIndex0, SpillLimit, + TargetMod, TargetCtx, Options) -> + {Coloring, SpillIndex, NewCFG} = + regalloc_1(RegAllocMod, CFG0, SpillIndex0, SpillLimit, TargetMod, TargetCtx, + Options, Liveness0), + {CFG, Liveness} = + case NewCFG of + same -> {CFG0, Liveness0}; + {rewritten, CFG1} -> {CFG1, TargetMod:analyze(CFG1, TargetCtx)} + end, + {Coloring, SpillIndex, CFG, Liveness}. + +regalloc_1(RegAllocMod, CFG0, SpillIndex0, SpillLimit, TargetMod, TargetCtx, + Options, Liveness) -> + {ScanBBs, Seen, SpillMap, SpillIndex1} = + scan_cfg(CFG0, Liveness, SpillIndex0, TargetMod, TargetCtx), + + {PartColoring, SpillIndex, NewCFG} = + case proplists:get_bool(ra_partitioned, Options) + andalso length(TargetMod:labels(CFG0, TargetCtx)) > ?TUNE_MIN_SPLIT_BBS + of + true -> + regalloc_partitioned(SpillMap, SpillIndex1, SpillLimit, ScanBBs, + CFG0, TargetMod, TargetCtx, RegAllocMod, Options); + _ -> + regalloc_whole(Seen, SpillMap, SpillIndex1, SpillLimit, ScanBBs, + CFG0, TargetMod, TargetCtx, RegAllocMod, Options) + end, + + SpillColors = [{T, {spill, S}} || {T, S} <- maps:to_list(SpillMap)], + Coloring = SpillColors ++ PartColoring, + + ?ASSERT(begin + AllPrecoloured = TargetMod:all_precoloured(TargetCtx), + MaxPhys = lists:max(AllPrecoloured) + 1, + Unused = unused(live_pseudos(Seen, SpillMap, MaxPhys), + SpillMap, CFG0, TargetMod, TargetCtx), + unused_unused(Unused, CFG0, TargetMod, TargetCtx) + end), + ?ASSERT(begin + CFG = + case NewCFG of + same -> CFG0; + {rewritten, CFG1} -> CFG1 + end, + check_coloring(Coloring, CFG, TargetMod, TargetCtx) + end), % Sanity-check + ?ASSERT(just_as_good_as(RegAllocMod, CFG, Liveness, SpillIndex0, SpillLimit, + TargetMod, TargetCtx, Options, SpillMap, Coloring, + Unused)), + {Coloring, SpillIndex, NewCFG}. + +regalloc_whole(Seen, SpillMap, SpillIndex0, SpillLimit, ScanBBs, + CFG, TargetMod, TargetCtx, RegAllocMod, Options) -> + AllPrecoloured = TargetMod:all_precoloured(TargetCtx), + MaxPhys = lists:max(AllPrecoloured) + 1, + LivePseudos = live_pseudos(Seen, SpillMap, MaxPhys), + {SubMap, InvMap, MaxPhys, MaxR, SubSpillLimit} = + number_and_map(AllPrecoloured, LivePseudos, SpillLimit), + BBs = transform_whole_cfg(ScanBBs, SubMap), + SubMod = #cfg{cfg=CFG, bbs=BBs, max_reg=MaxR}, + SubContext = #prepass_ctx{target_mod=TargetMod, target_ctx=TargetCtx, + max_phys=MaxPhys, inv=InvMap, sub=SubMap}, + {SubColoring, SpillIndex} = + RegAllocMod:regalloc(SubMod, SubMod, SpillIndex0, SubSpillLimit, ?MODULE, + SubContext, Options), + ?ASSERT(check_coloring(SubColoring, SubMod, ?MODULE, SubContext)), + {translate_coloring(SubColoring, InvMap), SpillIndex, same}. + +regalloc_partitioned(SpillMap, SpillIndex0, SpillLimit, ScanBBs, + CFG, TargetMod, TargetCtx, RegAllocMod, Options) -> + AllPrecoloured = TargetMod:all_precoloured(TargetCtx), + MaxPhys = lists:max(AllPrecoloured) + 1, + + DSets0 = initial_dsets(CFG, TargetMod, TargetCtx), + PartBBList = part_cfg(ScanBBs, SpillMap, MaxPhys), + DSets1 = join_whole_blocks(PartBBList, DSets0), + {PartBBsRLList, DSets2} = merge_small_parts(DSets1), + {PartBBs, DSets3} = merge_pointless_splits(PartBBList, ScanBBs, DSets2), + SeenMap = collect_seenmap(PartBBsRLList, PartBBs), + {RPostMap, _DSets4} = part_order(TargetMod:reverse_postorder(CFG, TargetCtx), + DSets3), + + {Allocations, SpillIndex} = + lists:mapfoldl( + fun({Root, Elems}, SpillIndex1) -> + #{Root := Seen} = SeenMap, + #{Root := RPost} = RPostMap, + LivePseudos = live_pseudos(Seen, SpillMap, MaxPhys), + {SubMap, InvMap, MaxPhys, MaxR, SubSpillLimit} = + number_and_map(AllPrecoloured, LivePseudos, SpillLimit), + BBs = transform_cfg(Elems, PartBBs, SubMap), + SubMod = #cfg{cfg=CFG, bbs=BBs, max_reg=MaxR, rpostorder=RPost}, + SubContext = #prepass_ctx{target_mod=TargetMod, target_ctx=TargetCtx, + max_phys=MaxPhys, inv=InvMap, sub=SubMap}, + {SubColoring, SpillIndex2} = + RegAllocMod:regalloc(SubMod, SubMod, SpillIndex1, SubSpillLimit, + ?MODULE, SubContext, Options), + ?ASSERT(check_coloring(SubColoring, SubMod, ?MODULE, SubContext)), + {{translate_coloring(SubColoring, InvMap), Elems}, SpillIndex2} + end, SpillIndex0, PartBBsRLList), + {Coloring, NewCFG} = + combine_allocations(Allocations, MaxPhys, PartBBs, TargetMod, TargetCtx, + CFG), + {Coloring, SpillIndex, NewCFG}. + +-spec number_and_map([target_reg()], target_liveset(), target_reg()) + -> {sub_map(), inv_map(), temp(), temp(), temp()}. +number_and_map(Phys, Pseud, SpillLimit) -> + MaxPhys = lists:max(Phys) + 1, + ?ASSERT(Pseud =:= [] orelse lists:min(Pseud) >= MaxPhys), + NrPseuds = length(Pseud), + MaxR = MaxPhys+NrPseuds, + PseudNrs = lists:zip(Pseud, lists:seq(MaxPhys, MaxR-1)), + MapList = lists:zip(Phys, Phys) % Physicals are identity-mapped + ++ PseudNrs, + ?ASSERT(MapList =:= lists:ukeysort(1, MapList)), + SubMap = {s,maps:from_list(MapList)}, + InvMap = {i,maps:from_list([{Fake, Real} || {Real, Fake} <- MapList])}, + SubSpillLimit = translate_spill_limit(MapList, SpillLimit), + {SubMap, InvMap, MaxPhys, MaxR, SubSpillLimit}. + +-spec translate_spill_limit([{target_reg(), temp()}], target_reg()) -> temp(). +translate_spill_limit([{Real,Fake}], SpillLimit) when Real < SpillLimit -> + Fake + 1; +translate_spill_limit([{Real,_}|Ps], SpillLimit) when Real < SpillLimit -> + translate_spill_limit(Ps, SpillLimit); +translate_spill_limit([{Real,Fake}|_], SpillLimit) when Real >= SpillLimit -> + Fake. + +-spec live_pseudos(seen(), spill_map(), target_reg()) -> target_liveset(). +live_pseudos(Seen, SpillMap, MaxPhys) -> + %% When SpillMap is much larger than Seen (which is typical in the partitioned + %% case), it is much more efficient doing it like this than making an ordset + %% of the spills and subtracting. + ordsets:from_list( + lists:filter(fun(R) -> R >= MaxPhys andalso not maps:is_key(R, SpillMap) + end, maps:keys(Seen))). + +-spec translate_coloring(hipe_map(), inv_map()) -> hipe_map(). +translate_coloring(SubColoring, InvMap) -> + lists:map(fun({T, P}) -> {imap_get(T, InvMap), P} end, SubColoring). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% First pass +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Spill trivially unallocatable temps, create internal target-independent +%% program representation, and collect a set of all used temps. +-record(spill_state, + {map :: spill_map() + ,ix :: spillno() + }). +-type spill_state() :: #spill_state{}. +-type spill_map() :: #{target_reg() => spillno()}. + +-spec scan_cfg(target_cfg(), target_liveness(), spillno(), module(), + target_context()) + -> {scan_bbs() + ,seen() + ,spill_map() + ,spillno() + }. +scan_cfg(CFG, Liveness, SpillIndex0, TgtMod, TgtCtx) -> + State0 = #spill_state{map=#{}, ix=SpillIndex0}, + {BBs, Seen, #spill_state{map=Spill, ix=SpillIndex}} = + scan_bbs(TgtMod:labels(CFG,TgtCtx), CFG, Liveness, #{}, State0, #{}, TgtMod, + TgtCtx), + {BBs, Seen, Spill, SpillIndex}. + +-type seen() :: #{target_reg() => []}. % set +-type scan_bb() :: {[instr()], target_liveset(), target_liveset()}. +-type scan_bbs() :: #{label() => scan_bb()}. + +-spec scan_bbs([label()], target_cfg(), target_liveness(), seen(), + spill_state(), scan_bbs(), module(), target_context()) + -> {scan_bbs(), seen(), spill_state()}. +scan_bbs([], _CFG, _Liveness, Seen, State, BBs, _TgtMod, _TgtCtx) -> + {BBs, Seen, State}; +scan_bbs([L|Ls], CFG, Liveness, Seen0, State0, BBs, TgtMod, TgtCtx) -> + Liveout = t_liveout(Liveness, L, TgtMod, TgtCtx), + {Code, Livein, Seen, State} = + scan_bb(lists:reverse(hipe_bb:code(TgtMod:bb(CFG, L, TgtCtx))), Liveout, + Seen0, State0, [], TgtMod, TgtCtx), + BB = {Code, Livein, Liveout}, + scan_bbs(Ls, CFG, Liveness, Seen, State, BBs#{L=>BB}, TgtMod, TgtCtx). + +-spec scan_bb([target_instr()], target_liveset(), seen(), spill_state(), + [instr()], module(), target_context()) + -> {[instr()] + ,target_liveset() + ,seen() + ,spill_state() + }. +scan_bb([], Live, Seen, State, IAcc, _TgtMod, _TgtCtx) -> + {IAcc, Live, Seen, State}; +scan_bb([I|Is], Live0, Seen0, State0, IAcc0, TgtMod, TgtCtx) -> + {TDef, TUse} = TgtMod:def_use(I,TgtCtx), + ?ASSERT(TDef =:= TgtMod:defines(I,TgtCtx)), + ?ASSERT(TUse =:= TgtMod:uses(I,TgtCtx)), + Def = ordsets:from_list(reg_names(TDef, TgtMod, TgtCtx)), + Use = ordsets:from_list(reg_names(TUse, TgtMod, TgtCtx)), + Live = ordsets:union(Use, ToSpill = ordsets:subtract(Live0, Def)), + Seen = add_seen(Def, add_seen(Use, Seen0)), + NewI = #instr{defuse={Def, Use}, is_move=TgtMod:is_move(I,TgtCtx)}, + IAcc = [NewI|IAcc0], + State = + case TgtMod:defines_all_alloc(I,TgtCtx) of + false -> State0; + true -> spill_all(ToSpill, TgtMod, TgtCtx, State0) + end, + %% We can drop "no-ops" here; where (if anywhere) is it worth it? + scan_bb(Is, Live, Seen, State, IAcc, TgtMod, TgtCtx). + +-spec t_liveout(target_liveness(), label(), module(), target_context()) -> + target_liveset(). +t_liveout(Liveness, L, TgtMod, TgtCtx) -> + %% FIXME: unnecessary sort; liveout is sorted, reg_names(...) should be sorted + %% or consist of a few sorted subsequences (per type) + ordsets:from_list(reg_names(TgtMod:liveout(Liveness, L, TgtCtx), TgtMod, + TgtCtx)). + +-spec reg_names([target_temp()], module(), target_context()) -> [target_reg()]. +reg_names(Regs, TgtMod, TgtCtx) -> + [TgtMod:reg_nr(X,TgtCtx) || X <- Regs]. + +-spec add_seen([target_reg()], seen()) -> seen(). +add_seen([], Seen) -> Seen; +add_seen([R|Rs], Seen) -> add_seen(Rs, Seen#{R=>[]}). + +-spec spill_all([target_reg()], module(), target_context(), spill_state()) -> + spill_state(). +spill_all([], _TgtMod, _TgtCtx, State) -> State; +spill_all([R|Rs], TgtMod, TgtCtx, State=#spill_state{map=Map, ix=Ix}) -> + case TgtMod:is_precoloured(R,TgtCtx) or maps:is_key(R, Map) of + true -> spill_all(Rs, TgtMod, TgtCtx, State); + false -> spill_all(Rs, TgtMod, TgtCtx, + State#spill_state{map=Map#{R=>Ix}, ix=Ix+1}) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Second pass (without split) +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Rewrite CFG to the new temp names. +-spec transform_whole_cfg(scan_bbs(), sub_map()) -> transformed_bbs(). +transform_whole_cfg(BBs0, SubMap) -> + maps:map(fun(_, BB) -> transform_whole_bb(BB, SubMap) end, BBs0). + +-spec transform_whole_bb(scan_bb(), sub_map()) -> transformed_bb(). +transform_whole_bb({Code, Livein, Liveout}, SubMap) -> + #transformed_bb{ + bb=hipe_bb:mk_bb([I#instr{defuse={smap_get_all_partial(Def, SubMap), + smap_get_all_partial(Use, SubMap)}} + || I = #instr{defuse={Def,Use}} <- Code]) + %% Assume mapping preserves monotonicity + ,livein=smap_get_all_partial(Livein, SubMap) + ,liveout=smap_get_all_partial(Liveout, SubMap) + }. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Second pass (with split) +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Discover program partitioning +%% Regretfully, this needs to be a separate pass, as having the global live set +%% is crucial to get a useful partitioning. + +%% Single-block parts are merged if there are multiple in a single block, as it +%% is judged to not be beneficial to make them too small. + +-type part_bb_part() :: {[instr()], target_liveset(), target_liveset()}. +-type part_bb() :: {single, part_bb_part()} + | {split, part_bb_part(), part_bb_part()}. +-type part_bb_list() :: [{label(), part_bb()}]. +-type part_bbs() :: #{label() => part_bb()}. +-type part_bb_sofar() :: single + | {split, [instr()], target_liveset()}. % , target_liveset() + +-spec part_cfg(scan_bbs(), spill_map(), target_reg()) -> part_bb_list(). +part_cfg(ScanBBs, SpillMap, MaxPhys) -> + Liveset = mk_part_liveset(SpillMap, MaxPhys), + lists:map(fun(BB) -> part_bb(BB, Liveset) end, maps:to_list(ScanBBs)). + +-spec part_bb({label(), scan_bb()}, part_liveset()) -> {label(), part_bb()}. +part_bb({L, BB0={Code0, Livein, Liveout}}, Liveset) -> + {Sofar, NewCode} = part_bb_1(lists:reverse(Code0), Liveset, Liveout, []), + BB = case Sofar of + single -> + ?ASSERT(Code0 =:= NewCode), + {single, BB0}; + {split, ExitCode, ExitLivein = EntryLiveout} -> + {split, {NewCode, Livein, EntryLiveout}, + {ExitCode, ExitLivein, Liveout}} + end, + {L, BB}. + +-spec part_bb_1([instr()], part_liveset(), target_liveset(), [instr()]) + -> {part_bb_sofar(), [instr()]}. +part_bb_1([], _Liveset, _Livein, IAcc) -> {single, IAcc}; +part_bb_1([I=#instr{defuse={Def,Use}}|Is], Liveset, Live0, IAcc0) -> + Live = ordsets:union(Use, ordsets:subtract(Live0, Def)), + IAcc = [I|IAcc0], + case part_none_live(Live, Liveset) of + false -> part_bb_1(Is, Liveset, Live, IAcc); + %% One split point will suffice + true -> {{split, IAcc, Live}, lists:reverse(Is)} + end. + +-spec part_none_live(target_liveset(), part_liveset()) -> boolean(). +part_none_live(Live, Liveset) -> + not lists:any(fun(R) -> part_liveset_is_live(R, Liveset) end, Live). + +-type part_liveset() :: {spill_map(), target_reg()}. + +-spec mk_part_liveset(spill_map(), target_reg()) -> part_liveset(). +mk_part_liveset(SpillMap, MaxPhys) -> {SpillMap, MaxPhys}. + +-spec part_liveset_is_live(target_reg(), part_liveset()) -> boolean(). +part_liveset_is_live(R, {SpillMap, MaxPhys}) when is_integer(R) -> + R >= MaxPhys andalso not maps:is_key(R, SpillMap). + +%% @doc Merges split blocks where entry and exit belong to the same DSet. +%% Does not change DSets +-spec merge_pointless_splits(part_bb_list(), scan_bbs(), bb_dsets()) + -> {part_bbs(), bb_dsets()}. +merge_pointless_splits(PartBBList0, ScanBBs, DSets0) -> + {PartBBList, DSets} = + merge_pointless_splits_1(PartBBList0, ScanBBs, DSets0, []), + {maps:from_list(PartBBList), DSets}. + +-spec merge_pointless_splits_1( + part_bb_list(), scan_bbs(), bb_dsets(), part_bb_list()) + -> {part_bb_list(), bb_dsets()}. +merge_pointless_splits_1([], _ScanBBs, DSets, Acc) -> {Acc, DSets}; +merge_pointless_splits_1([P={_,{single,_}}|Ps], ScanBBs, DSets, Acc) -> + merge_pointless_splits_1(Ps, ScanBBs, DSets, [P|Acc]); +merge_pointless_splits_1([P0={L,{split,_,_}}|Ps], ScanBBs, DSets0, Acc) -> + {EntryRoot, DSets1} = hipe_dsets:find({entry,L}, DSets0), + {ExitRoot, DSets} = hipe_dsets:find({exit,L}, DSets1), + case EntryRoot =:= ExitRoot of + false -> merge_pointless_splits_1(Ps, ScanBBs, DSets, [P0|Acc]); + true -> + %% Reuse the code list from ScanBBs rather than concatenating the split + %% parts + #{L := BB} = ScanBBs, + ?ASSERT(begin + {L,{split,{_EntryCode,_,_},{_ExitCode,_,_}}}=P0, % [_| + {_Code,_,_}=BB, + _Code =:= (_EntryCode ++ _ExitCode) + end), + merge_pointless_splits_1(Ps, ScanBBs, DSets, [{L,{single, BB}}|Acc]) + end. + +-spec merge_small_parts(bb_dsets()) -> {bb_dsets_rllist(), bb_dsets()}. +merge_small_parts(DSets0) -> + {RLList, DSets1} = hipe_dsets:to_rllist(DSets0), + RLLList = [{R, length(Elems), Elems} || {R, Elems} <- RLList], + merge_small_parts_1(RLLList, DSets1, []). + +-spec merge_small_parts_1( + [{bb_dset_key(), non_neg_integer(), [bb_dset_key()]}], + bb_dsets(), bb_dsets_rllist() + ) -> {bb_dsets_rllist(), bb_dsets()}. +merge_small_parts_1([], DSets, Acc) -> {Acc, DSets}; +merge_small_parts_1([{R, _, Es}], DSets, Acc) -> {[{R, Es}|Acc], DSets}; +merge_small_parts_1([{R, L, Es}|Ps], DSets, Acc) when L >= ?TUNE_TOO_FEW_BBS -> + merge_small_parts_1(Ps, DSets, [{R,Es}|Acc]); +merge_small_parts_1([Fst,{R, L, Es}|Ps], DSets, Acc) + when L >= ?TUNE_TOO_FEW_BBS -> + merge_small_parts_1([Fst|Ps], DSets, [{R,Es}|Acc]); +merge_small_parts_1([{R1,L1,Es1},{R2,L2,Es2}|Ps], DSets0, Acc) -> + ?ASSERT(L1 < ?TUNE_TOO_FEW_BBS andalso L2 < ?TUNE_TOO_FEW_BBS), + DSets1 = hipe_dsets:union(R1, R2, DSets0), + {R, DSets} = hipe_dsets:find(R1, DSets1), + merge_small_parts_1([{R,L2+L1,Es2++Es1}|Ps], DSets, Acc). + +%% @doc Partition an ordering over BBs into subsequences for the dsets that +%% contain them. +%% Does not change dsets. +-spec part_order([label()], bb_dsets()) + -> {#{bb_dset_key() => [label()]}, bb_dsets()}. +part_order(Lbs, DSets) -> part_order(Lbs, DSets, #{}). + +part_order([], DSets, Acc) -> {Acc, DSets}; +part_order([L|Ls], DSets0, Acc0) -> + {EntryRoot, DSets1} = hipe_dsets:find({entry,L}, DSets0), + {ExitRoot, DSets2} = hipe_dsets:find({exit,L}, DSets1), + Acc1 = map_append(EntryRoot, L, Acc0), + %% Only include the label once if both entry and exit is in same partition + Acc2 = case EntryRoot =:= ExitRoot of + true -> Acc1; + false -> map_append(ExitRoot, L, Acc1) + end, + part_order(Ls, DSets2, Acc2). + +map_append(Key, Elem, Map) -> + case Map of + #{Key := List} -> Map#{Key := [Elem|List]}; + #{} -> Map#{Key => [Elem]} + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Interference graph partitioning +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% We partition the program + +%% The algorithm considers two kinds of components; those that are local to a +%% basic block, and those that are not. The key is that any basic block belongs +%% to at most two non-local components; one from the beginning to the first +%% split point, and one from the end to the last split point. + +-type bb_dset_key() :: {entry | exit, label()}. +-type bb_dsets() :: hipe_dsets:dsets(bb_dset_key()). +-type bb_dsets_rllist() :: [{bb_dset_key(), [bb_dset_key()]}]. + +-spec initial_dsets(target_cfg(), module(), target_context()) -> bb_dsets(). +initial_dsets(CFG, TgtMod, TgtCtx) -> + Labels = TgtMod:labels(CFG, TgtCtx), + DSets0 = hipe_dsets:new(lists:append([[{entry,L},{exit,L}] || L <- Labels])), + Edges = lists:append([[{L, S} || S <- hipe_gen_cfg:succ(CFG, L)] + || L <- Labels]), + lists:foldl(fun({X, Y}, DS) -> hipe_dsets:union({exit,X}, {entry,Y}, DS) end, + DSets0, Edges). + +-spec join_whole_blocks(part_bb_list(), bb_dsets()) -> bb_dsets(). +join_whole_blocks(PartBBList, DSets0) -> + lists:foldl(fun({L, {single, _}}, DS) -> + hipe_dsets:union({entry,L}, {exit,L}, DS); + ({_, {split, _, _}}, DS) -> DS + end, DSets0, PartBBList). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Third pass +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Collect all referenced temps in each partition. + +%% Note: The temps could be collected during the partition pass for each +%% half-bb, and then combined here. Would that be beneficial? + +collect_seenmap(PartBBsRLList, PartBBs) -> + collect_seenmap(PartBBsRLList, #{}, PartBBs). + +collect_seenmap([], Acc, _PartBBs) -> Acc; +collect_seenmap([{R,Elems}|Ps], Acc, PartBBs) -> + Seen = collect_seen_part(Elems, #{}, PartBBs), + collect_seenmap(Ps, Acc#{R => Seen}, PartBBs). + +collect_seen_part([], Acc, _PartBBs) -> Acc; +collect_seen_part([{Half,L}|Es], Acc0, PartBBs) -> + BB = maps:get(L, PartBBs), + Code = case {Half, BB} of + {entry, {single, {C,_,_}}} -> C; + {entry, {split, {C,_,_}, _}} -> C; + {exit, {split, _, {C,_,_}}} -> C; + {exit, {single, _}} -> [] % Ignore; was collected by its entry half + end, + Acc = collect_seen_code(Code, Acc0), + collect_seen_part(Es, Acc, PartBBs). + +collect_seen_code([], Acc) -> Acc; +collect_seen_code([#instr{defuse={Def,Use}}|Is], Acc) -> + collect_seen_code(Is, add_seen(Def, add_seen(Use, Acc))). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Fourth pass +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Rewrite CFG to the new temp names. +-spec transform_cfg([bb_dset_key()], part_bbs(), sub_map()) -> transformed_bbs(). + +transform_cfg(Elems, PartBBs, SubMap) -> + transform_cfg(Elems, PartBBs, SubMap, #{}). + +transform_cfg([], _PartBBs, _SubMap, Acc) -> Acc; +transform_cfg([{Half,L}|Es], PartBBs, SubMap, Acc0) -> + #{L := PBB} = PartBBs, + Acc = case {Half, PBB} of + {entry, {single,BB}} -> Acc0#{L=>transform_bb(BB, SubMap)}; + {entry, {split,BB,_}} -> Acc0#{L=>transform_bb(BB, SubMap)}; + {exit, {split,_,BB}} -> Acc0#{L=>transform_bb(BB, SubMap)}; + {exit, {single, _}} -> Acc0 % Was included by the entry half + end, + transform_cfg(Es, PartBBs, SubMap, Acc). + +-spec transform_bb(part_bb_part(), sub_map()) -> transformed_bb(). +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. +%% +%% We optimistically assume that there will be no such collisions, and when +%% there are, we fix them up as they're found. + +-spec combine_allocations([{hipe_map(), [bb_dset_key()]}], target_reg(), + part_bbs(), module(), target_context(), target_cfg()) + -> {hipe_map(), same | {rewritten, target_cfg()}}. +combine_allocations([{A,_}|As], MaxPhys, PartBBs, TgtMod, TgtCtx, CFG) -> + {Phys, Pseuds} = lists:partition(fun({R,_}) -> R < MaxPhys end, A), + {Seen, _, []} = partition_by_seen(Pseuds, #{}, [], []), + combine_allocations(As, MaxPhys, PartBBs, TgtMod, TgtCtx, Phys, Seen, Pseuds, + {same, CFG}). + +-spec combine_allocations([{hipe_map(), [bb_dset_key()]}], target_reg(), + part_bbs(), module(), target_context(), hipe_map(), + seen(), hipe_map(), {same|rewritten, target_cfg()}) + -> {hipe_map(), same | {rewritten, target_cfg()}}. +combine_allocations([], _MaxPhys, _PartBBs, _TgtMod, _TgtCtx, Phys, _Seen, + Pseuds, CFGT) -> + {Phys ++ Pseuds, case CFGT of + {same, _} -> same; + {rewritten, _} -> CFGT + end}; +combine_allocations([{A,PartElems}|As], MaxPhys, PartBBs, TgtMod, TgtCtx, 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, TgtMod, TgtCtx, Phys, Seen, + Pseuds++Acc, CFGT); + _ -> + %% There were collisions; rename all the temp numbers in Collisions + {CFG, Renamed} = rename(Collisions, PartElems, PartBBs, TgtMod, TgtCtx, + CFG0), + combine_allocations(As, MaxPhys, PartBBs, TgtMod, TgtCtx, 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_context(), target_cfg()) + -> {target_cfg(), hipe_map()}. +rename(CollisionList, PartElems, PartBBs, TgtMod, TgtCtx, CFG0) -> + {Map, Renamed} = new_names(CollisionList, TgtMod, TgtCtx, #{}, []), + Fun = fun(I) -> + TgtMod:subst_temps( + fun(Temp) -> + N = TgtMod:reg_nr(Temp, TgtCtx), + case Map of + #{N := Subst} -> TgtMod:update_reg_nr(Subst, Temp, TgtCtx); + #{} -> Temp + end + end, I, TgtCtx) + end, + {rename_1(PartElems, PartBBs, TgtMod, TgtCtx, Fun, CFG0), Renamed}. + +-type rename_map() :: #{target_reg() => target_reg()}. +-type rename_fun() :: fun((target_instr()) -> target_instr()). + +-spec new_names(hipe_map(), module(), target_context(), rename_map(), + hipe_map()) + -> {rename_map(), hipe_map()}. +new_names([], _TgtMod, _TgtCtx, Map, Renamed) -> {Map, Renamed}; +new_names([{R,C}|As], TgtMod, TgtCtx, Map, Renamed) -> + Subst = TgtMod:new_reg_nr(TgtCtx), + new_names(As, TgtMod, TgtCtx, 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(), target_context(), + rename_fun(), target_cfg()) -> target_cfg(). +rename_1([], _PartBBs, _TgtMod, _TgtCtx, _Fun, CFG) -> CFG; +rename_1([{Half,L}|Es], PartBBs, TgtMod, TgtCtx, Fun, CFG0) -> + Code0 = hipe_bb:code(BB = TgtMod:bb(CFG0, L, TgtCtx)), + 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 = TgtMod:update_bb(CFG0, L, hipe_bb:code_update(BB, Code), TgtCtx), + rename_1(Es, PartBBs, TgtMod, TgtCtx, 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 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-type sub_map() :: {s,#{target_reg() => temp()}}. +-type inv_map() :: {i,#{temp() => target_reg()}}. + +-spec smap_get(target_reg(), sub_map()) -> temp(). +smap_get(Temp, {s,Map}) when is_integer(Temp) -> maps:get(Temp, Map). + +-spec imap_get(temp(), inv_map()) -> target_reg(). +imap_get(Temp, {i,Map}) when is_integer(Temp) -> maps:get(Temp, Map). + +-spec smap_get_all_partial([target_reg()], sub_map()) -> [temp()]. +smap_get_all_partial([], _) -> []; +smap_get_all_partial([T|Ts], SMap={s,Map}) when is_integer(T) -> + case Map of + #{T := R} -> [R|smap_get_all_partial(Ts, SMap)]; + #{} -> smap_get_all_partial(Ts, SMap) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Validation +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-ifdef(DO_ASSERT). +%%%%%%%%%%%%%%%%%%%% +%% Check that the coloring is correct (if the IG is correct): +%% + +%% Define these as 'ok' or 'report(X,Y)' depending on how much output you want. +-define(report0(X,Y), ?IF_DEBUG_LEVEL(0,?msg(X, Y),ok)). +-define(report(X,Y), ?IF_DEBUG_LEVEL(1,?msg(X, Y),ok)). +-define(report2(X,Y), ?IF_DEBUG_LEVEL(2,?msg(X, Y),ok)). +-define(report3(X,Y), ?IF_DEBUG_LEVEL(3,?msg(X, Y),ok)). + +check_coloring(Coloring, CFG, TgtMod, TgtCtx) -> + ?report0("checking coloring ~p~n",[Coloring]), + IG = hipe_ig:build(CFG, TgtMod:analyze(CFG,TgtCtx), TgtMod, TgtCtx), + check_cols(hipe_vectors:list(hipe_ig:adj_list(IG)), + init_coloring(Coloring, TgtMod, TgtCtx)). + +init_coloring(Xs, TgtMod, TgtCtx) -> + hipe_temp_map:cols2tuple(Xs, TgtMod, TgtCtx). + +check_color_of(X, Cols) -> + case hipe_temp_map:find(X, Cols) of + unknown -> + uncolored; + C -> + C + end. + +check_cols([], _Cols) -> + ?report("coloring valid~n",[]), + true; +check_cols([{X,Neighbours}|Xs], Cols) -> + Cs = [{N, check_color_of(N, Cols)} || N <- Neighbours], + C = check_color_of(X, Cols), + case valid_coloring(X, C, Cs) of + yes -> + check_cols(Xs, Cols); + {no,Invalids} -> + ?msg("node ~p has same color (~p) as ~p~n", [X,C,Invalids]), + check_cols(Xs, Cols) andalso false + end. + +valid_coloring(_X, _C, []) -> + yes; +valid_coloring(X, C, [{Y,C}|Ys]) -> + case valid_coloring(X, C, Ys) of + yes -> {no, [Y]}; + {no,Zs} -> {no, [Y|Zs]} + end; +valid_coloring(X, C, [_|Ys]) -> + valid_coloring(X, C, Ys). + +unused_unused(Unused, CFG, TgtMod, TgtCtx) -> + IG = hipe_ig:build(CFG, TgtMod:analyze(CFG,TgtCtx), TgtMod, TgtCtx), + lists:all(fun(R) -> case hipe_ig:get_node_degree(R, IG) of + 0 -> true; + Deg -> + ?msg("Temp ~w is in unused but has degree ~w~n", + [R, Deg]), + false + end end, Unused). + +%%%%%%%%%%%%%%%%%%%% +%% Check that no register allocation opportunities were missed due to ?MODULE +%% +just_as_good_as(RegAllocMod, CFG, Liveness, SpillIndex0, SpillLimit, TgtMod, + TgtCtx, Options, SpillMap, Coloring, Unused) -> + {CheckColoring, _} = + RegAllocMod:regalloc(CFG, Liveness, SpillIndex0, SpillLimit, TgtMod, TgtCtx, + Options), + Now = lists:sort([{R,Kind} || {R,{Kind,_}} <- Coloring, + not ordsets:is_element(R, Unused)]), + Check = lists:sort([{R,Kind} || {R,{Kind,_}} <- CheckColoring, + not ordsets:is_element(R, Unused)]), + CheckMap = maps:from_list(Check), + SaneSpills = all_spills_sane_1(CheckColoring, SpillMap), + case SaneSpills + andalso lists:all(fun({R, spill}) -> maps:get(R, CheckMap) =:= spill; + ({_,reg}) -> true + end, Now) + of + true -> true; + false -> + {NowRegs, _} = _NowCount = count(Now), + {CheckRegs, _} = _CheckCount = count(Check), + {M,F,A} = element(2, element(3, CFG)), + io:fwrite(standard_error, "Colorings differ (~w, ~w)!~n" + "MFA: ~w:~w/~w~n" + "Unused: ~w~n" + "Now:~w~nCorrect:~w~n", + [TgtMod, RegAllocMod, + M,F,A, + Unused, + Now -- Check, Check -- Now]), + SaneSpills andalso NowRegs >= CheckRegs + end. + +count(C) -> {length([[] || {_, reg} <- C]), + length([[] || {_, spill} <- C])}. + +unused(LivePseudos, SpillMap, CFG, TgtMod, TgtCtx) -> + {TMin, TMax} = TgtMod:var_range(CFG,TgtCtx), + SpillOSet = ordsets:from_list(maps:keys(SpillMap)), + PhysOSet = ordsets:from_list(TgtMod:all_precoloured(TgtCtx)), + Used = ordsets:union(LivePseudos, ordsets:union(PhysOSet, SpillOSet)), + ordsets:subtract(lists:seq(TMin, TMax), Used). + +%% Check that no temp that we wrote off was actually allocatable. +all_spills_sane_1(_, Empty) when map_size(Empty) =:= 0 -> true; +all_spills_sane_1([], _Nonempty) -> false; +all_spills_sane_1([{T, {reg, _}}|Cs], SpillMap) -> + not maps:is_key(T, SpillMap) andalso all_spills_sane_1(Cs, SpillMap); +all_spills_sane_1([{T, {spill, _}}|Cs], SpillMap) -> + all_spills_sane_1(Cs, maps:remove(T, SpillMap)). + +-endif. % DO_ASSERT + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Pseudo-target interface +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +analyze(Cfg, _ModRec) -> Cfg. +bb(Cfg=#cfg{bbs=BBs}, Ix, _ModRec) -> + case BBs of + #{Ix := #transformed_bb{bb=BB}} -> BB; + _ -> error(badarg, [Cfg, Ix]) + end. +args(Arity, #prepass_ctx{target_mod=TgtMod, target_ctx=TgtCtx, sub=SubM}) -> + smap_get(TgtMod:args(Arity,TgtCtx), SubM). +labels(#cfg{bbs=BBs}, _ModRec) -> maps:keys(BBs). +livein(#cfg{bbs=BBs}, Lb, _SubMod) -> + #{Lb := #transformed_bb{livein=Livein}} = BBs, + Livein. +liveout(#cfg{bbs=BBs}, Lb, _SubMod) -> + #{Lb := #transformed_bb{liveout=Liveout}} = BBs, + Liveout. +uses(I, MR) -> element(2, def_use(I, MR)). +defines(I, MR) -> element(1, def_use(I, MR)). +def_use(#instr{defuse=DefUse}, _ModRec) -> DefUse. +is_move(#instr{is_move=IM}, _ModRec) -> IM. +is_fixed(Reg, #prepass_ctx{target_mod=TgtMod,target_ctx=TgtCtx,inv=InvM}) -> + TgtMod:is_fixed(imap_get(Reg, InvM),TgtCtx). % XXX: Is this hot? +is_global(Reg, #prepass_ctx{target_mod=TgtMod,target_ctx=TgtCtx, + max_phys=MaxPhys}) when Reg < MaxPhys -> + TgtMod:is_global(Reg,TgtCtx). % assume id-map +is_precoloured(Reg, #prepass_ctx{max_phys=MaxPhys}) -> Reg < MaxPhys. +reg_nr(Reg, _ModRec) -> Reg. % After mapping (naturally) +non_alloc(#cfg{cfg=CFG}, #prepass_ctx{target_mod=TgtMod,target_ctx=TgtCtx, + sub=SubM}) -> + smap_get_all_partial(reg_names(TgtMod:non_alloc(CFG,TgtCtx), TgtMod, TgtCtx), + SubM). +number_of_temporaries(#cfg{max_reg=MaxR}, _ModRec) -> MaxR. +allocatable(#prepass_ctx{target_mod=TgtMod, target_ctx=TgtCtx}) -> + TgtMod:allocatable(TgtCtx). % assume id-map +physical_name(Reg, _ModRec) -> Reg. +all_precoloured(#prepass_ctx{target_mod=TgtMod, target_ctx=TgtCtx}) -> + TgtMod:all_precoloured(TgtCtx). % dito +var_range(#cfg{cfg=_CFG, max_reg=MaxReg}, + #prepass_ctx{target_mod=_TgtMod, target_ctx=_TgtCtx}) -> + ?ASSERT(begin {TgtMin, _} = _TgtMod:var_range(_CFG,_TgtCtx), + TgtMin =:= 0 + end), + {0, MaxReg-1}. + +postorder(#cfg{cfg=CFG,rpostorder=undefined}, + #prepass_ctx{target_mod=TgtMod,target_ctx=TgtCtx}) -> + TgtMod:postorder(CFG,TgtCtx); +postorder(#cfg{rpostorder=Labels}, _ModRec) when is_list(Labels) -> + lists:reverse(Labels). + +reverse_postorder(#cfg{cfg=CFG,rpostorder=undefined}, + #prepass_ctx{target_mod=TgtMod,target_ctx=TgtCtx}) -> + TgtMod:reverse_postorder(CFG,TgtCtx); +reverse_postorder(#cfg{rpostorder=Labels}, _ModRec) when is_list(Labels) -> + Labels. diff --git a/lib/hipe/regalloc/hipe_restore_reuse.erl b/lib/hipe/regalloc/hipe_restore_reuse.erl new file mode 100644 index 0000000000..2158bd185e --- /dev/null +++ b/lib/hipe/regalloc/hipe_restore_reuse.erl @@ -0,0 +1,516 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%@doc +%% RESTORE REUSE LIVE RANGE SPLITTING PASS +%% +%% This is a simple live range splitter that tries to avoid sequences where a +%% temporary is accessed on stack multiple times by keeping a copy of that temp +%% around in a register. +%% +%% At any point where a temporary that is expected to be spilled (see uses of +%% spills_add_list/2) is defined or used, this pass considers that temporary +%% "available". +%% +%% Limitations: +%% * If a live range part starts with several different restores, this module +%% will introduce a new temp number for each of them, and later be forced to +%% generate phi blocks. It would be more efficient to introduce just a +%% single temp number. That would also remove the need for the phi blocks. +%% * If a live range part ends in a definition, that definition should just +%% define the base temp rather than the substitution, since some CISC +%% targets might be able to inline the memory access in the instruction. +-module(hipe_restore_reuse). + +-export([split/4]). + +%% Exports for hipe_range_split, which uses restore_reuse as one possible spill +%% "mode" +-export([analyse/3 + ,renamed_in_block/2 + ,split_in_block/2 + ]). +-export_type([avail/0]). + +-compile(inline). + +%% -define(DO_ASSERT, 1). +-include("../main/hipe.hrl"). + +-type target_cfg() :: any(). +-type liveness() :: any(). +-type target_module() :: module(). +-type target_context() :: any(). +-type target() :: {target_module(), target_context()}. +-type label() :: non_neg_integer(). +-type reg() :: non_neg_integer(). +-type instr() :: any(). +-type temp() :: any(). + +-spec split(target_cfg(), liveness(), target_module(), target_context()) + -> target_cfg(). +split(CFG, Liveness, TargetMod, TargetContext) -> + Target = {TargetMod, TargetContext}, + Avail = analyse(CFG, Liveness, Target), + rewrite(CFG, Target, Avail). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-opaque avail() :: #{label() => avail_bb()}. + +-record(avail_bb, { + %% Blocks where HasCall is true are considered to have too high + %% register pressure to support a register copy of a temp + has_call :: boolean(), + %% AvailOut: Temps that can be split (are available) + out :: availset(), + %% Gen: AvailOut generated locally + gen :: availset(), + %% WantIn: Temps that are split + want :: regset(), + %% Self: Temps with avail-want pairs locally + self :: regset(), + %% DefIn: Temps shadowed by later def in same live range part + defin :: regset(), + pred :: [label()], + succ :: [label()] + }). +-type avail_bb() :: #avail_bb{}. + +avail_get(L, Avail) -> maps:get(L, Avail). +avail_set(L, Val, Avail) -> maps:put(L, Val, Avail). +avail_has_call(L, Avail) -> (avail_get(L, Avail))#avail_bb.has_call. +avail_out(L, Avail) -> (avail_get(L, Avail))#avail_bb.out. +avail_self(L, Avail) -> (avail_get(L, Avail))#avail_bb.self. +avail_pred(L, Avail) -> (avail_get(L, Avail))#avail_bb.pred. +avail_succ(L, Avail) -> (avail_get(L, Avail))#avail_bb.succ. + +avail_in(L, Avail) -> + case avail_pred(L, Avail) of + [] -> availset_empty(); % entry + Pred -> + lists:foldl(fun(P, ASet) -> + availset_intersect(avail_out(P, Avail), ASet) + end, availset_top(), Pred) + end. + +want_in(L, Avail) -> (avail_get(L, Avail))#avail_bb.want. +want_out(L, Avail) -> + lists:foldl(fun(S, Set) -> + ordsets:union(want_in(S, Avail), Set) + end, ordsets:new(), avail_succ(L, Avail)). + +def_in(L, Avail) -> (avail_get(L, Avail))#avail_bb.defin. +def_out(L, Avail) -> + case avail_succ(L, Avail) of + [] -> ordsets:new(); % entry + Succ -> + ordsets:intersection([def_in(S, Avail) || S <- Succ]) + end. + +-type regset() :: ordsets:ordset(reg()). +-type availset() :: top | regset(). +availset_empty() -> []. +availset_top() -> top. +availset_intersect(top, B) -> B; +availset_intersect(A, top) -> A; +availset_intersect(A, B) -> ordsets:intersection(A, B). +availset_union(top, _) -> top; +availset_union(_, top) -> top; +availset_union(A, B) -> ordsets:union(A, B). +ordset_intersect_availset(OS, top) -> OS; +ordset_intersect_availset(OS, AS) -> ordsets:intersection(OS, AS). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Analysis pass +%% +%% The analysis pass collects the set of temps we're interested in splitting +%% (Spills), and computes three dataflow analyses for this subset of temps. +%% +%% Avail, which is the set of temps which are available in register from a +%% previous (potential) spill or restore without going through a HasCall +%% block. +%% Want, which is a liveness analysis for the subset of temps used by an +%% instruction that are also in Avail at that point. In other words, Want is +%% the set of temps that are split (has a register copy) at a particular +%% point. +%% Def, which are the temps that are already going to be spilled later, and so +%% need not be spilled when they're defined. +%% +%% Lastly, it computes the set Self for each block, which is the temps that have +%% avail-want pairs in the same block, and so should be split in that block even +%% if they're not in WantIn for the block. + +-spec analyse(target_cfg(), liveness(), target()) -> avail(). +analyse(CFG, Liveness, Target) -> + Avail0 = analyse_init(CFG, Liveness, Target), + RPO = reverse_postorder(CFG, Target), + AvailLs = [L || L <- RPO, not avail_has_call(L, Avail0)], + Avail1 = avail_dataf(AvailLs, Avail0), + Avail2 = analyse_filter_want(maps:keys(Avail1), Avail1), + PO = lists:reverse(RPO), + want_dataf(PO, Avail2). + +-spec analyse_init(target_cfg(), liveness(), target()) -> avail(). +analyse_init(CFG, Liveness, Target) -> + analyse_init(labels(CFG, Target), CFG, Liveness, Target, #{}, []). + +-spec analyse_init([label()], target_cfg(), liveness(), target(), spillset(), + [{label(), avail_bb()}]) + -> avail(). +analyse_init([], _CFG, _Liveness, Target, Spills0, Acc) -> + %% Precoloured temps can't be spilled + Spills = spills_filter(fun(R) -> not is_precoloured(R, Target) end, Spills0), + analyse_init_1(Acc, Spills, []); +analyse_init([L|Ls], CFG, Liveness, Target, Spills0, Acc) -> + {DefIn, Gen, Self, Want, HasCall0} = + analyse_scan(hipe_bb:code(bb(CFG, L, Target)), Target, + ordsets:new(), ordsets:new(), ordsets:new(), + ordsets:new()), + {Spills, Out, HasCall} = + case HasCall0 of + false -> {Spills0, availset_top(), false}; + {true, CallDefs} -> + Spill = ordsets:subtract(liveout(Liveness, L, Target), CallDefs), + {spills_add_list(Spill, Spills0), Gen, true} + end, + Pred = hipe_gen_cfg:pred(CFG, L), + Succ = hipe_gen_cfg:succ(CFG, L), + Val = #avail_bb{gen=Gen, want=Want, self=Self, out=Out, has_call=HasCall, + pred=Pred, succ=Succ, defin=DefIn}, + analyse_init(Ls, CFG, Liveness, Target, Spills, [{L, Val} | Acc]). + +-spec analyse_init_1([{label(), avail_bb()}], spillset(), + [{label(), avail_bb()}]) + -> avail(). +analyse_init_1([], _Spills, Acc) -> maps:from_list(Acc); +analyse_init_1([{L, Val0}|Vs], Spills, Acc) -> + #avail_bb{out=Out,gen=Gen,want=Want,self=Self} = Val0, + Val = Val0#avail_bb{ + out = spills_filter_availset(Out, Spills), + gen = spills_filter_availset(Gen, Spills), + want = spills_filter_availset(Want, Spills), + self = spills_filter_availset(Self, Spills)}, + analyse_init_1(Vs, Spills, [{L, Val} | Acc]). + +-type spillset() :: #{reg() => []}. +-spec spills_add_list([reg()], spillset()) -> spillset(). +spills_add_list([], Spills) -> Spills; +spills_add_list([R|Rs], Spills) -> spills_add_list(Rs, Spills#{R => []}). + +-spec spills_filter_availset(availset(), spillset()) -> availset(). +spills_filter_availset([E|Es], Spills) -> + case Spills of + #{E := _} -> [E|spills_filter_availset(Es, Spills)]; + #{} -> spills_filter_availset(Es, Spills) + end; +spills_filter_availset([], _) -> []; +spills_filter_availset(top, _) -> top. + +spills_filter(Fun, Spills) -> maps:filter(fun(K, _) -> Fun(K) end, Spills). + +-spec analyse_scan([instr()], target(), Defset, Gen, Self, Want) + -> {Defset, Gen, Self, Want, HasCall} when + HasCall :: false | {true, regset()}, + Defset :: regset(), + Gen :: availset(), + Self :: regset(), + Want :: regset(). +analyse_scan([], _Target, Defs, Gen, Self, Want) -> + {Defs, Gen, Self, Want, false}; +analyse_scan([I|Is], Target, Defs0, Gen0, Self0, Want0) -> + {DefL, UseL} = reg_def_use(I, Target), + Use = ordsets:from_list(UseL), + Def = ordsets:from_list(DefL), + Self = ordsets:union(ordsets:intersection(Use, Gen0), Self0), + Want = ordsets:union(ordsets:subtract(Use, Defs0), Want0), + Defs = ordsets:union(Def, Defs0), + case defines_all_alloc(I, Target) of + true -> + [] = Is, %assertion + {Defs, ordsets:new(), Self, Want, {true, Def}}; + false -> + Gen = ordsets:union(ordsets:union(Def, Use), Gen0), + analyse_scan(Is, Target, Defs, Gen, Self, Want) + end. + +-spec avail_dataf([label()], avail()) -> avail(). +avail_dataf(RPO, Avail0) -> + case avail_dataf_once(RPO, Avail0, 0) of + {Avail, 0} -> Avail; + {Avail, _Changed} -> + avail_dataf(RPO, Avail) + end. + +-spec avail_dataf_once([label()], avail(), non_neg_integer()) + -> {avail(), non_neg_integer()}. +avail_dataf_once([], Avail, Changed) -> {Avail, Changed}; +avail_dataf_once([L|Ls], Avail0, Changed0) -> + ABB = #avail_bb{out=OldOut, gen=Gen} = avail_get(L, Avail0), + In = avail_in(L, Avail0), + {Changed, Avail} = + case availset_union(In, Gen) of + OldOut -> {Changed0, Avail0}; + Out -> {Changed0+1, avail_set(L, ABB#avail_bb{out=Out}, Avail0)} + end, + avail_dataf_once(Ls, Avail, Changed). + +-spec analyse_filter_want([label()], avail()) -> avail(). +analyse_filter_want([], Avail) -> Avail; +analyse_filter_want([L|Ls], Avail0) -> + ABB = #avail_bb{want=Want0, defin=DefIn0} = avail_get(L, Avail0), + In = avail_in(L, Avail0), + Want = ordset_intersect_availset(Want0, In), + DefIn = ordset_intersect_availset(DefIn0, In), + Avail = avail_set(L, ABB#avail_bb{want=Want, defin=DefIn}, Avail0), + analyse_filter_want(Ls, Avail). + +-spec want_dataf([label()], avail()) -> avail(). +want_dataf(PO, Avail0) -> + case want_dataf_once(PO, Avail0, 0) of + {Avail, 0} -> Avail; + {Avail, _Changed} -> + want_dataf(PO, Avail) + end. + +-spec want_dataf_once([label()], avail(), non_neg_integer()) + -> {avail(), non_neg_integer()}. +want_dataf_once([], Avail, Changed) -> {Avail, Changed}; +want_dataf_once([L|Ls], Avail0, Changed0) -> + ABB0 = #avail_bb{want=OldIn,defin=OldDef} = avail_get(L, Avail0), + AvailIn = avail_in(L, Avail0), + Out = want_out(L, Avail0), + DefOut = def_out(L, Avail0), + {Changed, Avail} = + case {ordsets:union(ordset_intersect_availset(Out, AvailIn), OldIn), + ordsets:union(ordset_intersect_availset(DefOut, AvailIn), OldDef)} + of + {OldIn, OldDef} -> {Changed0, Avail0}; + {In, DefIn} -> + ABB = ABB0#avail_bb{want=In,defin=DefIn}, + {Changed0+1, avail_set(L, ABB, Avail0)} + end, + want_dataf_once(Ls, Avail, Changed). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Rewrite pass +-type subst_dict() :: orddict:orddict(reg(), reg()). +-type input() :: #{label() => subst_dict()}. + +-spec rewrite(target_cfg(), target(), avail()) -> target_cfg(). +rewrite(CFG, Target, Avail) -> + RPO = reverse_postorder(CFG, Target), + rewrite(RPO, Target, Avail, #{}, CFG). + +-spec rewrite([label()], target(), avail(), input(), target_cfg()) + -> target_cfg(). +rewrite([], _Target, _Avail, _Input, CFG) -> CFG; +rewrite([L|Ls], Target, Avail, Input0, CFG0) -> + SplitHere = split_in_block(L, Avail), + {Input1, LInput} = + case Input0 of + #{L := LInput0} -> {Input0, LInput0}; + #{} -> {Input0#{L => []}, []} % entry block + end, + ?ASSERT([] =:= [X || X <- SplitHere, orddict:is_key(X, LInput)]), + ?ASSERT(want_in(L, Avail) =:= orddict:fetch_keys(LInput)), + {CFG1, LOutput} = + case {SplitHere, LInput} of + {[], []} -> % optimisation (rewrite will do nothing, so skip it) + {CFG0, LInput}; + _ -> + Code0 = hipe_bb:code(BB=bb(CFG0, L, Target)), + DefOut = def_out(L, Avail), + {Code, LOutput0, _DefIn} = + rewrite_instrs(Code0, Target, LInput, DefOut, SplitHere), + {update_bb(CFG0, L, hipe_bb:code_update(BB, Code), Target), LOutput0} + end, + {Input, CFG} = rewrite_succs(avail_succ(L, Avail), Target, L, LOutput, Avail, + Input1, CFG1), + rewrite(Ls, Target, Avail, Input, CFG). + +-spec renamed_in_block(label(), avail()) -> ordsets:ordset(reg()). +renamed_in_block(L, Avail) -> + ordsets:union([avail_self(L, Avail), want_in(L, Avail), + want_out(L, Avail)]). + +-spec split_in_block(label(), avail()) -> ordsets:ordset(reg()). +split_in_block(L, Avail) -> + ordsets:subtract(ordsets:union(avail_self(L, Avail), want_out(L, Avail)), + want_in(L, Avail)). + +-spec rewrite_instrs([instr()], target(), subst_dict(), regset(), [reg()]) + -> {[instr()], subst_dict(), regset()}. +rewrite_instrs([], _Target, Output, DefOut, []) -> + {[], Output, DefOut}; +rewrite_instrs([I|Is], Target, Input0, BBDefOut, SplitHere0) -> + {TDef, TUse} = def_use(I, Target), + {Def, Use} = {reg_names(TDef, Target), reg_names(TUse, Target)}, + %% Restores are generated in forward order by picking temps from SplitHere as + %% they're used or defined. After the last instruction, all temps have been + %% picked. + {ISplits, SplitHere} = + lists:partition(fun(R) -> + lists:member(R, Def) orelse lists:member(R, Use) + end, SplitHere0), + {Input, Restores} = + case ISplits of + [] -> {Input0, []}; + _ -> + make_splits(ISplits, Target, TDef, TUse, Input0, []) + end, + %% Here's the recursive call + {Acc0, Output, DefOut} = + rewrite_instrs(Is, Target, Input, BBDefOut, SplitHere), + %% From here we're processing instructions in reverse order, because to avoid + %% redundant spills we need to walk the 'def' dataflow, which is in reverse. + SubstFun = fun(Temp) -> + case orddict:find(reg_nr(Temp, Target), Input) of + {ok, NewTemp} -> NewTemp; + error -> Temp + end + end, + Acc1 = insert_spills(TDef, Target, Input, DefOut, Acc0), + Acc = Restores ++ [subst_temps(SubstFun, I, Target) | Acc1], + DefIn = ordsets:union(DefOut, ordsets:from_list(Def)), + {Acc, Output, DefIn}. + +-spec make_splits([reg()], target(), [temp()], [temp()], subst_dict(), + [instr()]) + -> {subst_dict(), [instr()]}. +make_splits([], _Target, _TDef, _TUse, Input, Acc) -> + {Input, Acc}; +make_splits([S|Ss], Target, TDef, TUse, Input0, Acc0) -> + SubstReg = new_reg_nr(Target), + {Acc, Subst} = + case find_reg_temp(S, TUse, Target) of + error -> + {ok, Temp} = find_reg_temp(S, TDef, Target), + {Acc0, update_reg_nr(SubstReg, Temp, Target)}; + {ok, Temp} -> + Subst0 = update_reg_nr(SubstReg, Temp, Target), + Acc1 = [mk_move(Temp, Subst0, Target) | Acc0], + {Acc1, Subst0} + end, + Input = orddict:store(S, Subst, Input0), + make_splits(Ss, Target, TDef, TUse, Input, Acc). + +-spec find_reg_temp(reg(), [temp()], target()) -> error | {ok, temp()}. +find_reg_temp(_Reg, [], _Target) -> error; +find_reg_temp(Reg, [T|Ts], Target) -> + case reg_nr(T, Target) of + Reg -> {ok, T}; + _ -> find_reg_temp(Reg, Ts, Target) + end. + +-spec insert_spills([temp()], target(), subst_dict(), regset(), [instr()]) + -> [instr()]. +insert_spills([], _Target, _Input, _DefOut, Acc) -> Acc; +insert_spills([T|Ts], Target, Input, DefOut, Acc0) -> + R = reg_nr(T, Target), + Acc = + case orddict:find(R, Input) of + error -> Acc0; + {ok, Subst} -> + case lists:member(R, DefOut) of + true -> Acc0; + false -> [mk_move(Subst, T, Target) | Acc0] + end + end, + insert_spills(Ts, Target, Input, DefOut, Acc). + +-spec rewrite_succs([label()], target(), label(), subst_dict(), avail(), + input(), target_cfg()) -> {input(), target_cfg()}. +rewrite_succs([], _Target, _P, _POutput, _Avail, Input, CFG) -> {Input, CFG}; +rewrite_succs([L|Ls], Target, P, POutput, Avail, Input0, CFG0) -> + NewLInput = orddict_with_ordset(want_in(L, Avail), POutput), + {Input, CFG} = + case Input0 of + #{L := LInput} -> + CFG2 = + case required_phi_moves(LInput, NewLInput) of + [] -> CFG0; + ReqMovs -> + PhiLb = new_label(Target), + Code = [mk_move(S,D,Target) || {S,D} <- ReqMovs] + ++ [mk_goto(L, Target)], + PhiBB = hipe_bb:mk_bb(Code), + CFG1 = update_bb(CFG0, PhiLb, PhiBB, Target), + bb_redirect_jmp(L, PhiLb, P, CFG1, Target) + end, + {Input0, CFG2}; + #{} -> + {Input0#{L => NewLInput}, CFG0} + end, + rewrite_succs(Ls, Target, P, POutput, Avail, Input, CFG). + +-spec bb_redirect_jmp(label(), label(), label(), target_cfg(), target()) + -> target_cfg(). +bb_redirect_jmp(From, To, Lb, CFG, Target) -> + BB0 = bb(CFG, Lb, Target), + Last = redirect_jmp(hipe_bb:last(BB0), From, To, Target), + BB = hipe_bb:code_update(BB0, hipe_bb:butlast(BB0) ++ [Last]), + update_bb(CFG, Lb, BB, Target). + +-spec required_phi_moves(subst_dict(), subst_dict()) -> [{reg(), reg()}]. +required_phi_moves([], []) -> []; +required_phi_moves([P|Is], [P|Os]) -> required_phi_moves(Is, Os); +required_phi_moves([{K, In}|Is], [{K, Out}|Os]) -> + [{Out, In}|required_phi_moves(Is, Os)]. + +%% @doc Returns a new orddict with the keys in Set and their associated values. +-spec orddict_with_ordset(ordsets:ordset(K), orddict:orddict(K, V)) + -> orddict:orddict(K, V). +orddict_with_ordset([S|Ss], [{K, _}|_]=Dict) when S < K -> + orddict_with_ordset(Ss, Dict); +orddict_with_ordset([S|_]=Set, [{K, _}|Ds]) when S > K -> + orddict_with_ordset(Set, Ds); +orddict_with_ordset([_S|Ss], [{_K, _}=P|Ds]) -> % _S == _K + [P|orddict_with_ordset(Ss, Ds)]; +orddict_with_ordset([], _) -> []; +orddict_with_ordset(_, []) -> []. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Target module interface functions +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-define(TGT_IFACE_0(N), N( {M,C}) -> M:N( C)). +-define(TGT_IFACE_1(N), N(A1, {M,C}) -> M:N(A1, C)). +-define(TGT_IFACE_2(N), N(A1,A2, {M,C}) -> M:N(A1,A2, C)). +-define(TGT_IFACE_3(N), N(A1,A2,A3,{M,C}) -> M:N(A1,A2,A3,C)). + +?TGT_IFACE_2(bb). +?TGT_IFACE_1(def_use). +?TGT_IFACE_1(defines_all_alloc). +?TGT_IFACE_1(is_precoloured). +?TGT_IFACE_1(labels). +?TGT_IFACE_1(mk_goto). +?TGT_IFACE_2(mk_move). +?TGT_IFACE_0(new_label). +?TGT_IFACE_0(new_reg_nr). +?TGT_IFACE_3(redirect_jmp). +?TGT_IFACE_1(reg_nr). +?TGT_IFACE_1(reverse_postorder). +?TGT_IFACE_2(subst_temps). +?TGT_IFACE_3(update_bb). +?TGT_IFACE_2(update_reg_nr). + +liveout(Liveness, L, Target={TgtMod,TgtCtx}) -> + ordsets:from_list(reg_names(TgtMod:liveout(Liveness, L, TgtCtx), Target)). + +reg_names(Regs, {TgtMod,TgtCtx}) -> + [TgtMod:reg_nr(X,TgtCtx) || X <- Regs]. + +reg_def_use(I, Target) -> + {TDef, TUse} = def_use(I, Target), + {reg_names(TDef, Target), reg_names(TUse, Target)}. diff --git a/lib/hipe/regalloc/hipe_sparc_specific.erl b/lib/hipe/regalloc/hipe_sparc_specific.erl index 8d34604f84..78b6379eba 100644 --- a/lib/hipe/regalloc/hipe_sparc_specific.erl +++ b/lib/hipe/regalloc/hipe_sparc_specific.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,121 +11,138 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -module(hipe_sparc_specific). %% for hipe_coalescing_regalloc: --export([number_of_temporaries/1 - ,analyze/1 - ,labels/1 - ,all_precoloured/0 - ,bb/2 - ,liveout/2 - ,reg_nr/1 - ,def_use/1 - ,is_move/1 - ,is_precoloured/1 - ,var_range/1 - ,allocatable/0 - ,non_alloc/1 - ,physical_name/1 - ,reverse_postorder/1 - ,livein/2 - ,uses/1 - ,defines/1 +-export([number_of_temporaries/2 + ,analyze/2 + ,labels/2 + ,all_precoloured/1 + ,bb/3 + ,liveout/3 + ,reg_nr/2 + ,def_use/2 + ,is_move/2 + ,is_spill_move/2 + ,is_precoloured/2 + ,var_range/2 + ,allocatable/1 + ,non_alloc/2 + ,physical_name/2 + ,reverse_postorder/2 + ,livein/3 + ,uses/2 + ,defines/2 + ,defines_all_alloc/2 ]). %% for hipe_graph_coloring_regalloc: --export([is_fixed/1]). +-export([is_fixed/2]). %% for hipe_ls_regalloc: --export([args/1, is_arg/1, is_global/1, new_spill_index/1]). --export([breadthorder/1, postorder/1]). +-export([args/2, is_arg/2, is_global/2, new_spill_index/2]). +-export([breadthorder/2, postorder/2]). %% callbacks for hipe_regalloc_loop --export([defun_to_cfg/1, - check_and_rewrite/2]). +-export([check_and_rewrite/3]). + +%% callbacks for hipe_regalloc_prepass, hipe_range_split +-export([mk_move/3, + mk_goto/2, + redirect_jmp/4, + new_label/1, + new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -defun_to_cfg(Defun) -> - hipe_sparc_cfg:init(Defun). +%% callbacks for hipe_bb_weights, hipe_range_split +-export([branch_preds/2]). -check_and_rewrite(Defun, Coloring) -> - hipe_sparc_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal'). +check_and_rewrite(CFG, Coloring, no_context) -> + hipe_sparc_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal'). -reverse_postorder(CFG) -> +reverse_postorder(CFG, _) -> hipe_sparc_cfg:reverse_postorder(CFG). -non_alloc(CFG) -> - non_alloc(hipe_sparc_registers:nr_args(), hipe_sparc_cfg:params(CFG)). +non_alloc(CFG, no_context) -> + non_alloc_1(hipe_sparc_registers:nr_args(), hipe_sparc_cfg:params(CFG)). %% same as hipe_sparc_frame:fix_formals/2 -non_alloc(0, Rest) -> Rest; -non_alloc(N, [_|Rest]) -> non_alloc(N-1, Rest); -non_alloc(_, []) -> []. +non_alloc_1(0, Rest) -> Rest; +non_alloc_1(N, [_|Rest]) -> non_alloc_1(N-1, Rest); +non_alloc_1(_, []) -> []. %% Liveness stuff -analyze(CFG) -> +analyze(CFG, _) -> hipe_sparc_liveness_gpr:analyse(CFG). -livein(Liveness,L) -> +livein(Liveness,L,_) -> [X || X <- hipe_sparc_liveness_gpr:livein(Liveness,L), hipe_sparc:temp_is_allocatable(X)]. -liveout(BB_in_out_liveness,Label) -> +liveout(BB_in_out_liveness,Label,_) -> [X || X <- hipe_sparc_liveness_gpr:liveout(BB_in_out_liveness,Label), hipe_sparc:temp_is_allocatable(X)]. %% Registers stuff -allocatable() -> +allocatable(no_context) -> hipe_sparc_registers:allocatable_gpr(). -all_precoloured() -> +all_precoloured(no_context) -> hipe_sparc_registers:all_precoloured(). -is_precoloured(Reg) -> +is_precoloured(Reg, _) -> hipe_sparc_registers:is_precoloured_gpr(Reg). -is_fixed(R) -> +is_fixed(R, _) -> hipe_sparc_registers:is_fixed(R). -physical_name(Reg) -> +physical_name(Reg, _) -> Reg. %% CFG stuff -labels(CFG) -> +labels(CFG, _) -> hipe_sparc_cfg:labels(CFG). -var_range(_CFG) -> +var_range(_CFG, _) -> hipe_gensym:var_range(sparc). -number_of_temporaries(_CFG) -> +number_of_temporaries(_CFG, _) -> Highest_temporary = hipe_gensym:get_var(sparc), %% Since we can have temps from 0 to Max adjust by +1. Highest_temporary + 1. -bb(CFG,L) -> +bb(CFG,L,_) -> hipe_sparc_cfg:bb(CFG,L). +update_bb(CFG,L,BB,_) -> + hipe_sparc_cfg:bb_add(CFG,L,BB). + +branch_preds(Branch,_) -> + hipe_sparc_cfg:branch_preds(Branch). + %% SPARC stuff -def_use(Instruction) -> - {defines(Instruction), uses(Instruction)}. +def_use(Instruction, Ctx) -> + {defines(Instruction, Ctx), uses(Instruction, Ctx)}. -uses(I) -> +uses(I, _) -> [X || X <- hipe_sparc_defuse:insn_use_gpr(I), hipe_sparc:temp_is_allocatable(X)]. -defines(I) -> +defines(I, _) -> [X || X <- hipe_sparc_defuse:insn_def_gpr(I), hipe_sparc:temp_is_allocatable(X)]. -is_move(Instruction) -> +defines_all_alloc(I, _) -> + hipe_sparc_defuse:insn_defs_all_gpr(I). + +is_move(Instruction, _) -> case hipe_sparc:is_pseudo_move(Instruction) of true -> Dst = hipe_sparc:pseudo_move_dst(Instruction), @@ -142,28 +155,60 @@ is_move(Instruction) -> false -> false end. -reg_nr(Reg) -> +is_spill_move(Instruction, _) -> + hipe_sparc:is_pseudo_spill_move(Instruction). + +reg_nr(Reg, _) -> hipe_sparc:temp_reg(Reg). +mk_move(Src, Dst, _) -> + hipe_sparc:mk_pseudo_move(Src, Dst). + +mk_goto(Label, _) -> + hipe_sparc:mk_b_label(Label). + +redirect_jmp(Jmp, ToOld, ToNew, _) when is_integer(ToOld), is_integer(ToNew) -> + hipe_sparc_cfg:redirect_jmp(Jmp, ToOld, ToNew). + +new_label(_) -> + hipe_gensym:get_next_label(sparc). + +new_reg_nr(_) -> + hipe_gensym:get_next_var(sparc). + +update_reg_nr(Nr, Temp, _) -> + hipe_sparc:mk_temp(Nr, hipe_sparc:temp_type(Temp)). + +subst_temps(SubstFun, Instr, _) -> + hipe_sparc_subst:insn_temps( + fun(Op) -> + case hipe_sparc:temp_is_allocatable(Op) + andalso hipe_sparc:temp_type(Op) =/= 'double' + of + true -> SubstFun(Op); + false -> Op + end + end, Instr). + %%% Linear Scan stuff -new_spill_index(SpillIndex) when is_integer(SpillIndex) -> +new_spill_index(SpillIndex, _) when is_integer(SpillIndex) -> SpillIndex+1. -breadthorder(CFG) -> +breadthorder(CFG, _) -> hipe_sparc_cfg:breadthorder(CFG). -postorder(CFG) -> +postorder(CFG, _) -> hipe_sparc_cfg:postorder(CFG). -is_global(R) -> +is_global(R, _) -> R =:= hipe_sparc_registers:temp1() orelse R =:= hipe_sparc_registers:temp2() orelse R =:= hipe_sparc_registers:temp3() orelse hipe_sparc_registers:is_fixed(R). -is_arg(R) -> +is_arg(R, _) -> hipe_sparc_registers:is_arg(R). -args(CFG) -> +args(CFG, _) -> hipe_sparc_registers:args(hipe_sparc_cfg:arity(CFG)). diff --git a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl index 2edd3cb47e..485fdc212a 100644 --- a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl +++ b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2002-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,133 +11,182 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -module(hipe_sparc_specific_fp). %% for hipe_coalescing_regalloc: --export([number_of_temporaries/1 - ,analyze/1 - ,labels/1 - ,all_precoloured/0 - ,bb/2 - ,liveout/2 - ,reg_nr/1 - ,def_use/1 - ,is_move/1 - ,is_precoloured/1 - ,var_range/1 - ,allocatable/0 - ,non_alloc/1 - ,physical_name/1 - ,reverse_postorder/1 - ,livein/2 - ,uses/1 - ,defines/1 +-export([number_of_temporaries/2 + ,analyze/2 + ,labels/2 + ,all_precoloured/1 + ,bb/3 + ,liveout/3 + ,reg_nr/2 + ,def_use/2 + ,is_move/2 + ,is_spill_move/2 + ,is_precoloured/2 + ,var_range/2 + ,allocatable/1 + ,non_alloc/2 + ,physical_name/2 + ,reverse_postorder/2 + ,livein/3 + ,uses/2 + ,defines/2 + ,defines_all_alloc/2 ]). %% for hipe_graph_coloring_regalloc: --export([is_fixed/1]). +-export([is_fixed/2]). %% for hipe_ls_regalloc: -%%-export([args/1, is_arg/1, is_global, new_spill_index/1]). -%%-export([breadthorder/1, postorder/1]). +%%-export([args/2, is_arg/2, is_global, new_spill_index/2]). +%%-export([breadthorder/2, postorder/2]). %% callbacks for hipe_regalloc_loop --export([defun_to_cfg/1, - check_and_rewrite/2]). +-export([check_and_rewrite/3]). + +%% callbacks for hipe_regalloc_prepass, hipe_range_split +-export([mk_move/3, + mk_goto/2, + redirect_jmp/4, + new_label/1, + new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -defun_to_cfg(Defun) -> - hipe_sparc_cfg:init(Defun). +%% callbacks for hipe_bb_weights, hipe_range_split +-export([branch_preds/2]). -check_and_rewrite(Defun, Coloring) -> - hipe_sparc_ra_postconditions_fp:check_and_rewrite(Defun, Coloring). +check_and_rewrite(CFG, Coloring, no_context) -> + hipe_sparc_ra_postconditions_fp:check_and_rewrite(CFG, Coloring). -reverse_postorder(CFG) -> +reverse_postorder(CFG, _) -> hipe_sparc_cfg:reverse_postorder(CFG). -non_alloc(_CFG) -> +non_alloc(_CFG, _) -> []. %% Liveness stuff -analyze(CFG) -> +analyze(CFG, _) -> hipe_sparc_liveness_fpr:analyse(CFG). -livein(Liveness, L) -> +livein(Liveness, L, _) -> hipe_sparc_liveness_fpr:livein(Liveness, L). -liveout(BB_in_out_liveness, Label) -> +liveout(BB_in_out_liveness, Label, _) -> hipe_sparc_liveness_fpr:liveout(BB_in_out_liveness, Label). %% Registers stuff -allocatable() -> +allocatable(no_context) -> hipe_sparc_registers:allocatable_fpr(). -all_precoloured() -> - allocatable(). +all_precoloured(Ctx) -> + allocatable(Ctx). -is_precoloured(Reg) -> +is_precoloured(Reg, _) -> hipe_sparc_registers:is_precoloured_fpr(Reg). -is_fixed(_Reg) -> +is_fixed(_Reg, _) -> false. -physical_name(Reg) -> +physical_name(Reg, _) -> Reg. %% CFG stuff -labels(CFG) -> +labels(CFG, _) -> hipe_sparc_cfg:labels(CFG). -var_range(_CFG) -> +var_range(_CFG, _) -> hipe_gensym:var_range(sparc). -number_of_temporaries(_CFG) -> +number_of_temporaries(_CFG, _) -> Highest_temporary = hipe_gensym:get_var(sparc), %% Since we can have temps from 0 to Max adjust by +1. Highest_temporary + 1. -bb(CFG, L) -> +bb(CFG, L, _) -> hipe_sparc_cfg:bb(CFG, L). +update_bb(CFG,L,BB,_) -> + hipe_sparc_cfg:bb_add(CFG,L,BB). + +branch_preds(Branch,_) -> + hipe_sparc_cfg:branch_preds(Branch). + %% SPARC stuff -def_use(I) -> - {defines(I), uses(I)}. +def_use(I, Ctx) -> + {defines(I,Ctx), uses(I,Ctx)}. -uses(I) -> +uses(I, _) -> hipe_sparc_defuse:insn_use_fpr(I). -defines(I) -> +defines(I, _) -> hipe_sparc_defuse:insn_def_fpr(I). -is_move(I) -> +defines_all_alloc(I, _) -> + hipe_sparc_defuse:insn_defs_all_fpr(I). + +is_move(I, _) -> hipe_sparc:is_pseudo_fmove(I). -reg_nr(Reg) -> +is_spill_move(I, _) -> + hipe_sparc:is_pseudo_spill_fmove(I). + +reg_nr(Reg, _) -> hipe_sparc:temp_reg(Reg). +mk_move(Src, Dst, _) -> + hipe_sparc:mk_pseudo_fmove(Src, Dst). + +mk_goto(Label, _) -> + hipe_sparc:mk_b_label(Label). + +redirect_jmp(Jmp, ToOld, ToNew, _) when is_integer(ToOld), is_integer(ToNew) -> + hipe_sparc_cfg:redirect_jmp(Jmp, ToOld, ToNew). + +new_label(_) -> + hipe_gensym:get_next_label(sparc). + +new_reg_nr(_) -> + hipe_gensym:get_next_var(sparc). + +update_reg_nr(Nr, _Temp, _) -> + hipe_sparc:mk_temp(Nr, 'double'). + +subst_temps(SubstFun, Instr, _) -> + hipe_sparc_subst:insn_temps( + fun(Op) -> + case hipe_sparc:temp_is_allocatable(Op) + andalso hipe_sparc:temp_type(Op) =:= 'double' + of + true -> SubstFun(Op); + false -> Op + end + end, Instr). + -ifdef(notdef). -new_spill_index(SpillIndex)-> +new_spill_index(SpillIndex, _)-> SpillIndex+1. -breadthorder(CFG) -> +breadthorder(CFG, _) -> hipe_sparc_cfg:breadthorder(CFG). -postorder(CFG) -> +postorder(CFG, _) -> hipe_sparc_cfg:postorder(CFG). -is_global(_R) -> +is_global(_R, _) -> false. -is_arg(_R) -> +is_arg(_R, _) -> false. -args(_CFG) -> +args(_CFG, _) -> []. -endif. diff --git a/lib/hipe/regalloc/hipe_spillcost.erl b/lib/hipe/regalloc/hipe_spillcost.erl index b241e637d9..906cdac1aa 100644 --- a/lib/hipe/regalloc/hipe_spillcost.erl +++ b/lib/hipe/regalloc/hipe_spillcost.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,9 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -module(hipe_spillcost). diff --git a/lib/hipe/regalloc/hipe_spillcost.hrl b/lib/hipe/regalloc/hipe_spillcost.hrl index 3cadcbe432..b1e84cee16 100644 --- a/lib/hipe/regalloc/hipe_spillcost.hrl +++ b/lib/hipe/regalloc/hipe_spillcost.hrl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2009-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,9 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -type hipe_array() :: integer(). @@ -25,4 +18,3 @@ {uses :: hipe_array(), % number of uses of each temp bb_uses :: hipe_array() % number of basic blocks each temp occurs in }). - diff --git a/lib/hipe/regalloc/hipe_temp_map.erl b/lib/hipe/regalloc/hipe_temp_map.erl index 4085a0e1a7..58145efb3e 100644 --- a/lib/hipe/regalloc/hipe_temp_map.erl +++ b/lib/hipe/regalloc/hipe_temp_map.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,12 +11,9 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% %% %% =========================================================================== %% Copyright (c) 2001 by Erik Johansson. All Rights Reserved -%% Time-stamp: <2008-04-20 14:54:00 richard> %% =========================================================================== %% Module : hipe_temp_map %% Purpose : @@ -33,10 +26,12 @@ -module(hipe_temp_map). --export([cols2tuple/2, is_spilled/2, to_substlist/1]). +-export([cols2tuple/3, find/2, is_spilled/2, to_substlist/1]). -include("../main/hipe.hrl"). +-type target_context() :: any(). + %%---------------------------------------------------------------------------- %% Convert a list of [{R0, C1}, {R1, C2}, ...] to a temp_map %% (Currently implemented as a tuple) tuple {C1, C2, ...}. @@ -47,34 +42,32 @@ %% element 1 %%---------------------------------------------------------------------------- --spec cols2tuple(hipe_map(), atom()) -> hipe_temp_map(). +-spec cols2tuple(hipe_map(), module(), target_context()) -> hipe_temp_map(). -cols2tuple(Map, Target) -> - ?ASSERT(check_list(Map)), - SortedMap = lists:keysort(1, Map), - cols2tuple(0, SortedMap, [], Target). +cols2tuple(Map, TgtMod, TgtCtx) -> + SortedMap = lists:keysort(1, Map), + cols2tuple(0, SortedMap, [], TgtMod, TgtCtx). -%% sorted_cols2tuple(Map, Target) -> -%% ?ASSERT(check_list(Map)), +%% sorted_cols2tuple(Map, TgtMod, TgtCtx) -> %% ?ASSERT(Map =:= lists:keysort(1, Map)), -%% cols2tuple(0, Map, [], Target). +%% cols2tuple(0, Map, [], TgtMod, TgtCtx). %% Build a dense mapping -cols2tuple(_, [], Vs, _) -> +cols2tuple(_, [], Vs, _, _) -> %% Done reverse the list and convert to tuple. list_to_tuple(lists:reverse(Vs)); -cols2tuple(N, [{R, C}|Ms], Vs, Target) when N =:= R -> +cols2tuple(N, [{R, C}|Ms], Vs, TgtMod, TgtCtx) when N =:= R -> %% N makes sure the mapping is dense. N is he next key. - cols2tuple(N+1, Ms, [C|Vs], Target); -cols2tuple(N, SourceMapping, Vs, Target) -> + cols2tuple(N+1, Ms, [C|Vs], TgtMod, TgtCtx); +cols2tuple(N, SourceMapping=[{R,_}|_], Vs, TgtMod, TgtCtx) when N < R -> %% The source was sparse, make up some placeholders... Val = - case Target:is_precoloured(N) of + case TgtMod:is_precoloured(N, TgtCtx) of %% If it is precoloured, we know what to map it to. true -> {reg, N}; false -> unknown end, - cols2tuple(N+1, SourceMapping, [Val|Vs], Target). + cols2tuple(N+1, SourceMapping, [Val|Vs], TgtMod, TgtCtx). %% %% True if temp Temp is spilled. @@ -82,7 +75,7 @@ cols2tuple(N, SourceMapping, Vs, Target) -> -spec is_spilled(non_neg_integer(), hipe_temp_map()) -> boolean(). is_spilled(Temp, Map) -> - case element(Temp+1, Map) of + case find(Temp, Map) of {reg, _R} -> false; {fp_reg, _R}-> false; {spill, _N} -> true; @@ -106,9 +99,10 @@ is_spilled(Temp, Map) -> %% {spill, _N} -> false; %% unknown -> false %% end. -%% -%% %% Returns the inf temp Temp is mapped to. -%% find(Temp, Map) -> element(Temp+1, Map). + +%% Returns the inf temp Temp is mapped to. +find(Temp, Map) when Temp < tuple_size(Map) -> element(Temp+1, Map); +find(_, Map) when is_tuple(Map) -> unknown. % consistency with cols2tuple/3 %% diff --git a/lib/hipe/regalloc/hipe_x86_specific.erl b/lib/hipe/regalloc/hipe_x86_specific.erl index 4edf8674b7..dacfb71b00 100644 --- a/lib/hipe/regalloc/hipe_x86_specific.erl +++ b/lib/hipe/regalloc/hipe_x86_specific.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2001-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,9 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -ifdef(HIPE_AMD64). -define(HIPE_X86_SPECIFIC, hipe_amd64_specific). @@ -25,100 +18,113 @@ -define(HIPE_X86_REGISTERS, hipe_amd64_registers). -define(HIPE_X86_LIVENESS, hipe_amd64_liveness). -define(HIPE_X86_DEFUSE, hipe_amd64_defuse). +-define(HIPE_X86_SUBST, hipe_amd64_subst). -else. -define(HIPE_X86_SPECIFIC, hipe_x86_specific). -define(HIPE_X86_RA_POSTCONDITIONS, hipe_x86_ra_postconditions). -define(HIPE_X86_REGISTERS, hipe_x86_registers). -define(HIPE_X86_LIVENESS, hipe_x86_liveness). -define(HIPE_X86_DEFUSE, hipe_x86_defuse). +-define(HIPE_X86_SUBST, hipe_x86_subst). -endif. -module(?HIPE_X86_SPECIFIC). --export([number_of_temporaries/1]). +-export([number_of_temporaries/2]). %% The following exports are used as M:F(...) calls from other modules; %% e.g. hipe_x86_ra_ls. --export([analyze/1, - bb/2, - args/1, - labels/1, - livein/2, - liveout/2, - uses/1, - defines/1, - def_use/1, - is_arg/1, % used by hipe_ls_regalloc - is_move/1, - is_fixed/1, % used by hipe_graph_coloring_regalloc - is_global/1, - is_precoloured/1, - reg_nr/1, - non_alloc/1, - allocatable/0, - physical_name/1, - all_precoloured/0, - new_spill_index/1, % used by hipe_ls_regalloc - var_range/1, - breadthorder/1, - postorder/1, - reverse_postorder/1]). +-export([analyze/2, + bb/3, + args/2, + labels/2, + livein/3, + liveout/3, + uses/2, + defines/2, + defines_all_alloc/2, + def_use/2, + is_arg/2, % used by hipe_ls_regalloc + is_move/2, + is_spill_move/2, + is_fixed/2, % used by hipe_graph_coloring_regalloc + is_global/2, + is_precoloured/2, + reg_nr/2, + non_alloc/2, + allocatable/1, + physical_name/2, + all_precoloured/1, + new_spill_index/2, % used by hipe_ls_regalloc + var_range/2, + breadthorder/2, + postorder/2, + reverse_postorder/2]). %% callbacks for hipe_regalloc_loop --export([defun_to_cfg/1, - check_and_rewrite/2]). +-export([check_and_rewrite/3]). + +%% callbacks for hipe_regalloc_prepass, hipe_range_split +-export([mk_move/3, + mk_goto/2, + redirect_jmp/4, + new_label/1, + new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -defun_to_cfg(Defun) -> - hipe_x86_cfg:init(Defun). +%% callbacks for hipe_bb_weights +-export([branch_preds/2]). -check_and_rewrite(Defun, Coloring) -> - ?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite(Defun, Coloring, 'normal'). +check_and_rewrite(CFG, Coloring, _) -> + ?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite(CFG, Coloring, 'normal'). -reverse_postorder(CFG) -> +reverse_postorder(CFG, _) -> hipe_x86_cfg:reverse_postorder(CFG). -breadthorder(CFG) -> +breadthorder(CFG, _) -> hipe_x86_cfg:breadthorder(CFG). -postorder(CFG) -> +postorder(CFG, _) -> hipe_x86_cfg:postorder(CFG). %% Globally defined registers for linear scan -is_global(R) -> +is_global(R, _) -> ?HIPE_X86_REGISTERS:temp1() =:= R orelse ?HIPE_X86_REGISTERS:temp0() =:= R orelse ?HIPE_X86_REGISTERS:is_fixed(R). -is_fixed(R) -> +is_fixed(R, _) -> ?HIPE_X86_REGISTERS:is_fixed(R). -is_arg(R) -> +is_arg(R, _) -> ?HIPE_X86_REGISTERS:is_arg(R). -args(CFG) -> +args(CFG, _) -> ?HIPE_X86_REGISTERS:args(hipe_x86_cfg:arity(CFG)). -non_alloc(CFG) -> - non_alloc(?HIPE_X86_REGISTERS:nr_args(), hipe_x86_cfg:params(CFG)). +non_alloc(CFG, _) -> + non_alloc_1(?HIPE_X86_REGISTERS:nr_args(), hipe_x86_cfg:params(CFG)). %% same as hipe_x86_frame:fix_formals/2 -non_alloc(0, Rest) -> Rest; -non_alloc(N, [_|Rest]) -> non_alloc(N-1, Rest); -non_alloc(_, []) -> []. +non_alloc_1(0, Rest) -> Rest; +non_alloc_1(N, [_|Rest]) -> non_alloc_1(N-1, Rest); +non_alloc_1(_, []) -> []. %% Liveness stuff -analyze(CFG) -> +analyze(CFG, _) -> ?HIPE_X86_LIVENESS:analyze(CFG). -livein(Liveness,L) -> +livein(Liveness,L,_) -> [X || X <- ?HIPE_X86_LIVENESS:livein(Liveness,L), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_reg(X) =/= ?HIPE_X86_REGISTERS:fcalls(), hipe_x86:temp_reg(X) =/= ?HIPE_X86_REGISTERS:heap_limit(), hipe_x86:temp_type(X) =/= 'double']. -liveout(BB_in_out_liveness,Label) -> +liveout(BB_in_out_liveness,Label,_) -> [X || X <- ?HIPE_X86_LIVENESS:liveout(BB_in_out_liveness,Label), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_reg(X) =/= ?HIPE_X86_REGISTERS:fcalls(), @@ -127,37 +133,43 @@ liveout(BB_in_out_liveness,Label) -> %% Registers stuff -allocatable() -> +allocatable(_) -> ?HIPE_X86_REGISTERS:allocatable(). -all_precoloured() -> +all_precoloured(_) -> ?HIPE_X86_REGISTERS:all_precoloured(). -is_precoloured(Reg) -> +is_precoloured(Reg,_) -> ?HIPE_X86_REGISTERS:is_precoloured(Reg). -physical_name(Reg) -> +physical_name(Reg,_) -> Reg. %% CFG stuff -labels(CFG) -> +labels(CFG,_) -> hipe_x86_cfg:labels(CFG). -var_range(_CFG) -> +var_range(_CFG,_) -> hipe_gensym:var_range(x86). -number_of_temporaries(_CFG) -> +number_of_temporaries(_CFG,_) -> Highest_temporary = hipe_gensym:get_var(x86), %% Since we can have temps from 0 to Max adjust by +1. Highest_temporary + 1. -bb(CFG,L) -> +bb(CFG,L,_) -> hipe_x86_cfg:bb(CFG,L). +update_bb(CFG,L,BB,_) -> + hipe_x86_cfg:bb_add(CFG,L,BB). + +branch_preds(Instr,_) -> + hipe_x86_cfg:branch_preds(Instr). + %% X86 stuff -def_use(Instruction) -> +def_use(Instruction,_) -> {[X || X <- ?HIPE_X86_DEFUSE:insn_def(Instruction), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_type(X) =/= 'double'], @@ -166,17 +178,19 @@ def_use(Instruction) -> hipe_x86:temp_type(X) =/= 'double'] }. -uses(I) -> +uses(I,_) -> [X || X <- ?HIPE_X86_DEFUSE:insn_use(I), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_type(X) =/= 'double']. -defines(I) -> +defines(I,_) -> [X || X <- ?HIPE_X86_DEFUSE:insn_def(I), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_type(X) =/= 'double']. -is_move(Instruction) -> +defines_all_alloc(I,_) -> ?HIPE_X86_DEFUSE:insn_defs_all(I). + +is_move(Instruction,_) -> case hipe_x86:is_move(Instruction) of true -> Src = hipe_x86:move_src(Instruction), @@ -197,8 +211,49 @@ is_move(Instruction) -> false -> false end. -reg_nr(Reg) -> +is_spill_move(Instruction,_) -> + hipe_x86:is_pseudo_spill_move(Instruction). + +reg_nr(Reg,_) -> hipe_x86:temp_reg(Reg). -new_spill_index(SpillIndex) when is_integer(SpillIndex) -> +mk_move(Src, Dst, _) -> + hipe_x86:mk_move(Src, Dst). + +mk_goto(Label, _) -> + hipe_x86:mk_jmp_label(Label). + +redirect_jmp(Jmp, ToOld, ToNew, _) when is_integer(ToOld), is_integer(ToNew) -> + Ref = make_ref(), + put(Ref, false), + I = hipe_x86_subst:insn_lbls( + fun(Tgt) -> + if Tgt =:= ToOld -> put(Ref, true), ToNew; + is_integer(Tgt) -> Tgt + end + end, Jmp), + true = erase(Ref), % Assert that something was rewritten + I. + +new_label(_) -> + hipe_gensym:get_next_label(x86). + +new_reg_nr(_) -> + hipe_gensym:get_next_var(x86). + +update_reg_nr(Nr, Temp, _) -> + hipe_x86:mk_temp(Nr, hipe_x86:temp_type(Temp)). + +subst_temps(SubstFun, Instr, _) -> + ?HIPE_X86_SUBST:insn_temps( + fun(Op) -> + case hipe_x86:temp_is_allocatable(Op) + andalso hipe_x86:temp_type(Op) =/= 'double' + of + true -> SubstFun(Op); + false -> Op + end + end, Instr). + +new_spill_index(SpillIndex, _) when is_integer(SpillIndex) -> SpillIndex+1. diff --git a/lib/hipe/regalloc/hipe_x86_specific_x87.erl b/lib/hipe/regalloc/hipe_x86_specific_x87.erl index ece07cb2f9..3fe49e1f00 100644 --- a/lib/hipe/regalloc/hipe_x86_specific_x87.erl +++ b/lib/hipe/regalloc/hipe_x86_specific_x87.erl @@ -1,9 +1,5 @@ %% -*- erlang-indent-level: 2 -*- %% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2006-2016. All Rights Reserved. -%% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at @@ -15,9 +11,6 @@ %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. -%% -%% %CopyrightEnd% -%% -ifdef(HIPE_AMD64). -define(HIPE_X86_SPECIFIC_X87, hipe_amd64_specific_x87). @@ -32,110 +25,119 @@ -endif. -module(?HIPE_X86_SPECIFIC_X87). --export([allocatable/0, - is_precoloured/1, - %% var_range/1, - %% def_use/1, - %% is_fixed/1, - is_arg/1, - %% non_alloc/1, - new_spill_index/1, - number_of_temporaries/1 +-export([allocatable/2, + is_precoloured/2, + %% var_range/2, + %% def_use/2, + %% is_fixed/2, + is_arg/2, + %% non_alloc/2, + new_spill_index/2, + number_of_temporaries/2 ]). %% The following exports are used as M:F(...) calls from other modules; %% e.g. hipe_x86_ra_ls. --export([analyze/1, - bb/2, - args/1, - labels/1, - livein/2, - liveout/2, - uses/1, - defines/1, - is_global/1, - reg_nr/1, - physical_name/1, - breadthorder/1, - postorder/1, - reverse_postorder/1]). - -breadthorder(CFG) -> +-export([analyze/2, + bb/3, + args/2, + labels/2, + livein/3, + liveout/3, + uses/2, + defines/2, + defines_all_alloc/2, + is_spill_move/2, + is_global/2, + reg_nr/2, + physical_name/2, + breadthorder/2, + postorder/2, + reverse_postorder/2]). + +%% callbacks for hipe_x86_ra_ls +-export([check_and_rewrite/4]). + +%% Rewrite happens in hipe_x86_ra_finalise:finalise/4 +check_and_rewrite(CFG, _Coloring, 'linearscan', _) -> + {CFG, false}. + +breadthorder(CFG, _) -> hipe_x86_cfg:breadthorder(CFG). -postorder(CFG) -> +postorder(CFG, _) -> hipe_x86_cfg:postorder(CFG). -reverse_postorder(CFG) -> +reverse_postorder(CFG, _) -> hipe_x86_cfg:reverse_postorder(CFG). -is_global(_) -> +is_global(_, _) -> false. -ifdef(notdef). -is_fixed(_) -> +is_fixed(_, _) -> false. -endif. -is_arg(_) -> +is_arg(_, _) -> false. -args(_) -> +args(_, _) -> []. -ifdef(notdef). -non_alloc(_) -> +non_alloc(_, _) -> []. -endif. %% Liveness stuff -analyze(CFG) -> +analyze(CFG, _) -> ?HIPE_X86_LIVENESS:analyze(CFG). -livein(Liveness,L) -> +livein(Liveness,L,_) -> [X || X <- ?HIPE_X86_LIVENESS:livein(Liveness,L), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_type(X) =:= 'double']. -liveout(BB_in_out_liveness,Label) -> +liveout(BB_in_out_liveness,Label,_) -> [X || X <- ?HIPE_X86_LIVENESS:liveout(BB_in_out_liveness,Label), hipe_x86:temp_is_allocatable(X), hipe_x86:temp_type(X) =:= 'double']. %% Registers stuff -allocatable() -> +allocatable('linearscan', _) -> ?HIPE_X86_REGISTERS:allocatable_x87(). -is_precoloured(Reg) -> +is_precoloured(Reg, _) -> ?HIPE_X86_REGISTERS:is_precoloured_x87(Reg). -physical_name(Reg) -> +physical_name(Reg, _) -> Reg. %% CFG stuff -labels(CFG) -> +labels(CFG, _) -> hipe_x86_cfg:labels(CFG). -ifdef(notdef). -var_range(_CFG) -> +var_range(_CFG, _) -> {Min,Max} = hipe_gensym:var_range(x86), %% io:format("Var_range: ~w\n",[{Min,Max}]), {Min,Max}. -endif. -number_of_temporaries(_CFG) -> +number_of_temporaries(_CFG, _) -> Highest_temporary = hipe_gensym:get_var(x86), %% Since we can have temps from 0 to Max adjust by +1. Highest_temporary + 1. -bb(CFG,L) -> +bb(CFG,L,_) -> hipe_x86_cfg:bb(CFG,L). %% X86 stuff -ifdef(notdef). -def_use(Instruction) -> +def_use(Instruction, _) -> {[X || X <- ?HIPE_X86_DEFUSE:insn_def(Instruction), hipe_x86:temp_is_allocatable(X), temp_is_double(X)], @@ -145,21 +147,26 @@ def_use(Instruction) -> }. -endif. -uses(I) -> +uses(I, _) -> [X || X <- ?HIPE_X86_DEFUSE:insn_use(I), hipe_x86:temp_is_allocatable(X), temp_is_double(X)]. -defines(I) -> +defines(I, _) -> [X || X <- ?HIPE_X86_DEFUSE:insn_def(I), hipe_x86:temp_is_allocatable(X), temp_is_double(X)]. +defines_all_alloc(I, _) -> hipe_amd64_defuse:insn_defs_all(I). + +is_spill_move(I, _) -> + hipe_x86:is_pseudo_spill_fmove(I). + temp_is_double(Temp) -> hipe_x86:temp_type(Temp) =:= 'double'. -reg_nr(Reg) -> +reg_nr(Reg, _) -> hipe_x86:temp_reg(Reg). -new_spill_index(SpillIndex) -> +new_spill_index(SpillIndex, _) -> SpillIndex+1. |