Build System Brainstorming

[gabizon103]

Hello! This is where I'm going to keep a running journal of all things related to a potential build system/integration story for Filament.

[rachitnigam]

Awesome!!

[gabizon103]

Some setup

The first place that I think would benefit from some more careful coordination between XLS and Filament is data types. XLS allows you to declare something like:

struct Point {
  x: u32,
  y: u32
}

which you can then define functions on, as follows:

fn add(p: Point) -> Point {
   Point (p.x + 1, p.y + 1)
}

I haven't looked into it yet, but these structs probably get flattened into a bitvector or something, since that is how most other things seem to be stored. If we want to give add a Filament signature and compose it using gen, we would want it to have a signature like:

comp XLSadd<'G:1>(
  clk: 1,
  p: Point
) -> (
  out: Point
)

Because of the current inability to express a type like Point in Filament, the signature would have to look something like this:

comp XLSadd<'G:1>(
  clk: 1,
  p: 64
) -> (
  out: 64
)

where p instead is a flattened bitvector containing the Point fields.

Also, we might want to compose these XLS constructs with other non-XLS constructs, like a module (implemented in Filament, Verilog, whatever) with the following Filament signature:

comp PointMul<'G:2>(
   clk: 1,
   p1: Point,
   p2: Point
) -> (
  pout: Point
) {...}

We can imagine this module might return some Point (p1.x * p2.x, p1.y * p2.y), and we implemented it outside of XLS so that we could express reuse, which is why the signature above isn't fully pipelined.

The problem

Obviously, the hard part here is how we should interface with the XLS-level type information in Filament. I think I see a way to do this right now.

Solution 1

This solution would hopefully be a formalization of the very ad-hoc XLS FFT stuff I was doing very close to the paper deadline. In short, there were some simple XLS data types (tuples, arrays) that we wanted to pass to Filament so that we could use our testing harness. My solution for this was to:

1. Compile the XLS to Verilog, which would pack the input/output arrays into really long bitvectors (thousands of bits long each)
2. Make a Filament harness that took these thousands-of-bits-long bitvector as an inputs/outputs, using gen
3. Make a Filament wrapper for our Filament harness (😵‍💫) that would then splice these bitvector back into data in its original format, or at least something that we can interpret easily

This sounds sort of bad, but I think there are a few ways we can clean it up. Mainly, we would need to come up with some sort of hardware analog to an ABI that would tell us (really the Filament compiler) how data being passed between XLS/Filament is laid out and how it can find the information it wants. Using this, it would be easier to have the compiler do the steps that I described above, which were previously done by hand.

Less clear, however, is how we can import type information from XLS. If we are looking to build a coherent build system, it feels important that we should be able to reference XLS types from Filament, so that our signature can use type Point instead of breaking up the struct into something like p1_x: 32, p1_y: 32, or a packed array like p1: 64.

This seems like the hard part. I'm wondering if it would be possible to be able to import the XLS file at the top of the Filament file, and then parse it (or at least just the types). Then, the Filament compiler can see that Point is a struct with an x field and a y field, and use our ABI analog thing to know how this data would be laid out in the Verilog it gets back from invoking the XLS compiler. Then, the compiler can internally transform the Point fields into flattened bitvectors, or have each field be its own input, or whatever. At a high level, I think this would be enough for type checking and code generation.

[rachitnigam]

Less clear, however, is how we can import type information from XLS

This is tricky but one possible solution to this is importing the XLS compiler frontend as library. Rust can interface with C code so it should be possible to do the following:

1. Parse an XLS program
2. Look at the signature of modules we care about
3. Generate the relevant Filament signature along with source position information (we'll need some way to encode this explicitly in the compiler)

This is a heavyweight solution so we should chat with the XLS folks before diving into it but it feels like the "right solution"? Thoughts?

The compiler would have to know that p1.x is actually stored in p1[63:32], and then replace accordingly. Since we're working in Filament, this means that the compiler might have to insert instantiations of things like Slices in order to get p1[63:32].

Thank you for writing up the transformation; It's very elucidating! I'm quite tempted to say that we should actually go ahead and implement #99 for this eventually. However, as a first pass, when we translate the Point data structure from XLS, we can just say it's a 64-bit number and make it the Filament user's responsibility to interpret it correctly. Of course, eventually, we want to make it more semantic by exposing the struct-level information.

On the Hardware ABI pitch, I think struct definitions might play a key role. For example, if you think about modeling the FloPoCo modules, we also have different kinds of floats (IEEE vs. FloPoCo) which would be more naturally captured using struct definitions.

[gabizon103]

it should be possible to do the following:

Yep, this is what I was thinking! And I also agree that we should talk to the XLS people first.

when we translate the Point data structure from XLS, we can just say it's a 64-bit number and make it the Filament user's responsibility to interpret it correctly

Can you clarify what you mean by this? Because right now you obviously can't reference a type like Point from Filament, but if you are interfacing with an XLS-generated module you will still be interacting with the Point data in its 64-bit number form. So right now it is sort of up to the Filament user to interpret it correctly (this is what I had to do with all of the FFT business). And if/when we implement this, the Filament compiler will also see it as a 64 bit number, but it will also know where to find relevant fields so it can do the bit slicing instead of making the user do it. Does my explanation make sense?

One thing I am wondering about is how this would look if/when we have structs in Filament. I'm not so sure it would make sense to translate an XLS struct into a Filament struct, given that by the time the Filament compiler gets the XLS-generated Verilog to link in, there is not any explicit struct information, just a flattened bitvector. I think it makes the most sense to treat all of this XLS integration as a frontend, like you said, and it seems like Filament/the compiler already has all the tools to do this.

I think I see your point about using structs for the ABI stuff, but could you be a little more specific about how you see this playing out?

[rachitnigam]

There are two worlds:

Filament does not support structs (current case): This means that there is no way for XLS to communicate the "rich" nature of the 64-bit data type to Filament programs. The user writing the Filament program essentially relies on XLS to lower programs in such as way so that they know that for p: Point, p[0:31] is the same as p.x and p[32:63] is the same as p.y. An alternative would be that instead of generating a packed 64-bit signal, we generate two signals p_x and p_y for the fields in the Point struct. However, essentially, we're relying on knowledge of how XLS's lowering occurs to extract the various fields

Filament supports structs: In this world, we'd like both Filament and XLS programs to use the Point data structure and extract fields in the same way that XLS lets you do. In order to make this happen, we'd need to tell the Filament compiler how XLS lays out data for structs and emit the slicing code needed for Filament-level accesses like p.x. This is similar to Rust's repr annotation on structs which lets it efficiently pass around structs defined in/for C.

Does this make more sense?

[sampsyo]

This overall sounds like a super promising direction! Thanks for the detailed proposal, @gabizon103.

There's one piece I'd like to discuss more deeply: how to get XLS types into Filament? My suggestion is: we should not attempt to parse XLS code at this stage. Instead, to whatever extent we want to use types like Point in Filament, we should require these to be "recreated" manually on the Filament side. A later-stage (and more language-specific) tool can do the XLS-to-Filament translation.

@rachitnigam brought up the Rust/C analogy, which I think is instructive here: to do an "FFI" kinda thing between Rust and C, you typically do not import the C header in Rust-land. Check out this page on C/Rust FFI. Instead, you manually recreate the types & signatures from the header inside your Rust code. Rust's #[repr(C)] comes with documented guarantees about how those Rust declarations are going to line up with the C code, so you can easily see that you have done this manual mapping correctly. But there is no automatic mechanism for actually parsing C code to create these definitions for you.

The reason is that parsing C code is complicated and cannot realistically be done without depending on a "real" C compiler. (The same is true for us: parsing XLS code would realistically require depending on the XLS compiler as a library.) So instead, in Rust, that job is factored off to a separate tool: bindgen. This is a good layering because it separates the basic functionality (with manual "alignment" of types, and no dependency on Clang) from higher-level but optional automation when you need it (and are willing to incur a complicated dependency on Clang).

I think this the right way to go for us too… that is, we build the basic functionality for an FFI that works with any external language, and later consider building language-specific machinery to parse and understand those languages on top of that basic machinery.

[gabizon103]

Thank you for the input! The comparison to C/Rust clears things up for me. I think I'll take some time now to play around with other languages we might want to interface with (Hardcaml, Spade, etc) and figure out what a more generalized FFI would look like.

[sampsyo]

This is somewhat tangential, but I noticed a really interesting and very recent development in the FIRRTL ecosystem: they have started documenting an ABI. This document defines a contract that describes how FIRRTL-level interfaces are guaranteed to manifest in compiled Verilog code.

Interestingly, the spec for data types takes the opposite approach from XLS:

Passive bundles, when lowered, are lowered to packed structs with their fields recursively following these lowering rules.

Vectors, when lowered, are lowered to packed vectors with their element type recursively following these rules.

That is, FIRRTL-level "bundles" (their name for structs) are lowered to Verilog-level structs that look nearly identical. XLS, in contrast, lowers all its "fancy" datatypes to plain ol' bits. In fact, it kinda sounds like (from this document) FIRRTL used to do it the XLS way, and they want to change it:

Two ABIs are defined. ABIv1 describes a system in which no aggregate types appear on circuit boundaries (publicly visible locations). This ABI captures and formalizes the historic behavior of FIRRTL to verilog lowering. Specifically, this ABI, by construction, produces no aggregate Verilog types. ABIv2 defines an ABI in which aggregate types are preserved. Both these ABIs may evolve as new FIRRTL constructs are added.

I like the XLS (and FIRRTL ABIv1) approach better, for these reasons:

• it gives the compiler exact control over data layout
• it frees high-level languages from the constraints of Verilog datatype features
• it targets a more minimal subset of Verilog (treating it more like an RTL IR and less like a source language)

The trade-off is that it is less convenient to integrate with Verilog projects that want to pass Verilog-level structs around. This is presumably a priority for FIRRTL but does not seem like an important priority for us. If we wanted this kind of interop, we would probably instead want a Verilog-specific bindgen-like tool to generate code that reconstructs Verilog aggregate types from flattened bits.

[gabizon103]

We've spent some time talking about these things in our weekly meetings, and I think we have nailed down enough of what we want here (at least for a first pass) that maybe some implementation can begin soon. A high-level plan is to build some richer data types into Filament, and then build language-specific bindgen-like tools.

Ideas

I think the first thing we want to do here is add richer data types to Filament. There are two reasons: (1) we have been wanting to do this for a while anyway (at least with structs), and (2) having these constructs in Filament makes it easier to interop with other languages that have these data types.

At least to start, here are a few ideas:

Enums

The DSLX language reference describes an enum as

a group of related, scoped, named constants that do not pollute the module namespace

I think this fits nicely into Filament, where we could have something like:

enum MyEnum[BITWIDTH] {
   member1 := 0,
   member2 := 1
   ...
}

Uses of enum members could look like MyEnum.member1 or MyEnum::member1. I like :: better, but it doesn't matter all that much. Each member gets lowered to a constant primitive.

I've been trying to think about how we handle the timing information here. One idea is to force the user to give each member an availability interval in the enum declaration, like this (the syntax is silly but it illustrates the point I guess):

enum MyEnum[BITWIDTH] {
   member1 ['G, 'G+1] := 0,
   member2 ['G, 'G+3] := 1
   ...
}

Another idea I thought would be to not require an availability interval in the enum declaration and instead have the compiler figure it out after monomorphization happens. At this point, we would know the first and last uses of each enum member, so we could instantiate a constant primitive that spans that range. This would make the first typechecking pass (before monomorphizing) kind of messy, since our only option would be to assume that these will typecheck at some later point.

Or, instantiate a new constant primitive for each use of the enum member, available specifically for the interval that it is being used for.
This would be able to typecheck, I think.

This approach of not including timing information in the declaration feels a bit un-Filament-y, but I think it does make enums feel more "global".

Tuples

Filament has bundles, which allow you to create a group of signals available at different times, but of the same bit width. It could be nice to also have tuples, which would be a group of signals of different widths, but available at the same time. I figure a user could make a type declaration like type triple<i, j>: ['G+i, 'G+j] = (32, 8, 16), where 32, 8, and 16 are the widths of the signals that are part of the tuple. This would allow a user to have types like this in a module signature:

comp module1<'G:1>(
   in0: triple<0, 1>,
   ...
) -> () {...}

which would mean that the module accepts a 32-bit, 8-bit, and 16-bit input in the interval ['G, 'G+1] (which we would know from looking at the type declaration).

Structs

I think structs should be implemented as a group of named signals that can be different widths, and available at different times. So, basically the same as laid out in #99.

Later: interfacing with XLS

This has been brought up before, but we would need to define some FFI between XLS and Filament, similar to the one that exists between Rust and C. We could have something like:

#[repr(XLS)]
struct MyStruct {
   x: ['G, 'G+1] 32,
  y: ['G+1, 'G+2] 32
}

where the #[repr(XLS)] instructs the compiler to follow XLS's rules for compiling the struct. This would prove helpful in using the gen too, where we might want to use an XLS module that takes a struct as an input/output, for example. Instead of making the user figure out how the XLS compiler maps data, and then having the gen module's Filament interface do something silly like take a huge flat signal as input, they could manually import this XLS type into Filament, use it in the module's interface, and the compiler would make sure that it compiles the struct and flattens it before linking in the XLS-generated code.

[gabizon103]

A bit more on this, after @sampsyo and I talked today:

Adrian thought that it might be a good idea to separate data-level constructs from timing-parameterized constructs; meaning that as a first pass, we would implement general sum and product types strictly at a "data" level, meaning that where I originally gave the example type triple<i, j>: ['G+i, 'G+j] = (32, 8, 16), we would instead want something like type triple = (32, 8, 16). Then, the timing stuff would happen at the places where you actually use this type, so we could have a module signature like this:

comp MyModule<'G:1> (
  x: ['G, 'G+1] triple
) -> ()

I like this better because it creates a clear distinction between the data-level constructs and the timing-level constructs in the language, and is also consistent with how every other signal is treated in Filament, at least from the perspective of module boundaries. It is a bit less clear to me how this would work out for something like a struct, which would have different fields available at different times, but I'm sure we could come up with something with some more thinking.

[rachitnigam]

Awesome, I think the data-level separation makes a lot of sense for things like tuples. This decision is also forwards-compatible if we end up implementing a simple type-inference system that just assigns the simplest availability interval to all fields (available at the same time).

Regarding enums: these seem more restricted than enums in Rust which can have data fields. There is a proposal for more interesting enums (#125) but that can be done later on. These enums can basically be treated as constants and compiled in the way you described @gabizon103.

Seems like we have enough of a path charted out so time to implement!