Support linking multiple MLIR files in firtool

[unlsycn]

We propose a mechanism for linking multiple MLIR files in firtool. Specifically, this involves combining multiple circuits into a single one.

All modules instantiated within another module (i.e., all firrtl.instance operations) must have corresponding declarations in the same circuit, which can be either a firrtl.module or a firrtl.extmodule serving as an interface. Notably, a module can have both an interface (as an extmodule) and an implementation (as a module) within the same circuit.

The linking process works as follows: First, we verify that each instance has a corresponding declaration. Then, all circuits are concatenated into one. Finally, we iterate through all extmodules to find matching public module implementations, replacing them when possible and any remaining extmodules are treated as blackboxes.

For example, there are two .mlir files:

GCD.mlir

module {
  firrtl.circuit "GCD" {
    firrtl.module @GCD(out %output: !firrtl.bundle<valid: uint<1>, bits: bundle<z: uint<32>>>, in %input: !firrtl.bundle<valid: uint<1>, ready flip: uint<1>, bits: bundle<x: uint<32>, y: uint<32>>>, in %reset: !firrtl.uint<1>, in %clock: !firrtl.clock) attributes {convention = #firrtl<convention scalarized>} {
      ...
      %sub = firrtl.instance sub1 interesting_name @Subtractor(in a: !firrtl.uint<32>, in b: !firrtl.uint<32>, out z: !firrtl.uint<32>)
      ...
    }
    firrtl.extmodule @Subtractor(in a: !firrtl.uint<32>, in b: !firrtl.uint<32>, out z: !firrtl.uint<32>) attributes {defname = "Subtractor"}
  }
}

Subtractor.mlir

module {
  firrtl.circuit "Subtractor" {
    firrtl.module @Subtractor(in %a: !firrtl.uint<32>, in %b: !firrtl.uint<32>, out %z: !firrtl.uint<32>) attributes {convention = #firrtl<convention scalarized>} {
      ...
    }
  }
}

We can pass them to firtool together by

firtool GCD.mlir Subtractir.mlir

and produce a complete circuit:

module {
  firrtl.circuit "GCD"
    firrtl.module @GCD(out %output: !firrtl.bundle<valid: uint<1>, bits: bundle<z: uint<32>>>, in %input: !firrtl.bundle<valid: uint<1>, ready flip: uint<1>, bits: bundle<x: uint<32>, y: uint<32>>>, in %reset: !firrtl.uint<1>, in %clock: !firrtl.clock) attributes {convention = #firrtl<convention scalarized>} {
      ...
      %sub = firrtl.instance sub1 interesting_name @Subtractor(in a: !firrtl.uint<32>, in b: !firrtl.uint<32>, out z: !firrtl.uint<32>)
      ...
    }
    firrtl.module @Subtractor(in %a: !firrtl.uint<32>, in %b: !firrtl.uint<32>, out %z: !firrtl.uint<32>) attributes {convention = #firrtl<convention scalarized>} {
      ...
    }
  }
}

[seldridge]

There's a couple of other things that need to be considered here:

1. Mangling of private modules (private symbols). If the two circuits both have a module Queue, then these should be renamed, ideally deterministically (though I would not mandate this). The simple thing to do here is to use the circuit name as a prefix.
2. Layer-colored probes need to work. There are complicated ways to do this, but the simplest is to require have the layers of layer-colored probe ports on external modules use the exact same layers that are used in the circuit.

[sequencer]

Mangling of private modules (private symbols). If the two circuits both have a module Queue, then these should be renamed, ideally deterministically (though I would not mandate this). The simple thing to do here is to use the circuit name as a prefix.

I personally suggest just prefix the original circuit name to the private module Queue. However this also means we need to find all usage of Queue in the local circuit.

Layer-colored probes need to work. There are complicated ways to do this, but the simplest is to require have the layers of layer-colored probe ports on external modules use the exact same layers that are used in the circuit.

I strongly suggest the simplest way, the fundamental issue here is that, layers are also a interface to a module, we should check it at link time.

[sequencer]

At the first pass of linking(I'm not sure if it is a Pass) is mangling:
Mangling the name of all private module in all circuits and update the reference in to local circuit. We need to be careful to a possible malformed case that the mangling name of private module being conflict with other modules in other circuit if only prefix circuit name: e.g. Circuit A {Private Module AB} is conflict with Circuit AA {Private Module B} or Circuit C {Module AB}. So essentially, prefixing circuit name and suffix with the hashing of entire private module op is an ideal solution. However I suggest the mangling strategy(adding suffix or prefix) is also optional, since in our designs, we suffix the parameter hash for all modules in the generator, which actually is mangling in the DSL side.
This pass add two cmdline opt: --linking-prefix-circuit-name --linking-suffix-module-hash.

After resolving the mangling issue, other modules in different circuits from multiple mlirbc files should be moved("move" here is for saving memory) into the "base circuit": extmodule has two paths: 1. if public module with same name is found in other circuits, test the interface to be same, if true, delete the current extmodule and not moving it, otherwise throw an "interface not match exception", 2. if no public module are found for interface, just move the extmodule to the base circuit.
For all other modules, duplication should be checked for each movement, if existing a duplicate module, throw a "multiple definition exception".
So there are one additional command line --linking-base-circuit to indicate the base circuit to let other modules move in.

@unlsycn @seldridge wdty.

[unlsycn]

At the first pass of linking(I'm not sure if it is a Pass) is mangling: Mangling the name of all private module in all circuits and update the reference in to local circuit. We need to be careful to a possible malformed case that the mangling name of private module being conflict with other modules in other circuit if only prefix circuit name: e.g. Circuit A {Private Module AB} is conflict with Circuit AA {Private Module B} or Circuit C {Module AB}. So essentially, prefixing circuit name and suffix with the hashing of entire private module op is an ideal solution. However I suggest the mangling strategy(adding suffix or prefix) is also optional, since in our designs, we suffix the parameter hash for all modules in the generator, which actually is mangling in the DSL side. This pass add two cmdline opt: --linking-prefix-circuit-name --linking-suffix-module-hash.

After resolving the mangling issue, other modules in different circuits from multiple mlirbc files should be moved("move" here is for saving memory) into the "base circuit": extmodule has two paths: 1. if public module with same name is found in other circuits, test the interface to be same, if true, delete the current extmodule and not moving it, otherwise throw an "interface not match exception", 2. if no public module are found for interface, just move the extmodule to the base circuit. For all other modules, duplication should be checked for each movement, if existing a duplicate module, throw a "multiple definition exception". So there are one additional command line --linking-base-circuit to indicate the base circuit to let other modules move in.

@unlsycn @seldridge wdty.

Options like --linking-suffix-module-hash should not be exposed to users, since this would actually require users to determine if their input falls into the corner case while this case is impossible to construct with current Chisel or Zaozi. I prefer to add a --no-mangle option and use the circuit name as a prefix when this option isn't enabled by default. For situations where we can guarantee all symbols are unique (such as with Zaozi), we can pass this option to firtool to keep the module names readable after linking.

[unlsycn]

At the first pass of linking(I'm not sure if it is a Pass) is mangling: Mangling the name of all private module in all circuits and update the reference in to local circuit. We need to be careful to a possible malformed case that the mangling name of private module being conflict with other modules in other circuit if only prefix circuit name: e.g. Circuit A {Private Module AB} is conflict with Circuit AA {Private Module B} or Circuit C {Module AB}. So essentially, prefixing circuit name and suffix with the hashing of entire private module op is an ideal solution. However I suggest the mangling strategy(adding suffix or prefix) is also optional, since in our designs, we suffix the parameter hash for all modules in the generator, which actually is mangling in the DSL side. This pass add two cmdline opt: --linking-prefix-circuit-name --linking-suffix-module-hash.

After resolving the mangling issue, other modules in different circuits from multiple mlirbc files should be moved("move" here is for saving memory) into the "base circuit": extmodule has two paths: 1. if public module with same name is found in other circuits, test the interface to be same, if true, delete the current extmodule and not moving it, otherwise throw an "interface not match exception", 2. if no public module are found for interface, just move the extmodule to the base circuit. For all other modules, duplication should be checked for each movement, if existing a duplicate module, throw a "multiple definition exception". So there are one additional command line --linking-base-circuit to indicate the base circuit to let other modules move in.

@unlsycn @seldridge wdty.

There is a slight difference between "moving modules to the base circuit" and "simply merging circuits". Consider this case: a circuit whose modules are never referenced by the base circuit may contain illegal operations (e.g., an instance that doesn't match its declaration) that would not be checked. A more intuitive way to link circuits could be to simply concatenate them. By "concatenate", we mean iterating through all circuits and moving all operations (extmodules and modules) into a new circuit, which doesn't require an "entry" module to search all modules (though we still need to specify a base circuit to preserve its circuit name).

[unlsycn]

2. Layer-colored probes need to work. There are complicated ways to do this, but the simplest is to require have the layers of layer-colored probe ports on external modules use the exact same layers that are used in the circuit.

There are two requirements to verify:

1. An instance must have exactly matching layers compared to its declaration. This verification is already implemented in

   circt/lib/Dialect/FIRRTL/FIRRTLInstanceImplementation.cpp

   Lines 125 to 131 in 0b3feee

   	// Check that the instance op lists the correct layer requirements.
   	auto instanceLayers = instanceOp->getAttrOfType<ArrayAttr>("layers");
   	auto moduleLayers = referencedModule.getLayersAttr();
   	if (instanceLayers != moduleLayers)
   	return emitNote(instanceOp->emitOpError()
   	<< "layers must be " << moduleLayers << ", but got "
   	<< instanceLayers);

2. An extmodule must keep identical layers to its actual definition. We will perform this check when replacing extmodules with modules, since layers are part of the interface. Any mismatched extmodule that shares the same name with a module will be treated as a duplicate definition.

[seldridge]

I'm not super worried about accidental name collisions as this flow should theoretically allow for that to always be resolved so long as two circuits are linked. The only time that a true error occurs is if two circuits have the same public module. You can't do anything there and that's an error.

I would only mangle private symbols when necessary to avoid collisions. (Note: you will need to mangle lots of private symbols as this will fundamentally work at an MLIR level and not a FIRRTL level where there are few private symbols. E.g., you need to handle hierpath ops which will show up if you try to link after the FIRRTL pipeline runs.)

High level, this sounds good to me. I would like this implemented as:

1. A pass that merges circuits and does extmodule -> module resolution. This does not require that all extmodules be resolved (as you may link and still have unresolved references). Unresolved references is a Verilog elaboration-time problem.
2. A tool firtool-linker, firtool-ld, or firld (as I think @dtzSiFive originally called it) which invokes this pass and supports FIRRTL text input, MLIR input/output, and MLIR bytecode input/output.

I don't think that this should be part of firtool so long as everything supports mlir bytecode. E.g., an invocation like this should work: firld Foo.fir Bar.fir Baz.fir --emit-bytecode | firtool --format=mlir should work and will be fast. Alternatively: firld Foo.fir Bar.fir Bz.fir --emit-bytecode | circt-translate --export-firrtl.

[unlsycn]

I'm not super worried about accidental name collisions as this flow should theoretically allow for that to always be resolved so long as two circuits are linked. The only time that a true error occurs is if two circuits have the same public module. You can't do anything there and that's an error.

I would only mangle private symbols when necessary to avoid collisions. (Note: you will need to mangle lots of private symbols as this will fundamentally work at an MLIR level and not a FIRRTL level where there are few private symbols. E.g., you need to handle hierpath ops which will show up if you try to link after the FIRRTL pipeline runs.)

High level, this sounds good to me. I would like this implemented as:

1. A pass that merges circuits and does extmodule -> module resolution. This _does not_ require that all extmodules be resolved (as you may link and still have unresolved references). Unresolved references is a Verilog elaboration-time problem.

2. A tool `firtool-linker`, `firtool-ld`, or `firld` (as I think [@dtzSiFive](https://github.com/dtzSiFive) originally called it) which invokes this pass and supports FIRRTL text input, MLIR input/output, and MLIR bytecode input/output.

I don't think that this should be part of firtool so long as everything supports mlir bytecode. E.g., an invocation like this should work: firld Foo.fir Bar.fir Baz.fir --emit-bytecode | firtool --format=mlir should work and will be fast. Alternatively: firld Foo.fir Bar.fir Bz.fir --emit-bytecode | circt-translate --export-firrtl.

Is it necessary to support .fir files as input? The FIRRTL parser has a bunch of options which I personally think should be processed in firtool rather than firld. Perhaps we can parse .fir files in firtool first and link MLIR input exclusively in firld?

[seldridge]

Is it necessary to support .fir files as input? The FIRRTL parser has a bunch of options which I personally think should be processed in firtool rather than firld. Perhaps we can parse .fir files in firtool first and link MLIR input exclusively in firld?

Ah, sorry, no. Not necessary. It's fine if firld only operates on MLIR and MLIR bytecode. Yes, parsing all .fir files to MLIR (bytecode) and then using firld is completely fine.