Simplest subset of 6502

[BillG]

Dr Jefyll wrote:

Martin_H wrote:

Code: Select all

nop

I don't dispute the value of having an instruction that does nothing. But is it necessary to devote one of your precious sixteen opcode encodings?

While not as universally useful as a single-byte instruction,

Code: Select all

adc     #0

does the same thing...

[gfoot]

BillG wrote:

While not as universally useful as a single-byte instruction,

Code: Select all

adc     #0

does the same thing...

You kind of need a "clc" as well then, and then might as well just use the "clc" alone. There are a lot of two byte options. A branch-0 is maybe a decent true nop, that doesn't affect flags, in two bytes.

Even if there's no true "nop" though, the utility of having one more nearly-nop instruction is probably high enough to make it worthwhile.

[BillG]

Good point! or, and, eor then. Still, flags are modified.

Branch *-2 does not consume a consistent number of clock cycles depending upon page boundaries.

[litwr]

We may also remove ORA (and use AND and EOR instead), ROL (use ADC), INC (use ADC), BNE (use BEQ and JMP), and BCS.

[barnacle]

The ROL instruction is probably easiest to implement as an ADC internally any way, so no need for both.

If you're feeling enthusiastic, remove ORA and AND and EOR and replace them with a single NAND...

Neil

[Alarm Siren]

barnacle wrote:

If you're feeling enthusiastic, remove ORA and AND and EOR and replace them with a single NAND...

Alarm Siren wrote:

To be clear I am talking about strict subsets of one of the 65C816 or 65C02. You're not allowed to alter or add anything, only take things away; what you end up with must still be binary compatible with an existing 65C02 or 65C816 program which doesn't use the removed capabilities.

[Martin_H]

Dr Jefyll wrote:

I don't dispute the value of having an instruction that does nothing. But is it necessary to devote one of your precious sixteen opcode encodings?

Back in the day I sprinkled NOP instructions in my code during debugging to allow patching in place without the need to reassemble. That saved time as the NOPs allow for keeping branch offsets the same while inserting or removing instructions. That's probably less relevant with modern hardware, but they're also useful for adjusting timing as well. So I think a do nothing instruction of some sort is needed.

George's idea of BRA 0 as a NOP replacement would certainly be a possibility, but at two bytes it might be a little awkward during a patch in place scenario.

barnacle wrote:

If you're feeling enthusiastic, remove ORA and AND and EOR and replace them with a single NAND...

That would work and fits my Turing Tarpit Challenge, and I kinda like it. But it doesn't meet the challenge in this thread, and might be a tad rough for many people.

[Proxy]

ooooh, this is a pretty neat topic!

Martin_H wrote:

Code: Select all

Accumulator operations: and, ora, eor, adc, clc, inc, ror, and rol
Memory operations: lda #, lda absolute, lda (), sta absolute, and sta ()
Flow control instructions: bcc, bcs, beq, bne, jmp absolute, jmp (), jsr absolute, rts, and nop

That's 16 instructions

hmm, am i missing something? to me that adds up to 18 instructions (22 total opcodes)
also personally i like counting opcodes more than "instructions" as it seems less ambiguous.

anyways you could replace INC A with ADC # since it has the same function, but can also decrement.
personally I would drop JMP (abs) and NOP, i just don't find them that useful
and do you really need both types of branches (set and clear)? couldn't you make do with just BCS and BEQ, and then simulate the function of BCC and BNE via a macro or by reordering code?

that would bring the total down to 18 opcodes:

Code: Select all

01 - ADC #
02 - ADC abs
03 - ORA abs
04 - AND abs
05 - XOR abs
06 - ROL A
07 - ROR A
08 - CLC
09 - LDA #
10 - LDA abs
11 - LDA (zp)
12 - STA abs
13 - STA (zp)
14 - BCS r
15 - BEQ r
16 - JMP abs
17 - JSR abs
18 - RTS

you could get it down to 16 opcodes if you cut the indirect LDA/STA instructions.

hmm, thinking about it a bit more... technically LDA # and ADC # aren't needed either. assuming the code is located in ROM immediate values will also be in ROM inlined with the code, therefore you could simply put those values somewhere else in the ROM and use absolute addressing modes to get them.

basically, this:

Code: Select all

LDA #$72

is functionally the same as this:

Code: Select all

LDA a:value

.data
value:  .byte $72

therefore immediate addressing modes can be cut if an absolute version already exists.

anyways i really doubt you could get all the way down to 8 opcodes without severely limiting the CPU's functionality (and basically turning it into a slightly more fancy turing machine).
but 32 seems like it would be perfect, as that gives you enough opcodes to re-add some useful stuff.
example that i quickly threw together:

Code: Select all

01 - ADC #
02 - ADC abs
03 - ORA abs
04 - AND abs
05 - XOR abs
06 - ADC abs,x
07 - ORA abs,x
08 - AND abs,x
09 - XOR abs,x
10 - ROL A
11 - ROR A
12 - CLC
13 - TAX
14 - TXA
15 - TSX
16 - TXS
17 - PHA
18 - PLA
19 - LDA #
20 - LDA abs
21 - LDA abs,x
22 - LDA (zp)
23 - STA abs
24 - STA abs,x
25 - STA (zp)
26 - BCC r
27 - BCS r
28 - BNE r
29 - BEQ r
30 - JMP abs
31 - JSR abs
32 - RTS

sadly (zp),x doesn't exist. that would've been useful.

[sburrow]

This is intriguing to me. I ran across this topic some time ago, but now I'm suddenly interested.

I've been looking at One-Instruction Computers, something from Wikipedia. A common one is "subleq" which grabs, subtracts, stores, then branches. Apparently it's "Turing-Complete"?

Anyways, here's my little list, though I haven't tested it all myself to see if it would be enough or not. I am choosing immediate addressing for nearly all instructions with the idea that you can use self-manipulating code to achieve other addressing modes.

Code: Select all

LDA # 
STA a - Need to be able to store something somewhere eventually!
AND #, ORA #, and EOR # - Basic logic
ADC #, SBC # - For, um, math.
CMP #
BMI - Or some such branching.
ROL A - Just for fun!
JMP a - For larger jumps.

If you use BMI/BPL instead of BCC/BCS you don't need a carry flag necessarily. It would act more like BIT, checking bit #7 to branch or not branch.

I think CMP isn't absolutely needed if you have SBC. And somewhere above it was suggested to simply use NAND instead of AND, ORA, and EOR.

I saw someone else saying ADC #$00 would be a good replacement for NOP. That's clever

I think the original purpose was to have this still *useful* but I wonder if you could sorta replicate that "subleq" instruction using only LDA, SBC, STA, and BMI.

Interesting mind game. Thank you!

Chad

[barnacle]

ROR might be of more use than ROL (which is just adding the accumulator to itself).

Neil

[Martin_H]

Proxy wrote:

ooooh, this is a pretty neat topic!
hmm, am i missing something? to me that adds up to 18 instructions (22 total opcodes)

I didn't see your reply earlier, but I was counting all variations of an instruction as a single instruction. So LDA immediate and LDA (ZP) count as one instruction, but obviously more than one opcode. The same for STA, JMP and JSR. You're right that you can drop INC, but I kept it because I was trying to emulate the PDP-8.

sburrow wrote:

Anyways, here's my little list, though I haven't tested it all myself to see if it would be enough or not. I am choosing immediate addressing for nearly all instructions with the idea that you can use self-manipulating code to achieve other addressing modes.

Code: Select all

LDA # 
STA a - Need to be able to store something somewhere eventually!
AND #, ORA #, and EOR # - Basic logic
ADC #, SBC # - For, um, math.
CMP #
BMI - Or some such branching.
ROL A - Just for fun!
JMP a - For larger jumps.

That's a really spartan set of instructions. Now go over to my Turing Tarpit thread in programming and write a program using that subset!

barnacle wrote:

ROR might be of more use than ROL (which is just adding the accumulator to itself).

Good point.

[commodorejohn]

If you're feeling particularly masochistic, consider that ORA and EOR can be synthesized with the use of AND and ADC/SBC, SBC can be substituted by twos-complementing the subtrahend and using ADC, and CMP is just an SBC that doesn't save the result...

[Squonk]

Removed by author

[Arlet]

Squonk wrote:

If only a fixed-depth hardware stack is available (like in the low-en PICs), nothing else is required. OTOH, a dynamic stack would add TAX and TXS from the 6502 existing opcodes in order to initialize the stack pointer.

6502 has a fixed depth hardware stack, just like low-end PICs, except that it is bigger. If you reserve all of page 1 for the stack, you don't need to initialize the stack pointer. It will start at a random position, and just wrap around when it reaches the page boundary.

[GARTHWILSON]

Arlet wrote:

6502 has a fixed-depth hardware stack, just like low-end PICs, except that it is bigger. If you reserve all of page 1 for the stack, you don't need to initialize the stack pointer. It will start at a random position, and just wrap around when it reaches the page boundary.

The low-end PICs do not give the programmer access to the stack.

You do however need to initialize the stack pointer on the '02 if you ever want to do stack-relative addressing, like to add the fifth byte in a stack cell to the accumulator without pulling the top four bytes off first.  You would do ADC $105,X; but for that to always work, you must start the program with (or have in the reset routine) LDX #$FF, TXS (or replace $FF with whatever is the highest address in page 1 that you want the hardware stack to use).  Otherwise, with a random start point, if the stack wraps from $100 to $1FF to $1FE long before the stack space is full, the abs,X indexing could put you into page 2, completely out of the stack area.  For example, if you started randomly at $107 and put nine bytes on the stack, they would be at $107 through $100, then wrap to $1FF, and S would contain $FE.  Now if you do TSX, LDA $105,X, $105+$FE puts you at $203, which is out of the stack area.  This is introduced in chapter 5 of my 6502 stacks treatise, at http://wilsonminesco.com/stacks/stackaddressing.html .