Faster dedup instance graph (#1732)

* dedup: add faster InstanceGraph implementation and use it in dedup

The new implementation takes care not to hash the instance
types contained in DefInstance nodes.
This should make dedup considerably faster.

* FastInstanceGraph: cache vertices for faster findInstancesInHierarchy

* FastInstanceGraph: remove the parent name field since it isn't actually necessary

* FastInstanceGraph -> InstanceKeyGraph

* InstanceGraph: describe performance problems.

* InstanceKeyGraph: turn moduleMap into a def instead of a val

This will make changing implementation details much easier
in the future.

* InstanceKeyGraph: return childInstances as Seq instead of Map

This ensures a deterministic iteration order and it
can easily be turned into a Map for O(1) accesses.

* InstanceKeyGraph: add tests for public methods

* InstanceKeyGraph: group public methods together

* InstanceKeyGraphSpec: fix wording of a comment

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

1 files changed, 124 insertions, 0 deletions

diff --git a/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala b/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala
new file mode 100644
index 00000000..8d073ecb
--- /dev/null
+++ b/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala
@@ -0,0 +1,124 @@
+// See LICENSE for license details.
+
+package firrtlTests.analyses
+
+import firrtl.analyses.InstanceKeyGraph
+import firrtl.analyses.InstanceKeyGraph.InstanceKey
+import firrtl.testutils.FirrtlFlatSpec
+
+class InstanceKeyGraphSpec extends FirrtlFlatSpec {
+  behavior of "InstanceKeyGraph"
+
+  // Note that due to optimized implementations of Map1-4, at least 5 entries are needed to
+  // experience non-determinism
+  it should "preserve Module declaration order" in {
+    val input = """
+                  |circuit Top :
+                  |  module Top :
+                  |    inst c1 of Child1
+                  |    inst c2 of Child2
+                  |  module Child1 :
+                  |    inst a of Child1a
+                  |    inst b of Child1b
+                  |    skip
+                  |  module Child1a :
+                  |    skip
+                  |  module Child1b :
+                  |    skip
+                  |  module Child2 :
+                  |    skip
+                  |""".stripMargin
+    val circuit = parse(input)
+    val instGraph = new InstanceKeyGraph(circuit)
+    val childMap = instGraph.getChildInstances
+    childMap.map(_._1) should equal (Seq("Top", "Child1", "Child1a", "Child1b", "Child2"))
+  }
+
+  // Note that due to optimized implementations of Map1-4, at least 5 entries are needed to
+  // experience non-determinism
+  it should "preserve Instance declaration order" in {
+    val input = """
+                  |circuit Top :
+                  |  module Top :
+                  |    inst a of Child
+                  |    inst b of Child
+                  |    inst c of Child
+                  |    inst d of Child
+                  |    inst e of Child
+                  |    inst f of Child
+                  |  module Child :
+                  |    skip
+                  |""".stripMargin
+    val circuit = parse(input)
+    val instGraph = new InstanceKeyGraph(circuit)
+    val childMap = instGraph.getChildInstances.toMap
+    val insts = childMap("Top").map(_.name)
+    insts should equal (Seq("a", "b", "c", "d", "e", "f"))
+  }
+
+  it should "compute a correct and deterministic module order" in {
+    val input = """
+                  |circuit Top :
+                  |  module Top :
+                  |    inst c1 of Child1
+                  |    inst c2 of Child2
+                  |    inst c4 of Child4
+                  |    inst c3 of Child3
+                  |  module Child1 :
+                  |    inst a of Child1a
+                  |    inst b of Child1b
+                  |    skip
+                  |  module Child1a :
+                  |    skip
+                  |  module Child1b :
+                  |    skip
+                  |  module Child2 :
+                  |    skip
+                  |  module Child3 :
+                  |    skip
+                  |  module Child4 :
+                  |    skip
+                  |""".stripMargin
+    val circuit = parse(input)
+    val instGraph = new InstanceKeyGraph(circuit)
+    val order = instGraph.moduleOrder.map(_.name)
+    // Where it has freedom, the instance declaration order will be reversed.
+    order should equal (Seq("Top", "Child3", "Child4", "Child2", "Child1", "Child1b", "Child1a"))
+  }
+
+  it should "find hierarchical instances correctly in disconnected hierarchies" in {
+    val input =
+      """circuit Top :
+        |  module Top :
+        |    inst c of Child1
+        |  module Child1 :
+        |    skip
+        |
+        |  module Top2 :
+        |    inst a of Child2
+        |    inst b of Child3
+        |    skip
+        |  module Child2 :
+        |    inst a of Child2a
+        |    inst b of Child2b
+        |    skip
+        |  module Child2a :
+        |    skip
+        |  module Child2b :
+        |    skip
+        |  module Child3 :
+        |    skip
+        |""".stripMargin
+
+    val circuit = parse(input)
+    val iGraph = new InstanceKeyGraph(circuit)
+    iGraph.findInstancesInHierarchy("Top") shouldBe Seq(Seq(InstanceKey("Top", "Top")))
+    iGraph.findInstancesInHierarchy("Child1") shouldBe Seq(Seq(InstanceKey("Top", "Top"), InstanceKey("c", "Child1")))
+    iGraph.findInstancesInHierarchy("Top2") shouldBe Nil
+    iGraph.findInstancesInHierarchy("Child2") shouldBe Nil
+    iGraph.findInstancesInHierarchy("Child2a") shouldBe Nil
+    iGraph.findInstancesInHierarchy("Child2b") shouldBe Nil
+    iGraph.findInstancesInHierarchy("Child3") shouldBe Nil
+  }
+
+}