Home

Awesome

BitPat

BitPat is a bit-string pattern matching library for Bluespec, inspired by Morten Rhiger's "Type-Safe Pattern Combinators".

An example

To get a taste of BitPat, here's a simple instruction decoder:

import BitPat :: *;

function Action add(Bit#(5) rs2, Bit#(5) rs1, Bit#(5) rd) = action
  $display("time %0t - add %0d, %0d, %0d", $time, rd, rs1, rs2);
endaction;

function Action addi(Bit#(12) imm, Bit#(5) rs1, Bit#(5) rd) = action
  $display("time %0t - addi %0d, %0d, %0d", $time, rd, rs1, imm);
endaction;

module top ();
  // Example instruction
  Bit#(32) instr = 32'b0000000_00001_00010_000_00011_0110011;

  // Decoder
  genRules(
    switch(instr,
      when(pat(n(7'b0000000), v, v, n(3'b000), v, n(7'b0110011)), add),
      when(pat(               v, v, n(3'b000), v, n(7'b0010011)), addi)
    )
  );
endmodule

The case subject in the first argument of switch is matched against the pattern in the first argument of when and guards the right-hand-side function provided in the second argument of when. The genRules function then derives the actual Bluespec rules to execute the machine described.

The n combinator matches a specified numeric literal, whereas the v combinator (which stands for variable) matches any bit string and passes that bit string as an argument to the right-hand-side function. The width of the bit-string matched by v is inferred from the width of the corresponding function argument on the right-hand-side.

Getting started

The library sources are contained in BitPat.bsv. Examples are also provided as ExampleX.bsv and can be built on a system with a working installation of Bluespec by typing make. They can each be run with ./exampleX.

Library overview

The BitPat Bluespec module provides bit-pattern combinators for composing a pattern to match a case subject of width n.

typedef function Tuple2#(Bool, t1) f(Bit#(n) x, t0 k)
  BitPat#(numeric type n, type t0, type t1);

A BitPat pattern can be created using the pat function with any sequence of pattern combinators as arguments. For example, pat(n(8'b00010011)) is a pattern that will match a case subject value 8'b00010011 using the n combinator. Specific fields of the case subject can be extracted using the v combinator. For example, pat(n(3'b000),v,n(2'b11)) matches a bit string beginning with 000 and ending with 11, with anything in between. See the Pattern combinators section for details on available pattern combinators.

The Guarded polymorphic type is used to represent the result of matching the case subject against a pattern.

typedef struct {
  Bool guard;
  a val;
} Guarded#(type a);

The guard boolean field will carry the success/failure of a match, and the val field will carry the result of the right-hand-side function, typically an Action.

The when function

function Guarded#(a) when(BitPat#(n, t, a) p, t f, Bit#(n) s);

is used to apply a pattern. It recieves a pattern p together with a right-hand-side function f, and the case subject s to match against in the form of a bit string. The pattern p must be of the same bit-width as the case subject s. If the right-hand-side f recieves arguments, they should be declared in the pattern p using an appropriate combinator. The sizes and positions of the arguments of the right-hand-side f will define the bit-fields in the case subject s that will be passed to f. For example, if the right-hand-side function

function Action add(Bit#(5) rs2, Bit#(5) rs1, Bit#(5) rd) = action
  $display("time %0t - add %0d, %0d, %0d", $time, rd, rs1, rs2);
endaction;

and the pattern

pat(n(7'b0000000), v, v, n(3'b000), v, n(7'b0110011))

are matched against a 32-bit case subject, then the 3 n pattern combinators respectively match 7, 3 and 7 bits each, and each one of the 3 arguments of add are 5 bits wide.

In the following

Bit#(32) instr = 32'b0000000_00001_00010_000_00011_0110011;
Guared#(Action) gAct= when(pat(n(7'b0000000), v, v, n(3'b000), v, n(7'b0110011)), add, instr);

gAct is a Guarded#(Action) which will have its guard field set to True because:

Additionally, gAct will have its val field set to the value returned by a call to add with the following arguments:

That is, gAct.val is the same as add(instr[24:20], instr[19:15], instr[11:7]) or add(5'b00001, 5'b00010, 5'b00011).

Extra utility functions

function BitPat#(n, t0, t1) guarded(BitPat#(n, t0, t1) p, function Bool g(Bit#(n) x))

The function simply wraps a classic pattern (obtained with standard pat call) and takes a predicate that will be applied to the case subject in its entirety. The final guard is the logical and of this predicate and the standard guard. Note: the gv combinator described in the Pattern combinators section provides a similar but more local functionality.

function Action add(Bit#(5) rs2, Bit#(5) rs1, Bit#(5) rd) = action
  $display("time %0t - add %0d, %0d, %0d", $time, rd, rs1, rs2);
endaction;
function Action addi(Bit#(12) imm, Bit#(5) rs1, Bit#(5) rd) = action
  $display("time %0t - addi %0d, %0d, %0d (rd == 5)", $time, rd, rs1, imm);
endaction;
// some bit strings
Bit#(32) instr = 32'b0000000_00001_00010_000_00011_0110011; // maps to add
//Bit#(32) instr = 32'b0000000_00001_00010_000_00011_0010011; // maps to addi
List#(Guarded#(Action)) gActs = switch(instr,
  when(pat(n(7'b0000000), v, v, n(3'b000), v, n(7'b0110011)), add),
  when(pat(v, v, n(3'b000), v, n(7'b0010011)), addi)
);

Here, gActs is a list of the Guarded#(Action) returned by the add and addi when applied with the provided instr according to their respective patterns. Note that it is necessary for the return type of add and addi to be consistent (i.e. for switch to work, add and addi must return the same type).

function a pick(List#(Guarded#(a)) xs)
typeclass RulesGenerator#(type a);
  module rulesGenerator#(List#(Guarded#(a)) xs) (Tuple2#(Rules, PulseWire));
endtypeclass

An instance of RulesGenerator is defined in the BitPat library for the Action and List#(Action) Bluespec types. Invoking the rulesGenerator module will return a set of Rules corresponding to the Actions or sequences of Actions to execute when the guarding conditions are met. The returned PulseWire is a done signal indicating that the currently triggered rule/rules is/are done executing. It simply requires to be passed a List#(Guarded#(Action)) or List#(Guarded#(List#(Action))) and can be used as follows:

module top();
  match {.allRules, .done} <- rulesGenerator(gActs);
  addRules(allRules);
endmodule
module top();
  genRules(gActs);
endmodule

Pattern combinators

function BitPat#(n, t0, t0) n(Bit#(n) x)
function BitPat#(n, function t0 f(Bit#(n) x), t0) v()
function BitPat#(n, function t0 f(Bit#(n) x), t0) sv(Integer x)
function BitPat#(n, function t0 f(Bit#(n) x), t0) gv(function Bool g(Bit#(n) x))