aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2016-09-09 18:53:02 +0200
committerSverker Eriksson <[email protected]>2016-09-09 18:53:02 +0200
commit45bd8440673a814e068397235ce7794f22f1e3f5 (patch)
tree4525e75fff69e990ba308bf1bc7a99346ffdda4e /lib/hipe
parent8f6c2f8fb8e3bf2c7c6ebbc77ed2b0428d40fd78 (diff)
parentea710644b198f7800f0daf2de0d152cf8e3e9bb3 (diff)
downloadotp-45bd8440673a814e068397235ce7794f22f1e3f5.tar.gz
otp-45bd8440673a814e068397235ce7794f22f1e3f5.tar.bz2
otp-45bd8440673a814e068397235ce7794f22f1e3f5.zip
Merge branch 'sverker/hipe-speedy-reg-alloc/PR-1159/OTP-13879'
* sverker/hipe-speedy-reg-alloc/PR-1159: hipe: Refactor ra callbacks to accept context arg hipe: Reuse liveness between regalloc iterations hipe: Add ra_partitioned to o1 and up hipe_regalloc_prepass: Change splitting heuristic hipe: Make sure prepass temps are below SpillLimit hipe_regalloc_prepass: Rename coloring collisions hipe_ppc: Add code rewrite RA callbacks hipe_sparc: Add code rewrite RA callbacks hipe_arm: Add code rewrite RA callbacks hipe_x86: Add code rewrite RA callbacks hipe: Remove defun_to_cfg/1 RA callback Add new sanity assertion to hipe_regalloc_prepass Simplify hipe_x86_ra_finalise:conv_ra_maplet/3 hipe_x86: Simplify ra_postconditions is_mem_opnd hipe_x86: Fix pseudo_tailcall prettyprinting hipe_x86: Extra sanity assertions hipe: clean up unnecessary catches hipe: Remove temp reuse from call_fun hipe: Add IG partitioning to hipe_regalloc_prepass hipe: Add hipe_regalloc_prepass
Diffstat (limited to 'lib/hipe')
-rw-r--r--lib/hipe/amd64/Makefile1
-rw-r--r--lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl19
-rw-r--r--lib/hipe/amd64/hipe_amd64_registers.erl3
-rw-r--r--lib/hipe/amd64/hipe_amd64_subst.erl21
-rw-r--r--lib/hipe/arm/Makefile1
-rw-r--r--lib/hipe/arm/hipe_arm_defuse.erl7
-rw-r--r--lib/hipe/arm/hipe_arm_ra.erl28
-rw-r--r--lib/hipe/arm/hipe_arm_ra_ls.erl29
-rw-r--r--lib/hipe/arm/hipe_arm_ra_naive.erl6
-rw-r--r--lib/hipe/arm/hipe_arm_ra_postconditions.erl2
-rw-r--r--lib/hipe/arm/hipe_arm_registers.erl2
-rw-r--r--lib/hipe/arm/hipe_arm_subst.erl112
-rw-r--r--lib/hipe/main/hipe.app.src6
-rw-r--r--lib/hipe/main/hipe.erl6
-rw-r--r--lib/hipe/opt/hipe_spillmin.erl30
-rw-r--r--lib/hipe/opt/hipe_spillmin_color.erl33
-rw-r--r--lib/hipe/opt/hipe_spillmin_scan.erl44
-rw-r--r--lib/hipe/ppc/Makefile1
-rw-r--r--lib/hipe/ppc/hipe_ppc_defuse.erl7
-rw-r--r--lib/hipe/ppc/hipe_ppc_ra.erl28
-rw-r--r--lib/hipe/ppc/hipe_ppc_ra_ls.erl29
-rw-r--r--lib/hipe/ppc/hipe_ppc_ra_naive.erl6
-rw-r--r--lib/hipe/ppc/hipe_ppc_ra_postconditions.erl2
-rw-r--r--lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl2
-rw-r--r--lib/hipe/ppc/hipe_ppc_registers.erl2
-rw-r--r--lib/hipe/ppc/hipe_ppc_subst.erl82
-rw-r--r--lib/hipe/regalloc/Makefile1
-rw-r--r--lib/hipe/regalloc/hipe_amd64_specific_sse2.erl161
-rw-r--r--lib/hipe/regalloc/hipe_arm_specific.erl136
-rw-r--r--lib/hipe/regalloc/hipe_coalescing_regalloc.erl52
-rw-r--r--lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl90
-rw-r--r--lib/hipe/regalloc/hipe_ig.erl108
-rw-r--r--lib/hipe/regalloc/hipe_ls_regalloc.erl97
-rw-r--r--lib/hipe/regalloc/hipe_optimistic_regalloc.erl142
-rw-r--r--lib/hipe/regalloc/hipe_ppc_specific.erl138
-rw-r--r--lib/hipe/regalloc/hipe_ppc_specific_fp.erl132
-rw-r--r--lib/hipe/regalloc/hipe_reg_worklists.erl31
-rw-r--r--lib/hipe/regalloc/hipe_regalloc_loop.erl77
-rw-r--r--lib/hipe/regalloc/hipe_regalloc_prepass.erl1006
-rw-r--r--lib/hipe/regalloc/hipe_sparc_specific.erl138
-rw-r--r--lib/hipe/regalloc/hipe_sparc_specific_fp.erl132
-rw-r--r--lib/hipe/regalloc/hipe_temp_map.erl39
-rw-r--r--lib/hipe/regalloc/hipe_x86_specific.erl145
-rw-r--r--lib/hipe/regalloc/hipe_x86_specific_x87.erl99
-rw-r--r--lib/hipe/rtl/hipe_rtl_primops.erl17
-rw-r--r--lib/hipe/sparc/Makefile3
-rw-r--r--lib/hipe/sparc/hipe_sparc_defuse.erl13
-rw-r--r--lib/hipe/sparc/hipe_sparc_ra.erl27
-rw-r--r--lib/hipe/sparc/hipe_sparc_ra_ls.erl29
-rw-r--r--lib/hipe/sparc/hipe_sparc_ra_naive.erl6
-rw-r--r--lib/hipe/sparc/hipe_sparc_ra_postconditions.erl2
-rw-r--r--lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl3
-rw-r--r--lib/hipe/sparc/hipe_sparc_registers.erl2
-rw-r--r--lib/hipe/sparc/hipe_sparc_subst.erl85
-rw-r--r--lib/hipe/x86/Makefile1
-rw-r--r--lib/hipe/x86/hipe_x86_defuse.erl12
-rw-r--r--lib/hipe/x86/hipe_x86_pp.erl2
-rw-r--r--lib/hipe/x86/hipe_x86_ra.erl51
-rw-r--r--lib/hipe/x86/hipe_x86_ra_finalise.erl40
-rw-r--r--lib/hipe/x86/hipe_x86_ra_ls.erl48
-rw-r--r--lib/hipe/x86/hipe_x86_ra_naive.erl8
-rw-r--r--lib/hipe/x86/hipe_x86_ra_postconditions.erl40
-rw-r--r--lib/hipe/x86/hipe_x86_registers.erl2
-rw-r--r--lib/hipe/x86/hipe_x86_subst.erl94
64 files changed, 2745 insertions, 973 deletions
diff --git a/lib/hipe/amd64/Makefile b/lib/hipe/amd64/Makefile
index ea3559b7e6..617f6749ac 100644
--- a/lib/hipe/amd64/Makefile
+++ b/lib/hipe/amd64/Makefile
@@ -59,6 +59,7 @@ MODULES=hipe_amd64_assemble \
hipe_amd64_ra_sse2_postconditions \
hipe_amd64_registers \
hipe_amd64_spill_restore \
+ hipe_amd64_subst \
hipe_amd64_x87 \
hipe_amd64_sse2 \
hipe_rtl_to_amd64
diff --git a/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl b/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl
index bbf9170bc3..d062c0b37c 100644
--- a/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl
+++ b/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl
@@ -34,7 +34,7 @@ check_and_rewrite(AMD64CFG, Coloring) ->
check_and_rewrite(AMD64CFG, Coloring, Strategy) ->
%%io:format("Converting\n"),
- TempMap = hipe_temp_map:cols2tuple(Coloring,hipe_amd64_specific_sse2),
+ TempMap = hipe_temp_map:cols2tuple(Coloring,hipe_amd64_specific_sse2,no_context),
%%io:format("Rewriting\n"),
do_bbs(hipe_x86_cfg:labels(AMD64CFG), TempMap, Strategy, AMD64CFG, false).
@@ -119,17 +119,12 @@ is_mem_opnd(Opnd, TempMap) ->
#x86_temp{type=double} ->
Reg = hipe_x86:temp_reg(Opnd),
case hipe_x86:temp_is_allocatable(Opnd) of
- true ->
- case tuple_size(TempMap) > Reg of
+ true ->
+ case hipe_temp_map:is_spilled(Reg, TempMap) of
true ->
- case
- hipe_temp_map:is_spilled(Reg, TempMap) of
- true ->
- ?count_temp(Reg),
- true;
- false -> false
- end;
- _ -> false
+ ?count_temp(Reg),
+ true;
+ false -> false
end;
false -> true
end;
@@ -149,7 +144,7 @@ clone(Dst, Strategy) ->
spill_temp(Type, 'normal') ->
hipe_x86:mk_new_temp(Type);
spill_temp(double, 'linearscan') ->
- hipe_x86:mk_temp(hipe_amd64_specific_sse2:temp0(), double);
+ hipe_x86:mk_temp(hipe_amd64_specific_sse2:temp0(no_context), double);
spill_temp(Type, 'linearscan') when Type =:= tagged; Type =/= untagged ->
%% We can make a new temp here since we have yet to allocate registers for
%% these types
diff --git a/lib/hipe/amd64/hipe_amd64_registers.erl b/lib/hipe/amd64/hipe_amd64_registers.erl
index ada5311453..7c6965b938 100644
--- a/lib/hipe/amd64/hipe_amd64_registers.erl
+++ b/lib/hipe/amd64/hipe_amd64_registers.erl
@@ -253,6 +253,9 @@ ret(N) ->
_ -> exit({?MODULE, ret, N})
end.
+%% Note: the fact that (allocatable() UNION allocatable_x87() UNION
+%% allocatable_sse2()) is a subset of call_clobbered() is hard-coded in
+%% hipe_x86_defuse:insn_defs_all/1
call_clobbered() ->
[{?RAX,tagged},{?RAX,untagged}, % does the RA strip the type or not?
{?RDX,tagged},{?RDX,untagged},
diff --git a/lib/hipe/amd64/hipe_amd64_subst.erl b/lib/hipe/amd64/hipe_amd64_subst.erl
new file mode 100644
index 0000000000..7d0f06684b
--- /dev/null
+++ b/lib/hipe/amd64/hipe_amd64_subst.erl
@@ -0,0 +1,21 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 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
+%%
+%% 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.
+%%
+%% %CopyrightEnd%
+%%
+
+-include("../x86/hipe_x86_subst.erl").
diff --git a/lib/hipe/arm/Makefile b/lib/hipe/arm/Makefile
index 00b6732afa..ed2eccf428 100644
--- a/lib/hipe/arm/Makefile
+++ b/lib/hipe/arm/Makefile
@@ -61,6 +61,7 @@ MODULES=hipe_arm \
hipe_arm_ra_naive \
hipe_arm_ra_postconditions \
hipe_arm_registers \
+ hipe_arm_subst \
hipe_rtl_to_arm
HRL_FILES=hipe_arm.hrl
diff --git a/lib/hipe/arm/hipe_arm_defuse.erl b/lib/hipe/arm/hipe_arm_defuse.erl
index f57b0e601c..f92cf4f82a 100644
--- a/lib/hipe/arm/hipe_arm_defuse.erl
+++ b/lib/hipe/arm/hipe_arm_defuse.erl
@@ -22,6 +22,7 @@
-module(hipe_arm_defuse).
-export([insn_def_all/1, insn_use_all/1]).
-export([insn_def_gpr/1, insn_use_gpr/1]).
+-export([insn_defs_all_gpr/1]).
-include("hipe_arm.hrl").
%%%
@@ -55,6 +56,12 @@ insn_def_gpr(I) ->
_ -> []
end.
+insn_defs_all_gpr(I) ->
+ case I of
+ #pseudo_call{} -> true;
+ _ -> false
+ end.
+
call_clobbered_gpr() ->
[hipe_arm:mk_temp(R, T)
|| {R,T} <- hipe_arm_registers:call_clobbered() ++ all_fp_pseudos()].
diff --git a/lib/hipe/arm/hipe_arm_ra.erl b/lib/hipe/arm/hipe_arm_ra.erl
index 5a7884b63c..bfb649326c 100644
--- a/lib/hipe/arm/hipe_arm_ra.erl
+++ b/lib/hipe/arm/hipe_arm_ra.erl
@@ -24,28 +24,31 @@
ra(CFG0, Options) ->
%% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG0)),
- {CFG1, Coloring_fp, SpillIndex}
+ {CFG1, _FPLiveness1, Coloring_fp, SpillIndex}
= case proplists:get_bool(inline_fp, Options) of
%% true ->
-%% hipe_regalloc_loop:ra_fp(CFG0, Options,
+%% FPLiveness0 = hipe_arm_specific_fp:analyze(CFG0, no_context),
+%% hipe_regalloc_loop:ra_fp(CFG0, FPLiveness0, Options,
%% hipe_coalescing_regalloc,
-%% hipe_arm_specific_fp);
+%% hipe_arm_specific_fp, no_context);
false ->
- {CFG0,[],0}
+ {CFG0,undefined,[],0}
end,
%% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG1)),
- {CFG2, Coloring}
+ GPLiveness1 = hipe_arm_specific:analyze(CFG1, no_context),
+ {CFG2, _GPLiveness2, Coloring}
= case proplists:get_value(regalloc, Options, coalescing) of
coalescing ->
- ra(CFG1, SpillIndex, Options, hipe_coalescing_regalloc);
+ ra(CFG1, GPLiveness1, SpillIndex, Options, hipe_coalescing_regalloc);
optimistic ->
- ra(CFG1, SpillIndex, Options, hipe_optimistic_regalloc);
+ ra(CFG1, GPLiveness1, SpillIndex, Options, hipe_optimistic_regalloc);
graph_color ->
- ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc);
+ ra(CFG1, GPLiveness1, SpillIndex, Options,
+ hipe_graph_coloring_regalloc);
linear_scan ->
- hipe_arm_ra_ls:ra(CFG1, SpillIndex, Options);
+ hipe_arm_ra_ls:ra(CFG1, GPLiveness1, SpillIndex, Options);
naive ->
- hipe_arm_ra_naive:ra(CFG1, Coloring_fp, Options);
+ hipe_arm_ra_naive:ra(CFG1, GPLiveness1, Coloring_fp, Options);
_ ->
exit({unknown_regalloc_compiler_option,
proplists:get_value(regalloc,Options)})
@@ -53,5 +56,6 @@ ra(CFG0, Options) ->
%% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG2)),
hipe_arm_ra_finalise:finalise(CFG2, Coloring, Coloring_fp).
-ra(CFG, SpillIndex, Options, RegAllocMod) ->
- hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, hipe_arm_specific).
+ra(CFG, Liveness, SpillIndex, Options, RegAllocMod) ->
+ hipe_regalloc_loop:ra(CFG, Liveness, SpillIndex, Options, RegAllocMod,
+ hipe_arm_specific, no_context).
diff --git a/lib/hipe/arm/hipe_arm_ra_ls.erl b/lib/hipe/arm/hipe_arm_ra_ls.erl
index f9193ca9e0..0aa888da99 100644
--- a/lib/hipe/arm/hipe_arm_ra_ls.erl
+++ b/lib/hipe/arm/hipe_arm_ra_ls.erl
@@ -21,34 +21,35 @@
%%% Linear Scan register allocator for ARM
-module(hipe_arm_ra_ls).
--export([ra/3]).
+-export([ra/4]).
-ra(CFG, SpillIndex, Options) ->
- SpillLimit = hipe_arm_specific:number_of_temporaries(CFG),
- alloc(CFG, SpillIndex, SpillLimit, Options).
+ra(CFG, Liveness, SpillIndex, Options) ->
+ SpillLimit = hipe_arm_specific:number_of_temporaries(CFG, no_context),
+ alloc(CFG, Liveness, SpillIndex, SpillLimit, Options).
-alloc(CFG, SpillIndex, SpillLimit, Options) ->
- {Coloring, _NewSpillIndex, Liveness} =
+alloc(CFG, Liveness, SpillIndex, SpillLimit, Options) ->
+ {Coloring, _NewSpillIndex} =
regalloc(
- CFG,
+ CFG, Liveness,
hipe_arm_registers:allocatable_gpr()--
[hipe_arm_registers:temp3(),
hipe_arm_registers:temp2(),
hipe_arm_registers:temp1()],
[hipe_arm_cfg:start_label(CFG)],
SpillIndex, SpillLimit, Options,
- hipe_arm_specific),
+ hipe_arm_specific, no_context),
{NewCFG, _DidSpill} =
hipe_arm_ra_postconditions:check_and_rewrite(
CFG, Coloring, 'linearscan'),
- TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_arm_specific),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_arm_specific, no_context),
{SpillMap, _NewSpillIndex2} =
hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
- hipe_arm_specific, TempMap),
+ hipe_arm_specific, no_context, TempMap),
Coloring2 =
hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), SpillMap),
- {NewCFG, Coloring2}.
+ {NewCFG, Liveness, Coloring2}.
-regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
- hipe_ls_regalloc:regalloc(
- CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target).
+regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options,
+ TgtMod, TgtCtx) ->
+ hipe_ls_regalloc:regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex,
+ DontSpill, Options, TgtMod, TgtCtx).
diff --git a/lib/hipe/arm/hipe_arm_ra_naive.erl b/lib/hipe/arm/hipe_arm_ra_naive.erl
index 0ea4b04092..395beff292 100644
--- a/lib/hipe/arm/hipe_arm_ra_naive.erl
+++ b/lib/hipe/arm/hipe_arm_ra_naive.erl
@@ -20,11 +20,11 @@
%%
-module(hipe_arm_ra_naive).
--export([ra/3]).
+-export([ra/4]).
-include("hipe_arm.hrl").
-ra(CFG, _Coloring_fp, _Options) -> % -> {CFG, Coloring}
+ra(CFG, Liveness, _Coloring_fp, _Options) -> % -> {CFG, Liveness, Coloring}
{NewCFG,_DidSpill} =
hipe_arm_ra_postconditions:check_and_rewrite2(CFG, [], 'naive'),
- {NewCFG, []}.
+ {NewCFG, Liveness, []}.
diff --git a/lib/hipe/arm/hipe_arm_ra_postconditions.erl b/lib/hipe/arm/hipe_arm_ra_postconditions.erl
index 04365f29b0..412524e2e6 100644
--- a/lib/hipe/arm/hipe_arm_ra_postconditions.erl
+++ b/lib/hipe/arm/hipe_arm_ra_postconditions.erl
@@ -26,7 +26,7 @@
-include("hipe_arm.hrl").
check_and_rewrite(CFG, Coloring, Allocator) ->
- TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_arm_specific),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_arm_specific, no_context),
check_and_rewrite2(CFG, TempMap, Allocator).
check_and_rewrite2(CFG, TempMap, Allocator) ->
diff --git a/lib/hipe/arm/hipe_arm_registers.erl b/lib/hipe/arm/hipe_arm_registers.erl
index dcf039676b..3ecf2f2fdb 100644
--- a/lib/hipe/arm/hipe_arm_registers.erl
+++ b/lib/hipe/arm/hipe_arm_registers.erl
@@ -180,6 +180,8 @@ is_arg(R) ->
_ -> false
end.
+%% Note: the fact that allocatable_gpr() is a subset of call_clobbered() is
+%% hard-coded in hipe_arm_defuse:insn_defs_all_gpr/1
call_clobbered() -> % does the RA strip the type or not?
[{?R0,tagged},{?R0,untagged},
{?R1,tagged},{?R1,untagged},
diff --git a/lib/hipe/arm/hipe_arm_subst.erl b/lib/hipe/arm/hipe_arm_subst.erl
new file mode 100644
index 0000000000..4d077f3cd6
--- /dev/null
+++ b/lib/hipe/arm/hipe_arm_subst.erl
@@ -0,0 +1,112 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 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
+%%
+%% 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.
+%%
+%% %CopyrightEnd%
+%%
+
+-module(hipe_arm_subst).
+-export([insn_temps/2]).
+-include("hipe_arm.hrl").
+
+%% These should be moved to hipe_arm and exported
+-type temp() :: #arm_temp{}.
+-type shiftop() :: lsl | lsr | asr | ror.
+-type imm4() :: 0..15.
+-type imm5() :: 0..31.
+-type imm8() :: 0..255.
+-type am1() :: {imm8(),imm4()}
+ | temp()
+ | {temp(), rrx}
+ | {temp(), shiftop(), imm5()}
+ | {temp(), shiftop(), temp()}.
+-type am2() :: #am2{}.
+-type am3() :: #am3{}.
+-type arg() :: temp() | integer().
+-type funv() :: #arm_mfa{} | #arm_prim{} | temp().
+-type insn() :: tuple(). % for now
+
+-type subst_fun() :: fun((temp()) -> temp()).
+
+%% @doc Maps over the temporaries in an instruction
+-spec insn_temps(subst_fun(), insn()) -> insn().
+insn_temps(T, I) ->
+ AM1 = fun(O) -> am1_temps(T, O) end,
+ AM2 = fun(O) -> am2_temps(T, O) end,
+ AM3 = fun(O) -> am3_temps(T, O) end,
+ Arg = fun(O) -> arg_temps(T, O) end,
+ case I of
+ #alu {dst=D,src=L,am1=R} -> I#alu{dst=T(D),src=T(L),am1=AM1(R)};
+ #cmp {src=L,am1=R} -> I#cmp {src=T(L),am1=AM1(R)};
+ #load {dst=D,am2=S} -> I#load {dst=T(D),am2=AM2(S)};
+ #ldrsb {dst=D,am3=S} -> I#ldrsb {dst=T(D),am3=AM3(S)};
+ #move {dst=D,am1=S} -> I#move {dst=T(D),am1=AM1(S)};
+ #pseudo_move{dst=D,src=S} -> I#pseudo_move {dst=T(D),src=T(S)};
+ #store {src=S,am2=D} -> I#store {src=T(S),am2=AM2(D)};
+ #b_label{} -> I;
+ #comment{} -> I;
+ #label{} -> I;
+ #pseudo_bc{} -> I;
+ #pseudo_blr{} -> I;
+ #pseudo_call{funv=F} -> I#pseudo_call{funv=funv_temps(T, F)};
+ #pseudo_call_prepare{} -> I;
+ #pseudo_li{dst=D} -> I#pseudo_li{dst=T(D)};
+ #pseudo_switch{jtab=J=#arm_temp{},index=Ix=#arm_temp{}} ->
+ I#pseudo_switch{jtab=T(J),index=T(Ix)};
+ #pseudo_tailcall{funv=F,stkargs=Stk} ->
+ I#pseudo_tailcall{funv=funv_temps(T,F),stkargs=lists:map(Arg,Stk)};
+ #pseudo_tailcall_prepare{} -> I;
+ #smull{dstlo=DL,dsthi=DH,src1=L,src2=R} ->
+ I#smull{dstlo=T(DL),dsthi=T(DH),src1=T(L),src2=T(R)}
+ end.
+
+-spec am1_temps(subst_fun(), am1()) -> am1().
+am1_temps(_SubstTemp, T={C,R}) when is_integer(C), is_integer(R) -> T;
+am1_temps(SubstTemp, T=#arm_temp{}) -> SubstTemp(T);
+am1_temps(SubstTemp, {T=#arm_temp{},rrx}) -> {SubstTemp(T),rrx};
+am1_temps(SubstTemp, {A=#arm_temp{},Op,B=#arm_temp{}}) when is_atom(Op) ->
+ {SubstTemp(A),Op,SubstTemp(B)};
+am1_temps(SubstTemp, {T=#arm_temp{},Op,I}) when is_atom(Op), is_integer(I) ->
+ {SubstTemp(T),Op,I}.
+
+-spec am2_temps(subst_fun(), am2()) -> am2().
+am2_temps(SubstTemp, T=#am2{src=A=#arm_temp{},offset=O0}) ->
+ O = case O0 of
+ _ when is_integer(O0) -> O0;
+ #arm_temp{} -> SubstTemp(O0);
+ {B=#arm_temp{},rrx} -> {SubstTemp(B),rrx};
+ {B=#arm_temp{},Op,I} when is_atom(Op), is_integer(I) ->
+ {SubstTemp(B),Op,I}
+ end,
+ T#am2{src=SubstTemp(A),offset=O}.
+
+-spec am3_temps(subst_fun(), am3()) -> am3().
+am3_temps(SubstTemp, T=#am3{src=A=#arm_temp{},offset=O0}) ->
+ O = case O0 of
+ _ when is_integer(O0) -> O0;
+ #arm_temp{} -> SubstTemp(O0)
+ end,
+ T#am3{src=SubstTemp(A),offset=O}.
+
+-spec funv_temps(subst_fun(), funv()) -> funv().
+funv_temps(_SubstTemp, M=#arm_mfa{}) -> M;
+funv_temps(_SubstTemp, P=#arm_prim{}) -> P;
+funv_temps(SubstTemp, T=#arm_temp{}) -> SubstTemp(T).
+
+-spec arg_temps(subst_fun(), arg()) -> arg().
+arg_temps(_SubstTemp, Imm) when is_integer(Imm) -> Imm;
+arg_temps(SubstTemp, T=#arm_temp{}) -> SubstTemp(T).
diff --git a/lib/hipe/main/hipe.app.src b/lib/hipe/main/hipe.app.src
index 6c3a2741b3..96bcf7d7e8 100644
--- a/lib/hipe/main/hipe.app.src
+++ b/lib/hipe/main/hipe.app.src
@@ -55,6 +55,7 @@
hipe_amd64_specific_x87,
hipe_amd64_spill_restore,
hipe_amd64_sse2,
+ hipe_amd64_subst,
hipe_amd64_x87,
hipe_arm,
hipe_arm_assemble,
@@ -73,6 +74,7 @@
hipe_arm_ra_postconditions,
hipe_arm_registers,
hipe_arm_specific,
+ hipe_arm_subst,
hipe_bb,
hipe_beam_to_icode,
hipe_coalescing_regalloc,
@@ -142,9 +144,11 @@
hipe_ppc_registers,
hipe_ppc_specific,
hipe_ppc_specific_fp,
+ hipe_ppc_subst,
hipe_profile,
hipe_reg_worklists,
hipe_regalloc_loop,
+ hipe_regalloc_prepass,
hipe_rtl,
hipe_rtl_arch,
hipe_rtl_arith_32,
@@ -194,6 +198,7 @@
hipe_sparc_registers,
hipe_sparc_specific,
hipe_sparc_specific_fp,
+ hipe_sparc_subst,
hipe_spillcost,
hipe_spillmin,
hipe_spillmin_color,
@@ -221,6 +226,7 @@
hipe_x86_specific,
hipe_x86_specific_x87,
hipe_x86_spill_restore,
+ hipe_x86_subst,
hipe_x86_x87]},
{registered,[]},
{applications, [kernel,stdlib]},
diff --git a/lib/hipe/main/hipe.erl b/lib/hipe/main/hipe.erl
index 4e6de2e0dc..bee5da2195 100644
--- a/lib/hipe/main/hipe.erl
+++ b/lib/hipe/main/hipe.erl
@@ -1354,6 +1354,8 @@ opt_keys() ->
pp_rtl_lcm,
pp_rtl_ssapre,
pp_rtl_linear,
+ ra_partitioned,
+ ra_prespill,
regalloc,
remove_comments,
rtl_ssa,
@@ -1388,7 +1390,7 @@ o0_opts(_TargetArch) ->
[concurrent_comp, {regalloc,linear_scan}].
o1_opts(TargetArch) ->
- Common = [inline_fp, pmatch, peephole,
+ Common = [inline_fp, pmatch, peephole, ra_prespill, ra_partitioned,
icode_ssa_const_prop, icode_ssa_copy_prop, icode_inline_bifs,
rtl_ssa, rtl_ssa_const_prop, rtl_ssapre,
spillmin_color, use_indexing, remove_comments,
@@ -1458,6 +1460,8 @@ opt_negations() ->
{no_pp_native, pp_native},
{no_pp_rtl_lcm, pp_rtl_lcm},
{no_pp_rtl_ssapre, pp_rtl_ssapre},
+ {no_ra_partitioned, ra_partitioned},
+ {no_ra_prespill, ra_prespill},
{no_remove_comments, remove_comments},
{no_rtl_ssa, rtl_ssa},
{no_rtl_ssa_const_prop, rtl_ssa_const_prop},
diff --git a/lib/hipe/opt/hipe_spillmin.erl b/lib/hipe/opt/hipe_spillmin.erl
index 6bb6980ad5..a2efd35d26 100644
--- a/lib/hipe/opt/hipe_spillmin.erl
+++ b/lib/hipe/opt/hipe_spillmin.erl
@@ -29,7 +29,8 @@
%% ==========================================================================
%% Exported functions (short description):
%%
-%% stackalloc(CFG, StackSlots, SpillIndex, Options, Target, TempMap) ->
+%% stackalloc(CFG, StackSlots, SpillIndex, Options, TgtMod, TgtCtx,
+%% TempMap) ->
%% {Coloring, NumberOfSpills}
%% Takes a CFG and the TempMap from register allocation and returns
%% a coloring of stack slots.
@@ -49,7 +50,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-module(hipe_spillmin).
--export([stackalloc/6, stackalloc/7, mapmerge/2]).
+-export([stackalloc/7, stackalloc/8, mapmerge/2]).
%%-define(DEBUG, 1).
-define(HIPE_INSTRUMENT_COMPILER, true).
@@ -59,6 +60,8 @@
-include("../main/hipe.hrl").
-include("../flow/cfg.hrl").
+-type target_context() :: any().
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% stackalloc(CFG, StackSlots, SpillIndex, Options, Target, TempMap)
@@ -68,26 +71,29 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-spec stackalloc(#cfg{}, [_], non_neg_integer(),
- comp_options(), module(), hipe_temp_map()) ->
+ comp_options(), module(), target_context(), hipe_temp_map()) ->
{hipe_spill_map(), non_neg_integer()}.
-stackalloc(CFG, StackSlots, SpillIndex, Options, Target, TempMap) ->
- Liveness = Target:analyze(CFG),
- stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, Target, TempMap).
+stackalloc(CFG, StackSlots, SpillIndex, Options, TgtMod, TgtCtx, TempMap) ->
+ Liveness = TgtMod:analyze(CFG,TgtCtx),
+ stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, TgtMod, TgtCtx, TempMap).
-spec stackalloc(#cfg{}, _, [_], non_neg_integer(),
- comp_options(), module(), hipe_temp_map()) ->
+ comp_options(), module(), target_context(), hipe_temp_map()) ->
{hipe_spill_map(), non_neg_integer()}.
-stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, Target, TempMap) ->
+stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, TgtMod, TgtCtx,
+ TempMap) ->
case proplists:get_bool(spillmin_color, Options) of
false ->
- ?option_time(hipe_spillmin_scan:stackalloc(CFG, Liveness, StackSlots, SpillIndex,
- Options, Target, TempMap),
+ ?option_time(hipe_spillmin_scan:stackalloc(
+ CFG, Liveness, StackSlots, SpillIndex, Options, TgtMod,
+ TgtCtx, TempMap),
"Spill minimize, linear scan", Options);
true ->
- ?option_time(hipe_spillmin_color:stackalloc(CFG, Liveness, StackSlots, SpillIndex,
- Options, Target, TempMap),
+ ?option_time(hipe_spillmin_color:stackalloc(
+ CFG, Liveness, StackSlots, SpillIndex, Options, TgtMod,
+ TgtCtx, TempMap),
"Spill minimize, graph coloring", Options)
end.
diff --git a/lib/hipe/opt/hipe_spillmin_color.erl b/lib/hipe/opt/hipe_spillmin_color.erl
index 9c62fdf11a..a0d6b03503 100644
--- a/lib/hipe/opt/hipe_spillmin_color.erl
+++ b/lib/hipe/opt/hipe_spillmin_color.erl
@@ -41,7 +41,7 @@
-module(hipe_spillmin_color).
--export([stackalloc/7]).
+-export([stackalloc/8]).
%%-ifndef(DO_ASSERT).
%%-define(DO_ASSERT, true).
@@ -66,11 +66,15 @@
%% where Location is {spill,M}.
%% {spill,M} denotes the Mth spilled node
+-type target_context() :: any().
+
-spec stackalloc(#cfg{}, _, [_], non_neg_integer(),
- comp_options(), module(), hipe_temp_map()) ->
+ comp_options(), module(), target_context(), hipe_temp_map()) ->
{hipe_spill_map(), non_neg_integer()}.
-stackalloc(CFG, Live, _StackSlots, SpillIndex, _Options, Target, TempMap) ->
+stackalloc(CFG, Live, _StackSlots, SpillIndex, _Options, TargetMod,
+ TargetContext, TempMap) ->
+ Target = {TargetMod, TargetContext},
?report2("building IG~n", []),
{IG, NumNodes} = build_ig(CFG, Live, Target, TempMap),
{Cols, MaxColors} =
@@ -189,7 +193,7 @@ build_ig0(CFG, Live, Target, TempMap) ->
TempMapping = map_spilled_temporaries(TempMap),
TempMappingTable = setup_ets(TempMapping),
NumSpilled = length(TempMapping),
- IG = build_ig_bbs(Target:labels(CFG), CFG, Live, empty_ig(NumSpilled),
+ IG = build_ig_bbs(labels(CFG, Target), CFG, Live, empty_ig(NumSpilled),
Target, TempMap, TempMappingTable),
ets:delete(TempMappingTable),
{normalize_ig(IG), NumSpilled}.
@@ -539,18 +543,21 @@ is_visited(X, Vis) ->
%% *** INTERFACES TO OTHER MODULES ***
%%
-liveout(CFG, L, Target) ->
- ordsets:from_list(reg_names(Target:liveout(CFG, L), Target)).
+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, Target) ->
- hipe_bb:code(Target:bb(CFG, L)).
+bb(CFG, L, {TgtMod,TgtCtx}) ->
+ hipe_bb:code(TgtMod:bb(CFG, L, TgtCtx)).
-def_use(X, Target, TempMap) ->
- Defines = [Y || Y <- reg_names(Target:defines(X), Target),
+def_use(X, Target={TgtMod,TgtCtx}, TempMap) ->
+ Defines = [Y || Y <- reg_names(TgtMod:defines(X,TgtCtx), Target),
hipe_temp_map:is_spilled(Y, TempMap)],
- Uses = [Z || Z <- reg_names(Target:uses(X), Target),
+ Uses = [Z || Z <- reg_names(TgtMod:uses(X,TgtCtx), Target),
hipe_temp_map:is_spilled(Z, TempMap)],
{Defines, Uses}.
-reg_names(Regs, Target) ->
- [Target:reg_nr(X) || X <- Regs].
+reg_names(Regs, {TgtMod,TgtCtx}) ->
+ [TgtMod:reg_nr(X,TgtCtx) || X <- Regs].
diff --git a/lib/hipe/opt/hipe_spillmin_scan.erl b/lib/hipe/opt/hipe_spillmin_scan.erl
index 53cbc0014b..097a787152 100644
--- a/lib/hipe/opt/hipe_spillmin_scan.erl
+++ b/lib/hipe/opt/hipe_spillmin_scan.erl
@@ -60,7 +60,7 @@
-module(hipe_spillmin_scan).
--export([stackalloc/7]).
+-export([stackalloc/8]).
%%-define(DEBUG, 1).
-define(HIPE_INSTRUMENT_COMPILER, true).
@@ -70,6 +70,8 @@
-include("../main/hipe.hrl").
-include("../flow/cfg.hrl").
+-type target_context() :: any().
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% stackalloc(CFG, StackSlots, SpillIndex, Options, Target, TempMap)
@@ -86,10 +88,12 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-spec stackalloc(#cfg{}, _, [_], non_neg_integer(),
- comp_options(), module(), hipe_temp_map()) ->
+ comp_options(), module(), target_context(), hipe_temp_map()) ->
{hipe_spill_map(), non_neg_integer()}.
-stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, Target, TempMap) ->
+stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, TargetMod,
+ TargetContext, TempMap) ->
+ Target = {TargetMod, TargetContext},
?debug_msg("LinearScan: ~w\n", [erlang:statistics(runtime)]),
USIntervals = calculate_intervals(CFG, Liveness, Options,
Target, TempMap),
@@ -121,8 +125,8 @@ stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, Target, TempMap) ->
%% all other.
%%- - - - - - - - - - - - - - - - - - - - - - - -
calculate_intervals(CFG, Liveness, _Options, Target, TempMap) ->
- Interval = empty_interval(Target:number_of_temporaries(CFG)),
- Worklist = Target:reverse_postorder(CFG),
+ Interval = empty_interval(number_of_temporaries(CFG, Target)),
+ Worklist = reverse_postorder(CFG, Target),
intervals(Worklist, Interval, 1, CFG, Liveness, Target, TempMap).
%%- - - - - - - - - - - - - - - - - - - - - - - -
@@ -535,20 +539,26 @@ extend_interval(Pos, {Beginning, End})
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-bb(CFG, L, Target) ->
- Target:bb(CFG, L).
+bb(CFG, L, {TgtMod,TgtCtx}) ->
+ TgtMod:bb(CFG, L, TgtCtx).
+
+livein(Liveness, L, Target={TgtMod,TgtCtx}) ->
+ regnames(TgtMod:livein(Liveness, L, TgtCtx), Target).
+
+liveout(Liveness, L, Target={TgtMod,TgtCtx}) ->
+ regnames(TgtMod:liveout(Liveness, L, TgtCtx), Target).
-livein(Liveness, L, Target) ->
- regnames(Target:livein(Liveness, L), Target).
+number_of_temporaries(CFG, {TgtMod,TgtCtx}) ->
+ TgtMod:number_of_temporaries(CFG, TgtCtx).
-liveout(Liveness, L, Target) ->
- regnames(Target:liveout(Liveness, L), Target).
+uses(I, Target={TgtMod,TgtCtx}) ->
+ regnames(TgtMod:uses(I,TgtCtx), Target).
-uses(I, Target) ->
- regnames(Target:uses(I), Target).
+defines(I, Target={TgtMod,TgtCtx}) ->
+ regnames(TgtMod:defines(I,TgtCtx), Target).
-defines(I, Target) ->
- regnames(Target:defines(I), Target).
+regnames(Regs, {TgtMod,TgtCtx}) ->
+ [TgtMod:reg_nr(X,TgtCtx) || X <- Regs].
-regnames(Regs, Target) ->
- [Target:reg_nr(X) || X <- Regs].
+reverse_postorder(CFG, {TgtMod,TgtCtx}) ->
+ TgtMod:reverse_postorder(CFG, TgtCtx).
diff --git a/lib/hipe/ppc/Makefile b/lib/hipe/ppc/Makefile
index 1901dfa671..1ca1d51846 100644
--- a/lib/hipe/ppc/Makefile
+++ b/lib/hipe/ppc/Makefile
@@ -63,6 +63,7 @@ MODULES=hipe_ppc \
hipe_ppc_ra_postconditions \
hipe_ppc_ra_postconditions_fp \
hipe_ppc_registers \
+ hipe_ppc_subst \
hipe_rtl_to_ppc
HRL_FILES=hipe_ppc.hrl
diff --git a/lib/hipe/ppc/hipe_ppc_defuse.erl b/lib/hipe/ppc/hipe_ppc_defuse.erl
index 77b84dc574..305e88488d 100644
--- a/lib/hipe/ppc/hipe_ppc_defuse.erl
+++ b/lib/hipe/ppc/hipe_ppc_defuse.erl
@@ -22,6 +22,7 @@
-module(hipe_ppc_defuse).
-export([insn_def_all/1, insn_use_all/1]).
-export([insn_def_gpr/1, insn_use_gpr/1]).
+-export([insn_defs_all_gpr/1, insn_defs_all_fpr/1]).
-export([insn_def_fpr/1, insn_use_fpr/1]).
-include("hipe_ppc.hrl").
@@ -52,6 +53,9 @@ insn_def_gpr(I) ->
_ -> []
end.
+insn_defs_all_gpr(#pseudo_call{}) -> true;
+insn_defs_all_gpr(_) -> false.
+
call_clobbered_gpr() ->
[hipe_ppc:mk_temp(R, T)
|| {R,T} <- hipe_ppc_registers:call_clobbered() ++ all_fp_pseudos()].
@@ -116,6 +120,9 @@ insn_def_fpr(I) ->
_ -> []
end.
+insn_defs_all_fpr(#pseudo_call{}) -> true;
+insn_defs_all_fpr(_) -> false.
+
call_clobbered_fpr() ->
[hipe_ppc:mk_temp(R, 'double') || R <- hipe_ppc_registers:allocatable_fpr()].
diff --git a/lib/hipe/ppc/hipe_ppc_ra.erl b/lib/hipe/ppc/hipe_ppc_ra.erl
index bfb4d35139..f8614db4ef 100644
--- a/lib/hipe/ppc/hipe_ppc_ra.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra.erl
@@ -24,28 +24,31 @@
ra(CFG0, Options) ->
%% hipe_ppc_pp:pp(hipe_ppc_cfg:linearise(CFG0)),
- {CFG1, Coloring_fp, SpillIndex}
+ {CFG1, _FPLiveness1, Coloring_fp, SpillIndex}
= case proplists:get_bool(inline_fp, Options) of
true ->
- hipe_regalloc_loop:ra_fp(CFG0, Options,
+ FPLiveness0 = hipe_ppc_specific_fp:analyze(CFG0, no_context),
+ hipe_regalloc_loop:ra_fp(CFG0, FPLiveness0, Options,
hipe_coalescing_regalloc,
- hipe_ppc_specific_fp);
+ hipe_ppc_specific_fp, no_context);
false ->
- {CFG0,[],0}
+ {CFG0,undefined,[],0}
end,
%% hipe_ppc_pp:pp(hipe_ppc_cfg:linearise(CFG1)),
- {CFG2, Coloring}
+ GPLiveness1 = hipe_ppc_specific:analyze(CFG1, no_context),
+ {CFG2, _GPLiveness2, Coloring}
= case proplists:get_value(regalloc, Options, coalescing) of
coalescing ->
- ra(CFG1, SpillIndex, Options, hipe_coalescing_regalloc);
+ ra(CFG1, GPLiveness1, SpillIndex, Options, hipe_coalescing_regalloc);
optimistic ->
- ra(CFG1, SpillIndex, Options, hipe_optimistic_regalloc);
+ ra(CFG1, GPLiveness1, SpillIndex, Options, hipe_optimistic_regalloc);
graph_color ->
- ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc);
+ ra(CFG1, GPLiveness1, SpillIndex, Options,
+ hipe_graph_coloring_regalloc);
linear_scan ->
- hipe_ppc_ra_ls:ra(CFG1, SpillIndex, Options);
+ hipe_ppc_ra_ls:ra(CFG1, GPLiveness1, SpillIndex, Options);
naive ->
- hipe_ppc_ra_naive:ra(CFG1, Coloring_fp, Options);
+ hipe_ppc_ra_naive:ra(CFG1, GPLiveness1, Coloring_fp, Options);
_ ->
exit({unknown_regalloc_compiler_option,
proplists:get_value(regalloc,Options)})
@@ -53,5 +56,6 @@ ra(CFG0, Options) ->
%% hipe_ppc_pp:pp(hipe_ppc_cfg:linearise(CFG2)),
hipe_ppc_ra_finalise:finalise(CFG2, Coloring, Coloring_fp).
-ra(CFG, SpillIndex, Options, RegAllocMod) ->
- hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, hipe_ppc_specific).
+ra(CFG, Liveness, SpillIndex, Options, RegAllocMod) ->
+ hipe_regalloc_loop:ra(CFG, Liveness, SpillIndex, Options, RegAllocMod,
+ hipe_ppc_specific, no_context).
diff --git a/lib/hipe/ppc/hipe_ppc_ra_ls.erl b/lib/hipe/ppc/hipe_ppc_ra_ls.erl
index 52562fc321..5f331542e8 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_ls.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_ls.erl
@@ -21,34 +21,35 @@
%%% Linear Scan register allocator for PowerPC
-module(hipe_ppc_ra_ls).
--export([ra/3]).
+-export([ra/4]).
-ra(CFG, SpillIndex, Options) ->
- SpillLimit = hipe_ppc_specific:number_of_temporaries(CFG),
- alloc(CFG, SpillIndex, SpillLimit, Options).
+ra(CFG, Liveness, SpillIndex, Options) ->
+ SpillLimit = hipe_ppc_specific:number_of_temporaries(CFG, no_context),
+ alloc(CFG, Liveness, SpillIndex, SpillLimit, Options).
-alloc(CFG, SpillIndex, SpillLimit, Options) ->
- {Coloring, _NewSpillIndex, Liveness} =
+alloc(CFG, Liveness, SpillIndex, SpillLimit, Options) ->
+ {Coloring, _NewSpillIndex} =
regalloc(
- CFG,
+ CFG, Liveness,
hipe_ppc_registers:allocatable_gpr()--
[hipe_ppc_registers:temp3(),
hipe_ppc_registers:temp2(),
hipe_ppc_registers:temp1()],
[hipe_ppc_cfg:start_label(CFG)],
SpillIndex, SpillLimit, Options,
- hipe_ppc_specific),
+ hipe_ppc_specific, no_context),
{NewCFG, _DidSpill} =
hipe_ppc_ra_postconditions:check_and_rewrite(
CFG, Coloring, 'linearscan'),
- TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific, no_context),
{TempMap2,_NewSpillIndex2} =
hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
- hipe_ppc_specific, TempMap),
+ hipe_ppc_specific, no_context, TempMap),
Coloring2 =
hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
- {NewCFG, Coloring2}.
+ {NewCFG, Liveness, Coloring2}.
-regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
- hipe_ls_regalloc:regalloc(
- CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target).
+regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options,
+ TgtMod, TgtCtx) ->
+ hipe_ls_regalloc:regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex,
+ DontSpill, Options, TgtMod, TgtCtx).
diff --git a/lib/hipe/ppc/hipe_ppc_ra_naive.erl b/lib/hipe/ppc/hipe_ppc_ra_naive.erl
index ba269ae981..322fb1a171 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_naive.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_naive.erl
@@ -20,11 +20,11 @@
%%
-module(hipe_ppc_ra_naive).
--export([ra/3]).
+-export([ra/4]).
-include("hipe_ppc.hrl").
-ra(CFG, _Coloring_fp, _Options) -> % -> {CFG, Coloring}
+ra(CFG, Liveness, _Coloring_fp, _Options) -> % -> {CFG, Liveness, Coloring}
{NewCFG,_DidSpill} =
hipe_ppc_ra_postconditions:check_and_rewrite2(CFG, [], 'naive'),
- {NewCFG, []}.
+ {NewCFG, Liveness, []}.
diff --git a/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl b/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl
index 412aeeeba6..f084a30e63 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl
@@ -26,7 +26,7 @@
-include("hipe_ppc.hrl").
check_and_rewrite(CFG, Coloring, Allocator) ->
- TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific, no_context),
check_and_rewrite2(CFG, TempMap, Allocator).
check_and_rewrite2(CFG, TempMap, Allocator) ->
diff --git a/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl b/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl
index 553fac882b..81064079aa 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl
@@ -24,7 +24,7 @@
-include("hipe_ppc.hrl").
check_and_rewrite(CFG, Coloring) ->
- TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific_fp),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific_fp, no_context),
do_bbs(hipe_ppc_cfg:labels(CFG), TempMap, CFG, false).
do_bbs([], _TempMap, CFG, DidSpill) -> {CFG, DidSpill};
diff --git a/lib/hipe/ppc/hipe_ppc_registers.erl b/lib/hipe/ppc/hipe_ppc_registers.erl
index f4781d5ed7..8f6d9779fc 100644
--- a/lib/hipe/ppc/hipe_ppc_registers.erl
+++ b/lib/hipe/ppc/hipe_ppc_registers.erl
@@ -201,6 +201,8 @@ is_arg(R) ->
_ -> false
end.
+%% Note: the fact that allocatable_gpr() is a subset of call_clobbered() is
+%% hard-coded in hipe_ppc_defuse:insn_defs_all_gpr/1
call_clobbered() -> % does the RA strip the type or not?
[{?R0,tagged},{?R0,untagged},
%% R1 is reserved for C
diff --git a/lib/hipe/ppc/hipe_ppc_subst.erl b/lib/hipe/ppc/hipe_ppc_subst.erl
new file mode 100644
index 0000000000..5e43fd6471
--- /dev/null
+++ b/lib/hipe/ppc/hipe_ppc_subst.erl
@@ -0,0 +1,82 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 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
+%%
+%% 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.
+%%
+%% %CopyrightEnd%
+%%
+
+-module(hipe_ppc_subst).
+-export([insn_temps/2]).
+-include("hipe_ppc.hrl").
+
+%% These should be moved to hipe_ppc and exported
+-type temp() :: #ppc_temp{}.
+-type oper() :: temp() | #ppc_simm16{} | #ppc_uimm16{}.
+-type arg() :: temp() | integer().
+-type insn() :: tuple(). % for now
+
+-type subst_fun() :: fun((temp()) -> temp()).
+
+%% @doc Maps over the temporaries in an instruction
+-spec insn_temps(subst_fun(), insn()) -> insn().
+insn_temps(T, I) ->
+ A = fun(O) -> arg_temps(T, O) end,
+ O = fun(O) -> oper_temps(T, O) end,
+ case I of
+ #alu{dst=D,src1=L,src2=R} -> I#alu{dst=T(D),src1=T(L),src2=O(R)};
+ #b_label{} -> I;
+ %% #bc{} -> I;
+ #bctr{} -> I;
+ #blr{} -> I;
+ #cmp{src1=L,src2=R} -> I#cmp{src1=T(L),src2=O(R)};
+ #comment{} -> I;
+ #label{} -> I;
+ #load{dst=D,base=B} -> I#load{dst=T(D),base=T(B)};
+ #loadx{dst=D,base1=L,base2=R} -> I#loadx{dst=T(D),base1=T(L),base2=T(R)};
+ #mfspr{dst=D} -> I#mfspr{dst=T(D)};
+ #mtcr{src=S} -> I#mtcr{src=T(S)};
+ #mtspr{src=S} -> I#mtspr{src=T(S)};
+ #pseudo_bc{} -> I;
+ #pseudo_call{func=F} when not is_record(F, ppc_temp) -> I;
+ #pseudo_call_prepare{} -> I;
+ #pseudo_li{dst=D} -> I#pseudo_li{dst=T(D)};
+ #pseudo_move{dst=D,src=S} -> I#pseudo_move{dst=T(D),src=T(S)};
+ #pseudo_tailcall{func=F,stkargs=Stk} when not is_record(F, ppc_temp) ->
+ I#pseudo_tailcall{stkargs=lists:map(A,Stk)};
+ #pseudo_tailcall_prepare{} -> I;
+ #store{src=S,base=B} -> I#store{src=T(S),base=T(B)};
+ #storex{src=S,base1=L,base2=R} ->
+ I#storex{src=T(S),base1=T(L),base2=T(R)};
+ #unary{dst=D,src=S} -> I#unary{dst=T(D),src=T(S)};
+ #lfd{dst=D,base=B} -> I#lfd{dst=T(D),base=T(B)};
+ #lfdx{dst=D,base1=L,base2=R} -> I#lfdx{dst=T(D),base1=T(L),base2=T(R)};
+ #stfd{src=S,base=B} -> I#stfd{src=T(S),base=T(B)};
+ #stfdx{src=S,base1=L,base2=R} -> I#stfdx{src=T(S),base1=T(L),base2=T(R)};
+ #fp_binary{dst=D,src1=L,src2=R} ->
+ I#fp_binary{dst=T(D),src1=T(L),src2=T(R)};
+ #fp_unary{dst=D,src=S} -> I#fp_unary{dst=T(D),src=T(S)};
+ #pseudo_fmove{dst=D,src=S} -> I#pseudo_fmove{dst=T(D),src=T(S)}
+ end.
+
+-spec oper_temps(subst_fun(), oper()) -> oper().
+oper_temps(SubstTemp, T=#ppc_temp{}) -> SubstTemp(T);
+oper_temps(_SubstTemp, I=#ppc_simm16{}) -> I;
+oper_temps(_SubstTemp, I=#ppc_uimm16{}) -> I.
+
+-spec arg_temps(subst_fun(), arg()) -> arg().
+arg_temps(_SubstTemp, Imm) when is_integer(Imm) -> Imm;
+arg_temps(SubstTemp, T=#ppc_temp{}) -> SubstTemp(T).
diff --git a/lib/hipe/regalloc/Makefile b/lib/hipe/regalloc/Makefile
index ceb535f1c7..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 \
diff --git a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
index 2e5804337d..890df1b81a 100644
--- a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
+++ b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
@@ -21,41 +21,47 @@
-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,
+-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,
- temp0/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]).
+ 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,
- check_and_rewrite/3]).
+-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]).
%%----------------------------------------------------------------------------
@@ -63,99 +69,99 @@
%%----------------------------------------------------------------------------
-defun_to_cfg(AlreadyACFG) ->
- AlreadyACFG.
-
-check_and_rewrite(CFG, Coloring) ->
+check_and_rewrite(CFG, Coloring, no_context) ->
hipe_amd64_ra_sse2_postconditions:check_and_rewrite(CFG, Coloring).
-check_and_rewrite(CFG, Coloring, Strategy) ->
+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) ->
+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() ->
- allocatable('normal').
+allocatable(Ctx) ->
+ allocatable('normal', Ctx).
-allocatable('normal') ->
+allocatable('normal', _) ->
hipe_amd64_registers:allocatable_sse2();
-allocatable('linearscan') ->
+allocatable('linearscan', _) ->
hipe_amd64_registers:allocatable_sse2() --
[hipe_amd64_registers:sse2_temp0()].
-temp0() ->
+temp0(_) ->
hipe_amd64_registers:sse2_temp0().
-all_precoloured() ->
- allocatable().
+all_precoloured(Ctx) ->
+ allocatable(Ctx).
-is_precoloured(Reg) ->
- lists:member(Reg,all_precoloured()).
+is_precoloured(Reg, Ctx) ->
+ lists:member(Reg,all_precoloured(Ctx)).
-physical_name(Reg) ->
+physical_name(Reg, _) ->
Reg.
%% CFG stuff
-labels(CFG) ->
+labels(CFG, _) ->
hipe_x86_cfg:labels(CFG).
-var_range(_CFG) ->
+var_range(_CFG, _) ->
hipe_gensym:var_range(x86).
--spec number_of_temporaries(#cfg{}) -> non_neg_integer().
-number_of_temporaries(_CFG) ->
+-spec number_of_temporaries(#cfg{}, no_context) -> non_neg_integer().
+number_of_temporaries(_CFG, _) ->
Highest_temporary = hipe_gensym:get_var(x86),
%% Since we can have temps from 0 to Max adjust by +1.
Highest_temporary + 1.
-bb(CFG, L) ->
+bb(CFG, L, _) ->
hipe_x86_cfg:bb(CFG, L).
+update_bb(CFG,L,BB,_) ->
+ hipe_x86_cfg:bb_add(CFG,L,BB).
+
%% 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'],
@@ -164,17 +170,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),
@@ -184,9 +192,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_arm_specific.erl b/lib/hipe/regalloc/hipe_arm_specific.erl
index e04d80f690..06ab17b0e9 100644
--- a/lib/hipe/regalloc/hipe_arm_specific.erl
+++ b/lib/hipe/regalloc/hipe_arm_specific.erl
@@ -22,114 +22,123 @@
-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(AlreadyACFG) ->
- AlreadyACFG.
+%% callbacks for hipe_regalloc_prepass
+-export([new_reg_nr/1,
+ update_reg_nr/3,
+ update_bb/4,
+ subst_temps/3]).
-check_and_rewrite(CFG, Coloring) ->
+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 +151,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 bbb2e3ecf0..00bfbaa1b6 100644
--- a/lib/hipe/regalloc/hipe_coalescing_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl
@@ -30,7 +30,7 @@
%%-----------------------------------------------------------------------
-module(hipe_coalescing_regalloc).
--export([regalloc/5]).
+-export([regalloc/7]).
%%-ifndef(DEBUG).
%%-define(DEBUG,true).
@@ -54,17 +54,18 @@
%% 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", []),
- Liveness = Target:analyze(CFG),
- IG = hipe_ig:build(CFG, Liveness, 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),
@@ -73,7 +74,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]),
@@ -82,10 +84,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", []),
@@ -98,7 +100,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
{Coloring, SpillIndex2} =
build_namelist(Node_sets2, SpillIndex, Alias0, Color1),
?debug_msg("Coloring ~p\n", [Coloring]),
- {Coloring, SpillIndex2, Liveness}.
+ {Coloring, SpillIndex2}.
%%----------------------------------------------------------------------
%% Function: do_coloring
@@ -381,7 +383,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.
@@ -404,7 +406,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).
@@ -569,7 +571,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,
@@ -579,7 +581,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
@@ -587,7 +589,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);
@@ -629,7 +631,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 ->
@@ -713,7 +715,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);
_ ->
@@ -730,7 +732,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 ->
@@ -769,7 +771,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)).
%%----------------------------------------------------------------------
@@ -1030,3 +1032,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 1a3ea90c05..e91734d8be 100644
--- a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl
@@ -51,7 +51,7 @@
%%
-module(hipe_graph_coloring_regalloc).
--export([regalloc/5]).
+-export([regalloc/7]).
%%-ifndef(DO_ASSERT).
%%-define(DO_ASSERT, true).
@@ -77,18 +77,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, Live} = build_ig(CFG, Target),
+ {IG, Spill} = build_ig(CFG, Live, Target),
%% check_ig(IG),
?report3("graph: ~p~nphysical regs: ~p~n", [list_ig(IG), PhysRegs]),
%% 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,12 +100,12 @@ 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)),
- {Coloring, NewSpillIndex, Live}.
+ {Coloring, NewSpillIndex}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -112,21 +115,15 @@ 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),
empty_spill(NumN),
Target),
- {normalize_ig(IG), Spill, Live}.
+ {normalize_ig(IG), Spill}.
build_ig_bbs([], _CFG, _Live, IG, Spill, _Target) ->
{IG, Spill};
@@ -208,17 +205,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 +222,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 +403,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 +760,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 +809,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 47f8f6d08d..81eee2e03c 100644
--- a/lib/hipe/regalloc/hipe_ig.erl
+++ b/lib/hipe/regalloc/hipe_ig.erl
@@ -28,7 +28,7 @@
-module(hipe_ig).
--export([build/3,
+-export([build/4,
nodes_are_adjacent/3,
node_spill_cost/2,
node_adj_list/2,
@@ -38,8 +38,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 +64,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 +81,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 +347,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,19 +364,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{}, Liveness::_, atom()) -> #igraph{}.
+-spec build(#cfg{}, Liveness::_, module(), target_context()) -> #igraph{}.
-build(CFG, BBs_in_out_liveness, Target) ->
- 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))]),
@@ -394,7 +399,7 @@ build(CFG, BBs_in_out_liveness, 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.
@@ -403,13 +408,11 @@ build(CFG, BBs_in_out_liveness, 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),
@@ -432,7 +435,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
@@ -448,7 +452,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)),
@@ -500,14 +504,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]} ->
@@ -553,8 +558,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
%%----------------------------------------------------------------------
@@ -622,11 +628,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
@@ -651,11 +661,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
@@ -682,8 +696,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
@@ -691,7 +705,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),
@@ -713,8 +727,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
@@ -722,7 +736,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),
@@ -739,13 +753,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
@@ -774,3 +789,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_ls_regalloc.erl b/lib/hipe/regalloc/hipe_ls_regalloc.erl
index c318927077..0db18f5c62 100644
--- a/lib/hipe/regalloc/hipe_ls_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_ls_regalloc.erl
@@ -56,7 +56,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-module(hipe_ls_regalloc).
--export([regalloc/7, regalloc/8]).
+-export([regalloc/9]).
%%-define(DEBUG,1).
-define(HIPE_INSTRUMENT_COMPILER, true).
@@ -95,19 +95,10 @@
%% </ol>
%% @end
%%- - - - - - - - - - - - - - - - - - - - - - - -
-regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
- regalloc(CFG, undefined, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target).
-
-regalloc(CFG, Liveness0, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
+regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options,
+ TargetMod, TargetContext) ->
+ Target = {TargetMod, TargetContext},
?debug_msg("LinearScan: ~w\n", [erlang:statistics(runtime)]),
- %% Step 1: Calculate liveness (Call external implementation.)
- Liveness = case Liveness0 of
- undefined ->
- L=liveness(CFG, Target),
- ?debug_msg("liveness (done)~w\n", [erlang:statistics(runtime)]),
- L;
- _ -> Liveness0
- end,
USIntervals = calculate_intervals(CFG, Liveness,
Entrypoints, Options, Target),
?debug_msg("intervals (done) ~w\n", [erlang:statistics(runtime)]),
@@ -119,7 +110,7 @@ regalloc(CFG, Liveness0, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options,
{Coloring, NewSpillIndex}
= allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target),
?debug_msg("allocation (done) ~w\n", [erlang:statistics(runtime)]),
- {Coloring, NewSpillIndex, Liveness}.
+ {Coloring, NewSpillIndex}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
@@ -133,32 +124,33 @@ regalloc(CFG, Liveness0, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options,
%% 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)]),
@@ -298,7 +290,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),
@@ -314,7 +306,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),
@@ -760,38 +752,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_optimistic_regalloc.erl b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
index 67674be14c..031c799a2c 100644
--- a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
@@ -29,7 +29,7 @@
%%-----------------------------------------------------------------------
-module(hipe_optimistic_regalloc).
--export([regalloc/5]).
+-export([regalloc/7]).
-ifndef(DEBUG).
%%-define(DEBUG,true).
@@ -74,21 +74,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
%% 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",[]),
- Liveness = Target:analyze(CFG),
- IG_O = hipe_ig:build(CFG, Liveness, Target),
- IG = hipe_ig:build(CFG, Liveness, 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),
@@ -99,9 +100,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]),
@@ -114,11 +115,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),
@@ -176,10 +179,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),
@@ -219,15 +222,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,SpillIndex2,Liveness}.
+ {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",[]),
- Liveness = Target:analyze(CFG),
- IG = hipe_ig:build(CFG, Liveness, 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),
@@ -238,9 +241,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]),
@@ -253,7 +256,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),
@@ -295,10 +299,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),
@@ -321,7 +325,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
?debug_msg("Build mapping _N ~w\n",[Node_sets2]),
{Coloring, SpillIndex2} = build_namelist(Node_sets2,SpillIndex,Alias2,Color1),
?debug_msg("Coloring ~p\n",[Coloring]),
- {Coloring,SpillIndex2,Liveness}.
+ {Coloring,SpillIndex2}.
-endif.
%%----------------------------------------------------------------------
@@ -837,7 +841,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.
@@ -877,7 +882,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
@@ -905,7 +910,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.
@@ -1009,7 +1015,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.
@@ -1038,7 +1044,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.
@@ -1068,7 +1075,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.
@@ -1082,7 +1089,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
@@ -1092,7 +1100,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).
@@ -1286,7 +1294,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,
@@ -1296,13 +1304,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);
@@ -1353,7 +1361,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,
@@ -1364,7 +1372,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
@@ -1372,7 +1380,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);
@@ -1408,7 +1416,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)
@@ -1416,7 +1425,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 ->
@@ -1527,12 +1536,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,
@@ -1562,7 +1571,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);
_ ->
@@ -1579,7 +1588,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 ->
@@ -1612,7 +1621,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
@@ -1679,7 +1689,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
@@ -1705,16 +1716,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
@@ -1747,7 +1758,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
@@ -1755,7 +1767,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)).
%%----------------------------------------------------------------------
@@ -1768,7 +1780,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
@@ -2045,3 +2058,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 988501c96f..ed7a26de8c 100644
--- a/lib/hipe/regalloc/hipe_ppc_specific.erl
+++ b/lib/hipe/regalloc/hipe_ppc_specific.erl
@@ -22,114 +22,123 @@
-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(AlreadyACFG) ->
- AlreadyACFG.
+%% callbacks for hipe_regalloc_prepass
+-export([new_reg_nr/1,
+ update_reg_nr/3,
+ update_bb/4,
+ subst_temps/3]).
-check_and_rewrite(CFG, Coloring) ->
+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 +151,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 6f00111777..6daa624720 100644
--- a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
+++ b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
@@ -22,126 +22,152 @@
-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(AlreadyACFG) ->
- AlreadyACFG.
+%% callbacks for hipe_regalloc_prepass
+-export([new_reg_nr/1,
+ update_reg_nr/3,
+ update_bb/4,
+ subst_temps/3]).
-check_and_rewrite(CFG, 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..00679cf19c 100644
--- a/lib/hipe/regalloc/hipe_reg_worklists.erl
+++ b/lib/hipe/regalloc/hipe_reg_worklists.erl
@@ -30,8 +30,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 +90,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 fa42cdd0fb..3777f90534 100644
--- a/lib/hipe/regalloc/hipe_regalloc_loop.erl
+++ b/lib/hipe/regalloc/hipe_regalloc_loop.erl
@@ -21,37 +21,44 @@
%%% 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, CFG, 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, CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
+alloc(Coloring, CFG0, Liveness, SpillLimit, SpillIndex, Options,
+ RegAllocMod, TargetMod, TargetCtx) ->
?inc_counter(ra_iteration_counter, 1),
- {Coloring, _NewSpillIndex, Liveness} =
- 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),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod, TargetCtx),
{TempMap2, NewSpillIndex2} =
- hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
- TargetMod, TempMap),
+ 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
@@ -60,10 +67,38 @@ alloc(Defun, CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
%% false ->
%% ok
%% end,
- {NewDefun, Coloring2, NewSpillIndex2};
+ {CFG, Liveness, Coloring2, NewSpillIndex2};
_ ->
- NewCFG = TargetMod:defun_to_cfg(NewDefun),
%% Since SpillLimit is used as a low-water-mark
%% the list of temps not to spill is uninteresting.
- alloc(NewDefun, NewCFG, 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..2f1597ffd1
--- /dev/null
+++ b/lib/hipe/regalloc/hipe_regalloc_prepass.erl
@@ -0,0 +1,1006 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 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
+%%
+%% 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.
+%%
+%% %CopyrightEnd%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%@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 29d0908caf..4c575c1c83 100644
--- a/lib/hipe/regalloc/hipe_sparc_specific.erl
+++ b/lib/hipe/regalloc/hipe_sparc_specific.erl
@@ -22,114 +22,123 @@
-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(AlreadyACFG) ->
- AlreadyACFG.
+%% callbacks for hipe_regalloc_prepass
+-export([new_reg_nr/1,
+ update_reg_nr/3,
+ update_bb/4,
+ subst_temps/3]).
-check_and_rewrite(CFG, Coloring) ->
+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 +151,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 08c2541b41..0334142b95 100644
--- a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
+++ b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
@@ -22,126 +22,152 @@
-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(AlreadyACFG) ->
- AlreadyACFG.
+%% callbacks for hipe_regalloc_prepass
+-export([new_reg_nr/1,
+ update_reg_nr/3,
+ update_bb/4,
+ subst_temps/3]).
-check_and_rewrite(CFG, 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_temp_map.erl b/lib/hipe/regalloc/hipe_temp_map.erl
index 4085a0e1a7..b683d08054 100644
--- a/lib/hipe/regalloc/hipe_temp_map.erl
+++ b/lib/hipe/regalloc/hipe_temp_map.erl
@@ -33,10 +33,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 +49,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 +82,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 +106,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 f1007c95ed..67c45cdca5 100644
--- a/lib/hipe/regalloc/hipe_x86_specific.erl
+++ b/lib/hipe/regalloc/hipe_x86_specific.erl
@@ -25,100 +25,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(AlreadyACFG) ->
- AlreadyACFG.
+%% callbacks for hipe_regalloc_prepass
+-export([new_reg_nr/1,
+ update_reg_nr/3,
+ update_bb/4,
+ subst_temps/3]).
-check_and_rewrite(CFG, Coloring) ->
+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 +132,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 +174,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 +207,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 0c022d5a27..85923f8f44 100644
--- a/lib/hipe/regalloc/hipe_x86_specific_x87.erl
+++ b/lib/hipe/regalloc/hipe_x86_specific_x87.erl
@@ -32,117 +32,118 @@
-endif.
-module(?HIPE_X86_SPECIFIC_X87).
--export([allocatable/1,
- 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]).
+-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/3]).
+-export([check_and_rewrite/4]).
%% Rewrite happens in hipe_x86_ra_finalise:finalise/4
-check_and_rewrite(CFG, _Coloring, 'linearscan') ->
+check_and_rewrite(CFG, _Coloring, 'linearscan', _) ->
{CFG, false}.
-breadthorder(CFG) ->
+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('linearscan') ->
+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)],
@@ -152,21 +153,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.
diff --git a/lib/hipe/rtl/hipe_rtl_primops.erl b/lib/hipe/rtl/hipe_rtl_primops.erl
index 062fab842f..835f489ec0 100644
--- a/lib/hipe/rtl/hipe_rtl_primops.erl
+++ b/lib/hipe/rtl/hipe_rtl_primops.erl
@@ -845,7 +845,7 @@ gen_free_vars([], _, _, _, AccCode) -> AccCode.
%% call_fun (also handles enter_fun when Continuation = [])
gen_call_fun(Dst, ArgsAndFun, Continuation, Fail) ->
- NAddressReg = hipe_rtl:mk_new_reg(),
+ NCNAddressReg = hipe_rtl:mk_new_reg(),
ArityReg = hipe_rtl:mk_new_reg_gcsafe(),
[Fun|RevArgs] = lists:reverse(ArgsAndFun),
@@ -856,7 +856,7 @@ gen_call_fun(Dst, ArgsAndFun, Continuation, Fail) ->
BadFunLabName = hipe_rtl:label_name(NonClosureLabel),
BadFunCode =
[NonClosureLabel,
- hipe_rtl:mk_call([NAddressReg],
+ hipe_rtl:mk_call([NCNAddressReg],
'nonclosure_address',
[Fun, hipe_rtl:mk_imm(length(Args))],
hipe_rtl:label_name(CallNonClosureLabel),
@@ -865,25 +865,26 @@ gen_call_fun(Dst, ArgsAndFun, Continuation, Fail) ->
CallNonClosureLabel,
case Continuation of
[] ->
- hipe_rtl:mk_enter(NAddressReg, Args, not_remote);
+ hipe_rtl:mk_enter(NCNAddressReg, Args, not_remote);
_ ->
- hipe_rtl:mk_call(Dst, NAddressReg, Args,
+ hipe_rtl:mk_call(Dst, NCNAddressReg, Args,
Continuation, Fail, not_remote)
end],
{BadArityLabName, BadArityCode} = gen_fail_code(Fail, {badarity, Fun}),
- CheckGetCode =
- hipe_tagscheme:if_fun_get_arity_and_address(ArityReg, NAddressReg,
+ CNAddressReg = hipe_rtl:mk_new_reg(),
+ CheckGetCode =
+ hipe_tagscheme:if_fun_get_arity_and_address(ArityReg, CNAddressReg,
Fun, BadFunLabName,
0.9),
CheckArityCode = check_arity(ArityReg, length(RevArgs), BadArityLabName),
CallCode =
case Continuation of
[] -> %% This is a tailcall
- [hipe_rtl:mk_enter(NAddressReg, ArgsAndFun, not_remote)];
+ [hipe_rtl:mk_enter(CNAddressReg, ArgsAndFun, not_remote)];
_ -> %% Ordinary call
- [hipe_rtl:mk_call(Dst, NAddressReg, ArgsAndFun,
+ [hipe_rtl:mk_call(Dst, CNAddressReg, ArgsAndFun,
Continuation, Fail, not_remote)]
end,
[CheckGetCode, CheckArityCode, CallCode, BadFunCode, BadArityCode].
diff --git a/lib/hipe/sparc/Makefile b/lib/hipe/sparc/Makefile
index 0e36a43d8e..ac1230df7c 100644
--- a/lib/hipe/sparc/Makefile
+++ b/lib/hipe/sparc/Makefile
@@ -63,7 +63,8 @@ MODULES=hipe_rtl_to_sparc \
hipe_sparc_ra_naive \
hipe_sparc_ra_postconditions \
hipe_sparc_ra_postconditions_fp \
- hipe_sparc_registers
+ hipe_sparc_registers \
+ hipe_sparc_subst
HRL_FILES=hipe_sparc.hrl
ERL_FILES=$(MODULES:%=%.erl)
diff --git a/lib/hipe/sparc/hipe_sparc_defuse.erl b/lib/hipe/sparc/hipe_sparc_defuse.erl
index 4f66299f1d..4b5a19a19d 100644
--- a/lib/hipe/sparc/hipe_sparc_defuse.erl
+++ b/lib/hipe/sparc/hipe_sparc_defuse.erl
@@ -23,6 +23,7 @@
-export([insn_def_all/1, insn_use_all/1]).
-export([insn_def_gpr/1, insn_use_gpr/1]).
-export([insn_def_fpr/1, insn_use_fpr/1]).
+-export([insn_defs_all_gpr/1, insn_defs_all_fpr/1]).
-include("hipe_sparc.hrl").
%%%
@@ -51,6 +52,12 @@ insn_def_gpr(I) ->
_ -> []
end.
+insn_defs_all_gpr(I) ->
+ case I of
+ #pseudo_call{} -> true;
+ _ -> false
+ end.
+
call_clobbered_gpr() ->
[hipe_sparc:mk_temp(R, T)
|| {R,T} <- hipe_sparc_registers:call_clobbered() ++ all_fp_pseudos()].
@@ -115,6 +122,12 @@ insn_def_fpr(I) ->
_ -> []
end.
+insn_defs_all_fpr(I) ->
+ case I of
+ #pseudo_call{} -> true;
+ _ -> false
+ end.
+
call_clobbered_fpr() ->
[hipe_sparc:mk_temp(R, 'double') || R <- hipe_sparc_registers:allocatable_fpr()].
diff --git a/lib/hipe/sparc/hipe_sparc_ra.erl b/lib/hipe/sparc/hipe_sparc_ra.erl
index 5f955c2058..c4b909528d 100644
--- a/lib/hipe/sparc/hipe_sparc_ra.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra.erl
@@ -24,28 +24,30 @@
ra(CFG0, Options) ->
%% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG0)),
- {CFG1, Coloring_fp, SpillIndex}
+ {CFG1, _FPLiveness1, Coloring_fp, SpillIndex}
= case proplists:get_bool(inline_fp, Options) of
true ->
- hipe_regalloc_loop:ra_fp(CFG0, Options,
+ FPLiveness0 = hipe_sparc_specific_fp:analyze(CFG0, no_context),
+ hipe_regalloc_loop:ra_fp(CFG0, FPLiveness0, Options,
hipe_coalescing_regalloc,
- hipe_sparc_specific_fp);
+ hipe_sparc_specific_fp, no_context);
false ->
- {CFG0,[],0}
+ {CFG0,undefined,[],0}
end,
%% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG1)),
- {CFG2, Coloring}
+ GPLiveness1 = hipe_sparc_specific:analyze(CFG1, no_context),
+ {CFG2, _GPLiveness2, Coloring}
= case proplists:get_value(regalloc, Options, coalescing) of
coalescing ->
- ra(CFG1, SpillIndex, Options, hipe_coalescing_regalloc);
+ ra(CFG1, GPLiveness1, SpillIndex, Options, hipe_coalescing_regalloc);
optimistic ->
- ra(CFG1, SpillIndex, Options, hipe_optimistic_regalloc);
+ ra(CFG1, GPLiveness1, SpillIndex, Options, hipe_optimistic_regalloc);
graph_color ->
- ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc);
+ ra(CFG1, GPLiveness1, SpillIndex, Options, hipe_graph_coloring_regalloc);
linear_scan ->
- hipe_sparc_ra_ls:ra(CFG1, SpillIndex, Options);
+ hipe_sparc_ra_ls:ra(CFG1, GPLiveness1, SpillIndex, Options);
naive ->
- hipe_sparc_ra_naive:ra(CFG1, Coloring_fp, Options);
+ hipe_sparc_ra_naive:ra(CFG1, GPLiveness1, Coloring_fp, Options);
_ ->
exit({unknown_regalloc_compiler_option,
proplists:get_value(regalloc,Options)})
@@ -53,5 +55,6 @@ ra(CFG0, Options) ->
%% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG2)),
hipe_sparc_ra_finalise:finalise(CFG2, Coloring, Coloring_fp).
-ra(CFG, SpillIndex, Options, RegAllocMod) ->
- hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, hipe_sparc_specific).
+ra(CFG, Liveness, SpillIndex, Options, RegAllocMod) ->
+ hipe_regalloc_loop:ra(CFG, Liveness, SpillIndex, Options, RegAllocMod,
+ hipe_sparc_specific, no_context).
diff --git a/lib/hipe/sparc/hipe_sparc_ra_ls.erl b/lib/hipe/sparc/hipe_sparc_ra_ls.erl
index ced9addd31..7019937737 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_ls.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_ls.erl
@@ -21,34 +21,35 @@
%% Linear Scan register allocator for SPARC
-module(hipe_sparc_ra_ls).
--export([ra/3]).
+-export([ra/4]).
-ra(CFG, SpillIndex, Options) ->
- SpillLimit = hipe_sparc_specific:number_of_temporaries(CFG),
- alloc(CFG, SpillIndex, SpillLimit, Options).
+ra(CFG, Liveness, SpillIndex, Options) ->
+ SpillLimit = hipe_sparc_specific:number_of_temporaries(CFG, no_context),
+ alloc(CFG, Liveness, SpillIndex, SpillLimit, Options).
-alloc(CFG, SpillIndex, SpillLimit, Options) ->
- {Coloring, _NewSpillIndex, Liveness} =
+alloc(CFG, Liveness, SpillIndex, SpillLimit, Options) ->
+ {Coloring, _NewSpillIndex} =
regalloc(
- CFG,
+ CFG, Liveness,
hipe_sparc_registers:allocatable_gpr()--
[hipe_sparc_registers:temp3(),
hipe_sparc_registers:temp2(),
hipe_sparc_registers:temp1()],
[hipe_sparc_cfg:start_label(CFG)],
SpillIndex, SpillLimit, Options,
- hipe_sparc_specific),
+ hipe_sparc_specific, no_context),
{NewCFG, _DidSpill} =
hipe_sparc_ra_postconditions:check_and_rewrite(
CFG, Coloring, 'linearscan'),
- TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific, no_context),
{TempMap2,_NewSpillIndex2} =
hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
- hipe_sparc_specific, TempMap),
+ hipe_sparc_specific, no_context, TempMap),
Coloring2 =
hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
- {NewCFG, Coloring2}.
+ {NewCFG, Liveness, Coloring2}.
-regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
- hipe_ls_regalloc:regalloc(
- CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target).
+regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options,
+ TgtMod, TgtCtx) ->
+ hipe_ls_regalloc:regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex,
+ DontSpill, Options, TgtMod, TgtCtx).
diff --git a/lib/hipe/sparc/hipe_sparc_ra_naive.erl b/lib/hipe/sparc/hipe_sparc_ra_naive.erl
index f621d94553..745e44f2f9 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_naive.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_naive.erl
@@ -20,11 +20,11 @@
%%
-module(hipe_sparc_ra_naive).
--export([ra/3]).
+-export([ra/4]).
-include("hipe_sparc.hrl").
-ra(CFG, _Coloring_fp, _Options) -> % -> {CFG, Coloring}
+ra(CFG, Liveness, _Coloring_fp, _Options) -> % -> {CFG, Liveness, Coloring}
{NewCFG,_DidSpill} =
hipe_sparc_ra_postconditions:check_and_rewrite2(CFG, [], 'naive'),
- {NewCFG, []}.
+ {NewCFG, Liveness, []}.
diff --git a/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl b/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl
index 0336a6c59f..e8e231e35c 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl
@@ -26,7 +26,7 @@
-include("hipe_sparc.hrl").
check_and_rewrite(CFG, Coloring, Allocator) ->
- TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific, no_context),
check_and_rewrite2(CFG, TempMap, Allocator).
check_and_rewrite2(CFG, TempMap, Allocator) ->
diff --git a/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl b/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl
index d3e1d8cf93..544b8b05a8 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl
@@ -26,7 +26,8 @@
-include("hipe_sparc.hrl").
check_and_rewrite(CFG, Coloring) ->
- TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific_fp),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific_fp,
+ no_context),
do_bbs(hipe_sparc_cfg:labels(CFG), TempMap, CFG, false).
do_bbs([], _TempMap, CFG, DidSpill) -> {CFG, DidSpill};
diff --git a/lib/hipe/sparc/hipe_sparc_registers.erl b/lib/hipe/sparc/hipe_sparc_registers.erl
index 6681a10070..20138836dd 100644
--- a/lib/hipe/sparc/hipe_sparc_registers.erl
+++ b/lib/hipe/sparc/hipe_sparc_registers.erl
@@ -249,6 +249,8 @@ is_arg(R) ->
_ -> false
end.
+%% Note: the fact that allocatable_gpr() is a subset of call_clobbered() is
+%% hard-coded in hipe_sparc_defuse:insn_defs_all_gpr/1
call_clobbered() -> % does the RA strip the type or not?
[%% ?G0 is the non-allocatable constant zero
{?G1,tagged},{?G1,untagged},
diff --git a/lib/hipe/sparc/hipe_sparc_subst.erl b/lib/hipe/sparc/hipe_sparc_subst.erl
new file mode 100644
index 0000000000..e5cd244985
--- /dev/null
+++ b/lib/hipe/sparc/hipe_sparc_subst.erl
@@ -0,0 +1,85 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 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
+%%
+%% 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.
+%%
+%% %CopyrightEnd%
+%%
+
+-module(hipe_sparc_subst).
+-export([insn_temps/2]).
+-include("hipe_sparc.hrl").
+
+%% These should be moved to hipe_sparc and exported
+-type temp() :: #sparc_temp{}.
+-type src2() :: temp() | #sparc_simm13{}.
+-type src2b() :: src2() | #sparc_uimm5{}.
+-type funv() :: #sparc_mfa{} | #sparc_prim{} | temp().
+-type arg() :: temp() | integer().
+-type insn() :: tuple(). % for now
+
+-type subst_fun() :: fun((temp()) -> temp()).
+
+%% @doc Maps over the temporaries in an instruction
+-spec insn_temps(subst_fun(), insn()) -> insn().
+insn_temps(T, I) ->
+ S2 = fun(O) -> src2_temps(T, O) end,
+ S2B = fun(O) -> src2b_temps(T, O) end,
+ Arg = fun(O) -> arg_temps(T, O) end,
+ case I of
+ #alu{src1=L,src2=R,dst=D} -> I#alu{src1=T(L),src2=S2B(R),dst=T(D)};
+ #bp{} -> I;
+ #comment{} -> I;
+ #jmp{src1=L,src2=R} -> I#jmp{src1=T(L),src2=S2(R)};
+ #label{} -> I;
+ #pseudo_bp{} -> I;
+ #pseudo_call{funv=F} -> I#pseudo_call{funv=funv_temps(T,F)};
+ #pseudo_call_prepare{} -> I;
+ #pseudo_move{src=S,dst=D} -> I#pseudo_move{src=T(S),dst=T(D)};
+ #pseudo_ret{} -> I;
+ #pseudo_set{dst=D}-> I#pseudo_set{dst=T(D)};
+ #pseudo_tailcall{funv=F,stkargs=Stk} ->
+ I#pseudo_tailcall{funv=funv_temps(T,F),stkargs=lists:map(Arg,Stk)};
+ #pseudo_tailcall_prepare{} -> I;
+ #rdy{dst=D} -> I#rdy{dst=T(D)};
+ #sethi{dst=D} -> I#sethi{dst=T(D)};
+ #store{src=S,base=B,disp=D} -> I#store{src=T(S),base=T(B),disp=S2(D)};
+ #fp_binary{src1=L,src2=R,dst=D} ->
+ I#fp_binary{src1=T(L),src2=T(R),dst=T(D)};
+ #fp_unary{src=S,dst=D} -> I#fp_unary{src=T(S),dst=T(D)};
+ #pseudo_fload{base=B,disp=Di,dst=Ds} ->
+ I#pseudo_fload{base=T(B),disp=S2(Di),dst=T(Ds)};
+ #pseudo_fmove{src=S,dst=D} -> I#pseudo_fmove{src=T(S),dst=T(D)};
+ #pseudo_fstore{src=S,base=B,disp=D} ->
+ I#pseudo_fstore{src=T(S),base=T(B),disp=S2(D)}
+ end.
+
+-spec src2_temps(subst_fun(), src2()) -> src2().
+src2_temps(_SubstTemp, I=#sparc_simm13{}) -> I;
+src2_temps(SubstTemp, T=#sparc_temp{}) -> SubstTemp(T).
+
+-spec src2b_temps(subst_fun(), src2b()) -> src2b().
+src2b_temps(_SubstTemp, I=#sparc_uimm5{}) -> I;
+src2b_temps(SubstTemp, Op) -> src2_temps(SubstTemp, Op).
+
+-spec funv_temps(subst_fun(), funv()) -> funv().
+funv_temps(_SubstTemp, M=#sparc_mfa{}) -> M;
+funv_temps(_SubstTemp, P=#sparc_prim{}) -> P;
+funv_temps(SubstTemp, T=#sparc_temp{}) -> SubstTemp(T).
+
+-spec arg_temps(subst_fun(), arg()) -> arg().
+arg_temps(_SubstTemp, Imm) when is_integer(Imm) -> Imm;
+arg_temps(SubstTemp, T=#sparc_temp{}) -> SubstTemp(T).
diff --git a/lib/hipe/x86/Makefile b/lib/hipe/x86/Makefile
index 9b21270426..84edeaebe7 100644
--- a/lib/hipe/x86/Makefile
+++ b/lib/hipe/x86/Makefile
@@ -62,6 +62,7 @@ MODULES=hipe_rtl_to_x86 \
hipe_x86_ra_postconditions \
hipe_x86_registers \
hipe_x86_spill_restore \
+ hipe_x86_subst \
hipe_x86_x87
HRL_FILES=hipe_x86.hrl
diff --git a/lib/hipe/x86/hipe_x86_defuse.erl b/lib/hipe/x86/hipe_x86_defuse.erl
index 9cba6cbe4b..4455def74e 100644
--- a/lib/hipe/x86/hipe_x86_defuse.erl
+++ b/lib/hipe/x86/hipe_x86_defuse.erl
@@ -35,7 +35,7 @@
-endif.
-module(?HIPE_X86_DEFUSE).
--export([insn_def/1, insn_use/1]). %% src_use/1]).
+-export([insn_def/1, insn_defs_all/1, insn_use/1]). %% src_use/1]).
-include("../x86/hipe_x86.hrl").
%%%
@@ -64,6 +64,16 @@ insn_def(I) ->
_ -> []
end.
+
+%% @doc Answers whether instruction I defines all allocatable registers. Used by
+%% hipe_regalloc_prepass.
+-spec insn_defs_all(_) -> boolean().
+insn_defs_all(I) ->
+ case I of
+ #pseudo_call{} -> true;
+ _ -> false
+ end.
+
dst_def(Dst) ->
case Dst of
#x86_temp{} -> [Dst];
diff --git a/lib/hipe/x86/hipe_x86_pp.erl b/lib/hipe/x86/hipe_x86_pp.erl
index 9352cf5dbf..ff26a31877 100644
--- a/lib/hipe/x86/hipe_x86_pp.erl
+++ b/lib/hipe/x86/hipe_x86_pp.erl
@@ -171,7 +171,7 @@ pp_insn(Dev, I, Pre) ->
#pseudo_tailcall{'fun'=Fun, arity=Arity, stkargs=StkArgs, linkage=Linkage} ->
io:format(Dev, "\tpseudo_tailcall ", []),
pp_fun(Dev, Fun),
- io:format(Dev, "~w (", [Arity]),
+ io:format(Dev, " ~w (", [Arity]),
pp_args(Dev, StkArgs),
io:format(Dev, ") ~w\n", [Linkage]);
#pseudo_tailcall_prepare{} ->
diff --git a/lib/hipe/x86/hipe_x86_ra.erl b/lib/hipe/x86/hipe_x86_ra.erl
index 3af333ab4b..b64c22a76c 100644
--- a/lib/hipe/x86/hipe_x86_ra.erl
+++ b/lib/hipe/x86/hipe_x86_ra.erl
@@ -49,27 +49,24 @@ code_size(CFG) ->
ra(CFG0, Options) ->
%% hipe_x86_cfg:pp(CFG0),
- {CFG1, Coloring_fp, SpillIndex, Liveness} =
- case ra_fp(CFG0, Options) of
- {G, C, I} -> {G, C, I, undefined};
- {_,_,_,_}=T -> T
- end,
+ Liveness0 = ?HIPE_X86_SPECIFIC:analyze(CFG0, no_context),
+ {CFG1, Liveness, Coloring_fp, SpillIndex} = ra_fp(CFG0, Liveness0, Options),
%% hipe_x86_cfg:pp(CFG1),
?start_ra_instrumentation(Options,
code_size(CFG1),
element(2,hipe_gensym:var_range(x86))),
- {CFG2, Coloring}
+ {CFG2, _, Coloring}
= case proplists:get_value(regalloc, Options, coalescing) of
coalescing ->
- ra(CFG1, SpillIndex, Options, hipe_coalescing_regalloc);
+ ra(CFG1, Liveness, SpillIndex, Options, hipe_coalescing_regalloc);
optimistic ->
- ra(CFG1, SpillIndex, Options, hipe_optimistic_regalloc);
+ ra(CFG1, Liveness, SpillIndex, Options, hipe_optimistic_regalloc);
graph_color ->
- ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc);
+ ra(CFG1, Liveness, SpillIndex, Options, hipe_graph_coloring_regalloc);
linear_scan ->
?HIPE_X86_RA_LS:ra(CFG1, Liveness, SpillIndex, Options);
naive ->
- ?HIPE_X86_RA_NAIVE:ra(CFG1, Coloring_fp, Options);
+ ?HIPE_X86_RA_NAIVE:ra(CFG1, Liveness, Coloring_fp, Options);
_ ->
exit({unknown_regalloc_compiler_option,
proplists:get_value(regalloc,Options)})
@@ -80,11 +77,12 @@ ra(CFG0, Options) ->
%% hipe_x86_cfg:pp(CFG2),
?HIPE_X86_RA_FINALISE:finalise(CFG2, Coloring, Coloring_fp, Options).
-ra(CFG, SpillIndex, Options, RegAllocMod) ->
- hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, ?HIPE_X86_SPECIFIC).
+ra(CFG, Liveness, SpillIndex, Options, RegAllocMod) ->
+ hipe_regalloc_loop:ra(CFG, Liveness, SpillIndex, Options, RegAllocMod,
+ ?HIPE_X86_SPECIFIC, no_context).
-ifdef(HIPE_AMD64).
-ra_fp(CFG, Options) ->
+ra_fp(CFG, Liveness, Options) ->
Regalloc0 = proplists:get_value(regalloc, Options),
{Regalloc, TargetMod} =
case proplists:get_bool(inline_fp, Options) and (Regalloc0 =/= naive) of
@@ -96,25 +94,30 @@ ra_fp(CFG, Options) ->
end
end,
case Regalloc of
- coalescing -> ra_fp(CFG, Options, hipe_coalescing_regalloc, TargetMod);
- optimistic -> ra_fp(CFG, Options, hipe_optimistic_regalloc, TargetMod);
- graph_color -> ra_fp(CFG, Options, hipe_graph_coloring_regalloc,
- TargetMod);
- linear_scan -> hipe_amd64_ra_ls:ra_fp(CFG, Options, TargetMod);
- naive -> {CFG,[],0};
+ coalescing ->
+ ra_fp(CFG, Liveness, Options, hipe_coalescing_regalloc, TargetMod);
+ optimistic ->
+ ra_fp(CFG, Liveness, Options, hipe_optimistic_regalloc, TargetMod);
+ graph_color ->
+ ra_fp(CFG, Liveness, Options, hipe_graph_coloring_regalloc, TargetMod);
+ linear_scan -> hipe_amd64_ra_ls:ra_fp(CFG, Liveness, Options, TargetMod,
+ no_context);
+ naive -> {CFG,Liveness,[],0};
_ ->
exit({unknown_regalloc_compiler_option,
proplists:get_value(regalloc,Options)})
end.
-ra_fp(CFG, Options, RegAllocMod, TargetMod) ->
- hipe_regalloc_loop:ra_fp(CFG, Options, RegAllocMod, TargetMod).
+ra_fp(CFG, Liveness, Options, RegAllocMod, TargetMod) ->
+ hipe_regalloc_loop:ra_fp(CFG, Liveness, Options, RegAllocMod, TargetMod,
+ no_context).
-else.
-ra_fp(CFG, Options) ->
+ra_fp(CFG, Liveness, Options) ->
case proplists:get_bool(inline_fp, Options) of
true ->
- hipe_x86_ra_ls:ra_fp(CFG, Options, hipe_x86_specific_x87);
+ hipe_x86_ra_ls:ra_fp(CFG, Liveness, Options, hipe_x86_specific_x87,
+ no_context);
false ->
- {CFG,[],0}
+ {CFG,Liveness,[],0}
end.
-endif.
diff --git a/lib/hipe/x86/hipe_x86_ra_finalise.erl b/lib/hipe/x86/hipe_x86_ra_finalise.erl
index 62009abb76..edfd7b332c 100644
--- a/lib/hipe/x86/hipe_x86_ra_finalise.erl
+++ b/lib/hipe/x86/hipe_x86_ra_finalise.erl
@@ -244,49 +244,27 @@ mk_ra_map(TempMap, SpillLimit) ->
gb_trees:empty(),
TempMap).
-conv_ra_maplet(MapLet = {From,To}, SpillLimit, IsPrecoloured) ->
+conv_ra_maplet({From,To}, SpillLimit, IsPrecoloured)
+ when is_integer(From), From =< SpillLimit ->
%% From should be a pseudo, or a hard reg mapped to itself.
- if is_integer(From), From =< SpillLimit ->
- case ?HIPE_X86_REGISTERS:IsPrecoloured(From) of
- false -> [];
- _ ->
- case To of
- {reg, From} -> [];
- _ -> exit({?MODULE,conv_ra_maplet,MapLet})
- end
- end;
- true -> exit({?MODULE,conv_ra_maplet,MapLet})
+ case ?HIPE_X86_REGISTERS:IsPrecoloured(From) of
+ false -> ok;
+ _ -> To = {reg, From}, ok
end,
%% end of From check
case To of
- {reg, NewReg} ->
+ {reg, NewReg} when is_integer(NewReg) ->
%% NewReg should be a hard reg, or a pseudo mapped
%% to itself (formals are handled this way).
- if is_integer(NewReg) ->
- case ?HIPE_X86_REGISTERS:IsPrecoloured(NewReg) of
- true -> [];
- _ -> if From =:= NewReg -> [];
- true ->
- exit({?MODULE,conv_ra_maplet,MapLet})
- end
- end;
- true -> exit({?MODULE,conv_ra_maplet,MapLet})
- end,
- %% end of NewReg check
+ true = (?HIPE_X86_REGISTERS:IsPrecoloured(NewReg) orelse From =:= NewReg),
{From, NewReg};
- {spill, SpillIndex} ->
- %% SpillIndex should be >= 0.
- if is_integer(SpillIndex), SpillIndex >= 0 -> [];
- true -> exit({?MODULE,conv_ra_maplet,MapLet})
- end,
- %% end of SpillIndex check
+ {spill, SpillIndex} when is_integer(SpillIndex), SpillIndex >= 0 ->
ToTempNum = SpillLimit+SpillIndex+1,
MaxTempNum = hipe_gensym:get_var(x86),
if MaxTempNum >= ToTempNum -> ok;
true -> hipe_gensym:set_var(x86, ToTempNum)
end,
- {From, ToTempNum};
- _ -> exit({?MODULE,conv_ra_maplet,MapLet})
+ {From, ToTempNum}
end.
mk_ra_map_x87(FpMap, SpillLimit) ->
diff --git a/lib/hipe/x86/hipe_x86_ra_ls.erl b/lib/hipe/x86/hipe_x86_ra_ls.erl
index 9f019f9561..34ce50d494 100644
--- a/lib/hipe/x86/hipe_x86_ra_ls.erl
+++ b/lib/hipe/x86/hipe_x86_ra_ls.erl
@@ -35,66 +35,64 @@
-endif.
-module(?HIPE_X86_RA_LS).
--export([ra/4,ra_fp/3]).
+-export([ra/4,ra_fp/5]).
-define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation.
-include("../main/hipe.hrl").
ra(CFG, Liveness, SpillIndex, Options) ->
SpillLimit = ?HIPE_X86_SPECIFIC:number_of_temporaries(
- CFG),
+ CFG, no_context),
?inc_counter(bbs_counter, length(hipe_x86_cfg:labels(CFG))),
alloc(CFG, Liveness, SpillIndex, SpillLimit, Options).
-ra_fp(CFG, Options, TargetMod) ->
+ra_fp(CFG, Liveness, Options, TargetMod, TargetCtx) ->
?inc_counter(ra_calls_counter,1),
%% ?inc_counter(ra_caller_saves_counter,count_caller_saves(CFG)),
SpillIndex = 0,
- SpillLimit = TargetMod:number_of_temporaries(CFG),
+ SpillLimit = TargetMod:number_of_temporaries(CFG, TargetCtx),
?inc_counter(bbs_counter, length(hipe_x86_cfg:labels(CFG))),
?inc_counter(ra_iteration_counter,1),
%% ?HIPE_X86_PP:pp(Defun),
- {Coloring,NewSpillIndex,Liveness} =
- regalloc(CFG,
- undefined,
- TargetMod:allocatable('linearscan'),
+ {Coloring,NewSpillIndex} =
+ regalloc(CFG, Liveness,
+ TargetMod:allocatable('linearscan', TargetCtx),
[hipe_x86_cfg:start_label(CFG)],
SpillIndex, SpillLimit, Options,
- TargetMod),
+ TargetMod, TargetCtx),
{NewCFG, _DidSpill} =
- TargetMod:check_and_rewrite(CFG, Coloring, 'linearscan'),
- TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod),
+ TargetMod:check_and_rewrite(CFG, Coloring, 'linearscan', TargetCtx),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod, TargetCtx),
{TempMap2, NewSpillIndex2} =
hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
- TargetMod, TempMap),
+ TargetMod, TargetCtx, TempMap),
Coloring2 =
hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
?add_spills(Options, NewSpillIndex),
- {NewCFG, Coloring2, NewSpillIndex2, Liveness}.
+ {NewCFG, Liveness, Coloring2, NewSpillIndex2}.
-alloc(CFG, Liveness0, SpillIndex, SpillLimit, Options) ->
+alloc(CFG, Liveness, SpillIndex, SpillLimit, Options) ->
?inc_counter(ra_iteration_counter,1),
%% ?HIPE_X86_PP:pp(Defun),
- {Coloring, NewSpillIndex, Liveness} =
+ {Coloring, NewSpillIndex} =
regalloc(
- CFG,
- Liveness0,
+ CFG, Liveness,
?HIPE_X86_REGISTERS:allocatable()--
[?HIPE_X86_REGISTERS:temp1(),
?HIPE_X86_REGISTERS:temp0()],
[hipe_x86_cfg:start_label(CFG)],
SpillIndex, SpillLimit, Options,
- ?HIPE_X86_SPECIFIC),
+ ?HIPE_X86_SPECIFIC, no_context),
{NewCFG, _DidSpill} =
?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite(
CFG, Coloring, 'linearscan'),
%% ?HIPE_X86_PP:pp(NewDefun),
- TempMap = hipe_temp_map:cols2tuple(Coloring, ?HIPE_X86_SPECIFIC),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, ?HIPE_X86_SPECIFIC, no_context),
{TempMap2,NewSpillIndex2} =
hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
- ?HIPE_X86_SPECIFIC, TempMap),
+ ?HIPE_X86_SPECIFIC, no_context, TempMap),
Coloring2 =
hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
case proplists:get_bool(verbose_spills, Options) of
@@ -104,9 +102,9 @@ alloc(CFG, Liveness0, SpillIndex, SpillLimit, Options) ->
ok
end,
?add_spills(Options, NewSpillIndex),
- {NewCFG, Coloring2}.
+ {NewCFG, Liveness, Coloring2}.
-regalloc(CFG,Liveness,PhysRegs,Entrypoints, SpillIndex, DontSpill, Options,
- Target) ->
- hipe_ls_regalloc:regalloc(CFG,Liveness,PhysRegs,Entrypoints, SpillIndex,
- DontSpill, Options, Target).
+regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options,
+ TgtMod, TgtCtx) ->
+ hipe_ls_regalloc:regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex,
+ DontSpill, Options, TgtMod, TgtCtx).
diff --git a/lib/hipe/x86/hipe_x86_ra_naive.erl b/lib/hipe/x86/hipe_x86_ra_naive.erl
index 27e5af4aee..35de692e07 100644
--- a/lib/hipe/x86/hipe_x86_ra_naive.erl
+++ b/lib/hipe/x86/hipe_x86_ra_naive.erl
@@ -33,13 +33,13 @@
-endif.
-module(?HIPE_X86_RA_NAIVE).
--export([ra/3]).
+-export([ra/4]).
-include("../x86/hipe_x86.hrl").
-define(HIPE_INSTRUMENT_COMPILER, true). % enable instrumentation
-include("../main/hipe.hrl").
-ra(CFG0, Coloring_fp, Options) ->
+ra(CFG0, Liveness, Coloring_fp, Options) ->
CFG = hipe_x86_cfg:map_bbs(fun do_bb/2, CFG0),
NofSpilledFloats = count_non_float_spills(Coloring_fp),
NofFloats = length(Coloring_fp),
@@ -48,7 +48,7 @@ ra(CFG0, Coloring_fp, Options) ->
NofSpilledFloats -
NofFloats),
TempMap = [],
- {CFG,
+ {CFG, Liveness,
TempMap}.
do_bb(_Lbl, BB) ->
@@ -58,7 +58,7 @@ count_non_float_spills(Coloring_fp) ->
count_non_float_spills(Coloring_fp, 0).
count_non_float_spills([{_,To}|Tail], Num) ->
- case ?HIPE_X86_SPECIFIC_FP:is_precoloured(To) of
+ case ?HIPE_X86_SPECIFIC_FP:is_precoloured(To, no_context) of
true ->
count_non_float_spills(Tail, Num);
false ->
diff --git a/lib/hipe/x86/hipe_x86_ra_postconditions.erl b/lib/hipe/x86/hipe_x86_ra_postconditions.erl
index c73d029b9b..f496b71828 100644
--- a/lib/hipe/x86/hipe_x86_ra_postconditions.erl
+++ b/lib/hipe/x86/hipe_x86_ra_postconditions.erl
@@ -42,7 +42,7 @@
check_and_rewrite(CFG, Coloring, Strategy) ->
%% io:format("Converting\n"),
- TempMap = hipe_temp_map:cols2tuple(Coloring, ?HIPE_X86_SPECIFIC),
+ TempMap = hipe_temp_map:cols2tuple(Coloring, ?HIPE_X86_SPECIFIC, no_context),
%% io:format("Rewriting\n"),
do_bbs(hipe_x86_cfg:labels(CFG), TempMap, Strategy, CFG, false).
@@ -389,19 +389,12 @@ is_mem_opnd(Opnd, TempMap) ->
Reg = hipe_x86:temp_reg(Opnd),
case hipe_x86:temp_is_allocatable(Opnd) of
true ->
- case tuple_size(TempMap) > Reg of
+ case
+ hipe_temp_map:is_spilled(Reg, TempMap) of
true ->
- case
- hipe_temp_map:is_spilled(Reg, TempMap) of
- true ->
- ?count_temp(Reg),
- true;
- false -> false
- end;
- _ ->
- %% impossible, but was true in ls post and false in normal post
- exit({?MODULE,is_mem_opnd,Reg}),
- false
+ ?count_temp(Reg),
+ true;
+ false -> false
end;
false -> true
end;
@@ -416,15 +409,10 @@ is_spilled(Temp, TempMap) ->
case hipe_x86:temp_is_allocatable(Temp) of
true ->
Reg = hipe_x86:temp_reg(Temp),
- case tuple_size(TempMap) > Reg of
+ case hipe_temp_map:is_spilled(Reg, TempMap) of
true ->
- case hipe_temp_map:is_spilled(Reg, TempMap) of
- true ->
- ?count_temp(Reg),
- true;
- false ->
- false
- end;
+ ?count_temp(Reg),
+ true;
false ->
false
end;
@@ -441,14 +429,14 @@ clone(Dst, Strategy) ->
end,
spill_temp(Type, Strategy).
-spill_temp0(Type, 'normal') ->
+spill_temp0(Type, 'normal') when Type =/= double ->
hipe_x86:mk_new_temp(Type);
-spill_temp0(Type, 'linearscan') ->
+spill_temp0(Type, 'linearscan') when Type =/= double ->
hipe_x86:mk_temp(?HIPE_X86_REGISTERS:temp0(), Type).
-spill_temp(Type, 'normal') ->
+spill_temp(Type, 'normal') when Type =/= double ->
hipe_x86:mk_new_temp(Type);
-spill_temp(Type, 'linearscan') ->
+spill_temp(Type, 'linearscan') when Type =/= double ->
hipe_x86:mk_temp(?HIPE_X86_REGISTERS:temp1(), Type).
%%% Make a certain reg into a clone of Dst
@@ -460,6 +448,6 @@ clone2(Dst, RegOpt) ->
#x86_temp{} -> hipe_x86:temp_type(Dst)
end,
case RegOpt of
- [] -> hipe_x86:mk_new_temp(Type);
+ [] when Type =/= double -> hipe_x86:mk_new_temp(Type);
Reg -> hipe_x86:mk_temp(Reg, Type)
end.
diff --git a/lib/hipe/x86/hipe_x86_registers.erl b/lib/hipe/x86/hipe_x86_registers.erl
index 179d734501..f00bbfb280 100644
--- a/lib/hipe/x86/hipe_x86_registers.erl
+++ b/lib/hipe/x86/hipe_x86_registers.erl
@@ -224,6 +224,8 @@ ret(N) ->
exit({?MODULE, ret, N})
end.
+%% Note: the fact that (allocatable() UNION allocatable_x87()) is a subset of
+%% call_clobbered() is hard-coded in hipe_x86_defuse:insn_defs_all/1
call_clobbered() ->
[{?EAX,tagged},{?EAX,untagged}, % does the RA strip the type or not?
{?EDX,tagged},{?EDX,untagged},
diff --git a/lib/hipe/x86/hipe_x86_subst.erl b/lib/hipe/x86/hipe_x86_subst.erl
new file mode 100644
index 0000000000..5e642d1d06
--- /dev/null
+++ b/lib/hipe/x86/hipe_x86_subst.erl
@@ -0,0 +1,94 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 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
+%%
+%% 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.
+%%
+%% %CopyrightEnd%
+%%
+
+-ifdef(HIPE_AMD64).
+-define(HIPE_X86_SUBST, hipe_amd64_subst).
+-else.
+-define(HIPE_X86_SUBST, hipe_x86_subst).
+-endif.
+
+-module(?HIPE_X86_SUBST).
+-export([insn_temps/2]).
+-include("../x86/hipe_x86.hrl").
+
+%% These should be moved to hipe_x86 and exported
+-type temp() :: #x86_temp{}.
+-type oper() :: temp() | #x86_imm{} | #x86_mem{}.
+-type mfarec() :: #x86_mfa{}.
+-type prim() :: #x86_prim{}.
+-type funv() :: mfarec() | prim() | temp().
+-type insn() :: tuple(). % for now
+
+-type subst_fun() :: fun((temp()) -> temp()).
+
+%% @doc Maps over the temporaries in an instruction
+-spec insn_temps(subst_fun(), insn()) -> insn().
+insn_temps(SubstTemp, I) ->
+ O = fun(O) -> oper_temps(SubstTemp, O) end,
+ case I of
+ #alu {src=S, dst=D} -> I#alu {src=O(S), dst=O(D)};
+ #cmovcc {src=S, dst=D} -> I#cmovcc {src=O(S), dst=O(D)};
+ #cmp {src=S, dst=D} -> I#cmp {src=O(S), dst=O(D)};
+ #fmove {src=S, dst=D} -> I#fmove {src=O(S), dst=O(D)};
+ #fp_binop{src=S, dst=D} -> I#fp_binop{src=O(S), dst=O(D)};
+ #imul {src=S, temp=T} -> I#imul {src=O(S), temp=O(T)};
+ #lea {mem=M, temp=T} -> I#lea {mem=O(M), temp=O(T)};
+ #move {src=S, dst=D} -> I#move {src=O(S), dst=O(D)};
+ #movsx {src=S, dst=D} -> I#movsx {src=O(S), dst=O(D)};
+ #movzx {src=S, dst=D} -> I#movzx {src=O(S), dst=O(D)};
+ #shift {src=S, dst=D} -> I#shift {src=O(S), dst=O(D)};
+ #test {src=S, dst=D} -> I#test {src=O(S), dst=O(D)};
+ #fp_unop{arg=A} -> I#fp_unop{arg=O(A)};
+ #move64 {dst=D} -> I#move64 {dst=O(D)};
+ #push {src=S} -> I#push {src=O(S)};
+ #pop {dst=D} -> I#pop {dst=O(D)};
+ #jmp_switch{temp=T, jtab=J} ->
+ I#jmp_switch{temp=O(T), jtab=jtab_temps(SubstTemp, J)};
+ #pseudo_call{'fun'=F} ->
+ I#pseudo_call{'fun'=funv_temps(SubstTemp, F)};
+ #pseudo_tailcall{'fun'=F, stkargs=Stk} ->
+ I#pseudo_tailcall{'fun'=funv_temps(SubstTemp, F),
+ stkargs=lists:map(O, Stk)};
+ #comment{} -> I;
+ #jmp_label{} -> I;
+ #pseudo_tailcall_prepare{} -> I;
+ #pseudo_jcc{} -> I;
+ #ret{} -> I
+ end.
+
+-spec oper_temps(subst_fun(), oper()) -> oper().
+oper_temps(_SubstTemp, I=#x86_imm{}) -> I;
+oper_temps(SubstTemp, T=#x86_temp{}) -> SubstTemp(T);
+oper_temps(SubstTemp, M=#x86_mem{base=Base,off=Off}) ->
+ M#x86_mem{base=oper_temps(SubstTemp, Base),
+ off =oper_temps(SubstTemp, Off)}.
+
+-spec funv_temps(subst_fun(), funv()) -> funv().
+funv_temps(_SubstTemp, MFA=#x86_mfa{}) -> MFA;
+funv_temps(_SubstTemp, P=#x86_prim{}) -> P;
+funv_temps(SubstTemp, T=#x86_temp{}) -> SubstTemp(T).
+
+%% TODO: Undo this ifdeffery at the source (make jtab an #x86_imm{} on x86)
+-ifdef(HIPE_AMD64).
+jtab_temps(SubstTemp, T=#x86_temp{}) -> SubstTemp(T).
+-else.
+jtab_temps(_SubstTemp, DataLbl) when is_integer(DataLbl) -> DataLbl.
+-endif.