llvm / llvm/circt

[FIRRTL][HW] Large, sparse SubAccess cost-driven conversion?

Open
#6,234 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C++
Stars
2.2k
Forks
524
Avg merge
3d 2h
Merged PRs (30d)
46

Description

For situations involving a sparse subaccess/dynamic index, it may make sense to consider cost-based conversion to if/else. I don't know exactly where to draw the line here or if CIRCT should even do this. I would assume that backend tools are able to handle this just fine.

### Motivating Example

Currently, Chisel lets you write something like the following. (You can run this like `scala-cli Foo.scala -- 4` or `scala-cli Foo.scala -- 8`; the argument is the size of the address). This is a module which has a sparse array (all zeros and one one) and a subaccess into it:

```scala
//> using scala "2.13.11"
//> using lib "org.chipsalliance::chisel::6.0.0-M3"
//> using plugin "org.chipsalliance:::chisel-plugin::6.0.0-M3"
//> using options "-unchecked", "-deprecation", "-language:reflectiveCalls", "-feature", "-Xcheckinit", "-Xfatal-warnings", "-Ywarn-dead-code", "-Ywarn-unused", "-Ymacro-annotations"

import chisel3._
import circt.stage.ChiselStage

class Foo(addrSize: Int) extends Module {
val addr = IO(Input(UInt(addrSize.W)))
val out = IO(Output(UInt(8.W)))

val a = WireInit(Vec(BigInt(2).pow(addrSize).toInt, UInt(8.W)), DontCare)
a(0) := 1.U

out :<>= a(addr)
}

object Main extends App {
println(
ChiselStage.emitSystemVerilog(
gen = new Foo(args(0).toInt),
firtoolOpts = Array("-disable-all-randomization", "-strip-debug-info")
)
)
}
```

This produces FIRRTL like:

```
FIRRTL version 3.1.0
circuit Foo :
module Foo :
input clock : Clock
input reset : UInt<1>
input addr : UInt<4>
output out : UInt<8>

wire a : UInt<8>[16]
invalidate a[0]
invalidate a[1]
invalidate a[2]
invalidate a[3]
invalidate a[4]
invalidate a[5]
invalidate a[6]
invalidate a[7]
invalidate a[8]
invalidate a[9]
invalidate a[10]
invalidate a[11]
invalidate a[12]
invalidate a[13]
invalidate a[14]
invalidate a[15]
connect a[0], UInt<1>(0h1)
connect out, a[addr]
```

Or HW Dialect like:
```mlir
hw.module @Foo(in %clock : !seq.clock, in %reset : i1, in %addr : i4, out out : i8) {
%0 = hw.aggregate_constant [0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 0 : i8, 1 : i8] : !hw.array<16xi8>
%1 = hw.array_get %0[%addr] : !hw.array<16xi8>, i4
hw.output %1 : i8
}
```

And Verilog like:

```verilog
// Generated by CIRCT firtool-1.56.1-82-g3eecf95e0
module Foo(
input clock,
reset,
input [3:0] addr,
output [7:0] out
);

wire [15:0][7:0] _GEN =
{8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h0,
8'h1};
assign out = _GEN[addr];
endmodule
```

This is obviously more compact to emit as:

```verilog
module Foo(
input clock,
reset,
input [3:0] addr,
output [7:0] out
);
assign out = addr == 0;
endmodule
```

The question then becomes under what circumstances is it appropriate to make this optimization? Clearly for the hyperbolic case of a single `1` and everything else as `0` it would be better. However, what about if this is differently sparse? E.g., it has long runs of the same value?

Investigate improvements along this line of thinking or provide evidence that this isn't necessary given what backend tooling does.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the Scala reproducer in the issue and run `scala-cli Foo.scala -- 4` and `-- 8`, then compare its FIRRTL, HW dialect, and Verilog output. The issue names no implementation files or tests; done would require a justified cost-based conversion policy with coverage for sparse and repeated-value cases, or evidence that backend tools already handle them adequately.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, scala
Domain
compilers, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.