[FSM] Tracking issue for canonicalization and optimization patterns
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 2.2k
- Forks
- 524
- Avg merge
- 3d 2h
- Merged PRs (30d)
- 46
Description
This issue intends to serve as a place to dump ideas for possible canonicalization and optimizations of FSMs. Feel free to add new examples as well as implement those listed.
Open questions:
* How do we best specify these rewrite patterns so they apply to as many FSM usecases as possible? e.g., ideally we'd like to be able to detect mutually exclusive states in an FSM regardless if we're using `comb` or `arith` operators.
## FSM canonicalizations
These patterns should capture canonicalizations that are agnostic about the internal operations used within the FSM regions.
### Unreachable states
Was attempted in #3131 but an as of yet unresolved non deterministic error has prevented it from getting merged. Help wanted :).
## HW optimizations
These patterns intends to apply to FSMs that have been generated as/lowered to HW-style FSMs. This implies that RTL dialect operations are used within the various regions, and it is these which we match on.
### Mutually exclusive transitions
In the following, it can statically be determined that if the transition to `@seq_1_while_if guard` was not taken, the transition to `@fsm_exit guard` will always be taken.
```mlir
fsm.state @seq_1_while_header output {
fsm.output
} transitions {
fsm.transition @seq_1_while_if guard {
fsm.return %lt_reg.out
}
fsm.transition @fsm_exit guard {
%true_0 = hw.constant true
%0 = comb.xor %lt_reg.out, %true_0 : i1
fsm.return %0
}
}
// rewrites to
fsm.state @seq_1_while_header output {
fsm.output
} transitions {
fsm.transition @seq_1_while_if guard {
fsm.return %lt_reg.out
}
fsm.transition @fsm_exit
}
```
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 by reading the attempted unreachable-state work in #3131 and the mutually exclusive transition example in this issue. Clarify which canonicalization or hardware optimization pattern is in scope, how it should apply across FSM forms, and what test or reproducible example will demonstrate completion.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100