diff options
Diffstat (limited to 'lib/hipe/regalloc')
26 files changed, 2053 insertions, 870 deletions
diff --git a/lib/hipe/regalloc/Makefile b/lib/hipe/regalloc/Makefile index aaa4418f37..209f230a9b 100644 --- a/lib/hipe/regalloc/Makefile +++ b/lib/hipe/regalloc/Makefile @@ -51,6 +51,7 @@ MODULES = hipe_ig hipe_ig_moves hipe_moves \ hipe_coalescing_regalloc \ hipe_graph_coloring_regalloc \ hipe_regalloc_loop \ + hipe_regalloc_prepass \ hipe_ls_regalloc \ hipe_ppc_specific hipe_ppc_specific_fp \ hipe_sparc_specific hipe_sparc_specific_fp \ @@ -123,7 +124,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..9682d37520 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,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% -%% -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_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 +-export([new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). %%---------------------------------------------------------------------------- @@ -60,86 +62,99 @@ %%---------------------------------------------------------------------------- -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()]. -all_precoloured() -> - allocatable(). +temp0(_) -> + hipe_amd64_registers:sse2_temp0(). -is_precoloured(Reg) -> - lists:member(Reg,all_precoloured()). +all_precoloured(Ctx) -> + allocatable(Ctx). -physical_name(Reg) -> +is_precoloured(Reg, _) -> + hipe_amd64_registers:is_precoloured_sse2(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). + %% 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 +163,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), @@ -168,9 +185,26 @@ is_move(Instruction) -> false -> false end. -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) -> +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..cef22e5af9 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,127 @@ %% 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_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]). -defun_to_cfg(Defun) -> - hipe_arm_cfg:init(Defun). +%% callbacks for hipe_regalloc_prepass +-export([new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -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). + %% 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 +144,43 @@ is_move(Instruction) -> false -> false end. -reg_nr(Reg) -> +reg_nr(Reg, _) -> hipe_arm:temp_reg(Reg). +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..e8ccbec9f1 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)). %%---------------------------------------------------------------------- @@ -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..07aa812f4a 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), @@ -234,7 +216,7 @@ color_0(IG, Spill, PhysRegs, SpillIx, SpillLimit, NumNodes, Target, ?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,7 +397,7 @@ 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 -> @@ -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..b96920cbcf 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 @@ -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..a6450b4d96 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,127 @@ %% 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_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]). -defun_to_cfg(Defun) -> - hipe_ppc_cfg:init(Defun). +%% callbacks for hipe_regalloc_prepass +-export([new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -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). + %% 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 +144,45 @@ is_move(Instruction) -> false -> false end. -reg_nr(Reg) -> +reg_nr(Reg, _) -> hipe_ppc:temp_reg(Reg). +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..23cb6c0318 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,156 @@ %% 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_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]). -defun_to_cfg(Defun) -> - hipe_ppc_cfg:init(Defun). +%% callbacks for hipe_regalloc_prepass +-export([new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -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). + %% 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) -> +reg_nr(Reg, _) -> hipe_ppc:temp_reg(Reg). +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_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..5bbb0ba7c1 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,48 @@ %%% 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). + SpillLimit0 = TargetMod:number_of_temporaries(CFG0, TargetCtx), + {Coloring, _, CFG, Liveness} = + call_allocator_initial(CFG0, Liveness0, 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 +61,38 @@ 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. diff --git a/lib/hipe/regalloc/hipe_regalloc_prepass.erl b/lib/hipe/regalloc/hipe_regalloc_prepass.erl new file mode 100644 index 0000000000..e212420ad2 --- /dev/null +++ b/lib/hipe/regalloc/hipe_regalloc_prepass.erl @@ -0,0 +1,1000 @@ +%% -*- 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} = dsets_find({entry,L}, DSets0), + {ExitRoot, DSets} = 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} = 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 = dsets_union(R1, R2, DSets0), + {R, DSets} = 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} = dsets_find({entry,L}, DSets0), + {ExitRoot, DSets2} = 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() :: 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 = 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) -> 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) -> dsets_union({entry,L}, {exit,L}, DS); + ({_, {split, _, _}}, DS) -> DS + end, DSets0, PartBBList). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% The disjoint set forests data structure, for elements of arbitrary types. +%% Note that the find operation mutates the set. +%% +%% We could do this more efficiently if we restricted the elements to integers, +%% and used the (mutable) hipe arrays. For arbitrary terms ETS could be used, +%% for a persistent interface (which isn't that nice when even accessors return +%% modified copies), the array module could be used. +-type dsets(X) :: #{X => {node, X} | {root, non_neg_integer()}}. + +-spec dsets_new([E]) -> dsets(E). +dsets_new(Elems) -> maps:from_list([{E,{root,0}} || E <- Elems]). + +-spec dsets_find(E, dsets(E)) -> {E, dsets(E)}. +dsets_find(E, DS0) -> + case DS0 of + #{E := {root,_}} -> {E, DS0}; + #{E := {node,N}} -> + case dsets_find(N, DS0) of + {N, _}=T -> T; + {R, DS1} -> {R, DS1#{E := {node,R}}} + end + ;_ -> error(badarg, [E, DS0]) + end. + +-spec dsets_union(E, E, dsets(E)) -> dsets(E). +dsets_union(X, Y, DS0) -> + {XRoot, DS1} = dsets_find(X, DS0), + case dsets_find(Y, DS1) of + {XRoot, DS2} -> DS2; + {YRoot, DS2} -> + #{XRoot := {root,XRR}, YRoot := {root,YRR}} = DS2, + if XRR < YRR -> DS2#{XRoot := {node,YRoot}}; + XRR > YRR -> DS2#{YRoot := {node,XRoot}}; + true -> DS2#{YRoot := {node,XRoot}, XRoot := {root,XRR+1}} + end + end. + +-spec dsets_to_rllist(dsets(E)) -> {[{Root::E, Elems::[E]}], dsets(E)}. +dsets_to_rllist(DS0) -> + {Lists, DS} = dsets_to_rllist(maps:keys(DS0), #{}, DS0), + {maps:to_list(Lists), DS}. + +dsets_to_rllist([], Acc, DS) -> {Acc, DS}; +dsets_to_rllist([E|Es], Acc, DS0) -> + {ERoot, DS} = dsets_find(E, DS0), + dsets_to_rllist(Es, map_append(ERoot, E, Acc), DS). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% 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_sparc_specific.erl b/lib/hipe/regalloc/hipe_sparc_specific.erl index 8d34604f84..31fca81316 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,127 @@ %% 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_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]). -defun_to_cfg(Defun) -> - hipe_sparc_cfg:init(Defun). +%% callbacks for hipe_regalloc_prepass +-export([new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -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). + %% 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 +144,45 @@ is_move(Instruction) -> false -> false end. -reg_nr(Reg) -> +reg_nr(Reg, _) -> hipe_sparc:temp_reg(Reg). +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..050d65e1a9 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,156 @@ %% 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_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]). -defun_to_cfg(Defun) -> - hipe_sparc_cfg:init(Defun). +%% callbacks for hipe_regalloc_prepass +-export([new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -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). + %% 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) -> +reg_nr(Reg, _) -> hipe_sparc:temp_reg(Reg). +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..c1c8dbbcd6 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,105 @@ -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_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]). -defun_to_cfg(Defun) -> - hipe_x86_cfg:init(Defun). +%% callbacks for hipe_regalloc_prepass +-export([new_reg_nr/1, + update_reg_nr/3, + update_bb/4, + subst_temps/3]). -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 +125,40 @@ 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). + %% 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 +167,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 +200,25 @@ is_move(Instruction) -> false -> false end. -reg_nr(Reg) -> +reg_nr(Reg,_) -> hipe_x86:temp_reg(Reg). -new_spill_index(SpillIndex) when is_integer(SpillIndex) -> +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..4b4c83f76d 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,118 @@ -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_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 +146,23 @@ 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). + 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. |