[FIRRTL][HW] Large, sparse SubAccess cost-driven conversion?
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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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