develooper Front page | perl.perl6.internals | Postings from November 2004

Continuations, basic blocks, loops and register allocation

Thread Next
Leopold Toetsch
November 13, 2004 08:54
Continuations, basic blocks, loops and register allocation
Message ID:
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
   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

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,

Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About