Author: leo
Date: Mon Nov 7 05:48:24 2005
New Revision: 9816
Modified:
trunk/ast/node.c
trunk/imcc/cfg.c
trunk/imcc/debug.c
trunk/imcc/imc.c
trunk/imcc/imc.h
trunk/imcc/pbc.c
trunk/imcc/pcc.c
trunk/imcc/reg_alloc.c
trunk/imcc/symreg.c
trunk/imcc/symreg.h
trunk/imcc/unit.h
Log:
Speed up PASM/PIR compilation by several magnitudes
* the SymReg hash was fixed sized with ~25K entries
* imcc had spent by far most of it's time during just walking the
hash data buffer
* this is now improved by using variable sized hash data storage
---
* fixed bug #37627 reported by Nick Glencross
Modified: trunk/ast/node.c
==============================================================================
--- trunk/ast/node.c (original)
+++ trunk/ast/node.c Mon Nov 7 05:48:24 2005
@@ -1067,7 +1067,7 @@ create_Func(int nr, nodeType *self, node
self = create_1(nr, self, child);
r = child->u.r;
last = cur_unit->prev; /* XXX ->caller */
- r = _get_sym(last->hash, r->name);
+ r = _get_sym(&last->hash, r->name);
if (r) {
/* mark the name being a subroutine name
* s. Py_Local
Modified: trunk/imcc/cfg.c
==============================================================================
--- trunk/imcc/cfg.c (original)
+++ trunk/imcc/cfg.c Mon Nov 7 05:48:24 2005
@@ -61,14 +61,15 @@ find_basic_blocks (Parrot_Interp interpr
{
Basic_block *bb;
Instruction *ins;
+ SymHash *hsh = &unit->hash;
+ SymReg * r;
int nu = 0;
int i;
IMCC_info(interpreter, 2, "find_basic_blocks\n");
init_basic_blocks(unit);
- for (i = 0; i < HASH_SIZE; i++) {
- SymReg * r;
- for (r = unit->hash[i]; r; r = r->next) {
+ for (i = 0; i < hsh->size; i++) {
+ for (r = hsh->data[i]; r; r = r->next) {
if (r && (r->type & VTADDRESS)) {
r->last_ins = NULL;
}
@@ -140,7 +141,7 @@ find_basic_blocks (Parrot_Interp interpr
*/
if (!strcmp(ins->op, "bsr") || !strcmp(ins->op, "set_addr")) {
char *name = ins->r[0]->name;
- SymReg *r = get_sym(name);
+ r = get_sym(name);
if (*ins->op == 'b') { /* bsr */
Instruction * lab;
found = r != NULL && r->first_ins;
Modified: trunk/imcc/debug.c
==============================================================================
--- trunk/imcc/debug.c (original)
+++ trunk/imcc/debug.c Mon Nov 7 05:48:24 2005
@@ -158,17 +158,20 @@ void
dump_labels(IMC_Unit * unit)
{
int i;
+ SymHash *hsh = &unit->hash;
+ SymReg * r;
fprintf(stderr, "Labels\n");
fprintf(stderr, "name\tpos\tlast ref\n"
"-----------------------\n");
- for(i = 0; i < HASH_SIZE; i++) {
- SymReg * r = unit->hash[i];
+ for (i = 0; i < hsh->size; i++) {
+ for (r = hsh->data[i]; r; r = r->next) {
if (r && (r->type & VTADDRESS))
fprintf(stderr, "%s\t%d\t%d\n",
r->name,
r->first_ins ? r->first_ins->index : -1,
r->last_ins ? r->last_ins->index : -1);
+ }
}
fprintf(stderr, "\n");
}
Modified: trunk/imcc/imc.c
==============================================================================
--- trunk/imcc/imc.c (original)
+++ trunk/imcc/imc.c Mon Nov 7 05:48:24 2005
@@ -82,8 +82,8 @@ void
imc_cleanup(Interp *interp)
{
clear_globals(interp);
- mem_sys_free(IMCC_INFO(interp)->ghash);
- IMCC_INFO(interp)->ghash = NULL;
+ mem_sys_free(IMCC_INFO(interp)->ghash.data);
+ IMCC_INFO(interp)->ghash.data = NULL;
}
@@ -94,7 +94,7 @@ static IMC_Unit *
imc_new_unit(IMC_Unit_Type t)
{
IMC_Unit * unit = calloc(1, sizeof(IMC_Unit));
- unit->hash = mem_sys_allocate_zeroed(HASH_SIZE * sizeof(SymReg*));
+ create_symhash(&unit->hash);
unit->type = t;
return unit;
}
@@ -114,8 +114,8 @@ imc_open_unit(Parrot_Interp interp, IMC_
imc_info = IMCC_INFO(interp);
if (!imc_info->imc_units)
imc_info->imc_units = unit;
- if (!imc_info->ghash)
- imc_info->ghash = mem_sys_allocate_zeroed(HASH_SIZE * sizeof(SymReg*));
+ if (!imc_info->ghash.data)
+ create_symhash(&imc_info->ghash);
unit->prev = imc_info->last_unit;
if (imc_info->last_unit)
imc_info->last_unit->next = unit;
@@ -161,7 +161,7 @@ imc_free_unit(Parrot_Interp interp, IMC_
imc->n_comp_units--;
clear_locals(unit);
- free(unit->hash);
+ free(unit->hash.data);
free(unit);
}
Modified: trunk/imcc/imc.h
==============================================================================
--- trunk/imcc/imc.h (original)
+++ trunk/imcc/imc.h Mon Nov 7 05:48:24 2005
@@ -197,7 +197,7 @@ typedef struct _imc_info_t {
int dont_optimize;
int has_compile;
int allocated;
- SymReg ** ghash;
+ SymHash ghash;
SymReg * cur_namespace;
struct nodeType_t *top_node;
Modified: trunk/imcc/pbc.c
==============================================================================
--- trunk/imcc/pbc.c (original)
+++ trunk/imcc/pbc.c Mon Nov 7 05:48:24 2005
@@ -42,8 +42,8 @@ struct subs {
size_t size; /* code size in ops */
int ins_line; /* line# for debug */
int n_basic_blocks; /* block count */
- SymReg * labels[HASH_SIZE]; /* label names */
- SymReg * bsrs[HASH_SIZE]; /* bsr, set_addr locations */
+ SymHash labels; /* label names */
+ SymHash bsrs; /* bsr, set_addr locations */
IMC_Unit * unit;
int pmc_const; /* index in const table */
struct subs *prev;
@@ -58,7 +58,7 @@ struct cs_t {
struct subs *first; /* first sub of code segment */
struct cs_t *prev; /* previous code segment */
struct cs_t *next; /* next code segment */
- SymReg * key_consts[HASH_SIZE]; /* cached key constants for this seg */
+ SymHash key_consts; /* cached key constants for this seg */
int pic_idx; /* next index of PIC */
};
@@ -88,8 +88,8 @@ imcc_globals_destroy(int ex, void *param
s = cs->subs;
while (s) {
prev_s = s->prev;
- clear_sym_hash(s->labels);
- clear_sym_hash(s->bsrs);
+ clear_sym_hash(&s->labels);
+ clear_sym_hash(&s->bsrs);
mem_sys_free(s);
s = prev_s;
}
@@ -117,9 +117,10 @@ e_pbc_open(Interp * interpreter, void *p
cs->prev = globals.cs;
/* free previous cached key constants if any */
if (globals.cs) {
- SymReg **h = globals.cs->key_consts;
+ SymHash *h = &globals.cs->key_consts;
clear_sym_hash(h);
}
+ create_symhash(&cs->key_consts);
cs->next = NULL;
cs->subs = NULL;
cs->first = NULL;
@@ -206,6 +207,8 @@ make_new_sub(Interp *interpreter, IMC_Un
if (!globals.cs->first)
globals.cs->first = s;
globals.cs->subs = s;
+ create_symhash(&s->labels);
+ create_symhash(&s->bsrs);
#ifdef HAS_JIT
if ((IMCC_INFO(interpreter)->optimizer_level & OPT_J)) {
allocate_jit(interpreter, unit);
@@ -245,8 +248,8 @@ static void
store_label(Interp *interpreter, SymReg * r, int pc)
{
SymReg * label;
- label = _mk_address(interpreter, globals.cs->subs->labels,
str_dup(r->name),
- U_add_uniq_label);
+ label = _mk_address(interpreter, &globals.cs->subs->labels,
+ str_dup(r->name), U_add_uniq_label);
label->color = pc;
}
@@ -254,7 +257,8 @@ static void
store_bsr(Interp *interpreter, SymReg * r, int pc, int offset)
{
SymReg * bsr;
- bsr = _mk_address(interpreter, globals.cs->subs->bsrs, str_dup(r->name),
U_add_all);
+ bsr = _mk_address(interpreter, &globals.cs->subs->bsrs,
+ str_dup(r->name), U_add_all);
if (r->set == 'p')
bsr->set = 'p';
bsr->color = pc;
@@ -270,7 +274,7 @@ static void
store_key_const(char * str, int idx)
{
SymReg * c;
- c = _mk_const(globals.cs->key_consts, str_dup(str), 0);
+ c = _mk_const(&globals.cs->key_consts, str_dup(str), 0);
c->color = idx;
}
@@ -383,7 +387,7 @@ store_labels(Interp *interpreter, IMC_Un
if (addr->type & VTREGISTER)
continue;
/* branch found */
- label = _get_sym(globals.cs->subs->labels, addr->name);
+ label = _get_sym(&globals.cs->subs->labels, addr->name);
/* maybe global */
if (label)
continue;
@@ -442,7 +446,7 @@ find_global_label(char *name, struct sub
|| (sym->unit->namespace && !s->unit->namespace)
|| (!sym->unit->namespace && s->unit->namespace)))
continue;
- if ( (r = _get_sym(s->labels, name)) ) {
+ if ( (r = _get_sym(&s->labels, name)) ) {
*pc += r->color; /* here pc was stored */
*s1 = s;
return r;
@@ -461,10 +465,12 @@ fixup_bsrs(Interp *interpreter)
struct subs *s, *s1;
int jumppc = 0;
int pmc_const;
+ SymHash *hsh;
for (s = globals.cs->first; s; s = s->next) {
- for (i = 0; i < HASH_SIZE; i++) {
- for (bsr = s->bsrs[i]; bsr; bsr = bsr->next ) {
+ hsh = &s->bsrs;
+ for (i = 0; i < hsh->size; i++) {
+ for (bsr = hsh->data[i]; bsr; bsr = bsr->next ) {
#if IMC_TRACE_HIGH
fprintf(stderr, "fixup_bsr %s\n", bsr->name);
#endif
@@ -752,7 +758,7 @@ add_const_key(Interp *interpreter, opcod
struct PackFile_Constant *pfc;
opcode_t *rc;
- if ( (r = _get_sym(globals.cs->key_consts, s_key)) != 0)
+ if ( (r = _get_sym(&globals.cs->key_consts, s_key)) != 0)
return r->color;
pfc = malloc(sizeof(struct PackFile_Constant));
rc = PackFile_Constant_unpack_key(interpreter,
@@ -981,19 +987,25 @@ constant_folding(Interp *interpreter, IM
{
SymReg * r;
int i;
+ SymHash *hsh;
/* go through all consts of current sub */
- for (i = 0; i < HASH_SIZE; i++) {
+ hsh = &IMCC_INFO(interpreter)->ghash;
+ for (i = 0; i < hsh->size; i++) {
/* normally constants are in ghash ... */
- for (r = IMCC_INFO(interpreter)->ghash[i]; r; r = r->next) {
+ for (r = hsh->data[i]; r; r = r->next) {
if (r->type & (VTCONST|VT_CONSTP)) {
add_1_const(interpreter, r);
}
}
- /* ... but keychains 'K' are in local hash, they may contain
- * variables and constants
- */
- for (r = unit->hash[i]; r; r = r->next) {
+ }
+ /* ... but keychains 'K' are in local hash, they may contain
+ * variables and constants
+ */
+ hsh = &unit->hash;
+ for (i = 0; i < hsh->size; i++) {
+ /* normally constants are in ghash ... */
+ for (r = hsh->data[i]; r; r = r->next) {
if (r->type & VTCONST) {
add_1_const(interpreter, r);
}
@@ -1190,7 +1202,7 @@ e_pbc_emit(Interp *interpreter, void *pa
PIO_eprintf(NULL, "emit_pbc: op [%d %s]\n", ins->opnum, ins->op);
#endif
if ((addr = get_branch_reg(ins)) != 0 && !(addr->type & VTREGISTER)) {
- SymReg *label = _get_sym(globals.cs->subs->labels, addr->name);
+ SymReg *label = _get_sym(&globals.cs->subs->labels, addr->name);
/* maybe global */
if (label) {
addr->color = label->color - npc;
Modified: trunk/imcc/pcc.c
==============================================================================
--- trunk/imcc/pcc.c (original)
+++ trunk/imcc/pcc.c Mon Nov 7 05:48:24 2005
@@ -48,7 +48,7 @@ get_pasm_reg(Interp* interp, char *name)
{
SymReg *r;
- if ((r = _get_sym(cur_unit->hash, name)))
+ if ((r = _get_sym(&cur_unit->hash, name)))
return r;
return mk_pasm_reg(interp, str_dup(name));
}
@@ -61,7 +61,7 @@ get_const(Interp *interp, const char *na
{
SymReg *r;
- if ((r = _get_sym(IMCC_INFO(interp)->ghash, name)) && r->set == type)
+ if ((r = _get_sym(&IMCC_INFO(interp)->ghash, name)) && r->set == type)
return r;
return mk_const(interp, str_dup(name), type);
}
Modified: trunk/imcc/reg_alloc.c
==============================================================================
--- trunk/imcc/reg_alloc.c (original)
+++ trunk/imcc/reg_alloc.c Mon Nov 7 05:48:24 2005
@@ -196,9 +196,13 @@ make_stat(IMC_Unit * unit, int *sets, in
/* register usage summary */
char type[] = "INSP";
int i, j;
- for (i = 0; i < HASH_SIZE; i++) {
- SymReg * r = unit->hash[i];
- for (; r; r = r->next)
+ SymHash *hsh = &unit->hash;
+ SymReg * r;
+
+ for (i = 0; i < hsh->size; i++) {
+ for (r = hsh->data[i]; r; r = r->next) {
+ if (r->color > unit->max_color)
+ unit->max_color = r->color;
for (j = 0; j < 4; j++)
if (r->set == type[j] && (r->type & VTREGISTER)) {
if (sets)
@@ -207,6 +211,7 @@ make_stat(IMC_Unit * unit, int *sets, in
if (r->color > cols[j])
cols[j] = r->color;
}
+ }
}
if (cols) {
for (j = 0; j < 4; j++)
@@ -307,30 +312,22 @@ static void
build_reglist(Parrot_Interp interpreter, IMC_Unit * unit, int first)
{
int i, count, unused, n_symbols;
+ SymHash *hsh = &unit->hash;
+ SymReg * r;
UNUSED(first);
IMCC_info(interpreter, 2, "build_reglist\n");
/* count symbols */
if (unit->reglist)
free_reglist(unit);
- for (i = count = 0; i < HASH_SIZE; i++) {
- SymReg * r = unit->hash[i];
- for (; r; r = r->next) {
- if (r->type & VTREGISTER)
- count++;
- }
- }
+ count = unit->hash.entries;
if (count == 0)
return;
- if (count >= HASH_SIZE)
- IMCC_warning(interpreter, "build_reglist: probably too small HASH_SIZE"
- " (%d symbols)\n", count);
unit->reglist = mem_sys_allocate(count * sizeof(SymReg*));
- for (i = count = 0; i < HASH_SIZE; i++) {
- SymReg * r = unit->hash[i];
- /* Add each symbol to reglist */
- for (; r; r = r->next) {
+ for (i = count = 0; i < hsh->size; i++) {
+ for (r = hsh->data[i]; r; r = r->next) {
+ /* Add each symbol to reglist */
if (r->type & VTREGISTER) {
unit->reglist[count++] = r;
}
@@ -739,14 +736,17 @@ try_allocate(Parrot_Interp interpreter,
int x = 0;
int color;
char *avail;
- int t;
+ int t, n;
unsigned int *graph = unit->interference_graph;
SymReg ** reglist = unit->reglist;
/*
* unit->n_symbols should be an upper limit of needed colors
*/
- avail = mem_sys_allocate(unit->n_symbols + 1);
+ n = unit->n_symbols;
+ if (unit->max_color > n)
+ n = unit->max_color;
+ avail = mem_sys_allocate(n + 1);
while ((imcstack_depth(nodeStack) > 0) ) {
x=imcstack_pop(nodeStack);
Modified: trunk/imcc/symreg.c
==============================================================================
--- trunk/imcc/symreg.c (original)
+++ trunk/imcc/symreg.c Mon Nov 7 05:48:24 2005
@@ -52,11 +52,11 @@ pop_namespace(char * name)
/* Gets a symbol from the hash */
static SymReg *
-_get_sym_typed(SymReg * hsh[], const char * name, int t)
+_get_sym_typed(SymHash * hsh, const char * name, int t)
{
SymReg * p;
- int i = hash_str(name) % HASH_SIZE;
- for (p = hsh[i]; p; p = p->next) {
+ int i = hash_str(name) % hsh->size;
+ for (p = hsh->data[i]; p; p = p->next) {
if (!strcmp(name, p->name) && t == p->set)
return p;
}
@@ -73,7 +73,7 @@ _get_sym_typed(SymReg * hsh[], const cha
* should be changed.
*/
SymReg *
-_mk_symreg(SymReg* hsh[], char * name, int t)
+_mk_symreg(SymHash* hsh, char * name, int t)
{
SymReg * r;
if ((r = _get_sym_typed(hsh, name, t))) {
@@ -100,7 +100,7 @@ SymReg *
mk_symreg(Interp *interp, char * name, int t)
{
IMC_Unit *unit = IMCC_INFO(interp)->last_unit;
- return _mk_symreg(unit->hash, name, t);
+ return _mk_symreg(&unit->hash, name, t);
}
/*
@@ -140,7 +140,7 @@ mk_temp_reg(Interp *interp, int t)
SymReg *
mk_pcc_sub(Interp *interp, char * name, int proto) {
IMC_Unit *unit = IMCC_INFO(interp)->last_unit;
- SymReg *r = _mk_symreg(unit->hash, name, proto);
+ SymReg *r = _mk_symreg(&unit->hash, name, proto);
r->type = VT_PCC_SUB;
r->pcc_sub = calloc(1, sizeof(struct pcc_sub_t));
return r;
@@ -166,9 +166,9 @@ add_namespace(Parrot_Interp interp, IMC_
unit->namespace = g;
g->reg = ns;
g->type = VT_CONSTP;
- if (! (r = _get_sym(IMCC_INFO(interp)->ghash, g->name)) ||
+ if (! (r = _get_sym(&IMCC_INFO(interp)->ghash, g->name)) ||
r->type != VT_CONSTP )
- _store_symreg(IMCC_INFO(interp)->ghash, g);
+ _store_symreg(&IMCC_INFO(interp)->ghash, g);
}
}
@@ -239,7 +239,7 @@ SymReg *
mk_pasm_reg(Interp *interp, char * name)
{
SymReg * r;
- if ((r = _get_sym(cur_unit->hash, name))) {
+ if ((r = _get_sym(&cur_unit->hash, name))) {
free(name);
return r;
}
@@ -352,7 +352,7 @@ mk_const_ident(Interp *interp,
IMCC_fataly(interp, E_SyntaxError,
"global PMC constant not allowed");
}
- r = _mk_symreg(IMCC_INFO(interp)->ghash, name, t);
+ r = _mk_symreg(&IMCC_INFO(interp)->ghash, name, t);
}
else {
if (t == 'P') {
@@ -368,7 +368,7 @@ mk_const_ident(Interp *interp,
/* Makes a new constant*/
SymReg *
-_mk_const(SymReg *hsh[], char * name, int t)
+_mk_const(SymHash *hsh, char * name, int t)
{
SymReg * r = _mk_symreg(hsh, name, t);
r->type = VTCONST;
@@ -384,10 +384,9 @@ _mk_const(SymReg *hsh[], char * name, in
SymReg *
mk_const(Interp *interp, char * name, int t)
{
- SymReg **h = IMCC_INFO(interp)->ghash;
- if (!h)
- h = IMCC_INFO(interp)->ghash =
- mem_sys_allocate_zeroed(HASH_SIZE * sizeof(SymReg*));
+ SymHash *h = &IMCC_INFO(interp)->ghash;
+ if (!h->data)
+ create_symhash(h);
return _mk_const(h, name, t);
}
@@ -425,7 +424,7 @@ add_ns(char *name)
/* Makes a new address */
SymReg *
-_mk_address(Interp *interp, SymReg *hsh[], char * name, int uniq)
+_mk_address(Interp *interp, SymHash *hsh, char * name, int uniq)
{
SymReg * r;
if (uniq == U_add_all) {
@@ -462,7 +461,7 @@ SymReg *
mk_address(Interp *interp, char * name, int uniq)
{
SymReg * s;
- SymReg ** h = *name == '_' ? IMCC_INFO(interp)->ghash : cur_unit->hash;
+ SymHash *h = *name == '_' ? &IMCC_INFO(interp)->ghash : &cur_unit->hash;
s = _mk_address(interp, h, name, uniq);
if (*name == '_')
s->usage |= U_FIXUP;
@@ -476,7 +475,7 @@ mk_address(Interp *interp, char * name,
SymReg *
mk_sub_label(Interp *interp, char * name)
{
- SymReg * s = _mk_address(interp, IMCC_INFO(interp)->ghash,
+ SymReg * s = _mk_address(interp, &IMCC_INFO(interp)->ghash,
name, U_add_uniq_sub);
s->usage |= U_FIXUP;
return s;
@@ -488,7 +487,7 @@ mk_sub_label(Interp *interp, char * name
SymReg *
mk_sub_address(Interp *interp, char * name)
{
- SymReg * s = _mk_address(interp, IMCC_INFO(interp)->ghash,
+ SymReg * s = _mk_address(interp, &IMCC_INFO(interp)->ghash,
name, U_add_all);
s->usage |= U_FIXUP;
return s;
@@ -501,7 +500,7 @@ SymReg *
mk_local_label(Interp *interp, char * name)
{
IMC_Unit *unit = IMCC_INFO(interp)->last_unit;
- return _mk_address(interp, unit->hash, name, U_add_uniq_label);
+ return _mk_address(interp, &unit->hash, name, U_add_uniq_label);
}
/*
@@ -511,7 +510,7 @@ SymReg *
mk_label_address(Interp *interp, char * name)
{
IMC_Unit *unit = IMCC_INFO(interp)->last_unit;
- return _mk_address(interp, unit->hash, name, U_add_once);
+ return _mk_address(interp, &unit->hash, name, U_add_once);
}
@@ -569,7 +568,7 @@ link_keys(Interp *interp, int nargs, Sym
int i, len, any_slice;
char *key_str;
/* namespace keys are global consts - no cur_unit */
- SymReg **h = cur_unit ? cur_unit->hash : IMCC_INFO(interp)->ghash;
+ SymHash *h = cur_unit ? &cur_unit->hash : &IMCC_INFO(interp)->ghash;
if (nargs == 0)
IMCC_fataly(interp, E_SyntaxError,
@@ -653,31 +652,83 @@ free_sym(SymReg *r)
*
*/
+void
+create_symhash(SymHash *hash)
+{
+ hash->data = mem_sys_allocate_zeroed(16 * sizeof(SymReg*));
+ hash->size = 16;
+ hash->entries = 0;
+}
+
+static void
+resize_symhash(SymHash *hsh)
+{
+ SymHash nh;
+ SymReg *r, *next;
+ int new_size = hsh->size << 1;
+ int i, new_i;
+ SymReg ** next_r;
+ int n_next, j, k;
+
+ nh.data = mem_sys_allocate_zeroed(new_size * sizeof(SymReg*));
+ n_next = 16;
+ next_r = mem_sys_allocate_zeroed(n_next * sizeof(SymReg*));
+ for (i = 0; i < hsh->size; i++) {
+ j = 0;
+ for (r = hsh->data[i]; r; r = next) {
+ next = r->next;
+ /*
+ * have to remember all the chained next pointers and
+ * clear r->next
+ */
+ if (j >= n_next) {
+ n_next <<= 1;
+ next_r = mem_sys_realloc(next_r, n_next * sizeof(SymReg*));
+ }
+ r->next = NULL;
+ next_r[j++] = r;
+ }
+ for (k = 0; k < j; ++k) {
+ r = next_r[k];
+ new_i = hash_str(r->name) % new_size;
+ r->next = nh.data[new_i];
+ nh.data[new_i] = r;
+ }
+ }
+ mem_sys_free(hsh->data);
+ mem_sys_free(next_r);
+ hsh->data = nh.data;
+ hsh->size = new_size;
+}
+
/* Stores a symbol into the hash */
void
-_store_symreg(SymReg *hsh[], SymReg * r)
+_store_symreg(SymHash *hsh, SymReg * r)
{
- int i = hash_str(r->name) % HASH_SIZE;
+ int i = hash_str(r->name) % hsh->size;
#if IMC_TRACE_HIGH
printf(" store [%s]\n", r->name);
#endif
- r->next = hsh[i];
- hsh[i] = r;
+ r->next = hsh->data[i];
+ hsh->data[i] = r;
+ hsh->entries++;
+ if (hsh->entries >= hsh->size)
+ resize_symhash(hsh);
}
void
store_symreg(SymReg * r)
{
- _store_symreg(cur_unit->hash, r);
+ _store_symreg(&cur_unit->hash, r);
}
/* Gets a symbol from the hash */
SymReg *
-_get_sym(SymReg * hsh[], const char * name)
+_get_sym(SymHash * hsh, const char * name)
{
SymReg * p;
- int i = hash_str(name) % HASH_SIZE;
- for (p = hsh[i]; p; p = p->next) {
+ int i = hash_str(name) % hsh->size;
+ for (p = hsh->data[i]; p; p = p->next) {
#if IMC_TRACE_HIGH
printf(" [%s]\n", p->name);
#endif
@@ -691,12 +742,12 @@ _get_sym(SymReg * hsh[], const char * na
SymReg *
get_sym(const char * name)
{
- return _get_sym(cur_unit->hash, name);
+ return _get_sym(&cur_unit->hash, name);
}
/* find a symbol hash or ghash */
SymReg *
-_find_sym(Interp *interp, Namespace * nspace, SymReg * hsh[],
+_find_sym(Interp *interp, Namespace * nspace, SymHash * hsh,
const char * name)
{
Namespace * ns;
@@ -712,7 +763,7 @@ _find_sym(Interp *interp, Namespace * ns
p = _get_sym(hsh, name);
if (p)
return p;
- p = _get_sym(IMCC_INFO(interp)->ghash, name);
+ p = _get_sym(&IMCC_INFO(interp)->ghash, name);
if (p)
return p;
return 0;
@@ -723,57 +774,34 @@ SymReg *
find_sym(Interp *interp, const char * name)
{
if (cur_unit)
- return _find_sym(interp, namespace, cur_unit->hash, name);
+ return _find_sym(interp, namespace, &cur_unit->hash, name);
return NULL;
}
void
-_delete_sym(Interp* interp, IMC_Unit * unit, const char * name)
-{
- SymReg ** p;
- int i = hash_str(name) % HASH_SIZE;
- for (p = &unit->hash[i]; *p; p = &(*p)->next) {
- SymReg * deadmeat = *p;
- if (!strcmp(name, deadmeat->name)) {
- *p = deadmeat->next;
- if (deadmeat->life_info){
- free_life_info(unit, deadmeat);
- }
- free_sym(deadmeat);
- return;
- }
- }
-
- IMCC_fatal(interp, 1,
- "_delete_sym: tried to delete nonexistent symbol '%s'\n", name);
-}
-
-
-void
-clear_sym_hash(SymReg **hsh)
+clear_sym_hash(SymHash *hsh)
{
int i;
SymReg * p, *next;
- for (i = 0; i < HASH_SIZE; i++) {
- for (p = hsh[i]; p; ) {
+ for (i = 0; i < hsh->size; i++) {
+ for (p = hsh->data[i]; p; ) {
next = p->next;
- free_sym(p);
- p = next;
- }
- hsh[i] = NULL;
+ free_sym(p);
+ p = next;
+ }
+ hsh->data[i] = NULL;
}
+ hsh->entries = 0;
}
-void debug_dump_sym_hash(SymReg **hsh);
-
void
-debug_dump_sym_hash(SymReg **hsh)
+debug_dump_sym_hash(SymHash *hsh)
{
int i;
SymReg * p;
- for (i = 0; i < HASH_SIZE; i++) {
- for (p = hsh[i]; p; p = p->next) {
+ for (i = 0; i < hsh->size; i++) {
+ for (p = hsh->data[i]; p; p = p->next) {
fprintf(stderr, "%s ", p->name);
}
}
@@ -785,9 +813,9 @@ clear_locals(IMC_Unit * unit)
{
int i;
SymReg * p, *next;
- SymReg **hsh = unit->hash;
- for (i = 0; i < HASH_SIZE; i++) {
- for (p = hsh[i]; p; ) {
+ SymHash *hsh = &unit->hash;
+ for (i = 0; i < hsh->size; i++) {
+ for (p = hsh->data[i]; p; ) {
next = p->next;
if (unit && p->life_info) {
free_life_info(unit, p);
@@ -795,29 +823,20 @@ clear_locals(IMC_Unit * unit)
free_sym(p);
p = next;
}
- hsh[i] = NULL;
+ hsh->data[i] = NULL;
}
+ hsh->entries = 0;
}
/* Clear global symbols */
void
clear_globals(Interp *interp)
{
- int i;
- SymReg * p, *next;
+ SymHash *hsh = &IMCC_INFO(interp)->ghash;
- if (!IMCC_INFO(interp)->ghash)
+ if (!hsh->data)
return;
- for (i = 0; i < HASH_SIZE; i++) {
- for (p = IMCC_INFO(interp)->ghash[i]; p; ) {
- next = p->next;
- if (p->type & VTADDRESS)
- p->first_ins = p->last_ins = NULL;
- free_sym(p);
- p = next;
- }
- IMCC_INFO(interp)->ghash[i] = NULL;
- }
+ clear_sym_hash(hsh);
}
Modified: trunk/imcc/symreg.h
==============================================================================
--- trunk/imcc/symreg.h (original)
+++ trunk/imcc/symreg.h Mon Nov 7 05:48:24 2005
@@ -1,11 +1,6 @@
#if !defined(PARROT_IMCC_SYMREG_H_GUARD)
#define PARROT_IMCC_SYMREG_H_GUARD
-/* constants */
-
-#define HASH_SIZE 25013
-
-
/* types */
enum VARTYPE { /* variable type can be */
@@ -84,6 +79,11 @@ typedef struct _SymReg {
int pmc_type; /* class enum */
} SymReg;
+typedef struct _SymHash {
+ SymReg ** data;
+ int size;
+ int entries;
+} SymHash;
/* namespaces */
@@ -184,20 +184,22 @@ SymReg * find_sym(Interp *, const char *
SymReg * get_sym(const char * name);
SymReg* get_pasm_reg(Interp* interpreter, char *name);
SymReg* get_const(Interp *interpreter, const char *name, int type);
-SymReg * _get_sym(SymReg * hash[], const char * name);
-SymReg * _mk_symreg(SymReg* hash[],char * name, int t);
-SymReg * _mk_const(SymReg *hash[], char * name, int t);
-void _store_symreg(SymReg *hash[], SymReg * r);
-SymReg * _mk_address(Interp *, SymReg *hash[], char * name, int uniq);
+SymReg * _get_sym(SymHash *hash, const char * name);
+SymReg * _mk_symreg(SymHash *hash,char * name, int t);
+void create_symhash(SymHash *hash);
+SymReg * _mk_const(SymHash *hash, char * name, int t);
+void _store_symreg(SymHash *hash, SymReg * r);
+SymReg * _mk_address(Interp *, SymHash *hash, char * name, int uniq);
SymReg * link_keys(Interp *, int nargs, SymReg *keys[]);
void clear_locals(struct _IMC_Unit *);
-void clear_sym_hash(SymReg **);
+void clear_sym_hash(SymHash *);
void clear_globals(Interp *);
unsigned int hash_str(const char * str);
-void _delete_sym(Interp *, struct _IMC_Unit *, const char * name);
SymReg * dup_sym(SymReg *r);
+void debug_dump_sym_hash(SymHash *hsh);
-SymReg * _find_sym(Interp *,Namespace * ns, SymReg * hash[], const char *
name);
+
+SymReg * _find_sym(Interp *,Namespace * ns, SymHash *hash, const char * name);
char * _mk_fullname(Namespace * ns, const char * name);
char * mk_fullname(const char * name);
void push_namespace(char * name);
@@ -206,3 +208,13 @@ void pop_namespace(char * name);
#endif /* PARROT_IMCC_SYMREG_H_GUARD */
+/*
+ * Local variables:
+ * c-indentation-style: bsd
+ * c-basic-offset: 4
+ * indent-tabs-mode: nil
+ * End:
+ *
+ * vim: expandtab shiftwidth=4:
+*/
+
Modified: trunk/imcc/unit.h
==============================================================================
--- trunk/imcc/unit.h (original)
+++ trunk/imcc/unit.h Mon Nov 7 05:48:24 2005
@@ -20,7 +20,7 @@ typedef struct _IMC_Unit {
IMC_Unit_Type type;
Instruction * instructions;
Instruction * last_ins;
- SymReg ** hash;
+ SymHash hash;
Symbol * sym;
int bb_list_size;
int n_basic_blocks;
@@ -36,6 +36,7 @@ typedef struct _IMC_Unit {
unsigned int* interference_graph;
SymReg** reglist;
int n_symbols;
+ int max_color;
struct _IMC_Unit * prev;
struct _IMC_Unit * next;
