Instruction Set Design

An instruction tells the processor what operation to perform and where its operands come from. A sequence of instructions forms a program. The instruction-set architecture (ISA) defines the binary contract between software and the processor.

Do not equate an opcode with an instruction. The opcode says what operation to perform; the remaining fields say which values participate and how to find them.

Operand-Address Formats

For the expression $X=(A+B)\times(C-D)$:

Short instructions occupy less memory and can be fetched with fewer bytes. They may also require more instructions, so total program size and execution time depend on the complete encoding rather than one instruction in isolation.

Fixed-Length Block-Code Encoding

A processor can execute an operation only after its opcode has a unique binary pattern. With $K$ opcode bits, block coding offers at most $2^K$ patterns. A $K$-to-$2^K$ decoder can activate one instruction line.

Three bits encode exactly eight operations. Adding a ninth operation requires a wider fixed opcode or a different encoding scheme.

Expanding Opcodes

An expanding opcode reuses an otherwise unused short opcode as a prefix for a longer opcode. This trades some operand-field combinations for additional operations with fewer explicit operands.

Consider a 16-bit format with a 4-bit opcode followed by three 4-bit addresses. It can encode sixteen three-address operations. If only fifteen are used, prefix 1111 can signal that the next 4-bit field extends the opcode:

ordinary three-address: [ opcode 4 ][ A1 4 ][ A2 4 ][ A3 4 ]
two-address extension:  [ 1111 ][ opcode 4 ][ A1 4 ][ A2 4 ]
one-address extension:  [ 1111 ][ 1111 ][ opcode 4 ][ A1 4 ]
zero-address extension: [ 1111 ][ 1111 ][ 1111 ][ opcode 4 ]

The exact allocation is a design choice. The rule is that decoding must be unambiguous.

Capacity method

Count complete bit patterns rather than merely “unused names.” An $L$-bit instruction space contains $2^L$ encodings. An instruction with $a$ address bits consumes $2^a$ complete encodings because its address can vary independently.

Example 1: one- and zero-address instructions

A byte-addressable 64 B memory needs 6 address bits. With a 4-bit opcode, there are 16 short opcode patterns. Ten are used for one-address instructions, leaving six prefixes. Each prefix can absorb all $2^6$ former address patterns:

zero-address instructions.

Example 2: three- to two-address expansion

A 22-bit instruction has one 4-bit register field, two 6-bit memory-address fields, and therefore a 6-bit three-address opcode. Of 64 possible opcodes, 62 are used. Each of the two remaining prefixes can extend through one 6-bit field:

two-address operations.

Example 3: mixed 58 and 25 operations

A processor needs 58 three-address operations and 25 two-address operations; each address selects one of 16 locations.

• Address width: $\log_2 16=4$ bits.
• Three-address opcode width: $\lceil\log_2 58\rceil=6$ bits.
• Fixed instruction length: $6+3(4)=18$ bits.
• Unused 6-bit prefixes: $64-58=6$.
• Two-address capacity: $6\times2^4=96$, enough for 25 operations.
• Two-address opcode width: $6+4=10$ bits.

Example 4: count the complete 11-bit space

An 11-bit format has 4-bit address fields, five two-address instructions, and 32 one-address instructions:

zero-address encodings remain.

Huffman Opcode Encoding

If opcode frequencies are known, a prefix-free Huffman code minimizes the weighted average code length:

1. Create one leaf for each operation and label it with its probability.
2. Repeatedly combine the two smallest unmarked probabilities.
3. Label the two branches 0 and 1.
4. Read each code from root to leaf.

Frequent instructions get short codes; rare instructions get long codes. The source example assigns codes of lengths 2–4 to operations such as LOAD, STORE, SHIFT, NOT, JUMP, HALT, AND, and ADD.

For the characters in Mississippi, frequencies are $m:1$, $p:2$, $s:4$, and $i:4$. One valid Huffman tree gives lengths 3, 3, 2, and 1:

The advantage is minimum expected bits. The disadvantages are variable boundaries, serial prefix recognition, and a more complex decoder. Practical instruction sets usually favor regular parallel decoding even when a pure Huffman code is denser.

Addressing Modes

An addressing mode defines how an instruction obtains an operand or its effective address ($EA$).

Assume the instruction contains value/address $250$, register $R2=1000$, word size $k=4$, and $PC=400$:

The terms indexed and base-relative can use identical addition hardware. Their distinction is the programming interpretation and typical field width. Auto-indexing means the register is modified as part of operand access.

Instruction Classes

Data transfer

MOV, LOAD, STORE, stack push/pop, and register exchange move values without changing their bit patterns. The datapath still needs source selection, a route, and a destination write enable.

Arithmetic and logic

ADD, SUB, MUL, DIV, AND, OR, NOT, shifts, and rotates select ALU or iterative arithmetic functions. These instructions usually update condition flags.

System control and I/O

System instructions change privileged state, interrupt masks, or processor modes. Separate-I/O architectures use explicit input/output instructions; memory-mapped I/O uses ordinary load/store operations to special addresses.

Program control

• unconditional branch: BR NEXT;
• conditional branch: test a flag and possibly replace $PC$;
• counted branch: decrement a register and branch until a condition;
• subroutine call: save a return address and branch;
• return: restore the saved address;
• trap: request a synchronous software interrupt.

Status Register and Conditional Control

For four-bit addition 1111 + 0001 = 1 0000, $Z=1$, $C=1$, $N=0$, and $V=0$: unsigned 15 overflowed to zero, while signed $-1+1=0$ is valid.

An external interrupt resembles a hardware-generated subroutine call but may arrive asynchronously. The processor finishes or safely suspends current work, saves $PC$ and required status/register state, loads an interrupt-vector address, runs the service routine, then restores state before returning.

Instruction Execution at Register-Transfer Level

The foundation cycle becomes concrete when fields and addressing modes are included:

Not every instruction uses every phase. A register-register ADD needs no data-memory operand access; a STORE has no ALU result write-back; a taken branch writes $PC$.

Self-Check

1. Why is a zero-address instruction not an instruction with no operands?
2. A fixed opcode has 37 operations. What minimum opcode width is required?
3. With $R3=1200$ and displacement $=-24$, what is the base-relative effective address?
4. Why can $C=1$ and $V=0$ for the same addition?