Improve performance of LowerTypes renaming (#2024)

This is done by having LowerTypes uses two RenameMaps instead of one for
each module. There is one for renaming instance paths, and one for
renaming everything within modules.

Also add some utilities:
* TargetUtils for dealing with InstanceTargets
* RenameMap.fromInstanceRenames

4 files changed, 121 insertions, 8 deletions

diff --git a/src/test/scala/firrtl/RenameMapPrivateSpec.scala b/src/test/scala/firrtl/RenameMapPrivateSpec.scala
new file mode 100644
index 00000000..d735e6c8
--- /dev/null
+++ b/src/test/scala/firrtl/RenameMapPrivateSpec.scala
@@ -0,0 +1,39 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package firrtl
+
+import firrtl.annotations.Target
+import firrtl.annotations.TargetToken.{Instance, OfModule}
+import firrtl.analyses.InstanceKeyGraph
+import firrtl.testutils.FirrtlFlatSpec
+
+class RenameMapPrivateSpec extends FirrtlFlatSpec {
+  "RenameMap.fromInstanceRenames" should "handle instance renames" in {
+    def tar(str: String): Target = Target.deserialize(str)
+    val circuit = parse(
+      """circuit Top :
+        |  module Bar :
+        |    skip
+        |  module Foo :
+        |    inst bar of Bar
+        |  module Top :
+        |    inst foo1 of Foo
+        |    inst foo2 of Foo
+        |    inst bar of Bar
+        |""".stripMargin
+    )
+    val graph = InstanceKeyGraph(circuit)
+    val renames = Map(
+      OfModule("Foo") -> Map(Instance("bar") -> Instance("bbb")),
+      OfModule("Top") -> Map(Instance("foo1") -> Instance("ffff"))
+    )
+    val rm = RenameMap.fromInstanceRenames(graph, renames)
+    rm.get(tar("~Top|Top/foo1:Foo")) should be(Some(Seq(tar("~Top|Top/ffff:Foo"))))
+    rm.get(tar("~Top|Top/foo2:Foo")) should be(None)
+    // Check of nesting
+    rm.get(tar("~Top|Top/foo1:Foo/bar:Bar")) should be(Some(Seq(tar("~Top|Top/ffff:Foo/bbb:Bar"))))
+    rm.get(tar("~Top|Top/foo2:Foo/bar:Bar")) should be(Some(Seq(tar("~Top|Top/foo2:Foo/bbb:Bar"))))
+    rm.get(tar("~Top|Foo/bar:Bar")) should be(Some(Seq(tar("~Top|Foo/bbb:Bar"))))
+    rm.get(tar("~Top|Top/bar:Bar")) should be(None)
+  }
+}
diff --git a/src/test/scala/firrtl/passes/LowerTypesSpec.scala b/src/test/scala/firrtl/passes/LowerTypesSpec.scala
index 70fa51fd..7ca98544 100644
--- a/src/test/scala/firrtl/passes/LowerTypesSpec.scala
+++ b/src/test/scala/firrtl/passes/LowerTypesSpec.scala
@@ -2,10 +2,13 @@
 
 package firrtl.passes
 import firrtl.annotations.{CircuitTarget, IsMember}
+import firrtl.annotations.TargetToken.{Instance, OfModule}
+import firrtl.analyses.InstanceKeyGraph
 import firrtl.{CircuitState, RenameMap, Utils}
 import firrtl.options.Dependency
 import firrtl.stage.TransformManager
 import firrtl.stage.TransformManager.TransformDependency
+import firrtl.testutils.FirrtlMatchers
 import org.scalatest.flatspec.AnyFlatSpec
 
 /** Unit test style tests for [[LowerTypes]].
@@ -228,22 +231,35 @@ class LowerTypesRenamingSpec extends AnyFlatSpec {
 }
 
 /** Instances are a special case since they do not get completely destructed but instead become a 1-deep bundle. */
-class LowerTypesOfInstancesSpec extends AnyFlatSpec {
+class LowerTypesOfInstancesSpec extends AnyFlatSpec with FirrtlMatchers {
   import LowerTypesSpecUtils._
   private case class Lower(inst: firrtl.ir.DefInstance, fields: Seq[String], renameMap: RenameMap)
   private val m = CircuitTarget("m").module("m")
+  private val igraph = InstanceKeyGraph(
+    parse(
+      """circuit m:
+        |  module c:
+        |    skip
+        |  module m:
+        |    inst i of c
+        |""".stripMargin
+    )
+  )
   def resultToFieldSeq(res: Seq[(String, firrtl.ir.SubField)]): Seq[String] =
     res.map(_._2).map(r => s"${r.name} : ${r.tpe.serialize}")
   private def lower(
-    n:         String,
-    tpe:       String,
-    module:    String,
-    namespace: Set[String],
-    renames:   RenameMap = RenameMap()
+    n:            String,
+    tpe:          String,
+    module:       String,
+    namespace:    Set[String],
+    otherRenames: RenameMap = RenameMap()
   ): Lower = {
     val ref = firrtl.ir.DefInstance(firrtl.ir.NoInfo, n, module, parseType(tpe))
     val mutableSet = scala.collection.mutable.HashSet[String]() ++ namespace
-    val (newInstance, res) = DestructTypes.destructInstance(m, ref, mutableSet, renames, Set())
+    val instRenames = scala.collection.mutable.ListBuffer[(Instance, Instance)]()
+    val (newInstance, res) = DestructTypes.destructInstance(m, ref, mutableSet, instRenames, Set())
+    val instMap = Map(OfModule("m") -> instRenames.toMap)
+    val renames = RenameMap.fromInstanceRenames(igraph, instMap).andThen(otherRenames)
     Lower(newInstance, resultToFieldSeq(res), renames)
   }
   private def get(l: Lower, m: IsMember): Set[IsMember] = l.renameMap.get(m).get.toSet
@@ -305,7 +321,7 @@ class LowerTypesOfInstancesSpec extends AnyFlatSpec {
       assert(get(l, i) == Set(i_))
 
       // the ports renaming is also noted
-      val r = portRenames.andThen(otherRenames)
+      val r = portRenames.andThen(l.renameMap)
       assert(r.get(i.ref("b")).get == Seq(i_.ref("b__c")))
       assert(r.get(i.ref("b").field("c")).get == Seq(i_.ref("b__c")))
       assert(r.get(i.ref("b_c")).get == Seq(i_.ref("b_c")))
diff --git a/src/test/scala/firrtlTests/RenameMapSpec.scala b/src/test/scala/firrtlTests/RenameMapSpec.scala
index 29466c72..bebeb0bf 100644
--- a/src/test/scala/firrtlTests/RenameMapSpec.scala
+++ b/src/test/scala/firrtlTests/RenameMapSpec.scala
@@ -5,6 +5,8 @@ package firrtlTests
 import firrtl.RenameMap
 import firrtl.RenameMap.IllegalRenameException
 import firrtl.annotations._
+import firrtl.annotations.TargetToken.{Instance, OfModule}
+import firrtl.analyses.InstanceKeyGraph
 import firrtl.testutils._
 
 class RenameMapSpec extends FirrtlFlatSpec {
diff --git a/src/test/scala/firrtlTests/annotationTests/TargetUtilsSpec.scala b/src/test/scala/firrtlTests/annotationTests/TargetUtilsSpec.scala
new file mode 100644
index 00000000..38266efe
--- /dev/null
+++ b/src/test/scala/firrtlTests/annotationTests/TargetUtilsSpec.scala
@@ -0,0 +1,56 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package firrtlTests.annotationTests
+
+import firrtl.analyses.InstanceKeyGraph.InstanceKey
+import firrtl.annotations._
+import firrtl.annotations.TargetToken._
+import firrtl.annotations.TargetUtils._
+import firrtl.testutils.FirrtlFlatSpec
+
+class TargetUtilsSpec extends FirrtlFlatSpec {
+
+  behavior.of("instKeyPathToTarget")
+
+  it should "create a ModuleTarget for the top module" in {
+    val input = InstanceKey("Top", "Top") :: Nil
+    val expected = ModuleTarget("Top", "Top")
+    instKeyPathToTarget(input) should be(expected)
+  }
+
+  it should "create absolute InstanceTargets" in {
+    val input = InstanceKey("Top", "Top") ::
+      InstanceKey("foo", "Foo") ::
+      InstanceKey("bar", "Bar") ::
+      Nil
+    val expected = InstanceTarget("Top", "Top", Seq((Instance("foo"), OfModule("Foo"))), "bar", "Bar")
+    instKeyPathToTarget(input) should be(expected)
+  }
+
+  it should "support starting somewhere down the path" in {
+    val input = InstanceKey("Top", "Top") ::
+      InstanceKey("foo", "Foo") ::
+      InstanceKey("bar", "Bar") ::
+      InstanceKey("fizz", "Fizz") ::
+      Nil
+    val expected = InstanceTarget("Top", "Bar", Seq(), "fizz", "Fizz")
+    instKeyPathToTarget(input, Some("Bar")) should be(expected)
+  }
+
+  behavior.of("unfoldInstanceTargets")
+
+  it should "return nothing for ModuleTargets" in {
+    val input = ModuleTarget("Top", "Foo")
+    unfoldInstanceTargets(input) should be(Iterable())
+  }
+
+  it should "return all other InstanceTargets to the same instance" in {
+    val input = ModuleTarget("Top", "Top").instOf("foo", "Foo").instOf("bar", "Bar").instOf("fizz", "Fizz")
+    val expected =
+      input ::
+        ModuleTarget("Top", "Foo").instOf("bar", "Bar").instOf("fizz", "Fizz") ::
+        ModuleTarget("Top", "Bar").instOf("fizz", "Fizz") ::
+        Nil
+    unfoldInstanceTargets(input) should be(expected)
+  }
+}