Future directions for Calyx FSMs

[parthsarkar17]

In the past week, @CynyuS and I have had a few interesting ideas about the compiler IR for FSMs, and I wanted to take a moment to keep a running tally of potential future directions.

Current IR is Too Expressive

Based off a conversation I had with @sampsyo a while ago, I think an interesting observation about our FSM work is how the seemingly simple understanding of a hardware FSM (i.e. every state has a set of assignments and transitions) is expressive enough to capture all of Calyx's language semantics. We have shown this through a new pass pipeline that can compile every Calyx design solely using these FSMs, all the way down to Verilog.

However, I think there is room for improvement, in that the current compiler representation for FSMs is 1) too broad, and 2) perhaps as a consequence of point 1, does not present as strong of an interface as possible. Here is an example:

Example

This week, Cynthia and I met to work on the problem of the one-cycle handshake between dynamic while wrappers and their static bodies, implemented with the new ir::FSM constructs. Immediately, we ran into the problem that it was difficult to even identify cases of while-with-static-island-bodies. Because there is no outward distinction between FSMs implementing a static vs. dynamic schedule, we are forced to reach inside the FSM and derive kind-of messy distinguishing features (e.g. the absence of explicit start and done states in static island schedules) to make our implementation work. Now, coupled with the fact that users can define and compile their own FSMs, there are even more such distinguishing features to look out for.

This might just be an issue of code quality, in that it will always be possible to extract the info we're looking for. But, from the perspective of future students that work on this code, it would be awesome to neatly capture the code transformations we make in the IR constructs we use. For example, each of the following IRs would have different interfaces, which would make our transformations tidier and more specific.

• Dynamic FSM
  • exposes start / done
• Static Island FSM
  • exposes start / done, with guarantee of completing in n cycles
• Purely Static FSM
  • exposes start; guarantee of completing in n cycles

This separation would also be supremely helpful in FSM inlining.

Compiling User-Defined FSMs

As a result of @CynyuS's awesome work with parsing the new language construct, we must now also consider the possibility that FSMs that appear in the control of a design are user-defined. Unfortunately, the current -p fsm-opt pipeline throws a panic when we use this pipeline with user-defined FSMs. Even if we skip all of the analyses from which this panic arises, I have doubts that these FSMs can be correctly compiled because, again, the passes that I worked on earlier assume that all FSMs in the control section are compiler-generated with a very specific structure.

Here's a possibility: instead of modifying the existing fsm-opt pipeline to not panic, we create a very minimal set of passes that can correctly compile both user-defined FSMs and provide compiler-generated FSMs for existing Calyx control nodes. In my mind, this minimal pipeline would use the FSM separation I defined above. Using this mini-compiler as a proof-of-concept, we could introduce small optimizations (i.e. static FSM inlining) and benchmark our results, thereby proving the effectiveness of this IR. AFAIK, this would make a cool paper.

As always, open to discussion! I understand this final thought is quite an overhaul, but I'm hoping we can 1) repurpose existing analyses and 2) use what we learned in compiling schedules using FSMs to reduce the burden.

Thanks!