10User-defined types

1. Ground rules for typedef

A typedef lets you define the types your design actually talks about: a new name for an existing type, a set of named states, a record of several fields, or a value that takes one of several forms. When you use types that carry meaning instead of raw bit vectors, values mixed up by mistake are caught as type errors before any hardware is generated. This chapter covers type synonyms, enums, structs, and tagged unions.

Most examples here build a value in a single rule, print it with $display, and stop. Since the topic is type declarations, focus on the printed values and widths rather than on cycle traces. The width lines use valueOf(SizeOf#(T)): SizeOf#(T) is the width of T as a numeric type, and valueOf turns it into an integer you can print. The bit widths themselves come from the types chapter.

1.1 Where a typedef goes

User-defined types are declared only at the top level of a package. You cannot declare one inside a module or function; there is no local typedef.

package Cpu;

typedef Bit#(8) Byte;        // fine: package top level

module mkCpu(Empty);
  // typedef Bit#(4) Nibble; // not allowed inside a module
endmodule

endpackage

Note. If a module needs a local name for a type, use the Alias, NumAlias, or StrAlias provisos. The names they introduce are type variables, not types, so they start with a lowercase letter.

1.2 Each typedef makes a new type

An enum, struct, or union must be named by a typedef before you can use it. Unlike C, you cannot write an anonymous struct as the type of a variable or argument.

Each typedef that defines an enum, struct, or union creates a type distinct from every other type. Two structs with identical field names and identical field types are still different types, and assigning one to the other is a type error. Only a synonym is interchangeable with the type it names.

1.3 Capitalization

2. Type synonyms

2.1 Declaring a synonym

A type synonym gives an existing type another name. It does not create a new type.

Form

typedef ExistingType NewName;

typedef Bit#(8)   Byte;
typedef UInt#(16) Address;

Byte and Bit#(8) are one type under two names. You can assign between them without conversion, and error messages treat them as the same type. A synonym takes no deriving clause: Byte simply uses every instance Bit#(8) already has.

A synonym may name another synonym, and since an interface is a type, an interface can be given a synonym the same way.

2.2 Synonyms with parameters

Adding #(...) parameters after the name makes a polymorphic synonym.

Form

typedef ExistingType NewName#(type typeVariable);
typedef ExistingType NewName#(numeric type sizeVariable);

typedef Int#(n) MyInt#(numeric type n);
typedef Bit#(TAdd#(n, 1)) Wider#(numeric type n);

TAdd#(n, 1) is a type function that computes n + 1 at the type level.

Note. When a parameter stands for a size and its use does not make that clear, declare it numeric type n. Declared as plain type n, bsc treats it as an ordinary, non-numeric type.

2.3 Example: a synonym only renames

TypeSynonym.bsv declares two synonyms. Read the two typedef lines, then the three locals in rule show. Notice that the assignment raw = named has no conversion of any kind.

Predict before you run. How many bits does five have? What does the SizeOf Byte line print?

package TypeSynonym;

// A type synonym names an existing type. It introduces no new type:
// Byte and Bit#(8) are interchangeable everywhere.
typedef Bit#(8) Byte;

// A synonym may take parameters, which makes it polymorphic.
typedef Bit#(TAdd#(n, 1)) Wider#(numeric type n);

(* synthesize *)
module mkTop(Empty);

  rule show;
    Byte    named = 8'd200;
    Bit#(8) raw   = named;      // no conversion: the two types are the same
    Wider#(4) five = 5'b10011;

    $display("Byte        = %0d", named);
    $display("Bit#(8)     = %0d", raw);
    $display("Wider#(4)   = %b", five);
    $display("SizeOf Byte = %0d", valueOf(SizeOf#(Byte)));
    $finish(0);
  endrule

endmodule

endpackage

Check the result.

Try it yourself.

3. Enums

3.1 Declaring an enum

An enum creates a new type whose only values are the labels you list.

Form

typedef enum { Label1, Label2, ... } TypeName deriving (instances);

typedef enum { Fetch, Decode, Execute } Stage deriving (Bits, Eq, FShow);

You cannot assign a number to a Stage or compare one against an integer. Two different enums may reuse the same label.

3.2 What deriving gives you

3.3 Encodings

Without explicit encodings, the first label is 0 and each later label adds 1. The width is the smallest number of bits that holds the largest encoding.

When something outside the source fixes the codes, write them with =.

Form

typedef enum { Label1 = value, Label2 = value, ... } TypeName deriving (...);

typedef enum { Idle = 0, Busy = 4, Done } State deriving (Bits, Eq);

A label without a value takes the previous value plus one, so Done is 5. The largest encoding is 5, so the width is 3 bits. Giving two labels the same encoding is compile error T0069.

3.4 Example: names versus encodings

EnumType.bsv prints one Stage value four ways. Read the label list before the deriving clause: fshow shows the name, pack shows the bits.

Predict before you run. What does the is Decode line print? How wide is Stage?

package EnumType;

// An enum introduces a new type whose values are the listed labels.
// deriving supplies the instances the compiler needs to store it in
// hardware (Bits), compare it (Eq), and print it (FShow).
typedef enum { Fetch, Decode, Execute } Stage deriving (Bits, Eq, FShow);

(* synthesize *)
module mkTop(Empty);

  rule show;
    Stage current = Decode;

    // fshow prints the label; pack shows the encoding the compiler chose.
    $display("label    = ", fshow(current));
    $display("encoding = %b", pack(current));
    $display("is Decode = ", fshow(current == Decode));
    $display("width     = %0d", valueOf(SizeOf#(Stage)));
    $finish(0);
  endrule

endmodule

endpackage

Check the result.

Try it yourself.

4. Structs

4.1 Declaring a struct

A struct is a type made of named fields, all present at the same time.

Form

typedef struct {
  FieldType fieldName;
  ...
} TypeName deriving (instances);

typedef struct {
  Byte addr;
  Bool write;
} Request deriving (Bits, Eq, FShow);

4.2 Building a value and reading fields

Form

TypeName { field1: value, field2: value }   // construction
variable.field                              // read
variable.field = newValue;                  // update one field of a local

Request req = Request { addr: 8'h40, write: True };
Byte a = req.addr;     // 8'h40
req.write = False;     // changes only the write field of req

4.3 Bit layout

In the representation produced by deriving (Bits), the field declared first occupies the most significant bits. For Request, addr is bits 8..1 and write is bit 0. You never need to compute those positions to read a field, though. Reading by name returns the same value even if the declaration order changes.

4.4 Example: reading fields by name

StructType.bsv builds one Request and prints its fields, the whole value, and its width. Trace each initializer to the $display that reads it.

Predict before you run. What does the addr line print with %h? What does fshow(req) on the whole line look like?

package StructType;

// A struct groups named fields. Field names start lowercase.
typedef struct {
  Bit#(8) addr;
  Bool    write;
} Request deriving (Bits, Eq, FShow);

(* synthesize *)
module mkTop(Empty);

  rule show;
    Request req = Request { addr: 8'h40, write: True };

    // A field is read with dot notation.
    $display("addr    = %h", req.addr);
    $display("write   = ", fshow(req.write));
    $display("whole   = ", fshow(req));
    // The width is the sum of the field widths: 8 + 1.
    $display("width   = %0d", valueOf(SizeOf#(Request)));
    $finish(0);
  endrule

endmodule

endpackage

Check the result.

Try it yourself.

1. Write the construction as Request { write: True, addr: 8'h40 }. Nothing in the output changes: construction and use are linked by field name, not by position.
2. Add req.write = False; on the line after the construction. Only the write and whole lines change to False; addr is untouched.

5. Tagged unions

5.1 Declaring a tagged union

A tagged union holds exactly one of its alternatives and stores a tag that records which one.

Form

typedef union tagged {
  MemberType TagName;
  ...
} TypeName deriving (instances);

typedef union tagged {
  Byte    Immediate;
  Bit#(3) Register;
} Operand deriving (Bits, Eq, FShow);

5.2 Building a value

Form

tagged TagName value
tagged TagName            // void member

Operand a = tagged Immediate 8'd200;
Operand b = tagged Register 3'd7;

A member of type void is an alternative that carries no value. The Prelude's Maybe is built this way:

typedef union tagged {
  void Invalid;
  t    Valid;
} Maybe#(type t) deriving (Eq, Bits);

Maybe#(Bit#(8)) m    = tagged Valid 8'd5;
Maybe#(Bit#(8)) none = tagged Invalid;

5.3 How this differs from a C union

The tag is stored with the value, which is what separates a tagged union from a C union. SystemVerilog also has untagged unions; BSV has only tagged ones.

Note. Direct member selection such as op.Immediate is legal, but when op holds a different tag the result is undefined. It compiles, so type checking will not catch the mistake. To check the tag before taking the value, use pattern matching as in section 7.

5.4 Example: two values, two alternatives

TaggedUnion.bsv builds two values of the same type Operand: fromRegister holds the Register alternative and fromImmediate holds Immediate.

Predict before you run. Does fshow print the tag name too? How is 200 printed in hexadecimal?

package TaggedUnion;

// A tagged union holds exactly one of its alternatives, and remembers which.
// Tag names start uppercase. The two alternatives have deliberately
// different widths.
typedef union tagged {
  Bit#(8) Immediate;
  Bit#(3) Register;
} Operand deriving (Bits, Eq, FShow);

(* synthesize *)
module mkTop(Empty);

  rule show;
    Operand fromRegister  = tagged Register 3'd7;
    Operand fromImmediate = tagged Immediate 8'd200;

    $display("register  = ", fshow(fromRegister));
    $display("immediate = ", fshow(fromImmediate));
    // 1 tag bit plus the largest member, which is Immediate at 8 bits.
    $display("width     = %0d", valueOf(SizeOf#(Operand)));
    $finish(0);
  endrule

endmodule

endpackage

Check the result.

6. Computing packed widths

6.1 Width rules

The width of a deriving (Bits) representation depends on the kind of type.

Request and Operand are both 9 bits, for unrelated reasons. A Register value in Operand uses only the low 3 of the 8 payload bits; the bits above it are undefined. The tag sits in the most significant bits.

Note. Equal widths do not mean compatible layouts, and the two types still cannot be assigned to each other. Width tells you the storage cost, not whether two types are interchangeable.

6.2 Example: three widths

Widths.bsv prints only the widths of the three types. Work out all three from the rules above before you run it.

package Widths;

typedef enum { Fetch, Decode, Execute } Stage deriving (Bits, Eq);

typedef struct {
  Bit#(8) addr;
  Bool    write;
} Request deriving (Bits, Eq);

typedef union tagged {
  Bit#(8) Immediate;
  Bit#(3) Register;
} Operand deriving (Bits, Eq);

(* synthesize *)
module mkTop(Empty);

  rule show;
    // An enum takes as many bits as its label count needs.
    $display("Stage   = %0d", valueOf(SizeOf#(Stage)));
    // A struct is the sum of its fields.
    $display("Request = %0d", valueOf(SizeOf#(Request)));
    // A union is its tag plus its largest member, not the one it holds.
    $display("Operand = %0d", valueOf(SizeOf#(Operand)));
    $finish(0);
  endrule

endmodule

endpackage

Check the result. Lines reading 2, 9, and 9 for Stage, Request, and Operand match the table. Note that Operand is 9 bits regardless of which alternative a value holds.

Try it yourself.

7. Reading a tagged union with pattern matching

7.1 case ... matches

You take a value out of a tagged union while checking its tag.

Form

case (expression) matches
  tagged Tag1 .name1 : statement;
  tagged Tag2 .name2 : statement;
endcase

case (op) matches
  tagged Immediate .v : $display("immediate %0d", v);
  tagged Register  .r : $display("register %0d", r);
endcase

The pattern matching chapter covers nested patterns and the other places a pattern may appear.

7.2 Covering every alternative

A case statement may leave alternatives out; if none matches, it does nothing. Things are different when a case must produce a value, such as in a function that returns from each arm. Current bsc may compile a version with a missing alternative, and if no arm matches, the result is unspecified. The compiler will not catch every omission, so cover every alternative yourself.

7.3 Example: taking out the value by tag

resolve in PatternMatching.bsv takes an Operand and returns an 8-bit value. Trace each input through tag check, binding, and result. Notice that the two alternatives carry values of different types.

Predict before you run. Which arm handles tagged Immediate 8'd200? Why does only the Register arm call zeroExtend?

package PatternMatching;

typedef union tagged {
  Bit#(8) Immediate;
  Bit#(3) Register;
} Operand deriving (Bits, Eq, FShow);

// The pattern introduces .value and .number; each is visible only in its
// own arm.
function Bit#(8) resolve(Operand op);
  case (op) matches
    tagged Immediate .value  : return value;
    tagged Register  .number : return zeroExtend(number);
  endcase
endfunction

(* synthesize *)
module mkTop(Empty);

  rule show;
    $display("Immediate 200 -> %0d", resolve(tagged Immediate 8'd200));
    $display("Register  7   -> %0d", resolve(tagged Register 3'd7));
    $finish(0);
  endrule

endmodule

endpackage

Check the result.

Try it yourself.

8. Putting it together

UserTypes.bsv uses all four kinds of user-defined type in one program. Note how the synonym Byte is reused as a struct field type and as a union member type.

Predict before you run. What widths do the last four lines print?

package UserTypes;

// A type synonym names an existing type. It introduces no new type:
// Byte and Bit#(8) are interchangeable everywhere.
typedef Bit#(8) Byte;

// An enum introduces a new type whose values are the listed labels.
// deriving supplies the instances the compiler needs to store it in
// hardware (Bits), compare it (Eq), and print it (FShow).
typedef enum { Fetch, Decode, Execute } Stage deriving (Bits, Eq, FShow);

// A struct groups named fields. Field names start lowercase.
typedef struct {
  Byte   addr;
  Bool   write;
} Request deriving (Bits, Eq, FShow);

// A tagged union holds exactly one of its alternatives, and remembers which.
// Tag names start uppercase. The two alternatives have deliberately
// different widths: the union is as wide as its tag plus its *largest*
// member, not the member currently in it.
typedef union tagged {
  Byte    Immediate;
  Bit#(3) Register;
} Operand deriving (Bits, Eq, FShow);

(* synthesize *)
module mkTop(Empty);

  rule show;
    Byte     b   = 8'd200;
    Stage    st  = Decode;
    Request  req = Request { addr: 8'h40, write: True };
    Operand  op  = tagged Register 3'd7;

    $display("b        = %0d", b);
    $display("stage    = ", fshow(st));
    $display("request  = ", fshow(req));
    $display("operand  = ", fshow(op));

    // A tagged union is read by matching on the tag.
    case (op) matches
      tagged Immediate .v : $display("immediate value %0d", v);
      tagged Register  .r : $display("register number %0d", r);
    endcase

    // SizeOf#(T) is a numeric *type*; valueOf turns it into an integer.
    // This is how a width becomes something you can print.
    $display("width Byte    = %0d", valueOf(SizeOf#(Byte)));
    $display("width Stage   = %0d", valueOf(SizeOf#(Stage)));
    $display("width Request = %0d", valueOf(SizeOf#(Request)));
    // 1 tag bit + 8 for Immediate, the larger member. Register needs 3.
    $display("width Operand = %0d", valueOf(SizeOf#(Operand)));
    $finish(0);
  endrule

endmodule

endpackage

Check the result.

9. Common mistakes

9.1 Assigning between two same-shaped structs

typedef struct { Bit#(8) addr; Bool write; } Request deriving (Bits);
typedef struct { Bit#(8) addr; Bool write; } Other   deriving (Bits);

// Wrong: these are different types
Other copy = req;

// Right: if conversion is intended, copy the fields explicitly
Other copy = Other { addr: req.addr, write: req.write };

Each typedef makes a separate type, so error T0020 reports the expected type Other against the inferred Request. If the two really mean the same thing, use one type in the first place.

9.2 Doing arithmetic on enum values

typedef enum { Red, Green, Yellow } Light deriving (Bits, Eq);

// Wrong: Light has no Arith instance
Light next = current + 1;

// Right: name the next state by label
function Light nextLight(Light l);
  case (l)
    Red:    return Green;
    Green:  return Yellow;
    Yellow: return Red;
  endcase
endfunction

The wrong version fails with T0031, reporting no instance Arith#(Light). Working around it with pack, + 1, and unpack compiles, but stepping past the last state yields a bit pattern that has no label.

9.3 Extracting a struct field by bit position

typedef struct { Bit#(4) kind; Bit#(4) len; } Packet deriving (Bits);

// Wrong: the low four bits are len, not kind
Bit#(4) k = pack(p)[3:0];

// Right
Bit#(4) k = p.kind;

The first-declared field sits in the high bits, so pack(p)[3:0] is len. Reading by bit position silently returns the wrong value whenever field order or widths change. Read fields by name.

9.4 Reading a member without checking the tag

// Wrong: undefined when op holds Register
Bit#(8) v = op.Immediate;

// Right: use the value only in the arm that checked the tag
case (op) matches
  tagged Immediate .imm : v = imm;
  tagged Register  .r   : v = zeroExtend(r);
endcase

Direct selection compiles, so there is no error message. If results are occasionally strange, look for places that read a union member directly.

9.5 Not deriving an instance you use

// Wrong: fshow is used, but there is no FShow
typedef enum { Fetch, Decode, Execute } Stage deriving (Bits, Eq);
$display("stage = ", fshow(s));

// Right
typedef enum { Fetch, Decode, Execute } Stage deriving (Bits, Eq, FShow);

The error is reported as T0031 at the line that calls fshow, not at the declaration. When you see a missing-instance error, check that type's deriving list.

10. Summary

11. Check your understanding

1. Why can a Byte be assigned to a Bit#(8) without conversion, while two identically shaped structs cannot be assigned to each other?

   Show answer

   A synonym creates no new type, so Byte and Bit#(8) are the same type. A typedef that defines a struct always creates a new type distinct from every other.

2. How many bits does an enum with five labels need?

   Show answer

   Three. The default codes run from 0 to 4, and holding 4 takes 3 bits.

3. Explain separately why Request and Operand are each 9 bits wide.

   Show answer

   Request is the sum of its fields: 8 bits of addr plus 1 bit of write. Operand is 1 tag bit plus its largest member, the 8-bit Immediate.

4. Why is pattern matching safer than op.Immediate for reading a tagged union?

   Show answer

   Direct selection does not check the tag, so it reads an undefined value when another alternative is held. Pattern matching binds the value only in the arm whose tag matched.

5. If you swap the declaration order of a struct's fields, what happens to req.addr and to pack(req)?

   Show answer

   req.addr reads by name and keeps its value. pack(req) changes layout, because the first-declared field occupies the high bits.

The Practice problems below move a pipeline-stage enum to its next stage by label rather than by encoding, fix code that reads a request struct through its packed bits and picks up the wrong field, and take the value out of a Maybe or return zero when there is none. For each, check first whether the code handles values by name or depends on bit positions and encodings. The next chapter puts an enum to work as the state of a machine.