WiringTransform Refactor (#648)

Massive refactoring to WiringTransform with the use of a new EulerTour 
class to speed things up via fast least common ancestor (LCA) queries.

Changes include (but are not limited to):

* Use lowest common ancestor when wiring
* Add EulerTour class with naive and Berkman-Vishkin RMQ
* Adds LCA method for Instance Graph
* Enables "Two Sources" using "Top" wiring test as this is now valid
* Remove TopAnnotation from WiringTransform
* Represent WiringTransform sink as `Seq[Named]`
* Remove WiringUtils.countInstances, fix imports
* Support sources under sinks in WiringTransform
* Enable internal module wiring
* Support Wiring of Aggregates
h/t @edcote
fixes #728 

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>
Reviewed-by: Jack Koenig<jack.koenig3@gmail.com>

1 files changed, 16 insertions, 4 deletions

diff --git a/src/main/scala/firrtl/analyses/Netlist.scala b/src/main/scala/firrtl/analyses/Netlist.scala
index 4e211d8b..99f3645f 100644
--- a/src/main/scala/firrtl/analyses/Netlist.scala
+++ b/src/main/scala/firrtl/analyses/Netlist.scala
@@ -1,3 +1,5 @@
+// See LICENSE for license details.
+
 package firrtl.analyses
 
 import scala.collection.mutable
@@ -10,13 +12,14 @@ import firrtl.Mappers._
 
 
 /** A class representing the instance hierarchy of a working IR Circuit
-  * 
+  *
   * @constructor constructs an instance graph from a Circuit
   * @param c the Circuit to analyze
   */
 class InstanceGraph(c: Circuit) {
 
-  private def collectInstances(insts: mutable.Set[WDefInstance])(s: Statement): Statement = s match {
+  private def collectInstances(insts: mutable.Set[WDefInstance])
+                              (s: Statement): Statement = s match {
     case i: WDefInstance =>
       insts += i
       i
@@ -72,7 +75,7 @@ class InstanceGraph(c: Circuit) {
   /** Finds the absolute paths (each represented by a Seq of instances
     * representing the chain of hierarchy) of all instances of a
     * particular module.
-    * 
+    *
     * @param module the name of the selected module
     * @return a Seq[Seq[WDefInstance]] of absolute instance paths
     */
@@ -81,5 +84,14 @@ class InstanceGraph(c: Circuit) {
     instances flatMap { i => fullHierarchy(i) }
   }
 
-}
+  /** An `[[EulerTour]]` representation of the `[[DiGraph]]` */
+  lazy val tour = EulerTour(graph, trueTopInstance)
 
+  /** Finds the lowest common ancestor instances for two module names in
+    * a design
+    */
+  def lowestCommonAncestor(moduleA: Seq[WDefInstance],
+                           moduleB: Seq[WDefInstance]): Seq[WDefInstance] = {
+    tour.rmq(moduleA, moduleB)
+  }
+}