SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 7

CS Fundamentals for Placements · Lesson 7 of 90 · 19 min

Instruction set architecture and addressing modes

ISAinstruction formatopcodeoperand0/1/2/3-address instructionsstack machineaddressing modes (immediate, register, direct, indirect, register indirect, indexed, base-register, PC-relative, auto-increment/decrement)effective address numericalsRISC vs CISCload-store architecturex86ARMRISC-Vreading a small assembly program

These are the notes for CS Fundamentals for Placements, episode 7. Last episode you built a tiny CPU that fetches, decodes and executes. Now you design the language it understands, one problem at a time: the instruction set architecture (ISA), opcodes and operands, instruction formats and field-width numericals, 3, 2, 1 and 0-address instructions and the stack machine, every addressing mode (immediate, register, direct, indirect, register indirect, indexed, base-register, PC-relative, auto-increment and auto-decrement) with effective-address numericals, RISC vs CISC and the load-store architecture, the real ISAs x86, ARM and RISC-V, how to read a small assembly program produced by a real compiler, and how a function call works: the return address, the stack frame and the calling convention. Every term is explained in plain words, and there is a full glossary at the end.

All outputs below are real. Every Python program was run with Python 3.13. The assembly is real output of gcc 13.3.0 on an x86-64 Linux machine, and the bytes come from objdump on the same machine. The tiny CPUs in the demos are made up for teaching.

A quick refresher from earlier episodes: a bit is one 0 or 1, a byte is 8 bits. Memory (RAM) is a long row of numbered boxes; a box's number is its address. A register is a tiny, very fast storage box inside the CPU. The program counter (PC) holds the address of the next instruction, and the instruction register (IR) holds the one running now. The accumulator (ACC) is the one register that holds the running result in a simple CPU.

The seven problems

Problem What it teaches
Which commands exist? ISA, opcode, operand, ISA vs microarchitecture
Fit it into bits Instruction format, fields, opcode and register field widths, immediate
How many addresses? 3, 2, 1 and 0-address instructions, stack machine, postfix
Where is the data? Addressing modes, effective address (EA), EA numericals
Simple or rich instructions? CISC vs RISC, load-store architecture, x86, ARM, RISC-V
Read real assembly gcc output, modes in real code, variable-length bytes, a PC-relative jump
Call a function Return address, stack, stack frame, calling convention

Problem 1: which commands exist? (ISA, opcode, operand)

A CPU is a circuit. It understands only patterns of bits. So before anyone writes a compiler, someone must decide which commands exist and what each bit pattern means. Think of a restaurant.

A restaurant A CPU
The menu: you can only order what's on it The ISA (instruction set architecture): every command the CPU understands
The dish name, "paneer tikka" The opcode (operation code): what to do, like ADD, LOAD, JUMP
The details, "table 4, extra spicy" The operands: what to do it on: a register, a memory address or a plain number
  • An instruction is one command the CPU understands, for example ADD R1, R2 or LOAD 7.
  • The ISA is the contract between software and hardware. It lists: the instructions, the registers a program can use, the data types (8-bit, 32-bit integers, floats ...), the instruction formats (how bits are laid out), the addressing modes (how an instruction finds its data), and how memory is addressed.
  • A compiler only needs the ISA. It never needs to know how the chip is built inside.

ISA vs microarchitecture

Two restaurants can serve the same menu with very different kitchens.

Means Example
ISA What the CPU promises: the instructions and their meaning "ADD R1, R2 adds R2 to R1"
Microarchitecture How one particular chip keeps that promise: its circuits, pipeline, caches, speed one chip does the ADD in 1 cycle, another in 3
  • Two chips with the same ISA run the same program file (the same machine code).
  • A program compiled for one ISA will not run on a chip with a different ISA. That's why apps are built separately for different processors.

Problem 2: fit it into bits (instruction formats)

Our CPU reads 16 bits at a time, so every instruction must fit in 16 bits. We split them into parts. Each part is a field; the layout of fields is the instruction format.

| opcode: 4 bits | address: 12 bits |
  • 4 bits can count 2⁴ = 16 different opcodes.
  • 12 bits can name 2¹² = 4096 addresses, 0 to 4095.
  • General rule: n bits give 2ⁿ different choices.

The demo: encode and decode, then try address 5000

Two bit tricks are used. << (left shift) slides bits to the left: 2 << 12 puts the number 2 into the top 4 bits of a 16-bit word. | (bitwise OR) combines two bit patterns. >> (right shift) slides bits right, and & 0xFFF (AND with a mask) keeps only the low 12 bits. A mask is a bit pattern used to keep some bits and clear others; 0xFFF is hexadecimal for twelve 1s.

# a 16-bit instruction: 4-bit opcode | 12-bit address
OPS = ["LOAD", "STORE", "ADD", "SUB", "JMP", "JZ", "HALT"]

def encode(op, addr):
    code = OPS.index(op)
    if addr >= 2 ** 12:
        raise ValueError(f"address {addr} needs more than 12 bits")
    return (code << 12) | addr

def decode(word):
    return OPS[word >> 12], word & 0xFFF

for op, addr in [("LOAD", 7), ("ADD", 8), ("STORE", 4095)]:
    w = encode(op, addr)
    print(f"{op:5} {addr:4} -> {w:016b} -> {decode(w)}")

print(encode("LOAD", 5000))

Output:

LOAD     7 -> 0000000000000111 -> ('LOAD', 7)
ADD      8 -> 0010000000001000 -> ('ADD', 8)
STORE 4095 -> 0001111111111111 -> ('STORE', 4095)
Traceback (most recent call last):
  ...
    raise ValueError(f"address {addr} needs more than 12 bits")
ValueError: address 5000 needs more than 12 bits
  • The first 4 bits are the opcode (0010 = 2 = ADD), the last 12 are the address.
  • {w:016b} prints w in binary, 16 digits wide with leading zeros.
  • The failure: memory is bigger than 4096 boxes, and the instruction has no room to name address 5000. A field's width limits its reach. Addressing modes (Problem 4) fix this by letting the address live in a register instead.

Instruction format numericals

  • N instructions → the opcode needs ⌈log₂ N⌉ bits (log base 2, rounded up). ⌈x⌉ means "round up to a whole number".
  • R registers → each register field needs ⌈log₂ R⌉ bits.
  • An immediate is a constant number stored right inside the instruction (for example the 5 in ADD R1, #5). Whatever bits are left over usually hold it.

Worked example. A CPU has 40 instructions and 24 registers. A 32-bit instruction holds an opcode, two register fields and an immediate.

Field Why Bits
Opcode 2⁵ = 32 < 40 ≤ 64 = 2⁶ 6
Register 1 2⁴ = 16 < 24 ≤ 32 = 2⁵ 5
Register 2 same 5
Immediate 32 − 6 − 5 − 5 16

The classic trap is rounding down: 5 bits give only 32 opcodes, not 40.

Problem 3: how many addresses? (3, 2, 1 and 0-address instructions)

The obvious wish: every instruction names three things, two sources and a destination. ADD T1, A, B means T1 = A + B. But with 12-bit addresses, three addresses plus a 4-bit opcode is 40 bits. It doesn't fit in 16. So we shrink. Here is X = (A + B) × (C + D) four ways:

Style Meaning of ADD Code for X = (A + B) × (C + D) Count
3-address ADD D, S1, S2: D = S1 + S2 ADD T1, A, B ADD T2, C, D MUL X, T1, T2 3
2-address ADD D, S: D = D + S (first operand is source and destination) MOV T, A ADD T, B MOV X, C ADD X, D MUL X, T 5
1-address ADD S: ACC = ACC + S (the accumulator is the hidden operand) LOAD A ADD B STORE T LOAD C ADD D MUL T STORE X 7
0-address ADD: pop two values, push the sum (operands come from a stack) PUSH A PUSH B ADD PUSH C PUSH D ADD MUL POP X 8

Trade-off: fewer addresses per instruction → shorter instructions, but more of them. MOV (move) copies a value; T, T1, T2 are temporary variables.

The stack machine, live

A stack is a pile, like a pile of plates: you push onto the top and pop from the top only. Last in, first out (LIFO). A machine whose arithmetic takes its operands from a stack is a stack machine, and its instructions are 0-address instructions.

# 0-address code for X = (A + B) * (C + D)
env = {"A": 2, "B": 3, "C": 4, "D": 5}
prog = ["PUSH A", "PUSH B", "ADD", "PUSH C", "PUSH D",
        "ADD", "MUL", "POP X"]
stack = []
for ins in prog:
    op, *arg = ins.split()
    if op == "PUSH":
        stack.append(env[arg[0]])
    elif op == "POP":
        env[arg[0]] = stack.pop()
    else:                                  # ADD or MUL
        b, a = stack.pop(), stack.pop()
        stack.append(a + b if op == "ADD" else a * b)
    print(f"{ins:7} stack = {stack}")
print("X =", env["X"])

Output:

PUSH A  stack = [2]
PUSH B  stack = [2, 3]
ADD     stack = [5]
PUSH C  stack = [5, 4]
PUSH D  stack = [5, 4, 5]
ADD     stack = [5, 9]
MUL     stack = [45]
POP X   stack = []
X = 45
  • (2 + 3) × (4 + 5) = 5 × 9 = 45. ADD and MUL never named an address.
  • The order A B + C D + × is postfix notation (reverse Polish notation): the operator comes after its operands. Converting a normal (infix) expression to postfix gives the stack code directly.
  • Note b, a = stack.pop(), stack.pop(): the top is the second operand. For SUB and DIV the order matters.
  • Real use: the Java Virtual Machine runs bytecode on a stack-based architecture with an operand stack; its iadd instruction pops two ints and pushes their sum (source below).

Problem 4: where is the data? (addressing modes)

Two open problems: addresses that don't fit in the instruction, and arrays.

The failing attempt: an array with direct addressing only

An array of 1000 numbers sits at addresses 500 to 1499. With direct addressing every instruction names the exact address, so summing it needs one ADD per element.

mem = {500 + i: i + 1 for i in range(1000)}   # array 1..1000

# attempt: direct addressing only, one ADD per element
prog = ["LOAD 500"] + [f"ADD {500 + i}" for i in range(1, 1000)]
print("direct only:", len(prog), "instructions")
print(prog[:3], "...", prog[-1])

# fix: register indirect + auto-increment, in a loop
R0, R1, R2 = 0, 500, 1000      # sum, pointer, count
while R2:
    R0 += mem[R1]; R1 += 1      # ADD R0, (R1)+
    R2 -= 1                     # DEC R2 ; JNZ loop
print("loop: 6 instructions, sum =", R0)

Output:

direct only: 1000 instructions
['LOAD 500', 'ADD 501', 'ADD 502'] ... ADD 1499
loop: 6 instructions, sum = 500500
  • Why it fails: a million numbers need a million instructions, and the program must change whenever the array moves.
  • The fix: keep the address in a register (R1), use it, and add 1. The loop is 6 instructions however long the array: MOV R1, #500, MOV R2, #1000, MOV R0, #0, ADD R0, (R1)+, DEC R2, JNZ loop. DEC subtracts 1; JNZ jumps if the result was not zero. 1 + 2 + ... + 1000 = 1000 × 1001 / 2 = 500,500.

Real-life example: telling a delivery boy where to go

What you tell him Addressing mode
"Here's the parcel itself" (no trip) Immediate: the value is inside the instruction
"Go to house 42" Direct (absolute): the exact address is in the instruction
"House 42 has a note with the real address" (two trips) Indirect: the instruction holds the address of a box that holds the address
"Third house from where you're standing" PC-relative: an offset from the current position, the PC

All the modes

The effective address (EA) is the memory address where the operand actually sits. An addressing mode is a rule for finding the operand (and its EA).

Mode Syntax used here Effective address / operand Memory reads for the operand Typical use
Immediate LOAD #100 operand = 100 itself; no EA 0 constants: i = 0
Register LOAD R1 operand = value in R1; no EA 0 local variables in registers
Direct (absolute) LOAD 100 EA = 100 1 global variables at fixed addresses
Indirect LOAD @200 EA = mem[200] 2 pointers stored in memory
Register indirect LOAD (R1) EA = R1 1 pointers held in registers: *p
Indexed LOAD 500(R2) EA = 500 + R2 (fixed address + index register) 1 array element a[i]
Base-register (base + displacement) LOAD 4(BR) EA = BR + 4 (base register + small displacement) 1 fields of a record, locals in a stack frame, relocatable programs
PC-relative LOAD 12(PC) EA = PC + 12, PC = address of the next instruction 1 jumps and branches, position-independent code
Auto-increment LOAD (R1)+ EA = R1, then R1 = R1 + 1 1 walking forward through an array
Auto-decrement LOAD −(R1) first R1 = R1 − 1, then EA = R1 1 walking backwards, pushing onto a stack
  • A register that holds an address is called a pointer. Register indirect fixes the 12-bit problem: a 64-bit register can point anywhere in memory.
  • Indexed vs base-register: both compute "something + register". In indexed mode the instruction holds the big starting address and the register holds the small, changing index. In base-register mode the register holds the big starting address (the base) and the instruction holds a small fixed displacement (offset). Moving a whole block of data only means changing the base register.
  • In auto-increment/decrement on a real CPU, the step is the operand size (4 for an int), not always 1.

The demo: every mode on one memory

mem = {100: 7, 200: 300, 300: 42, 504: 9, 1012: 11}
R1, R2, BR = 300, 4, 500    # registers (BR = base register)
PC = 1000                   # already points to the next instruction

def show(mode, ea, value):
    print(f"{mode:26} EA={str(ea):5} value={value}")

show("immediate  LOAD #100", None, 100)
show("register   LOAD R1", None, R1)
show("direct     LOAD 100", 100, mem[100])
show("indirect   LOAD @200", mem[200], mem[mem[200]])
show("reg-indir  LOAD (R1)", R1, mem[R1])
show("indexed    LOAD 500(R2)", 500 + R2, mem[500 + R2])
show("base-reg   LOAD 4(BR)", BR + 4, mem[BR + 4])
show("PC-rel     LOAD 12(PC)", PC + 12, mem[PC + 12])
show("auto-inc   LOAD (R1)+", R1, mem[R1]); R1 += 1
print("R1 after auto-increment =", R1)

Output:

immediate  LOAD #100       EA=None  value=100
register   LOAD R1         EA=None  value=300
direct     LOAD 100        EA=100   value=7
indirect   LOAD @200       EA=300   value=42
reg-indir  LOAD (R1)       EA=300   value=42
indexed    LOAD 500(R2)    EA=504   value=9
base-reg   LOAD 4(BR)      EA=504   value=9
PC-rel     LOAD 12(PC)     EA=1012  value=11
auto-inc   LOAD (R1)+      EA=300   value=42
R1 after auto-increment = 301
  • Indirect goes 200 → finds 300 → reads mem[300] = 42: two memory trips. Register indirect reaches 300 straight from R1: one trip.
  • Indexed (500 + 4) and base-register (500 + 4) land on the same 504 here; they differ in who holds what.

Effective address numericals

  1. An instruction at address 2000 is 2 words long and uses PC-relative mode with offset 25 (one address per word). By the time it executes, PC has already moved past it: PC = 2002. EA = 2002 + 25 = 2027.
  2. An int array starts at 1000, each int is 4 bytes, the index register holds 3. EA = 1000 + 3 × 4 = 1012.
  3. LOAD @300, mem[300] = 800, mem[800] = 5. EA = 800, value = 5, two memory reads for the operand (three counting the instruction fetch).

Trap: PC-relative adds the offset to the address of the next instruction, not the current one.

Problem 5: simple or rich instructions? (RISC vs CISC)

CISC (Complex Instruction Set Computer) RISC (Reduced Instruction Set Computer)
Idea Many rich instructions; one can do a lot Few simple instructions, each about one cycle
Memory operands Arithmetic may read/write memory directly: ADD [mem], R1 Only LOAD and STORE touch memory (load-store architecture)
Instruction length Variable (different instructions, different sizes) Usually fixed (all the same size)
Decoding Harder Easy
Instructions per program Fewer More
Cycles per instruction Some take many cycles About one; easy to pipeline (overlap instructions)
Registers Fewer, traditionally Many general-purpose registers
Control unit (episode 6) Usually microprogrammed Usually hardwired
Examples x86 ARM, RISC-V

Adding a register to a memory value:

CISC:  ADD [mem], R1          ; one instruction, reads and writes memory

RISC:  LOAD  R2, [mem]        ; memory -> register
       ADD   R2, R2, R1       ; registers only
       STORE R2, [mem]        ; register -> memory

x86, ARM and RISC-V (facts from the sources below)

  • x86 (CISC): began with Intel's 8086, released on 8 June 1978. 8086 instructions were 1 to 6 bytes long, and its ALU instructions can take one operand from memory.
  • ARM (RISC): the company Arm licenses its instruction set and chip designs to other companies, which build their own chips. Its efficiency suits light, battery-powered devices such as smartphones.
  • RISC-V (RISC): begun in 2010 at UC Berkeley. It is open and royalty-free: anyone can implement it without paying for the ISA. It is a load-store architecture, and its base instructions are a fixed 32 bits long.

Problem 6: read real assembly

Assembly language is the ISA written as text: one line = one machine instruction, with names (mnemonics) like mov and add instead of bit patterns. An assembler turns it into machine code. A label like .L3: names an address so jumps can refer to it.

The C function:

int sum(int *a, int n) {
    int s = 0;
    for (int i = 0; i < n; i++)
        s += a[i];
    return s;
}

Command: gcc -O1 -S -masm=intel -fcf-protection=none -fno-asynchronous-unwind-tables sum.c (-S = stop at assembly, -O1 = light optimisation, -masm=intel = Intel syntax: destination first). Real output, with assembler directives (lines starting with a dot, like .file) removed:

sum:
    test    esi, esi
    jle .L4
    mov rax, rdi
    movsx   rsi, esi
    lea rcx, [rdi+rsi*4]
    mov edx, 0
.L3:
    add edx, DWORD PTR [rax]
    add rax, 4
    cmp rax, rcx
    jne .L3
.L1:
    mov eax, edx
    ret
.L4:
    mov edx, 0
    jmp .L1

Line by line (x86-64 registers: rdi, rsi, rax, rcx, rdx are 64-bit; edi, esi, eax, edx are their low 32 bits):

Instruction Meaning Addressing mode
(on entry) the array's address arrives in rdi, n in esi calling convention
test esi, esi / jle .L4 if n ≤ 0, skip the loop register; PC-relative jump
mov rax, rdi rax = pointer to a[0] register
movsx rsi, esi widen n from 32 to 64 bits, keeping the sign (sign extension, episode 3) register
lea rcx, [rdi+rsi*4] rcx = address of a[n] (just past the end); lea = load effective address, it computes the address without reading memory base + scaled index
mov edx, 0 s = 0 immediate
add edx, DWORD PTR [rax] s += the 4-byte int at address rax. An add that reads memory directly: CISC register indirect
add rax, 4 move the pointer to the next int auto-increment, done by hand
cmp rax, rcx / jne .L3 compare (sets flags, episode 6); jump back if not equal PC-relative
mov eax, edx / ret return value goes in eax; return calling convention

DWORD PTR means "a double word", 4 bytes. Notice gcc turned a[i] with i into a moving pointer: same result, fewer operations.

The bytes: variable length and a real PC-relative jump

Command: objdump -d -M intel sum.o (-d = disassemble). Real output (first part):

   0:   85 f6                   test   esi,esi
   2:   7e 1d                   jle    21 <sum+0x21>
   4:   48 89 f8                mov    rax,rdi
   7:   48 63 f6                movsxd rsi,esi
   a:   48 8d 0c b7             lea    rcx,[rdi+rsi*4]
   e:   ba 00 00 00 00          mov    edx,0x0
  13:   03 10                   add    edx,DWORD PTR [rax]
  15:   48 83 c0 04             add    rax,0x4
  19:   48 39 c8                cmp    rax,rcx
  1c:   75 f5                   jne    13 <sum+0x13>
  1e:   89 d0                   mov    eax,edx
  20:   c3                      ret
  • The left column is each instruction's address in hex. Lengths are 2, 2, 3, 3, 4, 5 ... bytes: variable-length instructions, a CISC trademark.
  • jne at 0x1c is 75 f5. 75 = "jump if not equal"; f5 is −11 as a signed byte (two's complement, episode 3). The next instruction is at 0x1e, and 0x1e − 11 = 0x13, exactly where the loop starts. EA = PC (next instruction) + offset: real PC-relative addressing.

Problem 7: call a function (return address, stack frame, calling convention)

A function (subroutine) is reusable code you CALL and that RETurns to where it was called from. CALL 10 jumps to address 10. But how does RET know where to come back to?

The failing attempt: CALL forgets where it came from

mem = {0: "CALL 10", 1: "HALT",
       10: "ADD 5", 11: "CALL 20", 12: "RET",
       20: "ADD 100", 21: "RET"}
PC, ACC, stack = 0, 0, []
while True:
    IR = mem[PC]; PC += 1                  # fetch
    op, *arg = IR.split()
    if op == "CALL":
        # stack.append(PC)       (forgot the return address)
        PC = int(arg[0])
    elif op == "RET":
        PC = stack.pop()
    elif op == "ADD":
        ACC += int(arg[0])
    elif op == "HALT":
        break
    print(f"{IR:8} ACC={ACC:3}  PC={PC:2}  stack={stack}")
print("done, ACC =", ACC)

Output:

CALL 10  ACC=  0  PC=10  stack=[]
ADD 5    ACC=  5  PC=11  stack=[]
CALL 20  ACC=  5  PC=20  stack=[]
ADD 100  ACC=105  PC=21  stack=[]
Traceback (most recent call last):
  ...
    PC = stack.pop()
IndexError: pop from empty list
  • Why it fails: RET has no idea where to go back to. A real CPU would jump to garbage.
  • Why not one register for the way back? Function 10 calls function 20; the second call would overwrite the first return address.
  • The fix: CALL pushes the address of the next instruction, the return address, onto a stack. RET pops it into PC. Replace the commented line with stack.append(PC) # push the return address:
CALL 10  ACC=  0  PC=10  stack=[1]
ADD 5    ACC=  5  PC=11  stack=[1]
CALL 20  ACC=  5  PC=20  stack=[1, 12]
ADD 100  ACC=105  PC=21  stack=[1, 12]
RET      ACC=105  PC=12  stack=[1]
RET      ACC=105  PC= 1  stack=[]
done, ACC = 105

The inner RET pops 12, the outer RET pops 1. LIFO matches nesting perfectly. In a real CPU the stack lives in memory and the stack pointer (SP) register (rsp on x86-64) holds the address of its top.

Real code: add3, a stack frame and a calling convention

int add3(int a, int b, int c) {
    return a + b + c;
}
int main(void) {
    return add3(10, 20, 12);
}

Command: gcc -O0 -S -masm=intel -fcf-protection=none -fno-asynchronous-unwind-tables add3.c (-O0 = no optimisation, so every step is visible). Real output, directives removed; the program exits with status 42:

add3:
    push    rbp
    mov rbp, rsp
    mov DWORD PTR -4[rbp], edi
    mov DWORD PTR -8[rbp], esi
    mov DWORD PTR -12[rbp], edx
    mov edx, DWORD PTR -4[rbp]
    mov eax, DWORD PTR -8[rbp]
    add edx, eax
    mov eax, DWORD PTR -12[rbp]
    add eax, edx
    pop rbp
    ret
main:
    push    rbp
    mov rbp, rsp
    mov edx, 12
    mov esi, 20
    mov edi, 10
    call    add3
    pop rbp
    ret
  • Calling convention: the agreed rules for calls: which registers carry the arguments, where the result goes, who saves which registers. In this output: 1st argument in edi, 2nd in esi, 3rd in edx, result in eax. Caller and callee must agree, or the values land in the wrong place.
  • call add3 pushes the return address and jumps. ret pops it back into the PC.
  • Stack frame: the function's own slice of the stack. push rbp saves the caller's frame pointer (rbp, the register that marks where the current frame starts), and mov rbp, rsp starts a new frame. The arguments are stored at rbp − 4, − 8, − 12: base-register addressing, with rbp as the base and −4 as the displacement. pop rbp restores the caller's frame.
  • A frame typically holds the return address, the saved frame pointer, saved registers and local variables. Each call gets a new frame, which is why recursion works.
higher addresses
   ...   caller's frame
   return address       <- pushed by call
   saved rbp            <- rbp points here after "mov rbp, rsp"
   a  at rbp - 4
   b  at rbp - 8
   c  at rbp - 12
lower addresses (the stack grows down)

Common mistakes (and the real output)

Mistake Real output Fix
Forcing address 5000 into a 12-bit field ValueError: address 5000 needs more than 12 bits Use register indirect or base-register addressing
Summing an array with direct addressing only direct only: 1000 instructions Register indirect + auto-increment in a loop (6 instructions)
CALL without saving the return address IndexError: pop from empty list Push the return address on the stack
PC-relative from the current address EA = 2000 + 25 = 2025 (wrong) PC already = next instruction: 2002 + 25 = 2027
40 opcodes in 5 bits 2⁵ = 32 < 40 ⌈log₂ 40⌉ = 6 bits
Confusing LOAD R1 with LOAD (R1) quiz: 600 instead of 900 R1 = value in R1; (R1) = memory at the address in R1
Popping operands in the wrong order for SUB a - b vs b - a The top of the stack is the second operand
"RISC means fewer instructions per program" RISC needs 3 instructions where CISC needs 1 RISC = fewer kinds of simple instructions, more of them per program

Mini project: a tiny register CPU with addressing modes

Build a CPU with four registers R0 to R3 that understands every operand style: #imm, Rn, addr, @addr, (Rn), (Rn)+, −(Rn) and disp(Rn). It sums an array of 5 with auto-increment, stores the result with direct mode, then tries indirect, indexed and auto-decrement. re is Python's regular-expression module, used here to recognise each operand pattern.

# tiny register CPU with addressing modes: #imm, Rn, addr, @addr, (Rn), (Rn)+, -(Rn), disp(Rn)
import re

mem = {500: 10, 501: 20, 502: 30, 503: 40, 504: 50,   # the array
       600: 502,                                       # a pointer to a[2]
       700: 0}                                         # result
R = [0] * 4                                            # R0..R3

def ea_and_value(op):
    """Return (effective address or None, value) for one operand."""
    if op.startswith("#"):                    # immediate
        return None, int(op[1:])
    if re.fullmatch(r"R\d", op):              # register
        return None, R[int(op[1])]
    if op.startswith("@"):                    # indirect
        ea = mem[int(op[1:])]
        return ea, mem[ea]
    m = re.fullmatch(r"(-?)\((R\d)\)(\+?)", op)
    if m:                                     # (Rn), (Rn)+, -(Rn)
        r = int(m[2][1])
        if m[1]: R[r] -= 1                    # auto-decrement: first
        ea = R[r]
        if m[3]: R[r] += 1                    # auto-increment: after
        return ea, mem[ea]
    m = re.fullmatch(r"(\d+)\((R\d)\)", op)   # indexed / base-register
    if m:
        ea = int(m[1]) + R[int(m[2][1])]
        return ea, mem[ea]
    return int(op), mem[int(op)]              # direct

prog = ["MOV R1, #500",        # 0  pointer to a[0]
        "MOV R2, #5",          # 1  count
        "MOV R0, #0",          # 2  sum
        "ADD R0, (R1)+",       # 3  sum += *R1, R1 += 1
        "SUB R2, #1",          # 4
        "JNZ 3",               # 5  loop while R2 != 0
        "STORE R0, 700",       # 6  direct
        "MOV R3, @600",        # 7  indirect: a[2]
        "ADD R3, 501(R2)",     # 8  indexed: mem[501 + R2]
        "MOV R3, -(R1)",       # 9  auto-decrement: last element
        "HALT"]
PC, Z = 0, 0
while True:
    IR = prog[PC]; PC += 1
    op, *rest = IR.replace(",", "").split()
    if op == "HALT": break
    if op == "JNZ":
        if not Z: PC = int(rest[0])
        continue
    dst = int(rest[0][1])
    if op == "STORE":
        mem[int(rest[1])] = R[dst]; info = f"mem[{rest[1]}] = {R[dst]}"
    else:
        ea, v = ea_and_value(rest[1])
        R[dst] = v if op == "MOV" else R[dst] + v if op == "ADD" else R[dst] - v
        Z = int(R[dst] == 0)
        info = f"EA={ea}  R{dst}={R[dst]}"
    print(f"{IR:15} {info:22} R={R}")

Output:

MOV R1, #500    EA=None  R1=500        R=[0, 500, 0, 0]
MOV R2, #5      EA=None  R2=5          R=[0, 500, 5, 0]
MOV R0, #0      EA=None  R0=0          R=[0, 500, 5, 0]
ADD R0, (R1)+   EA=500  R0=10          R=[10, 501, 5, 0]
SUB R2, #1      EA=None  R2=4          R=[10, 501, 4, 0]
ADD R0, (R1)+   EA=501  R0=30          R=[30, 502, 4, 0]
SUB R2, #1      EA=None  R2=3          R=[30, 502, 3, 0]
ADD R0, (R1)+   EA=502  R0=60          R=[60, 503, 3, 0]
SUB R2, #1      EA=None  R2=2          R=[60, 503, 2, 0]
ADD R0, (R1)+   EA=503  R0=100         R=[100, 504, 2, 0]
SUB R2, #1      EA=None  R2=1          R=[100, 504, 1, 0]
ADD R0, (R1)+   EA=504  R0=150         R=[150, 505, 1, 0]
SUB R2, #1      EA=None  R2=0          R=[150, 505, 0, 0]
STORE R0, 700   mem[700] = 150         R=[150, 505, 0, 0]
MOV R3, @600    EA=502  R3=30          R=[150, 505, 0, 30]
ADD R3, 501(R2) EA=501  R3=50          R=[150, 505, 0, 50]
MOV R3, -(R1)   EA=504  R3=50          R=[150, 504, 0, 50]
  • The loop sums 10 + 20 + 30 + 40 + 50 = 150 with one ADD instruction, reused 5 times.
  • @600: mem[600] = 502, so EA = 502 and R3 = a[2] = 30.
  • 501(R2) with R2 = 0: EA = 501, R3 = 30 + 20 = 50.
  • −(R1): R1 was 505 (one past the end); it drops to 504 first, then reads a[4] = 50.
  • Try it: add CALL/RET with a stack in mem and an SP register, or a PC-relative LOAD 12(PC).

Practice

  1. 100 instructions, 16 registers, three register fields in a 32-bit instruction. How many bits are left?
  2. Write X = A × B + C in 3, 2, 1 and 0-address code.
  3. A PC-relative instruction at 4000 is 4 bytes long (byte-addressed), offset −20. EA?
  4. 32-bit instructions with three register fields and 64 registers. How many bits can the opcode have, and how many opcodes is that at most?
  5. 16-bit instructions, 2 register fields, 8 registers. Bits left for the opcode? Maximum opcodes?
  6. An array of 8-byte doubles starts at 2000. Address of element 7?
  7. Base register = 3000, displacement = 0x40. EA?
  8. LOAD @X: how many memory accesses in total, including the instruction fetch (one-word instruction)?
  9. R1 = 1000, 4-byte elements. LOAD −(R1): EA and R1 afterwards?
  10. A 2-byte x86 jump at 0x40 has offset byte 0x10. Target? And with offset byte 0xF0?
  11. A branch at 1200 is 4 bytes long and must reach 1500 with PC-relative mode. Offset?
  12. Write the 0-address code for (A + B) × C − D.
  13. Which of these is legal in a load-store ISA: ADD R1, R2, R3, ADD R1, R2, [100], LOAD R1, [100]?
  14. Add JMP and JZ to the stack machine and sum 3 + 2 + 1 with a loop.
  15. R1 = 600, mem[600] = 900, mem[900] = 7. What do LOAD R1, LOAD (R1) and LOAD @600 load?
Solutions

Numbers checked with Python 3.13 (math.ceil(math.log2(n)) for field widths):

Q1 13 7 4
Q3 3984
Q4 14 16384
Q5 10 1024
Q6 2056 Q7 3064
Q10 0x52 0x32
Q11 296
  1. Opcode ⌈log₂ 100⌉ = 7, registers 3 × 4 = 12 → 32 − 19 = 13 bits left.
  2. 3-address: MUL T, A, B ADD X, T, C. 2-address: MOV X, A MUL X, B ADD X, C. 1-address: LOAD A MUL B ADD C STORE X. 0-address: PUSH A PUSH B MUL PUSH C ADD POP X.
  3. PC = 4004, EA = 4004 − 20 = 3984.
  4. 3 × ⌈log₂ 64⌉ = 18 → opcode 14 bits → at most 2¹⁴ = 16,384 opcodes.
  5. 2 × 3 = 6 → 10 bits → 1,024 opcodes.
  6. 2000 + 7 × 8 = 2056.
  7. 3000 + 64 = 3064.
  8. 3: fetch the instruction, read mem[X] to get the address, read the operand.
  9. R1 becomes 996 first, EA = 996.
  10. Next instruction at 0x42. 0x42 + 0x10 = 0x52. 0xF0 = −16 → 0x42 − 16 = 0x32.
  11. Offset = 1500 − (1200 + 4) = 296.
  12. Postfix A B + C × D −: PUSH A PUSH B ADD PUSH C MUL PUSH D SUB POP X.
  13. ADD R1, R2, R3 and LOAD R1, [100] are legal. ADD R1, R2, [100] is not: arithmetic can't touch memory.
  14. Solution below. Output: S = 6 N = 0.
  15. LOAD R1 → 600 (register), LOAD (R1) → 900 (register indirect), LOAD @600 → 7 (indirect: mem[600] = 900, mem[900] = 7).
# stack machine with JMP and JZ: S = 3 + 2 + 1 with a loop
env = {"N": 3, "S": 0, "ONE": 1}
prog = ["PUSH N", "JZ 11",                       # 0-1: if N == 0, go to 11
        "PUSH S", "PUSH N", "ADD", "POP S",      # 2-5: S = S + N
        "PUSH N", "PUSH ONE", "SUB", "POP N",    # 6-9: N = N - 1
        "JMP 0",                                 # 10: back to the top
        "HALT"]                                  # 11
stack, pc = [], 0
while True:
    op, *arg = prog[pc].split(); pc += 1
    if op == "PUSH": stack.append(env[arg[0]])
    elif op == "POP": env[arg[0]] = stack.pop()
    elif op == "JMP": pc = int(arg[0])
    elif op == "JZ":
        if stack.pop() == 0: pc = int(arg[0])
    elif op == "HALT": break
    else:
        b, a = stack.pop(), stack.pop()
        stack.append(a + b if op == "ADD" else a - b)
print("S =", env["S"], " N =", env["N"])

Output:

S = 6  N = 0

Quick quiz

R1 = 600, mem[600] = 900, mem[900] = 7. What does LOAD (R1) load?

  • A. 600
  • B. 900
  • C. 7
  • D. 1
Answer

B, 900. Brackets around a register mean register indirect: EA = R1 = 600, and mem[600] = 900. 600 would be register mode, and 7 would need one more memory trip (indirect through 600).

Interview questions

  • What is an ISA? The contract between hardware and software: the instructions, registers, data types, instruction formats and addressing modes a CPU supports. Compilers target the ISA.
  • ISA vs microarchitecture? ISA = what the CPU promises; microarchitecture = how one chip implements it. Different chips can share one ISA.
  • What are opcode and operand? Opcode = what to do (ADD); operands = what to do it on (registers, addresses, constants).
  • How many opcode bits for N instructions? ⌈log₂ N⌉.
  • 3, 2, 1 and 0-address instructions? Number of explicit operands. Fewer addresses → shorter instructions, more of them. 1-address uses an accumulator; 0-address uses a stack.
  • What is an effective address? The actual memory address of the operand after applying the addressing mode.
  • Immediate vs direct? Immediate: the value is in the instruction. Direct: the instruction holds the value's address.
  • Indirect vs register indirect? Indirect: the address is in memory (two memory reads). Register indirect: the address is in a register (one read).
  • Indexed vs base-register? Indexed: big address in the instruction + index in a register (arrays). Base: big address in a register + small displacement in the instruction (records, stack frames, relocation).
  • Why PC-relative? Short offsets instead of full addresses, and the code still works wherever it's loaded (position-independent code).
  • Which mode suits arrays? Stacks? Indexed or register indirect with auto-increment; auto-decrement/auto-increment for push/pop.
  • RISC vs CISC? RISC: few simple fixed-length instructions, load-store, many registers, easy to pipeline. CISC: many complex variable-length instructions, memory operands, denser code.
  • What is a load-store architecture? Only LOAD and STORE access memory; arithmetic uses registers only.
  • Examples? x86 is CISC; ARM and RISC-V are RISC.
  • What is a calling convention? Rules for passing arguments, returning results and saving registers across calls.
  • What is a stack frame? A function's slice of the stack: return address, saved frame pointer, saved registers, locals.
  • Where is the return address stored and why a stack? Pushed on the stack by CALL; LIFO matches nested and recursive calls.

Sources

Facts about real products, companies and dates in this episode come only from these pages (fetched 28 Oct 2026):

Glossary

Term Plain meaning Example
Instruction One command the CPU understands ADD R1, R2
ISA (instruction set architecture) The menu/contract: instructions, registers, data types, formats, addressing modes x86, ARM, RISC-V
Microarchitecture How one chip implements an ISA inside two x86 chips with different speeds
Opcode (operation code) The "what to do" part of an instruction ADD, LOAD, JMP
Operand The "on what" part: register, address or constant R2, 100, #5
Field One group of bits inside an instruction the 4-bit opcode field
Instruction format The layout of fields in an instruction opcode 4 bits, address 12 bits
Immediate A constant stored inside the instruction #5 in ADD R1, #5
⌈log₂ N⌉ Bits needed to give N things different codes (rounded up) 40 opcodes → 6 bits
Mask Bit pattern used to keep some bits and clear others & 0xFFF keeps 12 bits
Shift (<<, >>) Slide bits left or right 2 << 12
3-address instruction Two sources and a destination ADD T1, A, B
2-address instruction First operand is source and destination ADD T, B: T = T + B
1-address instruction Accumulator is the hidden operand ADD B: ACC = ACC + B
0-address instruction No addresses; operands come from a stack ADD pops two, pushes sum
Accumulator (ACC) The one register holding the running result in a simple CPU LOAD A puts A in ACC
Stack Memory used last in, first out pile of plates
Push / pop Put on top / take off the top PUSH A, POP X
LIFO Last in, first out the last call returns first
Stack machine CPU whose arithmetic uses a stack JVM bytecode
Postfix notation Operator after its operands A B + C D + ×
Addressing mode Rule for finding an operand immediate, indirect ...
Effective address (EA) Real memory address of the operand 500(R2), R2 = 4 → 504
Immediate mode Value inside the instruction LOAD #100 → 100
Register mode Value in a register LOAD R1 → 300
Direct (absolute) mode Instruction holds the address LOAD 100 → mem[100]
Indirect mode Instruction holds the address of the address LOAD @200 → mem[mem[200]]
Register indirect mode Register holds the address LOAD (R1) → mem[R1]
Pointer A value (often in a register) that is an address R1 = 300
Indexed mode Address in instruction + index register LOAD 500(R2)
Index register Register holding an element number or byte offset R2 = 4
Base-register mode Base register + displacement in instruction LOAD 4(BR)
Base register / displacement Register with a block's start / small offset added to it BR = 500, +4
PC-relative mode EA = PC (next instruction) + offset jne with offset −11
Auto-increment Use the register, then add the step (R1)+
Auto-decrement Subtract the step first, then use the register −(R1)
CISC Complex Instruction Set Computer: many rich, variable-length instructions x86
RISC Reduced Instruction Set Computer: few simple, fixed-length instructions ARM, RISC-V
Load-store architecture Only LOAD/STORE touch memory RISC-V
Variable-length instruction Instructions of different sizes x86: 2, 3, 4, 5 bytes
Pipeline Overlapping the steps of several instructions next episode series
x86 CISC ISA family that began with Intel's 8086 (1978) most desktop PCs
ARM RISC ISA family licensed by Arm to other chip makers smartphones
RISC-V Open, royalty-free RISC ISA begun at UC Berkeley in 2010 load-store, 32-bit base instructions
Assembly language The ISA written as text, one line per instruction add rax, 4
Mnemonic Short name of an instruction in assembly mov, jne
Assembler Program that turns assembly into machine code part of gcc's toolchain
Machine code The instruction bytes the CPU runs 75 f5
Disassembler Turns machine code back into assembly objdump -d
Label Name for an address in assembly .L3:
Directive Assembler instruction, not a CPU instruction .file, .globl
lea x86 "load effective address": compute an address, don't read memory lea rcx, [rdi+rsi*4]
cmp / jne Compare (set flags) / jump if not equal loop test
Function (subroutine) Reusable code that is called and returns add3
CALL / RET Push return address and jump / pop it into PC call add3, ret
Return address Address of the instruction after the CALL 1 and 12 in the demo
Stack pointer (SP, rsp) Register with the address of the stack top grows down on push
Frame pointer (rbp) Register marking the start of the current stack frame -4[rbp]
Stack frame A function's slice of the stack return address, saved rbp, locals
Calling convention Rules for arguments, return value and saved registers args in edi, esi, edx; result in eax
Position-independent code Code that works wherever it is loaded uses PC-relative jumps

Summary

  • The ISA is the hardware-software contract: instructions (opcode + operands), registers, formats and addressing modes. Microarchitecture is how a chip implements it.
  • An instruction format splits the bits into fields. N choices need ⌈log₂ N⌉ bits; leftover bits often hold an immediate. A 12-bit address field can't reach address 5000.
  • 3, 2, 1, 0-address code: fewer addresses → shorter instructions, more of them. A stack machine uses 0-address arithmetic and postfix order.
  • Addressing modes decide where the operand is: immediate, register, direct, indirect (2 trips), register indirect, indexed, base-register, PC-relative (from the next instruction), auto-increment and auto-decrement. EA = the operand's real address.
  • CISC (x86): rich, variable-length, memory operands. RISC (ARM, RISC-V): simple, fixed-length, load-store, easy to pipeline.
  • Real gcc output shows the modes in action: mov edx, 0 (immediate), [rax] (register indirect), [rdi+rsi*4] (base + scaled index), and jne bytes 75 f5 (PC-relative, −11).
  • CALL pushes the return address, RET pops it; each call gets a stack frame; the calling convention says where arguments and results go.

Next episode: Memory hierarchy and locality. Registers, cache, RAM and disk; SRAM vs DRAM; ROM, EEPROM and flash; HDD vs SSD; latency vs bandwidth; and the locality that makes it all work.