Explicitly Instantiate Multiplexers During Lowering

[rachitnigam]

Currently, the backend is in-charge of collecting all assignments to a port and generating an equivalent state in Verilog.
For example:

a.in = g1 ? b;
a.in = g2 ? c;
a.in = g3 ? d;

Gets converted into a mux:

a.in = g1 ? b : g2 ? c : g3 ? d : '0;

The goal of this proposal is to represent this process within Calyx itself using a new multi-ported std_mux primitive. The simplest benefit of doing this would be reducing the surface area of the backend even more and enabling us to experiment with different mux implementations, specifically, ones that do not implement priority logic like the one above.

Implementation

The std_mux primitive takes as its inputs:

• n data inputs
• An n-bit select signal
• A default value (this will enable supporting Annotations for Data Path Components #1169 in the future)

It produces a single output.

Since the primitive is multi-ported, i.e., the number of input ports depends on a parameter, this primitive cannot directly be represented in Calyx. We'd need to use some code generation to produce wrappers for muxes actually generated during compilation. The dumb solution is just writing down muxes with upto to 22 inputs or something

Lowering Pass

A final lowering pass would convert all the assignments in a program into direct assignments into std_mux. We'd change the verilog backend to no longer generate any muxes.

[sampsyo]

Super fun idea. I like the idea of bringing this stuff slightly more "in house."

One thing I don't have any good thoughts on: what are the relative merits of using std_mux vs. chains of conditional assignments? If std_mux exists, would anyone (frontends, optimizations, etc.) prefer to just use that instead of conditional assignments? Or are conditional assignments still the right thing for most cases, and std_mux is mostly useful as a lower-level thing?

[rachitnigam]

what are the relative merits of using std_mux vs. chains of conditional assignments?

Well, the big one is that that Calyx knows how to merge guarded assignments across groups. If you just use muxes directly, we'll consider them to be continuous assignments and warn that there are conflicts. More broadly, it allows us to reason about assignments directly since guards are transparent where std_mux is just a primitive

[sampsyo]

That sounds pretty legit. Makes me wonder about an alternate universe where guarded assignments are more "mux-like," but that is a step too far for this very realistic proposal.

[rachitnigam]

This is subsumed in some ways by #1423 since generating non-priority logic requires generating structural verilog that performs a similar task as explicit mux instantiation