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

1 files changed, 20 insertions, 12 deletions

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(