Instruction formats and expanding opcodes

Why it exists

An instruction is a single binary word, so everything the processor needs to know must be packed into its bits: which operation, which operands, which addressing mode. How many bits each field gets is a design trade-off: more opcode bits mean more operations, more register bits mean more registers, more address bits mean more memory can be named directly. Questions on this topic turn that trade-off into arithmetic: compute a field width, a range, or how many instructions fit. The expanding opcode technique, where a rarely needed long opcode is hidden inside the bits that another instruction uses for an address, is one of the most repeated numerical problems in the subject.

Prerequisites

You need the classification of instructions by their number of addresses from ISA design, and binary arithmetic from number systems.

Precise definitions

Instruction format. The division of the instruction word into fields: an opcode (which operation), zero to three operand specifiers (registers or memory addresses), possibly an addressing-mode field and an immediate or displacement constant. The same machine may have several formats, told apart by the opcode.

Field widths.

• Opcode: with $n$ different operations and a fixed-size opcode field, $\lceil \log_2 n \rceil$ bits.
• Register specifier: $\lceil \log_2 r \rceil$ bits for $r$ registers.
• Memory address: $\lceil \log_2 M \rceil$ bits to name one of $M$ addressable units directly.
• Immediate or offset: $k$ bits give a signed range $-2^{k-1}$ to $2^{k-1} - 1$ (2's complement).
• Instruction length = sum of the fields. Lengths are usually rounded to bytes or words, and unused bits are left as padding or used for extra opcode bits.

Fixed-length formats (a MIPS-style example, 32 bits). The widths below are those of the classic textbook MIPS architecture:

Five bits name one of 32 registers. The R-format instructions share opcode 0 and are told apart by the 6-bit function field.

Branch and jump reach. In the I format the 16-bit signed field is a word offset from the next instruction: with 4-byte instructions the reach is $-2^{15}$ to $2^{15} - 1$ words, that is $-128$ KB to $+128$ KB $- 4$ bytes around the branch. The J format gives a 26-bit word address, i.e. $2^{26}$ words $= 2^{28}$ bytes $= 256$ MB; the top bits of the new PC come from the current PC, so a jump stays inside a 256 MB region.

Variable-length formats. Instructions of different sizes (for example 1 to 15 bytes in x86) give compact code and many addressing modes, but the length is only known after decoding the first bytes, which complicates fetch and pipelining.

Expanding opcodes. Suppose the instruction word has $W$ bits and every address field has $a$ bits. If all instructions had two addresses there would be $2^{W - 2a}$ opcodes. Use only some of them for two-address instructions and keep the unused opcode values as escape codes: an escape tells the decoder that the opcode continues into the first address field, which therefore no longer holds an address. Each stage multiplies the number of available opcodes by $2^a$:

$N_2 = 2^{W-2a},\qquad N_1 = (N_2 - n_2)\,2^{a},\qquad N_0 = (N_1 - n_1)\,2^{a},$

where $n_2$ and $n_1$ are the numbers of two-address and one-address instructions actually defined. Then $N_1$ is the number of one-address opcodes available and $N_0 = (N_1 - n_1)\,2^a$ is the maximum number of zero-address instructions. The formulas require that each count is not negative ($n_2 \le N_2$, $n_1 \le N_1$). The idea works because the decoder reads the opcode left to right: a pattern that starts with a used two-address opcode is that instruction, while an escape pattern means "keep reading".

What the decoder needs. The code must be prefix-free: no opcode is the beginning of another one. The escape construction guarantees this, and it uses all patterns exactly once when no opcode is wasted.

How it works

For $W = 8$ and $a = 2$: $N_2 = 2^{8-4} = 16$ two-address opcodes. Use 15 of them. The unused pattern 1111 is an escape, giving $(16 - 15) \times 2^2 = 4$ one-address opcodes. Use 3. The remaining one is a second escape giving $(4 - 3) \times 2^2 = 4$ zero-address opcodes. The animation builds the patterns step by step; an x marks an address bit.

8-bit instruction, 2-bit address fields

[ opcode: 4 bits ][ addr 1: 2 ][ addr 2: 2 ]

The C program below decodes every one of the 256 words under this scheme and counts how many belong to each format: 240, 12 and 4, which add up to exactly 256 with no overlaps and no gaps.

Worked examples

#include <stdio.h>
 
/* decode an 8-bit instruction of the expanding-opcode scheme: 2-bit address fields,
   0000..1110 two-address, 111100..111110 one-address, 111111xx zero-address */
static const char *classify(unsigned w, int *index) {
    unsigned top = w >> 4;
    if (top < 15) { *index = (int)top; return "two-address"; }
    unsigned mid = (w >> 2) & 3;
    if (mid < 3) { *index = (int)mid; return "one-address"; }
    *index = (int)(w & 3);
    return "zero-address";
}
 
int main(void) {
    int count[3] = {0, 0, 0};
    for (unsigned w = 0; w < 256; w++) {
        int idx;
        const char *c = classify(w, &idx);
        count[c[0] == 't' ? 0 : c[0] == 'o' ? 1 : 2]++;
    }
    printf("words decoding as two-address: %d (15 opcodes x 16 address combinations)\n", count[0]);
    printf("words decoding as one-address: %d (3 opcodes x 4)\n", count[1]);
    printf("words decoding as zero-address: %d (4 opcodes)\n", count[2]);
    printf("total %d of 256\n", count[0] + count[1] + count[2]);
    int idx;
    const char *c = classify(0xF6, &idx);
    printf("0xF6 = 11110110 is %s instruction number %d\n", c, idx);
    c = classify(0xFE, &idx);
    printf("0xFE = 11111110 is %s instruction number %d\n", c, idx);
    c = classify(0x5A, &idx);
    printf("0x5A = 01011010 is %s instruction number %d\n", c, idx);
    /* the 16-bit example: 6-bit address fields, 14 two-address, 31 one-address */
    long two = 14, one = 31;
    long left_for_one = (16 - two) * 64;
    long left_for_zero = (left_for_one - one) * 64;
    printf("16-bit word, 6-bit addresses: %ld one-address codes available, %ld zero-address codes left\n", left_for_one, left_for_zero);
    return 0;
}

words decoding as two-address: 240 (15 opcodes x 16 address combinations)
words decoding as one-address: 12 (3 opcodes x 4)
words decoding as zero-address: 4 (4 opcodes)
total 256 of 256
0xF6 = 11110110 is one-address instruction number 1
0xFE = 11111110 is zero-address instruction number 2
0x5A = 01011010 is two-address instruction number 5
16-bit word, 6-bit addresses: 128 one-address codes available, 6208 zero-address codes left

Cheat box

Traps and GATE patterns

Connections

The number of address fields in each format comes from the ISA class in instruction set architecture, and the mode bits and displacement fields determine the addressing modes available. Fixed-length formats are central to the RISC philosophy. The control unit's first job is to decode these fields, which is a decoder feeding the control logic.

PYQs

Consider a processor that has 16 general purpose
registers and it uses 2-byte instruction format for all
its instructions. Variable-sized opcodes are
permitted. There are three different types of
instructions; M-type, R-type, and C-type. Each M-
type instruction has 2 register operands and a 6-bit
immediate operand. Each R-type instruction has 3
register operands. Each C-type instruction has a
register operand and a 6-bit offset value. If there are
2 unique M-type opcodes and 7 unique R-type
opcodes, which one of the following options gives
the maximum number of unique opcodes possible
for C-type instructions?

A processor has 64 general-purpose registers and
50 distinct instruction types. An instruction is
encoded in 32-bits. What is the maximum number
of bits that can be used to store the immediate
operand for the given instruction?

A processor with 16 general purpose registers uses
a 32-bit instruction format. The instruction format
consists of an opcode field, an addressing mode
field, two register operand fields, and a 16-bit
scalar field. If 8 addressing modes are to be
supported, the maximum number of unique
opcodes possible for every addressing mode is

A processor uses a 32-bit instruction format and
supports byte-addressable memory access. The
ISA of the processor has 150 distinct instructions.
The instructions are equally divided into two
types, namely R-type and I-type, whose formats
are shown below.
R-type Instruction Format:

I- type Instruction Format:

In the OPCODE, 1 bit is used to distinguish between
I-type and R-type instructions, and the remaining
bits indicate the operation. The processor has 50
architectural registers, and all register fields in the
instructions are of equal size.
Let X be the number of bits used to encode the
UNUSED field, Y be the number of bits used to
encode the OPCODE field, and Z be the number of
bits used to encode the immediate value/address
field The value of X + 2Y + Z is
.

A processor has 64 registers and uses 16-bit
instruction format. It has two types of instructions:
I-type and R-type. Each I-type instruction contains
an opcode, a register name, and a 4-bit immediate
value. Each R-type instruction contains an opcode
and two register names. If there are 8 distinct I-type
opcodes, then the maximum number of distinct R-
type opcodes is
.

A processor has 16 integer registers (R0, R1, ....,
R15) and 64 floating point registers (F0, F1, ....,
F63). It uses a 2-byte instruction format. There are
four categories of instructions: Type-1, Type-2,
Type-3 and Type-4. Type-1 category consists of four
instructions, each with 3 integer register operands
(3Rs). Type-2 category consists of eight instructions,
each with 2 floating point register operands (2Fs).
Type-3 category consists of fourteen instructions,
each with one integer register operand and one
floating point register operand (1R+1F). Type-4
category consists of N instructions, each with a
floating-point register operand (1F). The maximum
value of N is
.

A processor has 40 distinct instructions and 24
general purpose registers. A 32-bit instruction word
has an opcode, two register operands and an
immediate operand The number of bits available for
the immediate operand field is
.

Consider a Processor with 64 registers and an
instruction set of size twelve. Each instruction has
five distinct fields, namely, opcode, two source
register identifiers, one destination register
identifier, and a twelve-bit immediate value. Each
instruction must be stored in memory in a byte
aligned fashion. If a program has 100 instructions,
the amount of memory (in bytes) consumed by the
program text is
.

For computers based on three-address instruction
formats, each address field can be used to specify
which of the following:
S1: A memory operand
S2: A processor register
S3: An implied accumulator register

A machine has a 32-bit architecture, with 1-word
long instructions. It has 64 registers, each of which
is 32 bits long. It needs to support 45 instructions,
which have an immediate operand in addition to
two register operands. Assuming that the
immediate operand is an unsigned integer, the
maximum value of the immediate operand is

.

A CPU has 24-bit instructions. A program starts at
address 300 (in decimal). Which one of the
following is a legal program counter (all values in
decimal)?

Self-check

Revision card

References