One Foot on the Beach,
One in the Surf --
Frame Pointer for Split Stack
Didn't I say we weren't going to look at this yet?
Talking about
balancing the stack when we have just begun using it
wasn't boring enough?
I'm not going to complain if you skip ahead to getting binary output.
Oh, well.
There's a philosophy that you should allocate all the memory a function will need when you start a function, and deallocate it all when you finish.
It's not a meaningless philosophy.
And it's not really limited to the single-stack run-times, but it is the only way to keep a single stack runtime sane when parameter lists become longer and local variables increase.
I think we've seen enough of accessing variables on the parameter stack that I
can introduce the concept of a stack frame in somewhat abstract terms. After
this introduction, I'll show some actual implementations borrowed from the
split stack examples of this chapter.
Say we have a routine, routine 1 that has received two parameters, P1_1 and
P1_2. And it has two temporary values on the parameter stack, T1_1 and T1_2.
The parameter stack (pointed to by PSP) and the return stack (pointed to by
RSP) could be diagrammed as follows, using nnnn to show parameters and
temporaries, and rrrr to show return addresses from further back in the call
chain, and RA_0 to show the return address from the code that called routine
1:
nnnn
P1_1_
P1_2
T1_1
T1_2
<=
_PSP_
????
rrrr
RA_0
<=
_RSP_
????
????
????
????
And routine 1 calls another routine, routine 2, passing that routine two
parameters:
nnnn
P1_1_
P1_2
T1_1
T1_2
P2_1_
P2_2
<=
_PSP_
????
rrrr
RA_0
RA_1
<=
_RSP_
????
????
????
Now, that isn't too hard to keep track of, but what if you have a call
chain twenty calls deep? (The correct answer is that a called routine
shouldn't want to know, but that answer doesn't work for languages like Pascal
that want called routines to be able to access the caller routine's
environment.)
We could keep a frame pointer in some spare register, to show where the
parameters passed to the current routine are. The calling routine would push
the frame pointer before it makes a call. The called routine would move PSP to
the frame pointer on entry. And the stacks would look like this:
nnnn
P1_1_
P1_2
<=
_FP_
T1_1
T1_2
<=
_PSP_
????
rrrr
FA_0
RA_0
<=
_RSP_
????
????
????
And just after routine 1 calls routine 2 and routine 2 updates the frame
pointer, it looks like this:
nnnn
P1_1_
P1_2
T1_1
T1_2
P2_1_
P2_2
<=
_PSP_,_FP_
????
rrrr
FA_0
RA_0
FA_1
RA_1
<=
_RSP_
????
And routine 2, the called routine, can push temporaries on the parameter stack and reference its parameters via the frame pointer.
And if it needs, for some reason, to reference the previous frame (and knows that the caller routine pushed the frame pointer), it can go look at the previous frame pointer on the return stack.
Now, that would not be so hard on the 68000, because we have lots of
registers. We could do it like this:
* calling protocol for split stack frames
* with A6 as the parameter stack pointer
* and A4 as the frame pointer:
ROUTINE1
* ...
MOVE.L PARAMETER1,-(A6)
MOVE.L PARAMETER2,-(A6)
MOVE.L A4,(-A7)
BSR.W ROUTINE2
MOVE.L (A7)+,A4 ; pop own frame pointer
* ...
*
*
* routine entry protocol for split stack frames
* with A4 as the frame pointer
* and A6 as the parameter stack pointer:
ROUTINE2
MOVE.L A6,A4
* ...
MOVE.L 0(A4),D1 ; access the second parameter
* ...
SUB.L 4(A4),D3 ; access the first parameter
* ...
MOVE.L 4(A7),A0 ; get the caller's frame pointer
ADD.L 0(A0),D5 ; access the caller's last parameter pushed!
* ...
* routine return protocol in case of return-on-stack
LEA PARAMETER_SIZE-RETURN_SIZE(A4),A4
MOVE.L RETURN_VALUE0(A6),(A4)
...
MOVE.L RETURN_VALUEN(A6),N*4(A4)
MOVE.L A4,A6
RTS
* routine return protocol in case of return-in-register discipline:
MOVE.L A4,A6 ; clear the local frame, except for own parameters
LEA 8(A6),A6 ; drop two parameters
RTS
And we need to talk about the return protocol.
In many run-time disciplines, the return value is limited to what will fit in
one or two, or maybe three registers. In such a case, the only thing you need
to do to return, once you have the return values in your registers, is
deallocate all the stuff that you were using on stack, deallocate your
parameters, and return. Deallocate all the non-parameters is accomplished by moving the frame pointer in A4 back to the parameter stack pointer in A6.
But if you need to return something bigger than that, and the run-time supports doing so, the return protocol needs to calculate the difference and adjust A4, copy the return values into place, and then deallocate by moving the adjusted address in A4 to A6.
You have to wait to deallocate until after you copy the return values into place, of course. Otherwise, an interrupt might leave you calculating things that aren't there any more.
And the calling routine needs to restore its own frame pointer when the called routine returns.
Looks pretty reasonable, if that's what we want to do.
On the 6809, 6800 and 6801, of course we'd declare a frame pointer in the direct page, and that would require more code to maintain all that. It's an interesting exercise which I should ignore for now.
Oh, why not? 6809 code:
* calling protocol for split stack frames on 6809
* with U as the parameter stack pointer
* and direct page variable FP as the frame pointer:
ROUTINE1
* ...
LDD PARAMETER1
PSHU D
LDX PARAMETER2
PSHU X
LDX FP
PSHS X
LBSR ROUTINE2
PULS X
STX FP
* ...
*
*
* routine entry protocol for split stack frames on 6809
* with U as the parameter stack pointer
* and direct page variable FP as the frame pointer:
ROUTINE2
STU FP
* ...
LDX FP
LDD 0,X ; access the second parameter
* ...
LDY FP
SUBD 2,Y ; access the first parameter
* ...
LDX 2,S ; get the caller's frame pointer
ADDD 0,X ; access the caller's last parameter pushed!
* ...
* routine return protocol in case of return-in-register discipline:
LDU FP ; clear the local frame, except for own parameters
LEAU 4,U ; drop two parameters
RTS
* routine return protocol in case of return-on-stack
LDX FP
LEAX PARAMETER_SIZE-RETURN_SIZE,X
LDD RETURN_VALUE0,U
STD ,X
...
LDD RETURN_VALUEN,U
STD N*4,X
TFR X,U
RTS
6801:
* calling protocol for split stack frames on 6801
* with direct page variable PSP as the parameter stack pointer
* and direct page variable FP as the frame pointer:
ROUTINE1
* ...
LDD PARAMETER1
JSR PPSHD
LDX PARAMETER2
JSR PPSHX
LDX FP
PSHX
JSR ROUTINE2
PULX
STX FP
* ...
*
*
* routine entry protocol for split stack frames on 6801
* with direct page variable PSP as the parameter stack pointer
* and direct page variable FP as the frame pointer:
ROUTINE2
LDX PSP
STX FP
* ...
LDX FP
LDD 0,X ; access the second parameter
* ...
LDX FP
SUBD 2,X ; access the first parameter
* ...
TSX
LDX 2,X ; get the caller's frame pointer
ADDD 0,X ; access the caller's last parameter pushed!
* ...
* routine return protocol in case of return-in-register discipline:
LDX FP ; clear the local frame, except for own parameters
INX ; drop two parameters (might be done by subroutine).
INX
INX
INX
STX PSP
RTS
* routine return protocol in case of return-on-stack
LDD FP
ADDD #PARAMETER_SIZE-RETURN_SIZE
STD FP
LDX PSP
LDD RETURN_VALUE0,X
LDX FP
STD 0,X
...
LDX PSP
LDD RETURN_VALUEN,X
LDX FP
STD N*4,X
STX PSP
RTS
and 6800:
* calling protocol for split stack frames on 6800
* with direct page variable PSP as the parameter stack pointer
* and direct page variable FP as the frame pointer:
ROUTINE1
* ...
LDD PARAMETER1
JSR PPSHD
LDX PARAMETER2
JSR PPSHX
LDAA FP
LDAB FP+1
PSHB
PSHA
JSR ROUTINE2
PULB
PULA
STAA FP
STAB FP+1
* ...
*
*
* routine entry protocol for split stack frames on 6800
* with direct page variable PSP as the parameter stack pointer
* and direct page variable FP as the frame pointer:
ROUTINE2
LDX PSP
STX FP
* ...
LDX FP
LDAA 0,X ; access the second parameter
LDAB 1,X
* ...
LDX FP
SUBB 3,X ; access the first parameter
SBCA 2,X
* ...
TSX
LDX 2,X ; get the caller's frame pointer
ADDB 1,X ; access the caller's last parameter pushed!
ADCA 0,X
* ...
* routine return protocol in case of return-in-register discipline:
LDX FP ; clear the local frame, except for own parameters
INX ; drop two parameters (might be done by subroutine).
INX
INX
INX
STX PSP
RTS
* routine return protocol in case of return-on-stack
LDX FP
LDAB #PARAMETER_SIZE-RETURN_SIZE ; -128 <= SZ < 128!
JSR ADDBX
STX FP
LDX PSP
LDAA RETURN_VALUE0,X
LDAB RETURN_VALUE0+1,X
LDX FP
STAA 0,X
STAB 1,X
...
LDX PSP
LDAA RETURN_VALUEN,X
LDAB RETURN_VALUEN+1,X
LDX FP
STAA N*4,X
STAB N*4+1,X
STX PSP
RTS
* ...
ADDBX STX XWORK
CLRA
TSTB
BPL ADDBXP
COMA
ADDBXP ADDB XWORK+1
ADCA XWORK
STAB XWORK+1
STAA XWORK
LDX XWORK
RTS
You know, that doesn't look all that bad.
It's all untested, but it should work. Uhm, for some definition of "should" and "work".
In particular, the protocol for copying return values back up the parameter stack in the case of return values on the parameter stack won't be that simple. You can't just copy from the bottom up without overwriting something before you can get it copied in some cases. And you'll have the same problem copying from top down. Which means you'll need to schedule the copying so that locations that will be used for return values will get copied into place first.
You can schedule that by hand, but it's going to be a pain to do when it's necessary. You can also have a compiler schedule it for you, but the compiler has to chase all the dependencies down before it starts spitting out code.
All of which leaves us to appreciate the sensibility of limiting return values to what fits in a register or two -- if you're going to go to the trouble of using stack frames.
Another approach to handling return values, which I describe in the next chapter, would be to consider that the return parameters and call parameters might exist in the called routine's context at the same time, and copy the call parameters below where the return parameters will be left, which is much more sensible.I describe it there because it seems to go well with a stack frame that doesn't substantially change in size over the life of the routine. But there's no reason not to use it with this kind of stack frame.
Oh, and one more thing about getting the above code to work in a multitasking, multiprocessor environment on the 6800 and 6801 -- think about what happens if the CPU is interrupted in the middle of modifying PSP or FP, or using XWORK.
Your OS will need its own PSP, FP, XWORK, etc., and saving and restoring the user process's PSP, FP, XWORK, etc. will be a required step in switching tasks. Some other processes besides the OS may want their own virtual registers in the direct page, as well.
The 6809 can give each process its own direct page, of course.
No comments:
Post a Comment