Merge branch 'sverker/hipe-performance-o1/PR-1154/OTP-13862'

* sverker/hipe-performance-o1/PR-1154:
  hipe_sparc: Minimise CFG<->linear conversions
  hipe_ppc: Minimise CFG<->linear conversions
  hipe_arm: Minimise CFG<->linear conversions
  hipe_x86: Use lea instead of move+add
  hipe_arm: Improve peephole optimiser
  hipe_arm: Be resilient to crappy RTL
  hipe_ppc: Be resilient to crappy RTL
  hipe_sparc: Be resilient to crappy RTL
  hipe: Reuse liveness info for spillmin
  hipe_x86: Minimise CFG<->linear conversions
  hipe: Fix o0 and o1
  hipe: Add o0 and o1 to tests
  hipe_rtl_binary:get_word_integer/4: Handle imms
  hipe_x86: Be resilient to crappy RTL
  hipe_x86: LSRA for SSE2

71 files changed, 1027 insertions, 761 deletions

diff --git a/lib/hipe/amd64/Makefile b/lib/hipe/amd64/Makefile
index 8dc2af2679..ea3559b7e6 100644
--- a/lib/hipe/amd64/Makefile
+++ b/lib/hipe/amd64/Makefile
@@ -57,10 +57,10 @@ MODULES=hipe_amd64_assemble \
 	hipe_amd64_ra_naive \
 	hipe_amd64_ra_postconditions \
 	hipe_amd64_ra_sse2_postconditions \
-	hipe_amd64_ra_x87_ls \
 	hipe_amd64_registers \
 	hipe_amd64_spill_restore \
 	hipe_amd64_x87 \
+	hipe_amd64_sse2 \
 	hipe_rtl_to_amd64
 
 ERL_FILES=$(MODULES:%=%.erl)
@@ -125,10 +125,10 @@ $(EBIN)/hipe_amd64_ra_ls.beam: ../main/hipe.hrl ../x86/hipe_x86_ra_ls.erl
 $(EBIN)/hipe_amd64_ra_naive.beam: ../main/hipe.hrl ../x86/hipe_x86.hrl ../x86/hipe_x86_ra_naive.erl
 $(EBIN)/hipe_amd64_ra_postconditions.beam: ../main/hipe.hrl ../x86/hipe_x86.hrl ../x86/hipe_x86_ra_postconditions.erl
 $(EBIN)/hipe_amd64_ra_sse2_postconditions.beam: ../main/hipe.hrl
-$(EBIN)/hipe_amd64_ra_x87_ls.beam: ../main/hipe.hrl ../x86/hipe_x86_ra_x87_ls.erl
 $(EBIN)/hipe_amd64_registers.beam: ../rtl/hipe_literals.hrl
 $(EBIN)/hipe_amd64_spill_restore.beam: ../main/hipe.hrl ../x86/hipe_x86.hrl ../flow/cfg.hrl ../x86/hipe_x86_spill_restore.erl
 $(EBIN)/hipe_amd64_x87.beam: ../x86/hipe_x86_x87.erl
+$(EBIN)/hipe_amd64_sse2.beam: ../main/hipe.hrl ../x86/hipe_x86.hrl
 $(EBIN)/hipe_rtl_to_amd64.beam: ../x86/hipe_rtl_to_x86.erl ../rtl/hipe_rtl.hrl
 
 $(TARGET_FILES): ../x86/hipe_x86.hrl ../misc/hipe_consttab.hrl
diff --git a/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl b/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl
index b1f7bd7572..bbf9170bc3 100644
--- a/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl
+++ b/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl
@@ -21,7 +21,7 @@
 
 -module(hipe_amd64_ra_sse2_postconditions).
 
--export([check_and_rewrite/2]).
+-export([check_and_rewrite/2, check_and_rewrite/3]).
 
 -include("../x86/hipe_x86.hrl").
 -define(HIPE_INSTRUMENT_COMPILER, true).
@@ -29,40 +29,48 @@
 -define(count_temp(T), ?cons_counter(counter_mfa_mem_temps, T)).
 
 
-check_and_rewrite(AMD64Defun, Coloring) ->
+check_and_rewrite(AMD64CFG, Coloring) ->
+  check_and_rewrite(AMD64CFG, Coloring, 'normal').
+
+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, [], false),
-  {AMD64Defun#defun{code=Code1, var_range={0, hipe_gensym:get_var(x86)}}, 
-   DidSpill}.
-
-do_insns([I|Insns], TempMap, Accum, DidSpill0) ->
-  {NewIs, DidSpill1} = do_insn(I, TempMap),
-  do_insns(Insns, TempMap, lists:reverse(NewIs, Accum), DidSpill0 or DidSpill1);
-do_insns([], _TempMap, Accum, 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),
+  do_insns(Insns, TempMap, Strategy, lists:reverse(NewIs, Accum),
+	   DidSpill0 or DidSpill1);
+do_insns([], _TempMap, _Strategy, Accum, DidSpill) ->
   {lists:reverse(Accum), DidSpill}.
 
-do_insn(I, TempMap) ->	% Insn -> {Insn list, DidSpill}
+do_insn(I, TempMap, Strategy) ->	% Insn -> {Insn list, DidSpill}
   case I of
     #fmove{} ->
-      do_fmove(I, TempMap);
+      do_fmove(I, TempMap, Strategy);
     #fp_unop{} ->
-      do_fp_unop(I, TempMap);
+      do_fp_unop(I, TempMap, Strategy);
     #fp_binop{} ->
-      do_fp_binop(I, TempMap);
+      do_fp_binop(I, TempMap, Strategy);
     _ ->
       %% All non sse2 ops
       {[I], false}
   end.
 
 %%% Fix an fp_binop.
-do_fp_binop(I, TempMap) ->
+do_fp_binop(I, TempMap, Strategy) ->
   #fp_binop{src=Src,dst=Dst} = I,
   case is_mem_opnd(Dst, TempMap) of
     true ->
-      Tmp = clone(Dst),
+      Tmp = clone(Dst, Strategy),
       {[#fmove{src=Dst, dst=Tmp},
 	I#fp_binop{src=Src,dst=Tmp},
 	#fmove{src=Tmp,dst=Dst}],
@@ -71,11 +79,11 @@ do_fp_binop(I, TempMap) ->
       {[I], false}
   end.
 
-do_fp_unop(I, TempMap) ->
+do_fp_unop(I, TempMap, Strategy) ->
   #fp_unop{arg=Arg} = I,
   case is_mem_opnd(Arg, TempMap) of
     true ->
-      Tmp = clone(Arg),
+      Tmp = clone(Arg, Strategy),
       {[#fmove{src=Arg, dst=Tmp},
 	I#fp_unop{arg=Tmp},
 	#fmove{src=Tmp,dst=Arg}],
@@ -85,7 +93,7 @@ do_fp_unop(I, TempMap) ->
   end.
 
 %%% Fix an fmove op.
-do_fmove(I, TempMap) ->
+do_fmove(I, TempMap, Strategy) ->
   #fmove{src=Src,dst=Dst} = I,
   case
     (is_mem_opnd(Src, TempMap) andalso is_mem_opnd(Dst, TempMap))
@@ -93,7 +101,7 @@ do_fmove(I, TempMap) ->
     orelse ((not is_float_temp(Src)) andalso is_mem_opnd(Dst, TempMap))
   of
     true ->
-      Tmp = spill_temp(double),
+      Tmp = spill_temp(double, Strategy),
       {[#fmove{src=Src, dst=Tmp},I#fmove{src=Tmp,dst=Dst}],
        true};
     false ->
@@ -106,86 +114,45 @@ 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).
 
-clone(Dst) ->
+clone(Dst, Strategy) ->
   Type =
     case Dst of
       #x86_mem{} -> hipe_x86:mem_type(Dst);
       #x86_temp{} -> hipe_x86:temp_type(Dst)
     end,
-  spill_temp(Type).
-
-spill_temp(Type) ->
+  spill_temp(Type, Strategy).
+
+spill_temp(Type, 'normal') ->
+  hipe_x86:mk_new_temp(Type);
+spill_temp(double, 'linearscan') ->
+  hipe_x86:mk_temp(hipe_amd64_specific_sse2:temp0(), double);
+spill_temp(Type, 'linearscan') when Type =:= tagged; Type =/= untagged ->
+  %% We can make a new temp here since we have yet to allocate registers for
+  %% these types
   hipe_x86:mk_new_temp(Type).
 
 %%% Make a certain reg into a clone of Dst
diff --git a/lib/hipe/amd64/hipe_amd64_ra_x87_ls.erl b/lib/hipe/amd64/hipe_amd64_ra_x87_ls.erl
deleted file mode 100644
index 6da3f44cd3..0000000000
--- a/lib/hipe/amd64/hipe_amd64_ra_x87_ls.erl
+++ /dev/null
@@ -1,21 +0,0 @@
-%%
-%% %CopyrightBegin%
-%% 
-%% Copyright Ericsson AB 2004-2016. All Rights Reserved.
-%% 
-%% Licensed under the Apache License, Version 2.0 (the "License");
-%% you may not use this file except in compliance with the License.
-%% You may obtain a copy of the License at
-%%
-%%     http://www.apache.org/licenses/LICENSE-2.0
-%%
-%% Unless required by applicable law or agreed to in writing, software
-%% distributed under the License is distributed on an "AS IS" BASIS,
-%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-%% See the License for the specific language governing permissions and
-%% limitations under the License.
-%% 
-%% %CopyrightEnd%
-%%
-
--include("../x86/hipe_x86_ra_x87_ls.erl").
diff --git a/lib/hipe/amd64/hipe_amd64_registers.erl b/lib/hipe/amd64/hipe_amd64_registers.erl
index 780c2cc547..ada5311453 100644
--- a/lib/hipe/amd64/hipe_amd64_registers.erl
+++ b/lib/hipe/amd64/hipe_amd64_registers.erl
@@ -52,6 +52,7 @@
  	 tailcall_clobbered/0,
  	 temp0/0,
 	 temp1/0,
+	 sse2_temp0/0,
 	 %% fixed/0,
 	 wordsize/0
 	]).
@@ -107,6 +108,8 @@ heap_limit_offset() -> ?P_HP_LIMIT.
 -define(TEMP0, ?R14).
 -define(TEMP1, ?R13).
 
+-define(SSE2_TEMP0, 00).
+
 -define(PROC_POINTER, ?RBP).
 
 reg_name(R) ->
@@ -204,6 +207,8 @@ allocatable() ->
 allocatable_sse2() ->
   [00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15]. %% xmm0 - xmm15
 
+sse2_temp0() -> ?SSE2_TEMP0.
+
 allocatable_x87() ->
   [0,1,2,3,4,5,6].
 
diff --git a/lib/hipe/amd64/hipe_amd64_sse2.erl b/lib/hipe/amd64/hipe_amd64_sse2.erl
new file mode 100644
index 0000000000..ea6b6cb9ba
--- /dev/null
+++ b/lib/hipe/amd64/hipe_amd64_sse2.erl
@@ -0,0 +1,82 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2016. All Rights Reserved.
+%% 
+%% Licensed under the Apache License, Version 2.0 (the "License");
+%% you may not use this file except in compliance with the License.
+%% You may obtain a copy of the License at
+%%
+%%     http://www.apache.org/licenses/LICENSE-2.0
+%%
+%% Unless required by applicable law or agreed to in writing, software
+%% distributed under the License is distributed on an "AS IS" BASIS,
+%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%% See the License for the specific language governing permissions and
+%% limitations under the License.
+%% 
+%% %CopyrightEnd%
+%%
+%% Fix {mem, mem} floating point operations that result from linear scan
+%% allocated floats.
+
+-module(hipe_amd64_sse2).
+
+-export([map/1]).
+
+-include("../x86/hipe_x86.hrl").
+-include("../main/hipe.hrl").
+
+%%----------------------------------------------------------------------
+
+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),
+  do_insns(Insns, lists:reverse(NewIs, Accum));
+do_insns([], Accum) ->
+  lists:reverse(Accum).
+
+do_insn(I) ->
+  case I of
+    #fp_binop{} -> do_fp_binop(I);
+    #fmove{}    -> do_fmove(I);
+    _           -> [I]
+  end.
+
+do_fp_binop(I = #fp_binop{src=Src0,dst=Dst}) ->
+  {FixSrc, Src} = fix_binary(Src0, Dst),
+  FixSrc ++ [I#fp_binop{src=Src}].
+
+do_fmove(I = #fmove{src=Src0,dst=Dst}) ->
+  {FixSrc, Src} = fix_binary(Src0, Dst),
+  FixSrc ++ [I#fmove{src=Src}].
+
+fix_binary(Src0, Dst) ->
+  case is_mem_opnd(Src0) of
+    false -> {[], Src0};
+    true ->
+      case is_mem_opnd(Dst) of
+	false -> {[], Src0};
+	true ->
+	  Src1 = spill_temp(),
+	  {[hipe_x86:mk_fmove(Src0, Src1)], Src1}
+      end
+  end.
+
+is_mem_opnd(#x86_fpreg{reg=Reg}) ->
+  not hipe_amd64_registers:is_precoloured_sse2(Reg);
+is_mem_opnd(#x86_temp{type=double, reg=Reg}) ->
+  not hipe_amd64_registers:is_precoloured_sse2(Reg);
+is_mem_opnd(#x86_temp{type=_, reg=Reg}) ->
+  not hipe_amd64_registers:is_precoloured(Reg);
+is_mem_opnd(#x86_mem{}) -> true.
+
+spill_temp() ->
+  hipe_x86:mk_temp(hipe_amd64_registers:sse2_temp0(), double).
diff --git a/lib/hipe/arm/hipe_arm_cfg.erl b/lib/hipe/arm/hipe_arm_cfg.erl
index f2fa0a5164..2fb6675da9 100644
--- a/lib/hipe/arm/hipe_arm_cfg.erl
+++ b/lib/hipe/arm/hipe_arm_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]).
 -export([linearise/1]).
@@ -35,6 +36,7 @@
 -define(BREADTH_ORDER,true).  % for linear scan
 -define(PARAMS_NEEDED,true).
 -define(START_LABEL_UPDATE_NEEDED,true).
+-define(MAP_FOLD_NEEDED,true).
 
 -include("hipe_arm.hrl").
 -include("../flow/cfg.hrl").
diff --git a/lib/hipe/arm/hipe_arm_finalise.erl b/lib/hipe/arm/hipe_arm_finalise.erl
index a4b2f9c73c..55651d7180 100644
--- a/lib/hipe/arm/hipe_arm_finalise.erl
+++ b/lib/hipe/arm/hipe_arm_finalise.erl
@@ -20,13 +20,17 @@
 %%
 
 -module(hipe_arm_finalise).
--export([finalise/1]).
+-export([finalise/2]).
 -include("hipe_arm.hrl").
 
-finalise(Defun) ->
+finalise(Defun, Options) ->
   #defun{code=Code0} = Defun,
-  Code1 = peep(expand(Code0)),
-  Defun#defun{code=Code1}.
+  Code1Rev = expand(Code0),
+  Code2 = case proplists:get_bool(peephole, Options) of
+	    true -> peep(Code1Rev);
+	    false -> lists:reverse(Code1Rev)
+	  end,
+  Defun#defun{code=Code2}.
 
 expand(Insns) ->
   expand_list(Insns, []).
@@ -34,7 +38,7 @@ expand(Insns) ->
 expand_list([I|Insns], Accum) ->
   expand_list(Insns, expand_insn(I, Accum));
 expand_list([], Accum) ->
-  lists:reverse(Accum).
+  Accum.
 
 expand_insn(I, Accum) ->
   case I of
@@ -63,12 +67,67 @@ expand_insn(I, Accum) ->
       [I|Accum]
   end.
 
-peep(Insns) ->
-  peep_list(Insns, []).
+%% We do peephole "bottom-up" (in reverse, but applying rules to the correctly
+%% ordered list). This way, we can do replacements that would take multiple
+%% passes with an in-order peephole optimiser.
+%%
+%% N.B., if a rule wants to produce multiple instructions (even if some of them
+%% are unchanged, it should push the additional instructions on the More list,
+%% so that only the top instruction on Insns is new or changed, i.e. tl(Insns)
+%% should have been peepholed previously.
+peep(RevInsns) ->
+  peep_list_skip([], RevInsns).
+
+peep_list([#b_label{'cond'='al',label=Label}
+	   | (Insns = [#label{label=Label}|_])], More) ->
+  peep_list_skip(Insns, More);
+
+peep_list([#move{movop='mov',s=false,dst=#arm_temp{reg=Dst}
+		,am1=#arm_temp{reg=Dst}}|Insns], More) ->
+  peep_list_skip(Insns, More);
+
+peep_list([#move{movop='mov',s=false,dst=Dst,am1={Src,lsr,Imm}},
+	   #move{movop='mov',s=false,dst=Dst,am1={Dst,lsl,Imm}}
+	   |Insns], More) when Imm > 0, Imm =< 8 ->
+  peep_list([#alu{aluop='bic',s=false,dst=Dst,src=Src,am1={(1 bsl Imm)-1,0}}
+	    |Insns], More);
+peep_list([#move{movop='mov',s=false,dst=Dst,am1={Src,lsl,Imm}},
+	   #move{movop='mov',s=false,dst=Dst,am1={Dst,lsr,Imm}}
+	   |Insns], More) when Imm >= 24, Imm < 32 ->
+  peep_list([#alu{aluop='and',s=false,dst=Dst,src=Src
+		 ,am1={(1 bsl (32-Imm))-1,0}} | Insns], More);
+
+%% XXX: Load-after-store optimisation should also be applied to RTL, where it
+%% can be more general, expose opportunities for constant propagation, etc.
+peep_list([#store{stop='strb',src=Src,am2=Mem}=Str,
+	   #load {ldop='ldrb',dst=Dst,am2=Mem} | Insns], More) ->
+  peep_list([#alu{aluop='and',s=false,dst=Dst,src=Src,am1={16#ff,0}}|Insns],
+	    [Str|More]);
+peep_list([#store{stop='str',src=Src,am2=Mem}=Str,
+	   #load {ldop='ldr',dst=Dst,am2=Mem} | Insns], More) ->
+  peep_list([#move{movop='mov',s=false,dst=Dst,am1=Src}|Insns], [Str|More]);
+
+peep_list([#alu{aluop='and',s=false,dst=Dst,src=Src,am1={Mask,0}},
+	   #alu{aluop='bic',s=false,dst=Dst,src=Dst,am1={InvMask,0}}
+	   |Insns], More) ->
+  peep_list([#alu{aluop='and',s=false,dst=Dst,src=Src
+		 ,am1={Mask band (bnot InvMask),0}} | Insns], More);
+
+%% XXX: The place that generates brain-dead code like the following should be
+%% fixed rather than trying to patch it over here.
+peep_list([#load{ldop='ldrb',dst=Dst,am2=_Mem},
+	   #alu{aluop='bic',s=false,dst=Dst,src=Dst,am1={16#ff,0}}
+	   | Insns], More) ->
+  peep_list([#move{movop='mov',s=false,dst=Dst,am1={0,0}}|Insns], More);
+
+peep_list(Insns, [I|More]) ->
+  peep_list([I|Insns], More);
+peep_list(Accum, []) ->
+  Accum.
 
-peep_list([#b_label{'cond'='al',label=Label} | (Insns = [#label{label=Label}|_])], Accum) ->
-  peep_list(Insns, Accum);
-peep_list([I|Insns], Accum) ->
-  peep_list(Insns, [I|Accum]);
-peep_list([], Accum) ->
-  lists:reverse(Accum).
+%% Used as an optimisation instead of tailcalling peep_list/2 when Insns has
+%% already been peeped or is otherwise uninteresting (such as empty).
+peep_list_skip(Insns, [I|More]) ->
+  peep_list([I|Insns], More);
+peep_list_skip(Accum, []) ->
+  Accum.
diff --git a/lib/hipe/arm/hipe_arm_frame.erl b/lib/hipe/arm/hipe_arm_frame.erl
index e1e441a967..9a349b47d3 100644
--- a/lib/hipe/arm/hipe_arm_frame.erl
+++ b/lib/hipe/arm/hipe_arm_frame.erl
@@ -27,16 +27,14 @@
 
 -define(LIVENESS_ALL, hipe_arm_liveness_gpr). % since we have no FP yet
 
-frame(Defun) ->
-  Formals = fix_formals(hipe_arm:defun_formals(Defun)),
-  Temps0 = all_temps(hipe_arm:defun_code(Defun), Formals),
-  MinFrame = defun_minframe(Defun),
+frame(CFG) ->
+  Formals = fix_formals(hipe_arm_cfg:params(CFG)),
+  Temps0 = all_temps(CFG, Formals),
+  MinFrame = defun_minframe(CFG),
   Temps = ensure_minframe(MinFrame, Temps0),
-  ClobbersLR = clobbers_lr(hipe_arm:defun_code(Defun)),
-  CFG0 = hipe_arm_cfg:init(Defun),
-  Liveness = ?LIVENESS_ALL:analyse(CFG0),
-  CFG1 = do_body(CFG0, Liveness, Formals, Temps, ClobbersLR),
-  hipe_arm_cfg:linearise(CFG1).
+  ClobbersLR = clobbers_lr(CFG),
+  Liveness = ?LIVENESS_ALL:analyse(CFG),
+  do_body(CFG, Liveness, Formals, Temps, ClobbersLR).
 
 fix_formals(Formals) ->
   fix_formals(hipe_arm_registers:nr_args(), Formals).
@@ -51,32 +49,21 @@ do_body(CFG0, Liveness, Formals, Temps, ClobbersLR) ->
   do_prologue(CFG1, Context).
 
 do_blocks(CFG, Context) ->
-  Labels = hipe_arm_cfg:labels(CFG),
-  do_blocks(Labels, CFG, Context).
+  hipe_arm_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 = ?LIVENESS_ALL:liveout(Liveness, Label),
-  Block = hipe_arm_cfg:bb(CFG, Label),
   Code = hipe_bb:code(Block),
-  NewCode = do_block(Code, LiveOut, Context),
-  NewBlock = hipe_bb:code_update(Block, NewCode),
-  NewCFG = hipe_arm_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),
   do_block(Insns, LiveOut, Context, FPoff1, lists:reverse(NewIs, RevCode));
 do_block([], _, Context, FPoff, RevCode) ->
   FPoff0 = context_framesize(Context),
-  if FPoff =:= FPoff0 -> [];
-     true -> exit({?MODULE,do_block,FPoff})
-  end,
+  FPoff0 = FPoff,
   lists:reverse(RevCode, []).
 
 do_insn(I, LiveOut, Context, FPoff) ->
@@ -543,39 +530,46 @@ temp_is_pseudo(Temp) ->
 %%% Detect if a Defun's body clobbers LR.
 %%%
 
-clobbers_lr(Insns) ->
+clobbers_lr(CFG) ->
   LRreg = hipe_arm_registers:lr(),
   LRtagged = hipe_arm:mk_temp(LRreg, 'tagged'),
   LRuntagged = hipe_arm:mk_temp(LRreg, 'untagged'),
-  clobbers_lr(Insns, LRtagged, LRuntagged).
-
-clobbers_lr([I|Insns], LRtagged, LRuntagged) ->
-  Defs = hipe_arm_defuse:insn_def_gpr(I),
-  case lists:member(LRtagged, Defs) of
-    true -> true;
-    false ->
-      case lists:member(LRuntagged, Defs) of
-	true -> true;
-	false -> clobbers_lr(Insns, LRtagged, LRuntagged)
-      end
-  end;
-clobbers_lr([], _LRtagged, _LRuntagged) -> false.
+  any_insn(fun(I) ->
+	       Defs = hipe_arm_defuse:insn_def_gpr(I),
+	       lists:member(LRtagged, Defs)
+		 orelse lists:member(LRuntagged, Defs)
+	   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_arm_defuse:insn_def_all(I)),
-  S2 = tset_add_list(S1, hipe_arm_defuse:insn_use_all(I)),
-  find_temps(Insns, S2);
-find_temps([], S) ->
-  S.
+  tset_add_list(S1, hipe_arm_defuse:insn_use_all(I)).
+
+fold_insns(Fun, InitAcc, CFG) ->
+  hipe_arm_cfg:fold_bbs(
+    fun(_, BB, Acc0) -> lists:foldl(Fun, Acc0, hipe_bb:code(BB)) end,
+    InitAcc, CFG).
 
 tset_empty() ->
   gb_sets:new().
@@ -604,16 +598,11 @@ tset_to_list(S) ->
 %%% in the middle of a tailcall.
 %%%
 
-defun_minframe(Defun) ->
-  MaxTailArity = body_mta(hipe_arm:defun_code(Defun), 0),
-  MyArity = length(fix_formals(hipe_arm:defun_formals(Defun))),
+defun_minframe(CFG) ->
+  MaxTailArity = fold_insns(fun insn_mta/2, 0, CFG),
+  MyArity = length(fix_formals(hipe_arm_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/arm/hipe_arm_main.erl b/lib/hipe/arm/hipe_arm_main.erl
index dce1193b24..8a7fa86394 100644
--- a/lib/hipe/arm/hipe_arm_main.erl
+++ b/lib/hipe/arm/hipe_arm_main.erl
@@ -24,15 +24,17 @@
 
 rtl_to_arm(MFA, RTL, Options) ->
   Defun1 = hipe_rtl_to_arm:translate(RTL),
+  CFG1 = hipe_arm_cfg:init(Defun1),
   %% io:format("~w: after translate\n", [?MODULE]),
   %% hipe_arm_pp:pp(Defun1),
-  Defun2 = hipe_arm_ra:ra(Defun1, Options),
+  CFG2 = hipe_arm_ra:ra(CFG1, Options),
   %% io:format("~w: after regalloc\n", [?MODULE]),
-  %% hipe_arm_pp:pp(Defun2),
-  Defun3 = hipe_arm_frame:frame(Defun2),
+  %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG2)),
+  CFG3 = hipe_arm_frame:frame(CFG2),
+  Defun3 = hipe_arm_cfg:linearise(CFG3),
   %% io:format("~w: after frame\n", [?MODULE]),
   %% hipe_arm_pp:pp(Defun3),
-  Defun4 = hipe_arm_finalise:finalise(Defun3),
+  Defun4 = hipe_arm_finalise:finalise(Defun3, Options),
   %% io:format("~w: after finalise\n", [?MODULE]),
   pp(Defun4, MFA, Options),
   {native, arm, {unprofiled, Defun4}}.
diff --git a/lib/hipe/arm/hipe_arm_ra.erl b/lib/hipe/arm/hipe_arm_ra.erl
index 2f65e864fd..5a7884b63c 100644
--- a/lib/hipe/arm/hipe_arm_ra.erl
+++ b/lib/hipe/arm/hipe_arm_ra.erl
@@ -22,36 +22,36 @@
 -module(hipe_arm_ra).
 -export([ra/2]).
 
-ra(Defun0, Options) ->
-  %% hipe_arm_pp:pp(Defun0),
-  {Defun1, Coloring_fp, SpillIndex}
+ra(CFG0, Options) ->
+  %% hipe_arm_pp:pp(hipe_arm_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_arm_specific_fp);
 	false ->
-	  {Defun0,[],0}
+	  {CFG0,[],0}
       end,
-  %% hipe_arm_pp:pp(Defun1),
-  {Defun2, Coloring}
+  %% hipe_arm_pp:pp(hipe_arm_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_arm_ra_ls:ra(Defun1, SpillIndex, Options);
+	  hipe_arm_ra_ls:ra(CFG1, SpillIndex, Options);
 	naive ->
-	  hipe_arm_ra_naive:ra(Defun1, Coloring_fp, Options);
+	  hipe_arm_ra_naive:ra(CFG1, Coloring_fp, Options);
         _ ->
 	  exit({unknown_regalloc_compiler_option,
 		proplists:get_value(regalloc,Options)})
       end,
-  %% hipe_arm_pp:pp(Defun2),
-  hipe_arm_ra_finalise:finalise(Defun2, Coloring, Coloring_fp).
+  %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG2)),
+  hipe_arm_ra_finalise:finalise(CFG2, Coloring, Coloring_fp).
 
-ra(Defun, SpillIndex, Options, RegAllocMod) ->
-  hipe_regalloc_loop:ra(Defun, SpillIndex, Options, RegAllocMod, hipe_arm_specific).
+ra(CFG, SpillIndex, Options, RegAllocMod) ->
+  hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, hipe_arm_specific).
diff --git a/lib/hipe/arm/hipe_arm_ra_finalise.erl b/lib/hipe/arm/hipe_arm_ra_finalise.erl
index 4faeadcd7f..2a3fded147 100644
--- a/lib/hipe/arm/hipe_arm_ra_finalise.erl
+++ b/lib/hipe/arm/hipe_arm_ra_finalise.erl
@@ -23,12 +23,13 @@
 -export([finalise/3]).
 -include("hipe_arm.hrl").
 
-finalise(Defun, TempMap, _FPMap0=[]) ->
-  Code = hipe_arm:defun_code(Defun),
-  {_, SpillLimit} = hipe_arm:defun_var_range(Defun),
+finalise(CFG, TempMap, _FPMap0=[]) ->
+  {_, SpillLimit} = hipe_gensym:var_range(arm),
   Map = mk_ra_map(TempMap, SpillLimit),
-  NewCode = ra_code(Code, Map, []),
-  Defun#defun{code=NewCode}.
+  hipe_arm_cfg:map_bbs(fun(_Lbl, BB) -> ra_bb(BB, Map) end, CFG).
+
+ra_bb(BB, Map) ->
+  hipe_bb:code_update(BB, ra_code(hipe_bb:code(BB), Map, [])).
 
 ra_code([I|Insns], Map, Accum) ->
   ra_code(Insns, Map, [ra_insn(I, Map) | Accum]);
diff --git a/lib/hipe/arm/hipe_arm_ra_ls.erl b/lib/hipe/arm/hipe_arm_ra_ls.erl
index d9a360d00c..f9193ca9e0 100644
--- a/lib/hipe/arm/hipe_arm_ra_ls.erl
+++ b/lib/hipe/arm/hipe_arm_ra_ls.erl
@@ -23,15 +23,12 @@
 -module(hipe_arm_ra_ls).
 -export([ra/3]).
 
-ra(Defun, SpillIndex, Options) ->
-  NewDefun = Defun, %% hipe_${ARCH}_ra_rename:rename(Defun,Options),
-  CFG = hipe_arm_cfg:init(NewDefun),
+ra(CFG, SpillIndex, Options) ->
   SpillLimit = hipe_arm_specific:number_of_temporaries(CFG),
-  alloc(NewDefun, SpillIndex, SpillLimit, Options).
+  alloc(CFG, SpillIndex, SpillLimit, Options).
 
-alloc(Defun, SpillIndex, SpillLimit, Options) ->
-  CFG = hipe_arm_cfg:init(Defun),
-  {Coloring, _NewSpillIndex} =
+alloc(CFG, SpillIndex, SpillLimit, Options) ->
+  {Coloring, _NewSpillIndex, Liveness} =
     regalloc(
       CFG,
       hipe_arm_registers:allocatable_gpr()--
@@ -41,16 +38,16 @@ alloc(Defun, SpillIndex, SpillLimit, Options) ->
       [hipe_arm_cfg:start_label(CFG)],
       SpillIndex, SpillLimit, Options,
       hipe_arm_specific),
-  {NewDefun, _DidSpill} =
+  {NewCFG, _DidSpill} =
     hipe_arm_ra_postconditions:check_and_rewrite(
-      Defun, Coloring, 'linearscan'),
+      CFG, 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),
-  {NewDefun, Coloring2}.
+  {NewCFG, Coloring2}.
 
 regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
   hipe_ls_regalloc:regalloc(
diff --git a/lib/hipe/arm/hipe_arm_ra_naive.erl b/lib/hipe/arm/hipe_arm_ra_naive.erl
index 6201269f44..0ea4b04092 100644
--- a/lib/hipe/arm/hipe_arm_ra_naive.erl
+++ b/lib/hipe/arm/hipe_arm_ra_naive.erl
@@ -24,7 +24,7 @@
 
 -include("hipe_arm.hrl").
 
-ra(Defun, _Coloring_fp, _Options) ->	% -> {Defun, Coloring}
-  {NewDefun,_DidSpill} =
-    hipe_arm_ra_postconditions:check_and_rewrite2(Defun, [], 'naive'),
-  {NewDefun, []}.
+ra(CFG, _Coloring_fp, _Options) ->	% -> {CFG, Coloring}
+  {NewCFG,_DidSpill} =
+    hipe_arm_ra_postconditions:check_and_rewrite2(CFG, [], 'naive'),
+  {NewCFG, []}.
diff --git a/lib/hipe/arm/hipe_arm_ra_postconditions.erl b/lib/hipe/arm/hipe_arm_ra_postconditions.erl
index 40978e65f6..04365f29b0 100644
--- a/lib/hipe/arm/hipe_arm_ra_postconditions.erl
+++ b/lib/hipe/arm/hipe_arm_ra_postconditions.erl
@@ -25,17 +25,13 @@
 
 -include("hipe_arm.hrl").
 
-check_and_rewrite(Defun, Coloring, Allocator) ->
+check_and_rewrite(CFG, Coloring, Allocator) ->
   TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_arm_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(arm)},
-  {Defun#defun{code=Code1, var_range=VarRange},
-   DidSpill}.
+  do_bbs(hipe_arm_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_arm_cfg:bb(CFG0, Lbl)),
+  {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0),
+  CFG = hipe_arm_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/arm/hipe_rtl_to_arm.erl b/lib/hipe/arm/hipe_rtl_to_arm.erl
index 93342aba33..2f9181d517 100644
--- a/lib/hipe/arm/hipe_rtl_to_arm.erl
+++ b/lib/hipe/arm/hipe_rtl_to_arm.erl
@@ -138,7 +138,6 @@ mk_shift(S, Dst, Src1, ShiftOp, Src2) ->
   end.
 
 mk_shift_ii(S, Dst, Src1, ShiftOp, Src2) ->
-  io:format("~w: RTL alu with two immediates\n", [?MODULE]),
   Tmp = new_untagged_temp(),
   mk_li(Tmp, Src1,
 	mk_shift_ri(S, Dst, Tmp, ShiftOp, Src2)).
@@ -179,7 +178,6 @@ mk_arith(S, Dst, Src1, ArithOp, Src2) ->
   end.
 
 mk_arith_ii(S, Dst, Src1, ArithOp, Src2) ->
-  io:format("~w: RTL alu with two immediates\n", [?MODULE]),
   Tmp = new_untagged_temp(),
   mk_li(Tmp, Src1,
 	mk_arith_ri(S, Dst, Tmp, ArithOp, Src2)).
@@ -277,7 +275,6 @@ mk_branch(Src1, Cond, Src2, TrueLab, FalseLab, Pred) ->
   end.
 
 mk_branch_ii(Imm1, Cond, Imm2, TrueLab, FalseLab, Pred) ->
-  io:format("~w: RTL branch with two immediates\n", [?MODULE]),
   Tmp = new_untagged_temp(),
   mk_li(Tmp, Imm1,
 	mk_branch_ri(Tmp, Cond, Imm2,
@@ -472,7 +469,6 @@ mk_load(Dst, Base1, Base2, LoadSize, LoadSign) ->
   end.
 
 mk_load_ii(Dst, Base1, Base2, LdOp) ->
-  io:format("~w: RTL load with two immediates\n", [?MODULE]),
   Tmp = new_untagged_temp(),
   mk_li(Tmp, Base1,
 	mk_load_ri(Dst, Tmp, Base2, LdOp)).
@@ -485,7 +481,6 @@ mk_load_rr(Dst, Base1, Base2, LdOp) ->
   [hipe_arm:mk_load(LdOp, Dst, Am2)].
 
 mk_ldrsb_ii(Dst, Base1, Base2) ->
-  io:format("~w: RTL load signed byte with two immediates\n", [?MODULE]),
   Tmp = new_untagged_temp(),
   mk_li(Tmp, Base1,
 	mk_ldrsb_ri(Dst, Tmp, Base2)).
@@ -543,7 +538,7 @@ conv_return(I, Map, Data) ->
   {I2, Map0, Data}.
 
 conv_store(I, Map, Data) ->
-  {Base, Map0} = conv_dst(hipe_rtl:store_base(I), Map),
+  {Base, Map0} = conv_src(hipe_rtl:store_base(I), Map),
   {Src, Map1} = conv_src(hipe_rtl:store_src(I), Map0),
   {Offset, Map2} = conv_src(hipe_rtl:store_offset(I), Map1),
   StoreSize = hipe_rtl:store_size(I),
@@ -567,13 +562,28 @@ mk_store(Src, Base, Offset, StoreSize) ->
   end.
 
 mk_store2(Src, Base, Offset, StOp) ->
-  case hipe_arm:is_temp(Offset) of
+  case hipe_arm:is_temp(Base) of
     true ->
-      mk_store_rr(Src, Base, Offset, StOp);
-    _ ->
-      mk_store_ri(Src, Base, Offset, StOp)
+      case hipe_arm:is_temp(Offset) of
+	true ->
+	  mk_store_rr(Src, Base, Offset, StOp);
+	_ ->
+	  mk_store_ri(Src, Base, Offset, StOp)
+      end;
+    false ->
+      case hipe_arm:is_temp(Offset) of
+	true ->
+	  mk_store_ri(Src, Offset, Base, StOp);
+	_ ->
+	  mk_store_ii(Src, Base, Offset, StOp)
+      end
   end.
-  
+
+mk_store_ii(Src, Base, Offset, StOp) ->
+  Tmp = new_untagged_temp(),
+  mk_li(Tmp, Base,
+	mk_store_ri(Src, Tmp, Offset, StOp)).
+
 mk_store_ri(Src, Base, Offset, StOp) ->
   hipe_arm:mk_store(StOp, Src, Base, Offset, 'new', []).
    
diff --git a/lib/hipe/flow/cfg.inc b/lib/hipe/flow/cfg.inc
index a18bfbc526..cb5f397f64 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 
@@ -89,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.
 
 %%=====================================================================
@@ -307,11 +310,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 +338,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/main/hipe.app.src b/lib/hipe/main/hipe.app.src
index acae2c637d..6c3a2741b3 100644
--- a/lib/hipe/main/hipe.app.src
+++ b/lib/hipe/main/hipe.app.src
@@ -49,12 +49,12 @@
 	     hipe_amd64_ra_naive,
 	     hipe_amd64_ra_postconditions,
 	     hipe_amd64_ra_sse2_postconditions,
-	     hipe_amd64_ra_x87_ls,
 	     hipe_amd64_registers,
 	     hipe_amd64_specific,
 	     hipe_amd64_specific_sse2,
 	     hipe_amd64_specific_x87,
 	     hipe_amd64_spill_restore,
+	     hipe_amd64_sse2,
 	     hipe_amd64_x87,
 	     hipe_arm,
 	     hipe_arm_assemble,
@@ -217,7 +217,6 @@
 	     hipe_x86_ra_ls,
 	     hipe_x86_ra_naive,
 	     hipe_x86_ra_postconditions,
-	     hipe_x86_ra_x87_ls,
 	     hipe_x86_registers,
 	     hipe_x86_specific,
 	     hipe_x86_specific_x87,
diff --git a/lib/hipe/main/hipe.erl b/lib/hipe/main/hipe.erl
index 6c525dd143..4e6de2e0dc 100644
--- a/lib/hipe/main/hipe.erl
+++ b/lib/hipe/main/hipe.erl
@@ -1118,9 +1118,10 @@ help_hiper() ->
 
 help_options() ->
   HostArch = erlang:system_info(hipe_architecture),
-  O1 = expand_options([o1], HostArch),
-  O2 = expand_options([o2], HostArch),
-  O3 = expand_options([o3], HostArch),
+  O0 = expand_options([o0] ++ ?COMPILE_DEFAULTS, HostArch),
+  O1 = expand_options([o1] ++ ?COMPILE_DEFAULTS, HostArch),
+  O2 = expand_options([o2] ++ ?COMPILE_DEFAULTS, HostArch),
+  O3 = expand_options([o3] ++ ?COMPILE_DEFAULTS, HostArch),
   io:format("HiPE Compiler Options\n" ++
 	    " Boolean-valued options generally have corresponding " ++
 	    "aliases `no_...',\n" ++
@@ -1139,15 +1140,16 @@ help_options() ->
 	    "   pp_x86 = pp_native,\n" ++
 	    "   pp_amd64 = pp_native,\n" ++
 	    "   pp_ppc = pp_native,\n" ++
-	    "   o0,\n" ++
-	    "   o1 = ~p,\n" ++
+	    "   o0 = ~p,\n" ++
+	    "   o1 = ~p ++ o0,\n" ++
 	    "   o2 = ~p ++ o1,\n" ++
 	    "   o3 = ~p ++ o2.\n",
 	    [ordsets:from_list([verbose, debug, time, load, pp_beam,
 				pp_icode, pp_rtl, pp_native, pp_asm,
 				timeout]),
 	     expand_options([pp_all], HostArch),
-	     O1 -- [o1],
+	     O0 -- [o0],
+	     (O1 -- O0) -- [o1],
 	     (O2 -- O1) -- [o2],
 	     (O3 -- O2) -- [o3]]),
   ok.
@@ -1382,8 +1384,15 @@ opt_keys() ->
 
 %% Definitions:
 
+o0_opts(_TargetArch) ->
+  [concurrent_comp, {regalloc,linear_scan}].
+
 o1_opts(TargetArch) ->
-  Common = [inline_fp, pmatch, peephole],
+  Common = [inline_fp, pmatch, peephole,
+	    icode_ssa_const_prop, icode_ssa_copy_prop, icode_inline_bifs,
+	    rtl_ssa, rtl_ssa_const_prop, rtl_ssapre,
+	    spillmin_color, use_indexing, remove_comments,
+	    binary_opt, {regalloc,coalescing} | o0_opts(TargetArch)],
   case TargetArch of
     ultrasparc ->
       Common;
@@ -1402,11 +1411,8 @@ o1_opts(TargetArch) ->
   end.
 
 o2_opts(TargetArch) ->
-  Common = [icode_ssa_const_prop, icode_ssa_copy_prop, % icode_ssa_struct_reuse,
-	    icode_type, icode_inline_bifs, icode_call_elim, rtl_lcm,
-	    rtl_ssa, rtl_ssa_const_prop,
-	    spillmin_color, use_indexing, remove_comments,
-	    concurrent_comp, binary_opt | o1_opts(TargetArch)],
+  Common = [icode_type, icode_call_elim, % icode_ssa_struct_reuse,
+	    rtl_lcm | (o1_opts(TargetArch) -- [rtl_ssapre])],
   case TargetArch of
     T when T =:= amd64 orelse T =:= ppc64 -> % 64-bit targets
       [icode_range | Common];
@@ -1416,7 +1422,7 @@ o2_opts(TargetArch) ->
 
 o3_opts(TargetArch) ->
   %% no point checking for target architecture since this is checked in 'o1'
-  [icode_range, {regalloc,coalescing} | o2_opts(TargetArch)].
+  [icode_range | o2_opts(TargetArch)].
 
 %% Note that in general, the normal form for options should be positive.
 %% This is a good programming convention, so that tests in the code say
@@ -1481,7 +1487,8 @@ opt_basic_expansions() ->
   [{pp_all, [pp_beam, pp_icode, pp_rtl, pp_native]}].
 
 opt_expansions(TargetArch) ->
-  [{o1, o1_opts(TargetArch)},
+  [{o0, o0_opts(TargetArch)},
+   {o1, o1_opts(TargetArch)},
    {o2, o2_opts(TargetArch)},
    {o3, o3_opts(TargetArch)},
    {to_llvm, llvm_opts(o3, TargetArch)},
@@ -1528,13 +1535,21 @@ expand_kt2(Opts) ->
 
 -spec expand_options(comp_options(), hipe_architecture()) -> comp_options().
 
-expand_options(Opts, TargetArch) ->
+expand_options(Opts0, TargetArch) ->
+  Opts1 = proplists:normalize(Opts0, [{aliases, opt_aliases()}]),
+  Opts = normalise_opt_options(Opts1),
   proplists:normalize(Opts, [{negations, opt_negations()},
-			     {aliases, opt_aliases()},
 			     {expand, opt_basic_expansions()},
 			     {expand, opt_expansions(TargetArch)},
 			     {negations, opt_negations()}]).
 
+normalise_opt_options([o0|Opts]) -> [o0] ++ (Opts -- [o0, o1, o2, o3]);
+normalise_opt_options([o1|Opts]) -> [o1] ++ (Opts -- [o0, o1, o2, o3]);
+normalise_opt_options([o2|Opts]) -> [o2] ++ (Opts -- [o0, o1, o2, o3]);
+normalise_opt_options([o3|Opts]) -> [o3] ++ (Opts -- [o0, o1, o2, o3]);
+normalise_opt_options([O|Opts]) -> [O|normalise_opt_options(Opts)];
+normalise_opt_options([]) -> [].
+
 -spec check_options(comp_options()) -> 'ok'.
 
 check_options(Opts) ->
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_cfg.erl b/lib/hipe/ppc/hipe_ppc_cfg.erl
index 34d4bf54c5..ee9b4432e0 100644
--- a/lib/hipe/ppc/hipe_ppc_cfg.erl
+++ b/lib/hipe/ppc/hipe_ppc_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]).
 -export([linearise/1, params/1, reverse_postorder/1]).
@@ -34,6 +35,7 @@
 -define(BREADTH_ORDER,true).
 -define(PARAMS_NEEDED,true).
 -define(START_LABEL_UPDATE_NEEDED,true).
+-define(MAP_FOLD_NEEDED,true).
 
 -include("hipe_ppc.hrl").
 -include("../flow/cfg.hrl").
diff --git a/lib/hipe/ppc/hipe_ppc_frame.erl b/lib/hipe/ppc/hipe_ppc_frame.erl
index ff0450270f..8d37159ad8 100644
--- a/lib/hipe/ppc/hipe_ppc_frame.erl
+++ b/lib/hipe/ppc/hipe_ppc_frame.erl
@@ -24,16 +24,14 @@
 -include("hipe_ppc.hrl").
 -include("../rtl/hipe_literals.hrl").
 
-frame(Defun) ->
-  Formals = fix_formals(hipe_ppc:defun_formals(Defun)),
-  Temps0 = all_temps(hipe_ppc:defun_code(Defun), Formals),
-  MinFrame = defun_minframe(Defun),
+frame(CFG) ->
+  Formals = fix_formals(hipe_ppc_cfg:params(CFG)),
+  Temps0 = all_temps(CFG, Formals),
+  MinFrame = defun_minframe(CFG),
   Temps = ensure_minframe(MinFrame, Temps0),
-  ClobbersLR = clobbers_lr(hipe_ppc:defun_code(Defun)),
-  CFG0 = hipe_ppc_cfg:init(Defun),
-  Liveness = hipe_ppc_liveness_all:analyse(CFG0),
-  CFG1 = do_body(CFG0, Liveness, Formals, Temps, ClobbersLR),
-  hipe_ppc_cfg:linearise(CFG1).
+  ClobbersLR = clobbers_lr(CFG),
+  Liveness = hipe_ppc_liveness_all:analyse(CFG),
+  do_body(CFG, Liveness, Formals, Temps, ClobbersLR).
 
 fix_formals(Formals) ->
   fix_formals(hipe_ppc_registers:nr_args(), Formals).
@@ -44,27 +42,16 @@ fix_formals(_, []) -> [].
 
 do_body(CFG0, Liveness, Formals, Temps, ClobbersLR) ->
   Context = mk_context(Liveness, Formals, Temps, ClobbersLR),
-  CFG1 = do_blocks(CFG0, Context),
+  CFG1 = hipe_ppc_cfg:map_bbs(
+	   fun(Lbl, BB) -> do_block(Lbl, BB, Context) end, CFG0),
   do_prologue(CFG1, Context).
 
-do_blocks(CFG, Context) ->
-  Labels = hipe_ppc_cfg:labels(CFG),
-  do_blocks(Labels, CFG, Context).
-
-do_blocks([Label|Labels], CFG, Context) ->
+do_block(Label, Block, Context) ->
   Liveness = context_liveness(Context),
   LiveOut = hipe_ppc_liveness_all:liveout(Liveness, Label),
-  Block = hipe_ppc_cfg:bb(CFG, Label),
   Code = hipe_bb:code(Block),
-  NewCode = do_block(Code, LiveOut, Context),
-  NewBlock = hipe_bb:code_update(Block, NewCode),
-  NewCFG = hipe_ppc_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),
@@ -573,29 +560,41 @@ temp_is_pseudo(Temp) ->
 %%% Detect if a Defun's body clobbers LR.
 %%%
 
-clobbers_lr([I|Insns]) ->
-  case I of
-    #pseudo_call{} -> true;
-    %% mtspr to lr cannot occur yet
-    _ -> clobbers_lr(Insns)
-  end;
-clobbers_lr([]) -> false.
+clobbers_lr(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_ppc_defuse:insn_def_all(I)),
-  S2 = tset_add_list(S1, hipe_ppc_defuse:insn_use_all(I)),
-  find_temps(Insns, S2);
-find_temps([], S) ->
-  S.
+  tset_add_list(S1, hipe_ppc_defuse:insn_use_all(I)).
+
+fold_insns(Fun, InitAcc, CFG) ->
+  hipe_ppc_cfg:fold_bbs(
+    fun(_, BB, Acc0) -> lists:foldl(Fun, Acc0, hipe_bb:code(BB)) end,
+    InitAcc, CFG).
 
 tset_empty() ->
   gb_sets:new().
@@ -624,16 +623,11 @@ tset_to_list(S) ->
 %%% in the middle of a tailcall.
 %%%
 
-defun_minframe(Defun) ->
-  MaxTailArity = body_mta(hipe_ppc:defun_code(Defun), 0),
-  MyArity = length(fix_formals(hipe_ppc:defun_formals(Defun))),
+defun_minframe(CFG) ->
+  MaxTailArity = fold_insns(fun insn_mta/2, 0, CFG),
+  MyArity = length(fix_formals(hipe_ppc_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/ppc/hipe_ppc_main.erl b/lib/hipe/ppc/hipe_ppc_main.erl
index fd5cc2befb..5d1b0d0305 100644
--- a/lib/hipe/ppc/hipe_ppc_main.erl
+++ b/lib/hipe/ppc/hipe_ppc_main.erl
@@ -24,8 +24,10 @@
 
 rtl_to_ppc(MFA, RTL, Options) ->
   PPC1 = hipe_rtl_to_ppc:translate(RTL),
-  PPC2 = hipe_ppc_ra:ra(PPC1, Options),
-  PPC3 = hipe_ppc_frame:frame(PPC2),
+  PPC1CFG = hipe_ppc_cfg:init(PPC1),
+  PPC2CFG = hipe_ppc_ra:ra(PPC1CFG, Options),
+  PPC3CFG = hipe_ppc_frame:frame(PPC2CFG),
+  PPC3 = hipe_ppc_cfg:linearise(PPC3CFG),
   PPC4 = hipe_ppc_finalise:finalise(PPC3),
   ppc_pp(PPC4, MFA, Options),
   {native, powerpc, {unprofiled, PPC4}}.
diff --git a/lib/hipe/ppc/hipe_ppc_ra.erl b/lib/hipe/ppc/hipe_ppc_ra.erl
index 87c776f5d1..bfb4d35139 100644
--- a/lib/hipe/ppc/hipe_ppc_ra.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra.erl
@@ -22,36 +22,36 @@
 -module(hipe_ppc_ra).
 -export([ra/2]).
 
-ra(Defun0, Options) ->
-  %% hipe_ppc_pp:pp(Defun0),
-  {Defun1, Coloring_fp, SpillIndex}
+ra(CFG0, Options) ->
+  %% hipe_ppc_pp:pp(hipe_ppc_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_ppc_specific_fp);
 	false ->
-	  {Defun0,[],0}
+	  {CFG0,[],0}
       end,
-  %% hipe_ppc_pp:pp(Defun1),
-  {Defun2, Coloring}
+  %% hipe_ppc_pp:pp(hipe_ppc_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_ppc_ra_ls:ra(Defun1, SpillIndex, Options);
+	  hipe_ppc_ra_ls:ra(CFG1, SpillIndex, Options);
 	naive ->
-	  hipe_ppc_ra_naive:ra(Defun1, Coloring_fp, Options);
+	  hipe_ppc_ra_naive:ra(CFG1, Coloring_fp, Options);
         _ ->
 	  exit({unknown_regalloc_compiler_option,
 		proplists:get_value(regalloc,Options)})
       end,
-  %% hipe_ppc_pp:pp(Defun2),
-  hipe_ppc_ra_finalise:finalise(Defun2, Coloring, Coloring_fp).
+  %% hipe_ppc_pp:pp(hipe_ppc_cfg:linearise(CFG2)),
+  hipe_ppc_ra_finalise:finalise(CFG2, Coloring, Coloring_fp).
 
-ra(Defun, SpillIndex, Options, RegAllocMod) ->
-  hipe_regalloc_loop:ra(Defun, SpillIndex, Options, RegAllocMod, hipe_ppc_specific).
+ra(CFG, SpillIndex, Options, RegAllocMod) ->
+  hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, hipe_ppc_specific).
diff --git a/lib/hipe/ppc/hipe_ppc_ra_finalise.erl b/lib/hipe/ppc/hipe_ppc_ra_finalise.erl
index ea163221c2..78f123116e 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_finalise.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_finalise.erl
@@ -23,13 +23,14 @@
 -export([finalise/3]).
 -include("hipe_ppc.hrl").
 
-finalise(Defun, TempMap, FPMap0) ->
-  Code = hipe_ppc:defun_code(Defun),
-  {_, SpillLimit} = hipe_ppc:defun_var_range(Defun),
+finalise(CFG, TempMap, FPMap0) ->
+  {_, SpillLimit} = hipe_gensym:var_range(ppc),
   Map = mk_ra_map(TempMap, SpillLimit),
   FPMap1 = mk_ra_map_fp(FPMap0, SpillLimit),
-  NewCode = ra_code(Code, Map, FPMap1, []),
-  Defun#defun{code=NewCode}.
+  hipe_ppc_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/ppc/hipe_ppc_ra_ls.erl b/lib/hipe/ppc/hipe_ppc_ra_ls.erl
index 6e8304467e..52562fc321 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_ls.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_ls.erl
@@ -23,15 +23,12 @@
 -module(hipe_ppc_ra_ls).
 -export([ra/3]).
 
-ra(Defun, SpillIndex, Options) ->
-  NewDefun = Defun, %% hipe_${ARCH}_ra_rename:rename(Defun,Options),
-  CFG = hipe_ppc_cfg:init(NewDefun),
+ra(CFG, SpillIndex, Options) ->
   SpillLimit = hipe_ppc_specific:number_of_temporaries(CFG),
-  alloc(NewDefun, SpillIndex, SpillLimit, Options).
+  alloc(CFG, SpillIndex, SpillLimit, Options).
 
-alloc(Defun, SpillIndex, SpillLimit, Options) ->
-  CFG = hipe_ppc_cfg:init(Defun),
-  {Coloring, _NewSpillIndex} =
+alloc(CFG, SpillIndex, SpillLimit, Options) ->
+  {Coloring, _NewSpillIndex, Liveness} =
     regalloc(
       CFG,
       hipe_ppc_registers:allocatable_gpr()--
@@ -41,16 +38,16 @@ alloc(Defun, SpillIndex, SpillLimit, Options) ->
       [hipe_ppc_cfg:start_label(CFG)],
       SpillIndex, SpillLimit, Options,
       hipe_ppc_specific),
-  {NewDefun, _DidSpill} =
+  {NewCFG, _DidSpill} =
     hipe_ppc_ra_postconditions:check_and_rewrite(
-      Defun, Coloring, 'linearscan'),
+      CFG, 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),
-  {NewDefun, Coloring2}.
+  {NewCFG, Coloring2}.
 
 regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
   hipe_ls_regalloc:regalloc(
diff --git a/lib/hipe/ppc/hipe_ppc_ra_naive.erl b/lib/hipe/ppc/hipe_ppc_ra_naive.erl
index 24995be252..ba269ae981 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_naive.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_naive.erl
@@ -24,7 +24,7 @@
 
 -include("hipe_ppc.hrl").
 
-ra(Defun, _Coloring_fp, _Options) ->	% -> {Defun, Coloring}
-  {NewDefun,_DidSpill} =
-    hipe_ppc_ra_postconditions:check_and_rewrite2(Defun, [], 'naive'),
-  {NewDefun, []}.
+ra(CFG, _Coloring_fp, _Options) ->	% -> {CFG, Coloring}
+  {NewCFG,_DidSpill} =
+    hipe_ppc_ra_postconditions:check_and_rewrite2(CFG, [], 'naive'),
+  {NewCFG, []}.
diff --git a/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl b/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl
index 0b16ec3891..412aeeeba6 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl
@@ -25,17 +25,13 @@
 
 -include("hipe_ppc.hrl").
 
-check_and_rewrite(Defun, Coloring, Allocator) ->
+check_and_rewrite(CFG, Coloring, Allocator) ->
   TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_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(ppc)},
-  {Defun#defun{code=Code1, var_range=VarRange},
-   DidSpill}.
+  do_bbs(hipe_ppc_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_ppc_cfg:bb(CFG0, Lbl)),
+  {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0),
+  CFG = hipe_ppc_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/ppc/hipe_ppc_ra_postconditions_fp.erl b/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl
index 821aa66c11..553fac882b 100644
--- a/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl
+++ b/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl
@@ -23,13 +23,16 @@
 -export([check_and_rewrite/2]).
 -include("hipe_ppc.hrl").
 
-check_and_rewrite(Defun, Coloring) ->
+check_and_rewrite(CFG, Coloring) ->
   TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific_fp),
-  #defun{code=Code0} = Defun,
-  {Code1,DidSpill} = do_insns(Code0, TempMap, [], false),
-  VarRange = {0, hipe_gensym:get_var(ppc)},
-  {Defun#defun{code=Code1, var_range=VarRange},
-   DidSpill}.
+  do_bbs(hipe_ppc_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_ppc_cfg:bb(CFG0, Lbl)),
+  {Code, DidSpill} = do_insns(Code0, TempMap, [], DidSpill0),
+  CFG = hipe_ppc_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),
diff --git a/lib/hipe/ppc/hipe_rtl_to_ppc.erl b/lib/hipe/ppc/hipe_rtl_to_ppc.erl
index a994659616..a01e67a789 100644
--- a/lib/hipe/ppc/hipe_rtl_to_ppc.erl
+++ b/lib/hipe/ppc/hipe_rtl_to_ppc.erl
@@ -1031,7 +1031,7 @@ conv_return(I, Map, Data) ->
   {I2, Map0, Data}.
 
 conv_store(I, Map, Data) ->
-  {Base1, Map0} = conv_dst(hipe_rtl:store_base(I), Map),
+  {Base1, Map0} = conv_src(hipe_rtl:store_base(I), Map),
   {Src, Map1} = conv_src(hipe_rtl:store_src(I), Map0),
   {Base2, Map2} = conv_src(hipe_rtl:store_offset(I), Map1),
   StoreSize = hipe_rtl:store_size(I),
@@ -1056,13 +1056,28 @@ mk_store(Src, Base1, Base2, StoreSize) ->
   end.
 
 mk_store2(Src, Base1, Base2, StOp) ->
-  case hipe_ppc:is_temp(Base2) of
+  case hipe_ppc:is_temp(Base1) of
     true ->
-      mk_store_rr(Src, Base1, Base2, StOp);
+      case hipe_ppc:is_temp(Base2) of
+	true ->
+	  mk_store_rr(Src, Base1, Base2, StOp);
+	_ ->
+	  mk_store_ri(Src, Base1, Base2, StOp)
+      end;
     _ ->
-      mk_store_ri(Src, Base1, Base2, StOp)
+      case hipe_ppc:is_temp(Base2) of
+	true ->
+	  mk_store_ri(Src, Base2, Base1, StOp);
+	_ ->
+	  mk_store_ii(Src, Base1, Base2, StOp)
+      end
   end.
-  
+
+mk_store_ii(Src, Base, Disp, StOp) ->
+  Tmp = new_untagged_temp(),
+  mk_li(Tmp, Base,
+	mk_store_ri(Src, Tmp, Disp, StOp)).
+
 mk_store_ri(Src, Base, Disp, StOp) ->
   hipe_ppc:mk_store(StOp, Src, Disp, Base, 'new', []).
 
diff --git a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
index 50e5869d45..2e5804337d 100644
--- a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
+++ b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
@@ -42,7 +42,9 @@
          reg_nr/1,
 	 non_alloc/1,
 	 allocatable/0,
-         physical_name/1,
+	 allocatable/1,
+	 temp0/0,
+	 physical_name/1,
 	 all_precoloured/0,
 	 new_spill_index/1,	%% used by hipe_ls_regalloc
 	 var_range/1,
@@ -52,7 +54,8 @@
 
 %% callbacks for hipe_regalloc_loop
 -export([defun_to_cfg/1,
-	 check_and_rewrite/2]).
+	 check_and_rewrite/2,
+	 check_and_rewrite/3]).
 
 %%----------------------------------------------------------------------------
 
@@ -60,11 +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(CFG, Coloring, Strategy) ->
+  hipe_amd64_ra_sse2_postconditions:check_and_rewrite(
+    CFG, Coloring, Strategy).
 
 reverse_postorder(CFG) ->
   hipe_x86_cfg:reverse_postorder(CFG).
@@ -75,8 +82,8 @@ breadthorder(CFG) ->
 postorder(CFG) ->
   hipe_x86_cfg:postorder(CFG).
 
-is_global(_Reg) ->
-  false.
+is_global(Reg) ->
+  hipe_amd64_registers:sse2_temp0() =:= Reg.
  
 is_fixed(_Reg) ->
   false.
@@ -109,7 +116,16 @@ liveout(BB_in_out_liveness, Label) ->
 %% Registers stuff
 
 allocatable() ->
-  hipe_amd64_registers:allocatable_sse2().
+  allocatable('normal').
+
+allocatable('normal') ->
+  hipe_amd64_registers:allocatable_sse2();
+allocatable('linearscan') ->
+  hipe_amd64_registers:allocatable_sse2() --
+    [hipe_amd64_registers:sse2_temp0()].
+
+temp0() ->
+  hipe_amd64_registers:sse2_temp0().
 
 all_precoloured() ->
   allocatable().
diff --git a/lib/hipe/regalloc/hipe_arm_specific.erl b/lib/hipe/regalloc/hipe_arm_specific.erl
index 4e34cb1d99..e04d80f690 100644
--- a/lib/hipe/regalloc/hipe_arm_specific.erl
+++ b/lib/hipe/regalloc/hipe_arm_specific.erl
@@ -53,11 +53,11 @@
 -export([defun_to_cfg/1,
 	 check_and_rewrite/2]).
 
-defun_to_cfg(Defun) ->
-  hipe_arm_cfg:init(Defun).
+defun_to_cfg(AlreadyACFG) ->
+  AlreadyACFG.
 
-check_and_rewrite(Defun, Coloring) ->
-  hipe_arm_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal').
+check_and_rewrite(CFG, Coloring) ->
+  hipe_arm_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal').
 
 reverse_postorder(CFG) ->
   hipe_arm_cfg:reverse_postorder(CFG).
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_ppc_specific.erl b/lib/hipe/regalloc/hipe_ppc_specific.erl
index c49b1e510f..988501c96f 100644
--- a/lib/hipe/regalloc/hipe_ppc_specific.erl
+++ b/lib/hipe/regalloc/hipe_ppc_specific.erl
@@ -53,11 +53,11 @@
 -export([defun_to_cfg/1,
 	 check_and_rewrite/2]).
 
-defun_to_cfg(Defun) ->
-  hipe_ppc_cfg:init(Defun).
+defun_to_cfg(AlreadyACFG) ->
+  AlreadyACFG.
 
-check_and_rewrite(Defun, Coloring) ->
-  hipe_ppc_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal').
+check_and_rewrite(CFG, Coloring) ->
+  hipe_ppc_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal').
 
 reverse_postorder(CFG) ->
   hipe_ppc_cfg:reverse_postorder(CFG).
diff --git a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
index 454aa4c686..6f00111777 100644
--- a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
+++ b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
@@ -53,11 +53,11 @@
 -export([defun_to_cfg/1,
 	 check_and_rewrite/2]).
 
-defun_to_cfg(Defun) ->
-  hipe_ppc_cfg:init(Defun).
+defun_to_cfg(AlreadyACFG) ->
+  AlreadyACFG.
 
-check_and_rewrite(Defun, Coloring) ->
-  hipe_ppc_ra_postconditions_fp:check_and_rewrite(Defun, Coloring).
+check_and_rewrite(CFG, Coloring) ->
+  hipe_ppc_ra_postconditions_fp:check_and_rewrite(CFG, Coloring).
 
 reverse_postorder(CFG) ->
   hipe_ppc_cfg:reverse_postorder(CFG).
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/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/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 ece07cb2f9..0c022d5a27 100644
--- a/lib/hipe/regalloc/hipe_x86_specific_x87.erl
+++ b/lib/hipe/regalloc/hipe_x86_specific_x87.erl
@@ -32,7 +32,7 @@
 -endif.
 
 -module(?HIPE_X86_SPECIFIC_X87).
--export([allocatable/0,
+-export([allocatable/1,
 	 is_precoloured/1,
 	 %% var_range/1,
 	 %% def_use/1,
@@ -58,7 +58,14 @@
 	 physical_name/1,
 	 breadthorder/1,
 	 postorder/1,
- 	 reverse_postorder/1]).
+	 reverse_postorder/1]).
+
+%% callbacks for hipe_x86_ra_ls
+-export([check_and_rewrite/3]).
+
+%% Rewrite happens in hipe_x86_ra_finalise:finalise/4
+check_and_rewrite(CFG, _Coloring, 'linearscan') ->
+  {CFG, false}.
 
 breadthorder(CFG) ->
   hipe_x86_cfg:breadthorder(CFG).
@@ -103,7 +110,7 @@ liveout(BB_in_out_liveness,Label) ->
 
 %% Registers stuff
 
-allocatable() ->
+allocatable('linearscan') ->
   ?HIPE_X86_REGISTERS:allocatable_x87().
 
 is_precoloured(Reg) ->
diff --git a/lib/hipe/rtl/hipe_rtl_binary.erl b/lib/hipe/rtl/hipe_rtl_binary.erl
index fb9c0c196d..ad23df80d2 100644
--- a/lib/hipe/rtl/hipe_rtl_binary.erl
+++ b/lib/hipe/rtl/hipe_rtl_binary.erl
@@ -106,10 +106,20 @@ create_lbls(0) ->
 %%------------------------------------------------------------------------------
 
 get_word_integer(Var, Register, SystemLimitLblName, FalseLblName) ->
-  [EndLbl] = create_lbls(1),
-  EndName = hipe_rtl:label_name(EndLbl),
-  get_word_integer(Var, Register,SystemLimitLblName,  FalseLblName, EndName, EndName,
-		   [EndLbl]).
+  case hipe_rtl:is_imm(Var) of
+    true ->
+      TaggedVal = hipe_rtl:imm_value(Var),
+      true = hipe_tagscheme:is_fixnum(TaggedVal),
+      Val = hipe_tagscheme:fixnum_val(TaggedVal),
+      if Val < 0 -> [hipe_rtl:mk_goto(FalseLblName)];
+	true -> [hipe_rtl:mk_move(Register, hipe_rtl:mk_imm(Val))]
+      end;
+    false ->
+      [EndLbl] = create_lbls(1),
+      EndName = hipe_rtl:label_name(EndLbl),
+      get_word_integer(Var, Register,SystemLimitLblName,  FalseLblName,
+		       EndName, EndName, [EndLbl])
+  end.
 
 get_word_integer(Var, Register, SystemLimitLblName, FalseLblName, TrueLblName,
 		 BigLblName, Tail) ->
diff --git a/lib/hipe/sparc/hipe_rtl_to_sparc.erl b/lib/hipe/sparc/hipe_rtl_to_sparc.erl
index f9c043eafe..e170fec3d6 100644
--- a/lib/hipe/sparc/hipe_rtl_to_sparc.erl
+++ b/lib/hipe/sparc/hipe_rtl_to_sparc.erl
@@ -625,7 +625,7 @@ conv_return(I, Map, Data) ->
   {I2, Map0, Data}.
 
 conv_store(I, Map, Data) ->
-  {Base1, Map0} = conv_dst(hipe_rtl:store_base(I), Map), % no immediates allowed
+  {Base1, Map0} = conv_src(hipe_rtl:store_base(I), Map),
   {Src, Map1} = conv_src(hipe_rtl:store_src(I), Map0),
   {Base2, Map2} = conv_src(hipe_rtl:store_offset(I), Map1),
   StOp = conv_stop(hipe_rtl:store_size(I)),
@@ -649,13 +649,27 @@ mk_store(StOp, Src, Base1, Base2) ->
   end.
 
 mk_store2(StOp, Src, Base1, Base2) ->
-  case hipe_sparc:is_temp(Base2) of
+  case hipe_sparc:is_temp(Base1) of
     true ->
-      mk_store_rr(StOp, Src, Base1, Base2);
+      case hipe_sparc:is_temp(Base2) of
+	true ->
+	  mk_store_rr(StOp, Src, Base1, Base2);
+	_ ->
+	  mk_store_ri(StOp, Src, Base1, Base2)
+      end;
     _ ->
-      mk_store_ri(StOp, Src, Base1, Base2)
+      case hipe_sparc:is_temp(Base2) of
+	true ->
+	  mk_store_ri(StOp, Src, Base2, Base1);
+	_ ->
+	  mk_store_ii(StOp, Src, Base1, Base2)
+      end
   end.
   
+mk_store_ii(StOp, Src, Base, Disp) ->
+  Tmp = new_untagged_temp(),
+  mk_set(Base, Tmp, mk_store_ri(StOp, Src, Tmp, Disp)).
+
 mk_store_ri(StOp, Src, Base, Disp) ->
   hipe_sparc:mk_store(StOp, Src, Base, Disp, 'new', []).
 
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 19e7c92d2f..ced9addd31 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_ls.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_ls.erl
@@ -23,15 +23,12 @@
 -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),
-  {Coloring, _NewSpillIndex} =
+alloc(CFG, SpillIndex, SpillLimit, Options) ->
+  {Coloring, _NewSpillIndex, Liveness} =
     regalloc(
       CFG,
       hipe_sparc_registers:allocatable_gpr()--
@@ -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, [], SpillIndex, Options,
+    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),
diff --git a/lib/hipe/test/hipe_testsuite_driver.erl b/lib/hipe/test/hipe_testsuite_driver.erl
index a3048d907e..88576775ca 100644
--- a/lib/hipe/test/hipe_testsuite_driver.erl
+++ b/lib/hipe/test/hipe_testsuite_driver.erl
@@ -99,7 +99,7 @@ write_suite(Suite) ->
 write_header(#suite{suitename = SuiteName, outputfile = OutputFile,
 		    testcases = TestCases}) ->
     Exports = format_export(TestCases),
-    TimeLimit = 5,	%% with 1 or 2 it fails on some slow machines...
+    TimeLimit = 6,	%% with 1, 2, or 3 it fails on some slow machines...
     io:format(OutputFile,
 	      "%% ATTENTION!\n"
 	      "%% This is an automatically generated file. Do not edit.\n\n"
@@ -168,6 +168,10 @@ run(TestCase, Dir, _OutDir) ->
     HiPEOpts = try TestCase:hipe_options() catch error:undef -> [] end,
     {ok, TestCase} = hipe:c(TestCase, HiPEOpts),
     ok = TestCase:test(),
+    {ok, TestCase} = hipe:c(TestCase, [o1|HiPEOpts]),
+    ok = TestCase:test(),
+    {ok, TestCase} = hipe:c(TestCase, [o0|HiPEOpts]),
+    ok = TestCase:test(),
     ToLLVM = try TestCase:to_llvm() catch error:undef -> true end,
     case ToLLVM andalso hipe:llvm_support_available() of
 	true ->
diff --git a/lib/hipe/x86/Makefile b/lib/hipe/x86/Makefile
index 93f8b955dd..9b21270426 100644
--- a/lib/hipe/x86/Makefile
+++ b/lib/hipe/x86/Makefile
@@ -60,7 +60,6 @@ MODULES=hipe_rtl_to_x86 \
 	hipe_x86_ra_ls \
 	hipe_x86_ra_naive \
 	hipe_x86_ra_postconditions \
-	hipe_x86_ra_x87_ls \
 	hipe_x86_registers \
 	hipe_x86_spill_restore \
 	hipe_x86_x87
@@ -133,7 +132,6 @@ $(EBIN)/hipe_x86_ra: ../main/hipe.hrl
 $(EBIN)/hipe_x86_ra_dummy.beam: ../main/hipe.hrl
 $(EBIN)/hipe_x86_ra_ls.beam: ../main/hipe.hrl
 $(EBIN)/hipe_x86_ra_postconditions.beam: ../main/hipe.hrl
-$(EBIN)/hipe_x86_ra_x87_ls.beam: ../main/hipe.hrl
 $(EBIN)/hipe_x86_registers.beam: ../rtl/hipe_literals.hrl
 $(EBIN)/hipe_x86_spill_restore.beam: ../main/hipe.hrl ../flow/cfg.hrl
 $(EBIN)/hipe_x86_x87.beam: ../main/hipe.hrl
diff --git a/lib/hipe/x86/hipe_rtl_to_x86.erl b/lib/hipe/x86/hipe_rtl_to_x86.erl
index d13f63b1d9..4c8c98551c 100644
--- a/lib/hipe/x86/hipe_rtl_to_x86.erl
+++ b/lib/hipe/x86/hipe_rtl_to_x86.erl
@@ -85,7 +85,7 @@ conv_insn(I, Map, Data) ->
 	  true ->
 	    conv_shift(Dst, Src1, BinOp, Src2);
 	  false ->
-	    conv_alu(Dst, Src1, BinOp, Src2, [])
+	    conv_alu_nocc(Dst, Src1, BinOp, Src2, [])
 	end,
       {FixSrc1++FixSrc2++I2, Map2, Data};
     #alub{} ->
@@ -144,7 +144,7 @@ conv_insn(I, Map, Data) ->
       {I2, Map, Data};
     #load{} ->
       {Dst, Map0} = conv_dst(hipe_rtl:load_dst(I), Map),
-      {FixSrc, Src, Map1} = conv_src(hipe_rtl:load_src(I), Map0),
+      {FixSrc, Src, Map1} = conv_src_noimm(hipe_rtl:load_src(I), Map0),
       {FixOff, Off, Map2} = conv_src(hipe_rtl:load_offset(I), Map1),
       I2 = case {hipe_rtl:load_size(I), hipe_rtl:load_sign(I)} of
 	     {byte, signed} ->
@@ -171,6 +171,7 @@ conv_insn(I, Map, Data) ->
       Src = hipe_x86:mk_imm_from_atom(hipe_rtl:load_atom_atom(I)),
       I2 = [hipe_x86:mk_move(Src, Dst)],
       {I2, Map0, Data};
+    #move{src=Dst, dst=Dst} -> {[], Map, Data};
     #move{} ->
       {Dst, Map0} = conv_dst(hipe_rtl:move_dst(I), Map),
       {FixSrc, Src, Map1} = conv_src(hipe_rtl:move_src(I), Map0),
@@ -182,11 +183,11 @@ conv_insn(I, Map, Data) ->
       I2 = move_retvals(Args, [hipe_x86:mk_ret(-1)]),
       {FixArgs++I2, Map0, Data};
     #store{} ->
-      {Ptr, Map0} = conv_dst(hipe_rtl:store_base(I), Map),
+      {FixPtr, Ptr, Map0} = conv_src_noimm(hipe_rtl:store_base(I), Map),
       {FixSrc, Src, Map1} = conv_src(hipe_rtl:store_src(I), Map0),
       {FixOff, Off, Map2} = conv_src(hipe_rtl:store_offset(I), Map1),
       I2 = mk_store(hipe_rtl:store_size(I), Src, Ptr, Off),
-      {FixSrc++FixOff++I2, Map2, Data};
+      {FixPtr++FixSrc++FixOff++I2, Map2, Data};
     #switch{} ->	% this one also updates Data :-(
       %% from hipe_rtl2sparc, but we use a hairy addressing mode
       %% instead of doing the arithmetic manually
@@ -206,7 +207,7 @@ conv_insn(I, Map, Data) ->
       {I2, Map1, NewData};
     #fload{} ->
       {Dst, Map0} = conv_dst(hipe_rtl:fload_dst(I), Map),
-      {[], Src, Map1} = conv_src(hipe_rtl:fload_src(I), Map0),
+      {[], Src, Map1} = conv_src_noimm(hipe_rtl:fload_src(I), Map0),
       {[], Off, Map2} = conv_src(hipe_rtl:fload_offset(I), Map1),
       I2 = [hipe_x86:mk_fmove(hipe_x86:mk_mem(Src, Off, 'double'),Dst)],
       {I2, Map2, Data};
@@ -249,6 +250,22 @@ conv_insn(I, Map, Data) ->
 %%% Finalise the conversion of a 3-address ALU operation, taking
 %%% care to not introduce more temps and moves than necessary.
 
+conv_alu_nocc(Dst, Src1, 'add', Src2, Tail) ->
+  case (not same_opnd(Dst, Src1)) andalso (not same_opnd(Dst, Src2))
+    andalso (hipe_x86:is_temp(Src1) orelse hipe_x86:is_temp(Src2))
+  of
+    false -> conv_alu(Dst, Src1, 'add', Src2, Tail);
+    true -> % Use LEA
+      Type = typeof_dst(Dst),
+      Mem = case hipe_x86:is_temp(Src1) of
+	      true  -> hipe_x86:mk_mem(Src1, Src2, Type);
+	      false -> hipe_x86:mk_mem(Src2, Src1, Type)
+	    end,
+      [hipe_x86:mk_lea(Mem, Dst) | Tail]
+  end;
+conv_alu_nocc(Dst, Src1, BinOp, Src2, Tail) ->
+  conv_alu(Dst, Src1, BinOp, Src2, Tail).
+
 conv_alu(Dst, Src1, 'imul', Src2, Tail) ->
   mk_imul(Src1, Src2, Dst, Tail);
 conv_alu(Dst, Src1, BinOp, Src2, Tail) ->
@@ -572,6 +589,16 @@ conv_fun(Fun, Map) ->
       end
   end.
 
+conv_src_noimm(Opnd, Map) ->
+  R={FixSrc0, Src, NewMap} = conv_src(Opnd, Map),
+  case hipe_x86:is_imm(Src) of
+    false -> R;
+    true ->
+      Tmp = new_untagged_temp(),
+      {FixSrc0 ++ [hipe_x86:mk_move(Src, Tmp)],
+       Tmp, NewMap}
+  end.
+
 %%% Convert an RTL source operand (imm/var/reg).
 
 conv_src(Opnd, Map) ->
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 f66961a7a7..3af333ab4b 100644
--- a/lib/hipe/x86/hipe_x86_ra.erl
+++ b/lib/hipe/x86/hipe_x86_ra.erl
@@ -41,60 +41,80 @@
 %%-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, 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,
-			    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, Liveness, 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) ->
-  case proplists:get_bool(inline_fp, Options) and
-       (proplists:get_value(regalloc, Options) =/= naive) of
-    true ->
-      case proplists:get_bool(x87, Options) of
-	true ->
-	  hipe_amd64_ra_x87_ls:ra(Defun, Options);
-	false ->
-	  hipe_regalloc_loop:ra_fp(Defun, Options,
-				   hipe_coalescing_regalloc,
-				   hipe_amd64_specific_sse2)
-      end;
-    false ->
-      {Defun,[],0}
+ra_fp(CFG, Options) ->
+  Regalloc0 = proplists:get_value(regalloc, Options),
+  {Regalloc, TargetMod} =
+    case proplists:get_bool(inline_fp, Options) and (Regalloc0 =/= naive) of
+      false -> {naive, undefined};
+      true ->
+	case proplists:get_bool(x87, Options) of
+	  true ->  {linear_scan, hipe_amd64_specific_x87};
+	  false -> {Regalloc0,   hipe_amd64_specific_sse2}
+	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};
+    _ ->
+      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).
 -else.
-ra_fp(Defun, Options) ->
+ra_fp(CFG, Options) ->
   case proplists:get_bool(inline_fp, Options) of
     true ->
-      hipe_x86_ra_x87_ls:ra(Defun, Options);
+      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 5dd75cb7ae..62009abb76 100644
--- a/lib/hipe/x86/hipe_x86_ra_finalise.erl
+++ b/lib/hipe/x86/hipe_x86_ra_finalise.erl
@@ -25,23 +25,36 @@
 -define(HIPE_X86_RA_FINALISE,	hipe_amd64_ra_finalise).
 -define(HIPE_X86_REGISTERS,	hipe_amd64_registers).
 -define(HIPE_X86_X87,		hipe_amd64_x87).
+-define(HIPE_X86_SSE2,		hipe_amd64_sse2).
+-define(IF_HAS_SSE2(Expr),	Expr).
 -else.
 -define(HIPE_X86_RA_FINALISE,	hipe_x86_ra_finalise).
 -define(HIPE_X86_REGISTERS,	hipe_x86_registers).
 -define(HIPE_X86_X87,		hipe_x86_x87).
+-define(IF_HAS_SSE2(Expr),).
 -endif.
 
 -module(?HIPE_X86_RA_FINALISE).
 -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);
     _ ->
-      Defun1
+      case
+	proplists:get_bool(inline_fp, Options)
+	and (proplists:get_value(regalloc, Options) =:= linear_scan)
+      of
+	%% Ugly, but required to avoid Dialyzer complaints about "Unknown
+	%% function" hipe_x86_sse2:map/1
+	?IF_HAS_SSE2(true ->
+			?HIPE_X86_SSE2:map(CFG1);)
+	false ->
+	  CFG1
+      end
   end.
 
 %%%
@@ -50,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 3e34433111..9f019f9561 100644
--- a/lib/hipe/x86/hipe_x86_ra_ls.erl
+++ b/lib/hipe/x86/hipe_x86_ra_ls.erl
@@ -35,40 +35,65 @@
 -endif.
 
 -module(?HIPE_X86_RA_LS).
--export([ra/3,regalloc/7]).
+-export([ra/4,ra_fp/3]).
 -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, Liveness, 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, Liveness, SpillIndex, SpillLimit, Options).
+
+ra_fp(CFG, Options, TargetMod) ->
+  ?inc_counter(ra_calls_counter,1),
+  %% ?inc_counter(ra_caller_saves_counter,count_caller_saves(CFG)),
+  SpillIndex = 0,
+  SpillLimit = TargetMod:number_of_temporaries(CFG),
+  ?inc_counter(bbs_counter, length(hipe_x86_cfg:labels(CFG))),
+
+  ?inc_counter(ra_iteration_counter,1),
+  %% ?HIPE_X86_PP:pp(Defun),
 
+  {Coloring,NewSpillIndex,Liveness} =
+    regalloc(CFG,
+	     undefined,
+	     TargetMod:allocatable('linearscan'),
+	     [hipe_x86_cfg:start_label(CFG)],
+	     SpillIndex, SpillLimit, Options,
+	     TargetMod),
+
+  {NewCFG, _DidSpill} =
+    TargetMod:check_and_rewrite(CFG, Coloring, 'linearscan'),
+  TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod),
+  {TempMap2, NewSpillIndex2} =
+    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, Liveness}.
 
-alloc(Defun, SpillIndex, SpillLimit, Options) ->
+alloc(CFG, Liveness0, SpillIndex, SpillLimit, Options) ->
   ?inc_counter(ra_iteration_counter,1), 
   %% ?HIPE_X86_PP:pp(Defun),	
-  CFG = hipe_x86_cfg:init(Defun),
-  {Coloring, NewSpillIndex} = 
+  {Coloring, NewSpillIndex, Liveness} =
     regalloc(
-      CFG, 
+      CFG,
+      Liveness0,
       ?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} = 
-    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),
@@ -79,8 +104,9 @@ 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, 
+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/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..c73d029b9b 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),
@@ -169,14 +173,22 @@ do_jmp_switch(I, TempMap, Strategy) ->
 %%% Fix a lea op.
 
 do_lea(I, TempMap, Strategy) ->
-  #lea{temp=Temp} = I,
-  case is_spilled(Temp, TempMap) of
-    false ->
-      {[I], false};
-    true ->
-      NewTmp = spill_temp('untagged', Strategy),
-      {[I#lea{temp=NewTmp}, hipe_x86:mk_move(NewTmp, Temp)],
-       true}
+  #lea{mem=Mem0,temp=Temp0} = I,
+  {FixMem, Mem, DidSpill1} = fix_mem_operand(Mem0, TempMap, temp1(Strategy)),
+  case Mem of
+    #x86_mem{base=Base, off=#x86_imm{value=0}} ->
+      %% We've decayed into a move due to both operands being memory (there's an
+      %% 'add' in FixMem).
+      {FixMem ++ [hipe_x86:mk_move(Base, Temp0)], DidSpill1};
+    #x86_mem{} ->
+      {StoreTemp, Temp, DidSpill2} =
+	case is_mem_opnd(Temp0, TempMap) of
+	  false -> {[], Temp0, false};
+	  true ->
+	    Temp1 = clone2(Temp0, temp0(Strategy)),
+	    {[hipe_x86:mk_move(Temp1, Temp0)], Temp1, true}
+	end,
+      {FixMem ++ [I#lea{mem=Mem,temp=Temp} | StoreTemp], DidSpill1 or DidSpill2}
   end.
 
 %%% Fix a move op.
diff --git a/lib/hipe/x86/hipe_x86_ra_x87_ls.erl b/lib/hipe/x86/hipe_x86_ra_x87_ls.erl
deleted file mode 100644
index 1ee76e5948..0000000000
--- a/lib/hipe/x86/hipe_x86_ra_x87_ls.erl
+++ /dev/null
@@ -1,64 +0,0 @@
-%% $Id$
-%%
-%% %CopyrightBegin%
-%% 
-%% Copyright Ericsson AB 2006-2016. All Rights Reserved.
-%% 
-%% Licensed under the Apache License, Version 2.0 (the "License");
-%% you may not use this file except in compliance with the License.
-%% You may obtain a copy of the License at
-%%
-%%     http://www.apache.org/licenses/LICENSE-2.0
-%%
-%% Unless required by applicable law or agreed to in writing, software
-%% distributed under the License is distributed on an "AS IS" BASIS,
-%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-%% See the License for the specific language governing permissions and
-%% limitations under the License.
-%% 
-%% %CopyrightEnd%
-%%
-
-%% Linear Scan register allocator for x87
-
--ifdef(HIPE_AMD64).
--define(HIPE_X86_RA_X87_LS, hipe_amd64_ra_x87_ls).
--define(HIPE_X86_SPECIFIC_X87, hipe_amd64_specific_x87).
--define(HIPE_X86_PP, hipe_amd64_pp).
--define(HIPE_X86_RA_LS, hipe_amd64_ra_ls).
--else.
--define(HIPE_X86_RA_X87_LS, hipe_x86_ra_x87_ls).
--define(HIPE_X86_SPECIFIC_X87, hipe_x86_specific_x87).
--define(HIPE_X86_PP, hipe_x86_pp).
--define(HIPE_X86_RA_LS, hipe_x86_ra_ls).
--endif.
-
--module(?HIPE_X86_RA_X87_LS).
--export([ra/2]).
-
-%%-define(DEBUG,1).
-
--define(HIPE_INSTRUMENT_COMPILER, false). %% Turn off instrumentation.
--include("../main/hipe.hrl").
-
-ra(Defun, Options) ->
-    ?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 = ?HIPE_X86_SPECIFIC_X87:number_of_temporaries(CFG),
-    ?inc_counter(bbs_counter, length(hipe_x86_cfg:labels(CFG))),
-
-    ?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} =
-	?HIPE_X86_RA_LS:regalloc(Cfg,
-				 ?HIPE_X86_SPECIFIC_X87:allocatable(),
-				 [hipe_x86_cfg:start_label(Cfg)],
-				 SpillIndex, SpillLimit, Options,
-				 ?HIPE_X86_SPECIFIC_X87),
-
-    ?add_spills(Options, NewSpillIndex),
-    {Defun, Coloring, NewSpillIndex}.
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