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>

2 files changed, 794 insertions, 277 deletions

diff --git a/src/test/scala/firrtlTests/WiringTests.scala b/src/test/scala/firrtlTests/WiringTests.scala
index 01ad573f..5dd048a3 100644
--- a/src/test/scala/firrtlTests/WiringTests.scala
+++ b/src/test/scala/firrtlTests/WiringTests.scala
@@ -33,86 +33,87 @@ class WiringTests extends FirrtlFlatSpec {
     InferWidths
   )
 
-  "Wiring from r to X" should "work" in {
-    val sinks = Set("X")
-    val sas = WiringInfo("C", "r", sinks, "pin", "A")
+  it should "wire from a register source (r) to multiple extmodule sinks (X)" in {
+    val sinks = Seq(ModuleName("X", CircuitName("Top")))
+    val source = ComponentName("r", ModuleName("C", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
     val input =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a of A
-        |    a.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    inst b of B
-        |    b.clock <= clock
-        |    inst x of X
-        |    x.clock <= clock
-        |    inst d of D
-        |    d.clock <= clock
-        |  module B :
-        |    input clock: Clock
-        |    inst c of C
-        |    c.clock <= clock
-        |    inst d of D
-        |    d.clock <= clock
-        |  module C :
-        |    input clock: Clock
-        |    reg r: UInt<5>, clock
-        |  module D :
-        |    input clock: Clock
-        |    inst x1 of X
-        |    x1.clock <= clock
-        |    inst x2 of X
-        |    x2.clock <= clock
-        |  extmodule X :
-        |    input clock: Clock
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    inst b of B
+         |    b.clock <= clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |  module B :
+         |    input clock: Clock
+         |    inst c of C
+         |    c.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |  module C :
+         |    input clock: Clock
+         |    reg r: UInt<5>, clock
+         |  module D :
+         |    input clock: Clock
+         |    inst x1 of X
+         |    x1.clock <= clock
+         |    inst x2 of X
+         |    x2.clock <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |""".stripMargin
     val check =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a of A
-        |    a.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    inst b of B
-        |    b.clock <= clock
-        |    inst x of X
-        |    x.clock <= clock
-        |    inst d of D
-        |    d.clock <= clock
-        |    wire r: UInt<5>
-        |    r <= b.r
-        |    x.pin <= r
-        |    d.r <= r
-        |  module B :
-        |    input clock: Clock
-        |    output r: UInt<5>
-        |    inst c of C
-        |    c.clock <= clock
-        |    inst d of D
-        |    d.clock <= clock
-        |    r <= c.r_0
-        |    d.r <= r
-        |  module C :
-        |    input clock: Clock
-        |    output r_0: UInt<5>
-        |    reg r: UInt<5>, clock
-        |    r_0 <= r
-        |  module D :
-        |    input clock: Clock
-        |    input r: UInt<5>
-        |    inst x1 of X
-        |    x1.clock <= clock
-        |    inst x2 of X
-        |    x2.clock <= clock
-        |    x1.pin <= r
-        |    x2.pin <= r
-        |  extmodule X :
-        |    input clock: Clock
-        |    input pin: UInt<5>
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire r: UInt<5>
+         |    inst b of B
+         |    b.clock <= clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |    d.r <= r
+         |    r <= b.r
+         |    x.pin <= r
+         |  module B :
+         |    input clock: Clock
+         |    output r: UInt<5>
+         |    inst c of C
+         |    c.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |    r <= c.r_0
+         |    d.r <= r
+         |  module C :
+         |    input clock: Clock
+         |    output r_0: UInt<5>
+         |    reg r: UInt<5>, clock
+         |    r_0 <= r
+         |  module D :
+         |    input clock: Clock
+         |    input r: UInt<5>
+         |    inst x1 of X
+         |    x1.clock <= clock
+         |    inst x2 of X
+         |    x2.clock <= clock
+         |    x1.pin <= r
+         |    x2.pin <= r
+         |  extmodule X :
+         |    input clock: Clock
+         |    input pin: UInt<5>
+         |""".stripMargin
     val c = passes.foldLeft(parse(input)) {
       (c: Circuit, p: Pass) => p.run(c)
     }
@@ -121,41 +122,87 @@ class WiringTests extends FirrtlFlatSpec {
     (parse(retC.serialize).serialize) should be (parse(check).serialize)
   }
 
-  "Wiring from r.x to X" should "work" in {
-    val sinks = Set("X")
-    val sas = WiringInfo("A", "r.x", sinks, "pin", "A")
+  it should "wire from a register source (r) to multiple module sinks (X)" in {
+    val sinks = Seq(ModuleName("X", CircuitName("Top")))
+    val source = ComponentName("r", ModuleName("C", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
     val input =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a of A
-        |    a.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    reg r : {x: UInt<5>}, clock
-        |    inst x of X
-        |    x.clock <= clock
-        |  extmodule X :
-        |    input clock: Clock
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    inst b of B
+         |    b.clock <= clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |  module B :
+         |    input clock: Clock
+         |    inst c of C
+         |    c.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |  module C :
+         |    input clock: Clock
+         |    reg r: UInt<5>, clock
+         |  module D :
+         |    input clock: Clock
+         |    inst x1 of X
+         |    x1.clock <= clock
+         |    inst x2 of X
+         |    x2.clock <= clock
+         |  module X :
+         |    input clock: Clock
+         |""".stripMargin
     val check =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a of A
-        |    a.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    reg r: {x: UInt<5>}, clock
-        |    inst x of X
-        |    x.clock <= clock
-        |    wire r_x: UInt<5>
-        |    r_x <= r.x
-        |    x.pin <= r_x
-        |  extmodule X :
-        |    input clock: Clock
-        |    input pin: UInt<5>
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire r: UInt<5>
+         |    inst b of B
+         |    b.clock <= clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |    d.r <= r
+         |    r <= b.r
+         |    x.pin <= r
+         |  module B :
+         |    input clock: Clock
+         |    output r: UInt<5>
+         |    inst c of C
+         |    c.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |    r <= c.r_0
+         |    d.r <= r
+         |  module C :
+         |    input clock: Clock
+         |    output r_0: UInt<5>
+         |    reg r: UInt<5>, clock
+         |    r_0 <= r
+         |  module D :
+         |    input clock: Clock
+         |    input r: UInt<5>
+         |    inst x1 of X
+         |    x1.clock <= clock
+         |    inst x2 of X
+         |    x2.clock <= clock
+         |    x1.pin <= r
+         |    x2.pin <= r
+         |  module X :
+         |    input clock: Clock
+         |    input pin: UInt<5>
+         |""".stripMargin
     val c = passes.foldLeft(parse(input)) {
       (c: Circuit, p: Pass) => p.run(c)
     }
@@ -163,39 +210,91 @@ class WiringTests extends FirrtlFlatSpec {
     val retC = wiringPass.run(c)
     (parse(retC.serialize).serialize) should be (parse(check).serialize)
   }
-  "Wiring from clock to X" should "work" in {
-    val sinks = Set("X")
-    val sas = WiringInfo("A", "clock", sinks, "pin", "A")
+
+  it should "wire from a register sink (r) to a wire source (s) in another module (X)" in {
+    val sinks = Seq(ComponentName("s", ModuleName("X", CircuitName("Top"))))
+    val source = ComponentName("r", ModuleName("C", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
     val input =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a of A
-        |    a.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    inst x of X
-        |    x.clock <= clock
-        |  extmodule X :
-        |    input clock: Clock
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    inst b of B
+         |    b.clock <= clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |  module B :
+         |    input clock: Clock
+         |    inst c of C
+         |    c.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |  module C :
+         |    input clock: Clock
+         |    reg r: UInt<5>, clock
+         |  module D :
+         |    input clock: Clock
+         |    inst x1 of X
+         |    x1.clock <= clock
+         |    inst x2 of X
+         |    x2.clock <= clock
+         |  module X :
+         |    input clock: Clock
+         |    wire s: UInt<5>
+         |""".stripMargin
     val check =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a of A
-        |    a.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    inst x of X
-        |    x.clock <= clock
-        |    wire clock_0: Clock
-        |    clock_0 <= clock
-        |    x.pin <= clock_0
-        |  extmodule X :
-        |    input clock: Clock
-        |    input pin: Clock
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire r: UInt<5>
+         |    inst b of B
+         |    b.clock <= clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |    d.r <= r
+         |    r <= b.r
+         |    x.pin <= r
+         |  module B :
+         |    input clock: Clock
+         |    output r: UInt<5>
+         |    inst c of C
+         |    c.clock <= clock
+         |    inst d of D
+         |    d.clock <= clock
+         |    r <= c.r_0
+         |    d.r <= r
+         |  module C :
+         |    input clock: Clock
+         |    output r_0: UInt<5>
+         |    reg r: UInt<5>, clock
+         |    r_0 <= r
+         |  module D :
+         |    input clock: Clock
+         |    input r: UInt<5>
+         |    inst x1 of X
+         |    x1.clock <= clock
+         |    inst x2 of X
+         |    x2.clock <= clock
+         |    x1.pin <= r
+         |    x2.pin <= r
+         |  module X :
+         |    input clock: Clock
+         |    input pin: UInt<5>
+         |    wire s: UInt<5>
+         |    s <= pin
+         |""".stripMargin
     val c = passes.foldLeft(parse(input)) {
       (c: Circuit, p: Pass) => p.run(c)
     }
@@ -203,69 +302,210 @@ class WiringTests extends FirrtlFlatSpec {
     val retC = wiringPass.run(c)
     (parse(retC.serialize).serialize) should be (parse(check).serialize)
   }
-  "Two sources" should "fail" in {
-    val sinks = Set("X")
-    val sas = WiringInfo("A", "clock", sinks, "pin", "Top")
+
+  it should "wire from a SubField source (r.x) to an extmodule sink (X)" in {
+    val sinks = Seq(ModuleName("X", CircuitName("Top")))
+    val source = ComponentName("r.x", ModuleName("A", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
     val input =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a1 of A
-        |    a1.clock <= clock
-        |    inst a2 of A
-        |    a2.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    inst x of X
-        |    x.clock <= clock
-        |  extmodule X :
-        |    input clock: Clock
-        |""".stripMargin
-    intercept[WiringException] {
-      val c = passes.foldLeft(parse(input)) {
-        (c: Circuit, p: Pass) => p.run(c)
-      }
-      val wiringPass = new Wiring(Seq(sas))
-      val retC = wiringPass.run(c)
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    reg r : {x: UInt<5>}, clock
+         |    inst x of X
+         |    x.clock <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |""".stripMargin
+    val check =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire r_x: UInt<5>
+         |    reg r: {x: UInt<5>}, clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    x.pin <= r_x
+         |    r_x <= r.x
+         |  extmodule X :
+         |    input clock: Clock
+         |    input pin: UInt<5>
+         |""".stripMargin
+    val c = passes.foldLeft(parse(input)) {
+      (c: Circuit, p: Pass) => p.run(c)
+    }
+    val wiringPass = new Wiring(Seq(sas))
+    val retC = wiringPass.run(c)
+    (parse(retC.serialize).serialize) should be (parse(check).serialize)
+  }
+
+  it should "wire properly with a source as a submodule of a sink" in {
+    val sinks = Seq(ComponentName("s", ModuleName("A", CircuitName("Top"))))
+    val source = ComponentName("r", ModuleName("X", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
+    val input =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire s: UInt<5>
+         |    inst x of X
+         |    x.clock <= clock
+         |  module X :
+         |    input clock: Clock
+         |    reg r: UInt<5>, clock
+         |""".stripMargin
+    val check =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire pin: UInt<5>
+         |    wire s: UInt<5>
+         |    inst x of X
+         |    x.clock <= clock
+         |    pin <= x.r_0
+         |    s <= pin
+         |  module X :
+         |    input clock: Clock
+         |    output r_0: UInt<5>
+         |    reg r: UInt<5>, clock
+         |    r_0 <= r
+         |""".stripMargin
+    val c = passes.foldLeft(parse(input)) {
+      (c: Circuit, p: Pass) => p.run(c)
+    }
+    val wiringPass = new Wiring(Seq(sas))
+    val retC = wiringPass.run(c)
+    (parse(retC.serialize).serialize) should be (parse(check).serialize)
+  }
+
+  it should "wire with source and sink in the same module" in {
+    val sinks = Seq(ComponentName("s", ModuleName("A", CircuitName("Top"))))
+    val source = ComponentName("r", ModuleName("A", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
+    val input =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire s: UInt<5>
+         |    reg r: UInt<5>, clock
+         |""".stripMargin
+    val check =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire pin: UInt<5>
+         |    wire s: UInt<5>
+         |    reg r: UInt<5>, clock
+         |    s <= pin
+         |    pin <= r
+         |""".stripMargin
+    val c = passes.foldLeft(parse(input)) {
+      (c: Circuit, p: Pass) => p.run(c)
+    }
+    val wiringPass = new Wiring(Seq(sas))
+    val retC = wiringPass.run(c)
+    (parse(retC.serialize).serialize) should be (parse(check).serialize)
+  }
+
+  it should "wire multiple sinks in the same module" in {
+    val sinks = Seq(ComponentName("s", ModuleName("A", CircuitName("Top"))),
+                    ComponentName("t", ModuleName("A", CircuitName("Top"))))
+    val source = ComponentName("r", ModuleName("A", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
+    val input =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire s: UInt<5>
+         |    wire t: UInt<5>
+         |    reg r: UInt<5>, clock
+         |""".stripMargin
+    val check =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire pin: UInt<5>
+         |    wire s: UInt<5>
+         |    wire t: UInt<5>
+         |    reg r: UInt<5>, clock
+         |    t <= pin
+         |    s <= pin
+         |    pin <= r
+         |""".stripMargin
+    val c = passes.foldLeft(parse(input)) {
+      (c: Circuit, p: Pass) => p.run(c)
     }
+    val wiringPass = new Wiring(Seq(sas))
+    val retC = wiringPass.run(c)
+    (parse(retC.serialize).serialize) should be (parse(check).serialize)
   }
-  "Wiring from A.clock to X, with 2 A's, and A as top" should "work" in {
-    val sinks = Set("X")
-    val sas = WiringInfo("A", "clock", sinks, "pin", "A")
+
+  it should "wire clocks" in {
+    val sinks = Seq(ModuleName("X", CircuitName("Top")))
+    val source = ComponentName("clock", ModuleName("A", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
     val input =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a1 of A
-        |    a1.clock <= clock
-        |    inst a2 of A
-        |    a2.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    inst x of X
-        |    x.clock <= clock
-        |  extmodule X :
-        |    input clock: Clock
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    inst x of X
+         |    x.clock <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |""".stripMargin
     val check =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a1 of A
-        |    a1.clock <= clock
-        |    inst a2 of A
-        |    a2.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    inst x of X
-        |    x.clock <= clock
-        |    wire clock_0: Clock
-        |    clock_0 <= clock
-        |    x.pin <= clock_0
-        |  extmodule X :
-        |    input clock: Clock
-        |    input pin: Clock
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire clock_0: Clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    x.pin <= clock_0
+         |    clock_0 <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |    input pin: Clock
+         |""".stripMargin
     val c = passes.foldLeft(parse(input)) {
       (c: Circuit, p: Pass) => p.run(c)
     }
@@ -273,26 +513,120 @@ class WiringTests extends FirrtlFlatSpec {
     val retC = wiringPass.run(c)
     (parse(retC.serialize).serialize) should be (parse(check).serialize)
   }
-  "Wiring from A.clock to X, with 2 A's, and A as top, but Top instantiates X" should "error" in {
-    val sinks = Set("X")
-    val sas = WiringInfo("A", "clock", sinks, "pin", "A")
+
+  it should "handle two source instances with clearly defined sinks" in {
+    val sinks = Seq(ModuleName("X", CircuitName("Top")))
+    val source = ComponentName("clock", ModuleName("A", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
     val input =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a1 of A
-        |    a1.clock <= clock
-        |    inst a2 of A
-        |    a2.clock <= clock
-        |    inst x of X
-        |    x.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    inst x of X
-        |    x.clock <= clock
-        |  extmodule X :
-        |    input clock: Clock
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a1 of A
+         |    a1.clock <= clock
+         |    inst a2 of A
+         |    a2.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    inst x of X
+         |    x.clock <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |""".stripMargin
+    val check =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a1 of A
+         |    a1.clock <= clock
+         |    inst a2 of A
+         |    a2.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire clock_0: Clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    x.pin <= clock_0
+         |    clock_0 <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |    input pin: Clock
+         |""".stripMargin
+    val c = passes.foldLeft(parse(input)) {
+      (c: Circuit, p: Pass) => p.run(c)
+    }
+    val wiringPass = new Wiring(Seq(sas))
+    val retC = wiringPass.run(c)
+    (parse(retC.serialize).serialize) should be (parse(check).serialize)
+  }
+
+  it should "wire multiple clocks" in {
+    val sinks = Seq(ModuleName("X", CircuitName("Top")))
+    val source = ComponentName("clock", ModuleName("A", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
+    val input =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a1 of A
+         |    a1.clock <= clock
+         |    inst a2 of A
+         |    a2.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    inst x of X
+         |    x.clock <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |""".stripMargin
+    val check =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a1 of A
+         |    a1.clock <= clock
+         |    inst a2 of A
+         |    a2.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire clock_0: Clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    x.pin <= clock_0
+         |    clock_0 <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |    input pin: Clock
+         |""".stripMargin
+    val c = passes.foldLeft(parse(input)) {
+      (c: Circuit, p: Pass) => p.run(c)
+    }
+    val wiringPass = new Wiring(Seq(sas))
+    val retC = wiringPass.run(c)
+    (parse(retC.serialize).serialize) should be (parse(check).serialize)
+  }
+
+  it should "error with WiringException for indeterminate ownership" in {
+    val sinks = Seq(ModuleName("X", CircuitName("Top")))
+    val source = ComponentName("clock", ModuleName("A", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
+    val input =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a1 of A
+         |    a1.clock <= clock
+         |    inst a2 of A
+         |    a2.clock <= clock
+         |    inst x of X
+         |    x.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    inst x of X
+         |    x.clock <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |""".stripMargin
     intercept[WiringException] {
       val c = passes.foldLeft(parse(input)) {
         (c: Circuit, p: Pass) => p.run(c)
@@ -301,43 +635,45 @@ class WiringTests extends FirrtlFlatSpec {
       val retC = wiringPass.run(c)
     }
   }
-  "Wiring from A.r[a] to X" should "work" in {
-    val sinks = Set("X")
-    val sas = WiringInfo("A", "r[a]", sinks, "pin", "A")
+
+  it should "wire subindex source to sink" in {
+    val sinks = Seq(ModuleName("X", CircuitName("Top")))
+    val source = ComponentName("r[a]", ModuleName("A", CircuitName("Top")))
+    val sas = WiringInfo(source, sinks, "pin")
     val input =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a of A
-        |    a.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    reg r: UInt<2>[5], clock
-        |    node a = UInt(5)
-        |    inst x of X
-        |    x.clock <= clock
-        |  extmodule X :
-        |    input clock: Clock
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    reg r: UInt<2>[5], clock
+         |    node a = UInt(5)
+         |    inst x of X
+         |    x.clock <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |""".stripMargin
     val check =
-      """circuit Top :
-        |  module Top :
-        |    input clock: Clock
-        |    inst a of A
-        |    a.clock <= clock
-        |  module A :
-        |    input clock: Clock
-        |    reg r: UInt<2>[5], clock
-        |    node a = UInt(5)
-        |    inst x of X
-        |    x.clock <= clock
-        |    wire r_a: UInt<2>
-        |    r_a <= r[a]
-        |    x.pin <= r_a
-        |  extmodule X :
-        |    input clock: Clock
-        |    input pin: UInt<2>
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire r_a: UInt<2>
+         |    reg r: UInt<2>[5], clock
+         |    node a = UInt(5)
+         |    inst x of X
+         |    x.clock <= clock
+         |    x.pin <= r_a
+         |    r_a <= r[a]
+         |  extmodule X :
+         |    input clock: Clock
+         |    input pin: UInt<2>
+         |""".stripMargin
     val c = passes.foldLeft(parse(input)) {
       (c: Circuit, p: Pass) => p.run(c)
     }
@@ -346,37 +682,182 @@ class WiringTests extends FirrtlFlatSpec {
     (parse(retC.serialize).serialize) should be (parse(check).serialize)
   }
 
-  "Wiring annotations" should "work" in {
+  it should "wire using Annotations with a sink module" in {
     val source = SourceAnnotation(ComponentName("r", ModuleName("Top", CircuitName("Top"))), "pin")
     val sink = SinkAnnotation(ModuleName("X", CircuitName("Top")), "pin")
-    val top = TopAnnotation(ModuleName("Top", CircuitName("Top")), "pin")
     val input =
-      """circuit Top :
-        |  module Top :
-        |    input clk: Clock
-        |    inst x of X
-        |    reg r: UInt<5>, clk
-        |  extmodule X :
-        |    input clk: Clock
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clk: Clock
+         |    inst x of X
+         |    x.clk <= clk
+         |    reg r: UInt<5>, clk
+         |  extmodule X :
+         |    input clk: Clock
+         |""".stripMargin
     val check =
-      """circuit Top :
-        |  module Top :
-        |    input clk: Clock
-        |    inst x of X
-        |    reg r: UInt<5>, clk
-        |    wire r_0 : UInt<5>
-        |    r_0 <= r
-        |    x.pin <= r_0
-        |  extmodule X :
-        |    input clk: Clock
-        |    input pin: UInt<5>
-        |""".stripMargin
+      """|circuit Top :
+         |  module Top :
+         |    input clk: Clock
+         |    wire r_0 : UInt<5>
+         |    inst x of X
+         |    x.clk <= clk
+         |    reg r: UInt<5>, clk
+         |    x.pin <= r_0
+         |    r_0 <= r
+         |  extmodule X :
+         |    input clk: Clock
+         |    input pin: UInt<5>
+         |""".stripMargin
     val c = passes.foldLeft(parse(input)) {
       (c: Circuit, p: Pass) => p.run(c)
     }
     val wiringXForm = new WiringTransform()
-    val retC = wiringXForm.execute(CircuitState(c, LowForm, Some(AnnotationMap(Seq(source, sink, top))), None)).circuit
+    val retC = wiringXForm.execute(CircuitState(c, MidForm, Some(AnnotationMap(Seq(source, sink))), None)).circuit
+    (parse(retC.serialize).serialize) should be (parse(check).serialize)
+  }
+
+  it should "wire using Annotations with a sink component" in {
+    val source = SourceAnnotation(ComponentName("r", ModuleName("Top", CircuitName("Top"))), "pin")
+    val sink = SinkAnnotation(ComponentName("s", ModuleName("X", CircuitName("Top"))), "pin")
+    val input =
+      """|circuit Top :
+         |  module Top :
+         |    input clk: Clock
+         |    inst x of X
+         |    x.clk <= clk
+         |    reg r: UInt<5>, clk
+         |  module X :
+         |    input clk: Clock
+         |    wire s: UInt<5>
+         |""".stripMargin
+    val check =
+      """|circuit Top :
+         |  module Top :
+         |    input clk: Clock
+         |    wire r_0 : UInt<5>
+         |    inst x of X
+         |    x.clk <= clk
+         |    reg r: UInt<5>, clk
+         |    x.pin <= r_0
+         |    r_0 <= r
+         |  module X :
+         |    input clk: Clock
+         |    input pin: UInt<5>
+         |    wire s: UInt<5>
+         |    s <= pin
+         |""".stripMargin
+    val c = passes.foldLeft(parse(input)) {
+      (c: Circuit, p: Pass) => p.run(c)
+    }
+    val wiringXForm = new WiringTransform()
+    val retC = wiringXForm.execute(CircuitState(c, MidForm, Some(AnnotationMap(Seq(source, sink))), None)).circuit
+    (parse(retC.serialize).serialize) should be (parse(check).serialize)
+  }
+
+  it should "wire using annotations with Aggregate source" in {
+    val source = SourceAnnotation(ComponentName("bundle", ModuleName("A", CircuitName("Top"))), "pin")
+    val sink = SinkAnnotation(ModuleName("B", CircuitName("Top")), "pin")
+    val input =
+      """|circuit Top :
+         |  module Top :
+         |    input clock : Clock
+         |    inst a of A
+         |    inst b of B
+         |    a.clock <= clock
+         |    b.clock <= clock
+         |  module A :
+         |    input clock : Clock
+         |    wire bundle : {x : UInt<1>, y: UInt<1>, z: {zz : UInt<1>} }
+         |    bundle is invalid
+         |  module B :
+         |    input clock : Clock""".stripMargin
+    val check =
+      """|circuit Top :
+         |  module Top :
+         |    input clock : Clock
+         |    wire bundle : {x : UInt<1>, y: UInt<1>, z: {zz : UInt<1>} }
+         |    inst a of A
+         |    inst b of B
+         |    a.clock <= clock
+         |    b.clock <= clock
+         |    b.pin <= bundle
+         |    bundle <= a.bundle_0
+         |  module A :
+         |    input clock : Clock
+         |    output bundle_0 : {x : UInt<1>, y: UInt<1>, z: {zz : UInt<1>} }
+         |    wire bundle : {x : UInt<1>, y: UInt<1>, z: {zz : UInt<1>} }
+         |    bundle is invalid
+         |    bundle_0 <= bundle
+         |  module B :
+         |    input clock : Clock
+         |    input pin : {x : UInt<1>, y: UInt<1>, z: {zz : UInt<1>} }"""
+        .stripMargin
+    val c = passes.foldLeft(parse(input)) {
+      (c: Circuit, p: Pass) => p.run(c)
+    }
+    val wiringXForm = new WiringTransform()
+    val retC = wiringXForm.execute(CircuitState(c, MidForm, Some(AnnotationMap(Seq(source, sink))), None)).circuit
+    (parse(retC.serialize).serialize) should be (parse(check).serialize)
+  }
+
+  it should "wire one sink to multiple, disjoint extmodules" in {
+    val sinkX = Seq(ModuleName("X", CircuitName("Top")))
+    val sourceX = ComponentName("r.x", ModuleName("A", CircuitName("Top")))
+    val sinkY = Seq(ModuleName("Y", CircuitName("Top")))
+    val sourceY = ComponentName("r.x", ModuleName("A", CircuitName("Top")))
+    val wiSeq = Seq(
+      WiringInfo(sourceX, sinkX, "pin"),
+      WiringInfo(sourceY, sinkY, "pin"))
+    val input =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    reg r : {x: UInt<5>}, clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    inst y of Y
+         |    y.clock <= clock
+         |  extmodule X :
+         |    input clock: Clock
+         |  extmodule Y :
+         |    input clock: Clock
+         |""".stripMargin
+    val check =
+      """|circuit Top :
+         |  module Top :
+         |    input clock: Clock
+         |    inst a of A
+         |    a.clock <= clock
+         |  module A :
+         |    input clock: Clock
+         |    wire r_x_0: UInt<5>
+         |    wire r_x: UInt<5>
+         |    reg r: {x: UInt<5>}, clock
+         |    inst x of X
+         |    x.clock <= clock
+         |    inst y of Y
+         |    y.clock <= clock
+         |    x.pin <= r_x
+         |    r_x <= r.x
+         |    y.pin <= r_x_0
+         |    r_x_0 <= r.x
+         |  extmodule X :
+         |    input clock: Clock
+         |    input pin: UInt<5>
+         |  extmodule Y :
+         |    input clock: Clock
+         |    input pin: UInt<5>
+         |""".stripMargin
+    val c = passes.foldLeft(parse(input)) {
+      (c: Circuit, p: Pass) => p.run(c)
+    }
+    val wiringPass = new Wiring(wiSeq)
+    val retC = wiringPass.run(c)
     (parse(retC.serialize).serialize) should be (parse(check).serialize)
   }
 }
diff --git a/src/test/scala/firrtlTests/graph/EulerTourTests.scala b/src/test/scala/firrtlTests/graph/EulerTourTests.scala
new file mode 100644
index 00000000..0b69ce61
--- /dev/null
+++ b/src/test/scala/firrtlTests/graph/EulerTourTests.scala
@@ -0,0 +1,36 @@
+package firrtlTests.graph
+
+import firrtl.graph._
+import firrtlTests._
+
+class EulerTourTests extends FirrtlFlatSpec {
+
+  val top = "top"
+  val first_layer = Set("1a", "1b", "1c")
+  val second_layer = Set("2a", "2b", "2c")
+  val third_layer = Set("3a", "3b", "3c")
+  val last_null = Set.empty[String]
+
+  val m = Map(top -> first_layer) ++ first_layer.map{
+    case x => Map(x -> second_layer) }.flatten.toMap ++ second_layer.map{
+    case x => Map(x -> third_layer) }.flatten.toMap ++ third_layer.map{
+    case x => Map(x -> last_null) }.flatten.toMap
+
+  val graph = DiGraph(m)
+  val instances = graph.pathsInDAG(top).values.flatten
+  val tour = EulerTour(graph, top)
+
+  it should "show equivalency of Berkman--Vishkin and naive RMQs" in {
+    instances.toSeq.combinations(2).toList.map { case Seq(a, b) =>
+      tour.rmqNaive(a, b) should be (tour.rmqBV(a, b))
+    }
+  }
+
+  it should "determine naive RMQs of itself correctly" in {
+    instances.toSeq.map { case a => tour.rmqNaive(a, a) should be (a) }
+  }
+
+  it should "determine Berkman--Vishkin RMQs of itself correctly" in {
+    instances.toSeq.map { case a => tour.rmqNaive(a, a) should be (a) }
+  }
+}