A Proof-of-Concept fud Successor

[sampsyo]

fud is an important part of the Calyx ecosystem. What it lacks in research novelty it makes up in sheer utility.

Despite its centrality, fud has some problems. Some of these are baked in and would be pretty hard to change at this point:

• It can be surprisingly verbose/tedious to write new operations.
• It has a sometimes-confusing conflation between states and transformations between states.
• It does not do incrementalism nor parallelism, which seems a little odd because these are the main things that other build systems seek to offer. This is not a big deal for one-off transformations but gets surprisingly annoying for more costly jobs, such as running the Xilinx toolchain.
• The configuration system causes heartburn (see, for example, the very important verilog.data config option that is sometimes shared by other stages and sometimes not).
• Not the biggest deal in the world, but: it has problems with special characters (including spaces) in filenames that would require pretty pervasive refactoring to address.
• It's not written in Rust. :)

I am seeking comments on a proof-of-concept prototype successor to fud I hacked together that addresses all of those problems. It's pretty far from a complete replacement; it is just mature enough to demonstrate that such a replacement might be feasible. I want to show off the design and what is working so far, while at the same time emphasizing that literally everything is up for debate.

Here's a demo of some of the stuff that's currently supported:

The first few seconds are the most interesting; only watch to the end if you like waiting for EDA toolchains!

Design Approach

fud is a compiler driver, in the same sense that clang and gcc are compiler drivers. The interesting thing about fud is that it's an extensible, generic compiler driver: it has a generic way to register different states of a program and the ways to transform between them, and the generic machinery wires all that stuff up according to what you have and what you want.

I've thought for a long time about taking another whack at this "generic compiler driver" notion while baking in some of the lessons we've learned over the last several years (see above). This always seemed like a pretty heavy lift, however, primarily because of the basic machinery for executing commands—and doing this in parallel, and doing it incrementally. Even though fud is a compiler driver and not a full-fledged build system, all this started to seem uncomfortably like reimplementing a build system.

The idea that came to me a few weeks ago was that we could reuse an existing build tool to do that hard part: running commands, buffering their output, deciding when to re-run them, etc. Then fud itself could focus on the planning part, i.e., deciding which commands to run. Namely, there exists a popular tool with exactly this intent (just running jobs, while delegating the plan of what to execute): Ninja.

So that's the approach. There are two crates:

• fake ("fud-like make"): A generic compiler driver library with Ninja as its execution engine. You register an arbitrary set of states and another set of operations that transform between these states. Then, when the user asks you to transform from state A to B, it comes up with a plan to do that, generates a ninja.build file, and invokes ninja.
• fud2: A fud alternative implemented using fake. It provides the Calyx-relevant states and ops. The PoC version only has a few states implemented, so the whole source code is only 232 lines in one file, so that might be a good place to start looking if you want to see what the implementation looks like.

Quick User Manual

You need a configuration file, at ~/.config/fud2.toml. Start with something like this:

data = "/scratch/adrian/fake/fud2/data"

[calyx]
base = "/scratch/adrian/calyx"

The data path goes to fud2/data within the fake repo. calyx.base goes to your Calyx checkout. That's enough to get started.

You'll also need to install Ninja, which you can do from most package managers.

Here's what works in the current prototype:

• fud2 <file> -o <file>: Do the thing.
• Replace -o <file> with --to <state> to print to stdout.
• Replace the first <file> with --from <state> to read from stdin.
• Use --set <key>=<value> to override configuration options (or -s for short). For example, -s sim.data=<path> to specify the data file for simulation.
• Add --keep if you want to keep the intermediate files, which enables incremental compilation. You can find the intermediate files in a directory .fud2 inside the working directory. Without --keep, this gets automatically deleted after execution finishes.

There are a few alternative modes you can try too:

• --mode gen: Just generate the .fud2/build.ninja file but don't actually build anything. You can then type ninja -C .fud2 to run the build.
• --mode emit: Just print out the Ninja file. If you like, you can always do fud2 [...] --mode emit > build.ninja && ninja to make fud2 work more like a "normal" build system.
• --mode plan: Show a simple listing of the plan fud2 found for you (the sequence of operators it wants to run).
• --mode dot: Produce a GraphViz visualization of the selected plan, as a path through all available states. See below for an example.

What Is Lost

Here are some good things about OG fud that are not really possible in fud2 without a very different design:

• Loadable external modules with custom ops/states. This would be technically possible with, like, dlopen or whatever, but I'm just not sure it's worth it. (This cost is just because of switching from Python to Rust.)
• Not requiring Ninja. You have to install Ninja to use fud2! Although maybe it's possible to work around this one by bundling Turtle, a Rust reimplementation of Ninja. :)
• [this is the big one:] fud stages that do a lot of heavy lifting "internally" instead of delegating to external executables. In this design, fud2 is only responsible for deciding which commands to run; it does not contain code to do a bunch of the actual work during a build. All that "real work" has to be done by an actual command that is invokable through the command line.
  • The biggest example of this in the current PoC is the data converter. OG fud contains a surprisingly complicated bit of machinery to convert between its custom JSON format and flat hex data files suitable for readmemh or whatever. fud2 does not build in stuff like this. In fact, the current PoC ships with a little Python script that just invokes OG fud's machinery to do this!
  • This is obviously annoying in the short term; it means that fud2 is not a single, self-contained executable and it relies on a bunch of external tools to do its job.
  • I argue that, in the longer term, this is actually a good thing. It is a real problem that fud is so monolithic, and that the individual pieces are impossible to invoke separately from the high-level command orchestration. Problems include: (1) Hard to debug when something goes wrong, because it goes wrong inside fud and not in a command you can run independently. (2) Hard to test, for the same reasons. (3) Hard to reuse components in non-Calyx contexts. The data converter, for example, deserves a life outside of Calyx, IMO! (4) Essentially impossible to make incremental, because the intermediate products are not guaranteed to be files that can be cached. With all that in mind, I think the benefits of this kind of "atomization" into smaller utilities, invokable on the command line, will be a good thing for the long-term health of the project.

Status of the Proof of Concept

Here are some things missing from the PoC that probably wouldn't be that hard to implement:

• Configuration editing (fud config).
• Configuration health checks (fud check).
• Remote execution. If we bring this back, we should do it in a generic way, not just for the Xilinx ops.
• Proper streaming between commands. All inputs/outputs of each command are currently "spooled" to files on disk. (However, the input and output files are not copied needlessly; they are read from and written to in place.) This is probably fine TBH; I am not that concerned with the performance implications. But it should be possible to make work with some effort, if we really want it (and are willing to sacrifice incrementalism for this).
• Lots of ops from fud! Prominently, we would need the Cider ops.
• VCD generation. We'd want to implement this for all 3 simulation modes I currently have implemented as producing data files only (Icarus, Verilator, XRT).

Discussion Questions

I will claim a meeting slot to talk more about this. But even in the mean time, I am curious what people think about this approach!

• Do the benefits outweigh the costs, as enumerated above?
• Are there other costs or benefits I didn't mention?
• If we like this approach, do you have recommendations for next steps? Should I merge this into the Calyx repo at some point, even before it reaches feature parity with OG fud?

Thanks for taking a look!! Please post any and all questions; I am sure I left lots of details out.

[EclecticGriffin]

I am absolutely with you on fud being "too powerful" and monolithic particularly with respect to data generation. This became very frustrating for the interpreter and required me to add a separate stage/target just to output the parsed data so I could test with it:
https://github.com/calyxir/calyx/blob/main/fud/fud/stages/interpreter.py#L17

The data serialization and deserialization from the interpreter is also a real nasty block of code that I wrote once and have generally tried to avoid messing with at all costs, in part because it's not a standalone thing: https://github.com/calyxir/calyx/blob/main/fud/fud/stages/interpreter.py#L270

So I can totally see having things like datagen as their own mini-tool or script set within the repo but we then have to contend with making sure those pieces are available or bundling a bunch of binaries. That, as I think you've pointed out is a cost of moving away from the monolith.

I am however interested as to whether using Ninja can make things like caching results easy/free? The data conversion for large programs like LeNet took a non-trivial amount of time and it could be really useful to not have to rerun that since the data-files don't change that often, but building a caching system into fud always seemed like a step too far.

fud, in my experience, with it never really had a clear design document and so grew out of whatever was needed at the time. It may be useful to articulate precisely what we would want fud2 to be responsible for, as you have already partially done, what it's goals should be, and how it expects to interact with tools. A more atomized execution would suggest that, where applicable, we should be building a library of mini-drivers/utilities for handing things like data format conversions.

I also wonder how hard/possible it is to emulate the behavior of taking control of stdin for things like the debugger (which caused a non-trivial amount of problems).

[EclecticGriffin]

Fixing the stages thing might also be helpful since it always felt weird that there is a separate interpreter state that is just some arbitrary Calyx file that may or may not have been generated from the input file or otherwise just be the input file which of course necessitated interpreter-out as the output stage

[sampsyo]

Awesome; thanks for the comments here!!

I am however interested as to whether using Ninja can make things like caching results easy/free?

Yes! I didn't exactly make it clear, but this is part of the "incrementalism" goal that I mentioned a couple of times above. In particular, the --keep flag already essentially does this for the simulation ops that I've implemented. Under the hood, the .fud2 directly will contain the converted files (flat hex data files), and when you rerun fud2, it will just rely on Ninja to see that it can reuse that stuff as long as the input JSON file has not changed.

This also means that data conversion is easily parallelized with compilation. If you do --mode gen and then ninja -C .fud2 -j6 or whatever, this parallelism will happen automatically.

It may be useful to articulate precisely what we would want fud2 to be responsible for, as you have already partially done, what it's goals should be, and how it expects to interact with tools.

This is a good idea. I will try to write up something more complete like this at some point, perhaps for the Calyx docs?

I also wonder how hard/possible it is to emulate the behavior of taking control of stdin for things like the debugger (which caused a non-trivial amount of problems).

I think this should be OK because of a specific Ninja feature, the console pool:
https://ninja-build.org/manual.html#_the_literal_console_literal_pool

That feature hooks a command up directly to stdin/stdout for the parent process. And the Rust std::Process we use to launch Ninja inherits stdin/stdout from fud2 by default anyway. So hopefully this "just works"?

[rachitnigam]

@sampsyo über cool! I'm a particularly big fan of the ninja stuff. I do think that being able to register new stages easily has been a big win for my usage of fud; for example, Filament maintains a completely separately versioned set of stages for it's execution management with fud. If we eliminate that, we better have a clear story for extensibility. fud's superpower is that it already knows how to do most of what you want; you just need to specify the paths that are missing.

it never really had a clear design document and so grew out of whatever was needed at the time

@EclecticGriffin fud grew out of the need to make it easy for people to "run" Calyx programs. This means that you should be able to provide a Calyx file, a data file, and get an output. Other things have been slowly added on top of it, but fundamentally, it is a tool for running Calyx programs.

As we develop things like the AXI interface and the FIRRTL backend, what it means to run a Calyx program is changing. It is not enough to have a standard interface for all programs and we'll need to develop a clearer sense of what we're building.

The other project management-y thing here is what is the development, migration, and maintenance story for this new tool? fud is currently entirely maintained by me and I don't yet see which research project would drive the development of this tool. I do think that the ninja stuff could provide a good story for other build systems that we want to design using Calyx but again, nothing concrete.

[sampsyo]

I do think that being able to register new stages easily has been a big win for my usage of fud; for example, Filament maintains a completely separately versioned set of stages for it's execution management with fud.

Good point; Filament is the best example of an out-of-tree use of OG fud. In a worse-is-better sense, how bad would it be to just add the Filament ops to fud2 directly? I imagine they don't evolve all that quickly…

The dlopen-based extensibility approach is possible with some effort if we want it! Another, more exotic approach would be to provide some kind of scripting interface for extensibility, such as Starlark. I'll think about that latter option some more.

The other project management-y thing here is what is the development, migration, and maintenance story for this new tool?

I don't have a great story for migration… I was hoping that some of the discussion could help flesh that out. Overall, however, part of the goal with fud2 is that it should be much easier to maintain, simply because it does less.

As an example, part of my inspiration to start thinking about it again was because I recently found myself recommending to @ayakayorihiro that, at some point in the near future, she consider adding a fud stage for FIRRTL-to-Verilog compilation. As with many other times when I have recommended that someone add a fud stage, I had to add a lot of qualifiers about how fud is awesome but it is pretty complicated and new stages are not trivial to add. With fud2, I hope that difficulty is greatly reduced; like, the MrXL op consists of only 7 lines that are hopefully not too mysterious:
https://github.com/sampsyo/fake/blob/b15ec005215cca932fbcec21b39ca892a5228bf6/fud2/src/main.rs#L43-L50

Anyway, this doesn't answer the question "how will we maintain this?", because you're right, there is no research project here to justify a lot of investment. But I hope the overall maintenance burden will be lower in the long run, which is maybe in line with fud's role as a "supporting actor."

[rachitnigam]

One prompt to discuss the scope of this tool: we should differentiate between "project build tool" and "file build tool". Something like Edalize seems like a project build tool to me: each project requires specific configuration and edalizes manages the building of the whole set of dependencies. A "file build tool" (which is the misnomer I'm using for fud), is something that takes in exactly one file, assumes a bunch of properties about it (like the top module being named main) and generates some set of outputs.

Now, the cool thing with fud2 is that we can build a "file build tool" first and transform it into a project build tool later on. If we're clever, this will literally turn out to be the problem of generating the right ninja file to execute all the steps in the dependency chain for compiling all the files in a project which could be super powerful and enable things like #419.

[sampsyo]

Yes, thanks, this is a very good way of putting it… I was having trouble drawing a line between fud and that other category of build tools (Edalize, SiliconCompiler, Hammer, mflowgen), and I think this "file vs. project" distinction is a good way to describe it.

[sampsyo]

I'd like to propose some immediate next steps for adoption/migration:

1. I put all this stuff (the fud2 and fake crates) into the Calyx repository immediately.
2. I work on adding a bunch of documentation, including both design documents and "users's manual" type stuff.
3. I make some issues there about stuff we've talked about (and beyond) that would be required to make fud2 a viable replacement for fud.

At this point, fud2 would exist alongside OG fud, and we'd have a clear picture of the work required to fully migrate, but OG fud would not yet be deprecated. Hopefully, we can get a little more experience with using and extending fud2 that will clarify what to prioritize. At some later date, we will make the longer-term plan for actually going about the replacement.

What do folks think about this short-term plan? Even if you just want to say "sounds fine with me", I would appreciate the validation of knowing y'all don't see any obviously bad ideas with this modest next step. 😃 With apologies for @'ing you, some people I can imagine might have opinions about this stuff would include: @ayakayorihiro @EclecticGriffin @rachitnigam @anshumanmohan (non-exclusively; as ever, I'd love to hear from you even if you're not mentioned here ☺️).

(P.S., as a bonus: fud2 now has Cider stages, so you can do --to dat --through interp and even --to debug. And @ayakayorihiro recently added FIRRTL compilation in sampsyo/fake#1!)

[ayakayorihiro]

This sounds great to me!!

[anshumanmohan]

Same here! Exciting stuff!

[EclecticGriffin]

Also sounds good to me as that will force me to actually set it up

[rachitnigam]

One little topic that I would've been excited to discuss if I wasn't going to fall asleep in the next 10 minutes: using fud2 as a library to implement little runners for frontends and test harnesses. Two examples:

Filament fud2 Runner

Bigger Filament designs, like [frisc][], often require both Filament code and Calyx code to be compiled. It would be nice to be able to specify a TOML file like this:

fil_sources = ["alu.fil", "mem.fil"]
calyx_sources = ["harness.futil"]
data = ["instructions.json"]

And have a fud2 based tool automatically compile things, link them, and invoke the test harness. @anshumanmohan a runner for more complex PIFO-runner might also become feasible through this?

Generators and Modules

fud2, being a beautiful, perfect, Rust codebase, can now integrate into calyx itself and support our long-standing dreams of generative modules in Calyx (#419). The big idea would be writing some tool to parse in a Calyx project, extract all needed generator commands, run them through a fud2-based tool, and then invoke the Calyx compilation toolchain!

[sampsyo]

Super great points both!!

About a potential multi-file project thing: I suspect there's a clean way to extend fud2 to essentially just plan out multiple builds and concatenate the resulting Ninja code into one big file. That might get 80% of the way to doing what you envision here. This also very much seems relevant to @gabizon103 and his Filament build-system ambitions.

About invoking generators: indeed, there is something interesting to do here. In fact, the Calyx compiler side of things recently gained something like the required functionality to enable something like this: @ayakayorihiro's "primitive uses" backend (#1860) now lists all the instantiations of primitives, like std_reg(17) and std_reg(21) or whatever. (The purpose was that she can then run a FIRRTL generator to get the monomorphized primitive implementations for that universe.) Anyway, something like this is now possible-ish by gluing together these pieces…

[rachitnigam]

I suspect there's a clean way to extend fud2

Yup, that's what I was thinking too!

relevant to @gabizon103 and his Filament build-system ambitions.

I think this is more challenging; because the process of monomorphizing generates new dependencies during the compiler's run, it is impossible to statically detect the tool invocations that would be needed to build a Filament project. This is a long-term problem but it might be possible to build a build system within the Filament compiler to fix this (🤣)

The purpose was that she can then run a FIRRTL generator to get the monomorphized primitive implementations for that universe

I think there is a clean to way to this for Calyx. We extend calyx-frontend to support the new module syntax and do not provide a mechanism to turn those AST nodes into IR. This establishes the contract that Calyx programs must be fully monomorphized before being converted to the IR.

I think, in the long-term, we might want to expose various extension hooks in the frontend to make the language easier to use, along with little tools that get rid of those features before the IR. Another example is computed parameters which has been a long-time ask from various users.

[sampsyo]

the process of monomorphizing generates new dependencies during the compiler's run

Very tricky indeed! I don't know if this is helpful at all, but Ninja does have some special features built in to help deal with "dynamically-discovered dependencies"… roughly, you have the build write out a list of new dependencies to a file, and Ninja can ingest that:
https://ninja-build.org/manual.html#ref_dyndep

It doesn't exactly look easy, but it may be possible?

[rachitnigam]

On the generator front, I want to bubble-up FuseSoC's approach. You can specify generators using shell scripts:
https://github.com/olofk/corescore/blob/master/corescore.core#L874-L876

And then parameterize the generation on a per-target basis: https://github.com/olofk/corescore/blob/master/corescore.core#L352