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.
