Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 67 ยท Instruction Set Architecture

Zero-, One-, Two- and Three-Address Instructions and Stacks

Compare zero-, one-, two- and three-address instruction formats, evaluate expressions on each machine type, and see how a hardware stack works, with Python code.

How many operands should one instruction name? A single add needs two inputs and one output. If an instruction can name all three, programs are short, but each instruction is long. If it names none, instructions are tiny, but the program needs more of them. The number of explicit addresses in an instruction is a basic design choice, and it shapes the whole architecture.

In this lesson you will compare three-, two-, one- and zero-address instruction formats on a single expression, count instructions and memory accesses, and learn how a stack supports the zero-address style. It follows Instruction Formats and Encoding and comes before Addressing Modes.

The four address formats

Take the statement X = (A + B) * (C + D). Here is how each style computes it. In these listings M[x] means a memory word, R1 a register, and ACC an accumulator.

Three-address: each instruction names two sources and a destination.

Text
ADD R1, A, B       ; R1 = A + B
ADD R2, C, D       ; R2 = C + D
MUL X, R1, R2      ; X = R1 * R2

Two-address: the destination is also the first source, so it is overwritten.

Text
MOV R1, A          ; R1 = A
ADD R1, B          ; R1 = R1 + B
MOV R2, C
ADD R2, D
MUL R1, R2         ; R1 = R1 * R2
MOV X, R1

One-address (accumulator): one operand is implied: the accumulator.

Text
LOAD A             ; ACC = A
ADD B
STORE T            ; T = A + B
LOAD C
ADD D
MUL T              ; ACC = (C + D) * T
STORE X

Zero-address (stack): operands are implied by the top of a stack. Only push and pop name an address.

Text
PUSH A
PUSH B
ADD                ; replaces the top two with A + B
PUSH C
PUSH D
ADD
MUL
POP X
Format Instructions for the example Instruction size Where the operands live
Three-address 3 large (three fields) registers or memory
Two-address 6 medium registers or memory
One-address 7 small accumulator plus memory
Zero-address 8 smallest the stack

Notice the trade-off: fewer addresses means shorter instructions but a longer program. Which wins depends on how often the code runs from a cache, how much memory traffic each form causes, and how easy the hardware is to build. Modern RISC machines (MIPS, RISC-V, ARM) use three-address instructions on registers. x86 is two-address. Early computers were accumulator machines. The Java virtual machine and WebAssembly are zero-address stack machines.

How a stack works

A stack is a last-in, first-out store with two operations: push adds an item on top, and pop removes the item on top. A hardware stack lives in ordinary memory, and a register called the stack pointer (SP) tracks its top. Most machines let the stack grow toward lower addresses:

Text
PUSH:  SP <- SP - 1;  M[SP] <- value
POP:   value <- M[SP]; SP <- SP + 1

Stacks are central for three jobs: evaluating expressions, passing function arguments and return addresses (the call stack), and saving registers during an interrupt.

flowchart TD
  P1["PUSH A: stack = A"] --> P2["PUSH B: stack = A, B"]
  P2 --> ADD["ADD: pop B, pop A, push A+B"]
  ADD --> P3["PUSH C, PUSH D: stack = A+B, C, D"]
  P3 --> ADD2["ADD: stack = A+B, C+D"]
  ADD2 --> MUL["MUL: stack = (A+B)*(C+D)"]

Evaluating (A+B)(C+D) on a stack machine: operators work on whatever sits on top.*

Reverse Polish notation

Stack code corresponds to postfix (reverse Polish) notation, where the operator follows its operands: (A + B) * (C + D) becomes A B + C D + *. Postfix needs no parentheses and no precedence rules: you read left to right, push operands, and apply each operator to the top items. A compiler for a stack machine converts the usual infix expression into postfix and emits one instruction per token.

A stack machine and a register machine in Python

The code below converts an infix expression to postfix with the classic shunting-yard method, then runs it on a stack machine and counts instructions and memory accesses. It also generates three-address code for the same expression so you can compare.

Python Stack machine versus three-address code

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The stack machine needs 7 instructions plus the final pop, but each one is tiny and needs no register numbers. The three-address machine needs 3 but each instruction is wide and needs registers to exist.

Stack organization in hardware

There are two ways to build a stack:

  • A register stack keeps the top few entries in dedicated registers, so push and pop are fast but the size is fixed.
  • A memory stack keeps the entries in RAM with an SP register. It is nearly unlimited, but slower, and a stack overflow happens if it grows into other data.

Many designs combine both: a small hardware cache of the top of the stack, and the rest in memory. Besides push and pop, a processor needs CALL (push the return address, jump) and RET (pop the address into the PC). The next lesson on addressing modes shows how stack variables are reached with the base-plus-offset mode.

Python A memory stack with a stack pointer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The call stack of your programs is exactly this structure: every function call pushes a frame (return address, arguments, locals), and every return pops it.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the main advantage of three-address instructions?

    Naming two sources and a destination lets a single instruction do a complete operation, reducing the instruction count.
  2. 2. In a zero-address machine, where do the operands of ADD come from?

    Zero-address arithmetic instructions pop the top two stack entries and push the result.
  3. 3. How is (A + B) * C written in postfix?

    Each operator follows its operands: first A B +, then C, then *.
  4. 4. What happens to the stack pointer on a PUSH, in a stack that grows toward lower addresses?

    SP moves down to the new top, and the value is written there.
  5. 5. In a one-address (accumulator) machine, what is the implied operand?

    The instruction names only one operand; the accumulator is the other source and the destination.

Summary

  • The number of addresses in an instruction trades instruction length against program length.
  • Three-address formats give the shortest programs; two-address overwrites a source; one-address uses an accumulator; zero-address uses a stack.
  • A stack is last-in, first-out: push stores at a decremented stack pointer, pop reads and increments it.
  • Postfix notation maps directly onto stack instructions and needs no parentheses.
  • Stacks power expression evaluation, function calls and interrupt handling.

Continue with Addressing Modes.