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

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.