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

Re: Continuations, basic blocks, loops and register allocation

Thread Previous | Thread Next
From:
Leopold Toetsch
Date:
November 14, 2004 04:51
Subject:
Re: Continuations, basic blocks, loops and register allocation
Message ID:
200411141103.iAEB3ld13952@thu8.leo.home
Matt Fowles <ubermatt@gmail.com> wrote:
> Jeff~

> Yes, but in the case of the continuation resuming after foo, the
> continuation should restore the frame to the point where it was taken.
>  Thus all of the registers will be exactly as they were when the
> continuation was taken (i.e. in the correct place).

Yes, but Jeff's example wasn't really reflecting the problem.

The case I've shown looks like:

   .local pmc arr1, arr2
   arr1=[1,3,5]
   arr2=[1,5,9]
   x = choose(arr1)
   y = choose(arr2)
   # arr2 never used beyond
   $P0 = ...

At the last line the register allocator happily reuses the register that
arr2 had for $P0. That's totally legal in the absence of continuations.
So it doesn't suffice that the register frame is restored and that
variables are in the same place.

The effect of the continuation is the creation of a loop in the CFG.
Life time of variables and thus register allocation is different within
loops.

> Exceptions handlers, on the other hand, are a different story, because
> anything that is used in the catch block must be kept in the correct
> place through out the entire try block.

No they aren't really different. The presence of an exception handler
(and the code for installing such a handler) is more visible in PIR.
That's the only difference.

But again up to the above continuation example. The scheme source of the
relevant parts is this:

  (define (choose . all-choices)
    (let ((old-fail fail))
      (call-with-current-continuation
       (lambda (continuation)
       ...
  (let ((x (choose 1 3 5))
        (y (choose 1 5 9)))

In that source it's obvious that the continuations of choose are
captured in the local closures created by the lambda. So it's probably
just a lack of the compiler (and a lack of PIR syntax) to express the
relevant information that the call to choose has the possible
side-effect of being resumed just after the created "invokecc" opcode.

So from a HLL point of view that's all visible and clear.

<cite author="Piers">And, damnit, making a full continuation isn't
something a programmer should do lightly.
</cite>

And of course an HLL compiler can't and doesn't emit some code that
captures a continuation silently and w/o any reason.

So what to do:

1) Extending register frame size ad infinitum and never reuse a Parrot
register will definitely blow caches.

2) Generating an edge for every call to every previous calls will blow
the CFG and cause huge pressure on the register allocator. A lot of
spilling will be the result.

3) Using lexicals all over is slower (but HLL compilers will very likely
emit code that does exactly that anyway). So the problem may not be a
real problem anyway. We just know that an optimizer can't remove the
refetch of lexicals in most of the subroutines.

4) Having an explicit syntax construct "(call-with-current-continuation
" that expresses verbatim, what's going on, like e.g. with a reserved
word placed as a label:

  RESUMEABLE: x = choose(arr1)

leo

Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About