Proposal: Calyx-to-FIRRTL backend to use ESSENT

[sampsyo]

This note is the outcome of a brief conversation with @sbeamer. There's no particular timeframe for actually attempting this project, but I wanted to jot down an outline of the idea before I forget the details.

---

An interesting and self-contained mini-project within the Calyx ecosystem would be to build a backend that generates FIRRTL and uses the ESSENT simulator to run it. The main reason I think this would be exciting is because ESSENT is supposed to be very fast; it offers very snazzy kind of optimizations that are not found anywhere else. For more details on why ESSENT is cool, check out the WOSET paper and the follow-up about RepCut. This mini-project would be useful on one hand for making Calyx simulations go fast, and on the other hand for providing interesting benchmarks for the ESSENT project.

As background, FIRRTL was originally created as the IR for the Chisel HDL. It has a lot of complexity that it inherits from Chisel itself, but at its core is a subset called "LoFIRRTL" that is actually quite simple—and it's what ESSENT consumes. I think it would not be hard to translate a lowered Calyx program into a subset of FIRRTL that is like LoFIRRTL with perhaps a couple of extra features from the rest of FIRRTL, which the existing FIRRTL compiler passes could easily compile away.

Overview of the Translation

Here's an example. A lowered Calyx program looks something like this (taken from the venerable language-tutorial-iterate example program):

component main(@go go: 1, @clk clk: 1, @reset reset: 1) -> (@done done: 1) {
  cells {
    @external @data mem = std_mem_d1(32, 1, 1);
    @data val = std_reg(32);
    @data add = std_add(32);
    ...
  }
  wires {
    done = tdcc_done.out ? 1'd1;
    fsm.write_en = early_reset_cond0_go.out ? 1'd1;
    fsm.clk = clk;
    fsm.reset = reset;
    fsm.in = fsm.out != 1'd0 & early_reset_cond0_go.out ? adder.out;
    fsm.in = fsm.out == 1'd0 & early_reset_cond0_go.out ? 1'd0;
    ...
  }
  control {}
}

That is, each component has input ports, output ports, cell instantiations, and a list of guarded assignments—and that's it. An equivalent FIRRTL program is pretty easy to imagine; it looks something like this:

circuit main :
  module main :
    input go: UInt<1>
    input clk: Clock
    input reset: UInt<1>
    output done: UInt<1>

    inst mem of std_mem_d1_32_1_1
    inst val of std_reg_32
    inst add of std_add_32

    when tdcc_done.out :
      done <= 1
    fsm.clk <= clk
    fsm.reset <= reset
    when and(neg(eq(fsm.out, 0)), early_reset_cond0_go.out) :
      fsm.in <= adder.out
    when and(eq(fsm.out, 0), early_reset_cond0_go.out) :
      fsm.in <= 0

This imaginary translation embodies these conversions:

• Calyx components become FIRRTL modules.
• Component input/output ports become input and output declarations.
• The module/component hierarchy remains intact; we can inst to instantiate all the cells.
• Calyx's guarded assignments become FIRRTL when conditions wrapped around simple connect (<=) statements.
• Calyx guard expressions become FIRRTL expressions using its built-in inventory of primitive operations, such as and, neg, and eq.

Overall, this translation seems—on the surface, at least—to be pretty straightforward; perhaps even more straightforward than our current Verilog backend.

Primitives

That std_mem_d1_32_1_1 instance betrays the one topic that I think will be medium-hard here: the standard library. Calyx's standard library of primitives is of course implemented in Verilog. So one obvious challenge here is that we would need to write a reasonable subset of these in FIRRTL (or Chisel, maybe), and we would need to somewhat generalize Calyx's extern functionality so it's not hard-coded to work with Verilog implementations of primitives.

A less-obvious issue is that FIRRTL does not support parameterization of FIRRTL modules. You can parameterize extmodules, which are FIRRTL's equivalent of Calyx's externs, i.e., a way to wrap external Verilog code. But AFAICT you can't parameterize FIRRTL modules, and we would want our primitives to be FIRRTL code so they can be simulated by ESSENT. This is actually extremely similar to Calyx, where Verilog-implemented Calyx primitives can be parameterized, but Calyx-implemented components cannot, and the former works by relying on Verilog parameters rather than doing any of its own metaprogramming/elaboration.

One possible milestone could take a first step by using extmodule to wrap our existing Verilog primitive implementations. This would of course not let us use ESSENT, but it would provide a shortcut to testing our FIRRTL codegen: we could compile the whole thing from FIRRTL+Verilog to plain Verilog using the normal FIRRTL compiler and then simulate it with Verilator.

But the ultimate goal, of course, is to provide FIRRTL implementations of parameterized Calyx primitives. So we need a way to implement stuff like std_mem_d1(32, 1, 1) in FIRRTL. This means that we will need FIRRTL generators for each primitive. (See #419 for the much broader topic of integrating parameterized generators with the broader Calyx ecosystem.) We could do this with hand-rolled metaprogramming (little Python scripts that generate FIRRTL code) or by writing Chisel code, which provides its own metaprogramming and compiles naturally to FIRRTL.

The Test Harness

We need test code to run Calyx programs using the usual workflow: fill up the std_mem_* memories with initial data, tell the circuit to go, wait until it's done, and then extract the final memory values. The first version of this ESSENT test harness should do this by loading values into the memories through the interface that ESSENT exposes for this purpose.

A subsequent version could use a seemingly-recently-added, not-really-documented feature in FIRRTL: an annotation that tells the simulator to load a memory's initial inputs from a file. The only problem is that @sbeamer tells me this is not yet supported in ESSENT, so we would need to first add support for it. That doesn't seem like a huge challenge, fortunately.

Evaluation

It would be interesting to recreate the evaluation from the Cider paper (i.e., to use the same suite of benchmarks, for starters) and compare the running times of Verilator, Icarus, Cider, and ESSENT. One interesting factor will be separating startup time from sustained performance; as a JVM application, ESSENT will have a startup cost but benefit from JIT optimization in the long term.

A Wildcard

The official FIRRTL Scala library has been deprecated in favor of the firtool compiler that is part of CIRCT. Hopefully this mostly doesn't affect this project. It does mean, however, that one way to generate FIRRTL code is via the firrtl MLIR dialect. One could even implement the whole Calyx-to-FIRRTL translator as a C++ project that starts with the calyx dialect. But it seems just as easy, and perhaps easier to maintain in the face of MLIR changes, to implement it as a backend for our Rust project that generates FIRRTL code as strings.

[rachitnigam]

Finally catching up with this! Thanks for the excellent summary @sampsyo! The FIRRTL extern situation is tricky but perhaps unsurprising given how complicated reasoning about parameterized modules is. I wonder what the Chisel solution was: they must have some representation of memories and other primitives within the language. Can we try to use them?

We should also ask @ekiwi about this integration. If we're careful in the integration effort, we might get a bunch of other Chisel infrastructure for free!

[sampsyo]

On the topic of parameterized memories and stuff in Chisel: I think the solution at the FIRRTL level is to use FIRRTL's extmodule. While FIRRTL modules can't be parameterized (so Chisel has to be pre-"elaborated" before emitting FIRRTL), extmodules can have parameters, and they map directly onto Verilog parameters. (Which is a surprisingly similar policy to Calyx's.)

So using those could almost work for us, because we have Verilog implementations for all our primitives. The only problem, of course, is that ESSENT doesn't support Verilog extmodules (for obvious reasons). One option, however, could be to implement them in Chisel, so they compile to FIRRTL.

[sbeamer]

@sampsyo Thank you for writing this up!

The application of parameters is typically done by Chisel generators (which are valid Scala programs), so by the time it is in FIRRTL, it has been made concrete. Years ago, I heard aspirations to expose parameters at the FIRRTL level to enable generators with different front-end languages to cooperate, but I don't believe that went forward.

Just because ESSENT uses low-FIRRTL, it doesn't mean the proposed backend couldn't use all of FIRRTL's higher-level features. ESSENT calls the current Scala FIRRTL library to "lower" FIRRTL designs as its first step. For example, things like when statements are not low-FIRRTL, but can be lowered by a couple of passes. Yes, @rachitnigam, FIRRTL has abstractions to describe memories, and there are additional passes to lower them appropriately.

For the actual expression of FIRRTL, textual format is great. It might also be worth looking at the protobuf version, which can ease serialization/deserialization. If possible, I would target FIRRTL as of the 3.5 lineage, as that should hopefully be compatible with both the classic Scala FIRRTL code as well as the upcoming firrtool.

Despite my emphasis on simulation performance, I have not spent enough time optimizing tool time or even profiling where the time goes. For ESSENT, both the code generation time and the compilation time are significant fixed overheads. The code generation is largely taken up by the FIRRTL lowering process and acyclic graph partitioning. The compilation time could probably be improved with multi-file compilation. I often don't have the JVM running long enough to notice performance improvements from the JIT between runs.

Once the ESSENT-generated C++ is compiled, it is a fast simulator, but the time to create that is substantial. A recent fork of ESSENT generates Java insteads, hoping to reduce compile time and then get long term performance benefits from the JIT:

A Java Backend for ESSENT
https://woset-workshop.github.io/WOSET2022.html

[sampsyo]

Awesome; thanks for the notes!! Indeed; one cool outcome of this project could be an apples-to-apples comparison of the various parts of a simulator execution (code generation, compilation, starting up the simulator, actually simulating). And it's a cool idea to try a Java backend; I hadn't seen that.