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

Re: Continuations, basic blocks, loops and register allocation

Thread Previous | Thread Next
From:
Jeff Clites
Date:
November 13, 2004 10:52
Subject:
Re: Continuations, basic blocks, loops and register allocation
Message ID:
30B73C8A-35A5-11D9-AFE8-000393A6B9DA@mac.com
On Nov 13, 2004, at 8:53 AM, Leopold Toetsch wrote:

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

That analysis looks correct to me--any time you have a function call, 
the subsequent op might be a branch target, if there is a subsequent 
function call.

> We'd have just to force using lexicals for all vars

Having variable-size register sets would solve this, since you could 
have fixed assignments of variables to registers, and not have to 
suffer the overhead of moving data between registers and lexical pads 
over-and-over. Well, it doesn't really "solve" it--just makes it 
workable.

JEff


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