Implement InstanceTarget Behavior for Dedup + EliminateTargetPaths (#1539)

- RenameMap Behavior
-- Prevent transitive renaming A -> B -> C (continueRenaming)
-- Prevent transitive renaming for self-renames

- Target
-- Override toString as serialize for CompleteTarget
-- Expansion of stripHierarchy to enable stripping InstanceTargets to become ModuleTargets
Annotations
-- Bugfix in extractComponents where Products were not iterated over
-- Converts renamed targets to local targets using Target.referringModule to preserve sticky behavior

- Eliminate Target Paths
-- Make DuplicationHelper use LinkedHashMap, as we iterate over its contents and convert to Seq in def makePathless
-- Add DupedResult to map original module to new module targets
-- Update renaming to record a map from all relative instance paths to original module, to new module target
-- Consumes DedupedResult to give better name to new duplicated module if it was originally deduplicated
-- Reorder modules in attempt to preserve original ordering, pre-deduplication
-- Move utility functions to object
-- Bugfix: add self-renames to prevent ofModule _ of target _ cannot be renamed to Vector(_, _, _, ...) errors

- Dedup
-- Changed NoDedupAnnotation to contain ModuleTarget, rather than ModuleName
-- Added DedupedResult to map original module to the duplicate module
-- Consumes DupedResult to pick better name, if it existed
-- Updates renaming to chain the following: instancify deduped modules, remap differently named internal signals, then remap AST modules
-- Move utility functions to object
-- Remove annotations as part of determination of dedup correctness
-- Bugfix: add instance renames so that deduped modules have their instances properly renamed

- Dead Code Elimination
-- Add deletion of ASTModules

- Tests
-- Morphism Spec to ensure Dedup -> EliminateTargetPaths and EliminateTargetPaths -> Dedup patterns work properly
-- Update existing tests to make sure they work properly
-- Add Dedup tests to demonstrate instance renaming bug, EliminateTargetPaths for ofModule rename bug, and update RenameMap tests

Co-authored-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>
Co-authored-by: Adam Izraelevitz <adam.izraelevitz@sifive.com>
Co-authored-by: Adam Izraelevitz <azidar@gmail.com>
Co-authored-by: Jack Koenig <koenig@sifive.com>

5 files changed, 912 insertions, 35 deletions

diff --git a/src/test/scala/firrtl/testutils/FirrtlSpec.scala b/src/test/scala/firrtl/testutils/FirrtlSpec.scala
index cab66332..09abf547 100644
--- a/src/test/scala/firrtl/testutils/FirrtlSpec.scala
+++ b/src/test/scala/firrtl/testutils/FirrtlSpec.scala
@@ -180,6 +180,9 @@ trait FirrtlRunners extends BackendCompilationUtilities {
 }
 
 trait FirrtlMatchers extends Matchers {
+  def dontTouch(ref: ReferenceTarget): DontTouchAnnotation = {
+    DontTouchAnnotation(ref)
+  }
   def dontTouch(path: String): Annotation = {
     val parts = path.split('.')
     require(parts.size >= 2, "Must specify both module and component!")
diff --git a/src/test/scala/firrtlTests/AnnotationTests.scala b/src/test/scala/firrtlTests/AnnotationTests.scala
index a898d216..2b347034 100644
--- a/src/test/scala/firrtlTests/AnnotationTests.scala
+++ b/src/test/scala/firrtlTests/AnnotationTests.scala
@@ -75,7 +75,7 @@ abstract class AnnotationTests extends AnnotationSpec with Matchers {
     val tname = transform.name
     val inlineAnn = InlineAnnotation(CircuitName("Top"))
     val result = compiler.compile(CircuitState(parse(input), ChirrtlForm, Seq(inlineAnn)), Seq(transform))
-    result.annotations.head should matchPattern {
+    result.annotations.last should matchPattern {
       case DeletedAnnotation(`tname`, `inlineAnn`) =>
     }
     val exception = (intercept[Exception] {
diff --git a/src/test/scala/firrtlTests/annotationTests/EliminateTargetPathsSpec.scala b/src/test/scala/firrtlTests/annotationTests/EliminateTargetPathsSpec.scala
index d4502edb..e1cadf32 100644
--- a/src/test/scala/firrtlTests/annotationTests/EliminateTargetPathsSpec.scala
+++ b/src/test/scala/firrtlTests/annotationTests/EliminateTargetPathsSpec.scala
@@ -5,8 +5,8 @@ package firrtlTests.annotationTests
 import firrtl._
 import firrtl.annotations._
 import firrtl.annotations.analysis.DuplicationHelper
-import firrtl.annotations.transforms.NoSuchTargetException
-import firrtl.transforms.DontTouchAnnotation
+import firrtl.annotations.transforms.{NoSuchTargetException}
+import firrtl.transforms.{DontTouchAnnotation, DedupedResult}
 import firrtl.testutils.{FirrtlMatchers, FirrtlPropSpec}
 
 object EliminateTargetPathsSpec {
@@ -70,7 +70,7 @@ class EliminateTargetPathsSpec extends FirrtlPropSpec with FirrtlMatchers {
 
   val inputState = CircuitState(parse(input), ChirrtlForm)
   property("Hierarchical tokens should be expanded properly") {
-    val dupMap = new DuplicationHelper(inputState.circuit.modules.map(_.name).toSet)
+    val dupMap = DuplicationHelper(inputState.circuit.modules.map(_.name).toSet)
 
 
     // Only a few instance references
@@ -314,6 +314,7 @@ class EliminateTargetPathsSpec extends FirrtlPropSpec with FirrtlMatchers {
     val checks =
       """circuit Top :
         |  module Middle :
+        |  module Middle_ :
         |  module Top :
         |  module Leaf___Middle__l :
         |  module Leaf____Middle__l :""".stripMargin.split("\n")
@@ -389,11 +390,24 @@ class EliminateTargetPathsSpec extends FirrtlPropSpec with FirrtlMatchers {
          |  module Foo:
          |    inst bar of Bar
          |    inst baz of Bar""".stripMargin
+    val check =
+      """|circuit Foo:
+         |  module Bar___Foo_bar:
+         |    node x = UInt<1>(0)
+         |    skip
+         |  module Bar:
+         |    node x = UInt<1>(0)
+         |    skip
+         |  module Foo:
+         |    inst bar of Bar___Foo_bar
+         |    inst baz of Bar""".stripMargin
     val Bar_x = CircuitTarget("Foo").module("Bar").ref("x")
     val output = CircuitState(passes.ToWorkingIR.run(Parser.parse(input)), UnknownForm, Seq(DontTouchAnnotation(Bar_x)))
       .resolvePaths(Seq(CircuitTarget("Foo").module("Foo").instOf("bar", "Bar")))
 
+    val parsedCheck = Parser.parse(check)
     info(output.circuit.serialize)
+    (output.circuit.serialize) should be (parsedCheck.serialize)
 
     val newBar_x = CircuitTarget("Foo").module("Bar___Foo_bar").ref("x")
 
@@ -481,4 +495,115 @@ class EliminateTargetPathsSpec extends FirrtlPropSpec with FirrtlMatchers {
       DontTouchAnnotation(ModuleTarget("FooBar", "Bar___Foo_barBar").ref("baz"))
     )
   }
+
+  property("It should use DedupedResult names") {
+    val input =
+      """|circuit Top:
+         |  module Baz:
+         |    skip
+         |  module Bar:
+         |    inst baz of Baz
+         |    inst bazzz of Baz
+         |    skip
+         |  module Top:
+         |    inst bar of Bar
+         |""".stripMargin
+    val checks =
+      """|circuit Top :
+         |  module Baz_0 :
+         |  module Baz_1 :
+         |    inst baz of Baz_0
+         |    inst bazzz of Baz_1
+         |""".stripMargin.split("\n")
+    val baz = CircuitTarget("Top").module("Top").instOf("bar", "Bar").instOf("baz", "Baz")
+    val bazzz = CircuitTarget("Top").module("Top").instOf("bar", "Bar").instOf("bazzz", "Baz")
+    val annos = Seq(
+      DedupedResult(ModuleTarget("Top", "Baz_0"), Some(baz), 0),
+      DedupedResult(ModuleTarget("Top", "Baz_1"), Some(bazzz), 1),
+      DontTouchAnnotation(baz.ref("foo")),
+      DontTouchAnnotation(bazzz.ref("foo"))
+    )
+    val inputCircuit = Parser.parse(input)
+    val output = CircuitState(passes.ToWorkingIR.run(inputCircuit), UnknownForm, annos)
+      .resolvePaths(Seq(baz, bazzz))
+
+    info(output.circuit.serialize)
+
+    val outputLines = output.circuit.serialize.split("\n")
+    checks.foreach { line =>
+      outputLines should contain (line)
+    }
+    output.annotations.collect {
+      case a: DontTouchAnnotation => a
+    } should contain allOf (
+      DontTouchAnnotation(ModuleTarget("Top", "Baz_0").ref("foo")),
+      DontTouchAnnotation(ModuleTarget("Top", "Baz_1").ref("foo"))
+    )
+  }
+
+  property("It should not rename untouched modules") {
+    val input =
+      """|circuit Top:
+         |  module Baz:
+         |    node foo = UInt<1>(0)
+         |  module Bar:
+         |    inst lkj of Baz
+         |    inst asdf of Baz
+         |  module Top:
+         |    inst bar of Bar
+         |    inst baz of Baz
+         |""".stripMargin
+    val asdf = ModuleTarget("Top", "Top").instOf("bar", "Bar").instOf("asdf", "Baz")
+    val lkj = ModuleTarget("Top", "Top").instOf("bar", "Bar").instOf("lkj", "Baz")
+    val baz = ModuleTarget("Top", "Top").instOf("baz", "Baz")
+    val annos = Seq(
+      DontTouchAnnotation(asdf.ref("foo")),
+      DontTouchAnnotation(lkj.ref("foo")),
+      DontTouchAnnotation(baz.ref("foo"))
+    )
+    val inputCircuit = Parser.parse(input)
+    val output = CircuitState(passes.ToWorkingIR.run(inputCircuit), UnknownForm, annos)
+      .resolvePaths(Seq(asdf, lkj))
+
+    info(output.circuit.serialize)
+
+    output.annotations.collect { case a: DontTouchAnnotation => a } should be (Seq(
+      DontTouchAnnotation(ModuleTarget("Top", "Baz___Bar_asdf").ref("foo")),
+      DontTouchAnnotation(ModuleTarget("Top", "Baz___Bar_lkj").ref("foo")),
+      DontTouchAnnotation(baz.ref("foo"))
+    ))
+  }
+
+  property("It should properly rename modules with multiple instances") {
+    val input =
+      """|circuit Top:
+         |  module Core:
+         |    node clock = UInt<1>(0)
+         |  module System:
+         |    inst core_1 of Core
+         |    inst core_2 of Core
+         |    inst core_3 of Core
+         |    inst core_4 of Core
+         |  module Top:
+         |    inst system of System
+         |""".stripMargin
+    val absCoreInstances = (1 to 4).map { i =>
+      ModuleTarget("Top", "Top").instOf("system", "System").instOf(s"core_$i", "Core")
+    }
+    val relCoreInstances = (1 to 4).map { i =>
+      ModuleTarget("Top", "System").instOf(s"core_$i", "Core")
+    }
+    val coreModule = ModuleTarget("Top", "Core")
+    val annos = (coreModule +: (relCoreInstances ++ absCoreInstances)).map(DummyAnnotation(_))
+    val inputCircuit = Parser.parse(input)
+    val output = CircuitState(passes.ToWorkingIR.run(inputCircuit), UnknownForm, annos)
+      .resolvePaths(relCoreInstances ++ absCoreInstances)
+
+    info(output.circuit.serialize)
+
+    val checkDontTouches = (1 to 4).map { i =>
+      DummyAnnotation(ModuleTarget("Top", s"Core___System_core_$i"))
+    }
+    output.annotations.collect { case a: DummyAnnotation => a } should be (checkDontTouches)
+  }
 }
diff --git a/src/test/scala/firrtlTests/annotationTests/MorphismSpec.scala b/src/test/scala/firrtlTests/annotationTests/MorphismSpec.scala
new file mode 100644
index 00000000..985779ab
--- /dev/null
+++ b/src/test/scala/firrtlTests/annotationTests/MorphismSpec.scala
@@ -0,0 +1,571 @@
+// See LICENSE for license details.
+
+package firrtlTests.annotationTests
+
+import firrtl._
+import firrtl.annotations.{Annotation, CircuitTarget, CompleteTarget, DeletedAnnotation}
+import firrtl.annotations.transforms.{DupedResult, ResolvePaths}
+import firrtl.transforms.DedupedResult
+import org.scalatest.{FlatSpec, Matchers}
+
+class MorphismSpec extends FlatSpec with Matchers {
+
+  object AnAnnotation {
+    def apply(target: CompleteTarget) = new AnAnnotation(Some(target))
+  }
+
+  case class AnAnnotation(
+                           target: Option[CompleteTarget],
+                           from: Option[AnAnnotation] = None,
+                           cause: Option[String] = None
+                         ) extends Annotation {
+    override def update(renames: RenameMap): Seq[AnAnnotation] = {
+      if (target.isDefined) {
+        renames.get(target.get) match {
+          case None => Seq(this)
+          case Some(Seq()) => Seq(AnAnnotation(None, Some(this)))
+          case Some(targets) =>
+            //TODO: Add cause of renaming, requires FIRRTL change to RenameMap
+            targets.map { t => AnAnnotation(Some(t), Some(this)) }
+        }
+      } else Seq(this)
+    }
+
+    private def expand(stringBuilder: StringBuilder): StringBuilder = {
+      if (target.isDefined) {
+        stringBuilder.append(s"${target.get.serialize}")
+      } else {
+        stringBuilder.append(s"<DELETED>")
+      }
+      if (from.isDefined) {
+        val arrow = cause.map("(" + _ + ")").getOrElse("")
+        stringBuilder.append(s" <-$arrow- ")
+        from.get.expand(stringBuilder)
+      }
+      stringBuilder
+    }
+
+    override def serialize: String = expand(new StringBuilder()).toString
+  }
+
+  object StripDeleted extends Transform {
+
+    override def inputForm = UnknownForm
+
+    override def outputForm = UnknownForm
+
+    override def execute(a: CircuitState): CircuitState = {
+
+      val annotationsx = a.annotations.filter {
+        case a: DeletedAnnotation => false
+        case AnAnnotation(None, _, _) => false
+        case _: DupedResult => false
+        case _: DedupedResult => false
+        case _ => true
+      }
+
+      a.copy(annotations = annotationsx)
+
+    }
+
+  }
+
+  trait CircuitFixture {
+
+    /** An input FIRRTL string */
+    val input: String
+
+    lazy val output: String = input
+
+    /** Input annotations */
+    val annotations: AnnotationSeq = Seq.empty
+
+    val finalAnnotations: Option[AnnotationSeq] = None
+
+    lazy val state = CircuitState(Parser.parse(input), UnknownForm, annotations)
+  }
+
+  trait RightInverseFixture extends CircuitFixture {
+
+    /** An endomorphism i.e. a function mapping from CircuitState to CircuitState */
+    val f: Seq[Transform]
+
+    /** The right inverse of f */
+    val g: Seq[Transform]
+
+    val setup: Seq[Transform] = Seq(
+      firrtl.passes.ToWorkingIR,
+      new firrtl.ResolveAndCheck
+    )
+
+    val cleanup: Seq[Transform] = Seq(
+      StripDeleted
+    )
+
+    def apply(a: CircuitState): CircuitState = {
+      val ax = (setup ++ f ++ g).foldLeft(a) {
+        case (state, transform) => transform.runTransform(state)
+      }
+
+      cleanup.foldLeft(ax) {
+        case (state, transform) => transform.transform(state)
+      }
+    }
+
+    lazy val outputState = apply(state)
+
+    def test(): Unit = {
+
+      /* The output circuit should be the same as the input circuit */
+      outputState.circuit.serialize should be(Parser.parse(output).serialize)
+      info("the circuits are the same")
+      info(state.circuit.serialize)
+
+      /* The output annotations should match the input annotations */
+      info(s"Input annotations:\n\t${state.annotations.toList.mkString("\n\t")}")
+      info(s"Output annotations:\n\t${outputState.annotations.toList.mkString("\n\t")}")
+      if (finalAnnotations.nonEmpty) {
+        info(s"Final annotations:\n\t${finalAnnotations.get.toList.mkString("\n\t")}")
+      }
+
+      info(s"Output Annotation History:\n")
+      outputState.annotations.collect {
+        case a: AnAnnotation => info(a.serialize)
+      }
+
+      val inputAnnotations = state.annotations.filter {
+        case r: ResolvePaths => false
+        case other => true
+      }
+
+      if (finalAnnotations.isEmpty) {
+        outputState.annotations.size should be(inputAnnotations.size)
+        info("the number of annotations is the same")
+
+        outputState.annotations.zip(inputAnnotations).collect {
+          case (a: AnAnnotation, b: AnAnnotation) => a.target should be(b.target)
+        }
+        info("each annotation is the same")
+      } else {
+        outputState.annotations.zip(finalAnnotations.get).collect {
+          case (a: AnAnnotation, b: AnAnnotation) => a.target should be(b.target)
+        }
+
+        outputState.annotations.size should be(finalAnnotations.get.size)
+        info("the number of annotations is the same")
+
+        info("each annotation is the same as the final annotations")
+      }
+    }
+
+  }
+
+  trait IdempotencyFixture extends CircuitFixture {
+
+    /** An endomorphism */
+    val f: Seq[Transform]
+
+    val setup: Seq[Transform] = Seq(
+      firrtl.passes.ToWorkingIR,
+      new firrtl.ResolveAndCheck
+    )
+
+    val cleanup: Seq[Transform] = Seq(
+      StripDeleted
+    )
+
+    def apply(a: CircuitState): (CircuitState, CircuitState) = {
+
+      val once = (setup ++ f).foldLeft(a) {
+        case (state, transform) => transform.runTransform(state)
+      }
+
+      val twice = f.foldLeft(once) {
+        case (state, transform) => transform.runTransform(state)
+      }
+
+      val onceClean = cleanup.foldLeft(once) {
+        case (state, transform) => transform.transform(state)
+      }
+
+      val twiceClean = cleanup.foldLeft(twice) {
+        case (state, transform) => transform.transform(state)
+      }
+
+      (onceClean, twiceClean)
+
+    }
+
+    lazy val (oneApplication, twoApplications) = apply(state)
+
+    def test(): Unit = {
+
+      info("a second application does not change the circuit")
+      twoApplications.circuit.serialize should be(oneApplication.circuit.serialize)
+
+      info("each annotation is the same after a second application")
+      twoApplications.annotations.zip(oneApplication.annotations).foreach {
+        case (a, b) => a should be(b)
+      }
+
+      info("the number of annotations after a second application is the same")
+      twoApplications.annotations.size should be(oneApplication.annotations.size)
+
+    }
+
+  }
+
+  trait DefaultExample extends CircuitFixture {
+    override val input =
+      """|circuit Top:
+         |  module Foo:
+         |    node a = UInt<1>(0)
+         |    skip
+         |  module Bop:
+         |    node a = UInt<1>(0)
+         |    skip
+         |  module Fub:
+         |    node a = UInt<1>(0)
+         |    skip
+         |  module Bar:
+         |    node a = UInt<1>(0)
+         |    skip
+         |  module Baz:
+         |    input x: UInt<1>
+         |    inst foo of Foo
+         |    inst bar of Bar
+         |  module Qux:
+         |    input x: UInt<1>
+         |    inst foo of Fub
+         |    inst bar of Bop
+         |  module Top:
+         |    inst baz of Baz
+         |    inst qux of Qux""".stripMargin
+
+    def deduped =
+      """|circuit Top:
+         |  module Foo:
+         |    node a = UInt<1>(0)
+         |    skip
+         |  module Baz:
+         |    input x: UInt<1>
+         |    inst foo of Foo
+         |    inst bar of Foo
+         |  module Top:
+         |    inst baz of Baz
+         |    inst qux of Baz""".stripMargin
+
+    def allModuleInstances =
+      IndexedSeq(
+        CircuitTarget("Top").module("Foo"),
+        CircuitTarget("Top").module("Bar"),
+        CircuitTarget("Top").module("Fub"),
+        CircuitTarget("Top").module("Bop"),
+        CircuitTarget("Top").module("Baz"),
+        CircuitTarget("Top").module("Qux"),
+        CircuitTarget("Top").module("Top")
+      )
+
+    def allAbsoluteInstances =
+      IndexedSeq(
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("foo", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("bar", "Bar"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Qux").instOf("foo", "Fub"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Qux").instOf("bar", "Bop"),
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Qux"),
+        CircuitTarget("Top").module("Top")
+      )
+
+    def allRelative2LevelInstances =
+      IndexedSeq(
+        CircuitTarget("Top").module("Baz").instOf("foo", "Foo"),
+        CircuitTarget("Top").module("Baz").instOf("bar", "Bar"),
+        CircuitTarget("Top").module("Qux").instOf("foo", "Fub"),
+        CircuitTarget("Top").module("Qux").instOf("bar", "Bop"),
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Qux"),
+        CircuitTarget("Top").module("Top")
+      )
+
+    def allDedupedAbsoluteInstances =
+      IndexedSeq(
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("foo", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("bar", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Baz").instOf("foo", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Baz").instOf("bar", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Baz"),
+        CircuitTarget("Top").module("Top")
+      )
+  }
+
+
+  behavior of "EliminateTargetPaths"
+
+  // NOTE: equivalience is defined structurally in this case
+  trait RightInverseEliminateTargetsFixture extends RightInverseFixture with DefaultExample {
+    override val f: Seq[Transform] = Seq(new firrtl.transforms.DedupModules)
+    override val g: Seq[Transform] = Seq(new firrtl.annotations.transforms.EliminateTargetPaths)
+  }
+  trait IdempotencyEliminateTargetsFixture extends IdempotencyFixture with DefaultExample {
+    override val f: Seq[Transform] = Seq(new firrtl.annotations.transforms.EliminateTargetPaths)
+  }
+
+  it should "invert DedupModules with no annotations" in new RightInverseEliminateTargetsFixture {
+    override val annotations: AnnotationSeq = Seq(
+      ResolvePaths(allAbsoluteInstances)
+    )
+    test()
+  }
+
+  it should "invert DedupModules with absolute InstanceTarget annotations" in new RightInverseEliminateTargetsFixture {
+    override val annotations: AnnotationSeq =
+      allAbsoluteInstances.map(AnAnnotation(_)) :+ ResolvePaths(allAbsoluteInstances)
+
+    override val finalAnnotations: Option[AnnotationSeq] = Some(
+      allModuleInstances.map(AnAnnotation.apply)
+    )
+    test()
+  }
+
+  it should "invert DedupModules with all ModuleTarget annotations" in new RightInverseEliminateTargetsFixture {
+    override val annotations: AnnotationSeq =
+      allModuleInstances.map(AnAnnotation.apply) :+ ResolvePaths(allAbsoluteInstances)
+    test()
+  }
+
+  it should "invert DedupModules with relative InstanceTarget annotations" in new RightInverseEliminateTargetsFixture {
+    override val annotations: AnnotationSeq =
+      allRelative2LevelInstances.map(AnAnnotation.apply) :+ ResolvePaths(allAbsoluteInstances)
+
+    override val finalAnnotations: Option[AnnotationSeq] = Some(
+      allModuleInstances.map(AnAnnotation.apply)
+    )
+    test()
+  }
+
+  it should "invert DedupModules with a ReferenceTarget annotation" in new RightInverseEliminateTargetsFixture {
+    override val annotations: AnnotationSeq = Seq(
+      AnAnnotation(CircuitTarget("Top").module("Top").ref("x")),
+      ResolvePaths(allAbsoluteInstances)
+    )
+    test()
+  }
+
+  it should "invert DedupModules with partially duplicated modules" in new RightInverseEliminateTargetsFixture {
+    override val input =
+      """|circuit Top:
+         |  module Foo:
+         |    node a = UInt<1>(0)
+         |    skip
+         |  module Bar:
+         |    node a = UInt<1>(0)
+         |    skip
+         |  module Baz:
+         |    input x: UInt<1>
+         |    inst foo of Foo
+         |    inst foox of Foo
+         |    inst bar of Bar
+         |  module Top:
+         |    inst baz of Baz
+         |    inst qux of Baz""".stripMargin
+    override lazy val output =
+      """|circuit Top :
+         |  module Foo___Top_baz_bar :
+         |    node a = UInt<1>("h0")
+         |    skip
+         |  module Foo___Top_qux_foox :
+         |    node a = UInt<1>("h0")
+         |    skip
+         |  module Foo___Top_qux_bar :
+         |    node a = UInt<1>("h0")
+         |    skip
+         |  module Foo___Top_baz_foox :
+         |    node a = UInt<1>("h0")
+         |    skip
+         |  module Foo___Top_baz_foo :
+         |    node a = UInt<1>("h0")
+         |    skip
+         |  module Foo___Top_qux_foo :
+         |    node a = UInt<1>("h0")
+         |    skip
+         |  module Baz___Top_baz :
+         |    input x : UInt<1>
+         |    inst foo of Foo___Top_baz_foo
+         |    inst foox of Foo___Top_baz_foox
+         |    inst bar of Foo___Top_baz_bar
+         |  module Baz___Top_qux :
+         |    input x : UInt<1>
+         |    inst foo of Foo___Top_qux_foo
+         |    inst foox of Foo___Top_qux_foox
+         |    inst bar of Foo___Top_qux_bar
+         |  module Top :
+         |    inst baz of Baz___Top_baz
+         |    inst qux of Baz___Top_qux""".stripMargin
+    override val annotations: AnnotationSeq = Seq(
+      AnAnnotation(CircuitTarget("Top").module("Baz").instOf("foo", "Foo")),
+      ResolvePaths(Seq(
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("foo", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("foox", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("bar", "Bar"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Baz").instOf("foo", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Baz").instOf("foox", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Baz").instOf("bar", "Bar")
+      ))
+    )
+
+    override val finalAnnotations: Option[AnnotationSeq] = Some(Seq(
+      AnAnnotation(CircuitTarget("Top").module("Foo___Top_qux_foo")),
+      AnAnnotation(CircuitTarget("Top").module("Foo___Top_baz_foo"))
+    ))
+    test()
+  }
+
+  it should "be idempotent with per-module annotations" in new IdempotencyEliminateTargetsFixture {
+    /** An endomorphism */
+    override val annotations: AnnotationSeq =
+      allModuleInstances.map(AnAnnotation.apply) :+ ResolvePaths(allAbsoluteInstances)
+    test()
+  }
+
+  it should "be idempotent with per-instance annotations" in new IdempotencyEliminateTargetsFixture {
+    /** An endomorphism */
+    override val annotations: AnnotationSeq =
+      allAbsoluteInstances.map(AnAnnotation.apply) :+ ResolvePaths(allAbsoluteInstances)
+    test()
+  }
+
+  it should "be idempotent with relative module annotations" in new IdempotencyEliminateTargetsFixture {
+    /** An endomorphism */
+    override val annotations: AnnotationSeq =
+      allRelative2LevelInstances.map(AnAnnotation.apply) :+ ResolvePaths(allAbsoluteInstances)
+    test()
+  }
+
+  behavior of "DedupModules"
+
+  trait RightInverseDedupModulesFixture extends RightInverseFixture with DefaultExample {
+    override val f: Seq[Transform] = Seq(new firrtl.annotations.transforms.EliminateTargetPaths)
+    override val g: Seq[Transform] = Seq(new firrtl.transforms.DedupModules)
+  }
+
+  trait IdempotencyDedupModulesFixture extends IdempotencyFixture with DefaultExample {
+    override val f: Seq[Transform] = Seq(new firrtl.transforms.DedupModules)
+  }
+
+  it should "invert EliminateTargetPaths with no annotations" in new RightInverseDedupModulesFixture {
+    override val annotations: AnnotationSeq = Seq(
+      ResolvePaths(allAbsoluteInstances)
+    )
+    override lazy val output = deduped
+
+    test()
+  }
+
+  it should "invert EliminateTargetPaths with absolute InstanceTarget annotations" in new RightInverseDedupModulesFixture {
+    override val annotations: AnnotationSeq =
+      allAbsoluteInstances.map(AnAnnotation(_)) :+ ResolvePaths(allAbsoluteInstances)
+    override val finalAnnotations: Option[AnnotationSeq] = Some(allDedupedAbsoluteInstances.map(AnAnnotation.apply))
+    override lazy val output = deduped
+    test()
+  }
+
+  it should "invert EliminateTargetPaths with all ModuleTarget annotations" in new RightInverseDedupModulesFixture {
+    override val annotations: AnnotationSeq =
+      allModuleInstances.map(AnAnnotation.apply) :+ ResolvePaths(allAbsoluteInstances)
+    override val finalAnnotations: Option[AnnotationSeq] = Some(
+      allDedupedAbsoluteInstances.map(AnAnnotation.apply)
+    )
+    override lazy val output = deduped
+    test()
+  }
+
+  it should "invert EliminateTargetPaths with partially duplicated modules" in new RightInverseDedupModulesFixture {
+    override val input =
+      """|circuit Top:
+         |  module Foo:
+         |    node a = UInt<1>(0)
+         |    skip
+         |  module Bar:
+         |    node a = UInt<1>(0)
+         |    skip
+         |  module Baz:
+         |    input x: UInt<1>
+         |    inst foo of Foo
+         |    inst foox of Foo
+         |    inst bar of Bar
+         |  module Top:
+         |    inst baz of Baz
+         |    inst qux of Baz""".stripMargin
+    override lazy val output =
+      """|circuit Top :
+         |  module Foo :
+         |    node a = UInt<1>("h0")
+         |    skip
+         |  module Baz :
+         |    input x : UInt<1>
+         |    inst foo of Foo
+         |    inst foox of Foo
+         |    inst bar of Foo
+         |  module Top :
+         |    inst baz of Baz
+         |    inst qux of Baz""".stripMargin
+    override val annotations: AnnotationSeq = Seq(
+      AnAnnotation(CircuitTarget("Top").module("Baz").instOf("foo", "Foo")),
+      ResolvePaths(Seq(
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("foo", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("foox", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("bar", "Bar"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Baz").instOf("foo", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Baz").instOf("foox", "Foo"),
+        CircuitTarget("Top").module("Top").instOf("qux", "Baz").instOf("bar", "Bar")
+      ))
+    )
+
+    override val finalAnnotations: Option[AnnotationSeq] = Some(Seq(
+      AnAnnotation(CircuitTarget("Top").module("Top").instOf("baz", "Baz").instOf("foo", "Foo")),
+      AnAnnotation(CircuitTarget("Top").module("Top").instOf("qux", "Baz").instOf("foo", "Foo"))
+    ))
+    test()
+  }
+
+  it should "be idempotent with per-module annotations" in new IdempotencyDedupModulesFixture {
+    /** An endomorphism */
+    override val annotations: AnnotationSeq =
+      allModuleInstances.map(AnAnnotation.apply) :+ ResolvePaths(allAbsoluteInstances)
+    test()
+  }
+
+  it should "be idempotent with per-instance annotations" in new IdempotencyDedupModulesFixture {
+    /** An endomorphism */
+    override val annotations: AnnotationSeq =
+      allAbsoluteInstances.map(AnAnnotation.apply) :+ ResolvePaths(allAbsoluteInstances)
+    test()
+  }
+
+  it should "be idempotent with relative module annotations" in new IdempotencyDedupModulesFixture {
+    /** An endomorphism */
+    override val annotations: AnnotationSeq =
+      allRelative2LevelInstances.map(AnAnnotation.apply) :+ ResolvePaths(allAbsoluteInstances)
+    test()
+  }
+
+  /*
+  //TODO: Future tests of GroupComponents + InlineInstances renaming
+  behavior of "GroupComponents"
+  it should "invert InlineInstances with not annotations" in (pending)
+  it should "invert InlineInstances with InstanceTarget annotations" in (pending)
+  it should "invert InlineInstances with a ModuleTarget annotation" in (pending)
+  it should "invert InlineInstances with a ReferenceTarget annotation" in (pending)
+  it should "be idempotent" in (pending)
+
+  behavior of "InlineInstances"
+  it should "invert GroupComponents with not annotations" in (pending)
+  it should "invert GroupComponents with InstanceTarget annotations" in (pending)
+  it should "invert GroupComponents with a ModuleTarget annotation" in (pending)
+  it should "invert GroupComponents with a ReferenceTarget annotation" in (pending)
+  it should "be idempotent" in (pending)
+   */
+
+}
diff --git a/src/test/scala/firrtlTests/transforms/DedupTests.scala b/src/test/scala/firrtlTests/transforms/DedupTests.scala
index 4cc19c9d..6e0be81d 100644
--- a/src/test/scala/firrtlTests/transforms/DedupTests.scala
+++ b/src/test/scala/firrtlTests/transforms/DedupTests.scala
@@ -8,7 +8,6 @@ import firrtl.annotations._
 import firrtl.transforms.{DedupModules, NoCircuitDedupAnnotation}
 import firrtl.testutils._
 
-
 /**
  * Tests inline instances transformation
  */
@@ -318,7 +317,7 @@ class DedupModuleTests extends HighTransformSpec {
     execute(input, check, Seq.empty)
   }
 
-  "The module A and A_" should "not be deduped with different annotation targets" in {
+  "The module A and A_" should "dedup with different annotation targets" in {
     val input =
       """circuit Top :
         |  module Top :
@@ -337,15 +336,11 @@ class DedupModuleTests extends HighTransformSpec {
       """circuit Top :
         |  module Top :
         |    inst a1 of A
-        |    inst a2 of A_
+        |    inst a2 of A
         |  module A :
         |    output x: UInt<1>
         |    wire b: UInt<1>
         |    x <= b
-        |  module A_ :
-        |    output x: UInt<1>
-        |    wire b: UInt<1>
-        |    x <= b
       """.stripMargin
     execute(input, check, Seq(dontTouch("A.b")))
   }
@@ -375,7 +370,13 @@ class DedupModuleTests extends HighTransformSpec {
         |    wire b: UInt<1>
         |    x <= b
       """.stripMargin
-    execute(input, check, Seq(dontTouch("A.b"), dontTouch("A_.b")))
+    val cs = execute(input, check, Seq(
+      dontTouch(ReferenceTarget("Top", "A", Nil, "b", Nil)),
+      dontTouch(ReferenceTarget("Top", "A_", Nil, "b", Nil))
+    ))
+    cs.annotations.toSeq should contain (dontTouch(ModuleTarget("Top", "Top").instOf("a1", "A").ref("b")))
+    cs.annotations.toSeq should contain (dontTouch(ModuleTarget("Top", "Top").instOf("a2", "A").ref("b")))
+    cs.annotations.toSeq should not contain dontTouch(ReferenceTarget("Top", "A_", Nil, "b", Nil))
   }
   "The module A and A_" should "be deduped with same annotation targets when there are a lot" in {
     val input =
@@ -405,7 +406,7 @@ class DedupModuleTests extends HighTransformSpec {
     val annos = (0 until 100).flatMap(i => Seq(dontTouch(s"A.b[$i]"), dontTouch(s"A_.b[$i]")))
     execute(input, check, annos)
   }
-  "The module A and A_" should "not be deduped with same annotations with same multi-targets, but which have different root modules" in {
+  "The module A and A_" should "be deduped with same annotations with same multi-targets" in {
     val input =
       """circuit Top :
         |  module Top :
@@ -430,32 +431,33 @@ class DedupModuleTests extends HighTransformSpec {
       """circuit Top :
         |  module Top :
         |    inst a1 of A
-        |    inst a2 of A_
+        |    inst a2 of A
         |  module A :
         |    output x: UInt<1>
         |    inst b of B
         |    x <= b.x
-        |  module A_ :
-        |    output x: UInt<1>
-        |    inst b of B_
-        |    x <= b.x
         |  module B :
         |    output x: UInt<1>
         |    x <= UInt(1)
-        |  module B_ :
-        |    output x: UInt<1>
-        |    x <= UInt(1)
       """.stripMargin
     val Top = CircuitTarget("Top")
     val A = Top.module("A")
     val B = Top.module("B")
     val A_ = Top.module("A_")
     val B_ = Top.module("B_")
+    val Top_a1 = Top.module("Top").instOf("a1", "A")
+    val Top_a2 = Top.module("Top").instOf("a2", "A")
+    val Top_a1_b = Top_a1.instOf("b", "B")
+    val Top_a2_b = Top_a2.instOf("b", "B")
     val annoAB = MultiTargetDummyAnnotation(Seq(A, B), 0)
-    val annoA_B_ = MultiTargetDummyAnnotation(Seq(A_, B_), 0)
+    val annoA_B_ = MultiTargetDummyAnnotation(Seq(A_, B_), 1)
     val cs = execute(input, check, Seq(annoAB, annoA_B_))
-    cs.annotations.toSeq should contain (annoAB)
-    cs.annotations.toSeq should contain (annoA_B_)
+    cs.annotations.toSeq should contain (MultiTargetDummyAnnotation(Seq(
+      Top_a1, Top_a1_b
+    ), 0))
+    cs.annotations.toSeq should contain (MultiTargetDummyAnnotation(Seq(
+      Top_a2, Top_a2_b
+    ), 1))
   }
   "The module A and A_" should "be deduped with same annotations with same multi-targets, that share roots" in {
     val input =
@@ -495,42 +497,58 @@ class DedupModuleTests extends HighTransformSpec {
     val A = Top.module("A")
     val A_ = Top.module("A_")
     val annoA = MultiTargetDummyAnnotation(Seq(A, A.instOf("b", "B")), 0)
-    val annoA_ = MultiTargetDummyAnnotation(Seq(A_, A_.instOf("b", "B_")), 0)
+    val annoA_ = MultiTargetDummyAnnotation(Seq(A_, A_.instOf("b", "B_")), 1)
     val cs = execute(input, check, Seq(annoA, annoA_))
-    cs.annotations.toSeq should contain (annoA)
-    cs.annotations.toSeq should not contain (annoA_)
+    cs.annotations.toSeq should contain (MultiTargetDummyAnnotation(Seq(
+      Top.module("Top").instOf("a1", "A"),
+      Top.module("Top").instOf("a1", "A").instOf("b", "B")
+    ),0))
+    cs.annotations.toSeq should contain (MultiTargetDummyAnnotation(Seq(
+      Top.module("Top").instOf("a2", "A"),
+      Top.module("Top").instOf("a2", "A").instOf("b", "B")
+    ),1))
     cs.deletedAnnotations.isEmpty should be (true)
   }
-  "The deduping module A and A_" should "renamed internal signals that have different names" in {
+  "The deduping module A and A_" should "rename internal signals that have different names" in {
     val input =
       """circuit Top :
         |  module Top :
         |    inst a1 of A
+        |    a1 is invalid
         |    inst a2 of A_
+        |    a2 is invalid
         |  module A :
+        |    input x: UInt<1>
         |    output y: UInt<1>
-        |    y <= UInt(1)
+        |    node a = add(x, UInt(1))
+        |    y <= add(a, a)
         |  module A_ :
-        |    output x: UInt<1>
-        |    x <= UInt(1)
+        |    input x: UInt<1>
+        |    output y: UInt<1>
+        |    node b = add(x, UInt(1))
+        |    y <= add(b, b)
       """.stripMargin
     val check =
       """circuit Top :
         |  module Top :
         |    inst a1 of A
+        |    a1 is invalid
         |    inst a2 of A
+        |    a2 is invalid
         |  module A :
+        |    input x: UInt<1>
         |    output y: UInt<1>
-        |    y <= UInt<1>("h1")
+        |    node a = add(x, UInt<1>("h1"))
+        |    y <= add(a, a)
       """.stripMargin
     val Top = CircuitTarget("Top")
     val A = Top.module("A")
     val A_ = Top.module("A_")
-    val annoA = SingleTargetDummyAnnotation(A.ref("y"))
-    val annoA_ = SingleTargetDummyAnnotation(A_.ref("x"))
+    val annoA  = SingleTargetDummyAnnotation(A.ref("a"))
+    val annoA_ = SingleTargetDummyAnnotation(A_.ref("b"))
     val cs = execute(input, check, Seq(annoA, annoA_))
     cs.annotations.toSeq should contain (annoA)
-    cs.annotations.toSeq should not contain (SingleTargetDummyAnnotation(A.ref("x")))
+    cs.annotations.toSeq should not contain (SingleTargetDummyAnnotation(A.ref("b")))
     cs.deletedAnnotations.isEmpty should be (true)
   }
   "main" should "not be deduped even if it's the last module" in {
@@ -583,5 +601,165 @@ class DedupModuleTests extends HighTransformSpec {
       """.stripMargin
     execute(input, check, Seq(NoCircuitDedupAnnotation))
   }
+
+  "The deduping module A and A_" should "rename instances and signals that have different names" in {
+    val input =
+      """circuit Top :
+        |  module Top :
+        |    inst a of A
+        |    inst a_ of A_
+        |  module A :
+        |    inst b of B
+        |  module A_ :
+        |    inst b_ of B_
+        |  module B :
+        |    node foo = UInt<1>(0)
+        |  module B_ :
+        |    node bar = UInt<1>(0)
+      """.stripMargin
+    val check =
+      """circuit Top :
+        |  module Top :
+        |    inst a of A
+        |    inst a_ of A
+        |  module A :
+        |    inst b of B
+        |  module B :
+        |    node foo = UInt<1>(0)
+      """.stripMargin
+    val Top = CircuitTarget("Top")
+    val inst1 = Top.module("Top").instOf("a", "A").instOf("b", "B")
+    val inst2 = Top.module("Top").instOf("a_", "A_").instOf("b_", "B_")
+    val ref1 = Top.module("Top").instOf("a", "A").instOf("b", "B").ref("foo")
+    val ref2 = Top.module("Top").instOf("a_", "A_").instOf("b_", "B_").ref("bar")
+    val anno1 = MultiTargetDummyAnnotation(Seq(inst1, ref1), 0)
+    val anno2 = MultiTargetDummyAnnotation(Seq(inst2, ref2), 1)
+    val cs = execute(input, check, Seq(anno1, anno2))
+    cs.annotations.toSeq should contain (MultiTargetDummyAnnotation(Seq(
+      inst1, ref1
+    ),0))
+    cs.annotations.toSeq should contain (MultiTargetDummyAnnotation(Seq(
+      Top.module("Top").instOf("a_", "A").instOf("b", "B"),
+      Top.module("Top").instOf("a_", "A").instOf("b", "B").ref("foo")
+    ),1))
+    cs.deletedAnnotations.isEmpty should be (true)
+  }
+
+  "The deduping module A and A_" should "rename nested instances that have different names" in {
+    val input =
+      """circuit Top :
+        |  module Top :
+        |    inst a of A
+        |    inst a_ of A_
+        |  module A :
+        |    inst b of B
+        |  module A_ :
+        |    inst b_ of B_
+        |  module B :
+        |    inst c of C
+        |  module B_ :
+        |    inst c_ of C_
+        |  module C :
+        |    inst d of D
+        |  module C_ :
+        |    inst d_ of D_
+        |  module D :
+        |    node foo = UInt<1>(0)
+        |  module D_ :
+        |    node bar = UInt<1>(0)
+      """.stripMargin
+    val check =
+      """circuit Top :
+        |  module Top :
+        |    inst a of A
+        |    inst a_ of A
+        |  module A :
+        |    inst b of B
+        |  module B :
+        |    inst c of C
+        |  module C :
+        |    inst d of D
+        |  module D :
+        |    node foo = UInt<1>(0)
+      """.stripMargin
+    val Top = CircuitTarget("Top")
+    val inst1 = Top.module("Top").instOf("a", "A").instOf("b", "B").instOf("c", "C").instOf("d", "D")
+    val inst2 = Top.module("Top").instOf("a_", "A_").instOf("b_", "B_").instOf("c_", "C_").instOf("d_", "D_")
+    val ref1 = Top.module("Top").instOf("a", "A").instOf("b", "B").instOf("c", "C").instOf("d", "D").ref("foo")
+    val ref2 = Top.module("Top").instOf("a_", "A_").instOf("b_", "B_").instOf("c_", "C_").instOf("d_", "D_").ref("bar")
+    val anno1 = MultiTargetDummyAnnotation(Seq(inst1, ref1), 0)
+    val anno2 = MultiTargetDummyAnnotation(Seq(inst2, ref2), 1)
+    val cs = execute(input, check, Seq(anno1, anno2))
+    cs.annotations.toSeq should contain (MultiTargetDummyAnnotation(Seq(
+      inst1, ref1
+    ),0))
+    cs.annotations.toSeq should contain (MultiTargetDummyAnnotation(Seq(
+      Top.module("Top").instOf("a_", "A").instOf("b", "B").instOf("c", "C").instOf("d", "D"),
+      Top.module("Top").instOf("a_", "A").instOf("b", "B").instOf("c", "C").instOf("d", "D").ref("foo")
+    ),1))
+    cs.deletedAnnotations.isEmpty should be (true)
+  }
+
+  "Deduping modules with multiple instances" should "corectly rename instances" in {
+    val input =
+      """circuit Top :
+        |  module Top :
+        |    inst b of B
+        |    inst b_ of B_
+        |    inst a1 of A
+        |    inst a2 of A
+        |  module A :
+        |    inst b of B
+        |    inst b_ of B_
+        |  module B :
+        |    inst c of C
+        |  module B_ :
+        |    inst c of C
+        |  module C :
+        |    skip
+      """.stripMargin
+    val check =
+      """circuit Top :
+        |  module Top :
+        |    inst b of B
+        |    inst b_ of B
+        |    inst a1 of A
+        |    inst a2 of A
+        |  module A :
+        |    inst b of B
+        |    inst b_ of B
+        |  module B :
+        |    inst c of C
+        |  module C :
+        |    skip
+      """.stripMargin
+    val Top = CircuitTarget("Top").module("Top")
+    val bInstances = Seq(
+      Top.instOf("b", "B"),
+      Top.instOf("b_", "B_"),
+      Top.instOf("a1", "A").instOf("b_", "B_"),
+      Top.instOf("a2", "A").instOf("b_", "B_"),
+      Top.instOf("a1", "A").instOf("b", "B"),
+      Top.instOf("a2", "A").instOf("b", "B")
+    )
+    val cInstances = bInstances.map(_.instOf("c", "C"))
+    val annos = MultiTargetDummyAnnotation(bInstances ++ cInstances, 0)
+    val cs = execute(input, check, Seq(annos))
+    cs.annotations.toSeq should contain (MultiTargetDummyAnnotation(Seq(
+      Top.instOf("b", "B"),
+      Top.instOf("b_", "B"),
+      Top.instOf("a1", "A").instOf("b_", "B"),
+      Top.instOf("a2", "A").instOf("b_", "B"),
+      Top.instOf("a1", "A").instOf("b", "B"),
+      Top.instOf("a2", "A").instOf("b", "B"),
+      Top.instOf("b", "B").instOf("c", "C"),
+      Top.instOf("b_", "B").instOf("c", "C"),
+      Top.instOf("a1", "A").instOf("b_", "B").instOf("c", "C"),
+      Top.instOf("a2", "A").instOf("b_", "B").instOf("c", "C"),
+      Top.instOf("a1", "A").instOf("b", "B").instOf("c", "C"),
+      Top.instOf("a2", "A").instOf("b", "B").instOf("c", "C")
+    ),0))
+    cs.deletedAnnotations.isEmpty should be (true)
+  }
 }