11State machines with rules

1. States are an enum

A state machine is a register that holds "where we are" plus the logic that decides where to go next. In BSV the natural type for "where we are" is an enum: a new type whose only values are the labels you list.

Form

typedef enum { Idle, Count, Done } State deriving (Bits, Eq, FShow);

Reg#(State) state <- mkReg(Idle);

deriving (Bits) gives the type a bit pattern, which is what lets it live in a register; Eq gives ==; FShow lets fshow(state) print the label's name. Without explicit values the first label is 0 and each next one adds 1, in the fewest bits that hold the largest code. You compare states by label, never by number: state == Count, not state == 1.

The encoding, the comparison and the width of an enum value are the subject of the enum section of user-defined types, with a runnable example. This chapter uses enums as state labels and takes those rules as read.

2. One rule per state

Write the machine as one rule for each state. The guard names the state with ==; the body does that state's work and writes the next state into the register. Because a register holds exactly one label, guards on different labels are never true together, so the rules never compete and never conflict.

rule start (state == Idle);
  state <= Count;
endrule

rule count (state == Count && n < 3);
  n <= n + 1;
endrule

rule leave (state == Count && n == 3);
  state <= Done;
endrule

Read state as the current state and state <= … as the next state. A transition written in cycle k is the state the guards see in cycle k + 1. A state that needs more than one rule, like Count above, splits its condition so the two rules are still exclusive.

3. From a state table to rules

Design the machine as a table first, then write one rule per row.

The same table can become a single rule with a case (state) whose arms hold the conditions and writes. Both forms describe the same hardware; per-state rules keep each state's work local, the single rule keeps every transition in one place.

4. The phase register: ordering what one rule cannot do

A state machine is not only for protocols with named modes. It is also the answer when two operations must both happen but cannot share one atomic transition, because a firing is one transition in which every read sees the entry state. Keep a register that records the current step, and make exactly one rule enabled in each step.

Form

typedef enum { Step1, Step2, ... } Phase deriving (Bits, Eq);

Reg#(Phase) phase <- mkReg(Step1);

rule firstWork (phase == Step1);
  ...
  phase <= Step2;
endrule

typedef enum { Load, Shift, Done } Step deriving (Bits, Eq);
Reg#(Step) step <- mkReg(Load);

rule load (step == Load);
  data <= input_value;
  step <= Shift;
endrule

rule shift (step == Shift);
  data <= data << 1;
  step <= Done;
endrule

The conditions of load and shift can never be true together, so the scheduler never has to choose between them.

Note. Phase state costs a register and a cycle of latency. In exchange you get an observable busy interval, an unambiguous order, and an easy place to add steps to the protocol. Giving two conflicting rules a priority does not solve an ordering problem: priority chooses one operation per cycle; it does not guarantee that both eventually happen in the required order.

5. Ordering two transitions

OrderedRuleTransitions.bsv starts with value = 10, increment = 3, and phase = AddReady. addFirst is enabled only in AddReady, doubleSecond only in DoubleReady, and show only in Idle.

Predict before you run. Work out value and phase after each edge.

package OrderedRuleTransitions;

typedef enum { Idle, AddReady, DoubleReady } Phase
  deriving (Bits, Eq, FShow);

(* synthesize *)
module mkTop(Empty);
  Reg#(Bit#(8)) value <- mkReg(10);
  Reg#(Bit#(8)) increment <- mkReg(3);
  Reg#(Phase) phase <- mkReg(AddReady);

  // Each phase enables exactly one rule, so scheduling does not need
  // an arbitrary priority.
  rule addFirst (phase == AddReady);
    value <= value + increment;
    phase <= DoubleReady;
  endrule

  // DoubleReady is an observable intermediate state between the two
  // atomic transitions.
  rule doubleSecond (phase == DoubleReady);
    value <= value << 1;
    phase <= Idle;
  endrule

  rule show (phase == Idle);
    $display("value = %0d", value);
    $finish(0);
  endrule
endmodule

endpackage

Check the result.

A printed 26 means the addition happened before the doubling; the reverse order would give 10 × 2 + 3 = 23. The intermediate 13 is not a temporary expression inside one rule but real state held throughout cycle 1. This example compiles without warnings.

Try it yourself.

1. Set the initial value to 250 and increment to 10. The 8-bit sum 250 + 10 = 260 wraps past 256, so the intermediate value is 4 and the output is 8. This checks ordering and fixed-width arithmetic together.
2. Merge both steps into one rule as value <= (value + increment) << 1;. One cycle and the DoubleReady step disappear. If nothing outside needs to see the intermediate step, this is the simpler design.

6. Predict a two-state machine

A simple machine has two states and one input. A toggle holds q, 0 or 1, and an input t: when t is 1 the next state is the other one, when t is 0 the machine holds. As rules that is one rule guarded by t writing q <= ~q; a false guard is the hold.

Fill in the table. Cycle 0 starts from the reset state q = 0. The t column is the input the rule sees during that cycle, and the column you fill is q after the edge that ends it.

This is a browser model of the state machine, not a compiled design; the example above is the real toolchain.

7. A later option: sequential statements

Some processes read better as a plan than as a table: do this, then that. The StmtFSM library takes a seq … endseq of actions and compiles it into the state register and rules you would otherwise write by hand, one step per action, with the clock edge between steps. A seq that writes 3 to a register and then adds 4 ends at 7, because the second step runs in a later cycle and reads what the first committed; one rule holding both writes would read the entry value for both and could not express the order at all.

Nothing in this course requires StmtFSM; the finite state machines chapter covers it when you want it, including start, done and the started flag its testbench needs.

8. Apply it: replace a conflict with two transitions

The Practice problem below the example starts from two rules enabled in AddReady that both read and write the same registers, which is the conflict of rules that share state. Your job is to turn it into the machine of section 4 using the supplied Phase enum. Inspect the reset state and the transition made by start, then correct the next phase after addition and the guard on doubling. Check that the printed result could only come from the required order.

9. Summary

10. Check your understanding

1. Why do per-state rules never produce a conflict warning?

   Show answer

   Their guards compare one register against different labels. At the start of a cycle that register holds exactly one label, so at most one guard is true and the rules can never want the same cycle.

2. Two rules must both run, in a fixed order, but each needs to see what the other wrote. Why does giving one of them priority not solve it?

   Show answer

   Priority decides which rule fires when both want the same cycle; it does not sequence them. The fix is a phase register, which makes exactly one of them enabled per cycle and writes the next phase as part of the same atomic transition.

3. In the ordered-transitions example, what is held in value during cycle 1, and what would be lost by merging the two rules?

   Show answer

   value holds the intermediate 13 for the whole of cycle 1: it is real state, observable from outside. Merging the rules into value <= (value + increment) << 1; removes that observable step and the cycle it takes, which is the right trade only when nothing outside needs to see it.