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, 428 insertions, 135 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))
+      }
     }
 
   }