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.
--
Chip Salzenberg <[EMAIL PROTECTED]>
