Machine Instructions & Addressing Modes

The instruction set is the contract between hardware and software: it is what a compiler targets and what a processor must implement. Everything about it is a design choice, and every choice has a cost somewhere else.

The governing identity is that execution time is the product of three things, and any instruction set decision that improves one usually damages another:

$T=IC\times CPI\times T_{clock}$

where $IC$ is the instruction count, $CPI$ the average cycles per instruction, and $T_{clock}$ the clock period.

A rich instruction that does more work reduces the instruction count and raises the cycles each instruction takes. A simple instruction set does the reverse. Neither is obviously better, and the whole RISC-versus-CISC argument is an argument about which term dominates.

The second organising fact is that an addressing mode is just a rule for computing an effective address. Every mode in every instruction set exists because some data-access pattern — a constant, an array element, a pointer chase, a stack frame — was frequent enough that encoding it directly paid for the extra decode complexity.

So the way to answer a question about a mode is to write down its effective-address formula and count the memory accesses it implies.

1. Instruction Formats

Instructions are classified by how many operand addresses they carry explicitly.

Fewer explicit addresses means shorter instructions and more of them, because intermediate values must be moved into the implicit location before each operation.

A zero-address machine evaluates expressions in postfix order, pushing operands and letting each operation consume the top two stack entries. This is why compilers targeting stack machines translate expression trees into postfix directly.

Evaluating $(A+B)\times (C+D)$ takes three arithmetic instructions on a three-address machine and seven instructions on a stack machine — four pushes, two adds and a multiply, plus a pop to store the result.

The trade is instruction count against instruction size, which is exactly the first two terms of the execution-time identity.

2. RISC and CISC

The two philosophies differ in where complexity is placed.

A load-store architecture is the defining RISC feature: arithmetic instructions operate only on registers, and memory is touched only by explicit loads and stores.

The reason is pipelining. If any instruction might access memory, every pipeline stage must be prepared for a memory delay, and the pipeline becomes hard to keep full. Confining memory access to two instruction types makes the pipeline regular, which is what actually delivers the low CPI.

Fixed-length instructions matter for the same reason: the next instruction's address is known without decoding the current one, so fetching can proceed in parallel with decoding.

The historical argument for CISC was code density, which mattered when memory was expensive and compilers were weak. Both conditions changed, which is why modern high-performance designs are RISC-like internally even when they present a CISC instruction set externally.

Amdahl's law formalises why optimising the wrong component is wasted effort. If a fraction $f$ of the execution time is improved by a factor $s$, the overall speedup is

$S=\frac{1}{(1-f)+f/s}$

The limit as $s$ grows without bound is $1/(1-f)$, so a component occupying 40 per cent of the time can never yield more than a 1.67 times speedup however completely it is eliminated.

This is why the fraction of time matters rather than the fraction of instructions, and why measuring before optimising is the standing advice.

Raw instruction rate is a misleading metric for the same reason. Comparing two machines by millions of instructions per second is meaningless across different instruction sets, because a CISC instruction and a RISC instruction do different amounts of work, and only total execution time on a real program is comparable.

3. Addressing Modes

Each mode is defined by how the effective address is computed from the instruction's fields and the processor's registers.

Counting memory accesses is what most questions actually test. Immediate and register modes touch memory zero times for the operand; indirect touches it twice, once to fetch the pointer and once to fetch the datum.

Note that these counts exclude the instruction fetch itself, which every instruction requires. A question asking for total memory accesses must add it.

Each mode exists for a recognisable access pattern.

Immediate suits constants. Register suits values already in flight. Direct suits a fixed global variable. Register indirect suits a pointer. Indexed suits array traversal, since the index register is incremented while the base stays fixed. Base-plus-offset suits a structure field or a stack-frame local, since the offset is fixed at compile time while the base varies at run time.

PC-relative addressing is what makes code position-independent. A branch encoded as a displacement from the current program counter works wherever the code is loaded, which is why it is the standard mode for branches and why shared libraries rely on it.

Autoincrement and autodecrement modes exist because stepping through an array and pushing onto a stack are both extremely common, and folding the update into the access saves an instruction each time.

4. Effective Address Computation

The reliable procedure is to write the formula, then substitute.

For indexed mode with base $B$ and index register $R_i$, the effective address is $B+R_i$, and for a scaled version it is $B+R_i\times s$ where $s$ is the element size.

The scale factor is what makes array indexing work in bytes, since incrementing an index by 1 must advance the address by the size of one element.

For base-plus-offset, the effective address is $R_b+d$ with $d$ a signed displacement encoded in the instruction. Sign matters: a negative displacement addresses a local below the frame pointer, which is where local variables usually live.

For PC-relative, the effective address is the updated program counter plus the displacement. The subtlety is which value the program counter holds, since most machines increment it during fetch, so the displacement is relative to the next instruction rather than the current one.

That off-by-one is a standard exam trap, and the instruction set's convention must be read from the question rather than assumed.

5. Instruction Encoding

An instruction word is divided into fields, and the widths must add up.

For a machine with a 32-bit instruction, 4 bits of opcode, 3 register fields of 5 bits each and the rest as an immediate, the immediate field is $32-4-15=13$ bits.

With $k$ opcode bits, at most $2^k$ distinct opcodes exist, but that limit can be exceeded by expanding opcodes.

An expanding opcode uses a reserved pattern to indicate that further opcode bits follow, borrowing them from an operand field. Instructions with fewer operands can therefore afford longer opcodes, which is exactly how a format supports many zero-operand instructions alongside a few three-operand ones.

The counting question that follows is standard: given a fixed instruction width and a required number of instructions at each operand count, decide whether an encoding exists. The method is to compute how many bit patterns each group consumes and check that the total does not exceed the available space.

Alignment and endianness are the other encoding facts examined. A word-aligned access requires the address to be a multiple of the word size, and an unaligned access either costs extra cycles or faults, depending on the machine.

Big-endian stores the most significant byte at the lowest address; little-endian stores the least significant byte there. Neither is better, but a program that writes a word and reads back individual bytes will observe the difference, which is why network protocols specify a byte order explicitly.

6. Subroutines and the Stack

A subroutine call must save the return address and then transfer control.

Where the return address is saved determines whether recursion is possible. Saving it in a fixed memory location or a dedicated register means a second call overwrites the first, so recursion fails. Saving it on a stack means each call gets its own slot, and recursion works naturally.

The stack also carries the activation record: parameters, saved registers, local variables and the return address. The frame pointer gives a stable base from which locals are addressed by fixed offsets, which is precisely the base-plus-offset mode.

Register saving is split by convention into caller-saved and callee-saved sets. A caller-saved register may be destroyed by a call, so the caller preserves it if needed across the call. A callee-saved register must be restored by the subroutine before returning.

The split exists to reduce total saves: a caller that does not need a value across the call saves nothing, and a callee that does not use a register saves nothing.

7. Worked Examples

Example 1. A machine has 32-bit instructions with an 8-bit opcode. Instructions may address memory using a 24-bit direct address. How many distinct instructions can the machine encode, and what is the addressable memory size?

The opcode is 8 bits, so at most $2^8=256$ distinct instructions.

The address field is 24 bits, so $2^{24}$ distinct addresses are reachable, which is 16 mega-locations.

If each location holds one byte, that is 16 MB of addressable memory. If each holds a 32-bit word, it is 64 MB.

The unit matters and the question must state it, since "addressable memory" is ambiguous between byte-addressable and word-addressable machines. This ambiguity is deliberate in many exam stems, and the safe move is to state the assumption in the answer.

Example 2. Instruction LOAD R1, (R2) uses register indirect mode. How many memory accesses does executing it require in total?

Count the instruction fetch first, which every instruction needs: 1 access.

Now the operand. Register indirect means the effective address is the contents of R2, which is already in a register and needs no memory access to obtain.

Fetching the operand from that address costs 1 access.

The total is 2 memory accesses.

Compare with LOAD R1, @X, full indirect mode. That costs 1 for the instruction fetch, 1 to read the pointer stored at X, and 1 to read the datum, giving 3 accesses in total.

And LOAD R1, #5, immediate mode, costs only the 1 instruction fetch, since the operand travels inside the instruction itself.

Example 3. A program has 40 per cent load-store instructions, 40 per cent ALU instructions and 20 per cent branches, with CPIs of 4, 1 and 3 respectively. Find the average CPI, and the speedup if load-store CPI is reduced to 2.

Average CPI is the weighted sum of the individual CPIs.

$CPI=0.4(4)+0.4(1)+0.2(3)=1.6+0.4+0.6=2.6$

With load-store CPI reduced to 2:

$CP{I}^{\prime }=0.4(2)+0.4(1)+0.2(3)=0.8+0.4+0.6=1.8$

The speedup is the ratio of execution times, and since instruction count and clock period are unchanged, it is the ratio of CPIs.

Speedup $=2.6/1.8\approx 1.44$, about 44 per cent faster.

Note what the arithmetic shows: load-store instructions are only 40 per cent of the count but contributed 1.6 of the 2.6 average CPI, so they dominated the time. Optimising the component with the largest share of time, not the largest share of count, is what Amdahl's law formalises.

Example 4. An instruction set has 16-bit instructions and needs 14 three-address instructions, 30 two-address instructions and 45 zero-address instructions, with 4-bit address fields. Does an encoding exist?

Work from the largest operand count downward, tracking how much opcode space remains.

A three-address instruction uses 12 bits for its three 4-bit address fields, leaving 4 bits of opcode. Four bits give 16 patterns, and 14 are needed, so 2 patterns remain unused.

Those 2 remaining patterns expand. Each covers a 4-bit field that is now free, so together they supply $2\times 2^4=32$ two-address opcodes. Thirty are needed, leaving 2 spare.

Those 2 expand again over another 4-bit field, supplying $2\times 2^4=32$ one-address opcodes. None are needed, so all 32 remain.

Each of those 32 expands over the final 4-bit field, supplying $32\times 2^4=512$ zero-address opcodes. Only 45 are needed.

The encoding exists comfortably. The method generalises: at each level, multiply the unused patterns by $2^{\text{field width}}$ to get the space available at the next level.

Example 5. A branch instruction at address 2000 uses PC-relative addressing with a displacement of $-8$. Where does it branch to, on a machine with 4-byte instructions that increments the program counter during fetch?

The program counter is incremented during fetch, so by the time the displacement is applied it holds the address of the next instruction, which is $2000+4=2004$.

The effective address is $2004+(-8)=1996$.

The branch targets address 1996.

Had the machine applied the displacement to the current instruction's address instead, the target would have been 1992. The two differ by exactly one instruction length, and which convention applies must be read from the question.

The reason PC-relative is used here at all is position independence: if the whole block of code were loaded 1000 bytes higher, the branch would still reach the right place, because the displacement encodes a distance rather than a location.

Example 6. Why does saving the return address in a dedicated register prevent recursion, and how does a stack fix it?

A subroutine call must record where to resume. If that address goes into a single dedicated register, then a second call made before the first returns overwrites it.

Concretely, if routine $f$ calls itself, the inner call stores its return address over the outer call's, and when the inner call returns, control goes back correctly, but the outer call's return address is gone. The outer return then jumps to the wrong place.

A stack fixes this because each call pushes its own return address and each return pops the matching one. The last-in-first-out discipline of the stack matches the nesting discipline of calls exactly, which is why the two are inseparable.

The same reasoning extends beyond the return address. Parameters, saved registers and local variables all need per-invocation copies for recursion to work, which is why they are grouped into an activation record pushed on entry and popped on exit.

Summary

Execution time is instruction count times cycles per instruction times clock period, and instruction set choices trade these against each other.

Fewer explicit operand addresses means shorter instructions and more of them; a stack machine evaluates expressions in postfix order.

RISC is defined by load-store architecture, fixed-length instructions and a hardwired control unit, all of which exist to make pipelining regular. CISC bought code density with variable-length instructions and memory operands.

An addressing mode is a rule for computing an effective address, and each exists for a recognisable pattern: immediate for constants, indexed for arrays, base-plus-offset for stack locals and structure fields, PC-relative for position-independent branches.

Counting memory accesses is what most mode questions test: immediate and register cost zero for the operand, direct and register indirect cost one, full indirect costs two, and the instruction fetch is always extra.

PC-relative displacements are usually relative to the next instruction, because the program counter is incremented during fetch.

Field widths must add up, and expanding opcodes borrow bits from operand fields, with unused patterns at each level multiplying by the freed field width.

Alignment requires addresses to be multiples of the access size; endianness decides which byte of a word sits at the lowest address.

Saving the return address on a stack rather than in a register is what makes recursion possible, and the activation record extends the same reasoning to parameters, locals and saved registers.