[Tracker] Lowering high-level Calyx programs

[rachitnigam]

Lowering Calyx without having to rely on the native compiler seems to be one of the top requirements for folks wanting to use Calyx within CIRCT. This tracks the main compiler passes that need to be implemented to accomplish it.

Calyx has two abstractions that need to be encoded structurally: groups and control operators. The main compilation passes first remove control operators by generating new groups and then removes groups by inlining uses of their go and done signals.

• [ ] CompileControl: Removes control operators by encoding them into new groups which implement structural FSMs.
  • Current implementation uses the old, recursive compile control pass presented in the Calyx paper. It should be changed to use the new TopDownCompileControl algorithm which instantiates the entire control FSM in one go. The implementation also only supports lowering seq statements.
• [ ] GoInsertion: Guards assignments within a group with a go signal that ensures assignments only execute when the group is activated using the FSM.
  • The current implementation looks correct. We can mark this off once someone tests it.
• [ ] Inliner: This pass can be implemented using a simpler, wire-based inliner. Before implementing, ping @rachitnigam to see if this simpler pass has been implemented in the native compiler.
  • The RemoveGroups pass seems to implement a subset of the required transformation. However, it doesn't seem to handle inlining the reads from groups' go and done signals.

At the end of these passes, the Calyx program is purely-structural, i.e. it can be easily translated into hw programs.

[rachitnigam]

CC @mikeurbach since you mentioned you are interested in seeing this get done.

[cgyurgyik]

Current prototypes for these found in lib/Dialect/Calyx/Transforms. These are (likely) neither correct nor complete, and probably have suffered some bit rot.

[mikeurbach]

Thanks for opening this, I am interested in helping here.

One thing I've experimented with before was the use of the CIRCT FSM dialect as a lowering target for Calyx. I wonder if such an IR could help simplify these transforms, especially compile control. For starters, it's probably best to follow the original implementations and just massage the IR into a structural form, since that is a well-understood path by now.

It seems @cgyurgyik already has a good start on the three main lowering phases, so perhaps we can refine the task list a bit? For example, we already have one implementation of compile control, but I believe the preferred algorithm is not the one Chris originally implemented, so one task might be to update that and see if there is an improvement. Any other pieces that are incorrect or incomplete? There is also the work to go from structural Calyx to CIRCT's structural IRs, which is currently just a placeholder.

As I have time to pick up tasks here and there, I will chime in on this thread.

[rachitnigam]

I've updated the task list using the current state of the implementation. To start off with, the compile control implementation does indeed use the old, inside-out compilation algorithm that instantiates on FSM for each control operator. The native compiler has switched to using a different pass which compiles the FSM in one shot. Additionally, the current pass only supports compiling seq operators.

[mortbopet]

Just to update: I've been pushing on an alternative path to CompileControl, a path going through the FSM dialect (14ca56c139412084fefe62491149f82d77b9b47d, e04b7b6bede7629ef9b067782645d1419263a3bc). Work on this is almost finished (last part is #3601) whereafter control schedule lowering could be considered done.

[rachitnigam]

Awesome! Looking forward to the PR!