More reg groups

3 files changed, 150 insertions, 77 deletions

diff --git a/iterjit.c b/iterjit.c
index 3329185..57bcc42 100644
--- a/iterjit.c
+++ b/iterjit.c
@@ -249,7 +249,7 @@ struct jit_dest_iter_t
 
 static const reg_pool_t xmm_pool =
 {
-    16 /* n_registers */, 16 /* register size */,
+    16 /* n_registers */, 16 /* register size */, I_movdqa,
     { xmm0, xmm1, xmm2, xmm3, xmm4, xmm5, xmm6, xmm7,
       xmm8, xmm9, xmm10, xmm11, xmm12, xmm13, xmm14, xmm15,
     },
@@ -257,7 +257,7 @@ static const reg_pool_t xmm_pool =
 
 static const reg_pool_t gp64_pool =
 {
-    14 /* n_registers */, 8 /* register size */,
+    14 /* n_registers */, 8 /* register size */, I_mov,
     { rax, rbx, rcx, rdx, rsi, rdi,
       r8, r9, r10, r11, r12, r13, r14, r15,
     }
diff --git a/reggroups.c b/reggroups.c
index bc85ada..b9732d2 100644
--- a/reggroups.c
+++ b/reggroups.c
@@ -44,6 +44,26 @@ find_group (reg_alloc_t *ra, const char *name)
     return NULL;
 }
 
+static reg_group_t *
+find_owner (reg_alloc_t *ra, reg_t reg)
+{
+    int idx = reg_to_index (ra, reg);
+    int i;
+
+    for (i = 0; i < MAX_GROUPS; ++i)
+    {
+	reg_group_t *group = &ra->groups[i];
+	
+	if (group->name == NULL)
+	    continue;
+
+	if (group->allocated[idx] && group->spill_offset[idx] == -1)
+	    return group;
+    }
+
+    return NULL;
+}
+
 void
 reg_alloc_switch_group (reg_alloc_t *ra, const char *name)
 {
@@ -58,92 +78,133 @@ reg_alloc_free_group (reg_alloc_t *ra, const char *name)
     memset (group, 0, sizeof (reg_group_t));
 }
 
+
+static void
+take_ownership (reg_alloc_t *ra, reg_t reg)
+{
+    reg_group_t *old_owner = find_owner (ra, reg);
+    int idx = reg_to_index (ra, reg);
+
+    if (old_owner)
+    {
+	/* FIXME: spill the old owner */
+    }
+
+    ra->active->allocated[idx] = 1;
+    ra->active->spill_offset[idx] = -1;
+}
+
+static void
+relinguish_ownership (reg_alloc_t *ra, reg_t reg)
+{
+    int idx = reg_to_index (ra, reg);
+
+    ra->active->allocated[idx] = 0;
+    ra->active->spill_offset[idx] = -1;
+}
+
+static reg_t
+reload_one_reg (reg_alloc_t *ra, reg_t reg)
+{
+    reg_group_t *owner = find_owner (ra, reg);
+    reg_t new_location;
+    int idx;
+    int i;
+
+    if (owner == ra->active)
+	return reg;
+
+    idx = reg_to_index (ra, reg);
+    if (!ra->active->allocated[idx])
+    {
+	fprintf (stderr, "Attempting to reload a register that "
+		 "isn't allocated in the current group");
+	return (reg_t)0;
+    }
+
+    new_location = reg;
+    for (i = 0; i < ra->reg_pool->n_registers; ++i)
+    {
+	reg_t r = ra->reg_pool->registers[i];
+
+	if (!find_owner (ra, r))
+	{
+	    new_location = r;
+	    break;
+	}
+    }
+
+    if (new_location != reg)
+	relinguish_ownership (ra, reg);
+
+    take_ownership (ra, new_location);
+
+    /* FIXME: Insert unspill code into new_location */
+
+    return new_location;
+}
+
 /* After switching back to a group, this should be called for
  * all registers that will be used again before switching away.
+ *
+ * FIXME: these should be pointers, so that the registers can
+ * be reallocated in more convenient registers if necessary.
  */
 void
-reg_alloc_reload (reg_alloc_t *ra, int n_regs, reg_t reg, ...)
+reg_alloc_reload (reg_alloc_t *ra, reg_t *reg, ...)
 {
     va_list list;
 
     va_start (list, reg);
 
-    while (reg != (reg_t)0)
+    while (reg)
     {
-	int idx = reg_to_index (ra, reg);
+	*reg = reload_one_reg (ra, *reg);
 
-	if (ra->active->allocated[idx] && ra->active->spill_offset[idx] != -1)
-	{
-	    /* FIXME: unspill */
-	}
+	reg = va_arg (list, reg_t *);
     }
 
     va_end (list);
 }
-
 /* allocate some register within the current group */
 reg_t
 reg_alloc_alloc (reg_alloc_t *ra)
 {
-    int i, j;
+    int i;
 
-    /* Is there a register that is
-     * - unallocated in the current group
-     * - either unallocated or spilled in all other groups?
+    /* Is there a register that doesn't have an owner?
      */
-    for (i = 0; i < MAX_REGISTERS; ++i)
+    for (i = 0; i < ra->reg_pool->n_registers; ++i)
     {
-	if (ra->active->allocated[i])
-	    goto next_register;
-       
-	for (j = 0; j < MAX_GROUPS; ++j)
-	{
-	    reg_group_t *group = &ra->groups[i];
+	reg_t reg = ra->reg_pool->registers[i];
+	reg_group_t *owner = find_owner (ra, reg);
 
-	    if (group->name == NULL || group == ra->active)
-		continue;
+	if (!owner)
+	{
+	    take_ownership (ra, reg);
 
-	    if (group->allocated[i] && group->spill_offset[i] == -1)
-		goto next_register;
+	    return reg;
 	}
-
-	/* Found one */
-	return ra->reg_pool->registers[i];
-
-    next_register:
-	;
     }
 
-    /* No, then in order of best to worst group,
-     * look for a register that can be spilled.
-     * FIXME: the order is not best-to-worst right now
-     */
-    for (j = 0; j < MAX_GROUPS; ++j)
+    /* Is there a register that is owned by someone else? */
+    for (i = 0; i < ra->reg_pool->n_registers; ++i)
     {
-	reg_group_t *group = &ra->groups[i];
-
-	if (group->name == NULL || group == ra->active)
-	    continue;
+	reg_t reg = ra->reg_pool->registers[i];
+	reg_group_t *owner = find_owner (ra, reg);
 
-	for (i = 0; i < MAX_REGISTERS; ++i)
+	if (owner && owner != ra->active)
 	{
-	    if (ra->active->allocated[i])
-		continue;
-
-	    if (group->allocated[i] && group->spill_offset[i] == -1)
-	    {
-		/* Have a winner (or loser) */
-		/* FIXME: insert spill code */
-		group->spill_offset[i] = 100;
-		return ra->reg_pool->registers[i];
-	    }
+	    take_ownership (ra, reg);
+
+	    return reg;
 	}
     }
 
-    /* If we get here, something is seriously wrong. Either:
+    /* No. If we get here, something is seriously wrong. Either:
      * - an internal error in the register allocator has
-     *   produced a situation where a register is in used
-     *   but no group claims it is loaded.
+     *   produced a situation where a register is in use
+     *   but no group claims to own it.
      * - all registers in the current group have been allocated
      */
     for (i = 0; i < MAX_REGISTERS; ++i)
@@ -168,42 +229,53 @@ reg_alloc_alloc (reg_alloc_t *ra)
 reg_t
 reg_alloc_preserve (reg_alloc_t *ra, reg_t reg)
 {
-    int idx = reg_to_index (ra, reg);
-    int in_use;
+    reg_group_t *owner;
     int i;
 
+    owner = find_owner (ra, reg);
+
+    if (owner == ra->active)
+    {
+	fprintf (stderr, "Can't preserve value of allocated register\n");
+	return (reg_t)0;
+    }
+
     /* If the register is not in use by another group, then
-     * just mark it allocated in the current group.
+     * just take ownership.
      */
+    if (!owner)
+    {
+	take_ownership (ra, reg);
+	return reg;
+    }
 
-    /* Otherwise, if reg is not allocated in the current group,
-     * then spill it in the other group, and mark it in-use here.
+    /* Otherwise, is there some other unowned register in 
+     * the current group?
      */
+    for (i = 0; i < ra->reg_pool->n_registers; ++i)
+    {
+	reg_t r = ra->reg_pool->registers[i];
 
-    /* Otherwise, a new register must be allocated, and the
-     * content moved there. FIXME: so that means the allocator
-     * must know how to do reg-reg moves.
-     */
+	if (!find_owner (ra, r))
+	{
+	    take_ownership (ra, r);
 
-    /* Otherwise, a new register must be allocated
+	    /* FIXME: Issue "mov r, reg" */
 
-    /* Is the register in question being used by another group? */
-    for (i = 0; i < MAX_GROUPS; ++i)
-    {
-	reg_group_t *group = &ra->groups[i];
+	    return r;
+	}
     }
 
-    if (ra->active->allocated[idx])
-    {
-	/* Already allocated in this group, so
-	 * we have to move it somewhere else
-	 */
-    }
+    /* Otherwise, just spill reg in its current owner */
+    take_ownership (ra, reg);
+    return reg;
 }
 
 void
-reg_alloc_free (reg_alloc_t *ra, reg_t reg);
-
+reg_alloc_free (reg_alloc_t *ra, reg_t reg)
+{
+    relinguish_ownership (ra, reg);
+}
 
 typedef struct reg_info_t reg_info_t;
 typedef struct reg_alloc_t reg_alloc_t;
diff --git a/reggroups.h b/reggroups.h
index 95ac758..e4cab1a 100644
--- a/reggroups.h
+++ b/reggroups.h
@@ -12,6 +12,7 @@ struct reg_pool_t
 {
     int         n_registers;
     int         register_size;
+    op_t	reg_reg_instruction;
     reg_t       registers[MAX_REGISTERS];
 };
 
@@ -42,7 +43,7 @@ reg_alloc_free_group (reg_alloc_t *ra, const char *name);
  * all registers that will be used again before switching away.
  */
 void
-reg_alloc_reload (reg_alloc_t *ra, int n_regs, reg_t reg, ...);
+reg_alloc_reload (reg_alloc_t *ra, reg_t *reg, ...);
 
 /* allocate some register within the current group */
 reg_t