3-, 2-, 1- and 0-address machines: register, accumulator and stack code

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• 32-bit instruction, 6-bit opcode, two 5-bit register fields: immediate width? from Lesson 1.1.1
• Which step of the instruction cycle always references memory? from Lesson 1.1.1
• What does a 2ᵏ-to-1 MUX need? from Lesson 0.2.3

1 · The Hook

🎣

ADD X, Y, Z names three things; ADD alone names none. Both are real designs. Fewer operand fields give shorter instructions but more of them. GATE asks you to write an expression for each kind of machine, count the instructions and count the memory accesses.

2 · Predict First

🤔

A stack machine has instructions with no operand fields at all: ADD pops two numbers off a stack, adds them and pushes the sum. How would it compute X = (A + B) × (C − D)? Count the instructions.

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

PUSH A, PUSH B, ADD, PUSH C, PUSH D, SUB, MUL, POP X: 8 instructions. The order is the postfix form A B + C D − ×.

Three-address machines

OP dest, src1, src2: dest ← src1 OP src2. Each field may name a register or memory location.

ADD R1, A, B      ; R1 ← A + B
SUB R2, C, D      ; R2 ← C − D
MUL X, R1, R2     ; X ← R1 × R2           3 instructions

Two-address machines

OP dest, src: dest ← dest OP src. The first operand is overwritten, so values are often copied first with MOV.

MOV R1, A         ; R1 ← A
ADD R1, B         ; R1 ← R1 + B
MOV R2, C
SUB R2, D         ; R2 ← C − D
MUL R1, R2        ; R1 ← R1 × R2
MOV X, R1         ;                       6 instructions

One-address (accumulator) machines

One special register, the accumulator (AC), is always one operand and the destination. LOAD A (AC ← A), STORE X (X ← AC), ADD B (AC ← AC + B).

LOAD A            ; AC ← A
ADD  B            ; AC ← A + B
STORE T           ; T ← AC   (temporary in memory)
LOAD C
SUB  D            ; AC ← C − D
MUL  T            ; AC ← AC × T
STORE X           ;                       7 instructions

Zero-address (stack) machines

Operands live on a stack: a last-in, first-out list. PUSH A puts A on top; POP X removes the top into X. An operation pops the top value b, then the next value a, and pushes a OP b (so SUB computes second-from-top minus top). Write the expression in postfix (operator after its operands) and translate left to right: operand → PUSH, operator → the operation.

(A + B) × (C − D) → postfix A B + C D − × → 8 instructions (see Predict).

Load/store (register–register) machines

Only LOAD and STORE touch memory; arithmetic uses registers only (three register fields). Modern RISC processors (Lesson 1.3.2) work this way.

LOAD R1, A
LOAD R2, B
ADD  R1, R1, R2
LOAD R2, C
LOAD R3, D
SUB  R2, R2, R3
MUL  R1, R1, R2
STORE R1, X       ;                       8 instructions

The trade-off

Data memory accesses also differ: in the accumulator code every instruction reads or writes one memory word (7 accesses), while the load/store code makes 5 (4 loads, 1 store).

4 · Visual

Stack machine running  A B + C D - *   with A=2, B=3, C=7, D=4

PUSH A   [2]
PUSH B   [2 3]
ADD      [5]          pop 3, pop 2, push 2+3
PUSH C   [5 7]
PUSH D   [5 7 4]
SUB      [5 3]        pop 4, pop 7, push 7-4
MUL      [15]
POP X    []           X = 15

5 · Worked Examples

Example 1 Easy

Write zero-address code for X = A + B × C and count the instructions.

Solution

Postfix A B C × +: PUSH A, PUSH B, PUSH C, MUL, ADD, POP X → 6 instructions.

Example 2 Medium

Accumulator code for X = A × B + C × D. How many instructions?

Solution

LOAD A, MUL B, STORE T, LOAD C, MUL D, ADD T, STORE X → 7.

Example 3 GATE

A stack machine runs PUSH 5, PUSH 3, PUSH 2, MUL, SUB. What is on top of the stack?

Solution

After MUL: [5, 6]. SUB pops 6 then 5 and pushes 5 − 6 = −1.

6 · GATE Traps

⚠️

• Stack SUB and DIV compute second-from-top OP top, not the reverse.
• Two-address operations overwrite their first operand.
• Fewer addresses per instruction usually means more instructions.
• In accumulator code, a temporary result must be stored before the accumulator is reused.

7 · Memory Hook

🧠

"Three says it all, two overwrites, one has an accumulator, zero has a stack."

8 · Connect the Dots

Lesson 1.1.1 laid out the fields; this lesson chose how many operand fields to have. Next: what kinds of instructions a machine provides (moves, arithmetic, logic, shifts, compares, branches) and the flags that connect compares to branches.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markStack code length

How many instructions does a zero-address machine need for X = (A − B) / (C + D × E), including the final POP?

Numerical answer: ________

Q2MCQ1 markAccumulator

In a one-address instruction ADD M, where is the other operand and where does the result go?

• (A) In the accumulator; the result goes to the accumulator
• (B) Both in memory location M
• (C) In register R0; the result goes to M
• (D) On top of the stack; the result goes to M

Q3NAT2 marksStack evaluation

A stack machine runs PUSH 8, PUSH 2, PUSH 3, ADD, SUB, PUSH 4, MUL. What value is on top?

Numerical answer: ________

Q4NAT2 marksMemory accesses

An accumulator machine runs LOAD A, ADD B, STORE T, LOAD C, ADD D, MUL T, STORE X. Each instruction is one word. How many memory accesses in total (fetches and data)?

Numerical answer: ________

Q5MSQ2 marksTrade-offs

Which statements are true?

• (A) Zero-address instructions are shorter than three-address instructions.
• (B) A program usually needs more zero-address instructions than three-address instructions.
• (C) In a load/store machine, ADD may take an operand directly from memory.
• (D) Two-address arithmetic overwrites one source operand.

10 · Rule Card

• 3-address: dest ← src1 OP src2. 2-address: dest ← dest OP src. 1-address: AC ← AC OP M. 0-address: stack.
• Stack op: pop b, pop a, push a OP b. Translate via postfix.
• Load/store: only LOAD/STORE touch memory; arithmetic on registers.
• Fewer addresses → shorter instructions, more of them.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

three-address instructiontwo-address instructionaccumulator (AC)one-address instructionstack (LIFO)PUSH and POPzero-address instructionpostfix orderload/store architecture

12 · Answer Vault