hipe_x86: Minimise CFG<->linear conversions

Most x86 passes were either linearise(pass(to_cfg(Code))) or trivially
rewritable to process a CFG. This saves a great deal of time and memory
churn when compiling large programs.

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_x86_main.

17 files changed, 216 insertions, 222 deletions

diff --git a/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl b/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl
index 8483d2d0d5..bbf9170bc3 100644
--- a/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl
+++ b/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl
@@ -29,17 +29,21 @@
 -define(count_temp(T), ?cons_counter(counter_mfa_mem_temps, T)).
 
 
-check_and_rewrite(AMD64Defun, Coloring) ->
-  check_and_rewrite(AMD64Defun, Coloring, 'normal').
+check_and_rewrite(AMD64CFG, Coloring) ->
+  check_and_rewrite(AMD64CFG, Coloring, 'normal').
 
-check_and_rewrite(AMD64Defun, Coloring, Strategy) ->
+check_and_rewrite(AMD64CFG, Coloring, Strategy) ->
   %%io:format("Converting\n"),
   TempMap = hipe_temp_map:cols2tuple(Coloring,hipe_amd64_specific_sse2),
   %%io:format("Rewriting\n"),
-  #defun{code=Code0} = AMD64Defun,
-  {Code1, DidSpill} = do_insns(Code0, TempMap, Strategy, [], false),
-  {AMD64Defun#defun{code=Code1, var_range={0, hipe_gensym:get_var(x86)}}, 
-   DidSpill}.
+  do_bbs(hipe_x86_cfg:labels(AMD64CFG), TempMap, Strategy, AMD64CFG, false).
+
+do_bbs([], _, _, CFG, DidSpill) -> {CFG, DidSpill};
+do_bbs([Lbl|Lbls], TempMap, Strategy, CFG0, DidSpill0) ->
+  Code0 = hipe_bb:code(BB = hipe_x86_cfg:bb(CFG0, Lbl)),
+  {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0),
+  CFG = hipe_x86_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),
@@ -110,74 +114,27 @@ is_float_temp(#x86_mem{}) -> false.
 %%% Check if an operand denotes a memory cell (mem or pseudo).
 
 is_mem_opnd(Opnd, TempMap) ->
-  R =
-    case Opnd of
-      #x86_mem{} -> true;
-      #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 ->
-		    ?count_temp(Reg),
-		    true;
-		  false -> false
-		end;
-	      _ -> false
-	    end;
-	  false -> true
-	end;
-      _ -> false
-    end,
-  %% io:format("Op ~w mem: ~w\n",[Opnd,R]),
-  R.
-
-%%% Check if an operand is a spilled Temp.
-
-%%src_is_spilled(Src, TempMap) ->
-%%  case hipe_x86:is_temp(Src) of
-%%    true ->
-%%      Reg = hipe_x86:temp_reg(Src),
-%%      case hipe_x86:temp_is_allocatable(Src) of
-%%	true -> 
-%%	  case tuple_size(TempMap) > Reg of 
-%%	    true ->
-%%	      case hipe_temp_map:is_spilled(Reg, TempMap) of
-%%		true ->
-%%		  ?count_temp(Reg),
-%%		  true;
-%%		false ->
-%%		  false
-%%	      end;
-%%	    false ->
-%%	      false
-%%	  end;
-%%	false -> true
-%%      end;
-%%    false -> false
-%%  end.
-
-%% 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 
-%%  	true ->
-%%  	  case hipe_temp_map:is_spilled(Reg, TempMap) of
-%%  	    true ->
-%%  	      ?count_temp(Reg),
-%%  	      true;
-%%  	    false ->
-%%  	      false
-%%  	  end;
-%%  	false ->
-%%  	  false
-%%       end;
-%%     false -> true
-%%   end.
+  case Opnd of
+    #x86_mem{} -> true;
+    #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 ->
+		  ?count_temp(Reg),
+		  true;
+		false -> false
+	      end;
+	    _ -> false
+	  end;
+	false -> true
+      end;
+    _ -> false
+  end.
 
 %%% Make Reg a clone of Dst (attach Dst's type to Reg).
 
diff --git a/lib/hipe/amd64/hipe_amd64_sse2.erl b/lib/hipe/amd64/hipe_amd64_sse2.erl
index df78941be5..ea6b6cb9ba 100644
--- a/lib/hipe/amd64/hipe_amd64_sse2.erl
+++ b/lib/hipe/amd64/hipe_amd64_sse2.erl
@@ -30,9 +30,12 @@
 
 %%----------------------------------------------------------------------
 
-map(Defun = #defun{code=Code0}) ->
-  Code1 = do_insns(Code0, []),
-  Defun#defun{code=Code1}.
+map(CFG) ->
+  hipe_x86_cfg:map_bbs(fun do_bb/2, CFG).
+
+do_bb(_Lbl, BB) ->
+  Code = do_insns(hipe_bb:code(BB), []),
+  hipe_bb:code_update(BB, Code).
 
 do_insns([I|Insns], Accum) ->
   NewIs = do_insn(I),
diff --git a/lib/hipe/flow/cfg.inc b/lib/hipe/flow/cfg.inc
index a18bfbc526..97f6064822 100644
--- a/lib/hipe/flow/cfg.inc
+++ b/lib/hipe/flow/cfg.inc
@@ -32,6 +32,8 @@
 %%  bb(CFG, Label) - returns the basic block named 'Label' from the CFG.
 %%  bb_add(CFG, Label, NewBB) - makes NewBB the basic block associated
 %%       with Label.
+%%  map_bbs(Fun, CFG) - map over all code without changing control flow.
+%%  fold_bbs(Fun, Acc, CFG) - fold over the basic blocks in a CFG.
 %%  succ(Map, Label) - returns a list of successors of basic block 'Label'.
 %%  pred(Map, Label) - returns the predecessors of basic block 'Label'.
 %%  fallthrough(CFG, Label) - returns fall-through successor of basic 
@@ -307,11 +309,7 @@ redirect_phis([I|Rest], OldPred, NewPred, Acc) ->
 %% @doc  Adds a new basic block to a CFG (or updates an existing block).
 bb_add(CFG, Label, NewBB) ->
   %% Asserting that the NewBB is a legal basic block
-  Last = hipe_bb:last(NewBB),
-  case is_branch(Last) of
-    true  -> ok;
-    false -> throw({?MODULE, {"Basic block ends without branch", Last}})
-  end,
+  Last = assert_bb(NewBB),
   %% The order of the elements from branch_successors/1 is
   %% significant. It determines the basic block order when the CFG is
   %% converted to linear form. That order may have been tuned for
@@ -339,6 +337,48 @@ bb_add(CFG, Label, NewBB) ->
 		    HT2, OldSucc -- Succ),
   CFG#cfg{table = HT3}.
 
+-ifdef(MAP_FOLD_NEEDED).
+-spec map_bbs(fun((cfg_lbl(), hipe_bb:bb()) -> hipe_bb:bb()), cfg()) -> cfg().
+%% @doc  Map over the code in a CFG without changing any control flow.
+map_bbs(Fun, CFG = #cfg{table=HT0}) ->
+    HT = gb_trees:map(
+	   fun(Lbl, {OldBB, OldSucc, OldPred}) ->
+		   NewBB = Fun(Lbl, OldBB),
+		   %% Assert preconditions
+		   NewLast = assert_bb(NewBB),
+		   OldSucc = remove_duplicates(branch_successors(NewLast)),
+		   {NewBB, OldSucc, OldPred}
+	   end, HT0),
+    CFG#cfg{table=HT}.
+
+-spec fold_bbs(fun((cfg_lbl(), hipe_bb:bb(), Acc) -> Acc), Acc, cfg()) -> Acc.
+%% @doc  Fold over the basic blocks in a CFG in unspecified order.
+fold_bbs(Fun, InitAcc, #cfg{table=HT}) ->
+    gb_trees_fold(fun(Lbl, {BB, _, _}, Acc) -> Fun(Lbl, BB, Acc) end,
+		  InitAcc, HT).
+
+gb_trees_fold(Fun, InitAcc, Tree) ->
+    gb_trees_fold_1(Fun, InitAcc, gb_trees:iterator(Tree)).
+
+gb_trees_fold_1(Fun, InitAcc, Iter0) ->
+    case gb_trees:next(Iter0) of
+	none -> InitAcc;
+	{Key, Value, Iter} ->
+	    gb_trees_fold_1(Fun, Fun(Key, Value, InitAcc), Iter)
+    end.
+-endif. % MAP_FOLD_NEEDED
+
+assert_bb(BB) ->
+    assert_bb_is(hipe_bb:code(BB)).
+
+assert_bb_is([Last]) ->
+    true = is_branch(Last),
+    Last;
+assert_bb_is([I|Is]) ->
+    false = is_branch(I),
+    false = is_label(I),
+    assert_bb_is(Is).
+
 remove_pred(HT, FromL, PredL) ->
   case gb_trees:lookup(FromL, HT) of
     {value, {Block, Succ, Preds}} ->
diff --git a/lib/hipe/flow/hipe_bb.erl b/lib/hipe/flow/hipe_bb.erl
index 2da3a6dc99..08f5e0a0cb 100644
--- a/lib/hipe/flow/hipe_bb.erl
+++ b/lib/hipe/flow/hipe_bb.erl
@@ -41,6 +41,8 @@
 
 -include("hipe_bb.hrl").
 
+-export_type([bb/0]).
+
 %%
 %% Constructs a basic block.
 %% Returns a basic block: {bb, Code}
diff --git a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
index 8766712ecd..2e5804337d 100644
--- a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
+++ b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
@@ -63,15 +63,15 @@
 
 %%----------------------------------------------------------------------------
 
-defun_to_cfg(Defun) ->
-  hipe_x86_cfg:init(Defun).
+defun_to_cfg(AlreadyACFG) ->
+  AlreadyACFG.
 
-check_and_rewrite(Defun, Coloring) ->
-  hipe_amd64_ra_sse2_postconditions:check_and_rewrite(Defun, Coloring).
+check_and_rewrite(CFG, Coloring) ->
+  hipe_amd64_ra_sse2_postconditions:check_and_rewrite(CFG, Coloring).
 
-check_and_rewrite(Defun, Coloring, Strategy) ->
+check_and_rewrite(CFG, Coloring, Strategy) ->
   hipe_amd64_ra_sse2_postconditions:check_and_rewrite(
-    Defun, Coloring, Strategy).
+    CFG, Coloring, Strategy).
 
 reverse_postorder(CFG) ->
   hipe_x86_cfg:reverse_postorder(CFG).
diff --git a/lib/hipe/regalloc/hipe_x86_specific.erl b/lib/hipe/regalloc/hipe_x86_specific.erl
index 4edf8674b7..f1007c95ed 100644
--- a/lib/hipe/regalloc/hipe_x86_specific.erl
+++ b/lib/hipe/regalloc/hipe_x86_specific.erl
@@ -68,11 +68,11 @@
 -export([defun_to_cfg/1,
 	 check_and_rewrite/2]).
 
-defun_to_cfg(Defun) ->
-  hipe_x86_cfg:init(Defun).
+defun_to_cfg(AlreadyACFG) ->
+  AlreadyACFG.
 
-check_and_rewrite(Defun, Coloring) ->
-  ?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite(Defun, Coloring, 'normal').
+check_and_rewrite(CFG, Coloring) ->
+  ?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite(CFG, Coloring, 'normal').
 
 reverse_postorder(CFG) ->
   hipe_x86_cfg:reverse_postorder(CFG).
diff --git a/lib/hipe/regalloc/hipe_x86_specific_x87.erl b/lib/hipe/regalloc/hipe_x86_specific_x87.erl
index ff5d1b9c8b..0c022d5a27 100644
--- a/lib/hipe/regalloc/hipe_x86_specific_x87.erl
+++ b/lib/hipe/regalloc/hipe_x86_specific_x87.erl
@@ -64,8 +64,8 @@
 -export([check_and_rewrite/3]).
 
 %% Rewrite happens in hipe_x86_ra_finalise:finalise/4
-check_and_rewrite(Defun, _Coloring, 'linearscan') ->
-  {Defun, false}.
+check_and_rewrite(CFG, _Coloring, 'linearscan') ->
+  {CFG, false}.
 
 breadthorder(CFG) ->
   hipe_x86_cfg:breadthorder(CFG).
diff --git a/lib/hipe/x86/hipe_x86_cfg.erl b/lib/hipe/x86/hipe_x86_cfg.erl
index ab40b68580..b9f9c711f3 100644
--- a/lib/hipe/x86/hipe_x86_cfg.erl
+++ b/lib/hipe/x86/hipe_x86_cfg.erl
@@ -24,7 +24,7 @@
 -export([init/1,
          labels/1, start_label/1,
          succ/2, pred/2,
-         bb/2, bb_add/3]).
+         bb/2, bb_add/3, map_bbs/2, fold_bbs/3]).
 -export([postorder/1, reverse_postorder/1]).
 -export([linearise/1, params/1, arity/1, redirect_jmp/3]).
 
@@ -33,6 +33,7 @@
 -define(BREADTH_ORDER,true).
 -define(PARAMS_NEEDED,true).
 -define(START_LABEL_UPDATE_NEEDED,true).
+-define(MAP_FOLD_NEEDED,true).
 
 -include("hipe_x86.hrl").
 -include("../flow/cfg.hrl").
@@ -107,7 +108,7 @@ mk_goto(Label) ->
   hipe_x86:mk_jmp_label(Label).
 
 is_label(I) ->
-  hipe_x86:is_label(I).
+  case I of #label{} -> true; _ -> false end.
 
 label_name(Label) ->
   hipe_x86:label_label(Label).
diff --git a/lib/hipe/x86/hipe_x86_frame.erl b/lib/hipe/x86/hipe_x86_frame.erl
index 4cdc04007d..fc782571bf 100644
--- a/lib/hipe/x86/hipe_x86_frame.erl
+++ b/lib/hipe/x86/hipe_x86_frame.erl
@@ -46,15 +46,13 @@
 -include("../x86/hipe_x86.hrl").
 -include("../rtl/hipe_literals.hrl").
 
-frame(Defun, _Options) ->
-  Formals = fix_formals(hipe_x86:defun_formals(Defun)),
-  Temps0 = all_temps(hipe_x86:defun_code(Defun), Formals),
-  MinFrame = defun_minframe(Defun),
+frame(CFG0, _Options) ->
+  Formals = fix_formals(hipe_x86_cfg:params(CFG0)),
+  Temps0 = all_temps(CFG0, Formals),
+  MinFrame = defun_minframe(CFG0),
   Temps = ensure_minframe(MinFrame, Temps0),
-  CFG0 = hipe_x86_cfg:init(Defun),
   Liveness = ?HIPE_X86_LIVENESS:analyse(CFG0),
-  CFG1 = do_body(CFG0, Liveness, Formals, Temps),
-  hipe_x86_cfg:linearise(CFG1).
+  do_body(CFG0, Liveness, Formals, Temps).
 
 fix_formals(Formals) ->
   fix_formals(?HIPE_X86_REGISTERS:nr_args(), Formals).
@@ -69,23 +67,14 @@ do_body(CFG0, Liveness, Formals, Temps) ->
   do_prologue(CFG1, Context).
 
 do_blocks(CFG, Context) ->
-  Labels = hipe_x86_cfg:labels(CFG),
-  do_blocks(Labels, CFG, Context).
+  hipe_x86_cfg:map_bbs(fun(Lbl, BB) -> do_block(Lbl, BB, Context) end, CFG).
 
-do_blocks([Label|Labels], CFG, Context) ->
+do_block(Label, Block, Context) ->
   Liveness = context_liveness(Context),
   LiveOut = ?HIPE_X86_LIVENESS:liveout(Liveness, Label),
-  Block = hipe_x86_cfg:bb(CFG, Label),
   Code = hipe_bb:code(Block),
-  NewCode = do_block(Code, LiveOut, Context),
-  NewBlock = hipe_bb:code_update(Block, NewCode),
-  NewCFG = hipe_x86_cfg:bb_add(CFG, Label, NewBlock),
-  do_blocks(Labels, NewCFG, Context);
-do_blocks([], CFG, _) ->
-  CFG.
-
-do_block(Insns, LiveOut, Context) ->
-  do_block(Insns, LiveOut, Context, context_framesize(Context), []).
+  NewCode = do_block(Code, LiveOut, Context, context_framesize(Context), []),
+  hipe_bb:code_update(Block, NewCode).
 
 do_block([I|Insns], LiveOut, Context, FPoff0, RevCode) ->
   {NewIs, FPoff1} = do_insn(I, LiveOut, Context, FPoff0),
@@ -609,18 +598,20 @@ temp_is_pseudo(Temp) ->
 %%% 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),
   S2 = tset_filter(S1, fun(T) -> temp_is_pseudo(T) end),
   S2.
 
-find_temps([I|Insns], S0) ->
+find_temps(I, S0) ->
   S1 = tset_add_list(S0, hipe_x86_defuse:insn_def(I)),
-  S2 = tset_add_list(S1, hipe_x86_defuse:insn_use(I)),
-  find_temps(Insns, S2);
-find_temps([], S) ->
-  S.
+  tset_add_list(S1, hipe_x86_defuse:insn_use(I)).
+
+fold_insns(Fun, InitAcc, CFG) ->
+  hipe_x86_cfg:fold_bbs(
+    fun(_, BB, Acc0) -> lists:foldl(Fun, Acc0, hipe_bb:code(BB)) end,
+    InitAcc, CFG).
 
 -compile({inline, [tset_empty/0, tset_size/1, tset_insert/2,
 		   tset_filter/2, tset_to_list/1]}).
@@ -654,16 +645,11 @@ tset_to_list(S) ->
 %%% in the middle of a tailcall.
 %%%
 
-defun_minframe(Defun) ->
-  MaxTailArity = body_mta(hipe_x86:defun_code(Defun), 0),
-  MyArity = length(fix_formals(hipe_x86:defun_formals(Defun))),
+defun_minframe(CFG) ->
+  MaxTailArity = fold_insns(fun insn_mta/2, 0, CFG),
+  MyArity = length(fix_formals(hipe_x86_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/x86/hipe_x86_main.erl b/lib/hipe/x86/hipe_x86_main.erl
index 13b0bb6b28..341269b698 100644
--- a/lib/hipe/x86/hipe_x86_main.erl
+++ b/lib/hipe/x86/hipe_x86_main.erl
@@ -53,19 +53,23 @@
 ?RTL_TO_X86(MFA, RTL, Options) ->
   Translated = ?option_time(?HIPE_RTL_TO_X86:translate(RTL),
 			    "RTL-to-"?X86STR, Options),
-  SpillRest = 
+  TransCFG = ?option_time(hipe_x86_cfg:init(Translated),
+			  ?X86STR" to cfg", Options),
+  SpillRestCFG =
     case proplists:get_bool(caller_save_spill_restore, Options) of
       true ->
-	?option_time(?HIPE_X86_SPILL_RESTORE:spill_restore(Translated, Options),
+	?option_time(?HIPE_X86_SPILL_RESTORE:spill_restore(TransCFG, Options),
 		     ?X86STR" spill restore", Options);
       false ->
-	Translated
+	TransCFG
     end,
-  Allocated  = ?option_time(?HIPE_X86_RA:ra(SpillRest, Options),
-			    ?X86STR" register allocation", Options),
-  Framed     = ?option_time(?HIPE_X86_FRAME:frame(Allocated, Options), 
-			    ?X86STR" frame", Options),
-  Finalised  = ?option_time(hipe_x86_postpass:postpass(Framed, Options),
-			    ?X86STR" finalise", Options),
+  AllocatedCFG = ?option_time(?HIPE_X86_RA:ra(SpillRestCFG, Options),
+			       ?X86STR" register allocation", Options),
+  FramedCFG    = ?option_time(?HIPE_X86_FRAME:frame(AllocatedCFG, Options),
+			       ?X86STR" frame", Options),
+  Framed       = ?option_time(hipe_x86_cfg:linearise(FramedCFG),
+			      ?X86STR" linearise", Options),
+  Finalised    = ?option_time(hipe_x86_postpass:postpass(Framed, Options),
+			      ?X86STR" finalise", Options),
   ?HIPE_X86_PP:optional_pp(Finalised, MFA, Options),
   {native, ?X86TAG, {unprofiled, Finalised}}.
diff --git a/lib/hipe/x86/hipe_x86_ra.erl b/lib/hipe/x86/hipe_x86_ra.erl
index d47ba532fe..2e97b07e5d 100644
--- a/lib/hipe/x86/hipe_x86_ra.erl
+++ b/lib/hipe/x86/hipe_x86_ra.erl
@@ -41,40 +41,46 @@
 %%-define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation.
 -include("../main/hipe.hrl").
 
-ra(Defun0, Options) ->
-  %% ?HIPE_X86_PP:pp(Defun0),
-  {Defun1, Coloring_fp, SpillIndex} = ra_fp(Defun0, Options),
-  %% ?HIPE_X86_PP:pp(Defun1),
+-ifdef(HIPE_INSTRUMENT_COMPILER).
+code_size(CFG) ->
+  hipe_x86_cfg:fold_bbs(fun(_, BB, Acc) -> Acc + length(hipe_bb:code(BB)) end,
+			0, CFG).
+-endif. %% ifdef(HIPE_INSTRUMENT_COMPILER)
+
+ra(CFG0, Options) ->
+  %% hipe_x86_cfg:pp(CFG0),
+  {CFG1, Coloring_fp, SpillIndex} = ra_fp(CFG0, Options),
+  %% hipe_x86_cfg:pp(CFG1),
   ?start_ra_instrumentation(Options,
-			    length(hipe_x86:defun_code(Defun1)),
-			    element(2,hipe_x86:defun_var_range(Defun1))),
-  {Defun2, Coloring}
+			    code_size(CFG1),
+			    element(2,hipe_gensym:var_range(x86))),
+  {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_X86_RA_LS:ra(Defun1, SpillIndex, Options);
+	  ?HIPE_X86_RA_LS:ra(CFG1, SpillIndex, Options);
 	naive ->
-	  ?HIPE_X86_RA_NAIVE:ra(Defun1, Coloring_fp, Options);
+	  ?HIPE_X86_RA_NAIVE:ra(CFG1, Coloring_fp, Options);
         _ ->
 	  exit({unknown_regalloc_compiler_option,
 		proplists:get_value(regalloc,Options)})
       end,
   ?stop_ra_instrumentation(Options,
-			   length(hipe_x86:defun_code(Defun2)),
-			   element(2,hipe_x86:defun_var_range(Defun2))),
-  %% ?HIPE_X86_PP:pp(Defun2),
-  ?HIPE_X86_RA_FINALISE:finalise(Defun2, Coloring, Coloring_fp, Options).
+			   code_size(CFG2),
+  			   element(2,hipe_gensym:var_range(x86))),
+  %% hipe_x86_cfg:pp(CFG2),
+  ?HIPE_X86_RA_FINALISE:finalise(CFG2, Coloring, Coloring_fp, Options).
 
-ra(Defun, SpillIndex, Options, RegAllocMod) ->
-  hipe_regalloc_loop:ra(Defun, SpillIndex, Options, RegAllocMod, ?HIPE_X86_SPECIFIC).
+ra(CFG, SpillIndex, Options, RegAllocMod) ->
+  hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, ?HIPE_X86_SPECIFIC).
 
 -ifdef(HIPE_AMD64).
-ra_fp(Defun, Options) ->
+ra_fp(CFG, Options) ->
   Regalloc0 = proplists:get_value(regalloc, Options),
   {Regalloc, TargetMod} =
     case proplists:get_bool(inline_fp, Options) and (Regalloc0 =/= naive) of
@@ -86,25 +92,25 @@ ra_fp(Defun, Options) ->
 	end
     end,
   case Regalloc of
-    coalescing  -> ra_fp(Defun, Options, hipe_coalescing_regalloc, TargetMod);
-    optimistic  -> ra_fp(Defun, Options, hipe_optimistic_regalloc, TargetMod);
-    graph_color -> ra_fp(Defun, Options, hipe_graph_coloring_regalloc,
+    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(Defun, Options, TargetMod);
-    naive -> {Defun,[],0};
+    linear_scan -> hipe_amd64_ra_ls:ra_fp(CFG, Options, TargetMod);
+    naive -> {CFG,[],0};
     _ ->
       exit({unknown_regalloc_compiler_option,
 	    proplists:get_value(regalloc,Options)})
   end.
 
-ra_fp(Defun, Options, RegAllocMod, TargetMod) ->
-  hipe_regalloc_loop:ra_fp(Defun, Options, RegAllocMod, TargetMod).
+ra_fp(CFG, Options, RegAllocMod, TargetMod) ->
+  hipe_regalloc_loop:ra_fp(CFG, Options, RegAllocMod, TargetMod).
 -else.
-ra_fp(Defun, Options) ->
+ra_fp(CFG, Options) ->
   case proplists:get_bool(inline_fp, Options) of
     true ->
-      hipe_x86_ra_ls:ra_fp(Defun, Options, hipe_x86_specific_x87);
+      hipe_x86_ra_ls:ra_fp(CFG, Options, hipe_x86_specific_x87);
     false ->
-      {Defun,[],0}
+      {CFG,[],0}
   end.
 -endif.
diff --git a/lib/hipe/x86/hipe_x86_ra_finalise.erl b/lib/hipe/x86/hipe_x86_ra_finalise.erl
index 647d67eeeb..62009abb76 100644
--- a/lib/hipe/x86/hipe_x86_ra_finalise.erl
+++ b/lib/hipe/x86/hipe_x86_ra_finalise.erl
@@ -38,11 +38,11 @@
 -export([finalise/4]).
 -include("../x86/hipe_x86.hrl").
 
-finalise(Defun, TempMap, FpMap, Options) ->
-  Defun1 = finalise_ra(Defun, TempMap, FpMap, Options),
+finalise(CFG0, TempMap, FpMap, Options) ->
+  CFG1 = finalise_ra(CFG0, TempMap, FpMap, Options),
   case proplists:get_bool(x87, Options) of
     true ->
-      ?HIPE_X86_X87:map(Defun1);
+      ?HIPE_X86_X87:map(CFG1);
     _ ->
       case
 	proplists:get_bool(inline_fp, Options)
@@ -51,9 +51,9 @@ finalise(Defun, TempMap, FpMap, Options) ->
 	%% Ugly, but required to avoid Dialyzer complaints about "Unknown
 	%% function" hipe_x86_sse2:map/1
 	?IF_HAS_SSE2(true ->
-			?HIPE_X86_SSE2:map(Defun1);)
+			?HIPE_X86_SSE2:map(CFG1);)
 	false ->
-	  Defun1
+	  CFG1
       end
   end.
 
@@ -63,15 +63,16 @@ finalise(Defun, TempMap, FpMap, Options) ->
 %%% but I just want this to work now)
 %%%
 
-finalise_ra(Defun, [], [], _Options) ->
-  Defun;
-finalise_ra(Defun, TempMap, FpMap, Options) ->
-  Code = hipe_x86:defun_code(Defun),
-  {_, SpillLimit} = hipe_x86:defun_var_range(Defun),
+finalise_ra(CFG, [], [], _Options) ->
+  CFG;
+finalise_ra(CFG, TempMap, FpMap, Options) ->
+  {_, SpillLimit} = hipe_gensym:var_range(x86),
   Map = mk_ra_map(TempMap, SpillLimit),
   FpMap0 = mk_ra_map_fp(FpMap, SpillLimit, Options),
-  NewCode = ra_code(Code, Map, FpMap0),
-  Defun#defun{code=NewCode}.
+  hipe_x86_cfg:map_bbs(fun(_Lbl, BB) -> ra_bb(BB, Map, FpMap0) end, CFG).
+
+ra_bb(BB, Map, FpMap) ->
+  hipe_bb:code_update(BB, ra_code(hipe_bb:code(BB), Map, FpMap)).
 
 ra_code(Code, Map, FpMap) ->
   [ra_insn(I, Map, FpMap) || I <- Code].
diff --git a/lib/hipe/x86/hipe_x86_ra_ls.erl b/lib/hipe/x86/hipe_x86_ra_ls.erl
index 8cd51481dd..29097f492c 100644
--- a/lib/hipe/x86/hipe_x86_ra_ls.erl
+++ b/lib/hipe/x86/hipe_x86_ra_ls.erl
@@ -39,18 +39,14 @@
 -define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation.
 -include("../main/hipe.hrl").
 
-ra(Defun, SpillIndex, Options) ->
-  NewDefun = Defun, %% hipe_${ARCH}_ra_rename:rename(Defun,Options),
-  CFG = hipe_x86_cfg:init(NewDefun),
-
+ra(CFG, SpillIndex, Options) ->
   SpillLimit = ?HIPE_X86_SPECIFIC:number_of_temporaries(
 		 CFG),
   ?inc_counter(bbs_counter, length(hipe_x86_cfg:labels(CFG))),
-  alloc(NewDefun, SpillIndex, SpillLimit, Options).
+  alloc(CFG, SpillIndex, SpillLimit, Options).
 
-ra_fp(Defun, Options, TargetMod) ->
+ra_fp(CFG, Options, TargetMod) ->
   ?inc_counter(ra_calls_counter,1),
-  CFG = hipe_x86_cfg:init(Defun),
   %% ?inc_counter(ra_caller_saves_counter,count_caller_saves(CFG)),
   SpillIndex = 0,
   SpillLimit = TargetMod:number_of_temporaries(CFG),
@@ -58,17 +54,16 @@ ra_fp(Defun, Options, TargetMod) ->
 
   ?inc_counter(ra_iteration_counter,1),
   %% ?HIPE_X86_PP:pp(Defun),
-  Cfg = hipe_x86_cfg:init(Defun), % XXX: didn't we just compute this above?
 
   {Coloring,NewSpillIndex} =
-    regalloc(Cfg,
+    regalloc(CFG,
 	     TargetMod:allocatable('linearscan'),
-	     [hipe_x86_cfg:start_label(Cfg)],
+	     [hipe_x86_cfg:start_label(CFG)],
 	     SpillIndex, SpillLimit, Options,
 	     TargetMod),
 
-  {NewDefun, _DidSpill} =
-    TargetMod:check_and_rewrite(Defun, Coloring, 'linearscan'),
+  {NewCFG, _DidSpill} =
+    TargetMod:check_and_rewrite(CFG, Coloring, 'linearscan'),
   TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod),
   {TempMap2, NewSpillIndex2} =
     hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options,
@@ -76,24 +71,23 @@ ra_fp(Defun, Options, TargetMod) ->
   Coloring2 =
     hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2),
   ?add_spills(Options, NewSpillIndex),
-  {NewDefun, Coloring2, NewSpillIndex2}.
+  {NewCFG, Coloring2, NewSpillIndex2}.
 
-alloc(Defun, SpillIndex, SpillLimit, Options) ->
+alloc(CFG, SpillIndex, SpillLimit, Options) ->
   ?inc_counter(ra_iteration_counter,1), 
   %% ?HIPE_X86_PP:pp(Defun),	
-  CFG = hipe_x86_cfg:init(Defun),
   {Coloring, NewSpillIndex} = 
     regalloc(
-      CFG, 
+      CFG,
       ?HIPE_X86_REGISTERS:allocatable()--
       [?HIPE_X86_REGISTERS:temp1(),
        ?HIPE_X86_REGISTERS:temp0()],
       [hipe_x86_cfg:start_label(CFG)],
       SpillIndex, SpillLimit, Options,
       ?HIPE_X86_SPECIFIC),
-  {NewDefun, _DidSpill} =
+  {NewCFG, _DidSpill} =
     ?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite(
-      Defun, Coloring, 'linearscan'),
+      CFG, Coloring, 'linearscan'),
   %% ?HIPE_X86_PP:pp(NewDefun),
   TempMap = hipe_temp_map:cols2tuple(Coloring, ?HIPE_X86_SPECIFIC),
   {TempMap2,NewSpillIndex2} = 
@@ -108,7 +102,7 @@ alloc(Defun, SpillIndex, SpillLimit, Options) ->
       ok
   end,
   ?add_spills(Options, NewSpillIndex),
-  {NewDefun, Coloring2}.
+  {NewCFG, Coloring2}.
 
 regalloc(CFG,PhysRegs,Entrypoints, SpillIndex, DontSpill, Options, Target) ->
   hipe_ls_regalloc:regalloc(CFG,PhysRegs,Entrypoints, SpillIndex, 
diff --git a/lib/hipe/x86/hipe_x86_ra_naive.erl b/lib/hipe/x86/hipe_x86_ra_naive.erl
index 0ef4ef0a04..27e5af4aee 100644
--- a/lib/hipe/x86/hipe_x86_ra_naive.erl
+++ b/lib/hipe/x86/hipe_x86_ra_naive.erl
@@ -39,9 +39,8 @@
 -define(HIPE_INSTRUMENT_COMPILER, true). % enable instrumentation
 -include("../main/hipe.hrl").
 
-ra(X86Defun, Coloring_fp, Options) ->
-  #defun{code=Code0} = X86Defun,
-  Code1 = do_insns(Code0),
+ra(CFG0, 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),
   ?add_spills(Options, hipe_gensym:get_var(x86) -
@@ -49,10 +48,12 @@ ra(X86Defun, Coloring_fp, Options) ->
 	      NofSpilledFloats -
 	      NofFloats),
   TempMap = [],
-  {X86Defun#defun{code=Code1,
-		  var_range={0, hipe_gensym:get_var(x86)}},
+  {CFG,
    TempMap}.
 
+do_bb(_Lbl, BB) ->
+  hipe_bb:code_update(BB, do_insns(hipe_bb:code(BB))).
+
 count_non_float_spills(Coloring_fp) ->
   count_non_float_spills(Coloring_fp, 0).
 
diff --git a/lib/hipe/x86/hipe_x86_ra_postconditions.erl b/lib/hipe/x86/hipe_x86_ra_postconditions.erl
index 0a70bd1d22..343d04977d 100644
--- a/lib/hipe/x86/hipe_x86_ra_postconditions.erl
+++ b/lib/hipe/x86/hipe_x86_ra_postconditions.erl
@@ -40,14 +40,18 @@
 -include("../main/hipe.hrl").
 -define(count_temp(T), ?cons_counter(counter_mfa_mem_temps, T)).
 
-check_and_rewrite(Defun, Coloring, Strategy) ->
+check_and_rewrite(CFG, Coloring, Strategy) ->
   %% io:format("Converting\n"),
   TempMap = hipe_temp_map:cols2tuple(Coloring, ?HIPE_X86_SPECIFIC),
   %% io:format("Rewriting\n"),
-  #defun{code=Code0} = Defun,
-  {Code1, DidSpill} = do_insns(Code0, TempMap, Strategy, [], false),
-  {Defun#defun{code=Code1,var_range={0,hipe_gensym:get_var(x86)}},
-   DidSpill}.
+  do_bbs(hipe_x86_cfg:labels(CFG), TempMap, Strategy, CFG, false).
+
+do_bbs([], _, _, CFG, DidSpill) -> {CFG, DidSpill};
+do_bbs([Lbl|Lbls], TempMap, Strategy, CFG0, DidSpill0) ->
+  Code0 = hipe_bb:code(BB = hipe_x86_cfg:bb(CFG0, Lbl)),
+  {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0),
+  CFG = hipe_x86_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),
diff --git a/lib/hipe/x86/hipe_x86_spill_restore.erl b/lib/hipe/x86/hipe_x86_spill_restore.erl
index f17b91f33b..32b1eb7b40 100644
--- a/lib/hipe/x86/hipe_x86_spill_restore.erl
+++ b/lib/hipe/x86/hipe_x86_spill_restore.erl
@@ -25,13 +25,11 @@
 -ifdef(HIPE_AMD64).
 -define(HIPE_X86_SPILL_RESTORE, hipe_amd64_spill_restore).
 -define(HIPE_X86_LIVENESS,      hipe_amd64_liveness).
--define(HIPE_X86_SPECIFIC,      hipe_amd64_specific).
 -define(HIPE_X86_REGISTERS,	hipe_amd64_registers).
 -define(X86STR, "amd64").
 -else.
 -define(HIPE_X86_SPILL_RESTORE, hipe_x86_spill_restore).
 -define(HIPE_X86_LIVENESS,      hipe_x86_liveness).
--define(HIPE_X86_SPECIFIC,      hipe_x86_specific).
 -define(HIPE_X86_REGISTERS,     hipe_x86_registers).
 -define(X86STR, "x86").
 -endif.
@@ -51,15 +49,13 @@
 -include("../flow/cfg.hrl").     % Added for the definition of #cfg{}
 
 %% Main function
-spill_restore(Defun, Options) ->
-  CFG = ?option_time(firstPass(Defun), ?X86STR" First Pass", Options),
-  CFGFinal = ?option_time(secondPass(CFG), ?X86STR" Second Pass", Options),
-  hipe_x86_cfg:linearise(CFGFinal).
+spill_restore(CFG0, Options) ->
+  CFG1 = ?option_time(firstPass(CFG0), ?X86STR" First Pass", Options),
+  ?option_time(secondPass(CFG1), ?X86STR" Second Pass", Options).
 
 %% Performs the first pass of the algorithm.
 %% By working bottom up, introduce the pseudo_spills.
-firstPass(Defun) ->
-  CFG0 = ?HIPE_X86_SPECIFIC:defun_to_cfg(Defun),
+firstPass(CFG0) ->
   %% get the labels bottom up
   Labels = hipe_x86_cfg:postorder(CFG0),
   Liveness = ?HIPE_X86_LIVENESS:analyse(CFG0),
diff --git a/lib/hipe/x86/hipe_x86_x87.erl b/lib/hipe/x86/hipe_x86_x87.erl
index e874490252..10bb6aa75c 100644
--- a/lib/hipe/x86/hipe_x86_x87.erl
+++ b/lib/hipe/x86/hipe_x86_x87.erl
@@ -41,13 +41,12 @@
 
 %%----------------------------------------------------------------------
 
-map(Defun) ->
-  CFG0 = hipe_x86_cfg:init(Defun),
+map(CFG0) ->
   %% hipe_x86_cfg:pp(CFG0),
   Liveness = ?HIPE_X86_LIVENESS:analyse(CFG0),
   StartLabel = hipe_x86_cfg:start_label(CFG0),
   {CFG1,_} = do_blocks([], [StartLabel], CFG0, Liveness, [], gb_trees:empty()),
-  hipe_x86_cfg:linearise(CFG1).
+  CFG1.
 
 do_blocks(Pred, [Lbl|Lbls], CFG, Liveness, Map, BlockMap) ->
   case gb_trees:lookup(Lbl, BlockMap) of