Hello,

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

Trying again...

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.

$ 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)

We'll address that later.

Please post patch.

leo

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

Interesting.  I did a little more research, and checked out a fresh
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

I've committed the tailcall patch a minute ago with that one line
changed in reg_allog.c - please rediff.

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.

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.

No, that's ok. Constants are handled in imcc/pbc.c and aren't affected
by reg_alloc.c at all.

leo

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

These are fixed (assignment collisions in pcc.c)

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).

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.

leo