Add Expression Fuzzer (#1741)

Includes:
* Random generator of FIRRTL Expressions (UInt and SInt types)
* JQF SBT plugin and CLI
* Documentation in README.md

Co-authored-by: Jack Koenig <koenig@sifive.com>

7 files changed, 1395 insertions, 0 deletions

diff --git a/fuzzer/src/main/scala/firrtl/ExprGen.scala b/fuzzer/src/main/scala/firrtl/ExprGen.scala
new file mode 100644
index 00000000..fe85799a
--- /dev/null
+++ b/fuzzer/src/main/scala/firrtl/ExprGen.scala
@@ -0,0 +1,728 @@
+package firrtl.fuzzer
+
+import firrtl.ir._
+import firrtl.{PrimOps, Utils}
+
+import scala.language.higherKinds
+
+/** A generator that generates expressions of a certain type for a given IR type
+  */
+trait ExprGen[E <: Expression] { self =>
+  type Width = BigInt
+
+  /** The name of this generator, used for logging
+    */
+  def name: String
+
+  /** A [[StateGen]] that produces a one width UInt [[firrtl.ir.Expression Expression]]
+    */
+  def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, E]]
+
+  /** Takes a width and returns a [[StateGen]] that produces a UInt [[firrtl.ir.Expression Expression]] with the given width
+    *
+    * The input width will be greater than 1 and less than or equal to the
+    * maximum width allowed specified by the input state
+    */
+  def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, E]]
+
+  /** A [[StateGen]] that produces a one width SInt [[firrtl.ir.Expression Expression]]
+    */
+  def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, E]]
+
+  /** Takes a width and returns a [[StateGen]] that produces a SInt [[firrtl.ir.Expression Expression]] with the given width
+    *
+    * The input width will be greater than 1 and less than or equal to the
+    * maximum width allowed by the input state
+    */
+  def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, E]]
+
+  /** Returns a copy of this [[ExprGen]] that throws better exceptions
+    *
+    * Wraps this [[ExprGen]]'s functions with a try-catch that will wrap
+    * exceptions and record the name of this generator in an
+    * [[ExprGen.TraceException]].
+    */
+  def withTrace: ExprGen[E] = new ExprGen[E] {
+    import GenMonad.syntax._
+
+    def name = self.name
+
+    private def wrap[S: ExprState, G[_]: GenMonad](
+      name: String,
+      tpe: Type,
+      stateGen: StateGen[S, G, E]): StateGen[S, G, E] = {
+      StateGen { (s: S) =>
+        GenMonad[G].choose(0, 1).map ( _ =>
+          try {
+            GenMonad[G].generate(stateGen.run(s))
+          } catch {
+            case e: ExprGen.TraceException if e.trace.size < 10 =>
+              throw e.copy(trace = s"$name: ${tpe.serialize}" +: e.trace)
+            case e: IllegalArgumentException =>
+              throw ExprGen.TraceException(Seq(s"$name: ${tpe.serialize}"), e)
+          }
+        )
+      }
+    }
+
+    /** Identical to self.boolUIntGen, but will wrap exceptions in a [[ExprGen.TraceException]]
+      */
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, E]] = {
+      self.boolUIntGen.map(wrap(self.name, Utils.BoolType, _))
+    }
+
+    /** Identical to self.uintGen, but will wrap exceptions in a [[ExprGen.TraceException]]
+      */
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, E]] = {
+      self.uintGen.map(fn => (width: Width) => wrap(self.name, UIntType(IntWidth(width)), fn(width)))
+    }
+
+    /** Identical to self.boolSIntGen, but will wrap exceptions in a [[ExprGen.TraceException]]
+      */
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, E]] = {
+      self.boolSIntGen.map(wrap(self.name, SIntType(IntWidth(1)), _))
+    }
+
+    /** Identical to self.sintGen, but will wrap exceptions in a [[ExprGen.TraceException]]
+      */
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, E]] = {
+      self.sintGen.map(fn => (width: Width) => wrap(self.name, SIntType(IntWidth(width)), fn(width)))
+    }
+  }
+}
+
+/** An Expression Generator that generates [[firrtl.ir.DoPrim DoPrim]]s of the given operator
+  */
+abstract class DoPrimGen(val primOp: PrimOp) extends ExprGen[DoPrim] {
+  def name = primOp.serialize
+}
+
+object ExprGen {
+  type Width = BigInt
+
+  import GenMonad.syntax._
+
+  private def printStack(e: Throwable): String = {
+    val sw = new java.io.StringWriter()
+    val pw = new java.io.PrintWriter(sw)
+    e.printStackTrace(pw)
+    pw.flush()
+    sw.toString
+  }
+
+  case class TraceException(trace: Seq[String], cause: Throwable) extends Exception(
+    s"cause: ${printStack(cause)}\ntrace:\n${trace.reverse.mkString("\n")}\n"
+  )
+
+  def genWidth[G[_]: GenMonad](min: Int, max: Int): G[IntWidth] = GenMonad[G].choose(min, max).map(IntWidth(_))
+  def genWidthMax[G[_]: GenMonad](max: Int): G[IntWidth] = genWidth(1, max)
+
+  private def makeBinDoPrimStateGen[S: ExprState, G[_]: GenMonad](
+    primOp: PrimOp,
+    typeGen: Int => G[(Type, Type, Type)]): StateGen[S, G, DoPrim] = {
+    for {
+      t <- StateGen.inspectG((s: S) => typeGen(ExprState[S].maxWidth(s)))
+      (tpe1, tpe2, exprTpe) = t
+      expr1 <- ExprState[S].exprGen(tpe1)
+      expr2 <- ExprState[S].exprGen(tpe2)
+    } yield {
+      DoPrim(primOp, Seq(expr1, expr2), Seq.empty, exprTpe)
+    }
+  }
+
+  private def makeUnaryDoPrimStateGen[S: ExprState, G[_]: GenMonad](
+    primOp: PrimOp,
+    typeGen: Int => G[(Type, Type)]): StateGen[S, G, DoPrim] = {
+    for {
+      p <- StateGen.inspectG((s: S) => typeGen(ExprState[S].maxWidth(s)))
+      (tpe1, exprTpe) = p
+      expr1 <- ExprState[S].exprGen(tpe1)
+    } yield {
+      DoPrim(primOp, Seq(expr1), Seq.empty, exprTpe)
+    }
+  }
+
+  private def log2Floor(i: Int): Int = {
+    if (i > 0 && ((i & (i - 1)) == 0)) {
+      BigInt(i - 1).bitLength
+    } else {
+      BigInt(i - 1).bitLength - 1
+    }
+  }
+
+  def inspectMinWidth[S: ExprState, G[_]: GenMonad](min: Int): StateGen[S, G, IntWidth] = {
+    StateGen.inspectG { s =>
+      val maxWidth = ExprState[S].maxWidth(s)
+      GenMonad[G].choose(min, maxWidth).map(IntWidth(_))
+    }
+  }
+
+
+  object ReferenceGen extends ExprGen[Reference] {
+    def name = "Ref"
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, Reference]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, Reference]] = Some { width =>
+      referenceGenImp(UIntType(IntWidth(width)))
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, Reference]]  = sintGen.map(_(1))
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, Reference]] = Some { width =>
+      referenceGenImp(SIntType(IntWidth(width)))
+    }
+
+    private def referenceGenImp[S: ExprState, G[_]: GenMonad](tpe: Type): StateGen[S, G, Reference] = {
+      for {
+        // don't bother randomizing name, because it usually does not help with coverage
+        tryName <- StateGen.pure("ref")
+        ref <- ExprState[S].withRef(Reference(tryName, tpe))
+      } yield {
+        ref
+      }
+    }
+  }
+
+  object LiteralGen extends ExprGen[Literal] {
+    def name = "Literal"
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, Literal]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, Literal]] = Some { width =>
+      uintLiteralGenImp(width)
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, Literal]] = sintGen.map(_(1))
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, Literal]] = Some { width =>
+      sintLiteralGenImp(width)
+    }
+
+    private def uintLiteralGenImp[S: ExprState, G[_]: GenMonad](width: Width): StateGen[S, G, Literal] = {
+      val maxValue = if (width < BigInt(31)) {
+        (1 << width.toInt) - 1
+      } else {
+        Int.MaxValue
+      }
+      StateGen.liftG(for {
+        value <- GenMonad[G].choose(0, maxValue)
+      } yield {
+        UIntLiteral(value, IntWidth(width))
+      })
+    }
+
+    private def sintLiteralGenImp[S: ExprState, G[_]: GenMonad](width: Width): StateGen[S, G, Literal] = {
+      StateGen.liftG(
+        if (width <= BigInt(32)) {
+          GenMonad[G].choose(-(1 << (width.toInt - 1)), (1 << (width.toInt - 1)) - 1).map { value =>
+            SIntLiteral(value, IntWidth(width))
+          }
+        } else {
+          GenMonad[G].choose(Int.MinValue, Int.MaxValue).map { value =>
+            SIntLiteral(value, IntWidth(width))
+          }
+        }
+      )
+    }
+  }
+
+  abstract class AddSubDoPrimGen(isAdd: Boolean) extends DoPrimGen(if (isAdd) PrimOps.Add else PrimOps.Sub) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { width =>
+        def typeGen(maxWidth: Int): G[(Type, Type, Type)] = for {
+          randWidth <- GenMonad[G].choose(1, width.toInt - 1)
+          flip <- GenMonad.bool
+        } yield {
+          if (flip) {
+            (UIntType(IntWidth(randWidth)), UIntType(IntWidth(width.toInt - 1)), UIntType(IntWidth(width)))
+          } else {
+            (UIntType(IntWidth(width.toInt - 1)), UIntType(IntWidth(randWidth)), UIntType(IntWidth(width)))
+          }
+        }
+        makeBinDoPrimStateGen(primOp, typeGen)
+      }
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { width =>
+        def typeGen(maxWidth: Int): G[(Type, Type, Type)] = for {
+          randWidth <- GenMonad[G].choose(1, width.toInt - 1)
+          flip <- GenMonad.bool
+        } yield {
+          if (flip) {
+            (SIntType(IntWidth(randWidth)), SIntType(IntWidth(width.toInt - 1)), SIntType(IntWidth(width)))
+          } else {
+            (SIntType(IntWidth(width.toInt - 1)), SIntType(IntWidth(randWidth)), SIntType(IntWidth(width)))
+          }
+        }
+        makeBinDoPrimStateGen(primOp, typeGen)
+      }
+    }
+  }
+
+  object AddDoPrimGen extends AddSubDoPrimGen(isAdd = true)
+  object SubDoPrimGen extends AddSubDoPrimGen(isAdd = false)
+
+  object MulDoPrimGen extends DoPrimGen(PrimOps.Mul) {
+    private def imp[S: ExprState, G[_]: GenMonad](isUInt: Boolean): Option[Width => StateGen[S, G, DoPrim]] = {
+      val tpe = if (isUInt) UIntType(_) else SIntType(_)
+      Some { totalWidth =>
+        def typeGen(maxWidth: Int): G[(Type, Type, Type)] = for {
+          width1 <- GenMonad[G].choose(1, totalWidth.toInt - 1)
+          flip <- GenMonad.bool
+        } yield {
+          val t1 = tpe(IntWidth(math.max(totalWidth.toInt - width1, 0)))
+          val t2 = tpe(IntWidth(width1))
+          val t3 = tpe(IntWidth(totalWidth))
+          if (flip) (t2, t1, t3) else (t1, t2, t3)
+        }
+        makeBinDoPrimStateGen(primOp, typeGen)
+      }
+    }
+
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = true)
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = false)
+  }
+
+  object DivDoPrimGen extends DoPrimGen(PrimOps.Div) {
+    private def imp[S: ExprState, G[_]: GenMonad](isUInt: Boolean): Option[Width => StateGen[S, G, DoPrim]] = {
+      val tpe = if (isUInt) UIntType(_) else SIntType(_)
+      Some { resultWidth =>
+        val numWidth = if (isUInt) resultWidth.toInt else (resultWidth.toInt - 1)
+        def typeGen(maxWidth: Int): G[(Type, Type, Type)] = for {
+          denWidth <- genWidthMax(maxWidth)
+        } yield {
+          (tpe(IntWidth(numWidth)), tpe(denWidth), tpe(IntWidth(resultWidth)))
+        }
+        makeBinDoPrimStateGen(primOp, typeGen)
+      }
+    }
+
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = true)
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = false)
+  }
+
+  object RemDoPrimGen extends DoPrimGen(PrimOps.Rem) {
+    private def imp[S: ExprState, G[_]: GenMonad](isUInt: Boolean): Option[Width => StateGen[S, G, DoPrim]] = {
+      val tpe = if (isUInt) UIntType(_) else SIntType(_)
+      Some { resultWidth =>
+        def typeGen(maxWidth: Int): G[(Type, Type, Type)] = for {
+          argWidth <- genWidth(resultWidth.toInt, maxWidth)
+          flip <- GenMonad.bool
+        } yield {
+          val t1 = UIntType(argWidth)
+          val t2 = UIntType(IntWidth(resultWidth))
+          val t3 = t2
+          if (flip) (t2, t1, t3) else (t1, t2, t3)
+        }
+        makeBinDoPrimStateGen(primOp, typeGen)
+      }
+    }
+
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = true)
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = sintGen.map(_(1))
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = false)
+  }
+
+  abstract class CmpDoPrimGen(primOp: PrimOp) extends DoPrimGen(primOp) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = {
+      def typeGen(maxWidth: Int): G[(Type, Type, Type)] = for {
+        width1 <- genWidthMax(maxWidth)
+        width2 <- genWidthMax(maxWidth)
+        tpe <- GenMonad[G].oneOf(UIntType(_), SIntType(_))
+      } yield {
+        (tpe(width1), tpe(width2), Utils.BoolType)
+      }
+      Some(makeBinDoPrimStateGen(primOp, typeGen))
+    }
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+  }
+  object LtDoPrimGen extends CmpDoPrimGen(PrimOps.Lt)
+  object LeqDoPrimGen extends CmpDoPrimGen(PrimOps.Leq)
+  object GtDoPrimGen extends CmpDoPrimGen(PrimOps.Gt)
+  object GeqDoPrimGen extends CmpDoPrimGen(PrimOps.Geq)
+  object EqDoPrimGen extends CmpDoPrimGen(PrimOps.Eq)
+  object NeqDoPrimGen extends CmpDoPrimGen(PrimOps.Neq)
+
+  object PadDoPrimGen extends DoPrimGen(PrimOps.Pad) {
+    private def imp[S: ExprState, G[_]: GenMonad](isUInt: Boolean): Option[Width => StateGen[S, G, DoPrim]] = {
+      val tpe = if (isUInt) UIntType(_) else SIntType(_)
+      Some { resultWidth =>
+        for {
+          width1 <- StateGen.liftG(genWidthMax(resultWidth.toInt))
+          flip <- StateGen.liftG(GenMonad.bool)
+          expr <- ExprState[S].exprGen(tpe(if (flip) IntWidth(resultWidth) else width1))
+        } yield {
+          DoPrim(primOp, Seq(expr), Seq(if (flip) width1.width else resultWidth), tpe(IntWidth(resultWidth)))
+        }
+      }
+    }
+
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = true)
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = sintGen.map(_(1))
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = false)
+  }
+
+  object ShlDoPrimGen extends DoPrimGen(PrimOps.Shl) {
+    private def imp[S: ExprState, G[_]: GenMonad](isUInt: Boolean): Option[Width => StateGen[S, G, DoPrim]] = {
+      val tpe = if (isUInt) UIntType(_) else SIntType(_)
+      Some { totalWidth =>
+        for {
+          width1 <- StateGen.liftG(genWidthMax(totalWidth.toInt))
+          expr <- ExprState[S].exprGen(tpe(width1))
+        } yield {
+          val width2 = totalWidth.toInt - width1.width.toInt
+          DoPrim(primOp, Seq(expr), Seq(width2), tpe(IntWidth(totalWidth)))
+        }
+      }
+    }
+
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = true)
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = false)
+  }
+
+  object ShrDoPrimGen extends DoPrimGen(PrimOps.Shr) {
+    private def imp[S: ExprState, G[_]: GenMonad](isUInt: Boolean): Option[Width => StateGen[S, G, DoPrim]] = {
+      val tpe = if (isUInt) UIntType(_) else SIntType(_)
+      Some { minWidth =>
+        for {
+          exprWidth <- inspectMinWidth(minWidth.toInt)
+          expr <- ExprState[S].exprGen(tpe(exprWidth))
+          shamt <- StateGen.liftG(if (minWidth == BigInt(1)) {
+            GenMonad[G].choose(exprWidth.width.toInt - minWidth.toInt, Int.MaxValue)
+          } else {
+            GenMonad[G].const(exprWidth.width.toInt - minWidth.toInt)
+          })
+        } yield {
+          DoPrim(primOp, Seq(expr), Seq(shamt), tpe(IntWidth(minWidth)))
+        }
+      }
+    }
+
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = true)
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = sintGen.map(_(1))
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = false)
+  }
+
+  object DshlDoPrimGen extends DoPrimGen(PrimOps.Dshl) {
+    private def imp[S: ExprState, G[_]: GenMonad](isUInt: Boolean): Option[Width => StateGen[S, G, DoPrim]] = {
+      val tpe = if (isUInt) UIntType(_) else SIntType(_)
+      Some { totalWidth =>
+        val shWidthMax = log2Floor(totalWidth.toInt)
+        def typeGen(maxWidth: Int): G[(Type, Type, Type)] = for {
+          shWidth <- genWidthMax(shWidthMax)
+        } yield {
+          val w1 = totalWidth.toInt - ((1 << shWidth.width.toInt) - 1)
+          // println(s"TOTALWIDTH: $totalWidth, SHWIDHTMAX: ${shWidthMax}, SHWIDTH: $shWidth, ARGWITH: $w1")
+          (tpe(IntWidth(w1)), UIntType(shWidth), tpe(IntWidth(totalWidth)))
+        }
+        makeBinDoPrimStateGen(primOp, typeGen)
+      }
+    }
+
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = true)
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = false)
+  }
+
+  object DshrDoPrimGen extends DoPrimGen(PrimOps.Dshr) {
+    private def imp[S: ExprState, G[_]: GenMonad](isUInt: Boolean): Option[Width => StateGen[S, G, DoPrim]] = {
+      val tpe = if (isUInt) UIntType(_) else SIntType(_)
+      Some { width =>
+        def typeGen(maxWidth: Int): G[(Type, Type, Type)] = for {
+          w2 <- genWidthMax(maxWidth)
+        } yield {
+          (tpe(IntWidth(width)), tpe(w2), tpe(IntWidth(width)))
+        }
+        makeBinDoPrimStateGen(primOp, typeGen)
+      }
+    }
+
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = true)
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = sintGen.map(_(1))
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = imp(isUInt = false)
+  }
+
+  object CvtDoPrimGen extends DoPrimGen(PrimOps.Cvt) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = {
+      Some {
+        def typeGen(maxWidth: Int): G[(Type, Type)] = {
+          val resultType = SIntType(IntWidth(1))
+          GenMonad[G].const(resultType -> resultType)
+        }
+        makeUnaryDoPrimStateGen(primOp, typeGen)
+      }
+    }
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { width =>
+        def typeGen(maxWidth: Int): G[(Type, Type)] = for {
+          isUInt <- GenMonad[G].oneOf(true, false)
+        } yield {
+          val resultType = SIntType(IntWidth(width))
+          if (isUInt) {
+            UIntType(IntWidth(width.toInt - 1)) -> resultType
+          } else {
+            resultType -> resultType
+          }
+        }
+        makeUnaryDoPrimStateGen(primOp, typeGen)
+      }
+    }
+  }
+
+  object NegDoPrimGen extends DoPrimGen(PrimOps.Neg) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { width =>
+        def typeGen(maxWidth: Int): G[(Type, Type)] = for {
+          isUInt <- GenMonad[G].oneOf(true, false)
+        } yield {
+          val resultType = SIntType(IntWidth(width))
+          if (isUInt) {
+            UIntType(IntWidth(width.toInt - 1)) -> resultType
+          } else {
+            SIntType(IntWidth(width.toInt - 1)) -> resultType
+          }
+        }
+        makeUnaryDoPrimStateGen(primOp, typeGen)
+      }
+    }
+  }
+
+  object NotDoPrimGen extends DoPrimGen(PrimOps.Not) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { width =>
+        def typeGen(maxWidth: Int): G[(Type, Type)] = for {
+          isUInt <- GenMonad[G].oneOf(true, false)
+        } yield {
+          val resultType = UIntType(IntWidth(width))
+          if (isUInt) {
+            resultType -> resultType
+          } else {
+            SIntType(IntWidth(width)) -> resultType
+          }
+        }
+        makeUnaryDoPrimStateGen(primOp, typeGen)
+      }
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+  }
+
+  abstract class BitwiseDoPrimGen(primOp: PrimOp) extends DoPrimGen(primOp) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { width =>
+        def typeGen(maxWidth: Int): G[(Type, Type, Type)] = for {
+          width1 <- genWidthMax(width.toInt)
+          flip <- GenMonad.bool
+          tpe <- GenMonad[G].oneOf(UIntType(_), SIntType(_))
+        } yield {
+          val t1 = tpe(width1)
+          val t2 = tpe(IntWidth(width))
+          val t3 = UIntType(IntWidth(width))
+          if (flip) (t2, t1, t3) else (t1, t2, t3)
+        }
+        makeBinDoPrimStateGen(primOp, typeGen)
+      }
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+  }
+  object AndDoPrimGen extends BitwiseDoPrimGen(PrimOps.And)
+  object OrDoPrimGen extends BitwiseDoPrimGen(PrimOps.Or)
+  object XorDoPrimGen extends BitwiseDoPrimGen(PrimOps.Xor)
+
+  abstract class ReductionDoPrimGen(primOp: PrimOp) extends DoPrimGen(primOp) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = {
+      Some {
+        def typeGen(maxWidth: Int): G[(Type, Type)] = for {
+          width1 <- genWidthMax(maxWidth)
+          tpeFn <- GenMonad[G].oneOf(UIntType(_), SIntType(_))
+        } yield {
+          (tpeFn(width1), Utils.BoolType)
+        }
+        makeUnaryDoPrimStateGen(primOp, typeGen)
+      }
+    }
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+  }
+  object AndrDoPrimGen extends ReductionDoPrimGen(PrimOps.Andr)
+  object OrrDoPrimGen extends ReductionDoPrimGen(PrimOps.Orr)
+  object XorrDoPrimGen extends ReductionDoPrimGen(PrimOps.Xorr)
+
+  object CatDoPrimGen extends DoPrimGen(PrimOps.Cat) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { totalWidth =>
+        def typeGen(maxWidth: Int): G[(Type, Type, Type)] = for {
+          width1 <- GenMonad[G].choose(1, totalWidth.toInt - 1)
+          flip <- GenMonad.bool
+          tpe <- GenMonad[G].oneOf(UIntType(_), SIntType(_))
+        } yield {
+          val t1 = tpe(IntWidth(totalWidth.toInt - width1))
+          val t2 = tpe(IntWidth(width1))
+          val t3 = UIntType(IntWidth(totalWidth))
+          if (flip) (t2, t1, t3) else (t1, t2, t3)
+        }
+        makeBinDoPrimStateGen(primOp, typeGen)
+      }
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+  }
+
+  object BitsDoPrimGen extends DoPrimGen(PrimOps.Bits) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { resultWidth =>
+        for {
+          argWidth <- inspectMinWidth(resultWidth.toInt)
+          lo <- StateGen.liftG(GenMonad[G].choose(0, argWidth.width.toInt - resultWidth.toInt))
+          tpe <- StateGen.liftG(GenMonad[G].oneOf(UIntType(_), SIntType(_)))
+          arg <- ExprState[S].exprGen(tpe(argWidth))
+        } yield {
+          DoPrim(primOp, Seq(arg), Seq(lo + resultWidth - 1, lo), UIntType(IntWidth(resultWidth)))
+        }
+      }
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+  }
+
+  object HeadDoPrimGen extends DoPrimGen(PrimOps.Head) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { resultWidth =>
+        for {
+          argWidth <- inspectMinWidth(resultWidth.toInt)
+          tpe <- StateGen.liftG(GenMonad[G].oneOf(UIntType(_), SIntType(_)))
+          arg <- ExprState[S].exprGen(tpe(argWidth))
+        } yield {
+          DoPrim(primOp, Seq(arg), Seq(resultWidth), UIntType(IntWidth(resultWidth)))
+        }
+      }
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+  }
+
+  object TailDoPrimGen extends DoPrimGen(PrimOps.Tail) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { totalWidth =>
+        for {
+          maxWidth <- StateGen.inspect((s: S) => ExprState[S].maxWidth(s))
+          tailNum <- if (totalWidth < BigInt(maxWidth)) {
+            StateGen.liftG[S, G, Int](GenMonad[G].choose(1, maxWidth - totalWidth.toInt))
+          } else {
+            StateGen.pure[S, G, Int](0)
+          }
+          tpe <- StateGen.liftG(GenMonad[G].oneOf(UIntType(_), SIntType(_)))
+          arg <- ExprState[S].exprGen(tpe(IntWidth(totalWidth + tailNum)))
+        } yield {
+          DoPrim(primOp, Seq(arg), Seq(tailNum), UIntType(IntWidth(totalWidth)))
+        }
+      }
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+  }
+
+  object AsUIntDoPrimGen extends DoPrimGen(PrimOps.AsUInt) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { width =>
+        val intWidth = IntWidth(width)
+        for {
+          tpe <- StateGen.liftG(GenMonad[G].oneOf(UIntType(_), SIntType(_)))
+          arg <- ExprState[S].exprGen(tpe(intWidth))
+        } yield {
+          DoPrim(primOp, Seq(arg), Seq(), UIntType(intWidth))
+        }
+      }
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+  }
+
+  object AsSIntDoPrimGen extends DoPrimGen(PrimOps.AsSInt) {
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = None
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = None
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, DoPrim]] = sintGen.map(_(1))
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, DoPrim]] = {
+      Some { width =>
+        val intWidth = IntWidth(width)
+        for {
+          tpe <- StateGen.liftG(GenMonad[G].oneOf(UIntType(_), SIntType(_)))
+          arg <- ExprState[S].exprGen(tpe(intWidth))
+        } yield {
+          DoPrim(primOp, Seq(arg), Seq(), SIntType(intWidth))
+        }
+      }
+    }
+  }
+
+  object MuxGen extends ExprGen[Mux] {
+    def name = "mux"
+    private def imp[S: ExprState, G[_]: GenMonad](isUInt: Boolean)(width: BigInt): StateGen[S, G, Mux] = {
+      val tpe = if (isUInt) UIntType(_) else SIntType(_)
+      // spec states that types must be equivalent, but in practice we allow differing widths
+      for {
+        cond <- ExprState[S].exprGen(Utils.BoolType)
+        flip <- StateGen.liftG(GenMonad.bool)
+        expr1 <- ExprState[S].exprGen(tpe(IntWidth(width)))
+        width2 <- StateGen.liftG(genWidthMax(width.toInt))
+        expr2 <- ExprState[S].exprGen(tpe(width2))
+      } yield {
+        Mux(cond, expr1, expr2, tpe(IntWidth(width)))
+      }
+    }
+    def boolUIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, Mux]] = uintGen.map(_(1))
+    def uintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, Mux]] = {
+      Some { imp(isUInt = true) }
+    }
+
+    def boolSIntGen[S: ExprState, G[_]: GenMonad]: Option[StateGen[S, G, Mux]] = sintGen.map(_(1))
+    def sintGen[S: ExprState, G[_]: GenMonad]: Option[Width => StateGen[S, G, Mux]] = {
+      Some { imp(isUInt = false) }
+    }
+  }
+}
diff --git a/fuzzer/src/main/scala/firrtl/ExprGenParams.scala b/fuzzer/src/main/scala/firrtl/ExprGenParams.scala
new file mode 100644
index 00000000..909f3a16
--- /dev/null
+++ b/fuzzer/src/main/scala/firrtl/ExprGenParams.scala
@@ -0,0 +1,213 @@
+package firrtl.fuzzer
+
+import firrtl.{Namespace, Utils}
+import firrtl.ir._
+
+import scala.language.higherKinds
+
+/** A set of parameters for randomly generating [[firrtl.ir.Expression Expression]]s
+  */
+sealed trait ExprGenParams {
+
+  /** The maximum levels of nested sub-expressions that may be generated
+    */
+  def maxDepth: Int
+
+  /** The maximum width of any generated expression, including sub-expressions
+    */
+  def maxWidth: Int
+
+  /** A list of frequency/expression generator pairs
+    *
+    * The frequency number determines the probability that the corresponding
+    * generator will be chosen. i.e. for sequece Seq(1 -> A, 2 -> B, 3 -> C),
+    * the probabilities for A, B, and C are 1/6, 2/6, and 3/6 respectively.
+    * This sequency must be non-empty and all frequency numbers must be greater
+    * than zero.
+    */
+  def generators: Seq[(Int, ExprGen[_ <: Expression])]
+
+  /** The set of generated references that don't have a corresponding declaration
+    */
+  protected def unboundRefs: Set[Reference]
+
+  /** The namespace to use for generating new [[firrtl.ir.Reference Reference]]s
+    */
+  protected def namespace: Namespace
+
+  /** Returns a copy of this [[ExprGenParams]] with the maximum depth decremented
+    */
+  protected def decrementDepth: ExprGenParams
+
+  /** Returns a copy of this [[ExprGenParams]] with the maximum depth incremented
+    */
+  protected def incrementDepth: ExprGenParams
+
+  /** Returns a copy of this [[ExprGenParams]] with the reference added to the set of unbound references
+    */
+  protected def withRef(ref: Reference): ExprGenParams
+
+
+  import GenMonad.syntax._
+
+  /** Generator that generates an expression and wraps it in a Module
+    *
+    *  The generated references are bound to input ports and the generated
+    *  expression is assigned to an output port.
+    */
+  private def exprMod[G[_]: GenMonad]: StateGen[ExprGenParams, G, Module] = {
+    for {
+      width <- StateGen.inspectG((s: ExprGenParams) => ExprGen.genWidth(1, ExprState[ExprGenParams].maxWidth(s)))
+      tpe <- StateGen.liftG(GenMonad.frequency(
+        2 -> UIntType(width),
+        2 -> SIntType(width),
+        1 -> Utils.BoolType
+      ))
+      expr <- ExprState[ExprGenParams].exprGen(tpe)
+      outputPortRef <- tpe match {
+        case UIntType(IntWidth(width)) if width == BigInt(1) => ExprGen.ReferenceGen.boolUIntGen[ExprGenParams, G].get
+        case UIntType(IntWidth(width)) => ExprGen.ReferenceGen.uintGen[ExprGenParams, G].get(width)
+        case SIntType(IntWidth(width)) if width == BigInt(1) => ExprGen.ReferenceGen.boolSIntGen[ExprGenParams, G].get
+        case SIntType(IntWidth(width)) => ExprGen.ReferenceGen.sintGen[ExprGenParams, G].get(width)
+      }
+      unboundRefs <- StateGen.inspect { ExprState[ExprGenParams].unboundRefs(_) }
+    } yield {
+      val outputPort = Port(
+        NoInfo,
+        outputPortRef.name,
+        Output,
+        outputPortRef.tpe
+      )
+      Module(
+        NoInfo,
+        "foo",
+        unboundRefs.flatMap {
+          case ref if ref.name == outputPortRef.name => None
+          case ref => Some(Port(NoInfo, ref.name, Input, ref.tpe))
+        }.toSeq.sortBy(_.name) :+ outputPort,
+        Connect(NoInfo, outputPortRef, expr)
+      )
+    }
+  }
+
+  /** Runs the expression generator once and returns the generated expression
+    * wrapped in a Module and Circuit
+    */
+  def generateSingleExprCircuit[G[_]: GenMonad](): Circuit = {
+    exprMod.map { m =>
+      Circuit(NoInfo, Seq(m), m.name)
+    }.run(this).map(_._2).generate()
+  }
+}
+
+object ExprGenParams {
+
+  private case class ExprGenParamsImp(
+    maxDepth: Int,
+    maxWidth: Int,
+    generators: Seq[(Int, ExprGen[_ <: Expression])],
+    protected val unboundRefs: Set[Reference],
+    protected val namespace: Namespace) extends ExprGenParams {
+
+    protected def decrementDepth: ExprGenParams = this.copy(maxDepth = maxDepth - 1)
+    protected def incrementDepth: ExprGenParams = this.copy(maxDepth = maxDepth + 1)
+    protected def withRef(ref: Reference): ExprGenParams = this.copy(unboundRefs = unboundRefs + ref)
+  }
+
+  /** Constructs an [[ExprGenParams]] with the given parameters
+    */
+  def apply(
+    maxDepth: Int,
+    maxWidth: Int,
+    generators: Seq[(Int, ExprGen[_ <: Expression])]
+  ): ExprGenParams = {
+    require(maxWidth > 0, "maxWidth must be greater than zero")
+    ExprGenParamsImp(
+      maxDepth,
+      maxWidth,
+      generators,
+      Set.empty,
+      Namespace()
+    )
+  }
+
+  import GenMonad.syntax._
+
+  private def combineExprGens[S: ExprState, G[_]: GenMonad](
+    exprGenerators: Seq[(Int, ExprGen[_ <: Expression])]
+  )(tpe: Type): StateGen[S, G, Option[Expression]] = {
+    val boolUIntStateGens = exprGenerators.flatMap {
+      case (freq, gen) => gen.boolUIntGen[S, G].map(freq -> _.widen[Expression])
+    }
+    val uintStateGenFns = exprGenerators.flatMap {
+      case (freq, gen) => gen.uintGen[S, G].map { fn =>
+        (width: BigInt) => freq -> fn(width).widen[Expression]
+      }
+    }
+    val boolSIntStateGens = exprGenerators.flatMap {
+      case (freq, gen) => gen.boolSIntGen[S, G].map(freq -> _.widen[Expression])
+    }
+    val sintStateGenFns = exprGenerators.flatMap {
+      case (freq, gen) => gen.sintGen[S, G].map { fn =>
+        (width: BigInt) => freq -> fn(width).widen[Expression]
+      }
+    }
+    val stateGens: Seq[(Int, StateGen[S, G, Expression])] = tpe match {
+      case Utils.BoolType => boolUIntStateGens
+      case UIntType(IntWidth(width)) => uintStateGenFns.map(_(width))
+      case SIntType(IntWidth(width)) if width.toInt == 1 => boolSIntStateGens
+      case SIntType(IntWidth(width)) => sintStateGenFns.map(_(width))
+    }
+    StateGen { (s: S) =>
+      if (stateGens.isEmpty) {
+        GenMonad[G].const(s -> None)
+      } else if (stateGens.size == 1) {
+        stateGens(0)._2.run(s).map { case (ss, expr) => ss -> Some(expr) }
+      } else {
+        GenMonad.frequency(stateGens: _*).flatMap { stateGen =>
+          stateGen.run(s).map { case (ss, expr) => ss -> Some(expr) }
+        }
+      }
+    }
+  }
+
+  implicit val exprGenParamsExprStateInstance: ExprState[ExprGenParams] = new ExprState[ExprGenParams] {
+    def withRef[G[_]: GenMonad](ref: Reference): StateGen[ExprGenParams, G, Reference] = {
+      StateGen { (s: ExprGenParams) =>
+        val refx = ref.copy(name = s.namespace.newName(ref.name))
+        GenMonad[G].const(s.withRef(refx) -> refx)
+      }
+    }
+    def unboundRefs(s: ExprGenParams): Set[Reference] = s.unboundRefs
+    def maxWidth(s: ExprGenParams): Int = s.maxWidth
+
+    def exprGen[G[_]: GenMonad](tpe: Type): StateGen[ExprGenParams, G, Expression] = {
+      StateGen { (s: ExprGenParams) =>
+
+        val leafGen: Type => StateGen[ExprGenParams, G, Expression] = (tpe: Type) => combineExprGens(Seq(
+          1 -> ExprGen.LiteralGen,
+          1 -> ExprGen.ReferenceGen
+        ))(tpe).map(e => e.get) // should be safe because leaf generators are defined for all types
+
+        val branchGen: Type => StateGen[ExprGenParams, G, Expression] = (tpe: Type) => {
+          combineExprGens(s.generators)(tpe).flatMap {
+            case None => leafGen(tpe)
+            case Some(e) => StateGen.pure(e)
+          }
+        }
+
+        if (s.maxDepth > 0) {
+          // for recrusive generators, decrement maxDepth before recursing then increment when finished
+          GenMonad.frequency(
+            5 -> (branchGen(_)),
+            1 -> (leafGen(_))
+          ).flatMap(_(tpe).run(s.decrementDepth).map {
+            case (ss, e) => ss.incrementDepth -> e
+          })
+        } else {
+          leafGen(tpe).run(s)
+        }
+      }
+    }
+  }
+}
diff --git a/fuzzer/src/main/scala/firrtl/ExprState.scala b/fuzzer/src/main/scala/firrtl/ExprState.scala
new file mode 100644
index 00000000..f1a2f0d1
--- /dev/null
+++ b/fuzzer/src/main/scala/firrtl/ExprState.scala
@@ -0,0 +1,30 @@
+package firrtl.fuzzer
+
+import firrtl.ir.{Expression, Reference, Type}
+
+import scala.language.higherKinds
+
+/** A typeclass for types that represent the state of a random expression generator
+  */
+trait ExprState[State] {
+
+  /** Creates a [[StateGen]] that adds a reference to the input state and returns that reference
+    */
+  def withRef[Gen[_]: GenMonad](ref: Reference): StateGen[State, Gen, Reference]
+
+  /** Creates a [[StateGen]] that returns an [[firrtl.ir.Expression Expression]] with the specified type
+    */
+  def exprGen[Gen[_]: GenMonad](tpe: Type): StateGen[State, Gen, Expression]
+
+  /** Gets the set of unbound references
+    */
+  def unboundRefs(s: State): Set[Reference]
+
+  /** Gets the maximum allowed width of any Expression
+    */
+  def maxWidth(s: State): Int
+}
+
+object ExprState {
+  def apply[S: ExprState] = implicitly[ExprState[S]]
+}
diff --git a/fuzzer/src/main/scala/firrtl/FirrtlCompileTests.scala b/fuzzer/src/main/scala/firrtl/FirrtlCompileTests.scala
new file mode 100644
index 00000000..c891a9ab
--- /dev/null
+++ b/fuzzer/src/main/scala/firrtl/FirrtlCompileTests.scala
@@ -0,0 +1,131 @@
+package firrtl.fuzzer
+
+import com.pholser.junit.quickcheck.From
+import com.pholser.junit.quickcheck.generator.{Generator, GenerationStatus}
+import com.pholser.junit.quickcheck.random.SourceOfRandomness
+
+import firrtl.{ChirrtlForm, CircuitState, LowFirrtlCompiler}
+import firrtl.ir.Circuit
+
+import org.junit.Assert
+import org.junit.runner.RunWith
+
+import java.io.{PrintWriter, StringWriter}
+
+import edu.berkeley.cs.jqf.fuzz.Fuzz;
+import edu.berkeley.cs.jqf.fuzz.JQF;
+
+/** a GenMonad backed by [[com.pholser.junit.quickcheck.random.SourceOfRandomness SourceOfRandomness]]
+  */
+trait SourceOfRandomnessGen[A] {
+  def apply(): A
+
+  def flatMap[B](f: A => SourceOfRandomnessGen[B]): SourceOfRandomnessGen[B] =
+    SourceOfRandomnessGen { f(apply())() }
+
+  def map[B](f: A => B): SourceOfRandomnessGen[B] =
+    SourceOfRandomnessGen { f(apply()) }
+
+  def widen[B >: A]: SourceOfRandomnessGen[B] =
+    SourceOfRandomnessGen { apply() }
+}
+
+object SourceOfRandomnessGen {
+  implicit def sourceOfRandomnessGenGenMonadInstance(implicit r: SourceOfRandomness): GenMonad[SourceOfRandomnessGen] = new GenMonad[SourceOfRandomnessGen] {
+    import scala.collection.JavaConverters.seqAsJavaList
+    type G[T] = SourceOfRandomnessGen[T]
+    def flatMap[A, B](a: G[A])(f: A => G[B]): G[B] = a.flatMap(f)
+    def map[A, B](a: G[A])(f: A => B): G[B] = a.map(f)
+    def choose(min: Int, max: Int): G[Int] = SourceOfRandomnessGen {
+      r.nextLong(min, max).toInt // use r.nextLong instead of r.nextInt because r.nextInt is exclusive of max
+    }
+    def oneOf[T](items: T*): G[T] = {
+      val arr = seqAsJavaList(items)
+      const(arr).map(r.choose(_))
+    }
+    def const[T](c: T): G[T] = SourceOfRandomnessGen(c)
+    def widen[A, B >: A](ga: G[A]): G[B] = ga.widen[B]
+    def generate[A](ga: G[A]): A = ga.apply()
+  }
+
+  def apply[T](f: => T): SourceOfRandomnessGen[T] = new SourceOfRandomnessGen[T] {
+    def apply(): T = f
+  }
+}
+
+
+class FirrtlSingleModuleGenerator extends Generator[Circuit](classOf[Circuit]) {
+  override def generate(random: SourceOfRandomness, status: GenerationStatus): Circuit = {
+    implicit val r = random
+    import ExprGen._
+
+    val params = ExprGenParams(
+      maxDepth = 50,
+      maxWidth = 31,
+      generators = Seq(
+        1 -> AddDoPrimGen,
+        1 -> SubDoPrimGen,
+        1 -> MulDoPrimGen,
+        1 -> DivDoPrimGen,
+        1 -> LtDoPrimGen,
+        1 -> LeqDoPrimGen,
+        1 -> GtDoPrimGen,
+        1 -> GeqDoPrimGen,
+        1 -> EqDoPrimGen,
+        1 -> NeqDoPrimGen,
+        1 -> PadDoPrimGen,
+        1 -> ShlDoPrimGen,
+        1 -> ShrDoPrimGen,
+        1 -> DshlDoPrimGen,
+        1 -> CvtDoPrimGen,
+        1 -> NegDoPrimGen,
+        1 -> NotDoPrimGen,
+        1 -> AndDoPrimGen,
+        1 -> OrDoPrimGen,
+        1 -> XorDoPrimGen,
+        1 -> AndrDoPrimGen,
+        1 -> OrrDoPrimGen,
+        1 -> XorrDoPrimGen,
+        1 -> CatDoPrimGen,
+        1 -> BitsDoPrimGen,
+        1 -> HeadDoPrimGen,
+        1 -> TailDoPrimGen,
+        1 -> AsUIntDoPrimGen,
+        1 -> AsSIntDoPrimGen
+      )
+    )
+    params.generateSingleExprCircuit[SourceOfRandomnessGen]()
+  }
+}
+
+@RunWith(classOf[JQF])
+class FirrtlCompileTests {
+  private val lowFirrtlCompiler = new LowFirrtlCompiler()
+  private val header = "=" * 50 + "\n"
+  private val footer = header
+  private def message(c: Circuit, t: Throwable): String = {
+    val sw = new StringWriter()
+    val pw = new PrintWriter(sw)
+    t.printStackTrace(pw)
+    pw.flush()
+    header + c.serialize + "\n" + sw.toString + footer
+  }
+
+  @Fuzz
+  def compileSingleModule(@From(value = classOf[FirrtlSingleModuleGenerator]) c: Circuit) = {
+    compile(CircuitState(c, ChirrtlForm, Seq()))
+  }
+
+  // adapted from chisel3.Driver.execute and firrtl.Driver.execute
+  def compile(c: CircuitState) = {
+    val compiler = lowFirrtlCompiler
+    try {
+      val res = compiler.compile(c, Seq())
+    } catch {
+      case e: firrtl.CustomTransformException =>
+        Assert.assertTrue(message(c.circuit, e.cause), false)
+      case any : Throwable =>
+        Assert.assertTrue(message(c.circuit, any), false)
+    }
+  }
+}
diff --git a/fuzzer/src/main/scala/firrtl/FirrtlEquivalenceTest.scala b/fuzzer/src/main/scala/firrtl/FirrtlEquivalenceTest.scala
new file mode 100644
index 00000000..e0aa1707
--- /dev/null
+++ b/fuzzer/src/main/scala/firrtl/FirrtlEquivalenceTest.scala
@@ -0,0 +1,134 @@
+package firrtl.fuzzer
+
+import com.pholser.junit.quickcheck.From
+
+import edu.berkeley.cs.jqf.fuzz.Fuzz;
+import edu.berkeley.cs.jqf.fuzz.JQF;
+
+import firrtl._
+import firrtl.annotations.{Annotation, CircuitTarget, ModuleTarget, Target}
+import firrtl.ir.Circuit
+import firrtl.stage.{FirrtlCircuitAnnotation, InfoModeAnnotation, OutputFileAnnotation, TransformManager}
+import firrtl.stage.Forms.{VerilogMinimumOptimized, VerilogOptimized}
+import firrtl.stage.phases.WriteEmitted
+import firrtl.transforms.ManipulateNames
+import firrtl.util.BackendCompilationUtilities
+
+import java.io.{File, FileWriter, PrintWriter, StringWriter}
+import java.io.{File, FileWriter}
+
+import org.junit.Assert
+import org.junit.runner.RunWith
+
+object FirrtlEquivalenceTestUtils {
+
+  private class AddSuffixToTop(suffix: String) extends ManipulateNames[AddSuffixToTop] {
+    override def manipulate = (a: String, b: Namespace) => Some(b.newName(a + suffix))
+
+    override def execute(state: CircuitState): CircuitState = {
+      val block = (_: Target) => false
+      val allow: Target => Boolean = {
+        case _: ModuleTarget => true
+        case _: CircuitTarget => true
+        case _: Target => false
+      }
+      val renames = RenameMap()
+      val circuitx = run(state.circuit, renames, block, allow)
+      state.copy(circuit = circuitx, renames = Some(renames))
+    }
+  }
+
+  private def writeEmitted(state: CircuitState, outputFile: String): Unit = {
+    (new WriteEmitted).transform(state.annotations :+ OutputFileAnnotation(outputFile))
+  }
+
+  def firrtlEquivalenceTestPass(
+    circuit: Circuit,
+    referenceCompiler: TransformManager,
+    referenceAnnos: Seq[Annotation],
+    customCompiler: TransformManager,
+    customAnnos: Seq[Annotation],
+    testDir: File,
+    timesteps: Int = 1): Boolean = {
+    val baseAnnos = Seq(
+      InfoModeAnnotation("ignore"),
+      FirrtlCircuitAnnotation(circuit)
+    )
+
+    testDir.mkdirs()
+
+    val customTransforms = Seq(
+      customCompiler,
+      new AddSuffixToTop("_custom"),
+      new VerilogEmitter
+    )
+    val customResult = customTransforms.foldLeft(CircuitState(
+      circuit,
+      ChirrtlForm,
+      baseAnnos ++: EmitCircuitAnnotation(classOf[VerilogEmitter]) +: customAnnos
+    )) { case (state, transform) => transform.transform(state) }
+    val customName = customResult.circuit.main
+    val customOutputFile = new File(testDir, s"$customName.v")
+    writeEmitted(customResult, customOutputFile.toString)
+
+    val referenceTransforms = Seq(
+      referenceCompiler,
+      new AddSuffixToTop("_reference"),
+      new MinimumVerilogEmitter
+    )
+    val referenceResult = referenceTransforms.foldLeft(CircuitState(
+      circuit,
+      ChirrtlForm,
+      baseAnnos ++: EmitCircuitAnnotation(classOf[MinimumVerilogEmitter]) +: referenceAnnos
+    )) { case (state, transform) => transform.transform(state) }
+    val referenceName = referenceResult.circuit.main
+    val referenceOutputFile = new File(testDir, s"$referenceName.v")
+    writeEmitted(referenceResult, referenceOutputFile.toString)
+
+    BackendCompilationUtilities.yosysExpectSuccess(customName, referenceName, testDir, timesteps)
+  }
+}
+
+@RunWith(classOf[JQF])
+class FirrtlEquivalenceTests {
+  private val lowFirrtlCompiler = new LowFirrtlCompiler()
+  private val header = "=" * 50 + "\n"
+  private val footer = header
+  private def message(c: Circuit, t: Throwable): String = {
+    val sw = new StringWriter()
+    val pw = new PrintWriter(sw)
+    t.printStackTrace(pw)
+    pw.flush()
+    header + c.serialize + "\n" + sw.toString + footer
+  }
+  private val baseTestDir = new File("fuzzer/test_run_dir")
+
+  @Fuzz
+  def compileSingleModule(@From(value = classOf[FirrtlSingleModuleGenerator]) c: Circuit) = {
+    val testDir = new File(baseTestDir, f"${c.hashCode}%08x")
+    testDir.mkdirs()
+    val fileWriter = new FileWriter(new File(testDir, s"${c.main}.fir"))
+    fileWriter.write(c.serialize)
+    fileWriter.close()
+    val passed = try {
+      FirrtlEquivalenceTestUtils.firrtlEquivalenceTestPass(
+        circuit = c,
+        referenceCompiler = new TransformManager(VerilogMinimumOptimized),
+        referenceAnnos = Seq(),
+        customCompiler = new TransformManager(VerilogOptimized),
+        customAnnos = Seq(),
+        testDir = testDir
+      )
+    } catch {
+      case e: Throwable => {
+        Assert.assertTrue(s"exception thrown on input ${testDir}:\n${message(c, e)}", false)
+        throw e
+      }
+    }
+
+    if (!passed) {
+      Assert.assertTrue(
+        s"not equivalent to reference compiler on input ${testDir}:\n${c.serialize}\n", false)
+    }
+  }
+}
diff --git a/fuzzer/src/main/scala/firrtl/GenMonad.scala b/fuzzer/src/main/scala/firrtl/GenMonad.scala
new file mode 100644
index 00000000..36627f62
--- /dev/null
+++ b/fuzzer/src/main/scala/firrtl/GenMonad.scala
@@ -0,0 +1,96 @@
+package firrtl.fuzzer
+
+import scala.language.higherKinds
+
+/** Monads that represent a random value generator
+  */
+trait GenMonad[Gen[_]] {
+
+  /** Creates a new generator that applies the function to the output of the first generator and flattens the result
+    */
+  def flatMap[A, B](a: Gen[A])(f: A => Gen[B]): Gen[B]
+
+  /** Creates a new generator that applies the function to the output of the first generator
+    */
+  def map[A, B](a: Gen[A])(f: A => B): Gen[B]
+
+  /** Flattens a nested generator into a single generator
+    */
+  def flatten[A](gga: Gen[Gen[A]]): Gen[A] = flatMap(gga)(ga => ga)
+
+  /** Creates a generator that produces values uniformly distributed across the range
+    *
+    * The generated values are inclusive of both min and max.
+    */
+  def choose(min: Int, max: Int): Gen[Int]
+
+  /** Creates a generator that uniformly selects from a list of items
+    */
+  def oneOf[A](items: A*): Gen[A]
+
+  /** Creates a generator that always returns the same value
+    */
+  def const[A](c: A): Gen[A]
+
+  /** Returns the same generator but with a wider type parameter
+    */
+  def widen[A, B >: A](ga: Gen[A]): Gen[B]
+
+  /** Runs the given generator and returns the generated value
+    */
+  def generate[A](ga: Gen[A]): A
+}
+
+object GenMonad {
+  def apply[Gen[_]: GenMonad] = implicitly[GenMonad[Gen]]
+
+  /** Creates a generator that pick between true and false
+    */
+  def bool[Gen[_]: GenMonad]: Gen[Boolean] = GenMonad[Gen].oneOf(true, false)
+
+  /** Creates a generator that generates values based on the weights paired with each value
+    */
+  def frequency[Gen[_]: GenMonad, A](pairs: (Int, A)*): Gen[A] = {
+    assert(pairs.forall(_._1 > 0))
+    assert(pairs.size >= 1)
+    val total = pairs.map(_._1).sum
+    GenMonad[Gen].map(GenMonad[Gen].choose(1, total)) { startnum =>
+      var idx = 0
+      var num = startnum - pairs(idx)._1
+      while (num > 0) {
+        idx += 1
+        num -= pairs(idx)._1
+      }
+      pairs(idx)._2
+    }
+  }
+
+  /** Provides extension methods like .flatMap and .flatten for [[GenMonad]]s
+    */
+  object syntax {
+    final class GenMonadOps[Gen[_], A](ga: Gen[A])(implicit GM: GenMonad[Gen]) {
+      def flatMap[B](f: A => Gen[B]): Gen[B] = {
+        GM.flatMap(ga)(f)
+      }
+      def map[B](f: A => B): Gen[B] = {
+        GM.map(ga)(f)
+      }
+      def widen[B >: A]: Gen[B] = {
+        GM.widen[A, B](ga)
+      }
+      def generate(): A = {
+        GM.generate(ga)
+      }
+    }
+
+    final class GenMonadFlattenOps[Gen[_], A](gga: Gen[Gen[A]])(implicit GM: GenMonad[Gen]) {
+      def flatten: Gen[A] = GM.flatten(gga)
+    }
+
+    implicit def genMonadOps[Gen[_]: GenMonad, A](ga: Gen[A]): GenMonadOps[Gen, A] =
+      new GenMonadOps(ga)
+
+    implicit def genMonadFlattenOps[Gen[_]: GenMonad, A](gga: Gen[Gen[A]]): GenMonadFlattenOps[Gen, A] =
+      new GenMonadFlattenOps(gga)
+  }
+}
diff --git a/fuzzer/src/main/scala/firrtl/StateGen.scala b/fuzzer/src/main/scala/firrtl/StateGen.scala
new file mode 100644
index 00000000..67a02eed
--- /dev/null
+++ b/fuzzer/src/main/scala/firrtl/StateGen.scala
@@ -0,0 +1,63 @@
+package firrtl.fuzzer
+
+import scala.language.higherKinds
+
+/** Wraps a function that takes a function an produces a random state transition and value
+  *
+  * @tparam State the type of the initial and resulting state of this random computation
+  * @tparam Gen the random context that wraps the return value of this function
+  * @tparam A the type of the value returned by this function
+  */
+final case class StateGen[State, Gen[_], A](run: State => Gen[(State, A)]) {
+
+  /** Creates a new [[StateGen]] that applies the function to the result of this [[StateGen]] and flattens the result
+    */
+  def flatMap[B](fn: A => StateGen[State, Gen, B])(implicit GM: GenMonad[Gen]): StateGen[State, Gen, B] = {
+    StateGen { state =>
+      GM.flatMap(run(state)) { case (sx, a) =>
+        fn(a).run(sx)
+      }
+    }
+  }
+
+  /** Creates a new [[StateGen]] that applies the function to the result of this [[StateGen]]
+    */
+  def map[B](f: A => B)(implicit GM: GenMonad[Gen]): StateGen[State, Gen, B] = StateGen { state =>
+    GM.map(run(state)) { case (sx, a) =>
+      sx -> f(a)
+    }
+  }
+
+  /** Returns the same [[StateGen]] but with a wider result type parameter
+    */
+  def widen[B >: A](implicit GM: GenMonad[Gen]): StateGen[State, Gen, B] = StateGen { state =>
+    GM.map(run(state)) { case (state, a) => state -> a }
+  }
+}
+
+object StateGen {
+
+  /** Takes a constant value and turns it into a [[StateGen]]
+    */
+  def pure[S, Gen[_]: GenMonad, A](a: A): StateGen[S, Gen, A] = {
+    StateGen((s: S) => GenMonad[Gen].const(s -> a))
+  }
+
+  /** Takes a random value generator and turns it into a [[StateGen]]
+    */
+  def liftG[S, Gen[_]: GenMonad, A](ga: Gen[A]): StateGen[S, Gen, A] = {
+    StateGen((s: S) => GenMonad[Gen].map(ga)(s -> _))
+  }
+
+  /** Creates a [[StateGen]] produces a value from the input state without modifying it
+    */
+  def inspect[S, Gen[_]: GenMonad, A](fn: S => A): StateGen[S, Gen, A] = {
+    StateGen(s => GenMonad[Gen].const((s, fn(s))))
+  }
+
+  /** Creates a [[StateGen]] produces a random value from the input state without modifying it
+    */
+  def inspectG[S, Gen[_]: GenMonad, A](fn: S => Gen[A]): StateGen[S, Gen, A] = {
+    StateGen(s => GenMonad[Gen].map(fn(s)) { s -> _ })
+  }
+}