An external hardware stack for Forth on the 6502/65816 ?

[scotws]

I've been wondering if it would make sense to add an external hardware stack to my 6502 to help with Forth -- the idea would be to get the Data Stack (DS) out of Zero Page and free up the X Register. So far, I'd have to say "no", but maybe somebody has an idea I missed. I've gotten this far:

Concept
The idea would be to have an address you could just write to (STA $FF00 for example) that would push a byte on the "external" stack, while reading it would pop a byte (LDA $FF00). The processor wouldn't have to deal with any of the messy stack management stuff at all, and (in the case of Tali Forth) the X Register wouldn't be fixed as the DS pointer.

Hardware solutions (A CPLD is considered cheating in this project)
It turns out there actually was a LIFO chip out there for a while, the M66250E (http://www.alldatasheet.com/datasheet-p ... 66250.html) with 5120 8-bit words. Not being produced any more, of course. Lots of FIFO chips out there, but no LIFOs. Sigh.

Since we're looking for a bidirectional shift register, we could use the 74HCT194 (http://pdf1.alldatasheet.com/datasheet- ... CT194.html), one for each of the eight "slices" of the byte to be saved; that would give us a stack depth of four entries with eight ICs. If we want to be able to hold four DOUBLE numbers at once (a 16 word stack), we'd be using 32 chips. Ouch. The 74HCT299 (http://pdf1.alldatasheet.com/datasheet- ... CT299.html) can handle 8 bits, but that's still 16 chips. Both of these have seriell-to-parallel functions, there doesn't seem to be a "pure" bidirectional shift register on the market anywhere.

Third, we could rig up some system where some extra RAM is indexed by a register that has binary count up, count down functionality, something like two 74HCT193s. Far fewer chips used, but timing might be tricky, and much more glue logic.

(I briefly played with the notion of building a bidirectional shift register out of D flipflops -- it's actually not that complicated, it turns out -- but that would use even more chips and space.)

Problems with the 6502
For the sake of the discussion, let's just assume we have one of those solutions. Would it really be worth it? Remember, on the 6502 we have two bytes for every 16-bit stack entry, so something simple like DUP would end up as

Code: Select all

LDX $FF00
LDA $FF00

STA $FF00
STX $FF00
STA $FF00
STX $FF00

Which not only looks stupid, but takes 18 bytes and 24 clock ticks. The current code for Tali Forth is:

Code: Select all

DEX
DEX
LDA 3,x
STA 1,x
LDA 4,x
STA 2,x

That's 10 bytes and 20 cycles. So this kind of hardware support seems to slow things down. However --

Use with the 65816?
What about the 65816? Since we have freed up the X Register and it can be 16 bit wide, we can use it as the TOS (won't work with the 6502 because we can't keep one whole stack entry in the register). So we can reduce DUP to STX $FF00 and DROP becomes LDX $FF00 when in 16 bit mode. Now that's more like it.

However, I'm not sure how this stacks up (pun intended, though weak) compared to all the other ways of creating stacks on the 65816. Could this be worth the effort? Or should I wait for my own CPU project to build stacks from scratch ?

[barrym95838]

scotws wrote:

... Or should I wait for my own CPU project to build stacks from scratch ?

That's my vote, FWIW. I would really enjoy seeing what you have in mind for an original design.

Mike

[Edit: Jeff's KimKlone might be interesting reading for you, if you're interested in adding a separate PSP pointer and using unimplemented op-codes to push and pop.]

[GARTHWILSON]

From my experience writing my '816 (actually '802) Forth, I have to say that there were very few places in the whole thing that I needed X for anything else; so "freeing it up" really would have negligible value. I went through some exercises to see if having TOS in a register would be beneficial, and although there are places where it would be, there are others where it actually adds overhead. So I'd have to actually write an entire kernel and run programs on both kernels to find out if it was a wash or not.

Quote:

What about the 65816? Since we have freed up the X Register and it can be 16 bit wide, we can use it as the TOS (won't work with the 6502 because we can't keep one whole stack entry in the register). So we can reduce DUP to STX $FF00 and DROP becomes LDX $FF00 when in 16 bit mode. Now that's more like it.

Doing it the old-fashioned way, DROP on the '816 is just INX INX (one less byte and one less clock than a 16-bit LDX $FF00), although DUP is

Code: Select all

        DEX
        DEX
        LDA 2,X
        STA 0,X

When you have hundreds of primitives, you can bypass some of the DUPs because if it's inside a primitive, you don't need to DUP something just because the next thing will destroy it. Just use it in place without DUPing or destroying it. Similarly, you can have words you might want headerless like DUP>R , combinations that are commonly used. On the '816, DUP>R is only

Code: Select all

        LDA  0,X
        PHA

Next, what do you plan to do for looping controls, where the index and limit are on the hardware stack (meaning just accessing the top stack item is not enough), and you might also want to reach back further into it for J ? Would you have a separate stack for those?

[Rob Finch]

Quote:

Next, what do you plan to do for looping controls, where the index and limit are on the hardware stack (meaning just accessing the top stack item is not enough), and you might also want to reach back further into it for J ? Would you have a separate stack for those?

An adder combined with a counter connected to the address lines of the RAM could turn an ordinary RAM into a ring buffer. Incrementing / decrementing the counter would change the location that is the top of stack. You could also then read the next items on the stack up to the size of the RAM.

[nyef]

Rob Finch wrote:

An adder combined with a counter connected to the address lines of the RAM could turn an ordinary RAM into a ring buffer. Incrementing / decrementing the counter would change the location that is the top of stack. You could also then read the next items on the stack up to the size of the RAM.

So, combine this with a little more hardware trickery: Is there an up/down counter where you can set and query the counter value? If there is, and you can arrange a combination of pre-increment / post-decrement or the other way around, map it so that A0 runs to your RAM, A1 and A2 select between RAM at the counter index, RAM at pre-incremented counter index, RAM at post-decremented counter index, and the counter value itself, with the counter only getting clocked if A0 is high. Now you have a 16-bit wide stack with a manipulable pointer, operations to access the top of stack, to push, and to pop. And it only takes 3 address lines, a bit of decoding logic, a small RAM, and an up/down counter that I'm not about to claim exists (or claim does not exist). For more fun and games, have two pointers into the same memory.

A quick bit of digging suggests a couple of plausibilities for the counter... if you're willing to accept a limit of 16 stack entries.

[scotws]

GARTHWILSON wrote:

Next, what do you plan to do for looping controls, where the index and limit are on the hardware stack (meaning just accessing the top stack item is not enough), and you might also want to reach back further into it for J ? Would you have a separate stack for those?

Honestly, I hadn't thought that far yet. I'm still somewhat in shock that extra, specialized hardware might not be the best way to do something. Sort of conflicts with my world view to date .

[scotws]

barrym95838 wrote:

That's my vote, FWIW. I would really enjoy seeing what you have in mind for an original design.

(Laugh) Let's let me get my first primitive 6502 SBC out the door first, shall we?

If I had to answer, I'd say a stack machine with 16 bit words, because that should be simplest despite their well-known limitations (see http://users.ece.cmu.edu/~koopman/stack ... index.html for background). Make the address 64 k of words (for 128 Kb RAM). What makes me go pale is not the CPU itself, but the idea of creating an ALU. That might be where I chicken out and use CPLD or something ...

[nyef]

scotws wrote:

What makes me go pale is not the CPU itself, but the idea of creating an ALU. That might be where I chicken out and use CPLD or something ...

For what it's worth (possibly not much), Mouser still has 74LS181 ALUs in stock. The upside? It's a bit-slice ALU. The downside? LSTTL logic.