Switching Feet on the Beach --
Ephemeral Frame Pointer for Split
Stack
Talking about stack frames with a frame pointer on split stacks didn't put you to sleep?
Well, let's try it without a frame pointer register.
How would this work?
We're going to assume a runtime discipline in which every routine allocates all its parameters, local (dynamic) variables, and temporary variables on the parameter stack at entry, and never pushes anything else to it, never pops anything from it. Pascal can do this. Ada can do this. C can even do this, but it really doesn't need to.
Again, we have routine 1 that has received two parameters, P1_1 and P1_2. And it has two temporary values or local variables, we don't care which, on the parameter stack, T1_1 and T1_2. Reviewing the case without a stack frame, this is how we diagrammed it before:
| 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_
????
????
????
This time,
we're going to set up a frame without using a frame pointer register.
Here's how we start:
nnnn
<=
FP_0
P1_1_
P1_2
T1_1
T1_2
<=
_PSP_
????
rrrr
FA_0
RA_0
<=
_RSP_
????
????
????
Then the caller pushes its stack pointer as a frame pointer on the return
stack, and pushes the called routine's parameters on the parameter stack:
nnnn
<=
FP_0
P1_1_
P1_2
T1_1
T1_2
<=
FP_1
P2_1_
P2_2
<=
_PSP_
????
rrrr
FA_0
RA_0
FA_1
<=
_RSP_
????
????
????
Then the call issues.
On entry, the called routine will allocate space for its return parameter(s), and then copy the call parameters down, leaving room for the return parameter(s) where they can be left behind on exit:
nnnn
<=
FP_0
P1_1_
P1_2
T1_1
T1_2
<=
FP_1
RP2_1_
P2_1_
P2_2
<=
_PSP_
????
rrrr
FA_0
RA_0
FA_1
RA_0
<=
_RSP_
????
????
????
And then it will allocate room for the called function's local variables and temporary values, which will look like this:
nnnn
<=
FA_0
P1_1_
P1_2
T1_1
T1_2
<=
FA_1
RP2_1_
P2_1_
P2_2
V1_1
T1_1
<=
_PSP_
????
rrrr
FA_0
RA_0
FA_1
RA_0
<=
_RSP_
????
????
????
The called routine will reference all its own parameters, variables, and
temporaries via the parameter stack pointer. If it needs to reference
something in the caller's context and knows where it should be in the caller's
context, it can load the caller's frame pointer from the return stack and do
so.
At exit, it can simply deallocate everything but the return parameter(s) and
issue a return.
And the calling routine can immediately move the return parameter(s) where it
needs them, drop them, and go on its merry way.
* calling protocol for split stack frames on 68000
* with A6 as the parameter stack pointer,
* and the frame pointer saved to the return stack only.
ROUTINE1
* ...
MOVE.L A6,(-A7) ; saved A6 is the caller's frame pointer
MOVE.L PARAMETER1,-(A6)
MOVE.L PARAMETER2,-(A6)
BSR.W ROUTINE2
MOVE.L FRAME2.RETVAL1_OFFSET(A6),CALLSIZE+VARIABLEN_OFFSET(A6)
LEA RETURNSIZE1(A6),A6 ; deallocate parameters
LEA (A7),A7 ; drop frame pointer if it no longer needs it.
* ...
* and the caller must move results where they go in it's own frame
* immediately, to restore the parameter stack pointer offsets --
* or use some dynamic offset calculation that tracks what is on the stack.
* ...
*
*
* routine entry protocol for split stack frames
* and A6 as the parameter stack pointer
* and frame pointer on return stack only,
* but each routine allocates everything it needs on entry
* (Caller, of course, pushes call parameters before call,
* and pops return parameters to where they go on return.):
ROUTINE2
LEA -RETURNSIZE(A6),A6 ; call and return parameters are part of local frame
MOVE.L A6,A0 ; for copying
MOVE.L RETURNSIZE(A0),(A0)+
* ... repeat as necessary
LEA -FRAMESIZE+CALLSIZE+RETURNSIZE(A6),A6 ; allocate frame
* ...
MOVE.L PARAMETER2OFFSET(A6),D1 ; access the second parameter
* ...
SUB.L PARAMETER1OFFSET(A6),D3 ; access the first parameter
* ...
MOVE.L 4(A7),A0 ; get the caller's frame pointer
ADD.L CALLER.VARIABLENOFFSET(A0),D5 ; or something
* ...
* routine return protocol in all cases:
LEA FRAMESIZE-RETURNSIZE(A6),A6
RTS
I hope I wasn't too tired to get that right.
This also looks pretty reasonable.
On the 6809, we no longer need the frame pointer variable in DP:
* calling protocol for split stack frames on 6809
* with U as the parameter stack pointer,
* and the frame pointer saved to the return stack only.
ROUTINE1
* ...
PSHS U ; the caller's frame pointer
LDX PARAMETER1
LDD PARAMETER2
PSHU D,X
LBSR ROUTINE2
LDD FRAME2.RETVAL1_OFFSET,U
STD CALLSIZE+VARIABLEN_OFFSET,U
LEAU RETURNSIZE1,U ; deallocate parameters
LEAS 2,S ; drop frame pointer if it no longer needs it.
* ...
* and the caller must move results where they go in it's own frame
* immediately, to restore the parameter stack pointer offsets --
* or use some dynamic offset calculation that tracks what is on the stack.
* ...
*
*
* routine entry protocol for split stack frames
* and A6 as the parameter stack pointer
* and frame pointer on return stack only,
* but each routine allocates everything it needs on entry
* (Caller, of course, pushes call parameters before call,
* and pops return parameters to where they go on return.):
ROUTINE2
LEAU -RETURNSIZE,U ; call and return parameters are part of local frame
TFR U,X ; for copying
LDD RETURNSIZE,X
STD ,X++
* ... repeat as necessary
LEAU -FRAMESIZE+CALLSIZE+RETURNSIZE,U ; allocate frame
* ...
LDD PARAMETER2OFFSET,U ; access the second parameter
* ...
SUBD PARAMETER1OFFSET,U ; access the first parameter
* ...
LDX 2,S ; get the caller's frame pointer
ADDD CALLER.PARAMETERNOFFSET,X ; or something
* ...
* routine return protocol in all cases:
LEAU FRAMESIZE-RETURNSIZE,U
RTS
The 6801 has no surprises:
* 6801
* calling protocol for split stack frames on 6801
* with PSP as the parameter stack pointer,
* and the frame pointer saved to the return stack only.
ROUTINE1
* ...
LDX PSP
PSHX ; the caller's frame pointer
LDD PARAMETER1
JSR PPSHD
LDX PARAMETER2
JSR PPSHX
JSR ROUTINE2
LDX PSP
LDD FRAME2.RETVAL1_OFFSET,X
STD CALLSIZE+VARIABLEN_OFFSET,X
LDX PSP ; deallocate parameters
INX
INX
STX PSP
INS ; drop frame pointer if it no longer needs it.
INS
* ...
* and the caller must move results where they go in it's own frame
* immediately, to restore the parameter stack pointer offsets --
* or use some dynamic offset calculation that tracks what is on the stack.
* ...
*
*
* routine entry protocol for split stack frames
* and PSP as the parameter stack pointer
* and frame pointer on return stack only,
* but each routine allocates everything it needs on entry
* (Caller, of course, pushes call parameters before call,
* and pops return parameters to where they go on return.):
ROUTINE2
LDD PSP
ADDD #-RETURNSIZE ; call and return parameters are part of local frame
STD PSP
LDX PSP ; for copying
LDD RETURNSIZE,X
STD 0,X
INX
INX
* ... repeat as necessary
LDD PSP
ADDD #-FRAMESIZE+CALLSIZE+RETURNSIZE
STD PSP ; allocate frame
* ...
LDX PSP
LDD PARAMETER2OFFSET,X ; access the second parameter
* ...
LDX PSP
SUBD PARAMETER1OFFSET,X ; access the first parameter
* ...
TSX
LDX 2,X ; get the caller's frame pointer
ADDD CALLER.PARAMETERNOFFSET,X ; or something
* ...
* routine return protocol in all cases:
LDD PSP
ADDD #FRAMESIZE-RETURNSIZE
STD PSP
RTS
and the 6800:
* calling protocol for split stack frames on 6800
* with PSP as the parameter stack pointer,
* and the frame pointer saved to the return stack only.
ROUTINE1
* ...
LDAA PSP
LDAB PSP+1
PSHB ; the caller's frame pointer
PSHA
LDAA PARAMETER1
LDAB PARAMETER1+1
JSR PPSHD
LDX PARAMETER2
JSR PPSHX
JSR ROUTINE2
LDX PSP
LDAA FRAME2.RETVAL1_OFFSET,X
LDAB FRAME2.RETVAL1_OFFSET+1,X
STAA CALLSIZE+VARIABLEN_OFFSET,X
STAB CALLSIZE+VARIABLEN_OFFSET+1,X
LDX PSP ; deallocate parameters
INX
INX
STX PSP
INS ; drop frame pointer if it no longer needs it.
INS
* ...
* and the caller must move results where they go in it's own frame
* immediately, to restore the parameter stack pointer offsets --
* or use some dynamic offset calculation that tracks what is on the stack.
* ...
*
*
* routine entry protocol for split stack frames
* and PSP as the parameter stack pointer
* and frame pointer on return stack only,
* but each routine allocates everything it needs on entry
* (Caller, of course, pushes call parameters before call,
* and pops return parameters to where they go on return.):
ROUTINE2
LDAB #RETURNSIZE ; call and return parameters are part of local frame
JSR ADDBPSP
LDX PSP ; for copying
LDAA RETURNSIZE,X
LDAB RETURNSIZE+1,X
STAA 0,X
STAB 1,X
INX
INX
* ... repeat as necessary
LDAB #-FRAMESIZE+CALLSIZE+RETURNSIZE
JSR ADDBPSP ; allocate frame
* ...
LDX PSP
LDAA PARAMETER2OFFSET,X ; access the second parameter
LDAB PARAMETER2OFFSET+1,X
* ...
LDX PSP
SUBB PARAMETER1OFFSET+1,X ; access the first parameter
SBCA PARAMETER1OFFSET,X
* ...
TSX
LDX 2,X ; get the caller's frame pointer
ADDB CALLER.PARAMETERNOFFSET+1,X ; or something
ADCB CALLER.PARAMETERNOFFSET,X
* ...
* routine return protocol in all cases:
LDAB #FRAMESIZE-RETURNSIZE
JSR ADDBPSP
RTS
*
ADDBPSP CLRA
TSTB
BPL ADDBPSM
COMA
ADDBPSM ADDB PSP+1
ADCA PSP
STAB PSP+1
STAA PSP
RTS
*
ADDBX STX XWORK
CLRA
TSTB
BPL ADDBXP
COMA
ADDBXP ADDB XWORK+1
ADCA XWORK
STAB XWORK+1
STAA XWORK
LDX XWORK
RTS
And, again, that doesn't look all that bad.
A lot of that would be done on the 6800 and 6801 by low-level subroutines, of course, since we don't want the object just blowing up in size, just to support high-level constructs at run-time.
Well, really, if we're being sensible, we're not usually going to want to bother with frames.But you can mix and match frames like this with frameless in the split stack runtime, as long as you either don't reach into the caller's stack frame, or at least know what the caller's stack frame looks like so you know how to reach in.
And we must not forget that multitasking and multiprocessing on the
6800 and 6801 require saving and restoring the virtual registers in the
direct page -- PSP, XWORK, and such,
And I guess it's time to look at stack frames with a single combined stack. Yuck.
Or skip out and move ahead to binary output.
No comments:
Post a Comment