petdance/scratch — Issue #401: Register allocator and lexicals bug
Author: petdance
Created: 2011-11-01 05:42:15+00:00
State: open
Labels: bug, imcc, Pri-blocker, Sev-high

Code:
{{{
.sub ''
$P42 = new ['Integer']
.lex 'i', $P42
$P69 = new ['Integer']
.lex 'j', $P69
.lex 'foo', $P10
.lex 'bar', $P11
.lex 'baz', $P12
$P3 = new ['String']
.lex 'k', $P3

$P100 = new ['String']
$P100 = "oh no"
store_lex 'foo', $P100
$P101 = find_lex 'bar'
say $P101
.end
}}}

Should be a null PMC access, but prints "oh no". It looks like

{{{
.lex 'foo', $P0
}}}

isn't considered an instruction, but just saying "this lexical goes in this register". If that's the only mention of $P0, then there's no "first instruction". It builds a du-chain, then based on that throws away $P0 from the "needs allocation" list because it confuses it with an unused register (e.g. it thinks it got optimized out, which is not the case at all here).

This patch makes the issue go away:

{{{
diff --git a/compilers/imcc/reg_alloc.c b/compilers/imcc/reg_alloc.c
index de0f3e0..300216d 100644
--- a/compilers/imcc/reg_alloc.c
+++ b/compilers/imcc/reg_alloc.c
@@ -391,6 +391,9 @@ reg_sort_f(ARGIN(const void *a), ARGIN(const void *b))
const SymReg * const ra = *(const SymReg * const *)a;
const SymReg * const rb = *(const SymReg * const *)b;

+ if (!ra->first_ins || !rb->first_ins)
+ return 0;
+
if (ra->first_ins->index < rb->first_ins->index)
return -1;

@@ -473,7 +476,7 @@ build_reglist(PARROT_INTERP, ARGMOD(IMC_Unit *unit))

/* we might have unused symbols here, from optimizations */
for (i = count = unused = 0; i < n_symbols; i++) {
- if (!unit->reglist[i]->first_ins)
+ if (!unit->reglist[i]->first_ins && !(unit->reglist[i]->usage & U_LEXICAL))
unused++;
else if (i == count)
count++;
@@ -716,7 +719,7 @@ vanilla_reg_alloc(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
SymReg *r;
for (r = hsh->data[i]; r; r = r->next) {
/* TODO Ignore non-volatiles */
- if (REG_NEEDS_ALLOC(r) && r->use_count)
+ if (REG_NEEDS_ALLOC(r))
r->color = -1;
}
}
@@ -732,7 +735,7 @@ vanilla_reg_alloc(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
for (r = hsh->data[i]; r; r = r->next) {
if (r->set != reg_set)
continue;
- if (REG_NEEDS_ALLOC(r) && (r->color == -1) && r->use_count) {
+ if (REG_NEEDS_ALLOC(r) && (r->color == -1)) {
if (set_contains(avail, first_reg))
first_reg = first_avail(interp, unit, reg_set, NULL);

}}}

But it's kinda hacky. OTOH, so is the register allocator as a whole, and this is blocking me on NQP, so provided we can be sure we don't make the quicksort of symbols to allocate unstable I'd be OK with something like this going in. Will leave it until tomorrow to see if anyone has any better ideas.

Originally http://trac.parrot.org/parrot/ticket/2087