firrtl-spec

firrtl-spec copied to clipboard

This is a proposal for adding subword assignment support to FIRRTL. The full proposal can be viewed here: subword.pdf (EDIT: now out-of-date).

As a summary, this change would allow indexing expressions of type UInt or SInt to assign specific bits. This proposal only covers single-bit subword assignment at a static index. The "bit-index" expression must be used as a sink. For example, this would allow:

input x : UInt<4>
input y : UInt<1>
output z : UInt<4>

z <= x
z[0] <= y
z[1] <= bits(z, 0, 0)

The proposal gives an algorithm for transforming subword assignment to existing FIRRTL by rewriting using vectors (UInt<1>[n]). I have a prototype CIRCT implementation at https://github.com/zyedidia/circt/tree/subword-assignment that performs the transformation in the proposal.

Let me know what you think!

(I also included a small fix for the makefile since typing make on a fresh clone didn't work).

Finally, should this be a thing? There is certainly value in expressivity, but in an IR intended for transformation, sub-word updates of state are rather annoying to deal with

Subword assignments would be a neat feature for the frontend, mostly because Verilog developers have internalized a certain coding style that can heavily rely on these kinds of assignments. One good example is the TinyAES core which was rather awkward to translate to Chisel. I do agree that internally this should be converted into SSA. My one attempt to add subword assignments to firrtl, essentially tried to remove them very early on in the compilation flow by minimally splitting signals that are subword assigned.

Thanks for the feedback! Sorry for the wall of text, I've tried to respond to some of the concerns appropriately.

How does this participate in width inference?

That is a great question, and the proposal should be expanded with a dicussion of that. I think these are the options:

1. No participation: if you perform a bit-index on an integer with an unspecified width, you must also fully assign to it somewhere else to cause the width to be inferred.
2. No participation: the bit-index can only be used on integers where the width is specified.
3. It only participates in width inference when used as an L-value (currently as proposed the bit-index can only exist as an L-value) and an integer with an unspecified width is inferred to be at least i bits wide if it is used as x[i]. If the width is inferred somewhere else to be a value that is incompatible (a width less than i), then an error is raised.
4. It participates in width inference when used as both an L-value and an R-value in the same way as option 3 (assuming we add support for this being used as an R-value).

Options 1 and 2 are the simplest. Option 3 is perhaps more consistent with the rest of the spec because the bit-index information is used to infer the width. Option 4 is similar to 3 but relies on some other changes, and I'd like to note that currently the bits primop does not participate in width inference on its operand and changing that would be a major change. I'm not sure which one should be chosen, and this is definitely something to discuss.

How does this participate with combinatorial cycle detection?

There is a section in the proposal on combinational loops. The current answer is that combinational loops are allowed if the RHS only depends on bits that are distinct from the bit being assigned. Any operation that uses x depends on all bits of x, except for the bits operation, which only depends on the extracted bits of x (hi to lo). This allows writing certain "loops" (though the rule implies that they end up not being loops at the bit-level) that use the bits primop to extract distinct bits, like those shown in some of the examples in the proposal (e.g., example 6, which is from the Chisel issue tracker).

The FIRRTL spec currently has no wording on combinational loops (that I could find), so I am not sure if this information should go in the spec or if it is up to the implementation.

How do I set 1 bit of one element of a register of type vector of uints?

I think this composes fine on the LHS, although please let me know if there's a mistake I'm missing. For example:

reg r : UInt<4>[2], clock
r[0][1] <= ...

would set bit 1 of element 0. This is allowed by the "reference" production from the FIRRTL language definition.

Questions regarding the syntax, and assigning one bit vs multiple bits:

I think these are good questions with several possible solutions. There is a short discussion of this in the "Multi-bit subword assignment" section in the proposal. I think the possible solutions exist on a spectrum in a tradeoff between having inconsistencies and making large changes to the spec. The current proposal does have inconsistency between the bit-index and the bits primop (the bit-index can only be used on the LHS and only extracts one bit, while the bits primop can only be used on the RHS and extracts a range), but makes a relatively small change to the spec and leaves the way open for future larger enhancements that would bring more consistency (e.g., having a unified slicing operator for integers and vectors).

For example, one alternative is to use bits(x, 1, 0) <= ... syntax instead. This would make the bits primop the only primop that can be used on the LHS. This would also require changing the FIRRTL language definition (specifically the reference production), while the current syntax does not require a change to that grammar. In addition, there is perhaps a long-term goal of creating a general and unified slice operator (using bracket syntax such as x[hi:lo]) for both integers and vectors. Using bits on the LHS does not move towards that, while the current proposal does make a small move in that direction (because in that case x[i] would be allowed as an L-value on integers as well).

There are some other alternatives briefly listed in the full proposal, and a short list of the additional questions they raise.

Perhaps the bit-index should also be allowed on the RHS. I am not sure. But if that is not added in this proposal, it can be added in a future change if desired.

Overall, maybe the best thing would be to introduce [hi:lo]/[i] syntax for integers (and perhaps the slicing for vectors too?) and remove the bits primop. This proposal is a forwards-compatible step in that direction but doesn't go all the way.

There is now a PR in CIRCT that implements this via read-modify-write during the expand-whens pass: https://github.com/llvm/circt/pull/3658.

Logging approval from @azidar via offline discussion.

Any chance that we focus this change only on l-value bit-indices (aka subword assignments)? Why try to fix what is not broken and create extra work by requiring parsers to track types in order to disambiguate between SubAccess ([...]) and Bits (after this proposal also [...])? Since modules might be declared after they are instantiated, knowing all types would require a two pass parser, complicating things quite a bit.

Why try to fix what is not broken and create extra work by requiring parsers to track types in order to disambiguate between SubAccess ([...]) and Bits (after this proposal also [...])?

A parser already needs to track types assuming the parser only wants to build valid IR. 😉 The SFC parser has the appearance of not tracking types, but only because it splits parsing into parsing + InferKinds/CheckKinds + InferTypes/CheckTypes.

Since modules might be declared after they are instantiated, knowing all types would require a two pass parser, complicating things quite a bit.

We already have this problem assuming that we want to reject invalid IR in the parser. However, it's not that bad as it just means a parser need to (1) parse module definitions and (2) parse modules bodies. This is the natural split that arises when building a fast, parallel parser where each module body is parsed in parallel.

A parser already needs to track types assuming the parser only wants to build valid IR.

There is a difference between a parser and a type checker. Parsing is normally context-free whereas type checking does need a context.

We already have this problem assuming that we want to reject invalid IR in the parser.

Again, "type checker" =/= "parser"

But anyways, arguing about what a parser should and should not do isn't very helpful. My argument is that continuing to use bits(..., ..., ...) for R-value bit extraction would be the simplest solution with no important downside that I can see. Otherwise this PR needs to change the bits section in "Expressions" to the new syntax and we need to patch all firrtl serializers. Parsers will have to be able to deal with both legacy and new syntax in order to remain backwards-compatible and the original firrtl compiler would need a more complicated parser. The same would be true for essentially any non-handcrafted parser. So anyone using YACC or antlr or similar would have to hack around the ambiguity around bit-index and SubAccess.

I don't think the [x:y] syntax is ambiguous at the context-free language level -- there aren't multiple possible derivation trees when purely parsing (no types). For type checking, the type checker already needs to be able to look up the type of the value being indexed for vector indexing, so I don't see how this is different.

More generally, I think these are the choices regarding syntax and their downsides:

1. Use bits() for the LHS and RHS
   • Downsides: syntax is inconsistent with vector indexing; the bits() syntax is specifically intended to convey that it can only be used as an R-value (it has a "function call"-like syntax); this involves changing the FIRRTL grammar to allow bits() on the LHS, which is a bit cumbersome: do we remove bits from the primop non-terminal and make it a reference, even though its syntax is like a primop and not like a reference?
2. Use [x:y] for the LHS and RHS
   • Downsides: not backwards compatible, but this can be done for the next major version release of FIRRTL.
3. Use bits() only for the RHS and [x:y] only for the LHS
   • Downsides: inconsistent syntax between the two bits operators; more cumbersome to restrict in the grammar (needs a new non-terminal that can only be used on the LHS, since reference can currently be used on both RHS and LHS).
4. Allow bits() or [x:y] for the RHS and [x:y] only for the LHS (current proposal)
   • Downsides: duplicate syntax for the RHS.
5. Allow bits() or [x:y] for both the LHS and RHS (current implementation in CIRCT)
   • Downsides: duplicate syntax for the RHS and LHS; requires more changes to the FIRRTL grammar to allow bits() on the LHS (move bits to reference instead of primop?). Because of how the CIRCT parser works this is simpler to implement in CIRCT, and accepts a superset of the programs allowed by 4. Removing bits() in the future would resolve this mismatch.

All of these changes require at least a minor version increase, and only 2 requires a major version since it disallows bits() on the RHS. A big reason to have versions is to be able to improve FIRRTL more aggressively without worrying as much about older FIRRTL compilers.

Thanks for presenting this list. I generally prefer option 1 because it is the easiest to parse, but I can see now why you might prefer a different option. One thing to consider is that there are other primops that we might want to consider allowing as L-values in the future: tail, head and cat. (tail and head just being special cases of bits and cat being something that is allowed in Verilog.) Thus the concept of distinguishing between R-value only and L/R-value primops might make some sense.

This proposal has been pending for a long time. How about we all talk this through at the next Chisel meeting on Monday August 29th and make sure we get to a place where we can merge this into the spec on that day?

I started implementing this proposal for the firrtl compiler. One thing that needs to be clarified is how bit-indices interact with DontCare. I.e., describe how you are allowed to do something like x[0] is invalid.

I think it's fine to say that it will mark the particular bits in the integer as invalid. I think this is essentially the same as assigning a special constant with a bitindex, so I'm not sure it really needs any specific changes. I can add some clarifying wording to the invalidates section though.

I can add some clarifying wording to the invalidates section though.

I think that is a good idea. Just clarifying that bit-indices are allowed in a is invalid statement.

Here is my prototype implementation of this spec change for the firrtl compiler: https://github.com/chipsalliance/firrtl/pull/2545

These are my tests, please let me know if any of them disagree with your intention behind the spec: https://github.com/ekiwi/firrtl/blob/sub-word-assign-2/src/test/scala/firrtlTests/SubWordAssignmentTests.scala

I have updated the revision history and marked this as a minor version change. I think if everyone is in agreement this is ready to go. I think once this is merged, https://github.com/llvm/circt/pull/3658 will be ready to merge, and I will open a draft PR for Chisel that uses the IR nodes from Kevin's FIRRTL implementation to provide a Chisel API for this. Thanks everyone!