Skip to content

Instantly share code, notes, and snippets.

@seldridge

seldridge/forms2dep.md

Forked from azidar/forms2dep.md
Last active September 12, 2023 08:29
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save seldridge/0959d714fba6857c5f71ebc7c9044fcf to your computer and use it in GitHub Desktop.
Save seldridge/0959d714fba6857c5f71ebc7c9044fcf to your computer and use it in GitHub Desktop.
Download ZIP
Migrating FIRRTL Transforms from inputForm/outputForm to dependency API
Raw
forms2dep.md

Introduction

Hello! Hopefully you saw this linked to in a deprecation warning and want to migrate your code. Great! We want to make your migration as easy as possible. If you have any questions (or feedback), feel free to get in touch with a developer via any of the following mediums:

Thanks for bearing with us.

tl;dr:

  1. Mix-in DependencyAPIMigration into your transform
  2. Delete your transform's implementations of inputForm and outputForm
  3. Provide implementations of the four Dependency API methods:
  • prerequisites: Seq[TransformDependency]
  • optionalPrerequisites: Seq[TransformDependency]
  • optionalPrerequisiteOf: Seq[TransformDependency]
  • invalidates(a: Transform): Boolean

Read on for a full description of the motivations and implementations of this migration process.

Summary

In FIRRTL 1.3, we introduce a new Dependency API as a replacement for CircuitForm. The Dependency API enables fine grained specification of dependencies that makes the FIRRTL compiler and its use of custom transforms leaner and faster.

Please migrate your custom transforms to the new Dependency API. CircuitForm will be removed in FIRRTL 1.4.

What are Forms?

Forms were a way to describe, in the FIRRTL compiler, the state of the circuit regarding which IR nodes exist within the circuit and which properties a circuit description has. The following forms were available:

  • ChirrtlForm representing the output of Chisel
  • HighForm representing the FIRRTL specification
  • MidForm is HighForm with additional restrictions. This is a static-single-assignment (SSA) representation without when statements, subacceses, intervals, or fixed point types. Additionally, all bundle/vector connections are expanded and made explicit.
  • LowForm is MidForm with additional restrictions. Aggregate types (bundles and vectors) are flattened into their constituent parts, resets are converted to muxes, and all wires are converted to nodes (no wires exist in the circuit).

Lower forms are subsets of higher forms. As an example, consider the following HighForm FIRRTL circuit describing a multiplexer:

circuit MyMux:
  module MyMux:
    input a: UInt<1>
    input b: UInt<1>
    input sel: UInt<1>
    output c: UInt<1>
    when eq(sel, UInt<1>(0)):
      c <= a
    else:
      c <= b

When this is lowered to MidForm FIRRTL, all when statements are converted to mux. The resulting mid-form circuit is:

circuit MyMux:
  module MyMux:
    input a: UInt<1>
    input b: UInt<1>
    input sel: UInt<1>
    output c: UInt<1>

    node _GEN_0 = mux(eq(sel, UInt<1>("h0")), a, b)
    c <= _GEN_0

The FIRRTL compiler also had an UnknownForm which was a circuit whose form was not known or not set.

The FIRRTL compiler was constructed as a sequence of transformations of the FIRRTL IR. These transformations were then grouped together into "Lowering Compilers" for lowering the circuit from ChirrtlForm to LowForm:

  • ChirrtlToHighFirrtl which read ChirrtlForm and output HighForm
  • HighFirrtlToMiddleFirrtl which read HighForm and output MidForm
  • MiddleFirrtlToLowFirrtl which read MidForm and output LowForm
  • LowFirrtlOptimizations which read LowForm and output LowForm that was optimized for backend emission

While in-tree FIRRTL transforms could be added anywhere inside these transforms, custom transforms would specify their location by describing an inputForm and outputForm. The FIRRTL compiler would then insert custom transforms after lowering compilers with a matching outputForm and re-run any lowering compilers if the custom transform's outputForm was higher than the current form. E.g., a custom transform specified as inputForm=LowForm/outputForm=MidForm would result in the following sequence:

  1. MiddleFirrtlToLowFirrtl
  2. MyCustomTransform
  3. MiddleFirrtlToLowFirrtl

This proved to be problematic for a number of reasons:

  1. CircuitForm-based specification is too coarse grained. Custom transforms can only run at specific locations and re-lowerings would do too much work.
  2. The dependencies between in-tree transforms was implicit based on their ordering inside a lowering compiler. It was both unclear how in-tree transforms depend on each other.
  3. The CircuitForm specification for a transform inside a lowering compiler is either conservatively set to UnknownForm precluding the ability of this transform to be scheduled as a custom transform or, if set to something else, incorrect.
  4. There was no mechanism to specify dependencies between custom transforms other than ordering them in a certain way on the command line.
  5. The migration of Chisel and FIRRTL into a collection of Phases results in similar problems requiring specification of dependencies between Phases. Ergo, there's a general problem that we need to solve for all Chisel/FIRRTL infrastructure.

The new Dependency API is intended to fix these problems.

What is the new Dependency API?

The Dependency API is inspired by the LLVM compiler infrastructure's approach to passes and pass managers. We define both a Dependency API as a means for transforms to describe how they relate to other transforms and utilities for determining a valid transform ordering (or erroring if no such ordering is possible).

Dependency API

The FIRRTL Dependency API lets a transform specify four types of dependencies. For the purposes of discussion, we refer to these as the dependencies of some transform Foo. Other metasyntactic variables (Bar, Baz, Qux, and Quz), refer to other transforms:

  • prerequisites are the set of transforms that must run before Foo. If Bar is a prerequisite of Foo then Foo will not run correctly unless Bar before it.
  • invalidates are the set of transforms that Foo invalidates (destroys the work of) or enables more work to be done. If Foo invalidates Baz then Baz must be run again before any transform which has a prerequisite on Baz can safely run.
  • optionalPrerequisites are the set of transforms that should be run before Foo. However, any optionalPrerequisites will only actually run if the user requests they run or if listed as prerequisite by another transform. If Foo lists Qux as an optionalPrerequisite, then trying to run Foo by itself will just run Foo. However, trying to run Foo and Qux will cause Qux to run before Foo.
  • optionalPrerequisiteOf injects an optionalPrerequisite of Foo into another transform. Foo specifying Quz as an optionalPrerequisiteOf is equivalent to Quz specifying Foo as an optionalPrerequisite. This is not a mechanism to force downstream transforms to run! Trying to run Foo by itself will result in only Foo running. If running both Foo and Quz then Foo will run before Quz.

Both optionalPrerequisites and optionalPrerequisitesOf are a mechanism to coerce an ordering of one transform with respect to another, but are not a mechanism to add transforms that must be run.

Consider a custom transform called MyCustomTransform where you want to define its dependencies at a fine granularity. If this transform requires that a circuit has been deduplicated it can state that without having to broadly require HighForm. Additionally, if it generates new FIRRTL IR nodes with UnknownType, it can declare that types need to be inferred after it runs. It has no other requirements.

You can now describe this as:

import firrtl._
import firrtl.options.Dependency
import firrtl.passes.InferTypes
import firrtl.transforms.DedupModules
import firrtl.stage.TransformManager.TransformDependency

class MyCustomTransform extends Transform with DependencyAPIMigration {

  override def prerequisites: List[TransformDependency] = List(Dependency[DedupModules])

  override def invalidates(xform: Transform): Boolean = xform match {
    case InferTypes => true
    case _          => false
  }

  override def optionalPrerequisites: Seq[TransformDependency] = Seq.empty

  override def optionalPrerequisiteOf: Seq[TransformDependency] = Seq.empty

  override def execute(cs: CircuitState): CircuitState = ???
}

Here, TransformDependency is a type alias:

type TransformDependency = Dependency[Transform]

Dependencies can be specified as classes, objects, or a mix of both. The object firrtl.options.Dependency can be used to construct these and to convert objects to dependencies.

import firrtl._
import firrtl.options.Dependency
import firrtl.transforms.DedupModules
import firrtl.passes.InferTypes

val myDependencies: Seq[Dependency[Transform]] = Seq(
  Dependency[DedupModules], /* This transform is constructed from a class. Note brackets '[]' */
  Dependency(InferTypes)    /* This transform is constructed from an object. Note parentheses '()' */
)

val myTransforms: Seq[Transform] = myDependencies.map(_.getObject)

Migration Overview

To be compliant with FIRRTL 1.3, we provide a three-step migration process to move from CircuitForm to the new Dependency API.

  1. Mix-in the trait DependencyAPIMigration to your transform

  2. Remove your transform's definition of inputForm and outputForm

  3. Define your transform's dependencies using the Dependency API

With an example:

class Foo extends Transform {

  override def inputForm = HighForm

  override def outputForm = HighForm

  private def onModule(mod: DefModule): DefModule = ???

  override def execute(state: CircuitState): CircuitState = {

    val circuitx = state.circuit.map(onModule)

    val cleanedUp = InferTypes.execute(circuitx)

    state.copy(circuit = cleanedUp)
  }

}

Converted to use the Dependency API this now looks like:

import firrtl._
import firrtl.stage.Forms

class Foo extends Transform with DependencyAPIMigration {

  override def prerequisites = Forms.HighForm

  override def optionalPrerequisites = Seq.empty

  override def optionalPrerequisitesOf = Forms.HighEmitters

  override def invalidates(tx: Transform) = tx match {
    case InferTypes => true
    case _          => false
  }

  private def onModule(mod: DefModule): DefModule = ???

  override def execute(state: CircuitState): CircuitState = {

    val circuitx = state.circuit.map(onModule)

    state.copy(circuit = circuitx)
  }

}

The DependencyAPIMigration trait provides final implementations of inputForm and outputForm so that you can remove them from your custom transform.

The dependencies were divined in the following way:

  • prerequisites: Previously this transform depended on HighForm. We don't have any desire to change when this runs, so we define it's prerequisites as firrtl.stage.Forms.HighForm which is the same set of transforms that would have run previously.
  • optionalPrerequisites: It is unlikely that you will need to specify optional prerequisites unless your transform is an inputForm=LowForm transform. This is discussed more in the Corner Cases section.
  • optionalPrerequisiteOf: We'd like this transform to run before any relevant emitters. So, we use the shorthand firrtl.stage.Forms.HighEmitters which includes the HighFirrtlEmitter, MidFirrtlEmitter, LowFirrtlEmitter, and the Verilog emitters.
  • invalidates: While our transform was inputForm=HighForm/outputForm=HighForm, indicating that it invalidated nothing, we used a common pattern to "clean up" after the transform runs. You'll notice that in the original version, we ran InferTypes. As part of the migration process, you can move any cleanup transforms that you have into your invalidates definition.

We highly recommend you take the time to understand your transform you are migrating and implement the Dependency API properly.

Specifically, you should ask yourself:

  • What transforms does my transform actually require?
  • What transforms does my transform invalidate?

All FIRRTL transformations in the firrtl repo have been upgraded, and you can use them as an examples. In addition, you can checkout the dependency API tests.

The migration will require removing two functions def inputForm = ... and def outputForm = ... and implementing two functions override def prerequisites: List[Dependency[Transform]] = ... and override def invalidates(xform: Transform): Boolean = ....

Detailed Migration Information

What follows are specific guides on how you can migrate CircuitForm-based dependencies.

In the following subsections, these cases are highlighted with particular attention to options you have to migrate your transform to the Dependency API.

Converting CircuitForms to Prerequisites

Case 1: inputForm != LowForm

If your inputForm is not equal to LowForm, then you can use the following table to determine your prerequisites:

  • inputForm = firrtl.MidForm -> prerequisites = firrtl.stage.Forms.MidForm
  • inputForm = firrtl.HighForm -> prerequisites = firrtl.stage.Forms.Deduped
  • inputform = firrtl.ChirrtlForm -> prerequisites = Nil

If your inputForm was UnknownForm, then you need to understand the context where it was being used, and determine the prerequisites accordingly. Note that all forms in firrtl.stage.Forms._ are just collections of transformations. You can inspect that file to get a better idea of the transforms which make up the FIRRTL compiler.

Case 2: inputForm == LowForm

The definition of LowForm as an inputForm is ambiguous and requires special attention when migrating. For more information on the reasons for this see firrtl#1165.

If your have a custom transform with inputForm=LowForm, then this could mean different things based on what compiler you were using. You can run FIRRTL with different compilers/emitters and a custom transform Bar with inputForm=LowForm:

# Compile a circuit to Low FIRRTL
firrtl --compiler low --input-file Foo.fir --custom-transforms Bar

# Compile a circuit to Verilog with minimal optimizations
firrtl --compiler mverilog --input-file Foo.fir --custom-transforms Bar

# Compile a circuit to Verilog with full optimizations
firrtl --compiler verilog --input-file Foo.fir --custom-transforms Bar

For all three invocations, transform Bar runs as late as possible, right before the LowFirrtlEmitter or VerilogEmitter. If you want to preserve this behavior, you should need to use an optionalPrerequisite to cause the transform to run after optimizations, but not to force optimizations to run:

override def prerequisites = Forms.LowForm
override def optionalPrerequisites = Forms.LowFormOptimized

Alternatively, you can cause your transform to run as soon as the circuit has been compiled to low form:

override def prerequisites = Forms.LowForm
override def optionalPrerequisites = Seq.empty

The choice here depends on whether your transform benefits from running after optimizations.

In the event that you incorrectly wrote a transform that requires optimizations and will fail without optimizations, then you should declare this with a hard prerequisite:

override def prerequisites = Forms.LowFormOptimized
override def optionalPrerequisites = Seq.empty

Note that doing this will mean that optimizations will run if you include your custom transform and compile using --compile mverilog.

Converting CircuitForm to Invalidates

Case 1: inputForm == outputForm == UnknownForm

In this situation, you likely wrote a transform which you are using directly and not relying on existing scheduling. To get a handle on what it's invalidating, you should look at what transforms you chose to run after it. You likely invalidate at least those transforms.

Case 2: inputForm >= outputForm != UnknownForm

In this case, your transform likely does not invalidate any other transformations, because the inputForm/outputForm API wasn't rerunning any transforms. Thus, its likely you don't invalidate anything and you can use:

override def invalidates(xform: Transform): Boolean = false

You may alternatively mixin the PreservesAll[Transform] to get the same behavior.

If your transformation manually runs a bunch of transformations at the end to patch up the CircuitState, its possible to remove those and instead add them to your invalidates function. E.g., if your transformation runs DedupModules at the end, your invalidates could look like:

override def invalidates(a: Transform): Boolean = a match {
  case _: firrtl.transforms.DedupModules => true
  case _                                 => false
}
Case 3: inputForm < outputForm && outputForm != HighForm

For faster and less conservative invalidation, consider if you know more about what this transform does. If so, you can selectively invalidate the transforms you know need to be rerun. For example if you invalidate deduplication (and want it to be rerun) you can do the following:

override def invalidates(a: Transform): Boolean = a match {
  case _: firrtl.transforms.DedupModules => true
  case _                                 => false
}

To get identical behavior at the cost of runtime performance, you need to invalidate all transforms that ran between your inputForm and outputForm. For example, if your inputForm=LowForm and outputForm=MidForm, you need to invalidate everything that could have possibly ran after MidForm. You can do this with:

override def invalidates = (Forms.VerilogOptimized -- Forms.MidForm).contains(Dependency.fromTransform(a))
Case 4: inputForm < outputForm && outputForm == HighForm

The definition of HighForm as an outputForm (when the inputForm is lower than HighForm) requires special attention when migrating. For more information on the reasons for this see firrtl#1165.

If you have a custom transform with an inputForm "lower" than HighForm and an outputForm=HighForm, then you need to decide what you actually invalidate.

Previously, this would conservatively rerun numerous transforms including: ToWorkingIR, all resolve transforms (e.g., InferTypes), all checks (e.g., CheckTypes), and firrtl.transforms.DedupModules. Counterintuitively, if you transform was inputForm=HighForm/outputForm=HighForm none of these transforms would run. **In effect, outputForm=HighForm has different meaning for different inputForms.

With very high probability, your transform is not invalidating such a large swath of transforms and you'll see a benefit from trimming the invalidation set to what your transform actually invalidates. With similarly high probability, you are likely invalidating something and need to figure out what. Likely transform invalidation candidates are: ResolveKinds, InferTypes, Uniquify, ResolveFlows, and InferWidth. Your mileage may vary, however.

If you truly want to preserve the old behavior (or would just like to migrate with a guarantee of preserving old behavior), you can enable the old behavior with:

override def prerequisites = Forms.MidForm
override def optionalPrerequisites = Seq.empty
override def optionalPrerequisiteOf = Forms.MidEmitters

private val invalidates = Forms.VerilogOptimized.toSet -- Forms.MinimalHighForm
override def invalidates(a: Transform): Boolean = invalidates(Dependency.fromTransform(a))

Debugging

Default Invalidation Behavior

The default implementation for invalidation is to invalidate everything (except itself---it is impossible for a transform to invalidate itself). This conservative behavior can result in no valid transform ordering existing.

If you run into errors stating No transform ordering possible due to cyclic dependency... then you likely need to override the default invalidates.

If your transform perfectly cleans up after itself, you can use the helper trait PreservesAll[Transform] which provides an implementation of invalidating nothing. This is frequently mixed into in-tree FIRRTL transforms.

My Transform ran, but it didn't effect the output

If you got your transform to run, but it didn't produce any effect in an emitter circuit, then you may need to add an optionalPrerequisiteOf on one or more emitters.

For example, if your transform was an inputForm=MidForm/outputForm=MidForm transform then it should produce output if you invoke FIRRTL with ./firrtl --compiler middle --custom-transforms MyTransform. However, without an optionalPrerequisiteOf on the MiddleFirrtlEmitter, then your transform could legally be scheduled before the emitter.

To avoid this, add the optionalPrerequisiteOf:

override def optionalPrerequisiteOf = Forms.MidEmitters

Form.MidEmitters is the set of all emitters including MiddleFirrtlEmitter and later.

You can also inspect the order in which the transforms ran (see the next subsection).

Pretty Printing Your Transform Ordering

Sometimes it can be tricky to figure out what's going on. When did my transform get scheduled? Did it run in a sane place?

To help with this, you can use the prettyPrint method defined on firrtl.stage.transforms.Compiler. Alternatively, you can turn on --log-level info and you will get this pretty print output in your terminal.

Below is the full, current output for the FIRRTL compiler. An increase in indentation level indicates that something was invalidated some transforms are being re-run.

./utils/bin/firrtl -i regress/ICache.fir --compiler verilog --target-dir test_run_dir --log-level info
# Computed transform order in: 548.3 ms
# Determined Transform order that will be executed:
#   firrtl.stage.transforms.Compiler
#   ├── firrtl.passes.CheckChirrtl$
#   ├── firrtl.passes.CInferTypes$
#   ├── firrtl.passes.CInferMDir$
#   ├── firrtl.passes.RemoveCHIRRTL$
#   ├── firrtl.passes.ToWorkingIR$
#   ├── firrtl.passes.CheckHighForm$
#   ├── firrtl.passes.ResolveKinds$
#   ├── firrtl.passes.InferTypes$
#   ├── firrtl.passes.CheckTypes$
#   ├── firrtl.passes.Uniquify$
#   ├── firrtl.stage.TransformManager
#   │   ├── firrtl.passes.ResolveKinds$
#   │   └── firrtl.passes.InferTypes$
#   ├── firrtl.passes.ResolveFlows$
#   ├── firrtl.passes.CheckFlows$
#   ├── firrtl.passes.InferBinaryPoints
#   ├── firrtl.passes.TrimIntervals
#   ├── firrtl.passes.InferWidths
#   ├── firrtl.passes.CheckWidths$
#   ├── firrtl.transforms.InferResets
#   ├── firrtl.stage.TransformManager
#   │   └── firrtl.passes.CheckTypes$
#   ├── firrtl.transforms.DedupModules
#   ├── firrtl.passes.PullMuxes$
#   ├── firrtl.passes.ReplaceAccesses$
#   ├── firrtl.passes.ExpandConnects$
#   ├── firrtl.passes.ZeroLengthVecs$
#   ├── firrtl.passes.RemoveAccesses$
#   ├── firrtl.stage.TransformManager
#   │   ├── firrtl.passes.Uniquify$
#   │   └── firrtl.stage.TransformManager
#   │       ├── firrtl.passes.ResolveKinds$
#   │       └── firrtl.passes.InferTypes$
#   ├── firrtl.passes.ExpandWhensAndCheck
#   ├── firrtl.stage.TransformManager
#   │   ├── firrtl.passes.ResolveKinds$
#   │   ├── firrtl.passes.InferTypes$
#   │   ├── firrtl.passes.ResolveFlows$
#   │   └── firrtl.passes.InferWidths
#   ├── firrtl.passes.RemoveIntervals
#   ├── firrtl.passes.ConvertFixedToSInt$
#   ├── firrtl.passes.ZeroWidth$
#   ├── firrtl.stage.TransformManager
#   │   └── firrtl.passes.InferTypes$
#   ├── firrtl.passes.LowerTypes$
#   ├── firrtl.stage.TransformManager
#   │   ├── firrtl.passes.ResolveKinds$
#   │   ├── firrtl.passes.InferTypes$
#   │   ├── firrtl.passes.ResolveFlows$
#   │   └── firrtl.passes.InferWidths
#   ├── firrtl.passes.Legalize$
#   ├── firrtl.transforms.RemoveReset$
#   ├── firrtl.stage.TransformManager
#   │   └── firrtl.passes.ResolveFlows$
#   ├── firrtl.transforms.CheckCombLoops
#   ├── firrtl.checks.CheckResets
#   ├── firrtl.transforms.RemoveWires
#   ├── firrtl.passes.RemoveValidIf$
#   ├── firrtl.transforms.ConstantPropagation
#   ├── firrtl.passes.PadWidths$
#   ├── firrtl.stage.TransformManager
#   │   ├── firrtl.transforms.ConstantPropagation
#   │   └── firrtl.passes.Legalize$
#   ├── firrtl.passes.memlib.VerilogMemDelays$
#   ├── firrtl.stage.TransformManager
#   │   ├── firrtl.transforms.ConstantPropagation
#   │   └── firrtl.stage.TransformManager
#   │       └── firrtl.passes.Legalize$
#   ├── firrtl.passes.SplitExpressions$
#   ├── firrtl.transforms.CombineCats
#   ├── firrtl.passes.CommonSubexpressionElimination$
#   ├── firrtl.transforms.DeadCodeElimination
#   └── firrtl.VerilogEmitter
#       ├── firrtl.transforms.BlackBoxSourceHelper
#       ├── firrtl.transforms.FixAddingNegativeLiterals
#       ├── firrtl.transforms.ReplaceTruncatingArithmetic
#       ├── firrtl.transforms.InlineBitExtractionsTransform
#       ├── firrtl.transforms.PropagatePresetAnnotations
#       ├── firrtl.transforms.InlineCastsTransform
#       ├── firrtl.transforms.LegalizeClocksTransform
#       ├── firrtl.transforms.FlattenRegUpdate
#       ├── firrtl.transforms.DeadCodeElimination
#       ├── firrtl.passes.VerilogModulusCleanup$
#       ├── firrtl.transforms.VerilogRename
#       ├── firrtl.passes.VerilogPrep$
#       └── firrtl.AddDescriptionNodes

Other Features You May Be Interested In

DependnecyManager and the new firrtl.stage.transforms.Compiler

The Dependency API provides a polymorphic trait for determining the order of arbitrary things with dependencies specified using the Dependency API called DependencyManager. You will likely never have to use this directly, but it's worth mentioning.

Behind the scenes, a DependencyManager is a scheduler that will determine an ordering of transforms for some set of transforms you want to run. It, and it's children, all take the following parameters:

  • targets: a sequence of transforms you want to run
  • currentState: the transforms that have already run and not been invalidated
  • knownObjects: any existing transforms that you've already constructed. This can save work and prevent extra transforms from being constructed if they already exist.

Given arguments for these parameters, the DependencyManager will determine a good ordering of transforms that runs all targets without them being invalidated. It may fail to determine an ordering if you specified any circular dependencies.

For your purposes, you care about one child of DependencyManager: firrtl.stage.transforms.Compiler. This is a FIRRTL transform that runs other FIRRTL transforms for you. You can use this to construct arbitrary FIRRTL compilers to run whatever you want.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment