Lexicals, continuations, and register allocation
Matt Fowles
On Tue, 23 Nov 2004 21:15:33 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
> Below inline/attached are some thoughts WRT the subject.
>
> leo
>
>
> Lexicals, continuations, and register allocation
>
> 1) Recent discussions have shown that we obviously can't handle all
> the side effects of continuations correctly. Reusing preserved
> (non-volatile) registers after a call isn't possible any more, due to
> loops in the CFG a continuation might create.
>
> There are two proposed, accepted but undesirable work arounds:
> a) don't reuse registers - drawback spilling
> b) refetch all from lexicals - drawback execution time
Have we seen that this actually destroys us? Meaning, if we add the
extra CFG arcs, do we start spilling like mad? If not, this is much
ado about nothing.
I proposed an alternate scheme that has minimal impact on existing
code. Right now we guarantee that return continuations restore all
non-volatile registers. If we extend that guarantee to all
continuations, everything would just work with the caveat that changes
to value registers (as opposed to reference registers) are lost. This
is not a real loss though because refetch all lexicals already
requires backing store for I and N registers.
I suspect that Dan will be unhappy with both my answer and yours
though, so we should probably hear his solution, which I think may be
to add the extra CFG arcs.
Matt
--
"Computer Science is merely the post-Turing Decline of Formal Systems Theory."
-???
Leopold Toetsch
> Have we seen that this actually destroys us? Meaning, if we add the
> extra CFG arcs, do we start spilling like mad? If not, this is much
> ado about nothing.
Please first have a look at Dan's recent posting about Evil Sub. Then
estimate, how many subs may be called in 14000 basic blocks. For 100
subs only you get ~10000 more edges ...
Second, having this arcs means just that in that range i.e. from the
first subroutine to the last, you can't reuse a register around a call.
Question: how many from ~23000 registers might be effected. Please note
the currently rather low spill count despite the huge register usage.
> I proposed an alternate scheme that has minimal impact on existing
> code.
C source code or bytecode? The latter isn't effected at all in my scheme
if you just swap the two register ranges (I don't care currently). The
impact on C source changes would be low, even JIT works with just
s/ctx\.bp/ctp/g
> ... Right now we guarantee that return continuations restore all
> non-volatile registers. If we extend that guarantee to all
> continuations, everything would just work with the caveat that changes
> to value registers (as opposed to reference registers) are lost. This
> is not a real loss though because refetch all lexicals already
> requires backing store for I and N registers.
You are missing the point. It's not a question of preserving, it's
register re-using. And forcing all I and N registers into lexical PMCs
totally defeats the optimized usage of these registers.
> Matt
leo
Matt Fowles
On Tue, 23 Nov 2004 23:26:39 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
> Matt Fowles wrote:
>
> > Have we seen that this actually destroys us? Meaning, if we add the
> > extra CFG arcs, do we start spilling like mad? If not, this is much
> > ado about nothing.
>
> Please first have a look at Dan's recent posting about Evil Sub. Then
> estimate, how many subs may be called in 14000 basic blocks. For 100
> subs only you get ~10000 more edges ...
>
> Second, having this arcs means just that in that range i.e. from the
> first subroutine to the last, you can't reuse a register around a call.
> Question: how many from ~23000 registers might be effected. Please note
> the currently rather low spill count despite the huge register usage.
Won't your approach put every one of those things in its own register?
> > I proposed an alternate scheme that has minimal impact on existing
> > code.
>
> C source code or bytecode? The latter isn't effected at all in my scheme
> if you just swap the two register ranges (I don't care currently). The
> impact on C source changes would be low, even JIT works with just
> s/ctx\.bp/ctp/g
I meant it at the C level. This feels to me like a fairly major
internal change. Thus, I am a little surprised that the impact would
be as low as you claim. But you are definitely the authority on that.
> > ... Right now we guarantee that return continuations restore all
> > non-volatile registers. If we extend that guarantee to all
> > continuations, everything would just work with the caveat that changes
> > to value registers (as opposed to reference registers) are lost. This
> > is not a real loss though because refetch all lexicals already
> > requires backing store for I and N registers.
>
> You are missing the point. It's not a question of preserving, it's
> register re-using. And forcing all I and N registers into lexical PMCs
> totally defeats the optimized usage of these registers.
I don't think that I am. I understand that the question is one of
reuse. However, if a continuation restores registers to the data they
had when the continuation was taken, then all of the registers will
contain the things that exactly as the original allocator expects
them. Code later on can overwrite those registers safe in the
knowledge that any continuation which would jump back to the original
point would also set up its own registers. Thus, there is no need for
adding backward branches to the CFG. Also, you do not force all I,N
registers into lexical PMCs. You only force those ones that need
changes across re-invocations of a continuation to persistent to
persist. I would expect that such usages are extremely infrequent and
would not occur in finely tuned code. The majority of uses for I,N
registers will be optimizations on number crunching, such algorithms
will likely not use continuations. In fact, such algorithms are
usually not stateful at all, and thus would be completely unaffected.
Leopold Toetsch
> Won't your approach put every one of those things in its own register?
I've clearly stated that lexicals aka non-volatiles have distinct
registers.
> ... However, if a continuation restores registers to the data they
> had when the continuation was taken, then all of the registers will
> contain the things that exactly as the original allocator expects
> them.
Yes. We had that scheme until the indirect register frame addressing.
It was:
savetop
invokecc
restoretop
It was too slow - remember a factor of 5!
leo
Matt Fowles
On Wed, 24 Nov 2004 04:55:24 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
> Matt Fowles <uber...@gmail.com> wrote:
>
> > Won't your approach put every one of those things in its own register?
>
> I've clearly stated that lexicals aka non-volatiles have distinct
> registers.
Thus for these large subs, won't this be a large overhead?
> > ... However, if a continuation restores registers to the data they
> > had when the continuation was taken, then all of the registers will
> > contain the things that exactly as the original allocator expects
> > them.
>
> Yes. We had that scheme until the indirect register frame addressing.
> It was:
>
> savetop
> invokecc
> restoretop
>
> It was too slow - remember a factor of 5!
Yes, but that is because we COPIED the data for every invocation.
With what I am proposing we would only need to copy the data when
invoking a full continuation (so that the full continuation can be
invoked again later without disturbing its registers). Invoking
return continuations would be exactly the same as it is now. Thus you
only pay the cost if you are trying to do funny things with
continuations.
Bill Coffman
> Matt Fowles wrote:
>
> > Have we seen that this actually destroys us? Meaning, if we add the
> > extra CFG arcs, do we start spilling like mad? If not, this is much
> > ado about nothing.
>
> Please first have a look at Dan's recent posting about Evil Sub. Then
> estimate, how many subs may be called in 14000 basic blocks. For 100
> subs only you get ~10000 more edges ...
>
> Second, having this arcs means just that in that range i.e. from the
> first subroutine to the last, you can't reuse a register around a call.
> Question: how many from ~23000 registers might be effected. Please note
> the currently rather low spill count despite the huge register usage.
Keep in mind that you don't actually have to add all those CFG edges.
You already know precisely the effects of adding them. All
non-volatile symbols (those crossing subs that might make continuation
invocations) are garanteed to interfere. This is garanteed to be a
clique in the interference graph. No need to actually add the CFG
edges to know how the interference graph is effected.
This brings up the possibility of non-volatile symbols that cross subs
that are garanteed *not* to invoke continuations. Those would not
necessarily be part of the clique, but would be non-volatile (forced
into the upper half of registers). The register allocator could
handle that the way it currently does (the one I'm currently working
on, that is).
It bothers me that this discussion is not including the concept of
subs that don't call/invoke continuations. Remember the previous
posts about adding a label, or setting a pragma? Also, if that sub is
defined in the same imc source code, we can analyze it to see if there
is a continuation there or not.
Another interesting thing about this problem is that these new CFG
edges are rarely, or at least with low probability, ever travelled.
That can also be used to our advantage I think.
~Bill
Bill Coffman
> Matt Fowles <uber...@gmail.com> wrote:
> > ... However, if a continuation restores registers to the data they
> > had when the continuation was taken, then all of the registers will
> > contain the things that exactly as the original allocator expects
> > them.
>
> Yes. We had that scheme until the indirect register frame addressing.
> It was:
>
> savetop
> invokecc
> restoretop
>
> It was too slow - remember a factor of 5!
I think the problem was that you were saving 32*4 = 128 registers!
Even if you only used 5 or 10. Thats a factor of ten right there, I
bet. The right way to have done this was
savetop(n1,n2,n3,n4)
invokecc
restoretop(n1,n2,n3,n4)
Where n1..n4 are the number of registers to be saved, or better yet,
the length of the register array to save. That way, only the critical
registers would be saved, and that could be minimized by the
allocator. Then your memcpy's would have been optimized, but saving
600 bytes of unused territory was never going to work.
Bill
> leo
>
Leopold Toetsch
> On Tue, 23 Nov 2004 23:26:39 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
> Keep in mind that you don't actually have to add all those CFG edges.
> You already know precisely the effects of adding them. All
> non-volatile symbols (those crossing subs that might make continuation
> invocations) are garanteed to interfere. This is garanteed to be a
> clique in the interference graph. No need to actually add the CFG
> edges to know how the interference graph is effected.
Possible, but just another special cased exception. With that you get
two possible interferences of different kinds, with additional coding
overhead ...
> It bothers me that this discussion is not including the concept of
> subs that don't call/invoke continuations. Remember the previous
> posts about adding a label, or setting a pragma?
Sure. But I've no confirmation of a compiler writer that its possible.
Annotating PIR can only work for nested closures. If libraries are
involved you are out of luck.
And we have such code already in library/Streams/Sub.imc.
> ... Also, if that sub is
> defined in the same imc source code, we can analyze it to see if there
> is a continuation there or not.
And if not - see above.
> Another interesting thing about this problem is that these new CFG
> edges are rarely, or at least with low probability, ever travelled.
We just don't know it, rare or not doesn't matter.
> ~Bill
leo
Leopold Toetsch
> Leo~
> On Wed, 24 Nov 2004 04:55:24 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
>> I've clearly stated that lexicals aka non-volatiles have distinct
>> registers.
> Thus for these large subs, won't this be a large overhead?
Why? It's actually less overhead. In the normal case these lexicals are
created/stored in the scratchpad PMC array. So they have a storage,
equally large anyway. Accessing these lexicals is an array lookup at
best. Please look again at the picture I've drawn.
This approach saves the scratchpad PMC (or better the array part of it)
and the distinct non-volatile area, what we've now. It's cheaper.
>> It was too slow - remember a factor of 5!
> Yes, but that is because we COPIED the data for every invocation.
> With what I am proposing we would only need to copy the data when
> invoking a full continuation
That doesn't work. If you create a real continuation all continuations
up the call chain have to be real continuations. And copying or not
imposes different semantics on register usage.
leo
Miroslav Silovic
> Sure. But I've no confirmation of a compiler writer that its possible.
> Annotating PIR can only work for nested closures. If libraries are
> involved you are out of luck.
>
> And we have such code already in library/Streams/Sub.imc.
I've been thinking of what could be implemented using continuations.
Some possible ideas:
- multiple returns from regexp matches
- lazy lists. In particular gather/take
- junctions
- coroutines
- resumable exceptions
Thing is, we can't know what the Real World perl6 code is going to look
like. If it turns out that continuations are The Way to implement both
junctions and gather/take construct, 'out of luck' is a good description
of the ensuing fun and merryment. Basically, any PMC can be silently
swapped with a junction, possibly making anything that uses it backtrack
(what are the junctions supposed to be implemented as, anyway?) and I
can imagine that lots of production perl6 code will have gather/takes
all over the place - they look like an utterly nice way to construct a list.
My point is that continuations are rare because mainstream languages
(with a single exception) don't support them.
BTW, I wonder if there are any research papers on the topic of register
allocation in presence of continuations. I just looked at Citeseer, but
a quick cursory search didn't come up with anything useful.
Miro
Nicholas Clark
> Bill Coffman wrote:
> >Another interesting thing about this problem is that these new CFG
> >edges are rarely, or at least with low probability, ever travelled.
>
> We just don't know it, rare or not doesn't matter.
I'm probably going to get shot for suggesting this, but if each interpreter
has a count of the number of full continuations invoked (ie non-return
continuations), then I think that we can know when we *haven't*. Which (I'm
guessing - need a real finished parrot to know) won't be that often. So I'm
thinking
* counter incremented monotonically for every non-return continuation
invocation
* Store the value of this counter as part of sub entry
* Check the value against the stored counter on sub return
* If they differ, branch to slow case fixup code. (Well or branch round it
if they are the same)
Hmmm. But we still have to save all values out from registers before a call.
Pah. May not be a great win.
Nicholas Clark
Ken Fox
> +-----+----------------------+
> | ctp | interpreter state |
> +-----+----------------------+
> |
> +------------+
> |
> +------+-----+-----------+----------------------+
> | prev | ctx | lexicals | volatiles |
> +------+-----+-----------+----------------------+
> | p a r r o t r e g i s t e r s |
A very strong architecture for sure.
> + no lexical fetch overhead
That alone is worth the price of admission. No register allocator
needed because the HLL only needs volatiles for anonymous temporaries
which are easily allocated during expression parsing.
I would make a couple changes:
+-----+----------------------+
| ctp | interpreter state |
+-----+----------------------+
|
+--------------+------+-----+-----------+----------------------+
| caller's out | prev | ctx | lexicals | volatiles |
+--------------+------+-----+-----------+----------------------+
Merge with the variable sized stack frame proposal and expose
prev+ctx as registers. As long as an architecture change is on the
table, might as well make it a doozy. (Caller's out may need to be
padded if caller did not pass the right number of args.)
Sorry for the de-lurk. I'll now return to hacking on my storage to
storage VM which looks amazingly similar to Leo's VM. ;)
- Ken
Nicholas Clark
> As long as an architecture change is on the
> table, might as well make it a doozy.
Quite a lot of us would just like parrot COMPLETE and CORRECT before
starting to put a lot of effort into how fast it is.
PLEASE can we get parrot functionally complete, THEN start refactoring it
to go faster. Until such time as we have complete, functional high level
language running on it, with real world programs (rather than benchmarks and
torture tests) optimisations are likely to be premature, as we don't have
complete or realistic data of what our true speed problems are.
ONLY when we have a real language complete and running (and yes, 100% of
python running seems to be the easiest one here) do I feel that we'll
actually be justified in spending time and effort undoing things that
work (albeit slowly) and redoing them. Currently we keep liking to generate
a lot of heat (and little light) redoing things that are currently too slow,
which I have NO DOUBT that we're going to want to re-redo later in the light
of real data.
Nicholas Clark
Leopold Toetsch
> Leopold Toetsch wrote:
>> +-----+----------------------+
>> | ctp | interpreter state |
>> +-----+----------------------+
>> |
>> +------------+
>> |
>> +------+-----+-----------+----------------------+
>> | prev | ctx | lexicals | volatiles |
>> +------+-----+-----------+----------------------+
>> | p a r r o t r e g i s t e r s |
> A very strong architecture for sure.
> > + no lexical fetch overhead
> That alone is worth the price of admission. No register allocator
> needed because the HLL only needs volatiles for anonymous temporaries
> which are easily allocated during expression parsing.
Yep, I mentioned that.
> I would make a couple changes:
[ ... ]
I'm not gonna touch calling conventions. Actually by swapping the two
register ranges above it's fully compatible.
> +-----+----------------------+
> | ctp | interpreter state |
> +-----+----------------------+
> |
> +--------------+------+-----+-----------+----------------------+
> | caller's out | prev | ctx | lexicals | volatiles |
> +--------------+------+-----+-----------+----------------------+
> Merge with the variable sized stack frame proposal and expose
> prev+ctx as registers.
prev is the current (return) continuation, which is unvisible except for
the returncc opcode. Exposing it means a visible full continuation with
all the drawbacks. ctx has some stack top pointers e.g. for the control
stack and other stuff.
So C<push ctx_ctrl, eh> would push an exception handler. Other members
are flags e.g. warnings on/off. This would be very similar to a hardware
CPUs control registers: C<bor ctx_warn, .WARNING_UNDEF>.
> Sorry for the de-lurk.
I'd be glad to have you here.
> - Ken
leo
Leopold Toetsch
> I'm probably going to get shot for suggesting this, but if each interpreter
> has a count of the number of full continuations invoked (ie non-return
> continuations), then I think that we can know when we *haven't*.
Nobody gets shot - and - interesting idea, but
> * If they differ, branch to slow case fixup code.
Smells like duplicating the whole sub, which would make Evil Sub just
more Evil.
> Hmmm. But we still have to save all values out from registers before a call.
> Pah. May not be a great win.
Yep.
> Nicholas Clark
leo
Matt Fowles
On Wed, 24 Nov 2004 16:42:31 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
> And as a side effect it will make Dan's evils subs compile, because
> long-lived lexicals already have their storage aka register. Only temps
> need a register allocated.
What happens to temps that need to cross function calls in your scheme?
Leopold Toetsch
> On Wed, Nov 24, 2004 at 09:45:27AM -0500, Ken Fox wrote:
>> As long as an architecture change is on the
>> table, might as well make it a doozy.
> Quite a lot of us would just like parrot COMPLETE and CORRECT before
> starting to put a lot of effort into how fast it is.
Yes. Obviously my posting proposes a solution for the current incorrect
behavior of continuations in combination with register re-allocation.
And as a side effect it will make Dan's evils subs compile, because
long-lived lexicals already have their storage aka register. Only temps
need a register allocated.
> PLEASE can we get parrot functionally complete, THEN start refactoring it
> to go faster. Until such time as we have complete, functional high level
> language running on it, with real world programs (rather than benchmarks and
> torture tests) optimisations are likely to be premature, as we don't have
> complete or realistic data of what our true speed problems are.
That's of course right.
> Nicholas Clark
leo
Leopold Toetsch
> Leo~
> On Wed, 24 Nov 2004 16:42:31 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
>> And as a side effect it will make Dan's evils subs compile, because
>> long-lived lexicals already have their storage aka register. Only temps
>> need a register allocated.
> What happens to temps that need to cross function calls in your scheme?
These would go along with the lexicals in the non-volatile area. But
such temps are rare (AFAIK). You need a HLL construct like:
a = b + c + foo()
giving something like this:
a = new Undef
$P0 = new Undef
$P0 = b + c
$P1 = foo()
a = $P0 + $P1
The temp $P0 has to persist over the call and needs a permanent store
too.
> Matt
leo
Matt Fowles
On Wed, 24 Nov 2004 17:25:05 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
> Matt Fowles <uber...@gmail.com> wrote:
> > Leo~
>
> > On Wed, 24 Nov 2004 16:42:31 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
> >> And as a side effect it will make Dan's evils subs compile, because
> >> long-lived lexicals already have their storage aka register. Only temps
> >> need a register allocated.
>
> > What happens to temps that need to cross function calls in your scheme?
>
> These would go along with the lexicals in the non-volatile area. But
> such temps are rare (AFAIK). You need a HLL construct like:
>
> a = b + c + foo()
I am not sure that they are as rare as you think.
Bill Coffman
> Bill Coffman wrote:
> > On Tue, 23 Nov 2004 23:26:39 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
>
> > Keep in mind that you don't actually have to add all those CFG edges.
> > You already know precisely the effects of adding them. All
> > non-volatile symbols (those crossing subs that might make continuation
> > invocations) are garanteed to interfere. This is garanteed to be a
> > clique in the interference graph. No need to actually add the CFG
> > edges to know how the interference graph is effected.
>
> Possible, but just another special cased exception. With that you get
> two possible interferences of different kinds, with additional coding
> overhead ...
Instead of n*(n-1) arcs for n continuation passing subs (both to and
from), we can simply add a pseudo instruction. All n sub calls have
arcs to that pseudo-instruction, and out from it, to the instruction
after the sub call. This means only 2*n arcs (both to and from).
Each continuation calling sub becomes a kind of wormhole. Any symbol
crossing it, also crosses the pseudo-instruction. What makes it a
little complicated is how do these "ubiquetous" symbols interact with
the non-ubuiquitous? Those arcs are needed for this.
> I've no confirmation of a compiler writer that its possible.
> Annotating PIR can only work for nested closures. If libraries are
> involved you are out of luck.
It was Larry Wall who suggested the pragma in the long thread,
"Continuations, basic blocks, loops and register allocation ".
Although his message is somewhat genaral, he indicates a prefernce for
pragmas to turn off certain features that slow things down for
correctness. [gmail works great for finding stuff like that]
Bill
Chromatic
> Quite a lot of us would just like parrot COMPLETE and CORRECT before
> starting to put a lot of effort into how fast it is.
I'd settle for it compiling (#32514). If not for the broken build, I'd
have poked at three or four small TODO items and bugs in the past couple
of weeks.
An appropriate hierarchy of c-words is:
compiles -> correct -> complete -> competitive
First, Parrot must build on important platforms. Then it must pass the
tests. Then it must have all of the important features for the current
release. Only then (and maybe not even then, maybe for a future
release) does it need optimization.
-- c
Leopold Toetsch
> On Wed, 24 Nov 2004 17:25:05 +0100, Leopold Toetsch <l...@toetsch.at> wrote:
>> a = b + c + foo()
> I am not sure that they are as rare as you think.
Does it matter? They are no lexicals, you can't refetch them. So they
get a distinct storage. When foo() is known to the compiler that it
doesn't capture the continuation, the register can be reused else not.
> Matt
leo
Leopold Toetsch
> On Wed, 2004-11-24 at 15:04 +0000, Nicholas Clark wrote:
>> Quite a lot of us would just like parrot COMPLETE and CORRECT before
>> starting to put a lot of effort into how fast it is.
> I'd settle for it compiling (#32514).
Well, having just a short look at the error message seems to reveal
that your "as" doesn't croak the comment for the unused macro. I'd just
remove that and try again. I can't test it.
> ... If not for the broken build, I'd
> have poked at three or four small TODO items and bugs in the past couple
> of weeks.
> An appropriate hierarchy of c-words is:
> compiles -> correct -> complete -> competitive
But anyway, yes.
> First, Parrot must build on important platforms. Then it must pass the
> tests.
First is true most of the time, except for such platform stuff. I test
on two platforms, 3 computers. Tests are currently not passing due to
obvious violations of the recent pdd03 changes.
t/op/gc_13.imc would still fail because of continuation and register
allocation, it's just using lexicals now.
> ... Then it must have all of the important features for the current
> release. Only then (and maybe not even then, maybe for a future
> release) does it need optimization.
My mail - the originator of this thread, where this optimization
philosophy discussion seems now to take place - doesn't propose an
optimization, nor does it propose that scheme for that reason.
The context layout I've shown is just a way (IMHO) to solve the
correctness problem that currently exists.
Honestly I would prefer to discuss that interpreter layout (or other
realistic proposals that solve the problem).
> -- c
leo
Leopold Toetsch
>> two possible interferences of different kinds, with additional coding
>> overhead ...
> ... What makes it a
> little complicated is how do these "ubiquetous" symbols interact with
> the non-ubuiquitous? Those arcs are needed for this.
Yes that's what I've already stated above ;)
> It was Larry Wall who suggested the pragma in the long thread,
Yes I've bookmarked it. But a pragma doesn't solve outside effects of
libraries that just capture the continuation under your hood.
And - again - refetching lexicals doesn't work for things that aren't
lexicals, but just non-volatile temps.
> Bill
leo
Dan Sugalski
>Below inline/attached are some thoughts WRT the subject.
>
>leo
>
>
>
>1) Recent discussions have shown that we obviously can't handle all
>the side effects of continuations correctly. Reusing preserved
>(non-volatile) registers after a call isn't possible any more, due to
>loops in the CFG a continuation might create.
I admit, I've been watching the discussion and I just don't
understand why there's a problem.
So far as I can tell there are two cases here:
1) A return continuation
2) A regular continuation
We've already established that a return continuation preserves the
top half of the registers (though I think that's not been clear) so
there's just no problem there -- at the point a return continuation
returns, [IPSN]16-31 will be as they were when the return
continuation was created. Which, in practice, makes the I and N
registers useless for variables like loop counters, though fine for
constants (both real and effective) So continuations, as such, don't
make any difference here. A return is a return, and if it works right
the first time it should work right all the times.
The second case, where code takes an arbitrary continuation that
returns to location X, wherever X is. I'm missing the problem there,
too. Assuming there's a way to note the destination to the register
allocator (with those points being places where all registers must be
assumed to be trash) I'm not seeing the problem either. There are
only two cases here, where the destination is marked and where it
isn't. If it's marked, the register allocator assumes things are
dirty and loads everything, which is fine. If it's unmarked, the code
has essentially shot itself and everything quietly goes to hell since
you've lied to the register allocator and you shouldn't do that.
Which is fine too. Don't Do That.
N.B. that this is an issue that only affects the PIR register
allocator -- I'm not seeing a case where this can be an issue for
anything else, including plain assembly. If I'm missing something
this would be a good time to point out the missing bits.
>There are two proposed, accepted but undesirable work arounds:
>a) don't reuse registers - drawback spilling
>b) refetch all from lexicals - drawback execution time
Before I comment on this one, I want to double-check -- you're
proposing tossing the pads and going with a variable-sized register
frame, yes?
--
Dan
--------------------------------------it's like this-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk
Matt Fowles
That makes sense to me (and in fact matches what I have been failing
to articulate for a while now), thanks for the clarification.
Leopold Toetsch
> At 9:15 PM +0100 11/23/04, Leopold Toetsch wrote:
>>Below inline/attached are some thoughts WRT the subject.
>>
>>leo
>>
>>
>>Lexicals, continuations, and register allocation
>>
>>1) Recent discussions have shown that we obviously can't handle all
>>the side effects of continuations correctly. Reusing preserved
>>(non-volatile) registers after a call isn't possible any more, due to
>>loops in the CFG a continuation might create.
> I admit, I've been watching the discussion and I just don't
> understand why there's a problem.
> So far as I can tell there are two cases here:
> 1) A return continuation
> 2) A regular continuation
> We've already established that a return continuation preserves the
> top half of the registers (though I think that's not been clear) so
> there's just no problem there --
That term "preserves" needs some more clarification. Some months ago we
used the "savetop" / "restoretop" opcodes. They made a copy of half of
the register frame and restored it on return. The caller and the
subroutine did executed in the registers inside the interpreter
structure. We decided to give up this scheme in favour of the indirect
register addressing.
Now we have a new register frame, where a subroutine is executing.
Returning from the subroutine returns to the other register frame, which
of course means that the registers are preserved, because the subroutine
executed in a freshly allocated and of course different register frame.
> ... at the point a return continuation
> returns, [IPSN]16-31 will be as they were when the return
> continuation was created. Which, in practice, makes the I and N
> registers useless for variables like loop counters, though fine for
> constants (both real and effective)
Huh? You are now back with register copying? With the additional "benefit"
that we can't use integer loop counters anymore? Sorry, I can't believe
that you are proposing such a broken usage of (return) continuations.
> N.B. that this is an issue that only affects the PIR register
> allocator
Yes. That is what we are discussing since weeks.
>>There are two proposed, accepted but undesirable work arounds:
>>a) don't reuse registers - drawback spilling
>>b) refetch all from lexicals - drawback execution time
> Before I comment on this one, I want to double-check -- you're
> proposing tossing the pads and going with a variable-sized register
> frame, yes?
Yes. The data storage of one pad nesting is one register frame. The
lexicals in the top pad are reachable directly as registers. Lexicals in
outer pads still need fetching by the fetch_lex opcode.
R0..R15 are used as now, R16 .. Rn are preserved registers and lexicals.
This scheme BTW supports also Perl6 natural types as lexicals.
leo
Dan Sugalski
>Dan Sugalski <d...@sidhe.org> wrote:
>> At 9:15 PM +0100 11/23/04, Leopold Toetsch wrote:
>>>Below inline/attached are some thoughts WRT the subject.
>>>
>>>leo
>>>
>>>
>>>Lexicals, continuations, and register allocation
>>>
>>>1) Recent discussions have shown that we obviously can't handle all
>>>the side effects of continuations correctly. Reusing preserved
>>>(non-volatile) registers after a call isn't possible any more, due to
>>>loops in the CFG a continuation might create.
>
>> I admit, I've been watching the discussion and I just don't
>> understand why there's a problem.
>
>> So far as I can tell there are two cases here:
>
>> 1) A return continuation
>
>> 2) A regular continuation
>
>> We've already established that a return continuation preserves the
>> top half of the registers (though I think that's not been clear) so
>> there's just no problem there --
>
>That term "preserves" needs some more clarification. Some months ago we
>used the "savetop" / "restoretop" opcodes. They made a copy of half of
>the register frame and restored it on return. The caller and the
>subroutine did executed in the registers inside the interpreter
>structure. We decided to give up this scheme in favour of the indirect
>register addressing.
No, we didn't. We mandated that call/return preserved the top 16
registers of all the types automatically. That's *all* we did. The
rest is implementation detail.
> > ... at the point a return continuation
>> returns, [IPSN]16-31 will be as they were when the return
>> continuation was created. Which, in practice, makes the I and N
>> registers useless for variables like loop counters, though fine for
>> constants (both real and effective)
>
>Huh? You are now back with register copying?
No. I'm still on register preserving, which is where we started.
Quoth PDD 03 (which, I'll note, you agreed with)
The return continuation PMC type, used to create return
continuations used for call/return style programming, guarantees
that registers 16-31 for all types (P, N, S, and I) will be set
such that the contents of those registers are identical to the
content of the registers when the return continuation was
I<created>.
It's pretty clear, I think.
> > N.B. that this is an issue that only affects the PIR register
>> allocator
>
>Yes. That is what we are discussing since weeks.
Just checking. The answer is "no" of course, but you knew that when
you started this discussion. Architecture changes aren't an option
we're entertaining until after we're functionally complete. *That*,
I'm quite sure, I was clear on.
Matt Fowles
Not necessarily, you only need to copy in the case where a return
continuation was promoted. Thus, you can avoid copying for the common
call/return case. Also, we could allow hints that indicate a point
below which continuations do not need to be promoted (although this is
an optimization). Also, it is not that broken. In fact it has
identical semantics to the old save/restore ones. Recall that the
restore would overwrite the I/N values with what they were at save
time.
Thomas Seiler
> Architecture changes aren't an option we're entertaining until after we're
> functionally complete.
Just would like to ask a related question:
Is a change that invalidates an existing precompiled bytecode but not
the source code of it
considered as an architecture change ?
(At one point, packfiles contained a versioning scheme to catch
changes in the ABI.
Don't know about current state, though)
tom
Dan Sugalski
>At Tue 30 Nov 6:22pm, Dan Sugalski wrote:
>> Architecture changes aren't an option we're entertaining until after we're
>> functionally complete.
>
>Just would like to ask a related question:
>Is a change that invalidates an existing precompiled bytecode but not
>the source code of it
>considered as an architecture change ?
Nope. This'll happen as ops come, go if they're fundamentally broken
and/or stupid, and get shifted around. Changes to the packfile format
and the basic PMCs'll do it too.
>(At one point, packfiles contained a versioning scheme to catch
>changes in the ABI.
> Don't know about current state, though)
It still does, pretty reliably. (Or, rather, completely reliably so
far as I can tell. Which is very nice)
We've not yet declared fully backward-compatibility for bytecode
files. That's likely not going to happen until after the first final
release.