summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--iterjit.c29
-rw-r--r--reggroups.c204
-rw-r--r--reggroups.h58
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);
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-21 15:30:13 +0000