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, R2orLOAD 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}printswin 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
iaddinstruction 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.DECsubtracts 1;JNZjumps 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
- 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.
- An int array starts at 1000, each int is 4 bytes, the index register holds 3. EA = 1000 + 3 × 4 = 1012.
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.
jneat 0x1c is75 f5.75= "jump if not equal";f5is −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 inesi, 3rd inedx, result ineax. Caller and callee must agree, or the values land in the wrong place. call add3pushes the return address and jumps.retpops it back into the PC.- Stack frame: the function's own slice of the stack.
push rbpsaves the caller's frame pointer (rbp, the register that marks where the current frame starts), andmov rbp, rspstarts a new frame. The arguments are stored atrbp − 4,− 8,− 12: base-register addressing, withrbpas the base and −4 as the displacement.pop rbprestores 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/RETwith a stack inmemand an SP register, or a PC-relativeLOAD 12(PC).
Practice
- 100 instructions, 16 registers, three register fields in a 32-bit instruction. How many bits are left?
- Write X = A × B + C in 3, 2, 1 and 0-address code.
- A PC-relative instruction at 4000 is 4 bytes long (byte-addressed), offset −20. EA?
- 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?
- 16-bit instructions, 2 register fields, 8 registers. Bits left for the opcode? Maximum opcodes?
- An array of 8-byte doubles starts at 2000. Address of element 7?
- Base register = 3000, displacement = 0x40. EA?
LOAD @X: how many memory accesses in total, including the instruction fetch (one-word instruction)?- R1 = 1000, 4-byte elements.
LOAD −(R1): EA and R1 afterwards? - A 2-byte x86 jump at 0x40 has offset byte 0x10. Target? And with offset byte 0xF0?
- A branch at 1200 is 4 bytes long and must reach 1500 with PC-relative mode. Offset?
- Write the 0-address code for (A + B) × C − D.
- Which of these is legal in a load-store ISA:
ADD R1, R2, R3,ADD R1, R2, [100],LOAD R1, [100]? - Add
JMPandJZto the stack machine and sum 3 + 2 + 1 with a loop. - R1 = 600, mem[600] = 900, mem[900] = 7. What do
LOAD R1,LOAD (R1)andLOAD @600load?
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
- Opcode ⌈log₂ 100⌉ = 7, registers 3 × 4 = 12 → 32 − 19 = 13 bits left.
- 3-address:
MUL T, A, BADD X, T, C. 2-address:MOV X, AMUL X, BADD X, C. 1-address:LOAD AMUL BADD CSTORE X. 0-address:PUSH APUSH BMULPUSH CADDPOP X. - PC = 4004, EA = 4004 − 20 = 3984.
- 3 × ⌈log₂ 64⌉ = 18 → opcode 14 bits → at most 2¹⁴ = 16,384 opcodes.
- 2 × 3 = 6 → 10 bits → 1,024 opcodes.
- 2000 + 7 × 8 = 2056.
- 3000 + 64 = 3064.
- 3: fetch the instruction, read mem[X] to get the address, read the operand.
- R1 becomes 996 first, EA = 996.
- Next instruction at 0x42. 0x42 + 0x10 = 0x52. 0xF0 = −16 → 0x42 − 16 = 0x32.
- Offset = 1500 − (1200 + 4) = 296.
- Postfix
A B + C × D −:PUSH APUSH BADDPUSH CMULPUSH DSUBPOP X. ADD R1, R2, R3andLOAD R1, [100]are legal.ADD R1, R2, [100]is not: arithmetic can't touch memory.- Solution below. Output:
S = 6 N = 0. 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):
- Intel 8086 (Wikipedia): released 8 June 1978; gave rise to x86; instructions 1 to 6 bytes; ALU instructions can use one memory operand.
- RISC-V (Wikipedia mirror): begun 2010 at UC Berkeley; load-store; fixed-length 32-bit base instructions; royalty-free open licences.
- History of RISC-V: Berkeley origins: a free, open specification anyone can implement without royalties.
- ARM in Your Palm (Electronics For You): ARM is RISC; Arm licenses designs and the ISA to other chip makers; suits battery-powered devices such as smartphones.
- A Brief Intro to JVM Internals: the JVM runs bytecode on a stack-based architecture with an operand stack;
iaddpops two ints and pushes the sum.
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), andjnebytes75 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.