Fixing lint error: x + -1 (#1374)

* Generates lint-clean Verilog for the case: x + -1

...where x is anything and 1 is any literal.

Master behavior:

  input x : SInt<8>
  output z : SInt<9>
  z <= add(x, SInt(-2))

generates

  assign z = $signed(x) + -8'sh2;

After this PR:

  assign z = $signed(x) - 8'sh2;

If the literal is the maximum possible literal, a special case is triggered to properly trim the resulting subtraction.

Input:

  input x : SInt<2>
  output z : SInt<3>
  z <= add(x, SInt(-2))

now generates (after this PR)

  assign z = $signed(x) - 3'sh2;

* Updated documentation

* Change ArrayBuffer to ListBuffer

* Change name to minNegValue

* Remove mutable public interfaces

Co-authored-by: Albert Magyar <albert.magyar@gmail.com>
Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com>

4 files changed, 170 insertions, 3 deletions

diff --git a/src/main/scala/firrtl/Emitter.scala b/src/main/scala/firrtl/Emitter.scala
index 42137605..7ee652af 100644
--- a/src/main/scala/firrtl/Emitter.scala
+++ b/src/main/scala/firrtl/Emitter.scala
@@ -978,6 +978,7 @@ class VerilogEmitter extends SeqTransform with Emitter {
   /** Preamble for every emitted Verilog file */
   def transforms = Seq(
     new BlackBoxSourceHelper,
+    new FixAddingNegativeLiterals,
     new ReplaceTruncatingArithmetic,
     new InlineNotsTransform,
     new InlineBitExtractionsTransform,  // here after InlineNots to clean up not(not(...)) rename
diff --git a/src/main/scala/firrtl/transforms/FixAddingNegativeLiteralsTransform.scala b/src/main/scala/firrtl/transforms/FixAddingNegativeLiteralsTransform.scala
new file mode 100644
index 00000000..08bf4af4
--- /dev/null
+++ b/src/main/scala/firrtl/transforms/FixAddingNegativeLiteralsTransform.scala
@@ -0,0 +1,116 @@
+// See LICENSE for license details.
+
+package firrtl.transforms
+
+import firrtl.{CircuitState, LowForm, Namespace, PrimOps, Transform, Utils, WRef}
+import firrtl.ir._
+import firrtl.Mappers._
+import firrtl.PrimOps.{Add, AsSInt, Sub, Tail}
+
+import scala.collection.mutable
+
+object FixAddingNegativeLiterals {
+
+  /** Returns the maximum negative number represented by given width
+    * @param width width of the negative number
+    * @return maximum negative number
+    */
+  def minNegValue(width: BigInt): BigInt = -(1 << (width.toInt - 1))
+
+  /** Updates the type of the DoPrim from its arguments (e.g. if is UnknownType)
+    * @param d input DoPrim
+    * @return updated DoPrim with calculated type
+    */
+  def setType(d: DoPrim): DoPrim = {
+    PrimOps.set_primop_type(d)
+  }
+
+  /** Returns a module with fixed additions of negative literals
+    * @param m input module
+    * @return updated module
+    */
+  def fixupModule(m: DefModule): DefModule = {
+    val namespace = Namespace(m)
+    m map fixupStatement(namespace)
+  }
+
+  /** Returns a statement with fixed additions of negative literals
+    * @param namespace object to enabling creating unique names
+    * @param s input statement
+    * @return updated statement
+    */
+  def fixupStatement(namespace: Namespace)(s: Statement): Statement = {
+    val stmtBuffer = mutable.ListBuffer[Statement]()
+    val ret = s map fixupStatement(namespace) map fixupOnExpr(Utils.get_info(s), namespace, stmtBuffer)
+    if(stmtBuffer.isEmpty) {
+      ret
+    } else {
+      stmtBuffer += ret
+      Block(stmtBuffer.toList)
+    }
+  }
+
+  /** Returns a statement with fixed additions of negative literals
+    * @param info Info of statement containing this expression
+    * @param namespace object to enabling creating unique names
+    * @param e expression to fixup
+    * @return generated statements and the fixed expression
+    */
+  def fixupExpression(info: Info, namespace: Namespace)
+                     (e: Expression): (Seq[Statement], Expression) = {
+    val stmtBuffer = mutable.ListBuffer[Statement]()
+    val retExpr = fixupOnExpr(info, namespace, stmtBuffer)(e)
+    (stmtBuffer.toList, retExpr)
+  }
+
+  /** Returns a statement with fixed additions of negative literals
+    * @param info Info of statement containing this expression
+    * @param namespace object to enabling creating unique names
+    * @param stmtBuffer mutable buffer of statements - append to this for it to be inlined in the module
+    * @param e expression to fixup
+    * @return fixed expression
+    */
+  private def fixupOnExpr(info: Info, namespace: Namespace, stmtBuffer: mutable.ListBuffer[Statement])
+                         (e: Expression): Expression = {
+
+    // Helper function to create the subtraction expression
+    def fixupAdd(expr: Expression, litValue: BigInt, litWidth: BigInt): DoPrim = {
+      if(litValue == minNegValue(litWidth)) {
+        val posLiteral = SIntLiteral(-litValue)
+        assert(posLiteral.width.asInstanceOf[IntWidth].width - 1 == litWidth)
+        val sub = DefNode(info, namespace.newTemp, setType(DoPrim(Sub, Seq(expr, posLiteral), Nil, UnknownType)))
+        val tail = DefNode(info, namespace.newTemp, setType(DoPrim(Tail, Seq(WRef(sub)), Seq(1), UnknownType)))
+        stmtBuffer += sub
+        stmtBuffer += tail
+        setType(DoPrim(AsSInt, Seq(WRef(tail)), Nil, UnknownType))
+      } else {
+        val posLiteral = SIntLiteral(-litValue)
+        setType(DoPrim(Sub, Seq(expr, SIntLiteral(-litValue, IntWidth(litWidth))), Nil, UnknownType))
+      }
+    }
+
+    e map fixupOnExpr(info, namespace, stmtBuffer) match {
+      case DoPrim(Add, Seq(arg, lit@SIntLiteral(value, w@IntWidth(width))), Nil, t: SIntType) if value < 0 =>
+        fixupAdd(arg, value, width)
+      case DoPrim(Add, Seq(lit@SIntLiteral(value, w@IntWidth(width)), arg), Nil, t: SIntType) if value < 0 =>
+        fixupAdd(arg, value, width)
+      case other => other
+    }
+  }
+}
+
+/** Replaces adding a negative literal with subtracting that literal
+  *
+  * Verilator has a lint warning if a literal is negated in an expression, because it adds a bit to
+  * the literal and thus not all expressions in the add are the same. This is fixed here when we directly
+  * subtract the literal instead.
+  */
+class FixAddingNegativeLiterals extends Transform {
+  def inputForm = LowForm
+  def outputForm = LowForm
+
+  def execute(state: CircuitState): CircuitState = {
+    val modulesx = state.circuit.modules.map(FixAddingNegativeLiterals.fixupModule)
+    state.copy(circuit = state.circuit.copy(modules = modulesx))
+  }
+}
diff --git a/src/main/scala/firrtl/transforms/ReplaceTruncatingArithmetic.scala b/src/main/scala/firrtl/transforms/ReplaceTruncatingArithmetic.scala
index 1fe9a723..8aa1553a 100644
--- a/src/main/scala/firrtl/transforms/ReplaceTruncatingArithmetic.scala
+++ b/src/main/scala/firrtl/transforms/ReplaceTruncatingArithmetic.scala
@@ -1,3 +1,5 @@
+// See LICENSE for license details.
+
 package firrtl
 package transforms
 
@@ -24,10 +26,22 @@ object ReplaceTruncatingArithmetic {
     */
   def onExpr(netlist: Netlist)(expr: Expression): Expression =
     expr.map(onExpr(netlist)) match {
+      // If an unsigned wrapping add/sub
       case orig @ DoPrim(Tail, Seq(e), SeqBIOne, tailtpe) =>
         netlist.getOrElse(we(e), e) match {
-          case DoPrim(Add, args, cs, _) => DoPrim(Addw, args, cs, tailtpe)
-          case DoPrim(Sub, args, cs, _) => DoPrim(Subw, args, cs, tailtpe)
+          case DoPrim(Add, args, cs, u: UIntType) => DoPrim(Addw, args, cs, tailtpe)
+          case DoPrim(Sub, args, cs, u: UIntType) => DoPrim(Subw, args, cs, tailtpe)
+          case _ => orig // Not a candidate
+        }
+      // If a signed wrapping add/sub, there should be a cast
+      case orig @ DoPrim(AsSInt, Seq(x), _, casttpe) =>
+        netlist.getOrElse(we(x), x) match {
+          case DoPrim(Tail, Seq(e), SeqBIOne, tailtpe) =>
+            netlist.getOrElse(we(e), e) match {
+              case DoPrim(Add, args, cs, s: SIntType) => DoPrim(Addw, args, cs, casttpe)
+              case DoPrim(Sub, args, cs, s: SIntType) => DoPrim(Subw, args, cs, casttpe)
+              case _ => orig // Not a candidate
+            }
           case _ => orig // Not a candidate
         }
       case other => other // Not a candidate
diff --git a/src/test/scala/firrtlTests/VerilogEmitterTests.scala b/src/test/scala/firrtlTests/VerilogEmitterTests.scala
index bce9b155..f7f3a0bb 100644
--- a/src/test/scala/firrtlTests/VerilogEmitterTests.scala
+++ b/src/test/scala/firrtlTests/VerilogEmitterTests.scala
@@ -643,7 +643,7 @@ class VerilogEmitterSpec extends FirrtlFlatSpec {
         |z <= add(x, SInt(-1))
         |""".stripMargin
     )
-    result should containLine("assign z = $signed(x) + -4'sh1;")
+    result should containLine("assign z = $signed(x) - 4'sh1;")
   }
 
   it should "inline asSInt casts" in {
@@ -711,6 +711,42 @@ class VerilogEmitterSpec extends FirrtlFlatSpec {
     result should containLine("assign z = x == y;")
   }
 
+  it should "subtract positive literals instead of adding negative literals" in {
+    val compiler = new VerilogCompiler
+    val result = compileBody(
+      """input x : SInt<8>
+        |output z : SInt<9>
+        |z <= add(x, SInt(-2))
+        |""".stripMargin
+    )
+    result shouldNot containLine("assign z = $signed(x) + -8'sh2;")
+    result should    containLine("assign z = $signed(x) - 8'sh2;")
+  }
+
+  it should "subtract positive literals even with max negative literal" in {
+    val compiler = new VerilogCompiler
+    val result = compileBody(
+      """input x : SInt<2>
+        |output z : SInt<3>
+        |z <= add(x, SInt(-2))
+        |""".stripMargin
+    )
+    result shouldNot containLine("assign z = $signed(x) + -2'sh2;")
+    result should    containLine("assign z = $signed(x) - 3'sh2;")
+  }
+
+  it should "subtract positive literals even with max negative literal with no carryout" in {
+    val compiler = new VerilogCompiler
+    val result = compileBody(
+      """input x : SInt<2>
+        |output z : SInt<2>
+        |z <= add(x, SInt(-2))
+        |""".stripMargin
+    )
+    result shouldNot containLine("assign z = $signed(x) + -2'sh2;")
+    result should    containLine("assign _GEN_0 = $signed(x) - 3'sh2;")
+    result should    containLine("assign z = _GEN_0[1:0];")
+  }
 }
 
 class VerilogDescriptionEmitterSpec extends FirrtlFlatSpec {