chisel - Chisel/FIRRTL 工具链是否进行 bool 表达式优化？

Question

我正在生成要由 Chisel 编译的输入。以简单的方式进行操作可能会导致 bool 表达式不理想。例如，我倾向于生成嵌套的 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. 一些 bool 表达式是重复的，例如“!a”，因此可能可以进行一些优化以使用更少的计算来表达相同的函数，例如公共(public)子表达式消除，

2. 再次重复测试，例如“!a”，因此可能会进行一些优化以将其分解并测试一次，并且

3. 与上面的第 2 点类似，表达式非常深，因此可能可以进行一些优化，使其更像一棵树，而不像 Mux-es 的线性序列。

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

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

Answer 1

FIRRTL 编译器不支持通用子表达式消除 (CSE)，但不支持全局值编号 (GVN)。实际上，您可以预期最常见的子表达式将按照您在发出的 Verilog 中的预期进行组合。

FIRRTL 编译器不进行多路复用树优化。综合工具应该能够优化它所提供的任何东西，但遗憾的是，情况并非总是如此。因此，Chisel 和 FIRRTL 编译器选择不进行 mux 树优化以保留用户的意图。通常，用户正在编写一些特定的 Chisel，旨在通过综合工具以某种方式进行优化。如果 FIRRTL 编译器对 mux 树重新排序并产生结果质量 (QOR) 回归，那真的很糟糕。考虑这个 comment了解更多上下文。

也就是说，如果用户真的想在 FIRRTL 级别应用一些多路复用器重新排序，他们可以编写自定义 FIRRTL 优化转换(可能仅限于他们想要优化的模块/区域)。这可能是 FIRRTL 编译器的一个很好的可选功能。如果您正在生成 Chisel，这也是一个可用的选项——通过 FIRRTL IR 而不是在 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 树结构未修改。

Chisel 确实为 Vec 定义了一个 reduceTree 方法，可用于生成平衡的多路复用树。此外，原始示例中的多路复用器链可能可以用 util.MuxCase 进行更灵活的描述(不影响生成的多路复用器树):

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)
)