llvm / llvm/circt

[Comb] ShlOp canonicalization might lead to less optimal logic

Open
#6,569 1 comment 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

Comb [canonicalizes](https://github.com/llvm/circt/blob/ccdef1740c35216048a567081033f91cbc3a7ef8/lib/Dialect/Comb/CombFolds.cpp#L657-L658) `extract(lowBit, 1 << x) -> x == lowBit` but it could introduce a lot of comparisons which might be better not to apply:

```scala
//> using scala "2.13.10"
//> using lib "org.chipsalliance::chisel::6.0.0-RC1"
//> using plugin "org.chipsalliance:::chisel-plugin::6.0.0-RC1"
//> 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(width:Int, disable: Boolean) extends Module {
assert(width <= 31)
val depth = 1 << width
val sel = IO(Input(UInt(width.W)))
val out = IO(Output(Vec(depth.toInt, UInt(1.W))))
val shift = 1.asUInt(depth.W) << sel
if(disable)
dontTouch(shift)
for (i <- 0 until depth){
out(i) := shift(i)
}
}

object Main extends App {
println(
ChiselStage.emitSystemVerilog(
gen = new Foo(3, false),
firtoolOpts = Array("-disable-all-randomization", "-strip-debug-info")
)
)
println(
ChiselStage.emitSystemVerilog(
gen = new Foo(3, true),
firtoolOpts = Array("-disable-all-randomization", "-strip-debug-info")
)
)
}
```
w/ canonicalization:
```
// Generated by CIRCT firtool-1.62.0
module Foo(
input clock,
reset,
input [2:0] sel,
output out_0,
out_1,
out_2,
out_3,
out_4,
out_5,
out_6,
out_7
);

assign out_0 = sel == 3'h0;
assign out_1 = sel == 3'h1;
assign out_2 = sel == 3'h2;
assign out_3 = sel == 3'h3;
assign out_4 = sel == 3'h4;
assign out_5 = sel == 3'h5;
assign out_6 = sel == 3'h6;
assign out_7 = &sel;
endmodule
```

w/o canonicalization:
```
// Generated by CIRCT firtool-1.62.0
module Foo(
input clock,
reset,
input [2:0] sel,
output out_0,
out_1,
out_2,
out_3,
out_4,
out_5,
out_6,
out_7
);

wire [14:0] shift = 15'h1 << sel;
assign out_0 = shift[0];
assign out_1 = shift[1];
assign out_2 = shift[2];
assign out_3 = shift[3];
assign out_4 = shift[4];
assign out_5 = shift[5];
assign out_6 = shift[6];
assign out_7 = shift[7];
endmodule
```

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 lib/Dialect/Comb/CombFolds.cpp at the linked canonicalization around lines 657-658, then run the provided Scala reproducer with and without that canonicalization. Compare the generated SystemVerilog for the added comparisons and determine a canonicalization behavior that avoids the reported loss of optimization.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, scala
Domain
compilers, performance
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.