Add SortModules Transform (#1905)

* Add SortModules to transform to def-before-use

Adds a new transform, SortModules, that transforms a FIRRTL circuit
to enforce an invariant of modules and external modules being defined
before use. This transform is left as optional in the event that a
user may wish to have a quick way of getting the circuit to respect
this property as may be expected of some other tool, e.g., MLIR.

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@sifive.com>

* Add test of SortModules transform

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@sifive.com>

Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com>

2 files changed, 66 insertions, 0 deletions

diff --git a/src/main/scala/firrtl/transforms/SortModules.scala b/src/main/scala/firrtl/transforms/SortModules.scala
new file mode 100644
index 00000000..ffac1661
--- /dev/null
+++ b/src/main/scala/firrtl/transforms/SortModules.scala
@@ -0,0 +1,23 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package firrtl.transforms
+
+import firrtl.{CircuitState, DependencyAPIMigration, Transform}
+import firrtl.analyses.InstanceKeyGraph
+import firrtl.options.Dependency
+import firrtl.stage.Forms
+
+/** Return a circuit where all modules (and external modules) are defined before use. */
+class SortModules extends Transform with DependencyAPIMigration {
+
+  override def prerequisites = Seq(Dependency(firrtl.passes.CheckChirrtl))
+  override def optionalPrerequisites = Seq.empty
+  override def optionalPrerequisiteOf = Forms.ChirrtlEmitters
+  override def invalidates(a: Transform) = false
+
+  override def execute(state: CircuitState): CircuitState = {
+    val modulesx = InstanceKeyGraph(state.circuit).moduleOrder.reverse
+    state.copy(circuit = state.circuit.copy(modules = modulesx))
+  }
+
+}
diff --git a/src/test/scala/firrtlTests/transforms/SortModulesSpec.scala b/src/test/scala/firrtlTests/transforms/SortModulesSpec.scala
new file mode 100644
index 00000000..4aabeeea
--- /dev/null
+++ b/src/test/scala/firrtlTests/transforms/SortModulesSpec.scala
@@ -0,0 +1,43 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package firrtlTests.transforms
+
+import firrtl.{ir, CircuitState, Parser}
+import firrtl.transforms.SortModules
+import firrtl.traversals.Foreachers._
+
+import org.scalatest.flatspec.AnyFlatSpec
+import org.scalatest.matchers.should.Matchers
+
+import scala.collection.mutable
+
+class SortModulesSpec extends AnyFlatSpec with Matchers {
+
+  private def collectModules(names: mutable.ArrayBuffer[String], module: ir.DefModule): Unit = names += module.name
+
+  behavior.of("SortModules")
+
+  it should "enforce define before use of modules" in {
+
+    val input =
+      """|circuit Foo:
+         |  module Foo:
+         |    inst bar of Bar
+         |  module Bar:
+         |    inst baz of Baz
+         |  extmodule Baz:
+         |    input a: UInt<1>
+         |""".stripMargin
+
+    val state = CircuitState(Parser.parse(input), Seq.empty)
+    val moduleNames = mutable.ArrayBuffer.empty[String]
+
+    (new SortModules)
+      .execute(state)
+      .circuit
+      .foreach(collectModules(moduleNames, _: ir.DefModule))
+
+    (moduleNames should contain).inOrderOnly("Baz", "Bar", "Foo")
+  }
+
+}