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>

10 files changed, 1340 insertions, 170 deletions

diff --git a/src/main/scala/firrtl/annotations/Annotation.scala b/src/main/scala/firrtl/annotations/Annotation.scala
index 4c39bfee..fcbcdc96 100644
--- a/src/main/scala/firrtl/annotations/Annotation.scala
+++ b/src/main/scala/firrtl/annotations/Annotation.scala
@@ -27,7 +27,8 @@ trait Annotation extends Product {
   private def extractComponents(ls: scala.collection.Traversable[_]): Seq[Target] = {
     ls.collect {
       case c: Target => Seq(c)
-      case ls: scala.collection.Traversable[_] => extractComponents(ls)
+      case o: Product => extractComponents(o.productIterator.toIterable)
+      case x: scala.collection.Traversable[_] => extractComponents(x)
     }.foldRight(Seq.empty[Target])((seq, c) => c ++ seq)
   }
 
@@ -59,29 +60,39 @@ trait SingleTargetAnnotation[T <: Named] extends Annotation {
       case c: Target =>
         val x = renames.get(c)
         x.map(newTargets => newTargets.map(t => duplicate(t.asInstanceOf[T]))).getOrElse(List(this))
-      case _: Named =>
+      case from: Named =>
         val ret = renames.get(Target.convertNamed2Target(target))
-        ret.map(_.map(newT => Target.convertTarget2Named(newT: @unchecked) match {
-          case newTarget: T @unchecked =>
-            try {
-              duplicate(newTarget)
-            }
-            catch {
-              case _: java.lang.ClassCastException =>
-                val msg = s"${this.getClass.getName} target ${target.getClass.getName} " +
-                  s"cannot be renamed to ${newTarget.getClass}"
-                throw AnnotationException(msg)
-            }
-        })).getOrElse(List(this))
+        ret.map(_.map { newT =>
+          val result = newT match {
+            case c: InstanceTarget => ModuleName(c.ofModule, CircuitName(c.circuit))
+            case c: IsMember =>
+              val local = Target.referringModule(c)
+              c.setPathTarget(local)
+            case c: CircuitTarget => c.toNamed
+            case other => throw Target.NamedException(s"Cannot convert $other to [[Named]]")
+          }
+          Target.convertTarget2Named(result) match {
+            case newTarget: T @unchecked =>
+              try {
+                duplicate(newTarget)
+              }
+              catch {
+                case _: java.lang.ClassCastException =>
+                  val msg = s"${this.getClass.getName} target ${target.getClass.getName} " +
+                    s"cannot be renamed to ${newTarget.getClass}"
+                  throw AnnotationException(msg)
+              }
+          }
+        }).getOrElse(List(this))
     }
   }
 }
 
 /** [[MultiTargetAnnotation]] keeps the renamed targets grouped within a single annotation. */
 trait MultiTargetAnnotation extends Annotation {
-  /** Contains a sequence of [[Target]].
+  /** Contains a sequence of targets.
     * When created, [[targets]] should be assigned by `Seq(Seq(TargetA), Seq(TargetB), Seq(TargetC))`
-    * */
+    */
   val targets: Seq[Seq[Target]]
 
   /** Create another instance of this Annotation*/
diff --git a/src/main/scala/firrtl/annotations/Target.scala b/src/main/scala/firrtl/annotations/Target.scala
index 10c74e77..f33a8fdf 100644
--- a/src/main/scala/firrtl/annotations/Target.scala
+++ b/src/main/scala/firrtl/annotations/Target.scala
@@ -366,6 +366,9 @@ trait CompleteTarget extends Target {
   def addHierarchy(root: String, instance: String): IsComponent
 
   override def toTarget: CompleteTarget = this
+
+  // Very useful for debugging, I (@azidar) think this is reasonable
+  override def toString = serialize
 }
 
 
@@ -668,10 +671,14 @@ case class InstanceTarget(circuit: String,
   override def instOf(inst: String, of: String): InstanceTarget = InstanceTarget(circuit, module, asPath, inst, of)
 
   override def stripHierarchy(n: Int): IsModule = {
-    require(path.size >= n, s"Cannot strip $n levels of hierarchy from $this")
+    require(path.size + 1 >= n, s"Cannot strip $n levels of hierarchy from $this")
     if(n == 0) this else {
-      val newModule = path(n - 1)._2.value
-      InstanceTarget(circuit, newModule, path.drop(n), instance, ofModule)
+      if(path.size < n){
+        ModuleTarget(circuit, ofModule)
+      } else {
+        val newModule = path(n - 1)._2.value
+        InstanceTarget(circuit, newModule, path.drop(n), instance, ofModule)
+      }
     }
   }
 
diff --git a/src/main/scala/firrtl/annotations/analysis/DuplicationHelper.scala b/src/main/scala/firrtl/annotations/analysis/DuplicationHelper.scala
index f892c508..8f925ee7 100644
--- a/src/main/scala/firrtl/annotations/analysis/DuplicationHelper.scala
+++ b/src/main/scala/firrtl/annotations/analysis/DuplicationHelper.scala
@@ -12,24 +12,25 @@ import scala.collection.mutable
   * Calculates needed modifications to a circuit's module/instance hierarchy
   */
 case class DuplicationHelper(existingModules: Set[String]) {
+
   // Maps instances to the module it instantiates (an ofModule)
-  type InstanceOfModuleMap = mutable.HashMap[Instance, OfModule]
+  type InstanceOfModuleMap = mutable.LinkedHashMap[Instance, OfModule]
 
   // Maps a module to the instance/ofModules it instantiates
-  type ModuleHasInstanceOfModuleMap = mutable.HashMap[String, InstanceOfModuleMap]
+  type ModuleHasInstanceOfModuleMap = mutable.LinkedHashMap[String, InstanceOfModuleMap]
 
   // Maps original module names to new duplicated modules and their encapsulated instance/ofModules
-  type DupMap = mutable.HashMap[String, ModuleHasInstanceOfModuleMap]
+  type DupMap = mutable.LinkedHashMap[String, ModuleHasInstanceOfModuleMap]
 
   // Internal state to keep track of how paths duplicate
   private val dupMap = new DupMap()
 
   // Internal record of which paths are renamed to which new names, in the case of a collision
-  private val cachedNames = mutable.HashMap[(String, Seq[(Instance, OfModule)]), String]() ++
+  private val cachedNames = mutable.LinkedHashMap[(String, Seq[(Instance, OfModule)]), String]() ++
     existingModules.map(m => (m, Nil) -> m)
 
   // Internal record of all paths to ensure unique name generation
-  private val allModules = mutable.HashSet[String]() ++ existingModules
+  private val allModules = mutable.LinkedHashSet[String]() ++ existingModules
 
   /** Updates internal state (dupMap) to calculate instance hierarchy modifications so t's tokens in an instance can be
     * expressed as a tokens in a module (e.g. uniquify/duplicate the instance path in t's tokens)
diff --git a/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala b/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala
index a4cd2f3d..6bafa071 100644
--- a/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala
+++ b/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala
@@ -9,9 +9,10 @@ import firrtl.annotations.TargetToken.{Instance, OfModule, fromDefModuleToTarget
 import firrtl.annotations.analysis.DuplicationHelper
 import firrtl.annotations._
 import firrtl.ir._
-import firrtl.{CircuitState, DependencyAPIMigration, FirrtlInternalException, RenameMap, Transform, WDefInstance}
+import firrtl.{AnnotationSeq, CircuitState, DependencyAPIMigration, FirrtlInternalException, RenameMap, Transform}
 import firrtl.options.PreservesAll
 import firrtl.stage.Forms
+import firrtl.transforms.DedupedResult
 
 import scala.collection.mutable
 
@@ -26,8 +27,66 @@ case class ResolvePaths(targets: Seq[CompleteTarget]) extends Annotation {
   }
 }
 
+/** Holds the mapping from original module to the new, duplicated modules
+  * The original module target is unaffected by renaming
+  * @param newModules Instance target of what the original module now points to
+  * @param originalModule Original module
+  */
+case class DupedResult(newModules: Set[IsModule], originalModule: ModuleTarget) extends MultiTargetAnnotation {
+  override val targets: Seq[Seq[Target]] = Seq(newModules.toSeq)
+  override def duplicate(n: Seq[Seq[Target]]): Annotation = {
+    n.toList match {
+      case Seq(newMods) => DupedResult(newMods.collect { case x: IsModule => x }.toSet, originalModule)
+      case _ => DupedResult(Set.empty, originalModule)
+    }
+  }
+}
+
 case class NoSuchTargetException(message: String) extends FirrtlInternalException(message)
 
+object EliminateTargetPaths {
+
+  def renameModules(c: Circuit, toRename: Map[String, String], renameMap: RenameMap): Circuit = {
+    val ct = CircuitTarget(c.main)
+    val cx = if(toRename.contains(c.main)) {
+      renameMap.record(ct, CircuitTarget(toRename(c.main)))
+      c.copy(main = toRename(c.main))
+    } else {
+      c
+    }
+    def onMod(m: DefModule): DefModule = {
+      m map onStmt match {
+        case e: ExtModule if toRename.contains(e.name) =>
+          renameMap.record(ct.module(e.name), ct.module(toRename(e.name)))
+          e.copy(name = toRename(e.name))
+        case e: Module if toRename.contains(e.name)    =>
+          renameMap.record(ct.module(e.name), ct.module(toRename(e.name)))
+          e.copy(name = toRename(e.name))
+        case o => o
+      }
+    }
+    def onStmt(s: Statement): Statement = s map onStmt match {
+      case w@DefInstance(info, name, module, _) if toRename.contains(module) => w.copy(module = toRename(module))
+      case other => other
+    }
+    cx map onMod
+  }
+
+  def reorderModules(c: Circuit, toReorder: Map[String, Double]): Circuit = {
+    val newOrderMap = c.modules.zipWithIndex.map {
+      case (m, _) if toReorder.contains(m.name) => m.name -> toReorder(m.name)
+      case (m, i) if c.modules.size > 1 => m.name -> i.toDouble / (c.modules.size - 1)
+      case (m, _) => m.name -> 1.0
+    }.toMap
+
+    val newOrder = c.modules.sortBy { m => newOrderMap(m.name) }
+
+    c.copy(modules = newOrder)
+  }
+
+
+}
+
 /** For a set of non-local targets, modify the instance/module hierarchy of the circuit such that
   * the paths in each non-local target can be removed
   *
@@ -44,6 +103,7 @@ case class NoSuchTargetException(message: String) extends FirrtlInternalExceptio
   * C/x -> (C/x, C_/x) // where x is any reference in C
   */
 class EliminateTargetPaths extends Transform with DependencyAPIMigration with PreservesAll[Transform] {
+  import EliminateTargetPaths._
 
   override def prerequisites = Forms.MinimalHighForm
   override def optionalPrerequisites = Seq.empty
@@ -62,9 +122,6 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration with Pr
     case d@DefInstance(_, name, module, _) =>
       val ofModule = dupMap.getNewOfModule(originalModule, newModule, Instance(name), OfModule(module)).value
       d.copy(module = ofModule)
-    case d@WDefInstance(_, name, module, _) =>
-      val ofModule = dupMap.getNewOfModule(originalModule, newModule, Instance(name), OfModule(module)).value
-      d.copy(module = ofModule)
     case other => other map onStmt(dupMap)(originalModule, newModule)
   }
 
@@ -73,7 +130,10 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration with Pr
     * @param targets
     * @return
     */
-  def run(cir: Circuit, targets: Seq[IsMember]): (Circuit, RenameMap) = {
+  def run(cir: Circuit,
+          targets: Seq[IsMember],
+          iGraph: InstanceGraph
+         ): (Circuit, RenameMap, AnnotationSeq) = {
 
     val dupMap = DuplicationHelper(cir.modules.map(_.name).toSet)
 
@@ -85,8 +145,11 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration with Pr
 
     // Foreach module, calculate the unique names of its duplicates
     // Then, update the ofModules of instances that it encapsulates
-    cir.modules.foreach { m =>
-      dupMap.getDuplicates(m.name).foreach { newName =>
+
+    val ct = CircuitTarget(cir.main)
+    val annos = cir.modules.map { m =>
+      val newNames = dupMap.getDuplicates(m.name)
+      newNames.foreach { newName =>
         val newM = m match {
           case e: ExtModule => e.copy(name = newName)
           case o: Module =>
@@ -94,6 +157,7 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration with Pr
         }
         duplicatedModuleList += newM
       }
+      DupedResult(newNames.map(ct.module), ct.module(m.name))
     }
 
     val finalModuleList = duplicatedModuleList
@@ -105,34 +169,74 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration with Pr
     /* Foreach target, calculate the pathless version and only rename targets that are instantiated. Additionally, rename
      * module targets
      */
+    def addRecord(old: IsMember, newPathless: IsMember): Unit = old match {
+      case x: ModuleTarget =>
+        renameMap.record(x, newPathless)
+      case x: IsComponent if x.path.isEmpty =>
+        renameMap.record(x, newPathless)
+      case x: IsComponent =>
+        renameMap.record(x, newPathless)
+        addRecord(x.stripHierarchy(1), newPathless)
+    }
+    val duplicatedParents = mutable.Set[OfModule]()
     targets.foreach { t =>
-      val newTsx = dupMap.makePathless(t)
-      val newTs = newTsx
-      if(newTs.nonEmpty) {
-        renameMap.record(t, newTs)
-        val m = Target.referringModule(t)
-        val duplicatedModules = newTs.map(Target.referringModule)
-        val oldModule: Option[ModuleTarget] = m match {
-          case a: ModuleTarget if finalModuleSet(a.module) => Some(a)
-          case _                                           => None
+      val newTs = dupMap.makePathless(t)
+      val path = t.asPath
+      if (path.nonEmpty) { duplicatedParents += path(0)._2 }
+      newTs.toList match {
+        case Seq(pathless) =>
+          val mt = Target.referringModule(pathless)
+          addRecord(t, pathless)
+          renameMap.record(Target.referringModule(t), mt)
+        case _ =>
+      }
+    }
+
+    def addSelfRecord(mod: IsModule): Unit = mod match {
+      case m: ModuleTarget =>
+      case i: InstanceTarget if renameMap.underlying.contains(i) =>
+      case i: InstanceTarget =>
+        renameMap.record(i, i)
+        addSelfRecord(i.stripHierarchy(1))
+    }
+    val topMod = ModuleTarget(cir.main, cir.main)
+    duplicatedParents.foreach { parent =>
+      val paths = iGraph.findInstancesInHierarchy(parent.value)
+      val newTargets = paths.map { path =>
+        path.tail.foldLeft(topMod: IsModule) { case (mod, wDefInst) =>
+          mod.instOf(wDefInst.name, wDefInst.module)
         }
-        renameMap.record(m, (duplicatedModules).distinct)
       }
+      newTargets.foreach(addSelfRecord(_))
     }
 
     // Return modified circuit and associated renameMap
-    (cir.copy(modules = finalModuleList), renameMap)
+    (cir.copy(modules = finalModuleList), renameMap, annos)
   }
 
   override def execute(state: CircuitState): CircuitState = {
+    val moduleNames = state.circuit.modules.map(_.name).toSet
+
+    val (remainingAnnotations, targetsToEliminate, previouslyDeduped) =
+      state.annotations.foldLeft(
+        ( Vector.empty[Annotation],
+          Seq.empty[CompleteTarget],
+          Map.empty[IsModule, (ModuleTarget, Double)]
+        )
+      ) { case ((remainingAnnos, targets, dedupedResult), anno)  =>
+          anno match {
+            case ResolvePaths(ts)          =>
+              (remainingAnnos, ts ++ targets, dedupedResult)
+            case DedupedResult(orig, dups, idx) if dups.nonEmpty =>
+              (remainingAnnos, targets, dedupedResult ++ dups.map(_ -> (orig, idx)).toMap)
+            case other =>
+              (remainingAnnos :+ other, targets, dedupedResult)
+          }
+      }
 
-    val (annotations, annotationsx) = state.annotations.partition{
-      case a: ResolvePaths => true
-      case _               => false
-    }
 
     // Collect targets that are not local
-    val targets = annotations.map(_.asInstanceOf[ResolvePaths]).flatMap(_.targets.collect { case x: IsMember => x })
+    val targets = targetsToEliminate.collect { case x: IsMember => x }
 
     // Check validity of paths in targets
     val iGraph = new InstanceGraph(state.circuit)
@@ -140,7 +244,7 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration with Pr
     val targetsWithInvalidPaths = mutable.ArrayBuffer[IsMember]()
     targets.foreach { t =>
       val path = t match {
-        case m: ModuleTarget => Nil
+        case _: ModuleTarget => Nil
         case i: InstanceTarget => i.asPath
         case r: ReferenceTarget => r.path
       }
@@ -157,14 +261,18 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration with Pr
       throw NoSuchTargetException(s"""Some targets have illegal paths that cannot be resolved/eliminated: $string""")
     }
 
-    // get rid of path prefixes of modules with only one instance so we don't rename them
+    /* get rid of path prefixes of modules with only one instance so we don't rename them
+     * If instance targeted is in fact the only instance of a module, then it should not be renamed
+     * E.g. if Eliminate Target Paths on ~Top|Top/foo:Foo, but that is the only instance of Foo, then should return
+     *   ~Top|Top/foo:Foo, not ~Top|Top/foo:Foo___Top_foo
+     */
     val isSingleInstMod: String => Boolean = {
       val cache = mutable.Map.empty[String, Boolean]
       mod => cache.getOrElseUpdate(mod, iGraph.findInstancesInHierarchy(mod).size == 1)
     }
     val firstRenameMap = RenameMap()
-    val nonSingletonTargets = targets.foldLeft(Seq.empty[IsMember]) {
-      case (acc, t: IsComponent) if t.asPath.nonEmpty =>
+    val nonSingletonTargets = targets.foldRight(Seq.empty[IsMember]) {
+      case (t: IsComponent, acc) if t.asPath.nonEmpty =>
         val origPath = t.asPath
         val (singletonPrefix, rest) = origPath.partition {
           case (_, OfModule(mod)) =>
@@ -191,14 +299,14 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration with Pr
         } else {
           t +: acc
         }
-      case (acc, t) => t +: acc
+      case (t, acc) => t +: acc
     }
 
-    val (newCircuit, nextRenameMap) = run(state.circuit, nonSingletonTargets)
+    val (newCircuit, nextRenameMap, newAnnos) = run(state.circuit, nonSingletonTargets, iGraph)
 
     val renameMap =
       if (firstRenameMap.hasChanges) {
-        firstRenameMap andThen nextRenameMap
+        firstRenameMap.andThen(nextRenameMap)
       } else {
         nextRenameMap
       }
@@ -217,6 +325,30 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration with Pr
       newCircuit.copy(modules = modulesx)
     }
 
-    state.copy(circuit = newCircuitGC, renames = Some(renameMap), annotations = annotationsx)
+    val renamedModuleMap = RenameMap()
+
+    // If previous instance target mapped to a single previously deduped module, return original name
+    // E.g. if previously ~Top|Top/foo:Foo was deduped to ~Top|Top/foo:Bar, then
+    //  Eliminate target paths on ~Top|Top/foo:Bar should rename to ~Top|Top/foo:Foo, not
+    //  ~Top|Top/foo:Bar___Top_foo
+    val newModuleNameMapping = previouslyDeduped.flatMap {
+      case (current: IsModule, (orig: ModuleTarget, idx)) =>
+        renameMap.get(current).collect { case Seq(ModuleTarget(_, m)) => m -> orig.name }
+    }
+
+    val renamedCircuit = renameModules(newCircuitGC, newModuleNameMapping, renamedModuleMap)
+
+    val reorderedCircuit = reorderModules(renamedCircuit,
+      previouslyDeduped.map {
+        case (current: IsModule, (orig: ModuleTarget, idx)) =>
+          orig.name -> idx
+      }
+    )
+
+    state.copy(
+      circuit = reorderedCircuit,
+      renames = Some(renameMap.andThen(renamedModuleMap)),
+      annotations = remainingAnnotations ++ newAnnos
+    )
   }
 }
diff --git a/src/main/scala/firrtl/transforms/Dedup.scala b/src/main/scala/firrtl/transforms/Dedup.scala
index 09fd3af8..f91e2e41 100644
--- a/src/main/scala/firrtl/transforms/Dedup.scala
+++ b/src/main/scala/firrtl/transforms/Dedup.scala
@@ -9,15 +9,18 @@ import firrtl.analyses.InstanceGraph
 import firrtl.annotations._
 import firrtl.passes.{InferTypes, MemPortUtils}
 import firrtl.Utils.throwInternalError
+import firrtl.annotations.transforms.DupedResult
+import firrtl.annotations.TargetToken.{OfModule, Instance}
 import firrtl.options.{HasShellOptions, PreservesAll, ShellOption}
+import logger.LazyLogging
 
 // Datastructures
 import scala.collection.mutable
 
 
 /** A component, e.g. register etc. Must be declared only once under the TopAnnotation */
-case class NoDedupAnnotation(target: ModuleName) extends SingleTargetAnnotation[ModuleName] {
-  def duplicate(n: ModuleName): NoDedupAnnotation = NoDedupAnnotation(n)
+case class NoDedupAnnotation(target: ModuleTarget) extends SingleTargetAnnotation[ModuleTarget] {
+  def duplicate(n: ModuleTarget): NoDedupAnnotation = NoDedupAnnotation(n)
 }
 
 /** If this [[firrtl.annotations.Annotation Annotation]] exists in an [[firrtl.AnnotationSeq AnnotationSeq]],
@@ -34,10 +37,41 @@ case object NoCircuitDedupAnnotation extends NoTargetAnnotation with HasShellOpt
 
 }
 
+/** Holds the mapping from original module to the instances the original module pointed to
+  * The original module target is unaffected by renaming
+  * @param duplicate Instance target of what the original module now points to
+  * @param original Original module
+  * @param index the normalized position of the original module in the original module list, fraction between 0 and 1
+  */
+case class DedupedResult(original: ModuleTarget, duplicate: Option[IsModule], index: Double) extends MultiTargetAnnotation {
+  override val targets: Seq[Seq[Target]] = Seq(Seq(original), duplicate.toList)
+  override def duplicate(n: Seq[Seq[Target]]): Annotation = {
+    n.toList match {
+      case Seq(_, List(dup: IsModule)) => DedupedResult(original, Some(dup), index)
+      case _                           => DedupedResult(original, None, -1)
+    }
+  }
+}
+
 /** Only use on legal Firrtl.
   *
   * Specifically, the restriction of instance loops must have been checked, or else this pass can
-  *  infinitely recurse
+  * infinitely recurse.
+  *
+  * Deduped modules are renamed using a chain of 3 [[RenameMap]]s. The first
+  * [[RenameMap]] renames the original [[annotations.ModuleTarget]]s and relative
+  * [[annotations.InstanceTarget]]s to the groups of absolute [[annotations.InstanceTarget]]s that they
+  * target. These renames only affect instance names and paths and use the old
+  * module names. During this rename, modules will also have their instance
+  * names renamed if they dedup with a module that has different instance
+  * names.
+  * The second [[RenameMap]] renames all component names within modules that
+  * dedup with another module that has different component names.
+  * The third [[RenameMap]] renames original [[annotations.ModuleTarget]]s to their deduped
+  * [[annotations.ModuleTarget]].
+  *
+  * This transform will also emit [[DedupedResult]] for deduped modules that
+  * only have one instance.
   */
 class DedupModules extends Transform with DependencyAPIMigration with PreservesAll[Transform] {
 
@@ -54,9 +88,19 @@ class DedupModules extends Transform with DependencyAPIMigration with PreservesA
       state
     } else {
       // Don't try deduping the main module of the circuit
-      val noDedups = state.circuit.main +: state.annotations.collect { case NoDedupAnnotation(ModuleName(m, c)) => m }
-      val (newC, renameMap) = run(state.circuit, noDedups, state.annotations)
-      state.copy(circuit = newC, renames = Some(renameMap))
+      val noDedups = state.circuit.main +: state.annotations.collect { case NoDedupAnnotation(ModuleTarget(_, m)) => m }
+      val (remainingAnnotations, dupResults) = state.annotations.partition {
+        case _: DupedResult => false
+        case _                => true
+      }
+      val previouslyDupedMap = dupResults.flatMap {
+        case DupedResult(newModules, original) =>
+          newModules.collect {
+            case m: ModuleTarget => m.module -> original.module
+          }
+      }.toMap
+      val (newC, renameMap, newAnnos) = run(state.circuit, noDedups, previouslyDupedMap)
+      state.copy(circuit = newC, renames = Some(renameMap), annotations = newAnnos ++ remainingAnnotations)
     }
   }
 
@@ -65,40 +109,164 @@ class DedupModules extends Transform with DependencyAPIMigration with PreservesA
     * @param noDedups Modules not to dedup
     * @return Deduped Circuit and corresponding RenameMap
     */
-  def run(c: Circuit, noDedups: Seq[String], annos: Seq[Annotation]): (Circuit, RenameMap) = {
+  def run(c: Circuit,
+          noDedups: Seq[String],
+          previouslyDupedMap: Map[String, String]): (Circuit, RenameMap, AnnotationSeq) = {
 
     // RenameMap
     val componentRenameMap = RenameMap()
     componentRenameMap.setCircuit(c.main)
 
     // Maps module name to corresponding dedup module
-    val dedupMap = DedupModules.deduplicate(c, noDedups.toSet, annos, componentRenameMap)
+    val dedupMap = DedupModules.deduplicate(c, noDedups.toSet, previouslyDupedMap, componentRenameMap)
+    val dedupCliques = dedupMap.foldLeft(Map.empty[String, Set[String]]) {
+      case (dedupCliqueMap, (orig: String, dupMod: DefModule)) =>
+        val set = dedupCliqueMap.getOrElse(dupMod.name, Set.empty[String]) + dupMod.name + orig
+        dedupCliqueMap + (dupMod.name -> set)
+    }.flatMap { case (dedupName, set) =>
+      set.map { _ -> set }
+    }
 
     // Use old module list to preserve ordering
     // Lookup what a module deduped to, if its a duplicate, remove it
-    val dedupedModules = c.modules.flatMap { m =>
-      val mx = dedupMap(m.name)
-      if (mx.name == m.name) Some(mx) else None
+    val dedupedModules = {
+      val seen = mutable.Set[String]()
+      c.modules.flatMap { m =>
+        val dedupMod = dedupMap(m.name)
+        if (!seen(dedupMod.name)) {
+          seen += dedupMod.name
+          Some(dedupMod)
+        } else {
+          None
+        }
+      }
     }
 
-    val cname = CircuitName(c.main)
+    val ct = CircuitTarget(c.main)
+
     val map = dedupMap.map { case (from, to) =>
       logger.debug(s"[Dedup] $from -> ${to.name}")
-      ModuleName(from, cname) -> List(ModuleName(to.name, cname))
+      ct.module(from).asInstanceOf[CompleteTarget] -> Seq(ct.module(to.name))
     }
     val moduleRenameMap = RenameMap()
-    moduleRenameMap.recordAll(
-      map.map {
-        case (k: ModuleName, v: List[ModuleName]) => Target.convertNamed2Target(k) -> v.map(Target.convertNamed2Target)
+    moduleRenameMap.recordAll(map)
+
+    // Build instanceify renaming map
+    val instanceGraph = new InstanceGraph(c)
+    val instanceify = RenameMap()
+    val moduleName2Index = c.modules.map(_.name).zipWithIndex.map { case (n, i) =>
+      {
+        c.modules.size match {
+          case 0 => (n, 0.0)
+          case 1 => (n, 1.0)
+          case d => (n, i.toDouble / (d - 1))
+        }
       }
-    )
+    }.toMap
+
+    // get the ordered set of instances a module, includes new Deduped modules
+    val getChildrenInstances = (mod: String) => {
+      val childrenMap = instanceGraph.getChildrenInstances
+      val newModsMap: Map[String, mutable.LinkedHashSet[WDefInstance]] = dedupMap.map {
+        case (name, m: Module) =>
+          val set = new mutable.LinkedHashSet[WDefInstance]
+          InstanceGraph.collectInstances(set)(m.body)
+          m.name -> set
+        case (name, m: DefModule) =>
+          m.name -> mutable.LinkedHashSet.empty[WDefInstance]
+      }.toMap
+      childrenMap.get(mod).getOrElse(newModsMap(mod))
+    }
+
+    val instanceNameMap: Map[OfModule, Map[Instance, Instance]] = {
+      dedupMap.map { case (oldName, dedupedMod) =>
+        val key = OfModule(oldName)
+        val value = getChildrenInstances(oldName).zip(getChildrenInstances(dedupedMod.name)).map {
+          case (oldInst, newInst) => Instance(oldInst.name) -> Instance(newInst.name)
+        }.toMap
+        key -> value
+      }.toMap
+    }
+    val dedupAnnotations = c.modules.map(_.name).map(ct.module).flatMap { case mt@ModuleTarget(c, m) if dedupCliques(m).size > 1 =>
+      dedupMap.get(m) match {
+        case None => Nil
+        case Some(module: DefModule) =>
+          val paths = instanceGraph.findInstancesInHierarchy(m)
+          // If dedupedAnnos is exactly annos, contains is because dedupedAnnos is type Option
+          val newTargets = paths.map { path =>
+            val root: IsModule = ct.module(c)
+            path.foldLeft(root -> root) { case ((oldRelPath, newRelPath), WDefInstance(_, name, mod, _)) =>
+              if(mod == c) {
+                val mod = CircuitTarget(c).module(c)
+                mod -> mod
+              } else {
+                val enclosingMod = oldRelPath match {
+                  case i: InstanceTarget => i.ofModule
+                  case m: ModuleTarget => m.module
+                }
+                val instMap = instanceNameMap(OfModule(enclosingMod))
+                val newInstName = instMap(Instance(name)).value
+                val old = oldRelPath.instOf(name, mod)
+                old -> newRelPath.instOf(newInstName, mod)
+              }
+            }
+          }
+
+          // Add all relative paths to referredModule to map to new instances
+          def addRecord(from: IsMember, to: IsMember): Unit = from match {
+            case x: ModuleTarget =>
+              instanceify.record(x, to)
+            case x: IsComponent =>
+              instanceify.record(x, to)
+              addRecord(x.stripHierarchy(1), to)
+          }
+          // Instanceify deduped Modules!
+          if (dedupCliques(module.name).size > 1) {
+            newTargets.foreach { case (from, to) => addRecord(from, to) }
+          }
+          // Return Deduped Results
+          if (newTargets.size == 1) {
+            Seq(DedupedResult(mt, newTargets.headOption.map(_._1), moduleName2Index(m)))
+          } else Nil
+      }
+      case noDedups => Nil
+    }
 
-    (InferTypes.run(c.copy(modules = dedupedModules)), componentRenameMap.andThen(moduleRenameMap))
+    val finalRenameMap = instanceify.andThen(componentRenameMap).andThen(moduleRenameMap)
+    (InferTypes.run(c.copy(modules = dedupedModules)), finalRenameMap, dedupAnnotations.toList)
   }
 }
 
 /** Utility functions for [[DedupModules]] */
-object DedupModules {
+object DedupModules extends LazyLogging {
+  def fastSerializedHash(s: Statement): Int ={
+    def serialize(builder: StringBuilder, nindent: Int)(s: Statement): Unit = s match {
+      case Block(stmts) => stmts.map {
+        val x = serialize(builder, nindent)(_)
+        builder ++= "\n"
+        x
+      }
+      case Conditionally(info, pred, conseq, alt) =>
+        builder ++= ("  " * nindent)
+        builder ++= s"when ${pred.serialize} :"
+        builder ++= info.serialize
+        serialize(builder, nindent + 1)(conseq)
+        builder ++= "\n" + ("  " * nindent)
+        builder ++= "else :\n"
+        serialize(builder, nindent + 1)(alt)
+      case Print(info, string, args, clk, en) =>
+        builder ++= ("  " * nindent)
+        val strs = Seq(clk.serialize, en.serialize, string.string) ++
+          (args map (_.serialize))
+        builder ++= "printf(" + (strs mkString ", ") + ")" + info.serialize
+      case other: Statement =>
+        builder ++= ("  " * nindent)
+        builder ++= other.serialize
+    }
+    val builder = new mutable.StringBuilder()
+    serialize(builder, 0)(s)
+    builder.hashCode()
+  }
 
   /** Change's a module's internal signal names, types, infos, and modules.
     * @param rename Function to rename a signal. Called on declaration and references.
@@ -128,6 +296,7 @@ object DedupModules {
     }
     def onStmt(s: Statement): Statement = s match {
       case DefNode(info, name, value) =>
+        retype(name)(value.tpe)
         if(renameExps) DefNode(reinfo(info), rename(name), onExp(value))
         else DefNode(reinfo(info), rename(name), value)
       case WDefInstance(i, n, m, t) =>
@@ -242,7 +411,6 @@ object DedupModules {
     // If black box, return it (it has no instances)
     if (module.isInstanceOf[ExtModule]) return module
 
-
     // Get all instances to know what to rename in the module
     val instances = mutable.Set[WDefInstance]()
     InstanceGraph.collectInstances(instances)(module.asInstanceOf[Module].body)
@@ -251,15 +419,6 @@ object DedupModules {
     def getNewModule(old: String): DefModule = {
       moduleMap(name2name(old))
     }
-    // Define rename functions
-    def renameOfModule(instance: String, ofModule: String): String = {
-      val newOfModule = name2name(ofModule)
-      renameMap.record(
-        top.module(originalModule).instOf(instance, ofModule),
-        top.module(originalModule).instOf(instance, newOfModule)
-      )
-      newOfModule
-    }
     val typeMap = mutable.HashMap[String, Type]()
     def retype(name: String)(tpe: Type): Type = {
       if (typeMap.contains(name)) typeMap(name) else {
@@ -278,6 +437,10 @@ object DedupModules {
 
     renameMap.setModule(module.name)
     // Change module internals
+    // Define rename functions
+    def renameOfModule(instance: String, ofModule: String): String = {
+      name2name(ofModule)
+    }
     changeInternals({n => n}, retype, {i => i}, renameOfModule)(module)
   }
 
@@ -289,13 +452,11 @@ object DedupModules {
     * @param top CircuitTarget
     * @param moduleLinearization Sequence of modules from leaf to top
     * @param noDedups Set of modules to not dedup
-    * @param annotations All annotations to check if annotations are identical
     * @return
     */
   def buildRTLTags(top: CircuitTarget,
                    moduleLinearization: Seq[DefModule],
-                   noDedups: Set[String],
-                   annotations: Seq[Annotation]
+                   noDedups: Set[String]
                   ): (collection.Map[String, collection.Set[String]], RenameMap) = {
 
 
@@ -305,44 +466,6 @@ object DedupModules {
     // Maps a tag to all matching module names
     val tag2all = mutable.HashMap.empty[String, mutable.HashSet[String]]
 
-    val module2Annotations = mutable.HashMap.empty[String, mutable.HashSet[Annotation]]
-    annotations.foreach { a =>
-      a.getTargets.foreach { t =>
-        if (t.moduleOpt.isDefined) {
-          val annos = module2Annotations.getOrElseUpdate(t.moduleOpt.get, mutable.HashSet.empty[Annotation])
-          annos += a
-        }
-      }
-    }
-    def fastSerializedHash(s: Statement): Int ={
-      def serialize(builder: StringBuilder, nindent: Int)(s: Statement): Unit = s match {
-        case Block(stmts) => stmts.map {
-          val x = serialize(builder, nindent)(_)
-          builder ++= "\n"
-          x
-        }
-        case Conditionally(info, pred, conseq, alt) =>
-          builder ++= ("  " * nindent)
-          builder ++= s"when ${pred.serialize} :"
-          builder ++= info.serialize
-          serialize(builder, nindent + 1)(conseq)
-          builder ++= "\n" + ("  " * nindent)
-          builder ++= "else :\n"
-          serialize(builder, nindent + 1)(alt)
-        case Print(info, string, args, clk, en) =>
-          builder ++= ("  " * nindent)
-          val strs = Seq(clk.serialize, en.serialize, string.string) ++
-            (args map (_.serialize))
-          builder ++= "printf(" + (strs mkString ", ") + ")" + info.serialize
-        case other: Statement =>
-          builder ++= ("  " * nindent)
-          builder ++= other.serialize
-      }
-      val builder = new mutable.StringBuilder()
-      serialize(builder, 0)(s)
-      builder.hashCode()
-    }
-
     val agnosticRename = RenameMap()
 
     moduleLinearization.foreach { originalModule =>
@@ -358,15 +481,11 @@ object DedupModules {
         // Build name-agnostic module
         val agnosticModule = DedupModules.agnostify(top, originalModule, agnosticRename, "thisModule")
         agnosticRename.record(top.module(originalModule.name), top.module("thisModule"))
-        val agnosticAnnos = module2Annotations.getOrElse(
-          originalModule.name, mutable.HashSet.empty[Annotation]
-        ).map(_.update(agnosticRename))
         agnosticRename.delete(top.module(originalModule.name))
 
         // Build tag
         val builder = new mutable.ArrayBuffer[Any]()
         agnosticModule.ports.foreach { builder ++= _.serialize }
-        builder += agnosticAnnos
 
         agnosticModule match {
           case Module(i, n, ps, b) => builder ++= fastSerializedHash(b).toString()//.serialize
@@ -397,7 +516,7 @@ object DedupModules {
     */
   def deduplicate(circuit: Circuit,
                   noDedups: Set[String],
-                  annotations: Seq[Annotation],
+                  previousDupResults: Map[String, String],
                   renameMap: RenameMap): Map[String, DefModule] = {
 
     val (moduleMap, moduleLinearization) = {
@@ -406,10 +525,16 @@ object DedupModules {
     }
     val main = circuit.main
     val top = CircuitTarget(main)
-    val (tag2all, tagMap) = buildRTLTags(top, moduleLinearization, noDedups, annotations)
+
+    // Maps a module name to its agnostic name
+    // tagMap is a RenameMap containing ModuleTarget renames of original name to tag name
+    // tag2all is a Map of tag to original names of all modules with that tag
+    val (tag2all, tagMap) = buildRTLTags(top, moduleLinearization, noDedups)
 
     // Set tag2name to be the best dedup module name
     val moduleIndex = circuit.modules.zipWithIndex.map{case (m, i) => m.name -> i}.toMap
+
+    // returns the module matching the circuit name or the module with lower index otherwise
     def order(l: String, r: String): String = {
       if (l == main) l
       else if (r == main) r
@@ -418,10 +543,22 @@ object DedupModules {
 
     // Maps a module's tag to its deduplicated module
     val tag2name = mutable.HashMap.empty[String, String]
-    tag2all.foreach { case (tag, all) => tag2name(tag) = all.reduce(order)}
+
+    // Maps a deduped module name to its original Module (its instance names need to be updated)
+    val moduleMapWithOldNames = tag2all.map {
+      case (tag, all: collection.Set[String]) =>
+        val dedupWithoutOldName = all.reduce(order)
+        val dedupName = previousDupResults.getOrElse(dedupWithoutOldName, dedupWithoutOldName)
+        tag2name(tag) = dedupName
+        val dedupModule = moduleMap(dedupWithoutOldName) match {
+          case e: ExtModule => e.copy(name = dedupName)
+          case e: Module => e.copy(name = dedupName)
+        }
+        dedupName -> dedupModule
+    }.toMap
 
     // Create map from original to dedup name
-    val name2name = moduleMap.keysIterator.map{ originalModule =>
+    val name2name = moduleMap.keysIterator.map { originalModule =>
       tagMap.get(top.module(originalModule)) match {
         case Some(Seq(Target(_, Some(tag), Nil))) => originalModule -> tag2name(tag)
         case None => originalModule -> originalModule
@@ -430,7 +567,10 @@ object DedupModules {
     }.toMap
 
     // Build Remap for modules with deduped module references
-    val dedupedName2module = tag2name.map({ case (tag, name) => name -> DedupModules.dedupInstances(top, name, moduleMap, name2name, renameMap) })
+    val dedupedName2module = tag2name.map {
+      case (tag, name) => name -> DedupModules.dedupInstances(
+          top, name, moduleMapWithOldNames, name2name, renameMap)
+    }
 
     // Build map from original name to corresponding deduped module
     // It is important to flatMap before looking up the DefModules so that they aren't hashed
@@ -471,7 +611,9 @@ object DedupModules {
                        renameMap: RenameMap): Unit = {
 
     originalNames.zip(dedupedNames).foreach {
-      case (o, d) => if (o.component != d.component || o.ref != d.ref) renameMap.record(o, d)
+      case (o, d) => if (o.component != d.component || o.ref != d.ref) {
+        renameMap.record(o, d.copy(module = o.module))
+      }
     }
 
   }
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)
+  }
 }