Make InstanceGraph have deterministic and use defined iteration order (#843)

3 files changed, 78 insertions, 10 deletions

diff --git a/src/main/scala/firrtl/analyses/InstanceGraph.scala b/src/main/scala/firrtl/analyses/InstanceGraph.scala
index 91cf8d44..6eb67938 100644
--- a/src/main/scala/firrtl/analyses/InstanceGraph.scala
+++ b/src/main/scala/firrtl/analyses/InstanceGraph.scala
@@ -19,20 +19,19 @@ import firrtl.Mappers._
 class InstanceGraph(c: Circuit) {
 
   val moduleMap = c.modules.map({m => (m.name,m) }).toMap
-  private val instantiated = new mutable.HashSet[String]
+  private val instantiated = new mutable.LinkedHashSet[String]
   private val childInstances =
-    new mutable.HashMap[String,mutable.Set[WDefInstance]]
+    new mutable.LinkedHashMap[String, mutable.LinkedHashSet[WDefInstance]]
   for (m <- c.modules) {
-    childInstances(m.name) = new mutable.HashSet[WDefInstance]
+    childInstances(m.name) = new mutable.LinkedHashSet[WDefInstance]
     m map InstanceGraph.collectInstances(childInstances(m.name))
     instantiated ++= childInstances(m.name).map(i => i.module)
   }
 
-  private val uninstantiated = moduleMap.keySet -- instantiated
   private val instanceGraph = new MutableDiGraph[WDefInstance]
   private val instanceQueue = new mutable.Queue[WDefInstance]
 
-  uninstantiated.foreach({ subTop =>
+  for (subTop <- c.modules.view.map(_.name).filterNot(instantiated)) {
     val topInstance = WDefInstance(subTop,subTop)
     instanceQueue.enqueue(topInstance)
     while (instanceQueue.nonEmpty) {
@@ -46,7 +45,7 @@ class InstanceGraph(c: Circuit) {
         instanceGraph.addEdge(current,child)
       }
     }
-  })
+  }
 
   // The true top module (circuit main)
   private val trueTopInstance = WDefInstance(c.main, c.main)
@@ -61,7 +60,7 @@ class InstanceGraph(c: Circuit) {
   /** A list of absolute paths (each represented by a Seq of instances)
     * of all module instances in the Circuit.
     */
-  lazy val fullHierarchy: collection.Map[WDefInstance,Seq[Seq[WDefInstance]]] = graph.pathsInDAG(trueTopInstance)
+  lazy val fullHierarchy: mutable.LinkedHashMap[WDefInstance,Seq[Seq[WDefInstance]]] = graph.pathsInDAG(trueTopInstance)
 
   /** Finds the absolute paths (each represented by a Seq of instances
     * representing the chain of hierarchy) of all instances of a
@@ -94,11 +93,11 @@ class InstanceGraph(c: Circuit) {
     graph.transformNodes(_.module).linearize.map(moduleMap(_))
   }
 
-  
+
   /** Given a circuit, returns a map from module name to children
      * instance/module definitions
      */
-  def getChildrenInstances: scala.collection.Map[String,mutable.Set[WDefInstance]] = childInstances 
+  def getChildrenInstances: mutable.LinkedHashMap[String, mutable.LinkedHashSet[WDefInstance]] = childInstances
 
 
 }
diff --git a/src/main/scala/firrtl/graph/DiGraph.scala b/src/main/scala/firrtl/graph/DiGraph.scala
index 4b900be4..1d15d505 100644
--- a/src/main/scala/firrtl/graph/DiGraph.scala
+++ b/src/main/scala/firrtl/graph/DiGraph.scala
@@ -263,7 +263,7 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     * @param start the node to start at
     * @return a Map[T,Seq[Seq[T]]] where the value associated with v is the Seq of all paths from start to v
     */
-  def pathsInDAG(start: T): Map[T,Seq[Seq[T]]] = {
+  def pathsInDAG(start: T): LinkedHashMap[T,Seq[Seq[T]]] = {
     // paths(v) holds the set of paths from start to v
     val paths = new LinkedHashMap[T, mutable.Set[Seq[T]]]
     val queue = new mutable.Queue[T]
diff --git a/src/test/scala/firrtlTests/analyses/InstanceGraphTests.scala b/src/test/scala/firrtlTests/analyses/InstanceGraphTests.scala
index f01de1f4..e98c1895 100644
--- a/src/test/scala/firrtlTests/analyses/InstanceGraphTests.scala
+++ b/src/test/scala/firrtlTests/analyses/InstanceGraphTests.scala
@@ -15,6 +15,8 @@ class InstanceGraphTests extends FirrtlFlatSpec {
     (graph.getVertices map {v => (v, graph.getEdges(v))}).toMap
   }
 
+  behavior of "InstanceGraph"
+
   it should "recognize a simple hierarchy" in {
     val input = """
 circuit Top :
@@ -95,4 +97,71 @@ circuit Top :
     //   (f1, Fizz) -> (f, Foo) and (f2, Fizz) -> (b, Bar)
     g2.getEdges("Fizz") shouldBe Set("Foo", "Bar")
   }
+
+  // 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 = ToWorkingIR.run(parse(input))
+    val instGraph = new InstanceGraph(circuit)
+    val childMap = instGraph.getChildrenInstances
+    childMap.keys.toSeq 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 = ToWorkingIR.run(parse(input))
+    val instGraph = new InstanceGraph(circuit)
+    val childMap = instGraph.getChildrenInstances
+    val insts = childMap("Top").toSeq.map(_.name)
+    insts should equal (Seq("a", "b", "c", "d", "e", "f"))
+  }
+
+  // Note that due to optimized implementations of Map1-4, at least 5 entries are needed to
+  // experience non-determinism
+  it should "have defined fullHierarchy 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
+      |  module Child :
+      |    skip
+      |""".stripMargin
+    val circuit = ToWorkingIR.run(parse(input))
+    val instGraph = new InstanceGraph(circuit)
+    val hier = instGraph.fullHierarchy
+    hier.keys.toSeq.map(_.name) should equal (Seq("Top", "a", "b", "c", "d", "e"))
+  }
 }