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.

8 files changed, 105 insertions, 14 deletions

diff --git a/lib/hipe/sparc/hipe_sparc.erl b/lib/hipe/sparc/hipe_sparc.erl
index 916857b224..22e0761b69 100644
--- a/lib/hipe/sparc/hipe_sparc.erl
+++ b/lib/hipe/sparc/hipe_sparc.erl
@@ -87,6 +87,9 @@
 
 	 mk_pseudo_set/2,
 
+	 mk_pseudo_spill_move/3,
+	 is_pseudo_spill_move/1,
+
 	 mk_pseudo_tailcall/4,
 	 pseudo_tailcall_funv/1,
 	 pseudo_tailcall_linkage/1,
@@ -117,6 +120,9 @@
 	 pseudo_fmove_src/1,
 	 pseudo_fmove_dst/1,
 
+	 mk_pseudo_spill_fmove/3,
+	 is_pseudo_spill_fmove/1,
+
 	 mk_pseudo_fstore/3,
 	 mk_fstore/4,
 
@@ -269,6 +275,10 @@ mk_pseudo_ret() -> #pseudo_ret{}.
 
 mk_pseudo_set(Imm, Dst) -> #pseudo_set{imm=Imm, dst=Dst}.
 
+mk_pseudo_spill_move(Src, Temp, Dst) ->
+  #pseudo_spill_move{src=Src, temp=Temp, dst=Dst}.
+is_pseudo_spill_move(I) -> is_record(I, pseudo_spill_move).
+
 mk_pseudo_tailcall(FunV, Arity, StkArgs, Linkage) ->
   #pseudo_tailcall{funv=FunV, arity=Arity, stkargs=StkArgs, linkage=Linkage}.
 pseudo_tailcall_funv(#pseudo_tailcall{funv=FunV}) -> FunV.
@@ -375,6 +385,10 @@ is_pseudo_fmove(I) -> case I of #pseudo_fmove{} -> true; _ -> false end.
 pseudo_fmove_src(#pseudo_fmove{src=Src}) -> Src.
 pseudo_fmove_dst(#pseudo_fmove{dst=Dst}) -> Dst.
 
+mk_pseudo_spill_fmove(Src, Temp, Dst) ->
+  #pseudo_spill_fmove{src=Src, temp=Temp, dst=Dst}.
+is_pseudo_spill_fmove(I) -> is_record(I, pseudo_spill_fmove).
+
 mk_pseudo_fstore(Src, Base, Disp) ->
   #pseudo_fstore{src=Src, base=Base, disp=Disp}.
 
diff --git a/lib/hipe/sparc/hipe_sparc.hrl b/lib/hipe/sparc/hipe_sparc.hrl
index 4eae6777a9..f60e516e59 100644
--- a/lib/hipe/sparc/hipe_sparc.hrl
+++ b/lib/hipe/sparc/hipe_sparc.hrl
@@ -88,6 +88,8 @@
 -record(pseudo_move, {src, dst}).
 -record(pseudo_ret, {}).
 -record(pseudo_set, {imm, dst}).
+-record(pseudo_spill_fmove, {src, temp, dst}).
+-record(pseudo_spill_move, {src, temp, dst}).
 -record(pseudo_tailcall, {funv, arity, stkargs, linkage}).
 -record(pseudo_tailcall_prepare, {}).
 -record(rdy, {dst}).
diff --git a/lib/hipe/sparc/hipe_sparc_defuse.erl b/lib/hipe/sparc/hipe_sparc_defuse.erl
index cb75f82e2b..4d4b11e301 100644
--- a/lib/hipe/sparc/hipe_sparc_defuse.erl
+++ b/lib/hipe/sparc/hipe_sparc_defuse.erl
@@ -39,6 +39,7 @@ insn_def_gpr(I) ->
     #pseudo_call{} -> call_clobbered_gpr();
     #pseudo_move{dst=Dst} -> [Dst];
     #pseudo_set{dst=Dst} -> [Dst];
+    #pseudo_spill_move{temp=Temp, dst=Dst} -> [Temp, Dst];
     #pseudo_tailcall_prepare{} -> tailcall_clobbered_gpr();
     #rdy{dst=Dst} -> [Dst];
     #sethi{dst=Dst} -> [Dst];
@@ -72,6 +73,7 @@ insn_use_gpr(I) ->
       funv_use(FunV, arity_use_gpr(Arity));
     #pseudo_move{src=Src} -> [Src];
     #pseudo_ret{} -> [hipe_sparc:mk_rv()];
+    #pseudo_spill_move{src=Src} -> [Src];
     #pseudo_tailcall{funv=FunV,arity=Arity,stkargs=StkArgs} ->
       addsrcs(StkArgs, addtemps(tailcall_clobbered_gpr(), funv_use(FunV, arity_use_gpr(Arity))));
     #store{src=Src,base=Base,disp=Disp} ->
@@ -112,6 +114,7 @@ insn_def_fpr(I) ->
     #fp_unary{dst=Dst} -> [Dst];
     #pseudo_fload{dst=Dst} -> [Dst];
     #pseudo_fmove{dst=Dst} -> [Dst];
+    #pseudo_spill_fmove{temp=Temp, dst=Dst} -> [Temp, Dst];
     _ -> []
   end.
 
@@ -130,6 +133,7 @@ insn_use_fpr(I) ->
     #fp_unary{src=Src} -> [Src];
     #pseudo_fmove{src=Src} -> [Src];
     #pseudo_fstore{src=Src} -> [Src];
+    #pseudo_spill_fmove{src=Src} -> [Src];
     _ -> []
   end.
 
diff --git a/lib/hipe/sparc/hipe_sparc_frame.erl b/lib/hipe/sparc/hipe_sparc_frame.erl
index 6f29c3c905..1f2a259ca1 100644
--- a/lib/hipe/sparc/hipe_sparc_frame.erl
+++ b/lib/hipe/sparc/hipe_sparc_frame.erl
@@ -82,6 +82,10 @@ do_insn(I, LiveOut, Context, FPoff) ->
       {do_pseudo_tailcall(I, Context), context_framesize(Context)};
     #pseudo_fmove{} ->
       {do_pseudo_fmove(I, Context, FPoff), FPoff};
+    #pseudo_spill_move{} ->
+      {do_pseudo_spill_move(I, Context, FPoff), FPoff};
+    #pseudo_spill_fmove{} ->
+      {do_pseudo_spill_fmove(I, Context, FPoff), FPoff};
     _ ->
       {[I], FPoff}
   end.
@@ -110,6 +114,22 @@ do_pseudo_move(I, Context, FPoff) ->
       end
   end.
 
+do_pseudo_spill_move(I, Context, FPoff) ->
+  #pseudo_spill_move{src=Src,temp=Temp,dst=Dst} = 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_sparc:mk_pseudo_move(Src, Dst), 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(hipe_sparc:mk_sp(), SrcOffset, Temp,
+		 mk_store(Temp, hipe_sparc:mk_sp(), DstOffset, []))
+      end
+  end.
+
 do_pseudo_fmove(I, Context, FPoff) ->
   Dst = hipe_sparc:pseudo_fmove_dst(I),
   Src = hipe_sparc:pseudo_fmove_src(I),
@@ -127,6 +147,22 @@ do_pseudo_fmove(I, Context, FPoff) ->
       end
   end.
 
+do_pseudo_spill_fmove(I, Context, FPoff) ->
+  #pseudo_spill_fmove{src=Src,temp=Temp,dst=Dst} = I,
+  case temp_is_pseudo(Src) andalso temp_is_pseudo(Dst) of
+    false -> % Register allocator changed its mind, turn back to fmove
+      do_pseudo_fmove(hipe_sparc:mk_pseudo_fmove(Src, Dst), 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_fload(hipe_sparc:mk_sp(), SrcOffset, Temp)
+	    ++ mk_fstore(Temp, hipe_sparc:mk_sp(), DstOffset)
+      end
+  end.
+
 pseudo_offset(Temp, FPoff, Context) ->
   FPoff + context_offset(Context, Temp).
 
diff --git a/lib/hipe/sparc/hipe_sparc_ra_finalise.erl b/lib/hipe/sparc/hipe_sparc_ra_finalise.erl
index 5fdb73e197..a724821992 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_finalise.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_finalise.erl
@@ -38,6 +38,7 @@ ra_insn(I, Map, FPMap) ->
     #pseudo_call{} -> ra_pseudo_call(I, Map);
     #pseudo_move{} -> ra_pseudo_move(I, Map);
     #pseudo_set{} -> ra_pseudo_set(I, Map);
+    #pseudo_spill_move{} -> ra_pseudo_spill_move(I, Map);
     #pseudo_tailcall{} -> ra_pseudo_tailcall(I, Map);
     #rdy{} -> ra_rdy(I, Map);
     #sethi{} -> ra_sethi(I, Map);
@@ -47,6 +48,7 @@ ra_insn(I, Map, FPMap) ->
     #pseudo_fload{} -> ra_pseudo_fload(I, Map, FPMap);
     #pseudo_fmove{} -> ra_pseudo_fmove(I, FPMap);
     #pseudo_fstore{} -> ra_pseudo_fstore(I, Map, FPMap);
+    #pseudo_spill_fmove{} -> ra_pseudo_spill_fmove(I, FPMap);
     _ -> I
   end.
 
@@ -80,6 +82,12 @@ ra_pseudo_set(I=#pseudo_set{dst=Dst}, Map) ->
   NewDst = ra_temp(Dst, Map),
   I#pseudo_set{dst=NewDst}.
 
+ra_pseudo_spill_move(I=#pseudo_spill_move{src=Src,temp=Temp,dst=Dst}, Map) ->
+  NewSrc = ra_temp(Src, Map),
+  NewTemp = ra_temp(Temp, Map),
+  NewDst = ra_temp(Dst, Map),
+  I#pseudo_spill_move{src=NewSrc,temp=NewTemp,dst=NewDst}.
+
 ra_pseudo_tailcall(I=#pseudo_tailcall{funv=FunV,stkargs=StkArgs}, Map) ->
   NewFunV = ra_funv(FunV, Map),
   NewStkArgs = ra_args(StkArgs, Map),
@@ -120,6 +128,13 @@ ra_pseudo_fmove(I=#pseudo_fmove{src=Src,dst=Dst}, FPMap) ->
   NewDst = ra_temp_fp(Dst, FPMap),
   I#pseudo_fmove{src=NewSrc,dst=NewDst}.
 
+ra_pseudo_spill_fmove(I=#pseudo_spill_fmove{src=Src,temp=Temp,dst=Dst},
+		      FPMap) ->
+  NewSrc = ra_temp_fp(Src, FPMap),
+  NewTemp = ra_temp_fp(Temp, FPMap),
+  NewDst = ra_temp_fp(Dst, FPMap),
+  I#pseudo_spill_fmove{src=NewSrc,temp=NewTemp,dst=NewDst}.
+
 ra_pseudo_fstore(I=#pseudo_fstore{src=Src,base=Base}, Map, FPMap) ->
   NewSrc = ra_temp_fp(Src, FPMap),
   NewBase = ra_temp(Base, Map),
diff --git a/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl b/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl
index 984c97fbd4..d3ecb43ec6 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl
@@ -54,6 +54,7 @@ do_insn(I, TempMap, Strategy) ->
     #pseudo_call{} -> do_pseudo_call(I, TempMap, Strategy);
     #pseudo_move{} -> do_pseudo_move(I, TempMap, Strategy);
     #pseudo_set{} -> do_pseudo_set(I, TempMap, Strategy);
+    #pseudo_spill_move{} -> do_pseudo_spill_move(I, TempMap, Strategy);
     #pseudo_tailcall{} -> do_pseudo_tailcall(I, TempMap, Strategy);
     #rdy{} -> do_rdy(I, TempMap, Strategy);
     #sethi{} -> do_sethi(I, TempMap, Strategy);
@@ -92,14 +93,16 @@ do_pseudo_call(I=#pseudo_call{funv=FunV}, TempMap, Strategy) ->
 
 do_pseudo_move(I=#pseudo_move{src=Src,dst=Dst}, TempMap, Strategy) ->
   %% Either Dst or Src (but not both) may be a pseudo temp.
-  %% pseudo_move is a special case: in [XXX: not pseudo_tailcall]
-  %% 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 and pseudo_spill_move [XXX: not pseudo_tailcall]
+  %% are special cases: in all other instructions, all temps must
+  %% be non-pseudos after register allocation.
+  case temp_is_spilled(Src, TempMap)
+    andalso temp_is_spilled(Dst, TempMap)
+  of
+    true -> % Turn into pseudo_spill_move
+      Temp = clone(Src, temp1(Strategy)),
+      NewI = #pseudo_spill_move{src=Src,temp=Temp,dst=Dst},
+      {[NewI], true};
     _ ->
       {[I], false}
   end.
@@ -109,6 +112,11 @@ do_pseudo_set(I=#pseudo_set{dst=Dst}, TempMap, Strategy) ->
   NewI = I#pseudo_set{dst=NewDst},
   {[NewI | FixDst], DidSpill}.
 
+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}.
+
 do_pseudo_tailcall(I=#pseudo_tailcall{funv=FunV}, TempMap, Strategy) ->
   {FixFunV,NewFunV,DidSpill} = fix_funv(FunV, TempMap, Strategy),
   NewI = I#pseudo_tailcall{funv=NewFunV},
diff --git a/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl b/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl
index 751e91425c..5fa3a5fc59 100644
--- a/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl
+++ b/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl
@@ -43,6 +43,7 @@ do_insn(I, TempMap) ->
     #pseudo_fload{} -> do_pseudo_fload(I, TempMap);
     #pseudo_fmove{} -> do_pseudo_fmove(I, TempMap);
     #pseudo_fstore{} -> do_pseudo_fstore(I, TempMap);
+    #pseudo_spill_fmove{} -> do_pseudo_spill_fmove(I, TempMap);
     _ -> {[I], false}
   end.
 
@@ -67,11 +68,13 @@ do_pseudo_fload(I=#pseudo_fload{dst=Dst}, TempMap) ->
   {[NewI | FixDst], DidSpill}.
 
 do_pseudo_fmove(I=#pseudo_fmove{src=Src,dst=Dst}, TempMap) ->
-  case temp_is_spilled(Dst, TempMap) of
-    true ->
-      {FixSrc,NewSrc,DidSpill} = fix_src(Src, TempMap),
-      NewI = I#pseudo_fmove{src=NewSrc},
-      {FixSrc ++ [NewI], DidSpill};
+  case temp_is_spilled(Src, TempMap)
+    andalso temp_is_spilled(Dst, TempMap)
+  of
+    true -> % Turn into pseudo_spill_fmove
+      Temp = clone(Src),
+      NewI = #pseudo_spill_fmove{src=Src,temp=Temp,dst=Dst},
+      {[NewI], true};
     _ ->
       {[I], false}
   end.
@@ -81,6 +84,11 @@ do_pseudo_fstore(I=#pseudo_fstore{src=Src}, TempMap) ->
   NewI = I#pseudo_fstore{src=NewSrc},
   {FixSrc ++ [NewI], DidSpill}.
 
+do_pseudo_spill_fmove(I=#pseudo_spill_fmove{temp=Temp}, TempMap) ->
+  %% Temp is above the low water mark and must not have been spilled
+  false = temp_is_spilled(Temp, TempMap),
+  {[I], false}.
+
 %%% Fix Dst and Src operands.
 
 fix_src(Src, TempMap) ->
diff --git a/lib/hipe/sparc/hipe_sparc_subst.erl b/lib/hipe/sparc/hipe_sparc_subst.erl
index 1d0671464e..ce3bbb813a 100644
--- a/lib/hipe/sparc/hipe_sparc_subst.erl
+++ b/lib/hipe/sparc/hipe_sparc_subst.erl
@@ -44,6 +44,8 @@ insn_temps(T, I) ->
       #pseudo_move{src=S,dst=D} -> I#pseudo_move{src=T(S),dst=T(D)};
       #pseudo_ret{} -> I;
       #pseudo_set{dst=D}-> I#pseudo_set{dst=T(D)};
+      #pseudo_spill_move{src=S,temp=U,dst=D} ->
+	  I#pseudo_spill_move{src=T(S),temp=T(U),dst=T(D)};
       #pseudo_tailcall{funv=F,stkargs=Stk} ->
 	  I#pseudo_tailcall{funv=funv_temps(T,F),stkargs=lists:map(Arg,Stk)};
       #pseudo_tailcall_prepare{} -> I;
@@ -57,7 +59,9 @@ insn_temps(T, I) ->
 	  I#pseudo_fload{base=T(B),disp=S2(Di),dst=T(Ds)};
       #pseudo_fmove{src=S,dst=D} -> I#pseudo_fmove{src=T(S),dst=T(D)};
       #pseudo_fstore{src=S,base=B,disp=D} ->
-	  I#pseudo_fstore{src=T(S),base=T(B),disp=S2(D)}
+	  I#pseudo_fstore{src=T(S),base=T(B),disp=S2(D)};
+      #pseudo_spill_fmove{src=S,temp=U,dst=D} ->
+	  I#pseudo_spill_fmove{src=T(S),temp=T(U),dst=T(D)}
   end.
 
 -spec src2_temps(subst_fun(), src2()) -> src2().