[FIRRTL] Stable Randomization Across Optimization Modes

[seldridge]

For different cocktails of optimizations, Verilog generated from FIRRTL Dialect can produce different randomizations for the same seed.

Consider the following circuit with three registers:

circuit Foo:
  module Foo:
    input clock: Clock
    input d: UInt<4>
    output q: UInt<4>

    reg _r: UInt<4>, clock
    _r <= d

    reg r: UInt<4>, clock
    r <= d

    reg s: UInt<4>, clock
    s <= d

    q <= s

Under -preserve-values=all, the randomization is:

`define RANDOM $random
reg [31:0] _RANDOM;
_RANDOM = {`RANDOM};

_r = _RANDOM[3:0];
r = _RANDOM[7:4];
s = _RANDOM[11:8];

Under -preserve-values=named, the randomization is:

r = _RANDOM[3:0];
s = _RANDOM[7:4];

Under -preserve-values=none, the randomization is:

s = _RANDOM[3:0];

For the exact same seed each circuit will produce a different result.

This is problematic for a situation where a user observes a failure at a higher optimization level and needs to debug it on a lower optimization level. It would be ideal if the randomization was portable across optimization levels.

A naive approach would be to change the randomization to randomize all n-bit things with the same random value, at the cost of more correlated randomization and potentially making it harder to expose design bugs through random testing.

Note: this example is specifically constructed to take advantage of value preservation. There may exist similar situations where a used register is optimized away on one optimization level, but not on another. This is just the simplest example I could think of to show the problem.

[mwachs5]

The naive approach is not great, such an approach can lead to missed issues...

Could we write a wrapper around random number generation that does some hash of the hierarchal path + seed to give a deterministic random value?

[seldridge]

The naive approach is not great, such an approach can lead to missed issues...

That's my worry, too.

Could we write a wrapper around random number generation that does some hash of the hierarchal path + seed to give a deterministic random value?

This makes sense to try!

The only limitation is that different optimization levels need to preserve the hierarchy. This is a reasonable limitation. This may not work if there are more advanced optimizations, e.g., compiler-elective instance inlining driving by some cost model.

Thinking more, I think the randomization actually needs to be parametric, but communicated via the instance hierarchy. I have a hypothetical use case as follows: some module deep in the design throws an assert. I then extract the stimulus of this unit. However, if randomization is based only on hierarchy, then running the unit in isolation will result in different randomization and my extracted stimulus may no longer work. If instead, there is a per-instance seed assigned based on the hierarchy, I can both use the existing stimulus and know what parameter to set to get the exact same behavior.

WDYT?

[seldridge]

Stable randomization was implemented in https://github.com/llvm/circt/pull/3714.