Writing generic subroutines in assembly

[Lost]

I've recently been learning 6502 assembly on my own while I wait for my first 65c02 based computer kit to arrive. Most of the sample code I look at tends to be very small to make it easier to learn. There is one area which (to me) seams missing. What is a good way of performing stack operations in a complex program?

The system stack will get used up very quickly; at least the way I generally write programs. So far my tiny sample programs have used the system stack just fine but anything really useful is going to eat it too quickly:
- C-style subroutine calls
- mathematical expression calculators (RPN calculator)
- Recursion

I saw an interesting technique that divided up the zero page into a sort of 'scratch area' and parameter area using the regular stack only for the subroutine call. This would extend the use a bit but still won't be good for recursion.

I could use the methods I've used on other systems and create my own program stack in regular memory and use JMP for subroutine calls and returns but this isn't as easy to read a JSR/RTS.

I even went to the trouble of creating a couple of subroutines that let me use the JSR/RTS for subroutine calls and returns. In essence I would 'move' data from the system stack to my processor stack right at the start of my subroutine and put it all back at the end. This would let me use JSR/RTS with my own stack but it cost extra processing time.

So, I'm curious what others are doing?

On a related not I haven't found much on how to create code that is relocatable at execution time but I've decided I probably won't need that functionality for a while.

[GARTHWILSON]

Your questions should be pretty well answered in the discussion at viewtopic.php?t=148 . You should get into Forth eventually, which makes heavy but extremely efficient use of stack space. You will find that the 6502 is not short on stack space at all.

Edit, many years later: I have an extensive treatise on 6502 stacks (plural, not just the page-1 hardware stack) on my website, at http://wilsonminesco.com/stacks/ .

[Ruud]

Lost wrote:

So, I'm curious what others are doing?

I'm busy with a Pascal compiler that should be able to compile itself. And there a big stack is needed for pushing parameters for functions and procedures. I solved this by creating a program stack at the top of the free RAM. A pointer in the Zeropage points at the last free place, just like the original Stack.
Some info, not up to date, can be found here: http://www.baltissen.org/newhtm/pcomp.htm

[Lost]

GARTHWILSON wrote:

Your questions should be pretty well answered in the discussion at viewtopic.php?t=148 . You should get into Forth eventually, which makes heavy but extremely efficient use of stack space. You will find that the 6502 is not short on stack space at all.

Ah, the curse of not reading EVERYTHING before posting. Yes, that thread pretty much covers my question. With some surprising answers too.

GARTHWILSON wrote:

I've been using Forth for 13 years on the 65c02, with programs up to 10,000 lines with interrupts serviced in high-level Forth while NMIs interrupted those ISRs for service in assembly, and I've never gotten anywhere near running out of space on either stack except with the rare error situation that wouldn't be satisfied with 256MB of stack space.

I really didn't expect a 256 byte stack to go that far but from what you said I will be surprised.

[kc5tja]

The key to realizing efficient stack usage is to separate your concerns. You need a split data/return stack for maximum efficiency. The split is vital because it prevents you from ever having to duplicate parameters.

For example, suppose we have the following C code:

Code: Select all

void fnA(int a, int b) {
  ...
  fnB(a);
  ...
}

void fnB(int a) {
  ...
  fnC(a);
  ...
}

void fnC(int a) {
  /* do something with a here */
}

Your knee-jerk reaction is, "Duhh, don't do that." I would agree, except real-world code does not offer nearly the opportunities to optimize this kind of code as you'd like. As a result, I'd wager about 33% to 40% of space used on the C stack is devoted to "threading parameters" to the appropriate functions. That means, 33% or so of stack space is actually wasted. This is due entirely to the fact that C uses a single stack for both data and return information.

Pascal is worse because it allows for lexically scoped nested functions and procedures. It uses the stack for not only return and parameter information, but also for extra pointers to nested lexical environments. Combine that with Pascal's support for passing non-trivial objects by value, something C doesn't provide usually, we find ourselves with excessively heavy stack utilization.

If you use the CPU's stack strictly for holding return information, you'll find that you can nest your subroutines 124 times before you run out of space. That is a huge amount of nesting. I work on a professional Java servlet e-commerce application for a rediculously well-known company, handling thousands of hits per server per hour, and its method nesting levels, while they can get awfully deep, almost never reaches over 100. Therefore, the 6502's stack requirements ought to be enough for really hard-core, heavy-duty applications even today.

[Lost]

kc5tja wrote:

If you use the CPU's stack strictly for holding return information, you'll find that you can nest your subroutines 124 times before you run out of space. That is a huge amount of nesting.

What are the other 4 bytes for? Are they reserved for really badly timed interrupts?

Either way, I believe you about the depth not being an issue when the stack is used as you suggested.

[kc5tja]

Yes, I was considering at least one level of interrupt handling, and assuming no data is temporarily stored on the stack.