llvm / llvm/circt

[FSM] Tracking issue for canonicalization and optimization patterns

Open
#3,577 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

FSM help wanted
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

  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 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.