ALPP 02-14 -- One Foot on the Beach, One in the Surf -- Frame Pointer for Split Stack

One Foot on the Beach,
One in the Surf --
Frame Pointer for Split Stack

(Title Page/Index)

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. 

[JMR2024191759 note: I need to edit this. The code snippets and the explanation are slightly wrong. But, until I can get back to it, i have a concrete example of this which should clear things up, especially for the 68000, at: https://joels-programming-fun.blogspot.com/2024/10/alpp-02-18-ascending-wrong-island-single-stack-frame-example-68000.html#splitstack.]

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.

Well, that's enough for one chapter, and, as I say, I want to show you another way to do frames with a split stack before I show you how to do the single stack.

(Title Page/Index)