llvm / llvm/circt

[Comb][Synth] Failed to optimize redundant comparisons

Open
#8,924 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
2.2k
Forks
524
Avg merge
3d 2h
Merged PRs (30d)
46

Description

```sv
module Foo(input [2:0] c, output out);
assign out = c == 8'h1 | c == 8'h3 | c == 8'h5 | c == 8'h7 ;
endmodule
```
This is equivalent to `assign out = c[0]`.

```mlir
$ circt-verilog odd.sv | circt-synth
hw.module @Foo(in %c : i3, out out : i1) {
%0 = comb.extract %c from 2 : (i3) -> i1
%1 = comb.extract %c from 1 : (i3) -> i1
%2 = comb.extract %c from 0 : (i3) -> i1
%3 = comb.extract %c from 1 : (i3) -> i1
%4 = comb.extract %c from 2 : (i3) -> i1
%5 = aig.and_inv not %3, not %4 : i1
%6 = aig.and_inv %2, %5 : i1
%7 = aig.and_inv %1, not %0 : i1
%8 = aig.and_inv %2, %7 : i1
%9 = aig.and_inv not %1, %0 : i1
%10 = aig.and_inv %2, %9 : i1
%11 = aig.and_inv %1, %0 : i1
%12 = aig.and_inv %2, %11 : i1
%13 = aig.and_inv not %6, not %8 : i1
%14 = aig.and_inv not %10, not %12 : i1
%15 = aig.and_inv %13, %14 : i1
%16 = aig.and_inv not %15 : i1
hw.output %16 : i1
}
```

We could add comb level canonicalization but probably that's too heroic so would be nice to handle in synthesis side.
ABC's refactor pass works well for this IR so would be good to implement.
```mlir
$ circt-verilog odd.sv | circt-synth --abc-path=yosys-abc --abc-commands=refactor
module {
hw.module @Foo(in %c : i3, out out : i1) {
%0 = comb.extract %c from 0 : (i3) -> i1
hw.output %0 : i1
}
}
```

Contributor guide

No contributing guide indexed for this repository

Research direction

Reproduce the issue with circt-verilog odd.sv | circt-synth and compare it with circt-synth --abc-path=yosys-abc --abc-commands=refactor. Start by tracing the circt-synth ABC integration and its synthesis entry points. Done means redundant comparisons are reduced to the equivalent extracted bit, with regression coverage for this example.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.