search

chipsalliance / firrtl

Flexible Intermediate Representation for RTL
https://www.chisel-lang.org/firrtl/
Apache License 2.0
720 stars 176 forks source link

New Behavior Proposal: ModuleTarget behavior during Deduplication #1521

Open azidar opened 4 years ago

azidar commented 4 years ago

Introduction

Hi everyone! Here is my description of this pr: https://github.com/freechipsproject/firrtl/pull/1442, which implements new target behavior for transforms DedupModules and EliminateTargetPaths. This document will talk about the old behavior, and then the options for new behavior (plus justifications).

Ongoing Example

circuit Top:
  module Foo: ...
  module Bop: ...
  module Fub: ...
  module Bar: ...
  module Baz:
    inst foo of Foo
    inst bar of Bar
  module Qux:
    inst foo of Fub
    inst bar of Bop
  module Top:
    inst baz of Baz
    inst qux of Qux

Deduplication

Foo, Bop, Fub, Bar all dedup to Foo Baz and Qux dedup to Baz

For now, we only discuss Baz and Qux, but it may become relevant to have a three-level hierarchy so I'm keeping the full example around.

Old Behavior

ModuleName

When ModuleName was on a module that was deduplicated, it was sticky and transferred to the deduplicated module:

"~Top|Qux" >>> "~Top|Baz" "~Top|Baz" >>> "~Top|Baz"

ModuleTarget/InstanceTarget

If modules of identical structure but had different annotations referring to them using ModuleTarget or InstanceTarget, deduplication would not occur for the differently annotated modules. If they were the same, then deduplication would occur, with ModuleTargets renaming as such:

"~Top|Qux" >>> "~Top|Baz" "~Top|Baz" >>>"~Top|Baz" "~Top|Top/qux:Qux" >>> "~Top|Top/qux:Baz" "~Top|Top/baz:Baz" >>> "~Top|Top/baz:Baz"

New Behavior

The main user-goal was to use the new Target system to annotate modules of identical structure with different annotations. We have three different proposals for how to do this:

  1. Make ModuleTarget "sticky" like the ModuleName deduplication semantics
  2. Convert 'ModuleTarget' to 'InstanceTarget' automatically during deduplication
  3. Do both by implementing (1) with a new "sticky AST" target, while also implenting (2)

Option 1: Sticky ModuleTarget

With this option, it is pretty straightforward to implement; we just stop preventing deduplication from being sensitive to the annotations. Thus:

ModuleTarget("Top", "Qux") >>> ModuleTarget("Top", "Baz") ModuleTarget("Top", "Baz") >>> ModuleTarget("Top", "Baz") InstanceTarget("Top", "Top", Nil, "qux", "Qux") >>> InstanceTarget("Top", "Top", Nil, "qux", "Baz") InstanceTarget("Top", "Top", Nil, "baz", "Baz") >>> InstanceTarget("Top", "Top", Nil, "baz", "Baz")

Note that if only "Qux" had an annotation which previously propagated to "Baz", but then changed to prevent dedup, we would see non-local behavior change where changing "Qux" changes "Baz" annotations.

Pros:

  1. Simple to understand
  2. ModuleTargets always become ModuleTargets, so no type issue with renaming (e.g. MyAnno(mt: ModuleTarget) won't break under dedup.

Cons:

  1. Non-local annotation behavior (brittle to dedup).
  2. Non-reversible; annotations don't correctly propagate between eliminate-target-paths + dedup pattern

Option 2: Automatic InstanceTarget

The idea here is treat a ModuleTarget as referencing the instances of the module within the circuit. During duplication, we don't want to add an annotation to other instances; thus, we first convert it to an InstanceTarget.

ModuleTarget("Top", "Qux") >>> InstanceTarget("Top", "Top", Nil, "qux", "Baz") ModuleTarget("Top", "Baz") >>> InstanceTarget("Top", "Top", Nil, "baz", "Baz") InstanceTarget("Top", "Top", Nil, "qux", "Qux") >>> InstanceTarget("Top", "Top", Nil, "qux", "Baz") InstanceTarget("Top", "Top", Nil, "baz", "Baz") >>> InstanceTarget("Top", "Top", Nil, "baz", "Baz")

Note that an annotation on ModuleTarget("Top", "Qux") can look at the renamed value InstanceTarget("Top", "Top", Nil, "qux", "Baz") and derive the sticky version by looking at the final referred module "Baz".

Pros:

  1. Keeps annotation targeting independent of deduplication

Cons:

  1. "Sticky" behavior must be implemented by the annotation during its self-update function. May require additional book-keeping if the annotation is using an InstanceTarget of the deduped module to record the root of the reference.

Option 3: AST ModuleTargets + Automatic InstanceTarget

An "AST module target" is a ModuleTarget which has the same value for its module and circuit, e.g. ModuleTarget("Baz", "Baz"). The idea is that the CircuitTarget field now becomes a sort of 'scope' for the reference. Because the module and circuit are the same, it has no concept of instances because it thinks its top of the world. Thus during deduplication, we can do the following:

ModuleTarget("Qux", "Qux") >>> ModuleTarget("Baz", "Baz") ModuleTarget("Baz", "Baz") >>> ModuleTarget("Baz", "Baz") ModuleTarget("Top", "Qux") >>> InstanceTarget("Top", "Top", Nil, "qux", "Baz") ModuleTarget("Top", "Baz") >>> InstanceTarget("Top", "Top", Nil, "baz", "Baz") InstanceTarget("Top", "Top", Nil, "qux", "Qux") >>> InstanceTarget("Top", "Top", Nil, "qux", "Baz") InstanceTarget("Top", "Top", Nil, "baz", "Baz") >>> InstanceTarget("Top", "Top", Nil, "baz", "Baz")

Pros:

  1. Get sticky behavior with AST ModuleTarget
  2. Enable generic renaming of modules, independent of CircuitTarget

Cons:

  1. Removes CircuitTarget as a reliable namespace

Conclusion

I implemented option 3 (AST ModuleTargets + Automatic InstanceTarget), but I'm open to discussion. There is no TLDR, because I really need you to read the whole thing if you care to comment :)

Cheers!

jackkoenig commented 4 years ago

@azidar and I discussed this a bit, here are my thoughts from that discussion (not speaking for Adam, so he may disagree, particularly on (3))

1) This shouldn't block 1.3, we should do this but it's fine as a follow on 1.4

2) We should disentangle the concepts of "circuit" and "package"

Currently the circuit is the package and this is problematic. It makes it hard to "retop" a circuit because you are now changing the package. It makes linking different packages awkward because how can you refer to a subhierarchy of another package?

Strawman proposal is that we add a concept of package to CircuitState. This is not necessarily tied to this proposal, but the solution should be cognizant of a world with first-class package support.

Question about packages: how how do they affect Verilog emission, should the package prefix the module names?

3) AST targets should not be sticky, in fact they should block deduplication

Caveat: I feel like I haven't phrased this super well, and I'm not certain that I'm right here.

I think about it from the perspective of what happens if you split up a design and compile it separately. One (obvious) invariant is that that the resulting Verilog in the split compilation is functionally equivalent to the Verilog from a unified compilation. I don't think they have to be identical, some loss of cross-module optimization is fine (it's an optimization after all), but correctness obviously has to be preserved.

So then we have to reason about what cross-module things affect correctness: 1) Interfacing with other modules - obviously parent modules need blackbox representations of submodules to check types and connections 2) Combinational loop detection - there needs to be some connectivity analysis that can be globally checked 3) Width information - must be known for inputs and submodule outputs 4) Reset Type information - similar to width information

All of these are based on the connectivity of the module, the non-local information propagates via the connections of the ports.

If AST targets are sticky, then we introduce a 5th correctness concern: 5) Deduplication - annotations on modules that deduplicate with a module can affect correctness (eg. WiringTransform sinks)

It's not necessary bad to have additional global information that is necessary for this partitioned compilation, but Deduplication seems different in kind than the previous 4. As I stated, the non-local information only propagates along connections, in the case of Deduplication, it's purely based on structural equivalence. Also Deduplication is similar to the concept of CSE for functions, ie. it's similar to an optimization, so it's strange for it to be a correctness concern.

Historically, to make hierarchical place-and-route possible with Chisel, it has been a soft correctness concern, but perhaps the answer isn't to codify this wart via sticky annotations, but rather to make it possible to multiply instantiate a module in Chisel.

TLDR Sticky annotations make deduplication part of the definition of correctness in a way that is different than other non-local transformations and is thus not a great idea.

seldridge commented 4 years ago

Can this issue include some of the motivation for sticky annotations?

I struggle with this as I tend to view annotations as "information" and duplication/deduplication as non-destructive, information preserving views of the same circuit. However, I think I've had a limited view of what information is here. Consider the following:

Since deduplication is a proof of structural equivalence between two modules, I can see annotations sticky across deduplication as enabling a kind of inductive proof. E.g.:

  1. module Foo is analyzed and gets a NoCombinationalPathsAnnotation indicating that it has no combinational paths
  2. module Bar is added to the circuit (it's an ExtModule that gets linked in)
  3. module Bar deduplicates to module Foo
  4. By induction, Bar also has no combinational paths and should get a NoCombinationalPathsAnnotation

My gut instinct is that this (specific) example is a function of the type of information stored in an annotation and not the target used to attach it to the circuit. (That hints at an annotation mix-in with a complex update method.)

There are other annotations which obviously don't encode structural information, e.g., a HartIDAnnotation that encodes the hardware thread ID of one core in a multi-core Rocket build.

Are there other types of information like this?

How does this align with what you were thinking, @jackkoenig, @azidar?

seldridge commented 4 years ago

After re-reading @azidar's post, I think I'm saying almost the same thing. I do see the use case. :+1:

seldridge commented 4 years ago

Thinking some more about this...

I'm actually not sure that the module pointed at by ~Qux|Qux exists in the circuit ~Top. Put differently, what would the following renames mean in terms of circuit modifications?

I think the former is linking and the latter is fragmenting (whatever the opposite of linking is). E.g., linking would be:

circuit Top:
  extmodule Qux:
  module Top:
    inst qux of Qux
circuit Qux:
  module Qux:
    skip
circuit Top:
  module Qux:
    skip
  module Top:
    inst qux of Qux

This may imply that extmodule needs a means to avoid name conflicts, e.g., extmodule Qux as Quz.