Remove Output as Flip, add an "is output" bitmask to firrtl.module

[seldridge]

tl;dr: This is a proposal to add flow information to the type system via firrtl.source, firrtl.sink, and firrtl.duplex. This is a follow-up to removing type canonicalization in #944. As an example, FIRRTL Dialect would now look something like:

// Inputs are now `firrtl.source`.
// Outputs are now `firrtl.sink`.
firrtl.module @Foo (%a: !firrtl.source<uint<1>>, %b: !firrtl.sink<uint<1>>) {
  // A connect can then be trivially verified with two checks on flow and one check on type:
  //   1) LHS flow must be sink or duplex
  //   2) RHS flow must be source or duplex (or a sink port/instance)
  //   3) The type inside the flow must match exactly
  firrtl.connect %b, %a : !firrtl.sink<uint<1>>, !firrtl.source<uint<1>>
  // Wires and registers get a special `firrtl.duplex` type.
  %c = firrtl.wire : !firrtl.duplex<bundle<a: uint<1>, b: flip<uint<1>>>>
}

Types are then propagated across operations:

1. Subfield of source/sink will become sink/source if the field is a flip
2. Subfield of duplex is duplex
3. All other operations just propagate

This is in contrast to how the equivalent would look now:

// Inputs are unflipped.
// Outputs are flipped.
firrtl.module @Foo (%a: !firrtl.uint<1>, %b: !firrtl.flip<uint<1>>) {
  // Connect verification depends on computing flow.
  firrtl.connect %b, %a : !firrtl.flip<uint<1>>, !firrtl.uint<1>
  // Wires and registers are not identified later.
  // Connection semantics in lowering requires computing flow.
  %c = firrtl.wire : !firrtl.bundle<a: uint<1>, b: flip<uint<1>>>
}

This can either be implemented as an actual type or as a couple of bits that encode this for FIRRTL types. The latter option can still serialize/deserialize to the above, verbose format.

Long Form Description

With type canonicalization being removed from the FIRRTL Dialect (see: PR doing this #944 and motivating issue #919), there are some remaining weird things in the type system of the FIRRTL dialect.

First, output is represented as an outer flip.

After #944, there are only two places that a firrtl.flip type can actually show up: (1) on an output port and (2) inside a bundle. This is because a SubfieldOp will now strip flip information from a bundle field. E.g., for the wire above a subfield would look like and have type:

%c_b = firrtl.subfield(%c)("b") : (!firrtl.bundle<a: uint<1>, b: flip<uint<1>>>) -> !firrtl.uint<1>

If a value has type !firrtl.flip, it is thereby always an output.

While this is fine, without type canonicalization it would be better to not reuse !firrtl.flip to encode two different things.

Second, flow has to be recomputed whenever needed.

Duplex types have entirely different connection semantics than source/sink. This is evidenced by, even in code predating #944, our need for a bool firrtl::isDuplexValue(Value val) function. To compute this, you necessarily have to walk backwards to get to a declaration, keeping track of any flips in fields you see. This is not ideal from a performance perspective. If we have a dedicated type (or bit) we can then get O(1) flow computation and O(1) flow verification.

Output Port/Instance Input Caveats

FIRRTL allows you to read from output ports and input instance ports. This is generally useful for writing monitors that tap ports where you don't want to figure out what is driving the port. We remove this when lowering to RTL dialect, but this is still present in FIRRTL dialect.

This is not covered by this proposal and we would need to do an extra check to see if a RHS sink is allowed to be used as such.

[lattner]

Why not just out output ports to firrtl.module? If I understand correctly, this would eliminate firrtl.flip type and make us much more consistent with SFC's modeling.

I don't understand the concern about recomputing flow. There aren't that many passes that will need it, and creating some datastructures during lowering is going to be much cheaper than encoding this into the type system.

[azidar]

I know this is unrelated, but why are outputs flip, rather than inputs? The original reason for having inputs be flip is it enables instances to be source flow. I don't see the added benefit of deviating from SFC, perhaps I'm missing something?

When considering connection semantics, it is important to separate the semantics into (1) connection legality, and (2) expand connection behavior. Duplex flow is only considered when computing whether a given connection is legal. It plays no role in determining how to expand a connection.

To that end, incorporating duplex flow into the type system is not particularly useful outside of a validation step, as its actually irrelevant to determining the actual expansion behavior. Secondly, source/sink flows of an expression are determined by their usage (combined with the expression's type). This means that just knowing the type is insufficient to actually determine an expression's flow.

[seldridge]

@azidar is right here. Flow isn't needed to compute connect lowering, only to validate connects. After validation, only types matter. (This was fixed in: 98ace4d)

Therefore, adding flow to the type system doesn't make sense due to its

@clattner wrote:

I don't understand the concern about recomputing flow. There aren't that many passes that will need it, and creating some datastructures during lowering is going to be much cheaper than encoding this into the type system.

Fair. This coupled with the fact that we don't need flow after verification makes this a non-starter. (It was my mistake that this was needed more places than just in verification.)

The question is then how to represent input and output. Each port needs this, so probably add this as an attribute array on modules and extmodules. What do people think about this?

This would then serialize to:

// Inputs are now `firrtl.input`. (This is sugar, not a type.)
// Outputs are now `firrtl.output`. (This is sugar, not a type.)
firrtl.module @Foo (%a: !firrtl.input<uint<1>>, %b: !firrtl.output<uint<1>>) {
  // Because the inputs/outputs are actually of types that never contain flips, 
  // connects then have the following types. This is super-consistent
  // with how the SFC does it.
  firrtl.connect %b, %a : !firrtl.uint<1>, !firrtl.uint<1>
  // Wires and registers get a special `firrtl.duplex` type.
  %c = firrtl.wire : !firrtl.bundle<a: uint<1>, b: flip<uint<1>>>
}

[lattner]

The question is then how to represent input and output. Each port needs this, so probably add this as an attribute array on modules and extmodules. What do people think about this?

The simplest thing to do is add a parallel array attribute to the portNames. a 1 is an output.

A fancier thing to do is use a single attribute which stores all of them in bits of a big integer.