Change RawModule._commands to a VectorBuilder (backport #2839) (#2841)

* Change RawModule._commands to a VectorBuilder (#2839)

* Change RawModule._commands to a VectorBuilder

Use the resulting Vector to build the underlying Component's commands
and then use those instead of copying the original ArrayBuffer when
iterating on commands. Previously, the Component was using a List to
hold the commands which is particularly memory inefficient, especially
for large modules.

* Optimize Converter's handling of Seq[Command]

It previously converted the Commands to a List (which, while not
captured in the type system, they were already a List) and then used
head and tail iteration. This is less efficient with the new underlying
Vector implementation.

(cherry picked from commit 48a1ef0a3872c6b68d46145764d977926923a270)

* Waive false binary compatibility failures

Co-authored-by: Jack Koenig <koenig@sifive.com>
Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com>

2 files changed, 77 insertions, 53 deletions

diff --git a/core/src/main/scala/chisel3/RawModule.scala b/core/src/main/scala/chisel3/RawModule.scala
index f2ce4c70..9668313a 100644
--- a/core/src/main/scala/chisel3/RawModule.scala
+++ b/core/src/main/scala/chisel3/RawModule.scala
@@ -2,7 +2,6 @@
 
 package chisel3
 
-import scala.collection.mutable.{ArrayBuffer, HashMap}
 import scala.util.Try
 import scala.language.experimental.macros
 import scala.annotation.nowarn
@@ -13,6 +12,7 @@ import chisel3.internal.Builder._
 import chisel3.internal.firrtl._
 import chisel3.internal.sourceinfo.UnlocatableSourceInfo
 import _root_.firrtl.annotations.{IsModule, ModuleTarget}
+import scala.collection.immutable.VectorBuilder
 
 /** Abstract base class for Modules that contain Chisel RTL.
   * This abstract base class is a user-defined module which does not include implicit clock and reset and supports
@@ -23,14 +23,18 @@ abstract class RawModule(implicit moduleCompileOptions: CompileOptions) extends
   //
   // RTL construction internals
   //
-  private val _commands = ArrayBuffer[Command]()
+  // Perhaps this should be an ArrayBuffer (or ArrayBuilder), but DefModule is public and has Seq[Command]
+  // so our best option is to share a single Seq datastructure with that
+  private val _commands = new VectorBuilder[Command]()
   private[chisel3] def addCommand(c: Command) {
     require(!_closed, "Can't write to module after module close")
     _commands += c
   }
-  protected def getCommands = {
+  protected def getCommands: Seq[Command] = {
     require(_closed, "Can't get commands before module close")
-    _commands.toSeq
+    // Unsafe cast but we know that any RawModule uses a DefModule
+    // _component is defined as a var on BaseModule and we cannot override mutable vars
+    _component.get.asInstanceOf[DefModule].commands
   }
 
   //
@@ -153,7 +157,7 @@ abstract class RawModule(implicit moduleCompileOptions: CompileOptions) extends
         Seq()
       }
     }
-    val component = DefModule(this, name, firrtlPorts, invalidateCommands ++ getCommands)
+    val component = DefModule(this, name, firrtlPorts, invalidateCommands ++: _commands.result())
     _component = Some(component)
     _component
   }
diff --git a/core/src/main/scala/chisel3/internal/firrtl/Converter.scala b/core/src/main/scala/chisel3/internal/firrtl/Converter.scala
index 3d6e0d79..ca39608f 100644
--- a/core/src/main/scala/chisel3/internal/firrtl/Converter.scala
+++ b/core/src/main/scala/chisel3/internal/firrtl/Converter.scala
@@ -8,7 +8,7 @@ import firrtl.{ir => fir}
 import chisel3.internal.{castToInt, throwException, HasId}
 
 import scala.annotation.{nowarn, tailrec}
-import scala.collection.immutable.Queue
+import scala.collection.immutable.{Queue, VectorBuilder}
 import scala.collection.immutable.LazyList // Needed for 2.12 alias
 
 @nowarn("msg=class Port") // delete when Port becomes private
@@ -215,7 +215,7 @@ private[chisel3] object Converter {
     * @param alt Indicates if currently processing commands in the alternate (else) of the when scope
     */
   // TODO we should probably have a different structure in the IR to close elses
-  private case class WhenFrame(when: fir.Conditionally, outer: Queue[fir.Statement], alt: Boolean)
+  private case class WhenFrame(when: fir.Conditionally, outer: VectorBuilder[fir.Statement], alt: Boolean)
 
   /** Convert Chisel IR Commands into FIRRTL Statements
     *
@@ -226,52 +226,72 @@ private[chisel3] object Converter {
     * @return FIRRTL Statement that is equivalent to the input cmds
     */
   def convert(cmds: Seq[Command], ctx: Component): fir.Statement = {
-    @tailrec
-    def rec(acc: Queue[fir.Statement], scope: List[WhenFrame])(cmds: Seq[Command]): Seq[fir.Statement] = {
-      if (cmds.isEmpty) {
-        assert(scope.isEmpty)
-        acc
-      } else
-        convertSimpleCommand(cmds.head, ctx) match {
-          // Most Commands map 1:1
-          case Some(stmt) =>
-            rec(acc :+ stmt, scope)(cmds.tail)
-          // When scoping logic does not map 1:1 and requires pushing/popping WhenFrames
-          // Please see WhenFrame for more details
-          case None =>
-            cmds.head match {
-              case WhenBegin(info, pred) =>
-                val when = fir.Conditionally(convert(info), convert(pred, ctx, info), fir.EmptyStmt, fir.EmptyStmt)
-                val frame = WhenFrame(when, acc, false)
-                rec(Queue.empty, frame +: scope)(cmds.tail)
-              case WhenEnd(info, depth, _) =>
-                val frame = scope.head
-                val when =
-                  if (frame.alt) frame.when.copy(alt = fir.Block(acc))
-                  else frame.when.copy(conseq = fir.Block(acc))
-                // Check if this when has an else
-                cmds.tail.headOption match {
-                  case Some(AltBegin(_)) =>
-                    assert(!frame.alt, "Internal Error! Unexpected when structure!") // Only 1 else per when
-                    rec(Queue.empty, frame.copy(when = when, alt = true) +: scope.tail)(cmds.drop(2))
-                  case _ => // Not followed by otherwise
-                    // If depth > 0 then we need to close multiple When scopes so we add a new WhenEnd
-                    // If we're nested we need to add more WhenEnds to ensure each When scope gets
-                    // properly closed
-                    val cmdsx = if (depth > 0) WhenEnd(info, depth - 1, false) +: cmds.tail else cmds.tail
-                    rec(frame.outer :+ when, scope.tail)(cmdsx)
-                }
-              case OtherwiseEnd(info, depth) =>
-                val frame = scope.head
-                val when = frame.when.copy(alt = fir.Block(acc))
-                // TODO For some reason depth == 1 indicates the last closing otherwise whereas
-                //  depth == 0 indicates last closing when
-                val cmdsx = if (depth > 1) OtherwiseEnd(info, depth - 1) +: cmds.tail else cmds.tail
-                rec(scope.head.outer :+ when, scope.tail)(cmdsx)
-            }
-        }
+    var stmts = new VectorBuilder[fir.Statement]()
+    var scope: List[WhenFrame] = Nil
+    var cmdsIt = cmds.iterator.buffered
+    // Extra var because sometimes we want to push a Command to the head of cmdsIt
+    // This is more efficient than changing the iterator
+    var nextCmd: Command = null
+    while (nextCmd != null || cmdsIt.hasNext) {
+      val cmd = if (nextCmd != null) {
+        val _nextCmd = nextCmd
+        nextCmd = null
+        _nextCmd
+      } else {
+        cmdsIt.next()
+      }
+      convertSimpleCommand(cmd, ctx) match {
+        // Most Commands map 1:1
+        case Some(stmt) =>
+          stmts += stmt
+        // When scoping logic does not map 1:1 and requires pushing/popping WhenFrames
+        // Please see WhenFrame for more details
+        case None =>
+          cmd match {
+            case WhenBegin(info, pred) =>
+              val when = fir.Conditionally(convert(info), convert(pred, ctx, info), fir.EmptyStmt, fir.EmptyStmt)
+              val frame = WhenFrame(when, stmts, false)
+              stmts = new VectorBuilder[fir.Statement]
+              scope = frame :: scope
+            case WhenEnd(info, depth, _) =>
+              val frame = scope.head
+              val when =
+                if (frame.alt) frame.when.copy(alt = fir.Block(stmts.result()))
+                else frame.when.copy(conseq = fir.Block(stmts.result()))
+              // Check if this when has an else
+              cmdsIt.headOption match {
+                case Some(AltBegin(_)) =>
+                  assert(!frame.alt, "Internal Error! Unexpected when structure!") // Only 1 else per when
+                  scope = frame.copy(when = when, alt = true) :: scope.tail
+                  cmdsIt.next() // Consume the AltBegin
+                  stmts = new VectorBuilder[fir.Statement]
+                case _ => // Not followed by otherwise
+                  // If depth > 0 then we need to close multiple When scopes so we add a new WhenEnd
+                  // If we're nested we need to add more WhenEnds to ensure each When scope gets
+                  // properly closed
+                  if (depth > 0) {
+                    nextCmd = WhenEnd(info, depth - 1, false)
+                  }
+                  stmts = frame.outer
+                  stmts += when
+                  scope = scope.tail
+              }
+            case OtherwiseEnd(info, depth) =>
+              val frame = scope.head
+              val when = frame.when.copy(alt = fir.Block(stmts.result()))
+              // TODO For some reason depth == 1 indicates the last closing otherwise whereas
+              //  depth == 0 indicates last closing when
+              if (depth > 1) {
+                nextCmd = OtherwiseEnd(info, depth - 1)
+              }
+              stmts = frame.outer
+              stmts += when
+              scope = scope.tail
+          }
+      }
     }
-    fir.Block(rec(Queue.empty, List.empty)(cmds))
+    assert(scope.isEmpty)
+    fir.Block(stmts.result())
   }
 
   def convert(width: Width): fir.Width = width match {
@@ -347,7 +367,7 @@ private[chisel3] object Converter {
 
   def convert(component: Component): fir.DefModule = component match {
     case ctx @ DefModule(_, name, ports, cmds) =>
-      fir.Module(fir.NoInfo, name, ports.map(p => convert(p)), convert(cmds.toList, ctx))
+      fir.Module(fir.NoInfo, name, ports.map(p => convert(p)), convert(cmds, ctx))
     case ctx @ DefBlackBox(id, name, ports, topDir, params) =>
       fir.ExtModule(
         fir.NoInfo,