Port-validity as a first class concept

[rachitnigam]

In pursuit of the next big set of features of Calyx (pipelining, combinational components), we should extend the IR with a notion of port validity.

Port validity: A port is considered "valid" if it allows a value to be read from it. For example:

group foo {
  reg.in = add.out // Invalid because add.left and add.right are not driven
  x.in = reg.out     // Valid because registers always output valid values on the out port
}

Calyx already supports valid ports as a second class concept:

if lt.out with cond { ... }

The lt.out with cond syntax really says that "after running cond, the lt.out port will have a valid value on it (except in this case, it has the added complication that cond might be combinational and it's not really "after running cond" but "while cond is running". More on this later.)

Proposed extensions

1. with-syntax for groups: The group syntax is extended to represented the set of ports that can be read after the group has finished executing:

group foo with (r1.out, sqrt.out) {
  r1.write_en = sqrt.done;
  r1.in = 32'd10;
  sqrt.in = 32'd16;
  sqrt.go = 1'd1; // sqrt.out will remain valid forever after this executes
  foo[done] = r1.done;
}

2. comb syntax for combinational groups: The group[done] = 1'd1 is a well known wart in the design of Calyx. What we really want in this case is a combinational group with some special properties (such as valid ports). With the extended syntax, we can say:

comb cond with (lt.out, add.out) {
  lt.left = 32'd1;
  lt.right = 32'd10;
  add.right = 32'd1;
  add.left = 32'd10;
}

Note that a comb group does not have a done condition because all connections are always active in a combinational path. This also means that comb groups cannot occur inside most control operators. Initially, the only valid position for comb groups would be as condition for if and while control operators.

With a notion of valid ports, comb groups can be compiled into "normal" groups:

group cond with (lt_reg.out, add_reg.out) {
  lt.left = 32'd1;
  lt.right = 32'd10;
  lt_reg.in = lt.out; // Save the specified valid port

  add.right = 32'd1;
  add.left = 32'd10;
  add_reg.in = add.out; // Save the specified valid port
  ....
  cond[done] = lt_reg.done & add_reg.out;
}

The conversion from comb to group preserves the values that would've appeared on the specified valid ports. In this case, the two ports lt.out and add.out have been saved in lt_reg and add_reg. Note that this conversion will always result in a group that takes exactly one cycle because all specified ports can be within one cycle since the group is combinational.

This extension gives frontends the flexibility to specify combinational circuitry, let passes optimize combinational conditions (which is not currently possible with either static-timing or compile-control), and allow the rest of Calyx pipeline to deal with a homogenous notion of groups.

The Future: Dataflow execution

The comb group representation along with valid ports will allow us to specify a new dataflow operator that only allows comb groups within itself and automatically inserts registers.
Such dataflow execution can be basis for the pipeline operator as well.

[cgyurgyik]

group cond with (lt_reg.out, add_reg.out) {
  lt.left = 32'd1;
  lt.right = 32'd10;
  lt_reg.write_en = 1'd1; lt_reg.in = lt.out;
  add.right = 32'd1;
  add.left = 32'd10;
  ....
}

I'm a bit lost here. Where did these registers come from? It went from a combinational group to a single-cycled group?

Also I imagine that the comb group will still have the group[done] = 1'd1?
Wouldn't that pose a problem for lowering sequential combinational groups that use the same cells?

comb g1 { ... }
comb g2 { ... }
seq { g1; g2; }

[rachitnigam]

Good questions. I've updated the text above to clarify. TLDR:

1. comb groups don't have a done condition because assignments within them are always active. In other words, for something to be done, its state needs to be made visible with registers (through a stateful path).
2. comb groups cannot appear in most control operators because of this fact. They can appear as conditions for if and while and in the future, within the dataflow operation.

[sampsyo]

Awesome!!! I think this is a great way to proceed.

Here are a couple of notes:

• Just to clarify, this discussion—despite the name—doesn't head-on address the questions about "undefinedness" discussed in Rigor-ifying the language semantics #551 (comment). That's relevant, but this is about a different/adjacent issue.
• I'm super duper enthusiastic about special comb groups, and the idea to have them just omit go/done altogether. That simplifies a lot relative to trying to somehow generalize a monolithic set of go/done rules to cover both sequential and combinational logic. The incorporation of valid output ports seems like a great way to give the concept of groups a set of "superpowers" that will turn them into useful building blocks for things like scheduling. I'm excited about this creating an abstraction level at which registers for data-path logic can be implicit, which seems like a big boon for Calyx emitters.
• Here is something I honestly don't know the answer to: Should combinational groups also have input ports to facilitate that scheduling/data-flow stuff? Maybe not; maybe that's more easily inferred. But maybe a data-flow scheduler would want to just look at input and output ports to do its work rather than inspecting the internal structure of each combinational group. Not sure about this.

And two questions:

• Would control programs be able to enable combinational groups, like the currently do normal groups? [I wrote this question before seeing @rachitnigam's comment above saying "no," so I'm glad we're on the same page—leaving it here just for posterity. 😃] I'm thinking "no for now," because there would be no way to get the data out of those output ports. Instead, in the first milestone, control would only be able to refer to these combinational groups for if and while conditions, where Calyx's current behavior is tbh somewhat confusing.
• What is the benefit of declaring valid ports on non-combinational groups explicitly? (Why not just read from whatever ports?) I see what role they play for combinational groups, but for "normal" groups it is less clear. Are non-combinational (normal) groups going to be involved in data-flow compilation too?