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, 23 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))
+  }
+
+}