Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

leo (5366)

leo
  (email not shown publicly)

Journal of leo (5366)

Monday November 07, 2005
06:24 PM

"The Continuation Bug" is gone

[ #27504 ]

Today I've checked in the final fix for one of the longest outstanding bugs inside Parrot.

A short recap:

Having first-class continuation objects is one of the design goals of Parrot. A lot of HLLs support continuations with some special syntax and with continuations in the core a lot of HLL control structures and features like exceptions can be implemented easily.

But there was a problem with continuations. Continuations can change the CFG (control flow graph) of a program in such a way that there are suddenly loops, where the register allocation code isn't (and can't be) aware of it.

The following code piece from a test provided by Piers revealed the whole problem:

arr1 = "[1, 3, 5]"
arr2 = "[1, 5, 9]"
x = choose(arr1)
y = choose(arr2)
if (x * y != 15)
fail = find_lex "fail"
fail()

To the register allocator this looks like a linear control flow, which is just executed once (there is no loop outside of that code snippet). But actually the choose closures are capturing their continuations and are backtracking through the call to the fail function. We suddenly have a loop going from fail() to one of the choose() function call returns. The code that the register allocator should have been considering would be something like this:

  arr1 = "[1, 3, 5]"
  arr2 = "[1, 5, 9]"
choose_again_1: # label actually in front of function return
  x = choose(arr1)
choose_again_2:
  y = choose(arr2)
  if (x * y != 15)
  fail = find_lex "fail"
  fail()
  goto choose_again_1 or _2

This implies that the registers of the variables x, y, arr2 can't be reused for example to assign a register to the fail variable. But exactly this has happened and the code really "fail"ed.

There were some (IMHO) impractical proposals to fix this, like refetching all variables from lexicals all the time (and don't use native integers and numbers because these aren't lexicals) but the real fix for this is now in: that is - just don't reallocate the registers used by lexicals and non-volatile variables to other variables like temporaries.

That's the reason for variable-sized register frames and, well, some lack of visible progress of Parrot development for some time.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.