hipe: Reuse liveness info for spillmin

For x86, additionally reuse liveness from float LSRA for the GP LSRA.

14 files changed, 95 insertions, 75 deletions

diff --git a/lib/hipe/arm/hipe_arm_ra_ls.erl b/lib/hipe/arm/hipe_arm_ra_ls.erl
index d9a360d00c..7891403fc3 100644
--- a/lib/hipe/arm/hipe_arm_ra_ls.erl
+++ b/lib/hipe/arm/hipe_arm_ra_ls.erl
@@ -31,7 +31,7 @@ ra(Defun, SpillIndex, Options) ->
 
 alloc(Defun, SpillIndex, SpillLimit, Options) ->
   CFG = hipe_arm_cfg:init(Defun),
-  {Coloring, _NewSpillIndex} =
+  {Coloring, _NewSpillIndex, Liveness} =
     regalloc(
       CFG,
       hipe_arm_registers:allocatable_gpr()--
@@ -46,7 +46,7 @@ alloc(Defun, SpillIndex, SpillLimit, Options) ->
       Defun, Coloring, 'linearscan'),
   TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_arm_specific),
   {SpillMap, _NewSpillIndex2} =
-    hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options,
+    hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
 			     hipe_arm_specific, TempMap),
   Coloring2 =
     hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), SpillMap),
diff --git a/lib/hipe/opt/hipe_spillmin.erl b/lib/hipe/opt/hipe_spillmin.erl
index 4eeb1d71db..6bb6980ad5 100644
--- a/lib/hipe/opt/hipe_spillmin.erl
+++ b/lib/hipe/opt/hipe_spillmin.erl
@@ -49,7 +49,7 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 -module(hipe_spillmin).
--export([stackalloc/6, mapmerge/2]).
+-export([stackalloc/6, stackalloc/7, mapmerge/2]).
 
 %%-define(DEBUG, 1).
 -define(HIPE_INSTRUMENT_COMPILER, true).
@@ -69,16 +69,24 @@
 
 -spec stackalloc(#cfg{}, [_], non_neg_integer(),
 		 comp_options(), module(), hipe_temp_map()) ->
-                                {hipe_spill_map(), non_neg_integer()}.
+		    {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).
+
+-spec stackalloc(#cfg{}, _, [_], non_neg_integer(),
+		 comp_options(), module(), hipe_temp_map()) ->
+		    {hipe_spill_map(), non_neg_integer()}.
+
+stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, Target, TempMap) ->
   case proplists:get_bool(spillmin_color, Options) of
     false ->
-      ?option_time(hipe_spillmin_scan:stackalloc(CFG, StackSlots, SpillIndex,
+      ?option_time(hipe_spillmin_scan:stackalloc(CFG, Liveness, StackSlots, SpillIndex,
 						 Options, Target, TempMap),
 		   "Spill minimize, linear scan", Options);
     true ->
-      ?option_time(hipe_spillmin_color:stackalloc(CFG, StackSlots, SpillIndex,
+      ?option_time(hipe_spillmin_color:stackalloc(CFG, Liveness, StackSlots, SpillIndex,
 						  Options, Target, 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 7c23de44b4..9c62fdf11a 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/6]).
+-export([stackalloc/7]).
 
 %%-ifndef(DO_ASSERT).
 %%-define(DO_ASSERT, true).
@@ -66,13 +66,13 @@
 %%  where Location is {spill,M}.
 %% {spill,M} denotes the Mth spilled node
 
--spec stackalloc(#cfg{}, [_], non_neg_integer(),
+-spec stackalloc(#cfg{}, _, [_], non_neg_integer(),
 		 comp_options(), module(), hipe_temp_map()) ->
                                 {hipe_spill_map(), non_neg_integer()}.
 
-stackalloc(CFG, _StackSlots, SpillIndex, _Options, Target, TempMap) ->
+stackalloc(CFG, Live, _StackSlots, SpillIndex, _Options, Target, TempMap) ->
   ?report2("building IG~n", []),
-  {IG, NumNodes} = build_ig(CFG, Target, TempMap),
+  {IG, NumNodes} = build_ig(CFG, Live, Target, TempMap),
   {Cols, MaxColors} = 
     color_heuristic(IG, 0, NumNodes, NumNodes, NumNodes, Target, 1),
   SortedCols = lists:sort(Cols),
@@ -167,8 +167,8 @@ remap_temp_map0(Cols, [_Y|Ys], SpillIndex) ->
 %% Returns {Interference_graph, Number_Of_Nodes}
 %%
 
-build_ig(CFG, Target, TempMap) ->
-  try build_ig0(CFG, Target, TempMap)
+build_ig(CFG, Live, Target, TempMap) ->
+  try build_ig0(CFG, Live, Target, TempMap)
   catch error:Rsn -> exit({regalloc, build_ig, Rsn})
   end.
 
@@ -185,8 +185,7 @@ setup_ets0([X|Xs], Table, N) ->
   ets:insert(Table, {X, N}),
   setup_ets0(Xs, Table, N+1).
 
-build_ig0(CFG, Target, TempMap) ->
-  Live = Target:analyze(CFG),
+build_ig0(CFG, Live, Target, TempMap) ->
   TempMapping = map_spilled_temporaries(TempMap),
   TempMappingTable = setup_ets(TempMapping),
   NumSpilled = length(TempMapping),
diff --git a/lib/hipe/opt/hipe_spillmin_scan.erl b/lib/hipe/opt/hipe_spillmin_scan.erl
index 06b68e1934..53cbc0014b 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/6]).
+-export([stackalloc/7]).
 
 %%-define(DEBUG, 1).
 -define(HIPE_INSTRUMENT_COMPILER, true).
@@ -85,15 +85,12 @@
 %%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
--spec stackalloc(#cfg{}, [_], non_neg_integer(),
+-spec stackalloc(#cfg{}, _, [_], non_neg_integer(),
 		 comp_options(), module(), hipe_temp_map()) ->
                                 {hipe_spill_map(), non_neg_integer()}.
 
-stackalloc(CFG, StackSlots, SpillIndex, Options, Target, TempMap) ->
+stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, Target, TempMap) ->
   ?debug_msg("LinearScan: ~w\n", [erlang:statistics(runtime)]),
-  %% Step 1: Calculate liveness (Call external implementation.)
-  Liveness = liveness(CFG, Target),
-  ?debug_msg("liveness (done)~w\n", [erlang:statistics(runtime)]),
   USIntervals = calculate_intervals(CFG, Liveness, Options,
 				    Target, TempMap),
   %% ?debug_msg("intervals (done) ~w\n", [erlang:statistics(runtime)]),
@@ -538,9 +535,6 @@ extend_interval(Pos, {Beginning, End})
 %% 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-liveness(CFG, Target) ->
-  Target:analyze(CFG).
-
 bb(CFG, L, Target) ->
   Target:bb(CFG, L).
 
diff --git a/lib/hipe/ppc/hipe_ppc_ra_ls.erl b/lib/hipe/ppc/hipe_ppc_ra_ls.erl
index 6e8304467e..58d9f70b1f 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_ls.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_ls.erl
@@ -31,7 +31,7 @@ ra(Defun, SpillIndex, Options) ->
 
 alloc(Defun, SpillIndex, SpillLimit, Options) ->
   CFG = hipe_ppc_cfg:init(Defun),
-  {Coloring, _NewSpillIndex} =
+  {Coloring, _NewSpillIndex, Liveness} =
     regalloc(
       CFG,
       hipe_ppc_registers:allocatable_gpr()--
@@ -46,7 +46,7 @@ alloc(Defun, SpillIndex, SpillLimit, Options) ->
       Defun, Coloring, 'linearscan'),
   TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific),
   {TempMap2,_NewSpillIndex2} =
-    hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options,
+    hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
 			     hipe_ppc_specific, TempMap),
   Coloring2 =
     hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
diff --git a/lib/hipe/regalloc/hipe_coalescing_regalloc.erl b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl
index e2f817d369..bbb2e3ecf0 100644
--- a/lib/hipe/regalloc/hipe_coalescing_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl
@@ -51,13 +51,14 @@
 %%
 %% Returns:
 %%   Coloring    -- A coloring for specified CFG
-%%   SpillIndex0 -- A new spill index
+%%   SpillIndex2 -- A new spill index
 %%-----------------------------------------------------------------------
 
 regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
   %% Build interference graph
   ?debug_msg("Build IG\n", []),
-  IG = hipe_ig:build(CFG, Target),
+  Liveness = Target:analyze(CFG),
+  IG = hipe_ig:build(CFG, Liveness, Target),
   %% io:format("IG: ~p\n", [IG]),
 
   ?debug_msg("Init\n", []),
@@ -94,9 +95,10 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
   %% io:format("color0:~w\nColor1:~w\nNodes:~w\nNodes2:~w\nNum_Temps:~w\n",[Color0,Color1,Node_sets,Node_sets2,Num_Temps]),
 
   ?debug_msg("Build mapping ~p\n", [Node_sets2]),
-  Coloring = build_namelist(Node_sets2, SpillIndex, Alias0, Color1),
+  {Coloring, SpillIndex2} =
+    build_namelist(Node_sets2, SpillIndex, Alias0, Color1),
   ?debug_msg("Coloring ~p\n", [Coloring]),
-  Coloring.
+  {Coloring, SpillIndex2, Liveness}.
 
 %%----------------------------------------------------------------------
 %% Function:    do_coloring
diff --git a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl
index bc6e442236..1a3ea90c05 100644
--- a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl
@@ -82,7 +82,7 @@
 regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
   PhysRegs = Target:allocatable(),
   ?report2("building IG~n", []),
-  {IG, Spill} = build_ig(CFG, Target),
+  {IG, Spill, Live} = build_ig(CFG, Target),
 
   %% check_ig(IG),
   ?report3("graph: ~p~nphysical regs: ~p~n", [list_ig(IG), PhysRegs]),
@@ -102,7 +102,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
   Coloring = [{X, {reg, X}} || X <- NotAllocatable] ++ Cols,
   ?ASSERT(check_coloring(Coloring, IG, Target)),
 
-  {Coloring, NewSpillIndex}.
+  {Coloring, NewSpillIndex, Live}.
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -126,7 +126,7 @@ build_ig0(CFG, Target) ->
 			     empty_ig(NumN), 
 			     empty_spill(NumN),
 			     Target),
-  {normalize_ig(IG), Spill}.
+  {normalize_ig(IG), Spill, Live}.
 
 build_ig_bbs([], _CFG, _Live, IG, Spill, _Target) ->
   {IG, Spill};
diff --git a/lib/hipe/regalloc/hipe_ig.erl b/lib/hipe/regalloc/hipe_ig.erl
index 8fd5d0df1f..47f8f6d08d 100644
--- a/lib/hipe/regalloc/hipe_ig.erl
+++ b/lib/hipe/regalloc/hipe_ig.erl
@@ -28,7 +28,7 @@
 
 -module(hipe_ig).
 
--export([build/2, 
+-export([build/3,
 	 nodes_are_adjacent/3,
 	 node_spill_cost/2,
 	 node_adj_list/2,
@@ -368,10 +368,9 @@ initial_ig(NumTemps, Target) ->
 %%   An interference graph for the given CFG.
 %%----------------------------------------------------------------------
 
--spec build(#cfg{}, atom()) -> #igraph{}.
+-spec build(#cfg{}, Liveness::_, atom()) -> #igraph{}.
 
-build(CFG, Target) ->
-  BBs_in_out_liveness = Target:analyze(CFG),
+build(CFG, BBs_in_out_liveness, Target) ->
   Labels = Target:labels(CFG),
   %% How many temporaries exist?
   NumTemps = Target:number_of_temporaries(CFG),
diff --git a/lib/hipe/regalloc/hipe_ls_regalloc.erl b/lib/hipe/regalloc/hipe_ls_regalloc.erl
index d24b803524..c318927077 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]).
+-export([regalloc/7, regalloc/8]).
 
 %%-define(DEBUG,1).
 -define(HIPE_INSTRUMENT_COMPILER, true).
@@ -96,10 +96,18 @@
 %% @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) ->
   ?debug_msg("LinearScan: ~w\n", [erlang:statistics(runtime)]),
   %%     Step 1: Calculate liveness (Call external implementation.)
-  Liveness = liveness(CFG, Target),
-  ?debug_msg("liveness (done)~w\n", [erlang:statistics(runtime)]),
+  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)]),
@@ -108,10 +116,10 @@ regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
   %% ?debug_msg("Intervals ~w\n", [Intervals]),
   ?debug_msg("No intervals: ~w\n",[length(Intervals)]),
   ?debug_msg("count intervals (done) ~w\n", [erlang:statistics(runtime)]),
-  Allocation = allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target),
+  {Coloring, NewSpillIndex}
+    = allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target),
   ?debug_msg("allocation (done) ~w\n", [erlang:statistics(runtime)]),
-  Allocation.
-
+  {Coloring, NewSpillIndex, Liveness}.
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%                                                                    %%
diff --git a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
index 2ed9ec3b45..67674be14c 100644
--- a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
+++ b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
@@ -78,7 +78,7 @@
 %%
 %% Returns:
 %%   Coloring    -- A coloring for specified CFG
-%%   SpillIndex0 -- A new spill index
+%%   SpillIndex2 -- A new spill index
 %%-----------------------------------------------------------------------
 -ifdef(COMPARE_ITERATED_OPTIMISTIC).
 regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
@@ -86,8 +86,9 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
   ?debug_msg("CFG: ~p\n",[CFG]),
   %% Build interference graph
   ?debug_msg("Build IG\n",[]),
-  IG_O = hipe_ig:build(CFG, Target),
-  IG = hipe_ig:build(CFG, Target),
+  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)]),
   ?debug_msg("IG:\n",[]),
   ?print_adjacent(IG),
@@ -199,9 +200,10 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
   ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]),
 
   ?debug_msg("Build mapping _N ~w\n",[Node_sets2]),
-  Coloring = build_namelist(Node_sets2,SpillIndex,Alias2,Color1),
+  {Coloring,SpillIndex2} =
+    build_namelist(Node_sets2,SpillIndex,Alias2,Color1),
   ?debug_msg("Coloring ~p\n",[Coloring]),
-  SortedColoring = { sort_stack(element(1, Coloring)), element(2, Coloring)},
+  SortedColoring = {sort_stack(Coloring), SpillIndex2},
   ?debug_msg("SortedColoring ~p\n",[SortedColoring]),
   %%Coloring.
   ?debug_msg("----------------------Assign colors _O\n",[]),
@@ -217,14 +219,15 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
   SortedColoring_O = {sort_stack(element(1, Coloring_O)), element(2, Coloring_O)},
   ?debug_msg("SortedColoring_O ~p\n",[SortedColoring_O]),
   sanity_compare(SortedColoring_O, SortedColoring),
-  Coloring.
+  {Coloring,SpillIndex2,Liveness}.
 -else.
 regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
   ?debug_msg("optimistic ~w\n",[Target]),
   ?debug_msg("CFG: ~p\n",[CFG]),
   %% Build interference graph
   ?debug_msg("Build IG\n",[]),
-  IG = hipe_ig:build(CFG, Target),
+  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",[]),
   ?print_adjacent(IG),
@@ -316,9 +319,9 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
   ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]),
 
   ?debug_msg("Build mapping _N ~w\n",[Node_sets2]),
-  Coloring = build_namelist(Node_sets2,SpillIndex,Alias2,Color1),
+  {Coloring, SpillIndex2} = build_namelist(Node_sets2,SpillIndex,Alias2,Color1),
   ?debug_msg("Coloring ~p\n",[Coloring]),
-  Coloring.
+  {Coloring,SpillIndex2,Liveness}.
 -endif.
 
 %%----------------------------------------------------------------------
diff --git a/lib/hipe/regalloc/hipe_regalloc_loop.erl b/lib/hipe/regalloc/hipe_regalloc_loop.erl
index d29615a3a0..fa42cdd0fb 100644
--- a/lib/hipe/regalloc/hipe_regalloc_loop.erl
+++ b/lib/hipe/regalloc/hipe_regalloc_loop.erl
@@ -38,20 +38,19 @@ ra_common(Defun, SpillIndex, Options, RegAllocMod, TargetMod) ->
   ?inc_counter(ra_calls_counter, 1),
   CFG = TargetMod:defun_to_cfg(Defun),
   SpillLimit = TargetMod:number_of_temporaries(CFG),
-  alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod).
+  alloc(Defun, CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod).
 
-alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
+alloc(Defun, CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
   ?inc_counter(ra_iteration_counter, 1),
-  CFG = TargetMod:defun_to_cfg(Defun),
-  {Coloring, _NewSpillIndex} =
-    RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit, TargetMod, Options),
+  {Coloring, _NewSpillIndex, Liveness} =
+    RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit,TargetMod, Options),
   {NewDefun, DidSpill} = TargetMod:check_and_rewrite(Defun, Coloring),
   case DidSpill of
     false -> %% No new temps, we are done.
       ?add_spills(Options, _NewSpillIndex),
       TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod),
-      {TempMap2, NewSpillIndex2} = 
-	hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options, 
+      {TempMap2, NewSpillIndex2} =
+	hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
 				 TargetMod, TempMap),
       Coloring2 = 
 	hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
@@ -63,7 +62,8 @@ alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
       %% end,
       {NewDefun, 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, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod)
+      alloc(NewDefun, NewCFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod)
   end.
diff --git a/lib/hipe/sparc/hipe_sparc_ra_ls.erl b/lib/hipe/sparc/hipe_sparc_ra_ls.erl
index 19e7c92d2f..f2bceb8f2c 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_ls.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_ls.erl
@@ -31,7 +31,7 @@ ra(Defun, SpillIndex, Options) ->
 
 alloc(Defun, SpillIndex, SpillLimit, Options) ->
   CFG = hipe_sparc_cfg:init(Defun),
-  {Coloring, _NewSpillIndex} =
+  {Coloring, _NewSpillIndex, Liveness} =
     regalloc(
       CFG,
       hipe_sparc_registers:allocatable_gpr()--
@@ -46,7 +46,7 @@ alloc(Defun, SpillIndex, SpillLimit, Options) ->
       Defun, Coloring, 'linearscan'),
   TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific),
   {TempMap2,_NewSpillIndex2} =
-    hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options,
+    hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
 			     hipe_sparc_specific, TempMap),
   Coloring2 =
     hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
diff --git a/lib/hipe/x86/hipe_x86_ra.erl b/lib/hipe/x86/hipe_x86_ra.erl
index 2e97b07e5d..3af333ab4b 100644
--- a/lib/hipe/x86/hipe_x86_ra.erl
+++ b/lib/hipe/x86/hipe_x86_ra.erl
@@ -49,7 +49,11 @@ code_size(CFG) ->
 
 ra(CFG0, Options) ->
   %% hipe_x86_cfg:pp(CFG0),
-  {CFG1, Coloring_fp, SpillIndex} = ra_fp(CFG0, Options),
+  {CFG1, Coloring_fp, SpillIndex, Liveness} =
+    case ra_fp(CFG0, Options) of
+      {G, C, I} -> {G, C, I, undefined};
+      {_,_,_,_}=T -> T
+    end,
   %% hipe_x86_cfg:pp(CFG1),
   ?start_ra_instrumentation(Options,
 			    code_size(CFG1),
@@ -63,7 +67,7 @@ ra(CFG0, Options) ->
 	graph_color ->
 	  ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc);
 	linear_scan ->
-	  ?HIPE_X86_RA_LS:ra(CFG1, SpillIndex, Options);
+	  ?HIPE_X86_RA_LS:ra(CFG1, Liveness, SpillIndex, Options);
 	naive ->
 	  ?HIPE_X86_RA_NAIVE:ra(CFG1, Coloring_fp, Options);
         _ ->
diff --git a/lib/hipe/x86/hipe_x86_ra_ls.erl b/lib/hipe/x86/hipe_x86_ra_ls.erl
index 29097f492c..9f019f9561 100644
--- a/lib/hipe/x86/hipe_x86_ra_ls.erl
+++ b/lib/hipe/x86/hipe_x86_ra_ls.erl
@@ -35,15 +35,15 @@
 -endif.
 
 -module(?HIPE_X86_RA_LS).
--export([ra/3,ra_fp/3,regalloc/7]).
+-export([ra/4,ra_fp/3]).
 -define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation.
 -include("../main/hipe.hrl").
 
-ra(CFG, SpillIndex, Options) ->
+ra(CFG, Liveness, SpillIndex, Options) ->
   SpillLimit = ?HIPE_X86_SPECIFIC:number_of_temporaries(
 		 CFG),
   ?inc_counter(bbs_counter, length(hipe_x86_cfg:labels(CFG))),
-  alloc(CFG, SpillIndex, SpillLimit, Options).
+  alloc(CFG, Liveness, SpillIndex, SpillLimit, Options).
 
 ra_fp(CFG, Options, TargetMod) ->
   ?inc_counter(ra_calls_counter,1),
@@ -55,8 +55,9 @@ ra_fp(CFG, Options, TargetMod) ->
   ?inc_counter(ra_iteration_counter,1),
   %% ?HIPE_X86_PP:pp(Defun),
 
-  {Coloring,NewSpillIndex} =
+  {Coloring,NewSpillIndex,Liveness} =
     regalloc(CFG,
+	     undefined,
 	     TargetMod:allocatable('linearscan'),
 	     [hipe_x86_cfg:start_label(CFG)],
 	     SpillIndex, SpillLimit, Options,
@@ -66,19 +67,20 @@ ra_fp(CFG, Options, TargetMod) ->
     TargetMod:check_and_rewrite(CFG, Coloring, 'linearscan'),
   TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod),
   {TempMap2, NewSpillIndex2} =
-    hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options,
+    hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
 			     TargetMod, TempMap),
   Coloring2 =
     hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
   ?add_spills(Options, NewSpillIndex),
-  {NewCFG, Coloring2, NewSpillIndex2}.
+  {NewCFG, Coloring2, NewSpillIndex2, Liveness}.
 
-alloc(CFG, SpillIndex, SpillLimit, Options) ->
+alloc(CFG, Liveness0, SpillIndex, SpillLimit, Options) ->
   ?inc_counter(ra_iteration_counter,1), 
   %% ?HIPE_X86_PP:pp(Defun),	
-  {Coloring, NewSpillIndex} = 
+  {Coloring, NewSpillIndex, Liveness} =
     regalloc(
       CFG,
+      Liveness0,
       ?HIPE_X86_REGISTERS:allocatable()--
       [?HIPE_X86_REGISTERS:temp1(),
        ?HIPE_X86_REGISTERS:temp0()],
@@ -90,8 +92,8 @@ alloc(CFG, SpillIndex, SpillLimit, Options) ->
       CFG, Coloring, 'linearscan'),
   %% ?HIPE_X86_PP:pp(NewDefun),
   TempMap = hipe_temp_map:cols2tuple(Coloring, ?HIPE_X86_SPECIFIC),
-  {TempMap2,NewSpillIndex2} = 
-    hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options,
+  {TempMap2,NewSpillIndex2} =
+    hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
 			     ?HIPE_X86_SPECIFIC, TempMap),
   Coloring2 = 
     hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
@@ -104,6 +106,7 @@ alloc(CFG, SpillIndex, SpillLimit, Options) ->
   ?add_spills(Options, NewSpillIndex),
   {NewCFG, Coloring2}.
 
-regalloc(CFG,PhysRegs,Entrypoints, SpillIndex, DontSpill, Options, Target) ->
-  hipe_ls_regalloc:regalloc(CFG,PhysRegs,Entrypoints, SpillIndex, 
+regalloc(CFG,Liveness,PhysRegs,Entrypoints, SpillIndex, DontSpill, Options,
+	 Target) ->
+  hipe_ls_regalloc:regalloc(CFG,Liveness,PhysRegs,Entrypoints, SpillIndex,
 			    DontSpill, Options, Target).