diff --git a/host_regs.c b/host_regs.c
index 7786b18..82465f2 100644
--- a/host_regs.c
+++ b/host_regs.c
@@ -160,6 +160,11 @@
    for (i = 0; i < map->n_used; i++)
       if (map->orig[i] == orig)
          panic("addToHRegMap: duplicate entry");
+   if (!hregIsVirtual(orig))
+      panic("addToHRegMap: orig is not a vreg");
+   if (hregIsVirtual(replacement))
+      panic("addToHRegMap: replacement is not a vreg");
+
    assert(map->n_used+1 < N_HREG_REMAP);
    map->orig[map->n_used]        = orig;
    map->replacement[map->n_used] = replacement;
@@ -170,6 +175,8 @@
 HReg lookupHRegRemap ( HRegRemap* map, HReg orig )
 {
    Int i;
+   if (!hregIsVirtual(orig))
+      return orig;
    for (i = 0; i < map->n_used; i++)
       if (map->orig[i] == orig)
          return map->replacement[i];
diff --git a/include/host_regs.h b/include/host_regs.h
index 411d3cd..9bf1a75 100644
--- a/include/host_regs.h
+++ b/include/host_regs.h
@@ -109,6 +109,13 @@
 /*--- Indicating register remappings (for reg-alloc)    ---*/
 /*---------------------------------------------------------*/
 
+/* Note that such maps can only map virtual regs to real regs.
+   addToHRegRenap will barf if given a pair not of that form.  As a
+   result, no valid HRegRemap will bind a real reg to anything, and so
+   if lookupHRegMap is given a real reg, it returns it unchanged.
+   This is precisely the behaviour that the register allocator needs
+   to impose its decisions on the instructions it processes.  */
+
 #define N_HREG_REMAP 4
 
 typedef
diff --git a/reg_alloc.c b/reg_alloc.c
index f491a92..0e7b31d 100644
--- a/reg_alloc.c
+++ b/reg_alloc.c
@@ -93,6 +93,48 @@
 }
 
 
+/* Search forward from some given point in the incoming instruction
+   sequence.  Point is to select a virtual register to spill, by
+   finding the vreg which is mentioned as far ahead as possible, in
+   the hope that this will minimise the number of consequent reloads.
+
+   Only do the search for vregs which are Bound in the running state,
+   and for which the .mark field is set.  This allows the caller to
+   arbitrarily restrict the set of spill candidates to be considered.
+
+   Returns an index into the state array indicating the (v,r) pair to
+   spill, or -1 if none was found.  */
+static
+Int findMostDistantlyMentionedVReg ( 
+   void (*getRegUsage) (HRegUsage*, HInstr*),
+   HInstrArray* instrs_in,
+   Int          search_from_instr,
+   RRegState*   state,
+   Int          n_state
+)
+{
+   Int k, m;
+   Int furthest_k = -1;
+   Int furthest   = -1;
+   assert(search_from_instr >= 0);
+   for (k = 0; k < n_state; k++) {
+      if (!state[k].is_spill_cand)
+         continue;
+      assert(state[k].disp == Bound);
+      for (m = search_from_instr; m < instrs_in->arr_used; m++) {
+         if (instrMentionsReg(getRegUsage, 
+                              instrs_in->arr[m], state[k].vreg))
+            break;
+      }
+      if (m > furthest) {
+         furthest   = m;
+         furthest_k = k;
+      }
+   }
+   return furthest_k;
+}
+
+
 /* A target-independent register allocator for Valgrind.  Requires
    various functions which it uses to deal abstractly with
    instructions and registers, since it cannot have any
@@ -137,7 +179,7 @@
 )
 {
    /* Iterators and temporaries. */
-   Int       ii, j, k, m, furthest, furthest_k;
+   Int       ii, j, k, m, spillee;
    HReg      rreg, vreg;
    HRegUsage reg_usage;
 
@@ -170,6 +212,18 @@
 
 #  define INVALID_INSTRNO (-2)
 
+#  define EMIT_INSTR(_instr)                  \
+      do {                                    \
+        HInstr* _tmp = (_instr);              \
+        if (1) {                              \
+           fprintf(stdout, "**  ");           \
+           ppX86Instr(stdout, _tmp);          \
+           fprintf(stdout, "\n");             \
+        }                                     \
+        addHInstr ( instrs_out, _tmp );       \
+      } while (0)
+
+
    /* --------- Stage 0: set up output array. --------- */
    instrs_out = newHInstrArray();
 
@@ -443,7 +497,8 @@
       state[j].is_spill_cand = False;
    }
 
-   /* Process each insn in turn. */
+   /* ------ BEGIN: Process each insn in turn. ------ */
+
    for (ii = 0; ii < instrs_in->arr_used; ii++) {
 
       fprintf(stdout, "\n-----------\n%d   ", ii);
@@ -523,72 +578,54 @@
          Not yet.
       */
 
-      /* Update the local state.  Expire any v -> r bindings for 
-         vregs which have become dead. */
-      for (j = 0; j < n_state; j++) {
-         if (state[j].disp != Bound)
-            continue;
-         k = hregNumber(state[j].vreg);
-	 printf("possibly expire vreg %d\n", k);
-         assert(k >= 0 && k < n_vregs);
-         if (vreg_info[k].dead_before == ii) {
-	   printf("yes (state[%d])\n", j);
-           /* It's just gone dead.  Free up the associated rreg. */
-           state[j].disp = Free;
-           state[j].vreg = INVALID_HREG;
-         }
-      }
-
-
-      for (j = 0; j < n_state; j++) {
-         ppHReg(stdout, state[j].rreg);
-	 fprintf(stdout, "\t  ");
-	 switch (state[j].disp) {
-	    case Free: fprintf(stdout, "Free\n"); break;
-	    case Unavail: fprintf(stdout, "Unavail\n"); break;
-	    case Bound: fprintf(stdout, "BoundTo "); 
-                        ppHReg(stdout, state[j].vreg);
-                        fprintf(stdout, "\n"); break;
-	 }
-      }
-
-
+      /* ------ Pre-instruction actions for fixed rreg uses ------ */
 
       /* Now we have to deal with rregs which are about to be made
          live by this instruction -- in other words, are entering into
          one of their live ranges.  If any such rreg holds a vreg, we
-         will have to spill it in order to free up the rreg.
+         will have to free up the rreg.  The simplest solution which
+         is correct is to spill the rreg.
 
          Note we could do better:
          * Could move it into some other free rreg, if one is available 
          * Don't bother to spill if the spill-slot value is known to
            be consistent.
+	 * If the associated vreg live range ends at this insn,
+           no point in spilling or moving, since (in principle) the
+           rreg will be free anyway after that.
 
          Simplest way to do this is to iterate over the collection
          of rreg live ranges.
       */
       for (j = 0; j < rreg_info_used; j++) {
-         if (rreg_info[j].live_after == ii-1) {
-            /* rreg_info[j].rreg needs to be freed up.  Find out if
-               there is a vreg associated with it. */
-            for (k = 0; k < n_state; k++) {
-               if (state[k].rreg == rreg_info[j].rreg
-                   && state[k].disp == Bound)
-                  break;
-            }
-            if (k < n_state) {
-               /* Yes, there is an associated vreg.  Spill it. */
+         if (rreg_info[j].live_after == ii) {
+            /* rreg_info[j].rreg needs to be freed up.  Find 
+               the associated state entry. */
+	   printf("need to free up rreg: ");
+	   ppHReg(stdout, rreg_info[j].rreg);
+	   printf("\n");
+            for (k = 0; k < n_state; k++)
+	      if (state[k].rreg == rreg_info[j].rreg)
+		break;
+	    /* If this fails, we don't have an entry for this rreg.
+               Which we should. */
+	    assert(k < n_state);
+            if (state[k].disp == Bound) {
+               /* Yes, there is an associated vreg.  Spill it if it's
+                  still live. */
                m = hregNumber(state[k].vreg);
                assert(m >= 0 && m < n_vregs);
-               addHInstr ( instrs_out,
-                           (*genSpill)( vreg_info[m].spill_offset, 
-                                        state[k].rreg ) );
-               state[k].disp = Free;
-               state[k].vreg = INVALID_HREG;
+	       if (vreg_info[m].dead_before > ii)
+                  EMIT_INSTR( (*genSpill)( state[k].rreg,
+                                           vreg_info[m].spill_offset ) );
             }
+            state[k].disp = Unavail;
+            state[k].vreg = INVALID_HREG;
          }
       }
 
+      /* ------ Deal with the current instruction. ------ */
+
       /* Finally we can begin the processing of this instruction
          itself.  The aim is to free up enough rregs for this insn.
          This may generate spill stores since we may have to evict
@@ -609,6 +646,8 @@
          if (!hregIsVirtual(vreg)) 
             continue;
 
+	 printf("considering "); ppHReg(stdout, vreg); printf("\n");
+
          /* Now we're trying to find a rreg for "vreg".  First of all,
             if it already has an rreg assigned, we don't need to do
             anything more.  Search the current state to find out. */
@@ -622,24 +661,62 @@
 
          /* No luck.  The next thing to do is see if there is a
             currently free rreg available, of the correct class.  If
-            so, bag it.  NOTE, we could improve this to select an rreg
-            for which the next live-range event is as far ahead as
-            possible. */
-         for (k = 0; k < n_state; k++)
+            so, bag it.  NOTE, we could improve this by selecting an
+            rreg for which the next live-range event is as far ahead
+            as possible. */
+         for (k = 0; k < n_state; k++) {
             if (state[k].disp == Free
-                && (hregClass(state[k].rreg) == hregClass(vreg)))
+                && hregClass(state[k].rreg) == hregClass(vreg))
                break;
+         }
          if (k < n_state) {
             state[k].disp = Bound;
             state[k].vreg = vreg;
             addToHRegRemap(&remap, vreg, state[k].rreg);
+	    /* Generate a reload if needed. */
+            if (reg_usage.mode[j] != HRmWrite) {
+               m = hregNumber(vreg);
+               assert(m >= 0 && m < n_vregs);
+	       EMIT_INSTR( (*genReload)( state[k].rreg,
+                                         vreg_info[m].spill_offset ) );
+            }
             continue;
          }
 
-         /* There are no free registers, so we're going to have to
-            spill a vreg.  We need to make a good choice of vreg to
-            spill, and of course we need to be careful not to spill a
-            vreg which is needed by this insn. */
+	 /* There are no free rregs, but perhaps we can find one which
+            is bound to a vreg which is now dead.  If so, use that.
+            NOTE, we could improve this by selecting an rreg for which
+            the next live-range event is as far ahead as possible. */
+         for (k = 0; k < n_state; k++) {
+            if (state[k].disp == Bound
+                && hregClass(state[k].rreg) == hregClass(vreg)) {
+	       m = hregNumber(state[k].vreg);
+	       assert(m >= 0 && m < n_vregs);
+	       if (vreg_info[m].dead_before <= ii) {
+                  /* Ok, it's gone dead before this insn.  We can use
+                     it. */
+                  break;
+	       }
+	    }
+	 }
+         if (k < n_state) {
+            assert(state[k].disp == Bound);
+            state[k].vreg = vreg;
+            addToHRegRemap(&remap, vreg, state[k].rreg);
+	    /* Generate a reload if needed. */
+            if (reg_usage.mode[j] != HRmWrite) {
+               m = hregNumber(vreg);
+               assert(m >= 0 && m < n_vregs);
+	       EMIT_INSTR( (*genReload)( state[k].rreg,
+                                         vreg_info[m].spill_offset ) );
+            }
+            continue;
+	 }
+
+         /* Well, now we have no option but to spill a vreg.  It's
+            important to make a good choice of vreg to spill, and of
+            course we need to be careful not to spill a vreg which is
+            needed by this insn. */
 
          /* First, mark in the state, those rregs which are not spill
             candidates, due to holding a vreg mentioned by this
@@ -659,29 +736,16 @@
             }
          }
 
-         /* We can choose any rreg satisfying state[r].is_spill_cand
-            (so to speak).  Choose rreg so that the next use of its
-            associated vreg is as far ahead as possible, in the hope
-            that this will minimise the number of consequent reloads
-            required.  This is a bit expensive, but we don't have to
-            do it very often. */
-         furthest_k = -1;
-         furthest   = -1;
-         for (k = 0; k < n_state; k++) {
-            if (!state[k].is_spill_cand)
-               continue;
-            assert(state[k].disp == Bound);
-            for (m = ii+1; m < instrs_in->arr_used; m++)
-               if (instrMentionsReg(getRegUsage, 
-                                    instrs_in->arr[m], state[k].vreg))
-                  break;
-            if (m > furthest) {
-               furthest = m;
-               furthest_k = k;
-            }
-         }
+         /* We can choose to spill any rreg satisfying
+            state[r].is_spill_cand (so to speak).  Choose r so that
+            the next use of its associated vreg is as far ahead as
+            possible, in the hope that this will minimise the number
+            of consequent reloads required. */
+	 spillee
+            = findMostDistantlyMentionedVReg ( 
+                 getRegUsage, instrs_in, ii+1, state, n_state );
 
-         if (furthest_k == -1) {
+         if (spillee == -1) {
             /* Hmmmmm.  There don't appear to be any spill candidates.
                We're hosed. */
             fprintf(stderr, "reg_alloc: can't find a register in class: ");
@@ -690,41 +754,41 @@
             panic("reg_alloc: can't create a free register.");
          }
 
-         /* Right.  So we're going to spill state[furthest_k]. */
-         assert(state[furthest_k].disp == Bound);
+         /* Right.  So we're going to spill state[spillee]. */
+	 assert(spillee >= 0 && spillee < n_state);
+         assert(state[spillee].disp == Bound);
          /* check it's the right class */
-         assert(hregClass(state[furthest_k].rreg) == hregClass(vreg));
+         assert(hregClass(state[spillee].rreg) == hregClass(vreg));
          /* check we're not ejecting the vreg for which we are trying
             to free up a register. */
-         assert(state[furthest_k].vreg != vreg);
+         assert(state[spillee].vreg != vreg);
 
-         m = hregNumber(state[furthest_k].vreg);
+         m = hregNumber(state[spillee].vreg);
          assert(m >= 0 && m < n_vregs);
-         /* check that the vreg we're ejecting is still live. */
-         assert(vreg_info[m].dead_before > ii);
 
-         /* So here's the spill store. */
-         addHInstr ( instrs_out,
-                     (*genSpill)( vreg_info[m].spill_offset, 
-                                  state[furthest_k].rreg ) );
+         /* So here's the spill store.  Assert that we're spilling a
+            live vreg. */
+         assert(vreg_info[m].dead_before > ii);
+         EMIT_INSTR( (*genSpill)( state[spillee].rreg,
+                                  vreg_info[m].spill_offset ) );
 
          /* Update the state to reflect the new assignment for this
             rreg. */
-         state[furthest_k].vreg = vreg;
+         state[spillee].vreg = vreg;
 
          /* Now, if this vreg is being read or modified (as opposed to
             written), we have to generate a reload for it. */
          if (reg_usage.mode[j] != HRmWrite) {
             m = hregNumber(vreg);
             assert(m >= 0 && m < n_vregs);
-            addHInstr ( instrs_out,
-                        (*genReload)( vreg_info[m].spill_offset,
-                                      state[furthest_k].rreg ) );
+	    EMIT_INSTR( (*genReload)( state[spillee].rreg,
+                                      vreg_info[m].spill_offset ) );
+                                      
          }
 
          /* So after much twisting and turning, we have vreg mapped to
             state[furthest_k].rreg.  Note that in the map. */
-         addToHRegRemap(&remap, vreg, state[furthest_k].rreg);
+         addToHRegRemap(&remap, vreg, state[spillee].rreg);
 
       } /* iterate over registers in this instruction. */
 
@@ -741,10 +805,33 @@
 
       /* NOTE, DESTRUCTIVELY MODIFIES instrs_in->arr[ii]. */
       (*mapRegs)( &remap, instrs_in->arr[ii] );
-      addHInstr ( instrs_out, instrs_in->arr[ii] );
+      EMIT_INSTR( instrs_in->arr[ii] );
+
+      /* ------ Post-instruction actions for fixed rreg uses ------ */
+
+      /* Now we need to check for rregs exiting fixed live ranges
+	 after this instruction, and if so mark them as free. */
+
+      for (j = 0; j < rreg_info_used; j++) {
+         if (rreg_info[j].dead_before == ii+1) {
+            /* rreg_info[j].rreg is exiting a hard live range.  Mark
+               it as such in the main state array. */
+            for (k = 0; k < n_state; k++)
+               if (state[k].rreg == rreg_info[j].rreg)
+                  break;
+            /* If this assertion fails, we don't have an entry for
+               this rreg.  Which we should. */
+            assert(k < n_state);
+            assert(state[k].disp == Unavail);
+            state[k].disp = Free;
+            state[k].vreg = INVALID_HREG;
+         }
+      }
 
    } /* iterate over insns */
 
+   /* ------ END: Process each insn in turn. ------ */
+
    free(state);
    free(rreg_info);
    if (vreg_info) free(vreg_info);
diff --git a/test_main.c b/test_main.c
index ca51318..fd99ea9 100644
--- a/test_main.c
+++ b/test_main.c
@@ -24,6 +24,39 @@
 HInstrArray* /* not really, but for the time being ... */
              iselBB ( IRBB* bb );
 
+/* HACK */
+X86Instr* genSpill_X86 ( HReg rreg, Int offset )
+{
+   assert(!hregIsVirtual(rreg));
+   switch (hregClass(rreg)) {
+      case HRcInt:
+        return
+	X86Instr_Alu32M ( Xalu_MOV, X86RI_Reg(rreg), 
+		          X86AMode_IR(offset + 0x1000, 
+                                      hregX86_EBP()));
+      default: 
+         ppHRegClass(stderr, hregClass(rreg));
+         panic("genSpill_X86: unimplemented regclass");
+   }
+}
+
+/* HACK */
+X86Instr* genReload_X86 ( HReg rreg, Int offset )
+{
+   assert(!hregIsVirtual(rreg));
+   switch (hregClass(rreg)) {
+      case HRcInt:
+        return
+	X86Instr_Alu32R ( Xalu_MOV, 
+		          X86RMI_Mem(X86AMode_IR(offset + 0x1000, 
+                                                 hregX86_EBP())),
+                          rreg );
+      default: 
+         ppHRegClass(stderr, hregClass(rreg));
+         panic("genReload_X86: unimplemented regclass");
+   }
+}
+
 
 int main ( void )
 {
@@ -37,20 +70,73 @@
    addToIRTypeEnv ( env, t1, Ity_I32 );
    addToIRTypeEnv ( env, t2, Ity_I32 );
 
+   IRStmt* s10 = IRStmt_Tmp(t1, IRExpr_Const(IRConst_U32(1001)));
+   IRStmt* s11 = IRStmt_Tmp(t2, IRExpr_Const(IRConst_U32(2002)));
+
    IRStmt* s1 = IRStmt_Put(8,4, IRExpr_Const(IRConst_U32(99)) );
    IRStmt* s2 = IRStmt_Put(7,4, IRExpr_Binop(Iop_Add32,
                                              IRExpr_Tmp(t1),
 					     IRExpr_Const(IRConst_U32(55))));
+   s10->link = s11;
+   s11->link = s1;
    s1->link = s2;
 
-   bb = mk_IRBB(env, s1, IRNext_UJump(IRConst_U32(-65565)));
+   bb = mk_IRBB(env, s10, IRNext_UJump(IRConst_U32(-65565)));
 
    printf("bb is ...\n");
    ppIRBB(stdout, bb);
    printf("\n");
 
-   vcode = iselBB(bb);
+   //   vcode = iselBB(bb);
    {
+     Int i;
+     HReg vr0 = mkHReg(0, HRcInt, True);
+     HReg vr1 = mkHReg(1, HRcInt, True);
+     HReg vr2 = mkHReg(2, HRcInt, True);
+     HReg vr3 = mkHReg(3, HRcInt, True);
+     HReg eax = hregX86_EAX();
+     HReg ebx = hregX86_EBX();
+     HReg ecx = hregX86_ECX();
+     HReg edx = hregX86_EDX();
+     HReg ebp = hregX86_EBP();
+     vcode = newHInstrArray();
+
+     addHInstr(vcode, X86Instr_Alu32R(Xalu_MOV, 
+				      X86RMI_Imm(0x10001), vr0));
+     addHInstr(vcode, X86Instr_Alu32R(Xalu_MOV, 
+				      X86RMI_Imm(0x10101), vr1));
+     addHInstr(vcode, X86Instr_Alu32R(Xalu_MOV, 
+				      X86RMI_Imm(0x10201), vr2));
+     addHInstr(vcode, X86Instr_Alu32R(Xalu_MOV, 
+				      X86RMI_Imm(0x10301), vr3));
+
+     addHInstr(vcode, X86Instr_Alu32R(Xalu_MOV,
+				      X86RMI_Imm(0x99999), eax));
+     addHInstr(vcode, X86Instr_Alu32R(Xalu_MOV,
+				      X86RMI_Imm(0x99999), edx));
+
+     addHInstr(vcode, X86Instr_Alu32M(Xalu_MOV,
+				      X86RI_Reg(vr0),
+				      X86AMode_IR(0x100, ebp)));
+     addHInstr(vcode, X86Instr_Alu32M(Xalu_MOV,
+				      X86RI_Reg(vr1),
+				      X86AMode_IR(0x101, ebp)));
+     addHInstr(vcode, X86Instr_Alu32M(Xalu_MOV,
+				      X86RI_Reg(vr2),
+				      X86AMode_IR(0x101, ebp)));
+     addHInstr(vcode, X86Instr_Alu32M(Xalu_MOV,
+				      X86RI_Reg(vr3),
+				      X86AMode_IR(0x101, ebp)));
+   printf("\nBefore\n");
+   for (i = 0; i < vcode->arr_used; i++) {
+     ppX86Instr(stdout, vcode->arr[i]);
+     printf("\n");
+   }
+   printf("\n");
+   }
+
+   {
+     Int i;
      HInstrArray* rcode;
      HReg rregs_to_use[4];
      rregs_to_use[0] = hregX86_EAX();
@@ -59,16 +145,22 @@
      rregs_to_use[3] = hregX86_EDX();
 
      rcode =
-     doRegisterAllocation(vcode, 3, /* vregs */
+     doRegisterAllocation(vcode, 4, /* vregs */
                           rregs_to_use, 4, /* rregs */
 			  NULL, /* ismove */
 			  getRegUsage_X86Instr,
 			  mapRegs_X86Instr,
-			  NULL, /* genspill */
-			  NULL /* genreload */
+			  genSpill_X86,
+			  genReload_X86
 			  );
 
-
+   printf("\nAfter\n");
+   for (i = 0; i < rcode->arr_used; i++) {
+     ppX86Instr(stdout, rcode->arr[i]);
+     printf("\n");
    }
+   printf("\n");
+   }
+
    return 0;
 }
diff --git a/x86h_defs.c b/x86h_defs.c
index 7c0101b..2bff7b3 100644
--- a/x86h_defs.c
+++ b/x86h_defs.c
@@ -431,7 +431,10 @@
          if (i->Xin.Sh32.src == 0)
             addHRegUse(u, HRmRead, hregX86_ECX());
          return;
+      case Xin_RET:
+         return;
       default:
+         ppX86Instr(stderr, i);
          panic("getRegUsage_X86Instr");
    }
 }
@@ -450,7 +453,10 @@
       case Xin_Sh32:
          mapRegs_X86RM(m, i->Xin.Sh32.dst);
          return;
+      case Xin_RET:
+         return;
       default:
+         ppX86Instr(stderr, i);
          panic("mapRegs_X86Instr");
    }
 }