hipe: Reuse liveness between regalloc iterations

This is sound because the liveness data structure only stores liveness
info at basic block boundaries, and the rewrites that happen in
TargetSpecific:check_and_rewrite/2 preserves all existing definitions
and uses, and all new liveness intervals, belonging to newly introduced
temporaries, are always local to a basic block, and thus do not show up
in the liveout or livein sets for the basic block.

18 files changed, 198 insertions, 207 deletions

diff --git a/lib/hipe/arm/hipe_arm_ra.erl b/lib/hipe/arm/hipe_arm_ra.erl
index 5a7884b63c..d709cc537e 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),
+%%	  hipe_regalloc_loop:ra_fp(CFG0, FPLiveness0, Options,
 %%				   hipe_coalescing_regalloc,
 %%				   hipe_arm_specific_fp);
 	false ->
-	  {CFG0,[],0}
+	  {CFG0,undefined,[],0}
       end,
   %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG1)),
-  {CFG2, Coloring}
+  GPLiveness1 = hipe_arm_specific:analyze(CFG1),
+  {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).
diff --git a/lib/hipe/arm/hipe_arm_ra_ls.erl b/lib/hipe/arm/hipe_arm_ra_ls.erl
index f9193ca9e0..4d517d6697 100644
--- a/lib/hipe/arm/hipe_arm_ra_ls.erl
+++ b/lib/hipe/arm/hipe_arm_ra_ls.erl
@@ -21,16 +21,16 @@
 %%% Linear Scan register allocator for ARM
 
 -module(hipe_arm_ra_ls).
--export([ra/3]).
+-export([ra/4]).
 
-ra(CFG, SpillIndex, Options) ->
+ra(CFG, Liveness, SpillIndex, Options) ->
   SpillLimit = hipe_arm_specific:number_of_temporaries(CFG),
-  alloc(CFG, SpillIndex, SpillLimit, Options).
+  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(),
@@ -47,8 +47,9 @@ alloc(CFG, SpillIndex, SpillLimit, Options) ->
 			     hipe_arm_specific, 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,
+	 Target) ->
+  hipe_ls_regalloc:regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex,
+			    DontSpill, Options, Target).
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/ppc/hipe_ppc_ra.erl b/lib/hipe/ppc/hipe_ppc_ra.erl
index bfb4d35139..7c8a11773e 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),
+	  hipe_regalloc_loop:ra_fp(CFG0, FPLiveness0, Options,
 				   hipe_coalescing_regalloc,
 				   hipe_ppc_specific_fp);
 	false ->
-	  {CFG0,[],0}
+	  {CFG0,undefined,[],0}
       end,
   %% hipe_ppc_pp:pp(hipe_ppc_cfg:linearise(CFG1)),
-  {CFG2, Coloring}
+  GPLiveness1 = hipe_ppc_specific:analyze(CFG1),
+  {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).
diff --git a/lib/hipe/ppc/hipe_ppc_ra_ls.erl b/lib/hipe/ppc/hipe_ppc_ra_ls.erl
index 52562fc321..956b55d9f1 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_ls.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_ls.erl
@@ -21,16 +21,16 @@
 %%% Linear Scan register allocator for PowerPC
 
 -module(hipe_ppc_ra_ls).
--export([ra/3]).
+-export([ra/4]).
 
-ra(CFG, SpillIndex, Options) ->
+ra(CFG, Liveness, SpillIndex, Options) ->
   SpillLimit = hipe_ppc_specific:number_of_temporaries(CFG),
-  alloc(CFG, SpillIndex, SpillLimit, Options).
+  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(),
@@ -47,8 +47,9 @@ alloc(CFG, SpillIndex, SpillLimit, Options) ->
 			     hipe_ppc_specific, 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,
+	 Target) ->
+  hipe_ls_regalloc:regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex,
+			    DontSpill, Options, Target).
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/regalloc/hipe_coalescing_regalloc.erl b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl
index bbb2e3ecf0..5f4bd4e524 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/6]).
 
 %%-ifndef(DEBUG).
 %%-define(DEBUG,true).
@@ -54,10 +54,9 @@
 %%   SpillIndex2 -- A new spill index
 %%-----------------------------------------------------------------------
 
-regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
+regalloc(CFG, Liveness, SpillIndex, SpillLimit, Target, _Options) ->
   %% Build interference graph
   ?debug_msg("Build IG\n", []),
-  Liveness = Target:analyze(CFG),
   IG = hipe_ig:build(CFG, Liveness, Target),
   %% io:format("IG: ~p\n", [IG]),
 
@@ -98,7 +97,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
diff --git a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl
index f71feebfc6..225f06bded 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/6]).
 
 %%-ifndef(DO_ASSERT).
 %%-define(DO_ASSERT, true).
@@ -77,12 +77,13 @@
 %% 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(),
+%%                atom(), list()) -> {, non_neg_fixnum()}
 
-regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
+regalloc(CFG, Live, SpillIndex, SpillLimit, Target, _Options) ->
   PhysRegs = Target:allocatable(),
   ?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]),
@@ -102,7 +103,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
   Coloring = [{X, {reg, X}} || X <- NotAllocatable] ++ Cols,
   ?ASSERT(check_coloring(Coloring, IG, Target)),
 
-  {Coloring, NewSpillIndex, Live}.
+  {Coloring, NewSpillIndex}.
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -112,8 +113,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
 %% Returns {Interference_graph, Spill_cost_dictionary}
 %%
 
-build_ig(CFG, Target) ->
-  Live = Target:analyze(CFG),
+build_ig(CFG, Live, Target) ->
   NumN = Target:number_of_temporaries(CFG),  % poss. N-1?
   {IG, Spill} = build_ig_bbs(Target:labels(CFG), 
 			     CFG, 
@@ -121,7 +121,7 @@ build_ig(CFG, Target) ->
 			     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};
diff --git a/lib/hipe/regalloc/hipe_ls_regalloc.erl b/lib/hipe/regalloc/hipe_ls_regalloc.erl
index c318927077..8d9cd8f507 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/8]).
 
 %%-define(DEBUG,1).
 -define(HIPE_INSTRUMENT_COMPILER, true).
@@ -95,19 +95,8 @@
 %%   </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, Target) ->
   ?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 +108,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}.
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%                                                                    %%
@@ -760,9 +749,6 @@ create_freeregs([]) ->
 %% 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-liveness(CFG, Target) ->
-  Target:analyze(CFG).
-
 bb(CFG, L, Target) ->
   Target:bb(CFG,L).
 
diff --git a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
index 67674be14c..43c6424655 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/6]).
 
 -ifndef(DEBUG).
 %%-define(DEBUG,true).
@@ -81,12 +81,11 @@
 %%   SpillIndex2 -- A new spill index
 %%-----------------------------------------------------------------------
 -ifdef(COMPARE_ITERATED_OPTIMISTIC).
-regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
+regalloc(CFG, Liveness, SpillIndex, SpillLimit, Target, _Options) ->
   ?debug_msg("optimistic ~w\n",[Target]),
   ?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),
   ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]),
@@ -219,14 +218,13 @@ 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) ->
+regalloc(CFG, Liveness, SpillIndex, SpillLimit, Target, _Options) ->
   ?debug_msg("optimistic ~w\n",[Target]),
   ?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),
   ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]),
   ?debug_msg("IG:\n",[]),
@@ -321,7 +319,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.
 
 %%----------------------------------------------------------------------
diff --git a/lib/hipe/regalloc/hipe_regalloc_loop.erl b/lib/hipe/regalloc/hipe_regalloc_loop.erl
index 3b21a377df..9557461244 100644
--- a/lib/hipe/regalloc/hipe_regalloc_loop.erl
+++ b/lib/hipe/regalloc/hipe_regalloc_loop.erl
@@ -21,32 +21,32 @@
 %%% Common wrapper for graph_coloring and coalescing regallocs.
 
 -module(hipe_regalloc_loop).
--export([ra/5, ra_fp/4]).
+-export([ra/6, ra_fp/5]).
 
 %%-define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation.
 -include("../main/hipe.hrl").
 
-ra(CFG, SpillIndex, Options, RegAllocMod, TargetMod) ->
-  {NewCFG, Coloring, _NewSpillIndex} =
-    ra_common(CFG, SpillIndex, Options, RegAllocMod, TargetMod),
-  {NewCFG, Coloring}.
+ra(CFG, Liveness0, SpillIndex, Options, RegAllocMod, TargetMod) ->
+  {NewCFG, Liveness, Coloring, _NewSpillIndex} =
+    ra_common(CFG, Liveness0, SpillIndex, Options, RegAllocMod, TargetMod),
+  {NewCFG, Liveness, Coloring}.
 
-ra_fp(CFG, Options, RegAllocMod, TargetMod) ->
-  ra_common(CFG, 0, Options, RegAllocMod, TargetMod).
+ra_fp(CFG, Liveness, Options, RegAllocMod, TargetMod) ->
+  ra_common(CFG, Liveness, 0, Options, RegAllocMod, TargetMod).
 
-ra_common(CFG0, SpillIndex, Options, RegAllocMod, TargetMod) ->
+ra_common(CFG0, Liveness0, SpillIndex, Options, RegAllocMod, TargetMod) ->
   ?inc_counter(ra_calls_counter, 1),
   SpillLimit0 = TargetMod:number_of_temporaries(CFG0),
-  {Coloring, _, CFG, MaybeLiveness} =
-    call_allocator_initial(CFG0, SpillLimit0, SpillIndex, Options, RegAllocMod,
-			   TargetMod),
+  {Coloring, _, CFG, Liveness} =
+    call_allocator_initial(CFG0, Liveness0, SpillLimit0, SpillIndex, Options,
+			   RegAllocMod, TargetMod),
   %% The first iteration, the hipe_regalloc_prepass may create new temps, these
   %% should not end up above SpillLimit.
   SpillLimit = TargetMod:number_of_temporaries(CFG),
-  alloc(Coloring, CFG, MaybeLiveness, SpillLimit, SpillIndex, Options,
+  alloc(Coloring, CFG, Liveness, SpillLimit, SpillIndex, Options,
 	RegAllocMod, TargetMod).
 
-alloc(Coloring, CFG0, MaybeLiveness0, SpillLimit, SpillIndex, Options,
+alloc(Coloring, CFG0, Liveness, SpillLimit, SpillIndex, Options,
       RegAllocMod, TargetMod) ->
   ?inc_counter(ra_iteration_counter, 1),
   {CFG, DidSpill} = TargetMod:check_and_rewrite(CFG0, Coloring),
@@ -54,7 +54,6 @@ alloc(Coloring, CFG0, MaybeLiveness0, SpillLimit, SpillIndex, Options,
     false -> %% No new temps, we are done.
       ?add_spills(Options, _NewSpillIndex),
       TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod),
-      Liveness = liveness_force(TargetMod, CFG0, MaybeLiveness0),
       {TempMap2, NewSpillIndex2} =
 	hipe_spillmin:stackalloc(CFG0, Liveness, [], SpillIndex, Options,
 				 TargetMod, TempMap),
@@ -66,37 +65,36 @@ alloc(Coloring, CFG0, MaybeLiveness0, SpillLimit, SpillIndex, Options,
       %%   false ->
       %%     ok
       %% end,
-      {CFG, Coloring2, NewSpillIndex2};
+      {CFG, Liveness, Coloring2, NewSpillIndex2};
     _ ->
       %% Since SpillLimit is used as a low-water-mark
       %% the list of temps not to spill is uninteresting.
-      {NewColoring, _NewSpillIndex, Liveness} =
-	call_allocator(CFG, SpillLimit, SpillIndex, Options, RegAllocMod,
-		       TargetMod),
+      {NewColoring, _NewSpillIndex} =
+	call_allocator(CFG, Liveness, SpillLimit, SpillIndex, Options,
+		       RegAllocMod, TargetMod),
       alloc(NewColoring, CFG, Liveness, SpillLimit, SpillIndex, Options,
 	    RegAllocMod, TargetMod)
   end.
 
-call_allocator_initial(CFG, SpillLimit, SpillIndex, Options, RegAllocMod,
-		       TargetMod) ->
+call_allocator_initial(CFG, Liveness, SpillLimit, SpillIndex, Options,
+		       RegAllocMod, TargetMod) ->
   case proplists:get_bool(ra_prespill, Options) of
     true ->
       hipe_regalloc_prepass:regalloc_initial(
-	RegAllocMod, CFG, SpillIndex, SpillLimit, TargetMod, Options);
+	RegAllocMod, CFG, Liveness, SpillIndex, SpillLimit, TargetMod, Options);
     false ->
-      {C, SI, L} = RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit,
-					TargetMod, Options),
-      {C, SI, CFG, L}
+      {C, SI} = RegAllocMod:regalloc(CFG, Liveness, SpillIndex, SpillLimit,
+				     TargetMod, Options),
+      {C, SI, CFG, Liveness}
   end.
 
-call_allocator(CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
+call_allocator(CFG, Liveness, SpillLimit, SpillIndex, Options, RegAllocMod,
+	       TargetMod) ->
   case proplists:get_bool(ra_prespill, Options) of
     true ->
       hipe_regalloc_prepass:regalloc(
-	RegAllocMod, CFG, SpillIndex, SpillLimit, TargetMod, Options);
+	RegAllocMod, CFG, Liveness, SpillIndex, SpillLimit, TargetMod, Options);
     false ->
-      RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit, TargetMod, Options)
+      RegAllocMod:regalloc(CFG, Liveness, SpillIndex, SpillLimit, TargetMod,
+			   Options)
   end.
-
-liveness_force(TargetMod, CFG, undefined) -> TargetMod:analyze(CFG);
-liveness_force(_TargetMod, _CFG, Defined) -> Defined.
diff --git a/lib/hipe/regalloc/hipe_regalloc_prepass.erl b/lib/hipe/regalloc/hipe_regalloc_prepass.erl
index c2531bc451..75f377fcce 100644
--- a/lib/hipe/regalloc/hipe_regalloc_prepass.erl
+++ b/lib/hipe/regalloc/hipe_regalloc_prepass.erl
@@ -44,7 +44,7 @@
 %%    hipe_regalloc_loop iteration, skipping directly to rewrite without ever
 %%    calling RegAllocMod.
 -module(hipe_regalloc_prepass).
--export([regalloc/6, regalloc_initial/6]).
+-export([regalloc/7, regalloc_initial/7]).
 
 -ifndef(DEBUG).
 -compile(inline).
@@ -135,37 +135,35 @@
 -type temp() :: non_neg_integer().
 -type label() :: non_neg_integer().
 
--spec regalloc(module(), target_cfg(), spillno(), spillno(), module(),
-	       proplists:proplist())
-	      -> {hipe_map(), spillno(), target_liveness()}.
-regalloc(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options) ->
-  Liveness = Target:analyze(CFG),
+-spec regalloc(module(), target_cfg(), target_liveness(), spillno(), spillno(),
+	       module(), proplists:proplist())
+	      -> {hipe_map(), spillno()}.
+regalloc(RegAllocMod, CFG, Liveness, SpillIndex0, SpillLimit, Target,
+	 Options) ->
   {Coloring, SpillIndex, same} =
     regalloc_1(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options,
 	       Liveness),
-  {Coloring, SpillIndex, Liveness}.
+  {Coloring, SpillIndex}.
 
-%% regalloc_initial/6 is allowed to introduce new temporaries, unlike
-%% regalloc/6.
-%% In order for regalloc/6 to never introduce temporaries, regalloc/6 must never
-%% choose to do split allocation unless regalloc_initial/6 does. This is the
+%% 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(), spillno(), spillno(), module(),
-		       proplists:proplist())
+-spec regalloc_initial(module(), target_cfg(), target_liveness(), spillno(),
+		       spillno(), module(), proplists:proplist())
 		      -> {hipe_map(), spillno(), target_cfg(),
-			  undefined | target_liveness()}.
-regalloc_initial(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, Options) ->
-  Liveness0 = Target:analyze(CFG0),
+			  target_liveness()}.
+regalloc_initial(RegAllocMod, CFG0, Liveness0, SpillIndex0, SpillLimit, Target,
+		 Options) ->
   {Coloring, SpillIndex, NewCFG} =
     regalloc_1(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, Options,
 	       Liveness0),
-  %% It's not worth it to add rewriting of the liveness information; just return
-  %% 'undefined' and let it be recomputed when needed.
   {CFG, Liveness} =
     case NewCFG of
       same -> {CFG0, Liveness0};
-      {rewritten, CFG1} -> {CFG1, undefined}
+      {rewritten, CFG1} -> {CFG1, Target:analyze(CFG1)}
     end,
   {Coloring, SpillIndex, CFG, Liveness}.
 
@@ -204,7 +202,7 @@ regalloc_1(RegAllocMod, CFG0, SpillIndex0, SpillLimit, Target, Options,
 	      end,
 	    check_coloring(Coloring, CFG, Target)
 	  end), % Sanity-check
-  ?ASSERT(just_as_good_as(RegAllocMod, CFG, SpillIndex0, SpillLimit,
+  ?ASSERT(just_as_good_as(RegAllocMod, CFG, Liveness, SpillIndex0, SpillLimit,
 			  Target, Options, SpillMap, Coloring, Unused)),
   {Coloring, SpillIndex, NewCFG}.
 
@@ -218,8 +216,8 @@ regalloc_whole(Seen, SpillMap, SpillIndex0, SpillLimit, ScanBBs,
   BBs = transform_whole_cfg(ScanBBs, SubMap),
   SubMod = #cfg{cfg=CFG, bbs=BBs, max_reg=MaxR},
   SubTarget = #?MODULE{target=Target, max_phys=MaxPhys, inv=InvMap, sub=SubMap},
-  {SubColoring, SpillIndex, _} =
-    RegAllocMod:regalloc(SubMod, SpillIndex0, SubSpillLimit, SubTarget,
+  {SubColoring, SpillIndex} =
+    RegAllocMod:regalloc(SubMod, SubMod, SpillIndex0, SubSpillLimit, SubTarget,
 			 Options),
   ?ASSERT(check_coloring(SubColoring, SubMod, SubTarget)),
   {translate_coloring(SubColoring, InvMap), SpillIndex, same}.
@@ -249,9 +247,9 @@ regalloc_partitioned(SpillMap, SpillIndex0, SpillLimit, ScanBBs,
 	  SubMod = #cfg{cfg=CFG, bbs=BBs, max_reg=MaxR, rpostorder=RPost},
 	  SubTarget = #?MODULE{target=Target, max_phys=MaxPhys, inv=InvMap,
 			       sub=SubMap},
-	  {SubColoring, SpillIndex2, _} =
-	    RegAllocMod:regalloc(SubMod, SpillIndex1, SubSpillLimit, SubTarget,
-				 Options),
+	  {SubColoring, SpillIndex2} =
+	    RegAllocMod:regalloc(SubMod, SubMod, SpillIndex1, SubSpillLimit,
+				 SubTarget, Options),
 	  ?ASSERT(check_coloring(SubColoring, SubMod, SubTarget)),
 	  {{translate_coloring(SubColoring, InvMap), Elems}, SpillIndex2}
       end, SpillIndex0, PartBBsRLList),
@@ -885,10 +883,10 @@ unused_unused(Unused, CFG, Target) ->
 %%%%%%%%%%%%%%%%%%%%
 %% Check that no register allocation opportunities were missed due to ?MODULE
 %%
-just_as_good_as(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options,
-		SpillMap, Coloring, Unused) ->
-  {CheckColoring, _, _} = RegAllocMod:regalloc(CFG, SpillIndex0, SpillLimit,
-					       Target, Options),
+just_as_good_as(RegAllocMod, CFG, Liveness, SpillIndex0, SpillLimit, Target,
+		Options, SpillMap, Coloring, Unused) ->
+  {CheckColoring, _} = RegAllocMod:regalloc(CFG, Liveness, SpillIndex0,
+					    SpillLimit, Target, Options),
   Now   = lists:sort([{R,Kind} || {R,{Kind,_}} <- Coloring,
 				  not ordsets:is_element(R, Unused)]),
   Check = lists:sort([{R,Kind} || {R,{Kind,_}} <- CheckColoring,
diff --git a/lib/hipe/sparc/hipe_sparc_ra.erl b/lib/hipe/sparc/hipe_sparc_ra.erl
index 5f955c2058..a567e62e46 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),
+	  hipe_regalloc_loop:ra_fp(CFG0, FPLiveness0, Options,
 				   hipe_coalescing_regalloc,
 				   hipe_sparc_specific_fp);
 	false ->
-	  {CFG0,[],0}
+	  {CFG0,undefined,[],0}
       end,
   %% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG1)),
-  {CFG2, Coloring}
+  GPLiveness1 = hipe_sparc_specific:analyze(CFG1),
+  {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).
diff --git a/lib/hipe/sparc/hipe_sparc_ra_ls.erl b/lib/hipe/sparc/hipe_sparc_ra_ls.erl
index ced9addd31..4d4a870a69 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_ls.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_ls.erl
@@ -21,16 +21,16 @@
 %% Linear Scan register allocator for SPARC
 
 -module(hipe_sparc_ra_ls).
--export([ra/3]).
+-export([ra/4]).
 
-ra(CFG, SpillIndex, Options) ->
+ra(CFG, Liveness, SpillIndex, Options) ->
   SpillLimit = hipe_sparc_specific:number_of_temporaries(CFG),
-  alloc(CFG, SpillIndex, SpillLimit, Options).
+  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(),
@@ -47,8 +47,9 @@ alloc(CFG, SpillIndex, SpillLimit, Options) ->
 			     hipe_sparc_specific, 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,
+	 Target) ->
+  hipe_ls_regalloc:regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex,
+			    DontSpill, Options, Target).
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/x86/hipe_x86_ra.erl b/lib/hipe/x86/hipe_x86_ra.erl
index 3af333ab4b..1a860bebb1 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),
+  {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).
 
 -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,27 @@ 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);
+    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).
 -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);
     false ->
-      {CFG,[],0}
+      {CFG,Liveness,[],0}
   end.
 -endif.
diff --git a/lib/hipe/x86/hipe_x86_ra_ls.erl b/lib/hipe/x86/hipe_x86_ra_ls.erl
index 9f019f9561..be69ebd009 100644
--- a/lib/hipe/x86/hipe_x86_ra_ls.erl
+++ b/lib/hipe/x86/hipe_x86_ra_ls.erl
@@ -35,7 +35,7 @@
 -endif.
 
 -module(?HIPE_X86_RA_LS).
--export([ra/4,ra_fp/3]).
+-export([ra/4,ra_fp/4]).
 -define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation.
 -include("../main/hipe.hrl").
 
@@ -45,7 +45,7 @@ ra(CFG, Liveness, SpillIndex, Options) ->
   ?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) ->
   ?inc_counter(ra_calls_counter,1),
   %% ?inc_counter(ra_caller_saves_counter,count_caller_saves(CFG)),
   SpillIndex = 0,
@@ -55,9 +55,8 @@ ra_fp(CFG, Options, TargetMod) ->
   ?inc_counter(ra_iteration_counter,1),
   %% ?HIPE_X86_PP:pp(Defun),
 
-  {Coloring,NewSpillIndex,Liveness} =
-    regalloc(CFG,
-	     undefined,
+  {Coloring,NewSpillIndex} =
+    regalloc(CFG, Liveness,
 	     TargetMod:allocatable('linearscan'),
 	     [hipe_x86_cfg:start_label(CFG)],
 	     SpillIndex, SpillLimit, Options,
@@ -72,15 +71,14 @@ ra_fp(CFG, Options, TargetMod) ->
   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()],
@@ -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,
+regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options,
 	 Target) ->
-  hipe_ls_regalloc:regalloc(CFG,Liveness,PhysRegs,Entrypoints, SpillIndex,
+  hipe_ls_regalloc:regalloc(CFG, Liveness, PhysRegs, Entrypoints, SpillIndex,
 			    DontSpill, Options, Target).
diff --git a/lib/hipe/x86/hipe_x86_ra_naive.erl b/lib/hipe/x86/hipe_x86_ra_naive.erl
index 27e5af4aee..aeae01e98b 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) ->