Modify and optimize performance of propagate annotations (#2393)

* Change AnnotationSeq underlying from List to Seq

It was nothing but pointless copying.

* Make propagateAnnotations faster

There was lots of expensive logic for very little benefit.

5 files changed, 35 insertions, 49 deletions

diff --git a/src/main/scala/firrtl/Compiler.scala b/src/main/scala/firrtl/Compiler.scala
index 2017633d..3466f3e1 100644
--- a/src/main/scala/firrtl/Compiler.scala
+++ b/src/main/scala/firrtl/Compiler.scala
@@ -6,6 +6,7 @@ import logger._
 import java.io.Writer
 
 import scala.collection.mutable
+import scala.collection.immutable.VectorBuilder
 import scala.util.Try
 import scala.util.control.NonFatal
 import firrtl.annotations._
@@ -17,11 +18,11 @@ import firrtl.stage.Forms
 import firrtl.transforms.DedupAnnotationsTransform
 
 /** Container of all annotations for a Firrtl compiler */
-class AnnotationSeq private (private[firrtl] val underlying: List[Annotation]) {
-  def toSeq: Seq[Annotation] = underlying.toSeq
+class AnnotationSeq private (underlying: Seq[Annotation]) {
+  def toSeq: Seq[Annotation] = underlying
 }
 object AnnotationSeq {
-  def apply(xs: Seq[Annotation]): AnnotationSeq = new AnnotationSeq(xs.toList)
+  def apply(xs: Seq[Annotation]): AnnotationSeq = new AnnotationSeq(xs)
 }
 
 /** Current State of the Circuit
@@ -211,8 +212,8 @@ final case object UnknownForm extends CircuitForm(-1) {
 // Internal utilities to keep code DRY, not a clean interface
 private[firrtl] object Transform {
 
-  def remapAnnotations(name: String, before: CircuitState, after: CircuitState, logger: Logger): CircuitState = {
-    val remappedAnnotations = propagateAnnotations(name, logger, before.annotations, after.annotations, after.renames)
+  def remapAnnotations(after: CircuitState, logger: Logger): CircuitState = {
+    val remappedAnnotations = propagateAnnotations(after.annotations, after.renames)
 
     logger.trace(s"Annotations:")
     logger.trace(JsonProtocol.serializeRecover(remappedAnnotations))
@@ -222,51 +223,34 @@ private[firrtl] object Transform {
     CircuitState(after.circuit, after.form, remappedAnnotations, None)
   }
 
-  /** Propagate annotations and update their names.
-    *
-    * @param inAnno input AnnotationSeq
-    * @param resAnno result AnnotationSeq
-    * @param renameOpt result RenameMap
-    * @return the updated annotations
-    */
+  // This function is *very* mutable but it is fairly performance critical
   def propagateAnnotations(
-    name:      String,
-    logger:    Logger,
-    inAnno:    AnnotationSeq,
     resAnno:   AnnotationSeq,
     renameOpt: Option[RenameMap]
   ): AnnotationSeq = {
-    val newAnnotations = {
-      val inSet = mutable.LinkedHashSet() ++ inAnno
-      val resSet = mutable.LinkedHashSet() ++ resAnno
-      val deleted = (inSet -- resSet).map {
-        case DeletedAnnotation(xFormName, delAnno) => DeletedAnnotation(s"$xFormName+$name", delAnno)
-        case anno                                  => DeletedAnnotation(name, anno)
-      }
-      val created = resSet -- inSet
-      val unchanged = resSet & inSet
-      (deleted ++ created ++ unchanged)
-    }
-
-    // For each annotation, rename all annotations.
-    val renames = renameOpt.getOrElse(RenameMap())
-    val remapped2original = mutable.LinkedHashMap[Annotation, mutable.LinkedHashSet[Annotation]]()
-    val keysOfNote = mutable.LinkedHashSet[Annotation]()
-    val finalAnnotations = newAnnotations.flatMap { anno =>
-      val remappedAnnos = anno.update(renames)
-      remappedAnnos.foreach { remapped =>
-        val set = remapped2original.getOrElseUpdate(remapped, mutable.LinkedHashSet.empty[Annotation])
-        set += anno
-        if (set.size > 1) keysOfNote += remapped
+    // We dedup/distinct the resulting annotations when renaming occurs
+    val seen = new mutable.HashSet[Annotation]
+    val result = new VectorBuilder[Annotation]
+
+    val hasRenames = renameOpt.isDefined
+    val renames = renameOpt.getOrElse(null) // Null is bad but saving the allocation is worth it
+
+    val it = resAnno.toSeq.iterator
+    while (it.hasNext) {
+      val anno = it.next()
+      if (hasRenames) {
+        val renamed = anno.update(renames)
+        for (annox <- renamed) {
+          if (!seen(annox)) {
+            seen += annox
+            result += annox
+          }
+        }
+      } else {
+        result += anno
       }
-      remappedAnnos
-    }.toSeq
-    keysOfNote.foreach { key =>
-      logger.debug(s"""The following original annotations are renamed to the same new annotation.""")
-      logger.debug(s"""Original Annotations:\n  ${remapped2original(key).mkString("\n  ")}""")
-      logger.debug(s"""New Annotation:\n  $key""")
     }
-    finalAnnotations
+    result.result()
   }
 }
 
@@ -363,7 +347,7 @@ trait Transform extends TransformLike[CircuitState] with DependencyAPI[Transform
     */
   final def runTransform(state: CircuitState): CircuitState = {
     val result = execute(prepare(state))
-    Transform.remapAnnotations(name, state, result, logger)
+    Transform.remapAnnotations(result, logger)
   }
 
 }
diff --git a/src/main/scala/firrtl/package.scala b/src/main/scala/firrtl/package.scala
index adaddeda..844d84ec 100644
--- a/src/main/scala/firrtl/package.scala
+++ b/src/main/scala/firrtl/package.scala
@@ -7,7 +7,7 @@ package object firrtl {
   private val _dummyForms = firrtl.stage.Forms
 
   implicit def seqToAnnoSeq(xs: Seq[Annotation]) = AnnotationSeq(xs)
-  implicit def annoSeqToSeq(as: AnnotationSeq): Seq[Annotation] = as.underlying
+  implicit def annoSeqToSeq(as: AnnotationSeq): Seq[Annotation] = as.toSeq
 
   /* Options as annotations compatibility items */
   @deprecated("Use firrtl.stage.TargetDirAnnotation", "FIRRTL 1.2")
diff --git a/src/main/scala/firrtl/stage/transforms/UpdateAnnotations.scala b/src/main/scala/firrtl/stage/transforms/UpdateAnnotations.scala
index 8bd29b9c..5275de73 100644
--- a/src/main/scala/firrtl/stage/transforms/UpdateAnnotations.scala
+++ b/src/main/scala/firrtl/stage/transforms/UpdateAnnotations.scala
@@ -15,7 +15,7 @@ class UpdateAnnotations(val underlying: Transform)
   def aToB(a: CircuitState): (CircuitState, CircuitState) = (a, a)
 
   def bToA(b: (CircuitState, CircuitState)): CircuitState = {
-    Transform.remapAnnotations(name, b._1, b._2, logger)
+    Transform.remapAnnotations(b._2, logger)
   }
 
   def internalTransform(b: (CircuitState, CircuitState)): (CircuitState, CircuitState) = {
diff --git a/src/main/scala/firrtl/transforms/DedupAnnotations.scala b/src/main/scala/firrtl/transforms/DedupAnnotations.scala
index cad4d2be..9aad2fee 100644
--- a/src/main/scala/firrtl/transforms/DedupAnnotations.scala
+++ b/src/main/scala/firrtl/transforms/DedupAnnotations.scala
@@ -95,7 +95,7 @@ class DedupAnnotationsTransform extends Transform with DependencyAPIMigration {
   def execute(state: CircuitState): CircuitState = CircuitState(
     state.circuit,
     state.form,
-    DedupAnnotationsTransform.dedupAnnotations(state.annotations.underlying, InstanceKeyGraph(state.circuit)),
+    DedupAnnotationsTransform.dedupAnnotations(state.annotations.toSeq, InstanceKeyGraph(state.circuit)),
     state.renames
   )
 }
diff --git a/src/test/scala/firrtlTests/AnnotationTests.scala b/src/test/scala/firrtlTests/AnnotationTests.scala
index 7837b4ba..a51a8e77 100644
--- a/src/test/scala/firrtlTests/AnnotationTests.scala
+++ b/src/test/scala/firrtlTests/AnnotationTests.scala
@@ -45,7 +45,9 @@ abstract class AnnotationTests extends LowFirrtlTransformSpec with Matchers with
     r.annotations.toSeq should contain(ta)
   }
 
-  "Deleting annotations" should "create a DeletedAnnotation" in {
+  // This test is no longer true as of 1.5.0-RC2, see
+  // https://github.com/chipsalliance/firrtl/pull/2393
+  "Deleting annotations" should "create a DeletedAnnotation" ignore {
     val transform = Dependency[DeletingTransform]
     val compiler = makeVerilogCompiler(Seq(transform))
     val input =