blarney-lang / blarney

sort [3,4,1,0,2] = [0,1,2,3,4]

Sorting makes for a good introduction to the library. Let’s start with the simplest kind of sorter possible: given a pair of 8-bit values, the function twoSort returns the sorted pair.

This definition makes use of three Blarney constructs: the Bit type for bit vectors (parametised by the size of the vector); the comparison operator .<.; and the ternary conditional operator ?. A quick test bench to check that it works:

We use Blarney’s always construct to perform the given action on every clock cycle. Blarney actions include statements for displaying values during simulation (display), terminating the simulator (finish), and mutating state (see below). All statements in an Action execute in parallel, within a single cycle of an implicit clock. We can generate Verilog for the test bench as follows.

Assuming the above code is in a file named Sorter.hs, it can be compiled at the command-line using

where blc stands for Blarney compiler. This is just a script (from Blarney’s Scripts directory) that invokes GHC with the appropriate compiler flags. Running the resulting executable ./Sorter will produce Verilog in the /tmp/twoSort directory, including a makefile to build a Verilator simulator. The simulator can be built and run as follows.

Sometimes it can be convenient to skip Verilog generation, and use the in-Haskell simulator.

Now after running ./Sorter we see the test bench output directly.

The in-Haskell simulator is much slower than Verilator, but can be more convenient for small designs. It is currently an experimental feature.

We can build a general N-element sorter by connecting together multiple two-sorters. One of the simplest ways to do this is the bubble sort network. The key component is a function bubble that takes a list of inputs and returns a new list in which the smallest element comes first.

If we repeatedly call bubble then we end up with a sorted list.

Running the test bench

in simulation yields:

To see that the sort function really is describing a circuit, let’s draw the circuit digram for a 5-element bubble sorter.

The input list is supplied on the left, and the sorted output list is produced at the bottom. Each + denotes a two-sorter that takes inputs from the top and the left, and produces the smaller value to the bottom and the larger value to the right. See The design and verification of a sorter core for a more in-depth exploration of sorting circuits in Haskell.

For simplicity, we’ve made our sorter specific to lists of 8-bit values. But if we look at the types of the primitive functions it uses, we can see that it actually has a more general type.

So .<. can be used on any type in the Cmp (comparator) class. Similarly, ? can be used on any type in the Bits class (which allows packing to a bit vector and back again). So a more generic definition of twoSort would be:

Indeed, this would be the type inferred by the Haskell compiler if no type signature was supplied. Using Haskell’s rebindable syntax, we can also use an if-then-else expression instead of the ternary conditional operator:

So far, we’ve only seen display and finish actions inside a Blarney module. Also supported are creation and assignment of registers. To illustrate, here is a module that creates a 4-bit cycleCount register, increments it on each cycle, stopping when it reaches 10.

This example introduces a number of new library functions: makeReg creates a register, initialised to the given value; the val field yeilds the current value of the register; and when allows conditional actions to be introduced. We can use if-then-else in an Action context. For example, the final three lines above could have been written as:

Running top in simulation gives

Queues (also known as FIFOs) are a commonly used abstraction in hardware design. Blarney provides a range of different queue implementations, all of which implement the following interface available when importing Blarney.Queue.

The type Queue a represents a queue holding elements of type a, and provides a range of standard functions on queues. The enq method should only be called when notFull is true and the deq method should only be called when canDeq is true. Similarly, the first element of the queue is only valid when canDeq is true. Below, we present the simplest possible implementation of a one-element queue.

The following simple test bench illustrates how to use a queue.

Wires are a feature of the Action monad that offer a way for separate action blocks to communicate within the same clock cycle. Whereas assignment to a register becomes visible on the clock cycle after the assigment occurs, assignment to a wire is visible on the same cycle as the assignment. If no assignment is made to a wire on a particular cycle, then the wire emits its default value on that cycle. When multiple assignments to the same wire occur on the same cycle, the wire emits the bitwise disjunction of all the assigned values.

To illustrate, let’s implement an n-bit counter module that supports increment and decrement operations.

We’d like the counter to support parallel calls to inc and dec. That is, if inc and dec are called on the same cycle then the counter’s output is unchanged. We’ll achieve this using wires.

State machines are a common way of defining the control-path of a circuit. They are typically expressed by doing case-analysis of the current state and manually setting the next state. Quite often however, they can be expressed more neatly in a Recipe — a simple imperative language with various control-flow constructs.

To illustrate, here is a small state machine that computes the factorial of 10.

Blarney provides a lightweight compiler for the Recipe language (under 100 lines of code), which we invoke above through the call to runRecipe.

A very common use of recipes is to define test sequences. For example, here is a simple test sequence for the Counter module defined earlier.

Here, we increment counter on the first cycle, and then again on the second. On the third cycle, we both increment and decrement it in parallel. On the fourth cycle, we display the value and terminate the simulator.

For convenience, recipes can also be constucted using do notation. The Stmt monad is simply a wrapper around Recipe, which defines monadic bind as sequential composition. It is entirely syntatic sugar, providing no new functionality.

To illustrate, here’s the factorial example from earlier, rewritten using the Stmt monad.

We have found that some users prefer Recipe syntax, while others prefer Stmt syntax, so we offer both.

Blarney provides a variety of block RAM modules commonly supported on FPGAs. They are all based around the following interface.

When a load is issued for a given address, the value at that address appears on out on the next clock cycle. When a store is issued, the value is written to the RAM on the current cycle, and a load of the new value can be requested on the subsequent cycle. A parallel load and store should only be issued on the same cycle if the RAM has been created as a dual-port RAM (as opposed to a single-port RAM). To illustrate, here is a test bench that creates a single-port block RAM and performs a store followed by a load.

Somewhat-related to block RAMs are register files. The difference is that a register file allows the value at an address to be determined within a clock cycle. It also allows any number of reads and writes to be performed within the same cycle. Register files have the following interface.

To read from a register file, use the index method or the generic lookup operator !. Unlike block RAMs, register files (especially large ones) do not always map efficiently onto hardware, so use with care!

Sources and sinks are commonly-used flow-control abstractions in hardware description. They are often used to implement hardware modules that produce or consume data at a variable rate, depending on internal details of the module that the implementer does not wish to (or is unable to) expose. In Blarney, sources and sinks are captured by the following interfaces.

A queue is both a source and a sink.

Sources and sinks can be connected together.

Note that taking a sink as a function argument (input) is very similar to returning a source as a function result (output). Both allow the function to produce data at a variable rate. Is it therefore redundant to provide both Source and Sink? Not quite. When a function takes a sink as input, it knows when the caller is ready to consume before producing data; when a function returns a source as output, it knows when the caller does consume after producing data. This subtle difference can be important when the programmer wants minimise buffering and latency between producer and consumer. Often though, we don’t mind buffering (it’s good for Fmax) so our convention is to use the Stream type in most circumstances.

As an example, here’s a function that increments each value in an input stream to produce an output stream.

So far we’ve seen examples of top-level modules, i.e. modules with no inputs or outputs, being converted to Verilog. In fact, any Blarney function whose inputs and outputs are members of the Interface class can be converted to Verilog (and the Interface class supports generic deriving). To illustrate, we can convert the function inc (defined above) into a Verilog module as follows.

The generated Verilog module /tmp/inc/inc.v has the following interface:

Considering the definition of the Stream type, the correspondance between the Blarney and the Verilog is quite clear:

It is also possible to instantiate a Verilog module inside a Blarney description. To illustrate, here is a function that creates an instance of the Verilog inc module shown above.

Notice that interface of the Verilog module being instantiated is determined from the type signature. Here’s a sample top-level module that uses the makeInc function:

Using the following main function we can generate both the inc module and a top-level module that instantiates it.

Using this approach, we can maintain the module hierarchy of a Blarney design whenever we generate Verilog, rather than having to flatten it to big monolithic netlist. This technique can also be used to instantiate any Verilog module within a Blarney design.

When simply marking netlist boundaries within a Blarney design, the makeInstance/writeVerilogModule combination is rather low-level and error-prone. In particular, there is no requirement for the type of the instance to match the type of the module, and it would be nice to specify a boundary in a backend-independent way. To solve these problems, Blarney provides a makeBoundary function. We can now define makeInc as:

Unlike makeInstance, makeBoundary takes the module to instantiate as an argument. The type of the argument to makeBoundary must match the return type:

This means that it is unncessary to supply a type signature for makeInc now; it will be inferred. Furthermore, the top-level of our design no longer needs to call writeVerilogModule for the inc module because Blarney now knows how to generate a module for any instance that it encounters.

This is a common pattern in hardware design. Suppose we wish to move a multiplier out of a module and into an separate slave module, where the slave takes requests (pairs of 32-bit integers to multiply) and produces responses (32-bit results).

The slave component might be defined as:

The master component produces requests for the slave, and consumes responses from the slave. In the example below, the master simply asks the slave to multiply 2 by 2, waits for the response, and then terminates the simulation.

The top-level module which connects the master and the slave needs to introduce a cycle, which can be achieved simply using Haskell’s recursive-do (mdo) notation:

Sum types such as

do not permit generic deriving for the Bits class, so cannot be used for circuit-time values. (An elaboration-time value cannot be influenced by a circuit-time value, making the definition of unpack problematic for sum types, at least without resorting to language plugins). However, Blarney does support tagged unions, allowing the following definition.

The API for tagged unions is illustrated by the sample functions below.

Bit selection operators are used to extract a subset of bits out of a bit-vector. There are different flavours, depending on whether the indices are type-level numbers, elaboration-time numbers, or circuit-level numbers.

For type-level indices, we provide functions at and slice, and use type application to specify the type-level indices:

For elaboration-time indices of type Int, we provide unsafeAt and unsafeSlice:

The argument to unsafeAt could be out of range, and the result of unsafeSlice could have a different width to that implied by the range. Such cases will lead to confusing error messages, hence the "unsafe" prefix on the function names.

Finally, for circuit-level indicies of type Bit n, the generic lookup operator ! can be used:

Blarney’s generic lookup operator x!i returns the element of x at index i, and works for many different types of x and i. See Lookup for more details.

Recent work on specifying and implementing ISAs led us to develop two libraries for doing bit-string pattern matching. The first, BitPat, is statically-typed and based on the paper Type-safe pattern combinators. The second, BitScan, is dynamically typed but more expressive. As an example, BitScan, let’s us define the following instruction decoder for a tiny subset of RISC-V.

The nice thing about this decoder is that the scattered immediate field imm in the sw instruction is automatically assembled by the library. That is, the imm[11:5] part of the immediate is combined with the imm[4:0] part to give the final 12-bit immediate value passed to the right-hand-side function. Scattered immediates appear a lot in the RISC-V specification. Thanks to Jon Woodruff for suggesting this feature! For a fuller example of the BitScan module, see the Pebbles RV32I instruction decoder.

A few processor cores have been implemented in Blarney:

• Simple: 4-stage 8-bit CPU, with just 4 instructions, for learning.

• Pebbles: RISC-V CPU+GPU using plugable pipelines.

• Actora: 3-stage stack machine that runs code written a subset of Erlang.

One of the classic limitations of Lava is that identifier names are lost when the netlist is generated. In particular, this is problematic when we want to analyse, say, the critical-path of our circuit using a third-party tool, but there is no way to map the netlist names reported by the tool back to the Lava names in the original description.

Blarney provides a solution to this problem in the form of the Namer plugin. This is a simple GHC plugin (around 150 lines of code) that looks for monadic bindings of the form

where m has type Module a for any a, and automatically rewrites the binding as

where withName is a Blarney primitive that introduces name information inside m This simple approach captures quite a lot of useful names.

The plugin is completely optional, and disabled by default. To enable it, first install using cabal

and then pass the --enable-namer-plugin flag to blc.

To further improve the readability of generated code, we can also pass the --enable-name-prop and --enable-simplifier options to our circuit generator. This will enable the (experimental) name propagation and netlist simplification passes respectively.

Any type in the Bits class can be represented in hardware, e.g. stored in a wire, a register, or a RAM.

The Bits class supports generic deriving. For example, suppose we have a simple data type for memory requests:

To make this type a member of the Bits class, we have suffixed it with derving (Generic, Bits). The generic deriving mechanism for Bits does not support sum types: there is no way to convert a bit-vector (run-time circuit value) to a sum type (elaboration-time value) using the circuit primitives provided by Blarney (however, see tagged unions).

Any type in the Interface class can be used as a module input or output when doing modular compilation. Furthermore, collections of interfaces can be indexed by circuit-time values using the ! operator. To illustrate, here is an example circuit to split a stream of MemReq into four streams, using the lower two bits of the address to decide which output stream to use.

The Interface class supports generic deriving: just add Interface to the deriving clause for the datatype. In the above example, MemReq is an Interface, and so too is Queue a for any a that is also an Interface.

The generic lookup operator ! is provided by the Lookup class.

A wide range of combinations of types are supported. The functional dependency c → e allows the return type to be inferred from the collection type.

Any value whose type is in the FShow class, or any value of type Format, can be passed as arguments to the variadic display function.

As an example, here is how the FShow instance for pairs is defined.

The FShow class supports generic deriving.

The radix and padding used to display a bit vector can be specified using the following functions.

The FShow instance for Bit n uses decimal format with no padding.

The Cmp (comparator) class provides a range of familiar comparison operators, and supports generic deriving.

Only the first three operators must be defined; the others have default definitions.

The assignment operator is overloaded.

Example instances are Reg, Wire, and WriteOnly.

Converting interfaces to sources and sinks may turn out to be common. For example, Queue and Stack are both sources and sinks. Therefore the following type classes are provided.