todo

3 files changed, 291 insertions, 0 deletions

diff --git a/iterjit.c b/iterjit.c
index 5325b4c..fcb2f9d 100644
--- a/iterjit.c
+++ b/iterjit.c
@@ -64,6 +64,35 @@
     tell source iter to advance
 
   -=-
+
+  Issues:
+  - The stack based register allocator is not a good fit for this
+    scheme. How about the concept of register "groups"?
+
+    At all times, one group is "active". Allocations are done in this
+    group; registers from other groups can't be used. If such registers
+    are needed, they must be reallocated in the new group.
+
+    When there is no longer enough free registers in a group, a
+    register from another group is kicked out to the stack. When that
+    other group becomes active, all kicked-out registers are moved
+    back in (lazily?). Note, you can never allocate more than the
+    number of real registers within one group.
+
+    API:
+    reg_alloc_init (&ra, stack_manager_t *sman, reg_set_t *regs);
+    reg_alloc_switch (&ra, "name");
+    op_t = reg_alloc_alloc (&ra);
+
+    // The register becomes allocated in the current group
+    // with its current value
+    reg_alloc_preserve (&ra, op_t);
+
+    // After a switch to another group, this make sure the
+    // given registers are reloaded from the stack.
+    reg_alloc_reload (&ra, ..., -1);
+
+  -=-
     
   Iterator based JIT compiler
 
diff --git a/reggroups.c b/reggroups.c
new file mode 100644
index 0000000..5e5479a
--- /dev/null
+++ b/reggroups.c
@@ -0,0 +1,204 @@
+#include "stack-man.h"
+#include "simplex86.h"
+
+static int
+reg_to_index (reg_alloc_t *ra, reg_t reg)
+{
+    const reg_pool_t *pool = ra->reg_pool;
+    int i;
+
+    for (i = 0; i < MAX_REGISTER; ++i)
+    {
+	if (pool->registers[i] == reg)
+	    return i;
+    }
+
+    return -1;
+}
+
+void
+reg_alloc_init (reg_alloc_t *ra, stack_man_t *stack,
+		const reg_pool_t *reg_pool)
+{
+    int i;
+
+    ra->reg_pool = reg_pool;
+
+    memset (ra->groups, 0, sizeof (ra->groups));
+    ra->active = NULL;
+}
+
+static reg_group_t *
+find_group (reg_alloc_t *ra, const char *name)
+{
+    int i;
+
+    for (i = 0; i < MAX_GROUPS; ++i)
+    {
+	if (strcmp (ra->groups[i].name, name) == 0)
+	    return &(ra->groups[i]);
+    }
+
+    return NULL;
+}
+
+void
+reg_alloc_switch_group (reg_alloc_t *ra, const char *name)
+{
+    ra->active = find_group (ra, name);
+}
+
+void
+reg_alloc_free_group (reg_alloc_t *ra, const char *name)
+{
+    reg_group_t *group = find_group (ra, name);
+
+    memset (group, 0, sizeof (reg_group_t));
+}
+
+/* After switching back to a group, this should be called for
+ * all registers that will be used again before switching away.
+ */
+void
+reg_alloc_reload (reg_alloc_t *ra, int n_regs, reg_t reg, ...)
+{
+    va_list list;
+
+    va_start (list, reg);
+
+    while (reg != (reg_t)0)
+    {
+	int idx = op_to_index (reg);
+
+	if (ra->active->allocated[idx] && ra->active->spilled[idx] != -1)
+	{
+	    /* FIXME: unspill */
+	}
+    }
+
+    va_end (list);
+}
+
+/* allocate some register within the current group */
+reg_t
+reg_alloc_alloc (reg_alloc_t *ra)
+{
+    reg_t r;
+    int i, j;
+
+    /* Is there a register that doesn't currently have a value? */
+    for (i = 0; i < MAX_REGISTERS; ++i)
+    {
+	if (ra->active->allocated[i])
+	    continue;
+
+	if (unloaded (ra, i))
+	{
+	    ra->active->allocate[i] = 1;
+	    return ra->reg_pool[i];
+	}
+    }
+
+    /* 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)
+    {
+	reg_group_t *group = &ra->groups[i];
+
+	if (group->name == NULL || group == ra->active)
+	    continue;
+
+	for (i = 0; i < MAX_REGISTERS; ++i)
+	{
+	    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 i;
+	    }
+	}
+    }
+
+    /* At this point 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.
+     * - all registers have been allocated in the current group
+     */
+    for (i = 0; i < MAX_REGISTERS; ++i)
+    {
+	if (!ra->active->allocated[i])
+	{
+	    fprintf (
+		stderr,
+		"BUG in register allocator: slot available, "
+		"but no register can be spilled\n");
+	    return (reg_t)0;
+	}
+    }
+    
+    fprintf (stderr, "group %s is out of registers\n", ra->active->name);
+    return (reg_t)0;
+}
+
+/* @reg becomes allocated in the current group, though it
+ * may be moved to another register
+ */
+op_t
+reg_alloc_preserve (reg_alloc_t *ra, op_t reg);
+
+void
+reg_alloc_free (reg_alloc_t *ra, op_t reg);
+
+
+typedef struct reg_info_t reg_info_t;
+typedef struct reg_alloc_t reg_alloc_t;
+typedef struct reg_context_t reg_context_t;
+
+#define MAX_REGISTERS 64
+
+struct reg_alloc_t
+{
+    const reg_pool_t *  registers;
+    stack_man_t *       stack_man;
+};
+
+typedef enum
+{
+    UNUSED,             /* not in use by us, and not in use by parent */
+    IN_USE,             /* in use by us, but not parent */
+    SPILLABLE,          /* in use by parent, but not by us */
+    SPILLED,            /* parent value spilled on stack, and in use by us */
+    CLOBBERED,          /* parent value spilled on stack, but not used by us anymore */
+} reg_state_t;
+
+struct reg_info_t
+{
+    reg_state_t		state;
+
+    int                 spill_offset;
+};
+
+struct reg_context_t
+{
+    reg_alloc_t *       allocator;
+    reg_context_t *     parent;
+    reg_info_t          info[MAX_REGISTERS];
+};
+
+void
+reg_alloc_init (reg_alloc_t *     reg_alloc,
+                const reg_pool_t *registers,
+                stack_man_t *     stack_man,
+                reg_context_t *   initial_context,
+		int		  n_initial,
+		/* op_t reg, */   ...);
+
+/* The registers */
+
diff --git a/reggroups.h b/reggroups.h
new file mode 100644
index 0000000..b8c0dc7
--- /dev/null
+++ b/reggroups.h
@@ -0,0 +1,58 @@
+#include "stack-man.h"
+#include "simplex86.h"
+
+typedef struct reg_alloc_t reg_alloc_t;
+typedef struct reg_group_t reg_group_t;
+typedef struct reg_pool_t reg_pool_t;
+
+#define MAX_REGISTERS (64)
+#define MAX_GROUPS    (16)
+
+struct reg_pool_t
+{
+    int         n_registers;
+    int         register_size;
+    reg_t       registers[MAX_REGISTERS];
+};
+
+struct reg_group_t
+{
+    const char *name;
+    int allocated[MAX_REGISTERS];
+    int spill_offset[MAX_REGISTERS]; /* -1 if not spilled */
+};
+
+struct reg_alloc_t
+{
+    const reg_pool_t *reg_pool;
+    reg_group_t groups[MAX_GROUPS];
+    reg_group_t *active;
+};
+
+void
+reg_alloc_init (reg_alloc_t *ra, stack_man_t *stack, const reg_pool_t *reg_pool);
+
+void
+reg_alloc_switch_group (reg_alloc_t *ra, const char *name);
+
+void
+reg_alloc_free_group (reg_alloc_t *ra, const char *name);
+
+/* After switching back to a group, this should be called for
+ * all registers that will be used again before switching away.
+ */
+void
+reg_alloc_reload (reg_alloc_t *ra, op_t reg, ...);
+
+/* allocate some register within the current group */
+reg_t
+reg_alloc_alloc (reg_alloc_t *ra);
+
+/* @reg becomes allocated in the current group, though it
+ * may be moved to another register
+ */
+reg_t
+reg_alloc_preserve (reg_alloc_t *ra, reg_t reg);
+
+void
+reg_alloc_free (reg_alloc_t *ra, reg_t reg);