llvm / llvm/circt

[FIRRTL/IMCP] Suboptimal results with invalid states

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

Description

```mlir
firrtl.circuit "Example" {
firrtl.module private @Test(in %in1: !firrtl.uint<1>, in %in2: !firrtl.uint<1>, in %clock: !firrtl.clock, out %out: !firrtl.uint<1>) {
%r = firrtl.reg %clock : !firrtl.uint<1>
%0 = firrtl.or %in1, %r : (!firrtl.uint<1>, !firrtl.uint<1>) -> !firrtl.uint<1>
firrtl.strictconnect %out, %0 : !firrtl.uint<1>
firrtl.strictconnect %r, %in2 : !firrtl.uint<1>
}
firrtl.module @Example(in %clock: !firrtl.clock, out %s: !firrtl.uint<1>) {
%c1_ui1 = firrtl.constant 1 : !firrtl.uint<1>
%c0_ui1 = firrtl.constant 0 : !firrtl.uint<1>
%test_in1, %test_in2, %test_clock, %test_out = firrtl.instance test @Test(in in1: !firrtl.uint<1>, in in2: !firrtl.uint<1>, in clock: !firrtl.clock, out out: !firrtl.uint<1>)
firrtl.strictconnect %test_clock, %clock : !firrtl.clock
firrtl.strictconnect %test_in1, %c0_ui1 : !firrtl.uint<1>
firrtl.strictconnect %test_in2, %c1_ui1 : !firrtl.uint<1>
firrtl.strictconnect %s, %test_out : !firrtl.uint<1>
}
}
```

The current result of `-firrtl-imconstprop`:
```mlir
firrtl.circuit "Example" {
firrtl.module private @Test(in %in1: !firrtl.uint<1>, in %in2: !firrtl.uint<1>, in %clock: !firrtl.clock, out %out: !firrtl.uint<1>) {
%c1_ui1 = firrtl.constant 1 : !firrtl.uint<1>
firrtl.strictconnect %out, %c1_ui1 : !firrtl.uint<1>
}
firrtl.module @Example(in %clock: !firrtl.clock, out %s: !firrtl.uint<1>) {
%c1_ui1 = firrtl.constant 1 : !firrtl.uint<1>
%c0_ui1 = firrtl.constant 0 : !firrtl.uint<1>
%test_in1, %test_in2, %test_clock, %test_out = firrtl.instance test @Test(in in1: !firrtl.uint<1>, in in2: !firrtl.uint<1>, in clock: !firrtl.clock, out out: !firrtl.uint<1>)
firrtl.strictconnect %test_clock, %clock : !firrtl.clock
firrtl.strictconnect %test_in1, %c0_ui1 : !firrtl.uint<1>
firrtl.strictconnect %test_in2, %c1_ui1 : !firrtl.uint<1>
firrtl.strictconnect %s, %test_out : !firrtl.uint<1>
}
}
```

`%test_out` must be replaced by 1 but currently not. This is because `%out` is marked as overdefined in IMCP. More specifically the lattice value of `%out` changes from 0 to 1 (and it causes unification failure).
1. In the first visit of `%0 = firrtl.or %in1, %r`, the lattice states are `{%r: invalid, %in1: 0, %in2: 0}` and `or(invalid, 0)` is folded into `0`. Therefore the state of `%0` becomes 0.
2. However, after visiting `firrtl.strictconnect %r, %in2 : !firrtl.uint<1>`, the value of `r` becomes 1.
At this point, the lattice states are `{%r: 1, %in1: 0, %in2: 0, %0: 0}`.
3. Since the value of `r` is changed, we visit `%0` again. At this time, `firrtl.or(%r, %in1) = firrtl.or(1, 0)` so we get `1` as a folded result. So lattice value of `%0` becomes overdefined

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the -firrtl-imconstprop pass and the provided FIRRTL example, focusing on how invalid register values are folded and how lattice updates are handled. Reproduce the result and trace the transition from invalid to 1; done means %test_out is replaced by 1 without the value becoming overdefined or causing unification failure.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.