Gb_gates RISC

Gb_gates RISC is a very small hypothetical microprocessor created by Donald Knuth. He has created a software implementation of this microprocessor described as a circuit of logic gates.

The semantics of the processor is described in the gb_gates program of The Stanford Graphbase (SGB), and that program also gives the implementation as a circuit of logic gates.

Programming

The microprocessor cannot write memory, so the only mutable state is the few CPU registers. The processor is connected only to a read-only memory, which contains instructions and read-only data. The read-only memory is made of 16-bit words, a single word is read each time. The address is also a 16-bit word, so there could be at most 65536 words of memory, although in most cases you would have fewer than that.

There are up to 16 general purpose registers, each storing a 16-bit word, plus four status registers. However, the first general purpose register is the program counter, which is automatically incremented for each instruction. Further, smaller variants of the processor exist that have fewer registers, in which case the extra registers always read as zero.

All instructions are either one word or two word long, two word only if the instruction includes a 16-bit immediate argument. The instruction set is very uniform (that's why it's called a RISC after all), with the same addressing modes supported for each instruction. Most instructions are one word long, and contain four fields: a 6 bit long opcode, a 4 bit long destination register selector, a 2 bit long addressing mode, and a 4 bit long source field that together with the addressing mode selects the source.

The instructions use an input/output operand, which can be any register, and a second input operand, which can be in any of five addressing modes. The addressing modes are:

1. any general purpose register, selected by the source field;
2. a memory load with the address given by any general purpose register, selected by the source field;
3. a signed 4-bit immediate encoded in the source field;
4. the destination register added to a signed 4-bit immediate encoded in the source field;
5. a 16-bit immediate argument, encoded in the word after the instruction.

When the instruction is executed, the CPU computes the second source as above, as well as reads the first source from the destination register, then computes the one word long result, then stores that resulting word to the destination register, unless that register is one of the nonexistant registers that are always read as zero. The sign and zero status flags are also always set from the result, indicating whether that result is zero, equal to 0x8000, any other positive value, or any other negative value. The arithmetic and shift instrucions also set the carry and overflow flags; the bitwise and conditional move and instructions leave those two flags unchanged.

The possible operations are:

1. 16 different conditional move operations that set the result to the second source or leaves it unchanged as the first source, based on any of the 16 possible combinations of the four values of the sign and zero flags;
2. 16 different conditional move operations similar to the above but using the carry and overflow registers;
3. 16 bitwise logical instructions, one for each two-argument boolean function;
4. 4 arithmetic instructions: add, add with carry, subtract, subtract with borrow;
5. 8 shift instructions;
6. a call instruction that jumps to the address given by the second operand, but gives the return address as the result.

The conditional move instructions can be used as branch instructions when the destination register is the program counter. The subtract and subtract with borrow instructions treat the carry flag as a borrow flag like x86 does. The shift and call instructions ignore the first source operand.

Implementation

The program creates an implementation of the processor as an abstract logical circuit. The circuit is built of logical gates that operate on individual bits, as well as latches that delay a bit by one clock cycle, to provide persistent state. The input of the processor is the value read from the ROM and a RESET signal, the output is the address to read from memory in the next cycle.

The circuit doesn't contain the read-only memory, that part must be connected to the processor externally. The memory is synchronous with the processor, so it must read any memory cell in a single clock cycle.