Level 66: Ghosts of the Wrong Path

Open level →

The task

Goal: resolve the branch in EX: until now branches did not work in the pipeline (PC walked linearly), and EX already has zero (the ALU) and operand forwarding ready — Branch32 gives taken = isBr & (zero ^ f30) (beq is taken on zero, bne on ~zero), target = pc + imm (the B-imm is already in the payload from ImmGen32). A taken branch flushes two "ghosts" — the instructions fetched along the old path: clr IfId and IdEx (the price is 2 cycles), the next-PC mux switches to the target. Everything is gated by flush_en; priority over stall. The .end idempotence is preserved: the jal word is caught by the fetch-hold back in IF. Acceptance is exact-step on the counter and mixed loops (a branch and load-use at the same time) plus the flush_en=0 negative.

Until now branches did not work in the pipeline: the PC walked linearly. You resolve the branch in EX — where zero (the ALU) and operand forwarding are already available. A taken branch flushes two "ghosts" — the instructions that managed to enter IF/ID and ID/EX along the old path: their effects have not happened yet, so a clr is safe.

Editable files — pipetop.v, branch.v, idex.v (now 167 bits); hazard.v and fwd.v are read-only. Tasks:

  1. Extend IdEx32 to 167 bits. Add isBr and f30 (funct3[0]) — the branch resolves in EX from the payload.
  2. Build Branch32 (branch.v). taken = isBr & (zero ^ f30): zero is the Alu32 output (a branch executes as a sub), beq (f3=000) is taken on zero, bne (f3=001) on ~zero.
  3. Compute the target. Add32(pcE, immE): the B-imm is already in the payload from ImmGen32 (bimm.v from level 53 inside) — no separate decode in EX is needed. The third Add32 in the schematic.
  4. Route the flush. The flush_en gate, priority over stall, weaker than freeze: clrBase = stallG | takenF, IfId.en &= ~takenF, the next-PC mux: nextpc = takenF ? target : (hold ? pcw : pc4). The taken price = 2 cycles, not-taken is free.
  5. Check .end. The stop word 32'h0000006F is a jal, not isBr: the fetch-hold keeps the PC as on level 62, and the flush does not touch it. The halt idempotence is preserved.
  6. Run the loops. counter: 9 taken branches × 2 = 18 flushed slots (nflush 18), 22 cycles; the mixed program drives a branch and a load-use at the same time — 17/28 (stall 3, flush 4). The flush_en=0 negative must corrupt the result without errors.

Solution for self-checking

Build it yourself first. The solution below is a checkpoint.

What you should get: counter runs in 22 cycles (10 retirements + 4 fill + 18 flush cycles, nflush = 18, nstall = 0); the mixed program is 17/28 (stall 3, flush 4); the flush_en = 0 negative steers the PC past the loop with no errors, but the registers must differ from the golden.

Step 1 — Branch32 and the target. cond = zero ^ f30; taken = isBr & cond. In the top: Branch32 brz(takenRaw, isbrE, zeroE, f30E), Add32 brtg(brTgt, pcE, immE), takenF = takenRaw & flush_en, takenFr = takenF & nfreeze.

Step 2 — the priorities. clrBase = stallG | takenFr; stallClr = clrBase & nfreeze; IfId.en = (nfreeze & ~stallG) & ~takenFr; hold = freeze | isEnd | (stallG & ~takenFr); nextpc = takenFr ? brTgt : (hold ? pcw : pc4).

Step 3 — the checkpoint numbers. counter: 10 retires, 22 cycles (10 + 4 + 9×2 flush), nflush=18, nstall=0. Mixed (lw + a branch): 17/28 (17 + 4 + 4 flush + 3 stall), nstall=3, nflush=4. The flush_en=0 negative: branches are never taken, the pc walks past the loop, .end catches the halt — err=0, x5 must differ.

Check yourself

Why is flushing the ghosts safe, even though the instructions are already in the pipeline?

The old-path instructions have only entered IF/ID and ID/EX — their effects (register and memory writes) have not happened yet, so clr erases them without a trace. It still costs: 2 cycles per taken branch, which is why not-taken is the sensible default.