aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/regalloc
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/regalloc')
-rw-r--r--lib/hipe/regalloc/Makefile2
-rw-r--r--lib/hipe/regalloc/hipe_adj_list.erl6
-rw-r--r--lib/hipe/regalloc/hipe_amd64_specific.erl9
-rw-r--r--lib/hipe/regalloc/hipe_amd64_specific_sse2.erl174
-rw-r--r--lib/hipe/regalloc/hipe_amd64_specific_x87.erl9
-rw-r--r--lib/hipe/regalloc/hipe_arm_specific.erl145
-rw-r--r--lib/hipe/regalloc/hipe_coalescing_regalloc.erl62
-rw-r--r--lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl92
-rw-r--r--lib/hipe/regalloc/hipe_ig.erl115
-rw-r--r--lib/hipe/regalloc/hipe_ig_moves.erl17
-rw-r--r--lib/hipe/regalloc/hipe_ls_regalloc.erl99
-rw-r--r--lib/hipe/regalloc/hipe_moves.erl7
-rw-r--r--lib/hipe/regalloc/hipe_node_sets.erl7
-rw-r--r--lib/hipe/regalloc/hipe_optimistic_regalloc.erl155
-rw-r--r--lib/hipe/regalloc/hipe_ppc_specific.erl147
-rw-r--r--lib/hipe/regalloc/hipe_ppc_specific_fp.erl141
-rw-r--r--lib/hipe/regalloc/hipe_reg_worklists.erl37
-rw-r--r--lib/hipe/regalloc/hipe_regalloc_loop.erl85
-rw-r--r--lib/hipe/regalloc/hipe_regalloc_prepass.erl1000
-rw-r--r--lib/hipe/regalloc/hipe_sparc_specific.erl147
-rw-r--r--lib/hipe/regalloc/hipe_sparc_specific_fp.erl141
-rw-r--r--lib/hipe/regalloc/hipe_spillcost.erl7
-rw-r--r--lib/hipe/regalloc/hipe_spillcost.hrl8
-rw-r--r--lib/hipe/regalloc/hipe_temp_map.erl46
-rw-r--r--lib/hipe/regalloc/hipe_x86_specific.erl154
-rw-r--r--lib/hipe/regalloc/hipe_x86_specific_x87.erl111
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..9c94539bc6 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, Ctx) ->
+ lists:member(Reg,all_precoloured(Ctx)).
+
+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.