Merge pull request #1556 from freechipsproject/legalize-andreduce

Add LegalizeAndReductionsTransform

5 files changed, 186 insertions, 15 deletions

diff --git a/src/main/scala/firrtl/Emitter.scala b/src/main/scala/firrtl/Emitter.scala
index 24e6fb5f..2ebf11b6 100644
--- a/src/main/scala/firrtl/Emitter.scala
+++ b/src/main/scala/firrtl/Emitter.scala
@@ -8,13 +8,14 @@ import scala.collection.mutable
 
 import firrtl.ir._
 import firrtl.passes._
+import firrtl.transforms.LegalizeAndReductionsTransform
 import firrtl.annotations._
 import firrtl.traversals.Foreachers._
 import firrtl.PrimOps._
 import firrtl.WrappedExpression._
 import Utils._
 import MemPortUtils.{memPortField, memType}
-import firrtl.options.{HasShellOptions, ShellOption, StageUtils, PhaseException, Unserializable}
+import firrtl.options.{Dependency, HasShellOptions, ShellOption, StageUtils, PhaseException, Unserializable}
 import firrtl.stage.{RunFirrtlTransformAnnotation, TransformManager}
 // Datastructures
 import scala.collection.mutable.ArrayBuffer
@@ -180,7 +181,9 @@ class VerilogEmitter extends SeqTransform with Emitter {
   def inputForm = LowForm
   def outputForm = LowForm
 
-  override def prerequisites = firrtl.stage.Forms.LowFormOptimized
+  override def prerequisites =
+    Dependency[LegalizeAndReductionsTransform] +:
+    firrtl.stage.Forms.LowFormOptimized
 
   override def optionalPrerequisiteOf = Seq.empty
 
@@ -1160,7 +1163,9 @@ class VerilogEmitter extends SeqTransform with Emitter {
 
 class MinimumVerilogEmitter extends VerilogEmitter with Emitter {
 
-  override def prerequisites = firrtl.stage.Forms.LowFormMinimumOptimized
+  override def prerequisites =
+    Dependency[LegalizeAndReductionsTransform] +:
+    firrtl.stage.Forms.LowFormMinimumOptimized
 
   override def transforms = new TransformManager(firrtl.stage.Forms.VerilogMinimumOptimized, prerequisites)
     .flattenedTransformOrder
diff --git a/src/main/scala/firrtl/transforms/LegalizeReductions.scala b/src/main/scala/firrtl/transforms/LegalizeReductions.scala
new file mode 100644
index 00000000..9446c896
--- /dev/null
+++ b/src/main/scala/firrtl/transforms/LegalizeReductions.scala
@@ -0,0 +1,49 @@
+package firrtl
+package transforms
+
+import firrtl.ir._
+import firrtl.Mappers._
+import firrtl.options.{Dependency, PreservesAll}
+import firrtl.Utils.BoolType
+
+
+object LegalizeAndReductionsTransform {
+
+  private def allOnesOfType(tpe: Type): Literal = tpe match {
+    case UIntType(width @ IntWidth(x)) => UIntLiteral((BigInt(1) << x.toInt) - 1, width)
+    case SIntType(width) => SIntLiteral(-1, width)
+
+  }
+
+  def onExpr(expr: Expression): Expression = expr.map(onExpr) match {
+    case DoPrim(PrimOps.Andr, Seq(arg), _,_) if bitWidth(arg.tpe) > 64 =>
+      DoPrim(PrimOps.Eq, Seq(arg, allOnesOfType(arg.tpe)), Seq(), BoolType)
+    case other => other
+  }
+
+  def onStmt(stmt: Statement): Statement = stmt.map(onStmt).map(onExpr)
+
+  def onMod(mod: DefModule): DefModule = mod.map(onStmt)
+}
+
+/** Turns andr for expression > 64-bit into equality check with all ones
+  *
+  * Workaround a bug in Verilator v4.026 - v4.032 (inclusive).
+  * For context, see https://github.com/verilator/verilator/issues/2300
+  */
+class LegalizeAndReductionsTransform extends Transform with DependencyAPIMigration with PreservesAll[Transform] {
+
+  override def prerequisites =
+    firrtl.stage.Forms.WorkingIR ++
+    Seq( Dependency(passes.CheckTypes),
+         Dependency(passes.CheckWidths))
+
+  override def optionalPrerequisites = Nil
+
+  override def optionalPrerequisiteOf = Nil
+
+  def execute(state: CircuitState): CircuitState = {
+    val modulesx = state.circuit.modules.map(LegalizeAndReductionsTransform.onMod(_))
+    state.copy(circuit = state.circuit.copy(modules = modulesx))
+  }
+}
diff --git a/src/test/scala/firrtlTests/CustomTransformSpec.scala b/src/test/scala/firrtlTests/CustomTransformSpec.scala
index ef1dc86d..d736ec3c 100644
--- a/src/test/scala/firrtlTests/CustomTransformSpec.scala
+++ b/src/test/scala/firrtlTests/CustomTransformSpec.scala
@@ -9,7 +9,7 @@ import firrtl.ir._
 
 import firrtl.stage.{FirrtlSourceAnnotation, FirrtlStage, Forms, RunFirrtlTransformAnnotation}
 import firrtl.options.Dependency
-import firrtl.transforms.IdentityTransform
+import firrtl.transforms.{IdentityTransform, LegalizeAndReductionsTransform}
 
 import firrtl.testutils._
 
@@ -149,17 +149,18 @@ class CustomTransformSpec extends FirrtlFlatSpec {
                   ))
   }
 
-  they should "run right before the emitter when inputForm=LowForm" in {
+  they should "run right before the emitter* when inputForm=LowForm" in {
 
     val custom = Dependency[IdentityLowForm]
 
-    def testOrder(emitter: Dependency[Emitter], preceders: Seq[Dependency[Transform]]): Unit = {
-      info(s"""${preceders.map(_.getSimpleName).mkString(" -> ")} -> ${custom.getSimpleName} -> ${emitter.getSimpleName} ok!""")
+    def testOrder(after: Seq[Dependency[Transform]], before: Seq[Dependency[Transform]]): Unit = {
+      val expectedSlice: Seq[Dependency[Transform]] = before ++: custom +: after
 
-      val compiler = new firrtl.stage.transforms.Compiler(Seq(custom, emitter))
+      info(expectedSlice.map(_.getSimpleName).mkString(" -> ") + " ok!")
+
+      val compiler = new firrtl.stage.transforms.Compiler(custom +: after)
       info("Transform Order: \n" + compiler.prettyPrint("    "))
 
-      val expectedSlice = preceders ++ Seq(custom, emitter)
 
       compiler
         .flattenedTransformOrder
@@ -172,10 +173,10 @@ class CustomTransformSpec extends FirrtlFlatSpec {
         .map(target => new firrtl.stage.transforms.Compiler(target))
         .map(_.flattenedTransformOrder.map(Dependency.fromTransform(_)))
 
-    Seq( (Dependency[LowFirrtlEmitter],      Seq(low.last)      ),
-         (Dependency[MinimumVerilogEmitter], Seq(lowMinOpt.last)),
-         (Dependency[VerilogEmitter],        Seq(lowOpt.last)    ),
-         (Dependency[SystemVerilogEmitter],  Seq(lowOpt.last)   )
+    Seq( (Seq(Dependency[LowFirrtlEmitter]),                                                  Seq(low.last)      ),
+         (Seq(Dependency[LegalizeAndReductionsTransform], Dependency[MinimumVerilogEmitter]), Seq(lowMinOpt.last)),
+         (Seq(Dependency[LegalizeAndReductionsTransform], Dependency[VerilogEmitter]),        Seq(lowOpt.last)    ),
+         (Seq(Dependency[LegalizeAndReductionsTransform], Dependency[SystemVerilogEmitter]),  Seq(lowOpt.last)   )
     ).foreach((testOrder _).tupled)
   }
 
diff --git a/src/test/scala/firrtlTests/LoweringCompilersSpec.scala b/src/test/scala/firrtlTests/LoweringCompilersSpec.scala
index 4a7a1700..b9143b26 100644
--- a/src/test/scala/firrtlTests/LoweringCompilersSpec.scala
+++ b/src/test/scala/firrtlTests/LoweringCompilersSpec.scala
@@ -348,7 +348,10 @@ class LoweringCompilersSpec extends FlatSpec with Matchers {
       new TransformManager(Forms.LowFormMinimumOptimized).flattenedTransformOrder ++
         Seq(new Transforms.LowToLow, new firrtl.MinimumVerilogEmitter)
     val tm = (new TransformManager(Seq(Dependency[firrtl.MinimumVerilogEmitter], Dependency[Transforms.LowToLow])))
-    compare(expected, tm)
+    val patches = Seq(
+      Add(60, Seq(Dependency[firrtl.transforms.LegalizeAndReductionsTransform]))
+    )
+    compare(expected, tm, patches)
   }
 
   it should "schedule inputForm=LowForm after LowFirrtlOptimizations for the VerilogEmitter" in {
@@ -356,7 +359,10 @@ class LoweringCompilersSpec extends FlatSpec with Matchers {
       new TransformManager(Forms.LowFormOptimized).flattenedTransformOrder ++
         Seq(new Transforms.LowToLow, new firrtl.VerilogEmitter)
     val tm = (new TransformManager(Seq(Dependency[firrtl.VerilogEmitter], Dependency[Transforms.LowToLow])))
-    compare(expected, tm)
+    val patches = Seq(
+      Add(67, Seq(Dependency[firrtl.transforms.LegalizeAndReductionsTransform]))
+    )
+    compare(expected, tm, patches)
   }
 
 }
diff --git a/src/test/scala/firrtlTests/transforms/LegalizeReductions.scala b/src/test/scala/firrtlTests/transforms/LegalizeReductions.scala
new file mode 100644
index 00000000..664701c3
--- /dev/null
+++ b/src/test/scala/firrtlTests/transforms/LegalizeReductions.scala
@@ -0,0 +1,110 @@
+// See LICENSE for license details.
+
+package firrtlTests.transforms
+
+import firrtl._
+import firrtl.ir.StringLit
+import firrtl.testutils._
+
+import org.scalatest.flatspec.AnyFlatSpec
+
+import java.io.File
+
+object LegalizeAndReductionsTransformSpec extends FirrtlRunners {
+  private case class Test(
+    name: String,
+    op: String,
+    input: BigInt,
+    expected: BigInt,
+    forceWidth: Option[Int] = None
+  ) {
+    def toFirrtl: String = {
+      val width = forceWidth.getOrElse(input.bitLength)
+      val inputLit = s"""UInt("h${input.toString(16)}")"""
+      val expectLit = s"""UInt("h${expected.toString(16)}")"""
+      val assertMsg = StringLit(s"Assertion failed! $op($inputLit) != $expectLit!\n").verilogEscape
+      // Reset the register to something different from the input
+      val regReset = if (input == 0) 1 else 0
+      s"""
+circuit $name :
+  module $name :
+    input clock : Clock
+    input reset : UInt<1>
+
+    node input = $inputLit
+    node expected = $expectLit
+
+    reg r : UInt<$width>, clock with : (reset => (reset, UInt($regReset)))
+    r <= input
+    node expr = $op(r)
+    node equal = eq(expr, expected)
+
+    reg count : UInt<2>, clock with : (reset => (reset, UInt(0)))
+    count <= tail(add(count, UInt(1)), 1)
+
+    when not(reset) :
+      when eq(count, UInt(1)) :
+        printf(clock, UInt(1), "input = %x, expected = %x, expr = %x, equal = %x\\n", input, expected, expr, equal)
+        when not(equal) :
+          printf(clock, UInt(1), $assertMsg)
+          stop(clock, UInt(1), 1)
+        else :
+          stop(clock, UInt(1), 0)
+"""
+    }
+  }
+
+  private def executeTest(test: Test): Unit = {
+    import firrtl.stage._
+    import firrtl.options.TargetDirAnnotation
+    val prefix = test.name
+    val testDir = createTestDirectory(s"LegalizeReductions.$prefix")
+    // Run FIRRTL
+    val annos =
+      FirrtlSourceAnnotation(test.toFirrtl) ::
+      TargetDirAnnotation(testDir.toString) ::
+      CompilerAnnotation(new MinimumVerilogCompiler) ::
+      Nil
+    val resultAnnos = (new FirrtlStage).run(annos)
+    val outputFilename = resultAnnos.collectFirst { case OutputFileAnnotation(f) => f }
+    outputFilename.toRight(s"Output file not found!")
+    // Copy Verilator harness
+    val harness = new File(testDir, "top.cpp")
+    copyResourceToFile(cppHarnessResourceName, harness)
+    // Run Verilator
+    verilogToCpp(prefix, testDir, Nil, harness, suppressVcd = true) #&&
+    cppToExe(prefix, testDir) !
+    loggingProcessLogger
+    // Run binary
+    if (!executeExpectingSuccess(prefix, testDir)) {
+      throw new Exception("Test failed!") with scala.util.control.NoStackTrace
+    }
+  }
+}
+
+
+class LegalizeAndReductionsTransformSpec extends AnyFlatSpec {
+
+  import LegalizeAndReductionsTransformSpec._
+
+  behavior of "LegalizeAndReductionsTransform"
+
+  private val tests =
+    //   name                      primop  input                          expected  width
+    Test("andreduce_ones",         "andr", BigInt("1"*68, 2),             1) ::
+    Test("andreduce_zero",         "andr", 0,                             0, Some(68)) ::
+    Test("orreduce_ones",          "orr",  BigInt("1"*68, 2),             1) ::
+    Test("orreduce_high_one",      "orr",  BigInt("1" + "0"*67, 2),       1) ::
+    Test("orreduce_zero",          "orr",  0,                             0, Some(68)) ::
+    Test("xorreduce_high_one",     "xorr", BigInt("1" + "0"*67, 2),       1) ::
+    Test("xorreduce_high_low_one", "xorr", BigInt("1" + "0"*66 + "1", 2), 0) ::
+    Test("xorreduce_zero",         "xorr", 0,                             0, Some(68)) ::
+    Nil
+
+  for (test <- tests) {
+    it should s"support ${test.name}" in {
+      executeTest(test)
+    }
+  }
+
+}