Upstream intervals (#870)

Major features:

- Added Interval type, as well as PrimOps asInterval, clip, wrap, and sqz.
- Changed PrimOp names: bpset -> setp, bpshl -> incp, bpshr -> decp
- Refactored width/bound inferencer into a separate constraint solver
- Added transforms to infer, trim, and remove interval bounds
- Tests for said features

Plan to be released with 1.3

1 files changed, 53 insertions, 10 deletions

diff --git a/src/main/scala/firrtl/passes/CheckWidths.scala b/src/main/scala/firrtl/passes/CheckWidths.scala
index 07784e19..5ae5dad4 100644
--- a/src/main/scala/firrtl/passes/CheckWidths.scala
+++ b/src/main/scala/firrtl/passes/CheckWidths.scala
@@ -7,14 +7,21 @@ import firrtl.ir._
 import firrtl.PrimOps._
 import firrtl.traversals.Foreachers._
 import firrtl.Utils._
+import firrtl.constraint.IsKnown
 import firrtl.annotations.{CircuitTarget, ModuleTarget, Target, TargetToken}
 
 object CheckWidths extends Pass {
   /** The maximum allowed width for any circuit element */
   val MaxWidth = 1000000
-  val DshlMaxWidth = ceilLog2(MaxWidth + 1)
+  val DshlMaxWidth = getUIntWidth(MaxWidth)
   class UninferredWidth (info: Info, target: String) extends PassException(
-    s"""|$info : Uninferred width for target below. (Did you forget to assign to it?)
+    s"""|$info : Uninferred width for target below.serialize}. (Did you forget to assign to it?)
+        |$target""".stripMargin)
+  class UninferredBound (info: Info, target: String, bound: String) extends PassException(
+    s"""|$info : Uninferred $bound bound for target. (Did you forget to assign to it?)
+        |$target""".stripMargin)
+  class InvalidRange (info: Info, target: String, i: IntervalType) extends PassException(
+    s"""|$info : Invalid range ${i.serialize} for target below. (Are the bounds valid?)
         |$target""".stripMargin)
   class WidthTooSmall(info: Info, mname: String, b: BigInt) extends PassException(
     s"$info : [target $mname]  Width too small for constant $b.")
@@ -32,17 +39,25 @@ object CheckWidths extends Pass {
     s"$info: [target $mname] Parameter $n in tail operator is larger than input width $width.")
   class AttachWidthsNotEqual(info: Info, mname: String, eName: String, source: String) extends PassException(
     s"$info: [target $mname] Attach source $source and expression $eName must have identical widths.")
+  class DisjointSqueeze(info: Info, mname: String, squeeze: DoPrim)
+    extends PassException({
+      val toSqz = squeeze.args.head.serialize
+      val toSqzTpe = squeeze.args.head.tpe.serialize
+      val sqzTo = squeeze.args(1).serialize
+      val sqzToTpe = squeeze.args(1).tpe.serialize
+      s"$info: [module $mname] Disjoint squz currently unsupported: $toSqz:$toSqzTpe cannot be squeezed with $sqzTo's type $sqzToTpe"
+    })
 
   def run(c: Circuit): Circuit = {
     val errors = new Errors()
 
-    def check_width_w(info: Info, target: Target)(w: Width): Unit = {
-      w match {
-        case IntWidth(width) if width >= MaxWidth =>
+    def check_width_w(info: Info, target: Target, t: Type)(w: Width): Unit = {
+      (w, t) match {
+        case (IntWidth(width), _) if width >= MaxWidth =>
           errors.append(new WidthTooBig(info, target.serialize, width))
-        case w: IntWidth if w.width >= 0 =>
-        case _: IntWidth =>
+        case (w: IntWidth, f: FixedType) if (w.width < 0 && w.width == f.width) =>
           errors append new NegWidthException(info, target.serialize)
+        case (_: IntWidth, _) =>
         case _ =>
           errors append new UninferredWidth(info, target.prettyPrint("    "))
       }
@@ -57,9 +72,28 @@ object CheckWidths extends Pass {
     def check_width_t(info: Info, target: Target)(t: Type): Unit = {
       t match {
         case tt: BundleType => tt.fields.foreach(check_width_f(info, target))
+        //Supports when l = u (if closed)
+        case i@IntervalType(Closed(l), Closed(u), IntWidth(_)) if l <= u => i
+        case i:IntervalType if i.range == Some(Nil) =>
+          errors append new InvalidRange(info, target.prettyPrint("    "), i)
+          i
+        case i@IntervalType(KnownBound(l), KnownBound(u), IntWidth(p)) if l >= u =>
+          errors append new InvalidRange(info, target.prettyPrint("    "), i)
+          i
+        case i@IntervalType(KnownBound(_), KnownBound(_), IntWidth(_)) => i
+        case i@IntervalType(_: IsKnown, _, _) =>
+          errors append new UninferredBound(info, target.prettyPrint("    "), "upper")
+          i
+        case i@IntervalType(_, _: IsKnown, _) =>
+          errors append new UninferredBound(info, target.prettyPrint("    "), "lower")
+          i
+        case i@IntervalType(_, _, _) =>
+          errors append new UninferredBound(info, target.prettyPrint("    "), "lower")
+          errors append new UninferredBound(info, target.prettyPrint("    "), "upper")
+          i
         case tt => tt foreach check_width_t(info, target)
       }
-      t foreach check_width_w(info, target)
+      t foreach check_width_w(info, target, t)
     }
 
     def check_width_f(info: Info, target: Target)(f: Field): Unit =
@@ -77,6 +111,12 @@ object CheckWidths extends Pass {
             errors append new WidthTooSmall(info, target.serialize, e.value)
           case _ =>
         }
+        case sqz@DoPrim(Squeeze, Seq(a, b), _, IntervalType(Closed(min), Closed(max), _)) =>
+          (a.tpe, b.tpe) match {
+            case (IntervalType(Closed(la), Closed(ua), _), IntervalType(Closed(lb), Closed(ub), _)) if (ua < lb) || (ub < la) =>
+              errors append new DisjointSqueeze(info, target.serialize, sqz)
+            case other =>
+          }
         case DoPrim(Bits, Seq(a), Seq(hi, lo), _) if (hasWidth(a.tpe) && bitWidth(a.tpe) <= hi) =>
           errors append new BitsWidthException(info, target.serialize, hi, bitWidth(a.tpe), e.serialize)
         case DoPrim(Head, Seq(a), Seq(n), _) if (hasWidth(a.tpe) && bitWidth(a.tpe) < n) =>
@@ -87,7 +127,6 @@ object CheckWidths extends Pass {
           errors append new DshlTooBig(info, target.serialize)
         case _ =>
       }
-      //e map check_width_t(info, mname) map check_width_e(info, mname)
       e foreach check_width_e(info, target)
     }
 
@@ -111,11 +150,15 @@ object CheckWidths extends Pass {
             case ResetType =>
             case _ => errors.append(new CheckTypes.IllegalResetType(info, target.serialize, sx.name))
           }
+          if(!CheckTypes.validConnect(sx.tpe, sx.init.tpe)) {
+            val conMsg = sx.copy(info = NoInfo).serialize
+            errors.append(new CheckTypes.InvalidConnect(info, target.module, conMsg, WRef(sx), sx.init))
+          }
         case _ =>
       }
     }
 
-    def check_width_p(minfo: Info, target: ModuleTarget)(p: Port): Unit = check_width_t(p.info, target)(p.tpe)
+    def check_width_p(minfo: Info, target: ModuleTarget)(p: Port): Unit = check_width_t(p.info, target.ref(p.name))(p.tpe)
 
     def check_width_m(circuit: CircuitTarget)(m: DefModule): Unit = {
       m foreach check_width_p(m.info, circuit.module(m.name))