Fetching before you know

A pipeline fetches the next sequential instruction every cycle. A taken branch resolves a couple of stages later, after two wrong-path instructions have entered the pipe.

The fix is a flush: redirect the PC to the target and clear the valid bits of the younger instructions.

Each column is one cycle and each cell holds the PC in that stage, as traced by the testbench below. A struck-through cell is still in the register, but its valid bit is 0.

• Cycle 2: the branch at PC 4 resolves taken in Execute while 5 and 6 are already in flight.

• Cycle 3: Fetch is redirected to 0x40, and both younger instructions lose their valid bits.

• Cycles 3 and 4: Execute holds only flushed work, so two cycles are lost; 0x40 executes in cycle 5.

The full listing sits under Testbench below. It redirects the PC on a taken branch and clears both younger valid bits.

Branch penalty

Each flushed slot is a lost cycle in this single-issue sketch: fetch is stage 1, one item enters per cycle, fetch predicts sequential (not taken), redirect is immediate, and there is no extra fetch delay or overlapping stall. Baseline CPI is near 1. With the branch resolved in stage k, a taken branch discards k − 1 instructions, which equals wasted cycles here. A discarded count is not generally the same as elapsed recovery time.

If a fraction b of instructions are branches and a fraction t of those are taken, the average cost is:

• Resolve earlier (move comparison into decode) to cut k.

• Predict the outcome and fetch from the predicted target; flush only on a misprediction.

• Delay slots expose the bubble to software (rare in modern ISAs).

Common mistakes

Testbench

The three-stage front end plus the testbench that takes a branch and checks the resume address.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

module mini_frontend (
  input  logic        clk, rst_n,
  input  logic        taken,              // execute: a taken branch is resolved this cycle
  input  logic [7:0]  target,
  output logic [7:0]  exec_pc,
  output logic        exec_valid,         // instruction in execute is real
  output logic [7:0]  fetch_pc
);
  logic [7:0] pc, d_pc;
  logic       d_valid;

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      pc <= 8'd0;  d_valid <= 1'b0;  exec_valid <= 1'b0;
    end else begin
      // Fetch: redirect on a taken branch, otherwise sequential
      pc <= taken ? target : pc + 8'd1;
      // Decode: flush (drop) the instruction fetched on the wrong path
      d_pc    <= pc;
      d_valid <= !taken;
      // Execute: the instruction behind the branch is also wrong-path, so flush it too
      exec_pc    <= d_pc;
      exec_valid <= d_valid && !taken;
    end
  assign fetch_pc = pc;
endmodule

Related topics

• Retiming-friendly coding