Most FSM bugs have one of three shapes

A tester writes: “the memory took three writes, the driver sent two.” The FSM behind it has a default on every output and a recovery branch for every illegal state, and it still writes junk. Bugs that survive the coding rules usually take one of three shapes, and each leaves its own mark in the waveform.

The three stories below are real simulations of small buggy FSMs. In each one, find the first wrong slot, read the state and inputs there, and the case branch at fault follows.

Story 1: a write nobody sent

The sender's cmd bus means something only while valid is high. Between offers the sender leaves the last value on the bus, which the protocol allows. The write controller pulses wr_en for one cycle and then spends one cycle in BUSY while the memory recovers.

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

module wr_ctrl (
  input  logic       clk, rst_n,
  input  logic       valid,          // cmd means something only while valid = 1
  input  logic [1:0] cmd,            // 2'd1 = WRITE
  output logic       wr_en,
  output logic       busy
);
  typedef enum logic {IDLE, BUSY} state_t;
  state_t state, next;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) state <= IDLE;
    else        state <= next;
  always_comb begin
    next = state;  wr_en = 1'b0;
    case (state)
      IDLE: if (cmd == 2'd1) begin wr_en = 1'b1; next = BUSY; end  // BUG: valid not checked
      BUSY: next = IDLE;                                           // one recovery cycle
      default: next = IDLE;
    endcase
  end
  assign busy = (state == BUSY);
endmodule

Read each slot as one cycle, and look for an output that breaks the protocol rule “write only for a valid WRITE”.

• Slot 1: valid = 1 and cmd = 1, so wr_en = 1. This is the first real write.

• Slot 2: BUSY. The sender drops valid but leaves cmd at 1, which is legal.

• Slot 3, the first wrong slot: wr_en = 1 with valid = 0. The FSM is back in IDLE and decodes the stale cmd.

• Slot 6: the second real write. The memory saw writes in slots 1, 3 and 6.

Root cause: the IDLE branch tests cmd but not valid. A Mealy output reads its inputs in the same cycle, so it is only as clean as the inputs it decodes. Fix:

// snippet
      IDLE: if (valid && cmd == 2'd1) begin wr_en = 1'b1; next = BUSY; end

The same shape appears when a Mealy output decodes a bus during the cycles a mux is switching it, or reads a status flag the datapath updates one cycle late. Qualifying the decode is cheaper than turning the output into a Moore output, which costs a cycle of latency.

Story 2: five beats in a four-beat burst

The bus monitor reports five data beats for every burst of length 4, and the receiving FIFO overflows by one entry per burst. The counter cnt holds the number of beats already sent in this burst.

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

module burst_ctrl #(parameter int LEN = 4) (
  input  logic clk, rst_n, start,
  output logic beat, done
);
  typedef enum logic [1:0] {IDLE, BURST, DONE} state_t;
  state_t state, next;
  logic [2:0] cnt;                          // beats already sent in this burst
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin state <= IDLE; cnt <= 3'd0; end
    else begin
      state <= next;
      cnt   <= (state == BURST) ? cnt + 3'd1 : 3'd0;
    end
  always_comb begin
    next = state;  beat = 1'b0;  done = 1'b0;
    case (state)
      IDLE:  if (start) next = BURST;
      BURST: begin beat = 1'b1; if (cnt == LEN) next = DONE; end  // BUG: cnt starts at 0
      DONE:  begin done = 1'b1; next = IDLE; end
      default: next = IDLE;
    endcase
  end
endmodule

Count the slots where beat is high, and read cnt in each one.

• Slot 1: start = 1 in IDLE. The edge at the end of the slot moves the FSM to BURST.

• Slots 2 to 5: four beats, with cnt = 0, 1, 2 and 3. A correct burst ends here.

• Slot 6, the first wrong slot: a fifth beat with cnt = 4. A four-beat burst should never show that value while beat is high.

• Slot 7: DONE, one cycle late.

Root cause: during the last beat cnt holds LEN − 1, because it counts beats sent before the current one. Fix:

// snippet
      BURST: begin beat = 1'b1; if (cnt == LEN - 1) next = DONE; end

Write what the counter means at the moment of the compare in a comment next to its declaration: “beats already sent” or “number of the current beat”. The exit value then follows from the comment, and a reviewer can check it without simulating.

Story 3: a request that never finishes

The regression times out on the first request that hits the responder's fast path; slow requests pass. The requester raises req in REQ, keeps it high in WAIT, and leaves WAIT on ack. The responder pulses ack once per request, from zero to three cycles after req rises.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

module req_ctrl (
  input  logic clk, rst_n, start, ack,
  output logic req, done
);
  typedef enum logic [1:0] {IDLE, REQ, WAIT, DONE} state_t;
  state_t state, next;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) state <= IDLE;
    else        state <= next;
  always_comb begin
    next = state;  req = 1'b0;  done = 1'b0;
    case (state)
      IDLE: if (start) next = REQ;
      REQ:  begin req = 1'b1; next = WAIT; end                  // BUG: ack ignored here
      WAIT: begin req = 1'b1; if (ack) next = DONE; end
      DONE: begin done = 1'b1; next = IDLE; end
      default: next = IDLE;
    endcase
  end
endmodule

Follow ack and ask, in each slot where it is high, which state was there to see it.

• Slots 1 to 5: request 1. req rises in slot 2 (REQ), ack arrives in slot 4 (WAIT), and DONE follows in slot 5.

• Slot 7, the first wrong slot: ack = 1 while state = 1 (REQ). REQ moves to WAIT whatever ack says.

• Slots 8 to 11: WAIT with req high and ack low for ever. The responder has already answered and will not answer again.

Root cause: the protocol allows an answer in the first request cycle, and REQ does not test ack. Fix:

// snippet
      REQ:  begin req = 1'b1; if (ack) next = DONE; else next = WAIT; end

Slot 7 is now a transition: the same ack that was lost moves the FSM to DONE in slot 8, and the machine is idle again in slot 9. Merging REQ into WAIT would fix it too. A lock-up always has this shape in a trace: the release event happens, but in a state that does not look for it, one or more slots before the hang becomes visible. Lock-ups caused by an illegal encoding are a different mechanism, covered in illegal states and recovery.

A method for the next bug

1. Write the symptom as a broken rule: which output, which promise (“wr_en only with valid”, “four beats”, “every request finishes”).

2. Find the first wrong slot. Move back from the reported failure until the rule holds again; the slot after that is the one to study.

3. In that slot, read the state and every input the FSM decodes in that state.

4. The state names the case branch; the inputs name the condition that ran inside it.

5. Compare that branch with the protocol: does it test the qualifier, the right count, and every event that can arrive in this state?

6. Fix the branch, then rerun the failing stimulus and the bench below.

Checking the fixes

The bench drives the three fixed controllers together. Story 1 gets 200 cycles of random offers with junk on cmd whenever valid is low, and every write is counted against the valid WRITE offers. Story 2 runs three bursts and counts the beats in each. Story 3 runs one request for each ack latency from 0 to 3 and fails any request that is not done within ten cycles. Each check is aimed at one of the three bug lines.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

module wr_ctrl (
  input  logic       clk, rst_n,
  input  logic       valid,
  input  logic [1:0] cmd,            // 2'd1 = WRITE
  output logic       wr_en,
  output logic       busy
);
  typedef enum logic {IDLE, BUSY} state_t;
  state_t state, next;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) state <= IDLE;
    else        state <= next;
  always_comb begin
    next = state;  wr_en = 1'b0;
    case (state)
      IDLE: if (valid && cmd == 2'd1) begin wr_en = 1'b1; next = BUSY; end
      BUSY: next = IDLE;
      default: next = IDLE;
    endcase
  end
  assign busy = (state == BUSY);
endmodule

module burst_ctrl #(parameter int LEN = 4) (
  input  logic clk, rst_n, start,
  output logic beat, done
);
  typedef enum logic [1:0] {IDLE, BURST, DONE} state_t;
  state_t state, next;
  logic [2:0] cnt;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin state <= IDLE; cnt <= 3'd0; end
    else begin
      state <= next;
      cnt   <= (state == BURST) ? cnt + 3'd1 : 3'd0;
    end
  always_comb begin
    next = state;  beat = 1'b0;  done = 1'b0;
    case (state)
      IDLE:  if (start) next = BURST;
      BURST: begin beat = 1'b1; if (cnt == LEN - 1) next = DONE; end
      DONE:  begin done = 1'b1; next = IDLE; end
      default: next = IDLE;
    endcase
  end
endmodule

module req_ctrl (
  input  logic clk, rst_n, start, ack,
  output logic req, done
);
  typedef enum logic [1:0] {IDLE, REQ, WAIT, DONE} state_t;
  state_t state, next;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) state <= IDLE;
    else        state <= next;
  always_comb begin
    next = state;  req = 1'b0;  done = 1'b0;
    case (state)
      IDLE: if (start) next = REQ;
      REQ:  begin req = 1'b1; if (ack) next = DONE; else next = WAIT; end
      WAIT: begin req = 1'b1; if (ack) next = DONE; end
      DONE: begin done = 1'b1; next = IDLE; end
      default: next = IDLE;
    endcase
  end
endmodule

Common mistakes

Related topics

• Debug hierarchy before touching code

• Illegal states and recovery