[FSM] Tracking issue for canonicalization and optimization patterns

[mortbopet]

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.

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
}