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.

3 files changed, 38 insertions, 40 deletions

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) ->