Verilog emitter transform InlineBitExtractions (#1296)

* transform InlineBitExtractions

* InlineNotsTransform, InlineBitExtractionsTransform: inputForm/outputForm = UnknownForm

* clean up some minor redundancies from Adam review

* clarifications from Seldrige review

2 files changed, 117 insertions, 7 deletions

diff --git a/src/main/scala/firrtl/transforms/InlineBitExtractions.scala b/src/main/scala/firrtl/transforms/InlineBitExtractions.scala
new file mode 100644
index 00000000..c4f40700
--- /dev/null
+++ b/src/main/scala/firrtl/transforms/InlineBitExtractions.scala
@@ -0,0 +1,102 @@
+package firrtl
+package transforms
+
+import firrtl.ir._
+import firrtl.Mappers._
+import firrtl.PrimOps.{Bits, Head, Tail, Shr}
+import firrtl.Utils.{isBitExtract, isTemp}
+import firrtl.WrappedExpression._
+
+import scala.collection.mutable
+
+object InlineBitExtractionsTransform {
+
+  // Checks if an Expression is made up of only Bits terminated by a Literal or Reference.
+  // private because it's not clear if this definition of "Simple Expression" would be useful elsewhere.
+  // Note that this can have false negatives but MUST NOT have false positives.
+  private def isSimpleExpr(expr: Expression): Boolean = expr match {
+    case _: WRef | _: Literal | _: WSubField => true
+    case DoPrim(op, args, _,_) if isBitExtract(op) => args.forall(isSimpleExpr)
+    case _ => false
+  }
+
+  // replace Head/Tail/Shr with Bits for easier back-to-back Bits Extractions
+  private def lowerToDoPrimOpBits(expr: Expression): Expression = expr match {
+    case DoPrim(Head, rhs, c, tpe) if isSimpleExpr(expr) =>
+      val msb = bitWidth(rhs.head.tpe) - 1
+      val lsb = bitWidth(rhs.head.tpe) - c.head
+      DoPrim(Bits, rhs, Seq(msb,lsb), tpe)
+    case DoPrim(Tail, rhs, c, tpe) if isSimpleExpr(expr) =>
+      val msb = bitWidth(rhs.head.tpe) - c.head - 1
+      DoPrim(Bits, rhs, Seq(msb,0), tpe)
+    case DoPrim(Shr, rhs, c, tpe) if isSimpleExpr(expr) =>
+      DoPrim(Bits, rhs, Seq(bitWidth(rhs.head.tpe)-1, c.head), tpe)
+    case _ => expr // Not a candidate
+  }
+
+  /** Mapping from references to the [[firrtl.ir.Expression Expression]]s that drive them */
+  type Netlist = mutable.HashMap[WrappedExpression, Expression]
+
+  /** Recursively replace [[WRef]]s with new [[Expression]]s
+    *
+    * @param netlist a '''mutable''' HashMap mapping references to [[firrtl.ir.DefNode DefNode]]s to their connected
+    * [[firrtl.ir.Expression Expression]]s. It is '''not''' mutated in this function
+    * @param expr the Expression being transformed
+    * @return Returns expr with Bits inlined
+    */
+  def onExpr(netlist: Netlist)(expr: Expression): Expression = {
+    expr.map(onExpr(netlist)) match {
+      case e @ WRef(name, _,_,_) =>
+        netlist.get(we(e))
+               .filter(isBitExtract)
+               .getOrElse(e)
+      // replace back-to-back Bits Extractions
+      case lhs @ DoPrim(lop, ival, lc, ltpe) if isSimpleExpr(lhs) =>
+        ival.head match {
+          case of @ DoPrim(rop, rhs, rc, rtpe) if isSimpleExpr(of) =>
+            (lop, rop) match {
+              case (Head, Head) => DoPrim(Head, rhs, Seq(lc.head min rc.head), ltpe)
+              case (Tail, Tail) => DoPrim(Tail, rhs, Seq(lc.head + rc.head), ltpe)
+              case (Shr,  Shr)  => DoPrim(Shr,  rhs, Seq(lc.head + rc.head), ltpe)
+              case (_,_) => (lowerToDoPrimOpBits(lhs), lowerToDoPrimOpBits(of)) match {
+                case (DoPrim(Bits, _, Seq(lmsb, llsb), _), DoPrim(Bits, _, Seq(rmsb, rlsb), _)) =>
+                  DoPrim(Bits, rhs, Seq(lmsb+rlsb,llsb+rlsb), ltpe)
+                case (_,_) => lhs  // Not a candidate
+              }
+            }
+            case _ => lhs  // Not a candidate
+          }
+      case other => other // Not a candidate
+    }
+  }
+
+  /** Inline bits in a Statement
+    *
+    * @param netlist a '''mutable''' HashMap mapping references to [[firrtl.ir.DefNode DefNode]]s to their connected
+    * [[firrtl.ir.Expression Expression]]s. This function '''will''' mutate it if stmt is a [[firrtl.ir.DefNode
+    * DefNode]] with a Temporary name and a value that is a [[PrimOp]] Bits
+    * @param stmt the Statement being searched for nodes and transformed
+    * @return Returns stmt with Bits inlined
+    */
+  def onStmt(netlist: Netlist)(stmt: Statement): Statement =
+    stmt.map(onStmt(netlist)).map(onExpr(netlist)) match {
+      case node @ DefNode(_, name, value) if isTemp(name) =>
+        netlist(we(WRef(name))) = value
+        node
+      case other => other
+    }
+
+  /** Replaces bits in a Module */
+  def onMod(mod: DefModule): DefModule = mod.map(onStmt(new Netlist))
+}
+
+/** Inline nodes that are simple bits */
+class InlineBitExtractionsTransform extends Transform {
+  def inputForm = UnknownForm
+  def outputForm = UnknownForm
+
+  def execute(state: CircuitState): CircuitState = {
+    val modulesx = state.circuit.modules.map(InlineBitExtractionsTransform.onMod(_))
+    state.copy(circuit = state.circuit.copy(modules = modulesx))
+  }
+}
diff --git a/src/main/scala/firrtl/transforms/InlineNots.scala b/src/main/scala/firrtl/transforms/InlineNots.scala
index 3dab5168..299c130a 100644
--- a/src/main/scala/firrtl/transforms/InlineNots.scala
+++ b/src/main/scala/firrtl/transforms/InlineNots.scala
@@ -3,8 +3,8 @@ package transforms
 
 import firrtl.ir._
 import firrtl.Mappers._
-import firrtl.PrimOps.Not
-import firrtl.Utils.isTemp
+import firrtl.PrimOps.{Bits, Not}
+import firrtl.Utils.{isBitExtract, isTemp}
 import firrtl.WrappedExpression._
 
 import scala.collection.mutable
@@ -42,10 +42,18 @@ object InlineNotsTransform {
         netlist.get(we(e))
                .filter(isNot)
                .getOrElse(e)
+      // replace bits-of-not with not-of-bits to enable later bit extraction transform
+      case lhs @ DoPrim(op, Seq(lval), lcons, ltpe) if isBitExtract(op) && isSimpleExpr(lval) =>
+        netlist.getOrElse(we(lval), lval) match {
+          case DoPrim(Not, Seq(rhs), rcons, rtpe) =>
+            DoPrim(Not, Seq(DoPrim(op, Seq(rhs), lcons, ltpe)), rcons, ltpe)
+          case _ => lhs  // Not a candiate
+        }
       // replace back-to-back inversions with a straight rename
-      case lhs @ DoPrim(Not, Seq(inv), _,_) if isSimpleExpr(inv) =>
+      case lhs @ DoPrim(Not, Seq(inv), _, invtpe) if isSimpleExpr(lhs) && isSimpleExpr(inv) && (lhs.tpe == invtpe) && (bitWidth(lhs.tpe) == bitWidth(inv.tpe)) =>
         netlist.getOrElse(we(inv), inv) match {
-          case DoPrim(Not, Seq(rhs), _,_) if isSimpleExpr(inv) => rhs
+          case DoPrim(Not, Seq(rhs), _, rtpe) if (invtpe == rtpe) && (bitWidth(inv.tpe) == bitWidth(rhs.tpe)) =>
+            DoPrim(Bits, Seq(rhs), Seq(bitWidth(lhs.tpe)-1,0), rtpe)
           case _ => lhs  // Not a candiate
         }
       case other => other // Not a candidate
@@ -56,7 +64,7 @@ object InlineNotsTransform {
     *
     * @param netlist a '''mutable''' HashMap mapping references to [[firrtl.ir.DefNode DefNode]]s to their connected
     * [[firrtl.ir.Expression Expression]]s. This function '''will''' mutate it if stmt is a [[firrtl.ir.DefNode
-    * DefNode]] with a value that is a [[PrimOp]] Not
+    * DefNode]] with a Temporary name and a value that is a [[PrimOp]] Not
     * @param stmt the Statement being searched for nodes and transformed
     * @return Returns stmt with nots inlined
     */
@@ -74,8 +82,8 @@ object InlineNotsTransform {
 
 /** Inline nodes that are simple nots */
 class InlineNotsTransform extends Transform {
-  def inputForm = LowForm
-  def outputForm = LowForm
+  def inputForm = UnknownForm
+  def outputForm = UnknownForm
 
   def execute(state: CircuitState): CircuitState = {
     val modulesx = state.circuit.modules.map(InlineNotsTransform.onMod(_))