Introduction

In this first article, I set out to introduce the instruction set I designed for my disintegrated machine project. This is a computer implemented in discrete transistors. Naturally it needs to be simple. Everything needs to be simple. The instruction set needs to be simple.

Memory

The computer might be simple, but it still has to be powerful. It still needs to run at a few MHz and have large enough memory to be usable. So, before delving into the instruction set, I have to address this subject. I certainly am not going to build many kBytes of memory out of discrete transistors. That would be crazy. Even by the standards of this project. People in the transistor era used core memories and that's what I'm going to use as well. In fact, I managed to get my hands on a 16k by 16bit core memory on eBay. It's from an old PDP-11. It is in fairly decent shape, hopefully working too. We shall see.

The core matrix is in the center, hiding under it's protective cover. The things around the edge, that look like integrated circuits are actually not: they are diode blocks, that do some really magical stuff when it comes to memory addressing. I'll come back to this later.

Three of the diode blocks got damaged during shipping (thanks!!) so we can take a closer look at them:

Funny how you can clearly see each individual diode.

I also took a picture with the protective cover off:

The black squares in the center are just a sea of tiny ferrite rings. More than a quarter of million of them!

This thing is one component of the PDP-11 MF11-U memory solution and there is pretty good documentation on it online.

The MF11-U contained several PCBs of this size, but - being already a fairly modern design - was using 74xx logic and integrated sense amplifiers. As such, those extra boards are not much use for me even if I could have them, which I can't. The description of their operation and the hows and whys of it is still very nice to have though.

The linked documentation gives a cycle time for the whole memory system at 1000ns and an access time 425ns. I think I care more about the access time in this case, so - if I can replicate this performance using discrete transistors - I should expect about 2MHz of clock rate out of the memory. For now, I will assume that and plan accordingly: both the CPU and the memory will target a 2MHz clock rate.

Now, core memories are funky little buggers. They are very alien to us, modern humans. If you've heard anything about core memory, it's probably that it's non-volatile. You can remove power, put it in your garage for a decade, turn it back on and the content is still there. And that is true. As long as you refrained from waving magnets around its vicinity. Getting to said content though is ... problematic. You see: read is destructive.

Once a memory location is read, its content reverts to '0'. Consequently, if one wants to preserve the content of the memory, every read must be followed by a write to the same address with the read-back content. This is how DRAMs work, albeit this behavior is hidden by the integrated controller of the memory devices.

Furthermore, writes can only write '1'-s. They can flip a '0' to a '1', but not the other way around. This is how most EEPROMs work internally, again, many times hidden by their integrated controllers. This means that if one wants to write a new value into memory, first the old value must be read (thus turning all bits to 0) and then the new content can be written.

The short of it is that reads and writes always come in pairs: every read must be followed by a write and every write must be preceded by a read.

As an interesting side-note: one could implement in-memory 'logical OR' operations by doing subsequent writes to the same location, but I haven't found an application for this behavior. Not in this project at least.

CPU

These considerations have some implications for the CPU design that I will cover later. There is one thing however that's important to note at this point: since reads and writes must be paired, read-modify-write operations are practically free: once the old data is read out, there's no obligation to write the same content back in. You will see in a moment how this behavior influences the CPU architecture (a.k.a. the instruction set).

Before that though, I want to talk about another aspect: registers. Registers are very expensive in terms of transistors. For now, you have to take my word for it, but let me just say: I've tried for days to come up with an affordable yet high-performance register design and failed. The takeaway is this: state is expensive. I need to be very careful about how many bits the CPU needs to store. You will see the impact of this realization in the instruction set as well.

Finally, I didn't want to have different data- and address-bus widths. I know many 8-bit processors had 16-bit address buses, but I have always found those designs cumbersome. Strange quirks in the instruction set, weird double-wide register or register pairs, funky addressing modes and generally hideous solutions are abound. Plus, my core memory happens to be 16-bits wide. So, I decided to simplify things and go for a pure 16-bit processor implementation: both address and data width is 16 bits, thus the total addressable memory is 64kWord (or 128KByte).

Architecture

With all that intro, let's talk about the processor. Specifically how the processor looks from the perspective of a programmer!

The CPU has only 4 registers, each 16-bit wide:

• $PC or program counter that points to the currently executing instruction
• $SP or stack pointer
• $R0 which is a general purpose register
• $R1 which is another general purpose register (albeit not as versatile as $R0 is)

In fact, $SP and $R0 are completely interchangeable, the instruction set treats them identically. $R1 cannot be used in certain addressing modes, but otherwise is also identical to the other two registers. $SP is only called that because that's the intended use for it, but it could just as well be called $R2.

There are five addressing modes:

• Register: in this case the operand comes from a register. For instance $R0.
• Immediate: in this case the operand value is a constant, encoded in the instruction itself. This could be the literal value '13' for instance.
• Memory-immediate: in this case the operand is loaded from a constant location in memory. This can be denoted in assembly as [6].
• Memory-relative: in this case the operand is loaded from a register-relative location, where the offset is a constant. The assembly syntax for this is [$SP-3] as an example.
• Register-relative: in this case the operand is a register, but further modified by a constant value. One example could be: $r0+4

The instruction set follows the two-address philosophy. That is to say: for a binary operation, the destination is one of the sources. For instance, if one wants to add $R0 and $R1, the result will need to be either one of these. One of these operands is always a register, the other could be many other things as we will see.

Instruction encoding

Each instruction is 16-bits wide with the general instruction format being the following:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|       OPCODE      |    OPB    |  OPA  |         IMMED         |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

OPA codes (i.e. where does the first operand come from):

• 2b00 - $PC
• 2b01 - $SP
• 2b10 - $R0
• 2b11 - $R1

OPB input codes (i.e. where does the second operand come from):

• 3b000 - [ IMMED+$PC ]
• 3b001 - [ IMMED+$SP ]
• 3b010 - [ IMMED+$R0 ]
• 3b011 - [ IMMED ]
• 3b100 - IMMED+$PC
• 3b101 - IMMED+$SP
• 3b110 - IMMED+$R0
• 3b111 - IMMED

The immediate field contains a 6-bit constant, encoded as a two-s complement value. In other words, it can represent a value from -32 to 31.

In the OPB encodings you see the slight asymmetry of the instruction set I alluded to before: you can use either $PC, $SP or $R0 as the base register, but not $R1.

BINARY group

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 |    B_OP   | D |    OPB    |  OPA  |         IMMED         |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

This group contains instructions that take two operands and produce one result. B_OP codes are:

• 3b000 - SWAP/SWAPI
• 3b001 - OR
• 3b010 - AND
• 3b011 - XOR
• 3b101 - ADD
• 3b110 - SUB
• 3b111 - ISUB

In general, the 'D' bit determines which of the two operands is the destination: if 'D' is set to 0, OPA is the destination, if set to 1, OPB is the destination.

SWAP/SWAPI exchanges the values of OPA and OPB, thus it writes both operands. There are several things that are special about it that should be mentioned:

Since both operands are written, the 'D' bit doesn't encode useful information, so it is reused as follows:

If 'D' is set to 0, INTEN (the interrupt enable bit) bit is flipped during execution on top of performing the swap operation. This variant is denoted in the assembly as SWAPI. If 'D' is set to 1, normal SWAP operation is performed.

Another specialty is that while normal operations support register-immediate and immediate arguments in the OPB field, SWAP/SWAPI doesn't. It can only write to one register and one memory location, not to two registers.

Finally, if SWAP/SWAPI is executed against $PC (that is OPA is set to denote $PC as the first operand), the value of $PC gets incremented as it's written out to memory. In other words, the swapped out value will be the address of the next instruction instead of the current one. This might sound strange, but it is a very handy behavior for proper interrupt handling. I will discuss this in more detail in the chapter about interrupts.

The ISUB instruction performs OPB-OPA, while the SUB variant performs OPA-OPB. The other operations are symmetrical to their operands so only one variant is needed.

There is one unused encoding (opcode 3b100) that I don't have anything planned for at the moment.

Notice how certain combinations don't make too much sense. For instance, one can set OPA to be R0, OPB to be immediate, then set 'D' to 1. This would mean that the *target* of the instruction is the immediate field. Even more nonsensical would be to set OPA to $R0, OPB to immedate+R0 and set the 'D' bit. In this case what would even be the destination?!

Being a simple CPU, this is acceptable. These encodings are just not valid and the actions taken by the processor are not defined. A more rigorous definition could require raising some sort of exception, but that's too much to ask of such a small design. Even more importantly, one could make use of these holes in the instruction set to provide more functionality, but again, I'm not going to go there in this project.

A consequence of the encoding above is that - while most operations can target both registers and memory directly - certain pseudo-operations, such as 'logical NOT' (XOR with -1) or 'negation' (0-$R0) can only be done with register destinations.

UNARY group

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 1 | 0 | U_OP  | D |    OPB    |  OPA  |         IMMED         |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

These instructions take only one operand and produce a single result.

U_OP codes:

• 2b00 - MOV
• 2b01 - ISTAT
• 2b10 - ROR
• 2b11 - ROL

For MOV, the 'D' bit determines if OPA or OPB is the destination. Whatever is selected, the other one is the source.

ISTAT stores the interrupt request status in bit0 and the interrupt enable (INTEN) value in bit1 of the destination, which is determined by the 'D' field. The other operand field is not used.

ROL and ROR rotate left or right their single argument by one bit. 'D' determines if OPA or OPB is used as the argument as well as the destination. Here too, the other operand is left alone.

Just as with the binary group, a 'D' bit of 0 selects OPA while 1 selects OPB.

PREDICATE group

Predicates are the mechanism to create conditional execution (including conditional branches) in the instruction stream. They evaluate a condition, and execute the subsequent instruction if the condition is met. If the condition is not met, the subsequent instruction is skipped.

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 1 | 1 |    P_OP   |    OPB    |  OPA  |         IMMED         |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

P_OP codes:

• 3b000 - OPA == OPB
• 3b001 - OPA != OPB
• 3b010 - OPA < OPB (unsigned)
• 3b011 - OPA >= OPB (unsigned)
• 3b100 - OPA < OPB (signed)
• 3b101 - OPA >= OPB (signed)
• 3b110 - OPA <= OPB (signed)
• 3b111 - OPA > OPB (signed)

Notice that there's no 'D' bit here (it's consumed in the opcode and is actually used to invert the condition code). This is because there's no destination.

Interrupts

If you read the previous section carefully, you've already noticed the INTEN status bit, which determines if interrupts are enabled or not. If enabled, an interrupt can occur. The CPU handles an interrupt by swapping the $PC register with the content of the memory at address 1. This means that execution will start from the address stored in memory address '1', while the interrupted processes' $PC is stored in that same location. Of course, the INTEN bit is also cleared, so further interrupts are disabled. Notice how this is almost the behavior of an SWAPI $PC, [1] instruction, but not quite: we don't increment the $PC before storing it in memory.

Returning from an interrupt happens by executing an SWAPI $PC, [1] instruction.

I promised above to come back to the point of incrementing the $PC during a SWAP or SWAPI operation.

Imagine that wasn't the case! After returning from an interrupt, what would the content of memory location 1 be? It would be the address of the SWAPI instruction, the one that returned from the interrupt handler. Now, imagine a new interrupt occurring. Where would the execution pick up for the interrupt? It would be this very same SWAPI instruction and we would immediately return from the handler. This is highly undesirable. Of course it could be worked around, but it would be slow. So, instead the SWAP and SWAPI instructions are modified to add 1 to the $PC (and only if OPA designates $PC) during the swap operation. This ensures that the stored location is the instruction immediately after the last instruction of the interrupt handler. I will show how an interrupt handler would normally be created a little further down.

Reset

During reset, the processor reads memory address 0 and loads the value there into $PC. In other words, the first memory location is the reset vector. Easy. Of course, interrupts are also disabled.

Branches

You probably have noticed that any instruction can target PC as the result. This means that branches (unconditional ones or conditional ones if predicated) usually are just some other instruction, using the $PC as a destination. For instance, to return from a subroutine, one could simply do: MOV $PC, \[SP].

Normally, after an instruction is executed, the program counter ($PC) is incremented. However, if the target of the instruction is $PC itself, this is undesirable. Logic is there in the processor to inhibit this post-execution incrementing in these cases.

Function calls

Now we enter the territory of how to use the instruction set, not just what it is.

Normally the stack would be used to communicate arguments, store local variables and return values. Of course registers could also be used but there are precious few of them. $R0 is designated as the return value register, if it fits in 16 bits. $R0 also carries the first argument, again, if it fits in 16 bits. $R1 is a scratch register and can be clobbered by the callee. In other words, $R1 cannot be expected to keep it's value after a function call returns. The return address is saved on the stack. The code for a function call would be something like this:

MOV $R1, $PC+4
MOV \[$SP-1\], $R1
MOV $PC, \[$PC+1\]
.WORD <function address>
...

In the first instruction, we calculate the return address (which should be 4 words after the current instruction). The next one stores this value on the stack. The stack pointer is at this point pointing to the first free entry of the stack when the call happens, so the return address should be put one entry before that. The third instruction is the actual call. This loads the function address from the word after the current instruction ([$PC+1]) and puts it in $PC. Right after this move, we have the function address stored in the code. The return address is calculated to point to the instruction after the .WORD line, where the code continues.

Returning from a function is even easier:

MOV $PC, [$SP-1]

The instruction set doesn't have push or pop instructions as you probably have noticed, so $SP will have to be manually moved. This is part of putting all the arguments on the stack. So for instance, one can imagine putting three arguments on the stack (and a fourth one in $R0) in the following slightly longer code-snippet:

; 2nd argument
MOV $R0, \[$SP-12\]   ; some local variable
MOV \[$SP\], $R0
; 3nd argument
MOV $R0, 3          ; a constant
MOV \[$SP+1\], $R0
; 4th argument
MOV $R0, \[$PC+8\]    ; some large constant stored in the code
MOV \[$SP+2\], $R0
; 1st argument
MOV $R0, $R1        ; some value held in $R1
; Modify stack
ADD $SP, 4          ; 3 arguments, plus the return address
; Do the call similar to before
MOV $R1, $PC+5
MOV \[$SP-1\], $R1
MOV $PC, \[$PC+1\]
.WORD <function address>
.WORD \<4th argument constant>
...

Here you see the same technique of storing large constants within the code itself and making sure we jump over it. This is used a lot since there are no instructions to access arbitrary memory locations and immediates in the instructions are limited to a rather small range.

A function prologue can be imagined something like this:

ADD $SP, 4       ; allocate space for local variables

The corresponding epilogue is:

SUB $SP, 4       ; Restore stack
MOV $PC, \[$SP-1\] ; Return from function

One can also save $SP on the stack and restore it from there as well. Also, growing the stack upwards (as shown here) or down is a choice of taste. So is whether $SP points to the last occupied or the first free entry. This is all possible since the stack is managed by SW.

If you look through the code carefully, you'll see that PUSH/POP instructions would not have saved all that much (probably 1 instruction in the whole sequence), especially in C-like languages which heavily use stack-frames.

More about LARGE constants

I've already introduced this concept: put constants inside the code, reference them using PC-relative loads and make sure you jump over them during execution.

One might think that these extra jumps are wasteful and there is some truth to that. It's a price to pay for simplicity. However, just as in the full 'call' example above, it's possible to gather the constants in one location and jump over them using a single jump statement, amortizing this overhead quite a bit. In some cases, again, the 'call' example is a good one, the jump can be part of something that's already happening and thus comes for free.

Another good example would be tight loops: even if constants are used within that loop, they can be outside the loop itself so the loop executes at optimal speed. There may or may not be an extra jump either at the beginning or at the end of the loop, but that's cheap compared to how many times the loop itself is iterating.

The name of this technique is 'literal pools' and many architectures use it, the most prominent of them being ARM. The only thing unusual about it here is that the offset range is very limited, so the pools need to be very nearby and much more scattered around the code.

Zero page

The first few words of memory (up to location 31) can be directly addressed by any instruction. This is valuable as their values can be directly used as operands. Since register and memory access has the same speed in this system, these 32 locations can be thought of as extra registers. Well, almost. As discussed above, location 0 is the reset vector and location 1 is the interrupt vector. That leaves 30 entries. I believe the best way to deal with these is something like this:

Entry        Usage
-------      -------------------
0            reset vector
1            interrupt vector
2            syscall vector
3            caller-saved pseudo-register
4            caller-saved pseudo-register
5            caller-saved pseudo-register
6            caller-saved pseudo-register
7            callee-saved pseudo-register
8            callee-saved pseudo-register
9            callee-saved pseudo-register
10           callee-saved pseudo-register
11           caller-saved pseudo-register for system calls / syscall parameter 2
12           caller-saved pseudo-register for system calls / syscall parameter 3
13           caller-saved pseudo-register for system calls / syscall parameter 4
14           caller-saved pseudo-register for system calls / syscall parameter 5
15           callee-saved pseudo-register for system calls
16           callee-saved pseudo-register for system calls
17           callee-saved pseudo-register for system calls
18           callee-saved pseudo-register for system calls

Eight locations are reserved as extra 'registers' for functions to use as they wish. The only restriction is that half of them are expected to be clobbered by the callee (so need to be saved by the caller, if their value is to be preserved) while the other four are expected to be preserved through function calls. There's a separate set of eight locations used similarly, except inside system-calls. Locations 11 though 14 are also used to pass in extra parameters to syscalls, if $R0 (holding the first parameter) is insufficient.

System calls

This last note conveniently leads us to the discussion of syscalls. I later introduce an MMU that allows for proper protected mode, but when I wrote this section, I didn't yet think that it was simple enough to include in the design. So for now, let's assume no protected mode or anything similar to it in this processor; the operating system is very limited in what it can and cannot enforce. Still, not directly encoding the physical address for the system call entry point in the user code is desirable. One can imagine doing a system call using the following instruction sequence:

SWAP $PC, \[2\]
.WORD <syscall number>
...

Parameter passing would happen through $R0 and the four zero-page locations detailed in the previous section. Upon return, the return value would be in $R0, or in the same zero-page locations as the parameters were if $R0 is insufficient.

The syscall handler would need to do a little gymnastics to get things straightened out:

MOV $R1, [2]           ; increment return address to skip over syscall number
ADD $R1, 1
SWAP $SP, [$PC+2]      ; swap back user stack, saving ours as we go
MOV $PC, $R1           ; return to caller

.WORD <syscall stack>  ; syscall save area for $SP
.WORD 0                ; syscall save area for $R0

syscall:               ; entry point for syscalls

SWAP $SP, [$PC-2]      ; swap to our private stack, saving the user one as we go
MOV [$PC-2], $R0       ; save user-code state
MOV $R1, [2]           ; Load syscall number into $R1

...

MOV $PC, [$PC+1]
.WORD syscall-6

You see several of the previous techniques employed here. First, the syscall entry is in the middle of the code fragment. This is because both the prologue and the epilogue needs access to the location where $SP is saved. So we lead with the epilogue, then comes the storage area, finally the entry point with the prologue. This of course means that at the end, we have to jump to the very top to finish the prologue. This is most likely a long enough jump that a pc-relative immediate will not reach it, so a long jump (a move, followed by a word containing the location to jump to) is used. Notice how there are three data values embedded in this code fragment, but only a single jump is used to ensure that none of them gets executed.

SWAP instructions are used to save and restore the system-only stack efficiently. A SWAP instruction is also used to initiate a syscall. This stores the location after the actual swap in memory location 2. This address however is not the return address in this case, instead it contains the syscall number. This is the reason that it's so easy to extract it in the prologue, but also the reason that the return address needs to be incremented in the prologue.

One more thing of note here: we use SWAP to save $SP, but the storage location is in the code segment. This isn't technically self-modifying code as the location is never executed, but very closely related to it. What it means is that this code example would not work from ROM; it can only be used when executing from RAM (well, core in our case). A ROM-able variant can be dreamed up of course, but it would look slightly different and would probably need another reserved zero-page location.

Interrupt handler

The interrupt handler would look rather similar to the syscall handler, but some changes are necessary:

.WORD <interrupt stack> ; interrupt handler save area for $SP

MOV $R1, \[$SP-2\]  ; restore user-code state
MOV $R0, \[$SP-1\]  ; restore user-code state
SWAP \[$PC-3\], $SP ; swap back original stack, saving ours as we go
SWAPI $PC, \[1\]    ; return from interrupt

int\_handler: ; entry point for the interrupt handler

SWAP $SP, \[$PC-5\] ; swap to our private stack, saving the user one as we go
MOV \[$SP-1\], $R0    ; save user-code state
MOV \[$SP-2\], $R1  ; save user-code state

...

MOV $PC, \[$PC+1\]
.WORD int\_handler-4

Things moved around a little for sure, but the entry point is still sandwiched between the epilogue (at the top) and the prologue (below). Here the full user context, both $R0 and $R1 as well as $SP are saved and restored. The interrupt stack is adjusted upon system initialization such that two extra locations are available before it to store $R0 and $R1.

The jump back to the epilogue at the bottom happens similarly to syscalls.

Return from interrupts of course is handled by the SWAPI instruction. Notice how it is the very last instruction before the 'int_handler' label. When this instruction is executed, it stores $PC+1 in location [2], which is the address of the interrupt handler. So the next time around an interrupt occurs, we pick up execution at the right place.

Page -1

Strange name for sure, but what happens if the memory-immediate addressing mode is used with a negative immediate value? The value gets sign-extended and used as the address for the operation. This means, that the last few entries of the address space can be accessed with the same ease as the 0-page locations. The highest 32 addresses to be precise. These locations are ideal for I/O peripherals: they are too high for RAM, they can be accessed without extra gymnastics and I/O has to live somewhere.

Outro

This was a looooong article. Sorry about that. Hopefully, if you're reading this you either haven't fallen asleep or have awoken refreshed and ready for new adventures.

I have an instruction set simulator, and assembler and a disassembler coded up in Python for this processor. It is checked in at https://github.com/andrastantos/the\_d\_machine, if you want to check it out.

In the next installment, I will to talk about how I intend to implement the instruction set described here (the fancy word for it is the 'micro-architecture').

Till that time, see you and have a nice day!