Added flush capability to Queue (#2030)

Co-authored-by: Megan Wachs <megan@sifive.com>
Co-authored-by: Deborah Soung <debs@sifive.com>

3 files changed, 284 insertions, 12 deletions

diff --git a/src/main/scala/chisel3/util/Decoupled.scala b/src/main/scala/chisel3/util/Decoupled.scala
index 33682020..8909ffe3 100644
--- a/src/main/scala/chisel3/util/Decoupled.scala
+++ b/src/main/scala/chisel3/util/Decoupled.scala
@@ -163,8 +163,9 @@ object DeqIO {
 /** An I/O Bundle for Queues
   * @param gen The type of data to queue
   * @param entries The max number of entries in the queue.
+  * @param hasFlush A boolean for whether the generated Queue is flushable
   */
-class QueueIO[T <: Data](private val gen: T, val entries: Int) extends Bundle
+class QueueIO[T <: Data](private val gen: T, val entries: Int, val hasFlush: Boolean = false) extends Bundle
 { // See github.com/freechipsproject/chisel3/issues/765 for why gen is a private val and proposed replacement APIs.
 
   /* These may look inverted, because the names (enq/deq) are from the perspective of the client,
@@ -177,6 +178,9 @@ class QueueIO[T <: Data](private val gen: T, val entries: Int) extends Bundle
   val deq = Flipped(DeqIO(gen))
   /** The current amount of data in the queue */
   val count = Output(UInt(log2Ceil(entries + 1).W))
+  /** When asserted, reset the enqueue and dequeue pointers, effectively flushing the queue (Optional IO for a flushable Queue)*/ 
+  val flush = if (hasFlush) Some(Input(Bool())) else None
+
 }
 
 /** A hardware module implementing a Queue
@@ -187,7 +191,7 @@ class QueueIO[T <: Data](private val gen: T, val entries: Int) extends Bundle
   * @param flow True if the inputs can be consumed on the same cycle (the inputs "flow" through the queue immediately).
   * The ''valid'' signals are coupled.
   * @param useSyncReadMem True uses SyncReadMem instead of Mem as an internal memory element.
-  *
+  * @param hasFlush True if generated queue requires a flush feature
   * @example {{{
   * val q = Module(new Queue(UInt(), 16))
   * q.io.enq <> producer.io.out
@@ -199,7 +203,8 @@ class Queue[T <: Data](val gen: T,
                        val entries: Int,
                        val pipe: Boolean = false,
                        val flow: Boolean = false,
-                       val useSyncReadMem: Boolean = false)
+                       val useSyncReadMem: Boolean = false, 
+                       val hasFlush: Boolean = false)
                       (implicit compileOptions: chisel3.CompileOptions)
     extends Module() {
   require(entries > -1, "Queue must have non-negative number of entries")
@@ -215,19 +220,20 @@ class Queue[T <: Data](val gen: T,
     }
   }
 
-  val io = IO(new QueueIO(genType, entries))
-
+  val io = IO(new QueueIO(genType, entries, hasFlush))
   val ram = if (useSyncReadMem) SyncReadMem(entries, genType, SyncReadMem.WriteFirst) else Mem(entries, genType)
   val enq_ptr = Counter(entries)
   val deq_ptr = Counter(entries)
   val maybe_full = RegInit(false.B)
-
   val ptr_match = enq_ptr.value === deq_ptr.value
   val empty = ptr_match && !maybe_full
   val full = ptr_match && maybe_full
   val do_enq = WireDefault(io.enq.fire())
   val do_deq = WireDefault(io.deq.fire())
+  val flush = io.flush.getOrElse(false.B) 
 
+  // when flush is high, empty the queue
+  // Semantically, any enqueues happen before the flush.
   when (do_enq) {
     ram(enq_ptr.value) := io.enq.bits
     enq_ptr.inc()
@@ -238,6 +244,11 @@ class Queue[T <: Data](val gen: T,
   when (do_enq =/= do_deq) {
     maybe_full := do_enq
   }
+  when(flush) {
+    enq_ptr.reset()
+    deq_ptr.reset()
+    maybe_full := false.B
+  }  
 
   io.deq.valid := !empty
   io.enq.ready := !full
@@ -265,6 +276,7 @@ class Queue[T <: Data](val gen: T,
   }
 
   val ptr_diff = enq_ptr.value - deq_ptr.value
+
   if (isPow2(entries)) {
     io.count := Mux(maybe_full && ptr_match, entries.U, 0.U) | ptr_diff
   } else {
@@ -296,7 +308,8 @@ object Queue
       entries: Int = 2,
       pipe: Boolean = false,
       flow: Boolean = false,
-      useSyncReadMem: Boolean = false): DecoupledIO[T] = {
+      useSyncReadMem: Boolean = false,
+      hasFlush: Boolean = false): DecoupledIO[T] = {
     if (entries == 0) {
       val deq = Wire(new DecoupledIO(chiselTypeOf(enq.bits)))
       deq.valid := enq.valid
@@ -304,7 +317,7 @@ object Queue
       enq.ready := deq.ready
       deq
     } else {
-      val q = Module(new Queue(chiselTypeOf(enq.bits), entries, pipe, flow, useSyncReadMem))
+      val q = Module(new Queue(chiselTypeOf(enq.bits), entries, pipe, flow, useSyncReadMem, hasFlush))
       q.io.enq.valid := enq.valid // not using <> so that override is allowed
       q.io.enq.bits := enq.bits
       enq.ready := q.io.enq.ready
diff --git a/src/test/scala/chiselTests/QueueFlushSpec.scala b/src/test/scala/chiselTests/QueueFlushSpec.scala
new file mode 100644
index 00000000..11a411a8
--- /dev/null
+++ b/src/test/scala/chiselTests/QueueFlushSpec.scala
@@ -0,0 +1,259 @@
+package chiselTests
+
+import org.scalacheck._
+
+import chisel3._
+import chisel3.testers.{BasicTester, TesterDriver}
+import chisel3.util._
+import chisel3.util.random.LFSR
+import treadle.WriteVcdAnnotation
+
+/** Test elements can be enqueued and dequeued when flush is tied to false
+ * 
+  * @param elements The sequence of elements used in the queue
+  * @param queueDepth The max number of entries in the queue
+  * @param bitWidth Integer size of the data type used in the queue
+  * @param tap Integer tap('seed') for the LFSR
+  * @param useSyncReadMem True uses SyncReadMem instead of Mem as an internal memory element
+  */
+class ThingsPassThroughFlushQueueTester(elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: Int, useSyncReadMem: Boolean) extends ThingsPassThroughTester(elements, queueDepth, bitWidth, tap, useSyncReadMem, hasFlush = true) 
+
+/** Generic flush queue tester base class
+ * 
+  * @param elements The sequence of elements used in the queue
+  * @param queueDepth The max number of entries in the queue
+  * @param bitWidth Integer size of the data type used in the queue
+  * @param tap Integer tap('seed') for the LFSR
+  * @param useSyncReadMem True uses SyncReadMem instead of Mem as an internal memory element
+  */
+abstract class FlushQueueTesterBase(elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: Int, useSyncReadMem: Boolean) extends BasicTester {
+  val q = Module(new Queue(UInt(bitWidth.W), queueDepth, hasFlush = true))
+  val elems = VecInit(elements.map(_.U))
+  val inCnt = Counter(elements.length + 1)
+  val outCnt = RegInit(0.U(log2Ceil(elements.length).W))
+  val currQCnt = RegInit(0.U(log2Ceil(5).W))
+
+  val flush: Bool = WireInit(false.B)
+  val flushRegister = RegNext(flush, init = false.B)
+  q.io.flush.get := flush
+  q.io.enq.valid := (inCnt.value < elements.length.U)
+  q.io.deq.ready := LFSR(16)(tap)
+
+  q.io.enq.bits := elems(inCnt.value)
+  when(q.io.enq.fire()) {
+    inCnt.inc()
+    currQCnt := currQCnt + 1.U //counts how many items have been enqueued
+  }
+  when(q.io.deq.fire()) {     
+    assert(flushRegister === false.B) //check queue isn't flushed (can't dequeue an empty queue)
+  }
+  when(flushRegister) { //Internal signal maybe_full is a register so some signals update on the next cycle
+    //check that queue gets flushed when queue is full
+    assert(q.io.count === 0.U)
+    assert(!q.io.deq.valid, "Expected to not be able to dequeue when flush is asserted the previous cycle")
+    assert(q.io.enq.ready, "Expected enqueue to be ready when flush was asserted the previous cycle because queue should be empty")
+  } 
+  when(inCnt.value === elements.length.U) { //stop when all entries are enqueued
+    stop()
+  }
+}
+
+/** Test queue can flush at random times
+ * 
+  * @param elements The sequence of elements used in the queue
+  * @param queueDepth The max number of entries in the queue
+  * @param bitWidth Integer size of the data type used in the queue
+  * @param tap Integer tap('seed') for the LFSR
+  * @param useSyncReadMem True uses SyncReadMem instead of Mem as an internal memory element
+  */
+class QueueGetsFlushedTester(elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: Int, useSyncReadMem: Boolean) extends FlushQueueTesterBase(elements, queueDepth, bitWidth, tap, useSyncReadMem) {
+  flush := LFSR(16)((tap + 3) % 16)  //testing a flush when flush is called randomly
+  val halfCnt = (queueDepth + 1)/2
+
+  when(q.io.deq.fire()) {
+    //ensure that what comes out is what comes in
+    assert(currQCnt <= queueDepth.U)
+    assert(elems(outCnt) === q.io.deq.bits)
+    outCnt := outCnt + 1.U
+    when (currQCnt > 0.U) {
+      currQCnt := Mux(q.io.enq.fire(), currQCnt, (currQCnt - 1.U))
+    }
+  }
+  when(flush) {
+    assert(currQCnt === 0.U || q.io.deq.valid)
+    outCnt := outCnt + Mux(q.io.enq.fire(), (currQCnt + 1.U), currQCnt)
+    currQCnt := 0.U //resets the number of items currently inside queue
+  }
+}
+
+/** Test queue can flush when empty
+ * 
+  * @param elements The sequence of elements used in the queue
+  * @param queueDepth The max number of entries in the queue
+  * @param bitWidth Integer size of the data type used in the queue
+  * @param tap Integer tap('seed') for the LFSR
+  * @param useSyncReadMem True uses SyncReadMem instead of Mem as an internal memory element
+  */
+class EmptyFlushEdgecaseTester (elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: Int, useSyncReadMem: Boolean) extends FlushQueueTesterBase(elements, queueDepth, bitWidth, tap, useSyncReadMem) {
+  val cycleCounter = Counter(elements.length + 1)
+  cycleCounter.inc() //counts every cycle
+
+  //testing a flush when queue is empty
+  flush := (cycleCounter.value === 0.U && inCnt.value === 0.U) //flushed only before anything is enqueued  
+  q.io.enq.valid := (inCnt.value < elements.length.U) && !flush
+
+  when(q.io.deq.fire()) {
+    assert(elems(outCnt) === q.io.deq.bits)
+    outCnt := outCnt + 1.U
+  }
+}
+
+/** Test queue can enqueue during a flush
+ * 
+  * @param elements The sequence of elements used in the queue
+  * @param queueDepth The max number of entries in the queue
+  * @param bitWidth Integer size of the data type used in the queue
+  * @param tap Integer tap('seed') for the LFSR
+  * @param useSyncReadMem True uses SyncReadMem instead of Mem as an internal memory element
+  */
+class EnqueueEmptyFlushEdgecaseTester (elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: Int, useSyncReadMem: Boolean) extends FlushQueueTesterBase(elements, queueDepth, bitWidth, tap, useSyncReadMem) {
+  val cycleCounter = Counter(elements.length + 1)
+  val outCounter = Counter(elements.length + 1)
+
+  //testing an enqueue during a flush
+  flush := (cycleCounter.value === 0.U && inCnt.value === 0.U) //flushed only before anything is enqueued  
+  cycleCounter.inc() //counts every cycle
+
+  when(q.io.deq.fire()) {
+    //flush and enqueue were both active on the first cycle, 
+    //so that element is flushed immediately which makes outCnt off by one
+    assert(elems(outCounter.value + 1.U) === q.io.deq.bits) //ensure that what comes out is what comes in
+    outCounter.inc()
+  }
+}
+
+/** Test queue can flush when full
+ * 
+  * @param elements The sequence of elements used in the queue
+  * @param queueDepth The max number of entries in the queue
+  * @param bitWidth Integer size of the data type used in the queue
+  * @param tap Integer tap('seed') for the LFSR
+  * @param useSyncReadMem True uses SyncReadMem instead of Mem as an internal memory element
+  */
+class FullQueueFlushEdgecaseTester (elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: Int, useSyncReadMem: Boolean) extends FlushQueueTesterBase(elements, queueDepth, bitWidth, tap, useSyncReadMem) {
+
+  //testing a flush when queue is full
+  flush := (currQCnt === queueDepth.U)
+
+  when(q.io.deq.fire()) {
+    //ensure that what comes out is what comes in
+    assert(currQCnt <= queueDepth.U)
+    assert(elems(outCnt) === q.io.deq.bits)
+    outCnt := outCnt + 1.U
+    when (currQCnt > 0.U) {
+      currQCnt := currQCnt - 1.U
+    }
+  }
+  when(flush) {
+    outCnt := outCnt + currQCnt
+    currQCnt := 0.U //resets the number of items currently inside queue
+    assert(currQCnt === 0.U || q.io.deq.valid)
+  }
+}
+
+/** Test queue can dequeue on the same cycle as a flush
+ * 
+  * @param elements The sequence of elements used in the queue
+  * @param queueDepth The max number of entries in the queue
+  * @param bitWidth Integer size of the data type used in the queue
+  * @param tap Integer tap('seed') for the LFSR
+  * @param useSyncReadMem True uses SyncReadMem instead of Mem as an internal memory element
+  */
+class DequeueFullQueueEdgecaseTester (elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: Int, useSyncReadMem: Boolean) extends FlushQueueTesterBase(elements, queueDepth, bitWidth, tap, useSyncReadMem) {
+  //Queue should be able to dequeue when queue is not empty and flush is high
+
+  //testing a flush when dequeue is called
+  flush := currQCnt === (queueDepth/2).U
+  q.io.enq.valid := !flushRegister
+  q.io.deq.ready := flush
+
+  when(q.io.deq.fire()) {
+    //ensure that what comes out is what comes in
+    assert(currQCnt <= queueDepth.U)
+    assert(elems(outCnt) === q.io.deq.bits)
+    assert(currQCnt > 0.U)
+  }
+  when(flush) {
+    //The outcount register is one count behind because the dequeue happens at the same time as the flush
+    outCnt := outCnt + currQCnt + 1.U 
+    currQCnt := 0.U //resets the number of items currently inside queue
+    assert(currQCnt === 0.U || q.io.deq.valid)
+  }
+  when(flushRegister) {
+    //check that queue gets flushed when queue is full
+    assert(q.io.deq.fire() === false.B)
+  } 
+
+}
+
+class QueueFlushSpec extends ChiselPropSpec {
+  // Disable shrinking on error.
+  implicit val noShrinkListVal = Shrink[List[Int]](_ => Stream.empty)
+  implicit val noShrinkInt = Shrink[Int](_ => Stream.empty)
+  
+  property("Queue should have things pass through") {
+    forAll(vecSizes, safeUIntN(20), Gen.choose(0, 15), Gen.oneOf(true, false)) { (depth, se, tap, isSync) =>
+      whenever(se._1 >= 1 && depth >= 1 && se._2.nonEmpty) {
+        assertTesterPasses {
+          new ThingsPassThroughFlushQueueTester(se._2, depth, se._1, tap, isSync)
+        }
+      }
+    }
+  }
+  property("Queue should flush when requested") {
+    forAll(vecSizes, safeUIntN(20), Gen.choose(0, 15), Gen.oneOf(true, false)) { (depth, se, tap, isSync) =>
+      whenever(se._1 >= 1 && depth >= 1 && se._2.nonEmpty) {
+        assertTesterPasses {
+          new QueueGetsFlushedTester(se._2, depth, se._1, tap, isSync)
+        }
+      }
+    }
+  }
+  property("Queue flush when queue is empty") {
+    forAll(vecSizes, safeUIntN(20), Gen.choose(0, 15), Gen.oneOf(true, false)) { (depth, se, tap, isSync) =>
+      whenever(se._1 >= 1 && depth >= 1 && se._2.nonEmpty) {
+        assertTesterPasses {
+          new EmptyFlushEdgecaseTester(se._2, depth, se._1, tap, isSync)
+        }
+      }
+    }
+  }
+  property("Test queue can enqueue during a flush") {
+    forAll(vecSizes, safeUIntN(20), Gen.choose(0, 15), Gen.oneOf(true, false)) { (depth, se, tap, isSync) =>
+      whenever(se._1 >= 1 && depth >= 1 && se._2.nonEmpty) {
+        assertTesterPasses {
+          new EnqueueEmptyFlushEdgecaseTester(se._2, depth, se._1, tap, isSync)
+        }
+      }
+    }
+  }
+  property("Queue flush when queue is full") {
+    forAll(vecSizes, safeUIntN(20), Gen.choose(0, 15), Gen.oneOf(true, false)) { (depth, se, tap, isSync) =>
+      whenever(se._1 >= 1 && depth >= 1 && se._2.nonEmpty) {
+        assertTesterPasses {
+          new FullQueueFlushEdgecaseTester(se._2, depth, se._1, tap, isSync)
+        }
+      }
+    }
+  }
+  property("Queue should be able to dequeue when flush is high") {
+    forAll(Gen.choose(3, 5), safeUIntN(20), Gen.choose(0, 15), Gen.oneOf(true, false)) { (depth, se, tap, isSync) =>
+      whenever(se._1 >= 1 && depth >= 1 && se._2.nonEmpty) {
+        assertTesterPasses (
+          new DequeueFullQueueEdgecaseTester(se._2, depth, se._1, tap, isSync),
+          annotations = Seq(WriteVcdAnnotation)
+        )
+      }
+    }
+  }
+}
diff --git a/src/test/scala/chiselTests/QueueSpec.scala b/src/test/scala/chiselTests/QueueSpec.scala
index 3555a13c..51b899cb 100644
--- a/src/test/scala/chiselTests/QueueSpec.scala
+++ b/src/test/scala/chiselTests/QueueSpec.scala
@@ -9,8 +9,8 @@ import chisel3.testers.BasicTester
 import chisel3.util._
 import chisel3.util.random.LFSR
 
-class ThingsPassThroughTester(elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: Int, useSyncReadMem: Boolean) extends BasicTester {
-  val q = Module(new Queue(UInt(bitWidth.W), queueDepth, useSyncReadMem = useSyncReadMem))
+class ThingsPassThroughTester(elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: Int, useSyncReadMem: Boolean, hasFlush: Boolean) extends BasicTester {
+  val q = Module(new Queue(UInt(bitWidth.W), queueDepth, useSyncReadMem = useSyncReadMem, hasFlush = hasFlush))
   val elems = VecInit(elements.map {
     _.asUInt()
   })
@@ -19,7 +19,7 @@ class ThingsPassThroughTester(elements: Seq[Int], queueDepth: Int, bitWidth: Int
 
   q.io.enq.valid := (inCnt.value < elements.length.U)
   q.io.deq.ready := LFSR(16)(tap)
-
+  q.io.flush.foreach { _ := false.B } //Flush behavior is tested in QueueFlushSpec
   q.io.enq.bits := elems(inCnt.value)
   when(q.io.enq.fire()) {
     inCnt.inc()
@@ -205,7 +205,7 @@ class QueueSpec extends ChiselPropSpec {
     forAll(vecSizes, safeUIntN(20), Gen.choose(0, 15), Gen.oneOf(true, false)) { (depth, se, tap, isSync) =>
       whenever(se._1 >= 1 && depth >= 1 && se._2.nonEmpty) {
         assertTesterPasses {
-          new ThingsPassThroughTester(se._2, depth, se._1, tap, isSync)
+          new ThingsPassThroughTester(se._2, depth, se._1, tap, isSync, false)
         }
       }
     }