New external keyword to pass cells "by reference"

[rachitnigam]

We have a standard use case for passing memories "by reference" where instead of instantiating a memory inside a component, we inline a memory interface into the component interface and the calling component is responsible for correctly hooking up the signals to a memory.

For example, here is a component that takes a register "by reference" and increments the value in it:

component increment_reg(r0_done: 1, r0_out: 32) -> (r0_write_en: 1, r0_in: 32) {
  cells {
    a = std_add(32);
  }
  wires {
    group incr_reg {
      a.left = r0_out;
      a.right = 32'd1;
      r0_in = a.out;
      r0_write_en = 1'd1;
      incr_reg[done] = r0_done
    }
  }
  control {
    incr_reg;
  }
}

Note how the interface for some register r0 has been completely inlined into the interface of the component here. In fact, this is exactly what the externalize pass does. However, in addition to being a tedious way to connect hardware modules (which is something we can usually ignore in an IL), there is an important design problem: Inlining interfaces removes any semantic relationship between ports. For example, usually, we can infer that the group incr_reg takes one cycle if it is updating a register directly. However, in this case, we have no way to knowing this piece of information since the ports r0_done and r0_write_en could be arbitrary ports on different components.

This proposal elevates the @external attribute to a keyword and gives it specific semantics that enables components to pass subcomponents in a semantically meaningful way. Additionally, the proposal is backwards compatible; we provide a way to compile external cells to normal Calyx programs which enables the existing infrastructure to work properly.

The external Keyword

The semantics of @external attribute specify that the compiler will either inline the interface of the cell into the component (using the externalize pass) or, for simulation code, generate $readmemh commands to read and write initial and final states of the memory. For the default compilation flow, adding @external attributes to non-main components generates incorrect code (#987).

In this proposal, we elevate external to a keyword for cells:

component foo() -> () {
  cells {
    r = std_reg(32); // a normal cell
    external m = std_reg(32); // an external cell
  }
  wires {
    // Use `m` like any other cell in the body
    group upd_m {
      m.in = 32'd10;
      m.write_en = 1'd1;
      upd_m[done] = m.done;
    }
  }
  control {
    upd_m;
  }
}

Cells defined as external are used normally like other cells in the component: their ports and attributes can be used in the same way as a normal cell. This immediately fixes the problem of semantic alignment of ports.

invoke statements syntax is extended to allow them to pass in external cells:

component main() -> () {
  cells {
    f = foo();
    k1 = std_reg(32);
    k2 = std_reg(32);
  }
  wires {}
  control {
    invoke f[m = k1]()(); // pass in `k1` as the external cell `m`.
    invoke f[m = k2]()(); // different invokes can take different cells for the same parameter.
  }
}

Compiling external

The external keyword can be compiled to normal Calyx programs with the following semantics that keep it backwards compatible:

1. In non-main components, the interfaces of external cells gets inlined into the component.
2. invoke statements that pass in external cells get compiled to explicitly pass in the cells using wire assignments
3. In main components, external cells get a new attribute called @interface which has the same semantics as the current @external attribute. Specifically:

• During simulation compilation, the code generator generates $readmemh commands
• During synthesis compilation, the code generate inlines in the interface of the cell so that they can be connected to AXI interfaces.
• Alternate: An alternate design decision is to disallow external keyword in the main component entirely.

Changes to IR

• The ir::Cell data structure will get a new boolean field for external which will be set to true when the parser parses a cell with the external keyword.
• The ir::Invoke data structure will get a map called external_cells: Vec<Id, RRC<ir::Cell>> which will contain the mapping for the external cells.

Changes to validate

The validate pass needs to be changed to make sure that only cells that are actually marked external in each component are passed into corresponding invoke statements for instances of the component as well as make sure that the invoke statements pass in cells with the expected primitives, i.e., if a cell is an external std_reg(32), then the invoke passes a std_reg(32).

Inlining Interfaces

For the first step of the compilation, where non-main components need to inline the interfaces of external cells, we can simply use the code from the externalize pass directly. We would have to change the behavior of the pass to insert @interface attributes for external cells in main.

Compiling invoke

The pass should compile invoke statements that look like this:

invoke f[m = k1]()();

into:

invoke f[](m_done = k1.done, m_out = k1.out)(m_in = k1.in, m_write_en = k1.write_en);

At the end of the pass, no invoke statement should have external cells being passed into it.

In the modified version of the externalize pass, we will inline each external cell's interface into the component's signature. Next, the pass should go over each invoke statement and generate additional input and output assignments corresponding to the cell's interface. For example, in the above case, we would generate the inputs:

m_done = k1.done, m_out = k1.out

and outputs:

m_in = k1.in, m_write_en = k1.write_en

Finally, the pass should clear the invoke data structure's external_cells field.

Effect on Other Passes

• Certain passes probably assume that invoke statement mention all the cells they use in the inputs and outputs. For example, the LiveRangeAnalysis and ReadWriteSet probably need to be updated to work with the new invoke representation.
• The DeadCellRemoval pass needs to treat external cells the same way it treats @external cells and make sure they cannot be eliminated.
• The ComponentInliner can potentially be updated to directly inline the new invoke representation which will avoid generating extra continuous assignments.

Effect on Cider

Since the change is backwards compatible, the interpreter can continue working with programs generated after the externalize pass. @EclecticGriffin can help us outline the changes needed to make the interpreter work with external cells directly.

[sampsyo]

This is super awesome!! This seems like a very juicy advancement that will make Calyx quite a bit more expressive. It is nice that this can be "compiled away" into the design pattern that we describe in this part of the docs. The design seems great. The only bikesheddy low-level alternative I could imagine would be making the declarations look more like the invoke syntax, like:

component foo[m = std_reg(32)]() -> () { ... }

…but that has the obvious downside of making the external components look less like the internal ones, so I think we should reject it.

Two other very low-level thoughts:

• Hopefully this simplifies the NTT frontend, which IIRC makes frequent use of this "inside-out" by-reference pattern.
• This introduces the possibility for "component aliasing." That is, two different external cells in a component might actually be the same underlying component. Internal cells, needless to say, still cannot alias.

[rachitnigam]

Yeah, the aliasing problem is a little troublesome and I'd like for that to not be allowed. We could place the syntactic restriction that the same cell may not be mentioned twice in an invoke statement. Long-term, this should be handled by some sort of affine type system.

[cgyurgyik]

Hopefully this simplifies the NTT frontend, which IIRC makes frequent use of this "inside-out" by-reference pattern.

I think that's the case for TVM, not NTT. It would be nice to have some way to enforce read/write-only memories, i.e., only hook in a subset of wires.

invoke f[](m_done = k1.done, m_out = k1.out)(m_in = k1.in, m_write_en = k1.write_en);

Couldn't this potentially lead to name duplication, since nothing stops a user from having a wire named m_done?

[rachitnigam]

Couldn't this potentially lead to name duplication, since nothing stops a user from having a wire named m_done?

We can use the name generator to ensure that we generate unique names for ports of external cells.

It would be nice to have some way to enforce read/write-only memories, i.e., only hook in a subset of wires.

There seem to be two different proposals here:

1. Some language-level way to enforce read/write-only cells. We can do this using an attribute.
2. Eliminating unused wires. This already happens when things are inlined into a component. I think its harder to reason about changing interfaces for modules, especially if they may be externally visible.