The Fetch-Decode-Execute Cycle

A CPU is a state machine. Its state is the contents of its registers (including the program counter and flag registers) plus the contents of memory. The instruction cycle is the transition function: given the current state, fetch the next instruction, decode it, execute it, and arrive at a new state. Repeat forever (or until the machine is powered off or halted).

The classic textbook decomposition breaks the cycle into three named phases:

1. Fetch — Read the instruction bytes from memory at the address stored in the Program Counter (PC).
2. Decode — Interpret those bytes: which operation is this? which registers or memory locations does it touch? what immediate values are embedded?
3. Execute — Carry out the operation: perform an arithmetic computation, move data, change the PC, or interact with I/O.

Some textbooks and architectures split this further into Fetch / Decode / Execute / Memory-access / Write-back (this is exactly the 5-stage RISC pipeline model). But conceptually, those are all sub-phases of the fundamental three.

An analogy: imagine a kitchen chef following a recipe card. Fetching is picking up the next card from the pile. Decoding is reading the card and understanding what it says ("sauté onions until golden"). Executing is actually doing it. The chef's finger pointing at the current card in the pile is the program counter. After the step is done, the finger moves to the next card — unless the recipe says "if the sauce is too thick, jump to step 12", in which case the finger jumps.

This analogy is imperfect — real CPUs are doing millions of "recipe cards" per second and may have multiple chefs working ahead speculatively — but it captures the essential structure.

# Let's observe the cycle from outside using Linux perf.
# This counts instructions retired (i.e., actually completed cycles) for 'ls'.
perf stat -e instructions,cycles ls /

# You'll see something like:
#   1,234,567   instructions   # total fetched+decoded+executed
#   2,345,678   cycles         # total clock cycles
# IPC = instructions/cycles ≈ 0.52 here — below 1 means stalls.

The Program Counter (PC) is a hardware register that holds the memory address of the next instruction to be fetched. On x86-64, this register is called RIP (Register Instruction Pointer). On ARM64, it is PC. On RISC-V, it is also called pc.

The PC is what gives a program its sequential character: at the start of each fetch phase, the CPU reads the address in PC, fetches that instruction, and then — before executing — increments PC by the width of the instruction. On fixed-width ISAs (RISC-V, ARM, most RISC designs), all instructions are the same width (4 bytes on RV32/RV64), so PC always increments by 4. On variable-width ISAs (x86), the CPU must partially decode the instruction to know how many bytes to advance PC by — 1 to 15 bytes on modern x86.

The PC is the only register the programmer cannot directly read or write arbitrarily on most ISAs (you cannot say "move 0x12345 into RIP" the way you can move a value into RAX). Instead, you change the PC indirectly by executing branch instructions (jmp, call, ret on x86; b, bl, ret on ARM; jal, jalr on RISC-V), which write a new value into the PC as their side effect.

Why does this matter for kernel developers? Every exception, interrupt, and system call involves hardware saving the current PC (so the kernel can return to user space at exactly the right instruction) and loading a new PC (the interrupt handler or system call entry point). The kernel's struct pt_regs on x86-64 stores rip for exactly this reason — it is the saved PC at the moment the interrupt occurred.

// In Linux kernel source, arch/x86/include/asm/ptrace.h
// struct pt_regs holds the CPU state saved on interrupt/syscall entry.
// 'ip' is the saved RIP — i.e., the program counter at the moment
// the interrupt fired. The kernel uses this to return to user space.
struct pt_regs {
    unsigned long r15;
    unsigned long r14;
    // ... other registers ...
    unsigned long ip;   /* saved RIP = saved PC */
    unsigned long cs;
    unsigned long flags;
    unsigned long sp;
    unsigned long ss;
};

// In GDB, you can read the PC directly:
// (gdb) info registers rip
// rip  0xffffffff81234567  <some_kernel_function+0x3>

The fetch phase seems simple — just read from memory — but it involves several real hardware mechanisms.

Step 1: Drive the PC onto the address bus. The control unit takes the value in the PC register and places it on the address bus, signaling "I want to read from this address."

Step 2: Memory responds with bytes. In the ideal case, those bytes come from the L1 instruction cache (L1-I) in a few cycles. If there is an L1-I miss, the request cascades to L2, L3, and eventually DRAM. A DRAM access takes 60–100 ns — roughly 200–300 CPU cycles at 3 GHz — which is why a fetch that misses all caches stalls the pipeline for hundreds of cycles. This is called an instruction fetch miss or I-cache miss, and it is one of the dominant performance bottlenecks for code with large working sets or unpredictable control flow.

Step 3: Instruction Register. The fetched bytes are loaded into the Instruction Register (IR). The IR is a dedicated register (not visible to the programmer) that holds the current instruction throughout the decode and execute phases. On simple microarchitectures, the IR is literally one flip-flop-wide register. On superscalar processors, there may be a small buffer (instruction queue or fetch buffer) that holds several fetched instructions ahead of the decode unit.

Step 4: PC increment. Simultaneously (or immediately after), the PC is updated. On fixed-width ISAs, the adder is trivial: PC ← PC + 4. On x86, the CPU must look at the first byte (and sometimes the second) of the newly-fetched instruction to determine its length before it can fully advance the PC — this is why the x86 decode stage is significantly more complex than RISC decoders.

Virtual vs Physical addresses. On any modern OS-managed system, the address in PC is a virtual address. The Memory Management Unit (MMU) translates it to a physical address before driving the memory bus. If the virtual page is not present in the Translation Lookaside Buffer (TLB), a TLB miss happens, triggering a page table walk — which itself is a series of memory fetches. This is a rabbit hole worth knowing exists; you will encounter it deeply in the memory management module.

# You can see instruction-cache misses with perf:
perf stat -e L1-icache-misses,L1-icache-loads ./your_program

# Or watch the full pipeline stall breakdown:
perf stat -e cycles,instructions,cache-misses,branch-misses ./your_program

An instruction set architecture (ISA) defines a contract: given these bits, the CPU will perform this operation. Instruction encoding is the binary format — the precise layout of those bits — that the assembler produces and the decoder consumes.

RISC-V: a beautiful, clean example

RISC-V uses 32-bit fixed-width instructions with 6-bit opcodes and several well-defined formats. Every R-type (register-to-register) instruction looks like this:

Bit range:  [31:25]  [24:20]  [19:15]  [14:12]  [11:7]   [6:0]
Field:       funct7    rs2      rs1      funct3    rd      opcode

For add x5, x3, x4 (x5 = x3 + x4):

• opcode = 0110011 (integer register-register ops)
• funct3 = 000 (ADD vs SUB etc.)
• funct7 = 0000000 (ADD; 0100000 would be SUB)
• rs1 = 00011 (x3), rs2 = 00100 (x4), rd = 00101 (x5)
• Assembled: 0000000 00100 00011 000 00101 0110011 = 0x00418293 (verify at riscv.godbolt.org)

x86-64: a complex, layered example

x86 instructions are variable length (1–15 bytes) and have a complex prefix/opcode/ModRM/SIB/displacement/immediate structure that evolved since 1978. For example:

mov rax, [rbx + rcx*4 + 0x10] encodes to:

48 8B 44 8B 10

• 48 — REX.W prefix (64-bit operand size)
• 8B — MOV r64, r/m64 opcode
• 44 — ModRM byte: mod=01, reg=000 (rax), r/m=100 (SIB follows)
• 8B — SIB byte: scale=10 (×4), index=001 (rcx), base=011 (rbx)
• 10 — 8-bit displacement 0x10

This complexity is why x86 decoders consume a disproportionate fraction of the chip's area and power budget compared to RISC designs.

Why encoding matters for kernel developers

Kernel developers encounter instruction encoding in several concrete ways: kprobes patches live kernel code by replacing the first byte of a target instruction with 0xCC (INT3) — the single-byte x86 breakpoint instruction. ftrace uses a 5-byte call instruction at function entry (a "trampoline") that it can patch at runtime. eBPF's JIT compiler synthesizes instruction bytes directly. Understanding encoding is what makes these techniques possible.

// Disassemble your own binary with objdump to see encoding.
// Compile a tiny C function:
// gcc -O2 -c tiny.c -o tiny.o && objdump -d -M intel tiny.o

// tiny.c:
int add(int a, int b) { return a + b; }

// Typical objdump output:
// 0000000000000000 <add>:
//    0: 8d 04 37   lea eax,[rdi+rsi*1]
//    3: c3         ret
//
// '8d' = LEA opcode, '04' = ModRM, '37' = SIB (scale=0, index=rsi, base=rdi)
// '37' is actually 0011 0111: scale=00(×1), index=110(rsi), base=111(rdi)
// This is the entire function in 4 bytes.

Once the instruction bytes are in the Instruction Register, the decode unit breaks them apart and generates the set of control signals that will drive every other part of the CPU for this instruction's execution.

Think of the decoder as a combinational logic network (in simple CPUs) or a microcode ROM lookup (in more complex ones): it takes the instruction bits as input and outputs a set of boolean signals like:

• ALU operation selector: ADD? SUB? AND? OR? SHIFT?
• Source register indices: which registers are rs1, rs2?
• Destination register index: which register gets the result (rd)?
• Memory operation: should we read from memory? write to memory?
• Immediate value: is there an embedded constant, and how do we sign-extend it?
• Branch condition: does this instruction potentially change the PC?
• Write-enable for various register file ports.

Microcoded vs hardwired decoders

On simple or older CPUs (the 8086, early RISC processors, simple microcontrollers), the decoder is hardwired logic — a direct mapping from instruction bits to control signals, synthesized as combinational circuits.

On complex ISAs, especially x86, the decoder uses microcode: a small internal read-only program stored in the CPU. An x86 macro-instruction like REP MOVSB (block memory copy) decodes into potentially dozens of simpler internal operations called micro-operations (µops). The microcode sequencer steps through these µops one by one, each being a simple RISC-like operation that the execution units understand. Modern x86 CPUs (Intel Core, AMD Zen) have up to 4 or 5 decoders in parallel — one complex (handles multi-µop instructions) and several simple (handle 1-µop instructions) — to maintain throughput.

Register renaming during decode

On out-of-order processors, decode also performs register renaming: the architectural register numbers (like RAX=0, RBX=3) are mapped to physical register file slots from a larger pool. This eliminates false dependencies (write-after-write and write-after-read hazards) and is the foundation of out-of-order execution. It is relevant to kernel developers because it means the CPU may be executing instructions from well ahead of the current "logical" position in the program — a key insight for understanding memory ordering and the need for memory barriers.

# See how many micro-ops an instruction sequence produces on real x86 hardware.
# The 'uops_issued.any' event counts µops fed from the decoder.
perf stat -e uops_issued.any,instructions ./a.out

# You can also use LLVM-MCA to statically analyze µop counts:
# llvm-mca -mcpu=znver3 < snippet.s
# (available in llvm-tools on most Linux distros)

Execution is where the actual work happens. The decoded control signals drive the datapath: the collection of functional units, buses, and registers that process data.

The Register File

The register file is a small, fast memory array built directly into the CPU die. On x86-64 there are 16 general-purpose architectural registers (RAX–R15); on RISC-V there are 32 (x0–x31, where x0 is hardwired to zero). The register file has multiple read ports and write ports so that operands can be read and results written in a single cycle. Modern out-of-order CPUs have much larger physical register files (hundreds of entries) that back the smaller architectural register file.

The ALU

The Arithmetic Logic Unit is the combinational circuit that performs integer arithmetic and bitwise operations: add, subtract, AND, OR, XOR, NOT, shifts, comparisons. The ALU takes two input operands (from registers or with one being an immediate constant embedded in the instruction) and produces a result plus condition codes (also called flags):

• Zero flag (ZF): result was zero
• Carry flag (CF): unsigned overflow occurred
• Overflow flag (OF): signed overflow occurred
• Sign flag (SF): result was negative

Conditional branch instructions (like je / jne on x86, which check ZF) do not do their own arithmetic — they just examine the flags register. This is why cmp a, b (which computes a−b and sets flags but discards the result) must come immediately before a conditional jump.

Memory access phase

For load and store instructions, execution has an extra phase: the Effective Address is computed (e.g., base register + displacement), then memory is accessed. On the classic 5-stage RISC pipeline this is a separate named stage (MEM). Store instructions write to the store buffer first; the data is committed to the cache hierarchy later.

Write-back

The result of the execution is written back to the destination register in the register file. This completes the instruction cycle, and the processor is ready to begin the next fetch.

// Compiler Explorer (godbolt.org) is the best way to see decode/execute.
// Paste this C and choose target x86-64 with -O2:

int clamp(int x, int lo, int hi) {
    if (x < lo) return lo;
    if (x > hi) return hi;
    return x;
}

// GCC -O2 output (x86-64):
// clamp:
//   cmp edi, esi       ; x - lo, sets flags
//   cmovge eax, edi    ; if x >= lo: eax = x  (conditional move, no branch!)
//   cmovl  eax, esi    ; if x <  lo: eax = lo
//   cmp eax, edx       ; clamp_result - hi
//   cmovg  eax, edx    ; if > hi: eax = hi
//   ret
//
// Notice: no jumps! The compiler used CMOV (conditional move) to avoid
// unpredictable branches. This shows how decode+execute work together:
// CMOV decodes to: "read flags, read two sources, write dest conditionally".

In the abstract model, "execute" is a single step. In real hardware, a single instruction's execution is orchestrated as a sequence of micro-operations (µops or microinstructions) — each one being an atomic action that takes one cycle on one functional unit.

A concrete example for a simple RISC instruction LOAD r1, [r2 + 8] (load a word from memory address r2+8 into register r1) might decompose into these micro-operations:

1. MAR ← r2 + 8 — Compute the effective address and place it in the Memory Address Register
2. MDR ← Memory[MAR] — Issue the read request; wait for data in the Memory Data Register
3. r1 ← MDR — Write the loaded value into the destination register

For a STORE r3, [r2 + 16]:

1. MAR ← r2 + 16
2. MDR ← r3
3. Memory[MAR] ← MDR

The Control Unit (CU) is the hardware block that sequences these micro-operations, activating the right combinational path at each sub-step. In a hardwired CU, this is a finite-state machine whose next-state logic is combinational. In a microcoded CU, the microprogram ROM holds the sequence of µops, and a microprogram counter steps through them.

Why micro-operations matter for kernel developers

• Atomic instructions: x86's LOCK CMPXCHG (used in spinlocks, atomic_cmpxchg in the kernel) generates a specific µop sequence that the CPU guarantees completes atomically with respect to other cores via the cache-coherency protocol. Understanding that even "atomic" instructions are internally a sequence of µops is what allows you to reason about why the LOCK prefix is needed.
• Instruction fusion: Modern CPUs can fuse two adjacent µops (e.g., a CMP followed by a Jcc) into a single fused µop that consumes one decode slot and one scheduler slot. This is a micro-architectural optimization visible to profiling tools like perf and llvm-mca.
• Microcode patches: The Spectre/Meltdown mitigations that Intel deployed in early 2018 included microcode updates — literally patching the microcode ROM in the CPU at boot time to alter the behavior of certain instruction sequences. The Linux kernel loads these microcode updates from /lib/firmware/ during early boot via intel-microcode or amd-ucode packages.

// Observe that the kernel loads microcode updates at boot.
// On a running Linux system:
dmesg | grep -i microcode
// Output example:
// [    0.000000] microcode: microcode updated early to revision 0xf0
// [    3.141592] microcode: CPU0: updated to revision 0xf0, date = 2023-08-08

// The kernel source that does this is in arch/x86/kernel/cpu/microcode/

Pipelining is the technique of overlapping the fetch, decode, and execute phases of multiple instructions simultaneously — the same way a car assembly line overlaps the assembly of multiple cars. While instruction N is being executed, instruction N+1 is being decoded, and instruction N+2 is being fetched.

The classic 5-stage RISC pipeline (used in MIPS, early ARM, RISC-V educational implementations):

Stage 1: IF  — Instruction Fetch
Stage 2: ID  — Instruction Decode / Register Read
Stage 3: EX  — Execute (ALU)
Stage 4: MEM — Memory Access
Stage 5: WB  — Write Back

At any given clock cycle, five different instructions are in five different stages simultaneously. In the ideal case, the pipeline completes one instruction per clock (IPC = 1). Modern superscalar CPUs have 14–20+ pipeline stages and can issue 4–6 instructions per clock.

Pipeline hazards

Pipelines introduce hazards — situations where the ideal overlap is impossible:

1. Structural hazard: Two instructions need the same hardware resource simultaneously (e.g., only one memory port, but one instruction needs to fetch and another needs to load).

2. Data hazard (RAW — Read After Write): Instruction N writes to register R1, and instruction N+1 needs to read R1 — but N+1 reaches the ID stage before N has completed WB. The processor either stalls (inserts "bubble" NOPs) or uses forwarding/bypassing — a wire from the EX output directly back to the EX input for the next instruction, skipping the register file write-then-read roundtrip.

3. Control hazard (branch hazard): A conditional branch at EX stage has not yet determined whether to jump, but the fetch unit has already loaded the next sequential instruction. If the branch is taken, that fetched instruction is wrong and must be flushed. Modern processors use branch prediction (predicting taken/not-taken, and the target address) to keep the pipeline full, accepting the occasional misprediction penalty (10–20 cycles on modern hardware).

Kernel developers encounter pipeline effects when writing hot-path code, when arranging data to avoid unnecessary memory accesses (cache line friendliness), and fundamentally when reasoning about the smp_wmb() / smp_rmb() memory barriers — which prevent the processor's pipeline and store buffers from reordering memory operations in ways that would violate the memory model.

// GCC's __builtin_expect() helps the branch predictor by telling the
// compiler which branch is "likely" — so the compiler arranges code
// so that the common case falls through (no branch taken):

// In Linux kernel source, include/linux/compiler.h:
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

// Usage in kernel code (e.g., a fast-path check):
if (unlikely(signal_pending(current))) {
    // This path is rarely taken; the branch predictor
    // will be trained to predict "not taken" here,
    // minimizing pipeline flushes on the common path.
    do_signal();
}

The normal increment of the PC (PC ← PC + instruction_size) provides sequential execution. Control flow instructions override this, loading a new value into the PC.

Types of control flow instructions

1. Unconditional jump (jmp label on x86, b target on ARM, j target on RISC-V): PC ← target address. Target may be PC-relative (PC + offset, common on RISC) or absolute.

2. Conditional branch (je, jne, jl, etc. on x86; beq, bne, blt on RISC-V): if condition (based on flags/registers), PC ← target; else PC ← PC + 4.

3. Call/Link (call func on x86; jal ra, func on RISC-V): saves the return address (PC + 4 or PC + instruction_size) into a link register or onto the stack, then PC ← target. The kernel's function call ABI is built on this.

4. Return (ret on x86 = pop rip; ret on RISC-V = jalr x0, 0(ra)): loads the saved return address back into PC.

5. Indirect branch (jmp *rax on x86): PC ← contents of rax. Used for function pointers, vtables, switch tables, and — critically — the RETPOLINE mitigation for Spectre variant 2, which the kernel uses heavily.

Special control flow: traps and interrupts

A trap (software interrupt, syscall, int 0x80) is a deliberate transfer of control from user space to the kernel. The hardware atomically saves the current PC (and other state) to a per-CPU kernel stack, loads the address of the kernel entry point from a descriptor table (IDT on x86, vector table on ARM), and begins fetching kernel instructions. This is the fetch-decode-execute cycle changing context — the CPU transitions from executing user-space code to executing kernel code, with a completely different PC.

Hardware interrupts work similarly but are asynchronous — they can fire between any two instructions, at any PC value. This is why the kernel saves the full pt_regs structure (all registers including the PC/RIP) on interrupt entry: it needs to restore exactly the interrupted state when the handler returns.

// On x86-64 Linux, a system call uses the SYSCALL instruction.
// SYSCALL does (atomically, in hardware):
//   RCX ← RIP (save return address)
//   R11 ← RFLAGS
//   RIP ← MSR_LSTAR  (the kernel entry point, set at boot)
//   CS  ← kernel code segment
//
// Let's trace what happens with a simple write() syscall:
// in user space:
mov rax, 1          // syscall number: write
mov rdi, 1          // fd: stdout
lea rsi, [msg]      // buf
mov rdx, 13         // len
syscall             // PC jumps to kernel entry_SYSCALL_64

// The kernel entry point (arch/x86/entry/entry_64.S) then:
//   saves all registers to the kernel stack
//   calls do_syscall_64()
//   which calls sys_write() → ksys_write() → ...
//   eventually executes SYSRET which restores RIP from RCX

Theory is best anchored by observation. Here are the concrete tools that let you watch the fetch-decode-execute cycle in action.

GDB: stepping through instructions

stepi in GDB advances execution by exactly one machine instruction (not one source line). nexti does the same but steps over calls. info registers shows the current state of all architectural registers including rip (the PC). display/i $rip causes GDB to disassemble and display the current instruction before every prompt. This is literally watching the PC advance one fetch-decode-execute cycle at a time.

objdump / llvm-objdump: static disassembly

Disassembly translates the encoded bytes back into human-readable assembly. objdump -d -M intel vmlinux (where vmlinux is the unstripped kernel binary) lets you read the kernel's machine code.

perf: cycle-level hardware counters

The CPU exposes hardware performance counters via special Model-Specific Registers (MSRs on x86). The Linux perf tool reads these. Counters like instructions, cycles, cache-misses, branch-misses, uops_issued.any directly reflect what the fetch-decode-execute cycle is doing.

Compiler Explorer (godbolt.org)

Paste C/C++/Rust code, select a target architecture (x86-64, AArch64, RISC-V 64), choose a compiler and optimization level, and instantly see the assembly output. This is the best interactive tool for understanding how high-level constructs map to instructions that will be fetched-decoded-executed.

QEMU + GDB stub

To observe the kernel's own instruction cycle, you can run a Linux kernel in QEMU with the -s -S flags (expose a GDB server, pause at entry). Then attach GDB with target remote :1234 and step through the very first kernel instructions executed at boot — before even start_kernel() is called.

# Run GDB on a simple program and step instruction-by-instruction:
gcc -g -O0 -o demo demo.c
gdb ./demo
# In GDB:
# (gdb) break main
# (gdb) run
# (gdb) display/i $rip      # show instruction at PC before each prompt
# (gdb) stepi               # execute exactly ONE machine instruction
# (gdb) info registers      # inspect all registers including rip
# (gdb) x/4i $rip           # disassemble 4 instructions starting at PC

# To debug the kernel in QEMU:
# Terminal 1:
qemu-system-x86_64 -kernel bzImage -initrd initramfs.cpio.gz \
  -nographic -append 'console=ttyS0' -s -S
# Terminal 2:
gdb vmlinux
# (gdb) target remote :1234
# (gdb) break start_kernel
# (gdb) continue
# (gdb) stepi