Front page | perl.perl6.internals |
Postings from November 2004
As the analysis of test errors of the new reigster allocator has shown,
we have a problem WRT register allocation. This problem isn't new, but
as the allocator is more efficiently reusing registers (or reusing them
in a different way) it's exposed again.
0) The register allocator isn't to blame, that looks really fine.
We have two kinds of problems one with exceptions and one with
continuations. As exceptions are continuations, we could also define it
as the same problem. Anyway, the usage of exceptions is a bit different.
Catch blocks are local labels only AFAIK in HLL. Parrot allows currently
a Sub too, but that might be bogus.
1) Exceptions (see t/op/gc_14.imc)
We have a typical usage showing the problem like:
n = x
... # code that can reuse register of n
newsub eh, .Exception_Handler, catch
set_eh eh
# code that migth through
n = y
clear_eh
catch:
print n
Now the register allocator just doesn't know that there exists a control
flow graph edge from anywhere in the try block to the catch label. The
register of variable n from the first statement is therefore not
preserved, as it's reassigned in the try block. So the catch block can
get the wrong value (neither x nor y) of n.
A simble solution could look like:
n = x
new eh, .Exception_Handler
set_eh eh, catch
# code that might through
n = y
clear_eh
catch:
with the changed opcode C<set_eh (in PMC, labelconst INT).
This would suffice to make a real branch target out of the catch label
and the register allocator should do the right thing. You can test that
by inserting "unless $P0, catch" after "set_eh" in the mentioned test.
(there is some code in imcc that specially treats newsub, but the newsub
ocpode isn't the branch - basically everything below C<set_eh> may
branch to the catch label)
(Did I already mention that implict behavior like using a register or
branching is bad)
2) Continuations (t/op/gc_13.imc [Hi Piers])
Again we have a hidden branch done by a Continuation, or better a loop.
The control flow of the main program is basically represented by this
conventional code fragment:
arr1=[...]; arr2=[...]
loop1: x = choose(arr1)
loop2: y = choose(arr2)
...
failed = fail()
goto (loop1, loop2)[failed]
except that the gotos are performed by backtracking via the
continuations. So we don't have these loop labels and the continuation
continues at the next opcode after the invocation of choose() and not at
the shown position above.
So again, the register allocator doesn't see that there is a branch, the
variable's arr2 register is clobbered, in this case by the fail closure.
As we never know, if a subroutine captures the return continuation and
creates such loops like above, we have in the absence of other syntax
actually no chance to hold any variable in a register as far as I can
see now. We'd have just to force using lexicals for all vars, except for
leaf subroutines (that don't call other subs) or subs that just call one
sub (they can't create loops).
Another idea is to create edges from all 1..n function calls in a sub to
the previos 0..n-1 calls, so that basically all possible loops done via
possible continuations are represented in the CFG.
Comments welcome,
leo
Thread Next