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>

1 files changed, 43 insertions, 0 deletions

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")
+  }
+
+}