[RFC] new cover-values statement to efficiently count mutually-exclusive events

[ekiwi]

Checklist

• Did you write out a description of the feature you want to see?
• Did you look around for any related features?

Feature Description

I would like to extend the firrtl spec to add a new cover-values (working name, could easily be changed) statement that excepts any ground type wire as input. This statement asks the simulation backend to count how often each possible value of the input is present on a rising clock edge.

For a 2-bit signal like val a = IO(Input(UInt(2.W))) writing cover-values(a) would now be equivalent to writing:

cover(a === 0.U)
cover(a === 1.U)
cover(a === 2.U)
cover(a === 3.U)

The important difference is that with the cover-values(a) construct, we know by construction, that a has only one value per cycle. Thus the count can be implemented by indexing into an array (for software simulation) or into a memory (for FPGA accelerated simulation).

This new feature would allow us to specify the state coverage metric used by the DiFuzz paper: https://github.com/compsec-snu/difuzz-rtl

I do not know yet what Verilog construct this would best map to. Maybe @seldridge or @jackkoenig have a good idea.

Type of Feature

• firrtl extension

[aswaterman]

Just a thought... for the existing Boolean case, excluding 0 makes sense for obvious reasons. But it's not clear that excluding 0 for the generalized UInt case is the right thing to do. It's also not clear that including all values through 2^w-1 is always the right thing to do either. (Consider covering all states of a state machine, where the valid states are 0..5.) So, maybe the API would benefit from being generalized to accept a range or a set of integral values (or a description of the enum type, in the state-machine example).

[ekiwi]

Thanks for your insightful feedback @aswaterman !

Just a thought... for the existing Boolean case, excluding 0 makes sense for obvious reasons. But it's not clear that excluding 0 for the generalized UInt case is the right thing to do.

I agree. I think I was overzealous to make everything fit into the current cover statement. I now believe that it might be better to have an additional cover-all (or similar) statement that just count how often every possible bit pattern is active, no matter the size of the input.

It's also not clear that including all values through 2^w-1 is always the right thing to do either.

I was planning for this to be a low-level firrtl API, so the new cover-all primitive would not necessarily be exposed to the chisel user directly. The goal is to allow for a significant performance optimization, when the coverage counters can be implemented as an array of counter where only one is updated every cycle. Thus the values covered needs to be on a dense interval to take advantage of this. If they are not, then we have to do the translation to an array index somewhere and the simplest solution would be to just generate combinatorial firrtl code to do the transformation. If you have an interval that does not start at zero but e.g. at 10, then you can always generate a sub(value, UInt(10)) from your chisel library.

One thing I think is worth considering is a max-value hint. Since that would allow you to reduce the memory usage by almost 50%. So for example if you want to cover all values from 0 to 8, then without a max-value hint we would need to allocate an array with 16 entries. If we have a max-value=8 hint, we can just add an assertion in the simulator that the array index is always smaller 9 and then we only would have to allocate memory for 9 counters.

[aswaterman]

I was planning for this to be a low-level firrtl API

Derp. Not sure why I responded in the chisel context, given the repo we're on.

I now believe that it might be better to have an additional cover-all (or similar) statement

Yeah, makes sense.

you can always generate a sub(value, UInt(10))

Yeah, I appreciate the economy of keeping the new primitive zero-based and using additional nodes to map more general input ranges onto the new primitive.

[seldridge]

I'm not an expert on SVA either, but this sounds like a proposal for synthesizable covergroups/coverpoints in FIRRTL and is leading towards also adding support for coverpoint bins. I think the notion of "only caring about a subset of all possible values a signal can take" is equivalent to defining coverpoint bins for the states you care about and then binning everything else into an "invalid" bin (which is likely also useful to know about).

I think both support for emitting SVA coverpoint/covergroup and synthesizing these into hardware is useful. The synthesis of these is pushing more towards FireSim type concepts which have not been previously explored?

We should add whatever ops we need to FIRRTL IR to represent these concepts. I do admit that these concepts are likely far, far easier to implement/model/realize in CIRCT than in Scala FIRRTL and I'm not opposed to prototyping the support in CIRCT first. There's already support for the more SVA-flavored things in CIRCT's SystemVerilog Dialect (e.g., force/release and both concurrent and immediate flavors of assert/assume/cover). I have not needed to add coverpoint/covergroup, but that's clearly missing.

It is likely also worth having @darthscsi weigh in here.