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

3 files changed, 93 insertions, 29 deletions

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