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 15, 2004 04:03
Subject:
Re: Continuations, basic blocks, loops and register allocation
Message ID:
200411151104.iAFB4nl17963@thu8.leo.home
Bill Coffman <bill.coffman@gmail.com> wrote:
> On Sun, 14 Nov 2004 17:03:33 -0500, Dan Sugalski <dan@sidhe.org> wrote:

>> We don't really have that much of a problem. What we have is just
>> something more simple -- the target of a continuation marks the start
>> of a basic block. That means that we have to assume everything we
>> don't get handed back from the function's dirty and should be
>> refetched.

> I tend to agree that this is not such a problem.  Basically, Parrot
> has various control flow possibilities that were not previously
> considered.  (1) An exception can happen in a try block, so CFG arcs
> need to be added from statements within the try block to the catch.

I've already proposed a simple solution for the exception case:

   new eh, Exception_Handler
   set_eh eh, catch_label
   # try block
  catch_label:
   # catch block

The try block is starting exactly at this point, where the exception
handler gets pushed onto the contol stack. By connecting the C<set_eh>
opcode to the catch block with an edge in the CFG, we could easily
prevent the reuse of registers located in front of the try block.

> (2) Continuations, which I don't pretend to understand, can also flow
> in previously unconsidered directions.  Those arcs need to be added to
> the CFG.

As said: there are no invisible continuations taken. From an HLL point
of view, it's very clear what is happening.

> For continuations, however, it seems like those really are control
> flow arcs that need to be added.  If analysis can trim a few of them,
> then that would be great, but if people are using continuations, maybe
> they shouldn't expect high performance, and extra register spilling
> may be another side effect.

If you insert automatically these CFG edges you can't trim them down,
there is no such analysis that could find points, where it isn't
necessary. So we have the performance degradation for *all* subs,
because w/o any compiler hints any subroutine invocation could act as a
loop.

Again - we'd get such loops:

   sub1()  <---+  <---------+
   ...         |            |
   sub2()  ----+    <-+     |
   ...                |     |
   sub3()  -----------+-----+

The backward branches are going to the opcode after the invoke. You'd
have to connect sub 1..n to sub 0..n-1. This are 81 loops for calling 10
subroutines in a row. This kills for sure all efforts the register
allocator might take, we'll end up with spilling a lot.

> ~Bill

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