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
.
- Example0.bsv is the short example presented in this README
- Example1.bsv makes use of advances features and uses the
Action
RulesGenerator instance - Example2.bsv makes use of advances features and uses the
List#(Action)
RulesGenerator instance - Example3.bsv uses BitPat in a purely combinational context
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:
-
the
n(7'b0000000)
pattern operating on bits 31 to 25 of the case subject is satisfied:instr[31:25] == 7'b0000000
-
the
n(3'b000)
pattern operating on bits 14 to 12 of the case subject is satisfied:instr[14:12] == 3'b000
-
the
n(7'b0110011)
pattern operating on bits 6 to 0 of the case subject is satisfied:instr[6:0] == 7'b0110011
Additionally, gAct
will have its val
field set to the value
returned by a call to add
with the following arguments:
-
the first
v
pattern combinator corresponds to the firstBit#(5)
argumentrs2
and will have the value of the case subject at position 24 to 20, that isinstr[24:20]
or5'b00001
-
the second
v
pattern combinator corresponds to the secondBit#(5)
argumentrs1
and will have the value of the case subject at position 19 to 15, that isinstr[19:15]
or5'b00010
-
the third
v
pattern combinator corresponds to the thirdBit#(5)
argumentrd
and will have the value of the case subject at position 11 to 7, that isinstr[11:7]
or5'b00011
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
- The
guarded
function is provided to predicate a whole pattern:
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.
- The BitBat library provides a
switch
function to composeGuarded
types together in aList
:
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).
- The
pick
function is provided to return the firsta
with a guard ofTrue
out of aList#(Guarded#(a))
:
function a pick(List#(Guarded#(a)) xs)
- The
RulesGenerator
typeclass defines therulesGenerator
module as follows:
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 Action
s or sequences of Action
s 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
- The
genRules
module is a wrapper around therulesGenerator
that performs theaddRules
and does not provide explicit handles to the generated rules or done signal. It can be used as follows:
module top();
genRules(gActs);
endmodule
Pattern combinators
- The
n
numeric literal combinator expects aBit#(n)
as argument. It advances the case subject's bit string and returnsTrue
on successfull match, or simply returnsFalse
on failure.
function BitPat#(n, t0, t0) n(Bit#(n) x)
- The
v
variable combinator takes no argument. It advances the case subject's bit string by the size of the next argument in the continuation which gets partially applied with the value extracted from the bit string, and always returnsTrue
.
function BitPat#(n, function t0 f(Bit#(n) x), t0) v()
- The
sv
sized variable combinator is similar to the variable combinator, but takes anInteger
as argument to provide more rich compile time errors when there is a size mismatch between the pattern and the continuation's argument.
function BitPat#(n, function t0 f(Bit#(n) x), t0) sv(Integer x)
- The
gv
guarded variable combinator is similar to the variable combinator, but take a predicate functiong
. The guard returned by the combinator is the result ofg
applied to the value extracted from the bit string.
function BitPat#(n, function t0 f(Bit#(n) x), t0) gv(function Bool g(Bit#(n) x))