Delay replacement of invalid signals with 0 until after/during optimizations

[jackkoenig]

Checklist

• [x] Did you write out a description of the feature you want to see?
• [x] Did you look around for any related features?
• [x] Did you specify relevant external information?

Feature Description

There are cases where an invalid path could propagate and optimize away muxes, but because we replace the invalid signal with 0 before optimizations, you end up with a mux. For example.

circuit test :
  module test :
    input in : UInt<8>
    input flag : UInt<1>

    output out : UInt<8>

    wire x : UInt<8>
    x is invalid
    wire y : UInt<8>
    y is invalid

    when flag :
      y <= in
    else :
      y <= x

    out <= y

We end up with a mux for y: y <= mux(flag, in, UInt(0). If we could propagate the "invalidness" of x to constant propagation, this mux could be eliminated.

Type of Feature

• new feature/API

Related Features

I don't know of any.

External Information

Motivating chisel-users thread: https://groups.google.com/u/1/g/chisel-users/c/-zPdKL-Sgp0

[ekiwi]

If we start optimizing based on invalid signals, we need to nail down their semantics a little better.

Looking at the following example:

circuit test :
  module test :
    input clock : Clock
    wire x : UInt<8>
    x is invalid
    node y = x
    assert(clock, eq(sub(x, y), UInt(0)), UInt(1), "x - y === 0.U")

Should the firrtl compile be allowed to generate code that violates the assert? It currently does not.

However, if we include the invalid in the constant prop, we might end up with something like this:

circuit test :
  module test :
    input clock : Clock
    assert(clock, eq(sub(Invalid, Invalid), UInt(0)), UInt(1), "x - y === 0.U")

Now, what is the result of sub(Invalid, Invalid)? If the invalids come from two independent sources, I would say that it could be anything. However, since they come from the same source, maybe, the results should always be zero.

[ekiwi]

Example with two muxes that might not be possible to optimize if we require that a single source of invalid always has the same value:

circuit test2 :
  module test2 :
    input in : UInt<8>
    input in2 : UInt<8>
    input flag : UInt<1>

    output out : UInt<8>
    output out2 : UInt<8>

    wire x : UInt<8>
    x is invalid
    wire y : UInt<8>
    y is invalid
    wire y2 : UInt<8>
    y2 is invalid

    when flag :
      y <= in
      y2 <= in2
    else :
      y <= x
      y2 <= x

    out <= y
    out2 <= y2

Verilog:

module test2(
  input  [7:0] in,
  input  [7:0] in2,
  input        flag,
  output [7:0] out,
  output [7:0] out2
);
  assign out = flag ? in : 8'h0; // @[]
  assign out2 = flag ? in2 : 8'h0; // @[]
endmodule

Invariant that would be violated by the proposed optimization:

(!flag) => (out == out2)

To clarify the optimization we are talking about here would yield:

module test2(
  input  [7:0] in,
  input  [7:0] in2,
  input        flag,
  output [7:0] out,
  output [7:0] out2
);
  assign out = in;
  assign out2 = in2;
endmodule

An alternative that would preserve the invariant and get rid of one mux would be:

module test2(
  input  [7:0] in,
  input  [7:0] in2,
  input        flag,
  output [7:0] out,
  output [7:0] out2
);
  assign out = in; // @[]
  assign out2 = flag ? in2 : in; // @[]

[seldridge]

FYI: MLIR FIRRTL Dialect added and uses an invalid expression in https://github.com/llvm/circt/commit/052de6df6f4ba9d0b75c7ef9966bf8f3a80a7433. This should enable better invalid-ness as specific values are now assigned invalid (and these can then be the same or different).

[ekiwi]

FYI: MLIR FIRRTL Dialect added and uses an invalid expression in llvm/circt@052de6d. This should enable better invalid-ness as specific values are now assigned invalid (and these can then be the same or different).

Does this mean that optimizing my example to the following is now legal in MLIR FIRRTL?

module test2(
  input  [7:0] in,
  input  [7:0] in2,
  input        flag,
  output [7:0] out,
  output [7:0] out2
);
  assign out = in;
  assign out2 = in2;
endmodule

We really should document the "correct" interpretation of invalid in the firrtl spec before compilers start taking advantage of it.

[seldridge]

@ekiwi: Currently CIRCT has an invalid value and is doing optimizations on it. This will result in the exact Verilog that you show in the above comment. (out = in; out2 = in2;)

I'm extremely nervous that invalid being undefined means that a FIRRTL compiler can choose to make extremely aggressive optimizations that are going to cause deviations from Chisel code. I'm doubly worried by the fact that Chisel and Chisel2 compatibility mode is likely to introduce assumptions where foo := DontCare being optimized to zero may be necessary for correct functionality.

[ekiwi]

I'm extremely nervous that invalid being undefined means that a FIRRTL compiler can choose to make extremely aggressive optimizations that are going to cause deviations from Chisel code. I'm doubly worried by the fact that Chisel and Chisel2 compatibility mode is likely to introduce assumptions where foo := DontCare being optimized to zero may be necessary for correct functionality.

Does CIRCT use invalid to optimize divison by zero or out-of-bounds accesses? If so it might actually violate the spec.

[seldridge]

Not that I'm aware of. The current division folds are:

• div(_, invalid) -> 0
• div(a, a) -> 1
• div(x, 1) -> x (this is uncontroversial...)

There is nothing that is producing invalid for those situations as far as I'm aware, e.g., div(a, 0) -> invalid does not exist.

The current one that I'm worried about is stuff like:

circuit Foo :
  module Foo :
    input a: UInt<1>
    output b: UInt<1>

    wire w: UInt<1>
    w is invalid

    b <= xor(a, w)

CIRCT will fold xor(_, invalid) -> invalid resulting in b = 0; whereas Scala FIRRTL will produce b = a; due to xor(a, 0) -> a.

[ekiwi]

CIRCT will fold xor(_, invalid) -> invalid resulting in b = 0; whereas Scala FIRRTL will produce b = a; due to xor(a, 0) -> a.

That is fine. Probably should be a warning though.