Is the following a way of implementing the Forth swap primitive ?



Is there another faster way of implementing swap ?

LOL, that's a pretty complicated way to do a SWAP ! But yes, it'll work. Is this for a stack machine where the instructions shown are assembly-language instructions (making this a primitive)?

Yes, they are assembly language instructions for a stack machine. There isn't an easy way to do a swap primitive in hardware, so I'm looking at how it can be done using the limited instruction set. Although it's six instructions I think it'll execute in only two clock cycles. The instructions are short - 5 bits. I thought there might be a way using DUP and XOR as well.

I've basically got the Bugs18 instruction set plus a couple of more instructions. I have room to add a couple of instruction if that would help. But it can't be an exchange. About the only thing I could think of was to modify the DROP instruction to shift the dropped values into a temp storage area then add two instructions to push back the temporary storage words. That would reduce the instruction sequence to four instructions, but the additional instructions would be useless for anything but a swap.

Could you take a leaf from the Z80 implementation, and implement a swap by twiddling the addressing of the register file?? (I'm assuming the stack, or the top of it, are actually registers on chip)

What if you don't actually swap what's in those locations? Could there be some sort of indirection or register renaming that merely alters which register gets selected?

Just throwin' the idea out there. That's how my KK Computer swaps the contents of K0 and K3 when doing a Far jump or call -- it just toggles a flipflop that says which register is which; the data never actually moves. Obviously that's in a much simpler context, and the cost in your case would be a lot higher. But maybe there'd be spin-off benefits that make it worthwhile. I leave that to you to judge!

( For those who may've missed it, the post describing the Bugs18 CPU is here. )

ps- darn it, Ed! You managed to post while I was still typing!

Thanks, I had not thought of fiddling with the address. Maybe some kind of map would work. There are only 64 locations after all. The LSB address bit can't just be flipped because that would mean memory is accessed in pairs on even addresses and the address might be odd.
Memory is laid out like:
address0
address1
address0
If the bit of the second cell is flipped which other cell should be referenced ?

If there was a map maybe incrementing the one cell and decrementing the other one would do for a swap. But that's tricky because the map may need to be reset at some point. The problem is also parallel hardware. What if there's a swap followed by a swap (with an intervening operation) ? A map could get quite scrambled.
In any case its looking like a complicated solution would be required.

I may go back to changing DROP into a POP operation into a fifo instead of a stack. Then have add a PUSH from fifo operation. It would allow swapping the order of words on the stack around. It might be usable with other things like numeric conversions.

would change the order of the top three words around on stack. Maybe if the fifo were accessible with fetch and store too it would be more useful.
I have to put some more thought into it.

Actually, this is no more difficult than any other single-cycle primitive. In psuedo-HDL:


The only reason that Bugs18 does not implement swap is because other primitives were deemed more valuable given the limited choice of 16 4-bit encodings. A wider opcode (eg. 32 5-bit encodings) would increase the choices of what to implement.

Myron Plichota

I've been a bit misleading in the simplicity of the core.
I should maybe mention that the instructions are all executing in parallel at the same time (sort of). The new top of stack from one instruction is fed to the next one in a cascade of logic, and the instruction needs to update the stack at the same time. Right now I have the core writing only one value to the top of stack per instruction executed (five write ports). Updating the next on stack at the same time would double the number of write ports required just for that single instruction, and the cores already huge (50,000 LUTs). It's only about 350 LOC but has lots of read / write ports in it.
Cascading the logic no double slows down the cycle time a lot but everything gets done in one cycle.

It must be the second write port which hurts - but then, it's only needed for one register, I think? Is there a way to make use of that?

It does sound challenging! But since you're crazy enough to contemplate a parallel implementation I thought I'd throw the idea out there -- a map, as you say. Register renaming, although in a form far more complex and expensive than what my KK or the Z80 does.

Two, since it's a swap we want. Probably what you meant. But the real trouble is it won't always be the same two, if I understand what Rob's up to.

(I was thinking one of the writes just uses the usual write port - you need one write port to get anywhere! - and so it's only the other write which needs a second port. If that were always the top of stack - and if that were always the same physical register - then I was thinking of pulling that register out of the register file. However, you might be right, and the world of Rob's CPU is much more complex than that.)