register allocation
Bill Coffman
I have addressed almost all the code issues from the last patch. That
broke some things, which I had to fix, but they're fixed. A couple
other improvements too. Here's the state of things:
* I have the below failed tests. I haven't looked into these. Can
someone tell me if the tests are broken, or is my allocator broken. I
know they don't fail for the current cvs code (as of yesterday).
Failed Test Stat Wstat Total Fail Failed List of Failed
-------------------------------------------------------------------------------
t/library/dumper.t 13 3328 13 13 100.00% 1-13
t/op/gc.t 1 256 18 1 5.56% 13
t/pmc/sub.t 1 256 78 1 1.28% 78
4 tests and 59 subtests skipped.
Failed 3/124 test scripts, 97.58% okay. 15/1975 subtests failed, 99.24% okay.
* Still have a memory leak that blocks Dan's evil code from compiling.
* Run time isn't so great, with 10x gcc -O2, for 200 symbols, and 100x
for 500 syms. Below, is for 1000 syms. Still, this is much better
than the previous allocator, which crashed my workstation around 130
symbols.
#vars gcc parrot
198 6.84 66.88
199 7.29 82.03
200 9.86 109.86
500 0.74 125.39
501 0.68 99.53
999 1.68 755.30
1000 2.06 988.55
1001 1.79 723.25
* Considerable improvements are on the way. Some are fairly low
hanging fruit, but my biggest worry is not to break things along the
way, which is all too easy to do.
~Bill
Bill Coffman
Leopold Toetsch
> Hello,
> I have addressed almost all the code issues from the last patch.
> * I have the below failed tests.
> Failed Test Stat Wstat Total Fail Failed List of Failed
> -------------------------------------------------------------------------------
> t/library/dumper.t 13 3328 13 13 100.00% 1-13
> t/op/gc.t 1 256 18 1 5.56% 13
> t/pmc/sub.t 1 256 78 1 1.28% 78
These tests should be sane. While the first two .t are fairly complex,
t/pmc/sub_78.imc is quite simple. You could compare the produced code
of "parrot -o- foo.imc". Run it with "-t" to see, where output differs.
> * Still have a memory leak that blocks Dan's evil code from compiling.
$ valgrind --leak-check=yes --show-reachable=yes ./parrot --leak-test foo.imc
(there are some other leaks, so just have a look at increasing leak
counts for increased symbol usage)
> * Run time isn't so great,
We'll address that later.
Please post patch.
leo
Leopold Toetsch
> Hello,
> * I have the below failed tests. I haven't looked into these. Can
> someone tell me if the tests are broken, or is my allocator broken. I
> know they don't fail for the current cvs code (as of yesterday).
>
> Failed Test Stat Wstat Total Fail Failed List of Failed
> -------------------------------------------------------------------------------
> t/library/dumper.t 13 3328 13 13 100.00% 1-13
> t/op/gc.t 1 256 18 1 5.56% 13
> t/pmc/sub.t 1 256 78 1 1.28% 78
These errors look remarkable the same, when I turn on OPT_SUB that is,
when allocate_wanted_regs() is used. And this code did miss registers
sets like 'K' (compound keys).
Changing imcc/reg_alloc.c:890 to:
if (r->color >= 0 || r->want_regno == -1 || strchr("ISPN", r->set
== 0))
did fix this flaw.
leo
Bill Coffman
CVS tree. I did nothing more than insert a conflict checker into
reg_alloc.c That is, whatever pre-colored registers have been
assigned to symbols, I verify that none of them are conflicting.
Guess what I got?
make[1]: Leaving directory `/usr/home/coffman/dev/parrot/parrot/docs'
./parrot -o runtime/parrot/library/Data/Dumper/Base.pbc
runtime/parrot/library/Data/Dumper/Base.imc
********** <<< added new here
node 1 = defname(S) is colored 5 and neighbor 9 = S5(S) is colored 5
parrot: imcc/reg_alloc.c:200: imc_reg_alloc: Assertion `r->color==-1
|| r->color != unit->reglist[y]->color' failed.
make: *** [runtime/parrot/library/Data/Dumper/Base.pbc] Aborted
The routine you mentioned, allocate_wanted_regs() doesn't assign
wanted regs if in conflict, but as far as I can tell, there's no check
on the integrity of precolored nodes. Not quite sure what the correct
behaviour is for allocator, when it's given conflicts.
I saw 'K' compounded key somewhere, but don't know what it is. I know
reg_alloc.c pretty well though. Offhand I'd say it's not handled in
reg_alloc. Maybe it should be?
~Bill
Leopold Toetsch
> Interesting. I did a little more research, and checked out a fresh
> CVS tree.
I've committed the tailcall patch a minute ago with that one line
changed in reg_allog.c - please rediff.
> ... I did nothing more than insert a conflict checker into
> reg_alloc.c
> The routine you mentioned, allocate_wanted_regs() doesn't assign
> wanted regs if in conflict, but as far as I can tell, there's no check
> on the integrity of precolored nodes. Not quite sure what the correct
> behaviour is for allocator, when it's given conflicts.
These precolored wanted_regs are created for function arguments and
return values only (and for registers used during function calls).
And indeed, if there is a conflict the register shouldn't get a color.
Seems to work now, as I don't get these test failures anymore.
> I saw 'K' compounded key somewhere, but don't know what it is.
It's a notion for a key like in:
set P1, P2["abc" ; 1]
set_p_p_kc
The last arg is a r->set := 'K' and points to a chain of other
SymRegs. It's actually a PMC entry in the contant table, where the color
is the index in constants.
>... I know
> reg_alloc.c pretty well though. Offhand I'd say it's not handled in
> reg_alloc. Maybe it should be?
No, that's ok. Constants are handled in imcc/pbc.c and aren't affected
by reg_alloc.c at all.
> ~Bill
leo
Leopold Toetsch
>
> You're patch looks suspiciously like a typo. strchr("ISPN", r->set == 0))
Brrr, massive lack of coffein must have misdirect my fingers ...
I'll check it.
For now please just don't call allocate_wanted_regs().
Thanks,
leo
Leopold Toetsch
> Hello,
> * I have the below failed tests.
> t/library/dumper.t 13 3328 13 13 100.00% 1-13
These are fixed (assignment collisions in pcc.c)
> t/op/gc.t 1 256 18 1 5.56% 13
Is very similar to the case below - gc_14 (you might read that one
first, it's a bit simpler). The variable C<arr2> is assigned to P17. In
gc_13.imc:80 the temp C<$P0> is also getting this register. Now when
the algorithm backtracks over "y = choose(arr2)" arr2 in P17 is
clobbered and we get "shift_pmc() not implemented in class 'Closure'".
(You can turn on these print statements to see the flow of operations)
There is no sign in the source code, that the control flow from calling
choose() the second time to calling the "fail" closure might be a branch
target. We basically have a loop (due to the continuation usage), which
the register allocator can't be aware of.
Inserting a label e.g.
lp:
y = choose(arr2)
and a "branch lp" after the call to the "fail" closure hides the
problem, because with that loop, C<arr2> is preserved. (arr1 is still
clobbered, but the algorithm doesn't bactrack there again).
> t/pmc/sub.t 1 256 78 1 1.28% 78
tb_loop:
set P17, P16[K16]
^^^^^
Somewhere a SymReg with set 'K' has slipped into the register allocator.
Excluding r->set != 'K' in build_reglist():405 fixes that.
Now failing too is t/op/gc_14 (and an exception test, which is the
same). These 2 are a bit tricky and I don't know, which result is
correct - or better there is probably no answer.
We have this recursive method:
sub b11 method
.param int n
.local int n1
n1 = n + 1
newsub $P0, .Exception_Handler, catch
set_eh $P0
n = self."b11"(n1)
clear_eh
catch:
.pcc_begin_return
.return n
.pcc_end_return
.end
C<n1> is going into the recursive call, C<n> is the return result. Now
it depends on the register allocator which register C<n1> and C<n> have.
When the allocator isn't really clever then it assigns different
registers. So C<n> is preserved when the exception is fired as the
recursion limit is hit.
The new allocator assigns both C<n1> and C<n> to the same Parrot
register. This is technically correct, as the life-span of C<n> ends on
the line where it's used as a return result of the recursive method call.
Therefore we have a piece of code that in the presence of exceptions may
behave differently depending on some implementation details. This is
AFAIK very the same, as the gcc warning we had until a few days about a
possibly clobbered variable used around setjmp (s. src/inter_run.c:55,
and the variable offset. (It's a volatile now)
This is totally the same variable usage like above's C<n> and the result
depends on register allocation details.
> ~Bill
leo