Chisel/FIRRTL工具链做布尔表达式优化吗？

Question

我正在生成由Chisel编译的输入。这样做的简单方式可能会导致次优布尔表达式。例如，我倾向于生成嵌套的Mux()-es链，如下所示：

  x :=
    Mux(!a && !b && !c && d, 13,
        Mux(!a && !b && c, 3,
            Mux(!a && !b, 2,
                Mux(!a && b, temp1,
                    Mux(a && e, 11,
                        Mux(a, 0,
                            -1))))))

如你所见，

1. 一些布尔表达式是重复的，例如"!a"，因此很可能可以使用较少的计算来进行一些优化来表示相同的函数，例如常用的子表达式消除，
2. 再次重复测试，例如"!a"，因此很可能会进行一些优化，将其分解出来并进行一次测试，并且
3. 类似于上面的第2点，表达式非常深，因此可能会进行一些优化，使其更像一棵树，而不是一个线性的Mux序列。

我不做的一件事是有复杂的谓词表达式:每个谓词只是一个术语的连词，每个术语只是一个var或其否定。

我可以尝试在代码生成器中实现这类转换，但这样做，我最终会为布尔表达式编写自己的优化编译器。相反，我是否可以生成上面的内容，并依赖Chisel/FIRRTL工具链来优化这种复杂程度的布尔表达式？这类表达式可能与上面的表达式大小差不多，甚至可能是其大小的两倍。

Answer 1

FIRRTL编译器确实支持公共子表达式消除(CSE)，但不支持全局值编号(GVN)。实际上，您可以预期大多数常见的子表达式将像您在发出的Verilog中所期望的那样进行组合。

FIRRTL编译器不进行mux树优化。综合工具应该能够优化它所给出的任何东西，但不幸的是，情况并不总是如此。因此，Chisel和FIRRTL编译器选择不做mux树优化以保持用户的意图。通常，用户正在编写一些特定的Chisel，目的是通过综合工具以某种方式进行优化。如果FIRRTL编译器重新排序mux树并产生质量的结果(QOR)回归，那就太糟糕了。考虑一下这个评论获得更多的上下文。

也就是说，如果用户真的想在FIRRTL级别应用一些mux重新排序，他们可以编写一个自定义的FIRRTL优化转换(该转换的作用域可能仅限于他们想要优化的模块/区域)。这可能是FIRRTL编译器的一个很好的可选特性。如果您正在生成Chisel，这也是一个可用的选项--在FIRRTL上编写优化可能更简单，而不是在Chisel生成库中。

现在，这是如何与原始示例交互的呢？从一个稍微简化的版本开始：

import chisel3._
import chisel3.internal.sourceinfo.UnlocatableSourceInfo

class Foo extends RawModule {

  private implicit val noInfo = UnlocatableSourceInfo

  val a = IO(Input(Bool()))
  val b = IO(Input(Bool()))
  val c = IO(Input(Bool()))
  val d = IO(Input(Bool()))
  val e = IO(Input(Bool()))

  val x = IO(Output(UInt()))

  x := Mux(!a && !b && !c && d, 1.U,
           Mux(!a && !b && c, 2.U,
               Mux(!a && !b, 3.U,
                   Mux(!a && b, 4.U,
                       Mux(a && e, 5.U,
                           Mux(a, 6.U, 0.U))))))

}

当使用Chisel 3.3.2和FIRRTL 1.3.2编译时，结果是以下Verilog：

module Foo(
  input        a,
  input        b,
  input        c,
  input        d,
  input        e,
  output [2:0] x
);
  wire  _T = ~a;
  wire  _T_1 = ~b;
  wire  _T_2 = _T & _T_1;
  wire  _T_3 = ~c;
  wire  _T_4 = _T_2 & _T_3;
  wire  _T_5 = _T_4 & d;
  wire  _T_9 = _T_2 & c;
  wire  _T_14 = _T & b;
  wire  _T_15 = a & e;
  wire [2:0] _T_16 = a ? 3'h6 : 3'h0;
  wire [2:0] _T_17 = _T_15 ? 3'h5 : _T_16;
  wire [2:0] _T_18 = _T_14 ? 3'h4 : _T_17;
  wire [2:0] _T_19 = _T_2 ? 3'h3 : _T_18;
  wire [2:0] _T_20 = _T_9 ? 3'h2 : _T_19;
  assign x = _T_5 ? 3'h1 : _T_20;
endmodule

意见：

1. CSE正在做它的工作，例如，~a & ~b放在_T_2中并被重用。
2. mux树结构未经修改。

凿子确实有一个为reduceTree定义的Vec方法，它可以用来生成平衡的mux树。此外，在最初的示例中，可能可以用util.MuxCase (不影响生成的mux树)更可伸缩地描述mux链：

x := MuxCase(
  default = 0.U,
  mapping = Seq(
    (!a && !b && !c && d) -> 1.U,
    (!a && !b && c)       -> 2.U,
    (!a && !b)            -> 3.U,
    (!a && b)             -> 4.U,
    (a && e)              -> 5.U,
    (a)                   -> 6.U)
)