hipe_sparc: Minimise CFG<->linear conversions

Now, there will only ever be a single Linear->CFG conversion, just after
lowering from RTL, and only ever a single CFG->Linear conversion, just
before the finalise pass. Both of these now happen in hipe_sparc_main.

12 files changed, 102 insertions, 89 deletions

diff --git a/lib/hipe/flow/cfg.inc b/lib/hipe/flow/cfg.inc
index 97f6064822..cb5f397f64 100644
--- a/lib/hipe/flow/cfg.inc
+++ b/lib/hipe/flow/cfg.inc
@@ -91,6 +91,7 @@
 -define(BREADTH_ORDER,true). % for linear scan
 -define(PARAMS_NEEDED,true).
 -define(START_LABEL_UPDATE_NEEDED,true).
+-define(MAP_FOLD_NEEDED,true).
 -endif.
 
 %%=====================================================================
diff --git a/lib/hipe/regalloc/hipe_sparc_specific.erl b/lib/hipe/regalloc/hipe_sparc_specific.erl
index 8d34604f84..29d0908caf 100644
--- a/lib/hipe/regalloc/hipe_sparc_specific.erl
+++ b/lib/hipe/regalloc/hipe_sparc_specific.erl
@@ -53,11 +53,11 @@
 -export([defun_to_cfg/1,
 	 check_and_rewrite/2]).
 
-defun_to_cfg(Defun) ->
-  hipe_sparc_cfg:init(Defun).
+defun_to_cfg(AlreadyACFG) ->
+  AlreadyACFG.
 
-check_and_rewrite(Defun, Coloring) ->
-  hipe_sparc_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal').
+check_and_rewrite(CFG, Coloring) ->
+  hipe_sparc_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal').
 
 reverse_postorder(CFG) ->
   hipe_sparc_cfg:reverse_postorder(CFG).
diff --git a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
index 2edd3cb47e..08c2541b41 100644
--- a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
+++ b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
@@ -53,11 +53,11 @@
 -export([defun_to_cfg/1,
 	 check_and_rewrite/2]).
 
-defun_to_cfg(Defun) ->
-  hipe_sparc_cfg:init(Defun).
+defun_to_cfg(AlreadyACFG) ->
+  AlreadyACFG.
 
-check_and_rewrite(Defun, Coloring) ->
-  hipe_sparc_ra_postconditions_fp:check_and_rewrite(Defun, Coloring).
+check_and_rewrite(CFG, Coloring) ->
+  hipe_sparc_ra_postconditions_fp:check_and_rewrite(CFG, Coloring).
 
 reverse_postorder(CFG) ->
   hipe_sparc_cfg:reverse_postorder(CFG).
diff --git a/lib/hipe/sparc/hipe_sparc_cfg.erl b/lib/hipe/sparc/hipe_sparc_cfg.erl
index 0b2c77f27b..957c8a0d24 100644
--- a/lib/hipe/sparc/hipe_sparc_cfg.erl
+++ b/lib/hipe/sparc/hipe_sparc_cfg.erl
@@ -24,6 +24,7 @@
 -export([init/1,
          labels/1, start_label/1,
          succ/2,
+         map_bbs/2, fold_bbs/3,
          bb/2, bb_add/3]).
 -export([postorder/1, reverse_postorder/1]).
 -export([linearise/1]).
diff --git a/lib/hipe/sparc/hipe_sparc_frame.erl b/lib/hipe/sparc/hipe_sparc_frame.erl
index a42c1983f4..37f29e660a 100644
--- a/lib/hipe/sparc/hipe_sparc_frame.erl
+++ b/lib/hipe/sparc/hipe_sparc_frame.erl
@@ -25,16 +25,14 @@
 -include("hipe_sparc.hrl").
 -include("../rtl/hipe_literals.hrl").
 
-frame(Defun) ->
-  Formals = fix_formals(hipe_sparc:defun_formals(Defun)),
-  Temps0 = all_temps(hipe_sparc:defun_code(Defun), Formals),
-  MinFrame = defun_minframe(Defun),
+frame(CFG) ->
+  Formals = fix_formals(hipe_sparc_cfg:params(CFG)),
+  Temps0 = all_temps(CFG, Formals),
+  MinFrame = defun_minframe(CFG),
   Temps = ensure_minframe(MinFrame, Temps0),
-  ClobbersRA = clobbers_ra(hipe_sparc:defun_code(Defun)),
-  CFG0 = hipe_sparc_cfg:init(Defun),
-  Liveness = hipe_sparc_liveness_all:analyse(CFG0),
-  CFG1 = do_body(CFG0, Liveness, Formals, Temps, ClobbersRA),
-  hipe_sparc_cfg:linearise(CFG1).
+  ClobbersRA = clobbers_ra(CFG),
+  Liveness = hipe_sparc_liveness_all:analyse(CFG),
+  do_body(CFG, Liveness, Formals, Temps, ClobbersRA).
 
 fix_formals(Formals) ->
   fix_formals(hipe_sparc_registers:nr_args(), Formals).
@@ -550,29 +548,41 @@ temp_is_pseudo(Temp) ->
 %%% Detect if a Defun's body clobbers RA.
 %%%
 
-clobbers_ra(Insns) ->
-  case Insns of
-    [#pseudo_call{}|_] -> true;
-    %% moves to RA cannot occur yet
-    [_|Rest] -> clobbers_ra(Rest);
-    [] -> false
+clobbers_ra(CFG) ->
+  any_insn(fun(#pseudo_call{}) -> true;
+	      (_) -> false
+	   end, CFG).
+
+any_insn(Pred, CFG) ->
+  %% Abuse fold to do an efficient "any"-operation using nonlocal control flow
+  FoundSatisfying = make_ref(),
+  try fold_insns(fun (I, _) ->
+		     case Pred(I) of
+		       true -> throw(FoundSatisfying);
+		       false -> false
+		     end
+		 end, false, CFG)
+  of _ -> false
+  catch FoundSatisfying -> true
   end.
 
 %%%
 %%% Build the set of all temps used in a Defun's body.
 %%%
 
-all_temps(Code, Formals) ->
-  S0 = find_temps(Code, tset_empty()),
+all_temps(CFG, Formals) ->
+  S0 = fold_insns(fun find_temps/2, tset_empty(), CFG),
   S1 = tset_del_list(S0, Formals),
   tset_filter(S1, fun(T) -> temp_is_pseudo(T) end).
 
-find_temps([I|Insns], S0) ->
+find_temps(I, S0) ->
   S1 = tset_add_list(S0, hipe_sparc_defuse:insn_def_all(I)),
-  S2 = tset_add_list(S1, hipe_sparc_defuse:insn_use_all(I)),
-  find_temps(Insns, S2);
-find_temps([], S) ->
-  S.
+  tset_add_list(S1, hipe_sparc_defuse:insn_use_all(I)).
+
+fold_insns(Fun, InitAcc, CFG) ->
+  hipe_sparc_cfg:fold_bbs(
+    fun(_, BB, Acc0) -> lists:foldl(Fun, Acc0, hipe_bb:code(BB)) end,
+    InitAcc, CFG).
 
 tset_empty() ->
   gb_sets:new().
@@ -601,16 +611,11 @@ tset_to_list(S) ->
 %%% in the middle of a tailcall.
 %%%
 
-defun_minframe(Defun) ->
-  MaxTailArity = body_mta(hipe_sparc:defun_code(Defun), 0),
-  MyArity = length(fix_formals(hipe_sparc:defun_formals(Defun))),
+defun_minframe(CFG) ->
+  MaxTailArity = fold_insns(fun insn_mta/2, 0, CFG),
+  MyArity = length(fix_formals(hipe_sparc_cfg:params(CFG))),
   erlang:max(MaxTailArity - MyArity, 0).
 
-body_mta([I|Code], MTA) ->
-  body_mta(Code, insn_mta(I, MTA));
-body_mta([], MTA) ->
-  MTA.
-
 insn_mta(I, MTA) ->
   case I of
     #pseudo_tailcall{arity=Arity} ->
diff --git a/lib/hipe/sparc/hipe_sparc_main.erl b/lib/hipe/sparc/hipe_sparc_main.erl
index c16751c7bd..8e9c560bb2 100644
--- a/lib/hipe/sparc/hipe_sparc_main.erl
+++ b/lib/hipe/sparc/hipe_sparc_main.erl
@@ -24,12 +24,14 @@
 
 rtl_to_sparc(MFA, RTL, Options) ->
   Defun1 = hipe_rtl_to_sparc:translate(RTL),
+  CFG1 = hipe_sparc_cfg:init(Defun1),
   %% io:format("~w: after translate\n", [?MODULE]),
   %% hipe_sparc_pp:pp(Defun1),
-  Defun2 = hipe_sparc_ra:ra(Defun1, Options),
+  CFG2 = hipe_sparc_ra:ra(CFG1, Options),
   %% io:format("~w: after regalloc\n", [?MODULE]),
-  %% hipe_sparc_pp:pp(Defun2),
-  Defun3 = hipe_sparc_frame:frame(Defun2),
+  %% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG2)),
+  CFG3 = hipe_sparc_frame:frame(CFG2),
+  Defun3 = hipe_sparc_cfg:linearise(CFG3),
   %% io:format("~w: after frame\n", [?MODULE]),
   %% hipe_sparc_pp:pp(Defun3),
   Defun4 = hipe_sparc_finalise:finalise(Defun3),
diff --git a/lib/hipe/sparc/hipe_sparc_ra.erl b/lib/hipe/sparc/hipe_sparc_ra.erl
index afea8c9b4c..5f955c2058 100644
--- a/lib/hipe/sparc/hipe_sparc_ra.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra.erl
@@ -22,36 +22,36 @@
 -module(hipe_sparc_ra).
 -export([ra/2]).
 
-ra(Defun0, Options) ->
-  %% hipe_sparc_pp:pp(Defun0),
-  {Defun1, Coloring_fp, SpillIndex}
+ra(CFG0, Options) ->
+  %% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG0)),
+  {CFG1, Coloring_fp, SpillIndex}
     = case proplists:get_bool(inline_fp, Options) of
 	true ->
-	  hipe_regalloc_loop:ra_fp(Defun0, Options,
+	  hipe_regalloc_loop:ra_fp(CFG0, Options,
 				   hipe_coalescing_regalloc,
 				   hipe_sparc_specific_fp);
 	false ->
-	  {Defun0,[],0}
+	  {CFG0,[],0}
       end,
-  %% hipe_sparc_pp:pp(Defun1),
-  {Defun2, Coloring}
+  %% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG1)),
+  {CFG2, Coloring}
     = case proplists:get_value(regalloc, Options, coalescing) of
 	coalescing ->
-	  ra(Defun1, SpillIndex, Options, hipe_coalescing_regalloc);
+	  ra(CFG1, SpillIndex, Options, hipe_coalescing_regalloc);
 	optimistic ->
-	  ra(Defun1, SpillIndex, Options, hipe_optimistic_regalloc);
+	  ra(CFG1, SpillIndex, Options, hipe_optimistic_regalloc);
 	graph_color ->
-	  ra(Defun1, SpillIndex, Options, hipe_graph_coloring_regalloc);
+	  ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc);
 	linear_scan ->
-	  hipe_sparc_ra_ls:ra(Defun1, SpillIndex, Options);
+	  hipe_sparc_ra_ls:ra(CFG1, SpillIndex, Options);
 	naive ->
-	  hipe_sparc_ra_naive:ra(Defun1, Coloring_fp, Options);
+	  hipe_sparc_ra_naive:ra(CFG1, Coloring_fp, Options);
         _ ->
 	  exit({unknown_regalloc_compiler_option,
 		proplists:get_value(regalloc,Options)})
       end,
-  %% hipe_sparc_pp:pp(Defun2),
-  hipe_sparc_ra_finalise:finalise(Defun2, Coloring, Coloring_fp).
+  %% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG2)),
+  hipe_sparc_ra_finalise:finalise(CFG2, Coloring, Coloring_fp).
 
-ra(Defun, SpillIndex, Options, RegAllocMod) ->
-  hipe_regalloc_loop:ra(Defun, SpillIndex, Options, RegAllocMod, hipe_sparc_specific).
+ra(CFG, SpillIndex, Options, RegAllocMod) ->
+  hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, hipe_sparc_specific).
diff --git a/lib/hipe/sparc/hipe_sparc_ra_finalise.erl b/lib/hipe/sparc/hipe_sparc_ra_finalise.erl
index dc1e69c101..5d6056071c 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_finalise.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_finalise.erl
@@ -23,13 +23,14 @@
 -export([finalise/3]).
 -include("hipe_sparc.hrl").
 
-finalise(Defun, TempMap, FPMap0) ->
-  Code = hipe_sparc:defun_code(Defun),
-  {_, SpillLimit} = hipe_sparc:defun_var_range(Defun),
+finalise(CFG, TempMap, FPMap0) ->
+  {_, SpillLimit} = hipe_gensym:var_range(sparc),
   Map = mk_ra_map(TempMap, SpillLimit),
   FPMap1 = mk_ra_map_fp(FPMap0, SpillLimit),
-  NewCode = ra_code(Code, Map, FPMap1, []),
-  Defun#defun{code=NewCode}.
+  hipe_sparc_cfg:map_bbs(fun(_Lbl, BB) -> ra_bb(BB, Map, FPMap1) end, CFG).
+
+ra_bb(BB, Map, FpMap) ->
+  hipe_bb:code_update(BB, ra_code(hipe_bb:code(BB), Map, FpMap, [])).
 
 ra_code([I|Insns], Map, FPMap, Accum) ->
   ra_code(Insns, Map, FPMap, [ra_insn(I, Map, FPMap) | Accum]);
diff --git a/lib/hipe/sparc/hipe_sparc_ra_ls.erl b/lib/hipe/sparc/hipe_sparc_ra_ls.erl
index f2bceb8f2c..ced9addd31 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_ls.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_ls.erl
@@ -23,14 +23,11 @@
 -module(hipe_sparc_ra_ls).
 -export([ra/3]).
 
-ra(Defun, SpillIndex, Options) ->
-  NewDefun = Defun, %% hipe_${ARCH}_ra_rename:rename(Defun,Options),
-  CFG = hipe_sparc_cfg:init(NewDefun),
+ra(CFG, SpillIndex, Options) ->
   SpillLimit = hipe_sparc_specific:number_of_temporaries(CFG),
-  alloc(NewDefun, SpillIndex, SpillLimit, Options).
+  alloc(CFG, SpillIndex, SpillLimit, Options).
 
-alloc(Defun, SpillIndex, SpillLimit, Options) ->
-  CFG = hipe_sparc_cfg:init(Defun),
+alloc(CFG, SpillIndex, SpillLimit, Options) ->
   {Coloring, _NewSpillIndex, Liveness} =
     regalloc(
       CFG,
@@ -41,16 +38,16 @@ alloc(Defun, SpillIndex, SpillLimit, Options) ->
       [hipe_sparc_cfg:start_label(CFG)],
       SpillIndex, SpillLimit, Options,
       hipe_sparc_specific),
-  {NewDefun, _DidSpill} =
+  {NewCFG, _DidSpill} =
     hipe_sparc_ra_postconditions:check_and_rewrite(
-      Defun, Coloring, 'linearscan'),
+      CFG, Coloring, 'linearscan'),
   TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific),
   {TempMap2,_NewSpillIndex2} =
     hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
 			     hipe_sparc_specific, TempMap),
   Coloring2 =
     hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
-  {NewDefun, Coloring2}.
+  {NewCFG, Coloring2}.
 
 regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
   hipe_ls_regalloc:regalloc(
diff --git a/lib/hipe/sparc/hipe_sparc_ra_naive.erl b/lib/hipe/sparc/hipe_sparc_ra_naive.erl
index b6c33dec6c..f621d94553 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_naive.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_naive.erl
@@ -24,7 +24,7 @@
 
 -include("hipe_sparc.hrl").
 
-ra(Defun, _Coloring_fp, _Options) ->	% -> {Defun, Coloring}
-  {NewDefun,_DidSpill} =
-    hipe_sparc_ra_postconditions:check_and_rewrite2(Defun, [], 'naive'),
-  {NewDefun, []}.
+ra(CFG, _Coloring_fp, _Options) ->	% -> {CFG, Coloring}
+  {NewCFG,_DidSpill} =
+    hipe_sparc_ra_postconditions:check_and_rewrite2(CFG, [], 'naive'),
+  {NewCFG, []}.
diff --git a/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl b/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl
index ab31b3c8d9..0336a6c59f 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl
@@ -25,17 +25,13 @@
 
 -include("hipe_sparc.hrl").
 
-check_and_rewrite(Defun, Coloring, Allocator) ->
+check_and_rewrite(CFG, Coloring, Allocator) ->
   TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific),
-  check_and_rewrite2(Defun, TempMap, Allocator).
+  check_and_rewrite2(CFG, TempMap, Allocator).
 
-check_and_rewrite2(Defun, TempMap, Allocator) ->
+check_and_rewrite2(CFG, TempMap, Allocator) ->
   Strategy = strategy(Allocator),
-  #defun{code=Code0} = Defun,
-  {Code1,DidSpill} = do_insns(Code0, TempMap, Strategy, [], false),
-  VarRange = {0, hipe_gensym:get_var(sparc)},
-  {Defun#defun{code=Code1, var_range=VarRange},
-   DidSpill}.
+  do_bbs(hipe_sparc_cfg:labels(CFG), TempMap, Strategy, CFG, false).
 
 strategy(Allocator) ->
   case Allocator of
@@ -44,6 +40,13 @@ strategy(Allocator) ->
     'naive' -> 'fixed'
   end.
 
+do_bbs([], _, _, CFG, DidSpill) -> {CFG, DidSpill};
+do_bbs([Lbl|Lbls], TempMap, Strategy, CFG0, DidSpill0) ->
+  Code0 = hipe_bb:code(BB = hipe_sparc_cfg:bb(CFG0, Lbl)),
+  {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0),
+  CFG = hipe_sparc_cfg:bb_add(CFG0, Lbl, hipe_bb:code_update(BB, Code)),
+  do_bbs(Lbls, TempMap, Strategy, CFG, DidSpill).
+
 do_insns([I|Insns], TempMap, Strategy, Accum, DidSpill0) ->
   {NewIs, DidSpill1} = do_insn(I, TempMap, Strategy),
   do_insns(Insns, TempMap, Strategy, lists:reverse(NewIs, Accum), DidSpill0 or DidSpill1);
diff --git a/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl b/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl
index d893ac26e9..d3e1d8cf93 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl
@@ -25,13 +25,16 @@
 
 -include("hipe_sparc.hrl").
 
-check_and_rewrite(Defun, Coloring) ->
+check_and_rewrite(CFG, Coloring) ->
   TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific_fp),
-  #defun{code=Code0} = Defun,
-  {Code1,DidSpill} = do_insns(Code0, TempMap, [], false),
-  VarRange = {0, hipe_gensym:get_var(sparc)},
-  {Defun#defun{code=Code1, var_range=VarRange},
-   DidSpill}.
+  do_bbs(hipe_sparc_cfg:labels(CFG), TempMap, CFG, false).
+
+do_bbs([], _TempMap, CFG, DidSpill) -> {CFG, DidSpill};
+do_bbs([Lbl|Lbls], TempMap, CFG0, DidSpill0) ->
+  Code0 = hipe_bb:code(BB = hipe_sparc_cfg:bb(CFG0, Lbl)),
+  {Code, DidSpill} = do_insns(Code0, TempMap, [], DidSpill0),
+  CFG = hipe_sparc_cfg:bb_add(CFG0, Lbl, hipe_bb:code_update(BB, Code)),
+  do_bbs(Lbls, TempMap, CFG, DidSpill).
 
 do_insns([I|Insns], TempMap, Accum, DidSpill0) ->
   {NewIs, DidSpill1} = do_insn(I, TempMap),