I'm noodling around with some ideas around stacks and parameter passing to allow reentrant programming. So I built two separate stack modules to see how many instructions are required for basic operations. I tried to make the interfaces similar enough that I could switch between them and judge their relative merits.

The first is the X register stack I've seen in several Forths (including Tali Forth): https://github.com/Martin-H1/Lisp65/blob/master/stack.asm

The second is a 16 bit stack pointer in page zero that grows downward from ram top: https://github.com/Martin-H1/Lisp65/blob/master/bigstack.asm

It's pretty clear that the Forth style stack is leaner, faster, and more suited for fast light calls. For example I could see it used as the calling standard for a math library, a heap, or I/O. The problem is that it doesn't support that much depth, consumes a register, and half of page zero. That makes interfacing it with reused code a challenge at times.

The second stack seems way too big and slow for operations like push, drop, swap. But on the plus side supports large allocations, stack depth, and a light register and page zero footprint. That allows interfacing with reused code.

Not sure where I am going with this, other than I am curious if anyone has better ideas?

To save him some typing, I will first point you to Garth's excellent Stacks Treatise.

As to your own points, yea, I feel there's no single answer. Different solutions are better for different situations, it all depends how you intend to use them.

There is however a third method you may not have considered, where you can use the Actual Stack for parameter passing - even on the 6502. You just have to use the TSX / TXS instructions and the a, x addressing mode with a base offset.

E.g. see this macro library I wrote. This is basically very similar to your first option, but without permanently tying up the X register - it can still be used for other purposes when you're not accessing the stack.

_________________
Want to design a PCB for your project? I strongly recommend KiCad. Its free, its multiplatform, and its easy to learn!
Also, I maintain KiCad libraries of Retro Computing and Arduino components you might find useful.

If you want to stick with a 6502 instead of a 65816, you might consider adding extra hardware to do the job. For example, you could map half of zero page to an unused section of RAM and hook up an up/down counter to drive address lines when that half of zero page is accessed. That way you could pulse the counter and have a new half zero page to work with for every function. You can pass parameters on the stack or just copy them to directly where you will need them in the mapped zero page if you aren't copying from another mapped zero page. I suppose you might also be able to set up a part of the memory map to point to the current half zero page plus one so you can copy from the current page to the next one directly saving cycles at the expense of more hardware.

This is all overly complicated but I think it will be faster than just about anything else you could do on the 6502.

EDIT: Alarm Siren, neat macros! Do you need to index by X for the STA in PTA?

You could use a hybrid technique using the CPU stack for arguments and locals but copying/restoring from RAM as it gets too full/empty.

I think BBC BASIC uses this approach when executing deeply nested procedures. Top active procedures are on the CPU stack for fast access while the stack image for parent precedures is copied to a software stack that grows down from below the screen memory (HIMEM).

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

@Druzyek, thanks for the reply, my project is a rewrite of a small Lisp interpreter from C to 6502 assembly, while making it generally reusable. So new hardware isn't something I want to consider. I tried using cc65 for the initial port, but between the cc65 overheard and lisp overheard, there was nothing left for programs.

@Alarm Siren, thanks for the links, I read through them and there was lots of useful information.

@BitWise, I think I will probably end up using a hybrid technique. The low level program machinery (e.g. I/O, memory management, and math) can use a small stack, as there's no recursion, few arguments, and call depths are shallow. It's parsing and evaluation where deep recursion can come into play. So I think a large stack specifically for those functions will be needed.

Thanks



Yep. and PTX, PTY and PTZ. Looks like I forgot to put it on that whole class of macro
Apart from checking they compile, I've not had anything complex enough yet to test them in. Still being mucking around trying to get my UART working.
I'll update the file now.

EDIT: Updated.

_________________
Want to design a PCB for your project? I strongly recommend KiCad. Its free, its multiplatform, and its easy to learn!
Also, I maintain KiCad libraries of Retro Computing and Arduino components you might find useful.

Do you know if every child procedure copies or if they had some sort of system for comparing stack space needed to stack space left before copying?

[Edit: I think this was in response to something in the macro library Alarm Siren linked to. My comment seems pretty out of place without having said this before.]

In my macros, I like to use prepositions to clarify; so you have for example

There's no doubt about the direction, ie, which one is the source and which is the destination, and it's more English-like, and it takes no extra bytes or execution time in the final machine code. "to" and "from" are EQUates that the macro uses to conditionally assemble the copying to be one direction or the other. Such parameters can also be put in the parameter list to just improve readability, without actually using them in the macro.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

I can't remember what the criteria is.

The disassembly here https://acorn.huininga.nl/pub/docs/sourcecode/Acorn/BASIC%202/BASIC2.asm
has the stack push at $B1A7 and the pull at $B236.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

Thanks. I was just wondering myself about the best way to do it. I have been thinking a slightly more sophisticated macro system could figure out automatically how much stack space your local variables need and copy that many bytes off the stack for you. I did something similar to manage zero page memory by pushing enough zero page bytes to hold function arguments and locals. It was not very efficient since it reuses the same memory over and over even if there is more zero page available.

I was thinking about this. Wouldn't this fail if you needed to use the stack for anything? For example, you have this for PKA:
Wouldn't this stop working if you did something like this:

I think the secret would be only doing the TSX once at the beginning, but then you have to keep track of it yourself. What do you think?

You can save X on the stack too, but then take that into account when formulating the number to add the index to. It not always necessary to re-do the TSX just because you pushed or pulled something. (This is all covered in the 6502 stacks treatise.) The macro will probably need to be modified.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

As stated in the 6502 stacks treatise, the most stack-intensive Forth application I could come up with, including servicing interrupts in high-level Forth, and also having the RTC on NMI interrupts, did not take more than 20% of either page 1 or page 0. Regarding the space it does take, keep in mind that having the ZP data stack reduces the need for other variables and pointers that are normally kept in page 0; so the penalty is little or none. You may even come out ahead.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

PKA is defined as copying into A the value at Offset from the top of the stack. If you've pushed something onto the stack, you need to adjust your offset to compensate. To avoid these difficulties, I envisage programs using the PHN macro to reserve an amount of space on the stack for locals. So, you'd get something like this:



I have considered modifying the macros, or adding a new set, that allows you to optionally skip the TSX if you know that you're not overwriting X in the mean-time thus improving performance a little - which would also permit your suggestion that allows you to still use the normal push/pull without clobbering the offsets since X isn't being constantly reloaded, but I originally decided that overcomplicated what I was trying to achieve. Also, the point of the macros is that you're not permanently turning X into an extra stack pointer, so it is expected that X may get used for other purposes in between stack accesses, so logically X will need to be reloaded.

A thought I've just had, would be modify the ENTER and LEAVE macros thusly:

My intent with ENTER/LEAVE was to simplify the process of entering and exiting from an Interrupt context, but with this addition it can also be used in ordinary function calls to preserve register state and reserve space for locals on the stack. The caller function's register values (and stack values, for that matter) can still be accessed with an appropriate PKA/PTA offset.

_________________
Want to design a PCB for your project? I strongly recommend KiCad. Its free, its multiplatform, and its easy to learn!
Also, I maintain KiCad libraries of Retro Computing and Arduino components you might find useful.

Would you do that by having the macro assign a temporary value that is added to the hard coded base address and replace all push and pull arguments with macros that increase or decrease that value? It seems like it would be tough to keep adding and subtracting to the base yourself, especially if you go back and add a push or pull and have to redo the following ones.

That makes sense. If it helps you, I think it is good that you have them, even if you sacrifice a little speed for ease of use.

I was curious about maximizing performance, so I tested out a few different ways on a simple function. When A='a', X=3, and Y=4 the function prints "aaabbbcccddd." A returns with the count of characters printed. Here are the cycle counts for the ways I tried, even though I would not say they are generalizable in any way. I imagine doing some of this with macros but they are expanded so you can see what I'm thinking. Could I change anything to make it faster?

I think doing everything in zero page could be the fastest. The fourth way without pushing anything only works for top level functions. I don't think it is possible with macros but a more sophisticated program could automatically rearrange zero page usage so as few bytes as possible have to be pushed.

1. Hardware stack: 322
2. Pushing zero page with loop: 324
3. Pushing zero page with unrolled loop: 277
4. Zero page with no pushing: 229
5. Zero page stack: 323

Output = AAABBBCCCDDD

1. Hardware stack


2, 3, 4. Zero page


5. Zero page stack