Tracing programs: registers, memory and flags; counting memory references and cycles

0 · Recall Warm-up

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

• while (*p++): which mode? from Lesson 1.2.3
• With R1 = 400 and the chapter table, LOAD R0, 100(R1) loads? from Lesson 1.2.2
• How many instructions execute: MOV R1,#6; loop ADD, SUB R1,R1,#2, BNZ; HALT? from Lesson 1.1.3

1 · The Hook

🎣

Many GATE COA questions hand you ten lines of assembly, initial register and memory values, and ask for one number: a final value, a count of memory references, or a total of clock cycles. The method is always the same: trace it, carefully, in a table.

2 · Predict First

🤔

The array-sum loop with n = 5 runs 3 setup instructions, a 5-instruction loop body and 2 closing instructions. How many instructions execute?

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

3 · Core Concept

💡

Predict First — the answer

3 + 5 × 5 + 2 = 30.

The full array-sum program

A is an array of n = 5 four-byte integers at address 1000 holding 3, 8, 1, 6, 2. SUM is at address 2000. One-word instructions.

MOV   R1, #0          ; sum = 0
      MOV   R2, #0          ; byte offset of A[i]
      MOV   R3, #5          ; elements left
LOOP: LOAD  R4, 1000(R2)    ; R4 ← A[i]
      ADD   R1, R1, R4
      ADD   R2, R2, #4
      SUB   R3, R3, #1
      BNZ   R3, LOOP
      STORE R1, 2000        ; SUM ← sum
      HALT

Trace in a table

SUM = 20.

Counting

• Instructions executed: 3 + 5 × 5 + 2 = 30.
• Memory references: 30 instruction fetches + 5 loads + 1 store = 36.
• Clock cycles, given cycles per instruction type: MOV 1, LOAD 3, ADD 1, SUB 1, BNZ 2, STORE 3, HALT 1: setup 3 × 1 = 3; loop 5 × (3 + 1 + 1 + 1 + 2) = 40; end 3 + 1 = 4; total 47.

General: cycles = Σ over instruction types (times executed × cycles each).

Instruction addresses

When instructions have different sizes, add sizes to find addresses. With a start of 1000 and sizes 4, 4, 8, 4 bytes, the instructions start at 1000, 1004, 1008, 1016. The address after an instruction is what the PC holds while it runs (Lesson 0.1.1); GATE uses this to ask which return address gets saved (Lessons 1.3.2 and 6.2.1).

A memory-updating loop

Word-addressable memory; M[3000] = 6; R3 = 2000; M[2000] … M[2009] all hold 100.

MOV  R1, (3000)    ; R1 ← M[3000] = 6
LOOP: MOV  R2, (R3)      ; R2 ← M[R3]
      ADD  R2, R1        ; R2 ← R2 + R1
      MOV  (R3), R2      ; M[R3] ← R2
      INC  R3
      DEC  R1
      BNZ  LOOP          ; branch if the last result (R1) ≠ 0
      HALT

The loop runs 6 times (R1 = 6, 5, …, 1). It writes M[2000] = 106, M[2001] = 105, …, M[2005] = 101; M[2006] stays 100. Data memory references: 1 (first MOV) + 6 × 2 (read and write per iteration) = 13. Instructions executed: 1 + 6 × 6 + 1 = 38.

4 · Visual

Counting template

  section      times run   instructions   cycles each        subtotal
  setup        1           3 MOV          1                  3
  loop body    5           LOAD ADD ADD   3+1+1+1+2 = 8      40
                           SUB BNZ
  end          1           STORE HALT     3+1                4
                                                     total   47 cycles

5 · Worked Examples

Example 1 Easy

In the array-sum program with n = 5, how many data memory references are made?

Solution

5 loads + 1 store = 6.

Example 2 Medium

Same program, but every instruction is 2 words long. How many memory references in total?

Solution

Fetches: 30 instructions × 2 words = 60; data 6; total 66.

Example 3 GATE

In the memory-updating loop, what is M[2003] after it runs?

Solution

Iterations write 2000 (+6), 2001 (+5), 2002 (+4), 2003 (+3): M[2003] = 103.

6 · GATE Traps

⚠️

• Count executed instructions, not lines: a loop body counts once per iteration.
• The last iteration still executes the branch (not taken): include it.
• "Memory references" usually means fetches and data; "data references" means operands only. Read which.
• Multi-word instructions need several fetch accesses each.

7 · Memory Hook

🧠

"Trace in a table, count by section." Setup once, body × iterations, end once.

8 · Connect the Dots

You can now run a program by hand and count its cost. Last lesson of Phase 1: the stack in memory, subroutine calls and returns, and the RISC vs CISC design styles.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markInstruction count

The array-sum program runs with n = 8 (same code). How many instructions execute?

Numerical answer: ________

Q2NAT2 marksMemory references

The array-sum program with n = 8, one-word instructions: total memory references (fetches and data)?

Numerical answer: ________

Q3NAT2 marksCycles

The array-sum program with n = 8 and the cycle costs MOV 1, LOAD 3, ADD 1, SUB 1, BNZ 2, STORE 3, HALT 1. Total cycles?

Numerical answer: ________

Q4MCQ1 markTrace

What is R2 after this code?

MOV R1, #5
      MOV R2, #1
LOOP: MUL R2, R2, R1
      SUB R1, R1, #1
      BNZ R1, LOOP

• (A) 720
• (B) 120
• (C) 5
• (D) 24

Q5NAT1 markInstruction address

A program starts at byte address 1000. Its first four instructions are 4, 4, 8 and 4 bytes long. At what address does the fourth instruction start?

Numerical answer: ________

10 · Rule Card

• Trace values in a table: one row per iteration.
• IC = setup + iterations × body + end (the final not-taken branch counts).
• Memory references = Σ instruction words fetched + data accesses.
• Cycles = Σ (executions × cycles of that instruction).
• Instruction addresses: running sum of sizes.

11 · Concept Ledger

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

program trace tableexecuted-instruction countmemory-reference countcycle count by sectioninstruction addresses from sizes

12 · Answer Vault