New external keyword to pass cells "by reference"

[rachitnigam]

Discussed in #992

@paili0628 will be working this in four PRs:

1. Update the IR structures
2. Extend the parser and frontend data datastructures to parse new syntax
3. Update the well-formed pass to check that invoke statements correctly use external cells
4. Update the externalize pass to compile external cell and invoke syntax into standard syntax
5. Replace the @external attribute with @interface and disallow @interface annotation on non-toplevel modules (also fixes Disallow @external in subcomponents when generating verilog #987)

As a bonus, this addresses some of the semantic weirdness from #621.

^{Originally posted by rachitnigam April 29, 2022}
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.