Emit better code for linear mux trees

[seldridge]

The FIRRTL Dialect doesn't have a switch primitive and instead relies on mux trees to describe conditional assignment. Some of these mux trees are super regular and could be raised to more semantically meaningful Verilog/SystemVerilog constructs like case, casex, or casez.

Add the case variants to the SystemVerilog dialect and explore raising mux trees into these.

Example

The following FIRRTL code is describing a seven segment decoder which would look a lot better as a case:

circuit SevenSegmentDecoder :
  module SevenSegmentDecoder :
    input in : UInt<4>
    output out : UInt<7>

    node _T = eq(UInt<4>("h1"), in) 
    node _T_1 = mux(_T, UInt<6>("h6"), UInt<6>("h3f")) 
    node _T_2 = eq(UInt<4>("h2"), in) 
    node _T_3 = mux(_T_2, UInt<7>("h5b"), pad(_T_1, 7)) 
    node _T_4 = eq(UInt<4>("h3"), in) 
    node _T_5 = mux(_T_4, UInt<7>("h4f"), _T_3) 
    node _T_6 = eq(UInt<4>("h4"), in) 
    node _T_7 = mux(_T_6, UInt<7>("h66"), _T_5) 
    node _T_8 = eq(UInt<4>("h5"), in) 
    node _T_9 = mux(_T_8, UInt<7>("h6d"), _T_7) 
    node _T_10 = eq(UInt<4>("h6"), in) 
    node _T_11 = mux(_T_10, UInt<7>("h7d"), _T_9) 
    node _T_12 = eq(UInt<4>("h7"), in) 
    node _T_13 = mux(_T_12, UInt<7>("h7"), _T_11) 
    node _T_14 = eq(UInt<4>("h8"), in) 
    node _T_15 = mux(_T_14, UInt<7>("h7f"), _T_13) 
    node _T_16 = eq(UInt<4>("h9"), in) 
    node _T_17 = mux(_T_16, UInt<7>("h6f"), _T_15) 
    node _T_18 = eq(UInt<4>("ha"), in) 
    node _T_19 = mux(_T_18, UInt<7>("h77"), _T_17) 
    node _T_20 = eq(UInt<4>("hb"), in) 
    node _T_21 = mux(_T_20, UInt<7>("h7c"), _T_19) 
    node _T_22 = eq(UInt<4>("hc"), in) 
    node _T_23 = mux(_T_22, UInt<7>("h39"), _T_21) 
    node _T_24 = eq(UInt<4>("hd"), in) 
    node _T_25 = mux(_T_24, UInt<7>("h5e"), _T_23) 
    node _T_26 = eq(UInt<4>("he"), in) 
    node _T_27 = mux(_T_26, UInt<7>("h79"), _T_25) 
    node _T_28 = eq(UInt<4>("hf"), in) 
    out <= mux(_T_28, UInt<7>("h71"), _T_27)

Currently, CIRCT produces the following Verilog for this (firtool -lower-to-rtl -enable-lower-types -verilog SevenSegmentDecoder.fir):

module SevenSegmentDecoder(
  input  [3:0] in,
  output [6:0] out);

  assign out = &in ? 7'h71 : in == 4'hE ? 7'h79 : in == 4'hD ? 7'h5E : in == 4'hC ? 7'h39 : in == 4'hB ? 7'h7C : in == 4'hA ? 7'h77 : in == 4'h9 ? 7'h6F : in == 4'h8 ? 7'h7F : in == 4'h7 ? 7'h7 : in == 4'h6 ? 7'h7D : in == 4'h5 ? 7'h6D : in == 4'h4 ? 7'h66 : in == 4'h3 ? 7'h4F : in == 4'h2 ? 7'h5B : {1'h0, in == 4'h1 ? 6'h6 : 6'h3F};	// SevenSegmentDecoder.fir:2:3, :6:15, :7:{17,40}, :8:17, :9:{17,27}, :10:17, :11:{17,27}, :12:17, :13:{17,27}, :14:17, :15:{17,27}, :16:18, :17:{18,29}, :18:18, :19:18, :20:{18,21}, :21:{18,29}, :22:{18,21}, :23:{18,29}, :24:{18,21}, :25:{18,29}, :26:{18,21}, :27:{18,29}, :28:{18,21}, :29:18, :30:{18,21}, :31:{18,29}, :32:{18,21}, :33:{18,29}, :34:18, :35:{18,29}
endmodule

The Scala FIRRTL Compiler is more structurally similar to the input FIRRTL, but is still structural (firrtl -i SevenSegmentDecoder.fir):

module SevenSegmentDecoder(
  input  [3:0] in,
  output [6:0] out
);
  wire [5:0] _T_1 = 4'h1 == in ? 6'h6 : 6'h3f;
  wire [6:0] _T_3 = 4'h2 == in ? 7'h5b : {{1'd0}, _T_1};
  wire [6:0] _T_5 = 4'h3 == in ? 7'h4f : _T_3;
  wire [6:0] _T_7 = 4'h4 == in ? 7'h66 : _T_5;
  wire [6:0] _T_9 = 4'h5 == in ? 7'h6d : _T_7;
  wire [6:0] _T_11 = 4'h6 == in ? 7'h7d : _T_9;
  wire [6:0] _T_13 = 4'h7 == in ? 7'h7 : _T_11;
  wire [6:0] _T_15 = 4'h8 == in ? 7'h7f : _T_13;
  wire [6:0] _T_17 = 4'h9 == in ? 7'h6f : _T_15;
  wire [6:0] _T_19 = 4'ha == in ? 7'h77 : _T_17;
  wire [6:0] _T_21 = 4'hb == in ? 7'h7c : _T_19;
  wire [6:0] _T_23 = 4'hc == in ? 7'h39 : _T_21;
  wire [6:0] _T_25 = 4'hd == in ? 7'h5e : _T_23;
  wire [6:0] _T_27 = 4'he == in ? 7'h79 : _T_25;
  assign out = 4'hf == in ? 7'h71 : _T_27;
endmodule

Ideally, this would be represented as something like:

always_comb begin
  case(in)
    4'h0:    out = 7'h3F;
    4'h1:    out = 7'h06;
    4'h2:    out = 7'h5B;
    4'h3:    out = 7'h4F;
    4'h4:    out = 7'h66;
    4'h5:    out = 7'h6D;
    4'h6:    out = 7'h7D;
    4'h7:    out = 7'h07;
    4'h8:    out = 7'h7F;
    4'h9:    out = 7'h6F;
    4'hA:    out = 7'h77;
    4'hb:    out = 7'h7C;
    4'hC:    out = 7'h39;
    4'hd:    out = 7'h5E;
    4'hE:    out = 7'h79;
    4'hF:    out = 7'h71;
  endcase
end

This example came from using the MuxLookup utility in Chisel. See this Scastie snippet.

[lattner]

Ok, I added IR and ExportVerilog support for sv.casez in patches leading up to 7b7b7b6. If the printed IR looks right to you then I'll add some pattern matching to form these nodes.

[seldridge]

@lattner: I think this looks fine modulo use of '?' in the match as opposed to 'x' (which I don't think works with casez).

After looking into this more, we should tread carefully with promoting things to casez. Cliff Cummings analyses are probably worth examining: http://www.sunburst-design.com/papers/CummingsSNUG1999SJ_SynthMismatch.pdf.

From what I've gathered from skimming some casez sections in there... this is generally safe, but can yield simulation mismatches as this will (in simulation only?) match on z. Usage of true high impedance z is mostly rare in designs or relegated to things far away from case-like structures (e.g., a high speed serial driver probably wouldn't use this, but instruction decode would). However, if we aggressively promote if/else to casez we may wind up with usages of casez in places that a human designer would never use (e.g., that hypothetical high speed serial driver).

Therefore, we may want to think about how to defensively program warnings or errors to (in simulation) catch if a true z is getting passed in. E.g., if we pattern match and promote to casez with wildcards, then maybe we should also emit an ifdef-guarded if (foo === 1'bz) { assert(...) }.

Any use of casex is likely to blow up a design as that will match on x. Annoyingly, x has a way of leaking into designs either intentionally as poison or unintentionally due to how Verilog likes to generate these for everything.

tl;dr: Pattern matching to case is probably awesome. Tread carefully with casez, tread extremely carefully with casex and consider not using.

[seldridge]

Small clarification. The 'x' needs to be changed to either 'z', 'Z', or '?' for casez. Any of these are equivalent. However, rough consensus is that '?' is preferred over the former two.

I expect that tooling or linting will want one style over another. I have not verified this hypothesis with any data points.

[lattner]

Cool, I'll change it to ?.

I think the concerns about casez is mostly about human authored cases, but I think there is an important point to define: I think we should require casez to always be "total", e.g. that the last case is always required to be a default.

[lattner]

Switched to ? in a4a857e

[lattner]

See also the crazy case that seems like it would be better as a casez in #668

[lattner]

Here's another testcase:

hw.module @top_mod(%sel: i2, %a: i8, %b: i8, %c: i8) -> (%y: i8) {
    %c0_i2 = hw.constant 0 : i2
    %c1_i2 = hw.constant 1 : i2
    %c-1_i8 = hw.constant -1 : i8
    %c-2_i2 = hw.constant -2 : i2
    %0 = comb.icmp eq %sel, %c-2_i2 : i2
    %1 = comb.mux %0, %c, %c-1_i8 : i8
    %2 = comb.icmp eq %sel, %c1_i2 : i2
    %3 = comb.mux %2, %b, %1 : i8
    %4 = comb.icmp eq %sel, %c0_i2 : i2
    %5 = comb.mux %4, %a, %3 : i8
    hw.output %5 : i8
  }

[lattner]

instead of directly generating alwayscomb + switch, we should instead lower to array_create/array_get, and allow PrettifyVerilog to generate switches when appropriate.