5.2.2 Data dependences: RAW, WAR, WAW; finding them in code

0 · Recall Warm-up

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

Speedup of a balanced 6-stage pipeline with 0.5 stalls per instruction? from Lesson 5.2.1
In which stages are registers read and written? from Lesson 5.1.3
What does CMP change? from Lesson 1.1.3

1 · The Hook

🎣

ADD R1, R2, R3 then SUB R4, R1, R5: the SUB needs the R1 the ADD is still computing. That is one kind of dependence. Two other kinds involve no data flow at all, only reused register names. GATE asks you to find and count all three in a code fragment.

2 · Predict First

🤔

I1: ADD R1, R2, R3 and I2: MUL R2, R4, R5. I2 overwrites R2, which I1 reads. Is there a problem if I2 somehow wrote R2 before I1 read it?

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

3 · Core Concept

💡

Predict First — the answer

Yes: I1 would read the new R2 and compute the wrong sum. This is a WAR (write-after-read) dependence: no value flows from I1 to I2, but their order must be kept.

The three data dependences

For an earlier instruction i and a later instruction j:

Name	Condition	Also called
RAW (read after write)	j reads a register that i writes	true (flow) dependence
WAR (write after read)	j writes a register that i reads	anti-dependence
WAW (write after write)	j writes a register that i writes	output dependence

Count a pair only if no instruction between them writes that register (otherwise the dependence is with that nearer instruction).

Which ones stall our pipeline

In the in-order 5-stage pipeline, every instruction reads in ID and writes in WB, in program order. A later instruction can never write before an earlier one reads (WAR) or writes (WAW). So only RAW causes hazards there. WAR and WAW become hazards when instructions can complete out of order (multi-cycle units, Lesson 5.3.1, or out-of-order processors).

WAR and WAW are name dependences: they disappear if the later instruction writes to a different register (register renaming). RAW is real data flow and cannot be renamed away.

Worked example

I1: ADD R1, R2, R3
I2: SUB R4, R1, R5
I3: AND R2, R4, R1
I4: OR  R1, R6, R2

RAW: I1→I2 (R1), I1→I3 (R1), I2→I3 (R4), I3→I4 (R2): 4
WAR: I1→I3 (R2: I1 reads, I3 writes), I2→I4 (R1), I3→I4 (R1): 3
WAW: I1→I4 (R1): 1

4 · Visual

I1: ADD R1, R2, R3
        |   \ R2 read ......... WAR ......... I3 writes R2
        | R1 written
        +---- RAW ----> I2 reads R1
        +---- RAW ----> I3 reads R1
        +---- WAW ----> I4 writes R1

5 · Worked Examples

Example 1 Easy

I1: LOAD R5, 0(R1); I2: ADD R6, R5, R2. Dependence?

Solution

RAW on R5 (I2 reads what I1 writes).

Example 2 Medium

I1: ADD R1, R2, R3; I2: SUB R2, R4, R5; I3: MUL R1, R6, R7. List the dependences.

Solution

WAR I1→I2 (R2); WAW I1→I3 (R1). No RAW.

Example 3 GATE

Which dependences can cause hazards in the classic in-order 5-stage pipeline?

Solution

Only RAW; WAR and WAW need out-of-order completion.

6 · GATE Traps

⚠️

RAW = true data flow; WAR/WAW are name conflicts.
Direction matters: WAR means the later instruction writes.
Skip a pair if a register is rewritten in between.
In the in-order 5-stage pipeline, only RAW stalls.

7 · Memory Hook

🧠

"Name the second action first: Read-After-Write means the later one reads."

8 · Connect the Dots

This lesson found dependences; the next one handles the dangerous kind, RAW, in the pipeline: by stalling, by forwarding, and the one case forwarding cannot fully fix, the load-use hazard.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksCount RAW

How many RAW dependences?

I1: MUL R3, R1, R2
I2: ADD R4, R3, R1
I3: SUB R1, R4, R5
I4: ADD R3, R1, R4

Numerical answer: ________

Q2NAT2 marksCount WAR

Same code: how many WAR dependences?

Numerical answer: ________

Q3NAT1 markCount WAW

Same code: how many WAW dependences?

Numerical answer: ________

Q4MCQ1 markRenaming

(A) none
(B) RAW only
(C) all three
(D) WAR and WAW

Q5MSQ2 marksStatements

Which are true?

(A) In the in-order 5-stage pipeline, WAW causes frequent stalls.
(B) WAW is also called output dependence.
(C) WAR is also called anti-dependence.
(D) A RAW dependence means the later instruction needs the earlier one's result.

10 · Rule Card

RAW: later reads what earlier writes (true). WAR: later writes what earlier reads (anti). WAW: both write (output).
Count only nearest pairs (no intervening write).
In-order 5-stage: only RAW stalls. Renaming removes WAR/WAW.

11 · Concept Ledger

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

RAW (true/flow) dependenceWAR (anti) dependenceWAW (output) dependencename dependenceregister renamingout-of-order completion

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

6 / 1.5 = 4.
Read in ID, written in WB.
Only the flags.