Chip Salzenberg <[EMAIL PROTECTED]> writes:
> On Wed, Jun 08, 2005 at 10:26:59PM +0100, The Perl 6 Summarizer wrote:
>> Loop Improvements
>> Oh no! It's the register allocator problems again. One of these days I
>> swear I'm going to swot up on this stuff properly, work out whether it's
>> really the case that full continuations break any conceivable register
>> allocator and summarize all the issues for everyone in a nice white
>> paper/summary.
>
> "It's not really that complicated. It just takes a long time to explain."
> -- Dr. Howland Owll, on SubGenius doctrine
>
> Consider this code:
>
> sub example1 {
> my $a = foo();
> print $a;
> my $b = bar();
> print $b;
> }
>
> It's obvious that $a and $b can be allocated the same register because
> once $b has been set, $a is never used again.
>
> (Please ignore that $a and $b are variables that can't be stored
> purely in registers. The real world case that I'm illustrating deals
> with temporaries and other values that lack user-visible names. But
> the issue is best illustrated this way.)
>
> Now consider this:
>
> sub example2 {
> my $a = foo();
> do {
> print $a;
> $b = bar();
> print $b;
> } while ($b);
> }
>
> You can see that it's now *not* OK to allocate $a and $b to the same
> register, because the flow of control can jump back to the print $a
> even after $b is assigned.
>
> Look at the first function again, and consider what happens if &foo
> captures its return continuation _and_&bar_invokes_it_. It would
> effectively amount to the same issue as example2:
>
> sub foo {
> $a = 1;
> foo();
> _implicit_label_for_return_continuation:
> print $a;
> $b = bar();
> print $b;
> }
>
> bar() {
> if rand() < 0.5 { goto _implicit_label_for_return_continuation }
> return "lucky";
> }
>
> Therefore, register allocation must allow for implicit flow of control
> from *every* function call to *every* function return ... or, more
> precisely, to where *every* continuation is taken, including function
> return continuations.
Buf if you fallow the calling conventions that looks like:
sub foo {
$a = 1.
$c = 10;
print $c
save_dollar_a_and_only_dollar_a_because_im_going_to_use_it_after_this_function_call
foo()
_implicit_label_for_return_continuation:
restore_dollar_a
_ooh_i_dont_have_to_save_anything
$b = bar()
_nor_do_i_have_to_restore_anything
print $b
}
That's what caller saves means. You only have to save everything that you're
going to care about after the function returns. You don't have to save the
world, because if it was important it's already been saved further up the call
chain.
This means, of course, that the continuation needs to save the state of the
restore stack, but I thought we already knew that.
Of course, if you're going to actually use GOTO to get to some label that you
should only get to via a continuation (as you do in the code example) then you
deserve to get everything you've got coming to you. A continuation must contain
everything needed to restore the user registers to the correct state no matter
how many times they were taken.
I really don't see how this affects register allocation; the call to bar
doesn't need to save $a because it's not referred to (lexically) after the call
returns. So what if the call to bar might take a continuation. Taking that
continuation should be exactly equivalent to returning from the call to
foo. You really have to stop thinking of continuations as gotos.
