From bd1521672254390ea7e452238fcd436cf8e312ee Mon Sep 17 00:00:00 2001 From: Søren Sandmann Pedersen Date: Mon, 2 Sep 2013 20:07:17 -0400 Subject: todo --- iterjit.c | 29 +++++++++ reggroups.c | 204 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ reggroups.h | 58 +++++++++++++++++ 3 files changed, 291 insertions(+) create mode 100644 reggroups.c create mode 100644 reggroups.h 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); -- cgit v1.2.3