Combine cats (#851)

- Add firrtl.transforms.CombineCats
- Use CombineCats in LowFirrtlOptimization
- Modify Verilog emitter to allow for nested Cat DoPrims
- Modify firrtlEquivalenceTest to write input FIRRTL string to test directory

3 files changed, 93 insertions, 2 deletions

diff --git a/src/main/scala/firrtl/Emitter.scala b/src/main/scala/firrtl/Emitter.scala
index e28a3d20..0897b2db 100644
--- a/src/main/scala/firrtl/Emitter.scala
+++ b/src/main/scala/firrtl/Emitter.scala
@@ -246,7 +246,29 @@ class VerilogEmitter extends SeqTransform with Emitter {
        case _: UIntLiteral | _: SIntLiteral | _: WRef | _: WSubField =>
        case _ => throw EmitterException(s"Can't emit ${e.getClass.getName} as PrimOp argument")
      }
-     doprim.args foreach checkArgumentLegality
+
+     def checkCatArgumentLegality(e: Expression): Unit = e match {
+       case _: UIntLiteral | _: SIntLiteral | _: WRef | _: WSubField =>
+       case DoPrim(Cat, args, _, _) => args foreach(checkCatArgumentLegality)
+       case _ => throw EmitterException(s"Can't emit ${e.getClass.getName} as PrimOp argument")
+     }
+
+     def castCatArgs(a0: Expression, a1: Expression): Seq[Any] = {
+       val a0Seq = a0 match {
+         case cat@DoPrim(PrimOps.Cat, args, _, _) => castCatArgs(args.head, args(1))
+         case _ => Seq(cast(a0))
+       }
+       val a1Seq = a1 match {
+         case cat@DoPrim(PrimOps.Cat, args, _, _) => castCatArgs(args.head, args(1))
+         case _ => Seq(cast(a1))
+       }
+       a0Seq ++ Seq(",") ++ a1Seq
+     }
+
+     doprim.op match {
+       case Cat => doprim.args foreach(checkCatArgumentLegality)
+       case other => doprim.args foreach checkArgumentLegality
+     }
      doprim.op match {
        case Add => Seq(cast_if(a0), " + ", cast_if(a1))
        case Addw => Seq(cast_if(a0), " + ", cast_if(a1))
@@ -298,7 +320,7 @@ class VerilogEmitter extends SeqTransform with Emitter {
        case Andr => Seq("&", cast(a0))
        case Orr => Seq("|", cast(a0))
        case Xorr => Seq("^", cast(a0))
-       case Cat => Seq("{", cast(a0), ",", cast(a1), "}")
+       case Cat => "{" +: (castCatArgs(a0, a1) :+ "}")
        // If selecting zeroth bit and single-bit wire, just emit the wire
        case Bits if c0 == 0 && c1 == 0 && bitWidth(a0.tpe) == BigInt(1) => Seq(a0)
        case Bits if c0 == c1 => Seq(a0, "[", c0, "]")
diff --git a/src/main/scala/firrtl/LoweringCompilers.scala b/src/main/scala/firrtl/LoweringCompilers.scala
index 92f9a9a4..c22fe99f 100644
--- a/src/main/scala/firrtl/LoweringCompilers.scala
+++ b/src/main/scala/firrtl/LoweringCompilers.scala
@@ -108,6 +108,7 @@ class LowFirrtlOptimization extends CoreTransform {
     passes.memlib.VerilogMemDelays, // TODO move to Verilog emitter
     new firrtl.transforms.ConstantPropagation,
     passes.SplitExpressions,
+    new firrtl.transforms.CombineCats,
     passes.CommonSubexpressionElimination,
     new firrtl.transforms.DeadCodeElimination)
 }
diff --git a/src/main/scala/firrtl/transforms/CombineCats.scala b/src/main/scala/firrtl/transforms/CombineCats.scala
new file mode 100644
index 00000000..1265a5c3
--- /dev/null
+++ b/src/main/scala/firrtl/transforms/CombineCats.scala
@@ -0,0 +1,68 @@
+
+package firrtl
+package transforms
+
+import firrtl.ir._
+import firrtl.Mappers._
+import firrtl.PrimOps._
+import firrtl.WrappedExpression._
+import firrtl.annotations.NoTargetAnnotation
+
+import scala.collection.mutable
+
+case class MaxCatLenAnnotation(maxCatLen: Int) extends NoTargetAnnotation
+
+object CombineCats {
+  /** Mapping from references to the [[Expression]]s that drive them paired with their Cat length */
+  type Netlist = mutable.HashMap[WrappedExpression, (Int, Expression)]
+
+  def expandCatArgs(maxCatLen: Int, netlist: Netlist)(expr: Expression): (Int, Expression) = expr match {
+    case cat@DoPrim(Cat, args, _, _) =>
+      val (a0Len, a0Expanded) = expandCatArgs(maxCatLen - 1, netlist)(args.head)
+      val (a1Len, a1Expanded) = expandCatArgs(maxCatLen - a0Len, netlist)(args(1))
+      (a0Len + a1Len, cat.copy(args = Seq(a0Expanded, a1Expanded)).asInstanceOf[Expression])
+    case other =>
+      netlist.get(we(expr)).collect {
+        case (len, cat@DoPrim(Cat, _, _, _)) if maxCatLen >= len => expandCatArgs(maxCatLen, netlist)(cat)
+      }.getOrElse((1, other))
+  }
+
+  def onStmt(maxCatLen: Int, netlist: Netlist)(stmt: Statement): Statement = {
+    stmt.map(onStmt(maxCatLen, netlist)) match {
+      case node@DefNode(_, name, value) =>
+        val catLenAndVal = value match {
+          case cat@DoPrim(Cat, _, _, _) => expandCatArgs(maxCatLen, netlist)(cat)
+          case other => (1, other)
+        }
+        netlist(we(WRef(name))) = catLenAndVal
+        node.copy(value = catLenAndVal._2)
+      case other => other
+    }
+  }
+
+  def onMod(maxCatLen: Int)(mod: DefModule): DefModule = mod.map(onStmt(maxCatLen, new Netlist))
+}
+
+/** Combine Cat DoPrims
+  *
+  * Expands the arguments of any Cat DoPrims if they are references to other Cat DoPrims.
+  * Operates only on Cat DoPrims that are node values.
+  *
+  * Use [[MaxCatLenAnnotation]] to limit the number of elements that can be concatenated.
+  * The default maximum number of elements is 10.
+  */
+class CombineCats extends Transform {
+  def inputForm: LowForm.type = LowForm
+  def outputForm: LowForm.type = LowForm
+  val defaultMaxCatLen = 10
+
+  def execute(state: CircuitState): CircuitState = {
+    val maxCatLen = state.annotations.collectFirst {
+      case m: MaxCatLenAnnotation => m.maxCatLen
+    }.getOrElse(defaultMaxCatLen)
+
+    val modulesx = state.circuit.modules.map(CombineCats.onMod(maxCatLen))
+    state.copy(circuit = state.circuit.copy(modules = modulesx))
+  }
+}
+