Addressing Modes

An instruction's operands cannot simply be "the number." Every operand reference must be decoded into one of a small number of operand locations: a constant baked into the instruction word, a register, a memory cell, or the instruction stream itself (relative to the program counter). The addressing mode is the piece of the instruction encoding — often a few bits in the opcode/funct fields, sometimes implicit in the instruction's format — that tells the datapath which recipe to use and supplies the raw material (an immediate value, a register number, or both) that the recipe consumes. Formally, an addressing mode is a function ``` effective_operand = f(instruction_fields, register_file, memory, PC) ``` that different modes instantiate differently. Immediate addressing sets `effective_operand` directly from a sign- or zero-extended bit field inside the instruction — no register file or memory lookup needed. Register addressing sets `effective_operand` to the contents of a register named by an index field. Base-offset (also called base-displacement or register-indirect-with-offset) addressing first computes an effective address as `EA = R[base] + sign_extend(offset)`, then reads or writes memory at that address. PC-relative addressing computes `EA = PC + sign_extend(offset)` (often with the offset pre-scaled, e.g., multiplied by 2 or 4), used almost exclusively for branches and jumps so that control transfers are expressed as distances rather than absolute addresses. The unifying theme is a trade-off between encoding cost and reach. Immediate and register modes are cheap to decode and need no adder or memory access, but immediates are limited by field width and registers are limited in number. Base-offset and PC-relative modes need an adder (and, for base-offset loads/stores, a memory access) but can reach any byte in the address space relative to a movable reference point. A RISC instruction set typically supports exactly these four modes and nothing fancier (no memory-indirect, no scaled-index-with-two-registers) — this restraint is what makes the Single-Cycle Datapath uniform enough to build from one small set of muxes and one adder, rather than a combinatorial explosion of address-computation units.

Decoding an addressing mode is a two-stage process baked into instruction execution: (1) identify the mode from opcode/format bits, and (2) compute the effective operand or effective address using the fields that mode defines. The stages below describe this for a generic RISC-style ISA (matching RISC-V/MIPS conventions), then generalize.

Immediate addressing. The instruction encodes an immediate field directly. The control unit sign-extends (arithmetic immediates) or zero-extends (some logical/CSR immediates) this field to the machine word width. No register read for the second operand, no memory access.

Register addressing. Small index fields (e.g., 5 bits for 32 registers) select entries from the register file. Both source operands and the destination are named this way in R-type instructions. This is the default, cheapest mode and requires only a register file read/write port.

Base-offset addressing. Used by loads and stores. One register field supplies the base address (often a pointer or the stack pointer); an immediate field supplies a signed offset (a byte displacement, e.g., a struct field's position or an array index times element size). The ALU computes `EA = base + offset`; this address goes to the data memory, not the instruction memory.

PC-relative addressing. Used by conditional branches and some jumps. An immediate field encodes a signed offset in instruction-count units or bytes from the current instruction's address (or the next one, depending on ISA convention). The datapath computes `next_PC = PC + offset` (with scaling), enabling the same branch instruction to work correctly no matter where in memory the code is loaded — the essence of position-independent code. ``` // Generic instruction execution loop showing addressing-mode dispatch. // Assumes fields opcode, mode, rd, rs1, rs2, imm are already extracted // from the fetched instruction word by the decode stage. function EXECUTE(instr, RegFile, Mem, PC): switch instr.mode: case IMMEDIATE: // e.g., ADDI rd, rs1, imm => rd = rs1 + imm operand2 = sign_extend(instr.imm) result = ALU(RegFile[instr.rs1], operand2, instr.op) RegFile[instr.rd] = result next_PC = PC + 4 case REGISTER: // e.g., ADD rd, rs1, rs2 => rd = rs1 + rs2 operand2 = RegFile[instr.rs2] result = ALU(RegFile[instr.rs1], operand2, instr.op) RegFile[instr.rd] = result next_PC = PC + 4 case BASE_OFFSET: // e.g., LW rd, imm(rs1) => rd = Mem[rs1 + imm] // SW rs2, imm(rs1) => Mem[rs1 + imm] = rs2 EA = RegFile[instr.rs1] + sign_extend(instr.imm) if instr.op == LOAD: RegFile[instr.rd] = Mem.read(EA, instr.width) else if instr.op == STORE: Mem.write(EA, RegFile[instr.rs2], instr.width) next_PC = PC + 4 case PC_RELATIVE: // e.g., BEQ rs1, rs2, offset taken = (RegFile[instr.rs1] == RegFile[instr.rs2]) // condition varies by op target = PC + sign_extend(instr.imm) SCALE next_PC = taken ? target : PC + 4 return next_PC ``` The `mode` value in this pseudocode is not necessarily a separate field the hardware stores — in a real ISA it is implied by the opcode. Decode logic (a small lookup driven by the opcode bits) sets control signals such as `ALUSrc`, `RegWrite`, `MemRead`, `MemWrite`, and `Branch`; the addressing mode is really the pattern of these signals*, not an extra tag. Thinking of "mode" as an explicit case in pseudocode is a teaching simplification of what is, in hardware, a set of independently-set control wires feeding muxes.

Time cost per mode. Every addressing mode adds at most one extra pipeline-stage-worth of work beyond a register read:

• Immediate: `O(1)` — a sign-extension circuit (pure combinational logic, essentially free, adds negligible propagation delay) feeds the ALU directly. No dependency on the register file for the second operand.
• Register: `O(1)` — a register file read is a fixed-latency multiplexer/decoder lookup over `2^k` entries for a `k`-bit index (`k=5` gives 32 registers), independent of program size.
• Base-offset: `O(1)` time but two sequential operations — an adder computes `EA` in one cycle-equivalent, then a memory access (cache lookup) follows. This is why loads/stores are often the highest-latency common instructions and why load-use hazards exist in pipelines.
• PC-relative: `O(1)` — one adder computes the branch target in parallel with the ALU's comparison logic, so a well-designed datapath overlaps target computation with condition evaluation rather than serializing them.

All four modes are constant-time with respect to program size, which is essential: instruction execution time must not grow as the program grows, or performance would degrade with program complexity. The only "search" in any of these modes is the register file lookup, and that search is a hardware decoder over a fixed, small address space (`5` bits → `32` entries), not a linear or logarithmic search — so it is correctly O(1), not O(log n) as a software index lookup might be.

Space/encoding cost. The determining resource is instruction bits. A 32-bit instruction word must carve out fields for opcode, register indices, and immediates simultaneously. If an ISA supports `r` registers, each register field costs `⌈log2 r⌉` bits; a base-offset load/store instruction needs two register fields (destination and base) plus an immediate, e.g., RISC-V's I-type format spends `5+5+12 = 22` bits on operands out of 32, leaving 10 for `opcode`/`funct3`. This is why immediates are typically short (12–16 bits) — they compete directly with opcode space and register fields inside a fixed-width word. Wider immediates (e.g., RISC-V's `lui`/`auipc` 20-bit immediates, or `jal`'s 20-bit reach) sacrifice other fields or restrict which registers/operations can appear, illustrating the core encoding trade-off.

Correctness argument. The invariant that guarantees each mode is correct is: the effective address/operand computed by the datapath, before any load/store or register write, must equal the value obtained by directly evaluating the assembly-level operand expression the mode represents. This is proven mode-by-mode by construction:

• Immediate: `sign_extend` is defined so that for any `n`-bit two's-complement immediate `i`, `sign_extend(i)` as a 32/64-bit value equals the mathematical integer `i` represented in two's complement — this is a standard bit-replication lemma (replicate the sign bit into all higher-order positions), verifiable by induction on the number of replicated bits.
• Register: correctness reduces to the register file's read/write consistency — a read of register `r` returns the most recently written value to `r` (assuming no concurrent write-read hazard, which pipelining handles via forwarding or stalls).
• Base-offset: correctness follows from the definition `EA = base + offset` matching the compiler's address computation for arrays/structs (`array_base + index * element_size` folded into the offset, or `struct_base + field_offset`), so the address the compiler intended is exactly the address the hardware computes.
• PC-relative: correctness requires that the offset be computed relative to a well-defined reference PC (commonly the address of the branch instruction itself). If the assembler/hardware disagree on whether the reference is `PC` or `PC+4`, every branch target is off by one instruction — this is precisely why ISA manuals pin down the reference point exactly, and why the invariant "offset is measured from address X" must hold uniformly across assembler and hardware.

Honest tradeoffs. More addressing modes (as in CISC machines like x86, which support memory-indirect, scaled-index, and even memory-to-memory operations) increase code density and can reduce instruction count, but they enlarge decode logic, complicate pipelining (variable-latency, multi-step effective-address computations), and bloat the ISA's opcode space. RISC philosophy deliberately restricts memory addressing to load/store instructions with a single base-offset mode, accepting slightly larger code (more instructions) in exchange for uniform, single-cycle-friendly control logic — a trade that has repeatedly won out in modern high-performance and low-power designs.

Trace the addressing modes used when compiling this C snippet to RISC-V-style assembly: ```c int arr[10]; int i = 3; arr[i] = arr[i] + 5; ``` Assume `x10` holds the base address of `arr`, and `x11` holds `i`. Each `int` is 4 bytes, so index `i` must be scaled by 4 before use as a byte offset.

Trace with concrete memory: suppose `arr` starts at address `0x1000`, so `arr[3]` lives at `0x1000 + 12 = 0x100C`, and currently `Mem[0x100C] = 20`. 1. `x12 = 12` (immediate-shifted index scaled to a byte offset). 2. `x13 = 0x1000 + 12 = 0x100C` (register-addressed sum — the effective address of the array element, computed once and reused). 3. `lw` uses base-offset addressing: `EA = x13 + 0 = 0x100C`; loads `x14 = 20`. 4. `x15 = 20 + 5 = 25` (immediate addressing again). 5. `sw` uses base-offset addressing: writes `25` back to `Mem[0x100C]`. 6. `beq` computes a PC-relative target to jump to a label `done`; if `done` is 5 instructions (20 bytes) ahead, `offset = 20`, and `target = PC + 20`. Notice how the same base-offset instruction form (`lw`/`sw` with `offset(base)`) is reused for both the read and the write — the compiler computed the effective address once (step 2) and both memory instructions reference it via `0(x13)`, avoiding redundant address arithmetic. This reuse is a direct consequence of separating address computation (register mode) from memory access (base-offset mode) as distinct instructions, which a CISC single "memory-to-memory add" instruction would hide but a RISC load/store split exposes and lets the compiler optimize.

The idea of separating "where is the operand" from "what is the operation" traces back to the earliest stored-program computers, where engineers first confronted the tension between compact instruction words and flexible operand access.

Compilers rely on addressing modes as their fundamental vocabulary for code generation: every local variable access becomes base-offset addressing off the stack or frame pointer, every constant becomes an immediate, and every function call and loop becomes a PC-relative branch or jump. Operating systems depend on PC-relative addressing to implement position-independent code (PIC), which allows shared libraries to be loaded at different addresses in different processes without relocation — a cornerstone of address space layout randomization (ASLR) used for security hardening. Debuggers and disassemblers must decode addressing modes correctly to reconstruct meaningful assembly from raw bytes, and JIT compilers (in JVMs, V8, LuaJIT) generate machine code on the fly that must respect the exact addressing-mode encodings of the target ISA. Understanding addressing modes is also the direct on-ramp to The Single-Cycle Datapath, where each mode corresponds to a specific setting of control signals (`ALUSrc`, `MemtoReg`, `Branch`, `PCSrc`) driving multiplexers, and to Procedure Calls and the Stack, where base-offset addressing off the stack pointer implements local variables and saved registers, and PC-relative jumps implement calls and returns.

Ask the tutor: How do addressing modes map onto the actual control signals and multiplexers in a single-cycle datapath?