[HW] Parameterized Modules, step #2: using expressions

[lattner]

As a follow on to Issue #1489 (step 1), we need to start building the "expression language" for parameters (e.g. "foo+42 * (bar&1)". Some basic requirements:

• Parameters need to be refer to the declarations set up in step 1: #1489.
• They need to be referrable from types (so we can have a bitvector whose width is "n").
• We also have to keep parameters and values separate: parameters are a metaprogramming system, and while it is ok for the value domain to use parameters, it isn't ok for parameters to depend on values.
• Parameters have a expanded/different type system (incl strings, etc) than comb logic does.

Because these have to be referenced from types, they must be attributes. I think we should add something like the following two attributes:

• hw.param.ref "someparam" : whatevertype: a reference to a named parameter in the current context. I think that referring to them by name is fine.
• hw.param.binop "add" lhs, rhs : whatevertype: we need a grammar of simple expression operators, we can learn from AffineExpr here.

We need to define what the operators are, but can start with some simple and obvious ones like add/sub/mul to get started. We would also use IntegerAttr in the expression grammar.

To start using these, we should:

1) take the recently added "sv.localparam" and change it (back, sorry my advice was bad in the PR review) to taking an attribute as an operand instead of taking an SSA value. This operator because a way of forming a named parameter within a context, projecting it from the parameter domain (attributes) into the SSA value domain.

2) add a new "hw.param" op which returns (e.g.) an integer SSA value and takes an attribute. It is the same as sv.localparam but is for the "anonymous" usecase, where you want to just reference "n" on the right side of a comb.add or whatever.

3) extend hw.instance to be able to specify parameters to parameterized modules, this is an attribute list.

We should then add ExportVerilog support for this whole stack.

Step #⁠3 will be to start setting up the parameterized type system.

[teqdruid]

I suspect we are barking up the wrong tree with Attributes rather than Values. Regardless of which we use, we'll have to come up with an expression language. SSA Value semantics provide that framework, which I think is why hw.param.binop et al are a good idea.

• We also have to keep parameters and values separate: parameters are a metaprogramming system, and while it is ok for the value domain to use parameters, it isn't ok for parameters to depend on values

Do you mean MLIR Value or a runtime value? If the latter, I absolutely agree. If the former, why? We could have two different Value type systems: the existing one for runtime values and a new one for parameters.

Because these have to be referenced from types, they must be attributes.

Why? When creating the HWModuleOp body IR, we don't know what the parameterized types are anyway. So we will have to create a generic type (that composes nicely with the existing hw/seq/comb ops) which depends on something which isn't known locally.

Further, one may not know the parameterized type at all (i.e. if the user wants to output an SV-parameterized module) or it may be necessary to climb up an arbitrary number of levels in the instance hierarchy to determine (if you want to specialize or validate the parameterized module). In the latter case, I strongly suspect using MLIR Values everywhere could make this analysis easier since we could use (what I assume to be) general inter-function/module dataflow analysis without having to teach it about Attributes.

---

Here's a rough sketch I wrote late last night of integer parameters:

hw.module @foo_parameterized params: (%b: !hw.param<i8>) ports: () {
  %c0_i8 = hw.constant 0 : i8
  hw.param.if (%b == %c0_i8) {
    ...
  }

  hw.param.for ({i in range(b)}) {
    ...
  }
}

hw.module @add1param params: (%e: !hw.param<i8>) ports: () {
  %c1 = hw.constant 1 : !hw.param<i8>
  %b = hw.params.add %e, %c1
  hw.instance @foo_parameterized (%b) "foo_plusone" ()
}

hw.module @top () {
  %c1 = hw.constant 1 : !hw.param<i8>
  hw.instance @add1param (%c1) "addOneParam" ()
}

And one of type parameterization:

hw.module @typeparam params: (%c: !hw.typeparam) ports: (%d: !hw.parameterized_type<"c">) -> (%x: !hw.parameterized_type<"c">) {
  hw.typeparam.if_dyn_cast %d as int %dAsI {
    %x2 = comb.add %dAsI, %dAsI : !hw.parameterized_type.int<"c">
    %r = hw.param.box %x2 : !hw.parameterized_type<"c">
    hw.output %r 
  }
  hw.typeparam.if_dyn_cast %d as array %dAsA {
    ...
  }
}

The param expression language operators and overall syntax are irrelevant since we agree that they're inevitable. The point is that I think they can operate on Values -- even for types.

---

WDYT?

[teqdruid]

Alternatively, we could do this in a more functional style: create a compile-time function which returns a module. (Kinda like a generator.) This approach fits better with my mental model of different compilation steps, but it is probably crazy.

[teqdruid]

I think @stephenneuendorffer summed up my Value-based proposal rather eloquently earlier: "why invent another way to define an IR?" (paraphrased).

Following today's discussion, here's -- from what I understood by the end of the meeting -- the crux of why a Value-based proposal isn't ideal:

hw.module @a params: (%width: !hw.param<i8>) ports: () {
  %widthPlusOne = hw.params.add %width, 1
  %widthPlusOneMinusOne hw.params.add %widthPlusOne, -1
  hw.params.definetype "width", %width
  hw.params.definetype "widthPlusOneMinusOne", %widthPlusOneMinusOne
  %c1 = hw.const 1 : !hw.params.typeparam<"width">
  %c2 = hw.const 2 : !hw.params.typeparam<"widthPlusOneMinusOne">
  %three = comb.add %c1, %c2
}

The comb.add verifier needs to ensure that %c1 and %c2 are integers of the same width. The Types of them, however, don't trivially match (pointer-based) so the SSA would have to be evaluated in order to determine the actual type -- which is expensive. (And not possible in the verifier...?)

If we use an attribute-based expression language, however, it is possible to compute the types at/before verification time.... in this case.

There exist, however, cases wherein type equality cannot by resolved locally at all:

hw.module @b params: (width1: #hw.typeparam, width2: #hw.typeparam)
             ports:  (%a: !hw.parameterized_type<width1>, %b: !hw.parameterized_type<width2>) {
  comb.add %a, %b: ?
}

How would the comb.add verifier do type checking here? I don't think it could. The verifier needs contextual information to do the comparison -- which could be different for each instance of the module.

If I'm correct about that, it follows that we'd have to deal with cases wherein verifiers cannot participate in type checking at construction time. Rather, a post-construction instance-hierarchy-traversal (which tracks the contextual parameter values) would be required to verify the types. (This assumes that the parameter values are known to the compiler, which they won't be if one wants to output a parameterized verilog module.) An instance-hierarchy-traversal verification pass is actually worse than the 2 pass IR construction which @stephenneuendorffer was speaking about earlier today, so please someone (@lattner) tell me I'm way off-base and why.

So if we end up in a situation where we just have to accept that the verifiers (in certain cases which could be quite common) cannot check types, why not use my Value based scheme?

[lattner]

This is technically in place now, but still lacks an expression grammar. I'll take care of that in the next couple days as I have time. Step #3+ will be support for parametric types will will be several balls of wax.

[teqdruid]

Any response to my comment above? How are we going to deal with the situation wherein we can't compute the resolved types locally?

[lattner]

That was just intended as a status update.

How about we talk about it on wednesday. In short, you're correct that we need to solve this problem, but that doesn't happen by breaking type identity. Getting the expression grammar and its canonicalization "right" is the critical piece to this, as well as providing a "asserting cast" escape hatch to handle the otherwise unsolvable problem you're pointing out.

[lattner]

Simple +/* expressions are now supported. I'll file steps #3 and #4.