Designing a trivial CPU, part 2: machine code
Go to the first post in this series.
Introduction
I’m designing a small CPU. In the last post, I picked (fairly
arbitrarily) bit-size, registers, addressing modes, and an instruction
set. To recap, that’s: 8 bits; four registers (x, y, i and j);
four additional indirect modes ((i), (j), k and (k)), where
k is an 8-bit constant.
The instructions are summarised below:
| Instruction | Operation | Addressing (r') |
Opcodes |
|---|---|---|---|
MOV r, r' |
r = r' | regs | 16 |
LDR r, ind |
r = ind | indir | 16 |
STR ind, r |
ind = r' | (i), (j), (k) |
16 |
ADD r, r' |
r = r + r' | regs, indir | 32 |
SUB r, r' |
r = r - r' | regs, indir | 32 |
ADC r, r' |
r = r + r’ + C | regs, indir | 32 |
SBC r, r' |
r = r - r’ + C | regs, indir | 32 |
INC r' |
r = r + 1 | regs | 4 |
DEC r' |
r = r - 1 | regs | 4 |
JMP cc k |
pc = k if cc | — | 4 |
ASR r' |
C = r & 1; r = r >>> 1 | regs | 4 |
LSR r' |
C = r & 1; r = r >> 1 | regs | 4 |
ROR r' |
C = r & 1; r = r >> 1 | r << 7 | regs | 4 |
RRC r' |
C = r & 1; r = r >> 1 | C << 7 | regs | 4 |
IN r, (k) |
r = (k) | regs | 4 |
OUT (k), r |
(k) = r | regs | 4 |
Todays’ post is about fitting the instruction set above into the 256 available opcodes.
Mapping to opcodes: consistency
The opcodes of the processor are 8 bits wide. Each distinct
instruction (such as ADC x, (i)) maps to one opcode. The question
is: for each instruction, which one?
What we want to do here is ensure that the process of decoding the
instructions is as simple as possible. This means that similar
functionality should be grouped together in some way. For example,
similar instructions should share as many common bits as possible. The
target register (r) should be encoded in the same place every time,
and in the same way, and so on.
With that in mind, we can paint in quite a few features very quickly. Arbitrarily, let’s put the register/operand information in the LSBs of the instruction, leaving the MSBs to indicate which instruction it is.
Arithmetic
The ADD and SUB instructions account for 128 opcodes – half of
the available space – so let’s put them in the upper half of the
opcode space, with opcodes like 1xxx xxxx. They each have a
destination register, one of four, and two kinds of source (either the
four registers, or the four indirect modes). So we could put the
destination register in bits 2-3, the kind of source in bit 4, and the
source in bits 0-1. That leaves us with bits 5 and 6 to encode whether
it’s ADD or SUB, and whether it’s using the carry bit from a
previous operation:
| Instruction | 7 | 6 | 5 | 4 | 3-2 | 1-0 |
|---|---|---|---|---|---|---|
op r, r' |
1 | add/sub | carry | 0 | r |
r' |
op r, ind |
1 | add/sub | carry | 1 | r |
ind |
I’m going to leave INC and DEC for later, as they’re much smaller.
Register and memory moves
The next biggest class of operation is the move operations – between
registers, or to and from RAM. These account for 44 opcodes between
them. Let’s put them all in the first opcodes, 00xx xxxx. Note that
LDR and STR both use indirect addressing, and MOV works with two
registers. We’ve previously used bit 4 to indicate indirect
addressing, so LDR and STR can both have bit 4 set, and MOV have
it clear.
| Instruction | 7 | 6 | 5 | 4 | 3-2 | 1-0 |
|---|---|---|---|---|---|---|
MOV r, r' |
0 | 0 | 0 | 0 | r |
r' |
LDR r, ind |
0 | 0 | 0 | 1 | r |
ind |
| unused | 0 | 0 | 1 | 0 | – | – |
STR ind, r |
0 | 0 | 1 | 1 | r |
ind |
Shifts
Next, we have the four right shift/rotate instructions. These all
operate on a single register, with no indirect addressing. There’s
four instructions, and four registers. We’ve generally been using bit
4 = 0 for register-based instructions, and conveniently the unuse
block above is one of those, so we can fit these instructions in
there:
| Instruction | 7 | 6 | 5 | 4 | 3-2 | 1-0 |
|---|---|---|---|---|---|---|
ASR r |
0 | 0 | 1 | 0 | r |
00 |
LSR r |
0 | 0 | 1 | 0 | r |
01 |
ROR r |
0 | 0 | 1 | 0 | r |
10 |
RRC r |
0 | 0 | 1 | 0 | r |
11 |
This means that, we’ve filled up all the opcodes 1xxx xxxx and 00xx xxxx, leaving 01xx xxxx unallocated so far.
The rest
We’ve still got INC/DEC (8 opcodes), IN/OUT (8 opcodes), and
JMP (8 opcodes). I’m going to fit the first four into the same
block: 0100 xxxx. This makes sense for the arithmetic ops, as this
is a “register” block, with bit 4 clear. It’s less obvious that it’s
appropriate for the I/O ops, given that they both use a (k)
indirection. We might have to revisit this later.
Finally, there’s the JMP instruction. That takes two parameters: the
condition code, cc, and an 8-bit constant address to jump to, k.
That’s 4 opcodes (one for each of the conditions).
Filling all of these in, we have:
| Instruction | 7 | 6 | 5 | 4 | 3-2 | 1-0 |
|---|---|---|---|---|---|---|
INC r/DEC r |
0 | 1 | 0 | 0 | r |
0 i/d |
IN r, (k) |
0 | 1 | 0 | 0 | r |
10 |
OUT (k), r |
0 | 1 | 0 | 0 | r |
11 |
JMP cc k |
0 | 1 | 1 | 1 | 00 | cc |
This leaves a few ranges unused:
| Instruction | 7 | 6 | 5 | 4 | 3-2 | 1-0 |
|---|---|---|---|---|---|---|
| unused | 0 | 1 | 0 | 1 | – | – |
| unused | 0 | 1 | 1 | 0 | – | – |
| unused | 0 | 1 | 1 | 1 | 01 | – |
| unused | 0 | 1 | 1 | 1 | 10 | – |
| unused | 0 | 1 | 1 | 1 | 11 | – |
Overview and conclusion
There are 16 blocks of opcodes, corresponding to the four MSBs of the opcode space. We’ve allocated 12 of those blocks fully, and two more partially. We can summarise them in this table:
| xx00 | xx01 | xx10 | xx11 | |
|---|---|---|---|---|
| 00xx | MOV |
LDR |
shift | STR |
| 01xx | misc | JMP |
||
| 10xx | ADD |
ADD |
ADC |
ADC |
| 11xx | SUB |
SUB |
SBC |
SBC |
A more detailed table, showing all of the opcodes, is available as a spreadsheet.
The next post is going to be about the structure of the hardware, and how it gets controlled to execute these instructions.