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>

4 files changed, 10 insertions, 15 deletions

diff --git a/src/main/scala/firrtl/passes/clocklist/ClockList.scala b/src/main/scala/firrtl/passes/clocklist/ClockList.scala
index bd2536ab..073eb050 100644
--- a/src/main/scala/firrtl/passes/clocklist/ClockList.scala
+++ b/src/main/scala/firrtl/passes/clocklist/ClockList.scala
@@ -8,7 +8,7 @@ import firrtl.ir._
 import annotations._
 import Utils.error
 import java.io.{File, CharArrayWriter, PrintWriter, Writer}
-import wiring.WiringUtils.{getChildrenMap, countInstances, ChildrenMap, getLineage}
+import wiring.WiringUtils.{getChildrenMap, getLineage}
 import wiring.Lineage
 import ClockListUtils._
 import Utils._
@@ -30,7 +30,7 @@ class ClockList(top: String, writer: Writer) extends Pass {
     // === Checks ===
     // TODO(izraelevitz): Check all registers/memories use "clock" clock port
     // ==============
-    
+
     // Clock sources must be blackbox outputs and top's clock
     val partialSourceList = getSourceList(moduleMap)(lineages)
     val sourceList = partialSourceList ++ moduleMap(top).ports.collect{ case Port(i, n, Input, ClockType) => n }
@@ -39,7 +39,7 @@ class ClockList(top: String, writer: Writer) extends Pass {
     // Remove everything from the circuit, unless it has a clock type
     // This simplifies the circuit drastically so InlineInstances doesn't take forever.
     val onlyClockCircuit = RemoveAllButClocks.run(c)
-    
+
     // Inline the clock-only circuit up to the specified top module
     val modulesToInline = (c.modules.collect { case Module(_, n, _, _) if n != top => ModuleName(n, CircuitName(c.main)) }).toSet
     val inlineTransform = new InlineInstances
diff --git a/src/main/scala/firrtl/passes/clocklist/ClockListTransform.scala b/src/main/scala/firrtl/passes/clocklist/ClockListTransform.scala
index b04171a7..24f25525 100644
--- a/src/main/scala/firrtl/passes/clocklist/ClockListTransform.scala
+++ b/src/main/scala/firrtl/passes/clocklist/ClockListTransform.scala
@@ -8,7 +8,6 @@ import firrtl.ir._
 import annotations._
 import Utils.error
 import java.io.{File, CharArrayWriter, PrintWriter, Writer}
-import wiring.WiringUtils.{getChildrenMap, countInstances, ChildrenMap, getLineage}
 import wiring.Lineage
 import ClockListUtils._
 import Utils._
@@ -22,23 +21,23 @@ object ClockListAnnotation {
 [Optional] ClockList
   List which signal drives each clock of every descendent of specified module
 
-Usage: 
+Usage:
   --list-clocks -c:<circuit>:-m:<module>:-o:<filename>
   *** Note: sub-arguments to --list-clocks should be delimited by : and not white space!
-"""    
-  
+"""
+
     //Parse pass options
     val passOptions = PassConfigUtil.getPassOptions(t, usage)
     val outputConfig = passOptions.getOrElse(
-      OutputConfigFileName, 
+      OutputConfigFileName,
       error("No output config file provided for ClockList!" + usage)
     )
     val passCircuit = passOptions.getOrElse(
-      PassCircuitName, 
+      PassCircuitName,
       error("No circuit name specified for ClockList!" + usage)
     )
     val passModule = passOptions.getOrElse(
-      PassModuleName, 
+      PassModuleName,
       error("No module name specified for ClockList!" + usage)
     )
     passOptions.get(InputConfigFileName) match {
@@ -65,7 +64,7 @@ class ClockListTransform extends Transform {
   def passSeq(top: String, writer: Writer): Seq[Pass] =
     Seq(new ClockList(top, writer))
   def execute(state: CircuitState): CircuitState = getMyAnnotations(state) match {
-    case Seq(ClockListAnnotation(ModuleName(top, CircuitName(state.circuit.main)), out)) => 
+    case Seq(ClockListAnnotation(ModuleName(top, CircuitName(state.circuit.main)), out)) =>
       val outputFile = new PrintWriter(out)
       val newC = (new ClockList(top, outputFile)).run(state.circuit)
       outputFile.close()
diff --git a/src/main/scala/firrtl/passes/clocklist/ClockListUtils.scala b/src/main/scala/firrtl/passes/clocklist/ClockListUtils.scala
index b81d0c7e..892f1642 100644
--- a/src/main/scala/firrtl/passes/clocklist/ClockListUtils.scala
+++ b/src/main/scala/firrtl/passes/clocklist/ClockListUtils.scala
@@ -8,7 +8,6 @@ import firrtl.ir._
 import annotations._
 import Utils.error
 import java.io.{File, CharArrayWriter, PrintWriter, Writer}
-import wiring.WiringUtils.{getChildrenMap, countInstances, ChildrenMap, getLineage}
 import wiring.Lineage
 import ClockListUtils._
 import Utils._
@@ -61,4 +60,3 @@ object ClockListUtils {
     }
   }
 }
-
diff --git a/src/main/scala/firrtl/passes/clocklist/RemoveAllButClocks.scala b/src/main/scala/firrtl/passes/clocklist/RemoveAllButClocks.scala
index 53787b1d..1178ce69 100644
--- a/src/main/scala/firrtl/passes/clocklist/RemoveAllButClocks.scala
+++ b/src/main/scala/firrtl/passes/clocklist/RemoveAllButClocks.scala
@@ -8,8 +8,6 @@ import firrtl.ir._
 import annotations._
 import Utils.error
 import java.io.{File, CharArrayWriter, PrintWriter, Writer}
-import wiring.WiringUtils.{getChildrenMap, countInstances, ChildrenMap, getLineage}
-import wiring.Lineage
 import ClockListUtils._
 import Utils._
 import memlib.AnalysisUtils._