Add a few mux-of-const and reg-of-and/or canonicalizers.

[rwy7]

trafficstars

This PR adds four new canonicalization patterns to FIRRTL.

mux(cond, 0, b) -> and(not(cond), b)
mux(cond, 1, b) -> or(cond, b)
mux(cond, a, 0) -> and(cond, a)
mux(cond, a, 1) -> or(not(cond), a)

These canonicalizations are already present for the comb dialect, but we want to run these canonicalizers before lowering layers, which can obscure constant ops behind ports.

The problem with these mux canonicalizers is, they conflict with a register canonicalizer. This register canonicalizer converts a register to a constant, if the register's next-value is a mux of either the register itself, or a constant. For example:

connect(reg, mux(reset, 0, reg)) ==> reg -> 0

These new canonicalizers would transform the connect to:

connect(reg, and(not(reset), reg))

...which prevents the register canonicalizer from running. To get this behaviour back, this PR adds four additional canonicalizations for both registers and reg resets: For registers, the canonicalizers are:

connect(reg, and(reg, x)) ==> reg -> 0
connect(reg, and(x, reg)) ==> reg -> 0

connect(reg, or(reg, x)) ==> reg -> 1
connect(reg, or(x, reg)) ==> reg -> 1

For regresets, we have the same canonicalizers, but with an additional check: the reset value must be a constant zero or one.

reset(reg) = 0 ==> connect(reg, and(reg, x)) ==> reg -> 0
reset(reg) = 0 ==> connect(reg, and(x, reg)) ==> reg -> 0

reset(reg) = 1 ==> connect(reg, or(reg, x)) ==> reg -> 1
reset(reg) = 1 ==> connect(reg, or(x, reg)) ==> reg -> 1

[rwy7]

The symmetry of these may motivate a canonical mux representation. I.e., this could be written as four canonicalizers for each of the four permutations of where a single binary constant could appear or as two canonicalizers for two of the permutations and then one canonicalizer that puts constants in "canonical" position. "Constants last" is the canonical form chosen below:

mux(cond, a, 0) -> and(cond, a)
mux(cond, a, 1) -> or(not(cond), a)
mux(cond, constant, nonconstant) -> mux(~cond, nonconstant, constant)

Do we already have a canonical form form muxes?

This is a cool idea! I don't see anything like this, but I do see a conflicting canonicalization in comb:

mux(!p, x, y) -> mux(p, y, x)

(this canonicalization is missing in FIRRTL)

Usually our canonicalizers are reducing the cost of a computation, but negating the condition would increase the cost. Maybe, putting constants last only makes sense when the op is symmetric and can freely rearrange its operands.

[rwy7]

Have you gotten any data from internal designs?

For the most part, these canonicalizers just shuffle around the source-info comments and variable spilling in the verilog. There are a few places where the expressions are different but not meaningfully so, and I've only spotted one place where a mux actually was optimized away.

[seldridge]

Usually our canonicalizers are reducing the cost of a computation, but negating the condition would increase the cost.

Yes, this would be bad. Given that, I think the right approach is to keep the four canonicalizers and, in a follow-on, add the mux(!cond, a, b) -> mux(cond, b, a).

[dtzSiFive]

Friendly ping -- what's the status of this? Does this need more review or anything else? Thanks!