Re: Continuations, basic blocks, loops and register allocation

[Jeff Clites]

On Nov 14, 2004, at 3:03 AM, Leopold Toetsch wrote:
Matt Fowles <[EMAIL PROTECTED]> wrote:
Yes, but in the case of the continuation resuming after foo, the
continuation should restore the frame to the point where it was taken.
 Thus all of the registers will be exactly as they were when the
continuation was taken (i.e. in the correct place).
Yes, but Jeff's example wasn't really reflecting the problem.
How come? (Not quibbling--just afraid I'm missing something.) It seems 
that even this function body shows the problem:

        a = 1
        foo()
        print a
        b = 10
        return b
It would seem (w/o continuations) that b should be able to re-use a's 
register, but if it does then we'll print 10 instead of 1 "the second 
time".

So what to do:
1) Extending register frame size ad infinitum and never reuse a Parrot
register will definitely blow caches.
2) Generating an edge for every call to every previous calls will blow
the CFG and cause huge pressure on the register allocator. A lot of
spilling will be the result.
3) Using lexicals all over is slower (but HLL compilers will very 
likely
emit code that does exactly that anyway). So the problem may not be a
real problem anyway. We just know that an optimizer can't remove the
refetch of lexicals in most of the subroutines.
It seems that, in term of cache locality, the same problem is there 
with more registers v. spilling v. lexicals. That is, if you have 100 
local variables whose lifetimes overlap (due to continuations), then 
you need 100 distinct memory locations to (repeatedly) access.

4) Having an explicit syntax construct "(call-with-current-continuation
" that expresses verbatim, what's going on, like e.g. with a reserved
word placed as a label:
  RESUMEABLE: x = choose(arr1)
I don't think that really helps either: If you have such a call, then 
all the frames higher up the stack also can "return multiple times", so 
they have the behavior, even w/o the label.

On the other hand, this Ruby code really bugs me (note: "$" variables 
in Ruby are globals):

% cat continuation5.ruby
def strange
    callcc {|continuation| $saved = continuation}
end
def outer
    a = 0
    strange()
    a = a + 1
    print "a = ", a, "\n"
    a = "hello"
    print "a = ", a, "\n"
end
outer()
$saved.call
% ruby continuation5.ruby
a = 1
a = hello
continuation5.ruby:8:in `+': failed to convert Fixnum into String 
(TypeError)
        from continuation5.ruby:8:in `outer'
        from continuation5.ruby:14

What bugs me is that "outer" gets an error when the continuation is 
invoked, because "the second time" strange() returns, "a" is a string 
and so you can't add 1 to it. But looking at the definition of "outer", 
you'd expect that you could never get such an error. (Without the line 
setting "a" to "hello", you get an infinite loop, printing increasing 
integers.)

JEff