Instruction Sets and Formats

An instruction set architecture (ISA) is the contract between hardware and software: the instructions, registers, data types and addressing modes a programmer (or compiler) can use.

What an instruction contains

Every instruction has an opcode (which operation) and usually operand fields (where the data is: a register number, a memory address, or a constant). The number of bits for each field follows from how many choices it must express:

• k distinct opcodes need ⌈log₂ k⌉ bits;
• r registers need ⌈log₂ r⌉ bits per register field;
• a memory of 2ⁿ addressable units needs n bits for a full address.

Example: a 32-bit instruction holds an opcode, two register fields and an immediate constant. With 70 instructions and 50 registers, the opcode needs ⌈log₂ 70⌉ = 7 bits and each register field ⌈log₂ 50⌉ = 6 bits, leaving 32 − 7 − 2 × 6 = 13 bits for the immediate.

Number of addresses per instruction

The same computation, X = (A + B) × (C − D), looks different depending on how many operands an instruction names:

Fewer addresses mean shorter instructions but more of them. A stack machine evaluates an expression in postfix order (A B + C D − ×), which is how Java bytecode and many calculators work:

def stack_program(postfix, target):
    code, stack = [], []
    for token in postfix.split():
        if token in "+-*/":
            code.append({"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}[token])
            b, a = stack.pop(), stack.pop()
            stack.append(f"({a}{token}{b})")
        else:
            code.append(f"PUSH {token}")
            stack.append(token)
    code.append(f"POP {target}")
    return code, stack[0]

code, expr = stack_program("A B + C D - *", "X")
print("; ".join(code))
print(len(code), "instructions compute", expr)

PUSH A; PUSH B; ADD; PUSH C; PUSH D; SUB; MUL; POP X
8 instructions compute ((A+B)*(C-D))

Fixed and variable formats

• Fixed-length instructions (all 32 bits, as in RISC-V and ARM) are simple to fetch and decode, and suit pipelining.
• Variable-length instructions (1 to 15 bytes in x86) save memory and allow rich operands, but decoding is harder.

Expanding opcodes

When instructions with fewer operands have spare bits, those bits can extend the opcode. Suppose instructions are 12 bits long and an address field is 4 bits:

• A 2-address instruction is opcode (4 bits) + 2 addresses: up to 16 opcodes.
• If only 13 two-address instructions are defined, the remaining 3 opcode patterns can each be followed by another 4 bits of opcode, giving 3 × 16 = 48 one-address instructions.
• If only 40 one-address instructions are used, the remaining 8 patterns can each be extended once more, giving 8 × 16 = 128 zero-address instructions.

The rule: each unused pattern at one level becomes 2^{(field width)} patterns at the next level.

RISC and CISC

Modern x86 processors translate CISC instructions internally into RISC-like micro-operations.

Practice questions

code, stack = [], []
for t in "A B * C +".split():
    code.append({"*": "MUL", "+": "ADD"}.get(t, f"PUSH {t}"))
code.append("POP X")
print(len(code))