[RFC] Strong, Annotated Enums

[hngenc]

In response to deafening demand from billions of Chisel users worldwide, I am proposing a new enum API that addresses the concerns raised in #373. It aims to deliver a new strongly-typed enum class that is automatically annotated for the convenience of FIRRTL transforms and waveform viewers.

Motivation

Enums in Chisel suffer from the following deficiencies:

• They are weakly-typed, and completely interchangeable with any UInt.
• They do not preserve their names when translated to FIRRTL, so HDL backends and waveform viewers cannot make any use of them.
• The current API only allows enums to be given sequential values. Users cannot map their enums to custom values (such as for one-hot states).
• The current API requires users to count their enum values by hand. This is annoying, especially when adding new enum values.

Existing Solutions

Here, I list existing enum implementations in Scala and Chisel to see if any satisfy our needs. Unfortunately, Scala 2's lack of an enum keyword make most of these solutions feel awkward.

Chisel

First, of course, there is Chisel's current enum API:

val sIdle :: s1 :: s2 :: Nil = Enum(3)

The weaknesses of this approach have already been discussed above, but it does get points for being concise and readable.

Scala Enumeration Class

A simple example can be seen below:

object MyEnums extends Enumeration {
  val sIdle, s1, s2 = Value
}

If the user wishes, they can also map specific enums to custom integers:

object MyEnums extends Enumeration {
  val sIdle, s1 = Value
  s3 = Value(10)
}

This API addresses some of our concerns. It is also easy to iterate over the enum values after they are created using the MyEnums.Values set. Unfortunately, it has the following drawbacks that make it unsuitable for use in Chisel:

• Scala's enums can be mapped to integers and strings, but not to UInts or other Chisel datatypes.
• Scala's enums are weakly-typed. All enumerations, even if they are in different objects, share the same type.

Scala Case Objects

An example of this enum implementation can be seen in the Chisel JTAG FSM. A simplified example is shown below:

sealed abstract class MyEnum(val id: Int) {
  def U: UInt = id.U
}

object MyEnum {
  val all: Set[MyEnum] = Set(sIdle, s1, s2)
}

case object sIdle extends MyEnum(0)
case object s1 extends MyEnum(1)
case object s2 extends MyEnum(2)

This method is quite powerful, as the enum is actually a new class that the user may customize in whatever way they wish. They can add new methods to the MyEnum class, or add new parameters to its constructor for pattern-matching purposes. However, this method also has its weaknesses:

• It is not concise. There is a lot of boilerplate code that the user has to write, even if they want very simple functionality.
• The MyEnum class has to be casted into UInt form whenever the user wishes to plug it into a Chisel function. Therefore, type-safety is lost in the places where it matters most.
• When a new enum is added, the all set has to be updated. This is easy to forget, but if we abandon the all set, then we lose an easy way to iterate over enum values.

Enumeratum

Enumeratum is a popular third-party implementation of enums in Scala. It is advertised as being "type-safe, reflection-free, powerful...with exhaustive pattern match warnings." A simple example is presented below:

import enumeratum._

sealed trait MyEnum extends EnumEntry

object MyEnum extends Enum[MyEnum] {
  val values = findValues // This is a required macro

  case object sIdle extends MyEnum
  case object s1 extends MyEnum
  case object s2 extends MyEnum
}

If users want to give custom, non-sequential values to their enums, they can use the following code:

import enumeratum.values._

sealed abstract class MyEnum(val value: Int, val name: String) extends IntEnumEntry

case object MyEnum extends IntEnum[MyEnum] {
  val values = findValues

  case object sIdle extends MyEnum(0, name = "sIdle")
  case object s1 extends MyEnum(1, name = "s1")
  case object s2 extends MyEnum(value = 10, name = "s2")
}

Enumeratum is a great library. The enums it provides are type-safe and are checked at compile-time for uniqueness. However, it too presents some drawbacks:

• I don't believe there is a way to map enum values to Chisel datatypes.
• There is still too much boilerplate for my personal taste. In particular, being required to define each enum on a separate line seems overly-verbose.
• Our project would depend upon another third-party library.

Scala 3 Enums

Finally, Scala 3 will include the enum keyword. This is pretty much as close to an ideal API as we're gonna see in this RFC (because I'm not gonna go over enums in other languages):

enum MyEnum {
  case sIdle, s1, s2
}

The enums can be mapped to custom values are seen in this example:

enum MyEnum(val x: Int) {
  case sIdle extends MyEnum(0)
  case s1 extends MyEnum(1)
  case s2 extends MyEnum(10)
}

So, pretty similar to C++ enums, but more verbose when specifying custom values. The drawbacks, unfortunately, are devastating:

• We can't wait for Scala 3

Proposed Solution

Developers will use the following API to create their own enum classes:

class MyEnum extends EnumType

object MyEnum extends StrongEnum[MyEnum] {
  val sIdle, s1, s2 = Value
  val sCustom = Value(100.U)
}

Later, in a module, the user could access the enum values as below:

val state = RegInit(MyEnum.sIdle)
val next_state = Mux(cond, MyEnum.sIdle, MyEnum.s1)

val all_values = MyEnum.Values

I'm not settled on naming the new types EnumType and StrongEnum. I can take suggestions for better names if anyone has them. In either case, the pros and cons of this new API are discussed below.

Pros:

• The enums are all Chisel datatypes, inheriting from either Data or Element. Thus, they can be used in muxes, bundles, vecs, or whatever.
• The enums are strongly-typed, rather than just being aliases for UInts. Thus, the following code will be illegal: Mux(cond, sIdle, 0.U).
• All instances of EnumType and its subclasses will automatically annotate themselves when they are created. Thus, we shall be able to annotate every wire, register, and node that is of type MyEnum without any fancy macros.
• The enums are all grouped into a single set of curly braces, as in most other languages. This also has the advantage of placing them all into their own "namespace".
  • If users wish, they can import MyEnum._ to bring all enum names into the existing namespace.
• The enums can be iterated over using the MyEnum.Values list.
• This format bares strong resemblances to Scala's default enumeration API (as well as to Enumeratum).
• The code is less verbose than Scala's case objects or Enumeratum.

Cons:

• The enums can only be mapped to UInts. However, as per #373, this may be the preferred behavior anyway. In any case, the user-facing API does leave open the possibility of incorporating signed enums in the future.
• The EnumType class will have to be mutable, even when it is a literal type. This is to spare the user the inconvenience of typing out EnumType's constructor parameters. Those parameters will be stored as vars instead, and accessed through special constructFromLiteral methods that the user won't touch.
  • It is possible that there is a workaround here that someone more familiar with Scala will be able to point out to me, but StackOverflow seems to suggest otherwise.
• There will probably not be any pattern-matching checking capabilities, but I'm not really sure how often that will be needed anyway. Developers will just have to be vigilant to make sure they give default cases to all their pattern-matching functions when operating on EnumTypes.
• The code is slightly more verbose than Scala's built-in enumerations, and considerably more verbose than the existing Chisel enums.

Implementation

I've constructed a toy example of the EnumType and StrongEnum classes already in a personal project outside of Chisel. I'm 95% confident that the above API can be implemented without any modifications to existing Chisel code. New code will simply be added in to new files.

There will have to be heavy use of reflection, though hopefully no macros. As mentioned above, a few classes that should ideally be immutable will have to be mutable in order to work around Scala's syntax. This could possibly be confusing to future maintainers.

TLDR

Chisel's existing enum implementation is good for simple use-cases, but not so useful outside of them. Other existing enum implementations in Scala also have drawbacks that I believe preclude their use in Chisel. I propose a new StrongEnum API that looks similar to Scala's built-in enumerators, but which has several advantages over them.

[mwachs5]

I skimmed this. Here is a pattern that I currently use a lot (from https://github.com/freechipsproject/rocket-chip/blob/master/src/main/scala/devices/debug/Debug.scala#L920)

    object CtrlState extends scala.Enumeration {
      type CtrlState = Value
      val Waiting, CheckGenerate, Exec, Custom = Value

      def apply( t : Value) : UInt = {
        t.id.U(log2Up(values.size).W)
      }
    }

I like this pattern because it gives the user access to both the integer and UInt values, without asking the user to figure out how to do the cast every time.

What does your proposed solution actually EMIT? Since the problem seems to mostly be that nothing is emitted into the downstream FIRRTL/Verilog code.

[hngenc]

Your pattern is the default Scala enumeration pattern with an apply added. This works fine for many cases, but it sacrifices type-safety. Additionally, I don't agree that the user is spared the inconvenience of figuring out how to cast. To get UInt values, they have to remember to call CtrlState(Waiting), and to get integer values, they have to call Waiting.id. But I agree that that isn't a big burden. In my proposed solution, users would cast to UInts and integers through the asUInt() and litValue functions, which I believe are consistent with other Chisel datatypes. But in most cases, like when connecting wires or registers, they won't have to cast anything.

Neither FIRRTL nor Verilog have any concept of enumerations (unlike VHDL), so the emitted code would still replace enums with UInts. However, my proposed solution would generate FIRRTL annotations describing which signals are mapped to which enums. I'm told that there is a waveform viewer in the works that will be able to read those annotations and display the signals accordingly.

[seldridge]

Yeah, both Data and Element have asUInt as an abstract member, so any concrete children would implement this. Users would get easy StrongEnum => UInt conversion for free.

Also, @hngenc: this proposal wouldn't have any effect on use of the Scala enumeration pattern, correct? (... since that's all out-of-band with Chisel Enum/StrongEnum?)

SystemVerilog does support enumerated types (while Verilog does not). If you have suitable annotations, then the SystemVerilog emitter should be able to be modified to emit actual enums as opposed to logic (or whatever it's doing).

Two questions/comments on my end so far:

1. What mathematical operations should be allowed on enumerated types (if any)? Do these fit within the standard Num hierarchy?
2. The emission of SystemVerilog enums would be hugely beneficial. I think that an implementation of this would lay all the necessary groundwork. Are there any foreseeable problems with doing this?

One thought:

• A benefit of this is that you get static type safety. However, I think there's an implied assertion here. Anything that is a StrongEnum, e.g., state and next_state, should never be any value which is not one of the enumerated types. It seems like you should be able to also emit an assertion (perhaps optionally) that checks that state and next_state are never given an invalid run-time value.

[mwachs5]

" In my proposed solution, users would cast to UInts and integers through the asUInt() and litValue functions, "

That sounds good, and I agree that doing it the more chisely way is better than a one-off.

[mwachs5]

As a note, For non-system Verilog, I have seen a coding style which use things like:

module foo() begin
  `localparam IDLE=2'h00
  `localparam BUSY=2'h01
...
end
...

But if this PR is not about what is actually emitted and is just emitting annotations, that seems like not worth debating here.

[chick]

I wonder if it might not be better to design your FSM API first then invent the enumeration API to service that. I think your background analysis look very good, but I'd guess you'd find patterns in the FSM that would guide the enumeration decisions.

[mwachs5]

But enumerations are much more useful than for FSMs. E.g. for encoding command types.

[hngenc]

@seldridge Correct, this proposal wouldn't have any effect on scala.Enumeration. To answer your other two questions:

1. We would permit equality and ordering checks like ===, < and >. The enums would not extend Num, because I don't think it makes sense to multiply or divide them. I am still undecided about adding the ability to add to or subtract from enums. If we do add this ability, we would have to decide whether + simply increments the UInt value or whether it goes to the next enum in the list. Perhaps it would be best to require that the user overload this operator.
2. There is one problem that I forsee: One of the main advantage of enums in SystemVerilog seems to be that the synthesizer can choose which values to assign to them. However, in my implementation, all enum values would already have been tied to certain literals by the time they were emitted into FIRRTL. Thus, we would lose this advantage. It would be easiest on my end if FIRRTL added a new enum construct, but that seems unlikely. I'll put some more thought into overcoming this. I feel like more descriptive annotations may do the trick.

Your assertion idea sounds good. I don't think there would be any trouble emitting those.

[hngenc]

@chick Yeah, I could draw up an FSM proposal as well before diving into this, just to make sure that there are no blind spots that I'm missing. But I agree with @mwachs5 that Chisel enums should be designed to support more general use-cases.

Edit: Actually, I think you're right @chick. I'll design the FSM API concurrently, just to make sure they fit together smoothly.

[ducky64]

This looks good!

Some thoughts:

• What happens if you have have multiple val ... = Value lines? Do they continue numbering from the previous? What if you have a (or several) val ... = Value(...) which fixes a value interspersed in there? What happens if there's overlap / duplication?
• Pattern matching: there generally isn't native-like pattern matching support for Chisel types, since we have no control over the match statement. The closest we get is the switch construct, which this would need to work well with.
• Why does EnumType need to be mutable beyond the (semi)mutability needed for bindings? I'm probably missing something real obvious here...
• As for Enumeratum, some of the drawbacks could be addressed by taking the ideas and reimplementing them in a Chisel-specific way. But there is definitely a lot of boilerplate, and I don't see any semantic or syntax benefits over your proposal, which seems like a mix of the best parts of Enumeratum and Scala enums.
• Yes, emitter changes are out of the scope of this RFC, but this appears to lay the groundwork. Also, having a standardized enum API would be nice to get everyone writing the same style of Chisel, instead of everyone and their dog (or plush duck) devising some homebrew enum API, and everyone learning like 10 styles of enum, and when emitter upgrades do come around it doesn't work with everyone's distinctive style.

[hngenc]

@ducky64 Thanks!

What happens if you have have multiple val ... = Value lines?

Each Value will continue incrementing from the previous value. If there are any val v = Value(x) calls interspersed, then x will be the new number that we increment from. This is similar to C++ style enums. Duplicates will be forbidden, and for each val v = Value(y) call, y will have to be greater than the last value. This should prevent overlap.

The closest we get is the switch construct, which this would need to work well with.

As long as the enum is a literal, I believe it'll work with switch.

Why does EnumType need to be mutable beyond the (semi)mutability needed for bindings?

Because I don't want to force the user to re-type its constructor parameters. Consider this dummy example of EnumType:

class EnumType (width: Int, lit: Option[LitArg]) extends Data {
...
}

class MyEnum(width: Int, lit: Option[LitArg]) extends EnumType(width, lit)

Basically, the user will be required to repeat the constructor parameters of EnumType every time they want to create their own enum. This seems overly verbose to me. The only workaround I could find was something like this:

class EnumType extends Data {
  var width: Int
  var lit: Option[LitArg]

  def constructFromLiteral(w: Int, l: Option[LitArg]) = { width = w; lit = l }
  ...
}

class MyEnum extends EnumType

Its kind of hacky, so if anyone has a better idea, I would be eager to hear it.

[ducky64]

Going into implementation details now:

• litArg as a Data field has been removed, the literal value information is now part of the binding. I'd imagine that your enumeration values (objects) would be bound to a literal by the = Value assignment.
• As for width, that's only a required field for a Element subtype, so I don't think you need to worry about that.
• I don't think every instance of the enum chisel type needs a copy of width. I think that's something that could be determined once during the = Value calls, and stored in a class variable (could be Option type, initialized to None, write-once) and referred to when needed in the future. This would also make the MyEnum type directly instantiable, which should fit with the similar Bundle pattern.
• Related: in your example, can you provide an example of how you would use the MyEnum as a chisel type, for instance, instantiating a register of MyEnum type without an initial value?
• I may also be missing some implementation detail that precludes the above.

[hngenc]

Huh, I hadn't known that litArg was removed. I see now that I've been looking at the 3.1.2 branch. But I don't think any of the changes in master should change my planned public API.

You're right about width. The width of the enums could be stored in their companion object. That is where it must be calculated anyway, to make sure that all instances are wide enough to store every possible enum value.

[C]an you provide an example of how you would use the MyEnum as a chisel type, for instance, instantiating a register of MyEnum type without an initial value?

I'm planning to get this working first:

val r = Reg(new MyEnum())

Afterwards, I might be able to drop the new keyword to get this:

val r = Reg(MyEnum())

[hngenc]

If anybody is interested, I've made a pull request for my enum implementation: #892.