21FIFOs, split, and the library primitives

Almost every BSV design is built from the same handful of library pieces: sized bit vectors, tuples, registers, FIFOs, and the simulator's system tasks. This chapter teaches each one as a contract you can rely on: what its type fixes before any hardware exists, what its methods do within one clock cycle, and when a call makes a rule wait. The numeric types and their explicit width conversions have their own chapter, Types, widths and explicit conversion, and so do mkReg and mkRegU, in Registers and one rule. Here we take up split and tuples, FIFO and FIFOF, and the system tasks.

You should be comfortable with Bit#(n), provisos such as Add from Typeclasses and provisos, and the difference between value methods, Action methods, and atomic rules from Methods: value, Action, ActionValue. Implicit conditions, from Guards: hold and stop, matter most in the FIFO sections.

Every example compiles with bsc, generates Verilog, and simulates it with Icarus Verilog. Run performs all three steps in order.

1. split and tuples

1.1 split takes its boundary from the result type

split divides one vector into a high part and a low part. It has no argument that says where to cut. The caller writes the result type, and the compiler solves the two widths from it.

Syntax

function Tuple2#(Bit#(m), Bit#(n)) split(Bit#(mn) value)
  provisos (Add#(m, n, mn));

Bit#(8) a = 8'hA5;                             // 1010_0101
Tuple2#(Bit#(2), Bit#(6)) parts = split(a);
// tpl_1(parts) is 2'b10 and tpl_2(parts) is 6'b100101

If the two result widths do not add up to the input width, no m and n can satisfy Add, and compilation stops before any hardware is generated.

1.2 Tuples group a few values by position

Tuple2 through Tuple8 hold a small, fixed number of values without a dedicated type. You build them with tuple2, tuple3, and so on, and read them with tpl_1, tpl_2, and so on, or bind every member at once with match, the pattern form from Pattern matching.

Syntax

Tuple2#(type1, type2) name = tuple2(value1, value2);
type1 first = tpl_1(name);
match {.x, .y} = name;

let pair = tuple2(8'h12, True);
Bit#(8) data  = tpl_1(pair);     // 8'h12
Bool    valid = tpl_2(pair);     // True
match {.d, .v} = pair;           // d is 8'h12, v is True

Members have no names, only positions. Tuples suit short-lived results such as the output of split. When the values describe a reusable concept, a struct with named fields documents itself and cannot be read in the wrong order.

1.3 Example: splitting a 12-bit frame

SplitVector.bsv divides a 12-bit frame into a 4-bit kind and an 8-bit payload. Read the signature of splitFrame first: its result type is the only place the boundary appears. Then read the match declaration in the rule show.

The input 12'ha5c is 1010 0101 1100 in binary. The result type Tuple2#(Bit#(4), Bit#(8)) gives m = 4 and n = 8, and Add#(4, 8, 12) holds.

Predict before you run.

1. Which bits, 11..8 or 3..0, become kind?
2. What two hex values are printed?
3. Does the body of splitFrame mention the numbers 4 or 8?

package SplitVector;

function Tuple2#(Bit#(4), Bit#(8)) splitFrame(Bit#(12) frame);
  // The result widths determine where split divides the vector.
  return split(frame);
endfunction

(* synthesize *)
module mkTop(Empty);
  rule show;
    match {.kind, .payload} = splitFrame(12'ha5c);
    $display("kind=%h payload=%h", kind, payload);
    $finish(0);
  endrule
endmodule

endpackage

Check the result.

The boundary sits four bits from the top, exactly as the first result width says, and nothing in the function body names it.

Try it yourself.

1. Change the result type to Tuple2#(Bit#(8), Bit#(4)). The boundary moves to four bits from the bottom, and the line becomes kind=a5 payload=c. The function body stays the same.
2. Change it to Tuple2#(Bit#(4), Bit#(4)) while the input stays Bit#(12). Compilation stops with bsc error T0031, which reports that no instance of Add#(4, 4, 12) exists and points at the split call. The fix is to make the result widths add up to 12, not to truncate anything.

2. FIFO: order and implicit conditions

2.1 The four methods

A FIFO holds values in arrival order. FIFO#(a) from the FIFO package provides four methods.

Syntax

import FIFO::*;

FIFO#(type) name <- mkFIFO;              // depth chosen by the library
FIFO#(type) name <- mkSizedFIFO(depth);  // explicit depth
FIFO#(type) name <- mkFIFO1;             // depth 1

FIFO#(Bit#(8)) queue <- mkSizedFIFO(4);

rule produce;
  queue.enq(8'h12);
endrule

rule consume;
  Bit#(8) oldest = queue.first;
  queue.deq;
endrule

2.2 first and deq in the same rule

On mkFIFO, mkSizedFIFO and mkFIFO1, first reports the FIFO as it was at the start of the cycle, and deq takes effect at the end (mkLFIFO and mkBypassFIFO order their methods differently). When one rule calls both, first returns exactly the entry that deq removes. The order of the two statements inside the rule does not change that, because a rule is atomic, as Rules that share state showed.

2.3 Implicit conditions make callers wait

None of the methods needs an explicit "is it full?" or "is it empty?" test. Each method's readiness becomes part of the guard of any rule that calls it. In the snippet above, produce simply does not fire while the FIFO is full, and consume does not fire while it is empty.

Note. A rule that waits on an implicit condition produces no error. It just never fires. If nothing else can change the FIFO, the design stops making progress.

2.4 Example: two values leave in arrival order

FIFOOrder.bsv enqueues two bytes and removes them again. Note the depth in mkSizedFIFO(2), then read the four rules in step order. Each rule is guarded by a different step value, so exactly one rule runs per cycle.

Predict before you run.

1. Which value does dequeueFirst print, and which does dequeueSecond print?
2. Does any rule test whether the FIFO is empty or full?
3. If $display in dequeueFirst moved below queue.deq, would the printed value change?

package FIFOOrder;

import FIFO::*;

(* synthesize *)
module mkTop(Empty);
  FIFO#(Bit#(8)) queue <- mkSizedFIFO(2);
  Reg#(UInt#(3)) step <- mkReg(0);

  rule enqueueFirst (step == 0);
    queue.enq(8'h12);
    step <= 1;
  endrule

  rule enqueueSecond (step == 1);
    queue.enq(8'h34);
    step <= 2;
  endrule

  // first reads the oldest entry and deq removes that same entry.
  rule dequeueFirst (step == 2);
    $display("first=%h", queue.first);
    queue.deq;
    step <= 3;
  endrule

  rule dequeueSecond (step == 3);
    $display("second=%h", queue.first);
    queue.deq;
    $finish(0);
  endrule
endmodule

endpackage

Check the result.

No rule tested for empty or full; the implicit conditions handled it. Moving $display below queue.deq still prints first=12, because statement order inside one atomic rule does not make the dequeue visible early.

Try it yourself.

1. Change the depth to mkSizedFIFO(1). In cycle 1, enqueueSecond calls enq on a full FIFO, so its implicit condition is false and the rule cannot fire. step stays at 1, no other rule is enabled, and the design deadlocks. Nothing is printed and $finish is never reached, so the run ends only when the execution time limit stops it. Silence without an error is the typical symptom of a stalled implicit condition.

mkFIFO leaves the capacity to the library, while mkSizedFIFO(depth) sets it. Start from mkFIFO when correctness must not depend on depth, and choose a sized FIFO when buffering is part of the design, as the deadlock shows it can be.

2.5 Example: a full queue holds the producer, an empty one the consumer

In FIFOOrder.bsv a phase register made sure no call ever met a full or empty FIFO. FIFOBackpressure.bsv lets both happen. tick counts cycles. produce enqueues 0, 1, 2 and 3 while sent < 4 and never asks whether the queue is full. consume has the explicit guard cycle >= 3 and never asks whether the queue is empty. The queue is mkSizedFIFO(2). Every printed line starts with the cycle number, so a cycle in which a rule did not fire shows up as a missing line; stop ends the run in cycle 9.

package FIFOBackpressure;

import FIFO::*;

(* synthesize *)
module mkTop(Empty);
  FIFO#(UInt#(8)) queue <- mkSizedFIFO(2);
  Reg#(UInt#(8)) cycle <- mkReg(0);
  Reg#(UInt#(8)) sent <- mkReg(0);

  rule tick;
    cycle <= cycle + 1;
  endrule

  // No full test here: enq's implicit condition stops this rule while the queue is full.
  rule produce (sent < 4);
    queue.enq(sent);
    sent <= sent + 1;
    $display("cycle %0d: enq %0d", cycle, sent);
  endrule

  // The explicit guard opens at cycle 3; deq still waits for an entry.
  rule consume (cycle >= 3);
    queue.deq;
    $display("cycle %0d: deq %0d", cycle, queue.first);
  endrule

  rule stop (cycle == 9);
    $display("cycle %0d: stop", cycle);
    $finish(0);
  endrule
endmodule

endpackage

Predict before you run. For each cycle, write how many entries the queue holds at the start, whether each rule's explicit guard is true, whether its FIFO method is ready, and which lines appear.

Check the result. Compare every line with this trace. In each guard/ready pair the first value is the explicit guard and the second is the readiness of the FIFO method; the rule fires only when both are true.

The values leave in the order they arrived, 0 to 3, and no value was lost or repeated, although neither rule tests the queue. The silent cycles have different causes that look identical in the output: in cycle 2 the producer waits on enq (and keeps waiting through cycle 3), and in cycles 7 and 8 the consumer waits on deq.

Try it yourself.

1. Change the depth to mkSizedFIFO(4). The producer is never blocked: the lines are enq 0 to enq 3 in cycles 0 to 3, with cycle 3: deq 0 in the same cycle as enq 3, and then deq 1, deq 2 and deq 3 in cycles 4, 5 and 6.
2. Restore depth 2 and change consume's guard to cycle >= 1. Predict the cycle of the last deq line before you run.

3. FIFOF: readiness as values

3.1 notFull and notEmpty

FIFOF#(a) from the FIFOF package has every FIFO method plus two value methods. They let control logic look at the FIFO's state without waiting on it. On mkSizedFIFOF they report the state at the start of the cycle, like its other value methods (bypass and mkCReg-based elements can show same-cycle writes).

Syntax

import FIFOF::*;

FIFOF#(type) name <- mkSizedFIFOF(depth);
Bool roomLeft  = name.notFull;    // enq could proceed
Bool hasData   = name.notEmpty;   // first and deq could proceed

FIFOF#(Bit#(8)) queue <- mkSizedFIFOF(4);
Reg#(UInt#(8)) stalls <- mkReg(0);

rule countStalls (!queue.notFull);
  stalls <= stalls + 1;           // one count per cycle spent full
endrule

countStalls never calls enq or deq, so it has no implicit condition from the FIFO. It fires in every cycle that begins with the queue full, which is exactly the kind of "do something else" behavior the flags are for.

3.2 Example: two flags across fill levels

FIFOFStatus.bsv prints both flags while the FIFO holds 0, 2, 1, and 0 entries. Check the depth in mkSizedFIFOF(2), then follow step through the five rules. Each $display runs before that rule's own enq, deq, or clear takes effect.

Predict before you run. Write the pair (notFull, notEmpty) for each of the four printed lines.

1. What does an empty two-entry FIFOF report?
2. What does it report with two entries?
3. With one entry, can both flags be true at once?

package FIFOFStatus;

import FIFOF::*;

(* synthesize *)
module mkTop(Empty);
  FIFOF#(Bit#(8)) queue <- mkSizedFIFOF(2);
  Reg#(UInt#(3)) step <- mkReg(0);

  rule enqueueFirst (step == 0);
    $display("empty: notFull=%0d notEmpty=%0d", queue.notFull, queue.notEmpty);
    queue.enq(8'haa);
    step <= 1;
  endrule

  rule enqueueSecond (step == 1);
    queue.enq(8'hbb);
    step <= 2;
  endrule

  // A two-entry FIFOF reports notFull false after two enqueues.
  rule removeOne (step == 2);
    $display("full: notFull=%0d notEmpty=%0d", queue.notFull, queue.notEmpty);
    queue.deq;
    step <= 3;
  endrule

  rule clearRest (step == 3);
    $display("one: notFull=%0d notEmpty=%0d", queue.notFull, queue.notEmpty);
    queue.clear;
    step <= 4;
  endrule

  rule finish (step == 4);
    $display("cleared: notFull=%0d notEmpty=%0d", queue.notFull, queue.notEmpty);
    $finish(0);
  endrule
endmodule

endpackage

Check the result.

The two flags move independently. A producer whose rule is guarded by notEmpty would have its explicit guard true at the wrong times: false in front of an empty FIFO, and true in front of a full one, where enq's own implicit condition then keeps the rule from being enabled at all. A true explicit guard is not the same as an enabled rule.

Try it yourself.

1. Change the depth to mkSizedFIFOF(3). Two entries no longer fill the FIFO, so the full: line prints notFull=1 notEmpty=1, and its label becomes wrong. The flags describe capacity relative to the chosen depth, not the number of enq calls in the code.

3.3 Implicit conditions or flags?

Decide by what the caller should do when the FIFO is not ready.

4. System tasks

4.1 Tasks for the simulator

System tasks begin with $. They are actions or values provided by the simulator, used in testbenches and for debugging.

Syntax

$display(format, arguments...);   // print one line
$write(format, arguments...);     // print without a newline
$finish(exitCode);                // end the simulation
let now <- $time;                 // current simulation time

rule report (count == 3);
  let now <- $time;
  $display("time=%0t count=%0d", now, count);
  $finish(0);
endrule

4.2 System tasks are not hardware

bsc emits system tasks inside a Verilog block wrapped in synopsys translate_off and translate_on comments, and synthesis tools skip that block. A module whose result is visible only as printed text therefore has no behavior in silicon. Keep system tasks in testbenches or clearly simulation-only code, and expose a module's results through its interface and state.

5. Common mistakes

5.1 split result widths that do not add up

Bit#(12) frame = 12'ha5c;

// Wrong: 4 + 4 is not 12, so Add#(4, 4, 12) has no instance (T0031)
Tuple2#(Bit#(4), Bit#(4)) bad = split(frame);

// Right: the result widths sum to the input width
Tuple2#(Bit#(4), Bit#(8)) good = split(frame);

The error points at the split call, but the thing to fix is the result type. Write the field widths down first and check that they sum to the input width.

5.2 Guarding a producer with notEmpty

// Wrong: a producer that waits for data instead of room
rule produce (queue.notEmpty);
  queue.enq(x);
endrule

// Right: a producer asks whether there is room
rule produce (queue.notFull);
  queue.enq(x);
endrule

notEmpty answers the consumer's question. With the wrong flag, the producer stays idle while the FIFO is empty, which is exactly when it should run.

5.3 Expecting deq to change first inside the same rule

rule takeTwo;
  Bit#(8) a = queue.first;
  queue.deq;
  Bit#(8) b = queue.first;   // still the same entry as a
endrule

Both reads of first see the start of the cycle, so a and b are equal. Taking two entries needs a different structure, such as two FIFOs, or calls spread over two cycles.

6. Summary

7. Check your understanding

1. Where does split get its boundary, and at which stage is a wrong boundary reported?

   Show answer

   From the result type. The compiler solves m and n from the two result widths and checks Add#(m, n, mn). Widths that do not sum to the input width fail during type checking with T0031, before any hardware exists.

2. Why does first return the entry that deq removes when one rule calls both?

   Show answer

   first is a value method and, on mkFIFO, reports the state at the start of the cycle. deq is an Action whose effect commits at the end of the cycle. Inside one atomic rule, statement order does not make the removal visible early.

3. A two-entry FIFOF holds one entry. What are notFull and notEmpty, and which one should a producer check?

   Show answer

   Both are true: there is room for one more entry and one entry to read. A producer checks notFull; notEmpty belongs to the consumer.

4. With mkSizedFIFO(1), which rule stalls in FIFOOrder.bsv, and why is there no error message?

   Show answer

   enqueueSecond stalls, because its enq targets a full FIFO and the implicit condition is false. A false implicit condition only keeps a rule from firing; it is not an error. Since step never advances, no other rule fires either, and the run ends at the time limit.

Each Practice problem below reuses one contract from this chapter: a method that divides a 12-bit frame into a 4-bit kind and an 8-bit payload, a queue method that must return and remove the oldest buffered byte, and an elastic queue that reports it cannot accept data even while it is empty.