Modules for Calyx

[sampsyo]

Especially given the recent discussion about numerical libraries culminating in #416, I've been thinking a bit about what libraries should look like in Calyx. Aside from the status quo, i.e., the ability to import other Calyx files, this note explores the general question of what a more complete ecosystem of modules for Calyx would look like.

The vision is this: if we wanted to let developers do something like calyx-pkg install fixedpt to get access to a complete complement of fixed-point math operators, how would that need to work? How do you make a Cargo or npm for hardware libraries (and as a consequence expunge the term "IP block" from the universe forever)? The goal here is not to actually design a solution but to frame the problem and outline the shape that a solution must have.

In particular, let's imagine that we have already solved the boring parts: the package registry, where to host the actual files, versioning, dependency resolution, namespacing, integrity checks—those we could just steal from the real Cargo. But what makes packaging and modularity different from the same concept in software when we're talking about hardware? I think the biggest difference is the need for module-level metaprogramming.

Some Observations and a Contradiction

Here are a few direct observations about the problem:

• Calyx is an intermediate language, not an end-user source programming language—and packaging is typically the domain of source languages, not ILs. It's not as if people go around distributing libraries as LLVM bitcode files, for example. One reason is that libraries are pretty useless for development without their source-level interface declarations (e.g., header files in C). But the primary audience for a Calyx library would be generator writers, not ordinary source-code programmers—which means that Calyx declarations probably are the right level of abstraction.
• It's already conventional wisdom that the key to reusable hardware design is metaprogramming. In the hardware world, the terms are "hardware generators" and "elaboration," but both are really just different words for metaprogramming. This notion seems very hard to argue with: a single hardware description of a matrix multiply unit, for example, is not very reusable; one that can be parameterized on input size, block size, numerical precision, buffering style, and so on is truly a library. Every modern HDL out there has some fancy metaprogramming story—for instance, it's a major selling point in Chisel, and CoreIR has built-in support for generators. And needless to say, Calyx itself is all about higher-level generators—it's right there in the ASPLOS paper title! (Metaprogrammed libraries seem marginally useful in software too—C++ header-only template libraries are essentially metaprogrammed libraries, for instance, and Cargo packages have limited metaprogramming in the form of feature flags. But while they're nice to have in reusable software, they are absolutely critical in reusable hardware.)
• It would be painful and probably a waste of time to invent an actual metaprogramming system for Calyx itself. All the options seem bad: we could provide simple but inflexible compile-time parameters like Verilog; extend them to ad hoc compile-time manipulations like C++; allow arbitrary Turing-complete meta-level execution like a Scala embedded DSL; etc. There are so many possible ways to do metaprogramming, and they all have pretty severe trade-offs: simpler ones are more analyzable but less flexible, and less restrictive ones can quickly turn into nightmares of complexity (looking at you, C++ templates). Choosing any one point in this well-known trade-off space would be making a deal with the devil. And it seems especially needless given that Calyx code is already intended to be generated by some frontend compiler! It seems like a total non-starter to bake in some form of bespoke Calyx-level metaprogramming and then have all our generators generate generators.

These observations lead to a contradiction: we want libraries; libraries inherently involve metaprogramming; but it would be ridiculous to invent our own metaprogramming system in Calyx. I think the key to resolving this contradiction is to give up: to avoid solving the metaprogramming problem ourselves and instead foist the responsibility onto any old Calyx generator.

Meta-Parameters to Calyx Components

Let's first take stock of the kind of metaprogramming that is sneakily already possible in Calyx: parameters to Verilog-implemented Calyx externs. For example, our core.futil currently contains a declaration like this:

extern "core.sv" {
  primitive std_add<"share"=1>[width](left: width, right: width) -> (out: width);
}

where width is a parameter that gets threaded into the SystemVerilog implementation. Calyx programs that use this library can now declare cells like std_add(32), std_add(42) if they want, whatever! The implementation starts like this:

module std_add #(
    parameter width = 32
) (
   input wire               logic [width-1:0] left,

That parameter keyword is the entry point to Verilog's own metaprogramming facility (known as "elaboration," but it's the same thing). So in a way, Calyx parameters are a way to abdicate the need for metaprogramming to the Verilog compiler. It might seem strange at first that we have this whole parameter facility just for Verilog code—that proper Calyx code doesn't enjoy the same functionality. As argued above, though, Calyx is supposed to represent generated code, not generating code. Adding this style of metaprogramming to Calyx code would be a mess and a slippery slope with no clear endpoint.

So why do we have these parameters at all? I think there are a few reasons why we need them:

1. Naming convenience. It would be ridiculous, albeit semantically equivalent, to exhaustively declare std_add_1, std_add_2, and so on. It's really, really nice from a practical perspective for frontends to have a way to use any width of adder they want without worrying about getting the naming convention right—or whether we pre-generated enough adder names ahead of time.
2. Allowing semantic assumptions. Although we don't do much of this currently, one can imagine a constant-folding pass that replaced additions of constants with constants. This pass would need to know that std_add performs integer addition—presumably by recognizing the name. It would be horrible if this pass needed to parse the name of std_add_42 to draw the same conclusion. The same need applies to a Calyx interpreter that needs to know how to add numbers without simulating the SystemVerilog.
3. Compact Verilog output. Calyx's primary (and currently only!) backend is SystemVerilog. As another ruthlessly practical matter, it's sort of nice that the generated SV preserves parameterized module declarations instead of requiring duplicated code for every parameterization.

So even if it seems odd at first glance, I think our current design has already struck a nice "division of labor" for the library metaprogramming problem. Calyx is involved in parameters at the type level, but it abdicates responsibility for metaprogramming at the term level. Doing the ordinary polymorphism thing for the port widths in std_add is very useful for making library declarations intelligible, but Calyx is wise to avoid getting its hands dirty with actually interpolating the parameters in the implementation. By delegating the latter responsibility to the already-existing metaprogramming facility in the SystemVerilog synthesizer, Calyx gets to sidestep the unpleasantness of deciding what the world's greatest metaprogramming facility would look like.

Strawperson Proposal for Metaprogrammed Modules

What if we took this same division of responsibilities and ran with it? Calyx would stay in charge of how parameters affect its (quite simple) type system and delegate the actual metaprogramming problem to those who do it best already: Calyx frontends.

The strawperson proposal is this: Calyx libraries invoke an external tool to generate the Calyx implementations for a given set of parameters. The Calyx compiler runs an actual command line in a subprocess to instantiate the library. Making up some syntax, we might define an exponentiation library like this:

extern mymath(width) "!python gen_exp.py {width}" {
  primitive exp(in: width) -> (out: width);
}

This extern block works like a normal SystemVerilog-backed extern, but the ! indicates that we have to run a program instead of just reading a file to get the implementation. (And the generated code may be Calyx code instead of SystemVerilog source.) I have invented some silly interpolation syntax for indicating how to pass parameters like width to the generator via command-line arguments.

This imaginary syntax also introduces names (mymath) and parameters (width) for these extern blocks. The idea is stolen directly from ML module functors. Relative to the current syntax for parameterized extern primitives, this functor style would allow several related declarations to share a single parameter. It would also simplify the logistics a bit by letting a single generator execution to produce a big Calyx file with multiple parameterized component implementations (instead of requiring a new subprocess for every instantiated component). You'd instantiate our exponentiation component, for example, using syntax like mymath(32)::exp.

Now, this strawperson has some pretty obvious problems! We have essentially made Unix itself the de facto abstraction for metaprogramming. Requiring the compiler to invoke arbitrary external commands during compilation would have severe pitfalls:

• What if a generator runs rm -rf /?
• Won't this be super inconvenient on Windows?
• Can't these Calyx libraries have arbitrary non-Calyx dependencies—like, a library might require Python to generate, which is sad if you want to use it in a context that doesn't itself need any Python?

Yes, all of these drawbacks make this proposal seem kind of silly—they're not pitfalls that your favorite language's module system must typically contend with. I contend that they may, however, be the necessary price to be paid for decoupling the metaprogramming mechanism from the language. And there may be creative ways to mitigate these problems:

• Metaprogramming could, at the very least, be relegated to a separate phase from compilation. The package management tool could be responsible for analyzing your code to find the required module instantiations, running the generator, and saving the result.
• This separate phase could certainly cache instantiations so it's easy to reuse the mymath(32) module without rerunning the generator.
• The generation for popular parameter values could even be done server-side, hypothetically. Libraries could come with cryptographic hashes of the generated code for these parameter sets to authenticate the pre-generated versions.

Related Work

• There is real-world precedent for hijacking traditional software package managers to encapsulate hardware libraries. For example, svreal is available via pip.
• FuseSoC is a very complete system for composing RTL "IP blocks" that works like a package manager.
• Veritas, VIVP, and vpm are straightforward npm-like package managers for Verilog modules. There is plenty to learn from in their basic packaging functionality. They do not directly address metaprogramming concerns.
• SiFive's DUH also has to do with packaging hardware modules for reuse. It's more focused on full-scale ASIC workflows, such as specifying hardware-level interfaces and providing clock and power network plumbing, and less on accelerator-like computational libraries.

[cgyurgyik]

extern mymath(width) "!python gen_exp.py {width}" {
  primitive exp(in: width) -> (out: width);
}

are you imagining this will simply be replaced with a component of the given type, e.g. if width = 32:

component exp(in: 32) -> (out: 32) { ... }

[sampsyo]

Yeah! That's a good way of putting it. But to preserve the fact this is a specific instantiation of the exp "prototype," the syntax might even look like this:

component mymath(32)::exp(in: 32) -> (out: 32) { ... }

…assuming we don't hate my C++-style namespacing of mymath(32)::exp.

[cgyurgyik]

Yeah! That's a good way of putting it. But to preserve the fact this is a specific instantiation of the exp "prototype," the syntax might even look like this:

component mymath(32)::exp(in: 32) -> (out: 32) { ... }

…assuming we don't hate my C++-style namespacing of mymath(32)::exp.

Got it, how were you imagining what instantiations would be processed? For example, if I'm understanding correctly, this would require a pass over the program, finding every instance of mymath(width)::exp for a unique width, and creating a component for each.

[sampsyo]

Oo wow, threaded replies! What do you know.

Yeah, pretty much exactly that. Or maybe you have to explicitly say, like, use mymath(32) in order to get access to the components defined therein—and that triggers the "package manager" thing to instantiate the library.

[rachitnigam]

@sampsyo Any thoughts on how namespace and name resolution should work? We've run into this problem in #431 where generated and library names collide. Obviously, namespaces are a nice solution but I don't want to build a full-blown name resolution system. Is there an approach that is both incremental and sane?

[cgyurgyik]

Is there a simple answer to why namespaces are hard to implement?

namespace n1 {
  component foo() -> () { ... }
}

namespace n2 {
  component foo() -> () { ... }
}

// To use: n1::foo or n2::foo. (Useful) error if trying to use only `foo`.

It obviously gets ugly when you::have::something::like::cpp::style::namespaces::foo(). I imagine there are more complicated cases than this, but none that are immediately obvious to me.

[rachitnigam]

Here is an example:

namespace n1 {
  namespace foo { component bar... }
}
namespace n2 {
  namespace foo { component bar... }
}

import n1::foo;
import n2::foo;

foo::bar(...) // Which bar to resolve to?

In the general, I think problems start arising if we don't carefully think about name resolution and what kinds of uses should have an error. Neither definition in this program are bad—the fully qualified names are distinct. However, the import statements make this complicated. I'm not saying there is not solution to this; however, I don't know if I want to spend time implementing a full-fledged name resolution system.

[cgyurgyik]

Got it. I guess in my mind I was thinking keep it stupid simple. If you want to use n1::foo::bar, you need to fully qualify it,
so foo::bar(...) is a resolution error.

To add onto this, in C++ land, namespace pollution is bad, e.g. Google C++ style guide.

std::vector<int> v = { 1, 2, 3};

is preferred over

using namespace std;
vector<int> v = {1, 2, 3};

[sampsyo]

As meta-commentary, the constraints for namespacing in an IR seem at least somewhat different from namespacing in a user-facing programming language. For example, verbosity need not really be a top-level concern when code will typically be generated, for instance.

I agree with @cgyurgyik that the sensible first-order approach would be that there is no way to import stuff "from" a module. That is, if you have ns::foo, there is no use or import conjuration possible to make this accessible via just the name foo—you always need to refer to it as ns::foo. Coupling that with top-level namespaces only (no nesting) could make for an extremely simple system. And to re-emphasize, lots of flexibility and user features seem unnecessary because it's an IR.

[rachitnigam]

Looks like FuseSoC provide a way to call generators: https://fusesoc.readthedocs.io/en/stable/user/build_system/generators.html

[sampsyo]

Neat! Seems like they also settled on the "Unix is the universal language" notion:

Generators can be written in any language. The only requirement is that they are executable on the command line and accepts a yaml file for configuration as its first argument.

It also looks like they have a partial notion of "on-demand" generation of differently-parameterized modules, based on a cryptographic hash of the parameters:

Instead of fusesoc rerunning a generator each time and producing the same result it is possible to configure fusesoc to cache generator output and try to detect if a new run would produce the same output. […] If set to input fusesoc will calculate a SHA256 hash of the generator input yaml file data and use this hash for detecting if something has changed and a rerun would be needed.

Seems like something to be learned here…

[sampsyo]

Because we are circling around this category of discussion as a result of #1596 and related stuff, I just wanted to revisit the most relevant pieces that I think are worth discussing.

In general, I still think the above strawperson proposal is not a bad place to start, despite the shortcomings I listed originally. As a synopsis, the extension would look like this—with slightly massaged syntax:

extern mod mymath(WIDTH) "!python gen_exp.py {WIDTH}" {
  component exp(in: WIDTH) -> (out: WIDTH);
}

component main() -> () {
  cells {
    some_exp = mymath(32)::exp;
  }
  // ...
}

In a sense, user-facing idea here is to allow parameterization of Calyx-implemented components in a way that doesn't look too different from the way we allow parameterization of Verilog-implemented primitives. That is, if exp here were a primitive, we would instantiate it as exp(32). In this proposal, we instead introduce namespaces and parameterize those. Parameterization and namespacing may seem orthogonal, but like chocolate and peanut butter, I believe they are two great tastes that taste great together: a namespace provides a natural "boundary" at which to do parameterization. It seems important to have such a "boundary" that is decoupled from individual components.

Concretely, the proposed language extension has only two things:

• extern mod. This lets you define the parameterized signatures for Calyx code that needs to be generated by an external program. It also describes how to invoke that program to generate the necessary Calyx code.
• A new syntax for referring to component definitions in the cells section: namespace(params...)::comp. This adds to the two extant styles, which are plain ol comp and comp(params...).

To implement this extension, we would write a new pass that runs the generators and resolves the component names, "monomorphizing" them. Here's what this pass would do:

1. Look through the entire program to search for namespace(params...)::comp references in all cells sections. Gather up all the unique namespace(params...) uses.
2. For each such unique namespace-use:
   • Compute a cryptographic hash of the namespace name and parameter list. For example, perhaps mymath(32) hashes to 123abc.
   • Look in an on-disk cache, like at ~/.cache/calyx/mymath_123abc.futil. If it exists, finish this step.
   • If it doesn't, execute the associated command, like python gen_exp.py 32, and put the result in the above file.
   • At this point, maybe (in debug mode?) do some double-checking that the generated Calyx file actually conforms to the expected signatures in the extern mod declaration.
3. Replace the extern mod statement with a sequence of imports. In our example, we only have one use of mymath, so this becomes the single statement import "~/.cache/calyx/mymath_123abc.futil".
4. Replace all the component references with mangled names. So, for example, some_exp = mymath(32)::exp becomes some_exp = mymath_123abc_exp.

The point of this process is that namespaces are the point where metaprogramming happens, meaning that this is the point where we invoke generator scripts and do any caching we want to do. A cryptographic hash of the parameters suffices to unambiguously identify the generated code—unless, of course, the code for the generator changes (so we probably want a way to invalidate this cache).

---

I realize that this proposal has the uncomfortable property of turning the Calyx compiler into something more like a build system. That is, the Calyx compiler doesn't currently need to do any complicated orchestration of commands, files on the filesystem, etc.; that is all fud's job. The proposed pass above would need to do a bunch of command invocation, all of which could fail, and manage an on-disk cache and stuff—pretty complicated real-world stuff that is not the traditional domain of a compiler, TBH!

I acknowledge that this is not great. But in a way, I don't see a complete way around the fact that parameterization needs to be a first-class language feature to be useful. There is a chance we want the above rewriting to be an external tool rather than a pass built into the compiler, but that is a minor difference in the end.

[rachitnigam]

In another relevant conversation with Spade people today, the topic of generating "collaterals" such as TCL scripts came up. I think sadly something like that is inevitable in a toolchain like Filament and Calyx so providing sane first class support for it doesn't sound too terrible to me.

[rachitnigam]

There is a chance we want the above rewriting to be an external tool rather than a pass built into the compiler, but that is a minor difference in the end.

I'm not sure about that. An external tool doing this means that the compiler IR doesn't need to reason about parameterization explicitly. This could work pretty well (and something I was thinking we could do for a parameterized Calyx IL) since it reduces the complexity and redesign of the core IR.

[sampsyo]

All that is true. One trade-off to acknowledge here, however, is that making it a "pre-processing" pass means that the compiler never sees parameterized component instantiations like mymath(32)::exp; it only ever sees mangled names like mymath_123abc_exp. So optimizations could not reason about parameters if they wanted to—e.g., bit-width optimization would be impossible.

[rachitnigam]

Absolutely! I was considering that a feature instead of a bug. In general, I'm not yet convinced that you want to be able to optimize Calyx program with respect to parameters. However, a general parameterized IR itself is probably not a bad idea and something worth exploring as a standalone research project, potentially built on top of the Calyx infrastructure.

[sampsyo]

Yeah. There is an analogy here to stuff like C++ and Rust, where LLVM only sees the mangled names of flat, "normal" functions. If you want to do anything on the non-monomorphized code, you have to do that before LLVM.

[sampsyo]

One outcome from today's synchronous discussion was that we're all pretty much on board with pursuing something like the strawperson proposal above, and what we need next is a techincal design we can implement.

dependencies and stuff

We also discussed the biggest downside to this proposal, which is the messiness of having the "interface" to generator programs be Unix command invocations. This presents lots of annoying problems having to do with dependencies: how do we make sure these generator programs have everything they need to actually run? If the generator program is just a Python script, for example, it might have Python dependencies or need a specific version of the Python interpreter… supplying all of that is a huge pain that we do not want to solve.

One can imagine "fancy" solutions to this that include:

1. all generators are OCI/Docker containers
2. all generators are WebAssembly/WASI programs

But I think what we should do for now is just punt: generators are Unix commands, and satisfying those dependencies is not our problem. If you need Python dependencies, then set up a virtualenv or whatever ahead of time. If you need to build a Rust generator tool, run cargo build ahead of time; that's not part of what we promise to run for you. Any further fanciness can come later.

tooling

The biggest question to be resolved, in my view, is what the tooling looks like. That is, how does the thing work that is responsible for executing generator commands, caching their output, mangling names, and rewriting code to use those mangled names? We have tossed around 3 main options:

1. A Calyx compiler pass.
2. Part of the fud infrastructure, i.e., generators need to be given as fud stages.
3. A separate standalone tool, orchestrated by fud as part of the Calyx build process.

I'll resist recapping all the reasons, but I (somewhat strongly) prefer option 3. I think an interesting phase of work would be speccing out how that standalone tool would work.

non-parameterized namespaces

Here's a question that came up: do we want (at any point) to support the non-parameterized version of modules/namespaces? Like, should a Calyx program—with no parameterization/code generation in sight—be able to write something like this?

mod mystuff {
  component comp() -> () { ... }
}

component main() {
  cells {
    c = mystuff::comp();
  }
  ...
}

Here, the mystuff module is just a namespace, so this is equivalent to a mangled version:

component mystuff_comp() -> () { ... }

component main() {
  cells {
    c = mystuff_comp();
  }
  ...
}

So this by itself is, like, marginally convenient but not all that important. It could be a semi-pleasant way to avoid naming conflicts. But it's not super compelling for an IR, where convenience shouldn't matter much. (Whether we implement it as a compiler pass, part of the AST loading, or a separate transformation seems orthogonal.)

The reason to do it would be that it would simplify the library-generation process into two steps. That is, we would first generate a module, transforming this:

extern mod mymath(WIDTH) "!python gen_exp.py {WIDTH}" {
  component exp(in: WIDTH) -> (out: WIDTH);
}

Into this:

mod mymath_123abc {
  component exp(in: 32) -> (out: 32) {
    // actual implementation here
  }
}

That first step does all the generation, but namespaces are still preserved. Then the second step would perform the name-mangling to flatten namespaces. Having these two transformations be somewhat decoupled into smaller steps seems nice.

So that would be a reason to add non-parameterized namespaces to Calyx: merely to support parameterized (generator-driven) namespaces in a simpler way.

If we did chose this route, we would build non-parameterized namespaces first, and then implement the whole generator-invoking tool on top of that.