Merge pull request #928 from freechipsproject/dont-append-to-lists

Adds performance improvements by removing list appends.

10 files changed, 41 insertions, 36 deletions

diff --git a/src/main/scala/firrtl/RenameMap.scala b/src/main/scala/firrtl/RenameMap.scala
index e95260af..c41f15b9 100644
--- a/src/main/scala/firrtl/RenameMap.scala
+++ b/src/main/scala/firrtl/RenameMap.scala
@@ -308,7 +308,7 @@ final class RenameMap private () {
       case (x, Seq(y)) if x == y =>
       case _ =>
         tos.foreach{recordSensitivity(from, _)}
-        val existing = underlying.getOrElse(from, Seq.empty)
+        val existing = underlying.getOrElse(from, Vector.empty)
         val updated = existing ++ tos
         underlying(from) = updated
         getCache.clear()
diff --git a/src/main/scala/firrtl/Utils.scala b/src/main/scala/firrtl/Utils.scala
index 2d1b0b74..44b16bf8 100644
--- a/src/main/scala/firrtl/Utils.scala
+++ b/src/main/scala/firrtl/Utils.scala
@@ -256,10 +256,9 @@ object Utils extends LazyLogging {
     case ex: ValidIf => create_exps(ex.value) map (e1 => ValidIf(ex.cond, e1, e1.tpe))
     case ex => ex.tpe match {
       case (_: GroundType) => Seq(ex)
-      case (t: BundleType) => (t.fields foldLeft Seq[Expression]())((exps, f) =>
-        exps ++ create_exps(WSubField(ex, f.name, f.tpe,times(gender(ex), f.flip))))
-      case (t: VectorType) => (0 until t.size foldLeft Seq[Expression]())((exps, i) =>
-        exps ++ create_exps(WSubIndex(ex, i, t.tpe,gender(ex))))
+      case t: BundleType =>
+        t.fields.flatMap(f => create_exps(WSubField(ex, f.name, f.tpe,times(gender(ex), f.flip))))
+      case t: VectorType => (0 until t.size).flatMap(i => create_exps(WSubIndex(ex, i, t.tpe,gender(ex))))
     }
   }
 
@@ -301,6 +300,7 @@ object Utils extends LazyLogging {
     onExp(expression)
     ReferenceTarget(main, module, Nil, ref, tokens)
   }
+   @deprecated("get_flip is fundamentally slow, use to_flip(gender(expr))", "1.2")
    def get_flip(t: Type, i: Int, f: Orientation): Orientation = {
      if (i >= get_size(t)) throwInternalError(s"get_flip: shouldn't be here - $i >= get_size($t)")
      t match {
diff --git a/src/main/scala/firrtl/passes/ExpandWhens.scala b/src/main/scala/firrtl/passes/ExpandWhens.scala
index 3665590f..9136c913 100644
--- a/src/main/scala/firrtl/passes/ExpandWhens.scala
+++ b/src/main/scala/firrtl/passes/ExpandWhens.scala
@@ -204,14 +204,13 @@ object ExpandWhens extends Pass {
 
   /** Returns all references to all Female leaf subcomponents of a reference */
   private def getFemaleRefs(n: String, t: Type, g: Gender): Seq[Expression] = {
-    def getGender(t: Type, i: Int, g: Gender): Gender = times(g, get_flip(t, i, Default))
     val exps = create_exps(WRef(n, t, ExpKind, g))
-    (exps.zipWithIndex foldLeft Seq[Expression]()){
-      case (expsx, (exp, j)) => exp.tpe match {
-        case AnalogType(w) => expsx
-        case _ => getGender(t, j, g) match {
-          case (BIGENDER | FEMALE) => expsx :+ exp
-          case _ => expsx
+    exps.flatMap { case exp =>
+      exp.tpe match {
+        case AnalogType(w) => None
+        case _ => gender(exp) match {
+          case (BIGENDER | FEMALE) => Some(exp)
+          case _ => None
         }
       }
     }
diff --git a/src/main/scala/firrtl/passes/InferWidths.scala b/src/main/scala/firrtl/passes/InferWidths.scala
index 1e9532c8..26d346bb 100644
--- a/src/main/scala/firrtl/passes/InferWidths.scala
+++ b/src/main/scala/firrtl/passes/InferWidths.scala
@@ -263,12 +263,12 @@ object InferWidths extends Pass {
           val n = get_size(s.loc.tpe)
           val locs = create_exps(s.loc)
           val exps = create_exps(s.expr)
-          v ++= ((locs zip exps).zipWithIndex flatMap {case ((locx, expx), i) =>
-            get_flip(s.loc.tpe, i, Default) match {
+          v ++= locs.zip(exps).flatMap { case (locx, expx) =>
+            to_flip(gender(locx)) match {
               case Default => get_constraints_t(locx.tpe, expx.tpe)//WGeq(getWidth(locx), getWidth(expx))
               case Flip => get_constraints_t(expx.tpe, locx.tpe)//WGeq(getWidth(expx), getWidth(locx))
             }
-          })
+          }
         case (s: PartialConnect) =>
           val ls = get_valid_points(s.loc.tpe, s.expr.tpe, Default, Default)
           val locs = create_exps(s.loc)
@@ -276,7 +276,7 @@ object InferWidths extends Pass {
           v ++= (ls flatMap {case (x, y) =>
             val locx = locs(x)
             val expx = exps(y)
-            get_flip(s.loc.tpe, x, Default) match {
+            to_flip(gender(locx)) match {
               case Default => get_constraints_t(locx.tpe, expx.tpe)//WGeq(getWidth(locx), getWidth(expx))
               case Flip => get_constraints_t(expx.tpe, locx.tpe)//WGeq(getWidth(expx), getWidth(locx))
             }
diff --git a/src/main/scala/firrtl/passes/Inline.scala b/src/main/scala/firrtl/passes/Inline.scala
index d6af69c1..feda80f2 100644
--- a/src/main/scala/firrtl/passes/Inline.scala
+++ b/src/main/scala/firrtl/passes/Inline.scala
@@ -128,18 +128,18 @@ class InlineInstances extends Transform {
         val port = ComponentName(s"$ref.$field", currentModule)
         val inst = ComponentName(s"$ref", currentModule)
         (renames.get(port), renames.get(inst)) match {
-          case (Some(p :: Nil), _)              =>
+          case (Some(Seq(p)), _)              =>
             p.toTarget match {
               case ReferenceTarget(_, _, Seq(), r, Seq(TargetToken.Field(f))) => wsf.copy(expr = wr.copy(name = r), name = f)
               case ReferenceTarget(_, _, Seq(), r, Seq()) => WRef(r, tpe, WireKind, gen)
             }
-          case (None,           Some(i :: Nil)) => wsf.map(appendRefPrefix(currentModule, renames))
+          case (None,           Some(Seq(i))) => wsf.map(appendRefPrefix(currentModule, renames))
           case (None,           None)           => wsf
         }
       case wr@ WRef(name, _, _, _) =>
         val comp = ComponentName(name, currentModule)
         renames.get(comp).orElse(Some(Seq(comp))) match {
-          case Some(car :: Nil) => wr.copy(name=car.name)
+          case Some(Seq(car)) => wr.copy(name=car.name)
           case c@ Some(_)       => throw new PassException(
             s"Inlining found mlutiple renames for ref $comp -> $c. This should be impossible...")
         }
diff --git a/src/main/scala/firrtl/passes/LowerTypes.scala b/src/main/scala/firrtl/passes/LowerTypes.scala
index 663241d3..ee03afb5 100644
--- a/src/main/scala/firrtl/passes/LowerTypes.scala
+++ b/src/main/scala/firrtl/passes/LowerTypes.scala
@@ -47,15 +47,15 @@ object LowerTypes extends Transform {
       val name = root + loweredName(e)
       renames.rename(root + e.serialize, name)
       Seq(name)
-    case (t: BundleType) => t.fields.foldLeft(Seq[String]()){(names, f) =>
+    case (t: BundleType) => t.fields.flatMap { f =>
       val subNames = renameExps(renames, WSubField(e, f.name, f.tpe, times(gender(e), f.flip)), root)
       renames.rename(root + e.serialize, subNames)
-      names ++ subNames
+      subNames
     }
-    case (t: VectorType) => (0 until t.size).foldLeft(Seq[String]()){(names, i) =>
+    case (t: VectorType) => (0 until t.size).flatMap { i =>
       val subNames = renameExps(renames, WSubIndex(e, i, t.tpe,gender(e)), root)
       renames.rename(root + e.serialize, subNames)
-      names ++ subNames
+      subNames
     }
   }
 
diff --git a/src/main/scala/firrtl/passes/Passes.scala b/src/main/scala/firrtl/passes/Passes.scala
index 3658d368..bb65201b 100644
--- a/src/main/scala/firrtl/passes/Passes.scala
+++ b/src/main/scala/firrtl/passes/Passes.scala
@@ -125,13 +125,13 @@ object ExpandConnects extends Pass {
           case sx: DefMemory => genders(sx.name) = MALE; sx
           case sx: DefNode => genders(sx.name) = MALE; sx
           case sx: IsInvalid =>
-            val invalids = (create_exps(sx.expr) foldLeft Seq[Statement]())(
-               (invalids,  expx) => gender(set_gender(expx)) match {
-                  case BIGENDER => invalids :+ IsInvalid(sx.info, expx)
-                  case FEMALE => invalids :+ IsInvalid(sx.info, expx)
-                  case _ => invalids
+            val invalids = create_exps(sx.expr).flatMap { case expx =>
+               gender(set_gender(expx)) match {
+                  case BIGENDER => Some(IsInvalid(sx.info, expx))
+                  case FEMALE => Some(IsInvalid(sx.info, expx))
+                  case _ => None
                }
-            )
+            }
             invalids.size match {
                case 0 => EmptyStmt
                case 1 => invalids.head
@@ -140,8 +140,8 @@ object ExpandConnects extends Pass {
           case sx: Connect =>
             val locs = create_exps(sx.loc)
             val exps = create_exps(sx.expr)
-            Block((locs zip exps).zipWithIndex map {case ((locx, expx), i) =>
-               get_flip(sx.loc.tpe, i, Default) match {
+            Block(locs.zip(exps).map { case (locx, expx) =>
+               to_flip(gender(locx)) match {
                   case Default => Connect(sx.info, locx, expx)
                   case Flip => Connect(sx.info, expx, locx)
                }
@@ -154,7 +154,7 @@ object ExpandConnects extends Pass {
               locs(x).tpe match {
                 case AnalogType(_) => Attach(sx.info, Seq(locs(x), exps(y)))
                 case _ =>
-                  get_flip(sx.loc.tpe, x, Default) match {
+                  to_flip(gender(locs(x))) match {
                     case Default => Connect(sx.info, locs(x), exps(y))
                     case Flip => Connect(sx.info, exps(y), locs(x))
                   }
diff --git a/src/main/scala/firrtl/transforms/RemoveKeywordCollisions.scala b/src/main/scala/firrtl/transforms/RemoveKeywordCollisions.scala
index 05fd0228..66e39e53 100644
--- a/src/main/scala/firrtl/transforms/RemoveKeywordCollisions.scala
+++ b/src/main/scala/firrtl/transforms/RemoveKeywordCollisions.scala
@@ -65,9 +65,9 @@ class RemoveKeywordCollisions(keywords: Set[String]) extends Transform {
     }
 
     namedx match {
-      case ComponentName(n, _) :: Nil => n
-      case ModuleName(n, _)    :: Nil => n
-      case CircuitName(n)      :: Nil => n
+      case Seq(ComponentName(n, _)) => n
+      case Seq(ModuleName(n, _))    => n
+      case Seq(CircuitName(n))      => n
       case x => throw new PassException(
         s"Verilog renaming shouldn't result in multiple renames, but found '$named -> $namedx'")
     }
@@ -189,7 +189,7 @@ class RemoveKeywordCollisions(keywords: Set[String]) extends Transform {
 
     // Rename the circuit if the top module was renamed
     val mainx = renames.get(ModuleName(c.main, CircuitName(c.main))) match {
-      case Some(ModuleName(m, _) :: Nil) =>
+      case Some(Seq(ModuleName(m, _))) =>
         renames.rename(CircuitName(c.main), CircuitName(m))
         m
       case x@ Some(_) => throw new PassException(
diff --git a/src/test/scala/firrtlTests/UnitTests.scala b/src/test/scala/firrtlTests/UnitTests.scala
index 62ed561e..2cf9c001 100644
--- a/src/test/scala/firrtlTests/UnitTests.scala
+++ b/src/test/scala/firrtlTests/UnitTests.scala
@@ -95,6 +95,7 @@ class UnitTests extends FirrtlFlatSpec {
       ResolveKinds,
       InferTypes,
       CheckTypes,
+      ResolveGenders,
       ExpandConnects)
     val input =
      """circuit Unit :
diff --git a/src/test/scala/firrtlTests/WidthSpec.scala b/src/test/scala/firrtlTests/WidthSpec.scala
index 9ca965f6..ab8cb7ac 100644
--- a/src/test/scala/firrtlTests/WidthSpec.scala
+++ b/src/test/scala/firrtlTests/WidthSpec.scala
@@ -53,6 +53,7 @@ class WidthSpec extends FirrtlFlatSpec {
       ResolveKinds,
       InferTypes,
       CheckTypes,
+      ResolveGenders,
       InferWidths,
       CheckWidths)
     val input =
@@ -75,6 +76,7 @@ class WidthSpec extends FirrtlFlatSpec {
       ResolveKinds,
       InferTypes,
       CheckTypes,
+      ResolveGenders,
       InferWidths,
       CheckWidths)
     val input =
@@ -93,6 +95,7 @@ class WidthSpec extends FirrtlFlatSpec {
       ResolveKinds,
       InferTypes,
       CheckTypes,
+      ResolveGenders,
       InferWidths,
       CheckWidths)
     val input =
@@ -117,6 +120,7 @@ class WidthSpec extends FirrtlFlatSpec {
       ResolveKinds,
       InferTypes,
       CheckTypes,
+      ResolveGenders,
       InferWidths)
     val input =
       """circuit Unit :
@@ -138,6 +142,7 @@ class WidthSpec extends FirrtlFlatSpec {
       ResolveKinds,
       InferTypes,
       CheckTypes,
+      ResolveGenders,
       InferWidths)
     val input =
       """circuit Unit :