This post originated from an RSS feed registered with Agile Buzz
by James Robertson.
Original Post: callee or caller saves
Feed Title: Michael Lucas-Smith
Feed URL: http://www.michaellucassmith.com/site.atom
Feed Description: Smalltalk and my misinterpretations of life
One last thought (hopefully) before I stop on this register nonsense for the day :)
Callee or Caller saves registers. What is this all about? Well, when you call off to another method you have no guarantee that the registers will be the way you left them when you get control again.
Regardless of continuations, this is still the case. Any information you want to survive across calls has to be stored 'somewhere else'. Typically, this somewhere else has been the stack because it is a very convenient place to store things.
The usual technique is caller saves, before you call another method you save what you need in to the stack and then when you get back you can restore your values again.
The flip side of this is callee saves. At the start of your method you store all the registers you're going to modify in to the stack and before you leave you release them.
Both have their advantages. For instance, callee saves means only the volatile registers will be saved. But it means we have to go through that method to 'unwind' (not that this is a huge problem), otherwise the registers will not be restored.
Caller saves means you don't have to 'unwind' through all the methods you've called, but you may be saving more than you need too. Not that this is a problem either, as there is a push-all and pop-all instruction which is relatively fast.
So which should be used in a CPS like system? Well, instead of approaching them from their merits, we can look at the previous results found. All the arguments to the method that were used were long lived - they stayed in the method's context until the last statement. Therefore we know we want to save them until the end.
If we push our method arguments on to the stack at the top of our method, we free up more registers for calling (in fact, all five of them are now available to us). We also know from statement analysis of any statement that has a variable that is medium-long lived so at the beginning of the method we can allocate room for them as well.
This is sort of a 'hybrid' of callee and caller. Because we're continuations don't really care about 'returning' and the variable optimiser has already reduced the amount of medium-long lived variables to a minimum. So effectively, the majority of our program is floatsum, it has no lasting affects.
We don't even need to 'pop' those things we've placed on the stack, because when we jump to our next continuation the stack-pointer will move back to where it came from and all is forgotten. With some smart ordering we can even have methods that require stack-passing-style to have all their information already on the stack in the right order, with only a few slots to be pocked from register return results.
This ends up giving us very effecient methods using our five free registers to their best ability, giving the callee the ability to store what it needs. AND! giving the callee the free assumption that it can do whatever it wants with any general purpose register it wants! This is the freedom we really need to make continuations work.
Storing a continuation thus becomes an act of remembering the eight registers (adjusting the stack pointer) and moving relevant stack-allocated objects to a heap. That's it. That continuation can be called upon at any time by pop-all and jmping.
This is a tremendous advantage, especially when you consider that BlockClosures are a Continuation.
Previous Topic
