Deprecate InstanceGraph (#1800)

* InstanceKeyGraph: add staticInstanceCount, getGraph and getChildrenInstanceMap

* InstanceKeyGraph: reachableModules, unreachableModules, lowestCommonAncestor and fullHierarchy

* Replace usage of InstanceGraph with InstanceKeyGraph

Also deprecates all unused methods.

* WiringUtils: make new version of sinksToSources package private

This will make our live easier next time we need to change it.

* CircuitGraph: use InstanceKeyGraph

* InstanceKeyGraphSpec: respect maximum line width

* InstanceKeyGraph: make constructor private

* InstanceKeyGraph: move lowestCommonAncestor function to Wiring

* WiringUtils: update deprecation message

15 files changed, 439 insertions, 74 deletions

diff --git a/src/main/scala/firrtl/analyses/CircuitGraph.scala b/src/main/scala/firrtl/analyses/CircuitGraph.scala
index 426fd012..506bba57 100644
--- a/src/main/scala/firrtl/analyses/CircuitGraph.scala
+++ b/src/main/scala/firrtl/analyses/CircuitGraph.scala
@@ -3,6 +3,7 @@
 package firrtl.analyses
 
 import firrtl.Kind
+import firrtl.analyses.InstanceKeyGraph.InstanceKey
 import firrtl.annotations.TargetToken.{Instance, OfModule}
 import firrtl.annotations._
 import firrtl.ir.{Circuit, DefInstance}
@@ -48,10 +49,10 @@ class CircuitGraph private[analyses] (connectionGraph: ConnectionGraph) {
   private val irLookup = connectionGraph.irLookup
 
   // Module/Instance Hierarchy information
-  private lazy val instanceGraph = new InstanceGraph(circuit)
+  private lazy val instanceGraph = InstanceKeyGraph(circuit)
 
   // Per module, which modules does it instantiate
-  private lazy val moduleChildren = instanceGraph.getChildrenInstanceOfModule
+  private lazy val moduleChildren = instanceGraph.getChildInstances.toMap
 
   // Top-level module target
   private val main = ModuleTarget(circuit.main, circuit.main)
@@ -80,7 +81,7 @@ class CircuitGraph private[analyses] (connectionGraph: ConnectionGraph) {
     */
   def absolutePaths(mt: ModuleTarget): Seq[IsModule] = instanceGraph.findInstancesInHierarchy(mt.module).map {
     case seq if seq.nonEmpty => seq.foldLeft(CircuitTarget(circuit.main).module(circuit.main): IsModule) {
-      case (it, DefInstance(_, instance, ofModule, _)) => it.instOf(instance, ofModule)
+      case (it, InstanceKey(instance, ofModule)) => it.instOf(instance, ofModule)
     }
   }
 
@@ -113,9 +114,7 @@ class CircuitGraph private[analyses] (connectionGraph: ConnectionGraph) {
     val leafModule = path.leafModule
     val children = moduleChildren(leafModule)
     val localRefs = localReferences(path, kind)
-    localRefs ++ children.flatMap {
-      case (Instance(inst), OfModule(ofModule)) => deepReferences(kind, path.instOf(inst, ofModule))
-    }
+    localRefs ++ children.flatMap { child => deepReferences(kind, path.instOf(child.name, child.module)) }
   }
 
   /** Return all absolute references to signals of the given kind directly contained in the module
diff --git a/src/main/scala/firrtl/analyses/InstanceGraph.scala b/src/main/scala/firrtl/analyses/InstanceGraph.scala
index c0aec4aa..f994b39a 100644
--- a/src/main/scala/firrtl/analyses/InstanceGraph.scala
+++ b/src/main/scala/firrtl/analyses/InstanceGraph.scala
@@ -25,8 +25,10 @@ import firrtl.annotations.TargetToken._
   *       Hashing and comparing deep bundle types however is inefficient which can manifest in slower then necessary
   *       lookups and insertions.
   */
+@deprecated("Use InstanceKeyGraph instead.", "FIRRTL 1.4")
 class InstanceGraph(c: Circuit) {
 
+  @deprecated("Use InstanceKeyGraph.moduleMap instead.", "FIRRTL 1.4")
   val moduleMap = c.modules.map({m => (m.name,m) }).toMap
   private val instantiated = new mutable.LinkedHashSet[String]
   private val childInstances =
@@ -64,11 +66,13 @@ class InstanceGraph(c: Circuit) {
     * every DefInstance arising from every instance statement in
     * that module.
     */
+  @deprecated("Use InstanceKeyGraph.graph instead.", "FIRRTL 1.4")
   lazy val graph = DiGraph(instanceGraph)
 
   /** A list of absolute paths (each represented by a Seq of instances)
     * of all module instances in the Circuit.
     */
+  @deprecated("Use InstanceKeyGraph.fullHierarchy instead.", "FIRRTL 1.4")
   lazy val fullHierarchy: mutable.LinkedHashMap[DefInstance,Seq[Seq[DefInstance]]] = graph.pathsInDAG(trueTopInstance)
 
   /** A count of the *static* number of instances of each module. For any module other than the top (main) module, this is
@@ -77,6 +81,7 @@ class InstanceGraph(c: Circuit) {
     * associated count of one, even though it is never directly instantiated. Any modules *not* instantiated at all will
     * have a count of zero.
     */
+  @deprecated("Use InstanceKeyGraph.staticInstanceCount instead.", "FIRRTL 1.4")
   lazy val staticInstanceCount: Map[OfModule, Int] = {
     val foo = mutable.LinkedHashMap.empty[OfModule, Int]
     childInstances.keys.foreach {
@@ -98,17 +103,20 @@ class InstanceGraph(c: Circuit) {
     * @param module the name of the selected module
     * @return a Seq[ Seq[DefInstance] ] of absolute instance paths
     */
+  @deprecated("Use InstanceKeyGraph.findInstancesInHierarchy instead (now with caching of vertices!).", "FIRRTL 1.4")
   def findInstancesInHierarchy(module: String): Seq[Seq[DefInstance]] = {
     val instances = graph.getVertices.filter(_.module == module).toSeq
     instances flatMap { i => fullHierarchy.getOrElse(i, Nil) }
   }
 
   /** An [[firrtl.graph.EulerTour EulerTour]] representation of the [[firrtl.graph.DiGraph DiGraph]] */
+  @deprecated("Should have been private. Do not use outside of InstanceGraph.", "FIRRTL 1.4")
   lazy val tour = EulerTour(graph, trueTopInstance)
 
   /** Finds the lowest common ancestor instances for two module names in
     * a design
     */
+  @deprecated("Use InstanceKeyGraph and EulerTour(iGraph.graph, iGraph.top).rmq(moduleA, moduleB).", "FIRRTL 1.4")
   def lowestCommonAncestor(moduleA: Seq[DefInstance],
                            moduleB: Seq[DefInstance]): Seq[DefInstance] = {
     tour.rmq(moduleA, moduleB)
@@ -118,6 +126,7 @@ class InstanceGraph(c: Circuit) {
     * Module order from highest module to leaf module
     * @return sequence of modules in order from top to leaf
     */
+  @deprecated("Use InstanceKeyGraph.moduleOrder instead.", "FIRRTL 1.4")
   def moduleOrder: Seq[DefModule] = {
     graph.transformNodes(_.module).linearize.map(moduleMap(_))
   }
@@ -126,11 +135,13 @@ class InstanceGraph(c: Circuit) {
   /** Given a circuit, returns a map from module name to children
      * instance/module definitions
      */
+  @deprecated("Use InstanceKeyGraph.getChildInstances instead.", "FIRRTL 1.4")
   def getChildrenInstances: mutable.LinkedHashMap[String, mutable.LinkedHashSet[DefInstance]] = childInstances
 
   /** Given a circuit, returns a map from module name to children
     * instance/module [[firrtl.annotations.TargetToken]]s
     */
+  @deprecated("Use InstanceKeyGraph.getChildInstances instead.", "FIRRTL 1.4")
   def getChildrenInstanceOfModule: mutable.LinkedHashMap[String, mutable.LinkedHashSet[(Instance, OfModule)]] =
     childInstances.map(kv => kv._1 -> kv._2.map(_.toTokens))
 
@@ -146,21 +157,26 @@ class InstanceGraph(c: Circuit) {
   /** Given a circuit, returns a map from module name to a map
     * in turn mapping instances names to corresponding module names
     */
+  @deprecated("Use InstanceKeyGraph.getChildInstanceMap instead.", "FIRRTL 1.4")
   def getChildrenInstanceMap: collection.Map[OfModule, collection.Map[Instance, OfModule]] =
     childInstances.map(kv => kv._1.OfModule -> asOrderedMap(kv._2, (i: DefInstance) => i.toTokens))
 
   /** The set of all modules in the circuit */
+  @deprecated("Use InstanceKeyGraph instead.", "FIRRTL 1.4")
   lazy val modules: collection.Set[OfModule] = graph.getVertices.map(_.OfModule)
 
   /** The set of all modules in the circuit reachable from the top module */
+  @deprecated("Use InstanceKeyGraph instead.", "FIRRTL 1.4")
   lazy val reachableModules: collection.Set[OfModule] =
     mutable.LinkedHashSet(trueTopInstance.OfModule) ++ graph.reachableFrom(trueTopInstance).map(_.OfModule)
 
   /** The set of all modules *not* reachable in the circuit */
+  @deprecated("Use InstanceKeyGraph.unreachableModules instead.", "FIRRTL 1.4")
   lazy val unreachableModules: collection.Set[OfModule] = modules diff reachableModules
 
 }
 
+@deprecated("Use InstanceKeyGraph instead.", "FIRRTL 1.4")
 object InstanceGraph {
 
   /** Returns all DefInstances in a Statement
@@ -169,6 +185,7 @@ object InstanceGraph {
     * @param s statement to descend
     * @return
     */
+  @deprecated("Use InstanceKeyGraph.collectInstances instead.", "FIRRTL 1.4")
   def collectInstances(insts: mutable.Set[DefInstance])
                       (s: Statement): Unit = s match {
     case i: DefInstance => insts += i
diff --git a/src/main/scala/firrtl/analyses/InstanceKeyGraph.scala b/src/main/scala/firrtl/analyses/InstanceKeyGraph.scala
index 49b91788..761315dc 100644
--- a/src/main/scala/firrtl/analyses/InstanceKeyGraph.scala
+++ b/src/main/scala/firrtl/analyses/InstanceKeyGraph.scala
@@ -4,7 +4,7 @@ package firrtl.analyses
 
 import firrtl.annotations._
 import firrtl.annotations.TargetToken._
-import firrtl.graph.{DiGraph, MutableDiGraph}
+import firrtl.graph.{DiGraph, EulerTour, MutableDiGraph}
 import firrtl.ir
 
 import scala.collection.mutable
@@ -14,7 +14,7 @@ import scala.collection.mutable
   * pairs of InstanceName and Module name as vertex keys instead of using WDefInstance
   * which will hash the instance type causing some performance issues.
   */
-class InstanceKeyGraph(c: ir.Circuit) {
+class InstanceKeyGraph private(c: ir.Circuit) {
   import InstanceKeyGraph._
 
   private val nameToModule: Map[String, ir.DefModule] = c.modules.map({m => (m.name,m) }).toMap
@@ -23,24 +23,60 @@ class InstanceKeyGraph(c: ir.Circuit) {
   }
   private val instantiated = childInstances.flatMap(_._2).map(_.module).toSet
   private val roots = c.modules.map(_.name).filterNot(instantiated)
-  private val graph = buildGraph(childInstances, roots)
+  private val internalGraph = buildGraph(childInstances, roots)
   private val circuitTopInstance = topKey(c.main)
   // cache vertices to speed up repeat calls to findInstancesInHierarchy
-  private lazy val vertices = graph.getVertices
+  private lazy val vertices = internalGraph.getVertices
 
   /** A list of absolute paths (each represented by a Seq of instances) of all module instances in the Circuit. */
-  private lazy val fullHierarchy: mutable.LinkedHashMap[InstanceKey, Seq[Seq[InstanceKey]]] =
-    graph.pathsInDAG(circuitTopInstance)
+  private lazy val cachedFullHierarchy: mutable.LinkedHashMap[InstanceKey, Seq[Seq[InstanceKey]]] =
+    internalGraph.pathsInDAG(circuitTopInstance)
+
+  /** modules reachable from the main module as well as the main modules itself */
+  private lazy val cachedReachableModules: Seq[OfModule] =
+    circuitTopInstance.OfModule +: internalGraph.reachableFrom(circuitTopInstance).toSeq.map(_.OfModule)
+
+  private lazy val cachedUnreachableModules: Seq[OfModule] = {
+    val all = mutable.LinkedHashSet(childInstances.map(c => OfModule(c._1)):_*)
+    val reachable = mutable.LinkedHashSet(cachedReachableModules:_*)
+    all.diff(reachable).toSeq
+  }
+
+  /** returns the underlying graph */
+  def graph: DiGraph[InstanceKey] = internalGraph
+
+  /** returns the key to the top (main) module */
+  def top: InstanceKey = circuitTopInstance
 
   /** maps module names to the DefModule node */
   def moduleMap: Map[String, ir.DefModule] = nameToModule
 
   /** Module order from highest module to leaf module */
-  def moduleOrder: Seq[ir.DefModule] = graph.transformNodes(_.module).linearize.map(nameToModule(_))
+  def moduleOrder: Seq[ir.DefModule] = internalGraph.transformNodes(_.module).linearize.map(nameToModule(_))
 
   /** Returns a sequence that can be turned into a map from module name to instances defined in said module. */
   def getChildInstances: Seq[(String, Seq[InstanceKey])] = childInstances
 
+  /** A count of the *static* number of instances of each module. For any module other than the top (main) module,
+    * this is equivalent to the number of inst statements in the circuit instantiating each module,
+    * irrespective of the number of times (if any) the enclosing module appears in the hierarchy.
+    * Note that top module of the circuit has an associated count of one, even though it is never directly instantiated.
+    * Any modules *not* instantiated at all will have a count of zero.
+    */
+  def staticInstanceCount: Map[OfModule, Int] = cachedStaticInstanceCount
+
+  private lazy val cachedStaticInstanceCount = {
+    val foo = mutable.LinkedHashMap.empty[OfModule, Int]
+    childInstances.foreach {
+      case (main, _) if main == c.main => foo += main.OfModule  -> 1
+      case (other, _)                  => foo += other.OfModule -> 0
+    }
+    childInstances.flatMap(_._2).map(_.OfModule).foreach {
+      mod => foo += mod -> (foo(mod) + 1)
+    }
+    foo.toMap
+  }
+
   /** Finds the absolute paths (each represented by a Seq of instances
     * representing the chain of hierarchy) of all instances of a particular
     * module. Note that this includes one implicit instance of the top (main)
@@ -52,12 +88,32 @@ class InstanceKeyGraph(c: ir.Circuit) {
     */
   def findInstancesInHierarchy(module: String): Seq[Seq[InstanceKey]] = {
     val instances = vertices.filter(_.module == module).toSeq
-    instances.flatMap{ i => fullHierarchy.getOrElse(i, Nil) }
+    instances.flatMap{ i => cachedFullHierarchy.getOrElse(i, Nil) }
   }
+
+  /** Given a circuit, returns a map from module name to a map
+    * in turn mapping instances names to corresponding module names
+    */
+  def getChildInstanceMap: mutable.LinkedHashMap[OfModule, mutable.LinkedHashMap[Instance, OfModule]] =
+    mutable.LinkedHashMap(childInstances.map { case (k, v) =>
+      val moduleMap: mutable.LinkedHashMap[Instance, OfModule] = mutable.LinkedHashMap(v.map(_.toTokens):_*)
+      TargetToken.OfModule(k) -> moduleMap
+    }:_*)
+
+  /** All modules in the circuit reachable from the top module */
+  def reachableModules: Seq[OfModule] = cachedReachableModules
+
+  /** All modules *not* reachable from the top module of the circuit */
+  def unreachableModules: Seq[OfModule] = cachedUnreachableModules
+
+  /** A list of absolute paths (each represented by a Seq of instances) of all module instances in the Circuit. */
+  def fullHierarchy: mutable.LinkedHashMap[InstanceKey, Seq[Seq[InstanceKey]]] = cachedFullHierarchy
 }
 
 
 object InstanceKeyGraph {
+  def apply(c: ir.Circuit): InstanceKeyGraph = new InstanceKeyGraph(c)
+
   /** We want to only use this untyped version as key because hashing bundle types is expensive
     * @param name the name of the instance
     * @param module the name of the module that is instantiated
diff --git a/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala b/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala
index 402f7028..d92d3b5e 100644
--- a/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala
+++ b/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala
@@ -3,7 +3,7 @@
 package firrtl.annotations.transforms
 
 import firrtl.Mappers._
-import firrtl.analyses.InstanceGraph
+import firrtl.analyses.InstanceKeyGraph
 import firrtl.annotations.ModuleTarget
 import firrtl.annotations.TargetToken.{Instance, OfModule, fromDefModuleToTargetToken}
 import firrtl.annotations.analysis.DuplicationHelper
@@ -132,7 +132,7 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration {
     */
   def run(cir: Circuit,
           targets: Seq[IsMember],
-          iGraph: InstanceGraph
+          iGraph: InstanceKeyGraph
          ): (Circuit, RenameMap, AnnotationSeq) = {
 
     val dupMap = DuplicationHelper(cir.modules.map(_.name).toSet)
@@ -239,8 +239,8 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration {
     val targets = targetsToEliminate.collect { case x: IsMember => x }
 
     // Check validity of paths in targets
-    val iGraph = new InstanceGraph(state.circuit)
-    val instanceOfModules = iGraph.getChildrenInstanceOfModule
+    val iGraph = InstanceKeyGraph(state.circuit)
+    val instanceOfModules = iGraph.getChildInstances.map { case(k,v) => k -> v.map(_.toTokens) }.toMap
     val targetsWithInvalidPaths = mutable.ArrayBuffer[IsMember]()
     targets.foreach { t =>
       val path = t match {
@@ -311,8 +311,8 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration {
         nextRenameMap
       }
 
-    val iGraphx = new InstanceGraph(newCircuit)
-    val newlyUnreachableModules = iGraphx.unreachableModules diff iGraph.unreachableModules
+    val iGraphx = InstanceKeyGraph(newCircuit)
+    val newlyUnreachableModules = iGraphx.unreachableModules.toSet diff iGraph.unreachableModules.toSet
 
     val newCircuitGC = {
       val modulesx = newCircuit.modules.flatMap{
diff --git a/src/main/scala/firrtl/passes/Inline.scala b/src/main/scala/firrtl/passes/Inline.scala
index 39cb4b9c..ad963b19 100644
--- a/src/main/scala/firrtl/passes/Inline.scala
+++ b/src/main/scala/firrtl/passes/Inline.scala
@@ -7,7 +7,7 @@ import firrtl.ir._
 import firrtl.Mappers._
 import firrtl.annotations._
 import firrtl.annotations.TargetToken.{Instance, OfModule}
-import firrtl.analyses.{InstanceGraph}
+import firrtl.analyses.InstanceKeyGraph
 import firrtl.graph.{DiGraph, MutableDiGraph}
 import firrtl.stage.{Forms, RunFirrtlTransformAnnotation}
 import firrtl.options.{RegisteredTransform, ShellOption}
@@ -80,7 +80,7 @@ class InlineInstances extends Transform with DependencyAPIMigration with Registe
    // 3) All annotated instances exist, and their modules can be inline
    def check(c: Circuit, moduleNames: Set[ModuleName], instanceNames: Set[ComponentName]): Unit = {
       val errors = mutable.ArrayBuffer[PassException]()
-      val moduleMap = new InstanceGraph(c).moduleMap
+      val moduleMap = InstanceKeyGraph(c).moduleMap
       def checkExists(name: String): Unit =
          if (!moduleMap.contains(name))
             errors += new PassException(s"Annotated module does not exist: $name")
@@ -136,10 +136,10 @@ class InlineInstances extends Transform with DependencyAPIMigration with Registe
     check(c, modsToInline, instsToInline)
     val flatModules = modsToInline.map(m => m.name)
     val flatInstances: Set[(OfModule, Instance)] = instsToInline.map(i => OfModule(i.module.name) -> Instance(i.name)) ++ getInstancesOf(c, flatModules)
-    val iGraph = new InstanceGraph(c)
+    val iGraph = InstanceKeyGraph(c)
     val namespaceMap = collection.mutable.Map[String, Namespace]()
     // Map of Module name to Map of instance name to Module name
-    val instMaps = iGraph.getChildrenInstanceMap
+    val instMaps = iGraph.getChildInstanceMap
 
     /** Add a prefix to all declarations updating a [[Namespace]] and appending to a [[RenameMap]] */
     def appendNamePrefix(
diff --git a/src/main/scala/firrtl/passes/wiring/Wiring.scala b/src/main/scala/firrtl/passes/wiring/Wiring.scala
index c62a565e..3f74e5d2 100644
--- a/src/main/scala/firrtl/passes/wiring/Wiring.scala
+++ b/src/main/scala/firrtl/passes/wiring/Wiring.scala
@@ -5,11 +5,14 @@ package wiring
 
 import firrtl._
 import firrtl.ir._
+
 import scala.collection.mutable
 import firrtl.annotations._
 import firrtl.annotations.AnnotationUtils._
-import firrtl.analyses.InstanceGraph
+import firrtl.analyses.InstanceKeyGraph
 import WiringUtils._
+import firrtl.analyses.InstanceKeyGraph.InstanceKey
+import firrtl.graph.EulerTour
 
 /** A data store of one sink--source wiring relationship */
 case class WiringInfo(source: ComponentName, sinks: Seq[Named], pin: String)
@@ -47,7 +50,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass {
            else ns.newName(tokenize(c) filterNot ("[]." contains _) mkString "_")
          })}}
 
-    val iGraph = new InstanceGraph(c)
+    val iGraph = InstanceKeyGraph(c)
     names.zip(portNames).map{ case(WiringNames(comp, so, si, _), pn) =>
       computeModifications(c, iGraph, comp, so, si, pn) }
   }
@@ -67,7 +70,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass {
     * to pending modifications
     */
   private def computeModifications(c: Circuit,
-                                   iGraph: InstanceGraph,
+                                   iGraph: InstanceKeyGraph,
                                    compName: String,
                                    source: String,
                                    sinks: Seq[Named],
@@ -94,12 +97,17 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass {
     def makeWireC(m: Modifications, portName: String, c: (String, String)): Modifications =
       m.copy(addPortOrWire = Some(m.addPortOrWire.getOrElse((portName, DecWire))), cons = (m.cons :+ c).distinct )
 
+    val tour = EulerTour(iGraph.graph, iGraph.top)
+    // Finds the lowest common ancestor instances for two module names in a design
+    def lowestCommonAncestor(moduleA: Seq[InstanceKey], moduleB: Seq[InstanceKey]): Seq[InstanceKey] =
+      tour.rmq(moduleA, moduleB)
+
     owners.foreach { case (sink, source) =>
-      val lca = iGraph.lowestCommonAncestor(sink, source)
+      val lca = lowestCommonAncestor(sink, source)
 
       // Compute metadata along Sink to LCA paths.
       sink.drop(lca.size - 1).sliding(2).toList.reverse.foreach {
-        case Seq(WDefInstance(_,_,pm,_), WDefInstance(_,ci,cm,_)) =>
+        case Seq(InstanceKey(_,pm), InstanceKey(ci,cm)) =>
           val to = s"$ci.${portNames(cm)}"
           val from = s"${portNames(pm)}"
           meta(pm) = makeWireC(meta(pm), portNames(pm), (to, from))
@@ -107,12 +115,12 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass {
             addPortOrWire = Some((portNames(cm), DecInput))
           )
         // Case where the sink is the LCA
-        case Seq(WDefInstance(_,_,pm,_)) =>
+        case Seq(InstanceKey(_,pm)) =>
           // Case where the source is also the LCA
           if (source.drop(lca.size).isEmpty) {
             meta(pm) = makeWire(meta(pm), portNames(pm))
           } else {
-            val WDefInstance(_,ci,cm,_) = source.drop(lca.size).head
+            val InstanceKey(ci,cm) = source.drop(lca.size).head
             val to = s"${portNames(pm)}"
             val from = s"$ci.${portNames(cm)}"
             meta(pm) = makeWireC(meta(pm), portNames(pm), (to, from))
@@ -120,7 +128,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass {
       }
 
       // Compute metadata for the Sink
-      sink.last match { case WDefInstance(_, _, m, _) =>
+      sink.last match { case InstanceKey( _, m) =>
         if (sinkComponents.contains(m)) {
           val from = s"${portNames(m)}"
           sinkComponents(m).foreach( to =>
@@ -132,7 +140,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass {
       }
 
       // Compute metadata for the Source
-      source.last match { case WDefInstance(_, _, m, _) =>
+      source.last match { case InstanceKey( _, m) =>
         val to = s"${portNames(m)}"
         val from = compName
         meta(m) = meta(m).copy(
@@ -142,7 +150,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass {
 
       // Compute metadata along Source to LCA path
       source.drop(lca.size - 1).sliding(2).toList.reverse.map {
-        case Seq(WDefInstance(_,_,pm,_), WDefInstance(_,ci,cm,_)) => {
+        case Seq(InstanceKey(_,pm), InstanceKey(ci,cm)) => {
           val to = s"${portNames(pm)}"
           val from = s"$ci.${portNames(cm)}"
           meta(pm) = meta(pm).copy(
@@ -153,12 +161,12 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass {
           )
         }
         // Case where the source is the LCA
-        case Seq(WDefInstance(_,_,pm,_)) => {
+        case Seq(InstanceKey(_,pm)) => {
           // Case where the sink is also the LCA. We do nothing here,
           // as we've created the connecting wire above
           if (sink.drop(lca.size).isEmpty) {
           } else {
-            val WDefInstance(_,ci,cm,_) = sink.drop(lca.size).head
+            val InstanceKey(ci,cm) = sink.drop(lca.size).head
             val to = s"$ci.${portNames(cm)}"
             val from = s"${portNames(pm)}"
             meta(pm) = meta(pm).copy(
diff --git a/src/main/scala/firrtl/passes/wiring/WiringUtils.scala b/src/main/scala/firrtl/passes/wiring/WiringUtils.scala
index 5f09bbe0..c220692a 100644
--- a/src/main/scala/firrtl/passes/wiring/WiringUtils.scala
+++ b/src/main/scala/firrtl/passes/wiring/WiringUtils.scala
@@ -7,11 +7,13 @@ import firrtl._
 import firrtl.ir._
 import firrtl.Utils._
 import firrtl.Mappers._
+import firrtl.analyses.InstanceKeyGraph.InstanceKey
 import firrtl.traversals.Foreachers._
+
 import scala.collection.mutable
 import firrtl.annotations._
 import firrtl.annotations.AnnotationUtils._
-import firrtl.analyses.InstanceGraph
+import firrtl.analyses.{InstanceGraph, InstanceKeyGraph}
 
 /** Declaration kind in lineage (e.g. input port, output port, wire)
   */
@@ -112,9 +114,66 @@ object WiringUtils {
     * @return a map of sink instance names to source instance names
     * @throws WiringException if a sink is equidistant to two sources
     */
-  @deprecated("This method can lead to non-determinism in your compiler pass. Use sinksToSourcesSeq instead!", "Firrtl 1.4")
-  def sinksToSources(sinks: Seq[Named], source: String, i: InstanceGraph): Map[Seq[WDefInstance], Seq[WDefInstance]] =
-    sinksToSourcesSeq(sinks, source, i).toMap
+  @deprecated("This method can lead to non-determinism in your compiler pass and exposes internal details." +
+    " Please file an issue with firrtl if you have a use case!", "Firrtl 1.4")
+  def sinksToSources(sinks: Seq[Named], source: String, i: InstanceGraph): Map[Seq[WDefInstance], Seq[WDefInstance]] = {
+    // The order of owners influences the order of the results, it thus needs to be deterministic with a  LinkedHashMap.
+    val owners = new mutable.LinkedHashMap[Seq[WDefInstance], Vector[Seq[WDefInstance]]]
+    val queue = new mutable.Queue[Seq[WDefInstance]]
+    val visited = new mutable.HashMap[Seq[WDefInstance], Boolean].withDefaultValue(false)
+
+    val sourcePaths = i.fullHierarchy.collect { case (k,v) if k.module == source =>  v }
+    sourcePaths.flatten.foreach { l =>
+      queue.enqueue(l)
+      owners(l) = Vector(l)
+    }
+
+    val sinkModuleNames = sinks.map(getModuleName).toSet
+    val sinkPaths = i.fullHierarchy.collect { case (k,v) if sinkModuleNames.contains(k.module) => v }
+    // sinkInsts needs to have unique entries but is also iterated over which is why we use a LinkedHashSet
+    val sinkInsts = mutable.LinkedHashSet() ++ sinkPaths.flatten
+
+    /** If we're lucky and there is only one source, then that source owns
+      * all sinks. If we're unlucky, we need to do a full (slow) BFS
+      * to figure out who owns what. Currently, the BFS is not
+      * performant.
+      *
+      * [todo] The performance of this will need to be improved.
+      * Possible directions are that if we're purely source-under-sink
+      * or sink-under-source, then ownership is trivially a mapping
+      * down/up. Ownership seems to require a BFS if we have
+      * sources/sinks not under sinks/sources.
+      */
+    if (queue.size == 1) {
+      val u = queue.dequeue
+      sinkInsts.foreach { v => owners(v) = Vector(u) }
+    } else {
+      while (queue.nonEmpty) {
+        val u = queue.dequeue
+        visited(u) = true
+
+        val edges = (i.graph.getEdges(u.last).map(u :+ _).toVector :+ u.dropRight(1))
+
+        // [todo] This is the critical section
+        edges
+          .filter( e => !visited(e) && e.nonEmpty )
+          .foreach{ v =>
+            owners(v) = owners.getOrElse(v, Vector()) ++ owners(u)
+            queue.enqueue(v)
+          }
+      }
+
+      // Check that every sink has one unique owner. The only time that
+      // this should fail is if a sink is equidistant to two sources.
+      sinkInsts.foreach { s =>
+        if (!owners.contains(s) || owners(s).size > 1) {
+          throw new WiringException(
+            s"Unable to determine source mapping for sink '${s.map(_.name)}'") }
+      }
+    }
+
+    owners.collect { case (k, v) if sinkInsts.contains(k) => (k, v.flatten) }.toMap
+  }
 
   /** Return a map of sink instances to source instances that minimizes
     * distance
@@ -125,15 +184,12 @@ object WiringUtils {
     * @return a map of sink instance names to source instance names
     * @throws WiringException if a sink is equidistant to two sources
     */
-  def sinksToSourcesSeq(sinks: Seq[Named],
-                     source: String,
-                     i: InstanceGraph):
-      Seq[(Seq[WDefInstance], Seq[WDefInstance])] = {
+  private[firrtl] def sinksToSourcesSeq(sinks: Seq[Named], source: String, i: InstanceKeyGraph):
+      Seq[(Seq[InstanceKey], Seq[InstanceKey])] = {
     // The order of owners influences the order of the results, it thus needs to be deterministic with a  LinkedHashMap.
-    val owners = new mutable.LinkedHashMap[Seq[WDefInstance], Vector[Seq[WDefInstance]]]
-    val queue = new mutable.Queue[Seq[WDefInstance]]
-    val visited = new mutable.HashMap[Seq[WDefInstance], Boolean]
-      .withDefaultValue(false)
+    val owners = new mutable.LinkedHashMap[Seq[InstanceKey], Vector[Seq[InstanceKey]]]
+    val queue = new mutable.Queue[Seq[InstanceKey]]
+    val visited = new mutable.HashMap[Seq[InstanceKey], Boolean].withDefaultValue(false)
 
     val sourcePaths = i.fullHierarchy.collect { case (k,v) if k.module == source =>  v }
     sourcePaths.flatten.foreach { l =>
@@ -165,7 +221,7 @@ object WiringUtils {
         val u = queue.dequeue
         visited(u) = true
 
-        val edges = (i.graph.getEdges(u.last).map(u :+ _).toVector :+ u.dropRight(1))
+        val edges = i.graph.getEdges(u.last).map(u :+ _).toVector :+ u.dropRight(1)
 
         // [todo] This is the critical section
         edges
diff --git a/src/main/scala/firrtl/transforms/CheckCombLoops.scala b/src/main/scala/firrtl/transforms/CheckCombLoops.scala
index dbfd5cf8..6403be23 100644
--- a/src/main/scala/firrtl/transforms/CheckCombLoops.scala
+++ b/src/main/scala/firrtl/transforms/CheckCombLoops.scala
@@ -11,7 +11,7 @@ import firrtl.traversals.Foreachers._
 import firrtl.annotations._
 import firrtl.Utils.throwInternalError
 import firrtl.graph._
-import firrtl.analyses.InstanceGraph
+import firrtl.analyses.InstanceKeyGraph
 import firrtl.options.{Dependency, RegisteredTransform, ShellOption}
 
 /**
@@ -241,7 +241,7 @@ class CheckCombLoops extends Transform
       case ann: Annotation => CircuitTarget(c.main)
     }
     val moduleMap = c.modules.map({m => (m.name,m) }).toMap
-    val iGraph = new InstanceGraph(c).graph
+    val iGraph = InstanceKeyGraph(c).graph
     val moduleDeps = iGraph.getEdgeMap.map({ case (k,v) => (k.module, (v map { i => (i.name, i.module) }).toMap) }).toMap
     val topoSortedModules = iGraph.transformNodes(_.module).linearize.reverse map { moduleMap(_) }
     val moduleGraphs = new mutable.HashMap[String, ConnMap]
diff --git a/src/main/scala/firrtl/transforms/ConstantPropagation.scala b/src/main/scala/firrtl/transforms/ConstantPropagation.scala
index c3c615e0..ce36dd72 100644
--- a/src/main/scala/firrtl/transforms/ConstantPropagation.scala
+++ b/src/main/scala/firrtl/transforms/ConstantPropagation.scala
@@ -11,7 +11,7 @@ import firrtl.Utils._
 import firrtl.Mappers._
 import firrtl.PrimOps._
 import firrtl.graph.DiGraph
-import firrtl.analyses.InstanceGraph
+import firrtl.analyses.InstanceKeyGraph
 import firrtl.annotations.TargetToken.Ref
 import firrtl.options.Dependency
 
@@ -739,8 +739,8 @@ class ConstantPropagation extends Transform with DependencyAPIMigration with Res
 
 
   private def run(c: Circuit, dontTouchMap: Map[OfModule, Set[String]]): Circuit = {
-    val iGraph = new InstanceGraph(c)
-    val moduleDeps = iGraph.getChildrenInstanceMap
+    val iGraph = InstanceKeyGraph(c)
+    val moduleDeps = iGraph.getChildInstanceMap
     val instCount = iGraph.staticInstanceCount
 
     // DiGraph using Module names as nodes, destination of edge is a parent Module
diff --git a/src/main/scala/firrtl/transforms/DeadCodeElimination.scala b/src/main/scala/firrtl/transforms/DeadCodeElimination.scala
index f9e35818..c883bdfb 100644
--- a/src/main/scala/firrtl/transforms/DeadCodeElimination.scala
+++ b/src/main/scala/firrtl/transforms/DeadCodeElimination.scala
@@ -6,7 +6,7 @@ import firrtl.ir._
 import firrtl.passes._
 import firrtl.annotations._
 import firrtl.graph._
-import firrtl.analyses.InstanceGraph
+import firrtl.analyses.InstanceKeyGraph
 import firrtl.Mappers._
 import firrtl.Utils.{throwInternalError, kind}
 import firrtl.MemoizedHash._
@@ -314,7 +314,7 @@ class DeadCodeElimination extends Transform
           doTouchExtMods: Set[String]): CircuitState = {
     val c = state.circuit
     val moduleMap = c.modules.map(m => m.name -> m).toMap
-    val iGraph = new InstanceGraph(c)
+    val iGraph = InstanceKeyGraph(c)
     val moduleDeps = iGraph.graph.getEdgeMap.map({ case (k,v) =>
       k.module -> v.map(i => i.name -> i.module).toMap
     })
diff --git a/src/main/scala/firrtl/transforms/Dedup.scala b/src/main/scala/firrtl/transforms/Dedup.scala
index 30558129..627af11f 100644
--- a/src/main/scala/firrtl/transforms/Dedup.scala
+++ b/src/main/scala/firrtl/transforms/Dedup.scala
@@ -157,7 +157,7 @@ class DedupModules extends Transform with DependencyAPIMigration {
     moduleRenameMap.recordAll(map)
 
     // Build instanceify renaming map
-    val instanceGraph = new InstanceKeyGraph(c)
+    val instanceGraph = InstanceKeyGraph(c)
     val instanceify = RenameMap()
     val moduleName2Index = c.modules.map(_.name).zipWithIndex.map { case (n, i) =>
       {
@@ -467,7 +467,7 @@ object DedupModules extends LazyLogging {
                   renameMap: RenameMap): Map[String, DefModule] = {
 
     val (moduleMap, moduleLinearization) = {
-      val iGraph = new InstanceKeyGraph(circuit)
+      val iGraph = InstanceKeyGraph(circuit)
       (iGraph.moduleMap, iGraph.moduleOrder.reverse)
     }
     val main = circuit.main
diff --git a/src/main/scala/firrtl/transforms/ManipulateNames.scala b/src/main/scala/firrtl/transforms/ManipulateNames.scala
index ea988e72..f15b546f 100644
--- a/src/main/scala/firrtl/transforms/ManipulateNames.scala
+++ b/src/main/scala/firrtl/transforms/ManipulateNames.scala
@@ -3,7 +3,7 @@
 package firrtl.transforms
 
 import firrtl._
-import firrtl.analyses.InstanceGraph
+import firrtl.analyses.InstanceKeyGraph
 import firrtl.Mappers._
 
 import firrtl.annotations.{
@@ -422,7 +422,7 @@ abstract class ManipulateNames[A <: ManipulateNames[_] : ClassTag] extends Trans
          * roots ensures that the rename map is safe for parents to blindly consult. Store this in mapping of old module
          * target to new module to allow the modules to be put in the old order.
          */
-        val modulesx: Map[ModuleTarget, ir.DefModule] = new InstanceGraph(c).moduleOrder.reverse
+        val modulesx: Map[ModuleTarget, ir.DefModule] = InstanceKeyGraph(c).moduleOrder.reverse
           .map(m => t.module(m.name) -> onModule(m, r, t))
           .toMap
 
diff --git a/src/main/scala/firrtl/transforms/RenameModules.scala b/src/main/scala/firrtl/transforms/RenameModules.scala
index edd9fefb..d37f8c39 100644
--- a/src/main/scala/firrtl/transforms/RenameModules.scala
+++ b/src/main/scala/firrtl/transforms/RenameModules.scala
@@ -2,7 +2,7 @@
 
 package firrtl.transforms
 
-import firrtl.analyses.{InstanceGraph, ModuleNamespaceAnnotation}
+import firrtl.analyses.{InstanceKeyGraph, ModuleNamespaceAnnotation}
 import firrtl.ir._
 import firrtl._
 import firrtl.stage.Forms
@@ -39,7 +39,7 @@ class RenameModules extends Transform with DependencyAPIMigration {
       logger.warn("Skipping Rename Modules")
       state
     } else {
-      val moduleOrder = new InstanceGraph(state.circuit).moduleOrder.reverse
+      val moduleOrder = InstanceKeyGraph(state.circuit).moduleOrder.reverse
       val nameMappings = new mutable.HashMap[String, String]()
       moduleOrder.foreach(collectNameMapping(namespace.get, nameMappings))
 
diff --git a/src/main/scala/firrtl/transforms/TopWiring.scala b/src/main/scala/firrtl/transforms/TopWiring.scala
index 59c494c7..aa046770 100644
--- a/src/main/scala/firrtl/transforms/TopWiring.scala
+++ b/src/main/scala/firrtl/transforms/TopWiring.scala
@@ -4,9 +4,10 @@ package TopWiring
 
 import firrtl._
 import firrtl.ir._
-import firrtl.passes.{InferTypes, LowerTypes, ResolveKinds, ResolveFlows, ExpandConnects}
+import firrtl.passes.{ExpandConnects, InferTypes, LowerTypes, ResolveFlows, ResolveKinds}
 import firrtl.annotations._
 import firrtl.Mappers._
+import firrtl.analyses.InstanceKeyGraph
 import firrtl.stage.Forms
 import firrtl.options.Dependency
 
@@ -129,8 +130,8 @@ class TopWiringTransform extends Transform with DependencyAPIMigration {
   private def getSourcesMap(state: CircuitState): Map[String,Seq[(ComponentName, Type, Boolean, InstPath, String)]] = {
     val sSourcesModNames = getSourceModNames(state)
     val sSourcesNames = getSourceNames(state)
-    val instGraph = new firrtl.analyses.InstanceGraph(state.circuit)
-    val cMap = instGraph.getChildrenInstances.map{ case (m, wdis) =>
+    val instGraph = firrtl.analyses.InstanceKeyGraph(state.circuit)
+    val cMap = instGraph.getChildInstances.map{ case (m, wdis) =>
         (m -> wdis.map{ case wdi => (wdi.name, wdi.module) }.toSeq) }.toMap
     val topSort = instGraph.moduleOrder.reverse
 
@@ -167,7 +168,7 @@ class TopWiringTransform extends Transform with DependencyAPIMigration {
     */
   private def onModule(sources: Map[String, Seq[(ComponentName, Type, Boolean, InstPath, String)]],
                        portnamesmap : mutable.Map[String,String],
-                       instgraph : firrtl.analyses.InstanceGraph,
+                       instgraph : firrtl.analyses.InstanceKeyGraph,
                        namespacemap : Map[String, Namespace])
                       (module: DefModule): DefModule = {
     val namespace = namespacemap(module.name)
@@ -186,6 +187,7 @@ class TopWiringTransform extends Transform with DependencyAPIMigration {
         } }
 
         // Add connections to Module
+        val childInstances = instgraph.getChildInstances.toMap
         module match {
           case m: Module =>
             val connections: Seq[Connect] = p.map { case (ComponentName(cname,_), _, _ , path, prefix) =>
@@ -205,7 +207,7 @@ class TopWiringTransform extends Transform with DependencyAPIMigration {
                        val instportname =  portnamesmap.get(prefix + path.tail.mkString("_")) match {
                            case Some(ipn) => ipn
                            case None => {
-                             val instmod = instgraph.getChildrenInstances(module.name).collectFirst {
+                             val instmod = childInstances(module.name).collectFirst {
                                  case wdi if wdi.name == path.head => wdi.module}.get
                              val instnamespace = namespacemap(instmod)
                              portnamesmap(prefix + path.tail.mkString("_")) =
@@ -244,7 +246,7 @@ class TopWiringTransform extends Transform with DependencyAPIMigration {
     val sources = getSourcesMap(state)
     val (nstate, nmappings) = if (sources.nonEmpty) {
       val portnamesmap: mutable.Map[String,String] = mutable.Map()
-      val instgraph = new firrtl.analyses.InstanceGraph(state.circuit)
+      val instgraph = InstanceKeyGraph(state.circuit)
       val namespacemap = state.circuit.modules.map{ case m => (m.name -> Namespace(m)) }.toMap
       val modulesx = state.circuit.modules map onModule(sources, portnamesmap, instgraph, namespacemap)
       val newCircuit = state.circuit.copy(modules = modulesx)
diff --git a/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala b/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala
index 8d073ecb..ec403259 100644
--- a/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala
+++ b/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala
@@ -4,10 +4,105 @@ package firrtlTests.analyses
 
 import firrtl.analyses.InstanceKeyGraph
 import firrtl.analyses.InstanceKeyGraph.InstanceKey
+import firrtl.annotations.TargetToken.OfModule
+import firrtl.graph.DiGraph
 import firrtl.testutils.FirrtlFlatSpec
 
 class InstanceKeyGraphSpec extends FirrtlFlatSpec {
-  behavior of "InstanceKeyGraph"
+  behavior of "InstanceKeyGraph.graph"
+
+  private def getEdgeSet(graph: DiGraph[String]): collection.Map[String, collection.Set[String]] = {
+    (graph.getVertices map {v => (v, graph.getEdges(v))}).toMap
+  }
+
+  it should "recognize a simple hierarchy" 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 graph = InstanceKeyGraph(parse(input)).graph.transformNodes(_.module)
+    getEdgeSet(graph) shouldBe Map(
+      "Top" -> Set("Child1", "Child2"),
+      "Child1" -> Set("Child1a", "Child1b"),
+      "Child2" -> Set(), "Child1a" -> Set(), "Child1b" -> Set())
+  }
+
+  it should "recognize 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 graph = InstanceKeyGraph(parse(input)).graph.transformNodes(_.module)
+    getEdgeSet(graph) shouldBe Map(
+      "Top" -> Set("Child1"),
+      "Top2" -> Set("Child2", "Child3"),
+      "Child2" -> Set("Child2a", "Child2b"),
+      "Child1" -> Set(), "Child2a" -> Set(), "Child2b" -> Set(), "Child3" -> Set())
+  }
+
+  it should "not drop duplicate nodes when they collide as a result of transformNodes" in {
+    val input =
+      """circuit Top :
+        |  module Buzz :
+        |    skip
+        |  module Fizz :
+        |    inst b of Buzz
+        |  module Foo :
+        |    inst f1 of Fizz
+        |  module Bar :
+        |    inst f2 of Fizz
+        |  module Top :
+        |    inst f of Foo
+        |    inst b of Bar
+        |""".stripMargin
+    val graph = InstanceKeyGraph(parse(input)).graph
+
+    // Create graphs with edges from child to parent module
+    // g1 has collisions on parents to children, ie. it combines:
+    //   (f1, Fizz) -> (b, Buzz) and (f2, Fizz) -> (b, Buzz)
+    val g1 = graph.transformNodes(_.module).reverse
+    g1.getEdges("Fizz") shouldBe Set("Foo", "Bar")
+
+    val g2 = graph.reverse.transformNodes(_.module)
+    // g2 combines
+    //   (f1, Fizz) -> (f, Foo) and (f2, Fizz) -> (b, Bar)
+    g2.getEdges("Fizz") shouldBe Set("Foo", "Bar")
+  }
+
+
+  behavior of "InstanceKeyGraph.getChildInstances"
 
   // Note that due to optimized implementations of Map1-4, at least 5 entries are needed to
   // experience non-determinism
@@ -29,7 +124,7 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec {
                   |    skip
                   |""".stripMargin
     val circuit = parse(input)
-    val instGraph = new InstanceKeyGraph(circuit)
+    val instGraph = InstanceKeyGraph(circuit)
     val childMap = instGraph.getChildInstances
     childMap.map(_._1) should equal (Seq("Top", "Child1", "Child1a", "Child1b", "Child2"))
   }
@@ -50,12 +145,14 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec {
                   |    skip
                   |""".stripMargin
     val circuit = parse(input)
-    val instGraph = new InstanceKeyGraph(circuit)
+    val instGraph = InstanceKeyGraph(circuit)
     val childMap = instGraph.getChildInstances.toMap
     val insts = childMap("Top").map(_.name)
     insts should equal (Seq("a", "b", "c", "d", "e", "f"))
   }
 
+  behavior of "InstanceKeyGraph.moduleOrder"
+
   it should "compute a correct and deterministic module order" in {
     val input = """
                   |circuit Top :
@@ -80,12 +177,14 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec {
                   |    skip
                   |""".stripMargin
     val circuit = parse(input)
-    val instGraph = new InstanceKeyGraph(circuit)
+    val instGraph = 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"))
   }
 
+  behavior of "InstanceKeyGraph.findInstancesInHierarchy"
+
   it should "find hierarchical instances correctly in disconnected hierarchies" in {
     val input =
       """circuit Top :
@@ -111,9 +210,10 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec {
         |""".stripMargin
 
     val circuit = parse(input)
-    val iGraph = new InstanceKeyGraph(circuit)
+    val iGraph = 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("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
@@ -121,4 +221,131 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec {
     iGraph.findInstancesInHierarchy("Child3") shouldBe Nil
   }
 
+  behavior of "InstanceKeyGraph.staticInstanceCount"
+
+  it should "report that there is one instance of the top module" in {
+    val input =
+      """|circuit Foo:
+         |  module Foo:
+         |    skip
+         |""".stripMargin
+    val iGraph = InstanceKeyGraph(parse(input))
+    val expectedCounts = Map(OfModule("Foo") -> 1)
+    iGraph.staticInstanceCount should be (expectedCounts)
+  }
+
+  it should "report correct number of instances for a sample circuit" in {
+    val input =
+      """|circuit Foo:
+         |  module Baz:
+         |    skip
+         |  module Bar:
+         |    inst baz1 of Baz
+         |    inst baz2 of Baz
+         |    inst baz3 of Baz
+         |    skip
+         |  module Foo:
+         |    inst bar1 of Bar
+         |    inst bar2 of Bar
+         |""".stripMargin
+    val iGraph = InstanceKeyGraph(parse(input))
+    val expectedCounts = Map(OfModule("Foo") -> 1,
+      OfModule("Bar") -> 2,
+      OfModule("Baz") -> 3)
+    iGraph.staticInstanceCount should be (expectedCounts)
+  }
+
+  it should "report zero instances for dead modules" in {
+    val input =
+      """|circuit Foo:
+         |  module Bar:
+         |    skip
+         |  module Foo:
+         |    skip
+         |""".stripMargin
+    val iGraph = InstanceKeyGraph(parse(input))
+    val expectedCounts = Map(OfModule("Foo") -> 1,
+      OfModule("Bar") -> 0)
+    iGraph.staticInstanceCount should be (expectedCounts)
+  }
+
+  behavior of "InstanceKeyGraph.getChildInstanceMap"
+
+  it should "preserve Module declaration order" in {
+    val input = """
+                  |circuit Top :
+                  |  module Top :
+                  |    inst c1 of Child1
+                  |    inst c2 of Child2
+                  |    inst c3 of Child1
+                  |    inst c4 of Child1
+                  |    inst c5 of Child1
+                  |  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 = InstanceKeyGraph(circuit)
+    val childMap = instGraph.getChildInstanceMap
+
+    val modules = childMap.keys.toSeq.map(_.value)
+    assert(modules == Seq("Top", "Child1", "Child1a", "Child1b", "Child2"))
+
+    assert(childMap(OfModule("Child1a")).isEmpty)
+    assert(childMap(OfModule("Child1b")).isEmpty)
+    assert(childMap(OfModule("Child2")).isEmpty)
+
+    val topInstances = childMap(OfModule("Top")).map { case (k,v) => k.value -> v.value}.toSeq
+    assert(topInstances ==
+      Seq("c1" -> "Child1", "c2" -> "Child2", "c3" -> "Child1", "c4" -> "Child1", "c5" -> "Child1"))
+
+    val child1Instance = childMap(OfModule("Child1")).map { case (k,v) => k.value -> v.value}.toSeq
+    assert(child1Instance == Seq("a" -> "Child1a", "b" -> "Child1b"))
+  }
+
+  behavior of "InstanceKeyGraph.fullHierarchy"
+
+  // 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 instGraph = InstanceKeyGraph(parse(input))
+    val hier = instGraph.fullHierarchy
+    hier.keys.toSeq.map(_.name) should equal (Seq("Top", "a", "b", "c", "d", "e"))
+  }
+
+  behavior of "Reachable/Unreachable helper methods"
+
+  they should "report correct reachable/unreachable counts" in {
+    val input =
+      """|circuit Top:
+         |  module Unreachable:
+         |    skip
+         |  module Reachable:
+         |    skip
+         |  module Top:
+         |    inst reachable of Reachable
+         |""".stripMargin
+    val iGraph = InstanceKeyGraph(parse(input))
+    iGraph.reachableModules should contain theSameElementsAs Seq(OfModule("Top"), OfModule("Reachable"))
+    iGraph.unreachableModules should contain theSameElementsAs Seq(OfModule("Unreachable"))
+  }
 }