hipe: Add pseudo_spill_f?move instructions

These pseudo instructions are added to all backends and allow spill slot
to spill slot move coalescing in a clean way.

They have regular move semantics, but contain an additional scratch
register to be used if both source and destination are spilled, and can
not be move coalesced.

Additionally, a register allocator callback
Target:is_spill_move(Instr, Context) is added which allows the spill
slot allocators to check for these instructions and try to coalesce the
spill slots the two temporaries are allocated to.

7 files changed, 70 insertions, 13 deletions

diff --git a/lib/hipe/arm/hipe_arm.erl b/lib/hipe/arm/hipe_arm.erl
index e34a00f561..3b090b501a 100644
--- a/lib/hipe/arm/hipe_arm.erl
+++ b/lib/hipe/arm/hipe_arm.erl
@@ -79,6 +79,9 @@
 	 pseudo_move_dst/1,
 	 pseudo_move_src/1,
 
+	 mk_pseudo_spill_move/3,
+	 is_pseudo_spill_move/1,
+
 	 mk_pseudo_switch/3,
 
 	 mk_pseudo_tailcall/4,
@@ -250,6 +253,10 @@ is_pseudo_move(I) -> case I of #pseudo_move{} -> true; _ -> false end.
 pseudo_move_dst(#pseudo_move{dst=Dst}) -> Dst.
 pseudo_move_src(#pseudo_move{src=Src}) -> Src.
 
+mk_pseudo_spill_move(Dst, Temp, Src) ->
+  #pseudo_spill_move{dst=Dst, temp=Temp, src=Src}.
+is_pseudo_spill_move(I) -> is_record(I, pseudo_spill_move).
+
 mk_pseudo_switch(JTab, Index, Labels) ->
   #pseudo_switch{jtab=JTab, index=Index, labels=Labels}.
 
diff --git a/lib/hipe/arm/hipe_arm.hrl b/lib/hipe/arm/hipe_arm.hrl
index 67bc07634e..be06b1ebd7 100644
--- a/lib/hipe/arm/hipe_arm.hrl
+++ b/lib/hipe/arm/hipe_arm.hrl
@@ -101,6 +101,7 @@
 -record(pseudo_call_prepare, {nrstkargs}).
 -record(pseudo_li, {dst, imm, label}).	% pre-generated label for use by the assembler
 -record(pseudo_move, {dst, src}).
+-record(pseudo_spill_move, {dst, temp, src}).
 -record(pseudo_switch, {jtab, index, labels}).
 -record(pseudo_tailcall, {funv, arity, stkargs, linkage}).
 -record(pseudo_tailcall_prepare, {}).
diff --git a/lib/hipe/arm/hipe_arm_defuse.erl b/lib/hipe/arm/hipe_arm_defuse.erl
index 0e62070c6c..652299a514 100644
--- a/lib/hipe/arm/hipe_arm_defuse.erl
+++ b/lib/hipe/arm/hipe_arm_defuse.erl
@@ -40,6 +40,7 @@ insn_def_gpr(I) ->
     #pseudo_call{} -> call_clobbered_gpr();
     #pseudo_li{dst=Dst} -> [Dst];
     #pseudo_move{dst=Dst} -> [Dst];
+    #pseudo_spill_move{dst=Dst, temp=Temp} -> [Dst, Temp];
     #pseudo_tailcall_prepare{} -> tailcall_clobbered_gpr();
     #smull{dstlo=DstLo,dsthi=DstHi,src1=Src1} ->
       %% ARM requires DstLo, DstHi, and Src1 to be distinct.
@@ -83,6 +84,7 @@ insn_use_gpr(I) ->
     #pseudo_call{funv=FunV,sdesc=#arm_sdesc{arity=Arity}} ->
       funv_use(FunV, arity_use_gpr(Arity));
     #pseudo_move{src=Src} -> [Src];
+    #pseudo_spill_move{src=Src} -> [Src];
     #pseudo_switch{jtab=JTabR,index=IndexR} -> addtemp(JTabR, [IndexR]);
     #pseudo_tailcall{funv=FunV,arity=Arity,stkargs=StkArgs} ->
       addargs(StkArgs, addtemps(tailcall_clobbered_gpr(), funv_use(FunV, arity_use_gpr(Arity))));
diff --git a/lib/hipe/arm/hipe_arm_frame.erl b/lib/hipe/arm/hipe_arm_frame.erl
index e323907e31..a1004fb609 100644
--- a/lib/hipe/arm/hipe_arm_frame.erl
+++ b/lib/hipe/arm/hipe_arm_frame.erl
@@ -69,6 +69,8 @@ do_insn(I, LiveOut, Context, FPoff) ->
       do_pseudo_call_prepare(I, FPoff);
     #pseudo_move{} ->
       {do_pseudo_move(I, Context, FPoff), FPoff};
+    #pseudo_spill_move{} ->
+      {do_pseudo_spill_move(I, Context, FPoff), FPoff};
     #pseudo_tailcall{} ->
       {do_pseudo_tailcall(I, Context), context_framesize(Context)};
     _ ->
@@ -100,6 +102,26 @@ pseudo_offset(Temp, FPoff, Context) ->
   FPoff + context_offset(Context, Temp).
 
 %%%
+%%% Moves from one spill slot to another
+%%%
+
+do_pseudo_spill_move(I, Context, FPoff) ->
+  #pseudo_spill_move{dst=Dst, temp=Temp, src=Src} = I,
+  case temp_is_pseudo(Src) andalso temp_is_pseudo(Dst) of
+    false -> % Register allocator changed its mind, turn back to move
+      do_pseudo_move(hipe_arm:mk_pseudo_move(Dst, Src), Context, FPoff);
+    true ->
+      SrcOffset = pseudo_offset(Src, FPoff, Context),
+      DstOffset = pseudo_offset(Dst, FPoff, Context),
+      case SrcOffset =:= DstOffset of
+	true -> []; % omit move-to-self
+	false ->
+	  mk_load('ldr', Temp, SrcOffset, mk_sp(),
+		  mk_store('str', Temp, DstOffset, mk_sp(), []))
+      end
+  end.
+
+%%%
 %%% Return - deallocate frame and emit 'ret $N' insn.
 %%%
 
diff --git a/lib/hipe/arm/hipe_arm_ra_finalise.erl b/lib/hipe/arm/hipe_arm_ra_finalise.erl
index 9bfe0a9a83..80cd470708 100644
--- a/lib/hipe/arm/hipe_arm_ra_finalise.erl
+++ b/lib/hipe/arm/hipe_arm_ra_finalise.erl
@@ -25,11 +25,17 @@ 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]);
+  ra_code(Insns, Map, ra_insn(I, Map, Accum));
 ra_code([], _Map, Accum) ->
   lists:reverse(Accum).
 
-ra_insn(I, Map) ->
+ra_insn(I, Map, Accum) ->
+  case I of
+    #pseudo_move{} -> ra_pseudo_move(I, Map, Accum);
+    _ -> [ra_insn_1(I, Map) | Accum]
+  end.
+
+ra_insn_1(I, Map) ->
   case I of
     #alu{} -> ra_alu(I, Map);
     #cmp{} -> ra_cmp(I, Map);
@@ -38,7 +44,7 @@ ra_insn(I, Map) ->
     #move{} -> ra_move(I, Map);
     #pseudo_call{} -> ra_pseudo_call(I, Map);
     #pseudo_li{} -> ra_pseudo_li(I, Map);
-    #pseudo_move{} -> ra_pseudo_move(I, Map);
+    #pseudo_spill_move{} -> ra_pseudo_spill_move(I, Map);
     #pseudo_switch{} -> ra_pseudo_switch(I, Map);
     #pseudo_tailcall{} -> ra_pseudo_tailcall(I, Map);
     #smull{} -> ra_smull(I, Map);
@@ -80,10 +86,19 @@ ra_pseudo_li(I=#pseudo_li{dst=Dst}, Map) ->
   NewDst = ra_temp(Dst, Map),
   I#pseudo_li{dst=NewDst}.
 
-ra_pseudo_move(I=#pseudo_move{dst=Dst,src=Src}, Map) ->
+ra_pseudo_move(I=#pseudo_move{dst=Dst,src=Src}, Map, Accum) ->
+  NewDst = ra_temp(Dst, Map),
+  NewSrc = ra_temp(Src, Map),
+  case NewSrc#arm_temp.reg =:= NewDst#arm_temp.reg of
+    true -> Accum;
+    false -> [I#pseudo_move{dst=NewDst,src=NewSrc} | Accum]
+  end.
+
+ra_pseudo_spill_move(I=#pseudo_spill_move{dst=Dst,temp=Temp,src=Src}, Map) ->
   NewDst = ra_temp(Dst, Map),
+  NewTemp = ra_temp(Temp, Map),
   NewSrc = ra_temp(Src, Map),
-  I#pseudo_move{dst=NewDst,src=NewSrc}.
+  I#pseudo_spill_move{dst=NewDst, temp=NewTemp, src=NewSrc}.
 
 ra_pseudo_switch(I=#pseudo_switch{jtab=JTab,index=Index}, Map) ->
   NewJTab = ra_temp(JTab, Map),
diff --git a/lib/hipe/arm/hipe_arm_ra_postconditions.erl b/lib/hipe/arm/hipe_arm_ra_postconditions.erl
index 8d1ee1cb94..23c305511f 100644
--- a/lib/hipe/arm/hipe_arm_ra_postconditions.erl
+++ b/lib/hipe/arm/hipe_arm_ra_postconditions.erl
@@ -56,6 +56,7 @@ do_insn(I, TempMap, Strategy) ->
     #pseudo_call{} -> do_pseudo_call(I, TempMap, Strategy);
     #pseudo_li{} -> do_pseudo_li(I, TempMap, Strategy);
     #pseudo_move{} -> do_pseudo_move(I, TempMap, Strategy);
+    #pseudo_spill_move{} -> do_pseudo_spill_move(I, TempMap, Strategy);
     #pseudo_switch{} -> do_pseudo_switch(I, TempMap, Strategy);
     #pseudo_tailcall{} -> do_pseudo_tailcall(I, TempMap, Strategy);
     #smull{} -> do_smull(I, TempMap, Strategy);
@@ -108,18 +109,25 @@ do_pseudo_li(I=#pseudo_li{dst=Dst}, TempMap, Strategy) ->
 
 do_pseudo_move(I=#pseudo_move{dst=Dst,src=Src}, TempMap, Strategy) ->
   %% Either Dst or Src (but not both) may be a pseudo temp.
-  %% pseudo_move and pseudo_tailcall are special cases: in
-  %% all other instructions, all temps must be non-pseudos
-  %% after register allocation.
-  case temp_is_spilled(Dst, TempMap) of
-    true -> % Src must not be a pseudo
-      {FixSrc,NewSrc,DidSpill} = fix_src1(Src, TempMap, Strategy),
-      NewI = I#pseudo_move{src=NewSrc},
-      {FixSrc ++ [NewI], DidSpill};
+  %% pseudo_move, pseudo_spill_move, and pseudo_tailcall
+  %% are special cases: in all other instructions, all
+  %% temps must be non-pseudos after register allocation.
+  case temp_is_spilled(Dst, TempMap)
+    andalso temp_is_spilled(Dst, TempMap)
+  of
+    true -> % Turn into pseudo_spill_move
+      Temp = clone(Src, temp1(Strategy)),
+      NewI = #pseudo_spill_move{dst=Dst, temp=Temp, src=Src},
+      {[NewI], true};
     _ ->
       {[I], false}
   end.
 
+do_pseudo_spill_move(I = #pseudo_spill_move{temp=Temp}, TempMap, _Strategy) ->
+  %% Temp is above the low water mark and must not have been spilled
+  false = temp_is_spilled(Temp, TempMap),
+  {[I], false}. % nothing to do
+
 do_pseudo_switch(I=#pseudo_switch{jtab=JTab,index=Index}, TempMap, Strategy) ->
   {FixJTab,NewJTab,DidSpill1} = fix_src1(JTab, TempMap, Strategy),
   {FixIndex,NewIndex,DidSpill2} = fix_src2(Index, TempMap, Strategy),
diff --git a/lib/hipe/arm/hipe_arm_subst.erl b/lib/hipe/arm/hipe_arm_subst.erl
index a41a907a4c..4ff245f414 100644
--- a/lib/hipe/arm/hipe_arm_subst.erl
+++ b/lib/hipe/arm/hipe_arm_subst.erl
@@ -59,6 +59,8 @@ insn_temps(T, I) ->
       #pseudo_call{funv=F} -> I#pseudo_call{funv=funv_temps(T, F)};
       #pseudo_call_prepare{} -> I;
       #pseudo_li{dst=D} -> I#pseudo_li{dst=T(D)};
+      #pseudo_spill_move{dst=D,temp=U,src=S} ->
+	  I#pseudo_spill_move{dst=T(D),temp=T(U),src=T(S)};
       #pseudo_switch{jtab=J=#arm_temp{},index=Ix=#arm_temp{}} ->
 	  I#pseudo_switch{jtab=T(J),index=T(Ix)};
       #pseudo_tailcall{funv=F,stkargs=Stk} ->