Register stacks, return continuations, and speeding up calling
Dan Sugalski
*again* (I had this down for next month, but I guess it's a chaotic
cycle). Normally I'd just let it spin out, but we *do* have an issue
with sub call speeds, and I don't see how fiddling with this will do
any harm otherwise.
We've two big issues with sub calling.
The first is the CPS style chews through continuation objects at a
massive rate, and using them means that everything needs to be COW.
The second is that with the register file, we're doing a lot of
copying of data on each sub call and, while code can (though at the
moment really doesn't) restrict which sets of registers gets saved,
that doesn't work for indirect calls to bytecode, via vtable
functions and whatnot.
I've solutions of a sort for both problems.
For the first, we've got the infrastructure in place to do what we
need. A return continuation can be recycled *if* we know it hasn't
been used. With the return continuation register, that's now easy.
First, we remove the return continuation from the registers the
called sub/method sees. The continuation's still there, in the return
register, but it's not in the general register set. Next, we
distinguish between actual and potential continuations.
A return continuation is a *potential* continuation. That is, it
*can* be a full continuation, but until something actually does
something to it, most of its continuation-ness can be deferred. That
is, unless something takes a real continuation or fetches the return
continuation out of the return continuation register (thus turning it
from potential to actual) the continuation can be safely recycled
once invoked and doesn't have to go COW-marking stacks or anything.
This does mean that we'd want to encourage people to use the
<invoke>cc ops to call a function or method (as they're the only ones
that can safely create a potential continuation) and use the return
op to invoke the return continuation in the return continuation
register (so it can then go recycle the continuation after extracting
out all the good bits)
Taking a continuation can *also* mark the current interpreter
structure as dirty. That way when return is invoked, if the
interpreter *isn't* dirty we can immediately recycle the register
file if we choose to hang the current register file off a pointer.
For the register copying problem, we've a couple of options. At the
moment I'm leaning towards re-abstracting out the register file and
hanging it off a pointer in the interpreter structure. We can
allocate a new register file when making a sub call and only copy the
relevant bits into it as a sort of extra bonus for speed. (And copy
back only the relevant bits on return) The two downsides to this are
that it does slow access to the actual registers, which'll impact the
interpreter by a bit, and it will completely invalidate all the
existing JIT code.
I'll note that I'm not sure that the register copying issue will
truly be an issue in most code, if proper save/restore sets are done,
which could be helped by hints passed to the pir compiler by whatever
compiler modules are being used. On the other hand, looking at the -t
output from The Work Project, I see a near-insane amount of bytecoded
vtable method calling, so I'm willing to accept that it'll be an
issue for many people. (I'd not have the problem if my data types had
their vtable functions written in C. I chose not to for
implementation speed reasons and because the dynloading stuff was
badly broken when I needed them. I'm reasonably sure that the big
languages (perl/python/ruby/tcl (Hi Wil) will have their basic PMC
classes all done up in C)
I think this makes some sense, but I'm kinda sick at the moment, so
it may not. (OTOH, being ill is likely why I'm looking at this again,
so we take the good with the bad...)
--
Dan
--------------------------------------it's like this-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk
Leopold Toetsch
> The first is the CPS style chews through continuation objects at a
> massive rate, and using them means that everything needs to be COW.
We don't have COWed stacks, they are all single chunk already.
> A return continuation is a *potential* continuation.
Ok, the return of the return continuation recycling. But it's likely a
bit more complicated. Creating a Continuation somewhere down a call
chain has to mark all return continuations up as non-recyclable. And as
the Continuation PMC can get passed anywhere, it looks to me that just
the presence of one Continuation PMC invalidates all return
continuations.
The proposed scheme with big register chunks and a watermark at the
frame pointer of the "highest" continuation looks more sane.
> ..., and it will completely invalidate all the
> existing JIT code.
Only i386, which is the only one that does not already a CPU register
indirect addressing of Parrot registers. i386 is currently being fixed.
When that's done, all JIT platforms basically need *one* additional
instruction in one place, e.g. for PPC:
r16 = BP_OFFS(r13) # get base bointer from interpreter
> ..., but I'm kinda sick at the moment,
Get well soon.
leo
Dan Sugalski
>Dan Sugalski <d...@sidhe.org> wrote:
>
>> The first is the CPS style chews through continuation objects at a
>> massive rate, and using them means that everything needs to be COW.
>
>We don't have COWed stacks, they are all single chunk already.
Yeah, I know, but I've been considering allowing stack back-peeking
and modifying. Sorry, wasn't clear.
> > A return continuation is a *potential* continuation.
>
>Ok, the return of the return continuation recycling. But it's likely a
>bit more complicated. Creating a Continuation somewhere down a call
>chain has to mark all return continuations up as non-recyclable.
Right. Any time an actual continuation is created we need to walk
back up the call chain and mark all the pending return continuations
as non-recyclable.
> And as
>the Continuation PMC can get passed anywhere, it looks to me that just
>the presence of one Continuation PMC invalidates all return
>continuations.
No, it doesn't, luckily. The worst case here is that invoking a
continuation will leave some return continuations to be cleaned up by
a DOD sweep.
>The proposed scheme with big register chunks and a watermark at the
>frame pointer of the "highest" continuation looks more sane.
Yeah, that's what I thought back when we started parrot--that's the
original design of the register stacks. At this point I *don't* think
it's the right thing, for a few reasons.
*) It was annoyingly error prone
*) If we switch to the scheme we've been arguing over the number of
register frame pushes will approach 0, so there's little point in the
complexity.
If we're not saving much on the register stacks (and with the switch
in calls we won't be, which means we can drop the pushtop/poptop
stuff on calls) it's easier to go with a one-frame-per-chunk setup.
> > ..., and it will completely invalidate all the
>> existing JIT code.
>
>Only i386, which is the only one that does not already a CPU register
>indirect addressing of Parrot registers. i386 is currently being fixed.
>When that's done, all JIT platforms basically need *one* additional
>instruction in one place, e.g. for PPC:
>
> r16 = BP_OFFS(r13) # get base bointer from interpreter
What, we have two registers dedicated? One for the interpreter
pointer and one for the start of registers? I didn't realize that. If
so, then nevermind.
> > ..., but I'm kinda sick at the moment,
>
>Get well soon.
Let's hope that's after we get this hashed out. :)
Leopold Toetsch
> At 9:16 AM +0200 10/20/04, Leopold Toetsch wrote:
> Right. Any time an actual continuation is created we need to walk back
> up the call chain and mark all the pending return continuations as
> non-recyclable.
Ok.
> If we're not saving much on the register stacks (and with the switch in
> calls we won't be, which means we can drop the pushtop/poptop stuff on
> calls) it's easier to go with a one-frame-per-chunk setup.
Yep, it's easier. Let's start with that.
>> r16 = BP_OFFS(r13) # get base bointer from interpreter
>
> What, we have two registers dedicated? One for the interpreter pointer
> and one for the start of registers? I didn't realize that. If so, then
> nevermind.
Well, not quite ;) But it's absolutely no problem for e.g. PPC. It got
plenty of callee-saved registers. For i386 the frame-pointer is
currently being created in %ebx, interpreter access, which is basically
rare, needs:
mov -16(%ebp), %eax # get interpreter
And that's needed too for getting the new frame pointer
mov BP_OFFS(%eax), %ebx # only for reload after invoke
Accessing e.g. a non-mapped I2 is already:
mov 8(%ebx), %eax
which isn't worse then the old absolute address thingy.
leo
Dan Sugalski
>Dan Sugalski wrote:
>>At 9:16 AM +0200 10/20/04, Leopold Toetsch wrote:
>
>>Right. Any time an actual continuation is created we need to walk
>>back up the call chain and mark all the pending return
>>continuations as non-recyclable.
>
>Ok.
>
>>If we're not saving much on the register stacks (and with the
>>switch in calls we won't be, which means we can drop the
>>pushtop/poptop stuff on calls) it's easier to go with a
>>one-frame-per-chunk setup.
>
>Yep, it's easier. Let's start with that.
Good. Today I can manage eaiser. I'm not sure past that. :)
>>> r16 = BP_OFFS(r13) # get base bointer from interpreter
>>
>>What, we have two registers dedicated? One for the interpreter
>>pointer and one for the start of registers? I didn't realize that.
>>If so, then nevermind.
>
>Well, not quite ;) But it's absolutely no problem for e.g. PPC. It
>got plenty of callee-saved registers. For i386 the frame-pointer is
>currently being created in %ebx, interpreter access, which is
>basically rare, needs:
>
> mov -16(%ebp), %eax # get interpreter
>
>And that's needed too for getting the new frame pointer
>
> mov BP_OFFS(%eax), %ebx # only for reload after invoke
>
>Accessing e.g. a non-mapped I2 is already:
>
> mov 8(%ebx), %eax
>
>which isn't worse then the old absolute address thingy.
'Kay, now I'm confused. I thought we were talking about removing the
registers from out of the interpreter structure, which'd leave us
needing two pointers, one for the interpreter struct and one for the
registers. (With no link back from the register stack top to the
interpreter) That not the case?
Leopold Toetsch
> 'Kay, now I'm confused. I thought we were talking about removing the
> registers from out of the interpreter structure, which'd leave us
> needing two pointers, one for the interpreter struct and one for the
> registers.
Ok, short summary of future layout of JIT regs:
item PPC i386
------------------------------------------------
interpreter r13 -16(%ebp)
frame pointer r16 %ebx
Register addressing is done relative to the frame pointer, which will be
in a register. The interpreter isn't used that often inside integer JIT
code, so it isn't in an register in i386 but is easily reloaded into one.
Currently the frame pointer and the interpreter are the same.
Code that branches (invoke) will reload the frame pointer from the
interpreter.
leo
Dan Sugalski
Ah, OK. That make sense. (Which is probably a clue that it's time to
go lie down, but that's a separate issue)
In that case I won't worry about it, and I think I know what I'd like
to do with the interpreter, the register frame, and the register
backing stack. I'll muddle it about some and see where it goes.
Jeff Clites
> Dan Sugalski wrote:
>> 'Kay, now I'm confused. I thought we were talking about removing the
>> registers from out of the interpreter structure, which'd leave us
>> needing two pointers, one for the interpreter struct and one for the
>> registers.
>
> Ok, short summary of future layout of JIT regs:
>
> item PPC i386
> ------------------------------------------------
> interpreter r13 -16(%ebp)
> frame pointer r16 %ebx
>
> Register addressing is done relative to the frame pointer, which will
> be in a register. The interpreter isn't used that often inside integer
> JIT code, so it isn't in an register in i386 but is easily reloaded
> into one.
>
> Currently the frame pointer and the interpreter are the same.
Just to clarify: This is the approach wherein each frame gets a fresh
set of registers, and function call and return (or continuation
invocation) copy the relevant registers between the register sets? And
this isn't quite the scheme from the "towards a new call scheme"
thread, in which we'd be duplicating the interpreter context for each
frame, right? (And the latter was what you did in "Proof of concept -
hack_42 (was: the whole and everything)", right?)
Just trying to sort out all of the ideas.
JEff
Leopold Toetsch
> Just to clarify: This is the approach wherein each frame gets a fresh
> set of registers, and function call and return (or continuation
> invocation) copy the relevant registers between the register sets?
Yes. Function arguments and return values get copied as well as the
interpreter context. Its basically the same as was in, until around
0.0.3, except that we had 4 register frame pointers and 4 stacks. I
really want to have just one register frame pointer now. It avoids 3/4th
of the stack push/pop overhead and mappes nicely to run loops, including
JIT.
> ... And
> this isn't quite the scheme from the "towards a new call scheme"
> thread, in which we'd be duplicating the interpreter context for each
> frame, right? (And the latter was what you did in "Proof of concept -
> hack_42 (was: the whole and everything)", right?)
Yep. That scheme was a bit too error prone during implementation
attempts and it didn't perform well for recursive functions. Changing
the interpreter pointer, or having an indirection fot the access to the
interpreter, isn't really simple.
> JEff
leo
Leopold Toetsch
> In that case I won't worry about it, and I think I know what I'd like to
> do with the interpreter, the register frame, and the register backing
> stack. I'll muddle it about some and see where it goes.
JIT/i386 is up to date now that is: it doesn't do any absolute register
addressing anymore.
So what next:
* deprecate the usage of allmost all register stack push and pops?
I think we don't need them anymore. Register preservering is done as
part of the call sequence. The only ops needed are IMHO:
saveall/restoreall to support stack calling conventions. The question
is: is saveall supposed to copy registers or just prepare a fresh set of
registers.
* remove the {push,pop}{top,bottom}{i,s,p,n} opcodes from tests
* implement the new indirect register frame
Comments welcome,
leo
Leopold Toetsch
the current and a possible future register layout (-DINDIRECT). You can
time the normal function calling core with the mops benchmark by
compiling it with -DMOPS.
Have fun,
leo
Dan Sugalski
I think the next steps are:
1) Implement the new indirect register frame
2) Note in the calling conventions that saving and restoring the top
register set isn't required
3) Get IMCC to skip the save/restore set
and we see where we go from there. I'm not inclined, yet, to drop the
register stacks and the push/pop ops as there are certainly times
when it's useful, being a quick way to spill and unspill a set of
registers for a basic block.
Jeff Clites
> Dan Sugalski wrote:
>> In that case I won't worry about it, and I think I know what I'd like
>> to do with the interpreter, the register frame, and the register
>> backing stack. I'll muddle it about some and see where it goes.
>
> JIT/i386 is up to date now that is: it doesn't do any absolute
> register addressing anymore.
>
> So what next:
>
> * deprecate the usage of allmost all register stack push and pops?
>
> I think we don't need them anymore. Register preservering is done as
> part of the call sequence.
Are we still planning to move the current return continuation and
current sub, out of the registers and into their own spots in the
interpreter context (in order to avoid the PMC creation overhead in the
common case, etc.)? (Or, have we already done this?)
JEff
Leopold Toetsch
> Are we still planning to move the current return continuation and
> current sub, out of the registers and into their own spots in the
> interpreter context
The current sub, continuation, and object already have a storage in the
context structure and are accessible via the C<interpinfo> opcode.
Invocing a subroutine copies P0..P2 into the context already.
What's missing is the distinction between:
invoke Px # maybe return
return # use current continuation in context
> ... (in order to avoid the PMC creation overhead in the
> common case, etc.)?
The main reason for the storage in the context isn't that. We need it
for the backtrace generation. Currently P1 could be swapped out into the
register frame, so that's unknown, where the continuation (and the
caller) is.
That said optimization isn't really possible with the calling scheme,
because we need a storage for the context. This has to be a managed
object so that we are able to cleanup dead code during GC.
> JEff
leo
Leopold Toetsch
> At 5:34 PM +0200 10/21/04, Leopold Toetsch wrote:
>> The question
>> is: is saveall supposed to copy registers or just prepare a fresh set
>> of registers.
What about that?
> I think the next steps are:
>
> 1) Implement the new indirect register frame
> 2) Note in the calling conventions that saving and restoring the top
> register set isn't required
> 3) Get IMCC to skip the save/restore set
Ok.
> and we see where we go from there. I'm not inclined, yet, to drop the
> register stacks and the push/pop ops as there are certainly times when
> it's useful, being a quick way to spill and unspill a set of registers
> for a basic block.
Not really IMHO. It doesn't get you more addressable registers, i.e. you
can always access ony e.g. 2 x 16 at once. With spilling into an array
the range of "registers" is extended.
If a basic block got such a behavior that it needs more registers
locally then allocation of these registers isn't a problem. And in
praxis you don't have that anyway, because a basic block is *branchless*
per definition.
leo
Dan Sugalski
>Dan Sugalski wrote:
>>At 5:34 PM +0200 10/21/04, Leopold Toetsch wrote:
>
>>>The question is: is saveall supposed to copy registers or just
>>>prepare a fresh set of registers.
>
>What about that?
Missed that, sorry. A copy.
>>and we see where we go from there. I'm not inclined, yet, to drop
>>the register stacks and the push/pop ops as there are certainly
>>times when it's useful, being a quick way to spill and unspill a
>>set of registers for a basic block.
>
>Not really IMHO. It doesn't get you more addressable registers, i.e.
>you can always access ony e.g. 2 x 16 at once. With spilling into an
>array the range of "registers" is extended.
>If a basic block got such a behavior that it needs more registers
>locally then allocation of these registers isn't a problem. And in
>praxis you don't have that anyway, because a basic block is
>*branchless* per definition.
I realize that a basic block's branchless, Leo. What I was talking
about was the *entry* (or exit) to a basic block. If you have a
looping block construct:
FOO
|
V
BAR<-+
+---+
|
V
BAZ
where the BAR basic block either is entered from the beginning or
looped into, the register coloring code is in a position to do some
save optimizations. It *could* spill the used registers, or it could
just push the whole set onto the register stack and start fresh,
popping off the old set when the code's done.
Leopold Toetsch
> ... It *could* spill the used registers, or it could
> just push the whole set onto the register stack and start fresh,
> popping off the old set when the code's done.
Or probably much simpler: given a fairly big linear register frame, just
advance the base pointer by a small increment, which makes the first x
registers unusable, existing regs are at (n-x) and fresh regs are at
(32-x). This is my preferred idea, when we really need extending the
register range.
Anyway, both schemes are rather complicated when it comes to register
coloring. FWIW, when AMD designed the x86-64 chip, they found that
(IIRC) 99.8% of the tested C programs fits into 16 regs (which aren't
all allocatable). We should therefore have no problem with 32, if
register allocation is fixed eventually.
leo